2 * SPDX-License-Identifier: BSD-2-Clause
4 * Copyright (c) 2004 Poul-Henning Kamp
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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.
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
31 * Unit number allocation functions.
33 * These functions implement a mixed run-length/bitmap management of unit
34 * number spaces in a very memory efficient manner.
36 * Allocation policy is always lowest free number first.
38 * A return value of -1 signals that no more unit numbers are available.
40 * There is no cost associated with the range of unitnumbers, so unless
41 * the resource really is finite, specify INT_MAX to new_unrhdr() and
42 * forget about checking the return value.
44 * If a mutex is not provided when the unit number space is created, a
45 * default global mutex is used. The advantage to passing a mutex in, is
46 * that the alloc_unrl() function can be called with the mutex already
47 * held (it will not be released by alloc_unrl()).
49 * The allocation function alloc_unr{l}() never sleeps (but it may block on
50 * the mutex of course).
52 * Freeing a unit number may require allocating memory, and can therefore
53 * sleep so the free_unr() function does not come in a pre-locked variant.
55 * A userland test program is included.
57 * Memory usage is a very complex function of the exact allocation
58 * pattern, but always very compact:
59 * * For the very typical case where a single unbroken run of unit
60 * numbers are allocated 44 bytes are used on i386.
61 * * For a unit number space of 1000 units and the random pattern
62 * in the usermode test program included, the worst case usage
63 * was 252 bytes on i386 for 500 allocated and 500 free units.
64 * * For a unit number space of 10000 units and the random pattern
65 * in the usermode test program included, the worst case usage
66 * was 798 bytes on i386 for 5000 allocated and 5000 free units.
67 * * The worst case is where every other unit number is allocated and
68 * the rest are free. In that case 44 + N/4 bytes are used where
69 * N is the number of the highest unit allocated.
72 #include <sys/param.h>
73 #include <sys/types.h>
74 #include <sys/_unrhdr.h>
78 #include <sys/bitstring.h>
79 #include <sys/malloc.h>
80 #include <sys/kernel.h>
81 #include <sys/systm.h>
82 #include <sys/limits.h>
84 #include <sys/mutex.h>
87 * In theory it would be smarter to allocate the individual blocks
88 * with the zone allocator, but at this time the expectation is that
89 * there will typically not even be enough allocations to fill a single
90 * page, so we stick with malloc for now.
92 static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation");
94 #define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
95 #define Free(foo) free(foo, M_UNIT)
97 static struct mtx unitmtx;
99 MTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF);
101 #else /* ...USERLAND */
103 #include <bitstring.h>
112 #define KASSERT(cond, arg) \
121 #define Malloc(foo) _Malloc(foo, __LINE__)
123 _Malloc(size_t foo, int line)
126 KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
127 return (calloc(foo, 1));
129 #define Free(foo) free(foo)
133 #define UNR_NO_MTX ((void *)(uintptr_t)-1)
140 mtx_lock(struct mtx *mp)
142 KASSERT(mp->state == 0, ("mutex already locked"));
147 mtx_unlock(struct mtx *mp)
149 KASSERT(mp->state == 1, ("mutex not locked"));
156 mtx_assert(struct mtx *mp, int flag)
158 if (flag == MA_OWNED) {
159 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
163 #define CTASSERT(foo)
164 #define WITNESS_WARN(flags, lock, fmt, ...) (void)0
166 #endif /* USERLAND */
169 * This is our basic building block.
171 * It can be used in three different ways depending on the value of the ptr
173 * If ptr is NULL, it represents a run of free items.
174 * If ptr points to the unrhdr it represents a run of allocated items.
175 * Otherwise it points to a bitstring of allocated items.
177 * For runs the len field is the length of the run.
178 * For bitmaps the len field represents the number of allocated items.
180 * The bitmap is the same size as struct unr to optimize memory management.
182 * Two special ranges are not covered by unrs:
183 * - at the start of the allocator space, all elements in [low, low + first)
185 * - at the end of the allocator space, all elements in [high - last, high]
189 TAILQ_ENTRY(unr) list;
195 bitstr_t map[sizeof(struct unr) / sizeof(bitstr_t)];
198 CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
200 /* Number of bits we can store in the bitmap */
201 #define NBITS (NBBY * sizeof(((struct unrb *)NULL)->map))
204 is_bitmap(struct unrhdr *uh, struct unr *up)
206 return (up->ptr != uh && up->ptr != NULL);
209 /* Is the unrb empty in at least the first len bits? */
211 ub_empty(struct unrb *ub, int len) {
214 bit_ffs(ub->map, len, &first_set);
215 return (first_set == -1);
218 /* Is the unrb full? That is, is the number of set elements equal to len? */
220 ub_full(struct unrb *ub, int len)
224 bit_ffc(ub->map, len, &first_clear);
225 return (first_clear == -1);
229 * start: ipos = -1, upos = NULL;
230 * end: ipos = -1, upos = uh
240 create_iter_unr(struct unrhdr *uh)
242 struct unrhdr_iter *iter;
244 iter = Malloc(sizeof(*iter));
248 iter->upos_first_item = -1;
253 next_iter_unrl(struct unrhdr *uh, struct unrhdr_iter *iter)
260 if (iter->ipos == -1) {
261 if (iter->upos == uh)
264 if (uh->first == 0) {
265 up = TAILQ_FIRST(&uh->head);
274 iter->upos_first_item = uh->low;
282 /* Special case for the compacted [low, first) run. */
284 if (y + 1 < uh->low + uh->first) {
288 up = iter->upos = TAILQ_FIRST(&uh->head);
289 iter->upos_first_item = uh->low + uh->first;
293 if (y + 1 < iter->upos_first_item + up->len) {
297 } else if (is_bitmap(uh, up)) {
299 bit_ffs_at(&ub->map[0],
300 y + 1 - iter->upos_first_item,
303 iter->ipos = iter->upos_first_item + c;
308 iter->upos_first_item += up->len;
309 y = iter->upos_first_item - 1;
310 up = iter->upos = TAILQ_NEXT((struct unr *)iter->upos, list);
311 if (iter->upos == NULL) {
320 * returns -1 on end, otherwise the next element
323 next_iter_unr(void *handle)
326 struct unrhdr_iter *iter;
332 next_iter_unrl(uh, iter);
339 free_iter_unr(void *handle)
344 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
346 * Consistency check function.
348 * Checks the internal consistency as well as we can.
350 * Called at all boundaries of this API.
353 check_unrhdr(struct unrhdr *uh, int line)
362 TAILQ_FOREACH(up, &uh->head, list) {
364 if (is_bitmap(uh, up)) {
366 KASSERT (up->len <= NBITS,
367 ("UNR inconsistency: len %u max %zd (line %d)\n",
368 up->len, NBITS, line));
371 bit_count(ub->map, 0, up->len, &w);
373 } else if (up->ptr != NULL)
376 KASSERT (y == uh->busy,
377 ("UNR inconsistency: items %u found %u (line %d)\n",
379 KASSERT (z == uh->alloc,
380 ("UNR inconsistency: chunks %u found %u (line %d)\n",
381 uh->alloc, z, line));
387 check_unrhdr(struct unrhdr *uh __unused, int line __unused)
395 * Userland memory management. Just use calloc and keep track of how
396 * many elements we have allocated for check_unrhdr().
399 static __inline void *
400 new_unr(struct unrhdr *uh, void **p1, void **p2)
405 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
418 delete_unr(struct unrhdr *uh, void *ptr)
424 TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
428 clean_unrhdrl(struct unrhdr *uh)
433 mtx_assert(uh->mtx, MA_OWNED);
434 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
435 TAILQ_REMOVE(&uh->ppfree, up, list);
446 clean_unrhdr(struct unrhdr *uh)
457 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
460 KASSERT(low >= 0 && low <= high,
461 ("UNR: use error: new_unrhdr(%d, %d)", low, high));
462 if (mutex == UNR_NO_MTX)
464 else if (mutex != NULL)
468 TAILQ_INIT(&uh->head);
469 TAILQ_INIT(&uh->ppfree);
473 uh->last = 1 + (high - low);
476 check_unrhdr(uh, __LINE__);
480 * Allocate a new unrheader set.
482 * Highest and lowest valid values given as parameters.
486 new_unrhdr(int low, int high, struct mtx *mutex)
490 uh = Malloc(sizeof *uh);
491 init_unrhdr(uh, low, high, mutex);
496 delete_unrhdr(struct unrhdr *uh)
499 check_unrhdr(uh, __LINE__);
500 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
501 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
502 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
503 ("unrhdr has postponed item for free"));
508 clear_unrhdr(struct unrhdr *uh)
512 KASSERT(TAILQ_EMPTY(&uh->ppfree),
513 ("unrhdr has postponed item for free"));
514 TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {
522 init_unrhdr(uh, uh->low, uh->high, uh->mtx);
524 check_unrhdr(uh, __LINE__);
528 * Look for sequence of items which can be combined into a bitmap, if
529 * multiple are present, take the one which saves most memory.
531 * Return (1) if a sequence was found to indicate that another call
532 * might be able to do more. Return (0) if we found no suitable sequence.
534 * NB: called from alloc_unr(), no new memory allocation allowed.
537 optimize_unr(struct unrhdr *uh)
539 struct unr *up, *uf, *us;
540 struct unrb *ub, *ubf;
544 * Look for the run of items (if any) which when collapsed into
545 * a bitmap would save most memory.
549 TAILQ_FOREACH(uf, &uh->head, list) {
550 if (uf->len >= NBITS)
553 if (is_bitmap(uh, uf))
558 up = TAILQ_NEXT(up, list);
561 if ((up->len + l) > NBITS)
564 if (is_bitmap(uh, up))
577 * If the first element is not a bitmap, make it one.
578 * Trying to do so without allocating more memory complicates things
581 if (!is_bitmap(uh, us)) {
582 uf = TAILQ_NEXT(us, list);
583 TAILQ_REMOVE(&uh->head, us, list);
585 l = us->ptr == uh ? 1 : 0;
587 bit_nclear(ub->map, 0, NBITS - 1);
589 bit_nset(ub->map, 0, a);
590 if (!is_bitmap(uh, uf)) {
592 bit_nclear(ub->map, a, a + uf->len - 1);
594 bit_nset(ub->map, a, a + uf->len - 1);
600 for (l = 0; l < uf->len; l++, a++) {
601 if (bit_test(ubf->map, l))
604 bit_clear(ub->map, a);
607 delete_unr(uh, uf->ptr);
614 uf = TAILQ_NEXT(us, list);
617 if (uf->len + us->len > NBITS)
619 if (uf->ptr == NULL) {
620 bit_nclear(ub->map, us->len, us->len + uf->len - 1);
622 TAILQ_REMOVE(&uh->head, uf, list);
624 } else if (uf->ptr == uh) {
625 bit_nset(ub->map, us->len, us->len + uf->len - 1);
627 TAILQ_REMOVE(&uh->head, uf, list);
631 for (l = 0; l < uf->len; l++, us->len++) {
632 if (bit_test(ubf->map, l))
633 bit_set(ub->map, us->len);
635 bit_clear(ub->map, us->len);
637 TAILQ_REMOVE(&uh->head, uf, list);
645 * See if a given unr should be collapsed with a neighbor.
647 * NB: called from alloc_unr(), no new memory allocation allowed.
650 collapse_unr(struct unrhdr *uh, struct unr *up)
655 /* If bitmap is all set or clear, change it to runlength */
656 if (is_bitmap(uh, up)) {
658 if (ub_full(ub, up->len)) {
659 delete_unr(uh, up->ptr);
661 } else if (ub_empty(ub, up->len)) {
662 delete_unr(uh, up->ptr);
667 /* If nothing left in runlength, delete it */
669 upp = TAILQ_PREV(up, unrhd, list);
671 upp = TAILQ_NEXT(up, list);
672 TAILQ_REMOVE(&uh->head, up, list);
677 /* If we have "hot-spot" still, merge with neighbor if possible */
679 upp = TAILQ_PREV(up, unrhd, list);
680 if (upp != NULL && up->ptr == upp->ptr) {
682 TAILQ_REMOVE(&uh->head, upp, list);
685 upp = TAILQ_NEXT(up, list);
686 if (upp != NULL && up->ptr == upp->ptr) {
688 TAILQ_REMOVE(&uh->head, upp, list);
693 /* Merge into ->first if possible */
694 upp = TAILQ_FIRST(&uh->head);
695 if (upp != NULL && upp->ptr == uh) {
696 uh->first += upp->len;
697 TAILQ_REMOVE(&uh->head, upp, list);
703 /* Merge into ->last if possible */
704 upp = TAILQ_LAST(&uh->head, unrhd);
705 if (upp != NULL && upp->ptr == NULL) {
706 uh->last += upp->len;
707 TAILQ_REMOVE(&uh->head, upp, list);
713 /* Try to make bitmaps */
714 while (optimize_unr(uh))
719 * Allocate a free unr.
722 alloc_unrl(struct unrhdr *uh)
730 mtx_assert(uh->mtx, MA_OWNED);
731 check_unrhdr(uh, __LINE__);
732 x = uh->low + uh->first;
734 up = TAILQ_FIRST(&uh->head);
737 * If we have an ideal split, just adjust the first+last
739 if (up == NULL && uh->last > 0) {
747 * We can always allocate from the first list element, so if we have
748 * nothing on the list, we must have run out of unit numbers.
753 KASSERT(up->ptr != uh, ("UNR first element is allocated"));
755 if (up->ptr == NULL) { /* free run */
758 } else { /* bitmap */
760 bit_ffc(ub->map, up->len, &y);
761 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
766 collapse_unr(uh, up);
771 alloc_unr(struct unrhdr *uh)
785 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
787 struct unr *up, *upn;
792 mtx_assert(uh->mtx, MA_OWNED);
794 if (item < uh->low + uh->first || item > uh->high)
797 up = TAILQ_FIRST(&uh->head);
799 if (up == NULL && item - uh->low == uh->first) {
803 check_unrhdr(uh, __LINE__);
807 i = item - uh->low - uh->first;
810 up = new_unr(uh, p1, p2);
813 TAILQ_INSERT_TAIL(&uh->head, up, list);
814 up = new_unr(uh, p1, p2);
817 TAILQ_INSERT_TAIL(&uh->head, up, list);
818 uh->last = uh->high - uh->low - i;
820 check_unrhdr(uh, __LINE__);
823 /* Find the item which contains the unit we want to allocate. */
824 TAILQ_FOREACH(up, &uh->head, list) {
833 up = new_unr(uh, p1, p2);
836 TAILQ_INSERT_TAIL(&uh->head, up, list);
838 up = new_unr(uh, p1, p2);
841 TAILQ_INSERT_TAIL(&uh->head, up, list);
845 if (is_bitmap(uh, up)) {
847 if (bit_test(ub->map, i) == 0) {
852 } else if (up->ptr == uh)
855 KASSERT(up->ptr == NULL,
856 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
858 /* Split off the tail end, if any. */
859 tl = up->len - (1 + i);
861 upn = new_unr(uh, p1, p2);
864 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
867 /* Split off head end, if any */
869 upn = new_unr(uh, p1, p2);
872 TAILQ_INSERT_BEFORE(up, upn, list);
878 last = uh->high - uh->low - (item - uh->low);
882 collapse_unr(uh, up);
883 check_unrhdr(uh, __LINE__);
888 alloc_unr_specific(struct unrhdr *uh, u_int item)
893 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
895 p1 = Malloc(sizeof(struct unr));
896 p2 = Malloc(sizeof(struct unr));
900 i = alloc_unr_specificl(uh, item, &p1, &p2);
915 * If we can save unrs by using a bitmap, do so.
918 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
920 struct unr *up, *upp, *upn;
924 KASSERT(item >= uh->low && item <= uh->high,
925 ("UNR: free_unr(%u) out of range [%u...%u]",
926 item, uh->low, uh->high));
927 check_unrhdr(uh, __LINE__);
929 upp = TAILQ_FIRST(&uh->head);
931 * Freeing in the ideal split case
933 if (item + 1 == uh->first && upp == NULL) {
937 check_unrhdr(uh, __LINE__);
941 * Freeing in the ->first section. Create a run starting at the
942 * freed item. The code below will subdivide it.
944 if (item < uh->first) {
945 up = new_unr(uh, p1, p2);
947 up->len = uh->first - item;
948 TAILQ_INSERT_HEAD(&uh->head, up, list);
949 uh->first -= up->len;
954 /* Find the item which contains the unit we want to free */
955 TAILQ_FOREACH(up, &uh->head, list) {
961 /* Handle bitmap items */
962 if (is_bitmap(uh, up)) {
965 KASSERT(bit_test(ub->map, item) != 0,
966 ("UNR: Freeing free item %d (bitmap)\n", item));
967 bit_clear(ub->map, item);
969 collapse_unr(uh, up);
973 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
975 /* Just this one left, reap it */
979 collapse_unr(uh, up);
983 /* Check if we can shift the item into the previous 'free' run */
984 upp = TAILQ_PREV(up, unrhd, list);
985 if (item == 0 && upp != NULL && upp->ptr == NULL) {
989 collapse_unr(uh, up);
993 /* Check if we can shift the item to the next 'free' run */
994 upn = TAILQ_NEXT(up, list);
995 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
999 collapse_unr(uh, up);
1003 /* Split off the tail end, if any. */
1004 pl = up->len - (1 + item);
1006 upp = new_unr(uh, p1, p2);
1009 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
1012 /* Split off head end, if any */
1014 upp = new_unr(uh, p1, p2);
1017 TAILQ_INSERT_BEFORE(up, upp, list);
1022 collapse_unr(uh, up);
1026 free_unr(struct unrhdr *uh, u_int item)
1030 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
1031 p1 = Malloc(sizeof(struct unr));
1032 p2 = Malloc(sizeof(struct unr));
1033 if (uh->mtx != NULL)
1035 free_unrl(uh, item, &p1, &p2);
1037 if (uh->mtx != NULL)
1038 mtx_unlock(uh->mtx);
1046 #include "opt_ddb.h"
1048 #include <ddb/ddb.h>
1052 #if (defined(_KERNEL) && defined(DDB)) || !defined(_KERNEL)
1054 #if !defined(_KERNEL)
1055 #define db_printf printf
1059 print_unr(struct unrhdr *uh, struct unr *up)
1064 db_printf(" %p len = %5u ", up, up->len);
1065 if (up->ptr == NULL)
1066 db_printf("free\n");
1067 else if (up->ptr == uh)
1068 db_printf("alloc\n");
1071 db_printf("bitmap [");
1072 for (x = 0; x < up->len; x++) {
1073 if (bit_test(ub->map, x))
1083 print_unrhdr(struct unrhdr *uh)
1089 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
1090 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
1091 x = uh->low + uh->first;
1092 TAILQ_FOREACH(up, &uh->head, list) {
1093 db_printf(" from = %5u", x);
1095 if (up->ptr == NULL || up->ptr == uh)
1104 #if defined(_KERNEL) && defined(DDB)
1105 DB_SHOW_COMMAND(unrhdr, unrhdr_print_unrhdr)
1108 db_printf("show unrhdr addr\n");
1112 print_unrhdr((struct unrhdr *)addr);
1116 print_unrhdr_iter(struct unrhdr_iter *iter)
1118 db_printf("iter %p unrhdr %p ipos %d upos %p ufi %d\n",
1119 iter, iter->uh, iter->ipos, iter->upos, iter->upos_first_item);
1122 DB_SHOW_COMMAND(unrhdr_iter, unrhdr_print_iter)
1125 db_printf("show unrhdr_iter addr\n");
1129 print_unrhdr_iter((struct unrhdr_iter *)addr);
1133 #ifndef _KERNEL /* USERLAND test driver */
1136 * Simple stochastic test driver for the above functions. The code resides
1137 * here so that it can access static functions and structures.
1140 static bool verbose;
1141 #define VPRINTF(...) {if (verbose) printf(__VA_ARGS__);}
1144 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
1149 VPRINTF("F %u\n", i);
1157 VPRINTF("A %d\n", j);
1164 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
1168 j = alloc_unr_specific(uh, i);
1170 VPRINTF("F %u\n", i);
1175 VPRINTF("A %d\n", j);
1184 test_iter_compar(const void *a, const void *b)
1186 return (*(const int *)a - *(const int *)b);
1190 test_iter_fill(int *vals, struct unrhdr *uh, int i, int v, int *res)
1195 x = alloc_unr_specific(uh, v);
1197 VPRINTF("alloc_unr_specific failed %d %d\n", x, v);
1208 int i, j, v, x, res;
1211 uh = new_unrhdr(TBASE, INT_MAX, NULL);
1212 for (i = 0; i < XSIZE; i++) {
1213 vals[i] = i + TBASE;
1214 x = alloc_unr_specific(uh, i + TBASE);
1215 if (x != i + TBASE) {
1216 VPRINTF("alloc_unr_specific failed %d %d\n", x,
1221 for (; i < ISIZE; i++) {
1224 v = arc4random_uniform(INT_MAX);
1227 for (j = 0; j < i; j++) {
1228 if (v == vals[j] || v + 1 == vals[j])
1233 test_iter_fill(vals, uh, i, v, &res);
1236 test_iter_fill(vals, uh, i, v, &res);
1238 qsort(vals, ISIZE, sizeof(vals[0]), test_iter_compar);
1240 ihandle = create_iter_unr(uh);
1242 while ((v = next_iter_unr(ihandle)) != -1) {
1244 VPRINTF("iter %d: iter %d != val %d\n", i, v, vals[i]);
1251 VPRINTF("iter %d: val %d\n", i, v);
1255 free_iter_unr(ihandle);
1265 printf("%s [-h] [-i] [-r REPETITIONS] [-v]\n", argv[0]);
1269 main(int argc, char **argv)
1273 long count = 10000; /* Number of unrs to test */
1280 testing_iter = false;
1282 while ((ch = getopt(argc, argv, "hir:v")) != -1) {
1285 testing_iter = true;
1289 reps = strtol(optarg, NULL, 0);
1290 if (errno == ERANGE || errno == EINVAL) {
1306 setbuf(stdout, NULL);
1311 uh = new_unrhdr(0, count - 1, NULL);
1314 a = calloc(count, sizeof(char));
1316 err(1, "calloc failed");
1318 printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
1319 printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
1320 printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
1321 printf("NBITS %lu\n", (unsigned long)NBITS);
1322 for (m = 0; m < count * reps; m++) {
1323 i = arc4random_uniform(count);
1325 if (a[i] && (j & 1))
1328 if ((arc4random() & 1) != 0)
1329 test_alloc_unr(uh, i, a);
1331 test_alloc_unr_specific(uh, i, a);
1335 check_unrhdr(uh, __LINE__);
1337 for (i = 0; i < (u_int)count; i++) {
1340 printf("C %u\n", i);