Re: [GIT PULL] kdbus for 4.1-rc1

Daniel Mack
2015-04-24T11:26:30Z

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