[PATCH bpf-next v2 1/6] include/bpf.h: Remove map_insert_ctx() stubs

[PATCH bpf-next v2 1/6] include/bpf.h: Remove map_insert_ctx() stubs

[Toke Høiland-Jørgensen]

From: Toke Høiland-Jørgensen <toke@redhat.com>

When we changed the device and CPU maps to use linked lists instead of
bitmaps, we also removed the need for the map_insert_ctx() helpers to keep
track of the bitmaps inside each map. However, it seems I forgot to remove
the function definitions stubs, so remove those here.

Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 include/linux/bpf.h |   10 ----------
 1 file changed, 10 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 18f4cc2c6acd..bfdb54dd2ad1 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -713,7 +713,6 @@ struct xdp_buff;
 struct sk_buff;
 
 struct bpf_dtab_netdev *__dev_map_lookup_elem(struct bpf_map *map, u32 key);
-void __dev_map_insert_ctx(struct bpf_map *map, u32 index);
 void __dev_map_flush(struct bpf_map *map);
 int dev_map_enqueue(struct bpf_dtab_netdev *dst, struct xdp_buff *xdp,
 		    struct net_device *dev_rx);
@@ -721,7 +720,6 @@ int dev_map_generic_redirect(struct bpf_dtab_netdev *dst, struct sk_buff *skb,
 			     struct bpf_prog *xdp_prog);
 
 struct bpf_cpu_map_entry *__cpu_map_lookup_elem(struct bpf_map *map, u32 key);
-void __cpu_map_insert_ctx(struct bpf_map *map, u32 index);
 void __cpu_map_flush(struct bpf_map *map);
 int cpu_map_enqueue(struct bpf_cpu_map_entry *rcpu, struct xdp_buff *xdp,
 		    struct net_device *dev_rx);
@@ -801,10 +799,6 @@ static inline struct net_device  *__dev_map_lookup_elem(struct bpf_map *map,
 	return NULL;
 }
 
-static inline void __dev_map_insert_ctx(struct bpf_map *map, u32 index)
-{
-}
-
 static inline void __dev_map_flush(struct bpf_map *map)
 {
 }
@@ -834,10 +828,6 @@ struct bpf_cpu_map_entry *__cpu_map_lookup_elem(struct bpf_map *map, u32 key)
 	return NULL;
 }
 
-static inline void __cpu_map_insert_ctx(struct bpf_map *map, u32 index)
-{
-}
-
 static inline void __cpu_map_flush(struct bpf_map *map)
 {
 }

[PATCH bpf-next v2 3/6] uapi/bpf: Add new devmap_hash type

[Toke Høiland-Jørgensen]

From: Toke Høiland-Jørgensen <toke@redhat.com>

This adds the BPF_MAP_TYPE_DEVMAP_HASH type to the uapi bpf.h header, for
use in the subsequent patch adding the support to the kernel.

Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 include/uapi/linux/bpf.h |    1 +
 1 file changed, 1 insertion(+)

diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index ead27aebf491..7a0301407f3a 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -134,6 +134,7 @@ enum bpf_map_type {
 	BPF_MAP_TYPE_QUEUE,
 	BPF_MAP_TYPE_STACK,
 	BPF_MAP_TYPE_SK_STORAGE,
+	BPF_MAP_TYPE_DEVMAP_HASH,
 };
 
 /* Note that tracing related programs such as

[PATCH bpf-next v2 2/6] xdp: Refactor devmap allocation code for reuse

[Toke Høiland-Jørgensen]

From: Toke Høiland-Jørgensen <toke@redhat.com>

The subsequent patch to add a new devmap sub-type can re-use much of the
initialisation and allocation code, so refactor it into separate functions.

Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 kernel/bpf/devmap.c |  137 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 84 insertions(+), 53 deletions(-)

diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
index d83cf8ccc872..a2fe16362129 100644
--- a/kernel/bpf/devmap.c
+++ b/kernel/bpf/devmap.c
@@ -60,7 +60,7 @@ struct xdp_bulk_queue {
 struct bpf_dtab_netdev {
 	struct net_device *dev; /* must be first member, due to tracepoint */
 	struct bpf_dtab *dtab;
-	unsigned int bit;
+	unsigned int idx; /* keep track of map index for tracepoint */
 	struct xdp_bulk_queue __percpu *bulkq;
 	struct rcu_head rcu;
 };
@@ -75,28 +75,22 @@ struct bpf_dtab {
 static DEFINE_SPINLOCK(dev_map_lock);
 static LIST_HEAD(dev_map_list);
 
-static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
+static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
+			    bool check_memlock)
 {
-	struct bpf_dtab *dtab;
 	int err, cpu;
 	u64 cost;
 
-	if (!capable(CAP_NET_ADMIN))
-		return ERR_PTR(-EPERM);
-
 	/* check sanity of attributes */
 	if (attr->max_entries == 0 || attr->key_size != 4 ||
 	    attr->value_size != 4 || attr->map_flags & ~DEV_CREATE_FLAG_MASK)
-		return ERR_PTR(-EINVAL);
+		return -EINVAL;
 
 	/* Lookup returns a pointer straight to dev->ifindex, so make sure the
 	 * verifier prevents writes from the BPF side
 	 */
 	attr->map_flags |= BPF_F_RDONLY_PROG;
 
-	dtab = kzalloc(sizeof(*dtab), GFP_USER);
-	if (!dtab)
-		return ERR_PTR(-ENOMEM);
 
 	bpf_map_init_from_attr(&dtab->map, attr);
 
@@ -107,9 +101,7 @@ static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
 	/* if map size is larger than memlock limit, reject it */
 	err = bpf_map_charge_init(&dtab->map.memory, cost);
 	if (err)
-		goto free_dtab;
-
-	err = -ENOMEM;
+		return -EINVAL;
 
 	dtab->flush_list = alloc_percpu(struct list_head);
 	if (!dtab->flush_list)
@@ -124,19 +116,38 @@ static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
 	if (!dtab->netdev_map)
 		goto free_percpu;
 
-	spin_lock(&dev_map_lock);
-	list_add_tail_rcu(&dtab->list, &dev_map_list);
-	spin_unlock(&dev_map_lock);
-
-	return &dtab->map;
+	return 0;
 
 free_percpu:
 	free_percpu(dtab->flush_list);
 free_charge:
 	bpf_map_charge_finish(&dtab->map.memory);
-free_dtab:
-	kfree(dtab);
-	return ERR_PTR(err);
+	return -ENOMEM;
+}
+
+static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
+{
+	struct bpf_dtab *dtab;
+	int err;
+
+	if (!capable(CAP_NET_ADMIN))
+		return ERR_PTR(-EPERM);
+
+	dtab = kzalloc(sizeof(*dtab), GFP_USER);
+	if (!dtab)
+		return ERR_PTR(-ENOMEM);
+
+	err = dev_map_init_map(dtab, attr, true);
+	if (err) {
+		kfree(dtab);
+		return ERR_PTR(err);
+	}
+
+	spin_lock(&dev_map_lock);
+	list_add_tail_rcu(&dtab->list, &dev_map_list);
+	spin_unlock(&dev_map_lock);
+
+	return &dtab->map;
 }
 
 static void dev_map_free(struct bpf_map *map)
