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? 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; unsigned int starved; }; -- Amirali Shambayati Bachelor Student Computer Engineering Department Sharif University of Technology Tehran, Iran
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
"noop_data" has a reference to start point of bundles list, called "writeQueue"
struct noop_data { struct list_head readQueue; struct list_head writeQueue; struct bundle bun;
Why are you embedding a struct bundle here?
This was my focus, too. In my previous mail, I said that this is wrong. But I think that there is another problem here as well: Amirali wants writeQueue to be the "start point of bundles list", but it won't. writeQueue is just a linked list (LL) of nodes of type 'struct noop_data'. (I am hoping that you, Jonathan, have more experience with this than me. What do you think?) Looking at the definition of list_head, it is just a pair of next-prev pointers. As such, 'head' is a misnomer. (I don't usually barge-in, criticizing, so don't bite my head off, please!) I need to dig a bit more into this. later, ali
Whoops!
struct noop_data {
struct list_head writeQueue;
writeQueue is just a linked list (LL) of nodes of type 'struct noop_data'. (I am hoping that you, Jonathan, have more experience with
Uh, not quite! :-) Ignore my previous post. I'll try to clarify in another email to the OP.
I need to dig a bit more into this.
I did warn! :-)
Hi Amirali,
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?
I'm definitely on the newb end of things as far as kernel data structures go. So getting another opinion would be prudent. As for a manual, Wolfgang Mauerer's book, Professional Linux Kernel Architecture, is an excellent resource. It does touch on double linked-lists (LL), though I've only glanced at it.
"noop_data" has a reference to start point of bundles list, called "writeQueue"
I don't think so. See below.
struct bundle {
struct list_head bundlesQueue; struct list_head reqsQueue;
What I see here is that you are putting such nodes on 2 LLs.
struct noop_data { struct list_head readQueue; struct list_head writeQueue;
What I see here is that you are putting such nodes on 2 LLs, but
struct bundle bun;
each node has a single node of the type 'struct bundle' ie a struct which has int bundleNumber; int size; ... int filled[8]; Likely, this is not what you want. later, ali
All right, let's take another stab at this.
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
My interpretation of what you got is as follows, based on what you've said you'll be assigning each list_head to: struct noop_data { struct list_head readQueue; // You haven't explicitly stated which // LL this will be assigned to. struct list_head writeQueue;// The head of a LL of 'struct bundle' // nodes. struct bundle { int bundleNumber; int size; struct list_head bundlesQueue; // The LL of 'struct bundle' struct list_head reqsQueue; // The head of a LL of // 'struct request'? int filled[8]; } bun; unsigned int starved; }; Depending on how you're going to assign these, you may end up with spaghetti. As I indicated before, the nested inclusion of 'struct bundle' is likely wrong. later, ali
"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; unsigned int starved; };
Ali thanks for your valuable comments. Would you suggest me an alternative method to implement the structure I explained? On Mon, Jun 6, 2011 at 10:05 AM, Ali Bahar <ali@internetdog.org> wrote:
All right, let's take another stab at this.
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
My interpretation of what you got is as follows, based on what you've said you'll be assigning each list_head to:
struct noop_data { struct list_head readQueue; // You haven't explicitly stated which // LL this will be assigned to. struct list_head writeQueue;// The head of a LL of 'struct bundle' // nodes. struct bundle { int bundleNumber; int size; struct list_head bundlesQueue; // The LL of 'struct bundle' struct list_head reqsQueue; // The head of a LL of // 'struct request'? int filled[8]; } bun; unsigned int starved; };
Depending on how you're going to assign these, you may end up with spaghetti. As I indicated before, the nested inclusion of 'struct bundle' is likely wrong.
later, ali
"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; unsigned int starved; };
-- Amirali Shambayati Bachelor Student Computer Engineering Department Sharif University of Technology Tehran, Iran
On Mon, Jun 06, 2011 at 10:43:20AM +0430, Amirali Shambayati wrote:
Ali thanks for your valuable comments. Would you suggest me an alternative method to implement the structure I explained?
I don't know, sufficiently, what you _intend_ to implement. As described originally,
"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)
your data structures are capable of fitting what you say; however, they may not match that which you have visualized in your mind. It'd take even more guess-work on my part to divine the latter. Let me go out on a limb here, and suggest the following. I don't think you have any kernel-specific issues. This is the sort of thing which is best handled by sitting down with someone, and articulating what you have in mind. The bugs (in your visualization-to-implementation) are then sure to come out.
Sharif University of Technology
Judging by the word of mouth, and the grad students I've seen, Sharif should be full of exceptionally bright students. Grab the guy next to you, and talk it out. later, ali
Hello all, I debugged my code (which I explained in previous mails), and I found out this: In the function which I add bundles to writeQueue and requests to bundle, everything goes well and it seems that, this structure works well. But! in another function(which its task is dispatching requests to lower level), as I traverse in reqsQueue, in bundle, requests which have already been added to list are not available! Any idea? Regards, On Tue, Jun 7, 2011 at 6:21 AM, Ali Bahar <ali@internetdog.org> wrote:
On Mon, Jun 06, 2011 at 10:43:20AM +0430, Amirali Shambayati wrote:
Ali thanks for your valuable comments. Would you suggest me an alternative method to implement the structure I explained?
I don't know, sufficiently, what you _intend_ to implement. As described originally,
"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)
your data structures are capable of fitting what you say; however, they may not match that which you have visualized in your mind. It'd take even more guess-work on my part to divine the latter.
Let me go out on a limb here, and suggest the following.
I don't think you have any kernel-specific issues. This is the sort of thing which is best handled by sitting down with someone, and articulating what you have in mind. The bugs (in your visualization-to-implementation) are then sure to come out.
Sharif University of Technology
Judging by the word of mouth, and the grad students I've seen, Sharif should be full of exceptionally bright students. Grab the guy next to you, and talk it out.
later, ali
-- Amirali Shambayati Bachelor Student Computer Engineering Department Sharif University of Technology Tehran, Iran
Hi, I found my fault :) On Sun, Jun 12, 2011 at 8:12 PM, Amirali Shambayati < amirali.shambayati@gmail.com> wrote:
Hello all, I debugged my code (which I explained in previous mails), and I found out this: In the function which I add bundles to writeQueue and requests to bundle, everything goes well and it seems that, this structure works well. But! in another function(which its task is dispatching requests to lower level), as I traverse in reqsQueue, in bundle, requests which have already been added to list are not available!
Any idea?
Regards,
On Tue, Jun 7, 2011 at 6:21 AM, Ali Bahar <ali@internetdog.org> wrote:
On Mon, Jun 06, 2011 at 10:43:20AM +0430, Amirali Shambayati wrote:
Ali thanks for your valuable comments. Would you suggest me an alternative method to implement the structure I explained?
I don't know, sufficiently, what you _intend_ to implement. As described originally,
"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)
your data structures are capable of fitting what you say; however, they may not match that which you have visualized in your mind. It'd take even more guess-work on my part to divine the latter.
Let me go out on a limb here, and suggest the following.
I don't think you have any kernel-specific issues. This is the sort of thing which is best handled by sitting down with someone, and articulating what you have in mind. The bugs (in your visualization-to-implementation) are then sure to come out.
Sharif University of Technology
Judging by the word of mouth, and the grad students I've seen, Sharif should be full of exceptionally bright students. Grab the guy next to you, and talk it out.
later, ali
-- Amirali Shambayati Bachelor Student Computer Engineering Department Sharif University of Technology Tehran, Iran
-- Amirali Shambayati Bachelor Student Computer Engineering Department Sharif University of Technology Tehran, Iran
participants (3)
-
Ali Bahar -
Amirali Shambayati -
Jonathan Neuschäfer