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/8.3/sys/kern/subr_unit.c 219642 2011-03-14 17:08:30Z jh $
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 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/types.h>
71 #include <sys/queue.h>
72 #include <sys/bitstring.h>
73
74 #ifdef _KERNEL
75
76 #include <sys/param.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 <stdio.h>
102 #include <stdlib.h>
103 #include <string.h>
104
105 #define KASSERT(cond, arg) \
106 do { \
107 if (!(cond)) { \
108 printf arg; \
109 abort(); \
110 } \
111 } while (0)
112
113 static int no_alloc;
114 #define Malloc(foo) _Malloc(foo, __LINE__)
115 static void *
116 _Malloc(size_t foo, int line)
117 {
118
119 KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
120 return (calloc(foo, 1));
121 }
122 #define Free(foo) free(foo)
123
124 struct unrhdr;
125
126
127 struct mtx {
128 int state;
129 } unitmtx;
130
131 static void
132 mtx_lock(struct mtx *mp)
133 {
134 KASSERT(mp->state == 0, ("mutex already locked"));
135 mp->state = 1;
136 }
137
138 static void
139 mtx_unlock(struct mtx *mp)
140 {
141 KASSERT(mp->state == 1, ("mutex not locked"));
142 mp->state = 0;
143 }
144
145 #define MA_OWNED 9
146
147 static void
148 mtx_assert(struct mtx *mp, int flag)
149 {
150 if (flag == MA_OWNED) {
151 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
152 }
153 }
154
155 #define CTASSERT(foo)
156 #define WITNESS_WARN(flags, lock, fmt, ...) (void)0
157
158 #endif /* USERLAND */
159
160 /*
161 * This is our basic building block.
162 *
163 * It can be used in three different ways depending on the value of the ptr
164 * element:
165 * If ptr is NULL, it represents a run of free items.
166 * If ptr points to the unrhdr it represents a run of allocated items.
167 * Otherwise it points to an bitstring of allocated items.
168 *
169 * For runs the len field is the length of the run.
170 * For bitmaps the len field represents the number of allocated items.
171 *
172 * The bitmap is the same size as struct unr to optimize memory management.
173 */
174 struct unr {
175 TAILQ_ENTRY(unr) list;
176 u_int len;
177 void *ptr;
178 };
179
180 struct unrb {
181 u_char busy;
182 bitstr_t map[sizeof(struct unr) - 1];
183 };
184
185 CTASSERT(sizeof(struct unr) == sizeof(struct unrb));
186
187 /* Number of bits in the bitmap */
188 #define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8)
189
190 /* Header element for a unr number space. */
191
192 struct unrhdr {
193 TAILQ_HEAD(unrhd,unr) head;
194 u_int low; /* Lowest item */
195 u_int high; /* Highest item */
196 u_int busy; /* Count of allocated items */
197 u_int alloc; /* Count of memory allocations */
198 u_int first; /* items in allocated from start */
199 u_int last; /* items free at end */
200 struct mtx *mtx;
201 TAILQ_HEAD(unrfr,unr) ppfree; /* Items to be freed after mtx
202 lock dropped */
203 };
204
205
206 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
207 /*
208 * Consistency check function.
209 *
210 * Checks the internal consistency as well as we can.
211 *
212 * Called at all boundaries of this API.
213 */
214 static void
215 check_unrhdr(struct unrhdr *uh, int line)
216 {
217 struct unr *up;
218 struct unrb *ub;
219 u_int x, y, z, w;
220
221 y = uh->first;
222 z = 0;
223 TAILQ_FOREACH(up, &uh->head, list) {
224 z++;
225 if (up->ptr != uh && up->ptr != NULL) {
226 ub = up->ptr;
227 KASSERT (up->len <= NBITS,
228 ("UNR inconsistency: len %u max %d (line %d)\n",
229 up->len, NBITS, line));
230 z++;
231 w = 0;
232 for (x = 0; x < up->len; x++)
233 if (bit_test(ub->map, x))
234 w++;
235 KASSERT (w == ub->busy,
236 ("UNR inconsistency: busy %u found %u (line %d)\n",
237 ub->busy, w, line));
238 y += w;
239 } else if (up->ptr != NULL)
240 y += up->len;
241 }
242 KASSERT (y == uh->busy,
243 ("UNR inconsistency: items %u found %u (line %d)\n",
244 uh->busy, y, line));
245 KASSERT (z == uh->alloc,
246 ("UNR inconsistency: chunks %u found %u (line %d)\n",
247 uh->alloc, z, line));
248 }
249
250 #else
251
252 static __inline void
253 check_unrhdr(struct unrhdr *uh, int line)
254 {
255
256 }
257
258 #endif
259
260
261 /*
262 * Userland memory management. Just use calloc and keep track of how
263 * many elements we have allocated for check_unrhdr().
264 */
265
266 static __inline void *
267 new_unr(struct unrhdr *uh, void **p1, void **p2)
268 {
269 void *p;
270
271 uh->alloc++;
272 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
273 if (*p1 != NULL) {
274 p = *p1;
275 *p1 = NULL;
276 return (p);
277 } else {
278 p = *p2;
279 *p2 = NULL;
280 return (p);
281 }
282 }
283
284 static __inline void
285 delete_unr(struct unrhdr *uh, void *ptr)
286 {
287 struct unr *up;
288
289 uh->alloc--;
290 up = ptr;
291 TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
292 }
293
294 void
295 clean_unrhdrl(struct unrhdr *uh)
296 {
297 struct unr *up;
298
299 mtx_assert(uh->mtx, MA_OWNED);
300 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
301 TAILQ_REMOVE(&uh->ppfree, up, list);
302 mtx_unlock(uh->mtx);
303 Free(up);
304 mtx_lock(uh->mtx);
305 }
306
307 }
308
309 void
310 clean_unrhdr(struct unrhdr *uh)
311 {
312
313 mtx_lock(uh->mtx);
314 clean_unrhdrl(uh);
315 mtx_unlock(uh->mtx);
316 }
317
318 /*
319 * Allocate a new unrheader set.
320 *
321 * Highest and lowest valid values given as parameters.
322 */
323
324 struct unrhdr *
325 new_unrhdr(int low, int high, struct mtx *mutex)
326 {
327 struct unrhdr *uh;
328
329 KASSERT(low >= 0 && low <= high,
330 ("UNR: use error: new_unrhdr(%d, %d)", low, high));
331 uh = Malloc(sizeof *uh);
332 if (mutex != NULL)
333 uh->mtx = mutex;
334 else
335 uh->mtx = &unitmtx;
336 TAILQ_INIT(&uh->head);
337 TAILQ_INIT(&uh->ppfree);
338 uh->low = low;
339 uh->high = high;
340 uh->first = 0;
341 uh->last = 1 + (high - low);
342 check_unrhdr(uh, __LINE__);
343 return (uh);
344 }
345
346 void
347 delete_unrhdr(struct unrhdr *uh)
348 {
349
350 check_unrhdr(uh, __LINE__);
351 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
352 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
353 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
354 ("unrhdr has postponed item for free"));
355 Free(uh);
356 }
357
358 static __inline int
359 is_bitmap(struct unrhdr *uh, struct unr *up)
360 {
361 return (up->ptr != uh && up->ptr != NULL);
362 }
363
364 /*
365 * Look for sequence of items which can be combined into a bitmap, if
366 * multiple are present, take the one which saves most memory.
367 *
368 * Return (1) if a sequence was found to indicate that another call
369 * might be able to do more. Return (0) if we found no suitable sequence.
370 *
371 * NB: called from alloc_unr(), no new memory allocation allowed.
372 */
373 static int
374 optimize_unr(struct unrhdr *uh)
375 {
376 struct unr *up, *uf, *us;
377 struct unrb *ub, *ubf;
378 u_int a, l, ba;
379
380 /*
381 * Look for the run of items (if any) which when collapsed into
382 * a bitmap would save most memory.
383 */
384 us = NULL;
385 ba = 0;
386 TAILQ_FOREACH(uf, &uh->head, list) {
387 if (uf->len >= NBITS)
388 continue;
389 a = 1;
390 if (is_bitmap(uh, uf))
391 a++;
392 l = uf->len;
393 up = uf;
394 while (1) {
395 up = TAILQ_NEXT(up, list);
396 if (up == NULL)
397 break;
398 if ((up->len + l) > NBITS)
399 break;
400 a++;
401 if (is_bitmap(uh, up))
402 a++;
403 l += up->len;
404 }
405 if (a > ba) {
406 ba = a;
407 us = uf;
408 }
409 }
410 if (ba < 3)
411 return (0);
412
413 /*
414 * If the first element is not a bitmap, make it one.
415 * Trying to do so without allocating more memory complicates things
416 * a bit
417 */
418 if (!is_bitmap(uh, us)) {
419 uf = TAILQ_NEXT(us, list);
420 TAILQ_REMOVE(&uh->head, us, list);
421 a = us->len;
422 l = us->ptr == uh ? 1 : 0;
423 ub = (void *)us;
424 ub->busy = 0;
425 if (l) {
426 bit_nset(ub->map, 0, a);
427 ub->busy += a;
428 } else {
429 bit_nclear(ub->map, 0, a);
430 }
431 if (!is_bitmap(uh, uf)) {
432 if (uf->ptr == NULL) {
433 bit_nclear(ub->map, a, a + uf->len - 1);
434 } else {
435 bit_nset(ub->map, a, a + uf->len - 1);
436 ub->busy += uf->len;
437 }
438 uf->ptr = ub;
439 uf->len += a;
440 us = uf;
441 } else {
442 ubf = uf->ptr;
443 for (l = 0; l < uf->len; l++, a++) {
444 if (bit_test(ubf->map, l)) {
445 bit_set(ub->map, a);
446 ub->busy++;
447 } else {
448 bit_clear(ub->map, a);
449 }
450 }
451 uf->len = a;
452 delete_unr(uh, uf->ptr);
453 uf->ptr = ub;
454 us = uf;
455 }
456 }
457 ub = us->ptr;
458 while (1) {
459 uf = TAILQ_NEXT(us, list);
460 if (uf == NULL)
461 return (1);
462 if (uf->len + us->len > NBITS)
463 return (1);
464 if (uf->ptr == NULL) {
465 bit_nclear(ub->map, us->len, us->len + uf->len - 1);
466 us->len += uf->len;
467 TAILQ_REMOVE(&uh->head, uf, list);
468 delete_unr(uh, uf);
469 } else if (uf->ptr == uh) {
470 bit_nset(ub->map, us->len, us->len + uf->len - 1);
471 ub->busy += uf->len;
472 us->len += uf->len;
473 TAILQ_REMOVE(&uh->head, uf, list);
474 delete_unr(uh, uf);
475 } else {
476 ubf = uf->ptr;
477 for (l = 0; l < uf->len; l++, us->len++) {
478 if (bit_test(ubf->map, l)) {
479 bit_set(ub->map, us->len);
480 ub->busy++;
481 } else {
482 bit_clear(ub->map, us->len);
483 }
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->busy == up->len) {
507 delete_unr(uh, up->ptr);
508 up->ptr = uh;
509 } else if (ub->busy == 0) {
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 KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
608 bit_ffc(ub->map, up->len, &y);
609 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
610 bit_set(ub->map, y);
611 ub->busy++;
612 x += y;
613 }
614 uh->busy++;
615 collapse_unr(uh, up);
616 return (x);
617 }
618
619 int
620 alloc_unr(struct unrhdr *uh)
621 {
622 int i;
623
624 mtx_lock(uh->mtx);
625 i = alloc_unrl(uh);
626 clean_unrhdrl(uh);
627 mtx_unlock(uh->mtx);
628 return (i);
629 }
630
631 static int
632 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
633 {
634 struct unr *up, *upn;
635 struct unrb *ub;
636 u_int i, last, tl;
637
638 mtx_assert(uh->mtx, MA_OWNED);
639
640 if (item < uh->low + uh->first || item > uh->high)
641 return (-1);
642
643 up = TAILQ_FIRST(&uh->head);
644 /* Ideal split. */
645 if (up == NULL && item - uh->low == uh->first) {
646 uh->first++;
647 uh->last--;
648 uh->busy++;
649 check_unrhdr(uh, __LINE__);
650 return (item);
651 }
652
653 i = item - uh->low - uh->first;
654
655 if (up == NULL) {
656 up = new_unr(uh, p1, p2);
657 up->ptr = NULL;
658 up->len = i;
659 TAILQ_INSERT_TAIL(&uh->head, up, list);
660 up = new_unr(uh, p1, p2);
661 up->ptr = uh;
662 up->len = 1;
663 TAILQ_INSERT_TAIL(&uh->head, up, list);
664 uh->last = uh->high - uh->low - i;
665 uh->busy++;
666 check_unrhdr(uh, __LINE__);
667 return (item);
668 } else {
669 /* Find the item which contains the unit we want to allocate. */
670 TAILQ_FOREACH(up, &uh->head, list) {
671 if (up->len > i)
672 break;
673 i -= up->len;
674 }
675 }
676
677 if (up == NULL) {
678 if (i > 0) {
679 up = new_unr(uh, p1, p2);
680 up->ptr = NULL;
681 up->len = i;
682 TAILQ_INSERT_TAIL(&uh->head, up, list);
683 }
684 up = new_unr(uh, p1, p2);
685 up->ptr = uh;
686 up->len = 1;
687 TAILQ_INSERT_TAIL(&uh->head, up, list);
688 goto done;
689 }
690
691 if (is_bitmap(uh, up)) {
692 ub = up->ptr;
693 if (bit_test(ub->map, i) == 0) {
694 bit_set(ub->map, i);
695 ub->busy++;
696 goto done;
697 } else
698 return (-1);
699 } else if (up->ptr == uh)
700 return (-1);
701
702 KASSERT(up->ptr == NULL,
703 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
704
705 /* Split off the tail end, if any. */
706 tl = up->len - (1 + i);
707 if (tl > 0) {
708 upn = new_unr(uh, p1, p2);
709 upn->ptr = NULL;
710 upn->len = tl;
711 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
712 }
713
714 /* Split off head end, if any */
715 if (i > 0) {
716 upn = new_unr(uh, p1, p2);
717 upn->len = i;
718 upn->ptr = NULL;
719 TAILQ_INSERT_BEFORE(up, upn, list);
720 }
721 up->len = 1;
722 up->ptr = uh;
723
724 done:
725 last = uh->high - uh->low - (item - uh->low);
726 if (uh->last > last)
727 uh->last = last;
728 uh->busy++;
729 collapse_unr(uh, up);
730 check_unrhdr(uh, __LINE__);
731 return (item);
732 }
733
734 int
735 alloc_unr_specific(struct unrhdr *uh, u_int item)
736 {
737 void *p1, *p2;
738 int i;
739
740 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
741
742 p1 = Malloc(sizeof(struct unr));
743 p2 = Malloc(sizeof(struct unr));
744
745 mtx_lock(uh->mtx);
746 i = alloc_unr_specificl(uh, item, &p1, &p2);
747 mtx_unlock(uh->mtx);
748
749 if (p1 != NULL)
750 Free(p1);
751 if (p2 != NULL)
752 Free(p2);
753
754 return (i);
755 }
756
757 /*
758 * Free a unr.
759 *
760 * If we can save unrs by using a bitmap, do so.
761 */
762 static void
763 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
764 {
765 struct unr *up, *upp, *upn;
766 struct unrb *ub;
767 u_int pl;
768
769 KASSERT(item >= uh->low && item <= uh->high,
770 ("UNR: free_unr(%u) out of range [%u...%u]",
771 item, uh->low, uh->high));
772 check_unrhdr(uh, __LINE__);
773 item -= uh->low;
774 upp = TAILQ_FIRST(&uh->head);
775 /*
776 * Freeing in the ideal split case
777 */
778 if (item + 1 == uh->first && upp == NULL) {
779 uh->last++;
780 uh->first--;
781 uh->busy--;
782 check_unrhdr(uh, __LINE__);
783 return;
784 }
785 /*
786 * Freeing in the ->first section. Create a run starting at the
787 * freed item. The code below will subdivide it.
788 */
789 if (item < uh->first) {
790 up = new_unr(uh, p1, p2);
791 up->ptr = uh;
792 up->len = uh->first - item;
793 TAILQ_INSERT_HEAD(&uh->head, up, list);
794 uh->first -= up->len;
795 }
796
797 item -= uh->first;
798
799 /* Find the item which contains the unit we want to free */
800 TAILQ_FOREACH(up, &uh->head, list) {
801 if (up->len > item)
802 break;
803 item -= up->len;
804 }
805
806 /* Handle bitmap items */
807 if (is_bitmap(uh, up)) {
808 ub = up->ptr;
809
810 KASSERT(bit_test(ub->map, item) != 0,
811 ("UNR: Freeing free item %d (bitmap)\n", item));
812 bit_clear(ub->map, item);
813 uh->busy--;
814 ub->busy--;
815 collapse_unr(uh, up);
816 return;
817 }
818
819 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
820
821 /* Just this one left, reap it */
822 if (up->len == 1) {
823 up->ptr = NULL;
824 uh->busy--;
825 collapse_unr(uh, up);
826 return;
827 }
828
829 /* Check if we can shift the item into the previous 'free' run */
830 upp = TAILQ_PREV(up, unrhd, list);
831 if (item == 0 && upp != NULL && upp->ptr == NULL) {
832 upp->len++;
833 up->len--;
834 uh->busy--;
835 collapse_unr(uh, up);
836 return;
837 }
838
839 /* Check if we can shift the item to the next 'free' run */
840 upn = TAILQ_NEXT(up, list);
841 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
842 upn->len++;
843 up->len--;
844 uh->busy--;
845 collapse_unr(uh, up);
846 return;
847 }
848
849 /* Split off the tail end, if any. */
850 pl = up->len - (1 + item);
851 if (pl > 0) {
852 upp = new_unr(uh, p1, p2);
853 upp->ptr = uh;
854 upp->len = pl;
855 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
856 }
857
858 /* Split off head end, if any */
859 if (item > 0) {
860 upp = new_unr(uh, p1, p2);
861 upp->len = item;
862 upp->ptr = uh;
863 TAILQ_INSERT_BEFORE(up, upp, list);
864 }
865 up->len = 1;
866 up->ptr = NULL;
867 uh->busy--;
868 collapse_unr(uh, up);
869 }
870
871 void
872 free_unr(struct unrhdr *uh, u_int item)
873 {
874 void *p1, *p2;
875
876 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
877 p1 = Malloc(sizeof(struct unr));
878 p2 = Malloc(sizeof(struct unr));
879 mtx_lock(uh->mtx);
880 free_unrl(uh, item, &p1, &p2);
881 clean_unrhdrl(uh);
882 mtx_unlock(uh->mtx);
883 if (p1 != NULL)
884 Free(p1);
885 if (p2 != NULL)
886 Free(p2);
887 }
888
889 #ifndef _KERNEL /* USERLAND test driver */
890
891 /*
892 * Simple stochastic test driver for the above functions
893 */
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(%d) [", ub->busy);
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 printf("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 printf("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 printf("F %u\n", i);
967 a[i] = 0;
968 free_unr(uh, i);
969 } else {
970 a[i] = 1;
971 printf("A %d\n", j);
972 }
973 }
974
975 /* Number of unrs to test */
976 #define NN 10000
977
978 int
979 main(int argc __unused, const char **argv __unused)
980 {
981 struct unrhdr *uh;
982 u_int i, x, m, j;
983 char a[NN];
984
985 setbuf(stdout, NULL);
986 uh = new_unrhdr(0, NN - 1, NULL);
987 print_unrhdr(uh);
988
989 memset(a, 0, sizeof a);
990 srandomdev();
991
992 fprintf(stderr, "sizeof(struct unr) %zu\n", sizeof(struct unr));
993 fprintf(stderr, "sizeof(struct unrb) %zu\n", sizeof(struct unrb));
994 fprintf(stderr, "sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
995 fprintf(stderr, "NBITS %d\n", NBITS);
996 x = 1;
997 for (m = 0; m < NN * 100; m++) {
998 j = random();
999 i = (j >> 1) % NN;
1000 #if 0
1001 if (a[i] && (j & 1))
1002 continue;
1003 #endif
1004 if ((random() & 1) != 0)
1005 test_alloc_unr(uh, i, a);
1006 else
1007 test_alloc_unr_specific(uh, i, a);
1008
1009 if (1) /* XXX: change this for detailed debug printout */
1010 print_unrhdr(uh);
1011 check_unrhdr(uh, __LINE__);
1012 }
1013 for (i = 0; i < NN; i++) {
1014 if (a[i]) {
1015 printf("C %u\n", i);
1016 free_unr(uh, i);
1017 print_unrhdr(uh);
1018 }
1019 }
1020 print_unrhdr(uh);
1021 delete_unrhdr(uh);
1022 return (0);
1023 }
1024 #endif
Cache object: ec1d5c0fee90556cca2d31deb8a87f77
|