contrib/isc-dhcp/omapip/handle.c

   1 /* handle.c
   2
   3    Functions for maintaining handles on objects. */
   4
   5 /*
   6  * Copyright (c) 1999-2000 Internet Software Consortium.
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of The Internet Software Consortium nor the names
  19  *    of its contributors may be used to endorse or promote products derived
  20  *    from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
  23  * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  24  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  25  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  26  * DISCLAIMED.  IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
  27  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  29  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  30  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  31  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  32  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  33  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  * This software has been written for the Internet Software Consortium
  37  * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
  38  * To learn more about the Internet Software Consortium, see
  39  * ``http://www.isc.org/''.  To learn more about Vixie Enterprises,
  40  * see ``http://www.vix.com''.   To learn more about Nominum, Inc., see
  41  * ``http://www.nominum.com''.
  42  */
  43
  44 #include <omapip/omapip_p.h>
  45
  46 /* The handle table is a hierarchical tree designed for quick mapping
  47    of handle identifiers to objects.  Objects contain their own handle
  48    identifiers if they have them, so the reverse mapping is also
  49    quick.  The hierarchy is made up of table objects, each of which
  50    has 120 entries, a flag indicating whether the table is a leaf
  51    table or an indirect table, the handle of the first object covered
  52    by the table and the first object after that that's *not* covered
  53    by the table, a count of how many objects of either type are
  54    currently stored in the table, and an array of 120 entries pointing
  55    either to objects or tables.
  56
  57    When we go to add an object to the table, we look to see if the
  58    next object handle to be assigned is covered by the outermost
  59    table.  If it is, we find the place within that table where the
  60    next handle should go, and if necessary create additional nodes in
  61    the tree to contain the new handle.  The pointer to the object is
  62    then stored in the correct position.
  63
  64    Theoretically, we could have some code here to free up handle
  65    tables as they go out of use, but by and large handle tables won't
  66    go out of use, so this is being skipped for now.  It shouldn't be
  67    too hard to implement in the future if there's a different
  68    application. */
  69
  70 omapi_handle_table_t *omapi_handle_table;
  71 omapi_handle_t omapi_next_handle = 1;   /* Next handle to be assigned. */
  72
  73 static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
  74                                             omapi_handle_t,
  75                                             omapi_handle_table_t *);
  76 static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
  77                                                   omapi_handle_table_t *,
  78                                                   omapi_object_t *);
  79 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
  80
  81 isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o)
  82 {
  83         int tabix;
  84         isc_result_t status;
  85
  86         if (o -> handle) {
  87                 *h = o -> handle;
  88                 return ISC_R_SUCCESS;
  89         }
  90
  91         if (!omapi_handle_table) {
  92                 omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
  93                 if (!omapi_handle_table)
  94                         return ISC_R_NOMEMORY;
  95                 memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
  96                 omapi_handle_table -> first = 0;
  97                 omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE;
  98                 omapi_handle_table -> leafp = 1;
  99         }
 100
 101         /* If this handle doesn't fit in the outer table, we need to
 102            make a new outer table.  This is a while loop in case for
 103            some reason we decide to do disjoint handle allocation,
 104            where the next level of indirection still isn't big enough
 105            to enclose the next handle ID. */
 106
 107         while (omapi_next_handle >= omapi_handle_table -> limit) {
 108                 omapi_handle_table_t *new;
 109
 110                 new = dmalloc (sizeof *new, MDL);
 111                 if (!new)
 112                         return ISC_R_NOMEMORY;
 113                 memset (new, 0, sizeof *new);
 114                 new -> first = 0;
 115                 new -> limit = (omapi_handle_table -> limit *
 116                                                OMAPI_HANDLE_TABLE_SIZE);
 117                 new -> leafp = 0;
 118                 new -> children [0].table = omapi_handle_table;
 119                 omapi_handle_table = new;
 120         }
 121
 122         /* Try to cram this handle into the existing table. */
 123         status = omapi_object_handle_in_table (omapi_next_handle,
 124                                                omapi_handle_table, o);
 125         /* If it worked, return the next handle and increment it. */
 126         if (status == ISC_R_SUCCESS) {
 127                 *h = omapi_next_handle;
 128                 omapi_next_handle++;
 129                 return ISC_R_SUCCESS;
 130         }
 131         if (status != ISC_R_NOSPACE)
 132                 return status;
 133
 134         status = omapi_handle_table_enclose (&omapi_handle_table);
 135         if (status != ISC_R_SUCCESS)
 136                 return status;
 137
 138         status = omapi_object_handle_in_table (omapi_next_handle,
 139                                                omapi_handle_table, o);
 140         if (status != ISC_R_SUCCESS)
 141                 return status;
 142         *h = omapi_next_handle;
 143         omapi_next_handle++;
 144
 145         return ISC_R_SUCCESS;
 146 }
 147
 148 static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
 149                                                   omapi_handle_table_t *table,
 150                                                   omapi_object_t *o)
 151 {
 152         omapi_handle_table_t *inner;
 153         omapi_handle_t scale, index;
 154         isc_result_t status;
 155
 156         if (table -> first > h || table -> limit <= h)
 157                 return ISC_R_NOSPACE;
 158
 159         /* If this is a leaf table, just stash the object in the
 160            appropriate place. */
 161         if (table -> leafp) {
 162                 status = (omapi_object_reference
 163                           (&table -> children [h - table -> first].object,
 164                            o, MDL));
 165                 if (status != ISC_R_SUCCESS)
 166                         return status;
 167                 o -> handle = h;
 168                 return ISC_R_SUCCESS;
 169         }
 170
 171         /* Scale is the number of handles represented by each child of this
 172            table.   For a leaf table, scale would be 1.   For a first level
 173            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
 174         scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
 175
 176         /* So the next most direct table from this one that contains the
 177            handle must be the subtable of this table whose index into this
 178            table's array of children is the handle divided by the scale. */
 179         index = (h - table -> first) / scale;
 180         inner = table -> children [index].table;
 181
 182         /* If there is no more direct table than this one in the slot
 183            we came up with, make one. */
 184         if (!inner) {
 185                 inner = dmalloc (sizeof *inner, MDL);
 186                 if (!inner)
 187                         return ISC_R_NOMEMORY;
 188                 memset (inner, 0, sizeof *inner);
 189                 inner -> first = index * scale + table -> first;
 190                 inner -> limit = inner -> first + scale;
 191                 if (scale == OMAPI_HANDLE_TABLE_SIZE)
 192                         inner -> leafp = 1;
 193                 table -> children [index].table = inner;
 194         }
 195
 196         status = omapi_object_handle_in_table (h, inner, o);
 197         if (status == ISC_R_NOSPACE) {
 198                 status = (omapi_handle_table_enclose
 199                           (&table -> children [index].table));
 200                 if (status != ISC_R_SUCCESS)
 201                         return status;
 202
 203                 return omapi_object_handle_in_table
 204                         (h, table -> children [index].table, o);
 205         }
 206         return status;
 207 }
 208
 209 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
 210 {
 211         omapi_handle_table_t *inner = *table;
 212         omapi_handle_table_t *new;
 213         int index, base, scale;
 214
 215         /* The scale of the table we're enclosing is going to be the
 216            difference between its "first" and "limit" members.  So the
 217            scale of the table enclosing it is going to be that multiplied
 218            by the table size. */
 219         scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;
 220
 221         /* The range that the enclosing table covers is going to be
 222            the result of subtracting the remainder of dividing the
 223            enclosed table's first entry number by the enclosing
 224            table's scale.  If handle IDs are being allocated
 225            sequentially, the enclosing table's "first" value will be
 226            the same as the enclosed table's "first" value. */
 227         base = inner -> first - inner -> first % scale;
 228
 229         /* The index into the enclosing table at which the enclosed table
 230            will be stored is going to be the difference between the "first"
 231            value of the enclosing table and the enclosed table - zero, if
 232            we are allocating sequentially. */
 233         index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;
 234
 235         new = dmalloc (sizeof *new, MDL);
 236         if (!new)
 237                 return ISC_R_NOMEMORY;
 238         memset (new, 0, sizeof *new);
 239         new -> first = base;
 240         new -> limit = base + scale;
 241         if (scale == OMAPI_HANDLE_TABLE_SIZE)
 242                 new -> leafp = 0;
 243         new -> children [index].table = inner;
 244         *table = new;
 245         return ISC_R_SUCCESS;
 246 }
 247
 248 isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h)
 249 {
 250         return omapi_handle_lookup_in (o, h, omapi_handle_table);
 251 }
 252
 253 static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
 254                                             omapi_handle_t h,
 255                                             omapi_handle_table_t *table)
 256
 257 {
 258         omapi_handle_table_t *inner;
 259         omapi_handle_t scale, index;
 260
 261         if (!table || table -> first > h || table -> limit <= h)
 262                 return ISC_R_NOTFOUND;
 263
 264         /* If this is a leaf table, just grab the object. */
 265         if (table -> leafp) {
 266                 /* Not there? */
 267                 if (!table -> children [h - table -> first].object)
 268                         return ISC_R_NOTFOUND;
 269                 return omapi_object_reference
 270                         (o, table -> children [h - table -> first].object,
 271                          MDL);
 272         }
 273
 274         /* Scale is the number of handles represented by each child of this
 275            table.   For a leaf table, scale would be 1.   For a first level
 276            of indirection, 120.   For a second, 120 * 120.   Et cetera. */
 277         scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
 278
 279         /* So the next most direct table from this one that contains the
 280            handle must be the subtable of this table whose index into this
 281            table's array of children is the handle divided by the scale. */
 282         index = (h - table -> first) / scale;
 283         inner = table -> children [index].table;
 284
 285         return omapi_handle_lookup_in (o, h, table -> children [index].table);
 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         isc_result_t status;
 293         omapi_handle_t h;
 294
 295         if (handle -> type == omapi_datatype_int)
 296                 h = handle -> u.integer;
 297         else if (handle -> type == omapi_datatype_data &&
 298                  handle -> u.buffer.len == sizeof h) {
 299                 memcpy (&h, handle -> u.buffer.value, sizeof h);
 300                 h = ntohl (h);
 301         } else
 302                 return ISC_R_INVALIDARG;
 303         return omapi_handle_lookup (obj, h);
 304 }