]>
Commit | Line | Data |
---|---|---|
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 | ||
64 | omapi_handle_table_t *omapi_handle_table; | |
65 | omapi_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 |
70 | static 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 |
74 | static isc_result_t omapi_object_handle_in_table (omapi_handle_t, |
75 | omapi_handle_table_t *, | |
76 | omapi_object_t *); | |
77 | static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **); | |
78 | ||
79 | isc_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 | ||
145 | static 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 | ||
206 | static 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 | ||
245 | isc_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 | ||
250 | static 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. */ | |
289 | isc_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 | ||
305 | isc_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 | } |