linux-kernel - [PATCH v2 3/5] of: unittest: hashed phandles unitest

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:	Mon, 16 May 2016 19:52:34 +0300
From:	Pantelis Antoniou <pantelis.antoniou@...sulko.com>
To:	Rob Herring <robherring2@...il.com>
Cc:	Frank Rowand <frowand.list@...il.com>,
	Matt Porter <mporter@...sulko.com>,
	Grant Likely <grant.likely@...retlab.ca>,
	Koen Kooi <koen@...inion.thruhere.net>,
	Guenter Roeck <linux@...ck-us.net>,
	Marek Vasut <marex@...x.de>,
	Geert Uytterhoeven <geert@...ux-m68k.org>,
	devicetree@...r.kernel.org, linux-kernel@...r.kernel.org,
	Pantelis Antoniou <pantelis.antoniou@...sulko.com>,
	Pantelis Antoniou <panto@...oniou-consulting.com>
Subject: [PATCH v2 3/5] of: unittest: hashed phandles unitest

Add a benchmarking hashed phandles unittest which report what kind
of speed up we get switching to hashed phandle lookups.

 ### dt-test ### the hash method is 8.2 times faster than the original

On the beaglebone we perform about 1877 phandle lookups until that
point in the unittest. Each non-hashed lookup takes about 23us when
the cash is hot, while the hash lookup takes about 3us.

For those 1877 lookup we get a speedup in the boot sequence of
1877 * (23 - 3) = 37.5ms, which is not spectacular but there's no
point in wasting cycles and energy.

Signed-off-by: Pantelis Antoniou <pantelis.antoniou@...sulko.com>
---
 drivers/of/unittest.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)

diff --git a/drivers/of/unittest.c b/drivers/of/unittest.c
index 7ea3689..59cad84 100644
--- a/drivers/of/unittest.c
+++ b/drivers/of/unittest.c
@@ -25,6 +25,9 @@
 
 #include <linux/bitops.h>
 
+#include <linux/timekeeping.h>
+#include <linux/random.h>
+
 #include "of_private.h"
 
 static struct unittest_results {
@@ -2266,6 +2269,70 @@ out:
 static inline void __init of_unittest_overlay(void) { }
 #endif
 
+#define PHANDLE_LOOKUPS	1000
+
+static void __init of_unittest_phandle_hash(void)
+{
+	struct device_node *node;
+	phandle max_phandle;
+	u32 ph;
+	unsigned long flags;
+	int i, j, total;
+	ktime_t start, end;
+	s64 dur[2];
+	int dec, frac;
+
+	/* test only available when hashing is available */
+	if (!of_phandle_ht_available()) {
+		pr_warn("phandle hash test requires hash to be initialized\n");
+		return;
+	}
+
+	/* find the maximum phandle of the tree */
+	raw_spin_lock_irqsave(&devtree_lock, flags);
+	max_phandle = 0;
+	total = 0;
+	for_each_of_allnodes(node) {
+		if (node->phandle != (phandle)-1U &&
+				node->phandle > max_phandle)
+			max_phandle = node->phandle;
+		total++;
+	}
+	raw_spin_unlock_irqrestore(&devtree_lock, flags);
+	max_phandle++;
+
+	pr_debug("phandle: max-phandle #%u, #%d total nodes\n",
+			(u32)max_phandle, total);
+
+	/* perform random lookups using the hash */
+	for (j = 0; j < 2; j++) {
+
+		/* disabled for pass #0, enabled for pass #1 */
+		of_phandle_ht_is_disabled = j == 0;
+
+		start = ktime_get_raw();
+		for (i = 0; i < PHANDLE_LOOKUPS; i++) {
+			ph = prandom_u32() % max_phandle;
+			node = of_find_node_by_phandle(ph);
+			of_node_put(node);
+		}
+		end = ktime_get_raw();
+
+		dur[j] = ktime_to_us(end) - ktime_to_us(start);
+		pr_debug("#%d lookups in %lld us (%s)\n",
+				PHANDLE_LOOKUPS, dur[j],
+				j == 0 ? "original" : "hashed");
+	}
+
+	unittest(dur[0] > dur[1], "Non hashing phandles are faster!?");
+
+	dec = (int)div64_s64(dur[0] * 10 + 5, dur[1]);
+	frac = dec % 10;
+	dec /= 10;
+	pr_info("the hash method is %d.%d times faster than the original\n",
+			dec, frac);
+}
+
 static int __init of_unittest(void)
 {
 	struct device_node *np;
@@ -2300,6 +2367,7 @@ static int __init of_unittest(void)
 	of_unittest_match_node();
 	of_unittest_platform_populate();
 	of_unittest_overlay();
+	of_unittest_phandle_hash();
 
 	/* Double check linkage after removing testcase data */
 	of_unittest_check_tree_linkage();
-- 
1.7.12