Bug 15379 - u32 classifier port range calculation error
Summary: u32 classifier port range calculation error
Status: RESOLVED DOCUMENTED
Alias: None
Product: Networking
Classification: Unclassified
Component: Other (show other bugs)
Hardware: All Linux
: P1 normal
Assignee: Arnaldo Carvalho de Melo
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-02-23 20:56 UTC by Reinaldo Carvalho
Modified: 2012-06-27 13:39 UTC (History)
1 user (show)

See Also:
Kernel Version: All (2.6.32 tested)
Subsystem:
Regression: No
Bisected commit-id:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Description Reinaldo Carvalho 2010-02-23 20:56:04 UTC 
U32 classifier have a problem on mask calculation of IP port range value.

To reproduce the problem:

##### MASK CALCULATION FOR PORT RANGE 6880->6911

echo "obase=16;(2^13)-32" | bc
1FE0

Example:

###### TC SAMPLE RULES
tc qdisc del dev eth0 root >/dev/null 2>&1

tc qdisc  add dev eth0 root handle 1: htb default 1100
tc class  add dev eth0 root classid 1:1000 htb rate 1000Mbit ceil 1000Mbit
tc class  add dev eth0 classid 1:1100 parent 1:1000 htb prio 0 rate 999Mbit ceil 999Mbit
tc class  add dev eth0 classid 1:1200 parent 1:1000 htb prio 0 rate 1Mbit   ceil 1Mbit

tc filter add dev eth0 protocol ip prio 1 parent 1: u32 flowid 1:1200 match ip dport 6880 0x1FE0

###### STATS CLEAN ** success 0
tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt 0 flowid 1:1200  (rule hit 116 success 0)
  match 00001ae0/00001fe0 at 20 (success 0 )

###### SENDING PACKETS I
# nmap example.ufpa.br -p 1-10000

###### STATS I ** success 32 (OK)
# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt 0 flowid 1:1200  (rule hit 12676 success 32)
  match 00001ae0/00001fe0 at 20 (success 32 )

###### SENDING PACKETS II
# nmap example.ufpa.br -p 10000-20000

###### STATS II ** success 64 (ERROR) - should not match

# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt 0 flowid 1:1200  (rule hit 25172 success 64)
  match 00001ae0/00001fe0 at 20 (success 64 )

###### SENDING PACKETS III
# nmap example.ufpa.br -p 20000-30000

###### STATS III ** success 96 (ERROR) - should not match

# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt 0 flowid 1:1200  (rule hit 43131 success 96)
  match 00001ae0/00001fe0 at 20 (success 96 )

### End
Comment 1 Andrew Morton 2010-02-24 22:53:02 UTC 
(switched to email.  Please respond via emailed reply-to-all, not via the
bugzilla web interface).

On Tue, 23 Feb 2010 20:56:09 GMT bugzilla-daemon@bugzilla.kernel.org wrote:

> http://bugzilla.kernel.org/show_bug.cgi?id=15379
> 
>            Summary: u32 classifier port range calculation error
>            Product: Networking
>            Version: 2.5
>     Kernel Version: All (2.6.32 tested)
>           Platform: All
>         OS/Version: Linux
>               Tree: Mainline
>             Status: NEW
>           Severity: normal
>           Priority: P1
>          Component: Other
>         AssignedTo: acme@ghostprotocols.net
>         ReportedBy: reinaldoc@gmail.com
>         Regression: No
> 
> 
> U32 classifier have a problem on mask calculation of IP port range value.
> 
> To reproduce the problem:
> 
> ##### MASK CALCULATION FOR PORT RANGE 6880->6911
> 
> echo "obase=16;(2^13)-32" | bc
> 1FE0
> 
> Example:
> 
> ###### TC SAMPLE RULES
> tc qdisc del dev eth0 root >/dev/null 2>&1
> 
> tc qdisc  add dev eth0 root handle 1: htb default 1100
> tc class  add dev eth0 root classid 1:1000 htb rate 1000Mbit ceil 1000Mbit
> tc class  add dev eth0 classid 1:1100 parent 1:1000 htb prio 0 rate 999Mbit
> ceil 999Mbit
> tc class  add dev eth0 classid 1:1200 parent 1:1000 htb prio 0 rate 1Mbit  
> ceil 1Mbit
> 
> tc filter add dev eth0 protocol ip prio 1 parent 1: u32 flowid 1:1200 match
> ip
> dport 6880 0x1FE0
> 
> ###### STATS CLEAN ** success 0
> tc -s filter show dev eth0
> filter parent 1: protocol ip pref 1 u32
> filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt
> 0
> flowid 1:1200  (rule hit 116 success 0)
>   match 00001ae0/00001fe0 at 20 (success 0 )
> 
> ###### SENDING PACKETS I
> # nmap example.ufpa.br -p 1-10000
> 
> ###### STATS I ** success 32 (OK)
> # tc -s filter show dev eth0
> filter parent 1: protocol ip pref 1 u32
> filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt
> 0
> flowid 1:1200  (rule hit 12676 success 32)
>   match 00001ae0/00001fe0 at 20 (success 32 )
> 
> ###### SENDING PACKETS II
> # nmap example.ufpa.br -p 10000-20000
> 
> ###### STATS II ** success 64 (ERROR) - should not match
> 
> # tc -s filter show dev eth0
> filter parent 1: protocol ip pref 1 u32
> filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt
> 0
> flowid 1:1200  (rule hit 25172 success 64)
>   match 00001ae0/00001fe0 at 20 (success 64 )
> 
> ###### SENDING PACKETS III
> # nmap example.ufpa.br -p 20000-30000
> 
> ###### STATS III ** success 96 (ERROR) - should not match
> 
> # tc -s filter show dev eth0
> filter parent 1: protocol ip pref 1 u32
> filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800 bkt
> 0
> flowid 1:1200  (rule hit 43131 success 96)
>   match 00001ae0/00001fe0 at 20 (success 96 )
> 
> ### End
Comment 2 Anonymous Emailer 2010-02-25 03:25:00 UTC 
Reply-To: hadi@cyberus.ca