@@ -235,7 +246,7 @@ static int bq_xmit_all(struct xdp_bulk_queue *bq, u32 flags,
 out:
 	bq->count = 0;
 
-	trace_xdp_devmap_xmit(&obj->dtab->map, obj->bit,
+	trace_xdp_devmap_xmit(&obj->dtab->map, obj->idx,
 			      sent, drops, bq->dev_rx, dev, err);
 	bq->dev_rx = NULL;
 	__list_del_clearprev(&bq->flush_node);
@@ -412,17 +423,52 @@ static int dev_map_delete_elem(struct bpf_map *map, void *key)
 	return 0;
 }
 
-static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
-				u64 map_flags)
+static struct bpf_dtab_netdev *__dev_map_alloc_node(struct net *net,
+						    struct bpf_dtab *dtab,
+						    u32 ifindex,
+						    unsigned int idx)
 {
-	struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
-	struct net *net = current->nsproxy->net_ns;
 	gfp_t gfp = GFP_ATOMIC | __GFP_NOWARN;
+	struct bpf_dtab_netdev *dev;
+	struct xdp_bulk_queue *bq;
+	int cpu;
+
+	dev = kmalloc_node(sizeof(*dev), gfp, dtab->map.numa_node);
+	if (!dev)
+		return ERR_PTR(-ENOMEM);
+
+	dev->bulkq = __alloc_percpu_gfp(sizeof(*dev->bulkq),
+					sizeof(void *), gfp);
+	if (!dev->bulkq) {
+		kfree(dev);
+		return ERR_PTR(-ENOMEM);
+	}
+
+	for_each_possible_cpu(cpu) {
+		bq = per_cpu_ptr(dev->bulkq, cpu);
+		bq->obj = dev;
+	}
+
+	dev->dev = dev_get_by_index(net, ifindex);
+	if (!dev->dev) {
+		free_percpu(dev->bulkq);
+		kfree(dev);
+		return ERR_PTR(-EINVAL);
+	}
+
+	dev->idx = idx;
+	dev->dtab = dtab;
+
+	return dev;
+}
+
+static int __dev_map_update_elem(struct net *net, struct bpf_map *map,
+				 void *key, void *value, u64 map_flags)
+{
+	struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
 	struct bpf_dtab_netdev *dev, *old_dev;
 	u32 ifindex = *(u32 *)value;
-	struct xdp_bulk_queue *bq;
 	u32 i = *(u32 *)key;
-	int cpu;
 
 	if (unlikely(map_flags > BPF_EXIST))
 		return -EINVAL;
@@ -434,31 +480,9 @@ static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
 	if (!ifindex) {
 		dev = NULL;
 	} else {
-		dev = kmalloc_node(sizeof(*dev), gfp, map->numa_node);
-		if (!dev)
-			return -ENOMEM;
-
-		dev->bulkq = __alloc_percpu_gfp(sizeof(*dev->bulkq),
-						sizeof(void *), gfp);
-		if (!dev->bulkq) {
-			kfree(dev);
-			return -ENOMEM;
-		}
-
-		for_each_possible_cpu(cpu) {
-			bq = per_cpu_ptr(dev->bulkq, cpu);
-			bq->obj = dev;
-		}
-
-		dev->dev = dev_get_by_index(net, ifindex);
-		if (!dev->dev) {
-			free_percpu(dev->bulkq);
-			kfree(dev);
-			return -EINVAL;
-		}
-
-		dev->bit = i;
-		dev->dtab = dtab;
+		dev = __dev_map_alloc_node(net, dtab, ifindex, i);
+		if (IS_ERR(dev))
+			return PTR_ERR(dev);
 	}
 
 	/* Use call_rcu() here to ensure rcu critical sections have completed
@@ -472,6 +496,13 @@ static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
 	return 0;
 }
 
+static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
+			       u64 map_flags)
+{
+	return __dev_map_update_elem(current->nsproxy->net_ns,
+				     map, key, value, map_flags);
+}
+
 const struct bpf_map_ops dev_map_ops = {
 	.map_alloc = dev_map_alloc,
 	.map_free = dev_map_free,

[PATCH bpf-next v2 0/6] xdp: Add devmap_hash map type

[Toke Høiland-Jørgensen]

This series adds a new map type, devmap_hash, that works like the existing
devmap type, but using a hash-based indexing scheme. This is useful for the use
case where a devmap is indexed by ifindex (for instance for use with the routing
table lookup helper). For this use case, the regular devmap needs to be sized
after the maximum ifindex number, not the number of devices in it. A hash-based
indexing scheme makes it possible to size the map after the number of devices it
should contain instead.

This was previously part of my patch series that also turned the regular
bpf_redirect() helper into a map-based one; for this series I just pulled out
the patches that introduced the new map type.

Changelog:

v2:

- Split commit adding the new map type so uapi and tools changes are separate.

Changes to these patches since the previous series:

- Rebase on top of the other devmap changes (makes this one simpler!)
- Don't enforce key==val, but allow arbitrary indexes.
- Rename the type to devmap_hash to reflect the fact that it's just a hashmap now.

---

Toke Høiland-Jørgensen (6):
      include/bpf.h: Remove map_insert_ctx() stubs
      xdp: Refactor devmap allocation code for reuse
      uapi/bpf: Add new devmap_hash type
      xdp: Add devmap_hash map type for looking up devices by hashed index
      tools/libbpf_probes: Add new devmap_hash type
      tools: Add definitions for devmap_hash map type


 include/linux/bpf.h                     |   11 -
 include/linux/bpf_types.h               |    1 
 include/trace/events/xdp.h              |    3 
 include/uapi/linux/bpf.h                |    1 
 kernel/bpf/devmap.c                     |  325 ++++++++++++++++++++++++++-----
 kernel/bpf/verifier.c                   |    2 
 net/core/filter.c                       |    9 +
 tools/bpf/bpftool/map.c                 |    1 
 tools/include/uapi/linux/bpf.h          |    1 
 tools/lib/bpf/libbpf_probes.c           |    1 
 tools/testing/selftests/bpf/test_maps.c |   16 ++
 11 files changed, 310 insertions(+), 61 deletions(-)

[PATCH bpf-next v2 5/6] tools/libbpf_probes: Add new devmap_hash type

[Toke Høiland-Jørgensen]

From: Toke Høiland-Jørgensen <toke@redhat.com>

This adds the definition for BPF_MAP_TYPE_DEVMAP_HASH to libbpf_probes.c in
tools/lib/bpf.

Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 tools/lib/bpf/libbpf_probes.c |    1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/lib/bpf/libbpf_probes.c b/tools/lib/bpf/libbpf_probes.c
index ace1a0708d99..4b0b0364f5fc 100644
--- a/tools/lib/bpf/libbpf_probes.c
+++ b/tools/lib/bpf/libbpf_probes.c
@@ -244,6 +244,7 @@ bool bpf_probe_map_type(enum bpf_map_type map_type, __u32 ifindex)
 	case BPF_MAP_TYPE_ARRAY_OF_MAPS:
 	case BPF_MAP_TYPE_HASH_OF_MAPS:
 	case BPF_MAP_TYPE_DEVMAP:
+	case BPF_MAP_TYPE_DEVMAP_HASH:
 	case BPF_MAP_TYPE_SOCKMAP:
 	case BPF_MAP_TYPE_CPUMAP:
 	case BPF_MAP_TYPE_XSKMAP:

[PATCH bpf-next v2 6/6] tools: Add definitions for devmap_hash map type

[Toke Høiland-Jørgensen]

From: Toke Høiland-Jørgensen <toke@redhat.com>

This adds a selftest, syncs the tools/ uapi header and adds the
devmap_hash name to bpftool for the new devmap_hash map type.

Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 tools/bpf/bpftool/map.c                 |    1 +
 tools/include/uapi/linux/bpf.h          |    1 +
 tools/testing/selftests/bpf/test_maps.c |   16 ++++++++++++++++
 3 files changed, 18 insertions(+)

diff --git a/tools/bpf/bpftool/map.c b/tools/bpf/bpftool/map.c
index 5da5a7311f13..c345f819b840 100644
--- a/tools/bpf/bpftool/map.c
+++ b/tools/bpf/bpftool/map.c
@@ -37,6 +37,7 @@ const char * const map_type_name[] = {
 	[BPF_MAP_TYPE_ARRAY_OF_MAPS]		= "array_of_maps",
 	[BPF_MAP_TYPE_HASH_OF_MAPS]		= "hash_of_maps",
 	[BPF_MAP_TYPE_DEVMAP]			= "devmap",
+	[BPF_MAP_TYPE_DEVMAP_HASH]		= "devmap_hash",
 	[BPF_MAP_TYPE_SOCKMAP]			= "sockmap",
 	[BPF_MAP_TYPE_CPUMAP]			= "cpumap",
 	[BPF_MAP_TYPE_XSKMAP]			= "xskmap",
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index cecf42c871d4..8afaa0a19c67 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -134,6 +134,7 @@ enum bpf_map_type {
 	BPF_MAP_TYPE_QUEUE,
 	BPF_MAP_TYPE_STACK,
 	BPF_MAP_TYPE_SK_STORAGE,
+	BPF_MAP_TYPE_DEVMAP_HASH,
 };
 
 /* Note that tracing related programs such as
diff --git a/tools/testing/selftests/bpf/test_maps.c b/tools/testing/selftests/bpf/test_maps.c
index a3fbc571280a..086319caf2d9 100644
--- a/tools/testing/selftests/bpf/test_maps.c
+++ b/tools/testing/selftests/bpf/test_maps.c
@@ -508,6 +508,21 @@ static void test_devmap(unsigned int task, void *data)
 	close(fd);
 }
 
+static void test_devmap_hash(unsigned int task, void *data)
+{
+	int fd;
+	__u32 key, value;
+
+	fd = bpf_create_map(BPF_MAP_TYPE_DEVMAP_HASH, sizeof(key), sizeof(value),
+			    2, 0);
+	if (fd < 0) {
+		printf("Failed to create devmap_hash '%s'!\n", strerror(errno));
+		exit(1);
+	}
+
+	close(fd);
+}
+
 static void test_queuemap(unsigned int task, void *data)
 {
 	const int MAP_SIZE = 32;
@@ -1675,6 +1690,7 @@ static void run_all_tests(void)
 	test_arraymap_percpu_many_keys();
 
 	test_devmap(0, NULL);
+	test_devmap_hash(0, NULL);
 	test_sockmap(0, NULL);
 
 	test_map_large();

[PATCH bpf-next v2 4/6] xdp: Add devmap_hash map type for looking up devices by hashed index

[Toke Høiland-Jørgensen]

From: Toke Høiland-Jørgensen <toke@redhat.com>

A common pattern when using xdp_redirect_map() is to create a device map
where the lookup key is simply ifindex. Because device maps are arrays,
this leaves holes in the map, and the map has to be sized to fit the
largest ifindex, regardless of how many devices actually are actually
needed in the map.

This patch adds a second type of device map where the key is looked up
using a hashmap, instead of being used as an array index. This allows maps
to be densely packed, so they can be smaller.

Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
---
 include/linux/bpf.h        |    7 ++
 include/linux/bpf_types.h  |    1 
 include/trace/events/xdp.h |    3 -
 kernel/bpf/devmap.c        |  192 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c      |    2 
 net/core/filter.c          |    9 ++
 6 files changed, 211 insertions(+), 3 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index bfdb54dd2ad1..f9a506147c8a 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -713,6 +713,7 @@ struct xdp_buff;
 struct sk_buff;
 
 struct bpf_dtab_netdev *__dev_map_lookup_elem(struct bpf_map *map, u32 key);
+struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key);
 void __dev_map_flush(struct bpf_map *map);
 int dev_map_enqueue(struct bpf_dtab_netdev *dst, struct xdp_buff *xdp,
 		    struct net_device *dev_rx);
@@ -799,6 +800,12 @@ static inline struct net_device  *__dev_map_lookup_elem(struct bpf_map *map,
 	return NULL;
 }
 
+static inline struct net_device  *__dev_map_hash_lookup_elem(struct bpf_map *map,
+							     u32 key)
+{
+	return NULL;
+}
+
 static inline void __dev_map_flush(struct bpf_map *map)
 {
 }
diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h
index eec5aeeeaf92..36a9c2325176 100644
--- a/include/linux/bpf_types.h
+++ b/include/linux/bpf_types.h
@@ -62,6 +62,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_ARRAY_OF_MAPS, array_of_maps_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_HASH_OF_MAPS, htab_of_maps_map_ops)
 #ifdef CONFIG_NET
 BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP, dev_map_ops)
+BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP_HASH, dev_map_hash_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_SK_STORAGE, sk_storage_map_ops)
 #if defined(CONFIG_BPF_STREAM_PARSER)
 BPF_MAP_TYPE(BPF_MAP_TYPE_SOCKMAP, sock_map_ops)
diff --git a/include/trace/events/xdp.h b/include/trace/events/xdp.h
index 68899fdc985b..8c8420230a10 100644
--- a/include/trace/events/xdp.h
+++ b/include/trace/events/xdp.h
@@ -175,7 +175,8 @@ struct _bpf_dtab_netdev {
 #endif /* __DEVMAP_OBJ_TYPE */
 
 #define devmap_ifindex(fwd, map)				\
-	((map->map_type == BPF_MAP_TYPE_DEVMAP) ?		\
+	((map->map_type == BPF_MAP_TYPE_DEVMAP ||		\
+	  map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) ?		\
 	  ((struct _bpf_dtab_netdev *)fwd)->dev->ifindex : 0)
 
 #define _trace_xdp_redirect_map(dev, xdp, fwd, map, idx)		\
diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
index a2fe16362129..341af02f049d 100644
--- a/kernel/bpf/devmap.c
+++ b/kernel/bpf/devmap.c
@@ -37,6 +37,12 @@
  * notifier hook walks the map we know that new dev references can not be
  * added by the user because core infrastructure ensures dev_get_by_index()
  * calls will fail at this point.
+ *
+ * The devmap_hash type is a map type which interprets keys as ifindexes and
+ * indexes these using a hashmap. This allows maps that use ifindex as key to be
+ * densely packed instead of having holes in the lookup array for unused
+ * ifindexes. The setup and packet enqueue/send code is shared between the two
+ * types of devmap; only the lookup and insertion is different.
  */
 #include <linux/bpf.h>
 #include <net/xdp.h>
@@ -59,6 +65,7 @@ struct xdp_bulk_queue {
 
 struct bpf_dtab_netdev {
 	struct net_device *dev; /* must be first member, due to tracepoint */
+	struct hlist_node index_hlist;
 	struct bpf_dtab *dtab;
 	unsigned int idx; /* keep track of map index for tracepoint */
 	struct xdp_bulk_queue __percpu *bulkq;
@@ -70,11 +77,29 @@ struct bpf_dtab {
 	struct bpf_dtab_netdev **netdev_map;
 	struct list_head __percpu *flush_list;
 	struct list_head list;
+
+	/* these are only used for DEVMAP_HASH type maps */
+	unsigned int items;
+	struct hlist_head *dev_index_head;
+	spinlock_t index_lock;
 };
 
 static DEFINE_SPINLOCK(dev_map_lock);
 static LIST_HEAD(dev_map_list);
 
+static struct hlist_head *dev_map_create_hash(void)
+{
+	int i;
+	struct hlist_head *hash;
+
+	hash = kmalloc_array(NETDEV_HASHENTRIES, sizeof(*hash), GFP_KERNEL);
+	if (hash != NULL)
+		for (i = 0; i < NETDEV_HASHENTRIES; i++)
+			INIT_HLIST_HEAD(&hash[i]);
+
+	return hash;
+}
+
 static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
 			    bool check_memlock)
 {
@@ -98,6 +123,9 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
 	cost = (u64) dtab->map.max_entries * sizeof(struct bpf_dtab_netdev *);
 	cost += sizeof(struct list_head) * num_possible_cpus();
 
+	if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH)
+		cost += sizeof(struct hlist_head) * NETDEV_HASHENTRIES;
+
 	/* if map size is larger than memlock limit, reject it */
 	err = bpf_map_charge_init(&dtab->map.memory, cost);
 	if (err)
@@ -116,8 +144,18 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
 	if (!dtab->netdev_map)
 		goto free_percpu;
 
+	if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
+		dtab->dev_index_head = dev_map_create_hash();
+		if (!dtab->dev_index_head)
+			goto free_map_area;
+
+		spin_lock_init(&dtab->index_lock);
+	}
+
 	return 0;
 
+free_map_area:
+	bpf_map_area_free(dtab->netdev_map);
 free_percpu:
 	free_percpu(dtab->flush_list);
 free_charge:
@@ -199,6 +237,7 @@ static void dev_map_free(struct bpf_map *map)
 
 	free_percpu(dtab->flush_list);
 	bpf_map_area_free(dtab->netdev_map);
+	kfree(dtab->dev_index_head);
 	kfree(dtab);
 }
 
@@ -219,6 +258,70 @@ static int dev_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 	return 0;
 }
 
+static inline struct hlist_head *dev_map_index_hash(struct bpf_dtab *dtab,
+						    int idx)
+{
+	return &dtab->dev_index_head[idx & (NETDEV_HASHENTRIES - 1)];
+}
+
+struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key)
+{
+	struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
+	struct hlist_head *head = dev_map_index_hash(dtab, key);
+	struct bpf_dtab_netdev *dev;
+
+	hlist_for_each_entry_rcu(dev, head, index_hlist)
+		if (dev->idx == key)
+			return dev;
+
+	return NULL;
+}
+
+static int dev_map_hash_get_next_key(struct bpf_map *map, void *key,
+				    void *next_key)
+{
+	struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
+	u32 idx, *next = next_key;
+	struct bpf_dtab_netdev *dev, *next_dev;
+	struct hlist_head *head;
+	int i = 0;
+
+	if (!key)
+		goto find_first;
+
+	idx = *(u32 *)key;
+
+	dev = __dev_map_hash_lookup_elem(map, idx);
+	if (!dev)
+		goto find_first;
+
+	next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(&dev->index_hlist)),
+				    struct bpf_dtab_netdev, index_hlist);
+
+	if (next_dev) {
+		*next = next_dev->idx;
+		return 0;
+	}
+
+	i = idx & (NETDEV_HASHENTRIES - 1);
+	i++;
+
+ find_first:
+	for (; i < NETDEV_HASHENTRIES; i++) {
+		head = dev_map_index_hash(dtab, i);
+
+		next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),
+					    struct bpf_dtab_netdev,
+					    index_hlist);
+		if (next_dev) {
+			*next = next_dev->idx;
+			return 0;
+		}
+	}
+
+	return -ENOENT;
+}
+
 static int bq_xmit_all(struct xdp_bulk_queue *bq, u32 flags,
 		       bool in_napi_ctx)
 {
@@ -374,6 +477,15 @@ static void *dev_map_lookup_elem(struct bpf_map *map, void *key)
 	return dev ? &dev->ifindex : NULL;
 }
 
