Solved

Memory pool for structures

Posted on 2003-12-09
7
511 Views
Last Modified: 2010-04-15
I've got an embedded system which wishes to avoid fragmentation.  The structure in question is going to be in constant use with several thousand of these messages being created and destroyed:

struct ex1
{
    char* name;
    int id;
    void* data;
};

struct ex2
{
    char* name;
    char* anotherName;
    void* data;
};

...


struct mainStruct
{
    enum_msg type;
    union
    {
        ex1* p_num1;
        ex2* p_num2;
        ....
    } data;
};


With all these different sized structures (ex1, ex2, ...) the memory will get framented very easily and very quickly.  I would think the best way to approach this would be with a memory pool.  Any suggestions on how to begin?  Any examples?
0
Comment
Question by:pringle
7 Comments
 
LVL 44

Assisted Solution

by:Karl Heinz Kremer
Karl Heinz Kremer earned 60 total points
ID: 9908722
You could use the GNU Memory Pool Malloc Library (http://www.plt.rwth-aachen.de/ov/english/libmpm.html), or write your own memory manager. All you need to do is create are replacements for the malloc and free functions.Your malloc would then treat requests for different sizes differently. Let's assume that you only care about ex1, ex2 and mainStruct, all other requests would be handled by the standard malloc. If your malloc receives a request for sizeof(ex1), it would return one element from an array of ex1 elements. If it receives a request for sizeof(ex2), it would return one element from an array of ex2 elements, and so on. You of course of the keep a free list for these arrays, so that a call to free() would return one array element to the pool. Malloc would always return the first free element from the respective pool.
In case you run out of pool elments, you would just pass the call on the the standard malloc (or allocate more memory for your pool, depending on how often you think this will happen).
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9908744

As long as your system has sufficient "real" memory to keep everything in memory (avoiding page swaps) then just grabbing the next chuck from the heap is as good as any.

struct ex1
{
    char* name;
    int id;
    void* data;
};

struct ex2
{
    char* name;
    char* anotherName;
    void* data;
};

struct ex1 X1;
struct ex2 X2;

  X1 = (struct ex1 *)malloc (sizeof (struct ex1));
  X1->name = malloc (some length);
  X1->data = malloc (some more);

  X2 = (struct ex2 *) malloc (sizeof (struct ex2));
  X2->name = malloc (this length);
  X2->anotherName = malloc (that length);
  X2->data = malloc (this other length);

Because malloc tends to assign memory based on the next free address, all of the data contained with the X1 structure will likely be very closely positioned in memory.  The same holds true for X2 and its data.

If you were doing massive amounts of random memory allocation and freeing, you could wind up with some data items scattered through memory.  But for the most part it won't be a problem.


Kent
0
 
LVL 22

Assisted Solution

by:grg99
grg99 earned 60 total points
ID: 9909060
How much memory do you have to play with?    What are going to be the lengths of those char * strings?

Are thoase char * strings also going to be allocated on the heap, or will they be pointerss to static data?

It looks like you could settle on a fixed 12-byte (or whatever it takes) allocation size for your basic message structures.

The variable length strings are going to be more of a problem.  Depending on their length, you might get away with also allocating those in 12-byte increments.  Or 8-byte increments with a pointer to the next chunk.

With a few tricks like these you can probably totally avoid fragmentation problems.

0
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 60 total points
ID: 9909109

Hi grg,

You got me to thinking about this.  (It's not always good that I get to thinking -- you never know what I might dream up. :) )

Hi pringle,

You can create a function to create each of these structure so that the struct and all of its data are in contiguous memory.  If the data assigned to each struct will not change in length (so that it doesn't have to move) this can work out pretty well and will nearly eliminate cache voiding due to memory fragmentation of the structure items.  If the data can change length, a similar function can easily be devised to relocate the struct and rebuild the data areas.

struct ex1
{
    char* name;
    int id;
    void* data;
};

struct *ex1 CreateEx1Structure (char *name, int id, char *data)
{
  struct ex1 *X1;

  X1 = (struct ex1 *)malloc (sizeof (struct ex1) + strlen (name) + strlen (data) + 2);
  X1->name = ((char *)X1)+sizeof (struct ex1);
  X1->data = ex1->name + strlen (name) + 1;
  strcpy (X1->name, name);
  strcpy (X1->data, data);
  X1->id = id;
  reutrn (X1);
}

It would take a pretty intensive program for me to want to do this, but it is certainly possible and under the right conditions it's even practical.

Kent
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 70 total points
ID: 9910585
Hi Pringle,

Taking these wonderful ideas one step furthur ...

>The structure in question is going to be in constant use with several thousand of these messages being created and
>destroyed:
allocate memory for say a few thousand of such structs and write a small manager for managing them ...
e.g.
top = (struct mainStruct *) malloc ( sizeof (struct mainStruct ) * 2048 );
to make maximum use of memory allocated, request this allocation quantity as a power of 2 (sizeof struct * 2048)

keep a bitmap and next free index to manage this pool of structs ... the bitmap will hold a 1 for each allocated index in this array of structs and a 0 for free index ... next index will hold the next free index which you will allocate when a request arrives ... On receving a request, you allocate the struct at index pointed by next free index and then advance this pointer to the next available index ...

A free request will change a bit in the bit map from 1 to 0

The problem now however would be internal fragmentation ... you will have intermixed 0s and 1s in a bitmap leading to slightly higher processing requirements than having sorted ones ...

If the structs in the array get exhausted and you need to allocate more structs, you can always realloc() the array and extend the bitmap ... the initial contents of the array and the bitmap remain the same

Going one step further would be to have mechanism for sorting out your 0s and 1s in the bitmap ... this can be achieved by introducing a index layer between the index and addresses ...

another step further would be to introduce memory management for string allocation in char * name

but it all depends on how much functionality do you require ...

as you said, you have several thousand (10,000-20,000) of such structs .... some common platforms have minimum 64 butes allocation requests .... that way all you would be spending is around 10 Mb of memory ... not much and definitely not worth the pain unless you are having some serious constrints

If you do have serious constraints then consider this >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
sizeof each struct is 16 bytes and you have upto two char *s in each struct ... you can modify the struct definition to utilize the remaining fragmented 48 bytes by using char name[48] in place of char * and restrict you application to 48 byte strings (which for name should be a reasonable length)
exact figures can vary depending on your platform ... but if you are able to achieve this balance, it will save you the pain of extra coding and overhead for memory management

If these do not sound good to you, then you definitely need to write some extent of memory management stuff.

Cheers
Sunny
0
 

Author Comment

by:pringle
ID: 9914630
Thanks for the help everyone..  I decided to change the char* to fixed length char[]'s.  In addition, I'll be creating a single pool that can be increased when depleted to manage the memory.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9914723

Hi pringle,

Since the structs now have fixed length character fields, managing your own structures in a single pool requires only slightly more code than just issuing a malloc() for each structure.

If you get the time, how about trying your program with the single pool and again with malloc() assign structs.  I'd be interested to know the performance difference.  (I suspect that it won't be much.)

Kent
0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now