memarea.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403
  1. /* Copyright (c) 2008-2018, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file memarea.c
  5. *
  6. * \brief Implementation for memarea_t, an allocator for allocating lots of
  7. * small objects that will be freed all at once.
  8. */
  9. #include "orconfig.h"
  10. #include "lib/memarea/memarea.h"
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include "lib/arch/bytes.h"
  14. #include "lib/cc/torint.h"
  15. #include "lib/container/smartlist.h"
  16. #include "lib/log/log.h"
  17. #include "lib/log/util_bug.h"
  18. #include "lib/malloc/malloc.h"
  19. #ifndef DISABLE_MEMORY_SENTINELS
  20. /** If true, we try to detect any attempts to write beyond the length of a
  21. * memarea. */
  22. #define USE_SENTINELS
  23. /** All returned pointers should be aligned to the nearest multiple of this
  24. * value. */
  25. #define MEMAREA_ALIGN SIZEOF_VOID_P
  26. /** A value which, when masked out of a pointer, produces a maximally aligned
  27. * pointer. */
  28. #if MEMAREA_ALIGN == 4
  29. #define MEMAREA_ALIGN_MASK ((uintptr_t)3)
  30. #elif MEMAREA_ALIGN == 8
  31. #define MEMAREA_ALIGN_MASK ((uintptr_t)7)
  32. #else
  33. #error "void* is neither 4 nor 8 bytes long. I don't know how to align stuff."
  34. #endif /* MEMAREA_ALIGN == 4 || ... */
  35. #if defined(__GNUC__) && defined(FLEXIBLE_ARRAY_MEMBER)
  36. #define USE_ALIGNED_ATTRIBUTE
  37. /** Name for the 'memory' member of a memory chunk. */
  38. #define U_MEM mem
  39. #else
  40. #define U_MEM u.mem
  41. #endif /* defined(__GNUC__) && defined(FLEXIBLE_ARRAY_MEMBER) */
  42. #ifdef USE_SENTINELS
  43. /** Magic value that we stick at the end of a memarea so we can make sure
  44. * there are no run-off-the-end bugs. */
  45. #define SENTINEL_VAL 0x90806622u
  46. /** How many bytes per area do we devote to the sentinel? */
  47. #define SENTINEL_LEN sizeof(uint32_t)
  48. /** Given a mem_area_chunk_t with SENTINEL_LEN extra bytes allocated at the
  49. * end, set those bytes. */
  50. #define SET_SENTINEL(chunk) \
  51. STMT_BEGIN \
  52. set_uint32( &(chunk)->U_MEM[chunk->mem_size], SENTINEL_VAL ); \
  53. STMT_END
  54. /** Assert that the sentinel on a memarea is set correctly. */
  55. #define CHECK_SENTINEL(chunk) \
  56. STMT_BEGIN \
  57. uint32_t sent_val = get_uint32(&(chunk)->U_MEM[chunk->mem_size]); \
  58. tor_assert(sent_val == SENTINEL_VAL); \
  59. STMT_END
  60. #else /* !(defined(USE_SENTINELS)) */
  61. #define SENTINEL_LEN 0
  62. #define SET_SENTINEL(chunk) STMT_NIL
  63. #define CHECK_SENTINEL(chunk) STMT_NIL
  64. #endif /* defined(USE_SENTINELS) */
  65. /** Increment <b>ptr</b> until it is aligned to MEMAREA_ALIGN. */
  66. static inline void *
  67. realign_pointer(void *ptr)
  68. {
  69. uintptr_t x = (uintptr_t)ptr;
  70. x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
  71. /* Reinstate this if bug 930 ever reappears
  72. tor_assert(((void*)x) >= ptr);
  73. */
  74. return (void*)x;
  75. }
  76. /** Implements part of a memarea. New memory is carved off from chunk->mem in
  77. * increasing order until a request is too big, at which point a new chunk is
  78. * allocated. */
  79. typedef struct memarea_chunk_t {
  80. /** Next chunk in this area. Only kept around so we can free it. */
  81. struct memarea_chunk_t *next_chunk;
  82. size_t mem_size; /**< How much RAM is available in mem, total? */
  83. char *next_mem; /**< Next position in mem to allocate data at. If it's
  84. * equal to mem+mem_size, this chunk is full. */
  85. #ifdef USE_ALIGNED_ATTRIBUTE
  86. /** Actual content of the memory chunk. */
  87. char mem[FLEXIBLE_ARRAY_MEMBER] __attribute__((aligned(MEMAREA_ALIGN)));
  88. #else
  89. union {
  90. char mem[1]; /**< Memory space in this chunk. */
  91. void *void_for_alignment_; /**< Dummy; used to make sure mem is aligned. */
  92. } u; /**< Union used to enforce alignment when we don't have support for
  93. * doing it right. */
  94. #endif /* defined(USE_ALIGNED_ATTRIBUTE) */
  95. } memarea_chunk_t;
  96. /** How many bytes are needed for overhead before we get to the memory part
  97. * of a chunk? */
  98. #define CHUNK_HEADER_SIZE offsetof(memarea_chunk_t, U_MEM)
  99. /** What's the smallest that we'll allocate a chunk? */
  100. #define CHUNK_SIZE 4096
  101. /** A memarea_t is an allocation region for a set of small memory requests
  102. * that will all be freed at once. */
  103. struct memarea_t {
  104. memarea_chunk_t *first; /**< Top of the chunk stack: never NULL. */
  105. };
  106. /** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
  107. static memarea_chunk_t *
  108. alloc_chunk(size_t sz)
  109. {
  110. tor_assert(sz < SIZE_T_CEILING);
  111. size_t chunk_size = sz < CHUNK_SIZE ? CHUNK_SIZE : sz;
  112. memarea_chunk_t *res;
  113. chunk_size += SENTINEL_LEN;
  114. res = tor_malloc(chunk_size);
  115. res->next_chunk = NULL;
  116. res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
  117. res->next_mem = res->U_MEM;
  118. tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
  119. ((char*)res)+chunk_size);
  120. tor_assert(realign_pointer(res->next_mem) == res->next_mem);
  121. SET_SENTINEL(res);
  122. return res;
  123. }
  124. /** Release <b>chunk</b> from a memarea. */
  125. static void
  126. memarea_chunk_free_unchecked(memarea_chunk_t *chunk)
  127. {
  128. CHECK_SENTINEL(chunk);
  129. tor_free(chunk);
  130. }
  131. /** Allocate and return new memarea. */
  132. memarea_t *
  133. memarea_new(void)
  134. {
  135. memarea_t *head = tor_malloc(sizeof(memarea_t));
  136. head->first = alloc_chunk(CHUNK_SIZE);
  137. return head;
  138. }
  139. /** Free <b>area</b>, invalidating all pointers returned from memarea_alloc()
  140. * and friends for this area */
  141. void
  142. memarea_drop_all_(memarea_t *area)
  143. {
  144. memarea_chunk_t *chunk, *next;
  145. for (chunk = area->first; chunk; chunk = next) {
  146. next = chunk->next_chunk;
  147. memarea_chunk_free_unchecked(chunk);
  148. }
  149. area->first = NULL; /*fail fast on */
  150. tor_free(area);
  151. }
  152. /** Forget about having allocated anything in <b>area</b>, and free some of
  153. * the backing storage associated with it, as appropriate. Invalidates all
  154. * pointers returned from memarea_alloc() for this area. */
  155. void
  156. memarea_clear(memarea_t *area)
  157. {
  158. memarea_chunk_t *chunk, *next;
  159. if (area->first->next_chunk) {
  160. for (chunk = area->first->next_chunk; chunk; chunk = next) {
  161. next = chunk->next_chunk;
  162. memarea_chunk_free_unchecked(chunk);
  163. }
  164. area->first->next_chunk = NULL;
  165. }
  166. area->first->next_mem = area->first->U_MEM;
  167. }
  168. /** Return true iff <b>p</b> is in a range that has been returned by an
  169. * allocation from <b>area</b>. */
  170. int
  171. memarea_owns_ptr(const memarea_t *area, const void *p)
  172. {
  173. memarea_chunk_t *chunk;
  174. const char *ptr = p;
  175. for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
  176. if (ptr >= chunk->U_MEM && ptr < chunk->next_mem)
  177. return 1;
  178. }
  179. return 0;
  180. }
  181. /** Return a pointer to a chunk of memory in <b>area</b> of at least <b>sz</b>
  182. * bytes. <b>sz</b> should be significantly smaller than the area's chunk
  183. * size, though we can deal if it isn't. */
  184. void *
  185. memarea_alloc(memarea_t *area, size_t sz)
  186. {
  187. memarea_chunk_t *chunk = area->first;
  188. char *result;
  189. tor_assert(chunk);
  190. CHECK_SENTINEL(chunk);
  191. tor_assert(sz < SIZE_T_CEILING);
  192. if (sz == 0)
  193. sz = 1;
  194. tor_assert(chunk->next_mem <= chunk->U_MEM + chunk->mem_size);
  195. const size_t space_remaining =
  196. (chunk->U_MEM + chunk->mem_size) - chunk->next_mem;
  197. if (sz > space_remaining) {
  198. if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
  199. /* This allocation is too big. Stick it in a special chunk, and put
  200. * that chunk second in the list. */
  201. memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE);
  202. new_chunk->next_chunk = chunk->next_chunk;
  203. chunk->next_chunk = new_chunk;
  204. chunk = new_chunk;
  205. } else {
  206. memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE);
  207. new_chunk->next_chunk = chunk;
  208. area->first = chunk = new_chunk;
  209. }
  210. tor_assert(chunk->mem_size >= sz);
  211. }
  212. result = chunk->next_mem;
  213. chunk->next_mem = chunk->next_mem + sz;
  214. /* Reinstate these if bug 930 ever comes back
  215. tor_assert(chunk->next_mem >= chunk->U_MEM);
  216. tor_assert(chunk->next_mem <= chunk->U_MEM+chunk->mem_size);
  217. */
  218. chunk->next_mem = realign_pointer(chunk->next_mem);
  219. return result;
  220. }
  221. /** As memarea_alloc(), but clears the memory it returns. */
  222. void *
  223. memarea_alloc_zero(memarea_t *area, size_t sz)
  224. {
  225. void *result = memarea_alloc(area, sz);
  226. memset(result, 0, sz);
  227. return result;
  228. }
  229. /** As memdup, but returns the memory from <b>area</b>. */
  230. void *
  231. memarea_memdup(memarea_t *area, const void *s, size_t n)
  232. {
  233. char *result = memarea_alloc(area, n);
  234. memcpy(result, s, n);
  235. return result;
  236. }
  237. /** As strdup, but returns the memory from <b>area</b>. */
  238. char *
  239. memarea_strdup(memarea_t *area, const char *s)
  240. {
  241. return memarea_memdup(area, s, strlen(s)+1);
  242. }
  243. /** As strndup, but returns the memory from <b>area</b>. */
  244. char *
  245. memarea_strndup(memarea_t *area, const char *s, size_t n)
  246. {
  247. size_t ln = 0;
  248. char *result;
  249. tor_assert(n < SIZE_T_CEILING);
  250. for (ln = 0; ln < n && s[ln]; ++ln)
  251. ;
  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. }
  286. #else /* !(!defined(DISABLE_MEMORY_SENTINELS)) */
  287. struct memarea_t {
  288. smartlist_t *pieces;
  289. };
  290. memarea_t *
  291. memarea_new(void)
  292. {
  293. memarea_t *ma = tor_malloc_zero(sizeof(memarea_t));
  294. ma->pieces = smartlist_new();
  295. return ma;
  296. }
  297. void
  298. memarea_drop_all_(memarea_t *area)
  299. {
  300. memarea_clear(area);
  301. smartlist_free(area->pieces);
  302. tor_free(area);
  303. }
  304. void
  305. memarea_clear(memarea_t *area)
  306. {
  307. SMARTLIST_FOREACH(area->pieces, void *, p, tor_free_(p));
  308. smartlist_clear(area->pieces);
  309. }
  310. int
  311. memarea_owns_ptr(const memarea_t *area, const void *ptr)
  312. {
  313. SMARTLIST_FOREACH(area->pieces, const void *, p, if (ptr == p) return 1;);
  314. return 0;
  315. }
  316. void *
  317. memarea_alloc(memarea_t *area, size_t sz)
  318. {
  319. void *result = tor_malloc(sz);
  320. smartlist_add(area->pieces, result);
  321. return result;
  322. }
  323. void *
  324. memarea_alloc_zero(memarea_t *area, size_t sz)
  325. {
  326. void *result = tor_malloc_zero(sz);
  327. smartlist_add(area->pieces, result);
  328. return result;
  329. }
  330. void *
  331. memarea_memdup(memarea_t *area, const void *s, size_t n)
  332. {
  333. void *r = memarea_alloc(area, n);
  334. memcpy(r, s, n);
  335. return r;
  336. }
  337. char *
  338. memarea_strdup(memarea_t *area, const char *s)
  339. {
  340. size_t n = strlen(s);
  341. char *r = memarea_alloc(area, n+1);
  342. memcpy(r, s, n);
  343. r[n] = 0;
  344. return r;
  345. }
  346. char *
  347. memarea_strndup(memarea_t *area, const char *s, size_t n)
  348. {
  349. size_t ln = strnlen(s, n);
  350. char *r = memarea_alloc(area, ln+1);
  351. memcpy(r, s, ln);
  352. r[ln] = 0;
  353. return r;
  354. }
  355. void
  356. memarea_get_stats(memarea_t *area,
  357. size_t *allocated_out, size_t *used_out)
  358. {
  359. (void)area;
  360. *allocated_out = *used_out = 128;
  361. }
  362. void
  363. memarea_assert_ok(memarea_t *area)
  364. {
  365. (void)area;
  366. }
  367. #endif /* !defined(DISABLE_MEMORY_SENTINELS) */