1: /* handle.c
2:
3: Functions for maintaining handles on objects. */
4:
5: /*
6: * Copyright (c) 2009-2010,2012 by Internet Systems Consortium, Inc. ("ISC")
7: * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC")
8: * Copyright (c) 1999-2003 by Internet Software Consortium
9: *
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.
13: *
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.
21: *
22: * Internet Systems Consortium, Inc.
23: * 950 Charter Street
24: * Redwood City, CA 94063
25: * <info@isc.org>
26: * https://www.isc.org/
27: *
28: * This software has been written for Internet Systems Consortium
29: * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
30: * To learn more about Internet Systems Consortium, see
31: * ``https://www.isc.org/''. To learn more about Vixie Enterprises,
32: * see ``http://www.vix.com''. To learn more about Nominum, Inc., see
33: * ``http://www.nominum.com''.
34: */
35:
36: #include "dhcpd.h"
37:
38: #include <omapip/omapip_p.h>
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:
67: #define FIND_HAND 0
68: #define CLEAR_HAND 1
69:
70: static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
71: omapi_handle_t,
72: omapi_handle_table_t *,
73: int);
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: {
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) {
89: omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
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:
107: new = dmalloc (sizeof *new, MDL);
108: if (!new)
109: return ISC_R_NOMEMORY;
110: memset (new, 0, sizeof *new);
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,
161: o, MDL));
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) {
182: inner = dmalloc (sizeof *inner, MDL);
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:
232: new = dmalloc (sizeof *new, MDL);
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: {
247: return(omapi_handle_lookup_in(o, h, omapi_handle_table, FIND_HAND));
248: }
249:
250: static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
251: omapi_handle_t h,
252: omapi_handle_table_t *table,
253: int op)
254: {
255: omapi_handle_t scale, index;
256:
257: if (!table || table->first > h || table->limit <= h)
258: return(ISC_R_NOTFOUND);
259:
260: /* If this is a leaf table, just grab the object. */
261: if (table->leafp) {
262: /* Not there? */
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: }
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. */
278: scale = (table->limit - table->first) / OMAPI_HANDLE_TABLE_SIZE;
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. */
283: index = (h - table->first) / scale;
284:
285: return(omapi_handle_lookup_in(o, h, table->children[index].table, op));
286: }
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: {
292: omapi_handle_t h;
293:
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);
300: } else
301: return(ISC_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));
308: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to handle.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / dhcp / omapip