2 * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
3 * Original Author: Hans Boehm
5 * This file may be redistributed and/or modified under the
6 * terms of the GNU General Public License as published by the Free Software
7 * Foundation; either version 2, or (at your option) any later version.
9 * It is distributed in the hope that it will be useful, but WITHOUT ANY
10 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11 * FOR A PARTICULAR PURPOSE. See the GNU General Public License in the
12 * file doc/COPYING for more details.
15 #if defined(HAVE_CONFIG_H)
19 #define AO_REQUIRE_CAS
20 #include "atomic_ops_stack.h"
21 #include <string.h> /* for ffs, which is assumed reentrant. */
23 #ifdef AO_TRACE_MALLOC
29 * We round up each allocation request to the next power of two
31 * We keep one stack of free objects for each size. Each object
32 * has an initial word (offset -sizeof(AO_t) from the visible pointer)
33 * which contains either
34 * The binary log of the object size in bytes (small objects)
35 * The object size (a multiple of CHUNK_SIZE) for large objects.
36 * The second case only arises if mmap-based allocation is supported.
37 * We align the user-visible part of each object on a GRANULARITY
38 * byte boundary. That means that the actual (hidden) start of
39 * the object starts a word before this boundary.
43 # define LOG_MAX_SIZE 16
44 /* We assume that 2**LOG_MAX_SIZE is a multiple of page size. */
49 /* Assumed to be at least sizeof(AO_t). */
52 #define CHUNK_SIZE (1 << LOG_MAX_SIZE)
54 #ifndef AO_INITIAL_HEAP_SIZE
55 # define AO_INITIAL_HEAP_SIZE (2*(LOG_MAX_SIZE+1)*CHUNK_SIZE)
58 char AO_initial_heap[AO_INITIAL_HEAP_SIZE];
60 static volatile AO_t initial_heap_ptr = (AO_t)AO_initial_heap;
61 static volatile char *initial_heap_lim = AO_initial_heap + AO_INITIAL_HEAP_SIZE;
63 #if defined(HAVE_MMAP)
65 #include <sys/types.h>
70 static volatile AO_t mmap_enabled = 0;
73 AO_malloc_enable_mmap(void)
75 AO_store(&mmap_enabled, 1);
78 static char *get_mmaped(size_t sz)
82 assert(!(sz & (CHUNK_SIZE - 1)));
83 if (!mmap_enabled) return 0;
84 # if defined(MAP_ANONYMOUS)
85 result = mmap(0, sz, PROT_READ | PROT_WRITE,
86 MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
87 # elif defined(MAP_ANON)
88 result = mmap(0, sz, PROT_READ | PROT_WRITE,
89 MAP_PRIVATE | MAP_ANON, -1, 0);
92 int zero_fd = open("/dev/zero", O_RDONLY);
93 result = mmap(0, sz, PROT_READ | PROT_WRITE,
94 MAP_PRIVATE, zero_fd, 0);
98 if (result == MAP_FAILED) result = 0;
102 /* Allocate an object of size (incl. header) of size > CHUNK_SIZE. */
103 /* sz includes space for an AO_t-sized header. */
105 AO_malloc_large(size_t sz)
108 /* The header will force us to waste ALIGNMENT bytes, incl. header. */
110 /* Round to multiple of CHUNK_SIZE. */
111 sz = (sz + CHUNK_SIZE - 1) & ~(CHUNK_SIZE - 1);
112 result = get_mmaped(sz);
113 if (result == 0) return 0;
115 ((AO_t *)result)[-1] = (AO_t)sz;
120 AO_free_large(char * p)
122 AO_t sz = ((AO_t *)p)[-1];
123 if (munmap(p - ALIGNMENT, (size_t)sz) != 0)
124 abort(); /* Programmer error. Not really async-signal-safe, but ... */
131 AO_malloc_enable_mmap(void)
135 static char *get_mmaped(size_t sz)
141 AO_malloc_large(size_t sz)
147 AO_free_large(char * p)
149 abort(); /* Programmer error. Not really async-signal-safe, but ... */
162 initial_ptr = (char *)AO_load(&initial_heap_ptr);
163 my_chunk_ptr = (char *)(((AO_t)initial_ptr + (ALIGNMENT - 1))
165 if (initial_ptr != my_chunk_ptr)
167 /* Align correctly. If this fails, someone else did it for us. */
168 AO_compare_and_swap_acquire(&initial_heap_ptr, (AO_t)initial_ptr,
171 my_lim = my_chunk_ptr + CHUNK_SIZE;
172 if (my_lim <= initial_heap_lim)
174 if (!AO_compare_and_swap(&initial_heap_ptr, (AO_t)my_chunk_ptr,
179 /* We failed. The initial heap is used up. */
180 my_chunk_ptr = get_mmaped(CHUNK_SIZE);
181 assert (!((AO_t)my_chunk_ptr & (ALIGNMENT-1)));
185 /* Object free lists. Ith entry corresponds to objects */
186 /* of total size 2**i bytes. */
187 AO_stack_t AO_free_list[LOG_MAX_SIZE+1];
189 /* Chunk free list, linked through first word in chunks. */
190 /* All entries of size CHUNK_SIZE. */
191 AO_stack_t AO_chunk_free_list;
193 /* Break up the chunk, and add it to the object free list for */
194 /* the given size. Sz must be a power of two. */
195 /* We have exclusive access to chunk. */
197 add_chunk_as(void * chunk, size_t sz, unsigned log_sz)
199 char *first = (char *)chunk + ALIGNMENT - sizeof(AO_t);
200 char *limit = (char *)chunk + CHUNK_SIZE - sz;
203 for (p = first; p <= limit; p = next) {
205 AO_stack_push(AO_free_list+log_sz, (AO_t *)p);
209 static int msbs[16] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
211 /* Return the position of the most significant set bit in the */
213 /* We follow the conventions of ffs(), i.e. the least */
214 /* significant bit is number one. */
218 if ((s & 0xff) != s) {
219 /* The following shift often generates warnings on 32-bit arch's */
220 /* That's OK, because it will never be executed there. */
221 if (sizeof(size_t) > 4 && (s >> 32) != 0)
250 size_t adj_sz = sz + sizeof(AO_t);
253 return AO_malloc_large(sz);
254 log_sz = msb(adj_sz-1);
255 result = AO_stack_pop(AO_free_list+log_sz);
256 while (0 == result) {
257 void * chunk = get_chunk();
258 if (0 == chunk) return 0;
259 adj_sz = 1 << log_sz;
260 add_chunk_as(chunk, adj_sz, log_sz);
261 result = AO_stack_pop(AO_free_list+log_sz);
264 # ifdef AO_TRACE_MALLOC
265 fprintf(stderr, "%x: AO_malloc(%lu) = %p\n",
266 (int)pthread_self(), (unsigned long)sz, result+1);
274 char *base = (char *)p - sizeof(AO_t);
278 log_sz = *(AO_t *)base;
279 # ifdef AO_TRACE_MALLOC
280 fprintf(stderr, "%x: AO_free(%p sz:%lu)\n", (int)pthread_self(), p,
282 (log_sz > LOG_MAX_SIZE? log_sz : (1 << log_sz)));
284 if (log_sz > LOG_MAX_SIZE)
287 AO_stack_push(AO_free_list+log_sz, (AO_t *)base);