From 74298f8ca11dc8d3b0359d1d4e124d6494c3eeac Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Fri, 10 Apr 2009 01:15:42 +0200 Subject: * digital/avr/modules/usb: - imported LUFA. --- .../usb/lufa/LUFA/MemoryAllocator/DynAlloc.c | 226 +++++++++++++++++++++ .../usb/lufa/LUFA/MemoryAllocator/DynAlloc.h | 182 +++++++++++++++++ 2 files changed, 408 insertions(+) create mode 100644 digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c create mode 100644 digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h (limited to 'digital/avr/modules/usb/lufa/LUFA/MemoryAllocator') diff --git a/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c new file mode 100644 index 00000000..a91e0f35 --- /dev/null +++ b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.c @@ -0,0 +1,226 @@ +/* + LUFA Library + Copyright (C) Dean Camera, 2009. + + dean [at] fourwalledcubicle [dot] com + www.fourwalledcubicle.com +*/ + +/* + Copyright 2009 Dean Camera (dean [at] fourwalledcubicle [dot] com) + + Permission to use, copy, modify, and distribute this software + and its documentation for any purpose and without fee is hereby + granted, provided that the above copyright notice appear in all + copies and that both that the copyright notice and this + permission notice and warranty disclaimer appear in supporting + documentation, and that the name of the author not be used in + advertising or publicity pertaining to distribution of the + software without specific, written prior permission. + + The author disclaim all warranties with regard to this + software, including all implied warranties of merchantability + and fitness. In no event shall the author be liable for any + special, indirect or consequential damages or any damages + whatsoever resulting from loss of use, data or profits, whether + in an action of contract, negligence or other tortious action, + arising out of or in connection with the use or performance of + this software. +*/ + +#define INCLUDE_FROM_DYNALLOC_C +#include "DynAlloc.h" + +struct +{ + char Mem_Heap[NUM_BLOCKS * BLOCK_SIZE]; + void* Mem_Handles[NUM_HANDLES]; + uint8_t Mem_Block_Flags[(NUM_BLOCKS / 4) + ((NUM_BLOCKS % 4) ? 1 : 0)]; + uint8_t FlagMaskLookupMask[4]; + uint8_t FlagMaskLookupNum[4]; +} Mem_MemData = {FlagMaskLookupMask: {(3 << 0), (3 << 2), (3 << 4), (3 << 6)}, + FlagMaskLookupNum: { 0, 2, 4, 6}}; + +static uint8_t Mem_GetBlockFlags(const Block_Number_t BlockNum) +{ + const Block_Number_t BlockIndex = (BlockNum >> 2); + const uint8_t FlagMask = Mem_MemData.FlagMaskLookupMask[BlockNum & 0x03]; + const uint8_t FlagMaskShift = Mem_MemData.FlagMaskLookupNum[BlockNum & 0x03]; + + return ((Mem_MemData.Mem_Block_Flags[BlockIndex] & FlagMask) >> FlagMaskShift); +} + +static void Mem_SetBlockFlags(const Block_Number_t BlockNum, const uint8_t Flags) +{ + const Block_Number_t BlockIndex = (BlockNum >> 2); + const uint8_t FlagMask = Mem_MemData.FlagMaskLookupMask[BlockNum & 0x03]; + const uint8_t FlagMaskShift = Mem_MemData.FlagMaskLookupNum[BlockNum & 0x03]; + + Mem_MemData.Mem_Block_Flags[BlockIndex] &= ~FlagMask; + Mem_MemData.Mem_Block_Flags[BlockIndex] |= (Flags << FlagMaskShift); +} + +static inline void Mem_Defrag(void) +{ + Block_Number_t FreeStartBlock = 0; + char* FreeStartPtr = NULL; + char* UsedStartPtr = NULL; + Block_Number_t CurrBlock; + + for (CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++) + { + if (!(Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK)) + { + FreeStartPtr = &Mem_MemData.Mem_Heap[CurrBlock * BLOCK_SIZE]; + FreeStartBlock = CurrBlock; + break; + } + } + + if (FreeStartPtr == NULL) + return; + + while (++CurrBlock < NUM_BLOCKS) + { + uint8_t CurrBlockFlags = Mem_GetBlockFlags(CurrBlock); + + if (CurrBlockFlags & BLOCK_USED_MASK) + { + UsedStartPtr = &Mem_MemData.Mem_Heap[CurrBlock * BLOCK_SIZE]; + + for (Handle_Number_t HandleNum = 0; HandleNum < NUM_HANDLES; HandleNum++) + { + if (Mem_MemData.Mem_Handles[HandleNum] == UsedStartPtr) + { + Mem_MemData.Mem_Handles[HandleNum] = FreeStartPtr; + break; + } + } + + memcpy(FreeStartPtr, UsedStartPtr, BLOCK_SIZE); + FreeStartPtr += BLOCK_SIZE; + + Mem_SetBlockFlags(FreeStartBlock++, CurrBlockFlags); + Mem_SetBlockFlags(CurrBlock, 0); + } + } +} + +static inline bool Mem_FindFreeBlocks(Block_Number_t* const RetStartPtr, const Block_Number_t Blocks) +{ + Block_Number_t FreeInCurrSec = 0; + + for (Block_Number_t CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++) + { + if (Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK) + FreeInCurrSec = 0; + else + FreeInCurrSec++; + + if (FreeInCurrSec >= Blocks) + { + *RetStartPtr = CurrBlock; + return true; + } + } + + return false; +} + +Mem_Handle_t Mem_Alloc(const Alloc_Size_t Bytes) +{ + Block_Number_t ReqBlocks = (Bytes / BLOCK_SIZE); + Block_Number_t StartBlock; + + if (Bytes % BLOCK_SIZE) + ReqBlocks++; + + if (!(Mem_FindFreeBlocks(&StartBlock, ReqBlocks))) + { + Mem_Defrag(); + + if (!(Mem_FindFreeBlocks(&StartBlock, ReqBlocks))) + return NULL; + } + + for (Block_Number_t UsedBlock = 0; UsedBlock < (ReqBlocks - 1); UsedBlock++) + Mem_SetBlockFlags((StartBlock + UsedBlock), (BLOCK_USED_MASK | BLOCK_LINKED_MASK)); + + Mem_SetBlockFlags((StartBlock + (ReqBlocks - 1)), BLOCK_USED_MASK); + + for (Handle_Number_t AllocEntry = 0; AllocEntry < NUM_HANDLES; AllocEntry++) + { + Mem_Handle_t CurrHdl = (Mem_Handle_t)&Mem_MemData.Mem_Handles[AllocEntry]; + + if (DEREF(CurrHdl, void*) == NULL) + { + DEREF(CurrHdl, void*) = &Mem_MemData.Mem_Heap[StartBlock * BLOCK_SIZE]; + return CurrHdl; + } + } + + return NULL; +} + +Mem_Handle_t Mem_Realloc(Mem_Handle_t CurrAllocHdl, const Alloc_Size_t Bytes) +{ + Mem_Free(CurrAllocHdl); + return Mem_Alloc(Bytes); +} + +Mem_Handle_t Mem_Calloc(const Alloc_Size_t Bytes) +{ + Mem_Handle_t AllocHdl = Mem_Alloc(Bytes); + + if (AllocHdl != NULL) + memset(DEREF(AllocHdl, void*), 0x00, Bytes); + + return AllocHdl; +} + +void Mem_Free(Mem_Handle_t CurrAllocHdl) +{ + char* MemBlockPtr = DEREF(CurrAllocHdl, char*); + Block_Number_t CurrBlock = ((uint16_t)(MemBlockPtr - Mem_MemData.Mem_Heap) / BLOCK_SIZE); + uint8_t CurrBlockFlags; + + if ((CurrAllocHdl == NULL) || (MemBlockPtr == NULL)) + return; + + do + { + CurrBlockFlags = Mem_GetBlockFlags(CurrBlock); + Mem_SetBlockFlags(CurrBlock, 0); + + CurrBlock++; + } + while (CurrBlockFlags & BLOCK_LINKED_MASK); + + DEREF(CurrAllocHdl, void*) = NULL; +} + +Block_Number_t Mem_TotalFreeBlocks(void) +{ + Block_Number_t FreeBlocks = 0; + + for (Block_Number_t CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++) + { + if (!(Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK)) + FreeBlocks++; + } + + return FreeBlocks; +} + +Handle_Number_t Mem_TotalFreeHandles(void) +{ + Handle_Number_t FreeHandles = 0; + + for (Handle_Number_t CurrHandle = 0; CurrHandle < NUM_HANDLES; CurrHandle++) + { + if (Mem_MemData.Mem_Handles[CurrHandle] == NULL) + FreeHandles++; + } + + return FreeHandles; +} diff --git a/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h new file mode 100644 index 00000000..6fd743ea --- /dev/null +++ b/digital/avr/modules/usb/lufa/LUFA/MemoryAllocator/DynAlloc.h @@ -0,0 +1,182 @@ +/* + LUFA Library + Copyright (C) Dean Camera, 2009. + + dean [at] fourwalledcubicle [dot] com + www.fourwalledcubicle.com +*/ + +/* + Copyright 2009 Dean Camera (dean [at] fourwalledcubicle [dot] com) + + Permission to use, copy, modify, and distribute this software + and its documentation for any purpose and without fee is hereby + granted, provided that the above copyright notice appear in all + copies and that both that the copyright notice and this + permission notice and warranty disclaimer appear in supporting + documentation, and that the name of the author not be used in + advertising or publicity pertaining to distribution of the + software without specific, written prior permission. + + The author disclaim all warranties with regard to this + software, including all implied warranties of merchantability + and fitness. In no event shall the author be liable for any + special, indirect or consequential damages or any damages + whatsoever resulting from loss of use, data or profits, whether + in an action of contract, negligence or other tortious action, + arising out of or in connection with the use or performance of + this software. +*/ + +/** \file + * + * Dynamic, auto-defragmenting block memory allocator library. This library provides a convenient replacement for + * the standard avr-libc dynamic memory allocation routines. Memory is handed out in block chunks, to reduce the + * management memory overhead. + * + * Unlike the normal memory allocation routines, this library gives out handles to memory which must be dereferenced + * at the exact time of use, rather than handing back direct memory pointers. By using library managed handles + * instead of pointers, allocated memory blocks can be shifted around as needed transparently to defragment the + * memory as more blocks are requested. + * + * The memory heap is static, thus the total memory usage of the compiled application (as reported by the avr-size + * tool of the AVR-GCC toolchain) includes the dynamic memory heap. + * + * The constants NUM_BLOCKS, BLOCK_SIZE and NUM_HANDLES must be defined in the project makefile (and passed to the + * preprocessor via the -D GCC switch) for this library to compile. + * + * NUM_BLOCKS indicates the number of memory blocks in the memory psudoheap which can be chaned together and handed + * to the application via a memory handle. NUM_HANDLES is the maximum number of memory handles (pointing to one or + * more chained memory blocks) which can be handed out simultaneously before requring a handle (and its associated + * memory) to be freed. BLOCK_SIZE gives the number of bytes in each memory block. + */ + +#ifndef __DYN_ALLOC__ +#define __DYN_ALLOC__ + + /* Includes : */ + #include + #include + #include + + /* Preprocessor Checks: */ + #if (!defined(NUM_BLOCKS) || !defined(BLOCK_SIZE) || !defined(NUM_HANDLES)) + #error NUM_BLOCKS, BLOCK_SIZE and NUM_HANDLES must be defined before use via makefile. + #endif + + /* Public Interface - May be used in end-application: */ + /* Macros: */ + /** Macro to dereference a given memory handle into the given type. The given type should be a pointer + * if the memory is to contain an array of items, or should be a standard type (such as a primative or + * structure) if the memory is to hold a single item of a single type. */ + #define DEREF(handle, type) (*(type*)handle) + + /** Constant, giving the total heap size in bytes. */ + #define ALLOCABLE_BYTES (1UL * NUM_BLOCKS * BLOCK_SIZE) + + /* Type Defines: */ + /** Memory handle type, used to store handles given by the library functions. */ + typedef const void** Mem_Handle_t; + + #if (ALLOCABLE_BYTES > 0xFFFF) || defined(__DOXYGEN__) + /** Type define for the size (in bytes) for an allocation for passing to the library functions. + * The exact type width varies depending on the value of ALLOCABLE_BYTES to ensure that a single + * allocation can request the entire heap if needed. + */ + typedef uint32_t Alloc_Size_t; + #elif (ALLOCABLE_BYTES > 0xFF) + typedef uint16_t Alloc_Size_t; + #else + typedef uint8_t Alloc_Size_t; + #endif + + #if (NUM_BLOCKS > 0xFFFF) || defined(__DOXYGEN__) + /** Type define for a block number in the heap. The exact type width varies depending on the + * value of NUM_BLOCKS to ensure that the type can store an index to any block in the block pool. + */ + typedef uint32_t Block_Number_t; + #elif (NUM_BLOCKS > 0xFF) + typedef uint16_t Block_Number_t; + #else + typedef uint8_t Block_Number_t; + #endif + + #if (NUM_HANDLES > 0xFFFF) || defined(__DOXYGEN__) + /** Type define for a handle number. The exact type width varies depending on the value of NUM_HANDLES + * to ensure that the type can store the index of any handle in the handle pool. + */ + typedef uint32_t Handle_Number_t; + #elif (NUM_HANDLES > 0xFF) + typedef uint16_t Handle_Number_t; + #else + typedef uint8_t Handle_Number_t; + #endif + + /* Function Prototypes: */ + /** Allocates a given number of blocks from the heap (calculated from the requested number of bytes) and + * returns a handle to the newly allocated memory. + * + * \param Bytes The number of bytes requested to be allocated from the heap + * + * \return NULL handle if the allocation fails, or handle to the allocated memory if the allocation succeeds + */ + Mem_Handle_t Mem_Alloc(const Alloc_Size_t Bytes); + + /** Allocates a given number of blocks from the heap (calculated from the requested number of bytes) and + * returns a handle to the newly allocated memory. Calloced memory is automatically cleared to all 0x00 + * values at the time of allocation. + * + * \param Bytes The number of pre-cleared bytes requested to be allocated from the heap + * + * \return NULL handle if the allocation fails, or handle to the allocated memory if the allocation succeeds + */ + Mem_Handle_t Mem_Calloc(const Alloc_Size_t Bytes); + + /** Deallocates a given memory handle, and attempts to allocates the given number of blocks from the heap + * (calculated from the requested number of bytes) immediately following the deallocation. The new memory + * may be located in the same area as the previous memory, but this is not guaranteed. + * + * \param CurrAllocHdl Handle to an already allocated section of memory in the heap to deallocate + * \param Bytes The number of bytes requested to be allocated from the heap following the + * deallocation + * + * \return NULL handle if the allocation fails, or handle to the allocated memory if the allocation succeeds + * + * \warning Even if the allocation fails, the deallocation will still occur. Care should be taken to ensure + * that the previously allocated memory is not used following an unsuccessful realloc(). + */ + Mem_Handle_t Mem_Realloc(Mem_Handle_t CurrAllocHdl, const Alloc_Size_t Bytes); + + /** Deallocates a given previously allocated section of memory from the heap. + * + * \param CurrAllocHdl Handle to a previously allocated section of memory in the heap + */ + void Mem_Free(Mem_Handle_t CurrAllocHdl); + + /** Returns the total number of unallocated blocks in the heap. + * + * \return Number of free blocks in the heap, as a Block_Number_t integer + */ + Block_Number_t Mem_TotalFreeBlocks(void); + + /** Returns the total number of unallocated handles in the handle pool. + * + * \return Number of free handles in the handle pool, as a Handle_Number_t integer + */ + Handle_Number_t Mem_TotalFreeHandles(void); + + /* Private Interface - For use in library only: */ + #if !defined(__DOXYGEN__) + /* Macros: */ + #define BLOCK_USED_MASK (1 << 0) + #define BLOCK_LINKED_MASK (1 << 1) + + /* Function Prototypes: */ + #if defined(INCLUDE_FROM_DYNALLOC_C) + static uint8_t Mem_GetBlockFlags(const Block_Number_t BlockNum); + static void Mem_SetBlockFlags(const Block_Number_t BlockNum, const uint8_t Flags); + static void Mem_Defrag(void); + #endif + #endif + +#endif -- cgit v1.2.3