因此，我被分配了一项任务来实现一个自由列表。一个列表，将要释放的项目添加到该列表中，稍后该列表将一次性释放：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: %sn", 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 startsn");
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 readyn");
printf("total = %1.3lf sn", end-begin);
printf("m+f = %1.3g sn", (end-begin)/(2*n0));
printf("cy = %1.3lf sn", ((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创建的列表中删除元素。。。
正如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);
在CCD_ 4的末尾。
惊喜
有一次，我评论道：
您还需要释放数据以及列表条目。
让我有些惊讶的是，在重新测试时，这是没有必要的。事实上，在我的机器上，在free_list_memory()中，所有的数据指针都是空的。这实际上很不幸——malloc()正在返回零数据。实际情况是，列表释放代码释放保存数据的原始list_t指针，然后将原始数据指针添加到空闲列表，将其视为list_t结构。如果分配的块的大小(来自nextsize()的随机数)小于list_t，则这变得不确定。
为了解决这些问题并获得真正干净的运行，即使有不同数量的条目，我创建了这个插入指令的代码版本(WhozCraig的函数处于活动状态)。
修订后的代码
注意，该代码确保所分配的空间至少与list_t结构一样大；这对于避免内存访问错误至关重要(在较长的运行中；我使用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 nulln", 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 %pn", 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 nulln", 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: %zun", 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: %sn", 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 startsn");
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("Donen");
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 readyn");
printf("total = %1.3lf sn", end-begin);
printf("m+f = %1.3g sn", (end-begin)/(2*n0));
printf("cy = %1.3lf sn", ((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函数不会考虑列表是循环的这一事实。最后一个节点CCD_ 22成员引用回CCD_。
如果是这样的话，这更像是你需要的：
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);
}
}
我必须诚实。我没有诊断其余部分，但如果这个列表确实是循环的，这是一个明显的问题。
祝你好运。
如果只朝一个方向发展，为什么要使用双链接(闭环)列表作为空闲列表。
您的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;
}
}