[thirdparty/dhcp.git] / omapip / handle.c

/* handle.c

   Functions for maintaining handles on objects. */

/*
 * Copyright (c) 2009-2010,2012,2014 by Internet Systems Consortium, Inc. ("ISC")
 * Copyright (c) 2004-2007 by Internet Systems Consortium, Inc. ("ISC")
 * Copyright (c) 1999-2003 by Internet Software Consortium
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 *   Internet Systems Consortium, Inc.
 *   950 Charter Street
 *   Redwood City, CA 94063
 *   <info@isc.org>
 *   https://www.isc.org/
 *
 */

#include "dhcpd.h"

#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. */

#define FIND_HAND  0
#define CLEAR_HAND 1

static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
					    omapi_handle_t,
					    omapi_handle_table_t *,
					    int);
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)
{
	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, FIND_HAND));
}

static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
					    omapi_handle_t h,
					    omapi_handle_table_t *table,
					    int op)
{
	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);
		if (op == CLEAR_HAND) {
			table->children[h - table->first].object = NULL;
			return(ISC_R_SUCCESS);
		} else {
			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;

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

/* 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)
{
	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(DHCP_R_INVALIDARG);
	return(omapi_handle_lookup(obj, h));
}

isc_result_t omapi_handle_clear(omapi_handle_t h)
{
	return(omapi_handle_lookup_in(NULL, h, omapi_handle_table, CLEAR_HAND));
}
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	*/
61b844bf TL	29
fe5b0fdd DH	30	#include "dhcpd.h"
fe5b0fdd DH	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 **,
61b844bf TL	65	omapi_handle_t,
4a5098e9 SR	66	omapi_handle_table_t *,
4a5098e9 SR	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)
61b844bf TL	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,
4a5098e9 SR	247	int op)
61b844bf	248	{
61b844bf TL	249	omapi_handle_t scale, index;
61b844bf TL	250
4a5098e9 SR	251	if (!table \|\| table->first > h \|\| table->limit <= h)
4a5098e9 SR	252	return(ISC_R_NOTFOUND);
61b844bf TL	253
61b844bf TL	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;
581e37e4 TL	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	}