Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753399AbbDXK3A (ORCPT ); Fri, 24 Apr 2015 06:29:00 -0400 Received: from svenfoo.org ([82.94.215.22]:50857 "EHLO mail.zonque.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752681AbbDXK25 (ORCPT ); Fri, 24 Apr 2015 06:28:57 -0400 Message-ID: <553A1AE6.9060902@zonque.org> Date: Fri, 24 Apr 2015 12:28:54 +0200 From: Daniel Mack User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0 MIME-Version: 1.0 To: Borislav Petkov , Steven Noonan CC: David Herrmann , Greg Kroah-Hartman , "Eric W. Biederman" , Linus Torvalds , Andrew Morton , Arnd Bergmann , One Thousand Gnomes , Tom Gundersen , Jiri Kosina , Andy Lutomirski , linux-kernel , Djalal Harouni Subject: Re: [GIT PULL] kdbus for 4.1-rc1 References: <20150413190350.GA9485@kroah.com> <8738434yjk.fsf@x220.int.ebiederm.org> <20150422085827.GA6962@pd.tnic> <20150423191433.GB13607@kroah.com> <20150423205640.GR28327@pd.tnic> <20150423214111.GT28327@pd.tnic> <20150424090402.GA24014@pd.tnic> In-Reply-To: <20150424090402.GA24014@pd.tnic> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3512 Lines: 78 Hi, On 04/24/2015 11:04 AM, Borislav Petkov wrote: > On Thu, Apr 23, 2015 at 10:02:52PM -0700, Steven Noonan wrote: >> On Thu, Apr 23, 2015 at 2:41 PM, Borislav Petkov 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. Sure, for broadcasts, we have to walk the list of peers connected to the bus and see which one is interested in a particular message. We do that by looking at the match rules of each of them, which are based on well-known names, IDs, notification types or bloom filters. The policy logic limits this further, as receivers of a broadcast must have TALK access to the sender. If these rules let a message pass, all the metadata that the receiving peer asked for (by setting a flag at connect time) is collected, unless it has been collected already for some other peer for the same message. In other words, in worst case, we collect all the metadata items exactly once per message. If none of the connections with permissive match/policy rules for a message is interested in any metadata items, nothing will be collected at all. The reason why the peers are organized in a hash table is that we have to look them up by ID for unicast messages. > 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. If the receiving side doesn't need it, it shouldn't opt-in for that piece of information. The metadata logic is really only there so receiving peers are directly supplied with information that they would otherwise look up themselves from /proc or something. Also, we collect metadata at send time and for every message intentionally, so that it reflects the state of the sender at the time of sending. This way, the information is not subject to races of asynchronous lookups. > 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 exactly what happens :) There are some more details on this in kdbus.match(7). Thanks, Daniel -- 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/