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/10.3/sys/kern/subr_unit.c 255057 2013-08-30 07:37:45Z kib $
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/types.h>
71 #include <sys/bitstring.h>
72 #include <sys/_unrhdr.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 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
191 /*
192 * Consistency check function.
193 *
194 * Checks the internal consistency as well as we can.
195 *
196 * Called at all boundaries of this API.
197 */
198 static void
199 check_unrhdr(struct unrhdr *uh, int line)
200 {
201 struct unr *up;
202 struct unrb *ub;
203 u_int x, y, z, w;
204
205 y = uh->first;
206 z = 0;
207 TAILQ_FOREACH(up, &uh->head, list) {
208 z++;
209 if (up->ptr != uh && up->ptr != NULL) {
210 ub = up->ptr;
211 KASSERT (up->len <= NBITS,
212 ("UNR inconsistency: len %u max %d (line %d)\n",
213 up->len, NBITS, line));
214 z++;
215 w = 0;
216 for (x = 0; x < up->len; x++)
217 if (bit_test(ub->map, x))
218 w++;
219 KASSERT (w == ub->busy,
220 ("UNR inconsistency: busy %u found %u (line %d)\n",
221 ub->busy, w, line));
222 y += w;
223 } else if (up->ptr != NULL)
224 y += up->len;
225 }
226 KASSERT (y == uh->busy,
227 ("UNR inconsistency: items %u found %u (line %d)\n",
228 uh->busy, y, line));
229 KASSERT (z == uh->alloc,
230 ("UNR inconsistency: chunks %u found %u (line %d)\n",
231 uh->alloc, z, line));
232 }
233
234 #else
235
236 static __inline void
237 check_unrhdr(struct unrhdr *uh, int line)
238 {
239
240 }
241
242 #endif
243
244
245 /*
246 * Userland memory management. Just use calloc and keep track of how
247 * many elements we have allocated for check_unrhdr().
248 */
249
250 static __inline void *
251 new_unr(struct unrhdr *uh, void **p1, void **p2)
252 {
253 void *p;
254
255 uh->alloc++;
256 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
257 if (*p1 != NULL) {
258 p = *p1;
259 *p1 = NULL;
260 return (p);
261 } else {
262 p = *p2;
263 *p2 = NULL;
264 return (p);
265 }
266 }
267
268 static __inline void
269 delete_unr(struct unrhdr *uh, void *ptr)
270 {
271 struct unr *up;
272
273 uh->alloc--;
274 up = ptr;
275 TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
276 }
277
278 void
279 clean_unrhdrl(struct unrhdr *uh)
280 {
281 struct unr *up;
282
283 mtx_assert(uh->mtx, MA_OWNED);
284 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
285 TAILQ_REMOVE(&uh->ppfree, up, list);
286 mtx_unlock(uh->mtx);
287 Free(up);
288 mtx_lock(uh->mtx);
289 }
290
291 }
292
293 void
294 clean_unrhdr(struct unrhdr *uh)
295 {
296
297 mtx_lock(uh->mtx);
298 clean_unrhdrl(uh);
299 mtx_unlock(uh->mtx);
300 }
301
302 void
303 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
304 {
305
306 KASSERT(low >= 0 && low <= high,
307 ("UNR: use error: new_unrhdr(%d, %d)", low, high));
308 if (mutex != NULL)
309 uh->mtx = mutex;
310 else
311 uh->mtx = &unitmtx;
312 TAILQ_INIT(&uh->head);
313 TAILQ_INIT(&uh->ppfree);
314 uh->low = low;
315 uh->high = high;
316 uh->first = 0;
317 uh->last = 1 + (high - low);
318 check_unrhdr(uh, __LINE__);
319 }
320
321 /*
322 * Allocate a new unrheader set.
323 *
324 * Highest and lowest valid values given as parameters.
325 */
326
327 struct unrhdr *
328 new_unrhdr(int low, int high, struct mtx *mutex)
329 {
330 struct unrhdr *uh;
331
332 uh = Malloc(sizeof *uh);
333 init_unrhdr(uh, low, high, mutex);
334 return (uh);
335 }
336
337 void
338 delete_unrhdr(struct unrhdr *uh)
339 {
340
341 check_unrhdr(uh, __LINE__);
342 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
343 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
344 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
345 ("unrhdr has postponed item for free"));
346 Free(uh);
347 }
348
349 static __inline int
350 is_bitmap(struct unrhdr *uh, struct unr *up)
351 {
352 return (up->ptr != uh && up->ptr != NULL);
353 }
354
355 /*
356 * Look for sequence of items which can be combined into a bitmap, if
357 * multiple are present, take the one which saves most memory.
358 *
359 * Return (1) if a sequence was found to indicate that another call
360 * might be able to do more. Return (0) if we found no suitable sequence.
361 *
362 * NB: called from alloc_unr(), no new memory allocation allowed.
363 */
364 static int
365 optimize_unr(struct unrhdr *uh)
366 {
367 struct unr *up, *uf, *us;
368 struct unrb *ub, *ubf;
369 u_int a, l, ba;
370
371 /*
372 * Look for the run of items (if any) which when collapsed into
373 * a bitmap would save most memory.
374 */
375 us = NULL;
376 ba = 0;
377 TAILQ_FOREACH(uf, &uh->head, list) {
378 if (uf->len >= NBITS)
379 continue;
380 a = 1;
381 if (is_bitmap(uh, uf))
382 a++;
383 l = uf->len;
384 up = uf;
385 while (1) {
386 up = TAILQ_NEXT(up, list);
387 if (up == NULL)
388 break;
389 if ((up->len + l) > NBITS)
390 break;
391 a++;
392 if (is_bitmap(uh, up))
393 a++;
394 l += up->len;
395 }
396 if (a > ba) {
397 ba = a;
398 us = uf;
399 }
400 }
401 if (ba < 3)
402 return (0);
403
404 /*
405 * If the first element is not a bitmap, make it one.
406 * Trying to do so without allocating more memory complicates things
407 * a bit
408 */
409 if (!is_bitmap(uh, us)) {
410 uf = TAILQ_NEXT(us, list);
411 TAILQ_REMOVE(&uh->head, us, list);
412 a = us->len;
413 l = us->ptr == uh ? 1 : 0;
414 ub = (void *)us;
415 ub->busy = 0;
416 if (l) {
417 bit_nset(ub->map, 0, a);
418 ub->busy += a;
419 } else {
420 bit_nclear(ub->map, 0, a);
421 }
422 if (!is_bitmap(uh, uf)) {
423 if (uf->ptr == NULL) {
424 bit_nclear(ub->map, a, a + uf->len - 1);
425 } else {
426 bit_nset(ub->map, a, a + uf->len - 1);
427 ub->busy += uf->len;
428 }
429 uf->ptr = ub;
430 uf->len += a;
431 us = uf;
432 } else {
433 ubf = uf->ptr;
434 for (l = 0; l < uf->len; l++, a++) {
435 if (bit_test(ubf->map, l)) {
436 bit_set(ub->map, a);
437 ub->busy++;
438 } else {
439 bit_clear(ub->map, a);
440 }
441 }
442 uf->len = a;
443 delete_unr(uh, uf->ptr);
444 uf->ptr = ub;
445 us = uf;
446 }
447 }
448 ub = us->ptr;
449 while (1) {
450 uf = TAILQ_NEXT(us, list);
451 if (uf == NULL)
452 return (1);
453 if (uf->len + us->len > NBITS)
454 return (1);
455 if (uf->ptr == NULL) {
456 bit_nclear(ub->map, us->len, us->len + uf->len - 1);
457 us->len += uf->len;
458 TAILQ_REMOVE(&uh->head, uf, list);
459 delete_unr(uh, uf);
460 } else if (uf->ptr == uh) {
461 bit_nset(ub->map, us->len, us->len + uf->len - 1);
462 ub->busy += uf->len;
463 us->len += uf->len;
464 TAILQ_REMOVE(&uh->head, uf, list);
465 delete_unr(uh, uf);
466 } else {
467 ubf = uf->ptr;
468 for (l = 0; l < uf->len; l++, us->len++) {
469 if (bit_test(ubf->map, l)) {
470 bit_set(ub->map, us->len);
471 ub->busy++;
472 } else {
473 bit_clear(ub->map, us->len);
474 }
475 }
476 TAILQ_REMOVE(&uh->head, uf, list);
477 delete_unr(uh, ubf);
478 delete_unr(uh, uf);
479 }
480 }
481 }
482
483 /*
484 * See if a given unr should be collapsed with a neighbor.
485 *
486 * NB: called from alloc_unr(), no new memory allocation allowed.
487 */
488 static void
489 collapse_unr(struct unrhdr *uh, struct unr *up)
490 {
491 struct unr *upp;
492 struct unrb *ub;
493
494 /* If bitmap is all set or clear, change it to runlength */
495 if (is_bitmap(uh, up)) {
496 ub = up->ptr;
497 if (ub->busy == up->len) {
498 delete_unr(uh, up->ptr);
499 up->ptr = uh;
500 } else if (ub->busy == 0) {
501 delete_unr(uh, up->ptr);
502 up->ptr = NULL;
503 }
504 }
505
506 /* If nothing left in runlength, delete it */
507 if (up->len == 0) {
508 upp = TAILQ_PREV(up, unrhd, list);
509 if (upp == NULL)
510 upp = TAILQ_NEXT(up, list);
511 TAILQ_REMOVE(&uh->head, up, list);
512 delete_unr(uh, up);
513 up = upp;
514 }
515
516 /* If we have "hot-spot" still, merge with neighbor if possible */
517 if (up != NULL) {
518 upp = TAILQ_PREV(up, unrhd, list);
519 if (upp != NULL && up->ptr == upp->ptr) {
520 up->len += upp->len;
521 TAILQ_REMOVE(&uh->head, upp, list);
522 delete_unr(uh, upp);
523 }
524 upp = TAILQ_NEXT(up, list);
525 if (upp != NULL && up->ptr == upp->ptr) {
526 up->len += upp->len;
527 TAILQ_REMOVE(&uh->head, upp, list);
528 delete_unr(uh, upp);
529 }
530 }
531
532 /* Merge into ->first if possible */
533 upp = TAILQ_FIRST(&uh->head);
534 if (upp != NULL && upp->ptr == uh) {
535 uh->first += upp->len;
536 TAILQ_REMOVE(&uh->head, upp, list);
537 delete_unr(uh, upp);
538 if (up == upp)
539 up = NULL;
540 }
541
542 /* Merge into ->last if possible */
543 upp = TAILQ_LAST(&uh->head, unrhd);
544 if (upp != NULL && upp->ptr == NULL) {
545 uh->last += upp->len;
546 TAILQ_REMOVE(&uh->head, upp, list);
547 delete_unr(uh, upp);
548 if (up == upp)
549 up = NULL;
550 }
551
552 /* Try to make bitmaps */
553 while (optimize_unr(uh))
554 continue;
555 }
556
557 /*
558 * Allocate a free unr.
559 */
560 int
561 alloc_unrl(struct unrhdr *uh)
562 {
563 struct unr *up;
564 struct unrb *ub;
565 u_int x;
566 int y;
567
568 mtx_assert(uh->mtx, MA_OWNED);
569 check_unrhdr(uh, __LINE__);
570 x = uh->low + uh->first;
571
572 up = TAILQ_FIRST(&uh->head);
573
574 /*
575 * If we have an ideal split, just adjust the first+last
576 */
577 if (up == NULL && uh->last > 0) {
578 uh->first++;
579 uh->last--;
580 uh->busy++;
581 return (x);
582 }
583
584 /*
585 * We can always allocate from the first list element, so if we have
586 * nothing on the list, we must have run out of unit numbers.
587 */
588 if (up == NULL)
589 return (-1);
590
591 KASSERT(up->ptr != uh, ("UNR first element is allocated"));
592
593 if (up->ptr == NULL) { /* free run */
594 uh->first++;
595 up->len--;
596 } else { /* bitmap */
597 ub = up->ptr;
598 KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
599 bit_ffc(ub->map, up->len, &y);
600 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
601 bit_set(ub->map, y);
602 ub->busy++;
603 x += y;
604 }
605 uh->busy++;
606 collapse_unr(uh, up);
607 return (x);
608 }
609
610 int
611 alloc_unr(struct unrhdr *uh)
612 {
613 int i;
614
615 mtx_lock(uh->mtx);
616 i = alloc_unrl(uh);
617 clean_unrhdrl(uh);
618 mtx_unlock(uh->mtx);
619 return (i);
620 }
621
622 static int
623 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
624 {
625 struct unr *up, *upn;
626 struct unrb *ub;
627 u_int i, last, tl;
628
629 mtx_assert(uh->mtx, MA_OWNED);
630
631 if (item < uh->low + uh->first || item > uh->high)
632 return (-1);
633
634 up = TAILQ_FIRST(&uh->head);
635 /* Ideal split. */
636 if (up == NULL && item - uh->low == uh->first) {
637 uh->first++;
638 uh->last--;
639 uh->busy++;
640 check_unrhdr(uh, __LINE__);
641 return (item);
642 }
643
644 i = item - uh->low - uh->first;
645
646 if (up == NULL) {
647 up = new_unr(uh, p1, p2);
648 up->ptr = NULL;
649 up->len = i;
650 TAILQ_INSERT_TAIL(&uh->head, up, list);
651 up = new_unr(uh, p1, p2);
652 up->ptr = uh;
653 up->len = 1;
654 TAILQ_INSERT_TAIL(&uh->head, up, list);
655 uh->last = uh->high - uh->low - i;
656 uh->busy++;
657 check_unrhdr(uh, __LINE__);
658 return (item);
659 } else {
660 /* Find the item which contains the unit we want to allocate. */
661 TAILQ_FOREACH(up, &uh->head, list) {
662 if (up->len > i)
663 break;
664 i -= up->len;
665 }
666 }
667
668 if (up == NULL) {
669 if (i > 0) {
670 up = new_unr(uh, p1, p2);
671 up->ptr = NULL;
672 up->len = i;
673 TAILQ_INSERT_TAIL(&uh->head, up, list);
674 }
675 up = new_unr(uh, p1, p2);
676 up->ptr = uh;
677 up->len = 1;
678 TAILQ_INSERT_TAIL(&uh->head, up, list);
679 goto done;
680 }
681
682 if (is_bitmap(uh, up)) {
683 ub = up->ptr;
684 if (bit_test(ub->map, i) == 0) {
685 bit_set(ub->map, i);
686 ub->busy++;
687 goto done;
688 } else
689 return (-1);
690 } else if (up->ptr == uh)
691 return (-1);
692
693 KASSERT(up->ptr == NULL,
694 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
695
696 /* Split off the tail end, if any. */
697 tl = up->len - (1 + i);
698 if (tl > 0) {
699 upn = new_unr(uh, p1, p2);
700 upn->ptr = NULL;
701 upn->len = tl;
702 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
703 }
704
705 /* Split off head end, if any */
706 if (i > 0) {
707 upn = new_unr(uh, p1, p2);
708 upn->len = i;
709 upn->ptr = NULL;
710 TAILQ_INSERT_BEFORE(up, upn, list);
711 }
712 up->len = 1;
713 up->ptr = uh;
714
715 done:
716 last = uh->high - uh->low - (item - uh->low);
717 if (uh->last > last)
718 uh->last = last;
719 uh->busy++;
720 collapse_unr(uh, up);
721 check_unrhdr(uh, __LINE__);
722 return (item);
723 }
724
725 int
726 alloc_unr_specific(struct unrhdr *uh, u_int item)
727 {
728 void *p1, *p2;
729 int i;
730
731 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
732
733 p1 = Malloc(sizeof(struct unr));
734 p2 = Malloc(sizeof(struct unr));
735
736 mtx_lock(uh->mtx);
737 i = alloc_unr_specificl(uh, item, &p1, &p2);
738 mtx_unlock(uh->mtx);
739
740 if (p1 != NULL)
741 Free(p1);
742 if (p2 != NULL)
743 Free(p2);
744
745 return (i);
746 }
747
748 /*
749 * Free a unr.
750 *
751 * If we can save unrs by using a bitmap, do so.
752 */
753 static void
754 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
755 {
756 struct unr *up, *upp, *upn;
757 struct unrb *ub;
758 u_int pl;
759
760 KASSERT(item >= uh->low && item <= uh->high,
761 ("UNR: free_unr(%u) out of range [%u...%u]",
762 item, uh->low, uh->high));
763 check_unrhdr(uh, __LINE__);
764 item -= uh->low;
765 upp = TAILQ_FIRST(&uh->head);
766 /*
767 * Freeing in the ideal split case
768 */
769 if (item + 1 == uh->first && upp == NULL) {
770 uh->last++;
771 uh->first--;
772 uh->busy--;
773 check_unrhdr(uh, __LINE__);
774 return;
775 }
776 /*
777 * Freeing in the ->first section. Create a run starting at the
778 * freed item. The code below will subdivide it.
779 */
780 if (item < uh->first) {
781 up = new_unr(uh, p1, p2);
782 up->ptr = uh;
783 up->len = uh->first - item;
784 TAILQ_INSERT_HEAD(&uh->head, up, list);
785 uh->first -= up->len;
786 }
787
788 item -= uh->first;
789
790 /* Find the item which contains the unit we want to free */
791 TAILQ_FOREACH(up, &uh->head, list) {
792 if (up->len > item)
793 break;
794 item -= up->len;
795 }
796
797 /* Handle bitmap items */
798 if (is_bitmap(uh, up)) {
799 ub = up->ptr;
800
801 KASSERT(bit_test(ub->map, item) != 0,
802 ("UNR: Freeing free item %d (bitmap)\n", item));
803 bit_clear(ub->map, item);
804 uh->busy--;
805 ub->busy--;
806 collapse_unr(uh, up);
807 return;
808 }
809
810 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
811
812 /* Just this one left, reap it */
813 if (up->len == 1) {
814 up->ptr = NULL;
815 uh->busy--;
816 collapse_unr(uh, up);
817 return;
818 }
819
820 /* Check if we can shift the item into the previous 'free' run */
821 upp = TAILQ_PREV(up, unrhd, list);
822 if (item == 0 && upp != NULL && upp->ptr == NULL) {
823 upp->len++;
824 up->len--;
825 uh->busy--;
826 collapse_unr(uh, up);
827 return;
828 }
829
830 /* Check if we can shift the item to the next 'free' run */
831 upn = TAILQ_NEXT(up, list);
832 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
833 upn->len++;
834 up->len--;
835 uh->busy--;
836 collapse_unr(uh, up);
837 return;
838 }
839
840 /* Split off the tail end, if any. */
841 pl = up->len - (1 + item);
842 if (pl > 0) {
843 upp = new_unr(uh, p1, p2);
844 upp->ptr = uh;
845 upp->len = pl;
846 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
847 }
848
849 /* Split off head end, if any */
850 if (item > 0) {
851 upp = new_unr(uh, p1, p2);
852 upp->len = item;
853 upp->ptr = uh;
854 TAILQ_INSERT_BEFORE(up, upp, list);
855 }
856 up->len = 1;
857 up->ptr = NULL;
858 uh->busy--;
859 collapse_unr(uh, up);
860 }
861
862 void
863 free_unr(struct unrhdr *uh, u_int item)
864 {
865 void *p1, *p2;
866
867 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
868 p1 = Malloc(sizeof(struct unr));
869 p2 = Malloc(sizeof(struct unr));
870 mtx_lock(uh->mtx);
871 free_unrl(uh, item, &p1, &p2);
872 clean_unrhdrl(uh);
873 mtx_unlock(uh->mtx);
874 if (p1 != NULL)
875 Free(p1);
876 if (p2 != NULL)
877 Free(p2);
878 }
879
880 #ifndef _KERNEL /* USERLAND test driver */
881
882 /*
883 * Simple stochastic test driver for the above functions
884 */
885
886 static void
887 print_unr(struct unrhdr *uh, struct unr *up)
888 {
889 u_int x;
890 struct unrb *ub;
891
892 printf(" %p len = %5u ", up, up->len);
893 if (up->ptr == NULL)
894 printf("free\n");
895 else if (up->ptr == uh)
896 printf("alloc\n");
897 else {
898 ub = up->ptr;
899 printf("bitmap(%d) [", ub->busy);
900 for (x = 0; x < up->len; x++) {
901 if (bit_test(ub->map, x))
902 printf("#");
903 else
904 printf(" ");
905 }
906 printf("]\n");
907 }
908 }
909
910 static void
911 print_unrhdr(struct unrhdr *uh)
912 {
913 struct unr *up;
914 u_int x;
915
916 printf(
917 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
918 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
919 x = uh->low + uh->first;
920 TAILQ_FOREACH(up, &uh->head, list) {
921 printf(" from = %5u", x);
922 print_unr(uh, up);
923 if (up->ptr == NULL || up->ptr == uh)
924 x += up->len;
925 else
926 x += NBITS;
927 }
928 }
929
930 static void
931 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
932 {
933 int j;
934
935 if (a[i]) {
936 printf("F %u\n", i);
937 free_unr(uh, i);
938 a[i] = 0;
939 } else {
940 no_alloc = 1;
941 j = alloc_unr(uh);
942 if (j != -1) {
943 a[j] = 1;
944 printf("A %d\n", j);
945 }
946 no_alloc = 0;
947 }
948 }
949
950 static void
951 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
952 {
953 int j;
954
955 j = alloc_unr_specific(uh, i);
956 if (j == -1) {
957 printf("F %u\n", i);
958 a[i] = 0;
959 free_unr(uh, i);
960 } else {
961 a[i] = 1;
962 printf("A %d\n", j);
963 }
964 }
965
966 /* Number of unrs to test */
967 #define NN 10000
968
969 int
970 main(int argc __unused, const char **argv __unused)
971 {
972 struct unrhdr *uh;
973 u_int i, x, m, j;
974 char a[NN];
975
976 setbuf(stdout, NULL);
977 uh = new_unrhdr(0, NN - 1, NULL);
978 print_unrhdr(uh);
979
980 memset(a, 0, sizeof a);
981 srandomdev();
982
983 fprintf(stderr, "sizeof(struct unr) %zu\n", sizeof(struct unr));
984 fprintf(stderr, "sizeof(struct unrb) %zu\n", sizeof(struct unrb));
985 fprintf(stderr, "sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
986 fprintf(stderr, "NBITS %d\n", NBITS);
987 x = 1;
988 for (m = 0; m < NN * 100; m++) {
989 j = random();
990 i = (j >> 1) % NN;
991 #if 0
992 if (a[i] && (j & 1))
993 continue;
994 #endif
995 if ((random() & 1) != 0)
996 test_alloc_unr(uh, i, a);
997 else
998 test_alloc_unr_specific(uh, i, a);
999
1000 if (1) /* XXX: change this for detailed debug printout */
1001 print_unrhdr(uh);
1002 check_unrhdr(uh, __LINE__);
1003 }
1004 for (i = 0; i < NN; i++) {
1005 if (a[i]) {
1006 printf("C %u\n", i);
1007 free_unr(uh, i);
1008 print_unrhdr(uh);
1009 }
1010 }
1011 print_unrhdr(uh);
1012 delete_unrhdr(uh);
1013 return (0);
1014 }
1015 #endif
Cache object: 89896f71b1b97b679e72a6ef5d627afd
|