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