Segfault hidden in list.h

Segfault hidden in list.h

[Rose, Billy]

The code inside of __list_add:

next->prev = new;
new->next = next;
new->prev = prev;
pre-next = new;

needs to be altered to:

new->prev = prev;
new->next = next;
next->prev = new;
prev->next = new;

If something is accessing the list in reverse at the time of insertion and
"next->prev = new;" has been executed, there exists a moment when new->prev
may contain garbage if the element had been used in another list and is
being transposed into a new one. Even if garbage is not present, and the
element had just been initialized (i.e. new->prev = new), a false list head
will appear briefly (from the executing thread's point of view).

Billy Rose 
wrose@loislaw.com

Re: Segfault hidden in list.h

[David S. Miller]

   From: Linus Torvalds <torvalds@transmeta.com>
   Date: Sun, 12 May 2002 17:59:27 -0700 (PDT)
   
   If the coder doesn't lock his data structures, it doesn't matter _what_
   order we execute the list modifications in - different architectures will
   do different thing with inter-CPU memory ordering, and trying to order
   memory accesses on a source level is futile.

However, if the list manipulation had some memory barriers
added to it...

The people doing the lockless reader RCU stuff could benefit from such
an interface.

Re: Segfault hidden in list.h

[Linus Torvalds]

On Sun, 12 May 2002, Rose, Billy wrote:
>
> If something is accessing the list in reverse at the time of insertion and
> "next->prev = new;" has been executed, there exists a moment when new->prev

No.

If the coder doesn't lock his data structures, it doesn't matter _what_
order we execute the list modifications in - different architectures will
do different thing with inter-CPU memory ordering, and trying to order
memory accesses on a source level is futile.

		Linus

RE: Segfault hidden in list.h

[Rose, Billy]

I'm not hitting it, but I came across it while writing an application server
based on TUX 2.1.0. I noticed that Ingo didn't lock a list during reads. As
long as his code traverses forward (which it does) all is well. If, however,
some module writer out there fails to lock a list for reads and traverses
said list in reverse, a failure could result. 

By logic design this assignment ordering eliminates the need for a read
lock, hence improving performance, not just data integrity.

Billy Rose 
wrose@loislaw.com

> -----Original Message-----
> From: Jeff Garzik [mailto:jgarzik@mandrakesoft.com]
> Sent: Sunday, May 12, 2002 7:45 PM
> To: Rose, Billy
> Subject: Re: Segfault hidden in list.h
> 
> 
> Rose, Billy wrote:
> 
> >The code inside of __list_add:
> >
> >next->prev = new;
> >new->next = next;
> >new->prev = prev;
> >pre-next = new;
> >
> >needs to be altered to:
> >
> >new->prev = prev;
> >new->next = next;
> >next->prev = new;
> >prev->next = new;
> >
> >If something is accessing the list in reverse at the time of 
> insertion and
> >"next->prev = new;" has been executed, there exists a moment 
> when new->prev
> >may contain garbage if the element had been used in another 
> list and is
> >being transposed into a new one. Even if garbage is not 
> present, and the
> >element had just been initialized (i.e. new->prev = new), a 
> false list head
> >will appear briefly (from the executing thread's point of view).
> >
> 
> It sounds like you need better locking, if you are hitting this...
> 
> 

Re: Segfault hidden in list.h

[Linus Torvalds]

On Sun, 12 May 2002, David S. Miller wrote:
>
>    If the coder doesn't lock his data structures, it doesn't matter _what_
>    order we execute the list modifications in - different architectures will
>    do different thing with inter-CPU memory ordering, and trying to order
>    memory accesses on a source level is futile.
>
> However, if the list manipulation had some memory barriers
> added to it...

That would just make _those_ much slower, with some very doubtful end
results.

Show me numbers, and show me readable source, and show me a proof that the
memory ordering actually works, and I may consider lockless algorithms
worthwhile. As it is, they are damn fragile and require more care that I
personally care to expect out of 99.9% of all programmers.

And I'm sure as hell not going to put any lockless stuff in functions
meant for "normal human consumption". If we create list macros like that,
they had better be called "lockless_list_add_be_damn_careful_about_it()"
rather than "list_add()".

		Linus

RE: Segfault hidden in list.h

[Rose, Billy]

I stand corrected. I guess my philosophy is for the long sought after
"prefect world" example...

Cheers :)

Billy Rose 
wrose@loislaw.com

> -----Original Message-----
> From: Linus Torvalds [mailto:torvalds@transmeta.com]
> Sent: Sunday, May 12, 2002 7:59 PM
> To: Rose, Billy
> Cc: Kernel Mailing List
> Subject: Re: Segfault hidden in list.h
> 
> 
> 
> 
> On Sun, 12 May 2002, Rose, Billy wrote:
> >
> > If something is accessing the list in reverse at the time 
> of insertion and
> > "next->prev = new;" has been executed, there exists a 
> moment when new->prev
> 
> No.
> 
> If the coder doesn't lock his data structures, it doesn't 
> matter _what_
> order we execute the list modifications in - different 
> architectures will
> do different thing with inter-CPU memory ordering, and trying to order
> memory accesses on a source level is futile.
> 
> 		Linus
> 

RE: Segfault hidden in list.h

[Davide Libenzi]

On Sun, 12 May 2002, Rose, Billy wrote:

> The code inside of __list_add:
>
> next->prev = new;
> new->next = next;
> new->prev = prev;
> pre-next = new;
>
> needs to be altered to:
>
> new->prev = prev;
> new->next = next;
> next->prev = new;
> prev->next = new;

you need a wmb also :

new->prev = prev;
new->next = next;
wmb
next->prev = new;
prev->next = new;




- Davide

Re: Segfault hidden in list.h

[David S. Miller]

   From: Linus Torvalds <torvalds@transmeta.com>
   Date: Sun, 12 May 2002 18:08:28 -0700 (PDT)

   And I'm sure as hell not going to put any lockless stuff in functions
   meant for "normal human consumption". If we create list macros like that,
   they had better be called "lockless_list_add_be_damn_careful_about_it()"
   rather than "list_add()".
   
That was what I was suggesting.  I didn't intend for the memory
barriers to go into the existing list macros.

RE: Segfault hidden in list.h

[Rose, Billy]

I stand to correct myself further. Ingo has a wrapper function around a more
general purpose function, and the wrapper locks the list. All is good as
long as the general purpose function isn't called directly. My apologies to
Ingo for not scanning the code closer, the function names are almost
identical and I missed that...

Billy Rose 
wrose@loislaw.com

> -----Original Message-----
> From: Rose, Billy [mailto:wrose@loislaw.com]
> Sent: Sunday, May 12, 2002 8:10 PM
> To: 'Linus Torvalds'
> Cc: Kernel Mailing List
> Subject: RE: Segfault hidden in list.h
> 
> 
> I stand corrected. I guess my philosophy is for the long sought after
> "prefect world" example...
> 
> Cheers :)
> 
> Billy Rose 
> wrose@loislaw.com
> 
> > -----Original Message-----
> > From: Linus Torvalds [mailto:torvalds@transmeta.com]
> > Sent: Sunday, May 12, 2002 7:59 PM
> > To: Rose, Billy
> > Cc: Kernel Mailing List
> > Subject: Re: Segfault hidden in list.h
> > 
> > 
> > 
> > 
> > On Sun, 12 May 2002, Rose, Billy wrote:
> > >
> > > If something is accessing the list in reverse at the time 
> > of insertion and
> > > "next->prev = new;" has been executed, there exists a 
> > moment when new->prev
> > 
> > No.
> > 
> > If the coder doesn't lock his data structures, it doesn't 
> > matter _what_
> > order we execute the list modifications in - different 
> > architectures will
> > do different thing with inter-CPU memory ordering, and 
> trying to order
> > memory accesses on a source level is futile.
> > 
> > 		Linus
> > 
> -
> To unsubscribe from this list: send the line "unsubscribe 
> linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

