buddy/mpool.h

   1 #ifndef MPOOL_H_
   2 #define MPOOL_H_
   3
   4 #include <stdlib.h>
   5 #include <sys/queue.h>
   6
   7 /*#define MPOOL_DEBUG*/
   8 /*#define MPOOL_OPT_FOR_SECURITY*/
   9 #define MPOOL_STATS
  10
  11 #ifdef MPOOL_DEBUG
  12 #define DPRINTF(a) printf a
  13 #else
  14 #define DPRINTF(a)
  15 #endif
  16
  17 /* `flags' bits in blknode data structure */
  18 #define MPOOL_NODE_AVAIL  (1 << 0)    /* If not set, node is reserved, else available */
  19 #define MPOOL_NODE_LR     (1 << 1)    /* If not set, node is left buddy, else right buddy */
  20 #define MPOOL_NODE_PARENT (1 << 2)    /* If not set, parent is left buddy, else right buddy */
  21
  22 #define MPOOL_BLOCK_USED   0    /* Block is used */
  23 #define MPOOL_BLOCK_AVAIL  1    /* Block is available */
  24 #define MPOOL_BLOCK_LEFT   2    /* Block is left buddy */
  25 #define MPOOL_BLOCK_RIGHT  3    /* Block is right buddy */
  26 #define MPOOL_BLOCK_PARENT 4    /* Block's parent is right buddy */
  27
  28 /* Macro definitions */
  29 #define MPOOL_MARK_AVAIL(pnode) pnode->flags |= MPOOL_NODE_AVAIL
  30 #define MPOOL_MARK_USED(pnode) pnode->flags &= ~MPOOL_NODE_AVAIL
  31 #define MPOOL_MARK_LEFT(pnode) pnode->flags &= ~MPOOL_NODE_LR
  32 #define MPOOL_MARK_RIGHT(pnode) pnode->flags |= MPOOL_NODE_LR
  33 #define MPOOL_MARK_PARENT(pnode) pnode->flags |= MPOOL_NODE_PARENT
  34 #define MPOOL_MARK_NOTPARENT(pnode) pnode->flags &= ~MPOOL_NODE_PARENT
  35
  36 #define MPOOL_IS_AVAIL(pnode) ((pnode->flags & MPOOL_NODE_AVAIL) != 0)
  37 #define MPOOL_IS_USED(pnode)  ((pnode->flags & MPOOL_NODE_AVAIL) == 0)
  38 #define MPOOL_IS_LEFT(pnode)  ((pnode->flags & MPOOL_NODE_LR) == 0)
  39 #define MPOOL_IS_RIGHT(pnode) ((pnode->flags & MPOOL_NODE_LR) != 0)
  40 #define MPOOL_IS_PARENT(pnode) ((pnode->flags & MPOOL_NODE_PARENT) != 0)
  41
  42 #define MPOOL_GET_LEFT_BUDDY_OF(pnode) \
  43     ((blknode_t *)((char *)pnode - (1 << pnode->logsize)))
  44 #define MPOOL_GET_RIGHT_BUDDY_OF(pnode) \
  45     ((blknode_t *)((char *)pnode + (1 << pnode->logsize)))
  46
  47 /* This macro is provided for easy initialization of a blknode structure */
  48 #define MPOOL_BLOCK_INIT(_node, _base, _ptr, _avail, _lr, _parent, _logsize) \
  49     do {                                                                \
  50         _node = _base;                                                  \
  51         _node->ptr = _ptr;                                              \
  52         _node->logsize = _logsize;                                      \
  53                                                                         \
  54         /* Availability */                                              \
  55         if ((_avail) == MPOOL_BLOCK_AVAIL)                              \
  56             MPOOL_MARK_AVAIL(_node);                                    \
  57         else                                                            \
  58             MPOOL_MARK_USED(_node);                                     \
  59                                                                         \
  60         /* Left-Right relationship */                                   \
  61         if ((_lr) == MPOOL_BLOCK_RIGHT)                                 \
  62             MPOOL_MARK_RIGHT(_node);                                    \
  63         else                                                            \
  64             MPOOL_MARK_LEFT(_node);                                     \
  65                                                                         \
  66         /* Parent L-R relationship */                                   \
  67         if ((_parent) == MPOOL_BLOCK_PARENT)                            \
  68             MPOOL_MARK_PARENT(_node);                                   \
  69         else                                                            \
  70             MPOOL_MARK_NOTPARENT(_node);                                \
  71     } while(0)
  72
  73 typedef struct blknode {
  74     unsigned char flags;    /* availability, left-right buddiness, parentship */
  75     size_t logsize;         /* logarithm of size with base 2 */
  76     void *ptr;              /* what mpool_alloc() returns */
  77     LIST_ENTRY(blknode) next_chunk;
  78 } blknode_t;
  79
  80 typedef struct mpool {
  81     void *mem;
  82     size_t nblocks;       /* nblocks = maxlogsize - minlogsize + 1 */
  83     size_t maxlogsize;    /* logarithm of maximum size of chunk with base 2 */
  84     size_t minlogsize;    /* logarithm of minimum size of chunk with base 2 */
  85 #ifdef MPOOL_STATS
  86     size_t nsplits;       /* number of splits made */
  87     size_t nmerges;       /* number of merges made */
  88 #endif
  89     LIST_HEAD(blkhead, blknode) *blktable;
  90 } mpool_t;
  91
  92 typedef struct blkhead blkhead_t;
  93
  94 typedef enum {
  95     MPOOL_OK,
  96     MPOOL_EBADVAL,
  97     MPOOL_ENOMEM,
  98     MPOOL_ERANGE
  99 } mpret_t;
 100
 101 /* Function prototypes */
 102 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize);
 103 void *mpool_alloc(mpool_t *mpool, size_t blksize);
 104 void mpool_free(mpool_t *mpool, void *ptr);
 105 void mpool_destroy(mpool_t *mpool);
 106
 107 #endif    /* MPOOL_H_ */