+static void *dev_map_hash_lookup_elem(struct bpf_map *map, void *key)
+{
+	struct bpf_dtab_netdev *obj = __dev_map_hash_lookup_elem(map,
+								*(u32 *)key);
+	struct net_device *dev = obj ? obj->dev : NULL;
+
+	return dev ? &dev->ifindex : NULL;
+}
+
 static void dev_map_flush_old(struct bpf_dtab_netdev *dev)
 {
 	if (dev->dev->netdev_ops->ndo_xdp_xmit) {
@@ -423,6 +535,27 @@ static int dev_map_delete_elem(struct bpf_map *map, void *key)
 	return 0;
 }
 
+static int dev_map_hash_delete_elem(struct bpf_map *map, void *key)
+{
+	struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
+	struct bpf_dtab_netdev *old_dev;
+	int k = *(u32 *)key;
+
+	old_dev = __dev_map_hash_lookup_elem(map, k);
+	if (!old_dev)
+		return 0;
+
+	spin_lock(&dtab->index_lock);
+	if (!hlist_unhashed(&old_dev->index_hlist)) {
+		dtab->items--;
+		hlist_del_init_rcu(&old_dev->index_hlist);
+	}
+	spin_unlock(&dtab->index_lock);
+
+	call_rcu(&old_dev->rcu, __dev_map_entry_free);
+	return 0;
+}
+
 static struct bpf_dtab_netdev *__dev_map_alloc_node(struct net *net,
 						    struct bpf_dtab *dtab,
 						    u32 ifindex,
@@ -503,6 +636,55 @@ static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
 				     map, key, value, map_flags);
 }
 
