具有唯一列表 ID 的链表的 C 实现

Question

我需要在内核代码中实现一个链表（不确定它是否太重要）。代码应该用 0 到 255 之间的数字标识每个链表。并且每个节点在列表中也有一个 id 和一些其他数据字段。我在让它工作时遇到了一些麻烦，并且不确定出了什么问题我已经写得很清楚了，但它似乎存在分段问题。我很乐意了解这里出了什么问题。

注意：我很确定问题不在于它使用内核函数这一事实。

#undef __KERNEL__
#define __KERNEL__
#undef MODULE
#define MODULE
#include <linux/kernel.h>  
#include <linux/module.h>  
#include <linux/fs.h>       
#include <linux/uaccess.h>  
#include <linux/string.h>   

MODULE_LICENSE("GPL");

typedef struct Node { 
    long node_id;
    char data[256];
    int data_size;
    struct Node next;
};

typedef struct List { 
    int list_id;
    struct Node head;
};

/* array holds the Lists by their list_id number */
static struct List* lists = (List*) kmalloc(256 * sizeof(List), GFP_KERNEL);

static struct List* get_list(int list_id) {
    return lists[list_id];
}

static struct Node* get_node(struct List* list, long node_id) {
    struct Node* node = list->head;
    while (node != NULL) {
        if (node->node_id == node_id) {
            return node;
        }
        node = node->next;
    }
    return NULL;
}

static void add_node(struct List* list, long node_id) {
    struct Node* node;
    node = kmalloc(sizeof(Node), GFP_KERNEL);
    node->next = list->head;
    list->head = node;
}

static void add_list(int list_id) {
    struct List* list;
    list = kmalloc(sizeof(List), GFP_KERNEL);
    list->list_id = list_id;
    lists[list->list_id] = list;
}

static void free_list(struct List* list) {
    if (list == NULL) {
        return;
    }
    while (list->head != NULL) {
        struct Node* node = list->head;
        list->head = node->next;
        kfree(node);
    }
    kfree(list);
}

static void free_lists(void) {
    int list_id;
    for (list_id = 0 ; list_id < 256; list_id++) {
        free_list(lists[list_id]);
    }
}

Answer 1

struct Node next;

您的 struct Node 定义中的这一行特别创建了非终止递归，其中 struct Node 需要另一个已定义的 struct Node 才能正确定义，这需要另一个 struct Node，以此类推：

我们使用指针是因为我们可以用 NULL 终止链表，这意味着没有更多的节点可以连接：

我假设您正在尝试以这种方式实现您的链接列表和节点，因为您对它们的操作就像它们是您函数中的指针一样，最值得注意的是 get_list。

关于kmalloc还有一点值得一提：

kmalloc is the normal method of allocating memory for objects smaller than page size in the kernel.

Although I've read that kmalloc can allocate way more memory than this default page size in modern kernels，我不知道具体是什么 Linux 版本或您使用的环境。做出以下假设，您可能需要重新考虑这些数据结构的整体实现或至少您对 kmalloc 的使用：

Linux 使用默认页面大小 4kb
您的节点结构，使用 8 字节指针、4 字节整数、1 字节字符和 8 字节长整数，占用 276 字节。
添加另一个整数的 List 结构占用 280 个字节。
static struct List* lists 分配 List 结构大小的 256 倍，四舍五入为 72kb，比页面大小大得多。

首先，我建议您让列表使用指向头节点的指针，而不是让列表存储头本身。我还建议您将 char data[256] 设为 dynamic array， 最大容量 为 256，这样您也可以节省一些 space。我还建议您使用指向列表的指针数组（static struct List* lists[256] 而不是 static struct List* lists 或 static struct List lists[256]）。

具有唯一列表 ID 的链表的 C 实现

C implementation of linked lists with unique list id's

c

implementation

linked-list

data-structures