具有唯一列表 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 定义中的这一行特别创建了非终止递归，其中 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 的使用:

1. Linux 使用默认页面大小 4kb
2. 您的 Node 结构体使用 8 字节指针、4 字节整数、1 字节字符和 8 字节长整数，占用 276 字节。
3. 您的 List 结构体添加了另一个整数，占用 280 个字节。
4. 静态结构 List* 列表 分配的大小是 List 结构大小的 256 倍，四舍五入为 72kb，这远远大于页面大小。

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