[lkml]   [2014]   [Sep]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [PATCH] kcmp: Fix standard comparison bug
On Thu, Sep 04, 2014 at 12:40:06PM +0200, Rasmus Villemoes wrote:
> The C operator <= defines a perfectly fine total ordering on the set
> of values representable in a long. However, unlike its namesake in the
> integers, it is not translation invariant, meaning that we do not have
> "b <= c" iff "a+b <= a+c" for all a,b,c.
> This means that it is always wrong to try to boil down the
> relationship between two longs to a question about the sign of their
> difference, because the resulting relation [a LEQ b iff a-b <= 0] is
> neither anti-symmetric or transitive. The former is due to
> -LONG_MIN==LONG_MIN (take any two a,b with a-b = LONG_MIN; then a LEQ
> b and b LEQ a, but a != b). The latter can either be seen observing
> that x LEQ x+1 for all x, implying x LEQ x+1 LEQ x+2 ... LEQ x-1 LEQ
> x; or more directly with the simple example a=LONG_MIN, b=0, c=1, for
> which a-b < 0, b-c < 0, but a-c > 0.
> Note that it makes absolutely no difference that a transmogrying
> bijection has been applied before the comparison is done. In fact, had
> the obfuscation not been done, one could probably not observe the bug
> (assuming all values being compared always lie in one half of the
> address space, the mathematical value of a-b is always representable
> in a long). As it stands, one can easily obtain three file descriptors
> exhibiting the non-transitivity of kcmp().
> Cc: <>
> Signed-off-by: Rasmus Villemoes <>

Just noted that Andrew's email address has been screwed for some reason,
fixed. Guys, pick it up please, and many thanks to Rasmus for finding it.

 \ /
  Last update: 2014-09-05 20:21    [W:0.056 / U:0.480 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site