This is expected.
An incoming packet is masked with 0x1FE0 at offset 20 and the
value is compared to 6880. If they match, success.
So between 1-10000, you essentially have some starting at 6880. 
And then at a large number prolly around port 15000, you have
a few more. and the pattern repeats etc.

cheers,
jamal

On Wed, 2010-02-24 at 14:52 -0800, Andrew Morton wrote:
> (switched to email.  Please respond via emailed reply-to-all, not via the
> bugzilla web interface).
> 
> On Tue, 23 Feb 2010 20:56:09 GMT bugzilla-daemon@bugzilla.kernel.org wrote:
> 
> > http://bugzilla.kernel.org/show_bug.cgi?id=15379
> > 
> >            Summary: u32 classifier port range calculation error
> >            Product: Networking
> >            Version: 2.5
> >     Kernel Version: All (2.6.32 tested)
> >           Platform: All
> >         OS/Version: Linux
> >               Tree: Mainline
> >             Status: NEW
> >           Severity: normal
> >           Priority: P1
> >          Component: Other
> >         AssignedTo: acme@ghostprotocols.net
> >         ReportedBy: reinaldoc@gmail.com
> >         Regression: No
> > 
> > 
> > U32 classifier have a problem on mask calculation of IP port range value.
> > 
> > To reproduce the problem:
> > 
> > ##### MASK CALCULATION FOR PORT RANGE 6880->6911
> > 
> > echo "obase=16;(2^13)-32" | bc
> > 1FE0
> > 
> > Example:
> > 
> > ###### TC SAMPLE RULES
> > tc qdisc del dev eth0 root >/dev/null 2>&1
> > 
> > tc qdisc  add dev eth0 root handle 1: htb default 1100
> > tc class  add dev eth0 root classid 1:1000 htb rate 1000Mbit ceil 1000Mbit
> > tc class  add dev eth0 classid 1:1100 parent 1:1000 htb prio 0 rate 999Mbit
> > ceil 999Mbit
> > tc class  add dev eth0 classid 1:1200 parent 1:1000 htb prio 0 rate 1Mbit  
> > ceil 1Mbit
> > 
> > tc filter add dev eth0 protocol ip prio 1 parent 1: u32 flowid 1:1200 match
> ip
> > dport 6880 0x1FE0
> > 
> > ###### STATS CLEAN ** success 0
> > tc -s filter show dev eth0
> > filter parent 1: protocol ip pref 1 u32
> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
> bkt 0
> > flowid 1:1200  (rule hit 116 success 0)
> >   match 00001ae0/00001fe0 at 20 (success 0 )
> > 
> > ###### SENDING PACKETS I
> > # nmap example.ufpa.br -p 1-10000
> > 
> > ###### STATS I ** success 32 (OK)
> > # tc -s filter show dev eth0
> > filter parent 1: protocol ip pref 1 u32
> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
> bkt 0
> > flowid 1:1200  (rule hit 12676 success 32)
> >   match 00001ae0/00001fe0 at 20 (success 32 )
> > 
> > ###### SENDING PACKETS II
> > # nmap example.ufpa.br -p 10000-20000
> > 
> > ###### STATS II ** success 64 (ERROR) - should not match
> > 
> > # tc -s filter show dev eth0
> > filter parent 1: protocol ip pref 1 u32
> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
> bkt 0
> > flowid 1:1200  (rule hit 25172 success 64)
> >   match 00001ae0/00001fe0 at 20 (success 64 )
> > 
> > ###### SENDING PACKETS III
> > # nmap example.ufpa.br -p 20000-30000
> > 
> > ###### STATS III ** success 96 (ERROR) - should not match
> > 
> > # tc -s filter show dev eth0
> > filter parent 1: protocol ip pref 1 u32
> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
> bkt 0
> > flowid 1:1200  (rule hit 43131 success 96)
> >   match 00001ae0/00001fe0 at 20 (success 96 )
> > 
> > ### End
> 
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
Comment 3 Reinaldo Carvalho 2010-02-25 11:27:02 UTC 
Then u32 mask is useless. Or exist a correct mask to match with especific range?

