Skip to content

Commit

Permalink
Memory allocator
Browse files Browse the repository at this point in the history
Sebastien Bourdeauducq committed Jun 1, 2012
1 parent 3f1fd02 commit 6707cd1
Showing 18 changed files with 1,726 additions and 45 deletions.
4 changes: 2 additions & 2 deletions Makefile
Original file line number Diff line number Diff line change
@@ -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

22 changes: 22 additions & 0 deletions libmm/Makefile
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 .*~ *~
24 changes: 24 additions & 0 deletions libmm/include/malloc.h
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 */
74 changes: 74 additions & 0 deletions libmm/mm_addfreechunk.c
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;
}
}
56 changes: 56 additions & 0 deletions libmm/mm_calloc.c
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;
}
57 changes: 57 additions & 0 deletions libmm/mm_environment.h
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 */
129 changes: 129 additions & 0 deletions libmm/mm_free.c
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);
}
184 changes: 184 additions & 0 deletions libmm/mm_initialize.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,184 @@
/****************************************************************************
* mm/mm_initialize.c
*
* 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.
*
****************************************************************************/

#include "mm_environment.h"
#include "mm_internal.h"

/* This is the size of the heap provided to mm */

size_t g_heapsize;

/* This is the first and last nodes of the heap */

struct mm_allocnode_s *g_heapstart[CONFIG_MM_REGIONS];
struct mm_allocnode_s *g_heapend[CONFIG_MM_REGIONS];

#if CONFIG_MM_REGIONS > 1
int g_nregions;
#endif

/* All free nodes are maintained in a doubly linked list. This
* array provides some hooks into the list at various points to
* speed searches for free nodes.
*/

struct mm_freenode_s g_nodelist[MM_NNODES];

/****************************************************************************
* Public Functions
****************************************************************************/

/****************************************************************************
* Function: mm_initialize
*
* Description:
* This is an internal OS function called only at power-up
* boot time.
*
* Parameters:
* heapstart - Start of the initial heap region
* heapsize - Size of the initial heap region
*
* Return Value:
* None
*
* Assumptions:
*
****************************************************************************/

void mm_initialize(void *heapstart, size_t heapsize)
{
int i;

mvdbg("Heap: start=%p size=%u\n", heapstart, heapsize);

CHECK_ALLOCNODE_SIZE;
CHECK_FREENODE_SIZE;

/* Set up global variables */

g_heapsize = 0;

#if CONFIG_MM_REGIONS > 1
g_nregions = 0;
#endif

/* Initialize the node array */

memset(g_nodelist, 0, sizeof(struct mm_freenode_s) * MM_NNODES);
for (i = 1; i < MM_NNODES; i++)
{
g_nodelist[i-1].flink = &g_nodelist[i];
g_nodelist[i].blink = &g_nodelist[i-1];
}

/* Add the initial region of memory to the heap */

mm_addregion(heapstart, heapsize);
}

/****************************************************************************
* Function: mm_addregion
*
* Description:
* This function gives a region of contiguous memory to
* the memory manager
*
* Parameters:
* heapstart - Start of the heap region
* heapsize - Size of the heap region
*
* Return Value:
* None
*
* Assumptions:
*
****************************************************************************/

