Skip to contentSkip to conversation

bpf: adding map batch processing support

RFC In review Brian Vazquez 3 participants 7 messages Nov 7, 2019 – Nov 15, 2019 1 message not in the archive

Subsystems (7)
lore
Share & tools
lore
#0 lore raw

cover bpf: adding map batch processing support

This is a follow up in the effort to batch bpf map operations to reduce the syscall overhead with the map_ops. I initially proposed the idea and the discussion is here:
https://lore.kernel.org/bpf/[email protected]/

Yonghong talked at the LPC about this and also proposed and idea that handles the special weird case of hashtables by doing traversing using the buckets as a reference instead of a key. Discussion is here:
https://lore.kernel.org/bpf/[email protected]/

This RFC proposes a way to extend batch operations for more data structures by creating generic batch functions that can be used instead of implementing the operations for each individual data structure, reducing the code that needs to be maintained. The series contains the patches used in Yonghong's RFC and the patch that adds the generic implementation of the operations plus some testing with pcpu hashmaps and arrays. Note that pcpu hashmap shouldn't use the generic implementation and it either should have its own implementation or share the one introduced by Yonghong, I added that just as an example to show that the generic implementation can be easily added to a data structure.

What I want to achieve with this RFC is to collect early feedback and see if there's any major concern about this before I move forward. I do plan to better separate this into different patches and explain them properly in the commit messages.

Current known issues where I would like to discuss are the followings:

