1 /* -----------------------------------------------------------------------------
3 * (c) The GHC Team 1998-1999
5 * MegaBlock Allocator Interface. This file contains all the dirty
6 * architecture-dependent hackery required to get a chunk of aligned
7 * memory from the operating system.
9 * ---------------------------------------------------------------------------*/
11 /* This is non-posix compliant. */
12 /* #include "PosixSource.h" */
18 #include "BlockAlloc.h"
30 #ifdef HAVE_SYS_TYPES_H
31 #include <sys/types.h>
33 #ifndef mingw32_HOST_OS
34 # ifdef HAVE_SYS_MMAN_H
35 # include <sys/mman.h>
45 #include <mach/vm_map.h>
50 lnat mblocks_allocated = 0;
52 /* -----------------------------------------------------------------------------
53 The MBlock Map: provides our implementation of HEAP_ALLOCED()
54 -------------------------------------------------------------------------- */
56 #if SIZEOF_VOID_P == 4
57 StgWord8 mblock_map[MBLOCK_MAP_SIZE]; // initially all zeros
58 #elif SIZEOF_VOID_P == 8
59 static MBlockMap dummy_mblock_map;
60 MBlockMap *mblock_cache = &dummy_mblock_map;
61 int mblock_map_count = 0;
62 MBlockMap **mblock_maps = NULL;
65 findMBlockMap(void *p)
68 StgWord32 hi = (StgWord32) (((StgWord)p) >> 32);
69 for( i = 0; i < mblock_map_count; i++ )
71 if(mblock_maps[i]->addrHigh32 == hi)
73 return mblock_maps[i];
80 slowIsHeapAlloced(void *p)
82 MBlockMap *map = findMBlockMap(p);
86 return map->mblocks[MBLOCK_MAP_ENTRY(p)];
94 markHeapAlloced(void *p)
96 #if SIZEOF_VOID_P == 4
97 mblock_map[MBLOCK_MAP_ENTRY(p)] = 1;
98 #elif SIZEOF_VOID_P == 8
99 MBlockMap *map = findMBlockMap(p);
103 mblock_maps = realloc(mblock_maps,
104 sizeof(MBlockMap*) * mblock_map_count);
105 map = mblock_maps[mblock_map_count-1] = calloc(1,sizeof(MBlockMap));
106 map->addrHigh32 = (StgWord32) (((StgWord)p) >> 32);
108 map->mblocks[MBLOCK_MAP_ENTRY(p)] = 1;
113 /* -----------------------------------------------------------------------------
114 Allocate new mblock(s)
115 -------------------------------------------------------------------------- */
120 return getMBlocks(1);
123 /* -----------------------------------------------------------------------------
126 On Unix-like systems, we use mmap() to allocate our memory. We
127 want memory in chunks of MBLOCK_SIZE, and aligned on an MBLOCK_SIZE
128 boundary. The mmap() interface doesn't give us this level of
129 control, so we have to use some heuristics.
131 In the general case, if we want a block of n megablocks, then we
132 allocate n+1 and trim off the slop from either side (using
133 munmap()) to get an aligned chunk of size n. However, the next
134 time we'll try to allocate directly after the previously allocated
135 chunk, on the grounds that this is aligned and likely to be free.
136 If it turns out that we were wrong, we have to munmap() and try
137 again using the general method.
139 Note on posix_memalign(): this interface is available on recent
140 systems and appears to provide exactly what we want. However, it
141 turns out not to be as good as our mmap() implementation, because
142 it wastes extra space (using double the address space, in a test on
143 x86_64/Linux). The problem seems to be that posix_memalign()
144 returns memory that can be free()'d, so the library must store
145 extra information along with the allocated block, thus messing up
146 the alignment. Hence, we don't use posix_memalign() for now.
148 -------------------------------------------------------------------------- */
150 #if !defined(mingw32_HOST_OS) && !defined(cygwin32_HOST_OS)
152 // A wrapper around mmap(), to abstract away from OS differences in
153 // the mmap() interface.
156 my_mmap (void *addr, lnat size)
160 #if defined(solaris2_HOST_OS) || defined(irix_HOST_OS)
162 int fd = open("/dev/zero",O_RDONLY);
163 ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
167 ret = mmap(addr, size, PROT_READ | PROT_WRITE,
168 MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
170 // Without MAP_FIXED, Apple's mmap ignores addr.
171 // With MAP_FIXED, it overwrites already mapped regions, whic
172 // mmap(0, ... MAP_FIXED ...) is worst of all: It unmaps the program text
173 // and replaces it with zeroes, causing instant death.
174 // This behaviour seems to be conformant with IEEE Std 1003.1-2001.
175 // Let's just use the underlying Mach Microkernel calls directly,
176 // they're much nicer.
180 if(addr) // try to allocate at adress
181 err = vm_allocate(mach_task_self(),(vm_address_t*) &ret, size, FALSE);
182 if(!addr || err) // try to allocate anywhere
183 err = vm_allocate(mach_task_self(),(vm_address_t*) &ret, size, TRUE);
186 // don't know what the error codes mean exactly, assume it's
187 // not our problem though.
188 errorBelch("memory allocation failed (requested %lu bytes)", size);
189 stg_exit(EXIT_FAILURE);
191 vm_protect(mach_task_self(),ret,size,FALSE,VM_PROT_READ|VM_PROT_WRITE);
194 ret = mmap(addr, size, PROT_READ | PROT_WRITE | PROT_EXEC,
195 MAP_ANON | MAP_PRIVATE, -1, 0);
198 if (ret == (void *)-1) {
199 if (errno == ENOMEM ||
200 (errno == EINVAL && sizeof(void*)==4 && size >= 0xc0000000)) {
201 // If we request more than 3Gig, then we get EINVAL
202 // instead of ENOMEM (at least on Linux).
203 errorBelch("out of memory (requested %lu bytes)", size);
204 stg_exit(EXIT_FAILURE);
206 barf("getMBlock: mmap: %s", strerror(errno));
213 // Implements the general case: allocate a chunk of memory of 'size'
217 gen_map_mblocks (lnat size)
222 // Try to map a larger block, and take the aligned portion from
223 // it (unmap the rest).
225 ret = my_mmap(0, size);
227 // unmap the slop bits around the chunk we allocated
228 slop = (W_)ret & MBLOCK_MASK;
230 if (munmap(ret, MBLOCK_SIZE - slop) == -1) {
231 barf("gen_map_mblocks: munmap failed");
233 if (slop > 0 && munmap(ret+size-slop, slop) == -1) {
234 barf("gen_map_mblocks: munmap failed");
237 // ToDo: if we happened to get an aligned block, then don't
238 // unmap the excess, just use it. For this to work, you
239 // need to keep in mind the following:
240 // * Calling my_mmap() with an 'addr' arg pointing to
241 // already my_mmap()ed space is OK and won't fail.
242 // * If my_mmap() can't satisfy the request at the
243 // given 'next_request' address in getMBlocks(), that
244 // you unmap the extra mblock mmap()ed here (or simply
245 // satisfy yourself that the slop introduced isn't worth
249 // next time, try after the block we just got.
250 ret += MBLOCK_SIZE - slop;
255 // The external interface: allocate 'n' mblocks, and return the
261 static caddr_t next_request = (caddr_t)HEAP_BASE;
263 lnat size = MBLOCK_SIZE * n;
266 if (next_request == 0) {
267 // use gen_map_mblocks the first time.
268 ret = gen_map_mblocks(size);
270 ret = my_mmap(next_request, size);
272 if (((W_)ret & MBLOCK_MASK) != 0) {
274 #if 0 // defined(DEBUG)
275 errorBelch("warning: getMBlock: misaligned block %p returned when allocating %d megablock(s) at %p", ret, n, next_request);
278 // unmap this block...
279 if (munmap(ret, size) == -1) {
280 barf("getMBlock: munmap failed");
282 // and do it the hard way
283 ret = gen_map_mblocks(size);
287 // Next time, we'll try to allocate right after the block we just got.
288 // ToDo: check that we haven't already grabbed the memory at next_request
289 next_request = ret + size;
291 debugTrace(DEBUG_gc, "allocated %d megablock(s) at %p",n,ret);
294 for (i = 0; i < n; i++) {
295 markHeapAlloced( ret + i * MBLOCK_SIZE );
298 mblocks_allocated += n;
306 /* XXX Do something here */
309 #else /* defined(mingw32_HOST_OS) || defined(cygwin32_HOST_OS) */
311 /* alloc_rec keeps the info we need to have matching VirtualAlloc and
314 typedef struct alloc_rec_ {
315 char* base; /* non-aligned base address, directly from VirtualAlloc */
316 int size; /* Size in bytes */
317 struct alloc_rec_* next;
320 typedef struct block_rec_ {
321 char* base; /* base address, non-MBLOCK-aligned */
322 int size; /* size in bytes */
323 struct block_rec_* next;
326 static alloc_rec* allocs = 0;
327 static block_rec* free_blocks = 0;
332 alloc_rec* rec = (alloc_rec*)malloc(sizeof(alloc_rec));
333 rec->size = (n+1)*MBLOCK_SIZE;
335 VirtualAlloc(NULL, rec->size, MEM_RESERVE, PAGE_READWRITE);
340 "getMBlocks: VirtualAlloc MEM_RESERVE %d blocks failed with: %ld\n"
341 , n, GetLastError());
347 alloc_rec* it=allocs;
348 for(; it->next!=0 && it->next->base<rec->base; it=it->next) ;
352 debugTrace(DEBUG_gc, "allocated %d megablock(s) at 0x%x",n,(nat)rec->base);
359 insertFree(char* alloc_base, int alloc_size) {
361 temp.base=0; temp.size=0; temp.next=free_blocks;
363 block_rec* it = free_blocks;
364 block_rec* prev = &temp;
365 for( ; it!=0 && it->base<alloc_base; prev=it, it=it->next) ;
367 if(it!=0 && alloc_base+alloc_size == it->base) {
368 if(prev->base + prev->size == alloc_base) { /* Merge it, alloc, prev */
369 prev->size += alloc_size + it->size;
370 prev->next = it->next;
372 } else { /* Merge it, alloc */
373 it->base = alloc_base;
374 it->size += alloc_size;
376 } else if(prev->base + prev->size == alloc_base) { /* Merge alloc, prev */
377 prev->size += alloc_size;
378 } else { /* Merge none */
379 block_rec* rec = (block_rec*)malloc(sizeof(block_rec));
380 /* TODO: Check malloc failure */
381 rec->base=alloc_base;
382 rec->size=alloc_size;
386 free_blocks=temp.next;
391 findFreeBlocks(nat n) {
393 block_rec* it=free_blocks;
394 int required_size = n*MBLOCK_SIZE;
395 /* TODO: Don't just take first block, find smallest sufficient block */
397 temp.next=free_blocks; temp.base=0; temp.size=0;
398 block_rec* prev=&temp;
399 for( ; it!=0 && it->size<required_size; prev=it, it=it->next ) ;
401 if( (((unsigned long)it->base) & MBLOCK_MASK) == 0) { /* MBlock aligned */
402 ret = (void*)it->base;
403 if(it->size==required_size) {
407 it->base += required_size;
408 it->size -=required_size;
411 char* need_base = (char*)(((unsigned long)it->base) & ((unsigned long)~MBLOCK_MASK)) + MBLOCK_SIZE;
412 block_rec* next = (block_rec*)malloc(sizeof(block_rec));
413 /* TODO: Check malloc failure */
414 int new_size = need_base - it->base;
415 next->base = need_base +required_size;
416 next->size = it->size - (new_size+required_size);
418 next->next = it->next;
420 ret=(void*)need_base;
423 free_blocks=temp.next;
427 /* VirtualAlloc MEM_COMMIT can't cross boundaries of VirtualAlloc MEM_RESERVE,
428 so we might need to do many VirtualAlloc MEM_COMMITs. We simply walk the
429 (ordered) allocated blocks. */
431 commitBlocks(char* base, int size) {
432 alloc_rec* it=allocs;
433 for( ; it!=0 && (it->base+it->size)<base; it=it->next ) ;
434 for( ; it!=0 && size>0; it=it->next ) {
435 int size_delta = it->size - (base-it->base);
436 if(size_delta>size) size_delta=size;
437 void* temp = VirtualAlloc(base, size_delta, MEM_COMMIT, PAGE_READWRITE);
439 debugBelch("getMBlocks: VirtualAlloc MEM_COMMIT failed: %ld", GetLastError());
448 ret = findFreeBlocks(n);
450 alloc_rec* alloc = allocNew(n);
451 /* We already belch in allocNew if it fails */
453 insertFree(alloc->base, alloc->size);
454 ret = findFreeBlocks(n);
459 /* (In)sanity tests */
460 if (((W_)ret & MBLOCK_MASK) != 0) barf("getMBlocks: misaligned block returned");
462 commitBlocks(ret, MBLOCK_SIZE*n);
464 /* Global bookkeeping */
465 mblocks_allocated += n;
468 markHeapAlloced( ret + i * MBLOCK_SIZE );
479 block_rec* it = free_blocks;
481 if(!VirtualFree((void*)it->base, it->size, MEM_DECOMMIT))
482 debugBelch("freeAllMBlocks: VirtualFree MEM_DECOMMIT failed with %ld", GetLastError());
490 alloc_rec* it = allocs;
492 if(!VirtualFree((void*)it->base, 0, MEM_RELEASE))
493 debugBelch("freeAllMBlocks: VirtualFree MEM_RELEASE failed with %ld", GetLastError());