void mm_addregion(void *heapstart, size_t heapsize)
{
struct mm_freenode_s *node;
uintptr_t heapbase;
uintptr_t heapend;
#if CONFIG_MM_REGIONS > 1
int IDX = g_nregions;
#else
# define IDX 0
#endif

/* Adjust the provide heap start and size so that they are
* both aligned with the MM_MIN_CHUNK size.
*/

heapbase = MM_ALIGN_UP((uintptr_t)heapstart);
heapend = MM_ALIGN_DOWN((uintptr_t)heapstart + (uintptr_t)heapsize);
heapsize = heapend - heapbase;

mvdbg("Region %d: base=%p size=%u\n", IDX+1, heapstart, heapsize);

/* Add the size of this region to the total size of the heap */

g_heapsize += heapsize;

/* Create two "allocated" guard nodes at the beginning and end of
* the heap. These only serve to keep us from allocating outside
* of the heap.
*
* And create one free node between the guard nodes that contains
* all available memory.
*/

g_heapstart[IDX] = (struct mm_allocnode_s *)heapbase;
g_heapstart[IDX]->size = SIZEOF_MM_ALLOCNODE;
g_heapstart[IDX]->preceding = MM_ALLOC_BIT;

node = (struct mm_freenode_s *)(heapbase + SIZEOF_MM_ALLOCNODE);
node->size = heapsize - 2*SIZEOF_MM_ALLOCNODE;
node->preceding = SIZEOF_MM_ALLOCNODE;

g_heapend[IDX] = (struct mm_allocnode_s *)(heapend - SIZEOF_MM_ALLOCNODE);
g_heapend[IDX]->size = SIZEOF_MM_ALLOCNODE;
g_heapend[IDX]->preceding = node->size | MM_ALLOC_BIT;

#undef IDX

#if CONFIG_MM_REGIONS > 1
g_nregions++;
#endif

/* Add the single, large free node to the nodelist */

mm_addfreechunk(node);
}
148 changes: 148 additions & 0 deletions libmm/mm_internal.h
Original file line number Diff line number Diff line change
@@ -0,0 +1,148 @@
/************************************************************************
* mm/mm_internal.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_INTERNAL_H
#define __MM_INTERNAL_H

/* Chunk Header Definitions *********************************************/
/* These definitions define the characteristics of allocator
*
* MM_MIN_SHIFT is used to define MM_MIN_CHUNK.
* MM_MIN_CHUNK - is the smallest physical chunk that can
* be allocated. It must be at least a large as
* sizeof(struct mm_freenode_s). Larger values may
* improve performance slightly, but will waste memory
* due to quantization losses.
*
* MM_MAX_SHIFT is used to define MM_MAX_CHUNK
* MM_MAX_CHUNK is the largest, contiguous chunk of memory
* that can be allocated. It can range from 16-bytes to
* 4Gb. Larger values of MM_MAX_SHIFT can cause larger
* data structure sizes and, perhaps, minor performance
* losses.
*/

# define MM_MIN_SHIFT 4 /* 16 bytes */
# define MM_MAX_SHIFT 22 /* 4 Mb */

/* All other definitions derive from these two */

#define MM_MIN_CHUNK (1 << MM_MIN_SHIFT)
#define MM_MAX_CHUNK (1 << MM_MAX_SHIFT)
#define MM_NNODES (MM_MAX_SHIFT - MM_MIN_SHIFT + 1)

#define MM_GRAN_MASK (MM_MIN_CHUNK-1)
#define MM_ALIGN_UP(a) (((a) + MM_GRAN_MASK) & ~MM_GRAN_MASK)
#define MM_ALIGN_DOWN(a) ((a) & ~MM_GRAN_MASK)

/* An allocated chunk is distinguished from a free chunk by
* bit 31 of the 'preceding' chunk size. If set, then this is
* an allocated chunk.
*/

#define MM_ALLOC_BIT 0x80000000
#define MM_IS_ALLOCATED(n) \
((int)((struct mm_allocnode_s*)(n)->preceding) < 0))


/* Determine the size of the chunk size/offset type */

typedef size_t mmsize_t;
#define MMSIZE_MAX SIZE_MAX

#define CONFIG_MM_REGIONS 1

/* This describes an allocated chunk. An allocated chunk is
* distinguished from a free chunk by bit 15/31 of the 'preceding' chunk
* size. If set, then this is an allocated chunk.
*/

struct mm_allocnode_s
{
mmsize_t size; /* Size of this chunk */
mmsize_t preceding; /* Size of the preceding chunk */
};

/* What is the size of the allocnode? */

#define SIZEOF_MM_ALLOCNODE 8

#define CHECK_ALLOCNODE_SIZE \
DEBUGASSERT(sizeof(struct mm_allocnode_s) == SIZEOF_MM_ALLOCNODE)

/* This describes a free chunk */

struct mm_freenode_s
{
mmsize_t size; /* Size of this chunk */
mmsize_t preceding; /* Size of the preceding chunk */
struct mm_freenode_s *flink; /* Supports a doubly linked list */
struct mm_freenode_s *blink;
};

/* What is the size of the freenode? */

#define SIZEOF_MM_FREENODE 16

#define CHECK_FREENODE_SIZE \
DEBUGASSERT(sizeof(struct mm_freenode_s) == SIZEOF_MM_FREENODE)


/* This is the size of the heap provided to mm */
extern size_t g_heapsize;

/* This is the first and last nodes of the heap */
extern struct mm_allocnode_s *g_heapstart[CONFIG_MM_REGIONS];
extern struct mm_allocnode_s *g_heapend[CONFIG_MM_REGIONS];

