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

[Siddhesh Poyarekar <siddhesh at redhat dot com>]

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.
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?

Siddhesh

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.  */
 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;
 
@@ -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;
 
   while (!is_prime (seed))
     seed += 2;