lkml.org 
[lkml]   [2019]   [Mar]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH] bpf: do not start from first bucket if elem is not found on a htab
    Date
    From: Brian Vazquez <brianvv@google.com>

    When you want to traverse an entire map using BPF_MAP_GET_NEXT_KEY and
    key provided is not present due to a deletion you will start iterating the
    map from the beginning without noticing it. This patch changes the
    starting bucket in those situations to the bucket where key was
    suppossed to be.

    Note that you can still get stuck in the same bucket but it is less
    likely than getting stuck in a loop restarting from the beginning of
    the entire map.

    Signed-off-by: Brian Vazquez <brianvv@google.com>
    Signed-off-by: Maciej Żenczykowski <maze@google.com>
    ---
    kernel/bpf/hashtab.c | 6 ++++--
    1 file changed, 4 insertions(+), 2 deletions(-)

    diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
    index fed15cf94dca6..eea046d269f51 100644
    --- a/kernel/bpf/hashtab.c
    +++ b/kernel/bpf/hashtab.c
    @@ -611,11 +611,14 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)

    hash = htab_map_hash(key, key_size, htab->hashrnd);

    - head = select_bucket(htab, hash);
    + /* keep track of current bucket */
    + i = hash & (htab->n_buckets - 1);
    + head = select_bucket(htab, i);

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

    + /* this will start looking from bucket i */
    if (!l)
    goto find_first_elem;

    @@ -630,7 +633,6 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
    }

    /* no more elements in this hash list, go to the next bucket */
    - i = hash & (htab->n_buckets - 1);
    i++;

    find_first_elem:
    --
    2.21.0.392.gf8f6787159e-goog
    \
     
     \ /
      Last update: 2019-03-31 08:44    [W:6.525 / U:0.372 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site