From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S934068AbbDXL0a (ORCPT ); Fri, 24 Apr 2015 07:26:30 -0400 Received: from svenfoo.org ([82.94.215.22]:51314 "EHLO mail.zonque.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933059AbbDXL01 (ORCPT ); Fri, 24 Apr 2015 07:26:27 -0400 Message-ID: <553A2860.6000305@zonque.org> Date: Fri, 24 Apr 2015 13:26:24 +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 CC: Steven Noonan , 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> <553A1AE6.9060902@zonque.org> <20150424105047.GA24894@pd.tnic> In-Reply-To: <20150424105047.GA24894@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 Hi, On 04/24/2015 12:50 PM, Borislav Petkov wrote: > On Fri, Apr 24, 2015 at 12:28:54PM +0200, Daniel Mack wrote: >> 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 > > And this "... we have to walk the list ..." right there raises the > alarm. Can this walking of elements where you know they wouldn't match > be avoided? Yes, see below. >> 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. > > So it sounds to me like there are characteristics which can already > prepare lists of recipients interested in some sort of message. So > would it be possible for recipients to "register" for such messages > and the sending side would simply iterate a list of solely interested > recipients? > > This will definitely save you the iteration over all n connections and > would make the metadata collection probably not needed (or at least a > subset of it) because recipients will have to establish eligibility for > receiving a certain message at register time and once they're on the > list, you implicitly know why they're there. David is working on patches that store hashes of the matches in trees so we can look them up more efficiently. We'd still need to check the bloom filter for all remaining candidates though. These are, however, implementation details which potentially make the code harder to read. We are well aware of certain spots that can be made more efficient, but we were hoping for more reviews by keeping the implementation simple for now. >> 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. > > But we still iterate through there and look at the arg @what and > ->collected. And this is useless work which can be avoided IMHO. Not sure if it really matters, but we can probably add an early bail there, yes. Something like what &= ~mp->collected; if (!what) return; Noted down, thanks! >>> 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). > > But this is not for KDBUS_DST_ID_BROADCAST types, right? Yes it is - all broadcast messages are subject to opt-in filters installed by the receiving peer. Thanks, Daniel