Skip to contentSkip to conversation

aio: optimize free kioctx slot search

PATCH In review Gu Zheng 3 participants 5 messages Dec 26, 2013 – Dec 27, 2013

Subsystems (2)
lore
Share & tools
lore

Gu Zheng

author
#0 lore raw

PATCH 1/1 aio: optimize free kioctx slot search

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.

---
 fs/aio.c |   10 ++++++++--
 1 files changed, 8 insertions(+), 2 deletions(-)
fs/aio.c +8 -2
index 062a5f6..489fda6 100644
@@ -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);
 
Signature · 7 lines
1.7.7

--
To unsubscribe, send a message with 'unsubscribe linux-aio' in
the body to [email protected].  For more info on Linux AIO,
see: http://www.kvack.org/aio/
Don't email: <a href=mailto:"[email protected]">[email protected]</a>
Reviewed-by on v1 1/1
#1 lore raw
Quoted 10 lines · 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.

Thanks
Miao

Quoted 52 lines
---
 fs/aio.c |   10 ++++++++--
 1 files changed, 8 insertions(+), 2 deletions(-)
fs/aio.c +8 -2
index 062a5f6..489fda6 100644
@@ -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);
 
#2 lore raw
In reply to Gu Zheng
Quoted 3 lines · Gu Zheng

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?

Signature · 4 lines
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."
author
#3 lore raw

Hi Matthew,

Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · Gu Zheng

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

Quoted 1 line

--
To unsubscribe, send a message with 'unsubscribe linux-aio' in the body to [email protected]. For more info on Linux AIO,
see: http://www.kvack.org/aio/
Don't email: <a href=mailto:"[email protected]">[email protected]</a>

#4 lore raw
Quoted 4 lines · Gu Zheng

Hi Matthew,

Quoted 1 line · Matthew Wilcox

On Thu, Dec 26, 2013 at 06:22:10PM +0800, Gu Zheng wrote:

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

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.

Signature · 4 lines
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."