[PATCH 12/14] configure, ir, writer: Use parallel sort for big type sequences
Dodji Seketeli
dodji@seketeli.org
Fri Sep 25 21:06:06 GMT 2026
Sorting type sequences that contain more than 1.2 millions of types
(e.g, 2 millions types) seems to result in some quadratic degradation
of performance, at least when using the type_topo_comp "less than"
comparison operator. This is especially true when analyzing a Linux
kernel vmlinux binary.
This patch addresses the issue by using the parallel sort from
libstdc++, which API is present since C++17. The parallel sort is
used only when the number of types is greater than 1.2M.
The patch introduces abigail::ir::sort_types that encapsulates the use
of std::sort(std::execution::{par,seq}, ...) if the TBB dependency is
present. That new function is used by
sort_types_for_hash_computing_and_c14n, type_maps::get_types_sorted
and abigail::xml_writer::sort_types.
The configure script is adjusted to use C++17 instead of C++14, to
detect the presence of the TBB dependency and adjust the compilation
and linking flags accordingly.
Note that indirectly invoking the TBB library through parallel
std::sort induces what appears to be false positive warnings from
Thread Sanitizer. I believe this is because TBB itself is not
compiled with Thread Sanitizer and so the later misses some threading
and synchronization calls that happen in the former. The patch thus
updates the tsan-suppression.txt file to suppress those false positive
warnings.
* configure.ac: Conditionally use C++17 if the compiler supports
it, instead of the default C++14. If the compiler supports C++17,
then detect the presence of TBB and set the DEPS_{CPPFLAGS,LIBS}
variables accordingly.
* tsan-suppression.txt: Update Thread Sanitizer suppression.
* src/abg-ir-priv.h: Optionally #include <execution> if we are
compiled with C++17.
(sort_types): New function template.
(sort_types_for_hash_computing_and_c14n): Use the new sort_types.
Add a 'do_log' parameter.
(hash_and_canonicalize_types): Adjust to the new signature of
sort_types_for_hash_computing_and_c14n.
* src/abg-ir.cc (type_maps::get_types_sorted): Use the new
abigail::ir::sort_types instead of std::sort.
* src/abg-writer.cc (write_context::sort_types): Likewise.
* autoconf-archive/ax_check_compile_flag.m4: Copy new file from
GNU Autoconf archive at
https://github.com/autoconf-archive/autoconf-archive.
Signed-off-by: Dodji Seketeli <dodji@seketeli.org>
---
autoconf-archive/ax_check_compile_flag.m4 | 63 +++++++++++++++
configure.ac | 98 +++++++++++++++++++----
src/abg-ir-priv.h | 62 +++++++++++++-
src/abg-ir.cc | 4 +-
src/abg-writer.cc | 8 +-
tsan-suppression.txt | 36 ++++++---
6 files changed, 237 insertions(+), 34 deletions(-)
create mode 100644 autoconf-archive/ax_check_compile_flag.m4
diff --git a/autoconf-archive/ax_check_compile_flag.m4 b/autoconf-archive/ax_check_compile_flag.m4
new file mode 100644
index 00000000..54191c55
--- /dev/null
+++ b/autoconf-archive/ax_check_compile_flag.m4
@@ -0,0 +1,63 @@
+# ===========================================================================
+# https://www.gnu.org/software/autoconf-archive/ax_check_compile_flag.html
+# ===========================================================================
+#
+# SYNOPSIS
+#
+# AX_CHECK_COMPILE_FLAG(FLAG, [ACTION-SUCCESS], [ACTION-FAILURE], [EXTRA-FLAGS], [INPUT])
+#
+# DESCRIPTION
+#
+# Check whether the given FLAG works with the current language's compiler
+# or gives an error. (Warnings, however, are ignored)
+#
+# ACTION-SUCCESS/ACTION-FAILURE are shell commands to execute on
+# success/failure.
+#
+# If EXTRA-FLAGS is defined, it is added to the current language's default
+# flags (e.g. CFLAGS) when the check is done. The check is thus made with
+# the flags: "CFLAGS EXTRA-FLAGS FLAG". This can for example be used to
+# force the compiler to issue an error when a bad flag is given.
+#
+# INPUT gives an alternative input source to AC_COMPILE_IFELSE.
+#
+# NOTE: Implementation based on AX_CFLAGS_GCC_OPTION. Please keep this
+# macro in sync with AX_CHECK_{PREPROC,LINK}_FLAG.
+#
+# LICENSE
+#
+# Copyright (c) 2008 Guido U. Draheim <guidod@gmx.de>
+# Copyright (c) 2011 Maarten Bosmans <mkbosmans@gmail.com>
+#
+# Copying and distribution of this file, with or without modification, are
+# permitted in any medium without royalty provided the copyright notice
+# and this notice are preserved. This file is offered as-is, without any
+# warranty.
+
+#serial 11
+
+AC_DEFUN([AX_CHECK_COMPILE_FLAG],
+[AC_PREREQ(2.64)dnl for _AC_LANG_PREFIX and AS_VAR_IF
+AS_VAR_PUSHDEF([CACHEVAR],[ax_cv_check_[]_AC_LANG_ABBREV[]flags_$4_$1])dnl
+AC_CACHE_CHECK([whether the _AC_LANG compiler accepts $1], CACHEVAR, [
+ ax_check_save_flags=$[]_AC_LANG_PREFIX[]FLAGS
+ if test x"m4_case(_AC_LANG,
+ [C], [$GCC],
+ [C++], [$GXX],
+ [Fortran], [$GFC],
+ [Fortran 77], [$G77],
+ [Objective C], [$GOBJC],
+ [Objective C++], [$GOBJCXX],
+ [no])" = xyes ; then
+ add_gnu_werror="-Werror"
+ fi
+ _AC_LANG_PREFIX[]FLAGS="$[]_AC_LANG_PREFIX[]FLAGS $4 $1 $add_gnu_werror"
+ AC_COMPILE_IFELSE([m4_default([$5],[AC_LANG_PROGRAM()])],
+ [AS_VAR_SET(CACHEVAR,[yes])],
+ [AS_VAR_SET(CACHEVAR,[no])])
+ _AC_LANG_PREFIX[]FLAGS=$ax_check_save_flags])
+AS_VAR_IF(CACHEVAR,yes,
+ [m4_default([$2], :)],
+ [m4_default([$3], :)])
+AS_VAR_POPDEF([CACHEVAR])dnl
+])dnl AX_CHECK_COMPILE_FLAGS
diff --git a/configure.ac b/configure.ac
index b64da22c..50ea33a6 100644
--- a/configure.ac
+++ b/configure.ac
@@ -67,6 +67,10 @@ dnl This one is to be able to run "make check-valgrind"
dnl and have unit tests run under der Valgrind.
m4_include([autoconf-archive/ax_valgrind_check.m4])
+dnl This one is to detect supported compiler flags with
+dnl AX_CHECK_COMPILE_FLAG.
+m4_include([autoconf-archive/ax_check_compile_flag.m4])
+
AM_INIT_AUTOMAKE([1.11.1 foreign subdir-objects dist-xz tar-ustar parallel-tests])
AM_MAINTAINER_MODE([enable])
@@ -286,12 +290,54 @@ LT_INIT
AC_LANG([C++])
AC_LANG_COMPILER_REQUIRE
+dnl Set the level of C++ standard we use.
dnl
-dnl We use C++14. It has been the default in G++ since GCC 6. In el8
-dnl (that we still support), we do have GCC 8.x with c++14 as the
-dnl default, still.
-dnl
-CXX_STANDARD=c++14
+dnl By default, we use C++14. It has been the default in G++ since
+dnl GCC 8.5, which is what el8 has. We still support el8.
+CAN_SUPPORT_PARALLEL_SORT=no
+DEFAULT_CXX_STANDARD=14
+CXX_STANDARD=$DEFAULT_CXX_STANDARD
+AC_LANG_PUSH([C++])
+AX_CHECK_COMPILE_FLAG([-std=c++${CXX_STANDARD}], [
+ AC_MSG_NOTICE([C++$CXX_STANDARD language support detected, using it])
+ AC_DEFINE([HAVE_CXX$CXX_STANDARD], [1], [Define if C++$CXX_STANDARD is supported])
+], [
+ AC_MSG_ERROR([C++$CXX_STANDARD support is required])
+])
+AC_LANG_POP([C++])
+
+dnl But if the compiler supports C++17, we use that because we'd like
+dnl to use the parallel sort algorithms.
+AC_LANG_PUSH([C++])
+AX_CHECK_COMPILE_FLAG([-std=c++17], [
+ AC_MSG_NOTICE([C++17 language support detected, using it])
+ CXX_STANDARD=17
+ AC_DEFINE([HAVE_CXX17], [1], [Define if C++17 is supported])
+ CAN_SUPPORT_PARALLEL_SORT=yes
+], [
+ AC_MSG_NOTICE([C++17 support is not present, falling back to C++$CXX_STANDARD])
+])
+AC_LANG_POP([C++])
+
+if test x$CAN_SUPPORT_PARALLEL_SORT = xyes; then
+ ac_save_CXXFLAGS="$CXXFLAGS"
+ CXXFLAGS="-std=c++$CXX_STANDARD"
+ AC_LANG_PUSH([C++])
+ AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[#include <execution>]])],
+ [HAS_EXECUTION_HEADER_FILE=yes],
+ [HAS_EXECUTION_HEADER_FILE=no])
+ AC_LANG_POP([C++])
+ CXXFLAGS="$ac_save_CXXFLAGS"
+
+fi
+
+if test x$HAS_EXECUTION_HEADER_FILE = xyes; then
+ AC_MSG_NOTICE([has <execution> header file])
+ AC_DEFINE([HAS_EXECUTION_HEADER_FILE], [1], [Define if C++17 and <execution> header file are supported])
+else
+ AC_MSG_NOTICE([Could not support parallel sort so defaulting back to C++$DEFAULT_CXX_STANDARD])
+ CXX_STANDARD=$DEFAULT_CXX_STANDARD
+fi
dnl
dnl check if the c++ compiler has support __attribute__((visibility("hidden")))
@@ -552,6 +598,27 @@ AC_SUBST(LIBXML2_VERSION)
AC_SUBST(XML_LIBS)
AC_SUBST(XML_CFLAGS)
+dnl Check for dependency: tbb.
+HAS_PARALLEL_SORT_SUPPORT=no
+if test x$HAS_EXECUTION_HEADER_FILE = xyes; then
+ TBB_VERSION=2018.2
+
+ AC_MSG_NOTICE([using PKG_CONFIG_PATH=$PKG_CONFIG_PATH to check for tbb]);
+ FOUND_TBB=no
+ PKG_CHECK_MODULES(TBB, tbb >= $TBB_VERSION, FOUND_TBB=yes, FOUND_TBB=no)
+ if test x$FOUND_TBB = xyes; then
+ AC_DEFINE([HAS_PARALLEL_SORT_SUPPORT], 1,
+ [Defined if the system has parallel sort support])
+ AC_SUBST(TBB_VERSION)
+ AC_SUBST(TBB_LIBS)
+ AC_SUBST(TBB_CFLAGS)
+ AC_MSG_NOTICE([found libtbb, enabled support for parallel sort \o/])
+ HAS_PARALLEL_SORT_SUPPORT=yes
+ else
+ AC_MSG_NOTICE([no libtbb found, disabled support for parallel sort])
+ fi
+fi
+
dnl Check for dependency: xxhash
XXHASH_VERSION=0.8.0
PKG_CHECK_MODULES(XXHASH, libxxhash >= $XXHASH_VERSION)
@@ -956,7 +1023,7 @@ AM_CONDITIONAL(ENABLE_RUNNING_TESTS_WITH_PY3, test x$RUN_TESTS_WITH_PY3 = xyes)
AM_CONDITIONAL(ENABLE_PYTHON3_INTERPRETER, test x$PYTHON3_INTERPRETER != xno)
AC_SUBST(PYTHON)
-DEPS_CPPFLAGS="$XML_CFLAGS $XXHASH_CFLAGS $ELF_CFLAGS $DW_CFLAGS $LZMA_CFLAGS"
+DEPS_CPPFLAGS="$TBB_CFLAGS $XML_CFLAGS $XXHASH_CFLAGS $ELF_CFLAGS $DW_CFLAGS $LZMA_CFLAGS"
AC_SUBST(DEPS_CPPFLAGS)
dnl Check for the presence of doxygen program
@@ -1075,7 +1142,7 @@ fi
MT_LIBS=-latomic
dnl Set the list of libraries libabigail depends on
-DEPS_LIBS="$XML_LIBS $CTF_LIBS $BPF_LIBS $LZMA_LIBS $MT_LIBS"
+DEPS_LIBS="$TBB_LIBS $XML_LIBS $CTF_LIBS $BPF_LIBS $LZMA_LIBS $MT_LIBS"
if test x$ENABLE_INLINED_XXHASH = xno; then
DEPS_LIBS="$DEPS_LIBS $XXHASH_LIBS"
fi
@@ -1085,7 +1152,7 @@ AC_SUBST(DEPS_LIBS)
if test x$ABIGAIL_DEVEL != x; then
CFLAGS="-g -Og -Wall -Wextra -Werror -D_FORTIFY_SOURCE=2"
- CXXFLAGS="-g -Og -Wall -Wextra -Werror -D_FORTIFY_SOURCE=2 -D_GLIBCXX_DEBUG"
+ CXXFLAGS="-std=c++$CXX_STANDARD -g -Og -Wall -Wextra -Werror -D_FORTIFY_SOURCE=2 -D_GLIBCXX_DEBUG"
fi
if test x$ABIGAIL_DEBUG != x; then
@@ -1124,6 +1191,8 @@ if test x$ENABLE_INLINED_XXHASH = xyes; then
CXXFLAGS="$CXXFLAGS -DXXH_INLINE_ALL=1"
fi
+CXXFLAGS="$CXXFLAGS -std=c++$CXX_STANDARD"
+
dnl Set a few Automake conditionals
AM_CONDITIONAL([ENABLE_THREAD_SANITIZER],[test "x$ENABLE_TSAN" = "xyes"])
@@ -1131,9 +1200,6 @@ AM_CONDITIONAL([CTF_READER],[test "x$ENABLE_CTF" = "xyes"])
AM_CONDITIONAL([BTF_READER],[test "x$ENABLE_BTF" = "xyes"])
AM_CONDITIONAL([ENABLE_LIBABIGAIL_MULTITHREADING],[test "x$ENABLE_MULTITHREADING" = "xyes"])
-dnl Set the level of C++ standard we use.
-CXXFLAGS="$CXXFLAGS -std=$CXX_STANDARD"
-
use_prefixed_includedir=""
if test x$prefix != x; then
use_prefixed_includedir=$prefix
@@ -1785,14 +1851,16 @@ AC_MSG_NOTICE([
ELF_CFLAGS : ${ELF_CFLAGS}
DW_LIBS : ${DW_LIBS}
DW_CFLAGS : ${DW_CFLAGS}
- XML_LIBS $ ${XML_LIBS}
- XML_CFLAGS $ ${XML_CFLAGS}
- DEPS_LIBS $ ${DEPS_LIBS}
+ XML_LIBS : ${XML_LIBS}
+ XML_CFLAGS : ${XML_CFLAGS}
+ DEPS_LIBS : ${DEPS_LIBS}
+ DEPS_CPPFLAGS : ${DEPS_CPPFLAGS}
Python : ${PYTHON}
OPTIONAL FEATURES:
- C++ standard level : ${CXX_STANDARD}
+ C++ standard level : C++${CXX_STANDARD}
Enable multithreading support : ${ENABLE_MULTITHREADING}
+ Enable parallel sort : ${HAS_PARALLEL_SORT_SUPPORT}
Enable inlined-only xxhash library : ${ENABLE_INLINED_XXHASH}
Enable rpm support in abipkgdiff : ${ENABLE_RPM}
Enable rpm/zstd in abipkgdiff testing : ${ENABLE_RPM_ZSTD}
diff --git a/src/abg-ir-priv.h b/src/abg-ir-priv.h
index ed453c58..641ac27d 100644
--- a/src/abg-ir-priv.h
+++ b/src/abg-ir-priv.h
@@ -12,6 +12,7 @@
#ifndef __ABG_IR_PRIV_H__
#define __ABG_IR_PRIV_H__
+#include "config.h"
#include <algorithm>
#include <iostream>
@@ -19,6 +20,9 @@
#include <sstream>
#include <mutex>
#include <atomic>
+#ifdef HAS_EXECUTION_HEADER_FILE
+#include <execution>
+#endif
#include <memory>
#include "abg-hash.h"
@@ -1708,6 +1712,55 @@ canonicalize(type_base_sptr type,
type_base_sptr
hash_and_canonicalize_type(type_base_sptr t);
+/// Sort types.
+///
+///
+/// Depending on the number of types and on the presence of
+/// multithreading support, use C++17 parallel sorting or not.
+///
+/// @param begin an iterator pointing to the beginning of the sequence
+/// of types to sort.
+///
+/// @param end an iterator pointing to the end of the sequence of
+/// types to sort.
+///
+/// @param comp the comparison functor to use for sorting.
+///
+/// @param do_log emit leg messges if set to true.
+///
+/// @tparm IteratorType the iterator type to use for @p begin @p end.
+///
+/// @tparm SortingFunctorType the sorting functor to use.
+template <typename IteratorType, typename SortingFunctorType>
+void
+sort_types(IteratorType begin,
+ IteratorType end,
+ SortingFunctorType comp,
+ bool do_log = false)
+{
+ auto d = std::distance(begin, end);
+ if (do_log)
+ std::cerr << "number of types to canonicalize: " << d << std::endl;
+#if HAS_PARALLEL_SORT_SUPPORT
+ if (d > 1200000)
+ {
+ if (do_log)
+ std::cerr << "using sort(std::execution::par, ...)\n";
+ std::sort(std::execution::par, begin, end, comp);
+ }
+ else
+ {
+ if (do_log)
+ std::cerr << "using sort(std::execution::seq, ...)\n";
+ std::sort(std::execution::par, begin, end, comp);
+ }
+#else
+ if (do_log)
+ std::cerr << "using sort(begin, end, comp)\n";
+ std::sort(begin, end, comp);
+#endif
+}
+
/// Sort types before hashing (and then canonicalizing) them.
///
/// @param begin an iterator pointing to the beginning of the sequence
@@ -1716,14 +1769,17 @@ hash_and_canonicalize_type(type_base_sptr t);
/// @param end an iterator pointing to the end of the sequence of
/// types to sort.
///
+/// @param do_log emit leg messges if set to true.
+///
/// @tparm IteratorType the iterator type to use for @p begin @p end.
template <typename IteratorType>
void
sort_types_for_hash_computing_and_c14n(IteratorType begin,
- IteratorType end)
+ IteratorType end,
+ bool do_log = false)
{
sort_for_hash_functor comp;
- return std::sort(begin, end, comp);
+ return sort_types(begin, end, comp, do_log);
}
void
@@ -2033,7 +2089,7 @@ hash_and_canonicalize_types(SequenceType &types,
tmr.start();
}
- sort_types_for_hash_computing_and_c14n(types.begin(), types.end());
+ sort_types_for_hash_computing_and_c14n(types.begin(), types.end(), do_log);
if (do_log)
{
diff --git a/src/abg-ir.cc b/src/abg-ir.cc
index 2d300ca1..7828267b 100644
--- a/src/abg-ir.cc
+++ b/src/abg-ir.cc
@@ -1633,7 +1633,9 @@ type_maps::get_types_sorted() const
priv_->sorted_types_.push_back(t);
type_topo_comp comp;
- sort(priv_->sorted_types_.begin(), priv_->sorted_types_.end(), comp);
+ sort_types(priv_->sorted_types_.begin(),
+ priv_->sorted_types_.end(),
+ comp);
}
return priv_->sorted_types_;
diff --git a/src/abg-writer.cc b/src/abg-writer.cc
index 7b82eeb9..b8828c8a 100644
--- a/src/abg-writer.cc
+++ b/src/abg-writer.cc
@@ -779,7 +779,7 @@ public:
++i)
sorted.push_back(const_cast<type_base*>(*i));
type_topo_comp comp;
- sort(sorted.begin(), sorted.end(), comp);
+ abigail::ir::sort_types(sorted.begin(), sorted.end(), comp);
}
/// Sort the content of a map of type pointers into a vector.
@@ -798,7 +798,7 @@ public:
for (auto& type : types)
sorted.push_back(type);
type_topo_comp comp;
- sort(sorted.begin(), sorted.end(), comp);
+ abigail::ir::sort_types(sorted.begin(), sorted.end(), comp);
}
/// Sort the content of a map of type pointers into a vector.
@@ -819,7 +819,7 @@ public:
++i)
sorted.push_back(type_base_sptr(i->second));
type_topo_comp comp;
- sort(sorted.begin(), sorted.end(), comp);
+ abigail::ir::sort_types(sorted.begin(), sorted.end(), comp);
}
/// Sort the content of a vector of function types into a vector of
@@ -841,7 +841,7 @@ public:
++i)
sorted.push_back(*i);
type_topo_comp comp;
- sort(sorted.begin(), sorted.end(), comp);
+ abigail::ir::sort_types(sorted.begin(), sorted.end(), comp);
}
/// Flag a type as having been written out to the XML output.
diff --git a/tsan-suppression.txt b/tsan-suppression.txt
index bb379e5e..d04d1b3e 100644
--- a/tsan-suppression.txt
+++ b/tsan-suppression.txt
@@ -1,12 +1,26 @@
-# false positive lock-order-inversion report
-# probably due to the fact that thread sanitizer doesn't support
-# recursive mutexes
-# deadlock:^abigail::ir::add_decl_to_scope
-# deadlock:^abigail::dwarf::reader::associate_die_to_decl
-# deadlock:^abigail::ir::class_decl::traverse
-# deadlock:^abigail::ir::elf_symbol::get_name
-# deadlock:^abigail::ir::scope_decl::add_member_decl
-# deadlock:^abigail::ir::get_class_or_union_flat_representation
-# deadlock:^abigail::abixml::build_class_decl_if_not_suppressed
-# deadlock:^build_class_decl_if_not_suppressed
+# This removes false positive data race report from thread sanitizer
+# when using TBB indirectly from the parallel version of std::sort.
+# The parallel std::sort, is called from abigail::ir::sort_types in a
+# sequential manner, so there is almost no chance to see data races
+# there, unless the comparison functor used by the sort is not thread
+# safe. But I doubt it because the warnings issued by Thread
+# Sanitizer don't argue in that direction.
+# Maybe compiling TBB with Thread Sanitizer support could remove those
+# false positives ... but for now, we need these suppression.
+# race:^rml::internal::MemoryPool::getTLS
+# race:^tbb::detail::r1::__TBB_InitOnce::remove_ref
+# race:^tbb::detail::r1::affinity_helper::protect_affinity_mask
+# race:^tbb::detail::r1::arena::create
+# race:^tbb::detail::r1::market::unregister_and_destroy_client
+# race:^tbb::detail::r1::rml::private_server::wake_some
+# race:^tbb::detail::r1::thread_dispatcher::process
+# race:^memmove
+# race:^memcmp
+
+race:^__pstl::__tbb_backend::*
+race:^rml::internal::MemoryPool::*
+race:^tbb::detail::d1::*
+race:^tbb::detail::r1::*
+race:operator delete[]
+race:memcmp
--
2.55.0
More information about the Libabigail
mailing list