[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.

12 files changed, 1568 insertions, 172 deletions

diff --git a/server/Makefile.am b/server/Makefile.am
index 8e8ce889..614b4082 100644
--- a/server/Makefile.am
+++ b/server/Makefile.am
@@ -10,7 +10,7 @@ dist_sysconf_DATA = dhcpd.conf.example
 sbin_PROGRAMS = dhcpd
 dhcpd_SOURCES = dhcpd.c dhcp.c bootp.c confpars.c db.c class.c failover.c \
 		omapi.c mdb.c stables.c salloc.c ddns.c dhcpleasequery.c \
-		dhcpv6.c mdb6.c ldap.c ldap_casa.c
+		dhcpv6.c mdb6.c ldap.c ldap_casa.c leasechain.c
 
 dhcpd_CFLAGS = $(LDAP_CFLAGS)
 dhcpd_LDADD = ../common/libdhcp.a ../omapip/libomapi.a \
diff --git a/server/Makefile.in b/server/Makefile.in
index 939e47ee..ae1bee87 100644
--- a/server/Makefile.in
+++ b/server/Makefile.in
@@ -102,7 +102,7 @@ am_dhcpd_OBJECTS = dhcpd-dhcpd.$(OBJEXT) dhcpd-dhcp.$(OBJEXT) \
 	dhcpd-salloc.$(OBJEXT) dhcpd-ddns.$(OBJEXT) \
 	dhcpd-dhcpleasequery.$(OBJEXT) dhcpd-dhcpv6.$(OBJEXT) \
 	dhcpd-mdb6.$(OBJEXT) dhcpd-ldap.$(OBJEXT) \
-	dhcpd-ldap_casa.$(OBJEXT)
+	dhcpd-ldap_casa.$(OBJEXT) dhcpd-leasechain.$(OBJEXT)
 dhcpd_OBJECTS = $(am_dhcpd_OBJECTS)
 dhcpd_DEPENDENCIES = ../common/libdhcp.a ../omapip/libomapi.a \
 	../dhcpctl/libdhcpctl.a ../bind/lib/libirs.a \
@@ -357,7 +357,7 @@ AM_CPPFLAGS = -I.. -DLOCALSTATEDIR='"@localstatedir@"'
 dist_sysconf_DATA = dhcpd.conf.example
 dhcpd_SOURCES = dhcpd.c dhcp.c bootp.c confpars.c db.c class.c failover.c \
 		omapi.c mdb.c stables.c salloc.c ddns.c dhcpleasequery.c \
-		dhcpv6.c mdb6.c ldap.c ldap_casa.c
+		dhcpv6.c mdb6.c ldap.c ldap_casa.c leasechain.c
 
 dhcpd_CFLAGS = $(LDAP_CFLAGS)
 dhcpd_LDADD = ../common/libdhcp.a ../omapip/libomapi.a \
@@ -465,6 +465,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-failover.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-ldap.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-ldap_casa.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-leasechain.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-mdb.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-mdb6.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dhcpd-omapi.Po@am__quote@
@@ -722,6 +723,20 @@ dhcpd-ldap_casa.obj: ldap_casa.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='ldap_casa.c' object='dhcpd-ldap_casa.obj' libtool=no @AMDEPBACKSLASH@
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(dhcpd_CFLAGS) $(CFLAGS) -c -o dhcpd-ldap_casa.obj `if test -f 'ldap_casa.c'; then $(CYGPATH_W) 'ldap_casa.c'; else $(CYGPATH_W) '$(srcdir)/ldap_casa.c'; fi`
+
+dhcpd-leasechain.o: leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(dhcpd_CFLAGS) $(CFLAGS) -MT dhcpd-leasechain.o -MD -MP -MF $(DEPDIR)/dhcpd-leasechain.Tpo -c -o dhcpd-leasechain.o `test -f 'leasechain.c' || echo '$(srcdir)/'`leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/dhcpd-leasechain.Tpo $(DEPDIR)/dhcpd-leasechain.Po
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='leasechain.c' object='dhcpd-leasechain.o' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(dhcpd_CFLAGS) $(CFLAGS) -c -o dhcpd-leasechain.o `test -f 'leasechain.c' || echo '$(srcdir)/'`leasechain.c
+
+dhcpd-leasechain.obj: leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(dhcpd_CFLAGS) $(CFLAGS) -MT dhcpd-leasechain.obj -MD -MP -MF $(DEPDIR)/dhcpd-leasechain.Tpo -c -o dhcpd-leasechain.obj `if test -f 'leasechain.c'; then $(CYGPATH_W) 'leasechain.c'; else $(CYGPATH_W) '$(srcdir)/leasechain.c'; fi`
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/dhcpd-leasechain.Tpo $(DEPDIR)/dhcpd-leasechain.Po
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='leasechain.c' object='dhcpd-leasechain.obj' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(dhcpd_CFLAGS) $(CFLAGS) -c -o dhcpd-leasechain.obj `if test -f 'leasechain.c'; then $(CYGPATH_W) 'leasechain.c'; else $(CYGPATH_W) '$(srcdir)/leasechain.c'; fi`
 install-man5: $(man_MANS)
 	@$(NORMAL_INSTALL)
 	@list1=''; \
diff --git a/server/confpars.c b/server/confpars.c
index c9c149f5..3240e5cc 100644
--- a/server/confpars.c
+++ b/server/confpars.c
@@ -1759,6 +1759,14 @@ void parse_pool_statement (cfile, group, type)
 			pool_dereference(&lp->pool, MDL);
 			pool_reference(&lp->pool, pp, MDL);
 		}
+
+#if defined (BINARY_LEASES)
+		/* If we are doing binary leases we also need to add the
+		 * addresses in for leasechain allocation.
+		 */
+		pp->lease_count += pool->lease_count;
+#endif
+
 		break;
 	}
 
