From 7768c51b7b1ef0becc4090705a9bd2f14aa28d00 Mon Sep 17 00:00:00 2001 From: gdisirio Date: Thu, 28 Aug 2008 13:34:46 +0000 Subject: git-svn-id: svn://svn.code.sf.net/p/chibios/svn/trunk@412 35acf78f-673a-0410-8e92-d51de3d6d3f4 --- src/chheap.c | 231 +++++++++++++++++++++++++++++++++++++++++++++++++ src/chmempools.c | 48 +++++----- src/include/ch.h | 1 + src/include/heap.h | 40 +++++++++ src/include/mempools.h | 3 + src/kernel.mk | 3 +- src/templates/chconf.h | 20 +++++ 7 files changed, 317 insertions(+), 29 deletions(-) create mode 100644 src/chheap.c create mode 100644 src/include/heap.h (limited to 'src') diff --git a/src/chheap.c b/src/chheap.c new file mode 100644 index 000000000..dbab1dbd5 --- /dev/null +++ b/src/chheap.c @@ -0,0 +1,231 @@ +/* + ChibiOS/RT - Copyright (C) 2006-2007 Giovanni Di Sirio. + + This file is part of ChibiOS/RT. + + ChibiOS/RT is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + ChibiOS/RT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +/** + * @addtogroup Memory + * @{ + */ + +#include + +#ifdef CH_USE_HEAP + +#ifndef CH_USE_MALLOC_HEAP + +#define MAGIC 0xF5A0 +#define ALIGN_TYPE void * +#define ALIGN_MASK (sizeof(ALIGN_TYPE) - 1) +#define ALIGN_SIZE(p) (((size_t)(p) + ALIGN_MASK) & ~ALIGN_MASK) + +struct header { + union { + struct header *h_next; + size_t h_magic; + }; + size_t h_size; +}; + +static struct { + struct header free; /* Guaranteed to be not adjacent to the heap */ +#if defined(CH_USE_MUTEXES) +#define H_LOCK() chMtxLock(&heap.hmtx) +#define H_UNLOCK() chMtxLock(&heap.hmtx) + Mutex hmtx; +#elif defined(CH_USE_SEMAPHORES) +#define H_LOCK() chSemWait(&heap.hsem) +#define H_UNLOCK() chMtxSignal(&heap.hsem) + Semaphore hsem; +#else +#error "The heap allocator requires mutexes or semaphores to be enabled" +#endif +#if CH_HEAP_SIZE > 0 + union { + ALIGN_TYPE alignment; + char buffer[ALIGN_SIZE(CH_HEAP_SIZE)]; + }; +#endif +} heap; + +/** + * Initializes the allocator subsystem. + * @note It is internally invoked, this function should not normally be + * invoked from the user code. + */ +void chHeapInit(void) { + struct header *hp; + +#if CH_HEAP_SIZE == 0 + extern char __heap_base__; + extern char __heap_end__; + + hp = (void *)&__heap_base__; + hp->h_size = &__heap_end__ - &__heap_base__ - sizeof(struct header); +#else + hp = (void *)&heap; + hp->h_size = (&heap.buffer[ALIGN_SIZE(CH_HEAP_SIZE)] - &heap.buffer[0]) - + sizeof(struct header); +#endif + hp->h_next = NULL; + heap.free.h_next = hp; + heap.free.h_size = 0; +#if defined(CH_USE_MUTEXES) + chMtxInit(&heap.hmtx); +#else + chSemInit(&heap.hsem, 1); +#endif +} + +/** + * Allocates a block of memory from the heap by using the first-fit algorithm. + * The allocated block is guaranteed to be properly aligned for a pointer data + * type. + * @param size the size of the block to be allocated. Note that the allocated + * block may be a bit bigger than the requested size for alignment + * and fragmentation reasons. + * @return a pointer to the allocated block or \p NULL if the block cannot be + * allocated. + */ +void *chHeapAlloc(size_t size) { + struct header *qp, *hp, *fp; + + size = ALIGN_SIZE(size); + qp = &heap.free; + H_LOCK(); + + while (qp->h_next != NULL) { + hp = qp->h_next; + if (hp->h_size >= size) { + if (hp->h_size < size + sizeof(struct header)) { + /* Gets the whole block even if it is slightly bigger than the + requested size because the fragment would be too small to be + useful */ + qp->h_next = hp->h_next; + } + else { + /* Block bigger enough, must split it */ + fp = (void *)((char *)(hp) + sizeof(struct header) + size); + fp->h_next = qp->h_next; + fp->h_size = hp->h_size - sizeof(struct header) - size; + qp->h_next = fp; + hp->h_size = size; + } + hp->h_magic = MAGIC; + + H_UNLOCK(); + return (void *)(hp + 1); + } + qp = hp; + } + + H_UNLOCK(); + return NULL; +} + +#define LIMIT(p) (struct header *)((char *)(p) + (p)->h_size) + +/** + * Frees a previously allocated memory block. + * @param p the memory block pointer + */ +void chHeapFree(void *p) { + struct header *qp, *hp; + + hp = (struct header *)p - 1; + + chDbgAssert(hp->h_magig == MAGIC, "chheap.c, chHeapFree() #1"); + + qp = &heap.free; + H_LOCK(); + + while (TRUE) { + + chDbgAssert((hp < qp) && (hp >= LIMIT(qp)), "chheap.c, chHeapFree() #2"); + + if (((qp == &heap.free) || (hp > qp)) && + ((qp->h_next == NULL) || (hp < qp->h_next))) { + /* Insertion after qp */ + hp->h_next = qp->h_next; + qp->h_next = hp; + /* Verifies if the newly inserted block should be merged */ + if (LIMIT(hp) == hp->h_next) { + /* Merge with the next block */ + hp->h_size += hp->h_next->h_size + sizeof(struct header); + hp->h_next = hp->h_next->h_next; + } + if ((LIMIT(qp) == hp)) { /* Cannot happen when qp == &heap.free */ + /* Merge with the previous block */ + qp->h_size += hp->h_size + sizeof(struct header); + qp->h_next = hp->h_next; + } + + H_UNLOCK(); + return; + } + qp = qp->h_next; + } +} + +#else /* CH_USE_MALLOC_HEAP */ + +#include + +#if defined(CH_USE_MUTEXES) +#define H_LOCK() chMtxLock(&hmtx) +#define H_UNLOCK() chMtxLock(&hmtx) +static Mutex hmtx; +#elif defined(CH_USE_SEMAPHORES) +#define H_LOCK() chSemWait(&hsem) +#define H_UNLOCK() chMtxSignal(&hsem) +static Semaphore hsem; +#else +#error "The heap allocator requires mutexes or semaphores to be enabled" +#endif + +void chHeapInit(void) { + +#if defined(CH_USE_MUTEXES) + chMtxInit(&hmtx); +#else + chSemInit(&hsem, 1); +#endif +} + +void *chHeapAlloc(size_t size) { + void *p; + + H_LOCK(); + + p = malloc(size); + + H_UNLOCK(); + return p; +} + +void chHeapFree(void *p) { + + H_LOCK(); + + free(p); + + H_UNLOCK(); +} + +#endif /* CH_USE_MALLOC_HEAP */ + +#endif /* CH_USE_HEAP */ diff --git a/src/chmempools.c b/src/chmempools.c index 5b714a73e..49020d9b2 100644 --- a/src/chmempools.c +++ b/src/chmempools.c @@ -26,29 +26,6 @@ #ifdef CH_USE_MEMPOOLS -#ifndef CH_MEMPOOLS_PROVIDE_SBRK -#include -#else -/* - * Optional internal sbrk() implementation, this code requires the linker to - * provide two symbols: __heap_base__ and __heap_end__ that are the boundaries - * of the free RAM space. - */ -extern char __heap_base__; -extern char __heap_end__; -static char *current = &__heap_base__; - -void *sbrk(ptrdiff_t increment) { - char *cp; - - if (current + increment >= &__heap_end__) - return (void *)-1; - cp = current; - current += increment; - return cp; -} -#endif /* CH_MEMPOOLS_PROVIDE_SBRK */ - /** * Initializes a memory pool. * @param mp pointer to a \p MemoryPool structure @@ -67,7 +44,7 @@ void chPoolInit(MemoryPool *mp, size_t size) { * Allocates an object from a memory pool. * @param mp pointer to a \p MemoryPool structure * @param allow_growth if \p TRUE then the object is allocated by using - * \p sbrk() in case the memory pool is empty + * \p chHeapAlloc() in case the memory pool is empty * @return the pointer to the allocated object or \p NULL if the memory is * exhausted */ @@ -79,13 +56,13 @@ void *chPoolAlloc(MemoryPool *mp, bool_t allow_growth) { chSysLock(); if (mp->mp_next == NULL) { +#ifdef CH_USE_HEAP if (allow_growth) { - p = sbrk(mp->mp_object_size); chSysUnlock(); - if (p != (void *)-1) - return p; + return chHeapAlloc(mp->mp_object_size); } +#endif /* CH_USE_HEAP */ return NULL; } p = mp->mp_next; @@ -96,7 +73,7 @@ void *chPoolAlloc(MemoryPool *mp, bool_t allow_growth) { } /** - * Releases (or adds) an object to a memory pool. + * Releases (or adds) an object into a memory pool. * @param mp pointer to a \p MemoryPool structure * @param objp the pointer to the object to be released or added * @note the object is assumed to be of the right size for the specified @@ -116,6 +93,21 @@ void chPoolFree(MemoryPool *mp, void *objp) { chSysUnlock(); } +#ifdef CH_USE_HEAP +/** + * Releases all the objects contained into a pool. + * @param mp pointer to a \p MemoryPool structure + * @note It is assumed that all the object are allocated using the heap + * allocator, do not use this function if the pool contains other kind + * of objects. + */ +void chPoolRelease(MemoryPool *mp) { + + while (mp->mp_next) + chHeapFree(mp->mp_next); +} +#endif + #endif /* CH_USE_MEMPOOLS */ /** @} */ diff --git a/src/include/ch.h b/src/include/ch.h index 18b766b9a..7325de0db 100644 --- a/src/include/ch.h +++ b/src/include/ch.h @@ -42,6 +42,7 @@ #include "sleep.h" #include "queues.h" #include "serial.h" +#include "heap.h" #include "mempools.h" #include "debug.h" diff --git a/src/include/heap.h b/src/include/heap.h new file mode 100644 index 000000000..9619eba2f --- /dev/null +++ b/src/include/heap.h @@ -0,0 +1,40 @@ +/* + ChibiOS/RT - Copyright (C) 2006-2007 Giovanni Di Sirio. + + This file is part of ChibiOS/RT. + + ChibiOS/RT is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + ChibiOS/RT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +/** + * @addtogroup Heap + * @{ + */ + +#ifndef _HEAP_H_ +#define _HEAP_H_ + +#ifdef __cplusplus +extern "C" { +#endif + void chHeapInit(void); + void *chHeapAlloc(size_t size); + void chHeapFree(void *p); +#ifdef __cplusplus +} +#endif + +#endif /* _HEAP_H_ */ + +/** @} */ diff --git a/src/include/mempools.h b/src/include/mempools.h index 12edf97fe..2dbf6bf37 100644 --- a/src/include/mempools.h +++ b/src/include/mempools.h @@ -42,6 +42,9 @@ extern "C" { void chPoolInit(MemoryPool *mp, size_t size); void *chPoolAlloc(MemoryPool *mp, bool_t grow); void chPoolFree(MemoryPool *mp, void *objp); +#ifdef CH_USE_HEAP + void chPoolRelease(MemoryPool *mp); +#endif #ifdef __cplusplus } #endif diff --git a/src/kernel.mk b/src/kernel.mk index 1aa60125b..052303e1e 100644 --- a/src/kernel.mk +++ b/src/kernel.mk @@ -6,4 +6,5 @@ KERNSRC = ../../src/chinit.c ../../src/chdebug.c \ ../../src/chsem.c ../../src/chmtx.c \ ../../src/chevents.c ../../src/chmsg.c \ ../../src/chsleep.c ../../src/chqueues.c \ - ../../src/chserial.c ../../src/chmempools.c + ../../src/chserial.c ../../src/chheap.c \ + ../../src/chmempools.c diff --git a/src/templates/chconf.h b/src/templates/chconf.h index d059f3097..65ae9870e 100644 --- a/src/templates/chconf.h +++ b/src/templates/chconf.h @@ -138,6 +138,26 @@ * are included in the kernel.*/ #define CH_USE_SERIAL_HALFDUPLEX +/** Configuration option: if specified then the memory heap allocator APIs + * are included in the kernel.*/ +#define CH_USE_HEAP + +/** Configuration option: Number of RAM bytes to use as system heap. If set to + * zero then the whole available RAM is used as system heap. + * @note In order to use the whole RAM as system heap the linker script must + * provide the \p __heap_base__ and \p __heap_end__ symbols. + * @note requires \p CH_USE_HEAP. + */ +#define CH_HEAP_SIZE 0 + +/** Configuration option: enforces the use of the C-runtime \p malloc() and + * \p free() functions as backend for the system heap allocator.*/ +//#define CH_USE_MALLOC_HEAP + +/** Configuration option: if specified then the memory pools allocator APIs + * are included in the kernel.*/ +#define CH_USE_MEMPOOLS + /** Configuration option: Frequency of the system timer that drives the system * ticks. This also defines the system time unit.*/ #define CH_FREQUENCY 1000 -- cgit v1.2.3