空闲列表实现无法正常工作
Free list implementation not working properly
所以，我被分配了一个任务来实现一个空闲列表。将要 free:d 的项目添加到列表中，稍后该列表一次性成为 free:d。我写了以下内容：
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct list_t list_t;
struct list_t {
list_t* succ;
list_t* pred;
void* data;
};
list_t* free_list;
void free_list_memory(void)
{
list_t *p , *q;
p = free_list;
while (p != NULL) {
q = p->succ;
free(p);
p = q;
}
}
void add_to_free_list(list_t* add) {
if (free_list != NULL) {
add->pred = free_list->pred;
add->succ = free_list;
free_list->pred->succ = add;
free_list->pred = add;
} else {
free_list = add;
add->succ = add;
add->pred = add;
}
}
static double sec(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + 1e-6 * tv.tv_usec;
}
int empty(list_t* list)
{
return list == list->succ;
}
list_t *new_list(void* data)
{
list_t* list;
list = malloc(sizeof(list_t));
assert(list != NULL);
list->succ = list->pred = list;
list->data = data;
return list;
}
void add(list_t* list, void* data)
{
list_t* link;
list_t* temp;
link = new_list(data);
list->pred->succ= link;
link->succ = list;
temp = list->pred;
list->pred = link;
link->pred = temp;
}
void take_out(list_t* list)
{
list->pred->succ = list->succ;
list->succ->pred = list->pred;
list->succ = list->pred = list;
}
void* take_out_first(list_t* list)
{
list_t* succ;
void* data;
if (list->succ->data == NULL)
return NULL;
data = list->succ->data;
succ = list->succ;
take_out(succ);
free(succ);
return data;
}
static size_t nextsize()
{
#if 1
return rand() % 4096;
#else
size_t size;
static int i;
static size_t v[] = { 24, 520, 32, 32, 72, 8000, 16, 24, 212 };
size = v[i];
i = (i + 1) % (sizeof v/ sizeof v[0]);
return size;
#endif
}
static void fail(char* s)
{
fprintf(stderr, "check: %s\n", s);
abort();
}
int main(int ac, char** av)
{
int n = 50; /* mallocs in main. */
int n0;
list_t* head;
double begin;
double end;
double t = 2.5e-9;
if (ac > 1)
n = atoi(av[1]);
n0 = n;
head = new_list(NULL);
printf("check starts\n");
begin = sec();
while (n > 0) {
add(head, malloc(nextsize()));
n -= 1;
if ((n & 1) && !empty(head)) {
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
}
}
printf("Done");
while (!empty(head))
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
free_list_memory(); //added line
end = sec();
printf("check is ready\n");
printf("total = %1.3lf s\n", end-begin);
printf("m+f = %1.3g s\n", (end-begin)/(2*n0));
printf("cy = %1.3lf s\n", ((end-begin)/(2*n0))/t);
return 0;
}
运行 代码给出：
a.out(10009,0x7fff79ec0300) malloc: *** error for object 0x7fe160c04b20: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
DoneAbort trap: 6
运行 在 valgrind 中给出：
check starts
==10011== Invalid read of size 8
==10011== at 0x1000009B8: free_list_memory (check.c:20)
==10011== by 0x100000D8B: main (check.c:163)
==10011== Address 0x10081e270 is 0 bytes inside a block of size 423 free'd
==10011== at 0x10000894F: free (in /usr/local/Cellar/valgrind/HEAD/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==10011== by 0x1000009CA: free_list_memory (check.c:21)
==10011== by 0x100000D8B: main (check.c:163)
==10011==
==10011== Invalid free() / delete / delete[] / realloc()
==10011== at 0x10000894F: free (in /usr/local/Cellar/valgrind/HEAD/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==10011== by 0x1000009CA: free_list_memory (check.c:21)
==10011== by 0x100000D8B: main (check.c:163)
==10011== Address 0x10081e270 is 0 bytes inside a block of size 423 free'd
==10011== at 0x10000894F: free (in /usr/local/Cellar/valgrind/HEAD/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==10011== by 0x1000009CA: free_list_memory (check.c:21)
==10011== by 0x100000D8B: main (check.c:163)
==10011==
==10011==
==10011== More than 10000000 total errors detected. I'm not reporting any more.
==10011== Final error counts will be inaccurate. Go fix your program!
==10011== Rerun with --error-limit=no to disable this cutoff. Note
==10011== that errors may occur in your program without prior warning from
==10011== Valgrind, because errors are no longer being displayed.
==10011==
^C==10011==
==10011== HEAP SUMMARY:
==10011== in use at exit: 38,785 bytes in 423 blocks
==10011== total heap usage: 602 allocs, 6,176,342 frees, 149,153 bytes allocated
==10011==
==10011== LEAK SUMMARY:
==10011== definitely lost: 0 bytes in 0 blocks
==10011== indirectly lost: 0 bytes in 0 blocks
==10011== possibly lost: 0 bytes in 0 blocks
==10011== still reachable: 4,120 bytes in 2 blocks
==10011== suppressed: 34,665 bytes in 421 blocks
==10011== Rerun with --leak-check=full to see details of leaked memory
==10011==
==10011== For counts of detected and suppressed errors, rerun with: -v
==10011== ERROR SUMMARY: 10000000 errors from 2 contexts (suppressed: 0 from 0)
现在，我不明白出了什么问题，因为我正在从使用 malloc 创建的列表中删除元素...
为什么你的空闲列表使用双链（闭环）列表，如果只在一个方向上。
您的 void free_list_memory(void) 函数在尝试 运行 第二次遍历您的列表时崩溃。
也许这有帮助：
void add_to_free_list(list_t* add) {
if (free_list != NULL) {
free_list->succ = add;
add->succ = NULL;
} else {
free_list = add;
add->succ = NULL;
}
}
与WhozCraig 一样，问题更多的是代码在到达空闲列表的末尾时不会停止，因为它是一个循环列表，终止条件是寻找不存在的空指针不存在。
您可以通过将 free_list_memory() 重写为：
来解决大部分问题
static void free_list_memory(void)
{
if (free_list == 0)
return;
list_t *p = free_list;
do
{
list_t *q = p->succ;
// free(p->data); // Removed: see commentary below!
free(p);
p = q;
} while (p != free_list);
}
通过这一更改，我获得了一个大小为 24 的未释放内存块（在 64 位版本上）。所以有一个 list_t 没有被释放。该项目在 head;它恰好有一个 NULL 数据指针，因此您可以使用以下方法修复最终泄漏：
free(head);
在 main() 结束时。
惊喜！
曾经评论过：
You also need to free the data as well as the list entry.
令我惊讶的是，在重新测试时，没有必要这样做。事实上，在我的机器上，在 free_list_memory() 中，所有数据指针都是空的。这实际上很不幸 — malloc() 正在返回归零数据。实际上，列表释放代码释放了保存数据的原始 list_t 指针，然后将原始数据指针添加到空闲列表，将其视为 list_t 结构。如果分配块的大小（来自 nextsize() 的随机数）小于 list_t.
为了解决问题并获得真正干净的 运行，即使条目数量不同，我创建了代码的这个检测版本（WhozCraig 的功能处于活动状态）。
修改后的代码
请注意，代码确保分配的 space 至少与 list_t 结构一样大；这对于避免内存访问错误至关重要（在更长的 运行s 上；我使用 200 来解决小分配问题而不添加 sizeof(list_t) 因为碰巧前 50 个分配总是足够大）。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
typedef struct list_t list_t;
struct list_t {
list_t* succ;
list_t* pred;
void* data;
};
list_t* free_list;
static
void free_list_memory(void)
{
if (!free_list)
return;
// terminate "last" node (the node that refers
// back to the node pointed to by free_list,
// including a potential self-referencing node)
free_list->pred->succ = NULL;
// now run the loop. uses free_list as the iterator
// as it will finish with NULL, as it will be empty.
while (free_list)
{
void *p = free_list;
if (free_list->data == 0)
printf("2 %p: data is null\n", free_list);
//free(free_list->data); // Not necessary
free_list = free_list->succ;
free(p);
}
}
#if 0
static void free_list_memory(void)
{
if (free_list == 0)
return;
list_t *p = free_list;
do
{
list_t *q = p->succ;
// free(p->data); // Removed: see commentary below!
free(p);
p = q;
} while (p != free_list);
}
#endif
#if 0
/* Broken code from question - does not handle circular list */
void free_list_memory(void)
{
list_t *p , *q;
p = free_list;
while (p != NULL) {
q = p->succ;
free(p);
p = q;
}
}
#endif
static
void add_to_free_list(list_t* add) {
if (free_list != NULL) {
add->pred = free_list->pred;
add->succ = free_list;
free_list->pred->succ = add;
free_list->pred = add;
} else {
free_list = add;
add->succ = add;
add->pred = add;
}
add->data = 0; // Added to avoid access to uninitialized data warning from valgrind
}
static double sec(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + 1e-6 * tv.tv_usec;
}
static
int empty(list_t* list)
{
return list == list->succ;
}
static
list_t *new_list(void* data)
{
list_t* list;
list = malloc(sizeof(list_t));
printf("1: data address is %p\n", data);
assert(list != NULL);
list->succ = list->pred = list;
list->data = data;
return list;
}
static
void add(list_t* list, void* data)
{
list_t* link;
list_t* temp;
link = new_list(data);
list->pred->succ= link;
link->succ = list;
temp = list->pred;
list->pred = link;
link->pred = temp;
}
static
void take_out(list_t* list)
{
list->pred->succ = list->succ;
list->succ->pred = list->pred;
list->succ = list->pred = list;
}
static
void* take_out_first(list_t* list)
{
list_t* succ;
void* data;
if (list->succ->data == NULL)
{
printf("3: %p - data is null\n", list->succ);
return NULL;
}
data = list->succ->data;
succ = list->succ;
take_out(succ);
free(succ);
return data;
}
static size_t nextsize(void)
{
#if 1
size_t v = rand() % 4096 + sizeof(list_t);
printf("Size: %zu\n", v);
return v;
//return rand() % 4096;
#else
size_t size;
static int i;
static size_t v[] = { 24, 520, 32, 32, 72, 8000, 16, 24, 212 };
size = v[i];
i = (i + 1) % (sizeof v/ sizeof v[0]);
return size;
#endif
}
#if 0
static void fail(char* s)
{
fprintf(stderr, "check: %s\n", s);
abort();
}
#endif
int main(int ac, char** av)
{
int n = 50; /* mallocs in main. */
int n0;
list_t* head;
double begin;
double end;
double t = 2.5e-9;
if (ac > 1)
n = atoi(av[1]);
n0 = n;
head = new_list(NULL);
printf("check starts\n");
begin = sec();
while (n > 0) {
add(head, malloc(nextsize()));
n -= 1;
if ((n & 1) && !empty(head)) {
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
}
}
printf("Done\n");
while (!empty(head))
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
free_list_memory(); //added line
free(head);
end = sec();
printf("Check is ready\n");
printf("total = %1.3lf s\n", end-begin);
printf("m+f = %1.3g s\n", (end-begin)/(2*n0));
printf("cy = %1.3lf s\n", ((end-begin)/(2*n0))/t);
return 0;
}
我习惯使用的编译选项（这里我抑制了优化以避免在main()中内联所有内容）需要非静态函数的声明，所以我在每个函数中添加了static除了main() 这还不是静态的。必要时我还添加了 (void) 代替 ()。
$ gcc -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
> -Wold-style-definition -Werror crashing.c -o crashing
$
Valgrind 输出
$ valgrind --leak-check=full --suppressions=suppressions crashing 10
==41722== Memcheck, a memory error detector
==41722== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==41722== Using Valgrind-3.11.0.SVN and LibVEX; rerun with -h for copyright info
==41722== Command: crashing 10
==41722==
--41722-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option
--41722-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 2 times)
--41722-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 4 times)
1: data address is 0x0
check starts
Size: 447
1: data address is 0x10083f3e0
Size: 2825
1: data address is 0x100842440
Size: 3313
1: data address is 0x100842f90
Size: 3138
1: data address is 0x100843cd0
Size: 1946
1: data address is 0x10083f760
Size: 2784
1: data address is 0x100844960
Size: 3824
1: data address is 0x100845480
Size: 2582
1: data address is 0x100846410
Size: 3931
1: data address is 0x100846ed0
Size: 1125
1: data address is 0x100847ed0
Done
2 0x10083f3e0: data is null
2 0x100842440: data is null
2 0x100842f90: data is null
2 0x100843cd0: data is null
2 0x10083f760: data is null
2 0x100844960: data is null
2 0x100845480: data is null
2 0x100846410: data is null
2 0x100846ed0: data is null
2 0x100847ed0: data is null
Check is ready
total = 0.010 s
m+f = 0.000487 s
cy = 194959.641 s
==41722==
==41722== HEAP SUMMARY:
==41722== in use at exit: 39,132 bytes in 430 blocks
==41722== total heap usage: 528 allocs, 98 frees, 71,359 bytes allocated
==41722==
==41722== LEAK SUMMARY:
==41722== definitely lost: 0 bytes in 0 blocks
==41722== indirectly lost: 0 bytes in 0 blocks
==41722== possibly lost: 0 bytes in 0 blocks
==41722== still reachable: 26,034 bytes in 311 blocks
==41722== suppressed: 13,098 bytes in 119 blocks
==41722== Reachable blocks (those to which a pointer was found) are not shown.
==41722== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==41722==
==41722== For counts of detected and suppressed errors, rerun with: -v
==41722== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 15 from 15)
$
并且从打印的指针值可以看出，添加到空闲列表的数据确实是数据，而不是保存数据的list_t结构。
简单地将整个 list_t 结构从活动列表移动到空闲列表，而不是释放 list_t 结构并将数据用作空闲列表中的 list_t 结构。
此外，您可能应该记录数据的大小，以便了解空闲列表中的内容是否可用于特定分配。
假设您的其余代码是正确的（这是一个 大 假设），您的 free_memory_list 函数没有考虑 列表是循环的。最后一个节点 succ 成员指回 free_list.
中保存的地址
如果是这样的话，这更类似于你需要的：
void free_list_memory(void)
{
if (!free_list)
return;
// terminate "last" node (the node that refers
// back to the node pointed to by free_list,
// including a potential self-referencing node)
free_list->pred->succ = NULL;
// now run the loop. uses free_list as the iterator
// as it will finish with NULL, as it will be empty.
while (free_list)
{
void *p = free_list;
free_list = free_list->succ;
free(p);
}
}
我必须说实话。我没有诊断其余部分，但如果这个列表确实是循环的，这是一个明显的问题。
祝你好运。
所以，我被分配了一个任务来实现一个空闲列表。将要 free:d 的项目添加到列表中，稍后该列表一次性成为 free:d。我写了以下内容：
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct list_t list_t;
struct list_t {
list_t* succ;
list_t* pred;
void* data;
};
list_t* free_list;
void free_list_memory(void)
{
list_t *p , *q;
p = free_list;
while (p != NULL) {
q = p->succ;
free(p);
p = q;
}
}
void add_to_free_list(list_t* add) {
if (free_list != NULL) {
add->pred = free_list->pred;
add->succ = free_list;
free_list->pred->succ = add;
free_list->pred = add;
} else {
free_list = add;
add->succ = add;
add->pred = add;
}
}
static double sec(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + 1e-6 * tv.tv_usec;
}
int empty(list_t* list)
{
return list == list->succ;
}
list_t *new_list(void* data)
{
list_t* list;
list = malloc(sizeof(list_t));
assert(list != NULL);
list->succ = list->pred = list;
list->data = data;
return list;
}
void add(list_t* list, void* data)
{
list_t* link;
list_t* temp;
link = new_list(data);
list->pred->succ= link;
link->succ = list;
temp = list->pred;
list->pred = link;
link->pred = temp;
}
void take_out(list_t* list)
{
list->pred->succ = list->succ;
list->succ->pred = list->pred;
list->succ = list->pred = list;
}
void* take_out_first(list_t* list)
{
list_t* succ;
void* data;
if (list->succ->data == NULL)
return NULL;
data = list->succ->data;
succ = list->succ;
take_out(succ);
free(succ);
return data;
}
static size_t nextsize()
{
#if 1
return rand() % 4096;
#else
size_t size;
static int i;
static size_t v[] = { 24, 520, 32, 32, 72, 8000, 16, 24, 212 };
size = v[i];
i = (i + 1) % (sizeof v/ sizeof v[0]);
return size;
#endif
}
static void fail(char* s)
{
fprintf(stderr, "check: %s\n", s);
abort();
}
int main(int ac, char** av)
{
int n = 50; /* mallocs in main. */
int n0;
list_t* head;
double begin;
double end;
double t = 2.5e-9;
if (ac > 1)
n = atoi(av[1]);
n0 = n;
head = new_list(NULL);
printf("check starts\n");
begin = sec();
while (n > 0) {
add(head, malloc(nextsize()));
n -= 1;
if ((n & 1) && !empty(head)) {
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
}
}
printf("Done");
while (!empty(head))
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
free_list_memory(); //added line
end = sec();
printf("check is ready\n");
printf("total = %1.3lf s\n", end-begin);
printf("m+f = %1.3g s\n", (end-begin)/(2*n0));
printf("cy = %1.3lf s\n", ((end-begin)/(2*n0))/t);
return 0;
}
运行 代码给出：
a.out(10009,0x7fff79ec0300) malloc: *** error for object 0x7fe160c04b20: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
DoneAbort trap: 6
运行 在 valgrind 中给出：
check starts
==10011== Invalid read of size 8
==10011== at 0x1000009B8: free_list_memory (check.c:20)
==10011== by 0x100000D8B: main (check.c:163)
==10011== Address 0x10081e270 is 0 bytes inside a block of size 423 free'd
==10011== at 0x10000894F: free (in /usr/local/Cellar/valgrind/HEAD/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==10011== by 0x1000009CA: free_list_memory (check.c:21)
==10011== by 0x100000D8B: main (check.c:163)
==10011==
==10011== Invalid free() / delete / delete[] / realloc()
==10011== at 0x10000894F: free (in /usr/local/Cellar/valgrind/HEAD/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==10011== by 0x1000009CA: free_list_memory (check.c:21)
==10011== by 0x100000D8B: main (check.c:163)
==10011== Address 0x10081e270 is 0 bytes inside a block of size 423 free'd
==10011== at 0x10000894F: free (in /usr/local/Cellar/valgrind/HEAD/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==10011== by 0x1000009CA: free_list_memory (check.c:21)
==10011== by 0x100000D8B: main (check.c:163)
==10011==
==10011==
==10011== More than 10000000 total errors detected. I'm not reporting any more.
==10011== Final error counts will be inaccurate. Go fix your program!
==10011== Rerun with --error-limit=no to disable this cutoff. Note
==10011== that errors may occur in your program without prior warning from
==10011== Valgrind, because errors are no longer being displayed.
==10011==
^C==10011==
==10011== HEAP SUMMARY:
==10011== in use at exit: 38,785 bytes in 423 blocks
==10011== total heap usage: 602 allocs, 6,176,342 frees, 149,153 bytes allocated
==10011==
==10011== LEAK SUMMARY:
==10011== definitely lost: 0 bytes in 0 blocks
==10011== indirectly lost: 0 bytes in 0 blocks
==10011== possibly lost: 0 bytes in 0 blocks
==10011== still reachable: 4,120 bytes in 2 blocks
==10011== suppressed: 34,665 bytes in 421 blocks
==10011== Rerun with --leak-check=full to see details of leaked memory
==10011==
==10011== For counts of detected and suppressed errors, rerun with: -v
==10011== ERROR SUMMARY: 10000000 errors from 2 contexts (suppressed: 0 from 0)
现在，我不明白出了什么问题，因为我正在从使用 malloc 创建的列表中删除元素...
为什么你的空闲列表使用双链（闭环）列表，如果只在一个方向上。
您的 void free_list_memory(void) 函数在尝试 运行 第二次遍历您的列表时崩溃。
也许这有帮助：
void add_to_free_list(list_t* add) {
if (free_list != NULL) {
free_list->succ = add;
add->succ = NULL;
} else {
free_list = add;
add->succ = NULL;
}
}
与WhozCraig
您可以通过将 free_list_memory() 重写为：
static void free_list_memory(void)
{
if (free_list == 0)
return;
list_t *p = free_list;
do
{
list_t *q = p->succ;
// free(p->data); // Removed: see commentary below!
free(p);
p = q;
} while (p != free_list);
}
通过这一更改，我获得了一个大小为 24 的未释放内存块（在 64 位版本上）。所以有一个 list_t 没有被释放。该项目在 head;它恰好有一个 NULL 数据指针，因此您可以使用以下方法修复最终泄漏：
free(head);
在 main() 结束时。
惊喜！
曾经评论过：
You also need to free the data as well as the list entry.
令我惊讶的是，在重新测试时，没有必要这样做。事实上，在我的机器上，在 free_list_memory() 中，所有数据指针都是空的。这实际上很不幸 — malloc() 正在返回归零数据。实际上，列表释放代码释放了保存数据的原始 list_t 指针，然后将原始数据指针添加到空闲列表，将其视为 list_t 结构。如果分配块的大小（来自 nextsize() 的随机数）小于 list_t.
为了解决问题并获得真正干净的 运行，即使条目数量不同，我创建了代码的这个检测版本（WhozCraig 的功能处于活动状态）。
修改后的代码
请注意，代码确保分配的 space 至少与 list_t 结构一样大；这对于避免内存访问错误至关重要（在更长的 运行s 上；我使用 200 来解决小分配问题而不添加 sizeof(list_t) 因为碰巧前 50 个分配总是足够大）。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
typedef struct list_t list_t;
struct list_t {
list_t* succ;
list_t* pred;
void* data;
};
list_t* free_list;
static
void free_list_memory(void)
{
if (!free_list)
return;
// terminate "last" node (the node that refers
// back to the node pointed to by free_list,
// including a potential self-referencing node)
free_list->pred->succ = NULL;
// now run the loop. uses free_list as the iterator
// as it will finish with NULL, as it will be empty.
while (free_list)
{
void *p = free_list;
if (free_list->data == 0)
printf("2 %p: data is null\n", free_list);
//free(free_list->data); // Not necessary
free_list = free_list->succ;
free(p);
}
}
#if 0
static void free_list_memory(void)
{
if (free_list == 0)
return;
list_t *p = free_list;
do
{
list_t *q = p->succ;
// free(p->data); // Removed: see commentary below!
free(p);
p = q;
} while (p != free_list);
}
#endif
#if 0
/* Broken code from question - does not handle circular list */
void free_list_memory(void)
{
list_t *p , *q;
p = free_list;
while (p != NULL) {
q = p->succ;
free(p);
p = q;
}
}
#endif
static
void add_to_free_list(list_t* add) {
if (free_list != NULL) {
add->pred = free_list->pred;
add->succ = free_list;
free_list->pred->succ = add;
free_list->pred = add;
} else {
free_list = add;
add->succ = add;
add->pred = add;
}
add->data = 0; // Added to avoid access to uninitialized data warning from valgrind
}
static double sec(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + 1e-6 * tv.tv_usec;
}
static
int empty(list_t* list)
{
return list == list->succ;
}
static
list_t *new_list(void* data)
{
list_t* list;
list = malloc(sizeof(list_t));
printf("1: data address is %p\n", data);
assert(list != NULL);
list->succ = list->pred = list;
list->data = data;
return list;
}
static
void add(list_t* list, void* data)
{
list_t* link;
list_t* temp;
link = new_list(data);
list->pred->succ= link;
link->succ = list;
temp = list->pred;
list->pred = link;
link->pred = temp;
}
static
void take_out(list_t* list)
{
list->pred->succ = list->succ;
list->succ->pred = list->pred;
list->succ = list->pred = list;
}
static
void* take_out_first(list_t* list)
{
list_t* succ;
void* data;
if (list->succ->data == NULL)
{
printf("3: %p - data is null\n", list->succ);
return NULL;
}
data = list->succ->data;
succ = list->succ;
take_out(succ);
free(succ);
return data;
}
static size_t nextsize(void)
{
#if 1
size_t v = rand() % 4096 + sizeof(list_t);
printf("Size: %zu\n", v);
return v;
//return rand() % 4096;
#else
size_t size;
static int i;
static size_t v[] = { 24, 520, 32, 32, 72, 8000, 16, 24, 212 };
size = v[i];
i = (i + 1) % (sizeof v/ sizeof v[0]);
return size;
#endif
}
#if 0
static void fail(char* s)
{
fprintf(stderr, "check: %s\n", s);
abort();
}
#endif
int main(int ac, char** av)
{
int n = 50; /* mallocs in main. */
int n0;
list_t* head;
double begin;
double end;
double t = 2.5e-9;
if (ac > 1)
n = atoi(av[1]);
n0 = n;
head = new_list(NULL);
printf("check starts\n");
begin = sec();
while (n > 0) {
add(head, malloc(nextsize()));
n -= 1;
if ((n & 1) && !empty(head)) {
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
}
}
printf("Done\n");
while (!empty(head))
add_to_free_list(take_out_first(head)); //before free(take_out_first(head))
free_list_memory(); //added line
free(head);
end = sec();
printf("Check is ready\n");
printf("total = %1.3lf s\n", end-begin);
printf("m+f = %1.3g s\n", (end-begin)/(2*n0));
printf("cy = %1.3lf s\n", ((end-begin)/(2*n0))/t);
return 0;
}
我习惯使用的编译选项（这里我抑制了优化以避免在main()中内联所有内容）需要非静态函数的声明，所以我在每个函数中添加了static除了main() 这还不是静态的。必要时我还添加了 (void) 代替 ()。
$ gcc -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
> -Wold-style-definition -Werror crashing.c -o crashing
$
Valgrind 输出
$ valgrind --leak-check=full --suppressions=suppressions crashing 10
==41722== Memcheck, a memory error detector
==41722== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==41722== Using Valgrind-3.11.0.SVN and LibVEX; rerun with -h for copyright info
==41722== Command: crashing 10
==41722==
--41722-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option
--41722-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 2 times)
--41722-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 4 times)
1: data address is 0x0
check starts
Size: 447
1: data address is 0x10083f3e0
Size: 2825
1: data address is 0x100842440
Size: 3313
1: data address is 0x100842f90
Size: 3138
1: data address is 0x100843cd0
Size: 1946
1: data address is 0x10083f760
Size: 2784
1: data address is 0x100844960
Size: 3824
1: data address is 0x100845480
Size: 2582
1: data address is 0x100846410
Size: 3931
1: data address is 0x100846ed0
Size: 1125
1: data address is 0x100847ed0
Done
2 0x10083f3e0: data is null
2 0x100842440: data is null
2 0x100842f90: data is null
2 0x100843cd0: data is null
2 0x10083f760: data is null
2 0x100844960: data is null
2 0x100845480: data is null
2 0x100846410: data is null
2 0x100846ed0: data is null
2 0x100847ed0: data is null
Check is ready
total = 0.010 s
m+f = 0.000487 s
cy = 194959.641 s
==41722==
==41722== HEAP SUMMARY:
==41722== in use at exit: 39,132 bytes in 430 blocks
==41722== total heap usage: 528 allocs, 98 frees, 71,359 bytes allocated
==41722==
==41722== LEAK SUMMARY:
==41722== definitely lost: 0 bytes in 0 blocks
==41722== indirectly lost: 0 bytes in 0 blocks
==41722== possibly lost: 0 bytes in 0 blocks
==41722== still reachable: 26,034 bytes in 311 blocks
==41722== suppressed: 13,098 bytes in 119 blocks
==41722== Reachable blocks (those to which a pointer was found) are not shown.
==41722== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==41722==
==41722== For counts of detected and suppressed errors, rerun with: -v
==41722== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 15 from 15)
$
并且从打印的指针值可以看出，添加到空闲列表的数据确实是数据，而不是保存数据的list_t结构。
简单地将整个 list_t 结构从活动列表移动到空闲列表，而不是释放 list_t 结构并将数据用作空闲列表中的 list_t 结构。
此外，您可能应该记录数据的大小，以便了解空闲列表中的内容是否可用于特定分配。
假设您的其余代码是正确的（这是一个 大 假设），您的 free_memory_list 函数没有考虑 列表是循环的。最后一个节点 succ 成员指回 free_list.
如果是这样的话，这更类似于你需要的：
void free_list_memory(void)
{
if (!free_list)
return;
// terminate "last" node (the node that refers
// back to the node pointed to by free_list,
// including a potential self-referencing node)
free_list->pred->succ = NULL;
// now run the loop. uses free_list as the iterator
// as it will finish with NULL, as it will be empty.
while (free_list)
{
void *p = free_list;
free_list = free_list->succ;
free(p);
}
}
我必须说实话。我没有诊断其余部分，但如果这个列表确实是循环的，这是一个明显的问题。
祝你好运。