[Little Brosers] Memory management issues

OK, first, happy new year ! Hope you all had great holida… come on, it’s ROSE’s logbook 😉

So for the last two weeks, I kept working one our lovely merkle tree and all the code it implies.


Indeed, first week was about adding interactivity to the simulation. Thus I added a shell to our simulation program as well as a thread per Device. “Device” is a c++ class wrapping the Little Brosers API which is supposed to emulate a running drop/phone.

Also I added basic C++ TCP server/client to the drops. Allowing them to communicate whenever main’s thread asks them to interact with each other. For now they are only able to ping the other. But I will use this communication channel to implement the diff-like. Indeed, until now, all the code I wrote could be tested without the presence of another Device. All was creating a merkle tree and adding messages to it. No interaction.

In total this interactivity implies 2 threads per Device(one for its “main” thread, another one for the tcp) and one for the main().

Rolling memory

So, while my merkle tree building process was believed to be fully terminated, I noticed yersterday a BIG issue. First some context:

In Guillaume’s Python script, the messages where dynamically allocated whenever it was necessary. Embedded C code does not allow this.

Also, in python, the messages were directly accessible. In our drops, the will be stored in the external flash memory.

Thus, I had to creat a C structure called a “slot pool” :

#define LB_NB_MAX_MSGS 50

typedef struct lb_bucket_slot lb_bucket_slot;
struct lb_bucket_slot {
    lb_bucket_slot *p_previous;
    lb_bucket_slot *p_next;
    message_t *p_msg;
    uint32_t timestamp;
    uint8_t p_hash[MESSAGE_SIGNATURE_SIZE];

typedef struct {
    // The + 1 is used to ease the memory management when all slots are full
    lb_bucket_slot slots[LB_NB_MAX_MSGS + 1];
    lb_bucket_slot *begin_busy;
    lb_bucket_slot *begin_free;
    size_t nb_free;
} lb_slot_pool;

As you ca see, a slot_pool is a big array of slots. A slot is a simple structure meant to represent in RAM one particular message stored in the external flash, with a copy of the message’s time stamp and signature for ease-of-use reasons.

So this pool has a limited capacity. Its capacity will eventually be the number of messages we can fit in our external memory. But for now, during simulation, we can choose any size. Here it is 50.

The thing is, what to do when we run out of free slots? Well, we are supposed to free the one referring to the oldest message. This feature was badly implemented by…. me. So i spent the whole day of yesterday re-thinking the management of this pool. And during the process, re-writing the merkle tree build process.


Now everything works fine. The slot pool size can be from 1 to +infinite. And whenever a pool of messages is submitted to this merkle tree, it will only keep the newest it can store.

I reviewed the entire code with Guillaume today and we found some edge-cases in the merkle tree build process that wear treated before yesterday (with the bad memory implementation) but not today. However, those cases are easy to solve with the new memory model. In this specific case, I clearly saw that a CI with unitary tests would have noticed me that the merkle tree build process of my new memory management forgot some edge cases that the previous model took care of.So now and more than ever, we realy need to write tests for this whole merkle tree thing. Don’t worry, Guillaume should be on it as I am writing this post.


See you next week !


Antony Lopez

Antony Lopez

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>




This site uses Akismet to reduce spam. Learn how your comment data is processed.