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