1 /* $NetBSD: leasechain.c,v 1.3 2022/04/03 01:10:59 christos Exp $ */
2
3 /* leasechain.c
4
5 Additional support for in-memory database support */
6
7 /*
8 * Copyright (C) 2015-2022 Internet Systems Consortium, Inc. ("ISC")
9 *
10 * This Source Code Form is subject to the terms of the Mozilla Public
11 * License, v. 2.0. If a copy of the MPL was not distributed with this
12 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
20 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 *
22 * Internet Systems Consortium, Inc.
23 * PO Box 360
24 * Newmarket, NH 03857 USA
25 * <info@isc.org>
26 * https://www.isc.org/
27 *
28 */
29
30 #include <sys/cdefs.h>
31 __RCSID("$NetBSD: leasechain.c,v 1.3 2022/04/03 01:10:59 christos Exp $");
32
33 /*! \file server\leasechaing.c
34 *
35 * \page leasechain structures overview
36 *
37 * A brief description of the leasechain structures
38 *
39 * This file provides additional data structures for a leasecain to
40 * provide faster access to leases on the queues associated with a pool
41 * than a linear walk. Each pool has a set of queues: active, free, backup,
42 * expired and abandoned to track leases as they are handed out and returned.
43 * The original code use a simply linear list for each of those pools but
44 * this can present performance issues if the pool is large and the lists are
45 * long.
46 * This code adds an array on top of the list allowing us to search the list
47 * in a binary fashion instead of a linear walk.
48 *
49 * \verbatim
50 * leasechain
51 * +------------+ +-------+-------+-------+-------+
52 * | lease list |--> | lease | lease | lease | lease |....
53 * | start | | ptr | ptr | ptr | ptr |
54 * | end | +-------+-------+-------+-------+
55 * | max | | |
56 * +------------+ V V
57 * +-------+ +-------+
58 * | lease | | lease |
59 * | | | |
60 * | next |->| next |->NULL
61 * NULL<- | prev |<-| prev |
62 * +-------+ +-------+
63 *
64 * The linked list is maintained in an ordered state. Inserting an entry is
65 * accomplished by doing a binary search on the array to find the proper place
66 * in the list and then updating the pointers in the linked list to include the
67 * new entry. The entry is added into the array by copying the remainder of
68 * the array to provide space for the new entry.
69 * Removing an entry is the reverse.
70 * The arrays for the queues will be pre-allocated but not all of them will be
71 * large enough to hold all of the leases. If additional space is required the
72 * array will be grown.
73 */
74
75 #include "dhcpd.h"
76
77 #if defined (BINARY_LEASES)
78 /* Default number number of lease pointers to add to the leasechain array
79 * everytime it grows beyond the current size
80 */
81 #define LC_GROWTH_DELTA 256
82
83 /*!
84 *
85 * \brief Check if leasechain isn't empty
86 *
87 * \param lc The leasechain to check
88 *
89 * \return 1 if leasechain isn't empty
90 */
91 int
lc_not_empty(struct leasechain * lc)92 lc_not_empty( struct leasechain *lc ) {
93 #if defined (DEBUG_BINARY_LEASES)
94 log_debug("LC empty check %s:%d", MDL);
95 INSIST(lc != NULL);
96 #endif
97
98 return (lc->nelem > 0 ? 1 : 0);
99 }
100
101 /*!
102 *
103 * \brief Get the first lease from a leasechain
104 *
105 * \param lc The leasechain to check
106 *
107 * \return A pointer to the first lease from a lease chain, or NULL if none found
108 */
109 struct lease *
lc_get_first_lease(struct leasechain * lc)110 lc_get_first_lease(struct leasechain *lc) {
111 #if defined (DEBUG_BINARY_LEASES)
112 log_debug("LC Get first %s:%d", MDL);
113 INSIST(lc != NULL);
114 INSIST(lc->total >= lc->nelem);
115 #endif
116
117 if (lc->nelem > 0) {
118 return (lc->list)[0];
119 }
120 return (NULL);
121 }
122
123 /*!
124 *
125 * \brief Get the next lease from the chain, based on the lease passed in.
126 *
127 * \param lc The leasechain to check
128 * \param lp The lease to start from
129 *
130 * \return The next lease in the ordered list after lp
131 */
132 struct lease *
lc_get_next(struct leasechain * lc,struct lease * lp)133 lc_get_next(struct leasechain *lc, struct lease *lp) {
134 #if defined (DEBUG_BINARY_LEASES)
135 log_debug("LC Get next %s:%d", MDL);
136 INSIST(lc != NULL);
137 INSIST(lp != NULL);
138 #endif
139
140 return lp->next;
141 }
142
143 /*!
144 *
145 * \brief Find the best position for inserting a lease
146 *
147 * Given a potential range of the array to insert the lease into this routine
148 * will recursively examine the range to find the proper place in which to
149 * insert the lease.
150 *
151 * \param lc The leasechain to add the lease to
152 * \param lp The lease to insert
153 * \param min The minium index of the potential range for insertion
154 * \param max The maximum index of the potential range for insertion
155 *
156 * \return The index of the array entry to insert the lease
157 */
158 size_t
lc_binary_search_insert_point(struct leasechain * lc,struct lease * lp,size_t min,size_t max)159 lc_binary_search_insert_point(struct leasechain *lc,
160 struct lease *lp,
161 size_t min, size_t max)
162 {
163 size_t mid_index = ((max - min)/2) + min;
164
165 if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
166 ((lc->list[mid_index]->sort_time == lp->sort_time) &&
167 (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
168 if (mid_index == min) {
169 /* insert in the min position, as sort_time is larger */
170 return (min);
171 }
172 /* try again with lower half of list */
173 return (lc_binary_search_insert_point(lc, lp,
174 min, mid_index - 1));
175 } else if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
176 ((lc->list[mid_index]->sort_time == lp->sort_time) &&
177 (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
178 if (mid_index == max) {
179 /* insert in mid_index + 1 as sort_time is smaller */
180 return (mid_index+1);
181 }
182 /* try again with upper half of list */
183 return (lc_binary_search_insert_point(lc, lp,
184 mid_index + 1, max));
185 }
186
187 /* sort_time and sort_tiebreaker match, so insert in this position */
188 return (mid_index);
189 }
190
191 /*!
192 *
193 * \brief Find an exact match for a lease
194 *
195 * Given a potential range of the array to search this routine
196 * will recursively examine the range to find the proper lease
197 *
198 * \param lc The leasechain to check
199 * \param lp The lease to find
200 * \param min The minium index of the search range
201 * \param max The maximum index of the search range
202 *
203 * \return The index of the array entry for the lease, SIZE_MAX if the lease
204 * wasn't found
205 */
206
207 size_t
lc_binary_search_lease(struct leasechain * lc,struct lease * lp,size_t min,size_t max)208 lc_binary_search_lease(struct leasechain *lc,
209 struct lease *lp,
210 size_t min, size_t max)
211 {
212 size_t mid_index;
213 size_t i;
214
215 if (max < min) {
216 /* lease not found */
217 return (SIZE_MAX);
218 }
219
220 mid_index = ((max - min)/2) + min;
221
222 if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
223 ((lc->list[mid_index]->sort_time == lp->sort_time) &&
224 (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
225 if (mid_index == min) {
226 /* lease not found */
227 return (SIZE_MAX);
228 }
229 /* try the lower half of the list */
230 return (lc_binary_search_lease(lc, lp, min, mid_index - 1));
231 } else if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
232 ((lc->list[mid_index]->sort_time == lp->sort_time) &&
233 (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
234 /* try the upper half of the list */
235 return (lc_binary_search_lease(lc, lp, mid_index + 1, max));
236 }
237
238 /*
239 * As sort_time/sort_tiebreaker may not be unique in the list, once we
240 * find a match, we need to look before and after from this position
241 * for all matching sort_time/sort_tiebreaker until we find the exact
242 * lease or until no matching lease is found
243 */
244 if (lp == lc->list[mid_index]) {
245 return (mid_index);
246 }
247
248 /* Check out entries below the mid_index */
249 if (mid_index > min) {
250 /* We will break out of the loop if we either go past the
251 * canddiates or hit the end of the range when i == min. As
252 * i is unsigned we can't check it in the for loop itself.
253 */
254 for (i = mid_index - 1; ; i--) {
255 if (lp == lc->list[i]) {
256 return (i);
257 }
258
259 /* Are we done with this range? */
260 if ((i == min) ||
261 ((lc->list[i]->sort_time != lp->sort_time) ||
262 ((lc->list[i]->sort_time == lp->sort_time) &&
263 (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker)))) {
264 break;
265 }
266 }
267 }
268
269 /* Check out entries above the mid_index */
270 if (mid_index < max) {
271 /* We will break out of the loop if we either go past the
272 * canddiates or hit the end of the range when i == max.
273 */
274 for (i = mid_index + 1; i <= max; i++) {
275 if (lp == lc->list[i]) {
276 return (i);
277 }
278
279 if ((lc->list[i]->sort_time != lp->sort_time) ||
280 ((lc->list[i]->sort_time == lp->sort_time) &&
281 (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker))) {
282 break;
283 }
284 }
285 }
286
287 /* Lease not found */
288 return (SIZE_MAX);
289 }
290
291 /*!
292 *
293 * \brief Increase the size of the array for the lease chain
294 *
295 * \param lc The leasechain to expand
296 *
297 * If we are unable to allocate memory we log a fatal error. There's
298 * not much else to do as we can't figure out where to put the lease.
299 *
300 * If we can allocate memory we copy the old lease chain to the new
301 * lease chain and free the old.
302 */
303 void
lc_grow_chain(struct leasechain * lc)304 lc_grow_chain(struct leasechain *lc) {
305 #if defined (DEBUG_BINARY_LEASES)
306 log_debug("LC grow lease chain max was %zu, %s:%d", lc->total, MDL);
307 #endif
308
309 void *p;
310 size_t temp_size;
311
312 if (lc->growth == 0)
313 temp_size = lc->total + LC_GROWTH_DELTA;
314 else
315 temp_size = lc->total + lc->growth;
316
317 /* try to allocate the memory */
318 p = dmalloc(sizeof(struct lease *) * temp_size, MDL);
319 if (p == NULL) {
320 log_fatal("LC grow, unable to allocated memory %s:%d", MDL);
321 }
322
323 /* Success, copy the lease chain and install the new one */
324 if (lc->list != NULL) {
325 memcpy(p, lc->list, sizeof(struct lease *) * lc->nelem);
326 dfree(lc->list, MDL);
327 }
328 lc->list = (struct lease **) p;
329 lc->total = temp_size;
330
331 return;
332 }
333
334
335 /*!
336 *
337 * \brief Link a lease to a lease chain position
338 *
339 * This function may increase the size of the lease chain if necessary and will
340 * probably need to move entries in the lease chain around.
341 *
342 * \param lc The leasechain to update
343 * \param lp The lease to insert
344 * \param n The position in which to insert the lease
345 *
346 */
347 void
lc_link_lcp(struct leasechain * lc,struct lease * lp,size_t n)348 lc_link_lcp(struct leasechain *lc, struct lease *lp, size_t n) {
349 #if defined (DEBUG_BINARY_LEASES)
350 log_debug("LC link lcp %s:%d", MDL);
351 INSIST (lc != NULL);
352 INSIST (lp != NULL);
353 #endif
354
355 if (lc->nelem == lc->total) {
356 lc_grow_chain(lc);
357 }
358
359 #if defined (DEBUG_BINARY_LEASES)
360 log_debug("LC Link lcp position %zu, elem %zu, %s:%d",
361 n, lc->nelem, MDL);
362 #endif
363
364 /* create room for the new pointer */
365 if (n < lc->nelem) {
366 #if defined (DEBUG_BINARY_LEASES)
367 log_debug("LC link lcp moving position %zu, moving %zu. %s:%d",
368 n, (lc->nelem-n), MDL);
369 #endif
370 memmove(lc->list + n + 1, lc->list + n,
371 sizeof(struct lease *) * (lc->nelem-n));
372 }
373
374 /* clean any stale pointer info from this position before calling
375 * lease_reference as it won't work if pointer is not NULL
376 */
377 lc->list[n] = NULL;
378 lease_reference(&(lc->list[n]), lp, MDL);
379
380 lc->nelem++;
381
382 lp->lc = lc;
383
384 return;
385 }
386
387 /*!
388 *
389 * \brief Insert the lease at the specified position in both the lease chain
390 * and the linked list
391 *
392 * This function may increase the size of the lease chain if necessary and will
393 * probably need to move entries in the lease chain around.
394 * \param lc The leasechain to update
395 * \param lp The lease to insert
396 * \param n The position in which to insert the lease
397 *
398 */
399 void
lc_add_lease_pos(struct leasechain * lc,struct lease * lp,size_t pos)400 lc_add_lease_pos(struct leasechain *lc, struct lease *lp, size_t pos) {
401 #if defined (DEBUG_BINARY_LEASES)
402 log_debug("LC Add lease position %zu, %s:%d", pos, MDL);
403 INSIST (lc != NULL);
404 INSIST (lp != NULL);
405 #endif
406 lc_link_lcp(lc, lp, pos);
407
408 #if 0
409 /* this shoudln't be necessary, if we still have pointers on
410 * the lease being inserted things are broken
411 */
412 if (lp->prev) {
413 lease_dereference(&lp->prev, MDL);
414 }
415 if (lp->next) {
416 lease_dereference(&lp->next, MDL);
417 }
418 #endif
419
420 /* not the first element? */
421 if (pos > 0) {
422 if (lc->list[pos-1]->next) {
423 lease_dereference(&(lc->list[pos-1]->next), MDL);
424 }
425 lease_reference(&(lc->list[pos-1]->next), lp, MDL);
426 lease_reference(&lp->prev, lc->list[pos-1], MDL );
427 }
428
429 /* not the last element? we've already bumped nelem when linking
430 * into the lease chain so nelem should never be zero here */
431 if (pos < (lc->nelem-1)) {
432 if (lc->list[pos+1]->prev) {
433 lease_dereference(&(lc->list[pos+1]->prev), MDL);
434 }
435 lease_reference(&(lc->list[pos+1]->prev), lp, MDL);
436 lease_reference(&lp->next, lc->list[pos+1], MDL);
437 }
438
439 return;
440 }
441
442 #ifdef POINTER_DEBUG
443 /*!
444 *
445 * \brief Debug only code, check the lease to verify it is sorted
446 *
447 * \param lc The leasechain to verify
448 *
449 * Calls log_fatal if the leasechain is not properly sorted
450 */
451 void
lc_check_lc_sort_order(struct leasechain * lc)452 lc_check_lc_sort_order(struct leasechain *lc) {
453 size_t i;
454 TIME t = 0;
455 long int tiebreak = 0;
456
457 log_debug("LC check sort %s:%d", MDL);
458 for (i = 0; i < lc->nelem; i++ ) {
459 if ((lc->list[i]->sort_time < t) ||
460 ((lc->list[i]->sort_time == t) &&
461 (lc->list[i]->tiebreaker < tiebreaker))) {
462 if (i > 0) {
463 print_lease(lc->list[i-1]);
464 }
465 print_lease(lc->list[i]);
466 if (i < lc->nelem - 1) {
467 print_lease(lc->list[i+1]);
468 }
469 log_fatal("lc[%p] not sorted properly", lc);
470 }
471
472 t = lc->list[i]->sort_time;
473 tiebreak = lc->list[i]->sort_tiebreaker;
474 }
475 }
476 #endif
477
478 /*!
479 *
480 * \brief Add a lease into the sorted lease and lease chain
481 * The sort_time is set by the caller while the sort_tiebreaker is set here
482 * The value doesn't much matter as long as it prvoides a way to have different
483 * values in most of the leases.
484 *
485 * When choosing a value for tiebreak we choose:
486 * 0 for the first lease in the queue
487 * 0 if the lease is going to the end of the queue with a sort_time greater
488 * than that of the current last lease
489 * previous tiebreaker + 1 if it is going to the end of the queue with a
490 * sort_time equal to that of the current last lease
491 * random if none of the above fit
492 *
493 * During startup when we can take advantage of the fact that leases may already
494 * be sorted and so check the end of the list to see if we can simply add the
495 * lease to the end.
496 *
497 * \param lc The leasechain in which to insert the lease
498 * \param lp The lease to insert
499 *
500 */
501 void
lc_add_sorted_lease(struct leasechain * lc,struct lease * lp)502 lc_add_sorted_lease(struct leasechain *lc, struct lease *lp) {
503 size_t pos;
504
505 #if defined (DEBUG_BINARY_LEASES)
506 log_debug("LC add sorted %s:%d", MDL);
507 INSIST (lc != NULL);
508 INSIST (lp != NULL);
509 #endif
510 if (lc->nelem == 0) {
511 /* The first lease start with a tiebreak of 0 and add it at
512 * the first position */
513 lp->sort_tiebreaker = 0;
514
515 lc_add_lease_pos(lc, lp, 0);
516 /* log_debug("LC add sorted done, %s:%d", MDL); */
517
518 return;
519 }
520
521 if (lp->sort_time > lc->list[lc->nelem-1]->sort_time) {
522 /* Adding to end of queue, with a different sort time */
523 lp->sort_tiebreaker = 0;
524 pos = lc->nelem;
525 } else if (lp->sort_time == lc->list[lc->nelem-1]->sort_time) {
526 /* Adding to end of queue, with the same sort time */
527 if (lc->list[lc->nelem-1]->sort_tiebreaker < LONG_MAX)
528 lp->sort_tiebreaker =
529 lc->list[lc->nelem-1]->sort_tiebreaker+1;
530 else
531 lp->sort_tiebreaker = LONG_MAX;
532 pos = lc->nelem;
533 } else {
534 /* Adding somewhere in the queue, just pick a random value */
535 lp->sort_tiebreaker = random();
536 pos = lc_binary_search_insert_point(lc, lp, 0, lc->nelem - 1);
537 }
538
539 /* Finally add it to the queue */
540 lc_add_lease_pos(lc, lp, pos);
541
542 #if defined (DEBUG_BINARY_LEASES)
543 log_debug("LC add sorted complete position %zu, elements %zu, %s:%d",
544 pos, lc->nelem, MDL);
545 #endif
546
547 #ifdef POINTER_DEBUG
548 lc_check_lc_sort_order(lc);
549 #endif
550 }
551
552 /*!
553 *
554 * \brief Remove the Nth pointer from a leasechain structure and update counters.
555 * The pointers in the array will be moved to fill in the hole if necessary.
556 *
557 * \param lc The lease chain to update
558 * \param n the entry to remove from the lease chain
559 */
560 void
lc_unlink_lcp(struct leasechain * lc,size_t n)561 lc_unlink_lcp(struct leasechain *lc, size_t n) {
562 #if defined (DEBUG_BINARY_LEASES)
563 log_debug("LC unlink lcp %s:%d", MDL);
564
565 /* element index to remove must be less than the number of elements present */
566 INSIST(n < lc->nelem);
567 #endif
568
569 /* Clear the pointer from the lease back to the LC */
570 lc->list[n]->lc = NULL;
571
572 /* Clear the pointer from the LC to the lease */
573 lease_dereference(&(lc->list[n]), MDL);
574
575 /* memove unless we are removing the last element */
576 if ((lc->nelem-1) > n) {
577 memmove(lc->list + n, lc->list + n + 1,
578 sizeof(struct lease *) * (lc->nelem-1-n));
579 }
580 lc->nelem--;
581 }
582
583 /*!
584 *
585 * \brief Remove a lease from a specific position. This will first unlink
586 * the lease from the lease chain and then update the linked list.
587 *
588 * \param lc The lease chain to update
589 * \param pos the entry to remove from the lease chain
590 */
591 void
lc_unlink_lease_pos(struct leasechain * lc,size_t pos)592 lc_unlink_lease_pos(struct leasechain *lc, size_t pos)
593 {
594 #if defined (DEBUG_BINARY_LEASES)
595 INSIST(lc != NULL);
596 #endif
597
598 struct lease *lp = NULL;
599 lease_reference(&lp, lc->list[pos], MDL);
600
601 /* unlink from lease chain list */
602 lc_unlink_lcp(lc, pos);
603
604 /* unlink from the linked list */
605 if (lp->next) {
606 lease_dereference(&lp->next->prev, MDL);
607 if (lp->prev)
608 lease_reference(&lp->next->prev, lp->prev, MDL);
609 }
610 if (lp->prev) {
611 lease_dereference(&lp->prev->next, MDL);
612 if (lp->next)
613 lease_reference(&lp->prev->next, lp->next, MDL);
614 lease_dereference(&lp->prev, MDL);
615 }
616 if (lp->next) {
617 lease_dereference(&lp->next, MDL);
618 }
619 lease_dereference(&lp, MDL);
620 }
621
622 /*!
623 *
624 * \brief Find a lease in the lease chain and then remove it
625 * If we can't find the lease on the given lease chain it's a fatal error.
626 *
627 * \param lc The lease chain to update
628 * \param lp The lease to remove
629 */
630 void
lc_unlink_lease(struct leasechain * lc,struct lease * lp)631 lc_unlink_lease(struct leasechain *lc, struct lease *lp) {
632 #if defined (DEBUG_BINARY_LEASES)
633 log_debug("LC unlink lease %s:%d", MDL);
634
635 INSIST(lc != NULL);
636 INSIST(lc->list != NULL);
637 INSIST(lp != NULL );
638 INSIST(lp->lc != NULL );
639 INSIST(lp->lc == lc );
640 #endif
641
642 size_t pos = lc_binary_search_lease(lc, lp, 0, lc->nelem-1);
643 if (pos == SIZE_MAX) {
644 /* fatal, lease not found in leasechain */
645 log_fatal("Lease with binding state %s not on its queue.",
646 (lp->binding_state < 1 ||
647 lp->binding_state > FTS_LAST)
648 ? "unknown"
649 : binding_state_names[lp->binding_state - 1]);
650 }
651
652 lc_unlink_lease_pos(lc, pos);
653 }
654
655 /*!
656 *
657 * \brief Unlink all the leases in the lease chain and free the
658 * lease chain structure. The leases will be freed if and when
659 * any other references to them are cleared.
660 *
661 * \param lc the lease chain to clear
662 */
663 void
lc_delete_all(struct leasechain * lc)664 lc_delete_all(struct leasechain *lc) {
665 size_t i;
666
667 if (lc->nelem > 0) {
668 /* better to delete from the last one, to avoid the memmove */
669 for (i = lc->nelem - 1; ; i--) {
670 lc_unlink_lease_pos(lc, i);
671 if (i == 0) {
672 break;
673 }
674 }
675 }
676
677 /* and then get rid of the list itself */
678 if (lc->list != NULL) {
679 dfree(lc->list, MDL);
680 lc->list = NULL;
681 }
682
683 lc->total = 0;
684 lc->nelem = 0;
685 }
686
687 /*!
688 *
689 * \brief Set the growth value. This is the number of elements to
690 * add to the array whenever it needs to grow.
691 *
692 * \param lc the lease chain to set up
693 * \param growth the growth value to use
694 */
695 void
lc_init_growth(struct leasechain * lc,size_t growth)696 lc_init_growth(struct leasechain *lc, size_t growth) {
697 lc->growth = growth;
698 }
699
700 #endif /* #if defined (BINARY_LEASES) */
701