使用深度优先搜索遍历任务子树的内核模块。

Question

我知道如何创建内核并通过简单包含linux/sched.h并使用以下代码线性迭代进程：

struct task_struct *task;

for_each_process(task)
{
   printk("Name: %s PID: [%d]\n", task->comm, task->pid);
}

如何使用深度优先搜索打印这些任务？我希望输出结果类似于ps -eLf的输出。

以下代码片段仅供参考：

struct task_struct *task;
struct list_head *list;
list_for_each(list, &init_task->children) {
    task = list_entry(list, struct task_struct, sibling);
    /* task points to the next child in the list */
}

我知道task->comm返回任务的名称，task->pid返回该任务的PID。

用于状态和父PID的字段是什么？

- Hassan Jalil

---

你需要实现DFS或BFS算法。在谷歌上搜索可以找到算法。如果你正在寻找一些API，内核中没有对DFS或BFS的支持。 - Vivek S

Answer 1

这篇文章有点老，但是我看到它似乎是第3章中的编程项目之一，在《操作系统概念第9版》中发现的，所以其他人也可能会寻找。

你开始使用的代码直接来自书本，但它是一个很好的起点。你只需要实现深度优先搜索算法(DFS)。以下是可以完成它的代码，应该很容易理解：

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/init.h>

/**
 * Performs a DFS on a given task's children.
 *
 * @void
 */
void DFS(struct task_struct *task)
{   
    struct task_struct *child;
    struct list_head *list;

    printk("name: %s, pid: [%d], state: %li\n", task->comm, task->pid, task->state);
    list_for_each(list, &task->children) {
        child = list_entry(list, struct task_struct, sibling);
        DFS(child);
    }
}

/**
 * This function is called when the module is loaded. 
 *
 * @return 0  upon success
 */ 
int task_lister_init(void)
{
    printk(KERN_INFO "Loading Task Lister Module...\n");
    DFS(&init_task);

    return 0;
}

/**
 * This function is called when the module is removed.
 *
 * @void
 */
void task_lister_exit(void)
{
    printk(KERN_INFO "Removing Task Lister Module...\n");
}

// Macros for registering module entry and exit points.
module_init(task_lister_init);
module_exit(task_lister_exit);

- tam5

---

我原本以为 list_entry(list, struct task_struct, sibling); 应该是 list_entry(list, struct task_struct, children); 但它并不起作用。你能否请解释一下我错在哪里？ - Vivek Maran

Answer 2

您可以使用task->state /* -1 表示不可运行，0 表示可运行，>0 表示已停止 */来获取状态。

使用task->parent->pid来获取父进程的 pid。

- joe

---

有没有关于获取dfs的帮助？ - Hassan Jalil

Answer 3

关于uid和tgid，您可以参考task_struct中的cred结构。关于优先级，您可以参考rt_priority（用于实时优先级）和prio字段。对于其他字段，您可以参考proc目录（因为ps将从proc获取输入）。

- Amar

Answer 4

我看到被接受的答案使用了递归。即使代码更简单，也在内核代码中编写递归函数仍然是一个非常糟糕的主意。内核可用的堆栈大小有限，递归函数很容易超出限制并导致所有内容崩溃。您应该迭代实现DFS/BFS：维基百科页面（DFS，BFS）提供了代码示例和解释。

下面是一种使用支持struct作为队列的简单DFS和BFS实现（已在内核5.10上测试）。由于迭代DFS和BFS之间唯一的区别是将新元素推入队列头部或尾部，因此我同时实现了两者，您可以通过添加#define BFS轻松切换到BFS。

// Uncomment to use BFS instead of DFS
// #define BFS

static void dump_children_tree(struct task_struct *task) {
    char comm[TASK_COMM_LEN];
    struct task_struct *child;
    struct list_head *list;
    struct queue *q, *tmp;
#ifdef BFS
    struct queue **tail;
#endif
    pid_t ppid;

    q = kmalloc(sizeof *q, GFP_KERNEL);
    if (!q)
        goto out_nomem;

    q->task = task;
    q->next = NULL;
#ifdef BFS
    tail = &q->next;
#endif

    while (q) {
        task = q->task;
#ifndef BFS
        tmp = q;
        q = q->next;
        kfree(tmp);
#endif

        rcu_read_lock();
        ppid = rcu_dereference(task->real_parent)->pid;
        rcu_read_unlock();

        pr_info("Name: %-20s State: %ld\tPID: %d\tPPID: %d\n",
            get_task_comm(comm, task),
            task->state,
            task->pid,
            ppid
        );

        list_for_each(list, &task->children) {
            child = list_entry(list, struct task_struct, sibling);
            get_task_struct(child);

            tmp = kmalloc(sizeof *tmp, GFP_KERNEL);
            if (!tmp)
                goto out_nomem;

            tmp->task = child;
#ifdef BFS
            tmp->next = NULL;
            *tail = tmp;
            tail = &tmp->next;
#else // DFS
            tmp->next = q;
            q = tmp;
#endif
        }

        put_task_struct(task);
#ifdef BFS
        tmp = q;
        q = q->next;
        kfree(tmp);
#endif
    }

    return;

out_nomem:
    while (q) {
        tmp = q;
        q = q->next;
        kfree(tmp);
    }
}

注意: 上述函数假定get_task_struct()已在传递的task上被调用，并在返回之前自动为其调用put_task_struct()。

- Marco Bonelli