[Cake] fq_codel_fast

[Cake] fq_codel_fast

[Dave Taht]

It has been a long time since I profiled the kernel on small platforms.

* tc filtering has got rcu'd
* routing lookup code "improved"
* flow dissector grew massively
* fq_codel grew "features"

Anyway, this should be a drop in replacement (presently) for fq_codel,
that compiles out of tree and rips out almost everything I don't like.

https://github.com/dtaht/fq_codel_fast

I think the tc filter thing really hurt us in cake.

gonna go profile, then maybe add in ye olde shaper

-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] fq_codel_fast

[Pete Heist]

[-- Attachment #1: Type: text/plain, Size: 575 bytes --]


> On Aug 29, 2018, at 3:04 AM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> Anyway, this should be a drop in replacement (presently) for fq_codel,
> that compiles out of tree and rips out almost everything I don't like.
> 
> https://github.com/dtaht/fq_codel_fast

Cool…I’d give it a quick run but it doesn’t compile for me (attached). Kernel version?

> I think the tc filter thing really hurt us in cake.

It would be interesting to see how much. Jon also expressed concern and I’d been meaning to try some benchmarks before and after that change…


[-- Attachment #2: fq_codel_fast_compile.txt --]
[-- Type: text/plain, Size: 2969 bytes --]

root@ubuntu:~/src/fq_codel_fast$ make
make -C /lib/modules/4.15.0-33-generic/build SUBDIRS=/root/src/fq_codel_fast modules LDFLAGS_MODULE="--build-id=0xa524fc2e39dc291199b9b04fb890ea1548f17641" CFLAGS_MODULE="-DCAKE_VERSION=\\\"a524fc2e39dc291199b9b04fb890ea1548f17641\\\""
make[1]: Entering directory '/usr/src/linux-headers-4.15.0-33-generic'
  CC [M]  /root/src/fq_codel_fast/sch_fq_codel.o
/root/src/fq_codel_fast/sch_fq_codel.c: In function ‘fq_codel_init’:
/root/src/fq_codel_fast/sch_fq_codel.c:444:8: error: too many arguments to function ‘tcf_block_get’
  err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
        ^~~~~~~~~~~~~
In file included from /root/src/fq_codel_fast/sch_fq_codel.c:26:0:
./include/net/pkt_cls.h:41:5: note: declared here
 int tcf_block_get(struct tcf_block **p_block,
     ^~~~~~~~~~~~~
/root/src/fq_codel_fast/sch_fq_codel.c:449:14: error: implicit declaration of function ‘kvcalloc’; did you mean ‘kvzalloc’? [-Werror=implicit-function-declaration]
   q->flows = kvcalloc(FQ_FLOWS,
              ^~~~~~~~
              kvzalloc
/root/src/fq_codel_fast/sch_fq_codel.c:449:12: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
   q->flows = kvcalloc(FQ_FLOWS,
            ^
/root/src/fq_codel_fast/sch_fq_codel.c:456:15: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
   q->backlogs = kvcalloc(FQ_FLOWS, sizeof(u32), GFP_KERNEL);
               ^
/root/src/fq_codel_fast/sch_fq_codel.c: At top level:
/root/src/fq_codel_fast/sch_fq_codel.c:652:15: error: initialization from incompatible pointer type [-Werror=incompatible-pointer-types]
  .tcf_block = fq_codel_tcf_block,
               ^~~~~~~~~~~~~~~~~~
/root/src/fq_codel_fast/sch_fq_codel.c:652:15: note: (near initialization for ‘fq_codel_class_ops.tcf_block’)
/root/src/fq_codel_fast/sch_fq_codel.c:667:11: error: initialization from incompatible pointer type [-Werror=incompatible-pointer-types]
  .init  = fq_codel_init,
           ^~~~~~~~~~~~~
/root/src/fq_codel_fast/sch_fq_codel.c:667:11: note: (near initialization for ‘fq_codel_qdisc_ops.init’)
/root/src/fq_codel_fast/sch_fq_codel.c:670:13: error: initialization from incompatible pointer type [-Werror=incompatible-pointer-types]
  .change  = fq_codel_change,
             ^~~~~~~~~~~~~~~
/root/src/fq_codel_fast/sch_fq_codel.c:670:13: note: (near initialization for ‘fq_codel_qdisc_ops.change’)
cc1: some warnings being treated as errors
scripts/Makefile.build:339: recipe for target '/root/src/fq_codel_fast/sch_fq_codel.o' failed
make[2]: *** [/root/src/fq_codel_fast/sch_fq_codel.o] Error 1
Makefile:1552: recipe for target '_module_/root/src/fq_codel_fast' failed
make[1]: *** [_module_/root/src/fq_codel_fast] Error 2
make[1]: Leaving directory '/usr/src/linux-headers-4.15.0-33-generic'
Makefile:8: recipe for target 'default' failed
make: *** [default] Error 2

Re: [Cake] fq_codel_fast

[Dave Taht]

I'm presently compiling against net-next.
On Wed, Aug 29, 2018 at 1:12 AM Pete Heist <pete@heistp.net> wrote:
>
>
> > On Aug 29, 2018, at 3:04 AM, Dave Taht <dave.taht@gmail.com> wrote:
> >
> > Anyway, this should be a drop in replacement (presently) for fq_codel,
> > that compiles out of tree and rips out almost everything I don't like.
> >
> > https://github.com/dtaht/fq_codel_fast
>
> Cool…I’d give it a quick run but it doesn’t compile for me (attached). Kernel version?
>
> > I think the tc filter thing really hurt us in cake.
>
> It would be interesting to see how much. Jon also expressed concern and I’d been meaning to try some benchmarks before and after that change…
>


-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] fq_codel_fast

[Dave Taht]

This version does indeed work against net-next. I managed to break
myself because I'd been fiddling with flows 32 in some cases, and my
version
returns ENOTSUPP for that which sqm doesn't catch... and ohhh....
boy... htb with a 1000 packet fifo buffer fallback... SUCKS! :)

As for profiling, once again I found myself distracted by the ecn
debate. Fitting ecn 500 flows through a 100mbit bottleneck results in
1300 packets outstanding
26 flows that can't start (presumably due to ecn fall back), and
without ecn, 450 packets outstanding 3 flows that can't start.

On Wed, Aug 29, 2018 at 7:23 AM Dave Taht <dave.taht@gmail.com> wrote:
>
> I'm presently compiling against net-next.
> On Wed, Aug 29, 2018 at 1:12 AM Pete Heist <pete@heistp.net> wrote:
> >
> >
> > > On Aug 29, 2018, at 3:04 AM, Dave Taht <dave.taht@gmail.com> wrote:
> > >
> > > Anyway, this should be a drop in replacement (presently) for fq_codel,
> > > that compiles out of tree and rips out almost everything I don't like.
> > >
> > > https://github.com/dtaht/fq_codel_fast
> >
> > Cool…I’d give it a quick run but it doesn’t compile for me (attached). Kernel version?
> >
> > > I think the tc filter thing really hurt us in cake.
> >
> > It would be interesting to see how much. Jon also expressed concern and I’d been meaning to try some benchmarks before and after that change…
> >
>
>
> --
>
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619



-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] fq_codel_fast

[Pete Heist]

[-- Attachment #1: Type: text/plain, Size: 2841 bytes --]

Interesting, sounds like a good data point for the ECN debate. I wonder if that pathology happens at lower flow counts.

I’ve been getting into FreeNet’s backhaul. Four of their backhaul links, the orange lines in the following map, are licensed spectrum full-duplex 100Mbit wireless links (not sure what tech, I’ll ask). I’ve so far not witnessed any bloat in these links because they seem to be over-provisioned based on the rates of the CPE connections, although that may change as AC is increasingly deployed.

http://mapa.czfree.net/#lat=50.76176199690661&lng=15.06277084350586&zoom=13&autofilter=1&type=satellite&geolocate=98%7C114%7C111%7C117%7C109%7C111%7C118%7C115%7C107%7C97&node=6101&aponly=1&bbonly=1&actlink=1&actnode=1&tilt=0&heading=0& <http://mapa.czfree.net/#lat=50.76176199690661&lng=15.06277084350586&zoom=13&autofilter=1&type=satellite&geolocate=98|114|111|117|109|111|118|115|107|97&node=6101&aponly=1&bbonly=1&actlink=1&actnode=1&tilt=0&heading=0&>

Active flow counts appear to be in the tens sometimes, probably not hundreds very often, from what I’ve witnessed so far...

> On Aug 30, 2018, at 8:24 PM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> This version does indeed work against net-next. I managed to break
> myself because I'd been fiddling with flows 32 in some cases, and my
> version
> returns ENOTSUPP for that which sqm doesn't catch... and ohhh....
> boy... htb with a 1000 packet fifo buffer fallback... SUCKS! :)
> 
> As for profiling, once again I found myself distracted by the ecn
> debate. Fitting ecn 500 flows through a 100mbit bottleneck results in
> 1300 packets outstanding
> 26 flows that can't start (presumably due to ecn fall back), and
> without ecn, 450 packets outstanding 3 flows that can't start.
> 
> On Wed, Aug 29, 2018 at 7:23 AM Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> I'm presently compiling against net-next.
>> On Wed, Aug 29, 2018 at 1:12 AM Pete Heist <pete@heistp.net> wrote:
>>> 
>>> 
>>>> On Aug 29, 2018, at 3:04 AM, Dave Taht <dave.taht@gmail.com> wrote:
>>>> 
>>>> Anyway, this should be a drop in replacement (presently) for fq_codel,
>>>> that compiles out of tree and rips out almost everything I don't like.
>>>> 
>>>> https://github.com/dtaht/fq_codel_fast
>>> 
>>> Cool…I’d give it a quick run but it doesn’t compile for me (attached). Kernel version?
>>> 
>>>> I think the tc filter thing really hurt us in cake.
>>> 
>>> It would be interesting to see how much. Jon also expressed concern and I’d been meaning to try some benchmarks before and after that change…
>>> 
>> 
>> 
>> --
>> 
>> Dave Täht
>> CEO, TekLibre, LLC
>> http://www.teklibre.com
>> Tel: 1-669-226-2619
> 
> 
> 
> -- 
> 
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619


[-- Attachment #2: Type: text/html, Size: 4447 bytes --]

Re: [Cake] fq_codel_fast

[Dave Taht]

There was a very good paper or two (I think luca co-authored one) that
showed that "active flows" were generally measured in the mid 200s in
nearly any scenario. I agreed with that which was in part why I felt
we could stick
with 1024 queues, a direct mapped hash, and a couple collisions.

cake can falsify that conclusion, or not - at least with ecn enabled,
it does falsify it. I think. Can't remember the paper's name....

whether or not accepting 3x more delay as in this case is good,
well... more measurements await via
https://www.bufferbloat.net/projects/ecn-sane/wiki/ and the ecn-sane
mailing list is now active.

My original cake code dropped ecn on overload. I tended to think a
little ecn a good thing.


On Thu, Sep 6, 2018 at 10:10 AM Pete Heist <pete@heistp.net> wrote:
>
> Interesting, sounds like a good data point for the ECN debate. I wonder if that pathology happens at lower flow counts.
>
> I’ve been getting into FreeNet’s backhaul. Four of their backhaul links, the orange lines in the following map, are licensed spectrum full-duplex 100Mbit wireless links (not sure what tech, I’ll ask). I’ve so far not witnessed any bloat in these links because they seem to be over-provisioned based on the rates of the CPE connections, although that may change as AC is increasingly deployed.
>
> http://mapa.czfree.net/#lat=50.76176199690661&lng=15.06277084350586&zoom=13&autofilter=1&type=satellite&geolocate=98%7C114%7C111%7C117%7C109%7C111%7C118%7C115%7C107%7C97&node=6101&aponly=1&bbonly=1&actlink=1&actnode=1&tilt=0&heading=0&
>
> Active flow counts appear to be in the tens sometimes, probably not hundreds very often, from what I’ve witnessed so far...
>
> On Aug 30, 2018, at 8:24 PM, Dave Taht <dave.taht@gmail.com> wrote:
>
> This version does indeed work against net-next. I managed to break
> myself because I'd been fiddling with flows 32 in some cases, and my
> version
> returns ENOTSUPP for that which sqm doesn't catch... and ohhh....
> boy... htb with a 1000 packet fifo buffer fallback... SUCKS! :)
>
> As for profiling, once again I found myself distracted by the ecn
> debate. Fitting ecn 500 flows through a 100mbit bottleneck results in
> 1300 packets outstanding
> 26 flows that can't start (presumably due to ecn fall back), and
> without ecn, 450 packets outstanding 3 flows that can't start.
>
> On Wed, Aug 29, 2018 at 7:23 AM Dave Taht <dave.taht@gmail.com> wrote:
>
>
> I'm presently compiling against net-next.
> On Wed, Aug 29, 2018 at 1:12 AM Pete Heist <pete@heistp.net> wrote:
>
>
>
> On Aug 29, 2018, at 3:04 AM, Dave Taht <dave.taht@gmail.com> wrote:
>
> Anyway, this should be a drop in replacement (presently) for fq_codel,
> that compiles out of tree and rips out almost everything I don't like.
>
> https://github.com/dtaht/fq_codel_fast
>
>
> Cool…I’d give it a quick run but it doesn’t compile for me (attached). Kernel version?
>
> I think the tc filter thing really hurt us in cake.
>
>
> It would be interesting to see how much. Jon also expressed concern and I’d been meaning to try some benchmarks before and after that change…
>
>
>
> --
>
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619
>
>
>
>
> --
>
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619
>
>


-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] fq_codel_fast

[Sebastian Moeller]

Hi Dave,



> On Sep 6, 2018, at 19:22, Dave Taht <dave.taht@gmail.com> wrote:
> 
> There was a very good paper or two (I think luca co-authored one) that
> showed that "active flows" were generally measured in the mid 200s in
> nearly any scenario. I agreed with that which was in part why I felt
> we could stick
> with 1024 queues, a direct mapped hash, and a couple collisions.
> 
> cake can falsify that conclusion, or not - at least with ecn enabled,
> it does falsify it. I think. Can't remember the paper's name....

	I believe you are looking for ( https://team.inria.fr/rap/files/2013/12/KMOR04.pdf ):
"On the Scalability of Fair Queueing"

Best Regards
	Sebastian


> 
> whether or not accepting 3x more delay as in this case is good,
> well... more measurements await via
> https://www.bufferbloat.net/projects/ecn-sane/wiki/ and the ecn-sane
> mailing list is now active.
> 
> My original cake code dropped ecn on overload. I tended to think a
> little ecn a good thing.
> 
> 
> On Thu, Sep 6, 2018 at 10:10 AM Pete Heist <pete@heistp.net> wrote:
>> 
>> Interesting, sounds like a good data point for the ECN debate. I wonder if that pathology happens at lower flow counts.
>> 
>> I’ve been getting into FreeNet’s backhaul. Four of their backhaul links, the orange lines in the following map, are licensed spectrum full-duplex 100Mbit wireless links (not sure what tech, I’ll ask). I’ve so far not witnessed any bloat in these links because they seem to be over-provisioned based on the rates of the CPE connections, although that may change as AC is increasingly deployed.
>> 
>> http://mapa.czfree.net/#lat=50.76176199690661&lng=15.06277084350586&zoom=13&autofilter=1&type=satellite&geolocate=98%7C114%7C111%7C117%7C109%7C111%7C118%7C115%7C107%7C97&node=6101&aponly=1&bbonly=1&actlink=1&actnode=1&tilt=0&heading=0&
>> 
>> Active flow counts appear to be in the tens sometimes, probably not hundreds very often, from what I’ve witnessed so far...
>> 
>> On Aug 30, 2018, at 8:24 PM, Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> This version does indeed work against net-next. I managed to break
>> myself because I'd been fiddling with flows 32 in some cases, and my
>> version
>> returns ENOTSUPP for that which sqm doesn't catch... and ohhh....
>> boy... htb with a 1000 packet fifo buffer fallback... SUCKS! :)
>> 
>> As for profiling, once again I found myself distracted by the ecn
>> debate. Fitting ecn 500 flows through a 100mbit bottleneck results in
>> 1300 packets outstanding
>> 26 flows that can't start (presumably due to ecn fall back), and
>> without ecn, 450 packets outstanding 3 flows that can't start.
>> 
>> On Wed, Aug 29, 2018 at 7:23 AM Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> 
>> I'm presently compiling against net-next.
>> On Wed, Aug 29, 2018 at 1:12 AM Pete Heist <pete@heistp.net> wrote:
>> 
>> 
>> 
>> On Aug 29, 2018, at 3:04 AM, Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> Anyway, this should be a drop in replacement (presently) for fq_codel,
>> that compiles out of tree and rips out almost everything I don't like.
>> 
>> https://github.com/dtaht/fq_codel_fast
>> 
>> 
>> Cool…I’d give it a quick run but it doesn’t compile for me (attached). Kernel version?
>> 
>> I think the tc filter thing really hurt us in cake.
>> 
>> 
>> It would be interesting to see how much. Jon also expressed concern and I’d been meaning to try some benchmarks before and after that change…
>> 
>> 
>> 
>> --
>> 
>> Dave Täht
>> CEO, TekLibre, LLC
>> http://www.teklibre.com
>> Tel: 1-669-226-2619
>> 
>> 
>> 
>> 
>> --
>> 
>> Dave Täht
>> CEO, TekLibre, LLC
>> http://www.teklibre.com
>> Tel: 1-669-226-2619
>> 
>> 
> 
> 
> -- 
> 
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] fq_codel_fast

