Gentoo Linux Documentation -- Gentoo Kernel Development/Hacking FAQ

Gentoo Kernel Development/Hacking FAQ

1.list.h by example

Before we jump right in and start messing with list.h, we have to know what we're going to be storing in our list. Hence we start off by defining the base element.

Code listing 1.1: my-element.h: Define the elements in the list

// these are defines that protect against multiple inclusion errors ...
// if this file is included by multiple files, the compile wont bomb out
#ifndef __MY_ELEMENT_H__
#define __MY_ELEMENT_H__

// this is needed in case you want to utilize list.h from userspace
#ifndef __KERNEL__
#define __KERNEL__
#include <linux/list.h>
#undef __KERNEL__
#else
#include <linux/list.h>
#endif

// here we define the little element that will make up the list
struct my_element {
	struct list_head	list;
	unsigned int		val;
};

#endif // __MY_ELEMENT_H__

Important: Please note that the list_head comes first ... you must always have this as the first element in your struct.

So now we have a structure called my_element that contains a list_head and a

Declaring the list

Now we know what kind of data we'll be storing in our list. But how exactly do we declare this new magical list ? Here we go:

Code listing 1.2: Declaring a linked list

#include "my-element.h"

// we can do it like this ...
// prototype: LIST_HEAD(name of variable)
void myfunc(void)
{
	LIST_HEAD(my_list_head);
}

// or we can do it like this
// prototype: INIT_LIST_HEAD(address of list head)
void anotherfunc(void)
{
	struct list_head another_list_head;
	INIT_LIST_HEAD(&another_list_head);
}

Woah now, that was pretty freaking exiciting ! It doesn't matter which way you choose to define your list, so long as you define it. Sometimes you may find it easier to do it the first way, sometimes you'll need the flexibilty of the second.

Adding to the list

Lets move on to something a *little* more useful. That is, lets add something to our spiffy list. It's really quite simple ... the hard part is visualizing the structure in your mind.

Code listing 1.3: Adding some elements to the list

#include "my-element.h"

// prototype: void list_add(address of element's list_head struct,
                            address of list head)
void myfunc(void)
{
	struct my_element ele;
	LIST_HEAD(my_list_head);

	list_add(&ele.list, &my_list_head);
}

Warning: You're responsible for making sure that ele isn't already in a list. If ele is already in a list (even if it's in the same list you're adding to), and you go running list_add on it, then chances are you'll encounter undefined behaviour (up to and including segfaults ... or kernel panics if you're in kernelspace).

Pretty simple stuff. This will take the list accessible via my_list_head and add ele to it as the new head. For example, if our list in memory was {4, 3, 2} with 4 being the head and we added a 5, we'd end up with 5 as the new head in {5, 4, 3, 2}.

Deleting from the list

Before we worry about accessing the data in the list and getting *anything* useful out of the code, lets worry about how to delete an item from the list.

Code listing 1.4: Deleting some elements to the list

#include "my-element.h"

// prototype: list_del(address of element's list_head struct)
void myfunc(void)
{
	struct my_element ele;
	LIST_HEAD(my_list_head);

	list_add(&ele.list, &my_list_head);
	list_del(&ele.list);
}

Warning: You're responsible for making sure that ele is really in the list. If you go trying to delete some element that was never added to a list, chances are you'll get invalid pointer dereferences (or that dreaded segfault and/or kernel panic in layman's terms).

It might be useful to note that when we 'delete' something from the list, we aren't actually freeing any memory. I might not have to tell you this, but not everyone may know this.

Retrieving elements from the list

OK, so we can make the list bigger and we can make it smaller. How exactcly do we extract the things we shoved into the list though ?

Code listing 1.5: Extraction of elements from the list

#include "my-element.h"

// prototype: (*my_element) list_entry(pointer to a list_head in the list,
                                       type of structure stored in the list,
                                       name of the list_struct within the struct)
