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

[Daniel Borkmann <daniel@iogearbox.net>]

Hi Daniel,

On 01/05/2017 09:04 PM, Daniel Mack wrote:
> On 01/05/2017 05:25 PM, Daniel Borkmann wrote:
>> On 12/29/2016 06:28 PM, Daniel Mack wrote:
>
>>> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
>>> new file mode 100644
>>> index 0000000..8b6a61d
>>> --- /dev/null
>>> +++ b/kernel/bpf/lpm_trie.c
>
> [..]
>
>>> +static struct bpf_map *trie_alloc(union bpf_attr *attr)
>>> +{
>>> +	struct lpm_trie *trie;
>>> +
>>> +	/* check sanity of attributes */
>>> +	if (attr->max_entries == 0 || attr->map_flags ||
>>> +	    attr->key_size < sizeof(struct bpf_lpm_trie_key) + 1   ||
>>> +	    attr->key_size > sizeof(struct bpf_lpm_trie_key) + 256 ||
>>> +	    attr->value_size != sizeof(u64))
>>> +		return ERR_PTR(-EINVAL);
>>
>> The correct attr->map_flags test here would need to be ...
>>
>>     attr->map_flags != BPF_F_NO_PREALLOC
>>
>> ... since in this case we don't have any prealloc pool, and
>> should that come one day that test could be relaxed again.
>>
>>> +	trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN);
>>> +	if (!trie)
>>> +		return NULL;
>>> +
>>> +	/* copy mandatory map attributes */
>>> +	trie->map.map_type = attr->map_type;
>>> +	trie->map.key_size = attr->key_size;
>>> +	trie->map.value_size = attr->value_size;
>>> +	trie->map.max_entries = attr->max_entries;
>>
>> You also need to fill in trie->map.pages as that is eventually
>> used to charge memory against in bpf_map_charge_memlock(), right
>> now that would remain as 0 meaning the map is not accounted for.
>
> Hmm, okay. The nodes are, however, allocated dynamically at runtime in
> this case. That means that we have trie->map.pages on each allocation,
> right?

The current scheme (f.e. htab_map_alloc() has some details, although
probably not too obvious) that was done charges worst-case cost up front,
so it would be in trie_alloc() where you fill map.pages and map_create()
will later account for them.

Thanks,
Daniel