Skip to contentSkip to conversation

CBQ and all other qdiscs now REALLY completely documented

LARTC jamal 3 participants 7 messages Dec 8, 2001 – Dec 10, 2001

lore
Share & tools
lore

jamal

author
#0 lore raw
Quoted 25 lines · bert hubert
Quoted 3 lines · bert hubert

One thing - does *anybody* understand how hash tables work in tc filter, and what they do? Furthermore, I could use some help with the tc filter police things.

Thanks to Andreas Steinmetz and David Sauer, tc hash tables are now documented as well, thanks!

See:

http://ds9a.nl/2.4Routing/HOWTO//cvs/2.4routing/output/2.4routing-12.html

And then 'Hashing filters for very fast massive filtering'.

I also finished documenting all parameters for TBF, CBQ, SFQ, PRIO, bfifo, pfifo and pfifo_fast. All queues in the Linux kernel are now described in the Linux Advanced Routing & Shaping HOWTO, which can be found on

                          http://ds9a.nl/2.4Routing

I want to send this off to the LDP and Freshmeat somewhere next week, I *would really* like people who are knowledgeable about this subject (this means you, ANK & Jamal 8) ) to read through this.

Quoted 7 lines

This HOWTO is rapidly becoming the perceived authoritative source for traffic control in linux (google on 'Linux Routing' finds it), it might as well be right! So if you have any time at all, check the parts you know about. I expect mistakes.

The parts of the table of contents that document stuff in the kernel not documented elsewhere:

"not documented elsewhere" comes out rude. Werner and I (and even Alexey when he was in the mood -- and i have seen some good documentation by other people as well) have spent numerous hours documenting, presenting and answering questions on mailing lists at times

Sample docs that i was personally involved in:
ftp://icaftp.epfl.ch/pub/linux/diffserv/misc/dsid-01.txt.gz You need to introduce the big picture to the user.
and what is wrong with the definitions used in
http://www.davin.ottawa.on.ca/ols/img10.htm that forced you to introduce your own?
Actually, the big picture is:
http://www.davin.ottawa.on.ca/ols/img9.htm
Also
http://www.linuxjournal.com/article.php?sid369
(was written in 98 but got published in 99)

Now despite all the bitching above, i think your efforts are noble.

