Re: [PATCH 2/2] kvfree_rcu: convert a page cache to lock-free variant
On Fri, Mar 12, 2021 at 01:38:14PM +0100, Uladzislau Rezki wrote:
> Hello, Paul.
>
> Please do not consider this patch. It is buggy :)
Consider it formally withdrawn, and thank you for letting me know!
Thanx, Paul
> --
> Vlad Rezki
>
> On Mon, Mar 8, 2021 at 8:50 PM Uladzislau Rezki (Sony)
> wrote:
>
> > Implement an access to the page cache as lock-free variant. This
> > is done because there are extra places where an access is required,
> > therefore making it lock-less will remove any lock contention.
> >
> > For example we have a shrinker path as well as a reclaim kthread.
> > In both cases a current CPU can access to a remote per-cpu page
> > cache that would require taking a lock to protect it.
> >
> > An "rcuscale" performance test suite can detect it and shows some
> > slight improvements:
> >
> > ../kvm.sh --memory 16G --torture rcuscale --allcpus --duration 10 \
> > --kconfig CONFIG_NR_CPUS=64 --bootargs "rcuscale.kfree_rcu_test=1 \
> > rcuscale.kfree_nthreads=16 rcuscale.holdoff=20 rcuscale.kfree_loops=1 \
> > rcuscale.kfree_rcu_test_double=1 torture.disable_onoff_at_boot"
> > --trust-make
> >
> > 100 iterations, checking total time taken by all kfree'ers in ns.:
> >
> > default: AVG: 10968415107.5 MIN: 10668412500 MAX: 11312145160
> > patch: AVG: 10787596486.1 MIN: 10397559880 MAX: 11214901050
> >
> > Signed-off-by: Uladzislau Rezki (Sony)
> > ---
> > kernel/rcu/tree.c | 91 +--
> > 1 file changed, 56 insertions(+), 35 deletions(-)
> >
> > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > index 9c8cfb01e9a6..4f04664d5ac0 100644
> > --- a/kernel/rcu/tree.c
> > +++ b/kernel/rcu/tree.c
> > @@ -3167,8 +3167,9 @@ struct kfree_rcu_cpu {
> > atomic_t work_in_progress;
> > struct hrtimer hrtimer;
> >
> > + // lock-free cache.
> > struct llist_head bkvcache;
> > - int nr_bkv_objs;
> > + atomic_t nr_bkv_objs;
> > };
> >
> > static DEFINE_PER_CPU(struct kfree_rcu_cpu, krc) = {
> > @@ -3215,49 +3216,79 @@ krc_this_cpu_unlock(struct kfree_rcu_cpu *krcp,
> > unsigned long flags)
> > raw_spin_unlock_irqrestore(>lock, flags);
> > }
> >
> > +/*
> > + * Increment 'v', if 'v' is below 'thresh'. Returns true if we
> > + * succeeded, false if 'v' + 1 would be bigger than 'thresh'.
> > + *
> > + * Decrement 'v' if 'v' is upper 'thresh'. Returns true if we
> > + * succeeded, false if 'v' - 1 would be smaller than 'thresh'.
> > + */
> > +static inline bool
> > +atomic_test_inc_dec(atomic_t *v, unsigned int thresh, bool inc)
> > +{
> > + unsigned int cur = atomic_read(v);
> > + unsigned int old;
> > +
> > + for (;;) {
> > + if (inc) {
> > + if (cur >= thresh)
> > + return false;
> > + } else {
> > + if (cur <= thresh)
> > + return false;
> > + }
> > +
> > + old = atomic_cmpxchg(v, cur, inc ? (cur + 1):(cur - 1));
> > + if (old == cur)
> > + break;
> > +
> > + cur = old;
> > + }
> > +
> > + return true;
> > +}
> > +
> > static inline struct kvfree_rcu_bulk_data *
> > get_cached_bnode(struct kfree_rcu_cpu *krcp)
> > {
> > - if (!krcp->nr_bkv_objs)
> > - return NULL;
> > + struct kvfree_rcu_bulk_data *bnode = NULL;
> >
> > - krcp->nr_bkv_objs--;
> > - return (struct kvfree_rcu_bulk_data *)
> > - llist_del_first(>bkvcache);
> > + if (atomic_test_inc_dec(>nr_bkv_objs, 0, false))
> > + bnode = (struct kvfree_rcu_bulk_data *)
> > + llist_del_first(>bkvcache);
> > +
> > + return bnode;
> > }
> >
> > static inline bool
> > put_cached_bnode(struct kfree_rcu_cpu *krcp,
> > struct kvfree_rcu_bulk_data *bnode)
> > {
> > - // Check the limit.
> > - if (krcp->nr_bkv_objs >= rcu_min_cached_objs)
> > - return false;
> > -
> > - llist_add((struct llist_node *) bnode, >bkvcache);
> > - krcp->nr_bkv_objs++;
> > - return true;
> > + if (atomic_test_inc_dec(>nr_bkv_objs, rcu_min_cached_objs,
> > true)) {
> > + llist_add((struct llist_node *) bnode, >bkvcache);
> > + return true;
> > + }
> >
> > + return false;
> > }
> >
> > static int
> > drain_page_cache(struct kfree_rcu_cpu *krcp)
> > {
> > - unsigned long flags;
> > - struct llist_node *page_list, *pos, *n;
> > - int freed = 0;
> > + struct kvfree_rcu_bulk_data *bnode;
> > + int num_pages, i;
> >
> > - raw_spin_lock_irqsave(>lock, flags);
> > - page_list = llist_del_all(>bkvcache);
> > - krcp->nr_bkv_objs = 0;
> > - raw_spin_unlock_irqrestore(>lock, flags);
> > + num_pages = atomic_read(>nr_bkv_objs);
> > +
> > +
[PATCH 2/2] kvfree_rcu: convert a page cache to lock-free variant
Implement an access to the page cache as lock-free variant. This
is done because there are extra places where an access is required,
therefore making it lock-less will remove any lock contention.
For example we have a shrinker path as well as a reclaim kthread.
In both cases a current CPU can access to a remote per-cpu page
cache that would require taking a lock to protect it.
An "rcuscale" performance test suite can detect it and shows some
slight improvements:
../kvm.sh --memory 16G --torture rcuscale --allcpus --duration 10 \
--kconfig CONFIG_NR_CPUS=64 --bootargs "rcuscale.kfree_rcu_test=1 \
rcuscale.kfree_nthreads=16 rcuscale.holdoff=20 rcuscale.kfree_loops=1 \
rcuscale.kfree_rcu_test_double=1 torture.disable_onoff_at_boot" --trust-make
100 iterations, checking total time taken by all kfree'ers in ns.:
default: AVG: 10968415107.5 MIN: 10668412500 MAX: 11312145160
patch: AVG: 10787596486.1 MIN: 10397559880 MAX: 11214901050
Signed-off-by: Uladzislau Rezki (Sony)
---
kernel/rcu/tree.c | 91 +--
1 file changed, 56 insertions(+), 35 deletions(-)
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 9c8cfb01e9a6..4f04664d5ac0 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3167,8 +3167,9 @@ struct kfree_rcu_cpu {
atomic_t work_in_progress;
struct hrtimer hrtimer;
+ // lock-free cache.
struct llist_head bkvcache;
- int nr_bkv_objs;
+ atomic_t nr_bkv_objs;
};
static DEFINE_PER_CPU(struct kfree_rcu_cpu, krc) = {
@@ -3215,49 +3216,79 @@ krc_this_cpu_unlock(struct kfree_rcu_cpu *krcp,
unsigned long flags)
raw_spin_unlock_irqrestore(>lock, flags);
}
+/*
+ * Increment 'v', if 'v' is below 'thresh'. Returns true if we
+ * succeeded, false if 'v' + 1 would be bigger than 'thresh'.
+ *
+ * Decrement 'v' if 'v' is upper 'thresh'. Returns true if we
+ * succeeded, false if 'v' - 1 would be smaller than 'thresh'.
+ */
+static inline bool
+atomic_test_inc_dec(atomic_t *v, unsigned int thresh, bool inc)
+{
+ unsigned int cur = atomic_read(v);
+ unsigned int old;
+
+ for (;;) {
+ if (inc) {
+ if (cur >= thresh)
+ return false;
+ } else {
+ if (cur <= thresh)
+ return false;
+ }
+
+ old = atomic_cmpxchg(v, cur, inc ? (cur + 1):(cur - 1));
+ if (old == cur)
+ break;
+
+ cur = old;
+ }
+
+ return true;
+}
+
static inline struct kvfree_rcu_bulk_data *
get_cached_bnode(struct kfree_rcu_cpu *krcp)
{
- if (!krcp->nr_bkv_objs)
- return NULL;
+ struct kvfree_rcu_bulk_data *bnode = NULL;
- krcp->nr_bkv_objs--;
- return (struct kvfree_rcu_bulk_data *)
- llist_del_first(>bkvcache);
+ if (atomic_test_inc_dec(>nr_bkv_objs, 0, false))
+ bnode = (struct kvfree_rcu_bulk_data *)
+ llist_del_first(>bkvcache);
+
+ return bnode;
}
static inline bool
put_cached_bnode(struct kfree_rcu_cpu *krcp,
struct kvfree_rcu_bulk_data *bnode)
{
- // Check the limit.
- if (krcp->nr_bkv_objs >= rcu_min_cached_objs)
- return false;
-
- llist_add((struct llist_node *) bnode, >bkvcache);
- krcp->nr_bkv_objs++;
- return true;
+ if (atomic_test_inc_dec(>nr_bkv_objs, rcu_min_cached_objs, true))
{
+ llist_add((struct llist_node *) bnode, >bkvcache);
+ return true;
+ }
+ return false;
}
static int
drain_page_cache(struct kfree_rcu_cpu *krcp)
{
- unsigned long flags;
- struct llist_node *page_list, *pos, *n;
- int freed = 0;
+ struct kvfree_rcu_bulk_data *bnode;
+ int num_pages, i;
- raw_spin_lock_irqsave(>lock, flags);
- page_list = llist_del_all(>bkvcache);
- krcp->nr_bkv_objs = 0;
- raw_spin_unlock_irqrestore(>lock, flags);
+ num_pages = atomic_read(>nr_bkv_objs);
+
+ for (i = 0; i < num_pages; i++) {
+ bnode = get_cached_bnode(krcp);
+ if (!bnode)
+ break;
- llist_for_each_safe(pos, n, page_list) {
- free_page((unsigned long)pos);
- freed++;
+ free_page((unsigned long) bnode);
}
- return freed;
+ return i;
}
/*
@@ -3314,10 +3345,8 @@ static void kfree_rcu_work(struct work_struct *work)
}
rcu_lock_release(_callback_map);
- raw_spin_lock_irqsave(>lock, flags);
if (put_cached_bnode(krcp, bkvhead[i]))
bkvhead[i] = NULL;
- raw_spin_unlock_irqrestore(>lock, flags);
if (bkvhead[i])
