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 typedef u_int32_t       u_daddr_t;      /* unsigned disk address */
  34
  35 static __inline int
  36 LOG2(u_daddr_t v)
  37 {
  38         int i = -1;
  39
  40         if (!v)
  41                 return(0);
  42         while (v) {
  43                 i++;
  44                 v >>= 1;
  45         }
  46         return (i);
  47 }
  48
  49 /*
  50  * blmeta and bl_bitmap_t MUST be a power of 2 in size.
  51  */
  52
  53 typedef struct blmeta {
  54         union {
  55             daddr_t     bmu_avail;      /* space available under us     */
  56             u_daddr_t   bmu_bitmap;     /* bitmap if we are a leaf      */
  57         } u;
  58         daddr_t         bm_bighint;     /* biggest contiguous block hint*/
  59 } blmeta_t;
  60
  61 typedef struct blist {
  62         daddr_t         bl_blocks;      /* area of coverage             */
  63         daddr_t         bl_radix;       /* coverage radix               */
  64         daddr_t         bl_skip;        /* starting skip                */
  65         daddr_t         bl_free;        /* number of free blocks        */
  66         blmeta_t        *bl_root;       /* root of radix tree           */
  67         daddr_t         bl_rootblks;    /* daddr_t blks allocated for tree */
  68 } *blist_t;
  69
  70 #define BLIST_META_RADIX        16
  71 #define BLIST_META_RADIX_SHIFT  LOG2(BLIST_META_RADIX)
  72 #define BLIST_BMAP_RADIX        (sizeof(u_daddr_t)*8)
  73 #define BLIST_BMAP_RADIX_SHIFT  LOG2(BLIST_BMAP_RADIX)
  74
  75 #define BLIST_MAX_ALLOC         BLIST_BMAP_RADIX
  76
  77 extern blist_t blist_create(daddr_t blocks);
  78 extern void blist_destroy(blist_t blist);
  79 extern daddr_t blist_alloc(blist_t blist, daddr_t count);
  80 extern void blist_free(blist_t blist, daddr_t blkno, daddr_t count);
  81 extern void blist_print(blist_t blist);
  82 extern void blist_resize(blist_t *pblist, daddr_t count, int freenew);
  83
  84 #endif  /* _SYS_BLIST_H_ */
  85