From mboxrd@z Thu Jan  1 00:00:00 1970
From: j.neuschaefer@gmx.net (Jonathan =?utf-8?Q?Neusch=C3=A4fer?=)
Date: Mon, 6 Jun 2011 03:47:34 +0200
Subject: kernel list data structure
In-Reply-To: <BANLkTimLaxnDx99t-A7MCzjr2kbOcDo=gA@mail.gmail.com>
References: <BANLkTimLaxnDx99t-A7MCzjr2kbOcDo=gA@mail.gmail.com>
Message-ID: <20110606014734.GE15862@debian.debian>
To: kernelnewbies@lists.kernelnewbies.org
List-Id: kernelnewbies.lists.kernelnewbies.org

On Sun, Jun 05, 2011 at 06:09:50PM +0430, Amirali Shambayati wrote:
> Hello all,
> I wanted to use list data structure implemented inside kernel. It seems that
> it is too different with usual concept from a list data structure. I studied
> about it, and I thought that I got familiar enough to use it. I have
> implemented a two-dimensioned list, using what I understood about kernel
> list.  But as I debugged my code, it seems that my concept is wrong. Would
> anyone guide me how to implement a two-dimensioned list, or introduce me a
> manual to learn about it more?

http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?) includes
a bit of description of the linked lists used in the kernel, maybe this
helps a bit.

A good example of a structure with two list_heads is struct task_struct
(include/linux/sched.h, line 1311):
	...
	/*
	 * children/sibling forms the list of my natural children
	 */
	struct list_head children;	/* list of my children */
	struct list_head sibling;       /* linkage in my parent's children list */
	...

> 
> I have two data structures called "noop_data" and "bundle". I have a list of
> bundles, which each one has a list of requests.
> I implemented it, this way:
> "noop_data" has a reference to start point of bundles list, called
> "writeQueue"
> "bundle" has a reference to start point of requests list, called
> "reqsQueue".
> "bundle" knows its related list using "bundlesQueue".
> "request" knows its related list using "queuelist". (request struct is
> already implemented in kernel)
> 
> struct bundle {
>     int bundleNumber;
>     int size;
>     struct list_head bundlesQueue;
>     struct list_head reqsQueue;
>     int filled[8];
> };
> 
> struct noop_data {
>     struct list_head readQueue;
>     struct list_head writeQueue;
>     struct bundle bun;

Why are you embedding a struct bundle here?

>     unsigned int starved;
> };

I can't see anything fundamentally wrong with this. Maybe your list-
walking code is wrong, somewhere.

HTH,
	Jonathan Neusch?fer