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(pnode) ((blknode_t *)((char *)pnode - (1 << pnode->logsize)))
  43 #define MPOOL_GET_RIGHT_BUDDY(pnode) ((blknode_t *)((char *)pnode + (1 << pnode->logsize)))
  44
  45 /* This macro is provided for easy initialization of a blknode structure */
  46 #define MPOOL_BLOCK_INIT(_node, _base, _ptr, _avail, _lr, _parent, _logsize) \
  47     do {                                                                \
  48         _node = _base;                                                  \
  49         _node->ptr = _ptr;                                              \
  50         _node->logsize = _logsize;                                      \
  51                                                                         \
  52         /* Availability */                                              \
  53         if ((_avail) == MPOOL_BLOCK_AVAIL)                              \
  54             _node->flags |= MPOOL_NODE_AVAIL;                           \
  55         else                                                            \
  56             _node->flags &= ~MPOOL_NODE_AVAIL;                          \
  57                                                                         \
  58         /* Left-Right relationship */                                   \
  59         if ((_lr) == MPOOL_BLOCK_RIGHT)                                 \
  60             _node->flags |= MPOOL_NODE_LR;                              \
  61         else                                                            \
  62             _node->flags &= ~MPOOL_NODE_LR;                             \
  63                                                                         \
  64         /* Parent L-R relationship */                                   \
  65         if ((_parent) == MPOOL_BLOCK_PARENT)                            \
  66             _node->flags |= MPOOL_NODE_PARENT;                          \
  67         else                                                            \
  68             _node->flags &= ~MPOOL_NODE_PARENT;                         \
  69     } while(0)
  70
  71 typedef struct blknode {
  72     unsigned char flags;    /* availability, left-right buddiness, inheritance */
  73     size_t logsize;         /* logarithm of size with base 2 */
  74     void *ptr;              /* pointer to beginning of free block (what mpool_alloc() returns) */
  75     LIST_ENTRY(blknode) next_chunk;
  76 } blknode_t;
  77
  78 typedef struct mpool {
  79     void *mem;
  80     size_t nblocks;       /* nblocks = logsize + 1 */
  81     size_t maxlogsize;    /* logarithm of maximum size of chunk with base 2 */
  82     size_t minlogsize;    /* logarithm of minimum size of chunk with base 2 */
  83 #ifdef MPOOL_STATS
  84     size_t nsplits;       /* number of splits made */
  85     size_t nmerges;       /* number of merges made */
  86 #endif
  87     LIST_HEAD(blkhead, blknode) *blktable;
  88 } mpool_t;
  89
  90 typedef struct blkhead blkhead_t;
  91
  92 typedef enum {
  93     MPOOL_OK,
  94     MPOOL_EBADVAL,
  95     MPOOL_ENOMEM,
  96     MPOOL_ERANGE
  97 } mpret_t;
  98
  99 /* Function prototypes */
 100 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize);
 101 void *mpool_alloc(mpool_t *mpool, size_t blksize);
 102 void mpool_free(mpool_t *mpool, void *ptr);
 103 void mpool_destroy(mpool_t *mpool);
 104
 105 #endif    /* MPOOL_H_ */