aboutsummaryrefslogtreecommitdiff
path: root/contrib/isc-dhcp/omapip/handle.c
blob: 3b99ec7c35191d0e5830f3755c1eb71dc00550a3 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
/* handle.c

   Functions for maintaining handles on objects. */

/*
 * Copyright (c) 1999-2000 Internet Software Consortium.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of The Internet Software Consortium nor the names
 *    of its contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
 * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * This software has been written for the Internet Software Consortium
 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
 * To learn more about the Internet Software Consortium, see
 * ``http://www.isc.org/''.  To learn more about Vixie Enterprises,
 * see ``http://www.vix.com''.   To learn more about Nominum, Inc., see
 * ``http://www.nominum.com''.
 */

#include <omapip/omapip_p.h>

/* The handle table is a hierarchical tree designed for quick mapping
   of handle identifiers to objects.  Objects contain their own handle
   identifiers if they have them, so the reverse mapping is also
   quick.  The hierarchy is made up of table objects, each of which
   has 120 entries, a flag indicating whether the table is a leaf
   table or an indirect table, the handle of the first object covered
   by the table and the first object after that that's *not* covered
   by the table, a count of how many objects of either type are
   currently stored in the table, and an array of 120 entries pointing
   either to objects or tables.

   When we go to add an object to the table, we look to see if the
   next object handle to be assigned is covered by the outermost
   table.  If it is, we find the place within that table where the
   next handle should go, and if necessary create additional nodes in
   the tree to contain the new handle.  The pointer to the object is
   then stored in the correct position.
   
   Theoretically, we could have some code here to free up handle
   tables as they go out of use, but by and large handle tables won't
   go out of use, so this is being skipped for now.  It shouldn't be
   too hard to implement in the future if there's a different
   application. */

omapi_handle_table_t *omapi_handle_table;
omapi_handle_t omapi_next_handle = 1;	/* Next handle to be assigned. */

static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
					    omapi_handle_t,
					    omapi_handle_table_t *);
static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
						  omapi_handle_table_t *,
						  omapi_object_t *);
static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);

isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o)
{
	int tabix;
	isc_result_t status;

	if (o -> handle) {
		*h = o -> handle;
		return ISC_R_SUCCESS;
	}
	
	if (!omapi_handle_table) {
		omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
		if (!omapi_handle_table)
			return ISC_R_NOMEMORY;
		memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
		omapi_handle_table -> first = 0;
		omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE;
		omapi_handle_table -> leafp = 1;
	}

	/* If this handle doesn't fit in the outer table, we need to
	   make a new outer table.  This is a while loop in case for
	   some reason we decide to do disjoint handle allocation,
	   where the next level of indirection still isn't big enough
	   to enclose the next handle ID. */

	while (omapi_next_handle >= omapi_handle_table -> limit) {
		omapi_handle_table_t *new;
		
		new = dmalloc (sizeof *new, MDL);
		if (!new)
			return ISC_R_NOMEMORY;
		memset (new, 0, sizeof *new);
		new -> first = 0;
		new -> limit = (omapi_handle_table -> limit *
					       OMAPI_HANDLE_TABLE_SIZE);
		new -> leafp = 0;
		new -> children [0].table = omapi_handle_table;
		omapi_handle_table = new;
	}

	/* Try to cram this handle into the existing table. */
	status = omapi_object_handle_in_table (omapi_next_handle,
					       omapi_handle_table, o);
	/* If it worked, return the next handle and increment it. */
	if (status == ISC_R_SUCCESS) {
		*h = omapi_next_handle;
		omapi_next_handle++;
		return ISC_R_SUCCESS;
	}
	if (status != ISC_R_NOSPACE)
		return status;

	status = omapi_handle_table_enclose (&omapi_handle_table);
	if (status != ISC_R_SUCCESS)
		return status;

	status = omapi_object_handle_in_table (omapi_next_handle,
					       omapi_handle_table, o);
	if (status != ISC_R_SUCCESS)
		return status;
	*h = omapi_next_handle;
	omapi_next_handle++;

	return ISC_R_SUCCESS;
}

