]>
git.ipfire.org Git - thirdparty/dhcp.git/blob - server/leasechain.c
3 Additional support for in-memory database support */
6 * Copyright (c) 2015-2017 by Internet Systems Consortium, Inc. ("ISC")
8 * This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
12 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
18 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 * Internet Systems Consortium, Inc.
22 * Redwood City, CA 94063
24 * https://www.isc.org/
28 /*! \file server\leasechaing.c
30 * \page leasechain structures overview
32 * A brief description of the leasechain structures
34 * This file provides additional data structures for a leasecain to
35 * provide faster access to leases on the queues associated with a pool
36 * than a linear walk. Each pool has a set of queues: active, free, backup,
37 * expired and abandoned to track leases as they are handed out and returned.
38 * The original code use a simply linear list for each of those pools but
39 * this can present performance issues if the pool is large and the lists are
41 * This code adds an array on top of the list allowing us to search the list
42 * in a binary fashion instead of a linear walk.
46 * +------------+ +-------+-------+-------+-------+
47 * | lease list |--> | lease | lease | lease | lease |....
48 * | start | | ptr | ptr | ptr | ptr |
49 * | end | +-------+-------+-------+-------+
55 * | next |->| next |->NULL
56 * NULL<- | prev |<-| prev |
59 * The linked list is maintained in an ordered state. Inserting an entry is
60 * accomplished by doing a binary search on the array to find the proper place
61 * in the list and then updating the pointers in the linked list to include the
62 * new entry. The entry is added into the array by copying the remainder of
63 * the array to provide space for the new entry.
64 * Removing an entry is the reverse.
65 * The arrays for the queues will be pre-allocated but not all of them will be
66 * large enough to hold all of the leases. If additional space is required the
67 * array will be grown.
72 #if defined (BINARY_LEASES)
73 /* Default number number of lease pointers to add to the leasechain array
74 * everytime it grows beyond the current size
76 #define LC_GROWTH_DELTA 256
80 * \brief Check if leasechain isn't empty
82 * \param lc The leasechain to check
84 * \return 1 if leasechain isn't empty
87 lc_not_empty( struct leasechain
*lc
) {
88 #if defined (DEBUG_BINARY_LEASES)
89 log_debug("LC empty check %s:%d", MDL
);
93 return (lc
->nelem
> 0 ? 1 : 0);
98 * \brief Get the first lease from a leasechain
100 * \param lc The leasechain to check
102 * \return A pointer to the first lease from a lease chain, or NULL if none found
105 lc_get_first_lease(struct leasechain
*lc
) {
106 #if defined (DEBUG_BINARY_LEASES)
107 log_debug("LC Get first %s:%d", MDL
);
109 INSIST(lc
->total
>= lc
->nelem
);
113 return (lc
->list
)[0];
120 * \brief Get the next lease from the chain, based on the lease passed in.
122 * \param lc The leasechain to check
123 * \param lp The lease to start from
125 * \return The next lease in the ordered list after lp
128 lc_get_next(struct leasechain
*lc
, struct lease
*lp
) {
129 #if defined (DEBUG_BINARY_LEASES)
130 log_debug("LC Get next %s:%d", MDL
);
140 * \brief Find the best position for inserting a lease
142 * Given a potential range of the array to insert the lease into this routine
143 * will recursively examine the range to find the proper place in which to
146 * \param lc The leasechain to add the lease to
147 * \param lp The lease to insert
148 * \param min The minium index of the potential range for insertion
149 * \param max The maximum index of the potential range for insertion
151 * \return The index of the array entry to insert the lease
154 lc_binary_search_insert_point(struct leasechain
*lc
,
156 size_t min
, size_t max
)
158 size_t mid_index
= ((max
- min
)/2) + min
;
160 if ((lc
->list
[mid_index
]->sort_time
> lp
->sort_time
) ||
161 ((lc
->list
[mid_index
]->sort_time
== lp
->sort_time
) &&
162 (lc
->list
[mid_index
]->sort_tiebreaker
> lp
->sort_tiebreaker
))) {
163 if (mid_index
== min
) {
164 /* insert in the min position, as sort_time is larger */
167 /* try again with lower half of list */
168 return (lc_binary_search_insert_point(lc
, lp
,
169 min
, mid_index
- 1));
170 } else if ((lc
->list
[mid_index
]->sort_time
< lp
->sort_time
) ||
171 ((lc
->list
[mid_index
]->sort_time
== lp
->sort_time
) &&
172 (lc
->list
[mid_index
]->sort_tiebreaker
< lp
->sort_tiebreaker
))) {
173 if (mid_index
== max
) {
174 /* insert in mid_index + 1 as sort_time is smaller */
175 return (mid_index
+1);
177 /* try again with upper half of list */
178 return (lc_binary_search_insert_point(lc
, lp
,
179 mid_index
+ 1, max
));
182 /* sort_time and sort_tiebreaker match, so insert in this position */
188 * \brief Find an exact match for a lease
190 * Given a potential range of the array to search this routine
191 * will recursively examine the range to find the proper lease
193 * \param lc The leasechain to check
194 * \param lp The lease to find
195 * \param min The minium index of the search range
196 * \param max The maximum index of the search range
198 * \return The index of the array entry for the lease, SIZE_MAX if the lease
203 lc_binary_search_lease(struct leasechain
*lc
,
205 size_t min
, size_t max
)
211 /* lease not found */
215 mid_index
= ((max
- min
)/2) + min
;
217 if ((lc
->list
[mid_index
]->sort_time
> lp
->sort_time
) ||
218 ((lc
->list
[mid_index
]->sort_time
== lp
->sort_time
) &&
219 (lc
->list
[mid_index
]->sort_tiebreaker
> lp
->sort_tiebreaker
))) {
220 if (mid_index
== min
) {
221 /* lease not found */
224 /* try the lower half of the list */
225 return (lc_binary_search_lease(lc
, lp
, min
, mid_index
- 1));
226 } else if ((lc
->list
[mid_index
]->sort_time
< lp
->sort_time
) ||
227 ((lc
->list
[mid_index
]->sort_time
== lp
->sort_time
) &&
228 (lc
->list
[mid_index
]->sort_tiebreaker
< lp
->sort_tiebreaker
))) {
229 /* try the upper half of the list */
230 return (lc_binary_search_lease(lc
, lp
, mid_index
+ 1, max
));
234 * As sort_time/sort_tiebreaker may not be unique in the list, once we
235 * find a match, we need to look before and after from this position
236 * for all matching sort_time/sort_tiebreaker until we find the exact
237 * lease or until no matching lease is found
239 if (lp
== lc
->list
[mid_index
]) {
243 /* Check out entries below the mid_index */
244 if (mid_index
> min
) {
245 /* We will break out of the loop if we either go past the
246 * canddiates or hit the end of the range when i == min. As
247 * i is unsigned we can't check it in the for loop itself.
249 for (i
= mid_index
- 1; ; i
--) {
250 if (lp
== lc
->list
[i
]) {
254 /* Are we done with this range? */
256 ((lc
->list
[i
]->sort_time
!= lp
->sort_time
) ||
257 ((lc
->list
[i
]->sort_time
== lp
->sort_time
) &&
258 (lc
->list
[i
]->sort_tiebreaker
!= lp
->sort_tiebreaker
)))) {
264 /* Check out entries above the mid_index */
265 if (mid_index
< max
) {
266 /* We will break out of the loop if we either go past the
267 * canddiates or hit the end of the range when i == max.
269 for (i
= mid_index
+ 1; i
<= max
; i
++) {
270 if (lp
== lc
->list
[i
]) {
274 if ((lc
->list
[i
]->sort_time
!= lp
->sort_time
) ||
275 ((lc
->list
[i
]->sort_time
== lp
->sort_time
) &&
276 (lc
->list
[i
]->sort_tiebreaker
!= lp
->sort_tiebreaker
))) {
282 /* Lease not found */
288 * \brief Increase the size of the array for the lease chain
290 * \param lc The leasechain to expand
292 * If we are unable to allocate memory we log a fatal error. There's
293 * not much else to do as we can't figure out where to put the lease.
295 * If we can allocate memory we copy the old lease chain to the new
296 * lease chain and free the old.
299 lc_grow_chain(struct leasechain
*lc
) {
300 #if defined (DEBUG_BINARY_LEASES)
301 log_debug("LC grow lease chain max was %zu, %s:%d", lc
->total
, MDL
);
308 temp_size
= lc
->total
+ LC_GROWTH_DELTA
;
310 temp_size
= lc
->total
+ lc
->growth
;
312 /* try to allocate the memory */
313 p
= dmalloc(sizeof(struct lease
*) * temp_size
, MDL
);
315 log_fatal("LC grow, unable to allocated memory %s:%d", MDL
);
318 /* Success, copy the lease chain and install the new one */
319 if (lc
->list
!= NULL
) {
320 memcpy(p
, lc
->list
, sizeof(struct lease
*) * lc
->nelem
);
321 dfree(lc
->list
, MDL
);
323 lc
->list
= (struct lease
**) p
;
324 lc
->total
= temp_size
;
332 * \brief Link a lease to a lease chain position
334 * This function may increase the size of the lease chain if necessary and will
335 * probably need to move entries in the lease chain around.
337 * \param lc The leasechain to update
338 * \param lp The lease to insert
339 * \param n The position in which to insert the lease
343 lc_link_lcp(struct leasechain
*lc
, struct lease
*lp
, size_t n
) {
344 #if defined (DEBUG_BINARY_LEASES)
345 log_debug("LC link lcp %s:%d", MDL
);
350 if (lc
->nelem
== lc
->total
) {
354 #if defined (DEBUG_BINARY_LEASES)
355 log_debug("LC Link lcp position %zu, elem %zu, %s:%d",
359 /* create room for the new pointer */
361 #if defined (DEBUG_BINARY_LEASES)
362 log_debug("LC link lcp moving position %zu, moving %zu. %s:%d",
363 n
, (lc
->nelem
-n
), MDL
);
365 memmove(lc
->list
+ n
+ 1, lc
->list
+ n
,
366 sizeof(struct lease
*) * (lc
->nelem
-n
));
369 /* clean any stale pointer info from this position before calling
370 * lease_reference as it won't work if pointer is not NULL
373 lease_reference(&(lc
->list
[n
]), lp
, MDL
);
384 * \brief Insert the lease at the specified position in both the lease chain
385 * and the linked list
387 * This function may increase the size of the lease chain if necessary and will
388 * probably need to move entries in the lease chain around.
389 * \param lc The leasechain to update
390 * \param lp The lease to insert
391 * \param n The position in which to insert the lease
395 lc_add_lease_pos(struct leasechain
*lc
, struct lease
*lp
, size_t pos
) {
396 #if defined (DEBUG_BINARY_LEASES)
397 log_debug("LC Add lease position %zu, %s:%d", pos
, MDL
);
401 lc_link_lcp(lc
, lp
, pos
);
404 /* this shoudln't be necessary, if we still have pointers on
405 * the lease being inserted things are broken
408 lease_dereference(&lp
->prev
, MDL
);
411 lease_dereference(&lp
->next
, MDL
);
415 /* not the first element? */
417 if (lc
->list
[pos
-1]->next
) {
418 lease_dereference(&(lc
->list
[pos
-1]->next
), MDL
);
420 lease_reference(&(lc
->list
[pos
-1]->next
), lp
, MDL
);
421 lease_reference(&lp
->prev
, lc
->list
[pos
-1], MDL
);
424 /* not the last element? we've already bumped nelem when linking
425 * into the lease chain so nelem should never be zero here */
426 if (pos
< (lc
->nelem
-1)) {
427 if (lc
->list
[pos
+1]->prev
) {
428 lease_dereference(&(lc
->list
[pos
+1]->prev
), MDL
);
430 lease_reference(&(lc
->list
[pos
+1]->prev
), lp
, MDL
);
431 lease_reference(&lp
->next
, lc
->list
[pos
+1], MDL
);
440 * \brief Debug only code, check the lease to verify it is sorted
442 * \param lc The leasechain to verify
444 * Calls log_fatal if the leasechain is not properly sorted
447 lc_check_lc_sort_order(struct leasechain
*lc
) {
450 long int tiebreak
= 0;
452 log_debug("LC check sort %s:%d", MDL
);
453 for (i
= 0; i
< lc
->nelem
; i
++ ) {
454 if ((lc
->list
[i
]->sort_time
< t
) ||
455 ((lc
->list
[i
]->sort_time
== t
) &&
456 (lc
->list
[i
]->tiebreaker
< tiebreaker
))) {
458 print_lease(lc
->list
[i
-1]);
460 print_lease(lc
->list
[i
]);
461 if (i
< lc
->nelem
- 1) {
462 print_lease(lc
->list
[i
+1]);
464 log_fatal("lc[%p] not sorted properly", lc
);
467 t
= lc
->list
[i
]->sort_time
;
468 tiebreak
= lc
->list
[i
]->sort_tiebreaker
;
475 * \brief Add a lease into the sorted lease and lease chain
476 * The sort_time is set by the caller while the sort_tiebreaker is set here
477 * The value doesn't much matter as long as it prvoides a way to have different
478 * values in most of the leases.
480 * When choosing a value for tiebreak we choose:
481 * 0 for the first lease in the queue
482 * 0 if the lease is going to the end of the queue with a sort_time greater
483 * than that of the current last lease
484 * previous tiebreaker + 1 if it is going to the end of the queue with a
485 * sort_time equal to that of the current last lease
486 * random if none of the above fit
488 * During startup when we can take advantage of the fact that leases may already
489 * be sorted and so check the end of the list to see if we can simply add the
492 * \param lc The leasechain in which to insert the lease
493 * \param lp The lease to insert
497 lc_add_sorted_lease(struct leasechain
*lc
, struct lease
*lp
) {
500 #if defined (DEBUG_BINARY_LEASES)
501 log_debug("LC add sorted %s:%d", MDL
);
505 if (lc
->nelem
== 0) {
506 /* The first lease start with a tiebreak of 0 and add it at
507 * the first position */
508 lp
->sort_tiebreaker
= 0;
510 lc_add_lease_pos(lc
, lp
, 0);
511 /* log_debug("LC add sorted done, %s:%d", MDL); */
516 if (lp
->sort_time
> lc
->list
[lc
->nelem
-1]->sort_time
) {
517 /* Adding to end of queue, with a different sort time */
518 lp
->sort_tiebreaker
= 0;
520 } else if (lp
->sort_time
== lc
->list
[lc
->nelem
-1]->sort_time
) {
521 /* Adding to end of queue, with the same sort time */
522 if (lc
->list
[lc
->nelem
-1]->sort_tiebreaker
< LONG_MAX
)
523 lp
->sort_tiebreaker
=
524 lc
->list
[lc
->nelem
-1]->sort_tiebreaker
+1;
526 lp
->sort_tiebreaker
= LONG_MAX
;
529 /* Adding somewhere in the queue, just pick a random value */
530 lp
->sort_tiebreaker
= random();
531 pos
= lc_binary_search_insert_point(lc
, lp
, 0, lc
->nelem
- 1);
534 /* Finally add it to the queue */
535 lc_add_lease_pos(lc
, lp
, pos
);
537 #if defined (DEBUG_BINARY_LEASES)
538 log_debug("LC add sorted complete position %zu, elements %zu, %s:%d",
539 pos
, lc
->nelem
, MDL
);
543 lc_check_lc_sort_order(lc
);
549 * \brief Remove the Nth pointer from a leasechain structure and update counters.
550 * The pointers in the array will be moved to fill in the hole if necessary.
552 * \param lc The lease chain to update
553 * \param n the entry to remove from the lease chain
556 lc_unlink_lcp(struct leasechain
*lc
, size_t n
) {
557 #if defined (DEBUG_BINARY_LEASES)
558 log_debug("LC unlink lcp %s:%d", MDL
);
560 /* element index to remove must be less than the number of elements present */
561 INSIST(n
< lc
->nelem
);
564 /* Clear the pointer from the lease back to the LC */
565 lc
->list
[n
]->lc
= NULL
;
567 /* Clear the pointer from the LC to the lease */
568 lease_dereference(&(lc
->list
[n
]), MDL
);
570 /* memove unless we are removing the last element */
571 if ((lc
->nelem
-1) > n
) {
572 memmove(lc
->list
+ n
, lc
->list
+ n
+ 1,
573 sizeof(struct lease
*) * (lc
->nelem
-1-n
));
580 * \brief Remove a lease from a specific position. This will first unlink
581 * the lease from the lease chain and then update the linked list.
583 * \param lc The lease chain to update
584 * \param pos the entry to remove from the lease chain
587 lc_unlink_lease_pos(struct leasechain
*lc
, size_t pos
)
589 #if defined (DEBUG_BINARY_LEASES)
593 struct lease
*lp
= NULL
;
594 lease_reference(&lp
, lc
->list
[pos
], MDL
);
596 /* unlink from lease chain list */
597 lc_unlink_lcp(lc
, pos
);
599 /* unlink from the linked list */
601 lease_dereference(&lp
->next
->prev
, MDL
);
603 lease_reference(&lp
->next
->prev
, lp
->prev
, MDL
);
606 lease_dereference(&lp
->prev
->next
, MDL
);
608 lease_reference(&lp
->prev
->next
, lp
->next
, MDL
);
609 lease_dereference(&lp
->prev
, MDL
);
612 lease_dereference(&lp
->next
, MDL
);
614 lease_dereference(&lp
, MDL
);
619 * \brief Find a lease in the lease chain and then remove it
620 * If we can't find the lease on the given lease chain it's a fatal error.
622 * \param lc The lease chain to update
623 * \param lp The lease to remove
626 lc_unlink_lease(struct leasechain
*lc
, struct lease
*lp
) {
627 #if defined (DEBUG_BINARY_LEASES)
628 log_debug("LC unlink lease %s:%d", MDL
);
631 INSIST(lc
->list
!= NULL
);
633 INSIST(lp
->lc
!= NULL
);
634 INSIST(lp
->lc
== lc
);
637 size_t pos
= lc_binary_search_lease(lc
, lp
, 0, lc
->nelem
-1);
638 if (pos
== SIZE_MAX
) {
639 /* fatal, lease not found in leasechain */
640 log_fatal("Lease with binding state %s not on its queue.",
641 (lp
->binding_state
< 1 ||
642 lp
->binding_state
> FTS_LAST
)
644 : binding_state_names
[lp
->binding_state
- 1]);
647 lc_unlink_lease_pos(lc
, pos
);
652 * \brief Unlink all the leases in the lease chain and free the
653 * lease chain structure. The leases will be freed if and when
654 * any other references to them are cleared.
656 * \param lc the lease chain to clear
659 lc_delete_all(struct leasechain
*lc
) {
663 /* better to delete from the last one, to avoid the memmove */
664 for (i
= lc
->nelem
- 1; ; i
--) {
665 lc_unlink_lease_pos(lc
, i
);
672 /* and then get rid of the list itself */
673 if (lc
->list
!= NULL
) {
674 dfree(lc
->list
, MDL
);
684 * \brief Set the growth value. This is the number of elements to
685 * add to the array whenever it needs to grow.
687 * \param lc the lease chain to set up
688 * \param growth the growth value to use
691 lc_init_growth(struct leasechain
*lc
, size_t growth
) {
695 #endif /* #if defined (BINARY_LEASES) */