Re: Segfault hidden in list.h

[Dipankar Sarma]

In article <Pine.LNX.4.44.0205121805220.15392-100000@home.transmeta.com> Linus Torvalds wrote:

> On Sun, 12 May 2002, David S. Miller wrote:
>> However, if the list manipulation had some memory barriers
>> added to it...

> That would just make _those_ much slower, with some very doubtful end
> results.

I agree. In most cases, list.h macros will be used under lock and
putting barriers there will penalize the common case.


> Show me numbers, and show me readable source, and show me a proof that the
> memory ordering actually works, and I may consider lockless algorithms
> worthwhile. As it is, they are damn fragile and require more care that I
> personally care to expect out of 99.9% of all programmers.
> And I'm sure as hell not going to put any lockless stuff in functions
> meant for "normal human consumption". If we create list macros like that,
> they had better be called "lockless_list_add_be_damn_careful_about_it()"
> rather than "list_add()".

It isn't really necessary to to put memeory barriers in list macros
for use with RCU. In many data structures, list traversal is done in
only one direction and therefore memory barriers can be put after
list_add() or such macros. If indeed traversal is more complicated
than that, it might not be a good idea to do lockfree traversal in
the first place.

As for readable lockless algorithms, sure they exist. See
http://prdownloads.sourceforge.net/lse/rt_rcu-2.5.3-1.patch.

Thanks
-- 
Dipankar Sarma  <dipankar@in.ibm.com> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.