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