Heap Management

[ChristianF]

So now I got something like this:
At the beginning I have a tree for the free Memory. This means, that I create a node which has e.g. 1MB (if max. Heap Memory is 1MB). When I allocate something, I subtract the wanted size, e.g. 4 Byte, and create a new node in the tree for the used memory. If there are now several nodes, and one is freed, I take it out of the tree for the used and insert it in the list for the free blocks. After Inserting this block I have to search for a block is directly behind.
For Example I insert a node with the address 0xD0010123 and has a size of 4 Bytes I look for a node with the address "address+size" IIRC. 0xD0010127. If there is a node with this address, I delete that node and add the size of the deleted block to the size of the just inserted.

Cheers Christian

[ChristianF]

Hmmm...
My tree is working right there. But there is a little problem within the macro for getting the address of the memory block.
The Macro is defined like this:

Code: Select all

#define GET_MEM_BLOCK_ADDRESS(node_address) \
	((unsigned char *)node_address - (int)&((heap_mem_block_t*)NULL)->node)

The comparison function looks like this:

Code: Select all

int avl_compare_heap_block_address(avl_node_t *node_a, avl_node_t *node_b)
{
	heap_mem_block_t *mem_block1 = (heap_mem_block_t *)GET_MEM_BLOCK_ADDRESS(node_a);
	heap_mem_block_t *mem_block2 = (heap_mem_block_t *)GET_MEM_BLOCK_ADDRESS(node_b);
	return( (mem_block1->address > mem_block2->address) ? -1 : (mem_block1->address < mem_block2->address) ? 1 : 0 );
}

The comparison function seems to be okay, but GET_MEM_BLOCK_ADDRESS calculates a wrong address so my search function don't find a block in the tree.
I hope someone could help me, because I don't see, what is wrong.


Cheers Christian

[ru2aqare]

I have no idea why it doesn't work, because it looks correct to me... Have you tried writing a simple test function like

Code: Select all

void test()
{
   heap_mem_block_t block;
   // not initialized - we need its address only.
   printf("addr of block is %p\n", &block);
   
   // get a pointer to a node structure.
   avl_node_t* p = &block.node;
   heap_mem_block_t* q = GET_MEM_BLOCK_ADDRESS(p);
   // check what the macro returns. it should match the previously printed value...
   printf("macro says its %p\n", q);
}

If this prints the same values, then the macro works fine, and the bug is elsewhere.

[ChristianF]

Mmmhhh...
I have written a function like this:

Code: Select all

void test_macro(void)
{
    heap_mem_block_t block;
    avl_node_t node;

    printf("address of block = 0x%x\n", &block);
    printf("address of node = 0x%x\n", &node);
    block.node = &node;
    printf("GET_MEM_BLOCK_ADDRESS(&node) = 0x%x\n", GET_MEM_BLOCK_ADDRESS(&node));
}

And here is what it prints on screen:

address of block = 0xc010bcb4
address of node = 0xc010bca0
GET_MEM_BLOCK_ADDRESS(&node) = 0xc010bc98

It seems to be that the offset is wrong.
I will have a look tomorrow, it's to late right now.

[ru2aqare]

I figured your issue from this:

Code: Select all

...
    block.node = &node;

And then I checked the previous page to see your heap_mem_block structure...

Code: Select all

typedef struct heap_mem_block
{
   ...
   avl_node_t *node;
} heap_mem_block_t;

The macro would only work if the avl_node_t structure was embedded inside the container heap_mem_block structure, like this:

Code: Select all

typedef struct heap_mem_block
{
   ...
   avl_node_t node; // NOT a pointer. structure is embedded inside the container.
} heap_mem_block_t;

... which is not the case. In your case, the avl_node_t structure actually occupies a different and not overlapping region of memory. To get to the parent structure, you would need a pointer inside the avl_node_t structure... Which kind of defeats the purpose of embedding the AVL node structure inside its container.

To put it in other words, my AVL and memory allocation code has structures like this:

Code: Select all

 pointer
   |
   v
   +-----------+---------------------+
   |  AVL node |   heap block header |
   +-----------+---------------------+

whereas your example has structures like this:

Code: Select all

 pointer
   |
   v
   +-------------------+---------------------+
   | heap block header | pointer to AVL node |
   +-------------------+---------------------+
                                        |
                                        v
                                 +-----------+
                                 | AVL node  |
                                 +-----------+

[ChristianF]

Mmmhhh...
that is right and I didn't see that.
And I see now that it is needed to set the node structure at the beginning of the memory block. Using a normal variable instead of a pointer simplifies very much. Thank you for the help. I will try it later when I finished working.

[ru2aqare]

Mmmhhh...
that is right and I didn't see that.
And I see now that it is needed to set the node structure at the beginning of the memory block. Using a normal variable instead of a pointer simplifies very much. Thank you for the help. I will try it later when I finished working.

It is not strictly required to move the node structure to the start of the container structure, as long as you use the macro to get the address of the container structure. However, it may save one or two instructions, so the code runs a tiny little bit faster.

The point of embedding the AVL node inside the memory block header was that it makes the need for a back-pointer from the AVL node to the memory block header unnecessary, also you don't have to allocate a separate memory block for the memory block header itself.

[ChristianF]

Good Morning from Germany.
It works well. At least I have to recheck and may be rewrite the code for searching a free place in heap, but this is not a problem.
I am thinking about creating on big node in the tree for free elements right after the initialisation of the heap...

Thanks for all the help and patience.
Cheers Christian