memarea.c 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313
  1. /* Copyright (c) 2008-2009, 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 "log.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. #ifdef USE_SENTINELS
  27. #define SENTINEL_VAL 0x90806622u
  28. #define SENTINEL_LEN sizeof(uint32_t)
  29. #define SET_SENTINEL(chunk) \
  30. STMT_BEGIN \
  31. set_uint32( &(chunk)->u.mem[chunk->mem_size], SENTINEL_VAL ); \
  32. STMT_END
  33. #define CHECK_SENTINEL(chunk) \
  34. STMT_BEGIN \
  35. uint32_t sent_val = get_uint32(&(chunk)->u.mem[chunk->mem_size]); \
  36. tor_assert(sent_val == SENTINEL_VAL); \
  37. STMT_END
  38. #else
  39. #define SENTINEL_LEN 0
  40. #define SET_SENTINEL(chunk) STMT_NIL
  41. #define CHECK_SENTINEL(chunk) STMT_NIL
  42. #endif
  43. /** Increment <b>ptr</b> until it is aligned to MEMAREA_ALIGN. */
  44. static INLINE void *
  45. realign_pointer(void *ptr)
  46. {
  47. uintptr_t x = (uintptr_t)ptr;
  48. x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
  49. tor_assert(((void*)x) >= ptr); // XXXX021 remove this once bug 930 is solved
  50. return (void*)x;
  51. }
  52. /** Implements part of a memarea. New memory is carved off from chunk->mem in
  53. * increasing order until a request is too big, at which point a new chunk is
  54. * allocated. */
  55. typedef struct memarea_chunk_t {
  56. /** Next chunk in this area. Only kept around so we can free it. */
  57. struct memarea_chunk_t *next_chunk;
  58. size_t mem_size; /**< How much RAM is available in u.mem, total? */
  59. char *next_mem; /**< Next position in u.mem to allocate data at. If it's
  60. * greater than or equal to mem+mem_size, this chunk is
  61. * full. */
  62. union {
  63. char mem[1]; /**< Memory space in this chunk. */
  64. void *_void_for_alignment; /**< Dummy; used to make sure mem is aligned. */
  65. } u;
  66. } memarea_chunk_t;
  67. #define CHUNK_HEADER_SIZE STRUCT_OFFSET(memarea_chunk_t, u)
  68. #define CHUNK_SIZE 4096
  69. /** A memarea_t is an allocation region for a set of small memory requests
  70. * that will all be freed at once. */
  71. struct memarea_t {
  72. memarea_chunk_t *first; /**< Top of the chunk stack: never NULL. */
  73. };
  74. /** How many chunks will we put into the freelist before freeing them? */
  75. #define MAX_FREELIST_LEN 4
  76. /** The number of memarea chunks currently in our freelist. */
  77. static int freelist_len=0;
  78. /** A linked list of unused memory area chunks. Used to prevent us from
  79. * spinning in malloc/free loops. */
  80. static memarea_chunk_t *freelist = NULL;
  81. /** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
  82. static memarea_chunk_t *
  83. alloc_chunk(size_t sz, int freelist_ok)
  84. {
  85. if (freelist && freelist_ok) {
  86. memarea_chunk_t *res = freelist;
  87. freelist = res->next_chunk;
  88. res->next_chunk = NULL;
  89. --freelist_len;
  90. CHECK_SENTINEL(res);
  91. return res;
  92. } else {
  93. size_t chunk_size = freelist_ok ? CHUNK_SIZE : sz;
  94. memarea_chunk_t *res;
  95. chunk_size += SENTINEL_LEN;
  96. res = tor_malloc_roundup(&chunk_size);
  97. res->next_chunk = NULL;
  98. res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
  99. res->next_mem = res->u.mem;
  100. tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
  101. ((char*)res)+chunk_size);
  102. tor_assert(realign_pointer(res->next_mem) == res->next_mem);
  103. SET_SENTINEL(res);
  104. return res;
  105. }
  106. }
  107. /** Release <b>chunk</b> from a memarea, either by adding it to the freelist
  108. * or by freeing it if the freelist is already too big. */
  109. static void
  110. chunk_free_unchecked(memarea_chunk_t *chunk)
  111. {
  112. CHECK_SENTINEL(chunk);
  113. if (freelist_len < MAX_FREELIST_LEN) {
  114. ++freelist_len;
  115. chunk->next_chunk = freelist;
  116. freelist = chunk;
  117. chunk->next_mem = chunk->u.mem;
  118. } else {
  119. tor_free(chunk);
  120. }
  121. }
  122. /** Allocate and return new memarea. */
  123. memarea_t *
  124. memarea_new(void)
  125. {
  126. memarea_t *head = tor_malloc(sizeof(memarea_t));
  127. head->first = alloc_chunk(CHUNK_SIZE, 1);
  128. return head;
  129. }
  130. /** Free <b>area</b>, invalidating all pointers returned from memarea_alloc()
  131. * and friends for this area */
  132. void
  133. memarea_drop_all(memarea_t *area)
  134. {
  135. memarea_chunk_t *chunk, *next;
  136. for (chunk = area->first; chunk; chunk = next) {
  137. next = chunk->next_chunk;
  138. chunk_free_unchecked(chunk);
  139. }
  140. area->first = NULL; /*fail fast on */
  141. tor_free(area);
  142. }
  143. /** Forget about having allocated anything in <b>area</b>, and free some of
  144. * the backing storage associated with it, as appropriate. Invalidates all
  145. * pointers returned from memarea_alloc() for this area. */
  146. void
  147. memarea_clear(memarea_t *area)
  148. {
  149. memarea_chunk_t *chunk, *next;
  150. if (area->first->next_chunk) {
  151. for (chunk = area->first->next_chunk; chunk; chunk = next) {
  152. next = chunk->next_chunk;
  153. chunk_free_unchecked(chunk);
  154. }
  155. area->first->next_chunk = NULL;
  156. }
  157. area->first->next_mem = area->first->u.mem;
  158. }
  159. /** Remove all unused memarea chunks from the internal freelist. */
  160. void
  161. memarea_clear_freelist(void)
  162. {
  163. memarea_chunk_t *chunk, *next;
  164. freelist_len = 0;
  165. for (chunk = freelist; chunk; chunk = next) {
  166. next = chunk->next_chunk;
  167. tor_free(chunk);
  168. }
  169. freelist = NULL;
  170. }
  171. /** Return true iff <b>p</b> is in a range that has been returned by an
  172. * allocation from <b>area</b>. */
  173. int
  174. memarea_owns_ptr(const memarea_t *area, const void *p)
  175. {
  176. memarea_chunk_t *chunk;
  177. const char *ptr = p;
  178. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  179. if (ptr >= chunk->u.mem && ptr < chunk->next_mem)
  180. return 1;
  181. }
  182. return 0;
  183. }
  184. /** Return a pointer to a chunk of memory in <b>area</b> of at least <b>sz</b>
  185. * bytes. <b>sz</b> should be significantly smaller than the area's chunk
  186. * size, though we can deal if it isn't. */
  187. void *
  188. memarea_alloc(memarea_t *area, size_t sz)
  189. {
  190. memarea_chunk_t *chunk = area->first;
  191. char *result;
  192. tor_assert(chunk);
  193. CHECK_SENTINEL(chunk);
  194. if (sz == 0)
  195. sz = 1;
  196. if (chunk->next_mem+sz > chunk->u.mem+chunk->mem_size) {
  197. if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
  198. /* This allocation is too big. Stick it in a special chunk, and put
  199. * that chunk second in the list. */
  200. memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE, 0);
  201. new_chunk->next_chunk = chunk->next_chunk;
  202. chunk->next_chunk = new_chunk;
  203. chunk = new_chunk;
  204. } else {
  205. memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE, 1);
  206. new_chunk->next_chunk = chunk;
  207. area->first = chunk = new_chunk;
  208. }
  209. tor_assert(chunk->mem_size >= sz);
  210. }
  211. result = chunk->next_mem;
  212. chunk->next_mem = chunk->next_mem + sz;
  213. // XXXX021 remove these once bug 930 is solved.
  214. tor_assert(chunk->next_mem >= chunk->u.mem);
  215. tor_assert(chunk->next_mem <= chunk->u.mem+chunk->mem_size);
  216. chunk->next_mem = realign_pointer(chunk->next_mem);
  217. return result;
  218. }
  219. /** As memarea_alloc(), but clears the memory it returns. */
  220. void *
  221. memarea_alloc_zero(memarea_t *area, size_t sz)
  222. {
  223. void *result = memarea_alloc(area, sz);
  224. memset(result, 0, sz);
  225. return result;
  226. }
  227. /** As memdup, but returns the memory from <b>area</b>. */
  228. void *
  229. memarea_memdup(memarea_t *area, const void *s, size_t n)
  230. {
  231. char *result = memarea_alloc(area, n);
  232. memcpy(result, s, n);
  233. return result;
  234. }
  235. /** As strdup, but returns the memory from <b>area</b>. */
  236. char *
  237. memarea_strdup(memarea_t *area, const char *s)
  238. {
  239. return memarea_memdup(area, s, strlen(s)+1);
  240. }
  241. /** As strndup, but returns the memory from <b>area</b>. */
  242. char *
  243. memarea_strndup(memarea_t *area, const char *s, size_t n)
  244. {
  245. size_t ln;
  246. char *result;
  247. const char *cp, *end = s+n;
  248. for (cp = s; cp < end && *cp; ++cp)
  249. ;
  250. /* cp now points to s+n, or to the 0 in the string. */
  251. ln = cp-s;
  252. result = memarea_alloc(area, ln+1);
  253. memcpy(result, s, ln);
  254. result[ln]='\0';
  255. return result;
  256. }
  257. /** Set <b>allocated_out</b> to the number of bytes allocated in <b>area</b>,
  258. * and <b>used_out</b> to the number of bytes currently used. */
  259. void
  260. memarea_get_stats(memarea_t *area, size_t *allocated_out, size_t *used_out)
  261. {
  262. size_t a = 0, u = 0;
  263. memarea_chunk_t *chunk;
  264. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  265. CHECK_SENTINEL(chunk);
  266. a += CHUNK_HEADER_SIZE + chunk->mem_size;
  267. tor_assert(chunk->next_mem >= chunk->u.mem);
  268. u += CHUNK_HEADER_SIZE + (chunk->next_mem - chunk->u.mem);
  269. }
  270. *allocated_out = a;
  271. *used_out = u;
  272. }
  273. /** Assert that <b>area</b> is okay. */
  274. void
  275. memarea_assert_ok(memarea_t *area)
  276. {
  277. memarea_chunk_t *chunk;
  278. tor_assert(area->first);
  279. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  280. CHECK_SENTINEL(chunk);
  281. tor_assert(chunk->next_mem >= chunk->u.mem);
  282. tor_assert(chunk->next_mem <=
  283. (char*) realign_pointer(chunk->u.mem+chunk->mem_size));
  284. }
  285. }