Re: [PATCH bpf-next v1] Document BPF_MAP_TYPE_LPM_TRIE

[Donald Hunter <donald.hunter@gmail.com>]

John Fastabend <john.fastabend@gmail.com> writes:

> Donald Hunter wrote:
>> +
>> +Usage
>> +=====
>> +
>> +Kernel BPF
>> +----------
>> +
>> +.. c:function::
>> +   void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
>> +
>> +The longest prefix entry for a given data value can be found using the
>> +``bpf_map_lookup_elem()`` helper. This helper returns a pointer to the
>> +value associated with the longest matching ``key``, or ``NULL`` if no
>> +entry was found.
>> +
>> +The ``key`` should have ``prefixlen`` set to ``max_prefixlen`` when
>> +performing longest prefix lookups. For example, when searching for the
>> +longest prefix match for an IPv4 address, ``prefixlen`` should be set to
>> +``32``.
>> +
>> +.. c:function::
>> +   long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)
>> +
>> +Prefix entries can be added or updated using the ``bpf_map_update_elem()``
>> +helper. This helper replaces existing elements atomically.
>> +
>> +``bpf_map_update_elem()`` returns ``0`` on success, or negative error in
>> +case of failure.
>> +
>> + .. note::
>> +    The flags parameter must be one of BPF_ANY, BPF_NOEXIST or BPF_EXIST,
>> +    but the value is ignored, giving BPF_ANY semantics.
>> +
>> +.. c:function::
>> +   long bpf_map_delete_elem(struct bpf_map *map, const void *key)
>> +
>> +Prefix entries can be deleted using the ``bpf_map_delete_elem()``
>> +helper. This helper will return 0 on success, or negative error in case
>> +of failure.
>
> The map ops lookup, update, delete and below userspace are pretty generic to
> all map types. How about moving those into a generic file about maps? Maybe
> ./Documentation/bpf/mpas.rst? Then perhaps there is a way to link to
> them from here.

For the map types I have looked at so far, there has been a bit of
variation in semantics. E.g. array has u32 key does not support delete
and only supports update with BPF_EXIST/ANY, lpm_trie has custom keys
and specific lookup and iteration semantics. Hash has the most generic
semantics for get, lookup, update and delete. I am happy to add some
generic documentation about the ops in ./Documentation/bpf/maps.rst but
I think it will still be necessary to have specific documentation for
each map type where the op behaviour deviates. I'd prefer to keep the
map specific pages self-contained enough that a reader gets a clear view
of behaviour for both kernel BPF and userspace all in one place.

>> +
>> +Userspace
>> +---------
>> +
>> +Access from userspace uses libbpf APIs with the same names as above, with
>> +the map identified by ``fd``.
>> +
>> +.. c:function::
>> +   int bpf_map_get_next_key (int fd, const void *cur_key, void *next_key)
>> +
>> +A userspace program can iterate through the entries in an LPM trie using
>> +libbpf's ``bpf_map_get_next_key()`` function. The first key can be
>> +fetched by calling ``bpf_map_get_next_key()`` with ``cur_key`` set to
>> +``NULL``. Subsequent calls will fetch the next key that follows the
>> +current key. ``bpf_map_get_next_key()`` returns ``0`` on success,
>> +``-ENOENT`` if cur_key is the last key in the hash, or negative error in
>> +case of failure.
>> +
>> +``bpf_map_get_next_key()`` will iterate through the LPM trie elements
>> +from leftmost leaf first. This means that iteration will return more
>> +specific keys before less specific ones.
>
> So I tihnk none of this is specific to LPM tries.
>
>> +
>> +Examples
>> +========
>> +
>> +Please see ``tools/samples/bpf/xdp_router_ipv4_user.c`` and
>
> I wouldn't link to samples. Can we link to a selftest? Maybe move the
> xdp_router_ipv4_user into a selftest otherwise no one ensures it is
> always working.

I will look for a suitable selftest that I can link to.

>> +``xdp_router_ipv4.bpf.c`` for a functional example. The code snippets
>> +below demonstrates API usage.
>> +
>> +Kernel BPF
>> +----------
>
> rest lgtm. Thanks for working on docs.