kernel list data structure

kernel list data structure

[Amirali Shambayati]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20110605/e4eb9106/attachment.html 

kernel list data structure

[Jonathan Neuschäfer]

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

kernel list data structure

[Ali Bahar]

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

kernel list data structure

[Ali Bahar]

> > "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

kernel list data structure

[Ali Bahar]

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! :-)

kernel list data structure

[Ali Bahar]

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;
> };

kernel list data structure

[Amirali Shambayati]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20110606/4be09663/attachment.html 

kernel list data structure

[Amirali Shambayati]

As I have read this pdf, I think I have assigned them right. I don't know
what's wrong? :-?
https://prof.hti.bfh.ch/myf1/adv-linux/courseNotes/*klist*-*intro*-1.3.*pdf*

On Mon, Jun 6, 2011 at 10:52 AM, Amirali Shambayati <
amirali.shambayati@gmail.com> wrote:

> As I have read the attached pdf, I think I have assigned them right. I
> don't know what's wrong? :-?
>
>
> On Mon, Jun 6, 2011 at 10:43 AM, Amirali Shambayati <
> amirali.shambayati at gmail.com> wrote:
>
>> 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
>>
>>
>
>
> --
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20110606/3f9f0ac5/attachment-0001.html 

kernel list data structure

[Amirali Shambayati]

I forgot to say that I use INIT_LIST_HEAD(&nd->writeQueue) and when I malloc
a bundle, I use INIT_LIST_HEAD(&bun->reqsQueue)
to make them as list heads. "nd" and "bun" are instantiations for noop_data
and bundle.

On Mon, Jun 6, 2011 at 11:01 AM, Amirali Shambayati <
amirali.shambayati@gmail.com> wrote:

> As I have read this pdf, I think I have assigned them right. I don't know
> what's wrong? :-?
> https://prof.hti.bfh.ch/myf1/adv-linux/courseNotes/*klist*-*intro*-1.3.*
> pdf*
>
>
> On Mon, Jun 6, 2011 at 10:52 AM, Amirali Shambayati <
> amirali.shambayati at gmail.com> wrote:
>
>> As I have read the attached pdf, I think I have assigned them right. I
>> don't know what's wrong? :-?
>>
>>
>> On Mon, Jun 6, 2011 at 10:43 AM, Amirali Shambayati <
>> amirali.shambayati at gmail.com> wrote:
>>
>>> 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
>>>
>>>
>>
>>
>> --
>> 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
>
>


-- 
Amirali Shambayati
Bachelor Student
Computer Engineering Department
Sharif University of Technology
Tehran, Iran
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20110606/c619e7f4/attachment.html 

kernel list data structure

[Jonathan Neuschäfer]

On Mon, Jun 06, 2011 at 11:01:37AM +0430, Amirali Shambayati wrote:
> As I have read this pdf, I think I have assigned them right. I don't know
> what's wrong? :-?
> https://prof.hti.bfh.ch/myf1/adv-linux/courseNotes/*klist*-*intro*-1.3.*pdf*

A good introduction, thanks.

Jonathan Neusch?fer

kernel list data structure

[Ali Bahar]

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

kernel list data structure

[Amirali Shambayati]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20110612/5c84a79c/attachment-0001.html 

kernel list data structure

[Amirali Shambayati]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20110613/f1973b83/attachment.html