用于列出任务的Linux内核模块-BFS

Question

我正在尝试使用Linux模块实现“广度优先搜索”以显示内核任务列表，但无法执行。以下是DFS的模块，有人可以建议如何做BFS

void dfs(struct task_struct *task) {
    struct task_struct *child; //Pointer to the next child
    struct list_head *list; //Children

    //task->comm is the task' name
    //task->state is the task's state (-1 unrunnable, 0 runnable, >0 stopped)
    //task->pid is the task's process ID
    printk(KERN_INFO "Name: %-20s State: %ld\tProcess ID: %d\n", task->comm, task->state, task->pid);

    list_for_each(list, &task->children) { //Loop over children
        child = list_entry(list, struct task_struct, sibling); //Get child
        /* child points to the next child in the list */
        dfs(child); //DFS from child
    }
}

Answer 1

首先，在内核代码中编写递归函数是一个非常不好的主意。内核的可用堆栈大小有限，递归函数可能会导致该溢出并使所有程序崩溃。您应该改为迭代实现DFS / BFS：Wikipedia页面（DFS，BFS）提供了解释和代码示例。

这是一个简单的BFS实现，使用支持struct作为队列：

// Task queue slot, just a singly-linked list.
struct queue {
    struct task_struct *task;
    struct queue *next;
};

static void bfs(struct task_struct *task) {
    struct task_struct *child;
    struct list_head *list;
    struct queue *q, *tmp, **tail;

    // Initialize queue allocating a single task slot.
    q = kmalloc(sizeof *q, GFP_KERNEL);
    // NOTE: check for error (tmp == NULL).

    q->task = task;
    q->next = NULL;
    tail = &q->next;

    // While the queue is not empty.
    while (q != NULL) {
        // Get first task in queue.
        task = q->task;

        pr_info("Name: %-20s State: %ld\tProcess ID: %d\n",
            task->comm,
            task->state,
            task->pid
        );

        // Add all children to the queue.
        list_for_each(list, &task->children) {
            child = list_entry(list, struct task_struct, sibling);
            get_task_struct(child);

            // Create new queue slot for child.
            tmp = kmalloc(sizeof *tmp, GFP_KERNEL);
            // NOTE: check for error (tmp == NULL).

            tmp->task = child;
            tmp->next = NULL;

            // Add child to queue and advance tail pointer.
            *tail = tmp;
            tail = &tmp->next;
        }

        put_task_struct(task);

        // Pop task from queue and free the slot, proceed to next.
        tmp = q;
        q = q->next;
        kfree(tmp);
    }
}

在内核4.9上测试。

---

重要：上面的bfs()函数假设get_task_struct()在传递的get_task_struct()上已经被调用，并自动为您调用task。请记住，每次要访问任务时都要使用put_task_struct()，完成时要使用put_task_struct()，就像我上面所做的那样。您发布的代码似乎不行。

get_task_struct()

---

正在运行的示例模块代码：

put_task_struct()