On Fri, 2006-07-07 at 10:00 +0200, Patrick McHardy wrote:
> Russell Stuart wrote:
> > Unfortunately you do things in the wrong order for ATM.
> > See: http://mailman.ds9a.nl/pipermail/lartc/2006q1/018314.html
> > for an overview of the problem, and then the attached email for
> > a detailed description of how the current patch addresses it.
> > It is a trivial fix.
>
> Actually that was the part I didn't understand, you keep talking
> (also in that comment in tc_core.c) about an "unknown overhead".
> What is that and why would it be unknown? The mail you attached
> is quite long, is there an simple example that shows what you
> mean?
The "unknown overhead" is just the overhead passed to tc
using the "tc ... overhead xxx" option. It is probably
what you intended to put into your addend attribute.
It is "unknown" because the kernel currently doesn't use
it. It is passed in the tc_ratespec, but is ignored by
the kernel as are most fields in there.
The easy way to fix the "ATM" problem described in the big
comment is simply to add the "overhead" to the packet
length before doing the RTAB lookup. (Identical comments
apply to STAB). If you don't accept this or understand
why, then go read the "long emails" which attempt to
explain it in detail. Jesper's initial version of the
patch did just that, BTW.
However if you do that then you have to adjust RTAB for
all cases (not just ATM) to reflect that the kernel is
now adding the overhead. Thus the RTAB tc sends to the
kernel now changes for different kernel versions, making
modern versions of tc incompatible with older kernels,
and visa versa. I didn't consider that acceptable.
My solution to this to give the kernel the old format
RTAB (ie the one that assumed the kernel didn't add the
overhead) and a small adjustment. This small adjustment
is called cell_align in the ATM patch. You do the same
thing with cell_align as the previous solution did with
the overhead - ie add it in just before looking up RTAB.
This is in effect all the kernel part of the ATM patch
does - make the kernel accept the cell_align option,
and add it to skb->len before looking up RTAB.
The difference between cell_align and overhead is that
cell_align is always 0 when there is no packetisation,
and even when non zero it is small (less than 1<<cell_log,
ie less than 8 for typical MTU's). So for anything bar
ATM it is zero which means old kernels are completely
unaffected, and even for ATM not sending it produces a
small error which means older kernels still benefit from
the "ATM" user space patch. This makes the proposed
"ATM" version of tc both forward and backward compatible.
One other point arises here. The fields in "tc_ratespec"
that "tc" fills and the kernel ignores are there so "tc
show" will work. The essence of the problem is "tc"
compiles the stuff you give it into a single "RTAB".
That "RTAB" can't be reverse compiled into the original
numbers the user provided. So if "tc show" is to work,
"tc" has to save that information somewhere. I don't
think the "tc_ratespec" was the best choice for two
reasons.
Firstly, having the fields show up in tc_ratespec
makes it seem like the kernel can use them. It can't,
as the "overhead" example above shows. Secondly, from
tc's point of view it is inflexible. Over time new
features have been be added to "tc", and each time a
new way of encoding it in the existing "tc_ratespec"
has to be invented. Thus we now have hacks like the
storing the "overhead" in the upper bits of the MPU
figure.
A better solution would be to provide a TLV (ie a
TCA_XXX constant) for TC's private use. From the
kernels point of view it would be an opaque structure
which just saves and echos back when asked. This
would solve both problems.
> > However, now you lot have made me go away and think, I have
> > another idea on how to attack this. Perhaps it will be
> > more palatable to you. It would replace RTAB and STAB with
> > a 28 byte structure for most protocol stacks - well all I can
> > think of off the top of my head, anyway. RTAB would have to
> > remain for backwards compatibility, of course.
>
> Can you describe in more detail?
OK, but first I want to make the point that the only
reason I suggest this is to get some sort of ATM
patch into the kernel, as the current patch on the
table is having a rough time.
Alan Cox made the point earlier (if I understood him
correctly) that this tabling lookup probably isn't
a big win on modern CPU's - we may be better off
moving it all into the kernel. Thinking about this,
I tried to come up with a way of describing the
mapping between skb->len and the on the wire packet
length for every protocol I know. This is what I
came up with.
Assume we have a packet length L, which is to be
transported by some protocol. For now we consider
one protocol only, ie: TCP, PPP, ATM, Ethernet or
whatever. I will generalise it to multiple protocols
later. I think a generalised transformation can be
made using using 5 numbers which are applied in this
order:
Overhead - A fixed overhead that is added to L.
Mpu - Minimum packet size. If the result of
(Overhead+L) is smaller that this, then
the new result becomes this size.
Round - The result is then rounded up to this
many bytes. For protocols that always
transmit single bytes this figure would be
1. If there were some protocol that
transmitted data as 4 byte chunks then this
would be 4. For ATM it is 48.
CellPay - If the packet is broken down into smaller
packets when sent, then this is the amount
of data that will fit into each chunk.
CallOver - This is the additional overhead each cell
carries.
The idea is the kernel would do this calculation on the
fly for each packet. If you represent this set of number
numbers as a comma separated list in the order they were
presented above, then here are some examples:
IP: 20
Ethernet: 18,64
PPP: 2
ATM: 0,0,48,48,5
It may be that 5 numbers are a overkill. It is for all
protocols I am aware of - for those you could get away
with 4. But I am no expert.
The next step is to generalise for many protocols. As
the protocols are stacked the length output by one
protocol becoming the input length for the downstream
one. So we just need to apply the same transformation
serially. I will use '+' to indicate the stacking. For
a typical ATM stack, PPPoE over LLC, we have:
ppp:2+pppoe:6+ethernet:14,64+llc:8+all5:4+atm:0,0,48,48,5
If this were implemented naively, then the kernel would
have to apply the above calculation 6 times, like this:
Protocol InputLength OutputLength
--------- ------------ ----------------
ppp skb->len skb->len+2
pppoe: skb->len+2 skb->len+2+6
ethernet: skb->len+2+6 skb->len+2+6+14
... and so on.
But it can be optimised. In this particular case we can
combine those six operations into 1:
adsl_pppoe_llc:34,64,48,48,5
The five numbers have the same meaning as before. It
it not difficult to come up with a generalised rule that
allows you to do this for most cases. For the remainder
(if they exist - I can't think of any) the kernel would
have to apply the transformation iteratively.
Before going on, it is worth while comparing this to the
current RTAB solution (and by implication STAB):
1. Oddly, the number of steps and hence speed for
common protocols is probably the same. Compare:
RTAB - You have to add an OverHead in the general
case.
- You have to scale by cell_log.
- You have to ensure the overhead+skb->len
doesn't overflow / underflow the RTAB.
- You have to do the lookup.
New - You have to add overhead.
- You have to check the MPU.
- You have to check if you have to apply
Round,CellPay,CellOver - but you won't
have to for any protocol except ATM.
2. Because of the cell_log, RTAB gives an 100% accurate
answer 1 time in every (1<<cell_log) packet lengths.
The new version is always 100% accurate.
3. The new version isn't as flexible as RTAB, as least
from the kernels point of view. Conceivably there are
protocols that could be handled by RTAB that are not
handled by the new one. Since RTAB is computed in
user space, this implies these new protocols might
be handled by a user space change only. The new
version would always require a kernel change. Note
however that even RTAB required a kernel change for
ATM, however.
So far we have what your STAB would provide us with - a
way to calculate the packet length. It takes 5 int's for
every protocol stack I can think of. It probably runs
faster for most protocols but is less robust to the
introduction of new protocols.
But some qdisc's need to know how long it takes to send a
packet. This is what RTAB provides us with, in fact.
So if we were to do away with RTAB completely, then we need
a way for the kernel to covert packet lengths into the time
it takes to send a packet. This is what I discuss next.
The comments apply to both STAB and the new algorithm above,
as they both compute packet lengths.
If J is the time it takes to send one byte over a link,
then we can compute RTAB from STAB like this:
for (int i = 0; i < array_length(STAB); i += 1)
RTAB[i] = STAB[i] * J;
This is exactly the operation "tc" performs now in user
space. It is possibly in user space because J is usually
less than 1, and thus is most conveniently represented as
a floating point number. Floating point operations in
the kernel are verboten.
I can think of two ways to move this operation into the
kernel. The straight forward way is to represent J as a
scale and a division. Ie the kernel does:
RTAB[i] = (STAB[i] << scale) / divisor.
The second way depends on that fact that most CPU's can
multiply two 32 uint's to produce a 64 bit result in a
single operation. I don't know whether this operation is
available to kernel code. But if it is, J can be
represented as a 32 bit fixed point number, with the
implied decimal point after the most significant 8 bits.
Then this operation would suffice:
extern long long mul64(unsigned long, a, unsigned long b);
RTAB[i] = (unsigned long)(mul64(STAB[i], J) >> 24);
This method doesn't use division, and is probably faster
on lower end CPU's. It would handle 100G Ethernet on a
machine with Hz == 1000, and 1200 bits/sec on a machine
with Hz == 10000.
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
