omapip/handle.c

   1 /* handle.c
   2
   3    Functions for maintaining handles on objects. */
   4
   5 /*
   6  * Copyright (c) 2009-2010,2012,2014 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  */
  29
  30 #include "dhcpd.h"
  31
  32 #include <omapip/omapip_p.h>
  33
  34 /* The handle table is a hierarchical tree designed for quick mapping
  35    of handle identifiers to objects.  Objects contain their own handle
  36    identifiers if they have them, so the reverse mapping is also
  37    quick.  The hierarchy is made up of table objects, each of which
  38    has 120 entries, a flag indicating whether the table is a leaf
  39    table or an indirect table, the handle of the first object covered
  40    by the table and the first object after that that's *not* covered
  41    by the table, a count of how many objects of either type are
  42    currently stored in the table, and an array of 120 entries pointing
  43    either to objects or tables.
  44
  45    When we go to add an object to the table, we look to see if the
  46    next object handle to be assigned is covered by the outermost
  47    table.  If it is, we find the place within that table where the
  48    next handle should go, and if necessary create additional nodes in
  49    the tree to contain the new handle.  The pointer to the object is
  50    then stored in the correct position.
  51
  52    Theoretically, we could have some code here to free up handle
  53    tables as they go out of use, but by and large handle tables won't
  54    go out of use, so this is being skipped for now.  It shouldn't be
  55    too hard to implement in the future if there's a different
  56    application. */
  57
  58 omapi_handle_table_t *omapi_handle_table;
  59 omapi_handle_t omapi_next_handle = 1;   /* Next handle to be assigned. */
  60
  61 #define FIND_HAND  0
  62 #define CLEAR_HAND 1
  63
  64 static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
  65                                             omapi_handle_t,
  66                                             omapi_handle_table_t *,
  67                                             int);
  68 static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
  69                                                   omapi_handle_table_t *,
  70                                                   omapi_object_t *);
  71 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
  72
  73 isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o)
  74 {
  75         isc_result_t status;
  76
  77         if (o -> handle) {
  78                 *h = o -> handle;
  79                 return ISC_R_SUCCESS;
  80         }
  81
  82         if (!omapi_handle_table) {
  83                 omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
  84                 if (!omapi_handle_table)
  85                         return ISC_R_NOMEMORY;
  86                 memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
  87                 omapi_handle_table -> first = 0;
  88                 omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE;
  89                 omapi_handle_table -> leafp = 1;
  90         }
  91
  92         /* If this handle doesn't fit in the outer table, we need to
  93            make a new outer table.  This is a while loop in case for
  94            some reason we decide to do disjoint handle allocation,
  95            where the next level of indirection still isn't big enough
  96            to enclose the next handle ID. */
  97
  98         while (omapi_next_handle >= omapi_handle_table -> limit) {
  99                 omapi_handle_table_t *new;
 100
 101                 new = dmalloc (sizeof *new, MDL);
 102                 if (!new)
 103                         return ISC_R_NOMEMORY;
 104                 memset (new, 0, sizeof *new);
 105                 new -> first = 0;
 106                 new -> limit = (omapi_handle_table -> limit *
 107                                                OMAPI_HANDLE_TABLE_SIZE);
 108                 new -> leafp = 0;
 109                 new -> children [0].table = omapi_handle_table;
 110                 omapi_handle_table = new;
 111         }
 112
 113         /* Try to cram this handle into the existing table. */
 114         status = omapi_object_handle_in_table (omapi_next_handle,
 115                                                omapi_handle_table, o);
 116         /* If it worked, return the next handle and increment it. */
 117         if (status == ISC_R_SUCCESS) {
 118                 *h = omapi_next_handle;
 119                 omapi_next_handle++;
 120                 return ISC_R_SUCCESS;
 121         }
 122         if (status != ISC_R_NOSPACE)
 123                 return status;
 124
 125         status = omapi_handle_table_enclose (&omapi_handle_table);
 126         if (status != ISC_R_SUCCESS)
 127                 return status;
 128
 129         status = omapi_object_handle_in_table (omapi_next_handle,
 130                                                omapi_handle_table, o);
 131         if (status != ISC_R_SUCCESS)
 132                 return status;
 133         *h = omapi_next_handle;
 134         omapi_next_handle++;
 135
 136         return ISC_R_SUCCESS;
 137 }
 138
 139 static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
 140                                                   omapi_handle_table_t *table,
 141                                                   omapi_object_t *o)
 142 {
 143         omapi_handle_table_t *inner;
 144         omapi_handle_t scale, index;
 145         isc_result_t status;
 146
 147         if (table -> first > h || table -> limit <= h)
 148                 return ISC_R_NOSPACE;
 149
 150         /* If this is a leaf table, just stash the object in the
 151            appropriate place. */
 152         if (table -> leafp) {
 153                 status = (omapi_object_reference
 154                           (&table -> children [h - table -> first].object,
 155                            o, MDL));
 156                 if (status != ISC_R_SUCCESS)
 157                         return status;
 158                 o -> handle = h;
 159                 return ISC_R_SUCCESS;
 160         }
 161
 162         /* Scale is the number of handles represented by each child of this
 163            table.   For a leaf table, scale would be 1.   For a first level
 164            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
 165         scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
 166
 167         /* So the next most direct table from this one that contains the
 168            handle must be the subtable of this table whose index into this
 169            table's array of children is the handle divided by the scale. */
 170         index = (h - table -> first) / scale;
 171         inner = table -> children [index].table;
 172
 173         /* If there is no more direct table than this one in the slot
 174            we came up with, make one. */
 175         if (!inner) {
 176                 inner = dmalloc (sizeof *inner, MDL);
 177                 if (!inner)
 178                         return ISC_R_NOMEMORY;
 179                 memset (inner, 0, sizeof *inner);
 180                 inner -> first = index * scale + table -> first;
 181                 inner -> limit = inner -> first + scale;
 182                 if (scale == OMAPI_HANDLE_TABLE_SIZE)
 183                         inner -> leafp = 1;
 184                 table -> children [index].table = inner;
 185         }
 186
 187         status = omapi_object_handle_in_table (h, inner, o);
 188         if (status == ISC_R_NOSPACE) {
 189                 status = (omapi_handle_table_enclose
 190                           (&table -> children [index].table));
 191                 if (status != ISC_R_SUCCESS)
 192                         return status;
 193
 194                 return omapi_object_handle_in_table
 195                         (h, table -> children [index].table, o);
 196         }
 197         return status;
 198 }
 199
 200 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
 201 {
 202         omapi_handle_table_t *inner = *table;
 203         omapi_handle_table_t *new;
 204         int index, base, scale;
 205
 206         /* The scale of the table we're enclosing is going to be the
 207            difference between its "first" and "limit" members.  So the
 208            scale of the table enclosing it is going to be that multiplied
 209            by the table size. */
 210         scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;
 211
 212         /* The range that the enclosing table covers is going to be
 213            the result of subtracting the remainder of dividing the
 214            enclosed table's first entry number by the enclosing
 215            table's scale.  If handle IDs are being allocated
 216            sequentially, the enclosing table's "first" value will be
 217            the same as the enclosed table's "first" value. */
 218         base = inner -> first - inner -> first % scale;
 219
 220         /* The index into the enclosing table at which the enclosed table
 221            will be stored is going to be the difference between the "first"
 222            value of the enclosing table and the enclosed table - zero, if
 223            we are allocating sequentially. */
 224         index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;
 225
 226         new = dmalloc (sizeof *new, MDL);
 227         if (!new)
 228                 return ISC_R_NOMEMORY;
 229         memset (new, 0, sizeof *new);
 230         new -> first = base;
 231         new -> limit = base + scale;
 232         if (scale == OMAPI_HANDLE_TABLE_SIZE)
 233                 new -> leafp = 0;
 234         new -> children [index].table = inner;
 235         *table = new;
 236         return ISC_R_SUCCESS;
 237 }
 238
 239 isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h)
 240 {
 241         return(omapi_handle_lookup_in(o, h, omapi_handle_table, FIND_HAND));
 242 }
 243
 244 static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
 245                                             omapi_handle_t h,
 246                                             omapi_handle_table_t *table,
 247                                             int op)
 248 {
 249         omapi_handle_t scale, index;
 250
 251         if (!table || table->first > h || table->limit <= h)
 252                 return(ISC_R_NOTFOUND);
 253
 254         /* If this is a leaf table, just grab the object. */
 255         if (table->leafp) {
 256                 /* Not there? */
 257                 if (!table->children[h - table->first].object)
 258                         return(ISC_R_NOTFOUND);
 259                 if (op == CLEAR_HAND) {
 260                         table->children[h - table->first].object = NULL;
 261                         return(ISC_R_SUCCESS);
 262                 } else {
 263                         return(omapi_object_reference
 264                                (o, table->children[h - table->first].object,
 265                                 MDL));
 266                 }
 267         }
 268
 269         /* Scale is the number of handles represented by each child of this
 270            table.   For a leaf table, scale would be 1.   For a first level
 271            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
 272         scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE;
 273
 274         /* So the next most direct table from this one that contains the
 275            handle must be the subtable of this table whose index into this
 276            table's array of children is the handle divided by the scale. */
 277         index = (h - table->first) / scale;
 278
 279         return(omapi_handle_lookup_in(o, h, table->children[index].table, op));
 280 }
 281
 282 /* For looking up objects based on handles that have been sent on the wire. */
 283 isc_result_t omapi_handle_td_lookup (omapi_object_t **obj,
 284                                      omapi_typed_data_t *handle)
 285 {
 286         omapi_handle_t h;
 287
 288         if (handle->type == omapi_datatype_int)
 289                 h = handle->u.integer;
 290         else if (handle->type == omapi_datatype_data &&
 291                  handle->u.buffer.len == sizeof h) {
 292                 memcpy(&h, handle->u.buffer.value, sizeof h);
 293                 h = ntohl(h);
 294         } else
 295                 return(DHCP_R_INVALIDARG);
 296         return(omapi_handle_lookup(obj, h));
 297 }
 298
 299 isc_result_t omapi_handle_clear(omapi_handle_t h)
 300 {
 301         return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
 302 }