Subject: [aqm] Quick Code review: CoDel and FQ-CoDel for FreeBSD's ipfw/dummynet

From: Dave Täht <[email-masked]>
Date: Tue, 1 Mar 2016 14:30:31 -0800

I had a chance to look over this patch last night.

http://caia.swin.edu.au/freebsd/aqm/patches/dummynet-aqm-patch-0.1-freebsd11-r295345.patch

My comments are by no means complete.

The BSD implementation has a few substantial differences from the Linux
implementation, but I'm not sure if further clarifying the internet
draft is needed or not.

I think section C1 below is potentially the only thing majorly wrong
with the BSD implementation, and that maybe I'm just not reading the
code right. Well... section F - ecn support - looks very wrong.

A) The BSD fq_codel implementation has 1 ms (jiffies) timestamp
resolution, (the ns2 one was floating point, the linux version (nanosec
>> 10), and cake uses nsec.[1])

In the draft we merely suggest a resolution "less than the target".

I am a little uncomfortable with 1 ms resolution as those trying to use
codel in DCs have used target and interval settings of 500us and 10ms.
Have not seen anyone publish anything using that however...

We have no real data on coarser resolutions. The initial tests at low
rates with this code appeared to work, I'd be interested
in seeing behaviors at 100mbit+.

and: Does freebsd have no higher precision timers available?

B) this initial BSD fq_codel implementation only extracts the 5 tuple
from tcp and udp packets on ipv6 and ipv4.

As this is the minimum suggested in the draft... and covers a huge
percentage of internet traffic, I'm cool with this.

Over time, however, the linux version has peered more deeply into the 5
tuple, covering encapsulations for ipv6, v4, gre0, and udplite, sctp, etc.

Otherwise it falls back to merely hashing the src/dst ips which is quite
ok in many scenarios, as does the bsd verson.

Recent additions to the linux hashing api include vlan ids and mpls
support, but those have not quite made it to the userspace tc utility.

We touch upon the potential need for hashing on alternate fields in the
draft and I would hope to see similar extensions emerge for the bsd
version over time.

udplite support, in particular, is a one liner to add to the relevant
IPPROTO_UDP case statements.

C) BSD fq_codel's hash is better than linux's default (until recently)
as it uses all the fields in ipv6 sanely.

Linux's construction of the hash originally for ipv6 was very poor,
which has improved a few times, and a subset of the new hashing API in
linux 4.2 and later is equivalent to this BSD implementation.

Again, so long as a good hash with avalanche properties is used, and
combined with a permuted hash, we're good. The jenkins hash used here
and in linux is good. But:

C1) I am not sure what HASHINIT does? I otherwise do not see code that
permutes the hash. (I know full well that the random permutation on
setup requirement in fq_codel makes it hard to have repeatable tests! -
but for shipping code it should be there)

D) The ipv6 support could be improved in that ipv6 can contain multiple
headers and the last decodable one could be used.

E) count is 16 bits here, 32 bits in linux. Damned if I know what the
net effect of that is. We used saturating arithmetic in cake but it's
really hard to hit it at 32 bits.

F) I think the ecn support is wrong in that the ECT marked packet needs
to be returned here, where instead no matter what, another packet is
dequeued. This leaks memory and never does anything sane with ecn.

while (now >= cst->drop_next_time && cst->dropping) {
+
+			if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) {
+				update_stats(q, 0, 1);
+				FREE_PKT(m);
+			}
+
+			m = codel_dodequeue(q, now, &ok_to_drop);

I do have the ability to run freebsd in a VM, however my last attempt at
building a kernel for it was a disaster - if there is a freebsd kernel
binary to try, I can try that....

[1] Cake uses nsec in the codel portion only because it needed a high
precision timestamp for the shaper portion of the code and the now
variable is reused throughout.

---

From: Jonathan Morton <[email-masked]>
Date: Wed, 2 Mar 2016 00:33:50 +0200

> On 2 Mar, 2016, at 00:30, Dave Täht <[email-masked]> wrote:
> 

Count used to be 16 bits in Linux too, and you noticed very bad effects in the "50:1 flows, 1:10 bandwidth" test which were corrected when I added the saturated arithmetic.  The change to a 32-bit count came after that.

 - Jonathan Morton

---

From: Dave Täht <[email-masked]>
Date: Tue, 1 Mar 2016 16:26:21 -0800

C1) Ah, the perturbation (salt) is applied to a section of the
to-be-hashed content, and then the whole thing is hashed in one go.

Gotta say I find the casting confusing, and does this end up being a 16
bit permute (rather than 24 or 32)? The unaligned accesses here might be
issues on some platforms. Perhaps 24 bits of permute and align the rest?

*((uint16_t *) &tuple[1]) = si->perturbation;

+	*((uint8_t *) &tuple[0]) = ip->ip_p;
+	*((uint16_t *) &tuple[1]) = si->perturbation;
+	*((uint32_t *) &tuple[3]) = ip->ip_src.s_addr;
+	*((uint32_t *) &tuple[7]) = ip->ip_dst.s_addr;

F) the ecn_mark code still definitely looks wrong to me.

Some new stuff

+		fqc_cfg->quantum = BOUND_VAR(fqc_cfg->quantum,256,6056);

We have not seen much need for smaller quantums than 256. I am not sure
where the 6056 figure comes from.

+		fqc_cfg->limit= BOUND_VAR(fqc_cfg->limit,1,20480);

