sys/sys/blist.h

   1 /*
   2  * Copyright (c) 1998 Matthew Dillon.  Terms of use and redistribution in all
   3  * forms are covered by the BSD copyright in the file "/usr/src/COPYRIGHT".
   4  *
   5  * Implements bitmap resource lists.
   6  *
   7  *      Usage:
   8  *              blist = blist_create(blocks)
   9  *              (void)  blist_destroy(blist)
  10  *              blkno = blist_alloc(blist, count)
  11  *              (void)  blist_free(blist, blkno, count)
  12  *              (void)  blist_resize(&blist, count, freeextra)
  13  *
  14  *
  15  *      Notes:
  16  *              on creation, the entire list is marked reserved.  You should
  17  *              first blist_free() the sections you want to make available
  18  *              for allocation before doing general blist_alloc()/free()
  19  *              ops.
  20  *
  21  *              SWAPBLK_NONE is returned on failure.  This module is typically
  22  *              capable of managing up to (2^31) blocks per blist, though
  23  *              the memory utilization would be insane if you actually did
  24  *              that.  Managing something like 512MB worth of 4K blocks
  25  *              eats around 32 KBytes of memory.
  26  *
  27  * $FreeBSD$
  28  */
  29
  30 #ifndef _SYS_BLIST_H_
  31 #define _SYS_BLIST_H_
  32
  33 #define LOG2(v)         (((u_daddr_t)(v) >= 0x80000000U) ? 31 : \
  34                         ((u_daddr_t)(v) >= 0x40000000U) ? 30 : \
  35                         ((u_daddr_t)(v) >= 0x20000000U) ? 29 : \
  36                         ((u_daddr_t)(v) >= 0x10000000U) ? 28 : \
  37                         ((u_daddr_t)(v) >= 0x08000000U) ? 27 : \
  38                         ((u_daddr_t)(v) >= 0x04000000U) ? 26 : \
  39                         ((u_daddr_t)(v) >= 0x02000000U) ? 25 : \
  40                         ((u_daddr_t)(v) >= 0x01000000U) ? 24 : \
  41                         ((u_daddr_t)(v) >= 0x00800000U) ? 23 : \
  42                         ((u_daddr_t)(v) >= 0x00400000U) ? 22 : \
  43                         ((u_daddr_t)(v) >= 0x00200000U) ? 21 : \
  44                         ((u_daddr_t)(v) >= 0x00100000U) ? 20 : \
  45                         ((u_daddr_t)(v) >= 0x00080000U) ? 19 : \
  46                         ((u_daddr_t)(v) >= 0x00040000U) ? 18 : \
  47                         ((u_daddr_t)(v) >= 0x00020000U) ? 17 : \
  48                         ((u_daddr_t)(v) >= 0x00010000U) ? 16 : \
  49                         ((u_daddr_t)(v) >= 0x00008000U) ? 15 : \
  50                         ((u_daddr_t)(v) >= 0x00004000U) ? 14 : \
  51                         ((u_daddr_t)(v) >= 0x00002000U) ? 13 : \
  52                         ((u_daddr_t)(v) >= 0x00001000U) ? 12 : \
  53                         ((u_daddr_t)(v) >= 0x00000800U) ? 11 : \
  54                         ((u_daddr_t)(v) >= 0x00000400U) ? 10 : \
  55                         ((u_daddr_t)(v) >= 0x00000200U) ? 9 : \
  56                         ((u_daddr_t)(v) >= 0x00000100U) ? 8 : \
  57                         ((u_daddr_t)(v) >= 0x00000080U) ? 7 : \
  58                         ((u_daddr_t)(v) >= 0x00000040U) ? 6 : \
  59                         ((u_daddr_t)(v) >= 0x00000020U) ? 5 : \
  60                         ((u_daddr_t)(v) >= 0x00000010U) ? 4 : \
  61                         ((u_daddr_t)(v) >= 0x00000008U) ? 3 : \
  62                         ((u_daddr_t)(v) >= 0x00000004U) ? 2 : \
  63                         ((u_daddr_t)(v) >= 0x00000002U) ? 1 : 0)
  64
  65 /*
  66  * blmeta and bl_bitmap_t MUST be a power of 2 in size.
  67  */
  68
  69 typedef struct blmeta {
  70         union {
  71             daddr_t     bmu_avail;      /* space available under us     */
  72             u_daddr_t   bmu_bitmap;     /* bitmap if we are a leaf      */
  73         } u;
  74         daddr_t         bm_bighint;     /* biggest contiguous block hint*/
  75 } blmeta_t;
  76
  77 typedef struct blist {
  78         daddr_t         bl_blocks;      /* area of coverage             */
  79         daddr_t         bl_radix;       /* coverage radix               */
  80         daddr_t         bl_skip;        /* starting skip                */
  81         daddr_t         bl_free;        /* number of free blocks        */
  82         blmeta_t        *bl_root;       /* root of radix tree           */
  83         daddr_t         bl_rootblks;    /* daddr_t blks allocated for tree */
  84 } *blist_t;
  85
  86 #define BLIST_META_RADIX        16
  87 #define BLIST_META_RADIX_SHIFT  LOG2(BLIST_META_RADIX)
  88 #define BLIST_BMAP_RADIX        (sizeof(u_daddr_t)*8)
  89 #define BLIST_BMAP_RADIX_SHIFT  LOG2(BLIST_BMAP_RADIX)
  90
  91 #define BLIST_MAX_ALLOC         BLIST_BMAP_RADIX
  92
  93 extern blist_t blist_create(daddr_t blocks);
  94 extern void blist_destroy(blist_t blist);
  95 extern daddr_t blist_alloc(blist_t blist, daddr_t count);
  96 extern void blist_free(blist_t blist, daddr_t blkno, daddr_t count);
  97 extern void blist_print(blist_t blist);
  98 extern void blist_resize(blist_t *pblist, daddr_t count, int freenew);
  99
 100 #endif  /* _SYS_BLIST_H_ */
 101