memarea.c 7.28 KB
Newer Older
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
/* Copyright (c) 2008, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/* $Id$ */

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

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

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

56
#define CHUNK_SIZE 4096
57

58
59
60
/** A memarea_t is an allocation region for a set of small memory requests
 * that will all be freed at once. */
struct memarea_t {
61
  memarea_chunk_t *first; /**< Top of the chunk stack: never NULL. */
62
63
};

64
65
66
67
#define MAX_FREELIST_LEN 4
int freelist_len=0;
static memarea_chunk_t *freelist = NULL;

68
69
/** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
static memarea_chunk_t *
70
alloc_chunk(size_t sz, int freelist_ok)
71
{
72
  if (freelist && freelist_ok) {
73
74
    memarea_chunk_t *res = freelist;
    freelist = res->next_chunk;
75
    res->next_chunk = NULL;
76
77
78
    --freelist_len;
    return res;
  } else {
79
    size_t chunk_size = freelist_ok ? CHUNK_SIZE : sz;
80
81
82
83
84
85
    memarea_chunk_t *res = tor_malloc_roundup(&chunk_size);
    res->next_chunk = NULL;
    res->mem_size = chunk_size - CHUNK_HEADER_SIZE;
    res->next_mem = res->u.mem;
    return res;
  }
86
87
}

88
89
90
static void
chunk_free(memarea_chunk_t *chunk)
{
91
  if (freelist_len < MAX_FREELIST_LEN) {
92
93
94
    ++freelist_len;
    chunk->next_chunk = freelist;
    freelist = chunk;
95
    chunk->next_mem = chunk->u.mem;
96
97
98
99
100
101
  } else {
    tor_free(chunk);
  }
}

/** Allocate and return new memarea. */
102
memarea_t *
103
memarea_new(void)
104
105
{
  memarea_t *head = tor_malloc(sizeof(memarea_t));
106
  head->first = alloc_chunk(CHUNK_SIZE, 1);
107
108
109
110
111
112
113
114
115
116
117
  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;
118
    chunk_free(chunk);
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
  }
  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;
134
      chunk_free(chunk);
135
136
137
138
139
140
    }
    area->first->next_chunk = NULL;
  }
  area->first->next_mem = area->first->u.mem;
}

Nick Mathewson's avatar
Nick Mathewson committed
141
/** Remove all unused memarea chunks from the internal freelist. */
142
143
144
145
146
147
148
149
150
151
152
153
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;
}

154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
/** 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);
  if (chunk->next_mem+sz > chunk->u.mem+chunk->mem_size) {
178
    if (sz+CHUNK_HEADER_SIZE >= CHUNK_SIZE) {
179
180
      /* This allocation is too big.  Stick it in a special chunk, and put
       * that chunk second in the list. */
181
      memarea_chunk_t *new_chunk = alloc_chunk(sz+CHUNK_HEADER_SIZE, 0);
182
183
184
185
      new_chunk->next_chunk = chunk->next_chunk;
      chunk->next_chunk = new_chunk;
      chunk = new_chunk;
    } else {
186
      memarea_chunk_t *new_chunk = alloc_chunk(CHUNK_SIZE, 1);
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
      new_chunk->next_chunk = chunk;
      area->first = chunk = new_chunk;
    }
    tor_assert(chunk->mem_size >= sz);
  }
  result = chunk->next_mem;
  chunk->next_mem = realign_pointer(chunk->next_mem + sz);
  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;
  for (cp = s; *cp && cp < end; ++cp)
    ;
  /* cp now points to s+n, or to the 0 in the string. */
  ln = cp-s;
  result = memarea_memdup(area, s, ln+1);
  result[ln]='\0';
  return result;
}

238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
/** 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) {
    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;
}

254
255
256
257
258
259
260
261
262
263
264
265
/** 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) {
    tor_assert(chunk->next_mem >= chunk->u.mem);
    tor_assert(chunk->next_mem <= chunk->u.mem+chunk->mem_size+MEMAREA_ALIGN);
  }
}
266