Memory and pointers

Question

Hi

I have need some some help with some thinking around a task.

My task is to create one memory area

void *memory = malloc(320);

and then use pointers to store texts into this storage place: We want to divide this area into data blocks of 32 bytes, sow we can store: 320/32 = 10 data blocks a 32 bytes. Into one data block I can store (1 ASCSII char = 1 bytes) 32 characters.

I have a bitmap that is 10 long where every bit indicates if data block is used(1) or not(0).

But what if I want to store a text that is 60 characters long? Then i need 2 data blocks (2 x 32 bytes). The bitmap shows that data block 2 and 6 are free, 1 and 6 is not side by side. How can I achieve this?

struct  data {
    char * text;
};

typedef struct data d;

d->text = ???

Answer 1

This is called memory fragmentation and is a serious problem. You have to report out of memory even though there is technically enough to support the block.

Managed languages like C# that don't allow pointers (in the normal case - please don't fixate on this) have the freedom to rearrange the underlying memory and fix this problem (though it's not free in terms of performance).

To fix the problem in C:
There's not a lot you can do because those pointers into the memory prevent you from reshuffling everything. Someone else has mentioned the buddy system and there are others but few are simple. A lot are based on having preset 'big chunks' and 'small chunks' and only allowing small requests small chunks etc... but that's all to stop arriving at the problem in the first place, once you're there you either deny the memory request or expand the pool.

Answer 2

As mentioned in other comments and answers, this is a fragmentation problem. You could either defragment the code (which will impose lots of requirements and limitations on how systems are allowed to access the memory), or allocate memory.

There are techniques to minimize fragmentation. One popular one is buddy memory allocation: http://en.wikipedia.org/wiki/Buddy_memory_allocation

Answer 3

You would have to add a kind of a memory manager layer that keeps track of what slots a particular entry occupies (in this case a string) and in which order the slots are used - your bit field would not be enough.

Answer 4

Your string data structure should be exactly like your block manager except it should track "local" blocks rather than all blocks in the memory pool.

Answer 5

Some thoughts off the top of my head:

• Add on to your storage architecture by having all requests to your storage go through a controller/manager that abstracts access to the storage (could be the same one that handles the bitmap). This would allow you to defragment your storage while not worrying about other parts of the app having pointers to the wrong place after defragmentation.

• You could rewrite the spec for your storage system so that one specific byte of each block is used to store a number identifying the "next" block (thus having only 31 bytes of effective storage per block).

Answer 6

You could a byte from the each of the 10 32 byte spaces and used that byte as an index to the continuation of the string. This would actually be a linked list, and you could make it a doubly linked list by having the forward and backward indexes.