Skip to content

Commit 8fe4592

Browse files
palmtenordavem330
palmtenor
authored and
davem330
committed
bpf: map_get_next_key to return first key on NULL
When iterating through a map, we need to find a key that does not exist in the map so map_get_next_key will give us the first key of the map. This often requires a lot of guessing in production systems. This patch makes map_get_next_key return the first key when the key pointer in the parameter is NULL. Signed-off-by: Teng Qin <qinteng@fb.com> Signed-off-by: Alexei Starovoitov <ast@kernel.org> Acked-by: Daniel Borkmann <daniel@iogearbox.net> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent 472ecf0 commit 8fe4592

5 files changed

Lines changed: 50 additions & 20 deletions

File tree

‎include/trace/events/bpf.h‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -321,11 +321,14 @@ TRACE_EVENT(bpf_map_next_key,
321321
__dynamic_array(u8, key, map->key_size)
322322
__dynamic_array(u8, nxt, map->key_size)
323323
__field(bool, key_trunc)
324+
__field(bool, key_null)
324325
__field(int, ufd)
325326
),
326327

327328
TP_fast_assign(
328-
memcpy(__get_dynamic_array(key), key, map->key_size);
329+
if (key)
330+
memcpy(__get_dynamic_array(key), key, map->key_size);
331+
__entry->key_null = !key;
329332
memcpy(__get_dynamic_array(nxt), key_next, map->key_size);
330333
__entry->type = map->map_type;
331334
__entry->key_len = min(map->key_size, 16U);
@@ -336,8 +339,9 @@ TRACE_EVENT(bpf_map_next_key,
336339
TP_printk("map type=%s ufd=%d key=[%s%s] next=[%s%s]",
337340
__print_symbolic(__entry->type, __MAP_TYPE_SYM_TAB),
338341
__entry->ufd,
339-
__print_hex(__get_dynamic_array(key), __entry->key_len),
340-
__entry->key_trunc ? " ..." : "",
342+
__entry->key_null ? "NULL" : __print_hex(__get_dynamic_array(key),
343+
__entry->key_len),
344+
__entry->key_trunc && !__entry->key_null ? " ..." : "",
341345
__print_hex(__get_dynamic_array(nxt), __entry->key_len),
342346
__entry->key_trunc ? " ..." : "")
343347
);

‎kernel/bpf/arraymap.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -182,7 +182,7 @@ int bpf_percpu_array_copy(struct bpf_map *map, void *key, void *value)
182182
static int array_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
183183
{
184184
struct bpf_array *array = container_of(map, struct bpf_array, map);
185-
u32 index = *(u32 *)key;
185+
u32 index = key ? *(u32 *)key : U32_MAX;
186186
u32 *next = (u32 *)next_key;
187187

188188
if (index >= array->map.max_entries) {

‎kernel/bpf/hashtab.c‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -540,23 +540,24 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
540540
struct hlist_nulls_head *head;
541541
struct htab_elem *l, *next_l;
542542
u32 hash, key_size;
543-
int i;
543+
int i = 0;
544544

545545
WARN_ON_ONCE(!rcu_read_lock_held());
546546

547547
key_size = map->key_size;
548548

549+
if (!key)
550+
goto find_first_elem;
551+
549552
hash = htab_map_hash(key, key_size);
550553

551554
head = select_bucket(htab, hash);
552555

553556
/* lookup the key */
554557
l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
555558

556-
if (!l) {
557-
i = 0;
559+
if (!l)
558560
goto find_first_elem;
559-
}
560561

561562
/* key was found, get next key in the same bucket */
562563
next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)),

‎kernel/bpf/syscall.c‎

Lines changed: 12 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -536,14 +536,18 @@ static int map_get_next_key(union bpf_attr *attr)
536536
if (IS_ERR(map))
537537
return PTR_ERR(map);
538538

539-
err = -ENOMEM;
540-
key = kmalloc(map->key_size, GFP_USER);
541-
if (!key)
542-
goto err_put;
543-
544-
err = -EFAULT;
545-
if (copy_from_user(key, ukey, map->key_size) != 0)
546-
goto free_key;
539+
if (ukey) {
540+
err = -ENOMEM;
541+
key = kmalloc(map->key_size, GFP_USER);
542+
if (!key)
543+
goto err_put;
544+
545+
err = -EFAULT;
546+
if (copy_from_user(key, ukey, map->key_size) != 0)
547+
goto free_key;
548+
} else {
549+
key = NULL;
550+
}
547551

548552
err = -ENOMEM;
549553
next_key = kmalloc(map->key_size, GFP_USER);

‎tools/testing/selftests/bpf/test_maps.c‎

Lines changed: 25 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ static int map_flags;
2828

2929
static void test_hashmap(int task, void *data)
3030
{
31-
long long key, next_key, value;
31+
long long key, next_key, first_key, value;
3232
int fd;
3333

3434
fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
@@ -89,10 +89,13 @@ static void test_hashmap(int task, void *data)
8989
assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
9090

9191
/* Iterate over two elements. */
92+
assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
93+
(first_key == 1 || first_key == 2));
9294
assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
93-
(next_key == 1 || next_key == 2));
95+
(next_key == first_key));
9496
assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
95-
(next_key == 1 || next_key == 2));
97+
(next_key == 1 || next_key == 2) &&
98+
(next_key != first_key));
9699
assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
97100
errno == ENOENT);
98101