-- 
Reinaldo de Carvalho


On Thu, Feb 25, 2010 at 12:24 AM, jamal <hadi@cyberus.ca> wrote:
>
> This is expected.
> An incoming packet is masked with 0x1FE0 at offset 20 and the
> value is compared to 6880. If they match, success.
> So between 1-10000, you essentially have some starting at 6880.
> And then at a large number prolly around port 15000, you have
> a few more. and the pattern repeats etc.
>
> cheers,
> jamal
>
> On Wed, 2010-02-24 at 14:52 -0800, Andrew Morton wrote:
>> (switched to email.  Please respond via emailed reply-to-all, not via the
>> bugzilla web interface).
>>
>> On Tue, 23 Feb 2010 20:56:09 GMT bugzilla-daemon@bugzilla.kernel.org wrote:
>>
>> > http://bugzilla.kernel.org/show_bug.cgi?id=15379
>> >
>> >            Summary: u32 classifier port range calculation error
>> >            Product: Networking
>> >            Version: 2.5
>> >     Kernel Version: All (2.6.32 tested)
>> >           Platform: All
>> >         OS/Version: Linux
>> >               Tree: Mainline
>> >             Status: NEW
>> >           Severity: normal
>> >           Priority: P1
>> >          Component: Other
>> >         AssignedTo: acme@ghostprotocols.net
>> >         ReportedBy: reinaldoc@gmail.com
>> >         Regression: No
>> >
>> >
>> > U32 classifier have a problem on mask calculation of IP port range value.
>> >
>> > To reproduce the problem:
>> >
>> > ##### MASK CALCULATION FOR PORT RANGE 6880->6911
>> >
>> > echo "obase=16;(2^13)-32" | bc
>> > 1FE0
>> >
>> > Example:
>> >
>> > ###### TC SAMPLE RULES
>> > tc qdisc del dev eth0 root >/dev/null 2>&1
>> >
>> > tc qdisc  add dev eth0 root handle 1: htb default 1100
>> > tc class  add dev eth0 root classid 1:1000 htb rate 1000Mbit ceil 1000Mbit
>> > tc class  add dev eth0 classid 1:1100 parent 1:1000 htb prio 0 rate
>> 999Mbit
>> > ceil 999Mbit
>> > tc class  add dev eth0 classid 1:1200 parent 1:1000 htb prio 0 rate 1Mbit
>> > ceil 1Mbit
>> >
>> > tc filter add dev eth0 protocol ip prio 1 parent 1: u32 flowid 1:1200
>> match ip
>> > dport 6880 0x1FE0
>> >
>> > ###### STATS CLEAN ** success 0
>> > tc -s filter show dev eth0
>> > filter parent 1: protocol ip pref 1 u32
>> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
>> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
>> bkt 0
>> > flowid 1:1200  (rule hit 116 success 0)
>> >   match 00001ae0/00001fe0 at 20 (success 0 )
>> >
>> > ###### SENDING PACKETS I
>> > # nmap example.ufpa.br -p 1-10000
>> >
>> > ###### STATS I ** success 32 (OK)
>> > # tc -s filter show dev eth0
>> > filter parent 1: protocol ip pref 1 u32
>> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
>> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
>> bkt 0
>> > flowid 1:1200  (rule hit 12676 success 32)
>> >   match 00001ae0/00001fe0 at 20 (success 32 )
>> >
>> > ###### SENDING PACKETS II
>> > # nmap example.ufpa.br -p 10000-20000
>> >
>> > ###### STATS II ** success 64 (ERROR) - should not match
>> >
>> > # tc -s filter show dev eth0
>> > filter parent 1: protocol ip pref 1 u32
>> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
>> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
>> bkt 0
>> > flowid 1:1200  (rule hit 25172 success 64)
>> >   match 00001ae0/00001fe0 at 20 (success 64 )
>> >
>> > ###### SENDING PACKETS III
>> > # nmap example.ufpa.br -p 20000-30000
>> >
>> > ###### STATS III ** success 96 (ERROR) - should not match
>> >
>> > # tc -s filter show dev eth0
>> > filter parent 1: protocol ip pref 1 u32
>> > filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
>> > filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht 800
>> bkt 0
>> > flowid 1:1200  (rule hit 43131 success 96)
>> >   match 00001ae0/00001fe0 at 20 (success 96 )
>> >
>> > ### End
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe netdev" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>
Comment 4 Anonymous Emailer 2010-02-25 13:25:37 UTC 
Reply-To: hadi@cyberus.ca