- Because Yonghong's UAPI definition was done specifically for iterating buckets, the batch field is u64 and is treated as an u64 instead of an opaque pointer, this won't work for other data structures that are going to use a key as a batch token with a size greater than
64. Although I think at this point the only key that couldn't be treated as a u64 is the key of a hashmap, and the hashmap won't use the generic interface.
- Not all the data structures use delete (because it's not a valid operation) i.e. arrays. So maybe lookup_and_delete_batch command is not needed and we can handle that operation with a lookup_batch and a flag.
- For delete_batch (not just the lookup_and_delete_batch). Is this operation really needed? If so, shouldn't it be better if the behaviour is delete the keys provided? I did that with my generic implementation but Yonghong's delete_batch for a hashmap deletes buckets.

Brian Vazquez (1):
bpf: add generic batch support

Yonghong Song (2):
bpf: adding map batch processing support tools/bpf: test bpf_map_lookup_and_delete_batch()

 include/linux/bpf.h                           |  21 +
 include/uapi/linux/bpf.h                      |  22 +
 kernel/bpf/arraymap.c                         |   4 +
 kernel/bpf/hashtab.c                          | 331 ++++++++++
 kernel/bpf/syscall.c                          | 573 ++++++++++++++----
 tools/include/uapi/linux/bpf.h                |  22 +
 tools/lib/bpf/bpf.c                           |  59 ++
 tools/lib/bpf/bpf.h                           |  13 +
 tools/lib/bpf/libbpf.map                      |   4 +
 .../map_tests/map_lookup_and_delete_batch.c   | 245 ++++++++
 .../map_lookup_and_delete_batch_array.c       | 118 ++++
 11 files changed, 1292 insertions(+), 120 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch.c
 create mode 100644 tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch_array.c
Signature · 1 line
2.24.0.432.g9d3f5f5b63-goog
#1 lore raw

RFC 1/3 bpf: adding map batch processing support

From: Yonghong Song <[email protected]>

Brian Vazquez has proposed BPF_MAP_DUMP command to look up more than one map entries per syscall.
https://lore.kernel.org/bpf/CABCgpaU3xxX6CMMxD+1knApivtc2jLBHysDXw-0E9bQEL0qC3A@mail.gmail.com/T/#t

During discussion, we found more use cases can be supported in a similar map operation batching framework. For example, batched map lookup and delete, which can be really helpful for bcc.
https://github.com/iovisor/bcc/blob/master/tools/tcptop.py#L233-L243
https://github.com/iovisor/bcc/blob/master/tools/slabratetop.py#L129-L138

Also, in bcc, we have API to delete all entries in a map.
https://github.com/iovisor/bcc/blob/master/src/cc/api/BPFTable.h#L257-L264

For map update, batched operations also useful as sometimes applications need to populate initial maps with more than one entry. For example, the below example is from kernel/samples/bpf/xdp_redirect_cpu_user.c:
https://github.com/torvalds/linux/blob/master/samples/bpf/xdp_redirect_cpu_user.c#L543-L550

This patch addresses all the above use cases. To make uapi stable, it also covers other potential use cases. For bpf syscall subcommands are introduced:
BPF_MAP_LOOKUP_BATCH
BPF_MAP_LOOKUP_AND_DELETE_BATCH
BPF_MAP_UPDATE_BATCH
BPF_MAP_DELETE_BATCH

The UAPI attribute structure looks like:

struct { /* struct used by BPF_MAP_*_BATCH commands */
__u64 batch; /* input/output:
* input: start batch,
* 0 to start from beginning.
* output: next start batch,
* 0 to end batching.
*/
__aligned_u64 keys;
__aligned_u64 values;
__u32 count; /* input/output:
* input: # of elements keys/values.
* output: # of filled elements. */
__u32 map_fd;
__u64 elem_flags;
__u64 flags;
} batch;

An opaque value 'batch' is used for user/kernel space communication for where in the map to start the operation for lookup/lookup_and_delete/delete.
input 'batch' = 0: to start the operation from the beginning of the map. output 'batch': if not 0, the next input for batch operation.

For lookup/lookup_and_delete:
operation: lookup/lookup_and_delete starting from a particular 'batch'. return:

     'batch'       'count'     return code     meaning
      0            0           0               Done. Nothing left
      0            0           -ENOSPC         no space to handle batch 0
      > 0          0           -ENOSPC         no space to handle 'batch'
      > 0          > 0         0               stopped right before 'batch'

Note that:
(1). Even if return code is 0 and return 'count' > 0, the return 'count' may
not be equal to input 'count'. This happens when there is no enough space to handle a batch.
(2). If the return code is an error and not -EFAULT,
'batch' indicates the batch has issues and 'count' indicates the number of elements successfully processed.

For delete:
operation: deletion starting from a particular 'batch'.
return: 0 means everything is deleted from 'batch'.
error code means something deletion not happening.

For update:
operation: update 'count' number of elements in 'keys'/'values'.
return: 0 means successful updates for all elements.
error code, if not -EFAULT, 'count' is the number of successful updates.

---
 include/linux/bpf.h      |   9 ++
 include/uapi/linux/bpf.h |  22 +++
 kernel/bpf/hashtab.c     | 327 +++++++++++++++++++++++++++++++++++++++
 kernel/bpf/syscall.c     |  67 ++++++++
 4 files changed, 425 insertions(+)
include/linux/bpf.h +9 -0
index 7c7f518811a66..66df540ee2473 100644
@@ -39,6 +39,15 @@ struct bpf_map_ops {
 	int (*map_get_next_key)(struct bpf_map *map, void *key, void *next_key);
 	void (*map_release_uref)(struct bpf_map *map);
 	void *(*map_lookup_elem_sys_only)(struct bpf_map *map, void *key);
+	int (*map_lookup_batch)(struct bpf_map *map, const union bpf_attr *attr,
+				union bpf_attr __user *uattr);
+	int (*map_lookup_and_delete_batch)(struct bpf_map *map,
+					   const union bpf_attr *attr,
+					   union bpf_attr __user *uattr);
+	int (*map_update_batch)(struct bpf_map *map, const union bpf_attr *attr,
+				union bpf_attr __user *uattr);
+	int (*map_delete_batch)(struct bpf_map *map, const union bpf_attr *attr,
+				union bpf_attr __user *uattr);
 
 	/* funcs callable from userspace and from eBPF programs */
 	void *(*map_lookup_elem)(struct bpf_map *map, void *key);
include/uapi/linux/bpf.h +22 -0
index df6809a764046..2d647fa6476cb 100644
@@ -107,6 +107,10 @@ enum bpf_cmd {
 	BPF_MAP_LOOKUP_AND_DELETE_ELEM,
 	BPF_MAP_FREEZE,
 	BPF_BTF_GET_NEXT_ID,
+	BPF_MAP_LOOKUP_BATCH,
+	BPF_MAP_LOOKUP_AND_DELETE_BATCH,
+	BPF_MAP_UPDATE_BATCH,
+	BPF_MAP_DELETE_BATCH,
 };
 
 enum bpf_map_type {
@@ -398,6 +402,24 @@ union bpf_attr {
 		__u64		flags;
 	};
 
+	struct { /* struct used by BPF_MAP_*_BATCH commands */
+		__u64		batch;	/* input/output:
+					 * input: start batch,
+					 *        0 to start from beginning.
+					 * output: next start batch,
+					 *         0 to end batching.
+					 */
+		__aligned_u64	keys;
+		__aligned_u64	values;
+		__u32		count;	/* input/output:
+					 * input: # of elements keys/values.
+					 * output: # of filled elements.
+					 */
+		__u32		map_fd;
+		__u64		elem_flags;
+		__u64		flags;
+	} batch;
+
 	struct { /* anonymous struct used by BPF_PROG_LOAD command */
 		__u32		prog_type;	/* one of enum bpf_prog_type */
 		__u32		insn_cnt;
kernel/bpf/hashtab.c +327 -0

345 lines not on this page · raw message

kernel/bpf/syscall.c +67 -0

79 lines not on this page · raw message

Signature · 1 line
2.24.0.432.g9d3f5f5b63-goog
#2 lore raw

RFC 2/3 tools/bpf: test bpf_map_lookup_and_delete_batch()

In reply to Brian Vazquez

From: Yonghong Song <[email protected]>

Added four libbpf API functions to support map batch operations:
. int bpf_map_delete_batch( ... )
. int bpf_map_lookup_batch( ... )
. int bpf_map_lookup_and_delete_batch( ... )
. int bpf_map_update_batch( ... )

Tested bpf_map_lookup_and_delete_batch() and bpf_map_update_batch() functionality.

  $ ./test_maps
  ...
  test_map_lookup_and_delete_batch:PASS
  ...

Note that I clumped uapi header sync patch, libbpf patch and tests patch together considering this is a RFC patch. Will do proper formating once it is out of RFC stage.

---
 tools/include/uapi/linux/bpf.h                |  22 +++
 tools/lib/bpf/bpf.c                           |  59 +++++++
 tools/lib/bpf/bpf.h                           |  13 ++
 tools/lib/bpf/libbpf.map                      |   4 +
 .../map_tests/map_lookup_and_delete_batch.c   | 155 ++++++++++++++++++
 5 files changed, 253 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch.c
tools/include/uapi/linux/bpf.h +22 -0
index df6809a764046..2d647fa6476cb 100644
@@ -107,6 +107,10 @@ enum bpf_cmd {
 	BPF_MAP_LOOKUP_AND_DELETE_ELEM,
 	BPF_MAP_FREEZE,
 	BPF_BTF_GET_NEXT_ID,
+	BPF_MAP_LOOKUP_BATCH,
+	BPF_MAP_LOOKUP_AND_DELETE_BATCH,
+	BPF_MAP_UPDATE_BATCH,
+	BPF_MAP_DELETE_BATCH,
 };
 
 enum bpf_map_type {
@@ -398,6 +402,24 @@ union bpf_attr {
 		__u64		flags;
 	};
 
+	struct { /* struct used by BPF_MAP_*_BATCH commands */
+		__u64		batch;	/* input/output:
+					 * input: start batch,
+					 *        0 to start from beginning.
+					 * output: next start batch,
+					 *         0 to end batching.
+					 */
+		__aligned_u64	keys;
+		__aligned_u64	values;
+		__u32		count;	/* input/output:
+					 * input: # of elements keys/values.
+					 * output: # of filled elements.
+					 */
+		__u32		map_fd;
+		__u64		elem_flags;
+		__u64		flags;
+	} batch;
+
 	struct { /* anonymous struct used by BPF_PROG_LOAD command */
 		__u32		prog_type;	/* one of enum bpf_prog_type */
 		__u32		insn_cnt;
tools/lib/bpf/bpf.c +59 -0

65 lines not on this page · raw message

tools/lib/bpf/bpf.h +13 -0
index 1c53bc5b4b3c7..e61da7a92a414 100644
@@ -123,6 +123,19 @@ LIBBPF_API int bpf_map_lookup_and_delete_elem(int fd, const void *key,
 LIBBPF_API int bpf_map_delete_elem(int fd, const void *key);
 LIBBPF_API int bpf_map_get_next_key(int fd, const void *key, void *next_key);
 LIBBPF_API int bpf_map_freeze(int fd);
+LIBBPF_API int bpf_map_delete_batch(int fd, __u64 *batch, __u32 *count,
+				    __u64 elem_flags, __u64 flags);
+LIBBPF_API int bpf_map_lookup_batch(int fd, __u64 *batch, void *keys,
+				    void *values, __u32 *count,
+				    __u64 elem_flags, __u64 flags);
+LIBBPF_API int bpf_map_lookup_and_delete_batch(int fd, __u64 *batch,
+					       void *keys, void *values,
+					       __u32 *count, __u64 elem_flags,
+					       __u64 flags);
+LIBBPF_API int bpf_map_update_batch(int fd, void *keys, void *values,
+				    __u32 *count, __u64 elem_flags,
+				    __u64 flags);
+
 LIBBPF_API int bpf_obj_pin(int fd, const char *pathname);
 LIBBPF_API int bpf_obj_get(const char *pathname);
 LIBBPF_API int bpf_prog_attach(int prog_fd, int attachable_fd,
tools/lib/bpf/libbpf.map +4 -0
index 86173cbb159d3..0529a770a04eb 100644
@@ -189,6 +189,10 @@ LIBBPF_0.0.4 {
 LIBBPF_0.0.5 {
 	global:
 		bpf_btf_get_next_id;
+		bpf_map_delete_batch;
+		bpf_map_lookup_and_delete_batch;
+		bpf_map_lookup_batch;
+		bpf_map_update_batch;
 } LIBBPF_0.0.4;
 
 LIBBPF_0.0.6 {
tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch.c new file +155 -0

155 lines not on this page · raw message

Signature · 1 line
2.24.0.432.g9d3f5f5b63-goog
#3 lore raw

Re: [RFC bpf-next 2/3] tools/bpf: test bpf_map_lookup_and_delete_batch()

Quoted 22 lines · Brian Vazquez

From: Yonghong Song <[email protected]>

Added four libbpf API functions to support map batch operations:
. int bpf_map_delete_batch( ... )
. int bpf_map_lookup_batch( ... )
. int bpf_map_lookup_and_delete_batch( ... )
. int bpf_map_update_batch( ... )

Tested bpf_map_lookup_and_delete_batch() and bpf_map_update_batch() functionality.

  $ ./test_maps
  ...
  test_map_lookup_and_delete_batch:PASS
  ...

Note that I clumped uapi header sync patch, libbpf patch and tests patch together considering this is a RFC patch. Will do proper formating once it is out of RFC stage.

---

[...]

Quoted 9 lines
tools/include/uapi/linux/bpf.h +8 -0
+       struct { /* struct used by BPF_MAP_*_BATCH commands */
+               __u64           batch;  /* input/output:
+                                        * input: start batch,
+                                        *        0 to start from beginning.
+                                        * output: next start batch,
+                                        *         0 to end batching.
+                                        */
+               __aligned_u64   keys;

tools/include/uapi/linux/bpf.h union bpf_attr { · line 422

Quoted 10 lines
tools/include/uapi/linux/bpf.h +10 -0
+               __aligned_u64   values;
+               __u32           count;  /* input/output:
+                                        * input: # of elements keys/values.
+                                        * output: # of filled elements.
+                                        */
+               __u32           map_fd;
+               __u64           elem_flags;
+               __u64           flags;
+       } batch;
+

Describe what elem_flags and flags are here?

[...]

tools/lib/bpf/bpf.h LIBBPF_API int bpf_map_lookup_and_delete_elem(int fd, const void *key, · line 137

Quoted 12 lines
tools/lib/bpf/bpf.h +12 -0
+LIBBPF_API int bpf_map_delete_batch(int fd, __u64 *batch, __u32 *count,
+                                   __u64 elem_flags, __u64 flags);
+LIBBPF_API int bpf_map_lookup_batch(int fd, __u64 *batch, void *keys,
+                                   void *values, __u32 *count,
+                                   __u64 elem_flags, __u64 flags);
+LIBBPF_API int bpf_map_lookup_and_delete_batch(int fd, __u64 *batch,
+                                              void *keys, void *values,
+                                              __u32 *count, __u64 elem_flags,
+                                              __u64 flags);
+LIBBPF_API int bpf_map_update_batch(int fd, void *keys, void *values,
+                                   __u32 *count, __u64 elem_flags,
+                                   __u64 flags);

Should we start using the same approach as with bpf_object__open_file (see LIBBPF_OPTS), so that we can keep adding extra fields without breaking ABI? The gist is: use function arguments for mandatory fields (as of right now, at least), and put all the optional fields into a xxx_opts struct, which can be NULL. Please see bpf_object__open_{file,mem} for details.

Quoted 9 lines
tools/lib/bpf/bpf.h +1 -0
+
 LIBBPF_API int bpf_obj_pin(int fd, const char *pathname);
 LIBBPF_API int bpf_obj_get(const char *pathname);
 LIBBPF_API int bpf_prog_attach(int prog_fd, int attachable_fd,
tools/lib/bpf/libbpf.map +0 -0
index 86173cbb159d3..0529a770a04eb 100644

tools/lib/bpf/libbpf.map LIBBPF_0.0.4 { · line 196

Quoted 8 lines
tools/lib/bpf/libbpf.map +4 -0
@@ -189,6 +189,10 @@ LIBBPF_0.0.4 {
 LIBBPF_0.0.5 {
        global:
                bpf_btf_get_next_id;
+               bpf_map_delete_batch;
+               bpf_map_lookup_and_delete_batch;
+               bpf_map_lookup_batch;
+               bpf_map_update_batch;
 } LIBBPF_0.0.4;

This should be in 0.0.6 section now.

Quoted 1 line

[...]

#4 lore raw

RFC 3/3 bpf: add generic batch support

In reply to Brian Vazquez

This commits add generic batch support, this coulde b used by data structures that don't have specific constrains or inconsistencies like hashmap. This implementation also allow us to incremenmtally add the support for the remaining data structures keeping less lines of code.

This commit also tests the generic batch operations with pcpu hashmaps and arrays. Note that pcpu hashmaps support was only added in this commit for demonstration purposes and the specific implementation should be used instead.

Cc Yonghong Song <[email protected]>
Cc Stanislav Fomichev <[email protected]>
Cc Petar Penkov <[email protected]>
Cc Willem de Bruijn <[email protected]>
---
 include/linux/bpf.h                           |  12 +
 kernel/bpf/arraymap.c                         |   4 +
 kernel/bpf/hashtab.c                          |   4 +
 kernel/bpf/syscall.c                          | 506 +++++++++++++-----
 .../map_tests/map_lookup_and_delete_batch.c   | 132 ++++-
 .../map_lookup_and_delete_batch_array.c       | 118 ++++
 6 files changed, 635 insertions(+), 141 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch_array.c
include/linux/bpf.h +12 -0
index 66df540ee2473..211f5d04748cc 100644
@@ -700,6 +700,18 @@ void bpf_map_charge_move(struct bpf_map_memory *dst,
 void *bpf_map_area_alloc(size_t size, int numa_node);
 void bpf_map_area_free(void *base);
 void bpf_map_init_from_attr(struct bpf_map *map, union bpf_attr *attr);
+int  generic_map_lookup_batch(struct bpf_map *map,
+			      const union bpf_attr *attr,
+			      union bpf_attr __user *uattr);
+int  generic_map_lookup_and_delete_batch(struct bpf_map *map,
+					 const union bpf_attr *attr,
+					 union bpf_attr __user *uattr);
+int  generic_map_update_batch(struct bpf_map *map,
+			      const union bpf_attr *attr,
+			      union bpf_attr __user *uattr);
+int  generic_map_delete_batch(struct bpf_map *map,
+			      const union bpf_attr *attr,
+			      union bpf_attr __user *uattr);
 
 extern int sysctl_unprivileged_bpf_disabled;
 
kernel/bpf/arraymap.c +4 -0
index 1c65ce0098a95..5afab2c36a3ba 100644
@@ -457,6 +457,10 @@ const struct bpf_map_ops array_map_ops = {
 	.map_direct_value_meta = array_map_direct_value_meta,
 	.map_seq_show_elem = array_map_seq_show_elem,
 	.map_check_btf = array_map_check_btf,
+	.map_lookup_batch = generic_map_lookup_batch,
+	.map_lookup_and_delete_batch = generic_map_lookup_and_delete_batch,
+	.map_update_batch = generic_map_update_batch,
+	.map_delete_batch = generic_map_lookup_batch,
 };
 
 const struct bpf_map_ops percpu_array_map_ops = {
kernel/bpf/hashtab.c +4 -0
index 10977cb321862..d68374b1cd83e 100644
@@ -1695,6 +1695,10 @@ const struct bpf_map_ops htab_percpu_map_ops = {
 	.map_update_elem = htab_percpu_map_update_elem,
 	.map_delete_elem = htab_map_delete_elem,
 	.map_seq_show_elem = htab_percpu_map_seq_show_elem,
+	.map_lookup_batch = generic_map_lookup_batch,
+	.map_lookup_and_delete_batch = generic_map_lookup_and_delete_batch,
+	.map_update_batch = generic_map_update_batch,
+	.map_delete_batch = generic_map_lookup_batch,
 };
 
 const struct bpf_map_ops htab_lru_percpu_map_ops = {
kernel/bpf/syscall.c +386 -120

549 lines not on this page · raw message

tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch.c +111 -21

218 lines not on this page · raw message

tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch_array.c new file +118 -0

118 lines not on this page · raw message

Signature · 1 line
2.24.0.432.g9d3f5f5b63-goog
#5 lore raw
In reply to Brian Vazquez
Quoted 21 lines · Brian Vazquez

This is a follow up in the effort to batch bpf map operations to reduce the syscall overhead with the map_ops. I initially proposed the idea and the discussion is here:
https://lore.kernel.org/bpf/[email protected]/

Yonghong talked at the LPC about this and also proposed and idea that handles the special weird case of hashtables by doing traversing using the buckets as a reference instead of a key. Discussion is here:
https://lore.kernel.org/bpf/[email protected]/

This RFC proposes a way to extend batch operations for more data structures by creating generic batch functions that can be used instead of implementing the operations for each individual data structure, reducing the code that needs to be maintained. The series contains the patches used in Yonghong's RFC and the patch that adds the generic implementation of the operations plus some testing with pcpu hashmaps and arrays. Note that pcpu hashmap shouldn't use the generic implementation and it either should have its own implementation or share the one introduced by Yonghong, I added that just as an example to show that the generic implementation can be easily added to a data structure.

Quoted 4 lines

What I want to achieve with this RFC is to collect early feedback and see if there's any major concern about this before I move forward. I do plan to better separate this into different patches and explain them properly in the commit messages.

Thanks Brian for working on this. The general approach described here is good to me. Having a generic implementation for batch operations looks good for maps (not hash table, queue/stack, etc.)

Quoted 10 lines

Current known issues where I would like to discuss are the followings:

- Because Yonghong's UAPI definition was done specifically for iterating buckets, the batch field is u64 and is treated as an u64 instead of an opaque pointer, this won't work for other data structures that are going to use a key as a batch token with a size greater than
64. Although I think at this point the only key that couldn't be treated as a u64 is the key of a hashmap, and the hashmap won't use the generic interface.

The u64 can be changed with a __aligned_u64 opaque value. This way, it can represent a pointer or a 64bit value.

Quoted 4 lines

- Not all the data structures use delete (because it's not a valid operation) i.e. arrays. So maybe lookup_and_delete_batch command is not needed and we can handle that operation with a lookup_batch and a flag.

This make sense.

Quoted 5 lines

- For delete_batch (not just the lookup_and_delete_batch). Is this operation really needed? If so, shouldn't it be better if the behaviour is delete the keys provided? I did that with my generic implementation but Yonghong's delete_batch for a hashmap deletes buckets.

We need batched delete in bcc. lookup_and_delete_batch is better as it can preserves more new map entries. Alternatively, deleting all entries after lookup is another option. But this may remove more new map entries. Statistically this may or may not matter though.

bcc does have a clear_table (clear_map) API, but not clear who is using it.

So, I did not have a concrete use case for delete_batch yet. I tend to think we should have delete_batch for API completeness, but maybe other people can comment on this as well.

Maybe initial patch, we can skip it. But we should still ensure user interface data structure can handle batch delete if it is needed later. The current data structure should handle this as far as I know.

Quoted 23 lines

Brian Vazquez (1):
bpf: add generic batch support

Yonghong Song (2):
bpf: adding map batch processing support tools/bpf: test bpf_map_lookup_and_delete_batch()

  include/linux/bpf.h                           |  21 +
  include/uapi/linux/bpf.h                      |  22 +
  kernel/bpf/arraymap.c                         |   4 +
  kernel/bpf/hashtab.c                          | 331 ++++++++++
  kernel/bpf/syscall.c                          | 573 ++++++++++++++----
  tools/include/uapi/linux/bpf.h                |  22 +
  tools/lib/bpf/bpf.c                           |  59 ++
  tools/lib/bpf/bpf.h                           |  13 +
  tools/lib/bpf/libbpf.map                      |   4 +
  .../map_tests/map_lookup_and_delete_batch.c   | 245 ++++++++
  .../map_lookup_and_delete_batch_array.c       | 118 ++++
  11 files changed, 1292 insertions(+), 120 deletions(-)

create mode 100644 tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch.c create mode 100644 tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch_array.c

A message that is not in the archive (sent off-list or not yet received): CAMzD94TekSSCCAZD4jZiUpdfMKDqWcwdNf42b_heTGvv1K-=fg@mail.gmail.com

#7 lore raw
Quoted 10 lines · Brian Vazquez

Hi Yonghong,

Thanks for reviewing it! I'm preparing the changes and will submit them sooner.

As for the right way to manage author rights, does anyone know what the correct approach is? Should I use Yonghong's patch and apply the extended support in different patches (i.e. support per_cpu maps, change batch from u64 to __aligned_u64, etc) or it is fine to apply the changes in place and write both sign-offs?

The logic flow of the patch set is most important.
You can add me as co-signoff if you reuse significant portion of my code.

Quoted 128 lines

Thanks,
Brian

On Tue, Nov 12, 2019 at 6:34 PM Yonghong Song <[email protected] <mailto:[email protected]>> wrote:

On 11/7/19 1:20 PM, Brian Vazquez wrote:
> This is a follow up in the effort to batch bpf map operations to
reduce
> the syscall overhead with the map_ops. I initially proposed the
idea and
> the discussion is here:
>
https://lore.kernel.org/bpf/[email protected]/
>
> Yonghong talked at the LPC about this and also proposed and idea that > handles the special weird case of hashtables by doing traversing
using
> the buckets as a reference instead of a key. Discussion is here:
> https://lore.kernel.org/bpf/[email protected]/
>
> This RFC proposes a way to extend batch operations for more data > structures by creating generic batch functions that can be used
instead
> of implementing the operations for each individual data structure, > reducing the code that needs to be maintained. The series
contains the
> patches used in Yonghong's RFC and the patch that adds the generic > implementation of the operations plus some testing with pcpu hashmaps > and arrays. Note that pcpu hashmap shouldn't use the generic > implementation and it either should have its own implementation
or share
> the one introduced by Yonghong, I added that just as an example
to show
> that the generic implementation can be easily added to a data
structure.
>
> What I want to achieve with this RFC is to collect early feedback
and see if
> there's any major concern about this before I move forward. I do plan > to better separate this into different patches and explain them
properly
> in the commit messages.

Thanks Brian for working on this. The general approach described here is good to me. Having a generic implementation for batch operations looks good for maps (not hash table, queue/stack, etc.)

>
> Current known issues where I would like to discuss are the
followings:
>
> - Because Yonghong's UAPI definition was done specifically for >    iterating buckets, the batch field is u64 and is treated as an u64 >    instead of an opaque pointer, this won't work for other data
structures
>    that are going to use a key as a batch token with a size
greater than
>    64. Although I think at this point the only key that couldn't be >    treated as a u64 is the key of a hashmap, and the hashmap
won't use
>    the generic interface.

The u64 can be changed with a __aligned_u64 opaque value. This way, it can represent a pointer or a 64bit value.

> - Not all the data structures use delete (because it's not a valid >    operation) i.e. arrays. So maybe lookup_and_delete_batch
command is
>    not needed and we can handle that operation with a
lookup_batch and a
>    flag.

This make sense.

> - For delete_batch (not just the lookup_and_delete_batch). Is this >    operation really needed? If so, shouldn't it be better if the >    behaviour is delete the keys provided? I did that with my generic >    implementation but Yonghong's delete_batch for a hashmap deletes >    buckets.

We need batched delete in bcc. lookup_and_delete_batch is better as it can preserves more new map entries. Alternatively, deleting all entries after lookup is another option. But this may remove more new map entries. Statistically this may or may not matter though.

bcc does have a clear_table (clear_map) API, but not clear who is using it.

So, I did not have a concrete use case for delete_batch yet. I tend to think we should have delete_batch for API completeness, but maybe other people can comment on this as well.

Maybe initial patch, we can skip it. But we should still ensure user interface data structure can handle batch delete if it is needed later. The current data structure should handle this as far as I know.

>
> Brian Vazquez (1):
>    bpf: add generic batch support
>
> Yonghong Song (2):
>    bpf: adding map batch processing support
>    tools/bpf: test bpf_map_lookup_and_delete_batch()
>
>   include/linux/bpf.h                           |  21 +
>   include/uapi/linux/bpf.h                      |  22 +
>   kernel/bpf/arraymap.c                         |   4 +
>   kernel/bpf/hashtab.c                          | 331 ++++++++++ >   kernel/bpf/syscall.c                          | 573
++++++++++++++----
>   tools/include/uapi/linux/bpf.h                |  22 +
>   tools/lib/bpf/bpf.c                           |  59 ++
>   tools/lib/bpf/bpf.h                           |  13 +
>   tools/lib/bpf/libbpf.map                      |   4 +
>   .../map_tests/map_lookup_and_delete_batch.c   | 245 ++++++++ >   .../map_lookup_and_delete_batch_array.c       | 118 ++++ >   11 files changed, 1292 insertions(+), 120 deletions(-)
>   create mode 100644
tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch.c
>   create mode 100644
tools/testing/selftests/bpf/map_tests/map_lookup_and_delete_batch_array.c
>