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