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