[PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[Liping Zhang]

From: Liping Zhang <zlpnobody@gmail.com>

Currently we just assume the element key as a u32 integer, regardless of
the set key length.

This is incorrect, for example, the tcp port number is only 16 bits.
So when we use the nft_payload expr to get the tcp dport and store
it to dreg, the dport will be stored at 0~15 bits, and 16~31 bits
will be padded with zero.

So the reg->data[dreg] will be looked like as below:
  0          15           31
  +-+-+-+-+-+-+-+-+-+-+-+-+
  | tcp dport |      0    |
  +-+-+-+-+-+-+-+-+-+-+-+-+
But for these big-endian systems, if we treate this register as a u32
integer, the element key will be larger than 65535, so the following
lookup in bitmap set will cause out of bound access.

Another issue is that if we add element with comments in bitmap
set(although the comments will be ignored eventually), the element will
vanish strangely. Because we treate the element key as a u32 integer, so
the comments will become the part of the element key, then the element
key will also be larger than 65535 and out of bound access will happen:
  # nft add element t s { 1 comment test }

Since set->klen is 1 or 2, it's fine to treate the element key as a u8 or
u16 integer.

Fixes: 665153ff5752 ("netfilter: nf_tables: add bitmap set type")
Signed-off-by: Liping Zhang <zlpnobody@gmail.com>
---
 net/netfilter/nft_set_bitmap.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)

diff --git a/net/netfilter/nft_set_bitmap.c b/net/netfilter/nft_set_bitmap.c
index 152d226..9b024e2 100644
--- a/net/netfilter/nft_set_bitmap.c
+++ b/net/netfilter/nft_set_bitmap.c
@@ -45,9 +45,17 @@ struct nft_bitmap {
 	u8	bitmap[];
 };
 
-static inline void nft_bitmap_location(u32 key, u32 *idx, u32 *off)
+static inline void nft_bitmap_location(const struct nft_set *set,
+				       const void *key,
+				       u32 *idx, u32 *off)
 {
-	u32 k = (key << 1);
+	u32 k;
+
+	if (set->klen == 2)
+		k = *(u16 *)key;
+	else
+		k = *(u8 *)key;
+	k <<= 1;
 
 	*idx = k / BITS_PER_BYTE;
 	*off = k % BITS_PER_BYTE;
@@ -69,7 +77,7 @@ static bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
 	u8 genmask = nft_genmask_cur(net);
 	u32 idx, off;
 
-	nft_bitmap_location(*key, &idx, &off);
+	nft_bitmap_location(set, key, &idx, &off);
 
 	return nft_bitmap_active(priv->bitmap, idx, off, genmask);
 }
@@ -83,7 +91,7 @@ static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
 	u8 genmask = nft_genmask_next(net);
 	u32 idx, off;
 
-	nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
+	nft_bitmap_location(set, nft_set_ext_key(ext), &idx, &off);
 	if (nft_bitmap_active(priv->bitmap, idx, off, genmask))
 		return -EEXIST;
 
@@ -102,7 +110,7 @@ static void nft_bitmap_remove(const struct net *net,
 	u8 genmask = nft_genmask_next(net);
 	u32 idx, off;
 
-	nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
+	nft_bitmap_location(set, nft_set_ext_key(ext), &idx, &off);
 	/* Enter 00 state. */
 	priv->bitmap[idx] &= ~(genmask << off);
 }
@@ -116,7 +124,7 @@ static void nft_bitmap_activate(const struct net *net,
 	u8 genmask = nft_genmask_next(net);
 	u32 idx, off;
 
-	nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
+	nft_bitmap_location(set, nft_set_ext_key(ext), &idx, &off);
 	/* Enter 11 state. */
 	priv->bitmap[idx] |= (genmask << off);
 }
