* [PATCH] netfilter: xt_hashlimit: Fix integer divide round to zero.
@ 2017-02-04 22:47 Alban Browaeys
2017-02-06 13:04 ` Pablo Neira Ayuso
0 siblings, 1 reply; 5+ messages in thread
From: Alban Browaeys @ 2017-02-04 22:47 UTC (permalink / raw)
To: Pablo Neira Ayuso
Cc: Patrick McHardy, Jozsef Kadlecsik, David S. Miller,
netfilter-devel, coreteam, netdev, linux-kernel, Alban Browaeys
Diving the divider by the multiplier before applying to the input.
When this would "divide by zero", divide the multiplier by the divider
first then multiply the input by this value.
Currently user2creds outputs zero when input value is bigger than the
number of slices and lower than scale.
This as then user input is applied an integer divide operation to
a number greater than itself (scale).
That rounds up to zero, then we mulitply zero by the credits slice size.
iptables -t filter -I INPUT --protocol tcp --match hashlimit
--hashlimit 40/second --hashlimit-burst 20 --hashlimit-mode srcip
--hashlimit-name syn-flood --jump RETURN
thus trigger the overflow detection code:
xt_hashlimit: overflow, try lower: 25000/20
(25000 as hashlimit avd and 20 the burst)
Here:
134217 slices of (HZ * CREDITS_PER_JIFFY) size.
500000 is user input value
1000000 is XT_HASHLIMIT_SCALE_v2
gives: 0 as user2creds output
Setting burst to "1" typically solve the issue ...
but setting it to "40" does too !
This is on 32bit arch calling into revision 2 of hashlimit.
Signed-off-by: Alban Browaeys <alban.browaeys@gmail.com>
---
net/netfilter/xt_hashlimit.c | 18 ++++++++----------
1 file changed, 8 insertions(+), 10 deletions(-)
diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
index 10063408141d..df75ad643eef 100644
--- a/net/netfilter/xt_hashlimit.c
+++ b/net/netfilter/xt_hashlimit.c
@@ -463,21 +463,19 @@ static u32 xt_hashlimit_len_to_chunks(u32 len)
/* Precision saver. */
static u64 user2credits(u64 user, int revision)
{
+ /* Avoid overflow: divide the constant operands first */
if (revision == 1) {
- /* If multiplying would overflow... */
- if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY_v1))
- /* Divide first. */
- return div64_u64(user, XT_HASHLIMIT_SCALE)
- * HZ * CREDITS_PER_JIFFY_v1;
+ return div64_u64(user, div64_u64(XT_HASHLIMIT_SCALE,
+ HZ * CREDITS_PER_JIFFY_v1));
- return div64_u64(user * HZ * CREDITS_PER_JIFFY_v1,
+ return user * div64_u64(HZ * CREDITS_PER_JIFFY_v1,
XT_HASHLIMIT_SCALE);
} else {
- if (user > 0xFFFFFFFFFFFFFFFFULL / (HZ*CREDITS_PER_JIFFY))
- return div64_u64(user, XT_HASHLIMIT_SCALE_v2)
- * HZ * CREDITS_PER_JIFFY;
+ if (XT_HASHLIMIT_SCALE_v2 >= HZ * CREDITS_PER_JIFFY)
+ return div64_u64(user, div64_u64(XT_HASHLIMIT_SCALE_v2,
+ HZ * CREDITS_PER_JIFFY));
- return div64_u64(user * HZ * CREDITS_PER_JIFFY,
+ return user * div64_u64(HZ * CREDITS_PER_JIFFY,
XT_HASHLIMIT_SCALE_v2);
}
}
--
2.11.0
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH] netfilter: xt_hashlimit: Fix integer divide round to zero.
2017-02-04 22:47 [PATCH] netfilter: xt_hashlimit: Fix integer divide round to zero Alban Browaeys
@ 2017-02-06 13:04 ` Pablo Neira Ayuso
2017-02-06 14:28 ` Alban Browaeys
0 siblings, 1 reply; 5+ messages in thread
From: Pablo Neira Ayuso @ 2017-02-06 13:04 UTC (permalink / raw)
To: Alban Browaeys
Cc: Patrick McHardy, Jozsef Kadlecsik, David S. Miller,
netfilter-devel, coreteam, netdev, linux-kernel
On Sat, Feb 04, 2017 at 11:47:31PM +0100, Alban Browaeys wrote:
> Diving the divider by the multiplier before applying to the input.
> When this would "divide by zero", divide the multiplier by the divider
> first then multiply the input by this value.
>
> Currently user2creds outputs zero when input value is bigger than the
> number of slices and lower than scale.
> This as then user input is applied an integer divide operation to
> a number greater than itself (scale).
> That rounds up to zero, then we mulitply zero by the credits slice size.
> iptables -t filter -I INPUT --protocol tcp --match hashlimit
> --hashlimit 40/second --hashlimit-burst 20 --hashlimit-mode srcip
> --hashlimit-name syn-flood --jump RETURN
> thus trigger the overflow detection code:
> xt_hashlimit: overflow, try lower: 25000/20
> (25000 as hashlimit avd and 20 the burst)
> Here:
> 134217 slices of (HZ * CREDITS_PER_JIFFY) size.
> 500000 is user input value
> 1000000 is XT_HASHLIMIT_SCALE_v2
> gives: 0 as user2creds output
> Setting burst to "1" typically solve the issue ...
> but setting it to "40" does too !
>
> This is on 32bit arch calling into revision 2 of hashlimit.
>
> Signed-off-by: Alban Browaeys <alban.browaeys@gmail.com>
> ---
> net/netfilter/xt_hashlimit.c | 18 ++++++++----------
> 1 file changed, 8 insertions(+), 10 deletions(-)
>
> diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
> index 10063408141d..df75ad643eef 100644
> --- a/net/netfilter/xt_hashlimit.c
> +++ b/net/netfilter/xt_hashlimit.c
> @@ -463,21 +463,19 @@ static u32 xt_hashlimit_len_to_chunks(u32 len)
> /* Precision saver. */
> static u64 user2credits(u64 user, int revision)
> {
> + /* Avoid overflow: divide the constant operands first */
> if (revision == 1) {
> - /* If multiplying would overflow... */
> - if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY_v1))
> - /* Divide first. */
> - return div64_u64(user, XT_HASHLIMIT_SCALE)
> - * HZ * CREDITS_PER_JIFFY_v1;
> + return div64_u64(user, div64_u64(XT_HASHLIMIT_SCALE,
> + HZ * CREDITS_PER_JIFFY_v1));
>
> - return div64_u64(user * HZ * CREDITS_PER_JIFFY_v1,
> + return user * div64_u64(HZ * CREDITS_PER_JIFFY_v1,
> XT_HASHLIMIT_SCALE);
I see two return statements here, the one coming later is
shadowed, this can't be right.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] netfilter: xt_hashlimit: Fix integer divide round to zero.
2017-02-06 13:04 ` Pablo Neira Ayuso
@ 2017-02-06 14:28 ` Alban Browaeys
2017-02-06 22:50 ` [PATCH v2] " Alban Browaeys
0 siblings, 1 reply; 5+ messages in thread
From: Alban Browaeys @ 2017-02-06 14:28 UTC (permalink / raw)
To: Pablo Neira Ayuso
Cc: Patrick McHardy, Jozsef Kadlecsik, David S. Miller,
netfilter-devel, coreteam, netdev, linux-kernel
Le lundi 06 février 2017 à 14:04 +0100, Pablo Neira Ayuso a écrit :
> On Sat, Feb 04, 2017 at 11:47:31PM +0100, Alban Browaeys wrote:
> > diff --git a/net/netfilter/xt_hashlimit.c
> > b/net/netfilter/xt_hashlimit.c
> > index 10063408141d..df75ad643eef 100644
> > --- a/net/netfilter/xt_hashlimit.c
> > +++ b/net/netfilter/xt_hashlimit.c
> > @@ -463,21 +463,19 @@ static u32 xt_hashlimit_len_to_chunks(u32 len)
> > /* Precision saver. */
> > static u64 user2credits(u64 user, int revision)
> > {
> > > > + /* Avoid overflow: divide the constant operands first */
> > > > if (revision == 1) {
> > > > - /* If multiplying would overflow... */
> > > > - if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY_v1))
> > > > - /* Divide first. */
> > > > - return div64_u64(user, XT_HASHLIMIT_SCALE)
> > > > - * HZ * CREDITS_PER_JIFFY_v1;
> > > > + return div64_u64(user, div64_u64(XT_HASHLIMIT_SCALE,
> > > > + HZ * CREDITS_PER_JIFFY_v1));
> >
> > > > - return div64_u64(user * HZ * CREDITS_PER_JIFFY_v1,
> > > > + return user * div64_u64(HZ * CREDITS_PER_JIFFY_v1,
> > XT_HASHLIMIT_SCALE);
>
> I see two return statements here, the one coming later is
> shadowed, this can't be right.
I fixed revision 2 case then copy the code to revision 1
and lost the condition in the process.
The code duplication is useless. I will rework it in v2.
Thank you for the review.
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH v2] netfilter: xt_hashlimit: Fix integer divide round to zero.
2017-02-06 14:28 ` Alban Browaeys
@ 2017-02-06 22:50 ` Alban Browaeys
2017-02-21 12:48 ` Pablo Neira Ayuso
0 siblings, 1 reply; 5+ messages in thread
From: Alban Browaeys @ 2017-02-06 22:50 UTC (permalink / raw)
To: Pablo Neira Ayuso
Cc: Patrick McHardy, Jozsef Kadlecsik, David S. Miller,
netfilter-devel, coreteam, netdev, linux-kernel, Alban Browaeys
Diving the divider by the multiplier before applying to the input.
When this would "divide by zero", divide the multiplier by the divider
first then multiply the input by this value.
Currently user2creds outputs zero when input value is bigger than the
number of slices and lower than scale.
This as then user input is applied an integer divide operation to
a number greater than itself (scale).
That rounds up to zero, then we mulitply zero by the credits slice size.
iptables -t filter -I INPUT --protocol tcp --match hashlimit
--hashlimit 40/second --hashlimit-burst 20 --hashlimit-mode srcip
--hashlimit-name syn-flood --jump RETURN
thus trigger the overflow detection code:
xt_hashlimit: overflow, try lower: 25000/20
(25000 as hashlimit avd and 20 the burst)
Here:
134217 slices of (HZ * CREDITS_PER_JIFFY) size.
500000 is user input value
1000000 is XT_HASHLIMIT_SCALE_v2
gives: 0 as user2creds output
Setting burst to "1" typically solve the issue ...
but setting it to "40" does too !
This is on 32bit arch calling into revision 2 of hashlimit.
Signed-off-by: Alban Browaeys <alban.browaeys@gmail.com>
---
v2:
- fix missing conditional statement in revision 1 case
<Pablo Neira Ayuso>.
I removed the code duplication between revision 1 and 2.
v1: https://lkml.org/lkml/2017/2/4/173
---
net/netfilter/xt_hashlimit.c | 25 +++++++++----------------
1 file changed, 9 insertions(+), 16 deletions(-)
diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
index 10063408141d..84ad5ab34558 100644
--- a/net/netfilter/xt_hashlimit.c
+++ b/net/netfilter/xt_hashlimit.c
@@ -463,23 +463,16 @@ static u32 xt_hashlimit_len_to_chunks(u32 len)
/* Precision saver. */
static u64 user2credits(u64 user, int revision)
{
- if (revision == 1) {
- /* If multiplying would overflow... */
- if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY_v1))
- /* Divide first. */
- return div64_u64(user, XT_HASHLIMIT_SCALE)
- * HZ * CREDITS_PER_JIFFY_v1;
-
- return div64_u64(user * HZ * CREDITS_PER_JIFFY_v1,
- XT_HASHLIMIT_SCALE);
- } else {
- if (user > 0xFFFFFFFFFFFFFFFFULL / (HZ*CREDITS_PER_JIFFY))
- return div64_u64(user, XT_HASHLIMIT_SCALE_v2)
- * HZ * CREDITS_PER_JIFFY;
+ u64 scale = (revision == 1) ?
+ XT_HASHLIMIT_SCALE : XT_HASHLIMIT_SCALE_v2;
+ u64 cpj = (revision == 1) ?
+ CREDITS_PER_JIFFY_v1 : CREDITS_PER_JIFFY;
- return div64_u64(user * HZ * CREDITS_PER_JIFFY,
- XT_HASHLIMIT_SCALE_v2);
- }
+ /* Avoid overflow: divide the constant operands first */
+ if (scale >= HZ * cpj)
+ return div64_u64(user, div64_u64(scale, HZ * cpj));
+
+ return user * div64_u64(HZ * cpj, scale);
}
static u32 user2credits_byte(u32 user)
--
2.11.0
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2] netfilter: xt_hashlimit: Fix integer divide round to zero.
2017-02-06 22:50 ` [PATCH v2] " Alban Browaeys
@ 2017-02-21 12:48 ` Pablo Neira Ayuso
0 siblings, 0 replies; 5+ messages in thread
From: Pablo Neira Ayuso @ 2017-02-21 12:48 UTC (permalink / raw)
To: Alban Browaeys
Cc: Patrick McHardy, Jozsef Kadlecsik, David S. Miller,
netfilter-devel, coreteam, netdev, linux-kernel
On Mon, Feb 06, 2017 at 11:50:33PM +0100, Alban Browaeys wrote:
> Diving the divider by the multiplier before applying to the input.
> When this would "divide by zero", divide the multiplier by the divider
> first then multiply the input by this value.
>
> Currently user2creds outputs zero when input value is bigger than the
> number of slices and lower than scale.
> This as then user input is applied an integer divide operation to
> a number greater than itself (scale).
> That rounds up to zero, then we mulitply zero by the credits slice size.
> iptables -t filter -I INPUT --protocol tcp --match hashlimit
> --hashlimit 40/second --hashlimit-burst 20 --hashlimit-mode srcip
> --hashlimit-name syn-flood --jump RETURN
> thus trigger the overflow detection code:
> xt_hashlimit: overflow, try lower: 25000/20
> (25000 as hashlimit avd and 20 the burst)
> Here:
> 134217 slices of (HZ * CREDITS_PER_JIFFY) size.
> 500000 is user input value
> 1000000 is XT_HASHLIMIT_SCALE_v2
> gives: 0 as user2creds output
> Setting burst to "1" typically solve the issue ...
> but setting it to "40" does too !
>
> This is on 32bit arch calling into revision 2 of hashlimit.
Applied to nf.git, thanks.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-02-21 12:49 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-02-04 22:47 [PATCH] netfilter: xt_hashlimit: Fix integer divide round to zero Alban Browaeys
2017-02-06 13:04 ` Pablo Neira Ayuso
2017-02-06 14:28 ` Alban Browaeys
2017-02-06 22:50 ` [PATCH v2] " Alban Browaeys
2017-02-21 12:48 ` Pablo Neira Ayuso
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).