Friday, May 14, 2010

Allocate only memory-groups for scatter-gather storage

Recently we wrote a simple but generic memory group for scatter-gather storage which could be just freed collectively in one single shot. So there is no free of any individual objects or data-set but just a alloc and a destroy. Its basically a simple power-of-2 alloc-only memory pool but used only for a specific scatter-gather result storage and processing scenarios.

Its not such a big deal but the generic approach impressed me to blog about it. And especially when your product is going to run in space now - Openclovis in space , some development genericity makes the framework cooler even though it isn't really required :-). In this case, we could have easily had multiple scatter-gather code references in different places as the usage scenarios were not complex as some of the earlier ones for which we developed other generic solutions which made more sense.

The idea was from a colleague of mine whom I consider to be an expert in object storage,synthesis and object-oriented generic design in general. Being a "C" programmer all my life, I had learnt some useful stuffs about writing code in a fashion that could be _easily_ re-used by anyone.

Before discussing the implementation details of the memory group, ask yourself a question:
"How many times have you faced a situation where you are supposed to hunt for variable-sized data-sets and save them in scatter-gather lists for fast but short-lived inspection and deletion".

Off-course this question is not relevant for dynamic typed languages like python but only holds good for "C" or C++. So if you are a python,ruby,perl or maybe even a Java programmer, you don't really have to read ahead and I leave it to your discretion :-)

It could be as simple as creating a storage array to hold the results and freeing them.
Something like:

void **data = NULL;
next_data = 1;
int count = 0;
while(next_data > 0)
if(!(count&15)) /*allocate and expand the result-set 16 at a time*/
data = realloc(data, (count+16) * sizeof(*data));
assert(data != NULL);
memset(data+count, 0, 16*sizeof(*data));
data[count] = calloc(1, getdatasize(&your_data_pool, count, &next_data) );
* Initialize data or fetch the result and copy it into data[count] and process data[count]
* free it here itself or delay frees to later if processing the data-set in batches

Now freeing them could be a simple one with a :free(data[count]); on each data-set after processing your results.The above result-data set to store results could even be a linked list, tree, or any data-structure that could hold these results for a short period of time.

Based on the data pool and the query of the data-set, your storage mechanism could slightly vary. But most of the times, it would represent a scatter-gather list accumulator.

Now if you want to follow this approach in many different places of the code which is supposed to accumulate and process results of different sizes,and then eliminate them immediately, you would have to effectively replicate the above code with maybe different variants.

To address this in a generic manner, we implemented a simple but generic allocate only memory group to address this scenario. We could have alternatively used our internal memory pool but the internal pool is used for fixed-size storage where you could create different pools to accomodate different storage sizes. Something like below to create a 1 MB pool that can be used to allocate objects upto size 32 bytes:

pool = pool_create(1<<20, 32, optional_flags);

and then allocate the data-set from the pool:

data = alloc_pool(pool, flags);

But most of the times, our data storage while quickly iterating through data-sets was not of fixed-size to pre-create memory cache pools and allocate objects from them. So we implemented an alternate but simple alloc-only memory group which used a simple power-of-2 allocator to allocate memory for the variable sized data-sets that could be used during scatter-gather. And this pool didn't have any individual object free but just had a collective free to destroy the entire scatter-gather memory group after usage.

The expectation is that these alloc-only memory groups would be short-lived and won't be residing in the process for longer periods holding memory. So the above scatter-gather result accumulator became something like this:

MemGroupT memGroup;
const int storageSizeBase = 8; /*just a initial base size. could be a sizeof(struct foo); */
memGroupInit(&memGroup, storageSizeBase);/*initialize a scatter-gather list with a base size*/

* The allocation of the data storage. is now from the above memGroup instead of a malloc.
* So within the "while" loop, you would have.
data[count] = memGroupAlloc(&memGroup, getdatasize(&your_data_pool, count, &next_data));

The above accumulates the resulting storage into an array for processing. You could just use them as it is after allocation. But the allocation base is from a group. And you could just base the &memGroup reference to other places in the code to allocate memory from its storage pool. And then after processing of the result-set, you could throw them all away instead of freeing each object/data individually using a collective or a 1 shot free like below:


which frees the memory group itself.

The above would also give you savings in iterating over your entire data-set storage in order to free the references later which could be sufficiently large. The implementation of memGroup uses a 32 slot memory pool where the memory capacity/storage in each slot is double the previous slot. So ideally you have a virtually large pool that could accomodate a max. allocation of 4 gig. (or 2 gig depending on whether you use the last slot or not. (1 << 32) or (1<<31))

I have also slightly spiced up the implementation by giving support to read-write memory groups. So you could write protect your objects or storage from the memory group whenever you want through something like:

object = memGroupAlloc(&memGroup, dataSize);
memcpy(object, mydata, dataSize);

Then you can convert the storage into a read-only location through something like this:

object = memGroupProtect(&memGroup, object);

So _any_ writes to the above "object" location would trigger a SIGSEGV or a segfault resulting in process-crash/core-dump as a read-only object memory location after memGroupProtect is write protected internally.

So you could lease the object to another portion of your code that isn't aware about the source of the object storage (like memGroup, malloc, etc.) thats expected to read the contents of the object and _not_ modify the object to be safe. And then you could again unprotect the object back later to modify it if you want through a later unprotect call on the same object:

object = memGroupUnprotect(&memGroup, object);

It resembles the mprotect syscalls: mprotect(obj, objlen, PROT_READ); and a mprotect(obj,objlen, PROT_READ| PROT_WRITE); but only for a small object snapshot from a big storage space.

memGroupProtect and unprotect internally use read-write and read-only mmap mirrors of a shared resource thats given out to the user as a data storage reference. You could also comment out the blocks in the below implementation that use a temp file for shared read-write and read-only mmap to protect and unprotect storage within the memGroup, throw-away the implementation of the protect and unprotect incase you don't need them and just use anonyous mmap or malloc calls to allocate a big storage chunk to your memGroup by modifying the memAlloc routine in the implementation below.

You can download/view the complete implementation here: Allocate-only MemGroups
Feel free to use the implementation in your code if you deem it fit for your usage-scenarios mentioned above.

No comments:

Post a Comment