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
28static 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)) ? 1 : 0),
81					   i);
82		}
83	}
84
85	return buf;
86}
87
88static bool
89i915_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
101static 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
112static 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
128skip:
129	i915_syncmap_free(&sync);
130	return err;
131}
132
133static 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
146static 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
163static 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
202static 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);
234out:
235	return dump_syncmap(sync, err);
236}
237
238static 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
271static 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	}
328out:
329	return dump_syncmap(sync, err);
330}
331
332static 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
396out:
397	return dump_syncmap(sync, err);
398}
399
400static 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));
442out:
443	return dump_syncmap(sync, err);
444}
445
446static 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	}
538out:
539	return dump_syncmap(sync, err);
540}
541
542static 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);
599out:
600	return dump_syncmap(sync, err);
601}
602
603int 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