74#include <sys/_unrhdr.h>
78#include <sys/bitstring.h>
79#include <sys/malloc.h>
80#include <sys/kernel.h>
82#include <sys/limits.h>
94#define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
95#define Free(foo) free(foo, M_UNIT)
103alloc_unr64(
struct unrhdr64 *unr64)
108 item = unr64->counter++;
116#include <bitstring.h>
125#define KASSERT(cond, arg) \
134#define Malloc(foo) _Malloc(foo, __LINE__)
136_Malloc(
size_t foo,
int line)
139 KASSERT(no_alloc == 0, (
"malloc in wrong place() line %d", line));
140 return (calloc(foo, 1));
142#define Free(foo) free(foo)
151mtx_lock(
struct mtx *mp)
153 KASSERT(mp->state == 0, (
"mutex already locked"));
158mtx_unlock(
struct mtx *mp)
160 KASSERT(mp->state == 1, (
"mutex not locked"));
167mtx_assert(
struct mtx *mp,
int flag)
169 if (
flag == MA_OWNED) {
170 KASSERT(mp->state == 1, (
"mtx_assert(MA_OWNED) not true"));
175#define WITNESS_WARN(flags, lock, fmt, ...) (void)0
194 TAILQ_ENTRY(
unr) list;
200 bitstr_t
map[
sizeof(
struct unr) / sizeof(bitstr_t)];
206#define NBITS (8 * sizeof(((struct unrb*)NULL)->map))
213 bit_ffs(ub->
map, len, &first_set);
214 return (first_set == -1);
223 bit_ffc(ub->
map, len, &first_clear);
224 return (first_clear == -1);
227#if defined(DIAGNOSTIC) || !defined(_KERNEL)
245 TAILQ_FOREACH(up, &uh->head, list) {
247 if (up->ptr != uh && up->ptr != NULL) {
249 KASSERT (up->len <=
NBITS,
250 (
"UNR inconsistency: len %u max %zd (line %d)\n",
251 up->len,
NBITS, line));
254 bit_count(ub->
map, 0, up->len, &w);
256 }
else if (up->ptr != NULL)
259 KASSERT (y == uh->busy,
260 (
"UNR inconsistency: items %u found %u (line %d)\n",
262 KASSERT (z == uh->alloc,
263 (
"UNR inconsistency: chunks %u found %u (line %d)\n",
264 uh->alloc, z, line));
282static __inline
void *
283new_unr(
struct unrhdr *uh,
void **p1,
void **p2)
288 KASSERT(*p1 != NULL || *p2 != NULL, (
"Out of cached memory"));
307 TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
315 mtx_assert(uh->mtx, MA_OWNED);
316 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
317 TAILQ_REMOVE(&uh->ppfree, up, list);
338 KASSERT(low >= 0 && low <= high,
339 (
"UNR: use error: new_unrhdr(%d, %d)", low, high));
344 TAILQ_INIT(&uh->head);
345 TAILQ_INIT(&uh->ppfree);
349 uh->last = 1 + (high - low);
374 KASSERT(uh->busy == 0, (
"unrhdr has %u allocations", uh->busy));
375 KASSERT(uh->alloc == 0, (
"UNR memory leak in delete_unrhdr"));
376 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
377 (
"unrhdr has postponed item for free"));
386 KASSERT(TAILQ_EMPTY(&uh->ppfree),
387 (
"unrhdr has postponed item for free"));
388 TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {
404 return (up->ptr != uh && up->ptr != NULL);
419 struct unr *up, *uf, *us;
420 struct unrb *ub, *ubf;
429 TAILQ_FOREACH(uf, &uh->head, list) {
430 if (uf->len >=
NBITS)
438 up = TAILQ_NEXT(up, list);
441 if ((up->len + l) >
NBITS)
462 uf = TAILQ_NEXT(us, list);
463 TAILQ_REMOVE(&uh->head, us, list);
465 l = us->ptr == uh ? 1 : 0;
469 bit_nset(ub->
map, 0, a);
472 bit_nclear(ub->
map, a, a + uf->len - 1);
474 bit_nset(ub->
map, a, a + uf->len - 1);
480 for (l = 0; l < uf->len; l++, a++) {
481 if (bit_test(ubf->
map, l))
484 bit_clear(ub->
map, a);
494 uf = TAILQ_NEXT(us, list);
497 if (uf->len + us->len >
NBITS)
499 if (uf->ptr == NULL) {
500 bit_nclear(ub->
map, us->len, us->len + uf->len - 1);
502 TAILQ_REMOVE(&uh->head, uf, list);
504 }
else if (uf->ptr == uh) {
505 bit_nset(ub->
map, us->len, us->len + uf->len - 1);
507 TAILQ_REMOVE(&uh->head, uf, list);
511 for (l = 0; l < uf->len; l++, us->len++) {
512 if (bit_test(ubf->
map, l))
513 bit_set(ub->
map, us->len);
515 bit_clear(ub->
map, us->len);
517 TAILQ_REMOVE(&uh->head, uf, list);
549 upp = TAILQ_PREV(up, unrhd, list);
551 upp = TAILQ_NEXT(up, list);
552 TAILQ_REMOVE(&uh->head, up, list);
559 upp = TAILQ_PREV(up, unrhd, list);
560 if (upp != NULL && up->ptr == upp->ptr) {
562 TAILQ_REMOVE(&uh->head, upp, list);
565 upp = TAILQ_NEXT(up, list);
566 if (upp != NULL && up->ptr == upp->ptr) {
568 TAILQ_REMOVE(&uh->head, upp, list);
574 upp = TAILQ_FIRST(&uh->head);
575 if (upp != NULL && upp->ptr == uh) {
576 uh->first += upp->len;
577 TAILQ_REMOVE(&uh->head, upp, list);
584 upp = TAILQ_LAST(&uh->head, unrhd);
585 if (upp != NULL && upp->ptr == NULL) {
586 uh->last += upp->len;
587 TAILQ_REMOVE(&uh->head, upp, list);
609 mtx_assert(uh->mtx, MA_OWNED);
611 x = uh->low + uh->first;
613 up = TAILQ_FIRST(&uh->head);
618 if (up == NULL && uh->last > 0) {
632 KASSERT(up->ptr != uh, (
"UNR first element is allocated"));
634 if (up->ptr == NULL) {
639 bit_ffc(ub->
map, up->len, &y);
640 KASSERT(y != -1, (
"UNR corruption: No clear bit in bitmap."));
664 struct unr *up, *upn;
668 mtx_assert(uh->mtx, MA_OWNED);
670 if (item < uh->low + uh->first || item > uh->high)
673 up = TAILQ_FIRST(&uh->head);
675 if (up == NULL && item - uh->low == uh->first) {
683 i = item - uh->low - uh->first;
689 TAILQ_INSERT_TAIL(&uh->head, up, list);
693 TAILQ_INSERT_TAIL(&uh->head, up, list);
694 uh->last = uh->high - uh->low - i;
700 TAILQ_FOREACH(up, &uh->head, list) {
712 TAILQ_INSERT_TAIL(&uh->head, up, list);
717 TAILQ_INSERT_TAIL(&uh->head, up, list);
723 if (bit_test(ub->
map, i) == 0) {
728 }
else if (up->ptr == uh)
731 KASSERT(up->ptr == NULL,
732 (
"alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
735 tl = up->len - (1 + i);
740 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
748 TAILQ_INSERT_BEFORE(up, upn, list);
754 last = uh->high - uh->low - (item - uh->low);
769 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
"alloc_unr_specific");
792free_unrl(
struct unrhdr *uh, u_int item,
void **p1,
void **p2)
794 struct unr *up, *upp, *upn;
798 KASSERT(item >= uh->low && item <= uh->high,
799 (
"UNR: free_unr(%u) out of range [%u...%u]",
800 item, uh->low, uh->high));
803 upp = TAILQ_FIRST(&uh->head);
807 if (item + 1 == uh->first && upp == NULL) {
818 if (item < uh->first) {
821 up->len = uh->first - item;
822 TAILQ_INSERT_HEAD(&uh->head, up, list);
823 uh->first -= up->len;
829 TAILQ_FOREACH(up, &uh->head, list) {
839 KASSERT(bit_test(ub->
map, item) != 0,
840 (
"UNR: Freeing free item %d (bitmap)\n", item));
841 bit_clear(ub->
map, item);
847 KASSERT(up->ptr == uh, (
"UNR Freeing free item %d (run))\n", item));
858 upp = TAILQ_PREV(up, unrhd, list);
859 if (item == 0 && upp != NULL && upp->ptr == NULL) {
868 upn = TAILQ_NEXT(up, list);
869 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
878 pl = up->len - (1 + item);
883 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
891 TAILQ_INSERT_BEFORE(up, upp, list);
904 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
"free_unr");
925#define VPRINTF(...) {if (verbose) printf(__VA_ARGS__);}
928print_unr(
struct unrhdr *uh,
struct unr *up)
933 printf(
" %p len = %5u ", up, up->len);
936 else if (up->ptr == uh)
941 for (x = 0; x < up->len; x++) {
942 if (bit_test(ub->
map, x))
952print_unrhdr(
struct unrhdr *uh)
958 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
959 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
960 x = uh->low + uh->first;
961 TAILQ_FOREACH(up, &uh->head, list) {
964 if (up->ptr == NULL || up->ptr == uh)
972test_alloc_unr(
struct unrhdr *uh, u_int i,
char a[])
977 VPRINTF(
"F %u\n", i);
985 VPRINTF(
"A %d\n", j);
992test_alloc_unr_specific(
struct unrhdr *uh, u_int i,
char a[])
998 VPRINTF(
"F %u\n", i);
1003 VPRINTF(
"A %d\n", j);
1010 printf(
"%s [-h] [-r REPETITIONS] [-v]\n", argv[0]);
1014main(
int argc,
char **argv)
1025 while ((ch = getopt(argc, argv,
"hr:v")) != -1) {
1029 reps = strtol(optarg, NULL, 0);
1030 if (errno == ERANGE || errno == EINVAL) {
1046 setbuf(stdout, NULL);
1050 a = calloc(
count,
sizeof(
char));
1052 err(1,
"calloc failed");
1054 printf(
"sizeof(struct unr) %zu\n",
sizeof(
struct unr));
1055 printf(
"sizeof(struct unrb) %zu\n",
sizeof(
struct unrb));
1056 printf(
"sizeof(struct unrhdr) %zu\n",
sizeof(
struct unrhdr));
1058 for (m = 0; m <
count * reps; m++) {
1059 i = arc4random_uniform(
count);
1061 if (a[i] && (j & 1))
1064 if ((arc4random() & 1) != 0)
1065 test_alloc_unr(uh, i, a);
1067 test_alloc_unr_specific(uh, i, a);
1073 for (i = 0; i < (u_int)
count; i++) {
void free(void *addr, struct malloc_type *mtp)
bitstr_t map[sizeof(struct unr)/sizeof(bitstr_t)]
int printf(const char *fmt,...)
static void collapse_unr(struct unrhdr *uh, struct unr *up)
MTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF)
void clean_unrhdrl(struct unrhdr *uh)
void clear_unrhdr(struct unrhdr *uh)
static int optimize_unr(struct unrhdr *uh)
static struct mtx unitmtx
static void free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
static int alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
static bool ub_empty(struct unrb *ub, int len)
void clean_unrhdr(struct unrhdr *uh)
static __inline void delete_unr(struct unrhdr *uh, void *ptr)
int alloc_unrl(struct unrhdr *uh)
int alloc_unr(struct unrhdr *uh)
void init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
void delete_unrhdr(struct unrhdr *uh)
int alloc_unr_specific(struct unrhdr *uh, u_int item)
static __inline int is_bitmap(struct unrhdr *uh, struct unr *up)
static __inline void * new_unr(struct unrhdr *uh, void **p1, void **p2)
struct unrhdr * new_unrhdr(int low, int high, struct mtx *mutex)
void free_unr(struct unrhdr *uh, u_int item)
static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation")
static bool ub_full(struct unrb *ub, int len)
CTASSERT((sizeof(struct unr) % sizeof(bitstr_t))==0)
static __inline void check_unrhdr(struct unrhdr *uh __unused, int line __unused)