diff options
Diffstat (limited to 'omapip/handle.c')
-rw-r--r-- | omapip/handle.c | 310 |
1 files changed, 310 insertions, 0 deletions
diff --git a/omapip/handle.c b/omapip/handle.c new file mode 100644 index 0000000..b69ef12 --- /dev/null +++ b/omapip/handle.c @@ -0,0 +1,310 @@ +/* handle.c + + Functions for maintaining handles on objects. */ + +/* + * Copyright (c) 2009-2010 by Internet Systems Consortium, Inc. ("ISC") + * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC") + * Copyright (c) 1999-2003 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT + * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * Internet Systems Consortium, Inc. + * 950 Charter Street + * Redwood City, CA 94063 + * <info@isc.org> + * https://www.isc.org/ + * + * This software has been written for Internet Systems Consortium + * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc. + * To learn more about Internet Systems Consortium, see + * ``https://www.isc.org/''. To learn more about Vixie Enterprises, + * see ``http://www.vix.com''. To learn more about Nominum, Inc., see + * ``http://www.nominum.com''. + */ + +#include "dhcpd.h" + +#include <omapip/omapip_p.h> + +/* The handle table is a hierarchical tree designed for quick mapping + of handle identifiers to objects. Objects contain their own handle + identifiers if they have them, so the reverse mapping is also + quick. The hierarchy is made up of table objects, each of which + has 120 entries, a flag indicating whether the table is a leaf + table or an indirect table, the handle of the first object covered + by the table and the first object after that that's *not* covered + by the table, a count of how many objects of either type are + currently stored in the table, and an array of 120 entries pointing + either to objects or tables. + + When we go to add an object to the table, we look to see if the + next object handle to be assigned is covered by the outermost + table. If it is, we find the place within that table where the + next handle should go, and if necessary create additional nodes in + the tree to contain the new handle. The pointer to the object is + then stored in the correct position. + + Theoretically, we could have some code here to free up handle + tables as they go out of use, but by and large handle tables won't + go out of use, so this is being skipped for now. It shouldn't be + too hard to implement in the future if there's a different + application. */ + +omapi_handle_table_t *omapi_handle_table; +omapi_handle_t omapi_next_handle = 1; /* Next handle to be assigned. */ + +#define FIND_HAND 0 +#define CLEAR_HAND 1 + +static isc_result_t omapi_handle_lookup_in (omapi_object_t **, + omapi_handle_t, + omapi_handle_table_t *, + int); +static isc_result_t omapi_object_handle_in_table (omapi_handle_t, + omapi_handle_table_t *, + omapi_object_t *); +static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **); + +isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o) +{ + isc_result_t status; + + if (o -> handle) { + *h = o -> handle; + return ISC_R_SUCCESS; + } + + if (!omapi_handle_table) { + omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL); + if (!omapi_handle_table) + return ISC_R_NOMEMORY; + memset (omapi_handle_table, 0, sizeof *omapi_handle_table); + omapi_handle_table -> first = 0; + omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE; + omapi_handle_table -> leafp = 1; + } + + /* If this handle doesn't fit in the outer table, we need to + make a new outer table. This is a while loop in case for + some reason we decide to do disjoint handle allocation, + where the next level of indirection still isn't big enough + to enclose the next handle ID. */ + + while (omapi_next_handle >= omapi_handle_table -> limit) { + omapi_handle_table_t *new; + + new = dmalloc (sizeof *new, MDL); + if (!new) + return ISC_R_NOMEMORY; + memset (new, 0, sizeof *new); + new -> first = 0; + new -> limit = (omapi_handle_table -> limit * + OMAPI_HANDLE_TABLE_SIZE); + new -> leafp = 0; + new -> children [0].table = omapi_handle_table; + omapi_handle_table = new; + } + + /* Try to cram this handle into the existing table. */ + status = omapi_object_handle_in_table (omapi_next_handle, + omapi_handle_table, o); + /* If it worked, return the next handle and increment it. */ + if (status == ISC_R_SUCCESS) { + *h = omapi_next_handle; + omapi_next_handle++; + return ISC_R_SUCCESS; + } + if (status != ISC_R_NOSPACE) + return status; + + status = omapi_handle_table_enclose (&omapi_handle_table); + if (status != ISC_R_SUCCESS) + return status; + + status = omapi_object_handle_in_table (omapi_next_handle, + omapi_handle_table, o); + if (status != ISC_R_SUCCESS) + return status; + *h = omapi_next_handle; + omapi_next_handle++; + + return ISC_R_SUCCESS; +} + +static isc_result_t omapi_object_handle_in_table (omapi_handle_t h, + omapi_handle_table_t *table, + omapi_object_t *o) +{ + omapi_handle_table_t *inner; + omapi_handle_t scale, index; + isc_result_t status; + + if (table -> first > h || table -> limit <= h) + return ISC_R_NOSPACE; + + /* If this is a leaf table, just stash the object in the + appropriate place. */ + if (table -> leafp) { + status = (omapi_object_reference + (&table -> children [h - table -> first].object, + o, MDL)); + if (status != ISC_R_SUCCESS) + return status; + o -> handle = h; + return ISC_R_SUCCESS; + } + + /* Scale is the number of handles represented by each child of this + table. For a leaf table, scale would be 1. For a first level + of indirection, 120. For a second, 120 * 120. Et cetera. */ + scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE; + + /* So the next most direct table from this one that contains the + handle must be the subtable of this table whose index into this + table's array of children is the handle divided by the scale. */ + index = (h - table -> first) / scale; + inner = table -> children [index].table; + + /* If there is no more direct table than this one in the slot + we came up with, make one. */ + if (!inner) { + inner = dmalloc (sizeof *inner, MDL); + if (!inner) + return ISC_R_NOMEMORY; + memset (inner, 0, sizeof *inner); + inner -> first = index * scale + table -> first; + inner -> limit = inner -> first + scale; + if (scale == OMAPI_HANDLE_TABLE_SIZE) + inner -> leafp = 1; + table -> children [index].table = inner; + } + + status = omapi_object_handle_in_table (h, inner, o); + if (status == ISC_R_NOSPACE) { + status = (omapi_handle_table_enclose + (&table -> children [index].table)); + if (status != ISC_R_SUCCESS) + return status; + + return omapi_object_handle_in_table + (h, table -> children [index].table, o); + } + return status; +} + +static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table) +{ + omapi_handle_table_t *inner = *table; + omapi_handle_table_t *new; + int index, base, scale; + + /* The scale of the table we're enclosing is going to be the + difference between its "first" and "limit" members. So the + scale of the table enclosing it is going to be that multiplied + by the table size. */ + scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE; + + /* The range that the enclosing table covers is going to be + the result of subtracting the remainder of dividing the + enclosed table's first entry number by the enclosing + table's scale. If handle IDs are being allocated + sequentially, the enclosing table's "first" value will be + the same as the enclosed table's "first" value. */ + base = inner -> first - inner -> first % scale; + + /* The index into the enclosing table at which the enclosed table + will be stored is going to be the difference between the "first" + value of the enclosing table and the enclosed table - zero, if + we are allocating sequentially. */ + index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE; + + new = dmalloc (sizeof *new, MDL); + if (!new) + return ISC_R_NOMEMORY; + memset (new, 0, sizeof *new); + new -> first = base; + new -> limit = base + scale; + if (scale == OMAPI_HANDLE_TABLE_SIZE) + new -> leafp = 0; + new -> children [index].table = inner; + *table = new; + return ISC_R_SUCCESS; +} + +isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h) +{ + return(omapi_handle_lookup_in(o, h, omapi_handle_table, FIND_HAND)); +} + +static isc_result_t omapi_handle_lookup_in (omapi_object_t **o, + omapi_handle_t h, + omapi_handle_table_t *table, + int op) +{ + omapi_handle_table_t *inner; + omapi_handle_t scale, index; + + if (!table || table->first > h || table->limit <= h) + return(ISC_R_NOTFOUND); + + /* If this is a leaf table, just grab the object. */ + if (table->leafp) { + /* Not there? */ + if (!table->children[h - table->first].object) + return(ISC_R_NOTFOUND); + if (op == CLEAR_HAND) { + table->children[h - table->first].object = NULL; + return(ISC_R_SUCCESS); + } else { + return(omapi_object_reference + (o, table->children[h - table->first].object, + MDL)); + } + } + + /* Scale is the number of handles represented by each child of this + table. For a leaf table, scale would be 1. For a first level + of indirection, 120. For a second, 120 * 120. Et cetera. */ + scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE; + + /* So the next most direct table from this one that contains the + handle must be the subtable of this table whose index into this + table's array of children is the handle divided by the scale. */ + index = (h - table->first) / scale; + inner = table->children[index].table; + + return(omapi_handle_lookup_in(o, h, table->children[index].table, op)); +} + +/* For looking up objects based on handles that have been sent on the wire. */ +isc_result_t omapi_handle_td_lookup (omapi_object_t **obj, + omapi_typed_data_t *handle) +{ + omapi_handle_t h; + + if (handle->type == omapi_datatype_int) + h = handle->u.integer; + else if (handle->type == omapi_datatype_data && + handle->u.buffer.len == sizeof h) { + memcpy(&h, handle->u.buffer.value, sizeof h); + h = ntohl(h); + } else + return(DHCP_R_INVALIDARG); + return(omapi_handle_lookup(obj, h)); +} + +isc_result_t omapi_handle_clear(omapi_handle_t h) +{ + return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND)); +} |