lkml.org 
[lkml]   [2019]   [Dec]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v4 1/2] rcu/tree: Add basic support for kfree_rcu() batching
On Tue, Dec 10, 2019 at 10:53:48AM +0100, Uladzislau Rezki wrote:
> On Wed, Sep 18, 2019 at 11:58:11AM +0200, Uladzislau Rezki wrote:
> > > Recently a discussion about stability and performance of a system
> > > involving a high rate of kfree_rcu() calls surfaced on the list [1]
> > > which led to another discussion how to prepare for this situation.
> > >
> > > This patch adds basic batching support for kfree_rcu(). It is "basic"
> > > because we do none of the slab management, dynamic allocation, code
> > > moving or any of the other things, some of which previous attempts did
> > > [2]. These fancier improvements can be follow-up patches and there are
> > > different ideas being discussed in those regards. This is an effort to
> > > start simple, and build up from there. In the future, an extension to
> > > use kfree_bulk and possibly per-slab batching could be done to further
> > > improve performance due to cache-locality and slab-specific bulk free
> > > optimizations. By using an array of pointers, the worker thread
> > > processing the work would need to read lesser data since it does not
> > > need to deal with large rcu_head(s) any longer.
> > >
> According to https://lkml.org/lkml/2017/12/19/706 there was an attempt
> to make use of kfree_bulk() interface. I have done some tests based on
> your patch and enhanced kfree_bulk() logic. Basically storing pointers
> in an array with a specific size makes sense to me and seems to others
> as well. I mean in comparison with "pointer chasing" way, when there is
> probably a cache misses each time the access is done to next element:

This looks like a great idea to me, that is chaining blocks together.

