- The server's "by client-id" and "by hardware address" hash table lists

  are now sorted according to the preference to re-allocate that lease to
  returning clients.  This should eliminate pool starvation problems
  arising when "INIT" clients were given new leases rather than presently
  active ones. [ISC-Bugs #16831b]

3 files changed, 181 insertions, 34 deletions

diff --git a/RELNOTES b/RELNOTES
index f1a717b4..33fa2eef 100644
--- a/RELNOTES
+++ b/RELNOTES
@@ -129,6 +129,12 @@ and for prodding me into improving it.
 - dhclient now closes its descriptor to dhclient.leases prior to executing
   dhclient-script.  Thanks to a patch from Tomas Pospisek.
 
+- The server's "by client-id" and "by hardware address" hash table lists
+  are now sorted according to the preference to re-allocate that lease to
+  returning clients.  This should eliminate pool starvation problems
+  arising when "INIT" clients were given new leases rather than presently
+  active ones.
+
 			Changes since 3.0.5rc2
 
 - Failover servers try harder to retransmit binding updates upon entering
diff --git a/server/dhcp.c b/server/dhcp.c
index 21fadf57..0bb9e5d0 100644
--- a/server/dhcp.c
+++ b/server/dhcp.c
@@ -34,7 +34,7 @@
 
 #ifndef lint
 static char copyright[] =
-"$Id: dhcp.c,v 1.192.2.67 2007/04/20 15:27:36 dhankins Exp $ Copyright (c) 2004-2007 Internet Systems Consortium.  All rights reserved.\n";
+"$Id: dhcp.c,v 1.192.2.68 2007/04/26 22:57:53 dhankins Exp $ Copyright (c) 2004-2007 Internet Systems Consortium.  All rights reserved.\n";
 #endif /* not lint */
 
 #include "dhcpd.h"
@@ -3098,10 +3098,14 @@ int find_lease (struct lease **lp,
 	}
 
 	/* If we found leases matching the client identifier, loop through
-	   the n_uid pointer looking for one that's actually valid.   We
-	   can't do this until we get here because we depend on
-	   packet -> known, which may be set by either the uid host
-	   lookup or the haddr host lookup. */
+	 * the n_uid pointer looking for one that's actually valid.   We
+	 * can't do this until we get here because we depend on
+	 * packet -> known, which may be set by either the uid host
+	 * lookup or the haddr host lookup.
+	 *
+	 * Note that the n_uid lease chain is sorted in order of
+	 * preference, so the first one is the best one.
+	 */
 	while (uid_lease) {
 #if defined (DEBUG_FIND_LEASE)
 		log_info ("trying next lease matching client id: %s",
@@ -3160,8 +3164,12 @@ int find_lease (struct lease **lp,
 #endif
 
 	/* Find a lease whose hardware address matches, whose client
-	   identifier matches, that's permitted, and that's on the
-	   correct subnet. */
+	 * identifier matches (or equally doesn't have one), that's
+	 * permitted, and that's on the correct subnet.
+	 *
+	 * Note that the n_hw chain is sorted in order of preference, so
+	 * the first one found is the best one.
+	 */
 	h.hlen = packet -> raw -> hlen + 1;
 	h.hbuf [0] = packet -> raw -> htype;
 	memcpy (&h.hbuf [1], packet -> raw -> chaddr, packet -> raw -> hlen);
diff --git a/server/mdb.c b/server/mdb.c
index 0ebe325b..5b4ee4d6 100644
--- a/server/mdb.c
+++ b/server/mdb.c
@@ -34,7 +34,7 @@
 
 #ifndef lint
 static char copyright[] =
-"$Id: mdb.c,v 1.67.2.27 2006/07/18 18:16:25 dhankins Exp $ Copyright (c) 2004-2005 Internet Systems Consortium.  All rights reserved.\n";
+"$Id: mdb.c,v 1.67.2.28 2007/04/26 22:57:53 dhankins Exp $ Copyright (c) 2004-2005 Internet Systems Consortium.  All rights reserved.\n";
 #endif /* not lint */
 
 #include "dhcpd.h"
@@ -1588,29 +1588,117 @@ int find_lease_by_hw_addr (struct lease **lp,
 				  hwaddr, hwlen, file, line);
 }
 
-/* Add the specified lease to the uid hash. */
-
-void uid_hash_add (lease)
-	struct lease *lease;
+/* If the lease is preferred over the candidate, return truth.  The
+ * 'cand' and 'lease' names are retained to read more clearly against
+ * the 'uid_hash_add' and 'hw_hash_add' functions (this is common logic
+ * to those two functions).
+ *
+ * 1) ACTIVE leases are preferred.  The active lease with
+ *    the longest lifetime is preferred over shortest.
+ * 2) "transitional states" are next, this time with the
+ *    most recent CLTT.
+ * 3) free/backup/etc states are next, again with CLTT.  In truth we
+ *    should never see reset leases for this.
+ * 4) Abandoned leases are always dead last.
+ */
+static isc_boolean_t
+client_lease_preferred(struct lease *cand, struct lease *lease)
 {
-	struct lease *head = (struct lease *)0;
-	struct lease *next = (struct lease *)0;
+	if (cand->binding_state == FTS_ACTIVE) {
+		if (lease->binding_state == FTS_ACTIVE &&
+		    lease->ends >= cand->ends)
+			return ISC_TRUE;
+	} else if (cand->binding_state == FTS_EXPIRED ||
+		   cand->binding_state == FTS_RELEASED) {
+		if (lease->binding_state == FTS_ACTIVE)
+			return ISC_TRUE;
+
+		if ((lease->binding_state == FTS_EXPIRED ||
+		     lease->binding_state == FTS_RELEASED) &&
+		    lease->cltt >= cand->cltt)
+			return ISC_TRUE;
+	} else if (cand->binding_state != FTS_ABANDONED) {
+		if (lease->binding_state == FTS_ACTIVE ||
+		    lease->binding_state == FTS_EXPIRED ||
+		    lease->binding_state == FTS_RELEASED)
+			return ISC_TRUE;
+
+		if (lease->binding_state != FTS_ABANDONED &&
+		    lease->cltt >= cand->cltt)
+			return ISC_TRUE;
+	} else /* (cand->binding_state == FTS_ABANDONED) */ {
+		if (lease->binding_state != FTS_ABANDONED ||
+		    lease->cltt >= cand->cltt)
+			return ISC_TRUE;
+	}
+
+	return ISC_FALSE;
+}
 
+/* Add the specified lease to the uid hash. */
+void
+uid_hash_add(struct lease *lease)
+{
+	struct lease *head = NULL;
+	struct lease *cand = NULL;
+	struct lease *prev = NULL;
+	struct lease *next = NULL;
 
 	/* If it's not in the hash, just add it. */
 	if (!find_lease_by_uid (&head, lease -> uid, lease -> uid_len, MDL))
 		lease_hash_add (lease_uid_hash, lease -> uid,
 				lease -> uid_len, lease, MDL);
 	else {
-		/* Otherwise, attach it to the end of the list. */
-		while (head -> n_uid) {
-			lease_reference (&next, head -> n_uid, MDL);
-			lease_dereference (&head, MDL);
-			lease_reference (&head, next, MDL);
-			lease_dereference (&next, MDL);
+		/* Otherwise, insert it into the list in order of its
+		 * preference for "resuming allocation to the client."
+		 *
+		 * Because we don't have control of the hash bucket index
+		 * directly, we have to remove and re-insert the client
+		 * id into the hash if we're inserting onto the head.
+		 */
+		lease_reference(&cand, head, MDL);
+		while (cand != NULL) {
+			if (client_lease_preferred(cand, lease))
+				break;
+
+			if (prev != NULL)
+				lease_dereference(&prev, MDL);
+			lease_reference(&prev, cand, MDL);
+
+			if (cand->n_uid != NULL)
+				lease_reference(&next, cand->n_uid, MDL);
+
+			lease_dereference(&cand, MDL);
+
+			if (next != NULL) {
+				lease_reference(&cand, next, MDL);
+				lease_dereference(&next, MDL);
+			}
 		}
-		lease_reference (&head -> n_uid, lease, MDL);
-		lease_dereference (&head, MDL);
+
+		/* If we want to insert 'before cand', and prev is NULL,
+		 * then it was the head of the list.  Assume that position.
+		 */
+		if (prev == NULL) {
+			lease_reference(&lease->n_uid, head, MDL);
+			lease_hash_delete(lease_uid_hash, lease->uid,
+					  lease->uid_len, MDL);
+			lease_hash_add(lease_uid_hash, lease->uid,
+				       lease->uid_len, lease, MDL);
+		} else /* (prev != NULL) */ {
+			if(prev->n_uid != NULL) {
+				lease_reference(&lease->n_uid, prev->n_uid,
+						MDL);
+				lease_dereference(&prev->n_uid, MDL);
+			}
+			lease_reference(&prev->n_uid, lease, MDL);
+
+			lease_dereference(&prev, MDL);
+		}
+
+		if (cand != NULL)
+			lease_dereference(&cand, MDL);
+		lease_dereference(&head, MDL);
 	}
 }
 
@@ -1664,11 +1752,13 @@ void uid_hash_delete (lease)
 
 /* Add the specified lease to the hardware address hash. */
 
-void hw_hash_add (lease)
-	struct lease *lease;
+void
+hw_hash_add(struct lease *lease)
 {
-	struct lease *head = (struct lease *)0;
-	struct lease *next = (struct lease *)0;
+	struct lease *head = NULL;
+	struct lease *cand = NULL;
+	struct lease *prev = NULL;
+	struct lease *next = NULL;
 
 	/* If it's not in the hash, just add it. */
 	if (!find_lease_by_hw_addr (&head, lease -> hardware_addr.hbuf,
@@ -1678,16 +1768,59 @@ void hw_hash_add (lease)
 				lease -> hardware_addr.hlen,
 				lease, MDL);
 	else {
-		/* Otherwise, attach it to the end of the list. */
-		while (head -> n_hw) {
-			lease_reference (&next, head -> n_hw, MDL);
-			lease_dereference (&head, MDL);
-			lease_reference (&head, next, MDL);
-			lease_dereference (&next, MDL);
+		/* Otherwise, insert it into the list in order of its
+		 * preference for "resuming allocation to the client."
+		 *
+		 * Because we don't have control of the hash bucket index
+		 * directly, we have to remove and re-insert the client
+		 * id into the hash if we're inserting onto the head.
+		 */
+		lease_reference(&cand, head, MDL);
+		while (cand != NULL) {
+			if (client_lease_preferred(cand, lease))
+				break;
+
+			if (prev != NULL)
+				lease_dereference(&prev, MDL);
+			lease_reference(&prev, cand, MDL);
+
+			if (cand->n_hw != NULL)
+				lease_reference(&next, cand->n_hw, MDL);
+
+			lease_dereference(&cand, MDL);
+
+			if (next != NULL) {
+				lease_reference(&cand, next, MDL);
+				lease_dereference(&next, MDL);
+			}
 		}
 
-		lease_reference (&head -> n_hw, lease, MDL);
-		lease_dereference (&head, MDL);
+		/* If we want to insert 'before cand', and prev is NULL,
+		 * then it was the head of the list.  Assume that position.
+		 */
+		if (prev == NULL) {
+			lease_reference(&lease->n_hw, head, MDL);
+			lease_hash_delete(lease_hw_addr_hash,
+					  lease->hardware_addr.hbuf,
+					  lease->hardware_addr.hlen, MDL);
+			lease_hash_add(lease_hw_addr_hash,
+				       lease->hardware_addr.hbuf,
+				       lease->hardware_addr.hlen,
+				       lease, MDL);
+		} else /* (prev != NULL) */ {
+			if(prev->n_hw != NULL) {
+				lease_reference(&lease->n_hw, prev->n_uid,
+						MDL);
+				lease_dereference(&prev->n_hw, MDL);
+			}
+			lease_reference(&prev->n_hw, lease, MDL);
+
+			lease_dereference(&prev, MDL);
+		}
+
+		if (cand != NULL)
+			lease_dereference(&cand, MDL);
+		lease_dereference(&head, MDL);
 	}
 }