FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_unit.c
1 /*-
2 * Copyright (c) 2004 Poul-Henning Kamp
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD: releng/11.0/sys/kern/subr_unit.c 300544 2016-05-24 00:14:58Z asomers $
27 *
28 *
29 * Unit number allocation functions.
30 *
31 * These functions implement a mixed run-length/bitmap management of unit
32 * number spaces in a very memory efficient manner.
33 *
34 * Allocation policy is always lowest free number first.
35 *
36 * A return value of -1 signals that no more unit numbers are available.
37 *
38 * There is no cost associated with the range of unitnumbers, so unless
39 * the resource really is finite, specify INT_MAX to new_unrhdr() and
40 * forget about checking the return value.
41 *
42 * If a mutex is not provided when the unit number space is created, a
43 * default global mutex is used. The advantage to passing a mutex in, is
44 * that the alloc_unrl() function can be called with the mutex already
45 * held (it will not be released by alloc_unrl()).
46 *
47 * The allocation function alloc_unr{l}() never sleeps (but it may block on
48 * the mutex of course).
49 *
50 * Freeing a unit number may require allocating memory, and can therefore
51 * sleep so the free_unr() function does not come in a pre-locked variant.
52 *
53 * A userland test program is included.
54 *
55 * Memory usage is a very complex function of the exact allocation
56 * pattern, but always very compact:
57 * * For the very typical case where a single unbroken run of unit
58 * numbers are allocated 44 bytes are used on i386.
59 * * For a unit number space of 1000 units and the random pattern
60 * in the usermode test program included, the worst case usage
61 * was 252 bytes on i386 for 500 allocated and 500 free units.
62 * * For a unit number space of 10000 units and the random pattern
63 * in the usermode test program included, the worst case usage
64 * was 798 bytes on i386 for 5000 allocated and 5000 free units.
65 * * The worst case is where every other unit number is allocated and
66 * the rest are free. In that case 44 + N/4 bytes are used where
67 * N is the number of the highest unit allocated.
68 */
69
70 #include <sys/param.h>
71 #include <sys/types.h>
72 #include <sys/_unrhdr.h>
73
74 #ifdef _KERNEL
75
76 #include <sys/bitstring.h>
77 #include <sys/malloc.h>
78 #include <sys/kernel.h>
79 #include <sys/systm.h>
80 #include <sys/limits.h>
81 #include <sys/lock.h>
82 #include <sys/mutex.h>
83
84 /*
85 * In theory it would be smarter to allocate the individual blocks
86 * with the zone allocator, but at this time the expectation is that
87 * there will typically not even be enough allocations to fill a single
88 * page, so we stick with malloc for now.
89 */
90 static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation");
91
92 #define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
93 #define Free(foo) free(foo, M_UNIT)
94
95 static struct mtx unitmtx;
96
97 MTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF);
98
99 #else /* ...USERLAND */
100
101 #include <bitstring.h>
102 #include <err.h>
103 #include <errno.h>
104 #include <getopt.h>
105 #include <stdbool.h>
106 #include <stdio.h>
107 #include <stdlib.h>
108 #include <string.h>
109
110 #define KASSERT(cond, arg) \
111 do { \
112 if (!(cond)) { \
113 printf arg; \
114 abort(); \
115 } \
116 } while (0)
117
118 static int no_alloc;
119 #define Malloc(foo) _Malloc(foo, __LINE__)
120 static void *
121 _Malloc(size_t foo, int line)
122 {
123
124 KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
125 return (calloc(foo, 1));
126 }
127 #define Free(foo) free(foo)
128
129 struct unrhdr;
130
131
132 struct mtx {
133 int state;
134 } unitmtx;
135
136 static void
137 mtx_lock(struct mtx *mp)
138 {
139 KASSERT(mp->state == 0, ("mutex already locked"));
140 mp->state = 1;
141 }
142
143 static void
144 mtx_unlock(struct mtx *mp)
145 {
146 KASSERT(mp->state == 1, ("mutex not locked"));
147 mp->state = 0;
148 }
149
150 #define MA_OWNED 9
151
152 static void
153 mtx_assert(struct mtx *mp, int flag)
154 {
155 if (flag == MA_OWNED) {
156 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
157 }
158 }
159
160 #define CTASSERT(foo)
161 #define WITNESS_WARN(flags, lock, fmt, ...) (void)0
162
163 #endif /* USERLAND */
164
165 /*
166 * This is our basic building block.
167 *
168 * It can be used in three different ways depending on the value of the ptr
169 * element:
170 * If ptr is NULL, it represents a run of free items.
171 * If ptr points to the unrhdr it represents a run of allocated items.
172 * Otherwise it points to a bitstring of allocated items.
173 *
174 * For runs the len field is the length of the run.
175 * For bitmaps the len field represents the number of allocated items.
176 *
177 * The bitmap is the same size as struct unr to optimize memory management.
178 */
179 struct unr {
180 TAILQ_ENTRY(unr) list;
181 u_int len;
182 void *ptr;
183 };
184
185 struct unrb {
186 bitstr_t map[sizeof(struct unr) / sizeof(bitstr_t)];
187 };
188
189 CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
190
191 /* Number of bits we can store in the bitmap */
192 #define NBITS (8 * sizeof(((struct unrb*)NULL)->map))
193
194 /* Is the unrb empty in at least the first len bits? */
195 static inline bool
196 ub_empty(struct unrb *ub, int len) {
197 int first_set;
198
199 bit_ffs(ub->map, len, &first_set);
200 return (first_set == -1);
201 }
202
203 /* Is the unrb full? That is, is the number of set elements equal to len? */
204 static inline bool
205 ub_full(struct unrb *ub, int len)
206 {
207 int first_clear;
208
209 bit_ffc(ub->map, len, &first_clear);
210 return (first_clear == -1);
211 }
212
213
214 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
215 /*
216 * Consistency check function.
217 *
218 * Checks the internal consistency as well as we can.
219 *
220 * Called at all boundaries of this API.
221 */
222 static void
223 check_unrhdr(struct unrhdr *uh, int line)
224 {
225 struct unr *up;
226 struct unrb *ub;
227 int w;
228 u_int y, z;
229
230 y = uh->first;
231 z = 0;
232 TAILQ_FOREACH(up, &uh->head, list) {
233 z++;
234 if (up->ptr != uh && up->ptr != NULL) {
235 ub = up->ptr;
236 KASSERT (up->len <= NBITS,
237 ("UNR inconsistency: len %u max %zd (line %d)\n",
238 up->len, NBITS, line));
239 z++;
240 w = 0;
241 bit_count(ub->map, 0, up->len, &w);
242 y += w;
243 } else if (up->ptr != NULL)
244 y += up->len;
245 }
246 KASSERT (y == uh->busy,
247 ("UNR inconsistency: items %u found %u (line %d)\n",
248 uh->busy, y, line));
249 KASSERT (z == uh->alloc,
250 ("UNR inconsistency: chunks %u found %u (line %d)\n",
251 uh->alloc, z, line));
252 }
253
254 #else
255
256 static __inline void
257 check_unrhdr(struct unrhdr *uh __unused, int line __unused)
258 {
259
260 }
261
262 #endif
263
264
265 /*
266 * Userland memory management. Just use calloc and keep track of how
267 * many elements we have allocated for check_unrhdr().
268 */
269
270 static __inline void *
271 new_unr(struct unrhdr *uh, void **p1, void **p2)
272 {
273 void *p;
274
275 uh->alloc++;
276 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
277 if (*p1 != NULL) {
278 p = *p1;
279 *p1 = NULL;
280 return (p);
281 } else {
282 p = *p2;
283 *p2 = NULL;
284 return (p);
285 }
286 }
287
288 static __inline void
289 delete_unr(struct unrhdr *uh, void *ptr)
290 {
291 struct unr *up;
292
293 uh->alloc--;
294 up = ptr;
295 TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
296 }
297
298 void
299 clean_unrhdrl(struct unrhdr *uh)
300 {
301 struct unr *up;
302
303 mtx_assert(uh->mtx, MA_OWNED);
304 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
305 TAILQ_REMOVE(&uh->ppfree, up, list);
306 mtx_unlock(uh->mtx);
307 Free(up);
308 mtx_lock(uh->mtx);
309 }
310
311 }
312
313 void
314 clean_unrhdr(struct unrhdr *uh)
315 {
316
317 mtx_lock(uh->mtx);
318 clean_unrhdrl(uh);
319 mtx_unlock(uh->mtx);
320 }
321
322 void
323 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
324 {
325
326 KASSERT(low >= 0 && low <= high,
327 ("UNR: use error: new_unrhdr(%d, %d)", low, high));
328 if (mutex != NULL)
329 uh->mtx = mutex;
330 else
331 uh->mtx = &unitmtx;
332 TAILQ_INIT(&uh->head);
333 TAILQ_INIT(&uh->ppfree);
334 uh->low = low;
335 uh->high = high;
336 uh->first = 0;
337 uh->last = 1 + (high - low);
338 check_unrhdr(uh, __LINE__);
339 }
340
341 /*
342 * Allocate a new unrheader set.
343 *
344 * Highest and lowest valid values given as parameters.
345 */
346
347 struct unrhdr *
348 new_unrhdr(int low, int high, struct mtx *mutex)
349 {
350 struct unrhdr *uh;
351
352 uh = Malloc(sizeof *uh);
353 init_unrhdr(uh, low, high, mutex);
354 return (uh);
355 }
356
357 void
358 delete_unrhdr(struct unrhdr *uh)
359 {
360
361 check_unrhdr(uh, __LINE__);
362 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
363 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
364 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
365 ("unrhdr has postponed item for free"));
366 Free(uh);
367 }
368
369 static __inline int
370 is_bitmap(struct unrhdr *uh, struct unr *up)
371 {
372 return (up->ptr != uh && up->ptr != NULL);
373 }
374
375 /*
376 * Look for sequence of items which can be combined into a bitmap, if
377 * multiple are present, take the one which saves most memory.
378 *
379 * Return (1) if a sequence was found to indicate that another call
380 * might be able to do more. Return (0) if we found no suitable sequence.
381 *
382 * NB: called from alloc_unr(), no new memory allocation allowed.
383 */
384 static int
385 optimize_unr(struct unrhdr *uh)
386 {
387 struct unr *up, *uf, *us;
388 struct unrb *ub, *ubf;
389 u_int a, l, ba;
390
391 /*
392 * Look for the run of items (if any) which when collapsed into
393 * a bitmap would save most memory.
394 */
395 us = NULL;
396 ba = 0;
397 TAILQ_FOREACH(uf, &uh->head, list) {
398 if (uf->len >= NBITS)
399 continue;
400 a = 1;
401 if (is_bitmap(uh, uf))
402 a++;
403 l = uf->len;
404 up = uf;
405 while (1) {
406 up = TAILQ_NEXT(up, list);
407 if (up == NULL)
408 break;
409 if ((up->len + l) > NBITS)
410 break;
411 a++;
412 if (is_bitmap(uh, up))
413 a++;
414 l += up->len;
415 }
416 if (a > ba) {
417 ba = a;
418 us = uf;
419 }
420 }
421 if (ba < 3)
422 return (0);
423
424 /*
425 * If the first element is not a bitmap, make it one.
426 * Trying to do so without allocating more memory complicates things
427 * a bit
428 */
429 if (!is_bitmap(uh, us)) {
430 uf = TAILQ_NEXT(us, list);
431 TAILQ_REMOVE(&uh->head, us, list);
432 a = us->len;
433 l = us->ptr == uh ? 1 : 0;
434 ub = (void *)us;
435 bit_nclear(ub->map, 0, NBITS - 1);
436 if (l)
437 bit_nset(ub->map, 0, a);
438 if (!is_bitmap(uh, uf)) {
439 if (uf->ptr == NULL)
440 bit_nclear(ub->map, a, a + uf->len - 1);
441 else
442 bit_nset(ub->map, a, a + uf->len - 1);
443 uf->ptr = ub;
444 uf->len += a;
445 us = uf;
446 } else {
447 ubf = uf->ptr;
448 for (l = 0; l < uf->len; l++, a++) {
449 if (bit_test(ubf->map, l))
450 bit_set(ub->map, a);
451 else
452 bit_clear(ub->map, a);
453 }
454 uf->len = a;
455 delete_unr(uh, uf->ptr);
456 uf->ptr = ub;
457 us = uf;
458 }
459 }
460 ub = us->ptr;
461 while (1) {
462 uf = TAILQ_NEXT(us, list);
463 if (uf == NULL)
464 return (1);
465 if (uf->len + us->len > NBITS)
466 return (1);
467 if (uf->ptr == NULL) {
468 bit_nclear(ub->map, us->len, us->len + uf->len - 1);
469 us->len += uf->len;
470 TAILQ_REMOVE(&uh->head, uf, list);
471 delete_unr(uh, uf);
472 } else if (uf->ptr == uh) {
473 bit_nset(ub->map, us->len, us->len + uf->len - 1);
474 us->len += uf->len;
475 TAILQ_REMOVE(&uh->head, uf, list);
476 delete_unr(uh, uf);
477 } else {
478 ubf = uf->ptr;
479 for (l = 0; l < uf->len; l++, us->len++) {
480 if (bit_test(ubf->map, l))
481 bit_set(ub->map, us->len);
482 else
483 bit_clear(ub->map, us->len);
484 }
485 TAILQ_REMOVE(&uh->head, uf, list);
486 delete_unr(uh, ubf);
487 delete_unr(uh, uf);
488 }
489 }
490 }
491
492 /*
493 * See if a given unr should be collapsed with a neighbor.
494 *
495 * NB: called from alloc_unr(), no new memory allocation allowed.
496 */
497 static void
498 collapse_unr(struct unrhdr *uh, struct unr *up)
499 {
500 struct unr *upp;
501 struct unrb *ub;
502
503 /* If bitmap is all set or clear, change it to runlength */
504 if (is_bitmap(uh, up)) {
505 ub = up->ptr;
506 if (ub_full(ub, up->len)) {
507 delete_unr(uh, up->ptr);
508 up->ptr = uh;
509 } else if (ub_empty(ub, up->len)) {
510 delete_unr(uh, up->ptr);
511 up->ptr = NULL;
512 }
513 }
514
515 /* If nothing left in runlength, delete it */
516 if (up->len == 0) {
517 upp = TAILQ_PREV(up, unrhd, list);
518 if (upp == NULL)
519 upp = TAILQ_NEXT(up, list);
520 TAILQ_REMOVE(&uh->head, up, list);
521 delete_unr(uh, up);
522 up = upp;
523 }
524
525 /* If we have "hot-spot" still, merge with neighbor if possible */
526 if (up != NULL) {
527 upp = TAILQ_PREV(up, unrhd, list);
528 if (upp != NULL && up->ptr == upp->ptr) {
529 up->len += upp->len;
530 TAILQ_REMOVE(&uh->head, upp, list);
531 delete_unr(uh, upp);
532 }
533 upp = TAILQ_NEXT(up, list);
534 if (upp != NULL && up->ptr == upp->ptr) {
535 up->len += upp->len;
536 TAILQ_REMOVE(&uh->head, upp, list);
537 delete_unr(uh, upp);
538 }
539 }
540
541 /* Merge into ->first if possible */
542 upp = TAILQ_FIRST(&uh->head);
543 if (upp != NULL && upp->ptr == uh) {
544 uh->first += upp->len;
545 TAILQ_REMOVE(&uh->head, upp, list);
546 delete_unr(uh, upp);
547 if (up == upp)
548 up = NULL;
549 }
550
551 /* Merge into ->last if possible */
552 upp = TAILQ_LAST(&uh->head, unrhd);
553 if (upp != NULL && upp->ptr == NULL) {
554 uh->last += upp->len;
555 TAILQ_REMOVE(&uh->head, upp, list);
556 delete_unr(uh, upp);
557 if (up == upp)
558 up = NULL;
559 }
560
561 /* Try to make bitmaps */
562 while (optimize_unr(uh))
563 continue;
564 }
565
566 /*
567 * Allocate a free unr.
568 */
569 int
570 alloc_unrl(struct unrhdr *uh)
571 {
572 struct unr *up;
573 struct unrb *ub;
574 u_int x;
575 int y;
576
577 mtx_assert(uh->mtx, MA_OWNED);
578 check_unrhdr(uh, __LINE__);
579 x = uh->low + uh->first;
580
581 up = TAILQ_FIRST(&uh->head);
582
583 /*
584 * If we have an ideal split, just adjust the first+last
585 */
586 if (up == NULL && uh->last > 0) {
587 uh->first++;
588 uh->last--;
589 uh->busy++;
590 return (x);
591 }
592
593 /*
594 * We can always allocate from the first list element, so if we have
595 * nothing on the list, we must have run out of unit numbers.
596 */
597 if (up == NULL)
598 return (-1);
599
600 KASSERT(up->ptr != uh, ("UNR first element is allocated"));
601
602 if (up->ptr == NULL) { /* free run */
603 uh->first++;
604 up->len--;
605 } else { /* bitmap */
606 ub = up->ptr;
607 bit_ffc(ub->map, up->len, &y);
608 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
609 bit_set(ub->map, y);
610 x += y;
611 }
612 uh->busy++;
613 collapse_unr(uh, up);
614 return (x);
615 }
616
617 int
618 alloc_unr(struct unrhdr *uh)
619 {
620 int i;
621
622 mtx_lock(uh->mtx);
623 i = alloc_unrl(uh);
624 clean_unrhdrl(uh);
625 mtx_unlock(uh->mtx);
626 return (i);
627 }
628
629 static int
630 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
631 {
632 struct unr *up, *upn;
633 struct unrb *ub;
634 u_int i, last, tl;
635
636 mtx_assert(uh->mtx, MA_OWNED);
637
638 if (item < uh->low + uh->first || item > uh->high)
639 return (-1);
640
641 up = TAILQ_FIRST(&uh->head);
642 /* Ideal split. */
643 if (up == NULL && item - uh->low == uh->first) {
644 uh->first++;
645 uh->last--;
646 uh->busy++;
647 check_unrhdr(uh, __LINE__);
648 return (item);
649 }
650
651 i = item - uh->low - uh->first;
652
653 if (up == NULL) {
654 up = new_unr(uh, p1, p2);
655 up->ptr = NULL;
656 up->len = i;
657 TAILQ_INSERT_TAIL(&uh->head, up, list);
658 up = new_unr(uh, p1, p2);
659 up->ptr = uh;
660 up->len = 1;
661 TAILQ_INSERT_TAIL(&uh->head, up, list);
662 uh->last = uh->high - uh->low - i;
663 uh->busy++;
664 check_unrhdr(uh, __LINE__);
665 return (item);
666 } else {
667 /* Find the item which contains the unit we want to allocate. */
668 TAILQ_FOREACH(up, &uh->head, list) {
669 if (up->len > i)
670 break;
671 i -= up->len;
672 }
673 }
674
675 if (up == NULL) {
676 if (i > 0) {
677 up = new_unr(uh, p1, p2);
678 up->ptr = NULL;
679 up->len = i;
680 TAILQ_INSERT_TAIL(&uh->head, up, list);
681 }
682 up = new_unr(uh, p1, p2);
683 up->ptr = uh;
684 up->len = 1;
685 TAILQ_INSERT_TAIL(&uh->head, up, list);
686 goto done;
687 }
688
689 if (is_bitmap(uh, up)) {
690 ub = up->ptr;
691 if (bit_test(ub->map, i) == 0) {
692 bit_set(ub->map, i);
693 goto done;
694 } else
695 return (-1);
696 } else if (up->ptr == uh)
697 return (-1);
698
699 KASSERT(up->ptr == NULL,
700 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
701
702 /* Split off the tail end, if any. */
703 tl = up->len - (1 + i);
704 if (tl > 0) {
705 upn = new_unr(uh, p1, p2);
706 upn->ptr = NULL;
707 upn->len = tl;
708 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
709 }
710
711 /* Split off head end, if any */
712 if (i > 0) {
713 upn = new_unr(uh, p1, p2);
714 upn->len = i;
715 upn->ptr = NULL;
716 TAILQ_INSERT_BEFORE(up, upn, list);
717 }
718 up->len = 1;
719 up->ptr = uh;
720
721 done:
722 last = uh->high - uh->low - (item - uh->low);
723 if (uh->last > last)
724 uh->last = last;
725 uh->busy++;
726 collapse_unr(uh, up);
727 check_unrhdr(uh, __LINE__);
728 return (item);
729 }
730
731 int
732 alloc_unr_specific(struct unrhdr *uh, u_int item)
733 {
734 void *p1, *p2;
735 int i;
736
737 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
738
739 p1 = Malloc(sizeof(struct unr));
740 p2 = Malloc(sizeof(struct unr));
741
742 mtx_lock(uh->mtx);
743 i = alloc_unr_specificl(uh, item, &p1, &p2);
744 mtx_unlock(uh->mtx);
745
746 if (p1 != NULL)
747 Free(p1);
748 if (p2 != NULL)
749 Free(p2);
750
751 return (i);
752 }
753
754 /*
755 * Free a unr.
756 *
757 * If we can save unrs by using a bitmap, do so.
758 */
759 static void
760 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
761 {
762 struct unr *up, *upp, *upn;
763 struct unrb *ub;
764 u_int pl;
765
766 KASSERT(item >= uh->low && item <= uh->high,
767 ("UNR: free_unr(%u) out of range [%u...%u]",
768 item, uh->low, uh->high));
769 check_unrhdr(uh, __LINE__);
770 item -= uh->low;
771 upp = TAILQ_FIRST(&uh->head);
772 /*
773 * Freeing in the ideal split case
774 */
775 if (item + 1 == uh->first && upp == NULL) {
776 uh->last++;
777 uh->first--;
778 uh->busy--;
779 check_unrhdr(uh, __LINE__);
780 return;
781 }
782 /*
783 * Freeing in the ->first section. Create a run starting at the
784 * freed item. The code below will subdivide it.
785 */
786 if (item < uh->first) {
787 up = new_unr(uh, p1, p2);
788 up->ptr = uh;
789 up->len = uh->first - item;
790 TAILQ_INSERT_HEAD(&uh->head, up, list);
791 uh->first -= up->len;
792 }
793
794 item -= uh->first;
795
796 /* Find the item which contains the unit we want to free */
797 TAILQ_FOREACH(up, &uh->head, list) {
798 if (up->len > item)
799 break;
800 item -= up->len;
801 }
802
803 /* Handle bitmap items */
804 if (is_bitmap(uh, up)) {
805 ub = up->ptr;
806
807 KASSERT(bit_test(ub->map, item) != 0,
808 ("UNR: Freeing free item %d (bitmap)\n", item));
809 bit_clear(ub->map, item);
810 uh->busy--;
811 collapse_unr(uh, up);
812 return;
813 }
814
815 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
816
817 /* Just this one left, reap it */
818 if (up->len == 1) {
819 up->ptr = NULL;
820 uh->busy--;
821 collapse_unr(uh, up);
822 return;
823 }
824
825 /* Check if we can shift the item into the previous 'free' run */
826 upp = TAILQ_PREV(up, unrhd, list);
827 if (item == 0 && upp != NULL && upp->ptr == NULL) {
828 upp->len++;
829 up->len--;
830 uh->busy--;
831 collapse_unr(uh, up);
832 return;
833 }
834
835 /* Check if we can shift the item to the next 'free' run */
836 upn = TAILQ_NEXT(up, list);
837 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
838 upn->len++;
839 up->len--;
840 uh->busy--;
841 collapse_unr(uh, up);
842 return;
843 }
844
845 /* Split off the tail end, if any. */
846 pl = up->len - (1 + item);
847 if (pl > 0) {
848 upp = new_unr(uh, p1, p2);
849 upp->ptr = uh;
850 upp->len = pl;
851 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
852 }
853
854 /* Split off head end, if any */
855 if (item > 0) {
856 upp = new_unr(uh, p1, p2);
857 upp->len = item;
858 upp->ptr = uh;
859 TAILQ_INSERT_BEFORE(up, upp, list);
860 }
861 up->len = 1;
862 up->ptr = NULL;
863 uh->busy--;
864 collapse_unr(uh, up);
865 }
866
867 void
868 free_unr(struct unrhdr *uh, u_int item)
869 {
870 void *p1, *p2;
871
872 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
873 p1 = Malloc(sizeof(struct unr));
874 p2 = Malloc(sizeof(struct unr));
875 mtx_lock(uh->mtx);
876 free_unrl(uh, item, &p1, &p2);
877 clean_unrhdrl(uh);
878 mtx_unlock(uh->mtx);
879 if (p1 != NULL)
880 Free(p1);
881 if (p2 != NULL)
882 Free(p2);
883 }
884
885 #ifndef _KERNEL /* USERLAND test driver */
886
887 /*
888 * Simple stochastic test driver for the above functions. The code resides
889 * here so that it can access static functions and structures.
890 */
891
892 static bool verbose;
893 #define VPRINTF(...) {if (verbose) printf(__VA_ARGS__);}
894
895 static void
896 print_unr(struct unrhdr *uh, struct unr *up)
897 {
898 u_int x;
899 struct unrb *ub;
900
901 printf(" %p len = %5u ", up, up->len);
902 if (up->ptr == NULL)
903 printf("free\n");
904 else if (up->ptr == uh)
905 printf("alloc\n");
906 else {
907 ub = up->ptr;
908 printf("bitmap [");
909 for (x = 0; x < up->len; x++) {
910 if (bit_test(ub->map, x))
911 printf("#");
912 else
913 printf(" ");
914 }
915 printf("]\n");
916 }
917 }
918
919 static void
920 print_unrhdr(struct unrhdr *uh)
921 {
922 struct unr *up;
923 u_int x;
924
925 printf(
926 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
927 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
928 x = uh->low + uh->first;
929 TAILQ_FOREACH(up, &uh->head, list) {
930 printf(" from = %5u", x);
931 print_unr(uh, up);
932 if (up->ptr == NULL || up->ptr == uh)
933 x += up->len;
934 else
935 x += NBITS;
936 }
937 }
938
939 static void
940 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
941 {
942 int j;
943
944 if (a[i]) {
945 VPRINTF("F %u\n", i);
946 free_unr(uh, i);
947 a[i] = 0;
948 } else {
949 no_alloc = 1;
950 j = alloc_unr(uh);
951 if (j != -1) {
952 a[j] = 1;
953 VPRINTF("A %d\n", j);
954 }
955 no_alloc = 0;
956 }
957 }
958
959 static void
960 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
961 {
962 int j;
963
964 j = alloc_unr_specific(uh, i);
965 if (j == -1) {
966 VPRINTF("F %u\n", i);
967 a[i] = 0;
968 free_unr(uh, i);
969 } else {
970 a[i] = 1;
971 VPRINTF("A %d\n", j);
972 }
973 }
974
975 static void
976 usage(char** argv)
977 {
978 printf("%s [-h] [-r REPETITIONS] [-v]\n", argv[0]);
979 }
980
981 int
982 main(int argc, char **argv)
983 {
984 struct unrhdr *uh;
985 char *a;
986 long count = 10000; /* Number of unrs to test */
987 long reps = 1, m;
988 int ch;
989 u_int i, x, j;
990
991 verbose = false;
992
993 while ((ch = getopt(argc, argv, "hr:v")) != -1) {
994 switch (ch) {
995 case 'r':
996 errno = 0;
997 reps = strtol(optarg, NULL, 0);
998 if (errno == ERANGE || errno == EINVAL) {
999 usage(argv);
1000 exit(2);
1001 }
1002
1003 break;
1004 case 'v':
1005 verbose = true;
1006 break;
1007 case 'h':
1008 default:
1009 usage(argv);
1010 exit(2);
1011 }
1012
1013
1014 }
1015
1016 setbuf(stdout, NULL);
1017 uh = new_unrhdr(0, count - 1, NULL);
1018 print_unrhdr(uh);
1019
1020 a = calloc(count, sizeof(char));
1021 if (a == NULL)
1022 err(1, "calloc failed");
1023 srandomdev();
1024
1025 printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
1026 printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
1027 printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
1028 printf("NBITS %lu\n", (unsigned long)NBITS);
1029 x = 1;
1030 for (m = 0; m < count * reps; m++) {
1031 j = random();
1032 i = (j >> 1) % count;
1033 #if 0
1034 if (a[i] && (j & 1))
1035 continue;
1036 #endif
1037 if ((random() & 1) != 0)
1038 test_alloc_unr(uh, i, a);
1039 else
1040 test_alloc_unr_specific(uh, i, a);
1041
1042 if (verbose)
1043 print_unrhdr(uh);
1044 check_unrhdr(uh, __LINE__);
1045 }
1046 for (i = 0; i < (u_int)count; i++) {
1047 if (a[i]) {
1048 if (verbose) {
1049 printf("C %u\n", i);
1050 print_unrhdr(uh);
1051 }
1052 free_unr(uh, i);
1053 }
1054 }
1055 print_unrhdr(uh);
1056 delete_unrhdr(uh);
1057 free(a);
1058 return (0);
1059 }
1060 #endif
Cache object: 5a92e8ac68ce07b29c92be9a0aaa6b54
|