Re: [PATCH v2] lib: gcd: prevent possible div by 0

From: Davidlohr Bueso
Date: Wed Sep 12 2012 - 16:30:29 EST


On Wed, 2012-09-12 at 12:36 -0700, Andrew Morton wrote:
> On Wed, 12 Sep 2012 21:20:30 +0200
> Davidlohr Bueso <dave@xxxxxxx> wrote:
>
> > On Wed, 2012-09-12 at 12:10 -0700, Andrew Morton wrote:
> > > On Mon, 10 Sep 2012 16:35:19 +0200
> > > Davidlohr Bueso <dave@xxxxxxx> wrote:
> > >
> > > > Account for all properties when a and/or b are 0:
> > > > gcd(0, 0) = 0
> > > > gcd(a, 0) = a
> > > > gcd(0, b) = b
> > > >
> > > > Cc: stable@xxxxxxxxxxxxxxx
> > >
> > > Why cc:stable? If this patch fixes some known problem in the current
> > > kernel then that really really should have been described in the
> > > changelog. Always. Please.
> >
> > Ok, I will keep it in mind next time. No known problem (at least that I
> > know of), but due to the nature of the potential bug, I thought that it
> > was worth adding it to stable.
>
> OK.
>
> I'm not personally averse to fixing such problems in -stable,
> particualrly in lib/ code. After all, people who take -stable kernels
> will then change them and add drivers and backport changes from later
> kernels, etc. They might be bitten by such a bug.

Yes, my thoughts exactly.
>
>
> I'm scratching my head a bit at the patch though. What does gcd(0, 13)
> mean? That 0 can be divided by 13 zero times, which is an integer
> result? I wonder why any non-buggy code would do that....
>

While I've been away from this kind of math for a while, based on the
Euclid's algorithm, if r = a mod b, then gcd(a, b) = gcd(b, r), so:

gcd(0, 13) = gcd(13, 0 mod 13) = gcd(13, 0)

Since the GCD of a and b is "the largest integer that divides both a
and b with no remainder", when r = 0, the algorithm will stop and
therefore gcd(13, 0) = 13.

http://mitpress.mit.edu/sicp/full-text/sicp/book/node19.html

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/