Ahh, let's start aiming for 40gb links.

+		fqc_cfg->flows_cnt= BOUND_VAR(fqc_cfg->flows_cnt,1,65536);

Given that you are using modulo in the code this is ok, but enforcing a
power of two here and using an and elsewhere might be good.

---

From: Rasool Al-Saadi <[email-masked]>
Date: Mon, 7 Mar 2016 02:44:48 +0000

> -----Original Message-----
> From: [email-masked] [mailto:owner-freebsd-
> [email-masked]] On Behalf Of Don Lewis
> Sent: Monday, 7 March 2016 7:41 AM
> To: Rasool Al-Saadi <[email-masked]>
> Cc: [email-masked]; Grenville Armitage
> <[email-masked]>; [email-masked]; [email-masked]
> Subject: Re: Dummynet AQM v0.1- CoDel and FQ-CoDel for FreeBSD's
> ipfw/dummynet
> 
> On 26 Feb, Rasool Al-Saadi wrote:
> > Dear all,
> >
> > I would like to announce that we (myself and Grenville Armitage)
> > released Dummynet AQM v0.1, which is an independent implementation
> of
> > CoDel and FQ-CoDel for FreeBSD's ipfw/dummynet framework, based on
> the
> > IETF  CoDel [1] and FQ-CoDel [2] Internet-Drafts. We prepared patches
> > for FreeBSD11-CURRENT-r295345  and FreeBSD 10.x-RELEASE (10.0, 10.1,
> > 10.2), and a technical report  of our implementation.
> >
> > Patches and documentation can be found in:
> > http://caia.swin.edu.au/freebsd/aqm
> 
> The FreeBSD 10 patch applies cleanly to FreeBSD 10.3-PRERELEASE, but the
> build fails on i386:
> 
> /usr/src/sbin/ipfw/dummynet.c:166:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[0],
>                                 ^~~~~~~~~~
> /usr/src/sbin/ipfw/dummynet.c:167:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[1] );
>                                 ^~~~~~~~~~
> /usr/src/sbin/ipfw/dummynet.c:177:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[0],
>                                 ^~~~~~~~~~
> /usr/src/sbin/ipfw/dummynet.c:178:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[1],
>                                 ^~~~~~~~~~
> /usr/src/sbin/ipfw/dummynet.c:179:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[3],
>                                 ^~~~~~~~~~
> /usr/src/sbin/ipfw/dummynet.c:180:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[4],
>                                 ^~~~~~~~~~
> /usr/src/sbin/ipfw/dummynet.c:181:5: error: format specifies type 'long' but
> the argument has type 'int64_t' (aka 'long long') [-Werror,-Wformat]
>                                 ep->par[5]
>                                 ^~~~~~~~~~
> 
> 
> The proper fix for this on FreeBSD is to cast these values to intmax_t and use
> the %jd printf format.
> 

Thanks for testing the patch and fixing the problem. We will apply your fix to the next version of our patch.

Regards,
Rasool

---

From: Don Lewis <[email-masked]>
Date: Thu, 10 Mar 2016 00:28:48 -0800 (PST)

On 26 Feb, Rasool Al-Saadi wrote:
> Dear all,
> 
> I would like to announce that we (myself and Grenville Armitage) released Dummynet AQM v0.1, which is an independent implementation of CoDel and FQ-CoDel for FreeBSD's ipfw/dummynet framework, based on the IETF  CoDel [1] and FQ-CoDel [2] Internet-Drafts.
> We prepared patches for FreeBSD11-CURRENT-r295345  and FreeBSD 10.x-RELEASE (10.0, 10.1, 10.2), and a technical report  of our implementation.
> 
> Technical report:
> http://caia.swin.edu.au/reports/160226A/CAIA-TR-160226A.pdf

I've got some results with running this on my firewall in an attempt to
tame a severe bufferbloat problem on my ADSL connection to the outside
world.

The raw speed numbers reported by my ADSL modem are 6016 Kb/s downstream
and 768 Kb/s upstream.  I set my MTU to 1492 to avoid fragmentation from
PPPoE overhead.

Using <http://www.dslreports.com/speedtest> with things unthrottled, I
observe about 5050 Kb/s downstream and 648Kb/s upstream, with a
bufferbloat rating of F.

I configured the system to use FQ-CoDel, with separate pipes for each
direction.  Because of the slow upstream speed, I increased the target
value for the upstream direction to 25 ms since a maximum size packet
will require about 20 ms to send.  I also set the
net.inet.tcp.experimental.initcwnd10 sysctl value to 0.  The latter
seemed to help a lot.  With this feature enabled, the initial packet
blast at the start of the upload caused a large initial latency spike,
and the initial transfer rate ended up being very slow and it took a
long time to ramp up to its maximum sustained value.

My current dummynet pipe bandwidth settings are 4800 Kb/s downstream and
615 Kb/s upstream.  The speedtest results for these settings are
about 4600 Kb/s downstream and about 600 Kb/s upstream.  I'm somewhat
disappointed in the bandwith loss, but my bufferbloat rating has
improved to mostly A's with some B's.

I do still see a large increase in latency at the start of transfers,
and then it oscillates for a while before settling down at a reasonable
value for the remainder of the transfer.  I suspect this is to be
expected.

It would be nice if the implementation was able to account for the PPPOE
and ATM framing overhead like the Linux implementation does.  I think
that would help performance when there is a mix of packet sizes.