lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAG-2HqUKJyf4B-JQunC17dw-eFkF69V9uMWAo8hFQxvwoOLc_A@mail.gmail.com>
Date:   Fri, 28 Oct 2016 16:33:50 +0200
From:   Tom Gundersen <teg@...m.no>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     David Herrmann <dh.herrmann@...il.com>,
        LKML <linux-kernel@...r.kernel.org>,
        Andy Lutomirski <luto@...capital.net>,
        Jiri Kosina <jikos@...nel.org>, Greg KH <greg@...ah.com>,
        Hannes Reinecke <hare@...e.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Arnd Bergmann <arnd@...db.de>,
        Josh Triplett <josh@...htriplett.org>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [RFC v1 06/14] bus1: util - queue utility library

On Fri, Oct 28, 2016 at 3:58 PM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Fri, Oct 28, 2016 at 03:47:58PM +0200, Tom Gundersen wrote:
>> On Fri, Oct 28, 2016 at 3:33 PM, Peter Zijlstra <peterz@...radead.org> wrote:
>> > On Fri, Oct 28, 2016 at 01:33:25PM +0200, Tom Gundersen wrote:
>
>> > And this, precisely, is what generates all the complexity found in this
>> > patch.  You want to strictly provide more than causality, which does
>> > not, as per the argument above, provide this at all.
>> >
>> > You're providing a semi-global ordering of things that are themselves
>> > not actually ordered.
>>
>> We are providing two things: causality (as in your physics example
>> above), and consistency (which, I agree, is cute, but not necessarily
>> crucial). However, the complexity comes from causality. Consistency is
>> trivial. The only thing needed for consistency is to tag each message
>> by its sender and use this to resolve conflicts in the ordering. The
>> alternative would be to just let these entries order arbitrarily
>> instead, but conceptually it would not be simpler and it would only
>> save us a few lines of code.
>
> Earlier you wrote:
>
>> >> To make this work with multicast, we must stage messages first, then
>> >> commit on a second round. That is, we must find some way to iterate
>> >> over all clocks before committing, but at the same time preventing any
>> >> races. The multicast-stability as you just described we get for free
>> >> by introducing the second-level ordering via sender-address.
>
> But you don't need the two-pass thing at all for causality. The entire
> two-pass thing, and the serialization, is part of the consistency thing.
>
> This is not virtually free.
>
> For causality, all you need is a single iteration, delivering the
> message one after the other, only ever doing local clock movements. You
> do not need to find the max clock in the multicast set and avoid races
> etc..

Ah, I see, we are talking past each other. The property we do want
(which is not trivial) is that we do not want to observe the effect
before the cause. If an event at A causes an event at B, then the two
events should be guaranteed to be observed at C in that order. i.e.,
if you send a multi-cast message from A to B and C and as a result of
receiving the message, B sends a message to C, we want to be
guaranteed that C receives the latter after the former.

If this property is not wanted, then (repeated) unicast can in most
cases be used instead of multi-cast (and a natural optimization, which
we left out for now, would be to skip the staging round for unicast
messages).

Cheers,

Tom

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