handle.c revision 40f53fa8d9c6a4fc38c0014495e7a42b08f52481
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Copyright (C) 1996-2000 Internet Software Consortium.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Permission to use, copy, modify, and distribute this software for any
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * purpose with or without fee is hereby granted, provided that the above
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * copyright notice and this permission notice appear in all copies.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT,
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt/* $Id: handle.c,v 1.16 2000/08/01 01:32:52 tale Exp $ */
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt/* Principal Author: Ted Lemon */
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Functions for maintaining handles on objects.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * The handle table is a hierarchical tree designed for quick mapping
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * of handle identifiers to objects. Objects contain their own handle
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * identifiers if they have them, so the reverse mapping is also
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * quick. The hierarchy is made up of table objects, each of which
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * has 120 entries, a flag indicating whether the table is a leaf
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table or an indirect table, the handle of the first object covered
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * by the table and the first object after that that's *not* covered
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * by the table, a count of how many objects of either type are
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * currently stored in the table, and an array of 120 entries pointing
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * either to objects or tables.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * When we go to add an object to the table, we look to see if the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * next object handle to be assigned is covered by the outermost
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table. If it is, we find the place within that table where the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * next handle should go, and if necessary create additional nodes in
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * the tree to contain the new handle. The pointer to the object is
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * then stored in the correct position.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Theoretically, we could have some code here to free up handle
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * tables as they go out of use, but by and large handle tables won't
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * go out of use, so this is being skipped for now. It shouldn't be
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * too hard to implement in the future if there's a different
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * application.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunttypedef struct omapi_handletable {
f3ad877eb05befbc862b0233d985758c0caef29aEvan Huntstatic omapi_handle_t next_handle = 1; /* Next handle to be assigned. */
f3ad877eb05befbc862b0233d985758c0caef29aEvan Huntstatic isc_mutex_t mutex; /* To lock the 2 previous variables. */
f3ad877eb05befbc862b0233d985758c0caef29aEvan Huntstatic isc_once_t once = ISC_ONCE_INIT; /* To initialize the mutex. */
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * initialize_mutex() is called by isc_once_do in object_gethandle()
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt RUNTIME_CHECK(isc_mutex_init(&mutex) == ISC_R_SUCCESS);
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * The scale of the table we're enclosing is going to be the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * difference between its "first" and "limit" members. So the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * scale of the table enclosing it is going to be that multiplied
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * by the table size.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt scale = (inner->first - inner->limit) * OMAPI_HANDLETABLE_SIZE;
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * The range that the enclosing table covers is going to be
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * the result of subtracting the remainder of dividing the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * enclosed table's first entry number by the enclosing
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table's scale. If handle IDs are being allocated
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * sequentially, the enclosing table's "first" value will be
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * the same as the enclosed table's "first" value.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * The index into the enclosing table at which the enclosed table
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * will be stored is going to be the difference between the "first"
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * value of the enclosing table and the enclosed table - zero, if
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * we are allocating sequentially.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt idx = (base - inner->first) / OMAPI_HANDLETABLE_SIZE;
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunthandle_store(omapi_handle_t h, omapi_handletable_t *table, omapi_object_t *o) {
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * If this is a leaf table, just stash the object in the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * appropriate place.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt OBJECT_REF(&table->children[h - table->first].object, o);
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Scale is the number of handles represented by each child of this
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table. For a leaf table, scale would be 1. For a first level
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * of indirection, 120. For a second, 120 * 120. Et cetera.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt scale = (table->limit - table->first) / OMAPI_HANDLETABLE_SIZE;
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * So the next most direct table from this one that contains the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * handle must be the subtable of this table whose index into this
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table's array of children is the handle divided by the scale.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * If there is no more direct table than this one in the slot
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * we came up with, make one.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt return (handle_store(h, table->children[idx].table, o));
f3ad877eb05befbc862b0233d985758c0caef29aEvan Huntobject_gethandle(omapi_handle_t *h, omapi_object_t *o) {
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt RUNTIME_CHECK(isc_once_do(&once, initialize_mutex) == ISC_R_SUCCESS);
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt if (o->handle != 0) {
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt toptable = isc_mem_get(omapi_mctx, sizeof(*toptable));
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * If this handle doesn't fit in the outer table, we need to
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * make a new outer table. This is a while loop in case for
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * some reason we decide to do disjoint handle allocation,
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * where the next level of indirection still isn't big enough
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * to enclose the next handle ID.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Try to cram this handle into the existing table.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * If it worked, return the next handle and increment it.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Huntlookup_iterate(omapi_object_t **o, omapi_handle_t h,
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt if (table == NULL || table->first > h || table->limit <= h)
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * If this is a leaf table, just grab the object.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Not there?
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt if (table->children[h - table->first].object == NULL)
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt OBJECT_REF(o, table->children[h - table->first].object);
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * Scale is the number of handles represented by each child of this
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table. For a leaf table, scale would be 1. For a first level
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * of indirection, 120. For a second, 120 * 120. Et cetera.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt scale = (table->limit - table->first) / OMAPI_HANDLETABLE_SIZE;
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * So the next most direct table from this one that contains the
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * handle must be the subtable of this table whose index into this
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt * table's array of children is the handle divided by the scale.
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunthandle_lookup(omapi_object_t **o, omapi_handle_t h) {
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt for (i = 0; i < OMAPI_HANDLETABLE_SIZE; i++)
f3ad877eb05befbc862b0233d985758c0caef29aEvan Hunt RUNTIME_CHECK(isc_once_do(&once, initialize_mutex) == ISC_R_SUCCESS);