From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-x233.google.com (mail-qk0-x233.google.com [IPv6:2607:f8b0:400d:c09::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id E69353B2A3 for ; Fri, 3 Mar 2017 01:21:57 -0500 (EST) Received: by mail-qk0-x233.google.com with SMTP id n127so161256358qkf.0 for ; Thu, 02 Mar 2017 22:21:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=Fobb+iVFMb8iJWG3JsZOCk5KPbs7lTP7Sii5an/4yks=; b=UMJ0AN8JlrE8C77ZFqlp0d7SwmkOZCe2a26003j+4EAysCWEL/r4ZNnbYjKTds7Crt 6fKAdNpA9bYIXaMFetgAZqldOl39yyZkqHv9m4mRGVJtPrXhJBFwKRUvnqz3Pet+efZ7 9hbXfJ2JNG2KovmC7VXDY969A99mDt8WaMhUu1JSmQmxF5t6C1dAg/NBMIxTufYNJI3g 8KJMYahfAbep6hnB7ppx7Y9TD/ab8BPBKBQpNBJbHR9QYr53os8UNPwfmPLryDYG+Jn5 mnbTHR0zPmcW+lZY4cqYcN/0UXxKPbHve213j3CZHoqTqpQiP85PgJN9/uK6pGOz9f4p TyDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=Fobb+iVFMb8iJWG3JsZOCk5KPbs7lTP7Sii5an/4yks=; b=GOTtkTUrjZ2BYXDzsbqsd4sMjd5Vhji+XXhia0yB5Urb8qNzZ3bBIqo0oZvEnyxwfo u+RMa9i1uDViqITk9KliqQLpXX2lrAijD6I1MydcEa0xZ6p4sQI2MjqRMsu28PsMc23U PuxpzExRQ+3kNIH8k2HAgmiMPIm+3UXno4sGugnM6hUTT8gNsg5LKY/m0L0qrZjLxKYx KuRno3ZYVDZGRRf/1W/OODbucGCaKpJTmq7PBh58GnGFuaSH8JYNU18utfFx9XbxTUx5 9qRHC0qQT2G/R7msvbPsfHhr6Hm9wLGId+V23iB1a+WKsMR3KICPPC0nAEgu+6NkNFTI z/Gw== X-Gm-Message-State: AMke39nKdQvw4b6zSovomjhS7qWaEcBLXsMocVLgEdV6VvbLfmZPQ9jsMFZxN2+Zjpsczm2n6r4L3ZUIpUqmkw== X-Received: by 10.200.3.81 with SMTP id w17mr1003116qtg.36.1488522117452; Thu, 02 Mar 2017 22:21:57 -0800 (PST) MIME-Version: 1.0 Received: by 10.12.142.132 with HTTP; Thu, 2 Mar 2017 22:21:56 -0800 (PST) In-Reply-To: References: <07479F0A-40DD-44E5-B67E-28117C7CF228@gmx.de> <1488400107.3610.1@smtp.autistici.org> <2B251BF1-C965-444D-A831-9981861E453E@gmx.de> <1488484262.16753.0@smtp.autistici.org> <98E899EF-5E66-42CC-88AA-79FA80A4F228@gmail.com> <2D2AE632-75BB-4DDE-B370-0996EFECF14B@gmail.com> From: Dave Taht Date: Thu, 2 Mar 2017 22:21:56 -0800 Message-ID: To: Jonathan Morton Cc: Eric Luehrsen , "cake@lists.bufferbloat.net" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Cake] [LEDE-DEV] Cake SQM killing my DIR-860L - was: [17.01] Kernel: bump to 4.4.51 X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Mar 2017 06:21:58 -0000 As this is devolving into a cake specific discussion, removing the lede mailing list. On Thu, Mar 2, 2017 at 9:49 PM, Jonathan Morton wro= te: > >> On 3 Mar, 2017, at 07:00, Eric Luehrsen wrote= : >> >> That's not what I was going for. Agree, it would not be good to depend >> on an inferior hash. You mentioned divide as a "cost." So I was >> proposing a thought around a "benefit" estimate. If hash collisions are >> not as important (or are they), then what is "benefit / cost?" > > The computational cost of one divide is not the only consideration I have= in mind. > > Cake=E2=80=99s set-associative hash is fundamentally predicated on the nu= mber 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 min= or part is then iterated to try to locate a matching or free bucket. > > This is considerably easier to do and reason about when everything is a p= ower of two. Then, modulus is a masking operation, and divide is a shift, = either of which can be done in one cycle flat. > > 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 oper= ates on. This is something a profile would shed more light on. Tried. Mips wasn't a good target. The jhash3 setup cost is bad, but I agree flow dissection can be deeply expensive. As well as the other 42+ functions a packet needs to traverse to get from ingress to egress. But staying on hashing: One thing that landed 4.10? 4.11? was fq_codel relying on a skb->hash if one already existed (injected already by tcp, or by hardware, or the tunneling tool). we only need to compute a partial hash on the smaller subset of keys in that case (if we can rely on the skb->hash which we cannot do in the nat case) Another thing I did, long ago, was read the (60s-era!) liturature about set-associative cpu cache architectures... and... In all of these cases I really, really wanted to just punt all this extra work to hardware in ingress - computing 3 hashes can be easily done in parallel there and appended to the packet as it completes. I have been working quite a bit more with the arm architecture of late, and the "perf" profiler over there is vastly better than the mips one we've had. (and aarch64 is *nice*. So is NEON) - but I hadn't got around to dinking with cake there until yesterday. One thing I'm noticing is that even the gigE capable arms have weak or non-existent L2 caches, and generally struggle to get past 700Mbits bidirectionally on the network. some quick tests of pfifo vs cake on the "lime-2" (armv7 dual core) are her= e: http://www.taht.net/~d/lime-2/ The rrul tests were not particularly pleasing. [1] ... A second thing on my mind is to be able to take advantage of A) more cores ... and B) hardware that increasingly has 4 or more lanes in it. 1) Presently fq_codel (and cake's) behavior there when set as a default qdisc is sub-optimal - if you have 64 hardware queues you end up with 64 instances, each with 1024 queues. While this might be awesome from a FQ perspective I really don't think the aqm will be as good. Or maybe it might be - what happens with 64000 queues at 100Mbit? 2) It's currently impossible to shape network traffic across cores. I'd like to imagine that with a single atomic exchange or sloppily shared values shaping would be feasible. (also softirq is a single thread, I believe) 3) mq and mqprio are commonly deployed on the high end for this. So I've thought about doing up another version - call it - I dunno - smq - "smart multi-queue" - and seeing how far we could get. > - Jonathan Morton > > _______________________________________________ > Cake mailing list > Cake@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/cake [1] If you are on this list and are not using flent, tough. I'm not going through the trouble of generating graphs myself anymore. --=20 Dave T=C3=A4ht Let's go make home routers and wifi faster! With better software! http://blog.cerowrt.org