1*13df4856Schristos /* $NetBSD: leasechain.c,v 1.3 2022/04/03 01:10:59 christos Exp $ */
23965be93Schristos
33965be93Schristos /* leasechain.c
43965be93Schristos
53965be93Schristos Additional support for in-memory database support */
63965be93Schristos
73965be93Schristos /*
8*13df4856Schristos * Copyright (C) 2015-2022 Internet Systems Consortium, Inc. ("ISC")
93965be93Schristos *
103965be93Schristos * This Source Code Form is subject to the terms of the Mozilla Public
113965be93Schristos * License, v. 2.0. If a copy of the MPL was not distributed with this
123965be93Schristos * file, You can obtain one at http://mozilla.org/MPL/2.0/.
133965be93Schristos *
143965be93Schristos * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
153965be93Schristos * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
163965be93Schristos * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
173965be93Schristos * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
183965be93Schristos * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
193965be93Schristos * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
203965be93Schristos * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
213965be93Schristos *
223965be93Schristos * Internet Systems Consortium, Inc.
23*13df4856Schristos * PO Box 360
24*13df4856Schristos * Newmarket, NH 03857 USA
253965be93Schristos * <info@isc.org>
263965be93Schristos * https://www.isc.org/
273965be93Schristos *
283965be93Schristos */
293965be93Schristos
303965be93Schristos #include <sys/cdefs.h>
31*13df4856Schristos __RCSID("$NetBSD: leasechain.c,v 1.3 2022/04/03 01:10:59 christos Exp $");
323965be93Schristos
333965be93Schristos /*! \file server\leasechaing.c
343965be93Schristos *
353965be93Schristos * \page leasechain structures overview
363965be93Schristos *
373965be93Schristos * A brief description of the leasechain structures
383965be93Schristos *
393965be93Schristos * This file provides additional data structures for a leasecain to
403965be93Schristos * provide faster access to leases on the queues associated with a pool
413965be93Schristos * than a linear walk. Each pool has a set of queues: active, free, backup,
423965be93Schristos * expired and abandoned to track leases as they are handed out and returned.
433965be93Schristos * The original code use a simply linear list for each of those pools but
443965be93Schristos * this can present performance issues if the pool is large and the lists are
453965be93Schristos * long.
463965be93Schristos * This code adds an array on top of the list allowing us to search the list
473965be93Schristos * in a binary fashion instead of a linear walk.
483965be93Schristos *
493965be93Schristos * \verbatim
503965be93Schristos * leasechain
513965be93Schristos * +------------+ +-------+-------+-------+-------+
523965be93Schristos * | lease list |--> | lease | lease | lease | lease |....
533965be93Schristos * | start | | ptr | ptr | ptr | ptr |
543965be93Schristos * | end | +-------+-------+-------+-------+
553965be93Schristos * | max | | |
563965be93Schristos * +------------+ V V
573965be93Schristos * +-------+ +-------+
583965be93Schristos * | lease | | lease |
593965be93Schristos * | | | |
603965be93Schristos * | next |->| next |->NULL
613965be93Schristos * NULL<- | prev |<-| prev |
623965be93Schristos * +-------+ +-------+
633965be93Schristos *
643965be93Schristos * The linked list is maintained in an ordered state. Inserting an entry is
653965be93Schristos * accomplished by doing a binary search on the array to find the proper place
663965be93Schristos * in the list and then updating the pointers in the linked list to include the
673965be93Schristos * new entry. The entry is added into the array by copying the remainder of
683965be93Schristos * the array to provide space for the new entry.
693965be93Schristos * Removing an entry is the reverse.
703965be93Schristos * The arrays for the queues will be pre-allocated but not all of them will be
713965be93Schristos * large enough to hold all of the leases. If additional space is required the
723965be93Schristos * array will be grown.
733965be93Schristos */
743965be93Schristos
753965be93Schristos #include "dhcpd.h"
763965be93Schristos
773965be93Schristos #if defined (BINARY_LEASES)
783965be93Schristos /* Default number number of lease pointers to add to the leasechain array
793965be93Schristos * everytime it grows beyond the current size
803965be93Schristos */
813965be93Schristos #define LC_GROWTH_DELTA 256
823965be93Schristos
833965be93Schristos /*!
843965be93Schristos *
853965be93Schristos * \brief Check if leasechain isn't empty
863965be93Schristos *
873965be93Schristos * \param lc The leasechain to check
883965be93Schristos *
893965be93Schristos * \return 1 if leasechain isn't empty
903965be93Schristos */
913965be93Schristos int
lc_not_empty(struct leasechain * lc)923965be93Schristos lc_not_empty( struct leasechain *lc ) {
933965be93Schristos #if defined (DEBUG_BINARY_LEASES)
943965be93Schristos log_debug("LC empty check %s:%d", MDL);
953965be93Schristos INSIST(lc != NULL);
963965be93Schristos #endif
973965be93Schristos
983965be93Schristos return (lc->nelem > 0 ? 1 : 0);
993965be93Schristos }
1003965be93Schristos
1013965be93Schristos /*!
1023965be93Schristos *
1033965be93Schristos * \brief Get the first lease from a leasechain
1043965be93Schristos *
1053965be93Schristos * \param lc The leasechain to check
1063965be93Schristos *
1073965be93Schristos * \return A pointer to the first lease from a lease chain, or NULL if none found
1083965be93Schristos */
1093965be93Schristos struct lease *
lc_get_first_lease(struct leasechain * lc)1103965be93Schristos lc_get_first_lease(struct leasechain *lc) {
1113965be93Schristos #if defined (DEBUG_BINARY_LEASES)
1123965be93Schristos log_debug("LC Get first %s:%d", MDL);
1133965be93Schristos INSIST(lc != NULL);
1143965be93Schristos INSIST(lc->total >= lc->nelem);
1153965be93Schristos #endif
1163965be93Schristos
1173965be93Schristos if (lc->nelem > 0) {
1183965be93Schristos return (lc->list)[0];
1193965be93Schristos }
1203965be93Schristos return (NULL);
1213965be93Schristos }
1223965be93Schristos
1233965be93Schristos /*!
1243965be93Schristos *
1253965be93Schristos * \brief Get the next lease from the chain, based on the lease passed in.
1263965be93Schristos *
1273965be93Schristos * \param lc The leasechain to check
1283965be93Schristos * \param lp The lease to start from
1293965be93Schristos *
1303965be93Schristos * \return The next lease in the ordered list after lp
1313965be93Schristos */
1323965be93Schristos struct lease *
lc_get_next(struct leasechain * lc,struct lease * lp)1333965be93Schristos lc_get_next(struct leasechain *lc, struct lease *lp) {
1343965be93Schristos #if defined (DEBUG_BINARY_LEASES)
1353965be93Schristos log_debug("LC Get next %s:%d", MDL);
1363965be93Schristos INSIST(lc != NULL);
1373965be93Schristos INSIST(lp != NULL);
1383965be93Schristos #endif
1393965be93Schristos
1403965be93Schristos return lp->next;
1413965be93Schristos }
1423965be93Schristos
1433965be93Schristos /*!
1443965be93Schristos *
1453965be93Schristos * \brief Find the best position for inserting a lease
1463965be93Schristos *
1473965be93Schristos * Given a potential range of the array to insert the lease into this routine
1483965be93Schristos * will recursively examine the range to find the proper place in which to
1493965be93Schristos * insert the lease.
1503965be93Schristos *
1513965be93Schristos * \param lc The leasechain to add the lease to
1523965be93Schristos * \param lp The lease to insert
1533965be93Schristos * \param min The minium index of the potential range for insertion
1543965be93Schristos * \param max The maximum index of the potential range for insertion
1553965be93Schristos *
1563965be93Schristos * \return The index of the array entry to insert the lease
1573965be93Schristos */
1583965be93Schristos size_t
lc_binary_search_insert_point(struct leasechain * lc,struct lease * lp,size_t min,size_t max)1593965be93Schristos lc_binary_search_insert_point(struct leasechain *lc,
1603965be93Schristos struct lease *lp,
1613965be93Schristos size_t min, size_t max)
1623965be93Schristos {
1633965be93Schristos size_t mid_index = ((max - min)/2) + min;
1643965be93Schristos
1653965be93Schristos if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
1663965be93Schristos ((lc->list[mid_index]->sort_time == lp->sort_time) &&
1673965be93Schristos (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
1683965be93Schristos if (mid_index == min) {
1693965be93Schristos /* insert in the min position, as sort_time is larger */
1703965be93Schristos return (min);
1713965be93Schristos }
1723965be93Schristos /* try again with lower half of list */
1733965be93Schristos return (lc_binary_search_insert_point(lc, lp,
1743965be93Schristos min, mid_index - 1));
1753965be93Schristos } else if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
1763965be93Schristos ((lc->list[mid_index]->sort_time == lp->sort_time) &&
1773965be93Schristos (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
1783965be93Schristos if (mid_index == max) {
1793965be93Schristos /* insert in mid_index + 1 as sort_time is smaller */
1803965be93Schristos return (mid_index+1);
1813965be93Schristos }
1823965be93Schristos /* try again with upper half of list */
1833965be93Schristos return (lc_binary_search_insert_point(lc, lp,
1843965be93Schristos mid_index + 1, max));
1853965be93Schristos }
1863965be93Schristos
1873965be93Schristos /* sort_time and sort_tiebreaker match, so insert in this position */
1883965be93Schristos return (mid_index);
1893965be93Schristos }
1903965be93Schristos
1913965be93Schristos /*!
1923965be93Schristos *
1933965be93Schristos * \brief Find an exact match for a lease
1943965be93Schristos *
1953965be93Schristos * Given a potential range of the array to search this routine
1963965be93Schristos * will recursively examine the range to find the proper lease
1973965be93Schristos *
1983965be93Schristos * \param lc The leasechain to check
1993965be93Schristos * \param lp The lease to find
2003965be93Schristos * \param min The minium index of the search range
2013965be93Schristos * \param max The maximum index of the search range
2023965be93Schristos *
2033965be93Schristos * \return The index of the array entry for the lease, SIZE_MAX if the lease
2043965be93Schristos * wasn't found
2053965be93Schristos */
2063965be93Schristos
2073965be93Schristos size_t
lc_binary_search_lease(struct leasechain * lc,struct lease * lp,size_t min,size_t max)2083965be93Schristos lc_binary_search_lease(struct leasechain *lc,
2093965be93Schristos struct lease *lp,
2103965be93Schristos size_t min, size_t max)
2113965be93Schristos {
2123965be93Schristos size_t mid_index;
2133965be93Schristos size_t i;
2143965be93Schristos
2153965be93Schristos if (max < min) {
2163965be93Schristos /* lease not found */
2173965be93Schristos return (SIZE_MAX);
2183965be93Schristos }
2193965be93Schristos
2203965be93Schristos mid_index = ((max - min)/2) + min;
2213965be93Schristos
2223965be93Schristos if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
2233965be93Schristos ((lc->list[mid_index]->sort_time == lp->sort_time) &&
2243965be93Schristos (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
2253965be93Schristos if (mid_index == min) {
2263965be93Schristos /* lease not found */
2273965be93Schristos return (SIZE_MAX);
2283965be93Schristos }
2293965be93Schristos /* try the lower half of the list */
2303965be93Schristos return (lc_binary_search_lease(lc, lp, min, mid_index - 1));
2313965be93Schristos } else if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
2323965be93Schristos ((lc->list[mid_index]->sort_time == lp->sort_time) &&
2333965be93Schristos (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
2343965be93Schristos /* try the upper half of the list */
2353965be93Schristos return (lc_binary_search_lease(lc, lp, mid_index + 1, max));
2363965be93Schristos }
2373965be93Schristos
2383965be93Schristos /*
2393965be93Schristos * As sort_time/sort_tiebreaker may not be unique in the list, once we
2403965be93Schristos * find a match, we need to look before and after from this position
2413965be93Schristos * for all matching sort_time/sort_tiebreaker until we find the exact
2423965be93Schristos * lease or until no matching lease is found
2433965be93Schristos */
2443965be93Schristos if (lp == lc->list[mid_index]) {
2453965be93Schristos return (mid_index);
2463965be93Schristos }
2473965be93Schristos
2483965be93Schristos /* Check out entries below the mid_index */
2493965be93Schristos if (mid_index > min) {
2503965be93Schristos /* We will break out of the loop if we either go past the
2513965be93Schristos * canddiates or hit the end of the range when i == min. As
2523965be93Schristos * i is unsigned we can't check it in the for loop itself.
2533965be93Schristos */
2543965be93Schristos for (i = mid_index - 1; ; i--) {
2553965be93Schristos if (lp == lc->list[i]) {
2563965be93Schristos return (i);
2573965be93Schristos }
2583965be93Schristos
2593965be93Schristos /* Are we done with this range? */
2603965be93Schristos if ((i == min) ||
2613965be93Schristos ((lc->list[i]->sort_time != lp->sort_time) ||
2623965be93Schristos ((lc->list[i]->sort_time == lp->sort_time) &&
2633965be93Schristos (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker)))) {
2643965be93Schristos break;
2653965be93Schristos }
2663965be93Schristos }
2673965be93Schristos }
2683965be93Schristos
2693965be93Schristos /* Check out entries above the mid_index */
2703965be93Schristos if (mid_index < max) {
2713965be93Schristos /* We will break out of the loop if we either go past the
2723965be93Schristos * canddiates or hit the end of the range when i == max.
2733965be93Schristos */
2743965be93Schristos for (i = mid_index + 1; i <= max; i++) {
2753965be93Schristos if (lp == lc->list[i]) {
2763965be93Schristos return (i);
2773965be93Schristos }
2783965be93Schristos
2793965be93Schristos if ((lc->list[i]->sort_time != lp->sort_time) ||
2803965be93Schristos ((lc->list[i]->sort_time == lp->sort_time) &&
2813965be93Schristos (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker))) {
2823965be93Schristos break;
2833965be93Schristos }
2843965be93Schristos }
2853965be93Schristos }
2863965be93Schristos
2873965be93Schristos /* Lease not found */
2883965be93Schristos return (SIZE_MAX);
2893965be93Schristos }
2903965be93Schristos
2913965be93Schristos /*!
2923965be93Schristos *
2933965be93Schristos * \brief Increase the size of the array for the lease chain
2943965be93Schristos *
2953965be93Schristos * \param lc The leasechain to expand
2963965be93Schristos *
2973965be93Schristos * If we are unable to allocate memory we log a fatal error. There's
2983965be93Schristos * not much else to do as we can't figure out where to put the lease.
2993965be93Schristos *
3003965be93Schristos * If we can allocate memory we copy the old lease chain to the new
3013965be93Schristos * lease chain and free the old.
3023965be93Schristos */
3033965be93Schristos void
lc_grow_chain(struct leasechain * lc)3043965be93Schristos lc_grow_chain(struct leasechain *lc) {
3053965be93Schristos #if defined (DEBUG_BINARY_LEASES)
3063965be93Schristos log_debug("LC grow lease chain max was %zu, %s:%d", lc->total, MDL);
3073965be93Schristos #endif
3083965be93Schristos
3093965be93Schristos void *p;
3103965be93Schristos size_t temp_size;
3113965be93Schristos
3123965be93Schristos if (lc->growth == 0)
3133965be93Schristos temp_size = lc->total + LC_GROWTH_DELTA;
3143965be93Schristos else
3153965be93Schristos temp_size = lc->total + lc->growth;
3163965be93Schristos
3173965be93Schristos /* try to allocate the memory */
3183965be93Schristos p = dmalloc(sizeof(struct lease *) * temp_size, MDL);
3193965be93Schristos if (p == NULL) {
3203965be93Schristos log_fatal("LC grow, unable to allocated memory %s:%d", MDL);
3213965be93Schristos }
3223965be93Schristos
3233965be93Schristos /* Success, copy the lease chain and install the new one */
3243965be93Schristos if (lc->list != NULL) {
3253965be93Schristos memcpy(p, lc->list, sizeof(struct lease *) * lc->nelem);
3263965be93Schristos dfree(lc->list, MDL);
3273965be93Schristos }
3283965be93Schristos lc->list = (struct lease **) p;
3293965be93Schristos lc->total = temp_size;
3303965be93Schristos
3313965be93Schristos return;
3323965be93Schristos }
3333965be93Schristos
3343965be93Schristos
3353965be93Schristos /*!
3363965be93Schristos *
3373965be93Schristos * \brief Link a lease to a lease chain position
3383965be93Schristos *
3393965be93Schristos * This function may increase the size of the lease chain if necessary and will
3403965be93Schristos * probably need to move entries in the lease chain around.
3413965be93Schristos *
3423965be93Schristos * \param lc The leasechain to update
3433965be93Schristos * \param lp The lease to insert
3443965be93Schristos * \param n The position in which to insert the lease
3453965be93Schristos *
3463965be93Schristos */
3473965be93Schristos void
lc_link_lcp(struct leasechain * lc,struct lease * lp,size_t n)3483965be93Schristos lc_link_lcp(struct leasechain *lc, struct lease *lp, size_t n) {
3493965be93Schristos #if defined (DEBUG_BINARY_LEASES)
3503965be93Schristos log_debug("LC link lcp %s:%d", MDL);
3513965be93Schristos INSIST (lc != NULL);
3523965be93Schristos INSIST (lp != NULL);
3533965be93Schristos #endif
3543965be93Schristos
3553965be93Schristos if (lc->nelem == lc->total) {
3563965be93Schristos lc_grow_chain(lc);
3573965be93Schristos }
3583965be93Schristos
3593965be93Schristos #if defined (DEBUG_BINARY_LEASES)
3603965be93Schristos log_debug("LC Link lcp position %zu, elem %zu, %s:%d",
3613965be93Schristos n, lc->nelem, MDL);
3623965be93Schristos #endif
3633965be93Schristos
3643965be93Schristos /* create room for the new pointer */
3653965be93Schristos if (n < lc->nelem) {
3663965be93Schristos #if defined (DEBUG_BINARY_LEASES)
3673965be93Schristos log_debug("LC link lcp moving position %zu, moving %zu. %s:%d",
3683965be93Schristos n, (lc->nelem-n), MDL);
3693965be93Schristos #endif
3703965be93Schristos memmove(lc->list + n + 1, lc->list + n,
3713965be93Schristos sizeof(struct lease *) * (lc->nelem-n));
3723965be93Schristos }
3733965be93Schristos
3743965be93Schristos /* clean any stale pointer info from this position before calling
3753965be93Schristos * lease_reference as it won't work if pointer is not NULL
3763965be93Schristos */
3773965be93Schristos lc->list[n] = NULL;
3783965be93Schristos lease_reference(&(lc->list[n]), lp, MDL);
3793965be93Schristos
3803965be93Schristos lc->nelem++;
3813965be93Schristos
3823965be93Schristos lp->lc = lc;
3833965be93Schristos
3843965be93Schristos return;
3853965be93Schristos }
3863965be93Schristos
3873965be93Schristos /*!
3883965be93Schristos *
3893965be93Schristos * \brief Insert the lease at the specified position in both the lease chain
3903965be93Schristos * and the linked list
3913965be93Schristos *
3923965be93Schristos * This function may increase the size of the lease chain if necessary and will
3933965be93Schristos * probably need to move entries in the lease chain around.
3943965be93Schristos * \param lc The leasechain to update
3953965be93Schristos * \param lp The lease to insert
3963965be93Schristos * \param n The position in which to insert the lease
3973965be93Schristos *
3983965be93Schristos */
3993965be93Schristos void
lc_add_lease_pos(struct leasechain * lc,struct lease * lp,size_t pos)4003965be93Schristos lc_add_lease_pos(struct leasechain *lc, struct lease *lp, size_t pos) {
4013965be93Schristos #if defined (DEBUG_BINARY_LEASES)
4023965be93Schristos log_debug("LC Add lease position %zu, %s:%d", pos, MDL);
4033965be93Schristos INSIST (lc != NULL);
4043965be93Schristos INSIST (lp != NULL);
4053965be93Schristos #endif
4063965be93Schristos lc_link_lcp(lc, lp, pos);
4073965be93Schristos
4083965be93Schristos #if 0
4093965be93Schristos /* this shoudln't be necessary, if we still have pointers on
4103965be93Schristos * the lease being inserted things are broken
4113965be93Schristos */
4123965be93Schristos if (lp->prev) {
4133965be93Schristos lease_dereference(&lp->prev, MDL);
4143965be93Schristos }
4153965be93Schristos if (lp->next) {
4163965be93Schristos lease_dereference(&lp->next, MDL);
4173965be93Schristos }
4183965be93Schristos #endif
4193965be93Schristos
4203965be93Schristos /* not the first element? */
4213965be93Schristos if (pos > 0) {
4223965be93Schristos if (lc->list[pos-1]->next) {
4233965be93Schristos lease_dereference(&(lc->list[pos-1]->next), MDL);
4243965be93Schristos }
4253965be93Schristos lease_reference(&(lc->list[pos-1]->next), lp, MDL);
4263965be93Schristos lease_reference(&lp->prev, lc->list[pos-1], MDL );
4273965be93Schristos }
4283965be93Schristos
4293965be93Schristos /* not the last element? we've already bumped nelem when linking
4303965be93Schristos * into the lease chain so nelem should never be zero here */
4313965be93Schristos if (pos < (lc->nelem-1)) {
4323965be93Schristos if (lc->list[pos+1]->prev) {
4333965be93Schristos lease_dereference(&(lc->list[pos+1]->prev), MDL);
4343965be93Schristos }
4353965be93Schristos lease_reference(&(lc->list[pos+1]->prev), lp, MDL);
4363965be93Schristos lease_reference(&lp->next, lc->list[pos+1], MDL);
4373965be93Schristos }
4383965be93Schristos
4393965be93Schristos return;
4403965be93Schristos }
4413965be93Schristos
4423965be93Schristos #ifdef POINTER_DEBUG
4433965be93Schristos /*!
4443965be93Schristos *
4453965be93Schristos * \brief Debug only code, check the lease to verify it is sorted
4463965be93Schristos *
4473965be93Schristos * \param lc The leasechain to verify
4483965be93Schristos *
4493965be93Schristos * Calls log_fatal if the leasechain is not properly sorted
4503965be93Schristos */
4513965be93Schristos void
lc_check_lc_sort_order(struct leasechain * lc)4523965be93Schristos lc_check_lc_sort_order(struct leasechain *lc) {
4533965be93Schristos size_t i;
4543965be93Schristos TIME t = 0;
4553965be93Schristos long int tiebreak = 0;
4563965be93Schristos
4573965be93Schristos log_debug("LC check sort %s:%d", MDL);
4583965be93Schristos for (i = 0; i < lc->nelem; i++ ) {
4593965be93Schristos if ((lc->list[i]->sort_time < t) ||
4603965be93Schristos ((lc->list[i]->sort_time == t) &&
4613965be93Schristos (lc->list[i]->tiebreaker < tiebreaker))) {
4623965be93Schristos if (i > 0) {
4633965be93Schristos print_lease(lc->list[i-1]);
4643965be93Schristos }
4653965be93Schristos print_lease(lc->list[i]);
4663965be93Schristos if (i < lc->nelem - 1) {
4673965be93Schristos print_lease(lc->list[i+1]);
4683965be93Schristos }
4693965be93Schristos log_fatal("lc[%p] not sorted properly", lc);
4703965be93Schristos }
4713965be93Schristos
4723965be93Schristos t = lc->list[i]->sort_time;
4733965be93Schristos tiebreak = lc->list[i]->sort_tiebreaker;
4743965be93Schristos }
4753965be93Schristos }
4763965be93Schristos #endif
4773965be93Schristos
4783965be93Schristos /*!
4793965be93Schristos *
4803965be93Schristos * \brief Add a lease into the sorted lease and lease chain
4813965be93Schristos * The sort_time is set by the caller while the sort_tiebreaker is set here
4823965be93Schristos * The value doesn't much matter as long as it prvoides a way to have different
4833965be93Schristos * values in most of the leases.
4843965be93Schristos *
4853965be93Schristos * When choosing a value for tiebreak we choose:
4863965be93Schristos * 0 for the first lease in the queue
4873965be93Schristos * 0 if the lease is going to the end of the queue with a sort_time greater
4883965be93Schristos * than that of the current last lease
4893965be93Schristos * previous tiebreaker + 1 if it is going to the end of the queue with a
4903965be93Schristos * sort_time equal to that of the current last lease
4913965be93Schristos * random if none of the above fit
4923965be93Schristos *
4933965be93Schristos * During startup when we can take advantage of the fact that leases may already
4943965be93Schristos * be sorted and so check the end of the list to see if we can simply add the
4953965be93Schristos * lease to the end.
4963965be93Schristos *
4973965be93Schristos * \param lc The leasechain in which to insert the lease
4983965be93Schristos * \param lp The lease to insert
4993965be93Schristos *
5003965be93Schristos */
5013965be93Schristos void
lc_add_sorted_lease(struct leasechain * lc,struct lease * lp)5023965be93Schristos lc_add_sorted_lease(struct leasechain *lc, struct lease *lp) {
5033965be93Schristos size_t pos;
5043965be93Schristos
5053965be93Schristos #if defined (DEBUG_BINARY_LEASES)
5063965be93Schristos log_debug("LC add sorted %s:%d", MDL);
5073965be93Schristos INSIST (lc != NULL);
5083965be93Schristos INSIST (lp != NULL);
5093965be93Schristos #endif
5103965be93Schristos if (lc->nelem == 0) {
5113965be93Schristos /* The first lease start with a tiebreak of 0 and add it at
5123965be93Schristos * the first position */
5133965be93Schristos lp->sort_tiebreaker = 0;
5143965be93Schristos
5153965be93Schristos lc_add_lease_pos(lc, lp, 0);
5163965be93Schristos /* log_debug("LC add sorted done, %s:%d", MDL); */
5173965be93Schristos
5183965be93Schristos return;
5193965be93Schristos }
5203965be93Schristos
5213965be93Schristos if (lp->sort_time > lc->list[lc->nelem-1]->sort_time) {
5223965be93Schristos /* Adding to end of queue, with a different sort time */
5233965be93Schristos lp->sort_tiebreaker = 0;
5243965be93Schristos pos = lc->nelem;
5253965be93Schristos } else if (lp->sort_time == lc->list[lc->nelem-1]->sort_time) {
5263965be93Schristos /* Adding to end of queue, with the same sort time */
5273965be93Schristos if (lc->list[lc->nelem-1]->sort_tiebreaker < LONG_MAX)
5283965be93Schristos lp->sort_tiebreaker =
5293965be93Schristos lc->list[lc->nelem-1]->sort_tiebreaker+1;
5303965be93Schristos else
5313965be93Schristos lp->sort_tiebreaker = LONG_MAX;
5323965be93Schristos pos = lc->nelem;
5333965be93Schristos } else {
5343965be93Schristos /* Adding somewhere in the queue, just pick a random value */
5353965be93Schristos lp->sort_tiebreaker = random();
5363965be93Schristos pos = lc_binary_search_insert_point(lc, lp, 0, lc->nelem - 1);
5373965be93Schristos }
5383965be93Schristos
5393965be93Schristos /* Finally add it to the queue */
5403965be93Schristos lc_add_lease_pos(lc, lp, pos);
5413965be93Schristos
5423965be93Schristos #if defined (DEBUG_BINARY_LEASES)
5433965be93Schristos log_debug("LC add sorted complete position %zu, elements %zu, %s:%d",
5443965be93Schristos pos, lc->nelem, MDL);
5453965be93Schristos #endif
5463965be93Schristos
5473965be93Schristos #ifdef POINTER_DEBUG
5483965be93Schristos lc_check_lc_sort_order(lc);
5493965be93Schristos #endif
5503965be93Schristos }
5513965be93Schristos
5523965be93Schristos /*!
5533965be93Schristos *
5543965be93Schristos * \brief Remove the Nth pointer from a leasechain structure and update counters.
5553965be93Schristos * The pointers in the array will be moved to fill in the hole if necessary.
5563965be93Schristos *
5573965be93Schristos * \param lc The lease chain to update
5583965be93Schristos * \param n the entry to remove from the lease chain
5593965be93Schristos */
5603965be93Schristos void
lc_unlink_lcp(struct leasechain * lc,size_t n)5613965be93Schristos lc_unlink_lcp(struct leasechain *lc, size_t n) {
5623965be93Schristos #if defined (DEBUG_BINARY_LEASES)
5633965be93Schristos log_debug("LC unlink lcp %s:%d", MDL);
5643965be93Schristos
5653965be93Schristos /* element index to remove must be less than the number of elements present */
5663965be93Schristos INSIST(n < lc->nelem);
5673965be93Schristos #endif
5683965be93Schristos
5693965be93Schristos /* Clear the pointer from the lease back to the LC */
5703965be93Schristos lc->list[n]->lc = NULL;
5713965be93Schristos
5723965be93Schristos /* Clear the pointer from the LC to the lease */
5733965be93Schristos lease_dereference(&(lc->list[n]), MDL);
5743965be93Schristos
5753965be93Schristos /* memove unless we are removing the last element */
5763965be93Schristos if ((lc->nelem-1) > n) {
5773965be93Schristos memmove(lc->list + n, lc->list + n + 1,
5783965be93Schristos sizeof(struct lease *) * (lc->nelem-1-n));
5793965be93Schristos }
5803965be93Schristos lc->nelem--;
5813965be93Schristos }
5823965be93Schristos
5833965be93Schristos /*!
5843965be93Schristos *
5853965be93Schristos * \brief Remove a lease from a specific position. This will first unlink
5863965be93Schristos * the lease from the lease chain and then update the linked list.
5873965be93Schristos *
5883965be93Schristos * \param lc The lease chain to update
5893965be93Schristos * \param pos the entry to remove from the lease chain
5903965be93Schristos */
5913965be93Schristos void
lc_unlink_lease_pos(struct leasechain * lc,size_t pos)5923965be93Schristos lc_unlink_lease_pos(struct leasechain *lc, size_t pos)
5933965be93Schristos {
5943965be93Schristos #if defined (DEBUG_BINARY_LEASES)
5953965be93Schristos INSIST(lc != NULL);
5963965be93Schristos #endif
5973965be93Schristos
5983965be93Schristos struct lease *lp = NULL;
5993965be93Schristos lease_reference(&lp, lc->list[pos], MDL);
6003965be93Schristos
6013965be93Schristos /* unlink from lease chain list */
6023965be93Schristos lc_unlink_lcp(lc, pos);
6033965be93Schristos
6043965be93Schristos /* unlink from the linked list */
6053965be93Schristos if (lp->next) {
6063965be93Schristos lease_dereference(&lp->next->prev, MDL);
6073965be93Schristos if (lp->prev)
6083965be93Schristos lease_reference(&lp->next->prev, lp->prev, MDL);
6093965be93Schristos }
6103965be93Schristos if (lp->prev) {
6113965be93Schristos lease_dereference(&lp->prev->next, MDL);
6123965be93Schristos if (lp->next)
6133965be93Schristos lease_reference(&lp->prev->next, lp->next, MDL);
6143965be93Schristos lease_dereference(&lp->prev, MDL);
6153965be93Schristos }
6163965be93Schristos if (lp->next) {
6173965be93Schristos lease_dereference(&lp->next, MDL);
6183965be93Schristos }
6193965be93Schristos lease_dereference(&lp, MDL);
6203965be93Schristos }
6213965be93Schristos
6223965be93Schristos /*!
6233965be93Schristos *
6243965be93Schristos * \brief Find a lease in the lease chain and then remove it
6253965be93Schristos * If we can't find the lease on the given lease chain it's a fatal error.
6263965be93Schristos *
6273965be93Schristos * \param lc The lease chain to update
6283965be93Schristos * \param lp The lease to remove
6293965be93Schristos */
6303965be93Schristos void
lc_unlink_lease(struct leasechain * lc,struct lease * lp)6313965be93Schristos lc_unlink_lease(struct leasechain *lc, struct lease *lp) {
6323965be93Schristos #if defined (DEBUG_BINARY_LEASES)
6333965be93Schristos log_debug("LC unlink lease %s:%d", MDL);
6343965be93Schristos
6353965be93Schristos INSIST(lc != NULL);
6363965be93Schristos INSIST(lc->list != NULL);
6373965be93Schristos INSIST(lp != NULL );
6383965be93Schristos INSIST(lp->lc != NULL );
6393965be93Schristos INSIST(lp->lc == lc );
6403965be93Schristos #endif
6413965be93Schristos
6423965be93Schristos size_t pos = lc_binary_search_lease(lc, lp, 0, lc->nelem-1);
6433965be93Schristos if (pos == SIZE_MAX) {
6443965be93Schristos /* fatal, lease not found in leasechain */
6453965be93Schristos log_fatal("Lease with binding state %s not on its queue.",
6463965be93Schristos (lp->binding_state < 1 ||
6473965be93Schristos lp->binding_state > FTS_LAST)
6483965be93Schristos ? "unknown"
6493965be93Schristos : binding_state_names[lp->binding_state - 1]);
6503965be93Schristos }
6513965be93Schristos
6523965be93Schristos lc_unlink_lease_pos(lc, pos);
6533965be93Schristos }
6543965be93Schristos
6553965be93Schristos /*!
6563965be93Schristos *
6573965be93Schristos * \brief Unlink all the leases in the lease chain and free the
6583965be93Schristos * lease chain structure. The leases will be freed if and when
6593965be93Schristos * any other references to them are cleared.
6603965be93Schristos *
6613965be93Schristos * \param lc the lease chain to clear
6623965be93Schristos */
6633965be93Schristos void
lc_delete_all(struct leasechain * lc)6643965be93Schristos lc_delete_all(struct leasechain *lc) {
6653965be93Schristos size_t i;
6663965be93Schristos
6673965be93Schristos if (lc->nelem > 0) {
6683965be93Schristos /* better to delete from the last one, to avoid the memmove */
6693965be93Schristos for (i = lc->nelem - 1; ; i--) {
6703965be93Schristos lc_unlink_lease_pos(lc, i);
6713965be93Schristos if (i == 0) {
6723965be93Schristos break;
6733965be93Schristos }
6743965be93Schristos }
6753965be93Schristos }
6763965be93Schristos
6773965be93Schristos /* and then get rid of the list itself */
6783965be93Schristos if (lc->list != NULL) {
6793965be93Schristos dfree(lc->list, MDL);
6803965be93Schristos lc->list = NULL;
6813965be93Schristos }
6823965be93Schristos
6833965be93Schristos lc->total = 0;
6843965be93Schristos lc->nelem = 0;
6853965be93Schristos }
6863965be93Schristos
6873965be93Schristos /*!
6883965be93Schristos *
6893965be93Schristos * \brief Set the growth value. This is the number of elements to
6903965be93Schristos * add to the array whenever it needs to grow.
6913965be93Schristos *
6923965be93Schristos * \param lc the lease chain to set up
6933965be93Schristos * \param growth the growth value to use
6943965be93Schristos */
6953965be93Schristos void
lc_init_growth(struct leasechain * lc,size_t growth)6963965be93Schristos lc_init_growth(struct leasechain *lc, size_t growth) {
6973965be93Schristos lc->growth = growth;
6983965be93Schristos }
6993965be93Schristos
7003965be93Schristos #endif /* #if defined (BINARY_LEASES) */
701