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, *sz, "|   ");
44 			else
45 				len = scnprintf(buf, *sz, "    ");
46 			buf += len;
47 			*sz -= len;
48 		}
49 		len = scnprintf(buf, *sz, "%x-> ", idx);
50 		buf += len;
51 		*sz -= len;
52 	}
53 
54 	/* We mark bits after the prefix as "X" */
55 	len = scnprintf(buf, *sz, "0x%016llx", p->prefix << p->height << SHIFT);
56 	buf += len;
57 	*sz -= len;
58 	X = (p->height + SHIFT) / 4;
59 	scnprintf(buf - X, *sz + X, "%*s", X, "XXXXXXXXXXXXXXXXX");
60 
61 	if (!p->height) {
62 		for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
63 			len = scnprintf(buf, *sz, " %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, *sz, "\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(__sync_child(p)[i], buf, sz,
79 					   depth + 1,
80 					   last << 1 | !!(p->bitmap >> (i + 1)),
81 					   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, 0, 1, 0);
98 	return true;
99 }
100 
101 static int check_syncmap_free(struct i915_syncmap **sync)
102 {
103 	i915_syncmap_free(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);
118 
119 	buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
120 	if (!buf)
121 		goto skip;
122 
123 	if (i915_syncmap_print_to_buf(sync, buf, PAGE_SIZE))
124 		pr_err("%s", buf);
125 
126 	kfree(buf);
127 
128 skip:
129 	i915_syncmap_free(&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(&sync);
143 	return check_syncmap_free(&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(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(sync, 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((*sync), ilog2((*sync)->bitmap), seqno);
190 	if (err)
191 		return err;
192 
193 	if (!i915_syncmap_is_later(sync, 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(&sync);
215 
216 	do {
217 		u64 context = i915_prandom_u64_state(&prng);
218 		unsigned long loop;
219 
220 		err = check_syncmap_free(&sync);
221 		if (err)
222 			goto out;
223 
224 		for (loop = 0; loop <= max; loop++) {
225 			err = check_one(&sync, context,
226 					prandom_u32_state(&prng));
227 			if (err)
228 				goto out;
229 		}
230 		max++;
231 	} while (!__igt_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(sync, 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((*sync), ilog2((*sync)->bitmap), seqno);
259 	if (err)
260 		return err;
261 
262 	if (!i915_syncmap_is_later(sync, 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(&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, context, 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(join)[__sync_branch_idx(join, 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(&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(&sync, context, 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(&sync, context, 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(&sync, context + idx, 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(&sync, context, 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(&sync);
413 	do {
414 		u64 context = i915_prandom_u64_state(&prng) & ~MASK;
415 		unsigned int idx;
416 
417 		if (i915_syncmap_is_later(&sync, context, 0)) /* Skip repeats */
418 			continue;
419 
420 		for (idx = 0; idx < KSYNCMAP; idx++) {
421 			err = i915_syncmap_set(&sync, context + idx, 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(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(&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);
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(&sync, context, 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(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(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(&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(&prng);
563 
564 		err = i915_syncmap_set(&sync, context, 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(&prng);
579 		expect = seqno_later(last_seqno, seqno);
580 
581 		for (i = 0; i < count; i++) {
582 			u64 context = i915_prandom_u64_state(&ctx);
583 
584 			if (i915_syncmap_is_later(&sync, 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(&sync, context, seqno);
592 			if (err)
593 				goto out;
594 		}
595 
596 		phase++;
597 	} while (!__igt_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