>
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index 1fe0418a5901..4f68662c1568 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -2595,6 +2595,13 @@ EXPORT_SYMBOL_GPL(call_rcu);
>
> /* Maximum number of jiffies to wait before draining a batch. */
> #define KFREE_DRAIN_JIFFIES (HZ / 50)
> +#define KFREE_BULK_MAX_SIZE 64
> +
> +struct kfree_rcu_bulk_data {
> + int nr_records;
> + void *records[KFREE_BULK_MAX_SIZE];
> + struct kfree_rcu_bulk_data *next;
> +};
>
> /*
> * Maximum number of kfree(s) to batch, if this limit is hit then the batch of
> @@ -2607,15 +2614,24 @@ struct kfree_rcu_cpu {
> struct rcu_work rcu_work;
>
> /* The list of objects being queued in a batch but are not yet
> - * scheduled to be freed.
> + * scheduled to be freed. For emergency path only.
> */
> struct rcu_head *head;
>
> /* The list of objects that have now left ->head and are queued for
> - * freeing after a grace period.
> + * freeing after a grace period. For emergency path only.
> */
> struct rcu_head *head_free;
>
> + /*
> + * It is a block list that keeps pointers in the array of specific
> + * size which are freed by the kfree_bulk() logic. Intends to improve
> + * drain throughput.
> + */
> + struct kfree_rcu_bulk_data *bhead;
> + struct kfree_rcu_bulk_data *bhead_free;
> + struct kfree_rcu_bulk_data *bcached;
> +
> /* Protect concurrent access to this structure. */
> spinlock_t lock;
> @@ -2637,23 +2653,39 @@ static void kfree_rcu_work(struct work_struct *work)
> {
> unsigned long flags;
> struct rcu_head *head, *next;
> + struct kfree_rcu_bulk_data *bhead, *bnext;
> struct kfree_rcu_cpu *krcp = container_of(to_rcu_work(work),
> struct kfree_rcu_cpu, rcu_work);
>
> spin_lock_irqsave(&krcp->lock, flags);
> head = krcp->head_free;
> krcp->head_free = NULL;
> + bhead = krcp->bhead_free;
> + krcp->bhead_free = NULL;
> spin_unlock_irqrestore(&krcp->lock, flags);
>
> /*
> * The head is detached and not referenced from anywhere, so lockless
> * access is Ok.
> */
> + for (; bhead; bhead = bnext) {
> + bnext = bhead->next;
> + kfree_bulk(bhead->nr_records, bhead->records);
> +
> + if (cmpxchg(&krcp->bcached, NULL, bhead))
> + kfree(bhead);

After the first iteration of loop, say cmpxchg succeeded, then is there a
point it doing repeated cmpxchg in future loops? AIUI, cmpxchg has a
serializing cost and better be avoided where possible.

But... there can be a case where bcached was used up while the loop is
running. Then there could be a point in reassigning it in future loop
iterations.

> +
> + cond_resched_tasks_rcu_qs();
> + }
> +
> + /*
> + * Emergency case only. It can happen under low
> + * memory condition when kmalloc gets failed, so
> + * the "bulk" path can not be temporary maintained.
> + */
> for (; head; head = next) {
> next = head->next;
> - /* Could be possible to optimize with kfree_bulk in future */

I'm glad I had left this comment ;-) ;-)

> __rcu_reclaim(rcu_state.name, head);
> - cond_resched_tasks_rcu_qs();

Why take off this cond_resched..() ?

> }
> }
>
> @@ -2671,11 +2703,15 @@ static inline bool queue_kfree_rcu_work(struct kfree_rcu_cpu *krcp)
> * another one, just refuse the optimization and it will be retried
> * again in KFREE_DRAIN_JIFFIES time.
> */
> - if (krcp->head_free)
> + if (krcp->bhead_free || krcp->head_free)
> return false;
>
> krcp->head_free = krcp->head;
> krcp->head = NULL;
> +
> + krcp->bhead_free = krcp->bhead;
> + krcp->bhead = NULL;
> +
> INIT_RCU_WORK(&krcp->rcu_work, kfree_rcu_work);
> queue_rcu_work(system_wq, &krcp->rcu_work);
>
> @@ -2747,6 +2783,7 @@ void kfree_call_rcu(struct rcu_head *head, rcu_callback_t func)
> {
> unsigned long flags;
> struct kfree_rcu_cpu *krcp;
> + struct kfree_rcu_bulk_data *bnode;
>
> /* kfree_call_rcu() batching requires timers to be up. If the scheduler
> * is not yet up, just skip batching and do the non-batched version.
> @@ -2754,16 +2791,35 @@ void kfree_call_rcu(struct rcu_head *head, rcu_callback_t func)
> if (rcu_scheduler_active != RCU_SCHEDULER_RUNNING)
> return kfree_call_rcu_nobatch(head, func);
>
> - head->func = func;
> -
> local_irq_save(flags); /* For safely calling this_cpu_ptr(). */
> krcp = this_cpu_ptr(&krc);
> spin_lock(&krcp->lock);
>
> + if (!krcp->bhead ||
> + krcp->bhead->nr_records == KFREE_BULK_MAX_SIZE) {
> + /* Need a new block. */
> + if (!(bnode = xchg(&krcp->bcached, NULL)))

Is it better to cache more than 1 block? But this is also Ok I think.

> + bnode = kmalloc(sizeof(struct kfree_rcu_bulk_data),
> + GFP_ATOMIC | __GFP_NOWARN);
> +
> + /* If gets failed, maintain the list instead. */
> + if (unlikely(!bnode)) {
> + head->func = func;
> + head->next = krcp->head;
> + krcp->head = head;
> + goto check_and_schedule;
> + }
> +
> + bnode->nr_records = 0;
> + bnode->next = krcp->bhead;
> + krcp->bhead = bnode;
> + }
> +
> /* Queue the kfree but don't yet schedule the batch. */
> - head->next = krcp->head;
> - krcp->head = head;
> + krcp->bhead->records[krcp->bhead->nr_records++] =
> + (void *) head - (unsigned long) func;
>
> +check_and_schedule:

> /* Schedule monitor for timely drain after KFREE_DRAIN_JIFFIES. */
> if (!xchg(&krcp->monitor_todo, true))
> schedule_delayed_work(&krcp->monitor_work, KFREE_DRAIN_JIFFIES);
>
> See below some test results with/without this patch:
>
> # HiKey 960 8xCPUs
> rcuperf.ko kfree_loops=200000 kfree_alloc_num=1000 kfree_rcu_test=1
> [ 159.017771] Total time taken by all kfree'ers: 92783584881 ns, loops: 200000, batches: 5117
> [ 126.862573] Total time taken by all kfree'ers: 70935580718 ns, loops: 200000, batches: 3953
>
> Running the "rcuperf" shows approximately ~23% better throughput in case of using

Awesome. Wow. Is this +23% with a slab allocator configuration?

You mentioned you will post a new version. Once you do it, I can take
another look and run some tests. Then I'll give your patch the Reviewed-by tag.

Thanks Uladzislau and Paul!

- Joel

> or its RCU callback does the work faster that leads to better throughput.
>
> I can upload the RFC/PATCH of that change providing the test details and so on.
>
> Any thoughts about it?
>
> Thank you in advance!
>
> --
> Vlad Rezki

\
 
 \ /
  Last update: 2019-12-12 06:28    [W:0.102 / U:21.744 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site