Hi, after reading Marek's and Sven's comments to my question about the vis code, and looking at the code a bit I came to the following conclusion about the first part of the cleanup, the finishing of the RCU conversion of the vis code:
It should be possible to get rid of the vis_hash_lock altogether, as the hash table has spinlocks for the hash lists itself; overall hash consistency might be a issue though - I would propose adding a hash_update function that updates a hash entry without deleting and re-adding the hlist node.
I think I found a bug in the hash_add function though. First there is a RCU-locked loop that checks if a entry does already exist, but the spinlock is taken after the rcu_read_unlock() - thus allowing the same entry to be appended twice if two threads try to add it at the same time.
If you want to contact me about this via IRC, I'm now idling in #batman - my nickname there is neoraider.
Thanks, Matthias
On Tuesday, May 08, 2012 03:35:07 Matthias Schiffer wrote:
It should be possible to get rid of the vis_hash_lock altogether, as the hash table has spinlocks for the hash lists itself;
Yes, the hash implementation was converted to use fine-grained locking instead of one big spinlock as was the rest of the code except for vis.
overall hash consistency might be a issue though - I would propose adding a hash_update function that updates a hash entry without deleting and re-adding the hlist node.
Can you give an example of such an "update" ? Where would we need it ?
I think I found a bug in the hash_add function though. First there is a RCU-locked loop that checks if a entry does already exist, but the spinlock is taken after the rcu_read_unlock() - thus allowing the same entry to be appended twice if two threads try to add it at the same time.
You are right - you found a bug. :)
Regards, Marek
On 05/08/2012 07:59 AM, Marek Lindner wrote:
On Tuesday, May 08, 2012 03:35:07 Matthias Schiffer wrote:
overall hash consistency might be a issue though - I would propose adding a hash_update function that updates a hash entry without deleting and re-adding the hlist node.
Can you give an example of such an "update" ? Where would we need it ?
It would be useful to keep the output consistent even when the hash is updated while the output is generated - as a delete-add sequence adds the new element at the head of the hlist, a RCU-locked reader will not see the element when the traversal position is between the head and the old position of the element. An hash_update could use hlist_replace_rcu() to replace an element in a way that each reader either sees the old or the new version, but none loses it completely.
A hash_update_if version that gets an additional callback that is provided with the old and the new element and gets to decide which element to keep in the hash could be used to compare the sequence numbers in the vis code and update the hash atomically.
Matthias
On Tuesday, May 08, 2012 22:18:34 Matthias Schiffer wrote:
It would be useful to keep the output consistent even when the hash is updated while the output is generated - as a delete-add sequence adds the new element at the head of the hlist, a RCU-locked reader will not see the element when the traversal position is between the head and the old position of the element. An hash_update could use hlist_replace_rcu() to replace an element in a way that each reader either sees the old or the new version, but none loses it completely.
A hash_update_if version that gets an additional callback that is provided with the old and the new element and gets to decide which element to keep in the hash could be used to compare the sequence numbers in the vis code and update the hash atomically.
How the rcu replace / update mechanism works is pretty clear to me. My question geared towards our own code base. At which point would you use this rcu update ? Every time an element in the hash is modified ?
Regards, Marek
On 05/09/2012 01:04 PM, Marek Lindner wrote:
On Tuesday, May 08, 2012 22:18:34 Matthias Schiffer wrote: How the rcu replace / update mechanism works is pretty clear to me. My question geared towards our own code base. At which point would you use this rcu update ? Every time an element in the hash is modified ?
Yes, my idea is to use this whenever a new packet is inserted into the vis hash to ensure the vis data a reader sees is always as consistant as possible. I know it wouldn't be fatal for the vis if a packet is missing from the data sometimes, but in my opinion a clean update is nicer :)
Matthias
On Wednesday, May 09, 2012 22:59:00 Matthias Schiffer wrote:
On 05/09/2012 01:04 PM, Marek Lindner wrote:
On Tuesday, May 08, 2012 22:18:34 Matthias Schiffer wrote: How the rcu replace / update mechanism works is pretty clear to me. My question geared towards our own code base. At which point would you use this rcu update ? Every time an element in the hash is modified ?
Yes, my idea is to use this whenever a new packet is inserted into the vis hash to ensure the vis data a reader sees is always as consistant as possible. I know it wouldn't be fatal for the vis if a packet is missing from the data sometimes, but in my opinion a clean update is nicer :)
Feel free to propose patches to introduce this functionality. So far, we have been living without it but maybe we overlooked a potential side effect ?
Regards, Marek
To ensure an entry isn't added twice all comparisons have to be protected by the hash line write spinlock. This doesn't really hurt as the case that it is tried to add an element already present to the hash shouldn't occur very often, so in most cases the lock would have have to be taken anyways.
Signed-off-by: Matthias Schiffer mschiffer@universe-factory.net --- hash.h | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-)
diff --git a/hash.h b/hash.h index 7bcb98f..2e0409a 100644 --- a/hash.h +++ b/hash.h @@ -109,26 +109,23 @@ static inline int hash_add(struct hashtable_t *hash, head = &hash->table[index]; list_lock = &hash->list_locks[index];
- rcu_read_lock(); - __hlist_for_each_rcu(node, head) { + spin_lock_bh(list_lock); + + hlist_for_each(node, head) { if (!compare(node, data)) continue;
ret = 1; - goto err_unlock; + goto unlock; } - rcu_read_unlock();
/* no duplicate found in list, add new element */ - spin_lock_bh(list_lock); hlist_add_head_rcu(data_node, head); - spin_unlock_bh(list_lock);
ret = 0; - goto out;
-err_unlock: - rcu_read_unlock(); +unlock: + spin_unlock_bh(list_lock); out: return ret; }
On Tuesday 08 May 2012 22:31:57 Matthias Schiffer wrote:
To ensure an entry isn't added twice all comparisons have to be protected by the hash line write spinlock. This doesn't really hurt as the case that it is tried to add an element already present to the hash shouldn't occur very often, so in most cases the lock would have have to be taken anyways.
Signed-off-by: Matthias Schiffer mschiffer@universe-factory.net
hash.h | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-)
diff --git a/hash.h b/hash.h index 7bcb98f..2e0409a 100644 --- a/hash.h +++ b/hash.h @@ -109,26 +109,23 @@ static inline int hash_add(struct hashtable_t *hash, head = &hash->table[index]; list_lock = &hash->list_locks[index];
- rcu_read_lock();
- __hlist_for_each_rcu(node, head) {
spin_lock_bh(list_lock);
hlist_for_each(node, head) { if (!compare(node, data)) continue;
ret = 1;
goto err_unlock;
goto unlock;
rcu_read_unlock();
/* no duplicate found in list, add new element */
spin_lock_bh(list_lock); hlist_add_head_rcu(data_node, head);
spin_unlock_bh(list_lock);
ret = 0;
goto out;
-err_unlock:
- rcu_read_unlock();
+unlock:
- spin_unlock_bh(list_lock);
out: return ret; }
Acked-by: Sven Eckelmann sven@narfation.org
Thanks, Sven
On Wednesday, May 09, 2012 04:38:58 Sven Eckelmann wrote:
Details
On Tuesday 08 May 2012 22:31:57 Matthias Schiffer wrote:
To ensure an entry isn't added twice all comparisons have to be protected by the hash line write spinlock. This doesn't really hurt as the case that it is tried to add an element already present to the hash shouldn't occur very often, so in most cases the lock would have have to be taken anyways.
[..]
-err_unlock:
rcu_read_unlock();+unlock:
spin_unlock_bh(list_lock);out: return ret; }
Acked-by: Sven Eckelmann sven@narfation.org
Applied in revision 41c5874.
Thanks, Marek
b.a.t.m.a.n@lists.open-mesh.org
-
Marek Lindner -
Matthias Schiffer -
Sven Eckelmann