linear_allocator.h 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208
  1. /*
  2. * linear_allocator.h
  3. *
  4. * @copyright Copyright (C) 2016 Sproute Networks, Inc.
  5. *
  6. * @author Avneesh Sachdev <avneesh@sproute.com>
  7. *
  8. * This file is part of Quagga.
  9. *
  10. * Quagga is free software; you can redistribute it and/or modify it
  11. * under the terms of the GNU General Public License as published by the
  12. * Free Software Foundation; either version 2, or (at your option) any
  13. * later version.
  14. *
  15. * Quagga is distributed in the hope that it will be useful, but
  16. * WITHOUT ANY WARRANTY; without even the implied warranty of
  17. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18. * General Public License for more details.
  19. *
  20. * You should have received a copy of the GNU General Public License
  21. * along with Quagga; see the file COPYING. If not, write to the Free
  22. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23. * 02111-1307, USA.
  24. */
  25. /*
  26. * Header file for the linear allocator.
  27. *
  28. * An allocator that allocates memory by walking down towards the end
  29. * of a buffer. No attempt is made to reuse blocks that are freed
  30. * subsequently. The assumption is that the buffer is big enough to
  31. * cover allocations for a given purpose.
  32. */
  33. #include <assert.h>
  34. #include <string.h>
  35. #include <stdint.h>
  36. #include <stddef.h>
  37. /*
  38. * Alignment for block allocated by the allocator. Must be a power of 2.
  39. */
  40. #define LINEAR_ALLOCATOR_ALIGNMENT 8
  41. #define LINEAR_ALLOCATOR_ALIGN(value) \
  42. (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1) & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
  43. /*
  44. * linear_allocator_align_ptr
  45. */
  46. static inline char *
  47. linear_allocator_align_ptr (char *ptr)
  48. {
  49. return (char *) LINEAR_ALLOCATOR_ALIGN ((intptr_t) ptr);
  50. }
  51. typedef struct linear_allocator_t_
  52. {
  53. char *buf;
  54. /*
  55. * Current location in the buffer.
  56. */
  57. char *cur;
  58. /*
  59. * End of buffer.
  60. */
  61. char *end;
  62. /*
  63. * Version number of the allocator, this is bumped up when the allocator
  64. * is reset and helps identifies bad frees.
  65. */
  66. uint32_t version;
  67. /*
  68. * The number of blocks that are currently allocated.
  69. */
  70. int num_allocated;
  71. } linear_allocator_t;
  72. /*
  73. * linear_allocator_block_t
  74. *
  75. * Header structure at the begining of each block.
  76. */
  77. typedef struct linear_allocator_block_t_
  78. {
  79. uint32_t flags;
  80. /*
  81. * The version of the allocator when this block was allocated.
  82. */
  83. uint32_t version;
  84. char data[0];
  85. } linear_allocator_block_t;
  86. #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
  87. #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
  88. /*
  89. * linear_allocator_block_size
  90. *
  91. * The total amount of space a block will take in the buffer,
  92. * including the size of the header.
  93. */
  94. static inline size_t
  95. linear_allocator_block_size (size_t user_size)
  96. {
  97. return LINEAR_ALLOCATOR_ALIGN (LINEAR_ALLOCATOR_HDR_SIZE + user_size);
  98. }
  99. /*
  100. * linear_allocator_ptr_to_block
  101. */
  102. static inline linear_allocator_block_t *
  103. linear_allocator_ptr_to_block (void *ptr)
  104. {
  105. void *block_ptr;
  106. block_ptr = ((char *) ptr) - offsetof (linear_allocator_block_t, data);
  107. return block_ptr;
  108. }
  109. /*
  110. * linear_allocator_init
  111. */
  112. static inline void
  113. linear_allocator_init (linear_allocator_t * allocator, char *buf,
  114. size_t buf_len)
  115. {
  116. memset (allocator, 0, sizeof (*allocator));
  117. assert (linear_allocator_align_ptr (buf) == buf);
  118. allocator->buf = buf;
  119. allocator->cur = buf;
  120. allocator->end = buf + buf_len;
  121. }
  122. /*
  123. * linear_allocator_reset
  124. *
  125. * Prepare an allocator for reuse.
  126. *
  127. * *** NOTE ** This implicitly frees all the blocks in the allocator.
  128. */
  129. static inline void
  130. linear_allocator_reset (linear_allocator_t *allocator)
  131. {
  132. allocator->num_allocated = 0;
  133. allocator->version++;
  134. allocator->cur = allocator->buf;
  135. }
  136. /*
  137. * linear_allocator_alloc
  138. */
  139. static inline void *
  140. linear_allocator_alloc (linear_allocator_t *allocator, size_t user_size)
  141. {
  142. size_t block_size;
  143. linear_allocator_block_t *block;
  144. block_size = linear_allocator_block_size (user_size);
  145. if (allocator->cur + block_size > allocator->end)
  146. {
  147. return NULL;
  148. }
  149. block = (linear_allocator_block_t *) allocator->cur;
  150. allocator->cur += block_size;
  151. block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
  152. block->version = allocator->version;
  153. allocator->num_allocated++;
  154. return block->data;
  155. }
  156. /*
  157. * linear_allocator_free
  158. */
  159. static inline void
  160. linear_allocator_free (linear_allocator_t *allocator, void *ptr)
  161. {
  162. linear_allocator_block_t *block;
  163. if (((char *) ptr) < allocator->buf || ((char *) ptr) >= allocator->end)
  164. {
  165. assert (0);
  166. return;
  167. }
  168. block = linear_allocator_ptr_to_block (ptr);
  169. if (block->version != allocator->version)
  170. {
  171. assert (0);
  172. return;
  173. }
  174. block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
  175. if (--allocator->num_allocated < 0)
  176. {
  177. assert (0);
  178. }
  179. }