[Pete Heist]

> On Sep 6, 2018, at 7:22 PM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> There was a very good paper or two (I think luca co-authored one) that
> showed that "active flows" were generally measured in the mid 200s in
> nearly any scenario. I agreed with that which was in part why I felt
> we could stick
> with 1024 queues, a direct mapped hash, and a couple collisions.

So I’m not sure if this is a great way to gauge active flow counts through a router, but at 8pm:

root@FreeNetVysina:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
446
FreeNetJerab:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
181
FreeNetOldrichova:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
228

Far from my estimate of tens. Many of those can be idle connections, I suspect. 60-80% of them are http/s.

Re: [Cake] fq_codel_fast

[Dave Taht]

re: conntrack - I think the udp standard for holding a hole punch open
is 2-3 minutes. I've
seen 30 sec or less in the field.

On Thu, Sep 6, 2018 at 11:36 AM Pete Heist <pete@heistp.net> wrote:
>
>
> > On Sep 6, 2018, at 7:22 PM, Dave Taht <dave.taht@gmail.com> wrote:
> >
> > There was a very good paper or two (I think luca co-authored one) that
> > showed that "active flows" were generally measured in the mid 200s in
> > nearly any scenario. I agreed with that which was in part why I felt
> > we could stick
> > with 1024 queues, a direct mapped hash, and a couple collisions.
>
> So I’m not sure if this is a great way to gauge active flow counts through a router, but at 8pm:
>
> root@FreeNetVysina:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
> 446
> FreeNetJerab:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
> 181
> FreeNetOldrichova:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
> 228
>
> Far from my estimate of tens. Many of those can be idle connections, I suspect. 60-80% of them are http/s.
>


