]>
Commit | Line | Data |
---|---|---|
3933e2aa SR |
1 | /* leasechain.c |
2 | ||
3 | Additional support for in-memory database support */ | |
4 | ||
5 | /* | |
75ab52e1 | 6 | * Copyright (c) 2015-2016 by Internet Systems Consortium, Inc. ("ISC") |
3933e2aa SR |
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 | ||
28 | /*! \file server\leasechaing.c | |
29 | * | |
30 | * \page leasechain structures overview | |
31 | * | |
32 | * A brief description of the leasechain structures | |
33 | * | |
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 | |
40 | * long. | |
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. | |
43 | * | |
44 | * \verbatim | |
45 | * leasechain | |
46 | * +------------+ +-------+-------+-------+-------+ | |
47 | * | lease list |--> | lease | lease | lease | lease |.... | |
48 | * | start | | ptr | ptr | ptr | ptr | | |
49 | * | end | +-------+-------+-------+-------+ | |
50 | * | max | | | | |
51 | * +------------+ V V | |
52 | * +-------+ +-------+ | |
53 | * | lease | | lease | | |
54 | * | | | | | |
55 | * | next |->| next |->NULL | |
56 | * NULL<- | prev |<-| prev | | |
57 | * +-------+ +-------+ | |
58 | * | |
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. | |
68 | */ | |
69 | ||
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 | ||
78 | /*! | |
79 | * | |
80 | * \brief Check if leasechain isn't empty | |
81 | * | |
82 | * \param lc The leasechain to check | |
83 | * | |
84 | * \return 1 if leasechain isn't empty | |
85 | */ | |
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 | ||
96 | /*! | |
97 | * | |
98 | * \brief Get the first lease from a leasechain | |
99 | * | |
100 | * \param lc The leasechain to check | |
101 | * | |
102 | * \return A pointer to the first lease from a lease chain, or NULL if none found | |
103 | */ | |
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 | ||
118 | /*! | |
119 | * | |
120 | * \brief Get the next lease from the chain, based on the lease passed in. | |
121 | * | |
122 | * \param lc The leasechain to check | |
123 | * \param lp The lease to start from | |
124 | * | |
125 | * \return The next lease in the ordered list after lp | |
126 | */ | |
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 | ||
138 | /*! | |
139 | * | |
140 | * \brief Find the best position for inserting a lease | |
141 | * | |
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 | |
144 | * insert the lease. | |
145 | * | |
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 | |
150 | * | |
151 | * \return The index of the array entry to insert the lease | |
152 | */ | |
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 | ||
186 | /*! | |
187 | * | |
188 | * \brief Find an exact match for a lease | |
189 | * | |
190 | * Given a potential range of the array to search this routine | |
191 | * will recursively examine the range to find the proper lease | |
192 | * | |
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 | |
197 | * | |
198 | * \return The index of the array entry for the lease, SIZE_MAX if the lease | |
199 | * wasn't found | |
200 | */ | |
201 | ||
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 | ||
286 | /*! | |
287 | * | |
288 | * \brief Increase the size of the array for the lease chain | |
289 | * | |
290 | * \param lc The leasechain to expand | |
291 | * | |
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. | |
294 | * | |
295 | * If we can allocate memory we copy the old lease chain to the new | |
296 | * lease chain and free the old. | |
297 | */ | |
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 | ||
330 | /*! | |
331 | * | |
332 | * \brief Link a lease to a lease chain position | |
333 | * | |
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. | |
336 | * | |
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 | |
340 | * | |
341 | */ | |
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 | ||
382 | /*! | |
383 | * | |
384 | * \brief Insert the lease at the specified position in both the lease chain | |
385 | * and the linked list | |
386 | * | |
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 | |
392 | * | |
393 | */ | |
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 | /*! | |
439 | * | |
440 | * \brief Debug only code, check the lease to verify it is sorted | |
441 | * | |
442 | * \param lc The leasechain to verify | |
443 | * | |
444 | * Calls log_fatal if the leasechain is not properly sorted | |
445 | */ | |
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 | ||
473 | /*! | |
474 | * | |
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. | |
479 | * | |
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 | |
487 | * | |
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 | |
490 | * lease to the end. | |
491 | * | |
492 | * \param lc The leasechain in which to insert the lease | |
493 | * \param lp The lease to insert | |
494 | * | |
495 | */ | |
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 | ||
547 | /*! | |
548 | * | |
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. | |
551 | * | |
552 | * \param lc The lease chain to update | |
553 | * \param n the entry to remove from the lease chain | |
554 | */ | |
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 | ||
578 | /*! | |
579 | * | |
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. | |
582 | * | |
583 | * \param lc The lease chain to update | |
584 | * \param pos the entry to remove from the lease chain | |
585 | */ | |
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 | ||
617 | /*! | |
618 | * | |
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. | |
621 | * | |
622 | * \param lc The lease chain to update | |
623 | * \param lp The lease to remove | |
624 | */ | |
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" | |
644 | : binding_state_names[lp->binding_state - 1]); | |
645 | } | |
646 | ||
647 | lc_unlink_lease_pos(lc, pos); | |
648 | } | |
649 | ||
3933e2aa SR |
650 | /*! |
651 | * | |
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. | |
655 | * | |
656 | * \param lc the lease chain to clear | |
657 | */ | |
658 | void | |
659 | lc_delete_all(struct leasechain *lc) { | |
660 | size_t i; | |
661 | ||
662 | if (lc->nelem > 0) { | |
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); | |
666 | if (i == 0) { | |
667 | break; | |
668 | } | |
669 | } | |
670 | } | |
671 | ||
672 | /* and then get rid of the list itself */ | |
72261e81 TM |
673 | if (lc->list != NULL) { |
674 | dfree(lc->list, MDL); | |
675 | lc->list = NULL; | |
676 | } | |
677 | ||
3933e2aa SR |
678 | lc->total = 0; |
679 | lc->nelem = 0; | |
680 | } | |
3933e2aa SR |
681 | |
682 | /*! | |
683 | * | |
684 | * \brief Set the growth value. This is the number of elements to | |
685 | * add to the array whenever it needs to grow. | |
686 | * | |
687 | * \param lc the lease chain to set up | |
688 | * \param growth the growth value to use | |
689 | */ | |
690 | void | |
691 | lc_init_growth(struct leasechain *lc, size_t growth) { | |
692 | lc->growth = growth; | |
693 | } | |
694 | ||
695 | #endif /* #if defined (BINARY_LEASES) */ |