about the heap:

[Sergei Organov]

How interesting that multiple people are digging in the same direction
simultaneously: I've just re-implemented the heap manager ;) I'm curious
why are you interested in the heap implementation -- maybe you can wait for
mine to be incorporated into the RTEMS and I can try to solve your problems
(if any) in my implementation.

"Bert"<doclzs at 21cn.com> writes:
> (1) what is the structure of the heap?

The structure described in the 'heap.c' is more correct than youth.

[... skipped diagrams ...]

> 
> (2)
> #define HEAP_OVERHEAD (sizeof( unsigned32 ) * 2)
> #define HEAP_BLOCK_USED_OVERHEAD (sizeof( void * ) * 2)
> #define HEAP_MINIMUM_SIZE (HEAP_OVERHEAD + sizeof (Heap_Block))
> 
> it said that "free block overhead is greater than used
>  block overhead". Why?

Because 'next' and 'previous' fields are used by the heap manager only in free
blocks, and in used blocks they are part of the user accessible area. However,
HEAP_BLOCK_USED_OVERHEAD has wrong definition, it should be
sizeof(unsigned32)*2, not sizeof(void*)*2 -- it's just luck that it works (due
to 32-bit pointers).

In my implementation used block overhead is even smaller -- only one word
instead of two in the current implementation.

> 
> (3)
> typedef struct {
>   Heap_Block *start;
>   Heap_Block *final;
>   Heap_Block *first;
>   Heap_Block *permanent_null;
>   Heap_Block *last;
>   unsigned32  page_size;
>   unsigned32  reserved;
> }   Heap_Control;
> 
> Is "start" not the same as "first" and "final" not the same as "last"? if
> not, what are the meanings of "start" and "final"? and the relation between
> "first" "last" "start" "final"?

Actually, the structure above is messy. That's how I'd reorganize it for
intention to be more clear:

typedef struct {
  /* Begin of Heap_Block - alike part */
  unsigned32  page_size;   /* allocation unit and alignment */
  unsigned32  reserved;         
  Heap_Block *first;       /* pointer to the first free block in the heap */
  Heap_Block *permanent_null;
  Heap_Block *last;        /* pointer to the last free block in the heap */
  /* End of Heap_Block - alike part */
  Heap_Block *start;       /* first valid block address in the heap */
  Heap_Block *final;       /* last valid block address in the heap */
} Heap_Control;

'start' and 'final' fields are in fact used only to check if a given address
belongs to the heap, i.e. addresses are checked to be within [start, final]
range.

The first part of the struct is tricky and IMHO unnecessary tricky. Anyway, it
still has problems as it would work only for architectures with 32-bit
pointers, so in my implementation I've changed it as well.

-- 
Sergei.