From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21426 invoked by alias); 3 Mar 2011 22:33:05 -0000 Received: (qmail 21398 invoked by uid 22791); 3 Mar 2011 22:33:03 -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-1.vmware.com (HELO smtp-outbound-1.vmware.com) (65.115.85.69) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 03 Mar 2011 22:32:57 +0000 Received: from mailhost3.vmware.com (mailhost3.vmware.com [10.16.27.45]) by smtp-outbound-1.vmware.com (Postfix) with ESMTP id 567841305A; Thu, 3 Mar 2011 14:32:56 -0800 (PST) Received: from msnyder-server.eng.vmware.com (promd-2s-dhcp138.eng.vmware.com [10.20.124.138]) by mailhost3.vmware.com (Postfix) with ESMTP id 14D7CCDA74; Thu, 3 Mar 2011 14:32:56 -0800 (PST) Message-ID: <4D701717.5070003@vmware.com> Date: Thu, 03 Mar 2011 22:33: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: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit 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/msg00227.txt.bz2 DJ Delorie wrote: >> As written, the function will access element [30] of a 30-element array. > > Um, no? > > 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...) Whee, here we go... (gdb) b higher_prime_index Breakpoint 2 at 0x79bed4: file /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175. (gdb) print higher_prime_index(0xffffffff) Breakpoint 2, higher_prime_index (n=4294967295) at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175 175 unsigned int low = 0; The program being debugged stopped while in a function called from GDB. Evaluation of the expression containing the function (higher_prime_index) will be abandoned. When the function is done executing, GDB will silently stop. (gdb) n 176 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1; (gdb) 178 while (low < high) (gdb) 180 unsigned int mid = low + (high - low) / 2; (gdb) display low 1: low = 0 (gdb) n 181 if (n > prime_tab[mid].prime) 1: low = 0 (gdb) 182 low = mid + 1; 1: low = 0(gdb) b higher_prime_index Breakpoint 2 at 0x79bed4: file /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175. (gdb) print higher_prime_index(0xffffffff) Breakpoint 2, higher_prime_index (n=4294967295) at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175 175 unsigned int low = 0; The program being debugged stopped while in a function called from GDB. Evaluation of the expression containing the function (higher_prime_index) will be abandoned. When the function is done executing, GDB will silently stop. (gdb) n 176 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1; (gdb) 178 while (low < high) (gdb) 180 unsigned int mid = low + (high - low) / 2; (gdb) display low 1: low = 0 (gdb) n 181 if (n > prime_tab[mid].prime) 1: low = 0 (gdb) 182 low = mid + 1; 1: low = 0 (gdb) 178 while (low < high) 1: low = 16 (gdb) 180 unsigned int mid = low + (high - low) / 2; 1: low = 16 (gdb) 181 if (n > prime_tab[mid].prime) 1: low = 16 (gdb) 182 low = mid + 1; (gdb) 178 while (low < high) 1: low = 16 (gdb) 180 unsigned int mid = low + (high - low) / 2; 1: low = 16 (gdb) 181 if (n > prime_tab[mid].prime) 1: low = 16 (gdb) 182 low = mid + 1; 1: low = 16 (gdb) 178 while (low < high) 1: low = 24 (gdb) 180 unsigned int mid = low + (high - low) / 2; 1: low = 24 (gdb) 181 if (n > prime_tab[mid].prime) 1: low = 24 (gdb) 182 low = mid + 1; 1: low = 24 (gdb) 178 while (low < high) 1: low = 28 (gdb) 180 unsigned int mid = low + (high - low) / 2; 1: low = 28 (gdb) 181 if (n > prime_tab[mid].prime) 1: low = 28 (gdb) 182 low = mid + 1; 1: low = 28 (gdb) 178 while (low < high) 1: low = 30 (gdb) 188 if (n > prime_tab[low].prime) 1: low = 30 (gdb)