#if CONFIG_MM_REGIONS > 1
extern int g_nregions;
#else
#define g_nregions 1
#endif

/* All free nodes are maintained in a doubly linked list. This
* array provides some hooks into the list at various points to
* speed searches for free nodes.
*/

extern struct mm_freenode_s g_nodelist[MM_NNODES];

extern void mm_shrinkchunk(struct mm_allocnode_s *node,
size_t size);
extern void mm_addfreechunk(struct mm_freenode_s *node);
extern int mm_size2ndx(size_t size);

#endif /* __MM_INTERNAL_H */
104 changes: 104 additions & 0 deletions libmm/mm_mallinfo.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,104 @@
/****************************************************************************
* mm/mm_mallinfo.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"


/****************************************************************************
* mallinfo
*
* Description:
* mallinfo returns a copy of updated current mallinfo.
*
****************************************************************************/

struct mallinfo mallinfo(void)
{
struct mm_allocnode_s *node;
size_t mxordblk = 0;
int ordblks = 0; /* Number of non-inuse chunks */
size_t uordblks = 0; /* Total allocated space */
size_t fordblks = 0; /* Total non-inuse space */
#if CONFIG_MM_REGIONS > 1
int region;
#else
# define region 0
#endif
static struct mallinfo info;

/* Visit each region */

#if CONFIG_MM_REGIONS > 1
for (region = 0; region < g_nregions; region++)
#endif
{
/* Visit each node in the region */

for (node = g_heapstart[region];
node < g_heapend[region];
node = (struct mm_allocnode_s *)((char*)node + node->size))
{
mvdbg("region=%d node=%p preceding=%p\n", region, node, node->preceding);
if (node->preceding & MM_ALLOC_BIT)
{
uordblks += node->size;
}
else
{
ordblks++;
fordblks += node->size;
if (node->size > mxordblk)
{
mxordblk = node->size;
}
}
}

mvdbg("region=%d node=%p g_heapend=%p\n", region, node, g_heapend[region]);
DEBUGASSERT(node == g_heapend[region]);
uordblks += SIZEOF_MM_ALLOCNODE; /* account for the tail node */
}
#undef region

DEBUGASSERT(uordblks + fordblks == g_heapsize);

info.arena = g_heapsize;
info.ordblks = ordblks;
info.mxordblk = mxordblk;
info.uordblks = uordblks;
info.fordblks = fordblks;
return info;
}
160 changes: 160 additions & 0 deletions libmm/mm_malloc.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,160 @@
/************************************************************
* mm/mm_malloc.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"

/************************************************************
* malloc
*
* Description:
* Find the smallest chunk that satisfies the request.
* Take the memory from that chunk, save the remaining,
* smaller chunk (if any).
*
* 8-byte alignment of the allocated data is assured.
*
************************************************************/

void *malloc(size_t size)
{
struct mm_freenode_s *node;
void *ret = NULL;
int ndx;

/* Handle bad sizes */

if (size <= 0)
{
return NULL;
}

/* Adjust the size to account for (1) the size of the allocated
* node and (2) to make sure that it is an even multiple of
* our granule size.
*/

size = MM_ALIGN_UP(size + SIZEOF_MM_ALLOCNODE);

/* Get the location in the node list to start the search.
* Special case really big alloctions
*/

if (size >= MM_MAX_CHUNK)
{
ndx = MM_NNODES-1;
}
else
{
/* Convert the request size into a nodelist index */

ndx = mm_size2ndx(size);
}

/* Search for a large enough chunk in the list of nodes.
* This list is ordered by size, but will have occasional
* zero sized nodes as we visit other g_nodelist[] entries.
*/

for (node = g_nodelist[ndx].flink;
node && node->size < size;
node = node->flink);

/* If we found a node with non-zero size, then this is one
* to use. Since the list is ordered, we know that is must be
* best fitting chunk available.
*/

if (node)
{
struct mm_freenode_s *remainder;
struct mm_freenode_s *next;
size_t remaining;

/* Remove the node. There must be a predecessor, but there may
* not be a successor node.
*/

DEBUGASSERT(node->blink);
node->blink->flink = node->flink;
if (node->flink)
{
node->flink->blink = node->blink;
}

/* Check if we have to split the free node into one of the
* allocated size and another smaller freenode. In some
* cases, the remaining bytes can be smaller (they may be
* SIZEOF_MM_ALLOCNODE). In that case, we will just carry
* the few wasted bytes at the end of the allocation.
*/

remaining = node->size - size;
if (remaining >= SIZEOF_MM_FREENODE)
{
/* Get a pointer to the next node in physical memory */

next = (struct mm_freenode_s*)(((char*)node) + node->size);

/* Create the remainder node */

remainder = (struct mm_freenode_s*)(((char*)node) + size);
remainder->size = remaining;
remainder->preceding = size;

/* Adjust the size of the node under consideration */

node->size = size;

/* Adjust the 'preceding' size of the (old) next node,
* preserving the allocated flag.
*/

next->preceding = remaining | (next->preceding & MM_ALLOC_BIT);

/* Add the remainder back into the nodelist */

mm_addfreechunk(remainder);
}

/* Handle the case of an exact size match */

node->preceding |= MM_ALLOC_BIT;
ret = (void*)((char*)node + SIZEOF_MM_ALLOCNODE);
}

mvdbg("Allocated %p, size %d\n", ret, size);
return ret;
}
190 changes: 190 additions & 0 deletions libmm/mm_memalign.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,190 @@
/************************************************************
* mm/mm_memalign.c
*
* 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.
*
************************************************************/

