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);
added
removed
libatomic_ops-1.2/src/atomic_ops_malloc.c
