Categories

[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.

Interactivity

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

[Little Brosers] Decorating my very own Christmas Merkle tree

Ho Ho Ho !

Guess who’s putting messages instead of presents at the foot of it’s Christmas Merkle tree ?

Ok so last week I wrote you a whole essai about how I planned to manage messages relatively to the drop’s Merkle tree, and how to build this tree.

Here is a simplistic summary:

Merkle tree ? Again?

Yes, this week I kept on testing my Merkle tree build process. I also tested the function allowing to insert new messages in a tree already containing messages. It may not seem that complicated, but I had to make sure to take into account every single case of insertion and not break my structure. And believe me, there is quite a lot. Don’t forget we have two sorting levels.

There is still no unitary test. But fear not, it’s coming soon ! With Guillaume, we agreed that he should be in charge of reviewing my code and writing the tests for it (see? I told you 😉 )

The reason for that is the following: Guillaume wrote the prototype python code for the Merkle tree and for our diff-like algorithm for comparing trees of two drops. We will see if I respected his vision of the whole process.

 

What’s comming for me?

Next step is writing the diff-like algorithm in C. However to write and test this, I am using a C++ simulation environment emulating the existence of two drops and their interaction. It kept me busy for the last three days, I am still building it before diving into the diff-like algorithm.

For now the drops C++ objects share the same thread. I’m thinking about giving each “virtual” drop its own.

 

That’s all for me,

 

Merry Christmas !

 

Antony Lopez

[Little Brosers] From Python to C

Soooooo… No joke this week, I’m almost gonna write an essai this time.

 

First step: Allocating memory for our Merkle tree

So, the first issue about implementing our Merkle tree structure using C is memory allocation.

A simple way would be to use recursive build function for each node and malloc() each of them. But, let’s remember that we will use this code on an embedded system. Dynamic allocation is not allowed.

So the first struggle was to find out how to staticaly allocate the space needed for our Merkle tree.

 

First I need to refresh your memory. Our Merkle tree is 4-ary balanced-ish. That is to say, each child of a node represents the time frame of the node divided by four. But this balanced time distribution rule is broken for the 4 first children of the tree, a.k.a. the root’s children. Those nodes have a an arbitrary part of the root’s time frame. This choice has been made because we think a lot of messages will be recent. Thus, the very last 24 hours will be more likely to contain messages than the last week.

To know when do we stop to split a node’s time frame, we have a constant in the code called BUCKET_SIZE. It gives the minimum time frame a node can represent. Thus, in this case, if the time frame width of a node divided by the number of children (4 here) is greater than BUCKET_SIZE, we split it. Otherwise, this node becomes a leaf.

Here is a basic representation:

So how do we statically allocate such a structure?

Several solutions were examined and to be short, the chosen one is the magic “python generated C header”.

In other terms, a python script included in our Makefile is called whenever the file containing our Merkle tree’s constants is modified and re-write a second header which only contains the size of our sub trees. This way we only have to include this generated header in our merkle_tree.c file and we know at compilation time the size needed for each subtree.

Oh and the sub trees are stored in C arrays.

 

Second step: Building the Merkle tree

Ok, now we know we have all the memory pre-allocated. The thing is…. we only have four dumb arrays. We need to turn this into a tree structure.

See below, we have 4 arrays of ‘node’ C structs and one node C stuct:

The sub trees are stored in their array in a Breadth First Search manner. The sizes of the arrays have been “#define” declared by the python script in a header.

The image above is a simplified representation of the sub trees and arrows are missing. Actually, There is also pointers to parent node.The job in this part has been to make sure each node C struct of the arrays is filled correctly and that each of its pointers is set.

For the curious ones, here is the content of a node C struct (for now):

struct node_t {
    uint64_t start;
    uint64_t end;
    uint32_t child_width;
    node_t *p_parent;
    node_t *p_children[LB_MT_NB_CHILDREN];
    uint16_t depth;
    uint16_t child_id;
    uint16_t array_id;

    slot_t *p_slots;
    uint8_t p_hash[SHA256_BLOCK_SIZE];
};

 

 

Third step: Attaching messages to leafs

We have now a Merkle tree structure we can explore without knowing it’s an array and just using the provided pointers in each node.

The next step is to find out which message has to be attached to which leaf. Also, the actual messages will be stored in external flash so we can’t “put” the message in the leaf structure. We will instead use structures called ‘slot’. Each slot can only correspond to one message and will have an integer which will correspond to the address of its message in the external flash. The only thing we will copy from the message is its time stamp, for convenience. This is what it looks like :

struct slot_t {
    slot_t *p_previous;
    slot_t *p_next;
    uint32_t msg_addr;
    uint32_t timestamp;
};

So each leaf will be able to have what we call a bucket, a.k.a. a linked list of slot_t C structs.

By the way, the slots are stored in a global array of slot_t. The array’s size is the max number of messages we can store in the external flash. We also have three global variables in the program of type slot_t* named begin_busyend_busy and begin_free. We will see that our array of slots can be seen as a pool of slots.

At startup, none of slots are used. Thus, we will attach the slots all together. Then will assign begin_free to the first slot of the array. Making begin_free the head of a linked list of ready-to-use slots.

During the tree building process, a slot will be detached from this linked list each time a message is being attached to a leaf’s bucket. The begin_busy and end_busy pointers will be set latter.

At the end of this process, each message will be attached to its slot. This slot will be placed in a leaf’s bucket following those rules:

  • When there is only one message belonging to a leaf’s time frame, the bucket of this leaf will be of size 1 and will contain this messages’s slot.
  • If several messages with different time stamps all belong to the same leaf, they will be attached to this leaf’s bucket. The bucket’s order will be based on the slots time stamps.
  • Finally, if several messages with the same time stamp all belong to the same leaf, the will be attached to this leaf’s bucket. We will not be able to order them by time stamp since their are equal. We will us their SHA256 instead.

Fourth step: Building our linked list of time-ordered messages

 

So now, we have a Merkle tree with (small) linked lists attached to its leafs. The only thing to do next is to attache all those linked lists together to have a long one. The begining and ending of this long list will be stored in the begin_busy and end_busy pointers. This long linked list will be used to travel across the messages list in an time ordered manner. Being able to doing so will be very useful because it allows us to not order the messages in the external flash.

 

What to do next ?

 

So yeah, it has been quit challenging to find an efficiente way to store and build this Merkle tree in C. I now understand why python is such an easy-to-prototype language.

 

Even if i have a some messages pools for which the tree building process succeed, I know for sure that it is not over yet. I found particular message pool which make crash my building process. So i might spend the following week fixing it.

 

By the way, there is still no automatic test using criterion in my code. I plan on adding some as soon as possible. For now I only use my eyes to read the text-representation of my tree and printf() error reporting in order to detect errors.

 

See you next week !

 

Antony Lopez

[Little Brosers] Tree best reasons to start working on our C library

Guess what, I spent less time finding this posts’s title joke than last week. I’m getting good at it !

 

Reason one: No-More-Windows

Let’s just say that designing our PCB using Windows 10 on my MacBook Pro (late 2011) was not the best time effective part of ROSE. More seriously, our PCB’s design is now over. I spent some time this week tweaking last details: adding the VIAs all over the board and designing the antenna to SoC track adapting its impedance to get the most out of our tiny little baby 2.4GHz antenna.

Oh and, I forgot to mention the number one killer feature of this board : There will be the following text engraved in it: “Little Brosers ROSE 2018”. Wow. So fancy. Much professional.

Reason two: Winter is coming, the end of ROSE too

My dear fellows know as much as me how reassuring the countdown of this blog’s welcome page is. Or is it?

Regarding our project, we were building tiny parts of the project until now and some start to interact. (mostly Android and nrf52 bluetooth stack for now)

Our merkle tree implementation and the “diff-like” algorithm written in python by Guillaume are functional but need to be translated to some more optimized C code. This is what I started to do this week and what will fill the next ones.

There is some big issues about how we will allocate the memory for the merkle tree and how we will link it to the messages stored in the external flash. For now, we need to validate the diff-like algorithm in order to test it with the bluetooth stack.Thus, we will simply dynamically allocate the merkle tree. This is still a big chunk of work to do. Of course we will switch to a static allocation later in the project.

Reason tree: Credibility

I just needed three elements to make my joke.

See you next week !

Antony Lopez

[Little-Brosers] Merkle trees

Hello everyone, this is Guillaume from the Little Brosers group.

 

We started this week working collectively by trying to estimate the key numbers of our project like memory size of our data, average and peak consumption, the rates needed at various interfaces… I’m not going to lie, this was a bit puzzling since we have a huge chunk of theoretical work to do before being able to correctly evaluate these things. However, the fact that we tried meant that even though our evaluations have turned out to be mostly approximations, our vision of the projects greatly advanced. We were able to take the decisions concerning the cryptographic algorithms we are going to use, our preliminary message structure, and I then started the works on the Merkle tree.

 

The Merkle tree structure will define how a drop and a phone can efficiently identify the messages they are missing from each other.

For those not familiar with it, a Merkle tree is something quite simple yet efficient used for example in P2P protocols to easily identify which data chunk is missing from users. The way it works is the following: each leaf represents a data chunk hashed using one’s favorite hash function. Then, each node is built by hashing concatenation of the children’s hashes. Two parties can then quickly identify what piece of information they have in common and what piece of information differs by comparing their Merkle tree. The comparison stars by the root, and if it is different, the children of the root are then compared etc… The comparison of a branch stops when you find two equal hashes or you reach the leaf, identifying a data block you’re missing.

 

Most classical examples of Merkle trees are binary trees, however in our case the tree will be n-ary, where n will be defined by the max number of hashes we can send over bluetooth in a single message, for energy efficiency purposes. The hash are most likely going to be md5, therefore 16 bytes long. The values we found for the max bluetooth payload in 4.2 are around 200 bytes, however we do not know how our payload will be when we really get our hands on the actual PCB. While we are still looking into bluetooth specs to determine which n we are going to use, i took 4 as reasonable example to start working on it while the rest of the group can continue their research.

 

One of the challenges was that we want to build our Merkle tree around chronological ordering of messages, where each node represents a time frame. However, our system will most likely not even keep track of time since it would be a waste of energy. What we decided to do was to implement a certificate signed by the server and delivered daily to all users, most likely at the same time everyday, certifying the current time. When a user encounters a drop during handshake there will be a phase where each party agrees on what time is “now” and recalculate its Merkle tree if needed. That way, a drop will at most have to recalculate their Merkle tree once every 24 hours + every time they receive new messages.

 

Since the agreement of what is considered “now” is the only agreement between the two parties before comparing trees, the next challenge was to think of the actual Merkle tree model to be used. I will skip on the details since the model is still prone to change in the next few days, but hopefully my next week post will be done once the tree structure and comparison protocol is formalised. I will then explain the choices made and think worst case scenarios.

That is what my next week will be: formally put on paper what I am currently thinking the Merkle tree comparison process will be, as well as update the first draft of the Merkle tree model. Once it is done, I will try to formally prove that the algorithm does the work, and try to look into worst case scenarios to ensure the process will still be reasonable in unusual cases.

 

For the moment, here is the draft of how a Merkle tree will be built. The is a small mistake in the placement of Message 14. The +6/+12 node should not have been subdivided since there is only one message inside. Message 14 should have been put directly inside the node. The formal rules will be available on our wiki most likely during next week (I do not know if the readers outside of Telecom have acess to it though, if not and some people are interested we will find another solution).

 

 

Thanks for reading, cheers, and see you next week,

Guillaume