Linux kernel linked lists - and sorting

Question

I'm implementing some system calls which are mainly supposed to maintain a list of processes, and a list of open files with each process. However I'm having a hard time debugging the code, which requires recompiling over and over again.

Here are probably my main problems:

1. When and how can I initialize the list keeping the processes? Currently I'm checking if the list is empty before initializing but it doesn't work. I also tried head == head->prev->next but failed.

2. What's the correct way to call the list_sort considering the related 'compare' function? I'm getting the error

[ 1827.710802] BUG: unable to handle kernel paging request at fffff550

[ 1827.710808] IP: [] compare+0x8/0x20

[ 1827.710814] *pde = 00a32067 *pte = 00000000

This is the code. I'd really appreciate you reviewing it, especially the init system call whose correct behavior the others rely on.

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/pid.h>
#include <linux/list.h>
#include <linux/fs.h>
#include <linux/proc_fs.h>
#include <linux/fdtable.h>
#include <linux/list_sort.h>
#include <linux/slab.h>


struct fileDescriptor {
    int fd;
    struct list_head list;
};

struct processInfo {
    struct task_struct task;
    int len_files;
    struct fileDescriptor listHead;
    struct list_head list;
};

struct processInfo listHead;

int compare(void* priv, struct list_head *a, struct list_head *b)
{
    struct processInfo *p1 = container_of(a, struct processInfo, list);
    struct processInfo *p2 = container_of(b, struct processInfo, list);

    if (p1->task.pid > p2->task.pid) return -1;
    else return 1;
}


asmlinkage long sys_init_process_list(pid_t p)
{   
    struct pid* pid;
    struct task_struct *task;
    struct files_struct *processFiles;
    struct fdtable *filesTable;
    struct processInfo *newProcess;

    if(list_empty(&listHead.list))
    {
        printk("____list_empty_____\n");
        INIT_LIST_HEAD(&listHead.list);
    }
    else
        printk("____list_not_empty_____\n");


    pid = find_get_pid(p);
    if (pid == NULL)
    {
        sys_init_process_list(1);
        return 1;
    }
    else 
    {
        struct list_head *list;
        struct task_struct *childTask;
        struct fileDescriptor *newfd;
        int i = 0;
        task = pid_task(pid, PIDTYPE_PID);
        newProcess = (struct processInfo*) kmalloc(sizeof(*newProcess), GFP_KERNEL);
        //copy task structure
        newProcess->task = *task;
        //adding file descriptors
        INIT_LIST_HEAD(&(newProcess->listHead).list);
        processFiles = task->files;
        filesTable = files_fdtable(processFiles);
        while (filesTable->fd[i] != NULL)
        {
            newfd = (struct fileDescriptor*) kmalloc(sizeof(*newfd), GFP_KERNEL);
            newfd->fd = i;
            INIT_LIST_HEAD(&newfd->list);
            list_add_tail(&(newfd->list), &(newProcess->listHead).list);
            i++;
        }
        newProcess->len_files = i;
        INIT_LIST_HEAD(&newProcess->list);
        // add the new node to mylist
        list_add_tail(&(newProcess->list), &(listHead.list));        
        //adding childern
        list_for_each(list, &task->children)
        {
            childTask = list_entry(list, struct task_struct, sibling);
            sys_init_process_list(childTask->pid);
        }
        return 0;
    }
}
//////////////////////////////////////////
asmlinkage long sys_sort_process_list(void)
{
    if(list_empty(&listHead.list))
    {
        printk("empty list\n");
        return 1;
    }
    list_sort(NULL, &listHead.list, compare);
    return 0;
}
////////////////////////////////////////
asmlinkage long sys_print_process_list(void)
{

    struct processInfo *aProcess;

    if (sys_sort_process_list())
    {
        printk("empty list\n");
        return 1;
    }

    list_for_each_entry(aProcess, &listHead.list, list)
    {
        printk("%d, %d\n", (aProcess->task).pid, aProcess->len_files);
    }
    return 0;
}
//////////////////////////////////////////////////
asmlinkage long sys_clear_process_list(void)
{   
    struct processInfo *aProcess, *tmp;

    if(list_empty(&listHead.list))
    {
        printk("empty list\n");
        return 1;
    }

    printk("deleting the list");

    list_for_each_entry_safe(aProcess, tmp, &listHead.list, list)
    {
        printk("freeing %d", (aProcess->task).pid);
        list_del(&aProcess->list);
        kfree(aProcess);
    }

    return 0;
}

EDIT: I managed to somehow solve my problem with 'static definition' which is done at compile time, namely I turned

struct processInfo listHead;

to

struct processInfo listHead =
{
    .list = LIST_HEAD_INIT(listHead.list)
}

and now everything seems to work just fine. I'm not sure if this is the best way though, so I'm going to keep the question open so other possible solutions may be added.

Answer 1

Unlike to many other object, zero-initialization of linked list leaves it in invalid state. That is, none of linked list's functions can be used for zero-initialized list. Even list_empty one.

Proper initialization of linked list includes LIST_HEAD_INIT (as a struct initializer) or INIT_LIST_HEAD (at runtime).