tp: filter for globs inside trace processor
This removes the overhead of passing all the strings to SQLite and
getting it to filter.
In the future, we can optimize this further by improving the glob
matching algorithm
Bug: 220373202
Change-Id: I29072d09898ab9b3ab5de388d474eaa26eab03ea
diff --git a/Android.bp b/Android.bp
index 03cd439..0793e08 100644
--- a/Android.bp
+++ b/Android.bp
@@ -7936,6 +7936,7 @@
name: "perfetto_src_trace_processor_db_db",
srcs: [
"src/trace_processor/db/column.cc",
+ "src/trace_processor/db/compare.cc",
"src/trace_processor/db/table.cc",
],
}
diff --git a/BUILD b/BUILD
index 6c19eb1..00a2a64 100644
--- a/BUILD
+++ b/BUILD
@@ -955,6 +955,7 @@
srcs = [
"src/trace_processor/db/column.cc",
"src/trace_processor/db/column.h",
+ "src/trace_processor/db/compare.cc",
"src/trace_processor/db/compare.h",
"src/trace_processor/db/table.cc",
"src/trace_processor/db/table.h",
diff --git a/gn/BUILD.gn b/gn/BUILD.gn
index f404832..946982f 100644
--- a/gn/BUILD.gn
+++ b/gn/BUILD.gn
@@ -80,6 +80,7 @@
"PERFETTO_VERSION_GEN=$enable_perfetto_version_gen",
"PERFETTO_TP_PERCENTILE=$enable_perfetto_trace_processor_percentile",
"PERFETTO_TP_LINENOISE=$enable_perfetto_trace_processor_linenoise",
+ "PERFETTO_TP_SQLITE=$enable_perfetto_trace_processor_sqlite",
"PERFETTO_TP_HTTPD=$enable_perfetto_trace_processor_httpd",
"PERFETTO_TP_JSON=$enable_perfetto_trace_processor_json",
"PERFETTO_LOCAL_SYMBOLIZER=$perfetto_local_symbolizer",
@@ -104,7 +105,8 @@
# All targets should depend on this target to inherit the right flags and
# include directories.
group("default_deps") {
- visibility = [ "../*" ] # Prevent chromium targets from depending on this (breaks component).
+ visibility = [ "../*" ] # Prevent chromium targets from depending on this
+ # (breaks component).
public_configs = [ ":default_config" ]
deps = [ ":gen_buildflags" ]
if (perfetto_build_standalone) {
@@ -124,7 +126,8 @@
# embedders that depend on perfetto (e.g. chrome). :public_config (see below) is
# used for that.
config("default_config") {
- visibility = [ "../*" ] # Prevent chromium targets from depending on this (breaks component).
+ visibility = [ "../*" ] # Prevent chromium targets from depending on this
+ # (breaks component).
configs = [ ":public_config" ]
defines = [ "PERFETTO_IMPLEMENTATION" ]
include_dirs = [
diff --git a/include/perfetto/base/build_configs/android_tree/perfetto_build_flags.h b/include/perfetto/base/build_configs/android_tree/perfetto_build_flags.h
index a02f467..6a17d04 100644
--- a/include/perfetto/base/build_configs/android_tree/perfetto_build_flags.h
+++ b/include/perfetto/base/build_configs/android_tree/perfetto_build_flags.h
@@ -36,6 +36,7 @@
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_VERSION_GEN() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_PERCENTILE() (0)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_LINENOISE() (0)
+#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_SQLITE() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_HTTPD() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_JSON() (0)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_LOCAL_SYMBOLIZER() (PERFETTO_BUILDFLAG_DEFINE_PERFETTO_OS_LINUX() || PERFETTO_BUILDFLAG_DEFINE_PERFETTO_OS_MAC() ||PERFETTO_BUILDFLAG_DEFINE_PERFETTO_OS_WIN())
diff --git a/include/perfetto/base/build_configs/bazel/perfetto_build_flags.h b/include/perfetto/base/build_configs/bazel/perfetto_build_flags.h
index 531445c..dde8b54 100644
--- a/include/perfetto/base/build_configs/bazel/perfetto_build_flags.h
+++ b/include/perfetto/base/build_configs/bazel/perfetto_build_flags.h
@@ -36,6 +36,7 @@
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_VERSION_GEN() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_PERCENTILE() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_LINENOISE() (1)
+#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_SQLITE() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_HTTPD() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_TP_JSON() (1)
#define PERFETTO_BUILDFLAG_DEFINE_PERFETTO_LOCAL_SYMBOLIZER() (PERFETTO_BUILDFLAG_DEFINE_PERFETTO_OS_LINUX() || PERFETTO_BUILDFLAG_DEFINE_PERFETTO_OS_MAC() ||PERFETTO_BUILDFLAG_DEFINE_PERFETTO_OS_WIN())
diff --git a/src/trace_processor/db/BUILD.gn b/src/trace_processor/db/BUILD.gn
index ebbd478..285af7c 100644
--- a/src/trace_processor/db/BUILD.gn
+++ b/src/trace_processor/db/BUILD.gn
@@ -18,6 +18,7 @@
sources = [
"column.cc",
"column.h",
+ "compare.cc",
"compare.h",
"table.cc",
"table.h",
@@ -31,6 +32,10 @@
"../../../include/perfetto/trace_processor",
"../containers",
]
+
+ if (enable_perfetto_trace_processor_sqlite) {
+ deps += [ "../../../gn:sqlite" ]
+ }
}
perfetto_unittest_source_set("unittests") {
@@ -44,6 +49,7 @@
"../../../gn:default_deps",
"../../../gn:gtest_and_gmock",
"../../base:base",
+ "../containers",
"../tables:tables",
]
}
diff --git a/src/trace_processor/db/column.cc b/src/trace_processor/db/column.cc
index 3339c82..d4a939b 100644
--- a/src/trace_processor/db/column.cc
+++ b/src/trace_processor/db/column.cc
@@ -160,7 +160,8 @@
rm->Intersect(RowMap());
}
return;
- } else if (op == FilterOp::kIsNotNull) {
+ }
+ if (op == FilterOp::kIsNotNull) {
PERFETTO_DCHECK(value.is_null());
if (is_nullable) {
row_map().FilterInto(rm, [this](uint32_t row) {
@@ -169,6 +170,10 @@
}
return;
}
+ if (op == FilterOp::kGlob) {
+ rm->Intersect(RowMap());
+ return;
+ }
if (value.type == SqlValue::Type::kDouble) {
double double_value = value.double_value;
@@ -275,6 +280,7 @@
break;
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
+ case FilterOp::kGlob:
PERFETTO_FATAL("Should be handled above");
}
}
@@ -290,7 +296,9 @@
return GetStringPoolStringAtIdx(row).data() == nullptr;
});
return;
- } else if (op == FilterOp::kIsNotNull) {
+ }
+
+ if (op == FilterOp::kIsNotNull) {
PERFETTO_DCHECK(value.is_null());
row_map().FilterInto(rm, [this](uint32_t row) {
return GetStringPoolStringAtIdx(row).data() != nullptr;
@@ -343,6 +351,12 @@
return v.data() != nullptr && compare::String(v, str_value) >= 0;
});
break;
+ case FilterOp::kGlob:
+ row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
+ auto v = GetStringPoolStringAtIdx(idx);
+ return v.data() != nullptr && compare::Glob(v, str_value) == 0;
+ });
+ break;
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
PERFETTO_FATAL("Should be handled above");
@@ -356,11 +370,18 @@
PERFETTO_DCHECK(value.is_null());
rm->Intersect(RowMap());
return;
- } else if (op == FilterOp::kIsNotNull) {
+ }
+
+ if (op == FilterOp::kIsNotNull) {
PERFETTO_DCHECK(value.is_null());
return;
}
+ if (op == FilterOp::kGlob) {
+ rm->Intersect(RowMap());
+ return;
+ }
+
if (value.type != SqlValue::Type::kLong) {
rm->Intersect(RowMap());
return;
@@ -400,6 +421,7 @@
break;
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
+ case FilterOp::kGlob:
PERFETTO_FATAL("Should be handled above");
}
}
diff --git a/src/trace_processor/db/column.h b/src/trace_processor/db/column.h
index ba0a981..42fda38 100644
--- a/src/trace_processor/db/column.h
+++ b/src/trace_processor/db/column.h
@@ -22,6 +22,7 @@
#include "perfetto/base/logging.h"
#include "perfetto/ext/base/optional.h"
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/null_term_string_view.h"
#include "src/trace_processor/containers/nullable_vector.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/containers/string_pool.h"
@@ -54,6 +55,7 @@
kLe,
kIsNull,
kIsNotNull,
+ kGlob,
};
// Represents a constraint on a column.
@@ -391,6 +393,10 @@
Constraint is_null() const {
return Constraint{col_idx_in_table_, FilterOp::kIsNull, SqlValue()};
}
+ Constraint glob(const char* value) const {
+ return Constraint{col_idx_in_table_, FilterOp::kGlob,
+ SqlValue::String(value)};
+ }
// Returns an Order for each Order type for this Column.
Order ascending() const { return Order{col_idx_in_table_, false}; }
@@ -533,9 +539,10 @@
case FilterOp::kNe:
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
- break;
+ case FilterOp::kGlob:
+ return false;
}
- return false;
+ PERFETTO_FATAL("For GCC");
}
// Slow path filter method which will perform a full table scan.
diff --git a/src/trace_processor/db/compare.cc b/src/trace_processor/db/compare.cc
new file mode 100644
index 0000000..982f3c2
--- /dev/null
+++ b/src/trace_processor/db/compare.cc
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/db/compare.h"
+
+#include "perfetto/base/build_config.h"
+#include "perfetto/base/compiler.h"
+
+#if PERFETTO_BUILDFLAG(PERFETTO_TP_SQLITE)
+#include <sqlite3.h>
+#endif
+
+namespace perfetto {
+namespace trace_processor {
+namespace compare {
+
+int Glob(NullTermStringView value, NullTermStringView pattern) {
+#if PERFETTO_BUILDFLAG(PERFETTO_TP_SQLITE)
+ return sqlite3_strglob(pattern.c_str(), value.c_str());
+#else
+ if (value == pattern)
+ return 0;
+
+ PERFETTO_FATAL("Glob not supported when SQLite not available");
+#endif
+}
+
+} // namespace compare
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/db/compare.h b/src/trace_processor/db/compare.h
index 0eb89b1..1d96407 100644
--- a/src/trace_processor/db/compare.h
+++ b/src/trace_processor/db/compare.h
@@ -17,12 +17,13 @@
#ifndef SRC_TRACE_PROCESSOR_DB_COMPARE_H_
#define SRC_TRACE_PROCESSOR_DB_COMPARE_H_
-#include <algorithm>
#include <stdint.h>
+#include <algorithm>
#include "perfetto/ext/base/optional.h"
#include "perfetto/ext/base/string_view.h"
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/null_term_string_view.h"
namespace perfetto {
namespace trace_processor {
@@ -98,6 +99,13 @@
return Bytes(a.data(), a.size(), b.data(), b.size());
}
+// Compares two number values by glob matching |pattern| within |value|;
+// returns:
+// * 0 if pattern matches value
+// * !0 otherwise.
+// This code matches the behaviour of sqlite3_strglob.
+int Glob(NullTermStringView value, NullTermStringView pattern);
+
// Compares two nullable numeric values; returns:
// * 0 if both a and b are null
// * <0 if a is null and b is non null
diff --git a/src/trace_processor/db/compare_unittest.cc b/src/trace_processor/db/compare_unittest.cc
index 190fb9a..2c6d7fc 100644
--- a/src/trace_processor/db/compare_unittest.cc
+++ b/src/trace_processor/db/compare_unittest.cc
@@ -15,6 +15,7 @@
*/
#include "src/trace_processor/db/compare.h"
+#include "src/trace_processor/containers/null_term_string_view.h"
#include "test/gtest_and_gmock.h"
namespace perfetto {
@@ -75,6 +76,21 @@
ASSERT_EQ(compare::SqlValue(aa, SqlValue::String("aa")), 0);
}
+TEST(CompareTest, Glob) {
+ NullTermStringView value = "foobar";
+ NullTermStringView p1 = "foo*";
+ NullTermStringView p2 = "*bar";
+ NullTermStringView p3 = "[f][o][a-z]ba*";
+ NullTermStringView p4 = "?[o][a-z]ba*";
+ NullTermStringView p5 = "[g-z][o][a-z]ba*";
+
+ ASSERT_EQ(compare::Glob(value, p1), 0);
+ ASSERT_EQ(compare::Glob(value, p2), 0);
+ ASSERT_EQ(compare::Glob(value, p3), 0);
+ ASSERT_EQ(compare::Glob(value, p4), 0);
+ ASSERT_NE(compare::Glob(value, p5), 0);
+}
+
} // namespace
} // namespace trace_processor
} // namespace perfetto
diff --git a/src/trace_processor/db/typed_column.h b/src/trace_processor/db/typed_column.h
index d286834..907abe4 100644
--- a/src/trace_processor/db/typed_column.h
+++ b/src/trace_processor/db/typed_column.h
@@ -133,10 +133,8 @@
if (column->IsColumnType<serialized_type>() &&
(column->IsNullable() == TH::is_optional) && !column->IsId()) {
return reinterpret_cast<const TypedColumn<T>*>(column);
- } else {
- PERFETTO_FATAL("Unsafe to convert Column TypedColumn (%s)",
- column->name());
}
+ PERFETTO_FATAL("Unsafe to convert Column TypedColumn (%s)", column->name());
}
private:
diff --git a/src/trace_processor/sqlite/db_sqlite_table.cc b/src/trace_processor/sqlite/db_sqlite_table.cc
index 0fc3162..99668aa 100644
--- a/src/trace_processor/sqlite/db_sqlite_table.cc
+++ b/src/trace_processor/sqlite/db_sqlite_table.cc
@@ -47,8 +47,9 @@
return FilterOp::kIsNull;
case SQLITE_INDEX_CONSTRAINT_ISNOTNULL:
return FilterOp::kIsNotNull;
- case SQLITE_INDEX_CONSTRAINT_LIKE:
case SQLITE_INDEX_CONSTRAINT_GLOB:
+ return FilterOp::kGlob;
+ case SQLITE_INDEX_CONSTRAINT_LIKE:
return base::nullopt;
#if SQLITE_VERSION_NUMBER >= 3038000
// LIMIT and OFFSET constraints were introduced in 3.38 but we
@@ -236,6 +237,10 @@
if (a_col.is_sorted && !b_col.is_sorted)
return true;
+ // Always prefer constraints which can filter to those we can't.
+ if (SqliteOpToFilterOp(a.op) && !SqliteOpToFilterOp(b.op))
+ return true;
+
// TODO(lalitm): introduce more orderings here based on empirical data.
return false;
});
@@ -512,6 +517,9 @@
case FilterOp::kIsNotNull:
writer.AppendString("IS NOT");
break;
+ case FilterOp::kGlob:
+ writer.AppendString("GLOB");
+ break;
}
writer.AppendChar(' ');
diff --git a/src/trace_processor/tables/BUILD.gn b/src/trace_processor/tables/BUILD.gn
index 66f0cfa..2bffb84 100644
--- a/src/trace_processor/tables/BUILD.gn
+++ b/src/trace_processor/tables/BUILD.gn
@@ -41,6 +41,7 @@
":tables",
"../../../gn:default_deps",
"../../../gn:gtest_and_gmock",
+ "../containers",
]
}
diff --git a/src/trace_processor/tables/macros_unittest.cc b/src/trace_processor/tables/macros_unittest.cc
index c9dd4b4..9e72244 100644
--- a/src/trace_processor/tables/macros_unittest.cc
+++ b/src/trace_processor/tables/macros_unittest.cc
@@ -16,6 +16,7 @@
#include "src/trace_processor/tables/macros.h"
+#include "src/trace_processor/containers/string_pool.h"
#include "test/gtest_and_gmock.h"
namespace perfetto {
@@ -406,6 +407,60 @@
ASSERT_STREQ(end_state->Get(1).string_value, "D");
}
+TEST_F(TableMacrosUnittest, Glob) {
+ cpu_slice_.Insert({});
+
+ TestCpuSliceTable::Row row;
+ row.end_state = pool_.InternString("Running");
+ cpu_slice_.Insert(row);
+
+ row.end_state = pool_.InternString("Disk");
+ cpu_slice_.Insert(row);
+
+ cpu_slice_.Insert({});
+
+ {
+ Table out = cpu_slice_.Filter({cpu_slice_.end_state().glob("?unning")});
+ const auto& end_state =
+ out.GetTypedColumnByName<StringPool::Id>("end_state");
+ ASSERT_EQ(out.row_count(), 1u);
+ ASSERT_EQ(end_state.GetString(0), "Running");
+ }
+
+ {
+ Table out = cpu_slice_.Filter({cpu_slice_.end_state().glob("[D]isk")});
+ const auto& end_state =
+ out.GetTypedColumnByName<StringPool::Id>("end_state");
+ ASSERT_EQ(out.row_count(), 1u);
+ ASSERT_EQ(end_state.GetString(0), "Disk");
+ }
+
+ {
+ Table out = cpu_slice_.Filter({cpu_slice_.end_state().glob("[A-Z]isk")});
+ const auto& end_state =
+ out.GetTypedColumnByName<StringPool::Id>("end_state");
+ ASSERT_EQ(out.row_count(), 1u);
+ ASSERT_EQ(end_state.GetString(0), "Disk");
+ }
+
+ {
+ Table out = cpu_slice_.Filter({cpu_slice_.end_state().glob("Run*")});
+ const auto& end_state =
+ out.GetTypedColumnByName<StringPool::Id>("end_state");
+ ASSERT_EQ(out.row_count(), 1u);
+ ASSERT_EQ(end_state.GetString(0), "Running");
+ }
+
+ {
+ Table out = cpu_slice_.Filter({cpu_slice_.end_state().glob("*")});
+ const auto& end_state =
+ out.GetTypedColumnByName<StringPool::Id>("end_state");
+ ASSERT_EQ(out.row_count(), 2u);
+ ASSERT_EQ(end_state.GetString(0), "Running");
+ ASSERT_EQ(end_state.GetString(1), "Disk");
+ }
+}
+
TEST_F(TableMacrosUnittest, FilterIdThenOther) {
TestCpuSliceTable::Row row;
row.cpu = 1;
