1 /* Copyright (c) 2008-2013, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
5 * \brief Implementation for memarea_t, an allocator for allocating lots of
6 * small objects that will be freed all at once.
16 /** If true, we try to detect any attempts to write beyond the length of a
20 /** All returned pointers should be aligned to the nearest multiple of this
22 #define MEMAREA_ALIGN SIZEOF_VOID_P
24 #if MEMAREA_ALIGN == 4
25 #define MEMAREA_ALIGN_MASK 3lu
26 #elif MEMAREA_ALIGN == 8
27 #define MEMAREA_ALIGN_MASK 7lu
29 #error "void* is neither 4 nor 8 bytes long. I don't know how to align stuff."
32 #if defined(__GNUC__) && defined(FLEXIBLE_ARRAY_MEMBER)
33 #define USE_ALIGNED_ATTRIBUTE
40 /** Magic value that we stick at the end of a memarea so we can make sure
41 * there are no run-off-the-end bugs. */
42 #define SENTINEL_VAL 0x90806622u
43 /** How many bytes per area do we devote to the sentinel? */
44 #define SENTINEL_LEN sizeof(uint32_t)
45 /** Given a mem_area_chunk_t with SENTINEL_LEN extra bytes allocated at the
46 * end, set those bytes. */
47 #define SET_SENTINEL(chunk) \
49 set_uint32( &(chunk)->U_MEM[chunk->mem_size], SENTINEL_VAL ); \
51 /** Assert that the sentinel on a memarea is set correctly. */
52 #define CHECK_SENTINEL(chunk) \
54 uint32_t sent_val = get_uint32(&(chunk)->U_MEM[chunk->mem_size]); \
55 tor_assert(sent_val == SENTINEL_VAL); \
58 #define SENTINEL_LEN 0
59 #define SET_SENTINEL(chunk) STMT_NIL
60 #define CHECK_SENTINEL(chunk) STMT_NIL
63 /** Increment <b>ptr</b> until it is aligned to MEMAREA_ALIGN. */
65 realign_pointer(void *ptr
)
67 uintptr_t x
= (uintptr_t)ptr
;
68 x
= (x
+MEMAREA_ALIGN_MASK
) & ~MEMAREA_ALIGN_MASK
;
69 /* Reinstate this if bug 930 ever reappears
70 tor_assert(((void*)x) >= ptr);
75 /** Implements part of a memarea. New memory is carved off from chunk->mem in
76 * increasing order until a request is too big, at which point a new chunk is
78 typedef struct memarea_chunk_t
{
79 /** Next chunk in this area. Only kept around so we can free it. */
80 struct memarea_chunk_t
*next_chunk
;
81 size_t mem_size
; /**< How much RAM is available in mem, total? */
82 char *next_mem
; /**< Next position in mem to allocate data at. If it's
83 * greater than or equal to mem+mem_size, this chunk is
85 #ifdef USE_ALIGNED_ATTRIBUTE
86 char mem
[FLEXIBLE_ARRAY_MEMBER
] __attribute__((aligned(MEMAREA_ALIGN
)));
89 char mem
[1]; /**< Memory space in this chunk. */
90 void *void_for_alignment_
; /**< Dummy; used to make sure mem is aligned. */
95 /** How many bytes are needed for overhead before we get to the memory part
97 #define CHUNK_HEADER_SIZE STRUCT_OFFSET(memarea_chunk_t, U_MEM)
99 /** What's the smallest that we'll allocate a chunk? */
100 #define CHUNK_SIZE 4096
102 /** A memarea_t is an allocation region for a set of small memory requests
103 * that will all be freed at once. */
105 memarea_chunk_t
*first
; /**< Top of the chunk stack: never NULL. */
108 /** How many chunks will we put into the freelist before freeing them? */
109 #define MAX_FREELIST_LEN 4
110 /** The number of memarea chunks currently in our freelist. */
111 static int freelist_len
=0;
112 /** A linked list of unused memory area chunks. Used to prevent us from
113 * spinning in malloc/free loops. */
114 static memarea_chunk_t
*freelist
= NULL
;
116 /** Helper: allocate a new memarea chunk of around <b>chunk_size</b> bytes. */
117 static memarea_chunk_t
*
118 alloc_chunk(size_t sz
, int freelist_ok
)
120 tor_assert(sz
< SIZE_T_CEILING
);
121 if (freelist
&& freelist_ok
) {
122 memarea_chunk_t
*res
= freelist
;
123 freelist
= res
->next_chunk
;
124 res
->next_chunk
= NULL
;
129 size_t chunk_size
= freelist_ok
? CHUNK_SIZE
: sz
;
130 memarea_chunk_t
*res
;
131 chunk_size
+= SENTINEL_LEN
;
132 res
= tor_malloc(chunk_size
);
133 res
->next_chunk
= NULL
;
134 res
->mem_size
= chunk_size
- CHUNK_HEADER_SIZE
- SENTINEL_LEN
;
135 res
->next_mem
= res
->U_MEM
;
136 tor_assert(res
->next_mem
+res
->mem_size
+SENTINEL_LEN
==
137 ((char*)res
)+chunk_size
);
138 tor_assert(realign_pointer(res
->next_mem
) == res
->next_mem
);
144 /** Release <b>chunk</b> from a memarea, either by adding it to the freelist
145 * or by freeing it if the freelist is already too big. */
147 chunk_free_unchecked(memarea_chunk_t
*chunk
)
149 CHECK_SENTINEL(chunk
);
150 if (freelist_len
< MAX_FREELIST_LEN
) {
152 chunk
->next_chunk
= freelist
;
154 chunk
->next_mem
= chunk
->U_MEM
;
160 /** Allocate and return new memarea. */
164 memarea_t
*head
= tor_malloc(sizeof(memarea_t
));
165 head
->first
= alloc_chunk(CHUNK_SIZE
, 1);
169 /** Free <b>area</b>, invalidating all pointers returned from memarea_alloc()
170 * and friends for this area */
172 memarea_drop_all(memarea_t
*area
)
174 memarea_chunk_t
*chunk
, *next
;
175 for (chunk
= area
->first
; chunk
; chunk
= next
) {
176 next
= chunk
->next_chunk
;
177 chunk_free_unchecked(chunk
);
179 area
->first
= NULL
; /*fail fast on */
183 /** Forget about having allocated anything in <b>area</b>, and free some of
184 * the backing storage associated with it, as appropriate. Invalidates all
185 * pointers returned from memarea_alloc() for this area. */
187 memarea_clear(memarea_t
*area
)
189 memarea_chunk_t
*chunk
, *next
;
190 if (area
->first
->next_chunk
) {
191 for (chunk
= area
->first
->next_chunk
; chunk
; chunk
= next
) {
192 next
= chunk
->next_chunk
;
193 chunk_free_unchecked(chunk
);
195 area
->first
->next_chunk
= NULL
;
197 area
->first
->next_mem
= area
->first
->U_MEM
;
200 /** Remove all unused memarea chunks from the internal freelist. */
202 memarea_clear_freelist(void)
204 memarea_chunk_t
*chunk
, *next
;
206 for (chunk
= freelist
; chunk
; chunk
= next
) {
207 next
= chunk
->next_chunk
;
213 /** Return true iff <b>p</b> is in a range that has been returned by an
214 * allocation from <b>area</b>. */
216 memarea_owns_ptr(const memarea_t
*area
, const void *p
)
218 memarea_chunk_t
*chunk
;
220 for (chunk
= area
->first
; chunk
; chunk
= chunk
->next_chunk
) {
221 if (ptr
>= chunk
->U_MEM
&& ptr
< chunk
->next_mem
)
227 /** Return a pointer to a chunk of memory in <b>area</b> of at least <b>sz</b>
228 * bytes. <b>sz</b> should be significantly smaller than the area's chunk
229 * size, though we can deal if it isn't. */
231 memarea_alloc(memarea_t
*area
, size_t sz
)
233 memarea_chunk_t
*chunk
= area
->first
;
236 CHECK_SENTINEL(chunk
);
237 tor_assert(sz
< SIZE_T_CEILING
);
240 if (chunk
->next_mem
+sz
> chunk
->U_MEM
+chunk
->mem_size
) {
241 if (sz
+CHUNK_HEADER_SIZE
>= CHUNK_SIZE
) {
242 /* This allocation is too big. Stick it in a special chunk, and put
243 * that chunk second in the list. */
244 memarea_chunk_t
*new_chunk
= alloc_chunk(sz
+CHUNK_HEADER_SIZE
, 0);
245 new_chunk
->next_chunk
= chunk
->next_chunk
;
246 chunk
->next_chunk
= new_chunk
;
249 memarea_chunk_t
*new_chunk
= alloc_chunk(CHUNK_SIZE
, 1);
250 new_chunk
->next_chunk
= chunk
;
251 area
->first
= chunk
= new_chunk
;
253 tor_assert(chunk
->mem_size
>= sz
);
255 result
= chunk
->next_mem
;
256 chunk
->next_mem
= chunk
->next_mem
+ sz
;
257 /* Reinstate these if bug 930 ever comes back
258 tor_assert(chunk->next_mem >= chunk->U_MEM);
259 tor_assert(chunk->next_mem <= chunk->U_MEM+chunk->mem_size);
261 chunk
->next_mem
= realign_pointer(chunk
->next_mem
);
265 /** As memarea_alloc(), but clears the memory it returns. */
267 memarea_alloc_zero(memarea_t
*area
, size_t sz
)
269 void *result
= memarea_alloc(area
, sz
);
270 memset(result
, 0, sz
);
274 /** As memdup, but returns the memory from <b>area</b>. */
276 memarea_memdup(memarea_t
*area
, const void *s
, size_t n
)
278 char *result
= memarea_alloc(area
, n
);
279 memcpy(result
, s
, n
);
283 /** As strdup, but returns the memory from <b>area</b>. */
285 memarea_strdup(memarea_t
*area
, const char *s
)
287 return memarea_memdup(area
, s
, strlen(s
)+1);
290 /** As strndup, but returns the memory from <b>area</b>. */
292 memarea_strndup(memarea_t
*area
, const char *s
, size_t n
)
296 tor_assert(n
< SIZE_T_CEILING
);
297 for (ln
= 0; ln
< n
&& s
[ln
]; ++ln
)
299 result
= memarea_alloc(area
, ln
+1);
300 memcpy(result
, s
, ln
);
305 /** Set <b>allocated_out</b> to the number of bytes allocated in <b>area</b>,
306 * and <b>used_out</b> to the number of bytes currently used. */
308 memarea_get_stats(memarea_t
*area
, size_t *allocated_out
, size_t *used_out
)
311 memarea_chunk_t
*chunk
;
312 for (chunk
= area
->first
; chunk
; chunk
= chunk
->next_chunk
) {
313 CHECK_SENTINEL(chunk
);
314 a
+= CHUNK_HEADER_SIZE
+ chunk
->mem_size
;
315 tor_assert(chunk
->next_mem
>= chunk
->U_MEM
);
316 u
+= CHUNK_HEADER_SIZE
+ (chunk
->next_mem
- chunk
->U_MEM
);
322 /** Assert that <b>area</b> is okay. */
324 memarea_assert_ok(memarea_t
*area
)
326 memarea_chunk_t
*chunk
;
327 tor_assert(area
->first
);
329 for (chunk
= area
->first
; chunk
; chunk
= chunk
->next_chunk
) {
330 CHECK_SENTINEL(chunk
);
331 tor_assert(chunk
->next_mem
>= chunk
->U_MEM
);
332 tor_assert(chunk
->next_mem
<=
333 (char*) realign_pointer(chunk
->U_MEM
+chunk
->mem_size
));