From patchwork Tue Jan 26 00:06:27 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paul Eggert X-Patchwork-Id: 10561 Received: (qmail 120215 invoked by alias); 26 Jan 2016 00:06:31 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 120206 invoked by uid 89); 26 Jan 2016 00:06:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 spammy=7619, 686, 68, 6, prime X-HELO: zimbra.cs.ucla.edu Subject: Re: [PATCH] Improve check against integer wraparound in hcreate_r [BZ #18240] To: Florian Weimer References: <56A210C4.80609@redhat.com> <56A42D78.1030506@cs.ucla.edu> <877fixs9or.fsf@mid.deneb.enyo.de> Cc: Florian Weimer , GNU C Library , Adhemerval Zanella From: Paul Eggert Message-ID: <56A6B883.2070801@cs.ucla.edu> Date: Mon, 25 Jan 2016 16:06:27 -0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 In-Reply-To: <877fixs9or.fsf@mid.deneb.enyo.de> On 01/25/2016 12:09 PM, Florian Weimer wrote: > - while (div * div < number && number % div != 0) > + while (div * (unsigned long long) div < number && number % div != 0) Good catch. But better yet, get rid of the '*' so that we needn't worry about whether the multiplication overflows. On typical platforms the divide instruction that the '%' is already doing will give us the information we need, so this is faster anyway. Something like the attached (untested) patch. diff --git a/misc/hsearch_r.c b/misc/hsearch_r.c index f6f16ed..1fca6b3 100644 --- a/misc/hsearch_r.c +++ b/misc/hsearch_r.c @@ -46,15 +46,12 @@ static int isprime (unsigned int number) { /* no even number will be passed */ - unsigned int div = 3; - - while (div * div < number && number % div != 0) - div += 2; - - return number % div != 0; + for (unsigned int div = 3; div <= number / div; div += 2) + if (number % div == 0) + return 0; + return 1; } - /* Before using the hash table we must allocate memory for it. Test for an existing table are done. We allocate one element more as the found prime number says. This is done for more effective @@ -71,13 +68,6 @@ __hcreate_r (size_t nel, struct hsearch_data *htab) return 0; } - if (nel >= SIZE_MAX / sizeof (_ENTRY)) - { - __set_errno (ENOMEM); - return 0; - } - - /* There is still another table active. Return with error. */ if (htab->table != NULL) return 0; @@ -86,10 +76,19 @@ __hcreate_r (size_t nel, struct hsearch_data *htab) use will not work. */ if (nel < 3) nel = 3; - /* Change nel to the first prime number not smaller as nel. */ - nel |= 1; /* make odd */ - while (!isprime (nel)) - nel += 2; + + /* Change nel to the first prime number in the range [nel, UINT_MAX - 2], + The '- 2' means 'nel += 2' cannot overflow. */ + for (nel |= 1; ; nel += 2) + { + if (UINT_MAX - 2 < nel) + { + __set_errno (ENOMEM); + return 0; + } + if (isprime (nel)) + break; + } htab->size = nel; htab->filled = 0;