void myfunc(void)
{
	struct my_element ele, *tmp_ele;
	LIST_HEAD(my_list_head);

	list_add(&ele.list, &my_list_head);

	// tmp_ele points to the 'ele' variable after both of these function calls
	tmp_ele = list_entry(&my_list_head, struct my_element, list);
	tmp_ele = list_entry(&ele.list, struct my_element, list);
}

Seems pretty freaking pointless doesn't it ? I mean, why make a list and add an element to it when it looks like you need the element to get it back ? Well, this is the point where you get a little creative (with emphasis on the you).

Free creativity

Bah, I'll be a little creative for you.

Code listing 1.6: For-each loops

#include "my-element.h"

// if, for some reason, you want to use list.h in userspace, replace
// the 'list_for_each' and 'list_for_each_prev' with the following macro's.

#define FOR_EACH(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
#define FOR_EACH_PREV(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = pos->prev)

void myfunc(void)
{
	struct my_element *tmp_ele;
	struct list_head *tmp_list_ele;
	LIST_HEAD(my_list_head);

	...
	// generate a list
	...

	list_for_each(tmp_list_ele, &my_list_head) {
		tmp_ele = list_entry(tmp_list_ele, struct my_element, list);
		...
		// play with tmp_ele
		...
	}

	list_for_each_prev(tmp_list_ele, &my_list_head) {
		tmp_ele = list_entry(tmp_list_ele, struct my_element, list);
		...
		// play with tmp_ele
		...
	}

	...
	// clean up the list
	...
}

Or if you wish to selectively progress along a list you can do something like this:

Code listing 1.7: Conditional walks

#include "my-element.h"

void myfunc(void)
{
	struct my_element *tmp_ele;
	struct list_head *tmp_list_ele;
	LIST_HEAD(my_list_head);

	...
	// generate a list
	...

	tmp_list_ele = my_list_head.next;
	while (tmp_list_ele != &my_list_head) {
		tmp_ele = list_entry(tmp_list_ele, struct my_element, list);

		if (tmp_ele->val > 0) {
			tmp_list_ele = tmp_list_ele->next;
		} else {
			tmp_ele->val = tmp_ele->val + 10;
			tmp_list_ele = tmp_list_ele->prev;
		}
	}

	...
	// clean up the list
	...
}

Note: If anyone has a better example, feel free to e-mail me it Mike Frysinger.

Hrm, well this example kind of sucks, but you get the idea of how to manually progress along a list. You can navigate via the prev and next pointers. If the structures have you a little confused, just remember that the list_head's all point to each other but they don't actually store anything. The structures we're interested in storing/retrieving are wrapped around the list_head structures in memory, and list_entry() just does some magic to retrieve them.

Bringing it all together

Here is some final code + execution. By now, this code should be cheese.

Code listing 1.8: my-element.h: Define the elements in the list

#ifndef __MY_ELEMENT_H__
#define __MY_ELEMENT_H__

// this is needed in case you want to utilize list.h from userspace
#ifndef __KERNEL__
#define __KERNEL__
#include <linux/list.h>
#undef __KERNEL__
#else
#include <linux/list.h>
#endif

// /*
 * adopted from code off of LKML
 * Bill Wendling (wendling_at_ganymede.isdn.uiuc.edu)
 * http://lists.insecure.org/lists/linux-kernel/2000/Feb/0472.html
 * (Improved <linux/lists.h> thread in Feb 2000)
 */
#define FOR_EACH(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
#define FOR_EACH_REVERSE(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = pos->prev)

// /*
 * Here we define the little element that will
 * make up the list of elements we use later ...
 *
 * Please note that the list_head comes first ...
 * you must *always* have this as the first element
 */
struct my_element {
	struct list_head	list;
	unsigned int		val;
};

#endif // __MY_ELEMENT_H__

Code listing 1.9: First we write list_example.c

#include <stdio.h>
#include "my-element.h"

