Skip to content

Commit

Permalink
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
Show file tree
Hide file tree
Showing 18 changed files with 1,726 additions and 45 deletions.
4 changes: 2 additions & 2 deletions Makefile
Expand Up @@ -2,9 +2,9 @@ MISPDIR=.
include $(MISPDIR)/common.mak

OBJECTS=crt0.o isr.o luainit.o main.o
OURLIBS=m yaffs2 glue lua
OURLIBS=m mm yaffs2 glue lua

CFLAGS+=-I$(MISPDIR)/libm/include -I$(LUADIR)/src
CFLAGS+=-I$(MISPDIR)/libm/include -I$(MISPDIR)/libmm/include -I$(LUADIR)/src

all: misp.bin

Expand Down
22 changes: 22 additions & 0 deletions libmm/Makefile
@@ -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 .*~ *~
24 changes: 24 additions & 0 deletions libmm/include/malloc.h
@@ -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 */
74 changes: 74 additions & 0 deletions libmm/mm_addfreechunk.c
@@ -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;
}
}
56 changes: 56 additions & 0 deletions libmm/mm_calloc.c
@@ -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;
}
57 changes: 57 additions & 0 deletions libmm/mm_environment.h
@@ -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 */
129 changes: 129 additions & 0 deletions libmm/mm_free.c
@@ -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);
}

0 comments on commit 6707cd1

Please sign in to comment.