aboutsummaryrefslogtreecommitdiff
path: root/src/common/memarea.c
blob: 0ae0ccca1d0929c530257856214c1f674fd84417 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
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
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
/* Copyright (c) 2008-2013, 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 <stdlib.h>
#include "memarea.h"
#include "util.h"
#include "compat.h"
#include "torlog.h"

/** 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

#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

#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
#define SENTINEL_LEN 0
#define SET_SENTINEL(chunk) STMT_NIL
#define CHECK_SENTINEL(chunk) STMT_NIL
#endif

/** 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 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;

/** How many bytes are needed for overhead before we get to the memory part
 * of a chunk? */
#define CHUNK_HEADER_SIZE STRUCT_OFFSET(memarea_chunk_t, u)

/** 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. */
};

/** How many chunks will we put into the freelist before freeing them? */
#define MAX_FREELIST_LEN 4
/** 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. */
static memarea_chunk_t *freelist = NULL;

/** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
static memarea_chunk_t *
alloc_chunk(size_t sz, int freelist_ok)
{
  tor_assert(sz < SIZE_T_CEILING);
  if (freelist && freelist_ok) {
    memarea_chunk_t *res = freelist;
    freelist = res->next_chunk;
    res->next_chunk = NULL;
    --freelist_len;
    CHECK_SENTINEL(res);
    return res;
  } else {
    size_t chunk_size = freelist_ok ? 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, either by adding it to the freelist
 * or by freeing it if the freelist is already too big. */
static void
chunk_free_unchecked(memarea_chunk_t *chunk)
{
  CHECK_SENTINEL(chunk);
  if (freelist_len < MAX_FREELIST_LEN) {
    ++freelist_len;
    chunk->next_chunk = freelist;
    freelist = chunk;
    chunk->next_mem = chunk->u.mem;
  } else {
    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, 1);
  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;
    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;
      chunk_free_unchecked(chunk);
    }
    area->first->next_chunk = NULL;
  }
  area->first->next_mem = area->first->u.mem;
}

/** Remove all unused memarea chunks from the internal freelist. */
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;
}

/** 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;
  if (chunk->next_mem+sz > chunk->u.mem+chunk->mem_size) {
    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, 0);
      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, 1);
      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;
  char *result;
  const char *cp, *end = s+n;
  tor_assert(n < SIZE_T_CEILING);
  for (cp = s; cp < end && *cp; ++cp)
    ;
  /* cp now points to s+n, or to the 0 in the string. */
  ln = cp-s;
  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));
  }
}