Can I specify the location of the heap to serialize my data?

Question

I want to store a program state in a file. So I have a mmapped file that I perform operations on and then save it and maybe use it later.

This is fine for simple things but if I want a long lived data structure that requires dynamic memory allocation, I need a memory allocator that I can force to allocate within the pages I have mmapped.

I'm fairly certain I can't do this with the standard c malloc, and I've looked at jemalloc and I don't know if I can see anything there. I don't know if I'm going the wrong way with this, but is there any way to specify the location/size of heap before it is used?

Answer 1

For something like this you don't really want dynamic memory allocation. What you want instead is an array which uses an index value of the pointed to element instead of an actual pointer.

Suppose you wanted to implement a binary tree. You can model it as follows:

struct tree {
    int free;
    int value;
    int left;
    int right;
};

The left and right fields contain the indexes of the nodes to the left and to the right of the given node, with the value -1 indicating no such node (i.e. it is equivalent to a NULL pointer in this context).

The free field can be used as a flag to determine whether a given element of the array is currently in use. If a node is marked with free equal to 1, the left field points to the next free node, making it easy to find free nodes.

Node 0 is special in that it is the start of the free list, and the right field points to the root node of the tree.

Then the following tree:

              7
           /     \
          3      10
         / \     / \
        1   4   8   12

Can be modeled as follows:

    free  value   left  right
   ---------------------------
0  |  1  |   0   |  8  |  1  |
   ---------------------------
1  |  0  |   7   |  2  |  3  |
   ---------------------------
2  |  0  |   3   |  4  |  5  |
   ---------------------------
3  |  0  |   10  |  6  |  7  |
   ---------------------------
4  |  0  |   1   | -1  |  -1 |
   ---------------------------
5  |  0  |   4   | -1  |  -1 |
   ---------------------------
6  |  0  |   8   | -1  |  -1 |
   ---------------------------
7  |  0  |   12  | -1  |  -1 |
   ---------------------------
8  |  1  |   0   |  9  |  -1 |
   ---------------------------
9  |  1  |   0   | -1  |  -1 |
   ---------------------------

Such a tree can either be memmapped, or kept in memory using malloc / realloc to manage the size.

If your data structure holds any kind of string, you'll want your structure to contain fixed size character arrays instead of pointers so that they serialize correctly.