/* malloc2.c (emx+gcc) -- Copyright (c) 1990-1996 by Eberhard Mattes */ #include /* For and */ #include /* For */ #include #include #include #include "malloc1.h" #define CHUNK_SIZE 65536 /* To do: take size of last free block into account, if no used block follows and if sbrk() must be called. */ /* Bug: sbrk/brk must not be called by user program to change data segment size (very complicated to fix). malloc returns NULL if it thinks the data segment size has been changed. */ #ifdef __MT__ static _rmutex _heap_rmutex; #endif mheader_t *_malloc_rover = NULL; mheader_t *_malloc_bottom = NULL; mheader_t *_malloc_top = NULL; int _emx_malloc_init (void) { maddr_t n; void *p; int result; #ifdef __MT__ static _smutex lock; #endif /* This is an attempt at provoking a linker error if malloc() has been replaced and -ltmalloc has been forgotten. By referencing the _emx_malloc_magic() function, we force in the module compiled from malloc.c. That will hopefully conflict with the replacement malloc(). */ _emx_malloc_magic (); #ifdef __MT__ _smutex_request (&lock); #endif if (_malloc_rover != NULL) result = TRUE; else { #ifdef __MT__ _rmutex_checked_create (&_heap_rmutex, 0); #endif n = ADDR (_sbrk (0)); if ((n & (ALIGNMENT-1)) != 0) _sbrk (ALIGNMENT - (n & (ALIGNMENT-1))); p = _sbrk (2 * MHEADER_SIZE); if (p == (void *)(-1) || (ADDR (p) & (ALIGNMENT-1)) != 0) result = FALSE; else { _malloc_bottom = _malloc_rover = p; _malloc_top = _malloc_bottom + 1; _malloc_bottom->size = 1; /* length = 0, free */ _malloc_top->size = END_OF_HEAP; /* End of heap */ result = TRUE; } } #ifdef __MT__ _smutex_release (&lock); #endif return result; } #ifdef __MT__ /* Lock the heap. */ void _heap_lock (void) { _rmutex_checked_request (&_heap_rmutex, _FMR_IGNINT); } /* Release the heap. */ void _heap_unlock (void) { _rmutex_checked_release (&_heap_rmutex); } #endif /* Pass 1: search from _malloc_rover to end of heap Pass 2: search from start of heap to _malloc_rover Pass 3: search from _malloc_rover to end of heap (after growing heap) If EXPAND_HEAP is non-zero, we are allowed to expand the heap. */ void *_malloc2 (size_t size, int expand_heap, int tile) { mheader_t *block, *base; void *p; msize_t len, n; maddr_t a; int pass; /* Sanity-check SIZE. Don't call sbrk() with negative argument */ if (size > MAX_SIZE) return NULL; /* Round up SIZE to a multiple of 4. */ size = ROUNDUP (size); pass = 1; /* Start new pass at _malloc_rover. */ restart: block = base = _malloc_rover; /* Skip blocks which are in use. Jump to free_start when we find a free block. */ in_use: if (block->size & MF_FREE) goto free_start; /* Same as in_use, but we already know that the current block is in use (speed hack). */ not_free: /* The second pass stops at _malloc_rover. */ if (pass == 2 && ADDR (block) > ADDR (_malloc_rover)) { block = _malloc_top; goto not_found; } /* Start next pass when reaching the end of the heap. */ if (block->size == END_OF_HEAP) { if (block != _malloc_top) return NULL; if (pass >= 2) goto not_found; ++pass; block = _malloc_bottom; goto in_use; } /* Move to the next block and repeat loop. */ block = MHEADER (ADDR (block) + MHEADER_SIZE + block->size); goto in_use; /* We found a free block. Now collapse successive free blocks until the block is big enough or there is not another adjacent free block. */ free_start: /* BASE points to the start of the free block we're examining. LEN is used to accumulate the length of successive free blocks. */ base = block; len = SIZE (base->size); /* If tiling is in effect, the block must not cross a 64K boundary. Compute N, the number of extra bytes required at the beginning of the block, based on the address of the current block, to align the data properly. */ n = 0; if (tile) { /* If the requested size is 64K or more or if the data crosses a 64K boundary, align the block to a 64K boundary. */ a = ADDR (base) + MHEADER_SIZE; if (((a + size) & 0xffff) < size) { n = a & 0xffff; if (n != 0) n = 0x10000 - n; } } free_loop: /* If the block is big enough, quit the loop and use the block. */ if (len >= size + n) goto found; /* Move to the next block. */ block = MHEADER (ADDR (base) + MHEADER_SIZE + len); /* If that block is in use, quit the loop and skip used blocks until another free block is found. */ if (!(block->size & MF_FREE)) goto not_free; /* Update LEN and collaps the current block and the new block into one free block, updating _malloc_rover if necessary. Then repeat the loop. */ len += MHEADER_SIZE + SIZE (block->size); if (_malloc_rover == block) _malloc_rover = base; base->size = len | MF_FREE; goto free_loop; /* A big enough block was found. Split it into up to three blocks, one of which will be marked used and returned to the caller. */ found: /* If alignment is required, create a free block of size n (including the header), then advance the pointer. This may create a block of size 0 (excluding the header). */ if (n != 0) { if ((n & MF_FLAGS) != 0) abort (); base->size = (n - MHEADER_SIZE) | MF_FREE; base = MHEADER (ADDR (base) + n); len -= n; } /* If there are more than 4 bytes left, create a free block after the block to be used. If there are 4 bytes left, we simply make the block 4 bytes too big. */ if (len - size > MHEADER_SIZE) { base->size = size; /* MF_FREE not set, ie, in use */ block = MHEADER (ADDR (base) + MHEADER_SIZE + size); block->size = (len - size - MHEADER_SIZE) | MF_FREE; } else base->size = len; /* in use! */ _malloc_rover = base; return (void *)(ADDR (base) + MHEADER_SIZE); not_found: if (!expand_heap) return NULL; if (tile) n = (size + 0x10000 + 0xfff) & ~0xfff; else { n = (size + MHEADER_SIZE + 0xfff) & ~0xfff; if (n < CHUNK_SIZE) n = CHUNK_SIZE; /* Memory is cheap, searching expensive */ } p = _sbrk (n); if (p == (void *)(-1)) return NULL; if (p != _malloc_top + 1) return NULL; _malloc_top->size = (n - MHEADER_SIZE) | MF_FREE; _malloc_top = MHEADER (ADDR (_malloc_top) + n); _malloc_top->size = END_OF_HEAP; pass = 3; _malloc_rover = base; goto restart; }