From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16141 invoked by alias); 3 Mar 2011 22:26:27 -0000 Received: (qmail 16121 invoked by uid 22791); 3 Mar 2011 22:26:26 -0000 X-SWARE-Spam-Status: No, hits=-5.1 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_HI,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-outbound-2.vmware.com (HELO smtp-outbound-2.vmware.com) (65.115.85.73) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 03 Mar 2011 22:26:19 +0000 Received: from mailhost2.vmware.com (mailhost2.vmware.com [10.16.67.167]) by smtp-outbound-2.vmware.com (Postfix) with ESMTP id 6E82843000; Thu, 3 Mar 2011 14:26:18 -0800 (PST) Received: from msnyder-server.eng.vmware.com (promd-2s-dhcp138.eng.vmware.com [10.20.124.138]) by mailhost2.vmware.com (Postfix) with ESMTP id 65ED98ED81; Thu, 3 Mar 2011 14:26:18 -0800 (PST) Message-ID: <4D70158A.5080209@vmware.com> Date: Thu, 03 Mar 2011 22:26:00 -0000 From: Michael Snyder User-Agent: Thunderbird 2.0.0.24 (X11/20101201) MIME-Version: 1.0 To: DJ Delorie CC: "gcc-patches@gcc.gnu.org" , "gdb-patches@sourceware.org" Subject: Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun References: <4D701056.1080208@vmware.com> <201103032211.p23MB9Ed003261@greed.delorie.com> In-Reply-To: <201103032211.p23MB9Ed003261@greed.delorie.com> Content-Type: multipart/mixed; boundary="------------030906070708090106010906" X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2011-03/txt/msg00224.txt.bz2 This is a multi-part message in MIME format. --------------030906070708090106010906 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-length: 772 DJ Delorie wrote: >> As written, the function will access element [30] of a 30-element array. > > Um, no? Y-uh-huh! > unsigned int mid = low + (high - low) / 2; > > This can never give mid == high unless low == high, which won't happen > in that loop. > > The math wants to search everything from (including) low to > (excluding) high. > > (but I'm willing to be proven wrong...) I am willing to do that! ;-) Compile this program, run it under gdb with the input "0xffffffff", and step through the code. You will see it assign the value "30" to "low" and use it to access the array. I suppose you could do it directly just by loading gdb into gdb, putting a breakpoint at the above function, and then calling it from gdb with the input 0xffffffff. --------------030906070708090106010906 Content-Type: text/x-csrc; name="hash.c" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="hash.c" Content-length: 2426 #include #include typedef unsigned int hashval_t; struct prime_ent { hashval_t prime; hashval_t inv; hashval_t inv_m2; /* inverse of prime-2 */ hashval_t shift; }; static struct prime_ent const prime_tab[] = { { 7, 0x24924925, 0x9999999b, 2 }, { 13, 0x3b13b13c, 0x745d1747, 3 }, { 31, 0x08421085, 0x1a7b9612, 4 }, { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, { 127, 0x02040811, 0x0624dd30, 6 }, { 251, 0x05197f7e, 0x073260a5, 7 }, { 509, 0x01824366, 0x02864fc8, 8 }, { 1021, 0x00c0906d, 0x014191f7, 9 }, { 2039, 0x0121456f, 0x0161e69e, 10 }, { 4093, 0x00300902, 0x00501908, 11 }, { 8191, 0x00080041, 0x00180241, 12 }, { 16381, 0x000c0091, 0x00140191, 13 }, { 32749, 0x002605a5, 0x002a06e6, 14 }, { 65521, 0x000f00e2, 0x00110122, 15 }, { 131071, 0x00008001, 0x00018003, 16 }, { 262139, 0x00014002, 0x0001c004, 17 }, { 524287, 0x00002001, 0x00006001, 18 }, { 1048573, 0x00003001, 0x00005001, 19 }, { 2097143, 0x00004801, 0x00005801, 20 }, { 4194301, 0x00000c01, 0x00001401, 21 }, { 8388593, 0x00001e01, 0x00002201, 22 }, { 16777213, 0x00000301, 0x00000501, 23 }, { 33554393, 0x00001381, 0x00001481, 24 }, { 67108859, 0x00000141, 0x000001c1, 25 }, { 134217689, 0x000004e1, 0x00000521, 26 }, { 268435399, 0x00000391, 0x000003b1, 27 }, { 536870909, 0x00000019, 0x00000029, 28 }, { 1073741789, 0x0000008d, 0x00000095, 29 }, { 2147483647, 0x00000003, 0x00000007, 30 }, /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ { 0xfffffffb, 0x00000006, 0x00000008, 31 } }; static unsigned int higher_prime_index (unsigned long n) { unsigned int low = 0; unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); while (low != high) { unsigned int mid = low + (high - low) / 2; if (n > prime_tab[mid].prime) low = mid + 1; else high = mid; } /* If we've run out of primes, abort. */ if (n > prime_tab[low].prime) { fprintf (stderr, "Cannot find prime bigger than %lu\n", n); abort (); } return low; } int main (int argc, char **argv) { if (argc < 2) { fprintf (stderr, "Usage: hash \n"); return 1; } printf ("Answer: %d\n", higher_prime_index (strtoul (argv[1], NULL, 0))); return 0; } --------------030906070708090106010906--