From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26201 invoked by alias); 16 May 2013 14:17:25 -0000 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 Received: (qmail 26187 invoked by uid 89); 16 May 2013 14:17:24 -0000 X-Spam-SWARE-Status: No, score=-7.3 required=5.0 tests=AWL,BAYES_00,KHOP_THREADED,RCVD_IN_HOSTKARMA_W,RCVD_IN_HOSTKARMA_WL,RP_MATCHES_RCVD,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.1 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Thu, 16 May 2013 14:17:23 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r4GEHMSa024132 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Thu, 16 May 2013 10:17:22 -0400 Received: from localhost.localdomain (ovpn-112-16.ams2.redhat.com [10.36.112.16]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r4GEHK4i012761; Thu, 16 May 2013 10:17:21 -0400 Message-ID: <5194EA6F.2000104@redhat.com> Date: Thu, 16 May 2013 14:17:00 -0000 From: Phil Muldoon MIME-Version: 1.0 To: Tom Tromey CC: "gdb-patches@sourceware.org" Subject: Re: [patch] Convert frame_stash to a hash table References: <5194DA88.6020705@redhat.com> <871u9711nn.fsf@fleche.redhat.com> In-Reply-To: <871u9711nn.fsf@fleche.redhat.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-SW-Source: 2013-05/txt/msg00620.txt.bz2 On 16/05/13 14:42, Tom Tromey wrote: >>>>>> "Phil" == Phil Muldoon writes: > > Phil> I think this patch improves the frame_stash "with filters" without > Phil> affecting "no filters" performance. > > Phil> Tested on x8664 with no regressions. > > Phil> What do you think? > > Thanks, Phil. I appreciate this. > > A few nits below. I have fixed up the changes, patch attached. Cheers, Phil -- Index: frame.c =================================================================== RCS file: /cvs/src/src/gdb/frame.c,v retrieving revision 1.317 diff -u -r1.317 frame.c --- frame.c 10 Apr 2013 15:11:11 -0000 1.317 +++ frame.c 16 May 2013 14:08:03 -0000 @@ -43,6 +43,7 @@ #include "block.h" #include "inline-frame.h" #include "tracepoint.h" +#include "hashtab.h" static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame); static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame); @@ -128,38 +129,107 @@ enum unwind_stop_reason stop_reason; }; -/* A frame stash used to speed up frame lookups. */ +/* A frame stash used to speed up frame lookups. Create a hash table + to stash frames previously accessed from the frame cache for + quicker subsequent retrieval. The hash table is emptied whenever + the frame cache is invalidated. */ + +static htab_t frame_stash; + +/* Internal function to calculate a hash from the frame_id addresses, + using as many valid addresses as possible. Frames below level 0 + are not stored in the hash table. */ + +static hashval_t +frame_addr_hash (const void *ap) +{ + const struct frame_info *frame = ap; + const struct frame_id f_id = frame->this_id.value; + hashval_t hash = 0; + + if (! f_id.stack_addr_p || ! f_id.code_addr_p || ! f_id.special_addr_p) + gdb_assert ("Cannot calculate hash for frame_id."); + + if (f_id.stack_addr_p) + hash = iterative_hash (&f_id.stack_addr, + sizeof (f_id.stack_addr), hash); + if (f_id.code_addr_p) + hash = iterative_hash (&f_id.code_addr, + sizeof (f_id.code_addr), hash); + if (f_id.special_addr_p) + hash = iterative_hash (&f_id.special_addr, + sizeof (f_id.special_addr), hash); -/* We currently only stash one frame at a time, as this seems to be - sufficient for now. */ -static struct frame_info *frame_stash = NULL; + return hash; +} + +/* Internal equality function for the hash table. This function + defers equality operations to frame_id_eq. */ + +static int +frame_addr_hash_eq (const void *a, const void *b) +{ + const struct frame_info *f_entry = a; + const struct frame_info *f_element = b; -/* Add the following FRAME to the frame stash. */ + return frame_id_eq (f_entry->this_id.value, + f_element->this_id.value); +} + +/* Internal function to create the frame_stash hash table. 100 seems + to be a good compromise to start the hash table at. */ + +static void +frame_stash_create (void) +{ + frame_stash = htab_create (100, + frame_addr_hash, + frame_addr_hash_eq, + NULL); +} + +/* Internal function to add a frame to the frame_stash hash table. Do + not store frames below 0 as they may not have any addresses to + calculate a hash. */ static void frame_stash_add (struct frame_info *frame) { - frame_stash = frame; + /* Do not stash frames below level 0. */ + if (frame->level >= 0) + { + struct frame_info **slot; + + slot = (struct frame_info **) htab_find_slot (frame_stash, + frame, + INSERT); + *slot = frame; + } } -/* Search the frame stash for an entry with the given frame ID. - If found, return that frame. Otherwise return NULL. */ +/* Internal function to search the frame stash for an entry with the + given frame ID. If found, return that frame. Otherwise return + NULL. */ static struct frame_info * frame_stash_find (struct frame_id id) { - if (frame_stash && frame_id_eq (frame_stash->this_id.value, id)) - return frame_stash; + struct frame_info dummy; + struct frame_info *frame; - return NULL; + dummy.this_id.value = id; + frame = htab_find (frame_stash, &dummy); + return frame; } -/* Invalidate the frame stash by removing all entries in it. */ +/* Internal function to invalidate the frame stash by removing all + entries in it. This only occurs when the frame cache is + invalidated. */ static void frame_stash_invalidate (void) { - frame_stash = NULL; + htab_empty (frame_stash); } /* Flag to control debugging. */ @@ -345,10 +415,9 @@ fprint_frame_id (gdb_stdlog, fi->this_id.value); fprintf_unfiltered (gdb_stdlog, " }\n"); } + frame_stash_add (fi); } - frame_stash_add (fi); - return fi->this_id.value; } @@ -2451,6 +2520,8 @@ { obstack_init (&frame_cache_obstack); + frame_stash_create (); + observer_attach_target_changed (frame_observer_target_changed); add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\