Back to index

tor  0.2.3.18-rc
memarea.c
Go to the documentation of this file.
00001 /* Copyright (c) 2008-2012, The Tor Project, Inc. */
00002 /* See LICENSE for licensing information */
00003 
00009 #include "orconfig.h"
00010 #include <stdlib.h>
00011 #include "memarea.h"
00012 #include "util.h"
00013 #include "compat.h"
00014 #include "torlog.h"
00015 
00018 #define USE_SENTINELS
00019 
00022 #define MEMAREA_ALIGN SIZEOF_VOID_P
00023 
00024 #if MEMAREA_ALIGN == 4
00025 #define MEMAREA_ALIGN_MASK 3lu
00026 #elif MEMAREA_ALIGN == 8
00027 #define MEMAREA_ALIGN_MASK 7lu
00028 #else
00029 #error "void* is neither 4 nor 8 bytes long. I don't know how to align stuff."
00030 #endif
00031 
00032 #ifdef USE_SENTINELS
00033 
00035 #define SENTINEL_VAL 0x90806622u
00036 
00037 #define SENTINEL_LEN sizeof(uint32_t)
00038 
00040 #define SET_SENTINEL(chunk)                                     \
00041   STMT_BEGIN                                                    \
00042   set_uint32( &(chunk)->u.mem[chunk->mem_size], SENTINEL_VAL ); \
00043   STMT_END
00044 
00045 #define CHECK_SENTINEL(chunk)                                           \
00046   STMT_BEGIN                                                            \
00047   uint32_t sent_val = get_uint32(&(chunk)->u.mem[chunk->mem_size]);     \
00048   tor_assert(sent_val == SENTINEL_VAL);                                 \
00049   STMT_END
00050 #else
00051 #define SENTINEL_LEN 0
00052 #define SET_SENTINEL(chunk) STMT_NIL
00053 #define CHECK_SENTINEL(chunk) STMT_NIL
00054 #endif
00055 
00057 static INLINE void *
00058 realign_pointer(void *ptr)
00059 {
00060   uintptr_t x = (uintptr_t)ptr;
00061   x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
00062   /* Reinstate this if bug 930 ever reappears
00063   tor_assert(((void*)x) >= ptr);
00064   */
00065   return (void*)x;
00066 }
00067 
00071 typedef struct memarea_chunk_t {
00073   struct memarea_chunk_t *next_chunk;
00074   size_t mem_size; 
00075   char *next_mem; 
00078   union {
00079     char mem[1]; 
00080     void *_void_for_alignment; 
00081   } u;
00082 } memarea_chunk_t;
00083 
00086 #define CHUNK_HEADER_SIZE STRUCT_OFFSET(memarea_chunk_t, u)
00087 
00089 #define CHUNK_SIZE 4096
00090 
00093 struct memarea_t {
00094   memarea_chunk_t *first; 
00095 };
00096 
00098 #define MAX_FREELIST_LEN 4
00099 
00100 static int freelist_len=0;
00103 static memarea_chunk_t *freelist = NULL;
00104 
00106 static memarea_chunk_t *
00107 alloc_chunk(size_t sz, int freelist_ok)
00108 {
00109   tor_assert(sz < SIZE_T_CEILING);
00110   if (freelist && freelist_ok) {
00111     memarea_chunk_t *res = freelist;
00112     freelist = res->next_chunk;
00113     res->next_chunk = NULL;
00114     --freelist_len;
00115     CHECK_SENTINEL(res);
00116     return res;
00117   } else {
00118     size_t chunk_size = freelist_ok ? CHUNK_SIZE : sz;
00119     memarea_chunk_t *res;
00120     chunk_size += SENTINEL_LEN;
00121     res = tor_malloc_roundup(&chunk_size);
00122     res->next_chunk = NULL;
00123     res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
00124     res->next_mem = res->u.mem;
00125     tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
00126                ((char*)res)+chunk_size);
00127     tor_assert(realign_pointer(res->next_mem) == res->next_mem);
00128     SET_SENTINEL(res);
00129     return res;
00130   }
00131 }
00132 
00135 static void
00136 chunk_free_unchecked(memarea_chunk_t *chunk)
00137 {
00138   CHECK_SENTINEL(chunk);
00139   if (freelist_len < MAX_FREELIST_LEN) {
00140     ++freelist_len;
00141     chunk->next_chunk = freelist;
00142     freelist = chunk;
00143     chunk->next_mem = chunk->u.mem;
00144   } else {
00145     tor_free(chunk);
00146   }
00147 }
00148 
00150 memarea_t *
00151 memarea_new(void)
00152 {
00153   memarea_t *head = tor_malloc(sizeof(memarea_t));
00154   head->first = alloc_chunk(CHUNK_SIZE, 1);
00155   return head;
00156 }
00157 
00160 void
00161 memarea_drop_all(memarea_t *area)
00162 {
00163   memarea_chunk_t *chunk, *next;
00164   for (chunk = area->first; chunk; chunk = next) {
00165     next = chunk->next_chunk;
00166     chunk_free_unchecked(chunk);
00167   }
00168   area->first = NULL; /*fail fast on */
00169   tor_free(area);
00170 }
00171 
00175 void
00176 memarea_clear(memarea_t *area)
00177 {
00178   memarea_chunk_t *chunk, *next;
00179   if (area->first->next_chunk) {
00180     for (chunk = area->first->next_chunk; chunk; chunk = next) {
00181       next = chunk->next_chunk;
00182       chunk_free_unchecked(chunk);
00183     }
00184     area->first->next_chunk = NULL;
00185   }
00186   area->first->next_mem = area->first->u.mem;
00187 }
00188 
00190 void
00191 memarea_clear_freelist(void)
00192 {
00193   memarea_chunk_t *chunk, *next;
00194   freelist_len = 0;
00195   for (chunk = freelist; chunk; chunk = next) {
00196     next = chunk->next_chunk;
00197     tor_free(chunk);
00198   }
00199   freelist = NULL;
00200 }
00201 
00204 int
00205 memarea_owns_ptr(const memarea_t *area, const void *p)
00206 {
00207   memarea_chunk_t *chunk;
00208   const char *ptr = p;
00209   for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
00210     if (ptr >= chunk->u.mem && ptr < chunk->next_mem)
00211       return 1;
00212   }
00213   return 0;
00214 }
00215 
00219 void *
00220 memarea_alloc(memarea_t *area, size_t sz)
00221 {
00222   memarea_chunk_t *chunk = area->first;
00223   char *result;
00224   tor_assert(chunk);
00225   CHECK_SENTINEL(chunk);
00226   tor_assert(sz < SIZE_T_CEILING);
00227   if (sz == 0)
00228     sz = 1;
00229   if (chunk->next_mem+sz > chunk->u.mem+chunk->mem_size) {
00230     if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
00231       /* This allocation is too big.  Stick it in a special chunk, and put
00232        * that chunk second in the list. */
00233       memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE, 0);
00234       new_chunk->next_chunk = chunk->next_chunk;
00235       chunk->next_chunk = new_chunk;
00236       chunk = new_chunk;
00237     } else {
00238       memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE, 1);
00239       new_chunk->next_chunk = chunk;
00240       area->first = chunk = new_chunk;
00241     }
00242     tor_assert(chunk->mem_size >= sz);
00243   }
00244   result = chunk->next_mem;
00245   chunk->next_mem = chunk->next_mem + sz;
00246   /* Reinstate these if bug 930 ever comes back
00247   tor_assert(chunk->next_mem >= chunk->u.mem);
00248   tor_assert(chunk->next_mem <= chunk->u.mem+chunk->mem_size);
00249   */
00250   chunk->next_mem = realign_pointer(chunk->next_mem);
00251   return result;
00252 }
00253 
00255 void *
00256 memarea_alloc_zero(memarea_t *area, size_t sz)
00257 {
00258   void *result = memarea_alloc(area, sz);
00259   memset(result, 0, sz);
00260   return result;
00261 }
00262 
00264 void *
00265 memarea_memdup(memarea_t *area, const void *s, size_t n)
00266 {
00267   char *result = memarea_alloc(area, n);
00268   memcpy(result, s, n);
00269   return result;
00270 }
00271 
00273 char *
00274 memarea_strdup(memarea_t *area, const char *s)
00275 {
00276   return memarea_memdup(area, s, strlen(s)+1);
00277 }
00278 
00280 char *
00281 memarea_strndup(memarea_t *area, const char *s, size_t n)
00282 {
00283   size_t ln;
00284   char *result;
00285   const char *cp, *end = s+n;
00286   tor_assert(n < SIZE_T_CEILING);
00287   for (cp = s; cp < end && *cp; ++cp)
00288     ;
00289   /* cp now points to s+n, or to the 0 in the string. */
00290   ln = cp-s;
00291   result = memarea_alloc(area, ln+1);
00292   memcpy(result, s, ln);
00293   result[ln]='\0';
00294   return result;
00295 }
00296 
00299 void
00300 memarea_get_stats(memarea_t *area, size_t *allocated_out, size_t *used_out)
00301 {
00302   size_t a = 0, u = 0;
00303   memarea_chunk_t *chunk;
00304   for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
00305     CHECK_SENTINEL(chunk);
00306     a += CHUNK_HEADER_SIZE + chunk->mem_size;
00307     tor_assert(chunk->next_mem >= chunk->u.mem);
00308     u += CHUNK_HEADER_SIZE + (chunk->next_mem - chunk->u.mem);
00309   }
00310   *allocated_out = a;
00311   *used_out = u;
00312 }
00313 
00315 void
00316 memarea_assert_ok(memarea_t *area)
00317 {
00318   memarea_chunk_t *chunk;
00319   tor_assert(area->first);
00320 
00321   for (chunk = area->first; chunk; chunk = chunk->next_chunk) {
00322     CHECK_SENTINEL(chunk);
00323     tor_assert(chunk->next_mem >= chunk->u.mem);
00324     tor_assert(chunk->next_mem <=
00325           (char*) realign_pointer(chunk->u.mem+chunk->mem_size));
00326   }
00327 }
00328