Re: [B.A.T.M.A.N.] [PATCHv5 3/3] batman-adv: Modified forwarding behaviour for multicast packets

["Linus Lüssing" <linus.luessing@web.de>]

On Fri, Jun 14, 2013 at 04:30:28PM +0200, Simon Wunderlich wrote:
> On Fri, Jun 14, 2013 at 11:02:05AM +0200, Linus Lüssing wrote:
>   
> >  /**
> > + * batadv_tt_orig_entries_count - count the number of originators
> > + * @head: a list of originators
> > + *
> > + * Return the number of originator entries in the given list.
> > + *
> > + * The caller needs to hold the rcu_read_lock().
> > + */
> > +static int batadv_tt_orig_entries_count(struct hlist_head *head)
> > +{
> > +	struct batadv_tt_orig_list_entry *orig_entry;
> > +	int count = 0;
> > +
> > +	hlist_for_each_entry_rcu(orig_entry, head, list) {
> > +		if (!atomic_read(&orig_entry->refcount))
> > +			continue;
> > +
> > +		count++;
> > +	}
> > +
> > +	return count;
> > +}
> > +
> > +/**
> > + * batadv_tt_global_hash_count - count the number of orig entries
> > + * @hash: hash table containing the tt entries
> > + * @addr: the mac address of the client to count entries for
> > + * @vid: VLAN identifier
> > + *
> > + * Return the number of originators advertising the given address/data
> > + * (excluding ourself).
> > + */
> > +int batadv_tt_global_hash_count(struct batadv_priv *bat_priv,
> > +				const uint8_t *addr, unsigned short vid)
> > +{
> > +	struct hlist_head *head, *orig_list;
> > +	struct batadv_tt_common_entry to_search, *tt_common_entry;
> > +	struct batadv_tt_global_entry *tt_global_entry;
> > +	uint32_t index;
> > +	int count = 0;
> > +
> > +	if (!bat_priv->tt.global_hash)
> > +		goto out;
> > +
> > +	memcpy(to_search.addr, addr, ETH_ALEN);
> > +	to_search.vid = vid;
> > +
> > +	index = batadv_choose_tt(&to_search, bat_priv->tt.global_hash->size);
> > +	head = &bat_priv->tt.global_hash->table[index];
> > +
> > +	rcu_read_lock();
> > +	hlist_for_each_entry_rcu(tt_common_entry, head, hash_entry) {
> > +		if (!batadv_compare_eth(tt_common_entry, addr))
> > +			continue;
> > +
> > +		if (!atomic_read(&tt_common_entry->refcount))
> > +			continue;
> > +
> > +		tt_global_entry = container_of(tt_common_entry,
> > +					       struct batadv_tt_global_entry,
> > +					       common);
> > +		orig_list = &tt_global_entry->orig_list;
> > +		count = batadv_tt_orig_entries_count(orig_list);
> > +		break;
> > +	}
> > +	rcu_read_unlock();
> > +
> > +out:
> > +	return count;
> > +}
> > +
> > +/**
> 
> I've been thinking about this part ... it is not good to iterate over the whole
> hash for every multicast packet - this is the fastpath after all, so it's critical.

This is what we do for any packet, it's a simple, fast hash-lookup
(and for the rare case of two entries having the same hash result,
then a small list lookup, too). Pretty much what we are doing with
any batadv_transtable_search(). It's mostly a copy-paste of the
batadv_tt_hash_find().

Except the batadv_tt_orig_entries_count(), that's a list lookup
which we do not have with a common transtable_search(). I had
thought about adding an atomic counter for the orig_list in and to
the struct tt_global_entry (but didn't do it because I wanted to
leave the original translation-table.c functions as untouched as
possible and thought the performance gain wouldn't be that huge).
Hm, but maybe you're right about the performance if we are going
to have a large mesh network with many originators claiming a
certain multicast address. I'm going to add that atomic counter.

> 
> Can't you just use batadv_tt_global_hash_find(), count the list entries within
> struct batadv_tt_global_entry (or find out if it is empty, one entry or more
> than one entry) and be done? This should be much faster.

But looking at that function again now, you're right, because the
lookup in batadv_tt_global_hash_count() is nearly identical now to
batadv_tt_global_hash_find(), I can use that one instead.
(Initially I needed to do such copying of the tt_global_hash_find()
function because of my wrong assumption that there'd be a
tt_global_entry for every originator announcing that address -
but, yeah, now that's even easier :) ).

Will change that :).

> 
> Apart from that, the patch series appears to be pretty mature now, I've done
> some more testing in my VMs and it looks good. Should be (hopefully) the last
> thing from my side. :)

No worries, every comment welcome. And with just 3 instead of ~15
multicast patches it's a lot easier to fix and rebase things now :P.

> 
> Cheers,
> 	Simon

Cheers, Linus