[master] Add support for manipulating lease queues via a binary search.

Add support for manipluating the queues holding leaes for time
based events (free, backup, active, expired, abandoned and reserved)
via a binary search instead of walking through the linked list.

1 files changed, 695 insertions, 0 deletions

diff --git a/server/leasechain.c b/server/leasechain.c
new file mode 100644
index 00000000..d394526d
--- /dev/null
+++ b/server/leasechain.c
@@ -0,0 +1,695 @@
+/* leasechain.c
+
+   Additional support for in-memory database support */
+
+/*
+ * Copyright (c) 2015 by Internet Systems Consortium, Inc. ("ISC")
+ *
+ * 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/
+ *
+ */
+
+/*! \file server\leasechaing.c
+ *
+ * \page leasechain structures overview
+ *
+ * A brief description of the leasechain structures
+ * 
+ * This file provides additional data structures for a leasecain to
+ * provide faster access to leases on the queues associated with a pool
+ * than a linear walk.  Each pool has a set of queues: active, free, backup,
+ * expired and abandoned to track leases as they are handed out and returned.
+ * The original code use a simply linear list for each of those pools but
+ * this can present performance issues if the pool is large and the lists are
+ * long.
+ * This code adds an array on top of the list allowing us to search the list
+ * in a binary fashion instead of a linear walk.
+ *
+ * \verbatim
+ * leasechain
+ * +------------+    +-------+-------+-------+-------+
+ * | lease list |--> | lease | lease | lease | lease |....
+ * | start      |    |  ptr  |  ptr  |  ptr  |  ptr  |
+ * | end        |    +-------+-------+-------+-------+
+ * | max        |                |       |
+ * +------------+                V       V
+ *                          +-------+  +-------+
+ *                          | lease |  | lease |
+ *                          |       |  |       |
+ *                          |  next |->|  next |->NULL
+ *                   NULL<- | prev  |<-| prev  |
+ *                          +-------+  +-------+
+ * 
+ * The linked list is maintained in an ordered state.  Inserting an entry is
+ * accomplished by doing a binary search on the array to find the proper place
+ * in the list and then updating the pointers in the linked list to include the
+ * new entry.  The entry is added into the array by copying the remainder of 
+ * the array to provide space for the new entry.
+ * Removing an entry is the reverse.
+ * The arrays for the queues will be pre-allocated but not all of them will be
+ * large enough to hold all of the leases.  If additional space is required the
+ * array will be grown.
+ */
+
+#include "dhcpd.h"
+
+#if defined (BINARY_LEASES)
+/* Default number number of lease pointers to add to the leasechain array
+ * everytime it grows beyond the current size
+ */
+#define LC_GROWTH_DELTA 256
+
+/*!
+ *
+ * \brief Check if leasechain isn't empty
+ *
+ * \param lc The leasechain to check
+ *
+ * \return 1 if leasechain isn't empty
+ */
+int
+lc_not_empty( struct leasechain *lc ) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC empty check %s:%d", MDL);
+	INSIST(lc != NULL);
+#endif
+
+	return (lc->nelem > 0 ? 1 : 0);
+}
+
+/*!
+ *
+ * \brief Get the first lease from a leasechain
+ *
+ * \param lc The leasechain to check
+ *
+ * \return A pointer to the first lease from a lease chain, or NULL if none found
+ */
+struct lease *
+lc_get_first_lease(struct leasechain *lc) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC Get first %s:%d", MDL);
+	INSIST(lc != NULL);
+	INSIST(lc->total >= lc->nelem);
+#endif
+
+	if (lc->nelem > 0) {
+		return (lc->list)[0];
+	}
+	return (NULL);
+}
+
+/*!
+ *
+ * \brief Get the next lease from the chain, based on the lease passed in.
+ *
+ * \param lc The leasechain to check
+ * \param lp The lease to start from
+ *
+ * \return The next lease in the ordered list after lp
+ */
+struct lease *
+lc_get_next(struct leasechain *lc, struct lease *lp) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC Get next %s:%d", MDL);
+	INSIST(lc != NULL);
+	INSIST(lp != NULL);
+#endif
+
+	return lp->next;
+}
+
+/*!
+ *
+ * \brief Find the best position for inserting a lease
+ *
+ * Given a potential range of the array to insert the lease into this routine
+ * will recursively examine the range to find the proper place in which to
+ * insert the lease.
+ * 
+ * \param lc The leasechain to add the lease to
+ * \param lp The lease to insert
+ * \param min The minium index of the potential range for insertion
+ * \param max The maximum index of the potential range for insertion
+ *
+ * \return The index of the array entry to insert the lease
+ */
+size_t 
+lc_binary_search_insert_point(struct leasechain *lc,
+			      struct lease *lp,
+			      size_t min, size_t max)
+{
+	size_t mid_index = ((max - min)/2) + min;
+
+	if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
+	    ((lc->list[mid_index]->sort_time == lp->sort_time) &&
+	     (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
+		if (mid_index == min) {
+			/* insert in the min position, as sort_time is larger */
+			return (min);
+		}
+		/* try again with lower half of list */
+		return (lc_binary_search_insert_point(lc, lp,
+						      min, mid_index - 1));
+	} else  if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
+		    ((lc->list[mid_index]->sort_time == lp->sort_time) && 
+		     (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
+		if (mid_index == max) {
+			/* insert in mid_index + 1 as sort_time is smaller */
+			return (mid_index+1);
+		}
+		/* try again with upper half of list */
+		return (lc_binary_search_insert_point(lc, lp,
+						      mid_index + 1, max));
+	}
+
+	/* sort_time and sort_tiebreaker match, so insert in this position */
+	return (mid_index);
+}
+
+/*!
+ *
+ * \brief Find an exact match for a lease
+ *
+ * Given a potential range of the array to search this routine
+ * will recursively examine the range to find the proper lease
+ * 
+ * \param lc The leasechain to check
+ * \param lp The lease to find
+ * \param min The minium index of the search range
+ * \param max The maximum index of the search range
+ *
+ * \return The index of the array entry for the lease, SIZE_MAX if the lease
+ * wasn't found
+ */
+
+size_t
+lc_binary_search_lease(struct leasechain *lc,
+		       struct lease *lp,
+		       size_t min, size_t max)
+{
+	size_t mid_index;
+	size_t i;
+
+	if (max < min) {
+		/* lease not found */
+		return (SIZE_MAX);
+	}
+
+	mid_index = ((max - min)/2) + min;
+
+	if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
+	    ((lc->list[mid_index]->sort_time == lp->sort_time) &&
+	     (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
+		if (mid_index == min) {
+			/* lease not found */
+			return (SIZE_MAX);
+		} 
+		/* try the lower half of the list */
+		return (lc_binary_search_lease(lc, lp, min, mid_index - 1));
+	} else if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
+		   ((lc->list[mid_index]->sort_time == lp->sort_time) &&
+		    (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
+		/* try the upper half of the list */	  
+		return (lc_binary_search_lease(lc, lp, mid_index + 1, max));
+	}
+
+	/*
+	 * As sort_time/sort_tiebreaker may not be unique in the list, once we
+	 * find a match, we need to look before and after from this position
+	 * for all matching sort_time/sort_tiebreaker until we find the exact
+	 * lease or until no matching lease is found
+	 */
+	if (lp == lc->list[mid_index]) {
+		return (mid_index);
+	}
+
+	/* Check out entries below the mid_index */
+	if (mid_index > min) {
+		/* We will break out of the loop if we either go past the
+	         * canddiates or hit the end of the range when i == min.  As
+		 * i is unsigned we can't check it in the for loop itself.
+		 */
+		for (i = mid_index - 1; ; i--) {
+			if (lp == lc->list[i]) {
+				return (i);
+			}
+
+			/* Are we done with this range? */
+			if ((i == min) ||
+			    ((lc->list[i]->sort_time != lp->sort_time) || 
+			     ((lc->list[i]->sort_time == lp->sort_time) &&
+			      (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker)))) {
+				break;
+			}
+		}
+	}
+
+	/* Check out entries above the mid_index */
+	if (mid_index < max) {
+		/* We will break out of the loop if we either go past the 
+	         * canddiates or hit the end of the range when i == max.
+		 */
+		for (i = mid_index + 1; i <= max; i++) {
+			if (lp == lc->list[i]) {
+				return (i);
+			}
+
+			if ((lc->list[i]->sort_time != lp->sort_time) ||
+			    ((lc->list[i]->sort_time == lp->sort_time) &&
+			     (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker))) {
+				break;
+			}
+		}
+	}
+
+	/* Lease not found */
+	return (SIZE_MAX);
+}
+
+/*!
+ *
+ * \brief Increase the size of the array for the lease chain
+ *
+ * \param lc The leasechain to expand
+ *
+ * If we are unable to allocate memory we log a fatal error.  There's
+ * not much else to do as we can't figure out where to put the lease.
+ *
+ * If we can allocate memory we copy the old lease chain to the new
+ * lease chain and free the old.
+ */
+void
+lc_grow_chain(struct leasechain *lc) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC grow lease chain max was %zu, %s:%d", lc->total, MDL);
+#endif
+
+	void *p;
+	size_t temp_size;
+
+	if (lc->growth == 0) 
+		temp_size = lc->total + LC_GROWTH_DELTA;
+	else
+		temp_size = lc->total + lc->growth;
+
+	/* try to allocate the memory */
+	p = dmalloc(sizeof(struct lease *) * temp_size, MDL);
+	if (p == NULL) {
+		log_fatal("LC grow, unable to allocated memory %s:%d", MDL);
+	}
+
+	/* Success, copy the lease chain and install the new one */
+	if (lc->list != NULL) {
+		memcpy(p, lc->list, sizeof(struct lease *) * lc->nelem);
+		dfree(lc->list, MDL);
+	}
+	lc->list = (struct lease **) p;
+	lc->total = temp_size;
+
+	return;
+}
+
+
+/*!
+ *
+ * \brief Link a lease to a lease chain position
+ *
+ * This function may increase the size of the lease chain if necessary and will
+ * probably need to move entries in the lease chain around.
+ *
+ * \param lc The leasechain to update
+ * \param lp The lease to insert
+ * \param n  The position in which to insert the lease
+ *
+ */
+void
+lc_link_lcp(struct leasechain *lc, struct lease *lp, size_t n) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC link lcp %s:%d", MDL);
+	INSIST (lc != NULL);
+	INSIST (lp != NULL);
+#endif
+
+	if (lc->nelem == lc->total) {
+		lc_grow_chain(lc);
+	}
+
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC Link lcp position %zu, elem %zu, %s:%d",
+		  n, lc->nelem, MDL);
+#endif
+
+	/* create room for the new pointer */
+	if (n < lc->nelem) {
+#if defined (DEBUG_BINARY_LEASES)
+		log_debug("LC link lcp moving position %zu, moving %zu. %s:%d",
+			  n, (lc->nelem-n), MDL);
+#endif
+		memmove(lc->list + n + 1,  lc->list + n,
+			sizeof(struct lease *) * (lc->nelem-n));
+	}
+
+	/* clean any stale pointer info from this position before calling 
+	 * lease_reference as it won't work if pointer is not NULL
+	 */
+	lc->list[n] = NULL;
+	lease_reference(&(lc->list[n]), lp, MDL);
+
+	lc->nelem++;
+
+	lp->lc = lc;
+
+	return;
+}
+
+/*!
+ * 
+ * \brief Insert the lease at the specified position in both the lease chain
+ * and the linked list
+ *
+ * This function may increase the size of the lease chain if necessary and will
+ * probably need to move entries in the lease chain around.
+ * \param lc The leasechain to update
+ * \param lp The lease to insert
+ * \param n  The position in which to insert the lease
+ *
+ */
+void
+lc_add_lease_pos(struct leasechain *lc, struct lease *lp, size_t pos) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC Add lease position %zu, %s:%d", pos, MDL);
+	INSIST (lc != NULL);
+	INSIST (lp != NULL);
+#endif
+	lc_link_lcp(lc, lp, pos);
+
+#if 0
+	/* this shoudln't be necessary, if we still have pointers on
+	 *  the lease being inserted things are broken
+	 */
+	if (lp->prev) {
+		lease_dereference(&lp->prev, MDL);
+	}
+	if (lp->next) {
+		lease_dereference(&lp->next, MDL);
+	}
+#endif
+
+	/* not the first element? */
+	if (pos > 0) {
+		if (lc->list[pos-1]->next) {
+			lease_dereference(&(lc->list[pos-1]->next), MDL);
+		}
+		lease_reference(&(lc->list[pos-1]->next), lp, MDL);
+		lease_reference(&lp->prev, lc->list[pos-1], MDL );
+	}
+
+	/* not the last element? we've already bumped nelem when linking
+	 * into the lease chain so nelem should never be zero here */
+	if (pos < (lc->nelem-1)) {
+		if (lc->list[pos+1]->prev) {
+			lease_dereference(&(lc->list[pos+1]->prev), MDL);
+		}
+		lease_reference(&(lc->list[pos+1]->prev), lp,  MDL);
+		lease_reference(&lp->next, lc->list[pos+1], MDL);
+	}
+
+	return;
+}
+
+#ifdef POINTER_DEBUG
+/*!
+ *
+ * \brief Debug only code, check the lease to verify it is sorted
+ *
+ * \param lc The leasechain to verify
+ *
+ * Calls log_fatal if the leasechain is not properly sorted
+ */
+void
+lc_check_lc_sort_order(struct leasechain *lc) {
+	size_t i;
+	TIME t = 0;
+	long int tiebreak = 0;
+
+	log_debug("LC check sort %s:%d", MDL);
+	for (i = 0; i < lc->nelem; i++ ) {
+		if ((lc->list[i]->sort_time < t)  ||
+		    ((lc->list[i]->sort_time == t) && 
+		     (lc->list[i]->tiebreaker < tiebreaker))) {
+			if (i > 0) {
+				print_lease(lc->list[i-1]);
+			}
+			print_lease(lc->list[i]);
+			if (i < lc->nelem - 1) {
+				print_lease(lc->list[i+1]);
+			}
+			log_fatal("lc[%p] not sorted properly", lc);
+		}
+
+		t = lc->list[i]->sort_time;
+		tiebreak = lc->list[i]->sort_tiebreaker;
+	}
+}
+#endif
+
+/*!
+ *
+ * \brief Add a lease into the sorted lease and lease chain
+ * The sort_time is set by the caller while the sort_tiebreaker is set here
+ * The value doesn't much matter as long as it prvoides a way to have different
+ * values in most of the leases.
+ * 
+ * When choosing a value for tiebreak we choose:
+ *  0 for the first lease in the queue
+ *  0 if the lease is going to the end of the queue with a sort_time greater
+ *  than that of the current last lease
+ *  previous tiebreaker + 1 if it is going to the end of the queue with a
+ *  sort_time equal to that of the current last lease
+ *  random if none of the above fit
+ *
+ * During startup when we can take advantage of the fact that leases may already
+ * be sorted and so check the end of the list to see if we can simply add the
+ * lease to the end.
+ * 
+ * \param lc The leasechain in which to insert the lease
+ * \param lp The lease to insert
+ *
+ */
+void
+lc_add_sorted_lease(struct leasechain *lc, struct lease *lp) {
+	size_t pos;
+
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC add sorted %s:%d", MDL);
+	INSIST (lc != NULL);
+	INSIST (lp != NULL);
+#endif
+	if (lc->nelem == 0) {
+		/* The first lease start with a tiebreak of 0 and add it at
+		 * the first position */
+		lp->sort_tiebreaker = 0;
+
+		lc_add_lease_pos(lc, lp, 0);
+		/* log_debug("LC add sorted done, %s:%d", MDL); */
+
+		return;
+	}
+
+	if (lp->sort_time > lc->list[lc->nelem-1]->sort_time) {
+		/* Adding to end of queue, with a different sort time */
+		lp->sort_tiebreaker = 0;
+		pos = lc->nelem;
+	} else if (lp->sort_time == lc->list[lc->nelem-1]->sort_time) {
+		/* Adding to end of queue, with the same sort time */
+		if (lc->list[lc->nelem-1]->sort_tiebreaker < LONG_MAX)
+			lp->sort_tiebreaker =
+			  lc->list[lc->nelem-1]->sort_tiebreaker+1;
+		else
+			lp->sort_tiebreaker = LONG_MAX;
+		pos = lc->nelem;
+	} else {
+		/* Adding somewhere in the queue, just pick a random value */
+		lp->sort_tiebreaker = random();
+		pos = lc_binary_search_insert_point(lc, lp, 0, lc->nelem - 1);
+	}
+
+	/* Finally add it to the queue */
+	lc_add_lease_pos(lc, lp, pos);
+
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC add sorted complete position %zu, elements %zu, %s:%d",
+		  pos, lc->nelem, MDL);
+#endif
+
+#ifdef POINTER_DEBUG
+	lc_check_lc_sort_order(lc);
+#endif
+}
+
+/*!
+ *
+ * \brief Remove the Nth pointer from a leasechain structure and update counters.
+ * The pointers in the array will be moved to fill in the hole if necessary.
+ *
+ * \param lc The lease chain to update
+ * \param n the entry to remove from the lease chain
+ */
+void
+lc_unlink_lcp(struct leasechain *lc, size_t n) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC unlink lcp %s:%d", MDL);
+
+	/* element index to remove must be less than the number of elements present */
+	INSIST(n < lc->nelem);
+#endif
+
+	/* Clear the pointer from the lease back to the LC */
+	lc->list[n]->lc = NULL;
+
+	/* Clear the pointer from the LC to the lease */
+	lease_dereference(&(lc->list[n]), MDL);
+
+	/*  memove unless we are removing the last element */
+	if ((lc->nelem-1) > n) {
+		memmove(lc->list + n, lc->list + n + 1,
+			sizeof(struct lease *) * (lc->nelem-1-n));
+	}
+	lc->nelem--;
+}
+
+/*!
+ *
+ * \brief Remove a lease from a specific position. This will first unlink
+ * the lease from the lease chain and then update the linked list.
+ *
+ * \param lc The lease chain to update
+ * \param pos the entry to remove from the lease chain
+ */
+void
+lc_unlink_lease_pos(struct leasechain *lc, size_t pos)
+{
+#if defined (DEBUG_BINARY_LEASES)
+	INSIST(lc != NULL);
+#endif
+
+	struct lease *lp = NULL;
+	lease_reference(&lp, lc->list[pos], MDL);
+
+	/* unlink from lease chain list */
+	lc_unlink_lcp(lc, pos);
+
+	/* unlink from the linked list */
+	if (lp->next) {
+		lease_dereference(&lp->next->prev, MDL);
+		if (lp->prev)
+			lease_reference(&lp->next->prev, lp->prev, MDL);
+	}
+	if (lp->prev) {
+		lease_dereference(&lp->prev->next, MDL);
+		if (lp->next)
+			lease_reference(&lp->prev->next, lp->next, MDL);
+		lease_dereference(&lp->prev, MDL);
+	}
+	if (lp->next) {
+		lease_dereference(&lp->next, MDL);
+	}
+	lease_dereference(&lp, MDL);
+}
+
+/*!
+ *
+ * \brief Find a lease in the lease chain and then remove it
+ * If we can't find the lease on the given lease chain it's a fatal error.
+ *
+ * \param lc The lease chain to update
+ * \param lp The lease to remove
+ */
+void
+lc_unlink_lease(struct leasechain *lc, struct lease *lp) {
+#if defined (DEBUG_BINARY_LEASES)
+	log_debug("LC unlink lease %s:%d", MDL);
+
+	INSIST(lc != NULL);
+	INSIST(lc->list != NULL);
+	INSIST(lp != NULL );
+	INSIST(lp->lc != NULL );
+	INSIST(lp->lc == lc );
+#endif
+
+	size_t pos = lc_binary_search_lease(lc, lp, 0, lc->nelem-1);
+	if (pos == SIZE_MAX) {
+		/* fatal, lease not found in leasechain */
+		log_fatal("Lease with binding state %s not on its queue.",
+			  (lp->binding_state < 1 ||
+			   lp->binding_state > FTS_LAST)
+			  ? "unknown"
+			  : binding_state_names[lp->binding_state - 1]);
+	}
+
+	lc_unlink_lease_pos(lc, pos);
+}
+
+#if defined (DEBUG_MEMORY_LEAKAGE) || \
+		defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
+/*!
+ *
+ * \brief Unlink all the leases in the lease chain and free the
+ * lease chain structure.  The leases will be freed if and when
+ * any other references to them are cleared.
+ *
+ * \param lc the lease chain to clear
+ */
+void
+lc_delete_all(struct leasechain *lc) {
+	size_t i;
+
+	if (lc->nelem > 0) {
+		/* better to delete from the last one, to avoid the memmove */
+		for (i = lc->nelem - 1; ; i--) {
+			lc_unlink_lease_pos(lc, i);
+			if (i == 0) {
+				break;
+			}
+		}
+	}
+
+	/* and then get rid of the list itself */
+	dfree(lc->list, MDL);
+	lc->list = NULL;
+	lc->total = 0;
+	lc->nelem = 0;
+}
+#endif
+
+/*!
+ *
+ * \brief Set the growth value.  This is the number of elements to
+ * add to the array whenever it needs to grow.
+ *
+ * \param lc the lease chain to set up
+ * \param growth the growth value to use
+ */
+void
+lc_init_growth(struct leasechain *lc, size_t growth) {
+	lc->growth = growth;
+}
+
+#endif /* #if defined (BINARY_LEASES) */