C: Linux built in linked list in kernel data structures usage

Question

I am attempting to add a system call to my linux kernel and it would be advantageous to use the built-in linked list as I am modifying the task_struct (by adding a linked list), and the task_struct already has quite a few struct list_head's in there for other purposes. For uniformity, I would like to stick with this data structure.

My issue is that I really don't fully understand how to use this structure. I see that they have "struct list_head children" for example. However, the implementation of this structure is simple a "*next" and "*last".

I've looked into examples online and every single one says, well make

struct node{
    int data;
    struct list_head list;
}; 

But wouldn't this indicate that the data structure I should be including in my task_struct should be

struct node list;

?

I don't quite understand how I would initialize the structure to contain the data I would like it to contain if I use list_head.

Essentially I want to add a linked list of system calls and tack them on to the process in the form of a linked list of char* (readable format).

For now, the semantics of obtaining the system call information is unimportant... I just need to figure out how to get the linked list working with the task_struct.

Edit: For example of what I am trying to do:

I've obtained a list of system calls performed by a function. I am keeping these in separate char* variables. I would like to add a list within the processes task_struct that keeps track of all of these system calls.

For example

Process 'abc' calls printf ~> equates to "WriteScreen" getchar ~> equates to "ReadKey"

I now have a userland piece of code that has these two strings. I call a system call that I will write (once per tag) to "tag" the process with these system calls.

After both calls, the task_struct of 'abc' has a list

abc->task_struct->tag_list

This list contains "WriteScreen" and "ReadKey".

Later I will use these tags to print a list of processes that have called WriteScreen, ReadKey, etc. The implementation of these will happen after I find out how to use the list to appropriately store the strings attached to a process.

Answer 1

So instead of creating a list of processes (task_struct) what you're trying to accomplish is a list per process.

This means that each process will have its own list, i.e. its own list head.

This list will store, in addition to next/prev pointers, a single piece of data, actually a string (could be the string itself or a pointer to a string elsewhere).

The list node will be therefore:

struct my_node {
    struct list_head list;
    char data[100]; // arbitrarily set to 100; could be also char*
}

The task_struct should be augmented with a new list head:

struct task_struct {
  // many members that contains info about a process
  ...

  struct list_head my_list;
}

Yes. You'll notice that both cases (when the process belongs to a list, and when the list belongs to the process) the member will be the same; only its use is different.

Now, when a process is created you should initialize the list head (as each process will have a new list):

struct task_struct *new_process;
INIT_LIST_HEAD(&new_process->my_list);

To insert a new node (supposing you already created it, that is, allocated memory and initialized its data):

struct my_node *node; 
struct task_struct *a_process;

[... my_node initialized ...]
[... a_proccess obtained somehow ...]

list_add_tail(&node->list, &a_process->my_list);

To iterate over the elements:

struct my_node *p;
struct task_struct *a_process

// list is the member name (yes, the member name) of your list inside my_node
list_for_each_entry(p, &a_process->my_list, list) {
  // do whatever you want with p
}

EDIT:

Note, however, that you have other ways to do what you are trying to do, without resorting to complex linked lists.

For instance, you could allocate a single char array and encode a list of strings by means of separating them by some char (commas, periods, and so on). This way:

"WriteScreen,ReadKey\0"

In this case you should look after your buffer limits, to never overflow it. On the other hand you do not have to take care of allocating and freeing nodes of a list.

Answer 2

The big reference about Linux Kernel linked list is http://www.makelinux.net/ldd3/chp-11-sect-5.

You initialize the struct like this:

struct node node_var = {
    .data = 0,
    .list = LIST_HEAD_INIT(node_var.list)
}

You traverse the list like this:

struct list_head *phead;
list_for_each(phead, node_var.list)
{
   struct node * pnode = list_entry(phead, struct node node_var, list);
   // Do what you may with the pnode.
}

It is true that it does look quite strange. We get pointers to struct node type by using a pointer to the field struct list_head of that struct. This magic is done by the container_of macro that is called inside list_entry.

Hope I did help.

Answer 3

EDIT: This answer was provided before the OP provided a more clear explanation of what he/she was trying to do.

You should only amend task_struct with a new member:

struct task_struct {
  // many members that contains info about a process
  ...
  // then come the lists that a process may participate
  ...
  // then you amend with your new list
  struct list_head my_list;
}

This augmentation in itself will do nothing, as no one will change or otherwise access this member.

You should declare your list head elsewhere (a global, for instance) and then you can start addind processes (task_struct) to your list.

LIST_HEAD(my_list_head); // this will declare, define and initialize a new variable:
                         // an empty list.

The Linux Kernel linked list macros will take care of everything for you.

task_struct *a_given_process; // assigned elsewhere, maybe passed as parameter to current function
list_add_tail(&a_given_process->my_list, my_list_head); // an example

EDIT:

To iterate over the items:

struct task_struct *p;

// my_list_head is the head of your list (declared with LIST_HEAD)
// my_list is the member name (yes, the member name) of your list inside task_struct
list_for_each_entry(p, my_list_head, my_list) {
  // do whatever you want with p
}