lkml.org 
[lkml]   [1999]   [Nov]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: AVL trees vs. Red-Black trees
On Tue, 30 Nov 1999, Andrea Arcangeli wrote:

> On Tue, 30 Nov 1999, Gerard Roudier wrote:
>
> >> "movl $0,%0\n\t"
> >> "movl $0,%1\n\t"
> >> "lock; addl $0,(%%esp)\n\t" /* flush our write buffers*/
> >
> >The 'lock' flushes write buffers of CPU2 to the cache, but:
>
> The lock there make no difference, I suggest to delete such last line as
> it's misleading IMHO.

The comment should instead read "memory barrier". It's there because it's
modeling existing code. It should arguably be modified there to a barrier
that is a non-existent on x86 if it actually needs a barrier at all. It
should only make a difference in timing, which will become less
deterministic - buffers get flushed opportunistically.

I've just tried it - the crash point does indeed become more sporadic.

At any rate, we have to figure out the rules we're going to use for the
portable kernel and not focus so much on the x86 details. It's not
immediately obvious where memory barriers should go on the generic system
so it might be nice if someone laid down the minimum ordering assumptions
for potential target machines.

Do we assume that processors always see their own local writes in program
order (locally fully ordered)? Does the bus always see writes in order
(write ordered)? Other processors (processor ordered)? Do we try to hide
all the interprocessor races inside a small set of macros like
set_current_state?

--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:55    [W:0.065 / U:0.016 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site