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