Patch "netfilter: nft_set_rbtree: bogus lookup/get on consecutive elements in named sets" has been added to the 5.4-stable tree

[Sasha Levin <sashal@xxxxxxxxxx>]

This is a note to let you know that I've just added the patch titled

    netfilter: nft_set_rbtree: bogus lookup/get on consecutive elements in named sets

to the 5.4-stable tree which can be found at:
    http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
     netfilter-nft_set_rbtree-bogus-lookup-get-on-consecu.patch
and it can be found in the queue-5.4 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree,
please let <stable@xxxxxxxxxxxxxxx> know about it.



commit b49a426ba57795b0220b371f4572edcf98e4afac
Author: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>
Date:   Fri Dec 6 20:23:29 2019 +0100

    netfilter: nft_set_rbtree: bogus lookup/get on consecutive elements in named sets
    
    [ Upstream commit db3b665dd77b34e34df00e17d7b299c98fcfb2c5 ]
    
    The existing rbtree implementation might store consecutive elements
    where the closing element and the opening element might overlap, eg.
    
            [ a, a+1) [ a+1, a+2)
    
    This patch removes the optimization for non-anonymous sets in the exact
    matching case, where it is assumed to stop searching in case that the
    closing element is found. Instead, invalidate candidate interval and
    keep looking further in the tree.
    
    The lookup/get operation might return false, while there is an element
    in the rbtree. Moreover, the get operation returns true as if a+2 would
    be in the tree. This happens with named sets after several set updates.
    
    The existing lookup optimization (that only works for the anonymous
    sets) might not reach the opening [ a+1,... element if the closing
    ...,a+1) is found in first place when walking over the rbtree. Hence,
    walking the full tree in that case is needed.
    
    This patch fixes the lookup and get operations.
    
    Fixes: e701001e7cbe ("netfilter: nft_rbtree: allow adjacent intervals with dynamic updates")
    Fixes: ba0e4d9917b4 ("netfilter: nf_tables: get set elements via netlink")
    Signed-off-by: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>
    Signed-off-by: Sasha Levin <sashal@xxxxxxxxxx>

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 57123259452f..a9f804f7a04a 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -74,8 +74,13 @@ static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *set
 				parent = rcu_dereference_raw(parent->rb_left);
 				continue;
 			}
-			if (nft_rbtree_interval_end(rbe))
-				goto out;
+			if (nft_rbtree_interval_end(rbe)) {
+				if (nft_set_is_anonymous(set))
+					return false;
+				parent = rcu_dereference_raw(parent->rb_left);
+				interval = NULL;
+				continue;
+			}
 
 			*ext = &rbe->ext;
 			return true;
@@ -88,7 +93,7 @@ static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *set
 		*ext = &interval->ext;
 		return true;
 	}
-out:
+
 	return false;
 }
 
@@ -139,8 +144,10 @@ static bool __nft_rbtree_get(const struct net *net, const struct nft_set *set,
 			if (flags & NFT_SET_ELEM_INTERVAL_END)
 				interval = rbe;
 		} else {
-			if (!nft_set_elem_active(&rbe->ext, genmask))
+			if (!nft_set_elem_active(&rbe->ext, genmask)) {
 				parent = rcu_dereference_raw(parent->rb_left);
+				continue;
+			}
 
 			if (!nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) ||
 			    (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END) ==
@@ -148,7 +155,11 @@ static bool __nft_rbtree_get(const struct net *net, const struct nft_set *set,
 				*elem = rbe;
 				return true;
 			}
-			return false;
+
+			if (nft_rbtree_interval_end(rbe))
+				interval = NULL;
+
+			parent = rcu_dereference_raw(parent->rb_left);
 		}
 	}