ISC DHCP  4.4.1
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) 2004-2017 by Internet Systems Consortium, Inc. ("ISC")
7  * Copyright (c) 1999-2003 by Internet Software Consortium
8  *
9  * This Source Code Form is subject to the terms of the Mozilla Public
10  * License, v. 2.0. If a copy of the MPL was not distributed with this
11  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
12  *
13  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
14  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
16  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
19  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20  *
21  * Internet Systems Consortium, Inc.
22  * 950 Charter Street
23  * Redwood City, CA 94063
24  * <info@isc.org>
25  * https://www.isc.org/
26  *
27  */
28 
29 #include "dhcpd.h"
30 
31 #include <omapip/omapip_p.h>
32 
33 /* The handle table is a hierarchical tree designed for quick mapping
34  of handle identifiers to objects. Objects contain their own handle
35  identifiers if they have them, so the reverse mapping is also
36  quick. The hierarchy is made up of table objects, each of which
37  has 120 entries, a flag indicating whether the table is a leaf
38  table or an indirect table, the handle of the first object covered
39  by the table and the first object after that that's *not* covered
40  by the table, a count of how many objects of either type are
41  currently stored in the table, and an array of 120 entries pointing
42  either to objects or tables.
43 
44  When we go to add an object to the table, we look to see if the
45  next object handle to be assigned is covered by the outermost
46  table. If it is, we find the place within that table where the
47  next handle should go, and if necessary create additional nodes in
48  the tree to contain the new handle. The pointer to the object is
49  then stored in the correct position.
50 
51  Theoretically, we could have some code here to free up handle
52  tables as they go out of use, but by and large handle tables won't
53  go out of use, so this is being skipped for now. It shouldn't be
54  too hard to implement in the future if there's a different
55  application. */
56 
58 omapi_handle_t omapi_next_handle = 1; /* Next handle to be assigned. */
59 
60 #define FIND_HAND 0
61 #define CLEAR_HAND 1
62 
63 static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
66  int);
67 static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
69  omapi_object_t *);
70 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
71 
73 {
74  isc_result_t status;
75 
76  if (o -> handle) {
77  *h = o -> handle;
78  return ISC_R_SUCCESS;
79  }
80 
81  if (!omapi_handle_table) {
83  if (!omapi_handle_table)
84  return ISC_R_NOMEMORY;
85  memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
86  omapi_handle_table -> first = 0;
88  omapi_handle_table -> leafp = 1;
89  }
90 
91  /* If this handle doesn't fit in the outer table, we need to
92  make a new outer table. This is a while loop in case for
93  some reason we decide to do disjoint handle allocation,
94  where the next level of indirection still isn't big enough
95  to enclose the next handle ID. */
96 
97  while (omapi_next_handle >= omapi_handle_table -> limit) {
99 
100  new = dmalloc (sizeof *new, MDL);
101  if (!new)
102  return ISC_R_NOMEMORY;
103  memset (new, 0, sizeof *new);
104  new -> first = 0;
105  new -> limit = (omapi_handle_table -> limit *
107  new -> leafp = 0;
108  new -> children [0].table = omapi_handle_table;
109  omapi_handle_table = new;
110  }
111 
112  /* Try to cram this handle into the existing table. */
113  status = omapi_object_handle_in_table (omapi_next_handle,
114  omapi_handle_table, o);
115  /* If it worked, return the next handle and increment it. */
116  if (status == ISC_R_SUCCESS) {
117  *h = omapi_next_handle;
119  return ISC_R_SUCCESS;
120  }
121  if (status != ISC_R_NOSPACE)
122  return status;
123 
124  status = omapi_handle_table_enclose (&omapi_handle_table);
125  if (status != ISC_R_SUCCESS)
126  return status;
127 
128  status = omapi_object_handle_in_table (omapi_next_handle,
129  omapi_handle_table, o);
130  if (status != ISC_R_SUCCESS)
131  return status;
132  *h = omapi_next_handle;
134 
135  return ISC_R_SUCCESS;
136 }
137 
138 static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
139  omapi_handle_table_t *table,
140  omapi_object_t *o)
141 {
142  omapi_handle_table_t *inner;
143  omapi_handle_t scale, index;
144  isc_result_t status;
145 
146  if (table -> first > h || table -> limit <= h)
147  return ISC_R_NOSPACE;
148 
149  /* If this is a leaf table, just stash the object in the
150  appropriate place. */
151  if (table -> leafp) {
152  status = (omapi_object_reference
153  (&table -> children [h - table -> first].object,
154  o, MDL));
155  if (status != ISC_R_SUCCESS)
156  return status;
157  o -> handle = h;
158  return ISC_R_SUCCESS;
159  }
160 
161  /* Scale is the number of handles represented by each child of this
162  table. For a leaf table, scale would be 1. For a first level
163  of indirection, 120. For a second, 120 * 120. Et cetera. */
164  scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
165 
166  /* So the next most direct table from this one that contains the
167  handle must be the subtable of this table whose index into this
168  table's array of children is the handle divided by the scale. */
169  index = (h - table -> first) / scale;
170  inner = table -> children [index].table;
171 
172  /* If there is no more direct table than this one in the slot
173  we came up with, make one. */
174  if (!inner) {
175  inner = dmalloc (sizeof *inner, MDL);
176  if (!inner)
177  return ISC_R_NOMEMORY;
178  memset (inner, 0, sizeof *inner);
179  inner -> first = index * scale + table -> first;
180  inner -> limit = inner -> first + scale;
181  if (scale == OMAPI_HANDLE_TABLE_SIZE)
182  inner -> leafp = 1;
183  table -> children [index].table = inner;
184  }
185 
186  status = omapi_object_handle_in_table (h, inner, o);
187  if (status == ISC_R_NOSPACE) {
188  status = (omapi_handle_table_enclose
189  (&table -> children [index].table));
190  if (status != ISC_R_SUCCESS)
191  return status;
192 
193  return omapi_object_handle_in_table
194  (h, table -> children [index].table, o);
195  }
196  return status;
197 }
198 
199 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
200 {
201  omapi_handle_table_t *inner = *table;
203  int index, base, scale;
204 
205  /* The scale of the table we're enclosing is going to be the
206  difference between its "first" and "limit" members. So the
207  scale of the table enclosing it is going to be that multiplied
208  by the table size. */
209  scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;
210 
211  /* The range that the enclosing table covers is going to be
212  the result of subtracting the remainder of dividing the
213  enclosed table's first entry number by the enclosing
214  table's scale. If handle IDs are being allocated
215  sequentially, the enclosing table's "first" value will be
216  the same as the enclosed table's "first" value. */
217  base = inner -> first - inner -> first % scale;
218 
219  /* The index into the enclosing table at which the enclosed table
220  will be stored is going to be the difference between the "first"
221  value of the enclosing table and the enclosed table - zero, if
222  we are allocating sequentially. */
223  index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;
224 
225  new = dmalloc (sizeof *new, MDL);
226  if (!new)
227  return ISC_R_NOMEMORY;
228  memset (new, 0, sizeof *new);
229  new -> first = base;
230  new -> limit = base + scale;
231  if (scale == OMAPI_HANDLE_TABLE_SIZE)
232  new -> leafp = 0;
233  new -> children [index].table = inner;
234  *table = new;
235  return ISC_R_SUCCESS;
236 }
237 
239 {
240  return(omapi_handle_lookup_in(o, h, omapi_handle_table, FIND_HAND));
241 }
242 
243 static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
244  omapi_handle_t h,
245  omapi_handle_table_t *table,
246  int op)
247 {
248  omapi_handle_t scale, index;
249 
250  if (!table || table->first > h || table->limit <= h)
251  return(ISC_R_NOTFOUND);
252 
253  /* If this is a leaf table, just grab the object. */
254  if (table->leafp) {
255  /* Not there? */
256  if (!table->children[h - table->first].object)
257  return(ISC_R_NOTFOUND);
258  if (op == CLEAR_HAND) {
259  table->children[h - table->first].object = NULL;
260  return(ISC_R_SUCCESS);
261  } else {
263  (o, table->children[h - table->first].object,
264  MDL));
265  }
266  }
267 
268  /* Scale is the number of handles represented by each child of this
269  table. For a leaf table, scale would be 1. For a first level
270  of indirection, 120. For a second, 120 * 120. Et cetera. */
271  scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE;
272 
273  /* So the next most direct table from this one that contains the
274  handle must be the subtable of this table whose index into this
275  table's array of children is the handle divided by the scale. */
276  index = (h - table->first) / scale;
277 
278  return(omapi_handle_lookup_in(o, h, table->children[index].table, op));
279 }
280 
281 /* For looking up objects based on handles that have been sent on the wire. */
283  omapi_typed_data_t *handle)
284 {
285  omapi_handle_t h;
286 
287  if (handle->type == omapi_datatype_int)
288  h = handle->u.integer;
289  else if (handle->type == omapi_datatype_data &&
290  handle->u.buffer.len == sizeof h) {
291  memcpy(&h, handle->u.buffer.value, sizeof h);
292  h = ntohl(h);
293  } else
294  return(DHCP_R_INVALIDARG);
295  return(omapi_handle_lookup(obj, h));
296 }
297 
299 {
300  return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
301 }
isc_result_t omapi_object_reference(omapi_object_t **, omapi_object_t *, const char *, int)
Definition: alloc.c:571
#define MDL
Definition: omapip.h:567
#define DHCP_R_INVALIDARG
Definition: result.h:48
#define CLEAR_HAND
Definition: handle.c:61
omapi_datatype_t type
Definition: omapip.h:50
struct omapi_typed_data_t::@3::@4 buffer
struct __omapi_handle_table * table
Definition: omapip_p.h:236
isc_result_t omapi_handle_lookup(omapi_object_t **o, omapi_handle_t h)
Definition: handle.c:238
#define FIND_HAND
Definition: handle.c:60
#define OMAPI_HANDLE_TABLE_SIZE
Definition: omapip_p.h:228
isc_result_t omapi_handle_td_lookup(omapi_object_t **obj, omapi_typed_data_t *handle)
Definition: handle.c:282
omapi_handle_t first
Definition: omapip_p.h:231
union omapi_typed_data_t::@3 u
omapi_handle_t limit
Definition: omapip_p.h:231
void * dmalloc(size_t, const char *, int)
Definition: alloc.c:57
isc_result_t omapi_object_handle(omapi_handle_t *h, omapi_object_t *o)
Definition: handle.c:72
unsigned int omapi_handle_t
Definition: omapip.h:36
isc_result_t omapi_handle_clear(omapi_handle_t h)
Definition: handle.c:298
omapi_handle_table_t * omapi_handle_table
Definition: handle.c:57
omapi_object_t * object
Definition: omapip_p.h:235
omapi_handle_t omapi_next_handle
Definition: handle.c:58
union __omapi_handle_table::@6 children[OMAPI_HANDLE_TABLE_SIZE]