On Thu, 2010-02-25 at 08:25 -0300, Reinaldo de Carvalho wrote:
> Then u32 mask is useless. Or exist a correct mask to match with especific
> range?

Ranges and masks typically dont mix well generally - this has nothing to
do with u32; try doing subnet ranges for example. It is hard to describe
port range 10->20 using masks..

If i read your email correctly: you are trying to get the first 32 ports
after 6880. It would seem to me the mask should be 0xFFE0, no? i.e your
bc calculation should be:
echo "obase=16;(2^16)-32" | bc

cheers,
jamal
Comment 5 Reinaldo Carvalho 2010-02-25 19:19:15 UTC 
On Thu, Feb 25, 2010 at 10:24 AM, jamal <hadi@cyberus.ca> wrote:
> On Thu, 2010-02-25 at 08:25 -0300, Reinaldo de Carvalho wrote:
>> Then u32 mask is useless. Or exist a correct mask to match with especific
>> range?
>
> Ranges and masks typically dont mix well generally - this has nothing to
> do with u32; try doing subnet ranges for example. It is hard to describe
> port range 10->20 using masks..
>
> If i read your email correctly: you are trying to get the first 32 ports
> after 6880. It would seem to me the mask should be 0xFFE0, no? i.e your
> bc calculation should be:
> echo "obase=16;(2^16)-32" | bc
>

No.

Testing with mask 0xFFE0... (1 port match)

# Stats...
# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht
800 bkt 0 flowid 1:1200  (rule hit 13 success 0)
  match 00001ae0/0000ffe0 at 20 (success 0 )

# Sending packets...
# nmap example.ufpa.br -p 1-65535

# Stats...
# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht
800 bkt 0 flowid 1:1200  (rule hit 65459 success 1)
  match 00001ae0/0000ffe0 at 20 (success 1 )
Comment 6 Anonymous Emailer 2010-02-25 21:48:12 UTC 
Reply-To: hadi@cyberus.ca

On Thu, 2010-02-25 at 16:11 -0300, Reinaldo de Carvalho wrote:

> Testing with mask 0xFFE0... (1 port match)
> 
> # Stats...
> # tc -s filter show dev eth0
> filter parent 1: protocol ip pref 1 u32
> filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht
> 800 bkt 0 flowid 1:1200  (rule hit 13 success 0)
>   match 00001ae0/0000ffe0 at 20 (success 0 )
> 
> # Sending packets...
> # nmap example.ufpa.br -p 1-65535
> 
> # Stats...
> # tc -s filter show dev eth0
> filter parent 1: protocol ip pref 1 u32
> filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1
> filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht
> 800 bkt 0 flowid 1:1200  (rule hit 65459 success 1)
>   match 00001ae0/0000ffe0 at 20 (success 1 )


Ok, you forced me to setup a system and install nmap.

-------
bigismall:~# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32 
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1 
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht
800 bkt 0 flowid 1:1200  (rule hit 15 success 0)
  match 00001ae0/0000ffe0 at 20 (success 0 ) 
bigismall:~# nmap bigi -p 1-65535

Starting Nmap 5.00 ( http://nmap.org ) at 2010-02-25 16:40 UTC
Interesting ports on bigi (10.0.0.26):
Not shown: 65532 closed ports
PORT   STATE SERVICE
22/tcp open  ssh
MAC Address: 00:16:2E:12:4D:2E (Unknown)

Nmap done: 1 IP address (1 host up) scanned in 65.55 seconds
bigismall:~# tc -s filter show dev eth0
filter parent 1: protocol ip pref 1 u32 
filter parent 1: protocol ip pref 1 u32 fh 800: ht divisor 1 
filter parent 1: protocol ip pref 1 u32 fh 800::800 order 2048 key ht
800 bkt 0 flowid 1:1200  (rule hit 65614 success 32)
  match 00001ae0/0000ffe0 at 20 (success 32 ) 
bigismall:~# 
--------------

cheers,
jamal
Note You need to log in before you can comment on or make changes to this bug.