#include "mm_environment.h"
#include "mm_internal.h"

/************************************************************
* memalign
*
* Description:
* memalign requests more than enough space from malloc,
* finds a region within that chunk that meets the alignment
* request and then frees any leading or trailing space.
*
* The alignment argument must be a power of two (not
* checked). 8-byte alignment is guaranteed by normal
* malloc calls.
*
************************************************************/

void *memalign(size_t alignment, size_t size)
{
struct mm_allocnode_s *node;
size_t rawchunk;
size_t alignedchunk;
size_t mask = (size_t)(alignment - 1);
size_t allocsize;

/* If this requested alignement less than or equal to the
* natural alignment of malloc, then just let malloc do the
* work.
*/

if (alignment <= MM_MIN_CHUNK)
{
return malloc(size);
}

/* Adjust the size to account for (1) the size of the allocated
* node, (2) to make sure that it is an even multiple of
* our granule size, and to include the alignment amount.
*
* Notice that we increase the allocation size by twice the
* the requested alignment. We do this so that there will
* be at least two valid alignment points within the allocated
* memory.
*
* NOTE: These are sizes given to malloc and not chunk sizes.
* The do not include SIZEOF_MM_ALLOCNODE.
*/

size = MM_ALIGN_UP(size); /* Make multiples of our granule size */
allocsize = size + 2*alignment; /* Add double full alignment size */

/* Then malloc that size */

rawchunk = (size_t)malloc(allocsize);
if (rawchunk == 0)
{
return NULL;
}

/* Get the node associated with the allocation and the next
* node after the allocation.
*/

node = (struct mm_allocnode_s*)(rawchunk - SIZEOF_MM_ALLOCNODE);

/* Find the aligned subregion */

alignedchunk = (rawchunk + mask) & ~mask;

/* Check if there is free space at the beginning of the aligned chunk */

if (alignedchunk != rawchunk)
{
struct mm_allocnode_s *newnode;
struct mm_allocnode_s *next;
size_t precedingsize;

/* Get the node the next node after the allocation. */

next = (struct mm_allocnode_s*)((char*)node + node->size);

/* Make sure that there is space to convert the preceding mm_allocnode_s
* into an mm_freenode_s. I think that this should always be true
*/

DEBUGASSERT(alignedchunk >= rawchunk + 8);

newnode = (struct mm_allocnode_s*)(alignedchunk - SIZEOF_MM_ALLOCNODE);

/* Preceding size is full size of the new 'node,' including
* SIZEOF_MM_ALLOCNODE
*/

precedingsize = (size_t)newnode - (size_t)node;

/* If we were unlucky, then the alignedchunk can lie in such
* a position that precedingsize < SIZEOF_NODE_FREENODE. We
* can't let that happen because we are going to cast 'node' to
* struct mm_freenode_s below. This is why we allocated memory
* large enough to support two alignment points. In this case,
* we will simply use the second alignment point.
*/

if (precedingsize < SIZEOF_MM_FREENODE)
{
alignedchunk += alignment;
newnode = (struct mm_allocnode_s*)(alignedchunk - SIZEOF_MM_ALLOCNODE);
precedingsize = (size_t)newnode - (size_t)node;
}

/* Set up the size of the new node */

newnode->size = (size_t)next - (size_t)newnode;
newnode->preceding = precedingsize | MM_ALLOC_BIT;

/* Reduce the size of the original chunk and mark it not allocated, */

node->size = precedingsize;
node->preceding &= ~MM_ALLOC_BIT;

/* Fix the preceding size of the next node */

next->preceding = newnode->size | (next->preceding & MM_ALLOC_BIT);

/* Convert the newnode chunk size back into malloc-compatible
* size by subtracting the header size SIZEOF_MM_ALLOCNODE.
*/

allocsize = newnode->size - SIZEOF_MM_ALLOCNODE;

/* Add the original, newly freed node to the free nodelist */

mm_addfreechunk((struct mm_freenode_s *)node);

/* Replace the original node with the newlay realloaced,
* aligned node
*/

node = newnode;
}

/* Check if there is free space at the end of the aligned chunk */

if (allocsize > size)
{
/* Shrink the chunk by that much -- remember, mm_shrinkchunk
* wants internal chunk sizes that include SIZEOF_MM_ALLOCNODE,
* and not the malloc-compatible sizes that we have.
*/

mm_shrinkchunk(node, size + SIZEOF_MM_ALLOCNODE);
}

return (void*)alignedchunk;
}
328 changes: 328 additions & 0 deletions libmm/mm_realloc.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,328 @@
/************************************************************
* mm/mm_realloc.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"

/************************************************************
* realloc
*
* Description:
* If the reallocation is for less space, then:
* (1) the current allocation is reduced in size
* (2) the remainder at the end of the allocation is
* returned to the free list.
*
* If the request is for more space and the current
* allocation can be extended, it will be extended by:
* (1) Taking the additional space from the following
* free chunk, or
* (2) Taking the additional space from the preceding
* free chunk.
* (3) Or both
*
* If the request is for more space but the current chunk
* cannot be extended, then malloc a new buffer, copy the
* data into the new buffer, and free the old buffer.
*
************************************************************/

