Well, I'm just finishing up the conversion to using dynamically allocated memory using the Contiki managed memory library. It took a bit longer than
I expected because the memory handling is part of the stack framework and is used in many places. Changing the memory handling while keeping the stack behavior the same was a bit of a challenge. However it's pretty much  finished and the long file transfers are still working.

In my previous post, I don't think I did a good job of explaining why dynamic memory allocation is important. So let me try and re-explain it in terms of how the stack was.

The initial implementation of the stack had a fixed number of elements for each table. An example would be like allocating a max number of 10 entries or the routing table and 5 entries for the indirect queue. A problem occurs if a particular application requires only 8 routing entries but 6 indirect queue entries. In that case, you ran out of memory.

Its very difficult to recover from situations where you run out of table/queue entries because the behavior may be unpredictable. This means that to be on the safe side, you would need to over-specify the max number of entries for each table/queue/list in order to have some margin of safety. This ends up wasting a lot of RAM. Another problem with this is that the stack uses something like twenty different  tables to keep track of everything (yes, I know its a lot...please  complain to the Zigbee Alliance). The amount of effort to tune the stack for each application would be tremendous and the inefficiency of the RAM usage is no good for something that is supposed to be in small, embedded applications.

If a standard memory allocation was used such as malloc, it would result in memory fragmentation. You can see an example of memory fragmentation in the drawing. Memory fragmentation is also an inefficient use of memory because even though the total amount of free memory may be available, you also need the memory to be adjacent so that you can fit the block into it. This becomes a problem in situations where many different sized blocks are being allocated and freed. With fragmentation, it becomes tougher to fit the large blocks due to the need for adjacent memory.

The Contiki memory management library overcomes this problem by having a feature called memory compacting. Every time a memory block is freed, all the used blocks that come after it will be moved down. This leaves all of the free memory in one ajacent heap so that you won't run into the fragmentation issues I mentioned earlier.

The memory management comes with a price though. It accomplishes this by using an added level of indirection. This means that when you allocate memory, you don't get a pointer to the actual memory. You get a pointer to a pointer to the memory. When you allocate managed memory, it will create a memory block structure which contains the size of the block and the pointer to the memory. It will then return a pointer to the managed memory pointer which points to the underlying memory.

The reason for this is that when memory is compacted, the address of the actual memory changes, but the changes are reflected in the managed memory pointer. So as long as you use the managed memory pointer, you will always be pointing to the correct address for the allocated memory. So to use the managed memory, all of the tables needed to be modified to use the managed memory pointer instead of actual memory. This added code size to the stack, however decreasing the RAM utilization takes priority over having a smaller code size for me. Its easier and cheaper to trade up to a microcontroller with a bigger flash, but it sure is tough to find one with a bigger RAM.

Here's an example of how the table handling changed.

Before:

rte_entry = list_head(rte_tbl);  // grab the route entry

next_hop = rte_entry->next_hop;  // get the next hop in the route entry

After:

mem_ptr = list_head(rte_tbl); // grab the memory pointer to the route entry

rte_entry = mem_ptr->mmem_ptr.mem_block_ptr;  // de-reference the memory pointer to get to the data

next_hop = rte_entry->next_hop; // now we can use the entry

There is one dangerous point about using the managed memory and I included a diagram so that it can be more easily seen. To actually access table elements, you have to de-reference the managed memory pointer and access the direct memory. However if in between de-referencing the pointer and actually using the table data, a block of memory gets freed somewhere, the de-reference pointer is useless and dangerous because it is now a dangling pointer. Since Contiki is not pre-emptive, you won't have to worry about a stray thread causing this situation, however it can occur if you have a function in between de-referencing and using the pointer. If the function frees memory somewhere, then it will be dangerous. So its best to use the pointer as soon as possible after de-referencing it.

Here's an example of an error case:

mem_ptr = list_head(rte_tbl);  // grab the first mem pointer from the route table

rte_entry = mem_ptr->mmem_ptr.mem_block_ptr; // de-reference the mem pointer

some_random_func(); // a memory block gets freed somewhere in here

next_hop = rte_entry->next_hop;  // this will be incorrect. the entry now points to junk.

