lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Wed, 15 Jan 2014 19:07:26 -0800 From: Eric Dumazet <eric.dumazet@...il.com> To: Daniel Borkmann <dborkman@...hat.com> Cc: davem@...emloft.net, netdev@...r.kernel.org, linux-kernel@...r.kernel.org, Hannes Frederic Sowa <hannes@...essinduktion.org>, Austin S Hemmelgarn <ahferroin7@...il.com>, Jesse Gross <jesse@...ira.com>, Jamal Hadi Salim <jhs@...atatu.com>, Stephen Hemminger <stephen@...workplumber.org>, Matt Mackall <mpm@...enic.com>, Pekka Enberg <penberg@...nel.org>, Christoph Lameter <cl@...ux-foundation.org>, Andy Gospodarek <andy@...yhouse.net>, Veaceslav Falico <vfalico@...hat.com>, Jay Vosburgh <fubar@...ibm.com>, Jakub Zawadzki <darkjames-ws@...kjames.pl> Subject: Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote: > Also, reciprocal_value() and reciprocal_divide() always return 0 > for divisions by 1. This is a bit worrisome as those functions > also get used in mm/slab.c and lib/flex_array.c, apparently for > index calculation to access array slots. Hi Daniel This off-by-one limitation is a known one, and mm/slab.c does not have an issue with it because : - Minimal object size is not 1 byte, but 8 (or maybe 4) - We always divide a multiple of the divisor, so there is no off-by-one effect. Little attached prog does a brute force check if needed. So far, the only relevant issue was about BPF, and a better documentation of reciprocal_divide() use cases. (I let Jesse comment on the flex_array case) I am unsure we want to 'fix' things, we tried hard in the past to avoid divides, so the ones we use are usually because the divisor is not constant, so the reciprocal doesn't help. (BPF is fixed in David tree) Thanks ! #include <stdio.h> typedef unsigned int u32; typedef unsigned long long u64; static u32 reciprocal_value(u32 k) { u64 val = (1LL << 32) + (k - 1); val /= k; return (u32)val; } static inline u32 reciprocal_divide(u32 A, u32 R) { return (u32)(((u64)A * R) >> 32); } #define LIMIT 1000*1000*1000 int main() { u32 divisor, dividend, reciprocal, next; int res = 0; for (divisor = 2; divisor < LIMIT; divisor++) { reciprocal = reciprocal_value(divisor); for (dividend = 0; ; dividend = next) { if (reciprocal_divide(dividend, reciprocal) != (dividend / divisor)) { printf("Arg: %u/%u was not properly computed (%u/%u)\n", dividend, divisor, reciprocal_divide(dividend, reciprocal), dividend / divisor); res = 1; break; } next = dividend + divisor; if (next < dividend) break; } } return res; } -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists