Kernel module that iterates over the tree of children of a task using depth first search

Question

So I know how to create a kernel and to iterate over the processes linearly by simply including linux/sched.h and using the following code:

struct task_struct *task;

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

How can I print these tasks using a depth first search? I want my output to be similar to the one of ps -eLf.

The following patch of code has been given for reference:

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 */
}

and I know that task->comm returns the name and task->pid returns the PID for that task.

What fields are used to for the state and parent PID?

Answer 1

you can get the state with task->state /* -1 unrunnable, 0 runnable, >0 stopped */

get the parent pid with task->parent->pid

Answer 2

For uid, tgid you can refer cred structure in task_struct. For priority you can refer rt_priority(for real time priority) and prio field. For other fields you may refer proc directory (Because ps will take input from proc).

Answer 3

I see the accepted answer is using recursion. Even if the code is simpler, it is still a very bad idea to write recursive functions in kernel code. The kernel has a limited stack size available and a recursive functions can easily overflow that and crash everything. You should implement DFS/BFS iteratively instead: the Wikipedia pages (DFS, BFS) have explanations and examples of code.

Here's a simple DFS and BFS implementation using a support struct as a queue (tested on kernel 5.10). Since the only difference between iterative DFS and BFS is pushing new elements on the head or the tail of the queue respectively, I just implemented both and you can switch to BFS by simply adding #define 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);
    }
}

NOTE: the above function assumes that get_task_struct() was already called on the passed task, and automatically calls put_task_struct() for you on it before returning.