mempool.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <errno.h>
  4. #include <string.h>
  5. #include <sys/mman.h>
  6. #include "mempool.h"
  7. MemPool* MemPool_alloc(size_t itemSize, size_t maxItems) {
  8. MemPool* mp;
  9. mp = calloc(1, sizeof(*mp));
  10. MemPool_init(mp, itemSize, maxItems);
  11. return mp;
  12. }
  13. void MemPool_init(MemPool* mp, size_t itemSize, size_t maxItems) {
  14. size_t allocSize;
  15. mp->itemSize = itemSize < sizeof(size_t) ? sizeof(size_t) : itemSize;
  16. mp->maxItems = maxItems;
  17. mp->fill = 0;
  18. mp->firstFree = 1; // first free is 1-based
  19. allocSize = mp->itemSize * mp->maxItems;
  20. int flags = MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE;
  21. mp->pool = mmap(NULL, allocSize, PROT_READ | PROT_WRITE, flags, 0, 0);
  22. if(mp->pool == MAP_FAILED) {
  23. fprintf(stderr, "mmap failed in %s: %s\n", __func__, strerror(errno));
  24. exit(1);
  25. }
  26. }
  27. void* MemPool_malloc(MemPool* mp) {
  28. if(mp->fill >= mp->maxItems) {
  29. fprintf(stderr, "MemPool overflowed max items %ld\n", mp->maxItems);
  30. return NULL;
  31. }
  32. size_t off = mp->itemSize * (mp->firstFree - 1);
  33. size_t next = *(size_t*)(mp->pool + off);
  34. if(next == 0) next = mp->firstFree + 1;
  35. mp->firstFree = next;
  36. // not used in operation
  37. mp->fill++;
  38. return mp->pool + off;
  39. }
  40. void* MemPool_calloc(MemPool* mp) {
  41. void* p = MemPool_malloc(mp);
  42. memset(p, 0, mp->itemSize);
  43. return p;
  44. }
  45. void MemPool_free(MemPool* mp, void* ptr) {
  46. size_t ooff = mp->itemSize * (mp->firstFree - 1);
  47. size_t noff = (ptr - mp->pool) / mp->itemSize;
  48. *(size_t*)(mp->pool + ooff) = noff + 1;
  49. // not used in operation
  50. mp->fill--;
  51. }
  52. // -------------------------------------------
  53. // tracked mempool
  54. MemPoolT* MemPoolT_alloc(size_t itemSize, size_t maxItems) {
  55. MemPoolT* mp;
  56. mp = calloc(1, sizeof(*mp));
  57. MemPoolT_init(mp, itemSize, maxItems);
  58. return mp;
  59. }
  60. void MemPoolT_init(MemPoolT* mp, size_t itemSize, size_t maxItems) {
  61. size_t allocSize;
  62. mp->itemSize = itemSize < sizeof(size_t) ? sizeof(size_t) : itemSize;
  63. mp->maxItems = maxItems;
  64. mp->fill = 0;
  65. mp->firstFree = 1; // first free is 1-based
  66. mp->highestUsed = 0;
  67. mp->bitfieldAlloc = 0;
  68. mp->bitfield = NULL;
  69. allocSize = mp->itemSize * mp->maxItems;
  70. int flags = MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE;
  71. mp->pool = mmap(NULL, allocSize, PROT_READ | PROT_WRITE, flags, 0, 0);
  72. if(!mp->pool || mp->pool == MAP_FAILED) {
  73. fprintf(stderr, "mmap failed in %s: %s\n", __func__, strerror(errno));
  74. exit(1);
  75. }
  76. }
  77. static inline void mpt_check_bitfield(MemPoolT* mp) {
  78. if((mp->fill / 64) + ((mp->fill % 64) > 0) >= mp->bitfieldAlloc) {
  79. mp->bitfieldAlloc = mp->bitfieldAlloc < 8 ? 8 : mp->bitfieldAlloc * 2;
  80. mp->bitfield = realloc(mp->bitfield, sizeof(*mp->bitfield) * mp->bitfieldAlloc);
  81. }
  82. }
  83. static inline size_t mpt_get_bf_index(MemPoolT* mp, size_t index) {
  84. return ((index - 1) / 64);
  85. }
  86. static inline int mpt_get_bf_bit(MemPoolT* mp, size_t index) {
  87. return ((index - 1) % 64);
  88. }
  89. static inline uint64_t mpt_get_bf_mask(MemPoolT* mp, size_t index) {
  90. return ((uint64_t)1) << mpt_get_bf_bit(mp, index);
  91. }
  92. static inline void mpt_set_bit(MemPoolT* mp, size_t index) {
  93. uint64_t mask = mpt_get_bf_mask(mp, index);
  94. int i = mpt_get_bf_index(mp, index);
  95. mp->bitfield[i] |= mask;
  96. }
  97. static inline void mpt_clear_bit(MemPoolT* mp, size_t index) {
  98. mp->bitfield[mpt_get_bf_index(mp, index)] &= ~mpt_get_bf_mask(mp, index);
  99. }
  100. static inline int mpt_get_bit(MemPoolT* mp, size_t index) {
  101. return 0 != (mp->bitfield[mpt_get_bf_index(mp, index)] & mpt_get_bf_mask(mp, index));
  102. }
  103. void* MemPoolT_malloc(MemPoolT* mp) {
  104. if(mp->fill >= mp->maxItems) {
  105. fprintf(stderr, "MemPool overflowed max items %ld\n", mp->maxItems);
  106. return NULL;
  107. }
  108. mpt_check_bitfield(mp);
  109. size_t off = mp->itemSize * (mp->firstFree - 1);
  110. size_t next = *(size_t*)(mp->pool + off);
  111. if(next == 0) next = mp->firstFree + 1;
  112. mpt_set_bit(mp, mp->firstFree);
  113. mp->firstFree = next;
  114. mp->highestUsed = next > mp->highestUsed ? next : mp->highestUsed;
  115. mp->fill++;
  116. return mp->pool + off;
  117. }
  118. void MemPoolT_free(MemPoolT* mp, void* ptr) {
  119. size_t ooff = mp->itemSize * (mp->firstFree - 1);
  120. size_t noff = (ptr - mp->pool) / mp->itemSize;
  121. if(mpt_get_bit(mp, noff + 1)) {
  122. mpt_clear_bit(mp, noff + 1);
  123. *(size_t*)(mp->pool + ooff) = noff + 1;
  124. mp->fill--;
  125. }
  126. }
  127. // these are 0-based indices used for iteration
  128. int MemPoolT_isSlotUsed(MemPoolT* mp, size_t index) {
  129. return mpt_get_bit(mp, index + 1);
  130. }
  131. void* MemPoolT_getNextUsedIndex(MemPoolT* mp, size_t* index) {
  132. if(mp->fill <= 0) return NULL;
  133. while(!mpt_get_bit(mp, *index + 1)) {
  134. (*index)++;
  135. if(*index >= mp->highestUsed - 1) {
  136. return NULL;
  137. }
  138. }
  139. if(*index >= mp->highestUsed - 1) return NULL;
  140. return mp->pool + ((*index) * mp->itemSize);
  141. }
  142. int MemPoolT_ownsPointer(MemPoolT* mp, void* ptr) {
  143. return ptr >= mp->pool && ptr < mp->pool + (mp->itemSize * mp->maxItems);
  144. }