linux-kernel - Re: [PATCH] lib: One less subtraction in binary search iterations.

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: <CANeycqqGYKs+Q+_6zpjfdQ+y-QBZLD+jGdU9-YJi9XaYXyCv-w@mail.gmail.com>
Date:	Mon, 8 Jul 2013 20:51:53 -0700
From:	Wedson Almeida Filho <wedsonaf@...il.com>
To:	Joe Perches <joe@...ches.com>
Cc:	Rusty Russell <rusty@...tcorp.com.au>,
	Tim Abbott <tabbott@...lice.com>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] lib: One less subtraction in binary search iterations.

On Sat, Jul 6, 2013 at 9:59 PM, Joe Perches <joe@...ches.com> wrote:
>
> Not correct.
>
>>       while (start < end) {
>> -             size_t mid = start + (end - start) / 2;
>> +             size_t mid = (start + end) / 2;
>
>         size_t start = 0x80000000;
>         size_t end   = 0x80000001;

Good point, they aren't equivalent in all cases.

For the overflow to happen though, we need an array with at least
N/2+1 entries, where N is the address space size. The array wouldn't
fit in addressable memory if the element size is greater than 1, so
this can only really happen when the element size is 1. Even then, it
would require the kernel range to be greater than half of all
addressable memory, and allow an allocation taking that much memory. I
don't know all architectures where linux runs, but I don't think such
configuration is likely to exist.
--
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/