diff --git a/server/dhcp.c b/server/dhcp.c
index 41f4c61c..e71720f6 100644
--- a/server/dhcp.c
+++ b/server/dhcp.c
@@ -4548,8 +4548,9 @@ int mockup_lease (struct lease **lp, struct packet *packet,
 int allocate_lease (struct lease **lp, struct packet *packet,
 		    struct pool *pool, int *peer_has_leases)
 {
-	struct lease *lease = (struct lease *)0;
-	struct lease *candl = (struct lease *)0;
+	struct lease *lease = NULL;
+	struct lease *candl = NULL;
+	struct lease *peerl = NULL;
 
 	for (; pool ; pool = pool -> next) {
 		if ((pool -> prohibit_list &&
@@ -4575,7 +4576,7 @@ int allocate_lease (struct lease **lp, struct packet *packet,
 		 * owned by a failover peer. */
 		if (pool->failover_peer != NULL) {
 			if (pool->failover_peer->i_am == primary) {
-				candl = pool->free;
+				candl = LEASE_GET_FIRST(pool->free);
 
 				/*
 				 * In normal operation, we never want to touch
@@ -4583,27 +4584,25 @@ int allocate_lease (struct lease **lp, struct packet *packet,
 				 * operation, we need to be able to pick up
 				 * the peer's leases after STOS+MCLT.
 				 */
-				if (pool->backup != NULL) {
+				peerl = LEASE_GET_FIRST(pool->backup);
+				if (peerl != NULL) {
 					if (((candl == NULL) ||
-					     (candl->ends >
-					      pool->backup->ends)) &&
-					    lease_mine_to_reallocate(
-							    pool->backup)) {
-						candl = pool->backup;
+					     (candl->ends > peerl->ends)) &&
+					    lease_mine_to_reallocate(peerl)) {
+						candl = peerl;
 					} else {
 						*peer_has_leases = 1;
 					}
 				}
 			} else {
-				candl = pool->backup;
+				candl = LEASE_GET_FIRST(pool->backup);
 
-				if (pool->free != NULL) {
+				peerl = LEASE_GET_FIRST(pool->free);
+				if (peerl != NULL) {
 					if (((candl == NULL) ||
-					     (candl->ends >
-					      pool->free->ends)) &&
-					    lease_mine_to_reallocate(
-							    pool->free)) {
-						candl = pool->free;
+					     (candl->ends > peerl->ends)) &&
+					    lease_mine_to_reallocate(peerl)) {
+						candl = peerl;
 					} else {
 						*peer_has_leases = 1;
 					}
@@ -4611,17 +4610,17 @@ int allocate_lease (struct lease **lp, struct packet *packet,
 			}
 
 			/* Try abandoned leases as a last resort. */
-			if ((candl == NULL) &&
-			    (pool->abandoned != NULL) &&
-			    lease_mine_to_reallocate(pool->abandoned))
-				candl = pool->abandoned;
+			peerl = LEASE_GET_FIRST(pool->abandoned);
+			if ((candl == NULL) && (peerl != NULL) &&
+			    lease_mine_to_reallocate(peerl))
+				candl = peerl;
 		} else
 #endif
 		{
-			if (pool -> free)
-				candl = pool -> free;
+			if (LEASE_NOT_EMPTY(pool->free))
+				candl = LEASE_GET_FIRST(pool->free);
 			else
-				candl = pool -> abandoned;
+				candl = LEASE_GET_FIRST(pool->abandoned);
 		}
 
 		/*
diff --git a/server/dhcpd.c b/server/dhcpd.c
index 3d2aa09a..cb4f0112 100644
--- a/server/dhcpd.c
+++ b/server/dhcpd.c
@@ -1117,6 +1117,12 @@ void postconf_initialization (int quiet)
 		data_string_forget(&db, MDL);
 	}
 
+#if defined (BINARY_LEASES)
+	if (local_family == AF_INET) {
+		log_info("Source compiled to use binary-leases");
+	}
+#endif
+
 	/* Don't need the options anymore. */
 	option_state_dereference(&options, MDL);
 }
diff --git a/server/failover.c b/server/failover.c
index 2486a735..a3a0383c 100644
--- a/server/failover.c
+++ b/server/failover.c
@@ -3,7 +3,7 @@
    Failover protocol support code... */
 
 /*
- * Copyright (c) 2004-2014 by Internet Systems Consortium, Inc. ("ISC")
+ * Copyright (c) 2004-2015 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
@@ -1939,18 +1939,33 @@ isc_result_t dhcp_failover_set_state (dhcp_failover_state_t *state,
 
 	  case partner_down:
 	    /* For every expired lease, set a timeout for it to become free. */
-	    for (s = shared_networks; s; s = s -> next) {
-		for (p = s -> pools; p; p = p -> next) {
-		    if (p -> failover_peer == state) {
-			for (l = p->expired ; l ; l = l->next) {
+	    for (s = shared_networks; s; s = s->next) {
+		for (p = s->pools; p; p = p->next) {
+#if defined (BINARY_LEASES)
+		    long int tiebreaker = 0;
+#endif
+		    if (p->failover_peer == state) {
+			for (l = LEASE_GET_FIRST(p->expired);
+			     l != NULL;
+			     l = LEASE_GET_NEXT(p->expired, l)) {
 			    l->tsfp = state->me.stos + state->mclt;
 			    l->sort_time = (l->tsfp > l->ends) ?
 					   l->tsfp : l->ends;
+#if defined (BINARY_LEASES)
+			    /* If necessary fix up the tiebreaker so the leases
+			     * maintain proper sort order.
+			     */
+			    l->sort_tiebreaker = tiebreaker;
+			    if (tiebreaker != LONG_MAX)
+			        tiebreaker++;
+#endif
+
 			}
-			if (p->expired &&
-			    (p->expired->sort_time < p->next_event_time)) {
 
-			    p->next_event_time = p->expired->sort_time;
+			l = LEASE_GET_FIRST(p->expired);
+			if (l && (l->sort_time < p->next_event_time)) {
+
+			    p->next_event_time = l->sort_time;
 #if defined (DEBUG_FAILOVER_TIMING)
 			    log_info ("add_timeout +%d %s",
 				      (int)(cur_time - p->next_event_time),
@@ -1967,7 +1982,6 @@ isc_result_t dhcp_failover_set_state (dhcp_failover_state_t *state,
 	    }
 	    break;
 
-
 	  default:
 	    break;
     }
@@ -2470,14 +2484,15 @@ dhcp_failover_pool_dobalance(dhcp_failover_state_t *state,
 {
 	int lts, total, thresh, hold, panic, pass;
 	int leases_queued = 0;
-	struct lease *lp = (struct lease *)0;
-	struct lease *next = (struct lease *)0;
+	struct lease *lp = NULL;
+	struct lease *next = NULL;
+	struct lease *ltemp = NULL;
 	struct shared_network *s;
 	struct pool *p;
 	binding_state_t peer_lease_state;
 	/* binding_state_t my_lease_state; */
         /* XXX Why is this my_lease_state never used? */
-	struct lease **lq;
+	LEASE_STRUCT_PTR lq;
 	int (*log_func)(const char *, ...);
 	const char *result, *reqlog;
 
@@ -2559,13 +2574,14 @@ dhcp_failover_pool_dobalance(dhcp_failover_state_t *state,
 		 * worth it.
 		 */
 		pass = 0;
-		lease_reference(&lp, *lq, MDL);
+		lease_reference(&lp, LEASE_GET_FIRSTP(lq), MDL);
 
 		while (lp) {
 			if (next)
 			    lease_dereference(&next, MDL);
-			if (lp->next)
-			    lease_reference(&next, lp->next, MDL);
+			ltemp = LEASE_GET_NEXTP(lq, lp);
+			if (ltemp != NULL)
+			    lease_reference(&next, ltemp, MDL);
 
 			/*
 			 * Stop if the pool is 'balanced enough.'
@@ -2613,7 +2629,7 @@ dhcp_failover_pool_dobalance(dhcp_failover_state_t *state,
 				lease_reference(&lp, next, MDL);
 			else if (!pass) {
 				pass = 1;
-				lease_reference(&lp, *lq, MDL);
+				lease_reference(&lp, LEASE_GET_FIRSTP(lq), MDL);
 			}
 		}
 
@@ -2657,6 +2673,7 @@ dhcp_failover_pool_check(struct pool *pool)
 	dhcp_failover_state_t *peer;
 	TIME est1, est2;
 	struct timeval tv;
+	struct lease *ltemp;
 
 	peer = pool->failover_peer;
 
@@ -2673,13 +2690,15 @@ dhcp_failover_pool_check(struct pool *pool)
 	 * lease is a virgin (ends = 0), we wind up sending this against
 	 * the max_balance bounds check.
 	 */
-	if(pool->free && pool->free->ends < cur_time)
-		est1 = cur_time - pool->free->ends;
+	ltemp = LEASE_GET_FIRST(pool->free);
+	if(ltemp && ltemp->ends < cur_time)
+		est1 = cur_time - ltemp->ends;
 	else
 		est1 = 0;
 
-	if(pool->backup && pool->backup->ends < cur_time)
-		est2 = cur_time - pool->backup->ends;
+	ltemp = LEASE_GET_FIRST(pool->backup);
+	if(ltemp && ltemp->ends < cur_time)
+		est2 = cur_time - ltemp->ends;
 	else
 		est2 = 0;
 
@@ -5651,7 +5670,7 @@ isc_result_t dhcp_failover_generate_update_queue (dhcp_failover_state_t *state,
 #define ABANDONED_LEASES 3
 #define BACKUP_LEASES 4
 #define RESERVED_LEASES 5
-	struct lease **lptr[RESERVED_LEASES+1];
+	LEASE_STRUCT_PTR lptr[RESERVED_LEASES+1];
 
 	/* Loop through each pool in each shared network and call the
 	   expiry routine on the pool. */
@@ -5668,7 +5687,9 @@ isc_result_t dhcp_failover_generate_update_queue (dhcp_failover_state_t *state,
 		lptr[RESERVED_LEASES] = &p->reserved;
 
 		for (i = FREE_LEASES; i <= RESERVED_LEASES; i++) {
-		    for (l = *(lptr [i]); l; l = l -> next) {
+		    for (l = LEASE_GET_FIRSTP(lptr[i]);
+			 l != NULL;
+			 l = LEASE_GET_NEXTP(lptr[i], l)) {
 			if ((l->flags & ON_QUEUE) == 0 &&
 			    (everythingp ||
 			     (l->tstp > l->atsfp) ||
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) */
diff --git a/server/mdb.c b/server/mdb.c
index ef54bedd..6a637b5e 100644
--- a/server/mdb.c
+++ b/server/mdb.c
@@ -761,9 +761,9 @@ void new_address_range (cfile, low, high, subnet, pool, lpchain)
 {
 #if defined(COMPACT_LEASES)
 	struct lease *address_range;
-	unsigned n, s;
+	unsigned s;
 #endif
-	unsigned min, max, i;
+	unsigned min, max, i, num_addrs;
 	char lowbuf [16], highbuf [16], netbuf [16];
 	struct shared_network *share = subnet -> shared_network;
 	struct lease *lt = (struct lease *)0;
@@ -819,22 +819,30 @@ void new_address_range (cfile, low, high, subnet, pool, lpchain)
 		min = host_addr (high, subnet -> netmask);
 	}
 
+	/* get the number of addresses we want, and add it to the pool info
+	 * this value is only for use when setting up lease chains and will
+	 * be overwritten when expire_all_pools is run
+	 */
+	num_addrs = max - min + 1;
+#if defined (BINARY_LEASES)
+	pool->lease_count += num_addrs;
+#endif
+
 	/* Get a lease structure for each address in the range. */
 #if defined (COMPACT_LEASES)
-	n = max - min + 1;
-	s = (n + 1) * sizeof (struct lease);
+	s = (num_addrs + 1) * sizeof (struct lease);
 	/* Check unsigned overflow in new_leases().
 	   With 304 byte lease structure (x64_86), this happens at
 	   range 10.0.0.0 10.215.148.52; */
 	if (((s % sizeof (struct lease)) != 0) ||
-	    ((s / sizeof (struct lease)) != (n + 1))) {
+	    ((s / sizeof (struct lease)) != (num_addrs + 1))) {
 		strcpy (lowbuf, piaddr (low));
 		strcpy (highbuf, piaddr (high));
-		parse_warn (cfile, "%s-%s is a far too large address range.",
+		parse_warn (cfile, "%s-%s is an overly large address range.",
 			   lowbuf, highbuf);
 		log_fatal ("Memory overflow.");
 	}
-	address_range = new_leases (n, MDL);
+	address_range = new_leases (num_addrs, MDL);
 	if (!address_range) {
 		strcpy (lowbuf, piaddr (low));
 		strcpy (highbuf, piaddr (high));
@@ -844,7 +852,7 @@ void new_address_range (cfile, low, high, subnet, pool, lpchain)
 #endif
 
 	/* Fill out the lease structures with some minimal information. */
-	for (i = 0; i < max - min + 1; i++) {
+	for (i = 0; i < num_addrs; i++) {
 		struct lease *lp = (struct lease *)0;
 #if defined (COMPACT_LEASES)
 		omapi_object_initialize ((omapi_object_t *)&address_range [i],
@@ -1112,7 +1120,7 @@ int supersede_lease (comp, lease, commit, propogate, pimmediate, from_pool)
 	int pimmediate;
 	int from_pool;
 {
-	struct lease *lp, **lq, *prev;
+	LEASE_STRUCT_PTR lq;
 	struct timeval tv;
 #if defined (FAILOVER_PROTOCOL)
 	int do_pool_check = 0;
@@ -1360,35 +1368,7 @@ int supersede_lease (comp, lease, commit, propogate, pimmediate, from_pool)
 
 	/* Remove the lease from its current place in its current
 	   timer sequence. */
-	/* XXX this is horrid. */
-	prev = (struct lease *)0;
-	for (lp = *lq; lp; lp = lp -> next) {
-		if (lp == comp)
-			break;
-		prev = lp;
-	}
-
-	if (!lp) {
-		log_fatal("Lease with binding state %s not on its queue.",
-			  (comp->binding_state < 1 ||
-			   comp->binding_state > FTS_LAST)
-			  ? "unknown"
-			  : binding_state_names[comp->binding_state - 1]);
-	}
-
-	if (prev) {
-		lease_dereference (&prev -> next, MDL);
-		if (comp -> next) {
-			lease_reference (&prev -> next, comp -> next, MDL);
-			lease_dereference (&comp -> next, MDL);
-		}
-	} else {
-		lease_dereference (lq, MDL);
-		if (comp -> next) {
-			lease_reference (lq, comp -> next, MDL);
-			lease_dereference (&comp -> next, MDL);
-		}
-	}
+	LEASE_REMOVEP(lq, comp);
 
 	/* Make the state transition. */
 	if (commit || !pimmediate)
@@ -1883,13 +1863,14 @@ void pool_timer (vpool)
 	struct pool *pool;
 	struct lease *next = NULL;
 	struct lease *lease = NULL;
+	struct lease *ltemp = NULL;
 #define FREE_LEASES 0
 #define ACTIVE_LEASES 1
 #define EXPIRED_LEASES 2
 #define ABANDONED_LEASES 3
 #define BACKUP_LEASES 4
 #define RESERVED_LEASES 5
-	struct lease **lptr[RESERVED_LEASES+1];
+	LEASE_STRUCT_PTR lptr[RESERVED_LEASES+1];
 	TIME next_expiry = MAX_TIME;
 	int i;
 	struct timeval tv;
@@ -1905,7 +1886,7 @@ void pool_timer (vpool)
 
 	for (i = FREE_LEASES; i <= RESERVED_LEASES; i++) {
 		/* If there's nothing on the queue, skip it. */
-		if (!*(lptr [i]))
+		if (!(LEASE_NOT_EMPTYP(lptr[i])))
 			continue;
 
 #if defined (FAILOVER_PROTOCOL)
@@ -1936,14 +1917,15 @@ void pool_timer (vpool)
 				continue;
 		}
 #endif		
-		lease_reference(&lease, *(lptr [i]), MDL);
+		lease_reference(&lease, LEASE_GET_FIRSTP(lptr[i]), MDL);
 
 		while (lease) {
 			/* Remember the next lease in the list. */
 			if (next)
 				lease_dereference(&next, MDL);
-			if (lease -> next)
-				lease_reference(&next, lease->next, MDL);
+			ltemp = LEASE_GET_NEXTP(lptr[i], lease);
+			if (ltemp)
+				lease_reference(&next, ltemp, MDL);
 
 			/* If we've run out of things to expire on this list,
 			   stop. */
@@ -2358,7 +2340,7 @@ int write_leases4(void) {
 	struct lease *l;
 	struct shared_network *s;
 	struct pool *p;
-	struct lease **lptr[RESERVED_LEASES+1];
+	LEASE_STRUCT_PTR lptr[RESERVED_LEASES+1];
 	int num_written = 0, i;
 
 	/* Write all the leases. */
@@ -2372,7 +2354,9 @@ int write_leases4(void) {
 		lptr[RESERVED_LEASES] = &p->reserved;
 
 		for (i = FREE_LEASES; i <= RESERVED_LEASES; i++) {
-		    for (l = *(lptr[i]); l; l = l->next) {
+		    for (l = LEASE_GET_FIRSTP(lptr[i]);
+			 l != NULL;
+			 l = LEASE_GET_NEXTP(lptr[i], l)) {
 #if !defined (DEBUG_DUMP_ALL_LEASES)
 			if (l->hardware_addr.hlen != 0 || l->uid_len != 0 ||
 			    l->tsfp != 0 || l->binding_state != FTS_FREE)
@@ -2499,6 +2483,137 @@ int write_leases ()
 	return (1);
 }
 
+#if !defined (BINARY_LEASES)
+#if defined (DEBUG_MEMORY_LEAKAGE) || \
+		defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
+/* Unlink all the leases in the queue.  This is only used for debugging
+ */
+void lease_remove_all(struct lease **lq) {
+	struct lease *lp, *ln = NULL;
+
+	/* nothing to do */
+	if (*lq == NULL)
+		return;
+
+	/* We simply derefernce the first item in the list.  When
+	 * it's reference counter goes to zero it will be cleaned
+	 * and the reference counter
+	 *
+	 * Get a pointer to the first item in the list and then
+	 * drop the reference from the queue pointer
+	 */
+	lease_reference(&lp, *lq, MDL);
+	lease_dereference(lq, MDL);
+
+	do {
+		/* if we have a next save a pointer to it and unlink it */
+		if (lp->next) {
+			lease_reference(&ln, lp->next, MDL);
+			lease_dereference(&lp->next, MDL);
+		}
+
+		/* get rid of what we currently have */
+		lease_dereference(&lp, MDL);
+
+		/* move the next to the current and loop */
+		lp = ln;
+		ln = NULL;
+	} while (lp != NULL);
+}
+#endif /* DEBUG_MEMORY_LEAKAGE... */
+
+/*
+ * This routine walks through a given lease queue (lq) looking
+ * for comp.  If it doesn't find the lease it is a fatal error
+ * as it should be on the given queue.  Once we find the lease
+ * we can remove it from this list.
+ */
+void lease_remove(struct lease **lq, struct lease *comp)
+{
+	struct lease *prev, *lp;
+
+	prev = NULL;
+	for (lp = *lq; lp != NULL; lp = lp->next) {
+		if (lp == comp)
+			break;
+		prev = lp;
+	}
+
+	if (!lp) {
+		log_fatal("Lease with binding state %s not on its queue.",
+			  (comp->binding_state < 1 ||
+			   comp->binding_state > FTS_LAST)
+			  ? "unknown"
+			  : binding_state_names[comp->binding_state - 1]);
+	}
+
+	if (prev) {
+		lease_dereference(&prev->next, MDL);
+		if (comp->next) {
+			lease_reference(&prev->next, comp->next, MDL);
+			lease_dereference (&comp->next, MDL);
+		}
+	} else {
+		lease_dereference(lq, MDL);
+		if (comp->next) {
+			lease_reference(lq, comp->next, MDL);
+			lease_dereference(&comp->next, MDL);
+		}
+	}
+}
+
+/* This routine inserts comp into lq in a sorted fashion.
+ * The sort key is comp->sort_time, smaller values are
+ * placed earlier in the list.
+ */
+void lease_insert(struct lease **lq, struct lease *comp)
+{
+	struct lease *prev, *lp;
+	static struct lease **last_lq = NULL;
+	static struct lease *last_insert_point = NULL;
+
+	/* This only works during server startup: during runtime, the last
+	 * lease may be dequeued in between calls.  If the queue is the same
+	 * as was used previously, and the lease structure isn't (this is not
+	 * a re-queue), use that as a starting point for the insertion-sort.
+	 */
+	if ((server_starting & SS_QFOLLOW) && (lq == last_lq) &&
+	    (comp != last_insert_point) && 
+	    (last_insert_point->sort_time <= comp->sort_time)) {
+		prev = last_insert_point;
+		lp = prev->next;
+	} else {
+		prev = NULL;
+		lp = *lq;
+	}
+
+	/* Insertion sort the lease onto the appropriate queue. */
+	for (; lp != NULL ; lp = lp->next) {
+		if (lp->sort_time >= comp->sort_time)
+			break;
+		prev = lp;
+	}
+
+	if (prev) {
+		if (prev->next) {
+			lease_reference(&comp->next, prev->next, MDL);
+			lease_dereference(&prev->next, MDL);
+		}
+		lease_reference(&prev->next, comp, MDL);
+	} else {
+		if (*lq) {
+			lease_reference (&comp->next, *lq, MDL);
+			lease_dereference(lq, MDL);
+		}
+		lease_reference(lq, comp, MDL);
+	}
+	last_insert_point = comp;
+	last_lq = lq;
+
+	return;
+}
+#endif
+
 /* In addition to placing this lease upon a lease queue depending on its
  * state, it also keeps track of the number of FREE and BACKUP leases in
  * existence, and sets the sort_time on the lease.
@@ -2513,9 +2628,7 @@ int write_leases ()
  */
 int lease_enqueue (struct lease *comp)
 {
-	struct lease **lq, *prev, *lp;
-	static struct lease **last_lq = NULL;
-	static struct lease *last_insert_point = NULL;
+	LEASE_STRUCT_PTR lq;  
 
 	/* No queue to put it on? */
 	if (!comp -> pool)
@@ -2589,43 +2702,8 @@ int lease_enqueue (struct lease *comp)
 		return 0;
 	}
 
-	/* This only works during server startup: during runtime, the last
-	 * lease may be dequeued in between calls.  If the queue is the same
-	 * as was used previously, and the lease structure isn't (this is not
-	 * a re-queue), use that as a starting point for the insertion-sort.
-	 */
-	if ((server_starting & SS_QFOLLOW) && (lq == last_lq) &&
-	    (comp != last_insert_point) && 
-	    (last_insert_point->sort_time <= comp->sort_time)) {
-		prev = last_insert_point;
-		lp = prev->next;
-	} else {
-		prev = NULL;
-		lp = *lq;
-	}
-
-	/* Insertion sort the lease onto the appropriate queue. */
-	for (; lp ; lp = lp->next) {
-		if (lp -> sort_time >= comp -> sort_time)
-			break;
-		prev = lp;
-	}
+	LEASE_INSERTP(lq, comp);
 
-	if (prev) {
-		if (prev -> next) {
-			lease_reference (&comp -> next, prev -> next, MDL);
-			lease_dereference (&prev -> next, MDL);
-		}
-		lease_reference (&prev -> next, comp, MDL);
-	} else {
-		if (*lq) {
-			lease_reference (&comp -> next, *lq, MDL);
-			lease_dereference (lq, MDL);
-		}
-		lease_reference (lq, comp, MDL);
-	}
-	last_insert_point = comp;
-	last_lq = lq;
 	return 1;
 }
 
@@ -2710,11 +2788,35 @@ void expire_all_pools ()
 	struct pool *p;
 	int i;
 	struct lease *l;
-	struct lease **lptr[RESERVED_LEASES+1];
+	LEASE_STRUCT_PTR lptr[RESERVED_LEASES+1];
 
 	/* Indicate that we are in the startup phase */
 	server_starting = SS_NOSYNC | SS_QFOLLOW;
 
+#if defined (BINARY_LEASES)
+	/* set up the growth factors for the binary leases.
+	 * We use 100% for free, 50% for active and backup
+	 * 20% for expired, abandoned and reserved
+	 * but no less than 100, 50, and 20.
+	 */
+	for (s = shared_networks; s; s = s -> next) {
+	    for (p = s -> pools; p != NULL; p = p -> next) {
+		size_t num_f = 100, num_a = 50, num_e = 20;
+		if (p->lease_count > 100) {
+		    num_f = p->lease_count;
+		    num_a = num_f / 2;
+		    num_e = num_f / 5;
+		}
+		lc_init_growth(&p->free, num_f);
+		lc_init_growth(&p->active, num_a);
+		lc_init_growth(&p->expired, num_a);
+		lc_init_growth(&p->abandoned, num_e);
+		lc_init_growth(&p->backup, num_e);
+		lc_init_growth(&p->reserved, num_e);
+	    }
+	}
+#endif
+
 	/* First, go over the hash list and actually put all the leases
 	   on the appropriate lists. */
 	lease_ip_hash_foreach(lease_ip_addr_hash, lease_instantiate);
@@ -2742,7 +2844,9 @@ void expire_all_pools ()
 		lptr [RESERVED_LEASES] = &p->reserved;
 
 		for (i = FREE_LEASES; i <= RESERVED_LEASES; i++) {
-		    for (l = *(lptr [i]); l; l = l -> next) {
+		    for (l = LEASE_GET_FIRSTP(lptr[i]);
+			 l != NULL;
+			 l = LEASE_GET_NEXTP(lptr[i], l)) {
 			p -> lease_count++;
 			if (l -> ends <= cur_time) {
 				if (l->binding_state == FTS_FREE) {
@@ -2782,7 +2886,7 @@ void dump_subnets ()
 	struct shared_network *s;
 	struct subnet *n;
 	struct pool *p;
-	struct lease **lptr[RESERVED_LEASES+1];
+	LEASE_STRUCT_PTR lptr[RESERVED_LEASES+1];
 	int i;
 
 	log_info ("Subnets:");
@@ -2803,7 +2907,9 @@ void dump_subnets ()
 		lptr [RESERVED_LEASES] = &p->reserved;
 
 		for (i = FREE_LEASES; i <= RESERVED_LEASES; i++) {
-		    for (l = *(lptr [i]); l; l = l -> next) {
+		    for (l = LEASE_GET_FIRSTP(lptr[i]);
+			 l != NULL;
+			 l = LEASE_GET_NEXTP(lptr[i], l)) {
 			    print_lease (l);
 		    }
 		}
@@ -2844,7 +2950,7 @@ void free_everything(void)
 	struct shared_network *nc = (struct shared_network *)0,
 		*nn = (struct shared_network *)0;
 	struct pool *pc = (struct pool *)0, *pn = (struct pool *)0;
-	struct lease *lc = (struct lease *)0, *ln = (struct lease *)0;
+	struct lease *lc = NULL, *ln = NULL,  *ltemp = NULL;
 	struct interface_info *ic = (struct interface_info *)0,
 		*in = (struct interface_info *)0;
 	struct class *cc = (struct class *)0, *cn = (struct class *)0;
@@ -2995,7 +3101,7 @@ void free_everything(void)
 		if (nc -> pools) {
 		    pool_reference (&pn, nc -> pools, MDL);
 		    do {
-			struct lease **lptr[RESERVED_LEASES+1];
+			LEASE_STRUCT_PTR lptr[RESERVED_LEASES+1];
 
 			if (pn) {
 			    pool_reference (&pc, pn, MDL);
@@ -3015,17 +3121,22 @@ void free_everything(void)
 
 			/* As (sigh) are leases. */
 			for (i = FREE_LEASES ; i <= RESERVED_LEASES ; i++) {
-			    if (*lptr [i]) {
-				lease_reference (&ln, *lptr [i], MDL);
+			    if (LEASE_NOT_EMPTYP(lptr[i])) {
+			        lease_reference(&ln, LEASE_GET_FIRSTP(lptr[i]), MDL);
 				do {
-				    if (ln) {
-					lease_reference (&lc, ln, MDL);
-					lease_dereference (&ln, MDL);
-				    }
-				    if (lc -> next) {
-					lease_reference (&ln, lc -> next, MDL);
-					lease_dereference (&lc -> next, MDL);
+				    /* save a pointer to the current lease */
+				    lease_reference (&lc, ln, MDL);
+				    lease_dereference (&ln, MDL);
+
+				    /* get the next lease if there is one */
+				    ltemp = LEASE_GET_NEXTP(lptr[i], lc);
+				    if (ltemp != NULL) {
+					lease_reference(&ln, ltemp, MDL);
 				    }
+
+				    /* remove the current lease from the queue */
+				    LEASE_REMOVEP(lptr[i], lc);
+
 				    if (lc -> billing_class)
 				       class_dereference (&lc -> billing_class,
 							  MDL);
@@ -3038,7 +3149,6 @@ void free_everything(void)
 					lease_dereference (&lc -> n_uid, MDL);
 				    lease_dereference (&lc, MDL);
 				} while (ln);
-				lease_dereference (lptr [i], MDL);
 			    }
 			}
 			if (pc -> group)
diff --git a/server/omapi.c b/server/omapi.c
index 17292e23..962aef88 100644
--- a/server/omapi.c
+++ b/server/omapi.c
@@ -3,7 +3,7 @@
    OMAPI object interfaces for the DHCP server. */
 
 /*
- * Copyright (c) 2012-2014 by Internet Systems Consortium, Inc. ("ISC")
+ * Copyright (c) 2012-2015 by Internet Systems Consortium, Inc. ("ISC")
  * Copyright (c) 2004-2009 by Internet Systems Consortium, Inc. ("ISC")
  * Copyright (c) 1999-2003 by Internet Software Consortium
  *
@@ -457,10 +457,13 @@ isc_result_t dhcp_lease_destroy (omapi_object_t *h, const char *file, int line)
 
 #if defined (DEBUG_MEMORY_LEAKAGE) || \
 		defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
-	/* XXX we should never be destroying a lease with a next
-	   XXX pointer except on exit... */
+	/* We no longer check for a next pointer as that should
+	 * be cleared when we destroy the pool and as before we
+	 * should only ever be doing that on exit.
 	if (lease->next)
 		lease_dereference (&lease->next, file, line);
+	 */
+
 	if (lease->n_hw)
 		lease_dereference (&lease->n_hw, file, line);
 	if (lease->n_uid)
@@ -1596,16 +1599,14 @@ isc_result_t dhcp_pool_destroy (omapi_object_t *h, const char *file, int line)
 		group_dereference (&pool -> group, file, line);
 	if (pool -> shared_network)
 	    shared_network_dereference (&pool -> shared_network, file, line);
-	if (pool -> active)
-		lease_dereference (&pool -> active, file, line);
-	if (pool -> expired)
-		lease_dereference (&pool -> expired, file, line);
-	if (pool -> free)
-		lease_dereference (&pool -> free, file, line);
-	if (pool -> backup)
-		lease_dereference (&pool -> backup, file, line);
-	if (pool -> abandoned)
-		lease_dereference (&pool -> abandoned, file, line);
+
+	POOL_DESTROYP(&pool->active);
+	POOL_DESTROYP(&pool->expired);
+	POOL_DESTROYP(&pool->free);
+	POOL_DESTROYP(&pool->backup);
+	POOL_DESTROYP(&pool->abandoned);
+	POOL_DESTROYP(&pool->reserved);
+
 #if defined (FAILOVER_PROTOCOL)
 	if (pool -> failover_peer)
 		dhcp_failover_state_dereference (&pool -> failover_peer,
diff --git a/server/tests/Makefile.am b/server/tests/Makefile.am
index fb345c54..84ae202b 100644
--- a/server/tests/Makefile.am
+++ b/server/tests/Makefile.am
@@ -15,7 +15,7 @@ info:
 DHCPSRC = ../dhcp.c ../bootp.c ../confpars.c ../db.c ../class.c      \
           ../failover.c ../omapi.c ../mdb.c ../stables.c ../salloc.c \
           ../ddns.c ../dhcpleasequery.c ../dhcpv6.c ../mdb6.c        \
-          ../ldap.c ../ldap_casa.c ../dhcpd.c
+          ../ldap.c ../ldap_casa.c ../dhcpd.c ../leasechain.c
 
 DHCPLIBS = $(top_builddir)/common/libdhcp.a $(top_builddir)/omapip/libomapi.a    \
           $(top_builddir)/dhcpctl/libdhcpctl.a $(top_builddir)/bind/lib/libirs.a \
@@ -25,7 +25,7 @@ DHCPLIBS = $(top_builddir)/common/libdhcp.a $(top_builddir)/omapip/libomapi.a
 ATF_TESTS =
 if HAVE_ATF
 
-ATF_TESTS += dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests
+ATF_TESTS += dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests leaseq_unittests
 
 dhcpd_unittests_SOURCES = $(DHCPSRC)
 dhcpd_unittests_SOURCES += simple_unittest.c
@@ -45,6 +45,9 @@ legacy_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 load_bal_unittests_SOURCES = $(DHCPSRC) load_bal_unittest.c
 load_bal_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 
+leaseq_unittests_SOURCES = $(DHCPSRC) leaseq_unittest.c
+leaseq_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
+
 check: $(ATF_TESTS)
 	sh ${top_srcdir}/tests/unittest.sh
 
diff --git a/server/tests/Makefile.in b/server/tests/Makefile.in
index a103666e..d0da6aa4 100644
--- a/server/tests/Makefile.in
+++ b/server/tests/Makefile.in
@@ -77,7 +77,7 @@ PRE_UNINSTALL = :
 POST_UNINSTALL = :
 build_triplet = @build@
 host_triplet = @host@
-@HAVE_ATF_TRUE@am__append_1 = dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests
+@HAVE_ATF_TRUE@am__append_1 = dhcpd_unittests legacy_unittests hash_unittests load_bal_unittests leaseq_unittests
 check_PROGRAMS = $(am__EXEEXT_2)
 subdir = server/tests
 DIST_COMMON = $(srcdir)/Makefile.in $(srcdir)/Makefile.am \
@@ -93,19 +93,20 @@ CONFIG_CLEAN_VPATH_FILES =
 @HAVE_ATF_TRUE@am__EXEEXT_1 = dhcpd_unittests$(EXEEXT) \
 @HAVE_ATF_TRUE@	legacy_unittests$(EXEEXT) \
 @HAVE_ATF_TRUE@	hash_unittests$(EXEEXT) \
-@HAVE_ATF_TRUE@	load_bal_unittests$(EXEEXT)
+@HAVE_ATF_TRUE@	load_bal_unittests$(EXEEXT) \
+@HAVE_ATF_TRUE@	leaseq_unittests$(EXEEXT)
 am__EXEEXT_2 = $(am__EXEEXT_1)
 am__dhcpd_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
 	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
 	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
 	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
-	simple_unittest.c
+	../leasechain.c simple_unittest.c
 am__objects_1 = dhcp.$(OBJEXT) bootp.$(OBJEXT) confpars.$(OBJEXT) \
 	db.$(OBJEXT) class.$(OBJEXT) failover.$(OBJEXT) \
 	omapi.$(OBJEXT) mdb.$(OBJEXT) stables.$(OBJEXT) \
 	salloc.$(OBJEXT) ddns.$(OBJEXT) dhcpleasequery.$(OBJEXT) \
 	dhcpv6.$(OBJEXT) mdb6.$(OBJEXT) ldap.$(OBJEXT) \
-	ldap_casa.$(OBJEXT) dhcpd.$(OBJEXT)
+	ldap_casa.$(OBJEXT) dhcpd.$(OBJEXT) leasechain.$(OBJEXT)
 @HAVE_ATF_TRUE@am_dhcpd_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	simple_unittest.$(OBJEXT)
 dhcpd_unittests_OBJECTS = $(am_dhcpd_unittests_OBJECTS)
@@ -118,17 +119,27 @@ am__hash_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
 	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
 	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
 	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
-	hash_unittest.c
+	../leasechain.c hash_unittest.c
 @HAVE_ATF_TRUE@am_hash_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	hash_unittest.$(OBJEXT)
 hash_unittests_OBJECTS = $(am_hash_unittests_OBJECTS)
 @HAVE_ATF_TRUE@hash_unittests_DEPENDENCIES = $(DHCPLIBS) \
 @HAVE_ATF_TRUE@	$(am__DEPENDENCIES_1)
+am__leaseq_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
+	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
+	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
+	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
+	../leasechain.c leaseq_unittest.c
+@HAVE_ATF_TRUE@am_leaseq_unittests_OBJECTS = $(am__objects_1) \
+@HAVE_ATF_TRUE@	leaseq_unittest.$(OBJEXT)
+leaseq_unittests_OBJECTS = $(am_leaseq_unittests_OBJECTS)
+@HAVE_ATF_TRUE@leaseq_unittests_DEPENDENCIES = $(DHCPLIBS) \
+@HAVE_ATF_TRUE@	$(am__DEPENDENCIES_1)
 am__legacy_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c ../confpars.c \
 	../db.c ../class.c ../failover.c ../omapi.c ../mdb.c \
 	../stables.c ../salloc.c ../ddns.c ../dhcpleasequery.c \
 	../dhcpv6.c ../mdb6.c ../ldap.c ../ldap_casa.c ../dhcpd.c \
-	mdb6_unittest.c
+	../leasechain.c mdb6_unittest.c
 @HAVE_ATF_TRUE@am_legacy_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	mdb6_unittest.$(OBJEXT)
 legacy_unittests_OBJECTS = $(am_legacy_unittests_OBJECTS)
@@ -138,7 +149,7 @@ am__load_bal_unittests_SOURCES_DIST = ../dhcp.c ../bootp.c \
 	../confpars.c ../db.c ../class.c ../failover.c ../omapi.c \
 	../mdb.c ../stables.c ../salloc.c ../ddns.c \
 	../dhcpleasequery.c ../dhcpv6.c ../mdb6.c ../ldap.c \
-	../ldap_casa.c ../dhcpd.c load_bal_unittest.c
+	../ldap_casa.c ../dhcpd.c ../leasechain.c load_bal_unittest.c
 @HAVE_ATF_TRUE@am_load_bal_unittests_OBJECTS = $(am__objects_1) \
 @HAVE_ATF_TRUE@	load_bal_unittest.$(OBJEXT)
 load_bal_unittests_OBJECTS = $(am_load_bal_unittests_OBJECTS)
@@ -177,9 +188,11 @@ am__v_CCLD_ = $(am__v_CCLD_@AM_DEFAULT_V@)
 am__v_CCLD_0 = @echo "  CCLD    " $@;
 am__v_CCLD_1 = 
 SOURCES = $(dhcpd_unittests_SOURCES) $(hash_unittests_SOURCES) \
-	$(legacy_unittests_SOURCES) $(load_bal_unittests_SOURCES)
+	$(leaseq_unittests_SOURCES) $(legacy_unittests_SOURCES) \
+	$(load_bal_unittests_SOURCES)
 DIST_SOURCES = $(am__dhcpd_unittests_SOURCES_DIST) \
 	$(am__hash_unittests_SOURCES_DIST) \
+	$(am__leaseq_unittests_SOURCES_DIST) \
 	$(am__legacy_unittests_SOURCES_DIST) \
 	$(am__load_bal_unittests_SOURCES_DIST)
 RECURSIVE_TARGETS = all-recursive check-recursive cscopelist-recursive \
@@ -361,7 +374,7 @@ EXTRA_DIST = Atffile
 DHCPSRC = ../dhcp.c ../bootp.c ../confpars.c ../db.c ../class.c      \
           ../failover.c ../omapi.c ../mdb.c ../stables.c ../salloc.c \
           ../ddns.c ../dhcpleasequery.c ../dhcpv6.c ../mdb6.c        \
-          ../ldap.c ../ldap_casa.c ../dhcpd.c
+          ../ldap.c ../ldap_casa.c ../dhcpd.c ../leasechain.c
 
 DHCPLIBS = $(top_builddir)/common/libdhcp.a $(top_builddir)/omapip/libomapi.a    \
           $(top_builddir)/dhcpctl/libdhcpctl.a $(top_builddir)/bind/lib/libirs.a \
@@ -380,6 +393,8 @@ ATF_TESTS = $(am__append_1)
 @HAVE_ATF_TRUE@legacy_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 @HAVE_ATF_TRUE@load_bal_unittests_SOURCES = $(DHCPSRC) load_bal_unittest.c
 @HAVE_ATF_TRUE@load_bal_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
+@HAVE_ATF_TRUE@leaseq_unittests_SOURCES = $(DHCPSRC) leaseq_unittest.c
+@HAVE_ATF_TRUE@leaseq_unittests_LDADD = $(DHCPLIBS) $(ATF_LDFLAGS)
 all: all-recursive
 
 .SUFFIXES:
@@ -426,6 +441,10 @@ hash_unittests$(EXEEXT): $(hash_unittests_OBJECTS) $(hash_unittests_DEPENDENCIES
 	@rm -f hash_unittests$(EXEEXT)
 	$(AM_V_CCLD)$(LINK) $(hash_unittests_OBJECTS) $(hash_unittests_LDADD) $(LIBS)
 
+leaseq_unittests$(EXEEXT): $(leaseq_unittests_OBJECTS) $(leaseq_unittests_DEPENDENCIES) $(EXTRA_leaseq_unittests_DEPENDENCIES) 
+	@rm -f leaseq_unittests$(EXEEXT)
+	$(AM_V_CCLD)$(LINK) $(leaseq_unittests_OBJECTS) $(leaseq_unittests_LDADD) $(LIBS)
+
 legacy_unittests$(EXEEXT): $(legacy_unittests_OBJECTS) $(legacy_unittests_DEPENDENCIES) $(EXTRA_legacy_unittests_DEPENDENCIES) 
 	@rm -f legacy_unittests$(EXEEXT)
 	$(AM_V_CCLD)$(LINK) $(legacy_unittests_OBJECTS) $(legacy_unittests_LDADD) $(LIBS)
@@ -453,6 +472,8 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ldap.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ldap_casa.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/leasechain.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/leaseq_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/load_bal_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mdb.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mdb6.Po@am__quote@
@@ -714,6 +735,20 @@ dhcpd.obj: ../dhcpd.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o dhcpd.obj `if test -f '../dhcpd.c'; then $(CYGPATH_W) '../dhcpd.c'; else $(CYGPATH_W) '$(srcdir)/../dhcpd.c'; fi`
 
+leasechain.o: ../leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT leasechain.o -MD -MP -MF $(DEPDIR)/leasechain.Tpo -c -o leasechain.o `test -f '../leasechain.c' || echo '$(srcdir)/'`../leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/leasechain.Tpo $(DEPDIR)/leasechain.Po
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='../leasechain.c' object='leasechain.o' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o leasechain.o `test -f '../leasechain.c' || echo '$(srcdir)/'`../leasechain.c
+
+leasechain.obj: ../leasechain.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT leasechain.obj -MD -MP -MF $(DEPDIR)/leasechain.Tpo -c -o leasechain.obj `if test -f '../leasechain.c'; then $(CYGPATH_W) '../leasechain.c'; else $(CYGPATH_W) '$(srcdir)/../leasechain.c'; fi`
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/leasechain.Tpo $(DEPDIR)/leasechain.Po
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='../leasechain.c' object='leasechain.obj' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o leasechain.obj `if test -f '../leasechain.c'; then $(CYGPATH_W) '../leasechain.c'; else $(CYGPATH_W) '$(srcdir)/../leasechain.c'; fi`
+
 # This directory's subdirectories are mostly independent; you can cd
 # into them and run 'make' without going through this Makefile.
 # To change the values of 'make' variables: instead of editing Makefiles,
diff --git a/server/tests/leaseq_unittest.c b/server/tests/leaseq_unittest.c
new file mode 100644
index 00000000..9a9313e5
--- /dev/null
+++ b/server/tests/leaseq_unittest.c
@@ -0,0 +1,503 @@
+/*
+ * Copyright (C) 2015 Internet Systems Consortium, Inc. ("ISC")
+ *
+ * Permission to use, copy, modify, and/or 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.
+ */
+
+#include <config.h>
+
+#include "dhcpd.h"
+
+#include <atf-c.h>
+
+/*
+ * Test the lease queue code.  These tests will verify that we can
+ * add, find and remove leases from the lease queue code
+ *
+ * Thoughout the tests
+ * lq will be the lease queue for which we add or removing leases
+ * test_leaseX will be the leases we add or remove
+ * We only care about the sort_time in the lease structure for these
+ * tests but need to do a lease_reference in order to keep the ref
+ * count positive to avoid the omapi code trying to free the object.
+ * We can't use lease_allocate easily as we haven't set up the omapi
+ * object information in the test.
+ */
+
+#if defined (BINARY_LEASES)
+#define INIT_LQ(LQ) memset(&(LQ), 0, sizeof(struct leasechain))
+#else
+#define INIT_LQ(LQ) lq = NULL
+#endif
+
+/* Test basic leaseq functions with a single lease */
+/*- empty, add, get, and remove */
+ATF_TC(leaseq_basic);
+ATF_TC_HEAD(leaseq_basic, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify basic functions");
+}
+
+ATF_TC_BODY(leaseq_basic, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease1, *check_lease;
+
+	INIT_LQ(lq);
+
+	memset(&test_lease1, 0, sizeof(struct lease));
+	test_lease1.sort_time = 10;
+	check_lease = NULL;
+	lease_reference(&check_lease, &test_lease1, MDL);
+
+	/* Check that the lq is empty */
+	if ((LEASE_NOT_EMPTY(lq)) || (LEASE_NOT_EMPTYP(&lq)))
+		atf_tc_fail("lq not empty at start.");
+
+	/* And that getting the first lease is okay when queue is empty  */
+	if ((LEASE_GET_FIRST(lq) != NULL) || (LEASE_GET_FIRSTP(&lq) != NULL))
+		atf_tc_fail("lease not null");
+
+	/* Add a lease */
+	LEASE_INSERTP(&lq, &test_lease1);
+
+	/* lq shouldn't be empty anymore */
+	if (!(LEASE_NOT_EMPTY(lq)) || !(LEASE_NOT_EMPTYP(&lq)))
+		atf_tc_fail("lq empty after insertion.");
+
+	/* We should have the same lease we inserted */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease1)
+		atf_tc_fail("leases don't match");
+
+	/* We should have the same lease we inserted */
+	check_lease = LEASE_GET_FIRSTP(&lq);
+	if (check_lease != &test_lease1)
+		atf_tc_fail("leases don't match");
+
+	/* Check that doing a get on the last lease returns NULL */
+	if ((LEASE_GET_NEXT(lq, check_lease) != NULL) ||
+	    (LEASE_GET_NEXTP(&lq, check_lease) != NULL)) {
+		atf_tc_fail("Next not null");
+	}
+
+	/* Remove the lease */
+	LEASE_REMOVEP(&lq, &test_lease1);
+
+	/* and verify the lease queue is empty again */
+	if ((LEASE_NOT_EMPTY(lq)) || (LEASE_NOT_EMPTYP(&lq)))
+		atf_tc_fail("lq not empty afer removal");
+
+	/* And that getting the first lease is okay when queue is empty  */
+	if ((LEASE_GET_FIRST(lq) != NULL) || (LEASE_GET_FIRSTP(&lq) != NULL))
+		atf_tc_fail("lease not null");
+}
+
+/* Test if we can add leases to the end of the list and remove them
+ * from the end */
+ATF_TC(leaseq_add_to_end);
+ATF_TC_HEAD(leaseq_add_to_end, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding to end of list");
+}
+
+ATF_TC_BODY(leaseq_add_to_end, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create and add 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 3; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+
+	/* Remove the last lease and check the list */
+	LEASE_REMOVEP(&lq, &test_lease[2]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("wrong lease after remove, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("wrong lease after remove, 2");
+
+	LEASE_REMOVEP(&lq, &test_lease[1]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("wrong lease after remove, 3");
+
+	LEASE_REMOVEP(&lq, check_lease);
+
+	/* The lease queue should now be empty */
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("lq not empty afer removal");
+}
+
+/* Test if we can add leases to the start of the list and remove them
+ * from the start */
+ATF_TC(leaseq_add_to_start);
+ATF_TC_HEAD(leaseq_add_to_start, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding to start of list");
+}
+
+ATF_TC_BODY(leaseq_add_to_start, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+	}
+
+	/* Add leases */
+	LEASE_INSERTP(&lq, &test_lease[2]);
+	LEASE_INSERTP(&lq, &test_lease[1]);
+	LEASE_INSERTP(&lq, &test_lease[0]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 3; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+
+	/* Remove the first lease and check the next one */
+	check_lease = LEASE_GET_FIRST(lq);
+	LEASE_REMOVEP(&lq, check_lease);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("wrong lease after remove, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 2");
+
+	check_lease = LEASE_GET_FIRST(lq);
+	LEASE_REMOVEP(&lq, check_lease);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 3");
+
+	LEASE_REMOVEP(&lq, check_lease);
+
+	/* The lease queue should now be empty */
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("lq not empty afer removal");
+}
+
+/* Test if we can add leases to the middle of the list and remove them
+ * from the middle */
+ATF_TC(leaseq_add_to_middle);
+ATF_TC_HEAD(leaseq_add_to_middle, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding to end of list");
+}
+
+ATF_TC_BODY(leaseq_add_to_middle, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+	}
+
+	/* Add leases */
+	LEASE_INSERTP(&lq, &test_lease[0]);
+	LEASE_INSERTP(&lq, &test_lease[2]);
+	LEASE_INSERTP(&lq, &test_lease[1]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 3; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+
+	/* Remove the middle lease and check the list */
+	LEASE_REMOVEP(&lq, &test_lease[1]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("wrong lease after remove, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 2");
+
+	LEASE_REMOVEP(&lq, &test_lease[0]);
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("wrong lease after remove, 3");
+
+	LEASE_REMOVEP(&lq, check_lease);
+
+	/* The lease queue should now be empty */
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("lq not empty afer removal");
+}
+
+/* Test if we can cycle the leases we add three leases then remove
+ * the first one, update it's sort time and re add it */
+ATF_TC(leaseq_cycle);
+ATF_TC_HEAD(leaseq_cycle, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify cycling the list");
+}
+
+ATF_TC_BODY(leaseq_cycle, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[3], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create and add 3 leases */
+	for (i = 0; i < 3; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* Remove first lease, update it and re-insert it */
+	LEASE_REMOVEP(&lq, &test_lease[0]);
+	test_lease[0].sort_time = 4;
+	LEASE_INSERTP(&lq, &test_lease[0]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("leases don't match, 1");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("leases don't match, 2");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("leases don't match, 3");
+
+	/* Remove first lease, update it and re-insert it */
+	LEASE_REMOVEP(&lq, &test_lease[1]);
+	test_lease[1].sort_time = 5;
+	LEASE_INSERTP(&lq, &test_lease[1]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("leases don't match, 4");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("leases don't match, 5");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("leases don't match, 6");
+
+	/* Remove first lease, update it and re-insert it */
+	LEASE_REMOVEP(&lq, &test_lease[2]);
+	test_lease[2].sort_time = 6;
+	LEASE_INSERTP(&lq, &test_lease[2]);
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	if (check_lease != &test_lease[0])
+		atf_tc_fail("leases don't match, 7");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[1])
+		atf_tc_fail("leases don't match, 8");
+	check_lease = LEASE_GET_NEXT(lq, check_lease);
+	if (check_lease != &test_lease[2])
+		atf_tc_fail("leases don't match, 9");
+}
+
+/* Test what happens if we set the growth factor to a smallish number
+ * and add enough leases to require it to grow multiple times
+ * Mostly this is for the binary leases case but we can most of the
+ * test for both.
+ */
+
+ATF_TC(leaseq_long);
+ATF_TC_HEAD(leaseq_long, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify a long list");
+}
+
+ATF_TC_BODY(leaseq_long, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[20], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+#if defined (BINARY_LEASES)
+	lc_init_growth(&lq, 5);
+#endif
+
+	/* create and add 10 leases */
+	for (i = 0; i < 10; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 10; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+
+	/* Remove first 5 */
+	for (i = 0; i < 5; i++) {
+		LEASE_REMOVEP(&lq, &test_lease[i]);
+	}
+
+	/* Add 10 more */
+	for (i = 10; i < 20; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		test_lease[i].sort_time = i;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* and the first 5 */
+	for (i = 0; i < 5; i++) {
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* and check them all out */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 20; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+}
+
+/* Test if we can add leases that all have the same sort time
+ */
+ATF_TC(leaseq_same_time);
+ATF_TC_HEAD(leaseq_same_time, tc)
+{
+	atf_tc_set_md_var(tc, "descr", "Verify adding leases with same time");
+}
+
+ATF_TC_BODY(leaseq_same_time, tc)
+{
+	LEASE_STRUCT lq;
+	struct lease test_lease[20], *check_lease;
+	int i;
+
+	INIT_LQ(lq);
+
+	/* create and add 20 leases */
+	for (i = 0; i < 20; i++) {
+		memset(&test_lease[i], 0, sizeof(struct lease));
+		if (i < 10) 
+			test_lease[i].sort_time = 10;
+		else
+			test_lease[i].sort_time = 20;
+		check_lease = NULL;
+		lease_reference(&check_lease, &test_lease[i], MDL);
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+#if defined (BINARY_LEASES)
+	/* the ordering isn't well defined for either but we check
+	 * to see what happens in the binary case.  At the start
+	 * the leases should stay in the order they were added.
+	 */
+
+	/* check ordering of leases */
+	check_lease = LEASE_GET_FIRST(lq);
+	for (i = 0; i < 20; i++) {
+		if (check_lease != &test_lease[i])
+			atf_tc_fail("leases don't match 1, %d", i);
+		check_lease = LEASE_GET_NEXT(lq, check_lease);
+	}
+	if (check_lease != NULL)
+		atf_tc_fail("lease not null");
+#endif
+
+	/* Remove first 10, update their time, but still before
+	 * the previous 10 and re add them */
+	for (i = 0; i < 10; i++) {
+		LEASE_REMOVEP(&lq, &test_lease[i]);
+		test_lease[i].sort_time = 15;
+		LEASE_INSERTP(&lq, &test_lease[i]);
+	}
+
+	/* The ordering becomes random at this point so we don't
+	 * check it.  We try to remove them all and see that
+	 * we got to an empty queue.
+	 */
+	for (i = 0; i < 20; i++) {
+		LEASE_REMOVEP(&lq, &test_lease[i]);
+	}
+	if (LEASE_NOT_EMPTY(lq))
+		atf_tc_fail("queue not empty");
+
+}
+
+ATF_TP_ADD_TCS(tp)
+{
+	ATF_TP_ADD_TC(tp, leaseq_basic);
+	ATF_TP_ADD_TC(tp, leaseq_add_to_end);
+	ATF_TP_ADD_TC(tp, leaseq_add_to_start);
+	ATF_TP_ADD_TC(tp, leaseq_add_to_middle);
+	ATF_TP_ADD_TC(tp, leaseq_cycle);
+	ATF_TP_ADD_TC(tp, leaseq_long);
+	ATF_TP_ADD_TC(tp, leaseq_same_time);
+	return (atf_no_error());
+}