-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Cake] fq_codel_fast

[Sebastian Moeller]

That means that the conntrack numbers give an upper bound, no?

Best Regards
	Sebastian

> On Sep 6, 2018, at 20:40, Dave Taht <dave.taht@gmail.com> wrote:
> 
> re: conntrack - I think the udp standard for holding a hole punch open
> is 2-3 minutes. I've
> seen 30 sec or less in the field.
> 
> On Thu, Sep 6, 2018 at 11:36 AM Pete Heist <pete@heistp.net> wrote:
>> 
>> 
>>> On Sep 6, 2018, at 7:22 PM, Dave Taht <dave.taht@gmail.com> wrote:
>>> 
>>> There was a very good paper or two (I think luca co-authored one) that
>>> showed that "active flows" were generally measured in the mid 200s in
>>> nearly any scenario. I agreed with that which was in part why I felt
>>> we could stick
>>> with 1024 queues, a direct mapped hash, and a couple collisions.
>> 
>> So I’m not sure if this is a great way to gauge active flow counts through a router, but at 8pm:
>> 
>> root@FreeNetVysina:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
>> 446
>> FreeNetJerab:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
>> 181
>> FreeNetOldrichova:~# grep ESTABLISHED /proc/net/ip_conntrack | wc -l
>> 228
>> 
>> Far from my estimate of tens. Many of those can be idle connections, I suspect. 60-80% of them are http/s.
>> 
> 
> 
> -- 
> 
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] fq_codel_fast

[Toke Høiland-Jørgensen]

Pete Heist <pete@heistp.net> writes:

>> On Sep 6, 2018, at 7:22 PM, Dave Taht <dave.taht@gmail.com> wrote:
>> 
>> There was a very good paper or two (I think luca co-authored one) that
>> showed that "active flows" were generally measured in the mid 200s in
>> nearly any scenario. I agreed with that which was in part why I felt
>> we could stick
>> with 1024 queues, a direct mapped hash, and a couple collisions.
>
> So I’m not sure if this is a great way to gauge active flow counts
> through a router, but at 8pm:

In the context of that paper you'd need to count the number of active
queues in fq_codel.

So `tc class show dev $DEV` and see how many classes are displayed...

-Toke