0

I've built a simple memory pool in C and I've also implemented the ability to implement memory blocks in this pool.

The memory blocks themselves are quite simple, just a doubly linked list with a free flag and size property.

What I'm trying to do now is create a function that takes a pointer to my memory pool and defragments the memory blocks inside so that allocated (free == 0) blocks are towards the beginning of the pool and deallocated blocks are towards the end of the pool.

For example, if I had the blocks of memory structured like this before I called my defragment function:

Block Size: 25 (41 w/ header), Free: 1
Block Size: 100 (116 w/ header), Free: 0
Block Size: 25 (41 w/ header), Free: 1
Block Size: 100 (116 w/ header), Free: 0
Block Size: 100 (116 w/ header), Free: 0
Block Size: 54 (70 w/ header), Free: 1

Then after calling my function the blocks would be arranged like so:

Block Size: 100 (116 w/ header), Free: 0
Block Size: 100 (116 w/ header), Free: 0
Block Size: 100 (116 w/ header), Free: 0
Block Size: 25 (41 w/ header), Free: 1
Block Size: 25 (41 w/ header), Free: 1
Block Size: 54 (70 w/ header), Free: 1

I've attempted to build the function already however I've ran into a problem with moving the correct blocks around it seems as this is my output after the function is called:

Block Size: 100 (116 w/ header), Free: 0
Block Size: 25 (41 w/ header), Free: 1
Block Size: 100 (116 w/ header), Free: 0
Block Size: 1744830464 (1744830480 w/ header), Free: 21

I'm not certain at all where the function is performing the incorrect operations so hopefully someone can shed some light on this for me.

My defragment function:

void defragment(Pool* pool)
{
    if(pool && pool->root)
    {
        Block* current = pool->root;

        while(current)
        {
            if(!current->free)
            {
                Block* current_prev = current->prev;

                if(current_prev && current_prev->free)
                {
                    Block* prev_prev = current_prev->prev;
                    int new_block_size = current_prev->size;

                    Block* moved_current = memmove(current_prev, current, sizeof(Block) + current->size);

                    if(!moved_current)
                    {
                        printf("couldn't move memory\n");
                    }
                    else
                    {
                        Block* new_block = initBlock((((char*)moved_current) + sizeof(Block) + moved_current->size), new_block_size);
                        new_block->prev = moved_current;
                        new_block->next = moved_current->next;

                        moved_current->prev = prev_prev;
                        moved_current->next = new_block;

                        if(prev_prev)
                        {
                            prev_prev->next = moved_current;
                        }

                        current = moved_current;
                        continue;
                    }
                }
            }

            current = current->next;
        }

        //Join Contiguous Blocks
    }
}

The call to the initBlock function just takes a memory address, treats it as a Block structure, then sets the free property to true and the size property to the given size.

I'm using the GCC compiler with the -std=C99 flag.

4

1 回答 1

1

It looks like you're not updating the prev field of the next block after swapping a pair of blocks. So when you advance to the next block and check to see if the previous block is free, you'll be accessing garbage. You need something like

if (newblock->next)
    new_block->next->prev = new_block;

in the else part above.

Other concerns

  • This will misbehave badly if your blocks are not immediately contiguous and in order within the pool. You probably ensure that the entire pool is a single contiguous block of memeory, but you might still run into problems if some other routine reorders things. For paranoid programming, its a good idea to stick in asserts to ensure these invariants aren't violated.
  • Any external pointers into a pool will be garbage after this operation
  • If you have odd-sized blocks (which you appear to), you'll get unaligned pointers, which at best are inefficient and and worst may crash.
  • It is normal for a pool like you're describing to have an associated array of fixed-sized "handles" containing pointers into the pool, and whenever you move a non-free block, you need to update the pointer in the corrsponding handle. The handles may also have "lock" flags that inhibit moving blocks -- in which case you need to check that flag and only move unlocked blocks, and when you move blocks you might want to move into a non-adjacent block. This may in turn get you in trouble with the first point above.
于 2016-04-14T20:18:12.027 回答