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