Re: AVL trees vs. Red-Black trees

Ingo Molnar (mingo@chiara.csoma.elte.hu)
Mon, 29 Nov 1999 21:54:11 +0100 (CET)


On Mon, 29 Nov 1999, Jamie Lokier wrote:

> [...] "lock;" guarantees
> atomicity not serialisation. Yet here you suggest that "any serializing
> instruction" includes the atomic ones. What am I misunderstanding?

'serializing' instructions are the ones that are barriers to all
speculative CPU mechanizms. Intel LOCK-ed instructions are preventing the
most important asynchron mechanism from occuring: speculative reads. They
do not prevent certain other mechanizm like TLB prefetch or icache
prefetch, but this is of little practical interest.

basically we need no serializing instructions at all, because Intel
guarantees the 'Program Order' shared memory model, which makes
serializing instructions (in the classical sense) meaningless. (they would
be much more important if the memory model was weakly ordered). But even
preventing TLB-prefetches can be important in some cases, eg. when we are
modifying page tables.

> And the that matter, whch instructions are serialising in this way?
> [...]

fully serializing instructions are: NVD, INVPG, WBINVD, IRET, IRETD, LGDT,
LLDT, LIDT, LTR, CPUID, RSM.

> Is "sfence" serialising? [...]

no, but in the WC memory model they are a write barrier. [otherwise every
write is a write barrier]

> What about a far jump? (Far jump serialises the execution unit in as
> much as you need one to switch between real & protected modes, for
> example, but I don't think it serialises memory accesses).

only IRET. Also i believe task switches are serializing because they have
an implicit LTR.

> And of course, are the rules for non-Intel "x86 compatible" processors
> just as strong?

once they do SMP we'll see.

-- mingo

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