2019-06-04 10:11:33 +02:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2015-02-05 02:03:32 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-05-15 11:30:47 +08:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-26 07:20:34 -08:00
|
|
|
|
2017-02-04 01:27:20 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-12-10 16:33:11 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-02-09 14:04:03 +11:00
|
|
|
|
2015-06-06 22:07:23 +02:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-03-18 20:01:16 +11:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2015-03-10 09:27:55 +11:00
|
|
|
|
2015-01-02 23:00:14 +01:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-02-05 02:03:34 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: use BIT(0) for locking.
As reported by Guenter Roeck, the new bit-locking using
BIT(1) doesn't work on the m68k architecture. m68k only requires
2-byte alignment for words and longwords, so there is only one
unused bit in pointers to structs - We current use two, one for the
NULLS marker at the end of the linked list, and one for the bit-lock
in the head of the list.
The two uses don't need to conflict as we never need the head of the
list to be a NULLS marker - the marker is only needed to check if an
object has moved to a different table, and the bucket head cannot
move. The NULLS marker is only needed in a ->next pointer.
As we already have different types for the bucket head pointer (struct
rhash_lock_head) and the ->next pointers (struct rhash_head), it is
fairly easy to treat the lsb differently in each.
So: Initialize buckets heads to NULL, and use the lsb for locking.
When loading the pointer from the bucket head, if it is NULL (ignoring
the lock big), report as being the expected NULLS marker.
When storing a value into a bucket head, if it is a NULLS marker,
store NULL instead.
And convert all places that used bit 1 for locking, to use bit 0.
Fixes: 8f0db018006a ("rhashtable: use bit_spin_locks to protect hash bucket.")
Reported-by: Guenter Roeck <linux@roeck-us.net>
Tested-by: Guenter Roeck <linux@roeck-us.net>
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-12 11:52:08 +10:00
|
|
|
|
2015-02-05 02:03:34 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-03 18:12:43 +10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-03 18:12:43 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-03 18:12:43 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-28 18:14:19 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-14 13:57:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2024-03-21 09:36:53 -07:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2019-05-16 15:19:48 +08:00
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2024-03-21 09:36:53 -07:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-24 00:50:27 +11:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-02-20 00:53:38 +01:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
2015-01-02 23:00:21 +01:00
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2024-03-21 09:36:53 -07:00
|
|
|
|
2025-08-06 14:41:47 +02:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2024-08-06 08:39:27 -07:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-08-21 22:01:48 -07:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
|
|
|
|
|
2017-06-07 22:47:13 -04:00
|
|
|
|
2015-03-14 13:57:22 +11:00
|
|
|
|
2015-01-02 23:00:21 +01:00
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2015-01-02 23:00:21 +01:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
2015-02-05 02:03:32 +01:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2019-04-12 11:52:07 +10:00
|
|
|
|
2015-03-24 14:18:17 +01:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2015-02-05 02:03:32 +01:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
2015-02-05 02:03:32 +01:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2015-02-05 02:03:32 +01:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2015-09-22 10:51:52 +02:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-03-24 14:18:17 +01:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-02-05 02:03:35 +01:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
2019-05-16 15:19:48 +08:00
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 14:18:17 +01:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-03-31 12:58:48 -07:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 09:53:17 +11:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-11 09:43:48 +11:00
|
|
|
|
2015-03-14 13:57:23 +11:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-19 16:40:21 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:25 +11:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2025-12-19 16:40:21 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2016-08-12 20:10:44 +02:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2016-08-12 20:10:44 +02:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:25 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
rhashtable: Fix race in rhashtable_destroy() and use regular work_struct
When we put our declared work task in the global workqueue with
schedule_delayed_work(), its delay parameter is always zero.
Therefore, we should define a regular work in rhashtable structure
instead of a delayed work.
By the way, we add a condition to check whether resizing functions
are NULL before cancelling the work, avoiding to cancel an
uninitialized work.
Lastly, while we wait for all work items we submitted before to run
to completion with cancel_delayed_work(), ht->mutex has been taken in
rhashtable_destroy(). Moreover, cancel_delayed_work() doesn't return
until all work items are accomplished, and when work items are
scheduled, the work's function - rht_deferred_worker() will be called.
However, as rht_deferred_worker() also needs to acquire the lock,
deadlock might happen at the moment as the lock is already held before.
So if the cancel work function is moved out of the lock covered scope,
this will avoid the deadlock.
Fixes: 97defe1 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: Ying Xue <ying.xue@windriver.com>
Cc: Thomas Graf <tgraf@suug.ch>
Acked-by: Thomas Graf <tgraf@suug.ch>
Signed-off-by: David S. Miller <davem@davemloft.net>
2015-01-16 11:13:09 +08:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-02-04 07:33:22 +11:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-12 15:28:40 +01:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2015-03-24 20:42:19 +00:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2019-03-21 09:39:52 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:26 +11:00
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-12-03 20:41:29 +08:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
|
|
|
|
|
2015-04-22 09:41:46 +02:00
|
|
|
|
|
|
|
|
|
2015-12-03 20:41:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
2018-08-21 22:01:45 -07:00
|
|
|
|
2015-12-03 20:41:29 +08:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-28 18:14:19 +02:00
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
|
|
|
|
|
2015-12-03 20:41:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2015-12-03 20:41:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
2015-12-03 20:41:29 +08:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:28 +11:00
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-12 11:52:07 +10:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2017-04-16 02:55:09 +02:00
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-03-04 17:29:48 +02:00
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2018-03-04 17:29:48 +02:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
2016-08-24 12:31:31 +02:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2026-04-18 09:41:21 +08:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-05-15 11:30:47 +08:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2015-05-15 11:30:47 +08:00
|
|
|
|
2026-04-18 09:41:21 +08:00
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-01-14 11:15:19 +08:00
|
|
|
|
|
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-01-14 11:15:19 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2022-12-06 11:36:32 -10:00
|
|
|
|
2024-11-28 04:16:25 -08:00
|
|
|
|
2025-01-14 11:15:19 +08:00
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
rhashtable: use bit_spin_locks to protect hash bucket.
This patch changes rhashtables to use a bit_spin_lock on BIT(1) of the
bucket pointer to lock the hash chain for that bucket.
The benefits of a bit spin_lock are:
- no need to allocate a separate array of locks.
- no need to have a configuration option to guide the
choice of the size of this array
- locking cost is often a single test-and-set in a cache line
that will have to be loaded anyway. When inserting at, or removing
from, the head of the chain, the unlock is free - writing the new
address in the bucket head implicitly clears the lock bit.
For __rhashtable_insert_fast() we ensure this always happens
when adding a new key.
- even when lockings costs 2 updates (lock and unlock), they are
in a cacheline that needs to be read anyway.
The cost of using a bit spin_lock is a little bit of code complexity,
which I think is quite manageable.
Bit spin_locks are sometimes inappropriate because they are not fair -
if multiple CPUs repeatedly contend of the same lock, one CPU can
easily be starved. This is not a credible situation with rhashtable.
Multiple CPUs may want to repeatedly add or remove objects, but they
will typically do so at different buckets, so they will attempt to
acquire different locks.
As we have more bit-locks than we previously had spinlocks (by at
least a factor of two) we can expect slightly less contention to
go with the slightly better cache behavior and reduced memory
consumption.
To enhance type checking, a new struct is introduced to represent the
pointer plus lock-bit
that is stored in the bucket-table. This is "struct rhash_lock_head"
and is empty. A pointer to this needs to be cast to either an
unsigned lock, or a "struct rhash_head *" to be useful.
Variables of this type are most often called "bkt".
Previously "pprev" would sometimes point to a bucket, and sometimes a
->next pointer in an rhash_head. As these are now different types,
pprev is NULL when it would have pointed to the bucket. In that case,
'blk' is used, together with correct locking protocol.
Signed-off-by: NeilBrown <neilb@suse.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
2019-04-02 10:07:45 +11:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-06-05 04:41:18 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-06-06 10:30:32 -07:00
|
|
|
|
|
|
|
|
|
2026-06-05 04:41:18 -07:00
|
|
|
|
2026-06-06 10:30:32 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-06-05 04:41:18 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
2024-11-23 02:29:29 -08:00
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2015-12-16 16:45:54 +08:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-12-19 10:45:28 +08:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-12-16 16:45:54 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-02-14 22:03:27 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-12-16 16:45:54 +08:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
|
|
|
|
|
2015-12-16 16:45:54 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:41 -08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2017-09-19 12:41:37 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2021-07-07 18:07:31 -07:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:41 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2017-12-04 10:31:41 -08:00
|
|
|
|
2025-12-19 16:40:21 +01:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2015-12-16 16:45:54 +08:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
|
|
|
|
|
2015-12-16 16:45:54 +08:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
|
|
|
|
|
2026-07-07 12:41:15 -04:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-07-02 09:35:34 -07:00
|
|
|
|
2018-04-24 08:29:13 +10:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:41 -08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-07-06 15:51:20 +02:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:19 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
|
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
|
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
|
|
|
|
|
2015-05-05 02:22:53 +02:00
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
2017-12-04 10:31:42 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-09-19 12:41:37 +02:00
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
|
|
|
|
|
2015-03-15 21:12:04 +11:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 09:53:17 +11:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
|
|
|
|
|
2016-08-18 16:50:56 +08:00
|
|
|
|
2019-03-21 14:42:40 +11:00
|
|
|
|
|
|
|
|
|
2015-03-24 09:53:17 +11:00
|
|
|
|
2015-03-14 13:57:20 +11:00
|
|
|
|
2015-03-15 21:12:04 +11:00
|
|
|
|
|
|
|
|
|
2015-02-04 07:33:23 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-20 21:56:59 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2018-07-16 13:26:13 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:21 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-12-10 16:33:11 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-25 13:07:45 +00:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-12-10 16:33:11 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-27 13:09:57 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:21 +11:00
|
|
|
|
2015-03-20 21:57:00 +11:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2026-04-27 13:09:57 +02:00
|
|
|
|
2015-03-24 09:53:17 +11:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
|
|
|
|
|
2024-03-21 09:36:53 -07:00
|
|
|
|
|
|
|
|
|
2015-03-19 22:31:13 +00:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-04-27 13:44:51 +08:00
|
|
|
|
|
|
|
|
|
2017-04-28 14:10:48 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-04-27 13:44:51 +08:00
|
|
|
|
2017-05-01 22:18:01 +02:00
|
|
|
|
2015-03-19 22:31:13 +00:00
|
|
|
|
2018-07-16 13:26:13 -07:00
|
|
|
|
2015-12-16 18:13:14 +08:00
|
|
|
|
2015-03-24 00:50:21 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-08-21 22:01:48 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-03-24 00:50:27 +11:00
|
|
|
|
2018-08-21 22:01:48 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-01-07 13:41:57 +08:00
|
|
|
|
2015-03-12 15:28:40 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2015-02-25 16:31:54 +01:00
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
|
|
|
|
|
2026-04-27 13:09:57 +02:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-27 13:09:57 +02:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-27 13:09:57 +02:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-27 13:09:57 +02:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-07-22 12:27:48 +02:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: drop ht->mutex in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() is a single-shot teardown routine:
cancel_work_sync() has already quiesced the deferred rehash worker, and
the function's documented contract requires the caller to guarantee no
other concurrent access to the rhashtable. Under those conditions
ht->mutex is not protecting anything -- taking it is a leftover from
the original teardown path.
That leftover is actively harmful: it closes a circular lock-class
dependency with fs_reclaim. The deferred rehash worker takes ht->mutex
and then allocates GFP_KERNEL memory in bucket_table_alloc(),
establishing
&ht->mutex -> fs_reclaim
After commit b32c4a213698 ("xattr: add rhashtable-based simple_xattr
infrastructure") introduced simple_xattr_ht_free(), which calls
rhashtable_free_and_destroy(), the simple_xattrs teardown became
reachable from evict() under the dcache shrinker. The subsequent
per-subsystem adaptations made the reverse edge concrete in three
independent code paths:
* commit 52b364fed6e1 ("shmem: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 5bd97f5c5f24 ("kernfs: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 50704c391fbf ("pidfs: adapt to rhashtable-based simple_xattrs")
Any of the three closes the cycle
fs_reclaim -> &ht->mutex
which lockdep reports as follows. This particular splat was observed
organically on a workstation kernel built from vfs-7.1-rc1.xattr at
~35h uptime under normal mixed workload, with CONFIG_PROVE_LOCKING=y.
The path happens to go through kernfs:
WARNING: possible circular locking dependency detected
7.0.0-faeab166167f-with-fixes-v1+ #191 Tainted: G U
kswapd0/243 is trying to acquire lock:
ffff8882e475c0f8 (&ht->mutex){+.+.}-{4:4},
at: rhashtable_free_and_destroy+0x36/0x740
but task is already holding lock:
ffffffffa8ad1d00 (fs_reclaim){+.+.}-{0:0},
at: balance_pgdat+0x995/0x1600
the existing dependency chain (in reverse order) is:
-> #1 (fs_reclaim){+.+.}-{0:0}:
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
fs_reclaim_acquire+0xd9/0x130
__kvmalloc_node_noprof+0xcd/0xb40
bucket_table_alloc.isra.0+0x5a/0x440
rhashtable_rehash_alloc+0x4e/0xd0
rht_deferred_worker+0x14b/0x440
process_one_work+0x8fd/0x16a0
worker_thread+0x601/0xff0
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
-> #0 (&ht->mutex){+.+.}-{4:4}:
check_prev_add+0xdb/0xce0
validate_chain+0x554/0x780
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
__mutex_lock+0x1b2/0x2550
rhashtable_free_and_destroy+0x36/0x740
kernfs_put.part.0+0x119/0x570
evict+0x3b6/0x9c0
__dentry_kill+0x181/0x540
shrink_dentry_list+0x135/0x440
prune_dcache_sb+0xdb/0x150
super_cache_scan+0x2ff/0x520
do_shrink_slab+0x35a/0xee0
shrink_slab_memcg+0x457/0x950
shrink_slab+0x43b/0x550
shrink_one+0x31a/0x6f0
shrink_many+0x31e/0xc80
shrink_node+0xeb3/0x14a0
balance_pgdat+0x8ed/0x1600
kswapd+0x2f3/0x530
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
Possible unsafe locking scenario:
CPU0 CPU1
---- ----
lock(fs_reclaim);
lock(&ht->mutex);
lock(fs_reclaim);
lock(&ht->mutex);
Note that lockdep tracks lock classes, not instances: the two
&ht->mutex sites are on different rhashtable objects (the deferred
worker was triggered by some unrelated rhashtable growth), but because
rhashtable_init() uses a single static lockdep key for all rhashtables,
this is a real class-level cycle. Once reported, lockdep disables
itself for the remainder of the boot, masking any subsequent locking
bugs.
Drop the mutex. After cancel_work_sync() the rehash worker is quiesced
and, per this function's contract, no other concurrent access is
possible; the tables are therefore owned exclusively by this function
and can be walked without any lock held.
Switch the table walks from rht_dereference() (which requires
ht->mutex to be held under CONFIG_PROVE_RCU) to rcu_dereference_raw(),
which has no lockdep annotation. rht_ptr_exclusive() already uses
rcu_dereference_protected(p, 1) and needs no change.
This is the only place in lib/rhashtable.c where &ht->mutex is
acquired from a path reachable under fs_reclaim; the deferred worker
is the only other site and it is the forward edge. Removing the
acquisition here therefore eliminates the class cycle for all three
subsystems that use simple_xattrs, not just the one in the splat
above. No locking-semantics change is introduced for correct users;
incorrect users would already be racing with rehash worker completion
regardless of the mutex.
Synthetic reproduction of the splat within a few-minute window was
unsuccessful across several attempts (tmpfs and kernfs zombies via
cgroupfs with open-fd-through-rmdir, with and without swap, up to
~60k reclaim-path executions of simple_xattr_ht_free() in a single
run), consistent with the rare coincidence-of-edges profile of the
bug: the forward edge is already registered in /proc/lockdep on any
idle system via rht_deferred_worker, but the reverse edge requires
evict() to complete kernfs_put()'s final release inside the fs_reclaim
critical section, which in my attempts was ordered against rather than
interleaved with the worker.
Fixes: b32c4a213698 ("xattr: add rhashtable-based simple_xattr infrastructure")
Signed-off-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
2026-04-23 02:33:49 +05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
rhashtable: add restart routine in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() cancels re-hash deferred work
then walks and destroys elements. at this moment, some elements can be
still in future_tbl. that elements are not destroyed.
test case:
nft_rhash_destroy() calls rhashtable_free_and_destroy() to destroy
all elements of sets before destroying sets and chains.
But rhashtable_free_and_destroy() doesn't destroy elements of future_tbl.
so that splat occurred.
test script:
%cat test.nft
table ip aa {
map map1 {
type ipv4_addr : verdict;
elements = {
0 : jump a0,
1 : jump a0,
2 : jump a0,
3 : jump a0,
4 : jump a0,
5 : jump a0,
6 : jump a0,
7 : jump a0,
8 : jump a0,
9 : jump a0,
}
}
chain a0 {
}
}
flush ruleset
table ip aa {
map map1 {
type ipv4_addr : verdict;
elements = {
0 : jump a0,
1 : jump a0,
2 : jump a0,
3 : jump a0,
4 : jump a0,
5 : jump a0,
6 : jump a0,
7 : jump a0,
8 : jump a0,
9 : jump a0,
}
}
chain a0 {
}
}
flush ruleset
%while :; do nft -f test.nft; done
Splat looks like:
[ 200.795603] kernel BUG at net/netfilter/nf_tables_api.c:1363!
[ 200.806944] invalid opcode: 0000 [#1] SMP DEBUG_PAGEALLOC KASAN PTI
[ 200.812253] CPU: 1 PID: 1582 Comm: nft Not tainted 4.17.0+ #24
[ 200.820297] Hardware name: To be filled by O.E.M. To be filled by O.E.M./Aptio CRB, BIOS 5.6.5 07/08/2015
[ 200.830309] RIP: 0010:nf_tables_chain_destroy.isra.34+0x62/0x240 [nf_tables]
[ 200.838317] Code: 43 50 85 c0 74 26 48 8b 45 00 48 8b 4d 08 ba 54 05 00 00 48 c7 c6 60 6d 29 c0 48 c7 c7 c0 65 29 c0 4c 8b 40 08 e8 58 e5 fd f8 <0f> 0b 48 89 da 48 b8 00 00 00 00 00 fc ff
[ 200.860366] RSP: 0000:ffff880118dbf4d0 EFLAGS: 00010282
[ 200.866354] RAX: 0000000000000061 RBX: ffff88010cdeaf08 RCX: 0000000000000000
[ 200.874355] RDX: 0000000000000061 RSI: 0000000000000008 RDI: ffffed00231b7e90
[ 200.882361] RBP: ffff880118dbf4e8 R08: ffffed002373bcfb R09: ffffed002373bcfa
[ 200.890354] R10: 0000000000000000 R11: ffffed002373bcfb R12: dead000000000200
[ 200.898356] R13: dead000000000100 R14: ffffffffbb62af38 R15: dffffc0000000000
[ 200.906354] FS: 00007fefc31fd700(0000) GS:ffff88011b800000(0000) knlGS:0000000000000000
[ 200.915533] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 200.922355] CR2: 0000557f1c8e9128 CR3: 0000000106880000 CR4: 00000000001006e0
[ 200.930353] Call Trace:
[ 200.932351] ? nf_tables_commit+0x26f6/0x2c60 [nf_tables]
[ 200.939525] ? nf_tables_setelem_notify.constprop.49+0x1a0/0x1a0 [nf_tables]
[ 200.947525] ? nf_tables_delchain+0x6e0/0x6e0 [nf_tables]
[ 200.952383] ? nft_add_set_elem+0x1700/0x1700 [nf_tables]
[ 200.959532] ? nla_parse+0xab/0x230
[ 200.963529] ? nfnetlink_rcv_batch+0xd06/0x10d0 [nfnetlink]
[ 200.968384] ? nfnetlink_net_init+0x130/0x130 [nfnetlink]
[ 200.975525] ? debug_show_all_locks+0x290/0x290
[ 200.980363] ? debug_show_all_locks+0x290/0x290
[ 200.986356] ? sched_clock_cpu+0x132/0x170
[ 200.990352] ? find_held_lock+0x39/0x1b0
[ 200.994355] ? sched_clock_local+0x10d/0x130
[ 200.999531] ? memset+0x1f/0x40
V2:
- free all tables requested by Herbert Xu
Signed-off-by: Taehee Yoo <ap420073@gmail.com>
Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: David S. Miller <davem@davemloft.net>
2018-07-08 11:55:51 +09:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
2015-01-02 23:00:20 +01:00
|
|
|
|
2026-04-20 20:03:26 -10:00
|
|
|
|
2015-02-25 16:31:54 +01:00
|
|
|
|
rhashtable: Fix race in rhashtable_destroy() and use regular work_struct
When we put our declared work task in the global workqueue with
schedule_delayed_work(), its delay parameter is always zero.
Therefore, we should define a regular work in rhashtable structure
instead of a delayed work.
By the way, we add a condition to check whether resizing functions
are NULL before cancelling the work, avoiding to cancel an
uninitialized work.
Lastly, while we wait for all work items we submitted before to run
to completion with cancel_delayed_work(), ht->mutex has been taken in
rhashtable_destroy(). Moreover, cancel_delayed_work() doesn't return
until all work items are accomplished, and when work items are
scheduled, the work's function - rht_deferred_worker() will be called.
However, as rht_deferred_worker() also needs to acquire the lock,
deadlock might happen at the moment as the lock is already held before.
So if the cancel work function is moved out of the lock covered scope,
this will avoid the deadlock.
Fixes: 97defe1 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: Ying Xue <ying.xue@windriver.com>
Cc: Thomas Graf <tgraf@suug.ch>
Acked-by: Thomas Graf <tgraf@suug.ch>
Signed-off-by: David S. Miller <davem@davemloft.net>
2015-01-16 11:13:09 +08:00
|
|
|
|
rhashtable: drop ht->mutex in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() is a single-shot teardown routine:
cancel_work_sync() has already quiesced the deferred rehash worker, and
the function's documented contract requires the caller to guarantee no
other concurrent access to the rhashtable. Under those conditions
ht->mutex is not protecting anything -- taking it is a leftover from
the original teardown path.
That leftover is actively harmful: it closes a circular lock-class
dependency with fs_reclaim. The deferred rehash worker takes ht->mutex
and then allocates GFP_KERNEL memory in bucket_table_alloc(),
establishing
&ht->mutex -> fs_reclaim
After commit b32c4a213698 ("xattr: add rhashtable-based simple_xattr
infrastructure") introduced simple_xattr_ht_free(), which calls
rhashtable_free_and_destroy(), the simple_xattrs teardown became
reachable from evict() under the dcache shrinker. The subsequent
per-subsystem adaptations made the reverse edge concrete in three
independent code paths:
* commit 52b364fed6e1 ("shmem: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 5bd97f5c5f24 ("kernfs: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 50704c391fbf ("pidfs: adapt to rhashtable-based simple_xattrs")
Any of the three closes the cycle
fs_reclaim -> &ht->mutex
which lockdep reports as follows. This particular splat was observed
organically on a workstation kernel built from vfs-7.1-rc1.xattr at
~35h uptime under normal mixed workload, with CONFIG_PROVE_LOCKING=y.
The path happens to go through kernfs:
WARNING: possible circular locking dependency detected
7.0.0-faeab166167f-with-fixes-v1+ #191 Tainted: G U
kswapd0/243 is trying to acquire lock:
ffff8882e475c0f8 (&ht->mutex){+.+.}-{4:4},
at: rhashtable_free_and_destroy+0x36/0x740
but task is already holding lock:
ffffffffa8ad1d00 (fs_reclaim){+.+.}-{0:0},
at: balance_pgdat+0x995/0x1600
the existing dependency chain (in reverse order) is:
-> #1 (fs_reclaim){+.+.}-{0:0}:
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
fs_reclaim_acquire+0xd9/0x130
__kvmalloc_node_noprof+0xcd/0xb40
bucket_table_alloc.isra.0+0x5a/0x440
rhashtable_rehash_alloc+0x4e/0xd0
rht_deferred_worker+0x14b/0x440
process_one_work+0x8fd/0x16a0
worker_thread+0x601/0xff0
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
-> #0 (&ht->mutex){+.+.}-{4:4}:
check_prev_add+0xdb/0xce0
validate_chain+0x554/0x780
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
__mutex_lock+0x1b2/0x2550
rhashtable_free_and_destroy+0x36/0x740
kernfs_put.part.0+0x119/0x570
evict+0x3b6/0x9c0
__dentry_kill+0x181/0x540
shrink_dentry_list+0x135/0x440
prune_dcache_sb+0xdb/0x150
super_cache_scan+0x2ff/0x520
do_shrink_slab+0x35a/0xee0
shrink_slab_memcg+0x457/0x950
shrink_slab+0x43b/0x550
shrink_one+0x31a/0x6f0
shrink_many+0x31e/0xc80
shrink_node+0xeb3/0x14a0
balance_pgdat+0x8ed/0x1600
kswapd+0x2f3/0x530
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
Possible unsafe locking scenario:
CPU0 CPU1
---- ----
lock(fs_reclaim);
lock(&ht->mutex);
lock(fs_reclaim);
lock(&ht->mutex);
Note that lockdep tracks lock classes, not instances: the two
&ht->mutex sites are on different rhashtable objects (the deferred
worker was triggered by some unrelated rhashtable growth), but because
rhashtable_init() uses a single static lockdep key for all rhashtables,
this is a real class-level cycle. Once reported, lockdep disables
itself for the remainder of the boot, masking any subsequent locking
bugs.
Drop the mutex. After cancel_work_sync() the rehash worker is quiesced
and, per this function's contract, no other concurrent access is
possible; the tables are therefore owned exclusively by this function
and can be walked without any lock held.
Switch the table walks from rht_dereference() (which requires
ht->mutex to be held under CONFIG_PROVE_RCU) to rcu_dereference_raw(),
which has no lockdep annotation. rht_ptr_exclusive() already uses
rcu_dereference_protected(p, 1) and needs no change.
This is the only place in lib/rhashtable.c where &ht->mutex is
acquired from a path reachable under fs_reclaim; the deferred worker
is the only other site and it is the forward edge. Removing the
acquisition here therefore eliminates the class cycle for all three
subsystems that use simple_xattrs, not just the one in the splat
above. No locking-semantics change is introduced for correct users;
incorrect users would already be racing with rehash worker completion
regardless of the mutex.
Synthetic reproduction of the splat within a few-minute window was
unsuccessful across several attempts (tmpfs and kernfs zombies via
cgroupfs with open-fd-through-rmdir, with and without swap, up to
~60k reclaim-path executions of simple_xattr_ht_free() in a single
run), consistent with the rare coincidence-of-edges profile of the
bug: the forward edge is already registered in /proc/lockdep on any
idle system via rht_deferred_worker, but the reverse edge requires
evict() to complete kernfs_put()'s final release inside the fs_reclaim
critical section, which in my attempts was ordered against rather than
interleaved with the worker.
Fixes: b32c4a213698 ("xattr: add rhashtable-based simple_xattr infrastructure")
Signed-off-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
2026-04-23 02:33:49 +05:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: add restart routine in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() cancels re-hash deferred work
then walks and destroys elements. at this moment, some elements can be
still in future_tbl. that elements are not destroyed.
test case:
nft_rhash_destroy() calls rhashtable_free_and_destroy() to destroy
all elements of sets before destroying sets and chains.
But rhashtable_free_and_destroy() doesn't destroy elements of future_tbl.
so that splat occurred.
test script:
%cat test.nft
table ip aa {
map map1 {
type ipv4_addr : verdict;
elements = {
0 : jump a0,
1 : jump a0,
2 : jump a0,
3 : jump a0,
4 : jump a0,
5 : jump a0,
6 : jump a0,
7 : jump a0,
8 : jump a0,
9 : jump a0,
}
}
chain a0 {
}
}
flush ruleset
table ip aa {
map map1 {
type ipv4_addr : verdict;
elements = {
0 : jump a0,
1 : jump a0,
2 : jump a0,
3 : jump a0,
4 : jump a0,
5 : jump a0,
6 : jump a0,
7 : jump a0,
8 : jump a0,
9 : jump a0,
}
}
chain a0 {
}
}
flush ruleset
%while :; do nft -f test.nft; done
Splat looks like:
[ 200.795603] kernel BUG at net/netfilter/nf_tables_api.c:1363!
[ 200.806944] invalid opcode: 0000 [#1] SMP DEBUG_PAGEALLOC KASAN PTI
[ 200.812253] CPU: 1 PID: 1582 Comm: nft Not tainted 4.17.0+ #24
[ 200.820297] Hardware name: To be filled by O.E.M. To be filled by O.E.M./Aptio CRB, BIOS 5.6.5 07/08/2015
[ 200.830309] RIP: 0010:nf_tables_chain_destroy.isra.34+0x62/0x240 [nf_tables]
[ 200.838317] Code: 43 50 85 c0 74 26 48 8b 45 00 48 8b 4d 08 ba 54 05 00 00 48 c7 c6 60 6d 29 c0 48 c7 c7 c0 65 29 c0 4c 8b 40 08 e8 58 e5 fd f8 <0f> 0b 48 89 da 48 b8 00 00 00 00 00 fc ff
[ 200.860366] RSP: 0000:ffff880118dbf4d0 EFLAGS: 00010282
[ 200.866354] RAX: 0000000000000061 RBX: ffff88010cdeaf08 RCX: 0000000000000000
[ 200.874355] RDX: 0000000000000061 RSI: 0000000000000008 RDI: ffffed00231b7e90
[ 200.882361] RBP: ffff880118dbf4e8 R08: ffffed002373bcfb R09: ffffed002373bcfa
[ 200.890354] R10: 0000000000000000 R11: ffffed002373bcfb R12: dead000000000200
[ 200.898356] R13: dead000000000100 R14: ffffffffbb62af38 R15: dffffc0000000000
[ 200.906354] FS: 00007fefc31fd700(0000) GS:ffff88011b800000(0000) knlGS:0000000000000000
[ 200.915533] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 200.922355] CR2: 0000557f1c8e9128 CR3: 0000000106880000 CR4: 00000000001006e0
[ 200.930353] Call Trace:
[ 200.932351] ? nf_tables_commit+0x26f6/0x2c60 [nf_tables]
[ 200.939525] ? nf_tables_setelem_notify.constprop.49+0x1a0/0x1a0 [nf_tables]
[ 200.947525] ? nf_tables_delchain+0x6e0/0x6e0 [nf_tables]
[ 200.952383] ? nft_add_set_elem+0x1700/0x1700 [nf_tables]
[ 200.959532] ? nla_parse+0xab/0x230
[ 200.963529] ? nfnetlink_rcv_batch+0xd06/0x10d0 [nfnetlink]
[ 200.968384] ? nfnetlink_net_init+0x130/0x130 [nfnetlink]
[ 200.975525] ? debug_show_all_locks+0x290/0x290
[ 200.980363] ? debug_show_all_locks+0x290/0x290
[ 200.986356] ? sched_clock_cpu+0x132/0x170
[ 200.990352] ? find_held_lock+0x39/0x1b0
[ 200.994355] ? sched_clock_local+0x10d/0x130
[ 200.999531] ? memset+0x1f/0x40
V2:
- free all tables requested by Herbert Xu
Signed-off-by: Taehee Yoo <ap420073@gmail.com>
Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: David S. Miller <davem@davemloft.net>
2018-07-08 11:55:51 +09:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-03-31 12:58:48 -07:00
|
|
|
|
2019-04-12 11:52:08 +10:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
rhashtable: drop ht->mutex in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() is a single-shot teardown routine:
cancel_work_sync() has already quiesced the deferred rehash worker, and
the function's documented contract requires the caller to guarantee no
other concurrent access to the rhashtable. Under those conditions
ht->mutex is not protecting anything -- taking it is a leftover from
the original teardown path.
That leftover is actively harmful: it closes a circular lock-class
dependency with fs_reclaim. The deferred rehash worker takes ht->mutex
and then allocates GFP_KERNEL memory in bucket_table_alloc(),
establishing
&ht->mutex -> fs_reclaim
After commit b32c4a213698 ("xattr: add rhashtable-based simple_xattr
infrastructure") introduced simple_xattr_ht_free(), which calls
rhashtable_free_and_destroy(), the simple_xattrs teardown became
reachable from evict() under the dcache shrinker. The subsequent
per-subsystem adaptations made the reverse edge concrete in three
independent code paths:
* commit 52b364fed6e1 ("shmem: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 5bd97f5c5f24 ("kernfs: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 50704c391fbf ("pidfs: adapt to rhashtable-based simple_xattrs")
Any of the three closes the cycle
fs_reclaim -> &ht->mutex
which lockdep reports as follows. This particular splat was observed
organically on a workstation kernel built from vfs-7.1-rc1.xattr at
~35h uptime under normal mixed workload, with CONFIG_PROVE_LOCKING=y.
The path happens to go through kernfs:
WARNING: possible circular locking dependency detected
7.0.0-faeab166167f-with-fixes-v1+ #191 Tainted: G U
kswapd0/243 is trying to acquire lock:
ffff8882e475c0f8 (&ht->mutex){+.+.}-{4:4},
at: rhashtable_free_and_destroy+0x36/0x740
but task is already holding lock:
ffffffffa8ad1d00 (fs_reclaim){+.+.}-{0:0},
at: balance_pgdat+0x995/0x1600
the existing dependency chain (in reverse order) is:
-> #1 (fs_reclaim){+.+.}-{0:0}:
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
fs_reclaim_acquire+0xd9/0x130
__kvmalloc_node_noprof+0xcd/0xb40
bucket_table_alloc.isra.0+0x5a/0x440
rhashtable_rehash_alloc+0x4e/0xd0
rht_deferred_worker+0x14b/0x440
process_one_work+0x8fd/0x16a0
worker_thread+0x601/0xff0
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
-> #0 (&ht->mutex){+.+.}-{4:4}:
check_prev_add+0xdb/0xce0
validate_chain+0x554/0x780
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
__mutex_lock+0x1b2/0x2550
rhashtable_free_and_destroy+0x36/0x740
kernfs_put.part.0+0x119/0x570
evict+0x3b6/0x9c0
__dentry_kill+0x181/0x540
shrink_dentry_list+0x135/0x440
prune_dcache_sb+0xdb/0x150
super_cache_scan+0x2ff/0x520
do_shrink_slab+0x35a/0xee0
shrink_slab_memcg+0x457/0x950
shrink_slab+0x43b/0x550
shrink_one+0x31a/0x6f0
shrink_many+0x31e/0xc80
shrink_node+0xeb3/0x14a0
balance_pgdat+0x8ed/0x1600
kswapd+0x2f3/0x530
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
Possible unsafe locking scenario:
CPU0 CPU1
---- ----
lock(fs_reclaim);
lock(&ht->mutex);
lock(fs_reclaim);
lock(&ht->mutex);
Note that lockdep tracks lock classes, not instances: the two
&ht->mutex sites are on different rhashtable objects (the deferred
worker was triggered by some unrelated rhashtable growth), but because
rhashtable_init() uses a single static lockdep key for all rhashtables,
this is a real class-level cycle. Once reported, lockdep disables
itself for the remainder of the boot, masking any subsequent locking
bugs.
Drop the mutex. After cancel_work_sync() the rehash worker is quiesced
and, per this function's contract, no other concurrent access is
possible; the tables are therefore owned exclusively by this function
and can be walked without any lock held.
Switch the table walks from rht_dereference() (which requires
ht->mutex to be held under CONFIG_PROVE_RCU) to rcu_dereference_raw(),
which has no lockdep annotation. rht_ptr_exclusive() already uses
rcu_dereference_protected(p, 1) and needs no change.
This is the only place in lib/rhashtable.c where &ht->mutex is
acquired from a path reachable under fs_reclaim; the deferred worker
is the only other site and it is the forward edge. Removing the
acquisition here therefore eliminates the class cycle for all three
subsystems that use simple_xattrs, not just the one in the splat
above. No locking-semantics change is introduced for correct users;
incorrect users would already be racing with rehash worker completion
regardless of the mutex.
Synthetic reproduction of the splat within a few-minute window was
unsuccessful across several attempts (tmpfs and kernfs zombies via
cgroupfs with open-fd-through-rmdir, with and without swap, up to
~60k reclaim-path executions of simple_xattr_ht_free() in a single
run), consistent with the rare coincidence-of-edges profile of the
bug: the forward edge is already registered in /proc/lockdep on any
idle system via rht_deferred_worker, but the reverse edge requires
evict() to complete kernfs_put()'s final release inside the fs_reclaim
critical section, which in my attempts was ordered against rather than
interleaved with the worker.
Fixes: b32c4a213698 ("xattr: add rhashtable-based simple_xattr infrastructure")
Signed-off-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
2026-04-23 02:33:49 +05:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: drop ht->mutex in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() is a single-shot teardown routine:
cancel_work_sync() has already quiesced the deferred rehash worker, and
the function's documented contract requires the caller to guarantee no
other concurrent access to the rhashtable. Under those conditions
ht->mutex is not protecting anything -- taking it is a leftover from
the original teardown path.
That leftover is actively harmful: it closes a circular lock-class
dependency with fs_reclaim. The deferred rehash worker takes ht->mutex
and then allocates GFP_KERNEL memory in bucket_table_alloc(),
establishing
&ht->mutex -> fs_reclaim
After commit b32c4a213698 ("xattr: add rhashtable-based simple_xattr
infrastructure") introduced simple_xattr_ht_free(), which calls
rhashtable_free_and_destroy(), the simple_xattrs teardown became
reachable from evict() under the dcache shrinker. The subsequent
per-subsystem adaptations made the reverse edge concrete in three
independent code paths:
* commit 52b364fed6e1 ("shmem: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 5bd97f5c5f24 ("kernfs: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 50704c391fbf ("pidfs: adapt to rhashtable-based simple_xattrs")
Any of the three closes the cycle
fs_reclaim -> &ht->mutex
which lockdep reports as follows. This particular splat was observed
organically on a workstation kernel built from vfs-7.1-rc1.xattr at
~35h uptime under normal mixed workload, with CONFIG_PROVE_LOCKING=y.
The path happens to go through kernfs:
WARNING: possible circular locking dependency detected
7.0.0-faeab166167f-with-fixes-v1+ #191 Tainted: G U
kswapd0/243 is trying to acquire lock:
ffff8882e475c0f8 (&ht->mutex){+.+.}-{4:4},
at: rhashtable_free_and_destroy+0x36/0x740
but task is already holding lock:
ffffffffa8ad1d00 (fs_reclaim){+.+.}-{0:0},
at: balance_pgdat+0x995/0x1600
the existing dependency chain (in reverse order) is:
-> #1 (fs_reclaim){+.+.}-{0:0}:
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
fs_reclaim_acquire+0xd9/0x130
__kvmalloc_node_noprof+0xcd/0xb40
bucket_table_alloc.isra.0+0x5a/0x440
rhashtable_rehash_alloc+0x4e/0xd0
rht_deferred_worker+0x14b/0x440
process_one_work+0x8fd/0x16a0
worker_thread+0x601/0xff0
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
-> #0 (&ht->mutex){+.+.}-{4:4}:
check_prev_add+0xdb/0xce0
validate_chain+0x554/0x780
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
__mutex_lock+0x1b2/0x2550
rhashtable_free_and_destroy+0x36/0x740
kernfs_put.part.0+0x119/0x570
evict+0x3b6/0x9c0
__dentry_kill+0x181/0x540
shrink_dentry_list+0x135/0x440
prune_dcache_sb+0xdb/0x150
super_cache_scan+0x2ff/0x520
do_shrink_slab+0x35a/0xee0
shrink_slab_memcg+0x457/0x950
shrink_slab+0x43b/0x550
shrink_one+0x31a/0x6f0
shrink_many+0x31e/0xc80
shrink_node+0xeb3/0x14a0
balance_pgdat+0x8ed/0x1600
kswapd+0x2f3/0x530
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
Possible unsafe locking scenario:
CPU0 CPU1
---- ----
lock(fs_reclaim);
lock(&ht->mutex);
lock(fs_reclaim);
lock(&ht->mutex);
Note that lockdep tracks lock classes, not instances: the two
&ht->mutex sites are on different rhashtable objects (the deferred
worker was triggered by some unrelated rhashtable growth), but because
rhashtable_init() uses a single static lockdep key for all rhashtables,
this is a real class-level cycle. Once reported, lockdep disables
itself for the remainder of the boot, masking any subsequent locking
bugs.
Drop the mutex. After cancel_work_sync() the rehash worker is quiesced
and, per this function's contract, no other concurrent access is
possible; the tables are therefore owned exclusively by this function
and can be walked without any lock held.
Switch the table walks from rht_dereference() (which requires
ht->mutex to be held under CONFIG_PROVE_RCU) to rcu_dereference_raw(),
which has no lockdep annotation. rht_ptr_exclusive() already uses
rcu_dereference_protected(p, 1) and needs no change.
This is the only place in lib/rhashtable.c where &ht->mutex is
acquired from a path reachable under fs_reclaim; the deferred worker
is the only other site and it is the forward edge. Removing the
acquisition here therefore eliminates the class cycle for all three
subsystems that use simple_xattrs, not just the one in the splat
above. No locking-semantics change is introduced for correct users;
incorrect users would already be racing with rehash worker completion
regardless of the mutex.
Synthetic reproduction of the splat within a few-minute window was
unsuccessful across several attempts (tmpfs and kernfs zombies via
cgroupfs with open-fd-through-rmdir, with and without swap, up to
~60k reclaim-path executions of simple_xattr_ht_free() in a single
run), consistent with the rare coincidence-of-edges profile of the
bug: the forward edge is already registered in /proc/lockdep on any
idle system via rht_deferred_worker, but the reverse edge requires
evict() to complete kernfs_put()'s final release inside the fs_reclaim
critical section, which in my attempts was ordered against rather than
interleaved with the worker.
Fixes: b32c4a213698 ("xattr: add rhashtable-based simple_xattr infrastructure")
Signed-off-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
2026-04-23 02:33:49 +05:00
|
|
|
|
2016-09-19 19:00:09 +08:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rhashtable: drop ht->mutex in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() is a single-shot teardown routine:
cancel_work_sync() has already quiesced the deferred rehash worker, and
the function's documented contract requires the caller to guarantee no
other concurrent access to the rhashtable. Under those conditions
ht->mutex is not protecting anything -- taking it is a leftover from
the original teardown path.
That leftover is actively harmful: it closes a circular lock-class
dependency with fs_reclaim. The deferred rehash worker takes ht->mutex
and then allocates GFP_KERNEL memory in bucket_table_alloc(),
establishing
&ht->mutex -> fs_reclaim
After commit b32c4a213698 ("xattr: add rhashtable-based simple_xattr
infrastructure") introduced simple_xattr_ht_free(), which calls
rhashtable_free_and_destroy(), the simple_xattrs teardown became
reachable from evict() under the dcache shrinker. The subsequent
per-subsystem adaptations made the reverse edge concrete in three
independent code paths:
* commit 52b364fed6e1 ("shmem: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 5bd97f5c5f24 ("kernfs: adapt to rhashtable-based simple_xattrs with lazy allocation")
* commit 50704c391fbf ("pidfs: adapt to rhashtable-based simple_xattrs")
Any of the three closes the cycle
fs_reclaim -> &ht->mutex
which lockdep reports as follows. This particular splat was observed
organically on a workstation kernel built from vfs-7.1-rc1.xattr at
~35h uptime under normal mixed workload, with CONFIG_PROVE_LOCKING=y.
The path happens to go through kernfs:
WARNING: possible circular locking dependency detected
7.0.0-faeab166167f-with-fixes-v1+ #191 Tainted: G U
kswapd0/243 is trying to acquire lock:
ffff8882e475c0f8 (&ht->mutex){+.+.}-{4:4},
at: rhashtable_free_and_destroy+0x36/0x740
but task is already holding lock:
ffffffffa8ad1d00 (fs_reclaim){+.+.}-{0:0},
at: balance_pgdat+0x995/0x1600
the existing dependency chain (in reverse order) is:
-> #1 (fs_reclaim){+.+.}-{0:0}:
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
fs_reclaim_acquire+0xd9/0x130
__kvmalloc_node_noprof+0xcd/0xb40
bucket_table_alloc.isra.0+0x5a/0x440
rhashtable_rehash_alloc+0x4e/0xd0
rht_deferred_worker+0x14b/0x440
process_one_work+0x8fd/0x16a0
worker_thread+0x601/0xff0
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
-> #0 (&ht->mutex){+.+.}-{4:4}:
check_prev_add+0xdb/0xce0
validate_chain+0x554/0x780
__lock_acquire+0x506/0xbf0
lock_acquire.part.0+0xc7/0x280
__mutex_lock+0x1b2/0x2550
rhashtable_free_and_destroy+0x36/0x740
kernfs_put.part.0+0x119/0x570
evict+0x3b6/0x9c0
__dentry_kill+0x181/0x540
shrink_dentry_list+0x135/0x440
prune_dcache_sb+0xdb/0x150
super_cache_scan+0x2ff/0x520
do_shrink_slab+0x35a/0xee0
shrink_slab_memcg+0x457/0x950
shrink_slab+0x43b/0x550
shrink_one+0x31a/0x6f0
shrink_many+0x31e/0xc80
shrink_node+0xeb3/0x14a0
balance_pgdat+0x8ed/0x1600
kswapd+0x2f3/0x530
kthread+0x36b/0x470
ret_from_fork+0x5bf/0x910
ret_from_fork_asm+0x1a/0x30
Possible unsafe locking scenario:
CPU0 CPU1
---- ----
lock(fs_reclaim);
lock(&ht->mutex);
lock(fs_reclaim);
lock(&ht->mutex);
Note that lockdep tracks lock classes, not instances: the two
&ht->mutex sites are on different rhashtable objects (the deferred
worker was triggered by some unrelated rhashtable growth), but because
rhashtable_init() uses a single static lockdep key for all rhashtables,
this is a real class-level cycle. Once reported, lockdep disables
itself for the remainder of the boot, masking any subsequent locking
bugs.
Drop the mutex. After cancel_work_sync() the rehash worker is quiesced
and, per this function's contract, no other concurrent access is
possible; the tables are therefore owned exclusively by this function
and can be walked without any lock held.
Switch the table walks from rht_dereference() (which requires
ht->mutex to be held under CONFIG_PROVE_RCU) to rcu_dereference_raw(),
which has no lockdep annotation. rht_ptr_exclusive() already uses
rcu_dereference_protected(p, 1) and needs no change.
This is the only place in lib/rhashtable.c where &ht->mutex is
acquired from a path reachable under fs_reclaim; the deferred worker
is the only other site and it is the forward edge. Removing the
acquisition here therefore eliminates the class cycle for all three
subsystems that use simple_xattrs, not just the one in the splat
above. No locking-semantics change is introduced for correct users;
incorrect users would already be racing with rehash worker completion
regardless of the mutex.
Synthetic reproduction of the splat within a few-minute window was
unsuccessful across several attempts (tmpfs and kernfs zombies via
cgroupfs with open-fd-through-rmdir, with and without swap, up to
~60k reclaim-path executions of simple_xattr_ht_free() in a single
run), consistent with the rare coincidence-of-edges profile of the
bug: the forward edge is already registered in /proc/lockdep on any
idle system via rht_deferred_worker, but the reverse edge requires
evict() to complete kernfs_put()'s final release inside the fs_reclaim
critical section, which in my attempts was ordered against rather than
interleaved with the worker.
Fixes: b32c4a213698 ("xattr: add rhashtable-based simple_xattr infrastructure")
Signed-off-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
2026-04-23 02:33:49 +05:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
rhashtable: add restart routine in rhashtable_free_and_destroy()
rhashtable_free_and_destroy() cancels re-hash deferred work
then walks and destroys elements. at this moment, some elements can be
still in future_tbl. that elements are not destroyed.
test case:
nft_rhash_destroy() calls rhashtable_free_and_destroy() to destroy
all elements of sets before destroying sets and chains.
But rhashtable_free_and_destroy() doesn't destroy elements of future_tbl.
so that splat occurred.
test script:
%cat test.nft
table ip aa {
map map1 {
type ipv4_addr : verdict;
elements = {
0 : jump a0,
1 : jump a0,
2 : jump a0,
3 : jump a0,
4 : jump a0,
5 : jump a0,
6 : jump a0,
7 : jump a0,
8 : jump a0,
9 : jump a0,
}
}
chain a0 {
}
}
flush ruleset
table ip aa {
map map1 {
type ipv4_addr : verdict;
elements = {
0 : jump a0,
1 : jump a0,
2 : jump a0,
3 : jump a0,
4 : jump a0,
5 : jump a0,
6 : jump a0,
7 : jump a0,
8 : jump a0,
9 : jump a0,
}
}
chain a0 {
}
}
flush ruleset
%while :; do nft -f test.nft; done
Splat looks like:
[ 200.795603] kernel BUG at net/netfilter/nf_tables_api.c:1363!
[ 200.806944] invalid opcode: 0000 [#1] SMP DEBUG_PAGEALLOC KASAN PTI
[ 200.812253] CPU: 1 PID: 1582 Comm: nft Not tainted 4.17.0+ #24
[ 200.820297] Hardware name: To be filled by O.E.M. To be filled by O.E.M./Aptio CRB, BIOS 5.6.5 07/08/2015
[ 200.830309] RIP: 0010:nf_tables_chain_destroy.isra.34+0x62/0x240 [nf_tables]
[ 200.838317] Code: 43 50 85 c0 74 26 48 8b 45 00 48 8b 4d 08 ba 54 05 00 00 48 c7 c6 60 6d 29 c0 48 c7 c7 c0 65 29 c0 4c 8b 40 08 e8 58 e5 fd f8 <0f> 0b 48 89 da 48 b8 00 00 00 00 00 fc ff
[ 200.860366] RSP: 0000:ffff880118dbf4d0 EFLAGS: 00010282
[ 200.866354] RAX: 0000000000000061 RBX: ffff88010cdeaf08 RCX: 0000000000000000
[ 200.874355] RDX: 0000000000000061 RSI: 0000000000000008 RDI: ffffed00231b7e90
[ 200.882361] RBP: ffff880118dbf4e8 R08: ffffed002373bcfb R09: ffffed002373bcfa
[ 200.890354] R10: 0000000000000000 R11: ffffed002373bcfb R12: dead000000000200
[ 200.898356] R13: dead000000000100 R14: ffffffffbb62af38 R15: dffffc0000000000
[ 200.906354] FS: 00007fefc31fd700(0000) GS:ffff88011b800000(0000) knlGS:0000000000000000
[ 200.915533] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 200.922355] CR2: 0000557f1c8e9128 CR3: 0000000106880000 CR4: 00000000001006e0
[ 200.930353] Call Trace:
[ 200.932351] ? nf_tables_commit+0x26f6/0x2c60 [nf_tables]
[ 200.939525] ? nf_tables_setelem_notify.constprop.49+0x1a0/0x1a0 [nf_tables]
[ 200.947525] ? nf_tables_delchain+0x6e0/0x6e0 [nf_tables]
[ 200.952383] ? nft_add_set_elem+0x1700/0x1700 [nf_tables]
[ 200.959532] ? nla_parse+0xab/0x230
[ 200.963529] ? nfnetlink_rcv_batch+0xd06/0x10d0 [nfnetlink]
[ 200.968384] ? nfnetlink_net_init+0x130/0x130 [nfnetlink]
[ 200.975525] ? debug_show_all_locks+0x290/0x290
[ 200.980363] ? debug_show_all_locks+0x290/0x290
[ 200.986356] ? sched_clock_cpu+0x132/0x170
[ 200.990352] ? find_held_lock+0x39/0x1b0
[ 200.994355] ? sched_clock_local+0x10d/0x130
[ 200.999531] ? memset+0x1f/0x40
V2:
- free all tables requested by Herbert Xu
Signed-off-by: Taehee Yoo <ap420073@gmail.com>
Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: David S. Miller <davem@davemloft.net>
2018-07-08 11:55:51 +09:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2015-03-24 14:18:20 +01:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-08-02 11:47:44 +02:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-03 18:12:43 +10:00
|
|
|
|
2017-02-25 22:39:50 +08:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-25 22:39:50 +08:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
|
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
2019-04-02 10:07:45 +11:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2020-07-24 20:14:34 +10:00
|
|
|
|
|
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-03 18:12:43 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2018-06-18 12:52:50 +10:00
|
|
|
|
2017-02-11 19:26:47 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