+static int __dev_map_hash_update_elem(struct net *net, struct bpf_map *map,
+				     void *key, void *value, u64 map_flags)
+{
+	struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
+	struct bpf_dtab_netdev *dev, *old_dev;
+	u32 ifindex = *(u32 *)value;
+	u32 idx = *(u32 *)key;
+
+	if (unlikely(map_flags > BPF_EXIST || !ifindex))
+		return -EINVAL;
+
+	old_dev = __dev_map_hash_lookup_elem(map, idx);
+	if (old_dev && (map_flags & BPF_NOEXIST))
+		return -EEXIST;
+
+	dev = __dev_map_alloc_node(net, dtab, ifindex, idx);
+	if (IS_ERR(dev))
+		return PTR_ERR(dev);
+
+	spin_lock(&dtab->index_lock);
+
+	if (old_dev) {
+		hlist_del_rcu(&old_dev->index_hlist);
+	} else {
+		if (dtab->items >= dtab->map.max_entries) {
+			spin_unlock(&dtab->index_lock);
+			call_rcu(&dev->rcu, __dev_map_entry_free);
+			return -ENOSPC;
+		}
+		dtab->items++;
+	}
+
+	hlist_add_head_rcu(&dev->index_hlist,
+			   dev_map_index_hash(dtab, idx));
+	spin_unlock(&dtab->index_lock);
+
+	if (old_dev)
+		call_rcu(&old_dev->rcu, __dev_map_entry_free);
+
+	return 0;
+}
+
+static int dev_map_hash_update_elem(struct bpf_map *map, void *key, void *value,
+				   u64 map_flags)
+{
+	return __dev_map_hash_update_elem(current->nsproxy->net_ns,
+					 map, key, value, map_flags);
+}
+
 const struct bpf_map_ops dev_map_ops = {
 	.map_alloc = dev_map_alloc,
 	.map_free = dev_map_free,
@@ -513,6 +695,16 @@ const struct bpf_map_ops dev_map_ops = {
 	.map_check_btf = map_check_no_btf,
 };
 
+const struct bpf_map_ops dev_map_hash_ops = {
+	.map_alloc = dev_map_alloc,
+	.map_free = dev_map_free,
+	.map_get_next_key = dev_map_hash_get_next_key,
+	.map_lookup_elem = dev_map_hash_lookup_elem,
+	.map_update_elem = dev_map_hash_update_elem,
+	.map_delete_elem = dev_map_hash_delete_elem,
+	.map_check_btf = map_check_no_btf,
+};
+
 static int dev_map_notification(struct notifier_block *notifier,
 				ulong event, void *ptr)
 {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a2e763703c30..231b9e22827c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3460,6 +3460,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
 			goto error;
 		break;
 	case BPF_MAP_TYPE_DEVMAP:
+	case BPF_MAP_TYPE_DEVMAP_HASH:
 		if (func_id != BPF_FUNC_redirect_map &&
 		    func_id != BPF_FUNC_map_lookup_elem)
 			goto error;
@@ -3542,6 +3543,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
 		break;
 	case BPF_FUNC_redirect_map:
 		if (map->map_type != BPF_MAP_TYPE_DEVMAP &&
+		    map->map_type != BPF_MAP_TYPE_DEVMAP_HASH &&
 		    map->map_type != BPF_MAP_TYPE_CPUMAP &&
 		    map->map_type != BPF_MAP_TYPE_XSKMAP)
 			goto error;
diff --git a/net/core/filter.c b/net/core/filter.c
index 089aaea0ccc6..276961c4e0d4 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -3517,7 +3517,8 @@ static int __bpf_tx_xdp_map(struct net_device *dev_rx, void *fwd,
 	int err;
 
 	switch (map->map_type) {
-	case BPF_MAP_TYPE_DEVMAP: {
+	case BPF_MAP_TYPE_DEVMAP:
+	case BPF_MAP_TYPE_DEVMAP_HASH: {
 		struct bpf_dtab_netdev *dst = fwd;
 
 		err = dev_map_enqueue(dst, xdp, dev_rx);
@@ -3554,6 +3555,7 @@ void xdp_do_flush_map(void)
 	if (map) {
 		switch (map->map_type) {
 		case BPF_MAP_TYPE_DEVMAP:
+		case BPF_MAP_TYPE_DEVMAP_HASH:
 			__dev_map_flush(map);
 			break;
 		case BPF_MAP_TYPE_CPUMAP:
@@ -3574,6 +3576,8 @@ static inline void *__xdp_map_lookup_elem(struct bpf_map *map, u32 index)
 	switch (map->map_type) {
 	case BPF_MAP_TYPE_DEVMAP:
 		return __dev_map_lookup_elem(map, index);
+	case BPF_MAP_TYPE_DEVMAP_HASH:
+		return __dev_map_hash_lookup_elem(map, index);
 	case BPF_MAP_TYPE_CPUMAP:
 		return __cpu_map_lookup_elem(map, index);
 	case BPF_MAP_TYPE_XSKMAP:
@@ -3655,7 +3659,8 @@ static int xdp_do_generic_redirect_map(struct net_device *dev,
 	ri->tgt_value = NULL;
 	WRITE_ONCE(ri->map, NULL);
 
-	if (map->map_type == BPF_MAP_TYPE_DEVMAP) {
+	if (map->map_type == BPF_MAP_TYPE_DEVMAP ||
+	    map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
 		struct bpf_dtab_netdev *dst = fwd;
 
 		err = dev_map_generic_redirect(dst, skb, xdp_prog);

Re: [PATCH bpf-next v2 0/6] xdp: Add devmap_hash map type

[Y Song]

On Sat, Jul 6, 2019 at 1:47 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> This series adds a new map type, devmap_hash, that works like the existing
> devmap type, but using a hash-based indexing scheme. This is useful for the use
> case where a devmap is indexed by ifindex (for instance for use with the routing
> table lookup helper). For this use case, the regular devmap needs to be sized
> after the maximum ifindex number, not the number of devices in it. A hash-based
> indexing scheme makes it possible to size the map after the number of devices it
> should contain instead.
>
> This was previously part of my patch series that also turned the regular
> bpf_redirect() helper into a map-based one; for this series I just pulled out
> the patches that introduced the new map type.
>
> Changelog:
>
> v2:
>
> - Split commit adding the new map type so uapi and tools changes are separate.
>
> Changes to these patches since the previous series:
>
> - Rebase on top of the other devmap changes (makes this one simpler!)
> - Don't enforce key==val, but allow arbitrary indexes.
> - Rename the type to devmap_hash to reflect the fact that it's just a hashmap now.
>
> ---
>
> Toke Høiland-Jørgensen (6):
>       include/bpf.h: Remove map_insert_ctx() stubs
>       xdp: Refactor devmap allocation code for reuse
>       uapi/bpf: Add new devmap_hash type
>       xdp: Add devmap_hash map type for looking up devices by hashed index
>       tools/libbpf_probes: Add new devmap_hash type
>       tools: Add definitions for devmap_hash map type

Thanks for re-organize the patch. I guess this can be tweaked a little more
to better suit for syncing between kernel and libbpf repo.

Let me provide a little bit background here. The below is
a sync done by Andrii from kernel/tools to libbpf repo.

=============
commit 39de6711795f6d1583ae96ed8d13892bc4475ac1
Author: Andrii Nakryiko <andriin@fb.com>
Date:   Tue Jun 11 09:56:11 2019 -0700

    sync: latest libbpf changes from kernel

    Syncing latest libbpf commits from kernel repository.
    Baseline commit:   e672db03ab0e43e41ab6f8b2156a10d6e40f243d
    Checkpoint commit: 5e2ac390fbd08b2a462db66cef2663e4db0d5191

    Andrii Nakryiko (9):
      libbpf: fix detection of corrupted BPF instructions section
      libbpf: preserve errno before calling into user callback
      libbpf: simplify endianness check
      libbpf: check map name retrieved from ELF
      libbpf: fix error code returned on corrupted ELF
      libbpf: use negative fd to specify missing BTF
      libbpf: simplify two pieces of logic
      libbpf: typo and formatting fixes
      libbpf: reduce unnecessary line wrapping

    Hechao Li (1):
      bpf: add a new API libbpf_num_possible_cpus()

    Jonathan Lemon (2):
      bpf/tools: sync bpf.h
      libbpf: remove qidconf and better support external bpf programs.

    Quentin Monnet (1):
      libbpf: prevent overwriting of log_level in bpf_object__load_progs()

     include/uapi/linux/bpf.h |   4 +
     src/libbpf.c             | 207 ++++++++++++++++++++++-----------------
     src/libbpf.h             |  16 +++
     src/libbpf.map           |   1 +
     src/xsk.c                | 103 ++++++-------------
     5 files changed, 167 insertions(+), 164 deletions(-)
==========

You can see the commits at tools/lib/bpf and
commits at tools/include/uapi/{linux/[bpf.h, btf.h], ...}
are sync'ed to libbpf repo.

So we would like kernel commits to be aligned that way for better
automatic syncing.

Therefore, your current patch set could be changed from
   >       include/bpf.h: Remove map_insert_ctx() stubs
   >       xdp: Refactor devmap allocation code for reuse
   >       uapi/bpf: Add new devmap_hash type
   >       xdp: Add devmap_hash map type for looking up devices by hashed index
   >       tools/libbpf_probes: Add new devmap_hash type
   >       tools: Add definitions for devmap_hash map type
to
      1. include/bpf.h: Remove map_insert_ctx() stubs
      2. xdp: Refactor devmap allocation code for reuse
      3. kernel non-tools changes (the above patch #3 and #4)
      4. tools/include/uapi change (part of the above patch #6)
      5. tools/libbpf_probes change
      6. other tools/ change (the above patch #6 - new patch #4).

Thanks!

Yonghong

>
>
>  include/linux/bpf.h                     |   11 -
>  include/linux/bpf_types.h               |    1
>  include/trace/events/xdp.h              |    3
>  include/uapi/linux/bpf.h                |    1
>  kernel/bpf/devmap.c                     |  325 ++++++++++++++++++++++++++-----
>  kernel/bpf/verifier.c                   |    2
>  net/core/filter.c                       |    9 +
>  tools/bpf/bpftool/map.c                 |    1
>  tools/include/uapi/linux/bpf.h          |    1
>  tools/lib/bpf/libbpf_probes.c           |    1
>  tools/testing/selftests/bpf/test_maps.c |   16 ++
>  11 files changed, 310 insertions(+), 61 deletions(-)
>

Re: [PATCH bpf-next v2 1/6] include/bpf.h: Remove map_insert_ctx() stubs

[Y Song]

On Sat, Jul 6, 2019 at 1:47 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> From: Toke Høiland-Jørgensen <toke@redhat.com>
>
> When we changed the device and CPU maps to use linked lists instead of
> bitmaps, we also removed the need for the map_insert_ctx() helpers to keep
> track of the bitmaps inside each map. However, it seems I forgot to remove
> the function definitions stubs, so remove those here.
>
> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>

Acked-by: Yonghong Song <yhs@fb.com>

Re: [PATCH bpf-next v2 2/6] xdp: Refactor devmap allocation code for reuse

[Y Song]

On Sat, Jul 6, 2019 at 1:47 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> From: Toke Høiland-Jørgensen <toke@redhat.com>
>
> The subsequent patch to add a new devmap sub-type can re-use much of the
> initialisation and allocation code, so refactor it into separate functions.
>
> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>

Acked-by: Yonghong Song <yhs@fb.com>

> ---
>  kernel/bpf/devmap.c |  137 +++++++++++++++++++++++++++++++--------------------
>  1 file changed, 84 insertions(+), 53 deletions(-)
>
> diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
> index d83cf8ccc872..a2fe16362129 100644
> --- a/kernel/bpf/devmap.c
> +++ b/kernel/bpf/devmap.c
> @@ -60,7 +60,7 @@ struct xdp_bulk_queue {
>  struct bpf_dtab_netdev {
>         struct net_device *dev; /* must be first member, due to tracepoint */
>         struct bpf_dtab *dtab;
> -       unsigned int bit;
> +       unsigned int idx; /* keep track of map index for tracepoint */
>         struct xdp_bulk_queue __percpu *bulkq;
>         struct rcu_head rcu;
>  };
> @@ -75,28 +75,22 @@ struct bpf_dtab {
>  static DEFINE_SPINLOCK(dev_map_lock);
>  static LIST_HEAD(dev_map_list);
>
> -static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
> +static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
> +                           bool check_memlock)
>  {
> -       struct bpf_dtab *dtab;
>         int err, cpu;
>         u64 cost;
>
> -       if (!capable(CAP_NET_ADMIN))
> -               return ERR_PTR(-EPERM);
> -
>         /* check sanity of attributes */
>         if (attr->max_entries == 0 || attr->key_size != 4 ||
>             attr->value_size != 4 || attr->map_flags & ~DEV_CREATE_FLAG_MASK)
> -               return ERR_PTR(-EINVAL);
> +               return -EINVAL;
>
>         /* Lookup returns a pointer straight to dev->ifindex, so make sure the
>          * verifier prevents writes from the BPF side
>          */
>         attr->map_flags |= BPF_F_RDONLY_PROG;
>
> -       dtab = kzalloc(sizeof(*dtab), GFP_USER);
> -       if (!dtab)
> -               return ERR_PTR(-ENOMEM);
>
>         bpf_map_init_from_attr(&dtab->map, attr);
>
> @@ -107,9 +101,7 @@ static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
>         /* if map size is larger than memlock limit, reject it */
>         err = bpf_map_charge_init(&dtab->map.memory, cost);
>         if (err)
> -               goto free_dtab;
> -
> -       err = -ENOMEM;
> +               return -EINVAL;
>
>         dtab->flush_list = alloc_percpu(struct list_head);
>         if (!dtab->flush_list)
> @@ -124,19 +116,38 @@ static struct bpf_map *dev_map_alloc(union bpf_attr *attr)
>         if (!dtab->netdev_map)
>                 goto free_percpu;
>
> -       spin_lock(&dev_map_lock);
> -       list_add_tail_rcu(&dtab->list, &dev_map_list);
> -       spin_unlock(&dev_map_lock);
> -
> -       return &dtab->map;
> +       return 0;
>
>  free_percpu:
>         free_percpu(dtab->flush_list);
>  free_charge:
>         bpf_map_charge_finish(&dtab->map.memory);
> -free_dtab:
> -       kfree(dtab);
> -       return ERR_PTR(err);
> +       return -ENOMEM;
> +}
> +
[...]

Re: [PATCH bpf-next v2 4/6] xdp: Add devmap_hash map type for looking up devices by hashed index

[Y Song]

On Sat, Jul 6, 2019 at 1:48 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> From: Toke Høiland-Jørgensen <toke@redhat.com>
>
> A common pattern when using xdp_redirect_map() is to create a device map
> where the lookup key is simply ifindex. Because device maps are arrays,
> this leaves holes in the map, and the map has to be sized to fit the
> largest ifindex, regardless of how many devices actually are actually
> needed in the map.
>
> This patch adds a second type of device map where the key is looked up
> using a hashmap, instead of being used as an array index. This allows maps
> to be densely packed, so they can be smaller.
>
> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
> ---
>  include/linux/bpf.h        |    7 ++
>  include/linux/bpf_types.h  |    1
>  include/trace/events/xdp.h |    3 -
>  kernel/bpf/devmap.c        |  192 ++++++++++++++++++++++++++++++++++++++++++++
>  kernel/bpf/verifier.c      |    2
>  net/core/filter.c          |    9 ++
>  6 files changed, 211 insertions(+), 3 deletions(-)
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index bfdb54dd2ad1..f9a506147c8a 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -713,6 +713,7 @@ struct xdp_buff;
>  struct sk_buff;
>
>  struct bpf_dtab_netdev *__dev_map_lookup_elem(struct bpf_map *map, u32 key);
> +struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key);
>  void __dev_map_flush(struct bpf_map *map);
>  int dev_map_enqueue(struct bpf_dtab_netdev *dst, struct xdp_buff *xdp,
>                     struct net_device *dev_rx);
> @@ -799,6 +800,12 @@ static inline struct net_device  *__dev_map_lookup_elem(struct bpf_map *map,
>         return NULL;
>  }
>
> +static inline struct net_device  *__dev_map_hash_lookup_elem(struct bpf_map *map,
> +                                                            u32 key)
> +{
> +       return NULL;
> +}
> +
>  static inline void __dev_map_flush(struct bpf_map *map)
>  {
>  }
> diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h
> index eec5aeeeaf92..36a9c2325176 100644
> --- a/include/linux/bpf_types.h
> +++ b/include/linux/bpf_types.h
> @@ -62,6 +62,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_ARRAY_OF_MAPS, array_of_maps_map_ops)
>  BPF_MAP_TYPE(BPF_MAP_TYPE_HASH_OF_MAPS, htab_of_maps_map_ops)
>  #ifdef CONFIG_NET
>  BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP, dev_map_ops)
> +BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP_HASH, dev_map_hash_ops)
>  BPF_MAP_TYPE(BPF_MAP_TYPE_SK_STORAGE, sk_storage_map_ops)
>  #if defined(CONFIG_BPF_STREAM_PARSER)
>  BPF_MAP_TYPE(BPF_MAP_TYPE_SOCKMAP, sock_map_ops)
> diff --git a/include/trace/events/xdp.h b/include/trace/events/xdp.h
> index 68899fdc985b..8c8420230a10 100644
> --- a/include/trace/events/xdp.h
> +++ b/include/trace/events/xdp.h
> @@ -175,7 +175,8 @@ struct _bpf_dtab_netdev {
>  #endif /* __DEVMAP_OBJ_TYPE */
>
>  #define devmap_ifindex(fwd, map)                               \
> -       ((map->map_type == BPF_MAP_TYPE_DEVMAP) ?               \
> +       ((map->map_type == BPF_MAP_TYPE_DEVMAP ||               \
> +         map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) ?          \
>           ((struct _bpf_dtab_netdev *)fwd)->dev->ifindex : 0)
>
>  #define _trace_xdp_redirect_map(dev, xdp, fwd, map, idx)               \
> diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
> index a2fe16362129..341af02f049d 100644
> --- a/kernel/bpf/devmap.c
> +++ b/kernel/bpf/devmap.c
> @@ -37,6 +37,12 @@
>   * notifier hook walks the map we know that new dev references can not be
>   * added by the user because core infrastructure ensures dev_get_by_index()
>   * calls will fail at this point.
> + *
> + * The devmap_hash type is a map type which interprets keys as ifindexes and
> + * indexes these using a hashmap. This allows maps that use ifindex as key to be
> + * densely packed instead of having holes in the lookup array for unused
> + * ifindexes. The setup and packet enqueue/send code is shared between the two
> + * types of devmap; only the lookup and insertion is different.
>   */
>  #include <linux/bpf.h>
>  #include <net/xdp.h>
> @@ -59,6 +65,7 @@ struct xdp_bulk_queue {
>
>  struct bpf_dtab_netdev {
>         struct net_device *dev; /* must be first member, due to tracepoint */
> +       struct hlist_node index_hlist;
>         struct bpf_dtab *dtab;
>         unsigned int idx; /* keep track of map index for tracepoint */
>         struct xdp_bulk_queue __percpu *bulkq;
> @@ -70,11 +77,29 @@ struct bpf_dtab {
>         struct bpf_dtab_netdev **netdev_map;
>         struct list_head __percpu *flush_list;
>         struct list_head list;
> +
> +       /* these are only used for DEVMAP_HASH type maps */
> +       unsigned int items;
> +       struct hlist_head *dev_index_head;
> +       spinlock_t index_lock;
>  };
>
>  static DEFINE_SPINLOCK(dev_map_lock);
>  static LIST_HEAD(dev_map_list);
>
> +static struct hlist_head *dev_map_create_hash(void)
> +{
> +       int i;
> +       struct hlist_head *hash;
> +
> +       hash = kmalloc_array(NETDEV_HASHENTRIES, sizeof(*hash), GFP_KERNEL);
> +       if (hash != NULL)
> +               for (i = 0; i < NETDEV_HASHENTRIES; i++)
> +                       INIT_HLIST_HEAD(&hash[i]);
> +
> +       return hash;
> +}
> +
>  static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
>                             bool check_memlock)
>  {
> @@ -98,6 +123,9 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
>         cost = (u64) dtab->map.max_entries * sizeof(struct bpf_dtab_netdev *);
>         cost += sizeof(struct list_head) * num_possible_cpus();
>
> +       if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH)
> +               cost += sizeof(struct hlist_head) * NETDEV_HASHENTRIES;
> +
>         /* if map size is larger than memlock limit, reject it */
>         err = bpf_map_charge_init(&dtab->map.memory, cost);
>         if (err)
> @@ -116,8 +144,18 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
>         if (!dtab->netdev_map)
>                 goto free_percpu;
>
> +       if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
> +               dtab->dev_index_head = dev_map_create_hash();
> +               if (!dtab->dev_index_head)
> +                       goto free_map_area;
> +
> +               spin_lock_init(&dtab->index_lock);
> +       }
> +
>         return 0;
>
> +free_map_area:
> +       bpf_map_area_free(dtab->netdev_map);
>  free_percpu:
>         free_percpu(dtab->flush_list);
>  free_charge:
> @@ -199,6 +237,7 @@ static void dev_map_free(struct bpf_map *map)
>
>         free_percpu(dtab->flush_list);
>         bpf_map_area_free(dtab->netdev_map);
> +       kfree(dtab->dev_index_head);
>         kfree(dtab);
>  }
>
> @@ -219,6 +258,70 @@ static int dev_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
>         return 0;
>  }
>
> +static inline struct hlist_head *dev_map_index_hash(struct bpf_dtab *dtab,
> +                                                   int idx)
> +{
> +       return &dtab->dev_index_head[idx & (NETDEV_HASHENTRIES - 1)];
> +}
> +
> +struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key)
> +{
> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
> +       struct hlist_head *head = dev_map_index_hash(dtab, key);
> +       struct bpf_dtab_netdev *dev;
> +
> +       hlist_for_each_entry_rcu(dev, head, index_hlist)
> +               if (dev->idx == key)
> +                       return dev;
> +
> +       return NULL;
> +}
> +
> +static int dev_map_hash_get_next_key(struct bpf_map *map, void *key,
> +                                   void *next_key)
> +{
> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
> +       u32 idx, *next = next_key;
> +       struct bpf_dtab_netdev *dev, *next_dev;
> +       struct hlist_head *head;
> +       int i = 0;
> +
> +       if (!key)
> +               goto find_first;
> +
> +       idx = *(u32 *)key;
> +
> +       dev = __dev_map_hash_lookup_elem(map, idx);
> +       if (!dev)
> +               goto find_first;
> +
> +       next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(&dev->index_hlist)),
> +                                   struct bpf_dtab_netdev, index_hlist);

Just want to get a better understanding. Why do you want
hlist_entry_safe instead of hlist_entry?
Also, maybe rcu_dereference instead of rcu_dereference_raw?
dev_map_hash_get_next_key() is called in syscall.c within rcu_read_lock region.

> +
> +       if (next_dev) {
> +               *next = next_dev->idx;
> +               return 0;
> +       }
> +
> +       i = idx & (NETDEV_HASHENTRIES - 1);
> +       i++;
> +
> + find_first:
> +       for (; i < NETDEV_HASHENTRIES; i++) {
> +               head = dev_map_index_hash(dtab, i);
> +
> +               next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),
> +                                           struct bpf_dtab_netdev,
> +                                           index_hlist);

ditto. The same question as the above.

> +               if (next_dev) {
> +                       *next = next_dev->idx;
> +                       return 0;
> +               }
> +       }
> +
> +       return -ENOENT;
> +}
> +
>  static int bq_xmit_all(struct xdp_bulk_queue *bq, u32 flags,
>                        bool in_napi_ctx)
>  {
> @@ -374,6 +477,15 @@ static void *dev_map_lookup_elem(struct bpf_map *map, void *key)
>         return dev ? &dev->ifindex : NULL;
>  }
>
> +static void *dev_map_hash_lookup_elem(struct bpf_map *map, void *key)
> +{
> +       struct bpf_dtab_netdev *obj = __dev_map_hash_lookup_elem(map,
> +                                                               *(u32 *)key);
> +       struct net_device *dev = obj ? obj->dev : NULL;

When obj->dev could be NULL?

> +
> +       return dev ? &dev->ifindex : NULL;
> +}
> +
>  static void dev_map_flush_old(struct bpf_dtab_netdev *dev)
>  {
>         if (dev->dev->netdev_ops->ndo_xdp_xmit) {
> @@ -423,6 +535,27 @@ static int dev_map_delete_elem(struct bpf_map *map, void *key)
>         return 0;
>  }
>
> +static int dev_map_hash_delete_elem(struct bpf_map *map, void *key)
> +{
> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
> +       struct bpf_dtab_netdev *old_dev;
> +       int k = *(u32 *)key;
> +
> +       old_dev = __dev_map_hash_lookup_elem(map, k);
> +       if (!old_dev)
> +               return 0;
> +
> +       spin_lock(&dtab->index_lock);
> +       if (!hlist_unhashed(&old_dev->index_hlist)) {
> +               dtab->items--;
> +               hlist_del_init_rcu(&old_dev->index_hlist);
> +       }
> +       spin_unlock(&dtab->index_lock);
> +
> +       call_rcu(&old_dev->rcu, __dev_map_entry_free);
> +       return 0;
> +}
> +
>  static struct bpf_dtab_netdev *__dev_map_alloc_node(struct net *net,
>                                                     struct bpf_dtab *dtab,
>                                                     u32 ifindex,
> @@ -503,6 +636,55 @@ static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
>                                      map, key, value, map_flags);
>  }
>
> +static int __dev_map_hash_update_elem(struct net *net, struct bpf_map *map,
> +                                    void *key, void *value, u64 map_flags)
> +{
> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
> +       struct bpf_dtab_netdev *dev, *old_dev;
> +       u32 ifindex = *(u32 *)value;
> +       u32 idx = *(u32 *)key;
> +
> +       if (unlikely(map_flags > BPF_EXIST || !ifindex))
> +               return -EINVAL;
> +
> +       old_dev = __dev_map_hash_lookup_elem(map, idx);
> +       if (old_dev && (map_flags & BPF_NOEXIST))
> +               return -EEXIST;
> +
> +       dev = __dev_map_alloc_node(net, dtab, ifindex, idx);
> +       if (IS_ERR(dev))
> +               return PTR_ERR(dev);
> +
> +       spin_lock(&dtab->index_lock);
> +
> +       if (old_dev) {
> +               hlist_del_rcu(&old_dev->index_hlist);
> +       } else {
> +               if (dtab->items >= dtab->map.max_entries) {
> +                       spin_unlock(&dtab->index_lock);
> +                       call_rcu(&dev->rcu, __dev_map_entry_free);
> +                       return -ENOSPC;
> +               }
> +               dtab->items++;
> +       }
> +
> +       hlist_add_head_rcu(&dev->index_hlist,
> +                          dev_map_index_hash(dtab, idx));
> +       spin_unlock(&dtab->index_lock);
> +
> +       if (old_dev)
> +               call_rcu(&old_dev->rcu, __dev_map_entry_free);
> +
> +       return 0;
> +}
> +
> +static int dev_map_hash_update_elem(struct bpf_map *map, void *key, void *value,
> +                                  u64 map_flags)
> +{
> +       return __dev_map_hash_update_elem(current->nsproxy->net_ns,
> +                                        map, key, value, map_flags);
> +}
> +
>  const struct bpf_map_ops dev_map_ops = {
>         .map_alloc = dev_map_alloc,
>         .map_free = dev_map_free,
> @@ -513,6 +695,16 @@ const struct bpf_map_ops dev_map_ops = {
>         .map_check_btf = map_check_no_btf,
>  };
>
> +const struct bpf_map_ops dev_map_hash_ops = {
> +       .map_alloc = dev_map_alloc,
> +       .map_free = dev_map_free,
> +       .map_get_next_key = dev_map_hash_get_next_key,
> +       .map_lookup_elem = dev_map_hash_lookup_elem,
> +       .map_update_elem = dev_map_hash_update_elem,
> +       .map_delete_elem = dev_map_hash_delete_elem,
> +       .map_check_btf = map_check_no_btf,
> +};
> +
>  static int dev_map_notification(struct notifier_block *notifier,
>                                 ulong event, void *ptr)
>  {
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a2e763703c30..231b9e22827c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3460,6 +3460,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
>                         goto error;
>                 break;
>         case BPF_MAP_TYPE_DEVMAP:
> +       case BPF_MAP_TYPE_DEVMAP_HASH:
>                 if (func_id != BPF_FUNC_redirect_map &&
>                     func_id != BPF_FUNC_map_lookup_elem)
>                         goto error;
> @@ -3542,6 +3543,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
>                 break;
>         case BPF_FUNC_redirect_map:
>                 if (map->map_type != BPF_MAP_TYPE_DEVMAP &&
> +                   map->map_type != BPF_MAP_TYPE_DEVMAP_HASH &&
>                     map->map_type != BPF_MAP_TYPE_CPUMAP &&
>                     map->map_type != BPF_MAP_TYPE_XSKMAP)
>                         goto error;
> diff --git a/net/core/filter.c b/net/core/filter.c
> index 089aaea0ccc6..276961c4e0d4 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -3517,7 +3517,8 @@ static int __bpf_tx_xdp_map(struct net_device *dev_rx, void *fwd,
>         int err;
>
>         switch (map->map_type) {
> -       case BPF_MAP_TYPE_DEVMAP: {
> +       case BPF_MAP_TYPE_DEVMAP:
> +       case BPF_MAP_TYPE_DEVMAP_HASH: {
>                 struct bpf_dtab_netdev *dst = fwd;
>
>                 err = dev_map_enqueue(dst, xdp, dev_rx);
> @@ -3554,6 +3555,7 @@ void xdp_do_flush_map(void)
>         if (map) {
>                 switch (map->map_type) {
>                 case BPF_MAP_TYPE_DEVMAP:
> +               case BPF_MAP_TYPE_DEVMAP_HASH:
>                         __dev_map_flush(map);
>                         break;
>                 case BPF_MAP_TYPE_CPUMAP:
> @@ -3574,6 +3576,8 @@ static inline void *__xdp_map_lookup_elem(struct bpf_map *map, u32 index)
>         switch (map->map_type) {
>         case BPF_MAP_TYPE_DEVMAP:
>                 return __dev_map_lookup_elem(map, index);
> +       case BPF_MAP_TYPE_DEVMAP_HASH:
> +               return __dev_map_hash_lookup_elem(map, index);
>         case BPF_MAP_TYPE_CPUMAP:
>                 return __cpu_map_lookup_elem(map, index);
>         case BPF_MAP_TYPE_XSKMAP:
> @@ -3655,7 +3659,8 @@ static int xdp_do_generic_redirect_map(struct net_device *dev,
>         ri->tgt_value = NULL;
>         WRITE_ONCE(ri->map, NULL);
>
> -       if (map->map_type == BPF_MAP_TYPE_DEVMAP) {
> +       if (map->map_type == BPF_MAP_TYPE_DEVMAP ||
> +           map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
>                 struct bpf_dtab_netdev *dst = fwd;
>
>                 err = dev_map_generic_redirect(dst, skb, xdp_prog);
>

Re: [PATCH bpf-next v2 6/6] tools: Add definitions for devmap_hash map type

[Quentin Monnet]

2019-07-06 10:47 UTC+0200 ~ Toke Høiland-Jørgensen <toke@redhat.com>
> From: Toke Høiland-Jørgensen <toke@redhat.com>
> 
> This adds a selftest, syncs the tools/ uapi header and adds the
> devmap_hash name to bpftool for the new devmap_hash map type.
> 
> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
> ---
>  tools/bpf/bpftool/map.c                 |    1 +
>  tools/include/uapi/linux/bpf.h          |    1 +
>  tools/testing/selftests/bpf/test_maps.c |   16 ++++++++++++++++
>  3 files changed, 18 insertions(+)
> 
> diff --git a/tools/bpf/bpftool/map.c b/tools/bpf/bpftool/map.c
> index 5da5a7311f13..c345f819b840 100644
> --- a/tools/bpf/bpftool/map.c
> +++ b/tools/bpf/bpftool/map.c
> @@ -37,6 +37,7 @@ const char * const map_type_name[] = {
>  	[BPF_MAP_TYPE_ARRAY_OF_MAPS]		= "array_of_maps",
>  	[BPF_MAP_TYPE_HASH_OF_MAPS]		= "hash_of_maps",
>  	[BPF_MAP_TYPE_DEVMAP]			= "devmap",
> +	[BPF_MAP_TYPE_DEVMAP_HASH]		= "devmap_hash",
>  	[BPF_MAP_TYPE_SOCKMAP]			= "sockmap",
>  	[BPF_MAP_TYPE_CPUMAP]			= "cpumap",
>  	[BPF_MAP_TYPE_XSKMAP]			= "xskmap",
> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
> index cecf42c871d4..8afaa0a19c67 100644
> --- a/tools/include/uapi/linux/bpf.h
> +++ b/tools/include/uapi/linux/bpf.h
> @@ -134,6 +134,7 @@ enum bpf_map_type {
>  	BPF_MAP_TYPE_QUEUE,
>  	BPF_MAP_TYPE_STACK,
>  	BPF_MAP_TYPE_SK_STORAGE,
> +	BPF_MAP_TYPE_DEVMAP_HASH,
>  };
>  
>  /* Note that tracing related programs such as

Hi Toke, thanks for the bpftool update!

Could you please also complete the documentation and bash completion for
the map type? We probably want to add the new name to the "bpftool map
help" message [0], to the manual page [1], and to the bash completion
file [2].

Thanks,
Quentin

[0]
https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/bpf/bpftool/map.c?h=v5.2-rc6#n1271
[1]
https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/bpf/bpftool/Documentation/bpftool-map.rst?h=v5.2-rc6#n46
[2]
https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/bpf/bpftool/bash-completion/bpftool?h=v5.2-rc6#n449

Re: [PATCH bpf-next v2 4/6] xdp: Add devmap_hash map type for looking up devices by hashed index

[Toke Høiland-Jørgensen]

Y Song <ys114321@gmail.com> writes:

> On Sat, Jul 6, 2019 at 1:48 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> From: Toke Høiland-Jørgensen <toke@redhat.com>
>>
>> A common pattern when using xdp_redirect_map() is to create a device map
>> where the lookup key is simply ifindex. Because device maps are arrays,
>> this leaves holes in the map, and the map has to be sized to fit the
>> largest ifindex, regardless of how many devices actually are actually
>> needed in the map.
>>
>> This patch adds a second type of device map where the key is looked up
>> using a hashmap, instead of being used as an array index. This allows maps
>> to be densely packed, so they can be smaller.
>>
>> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
>> ---
>>  include/linux/bpf.h        |    7 ++
>>  include/linux/bpf_types.h  |    1
>>  include/trace/events/xdp.h |    3 -
>>  kernel/bpf/devmap.c        |  192 ++++++++++++++++++++++++++++++++++++++++++++
>>  kernel/bpf/verifier.c      |    2
>>  net/core/filter.c          |    9 ++
>>  6 files changed, 211 insertions(+), 3 deletions(-)
>>
>> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
>> index bfdb54dd2ad1..f9a506147c8a 100644
>> --- a/include/linux/bpf.h
>> +++ b/include/linux/bpf.h
>> @@ -713,6 +713,7 @@ struct xdp_buff;
>>  struct sk_buff;
>>
>>  struct bpf_dtab_netdev *__dev_map_lookup_elem(struct bpf_map *map, u32 key);
>> +struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key);
>>  void __dev_map_flush(struct bpf_map *map);
>>  int dev_map_enqueue(struct bpf_dtab_netdev *dst, struct xdp_buff *xdp,
>>                     struct net_device *dev_rx);
>> @@ -799,6 +800,12 @@ static inline struct net_device  *__dev_map_lookup_elem(struct bpf_map *map,
>>         return NULL;
>>  }
>>
>> +static inline struct net_device  *__dev_map_hash_lookup_elem(struct bpf_map *map,
>> +                                                            u32 key)
>> +{
>> +       return NULL;
>> +}
>> +
>>  static inline void __dev_map_flush(struct bpf_map *map)
>>  {
>>  }
>> diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h
>> index eec5aeeeaf92..36a9c2325176 100644
>> --- a/include/linux/bpf_types.h
>> +++ b/include/linux/bpf_types.h
>> @@ -62,6 +62,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_ARRAY_OF_MAPS, array_of_maps_map_ops)
>>  BPF_MAP_TYPE(BPF_MAP_TYPE_HASH_OF_MAPS, htab_of_maps_map_ops)
>>  #ifdef CONFIG_NET
>>  BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP, dev_map_ops)
>> +BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP_HASH, dev_map_hash_ops)
>>  BPF_MAP_TYPE(BPF_MAP_TYPE_SK_STORAGE, sk_storage_map_ops)
>>  #if defined(CONFIG_BPF_STREAM_PARSER)
>>  BPF_MAP_TYPE(BPF_MAP_TYPE_SOCKMAP, sock_map_ops)
>> diff --git a/include/trace/events/xdp.h b/include/trace/events/xdp.h
>> index 68899fdc985b..8c8420230a10 100644
>> --- a/include/trace/events/xdp.h
>> +++ b/include/trace/events/xdp.h
>> @@ -175,7 +175,8 @@ struct _bpf_dtab_netdev {
>>  #endif /* __DEVMAP_OBJ_TYPE */
>>
>>  #define devmap_ifindex(fwd, map)                               \
>> -       ((map->map_type == BPF_MAP_TYPE_DEVMAP) ?               \
>> +       ((map->map_type == BPF_MAP_TYPE_DEVMAP ||               \
>> +         map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) ?          \
>>           ((struct _bpf_dtab_netdev *)fwd)->dev->ifindex : 0)
>>
>>  #define _trace_xdp_redirect_map(dev, xdp, fwd, map, idx)               \
>> diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
>> index a2fe16362129..341af02f049d 100644
>> --- a/kernel/bpf/devmap.c
>> +++ b/kernel/bpf/devmap.c
>> @@ -37,6 +37,12 @@
>>   * notifier hook walks the map we know that new dev references can not be
>>   * added by the user because core infrastructure ensures dev_get_by_index()
>>   * calls will fail at this point.
>> + *
>> + * The devmap_hash type is a map type which interprets keys as ifindexes and
>> + * indexes these using a hashmap. This allows maps that use ifindex as key to be
>> + * densely packed instead of having holes in the lookup array for unused
>> + * ifindexes. The setup and packet enqueue/send code is shared between the two
>> + * types of devmap; only the lookup and insertion is different.
>>   */
>>  #include <linux/bpf.h>
>>  #include <net/xdp.h>
>> @@ -59,6 +65,7 @@ struct xdp_bulk_queue {
>>
>>  struct bpf_dtab_netdev {
>>         struct net_device *dev; /* must be first member, due to tracepoint */
>> +       struct hlist_node index_hlist;
>>         struct bpf_dtab *dtab;
>>         unsigned int idx; /* keep track of map index for tracepoint */
>>         struct xdp_bulk_queue __percpu *bulkq;
>> @@ -70,11 +77,29 @@ struct bpf_dtab {
>>         struct bpf_dtab_netdev **netdev_map;
>>         struct list_head __percpu *flush_list;
>>         struct list_head list;
>> +
>> +       /* these are only used for DEVMAP_HASH type maps */
>> +       unsigned int items;
>> +       struct hlist_head *dev_index_head;
>> +       spinlock_t index_lock;
>>  };
>>
>>  static DEFINE_SPINLOCK(dev_map_lock);
>>  static LIST_HEAD(dev_map_list);
>>
>> +static struct hlist_head *dev_map_create_hash(void)
>> +{
>> +       int i;
>> +       struct hlist_head *hash;
>> +
>> +       hash = kmalloc_array(NETDEV_HASHENTRIES, sizeof(*hash), GFP_KERNEL);
>> +       if (hash != NULL)
>> +               for (i = 0; i < NETDEV_HASHENTRIES; i++)
>> +                       INIT_HLIST_HEAD(&hash[i]);
>> +
>> +       return hash;
>> +}
>> +
>>  static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
>>                             bool check_memlock)
>>  {
>> @@ -98,6 +123,9 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
>>         cost = (u64) dtab->map.max_entries * sizeof(struct bpf_dtab_netdev *);
>>         cost += sizeof(struct list_head) * num_possible_cpus();
>>
>> +       if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH)
>> +               cost += sizeof(struct hlist_head) * NETDEV_HASHENTRIES;
>> +
>>         /* if map size is larger than memlock limit, reject it */
>>         err = bpf_map_charge_init(&dtab->map.memory, cost);
>>         if (err)
>> @@ -116,8 +144,18 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
>>         if (!dtab->netdev_map)
>>                 goto free_percpu;
>>
>> +       if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
>> +               dtab->dev_index_head = dev_map_create_hash();
>> +               if (!dtab->dev_index_head)
>> +                       goto free_map_area;
>> +
>> +               spin_lock_init(&dtab->index_lock);
>> +       }
>> +
>>         return 0;
>>
>> +free_map_area:
>> +       bpf_map_area_free(dtab->netdev_map);
>>  free_percpu:
>>         free_percpu(dtab->flush_list);
>>  free_charge:
>> @@ -199,6 +237,7 @@ static void dev_map_free(struct bpf_map *map)
>>
>>         free_percpu(dtab->flush_list);
>>         bpf_map_area_free(dtab->netdev_map);
>> +       kfree(dtab->dev_index_head);
>>         kfree(dtab);
>>  }
>>
>> @@ -219,6 +258,70 @@ static int dev_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
>>         return 0;
>>  }
>>
>> +static inline struct hlist_head *dev_map_index_hash(struct bpf_dtab *dtab,
>> +                                                   int idx)
>> +{
>> +       return &dtab->dev_index_head[idx & (NETDEV_HASHENTRIES - 1)];
>> +}
>> +
>> +struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key)
>> +{
>> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
>> +       struct hlist_head *head = dev_map_index_hash(dtab, key);
>> +       struct bpf_dtab_netdev *dev;
>> +
>> +       hlist_for_each_entry_rcu(dev, head, index_hlist)
>> +               if (dev->idx == key)
>> +                       return dev;
>> +
>> +       return NULL;
>> +}
>> +
>> +static int dev_map_hash_get_next_key(struct bpf_map *map, void *key,
>> +                                   void *next_key)
>> +{
>> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
>> +       u32 idx, *next = next_key;
>> +       struct bpf_dtab_netdev *dev, *next_dev;
>> +       struct hlist_head *head;
>> +       int i = 0;
>> +
>> +       if (!key)
>> +               goto find_first;
>> +
>> +       idx = *(u32 *)key;
>> +
>> +       dev = __dev_map_hash_lookup_elem(map, idx);
>> +       if (!dev)
>> +               goto find_first;
>> +
>> +       next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(&dev->index_hlist)),
>> +                                   struct bpf_dtab_netdev, index_hlist);
>
> Just want to get a better understanding. Why do you want
> hlist_entry_safe instead of hlist_entry?

Erm, because the entry might not exist? The _safe variant just checks
the list pointer before casting to the containing struct.

> Also, maybe rcu_dereference instead of rcu_dereference_raw?

Well, the _raw() variant comes from the equivalent function in
hashtab.c, where I originally nicked most of this function, so think it
makes more sense to keep them the same.

> dev_map_hash_get_next_key() is called in syscall.c within rcu_read_lock region.
>
>> +
>> +       if (next_dev) {
>> +               *next = next_dev->idx;
>> +               return 0;
>> +       }
>> +
>> +       i = idx & (NETDEV_HASHENTRIES - 1);
>> +       i++;
>> +
>> + find_first:
>> +       for (; i < NETDEV_HASHENTRIES; i++) {
>> +               head = dev_map_index_hash(dtab, i);
>> +
>> +               next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),
>> +                                           struct bpf_dtab_netdev,
>> +                                           index_hlist);
>
> ditto. The same question as the above.
>
>> +               if (next_dev) {
>> +                       *next = next_dev->idx;
>> +                       return 0;
>> +               }
>> +       }
>> +
>> +       return -ENOENT;
>> +}
>> +
>>  static int bq_xmit_all(struct xdp_bulk_queue *bq, u32 flags,
>>                        bool in_napi_ctx)
>>  {
>> @@ -374,6 +477,15 @@ static void *dev_map_lookup_elem(struct bpf_map *map, void *key)
>>         return dev ? &dev->ifindex : NULL;
>>  }
>>
>> +static void *dev_map_hash_lookup_elem(struct bpf_map *map, void *key)
>> +{
>> +       struct bpf_dtab_netdev *obj = __dev_map_hash_lookup_elem(map,
>> +                                                               *(u32 *)key);
>> +       struct net_device *dev = obj ? obj->dev : NULL;
>
> When obj->dev could be NULL?

Never. This could just as well be written as

return obj ? obj->dev->ifindex : NULL;

but writing it this way keeps it consistent with the existing
dev_map_lookup_elem() function.

>> +
>> +       return dev ? &dev->ifindex : NULL;
>> +}
>> +
>>  static void dev_map_flush_old(struct bpf_dtab_netdev *dev)
>>  {
>>         if (dev->dev->netdev_ops->ndo_xdp_xmit) {
>> @@ -423,6 +535,27 @@ static int dev_map_delete_elem(struct bpf_map *map, void *key)
>>         return 0;
>>  }
>>
>> +static int dev_map_hash_delete_elem(struct bpf_map *map, void *key)
>> +{
>> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
>> +       struct bpf_dtab_netdev *old_dev;
>> +       int k = *(u32 *)key;
>> +
>> +       old_dev = __dev_map_hash_lookup_elem(map, k);
>> +       if (!old_dev)
>> +               return 0;
>> +
>> +       spin_lock(&dtab->index_lock);
>> +       if (!hlist_unhashed(&old_dev->index_hlist)) {
>> +               dtab->items--;
>> +               hlist_del_init_rcu(&old_dev->index_hlist);
>> +       }
>> +       spin_unlock(&dtab->index_lock);
>> +
>> +       call_rcu(&old_dev->rcu, __dev_map_entry_free);
>> +       return 0;
>> +}
>> +
>>  static struct bpf_dtab_netdev *__dev_map_alloc_node(struct net *net,
>>                                                     struct bpf_dtab *dtab,
>>                                                     u32 ifindex,
>> @@ -503,6 +636,55 @@ static int dev_map_update_elem(struct bpf_map *map, void *key, void *value,
>>                                      map, key, value, map_flags);
>>  }
>>
>> +static int __dev_map_hash_update_elem(struct net *net, struct bpf_map *map,
>> +                                    void *key, void *value, u64 map_flags)
>> +{
>> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
>> +       struct bpf_dtab_netdev *dev, *old_dev;
>> +       u32 ifindex = *(u32 *)value;
>> +       u32 idx = *(u32 *)key;
>> +
>> +       if (unlikely(map_flags > BPF_EXIST || !ifindex))
>> +               return -EINVAL;
>> +
>> +       old_dev = __dev_map_hash_lookup_elem(map, idx);
>> +       if (old_dev && (map_flags & BPF_NOEXIST))
>> +               return -EEXIST;
>> +
>> +       dev = __dev_map_alloc_node(net, dtab, ifindex, idx);
>> +       if (IS_ERR(dev))
>> +               return PTR_ERR(dev);
>> +
>> +       spin_lock(&dtab->index_lock);
>> +
>> +       if (old_dev) {
>> +               hlist_del_rcu(&old_dev->index_hlist);
>> +       } else {
>> +               if (dtab->items >= dtab->map.max_entries) {
>> +                       spin_unlock(&dtab->index_lock);
>> +                       call_rcu(&dev->rcu, __dev_map_entry_free);
>> +                       return -ENOSPC;
>> +               }
>> +               dtab->items++;
>> +       }
>> +
>> +       hlist_add_head_rcu(&dev->index_hlist,
>> +                          dev_map_index_hash(dtab, idx));
>> +       spin_unlock(&dtab->index_lock);
>> +
>> +       if (old_dev)
>> +               call_rcu(&old_dev->rcu, __dev_map_entry_free);
>> +
>> +       return 0;
>> +}
>> +
>> +static int dev_map_hash_update_elem(struct bpf_map *map, void *key, void *value,
>> +                                  u64 map_flags)
>> +{
>> +       return __dev_map_hash_update_elem(current->nsproxy->net_ns,
>> +                                        map, key, value, map_flags);
>> +}
>> +
>>  const struct bpf_map_ops dev_map_ops = {
>>         .map_alloc = dev_map_alloc,
>>         .map_free = dev_map_free,
>> @@ -513,6 +695,16 @@ const struct bpf_map_ops dev_map_ops = {
>>         .map_check_btf = map_check_no_btf,
>>  };
>>
>> +const struct bpf_map_ops dev_map_hash_ops = {
>> +       .map_alloc = dev_map_alloc,
>> +       .map_free = dev_map_free,
>> +       .map_get_next_key = dev_map_hash_get_next_key,
>> +       .map_lookup_elem = dev_map_hash_lookup_elem,
>> +       .map_update_elem = dev_map_hash_update_elem,
>> +       .map_delete_elem = dev_map_hash_delete_elem,
>> +       .map_check_btf = map_check_no_btf,
>> +};
>> +
>>  static int dev_map_notification(struct notifier_block *notifier,
>>                                 ulong event, void *ptr)
>>  {
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index a2e763703c30..231b9e22827c 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -3460,6 +3460,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
>>                         goto error;
>>                 break;
>>         case BPF_MAP_TYPE_DEVMAP:
>> +       case BPF_MAP_TYPE_DEVMAP_HASH:
>>                 if (func_id != BPF_FUNC_redirect_map &&
>>                     func_id != BPF_FUNC_map_lookup_elem)
>>                         goto error;
>> @@ -3542,6 +3543,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
>>                 break;
>>         case BPF_FUNC_redirect_map:
>>                 if (map->map_type != BPF_MAP_TYPE_DEVMAP &&
>> +                   map->map_type != BPF_MAP_TYPE_DEVMAP_HASH &&
>>                     map->map_type != BPF_MAP_TYPE_CPUMAP &&
>>                     map->map_type != BPF_MAP_TYPE_XSKMAP)
>>                         goto error;
>> diff --git a/net/core/filter.c b/net/core/filter.c
>> index 089aaea0ccc6..276961c4e0d4 100644
>> --- a/net/core/filter.c
>> +++ b/net/core/filter.c
>> @@ -3517,7 +3517,8 @@ static int __bpf_tx_xdp_map(struct net_device *dev_rx, void *fwd,
>>         int err;
>>
>>         switch (map->map_type) {
>> -       case BPF_MAP_TYPE_DEVMAP: {
>> +       case BPF_MAP_TYPE_DEVMAP:
>> +       case BPF_MAP_TYPE_DEVMAP_HASH: {
>>                 struct bpf_dtab_netdev *dst = fwd;
>>
>>                 err = dev_map_enqueue(dst, xdp, dev_rx);
>> @@ -3554,6 +3555,7 @@ void xdp_do_flush_map(void)
>>         if (map) {
>>                 switch (map->map_type) {
>>                 case BPF_MAP_TYPE_DEVMAP:
>> +               case BPF_MAP_TYPE_DEVMAP_HASH:
>>                         __dev_map_flush(map);
>>                         break;
>>                 case BPF_MAP_TYPE_CPUMAP:
>> @@ -3574,6 +3576,8 @@ static inline void *__xdp_map_lookup_elem(struct bpf_map *map, u32 index)
>>         switch (map->map_type) {
>>         case BPF_MAP_TYPE_DEVMAP:
>>                 return __dev_map_lookup_elem(map, index);
>> +       case BPF_MAP_TYPE_DEVMAP_HASH:
>> +               return __dev_map_hash_lookup_elem(map, index);
>>         case BPF_MAP_TYPE_CPUMAP:
>>                 return __cpu_map_lookup_elem(map, index);
>>         case BPF_MAP_TYPE_XSKMAP:
>> @@ -3655,7 +3659,8 @@ static int xdp_do_generic_redirect_map(struct net_device *dev,
>>         ri->tgt_value = NULL;
>>         WRITE_ONCE(ri->map, NULL);
>>
>> -       if (map->map_type == BPF_MAP_TYPE_DEVMAP) {
>> +       if (map->map_type == BPF_MAP_TYPE_DEVMAP ||
>> +           map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
>>                 struct bpf_dtab_netdev *dst = fwd;
>>
>>                 err = dev_map_generic_redirect(dst, skb, xdp_prog);
>>

Re: [PATCH bpf-next v2 6/6] tools: Add definitions for devmap_hash map type

[Toke Høiland-Jørgensen]

Quentin Monnet <quentin.monnet@netronome.com> writes:

> 2019-07-06 10:47 UTC+0200 ~ Toke Høiland-Jørgensen <toke@redhat.com>
>> From: Toke Høiland-Jørgensen <toke@redhat.com>
>> 
>> This adds a selftest, syncs the tools/ uapi header and adds the
>> devmap_hash name to bpftool for the new devmap_hash map type.
>> 
>> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
>> ---
>>  tools/bpf/bpftool/map.c                 |    1 +
>>  tools/include/uapi/linux/bpf.h          |    1 +
>>  tools/testing/selftests/bpf/test_maps.c |   16 ++++++++++++++++
>>  3 files changed, 18 insertions(+)
>> 
>> diff --git a/tools/bpf/bpftool/map.c b/tools/bpf/bpftool/map.c
>> index 5da5a7311f13..c345f819b840 100644
>> --- a/tools/bpf/bpftool/map.c
>> +++ b/tools/bpf/bpftool/map.c
>> @@ -37,6 +37,7 @@ const char * const map_type_name[] = {
>>  	[BPF_MAP_TYPE_ARRAY_OF_MAPS]		= "array_of_maps",
>>  	[BPF_MAP_TYPE_HASH_OF_MAPS]		= "hash_of_maps",
>>  	[BPF_MAP_TYPE_DEVMAP]			= "devmap",
>> +	[BPF_MAP_TYPE_DEVMAP_HASH]		= "devmap_hash",
>>  	[BPF_MAP_TYPE_SOCKMAP]			= "sockmap",
>>  	[BPF_MAP_TYPE_CPUMAP]			= "cpumap",
>>  	[BPF_MAP_TYPE_XSKMAP]			= "xskmap",
>> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
>> index cecf42c871d4..8afaa0a19c67 100644
>> --- a/tools/include/uapi/linux/bpf.h
>> +++ b/tools/include/uapi/linux/bpf.h
>> @@ -134,6 +134,7 @@ enum bpf_map_type {
>>  	BPF_MAP_TYPE_QUEUE,
>>  	BPF_MAP_TYPE_STACK,
>>  	BPF_MAP_TYPE_SK_STORAGE,
>> +	BPF_MAP_TYPE_DEVMAP_HASH,
>>  };
>>  
>>  /* Note that tracing related programs such as
>
> Hi Toke, thanks for the bpftool update!
>
> Could you please also complete the documentation and bash completion for
> the map type? We probably want to add the new name to the "bpftool map
> help" message [0], to the manual page [1], and to the bash completion
> file [2].

Sure, can do :)

-Toke

Re: [PATCH bpf-next v2 0/6] xdp: Add devmap_hash map type

[Toke Høiland-Jørgensen]

Y Song <ys114321@gmail.com> writes:

> On Sat, Jul 6, 2019 at 1:47 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> This series adds a new map type, devmap_hash, that works like the existing
>> devmap type, but using a hash-based indexing scheme. This is useful for the use
>> case where a devmap is indexed by ifindex (for instance for use with the routing
>> table lookup helper). For this use case, the regular devmap needs to be sized
>> after the maximum ifindex number, not the number of devices in it. A hash-based
>> indexing scheme makes it possible to size the map after the number of devices it
>> should contain instead.
>>
>> This was previously part of my patch series that also turned the regular
>> bpf_redirect() helper into a map-based one; for this series I just pulled out
>> the patches that introduced the new map type.
>>
>> Changelog:
>>
>> v2:
>>
>> - Split commit adding the new map type so uapi and tools changes are separate.
>>
>> Changes to these patches since the previous series:
>>
>> - Rebase on top of the other devmap changes (makes this one simpler!)
>> - Don't enforce key==val, but allow arbitrary indexes.
>> - Rename the type to devmap_hash to reflect the fact that it's just a hashmap now.
>>
>> ---
>>
>> Toke Høiland-Jørgensen (6):
>>       include/bpf.h: Remove map_insert_ctx() stubs
>>       xdp: Refactor devmap allocation code for reuse
>>       uapi/bpf: Add new devmap_hash type
>>       xdp: Add devmap_hash map type for looking up devices by hashed index
>>       tools/libbpf_probes: Add new devmap_hash type
>>       tools: Add definitions for devmap_hash map type
>
> Thanks for re-organize the patch. I guess this can be tweaked a little more
> to better suit for syncing between kernel and libbpf repo.
>
> Let me provide a little bit background here. The below is
> a sync done by Andrii from kernel/tools to libbpf repo.
>
> =============
> commit 39de6711795f6d1583ae96ed8d13892bc4475ac1
> Author: Andrii Nakryiko <andriin@fb.com>
> Date:   Tue Jun 11 09:56:11 2019 -0700
>
>     sync: latest libbpf changes from kernel
>
>     Syncing latest libbpf commits from kernel repository.
>     Baseline commit:   e672db03ab0e43e41ab6f8b2156a10d6e40f243d
>     Checkpoint commit: 5e2ac390fbd08b2a462db66cef2663e4db0d5191
>
>     Andrii Nakryiko (9):
>       libbpf: fix detection of corrupted BPF instructions section
>       libbpf: preserve errno before calling into user callback
>       libbpf: simplify endianness check
>       libbpf: check map name retrieved from ELF
>       libbpf: fix error code returned on corrupted ELF
>       libbpf: use negative fd to specify missing BTF
>       libbpf: simplify two pieces of logic
>       libbpf: typo and formatting fixes
>       libbpf: reduce unnecessary line wrapping
>
>     Hechao Li (1):
>       bpf: add a new API libbpf_num_possible_cpus()
>
>     Jonathan Lemon (2):
>       bpf/tools: sync bpf.h
>       libbpf: remove qidconf and better support external bpf programs.
>
>     Quentin Monnet (1):
>       libbpf: prevent overwriting of log_level in bpf_object__load_progs()
>
>      include/uapi/linux/bpf.h |   4 +
>      src/libbpf.c             | 207 ++++++++++++++++++++++-----------------
>      src/libbpf.h             |  16 +++
>      src/libbpf.map           |   1 +
>      src/xsk.c                | 103 ++++++-------------
>      5 files changed, 167 insertions(+), 164 deletions(-)
> ==========
>
> You can see the commits at tools/lib/bpf and
> commits at tools/include/uapi/{linux/[bpf.h, btf.h], ...}
> are sync'ed to libbpf repo.
>
> So we would like kernel commits to be aligned that way for better
> automatic syncing.
>
> Therefore, your current patch set could be changed from
>    >       include/bpf.h: Remove map_insert_ctx() stubs
>    >       xdp: Refactor devmap allocation code for reuse
>    >       uapi/bpf: Add new devmap_hash type
>    >       xdp: Add devmap_hash map type for looking up devices by hashed index
>    >       tools/libbpf_probes: Add new devmap_hash type
>    >       tools: Add definitions for devmap_hash map type
> to
>       1. include/bpf.h: Remove map_insert_ctx() stubs
>       2. xdp: Refactor devmap allocation code for reuse
>       3. kernel non-tools changes (the above patch #3 and #4)
>       4. tools/include/uapi change (part of the above patch #6)
>       5. tools/libbpf_probes change
>       6. other tools/ change (the above patch #6 - new patch #4).
>
> Thanks!

Ah, right, got the two uapi updates mixed up I guess. Will fix and
respin :)

-Toke

Re: [PATCH bpf-next v2 4/6] xdp: Add devmap_hash map type for looking up devices by hashed index

[Y Song]

On Mon, Jul 8, 2019 at 2:55 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Y Song <ys114321@gmail.com> writes:
>
> > On Sat, Jul 6, 2019 at 1:48 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> >>
> >> From: Toke Høiland-Jørgensen <toke@redhat.com>
> >>
> >> A common pattern when using xdp_redirect_map() is to create a device map
> >> where the lookup key is simply ifindex. Because device maps are arrays,
> >> this leaves holes in the map, and the map has to be sized to fit the
> >> largest ifindex, regardless of how many devices actually are actually
> >> needed in the map.
> >>
> >> This patch adds a second type of device map where the key is looked up
> >> using a hashmap, instead of being used as an array index. This allows maps
> >> to be densely packed, so they can be smaller.
> >>
> >> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
> >> ---
> >>  include/linux/bpf.h        |    7 ++
> >>  include/linux/bpf_types.h  |    1
> >>  include/trace/events/xdp.h |    3 -
> >>  kernel/bpf/devmap.c        |  192 ++++++++++++++++++++++++++++++++++++++++++++
> >>  kernel/bpf/verifier.c      |    2
> >>  net/core/filter.c          |    9 ++
> >>  6 files changed, 211 insertions(+), 3 deletions(-)
> >>
> >> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> >> index bfdb54dd2ad1..f9a506147c8a 100644
> >> --- a/include/linux/bpf.h
> >> +++ b/include/linux/bpf.h
> >> @@ -713,6 +713,7 @@ struct xdp_buff;
> >>  struct sk_buff;
> >>
> >>  struct bpf_dtab_netdev *__dev_map_lookup_elem(struct bpf_map *map, u32 key);
> >> +struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key);
> >>  void __dev_map_flush(struct bpf_map *map);
> >>  int dev_map_enqueue(struct bpf_dtab_netdev *dst, struct xdp_buff *xdp,
> >>                     struct net_device *dev_rx);
> >> @@ -799,6 +800,12 @@ static inline struct net_device  *__dev_map_lookup_elem(struct bpf_map *map,
> >>         return NULL;
> >>  }
> >>
> >> +static inline struct net_device  *__dev_map_hash_lookup_elem(struct bpf_map *map,
> >> +                                                            u32 key)
> >> +{
> >> +       return NULL;
> >> +}
> >> +
> >>  static inline void __dev_map_flush(struct bpf_map *map)
> >>  {
> >>  }
> >> diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h
> >> index eec5aeeeaf92..36a9c2325176 100644
> >> --- a/include/linux/bpf_types.h
> >> +++ b/include/linux/bpf_types.h
> >> @@ -62,6 +62,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_ARRAY_OF_MAPS, array_of_maps_map_ops)
> >>  BPF_MAP_TYPE(BPF_MAP_TYPE_HASH_OF_MAPS, htab_of_maps_map_ops)
> >>  #ifdef CONFIG_NET
> >>  BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP, dev_map_ops)
> >> +BPF_MAP_TYPE(BPF_MAP_TYPE_DEVMAP_HASH, dev_map_hash_ops)
> >>  BPF_MAP_TYPE(BPF_MAP_TYPE_SK_STORAGE, sk_storage_map_ops)
> >>  #if defined(CONFIG_BPF_STREAM_PARSER)
> >>  BPF_MAP_TYPE(BPF_MAP_TYPE_SOCKMAP, sock_map_ops)
> >> diff --git a/include/trace/events/xdp.h b/include/trace/events/xdp.h
> >> index 68899fdc985b..8c8420230a10 100644
> >> --- a/include/trace/events/xdp.h
> >> +++ b/include/trace/events/xdp.h
> >> @@ -175,7 +175,8 @@ struct _bpf_dtab_netdev {
> >>  #endif /* __DEVMAP_OBJ_TYPE */
> >>
> >>  #define devmap_ifindex(fwd, map)                               \
> >> -       ((map->map_type == BPF_MAP_TYPE_DEVMAP) ?               \
> >> +       ((map->map_type == BPF_MAP_TYPE_DEVMAP ||               \
> >> +         map->map_type == BPF_MAP_TYPE_DEVMAP_HASH) ?          \
> >>           ((struct _bpf_dtab_netdev *)fwd)->dev->ifindex : 0)
> >>
> >>  #define _trace_xdp_redirect_map(dev, xdp, fwd, map, idx)               \
> >> diff --git a/kernel/bpf/devmap.c b/kernel/bpf/devmap.c
> >> index a2fe16362129..341af02f049d 100644
> >> --- a/kernel/bpf/devmap.c
> >> +++ b/kernel/bpf/devmap.c
> >> @@ -37,6 +37,12 @@
> >>   * notifier hook walks the map we know that new dev references can not be
> >>   * added by the user because core infrastructure ensures dev_get_by_index()
> >>   * calls will fail at this point.
> >> + *
> >> + * The devmap_hash type is a map type which interprets keys as ifindexes and
> >> + * indexes these using a hashmap. This allows maps that use ifindex as key to be
> >> + * densely packed instead of having holes in the lookup array for unused
> >> + * ifindexes. The setup and packet enqueue/send code is shared between the two
> >> + * types of devmap; only the lookup and insertion is different.
> >>   */
> >>  #include <linux/bpf.h>
> >>  #include <net/xdp.h>
> >> @@ -59,6 +65,7 @@ struct xdp_bulk_queue {
> >>
> >>  struct bpf_dtab_netdev {
> >>         struct net_device *dev; /* must be first member, due to tracepoint */
> >> +       struct hlist_node index_hlist;
> >>         struct bpf_dtab *dtab;
> >>         unsigned int idx; /* keep track of map index for tracepoint */
> >>         struct xdp_bulk_queue __percpu *bulkq;
> >> @@ -70,11 +77,29 @@ struct bpf_dtab {
> >>         struct bpf_dtab_netdev **netdev_map;
> >>         struct list_head __percpu *flush_list;
> >>         struct list_head list;
> >> +
> >> +       /* these are only used for DEVMAP_HASH type maps */
> >> +       unsigned int items;
> >> +       struct hlist_head *dev_index_head;
> >> +       spinlock_t index_lock;
> >>  };
> >>
> >>  static DEFINE_SPINLOCK(dev_map_lock);
> >>  static LIST_HEAD(dev_map_list);
> >>
> >> +static struct hlist_head *dev_map_create_hash(void)
> >> +{
> >> +       int i;
> >> +       struct hlist_head *hash;
> >> +
> >> +       hash = kmalloc_array(NETDEV_HASHENTRIES, sizeof(*hash), GFP_KERNEL);
> >> +       if (hash != NULL)
> >> +               for (i = 0; i < NETDEV_HASHENTRIES; i++)
> >> +                       INIT_HLIST_HEAD(&hash[i]);
> >> +
> >> +       return hash;
> >> +}
> >> +
> >>  static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
> >>                             bool check_memlock)
> >>  {
> >> @@ -98,6 +123,9 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
> >>         cost = (u64) dtab->map.max_entries * sizeof(struct bpf_dtab_netdev *);
> >>         cost += sizeof(struct list_head) * num_possible_cpus();
> >>
> >> +       if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH)
> >> +               cost += sizeof(struct hlist_head) * NETDEV_HASHENTRIES;
> >> +
> >>         /* if map size is larger than memlock limit, reject it */
> >>         err = bpf_map_charge_init(&dtab->map.memory, cost);
> >>         if (err)
> >> @@ -116,8 +144,18 @@ static int dev_map_init_map(struct bpf_dtab *dtab, union bpf_attr *attr,
> >>         if (!dtab->netdev_map)
> >>                 goto free_percpu;
> >>
> >> +       if (attr->map_type == BPF_MAP_TYPE_DEVMAP_HASH) {
> >> +               dtab->dev_index_head = dev_map_create_hash();
> >> +               if (!dtab->dev_index_head)
> >> +                       goto free_map_area;
> >> +
> >> +               spin_lock_init(&dtab->index_lock);
> >> +       }
> >> +
> >>         return 0;
> >>
> >> +free_map_area:
> >> +       bpf_map_area_free(dtab->netdev_map);
> >>  free_percpu:
> >>         free_percpu(dtab->flush_list);
> >>  free_charge:
> >> @@ -199,6 +237,7 @@ static void dev_map_free(struct bpf_map *map)
> >>
> >>         free_percpu(dtab->flush_list);
> >>         bpf_map_area_free(dtab->netdev_map);
> >> +       kfree(dtab->dev_index_head);
> >>         kfree(dtab);
> >>  }
> >>
> >> @@ -219,6 +258,70 @@ static int dev_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
> >>         return 0;
> >>  }
> >>
> >> +static inline struct hlist_head *dev_map_index_hash(struct bpf_dtab *dtab,
> >> +                                                   int idx)
> >> +{
> >> +       return &dtab->dev_index_head[idx & (NETDEV_HASHENTRIES - 1)];
> >> +}
> >> +
> >> +struct bpf_dtab_netdev *__dev_map_hash_lookup_elem(struct bpf_map *map, u32 key)
> >> +{
> >> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
> >> +       struct hlist_head *head = dev_map_index_hash(dtab, key);
> >> +       struct bpf_dtab_netdev *dev;
> >> +
> >> +       hlist_for_each_entry_rcu(dev, head, index_hlist)
> >> +               if (dev->idx == key)
> >> +                       return dev;
> >> +
> >> +       return NULL;
> >> +}
> >> +
> >> +static int dev_map_hash_get_next_key(struct bpf_map *map, void *key,
> >> +                                   void *next_key)
> >> +{
> >> +       struct bpf_dtab *dtab = container_of(map, struct bpf_dtab, map);
> >> +       u32 idx, *next = next_key;
> >> +       struct bpf_dtab_netdev *dev, *next_dev;
> >> +       struct hlist_head *head;
> >> +       int i = 0;
> >> +
> >> +       if (!key)
> >> +               goto find_first;
> >> +
> >> +       idx = *(u32 *)key;
> >> +
> >> +       dev = __dev_map_hash_lookup_elem(map, idx);
> >> +       if (!dev)
> >> +               goto find_first;
> >> +
> >> +       next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(&dev->index_hlist)),
> >> +                                   struct bpf_dtab_netdev, index_hlist);
> >
> > Just want to get a better understanding. Why do you want
> > hlist_entry_safe instead of hlist_entry?
>
> Erm, because the entry might not exist? The _safe variant just checks
> the list pointer before casting to the containing struct.

hlist_entry_safe is certainly correct. Just want to better understand when
the entry might not exist. By looking at hashtab.c implementation, it has
the same possible-null-entry assumption, so we should be ok here.

>
> > Also, maybe rcu_dereference instead of rcu_dereference_raw?
>
> Well, the _raw() variant comes from the equivalent function in
> hashtab.c, where I originally nicked most of this function, so think it
> makes more sense to keep them the same.

Okay.

>
> > dev_map_hash_get_next_key() is called in syscall.c within rcu_read_lock region.
> >
> >> +
> >> +       if (next_dev) {
> >> +               *next = next_dev->idx;
> >> +               return 0;
> >> +       }
> >> +
> >> +       i = idx & (NETDEV_HASHENTRIES - 1);
> >> +       i++;
> >> +
> >> + find_first:
> >> +       for (; i < NETDEV_HASHENTRIES; i++) {
> >> +               head = dev_map_index_hash(dtab, i);
> >> +
> >> +               next_dev = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),
> >> +                                           struct bpf_dtab_netdev,
> >> +                                           index_hlist);
> >
> > ditto. The same question as the above.
> >
> >> +               if (next_dev) {
> >> +                       *next = next_dev->idx;
> >> +                       return 0;
> >> +               }
> >> +       }
> >> +
> >> +       return -ENOENT;
> >> +}
> >> +
> >>  static int bq_xmit_all(struct xdp_bulk_queue *bq, u32 flags,
> >>                        bool in_napi_ctx)
> >>  {
> >> @@ -374,6 +477,15 @@ static void *dev_map_lookup_elem(struct bpf_map *map, void *key)
> >>         return dev ? &dev->ifindex : NULL;
> >>  }
> >>
> >> +static void *dev_map_hash_lookup_elem(struct bpf_map *map, void *key)
> >> +{
> >> +       struct bpf_dtab_netdev *obj = __dev_map_hash_lookup_elem(map,
> >> +                                                               *(u32 *)key);
> >> +       struct net_device *dev = obj ? obj->dev : NULL;
> >
> > When obj->dev could be NULL?
>
> Never. This could just as well be written as
>
> return obj ? obj->dev->ifindex : NULL;
>
> but writing it this way keeps it consistent with the existing
> dev_map_lookup_elem() function.

Okay then in order to be consistent with the existing code base.

Thanks for all the explanation!