xref: /freebsd/sys/kern/subr_unit.c (revision 59c8e88e72633afbc47a4ace0d2170d00d51f7dc)
1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause
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  *
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 #define	UNR_NO_MTX	((void *)(uintptr_t)-1)
132 
133 struct mtx {
134 	int	state;
135 } unitmtx;
136 
137 static void
138 mtx_lock(struct mtx *mp)
139 {
140 	KASSERT(mp->state == 0, ("mutex already locked"));
141 	mp->state = 1;
142 }
143 
144 static void
145 mtx_unlock(struct mtx *mp)
146 {
147 	KASSERT(mp->state == 1, ("mutex not locked"));
148 	mp->state = 0;
149 }
150 
151 #define MA_OWNED	9
152 
153 static void
154 mtx_assert(struct mtx *mp, int flag)
155 {
156 	if (flag == MA_OWNED) {
157 		KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
158 	}
159 }
160 
161 #define CTASSERT(foo)
162 #define WITNESS_WARN(flags, lock, fmt, ...)	(void)0
163 
164 #endif /* USERLAND */
165 
166 /*
167  * This is our basic building block.
168  *
169  * It can be used in three different ways depending on the value of the ptr
170  * element:
171  *     If ptr is NULL, it represents a run of free items.
172  *     If ptr points to the unrhdr it represents a run of allocated items.
173  *     Otherwise it points to a bitstring of allocated items.
174  *
175  * For runs the len field is the length of the run.
176  * For bitmaps the len field represents the number of allocated items.
177  *
178  * The bitmap is the same size as struct unr to optimize memory management.
179  *
180  * Two special ranges are not covered by unrs:
181  * - at the start of the allocator space, all elements in [low, low + first)
182  *   are allocated;
183  * - at the end of the allocator space, all elements in [high - last, high]
184  *   are free.
185  */
186 struct unr {
187 	TAILQ_ENTRY(unr)	list;
188 	u_int			len;
189 	void			*ptr;
190 };
191 
192 struct unrb {
193 	bitstr_t		map[sizeof(struct unr) / sizeof(bitstr_t)];
194 };
195 
196 CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
197 
198 /* Number of bits we can store in the bitmap */
199 #define NBITS (NBBY * sizeof(((struct unrb *)NULL)->map))
200 
201 static inline bool
202 is_bitmap(struct unrhdr *uh, struct unr *up)
203 {
204 	return (up->ptr != uh && up->ptr != NULL);
205 }
206 
207 /* Is the unrb empty in at least the first len bits? */
208 static inline bool
209 ub_empty(struct unrb *ub, int len) {
210 	int first_set;
211 
212 	bit_ffs(ub->map, len, &first_set);
213 	return (first_set == -1);
214 }
215 
216 /* Is the unrb full?  That is, is the number of set elements equal to len? */
217 static inline bool
218 ub_full(struct unrb *ub, int len)
219 {
220 	int first_clear;
221 
222 	bit_ffc(ub->map, len, &first_clear);
223 	return (first_clear == -1);
224 }
225 
226 /*
227  * start: ipos = -1, upos = NULL;
228  * end:   ipos = -1, upos = uh
229  */
230 struct unrhdr_iter {
231 	struct unrhdr *uh;
232 	int ipos;
233 	int upos_first_item;
234 	void *upos;
235 };
236 
237 void *
238 create_iter_unr(struct unrhdr *uh)
239 {
240 	struct unrhdr_iter *iter;
241 
242 	iter = Malloc(sizeof(*iter));
243 	iter->ipos = -1;
244 	iter->uh = uh;
245 	iter->upos = NULL;
246 	iter->upos_first_item = -1;
247 	return (iter);
248 }
249 
250 static void
251 next_iter_unrl(struct unrhdr *uh, struct unrhdr_iter *iter)
252 {
253 	struct unr *up;
254 	struct unrb *ub;
255 	u_int y;
256 	int c;
257 
258 	if (iter->ipos == -1) {
259 		if (iter->upos == uh)
260 			return;
261 		y = uh->low - 1;
262 		if (uh->first == 0) {
263 			up = TAILQ_FIRST(&uh->head);
264 			if (up == NULL) {
265 				iter->upos = uh;
266 				return;
267 			}
268 			iter->upos = up;
269 			if (up->ptr == NULL)
270 				iter->upos = NULL;
271 			else
272 				iter->upos_first_item = uh->low;
273 		}
274 	} else {
275 		y = iter->ipos;
276 	}
277 
278 	up = iter->upos;
279 
280 	/* Special case for the compacted [low, first) run. */
281 	if (up == NULL) {
282 		if (y + 1 < uh->low + uh->first) {
283 			iter->ipos = y + 1;
284 			return;
285 		}
286 		up = iter->upos = TAILQ_FIRST(&uh->head);
287 		iter->upos_first_item = uh->low + uh->first;
288 	}
289 
290 	for (;;) {
291 		if (y + 1 < iter->upos_first_item + up->len) {
292 			if (up->ptr == uh) {
293 				iter->ipos = y + 1;
294 				return;
295 			} else if (is_bitmap(uh, up)) {
296 				ub = up->ptr;
297 				bit_ffs_at(&ub->map[0],
298 				    y + 1 - iter->upos_first_item,
299 				    up->len, &c);
300 				if (c != -1) {
301 					iter->ipos = iter->upos_first_item + c;
302 					return;
303 				}
304 			}
305 		}
306 		iter->upos_first_item += up->len;
307 		y = iter->upos_first_item - 1;
308 		up = iter->upos = TAILQ_NEXT((struct unr *)iter->upos, list);
309 		if (iter->upos == NULL) {
310 			iter->ipos = -1;
311 			iter->upos = uh;
312 			return;
313 		}
314 	}
315 }
316 
317 /*
318  * returns -1 on end, otherwise the next element
319  */
320 int
321 next_iter_unr(void *handle)
322 {
323 	struct unrhdr *uh;
324 	struct unrhdr_iter *iter;
325 
326 	iter = handle;
327 	uh = iter->uh;
328 	if (uh->mtx != NULL)
329 		mtx_lock(uh->mtx);
330 	next_iter_unrl(uh, iter);
331 	if (uh->mtx != NULL)
332 		mtx_unlock(uh->mtx);
333 	return (iter->ipos);
334 }
335 
336 void
337 free_iter_unr(void *handle)
338 {
339 	Free(handle);
340 }
341 
342 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
343 #ifndef __diagused
344 #define	__diagused
345 #endif
346 
347 /*
348  * Consistency check function.
349  *
350  * Checks the internal consistency as well as we can.
351  *
352  * Called at all boundaries of this API.
353  */
354 static void
355 check_unrhdr(struct unrhdr *uh, int line)
356 {
357 	struct unr *up;
358 	struct unrb *ub;
359 	int w;
360 	u_int y __diagused, z __diagused;
361 
362 	y = uh->first;
363 	z = 0;
364 	TAILQ_FOREACH(up, &uh->head, list) {
365 		z++;
366 		if (is_bitmap(uh, up)) {
367 			ub = up->ptr;
368 			KASSERT (up->len <= NBITS,
369 			    ("UNR inconsistency: len %u max %zd (line %d)\n",
370 			    up->len, NBITS, line));
371 			z++;
372 			w = 0;
373 			bit_count(ub->map, 0, up->len, &w);
374 			y += w;
375 		} else if (up->ptr != NULL)
376 			y += up->len;
377 	}
378 	KASSERT (y == uh->busy,
379 	    ("UNR inconsistency: items %u found %u (line %d)\n",
380 	    uh->busy, y, line));
381 	KASSERT (z == uh->alloc,
382 	    ("UNR inconsistency: chunks %u found %u (line %d)\n",
383 	    uh->alloc, z, line));
384 }
385 
386 #else
387 
388 static __inline void
389 check_unrhdr(struct unrhdr *uh __unused, int line __unused)
390 {
391 
392 }
393 
394 #endif
395 
396 /*
397  * Userland memory management.  Just use calloc and keep track of how
398  * many elements we have allocated for check_unrhdr().
399  */
400 
401 static __inline void *
402 new_unr(struct unrhdr *uh, void **p1, void **p2)
403 {
404 	void *p;
405 
406 	uh->alloc++;
407 	KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
408 	if (*p1 != NULL) {
409 		p = *p1;
410 		*p1 = NULL;
411 		return (p);
412 	} else {
413 		p = *p2;
414 		*p2 = NULL;
415 		return (p);
416 	}
417 }
418 
419 static __inline void
420 delete_unr(struct unrhdr *uh, void *ptr)
421 {
422 	struct unr *up;
423 
424 	uh->alloc--;
425 	up = ptr;
426 	TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
427 }
428 
429 void
430 clean_unrhdrl(struct unrhdr *uh)
431 {
432 	struct unr *up;
433 
434 	if (uh->mtx != NULL)
435 		mtx_assert(uh->mtx, MA_OWNED);
436 	while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
437 		TAILQ_REMOVE(&uh->ppfree, up, list);
438 		if (uh->mtx != NULL)
439 			mtx_unlock(uh->mtx);
440 		Free(up);
441 		if (uh->mtx != NULL)
442 			mtx_lock(uh->mtx);
443 	}
444 
445 }
446 
447 void
448 clean_unrhdr(struct unrhdr *uh)
449 {
450 
451 	if (uh->mtx != NULL)
452 		mtx_lock(uh->mtx);
453 	clean_unrhdrl(uh);
454 	if (uh->mtx != NULL)
455 		mtx_unlock(uh->mtx);
456 }
457 
458 void
459 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
460 {
461 
462 	KASSERT(low >= 0 && low <= high,
463 	    ("UNR: use error: new_unrhdr(%d, %d)", low, high));
464 	if (mutex == UNR_NO_MTX)
465 		uh->mtx = NULL;
466 	else if (mutex != NULL)
467 		uh->mtx = mutex;
468 	else
469 		uh->mtx = &unitmtx;
470 	TAILQ_INIT(&uh->head);
471 	TAILQ_INIT(&uh->ppfree);
472 	uh->low = low;
473 	uh->high = high;
474 	uh->first = 0;
475 	uh->last = 1 + (high - low);
476 	uh->busy = 0;
477 	uh->alloc = 0;
478 	check_unrhdr(uh, __LINE__);
479 }
480 
481 /*
482  * Allocate a new unrheader set.
483  *
484  * Highest and lowest valid values given as parameters.
485  */
486 
487 struct unrhdr *
488 new_unrhdr(int low, int high, struct mtx *mutex)
489 {
490 	struct unrhdr *uh;
491 
492 	uh = Malloc(sizeof *uh);
493 	init_unrhdr(uh, low, high, mutex);
494 	return (uh);
495 }
496 
497 void
498 delete_unrhdr(struct unrhdr *uh)
499 {
500 
501 	check_unrhdr(uh, __LINE__);
502 	KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
503 	KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
504 	KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
505 	    ("unrhdr has postponed item for free"));
506 	Free(uh);
507 }
508 
509 void
510 clear_unrhdr(struct unrhdr *uh)
511 {
512 	struct unr *up, *uq;
513 
514 	KASSERT(TAILQ_EMPTY(&uh->ppfree),
515 	    ("unrhdr has postponed item for free"));
516 	TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {
517 		if (up->ptr != uh) {
518 			Free(up->ptr);
519 		}
520 		Free(up);
521 	}
522 	uh->busy = 0;
523 	uh->alloc = 0;
524 	init_unrhdr(uh, uh->low, uh->high, uh->mtx);
525 
526 	check_unrhdr(uh, __LINE__);
527 }
528 
529 /*
530  * Look for sequence of items which can be combined into a bitmap, if
531  * multiple are present, take the one which saves most memory.
532  *
533  * Return (1) if a sequence was found to indicate that another call
534  * might be able to do more.  Return (0) if we found no suitable sequence.
535  *
536  * NB: called from alloc_unr(), no new memory allocation allowed.
537  */
538 static int
539 optimize_unr(struct unrhdr *uh)
540 {
541 	struct unr *up, *uf, *us;
542 	struct unrb *ub, *ubf;
543 	u_int a, l, ba;
544 
545 	/*
546 	 * Look for the run of items (if any) which when collapsed into
547 	 * a bitmap would save most memory.
548 	 */
549 	us = NULL;
550 	ba = 0;
551 	TAILQ_FOREACH(uf, &uh->head, list) {
552 		if (uf->len >= NBITS)
553 			continue;
554 		a = 1;
555 		if (is_bitmap(uh, uf))
556 			a++;
557 		l = uf->len;
558 		up = uf;
559 		while (1) {
560 			up = TAILQ_NEXT(up, list);
561 			if (up == NULL)
562 				break;
563 			if ((up->len + l) > NBITS)
564 				break;
565 			a++;
566 			if (is_bitmap(uh, up))
567 				a++;
568 			l += up->len;
569 		}
570 		if (a > ba) {
571 			ba = a;
572 			us = uf;
573 		}
574 	}
575 	if (ba < 3)
576 		return (0);
577 
578 	/*
579 	 * If the first element is not a bitmap, make it one.
580 	 * Trying to do so without allocating more memory complicates things
581 	 * a bit
582 	 */
583 	if (!is_bitmap(uh, us)) {
584 		uf = TAILQ_NEXT(us, list);
585 		TAILQ_REMOVE(&uh->head, us, list);
586 		a = us->len;
587 		l = us->ptr == uh ? 1 : 0;
588 		ub = (void *)us;
589 		bit_nclear(ub->map, 0, NBITS - 1);
590 		if (l)
591 			bit_nset(ub->map, 0, a);
592 		if (!is_bitmap(uh, uf)) {
593 			if (uf->ptr == NULL)
594 				bit_nclear(ub->map, a, a + uf->len - 1);
595 			else
596 				bit_nset(ub->map, a, a + uf->len - 1);
597 			uf->ptr = ub;
598 			uf->len += a;
599 			us = uf;
600 		} else {
601 			ubf = uf->ptr;
602 			for (l = 0; l < uf->len; l++, a++) {
603 				if (bit_test(ubf->map, l))
604 					bit_set(ub->map, a);
605 				else
606 					bit_clear(ub->map, a);
607 			}
608 			uf->len = a;
609 			delete_unr(uh, uf->ptr);
610 			uf->ptr = ub;
611 			us = uf;
612 		}
613 	}
614 	ub = us->ptr;
615 	while (1) {
616 		uf = TAILQ_NEXT(us, list);
617 		if (uf == NULL)
618 			return (1);
619 		if (uf->len + us->len > NBITS)
620 			return (1);
621 		if (uf->ptr == NULL) {
622 			bit_nclear(ub->map, us->len, us->len + uf->len - 1);
623 			us->len += uf->len;
624 			TAILQ_REMOVE(&uh->head, uf, list);
625 			delete_unr(uh, uf);
626 		} else if (uf->ptr == uh) {
627 			bit_nset(ub->map, us->len, us->len + uf->len - 1);
628 			us->len += uf->len;
629 			TAILQ_REMOVE(&uh->head, uf, list);
630 			delete_unr(uh, uf);
631 		} else {
632 			ubf = uf->ptr;
633 			for (l = 0; l < uf->len; l++, us->len++) {
634 				if (bit_test(ubf->map, l))
635 					bit_set(ub->map, us->len);
636 				else
637 					bit_clear(ub->map, us->len);
638 			}
639 			TAILQ_REMOVE(&uh->head, uf, list);
640 			delete_unr(uh, ubf);
641 			delete_unr(uh, uf);
642 		}
643 	}
644 }
645 
646 /*
647  * See if a given unr should be collapsed with a neighbor.
648  *
649  * NB: called from alloc_unr(), no new memory allocation allowed.
650  */
651 static void
652 collapse_unr(struct unrhdr *uh, struct unr *up)
653 {
654 	struct unr *upp;
655 	struct unrb *ub;
656 
657 	/* If bitmap is all set or clear, change it to runlength */
658 	if (is_bitmap(uh, up)) {
659 		ub = up->ptr;
660 		if (ub_full(ub, up->len)) {
661 			delete_unr(uh, up->ptr);
662 			up->ptr = uh;
663 		} else if (ub_empty(ub, up->len)) {
664 			delete_unr(uh, up->ptr);
665 			up->ptr = NULL;
666 		}
667 	}
668 
669 	/* If nothing left in runlength, delete it */
670 	if (up->len == 0) {
671 		upp = TAILQ_PREV(up, unrhd, list);
672 		if (upp == NULL)
673 			upp = TAILQ_NEXT(up, list);
674 		TAILQ_REMOVE(&uh->head, up, list);
675 		delete_unr(uh, up);
676 		up = upp;
677 	}
678 
679 	/* If we have "hot-spot" still, merge with neighbor if possible */
680 	if (up != NULL) {
681 		upp = TAILQ_PREV(up, unrhd, list);
682 		if (upp != NULL && up->ptr == upp->ptr) {
683 			up->len += upp->len;
684 			TAILQ_REMOVE(&uh->head, upp, list);
685 			delete_unr(uh, upp);
686 			}
687 		upp = TAILQ_NEXT(up, list);
688 		if (upp != NULL && up->ptr == upp->ptr) {
689 			up->len += upp->len;
690 			TAILQ_REMOVE(&uh->head, upp, list);
691 			delete_unr(uh, upp);
692 		}
693 	}
694 
695 	/* Merge into ->first if possible */
696 	upp = TAILQ_FIRST(&uh->head);
697 	if (upp != NULL && upp->ptr == uh) {
698 		uh->first += upp->len;
699 		TAILQ_REMOVE(&uh->head, upp, list);
700 		delete_unr(uh, upp);
701 		if (up == upp)
702 			up = NULL;
703 	}
704 
705 	/* Merge into ->last if possible */
706 	upp = TAILQ_LAST(&uh->head, unrhd);
707 	if (upp != NULL && upp->ptr == NULL) {
708 		uh->last += upp->len;
709 		TAILQ_REMOVE(&uh->head, upp, list);
710 		delete_unr(uh, upp);
711 		if (up == upp)
712 			up = NULL;
713 	}
714 
715 	/* Try to make bitmaps */
716 	while (optimize_unr(uh))
717 		continue;
718 }
719 
720 /*
721  * Allocate a free unr.
722  */
723 int
724 alloc_unrl(struct unrhdr *uh)
725 {
726 	struct unr *up;
727 	struct unrb *ub;
728 	u_int x;
729 	int y;
730 
731 	if (uh->mtx != NULL)
732 		mtx_assert(uh->mtx, MA_OWNED);
733 	check_unrhdr(uh, __LINE__);
734 	x = uh->low + uh->first;
735 
736 	up = TAILQ_FIRST(&uh->head);
737 
738 	/*
739 	 * If we have an ideal split, just adjust the first+last
740 	 */
741 	if (up == NULL && uh->last > 0) {
742 		uh->first++;
743 		uh->last--;
744 		uh->busy++;
745 		return (x);
746 	}
747 
748 	/*
749 	 * We can always allocate from the first list element, so if we have
750 	 * nothing on the list, we must have run out of unit numbers.
751 	 */
752 	if (up == NULL)
753 		return (-1);
754 
755 	KASSERT(up->ptr != uh, ("UNR first element is allocated"));
756 
757 	if (up->ptr == NULL) {	/* free run */
758 		uh->first++;
759 		up->len--;
760 	} else {		/* bitmap */
761 		ub = up->ptr;
762 		bit_ffc(ub->map, up->len, &y);
763 		KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
764 		bit_set(ub->map, y);
765 		x += y;
766 	}
767 	uh->busy++;
768 	collapse_unr(uh, up);
769 	return (x);
770 }
771 
772 int
773 alloc_unr(struct unrhdr *uh)
774 {
775 	int i;
776 
777 	if (uh->mtx != NULL)
778 		mtx_lock(uh->mtx);
779 	i = alloc_unrl(uh);
780 	clean_unrhdrl(uh);
781 	if (uh->mtx != NULL)
782 		mtx_unlock(uh->mtx);
783 	return (i);
784 }
785 
786 static int
787 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
788 {
789 	struct unr *up, *upn;
790 	struct unrb *ub;
791 	u_int i, last, tl;
792 
793 	if (uh->mtx != NULL)
794 		mtx_assert(uh->mtx, MA_OWNED);
795 
796 	if (item < uh->low + uh->first || item > uh->high)
797 		return (-1);
798 
799 	up = TAILQ_FIRST(&uh->head);
800 	/* Ideal split. */
801 	if (up == NULL && item - uh->low == uh->first) {
802 		uh->first++;
803 		uh->last--;
804 		uh->busy++;
805 		check_unrhdr(uh, __LINE__);
806 		return (item);
807 	}
808 
809 	i = item - uh->low - uh->first;
810 
811 	if (up == NULL) {
812 		up = new_unr(uh, p1, p2);
813 		up->ptr = NULL;
814 		up->len = i;
815 		TAILQ_INSERT_TAIL(&uh->head, up, list);
816 		up = new_unr(uh, p1, p2);
817 		up->ptr = uh;
818 		up->len = 1;
819 		TAILQ_INSERT_TAIL(&uh->head, up, list);
820 		uh->last = uh->high - uh->low - i;
821 		uh->busy++;
822 		check_unrhdr(uh, __LINE__);
823 		return (item);
824 	} else {
825 		/* Find the item which contains the unit we want to allocate. */
826 		TAILQ_FOREACH(up, &uh->head, list) {
827 			if (up->len > i)
828 				break;
829 			i -= up->len;
830 		}
831 	}
832 
833 	if (up == NULL) {
834 		if (i > 0) {
835 			up = new_unr(uh, p1, p2);
836 			up->ptr = NULL;
837 			up->len = i;
838 			TAILQ_INSERT_TAIL(&uh->head, up, list);
839 		}
840 		up = new_unr(uh, p1, p2);
841 		up->ptr = uh;
842 		up->len = 1;
843 		TAILQ_INSERT_TAIL(&uh->head, up, list);
844 		goto done;
845 	}
846 
847 	if (is_bitmap(uh, up)) {
848 		ub = up->ptr;
849 		if (bit_test(ub->map, i) == 0) {
850 			bit_set(ub->map, i);
851 			goto done;
852 		} else
853 			return (-1);
854 	} else if (up->ptr == uh)
855 		return (-1);
856 
857 	KASSERT(up->ptr == NULL,
858 	    ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
859 
860 	/* Split off the tail end, if any. */
861 	tl = up->len - (1 + i);
862 	if (tl > 0) {
863 		upn = new_unr(uh, p1, p2);
864 		upn->ptr = NULL;
865 		upn->len = tl;
866 		TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
867 	}
868 
869 	/* Split off head end, if any */
870 	if (i > 0) {
871 		upn = new_unr(uh, p1, p2);
872 		upn->len = i;
873 		upn->ptr = NULL;
874 		TAILQ_INSERT_BEFORE(up, upn, list);
875 	}
876 	up->len = 1;
877 	up->ptr = uh;
878 
879 done:
880 	last = uh->high - uh->low - (item - uh->low);
881 	if (uh->last > last)
882 		uh->last = last;
883 	uh->busy++;
884 	collapse_unr(uh, up);
885 	check_unrhdr(uh, __LINE__);
886 	return (item);
887 }
888 
889 int
890 alloc_unr_specific(struct unrhdr *uh, u_int item)
891 {
892 	void *p1, *p2;
893 	int i;
894 
895 	WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
896 
897 	p1 = Malloc(sizeof(struct unr));
898 	p2 = Malloc(sizeof(struct unr));
899 
900 	if (uh->mtx != NULL)
901 		mtx_lock(uh->mtx);
902 	i = alloc_unr_specificl(uh, item, &p1, &p2);
903 	if (uh->mtx != NULL)
904 		mtx_unlock(uh->mtx);
905 
906 	if (p1 != NULL)
907 		Free(p1);
908 	if (p2 != NULL)
909 		Free(p2);
910 
911 	return (i);
912 }
913 
914 /*
915  * Free a unr.
916  *
917  * If we can save unrs by using a bitmap, do so.
918  */
919 static void
920 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
921 {
922 	struct unr *up, *upp, *upn;
923 	struct unrb *ub;
924 	u_int pl;
925 
926 	KASSERT(item >= uh->low && item <= uh->high,
927 	    ("UNR: free_unr(%u) out of range [%u...%u]",
928 	     item, uh->low, uh->high));
929 	check_unrhdr(uh, __LINE__);
930 	item -= uh->low;
931 	upp = TAILQ_FIRST(&uh->head);
932 	/*
933 	 * Freeing in the ideal split case
934 	 */
935 	if (item + 1 == uh->first && upp == NULL) {
936 		uh->last++;
937 		uh->first--;
938 		uh->busy--;
939 		check_unrhdr(uh, __LINE__);
940 		return;
941 	}
942 	/*
943  	 * Freeing in the ->first section.  Create a run starting at the
944 	 * freed item.  The code below will subdivide it.
945 	 */
946 	if (item < uh->first) {
947 		up = new_unr(uh, p1, p2);
948 		up->ptr = uh;
949 		up->len = uh->first - item;
950 		TAILQ_INSERT_HEAD(&uh->head, up, list);
951 		uh->first -= up->len;
952 	}
953 
954 	item -= uh->first;
955 
956 	/* Find the item which contains the unit we want to free */
957 	TAILQ_FOREACH(up, &uh->head, list) {
958 		if (up->len > item)
959 			break;
960 		item -= up->len;
961 	}
962 
963 	/* Handle bitmap items */
964 	if (is_bitmap(uh, up)) {
965 		ub = up->ptr;
966 
967 		KASSERT(bit_test(ub->map, item) != 0,
968 		    ("UNR: Freeing free item %d (bitmap)\n", item));
969 		bit_clear(ub->map, item);
970 		uh->busy--;
971 		collapse_unr(uh, up);
972 		return;
973 	}
974 
975 	KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
976 
977 	/* Just this one left, reap it */
978 	if (up->len == 1) {
979 		up->ptr = NULL;
980 		uh->busy--;
981 		collapse_unr(uh, up);
982 		return;
983 	}
984 
985 	/* Check if we can shift the item into the previous 'free' run */
986 	upp = TAILQ_PREV(up, unrhd, list);
987 	if (item == 0 && upp != NULL && upp->ptr == NULL) {
988 		upp->len++;
989 		up->len--;
990 		uh->busy--;
991 		collapse_unr(uh, up);
992 		return;
993 	}
994 
995 	/* Check if we can shift the item to the next 'free' run */
996 	upn = TAILQ_NEXT(up, list);
997 	if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
998 		upn->len++;
999 		up->len--;
1000 		uh->busy--;
1001 		collapse_unr(uh, up);
1002 		return;
1003 	}
1004 
1005 	/* Split off the tail end, if any. */
1006 	pl = up->len - (1 + item);
1007 	if (pl > 0) {
1008 		upp = new_unr(uh, p1, p2);
1009 		upp->ptr = uh;
1010 		upp->len = pl;
1011 		TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
1012 	}
1013 
1014 	/* Split off head end, if any */
1015 	if (item > 0) {
1016 		upp = new_unr(uh, p1, p2);
1017 		upp->len = item;
1018 		upp->ptr = uh;
1019 		TAILQ_INSERT_BEFORE(up, upp, list);
1020 	}
1021 	up->len = 1;
1022 	up->ptr = NULL;
1023 	uh->busy--;
1024 	collapse_unr(uh, up);
1025 }
1026 
1027 void
1028 free_unr(struct unrhdr *uh, u_int item)
1029 {
1030 	void *p1, *p2;
1031 
1032 	WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
1033 	p1 = Malloc(sizeof(struct unr));
1034 	p2 = Malloc(sizeof(struct unr));
1035 	if (uh->mtx != NULL)
1036 		mtx_lock(uh->mtx);
1037 	free_unrl(uh, item, &p1, &p2);
1038 	clean_unrhdrl(uh);
1039 	if (uh->mtx != NULL)
1040 		mtx_unlock(uh->mtx);
1041 	if (p1 != NULL)
1042 		Free(p1);
1043 	if (p2 != NULL)
1044 		Free(p2);
1045 }
1046 
1047 #ifdef _KERNEL
1048 #include "opt_ddb.h"
1049 #ifdef DDB
1050 #include <ddb/ddb.h>
1051 #endif
1052 #endif
1053 
1054 #if (defined(_KERNEL) && defined(DDB)) || !defined(_KERNEL)
1055 
1056 #if !defined(_KERNEL)
1057 #define db_printf printf
1058 #endif
1059 
1060 static void
1061 print_unr(struct unrhdr *uh, struct unr *up)
1062 {
1063 	u_int x;
1064 	struct unrb *ub;
1065 
1066 	db_printf("  %p len = %5u ", up, up->len);
1067 	if (up->ptr == NULL)
1068 		db_printf("free\n");
1069 	else if (up->ptr == uh)
1070 		db_printf("alloc\n");
1071 	else {
1072 		ub = up->ptr;
1073 		db_printf("bitmap [");
1074 		for (x = 0; x < up->len; x++) {
1075 			if (bit_test(ub->map, x))
1076 				db_printf("#");
1077 			else
1078 				db_printf(" ");
1079 		}
1080 		db_printf("]\n");
1081 	}
1082 }
1083 
1084 static void
1085 print_unrhdr(struct unrhdr *uh)
1086 {
1087 	struct unr *up;
1088 	u_int x;
1089 
1090 	db_printf(
1091 	    "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
1092 	    uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
1093 	x = uh->low + uh->first;
1094 	TAILQ_FOREACH(up, &uh->head, list) {
1095 		db_printf("  from = %5u", x);
1096 		print_unr(uh, up);
1097 		if (up->ptr == NULL || up->ptr == uh)
1098 			x += up->len;
1099 		else
1100 			x += NBITS;
1101 	}
1102 }
1103 
1104 #endif
1105 
1106 #if defined(_KERNEL) && defined(DDB)
1107 DB_SHOW_COMMAND(unrhdr, unrhdr_print_unrhdr)
1108 {
1109 	if (!have_addr) {
1110 		db_printf("show unrhdr addr\n");
1111 		return;
1112 	}
1113 
1114 	print_unrhdr((struct unrhdr *)addr);
1115 }
1116 
1117 static void
1118 print_unrhdr_iter(struct unrhdr_iter *iter)
1119 {
1120 	db_printf("iter %p unrhdr %p ipos %d upos %p ufi %d\n",
1121 	    iter, iter->uh, iter->ipos, iter->upos, iter->upos_first_item);
1122 }
1123 
1124 DB_SHOW_COMMAND(unrhdr_iter, unrhdr_print_iter)
1125 {
1126 	if (!have_addr) {
1127 		db_printf("show unrhdr_iter addr\n");
1128 		return;
1129 	}
1130 
1131 	print_unrhdr_iter((struct unrhdr_iter *)addr);
1132 }
1133 #endif
1134 
1135 #ifndef _KERNEL	/* USERLAND test driver */
1136 
1137 /*
1138  * Simple stochastic test driver for the above functions.  The code resides
1139  * here so that it can access static functions and structures.
1140  */
1141 
1142 static bool verbose;
1143 #define VPRINTF(...)	{if (verbose) printf(__VA_ARGS__);}
1144 
1145 static void
1146 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
1147 {
1148 	int j;
1149 
1150 	if (a[i]) {
1151 		VPRINTF("F %u\n", i);
1152 		free_unr(uh, i);
1153 		a[i] = 0;
1154 	} else {
1155 		no_alloc = 1;
1156 		j = alloc_unr(uh);
1157 		if (j != -1) {
1158 			a[j] = 1;
1159 			VPRINTF("A %d\n", j);
1160 		}
1161 		no_alloc = 0;
1162 	}
1163 }
1164 
1165 static void
1166 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
1167 {
1168 	int j;
1169 
1170 	j = alloc_unr_specific(uh, i);
1171 	if (j == -1) {
1172 		VPRINTF("F %u\n", i);
1173 		a[i] = 0;
1174 		free_unr(uh, i);
1175 	} else {
1176 		a[i] = 1;
1177 		VPRINTF("A %d\n", j);
1178 	}
1179 }
1180 
1181 #define	TBASE	7
1182 #define	XSIZE	10
1183 #define	ISIZE	1000
1184 
1185 static int
1186 test_iter_compar(const void *a, const void *b)
1187 {
1188 	return (*(const int *)a - *(const int *)b);
1189 }
1190 
1191 static void
1192 test_iter_fill(int *vals, struct unrhdr *uh, int i, int v, int *res)
1193 {
1194 	int x;
1195 
1196 	vals[i] = v;
1197 	x = alloc_unr_specific(uh, v);
1198 	if (x != v) {
1199 		VPRINTF("alloc_unr_specific failed %d %d\n", x, v);
1200 		*res = 1;
1201 	}
1202 }
1203 
1204 static void
1205 test_iter(void)
1206 {
1207 	struct unrhdr *uh;
1208 	void *ihandle;
1209 	int vals[ISIZE];
1210 	int i, j, v, x, res;
1211 
1212 	res = 0;
1213 	uh = new_unrhdr(TBASE, INT_MAX, NULL);
1214 	for (i = 0; i < XSIZE; i++) {
1215 		vals[i] = i + TBASE;
1216 		x = alloc_unr_specific(uh, i + TBASE);
1217 		if (x != i + TBASE) {
1218 			VPRINTF("alloc_unr_specific failed %d %d\n", x,
1219 			    i + TBASE);
1220 			res = 1;
1221 		}
1222 	}
1223 	for (; i < ISIZE; i++) {
1224 		for (;;) {
1225 again:
1226 			v = arc4random_uniform(INT_MAX);
1227 			if (v < TBASE)
1228 				goto again;
1229 			for (j = 0; j < i; j++) {
1230 				if (v == vals[j] || v + 1 == vals[j])
1231 					goto again;
1232 			}
1233 			break;
1234 		}
1235 		test_iter_fill(vals, uh, i, v, &res);
1236 		i++, v++;
1237 		if (i < ISIZE)
1238 			test_iter_fill(vals, uh, i, v, &res);
1239 	}
1240 	qsort(vals, ISIZE, sizeof(vals[0]), test_iter_compar);
1241 
1242 	ihandle = create_iter_unr(uh);
1243 	i = 0;
1244 	while ((v = next_iter_unr(ihandle)) != -1) {
1245 		if (vals[i] != v) {
1246 			VPRINTF("iter %d: iter %d != val %d\n", i, v, vals[i]);
1247 			if (res == 0) {
1248 				if (verbose)
1249 					print_unrhdr(uh);
1250 				res = 1;
1251 			}
1252 		} else {
1253 			VPRINTF("iter %d: val %d\n", i, v);
1254 		}
1255 		i++;
1256 	}
1257 	free_iter_unr(ihandle);
1258 	clean_unrhdr(uh);
1259 	clear_unrhdr(uh);
1260 	delete_unrhdr(uh);
1261 	exit(res);
1262 }
1263 
1264 static void
1265 usage(char **argv)
1266 {
1267 	printf("%s [-h] [-i] [-r REPETITIONS] [-v]\n", argv[0]);
1268 }
1269 
1270 int
1271 main(int argc, char **argv)
1272 {
1273 	struct unrhdr *uh;
1274 	char *a;
1275 	long count = 10000;	/* Number of unrs to test */
1276 	long reps = 1, m;
1277 	int ch;
1278 	u_int i;
1279 	bool testing_iter;
1280 
1281 	verbose = false;
1282 	testing_iter = false;
1283 
1284 	while ((ch = getopt(argc, argv, "hir:v")) != -1) {
1285 		switch (ch) {
1286 		case 'i':
1287 			testing_iter = true;
1288 			break;
1289 		case 'r':
1290 			errno = 0;
1291 			reps = strtol(optarg, NULL, 0);
1292 			if (errno == ERANGE || errno == EINVAL) {
1293 				usage(argv);
1294 				exit(2);
1295 			}
1296 
1297 			break;
1298 		case 'v':
1299 			verbose = true;
1300 			break;
1301 		case 'h':
1302 		default:
1303 			usage(argv);
1304 			exit(2);
1305 		}
1306 	}
1307 
1308 	setbuf(stdout, NULL);
1309 
1310 	if (testing_iter)
1311 		test_iter();
1312 
1313 	uh = new_unrhdr(0, count - 1, NULL);
1314 	print_unrhdr(uh);
1315 
1316 	a = calloc(count, sizeof(char));
1317 	if (a == NULL)
1318 		err(1, "calloc failed");
1319 
1320 	printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
1321 	printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
1322 	printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
1323 	printf("NBITS %lu\n", (unsigned long)NBITS);
1324 	for (m = 0; m < count * reps; m++) {
1325 		i = arc4random_uniform(count);
1326 #if 0
1327 		if (a[i] && (j & 1))
1328 			continue;
1329 #endif
1330 		if ((arc4random() & 1) != 0)
1331 			test_alloc_unr(uh, i, a);
1332 		else
1333 			test_alloc_unr_specific(uh, i, a);
1334 
1335 		if (verbose)
1336 			print_unrhdr(uh);
1337 		check_unrhdr(uh, __LINE__);
1338 	}
1339 	for (i = 0; i < (u_int)count; i++) {
1340 		if (a[i]) {
1341 			if (verbose) {
1342 				printf("C %u\n", i);
1343 				print_unrhdr(uh);
1344 			}
1345 			free_unr(uh, i);
1346 		}
1347 	}
1348 	print_unrhdr(uh);
1349 	delete_unrhdr(uh);
1350 	free(a);
1351 	return (0);
1352 }
1353 #endif
1354