)]}' { "commit": "809fa972fd90ff27225294b17a027e908b2d7b7a", "tree": "3bb15ec5b897df4ea197339478bb5d76049a2761", "parents": [ "89770b0a69ee0e0e5e99c722192d535115f73778" ], "author": { "name": "Hannes Frederic Sowa", "email": "hannes@stressinduktion.org", "time": "Wed Jan 22 02:29:41 2014 +0100" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Tue Jan 21 23:17:20 2014 -0800" }, "message": "reciprocal_divide: update/correction of the algorithm\n\nJakub Zawadzki noticed that some divisions by reciprocal_divide()\nwere not correct [1][2], which he could also show with BPF code\nafter divisions are transformed into reciprocal_value() for runtime\ninvariance which can be passed to reciprocal_divide() later on;\nreverse in BPF dump ended up with a different, off-by-one K in\nsome situations.\n\nThis has been fixed by Eric Dumazet in commit aee636c4809fa5\n(\"bpf: do not use reciprocal divide\"). This follow-up patch\nimproves reciprocal_value() and reciprocal_divide() to work in\nall cases by using Granlund and Montgomery method, so that also\nfuture use is safe and without any non-obvious side-effects.\nKnown problems with the old implementation were that division by 1\nalways returned 0 and some off-by-ones when the dividend and divisor\nwhere very large. This seemed to not be problematic with its\ncurrent users, as far as we can tell. Eric Dumazet checked for\nthe slab usage, we cannot surely say so in the case of flex_array.\nStill, in order to fix that, we propose an extension from the\noriginal implementation from commit 6a2d7a955d8d resp. [3][4],\nby using the algorithm proposed in \"Division by Invariant Integers\nUsing Multiplication\" [5], Torbjörn Granlund and Peter L.\nMontgomery, that is, pseudocode for q \u003d n/d where q, n, d is in\nu32 universe:\n\n1) Initialization:\n\n int l \u003d ceil(log_2 d)\n uword m\u0027 \u003d floor((1\u003c\u003c32)*((1\u003c\u003cl)-d)/d)+1\n int sh_1 \u003d min(l,1)\n int sh_2 \u003d max(l-1,0)\n\n2) For q \u003d n/d, all uword:\n\n uword t \u003d (n*m\u0027)\u003e\u003e32\n q \u003d (t+((n-t)\u003e\u003esh_1))\u003e\u003esh_2\n\nThe assembler implementation from Agner Fog [6] also helped a lot\nwhile implementing. We have tested the implementation on x86_64,\nppc64, i686, s390x; on x86_64/haswell we\u0027re still half the latency\ncompared to normal divide.\n\nJoint work with Daniel Borkmann.\n\n [1] http://www.wireshark.org/~darkjames/reciprocal-buggy.c\n [2] http://www.wireshark.org/~darkjames/set-and-dump-filter-k-bug.c\n [3] https://gmplib.org/~tege/division-paper.pdf\n [4] http://homepage.cs.uiowa.edu/~jones/bcd/divide.html\n [5] http://citeseerx.ist.psu.edu/viewdoc/summary?doi\u003d10.1.1.1.2556\n [6] http://www.agner.org/optimize/asmlib.zip\n\nReported-by: Jakub Zawadzki \u003cdarkjames-ws@darkjames.pl\u003e\nCc: Eric Dumazet \u003ceric.dumazet@gmail.com\u003e\nCc: Austin S Hemmelgarn \u003cahferroin7@gmail.com\u003e\nCc: linux-kernel@vger.kernel.org\nCc: Jesse Gross \u003cjesse@nicira.com\u003e\nCc: Jamal Hadi Salim \u003cjhs@mojatatu.com\u003e\nCc: Stephen Hemminger \u003cstephen@networkplumber.org\u003e\nCc: Matt Mackall \u003cmpm@selenic.com\u003e\nCc: Pekka Enberg \u003cpenberg@kernel.org\u003e\nCc: Christoph Lameter \u003ccl@linux-foundation.org\u003e\nCc: Andy Gospodarek \u003candy@greyhouse.net\u003e\nCc: Veaceslav Falico \u003cvfalico@redhat.com\u003e\nCc: Jay Vosburgh \u003cfubar@us.ibm.com\u003e\nCc: Jakub Zawadzki \u003cdarkjames-ws@darkjames.pl\u003e\nSigned-off-by: Daniel Borkmann \u003cdborkman@redhat.com\u003e\nSigned-off-by: Hannes Frederic Sowa \u003channes@stressinduktion.org\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "3220b488dd1e043551d08b8031043fbd70c0b517", "old_mode": 33188, "old_path": "drivers/net/bonding/bond_main.c", "new_id": "f100bd958b8896d594d74012273137387e156b57", "new_mode": 33188, "new_path": "drivers/net/bonding/bond_main.c" }, { "type": "modify", "old_id": "21c648854a8c4861d7e26bdca97d940f8c28c466", "old_mode": 33188, "old_path": "drivers/net/bonding/bond_netlink.c", "new_id": "e8526552790cdab3e1c6cfe5cfb6558af2776947", "new_mode": 33188, "new_path": "drivers/net/bonding/bond_netlink.c" }, { "type": "modify", "old_id": "945a6668da8376ad125356a300b9d34a72ea4166", "old_mode": 33188, "old_path": "drivers/net/bonding/bond_options.c", "new_id": "85e434886f2e116a8b3ec13962dd70ba0ea884b4", "new_mode": 33188, "new_path": "drivers/net/bonding/bond_options.c" }, { "type": "modify", "old_id": "011f163c2c6771a9cbd335a507dfb390b081eca2", "old_mode": 33188, "old_path": "drivers/net/bonding/bond_sysfs.c", "new_id": "c083e9a66ece736493295ba6044ea2377b446d11", "new_mode": 33188, "new_path": "drivers/net/bonding/bond_sysfs.c" }, { "type": "modify", "old_id": "8a935f8f2b3c558ec7d288149ced77e3c60cc281", "old_mode": 33188, "old_path": "drivers/net/bonding/bonding.h", "new_id": "0a616c41dc9496c3cce31f6890ba3eeb992a96d5", "new_mode": 33188, "new_path": "drivers/net/bonding/bonding.h" }, { "type": "modify", "old_id": "6843cf193a445134cde17f7d2db6893399ac8cda", "old_mode": 33188, "old_path": "include/linux/flex_array.h", "new_id": "b6efb0c64408b35b7874726ca22c72f2e5fe21f3", "new_mode": 33188, "new_path": "include/linux/flex_array.h" }, { "type": "modify", "old_id": "f9c90b33285b24b2ef9870ee3d3fe3cf78f9283d", "old_mode": 33188, "old_path": "include/linux/reciprocal_div.h", "new_id": "8c5a3fb6c6c57821720dc307f3eeec944c56f974", "new_mode": 33188, "new_path": "include/linux/reciprocal_div.h" }, { "type": "modify", "old_id": "09bfffb08a56db285caa27146202f04e2188b480", "old_mode": 33188, "old_path": "include/linux/slab_def.h", "new_id": "96e8abae19a943375e39da1c779016a72cc07b7e", "new_mode": 33188, "new_path": "include/linux/slab_def.h" }, { "type": "modify", "old_id": "168bb2f495f207511bffe485c1070ea8bb6df30a", "old_mode": 33188, "old_path": "include/net/red.h", "new_id": "76e0b5f922c6c475e7f47a73d072282dfec53149", "new_mode": 33188, "new_path": "include/net/red.h" }, { "type": "modify", "old_id": "6948a6692fc4f6b70c2bfc0700afb7a971d7059e", "old_mode": 33188, "old_path": "lib/flex_array.c", "new_id": "2eed22fa507c7cb0756d7ef643f8a3454eb455ec", "new_mode": 33188, "new_path": "lib/flex_array.c" }, { "type": "modify", "old_id": "75510e94f7d0b2fcd5736a4e0aeb9ff282da11d1", "old_mode": 33188, "old_path": "lib/reciprocal_div.c", "new_id": "464152410c5123e191324a4cfb3ca5ea8ff66687", "new_mode": 33188, "new_path": "lib/reciprocal_div.c" }, { "type": "modify", "old_id": "a2bfc371b44a3339709be67d58004a00400abe8e", "old_mode": 33188, "old_path": "net/sched/sch_netem.c", "new_id": "de1059af6da14c563115147852c4f52b80a9387d", "new_mode": 33188, "new_path": "net/sched/sch_netem.c" } ] }