| Author |
Message |
|
|
 Posted: Dec 23, 2007 - 11:07 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
Hi guys,
Just posting a snippet of code here in case anyone wants to make use of it, or can suggest improvements.
It's called DynAlloc, and is essentially my own version of malloc and free, using an algorithm I dreamed up while on a car ride. It's probably not how the real malloc/free work, but it's slightly smaller.
It works by dividing up a large statically allocated "heap" into a number of equally sized, small blocks. Each one of these blocks can be set as used or (in the case of chains of blocks) linked to the next contiguous block.
When a number of bytes are requested, the number is padded out to the smallest number of blocks that can satisfy the required size. It them hunts through the block list, searching for the exact number of contiguous free blocks. Failing that, it then searches for one larger than the required number of blocks, then two, and so on. In this manner, the smallest contiguous number of blocks that can fit the requested byte size is used, reducing fragmentation.
This is more of an academic exercise than anything truly useful, but I welcome all improvements and discussion.
Memory overhead is eight bytes, plus two bits per block, aligned to the nearest byte. This results in 34 bytes of overhead when using 100 blocks of 8 bytes (800 byte heap), as the code does now.
DynAlloc.h
Code:
/*
Dynamic Allocation Library
(C) Dean Camera, 2007
www.fourwalledcubicle.com
*/
#ifndef __DYN_ALLOC__
#define __DYN_ALLOC__
/* Includes : */
#include <avr/io.h>
#include <stdio.h>
#include <stdbool.h>
/* Macros: */
#define NUM_BLOCKS 100
#define BLOCK_SIZE 8
#define BLOCK_USED_MASK (1 << 0)
#define BLOCK_LINKED_MASK (1 << 1)
/* Function Prototypes: */
void* Mem_Calloc(const uint16_t Bytes);
void* Mem_Realloc(void* CurrAllocPtr, const uint16_t Bytes);
void* Mem_Alloc(const uint16_t Bytes);
void Mem_Free(void* MemPtr);
#endif
DynAlloc.c
Code:
/*
Dynamic Allocation Library
(C) Dean Camera, 2007
www.fourwalledcubicle.com
*/
#include "DynAlloc.h"
struct
{
char Mem_Heap[NUM_BLOCKS * BLOCK_SIZE];
uint8_t Mem_Block_Flags[(NUM_BLOCKS / 4) + 1];
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 uint8_t BlockNum)
{
const uint8_t BlockIndex = (BlockNum / 4);
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 uint8_t BlockNum, const uint8_t Flags)
{
const uint8_t BlockIndex = (BlockNum / 4);
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);
}
void* Mem_Realloc(void* CurrAllocPtr, const uint16_t Bytes)
{
Mem_Free(CurrAllocPtr);
return Mem_Alloc(Bytes);
}
void* Mem_Calloc(const uint16_t Bytes)
{
char* AllocPtr = Mem_Alloc(Bytes);
if (AllocPtr != NULL)
{
char* ClearPtr = AllocPtr;
for (uint16_t ClearPos = 0; ClearPos < Bytes; ClearPos++)
*(ClearPtr++) = 0x00;
}
return AllocPtr;
}
void* Mem_Alloc(const uint16_t Bytes)
{
uint8_t ReqBlocks = (Bytes / BLOCK_SIZE);
if (Bytes % BLOCK_SIZE)
ReqBlocks++;
for (uint8_t SearchBlockSize = ReqBlocks; SearchBlockSize < NUM_BLOCKS; SearchBlockSize++)
{
uint8_t FreeInCurrSec = 0;
uint8_t StartOfFree = 0;
char* StartOfFreePtr = NULL;
bool FoundStart = false;
for (uint8_t CurrBlock = 0; CurrBlock < NUM_BLOCKS; CurrBlock++)
{
if (!(FoundStart) && !(Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK))
{
StartOfFreePtr = &Mem_MemData.Mem_Heap[CurrBlock * BLOCK_SIZE];
StartOfFree = CurrBlock;
FreeInCurrSec = 0;
FoundStart = true;
}
if (FoundStart)
{
if (!(Mem_GetBlockFlags(CurrBlock) & BLOCK_USED_MASK))
FreeInCurrSec++;
else
FoundStart = false;
if (FreeInCurrSec == SearchBlockSize)
{
for (uint8_t UsedBlock = 0; UsedBlock < SearchBlockSize; UsedBlock++)
Mem_SetBlockFlags((StartOfFree + UsedBlock), BLOCK_USED_MASK | BLOCK_LINKED_MASK);
Mem_SetBlockFlags(((StartOfFree + SearchBlockSize) - 1), BLOCK_USED_MASK);
return StartOfFreePtr;
}
}
}
}
return NULL;
}
void Mem_Free(void* MemPtr)
{
if (MemPtr == NULL)
return;
uint8_t CurrBlock = ((uint16_t)((char*)MemPtr - Mem_MemData.Mem_Heap) / BLOCK_SIZE);
uint8_t CurrBlockFlags;
do
{
CurrBlockFlags = Mem_GetBlockFlags(CurrBlock);
Mem_SetBlockFlags(CurrBlock, 0);
CurrBlock++;
}
while (CurrBlockFlags & BLOCK_LINKED_MASK);
}
EDIT: Updated code with Realloc and Calloc. Made slightly smaller.
- Dean  |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 23, 2007 - 03:19 PM |
|
Joined: Dec 20, 2002
Posts: 6697
Location: Dresden, Germany
|
|
Well, I wouldn't mind offering a second implementation of
malloc/free as part of avr-libc. Unlike with the vfprintf
switch, switching mallocs can be made even easier because
the function is always called directly, so there could be
a macro-based switch. Say, if you define a certain macro
before including stdlib.h, you select an alternate implementation:
Code:
#define __USE_BLOCK_MALLOC
#include <stdio.h>
As you're using a user-defined heap, the user would have to take
care of supplying the heap array himself.
What's probably needed to compare both implementations is to
have some kind of test suite script that judges not only memory
consumption but also things like fragmentation, RAM overhead
etc. |
_________________
Jörg Wunsch
Please don't send me PMs, use email instead.
Please read the `General information...' article before.
|
| |
|
|
|
|
|
|
Posted: Dec 23, 2007 - 10:51 PM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
|
Quote:
What's probably needed to compare both implementations is to
have some kind of test suite script that judges not only memory
consumption but also things like fragmentation, RAM overhead
etc.
I'm certainly not against putting it into avr-lib-c. This was just "one of those things" I dreamed up while riding in the car and had to program out when I got home.
How would I go about making such a suite? I could easily check the ram/flash usage, but the fragmentation would be harder.
In theory, this should be very low fragmentation, as the most-exact sized hole should be allocated each time - if you need 3 blocks, and there's a 10 blocks at the start of memory, the code will try to find a three (then four, then five, etc.) block hole before using the larger holes. It also helps that the memory is in blocks rather than bytes, so the holes are always a multiple of BLOCK_SIZE in size.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 23, 2007 - 10:54 PM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
|
Quote:
As you're using a user-defined heap, the user would have to take
care of supplying the heap array himself.
A user-defined heap is easier to keep track of, and means that the total memory usage for an app (excluding stack) is shown at compile time. I actually tried to use __heap_start, but kept getting an undefined error. What file gives the extern declaration for the __heap_start symbol?
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 24, 2007 - 12:45 AM |
|
Joined: Dec 20, 2002
Posts: 6697
Location: Dresden, Germany
|
|
> What file gives the extern declaration for the __heap_start symbol?
None, you have to declare it yourself. The symbol is inserted by the
linker.
You can have a look at the existing implementation for that.
The point with fragmentation isn't such an easy case. Say, someone
initially allocates objects so you are handing out 6 successive blocks.
Then, he comes along, and frees every other of them. In theory, you've
now got three free blocks again. However, next time he comes along, and
allocates a couple of objects that are just one byte larger than your
block size, so you have to allocate two consecutive blocks -- but you
cannot re-use the already freed blocks for that, and have to use new
ones.
This is usually what embedded developers are most fearing of when thinking
about dynamic memory allocation. |
_________________
Jörg Wunsch
Please don't send me PMs, use email instead.
Please read the `General information...' article before.
|
| |
|
|
|
|
|
|
Posted: Dec 24, 2007 - 12:54 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
Yes - that case isn't handled by the above code. However, it should still reduce the fragmentation by always choosing the best sized memory hole for allocations.
I'm currently working on the defragmenting allocation library. It uses a seperate allocation table which must be dereferenced when used so that the already-allocated blocks can be shuffled around. The end-user code would be something like this:
Code:
#include <avr/io.h>
#include "DynAlloc.h"
int main (void)
{
char** MyMem1 = (char**)Mem_Alloc(20);
char** MyMem2 = (char**)Mem_Alloc(20);
char** MyMem3 = (char**)Mem_Alloc(20);
(*MyMem1)[0] = 1;
(*MyMem2)[0] = 2;
(*MyMem3)[0] = 3;
MyMem1 = (char**)Mem_Realloc(MyMem1, 4);
(*MyMem1)[0] = 4;
Mem_Free(MyMem2);
MyMem2 = (char**)Mem_Alloc(4);
(*MyMem2)[0] = 5;
}
The library would take care of defragging the blocks (and updating the allocation table) if the first allocation attempt fails.
Would something like this be useful if I can get it to fit in well under 1KB or so?
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 24, 2007 - 01:45 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
All done, in 714 bytes for all functions - malloc(), calloc(), free() and realloc() (plus internal Mem_Defrag(), Mem_GetBlockFlags() and Mem_SetBlockFlags()). You do have to double-dereference when in use, but it auto-defragments when needed.
Attached is the latest code. I tested it with the following example:
Code:
int main (void)
{
char** MyMem1 = (char**)Mem_Alloc(BLOCK_SIZE);
char** MyMem2 = (char**)Mem_Alloc(BLOCK_SIZE);
char** MyMem3 = (char**)Mem_Alloc(BLOCK_SIZE);
(*MyMem1)[0] = 1;
(*MyMem2)[0] = 2;
(*MyMem3)[0] = 3;
MyMem1 = (char**)Mem_Realloc(MyMem1, BLOCK_SIZE * 2);
if (MyMem1 == NULL)
{
PORTC = 0xFF;
}
else
{
PORTC = 0x0F;
(*MyMem1)[0] = 4;
}
(*MyMem2)[0] = 22;
(*MyMem3)[0] = 33;
(*MyMem1)[0] = 44;
}
Which, when the library was set to only have four available blocks, caused the existing allocated blocks to be defragged to the start of memory before the larger block (which couldn't fit before) was allocated. The updated locations' memory was also changed, showing that the allocation table works just fine.
Needs some size/speed tweaks, but it's a great starting point.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 26, 2007 - 04:31 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
Joerg, are there any quality modifications I have to do before this could be submitted as a patch to the avr-lib-c project? I think an auto-defragmenting dynalloc library could be of use to users.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 26, 2007 - 08:16 AM |
|
Joined: Dec 20, 2002
Posts: 6697
Location: Dresden, Germany
|
|
> However, it should still reduce the fragmentation by always
> choosing the best sized memory hole for allocations.
I'm not sure I understand that sentence correctly. The standard malloc()
picks an exact-size hole first. Failing that, it picks the first chunk
that would have just enough memory to fulfill the request. Only after
that, it would go ahead, and allocate a new block.
> You do have to double-dereference when in use, but it auto-defragments when needed.
I think there are a number of libraries around doing that. Alas (unless
I completely misunderstood you), this is not compatible with the way malloc()
is used in C programs, as pointers that are in use are completely untrackable
by the library, so you're no longer API compatible.
> Joerg, are there any quality modifications I have to do before this could
> be submitted as a patch to the avr-lib-c project?
- a switch to flip between both implementation (like the macro one I suggested)
- doxygen documentation, even if you don't want to build it yourself. As the
current malloc() has an own chapter about its implementation details in addition
to the plain reference manual, this chapter needs to be extended so it at least
mentions both implementation. Ideally, it should also explain the internals of
the alternate implementation.
- test scripts (for the new test script framework) would be really helpful.
But that will only work if it's a true API compatible replacement. |
_________________
Jörg Wunsch
Please don't send me PMs, use email instead.
Please read the `General information...' article before.
|
| |
|
|
|
|
|
|
Posted: Dec 26, 2007 - 09:47 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
Ok, never mind then, I'll keep it as a seperate download on my site.
I've no idea how the real malloc works, so how I've done it is what I think is most logical. My code looks for an exact-sized hole first, then a hole one block larger than required, then two blocks, and so on. If a suitable space can't be found, it does a defragment and tries again.
To be able to defragment, it has to keep an allocation table of where each block segment starts. That's the reason behind the double-dereference -- once to get to the entry in the allocation table, and again to get to the current start location for the block. Non standard to be sure, but works quite well.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 26, 2007 - 07:22 PM |
|
Joined: Dec 30, 2005
Posts: 2093
Location: Longmont, CO USA
|
|
|
abcminiuser wrote:
To be able to defragment, it has to keep an allocation table of where each block segment starts.
And how do you fix all the C pointers to memory you've allocated? Once your routine hands the memory chunk back to the calling code, you have no control over how that pointer gets used, copied, deleted, or whatever.
Example:
Code:
typedef struct _linklist {
struct _linklist* forward;
struct _liunklist* backward;
char data[4];
} LinkType;
int main()
{
LinkType* MyMem1 = (LinkType*) Mem_Alloc( sizeof( LinkType ) );
LinkType* MyMem2 = (LinkType*) Mem_Alloc( sizeof( LinkType ) );
LinkType* MyMem3 = (LinkType*) Mem_Alloc( sizeof( LinkType ) );
/* link all three chunks together */
MyMem1->forward = MyMem2;
MyMem1->backward = MyMem3;
MyMem2->forward = MyMem3;
MyMem2->backward = MyMem1;
MyMem3->forward = MyMem1;
MyMem3->backward = MyMem2;
MyMem1->data[0] = 1;
MyMem2->data[0] = 2;
MyMem3->data[0] = 3;
MyMem1 = (LinkType) Mem_Realloc( MyMem1, BLOCK_SIZE * 2 );
if (MyMem1 == NULL)
{
PORTC = 0xFF;
}
else
{
PORTC = 0x0F;
(*MyMem1)[0] = 4;
}
MyMem2->data[0] = 22;
MyMem3->data[0] = 33;
MyMem1->data[0] = 44;
}
In the above example, the C code out of your control has used the pointers to memory and placed them where you "can't" find them (well, you can, but only if you're pretty smart). If your Realloc tries to move memory segments, most likely the linked list will break.
True, you can "rejoin" freed blocks that happen to reside next to one another, but in above example you would not be able to do that. Also, since you are allocating your blocks in equal sized chunks, you tend to get the rejoin ("coelesce"?) for free. 
This is called "garbage collection", and the problem has a long and honored history.
Overall, there is nothing wrong with your algorithm. It's actually a simpler version of the Linux kernel memory allocator.
Stu |
_________________
Engineering seems to boil down to: Cheap. Fast. Good. Choose two. Sometimes choose only one.
(My boss always chooses Cheap. Twice.)
|
| |
|
|
|
|
|
|
Posted: Dec 26, 2007 - 08:26 PM |
|
Joined: Jul 25, 2001
Posts: 322
Location: Few feet away from a grunting watercooled ATMEGA aware of imminant detonation.
|
|
[thinking out loud]
A memory defragging Re-alloc would be interresting.
MemDefrag(pointer1, size1, pointer2, size2, pointer3, size3)
Given the 3 or less/more pointers, the defragger can start flipping allocation possitions till everything is snuggly again. Without destroying memory contents!!
example:
pointer 1 = 3 bytes
pointer 2 is 2 bytes
pointer 3 is 1 bytes
relative position to heapstart:
Code:
before:
address
other[000]
...
[049]
ptr2 [050] 'v'
[051] 'e'
ptr3 [052] 'u'
ptr1 [100] 'i'
[101] 'l'
[102] 'o'
-------------
after:
other[000]
...
[049]
ptr1 [050] 'i'
[051] 'l'
[052] 'o'
ptr2 [053] 'v'
[054] 'e'
ptr3 [055] 'u'
[/thinking out loud] |
_________________
MY MICROCONTROLLER CAN BEAT THE HELL OUT OF YOUR MICROCONTROLLER /ATMEL
|
| |
|
|
|
|
|
|
Posted: Dec 27, 2007 - 12:17 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
|
Quote:
nd how do you fix all the C pointers to memory you've allocated? Once your routine hands the memory chunk back to the calling code, you have no control over how that pointer gets used, copied, deleted, or whatever.
Hence why it needs double-dereference to use the memory. What you get back is *not* a direct pointer to the allocated blocks, as it would be impossible to keep track of as you say and update the pointers. Instead, it points to a static entry in a seperate table I call the allocation table, which points to the memory. One dereference gets you to the pointer to the block start in the allocation table, another dereference gets you to the actual data start.
When defragmenting, the code squishes up all the allocated blocks next to one another, and updates the old values in the allocation table with the new location. Now, next time you dereference the pointer once in your code you're now pointing to the new data location, rather than the old.
The extra-step of indirection allows the memory manager to retain control over where the app is putting it's data. It does work and it does defragment correctly. I think I'll knock up a diagram to show how it works.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 27, 2007 - 12:38 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
Ok, here's a diagram of the sections of DynAlloc. From it, you can see how the degragmentation works, and how the app is able to keep track of the current data locations in the heap.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 27, 2007 - 02:37 PM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
I should mention the crux of the design - the allocation table isn't defragmented along with the main memory, so pointers to it remain valid. The pointer locations *in* the table, however, do get updated. When a block is freed, the associated allocation table entry is cleared to NULL.
During allocation, the first NULL entry in the allocation table is used to store the pointer to the starting memory block.
Attached is the updated code, with improved clarity and bugfixes.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 27, 2007 - 06:03 PM |
|
Joined: Dec 20, 2002
Posts: 6697
Location: Dresden, Germany
|
|
ISTR this is usually called a "handle based" memory allocator. Instead
of returning a pointer, you return a handle to the caller. This is an
opaque thing the user cannot use directly. Instead, when they want to
use it, they have to apply some kind of `use it' operator -- which could
be a simple dereference as in your case. Still, I'd say you'd better
supply a macro that performs the actual handle->pointer translation,
say
Code:
#define DEREF(handle) (*(handle))
The pointers obtained by DEREF() are by definition only valid until
another allocator operation (allocation/deallocation) is performed,
and have to be re-obtained afterwards (i.e. the users must not cache
them).
I don't think it were not useful, but it's simply another piece of cake
than a standard malloc()/free(). |
_________________
Jörg Wunsch
Please don't send me PMs, use email instead.
Please read the `General information...' article before.
|
| |
|
|
|
|
|
|
Posted: Dec 27, 2007 - 06:57 PM |
|
Joined: Dec 20, 2002
Posts: 6697
Location: Dresden, Germany
|
|
Btw., even better:
Code:
#define DEREF(handle, type) ((type)*(handle))
So you can e.g. use it like
Code:
DEREF(mhandle1, struct foo_t *)->foo_ele = ...;
|
_________________
Jörg Wunsch
Please don't send me PMs, use email instead.
Please read the `General information...' article before.
|
| |
|
|
|
|
|
|
Posted: Dec 28, 2007 - 02:22 AM |
|
Joined: Jan 23, 2004
Posts: 7014
Location: Melbourne, Victoria, Australia
|
|
|
Quote:
The pointers obtained by DEREF() are by definition only valid until
another allocator operation (allocation/deallocation) is performed,
and have to be re-obtained afterwards (i.e. the users must not cache
them).
Exactly how it has to be - defragmenting changes the pointer the handle points to, but not the handle itself.
I've changed the code (both code improvement and fixes), and it now passes the minimal test case. Here is a sample program, which works fine with four blocks and three handles:
Code:
#include "DynAlloc.h"
int main (void)
{
Mem_AllocPtr_t MyMem1 = Mem_Alloc(BLOCK_SIZE);
Mem_AllocPtr_t MyMem2 = Mem_Alloc(BLOCK_SIZE);
Mem_AllocPtr_t MyMem3 = Mem_Alloc(BLOCK_SIZE);
DEREF(MyMem1, char*)[0] = 1;
DEREF(MyMem2, char*)[0] = 2;
DEREF(MyMem3, char*)[0] = 3;
MyMem1 = Mem_Realloc(MyMem1, BLOCK_SIZE * 2);
if (MyMem1 == NULL)
{
PORTC = 0xFF;
for (;;);
}
else
{
PORTC = 0x0F;
DEREF(MyMem1, char*)[0] = 4;
}
DEREF(MyMem2, char*)[1] = 1;
DEREF(MyMem3, char*)[1] = 2;
DEREF(MyMem1, char*)[1] = 3;
}
Attached is the latest version, this sample included.
If you think it would be a valuable contribution to avr-lib-c, and won't take a year to add like my last patches, I'd be happy to make it suitable for inclusion.
- Dean |
_________________
|
| |
|
|
|
|
|
|
Posted: Dec 28, 2007 - 09:29 AM |
|
Joined: Dec 20, 2002
Posts: 6697
Location: Dresden, Germany
|
|
Alas, avr-libc aims to mainly/only be a (C) standard library. We've
been contemplating shipping a "useful things" library as an add-on for
years, and I'd see it as a good thing for such a library. We've got
other ideas around for such a library as well, but too little time to
really start such a project. Maybe you're willing to become the head
of such a project?
The basic idea is to ship a well-maintained, fairly universal set of
library functions that are useful, but go quite beyond the scope of
avr-libc itself. As avr-libc got a good reputation for its
maintenance state, the idea was to suggest to the users that such a
library is maintained by "essentially the same people" as avr-libc,
i.e. users would mentally consider it something like an avr-libc
"add-on". The goal would also be to ship it under the very same
license as avr-libc itself, as this is known to be generally
acceptable to both hobbyist as well as commercial embedded developers.
This is one of the differences to Pascal Stang's AVRlib which is GPLed
and thus not acceptable to some embedded developers. (Also, from
reading several forum threads, I've got my doubts about the
maintenance state of AVRlib, the pace they adopt new AVR devices etc.)
Such a project could even be maintained inside the same project area
on savannah.nongnu.org as avr-libc is, but I'd really like to make it
a separate "product", i.e. with separate releases, maybe a different
documentation tool (but we could also use doxygen if we want).
If you're interested, we could discuss that on the avr-libc-dev mailing
list. |
_________________
Jörg Wunsch
Please don't send me PMs, use email instead.
Please read the `General information...' article before.
|
| |
|
|
|
|
|
|
Posted: Dec 28, 2007 - 09:01 PM |
|
Joined: Jul 08, 2006
Posts: 504
Location: Sunnyvale, CA
|
|
'Nother idea.
Back in the dark ages (late 1970's) I had to write a heap allocator with simple defragmenter as an undergraduate homework. We were given a design where each allocated block had a header that consisted of an "allocated" flag and a length. malloc() returned an address that was just beyond the header. When a block was free()'d, you could reconstruct the pointer to the allocation block to pick up the header record. From there, you could compute the distance to the next higher neighbor and check it's allocated bit. If it was free, the two blocks were consolidated.
I'm pretty fuzzy on how next lower neighbors got consolidated. I believe that all the free blocks were threaded together on a link list that was kept sorted in memory order, so you could easily walk the list from the beginning to do a full consolidation. There was a minimum allocation size to allow room for the header and free list data structures.
-dave |
|
|
| |
|
|
|
|
|
|
FAQ •
Search •
Register •
Log in to check your private messages
Log in
• 
Minimize
• 
RSS
