Annotation of embedaddon/dhcp/omapip/handle.c, revision 1.1
1.1 ! misho 1: /* handle.c
! 2:
! 3: Functions for maintaining handles on objects. */
! 4:
! 5: /*
! 6: * Copyright (c) 2009-2010 by Internet Systems Consortium, Inc. ("ISC")
! 7: * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC")
! 8: * Copyright (c) 1999-2003 by Internet Software Consortium
! 9: *
! 10: * Permission to use, copy, modify, and distribute this software for any
! 11: * purpose with or without fee is hereby granted, provided that the above
! 12: * copyright notice and this permission notice appear in all copies.
! 13: *
! 14: * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
! 15: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
! 16: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
! 17: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
! 18: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
! 19: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
! 20: * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
! 21: *
! 22: * Internet Systems Consortium, Inc.
! 23: * 950 Charter Street
! 24: * Redwood City, CA 94063
! 25: * <info@isc.org>
! 26: * https://www.isc.org/
! 27: *
! 28: * This software has been written for Internet Systems Consortium
! 29: * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
! 30: * To learn more about Internet Systems Consortium, see
! 31: * ``https://www.isc.org/''. To learn more about Vixie Enterprises,
! 32: * see ``http://www.vix.com''. To learn more about Nominum, Inc., see
! 33: * ``http://www.nominum.com''.
! 34: */
! 35:
! 36: #include "dhcpd.h"
! 37:
! 38: #include <omapip/omapip_p.h>
! 39:
! 40: /* The handle table is a hierarchical tree designed for quick mapping
! 41: of handle identifiers to objects. Objects contain their own handle
! 42: identifiers if they have them, so the reverse mapping is also
! 43: quick. The hierarchy is made up of table objects, each of which
! 44: has 120 entries, a flag indicating whether the table is a leaf
! 45: table or an indirect table, the handle of the first object covered
! 46: by the table and the first object after that that's *not* covered
! 47: by the table, a count of how many objects of either type are
! 48: currently stored in the table, and an array of 120 entries pointing
! 49: either to objects or tables.
! 50:
! 51: When we go to add an object to the table, we look to see if the
! 52: next object handle to be assigned is covered by the outermost
! 53: table. If it is, we find the place within that table where the
! 54: next handle should go, and if necessary create additional nodes in
! 55: the tree to contain the new handle. The pointer to the object is
! 56: then stored in the correct position.
! 57:
! 58: Theoretically, we could have some code here to free up handle
! 59: tables as they go out of use, but by and large handle tables won't
! 60: go out of use, so this is being skipped for now. It shouldn't be
! 61: too hard to implement in the future if there's a different
! 62: application. */
! 63:
! 64: omapi_handle_table_t *omapi_handle_table;
! 65: omapi_handle_t omapi_next_handle = 1; /* Next handle to be assigned. */
! 66:
! 67: #define FIND_HAND 0
! 68: #define CLEAR_HAND 1
! 69:
! 70: static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
! 71: omapi_handle_t,
! 72: omapi_handle_table_t *,
! 73: int);
! 74: static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
! 75: omapi_handle_table_t *,
! 76: omapi_object_t *);
! 77: static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
! 78:
! 79: isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o)
! 80: {
! 81: isc_result_t status;
! 82:
! 83: if (o -> handle) {
! 84: *h = o -> handle;
! 85: return ISC_R_SUCCESS;
! 86: }
! 87:
! 88: if (!omapi_handle_table) {
! 89: omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
! 90: if (!omapi_handle_table)
! 91: return ISC_R_NOMEMORY;
! 92: memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
! 93: omapi_handle_table -> first = 0;
! 94: omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE;
! 95: omapi_handle_table -> leafp = 1;
! 96: }
! 97:
! 98: /* If this handle doesn't fit in the outer table, we need to
! 99: make a new outer table. This is a while loop in case for
! 100: some reason we decide to do disjoint handle allocation,
! 101: where the next level of indirection still isn't big enough
! 102: to enclose the next handle ID. */
! 103:
! 104: while (omapi_next_handle >= omapi_handle_table -> limit) {
! 105: omapi_handle_table_t *new;
! 106:
! 107: new = dmalloc (sizeof *new, MDL);
! 108: if (!new)
! 109: return ISC_R_NOMEMORY;
! 110: memset (new, 0, sizeof *new);
! 111: new -> first = 0;
! 112: new -> limit = (omapi_handle_table -> limit *
! 113: OMAPI_HANDLE_TABLE_SIZE);
! 114: new -> leafp = 0;
! 115: new -> children [0].table = omapi_handle_table;
! 116: omapi_handle_table = new;
! 117: }
! 118:
! 119: /* Try to cram this handle into the existing table. */
! 120: status = omapi_object_handle_in_table (omapi_next_handle,
! 121: omapi_handle_table, o);
! 122: /* If it worked, return the next handle and increment it. */
! 123: if (status == ISC_R_SUCCESS) {
! 124: *h = omapi_next_handle;
! 125: omapi_next_handle++;
! 126: return ISC_R_SUCCESS;
! 127: }
! 128: if (status != ISC_R_NOSPACE)
! 129: return status;
! 130:
! 131: status = omapi_handle_table_enclose (&omapi_handle_table);
! 132: if (status != ISC_R_SUCCESS)
! 133: return status;
! 134:
! 135: status = omapi_object_handle_in_table (omapi_next_handle,
! 136: omapi_handle_table, o);
! 137: if (status != ISC_R_SUCCESS)
! 138: return status;
! 139: *h = omapi_next_handle;
! 140: omapi_next_handle++;
! 141:
! 142: return ISC_R_SUCCESS;
! 143: }
! 144:
! 145: static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
! 146: omapi_handle_table_t *table,
! 147: omapi_object_t *o)
! 148: {
! 149: omapi_handle_table_t *inner;
! 150: omapi_handle_t scale, index;
! 151: isc_result_t status;
! 152:
! 153: if (table -> first > h || table -> limit <= h)
! 154: return ISC_R_NOSPACE;
! 155:
! 156: /* If this is a leaf table, just stash the object in the
! 157: appropriate place. */
! 158: if (table -> leafp) {
! 159: status = (omapi_object_reference
! 160: (&table -> children [h - table -> first].object,
! 161: o, MDL));
! 162: if (status != ISC_R_SUCCESS)
! 163: return status;
! 164: o -> handle = h;
! 165: return ISC_R_SUCCESS;
! 166: }
! 167:
! 168: /* Scale is the number of handles represented by each child of this
! 169: table. For a leaf table, scale would be 1. For a first level
! 170: of indirection, 120. For a second, 120 * 120. Et cetera. */
! 171: scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
! 172:
! 173: /* So the next most direct table from this one that contains the
! 174: handle must be the subtable of this table whose index into this
! 175: table's array of children is the handle divided by the scale. */
! 176: index = (h - table -> first) / scale;
! 177: inner = table -> children [index].table;
! 178:
! 179: /* If there is no more direct table than this one in the slot
! 180: we came up with, make one. */
! 181: if (!inner) {
! 182: inner = dmalloc (sizeof *inner, MDL);
! 183: if (!inner)
! 184: return ISC_R_NOMEMORY;
! 185: memset (inner, 0, sizeof *inner);
! 186: inner -> first = index * scale + table -> first;
! 187: inner -> limit = inner -> first + scale;
! 188: if (scale == OMAPI_HANDLE_TABLE_SIZE)
! 189: inner -> leafp = 1;
! 190: table -> children [index].table = inner;
! 191: }
! 192:
! 193: status = omapi_object_handle_in_table (h, inner, o);
! 194: if (status == ISC_R_NOSPACE) {
! 195: status = (omapi_handle_table_enclose
! 196: (&table -> children [index].table));
! 197: if (status != ISC_R_SUCCESS)
! 198: return status;
! 199:
! 200: return omapi_object_handle_in_table
! 201: (h, table -> children [index].table, o);
! 202: }
! 203: return status;
! 204: }
! 205:
! 206: static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
! 207: {
! 208: omapi_handle_table_t *inner = *table;
! 209: omapi_handle_table_t *new;
! 210: int index, base, scale;
! 211:
! 212: /* The scale of the table we're enclosing is going to be the
! 213: difference between its "first" and "limit" members. So the
! 214: scale of the table enclosing it is going to be that multiplied
! 215: by the table size. */
! 216: scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;
! 217:
! 218: /* The range that the enclosing table covers is going to be
! 219: the result of subtracting the remainder of dividing the
! 220: enclosed table's first entry number by the enclosing
! 221: table's scale. If handle IDs are being allocated
! 222: sequentially, the enclosing table's "first" value will be
! 223: the same as the enclosed table's "first" value. */
! 224: base = inner -> first - inner -> first % scale;
! 225:
! 226: /* The index into the enclosing table at which the enclosed table
! 227: will be stored is going to be the difference between the "first"
! 228: value of the enclosing table and the enclosed table - zero, if
! 229: we are allocating sequentially. */
! 230: index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;
! 231:
! 232: new = dmalloc (sizeof *new, MDL);
! 233: if (!new)
! 234: return ISC_R_NOMEMORY;
! 235: memset (new, 0, sizeof *new);
! 236: new -> first = base;
! 237: new -> limit = base + scale;
! 238: if (scale == OMAPI_HANDLE_TABLE_SIZE)
! 239: new -> leafp = 0;
! 240: new -> children [index].table = inner;
! 241: *table = new;
! 242: return ISC_R_SUCCESS;
! 243: }
! 244:
! 245: isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h)
! 246: {
! 247: return(omapi_handle_lookup_in(o, h, omapi_handle_table, FIND_HAND));
! 248: }
! 249:
! 250: static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
! 251: omapi_handle_t h,
! 252: omapi_handle_table_t *table,
! 253: int op)
! 254: {
! 255: omapi_handle_table_t *inner;
! 256: omapi_handle_t scale, index;
! 257:
! 258: if (!table || table->first > h || table->limit <= h)
! 259: return(ISC_R_NOTFOUND);
! 260:
! 261: /* If this is a leaf table, just grab the object. */
! 262: if (table->leafp) {
! 263: /* Not there? */
! 264: if (!table->children[h - table->first].object)
! 265: return(ISC_R_NOTFOUND);
! 266: if (op == CLEAR_HAND) {
! 267: table->children[h - table->first].object = NULL;
! 268: return(ISC_R_SUCCESS);
! 269: } else {
! 270: return(omapi_object_reference
! 271: (o, table->children[h - table->first].object,
! 272: MDL));
! 273: }
! 274: }
! 275:
! 276: /* Scale is the number of handles represented by each child of this
! 277: table. For a leaf table, scale would be 1. For a first level
! 278: of indirection, 120. For a second, 120 * 120. Et cetera. */
! 279: scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE;
! 280:
! 281: /* So the next most direct table from this one that contains the
! 282: handle must be the subtable of this table whose index into this
! 283: table's array of children is the handle divided by the scale. */
! 284: index = (h - table->first) / scale;
! 285: inner = table->children[index].table;
! 286:
! 287: return(omapi_handle_lookup_in(o, h, table->children[index].table, op));
! 288: }
! 289:
! 290: /* For looking up objects based on handles that have been sent on the wire. */
! 291: isc_result_t omapi_handle_td_lookup (omapi_object_t **obj,
! 292: omapi_typed_data_t *handle)
! 293: {
! 294: omapi_handle_t h;
! 295:
! 296: if (handle->type == omapi_datatype_int)
! 297: h = handle->u.integer;
! 298: else if (handle->type == omapi_datatype_data &&
! 299: handle->u.buffer.len == sizeof h) {
! 300: memcpy(&h, handle->u.buffer.value, sizeof h);
! 301: h = ntohl(h);
! 302: } else
! 303: return(ISC_R_INVALIDARG);
! 304: return(omapi_handle_lookup(obj, h));
! 305: }
! 306:
! 307: isc_result_t omapi_handle_clear(omapi_handle_t h)
! 308: {
! 309: return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
! 310: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to handle.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / dhcp / omapip