void *realloc(void *oldmem, size_t size)
{
struct mm_allocnode_s *oldnode;
struct mm_freenode_s *prev;
struct mm_freenode_s *next;
size_t oldsize;
size_t prevsize = 0;
size_t nextsize = 0;
void *newmem;

/* If oldmem is NULL, then realloc is equivalent to malloc */

if (!oldmem)
{
return malloc(size);
}

/* If size is zero, then realloc is equivalent to free */

if (size <= 0)
{
free(oldmem);
return NULL;
}

/* Adjust the size to account for (1) the size of the allocated
* node and (2) to make sure that it is an even multiple of
* our granule size.
*/

size = MM_ALIGN_UP(size + SIZEOF_MM_ALLOCNODE);

/* Map the memory chunk into an allocated node structure */

oldnode = (struct mm_allocnode_s *)((char*)oldmem - SIZEOF_MM_ALLOCNODE);

/* Check if this is a request to reduce the size of the allocation. */

oldsize = oldnode->size;
if (size <= oldsize)
{
/* Handle the special case where we are not going to change the
* size of the allocation.
*/
if (size < oldsize)
{
mm_shrinkchunk(oldnode, size);
}

/* Then return the original address */
return oldmem;
}

/* This is a request to increase the size of the allocation, Get the
* available sizes before and after the oldnode so that we can make
* the best decision
*/

next = (struct mm_freenode_s *)((char*)oldnode + oldnode->size);
if ((next->preceding & MM_ALLOC_BIT) == 0)
{
nextsize = next->size;
}

prev = (struct mm_freenode_s *)((char*)oldnode - (oldnode->preceding & ~MM_ALLOC_BIT));
if ((prev->preceding & MM_ALLOC_BIT) == 0)
{
prevsize = prev->size;
}

/* Now, check if we can extend the current allocation or not */

if (nextsize + prevsize + oldsize >= size)
{
size_t needed = size - oldsize;
size_t takeprev = 0;
size_t takenext = 0;

/* Check if we can extend into the previous chunk and if the
* previous chunk is smaller than the next chunk.
*/

if (prevsize > 0 && (nextsize >= prevsize || nextsize <= 0))
{
/* Can we get everything we need from the previous chunk? */

if (needed > prevsize)
{
/* No, take the whole previous chunk and get the
* rest that we need from the next chunk.
*/

takeprev = prevsize;
takenext = needed - prevsize;
}
else
{
/* Yes, take what we need from the previous chunk */

takeprev = needed;
takenext = 0;
}

needed = 0;
}

/* Check if we can extend into the next chunk and if we still
* need more memory.
*/

if (nextsize > 0 && needed)
{
/* Can we get everything we need from the next chunk? */

if (needed > nextsize)
{
/* No, take the whole next chunk and get the
* rest that we need from the previous chunk.
*/

takeprev = needed - nextsize;
takenext = nextsize;
}
else
{
/* Yes, take what we need from the previous chunk */

takeprev = 0;
takenext = needed;
}
}

/* Extend into the previous free chunk */

newmem = oldmem;
if (takeprev)
{
struct mm_allocnode_s *newnode;

/* Remove the previous 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;
}

/* Extend the node into the previous free chunk */

newnode = (struct mm_allocnode_s *)((char*)oldnode - takeprev);

/* Did we consume the entire preceding chunk? */

if (takeprev < prevsize)
{
/* No.. just take what we need from the previous chunk
* and put it back into the free list
*/

prev->size -= takeprev;
newnode->size = oldsize + takeprev;
newnode->preceding = prev->size | MM_ALLOC_BIT;
next->preceding = newnode->size | (next->preceding & MM_ALLOC_BIT);

/* Return the previous free node to the nodelist (with the new size) */

mm_addfreechunk(prev);

/* Now we want to return newnode */

oldnode = newnode;
}
else
{
/* Yes.. update its size (newnode->preceding is already set) */

newnode->size += oldsize;
newnode->preceding |= MM_ALLOC_BIT;
next->preceding = newnode->size | (next->preceding & MM_ALLOC_BIT);
}

oldnode = newnode;
oldsize = newnode->size;

/* Now we have to move the user contents 'down' in memory. memcpy should
* should be save for this.
*/

newmem = (void*)((char*)newnode + SIZEOF_MM_ALLOCNODE);
memcpy(newmem, oldmem, oldsize - SIZEOF_MM_ALLOCNODE);
}

/* Extend into the next free chunk */

if (takenext)
{
struct mm_freenode_s *newnode;
struct mm_allocnode_s *andbeyond;

/* Get the chunk following the next node (which could be the tail chunk) */

andbeyond = (struct mm_allocnode_s*)((char*)next + nextsize);

/* 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;
}

/* Extend the node into the next chunk */

oldnode->size = oldsize + takenext;
newnode = (struct mm_freenode_s *)((char*)oldnode + oldnode->size);

/* Did we consume the entire preceding chunk? */

if (takenext < nextsize)
{
/* No, take what we need from the next chunk and return it
* to the free nodelist.
*/

newnode->size = nextsize - takenext;
newnode->preceding = oldnode->size;
andbeyond->preceding = newnode->size | (andbeyond->preceding & MM_ALLOC_BIT);

/* Add the new free node to the nodelist (with the new size) */

mm_addfreechunk(newnode);
}
else
{
/* Yes, just update some pointers. */

andbeyond->preceding = oldnode->size | (andbeyond->preceding & MM_ALLOC_BIT);
}
}
return newmem;
}

/* The current chunk cannot be extended. Just allocate a new chunk and copy */

else
{
/* Allocate a new block. On failure, realloc must return NULL but
* leave the original memory in place.
*/
newmem = (void*)malloc(size);
if (newmem)
{
memcpy(newmem, oldmem, oldsize);
free(oldmem);
}

return newmem;
}

}

