From 3933e2aa5183d4602c4fffee4f2ae0d9ca25df99 Mon Sep 17 00:00:00 2001 From: Shawn Routhier Date: Wed, 27 May 2015 13:17:46 -0700 Subject: [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. --- server/Makefile.am | 2 +- server/Makefile.in | 19 +- server/confpars.c | 8 + server/dhcp.c | 45 ++- server/dhcpd.c | 6 + server/failover.c | 65 ++-- server/leasechain.c | 695 +++++++++++++++++++++++++++++++++++++++++ server/mdb.c | 310 ++++++++++++------ server/omapi.c | 27 +- server/tests/Makefile.am | 7 +- server/tests/Makefile.in | 53 +++- server/tests/leaseq_unittest.c | 503 +++++++++++++++++++++++++++++ 12 files changed, 1568 insertions(+), 172 deletions(-) create mode 100644 server/leasechain.c create mode 100644 server/tests/leaseq_unittest.c (limited to 'server') 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 + * + * 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 + +#include "dhcpd.h" + +#include + +/* + * 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()); +} -- cgit v1.2.1