src/trace_redaction/process_thread_timeline.cc - third_party/perfetto - Git at Google

 /*
  * Copyright (C) 2024 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_redaction/process_thread_timeline.h"

 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
 #include <optional>

 namespace perfetto::trace_redaction {
 namespace {
 // Limit the number of iterations to avoid an infinite loop. 10 is a generous
 // number of iterations.
 constexpr size_t kMaxSearchDepth = 10;

 bool OrderByPid(const ProcessThreadTimeline::Event& left,
                 const ProcessThreadTimeline::Event& right) {
   return left.pid() < right.pid();
 }

 }  // namespace

 void ProcessThreadTimeline::Append(const Event& event) {
   write_only_events_.push_back(event);
 }

 void ProcessThreadTimeline::Sort() {
   write_only_events_.sort(OrderByPid);

   // Copy all events that don't match adjacent events. This should reduce the
   // number of events because process trees may contain the same data
   // back-to-back.
   read_only_events_.reserve(write_only_events_.size());

   for (auto event : write_only_events_) {
     if (read_only_events_.empty() || event != read_only_events_.back()) {
       read_only_events_.push_back(event);
     }
   }

   // Events have been moved from the write-only list to the read-only vector.
   // The resources backing the write-only list can be release.
   write_only_events_.clear();
 }

 void ProcessThreadTimeline::Flatten() {
   // Union-find-like action to collapse the tree.
   for (auto& event : read_only_events_) {
     if (event.type() != Event::Type::kOpen) {
       continue;
     }

     auto event_with_package = Search(0, event.ts(), event.pid());

     if (event_with_package.has_value()) {
       event = Event::Open(event.ts(), event.pid(), event.ppid(),
                           event_with_package->uid());
     }
   }
 }

 void ProcessThreadTimeline::Reduce(uint64_t package_uid) {
   auto remove_open_events = [package_uid](const Event& event) {
     return event.uid() != package_uid && event.type() == Event::Type::kOpen;
   };

   read_only_events_.erase(
       std::remove_if(read_only_events_.begin(), read_only_events_.end(),
                      remove_open_events),
       read_only_events_.end());
 }

 ProcessThreadTimeline::Slice ProcessThreadTimeline::Search(uint64_t ts,
                                                            int32_t pid) const {
   Slice s;
   s.pid = pid;
   s.uid = 0;

   auto e = Search(0, ts, pid);
   if (e.has_value()) {
     s.uid = e->uid();
   }

   return s;
 }

 std::optional<ProcessThreadTimeline::Event>
 ProcessThreadTimeline::Search(size_t depth, uint64_t ts, int32_t pid) const {
   if (depth >= kMaxSearchDepth) {
     return std::nullopt;
   }

   auto event = FindPreviousEvent(ts, pid);

   if (!TestEvent(event)) {
     return event;
   }

   if (event->uid() != 0) {
     return event;
   }

   return Search(depth + 1, ts, event->ppid());
 }

 std::optional<size_t> ProcessThreadTimeline::GetDepth(uint64_t ts,
                                                       int32_t pid) const {
   return GetDepth(0, ts, pid);
 }

 std::optional<size_t> ProcessThreadTimeline::GetDepth(size_t depth,
                                                       uint64_t ts,
                                                       int32_t pid) const {
   if (depth >= kMaxSearchDepth) {
     return std::nullopt;
   }

   auto event = FindPreviousEvent(ts, pid);

   if (!TestEvent(event)) {
     return std::nullopt;
   }

   if (event->uid() != 0) {
     return depth;
   }

   return GetDepth(depth + 1, ts, event->ppid());
 }

 std::optional<ProcessThreadTimeline::Event>
 ProcessThreadTimeline::FindPreviousEvent(uint64_t ts, int32_t pid) const {
   Event fake = Event::Close(ts, pid);

   // Events are in ts-order within each pid-group. See Optimize(), Because each
   // group is small (the vast majority will have two events [start + event, no
   // reuse]).
   //
   // Find the first process event. Then perform a linear search. There won't be
   // many events per process.
   auto at = std::lower_bound(read_only_events_.begin(), read_only_events_.end(),
                              fake, OrderByPid);

   // `pid` was not found in `read_only_events_`.
   if (at == read_only_events_.end()) {
     return std::nullopt;
   }

   // "no best option".
   std::optional<Event> best;

   // Run through all events (related to this pid) and find the last event that
   // comes before ts. If the events were in order by time, the search could be
   // more efficient, but the gains are margin because:
   //
   // 1. The number of edge cases go up.
   //
   // 2. The code is harder to read.
   //
   // 3. The performance gains are minimal or non-existant because of the small
   //    number of events.
   for (; at != read_only_events_.end() && at->pid() == pid; ++at) {
     if (at->ts() > ts) {
       continue;  // Ignore events in the future.
     }

     // All ts values are positive. However, ts_at and ts_best are both less than
     // ts (see early condition), meaning they can be considered negative values.
     //
     //      at        best            ts
     //   <---+-----------+-------------+---->
     //      31          64            93
     //
     //      at        best            ts
     //   <---+-----------+-------------+---->
     //     -62         -29             0
     //
     // This means that the latest ts value under ts is the closest to ts.
     if (!best.has_value() || at->ts() > best->ts()) {
       best = *at;
     }
   }

   if (best.has_value() &&
       best->type() != ProcessThreadTimeline::Event::Type::kOpen) {
     return std::nullopt;
   }

   return best;
 }

 bool ProcessThreadTimeline::TestEvent(std::optional<Event> event) const {
   if (!event.has_value()) {
     return false;
   }

   // The thread/process was freed. It won't exist until a new open event.
   if (event->type() != Event::Type::kOpen) {
     return false;
   }

   // It is a rare case in production, but a common case in tests, the top-level
   // event will have no parent but will have the uid. So, to avoid make the
   // tests fragile and without taking on any risk, the uid should be checked
   // before the ppid.
   if (event->uid() != 0) {
     return true;
   }

   return event->ppid() != 0;
 }

 }  // namespace perfetto::trace_redaction
	/*
	* Copyright (C) 2024 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_redaction/process_thread_timeline.h"

	#include <algorithm>
	#include <cstddef>
	#include <cstdint>
	#include <optional>

	namespace perfetto::trace_redaction {
	namespace {
	// Limit the number of iterations to avoid an infinite loop. 10 is a generous
	// number of iterations.
	constexpr size_t kMaxSearchDepth = 10;

	bool OrderByPid(const ProcessThreadTimeline::Event& left,
	const ProcessThreadTimeline::Event& right) {
	return left.pid() < right.pid();
	}

	} // namespace

	void ProcessThreadTimeline::Append(const Event& event) {
	write_only_events_.push_back(event);
	}

	void ProcessThreadTimeline::Sort() {
	write_only_events_.sort(OrderByPid);

	// Copy all events that don't match adjacent events. This should reduce the
	// number of events because process trees may contain the same data
	// back-to-back.
	read_only_events_.reserve(write_only_events_.size());

	for (auto event : write_only_events_) {
	if (read_only_events_.empty() \|\| event != read_only_events_.back()) {
	read_only_events_.push_back(event);
	}
	}

	// Events have been moved from the write-only list to the read-only vector.
	// The resources backing the write-only list can be release.
	write_only_events_.clear();
	}

	void ProcessThreadTimeline::Flatten() {
	// Union-find-like action to collapse the tree.
	for (auto& event : read_only_events_) {
	if (event.type() != Event::Type::kOpen) {
	continue;
	}

	auto event_with_package = Search(0, event.ts(), event.pid());

	if (event_with_package.has_value()) {
	event = Event::Open(event.ts(), event.pid(), event.ppid(),
	event_with_package->uid());
	}
	}
	}

	void ProcessThreadTimeline::Reduce(uint64_t package_uid) {
	auto remove_open_events = [package_uid](const Event& event) {
	return event.uid() != package_uid && event.type() == Event::Type::kOpen;
	};

	read_only_events_.erase(
	std::remove_if(read_only_events_.begin(), read_only_events_.end(),
	remove_open_events),
	read_only_events_.end());
	}

	ProcessThreadTimeline::Slice ProcessThreadTimeline::Search(uint64_t ts,
	int32_t pid) const {
	Slice s;
	s.pid = pid;
	s.uid = 0;

	auto e = Search(0, ts, pid);
	if (e.has_value()) {
	s.uid = e->uid();
	}

	return s;
	}

	std::optional<ProcessThreadTimeline::Event>
	ProcessThreadTimeline::Search(size_t depth, uint64_t ts, int32_t pid) const {
	if (depth >= kMaxSearchDepth) {
	return std::nullopt;
	}

	auto event = FindPreviousEvent(ts, pid);

	if (!TestEvent(event)) {
	return event;
	}

	if (event->uid() != 0) {
	return event;
	}

	return Search(depth + 1, ts, event->ppid());
	}

	std::optional<size_t> ProcessThreadTimeline::GetDepth(uint64_t ts,
	int32_t pid) const {
	return GetDepth(0, ts, pid);
	}

	std::optional<size_t> ProcessThreadTimeline::GetDepth(size_t depth,
	uint64_t ts,
	int32_t pid) const {
	if (depth >= kMaxSearchDepth) {
	return std::nullopt;
	}

	auto event = FindPreviousEvent(ts, pid);

	if (!TestEvent(event)) {
	return std::nullopt;
	}

	if (event->uid() != 0) {
	return depth;
	}

	return GetDepth(depth + 1, ts, event->ppid());
	}

	std::optional<ProcessThreadTimeline::Event>
	ProcessThreadTimeline::FindPreviousEvent(uint64_t ts, int32_t pid) const {
	Event fake = Event::Close(ts, pid);

	// Events are in ts-order within each pid-group. See Optimize(), Because each
	// group is small (the vast majority will have two events [start + event, no
	// reuse]).
	//
	// Find the first process event. Then perform a linear search. There won't be
	// many events per process.
	auto at = std::lower_bound(read_only_events_.begin(), read_only_events_.end(),
	fake, OrderByPid);

	// `pid` was not found in `read_only_events_`.
	if (at == read_only_events_.end()) {
	return std::nullopt;
	}

	// "no best option".
	std::optional<Event> best;

	// Run through all events (related to this pid) and find the last event that
	// comes before ts. If the events were in order by time, the search could be
	// more efficient, but the gains are margin because:
	//
	// 1. The number of edge cases go up.
	//
	// 2. The code is harder to read.
	//
	// 3. The performance gains are minimal or non-existant because of the small
	// number of events.
	for (; at != read_only_events_.end() && at->pid() == pid; ++at) {
	if (at->ts() > ts) {
	continue; // Ignore events in the future.
	}

	// All ts values are positive. However, ts_at and ts_best are both less than
	// ts (see early condition), meaning they can be considered negative values.
	//
	// at best ts
	// <---+-----------+-------------+---->
	// 31 64 93
	//
	// at best ts
	// <---+-----------+-------------+---->
	// -62 -29 0
	//
	// This means that the latest ts value under ts is the closest to ts.
	if (!best.has_value() \|\| at->ts() > best->ts()) {
	best = *at;
	}
	}

	if (best.has_value() &&
	best->type() != ProcessThreadTimeline::Event::Type::kOpen) {
	return std::nullopt;
	}

	return best;
	}

	bool ProcessThreadTimeline::TestEvent(std::optional<Event> event) const {
	if (!event.has_value()) {
	return false;
	}

	// The thread/process was freed. It won't exist until a new open event.
	if (event->type() != Event::Type::kOpen) {
	return false;
	}

	// It is a rare case in production, but a common case in tests, the top-level
	// event will have no parent but will have the uid. So, to avoid make the
	// tests fragile and without taking on any risk, the uid should be checked
	// before the ppid.
	if (event->uid() != 0) {
	return true;
	}

	return event->ppid() != 0;
	}

	} // namespace perfetto::trace_redaction