Hou Tao <houtao@xxxxxxxxxxxxxxx> writes:
> From: Hou Tao <houtao1@xxxxxxxxxx>
>
> trie_get_next_key() uses node->prefixlen == key->prefixlen to identify
> an exact match, However, it is incorrect because when the target key
> doesn't fully match the found node (e.g., node->prefixlen != matchlen),
> these two nodes may also have the same prefixlen. It will return
> expected result when the passed key exist in the trie. However when a
> recently-deleted key or nonexistent key is passed to
> trie_get_next_key(), it may skip keys and return incorrect result.
>
> Fix it by using node->prefixlen == matchlen to identify exact matches.
> When the condition is true after the search, it also implies
> node->prefixlen equals key->prefixlen, otherwise, the search would
> return NULL instead.
>
> Fixes: b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map")
> Signed-off-by: Hou Tao <houtao1@xxxxxxxxxx>
Reviewed-by: Toke Høiland-Jørgensen <toke@xxxxxxxxxx>
