Re: [PATCH] Fix nss_db crash when db contains exactly one entry

["Carlos O'Donell" <carlos at systemhalted dot org>]

On Tue, Nov 27, 2012 at 2:21 PM, Siddhesh Poyarekar <siddhesh@redhat.com> wrote:
> On Tue, Nov 27, 2012 at 10:24:22PM +0530, Siddhesh Poyarekar wrote:
>> On Tue, Nov 27, 2012 at 11:42:46AM -0500, Carlos O'Donell wrote:
>> >
>> > Please inline your patches, it makes it *way* easier to review and comment.
>> >
>>
>> Ah I noticed that after I posted them.  I switched to mutt recently
>> and I guess I need to fix something in my muttrc.
>>
>> > The function is a modified `Trial Division' algorithm for computing
>> > the next prime.
>> >
>> > Please replace it with a correctly working Trial Division algorithm
>> > that uses squaring to avoid square roots. Then we can remove the
>> > quirky restrictions and end up with a robust piece of code that
>> > doesn't fail in weird corner cases.
>> >
>> > I suggest looking at:
>> > http://en.literateprograms.org/Trial_division_%28C%29
>> >
>> > I suggest against a Sieve of Eratosthenes because it increases the
>> > memory required by the computation. Keep it simple and low memory.
>> >
>>
>
> I was looking at this again and I think the prime algorithm is fine.

That depends on what you mean by "fine," yes it does do some things correctly.

We should document the restrictions and add an assert.

We don't want this to lead to hash table corruption at any point in the future.

> We need an odd prime number >= 3 because the hash function needs it - it
> does:
>
> hval2 = 1 + hash % (hashlength - 2)
>
> to get the second hash id.  Any trial division algorithm needs to
> start from 2, so we're basically just going one ahead and starting
> from 3.  So what I have done instead is make the next_prime() look
> like it should, which is pick the next odd number instead of simply
> ensuring odd input.  What do you think?

The function is_prime will reject 3 as being not-prime, even though it is.

We should just start at 5.

See below.

> ChangeLog:
>
>         * nss/makedb.c (next_prime): Get next odd number.
>
>
> diff --git a/nss/makedb.c b/nss/makedb.c
> index 8d7d027..33d2920 100644
> --- a/nss/makedb.c
> +++ b/nss/makedb.c
> @@ -591,10 +591,10 @@ copy_valstr (const void *nodep, const VISIT which, const int depth)
>  }
>
>
> +/* Check if a number is a prime greater than 3.  */

This doesn't say anything about the restrictions on the inputs.

I suggest:

/*  The function determines if the candidate is prime by using
a modified trial division algorithm. The candidate must be both
odd and greater than 4.  */

(with appropriate wrapping)

>  static int
>  is_prime (size_t candidate)
>  {
> -  /* No even number and none less than 10 will be passed here.  */
>    size_t divn = 3;
>    size_t sq = divn * divn;

Please add `assert (candidate > 4 && candidate % 2 != 0);'.

It's pretty optimal to compute this and prevents future issues.

I'm ignoring the issue of wrapping size_t when we execute `+= 4 *
divn;' since we're moving into the ridiculously sized database range
there.

> @@ -612,8 +612,8 @@ is_prime (size_t candidate)
>  static size_t
>  next_prime (size_t seed)
>  {
> -  /* Make it definitely odd.  */
> -  seed |= 1;
> +  /* Get the next odd number.  */
> +  seed = (seed + 1) | 1;

Add 4?

That way we always call is_prime with a valid candidate value.

e.g.
0 + 4 | 1 = 5; 5 > 4 && 5 %2 != 0
1 + 4 | 1 = 5; 7 > 4 && 7 %2 != 0
2 + 4 | 1 = 7; 7 > 4 && 7 %2 != 0
3 + 4 | 1 = 7; 7 > 4 && 9 %2 != 0
4 + 4 | 1 = 9; 9 > 4 && 9 %2 != 0
5 + 4 | 1 = 9; 9 > 4 && 11 %2 != 0
6 + 4 | 1 = 11; 11 > 4 && 11 %2 != 0
...

>
>    while (!is_prime (seed))
>      seed += 2;
>

OK with new comment, assert, starting at 5.

Cheers,
Carlos.