127 changes: 127 additions & 0 deletions libmm/mm_shrinkchunk.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,127 @@
/************************************************************************
* mm/mm_shrinkchunk.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_shrinkchunk
*
* Description:
* Reduce the size of the chunk specified by the node
* structure to the specified size. this internal logic
* is used both from memalign to dispose of any trailing
* memory in the aligned allocation and also by realloc
* when there is a request to reduce the size of an allocation.
*
* NOTE:
* size is the whole chunk size (payload and header)
*
************************************************************************/

void mm_shrinkchunk(struct mm_allocnode_s *node, size_t size)
{
struct mm_freenode_s *next;

/* Get a reference to the next node */

next = (struct mm_freenode_s*)((char*)node + node->size);

/* Check if it is free */

if ((next->preceding & MM_ALLOC_BIT) == 0)
{
struct mm_allocnode_s *andbeyond;
struct mm_freenode_s *newnode;

/* Get the chunk next the next node (which could be the tail chunk) */

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;
}

/* Create a new chunk that will hold both the next chunk
* and the tailing memory from the aligned chunk.
*/

newnode = (struct mm_freenode_s*)((char*)node + size);

/* Set up the size of the new node */

newnode->size = next->size + node->size - size;
newnode->preceding = size;
node->size = size;
andbeyond->preceding = newnode->size | (andbeyond->preceding & MM_ALLOC_BIT);

/* Add the new node to the freenodelist */

mm_addfreechunk(newnode);
}

