ISC DHCP  4.3.4
A reference DHCPv4 and DHCPv6 implementation
handle.c
Go to the documentation of this file.
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 
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 **,
67  int);
68 static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
70  omapi_object_t *);
71 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
72 
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) {
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 *
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;
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;
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;
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 
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 {
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. */
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 
300 {
301  return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
302 }
isc_result_t omapi_object_reference(omapi_object_t **, omapi_object_t *, const char *, int)
Definition: alloc.c:557
void * dmalloc(unsigned, const char *, int)
Definition: alloc.c:56
#define MDL
Definition: omapip.h:568
#define DHCP_R_INVALIDARG
Definition: result.h:48
#define CLEAR_HAND
Definition: handle.c:62
omapi_datatype_t type
Definition: omapip.h:51
struct omapi_typed_data_t::@3::@4 buffer
struct __omapi_handle_table * table
Definition: omapip_p.h:238
isc_result_t omapi_handle_lookup(omapi_object_t **o, omapi_handle_t h)
Definition: handle.c:239
#define FIND_HAND
Definition: handle.c:61
#define OMAPI_HANDLE_TABLE_SIZE
Definition: omapip_p.h:230
isc_result_t omapi_handle_td_lookup(omapi_object_t **obj, omapi_typed_data_t *handle)
Definition: handle.c:283
omapi_handle_t first
Definition: omapip_p.h:233
union omapi_typed_data_t::@3 u
omapi_handle_t limit
Definition: omapip_p.h:233
isc_result_t omapi_object_handle(omapi_handle_t *h, omapi_object_t *o)
Definition: handle.c:73
unsigned int omapi_handle_t
Definition: omapip.h:37
isc_result_t omapi_handle_clear(omapi_handle_t h)
Definition: handle.c:299
omapi_handle_table_t * omapi_handle_table
Definition: handle.c:58
omapi_object_t * object
Definition: omapip_p.h:237
omapi_handle_t omapi_next_handle
Definition: handle.c:59
union __omapi_handle_table::@6 children[OMAPI_HANDLE_TABLE_SIZE]