[B.A.T.M.A.N.] The current state of the batman-adv vis code

[B.A.T.M.A.N.] The current state of the batman-adv vis code

[Matthias Schiffer]

[-- Attachment #1: Type: text/plain, Size: 966 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: [B.A.T.M.A.N.] The current state of the batman-adv vis code

[Marek Lindner]

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

Re: [B.A.T.M.A.N.] The current state of the batman-adv vis code

[Matthias Schiffer]

[-- Attachment #1: Type: text/plain, Size: 1130 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: [B.A.T.M.A.N.] The current state of the batman-adv vis code

[Marek Lindner]

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

Re: [B.A.T.M.A.N.] The current state of the batman-adv vis code

[Matthias Schiffer]

[-- Attachment #1: Type: text/plain, Size: 635 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 262 bytes --]

Re: [B.A.T.M.A.N.] The current state of the batman-adv vis code

[Marek Lindner]

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

[B.A.T.M.A.N.] [PATCH] batman-adv: fix locking in hash_add()

[Matthias Schiffer]

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;
 }
-- 
1.7.10.1

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: fix locking in hash_add()

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 1394 bytes --]

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

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] [PATCH] batman-adv: fix locking in hash_add()

[Marek Lindner]

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