[PATCH] replace ida in workqueue with page-sized buffer

[PATCH] replace ida in workqueue with page-sized buffer

[Hillf Danton]

The id of worker of global work queue is monitored with kernel library, ida.

The ida in global work queue is redefined to be page-sized buffer,
which is allocated when initializing workqueue.

The new id allocator could monitor ids in the rage from 0 to INT_MAX.
The buffer is used to store freed ids, and if the peak number of ids,
in workqueue as whole, is not out of the capacity of the allocated
buffer, there is no more allocation of buffer after initializing.

The advantage looks that the new allocator runs faster.

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---

--- a/kernel/workqueue.c	2010-11-01 19:54:12.000000000 +0800
+++ b/kernel/workqueue.c	2010-12-18 20:34:48.000000000 +0800
@@ -40,7 +40,6 @@
 #include <linux/kallsyms.h>
 #include <linux/debug_locks.h>
 #include <linux/lockdep.h>
-#include <linux/idr.h>

 #include "workqueue_sched.h"

@@ -137,6 +136,13 @@ struct worker {
 	struct work_struct	rebind_work;	/* L: rebind worker to cpu */
 };

+struct ida_s {
+	int	id;
+	int	freed;
+	int	alloc;
+	int	*buf;
+};
+
 /*
  * Global per-cpu workqueue.  There's one and only one for each cpu
  * and all works are queued and processed here regardless of their
@@ -159,7 +165,7 @@ struct global_cwq {
 	struct timer_list	idle_timer;	/* L: worker idle timeout */
 	struct timer_list	mayday_timer;	/* L: SOS timer for dworkers */

-	struct ida		worker_ida;	/* L: for worker IDs */
+	struct ida_s		worker_ida;	/* L: for worker IDs */

 	struct task_struct	*trustee;	/* L: for gcwq shutdown */
 	unsigned int		trustee_state;	/* L: trustee state */
@@ -1280,6 +1286,34 @@ static struct worker *alloc_worker(void)
 	return worker;
 }

+static inline void ida_free_id(struct ida_s *ida, int id)
+{
+	if (id == ida->id -1)
+		ida->id--;
+	else if (ida->freed < ida->alloc) {
+		ida->buf[ida->freed] = id;
+		ida->freed++;
+	}
+}
+
+static inline int ida_alloc_id(struct ida_s *ida)
+{
+	int id;
+
+	if (ida->freed) {
+		ida->freed--;
+		return ida->buf[ida->freed];
+	}
+
+	id = ida->id;
+	if (id < INT_MAX)
+		ida->id++;
+	else
+		id = -ENOSPC;
+
+	return id;
+}
+
 /**
  * create_worker - create a new workqueue worker
  * @gcwq: gcwq the new worker will belong to
@@ -1302,14 +1336,12 @@ static struct worker *create_worker(stru
 	int id = -1;

 	spin_lock_irq(&gcwq->lock);
-	while (ida_get_new(&gcwq->worker_ida, &id)) {
-		spin_unlock_irq(&gcwq->lock);
-		if (!ida_pre_get(&gcwq->worker_ida, GFP_KERNEL))
-			goto fail;
-		spin_lock_irq(&gcwq->lock);
-	}
+	id = ida_alloc_id(&gcwq->worker_ida);
 	spin_unlock_irq(&gcwq->lock);

+	if (id < 0)
+		return NULL;
+
 	worker = alloc_worker();
 	if (!worker)
 		goto fail;
@@ -1343,7 +1375,7 @@ static struct worker *create_worker(stru
 fail:
 	if (id >= 0) {
 		spin_lock_irq(&gcwq->lock);
-		ida_remove(&gcwq->worker_ida, id);
+		ida_free_id(&gcwq->worker_ida, id);
 		spin_unlock_irq(&gcwq->lock);
 	}
 	kfree(worker);
@@ -1399,7 +1431,7 @@ static void destroy_worker(struct worker
 	kfree(worker);

 	spin_lock_irq(&gcwq->lock);
-	ida_remove(&gcwq->worker_ida, id);
+	ida_free_id(&gcwq->worker_ida, id);
 }

 static void idle_worker_timeout(unsigned long __gcwq)
@@ -3640,6 +3672,18 @@ out_unlock:
 }
 #endif /* CONFIG_FREEZER */

