Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Browse files
Browse the repository at this point in the history
Memory allocator
- Loading branch information
Sebastien Bourdeauducq
committed
Jun 1, 2012
1 parent
3f1fd02
commit 6707cd1
Showing
18 changed files
with
1,726 additions
and
45 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,22 @@ | ||
MISPDIR=.. | ||
include $(MISPDIR)/common.mak | ||
|
||
CFLAGS+=-I$(MISPDIR)/libmm/include | ||
OBJECTS=mm_addfreechunk.o mm_free.o mm_mallinfo.o mm_memalign.o mm_shrinkchunk.o mm_zalloc.o mm_calloc.o mm_initialize.o mm_malloc.o mm_realloc.o mm_size2ndx.o | ||
|
||
all: libmm.a | ||
|
||
# pull in dependency info for *existing* .o files | ||
-include $(OBJECTS:.o=.d) | ||
|
||
libmm.a: $(OBJECTS) | ||
$(AR) clr libmm.a $(OBJECTS) | ||
$(RANLIB) libmm.a | ||
|
||
%.o: %.c | ||
$(compile-dep) | ||
|
||
.PHONY: clean | ||
|
||
clean: | ||
rm -f $(OBJECTS) $(OBJECTS:.o=.d) libmm.a .*~ *~ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,24 @@ | ||
#ifndef __MALLOC_H | ||
#define __MALLOC_H | ||
|
||
struct mallinfo | ||
{ | ||
int arena; /* This is the total size of memory allocated | ||
* for use by malloc in bytes. */ | ||
int ordblks; /* This is the number of free (not in use) chunks */ | ||
int mxordblk; /* Size of the largest free (not in use) chunk */ | ||
int uordblks; /* This is the total size of memory occupied by | ||
* chunks handed out by malloc. */ | ||
int fordblks; /* This is the total size of memory occupied | ||
* by free (not in use) chunks.*/ | ||
}; | ||
|
||
struct mallinfo mallinfo(void); | ||
void *memalign(size_t boundary, size_t size); | ||
|
||
/* Those are non-standard */ | ||
void mm_initialize(void *heapstart, size_t heapsize); | ||
void mm_addregion(void *heapstart, size_t heapsize); | ||
void *zalloc(size_t size); | ||
|
||
#endif /* __MALLOC_H */ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,74 @@ | ||
/************************************************************************ | ||
* mm/mm_addfreechunk.c | ||
* | ||
* Copyright (C) 2007, 2009 Gregory Nutt. All rights reserved. | ||
* Author: Gregory Nutt <spudmonkey@racsa.co.cr> | ||
* | ||
* Redistribution and use in source and binary forms, with or without | ||
* modification, are permitted provided that the following conditions | ||
* are met: | ||
* | ||
* 1. Redistributions of source code must retain the above copyright | ||
* notice, this list of conditions and the following disclaimer. | ||
* 2. Redistributions in binary form must reproduce the above copyright | ||
* notice, this list of conditions and the following disclaimer in | ||
* the documentation and/or other materials provided with the | ||
* distribution. | ||
* 3. Neither the name NuttX nor the names of its contributors may be | ||
* used to endorse or promote products derived from this software | ||
* without specific prior written permission. | ||
* | ||
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | ||
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | ||
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | ||
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | ||
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, | ||
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS | ||
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED | ||
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN | ||
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
* POSSIBILITY OF SUCH DAMAGE. | ||
* | ||
************************************************************************/ | ||
|
||
#include "mm_environment.h" | ||
#include "mm_internal.h" | ||
|
||
/************************************************************************ | ||
* mm_addfreechunk | ||
* | ||
* Description: | ||
* Add a free chunk to the node next | ||
* | ||
************************************************************************/ | ||
|
||
void mm_addfreechunk(struct mm_freenode_s *node) | ||
{ | ||
struct mm_freenode_s *next; | ||
struct mm_freenode_s *prev; | ||
|
||
/* Convert the size to a nodelist index */ | ||
|
||
int ndx = mm_size2ndx(node->size); | ||
|
||
/* Now put the new node int the next */ | ||
|
||
for (prev = &g_nodelist[ndx], next = g_nodelist[ndx].flink; | ||
next && next->size && next->size < node->size; | ||
prev = next, next = next->flink); | ||
|
||
/* Does it go in mid next or at the end? */ | ||
|
||
prev->flink = node; | ||
node->blink = prev; | ||
node->flink = next; | ||
|
||
if (next) | ||
{ | ||
/* The new node goes between prev and next */ | ||
|
||
next->blink = node; | ||
} | ||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,56 @@ | ||
/************************************************************************ | ||
* mm_calloc.c | ||
* | ||
* Copyright (C) 2007, 2009 Gregory Nutt. All rights reserved. | ||
* Author: Gregory Nutt <spudmonkey@racsa.co.cr> | ||
* | ||
* Redistribution and use in source and binary forms, with or without | ||
* modification, are permitted provided that the following conditions | ||
* are met: | ||
* | ||
* 1. Redistributions of source code must retain the above copyright | ||
* notice, this list of conditions and the following disclaimer. | ||
* 2. Redistributions in binary form must reproduce the above copyright | ||
* notice, this list of conditions and the following disclaimer in | ||
* the documentation and/or other materials provided with the | ||
* distribution. | ||
* 3. Neither the name NuttX nor the names of its contributors may be | ||
* used to endorse or promote products derived from this software | ||
* without specific prior written permission. | ||
* | ||
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | ||
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | ||
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | ||
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | ||
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, | ||
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS | ||
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED | ||
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN | ||
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
* POSSIBILITY OF SUCH DAMAGE. | ||
* | ||
************************************************************************/ | ||
|
||
#include "mm_environment.h" | ||
#include "mm_internal.h" | ||
|
||
/************************************************************************ | ||
* calloc | ||
* | ||
* Descripton: | ||
* calloc calculates the size and calls zalloc | ||
************************************************************************/ | ||
|
||
void *calloc(size_t n, size_t elem_size) | ||
{ | ||
void *ret = NULL; | ||
|
||
if (n > 0 && elem_size > 0) | ||
{ | ||
ret = zalloc(n * elem_size); | ||
} | ||
|
||
return ret; | ||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,57 @@ | ||
/**************************************************************************** | ||
* mm/mm_environment.h | ||
* | ||
* Copyright (C) 2007-2009, 2011 Gregory Nutt. All rights reserved. | ||
* Author: Gregory Nutt <spudmonkey@racsa.co.cr> | ||
* | ||
* Redistribution and use in source and binary forms, with or without | ||
* modification, are permitted provided that the following conditions | ||
* are met: | ||
* | ||
* 1. Redistributions of source code must retain the above copyright | ||
* notice, this list of conditions and the following disclaimer. | ||
* 2. Redistributions in binary form must reproduce the above copyright | ||
* notice, this list of conditions and the following disclaimer in | ||
* the documentation and/or other materials provided with the | ||
* distribution. | ||
* 3. Neither the name NuttX nor the names of its contributors may be | ||
* used to endorse or promote products derived from this software | ||
* without specific prior written permission. | ||
* | ||
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | ||
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | ||
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | ||
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | ||
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, | ||
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS | ||
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED | ||
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN | ||
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
* POSSIBILITY OF SUCH DAMAGE. | ||
* | ||
****************************************************************************/ | ||
|
||
#ifndef __MM_ENVIRONMENT_H | ||
#define __MM_ENVIRONMENT_H | ||
|
||
#include <stdio.h> | ||
#include <stdlib.h> | ||
#include <stdint.h> | ||
#include <string.h> | ||
#include <errno.h> | ||
#include <assert.h> | ||
#include <malloc.h> | ||
|
||
#define mm_errno errno | ||
#ifdef MM_DEBUG | ||
#define mvdbg(format, arg...) printf(format, ##arg) | ||
#else | ||
#define mvdbg(format, arg...) | ||
#endif | ||
|
||
#define ASSERT(e) assert(e) | ||
#define DEBUGASSERT(e) assert(e) | ||
|
||
#endif /* __MM_ENVIRONMENT_H */ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,129 @@ | ||
/************************************************************************ | ||
* mm/mm_free.c | ||
* | ||
* Copyright (C) 2007, 2009 Gregory Nutt. All rights reserved. | ||
* Author: Gregory Nutt <spudmonkey@racsa.co.cr> | ||
* | ||
* Redistribution and use in source and binary forms, with or without | ||
* modification, are permitted provided that the following conditions | ||
* are met: | ||
* | ||
* 1. Redistributions of source code must retain the above copyright | ||
* notice, this list of conditions and the following disclaimer. | ||
* 2. Redistributions in binary form must reproduce the above copyright | ||
* notice, this list of conditions and the following disclaimer in | ||
* the documentation and/or other materials provided with the | ||
* distribution. | ||
* 3. Neither the name NuttX nor the names of its contributors may be | ||
* used to endorse or promote products derived from this software | ||
* without specific prior written permission. | ||
* | ||
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | ||
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | ||
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | ||
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | ||
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, | ||
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS | ||
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED | ||
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN | ||
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
* POSSIBILITY OF SUCH DAMAGE. | ||
* | ||
************************************************************************/ | ||
|
||
#include <assert.h> | ||
#include "mm_environment.h" | ||
#include "mm_internal.h" | ||
|
||
/************************************************************************ | ||
* free | ||
* | ||
* Description: | ||
* Returns a chunk of memory into the list of free nodes, | ||
* merging with adjacent free chunks if possible. | ||
* | ||
************************************************************************/ | ||
|
||
void free(void *mem) | ||
{ | ||
struct mm_freenode_s *node; | ||
struct mm_freenode_s *prev; | ||
struct mm_freenode_s *next; | ||
|
||
mvdbg("Freeing %p\n", mem); | ||
|
||
/* Protect against attempts to free a NULL reference */ | ||
|
||
if (!mem) | ||
{ | ||
return; | ||
} | ||
|
||
/* Map the memory chunk into a free node */ | ||
|
||
node = (struct mm_freenode_s *)((char*)mem - SIZEOF_MM_ALLOCNODE); | ||
node->preceding &= ~MM_ALLOC_BIT; | ||
|
||
/* Check if the following node is free and, if so, merge it */ | ||
|
||
next = (struct mm_freenode_s *)((char*)node + node->size); | ||
if ((next->preceding & MM_ALLOC_BIT) == 0) | ||
{ | ||
struct mm_allocnode_s *andbeyond; | ||
|
||
/* Get the node following the next node (which will | ||
* become the new next node). We know that we can never | ||
* index past the tail chunk because it is always allocated. | ||
*/ | ||
|
||
andbeyond = (struct mm_allocnode_s*)((char*)next + next->size); | ||
|
||
/* Remove the next node. There must be a predecessor, | ||
* but there may not be a successor node. | ||
*/ | ||
|
||
DEBUGASSERT(next->blink); | ||
next->blink->flink = next->flink; | ||
if (next->flink) | ||
{ | ||
next->flink->blink = next->blink; | ||
} | ||
|
||
/* Then merge the two chunks */ | ||
|
||
node->size += next->size; | ||
andbeyond->preceding = node->size | (andbeyond->preceding & MM_ALLOC_BIT); | ||
next = (struct mm_freenode_s *)andbeyond; | ||
} | ||
|
||
/* Check if the preceding node is also free and, if so, merge | ||
* it with this node | ||
*/ | ||
|
||
prev = (struct mm_freenode_s *)((char*)node - node->preceding); | ||
if ((prev->preceding & MM_ALLOC_BIT) == 0) | ||
{ | ||
/* Remove the node. There must be a predecessor, but there may | ||
* not be a successor node. | ||
*/ | ||
|
||
DEBUGASSERT(prev->blink); | ||
prev->blink->flink = prev->flink; | ||
if (prev->flink) | ||
{ | ||
prev->flink->blink = prev->blink; | ||
} | ||
|
||
/* Then merge the two chunks */ | ||
|
||
prev->size += node->size; | ||
next->preceding = prev->size | (next->preceding & MM_ALLOC_BIT); | ||
node = prev; | ||
} | ||
|
||
/* Add the merged node to the nodelist */ | ||
|
||
mm_addfreechunk(node); | ||
} |
Oops, something went wrong.