static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
						  omapi_handle_table_t *table,
						  omapi_object_t *o)
{
	omapi_handle_table_t *inner;
	omapi_handle_t scale, index;
	isc_result_t status;

	if (table -> first > h || table -> limit <= h)
		return ISC_R_NOSPACE;
	
	/* If this is a leaf table, just stash the object in the
	   appropriate place. */
	if (table -> leafp) {
		status = (omapi_object_reference
			  (&table -> children [h - table -> first].object,
			   o, MDL));
		if (status != ISC_R_SUCCESS)
			return status;
		o -> handle = h;
		return ISC_R_SUCCESS;
	}

	/* Scale is the number of handles represented by each child of this
	   table.   For a leaf table, scale would be 1.   For a first level
	   of indirection, 120.   For a second, 120 * 120.   Et cetera. */
	scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;

	/* So the next most direct table from this one that contains the
	   handle must be the subtable of this table whose index into this
	   table's array of children is the handle divided by the scale. */
	index = (h - table -> first) / scale;
	inner = table -> children [index].table;

	/* If there is no more direct table than this one in the slot
	   we came up with, make one. */
	if (!inner) {
		inner = dmalloc (sizeof *inner, MDL);
		if (!inner)
			return ISC_R_NOMEMORY;
		memset (inner, 0, sizeof *inner);
		inner -> first = index * scale + table -> first;
		inner -> limit = inner -> first + scale;
		if (scale == OMAPI_HANDLE_TABLE_SIZE)
			inner -> leafp = 1;
		table -> children [index].table = inner;
	}

	status = omapi_object_handle_in_table (h, inner, o);
	if (status == ISC_R_NOSPACE) {
		status = (omapi_handle_table_enclose
			  (&table -> children [index].table));
		if (status != ISC_R_SUCCESS)
			return status;

		return omapi_object_handle_in_table
			(h, table -> children [index].table, o);
	}
	return status;
}

static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
{
	omapi_handle_table_t *inner = *table;
	omapi_handle_table_t *new;
	int index, base, scale;

	/* The scale of the table we're enclosing is going to be the
	   difference between its "first" and "limit" members.  So the
	   scale of the table enclosing it is going to be that multiplied
	   by the table size. */
	scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;

	/* The range that the enclosing table covers is going to be
	   the result of subtracting the remainder of dividing the
	   enclosed table's first entry number by the enclosing
	   table's scale.  If handle IDs are being allocated
	   sequentially, the enclosing table's "first" value will be
	   the same as the enclosed table's "first" value. */
	base = inner -> first - inner -> first % scale;

	/* The index into the enclosing table at which the enclosed table
	   will be stored is going to be the difference between the "first"
	   value of the enclosing table and the enclosed table - zero, if
	   we are allocating sequentially. */
	index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;

	new = dmalloc (sizeof *new, MDL);
	if (!new)
		return ISC_R_NOMEMORY;
	memset (new, 0, sizeof *new);
	new -> first = base;
	new -> limit = base + scale;
	if (scale == OMAPI_HANDLE_TABLE_SIZE)
		new -> leafp = 0;
	new -> children [index].table = inner;
	*table = new;
	return ISC_R_SUCCESS;
}

isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h)
{
	return omapi_handle_lookup_in (o, h, omapi_handle_table);
}

static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
					    omapi_handle_t h,
					    omapi_handle_table_t *table)

{
	omapi_handle_table_t *inner;
	omapi_handle_t scale, index;

	if (!table || table -> first > h || table -> limit <= h)
		return ISC_R_NOTFOUND;
	
	/* If this is a leaf table, just grab the object. */
	if (table -> leafp) {
		/* Not there? */
		if (!table -> children [h - table -> first].object)
			return ISC_R_NOTFOUND;
		return omapi_object_reference
			(o, table -> children [h - table -> first].object,
			 MDL);
	}

	/* Scale is the number of handles represented by each child of this
	   table.   For a leaf table, scale would be 1.   For a first level
	   of indirection, 120.   For a second, 120 * 120.   Et cetera. */
	scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;

	/* So the next most direct table from this one that contains the
	   handle must be the subtable of this table whose index into this
	   table's array of children is the handle divided by the scale. */
	index = (h - table -> first) / scale;
	inner = table -> children [index].table;

	return omapi_handle_lookup_in (o, h, table -> children [index].table);
}

/* For looking up objects based on handles that have been sent on the wire. */
isc_result_t omapi_handle_td_lookup (omapi_object_t **obj,
				     omapi_typed_data_t *handle)
{
	isc_result_t status;
	omapi_handle_t h;

	if (handle -> type == omapi_datatype_int)
		h = handle -> u.integer;
	else if (handle -> type == omapi_datatype_data &&
		 handle -> u.buffer.len == sizeof h) {
		memcpy (&h, handle -> u.buffer.value, sizeof h);
		h = ntohl (h);
	} else
		return ISC_R_INVALIDARG;
	return omapi_handle_lookup (obj, h);
}