@@ -105,6 +108,8 @@ static void test_hashmap(int task, void *data)
105108

106109
key = 0;
107110
/* Check that map is empty. */
111+
assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
112+
errno == ENOENT);
108113
assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
109114
errno == ENOENT);
110115

@@ -133,7 +138,7 @@ static void test_hashmap_percpu(int task, void *data)
133138
{
134139
unsigned int nr_cpus = bpf_num_possible_cpus();
135140
long long value[nr_cpus];
136-
long long key, next_key;
141+
long long key, next_key, first_key;
137142
int expected_key_mask = 0;
138143
int fd, i;
139144

@@ -193,7 +198,13 @@ static void test_hashmap_percpu(int task, void *data)
193198
assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
194199

195200
/* Iterate over two elements. */
201+
assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
202+
((expected_key_mask & first_key) == first_key));
196203
while (!bpf_map_get_next_key(fd, &key, &next_key)) {
204+
if (first_key) {
205+
assert(next_key == first_key);
206+
first_key = 0;
207+
}
197208
assert((expected_key_mask & next_key) == next_key);
198209
expected_key_mask &= ~next_key;
199210

@@ -219,6 +230,8 @@ static void test_hashmap_percpu(int task, void *data)
219230

220231
key = 0;
221232
/* Check that map is empty. */
233+
assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
234+
errno == ENOENT);
222235
assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
223236
errno == ENOENT);
224237

@@ -264,6 +277,8 @@ static void test_arraymap(int task, void *data)
264277
assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
265278

266279
/* Iterate over two elements. */
280+
assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
281+
next_key == 0);
267282
assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
268283
next_key == 0);
269284
assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
@@ -319,6 +334,8 @@ static void test_arraymap_percpu(int task, void *data)
319334
assert(bpf_map_lookup_elem(fd, &key, values) == -1 && errno == ENOENT);
320335

321336
/* Iterate over two elements. */
337+
assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
338+
next_key == 0);
322339
assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
323340
next_key == 0);
324341
assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
@@ -400,6 +417,8 @@ static void test_map_large(void)
400417
errno == E2BIG);
401418

402419
/* Iterate through all elements. */
420+
assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
421+
key.c = -1;
403422
for (i = 0; i < MAP_SIZE; i++)
404423
assert(bpf_map_get_next_key(fd, &key, &key) == 0);
405424
assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
@@ -499,6 +518,7 @@ static void test_map_parallel(void)
499518
errno == EEXIST);
500519

501520
/* Check that all elements were inserted. */
521+
assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
502522
key = -1;
503523
for (i = 0; i < MAP_SIZE; i++)
504524
assert(bpf_map_get_next_key(fd, &key, &key) == 0);
@@ -518,6 +538,7 @@ static void test_map_parallel(void)
518538

519539
/* Nothing should be left. */
520540
key = -1;
541+
assert(bpf_map_get_next_key(fd, NULL, &key) == -1 && errno == ENOENT);
521542
assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
522543
}
523544

0 commit comments

Comments
 (0)