[My complaints about your style is you often are trying to present facts by using opinions. For example despite a lot of effort in the past to explain ingress qdisc to you in the past and, pointing you to very good documentation from CISCO you still ended using your opinions on what you thought it should be;->
My scanning of the document shows opinions still posing as miscontrued facts. It is improving compared to what i saw last when we discussed ingress. Let me clarify one thing in this email; i'll read what you have later.

Lets start by your description of TC_PRIO and TOS mappings etc:
Your descriptions of these values is insufficient. Consider this a tutorial and reword it as you wish but please avoid opinions. Ok here's clarification, this applies to both prio, default fifo 3 band queueing and CBQ defaultmap classification; applies to both packets being forwarded as well as locally generated:

First Step:
=====
Define TOS: This is a 4 bit value used as defined in RFC 1349.

0 1 2 3 4 5 6 7
+-----+-----+-----+-----+-----+-----+-----+-----+
| | | |
| PRECEDENCE | TOS | MBZ |
| | | |
+-----+-----+-----+-----+-----+-----+-----+-----+

Then define the values possible as:

                    1000   --   minimize delay
                    0100   --   maximize throughput
                    0010   --   maximize reliability
                    0001   --   minimize monetary cost
                    0000   --   normal service

Look at RFC 1349 for typical values used by different applications Then of course note that RFC 1349 is obsoleted by RFC 2474 (yes, you can weep);

Having said all that:

Linux remaps packets incoming with different values to some internal value; the colum "mapped to" shows the internal mapping

8value(hex) TOS(dec) mapped to(dec)
----------------------------------

0x0              0      0
                 1      7
                 2      0
                 3      0
                 4      2
                 5      2
                 6      2
                 7      2
0x10             8      6
                 9      6
                10      6
                11      6
                12      2
                13      2
                14      2
                15      2

Fill in the "8value(hex)" column gaps using the bitmap from RFC1349 for the 8 bits; These are the values ou would see with tcpdump -vvv I filled the two easiest ones i could compute in my head.

Second step:

Take the default priority map:
1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
This applies for both default prio and the 3-band FIFO queue. Note the queue map fitted on the last column

8 but value TOS mapped to queue map
---------------------------------------------

0x0              0      0              1
                 1      7              2
                 2      0              2
                 3      0              2
                 4      2              1
                 5      2              2
                 6      2              0
                 7      2              0
0x10             8      6              1
                 9      6              1
                10      6              1
                11      6              1
                12      2              1
                13      2              1
                14      2              1
                15      2              1

Queue 0 gets processed first then queue 1 then queue 2. In the strict priority processing such as in prio or default 3 band sched, queue 0 is processed until no more packets are left, then queue1 etc. This could result in starvation. You could avoid starvation by inserting a TBF in a prio; limit the size of the fifo in a class or use CBQ configured as WRR.
I hope the above explains why you have to recreate the priomap everytime you change the number of bands. You used the word "probably" which is wrong. The proper word is "MUST".
What i think would be useful for you to do is describe some of the vlaues used by some applications (RFC 1349 cut-n-paste job would help).

cheers,
jamal

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

author
#1 lore raw
Quoted 78 lines · bert hubert
Quoted 5 lines · jamal

Linux remaps packets incoming with different values to some internal value; the colum "mapped to" shows the internal mapping

8value(hex) TOS(dec) mapped to(dec)
----------------------------------

Quoted 16 lines
0x0              0      0
                 1      7
                 2      0
                 3      0
                 4      2
                 5      2
                 6      2
                 7      2
0x10             8      6
                 9      6
                10      6
                11      6
                12      2
                13      2
                14      2
                15      2

I find this tos2prio table in the kernel (2.5.x), which is somewhat different than your table:

0        TC_PRIO_BESTEFFORT,     0
1        TC_PRIO_(FILLER),       1
2        TC_PRIO_BESTEFFORT,     0
3        TC_PRIO_(BESTEFFORT),   0
4        TC_PRIO_BULK,           2
5        TC_PRIO_(BULK),         2
6        TC_PRIO_BULK,           2
7        TC_PRIO_(BULK),         2
8        TC_PRIO_INTERACTIVE,    6
9        TC_PRIO_(INTERACTIVE),  6
10       TC_PRIO_INTERACTIVE,    6
11       TC_PRIO_(INTERACTIVE),  6
12       TC_PRIO_INTERACTIVE_BULK,       4
13       TC_PRIO_(INTERACTIVE_BULK),     4
14       TC_PRIO_INTERACTIVE_BULK,       4
15       TC_PRIO_(INTERACTIVE_BULK)      4
Quoted 13 lines

Fill in the "8value(hex)" column gaps using the bitmap from RFC1349 for the 8 bits; These are the values ou would see with tcpdump -vvv I filled the two easiest ones i could compute in my head.

Second step:

Take the default priority map:
1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
This applies for both default prio and the 3-band FIFO queue. Note the queue map fitted on the last column

8 but value TOS mapped to queue map
---------------------------------------------

Quoted 16 lines
0x0              0      0              1
                 1      7              2
                 2      0              2
                 3      0              2
                 4      2              1
                 5      2              2
                 6      2              0
                 7      2              0
0x10             8      6              1
                 9      6              1
                10      6              1
                11      6              1
                12      2              1
                13      2              1
                14      2              1
                15      2              1

I've changed this table to:
TOS Bits Means Linux Priority Band
------------------------------------------------------------

Quoted 17 lines
0x0     0     Normal Service           0 Best Effort     1
0x2     1     Minimize Monetary Cost   1 Filler          2
0x4     2     Maximize Reliability     0 Best Effort     1
0x6     3     mmc+mr                   0 Best Effort     1
0x8     4     Maximize Throughput      2 Bulk            2
0xa     5     mmc+mt                   2 Bulk            2
0xc     6     mr+mt                    2 Bulk            2
0xe     7     mmc+mr+mt                2 Bulk            2
0x10    8     Minimize Delay           6 Interactive     0
0x12    9     mmc+md                   6 Interactive     0
0x14    10    mr+md                    6 Interactive     0
0x16    11    mmc+mr+md                6 Interactive     0
0x18    12    mt+md                    4 Int. Bulk       1
0x1a    13    mmc+mt+md                4 Int. Bulk       1
0x1c    14    mr+mt+md                 4 Int. Bulk       1
0x1e    15    mmc+mr+mt+md             4 Int. Bulk       1

Yes, sorry the last 4 are int_bulk (value 4) and not just bulk (2). good eye. You are still abusing the word TOS. Thats only 4 bits not 8; Use the terminology from RFC1349 at least.

Quoted 6 lines

http://ds9a.nl/lartc/HOWTO/cvs/2.4routing/output/2.4routing-9.html#ss9.2

Your table appears to imply that a Maximum Reliability, Mininum Delay packet, TOS bits=9, gets mapped to band 1, not 0, which would not make sense.

This is the priomap: 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 It says 1 is the right value

Quoted 4 lines

Laying it out like this, which does appear how it works, does mean that you can specify priorities in the priomap which do not correspond to possible TOS values.

You cant remap the 3 band scheduler trivially, but you should be able to replace it with a default prio qdisc get exactly the same behavior and use whatever map you want (eg your 0 to 1 substitution for TOS 1001)

Quoted 3 lines

Is it possible at all to set skb->priority from userspace without going through the tos2prio mapping?

SO_PRIORITY socket option is doable; you have to be root.

Quoted 1 line

CBQ can use the skb->priority to classify:

so do prio and pfifo_fast (as i am sure you are aware)

Quoted 10 lines
        /*
         *  Step 1. If skb->priority points to one of our classes, use it.
         */
        if (TC_H_MAJ(prio^sch->handle) = 0 &&
            (cl = cbq_class_lookup(q, prio)) != NULL)
                        return cl;

But to do this, you would need to be able to set skb->priority to a 32bit number:

Cant think of a straight way to do this .... Alexey would know,

cheers,
jamal

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

author
#2 lore raw
In reply to jamal
Quoted 5 lines · bert hubert

On Sat, Dec 08, 2001 at 08:14:10PM -0500, jamal wrote:

AFAICT, the priomap maps skb->priority to band. So the translation is as follows:

yes ;->

Quoted 7 lines
Quoted 2 lines

so do prio and pfifo_fast (as i am sure you are aware)

Of course, but only CBQ (& HTB, by the way) can extract a classid directly from it, without a priomap. Devik is planning to learn HTB to extract a classid directly from the fwmark, to skip a layer of indirection.

I am not sure if this is such a nice hack. Whats wrong with with using the fwmark classifier to select classes?

cheers,
jamal

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#4 lore raw
In reply to jamal
Quoted 5 lines · On Sun, Dec 09, 2001 at 09:14:46PM +0300, [email protected] wrote:
Quoted 3 lines
Quoted 2 lines

But to do this, you would need to be able to set skb->priority to a 32bit number:

Cant think of a straight way to do this .... Alexey would know,

SO_PRIORITY. Or I did not follow you?

Ah yes, thanks, that sets sk->priority which later sets skb->priority.

Regards,

bert

Signature · 8 lines
http://www.PowerDNS.com          Versatile DNS Software & Services
Trilab                                 The Technology People
Netherlabs BV / Rent-a-Nerd.nl           - Nerd Available -
'SYN! .. SYN|ACK! .. ACK!' - the mating call of the internet

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/
author
#5 lore raw
In reply to jamal
Quoted 10 lines · On Sun, 9 Dec 2001 [email protected] wrote:

Hello!

Quoted 5 lines
Quoted 3 lines

But to do this, you would need to be able to set skb->priority to a 32bit number:

Cant think of a straight way to do this .... Alexey would know,

SO_PRIORITY. Or I did not follow you?

So priority limits the size of skb->priority to be from 0..6; this wont work with that check in cbq.

cheers,
jamal

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#6 lore raw
In reply to jamal

Hello!

Quoted 2 lines

So priority limits the size of skb->priority to be from 0..6; this wont work with that check in cbq.

No, it does not. Values different of "low prio" defaults (0..6) are not allowed to user without privileges by evident reasons. User with correspoding capability may direct traffic to any class.

Alexey

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/