123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403 |
- /* Copyright (c) 2008-2018, The Tor Project, Inc. */
- /* See LICENSE for licensing information */
- /**
- * \file memarea.c
- *
- * \brief Implementation for memarea_t, an allocator for allocating lots of
- * small objects that will be freed all at once.
- */
- #include "orconfig.h"
- #include "lib/memarea/memarea.h"
- #include <stdlib.h>
- #include <string.h>
- #include "lib/arch/bytes.h"
- #include "lib/cc/torint.h"
- #include "lib/container/smartlist.h"
- #include "lib/log/log.h"
- #include "lib/log/util_bug.h"
- #include "lib/malloc/malloc.h"
- #ifndef DISABLE_MEMORY_SENTINELS
- /** If true, we try to detect any attempts to write beyond the length of a
- * memarea. */
- #define USE_SENTINELS
- /** All returned pointers should be aligned to the nearest multiple of this
- * value. */
- #define MEMAREA_ALIGN SIZEOF_VOID_P
- /** A value which, when masked out of a pointer, produces a maximally aligned
- * pointer. */
- #if MEMAREA_ALIGN == 4
- #define MEMAREA_ALIGN_MASK ((uintptr_t)3)
- #elif MEMAREA_ALIGN == 8
- #define MEMAREA_ALIGN_MASK ((uintptr_t)7)
- #else
- #error "void* is neither 4 nor 8 bytes long. I don't know how to align stuff."
- #endif /* MEMAREA_ALIGN == 4 || ... */
- #if defined(__GNUC__) && defined(FLEXIBLE_ARRAY_MEMBER)
- #define USE_ALIGNED_ATTRIBUTE
- /** Name for the 'memory' member of a memory chunk. */
- #define U_MEM mem
- #else
- #define U_MEM u.mem
- #endif /* defined(__GNUC__) && defined(FLEXIBLE_ARRAY_MEMBER) */
- #ifdef USE_SENTINELS
- /** Magic value that we stick at the end of a memarea so we can make sure
- * there are no run-off-the-end bugs. */
- #define SENTINEL_VAL 0x90806622u
- /** How many bytes per area do we devote to the sentinel? */
- #define SENTINEL_LEN sizeof(uint32_t)
- /** Given a mem_area_chunk_t with SENTINEL_LEN extra bytes allocated at the
- * end, set those bytes. */
- #define SET_SENTINEL(chunk) \
- STMT_BEGIN \
- set_uint32( &(chunk)->U_MEM[chunk->mem_size], SENTINEL_VAL ); \
- STMT_END
- /** Assert that the sentinel on a memarea is set correctly. */
- #define CHECK_SENTINEL(chunk) \
- STMT_BEGIN \
- uint32_t sent_val = get_uint32(&(chunk)->U_MEM[chunk->mem_size]); \
- tor_assert(sent_val == SENTINEL_VAL); \
- STMT_END
- #else /* !(defined(USE_SENTINELS)) */
- #define SENTINEL_LEN 0
- #define SET_SENTINEL(chunk) STMT_NIL
- #define CHECK_SENTINEL(chunk) STMT_NIL
- #endif /* defined(USE_SENTINELS) */
- /** Increment <b>ptr</b> until it is aligned to MEMAREA_ALIGN. */
- static inline void *
- realign_pointer(void *ptr)
- {
- uintptr_t x = (uintptr_t)ptr;
- x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
- /* Reinstate this if bug 930 ever reappears
- tor_assert(((void*)x) >= ptr);
- */
- return (void*)x;
- }
- /** Implements part of a memarea. New memory is carved off from chunk->mem in
- * increasing order until a request is too big, at which point a new chunk is
- * allocated. */
- typedef struct memarea_chunk_t {
- /** Next chunk in this area. Only kept around so we can free it. */
- struct memarea_chunk_t *next_chunk;
- size_t mem_size; /**< How much RAM is available in mem, total? */
- char *next_mem; /**< Next position in mem to allocate data at. If it's
- * equal to mem+mem_size, this chunk is full. */
- #ifdef USE_ALIGNED_ATTRIBUTE
- /** Actual content of the memory chunk. */
- char mem[FLEXIBLE_ARRAY_MEMBER] __attribute__((aligned(MEMAREA_ALIGN)));
- #else
- union {
- char mem[1]; /**< Memory space in this chunk. */
- void *void_for_alignment_; /**< Dummy; used to make sure mem is aligned. */
- } u; /**< Union used to enforce alignment when we don't have support for
- * doing it right. */
- #endif /* defined(USE_ALIGNED_ATTRIBUTE) */
- } memarea_chunk_t;
- /** How many bytes are needed for overhead before we get to the memory part
- * of a chunk? */
- #define CHUNK_HEADER_SIZE offsetof(memarea_chunk_t, U_MEM)
- /** What's the smallest that we'll allocate a chunk? */
- #define CHUNK_SIZE 4096
- /** A memarea_t is an allocation region for a set of small memory requests
- * that will all be freed at once. */
- struct memarea_t {
- memarea_chunk_t *first; /**< Top of the chunk stack: never NULL. */
- };
- /** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
- static memarea_chunk_t *
- alloc_chunk(size_t sz)
- {
- tor_assert(sz < SIZE_T_CEILING);
- size_t chunk_size = sz < CHUNK_SIZE ? CHUNK_SIZE : sz;
- memarea_chunk_t *res;
- chunk_size += SENTINEL_LEN;
- res = tor_malloc(chunk_size);
- res->next_chunk = NULL;
- res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
- res->next_mem = res->U_MEM;
- tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
- ((char*)res)+chunk_size);
- tor_assert(realign_pointer(res->next_mem) == res->next_mem);
- SET_SENTINEL(res);
- return res;
- }
- /** Release <b>chunk</b> from a memarea. */
- static void
- memarea_chunk_free_unchecked(memarea_chunk_t *chunk)
- {
- CHECK_SENTINEL(chunk);
- tor_free(chunk);
- }
- /** Allocate and return new memarea. */
- memarea_t *
- memarea_new(void)
- {
- memarea_t *head = tor_malloc(sizeof(memarea_t));
- head->first = alloc_chunk(CHUNK_SIZE);
- return head;
- }
- /** Free <b>area</b>, invalidating all pointers returned from memarea_alloc()
- * and friends for this area */
- void
- memarea_drop_all_(memarea_t *area)
- {
- memarea_chunk_t *chunk, *next;
- for (chunk = area->first; chunk; chunk = next) {
- next = chunk->next_chunk;
- memarea_chunk_free_unchecked(chunk);
- }
- area->first = NULL; /*fail fast on */
- tor_free(area);
- }
- /** Forget about having allocated anything in <b>area</b>, and free some of
- * the backing storage associated with it, as appropriate. Invalidates all
- * pointers returned from memarea_alloc() for this area. */
- void
- memarea_clear(memarea_t *area)
- {
- memarea_chunk_t *chunk, *next;
- if (area->first->next_chunk) {
- for (chunk = area->first->next_chunk; chunk; chunk = next) {
- next = chunk->next_chunk;
- memarea_chunk_free_unchecked(chunk);
- }
- area->first->next_chunk = NULL;
- }
- area->first->next_mem = area->first->U_MEM;
- }
- /** Return true iff <b>p</b> is in a range that has been returned by an
- * allocation from <b>area</b>. */
- int
- memarea_owns_ptr(const memarea_t *area, const void *p)
- {
- memarea_chunk_t *chunk;
- const char *ptr = p;
- for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
- if (ptr >= chunk->U_MEM && ptr < chunk->next_mem)
- return 1;
- }
- return 0;
- }
- /** Return a pointer to a chunk of memory in <b>area</b> of at least <b>sz</b>
- * bytes. <b>sz</b> should be significantly smaller than the area's chunk
- * size, though we can deal if it isn't. */
- void *
- memarea_alloc(memarea_t *area, size_t sz)
- {
- memarea_chunk_t *chunk = area->first;
- char *result;
- tor_assert(chunk);
- CHECK_SENTINEL(chunk);
- tor_assert(sz < SIZE_T_CEILING);
- if (sz == 0)
- sz = 1;
- tor_assert(chunk->next_mem <= chunk->U_MEM + chunk->mem_size);
- const size_t space_remaining =
- (chunk->U_MEM + chunk->mem_size) - chunk->next_mem;
- if (sz > space_remaining) {
- if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
- /* This allocation is too big. Stick it in a special chunk, and put
- * that chunk second in the list. */
- memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE);
- new_chunk->next_chunk = chunk->next_chunk;
- chunk->next_chunk = new_chunk;
- chunk = new_chunk;
- } else {
- memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE);
- new_chunk->next_chunk = chunk;
- area->first = chunk = new_chunk;
- }
- tor_assert(chunk->mem_size >= sz);
- }
- result = chunk->next_mem;
- chunk->next_mem = chunk->next_mem + sz;
- /* Reinstate these if bug 930 ever comes back
- tor_assert(chunk->next_mem >= chunk->U_MEM);
- tor_assert(chunk->next_mem <= chunk->U_MEM+chunk->mem_size);
- */
- chunk->next_mem = realign_pointer(chunk->next_mem);
- return result;
- }
- /** As memarea_alloc(), but clears the memory it returns. */
- void *
- memarea_alloc_zero(memarea_t *area, size_t sz)
- {
- void *result = memarea_alloc(area, sz);
- memset(result, 0, sz);
- return result;
- }
- /** As memdup, but returns the memory from <b>area</b>. */
- void *
- memarea_memdup(memarea_t *area, const void *s, size_t n)
- {
- char *result = memarea_alloc(area, n);
- memcpy(result, s, n);
- return result;
- }
- /** As strdup, but returns the memory from <b>area</b>. */
- char *
- memarea_strdup(memarea_t *area, const char *s)
- {
- return memarea_memdup(area, s, strlen(s)+1);
- }
- /** As strndup, but returns the memory from <b>area</b>. */
- char *
- memarea_strndup(memarea_t *area, const char *s, size_t n)
- {
- size_t ln = 0;
- char *result;
- tor_assert(n < SIZE_T_CEILING);
- for (ln = 0; ln < n && s[ln]; ++ln)
- ;
- result = memarea_alloc(area, ln+1);
- memcpy(result, s, ln);
- result[ln]='\0';
- return result;
- }
- /** Set <b>allocated_out</b> to the number of bytes allocated in <b>area</b>,
- * and <b>used_out</b> to the number of bytes currently used. */
- void
- memarea_get_stats(memarea_t *area, size_t *allocated_out, size_t *used_out)
- {
- size_t a = 0, u = 0;
- memarea_chunk_t *chunk;
- for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
- CHECK_SENTINEL(chunk);
- a += CHUNK_HEADER_SIZE + chunk->mem_size;
- tor_assert(chunk->next_mem >= chunk->U_MEM);
- u += CHUNK_HEADER_SIZE + (chunk->next_mem - chunk->U_MEM);
- }
- *allocated_out = a;
- *used_out = u;
- }
- /** Assert that <b>area</b> is okay. */
- void
- memarea_assert_ok(memarea_t *area)
- {
- memarea_chunk_t *chunk;
- tor_assert(area->first);
- for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
- CHECK_SENTINEL(chunk);
- tor_assert(chunk->next_mem >= chunk->U_MEM);
- tor_assert(chunk->next_mem <=
- (char*) realign_pointer(chunk->U_MEM+chunk->mem_size));
- }
- }
- #else /* !(!defined(DISABLE_MEMORY_SENTINELS)) */
- struct memarea_t {
- smartlist_t *pieces;
- };
- memarea_t *
- memarea_new(void)
- {
- memarea_t *ma = tor_malloc_zero(sizeof(memarea_t));
- ma->pieces = smartlist_new();
- return ma;
- }
- void
- memarea_drop_all_(memarea_t *area)
- {
- memarea_clear(area);
- smartlist_free(area->pieces);
- tor_free(area);
- }
- void
- memarea_clear(memarea_t *area)
- {
- SMARTLIST_FOREACH(area->pieces, void *, p, tor_free_(p));
- smartlist_clear(area->pieces);
- }
- int
- memarea_owns_ptr(const memarea_t *area, const void *ptr)
- {
- SMARTLIST_FOREACH(area->pieces, const void *, p, if (ptr == p) return 1;);
- return 0;
- }
- void *
- memarea_alloc(memarea_t *area, size_t sz)
- {
- void *result = tor_malloc(sz);
- smartlist_add(area->pieces, result);
- return result;
- }
- void *
- memarea_alloc_zero(memarea_t *area, size_t sz)
- {
- void *result = tor_malloc_zero(sz);
- smartlist_add(area->pieces, result);
- return result;
- }
- void *
- memarea_memdup(memarea_t *area, const void *s, size_t n)
- {
- void *r = memarea_alloc(area, n);
- memcpy(r, s, n);
- return r;
- }
- char *
- memarea_strdup(memarea_t *area, const char *s)
- {
- size_t n = strlen(s);
- char *r = memarea_alloc(area, n+1);
- memcpy(r, s, n);
- r[n] = 0;
- return r;
- }
- char *
- memarea_strndup(memarea_t *area, const char *s, size_t n)
- {
- size_t ln = strnlen(s, n);
- char *r = memarea_alloc(area, ln+1);
- memcpy(r, s, ln);
- r[ln] = 0;
- return r;
- }
- void
- memarea_get_stats(memarea_t *area,
- size_t *allocated_out, size_t *used_out)
- {
- (void)area;
- *allocated_out = *used_out = 128;
- }
- void
- memarea_assert_ok(memarea_t *area)
- {
- (void)area;
- }
- #endif /* !defined(DISABLE_MEMORY_SENTINELS) */
|