/* The next chunk is allocated. Try to free the end portion
* at the end chunk to be shrunk.
*/

else if (node->size >= size + SIZEOF_MM_FREENODE)
{
struct mm_freenode_s *newnode;

/* Create a new chunk that will hold both the next chunk
* and the tailing memory from the aligned chunk.
*/

newnode = (struct mm_freenode_s*)((char*)node + size);

/* Set up the size of the new node */

newnode->size = node->size - size;
newnode->preceding = size;
node->size = size;
next->preceding = newnode->size | MM_ALLOC_BIT;

/* Add the new node to the freenodelist */

mm_addfreechunk(newnode);
}
}
58 changes: 58 additions & 0 deletions libmm/mm_size2ndx.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,58 @@
/************************************************************************
* mm/mm_size2ndx.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"

/* Convert the size to a nodelist index */

int mm_size2ndx(size_t size)
{
int ndx = 0;

if (size >= MM_MAX_CHUNK)
{
return MM_NNODES-1;
}

size >>= MM_MIN_SHIFT;
while (size > 1)
{
ndx++;
size >>= 1;
}

return ndx;
}
56 changes: 56 additions & 0 deletions libmm/mm_zalloc.c
Original file line number Diff line number Diff line change
@@ -0,0 +1,56 @@
/************************************************************************
* mm/mm_zalloc.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"

/************************************************************************
* Name: zalloc
*
* Description:
* zalloc calls malloc, then zeroes out the allocated chunk.
*
************************************************************************/

void *zalloc(size_t size)
{
void *alloc = malloc(size);
if (alloc)
{
memset(alloc, 0, size);
}

return alloc;
}
3 changes: 2 additions & 1 deletion linker.ld
Original file line number Diff line number Diff line change
@@ -48,7 +48,8 @@ SECTIONS
*(COMMON)
. = ALIGN(4);
_ebss = .;
_end = .;
. = ALIGN(8);
_heapstart = .;
} > sdram
}

47 changes: 5 additions & 42 deletions main.c
Original file line number Diff line number Diff line change
@@ -1,5 +1,6 @@
#include <stdio.h>
#include <string.h>
#include <malloc.h>

#include <irq.h>
#include <uart.h>
@@ -8,62 +9,24 @@
#include <lauxlib.h>
#include <lualib.h>

void free(void *ptr)
{
printf("don't call me!\n");
while(1);
}

void *realloc(void *ptr, size_t size)
{
printf("don't call me!\n");
while(1);
}

static void *stupid_alloc(void *ud, void *ptr, size_t osize, size_t nsize)
{
static char buffer[1024*1024];
static int index;
void *r;

if((nsize % 4) != 0)
nsize += 4 - (nsize % 4);

if(nsize > 0) {
if(ptr == NULL) {
r = &buffer[index];
index += nsize;
if(index > sizeof(buffer)) {
printf("alloc failed\n");
return NULL;
}
return r;
} else {
r = stupid_alloc(NULL, NULL, 0, nsize);
if(r == NULL) return NULL;
memcpy(r, ptr, osize);
return r;
}
} else
return NULL;
}

static void test_lua(void)
{
lua_State *L;

L = lua_newstate(stupid_alloc, NULL); // TODO: use luaL_newstate from lauxlib
L = luaL_newstate();
luaL_openlibs(L);
luaL_dostring(L, "for i=10,1,-1 do print(i) end\n");

lua_close(L);
}

extern void *_heapstart;

int main()
{
irq_setmask(0);
irq_setie(1);
uart_init();
mm_initialize(&_heapstart, 64*1024*1024);

printf("Hello World\n");
test_lua();

0 comments on commit 6707cd1

Please sign in to comment.