| /****************************************************************************** |
| * Copyright (c) 2004, 2008 IBM Corporation |
| * All rights reserved. |
| * This program and the accompanying materials |
| * are made available under the terms of the BSD License |
| * which accompanies this distribution, and is available at |
| * http://www.opensource.org/licenses/bsd-license.php |
| * |
| * Contributors: |
| * IBM Corporation - initial implementation |
| *****************************************************************************/ |
| |
| |
| #include "stddef.h" |
| #include "stdlib.h" |
| #include "unistd.h" |
| #include "malloc_defs.h" |
| |
| |
| static int clean(void); |
| |
| |
| /* act points to the end of the initialized heap and the start of uninitialized heap */ |
| static char *act; |
| |
| /* Pointers to start and end of heap: */ |
| static char *heap_start, *heap_end; |
| |
| |
| /* |
| * Standard malloc function |
| */ |
| void * |
| malloc(size_t size) |
| { |
| char *header; |
| void *data; |
| size_t blksize; /* size of memory block including the chunk */ |
| |
| blksize = size + sizeof(struct chunk); |
| |
| /* has malloc been called for the first time? */ |
| if (act == 0) { |
| size_t initsize; |
| /* add some space so we have a good initial playground */ |
| initsize = (blksize + 0x1000) & ~0x0fff; |
| /* get initial memory region with sbrk() */ |
| heap_start = sbrk(initsize); |
| if (heap_start == (void*)-1) |
| return NULL; |
| heap_end = heap_start + initsize; |
| act = heap_start; |
| } |
| |
| header = act; |
| data = act + sizeof(struct chunk); |
| |
| /* Check if there is space left in the uninitialized part of the heap */ |
| if (act + blksize > heap_end) { |
| //search at begin of heap |
| header = heap_start; |
| |
| while ((((struct chunk *) header)->inuse != 0 |
| || ((struct chunk *) header)->length < size) |
| && header < act) { |
| header = header + sizeof(struct chunk) |
| + ((struct chunk *) header)->length; |
| } |
| |
| // check if heap is full |
| if (header >= act) { |
| if (clean()) { |
| // merging of free blocks succeeded, so try again |
| return malloc(size); |
| } else if (sbrk(blksize) == heap_end) { |
| // succeeded to get more memory, so try again |
| heap_end += blksize; |
| return malloc(size); |
| } else { |
| // No more memory available |
| return 0; |
| } |
| } |
| |
| // Check if we need to split this memory block into two |
| if (((struct chunk *) header)->length > blksize) { |
| //available memory is too big |
| int alt; |
| |
| alt = ((struct chunk *) header)->length; |
| ((struct chunk *) header)->inuse = 1; |
| ((struct chunk *) header)->length = size; |
| data = header + sizeof(struct chunk); |
| |
| //mark the rest of the heap |
| header = data + size; |
| ((struct chunk *) header)->inuse = 0; |
| ((struct chunk *) header)->length = |
| alt - blksize; |
| } else { |
| //new memory matched exactly in available memory |
| ((struct chunk *) header)->inuse = 1; |
| data = header + sizeof(struct chunk); |
| } |
| |
| } else { |
| |
| ((struct chunk *) header)->inuse = 1; |
| ((struct chunk *) header)->length = size; |
| |
| act += blksize; |
| } |
| |
| return data; |
| } |
| |
| |
| /* |
| * Merge free memory blocks in initialized heap if possible |
| */ |
| static int |
| clean(void) |
| { |
| char *header; |
| char *firstfree = 0; |
| char check = 0; |
| |
| header = heap_start; |
| //if (act == 0) // This should never happen |
| // act = heap_end; |
| |
| while (header < act) { |
| |
| if (((struct chunk *) header)->inuse == 0) { |
| if (firstfree == 0) { |
| /* First free block in a row, only save address */ |
| firstfree = header; |
| |
| } else { |
| /* more than one free block in a row, merge them! */ |
| ((struct chunk *) firstfree)->length += |
| ((struct chunk *) header)->length + |
| sizeof(struct chunk); |
| check = 1; |
| } |
| } else { |
| firstfree = 0; |
| |
| } |
| |
| header = header + sizeof(struct chunk) |
| + ((struct chunk *) header)->length; |
| |
| } |
| |
| return check; |
| } |