linux-kernel - [PATCH RFC 2/2] percpu_ida: Use for_each_tlm() macro for CPU lookup in steal

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 26 Mar 2014 14:34:24 +0100
From:	Alexander Gordeev <agordeev@...hat.com>
To:	linux-kernel@...r.kernel.org
Cc:	Alexander Gordeev <agordeev@...hat.com>,
	Kent Overstreet <kmo@...erainc.com>,
	Jens Axboe <axboe@...nel.dk>, Shaohua Li <shli@...nel.org>,
	Nicholas Bellinger <nab@...ux-iscsi.org>
Subject: [PATCH RFC 2/2] percpu_ida: Use for_each_tlm() macro for CPU lookup in steal_tags()

Function steal_tags() iterates thru 'cpus_have_tags' cpumask
ignoring the system's CPU topology. That leads to situations
when a newly stolen tag and the data structure(s) associated
with it (i.e. struct request in the block layer) topology-
wise are more remote from the stealing CPU than it could have
been had steal_tags() take the system's topology into accout.

This update makes use of for_each_tlm() macro and softens the
problem described above. As result, cache misses caused by
accesses from a CPU that stole a tag to that tag's associated
data are lessened.

As a side effect, percpu_ida::cpu_last_stolen variable became
superfluous and get eliminated.

Signed-off-by: Alexander Gordeev <agordeev@...hat.com>
Cc: Kent Overstreet <kmo@...erainc.com>
Cc: Jens Axboe <axboe@...nel.dk>
Cc: Shaohua Li <shli@...nel.org>
Cc: Nicholas Bellinger <nab@...ux-iscsi.org>
---
 include/linux/percpu_ida.h |    1 -
 lib/percpu_ida.c           |   46 ++++++++++++++++++-------------------------
 2 files changed, 19 insertions(+), 28 deletions(-)

diff --git a/include/linux/percpu_ida.h b/include/linux/percpu_ida.h
index f5cfdd6..0d891f3 100644
--- a/include/linux/percpu_ida.h
+++ b/include/linux/percpu_ida.h
@@ -40,7 +40,6 @@ struct percpu_ida {
 		 * we want to pick a cpu at random. Cycling through them every
 		 * time we steal is a bit easier and more or less equivalent:
 		 */
-		unsigned		cpu_last_stolen;
 
 		/* For sleeping on allocation failure */
 		wait_queue_head_t	wait;
diff --git a/lib/percpu_ida.c b/lib/percpu_ida.c
index 93d145e..5c51baa 100644
--- a/lib/percpu_ida.c
+++ b/lib/percpu_ida.c
@@ -63,42 +63,34 @@ static inline void move_tags(unsigned *dst, unsigned *dst_nr,
 static inline void steal_tags(struct percpu_ida *pool,
 			      struct percpu_ida_cpu *tags)
 {
-	unsigned cpus_have_tags, cpu = pool->cpu_last_stolen;
 	struct percpu_ida_cpu *remote;
+	struct cpumask **tlm;
+	int cpu;
 
-	for (cpus_have_tags = cpumask_weight(&pool->cpus_have_tags);
-	     cpus_have_tags; cpus_have_tags--) {
-		cpu = cpumask_next(cpu, &pool->cpus_have_tags);
+	for_each_tlm(tlm) {
+		for_each_cpu_and(cpu, *tlm, &pool->cpus_have_tags) {
+			cpumask_clear_cpu(cpu, &pool->cpus_have_tags);
 
-		if (cpu >= nr_cpu_ids) {
-			cpu = cpumask_first(&pool->cpus_have_tags);
-			if (cpu >= nr_cpu_ids)
-				BUG();
-		}
+			remote = per_cpu_ptr(pool->tag_cpu, cpu);
+			if (remote == tags)
+				continue;
 
-		pool->cpu_last_stolen = cpu;
-		remote = per_cpu_ptr(pool->tag_cpu, cpu);
+			spin_lock(&remote->lock);
 
-		cpumask_clear_cpu(cpu, &pool->cpus_have_tags);
+			if (remote->nr_free) {
+				memcpy(tags->freelist,
+				       remote->freelist,
+				       sizeof(unsigned) * remote->nr_free);
 
-		if (remote == tags)
-			continue;
+				tags->nr_free = remote->nr_free;
+				remote->nr_free = 0;
+			}
 
-		spin_lock(&remote->lock);
+			spin_unlock(&remote->lock);
 
-		if (remote->nr_free) {
-			memcpy(tags->freelist,
-			       remote->freelist,
-			       sizeof(unsigned) * remote->nr_free);
-
-			tags->nr_free = remote->nr_free;
-			remote->nr_free = 0;
+			if (tags->nr_free)
+				return;
 		}
-
-		spin_unlock(&remote->lock);
-
-		if (tags->nr_free)
-			break;
 	}
 }
 
-- 
1.7.7.6

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