memarea.c 9.2 KB
Newer Older
Karsten Loesing's avatar
Karsten Loesing committed
1
/* Copyright (c) 2008-2009, The Tor Project, Inc. */
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 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 <stdlib.h>
#include "memarea.h"
#include "util.h"
#include "compat.h"
#include "log.h"

16
17
18
19
/** If true, we try to detect any attempts to write beyond the length of a
 * memarea. */
#define USE_SENTINELS

20
21
22
23
24
25
26
27
28
29
30
31
/** All returned pointers should be aligned to the nearest multiple of this
 * value. */
#define MEMAREA_ALIGN SIZEOF_VOID_P

#if MEMAREA_ALIGN == 4
#define MEMAREA_ALIGN_MASK 3lu
#elif MEMAREA_ALIGN == 8
#define MEMAREA_ALIGN_MASK 7lu
#else
#error "void* is neither 4 nor 8 bytes long. I don't know how to align stuff."
#endif

32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#ifdef USE_SENTINELS
#define SENTINEL_VAL 0x90806622u
#define SENTINEL_LEN sizeof(uint32_t)
#define SET_SENTINEL(chunk)                                     \
  STMT_BEGIN                                                    \
  set_uint32( &(chunk)->u.mem[chunk->mem_size], SENTINEL_VAL ); \
  STMT_END
#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
#define SENTINEL_LEN 0
#define SET_SENTINEL(chunk) STMT_NIL
#define CHECK_SENTINEL(chunk) STMT_NIL
#endif

50
/** Increment <b>ptr</b> until it is aligned to MEMAREA_ALIGN. */
51
52
53
54
55
static INLINE void *
realign_pointer(void *ptr)
{
  uintptr_t x = (uintptr_t)ptr;
  x = (x+MEMAREA_ALIGN_MASK) & ~MEMAREA_ALIGN_MASK;
56
  tor_assert(((void*)x) >= ptr); // XXXX021 remove this once bug 930 is solved
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
  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 u.mem, total? */
  char *next_mem; /**< Next position in u.mem to allocate data at.  If it's
                   * greater than or equal to mem+mem_size, this chunk is
                   * full. */
  union {
    char mem[1]; /**< Memory space in this chunk.  */
    void *_void_for_alignment; /**< Dummy; used to make sure mem is aligned. */
  } u;
} memarea_chunk_t;

#define CHUNK_HEADER_SIZE STRUCT_OFFSET(memarea_chunk_t, u)

78
#define CHUNK_SIZE 4096
79

80
81
82
/** A memarea_t is an allocation region for a set of small memory requests
 * that will all be freed at once. */
struct memarea_t {
83
  memarea_chunk_t *first; /**< Top of the chunk stack: never NULL. */
84
85
};

86
/** How many chunks will we put into the freelist before freeing them? */
87
#define MAX_FREELIST_LEN 4
88
89
90
91
/** The number of memarea chunks currently in our freelist. */
static int freelist_len=0;
/** A linked list of unused memory area chunks.  Used to prevent us from
 * spinning in malloc/free loops. */
92
93
static memarea_chunk_t *freelist = NULL;

94
95
/** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
static memarea_chunk_t *
96
alloc_chunk(size_t sz, int freelist_ok)
97
{
98
  if (freelist && freelist_ok) {
99
100
    memarea_chunk_t *res = freelist;
    freelist = res->next_chunk;
101
    res->next_chunk = NULL;
102
    --freelist_len;
103
    CHECK_SENTINEL(res);
104
105
    return res;
  } else {
106
    size_t chunk_size = freelist_ok ? CHUNK_SIZE : sz;
107
108
109
    memarea_chunk_t *res;
    chunk_size += SENTINEL_LEN;
    res = tor_malloc_roundup(&chunk_size);
110
    res->next_chunk = NULL;
111
    res->mem_size = chunk_size - CHUNK_HEADER_SIZE - SENTINEL_LEN;
112
    res->next_mem = res->u.mem;
113
114
    tor_assert(res->next_mem+res->mem_size+SENTINEL_LEN ==
               ((char*)res)+chunk_size);
115
    tor_assert(realign_pointer(res->next_mem) == res->next_mem);
116
    SET_SENTINEL(res);
117
118
    return res;
  }
119
120
}

121
122
/** Release <b>chunk</b> from a memarea, either by adding it to the freelist
 * or by freeing it if the freelist is already too big. */
