can: add support for hash based access to EFF frame filters

PATCH Applied Oliver Hartkopp 2 participants 6 messages Apr 2, 2014 – May 19, 2014

Subsystems (4)

Networking Documentation CAN network drivers CAN network layer

lore

Share & tools

lore

Oliver Hartkopp

author maintainer

2014-04-02 18:25 UTC #0 lore raw

v2 cover can: add support for hash based access to EFF frame filters

In contrast to the direct access to the single SFF frame filters (which are indexed by the SFF CAN ID itself) the single EFF frame filters are arranged in a single linked hlist. To reduce the hlist traversal in the case of many filter subscriptions a hash based access is introduced for single EFF filters.

This patch set enhances and documents the hash based EFF filter sets in af_can.c .

Changes in v2:
Some coding style fixes, like
- indroduce spaces arround shift operations
- use ARRAY_SIZE(d->rx_sff) instead of CAN_SFF_RCV_ARRAY_SZ
- use ARRAY_SIZE(d->rx_eff) instead of CAN_EFF_RCV_ARRAY_SZ
- change to forward hash function as suggested by Marc

Oliver Hartkopp (3):
can: proc: make array printing function indenpendent from sff frames
can: add hash based access to single EFF frame filters
can: add documentation for CAN filter usage optimisation

 Documentation/networking/can.txt | 35 ++++++++++++++++++
 net/can/af_can.c                 | 31 +++++++++++++---
 net/can/af_can.h                 |  9 +++--
 net/can/proc.c                   | 76 ++++++++++++++++++++++++++++++++--------
 4 files changed, 129 insertions(+), 22 deletions(-)

Signature · 1 line

1.9.1

Oliver Hartkopp

author maintainer

2014-04-02 18:25 UTC #1 lore raw

PATCH v2 1/3 can: proc: make array printing function indenpendent from sff frames

The can_rcvlist_sff_proc_show_one() function which prints the array of filters for the single SFF CAN identifiers is prepared to be used by a second caller. Therefore it is also renamed to properly describe its future functionality.

Signed-off-by Oliver Hartkopp <[email protected]>

---
 net/can/af_can.h |  4 +++-
 net/can/proc.c   | 28 ++++++++++++++++------------
 2 files changed, 19 insertions(+), 13 deletions(-)

net/can/af_can.h +3 -1

index 6de58b4..b4bdaa3 100644
@@ -59,12 +59,14 @@ struct receiver {
 	char *ident;
 };
 
+#define CAN_SFF_RCV_ARRAY_SZ (1 << CAN_SFF_ID_BITS)
+
 enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };
 
 /* per device receive filters linked at dev->ml_priv */
 struct dev_rcv_lists {
 	struct hlist_head rx[RX_MAX];
-	struct hlist_head rx_sff[0x800];
+	struct hlist_head rx_sff[CAN_SFF_RCV_ARRAY_SZ];
 	int remove_on_zero_entries;
 	int entries;
 };

net/can/proc.c +16 ~~-12~~

index b543470..1621e59 100644
@@ -389,25 +389,26 @@ static const struct file_operations can_rcvlist_proc_fops = {
 	.release	= single_release,
 };
 
