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  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date:	Mon, 12 Mar 2012 22:12:21 -0700
From:	Maciej Żenczykowski <zenczykowski@...il.com>
To:	Maciej Żenczykowski <maze@...gle.com>
Cc:	netdev@...r.kernel.org
Subject: [PATCH] net: pfifo_fast - use ffs(x)-1 instead of array lookup

From: Maciej Żenczykowski <maze@...gle.com>

See ffs(x) definition in arch/x86/include/asm/bitops.h

  ffs - find first set bit in word

  ffs(value) returns 0 if value is 0 or the position of the first
  set bit if value is nonzero. The first (least significant) bit
  is at position 1.

On x86_64 ffs(x) is effectively:
  Z := -1
  BSFL X, Z
  return Z + 1

Since we subtract one, we effectively end up with:
  Z := -1
  BSFL X, Z
  return Z

This is certainly more readable than the open coded array that
was there before, supports an easier change in the number of bands,
and is probably faster to boot (no memory lookup).

However, on other architectures ffs() might not be so pretty,
hence use a clever arithmetic hack on other archs.
Unfortunately it only support 3 bands.

Signed-off-by: Maciej Żenczykowski <maze@...gle.com>
---
 net/sched/sch_generic.c |   18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

diff --git a/net/sched/sch_generic.c b/net/sched/sch_generic.c
index 67fc573e013a..935492d6a0b6 100644
--- a/net/sched/sch_generic.c
+++ b/net/sched/sch_generic.c
@@ -436,9 +436,19 @@ struct pfifo_fast_priv {
  * Convert a bitmap to the first band number where an skb is queued, where:
  * 	bitmap=0 means there are no skbs on any band.
  * 	bitmap=1 means there is an skb on band 0.
- *	bitmap=7 means there are skbs on all 3 bands, etc.
+ * 	bitmap=7 means there are skbs on all 3 bands, etc.
+ *
+ * This is equivalent to ffs(i) - 1
  */
-static const int bitmap2band[] = {-1, 0, 1, 0, 2, 0, 1, 0};
+static inline int bitmap2band(int i)
+{
+#if defined(CONFIG_X86_64)
+	return ffs(i) - 1; /* Known to be efficient. */
+#else
+	/* For i in 0..7 returns {-1, 0, 1, 0, 2, 0, 1, 0}[i] */
+	return ((26468 >> (i+i)) & 3) - 1;
+#endif
+}
 
 static inline struct sk_buff_head *band2list(struct pfifo_fast_priv *priv,
 					     int band)
@@ -464,7 +474,7 @@ static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc *qdisc)
 static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
 {
 	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
-	int band = bitmap2band[priv->bitmap];
+	int band = bitmap2band(priv->bitmap);
 
 	if (likely(band >= 0)) {
 		struct sk_buff_head *list = band2list(priv, band);
@@ -483,7 +493,7 @@ static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
 static struct sk_buff *pfifo_fast_peek(struct Qdisc *qdisc)
 {
 	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
-	int band = bitmap2band[priv->bitmap];
+	int band = bitmap2band(priv->bitmap);
 
 	if (band >= 0) {
 		struct sk_buff_head *list = band2list(priv, band);
-- 
1.7.9.4

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists