c - 完全未使用的内存如何碎片化？

Question

以下 C 代码示例(取自 http://bugs.python.org/issue19246)在 Windows 7 64 位上执行，同时在 32 位模式下编译

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


int create_huge_linked_list(void **last_item) {
    int i;
    void *prev_item = NULL;

    for(i = sizeof(void *); i < 1000000; i++) {
        void *new_item = malloc(i);
        if(new_item == NULL) {
            break;
        }
        *(void **)new_item = prev_item;
        prev_item = new_item;
    }
    *last_item = prev_item;
    return i;
}

void free_linked_list(void *last_item) {
    while(last_item != NULL) {
        void *prev_item = *(void **)last_item;
        free(last_item);
        last_item = prev_item;
    }
}

int stress_heap() {
    void *last_item;
    int amount = create_huge_linked_list(&last_item);
    free_linked_list(last_item);
    return amount;
}

void stress_twice(void) {
    int first = stress_heap();
    int second = stress_heap();
    printf("%i %i %f%%\n", first, second, 100.0 * second / first);
}

void stress_and_alloc_1_mb() {
    void *ptr;

    ptr = malloc(1000000);
    if(ptr != NULL) {
        printf("Successfully allocated 1 MB before stress\n");
        free(ptr);

        stress_heap();

        ptr = malloc(1000000);
        if(ptr != NULL) {
            printf("Successfully allocated 1 MB after stress\n");
            free(ptr);
        } else {
            printf("Failed to allocate 1 MB after stress\n");
        }
    } else {
        printf("Failed to allocate 1 MB before stress\n");
    }
}

int main() {
    stress_and_alloc_1_mb();
    stress_twice();
    return 0;
}

输出:

Successfully allocated 1 MB before stress
Failed to allocate 1 MB after stress
64855 64857 100.003084%

结果可能会被解释为:在整个内存分配和释放之后，进程的内存碎片非常严重，以至于没有长度为 1 MB 的 block 。 然而，压力过程可以连续重复而不会出现内存错误。

问题是:

1. 如果内存完全未使用，内存如何碎片化？
2. 如何修复该进程的内存碎片？

Answer 1

#1

这是一个有趣的问题，因为我们从来没有真正谈论过碎片化的使用中内存(现在让我们忽略缓存局部性)。当所述内存可用于再次分配时，内存碎片成为一个问题，但以前的内存分配将内存池分成更小的 block 需要将 block 连接在一起。

我认为你问这个问题的原因是因为你已经习惯了最坏情况的例子，在这种情况下，不移动任何东西就不存在这样的连续内存块。但即使在非最坏的情况下，检测潜在的碎片整理操作也可能是一个非常困难的问题，导致分配器在人类可以轻松找到解决方案的问题实例上阻塞。

但要回答您的问题，请考虑这个分配的内存块:

aaaabbbbcccc

现在 a 和 c 被释放了:

....bbbb....

现在 b 被释放了:

....____....

现在我们在内存池中有三个连续的独立内存块 - 它需要特殊代码来检测这一点，显然分配器对此进行了阻塞。

#2

答案很简单:对内存池进行碎片整理。这个问题的难易程度取决于使用的是哪种分配器以及它做了多少簿记工作。