123
static void
124
chunk_free_unchecked(memarea_chunk_t *chunk)
125
{
126
  CHECK_SENTINEL(chunk);
127
  if (freelist_len < MAX_FREELIST_LEN) {
128
129
130
    ++freelist_len;
    chunk->next_chunk = freelist;
    freelist = chunk;
131
    chunk->next_mem = chunk->u.mem;
132
133
134
135
136
137
  } else {
    tor_free(chunk);
  }
}

/** Allocate and return new memarea. */
138
memarea_t *
139
memarea_new(void)
140
141
{
  memarea_t *head = tor_malloc(sizeof(memarea_t));
142
  head->first = alloc_chunk(CHUNK_SIZE, 1);
143
144
145
146
147
148
149
150
151
152
153
  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;
154
    chunk_free_unchecked(chunk);
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
  }
  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;
170
      chunk_free_unchecked(chunk);
171
172
173
174
175
176
    }
    area->first->next_chunk = NULL;
  }
  area->first->next_mem = area->first->u.mem;
}

Nick Mathewson's avatar
Nick Mathewson committed
177
/** Remove all unused memarea chunks from the internal freelist. */
178
179
180
181
182
183
184
185
186
187
188
189
void
memarea_clear_freelist(void)
{
  memarea_chunk_t *chunk, *next;
  freelist_len = 0;
  for (chunk = freelist; chunk; chunk = next) {
    next = chunk->next_chunk;
    tor_free(chunk);
  }
  freelist = NULL;
}

190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
/** 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);
213
  CHECK_SENTINEL(chunk);
214
215
  if (sz == 0)
    sz = 1;
216
  if (chunk->next_mem+sz > chunk->u.mem+chunk->mem_size) {
217
    if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
218
219
      /* This allocation is too big.  Stick it in a special chunk, and put
       * that chunk second in the list. */
220
      memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE, 0);
221
222
223
224
      new_chunk->next_chunk = chunk->next_chunk;
      chunk->next_chunk = new_chunk;
      chunk = new_chunk;
    } else {
225
      memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE, 1);
226
227
228
229
230
231
      new_chunk->next_chunk = chunk;
      area->first = chunk = new_chunk;
    }
    tor_assert(chunk->mem_size >= sz);
  }
  result = chunk->next_mem;
232
  chunk->next_mem = chunk->next_mem + sz;
233
234
235
  // XXXX021 remove these once bug 930 is solved.
  tor_assert(chunk->next_mem >= chunk->u.mem);
  tor_assert(chunk->next_mem <= chunk->u.mem+chunk->mem_size);
236
  chunk->next_mem = realign_pointer(chunk->next_mem);
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
  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;
  char *result;
  const char *cp, *end = s+n;
272
  for (cp = s; cp < end && *cp; ++cp)
273
274
275
    ;
  /* cp now points to s+n, or to the 0 in the string. */
  ln = cp-s;
276
277
  result = memarea_alloc(area, ln+1);
  memcpy(result, s, ln);
278
279
280
281
  result[ln]='\0';
  return result;
}

282
283
284
285
286
287
288
289
/** 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) {
290
    CHECK_SENTINEL(chunk);
291
292
293
294
295
296
297
298
    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;
}

299
300
301
302
303
304
305
306
/** 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) {
307
    CHECK_SENTINEL(chunk);
308
    tor_assert(chunk->next_mem >= chunk->u.mem);
309
310
    tor_assert(chunk->next_mem <=
          (char*) realign_pointer(chunk->u.mem+chunk->mem_size));
311
312
  }
}
313