1#include "tests/test_internal.h"
2
3TEST_GROUP_DECLARE(stack_depot, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "records",
6 });
7
8#define SD_SEED 0xDEADBEEFULL
9#define SD_TRACE_LEN 8
10#define SD_MANY 4096
11static_assert(SD_MANY > STACK_DEPOT_HASH_SIZE); /* Force collisions */
12
13static void sd_make_trace(uintptr_t *entries, size_t len, uint64_t id) {
14 for (size_t i = 0; i < len; i++)
15 entries[i] = (uintptr_t) (0xffffffff80000000ULL + (id << 20) + i * 16);
16}
17
18TEST_DECLARE_UNIT(stack_depot, basic) {
19 stack_handle_t handle = stack_depot_save_current();
20 TEST_ASSERT_NONNULL(handle);
21
22 struct stack_depot_record *rec = stack_depot_get_record(key: handle);
23 TEST_ASSERT_NONNULL(rec);
24 TEST_ASSERT_GT(rec->num_entries, 0);
25 TEST_ASSERT_LE(rec->num_entries, STACK_TRACE_MAX_DEPTH);
26 TEST_ASSERT_EQ(refcount_read(&rec->refcount), 1);
27
28 uintptr_t entries[STACK_TRACE_MAX_DEPTH] = {0};
29 size_t n = stack_depot_read(key: handle, entries);
30 TEST_ASSERT_EQ(n, rec->num_entries);
31 TEST_ASSERT_MEM_EQ(entries, rec->entries, n * sizeof(uintptr_t));
32
33 stack_depot_put(key: handle);
34 return TEST_SUCCESS;
35}
36
37TEST_DECLARE_UNIT(stack_depot, dedup) {
38 uintptr_t trace[SD_TRACE_LEN];
39 sd_make_trace(entries: trace, SD_TRACE_LEN, id: 1);
40
41 stack_handle_t a =
42 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
43 TEST_ASSERT_NONNULL(a);
44 TEST_ASSERT_EQ(refcount_read(&stack_depot_get_record(a)->refcount), 1);
45
46 stack_handle_t b =
47 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
48 TEST_ASSERT_PTR_EQ(b, a);
49 TEST_ASSERT_EQ(refcount_read(&stack_depot_get_record(a)->refcount), 2);
50
51 /* A copy of the same bytes in a different buffer must dedup */
52 uintptr_t copy[SD_TRACE_LEN];
53 memcpy(copy, trace, sizeof(copy));
54 stack_handle_t c =
55 stack_depot_save(entries: copy, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
56 TEST_ASSERT_PTR_EQ(c, a);
57 TEST_ASSERT_EQ(refcount_read(&stack_depot_get_record(a)->refcount), 3);
58
59 stack_depot_put(key: c);
60 stack_depot_put(key: b);
61 TEST_ASSERT_EQ(refcount_read(&stack_depot_get_record(a)->refcount), 1);
62 stack_depot_put(key: a);
63
64 stack_handle_t d =
65 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
66 TEST_ASSERT_NONNULL(d);
67 TEST_ASSERT_EQ(refcount_read(&stack_depot_get_record(d)->refcount), 1);
68 stack_depot_put(key: d);
69
70 return TEST_SUCCESS;
71}
72
73TEST_DECLARE_UNIT(stack_depot, distinct) {
74 uintptr_t a[SD_TRACE_LEN], b[SD_TRACE_LEN];
75 sd_make_trace(entries: a, SD_TRACE_LEN, id: 2);
76 sd_make_trace(entries: b, SD_TRACE_LEN, id: 3);
77
78 stack_handle_t ha = stack_depot_save(entries: a, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
79 stack_handle_t hb = stack_depot_save(entries: b, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
80 TEST_ASSERT_NONNULL(ha);
81 TEST_ASSERT_NONNULL(hb);
82 TEST_ASSERT_PTR_NE(ha, hb);
83
84 /* Same prefix at shorter length is different record */
85 stack_handle_t hp =
86 stack_depot_save(entries: a, SD_TRACE_LEN / 2, ALLOC_FLAGS_DEFAULT);
87 TEST_ASSERT_NONNULL(hp);
88 TEST_ASSERT_PTR_NE(hp, ha);
89 TEST_ASSERT_EQ(stack_depot_get_record(hp)->num_entries, SD_TRACE_LEN / 2);
90
91 uintptr_t tail[SD_TRACE_LEN];
92 memcpy(tail, a, sizeof(tail));
93 tail[SD_TRACE_LEN - 1] ^= 0x1000;
94 stack_handle_t ht =
95 stack_depot_save(entries: tail, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
96 TEST_ASSERT_NONNULL(ht);
97 TEST_ASSERT_PTR_NE(ht, ha);
98
99 uintptr_t out[STACK_TRACE_MAX_DEPTH] = {0};
100 TEST_ASSERT_EQ(stack_depot_read(ht, out), SD_TRACE_LEN);
101 TEST_ASSERT_MEM_EQ(out, tail, sizeof(tail));
102
103 stack_depot_put(key: ht);
104 stack_depot_put(key: hp);
105 stack_depot_put(key: hb);
106 stack_depot_put(key: ha);
107 return TEST_SUCCESS;
108}
109
110TEST_DECLARE_UNIT(stack_depot, hash_bucket) {
111 uintptr_t trace[SD_TRACE_LEN];
112 sd_make_trace(entries: trace, SD_TRACE_LEN, id: 4);
113
114 uint32_t expect = stack_depot_hash(entries: trace, SD_TRACE_LEN);
115 stack_handle_t h =
116 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
117 TEST_ASSERT_NONNULL(h);
118
119 struct stack_depot_record *rec = stack_depot_get_record(key: h);
120 TEST_ASSERT_EQ(rec->hash, expect);
121
122 /* Test reachability from our end */
123 struct stack_depot_record_chain *chain =
124 &stack_depot_global.chains[rec->hash % STACK_DEPOT_HASH_SIZE];
125 bool found = false;
126 struct stack_depot_record *pos;
127 enum irql irql = spin_lock(&chain->lock);
128 list_for_each_entry(pos, &chain->list, hash_list) {
129 if (pos == rec) {
130 found = true;
131 break;
132 }
133 }
134 spin_unlock(&chain->lock, irql);
135 TEST_ASSERT(found);
136
137 stack_depot_put(key: h);
138 return TEST_SUCCESS;
139}
140
141TEST_DECLARE_UNIT(stack_depot, many, TEST_INTENSITY(128, 1024, 4096)) {
142 size_t count = ctx->intensity_val ? ctx->intensity_val : SD_MANY;
143 stack_handle_t *handles =
144 kmalloc(sizeof(*handles) * count, ALLOC_FLAGS_ZERO);
145 TEST_ASSERT_NONNULL(handles);
146
147 prng_seed(SD_SEED);
148
149 for (size_t i = 0; i < count; i++) {
150 uintptr_t trace[SD_TRACE_LEN];
151 sd_make_trace(entries: trace, SD_TRACE_LEN, id: 0x100 + i);
152 handles[i] = stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
153 if (!handles[i]) {
154 /* OOM? Unwind + skip */
155 for (size_t j = 0; j < i; j++)
156 stack_depot_put(key: handles[j]);
157 kfree(handles);
158 return TEST_SKIP(TEST_SKIP_RAM_LOW);
159 }
160 }
161
162 for (size_t i = 0; i < count; i++) {
163 uintptr_t want[SD_TRACE_LEN], got[STACK_TRACE_MAX_DEPTH] = {0};
164 sd_make_trace(entries: want, SD_TRACE_LEN, id: 0x100 + i);
165
166 TEST_ASSERT_EQ(stack_depot_read(handles[i], got), SD_TRACE_LEN);
167 TEST_ASSERT_MEM_EQ(got, want, sizeof(want));
168 TEST_ASSERT_EQ(
169 refcount_read(&stack_depot_get_record(handles[i])->refcount), 1);
170
171 /* Re-saving in random order should hit existing record */
172 TEST_ASSERT_PTR_EQ(
173 stack_depot_save(want, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT),
174 handles[i]);
175 stack_depot_put(key: handles[i]);
176 }
177
178 for (size_t i = 0; i < count; i++)
179 for (size_t j = i + 1; j < count; j++)
180 TEST_ASSERT_PTR_NE(handles[i], handles[j]);
181
182 for (size_t i = 0; i < count; i++)
183 stack_depot_put(key: handles[i]);
184
185 kfree(handles);
186 return TEST_SUCCESS;
187}
188
189TEST_DECLARE_UNIT(stack_depot, churn, TEST_INTENSITY(200, 2000, 20000)) {
190 prng_seed(SD_SEED + 1);
191
192 enum { SD_CHURN_SET = 32 };
193 size_t ops = ctx->intensity_val ? ctx->intensity_val : 2000;
194 stack_handle_t live[SD_CHURN_SET] = {0};
195
196 for (size_t op = 0; op < ops; op++) {
197 size_t i = prng_next() % SD_CHURN_SET;
198 uintptr_t trace[SD_TRACE_LEN];
199 sd_make_trace(entries: trace, SD_TRACE_LEN, id: 0x2000 + i);
200
201 if (live[i]) {
202 uintptr_t got[STACK_TRACE_MAX_DEPTH] = {0};
203 TEST_ASSERT_EQ(stack_depot_read(live[i], got), SD_TRACE_LEN);
204 TEST_ASSERT_MEM_EQ(got, trace, sizeof(trace));
205 stack_depot_put(key: live[i]);
206 live[i] = NULL;
207 } else {
208 live[i] =
209 stack_depot_save(entries: trace, SD_TRACE_LEN, ALLOC_FLAGS_DEFAULT);
210 TEST_ASSERT_NONNULL(live[i]);
211 TEST_ASSERT_EQ(stack_depot_get_record(live[i])->num_entries,
212 SD_TRACE_LEN);
213 }
214 }
215
216 for (size_t i = 0; i < SD_CHURN_SET; i++)
217 if (live[i])
218 stack_depot_put(key: live[i]);
219
220 return TEST_SUCCESS;
221}
222
223static __noinline void sd_save_n(stack_handle_t *out, size_t n) {
224 for (size_t i = 0; i < n; i++)
225 out[i] = stack_depot_save_current();
226}
227
228TEST_DECLARE_UNIT(stack_depot, save_current_dedup) {
229 stack_handle_t h[2] = {0};
230 volatile size_t n = 2;
231
232 sd_save_n(out: h, n);
233 TEST_ASSERT_NONNULL(h[0]);
234 TEST_ASSERT_NONNULL(h[1]);
235 TEST_ASSERT_PTR_EQ(h[0], h[1]);
236 TEST_ASSERT_EQ(refcount_read(&stack_depot_get_record(h[0])->refcount), 2);
237
238 stack_depot_put(key: h[1]);
239 stack_depot_put(key: h[0]);
240 return TEST_SUCCESS;
241}
242