1 /* $NetBSD: i915_syncmap.c,v 1.2 2021/12/18 23:45:31 riastradh Exp $ */
2
3 /*
4 * Copyright © 2017 Intel Corporation
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice (including the next
14 * paragraph) shall be included in all copies or substantial portions of the
15 * Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
22 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
23 * IN THE SOFTWARE.
24 *
25 */
26
27 #include <sys/cdefs.h>
28 __KERNEL_RCSID(0, "$NetBSD: i915_syncmap.c,v 1.2 2021/12/18 23:45:31 riastradh Exp $");
29
30 #include "../i915_selftest.h"
31 #include "i915_random.h"
32
33 static char *
__sync_print(struct i915_syncmap * p,char * buf,unsigned long * sz,unsigned int depth,unsigned int last,unsigned int idx)34 __sync_print(struct i915_syncmap *p,
35 char *buf, unsigned long *sz,
36 unsigned int depth,
37 unsigned int last,
38 unsigned int idx)
39 {
40 unsigned long len;
41 unsigned int i, X;
42
43 if (depth) {
44 unsigned int d;
45
46 for (d = 0; d < depth - 1; d++) {
47 if (last & BIT(depth - d - 1))
48 len = scnprintf(buf, *sz, "| ");
49 else
50 len = scnprintf(buf, *sz, " ");
51 buf += len;
52 *sz -= len;
53 }
54 len = scnprintf(buf, *sz, "%x-> ", idx);
55 buf += len;
56 *sz -= len;
57 }
58
59 /* We mark bits after the prefix as "X" */
60 len = scnprintf(buf, *sz, "0x%016llx", p->prefix << p->height << SHIFT);
61 buf += len;
62 *sz -= len;
63 X = (p->height + SHIFT) / 4;
64 scnprintf(buf - X, *sz + X, "%*s", X, "XXXXXXXXXXXXXXXXX");
65
66 if (!p->height) {
67 for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
68 len = scnprintf(buf, *sz, " %x:%x,",
69 i, __sync_seqno(p)[i]);
70 buf += len;
71 *sz -= len;
72 }
73 buf -= 1;
74 *sz += 1;
75 }
76
77 len = scnprintf(buf, *sz, "\n");
78 buf += len;
79 *sz -= len;
80
81 if (p->height) {
82 for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
83 buf = __sync_print(__sync_child(p)[i], buf, sz,
84 depth + 1,
85 last << 1 | !!(p->bitmap >> (i + 1)),
86 i);
87 }
88 }
89
90 return buf;
91 }
92
93 static bool
i915_syncmap_print_to_buf(struct i915_syncmap * p,char * buf,unsigned long sz)94 i915_syncmap_print_to_buf(struct i915_syncmap *p, char *buf, unsigned long sz)
95 {
96 if (!p)
97 return false;
98
99 while (p->parent)
100 p = p->parent;
101
102 __sync_print(p, buf, &sz, 0, 1, 0);
103 return true;
104 }
105
check_syncmap_free(struct i915_syncmap ** sync)106 static int check_syncmap_free(struct i915_syncmap **sync)
107 {
108 i915_syncmap_free(sync);
109 if (*sync) {
110 pr_err("sync not cleared after free\n");
111 return -EINVAL;
112 }
113
114 return 0;
115 }
116
dump_syncmap(struct i915_syncmap * sync,int err)117 static int dump_syncmap(struct i915_syncmap *sync, int err)
118 {
119 char *buf;
120
121 if (!err)
122 return check_syncmap_free(&sync);
123
124 buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
125 if (!buf)
126 goto skip;
127
128 if (i915_syncmap_print_to_buf(sync, buf, PAGE_SIZE))
129 pr_err("%s", buf);
130
131 kfree(buf);
132
133 skip:
134 i915_syncmap_free(&sync);
135 return err;
136 }
137
igt_syncmap_init(void * arg)138 static int igt_syncmap_init(void *arg)
139 {
140 struct i915_syncmap *sync = (void *)~0ul;
141
142 /*
143 * Cursory check that we can initialise a random pointer and transform
144 * it into the root pointer of a syncmap.
145 */
146
147 i915_syncmap_init(&sync);
148 return check_syncmap_free(&sync);
149 }
150
check_seqno(struct i915_syncmap * leaf,unsigned int idx,u32 seqno)151 static int check_seqno(struct i915_syncmap *leaf, unsigned int idx, u32 seqno)
152 {
153 if (leaf->height) {
154 pr_err("%s: not a leaf, height is %d\n",
155 __func__, leaf->height);
156 return -EINVAL;
157 }
158
159 if (__sync_seqno(leaf)[idx] != seqno) {
160 pr_err("%s: seqno[%d], found %x, expected %x\n",
161 __func__, idx, __sync_seqno(leaf)[idx], seqno);
162 return -EINVAL;
163 }
164
165 return 0;
166 }
167
check_one(struct i915_syncmap ** sync,u64 context,u32 seqno)168 static int check_one(struct i915_syncmap **sync, u64 context, u32 seqno)
169 {
170 int err;
171
172 err = i915_syncmap_set(sync, context, seqno);
173 if (err)
174 return err;
175
176 if ((*sync)->height) {
177 pr_err("Inserting first context=%llx did not return leaf (height=%d, prefix=%llx\n",
178 context, (*sync)->height, (*sync)->prefix);
179 return -EINVAL;
180 }
181
182 if ((*sync)->parent) {
183 pr_err("Inserting first context=%llx created branches!\n",
184 context);
185 return -EINVAL;
186 }
187
188 if (hweight32((*sync)->bitmap) != 1) {
189 pr_err("First bitmap does not contain a single entry, found %x (count=%d)!\n",
190 (*sync)->bitmap, hweight32((*sync)->bitmap));
191 return -EINVAL;
192 }
193
194 err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno);
195 if (err)
196 return err;
197
198 if (!i915_syncmap_is_later(sync, context, seqno)) {
199 pr_err("Lookup of first context=%llx/seqno=%x failed!\n",
200 context, seqno);
201 return -EINVAL;
202 }
203
204 return 0;
205 }
206
igt_syncmap_one(void * arg)207 static int igt_syncmap_one(void *arg)
208 {
209 I915_RND_STATE(prng);
210 IGT_TIMEOUT(end_time);
211 struct i915_syncmap *sync;
212 unsigned long max = 1;
213 int err;
214
215 /*
216 * Check that inserting a new id, creates a leaf and only that leaf.
217 */
218
219 i915_syncmap_init(&sync);
220
221 do {
222 u64 context = i915_prandom_u64_state(&prng);
223 unsigned long loop;
224
225 err = check_syncmap_free(&sync);
226 if (err)
227 goto out;
228
229 for (loop = 0; loop <= max; loop++) {
230 err = check_one(&sync, context,
231 prandom_u32_state(&prng));
232 if (err)
233 goto out;
234 }
235 max++;
236 } while (!__igt_timeout(end_time, NULL));
237 pr_debug("%s: Completed %lu single insertions\n",
238 __func__, max * (max - 1) / 2);
239 out:
240 return dump_syncmap(sync, err);
241 }
242
check_leaf(struct i915_syncmap ** sync,u64 context,u32 seqno)243 static int check_leaf(struct i915_syncmap **sync, u64 context, u32 seqno)
244 {
245 int err;
246
247 err = i915_syncmap_set(sync, context, seqno);
248 if (err)
249 return err;
250
251 if ((*sync)->height) {
252 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n",
253 context, (*sync)->height, (*sync)->prefix);
254 return -EINVAL;
255 }
256
257 if (hweight32((*sync)->bitmap) != 1) {
258 pr_err("First entry into leaf (context=%llx) does not contain a single entry, found %x (count=%d)!\n",
259 context, (*sync)->bitmap, hweight32((*sync)->bitmap));
260 return -EINVAL;
261 }
262
263 err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno);
264 if (err)
265 return err;
266
267 if (!i915_syncmap_is_later(sync, context, seqno)) {
268 pr_err("Lookup of first entry context=%llx/seqno=%x failed!\n",
269 context, seqno);
270 return -EINVAL;
271 }
272
273 return 0;
274 }
275
igt_syncmap_join_above(void * arg)276 static int igt_syncmap_join_above(void *arg)
277 {
278 struct i915_syncmap *sync;
279 unsigned int pass, order;
280 int err;
281
282 i915_syncmap_init(&sync);
283
284 /*
285 * When we have a new id that doesn't fit inside the existing tree,
286 * we need to add a new layer above.
287 *
288 * 1: 0x00000001
289 * 2: 0x00000010
290 * 3: 0x00000100
291 * 4: 0x00001000
292 * ...
293 * Each pass the common prefix shrinks and we have to insert a join.
294 * Each join will only contain two branches, the latest of which
295 * is always a leaf.
296 *
297 * If we then reuse the same set of contexts, we expect to build an
298 * identical tree.
299 */
300 for (pass = 0; pass < 3; pass++) {
301 for (order = 0; order < 64; order += SHIFT) {
302 u64 context = BIT_ULL(order);
303 struct i915_syncmap *join;
304
305 err = check_leaf(&sync, context, 0);
306 if (err)
307 goto out;
308
309 join = sync->parent;
310 if (!join) /* very first insert will have no parents */
311 continue;
312
313 if (!join->height) {
314 pr_err("Parent with no height!\n");
315 err = -EINVAL;
316 goto out;
317 }
318
319 if (hweight32(join->bitmap) != 2) {
320 pr_err("Join does not have 2 children: %x (%d)\n",
321 join->bitmap, hweight32(join->bitmap));
322 err = -EINVAL;
323 goto out;
324 }
325
326 if (__sync_child(join)[__sync_branch_idx(join, context)] != sync) {
327 pr_err("Leaf misplaced in parent!\n");
328 err = -EINVAL;
329 goto out;
330 }
331 }
332 }
333 out:
334 return dump_syncmap(sync, err);
335 }
336
igt_syncmap_join_below(void * arg)337 static int igt_syncmap_join_below(void *arg)
338 {
339 struct i915_syncmap *sync;
340 unsigned int step, order, idx;
341 int err = -ENODEV;
342
343 i915_syncmap_init(&sync);
344
345 /*
346 * Check that we can split a compacted branch by replacing it with
347 * a join.
348 */
349 for (step = 0; step < KSYNCMAP; step++) {
350 for (order = 64 - SHIFT; order > 0; order -= SHIFT) {
351 u64 context = step * BIT_ULL(order);
352
353 err = i915_syncmap_set(&sync, context, 0);
354 if (err)
355 goto out;
356
357 if (sync->height) {
358 pr_err("Inserting context=%llx (order=%d, step=%d) did not return leaf (height=%d, prefix=%llx\n",
359 context, order, step, sync->height, sync->prefix);
360 err = -EINVAL;
361 goto out;
362 }
363 }
364 }
365
366 for (step = 0; step < KSYNCMAP; step++) {
367 for (order = SHIFT; order < 64; order += SHIFT) {
368 u64 context = step * BIT_ULL(order);
369
370 if (!i915_syncmap_is_later(&sync, context, 0)) {
371 pr_err("1: context %llx (order=%d, step=%d) not found\n",
372 context, order, step);
373 err = -EINVAL;
374 goto out;
375 }
376
377 for (idx = 1; idx < KSYNCMAP; idx++) {
378 if (i915_syncmap_is_later(&sync, context + idx, 0)) {
379 pr_err("1: context %llx (order=%d, step=%d) should not exist\n",
380 context + idx, order, step);
381 err = -EINVAL;
382 goto out;
383 }
384 }
385 }
386 }
387
388 for (order = SHIFT; order < 64; order += SHIFT) {
389 for (step = 0; step < KSYNCMAP; step++) {
390 u64 context = step * BIT_ULL(order);
391
392 if (!i915_syncmap_is_later(&sync, context, 0)) {
393 pr_err("2: context %llx (order=%d, step=%d) not found\n",
394 context, order, step);
395 err = -EINVAL;
396 goto out;
397 }
398 }
399 }
400
401 out:
402 return dump_syncmap(sync, err);
403 }
404
igt_syncmap_neighbours(void * arg)405 static int igt_syncmap_neighbours(void *arg)
406 {
407 I915_RND_STATE(prng);
408 IGT_TIMEOUT(end_time);
409 struct i915_syncmap *sync;
410 int err = -ENODEV;
411
412 /*
413 * Each leaf holds KSYNCMAP seqno. Check that when we create KSYNCMAP
414 * neighbouring ids, they all fit into the same leaf.
415 */
416
417 i915_syncmap_init(&sync);
418 do {
419 u64 context = i915_prandom_u64_state(&prng) & ~MASK;
420 unsigned int idx;
421
422 if (i915_syncmap_is_later(&sync, context, 0)) /* Skip repeats */
423 continue;
424
425 for (idx = 0; idx < KSYNCMAP; idx++) {
426 err = i915_syncmap_set(&sync, context + idx, 0);
427 if (err)
428 goto out;
429
430 if (sync->height) {
431 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n",
432 context, sync->height, sync->prefix);
433 err = -EINVAL;
434 goto out;
435 }
436
437 if (sync->bitmap != BIT(idx + 1) - 1) {
438 pr_err("Inserting neighbouring context=0x%llx+%d, did not fit into the same leaf bitmap=%x (%d), expected %lx (%d)\n",
439 context, idx,
440 sync->bitmap, hweight32(sync->bitmap),
441 BIT(idx + 1) - 1, idx + 1);
442 err = -EINVAL;
443 goto out;
444 }
445 }
446 } while (!__igt_timeout(end_time, NULL));
447 out:
448 return dump_syncmap(sync, err);
449 }
450
igt_syncmap_compact(void * arg)451 static int igt_syncmap_compact(void *arg)
452 {
453 struct i915_syncmap *sync;
454 unsigned int idx, order;
455 int err = -ENODEV;
456
457 i915_syncmap_init(&sync);
458
459 /*
460 * The syncmap are "space efficient" compressed radix trees - any
461 * branch with only one child is skipped and replaced by the child.
462 *
463 * If we construct a tree with ids that are neighbouring at a non-zero
464 * height, we form a join but each child of that join is directly a
465 * leaf holding the single id.
466 */
467 for (order = SHIFT; order < 64; order += SHIFT) {
468 err = check_syncmap_free(&sync);
469 if (err)
470 goto out;
471
472 /* Create neighbours in the parent */
473 for (idx = 0; idx < KSYNCMAP; idx++) {
474 u64 context = idx * BIT_ULL(order) + idx;
475
476 err = i915_syncmap_set(&sync, context, 0);
477 if (err)
478 goto out;
479
480 if (sync->height) {
481 pr_err("Inserting context=%llx (order=%d, idx=%d) did not return leaf (height=%d, prefix=%llx\n",
482 context, order, idx,
483 sync->height, sync->prefix);
484 err = -EINVAL;
485 goto out;
486 }
487 }
488
489 sync = sync->parent;
490 if (sync->parent) {
491 pr_err("Parent (join) of last leaf was not the sync!\n");
492 err = -EINVAL;
493 goto out;
494 }
495
496 if (sync->height != order) {
497 pr_err("Join does not have the expected height, found %d, expected %d\n",
498 sync->height, order);
499 err = -EINVAL;
500 goto out;
501 }
502
503 if (sync->bitmap != BIT(KSYNCMAP) - 1) {
504 pr_err("Join is not full!, found %x (%d) expected %lx (%d)\n",
505 sync->bitmap, hweight32(sync->bitmap),
506 BIT(KSYNCMAP) - 1, KSYNCMAP);
507 err = -EINVAL;
508 goto out;
509 }
510
511 /* Each of our children should be a leaf */
512 for (idx = 0; idx < KSYNCMAP; idx++) {
513 struct i915_syncmap *leaf = __sync_child(sync)[idx];
514
515 if (leaf->height) {
516 pr_err("Child %d is a not leaf!\n", idx);
517 err = -EINVAL;
518 goto out;
519 }
520
521 if (leaf->parent != sync) {
522 pr_err("Child %d is not attached to us!\n",
523 idx);
524 err = -EINVAL;
525 goto out;
526 }
527
528 if (!is_power_of_2(leaf->bitmap)) {
529 pr_err("Child %d holds more than one id, found %x (%d)\n",
530 idx, leaf->bitmap, hweight32(leaf->bitmap));
531 err = -EINVAL;
532 goto out;
533 }
534
535 if (leaf->bitmap != BIT(idx)) {
536 pr_err("Child %d has wrong seqno idx, found %d, expected %d\n",
537 idx, ilog2(leaf->bitmap), idx);
538 err = -EINVAL;
539 goto out;
540 }
541 }
542 }
543 out:
544 return dump_syncmap(sync, err);
545 }
546
igt_syncmap_random(void * arg)547 static int igt_syncmap_random(void *arg)
548 {
549 I915_RND_STATE(prng);
550 IGT_TIMEOUT(end_time);
551 struct i915_syncmap *sync;
552 unsigned long count, phase, i;
553 u32 seqno;
554 int err;
555
556 i915_syncmap_init(&sync);
557
558 /*
559 * Having tried to test the individual operations within i915_syncmap,
560 * run a smoketest exploring the entire u64 space with random
561 * insertions.
562 */
563
564 count = 0;
565 phase = jiffies + HZ/100 + 1;
566 do {
567 u64 context = i915_prandom_u64_state(&prng);
568
569 err = i915_syncmap_set(&sync, context, 0);
570 if (err)
571 goto out;
572
573 count++;
574 } while (!time_after(jiffies, phase));
575 seqno = 0;
576
577 phase = 0;
578 do {
579 I915_RND_STATE(ctx);
580 u32 last_seqno = seqno;
581 bool expect;
582
583 seqno = prandom_u32_state(&prng);
584 expect = seqno_later(last_seqno, seqno);
585
586 for (i = 0; i < count; i++) {
587 u64 context = i915_prandom_u64_state(&ctx);
588
589 if (i915_syncmap_is_later(&sync, context, seqno) != expect) {
590 pr_err("context=%llu, last=%u this=%u did not match expectation (%d)\n",
591 context, last_seqno, seqno, expect);
592 err = -EINVAL;
593 goto out;
594 }
595
596 err = i915_syncmap_set(&sync, context, seqno);
597 if (err)
598 goto out;
599 }
600
601 phase++;
602 } while (!__igt_timeout(end_time, NULL));
603 pr_debug("Completed %lu passes, each of %lu contexts\n", phase, count);
604 out:
605 return dump_syncmap(sync, err);
606 }
607
i915_syncmap_mock_selftests(void)608 int i915_syncmap_mock_selftests(void)
609 {
610 static const struct i915_subtest tests[] = {
611 SUBTEST(igt_syncmap_init),
612 SUBTEST(igt_syncmap_one),
613 SUBTEST(igt_syncmap_join_above),
614 SUBTEST(igt_syncmap_join_below),
615 SUBTEST(igt_syncmap_neighbours),
616 SUBTEST(igt_syncmap_compact),
617 SUBTEST(igt_syncmap_random),
618 };
619
620 return i915_subtests(tests, NULL);
621 }
622