-static inline void can_rcvlist_sff_proc_show_one(struct seq_file *m,
-						 struct net_device *dev,
-						 struct dev_rcv_lists *d)
+static inline void can_rcvlist_proc_show_array(struct seq_file *m,
+					       struct net_device *dev,
+					       struct hlist_head *rcv_array,
+					       unsigned int rcv_array_sz)
 {
-	int i;
+	unsigned int i;
 	int all_empty = 1;
 
 	/* check whether at least one list is non-empty */
-	for (i = 0; i < 0x800; i++)
-		if (!hlist_empty(&d->rx_sff[i])) {
+	for (i = 0; i < rcv_array_sz; i++)
+		if (!hlist_empty(&rcv_array[i])) {
 			all_empty = 0;
 			break;
 		}
 
 	if (!all_empty) {
 		can_print_recv_banner(m);
-		for (i = 0; i < 0x800; i++) {
-			if (!hlist_empty(&d->rx_sff[i]))
-				can_print_rcvlist(m, &d->rx_sff[i], dev);
+		for (i = 0; i < rcv_array_sz; i++) {
+			if (!hlist_empty(&rcv_array[i]))
+				can_print_rcvlist(m, &rcv_array[i], dev);
 		}
 	} else
 		seq_printf(m, "  (%s: no entry)\n", DNAME(dev));

@@ -425,12 +426,15 @@ static int can_rcvlist_sff_proc_show(struct seq_file *m, void *v)
 
 	/* sff receive list for 'all' CAN devices (dev == NULL) */
 	d = &can_rx_alldev_list;
-	can_rcvlist_sff_proc_show_one(m, NULL, d);
+	can_rcvlist_proc_show_array(m, NULL, d->rx_sff, ARRAY_SIZE(d->rx_sff));
 
 	/* sff receive list for registered CAN devices */
 	for_each_netdev_rcu(&init_net, dev) {
-		if (dev->type == ARPHRD_CAN && dev->ml_priv)
-			can_rcvlist_sff_proc_show_one(m, dev, dev->ml_priv);
+		if (dev->type == ARPHRD_CAN && dev->ml_priv) {
+			d = dev->ml_priv;
+			can_rcvlist_proc_show_array(m, dev, d->rx_sff,
+						    ARRAY_SIZE(d->rx_sff));
+		}
 	}
 
 	rcu_read_unlock();

Signature · 1 line

1.9.1

Oliver Hartkopp

author maintainer

2014-04-02 18:25 UTC #2 lore raw

PATCH v2 2/3 can: add hash based access to single EFF frame filters

In reply to Oliver Hartkopp

Signed-off-by Oliver Hartkopp <[email protected]>

---
 net/can/af_can.c | 31 ++++++++++++++++++++++++++-----
 net/can/af_can.h |  5 ++++-
 net/can/proc.c   | 48 +++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 75 insertions(+), 9 deletions(-)

net/can/af_can.c +26 -5

index a27f8aa..ce82337 100644
@@ -338,6 +338,29 @@ static struct dev_rcv_lists *find_dev_rcv_lists(struct net_device *dev)
 }
 
 /**
+ * effhash - hash function for 29 bit CAN identifier reduction
+ * @can_id: 29 bit CAN identifier
+ *
+ * Description:
+ *  To reduce the linear traversal in one linked list of _single_ EFF CAN
+ *  frame subscriptions the 29 bit identifier is mapped to 10 bits.
+ *  (see CAN_EFF_RCV_HASH_BITS definition)
+ *
+ * Return:
+ *  Hash value from 0x000 - 0x3FF ( enforced by CAN_EFF_RCV_HASH_BITS mask )
+ */
+static unsigned int effhash(canid_t can_id)
+{
+	unsigned int hash;
+
+	hash = can_id;
+	hash ^= can_id >> CAN_EFF_RCV_HASH_BITS;
+	hash ^= can_id >> (2 * CAN_EFF_RCV_HASH_BITS);
+
+	return hash & ((1 << CAN_EFF_RCV_HASH_BITS) - 1);
+}
+
+/**
  * find_rcv_list - determine optimal filterlist inside device filter struct
  * @can_id: pointer to CAN identifier of a given can_filter
  * @mask: pointer to CAN mask of a given can_filter

@@ -400,10 +423,8 @@ static struct hlist_head *find_rcv_list(canid_t *can_id, canid_t *mask,
 	    !(*can_id & CAN_RTR_FLAG)) {
 
 		if (*can_id & CAN_EFF_FLAG) {
-			if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS)) {
-				/* RFC: a future use-case for hash-tables? */
-				return &d->rx[RX_EFF];
-			}
+			if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS))
+				return &d->rx_eff[effhash(*can_id)];
 		} else {
 			if (*mask == (CAN_SFF_MASK | CAN_EFF_RTR_FLAGS))
 				return &d->rx_sff[*can_id];

@@ -632,7 +653,7 @@ static int can_rcv_filter(struct dev_rcv_lists *d, struct sk_buff *skb)
 		return matches;
 
 	if (can_id & CAN_EFF_FLAG) {
-		hlist_for_each_entry_rcu(r, &d->rx[RX_EFF], list) {
+		hlist_for_each_entry_rcu(r, &d->rx_eff[effhash(can_id)], list) {
 			if (r->can_id == can_id) {
 				deliver(skb, r);
 				matches++;

net/can/af_can.h +4 -1

index b4bdaa3..fca0fe9 100644
@@ -60,13 +60,16 @@ struct receiver {
 };
 
 #define CAN_SFF_RCV_ARRAY_SZ (1 << CAN_SFF_ID_BITS)
+#define CAN_EFF_RCV_HASH_BITS 10
+#define CAN_EFF_RCV_ARRAY_SZ (1 << CAN_EFF_RCV_HASH_BITS)
 
-enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };
+enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_MAX };
 
 /* per device receive filters linked at dev->ml_priv */
 struct dev_rcv_lists {
 	struct hlist_head rx[RX_MAX];
 	struct hlist_head rx_sff[CAN_SFF_RCV_ARRAY_SZ];
+	struct hlist_head rx_eff[CAN_EFF_RCV_ARRAY_SZ];
 	int remove_on_zero_entries;
 	int entries;
 };

net/can/proc.c +45 -3

66 lines not on this page · raw message

Signature · 1 line

1.9.1

Oliver Hartkopp

author maintainer

2014-04-02 18:25 UTC #3 lore raw

PATCH v2 3/3 can: add documentation for CAN filter usage optimisation

In reply to Oliver Hartkopp

To benefit from special filters for single SFF or single EFF CAN identifier subscriptions the CAN_EFF_FLAG bit and the CAN_RTR_FLAG bit has to be set together with the CAN_(SFF|EFF)_MASK in can_filter.mask.

Signed-off-by Oliver Hartkopp <[email protected]>

---
 Documentation/networking/can.txt | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

Documentation/networking/can.txt +35 -0

index 0cbe6ec..9261fe8 100644
@@ -469,6 +469,41 @@ solution for a couple of reasons:
   having this 'send only' use-case we may remove the receive list in the
   Kernel to save a little (really a very little!) CPU usage.
 
+  4.1.1.1 CAN filter usage optimisation
+
+  The CAN filters are processed in per-device filter lists at CAN frame
+  reception time. To reduce the number of checks that need to be performed
+  while walking through the filter lists the CAN core provides an optimized
+  filter handling when the filter subscription focusses on a single CAN ID.
+
+  For the possible 2048 SFF CAN identifiers the identifier is used as an index
+  to access the corresponding subscription list without any further checks.
+  For the 2^29 possible EFF CAN identifiers a 10 bit XOR folding is used as
+  hash function to retrieve the EFF table index.
+
+  To benefit from the optimized filters for single CAN identifiers the
+  CAN_SFF_MASK or CAN_EFF_MASK have to be set into can_filter.mask together
+  with set CAN_EFF_FLAG and CAN_RTR_FLAG bits. A set CAN_EFF_FLAG bit in the
+  can_filter.mask makes clear that it matters whether a SFF or EFF CAN ID is
+  subscribed. E.g. in the example from above
+
+    rfilter[0].can_id   = 0x123;
+    rfilter[0].can_mask = CAN_SFF_MASK;
+
+  both SFF frames with CAN ID 0x123 and EFF frames with 0xXXXXX123 can pass.
+
+  To filter for only 0x123 (SFF) and 0x12345678 (EFF) CAN identifiers the
+  filter has to be defined in this way to benefit from the optimized filters:
+
+    struct can_filter rfilter[2];
+
+    rfilter[0].can_id   = 0x123;
+    rfilter[0].can_mask = (CAN_EFF_FLAG | CAN_RTR_FLAG | CAN_SFF_MASK);
+    rfilter[1].can_id   = 0x12345678 | CAN_EFF_FLAG;
+    rfilter[1].can_mask = (CAN_EFF_FLAG | CAN_RTR_FLAG | CAN_EFF_MASK);
+
+    setsockopt(s, SOL_CAN_RAW, CAN_RAW_FILTER, &rfilter, sizeof(rfilter));
+
   4.1.2 RAW socket option CAN_RAW_ERR_FILTER
 
   As described in chapter 3.4 the CAN interface driver can generate so

Signature · 1 line

1.9.1

Oliver Hartkopp

author maintainer

2014-05-06 17:55 UTC #4 lore raw

v2 cover can: add support for hash based access to EFF frame filters

In reply to Oliver Hartkopp

Hey Marc,

what about this patch set for can-next you had so much fun to review?

:-)

I was running this patch for a month now and it still applies properly.

Regards,
Oliver

-------- Original Message --------
Subject: [PATCH v2 0/3] can: add support for hash based access to EFF frame filters
Date: Wed, 2 Apr 2014 20:25:24 +0200
From: Oliver Hartkopp <[email protected]>
To: [email protected]
CC: Oliver Hartkopp <[email protected]>

This patch set enhances and documents the hash based EFF filter sets in af_can.c .

 Documentation/networking/can.txt | 35 ++++++++++++++++++
 net/can/af_can.c                 | 31 +++++++++++++---
 net/can/af_can.h                 |  9 +++--
 net/can/proc.c                   | 76 ++++++++++++++++++++++++++++++++--------
 4 files changed, 129 insertions(+), 22 deletions(-)

Signature · 6 lines

1.9.1

--
To unsubscribe from this list: send the line "unsubscribe linux-can" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Marc Kleine-Budde

maintainer Applied

2014-05-19 06:24 UTC #5 lore raw

In reply to Oliver Hartkopp

Quoted 20 lines · Oliver Hartkopp

In contrast to the direct access to the single SFF frame filters (which are indexed by the SFF CAN ID itself) the single EFF frame filters are arranged in a single linked hlist. To reduce the hlist traversal in the case of many filter subscriptions a hash based access is introduced for single EFF filters.
This patch set enhances and documents the hash based EFF filter sets in af_can.c .
Changes in v2:
Some coding style fixes, like
- indroduce spaces arround shift operations
- use ARRAY_SIZE(d->rx_sff) instead of CAN_SFF_RCV_ARRAY_SZ
- use ARRAY_SIZE(d->rx_eff) instead of CAN_EFF_RCV_ARRAY_SZ
- change to forward hash function as suggested by Marc
Oliver Hartkopp (3):
can: proc: make array printing function indenpendent from sff frames
can: add hash based access to single EFF frame filters
can: add documentation for CAN filter usage optimisation

Quoted 6 lines

 Documentation/networking/can.txt | 35 ++++++++++++++++++
 net/can/af_can.c                 | 31 +++++++++++++---
 net/can/af_can.h                 |  9 +++--
 net/can/proc.c                   | 76 ++++++++++++++++++++++++++++++++--------
 4 files changed, 129 insertions(+), 22 deletions(-)

Applied all three patches to can-next

Tnx,
Marc

Signature · 4 lines

Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |