omapip/handle.c

Go to the documentation of this file.
00001 /* handle.c
00002 
00003    Functions for maintaining handles on objects. */
00004 
00005 /*
00006  * Copyright (c) 2009-2010,2012,2014 by Internet Systems Consortium, Inc. ("ISC")
00007  * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC")
00008  * Copyright (c) 1999-2003 by Internet Software Consortium
00009  *
00010  * Permission to use, copy, modify, and distribute this software for any
00011  * purpose with or without fee is hereby granted, provided that the above
00012  * copyright notice and this permission notice appear in all copies.
00013  *
00014  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
00015  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
00016  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
00017  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00018  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
00019  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
00020  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00021  *
00022  *   Internet Systems Consortium, Inc.
00023  *   950 Charter Street
00024  *   Redwood City, CA 94063
00025  *   <info@isc.org>
00026  *   https://www.isc.org/
00027  *
00028  */
00029 
00030 #include "dhcpd.h"
00031 
00032 #include <omapip/omapip_p.h>
00033 
00034 /* The handle table is a hierarchical tree designed for quick mapping
00035    of handle identifiers to objects.  Objects contain their own handle
00036    identifiers if they have them, so the reverse mapping is also
00037    quick.  The hierarchy is made up of table objects, each of which
00038    has 120 entries, a flag indicating whether the table is a leaf
00039    table or an indirect table, the handle of the first object covered
00040    by the table and the first object after that that's *not* covered
00041    by the table, a count of how many objects of either type are
00042    currently stored in the table, and an array of 120 entries pointing
00043    either to objects or tables.
00044 
00045    When we go to add an object to the table, we look to see if the
00046    next object handle to be assigned is covered by the outermost
00047    table.  If it is, we find the place within that table where the
00048    next handle should go, and if necessary create additional nodes in
00049    the tree to contain the new handle.  The pointer to the object is
00050    then stored in the correct position.
00051    
00052    Theoretically, we could have some code here to free up handle
00053    tables as they go out of use, but by and large handle tables won't
00054    go out of use, so this is being skipped for now.  It shouldn't be
00055    too hard to implement in the future if there's a different
00056    application. */
00057 
00058 omapi_handle_table_t *omapi_handle_table;
00059 omapi_handle_t omapi_next_handle = 1;   /* Next handle to be assigned. */
00060 
00061 #define FIND_HAND  0
00062 #define CLEAR_HAND 1
00063 
00064 static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
00065                                             omapi_handle_t,
00066                                             omapi_handle_table_t *,
00067                                             int);
00068 static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
00069                                                   omapi_handle_table_t *,
00070                                                   omapi_object_t *);
00071 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
00072 
00073 isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o)
00074 {
00075         isc_result_t status;
00076 
00077         if (o -> handle) {
00078                 *h = o -> handle;
00079                 return ISC_R_SUCCESS;
00080         }
00081         
00082         if (!omapi_handle_table) {
00083                 omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
00084                 if (!omapi_handle_table)
00085                         return ISC_R_NOMEMORY;
00086                 memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
00087                 omapi_handle_table -> first = 0;
00088                 omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE;
00089                 omapi_handle_table -> leafp = 1;
00090         }
00091 
00092         /* If this handle doesn't fit in the outer table, we need to
00093            make a new outer table.  This is a while loop in case for
00094            some reason we decide to do disjoint handle allocation,
00095            where the next level of indirection still isn't big enough
00096            to enclose the next handle ID. */
00097 
00098         while (omapi_next_handle >= omapi_handle_table -> limit) {
00099                 omapi_handle_table_t *new;
00100                 
00101                 new = dmalloc (sizeof *new, MDL);
00102                 if (!new)
00103                         return ISC_R_NOMEMORY;
00104                 memset (new, 0, sizeof *new);
00105                 new -> first = 0;
00106                 new -> limit = (omapi_handle_table -> limit *
00107                                                OMAPI_HANDLE_TABLE_SIZE);
00108                 new -> leafp = 0;
00109                 new -> children [0].table = omapi_handle_table;
00110                 omapi_handle_table = new;
00111         }
00112 
00113         /* Try to cram this handle into the existing table. */
00114         status = omapi_object_handle_in_table (omapi_next_handle,
00115                                                omapi_handle_table, o);
00116         /* If it worked, return the next handle and increment it. */
00117         if (status == ISC_R_SUCCESS) {
00118                 *h = omapi_next_handle;
00119                 omapi_next_handle++;
00120                 return ISC_R_SUCCESS;
00121         }
00122         if (status != ISC_R_NOSPACE)
00123                 return status;
00124 
00125         status = omapi_handle_table_enclose (&omapi_handle_table);
00126         if (status != ISC_R_SUCCESS)
00127                 return status;
00128 
00129         status = omapi_object_handle_in_table (omapi_next_handle,
00130                                                omapi_handle_table, o);
00131         if (status != ISC_R_SUCCESS)
00132                 return status;
00133         *h = omapi_next_handle;
00134         omapi_next_handle++;
00135 
00136         return ISC_R_SUCCESS;
00137 }
00138 
00139 static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
00140                                                   omapi_handle_table_t *table,
00141                                                   omapi_object_t *o)
00142 {
00143         omapi_handle_table_t *inner;
00144         omapi_handle_t scale, index;
00145         isc_result_t status;
00146 
00147         if (table -> first > h || table -> limit <= h)
00148                 return ISC_R_NOSPACE;
00149         
00150         /* If this is a leaf table, just stash the object in the
00151            appropriate place. */
00152         if (table -> leafp) {
00153                 status = (omapi_object_reference
00154                           (&table -> children [h - table -> first].object,
00155                            o, MDL));
00156                 if (status != ISC_R_SUCCESS)
00157                         return status;
00158                 o -> handle = h;
00159                 return ISC_R_SUCCESS;
00160         }
00161 
00162         /* Scale is the number of handles represented by each child of this
00163            table.   For a leaf table, scale would be 1.   For a first level
00164            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
00165         scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
00166 
00167         /* So the next most direct table from this one that contains the
00168            handle must be the subtable of this table whose index into this
00169            table's array of children is the handle divided by the scale. */
00170         index = (h - table -> first) / scale;
00171         inner = table -> children [index].table;
00172 
00173         /* If there is no more direct table than this one in the slot
00174            we came up with, make one. */
00175         if (!inner) {
00176                 inner = dmalloc (sizeof *inner, MDL);
00177                 if (!inner)
00178                         return ISC_R_NOMEMORY;
00179                 memset (inner, 0, sizeof *inner);
00180                 inner -> first = index * scale + table -> first;
00181                 inner -> limit = inner -> first + scale;
00182                 if (scale == OMAPI_HANDLE_TABLE_SIZE)
00183                         inner -> leafp = 1;
00184                 table -> children [index].table = inner;
00185         }
00186 
00187         status = omapi_object_handle_in_table (h, inner, o);
00188         if (status == ISC_R_NOSPACE) {
00189                 status = (omapi_handle_table_enclose
00190                           (&table -> children [index].table));
00191                 if (status != ISC_R_SUCCESS)
00192                         return status;
00193 
00194                 return omapi_object_handle_in_table
00195                         (h, table -> children [index].table, o);
00196         }
00197         return status;
00198 }
00199 
00200 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
00201 {
00202         omapi_handle_table_t *inner = *table;
00203         omapi_handle_table_t *new;
00204         int index, base, scale;
00205 
00206         /* The scale of the table we're enclosing is going to be the
00207            difference between its "first" and "limit" members.  So the
00208            scale of the table enclosing it is going to be that multiplied
00209            by the table size. */
00210         scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;
00211 
00212         /* The range that the enclosing table covers is going to be
00213            the result of subtracting the remainder of dividing the
00214            enclosed table's first entry number by the enclosing
00215            table's scale.  If handle IDs are being allocated
00216            sequentially, the enclosing table's "first" value will be
00217            the same as the enclosed table's "first" value. */
00218         base = inner -> first - inner -> first % scale;
00219 
00220         /* The index into the enclosing table at which the enclosed table
00221            will be stored is going to be the difference between the "first"
00222            value of the enclosing table and the enclosed table - zero, if
00223            we are allocating sequentially. */
00224         index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;
00225 
00226         new = dmalloc (sizeof *new, MDL);
00227         if (!new)
00228                 return ISC_R_NOMEMORY;
00229         memset (new, 0, sizeof *new);
00230         new -> first = base;
00231         new -> limit = base + scale;
00232         if (scale == OMAPI_HANDLE_TABLE_SIZE)
00233                 new -> leafp = 0;
00234         new -> children [index].table = inner;
00235         *table = new;
00236         return ISC_R_SUCCESS;
00237 }
00238 
00239 isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h)
00240 {
00241         return(omapi_handle_lookup_in(o, h, omapi_handle_table, FIND_HAND));
00242 }
00243 
00244 static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
00245                                             omapi_handle_t h,
00246                                             omapi_handle_table_t *table,
00247                                             int op)
00248 {
00249         omapi_handle_t scale, index;
00250 
00251         if (!table || table->first > h || table->limit <= h)
00252                 return(ISC_R_NOTFOUND);
00253         
00254         /* If this is a leaf table, just grab the object. */
00255         if (table->leafp) {
00256                 /* Not there? */
00257                 if (!table->children[h - table->first].object)
00258                         return(ISC_R_NOTFOUND);
00259                 if (op == CLEAR_HAND) {
00260                         table->children[h - table->first].object = NULL;
00261                         return(ISC_R_SUCCESS);
00262                 } else {
00263                         return(omapi_object_reference
00264                                (o, table->children[h - table->first].object,
00265                                 MDL));
00266                 }
00267         }
00268 
00269         /* Scale is the number of handles represented by each child of this
00270            table.   For a leaf table, scale would be 1.   For a first level
00271            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
00272         scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE;
00273 
00274         /* So the next most direct table from this one that contains the
00275            handle must be the subtable of this table whose index into this
00276            table's array of children is the handle divided by the scale. */
00277         index = (h - table->first) / scale;
00278 
00279         return(omapi_handle_lookup_in(o, h, table->children[index].table, op));
00280 }
00281 
00282 /* For looking up objects based on handles that have been sent on the wire. */
00283 isc_result_t omapi_handle_td_lookup (omapi_object_t **obj,
00284                                      omapi_typed_data_t *handle)
00285 {
00286         omapi_handle_t h;
00287 
00288         if (handle->type == omapi_datatype_int)
00289                 h = handle->u.integer;
00290         else if (handle->type == omapi_datatype_data &&
00291                  handle->u.buffer.len == sizeof h) {
00292                 memcpy(&h, handle->u.buffer.value, sizeof h);
00293                 h = ntohl(h);
00294         } else
00295                 return(DHCP_R_INVALIDARG);
00296         return(omapi_handle_lookup(obj, h));
00297 }
00298 
00299 isc_result_t omapi_handle_clear(omapi_handle_t h)
00300 {
00301         return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
00302 }

Generated on 5 Apr 2014 for ISC DHCP by  doxygen 1.6.1