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