<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Mar 3, 2017 at 12:21 AM, Dave Taht <span dir="ltr"><<a href="mailto:dave.taht@gmail.com" target="_blank">dave.taht@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">As this is devolving into a cake specific discussion, removing the<br>
lede mailing list.<br>
<span class=""><br>
On Thu, Mar 2, 2017 at 9:49 PM, Jonathan Morton <<a href="mailto:chromatix99@gmail.com">chromatix99@gmail.com</a>> wrote:<br>
><br>
>> On 3 Mar, 2017, at 07:00, Eric Luehrsen <<a href="mailto:ericluehrsen@hotmail.com">ericluehrsen@hotmail.com</a>> wrote:<br>
>><br>
>> That's not what I was going for. Agree, it would not be good to depend<br>
>> on an inferior hash. You mentioned divide as a "cost." So I was<br>
>> proposing a thought around a "benefit" estimate. If hash collisions are<br>
>> not as important (or are they), then what is "benefit / cost?"<br>
><br>
> The computational cost of one divide is not the only consideration I have in mind.<br>
><br>
> Cake’s set-associative hash is fundamentally predicated on the number of hash buckets *not* being prime, as it requires further decomposing the hash into a major and minor part when a collision is detected.  The minor part is then iterated to try to locate a matching or free bucket.<br>
><br>
> This is considerably easier to do and reason about when everything is a power of two.  Then, modulus is a masking operation, and divide is a shift, either of which can be done in one cycle flat.<br>
><br>
> AFAIK, however, the main CPU cost of the hash function in Cake is not the hash itself, but the packet dissection required to obtain the data it operates on.  This is something a profile would shed more light on.<br>
<br>
</span>Tried. Mips wasn't a good target.<br>
<br>
The jhash3 setup cost is bad, but I agree flow dissection can be<br>
deeply expensive. As well as the other 42+ functions a packet needs to<br>
traverse to get from ingress to egress.<br>
<br>
But staying on hashing:<br>
<br>
One thing that landed 4.10? 4.11? was fq_codel relying on a skb->hash<br>
if one already existed (injected already by tcp, or by hardware, or<br>
the tunneling tool). we only need to compute a partial hash on the<br>
smaller subset of keys in that case (if we can rely on the skb->hash<br>
which we cannot do in the nat case)<br>
<br>
Another thing I did, long ago, was read the (60s-era!) liturature<br>
about set-associative cpu cache architectures... and...<br>
<br>
In all of these cases I really, really wanted to just punt all this<br>
extra work to hardware in ingress - computing 3 hashes can be easily<br>
done in parallel there and appended to the packet as it completes.<br>
<br>
I have been working quite a bit more with the arm architecture of<br>
late, and the "perf" profiler over there is vastly better than the<br>
mips one we've had.<br>
<br>
(and aarch64 is *nice*. So is NEON)<br>
<br>
- but I hadn't got around to dinking with cake there until yesterday.<br>
<br>
One thing I'm noticing is that even the gigE capable arms have weak or<br>
non-existent L2 caches, and generally struggle to get past 700Mbits<br>
bidirectionally on the network.<br>
<br>
some quick tests of pfifo vs cake on the "lime-2" (armv7 dual core) are here:<br>
<br>
<a href="http://www.taht.net/~d/lime-2/" rel="noreferrer" target="_blank">http://www.taht.net/~d/lime-2/</a><br>
<br>
The rrul tests were not particularly pleasing. [1]<br>
<br>
...<br>
<br>
A second thing on my mind is to be able to take advantage of A) more cores<br>
<br>
... and B) hardware that increasingly has 4 or more lanes in it.<br>
<br>
1)  Presently fq_codel (and cake's) behavior there when set as a<br>
default qdisc is sub-optimal - if you have 64 hardware queues you end<br>
up with 64 instances, each with 1024 queues. While this might be<br>
awesome from a FQ perspective I really don't think the aqm will be as<br>
good. Or maybe it might be - what happens with 64000 queues at<br>
100Mbit?<br>
<br>
2) It's currently impossible to shape network traffic across cores.<br>
I'd like to imagine that with a single atomic exchange or sloppily<br>
shared values shaping would be feasible.<br>
<br></blockquote><div><br></div><div>When you need to worry about multithreading, many times perfect is very much the enemy of good. Depending on how quickly you need to make the network react, you could do something along the lines of a "shared pool" of bandwidth. Each core gets a split of the bandwidth, any unused bandwidth can be added to the pool, and cores that want more bandwidth can take bandwidth from the pool. </div><div><br></div><div>You could treat it like task stealing, except each core can generate tokens that represent a quantum of bandwidth that is only valid for some interval. If a core suddenly needs bandwidth, it can attempt to "take back" from its publicly shared pool. If other cores have already borrowed, it can attempt to borrow from another core. If it can't find any spare bandwidth, it just waits for some interval related to how long a quantum is valid, and assumes it's safe.</div><div><br></div><div>Or something.. I don't know, it's 7am and I just woke up.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
(also softirq is a single thread, I believe)<br>
<br>
3) mq and mqprio are commonly deployed on the high end for this.<br>
<br>
So I've thought about doing up another version - call it - I dunno -<br>
smq - "smart multi-queue" - and seeing how far we could get.<br>
<span class=""><br>
>  - Jonathan Morton<br>
><br>
> ______________________________<wbr>_________________<br>
> Cake mailing list<br>
> <a href="mailto:Cake@lists.bufferbloat.net">Cake@lists.bufferbloat.net</a><br>
> <a href="https://lists.bufferbloat.net/listinfo/cake" rel="noreferrer" target="_blank">https://lists.bufferbloat.net/<wbr>listinfo/cake</a><br>
<br>
<br>
<br>
</span>[1] If you are on this list and are not using flent, tough. I'm not<br>
going through the trouble of generating graphs myself anymore.<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
Dave Täht<br>
Let's go make home routers and wifi faster! With better software!<br>
<a href="http://blog.cerowrt.org" rel="noreferrer" target="_blank">http://blog.cerowrt.org</a><br>
</font></span><div class="HOEnZb"><div class="h5">______________________________<wbr>_________________<br>
Cake mailing list<br>
<a href="mailto:Cake@lists.bufferbloat.net">Cake@lists.bufferbloat.net</a><br>
<a href="https://lists.bufferbloat.net/listinfo/cake" rel="noreferrer" target="_blank">https://lists.bufferbloat.net/<wbr>listinfo/cake</a><br>
</div></div></blockquote></div><br></div></div>