xref: /freebsd/sys/kern/subr_unit.c (revision 333dcaa4981d495bc1606a3bdf7445be56a451d5)
1f6bde1fdSPoul-Henning Kamp /*-
2f6bde1fdSPoul-Henning Kamp  * Copyright (c) 2004 Poul-Henning Kamp
3f6bde1fdSPoul-Henning Kamp  * All rights reserved.
4f6bde1fdSPoul-Henning Kamp  *
5f6bde1fdSPoul-Henning Kamp  * Redistribution and use in source and binary forms, with or without
6f6bde1fdSPoul-Henning Kamp  * modification, are permitted provided that the following conditions
7f6bde1fdSPoul-Henning Kamp  * are met:
8f6bde1fdSPoul-Henning Kamp  * 1. Redistributions of source code must retain the above copyright
9f6bde1fdSPoul-Henning Kamp  *    notice, this list of conditions and the following disclaimer.
10f6bde1fdSPoul-Henning Kamp  * 2. Redistributions in binary form must reproduce the above copyright
11f6bde1fdSPoul-Henning Kamp  *    notice, this list of conditions and the following disclaimer in the
12f6bde1fdSPoul-Henning Kamp  *    documentation and/or other materials provided with the distribution.
13f6bde1fdSPoul-Henning Kamp  *
14f6bde1fdSPoul-Henning Kamp  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15f6bde1fdSPoul-Henning Kamp  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16f6bde1fdSPoul-Henning Kamp  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17f6bde1fdSPoul-Henning Kamp  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18f6bde1fdSPoul-Henning Kamp  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19f6bde1fdSPoul-Henning Kamp  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20f6bde1fdSPoul-Henning Kamp  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21f6bde1fdSPoul-Henning Kamp  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22f6bde1fdSPoul-Henning Kamp  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23f6bde1fdSPoul-Henning Kamp  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24f6bde1fdSPoul-Henning Kamp  * SUCH DAMAGE.
25f6bde1fdSPoul-Henning Kamp  *
26f6bde1fdSPoul-Henning Kamp  * $FreeBSD$
27d9a54d5cSPoul-Henning Kamp  *
28d9a54d5cSPoul-Henning Kamp  *
29d9a54d5cSPoul-Henning Kamp  * Unit number allocation functions.
30f6bde1fdSPoul-Henning Kamp  *
31f6bde1fdSPoul-Henning Kamp  * These functions implement a mixed run-length/bitmap management of unit
32d9a54d5cSPoul-Henning Kamp  * number spaces in a very memory efficient manner.
33f6bde1fdSPoul-Henning Kamp  *
34d9a54d5cSPoul-Henning Kamp  * Allocation policy is always lowest free number first.
35f6bde1fdSPoul-Henning Kamp  *
36d9a54d5cSPoul-Henning Kamp  * A return value of -1 signals that no more unit numbers are available.
37f6bde1fdSPoul-Henning Kamp  *
38d9a54d5cSPoul-Henning Kamp  * There is no cost associated with the range of unitnumbers, so unless
39d9a54d5cSPoul-Henning Kamp  * the resource really is finite, specify INT_MAX to new_unrhdr() and
40d9a54d5cSPoul-Henning Kamp  * forget about checking the return value.
41f6bde1fdSPoul-Henning Kamp  *
42d9a54d5cSPoul-Henning Kamp  * If a mutex is not provided when the unit number space is created, a
43d9a54d5cSPoul-Henning Kamp  * default global mutex is used.  The advantage to passing a mutex in, is
446bccea7cSRebecca Cran  * that the alloc_unrl() function can be called with the mutex already
45d9a54d5cSPoul-Henning Kamp  * held (it will not be released by alloc_unrl()).
46d9a54d5cSPoul-Henning Kamp  *
47d9a54d5cSPoul-Henning Kamp  * The allocation function alloc_unr{l}() never sleeps (but it may block on
48d9a54d5cSPoul-Henning Kamp  * the mutex of course).
49d9a54d5cSPoul-Henning Kamp  *
50d9a54d5cSPoul-Henning Kamp  * Freeing a unit number may require allocating memory, and can therefore
51d9a54d5cSPoul-Henning Kamp  * sleep so the free_unr() function does not come in a pre-locked variant.
52f6bde1fdSPoul-Henning Kamp  *
53f6bde1fdSPoul-Henning Kamp  * A userland test program is included.
54f6bde1fdSPoul-Henning Kamp  *
556bccea7cSRebecca Cran  * Memory usage is a very complex function of the exact allocation
56d9a54d5cSPoul-Henning Kamp  * pattern, but always very compact:
57d9a54d5cSPoul-Henning Kamp  *    * For the very typical case where a single unbroken run of unit
58d9a54d5cSPoul-Henning Kamp  *      numbers are allocated 44 bytes are used on i386.
59d9a54d5cSPoul-Henning Kamp  *    * For a unit number space of 1000 units and the random pattern
60d9a54d5cSPoul-Henning Kamp  *      in the usermode test program included, the worst case usage
61d9a54d5cSPoul-Henning Kamp  *	was 252 bytes on i386 for 500 allocated and 500 free units.
62d9a54d5cSPoul-Henning Kamp  *    * For a unit number space of 10000 units and the random pattern
63d9a54d5cSPoul-Henning Kamp  *      in the usermode test program included, the worst case usage
64d9a54d5cSPoul-Henning Kamp  *	was 798 bytes on i386 for 5000 allocated and 5000 free units.
65d9a54d5cSPoul-Henning Kamp  *    * The worst case is where every other unit number is allocated and
6696240c89SEitan Adler  *	the rest are free.  In that case 44 + N/4 bytes are used where
67d9a54d5cSPoul-Henning Kamp  *	N is the number of the highest unit allocated.
68f6bde1fdSPoul-Henning Kamp  */
69f6bde1fdSPoul-Henning Kamp 
708907f744SAlan Somers #include <sys/param.h>
71f6bde1fdSPoul-Henning Kamp #include <sys/types.h>
72dc872d46SKonstantin Belousov #include <sys/_unrhdr.h>
73f6bde1fdSPoul-Henning Kamp 
74f6bde1fdSPoul-Henning Kamp #ifdef _KERNEL
75f6bde1fdSPoul-Henning Kamp 
76794277daSAlan Somers #include <sys/bitstring.h>
77f6bde1fdSPoul-Henning Kamp #include <sys/malloc.h>
78f6bde1fdSPoul-Henning Kamp #include <sys/kernel.h>
79f6bde1fdSPoul-Henning Kamp #include <sys/systm.h>
80d9a54d5cSPoul-Henning Kamp #include <sys/limits.h>
81d9a54d5cSPoul-Henning Kamp #include <sys/lock.h>
82d9a54d5cSPoul-Henning Kamp #include <sys/mutex.h>
83f6bde1fdSPoul-Henning Kamp 
84f6bde1fdSPoul-Henning Kamp /*
85f6bde1fdSPoul-Henning Kamp  * In theory it would be smarter to allocate the individual blocks
86f6bde1fdSPoul-Henning Kamp  * with the zone allocator, but at this time the expectation is that
87f6bde1fdSPoul-Henning Kamp  * there will typically not even be enough allocations to fill a single
88f6bde1fdSPoul-Henning Kamp  * page, so we stick with malloc for now.
89f6bde1fdSPoul-Henning Kamp  */
90f6bde1fdSPoul-Henning Kamp static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation");
91f6bde1fdSPoul-Henning Kamp 
92f6bde1fdSPoul-Henning Kamp #define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
93f6bde1fdSPoul-Henning Kamp #define Free(foo) free(foo, M_UNIT)
94f6bde1fdSPoul-Henning Kamp 
95d9a54d5cSPoul-Henning Kamp static struct mtx unitmtx;
96d9a54d5cSPoul-Henning Kamp 
97d9a54d5cSPoul-Henning Kamp MTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF);
98d9a54d5cSPoul-Henning Kamp 
99f6bde1fdSPoul-Henning Kamp #else /* ...USERLAND */
100f6bde1fdSPoul-Henning Kamp 
101794277daSAlan Somers #include <bitstring.h>
102794277daSAlan Somers #include <err.h>
103794277daSAlan Somers #include <errno.h>
104794277daSAlan Somers #include <getopt.h>
105794277daSAlan Somers #include <stdbool.h>
106f6bde1fdSPoul-Henning Kamp #include <stdio.h>
107f6bde1fdSPoul-Henning Kamp #include <stdlib.h>
108d9a54d5cSPoul-Henning Kamp #include <string.h>
109f6bde1fdSPoul-Henning Kamp 
110f6bde1fdSPoul-Henning Kamp #define KASSERT(cond, arg) \
111f6bde1fdSPoul-Henning Kamp 	do { \
112f6bde1fdSPoul-Henning Kamp 		if (!(cond)) { \
113f6bde1fdSPoul-Henning Kamp 			printf arg; \
114d9a54d5cSPoul-Henning Kamp 			abort(); \
115f6bde1fdSPoul-Henning Kamp 		} \
116f6bde1fdSPoul-Henning Kamp 	} while (0)
117f6bde1fdSPoul-Henning Kamp 
118d9a54d5cSPoul-Henning Kamp static int no_alloc;
119d9a54d5cSPoul-Henning Kamp #define Malloc(foo) _Malloc(foo, __LINE__)
120d9a54d5cSPoul-Henning Kamp static void *
121d9a54d5cSPoul-Henning Kamp _Malloc(size_t foo, int line)
122d9a54d5cSPoul-Henning Kamp {
123d9a54d5cSPoul-Henning Kamp 
124d9a54d5cSPoul-Henning Kamp 	KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
125d9a54d5cSPoul-Henning Kamp 	return (calloc(foo, 1));
126d9a54d5cSPoul-Henning Kamp }
127f6bde1fdSPoul-Henning Kamp #define Free(foo) free(foo)
128f6bde1fdSPoul-Henning Kamp 
129d9a54d5cSPoul-Henning Kamp struct unrhdr;
130d9a54d5cSPoul-Henning Kamp 
131d9a54d5cSPoul-Henning Kamp 
132d9a54d5cSPoul-Henning Kamp struct mtx {
133d9a54d5cSPoul-Henning Kamp 	int	state;
134d9a54d5cSPoul-Henning Kamp } unitmtx;
135d9a54d5cSPoul-Henning Kamp 
136d9a54d5cSPoul-Henning Kamp static void
137d9a54d5cSPoul-Henning Kamp mtx_lock(struct mtx *mp)
138d9a54d5cSPoul-Henning Kamp {
139d9a54d5cSPoul-Henning Kamp 	KASSERT(mp->state == 0, ("mutex already locked"));
140d9a54d5cSPoul-Henning Kamp 	mp->state = 1;
141d9a54d5cSPoul-Henning Kamp }
142d9a54d5cSPoul-Henning Kamp 
143d9a54d5cSPoul-Henning Kamp static void
144d9a54d5cSPoul-Henning Kamp mtx_unlock(struct mtx *mp)
145d9a54d5cSPoul-Henning Kamp {
146d9a54d5cSPoul-Henning Kamp 	KASSERT(mp->state == 1, ("mutex not locked"));
147d9a54d5cSPoul-Henning Kamp 	mp->state = 0;
148d9a54d5cSPoul-Henning Kamp }
149d9a54d5cSPoul-Henning Kamp 
150d9a54d5cSPoul-Henning Kamp #define MA_OWNED	9
151d9a54d5cSPoul-Henning Kamp 
152d9a54d5cSPoul-Henning Kamp static void
153d9a54d5cSPoul-Henning Kamp mtx_assert(struct mtx *mp, int flag)
154d9a54d5cSPoul-Henning Kamp {
155d9a54d5cSPoul-Henning Kamp 	if (flag == MA_OWNED) {
156d9a54d5cSPoul-Henning Kamp 		KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
157d9a54d5cSPoul-Henning Kamp 	}
158d9a54d5cSPoul-Henning Kamp }
159d9a54d5cSPoul-Henning Kamp 
160d9a54d5cSPoul-Henning Kamp #define CTASSERT(foo)
16124e8eaf1SJaakko Heinonen #define WITNESS_WARN(flags, lock, fmt, ...)	(void)0
162d9a54d5cSPoul-Henning Kamp 
163d9a54d5cSPoul-Henning Kamp #endif /* USERLAND */
164f6bde1fdSPoul-Henning Kamp 
165f6bde1fdSPoul-Henning Kamp /*
166f6bde1fdSPoul-Henning Kamp  * This is our basic building block.
167f6bde1fdSPoul-Henning Kamp  *
168f6bde1fdSPoul-Henning Kamp  * It can be used in three different ways depending on the value of the ptr
169f6bde1fdSPoul-Henning Kamp  * element:
170f6bde1fdSPoul-Henning Kamp  *     If ptr is NULL, it represents a run of free items.
171f6bde1fdSPoul-Henning Kamp  *     If ptr points to the unrhdr it represents a run of allocated items.
1728907f744SAlan Somers  *     Otherwise it points to a bitstring of allocated items.
173f6bde1fdSPoul-Henning Kamp  *
174f6bde1fdSPoul-Henning Kamp  * For runs the len field is the length of the run.
175f6bde1fdSPoul-Henning Kamp  * For bitmaps the len field represents the number of allocated items.
176f6bde1fdSPoul-Henning Kamp  *
177f6bde1fdSPoul-Henning Kamp  * The bitmap is the same size as struct unr to optimize memory management.
178f6bde1fdSPoul-Henning Kamp  */
179f6bde1fdSPoul-Henning Kamp struct unr {
180f6bde1fdSPoul-Henning Kamp 	TAILQ_ENTRY(unr)	list;
181f6bde1fdSPoul-Henning Kamp 	u_int			len;
182f6bde1fdSPoul-Henning Kamp 	void			*ptr;
183f6bde1fdSPoul-Henning Kamp };
184f6bde1fdSPoul-Henning Kamp 
185d9a54d5cSPoul-Henning Kamp struct unrb {
1868907f744SAlan Somers 	bitstr_t		map[sizeof(struct unr) / sizeof(bitstr_t)];
187d9a54d5cSPoul-Henning Kamp };
188d9a54d5cSPoul-Henning Kamp 
1898907f744SAlan Somers CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
190d9a54d5cSPoul-Henning Kamp 
1918907f744SAlan Somers /* Number of bits we can store in the bitmap */
1928907f744SAlan Somers #define NBITS (8 * sizeof(((struct unrb*)NULL)->map))
1938907f744SAlan Somers 
1948907f744SAlan Somers /* Is the unrb empty in at least the first len bits? */
1958907f744SAlan Somers static inline bool
1968907f744SAlan Somers ub_empty(struct unrb *ub, int len) {
1978907f744SAlan Somers 	int first_set;
1988907f744SAlan Somers 
1998907f744SAlan Somers 	bit_ffs(ub->map, len, &first_set);
2008907f744SAlan Somers 	return (first_set == -1);
2018907f744SAlan Somers }
2028907f744SAlan Somers 
2038907f744SAlan Somers /* Is the unrb full?  That is, is the number of set elements equal to len? */
2048907f744SAlan Somers static inline bool
2058907f744SAlan Somers ub_full(struct unrb *ub, int len)
2068907f744SAlan Somers {
2078907f744SAlan Somers 	int first_clear;
2088907f744SAlan Somers 
2098907f744SAlan Somers 	bit_ffc(ub->map, len, &first_clear);
2108907f744SAlan Somers 	return (first_clear == -1);
2118907f744SAlan Somers }
2128907f744SAlan Somers 
213f6bde1fdSPoul-Henning Kamp 
214f6bde1fdSPoul-Henning Kamp #if defined(DIAGNOSTIC) || !defined(_KERNEL)
215f6bde1fdSPoul-Henning Kamp /*
216f6bde1fdSPoul-Henning Kamp  * Consistency check function.
217f6bde1fdSPoul-Henning Kamp  *
218f6bde1fdSPoul-Henning Kamp  * Checks the internal consistency as well as we can.
219f6bde1fdSPoul-Henning Kamp  *
220f6bde1fdSPoul-Henning Kamp  * Called at all boundaries of this API.
221f6bde1fdSPoul-Henning Kamp  */
222f6bde1fdSPoul-Henning Kamp static void
223f6bde1fdSPoul-Henning Kamp check_unrhdr(struct unrhdr *uh, int line)
224f6bde1fdSPoul-Henning Kamp {
225f6bde1fdSPoul-Henning Kamp 	struct unr *up;
226d9a54d5cSPoul-Henning Kamp 	struct unrb *ub;
2271b82e02fSAlan Somers 	int w;
2281b82e02fSAlan Somers 	u_int y, z;
229f6bde1fdSPoul-Henning Kamp 
230d9a54d5cSPoul-Henning Kamp 	y = uh->first;
231f6bde1fdSPoul-Henning Kamp 	z = 0;
232f6bde1fdSPoul-Henning Kamp 	TAILQ_FOREACH(up, &uh->head, list) {
233f6bde1fdSPoul-Henning Kamp 		z++;
234f6bde1fdSPoul-Henning Kamp 		if (up->ptr != uh && up->ptr != NULL) {
235d9a54d5cSPoul-Henning Kamp 			ub = up->ptr;
236d9a54d5cSPoul-Henning Kamp 			KASSERT (up->len <= NBITS,
2378907f744SAlan Somers 			    ("UNR inconsistency: len %u max %zd (line %d)\n",
238d9a54d5cSPoul-Henning Kamp 			    up->len, NBITS, line));
239f6bde1fdSPoul-Henning Kamp 			z++;
240f6bde1fdSPoul-Henning Kamp 			w = 0;
2411b82e02fSAlan Somers 			bit_count(ub->map, 0, up->len, &w);
242d9a54d5cSPoul-Henning Kamp 			y += w;
243d9a54d5cSPoul-Henning Kamp 		} else if (up->ptr != NULL)
244f6bde1fdSPoul-Henning Kamp 			y += up->len;
245f6bde1fdSPoul-Henning Kamp 	}
246f6bde1fdSPoul-Henning Kamp 	KASSERT (y == uh->busy,
247f6bde1fdSPoul-Henning Kamp 	    ("UNR inconsistency: items %u found %u (line %d)\n",
248f6bde1fdSPoul-Henning Kamp 	    uh->busy, y, line));
249f6bde1fdSPoul-Henning Kamp 	KASSERT (z == uh->alloc,
250f6bde1fdSPoul-Henning Kamp 	    ("UNR inconsistency: chunks %u found %u (line %d)\n",
251f6bde1fdSPoul-Henning Kamp 	    uh->alloc, z, line));
252f6bde1fdSPoul-Henning Kamp }
253f6bde1fdSPoul-Henning Kamp 
254f6bde1fdSPoul-Henning Kamp #else
255f6bde1fdSPoul-Henning Kamp 
256f6bde1fdSPoul-Henning Kamp static __inline void
2578907f744SAlan Somers check_unrhdr(struct unrhdr *uh __unused, int line __unused)
258f6bde1fdSPoul-Henning Kamp {
259f6bde1fdSPoul-Henning Kamp 
260f6bde1fdSPoul-Henning Kamp }
261f6bde1fdSPoul-Henning Kamp 
262f6bde1fdSPoul-Henning Kamp #endif
263f6bde1fdSPoul-Henning Kamp 
264f6bde1fdSPoul-Henning Kamp 
265f6bde1fdSPoul-Henning Kamp /*
266f6bde1fdSPoul-Henning Kamp  * Userland memory management.  Just use calloc and keep track of how
267f6bde1fdSPoul-Henning Kamp  * many elements we have allocated for check_unrhdr().
268f6bde1fdSPoul-Henning Kamp  */
269f6bde1fdSPoul-Henning Kamp 
270f6bde1fdSPoul-Henning Kamp static __inline void *
271d9a54d5cSPoul-Henning Kamp new_unr(struct unrhdr *uh, void **p1, void **p2)
272f6bde1fdSPoul-Henning Kamp {
273d9a54d5cSPoul-Henning Kamp 	void *p;
274f6bde1fdSPoul-Henning Kamp 
275d9a54d5cSPoul-Henning Kamp 	uh->alloc++;
276d9a54d5cSPoul-Henning Kamp 	KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
277d9a54d5cSPoul-Henning Kamp 	if (*p1 != NULL) {
278d9a54d5cSPoul-Henning Kamp 		p = *p1;
279d9a54d5cSPoul-Henning Kamp 		*p1 = NULL;
280d9a54d5cSPoul-Henning Kamp 		return (p);
281d9a54d5cSPoul-Henning Kamp 	} else {
282d9a54d5cSPoul-Henning Kamp 		p = *p2;
283d9a54d5cSPoul-Henning Kamp 		*p2 = NULL;
284d9a54d5cSPoul-Henning Kamp 		return (p);
285d9a54d5cSPoul-Henning Kamp 	}
286f6bde1fdSPoul-Henning Kamp }
287f6bde1fdSPoul-Henning Kamp 
288f6bde1fdSPoul-Henning Kamp static __inline void
289f6bde1fdSPoul-Henning Kamp delete_unr(struct unrhdr *uh, void *ptr)
290f6bde1fdSPoul-Henning Kamp {
29109828ba9SKonstantin Belousov 	struct unr *up;
292d9a54d5cSPoul-Henning Kamp 
293f6bde1fdSPoul-Henning Kamp 	uh->alloc--;
29409828ba9SKonstantin Belousov 	up = ptr;
29509828ba9SKonstantin Belousov 	TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
29609828ba9SKonstantin Belousov }
29709828ba9SKonstantin Belousov 
29809828ba9SKonstantin Belousov void
29909828ba9SKonstantin Belousov clean_unrhdrl(struct unrhdr *uh)
30009828ba9SKonstantin Belousov {
30109828ba9SKonstantin Belousov 	struct unr *up;
30209828ba9SKonstantin Belousov 
30309828ba9SKonstantin Belousov 	mtx_assert(uh->mtx, MA_OWNED);
30409828ba9SKonstantin Belousov 	while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
30509828ba9SKonstantin Belousov 		TAILQ_REMOVE(&uh->ppfree, up, list);
30609828ba9SKonstantin Belousov 		mtx_unlock(uh->mtx);
30709828ba9SKonstantin Belousov 		Free(up);
30809828ba9SKonstantin Belousov 		mtx_lock(uh->mtx);
30909828ba9SKonstantin Belousov 	}
31009828ba9SKonstantin Belousov 
31109828ba9SKonstantin Belousov }
31209828ba9SKonstantin Belousov 
31309828ba9SKonstantin Belousov void
31409828ba9SKonstantin Belousov clean_unrhdr(struct unrhdr *uh)
31509828ba9SKonstantin Belousov {
31609828ba9SKonstantin Belousov 
31709828ba9SKonstantin Belousov 	mtx_lock(uh->mtx);
31809828ba9SKonstantin Belousov 	clean_unrhdrl(uh);
31909828ba9SKonstantin Belousov 	mtx_unlock(uh->mtx);
320f6bde1fdSPoul-Henning Kamp }
321f6bde1fdSPoul-Henning Kamp 
322dc872d46SKonstantin Belousov void
323dc872d46SKonstantin Belousov init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
324f6bde1fdSPoul-Henning Kamp {
325f6bde1fdSPoul-Henning Kamp 
326831aa555SJaakko Heinonen 	KASSERT(low >= 0 && low <= high,
327501812f2SJaakko Heinonen 	    ("UNR: use error: new_unrhdr(%d, %d)", low, high));
328d9a54d5cSPoul-Henning Kamp 	if (mutex != NULL)
329d9a54d5cSPoul-Henning Kamp 		uh->mtx = mutex;
330d9a54d5cSPoul-Henning Kamp 	else
331d9a54d5cSPoul-Henning Kamp 		uh->mtx = &unitmtx;
332f6bde1fdSPoul-Henning Kamp 	TAILQ_INIT(&uh->head);
33309828ba9SKonstantin Belousov 	TAILQ_INIT(&uh->ppfree);
334f6bde1fdSPoul-Henning Kamp 	uh->low = low;
335f6bde1fdSPoul-Henning Kamp 	uh->high = high;
336d9a54d5cSPoul-Henning Kamp 	uh->first = 0;
337d9a54d5cSPoul-Henning Kamp 	uh->last = 1 + (high - low);
338f6bde1fdSPoul-Henning Kamp 	check_unrhdr(uh, __LINE__);
339dc872d46SKonstantin Belousov }
340dc872d46SKonstantin Belousov 
341dc872d46SKonstantin Belousov /*
342dc872d46SKonstantin Belousov  * Allocate a new unrheader set.
343dc872d46SKonstantin Belousov  *
344dc872d46SKonstantin Belousov  * Highest and lowest valid values given as parameters.
345dc872d46SKonstantin Belousov  */
346dc872d46SKonstantin Belousov 
347dc872d46SKonstantin Belousov struct unrhdr *
348dc872d46SKonstantin Belousov new_unrhdr(int low, int high, struct mtx *mutex)
349dc872d46SKonstantin Belousov {
350dc872d46SKonstantin Belousov 	struct unrhdr *uh;
351dc872d46SKonstantin Belousov 
352dc872d46SKonstantin Belousov 	uh = Malloc(sizeof *uh);
353dc872d46SKonstantin Belousov 	init_unrhdr(uh, low, high, mutex);
354f6bde1fdSPoul-Henning Kamp 	return (uh);
355f6bde1fdSPoul-Henning Kamp }
356f6bde1fdSPoul-Henning Kamp 
357e4fea39eSPoul-Henning Kamp void
358e4fea39eSPoul-Henning Kamp delete_unrhdr(struct unrhdr *uh)
359e4fea39eSPoul-Henning Kamp {
360e4fea39eSPoul-Henning Kamp 
361d9a54d5cSPoul-Henning Kamp 	check_unrhdr(uh, __LINE__);
362e4fea39eSPoul-Henning Kamp 	KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
363e4fea39eSPoul-Henning Kamp 	KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
36409828ba9SKonstantin Belousov 	KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
36509828ba9SKonstantin Belousov 	    ("unrhdr has postponed item for free"));
366e4fea39eSPoul-Henning Kamp 	Free(uh);
367e4fea39eSPoul-Henning Kamp }
368e4fea39eSPoul-Henning Kamp 
369*333dcaa4SMatt Joras void
370*333dcaa4SMatt Joras clear_unrhdr(struct unrhdr *uh)
371*333dcaa4SMatt Joras {
372*333dcaa4SMatt Joras 	struct unr *up, *uq;
373*333dcaa4SMatt Joras 
374*333dcaa4SMatt Joras 	KASSERT(TAILQ_EMPTY(&uh->ppfree),
375*333dcaa4SMatt Joras 	    ("unrhdr has postponed item for free"));
376*333dcaa4SMatt Joras 	up = TAILQ_FIRST(&uh->head);
377*333dcaa4SMatt Joras 	while (up != NULL) {
378*333dcaa4SMatt Joras 		uq = TAILQ_NEXT(up, list);
379*333dcaa4SMatt Joras 		if (up->ptr != uh) {
380*333dcaa4SMatt Joras 			Free(up->ptr);
381*333dcaa4SMatt Joras 		}
382*333dcaa4SMatt Joras 		Free(up);
383*333dcaa4SMatt Joras 		up = uq;
384*333dcaa4SMatt Joras 	}
385*333dcaa4SMatt Joras 	TAILQ_INIT(&uh->head);
386*333dcaa4SMatt Joras 	uh->busy = 0;
387*333dcaa4SMatt Joras 	uh->alloc = 0;
388*333dcaa4SMatt Joras }
389*333dcaa4SMatt Joras 
390d9a54d5cSPoul-Henning Kamp static __inline int
391d9a54d5cSPoul-Henning Kamp is_bitmap(struct unrhdr *uh, struct unr *up)
392d9a54d5cSPoul-Henning Kamp {
393d9a54d5cSPoul-Henning Kamp 	return (up->ptr != uh && up->ptr != NULL);
394d9a54d5cSPoul-Henning Kamp }
395d9a54d5cSPoul-Henning Kamp 
396f6bde1fdSPoul-Henning Kamp /*
397d9a54d5cSPoul-Henning Kamp  * Look for sequence of items which can be combined into a bitmap, if
398d9a54d5cSPoul-Henning Kamp  * multiple are present, take the one which saves most memory.
399d9a54d5cSPoul-Henning Kamp  *
400d9a54d5cSPoul-Henning Kamp  * Return (1) if a sequence was found to indicate that another call
401d9a54d5cSPoul-Henning Kamp  * might be able to do more.  Return (0) if we found no suitable sequence.
402d9a54d5cSPoul-Henning Kamp  *
403d9a54d5cSPoul-Henning Kamp  * NB: called from alloc_unr(), no new memory allocation allowed.
404d9a54d5cSPoul-Henning Kamp  */
405d9a54d5cSPoul-Henning Kamp static int
406d9a54d5cSPoul-Henning Kamp optimize_unr(struct unrhdr *uh)
407d9a54d5cSPoul-Henning Kamp {
408d9a54d5cSPoul-Henning Kamp 	struct unr *up, *uf, *us;
409d9a54d5cSPoul-Henning Kamp 	struct unrb *ub, *ubf;
410d9a54d5cSPoul-Henning Kamp 	u_int a, l, ba;
411d9a54d5cSPoul-Henning Kamp 
412d9a54d5cSPoul-Henning Kamp 	/*
413d9a54d5cSPoul-Henning Kamp 	 * Look for the run of items (if any) which when collapsed into
414d9a54d5cSPoul-Henning Kamp 	 * a bitmap would save most memory.
415d9a54d5cSPoul-Henning Kamp 	 */
416d9a54d5cSPoul-Henning Kamp 	us = NULL;
417d9a54d5cSPoul-Henning Kamp 	ba = 0;
418d9a54d5cSPoul-Henning Kamp 	TAILQ_FOREACH(uf, &uh->head, list) {
419d9a54d5cSPoul-Henning Kamp 		if (uf->len >= NBITS)
420d9a54d5cSPoul-Henning Kamp 			continue;
421d9a54d5cSPoul-Henning Kamp 		a = 1;
422d9a54d5cSPoul-Henning Kamp 		if (is_bitmap(uh, uf))
423d9a54d5cSPoul-Henning Kamp 			a++;
424d9a54d5cSPoul-Henning Kamp 		l = uf->len;
425d9a54d5cSPoul-Henning Kamp 		up = uf;
426d9a54d5cSPoul-Henning Kamp 		while (1) {
427d9a54d5cSPoul-Henning Kamp 			up = TAILQ_NEXT(up, list);
428d9a54d5cSPoul-Henning Kamp 			if (up == NULL)
429d9a54d5cSPoul-Henning Kamp 				break;
430d9a54d5cSPoul-Henning Kamp 			if ((up->len + l) > NBITS)
431d9a54d5cSPoul-Henning Kamp 				break;
432d9a54d5cSPoul-Henning Kamp 			a++;
433d9a54d5cSPoul-Henning Kamp 			if (is_bitmap(uh, up))
434d9a54d5cSPoul-Henning Kamp 				a++;
435d9a54d5cSPoul-Henning Kamp 			l += up->len;
436d9a54d5cSPoul-Henning Kamp 		}
437d9a54d5cSPoul-Henning Kamp 		if (a > ba) {
438d9a54d5cSPoul-Henning Kamp 			ba = a;
439d9a54d5cSPoul-Henning Kamp 			us = uf;
440d9a54d5cSPoul-Henning Kamp 		}
441d9a54d5cSPoul-Henning Kamp 	}
442d9a54d5cSPoul-Henning Kamp 	if (ba < 3)
443d9a54d5cSPoul-Henning Kamp 		return (0);
444d9a54d5cSPoul-Henning Kamp 
445d9a54d5cSPoul-Henning Kamp 	/*
446d9a54d5cSPoul-Henning Kamp 	 * If the first element is not a bitmap, make it one.
447d9a54d5cSPoul-Henning Kamp 	 * Trying to do so without allocating more memory complicates things
448d9a54d5cSPoul-Henning Kamp 	 * a bit
449d9a54d5cSPoul-Henning Kamp 	 */
450d9a54d5cSPoul-Henning Kamp 	if (!is_bitmap(uh, us)) {
451d9a54d5cSPoul-Henning Kamp 		uf = TAILQ_NEXT(us, list);
452d9a54d5cSPoul-Henning Kamp 		TAILQ_REMOVE(&uh->head, us, list);
453d9a54d5cSPoul-Henning Kamp 		a = us->len;
454d9a54d5cSPoul-Henning Kamp 		l = us->ptr == uh ? 1 : 0;
455d9a54d5cSPoul-Henning Kamp 		ub = (void *)us;
4568907f744SAlan Somers 		bit_nclear(ub->map, 0, NBITS - 1);
4578907f744SAlan Somers 		if (l)
458d9a54d5cSPoul-Henning Kamp 			bit_nset(ub->map, 0, a);
459d9a54d5cSPoul-Henning Kamp 		if (!is_bitmap(uh, uf)) {
4608907f744SAlan Somers 			if (uf->ptr == NULL)
461d9a54d5cSPoul-Henning Kamp 				bit_nclear(ub->map, a, a + uf->len - 1);
4628907f744SAlan Somers 			else
463d9a54d5cSPoul-Henning Kamp 				bit_nset(ub->map, a, a + uf->len - 1);
464d9a54d5cSPoul-Henning Kamp 			uf->ptr = ub;
465d9a54d5cSPoul-Henning Kamp 			uf->len += a;
466d9a54d5cSPoul-Henning Kamp 			us = uf;
467d9a54d5cSPoul-Henning Kamp 		} else {
468d9a54d5cSPoul-Henning Kamp 			ubf = uf->ptr;
469d9a54d5cSPoul-Henning Kamp 			for (l = 0; l < uf->len; l++, a++) {
4708907f744SAlan Somers 				if (bit_test(ubf->map, l))
471d9a54d5cSPoul-Henning Kamp 					bit_set(ub->map, a);
4728907f744SAlan Somers 				else
473d9a54d5cSPoul-Henning Kamp 					bit_clear(ub->map, a);
474d9a54d5cSPoul-Henning Kamp 			}
475d9a54d5cSPoul-Henning Kamp 			uf->len = a;
476d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, uf->ptr);
477d9a54d5cSPoul-Henning Kamp 			uf->ptr = ub;
478d9a54d5cSPoul-Henning Kamp 			us = uf;
479d9a54d5cSPoul-Henning Kamp 		}
480d9a54d5cSPoul-Henning Kamp 	}
481d9a54d5cSPoul-Henning Kamp 	ub = us->ptr;
482d9a54d5cSPoul-Henning Kamp 	while (1) {
483d9a54d5cSPoul-Henning Kamp 		uf = TAILQ_NEXT(us, list);
484d9a54d5cSPoul-Henning Kamp 		if (uf == NULL)
485d9a54d5cSPoul-Henning Kamp 			return (1);
486d9a54d5cSPoul-Henning Kamp 		if (uf->len + us->len > NBITS)
487d9a54d5cSPoul-Henning Kamp 			return (1);
488d9a54d5cSPoul-Henning Kamp 		if (uf->ptr == NULL) {
489d9a54d5cSPoul-Henning Kamp 			bit_nclear(ub->map, us->len, us->len + uf->len - 1);
490d9a54d5cSPoul-Henning Kamp 			us->len += uf->len;
491d9a54d5cSPoul-Henning Kamp 			TAILQ_REMOVE(&uh->head, uf, list);
492d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, uf);
493d9a54d5cSPoul-Henning Kamp 		} else if (uf->ptr == uh) {
494d9a54d5cSPoul-Henning Kamp 			bit_nset(ub->map, us->len, us->len + uf->len - 1);
495d9a54d5cSPoul-Henning Kamp 			us->len += uf->len;
496d9a54d5cSPoul-Henning Kamp 			TAILQ_REMOVE(&uh->head, uf, list);
497d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, uf);
498d9a54d5cSPoul-Henning Kamp 		} else {
499d9a54d5cSPoul-Henning Kamp 			ubf = uf->ptr;
500d9a54d5cSPoul-Henning Kamp 			for (l = 0; l < uf->len; l++, us->len++) {
5018907f744SAlan Somers 				if (bit_test(ubf->map, l))
502d9a54d5cSPoul-Henning Kamp 					bit_set(ub->map, us->len);
5038907f744SAlan Somers 				else
504d9a54d5cSPoul-Henning Kamp 					bit_clear(ub->map, us->len);
505d9a54d5cSPoul-Henning Kamp 			}
506d9a54d5cSPoul-Henning Kamp 			TAILQ_REMOVE(&uh->head, uf, list);
507d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, ubf);
508d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, uf);
509d9a54d5cSPoul-Henning Kamp 		}
510d9a54d5cSPoul-Henning Kamp 	}
511d9a54d5cSPoul-Henning Kamp }
512d9a54d5cSPoul-Henning Kamp 
513d9a54d5cSPoul-Henning Kamp /*
514d9a54d5cSPoul-Henning Kamp  * See if a given unr should be collapsed with a neighbor.
515d9a54d5cSPoul-Henning Kamp  *
516d9a54d5cSPoul-Henning Kamp  * NB: called from alloc_unr(), no new memory allocation allowed.
517f6bde1fdSPoul-Henning Kamp  */
518f6bde1fdSPoul-Henning Kamp static void
519f6bde1fdSPoul-Henning Kamp collapse_unr(struct unrhdr *uh, struct unr *up)
520f6bde1fdSPoul-Henning Kamp {
521f6bde1fdSPoul-Henning Kamp 	struct unr *upp;
522d9a54d5cSPoul-Henning Kamp 	struct unrb *ub;
523f6bde1fdSPoul-Henning Kamp 
524d9a54d5cSPoul-Henning Kamp 	/* If bitmap is all set or clear, change it to runlength */
525d9a54d5cSPoul-Henning Kamp 	if (is_bitmap(uh, up)) {
526d9a54d5cSPoul-Henning Kamp 		ub = up->ptr;
5278907f744SAlan Somers 		if (ub_full(ub, up->len)) {
528d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, up->ptr);
529d9a54d5cSPoul-Henning Kamp 			up->ptr = uh;
5308907f744SAlan Somers 		} else if (ub_empty(ub, up->len)) {
531d9a54d5cSPoul-Henning Kamp 			delete_unr(uh, up->ptr);
532d9a54d5cSPoul-Henning Kamp 			up->ptr = NULL;
533d9a54d5cSPoul-Henning Kamp 		}
534d9a54d5cSPoul-Henning Kamp 	}
535d9a54d5cSPoul-Henning Kamp 
536d9a54d5cSPoul-Henning Kamp 	/* If nothing left in runlength, delete it */
537d9a54d5cSPoul-Henning Kamp 	if (up->len == 0) {
538d9a54d5cSPoul-Henning Kamp 		upp = TAILQ_PREV(up, unrhd, list);
539d9a54d5cSPoul-Henning Kamp 		if (upp == NULL)
540d9a54d5cSPoul-Henning Kamp 			upp = TAILQ_NEXT(up, list);
541d9a54d5cSPoul-Henning Kamp 		TAILQ_REMOVE(&uh->head, up, list);
542d9a54d5cSPoul-Henning Kamp 		delete_unr(uh, up);
543d9a54d5cSPoul-Henning Kamp 		up = upp;
544d9a54d5cSPoul-Henning Kamp 	}
545d9a54d5cSPoul-Henning Kamp 
546d9a54d5cSPoul-Henning Kamp 	/* If we have "hot-spot" still, merge with neighbor if possible */
547d9a54d5cSPoul-Henning Kamp 	if (up != NULL) {
548f6bde1fdSPoul-Henning Kamp 		upp = TAILQ_PREV(up, unrhd, list);
549f6bde1fdSPoul-Henning Kamp 		if (upp != NULL && up->ptr == upp->ptr) {
550f6bde1fdSPoul-Henning Kamp 			up->len += upp->len;
551f6bde1fdSPoul-Henning Kamp 			TAILQ_REMOVE(&uh->head, upp, list);
552f6bde1fdSPoul-Henning Kamp 			delete_unr(uh, upp);
553f6bde1fdSPoul-Henning Kamp 			}
554f6bde1fdSPoul-Henning Kamp 		upp = TAILQ_NEXT(up, list);
555f6bde1fdSPoul-Henning Kamp 		if (upp != NULL && up->ptr == upp->ptr) {
556f6bde1fdSPoul-Henning Kamp 			up->len += upp->len;
557f6bde1fdSPoul-Henning Kamp 			TAILQ_REMOVE(&uh->head, upp, list);
558f6bde1fdSPoul-Henning Kamp 			delete_unr(uh, upp);
559f6bde1fdSPoul-Henning Kamp 		}
560f6bde1fdSPoul-Henning Kamp 	}
561f6bde1fdSPoul-Henning Kamp 
562d9a54d5cSPoul-Henning Kamp 	/* Merge into ->first if possible */
563d9a54d5cSPoul-Henning Kamp 	upp = TAILQ_FIRST(&uh->head);
564d9a54d5cSPoul-Henning Kamp 	if (upp != NULL && upp->ptr == uh) {
565d9a54d5cSPoul-Henning Kamp 		uh->first += upp->len;
566d9a54d5cSPoul-Henning Kamp 		TAILQ_REMOVE(&uh->head, upp, list);
567d9a54d5cSPoul-Henning Kamp 		delete_unr(uh, upp);
568d9a54d5cSPoul-Henning Kamp 		if (up == upp)
569d9a54d5cSPoul-Henning Kamp 			up = NULL;
570d9a54d5cSPoul-Henning Kamp 	}
571d9a54d5cSPoul-Henning Kamp 
572d9a54d5cSPoul-Henning Kamp 	/* Merge into ->last if possible */
573d9a54d5cSPoul-Henning Kamp 	upp = TAILQ_LAST(&uh->head, unrhd);
574d9a54d5cSPoul-Henning Kamp 	if (upp != NULL && upp->ptr == NULL) {
575d9a54d5cSPoul-Henning Kamp 		uh->last += upp->len;
576d9a54d5cSPoul-Henning Kamp 		TAILQ_REMOVE(&uh->head, upp, list);
577d9a54d5cSPoul-Henning Kamp 		delete_unr(uh, upp);
578d9a54d5cSPoul-Henning Kamp 		if (up == upp)
579d9a54d5cSPoul-Henning Kamp 			up = NULL;
580d9a54d5cSPoul-Henning Kamp 	}
581d9a54d5cSPoul-Henning Kamp 
582d9a54d5cSPoul-Henning Kamp 	/* Try to make bitmaps */
583d9a54d5cSPoul-Henning Kamp 	while (optimize_unr(uh))
584d9a54d5cSPoul-Henning Kamp 		continue;
585d9a54d5cSPoul-Henning Kamp }
586d9a54d5cSPoul-Henning Kamp 
587f6bde1fdSPoul-Henning Kamp /*
588f6bde1fdSPoul-Henning Kamp  * Allocate a free unr.
589f6bde1fdSPoul-Henning Kamp  */
590d9a54d5cSPoul-Henning Kamp int
591d9a54d5cSPoul-Henning Kamp alloc_unrl(struct unrhdr *uh)
592f6bde1fdSPoul-Henning Kamp {
593d9a54d5cSPoul-Henning Kamp 	struct unr *up;
594d9a54d5cSPoul-Henning Kamp 	struct unrb *ub;
595f6bde1fdSPoul-Henning Kamp 	u_int x;
596f6bde1fdSPoul-Henning Kamp 	int y;
597f6bde1fdSPoul-Henning Kamp 
598d9a54d5cSPoul-Henning Kamp 	mtx_assert(uh->mtx, MA_OWNED);
599f6bde1fdSPoul-Henning Kamp 	check_unrhdr(uh, __LINE__);
600d9a54d5cSPoul-Henning Kamp 	x = uh->low + uh->first;
601d9a54d5cSPoul-Henning Kamp 
602f6bde1fdSPoul-Henning Kamp 	up = TAILQ_FIRST(&uh->head);
603f6bde1fdSPoul-Henning Kamp 
604d9a54d5cSPoul-Henning Kamp 	/*
605d9a54d5cSPoul-Henning Kamp 	 * If we have an ideal split, just adjust the first+last
606d9a54d5cSPoul-Henning Kamp 	 */
607d9a54d5cSPoul-Henning Kamp 	if (up == NULL && uh->last > 0) {
608d9a54d5cSPoul-Henning Kamp 		uh->first++;
609d9a54d5cSPoul-Henning Kamp 		uh->last--;
610f6bde1fdSPoul-Henning Kamp 		uh->busy++;
611f6bde1fdSPoul-Henning Kamp 		return (x);
612f6bde1fdSPoul-Henning Kamp 	}
613f6bde1fdSPoul-Henning Kamp 
614f6bde1fdSPoul-Henning Kamp 	/*
615d9a54d5cSPoul-Henning Kamp 	 * We can always allocate from the first list element, so if we have
616d9a54d5cSPoul-Henning Kamp 	 * nothing on the list, we must have run out of unit numbers.
617f6bde1fdSPoul-Henning Kamp 	 */
61893f6c81eSPoul-Henning Kamp 	if (up == NULL)
619d9a54d5cSPoul-Henning Kamp 		return (-1);
620d9a54d5cSPoul-Henning Kamp 
621d9a54d5cSPoul-Henning Kamp 	KASSERT(up->ptr != uh, ("UNR first element is allocated"));
622d9a54d5cSPoul-Henning Kamp 
623d9a54d5cSPoul-Henning Kamp 	if (up->ptr == NULL) {	/* free run */
624d9a54d5cSPoul-Henning Kamp 		uh->first++;
625f6bde1fdSPoul-Henning Kamp 		up->len--;
626d9a54d5cSPoul-Henning Kamp 	} else {		/* bitmap */
627d9a54d5cSPoul-Henning Kamp 		ub = up->ptr;
628d9a54d5cSPoul-Henning Kamp 		bit_ffc(ub->map, up->len, &y);
629d9a54d5cSPoul-Henning Kamp 		KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
630d9a54d5cSPoul-Henning Kamp 		bit_set(ub->map, y);
631d9a54d5cSPoul-Henning Kamp 		x += y;
632d9a54d5cSPoul-Henning Kamp 	}
633f6bde1fdSPoul-Henning Kamp 	uh->busy++;
634d9a54d5cSPoul-Henning Kamp 	collapse_unr(uh, up);
635f6bde1fdSPoul-Henning Kamp 	return (x);
636f6bde1fdSPoul-Henning Kamp }
637f6bde1fdSPoul-Henning Kamp 
638d9a54d5cSPoul-Henning Kamp int
639d9a54d5cSPoul-Henning Kamp alloc_unr(struct unrhdr *uh)
640d9a54d5cSPoul-Henning Kamp {
641d9a54d5cSPoul-Henning Kamp 	int i;
642d9a54d5cSPoul-Henning Kamp 
643d9a54d5cSPoul-Henning Kamp 	mtx_lock(uh->mtx);
644d9a54d5cSPoul-Henning Kamp 	i = alloc_unrl(uh);
64509828ba9SKonstantin Belousov 	clean_unrhdrl(uh);
646d9a54d5cSPoul-Henning Kamp 	mtx_unlock(uh->mtx);
647d9a54d5cSPoul-Henning Kamp 	return (i);
648d9a54d5cSPoul-Henning Kamp }
649d9a54d5cSPoul-Henning Kamp 
65013c02cbbSJaakko Heinonen static int
65113c02cbbSJaakko Heinonen alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
65213c02cbbSJaakko Heinonen {
65313c02cbbSJaakko Heinonen 	struct unr *up, *upn;
65413c02cbbSJaakko Heinonen 	struct unrb *ub;
65513c02cbbSJaakko Heinonen 	u_int i, last, tl;
65613c02cbbSJaakko Heinonen 
65713c02cbbSJaakko Heinonen 	mtx_assert(uh->mtx, MA_OWNED);
65813c02cbbSJaakko Heinonen 
65913c02cbbSJaakko Heinonen 	if (item < uh->low + uh->first || item > uh->high)
66013c02cbbSJaakko Heinonen 		return (-1);
66113c02cbbSJaakko Heinonen 
66213c02cbbSJaakko Heinonen 	up = TAILQ_FIRST(&uh->head);
66313c02cbbSJaakko Heinonen 	/* Ideal split. */
66413c02cbbSJaakko Heinonen 	if (up == NULL && item - uh->low == uh->first) {
66513c02cbbSJaakko Heinonen 		uh->first++;
66613c02cbbSJaakko Heinonen 		uh->last--;
66713c02cbbSJaakko Heinonen 		uh->busy++;
66813c02cbbSJaakko Heinonen 		check_unrhdr(uh, __LINE__);
66913c02cbbSJaakko Heinonen 		return (item);
67013c02cbbSJaakko Heinonen 	}
67113c02cbbSJaakko Heinonen 
67213c02cbbSJaakko Heinonen 	i = item - uh->low - uh->first;
67313c02cbbSJaakko Heinonen 
67413c02cbbSJaakko Heinonen 	if (up == NULL) {
67513c02cbbSJaakko Heinonen 		up = new_unr(uh, p1, p2);
67613c02cbbSJaakko Heinonen 		up->ptr = NULL;
67713c02cbbSJaakko Heinonen 		up->len = i;
67813c02cbbSJaakko Heinonen 		TAILQ_INSERT_TAIL(&uh->head, up, list);
67913c02cbbSJaakko Heinonen 		up = new_unr(uh, p1, p2);
68013c02cbbSJaakko Heinonen 		up->ptr = uh;
68113c02cbbSJaakko Heinonen 		up->len = 1;
68213c02cbbSJaakko Heinonen 		TAILQ_INSERT_TAIL(&uh->head, up, list);
68313c02cbbSJaakko Heinonen 		uh->last = uh->high - uh->low - i;
68413c02cbbSJaakko Heinonen 		uh->busy++;
68513c02cbbSJaakko Heinonen 		check_unrhdr(uh, __LINE__);
68613c02cbbSJaakko Heinonen 		return (item);
68713c02cbbSJaakko Heinonen 	} else {
68813c02cbbSJaakko Heinonen 		/* Find the item which contains the unit we want to allocate. */
68913c02cbbSJaakko Heinonen 		TAILQ_FOREACH(up, &uh->head, list) {
69013c02cbbSJaakko Heinonen 			if (up->len > i)
69113c02cbbSJaakko Heinonen 				break;
69213c02cbbSJaakko Heinonen 			i -= up->len;
69313c02cbbSJaakko Heinonen 		}
69413c02cbbSJaakko Heinonen 	}
69513c02cbbSJaakko Heinonen 
69613c02cbbSJaakko Heinonen 	if (up == NULL) {
69713c02cbbSJaakko Heinonen 		if (i > 0) {
69813c02cbbSJaakko Heinonen 			up = new_unr(uh, p1, p2);
69913c02cbbSJaakko Heinonen 			up->ptr = NULL;
70013c02cbbSJaakko Heinonen 			up->len = i;
70113c02cbbSJaakko Heinonen 			TAILQ_INSERT_TAIL(&uh->head, up, list);
70213c02cbbSJaakko Heinonen 		}
70313c02cbbSJaakko Heinonen 		up = new_unr(uh, p1, p2);
70413c02cbbSJaakko Heinonen 		up->ptr = uh;
70513c02cbbSJaakko Heinonen 		up->len = 1;
70613c02cbbSJaakko Heinonen 		TAILQ_INSERT_TAIL(&uh->head, up, list);
70713c02cbbSJaakko Heinonen 		goto done;
70813c02cbbSJaakko Heinonen 	}
70913c02cbbSJaakko Heinonen 
71013c02cbbSJaakko Heinonen 	if (is_bitmap(uh, up)) {
71113c02cbbSJaakko Heinonen 		ub = up->ptr;
71213c02cbbSJaakko Heinonen 		if (bit_test(ub->map, i) == 0) {
71313c02cbbSJaakko Heinonen 			bit_set(ub->map, i);
71413c02cbbSJaakko Heinonen 			goto done;
71513c02cbbSJaakko Heinonen 		} else
71613c02cbbSJaakko Heinonen 			return (-1);
71713c02cbbSJaakko Heinonen 	} else if (up->ptr == uh)
71813c02cbbSJaakko Heinonen 		return (-1);
71913c02cbbSJaakko Heinonen 
72013c02cbbSJaakko Heinonen 	KASSERT(up->ptr == NULL,
72113c02cbbSJaakko Heinonen 	    ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
72213c02cbbSJaakko Heinonen 
72313c02cbbSJaakko Heinonen 	/* Split off the tail end, if any. */
72413c02cbbSJaakko Heinonen 	tl = up->len - (1 + i);
72513c02cbbSJaakko Heinonen 	if (tl > 0) {
72613c02cbbSJaakko Heinonen 		upn = new_unr(uh, p1, p2);
72713c02cbbSJaakko Heinonen 		upn->ptr = NULL;
72813c02cbbSJaakko Heinonen 		upn->len = tl;
72913c02cbbSJaakko Heinonen 		TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
73013c02cbbSJaakko Heinonen 	}
73113c02cbbSJaakko Heinonen 
73213c02cbbSJaakko Heinonen 	/* Split off head end, if any */
73313c02cbbSJaakko Heinonen 	if (i > 0) {
73413c02cbbSJaakko Heinonen 		upn = new_unr(uh, p1, p2);
73513c02cbbSJaakko Heinonen 		upn->len = i;
73613c02cbbSJaakko Heinonen 		upn->ptr = NULL;
73713c02cbbSJaakko Heinonen 		TAILQ_INSERT_BEFORE(up, upn, list);
73813c02cbbSJaakko Heinonen 	}
73913c02cbbSJaakko Heinonen 	up->len = 1;
74013c02cbbSJaakko Heinonen 	up->ptr = uh;
74113c02cbbSJaakko Heinonen 
74213c02cbbSJaakko Heinonen done:
74313c02cbbSJaakko Heinonen 	last = uh->high - uh->low - (item - uh->low);
74413c02cbbSJaakko Heinonen 	if (uh->last > last)
74513c02cbbSJaakko Heinonen 		uh->last = last;
74613c02cbbSJaakko Heinonen 	uh->busy++;
74713c02cbbSJaakko Heinonen 	collapse_unr(uh, up);
74813c02cbbSJaakko Heinonen 	check_unrhdr(uh, __LINE__);
74913c02cbbSJaakko Heinonen 	return (item);
75013c02cbbSJaakko Heinonen }
75113c02cbbSJaakko Heinonen 
75213c02cbbSJaakko Heinonen int
75313c02cbbSJaakko Heinonen alloc_unr_specific(struct unrhdr *uh, u_int item)
75413c02cbbSJaakko Heinonen {
75513c02cbbSJaakko Heinonen 	void *p1, *p2;
75613c02cbbSJaakko Heinonen 	int i;
75713c02cbbSJaakko Heinonen 
75813c02cbbSJaakko Heinonen 	WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
75913c02cbbSJaakko Heinonen 
76013c02cbbSJaakko Heinonen 	p1 = Malloc(sizeof(struct unr));
76113c02cbbSJaakko Heinonen 	p2 = Malloc(sizeof(struct unr));
76213c02cbbSJaakko Heinonen 
76313c02cbbSJaakko Heinonen 	mtx_lock(uh->mtx);
76413c02cbbSJaakko Heinonen 	i = alloc_unr_specificl(uh, item, &p1, &p2);
76513c02cbbSJaakko Heinonen 	mtx_unlock(uh->mtx);
76613c02cbbSJaakko Heinonen 
76713c02cbbSJaakko Heinonen 	if (p1 != NULL)
76813c02cbbSJaakko Heinonen 		Free(p1);
76913c02cbbSJaakko Heinonen 	if (p2 != NULL)
77013c02cbbSJaakko Heinonen 		Free(p2);
77113c02cbbSJaakko Heinonen 
77213c02cbbSJaakko Heinonen 	return (i);
77313c02cbbSJaakko Heinonen }
77413c02cbbSJaakko Heinonen 
775f6bde1fdSPoul-Henning Kamp /*
776f6bde1fdSPoul-Henning Kamp  * Free a unr.
777f6bde1fdSPoul-Henning Kamp  *
778f6bde1fdSPoul-Henning Kamp  * If we can save unrs by using a bitmap, do so.
779f6bde1fdSPoul-Henning Kamp  */
780d9a54d5cSPoul-Henning Kamp static void
781d9a54d5cSPoul-Henning Kamp free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
782f6bde1fdSPoul-Henning Kamp {
783d9a54d5cSPoul-Henning Kamp 	struct unr *up, *upp, *upn;
784d9a54d5cSPoul-Henning Kamp 	struct unrb *ub;
785d9a54d5cSPoul-Henning Kamp 	u_int pl;
786f6bde1fdSPoul-Henning Kamp 
787f6bde1fdSPoul-Henning Kamp 	KASSERT(item >= uh->low && item <= uh->high,
788f6bde1fdSPoul-Henning Kamp 	    ("UNR: free_unr(%u) out of range [%u...%u]",
789f6bde1fdSPoul-Henning Kamp 	     item, uh->low, uh->high));
790f6bde1fdSPoul-Henning Kamp 	check_unrhdr(uh, __LINE__);
791f6bde1fdSPoul-Henning Kamp 	item -= uh->low;
792d9a54d5cSPoul-Henning Kamp 	upp = TAILQ_FIRST(&uh->head);
793f6bde1fdSPoul-Henning Kamp 	/*
794d9a54d5cSPoul-Henning Kamp 	 * Freeing in the ideal split case
795f6bde1fdSPoul-Henning Kamp 	 */
796d9a54d5cSPoul-Henning Kamp 	if (item + 1 == uh->first && upp == NULL) {
797d9a54d5cSPoul-Henning Kamp 		uh->last++;
798d9a54d5cSPoul-Henning Kamp 		uh->first--;
799d9a54d5cSPoul-Henning Kamp 		uh->busy--;
800f6bde1fdSPoul-Henning Kamp 		check_unrhdr(uh, __LINE__);
801f6bde1fdSPoul-Henning Kamp 		return;
802f6bde1fdSPoul-Henning Kamp 	}
803d9a54d5cSPoul-Henning Kamp 	/*
804d9a54d5cSPoul-Henning Kamp  	 * Freeing in the ->first section.  Create a run starting at the
805d9a54d5cSPoul-Henning Kamp 	 * freed item.  The code below will subdivide it.
806d9a54d5cSPoul-Henning Kamp 	 */
807d9a54d5cSPoul-Henning Kamp 	if (item < uh->first) {
808d9a54d5cSPoul-Henning Kamp 		up = new_unr(uh, p1, p2);
809d9a54d5cSPoul-Henning Kamp 		up->ptr = uh;
810d9a54d5cSPoul-Henning Kamp 		up->len = uh->first - item;
811d9a54d5cSPoul-Henning Kamp 		TAILQ_INSERT_HEAD(&uh->head, up, list);
812d9a54d5cSPoul-Henning Kamp 		uh->first -= up->len;
813f6bde1fdSPoul-Henning Kamp 	}
814f6bde1fdSPoul-Henning Kamp 
815d9a54d5cSPoul-Henning Kamp 	item -= uh->first;
816d9a54d5cSPoul-Henning Kamp 
817d9a54d5cSPoul-Henning Kamp 	/* Find the item which contains the unit we want to free */
818d9a54d5cSPoul-Henning Kamp 	TAILQ_FOREACH(up, &uh->head, list) {
819d9a54d5cSPoul-Henning Kamp 		if (up->len > item)
820d9a54d5cSPoul-Henning Kamp 			break;
821d9a54d5cSPoul-Henning Kamp 		item -= up->len;
822d9a54d5cSPoul-Henning Kamp 	}
823d9a54d5cSPoul-Henning Kamp 
824d9a54d5cSPoul-Henning Kamp 	/* Handle bitmap items */
825d9a54d5cSPoul-Henning Kamp 	if (is_bitmap(uh, up)) {
826d9a54d5cSPoul-Henning Kamp 		ub = up->ptr;
827d9a54d5cSPoul-Henning Kamp 
828d9a54d5cSPoul-Henning Kamp 		KASSERT(bit_test(ub->map, item) != 0,
829d9a54d5cSPoul-Henning Kamp 		    ("UNR: Freeing free item %d (bitmap)\n", item));
830d9a54d5cSPoul-Henning Kamp 		bit_clear(ub->map, item);
831d9a54d5cSPoul-Henning Kamp 		uh->busy--;
832d9a54d5cSPoul-Henning Kamp 		collapse_unr(uh, up);
833d9a54d5cSPoul-Henning Kamp 		return;
834d9a54d5cSPoul-Henning Kamp 	}
835d9a54d5cSPoul-Henning Kamp 
836d9a54d5cSPoul-Henning Kamp 	KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
837f6bde1fdSPoul-Henning Kamp 
838f6bde1fdSPoul-Henning Kamp 	/* Just this one left, reap it */
839f6bde1fdSPoul-Henning Kamp 	if (up->len == 1) {
840f6bde1fdSPoul-Henning Kamp 		up->ptr = NULL;
841f6bde1fdSPoul-Henning Kamp 		uh->busy--;
842f6bde1fdSPoul-Henning Kamp 		collapse_unr(uh, up);
843f6bde1fdSPoul-Henning Kamp 		return;
844f6bde1fdSPoul-Henning Kamp 	}
845f6bde1fdSPoul-Henning Kamp 
846d9a54d5cSPoul-Henning Kamp 	/* Check if we can shift the item into the previous 'free' run */
847f6bde1fdSPoul-Henning Kamp 	upp = TAILQ_PREV(up, unrhd, list);
848d9a54d5cSPoul-Henning Kamp 	if (item == 0 && upp != NULL && upp->ptr == NULL) {
849f6bde1fdSPoul-Henning Kamp 		upp->len++;
850f6bde1fdSPoul-Henning Kamp 		up->len--;
851f6bde1fdSPoul-Henning Kamp 		uh->busy--;
852d9a54d5cSPoul-Henning Kamp 		collapse_unr(uh, up);
853f6bde1fdSPoul-Henning Kamp 		return;
854f6bde1fdSPoul-Henning Kamp 	}
855f6bde1fdSPoul-Henning Kamp 
856d9a54d5cSPoul-Henning Kamp 	/* Check if we can shift the item to the next 'free' run */
857f6bde1fdSPoul-Henning Kamp 	upn = TAILQ_NEXT(up, list);
858d9a54d5cSPoul-Henning Kamp 	if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
859f6bde1fdSPoul-Henning Kamp 		upn->len++;
860f6bde1fdSPoul-Henning Kamp 		up->len--;
861f6bde1fdSPoul-Henning Kamp 		uh->busy--;
862d9a54d5cSPoul-Henning Kamp 		collapse_unr(uh, up);
863f6bde1fdSPoul-Henning Kamp 		return;
864f6bde1fdSPoul-Henning Kamp 	}
865f6bde1fdSPoul-Henning Kamp 
866f6bde1fdSPoul-Henning Kamp 	/* Split off the tail end, if any. */
867d9a54d5cSPoul-Henning Kamp 	pl = up->len - (1 + item);
868f6bde1fdSPoul-Henning Kamp 	if (pl > 0) {
869d9a54d5cSPoul-Henning Kamp 		upp = new_unr(uh, p1, p2);
870f6bde1fdSPoul-Henning Kamp 		upp->ptr = uh;
871f6bde1fdSPoul-Henning Kamp 		upp->len = pl;
872f6bde1fdSPoul-Henning Kamp 		TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
873f6bde1fdSPoul-Henning Kamp 	}
874f6bde1fdSPoul-Henning Kamp 
875d9a54d5cSPoul-Henning Kamp 	/* Split off head end, if any */
876d9a54d5cSPoul-Henning Kamp 	if (item > 0) {
877d9a54d5cSPoul-Henning Kamp 		upp = new_unr(uh, p1, p2);
878d9a54d5cSPoul-Henning Kamp 		upp->len = item;
879d9a54d5cSPoul-Henning Kamp 		upp->ptr = uh;
880d9a54d5cSPoul-Henning Kamp 		TAILQ_INSERT_BEFORE(up, upp, list);
881d9a54d5cSPoul-Henning Kamp 	}
882f6bde1fdSPoul-Henning Kamp 	up->len = 1;
883f6bde1fdSPoul-Henning Kamp 	up->ptr = NULL;
884f6bde1fdSPoul-Henning Kamp 	uh->busy--;
885d9a54d5cSPoul-Henning Kamp 	collapse_unr(uh, up);
886f6bde1fdSPoul-Henning Kamp }
887f6bde1fdSPoul-Henning Kamp 
888d9a54d5cSPoul-Henning Kamp void
889d9a54d5cSPoul-Henning Kamp free_unr(struct unrhdr *uh, u_int item)
890d9a54d5cSPoul-Henning Kamp {
891d9a54d5cSPoul-Henning Kamp 	void *p1, *p2;
892f6bde1fdSPoul-Henning Kamp 
8937550e3eaSKonstantin Belousov 	WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
894d9a54d5cSPoul-Henning Kamp 	p1 = Malloc(sizeof(struct unr));
895d9a54d5cSPoul-Henning Kamp 	p2 = Malloc(sizeof(struct unr));
896d9a54d5cSPoul-Henning Kamp 	mtx_lock(uh->mtx);
897d9a54d5cSPoul-Henning Kamp 	free_unrl(uh, item, &p1, &p2);
89809828ba9SKonstantin Belousov 	clean_unrhdrl(uh);
899d9a54d5cSPoul-Henning Kamp 	mtx_unlock(uh->mtx);
900d9a54d5cSPoul-Henning Kamp 	if (p1 != NULL)
901d9a54d5cSPoul-Henning Kamp 		Free(p1);
902d9a54d5cSPoul-Henning Kamp 	if (p2 != NULL)
903d9a54d5cSPoul-Henning Kamp 		Free(p2);
904f6bde1fdSPoul-Henning Kamp }
905f6bde1fdSPoul-Henning Kamp 
90693f6c81eSPoul-Henning Kamp #ifndef _KERNEL	/* USERLAND test driver */
90793f6c81eSPoul-Henning Kamp 
908f6bde1fdSPoul-Henning Kamp /*
909794277daSAlan Somers  * Simple stochastic test driver for the above functions.  The code resides
910794277daSAlan Somers  * here so that it can access static functions and structures.
911f6bde1fdSPoul-Henning Kamp  */
912f6bde1fdSPoul-Henning Kamp 
913794277daSAlan Somers static bool verbose;
914794277daSAlan Somers #define VPRINTF(...)	{if (verbose) printf(__VA_ARGS__);}
915794277daSAlan Somers 
916f6bde1fdSPoul-Henning Kamp static void
917f6bde1fdSPoul-Henning Kamp print_unr(struct unrhdr *uh, struct unr *up)
918f6bde1fdSPoul-Henning Kamp {
919f6bde1fdSPoul-Henning Kamp 	u_int x;
920d9a54d5cSPoul-Henning Kamp 	struct unrb *ub;
921f6bde1fdSPoul-Henning Kamp 
922f6bde1fdSPoul-Henning Kamp 	printf("  %p len = %5u ", up, up->len);
923f6bde1fdSPoul-Henning Kamp 	if (up->ptr == NULL)
924f6bde1fdSPoul-Henning Kamp 		printf("free\n");
925f6bde1fdSPoul-Henning Kamp 	else if (up->ptr == uh)
926f6bde1fdSPoul-Henning Kamp 		printf("alloc\n");
927f6bde1fdSPoul-Henning Kamp 	else {
928d9a54d5cSPoul-Henning Kamp 		ub = up->ptr;
9298907f744SAlan Somers 		printf("bitmap [");
930d9a54d5cSPoul-Henning Kamp 		for (x = 0; x < up->len; x++) {
931d9a54d5cSPoul-Henning Kamp 			if (bit_test(ub->map, x))
932d9a54d5cSPoul-Henning Kamp 				printf("#");
933f6bde1fdSPoul-Henning Kamp 			else
934d9a54d5cSPoul-Henning Kamp 				printf(" ");
935f6bde1fdSPoul-Henning Kamp 		}
936f6bde1fdSPoul-Henning Kamp 		printf("]\n");
937f6bde1fdSPoul-Henning Kamp 	}
938f6bde1fdSPoul-Henning Kamp }
939f6bde1fdSPoul-Henning Kamp 
940f6bde1fdSPoul-Henning Kamp static void
941f6bde1fdSPoul-Henning Kamp print_unrhdr(struct unrhdr *uh)
942f6bde1fdSPoul-Henning Kamp {
943f6bde1fdSPoul-Henning Kamp 	struct unr *up;
944f6bde1fdSPoul-Henning Kamp 	u_int x;
945f6bde1fdSPoul-Henning Kamp 
946d9a54d5cSPoul-Henning Kamp 	printf(
947d9a54d5cSPoul-Henning Kamp 	    "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
948d9a54d5cSPoul-Henning Kamp 	    uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
949d9a54d5cSPoul-Henning Kamp 	x = uh->low + uh->first;
950f6bde1fdSPoul-Henning Kamp 	TAILQ_FOREACH(up, &uh->head, list) {
951f6bde1fdSPoul-Henning Kamp 		printf("  from = %5u", x);
952f6bde1fdSPoul-Henning Kamp 		print_unr(uh, up);
953f6bde1fdSPoul-Henning Kamp 		if (up->ptr == NULL || up->ptr == uh)
954f6bde1fdSPoul-Henning Kamp 			x += up->len;
955f6bde1fdSPoul-Henning Kamp 		else
956f6bde1fdSPoul-Henning Kamp 			x += NBITS;
957f6bde1fdSPoul-Henning Kamp 	}
958f6bde1fdSPoul-Henning Kamp }
959f6bde1fdSPoul-Henning Kamp 
96013c02cbbSJaakko Heinonen static void
96113c02cbbSJaakko Heinonen test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
96213c02cbbSJaakko Heinonen {
96313c02cbbSJaakko Heinonen 	int j;
96413c02cbbSJaakko Heinonen 
96513c02cbbSJaakko Heinonen 	if (a[i]) {
966794277daSAlan Somers 		VPRINTF("F %u\n", i);
96713c02cbbSJaakko Heinonen 		free_unr(uh, i);
96813c02cbbSJaakko Heinonen 		a[i] = 0;
96913c02cbbSJaakko Heinonen 	} else {
97013c02cbbSJaakko Heinonen 		no_alloc = 1;
97113c02cbbSJaakko Heinonen 		j = alloc_unr(uh);
97213c02cbbSJaakko Heinonen 		if (j != -1) {
97313c02cbbSJaakko Heinonen 			a[j] = 1;
974794277daSAlan Somers 			VPRINTF("A %d\n", j);
97513c02cbbSJaakko Heinonen 		}
97613c02cbbSJaakko Heinonen 		no_alloc = 0;
97713c02cbbSJaakko Heinonen 	}
97813c02cbbSJaakko Heinonen }
97913c02cbbSJaakko Heinonen 
98013c02cbbSJaakko Heinonen static void
98113c02cbbSJaakko Heinonen test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
98213c02cbbSJaakko Heinonen {
98313c02cbbSJaakko Heinonen 	int j;
98413c02cbbSJaakko Heinonen 
98513c02cbbSJaakko Heinonen 	j = alloc_unr_specific(uh, i);
98613c02cbbSJaakko Heinonen 	if (j == -1) {
987794277daSAlan Somers 		VPRINTF("F %u\n", i);
98813c02cbbSJaakko Heinonen 		a[i] = 0;
98913c02cbbSJaakko Heinonen 		free_unr(uh, i);
99013c02cbbSJaakko Heinonen 	} else {
99113c02cbbSJaakko Heinonen 		a[i] = 1;
992794277daSAlan Somers 		VPRINTF("A %d\n", j);
99313c02cbbSJaakko Heinonen 	}
99413c02cbbSJaakko Heinonen }
99513c02cbbSJaakko Heinonen 
996794277daSAlan Somers static void
997794277daSAlan Somers usage(char** argv)
998794277daSAlan Somers {
999794277daSAlan Somers 	printf("%s [-h] [-r REPETITIONS] [-v]\n", argv[0]);
1000794277daSAlan Somers }
1001f6bde1fdSPoul-Henning Kamp 
1002f6bde1fdSPoul-Henning Kamp int
1003794277daSAlan Somers main(int argc, char **argv)
1004f6bde1fdSPoul-Henning Kamp {
1005f6bde1fdSPoul-Henning Kamp 	struct unrhdr *uh;
1006794277daSAlan Somers 	char *a;
1007794277daSAlan Somers 	long count = 10000;	/* Number of unrs to test */
100837f32e53SAlan Somers 	long reps = 1, m;
1009794277daSAlan Somers 	int ch;
10105e8fcdfeSEnji Cooper 	u_int i, j;
1011794277daSAlan Somers 
1012794277daSAlan Somers 	verbose = false;
1013794277daSAlan Somers 
1014794277daSAlan Somers 	while ((ch = getopt(argc, argv, "hr:v")) != -1) {
1015794277daSAlan Somers 		switch (ch) {
1016794277daSAlan Somers 		case 'r':
1017794277daSAlan Somers 			errno = 0;
1018794277daSAlan Somers 			reps = strtol(optarg, NULL, 0);
1019794277daSAlan Somers 			if (errno == ERANGE || errno == EINVAL) {
1020794277daSAlan Somers 				usage(argv);
1021794277daSAlan Somers 				exit(2);
1022794277daSAlan Somers 			}
1023794277daSAlan Somers 
1024794277daSAlan Somers 			break;
1025794277daSAlan Somers 		case 'v':
1026794277daSAlan Somers 			verbose = true;
1027794277daSAlan Somers 			break;
1028794277daSAlan Somers 		case 'h':
1029794277daSAlan Somers 		default:
1030794277daSAlan Somers 			usage(argv);
1031794277daSAlan Somers 			exit(2);
1032794277daSAlan Somers 		}
1033794277daSAlan Somers 
1034794277daSAlan Somers 
1035794277daSAlan Somers 	}
1036f6bde1fdSPoul-Henning Kamp 
1037d9a54d5cSPoul-Henning Kamp 	setbuf(stdout, NULL);
1038794277daSAlan Somers 	uh = new_unrhdr(0, count - 1, NULL);
1039d9a54d5cSPoul-Henning Kamp 	print_unrhdr(uh);
1040f6bde1fdSPoul-Henning Kamp 
1041794277daSAlan Somers 	a = calloc(count, sizeof(char));
1042794277daSAlan Somers 	if (a == NULL)
1043794277daSAlan Somers 		err(1, "calloc failed");
104413c02cbbSJaakko Heinonen 	srandomdev();
1045f6bde1fdSPoul-Henning Kamp 
1046794277daSAlan Somers 	printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
1047794277daSAlan Somers 	printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
1048794277daSAlan Somers 	printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
1049b4f69365SEd Maste 	printf("NBITS %lu\n", (unsigned long)NBITS);
1050794277daSAlan Somers 	for (m = 0; m < count * reps; m++) {
1051d9a54d5cSPoul-Henning Kamp 		j = random();
1052794277daSAlan Somers 		i = (j >> 1) % count;
1053d9a54d5cSPoul-Henning Kamp #if 0
1054d9a54d5cSPoul-Henning Kamp 		if (a[i] && (j & 1))
1055d9a54d5cSPoul-Henning Kamp 			continue;
1056d9a54d5cSPoul-Henning Kamp #endif
105713c02cbbSJaakko Heinonen 		if ((random() & 1) != 0)
105813c02cbbSJaakko Heinonen 			test_alloc_unr(uh, i, a);
105913c02cbbSJaakko Heinonen 		else
106013c02cbbSJaakko Heinonen 			test_alloc_unr_specific(uh, i, a);
106113c02cbbSJaakko Heinonen 
1062794277daSAlan Somers 		if (verbose)
1063f6bde1fdSPoul-Henning Kamp 			print_unrhdr(uh);
1064f6bde1fdSPoul-Henning Kamp 		check_unrhdr(uh, __LINE__);
1065f6bde1fdSPoul-Henning Kamp 	}
106637f32e53SAlan Somers 	for (i = 0; i < (u_int)count; i++) {
1067d9a54d5cSPoul-Henning Kamp 		if (a[i]) {
1068794277daSAlan Somers 			if (verbose) {
1069d9a54d5cSPoul-Henning Kamp 				printf("C %u\n", i);
1070e4fea39eSPoul-Henning Kamp 				print_unrhdr(uh);
1071d9a54d5cSPoul-Henning Kamp 			}
1072794277daSAlan Somers 			free_unr(uh, i);
1073794277daSAlan Somers 		}
1074d9a54d5cSPoul-Henning Kamp 	}
1075d9a54d5cSPoul-Henning Kamp 	print_unrhdr(uh);
1076e4fea39eSPoul-Henning Kamp 	delete_unrhdr(uh);
1077794277daSAlan Somers 	free(a);
1078f6bde1fdSPoul-Henning Kamp 	return (0);
1079f6bde1fdSPoul-Henning Kamp }
1080f6bde1fdSPoul-Henning Kamp #endif
1081