xref: /aosp_15_r20/external/perfetto/src/tracing/core/id_allocator_unittest.cc (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc)
1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "src/tracing/core/id_allocator.h"
18 
19 #include <type_traits>
20 #include <unordered_set>
21 
22 #include "test/gtest_and_gmock.h"
23 
24 namespace perfetto {
25 namespace {
26 
27 using ::testing::AllOf;
28 using ::testing::Each;
29 using ::testing::Eq;
30 using ::testing::IsEmpty;
31 using ::testing::Not;
32 using ::testing::SizeIs;
33 
34 MATCHER(ElementsAreUnique, "") {
35   std::unordered_set<typename std::remove_reference_t<arg_type>::value_type>
36       seenElements;
37 
38   for (const auto& element : arg) {
39     if (!seenElements.insert(element).second) {
40       *result_listener << "Duplicate element " << element;
41       return false;
42     }
43   }
44 
45   return true;
46 }
47 
TEST(IdAllocatorTest,IdAllocation)48 TEST(IdAllocatorTest, IdAllocation) {
49   using IdType = uint32_t;
50   const IdType kMaxId = 1023;
51   IdAllocator<IdType> id_allocator(kMaxId);
52 
53   for (int repetition = 0; repetition < 3; repetition++) {
54     std::set<IdType> ids;
55     for (IdType i = 1; i <= kMaxId; i++) {
56       auto id = id_allocator.Allocate();
57       EXPECT_NE(0u, id);
58       ASSERT_EQ(0u, ids.count(id));
59       ids.insert(id);
60     }
61 
62     // A further call should fail as we exhausted IDs.
63     ASSERT_EQ(0u, id_allocator.Allocate());
64 
65     // Removing one ID should be enough to make room for another one.
66     for (int i = 0; i < 3; i++) {
67       id_allocator.Free(42);
68       auto id = id_allocator.Allocate();
69       ASSERT_EQ(42u, id);
70     }
71 
72     // Remove the IDs at the boundaries and saturate again.
73     id_allocator.Free(1);
74     id_allocator.Free(kMaxId);
75     ASSERT_EQ(kMaxId, id_allocator.Allocate());
76     ASSERT_EQ(1u, id_allocator.Allocate());
77 
78     // Should be saturated again.
79     ASSERT_EQ(0u, id_allocator.Allocate());
80 
81     // Release IDs in reverse order.
82     for (IdType i = 0; i < kMaxId; i++)
83       id_allocator.Free(kMaxId - i);
84   }
85 }
86 
87 // Tests corner cases that might be caused by using all 2 ** sizeof(T) - 1 IDs.
TEST(IdAllocatorTest,IdAllocation_U8)88 TEST(IdAllocatorTest, IdAllocation_U8) {
89   IdAllocator<uint8_t> id_allocator(0xff);
90   for (size_t i = 0; i < 0xff; i++) {
91     uint8_t id = id_allocator.Allocate();
92     ASSERT_EQ(i + 1, id);
93   }
94   ASSERT_EQ(0u, id_allocator.Allocate());
95   id_allocator.Free(0xff);
96   ASSERT_EQ(0xff, id_allocator.Allocate());
97 }
98 
TEST(IdAllocatorTest,IdAllocationMultiple)99 TEST(IdAllocatorTest, IdAllocationMultiple) {
100   using IdType = uint16_t;
101   const IdType kMaxId = 1023;
102   IdAllocator<IdType> id_allocator(kMaxId);
103 
104   for (size_t i = 0; i < 250; i++) {
105     EXPECT_THAT(id_allocator.AllocateMultiple(4),
106                 AllOf(SizeIs(4), ElementsAreUnique(), Each(Not(Eq(0)))));
107   }
108 
109   EXPECT_THAT(id_allocator.AllocateMultiple(25), IsEmpty());
110 }
111 
112 }  // namespace
113 }  // namespace perfetto
114