omapip/handle.c

   1 /* handle.c
   2
   3    Functions for maintaining handles on objects. */
   4
   5 /*
   6  * Copyright (c) 2009-2010,2012 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_t scale, index;
 256
 257         if (!table || table->first > h || table->limit <= h)
 258                 return(ISC_R_NOTFOUND);
 259
 260         /* If this is a leaf table, just grab the object. */
 261         if (table->leafp) {
 262                 /* Not there? */
 263                 if (!table->children[h - table->first].object)
 264                         return(ISC_R_NOTFOUND);
 265                 if (op == CLEAR_HAND) {
 266                         table->children[h - table->first].object = NULL;
 267                         return(ISC_R_SUCCESS);
 268                 } else {
 269                         return(omapi_object_reference
 270                                (o, table->children[h - table->first].object,
 271                                 MDL));
 272                 }
 273         }
 274
 275         /* Scale is the number of handles represented by each child of this
 276            table.   For a leaf table, scale would be 1.   For a first level
 277            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
 278         scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE;
 279
 280         /* So the next most direct table from this one that contains the
 281            handle must be the subtable of this table whose index into this
 282            table's array of children is the handle divided by the scale. */
 283         index = (h - table->first) / scale;
 284
 285         return(omapi_handle_lookup_in(o, h, table->children[index].table, op));
 286 }
 287
 288 /* For looking up objects based on handles that have been sent on the wire. */
 289 isc_result_t omapi_handle_td_lookup (omapi_object_t **obj,
 290                                      omapi_typed_data_t *handle)
 291 {
 292         omapi_handle_t h;
 293
 294         if (handle->type == omapi_datatype_int)
 295                 h = handle->u.integer;
 296         else if (handle->type == omapi_datatype_data &&
 297                  handle->u.buffer.len == sizeof h) {
 298                 memcpy(&h, handle->u.buffer.value, sizeof h);
 299                 h = ntohl(h);
 300         } else
 301                 return(DHCP_R_INVALIDARG);
 302         return(omapi_handle_lookup(obj, h));
 303 }
 304
 305 isc_result_t omapi_handle_clear(omapi_handle_t h)
 306 {
 307         return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
 308 }