[PATCH] aio: optimize free kioctx slot search

[Gu Zheng]

Add a 'next_free' field into kioctx_table to store the next id that
may be free, in order to reduce the search region when we insert
kioctx into kioctx table.
When we take a free slot from kioctx_table, update 'next_free' to
the next slot. Also when we free one slot to kioctx_table, update 'next_free'
to the new free slot if it's smaller than 'next_free'. So that we can
ensure that the slots before 'next_free' are all used, and the search can start
from 'next_free' to reduce the search and improve the performance.

Signed-off-by: Gu Zheng <guz....@cn.fujitsu.com>
---
fs/aio.c | 10 ++++++++--
1 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/fs/aio.c b/fs/aio.c
index 062a5f6..489fda6 100644
--- a/fs/aio.c
+++ b/fs/aio.c
@@ -69,6 +69,7 @@ struct aio_ring {
struct kioctx_table {
struct rcu_head rcu;
unsigned nr;
+ unsigned next_free;
struct kioctx *table[];
};

@@ -548,11 +549,12 @@ static int ioctx_add_table(struct kioctx *ctx, struct mm_struct *mm)
table = rcu_dereference(mm->ioctx_table);

while (1) {
- if (table)
- for (i = 0; i < table->nr; i++)
+ if (table && table->next_free < table->nr)
+ for (i = table->next_free; i < table->nr; i++)
if (!table->table[i]) {
ctx->id = i;
table->table[i] = ctx;
+ table->next_free = i + 1;
rcu_read_unlock();
spin_unlock(&mm->ioctx_lock);

@@ -579,8 +581,10 @@ static int ioctx_add_table(struct kioctx *ctx, struct mm_struct *mm)
old = rcu_dereference(mm->ioctx_table);

if (!old) {
+ table->next_free = 0;
rcu_assign_pointer(mm->ioctx_table, table);
} else if (table->nr > old->nr) {
+ table->next_free = old->nr;
memcpy(table->table, old->table,
old->nr * sizeof(struct kioctx *));

@@ -716,6 +720,8 @@ static void kill_ioctx(struct mm_struct *mm, struct kioctx *ctx)

WARN_ON(ctx != table->table[ctx->id]);
table->table[ctx->id] = NULL;
+ if (ctx->id < table->next_free)
+ table->next_free = ctx->id;
rcu_read_unlock();
spin_unlock(&mm->ioctx_lock);

--
1.7.7

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majo...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

[Miao Xie]

On thu, 26 Dec 2013 18:22:10 +0800, Gu Zheng wrote:
> Add a 'next_free' field into kioctx_table to store the next id that
> may be free, in order to reduce the search region when we insert
> kioctx into kioctx table.
> When we take a free slot from kioctx_table, update 'next_free' to
> the next slot. Also when we free one slot to kioctx_table, update 'next_free'
> to the new free slot if it's smaller than 'next_free'. So that we can
> ensure that the slots before 'next_free' are all used, and the search can start
> from 'next_free' to reduce the search and improve the performance.
>
> Signed-off-by: Gu Zheng <guz....@cn.fujitsu.com>

Reviewed-by: Miao Xie <mi...@cn.fujitsu.com>

Thanks
Miao

[Matthew Wilcox]

On Thu, Dec 26, 2013 at 06:22:10PM +0800, Gu Zheng wrote:
> to the new free slot if it's smaller than 'next_free'. So that we can
> ensure that the slots before 'next_free' are all used, and the search can start
> from 'next_free' to reduce the search and improve the performance.

Have you benchmarked it? What kinds of improvements are you seeing?

--
Matthew Wilcox Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours. We can't possibly take such
a retrograde step."

[Gu Zheng]

Hi Matthew,

On 12/26/2013 10:13 PM, Matthew Wilcox wrote:

> On Thu, Dec 26, 2013 at 06:22:10PM +0800, Gu Zheng wrote:
>> to the new free slot if it's smaller than 'next_free'. So that we can
>> ensure that the slots before 'next_free' are all used, and the search can start
>> from 'next_free' to reduce the search and improve the performance.
>
> Have you benchmarked it? What kinds of improvements are you seeing?

Not yet. But the improvement is obvious, we can always reduce the search region and
improve the hit rate when trying to find a free slot with this change.

Regards,
Gu

[Matthew Wilcox]

On Fri, Dec 27, 2013 at 06:32:24PM +0800, Gu Zheng wrote:
> Hi Matthew,
> On 12/26/2013 10:13 PM, Matthew Wilcox wrote:
>
> > On Thu, Dec 26, 2013 at 06:22:10PM +0800, Gu Zheng wrote:
> >> to the new free slot if it's smaller than 'next_free'. So that we can
> >> ensure that the slots before 'next_free' are all used, and the search can start
> >> from 'next_free' to reduce the search and improve the performance.
> >
> > Have you benchmarked it? What kinds of improvements are you seeing?
>
> Not yet. But the improvement is obvious, we can always reduce the search region and
> improve the hit rate when trying to find a free slot with this change.

It's not so obvious to me. You've added extra stores, which may dirty
an additional cacheline. That may end up costing more than it saves.
I suspect the difference is lost in the noise, but I've been wrong about
these things before.

--
Matthew Wilcox Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours. We can't possibly take such
a retrograde step."