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