在C内存池中对内存块进行碎片整理

我在C中构建了一个简单的内存池，并且我还实现了在此池中实现内存块的功能。在C内存池中对内存块进行碎片整理

内存块本身非常简单，只是一个带有空白标志和大小属性的双向链表。

我现在要做的是创建一个函数，该函数需要一个指向我的内存池的指针并对内部的内存块进行碎片整理，以便分配的（free == 0）块朝向池的开始并释放块正朝着游泳池的尽头。

举例来说，如果我有记忆的块结构喜欢这个之前，我打电话给我的碎片整理功能：

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

然后打电话给我的功能之后块将被安排像这样：

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

我已经试图建立功能，但是我遇到了移动正确的块周围的问题似乎因为这是我的输出后函数被称为：

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

我并不确定函数执行的是不正确的操作，所以希望有人能为我阐明一些。

我的碎片整理功能：

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 
    } 
}

到initBlock函数的调用只是需要一个内存地址，将其视为一个块结构，然后设置自由属性为true和大小属性为给定大小。

我正在使用带-std = C99标志的GCC编译器。

来源

2016-04-14 Liam Potter

分配的块的所有者在重定位后会做什么？ –

@WeatherVane目前，我并不需要拥有所有者持有的指针，因为这是指向uni的指针。虽然拥有分配的中间目录并且指针持续存在会使我获得更高的分数，但它不是低分的要求。 –

碎片整理程序不知道用户放置内存指针的位置，因此您无法更新它们。当然，你只能整理未使用的区域。就像您在整理硬盘时一样，打开的文件无法移动。 –

看起来你没有在交换一对块之后更新下一个块的prev字段。所以当你前进到下一个块并检查前面的块是否空闲时，你将会访问垃圾。你需要像

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

在上面的else部分。

其他关注

这将严重行为不当，如果你的块不直接相邻，并在游泳池内秩序。您可能确保整个池是一个连续的memeory块，但如果其他例程重新排序，您可能仍会遇到问题。对于偏执狂编程来说，坚持断言以确保这些不变式不被侵犯是一个好主意。
任何外部指针到池中，将垃圾这个操作
后，如果有奇数大小的块（你出现），你会得到不对齐的指针，这充其量是低效的和最差可能会崩溃。
像你所描述的那样，池中有一个包含指向池的指针的固定大小的“句柄”的关联数组是非常正常的，并且每当你移动一个非空闲块时，都需要更新指针对应的手柄。手柄还可能有禁止移动块的“锁定”标志 - 在这种情况下，您需要检查该标志并仅移动未锁定的块，并且当您移动块时，可能需要移动到不相邻的块中。这可能会让你陷入上面的第一点。

来源

2016-04-14 20:18:12

在C内存池中对内存块进行碎片整理

回答

相关问题