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