ISC DHCP  4.3.3-P1
A reference DHCPv4 and DHCPv6 implementation
leasechain.c
Go to the documentation of this file.
1 /* leasechain.c
2 
3  Additional support for in-memory database support */
4 
5 /*
6  * Copyright (c) 2015 by Internet Systems Consortium, Inc. ("ISC")
7  *
8  * Permission to use, copy, modify, and distribute this software for any
9  * purpose with or without fee is hereby granted, provided that the above
10  * copyright notice and this permission notice appear in all copies.
11  *
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.
19  *
20  * Internet Systems Consortium, Inc.
21  * 950 Charter Street
22  * Redwood City, CA 94063
23  * <info@isc.org>
24  * https://www.isc.org/
25  *
26  */
27 
70 #include "dhcpd.h"
71 
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
75  */
76 #define LC_GROWTH_DELTA 256
77 
86 int
87 lc_not_empty( struct leasechain *lc ) {
88 #if defined (DEBUG_BINARY_LEASES)
89  log_debug("LC empty check %s:%d", MDL);
90  INSIST(lc != NULL);
91 #endif
92 
93  return (lc->nelem > 0 ? 1 : 0);
94 }
95 
104 struct lease *
105 lc_get_first_lease(struct leasechain *lc) {
106 #if defined (DEBUG_BINARY_LEASES)
107  log_debug("LC Get first %s:%d", MDL);
108  INSIST(lc != NULL);
109  INSIST(lc->total >= lc->nelem);
110 #endif
111 
112  if (lc->nelem > 0) {
113  return (lc->list)[0];
114  }
115  return (NULL);
116 }
117 
127 struct lease *
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);
131  INSIST(lc != NULL);
132  INSIST(lp != NULL);
133 #endif
134 
135  return lp->next;
136 }
137 
153 size_t
154 lc_binary_search_insert_point(struct leasechain *lc,
155  struct lease *lp,
156  size_t min, size_t max)
157 {
158  size_t mid_index = ((max - min)/2) + min;
159 
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 */
165  return (min);
166  }
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);
176  }
177  /* try again with upper half of list */
178  return (lc_binary_search_insert_point(lc, lp,
179  mid_index + 1, max));
180  }
181 
182  /* sort_time and sort_tiebreaker match, so insert in this position */
183  return (mid_index);
184 }
185 
202 size_t
203 lc_binary_search_lease(struct leasechain *lc,
204  struct lease *lp,
205  size_t min, size_t max)
206 {
207  size_t mid_index;
208  size_t i;
209 
210  if (max < min) {
211  /* lease not found */
212  return (SIZE_MAX);
213  }
214 
215  mid_index = ((max - min)/2) + min;
216 
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 */
222  return (SIZE_MAX);
223  }
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));
231  }
232 
233  /*
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
238  */
239  if (lp == lc->list[mid_index]) {
240  return (mid_index);
241  }
242 
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.
248  */
249  for (i = mid_index - 1; ; i--) {
250  if (lp == lc->list[i]) {
251  return (i);
252  }
253 
254  /* Are we done with this range? */
255  if ((i == min) ||
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)))) {
259  break;
260  }
261  }
262  }
263 
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.
268  */
269  for (i = mid_index + 1; i <= max; i++) {
270  if (lp == lc->list[i]) {
271  return (i);
272  }
273 
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))) {
277  break;
278  }
279  }
280  }
281 
282  /* Lease not found */
283  return (SIZE_MAX);
284 }
285 
298 void
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);
302 #endif
303 
304  void *p;
305  size_t temp_size;
306 
307  if (lc->growth == 0)
308  temp_size = lc->total + LC_GROWTH_DELTA;
309  else
310  temp_size = lc->total + lc->growth;
311 
312  /* try to allocate the memory */
313  p = dmalloc(sizeof(struct lease *) * temp_size, MDL);
314  if (p == NULL) {
315  log_fatal("LC grow, unable to allocated memory %s:%d", MDL);
316  }
317 
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);
322  }
323  lc->list = (struct lease **) p;
324  lc->total = temp_size;
325 
326  return;
327 }
328 
329 
342 void
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);
346  INSIST (lc != NULL);
347  INSIST (lp != NULL);
348 #endif
349 
350  if (lc->nelem == lc->total) {
351  lc_grow_chain(lc);
352  }
353 
354 #if defined (DEBUG_BINARY_LEASES)
355  log_debug("LC Link lcp position %zu, elem %zu, %s:%d",
356  n, lc->nelem, MDL);
357 #endif
358 
359  /* create room for the new pointer */
360  if (n < lc->nelem) {
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);
364 #endif
365  memmove(lc->list + n + 1, lc->list + n,
366  sizeof(struct lease *) * (lc->nelem-n));
367  }
368 
369  /* clean any stale pointer info from this position before calling
370  * lease_reference as it won't work if pointer is not NULL
371  */
372  lc->list[n] = NULL;
373  lease_reference(&(lc->list[n]), lp, MDL);
374 
375  lc->nelem++;
376 
377  lp->lc = lc;
378 
379  return;
380 }
381 
394 void
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);
398  INSIST (lc != NULL);
399  INSIST (lp != NULL);
400 #endif
401  lc_link_lcp(lc, lp, pos);
402 
403 #if 0
404  /* this shoudln't be necessary, if we still have pointers on
405  * the lease being inserted things are broken
406  */
407  if (lp->prev) {
408  lease_dereference(&lp->prev, MDL);
409  }
410  if (lp->next) {
411  lease_dereference(&lp->next, MDL);
412  }
413 #endif
414 
415  /* not the first element? */
416  if (pos > 0) {
417  if (lc->list[pos-1]->next) {
418  lease_dereference(&(lc->list[pos-1]->next), MDL);
419  }
420  lease_reference(&(lc->list[pos-1]->next), lp, MDL);
421  lease_reference(&lp->prev, lc->list[pos-1], MDL );
422  }
423 
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);
429  }
430  lease_reference(&(lc->list[pos+1]->prev), lp, MDL);
431  lease_reference(&lp->next, lc->list[pos+1], MDL);
432  }
433 
434  return;
435 }
436 
437 #ifdef POINTER_DEBUG
438 
446 void
447 lc_check_lc_sort_order(struct leasechain *lc) {
448  size_t i;
449  TIME t = 0;
450  long int tiebreak = 0;
451 
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))) {
457  if (i > 0) {
458  print_lease(lc->list[i-1]);
459  }
460  print_lease(lc->list[i]);
461  if (i < lc->nelem - 1) {
462  print_lease(lc->list[i+1]);
463  }
464  log_fatal("lc[%p] not sorted properly", lc);
465  }
466 
467  t = lc->list[i]->sort_time;
468  tiebreak = lc->list[i]->sort_tiebreaker;
469  }
470 }
471 #endif
472 
496 void
497 lc_add_sorted_lease(struct leasechain *lc, struct lease *lp) {
498  size_t pos;
499 
500 #if defined (DEBUG_BINARY_LEASES)
501  log_debug("LC add sorted %s:%d", MDL);
502  INSIST (lc != NULL);
503  INSIST (lp != NULL);
504 #endif
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;
509 
510  lc_add_lease_pos(lc, lp, 0);
511  /* log_debug("LC add sorted done, %s:%d", MDL); */
512 
513  return;
514  }
515 
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;
519  pos = lc->nelem;
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;
525  else
526  lp->sort_tiebreaker = LONG_MAX;
527  pos = lc->nelem;
528  } else {
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);
532  }
533 
534  /* Finally add it to the queue */
535  lc_add_lease_pos(lc, lp, pos);
536 
537 #if defined (DEBUG_BINARY_LEASES)
538  log_debug("LC add sorted complete position %zu, elements %zu, %s:%d",
539  pos, lc->nelem, MDL);
540 #endif
541 
542 #ifdef POINTER_DEBUG
543  lc_check_lc_sort_order(lc);
544 #endif
545 }
546 
555 void
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);
559 
560  /* element index to remove must be less than the number of elements present */
561  INSIST(n < lc->nelem);
562 #endif
563 
564  /* Clear the pointer from the lease back to the LC */
565  lc->list[n]->lc = NULL;
566 
567  /* Clear the pointer from the LC to the lease */
568  lease_dereference(&(lc->list[n]), MDL);
569 
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));
574  }
575  lc->nelem--;
576 }
577 
586 void
587 lc_unlink_lease_pos(struct leasechain *lc, size_t pos)
588 {
589 #if defined (DEBUG_BINARY_LEASES)
590  INSIST(lc != NULL);
591 #endif
592 
593  struct lease *lp = NULL;
594  lease_reference(&lp, lc->list[pos], MDL);
595 
596  /* unlink from lease chain list */
597  lc_unlink_lcp(lc, pos);
598 
599  /* unlink from the linked list */
600  if (lp->next) {
601  lease_dereference(&lp->next->prev, MDL);
602  if (lp->prev)
603  lease_reference(&lp->next->prev, lp->prev, MDL);
604  }
605  if (lp->prev) {
606  lease_dereference(&lp->prev->next, MDL);
607  if (lp->next)
608  lease_reference(&lp->prev->next, lp->next, MDL);
609  lease_dereference(&lp->prev, MDL);
610  }
611  if (lp->next) {
612  lease_dereference(&lp->next, MDL);
613  }
614  lease_dereference(&lp, MDL);
615 }
616 
625 void
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);
629 
630  INSIST(lc != NULL);
631  INSIST(lc->list != NULL);
632  INSIST(lp != NULL );
633  INSIST(lp->lc != NULL );
634  INSIST(lp->lc == lc );
635 #endif
636 
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)
643  ? "unknown"
645  }
646 
647  lc_unlink_lease_pos(lc, pos);
648 }
649 
650 #if defined (DEBUG_MEMORY_LEAKAGE) || \
651  defined (DEBUG_MEMORY_LEAKAGE_ON_EXIT)
652 
660 void
661 lc_delete_all(struct leasechain *lc) {
662  size_t i;
663 
664  if (lc->nelem > 0) {
665  /* better to delete from the last one, to avoid the memmove */
666  for (i = lc->nelem - 1; ; i--) {
667  lc_unlink_lease_pos(lc, i);
668  if (i == 0) {
669  break;
670  }
671  }
672  }
673 
674  /* and then get rid of the list itself */
675  dfree(lc->list, MDL);
676  lc->list = NULL;
677  lc->total = 0;
678  lc->nelem = 0;
679 }
680 #endif
681 
690 void
691 lc_init_growth(struct leasechain *lc, size_t growth) {
692  lc->growth = growth;
693 }
694 
695 #endif /* #if defined (BINARY_LEASES) */
#define FTS_LAST
Definition: dhcpd.h:537
struct leasechain * lc
Definition: dhcpd.h:555
Definition: dhcpd.h:550
void * dmalloc(unsigned, const char *, int)
Definition: alloc.c:56
int lc_not_empty(struct leasechain *lc)
#define MDL
Definition: omapip.h:568
int int int log_debug(const char *,...) __attribute__((__format__(__printf__
size_t total
Definition: dhcpd.h:976
size_t growth
Definition: dhcpd.h:979
void log_fatal(const char *,...) __attribute__((__format__(__printf__
TIME sort_time
Definition: dhcpd.h:560
binding_state_t binding_state
Definition: dhcpd.h:613
void dfree(void *, const char *, int)
Definition: alloc.c:131
long int sort_tiebreaker
Definition: dhcpd.h:562
struct lease * lc_get_first_lease(struct leasechain *lc)
struct lease * prev
Definition: dhcpd.h:554
struct lease * lc_get_next(struct leasechain *lc, struct lease *lp)
size_t nelem
Definition: dhcpd.h:978
time_t TIME
Definition: dhcpd.h:85
void lc_add_sorted_lease(struct leasechain *lc, struct lease *lp)
void lc_unlink_lease(struct leasechain *lc, struct lease *lp)
struct lease * next
Definition: dhcpd.h:552
void lc_init_growth(struct leasechain *lc, size_t growth)
const char * binding_state_names[]
Definition: stables.c:161
struct lease ** list
Definition: dhcpd.h:975