linux-kernel - Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1389841646.31367.391.camel@edumazet-glaptop2.roam.corp.google.com>
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 linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/