int main(int argc, char *argv[])
{
	struct my_element ele1, ele2, ele3, ele4, *tmp_ele;
	struct list_head *list_ele;

	// head setup (version 1)
	LIST_HEAD(my_list_head);
	// head setup (version 2)
	struct list_head another_list_head;
	INIT_LIST_HEAD(&another_list_head);

	ele1.val = 1;
	ele2.val = 2;
	ele3.val = 3;
	ele4.val = 4;

	if (list_empty(&my_list_head))
		printf("my_list is empty !\n");
	else
		printf("my_list isn't empty just yet !\n");

	// we add these in reverse order because list_add
	// adds elements to the start of the list
	list_add(&ele4.list, &my_list_head);
	list_add(&ele3.list, &my_list_head);
	list_add(&ele2.list, &my_list_head);
	list_add(&ele1.list, &my_list_head);

	printf("Traversing my_list (forward motion)\n");
	FOR_EACH(list_ele, &my_list_head) {
		tmp_ele = list_entry(list_ele, struct my_element, list);
		printf("\tFound an element with value %i\n", tmp_ele->val);
	}

	printf("Traversing my_list (reverse motion)\n");
	FOR_EACH_REVERSE(list_ele, &my_list_head) {
		tmp_ele = list_entry(list_ele, struct my_element, list);
		printf("\tFound an element with value %i\n", tmp_ele->val);
	}

	list_del(&ele3.list);
	list_del(&ele1.list);
	list_add_tail(&ele3.list, &my_list_head);

	printf("Traversing a smaller my_list (forward motion)\n");
	FOR_EACH(list_ele, &my_list_head) {
		tmp_ele = list_entry(list_ele, struct my_element, list);
		printf("\tFound an element with value %i\n", tmp_ele->val);
	}

	if (list_empty(&my_list_head))
		printf("my_list is empty !\n");
	else
		printf("my_list isn't empty just yet !\n");

	printf("Moving some elements from my_list to another_list\n");
	list_del(&ele2.list);
	list_add(&ele2.list, &another_list_head);
	list_add_tail(&ele1.list, &another_list_head);
	list_move(&ele4.list, &another_list_head);

	if (list_empty(&another_list_head))
		printf("another_list is empty !\n");
	else
		printf("another_list isn't empty just yet !\n");

	printf("Traversing another_list (forward motion)\n");
	FOR_EACH(list_ele, &another_list_head) {
		tmp_ele = list_entry(list_ele, struct my_element, list);
		printf("\tFound an element with value %i\n", tmp_ele->val);
	}

	return 0;
}

Code listing 1.10: Then we use list_example.c

# gcc -o list_example list_example.c 
# ./list_example 
my_list is empty !
Traversing my_list (forward motion)
        Found an element with value 1
        Found an element with value 2
        Found an element with value 3
        Found an element with value 4
Traversing my_list (reverse motion)
        Found an element with value 4
        Found an element with value 3
        Found an element with value 2
        Found an element with value 1
Traversing a smaller my_list (forward motion)
        Found an element with value 2
        Found an element with value 4
        Found an element with value 3
my_list isn't empty just yet !
Moving some elements from my_list to another_list
another_list isn't empty just yet !
Traversing another_list (forward motion)
        Found an element with value 4
        Found an element with value 2
        Found an element with value 1

2.list.h in kernelspace

3.semaphores (and mutexes)

4.spin locks

5.kmalloc

Updated 31 Jan 2003

Mike Frysinger
Author

Summary: A quick howto for many common linux kernel functions/data types.

Donate to support our development efforts.

Purchase RAM from Crucial.com and a percentage of your sale will go towards further Gentoo Linux development.

Looking for the right Web designer? Marketingtool.com is the world's largest directory of Web developers and other marketing-oriented firms. Use Marketingtool.com's free "Editor's Pick" service to find the Web design team that meets your exact needs.

Are you a Web designer? Then place a featured listing on Marketingtool.com to get noticed world-wide!

When you use "Editor's Pick" or place a featured listing, Marketingtool.com will donate a portion of revenue to the Gentoo Linux free software project.