Updated 2008-10-26: Just learned from Adam Dunkels, the author of the managed memory library (as well as Contiki and uIP), that the memory should only be dereferenced as its used. And the MMEM_PTR macro should be used to access the memory blocks only. That way, the error case won't be encountered. So looks like its time to re-modify the code to handle this. It should lead to a more robust design without needing to "play with fire" or at least run the risk of dangling pointers.

According to Adam, the problematic case should be rewritten like this:

mem_ptr = list_head(rte_tbl); // grab the first mem pointer from the route table

/* rte_entry = mem_ptr->mmem_ptr.mem_block_ptr; never de-reference and store the mem pointer like this */

some_random_func(); // a memory block gets freed somewhere in here

next_hop = ((struct tbl *)MMEM_PTR(mem_ptr))->next_hop; /* this is the way to access the memory pointed to by mem_ptr - this works even if a memory block was freed in some_random_func(). */

End update. The example error case will now only show what can happen if you abuse the memory management system  ;)

I've tried to keep the managed memory pointer handling away from the main parts of the code and isolated to the table files. That way, from a user point of view, you just call functions like rte_table_get_next_hop() and it will return the next hop data without worrying about de-referencing, dangling pointers, etc... That way, stack modification should be much easier for everyone. In most places, you only need to worry about handling the managed memory pointers if you are modifying the behavior of a table.

Well, that's all for now. Have a nice weekend!

TrackBack URI for this entry

Comments (4)

Subscribe to this comment's feed

Always use MMEM_PTR() to access the pointer
written by adam, October 25, 2008

Very nice post explaining how the mmem module works! Much better than the actual 'documentation' in the mmem module...

But, one very important point that needs to be raised: the MMEM_PTR() macro is the only way to access the pointer to the actual memory block. The pointer to the actual memory should never be explicitly accessed through the struct. Also, the pointer should never be stored somewhere else. By always using the MMEM_PTR() macro to access the memory, the problem with the moving addresses should not occur - or at least this was the idea behind the mmem module

The problematic case should be rewritten like this:

mem_ptr = list_head(rte_tbl); // grab the first mem pointer from the route table

/* rte_entry = mem_ptr->mmem_ptr.mem_block_ptr; never de-reference and store the mem pointer like this */

some_random_func(); // a memory block gets freed somewhere in here

next_hop = ((struct tbl *)MMEM_PTR(mem_ptr))->next_hop; /* this is the way to access the memory pointed to by mem_ptr - this works even if a memory block was freed in some_random_func(). */

Sorry if this was not clear from the module's documentation - the documentation for this module is known to be bad

report abuse

vote down

vote up

Votes: +1

...
written by Akiba, October 26, 2008

Hi Adam.
No problem. It was actually my mistake. I had run into the MMEM_PTR macro previously when I was reading through the code, but at that time, I didn't fully understand the behavior of the code. Now that you refreshed my memory, I could see why its needed. I'll be modifying the code to access the data elements through it. Hopefully, that will make things more robust and I won't need to run the risk of some later mod creating a dangling pointer.

BTW, congrats on all the activity at SICS recently. Sounds like you guys must be pretty busy.

report abuse

vote down

vote up

Votes: +0

A pointer to a pointer is a handle
written by David Kopf, February 25, 2009

At least that is what Apple called it in the original Macintosh toolbox (1984-). On the Mac a handle could be locked before dereferencing, then the pointer used in a section of code that called other toolbox functions that might shift memory around. The handle was then supposed to be unlocked to minimize "heap fragmentation". Not locking the handle was a frequent cause of the amusing Mac bomb dialog box.

report abuse

vote down

vote up

Votes: +0

...
written by Akiba, February 25, 2009

Thanks for the flashback. It's nice to know that we're rehashing problems that were solved in 1985 I will start to refer to the pointer to the memory pointer as a handle.

report abuse

vote down

vote up

Votes: +0

Show/Hide comment form

Name

Email

Website

Title

Comment

smaller | bigger

Subscribe via email (Registered users only)

I have read and agree to the Terms of Usage.

Write the displayed characters

Add Comment