URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [tags/] [gnu-src/] [newlib-1.18.0/] [newlib-1.18.0-or32-1.0rc2/] [newlib/] [libc/] [machine/] [xstormy16/] [tiny-malloc.c] - Rev 520
Compare with Previous | Blame | View Log
/* A replacement malloc with: - Much reduced code size; - Smaller RAM footprint; - The ability to handle downward-growing heaps; but - Slower; - Probably higher memory fragmentation; - Doesn't support threads (but, if it did support threads, it wouldn't need a global lock, only a compare-and-swap instruction); - Assumes the maximum alignment required is the alignment of a pointer; - Assumes that memory is already there and doesn't need to be allocated. * Synopsis of public routines malloc(size_t n); Return a pointer to a newly allocated chunk of at least n bytes, or null if no space is available. free(void* p); Release the chunk of memory pointed to by p, or no effect if p is null. realloc(void* p, size_t n); Return a pointer to a chunk of size n that contains the same data as does chunk p up to the minimum of (n, p's size) bytes, or null if no space is available. The returned pointer may or may not be the same as p. If p is null, equivalent to malloc. Unless the #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a size argument of zero (re)allocates a minimum-sized chunk. memalign(size_t alignment, size_t n); Return a pointer to a newly allocated chunk of n bytes, aligned in accord with the alignment argument, which must be a power of two. Will fail if 'alignment' is too large. calloc(size_t unit, size_t quantity); Returns a pointer to quantity * unit bytes, with all locations set to zero. cfree(void* p); Equivalent to free(p). malloc_trim(size_t pad); Release all but pad bytes of freed top-most memory back to the system. Return 1 if successful, else 0. malloc_usable_size(void* p); Report the number usable allocated bytes associated with allocated chunk p. This may or may not report more bytes than were requested, due to alignment and minimum size constraints. malloc_stats(); Prints brief summary statistics on stderr. mallinfo() Returns (by copy) a struct containing various summary statistics. mallopt(int parameter_number, int parameter_value) Changes one of the tunable parameters described below. Returns 1 if successful in changing the parameter, else 0. Actually, returns 0 always, as no parameter can be changed. */ #ifdef __xstormy16__ #define MALLOC_DIRECTION -1 #endif #ifndef MALLOC_DIRECTION #define MALLOC_DIRECTION 1 #endif #include <stddef.h> void* malloc(size_t); void free(void*); void* realloc(void*, size_t); void* memalign(size_t, size_t); void* valloc(size_t); void* pvalloc(size_t); void* calloc(size_t, size_t); void cfree(void*); int malloc_trim(size_t); size_t malloc_usable_size(void*); void malloc_stats(void); int mallopt(int, int); struct mallinfo mallinfo(void); typedef struct freelist_entry { size_t size; struct freelist_entry *next; } *fle; extern void * __malloc_end; extern fle __malloc_freelist; /* Return the number of bytes that need to be added to X to make it aligned to an ALIGN boundary. ALIGN must be a power of 2. */ #define M_ALIGN(x, align) (-(size_t)(x) & ((align) - 1)) /* Return the number of bytes that need to be subtracted from X to make it aligned to an ALIGN boundary. ALIGN must be a power of 2. */ #define M_ALIGN_SUB(x, align) ((size_t)(x) & ((align) - 1)) extern void __malloc_start; /* This is the minimum gap allowed between __malloc_end and the top of the stack. This is only checked for when __malloc_end is decreased; if instead the stack grows into the heap, silent data corruption will result. */ #define MALLOC_MINIMUM_GAP 32 #ifdef __xstormy16__ register void * stack_pointer asm ("r15"); #define MALLOC_LIMIT stack_pointer #else #define MALLOC_LIMIT __builtin_frame_address (0) #endif #if MALLOC_DIRECTION < 0 #define CAN_ALLOC_P(required) \ (((size_t) __malloc_end - (size_t)MALLOC_LIMIT \ - MALLOC_MINIMUM_GAP) >= (required)) #else #define CAN_ALLOC_P(required) \ (((size_t)MALLOC_LIMIT - (size_t) __malloc_end \ - MALLOC_MINIMUM_GAP) >= (required)) #endif /* real_size is the size we actually have to allocate, allowing for overhead and alignment. */ #define REAL_SIZE(sz) \ ((sz) < sizeof (struct freelist_entry) - sizeof (size_t) \ ? sizeof (struct freelist_entry) \ : sz + sizeof (size_t) + M_ALIGN(sz, sizeof (size_t))) #ifdef DEFINE_MALLOC void * __malloc_end = &__malloc_start; fle __malloc_freelist; void * malloc (size_t sz) { fle *nextfree; fle block; /* real_size is the size we actually have to allocate, allowing for overhead and alignment. */ size_t real_size = REAL_SIZE (sz); /* Look for the first block on the freelist that is large enough. */ for (nextfree = &__malloc_freelist; *nextfree; nextfree = &(*nextfree)->next) { block = *nextfree; if (block->size >= real_size) { /* If the block found is just the right size, remove it from the free list. Otherwise, split it. */ if (block->size < real_size + sizeof (struct freelist_entry)) { *nextfree = block->next; return (void *)&block->next; } else { size_t newsize = block->size - real_size; fle newnext = block->next; *nextfree = (fle)((size_t)block + real_size); (*nextfree)->size = newsize; (*nextfree)->next = newnext; goto done; } } /* If this is the last block on the freelist, and it was too small, enlarge it. */ if (! block->next && __malloc_end == (void *)((size_t)block + block->size)) { size_t moresize = real_size - block->size; if (! CAN_ALLOC_P (moresize)) return NULL; *nextfree = NULL; if (MALLOC_DIRECTION < 0) { block = __malloc_end = (void *)((size_t)block - moresize); } else { __malloc_end = (void *)((size_t)block + real_size); } goto done; } } /* No free space at the end of the free list. Allocate new space and use that. */ if (! CAN_ALLOC_P (real_size)) return NULL; if (MALLOC_DIRECTION > 0) { block = __malloc_end; __malloc_end = (void *)((size_t)__malloc_end + real_size); } else { block = __malloc_end = (void *)((size_t)__malloc_end - real_size); } done: block->size = real_size; return (void *)&block->next; } #endif #ifdef DEFINE_FREE void free (void *block_p) { fle *nextfree; fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next)); if (block_p == NULL) return; /* Look on the freelist to see if there's a free block just before or just after this block. */ for (nextfree = &__malloc_freelist; *nextfree; nextfree = &(*nextfree)->next) { fle thisblock = *nextfree; if ((size_t)thisblock + thisblock->size == (size_t) block) { thisblock->size += block->size; if (MALLOC_DIRECTION > 0 && thisblock->next && (size_t) block + block->size == (size_t) thisblock->next) { thisblock->size += thisblock->next->size; thisblock->next = thisblock->next->next; } return; } else if ((size_t) thisblock == (size_t) block + block->size) { if (MALLOC_DIRECTION < 0 && thisblock->next && (size_t) block == ((size_t) thisblock->next + thisblock->next->size)) { *nextfree = thisblock->next; thisblock->next->size += block->size + thisblock->size; } else { block->size += thisblock->size; block->next = thisblock->next; *nextfree = block; } return; } else if ((MALLOC_DIRECTION > 0 && (size_t) thisblock > (size_t) block) || (MALLOC_DIRECTION < 0 && (size_t) thisblock < (size_t) block)) break; } block->next = *nextfree; *nextfree = block; return; } #endif #ifdef DEFINE_REALLOC void * realloc (void *block_p, size_t sz) { fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next)); size_t real_size = REAL_SIZE (sz); size_t old_real_size; if (block_p == NULL) return malloc (sz); old_real_size = block->size; /* Perhaps we need to allocate more space. */ if (old_real_size < real_size) { void *result; size_t old_size = old_real_size - sizeof (size_t); /* Need to allocate, copy, and free. */ result = malloc (sz); if (result == NULL) return NULL; memcpy (result, block_p, old_size < sz ? old_size : sz); free (block_p); return result; } /* Perhaps we can free some space. */ if (old_real_size - real_size >= sizeof (struct freelist_entry)) { fle newblock = (fle)((size_t)block + real_size); block->size = real_size; newblock->size = old_real_size - real_size; free (&newblock->next); } return block_p; } #endif #ifdef DEFINE_CALLOC void * calloc (size_t n, size_t elem_size) { void *result; size_t sz = n * elem_size; result = malloc (sz); if (result != NULL) memset (result, 0, sz); return result; } #endif #ifdef DEFINE_CFREE void cfree (void *p) { free (p); } #endif #ifdef DEFINE_MEMALIGN void * memalign (size_t align, size_t sz) { fle *nextfree; fle block; /* real_size is the size we actually have to allocate, allowing for overhead and alignment. */ size_t real_size = REAL_SIZE (sz); /* Some sanity checking on 'align'. */ if ((align & (align - 1)) != 0 || align <= 0) return NULL; /* Look for the first block on the freelist that is large enough. */ /* One tricky part is this: We want the result to be a valid pointer to free. That means that there has to be room for a size_t before the block. If there's additional space before the block, it should go on the freelist, or it'll be lost---we could add it to the size of the block before it in memory, but finding the previous block is expensive. */ for (nextfree = &__malloc_freelist; ; nextfree = &(*nextfree)->next) { size_t before_size; size_t old_size; /* If we've run out of free blocks, allocate more space. */ if (! *nextfree) { old_size = real_size; if (MALLOC_DIRECTION < 0) { old_size += M_ALIGN_SUB (((size_t)__malloc_end - old_size + sizeof (size_t)), align); if (! CAN_ALLOC_P (old_size)) return NULL; block = __malloc_end = (void *)((size_t)__malloc_end - old_size); } else { block = __malloc_end; old_size += M_ALIGN ((size_t)__malloc_end + sizeof (size_t), align); if (! CAN_ALLOC_P (old_size)) return NULL; __malloc_end = (void *)((size_t)__malloc_end + old_size); } *nextfree = block; block->size = old_size; block->next = NULL; } else { block = *nextfree; old_size = block->size; } before_size = M_ALIGN (&block->next, align); if (before_size != 0) before_size = sizeof (*block) + M_ALIGN (&(block+1)->next, align); /* If this is the last block on the freelist, and it is too small, enlarge it. */ if (! block->next && old_size < real_size + before_size && __malloc_end == (void *)((size_t)block + block->size)) { if (MALLOC_DIRECTION < 0) { size_t moresize = real_size - block->size; moresize += M_ALIGN_SUB ((size_t)&block->next - moresize, align); if (! CAN_ALLOC_P (moresize)) return NULL; block = __malloc_end = (void *)((size_t)block - moresize); block->next = NULL; block->size = old_size = old_size + moresize; before_size = 0; } else { if (! CAN_ALLOC_P (before_size + real_size - block->size)) return NULL; __malloc_end = (void *)((size_t)block + before_size + real_size); block->size = old_size = before_size + real_size; } /* Two out of the four cases below will now be possible; which two depends on MALLOC_DIRECTION. */ } if (old_size >= real_size + before_size) { /* This block will do. If there needs to be space before it, split the block. */ if (before_size != 0) { fle old_block = block; old_block->size = before_size; block = (fle)((size_t)block + before_size); /* If there's no space after the block, we're now nearly done; just make a note of the size required. Otherwise, we need to create a new free space block. */ if (old_size - before_size <= real_size + sizeof (struct freelist_entry)) { block->size = old_size - before_size; return (void *)&block->next; } else { fle new_block; new_block = (fle)((size_t)block + real_size); new_block->size = old_size - before_size - real_size; if (MALLOC_DIRECTION > 0) { new_block->next = old_block->next; old_block->next = new_block; } else { new_block->next = old_block; *nextfree = new_block; } goto done; } } else { /* If the block found is just the right size, remove it from the free list. Otherwise, split it. */ if (old_size <= real_size + sizeof (struct freelist_entry)) { *nextfree = block->next; return (void *)&block->next; } else { size_t newsize = old_size - real_size; fle newnext = block->next; *nextfree = (fle)((size_t)block + real_size); (*nextfree)->size = newsize; (*nextfree)->next = newnext; goto done; } } } } done: block->size = real_size; return (void *)&block->next; } #endif #ifdef DEFINE_VALLOC void * valloc (size_t sz) { return memalign (128, sz); } #endif #ifdef DEFINE_PVALLOC void * pvalloc (size_t sz) { return memalign (128, sz + M_ALIGN (sz, 128)); } #endif #ifdef DEFINE_MALLINFO #include "malloc.h" struct mallinfo mallinfo (void) { struct mallinfo r; fle fr; size_t free_size; size_t total_size; size_t free_blocks; memset (&r, 0, sizeof (r)); free_size = 0; free_blocks = 0; for (fr = __malloc_freelist; fr; fr = fr->next) { free_size += fr->size; free_blocks++; if (! fr->next) { int atend; if (MALLOC_DIRECTION > 0) atend = (void *)((size_t)fr + fr->size) == __malloc_end; else atend = (void *)fr == __malloc_end; if (atend) r.keepcost = fr->size; } } if (MALLOC_DIRECTION > 0) total_size = (char *)__malloc_end - (char *)&__malloc_start; else total_size = (char *)&__malloc_start - (char *)__malloc_end; #ifdef DEBUG /* Fixme: should walk through all the in-use blocks and see if they're valid. */ #endif r.arena = total_size; r.fordblks = free_size; r.uordblks = total_size - free_size; r.ordblks = free_blocks; return r; } #endif #ifdef DEFINE_MALLOC_STATS #include "malloc.h" #include <stdio.h> void malloc_stats(void) { struct mallinfo i; FILE *fp; fp = stderr; i = mallinfo(); fprintf (fp, "malloc has reserved %u bytes between %p and %p\n", i.arena, &__malloc_start, __malloc_end); fprintf (fp, "there are %u bytes free in %u chunks\n", i.fordblks, i.ordblks); fprintf (fp, "of which %u bytes are at the end of the reserved space\n", i.keepcost); fprintf (fp, "and %u bytes are in use.\n", i.uordblks); } #endif #ifdef DEFINE_MALLOC_USABLE_SIZE size_t malloc_usable_size (void *block_p) { fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next)); return block->size - sizeof (size_t); } #endif #ifdef DEFINE_MALLOPT int mallopt (int n, int v) { (void)n; (void)v; return 0; } #endif