I did some investigation into libdw performance hotspots, and came up with a few tweaks that in total trim nearly 1/3 the running time. I'm running on Mark's recent empty-location patch, and I primarily used "tests/varlocs -k >/dev/null" as a moderately long-running benchmark. I'm using gcc-4.8.2-1.fc20.x86_64 and kernel-3.11.9-300.fc20.x86_64, running on an i7-2600.
The perf profile initially looked like this:
Samples: 343K of event 'cycles', Event count (approx.): 318932712301 33.69% varlocs libdw.so [.] __libdw_find_attr 16.47% varlocs libdw.so [.] lookup.isra.0 15.63% varlocs libdw.so [.] __libdw_form_val_len 13.11% varlocs libdw.so [.] dwarf_siblingof 4.84% varlocs libdw.so [.] dwarf_tag 4.62% varlocs libdw.so [.] walk_children.4364 2.35% varlocs libdw.so [.] __libdw_findabbrev 2.32% varlocs libdw.so [.] Dwarf_Abbrev_Hash_find 1.26% varlocs libdw.so [.] dwarf_child
Patch 1 addresses form_val_len with an inlined fast path for forms with constant length. Patch 2 is a rework of get_uleb128 and get_sleb128, which are significant in find_attr and elsewhere. Patch 3 addresses the hash lookup which is called often to find DIE abbreviations.
The perf profile now looks like this:
Samples: 229K of event 'cycles', Event count (approx.): 213925592727 44.63% varlocs libdw.so [.] __libdw_find_attr 22.28% varlocs libdw.so [.] dwarf_siblingof 7.64% varlocs libdw.so [.] walk_children.4388 7.07% varlocs libdw.so [.] dwarf_tag 5.18% varlocs libdw.so [.] __libdw_findabbrev 2.88% varlocs libdw.so [.] __libdw_form_val_compute_len 2.11% varlocs libdw.so [.] dwarf_child 1.44% varlocs libdw.so [.] __libdw_formref 1.12% varlocs libdw.so [.] scope_visitor
The remaining busy work is simply walking through attributes, from DIE to DIE. I believe optimizing this further will be hard without keeping track of DIE lengths somewhere, which is a lot to cache. Putting the length in Dwarf_Die itself is not feasible, because those are short- lived and frequently recreated.
Here's some summary information for how these patches change varloc -k:
libdw varlocs varlocs text time maxres Base: 243072 84.42s 242360k P1: 243296 74.91s 242356k P2: 243184 70.61s 242360k P3: 243600 56.75s 243588k
My timings are not statistically rigorous measurements, but it still seems a clear win across the board. Other benchmarks I've tried, like tests/allfcts and stap -l syscall.*, show similar improvement.
Feedback is always appreciated.
Thanks, Josh
Quite a few DW_FORMs have a fixed length for their data, and we can easily represent these in a small lookup table. The rest of the forms are left in the old function to compute as needed. Combined with inlining, this takes care of many forms with fewer branches and without any call. (It's conceivable that a smart compiler could make a similar lookup transformation from the large switch itself, but GCC doesn't.)
Signed-off-by: Josh Stone jistone@redhat.com --- libdw/ChangeLog | 6 ++++++ libdw/libdwP.h | 39 ++++++++++++++++++++++++++++++++++++--- libdw/libdw_form.c | 32 ++++---------------------------- 3 files changed, 46 insertions(+), 31 deletions(-)
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index 79bb4b57fc4a..a2e4b142a107 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,9 @@ +2013-12-09 Josh Stone jistone@redhat.com + + * libdw_form.c (__libdw_form_val_compute_len): Renamed function from + __libdw_form_val_len, now handling only non-constant form lengths. + * libdwP.h (__libdw_form_val_len): New inlined function. + 2013-12-09 Mark Wielaard mjw@redhat.com
* dwarf_getlocation.c (__libdw_intern_expression): Handle empty diff --git a/libdw/libdwP.h b/libdw/libdwP.h index 35ab6e79c3fa..bd668c710029 100644 --- a/libdw/libdwP.h +++ b/libdw/libdwP.h @@ -34,6 +34,7 @@ #include <stdbool.h>
#include <libdw.h> +#include <dwarf.h>
/* gettext helper macros. */ @@ -403,11 +404,43 @@ extern Dwarf_Abbrev *__libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, __nonnull_attribute__ (1) internal_function;
/* Helper functions for form handling. */ -extern size_t __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, - unsigned int form, - const unsigned char *valp) +extern size_t __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu, + unsigned int form, + const unsigned char *valp) __nonnull_attribute__ (1, 2, 4) internal_function;
+/* Find the length of a form attribute. */ +static inline size_t +__nonnull_attribute__ (1, 2, 4) +__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, + unsigned int form, const unsigned char *valp) +{ + /* Small lookup table of forms with fixed lengths. */ + static const uint8_t form_lengths[] = + { + [DW_FORM_data1] = 1, [DW_FORM_ref1] = 1, [DW_FORM_flag] = 1, + [DW_FORM_data2] = 2, [DW_FORM_ref2] = 2, + [DW_FORM_data4] = 4, [DW_FORM_ref4] = 4, + [DW_FORM_data8] = 8, [DW_FORM_ref8] = 8, [DW_FORM_ref_sig8] = 8, + }; + + /* Note that form_lengths[flag_present] is 0, like every other absent index. + * But since flag_present's length truly is 0, check for it explicitly. */ + if (form == DW_FORM_flag_present) + return 0; + + /* Return immediately for forms with fixed lengths. */ + if (form < sizeof(form_lengths) / sizeof(form_lengths[0])) + { + size_t len = form_lengths[form]; + if (len != 0) + return len; + } + + /* Other forms require some computation. */ + return __libdw_form_val_compute_len (dbg, cu, form, valp); +} + /* Helper function for DW_FORM_ref* handling. */ extern int __libdw_formref (Dwarf_Attribute *attr, Dwarf_Off *return_offset) __nonnull_attribute__ (1, 2) internal_function; diff --git a/libdw/libdw_form.c b/libdw/libdw_form.c index c476a6e31f32..cf8e4d854fcb 100644 --- a/libdw/libdw_form.c +++ b/libdw/libdw_form.c @@ -39,13 +39,15 @@
size_t internal_function -__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int form, - const unsigned char *valp) +__libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu, + unsigned int form, const unsigned char *valp) { const unsigned char *saved; Dwarf_Word u128; size_t result;
+ /* NB: This doesn't cover constant form lengths, which are + * already handled by the inlined __libdw_form_val_len. */ switch (form) { case DW_FORM_addr: @@ -82,32 +84,6 @@ __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int form, result = u128 + (valp - saved); break;
- case DW_FORM_flag_present: - result = 0; - break; - - case DW_FORM_ref1: - case DW_FORM_data1: - case DW_FORM_flag: - result = 1; - break; - - case DW_FORM_data2: - case DW_FORM_ref2: - result = 2; - break; - - case DW_FORM_data4: - case DW_FORM_ref4: - result = 4; - break; - - case DW_FORM_data8: - case DW_FORM_ref8: - case DW_FORM_ref_sig8: - result = 8; - break; - case DW_FORM_string: result = strlen ((char *) valp) + 1; break;
Josh Stone jistone@redhat.com writes:
- /* Small lookup table of forms with fixed lengths. */
- static const uint8_t form_lengths[] =
- {
[DW_FORM_data1] = 1, [DW_FORM_ref1] = 1, [DW_FORM_flag] = 1,
[DW_FORM_data2] = 2, [DW_FORM_ref2] = 2,
[DW_FORM_data4] = 4, [DW_FORM_ref4] = 4,
[DW_FORM_data8] = 8, [DW_FORM_ref8] = 8, [DW_FORM_ref_sig8] = 8,
- };
- /* Note that form_lengths[flag_present] is 0, like every other absent index.
- But since flag_present's length truly is 0, check for it explicitly. */
- if (form == DW_FORM_flag_present)
- return 0;
One way to get rid of this if would be to store X | 0x80 in the table (including 0 | 0x80 for DW_FORM_flag_present), and then return len ^ 0x80 later. I don't feel strongly about this though, and certainly not if it offsets the performance gains again ;)
- /* Return immediately for forms with fixed lengths. */
- if (form < sizeof(form_lengths) / sizeof(form_lengths[0]))
Space after sizeof
- {
size_t len = form_lengths[form];
if (len != 0)
- return len;
Fine otherwise.
Thanks, PM
On 12/12/2013 02:47 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
- /* Note that form_lengths[flag_present] is 0, like every other absent index.
- But since flag_present's length truly is 0, check for it explicitly. */
- if (form == DW_FORM_flag_present)
- return 0;
One way to get rid of this if would be to store X | 0x80 in the table (including 0 | 0x80 for DW_FORM_flag_present), and then return len ^ 0x80 later. I don't feel strongly about this though, and certainly not if it offsets the performance gains again ;)
That's a good idea, though I'd probably use len & 0x7f so the others don't need to have 0x80. I'll play with it.
- /* Return immediately for forms with fixed lengths. */
- if (form < sizeof(form_lengths) / sizeof(form_lengths[0]))
Space after sizeof
The spaces in all of these will be the end of me... ;)
Thanks, Josh
On 12/16/2013 02:18 PM, Roland McGrath wrote:
- /* Note that form_lengths[flag_present] is 0, like every other absent index.
- But since flag_present's length truly is 0, check for it explicitly. */
Extra * is bad comment formatting.
Right, Petr caught that on v2. These are committed now, but of course I'll still go back and address concerns if needed...
Thanks, Josh
This removes the IS_LIBDW distinction so LEB128 operations are now always inlined, and the implementations are simplified, more direct.
Signed-off-by: Josh Stone jistone@redhat.com --- libdw/ChangeLog | 14 +++++++ libdw/Makefile.am | 3 +- libdw/memory-access.c | 50 ----------------------- libdw/memory-access.h | 108 +++++++++++++++++++------------------------------- 4 files changed, 56 insertions(+), 119 deletions(-) delete mode 100644 libdw/memory-access.c
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index a2e4b142a107..93396e404d97 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,17 @@ +2013-12-10 Josh Stone jistone@redhat.com + + * memory-access.h (get_uleb128_rest_return): Removed. + (get_sleb128_rest_return): Removed + (get_uleb128_step): Make this a self-contained block. + (get_sleb128_step): Ditto, and use a bitfield to extend signs. + (get_uleb128): Make this wholly implemented by __libdw_get_uleb128. + (get_sleb128): Make this wholly implemented by __libdw_get_sleb128. + (__libdw_get_uleb128): Simplify and inline for all callers. + (__libdw_get_sleb128): Ditto. + * memory-access.c: Delete file. + * Makefile.am (libdw_a_SOURCES): Remove it. + (DEFS): Remove the now unused -DIS_LIBDW. + 2013-12-09 Josh Stone jistone@redhat.com
* libdw_form.c (__libdw_form_val_compute_len): Renamed function from diff --git a/libdw/Makefile.am b/libdw/Makefile.am index a22166a99e73..cd9e31435317 100644 --- a/libdw/Makefile.am +++ b/libdw/Makefile.am @@ -28,7 +28,6 @@ ## not, see http://www.gnu.org/licenses/. ## include $(top_srcdir)/config/eu.am -DEFS += -DIS_LIBDW if BUILD_STATIC AM_CFLAGS += -fpic endif @@ -79,7 +78,7 @@ libdw_a_SOURCES = dwarf_begin.c dwarf_begin_elf.c dwarf_end.c dwarf_getelf.c \ dwarf_getfuncs.c \ dwarf_decl_file.c dwarf_decl_line.c dwarf_decl_column.c \ dwarf_func_inline.c dwarf_getsrc_file.c \ - libdw_findcu.c libdw_form.c libdw_alloc.c memory-access.c \ + libdw_findcu.c libdw_form.c libdw_alloc.c \ libdw_visit_scopes.c \ dwarf_entry_breakpoints.c \ dwarf_next_cfi.c \ diff --git a/libdw/memory-access.c b/libdw/memory-access.c deleted file mode 100644 index 7666fb60a64c..000000000000 --- a/libdw/memory-access.c +++ /dev/null @@ -1,50 +0,0 @@ -/* Out of line functions for memory-access.h macros. - Copyright (C) 2005, 2006 Red Hat, Inc. - This file is part of elfutils. - - This file is free software; you can redistribute it and/or modify - it under the terms of either - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at - your option) any later version - - or - - * the GNU General Public License as published by the Free - Software Foundation; either version 2 of the License, or (at - your option) any later version - - or both in parallel, as here. - - elfutils is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received copies of the GNU General Public License and - the GNU Lesser General Public License along with this program. If - not, see http://www.gnu.org/licenses/. */ - -#ifdef HAVE_CONFIG_H -# include <config.h> -#endif -#include "libdwP.h" -#include "memory-access.h" - -uint64_t -internal_function -__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp) -{ - unsigned char __b; - get_uleb128_rest_return (acc, i, addrp); -} - -int64_t -internal_function -__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp) -{ - unsigned char __b; - int64_t _v = acc; - get_sleb128_rest_return (acc, i, addrp); -} diff --git a/libdw/memory-access.h b/libdw/memory-access.h index 16471990dfa0..0aa46c9994b9 100644 --- a/libdw/memory-access.h +++ b/libdw/memory-access.h @@ -37,90 +37,64 @@
/* Number decoding macros. See 7.6 Variable Length Data. */
-#define get_uleb128_step(var, addr, nth, break) \ - __b = *(addr)++; \ - var |= (uintmax_t) (__b & 0x7f) << (nth * 7); \ - if (likely ((__b & 0x80) == 0)) \ - break +#define len_leb128(var) ((8 * sizeof (var) + 6) / 7)
-#define get_uleb128(var, addr) \ +#define get_uleb128_step(var, addr, nth) \ do { \ - unsigned char __b; \ - var = 0; \ - get_uleb128_step (var, addr, 0, break); \ - var = __libdw_get_uleb128 (var, 1, &(addr)); \ + unsigned char __b = *(addr)++; \ + (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \ + if (likely ((__b & 0x80) == 0)) \ + return (var); \ } while (0)
-#define get_uleb128_rest_return(var, i, addrp) \ +static inline uint64_t +__libdw_get_uleb128 (const unsigned char **addrp) +{ + uint64_t acc = 0; + get_uleb128_step (acc, *addrp, 0); + for (unsigned int i = 1; i < len_leb128(acc); ++i) + get_uleb128_step (acc, *addrp, i); + /* Other implementations set VALUE to UINT_MAX in this + case. So we better do this as well. */ + return UINT64_MAX; +} + +#define get_uleb128(var, addr) \ do { \ - for (; i < 10; ++i) \ - { \ - get_uleb128_step (var, *addrp, i, return var); \ - } \ - /* Other implementations set VALUE to UINT_MAX in this \ - case. So we better do this as well. */ \ - return UINT64_MAX; \ + (var) = __libdw_get_uleb128(&(addr)); \ + (void)(var); \ } while (0)
/* The signed case is similar, but we sign-extend the result. */
-#define get_sleb128_step(var, addr, nth, break) \ - __b = *(addr)++; \ - _v |= (uint64_t) (__b & 0x7f) << (nth * 7); \ - if (likely ((__b & 0x80) == 0)) \ - { \ - var = (_v << (64 - (nth * 7) - 7)) >> (64 - (nth * 7) - 7); \ - break; \ - } \ - else do {} while (0) - -#define get_sleb128(var, addr) \ - do { \ - unsigned char __b; \ - int64_t _v = 0; \ - get_sleb128_step (var, addr, 0, break); \ - var = __libdw_get_sleb128 (_v, 1, &(addr)); \ - } while (0) - -#define get_sleb128_rest_return(var, i, addrp) \ +#define get_sleb128_step(var, addr, nth) \ do { \ - for (; i < 9; ++i) \ + unsigned char __b = *(addr)++; \ + if (likely ((__b & 0x80) == 0)) \ { \ - get_sleb128_step (var, *addrp, i, return var); \ + struct { signed int i:7; } __s = { .i = __b }; \ + (var) |= (typeof (var)) __s.i << ((nth) * 7); \ + return (var); \ } \ - __b = *(*addrp)++; \ - if (likely ((__b & 0x80) == 0)) \ - return var | ((uint64_t) __b << 63); \ - else \ - /* Other implementations set VALUE to INT_MAX in this \ - case. So we better do this as well. */ \ - return INT64_MAX; \ + (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \ } while (0)
-#ifdef IS_LIBDW -extern uint64_t __libdw_get_uleb128 (uint64_t acc, unsigned int i, - const unsigned char **addrp) - internal_function attribute_hidden; -extern int64_t __libdw_get_sleb128 (int64_t acc, unsigned int i, - const unsigned char **addrp) - internal_function attribute_hidden; -#else -static inline uint64_t -__attribute__ ((unused)) -__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp) -{ - unsigned char __b; - get_uleb128_rest_return (acc, i, addrp); -} static inline int64_t -__attribute__ ((unused)) -__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp) +__libdw_get_sleb128 (const unsigned char **addrp) { - unsigned char __b; - int64_t _v = acc; - get_sleb128_rest_return (acc, i, addrp); + int64_t acc = 0; + for (unsigned int i = 0; i < len_leb128(acc); ++i) + get_sleb128_step (acc, *addrp, i); + /* Other implementations set VALUE to INT_MAX in this + case. So we better do this as well. */ + return INT64_MAX; } -#endif + +#define get_sleb128(var, addr) \ + do { \ + (var) = __libdw_get_sleb128(&(addr)); \ + (void)(var); \ + } while (0)
/* We use simple memory access functions in case the hardware allows it.
Josh Stone jistone@redhat.com writes:
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index a2e4b142a107..93396e404d97 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,17 @@ +2013-12-10 Josh Stone jistone@redhat.com
- memory-access.h (get_uleb128_rest_return): Removed.
- (get_sleb128_rest_return): Removed
Period.
+static inline uint64_t +__libdw_get_uleb128 (const unsigned char **addrp) +{
- uint64_t acc = 0;
- get_uleb128_step (acc, *addrp, 0);
- for (unsigned int i = 1; i < len_leb128(acc); ++i)
- get_uleb128_step (acc, *addrp, i);
Is there a reason not to use for (i = 0; ...) instead of the pre-step followed by a for (i = 1; ...)? The only difference would be for len_leb128 of 0, where your code makes one step anyway, but that can't happen. Then you could just expand get_uleb128_step inline, and get rid of it altogether.
Also, the len_leb128 call needs space before (...).
- /* Other implementations set VALUE to UINT_MAX in this
case. So we better do this as well. */
- return UINT64_MAX;
+}
+#define get_uleb128(var, addr) \ do { \
- (var) = __libdw_get_uleb128(&(addr)); \
- (void)(var); \ } while (0)
Space before (...). Space after type cast operator.
Actually, could this actually be defined like this?
#define get_uleb128(var, addr) ((var) = __libdw_get_uleb128 (&(addr)))
Then you wouldn't need the cast as the only set-but-not-used warnings would come from sites that actually set but not use, and those could be changed to simply call __libdw_get_uleb128. But that's probably a logically separate change.
+#define get_sleb128_step(var, addr, nth) \ do { \
- unsigned char __b = *(addr)++; \
- if (likely ((__b & 0x80) == 0)) \ { \
struct { signed int i:7; } __s = { .i = __b }; \
(var) |= (typeof (var)) __s.i << ((nth) * 7); \
Oh, the bitfield trick is clever!
return (var); \ } \
- (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \ } while (0)
static inline int64_t +__libdw_get_sleb128 (const unsigned char **addrp) {
- int64_t acc = 0;
- for (unsigned int i = 0; i < len_leb128(acc); ++i)
Space before (...).
- get_sleb128_step (acc, *addrp, i);
- /* Other implementations set VALUE to INT_MAX in this
case. So we better do this as well. */
- return INT64_MAX;
}
+#define get_sleb128(var, addr) \
- do { \
- (var) = __libdw_get_sleb128(&(addr)); \
- (void)(var); \
- } while (0)
Same comments as for get_uleb128.
This all looks fine to me. I find the new code much clearer than the original, which seemed to wind every which way and was hard to follow.
Thanks, PM
On 12/12/2013 04:13 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
+static inline uint64_t +__libdw_get_uleb128 (const unsigned char **addrp) +{
- uint64_t acc = 0;
- get_uleb128_step (acc, *addrp, 0);
- for (unsigned int i = 1; i < len_leb128(acc); ++i)
- get_uleb128_step (acc, *addrp, i);
Is there a reason not to use for (i = 0; ...) instead of the pre-step followed by a for (i = 1; ...)? The only difference would be for len_leb128 of 0, where your code makes one step anyway, but that can't happen. Then you could just expand get_uleb128_step inline, and get rid of it altogether.
Ah, yes, I should explain that a little. I found that the code was actually faster with the first step unrolled. And you may have noticed I didn't do this for sleb128, because I found that slightly slower.
It seems to work like an extra hint to the compiler. There's already a likely-return in the loop, but writing it this way seems to convince gcc that the first step in particular is *really* likely to return. Then that step also gets to const-prop the zero.
I can only guess that the sign-extension for sleb128 is complicated enough to nullify the gain of unrolling.
+#define get_uleb128(var, addr) \ do { \
- (var) = __libdw_get_uleb128(&(addr)); \
- (void)(var); \ } while (0)
Space before (...). Space after type cast operator.
Actually, could this actually be defined like this?
#define get_uleb128(var, addr) ((var) = __libdw_get_uleb128 (&(addr)))
Then you wouldn't need the cast as the only set-but-not-used warnings would come from sites that actually set but not use, and those could be changed to simply call __libdw_get_uleb128. But that's probably a logically separate change.
Right, there are two reasons I kept it this way. One is the cast for set-but-not-used, as you note, which didn't trigger before because the former macros did both read and write the value in place. I think there was only one caller affected though, so I could just change that. The do-while keeps the macro as a statement, vs your expression, but maybe that doesn't matter much.
+#define get_sleb128_step(var, addr, nth) \ do { \
- unsigned char __b = *(addr)++; \
- if (likely ((__b & 0x80) == 0)) \ { \
struct { signed int i:7; } __s = { .i = __b }; \
(var) |= (typeof (var)) __s.i << ((nth) * 7); \
Oh, the bitfield trick is clever!
I should give credit, I found that trick here: http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
The former code was trying to sign-extend after the value was shifted and combined, which as a variable width is harder. I really like that this way the compiler is fully aware that this is a sign extension, rather than being a side effect of ORing bits or left-right shifts.
This all looks fine to me. I find the new code much clearer than the original, which seemed to wind every which way and was hard to follow.
I agree the original was convoluted, and I think it was actually broken for some edge cases, though you almost have to look at it preprocessed to make sense of it. In particular, __libdw_get_sleb128 ORed with acc in the final step, but only _v was kept updated throughout the loop. (But it's unlikely any real DWARF had a 10-byte sleb128 to hit this.)
Josh Stone jistone@redhat.com writes:
On 12/12/2013 04:13 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
+static inline uint64_t +__libdw_get_uleb128 (const unsigned char **addrp) +{
- uint64_t acc = 0;
- get_uleb128_step (acc, *addrp, 0);
- for (unsigned int i = 1; i < len_leb128(acc); ++i)
- get_uleb128_step (acc, *addrp, i);
Is there a reason not to use for (i = 0; ...) instead of the pre-step followed by a for (i = 1; ...)?
Ah, yes, I should explain that a little. I found that the code was actually faster with the first step unrolled.
Ah, I think that's fine then, but needs a comment.
Thanks, PM
On Thu, 2013-12-12 at 11:06 -0800, Josh Stone wrote:
On 12/12/2013 04:13 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
+#define get_sleb128_step(var, addr, nth) \ do { \
- unsigned char __b = *(addr)++; \
- if (likely ((__b & 0x80) == 0)) \ { \
struct { signed int i:7; } __s = { .i = __b }; \
(var) |= (typeof (var)) __s.i << ((nth) * 7); \
Oh, the bitfield trick is clever!
I should give credit, I found that trick here: http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
The former code was trying to sign-extend after the value was shifted and combined, which as a variable width is harder. I really like that this way the compiler is fully aware that this is a sign extension, rather than being a side effect of ORing bits or left-right shifts.
Sadly the neat trick triggers undefined behavior since we are trying to left shift a negative value. Even though it appears to work currently I am slightly afraid a compiler optimization might take advantage of this in the future (since it is undefined behavior it could just assume negative values won't occur) especially since this code is inlined in a lot of places, causing hard to diagnose errors.
The attached patch is very much not clever, but does what is intended in a well-defined way (it is basically what the DWARF spec gives as pseudo code). Does anybody see a better way?
Thanks,
Mark
On 04/22/2014 07:55 AM, Mark Wielaard wrote:
On Thu, 2013-12-12 at 11:06 -0800, Josh Stone wrote:
On 12/12/2013 04:13 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
+#define get_sleb128_step(var, addr, nth) \ do { \
- unsigned char __b = *(addr)++; \
- if (likely ((__b & 0x80) == 0)) \ { \
struct { signed int i:7; } __s = { .i = __b }; \
(var) |= (typeof (var)) __s.i << ((nth) * 7); \
Oh, the bitfield trick is clever!
I should give credit, I found that trick here: http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
The former code was trying to sign-extend after the value was shifted and combined, which as a variable width is harder. I really like that this way the compiler is fully aware that this is a sign extension, rather than being a side effect of ORing bits or left-right shifts.
Sadly the neat trick triggers undefined behavior since we are trying to left shift a negative value. Even though it appears to work currently I am slightly afraid a compiler optimization might take advantage of this in the future (since it is undefined behavior it could just assume negative values won't occur) especially since this code is inlined in a lot of places, causing hard to diagnose errors.
The attached patch is very much not clever, but does what is intended in a well-defined way (it is basically what the DWARF spec gives as pseudo code). Does anybody see a better way?
Multiply instead of shift. I.e.
(typeof (var)) (__b & 0x7f) * (1 << ((nth) * 7));
With any luck the compiler will even notice it's a multiply by a value with one bit set, and convert it back to a shift during optimization.
r~
On 04/22/2014 08:01 AM, Richard Henderson wrote:
On 04/22/2014 07:55 AM, Mark Wielaard wrote:
On Thu, 2013-12-12 at 11:06 -0800, Josh Stone wrote:
On 12/12/2013 04:13 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
+#define get_sleb128_step(var, addr, nth) \ do { \
- unsigned char __b = *(addr)++; \
- if (likely ((__b & 0x80) == 0)) \ { \
struct { signed int i:7; } __s = { .i = __b }; \
(var) |= (typeof (var)) __s.i << ((nth) * 7); \
Oh, the bitfield trick is clever!
I should give credit, I found that trick here: http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
The former code was trying to sign-extend after the value was shifted and combined, which as a variable width is harder. I really like that this way the compiler is fully aware that this is a sign extension, rather than being a side effect of ORing bits or left-right shifts.
Sadly the neat trick triggers undefined behavior since we are trying to left shift a negative value. Even though it appears to work currently I am slightly afraid a compiler optimization might take advantage of this in the future (since it is undefined behavior it could just assume negative values won't occur) especially since this code is inlined in a lot of places, causing hard to diagnose errors.
The attached patch is very much not clever, but does what is intended in a well-defined way (it is basically what the DWARF spec gives as pseudo code). Does anybody see a better way?
Multiply instead of shift. I.e.
(typeof (var)) (__b & 0x7f) * (1 << ((nth) * 7));
With any luck the compiler will even notice it's a multiply by a value with one bit set, and convert it back to a shift during optimization.
The trick in the original was that "(typeof (var)) __s.i" would extend the sign from the 7th bit, which I don't your mask will do. But if the only UB is left-shifting negative, then I think we can combine them.
Bah. That 1 needs to be typeof (var) too.
So in total:
struct { signed int i:7; } __s = { .i = __b }; (var) |= (typeof (var)) __s.i * ((typeof (var)) 1 << ((nth) * 7));
Better?
On 04/22/2014 08:52 AM, Josh Stone wrote:
The trick in the original was that "(typeof (var)) __s.i" would extend the sign from the 7th bit, which I don't your mask will do.
Yes, that was another cut/paste error. Not a great batting average this morning... ;-)
So in total:
struct { signed int i:7; } __s = { .i = __b }; (var) |= (typeof (var)) __s.i * ((typeof (var)) 1 << ((nth) * 7));
Better?
Yes, that's what I had in mind.
r~
On Tue, 2014-04-22 at 08:58 -0700, Richard Henderson wrote:
On 04/22/2014 08:52 AM, Josh Stone wrote:
So in total:
struct { signed int i:7; } __s = { .i = __b }; (var) |= (typeof (var)) __s.i * ((typeof (var)) 1 << ((nth) * 7));
Better?
Yes, that's what I had in mind.
Excellent. I changed the patch as attached. No undefined behavior detected, all tests PASS.
Thanks,
Mark
Mark Wielaard mjw@redhat.com writes:
Sadly the neat trick triggers undefined behavior since we are trying to left shift a negative value. Even though it appears to work currently I am slightly afraid a compiler optimization might take advantage of this in the future (since it is undefined behavior it could just assume negative values won't occur) especially since this code is inlined in a lot of places, causing hard to diagnose errors.
Ouch. Yeah, I agree, it is essentially a matter of time before this whole thing is optimized away or something.
diff --git a/libdw/memory-access.h b/libdw/memory-access.h index d0ee63c..c6e4bdc 100644 --- a/libdw/memory-access.h +++ b/libdw/memory-access.h @@ -70,8 +70,9 @@ __libdw_get_uleb128 (const unsigned char **addrp) unsigned char __b = *(addr)++; \ if (likely ((__b & 0x80) == 0)) \ { \
- struct { signed int i:7; } __s = { .i = __b }; \
- (var) |= (typeof (var)) __s.i << ((nth) * 7); \
- (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \
- if ((((nth) + 1) < 8 * sizeof (var)) && (__b & 0x40)) \
return (var); \ } \ (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \(var) |= -(((uint64_t) 1) << (((nth) + 1) * 7)); \
Wouldn't something like this get us off the hook as well?
- (var) |= (typeof (var)) __s.i << ((nth) * 7); \ + (var) |= (typeof (var)) \ + (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7)); \
We are really only using the bitfield trick to avoid having to sign-extend by hand, but we can shift unsigned without losing anything.
Thanks, PM
On 04/23/2014 03:17 AM, Petr Machata wrote:
Wouldn't something like this get us off the hook as well?
- (var) |= (typeof (var)) __s.i << ((nth) * 7); \
- (var) |= (typeof (var)) \
(((uint64_t) (typeof (var)) __s.i) << ((nth) * 7)); \
We are really only using the bitfield trick to avoid having to sign-extend by hand, but we can shift unsigned without losing anything.
It gets us off the hook, but might introduce a 64-bit shift where only a 32-bit shift was required.
Sadly, (unsigned typeof(var)) doesn't work. ;-)
But I gave the multiplication change a look, and the compiler is in fact optimizing the multiplication by a power of 2 back into a shift.
r~
Richard Henderson rth@redhat.com writes:
On 04/23/2014 03:17 AM, Petr Machata wrote:
Wouldn't something like this get us off the hook as well?
- (var) |= (typeof (var)) __s.i << ((nth) * 7); \
- (var) |= (typeof (var)) \
(((uint64_t) (typeof (var)) __s.i) << ((nth) * 7)); \
We are really only using the bitfield trick to avoid having to sign-extend by hand, but we can shift unsigned without losing anything.
It gets us off the hook, but might introduce a 64-bit shift where only a 32-bit shift was required.
Good point, but get_sleb128_step is only used from __libdw_get_sleb128, where the type is int64_t. This macro is not safe for outside use anyway, as it uses its parameters more than once.
Hmm, should we maybe #undef it after __libdw_get_sleb128, so that it's clear that it's for local use only?
Thanks, PM
On 04/23/2014 11:32 AM, Petr Machata wrote:
Richard Henderson rth@redhat.com writes:
On 04/23/2014 03:17 AM, Petr Machata wrote:
Wouldn't something like this get us off the hook as well?
- (var) |= (typeof (var)) __s.i << ((nth) * 7); \
- (var) |= (typeof (var)) \
(((uint64_t) (typeof (var)) __s.i) << ((nth) * 7)); \
We are really only using the bitfield trick to avoid having to sign-extend by hand, but we can shift unsigned without losing anything.
It gets us off the hook, but might introduce a 64-bit shift where only a 32-bit shift was required.
Good point, but get_sleb128_step is only used from __libdw_get_sleb128, where the type is int64_t. This macro is not safe for outside use anyway, as it uses its parameters more than once.
Hmm, should we maybe #undef it after __libdw_get_sleb128, so that it's clear that it's for local use only?
In that case, why play around with the typeof at all? Just merge the macro into its only user. At which point using uint64_t makes total sense in context.
Similarly with get_uleb128_step, I assume, at least wrt to the typeof.
r~
On 04/23/2014 11:51 AM, Richard Henderson wrote:
On 04/23/2014 11:32 AM, Petr Machata wrote:
Richard Henderson rth@redhat.com writes:
On 04/23/2014 03:17 AM, Petr Machata wrote:
Wouldn't something like this get us off the hook as well?
- (var) |= (typeof (var)) __s.i << ((nth) * 7); \
- (var) |= (typeof (var)) \
(((uint64_t) (typeof (var)) __s.i) << ((nth) * 7)); \
We are really only using the bitfield trick to avoid having to sign-extend by hand, but we can shift unsigned without losing anything.
It gets us off the hook, but might introduce a 64-bit shift where only a 32-bit shift was required.
Good point, but get_sleb128_step is only used from __libdw_get_sleb128, where the type is int64_t. This macro is not safe for outside use anyway, as it uses its parameters more than once.
Hmm, should we maybe #undef it after __libdw_get_sleb128, so that it's clear that it's for local use only?
In that case, why play around with the typeof at all? Just merge the macro into its only user. At which point using uint64_t makes total sense in context.
Similarly with get_uleb128_step, I assume, at least wrt to the typeof.
The way these are macro'd is partly a legacy of earlier code. It does help for the uleb case since unrolling the first step proved to benefit optimization. Keeping sleb this way is helpful to maintain their similarity as much as possible.
Sure, the typeof's are probably unnecessary anymore, but this is splitting hairs IMO. It doesn't help anything to drop this, and we could decide to provide narrower _libdw_get... in the future for certain callers.
How's this for a counter-proposal? I shamelessly reused your commit message and ChangeLog wording, please let me know if that's overstepping boundaries.
Thanks, PM
From 2ed5c470803d15c960a9a2574dc572ac1aa92b71 Mon Sep 17 00:00:00 2001
Message-Id: 2ed5c470803d15c960a9a2574dc572ac1aa92b71.1398284498.git.pmachata@redhat.com From: Petr Machata pmachata@redhat.com Date: Wed, 23 Apr 2014 22:19:57 +0200 Subject: [PATCH] libdw (get_sleb128_step): Remove undefined behavior. Gcc: nnimap+mail.corp.redhat.com:Sent To: elfutils-devel@lists.fedorahosted.org
As pointed out by gcc -fsanitize=undefined left shifting a negative value is undefined. Replace it with an explicit sign extension step.
Signed-off-by: Petr Machata pmachata@redhat.com --- libdw/ChangeLog | 5 +++++ libdw/memory-access.h | 3 ++- 2 files changed, 7 insertions(+), 1 deletions(-)
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index 49d70af..bd2f0e7 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,8 @@ +2014-04-23 Petr Machata pmachata@redhat.com + + * memory-access.h (get_sleb128_step): Remove undefined behavior of + left shifting a signed value by casting through unsigned. + 2014-04-13 Mark Wielaard mjw@redhat.com
* Makefile.am: Remove !MUDFLAP conditions. diff --git a/libdw/memory-access.h b/libdw/memory-access.h index d0ee63c..647a2f3 100644 --- a/libdw/memory-access.h +++ b/libdw/memory-access.h @@ -71,7 +71,8 @@ __libdw_get_uleb128 (const unsigned char **addrp) if (likely ((__b & 0x80) == 0)) \ { \ struct { signed int i:7; } __s = { .i = __b }; \ - (var) |= (typeof (var)) __s.i << ((nth) * 7); \ + (var) |= (typeof (var)) \ + (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7)); \ return (var); \ } \ (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \
On Wed, 2014-04-23 at 22:29 +0200, Petr Machata wrote:
How's this for a counter-proposal? I shamelessly reused your commit message and ChangeLog wording, please let me know if that's overstepping boundaries.
No it isn't. And thanks for the proposal. But I think I prefer the fix using multiplication as posted here: https://lists.fedorahosted.org/pipermail/elfutils-devel/2014-April/003991.ht... That one is also just a oneliner and more generic since it doesn't rely on having to cast to uint64_t. And Richard checked it still just generates a shift.
You are right that we don't really need the generic version, but just a int64_t one. But if we make it non-generic than I think we should go all the way and also do the other cleanups suggested to get rid of the typeofs and just use the 64bit types everywhere (and maybe inline or undef the macro). But please don't feel you need to clean it all up and "ungenericize" it all. That would be nice, but the main thing is that we get rid of the undefined behavior.
Thanks,
Mark
Mark Wielaard mjw@redhat.com writes:
On Wed, 2014-04-23 at 22:29 +0200, Petr Machata wrote:
How's this for a counter-proposal? I shamelessly reused your commit message and ChangeLog wording, please let me know if that's overstepping boundaries.
No it isn't. And thanks for the proposal. But I think I prefer the fix using multiplication as posted here: https://lists.fedorahosted.org/pipermail/elfutils-devel/2014-April/003991.ht... That one is also just a oneliner and more generic since it doesn't rely on having to cast to uint64_t. And Richard checked it still just generates a shift.
Ah, cool, I didn't notice that e-mail.
Thanks, PM
On Thu, 2014-04-24 at 00:32 +0200, Petr Machata wrote:
Mark Wielaard mjw@redhat.com writes:
But I think I prefer the fix using multiplication as posted here: https://lists.fedorahosted.org/pipermail/elfutils-devel/2014-April/003991.ht... That one is also just a oneliner and more generic since it doesn't rely on having to cast to uint64_t. And Richard checked it still just generates a shift.
Ah, cool, I didn't notice that e-mail.
OK, I pushed that fix and the other undefined behavior fixes posted earlier to master now:
readelf: handle_core_item make sure variable length array isn't zero size. libdwfl: __libdwfl_frame_reg_[gs]et use uint64_t when checking bits. readelf.c (print_gdb_index_section): Use unsigned int for 31 bits left shift. libdw (get_sleb128_step): Remove undefined behavior.
make CFLAGS="-g -fsanitize=undefined" && \ make CFLAGS="-g -fsanitize=undefined" check with gcc 4.9 should have zero FAILs now.
Cheers,
Mark
At the expense of some memory for a new static array in the CU, we can now retrieve low abbrev codes directly, without any hash operation. This relieves a hotspot from the modulus in hash lookup().
Signed-off-by: Josh Stone jistone@redhat.com --- libdw/ChangeLog | 7 +++++++ libdw/dwarf_getabbrev.c | 17 ++++++++++++++--- libdw/dwarf_tag.c | 7 +++++-- libdw/libdwP.h | 6 +++++- libdw/libdw_findcu.c | 2 ++ 5 files changed, 33 insertions(+), 6 deletions(-)
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index 93396e404d97..397f0c253348 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,5 +1,12 @@ 2013-12-10 Josh Stone jistone@redhat.com
+ * libdwP.h (Dwarf_CU): Add abbrev_array. + * libdw_findcu.c (__libdw_intern_next_unit): Initialize it. + * dwarf_getabbrev.c (__libdw_getabbrev): Use it. + * dwarf_tag.c (__libdw_findabbrev): Use it. + +2013-12-10 Josh Stone jistone@redhat.com + * memory-access.h (get_uleb128_rest_return): Removed. (get_sleb128_rest_return): Removed (get_uleb128_step): Make this a self-contained block. diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c index 87d89c1b816b..75cfea27c1ba 100644 --- a/libdw/dwarf_getabbrev.c +++ b/libdw/dwarf_getabbrev.c @@ -85,8 +85,14 @@ __libdw_getabbrev (dbg, cu, offset, lengthp, result) /* Check whether this code is already in the hash table. */ bool foundit = false; Dwarf_Abbrev *abb = NULL; - if (cu == NULL - || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL)) == NULL) + if (cu != NULL) + { + if (code < CU_ABBREV_ARRAY_SIZE) + abb = cu->abbrev_array[code]; + else + abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL); + } + if (cu == NULL || abb == NULL) { if (result == NULL) abb = libdw_typed_alloc (dbg, Dwarf_Abbrev); @@ -130,7 +136,12 @@ __libdw_getabbrev (dbg, cu, offset, lengthp, result)
/* Add the entry to the hash table. */ if (cu != NULL && ! foundit) - (void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb); + { + if (abb->code < CU_ABBREV_ARRAY_SIZE) + cu->abbrev_array[abb->code] = abb; + else + (void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb); + }
out: return abb; diff --git a/libdw/dwarf_tag.c b/libdw/dwarf_tag.c index ff012cf4265c..f76a7fe33c93 100644 --- a/libdw/dwarf_tag.c +++ b/libdw/dwarf_tag.c @@ -44,8 +44,11 @@ __libdw_findabbrev (struct Dwarf_CU *cu, unsigned int code) if (unlikely (code == 0)) return DWARF_END_ABBREV;
- /* See whether the entry is already in the hash table. */ - abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL); + /* See whether the entry is already in the list or hash table. */ + if (code < CU_ABBREV_ARRAY_SIZE) + abb = cu->abbrev_array[code]; + else + abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL); if (abb == NULL) while (cu->last_abbrev_offset != (size_t) -1l) { diff --git a/libdw/libdwP.h b/libdw/libdwP.h index bd668c710029..3cc94a3fc789 100644 --- a/libdw/libdwP.h +++ b/libdw/libdwP.h @@ -269,6 +269,8 @@ struct Dwarf_Aranges_s };
+#define CU_ABBREV_ARRAY_SIZE 256 + /* CU representation. */ struct Dwarf_CU { @@ -283,7 +285,9 @@ struct Dwarf_CU size_t type_offset; uint64_t type_sig8;
- /* Hash table for the abbreviations. */ + /* Simple array for the abbreviations with low codes. */ + Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE]; + /* Hash table for the abbreviations with higher codes. */ Dwarf_Abbrev_Hash abbrev_hash; /* Offset of the first abbreviation. */ size_t orig_abbrev_offset; diff --git a/libdw/libdw_findcu.c b/libdw/libdw_findcu.c index c0bff2af2a69..831cc4d24b71 100644 --- a/libdw/libdw_findcu.c +++ b/libdw/libdw_findcu.c @@ -33,6 +33,7 @@
#include <assert.h> #include <search.h> +#include <string.h> #include "libdwP.h"
static int @@ -105,6 +106,7 @@ __libdw_intern_next_unit (dbg, debug_types) newp->version = version; newp->type_sig8 = type_sig8; newp->type_offset = type_offset; + memset(newp->abbrev_array, 0, sizeof(newp->abbrev_array)); Dwarf_Abbrev_Hash_init (&newp->abbrev_hash, 41); newp->orig_abbrev_offset = newp->last_abbrev_offset = abbrev_offset; newp->lines = NULL;
Josh Stone jistone@redhat.com writes:
struct Dwarf_CU { @@ -283,7 +285,9 @@ struct Dwarf_CU size_t type_offset; uint64_t type_sig8;
- /* Hash table for the abbreviations. */
- /* Simple array for the abbreviations with low codes. */
- Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
This blows up Dwarf_CU from 100odd bytes to something like half the page, I'm not entirely fond of that. Especially since the hash table that follows is an on-demand-growing structure, having half a page reserved (possibly on stack) just in case seems wasteful.
I'm looking into some debuginfo files. libc has an average of 28 abbreviations per CU (with 108 being the most), libstdc++ an average of 77 (with 108 the most), gcc 88 (142), libbost_python 206 (290), vmlinux 112 (185). So reserving space for 256 seems overly generous. I'd be fine with a growable heap-allocated array capped at 256. Hopefully that would still be helpful performance-wise.
--- a/libdw/libdw_findcu.c +++ b/libdw/libdw_findcu.c @@ -105,6 +106,7 @@ __libdw_intern_next_unit (dbg, debug_types) newp->version = version; newp->type_sig8 = type_sig8; newp->type_offset = type_offset;
- memset(newp->abbrev_array, 0, sizeof(newp->abbrev_array));
Space after memset. That sizeof either shouldn't have parens, or there should be a space.
Thanks, PM
On 12/12/2013 09:07 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
struct Dwarf_CU { @@ -283,7 +285,9 @@ struct Dwarf_CU size_t type_offset; uint64_t type_sig8;
- /* Hash table for the abbreviations. */
- /* Simple array for the abbreviations with low codes. */
- Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
This blows up Dwarf_CU from 100odd bytes to something like half the page, I'm not entirely fond of that. Especially since the hash table that follows is an on-demand-growing structure, having half a page reserved (possibly on stack) just in case seems wasteful.
I'm looking into some debuginfo files. libc has an average of 28 abbreviations per CU (with 108 being the most), libstdc++ an average of 77 (with 108 the most), gcc 88 (142), libbost_python 206 (290), vmlinux 112 (185). So reserving space for 256 seems overly generous. I'd be fine with a growable heap-allocated array capped at 256. Hopefully that would still be helpful performance-wise.
OK, I'll experiment with less generous static sizes, on the heap, as well as dynamic/realloced size (still capped though).
I also had the idea that maybe lookup can sometimes skip the modulus, which was by far the hotspot instruction in lookup() by ~72%. Just basically moving my "is-it-a-small-code" branch into hash lookup. So everything would stay in the hash table, hopefully just a bit faster.
More things to try, anyway...
On 12/12/2013 11:16 AM, Josh Stone wrote:
On 12/12/2013 09:07 AM, Petr Machata wrote:
Josh Stone jistone@redhat.com writes:
struct Dwarf_CU { @@ -283,7 +285,9 @@ struct Dwarf_CU size_t type_offset; uint64_t type_sig8;
- /* Hash table for the abbreviations. */
- /* Simple array for the abbreviations with low codes. */
- Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
This blows up Dwarf_CU from 100odd bytes to something like half the page, I'm not entirely fond of that. Especially since the hash table that follows is an on-demand-growing structure, having half a page reserved (possibly on stack) just in case seems wasteful.
I'm looking into some debuginfo files. libc has an average of 28 abbreviations per CU (with 108 being the most), libstdc++ an average of 77 (with 108 the most), gcc 88 (142), libbost_python 206 (290), vmlinux 112 (185). So reserving space for 256 seems overly generous. I'd be fine with a growable heap-allocated array capped at 256. Hopefully that would still be helpful performance-wise.
OK, I'll experiment with less generous static sizes, on the heap, as well as dynamic/realloced size (still capped though).
I also had the idea that maybe lookup can sometimes skip the modulus, which was by far the hotspot instruction in lookup() by ~72%. Just basically moving my "is-it-a-small-code" branch into hash lookup. So everything would stay in the hash table, hopefully just a bit faster.
This actually works pretty well:
diff --git a/lib/dynamicsizehash.c b/lib/dynamicsizehash.c index 40f48d5ed119..eec9826c43be 100644 --- a/lib/dynamicsizehash.c +++ b/lib/dynamicsizehash.c @@ -50,7 +50,7 @@ lookup (htab, hval, val) TYPE val __attribute__ ((unused)); { /* First hash function: simply take the modul but prevent zero. */ - size_t idx = 1 + hval % htab->size; + size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
if (htab->table[idx].hashval != 0) { ---
libdw varlocs varlocs text time maxres Base: 243103 84.14s 237276k P1: 243295 74.90s 237276k P2: 243167 70.07s 237272k P3-old: 243583 57.14s 238464k P3-new: 243199 62.21s 237272k
This simple change (P3-new) is not quite as good as using the fixed array (P3-old), but it's still a speedup and doesn't add to the memory profile at all.
It's an improvement because well-behaved DWARF producers will use the lowest abbrev codes to be more compact in uleb128 encoding. Every file I've seen also has codes ordered, so __libdw_findabbrev/getabbrev will always build up the hash in increasing code order. This dynamic hash implementation already resizes itself to stay <90% full, which means here hval is always less than htab->size. A well-predicted branch proves to be faster than hitting the 'div' for me.
So in this typical case, the hash table is acting like just a dynamic array. However, if some strange DWARF producer didn't use low abbrev codes in order, the hash table will still do the right thing, no worse than before. And with other hash tables like sig8, where hval is large, the branch in that version of lookup() should be well-predicted the other way.
Thanks to Petr for the reviews - I made these changes:
Patch 1: Use 0x80 to represent flag_present's 0 in the table.
Patch 2: Added a comment for the manually unrolled step 0 of uleb128, and made both get_?leb128 macros into simple expressions. Fixed the one caller who was getting a set-but-unused warning from this.
Patch 3: Redid this as a smaller optimization directly on the hash lookup function. The performance gain is not as great, but it's a simpler change and doesn't increase memory use.
And my spacing should be improved everywhere. :)
Thanks, Josh
Quite a few DW_FORMs have a fixed length for their data, and we can easily represent these in a small lookup table. The rest of the forms are left in the old function to compute as needed. Combined with inlining, this takes care of many forms with fewer branches and without any call. (It's conceivable that a smart compiler could make a similar lookup transformation from the large switch itself, but GCC doesn't.)
Signed-off-by: Josh Stone jistone@redhat.com --- libdw/ChangeLog | 6 ++++++ libdw/libdwP.h | 36 +++++++++++++++++++++++++++++++++--- libdw/libdw_form.c | 32 ++++---------------------------- 3 files changed, 43 insertions(+), 31 deletions(-)
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index 79bb4b57fc4a..a2e4b142a107 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,9 @@ +2013-12-09 Josh Stone jistone@redhat.com + + * libdw_form.c (__libdw_form_val_compute_len): Renamed function from + __libdw_form_val_len, now handling only non-constant form lengths. + * libdwP.h (__libdw_form_val_len): New inlined function. + 2013-12-09 Mark Wielaard mjw@redhat.com
* dwarf_getlocation.c (__libdw_intern_expression): Handle empty diff --git a/libdw/libdwP.h b/libdw/libdwP.h index 35ab6e79c3fa..e323ce34f66b 100644 --- a/libdw/libdwP.h +++ b/libdw/libdwP.h @@ -34,6 +34,7 @@ #include <stdbool.h>
#include <libdw.h> +#include <dwarf.h>
/* gettext helper macros. */ @@ -403,11 +404,40 @@ extern Dwarf_Abbrev *__libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, __nonnull_attribute__ (1) internal_function;
/* Helper functions for form handling. */ -extern size_t __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, - unsigned int form, - const unsigned char *valp) +extern size_t __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu, + unsigned int form, + const unsigned char *valp) __nonnull_attribute__ (1, 2, 4) internal_function;
+/* Find the length of a form attribute. */ +static inline size_t +__nonnull_attribute__ (1, 2, 4) +__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, + unsigned int form, const unsigned char *valp) +{ + /* Small lookup table of forms with fixed lengths. Absent indexes are + * initialized 0, so any truly desired 0 is set to 0x80 and masked. */ + static const uint8_t form_lengths[] = + { + [DW_FORM_flag_present] = 0x80, + [DW_FORM_data1] = 1, [DW_FORM_ref1] = 1, [DW_FORM_flag] = 1, + [DW_FORM_data2] = 2, [DW_FORM_ref2] = 2, + [DW_FORM_data4] = 4, [DW_FORM_ref4] = 4, + [DW_FORM_data8] = 8, [DW_FORM_ref8] = 8, [DW_FORM_ref_sig8] = 8, + }; + + /* Return immediately for forms with fixed lengths. */ + if (form < sizeof form_lengths / sizeof form_lengths[0]) + { + uint8_t len = form_lengths[form]; + if (len != 0) + return len & 0x7f; /* Mask to allow 0x80 -> 0. */ + } + + /* Other forms require some computation. */ + return __libdw_form_val_compute_len (dbg, cu, form, valp); +} + /* Helper function for DW_FORM_ref* handling. */ extern int __libdw_formref (Dwarf_Attribute *attr, Dwarf_Off *return_offset) __nonnull_attribute__ (1, 2) internal_function; diff --git a/libdw/libdw_form.c b/libdw/libdw_form.c index c476a6e31f32..cf8e4d854fcb 100644 --- a/libdw/libdw_form.c +++ b/libdw/libdw_form.c @@ -39,13 +39,15 @@
size_t internal_function -__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int form, - const unsigned char *valp) +__libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu, + unsigned int form, const unsigned char *valp) { const unsigned char *saved; Dwarf_Word u128; size_t result;
+ /* NB: This doesn't cover constant form lengths, which are + * already handled by the inlined __libdw_form_val_len. */ switch (form) { case DW_FORM_addr: @@ -82,32 +84,6 @@ __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int form, result = u128 + (valp - saved); break;
- case DW_FORM_flag_present: - result = 0; - break; - - case DW_FORM_ref1: - case DW_FORM_data1: - case DW_FORM_flag: - result = 1; - break; - - case DW_FORM_data2: - case DW_FORM_ref2: - result = 2; - break; - - case DW_FORM_data4: - case DW_FORM_ref4: - result = 4; - break; - - case DW_FORM_data8: - case DW_FORM_ref8: - case DW_FORM_ref_sig8: - result = 8; - break; - case DW_FORM_string: result = strlen ((char *) valp) + 1; break;
Josh Stone jistone@redhat.com writes:
- /* Small lookup table of forms with fixed lengths. Absent indexes are
- initialized 0, so any truly desired 0 is set to 0x80 and masked. */
/* GNU coding style has comments that go without continuation asterisks. */
Sorry, I didn't notice this before. Or maybe it wasn't there, I don't know. The patch is fine otherwise, so it can be committed without re-posting after this is corrected.
- /* NB: This doesn't cover constant form lengths, which are
- already handled by the inlined __libdw_form_val_len. */
Here as well.
Thanks, PM
This removes the IS_LIBDW distinction so LEB128 operations are now always inlined, and the implementations are simplified, more direct.
Signed-off-by: Josh Stone jistone@redhat.com --- libdw/ChangeLog | 15 +++++++ libdw/Makefile.am | 3 +- libdw/dwarf_getlocation.c | 3 +- libdw/memory-access.c | 50 ---------------------- libdw/memory-access.h | 107 ++++++++++++++++------------------------------ 5 files changed, 55 insertions(+), 123 deletions(-) delete mode 100644 libdw/memory-access.c
diff --git a/libdw/ChangeLog b/libdw/ChangeLog index a2e4b142a107..aa7b9ca486c2 100644 --- a/libdw/ChangeLog +++ b/libdw/ChangeLog @@ -1,3 +1,18 @@ +2013-12-10 Josh Stone jistone@redhat.com + + * memory-access.h (get_uleb128_rest_return): Removed. + (get_sleb128_rest_return): Removed. + (get_uleb128_step): Make this a self-contained block. + (get_sleb128_step): Ditto, and use a bitfield to extend signs. + (get_uleb128): Make this wholly implemented by __libdw_get_uleb128. + (get_sleb128): Make this wholly implemented by __libdw_get_sleb128. + (__libdw_get_uleb128): Simplify and inline for all callers. + (__libdw_get_sleb128): Ditto. + * dwarf_getlocation.c (store_implicit_value): Void the unused uleb128. + * memory-access.c: Delete file. + * Makefile.am (libdw_a_SOURCES): Remove it. + (DEFS): Remove the now unused -DIS_LIBDW. + 2013-12-09 Josh Stone jistone@redhat.com
* libdw_form.c (__libdw_form_val_compute_len): Renamed function from diff --git a/libdw/Makefile.am b/libdw/Makefile.am index a22166a99e73..cd9e31435317 100644 --- a/libdw/Makefile.am +++ b/libdw/Makefile.am @@ -28,7 +28,6 @@ ## not, see http://www.gnu.org/licenses/. ## include $(top_srcdir)/config/eu.am -DEFS += -DIS_LIBDW if BUILD_STATIC AM_CFLAGS += -fpic endif @@ -79,7 +78,7 @@ libdw_a_SOURCES = dwarf_begin.c dwarf_begin_elf.c dwarf_end.c dwarf_getelf.c \ dwarf_getfuncs.c \ dwarf_decl_file.c dwarf_decl_line.c dwarf_decl_column.c \ dwarf_func_inline.c dwarf_getsrc_file.c \ - libdw_findcu.c libdw_form.c libdw_alloc.c memory-access.c \ + libdw_findcu.c libdw_form.c libdw_alloc.c \ libdw_visit_scopes.c \ dwarf_entry_breakpoints.c \ dwarf_next_cfi.c \ diff --git a/libdw/dwarf_getlocation.c b/libdw/dwarf_getlocation.c index 4124ae36b84f..8dffb83f496f 100644 --- a/libdw/dwarf_getlocation.c +++ b/libdw/dwarf_getlocation.c @@ -100,8 +100,7 @@ store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op) struct loc_block_s *block = libdw_alloc (dbg, struct loc_block_s, sizeof (struct loc_block_s), 1); const unsigned char *data = (const unsigned char *) (uintptr_t) op->number2; - Dwarf_Word blength; // Ignored, equal to op->number. - get_uleb128 (blength, data); + (void) __libdw_get_uleb128 (&data); // Ignored, equal to op->number. block->addr = op; block->data = (unsigned char *) data; block->length = op->number; diff --git a/libdw/memory-access.c b/libdw/memory-access.c deleted file mode 100644 index 7666fb60a64c..000000000000 --- a/libdw/memory-access.c +++ /dev/null @@ -1,50 +0,0 @@ -/* Out of line functions for memory-access.h macros. - Copyright (C) 2005, 2006 Red Hat, Inc. - This file is part of elfutils. - - This file is free software; you can redistribute it and/or modify - it under the terms of either - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at - your option) any later version - - or - - * the GNU General Public License as published by the Free - Software Foundation; either version 2 of the License, or (at - your option) any later version - - or both in parallel, as here. - - elfutils is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received copies of the GNU General Public License and - the GNU Lesser General Public License along with this program. If - not, see http://www.gnu.org/licenses/. */ - -#ifdef HAVE_CONFIG_H -# include <config.h> -#endif -#include "libdwP.h" -#include "memory-access.h" - -uint64_t -internal_function -__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp) -{ - unsigned char __b; - get_uleb128_rest_return (acc, i, addrp); -} - -int64_t -internal_function -__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp) -{ - unsigned char __b; - int64_t _v = acc; - get_sleb128_rest_return (acc, i, addrp); -} diff --git a/libdw/memory-access.h b/libdw/memory-access.h index 16471990dfa0..d0ee63c53f99 100644 --- a/libdw/memory-access.h +++ b/libdw/memory-access.h @@ -37,90 +37,59 @@
/* Number decoding macros. See 7.6 Variable Length Data. */
-#define get_uleb128_step(var, addr, nth, break) \ - __b = *(addr)++; \ - var |= (uintmax_t) (__b & 0x7f) << (nth * 7); \ - if (likely ((__b & 0x80) == 0)) \ - break - -#define get_uleb128(var, addr) \ - do { \ - unsigned char __b; \ - var = 0; \ - get_uleb128_step (var, addr, 0, break); \ - var = __libdw_get_uleb128 (var, 1, &(addr)); \ - } while (0) +#define len_leb128(var) ((8 * sizeof (var) + 6) / 7)
-#define get_uleb128_rest_return(var, i, addrp) \ +#define get_uleb128_step(var, addr, nth) \ do { \ - for (; i < 10; ++i) \ - { \ - get_uleb128_step (var, *addrp, i, return var); \ - } \ - /* Other implementations set VALUE to UINT_MAX in this \ - case. So we better do this as well. */ \ - return UINT64_MAX; \ + unsigned char __b = *(addr)++; \ + (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \ + if (likely ((__b & 0x80) == 0)) \ + return (var); \ } while (0)
-/* The signed case is similar, but we sign-extend the result. */ +static inline uint64_t +__libdw_get_uleb128 (const unsigned char **addrp) +{ + uint64_t acc = 0; + /* Unroll the first step to help the compiler optimize + for the common single-byte case. */ + get_uleb128_step (acc, *addrp, 0); + for (unsigned int i = 1; i < len_leb128 (acc); ++i) + get_uleb128_step (acc, *addrp, i); + /* Other implementations set VALUE to UINT_MAX in this + case. So we better do this as well. */ + return UINT64_MAX; +}
-#define get_sleb128_step(var, addr, nth, break) \ - __b = *(addr)++; \ - _v |= (uint64_t) (__b & 0x7f) << (nth * 7); \ - if (likely ((__b & 0x80) == 0)) \ - { \ - var = (_v << (64 - (nth * 7) - 7)) >> (64 - (nth * 7) - 7); \ - break; \ - } \ - else do {} while (0) +#define get_uleb128(var, addr) ((var) = __libdw_get_uleb128 (&(addr)))
-#define get_sleb128(var, addr) \ - do { \ - unsigned char __b; \ - int64_t _v = 0; \ - get_sleb128_step (var, addr, 0, break); \ - var = __libdw_get_sleb128 (_v, 1, &(addr)); \ - } while (0) +/* The signed case is similar, but we sign-extend the result. */
-#define get_sleb128_rest_return(var, i, addrp) \ +#define get_sleb128_step(var, addr, nth) \ do { \ - for (; i < 9; ++i) \ + unsigned char __b = *(addr)++; \ + if (likely ((__b & 0x80) == 0)) \ { \ - get_sleb128_step (var, *addrp, i, return var); \ + struct { signed int i:7; } __s = { .i = __b }; \ + (var) |= (typeof (var)) __s.i << ((nth) * 7); \ + return (var); \ } \ - __b = *(*addrp)++; \ - if (likely ((__b & 0x80) == 0)) \ - return var | ((uint64_t) __b << 63); \ - else \ - /* Other implementations set VALUE to INT_MAX in this \ - case. So we better do this as well. */ \ - return INT64_MAX; \ + (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7); \ } while (0)
-#ifdef IS_LIBDW -extern uint64_t __libdw_get_uleb128 (uint64_t acc, unsigned int i, - const unsigned char **addrp) - internal_function attribute_hidden; -extern int64_t __libdw_get_sleb128 (int64_t acc, unsigned int i, - const unsigned char **addrp) - internal_function attribute_hidden; -#else -static inline uint64_t -__attribute__ ((unused)) -__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp) -{ - unsigned char __b; - get_uleb128_rest_return (acc, i, addrp); -} static inline int64_t -__attribute__ ((unused)) -__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp) +__libdw_get_sleb128 (const unsigned char **addrp) { - unsigned char __b; - int64_t _v = acc; - get_sleb128_rest_return (acc, i, addrp); + int64_t acc = 0; + /* Unrolling 0 like uleb128 didn't prove to benefit optimization. */ + for (unsigned int i = 0; i < len_leb128 (acc); ++i) + get_sleb128_step (acc, *addrp, i); + /* Other implementations set VALUE to INT_MAX in this + case. So we better do this as well. */ + return INT64_MAX; } -#endif + +#define get_sleb128(var, addr) ((var) = __libdw_get_sleb128 (&(addr)))
/* We use simple memory access functions in case the hardware allows it.
Josh Stone jistone@redhat.com writes:
This removes the IS_LIBDW distinction so LEB128 operations are now always inlined, and the implementations are simplified, more direct.
This looks fine.
Thanks, PM
For Dwarf_Abbrev codes, the most common case is that they're packed at the low end, saving uleb128 encoding size. Since the hash table is always resized to be no more than 90% full, those codes are always less than the table size, and dividing for the remainder is unnecessary.
Dwarf_Dies are frequently created anew, and need to find abbrev each time, so even that one division becomes a noticeable hotspot. This patch adds a branch to avoid it, which is very predictable for the CPU.
Signed-off-by: Josh Stone jistone@redhat.com --- lib/ChangeLog | 4 ++++ lib/dynamicsizehash.c | 5 +++-- 2 files changed, 7 insertions(+), 2 deletions(-)
diff --git a/lib/ChangeLog b/lib/ChangeLog index 6ce3168f0ae6..9b8899e2ca5c 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,3 +1,7 @@ +2013-12-12 Josh Stone jistone@redhat.com + + * dynamicsizehash.c (lookup): Add a shortcut around division. + 2013-04-30 Jan Kratochvil jan.kratochvil@redhat.com
* eu-config.h (COMPAT_VERSION_NEWPROTO): New. Twice. diff --git a/lib/dynamicsizehash.c b/lib/dynamicsizehash.c index 40f48d5ed119..acb360030376 100644 --- a/lib/dynamicsizehash.c +++ b/lib/dynamicsizehash.c @@ -49,8 +49,9 @@ lookup (htab, hval, val) HASHTYPE hval; TYPE val __attribute__ ((unused)); { - /* First hash function: simply take the modul but prevent zero. */ - size_t idx = 1 + hval % htab->size; + /* First hash function: simply take the modul but prevent zero. Small values + * can skip the division, which helps performance when this is common. */ + size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
if (htab->table[idx].hashval != 0) {
Josh Stone jistone@redhat.com writes:
- /* First hash function: simply take the modul but prevent zero. */
- size_t idx = 1 + hval % htab->size;
- /* First hash function: simply take the modul but prevent zero. Small values
- can skip the division, which helps performance when this is common. */
- size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
Again the continuation *. Otherwise this is fine, feel free to commit after correcting this nit.
Thanks, PM
With fixed comment formatting, these patches are now pushed.
Thanks! Josh
elfutils-devel@lists.fedorahosted.org