1135956Sphk/*- 2135956Sphk * Copyright (c) 2004 Poul-Henning Kamp 3135956Sphk * All rights reserved. 4135956Sphk * 5135956Sphk * Redistribution and use in source and binary forms, with or without 6135956Sphk * modification, are permitted provided that the following conditions 7135956Sphk * are met: 8135956Sphk * 1. Redistributions of source code must retain the above copyright 9135956Sphk * notice, this list of conditions and the following disclaimer. 10135956Sphk * 2. Redistributions in binary form must reproduce the above copyright 11135956Sphk * notice, this list of conditions and the following disclaimer in the 12135956Sphk * documentation and/or other materials provided with the distribution. 13135956Sphk * 14135956Sphk * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15135956Sphk * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16135956Sphk * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17135956Sphk * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18135956Sphk * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19135956Sphk * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20135956Sphk * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21135956Sphk * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22135956Sphk * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23135956Sphk * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24135956Sphk * SUCH DAMAGE. 25135956Sphk * 26135956Sphk * $FreeBSD: stable/11/sys/kern/subr_unit.c 312327 2017-01-17 01:59:42Z ngie $ 27135956Sphk * 28143283Sphk * 29143283Sphk * Unit number allocation functions. 30143283Sphk * 31135956Sphk * These functions implement a mixed run-length/bitmap management of unit 32143283Sphk * number spaces in a very memory efficient manner. 33135956Sphk * 34143283Sphk * Allocation policy is always lowest free number first. 35135956Sphk * 36143283Sphk * A return value of -1 signals that no more unit numbers are available. 37135956Sphk * 38143283Sphk * There is no cost associated with the range of unitnumbers, so unless 39143283Sphk * the resource really is finite, specify INT_MAX to new_unrhdr() and 40143283Sphk * forget about checking the return value. 41135956Sphk * 42143283Sphk * If a mutex is not provided when the unit number space is created, a 43143283Sphk * default global mutex is used. The advantage to passing a mutex in, is 44218909Sbrucec * that the alloc_unrl() function can be called with the mutex already 45143283Sphk * held (it will not be released by alloc_unrl()). 46135956Sphk * 47143283Sphk * The allocation function alloc_unr{l}() never sleeps (but it may block on 48143283Sphk * the mutex of course). 49143283Sphk * 50143283Sphk * Freeing a unit number may require allocating memory, and can therefore 51143283Sphk * sleep so the free_unr() function does not come in a pre-locked variant. 52143283Sphk * 53135956Sphk * A userland test program is included. 54135956Sphk * 55218909Sbrucec * Memory usage is a very complex function of the exact allocation 56143283Sphk * pattern, but always very compact: 57143283Sphk * * For the very typical case where a single unbroken run of unit 58143283Sphk * numbers are allocated 44 bytes are used on i386. 59143283Sphk * * For a unit number space of 1000 units and the random pattern 60143283Sphk * in the usermode test program included, the worst case usage 61143283Sphk * was 252 bytes on i386 for 500 allocated and 500 free units. 62143283Sphk * * For a unit number space of 10000 units and the random pattern 63143283Sphk * in the usermode test program included, the worst case usage 64143283Sphk * was 798 bytes on i386 for 5000 allocated and 5000 free units. 65143283Sphk * * The worst case is where every other unit number is allocated and 66240518Seadler * the rest are free. In that case 44 + N/4 bytes are used where 67143283Sphk * N is the number of the highest unit allocated. 68135956Sphk */ 69135956Sphk 70299090Sasomers#include <sys/param.h> 71135956Sphk#include <sys/types.h> 72255057Skib#include <sys/_unrhdr.h> 73135956Sphk 74135956Sphk#ifdef _KERNEL 75135956Sphk 76298811Sasomers#include <sys/bitstring.h> 77135956Sphk#include <sys/malloc.h> 78135956Sphk#include <sys/kernel.h> 79135956Sphk#include <sys/systm.h> 80143283Sphk#include <sys/limits.h> 81143283Sphk#include <sys/lock.h> 82143283Sphk#include <sys/mutex.h> 83135956Sphk 84135956Sphk/* 85135956Sphk * In theory it would be smarter to allocate the individual blocks 86135956Sphk * with the zone allocator, but at this time the expectation is that 87135956Sphk * there will typically not even be enough allocations to fill a single 88135956Sphk * page, so we stick with malloc for now. 89135956Sphk */ 90135956Sphkstatic MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation"); 91135956Sphk 92135956Sphk#define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO) 93135956Sphk#define Free(foo) free(foo, M_UNIT) 94135956Sphk 95143283Sphkstatic struct mtx unitmtx; 96143283Sphk 97143283SphkMTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF); 98143283Sphk 99135956Sphk#else /* ...USERLAND */ 100135956Sphk 101298811Sasomers#include <bitstring.h> 102298811Sasomers#include <err.h> 103298811Sasomers#include <errno.h> 104298811Sasomers#include <getopt.h> 105298811Sasomers#include <stdbool.h> 106135956Sphk#include <stdio.h> 107135956Sphk#include <stdlib.h> 108143283Sphk#include <string.h> 109135956Sphk 110135956Sphk#define KASSERT(cond, arg) \ 111135956Sphk do { \ 112135956Sphk if (!(cond)) { \ 113135956Sphk printf arg; \ 114143283Sphk abort(); \ 115135956Sphk } \ 116135956Sphk } while (0) 117135956Sphk 118143283Sphkstatic int no_alloc; 119143283Sphk#define Malloc(foo) _Malloc(foo, __LINE__) 120143283Sphkstatic void * 121143283Sphk_Malloc(size_t foo, int line) 122143283Sphk{ 123143283Sphk 124143283Sphk KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line)); 125143283Sphk return (calloc(foo, 1)); 126143283Sphk} 127135956Sphk#define Free(foo) free(foo) 128135956Sphk 129143283Sphkstruct unrhdr; 130135956Sphk 131143283Sphk 132143283Sphkstruct mtx { 133143283Sphk int state; 134143283Sphk} unitmtx; 135143283Sphk 136143283Sphkstatic void 137143283Sphkmtx_lock(struct mtx *mp) 138143283Sphk{ 139143283Sphk KASSERT(mp->state == 0, ("mutex already locked")); 140143283Sphk mp->state = 1; 141143283Sphk} 142143283Sphk 143143283Sphkstatic void 144143283Sphkmtx_unlock(struct mtx *mp) 145143283Sphk{ 146143283Sphk KASSERT(mp->state == 1, ("mutex not locked")); 147143283Sphk mp->state = 0; 148143283Sphk} 149143283Sphk 150143283Sphk#define MA_OWNED 9 151143283Sphk 152143283Sphkstatic void 153143283Sphkmtx_assert(struct mtx *mp, int flag) 154143283Sphk{ 155143283Sphk if (flag == MA_OWNED) { 156143283Sphk KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true")); 157143283Sphk } 158143283Sphk} 159143283Sphk 160143283Sphk#define CTASSERT(foo) 161209256Sjh#define WITNESS_WARN(flags, lock, fmt, ...) (void)0 162143283Sphk 163143283Sphk#endif /* USERLAND */ 164143283Sphk 165135956Sphk/* 166135956Sphk * This is our basic building block. 167135956Sphk * 168135956Sphk * It can be used in three different ways depending on the value of the ptr 169135956Sphk * element: 170135956Sphk * If ptr is NULL, it represents a run of free items. 171135956Sphk * If ptr points to the unrhdr it represents a run of allocated items. 172299090Sasomers * Otherwise it points to a bitstring of allocated items. 173135956Sphk * 174135956Sphk * For runs the len field is the length of the run. 175135956Sphk * For bitmaps the len field represents the number of allocated items. 176135956Sphk * 177135956Sphk * The bitmap is the same size as struct unr to optimize memory management. 178135956Sphk */ 179135956Sphkstruct unr { 180135956Sphk TAILQ_ENTRY(unr) list; 181135956Sphk u_int len; 182135956Sphk void *ptr; 183135956Sphk}; 184135956Sphk 185143283Sphkstruct unrb { 186299090Sasomers bitstr_t map[sizeof(struct unr) / sizeof(bitstr_t)]; 187143283Sphk}; 188143283Sphk 189299090SasomersCTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0); 190143283Sphk 191299090Sasomers/* Number of bits we can store in the bitmap */ 192299090Sasomers#define NBITS (8 * sizeof(((struct unrb*)NULL)->map)) 193135956Sphk 194299090Sasomers/* Is the unrb empty in at least the first len bits? */ 195299090Sasomersstatic inline bool 196299090Sasomersub_empty(struct unrb *ub, int len) { 197299090Sasomers int first_set; 198299090Sasomers 199299090Sasomers bit_ffs(ub->map, len, &first_set); 200299090Sasomers return (first_set == -1); 201299090Sasomers} 202299090Sasomers 203299090Sasomers/* Is the unrb full? That is, is the number of set elements equal to len? */ 204299090Sasomersstatic inline bool 205299090Sasomersub_full(struct unrb *ub, int len) 206299090Sasomers{ 207299090Sasomers int first_clear; 208299090Sasomers 209299090Sasomers bit_ffc(ub->map, len, &first_clear); 210299090Sasomers return (first_clear == -1); 211299090Sasomers} 212299090Sasomers 213299090Sasomers 214135956Sphk#if defined(DIAGNOSTIC) || !defined(_KERNEL) 215135956Sphk/* 216135956Sphk * Consistency check function. 217135956Sphk * 218135956Sphk * Checks the internal consistency as well as we can. 219312327Sngie * 220135956Sphk * Called at all boundaries of this API. 221135956Sphk */ 222135956Sphkstatic void 223135956Sphkcheck_unrhdr(struct unrhdr *uh, int line) 224135956Sphk{ 225135956Sphk struct unr *up; 226143283Sphk struct unrb *ub; 227300539Sasomers int w; 228300539Sasomers u_int y, z; 229135956Sphk 230143283Sphk y = uh->first; 231135956Sphk z = 0; 232135956Sphk TAILQ_FOREACH(up, &uh->head, list) { 233135956Sphk z++; 234135956Sphk if (up->ptr != uh && up->ptr != NULL) { 235143283Sphk ub = up->ptr; 236143283Sphk KASSERT (up->len <= NBITS, 237299090Sasomers ("UNR inconsistency: len %u max %zd (line %d)\n", 238143283Sphk up->len, NBITS, line)); 239135956Sphk z++; 240135956Sphk w = 0; 241300539Sasomers bit_count(ub->map, 0, up->len, &w); 242143283Sphk y += w; 243312327Sngie } else if (up->ptr != NULL) 244135956Sphk y += up->len; 245135956Sphk } 246135956Sphk KASSERT (y == uh->busy, 247135956Sphk ("UNR inconsistency: items %u found %u (line %d)\n", 248135956Sphk uh->busy, y, line)); 249135956Sphk KASSERT (z == uh->alloc, 250135956Sphk ("UNR inconsistency: chunks %u found %u (line %d)\n", 251135956Sphk uh->alloc, z, line)); 252135956Sphk} 253135956Sphk 254135956Sphk#else 255135956Sphk 256135956Sphkstatic __inline void 257299090Sasomerscheck_unrhdr(struct unrhdr *uh __unused, int line __unused) 258135956Sphk{ 259135956Sphk 260135956Sphk} 261135956Sphk 262135956Sphk#endif 263135956Sphk 264135956Sphk 265135956Sphk/* 266135956Sphk * Userland memory management. Just use calloc and keep track of how 267135956Sphk * many elements we have allocated for check_unrhdr(). 268135956Sphk */ 269135956Sphk 270135956Sphkstatic __inline void * 271143283Sphknew_unr(struct unrhdr *uh, void **p1, void **p2) 272135956Sphk{ 273143283Sphk void *p; 274143283Sphk 275135956Sphk uh->alloc++; 276143283Sphk KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory")); 277143283Sphk if (*p1 != NULL) { 278143283Sphk p = *p1; 279143283Sphk *p1 = NULL; 280143283Sphk return (p); 281143283Sphk } else { 282143283Sphk p = *p2; 283143283Sphk *p2 = NULL; 284143283Sphk return (p); 285143283Sphk } 286135956Sphk} 287135956Sphk 288135956Sphkstatic __inline void 289135956Sphkdelete_unr(struct unrhdr *uh, void *ptr) 290135956Sphk{ 291171202Skib struct unr *up; 292143283Sphk 293135956Sphk uh->alloc--; 294171202Skib up = ptr; 295171202Skib TAILQ_INSERT_TAIL(&uh->ppfree, up, list); 296135956Sphk} 297135956Sphk 298171202Skibvoid 299171202Skibclean_unrhdrl(struct unrhdr *uh) 300171202Skib{ 301171202Skib struct unr *up; 302171202Skib 303171202Skib mtx_assert(uh->mtx, MA_OWNED); 304171202Skib while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) { 305171202Skib TAILQ_REMOVE(&uh->ppfree, up, list); 306171202Skib mtx_unlock(uh->mtx); 307171202Skib Free(up); 308171202Skib mtx_lock(uh->mtx); 309171202Skib } 310171202Skib 311171202Skib} 312171202Skib 313171202Skibvoid 314171202Skibclean_unrhdr(struct unrhdr *uh) 315171202Skib{ 316171202Skib 317171202Skib mtx_lock(uh->mtx); 318171202Skib clean_unrhdrl(uh); 319171202Skib mtx_unlock(uh->mtx); 320171202Skib} 321171202Skib 322255057Skibvoid 323255057Skibinit_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex) 324135956Sphk{ 325135956Sphk 326209844Sjh KASSERT(low >= 0 && low <= high, 327209816Sjh ("UNR: use error: new_unrhdr(%d, %d)", low, high)); 328143283Sphk if (mutex != NULL) 329143283Sphk uh->mtx = mutex; 330143283Sphk else 331143283Sphk uh->mtx = &unitmtx; 332135956Sphk TAILQ_INIT(&uh->head); 333171202Skib TAILQ_INIT(&uh->ppfree); 334135956Sphk uh->low = low; 335135956Sphk uh->high = high; 336143283Sphk uh->first = 0; 337143283Sphk uh->last = 1 + (high - low); 338135956Sphk check_unrhdr(uh, __LINE__); 339255057Skib} 340255057Skib 341255057Skib/* 342255057Skib * Allocate a new unrheader set. 343255057Skib * 344255057Skib * Highest and lowest valid values given as parameters. 345255057Skib */ 346255057Skib 347255057Skibstruct unrhdr * 348255057Skibnew_unrhdr(int low, int high, struct mtx *mutex) 349255057Skib{ 350255057Skib struct unrhdr *uh; 351255057Skib 352255057Skib uh = Malloc(sizeof *uh); 353255057Skib init_unrhdr(uh, low, high, mutex); 354135956Sphk return (uh); 355135956Sphk} 356135956Sphk 357136945Sphkvoid 358136945Sphkdelete_unrhdr(struct unrhdr *uh) 359136945Sphk{ 360136945Sphk 361143283Sphk check_unrhdr(uh, __LINE__); 362136945Sphk KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy)); 363136945Sphk KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr")); 364171202Skib KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL, 365171202Skib ("unrhdr has postponed item for free")); 366136945Sphk Free(uh); 367136945Sphk} 368136945Sphk 369143283Sphkstatic __inline int 370143283Sphkis_bitmap(struct unrhdr *uh, struct unr *up) 371143283Sphk{ 372143283Sphk return (up->ptr != uh && up->ptr != NULL); 373143283Sphk} 374143283Sphk 375135956Sphk/* 376143283Sphk * Look for sequence of items which can be combined into a bitmap, if 377143283Sphk * multiple are present, take the one which saves most memory. 378312327Sngie * 379143283Sphk * Return (1) if a sequence was found to indicate that another call 380143283Sphk * might be able to do more. Return (0) if we found no suitable sequence. 381143283Sphk * 382143283Sphk * NB: called from alloc_unr(), no new memory allocation allowed. 383135956Sphk */ 384143283Sphkstatic int 385143283Sphkoptimize_unr(struct unrhdr *uh) 386143283Sphk{ 387143283Sphk struct unr *up, *uf, *us; 388143283Sphk struct unrb *ub, *ubf; 389143283Sphk u_int a, l, ba; 390143283Sphk 391143283Sphk /* 392143283Sphk * Look for the run of items (if any) which when collapsed into 393143283Sphk * a bitmap would save most memory. 394143283Sphk */ 395143283Sphk us = NULL; 396143283Sphk ba = 0; 397143283Sphk TAILQ_FOREACH(uf, &uh->head, list) { 398143283Sphk if (uf->len >= NBITS) 399143283Sphk continue; 400143283Sphk a = 1; 401143283Sphk if (is_bitmap(uh, uf)) 402143283Sphk a++; 403143283Sphk l = uf->len; 404143283Sphk up = uf; 405143283Sphk while (1) { 406143283Sphk up = TAILQ_NEXT(up, list); 407143283Sphk if (up == NULL) 408143283Sphk break; 409143283Sphk if ((up->len + l) > NBITS) 410143283Sphk break; 411143283Sphk a++; 412143283Sphk if (is_bitmap(uh, up)) 413143283Sphk a++; 414143283Sphk l += up->len; 415143283Sphk } 416143283Sphk if (a > ba) { 417143283Sphk ba = a; 418143283Sphk us = uf; 419143283Sphk } 420143283Sphk } 421143283Sphk if (ba < 3) 422143283Sphk return (0); 423143283Sphk 424143283Sphk /* 425143283Sphk * If the first element is not a bitmap, make it one. 426143283Sphk * Trying to do so without allocating more memory complicates things 427143283Sphk * a bit 428143283Sphk */ 429143283Sphk if (!is_bitmap(uh, us)) { 430143283Sphk uf = TAILQ_NEXT(us, list); 431143283Sphk TAILQ_REMOVE(&uh->head, us, list); 432143283Sphk a = us->len; 433143283Sphk l = us->ptr == uh ? 1 : 0; 434143283Sphk ub = (void *)us; 435299090Sasomers bit_nclear(ub->map, 0, NBITS - 1); 436299090Sasomers if (l) 437143283Sphk bit_nset(ub->map, 0, a); 438143283Sphk if (!is_bitmap(uh, uf)) { 439299090Sasomers if (uf->ptr == NULL) 440143283Sphk bit_nclear(ub->map, a, a + uf->len - 1); 441299090Sasomers else 442143283Sphk bit_nset(ub->map, a, a + uf->len - 1); 443143283Sphk uf->ptr = ub; 444143283Sphk uf->len += a; 445143283Sphk us = uf; 446143283Sphk } else { 447143283Sphk ubf = uf->ptr; 448143283Sphk for (l = 0; l < uf->len; l++, a++) { 449299090Sasomers if (bit_test(ubf->map, l)) 450143283Sphk bit_set(ub->map, a); 451299090Sasomers else 452143283Sphk bit_clear(ub->map, a); 453143283Sphk } 454143283Sphk uf->len = a; 455143283Sphk delete_unr(uh, uf->ptr); 456143283Sphk uf->ptr = ub; 457143283Sphk us = uf; 458143283Sphk } 459143283Sphk } 460143283Sphk ub = us->ptr; 461143283Sphk while (1) { 462143283Sphk uf = TAILQ_NEXT(us, list); 463143283Sphk if (uf == NULL) 464143283Sphk return (1); 465143283Sphk if (uf->len + us->len > NBITS) 466143283Sphk return (1); 467143283Sphk if (uf->ptr == NULL) { 468143283Sphk bit_nclear(ub->map, us->len, us->len + uf->len - 1); 469143283Sphk us->len += uf->len; 470143283Sphk TAILQ_REMOVE(&uh->head, uf, list); 471143283Sphk delete_unr(uh, uf); 472143283Sphk } else if (uf->ptr == uh) { 473143283Sphk bit_nset(ub->map, us->len, us->len + uf->len - 1); 474143283Sphk us->len += uf->len; 475143283Sphk TAILQ_REMOVE(&uh->head, uf, list); 476143283Sphk delete_unr(uh, uf); 477143283Sphk } else { 478143283Sphk ubf = uf->ptr; 479143283Sphk for (l = 0; l < uf->len; l++, us->len++) { 480299090Sasomers if (bit_test(ubf->map, l)) 481143283Sphk bit_set(ub->map, us->len); 482299090Sasomers else 483143283Sphk bit_clear(ub->map, us->len); 484143283Sphk } 485143283Sphk TAILQ_REMOVE(&uh->head, uf, list); 486143283Sphk delete_unr(uh, ubf); 487143283Sphk delete_unr(uh, uf); 488143283Sphk } 489143283Sphk } 490143283Sphk} 491143283Sphk 492143283Sphk/* 493143283Sphk * See if a given unr should be collapsed with a neighbor. 494143283Sphk * 495143283Sphk * NB: called from alloc_unr(), no new memory allocation allowed. 496143283Sphk */ 497135956Sphkstatic void 498135956Sphkcollapse_unr(struct unrhdr *uh, struct unr *up) 499135956Sphk{ 500135956Sphk struct unr *upp; 501143283Sphk struct unrb *ub; 502135956Sphk 503143283Sphk /* If bitmap is all set or clear, change it to runlength */ 504143283Sphk if (is_bitmap(uh, up)) { 505143283Sphk ub = up->ptr; 506299090Sasomers if (ub_full(ub, up->len)) { 507143283Sphk delete_unr(uh, up->ptr); 508143283Sphk up->ptr = uh; 509299090Sasomers } else if (ub_empty(ub, up->len)) { 510143283Sphk delete_unr(uh, up->ptr); 511143283Sphk up->ptr = NULL; 512143283Sphk } 513143283Sphk } 514143283Sphk 515143283Sphk /* If nothing left in runlength, delete it */ 516143283Sphk if (up->len == 0) { 517143283Sphk upp = TAILQ_PREV(up, unrhd, list); 518143283Sphk if (upp == NULL) 519143283Sphk upp = TAILQ_NEXT(up, list); 520143283Sphk TAILQ_REMOVE(&uh->head, up, list); 521143283Sphk delete_unr(uh, up); 522143283Sphk up = upp; 523143283Sphk } 524143283Sphk 525143283Sphk /* If we have "hot-spot" still, merge with neighbor if possible */ 526143283Sphk if (up != NULL) { 527143283Sphk upp = TAILQ_PREV(up, unrhd, list); 528143283Sphk if (upp != NULL && up->ptr == upp->ptr) { 529143283Sphk up->len += upp->len; 530143283Sphk TAILQ_REMOVE(&uh->head, upp, list); 531143283Sphk delete_unr(uh, upp); 532143283Sphk } 533143283Sphk upp = TAILQ_NEXT(up, list); 534143283Sphk if (upp != NULL && up->ptr == upp->ptr) { 535143283Sphk up->len += upp->len; 536143283Sphk TAILQ_REMOVE(&uh->head, upp, list); 537143283Sphk delete_unr(uh, upp); 538143283Sphk } 539143283Sphk } 540143283Sphk 541143283Sphk /* Merge into ->first if possible */ 542143283Sphk upp = TAILQ_FIRST(&uh->head); 543143283Sphk if (upp != NULL && upp->ptr == uh) { 544143283Sphk uh->first += upp->len; 545135956Sphk TAILQ_REMOVE(&uh->head, upp, list); 546135956Sphk delete_unr(uh, upp); 547143283Sphk if (up == upp) 548143283Sphk up = NULL; 549135956Sphk } 550143283Sphk 551143283Sphk /* Merge into ->last if possible */ 552143283Sphk upp = TAILQ_LAST(&uh->head, unrhd); 553143283Sphk if (upp != NULL && upp->ptr == NULL) { 554143283Sphk uh->last += upp->len; 555135956Sphk TAILQ_REMOVE(&uh->head, upp, list); 556135956Sphk delete_unr(uh, upp); 557143283Sphk if (up == upp) 558143283Sphk up = NULL; 559135956Sphk } 560143283Sphk 561143283Sphk /* Try to make bitmaps */ 562143283Sphk while (optimize_unr(uh)) 563143283Sphk continue; 564135956Sphk} 565135956Sphk 566135956Sphk/* 567135956Sphk * Allocate a free unr. 568135956Sphk */ 569143283Sphkint 570143283Sphkalloc_unrl(struct unrhdr *uh) 571135956Sphk{ 572143283Sphk struct unr *up; 573143283Sphk struct unrb *ub; 574135956Sphk u_int x; 575135956Sphk int y; 576135956Sphk 577143283Sphk mtx_assert(uh->mtx, MA_OWNED); 578135956Sphk check_unrhdr(uh, __LINE__); 579143283Sphk x = uh->low + uh->first; 580143283Sphk 581143283Sphk up = TAILQ_FIRST(&uh->head); 582143283Sphk 583135956Sphk /* 584143283Sphk * If we have an ideal split, just adjust the first+last 585135956Sphk */ 586143283Sphk if (up == NULL && uh->last > 0) { 587143283Sphk uh->first++; 588143283Sphk uh->last--; 589135956Sphk uh->busy++; 590135956Sphk return (x); 591135956Sphk } 592135956Sphk 593135956Sphk /* 594312327Sngie * We can always allocate from the first list element, so if we have 595143283Sphk * nothing on the list, we must have run out of unit numbers. 596135956Sphk */ 597143550Sphk if (up == NULL) 598143283Sphk return (-1); 599143283Sphk 600143283Sphk KASSERT(up->ptr != uh, ("UNR first element is allocated")); 601143283Sphk 602143283Sphk if (up->ptr == NULL) { /* free run */ 603143283Sphk uh->first++; 604143283Sphk up->len--; 605143283Sphk } else { /* bitmap */ 606143283Sphk ub = up->ptr; 607143283Sphk bit_ffc(ub->map, up->len, &y); 608143283Sphk KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap.")); 609143283Sphk bit_set(ub->map, y); 610143283Sphk x += y; 611143283Sphk } 612135956Sphk uh->busy++; 613143283Sphk collapse_unr(uh, up); 614135956Sphk return (x); 615135956Sphk} 616135956Sphk 617143283Sphkint 618143283Sphkalloc_unr(struct unrhdr *uh) 619143283Sphk{ 620143283Sphk int i; 621143283Sphk 622143283Sphk mtx_lock(uh->mtx); 623143283Sphk i = alloc_unrl(uh); 624171202Skib clean_unrhdrl(uh); 625143283Sphk mtx_unlock(uh->mtx); 626143283Sphk return (i); 627143283Sphk} 628143283Sphk 629209710Sjhstatic int 630209710Sjhalloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2) 631209710Sjh{ 632209710Sjh struct unr *up, *upn; 633209710Sjh struct unrb *ub; 634209710Sjh u_int i, last, tl; 635209710Sjh 636209710Sjh mtx_assert(uh->mtx, MA_OWNED); 637209710Sjh 638209710Sjh if (item < uh->low + uh->first || item > uh->high) 639209710Sjh return (-1); 640209710Sjh 641209710Sjh up = TAILQ_FIRST(&uh->head); 642209710Sjh /* Ideal split. */ 643209710Sjh if (up == NULL && item - uh->low == uh->first) { 644209710Sjh uh->first++; 645209710Sjh uh->last--; 646209710Sjh uh->busy++; 647209710Sjh check_unrhdr(uh, __LINE__); 648209710Sjh return (item); 649209710Sjh } 650209710Sjh 651209710Sjh i = item - uh->low - uh->first; 652209710Sjh 653209710Sjh if (up == NULL) { 654209710Sjh up = new_unr(uh, p1, p2); 655209710Sjh up->ptr = NULL; 656209710Sjh up->len = i; 657209710Sjh TAILQ_INSERT_TAIL(&uh->head, up, list); 658209710Sjh up = new_unr(uh, p1, p2); 659209710Sjh up->ptr = uh; 660209710Sjh up->len = 1; 661209710Sjh TAILQ_INSERT_TAIL(&uh->head, up, list); 662209710Sjh uh->last = uh->high - uh->low - i; 663209710Sjh uh->busy++; 664209710Sjh check_unrhdr(uh, __LINE__); 665209710Sjh return (item); 666209710Sjh } else { 667209710Sjh /* Find the item which contains the unit we want to allocate. */ 668209710Sjh TAILQ_FOREACH(up, &uh->head, list) { 669209710Sjh if (up->len > i) 670209710Sjh break; 671209710Sjh i -= up->len; 672209710Sjh } 673209710Sjh } 674209710Sjh 675209710Sjh if (up == NULL) { 676209710Sjh if (i > 0) { 677209710Sjh up = new_unr(uh, p1, p2); 678209710Sjh up->ptr = NULL; 679209710Sjh up->len = i; 680209710Sjh TAILQ_INSERT_TAIL(&uh->head, up, list); 681209710Sjh } 682209710Sjh up = new_unr(uh, p1, p2); 683209710Sjh up->ptr = uh; 684209710Sjh up->len = 1; 685209710Sjh TAILQ_INSERT_TAIL(&uh->head, up, list); 686209710Sjh goto done; 687209710Sjh } 688209710Sjh 689209710Sjh if (is_bitmap(uh, up)) { 690209710Sjh ub = up->ptr; 691209710Sjh if (bit_test(ub->map, i) == 0) { 692209710Sjh bit_set(ub->map, i); 693209710Sjh goto done; 694209710Sjh } else 695209710Sjh return (-1); 696209710Sjh } else if (up->ptr == uh) 697209710Sjh return (-1); 698209710Sjh 699209710Sjh KASSERT(up->ptr == NULL, 700209710Sjh ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up)); 701209710Sjh 702209710Sjh /* Split off the tail end, if any. */ 703209710Sjh tl = up->len - (1 + i); 704209710Sjh if (tl > 0) { 705209710Sjh upn = new_unr(uh, p1, p2); 706209710Sjh upn->ptr = NULL; 707209710Sjh upn->len = tl; 708209710Sjh TAILQ_INSERT_AFTER(&uh->head, up, upn, list); 709209710Sjh } 710209710Sjh 711209710Sjh /* Split off head end, if any */ 712209710Sjh if (i > 0) { 713209710Sjh upn = new_unr(uh, p1, p2); 714209710Sjh upn->len = i; 715209710Sjh upn->ptr = NULL; 716209710Sjh TAILQ_INSERT_BEFORE(up, upn, list); 717209710Sjh } 718209710Sjh up->len = 1; 719209710Sjh up->ptr = uh; 720209710Sjh 721209710Sjhdone: 722209710Sjh last = uh->high - uh->low - (item - uh->low); 723209710Sjh if (uh->last > last) 724209710Sjh uh->last = last; 725209710Sjh uh->busy++; 726209710Sjh collapse_unr(uh, up); 727209710Sjh check_unrhdr(uh, __LINE__); 728209710Sjh return (item); 729209710Sjh} 730209710Sjh 731209710Sjhint 732209710Sjhalloc_unr_specific(struct unrhdr *uh, u_int item) 733209710Sjh{ 734209710Sjh void *p1, *p2; 735209710Sjh int i; 736209710Sjh 737209710Sjh WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific"); 738209710Sjh 739209710Sjh p1 = Malloc(sizeof(struct unr)); 740209710Sjh p2 = Malloc(sizeof(struct unr)); 741209710Sjh 742209710Sjh mtx_lock(uh->mtx); 743209710Sjh i = alloc_unr_specificl(uh, item, &p1, &p2); 744209710Sjh mtx_unlock(uh->mtx); 745209710Sjh 746209710Sjh if (p1 != NULL) 747209710Sjh Free(p1); 748209710Sjh if (p2 != NULL) 749209710Sjh Free(p2); 750209710Sjh 751209710Sjh return (i); 752209710Sjh} 753209710Sjh 754135956Sphk/* 755135956Sphk * Free a unr. 756135956Sphk * 757135956Sphk * If we can save unrs by using a bitmap, do so. 758135956Sphk */ 759143283Sphkstatic void 760143283Sphkfree_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2) 761135956Sphk{ 762143283Sphk struct unr *up, *upp, *upn; 763143283Sphk struct unrb *ub; 764143283Sphk u_int pl; 765135956Sphk 766135956Sphk KASSERT(item >= uh->low && item <= uh->high, 767135956Sphk ("UNR: free_unr(%u) out of range [%u...%u]", 768135956Sphk item, uh->low, uh->high)); 769135956Sphk check_unrhdr(uh, __LINE__); 770135956Sphk item -= uh->low; 771143283Sphk upp = TAILQ_FIRST(&uh->head); 772143283Sphk /* 773143283Sphk * Freeing in the ideal split case 774143283Sphk */ 775143283Sphk if (item + 1 == uh->first && upp == NULL) { 776143283Sphk uh->last++; 777143283Sphk uh->first--; 778143283Sphk uh->busy--; 779143283Sphk check_unrhdr(uh, __LINE__); 780143283Sphk return; 781143283Sphk } 782143283Sphk /* 783143283Sphk * Freeing in the ->first section. Create a run starting at the 784143283Sphk * freed item. The code below will subdivide it. 785143283Sphk */ 786143283Sphk if (item < uh->first) { 787143283Sphk up = new_unr(uh, p1, p2); 788143283Sphk up->ptr = uh; 789143283Sphk up->len = uh->first - item; 790143283Sphk TAILQ_INSERT_HEAD(&uh->head, up, list); 791143283Sphk uh->first -= up->len; 792143283Sphk } 793135956Sphk 794143283Sphk item -= uh->first; 795135956Sphk 796143283Sphk /* Find the item which contains the unit we want to free */ 797143283Sphk TAILQ_FOREACH(up, &uh->head, list) { 798143283Sphk if (up->len > item) 799143283Sphk break; 800143283Sphk item -= up->len; 801143283Sphk } 802135956Sphk 803143283Sphk /* Handle bitmap items */ 804143283Sphk if (is_bitmap(uh, up)) { 805143283Sphk ub = up->ptr; 806312327Sngie 807143283Sphk KASSERT(bit_test(ub->map, item) != 0, 808143283Sphk ("UNR: Freeing free item %d (bitmap)\n", item)); 809143283Sphk bit_clear(ub->map, item); 810143283Sphk uh->busy--; 811143283Sphk collapse_unr(uh, up); 812143283Sphk return; 813143283Sphk } 814135956Sphk 815143283Sphk KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item)); 816135956Sphk 817143283Sphk /* Just this one left, reap it */ 818143283Sphk if (up->len == 1) { 819143283Sphk up->ptr = NULL; 820143283Sphk uh->busy--; 821143283Sphk collapse_unr(uh, up); 822143283Sphk return; 823143283Sphk } 824135956Sphk 825143283Sphk /* Check if we can shift the item into the previous 'free' run */ 826143283Sphk upp = TAILQ_PREV(up, unrhd, list); 827143283Sphk if (item == 0 && upp != NULL && upp->ptr == NULL) { 828143283Sphk upp->len++; 829143283Sphk up->len--; 830143283Sphk uh->busy--; 831143283Sphk collapse_unr(uh, up); 832143283Sphk return; 833143283Sphk } 834135956Sphk 835143283Sphk /* Check if we can shift the item to the next 'free' run */ 836143283Sphk upn = TAILQ_NEXT(up, list); 837143283Sphk if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) { 838143283Sphk upn->len++; 839143283Sphk up->len--; 840135956Sphk uh->busy--; 841143283Sphk collapse_unr(uh, up); 842143283Sphk return; 843143283Sphk } 844135956Sphk 845143283Sphk /* Split off the tail end, if any. */ 846143283Sphk pl = up->len - (1 + item); 847143283Sphk if (pl > 0) { 848143283Sphk upp = new_unr(uh, p1, p2); 849143283Sphk upp->ptr = uh; 850143283Sphk upp->len = pl; 851143283Sphk TAILQ_INSERT_AFTER(&uh->head, up, upp, list); 852143283Sphk } 853135956Sphk 854143283Sphk /* Split off head end, if any */ 855143283Sphk if (item > 0) { 856143283Sphk upp = new_unr(uh, p1, p2); 857143283Sphk upp->len = item; 858143283Sphk upp->ptr = uh; 859143283Sphk TAILQ_INSERT_BEFORE(up, upp, list); 860143283Sphk } 861143283Sphk up->len = 1; 862143283Sphk up->ptr = NULL; 863143283Sphk uh->busy--; 864143283Sphk collapse_unr(uh, up); 865143283Sphk} 866135956Sphk 867143283Sphkvoid 868143283Sphkfree_unr(struct unrhdr *uh, u_int item) 869143283Sphk{ 870143283Sphk void *p1, *p2; 871135956Sphk 872170949Skib WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr"); 873143283Sphk p1 = Malloc(sizeof(struct unr)); 874143283Sphk p2 = Malloc(sizeof(struct unr)); 875143283Sphk mtx_lock(uh->mtx); 876143283Sphk free_unrl(uh, item, &p1, &p2); 877171202Skib clean_unrhdrl(uh); 878143283Sphk mtx_unlock(uh->mtx); 879143283Sphk if (p1 != NULL) 880143283Sphk Free(p1); 881143283Sphk if (p2 != NULL) 882143283Sphk Free(p2); 883135956Sphk} 884135956Sphk 885143550Sphk#ifndef _KERNEL /* USERLAND test driver */ 886143550Sphk 887135956Sphk/* 888298811Sasomers * Simple stochastic test driver for the above functions. The code resides 889298811Sasomers * here so that it can access static functions and structures. 890135956Sphk */ 891135956Sphk 892298811Sasomersstatic bool verbose; 893298811Sasomers#define VPRINTF(...) {if (verbose) printf(__VA_ARGS__);} 894298811Sasomers 895135956Sphkstatic void 896135956Sphkprint_unr(struct unrhdr *uh, struct unr *up) 897135956Sphk{ 898135956Sphk u_int x; 899143283Sphk struct unrb *ub; 900135956Sphk 901135956Sphk printf(" %p len = %5u ", up, up->len); 902135956Sphk if (up->ptr == NULL) 903135956Sphk printf("free\n"); 904135956Sphk else if (up->ptr == uh) 905135956Sphk printf("alloc\n"); 906135956Sphk else { 907143283Sphk ub = up->ptr; 908299090Sasomers printf("bitmap ["); 909143283Sphk for (x = 0; x < up->len; x++) { 910143283Sphk if (bit_test(ub->map, x)) 911143283Sphk printf("#"); 912312327Sngie else 913143283Sphk printf(" "); 914135956Sphk } 915135956Sphk printf("]\n"); 916135956Sphk } 917135956Sphk} 918135956Sphk 919135956Sphkstatic void 920135956Sphkprint_unrhdr(struct unrhdr *uh) 921135956Sphk{ 922135956Sphk struct unr *up; 923135956Sphk u_int x; 924135956Sphk 925143283Sphk printf( 926143283Sphk "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n", 927143283Sphk uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc); 928143283Sphk x = uh->low + uh->first; 929135956Sphk TAILQ_FOREACH(up, &uh->head, list) { 930135956Sphk printf(" from = %5u", x); 931135956Sphk print_unr(uh, up); 932135956Sphk if (up->ptr == NULL || up->ptr == uh) 933135956Sphk x += up->len; 934135956Sphk else 935135956Sphk x += NBITS; 936135956Sphk } 937135956Sphk} 938135956Sphk 939209710Sjhstatic void 940209710Sjhtest_alloc_unr(struct unrhdr *uh, u_int i, char a[]) 941209710Sjh{ 942209710Sjh int j; 943209710Sjh 944209710Sjh if (a[i]) { 945298811Sasomers VPRINTF("F %u\n", i); 946209710Sjh free_unr(uh, i); 947209710Sjh a[i] = 0; 948209710Sjh } else { 949209710Sjh no_alloc = 1; 950209710Sjh j = alloc_unr(uh); 951209710Sjh if (j != -1) { 952209710Sjh a[j] = 1; 953298811Sasomers VPRINTF("A %d\n", j); 954209710Sjh } 955209710Sjh no_alloc = 0; 956209710Sjh } 957209710Sjh} 958209710Sjh 959209710Sjhstatic void 960209710Sjhtest_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[]) 961209710Sjh{ 962209710Sjh int j; 963209710Sjh 964209710Sjh j = alloc_unr_specific(uh, i); 965209710Sjh if (j == -1) { 966298811Sasomers VPRINTF("F %u\n", i); 967209710Sjh a[i] = 0; 968209710Sjh free_unr(uh, i); 969209710Sjh } else { 970209710Sjh a[i] = 1; 971298811Sasomers VPRINTF("A %d\n", j); 972209710Sjh } 973209710Sjh} 974209710Sjh 975298811Sasomersstatic void 976298811Sasomersusage(char** argv) 977298811Sasomers{ 978298811Sasomers printf("%s [-h] [-r REPETITIONS] [-v]\n", argv[0]); 979298811Sasomers} 980135956Sphk 981135956Sphkint 982298811Sasomersmain(int argc, char **argv) 983135956Sphk{ 984135956Sphk struct unrhdr *uh; 985298811Sasomers char *a; 986298811Sasomers long count = 10000; /* Number of unrs to test */ 987300544Sasomers long reps = 1, m; 988298811Sasomers int ch; 989312319Sngie u_int i, j; 990135956Sphk 991298811Sasomers verbose = false; 992298811Sasomers 993298811Sasomers while ((ch = getopt(argc, argv, "hr:v")) != -1) { 994298811Sasomers switch (ch) { 995298811Sasomers case 'r': 996298811Sasomers errno = 0; 997298811Sasomers reps = strtol(optarg, NULL, 0); 998298811Sasomers if (errno == ERANGE || errno == EINVAL) { 999298811Sasomers usage(argv); 1000298811Sasomers exit(2); 1001298811Sasomers } 1002312319Sngie 1003298811Sasomers break; 1004298811Sasomers case 'v': 1005298811Sasomers verbose = true; 1006298811Sasomers break; 1007298811Sasomers case 'h': 1008298811Sasomers default: 1009298811Sasomers usage(argv); 1010298811Sasomers exit(2); 1011298811Sasomers } 1012298811Sasomers 1013298811Sasomers 1014298811Sasomers } 1015298811Sasomers 1016143283Sphk setbuf(stdout, NULL); 1017298811Sasomers uh = new_unrhdr(0, count - 1, NULL); 1018143283Sphk print_unrhdr(uh); 1019135956Sphk 1020298811Sasomers a = calloc(count, sizeof(char)); 1021298811Sasomers if (a == NULL) 1022298811Sasomers err(1, "calloc failed"); 1023209710Sjh srandomdev(); 1024135956Sphk 1025298811Sasomers printf("sizeof(struct unr) %zu\n", sizeof(struct unr)); 1026298811Sasomers printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb)); 1027298811Sasomers printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr)); 1028299120Semaste printf("NBITS %lu\n", (unsigned long)NBITS); 1029298811Sasomers for (m = 0; m < count * reps; m++) { 1030143283Sphk j = random(); 1031298811Sasomers i = (j >> 1) % count; 1032143283Sphk#if 0 1033143283Sphk if (a[i] && (j & 1)) 1034143283Sphk continue; 1035143283Sphk#endif 1036209710Sjh if ((random() & 1) != 0) 1037209710Sjh test_alloc_unr(uh, i, a); 1038209710Sjh else 1039209710Sjh test_alloc_unr_specific(uh, i, a); 1040209710Sjh 1041298811Sasomers if (verbose) 1042135956Sphk print_unrhdr(uh); 1043135956Sphk check_unrhdr(uh, __LINE__); 1044135956Sphk } 1045300544Sasomers for (i = 0; i < (u_int)count; i++) { 1046143283Sphk if (a[i]) { 1047298811Sasomers if (verbose) { 1048298811Sasomers printf("C %u\n", i); 1049298811Sasomers print_unrhdr(uh); 1050298811Sasomers } 1051136945Sphk free_unr(uh, i); 1052143283Sphk } 1053143283Sphk } 1054136945Sphk print_unrhdr(uh); 1055136945Sphk delete_unrhdr(uh); 1056298811Sasomers free(a); 1057135956Sphk return (0); 1058135956Sphk} 1059135956Sphk#endif 1060