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 */ 91int 92lc_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 */ 109struct lease * 110lc_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 */ 132struct lease * 133lc_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 */ 158size_t 159lc_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 207size_t 208lc_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 */ 303void 304lc_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 */ 347void 348lc_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 */ 399void 400lc_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 */ 451void 452lc_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 */ 501void 502lc_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 */ 560void 561lc_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 */ 591void 592lc_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 */ 630void 631lc_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 */ 663void 664lc_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 */ 695void 696lc_init_growth(struct leasechain *lc, size_t growth) { 697 lc->growth = growth; 698} 699 700#endif /* #if defined (BINARY_LEASES) */ 701