@@ -128,7 +136,7 @@ static bool nft_bitmap_flush(const struct net *net,
 	u8 genmask = nft_genmask_next(net);
 	u32 idx, off;
 
-	nft_bitmap_location(nft_set_ext_key(ext)->data[0], &idx, &off);
+	nft_bitmap_location(set, nft_set_ext_key(ext), &idx, &off);
 	/* Enter 10 state, similar to deactivation. */
 	priv->bitmap[idx] &= ~(genmask << off);
 
@@ -161,10 +169,9 @@ static void *nft_bitmap_deactivate(const struct net *net,
 	struct nft_bitmap *priv = nft_set_priv(set);
 	u8 genmask = nft_genmask_next(net);
 	struct nft_set_ext *ext;
-	u32 idx, off, key = 0;
+	u32 idx, off;
 
-	memcpy(&key, elem->key.val.data, set->klen);
-	nft_bitmap_location(key, &idx, &off);
+	nft_bitmap_location(set, elem->key.val.data, &idx, &off);
 
 	if (!nft_bitmap_active(priv->bitmap, idx, off, genmask))
 		return NULL;
-- 
2.5.5

[PATCH nf 2/2] netfilter: nft_set_bitmap: fix memory leak

[Liping Zhang]

From: Liping Zhang <zlpnobody@gmail.com>

Unlike other set types, we will not link struct nft_set_ext into our
internal structure, so we need to free it after activation, otherwise
the nft_set_ext's memory will be leaked forever.

Also move nf_tables_setelem_notify() to the front of ops->activate, so
we will not hit the use after free error.

Fixes: 665153ff5752 ("netfilter: nf_tables: add bitmap set type")
Signed-off-by: Liping Zhang <zlpnobody@gmail.com>
---
 net/netfilter/nf_tables_api.c  | 2 +-
 net/netfilter/nft_set_bitmap.c | 5 +++++
 2 files changed, 6 insertions(+), 1 deletion(-)

diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c
index 5e0ccfd..5b949e0 100644
--- a/net/netfilter/nf_tables_api.c
+++ b/net/netfilter/nf_tables_api.c
@@ -4809,10 +4809,10 @@ static int nf_tables_commit(struct net *net, struct sk_buff *skb)
 		case NFT_MSG_NEWSETELEM:
 			te = (struct nft_trans_elem *)trans->data;
 
-			te->set->ops->activate(net, te->set, &te->elem);
 			nf_tables_setelem_notify(&trans->ctx, te->set,
 						 &te->elem,
 						 NFT_MSG_NEWSETELEM, 0);
+			te->set->ops->activate(net, te->set, &te->elem);
 			nft_trans_destroy(trans);
 			break;
 		case NFT_MSG_DELSETELEM:
diff --git a/net/netfilter/nft_set_bitmap.c b/net/netfilter/nft_set_bitmap.c
index 9b024e2..dfaf299 100644
--- a/net/netfilter/nft_set_bitmap.c
+++ b/net/netfilter/nft_set_bitmap.c
@@ -127,6 +127,11 @@ static void nft_bitmap_activate(const struct net *net,
 	nft_bitmap_location(set, nft_set_ext_key(ext), &idx, &off);
 	/* Enter 11 state. */
 	priv->bitmap[idx] |= (genmask << off);
+
+	/* After the element is active in the bitmap, the dummy extension
+	 * object is not used anymore, free it now.
+	 */
+	nft_set_elem_destroy(set, ext, true);
 }
 
 static bool nft_bitmap_flush(const struct net *net,
-- 
2.5.5

Re: [PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[Pablo Neira Ayuso]

On Mon, Mar 06, 2017 at 12:02:52AM +0800, Liping Zhang wrote:
> From: Liping Zhang <zlpnobody@gmail.com>
> 
> Currently we just assume the element key as a u32 integer, regardless of
> the set key length.
> 
> This is incorrect, for example, the tcp port number is only 16 bits.
> So when we use the nft_payload expr to get the tcp dport and store
> it to dreg, the dport will be stored at 0~15 bits, and 16~31 bits
> will be padded with zero.
> 
> So the reg->data[dreg] will be looked like as below:
>   0          15           31
>   +-+-+-+-+-+-+-+-+-+-+-+-+
>   | tcp dport |      0    |
>   +-+-+-+-+-+-+-+-+-+-+-+-+
> But for these big-endian systems, if we treate this register as a u32
> integer, the element key will be larger than 65535, so the following
> lookup in bitmap set will cause out of bound access.
> 
> Another issue is that if we add element with comments in bitmap
> set(although the comments will be ignored eventually), the element will
> vanish strangely. Because we treate the element key as a u32 integer, so
> the comments will become the part of the element key, then the element
> key will also be larger than 65535 and out of bound access will happen:
>   # nft add element t s { 1 comment test }

Right, the userdata case is not handled properly. And in this case we
have no specific flag at set creation, so element comments may come
without previous notice via set flags.

I think we have to keep a list of dummy nft_set_ext that is only used
in the dump path, we can simplify this logic at the cost of increasing
memory consumption. Another alternative is to keep around a structure
to store only the set element userdata that we need for comments.

Let me think.

Your patches look good to me. Probably we can skip 2/2 if we introduce
the dummy nft_set_ext list, and remove the ->flush field for
nft_set_iter.

Thanks.

Re: [PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[Liping Zhang]

Hi Pablo,

2017-03-06 20:01 GMT+08:00 Pablo Neira Ayuso <pablo@netfilter.org>:
[...]
> Right, the userdata case is not handled properly. And in this case we
> have no specific flag at set creation, so element comments may come
> without previous notice via set flags.
>
> I think we have to keep a list of dummy nft_set_ext that is only used
> in the dump path, we can simplify this logic at the cost of increasing
> memory consumption. Another alternative is to keep around a structure
> to store only the set element userdata that we need for comments.
>
> Let me think.
>
> Your patches look good to me. Probably we can skip 2/2 if we introduce
> the dummy nft_set_ext list, and remove the ->flush field for
> nft_set_iter.
>

Actually I was preparing to send v2 about this patch, then I saw your
reply:). Because I find out that in nft_bitmap_walk(), the 'key' maybe
incorrect on the big-endian machines when the key length is 1.
So the patch diff looks like this:

static void nft_bitmap_walk(...)
                        key = ((idx * BITS_PER_BYTE) + off) >> 1;
-                       memcpy(nft_set_ext_key(ext), &key, set->klen);
+                       if (set->klen == 2)
+                               *(u16 *)nft_set_ext_key(ext) = key;
+                       else
+                               *(u8 *)nft_set_ext_key(ext) = key;

But if we will introduce the dummy nft_set_ext list to the whole elements
in the bitmap, the above part is not needed anymore, i.e. we need not to
convert the bit to key.

(Now start the second part, about the byte-order in nft)
Unrelated to this patch actually, I find that there's a little messy when we
store the u8 or u16 integer to the register, which may cause miss-match in
big-endian machines (Actually I have no big-endian machine around me,
so I can't verify it).

For example, dest pointer is declared as "u32 *dest = &regs->data[priv->dreg];",
but there are different ways to fetch the value:
1. fetching the l4 port, we use:
    *dest = 0;
    *(u16 *)dest = *(u16 *)ptr;

2. fetching the NFT_META_IIFTYPE, we use:
    *dest = 0;
    *(u16 *)dest = in->type;

3. fetching the NFT_CT_PROTO_SRC, we use:
    *dest = (__force __u16)tuple->src.u.all;

So method 1 and method 2 will cause the value stored like this, either in
big-endian or little-endian:
  0          15           31
  +-+-+-+-+-+-+-+-+-
  |  Value  |       0     |
  +-+-+-+-+-+-+-+-+-
But method 3 will cause the value stored like this, in big-endian machine:
  0          15           31
  +-+-+-+-+-+-+-+-+-
  |  0         |  Value   |
  +-+-+-+-+-+-+-+-+-

Later in nft_cmp, nft_set_hash, nft_set_rbtree, we use memcmp to do compare:
   "memcmp(&regs->data[priv->sreg], data/key, 2);"

So method 3 is wrong in big-endian, as 0~15 bits will always be zero. Maybe we
can introduce some wrapper functions to help us, for example:

static inline void nft_register_store16(u32 *dreg, u16 value)
{
        *dreg = 0;
        *(u16 *)dreg = value;
}

static inline void nft_register_store8(u32 *dreg, u8 value)
{
        *dreg = 0;
        *(u8 *)dreg = value;
}

...

Am I wrong? Or I totally misunderstood this byte-order issue?

Re: [PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[Pablo Neira Ayuso]

Hi Liping,

On Mon, Mar 06, 2017 at 10:27:20PM +0800, Liping Zhang wrote:
> Hi Pablo,
> 
> 2017-03-06 20:01 GMT+08:00 Pablo Neira Ayuso <pablo@netfilter.org>:
> [...]
> > Right, the userdata case is not handled properly. And in this case we
> > have no specific flag at set creation, so element comments may come
> > without previous notice via set flags.
> >
> > I think we have to keep a list of dummy nft_set_ext that is only used
> > in the dump path, we can simplify this logic at the cost of increasing
> > memory consumption. Another alternative is to keep around a structure
> > to store only the set element userdata that we need for comments.
> >
> > Let me think.
> >
> > Your patches look good to me. Probably we can skip 2/2 if we introduce
> > the dummy nft_set_ext list, and remove the ->flush field for
> > nft_set_iter.
> >
> 
> Actually I was preparing to send v2 about this patch, then I saw your
> reply:). Because I find out that in nft_bitmap_walk(), the 'key' maybe
> incorrect on the big-endian machines when the key length is 1.
> So the patch diff looks like this:
> 
> static void nft_bitmap_walk(...)
>                         key = ((idx * BITS_PER_BYTE) + off) >> 1;
> -                       memcpy(nft_set_ext_key(ext), &key, set->klen);
> +                       if (set->klen == 2)
> +                               *(u16 *)nft_set_ext_key(ext) = key;
> +                       else
> +                               *(u8 *)nft_set_ext_key(ext) = key;
> 
> But if we will introduce the dummy nft_set_ext list to the whole elements
> in the bitmap, the above part is not needed anymore, i.e. we need not to
> convert the bit to key.

Right, we can just walk over the list of dummy nft_set_ext if we
follow this approach.

> (Now start the second part, about the byte-order in nft)
> Unrelated to this patch actually, I find that there's a little messy when we
> store the u8 or u16 integer to the register, which may cause miss-match in
> big-endian machines (Actually I have no big-endian machine around me,
> so I can't verify it).
> 
> For example, dest pointer is declared as "u32 *dest = &regs->data[priv->dreg];",
> but there are different ways to fetch the value:
> 1. fetching the l4 port, we use:
>     *dest = 0;
>     *(u16 *)dest = *(u16 *)ptr;
> 
> 2. fetching the NFT_META_IIFTYPE, we use:
>     *dest = 0;
>     *(u16 *)dest = in->type;
>
> 3. fetching the NFT_CT_PROTO_SRC, we use:
>     *dest = (__force __u16)tuple->src.u.all;
>
> So method 1 and method 2 will cause the value stored like this, either in
> big-endian or little-endian:
>   0          15           31
>   +-+-+-+-+-+-+-+-+-
>   |  Value  |       0     |
>   +-+-+-+-+-+-+-+-+-
> But method 3 will cause the value stored like this, in big-endian machine:
>   0          15           31
>   +-+-+-+-+-+-+-+-+-
>   |  0         |  Value   |
>   +-+-+-+-+-+-+-+-+-
> 
> Later in nft_cmp, nft_set_hash, nft_set_rbtree, we use memcmp to do compare:
>    "memcmp(&regs->data[priv->sreg], data/key, 2);"
> 
> So method 3 is wrong in big-endian, as 0~15 bits will always be zero. Maybe we
> can introduce some wrapper functions to help us, for example:
> 
> static inline void nft_register_store16(u32 *dreg, u16 value)
> {
>         *dreg = 0;
>         *(u16 *)dreg = value;
> }
> 
> static inline void nft_register_store8(u32 *dreg, u8 value)
> {
>         *dreg = 0;
>         *(u8 *)dreg = value;
> }

I think this a good idea, send patches to add this and use them for
the nf tree, please.

> ...
> 
> Am I wrong? Or I totally misunderstood this byte-order issue?

This looks correct to me.

Note that:

*dest = 0;

is just there because of concatenations, so we make sure that we zero
the pad given that register allocation happens at 32-bit level.

Another note: For method 3. __force is there for the sparse checker
given the different endianness of both sides of the assignment.

Re: [PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[Liping Zhang]

2017-03-07 0:42 GMT+08:00 Pablo Neira Ayuso <pablo@netfilter.org>:
[...]
>> static inline void nft_register_store16(u32 *dreg, u16 value)
>> {
>>         *dreg = 0;
>>         *(u16 *)dreg = value;
>> }
>>
>> static inline void nft_register_store8(u32 *dreg, u8 value)
>> {
>>         *dreg = 0;
>>         *(u8 *)dreg = value;
>> }
>
> I think this a good idea, send patches to add this and use them for
> the nf tree, please.

OK. I will have a closer look into these.

Thanks Pablo.

>
>> ...
>>
>> Am I wrong? Or I totally misunderstood this byte-order issue?
>
> This looks correct to me.
>
> Note that:
>
> *dest = 0;
>
> is just there because of concatenations, so we make sure that we zero
> the pad given that register allocation happens at 32-bit level.
>
> Another note: For method 3. __force is there for the sparse checker
> given the different endianness of both sides of the assignment.

Re: [PATCH nf 1/2] netfilter: nft_set_bitmap: fetch the element key based on the set->klen

[Pablo Neira Ayuso]

On Mon, Mar 06, 2017 at 12:02:52AM +0800, Liping Zhang wrote:
> From: Liping Zhang <zlpnobody@gmail.com>
> 
> Currently we just assume the element key as a u32 integer, regardless of
> the set key length.
> 
> This is incorrect, for example, the tcp port number is only 16 bits.
> So when we use the nft_payload expr to get the tcp dport and store
> it to dreg, the dport will be stored at 0~15 bits, and 16~31 bits
> will be padded with zero.
> 
> So the reg->data[dreg] will be looked like as below:
>   0          15           31
>   +-+-+-+-+-+-+-+-+-+-+-+-+
>   | tcp dport |      0    |
>   +-+-+-+-+-+-+-+-+-+-+-+-+
> But for these big-endian systems, if we treate this register as a u32
> integer, the element key will be larger than 65535, so the following
> lookup in bitmap set will cause out of bound access.
> 
> Another issue is that if we add element with comments in bitmap
> set(although the comments will be ignored eventually), the element will
> vanish strangely. Because we treate the element key as a u32 integer, so
> the comments will become the part of the element key, then the element
> key will also be larger than 65535 and out of bound access will happen:
>   # nft add element t s { 1 comment test }
> 
> Since set->klen is 1 or 2, it's fine to treate the element key as a u8 or
> u16 integer.

Applied this one, thanks Liping.

I just sent a couple of a patch to fix element comments with bitmaps,
this is also implicitly fixing the leak that you aimed to fix with 2/2.