linux-kernel - Re: [GIT PULL] kdbus for 4.1-rc1

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: <20150424090402.GA24014@pd.tnic>
Date:	Fri, 24 Apr 2015 11:04:03 +0200
From:	Borislav Petkov <bp@...en8.de>
To:	Steven Noonan <steven@...inklabs.net>
Cc:	David Herrmann <dh.herrmann@...il.com>,
	Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Arnd Bergmann <arnd@...db.de>,
	One Thousand Gnomes <gnomes@...rguk.ukuu.org.uk>,
	Tom Gundersen <teg@...m.no>, Jiri Kosina <jkosina@...e.cz>,
	Andy Lutomirski <luto@...capital.net>,
	linux-kernel <linux-kernel@...r.kernel.org>,
	Daniel Mack <daniel@...que.org>,
	Djalal Harouni <tixxdz@...ndz.org>
Subject: Re: [GIT PULL] kdbus for 4.1-rc1

On Thu, Apr 23, 2015 at 10:02:52PM -0700, Steven Noonan wrote:
> On Thu, Apr 23, 2015 at 2:41 PM, Borislav Petkov <bp@...en8.de> wrote:
> > On Thu, Apr 23, 2015 at 11:22:39PM +0200, David Herrmann wrote:
> >> No it's not. O(256) equals O(1).
> >
> > Ok, you're right. Maybe O() was not the right thing to use when trying
> > to point out that iterating over 256 hash buckets and then following the
> > chain in each bucket per packet broadcast looks like a lot.
> >
> 
> Heh. I guess you could call it an "expensive O(1)". While big-O
> notation is useful for describing algorithm scalability with respect
> to input size, it falls flat on its face when trying to articulate
> impact in measurable units.

Right, so in thinking about this more today, on a fresh head, it still
is O(n) because we do broadcast the packet to n recipients - the
hash_for_each() thing iterates over 256 hash buckets and also follows
the linked list chain in each bucket. Its length is depending on how
many connections are in the bucket, i.e. recipients. And I'd guess that
number changes dynamically so probably linear.

And then there's the collection of, let's call it metadata of
questionable use, *per* packet which is pretty expensive in my book.
It becomes even more expensive if it is completely useless as in, the
receiving side doesn't need it all.

Now, one might argue that you have to do O(n) work when broadcasting
to n recipients anyway and you can't get that cheaper but maybe the
design is not optimal. Maybe it could be made to not broadcast at all,
or broadcast to a subset of recipients, only those which are actually
interested in the broadcast.

That's why I was looking at some simple token-based schemes. And that's
why I think Andy has some very cool ideas which we should definitely pay
attention to:

https://lkml.kernel.org/r/CALCETrXXUiYKAhsXsdqH2uZMddDhK5hX6V9%2BrZcHwa1X5WC%2B1g@mail.gmail.com

before we go and commit this thing and cast it stone. Because if it goes
in, there's no changing it because we'll be then breaking userspace and
that's no-no.

-- 
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
--
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/