Merge "Add volatile qualifier to AnnotateBenignRaceSized()'s address argument." into main
diff --git a/src/trace_processor/db/BUILD.gn b/src/trace_processor/db/BUILD.gn
index 2cc509f..604929d 100644
--- a/src/trace_processor/db/BUILD.gn
+++ b/src/trace_processor/db/BUILD.gn
@@ -70,6 +70,7 @@
"../tables",
"../views",
"storage",
+ "storage:fake_storage",
]
}
diff --git a/src/trace_processor/db/query_executor_unittest.cc b/src/trace_processor/db/query_executor_unittest.cc
index a33b128..e5022c0 100644
--- a/src/trace_processor/db/query_executor_unittest.cc
+++ b/src/trace_processor/db/query_executor_unittest.cc
@@ -17,11 +17,13 @@
#include "src/trace_processor/db/query_executor.h"
#include "src/trace_processor/db/storage/arrangement_storage.h"
+#include "src/trace_processor/db/storage/fake_storage.h"
#include "src/trace_processor/db/storage/id_storage.h"
#include "src/trace_processor/db/storage/null_storage.h"
#include "src/trace_processor/db/storage/numeric_storage.h"
#include "src/trace_processor/db/storage/selector_storage.h"
#include "src/trace_processor/db/storage/set_id_storage.h"
+#include "src/trace_processor/db/storage/storage.h"
#include "src/trace_processor/db/storage/string_storage.h"
#include "test/gtest_and_gmock.h"
@@ -221,6 +223,34 @@
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(0u, 4u));
}
+TEST(QueryExecutor, ArrangementOverlaySubsetInputRange) {
+ std::unique_ptr<storage::Storage> fake =
+ storage::FakeStorage::SearchSubset(5u, RowMap::Range(2u, 4u));
+
+ std::vector<uint32_t> arrangement{4, 1, 2, 2, 3};
+ storage::ArrangementStorage storage(std::move(fake), &arrangement);
+
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(0u)};
+ RowMap rm(1, 3);
+ QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+
+ ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u));
+}
+
+TEST(QueryExecutor, ArrangementOverlaySubsetInputBitvector) {
+ std::unique_ptr<storage::Storage> fake =
+ storage::FakeStorage::SearchSubset(5u, BitVector({0, 0, 1, 1, 0}));
+
+ std::vector<uint32_t> arrangement{4, 1, 2, 2, 3};
+ storage::ArrangementStorage storage(std::move(fake), &arrangement);
+
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(0u)};
+ RowMap rm(1, 3);
+ QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+
+ ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u));
+}
+
TEST(QueryExecutor, ArrangementStorageIndex) {
std::vector<int64_t> storage_data(5);
std::iota(storage_data.begin(), storage_data.end(), 0);
@@ -354,7 +384,7 @@
storage::NullStorage storage(std::move(selector), &null_bv);
// Filter.
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(0)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
QueryExecutor exec({&storage}, 9);
RowMap res = exec.Filter({c});
@@ -378,7 +408,7 @@
storage::NullStorage storage(std::move(selector), &null_bv);
// Filter.
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(0)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
QueryExecutor exec({&storage}, 10);
RowMap res = exec.Filter({c});
diff --git a/src/trace_processor/db/storage/arrangement_storage.cc b/src/trace_processor/db/storage/arrangement_storage.cc
index 38e6f77..ee777f4 100644
--- a/src/trace_processor/db/storage/arrangement_storage.cc
+++ b/src/trace_processor/db/storage/arrangement_storage.cc
@@ -52,10 +52,10 @@
arrangement.begin() + static_cast<int32_t>(in.end));
auto storage_result = inner_->Search(op, sql_val, Range(*min_i, *max_i + 1));
- BitVector::Builder builder(static_cast<uint32_t>(arrangement.size()));
+ BitVector::Builder builder(in.end, in.start);
if (storage_result.IsRange()) {
Range storage_range = std::move(storage_result).TakeIfRange();
- for (uint32_t i = 0; i < arrangement.size(); ++i) {
+ for (uint32_t i = in.start; i < in.end; ++i) {
builder.Append(storage_range.Contains(arrangement[i]));
}
} else {
diff --git a/src/trace_processor/db/storage/fake_storage.cc b/src/trace_processor/db/storage/fake_storage.cc
index 37474d0..8d2550c 100644
--- a/src/trace_processor/db/storage/fake_storage.cc
+++ b/src/trace_processor/db/storage/fake_storage.cc
@@ -55,16 +55,13 @@
return RangeOrBitVector(RowMap::Range());
case kRange:
case kBitVector: {
- BitVector bv;
+ BitVector::Builder builder(indices_size);
for (uint32_t* it = indices; it != indices + indices_size; ++it) {
- if ((strategy_ == kRange && range_.Contains(*it)) ||
- (strategy_ == kBitVector && bit_vector_.IsSet(*it))) {
- bv.AppendTrue();
- } else {
- bv.AppendFalse();
- }
+ bool in_range = strategy_ == kRange && range_.Contains(*it);
+ bool in_bv = strategy_ == kBitVector && bit_vector_.IsSet(*it);
+ builder.Append(in_range || in_bv);
}
- return RangeOrBitVector(std::move(bv));
+ return RangeOrBitVector(std::move(builder).Build());
}
}
PERFETTO_FATAL("For GCC");
diff --git a/src/trace_processor/db/storage/id_storage.cc b/src/trace_processor/db/storage/id_storage.cc
index 53e85a8..0493f97 100644
--- a/src/trace_processor/db/storage/id_storage.cc
+++ b/src/trace_processor/db/storage/id_storage.cc
@@ -83,8 +83,9 @@
if (op == FilterOp::kNe) {
if (sql_val.AsLong() > std::numeric_limits<uint32_t>::max() ||
- sql_val.AsLong() < std::numeric_limits<uint32_t>::min())
- return RangeOrBitVector(Range(0, size_));
+ sql_val.AsLong() < std::numeric_limits<uint32_t>::min()) {
+ return RangeOrBitVector(range);
+ }
uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
BitVector ret(range.start, false);
diff --git a/src/trace_processor/db/storage/id_storage_unittest.cc b/src/trace_processor/db/storage/id_storage_unittest.cc
index 13229e3..57c148d 100644
--- a/src/trace_processor/db/storage/id_storage_unittest.cc
+++ b/src/trace_processor/db/storage/id_storage_unittest.cc
@@ -100,7 +100,7 @@
IdStorage storage(100);
Range r = storage.Search(FilterOp::kNe, SqlValue::Long(-1), Range(30, 70))
.TakeIfRange();
- ASSERT_EQ(r.size(), 100u);
+ ASSERT_EQ(r.size(), 40u);
}
TEST(IdStorageUnittest, Sort) {
diff --git a/src/trace_processor/db/storage/null_storage.cc b/src/trace_processor/db/storage/null_storage.cc
index 7c3920e..cac62d6 100644
--- a/src/trace_processor/db/storage/null_storage.cc
+++ b/src/trace_processor/db/storage/null_storage.cc
@@ -21,6 +21,7 @@
#include "protos/perfetto/trace_processor/serialization.pbzero.h"
#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/storage/types.h"
#include "src/trace_processor/tp_metatrace.h"
@@ -33,7 +34,10 @@
RangeOrBitVector ReconcileStorageResult(FilterOp op,
const BitVector& non_null,
- RangeOrBitVector storage_result) {
+ RangeOrBitVector storage_result,
+ Range in_range) {
+ PERFETTO_CHECK(in_range.end <= non_null.size());
+
// Reconcile the results of the Search operation with the non-null indices
// to ensure only those positions are set.
BitVector res;
@@ -42,23 +46,25 @@
if (range.size() > 0) {
res = non_null.IntersectRange(non_null.IndexOfNthSet(range.start),
non_null.IndexOfNthSet(range.end - 1) + 1);
+
+ // We should always have at least as many elements as the input range
+ // itself.
+ PERFETTO_CHECK(res.size() <= in_range.end);
}
} else {
res = non_null.Copy();
res.UpdateSetBits(std::move(storage_result).TakeIfBitVector());
}
- // Make sure that the reconciled result is *precisely* the size of non_null
- // vector. This is important as there are assumptions which require that
- // these sizes match exactly.
- // TODO(lalitm): consider relaxing this constraint down the line.
- PERFETTO_DCHECK(res.size() <= non_null.size());
- res.Resize(non_null.size());
+ // Ensure that |res| exactly matches the size which we need to return,
+ // padding with zeros or truncating if necessary.
+ res.Resize(in_range.end, false);
// For the IS NULL constraint, we also need to include all the null indices
// themselves.
if (PERFETTO_UNLIKELY(op == FilterOp::kIsNull)) {
- BitVector null = non_null.Copy();
+ BitVector null = non_null.IntersectRange(in_range.start, in_range.end);
+ null.Resize(in_range.end, false);
null.Not();
res.Or(null);
}
@@ -83,7 +89,8 @@
uint32_t start = non_null_->CountSetBits(in.start);
uint32_t end = non_null_->CountSetBits(in.end);
return ReconcileStorageResult(
- op, *non_null_, storage_->Search(op, sql_val, RowMap::Range(start, end)));
+ op, *non_null_, storage_->Search(op, sql_val, RowMap::Range(start, end)),
+ in);
}
RangeOrBitVector NullStorage::IndexSearch(FilterOp op,
@@ -93,21 +100,21 @@
bool sorted) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "NullStorage::IndexSearch");
- BitVector storage_non_null;
+ BitVector::Builder storage_non_null(indices_size);
std::vector<uint32_t> storage_iv;
storage_iv.reserve(indices_size);
for (uint32_t* it = indices; it != indices + indices_size; it++) {
- if (non_null_->IsSet(*it)) {
+ bool is_non_null = non_null_->IsSet(*it);
+ if (is_non_null) {
storage_iv.push_back(non_null_->CountSetBits(*it));
- storage_non_null.AppendTrue();
- } else {
- storage_non_null.AppendFalse();
}
+ storage_non_null.Append(is_non_null);
}
RangeOrBitVector range_or_bv =
storage_->IndexSearch(op, sql_val, storage_iv.data(),
static_cast<uint32_t>(storage_iv.size()), sorted);
- return ReconcileStorageResult(op, storage_non_null, std::move(range_or_bv));
+ return ReconcileStorageResult(op, std::move(storage_non_null).Build(),
+ std::move(range_or_bv), Range(0, indices_size));
}
void NullStorage::StableSort(uint32_t*, uint32_t) const {
diff --git a/src/trace_processor/db/storage/null_storage_unittest.cc b/src/trace_processor/db/storage/null_storage_unittest.cc
index a7404ab..daa235f 100644
--- a/src/trace_processor/db/storage/null_storage_unittest.cc
+++ b/src/trace_processor/db/storage/null_storage_unittest.cc
@@ -83,7 +83,7 @@
NullStorage storage(FakeStorage::SearchSubset(4u, BitVector{0, 1, 0, 1}),
&bv);
- auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
+ auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 8));
ASSERT_THAT(ToIndexVector(res), ElementsAre(2, 6));
}
@@ -92,7 +92,7 @@
NullStorage storage(FakeStorage::SearchSubset(4u, BitVector{0, 1, 0, 1}),
&bv);
- auto res = storage.Search(FilterOp::kIsNull, SqlValue(), Range(0, 11));
+ auto res = storage.Search(FilterOp::kIsNull, SqlValue(), Range(0, 8));
ASSERT_THAT(ToIndexVector(res), ElementsAre(0, 2, 3, 4, 6, 7));
}
diff --git a/src/trace_processor/db/storage/numeric_storage.cc b/src/trace_processor/db/storage/numeric_storage.cc
index 184b1e1..b7ecfa9 100644
--- a/src/trace_processor/db/storage/numeric_storage.cc
+++ b/src/trace_processor/db/storage/numeric_storage.cc
@@ -220,11 +220,10 @@
// range, and rather just `not` range returned with `equal` operation.
RowMap::Range r = BinarySearchIntrinsic(FilterOp::kEq, value, range);
BitVector bv(r.start, true);
- bv.Resize(r.end);
+ bv.Resize(r.end, false);
bv.Resize(range.end, true);
return RangeOrBitVector(std::move(bv));
}
-
return RangeOrBitVector(LinearSearchInternal(op, value, range));
}
@@ -252,10 +251,10 @@
RowMap::Range range) const {
std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
if (op == FilterOp::kIsNotNull)
- return BitVector(size(), true);
+ return BitVector(range.end, true);
if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return BitVector(size(), false);
+ return BitVector(range.end, false);
BitVector::Builder builder(range.end, range.start);
if (const auto* u32 = std::get_if<uint32_t>(&*val)) {
@@ -428,7 +427,7 @@
PERFETTO_FATAL("Invalid column type for NumericStorage");
}
numeric_storage_msg->set_values(static_cast<const uint8_t*>(data_),
- static_cast<size_t>(type_size * size_));
+ static_cast<size_t>(type_size) * size_);
}
} // namespace storage
diff --git a/src/trace_processor/db/storage/set_id_storage.cc b/src/trace_processor/db/storage/set_id_storage.cc
index 76c7982..8244ae0 100644
--- a/src/trace_processor/db/storage/set_id_storage.cc
+++ b/src/trace_processor/db/storage/set_id_storage.cc
@@ -79,9 +79,10 @@
// range, and rather just `not` range returned with `equal` operation.
RowMap::Range eq_range =
BinarySearchIntrinsic(FilterOp::kEq, sql_val, range);
- BitVector bv(eq_range.start, true);
- bv.Resize(eq_range.end);
- bv.Resize(std::min(range.end - 1, eq_range.end), true);
+ BitVector bv(range.start, false);
+ bv.Resize(eq_range.start, true);
+ bv.Resize(eq_range.end, false);
+ bv.Resize(range.end, true);
return RangeOrBitVector(std::move(bv));
}
return RangeOrBitVector(BinarySearchIntrinsic(op, sql_val, range));
diff --git a/src/trace_processor/db/storage/storage.h b/src/trace_processor/db/storage/storage.h
index 989423c..605329b 100644
--- a/src/trace_processor/db/storage/storage.h
+++ b/src/trace_processor/db/storage/storage.h
@@ -38,14 +38,37 @@
// Searches for elements which match |op| and |value| between |range.start|
// and |range.end|.
+ //
+ // Returns either a range or BitVector which indicate the positions in |range|
+ // which match the constraint. If a BitVector is returned, it will be
+ // *precisely* as large as |range.end|.
+ //
+ // Notes for implementors:
+ // * Implementations should ensure that the return value *only* includes
+ // positions in |range| as callers will expect this to be true and can
+ // optimize based on this.
+ // * Implementations should ensure that, if they return a BitVector, it is
+ // precisely of size |range.end|.
virtual RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const = 0;
// Searches for elements which match |op| and |value| at the positions given
- // by |indices| array.
- // If the order defined by |indices| makes storage sorted, |sorted| flag
- // should be set to true.
+ // by |indices| array. The |sorted| flag allows the caller to specify if the
+ // order defined by |indices| makes storage sorted; implementations can use
+ // this to optimize how they search the storage.
+ //
+ // Returns either a range of BitVector which indicate the positions in
+ // |indices| which match the constraint. If a BitVector is returned, it will
+ // be *precisely* as large as |indices_count|.
+ //
+ // Notes for callers:
+ // * Callers should note that the return value of this function corresponds
+ // to positions in |indices| *not* positions in the storage.
+ //
+ // Notes for implementors:
+ // * Implementations should ensure that, if they return a BitVector, it is
+ // precisely of size |indices_count|.
virtual RangeOrBitVector IndexSearch(FilterOp op,
SqlValue value,
uint32_t* indices,
diff --git a/src/trace_processor/db/storage/string_storage.cc b/src/trace_processor/db/storage/string_storage.cc
index 0ba5f00..d1d88b7 100644
--- a/src/trace_processor/db/storage/string_storage.cc
+++ b/src/trace_processor/db/storage/string_storage.cc
@@ -182,7 +182,7 @@
// a range, and rather just `not` range returned with `equal` operation.
RowMap::Range r = BinarySearchIntrinsic(FilterOp::kEq, value, range);
BitVector bv(r.start, true);
- bv.Resize(r.end);
+ bv.Resize(r.end, false);
bv.Resize(range.end, true);
return RangeOrBitVector(std::move(bv));
}
@@ -214,12 +214,12 @@
RowMap::Range range) const {
if (sql_val.is_null() &&
(op != FilterOp::kIsNotNull && op != FilterOp::kIsNull)) {
- return BitVector();
+ return BitVector(range.end, false);
}
if (sql_val.type != SqlValue::kString &&
(op == FilterOp::kGlob || op == FilterOp::kRegex)) {
- return BitVector();
+ return BitVector(range.end, false);
}
StringPool::Id val =
