memarea.c 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336
  1. /* Copyright (c) 2008-2013, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /** \file memarea.c
  4. * \brief Implementation for memarea_t, an allocator for allocating lots of
  5. * small objects that will be freed all at once.
  6. */
  7. #include "orconfig.h"
  8. #include <stdlib.h>
  9. #include "memarea.h"
  10. #include "util.h"
  11. #include "compat.h"
  12. #include "torlog.h"
  13. /** If true, we try to detect any attempts to write beyond the length of a
  14. * memarea. */
  15. #define USE_SENTINELS
  16. /** All returned pointers should be aligned to the nearest multiple of this
  17. * value. */
  18. #define MEMAREA_ALIGN SIZEOF_VOID_P
  19. #if MEMAREA_ALIGN == 4
  20. #define MEMAREA_ALIGN_MASK 3lu
  21. #elif MEMAREA_ALIGN == 8
  22. #define MEMAREA_ALIGN_MASK 7lu
  23. #else
  24. #error "void* is neither 4 nor 8 bytes long. I don't know how to align stuff."
  25. #endif
  26. #if defined(__GNUC__) && defined(FLEXIBLE_ARRAY_MEMBER)
  27. #define USE_ALIGNED_ATTRIBUTE
  28. #define U_MEM mem
  29. #else
  30. #define U_MEM u.mem
  31. #endif
  32. #ifdef USE_SENTINELS
  33. /** Magic value that we stick at the end of a memarea so we can make sure
  34. * there are no run-off-the-end bugs. */
  35. #define SENTINEL_VAL 0x90806622u
  36. /** How many bytes per area do we devote to the sentinel? */
  37. #define SENTINEL_LEN sizeof(uint32_t)
  38. /** Given a mem_area_chunk_t with SENTINEL_LEN extra bytes allocated at the
  39. * end, set those bytes. */
  40. #define SET_SENTINEL(chunk) \
  41. STMT_BEGIN \
  42. set_uint32( &(chunk)->U_MEM[chunk->mem_size], SENTINEL_VAL ); \
  43. STMT_END
  44. /** Assert that the sentinel on a memarea is set correctly. */
  45. #define CHECK_SENTINEL(chunk) \
  46. STMT_BEGIN \
  47. uint32_t sent_val = get_uint32(&(chunk)->U_MEM[chunk->mem_size]); \
  48. tor_assert(sent_val == SENTINEL_VAL); \
  49. STMT_END
  50. #else
  51. #define SENTINEL_LEN 0
  52. #define SET_SENTINEL(chunk) STMT_NIL
  53. #define CHECK_SENTINEL(chunk) STMT_NIL
  54. #endif
  55. /** Increment <b>ptr</b> until it is aligned to MEMAREA_ALIGN. */
  56. static INLINE void *
  57. realign_pointer(void *ptr)
  58. {
  59. uintptr_t x = (uintptr_t)ptr;
  60. x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
  61. /* Reinstate this if bug 930 ever reappears
  62. tor_assert(((void*)x) >= ptr);
  63. */
  64. return (void*)x;
  65. }
  66. /** Implements part of a memarea. New memory is carved off from chunk->mem in
  67. * increasing order until a request is too big, at which point a new chunk is
  68. * allocated. */
  69. typedef struct memarea_chunk_t {
  70. /** Next chunk in this area. Only kept around so we can free it. */
  71. struct memarea_chunk_t *next_chunk;
  72. size_t mem_size; /**< How much RAM is available in mem, total? */
  73. char *next_mem; /**< Next position in mem to allocate data at. If it's
  74. * greater than or equal to mem+mem_size, this chunk is
  75. * full. */
  76. #ifdef USE_ALIGNED_ATTRIBUTE
  77. char mem[FLEXIBLE_ARRAY_MEMBER] __attribute__((aligned(MEMAREA_ALIGN)));
  78. #else
  79. union {
  80. char mem[1]; /**< Memory space in this chunk. */
  81. void *void_for_alignment_; /**< Dummy; used to make sure mem is aligned. */
  82. } u;
  83. #endif
  84. } memarea_chunk_t;
  85. /** How many bytes are needed for overhead before we get to the memory part
  86. * of a chunk? */
  87. #define CHUNK_HEADER_SIZE STRUCT_OFFSET(memarea_chunk_t, U_MEM)
  88. /** What's the smallest that we'll allocate a chunk? */
  89. #define CHUNK_SIZE 4096
  90. /** A memarea_t is an allocation region for a set of small memory requests
  91. * that will all be freed at once. */
  92. struct memarea_t {
  93. memarea_chunk_t *first; /**< Top of the chunk stack: never NULL. */
  94. };
  95. /** How many chunks will we put into the freelist before freeing them? */
  96. #define MAX_FREELIST_LEN 4
  97. /** The number of memarea chunks currently in our freelist. */
  98. static int freelist_len=0;
  99. /** A linked list of unused memory area chunks. Used to prevent us from
  100. * spinning in malloc/free loops. */
  101. static memarea_chunk_t *freelist = NULL;
  102. /** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
  103. static memarea_chunk_t *
  104. alloc_chunk(size_t sz, int freelist_ok)
  105. {
  106. tor_assert(sz < SIZE_T_CEILING);
  107. if (freelist && freelist_ok) {
  108. memarea_chunk_t *res = freelist;
  109. freelist = res->next_chunk;
  110. res->next_chunk = NULL;
  111. --freelist_len;
  112. CHECK_SENTINEL(res);
  113. return res;
  114. } else {
  115. size_t chunk_size = freelist_ok ? CHUNK_SIZE : sz;
  116. memarea_chunk_t *res;
  117. chunk_size += SENTINEL_LEN;
  118. res = tor_malloc(chunk_size);
  119. res->next_chunk = NULL;
  120. res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
  121. res->next_mem = res->U_MEM;
  122. tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
  123. ((char*)res)+chunk_size);
  124. tor_assert(realign_pointer(res->next_mem) == res->next_mem);
  125. SET_SENTINEL(res);
  126. return res;
  127. }
  128. }
  129. /** Release <b>chunk</b> from a memarea, either by adding it to the freelist
  130. * or by freeing it if the freelist is already too big. */
  131. static void
  132. chunk_free_unchecked(memarea_chunk_t *chunk)
  133. {
  134. CHECK_SENTINEL(chunk);
  135. if (freelist_len < MAX_FREELIST_LEN) {
  136. ++freelist_len;
  137. chunk->next_chunk = freelist;
  138. freelist = chunk;
  139. chunk->next_mem = chunk->U_MEM;
  140. } else {
  141. tor_free(chunk);
  142. }
  143. }
  144. /** Allocate and return new memarea. */
  145. memarea_t *
  146. memarea_new(void)
  147. {
  148. memarea_t *head = tor_malloc(sizeof(memarea_t));
  149. head->first = alloc_chunk(CHUNK_SIZE, 1);
  150. return head;
  151. }
  152. /** Free <b>area</b>, invalidating all pointers returned from memarea_alloc()
  153. * and friends for this area */
  154. void
  155. memarea_drop_all(memarea_t *area)
  156. {
  157. memarea_chunk_t *chunk, *next;
  158. for (chunk = area->first; chunk; chunk = next) {
  159. next = chunk->next_chunk;
  160. chunk_free_unchecked(chunk);
  161. }
  162. area->first = NULL; /*fail fast on */
  163. tor_free(area);
  164. }
  165. /** Forget about having allocated anything in <b>area</b>, and free some of
  166. * the backing storage associated with it, as appropriate. Invalidates all
  167. * pointers returned from memarea_alloc() for this area. */
  168. void
  169. memarea_clear(memarea_t *area)
  170. {
  171. memarea_chunk_t *chunk, *next;
  172. if (area->first->next_chunk) {
  173. for (chunk = area->first->next_chunk; chunk; chunk = next) {
  174. next = chunk->next_chunk;
  175. chunk_free_unchecked(chunk);
  176. }
  177. area->first->next_chunk = NULL;
  178. }
  179. area->first->next_mem = area->first->U_MEM;
  180. }
  181. /** Remove all unused memarea chunks from the internal freelist. */
  182. void
  183. memarea_clear_freelist(void)
  184. {
  185. memarea_chunk_t *chunk, *next;
  186. freelist_len = 0;
  187. for (chunk = freelist; chunk; chunk = next) {
  188. next = chunk->next_chunk;
  189. tor_free(chunk);
  190. }
  191. freelist = NULL;
  192. }
  193. /** Return true iff <b>p</b> is in a range that has been returned by an
  194. * allocation from <b>area</b>. */
  195. int
  196. memarea_owns_ptr(const memarea_t *area, const void *p)
  197. {
  198. memarea_chunk_t *chunk;
  199. const char *ptr = p;
  200. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  201. if (ptr >= chunk->U_MEM && ptr < chunk->next_mem)
  202. return 1;
  203. }
  204. return 0;
  205. }
  206. /** Return a pointer to a chunk of memory in <b>area</b> of at least <b>sz</b>
  207. * bytes. <b>sz</b> should be significantly smaller than the area's chunk
  208. * size, though we can deal if it isn't. */
  209. void *
  210. memarea_alloc(memarea_t *area, size_t sz)
  211. {
  212. memarea_chunk_t *chunk = area->first;
  213. char *result;
  214. tor_assert(chunk);
  215. CHECK_SENTINEL(chunk);
  216. tor_assert(sz < SIZE_T_CEILING);
  217. if (sz == 0)
  218. sz = 1;
  219. if (chunk->next_mem+sz > chunk->U_MEM+chunk->mem_size) {
  220. if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
  221. /* This allocation is too big. Stick it in a special chunk, and put
  222. * that chunk second in the list. */
  223. memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE, 0);
  224. new_chunk->next_chunk = chunk->next_chunk;
  225. chunk->next_chunk = new_chunk;
  226. chunk = new_chunk;
  227. } else {
  228. memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE, 1);
  229. new_chunk->next_chunk = chunk;
  230. area->first = chunk = new_chunk;
  231. }
  232. tor_assert(chunk->mem_size >= sz);
  233. }
  234. result = chunk->next_mem;
  235. chunk->next_mem = chunk->next_mem + sz;
  236. /* Reinstate these if bug 930 ever comes back
  237. tor_assert(chunk->next_mem >= chunk->U_MEM);
  238. tor_assert(chunk->next_mem <= chunk->U_MEM+chunk->mem_size);
  239. */
  240. chunk->next_mem = realign_pointer(chunk->next_mem);
  241. return result;
  242. }
  243. /** As memarea_alloc(), but clears the memory it returns. */
  244. void *
  245. memarea_alloc_zero(memarea_t *area, size_t sz)
  246. {
  247. void *result = memarea_alloc(area, sz);
  248. memset(result, 0, sz);
  249. return result;
  250. }
  251. /** As memdup, but returns the memory from <b>area</b>. */
  252. void *
  253. memarea_memdup(memarea_t *area, const void *s, size_t n)
  254. {
  255. char *result = memarea_alloc(area, n);
  256. memcpy(result, s, n);
  257. return result;
  258. }
  259. /** As strdup, but returns the memory from <b>area</b>. */
  260. char *
  261. memarea_strdup(memarea_t *area, const char *s)
  262. {
  263. return memarea_memdup(area, s, strlen(s)+1);
  264. }
  265. /** As strndup, but returns the memory from <b>area</b>. */
  266. char *
  267. memarea_strndup(memarea_t *area, const char *s, size_t n)
  268. {
  269. size_t ln = 0;
  270. char *result;
  271. tor_assert(n < SIZE_T_CEILING);
  272. for (ln = 0; ln < n && s[ln]; ++ln)
  273. ;
  274. result = memarea_alloc(area, ln+1);
  275. memcpy(result, s, ln);
  276. result[ln]='\0';
  277. return result;
  278. }
  279. /** Set <b>allocated_out</b> to the number of bytes allocated in <b>area</b>,
  280. * and <b>used_out</b> to the number of bytes currently used. */
  281. void
  282. memarea_get_stats(memarea_t *area, size_t *allocated_out, size_t *used_out)
  283. {
  284. size_t a = 0, u = 0;
  285. memarea_chunk_t *chunk;
  286. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  287. CHECK_SENTINEL(chunk);
  288. a += CHUNK_HEADER_SIZE + chunk->mem_size;
  289. tor_assert(chunk->next_mem >= chunk->U_MEM);
  290. u += CHUNK_HEADER_SIZE + (chunk->next_mem - chunk->U_MEM);
  291. }
  292. *allocated_out = a;
  293. *used_out = u;
  294. }
  295. /** Assert that <b>area</b> is okay. */
  296. void
  297. memarea_assert_ok(memarea_t *area)
  298. {
  299. memarea_chunk_t *chunk;
  300. tor_assert(area->first);
  301. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  302. CHECK_SENTINEL(chunk);
  303. tor_assert(chunk->next_mem >= chunk->U_MEM);
  304. tor_assert(chunk->next_mem <=
  305. (char*) realign_pointer(chunk->U_MEM+chunk->mem_size));
  306. }
  307. }