Add IdAllocator class
It will be used by both SharedMemoryArbiter and tracing::ServiceImpl
to allocate IDs for, respectively, writer IDs and buffer IDs.
Test: perfetto_tests --gtest_filter=IdAllocatorTest.*
Bug: 70284518
Change-Id: Id7cb75fbc256f04515ef24531f8a23cffbfad781
diff --git a/Android.bp b/Android.bp
index 1e7ebef..9ef2dcf 100644
--- a/Android.bp
+++ b/Android.bp
@@ -382,6 +382,8 @@
"src/tracing/core/chunked_protobuf_input_stream_unittest.cc",
"src/tracing/core/data_source_config.cc",
"src/tracing/core/data_source_descriptor.cc",
+ "src/tracing/core/id_allocator.cc",
+ "src/tracing/core/id_allocator_unittest.cc",
"src/tracing/core/service_impl.cc",
"src/tracing/core/service_impl_unittest.cc",
"src/tracing/core/trace_config.cc",
diff --git a/src/tracing/BUILD.gn b/src/tracing/BUILD.gn
index fec501b..2cef20a 100644
--- a/src/tracing/BUILD.gn
+++ b/src/tracing/BUILD.gn
@@ -30,6 +30,8 @@
"core/chunked_protobuf_input_stream.h",
"core/data_source_config.cc",
"core/data_source_descriptor.cc",
+ "core/id_allocator.cc",
+ "core/id_allocator.h",
"core/service_impl.cc",
"core/service_impl.h",
"core/trace_config.cc",
@@ -76,9 +78,9 @@
"../base",
"../base:test_support",
]
-
sources = [
"core/chunked_protobuf_input_stream_unittest.cc",
+ "core/id_allocator_unittest.cc",
"core/service_impl_unittest.cc",
"core/trace_packet_unittest.cc",
"ipc/posix_shared_memory_unittest.cc",
diff --git a/src/tracing/core/id_allocator.cc b/src/tracing/core/id_allocator.cc
new file mode 100644
index 0000000..5af876c
--- /dev/null
+++ b/src/tracing/core/id_allocator.cc
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2017 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/tracing/core/id_allocator.h"
+
+#include "perfetto/base/logging.h"
+
+namespace perfetto {
+
+IdAllocator::IdAllocator(IdType end) : max_id_(end - 1) {
+ PERFETTO_DCHECK(end > 1);
+}
+
+IdAllocator::~IdAllocator() = default;
+
+IdAllocator::IdType IdAllocator::Allocate() {
+ for (IdType ignored = 1; ignored <= max_id_; ignored++) {
+ last_id_ = last_id_ < max_id_ ? last_id_ + 1 : 1;
+ const auto id = last_id_;
+
+ // 0 is never a valid ID. So if we are looking for |id| == N and there are
+ // N or less elements in the vector, they must necessarily be all < N.
+ // e.g. if |id| == 4 and size() == 4, the vector will contain IDs 0,1,2,3.
+ if (id >= ids_.size()) {
+ ids_.resize(id + 1);
+ ids_[id] = true;
+ return id;
+ }
+
+ if (!ids_[id]) {
+ ids_[id] = true;
+ return id;
+ }
+ }
+ return 0;
+}
+
+void IdAllocator::Free(IdType id) {
+ if (id == 0 || id >= ids_.size() || !ids_[id]) {
+ PERFETTO_DCHECK(false);
+ return;
+ }
+ ids_[id] = false;
+}
+
+} // namespace perfetto
diff --git a/src/tracing/core/id_allocator.h b/src/tracing/core/id_allocator.h
new file mode 100644
index 0000000..4377632
--- /dev/null
+++ b/src/tracing/core/id_allocator.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#ifndef SRC_TRACING_CORE_ID_ALLOCATOR_H_
+#define SRC_TRACING_CORE_ID_ALLOCATOR_H_
+
+#include <stdint.h>
+
+#include <vector>
+
+namespace perfetto {
+
+// Handles assigment of IDs (int types) from a fixed-size pool.
+// Zero is not considered a valid ID.
+class IdAllocator {
+ public:
+ using IdType = uint32_t;
+
+ // |end| is exclusive.
+ explicit IdAllocator(IdType end);
+ ~IdAllocator();
+
+ // Returns an ID in the range [1, end - 1] or 0 if no more ids are available.
+ IdType Allocate();
+ void Free(IdType);
+
+ private:
+ IdAllocator(const IdAllocator&) = delete;
+ IdAllocator& operator=(const IdAllocator&) = delete;
+
+ const IdType max_id_;
+ IdType last_id_ = 0;
+ std::vector<bool> ids_;
+};
+
+} // namespace perfetto
+
+#endif // SRC_TRACING_CORE_ID_ALLOCATOR_H_
diff --git a/src/tracing/core/id_allocator_unittest.cc b/src/tracing/core/id_allocator_unittest.cc
new file mode 100644
index 0000000..683b1cf
--- /dev/null
+++ b/src/tracing/core/id_allocator_unittest.cc
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2017 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/tracing/core/id_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace perfetto {
+namespace {
+
+TEST(IdAllocatorTest, IdAllocation) {
+ using IdType = IdAllocator::IdType;
+ const IdType kMaxId = 1024;
+ IdAllocator id_allocator(kMaxId);
+
+ for (int repetition = 0; repetition < 3; repetition++) {
+ std::set<IdType> ids;
+ for (IdType i = 0; i < kMaxId - 1; i++) {
+ auto id = id_allocator.Allocate();
+ EXPECT_NE(0u, id);
+ ASSERT_EQ(0u, ids.count(id));
+ ids.insert(id);
+ }
+
+ // A further call should fail as we exhausted IDs.
+ ASSERT_EQ(0u, id_allocator.Allocate());
+
+ // Removing one ID should be enough to make room for another one.
+ for (int i = 0; i < 3; i++) {
+ id_allocator.Free(42);
+ auto id = id_allocator.Allocate();
+ ASSERT_EQ(42u, id);
+ }
+
+ // Remove the IDs at the boundaries and saturate again.
+ id_allocator.Free(1);
+ id_allocator.Free(kMaxId - 1);
+ ASSERT_EQ(kMaxId - 1, id_allocator.Allocate());
+ ASSERT_EQ(1u, id_allocator.Allocate());
+
+ // Should be saturated again.
+ ASSERT_EQ(0u, id_allocator.Allocate());
+
+ // Release IDs in reverse order.
+ for (IdType i = 0; i < kMaxId - 1; i++)
+ id_allocator.Free(kMaxId - 1 - i);
+ }
+}
+
+} // namespace
+} // namespace perfetto