一个帅气的链表节点删除引起的错误

源码下载

本文相关源码已整理，共 2 个文件。

打开下载目录 →

这是几年前在一个系统中的 DEBUG 经历，最近又发现了类似的错误，觉得应该分享出来。

可能很多人都知道如何在仅给出指向某节点的指针的情况下将节点删除，假设给定指针是 p，那么删除 p 只需 *p = *p->next 。下图演示了这个操作过程。图中 p 指向的节点复制了 p->next 的内容，这样，p 就替代了 p->next 。如果要释放被删除节点的内存，只需释放 p->next 即可。最后，整个链表的样子和直接删除节点 p 是一样的，数据 data1 被移除，整个链表也保持链接。“就跟从链表中将这个节点删除一样”。

cool_sign.jpg

下面两个代码是这种链表的简化的定义和使用示例。它的执行会引起一个段错误，因为删除链表节点时，释放的内存是 p 而不是 p->next 。因为 p 是作为链表中一个节点存在的，设计良好的操作系统会在这种情况下报告一个段错误。 

/* file list.h */
#ifndef __LIST_H__
#define __LIST_H__
#include <stdlib.h>

struct list_head {
  struct list_head *next;
};

#define LIST_HEAD_INIT(name) { &(name) }
#define LIST_HEAD(name) \
  struct list_head name = LIST_HEAD_INIT(name)

#define list_entry(ptr, type, member) \
  container_of(ptr, type, member)
#define container_of(ptr, type, member) ({ \
  const typeof(((type*)0)->member) *__mptr = (ptr); \
  (type *)((char *)__mptr - offsetof(type, member));})

#define for_each_node(list, name)  \
  struct list_head *name;  \
  for (name = list->next; name != list; name = name->next)

static inline void list_add(struct list_head *new, struct list_head *prev)
{
  new->next = prev->next;
  prev->next = new;
}

static inline void list_del(struct list_head *p)
{
  *p = *p->next;
}

static inline void list_delete_if(struct list_head *list,
  int (*f)(struct list_head *),
  void (*nfree)(struct list_head*))
{
  for_each_node(list, p) {
  if (f(p)) {
  struct list_head *t = p;
  list_del(p);
  nfree(t);
  }
  }
}

static inline void list_travel(struct list_head *list,
  void (*f)(struct list_head *))
{
  for_each_node(list, p)
  f(p);
}
#endif /* __LIST_H__ */

/* file main.c */
#include <stdio.h>
#include <malloc.h>
#include "list.h"

struct A {
  struct list_head list;
  int val;
};

void print_node(struct list_head *e)
{
  printf("node->val=%d,", list_entry(e, struct A, list)->val);
}

int val_is_2_p(struct list_head *e)
{
  return list_entry(e, struct A, list)->val == 1;
}

void node_free(struct list_head *e)
{
  free(list_entry(e, struct A, list));
}

int main()
{
  LIST_HEAD(list_of_a);

  struct A *node0 = (struct A*)malloc(sizeof(struct A)),
  *node1 = (struct A*)malloc(sizeof(struct A));

  node0->val = 1; node1->val = 2;
  list_add(&node0->list, &list_of_a);
  list_add(&node1->list, &list_of_a);

  list_travel(&list_of_a, print_node);
  putchar('\n');

  printf("delete node->val=2\n");
  list_delete_if(&list_of_a, val_is_2_p, node_free);

  list_travel(&list_of_a, print_node);
  putchar('\n');

  return 0;
}

这个错误很容易被发现，因为系统会报告段错误。发现后立即将释放的节点修改为 p->next 即可。但是，这仍然有问题。注意到节点的结构， *p=*p->next 并没有移动数据，只移动了指针。如果 list 元素不是结构的第一个节点， free 函数也是无法执行的。

当这一切都修改好后，依然有一个问题。系统中链表不是单独存在的，它与另一个数据结构配合使用，比如红黑树。一个节点同时出现在链表和红黑树中。首先我们删除了红黑树中的一个节点，然后将其从链表中移除并释放内存。如果按照这个流程，释放的内存是 p->next ，而这个节点很可能仍然链接在红黑树里。在大型系统中，内存是由内存管理模块分配的，这样系统就无法判断是否引用了无效的内存地址，系统仍会运行，大多数情况下结果还是正确的。但是，将会出现一次错误，这个错误不会引起系统崩溃，而是继续运行，最后给出错误的结果，这是最可怕的。

最終我放弃了这个没有写在教科书里的帅气的操作，链表节点的删除改成了下面这样，从此没出过问题。 

static inline void list_del(struct list_head **p)
{
  *p = (*p)->next;
}

By .