ISC DHCP 4.4.3-P1
A reference DHCPv4 and DHCPv6 implementation
 
Loading...
Searching...
No Matches
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-2022 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 * PO Box 360
23 * Newmarket, NH 03857 USA
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
58omapi_handle_t omapi_next_handle = 1; /* Next handle to be assigned. */
59
60#define FIND_HAND 0
61#define CLEAR_HAND 1
62
63static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
66 int);
67static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
70static 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) {
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,
115 /* If it worked, return the next handle and increment it. */
116 if (status == ISC_R_SUCCESS) {
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,
130 if (status != ISC_R_SUCCESS)
131 return status;
134
135 return ISC_R_SUCCESS;
136}
137
138static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
141{
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
199static 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
243static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
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. */
284{
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_handle(omapi_handle_t *h, omapi_object_t *o)
Definition handle.c:72
#define CLEAR_HAND
Definition handle.c:61
omapi_handle_table_t * omapi_handle_table
Definition handle.c:57
#define FIND_HAND
Definition handle.c:60
omapi_handle_t omapi_next_handle
Definition handle.c:58
isc_result_t omapi_handle_lookup(omapi_object_t **o, omapi_handle_t h)
Definition handle.c:238
isc_result_t omapi_handle_td_lookup(omapi_object_t **obj, omapi_typed_data_t *handle)
Definition handle.c:282
isc_result_t omapi_handle_clear(omapi_handle_t h)
Definition handle.c:298
#define ISC_R_SUCCESS
#define MDL
Definition omapip.h:567
struct __omapi_object omapi_object_t
Definition omapip.h:39
@ omapi_datatype_int
Definition omapip.h:42
@ omapi_datatype_data
Definition omapip.h:44
isc_result_t omapi_object_reference(omapi_object_t **, omapi_object_t *, const char *, int)
Definition alloc.c:571
unsigned int omapi_handle_t
Definition omapip.h:36
void * dmalloc(size_t, const char *, int)
Definition alloc.c:57
#define OMAPI_HANDLE_TABLE_SIZE
Definition omapip_p.h:231
struct __omapi_handle_table omapi_handle_table_t
#define DHCP_R_INVALIDARG
Definition result.h:49
omapi_handle_t first
Definition omapip_p.h:234
omapi_handle_t limit
Definition omapip_p.h:234
struct __omapi_handle_table * table
Definition omapip_p.h:239
union __omapi_handle_table::@164211330172214370145263323303307162114331216117 children[OMAPI_HANDLE_TABLE_SIZE]
omapi_object_t * object
Definition omapip_p.h:238
Definition data.h:289
struct element * value
Definition data.h:292