+static int __init init_ida(struct ida_s *ida, int pages)
+{
+	ida->buf = kzalloc(pages * PAGE_SIZE, GFP_KERNEL);
+	if (! ida->buf)
+		return -ENOMEM;
+
+	ida->alloc = (pages * PAGE_SIZE) / sizeof(int);
+	ida->freed = 0;
+	ida->id = 0;
+	return 0;
+}
+
 static int __init init_workqueues(void)
 {
 	unsigned int cpu;
@@ -3667,7 +3711,7 @@ static int __init init_workqueues(void)
 		setup_timer(&gcwq->mayday_timer, gcwq_mayday_timeout,
 			    (unsigned long)gcwq);

-		ida_init(&gcwq->worker_ida);
+		BUG_ON(0 != init_ida(&gcwq->worker_ida, 1));

 		gcwq->trustee_state = TRUSTEE_DONE;
 		init_waitqueue_head(&gcwq->trustee_wait);

Re: [PATCH] replace ida in workqueue with page-sized buffer

[Hillf Danton]

On Sat, Dec 18, 2010 at 9:10 PM, Hillf Danton <dhillf@gmail.com> wrote:
> The id of worker of global work queue is monitored with kernel library, ida.
>
> The ida in global work queue is redefined to be page-sized buffer,
> which is allocated when initializing workqueue.
>
> The new id allocator could monitor ids in the rage from 0 to INT_MAX.
> The buffer is used to store freed ids, and if the peak number of ids,
> in workqueue as whole, is not out of the capacity of the allocated
> buffer, there is no more allocation of buffer after initializing.
>
> The advantage looks that the new allocator runs faster.
>
> Signed-off-by: Hillf Danton <dhillf@gmail.com>

Hey Ingo

Please take a glance at the patch for replacing ida in workqueue at

       https://lkml.org/lkml/2010/12/18/35

thanks
Hillf

Re: [PATCH] replace ida in workqueue with page-sized buffer

[Ingo Molnar]

* Hillf Danton <dhillf@gmail.com> wrote:

> On Sat, Dec 18, 2010 at 9:10 PM, Hillf Danton <dhillf@gmail.com> wrote:
> > The id of worker of global work queue is monitored with kernel library, ida.
> >
> > The ida in global work queue is redefined to be page-sized buffer,
> > which is allocated when initializing workqueue.
> >
> > The new id allocator could monitor ids in the rage from 0 to INT_MAX.
> > The buffer is used to store freed ids, and if the peak number of ids,
> > in workqueue as whole, is not out of the capacity of the allocated
> > buffer, there is no more allocation of buffer after initializing.
> >
> > The advantage looks that the new allocator runs faster.
> >
> > Signed-off-by: Hillf Danton <dhillf@gmail.com>
> 
> Hey Ingo
> 
> Please take a glance at the patch for replacing ida in workqueue at
> 
>        https://lkml.org/lkml/2010/12/18/35
> 

Tejun is driving workqueues these days. (I've Cc:-ed him.)

Thanks,

	Ingo

Re: [PATCH] replace ida in workqueue with page-sized buffer

[Tejun Heo]

Hello,

On Sat, Dec 18, 2010 at 09:10:18PM +0800, Hillf Danton wrote:
> The id of worker of global work queue is monitored with kernel library, ida.
> 
> The ida in global work queue is redefined to be page-sized buffer,
> which is allocated when initializing workqueue.
> 
> The new id allocator could monitor ids in the rage from 0 to INT_MAX.
> The buffer is used to store freed ids, and if the peak number of ids,
> in workqueue as whole, is not out of the capacity of the allocated
> buffer, there is no more allocation of buffer after initializing.
> 
> The advantage looks that the new allocator runs faster.

I'm confused about why this is necessary.  It's not like workqueue ID
alloc/dealloc is hot path to begin with (they're quite lazy) and
during worker creation / destruction ida is a quite insignificant
part, so what is it trying to optimize?  It's not like ida allocator
is slow to begin with.

Also, the allocator looks quite dubious.

* What happens if more entries than what can fit in a page are freed?
  It'll just lose track of it.

* ida guarantees that always the lowest available slot is allocated.
  The new allocator doesn't.

So, why oh why?

-- 
tejun

Re: [PATCH] replace ida in workqueue with page-sized buffer

[Hillf Danton]

On Sat, Jan 8, 2011 at 7:57 PM, Ingo Molnar <mingo@elte.hu> wrote:
>> Hey Ingo
>>
>> Please take a glance at the patch for replacing ida in workqueue at
>>
>>        https://lkml.org/lkml/2010/12/18/35
>>
>
> Tejun is driving workqueues these days. (I've Cc:-ed him.)
>
> Thanks,
>
>        Ingo

Thank you Ingo.
Hillf

Re: [PATCH] replace ida in workqueue with page-sized buffer

[Hillf Danton]

On Sat, Jan 8, 2011 at 10:01 PM, Tejun Heo <tj@kernel.org> wrote:
> Hello,
>
> On Sat, Dec 18, 2010 at 09:10:18PM +0800, Hillf Danton wrote:
>> The id of worker of global work queue is monitored with kernel library, ida.
>>
>> The ida in global work queue is redefined to be page-sized buffer,
>> which is allocated when initializing workqueue.
>>
>> The new id allocator could monitor ids in the rage from 0 to INT_MAX.
>> The buffer is used to store freed ids, and if the peak number of ids,
>> in workqueue as whole, is not out of the capacity of the allocated
>> buffer, there is no more allocation of buffer after initializing.
>>
>> The advantage looks that the new allocator runs faster.
>
> I'm confused about why this is necessary.  It's not like workqueue ID
> alloc/dealloc is hot path to begin with (they're quite lazy) and
> during worker creation / destruction ida is a quite insignificant

Great point. Since quite lazy, the patch is quite inapplicable.

> part, so what is it trying to optimize?  It's not like ida allocator
> is slow to begin with.
>
> Also, the allocator looks quite dubious.
>
> * What happens if more entries than what can fit in a page are freed?
>  It'll just lose track of it.
>

Losing track of allocated ids could happen only if allocation is not
quite lazy, and it could be fixed by extending the page buffer, though
not included in the delivered patch.

> * ida guarantees that always the lowest available slot is allocated.
>  The new allocator doesn't.
>

Since the allocated ids are then hashed, the lowest available looks
unnecessary in workqueue, which simplifies allocation.

Thanks a lot for reviewing the patch.
Hillf