Re: [PATCH v3 1/2] bpf: add a longest prefix match trie map implementation

[Alexei Starovoitov]

On 1/14/17 4:17 AM, Daniel Mack wrote:

+static struct bpf_map *trie_alloc(union bpf_attr *attr)
+{
+       size_t cost, cost_per_node;
+       struct lpm_trie *trie;
+       int ret;
+
+       /* check sanity of attributes */
+       if (attr->max_entries == 0 ||
+           attr->map_flags != BPF_F_NO_PREALLOC ||
+           attr->key_size < sizeof(struct bpf_lpm_trie_key) + 1   ||
+           attr->key_size > sizeof(struct bpf_lpm_trie_key) + 256 ||
+           attr->value_size == 0)
+               return ERR_PTR(-EINVAL);

could you also make it root only for now ?
Like we did for lru map:
        if (lru && !capable(CAP_SYS_ADMIN))
                /* LRU implementation is much complicated than other
                 * maps.  Hence, limit to CAP_SYS_ADMIN for now.
                 */
                return ERR_PTR(-EPERM);

trie is not that complicated, but I think socket_filters
(the only unpriv prog type today) can live a release or
two without ability to use it.

In patch 2/2 there are some comments not in networking style:
+       /*
+        * Perform longest prefix-match on @key/@n_bits. That is,

As far as performance it has to be measured from datapath.
Like create tc+cls_bpf prog that does a dozen of trie lookups,
attach it to veth or tap and use
samples/pktgen/pktgen_bench_xmit_mode_netif_receive.sh
to send traffic into it.
Like: samples/bpf/test_cls_bpf.sh does.

Another alternative is to extend samples/bpf/map_perf_test
It has perf tests for most map types today (including lru)
and trie would be natural addition there.
I would prefer this latter option.

Thanks!