147979480SChris Wilson /* 247979480SChris Wilson * Copyright © 2017 Intel Corporation 347979480SChris Wilson * 447979480SChris Wilson * Permission is hereby granted, free of charge, to any person obtaining a 547979480SChris Wilson * copy of this software and associated documentation files (the "Software"), 647979480SChris Wilson * to deal in the Software without restriction, including without limitation 747979480SChris Wilson * the rights to use, copy, modify, merge, publish, distribute, sublicense, 847979480SChris Wilson * and/or sell copies of the Software, and to permit persons to whom the 947979480SChris Wilson * Software is furnished to do so, subject to the following conditions: 1047979480SChris Wilson * 1147979480SChris Wilson * The above copyright notice and this permission notice (including the next 1247979480SChris Wilson * paragraph) shall be included in all copies or substantial portions of the 1347979480SChris Wilson * Software. 1447979480SChris Wilson * 1547979480SChris Wilson * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 1647979480SChris Wilson * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 1747979480SChris Wilson * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 1847979480SChris Wilson * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 1947979480SChris Wilson * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 2047979480SChris Wilson * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 2147979480SChris Wilson * IN THE SOFTWARE. 2247979480SChris Wilson * 2347979480SChris Wilson */ 2447979480SChris Wilson 2547979480SChris Wilson #include "../i915_selftest.h" 2647979480SChris Wilson #include "i915_random.h" 2747979480SChris Wilson 2847979480SChris Wilson static char * 2947979480SChris Wilson __sync_print(struct i915_syncmap *p, 3047979480SChris Wilson char *buf, unsigned long *sz, 3147979480SChris Wilson unsigned int depth, 3247979480SChris Wilson unsigned int last, 3347979480SChris Wilson unsigned int idx) 3447979480SChris Wilson { 3547979480SChris Wilson unsigned long len; 3647979480SChris Wilson unsigned int i, X; 3747979480SChris Wilson 3847979480SChris Wilson if (depth) { 3947979480SChris Wilson unsigned int d; 4047979480SChris Wilson 4147979480SChris Wilson for (d = 0; d < depth - 1; d++) { 4247979480SChris Wilson if (last & BIT(depth - d - 1)) 4347979480SChris Wilson len = scnprintf(buf, *sz, "| "); 4447979480SChris Wilson else 4547979480SChris Wilson len = scnprintf(buf, *sz, " "); 4647979480SChris Wilson buf += len; 4747979480SChris Wilson *sz -= len; 4847979480SChris Wilson } 4947979480SChris Wilson len = scnprintf(buf, *sz, "%x-> ", idx); 5047979480SChris Wilson buf += len; 5147979480SChris Wilson *sz -= len; 5247979480SChris Wilson } 5347979480SChris Wilson 5447979480SChris Wilson /* We mark bits after the prefix as "X" */ 5547979480SChris Wilson len = scnprintf(buf, *sz, "0x%016llx", p->prefix << p->height << SHIFT); 5647979480SChris Wilson buf += len; 5747979480SChris Wilson *sz -= len; 5847979480SChris Wilson X = (p->height + SHIFT) / 4; 5947979480SChris Wilson scnprintf(buf - X, *sz + X, "%*s", X, "XXXXXXXXXXXXXXXXX"); 6047979480SChris Wilson 6147979480SChris Wilson if (!p->height) { 6247979480SChris Wilson for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) { 6347979480SChris Wilson len = scnprintf(buf, *sz, " %x:%x,", 6447979480SChris Wilson i, __sync_seqno(p)[i]); 6547979480SChris Wilson buf += len; 6647979480SChris Wilson *sz -= len; 6747979480SChris Wilson } 6847979480SChris Wilson buf -= 1; 6947979480SChris Wilson *sz += 1; 7047979480SChris Wilson } 7147979480SChris Wilson 7247979480SChris Wilson len = scnprintf(buf, *sz, "\n"); 7347979480SChris Wilson buf += len; 7447979480SChris Wilson *sz -= len; 7547979480SChris Wilson 7647979480SChris Wilson if (p->height) { 7747979480SChris Wilson for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) { 7847979480SChris Wilson buf = __sync_print(__sync_child(p)[i], buf, sz, 7947979480SChris Wilson depth + 1, 8047979480SChris Wilson last << 1 | !!(p->bitmap >> (i + 1)), 8147979480SChris Wilson i); 8247979480SChris Wilson } 8347979480SChris Wilson } 8447979480SChris Wilson 8547979480SChris Wilson return buf; 8647979480SChris Wilson } 8747979480SChris Wilson 8847979480SChris Wilson static bool 8947979480SChris Wilson i915_syncmap_print_to_buf(struct i915_syncmap *p, char *buf, unsigned long sz) 9047979480SChris Wilson { 9147979480SChris Wilson if (!p) 9247979480SChris Wilson return false; 9347979480SChris Wilson 9447979480SChris Wilson while (p->parent) 9547979480SChris Wilson p = p->parent; 9647979480SChris Wilson 9747979480SChris Wilson __sync_print(p, buf, &sz, 0, 1, 0); 9847979480SChris Wilson return true; 9947979480SChris Wilson } 10047979480SChris Wilson 10147979480SChris Wilson static int check_syncmap_free(struct i915_syncmap **sync) 10247979480SChris Wilson { 10347979480SChris Wilson i915_syncmap_free(sync); 10447979480SChris Wilson if (*sync) { 10547979480SChris Wilson pr_err("sync not cleared after free\n"); 10647979480SChris Wilson return -EINVAL; 10747979480SChris Wilson } 10847979480SChris Wilson 10947979480SChris Wilson return 0; 11047979480SChris Wilson } 11147979480SChris Wilson 11247979480SChris Wilson static int dump_syncmap(struct i915_syncmap *sync, int err) 11347979480SChris Wilson { 11447979480SChris Wilson char *buf; 11547979480SChris Wilson 11647979480SChris Wilson if (!err) 11747979480SChris Wilson return check_syncmap_free(&sync); 11847979480SChris Wilson 11947979480SChris Wilson buf = kmalloc(PAGE_SIZE, GFP_KERNEL); 12047979480SChris Wilson if (!buf) 12147979480SChris Wilson goto skip; 12247979480SChris Wilson 12347979480SChris Wilson if (i915_syncmap_print_to_buf(sync, buf, PAGE_SIZE)) 12447979480SChris Wilson pr_err("%s", buf); 12547979480SChris Wilson 12647979480SChris Wilson kfree(buf); 12747979480SChris Wilson 12847979480SChris Wilson skip: 12947979480SChris Wilson i915_syncmap_free(&sync); 13047979480SChris Wilson return err; 13147979480SChris Wilson } 13247979480SChris Wilson 13347979480SChris Wilson static int igt_syncmap_init(void *arg) 13447979480SChris Wilson { 13547979480SChris Wilson struct i915_syncmap *sync = (void *)~0ul; 13647979480SChris Wilson 13747979480SChris Wilson /* 13847979480SChris Wilson * Cursory check that we can initialise a random pointer and transform 13947979480SChris Wilson * it into the root pointer of a syncmap. 14047979480SChris Wilson */ 14147979480SChris Wilson 14247979480SChris Wilson i915_syncmap_init(&sync); 14347979480SChris Wilson return check_syncmap_free(&sync); 14447979480SChris Wilson } 14547979480SChris Wilson 14647979480SChris Wilson static int check_seqno(struct i915_syncmap *leaf, unsigned int idx, u32 seqno) 14747979480SChris Wilson { 14847979480SChris Wilson if (leaf->height) { 14947979480SChris Wilson pr_err("%s: not a leaf, height is %d\n", 15047979480SChris Wilson __func__, leaf->height); 15147979480SChris Wilson return -EINVAL; 15247979480SChris Wilson } 15347979480SChris Wilson 15447979480SChris Wilson if (__sync_seqno(leaf)[idx] != seqno) { 15547979480SChris Wilson pr_err("%s: seqno[%d], found %x, expected %x\n", 15647979480SChris Wilson __func__, idx, __sync_seqno(leaf)[idx], seqno); 15747979480SChris Wilson return -EINVAL; 15847979480SChris Wilson } 15947979480SChris Wilson 16047979480SChris Wilson return 0; 16147979480SChris Wilson } 16247979480SChris Wilson 16347979480SChris Wilson static int check_one(struct i915_syncmap **sync, u64 context, u32 seqno) 16447979480SChris Wilson { 16547979480SChris Wilson int err; 16647979480SChris Wilson 16747979480SChris Wilson err = i915_syncmap_set(sync, context, seqno); 16847979480SChris Wilson if (err) 16947979480SChris Wilson return err; 17047979480SChris Wilson 17147979480SChris Wilson if ((*sync)->height) { 17247979480SChris Wilson pr_err("Inserting first context=%llx did not return leaf (height=%d, prefix=%llx\n", 17347979480SChris Wilson context, (*sync)->height, (*sync)->prefix); 17447979480SChris Wilson return -EINVAL; 17547979480SChris Wilson } 17647979480SChris Wilson 17747979480SChris Wilson if ((*sync)->parent) { 17847979480SChris Wilson pr_err("Inserting first context=%llx created branches!\n", 17947979480SChris Wilson context); 18047979480SChris Wilson return -EINVAL; 18147979480SChris Wilson } 18247979480SChris Wilson 18347979480SChris Wilson if (hweight32((*sync)->bitmap) != 1) { 18447979480SChris Wilson pr_err("First bitmap does not contain a single entry, found %x (count=%d)!\n", 18547979480SChris Wilson (*sync)->bitmap, hweight32((*sync)->bitmap)); 18647979480SChris Wilson return -EINVAL; 18747979480SChris Wilson } 18847979480SChris Wilson 18947979480SChris Wilson err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno); 19047979480SChris Wilson if (err) 19147979480SChris Wilson return err; 19247979480SChris Wilson 19347979480SChris Wilson if (!i915_syncmap_is_later(sync, context, seqno)) { 19447979480SChris Wilson pr_err("Lookup of first context=%llx/seqno=%x failed!\n", 19547979480SChris Wilson context, seqno); 19647979480SChris Wilson return -EINVAL; 19747979480SChris Wilson } 19847979480SChris Wilson 19947979480SChris Wilson return 0; 20047979480SChris Wilson } 20147979480SChris Wilson 20247979480SChris Wilson static int igt_syncmap_one(void *arg) 20347979480SChris Wilson { 20447979480SChris Wilson I915_RND_STATE(prng); 20547979480SChris Wilson IGT_TIMEOUT(end_time); 20647979480SChris Wilson struct i915_syncmap *sync; 20747979480SChris Wilson unsigned long max = 1; 20847979480SChris Wilson int err; 20947979480SChris Wilson 21047979480SChris Wilson /* 21147979480SChris Wilson * Check that inserting a new id, creates a leaf and only that leaf. 21247979480SChris Wilson */ 21347979480SChris Wilson 21447979480SChris Wilson i915_syncmap_init(&sync); 21547979480SChris Wilson 21647979480SChris Wilson do { 21747979480SChris Wilson u64 context = i915_prandom_u64_state(&prng); 21847979480SChris Wilson unsigned long loop; 21947979480SChris Wilson 22047979480SChris Wilson err = check_syncmap_free(&sync); 22147979480SChris Wilson if (err) 22247979480SChris Wilson goto out; 22347979480SChris Wilson 22447979480SChris Wilson for (loop = 0; loop <= max; loop++) { 22547979480SChris Wilson err = check_one(&sync, context, 22647979480SChris Wilson prandom_u32_state(&prng)); 22747979480SChris Wilson if (err) 22847979480SChris Wilson goto out; 22947979480SChris Wilson } 23047979480SChris Wilson max++; 23147979480SChris Wilson } while (!__igt_timeout(end_time, NULL)); 23247979480SChris Wilson pr_debug("%s: Completed %lu single insertions\n", 23347979480SChris Wilson __func__, max * (max - 1) / 2); 23447979480SChris Wilson out: 23547979480SChris Wilson return dump_syncmap(sync, err); 23647979480SChris Wilson } 23747979480SChris Wilson 23847979480SChris Wilson static int check_leaf(struct i915_syncmap **sync, u64 context, u32 seqno) 23947979480SChris Wilson { 24047979480SChris Wilson int err; 24147979480SChris Wilson 24247979480SChris Wilson err = i915_syncmap_set(sync, context, seqno); 24347979480SChris Wilson if (err) 24447979480SChris Wilson return err; 24547979480SChris Wilson 24647979480SChris Wilson if ((*sync)->height) { 24747979480SChris Wilson pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n", 24847979480SChris Wilson context, (*sync)->height, (*sync)->prefix); 24947979480SChris Wilson return -EINVAL; 25047979480SChris Wilson } 25147979480SChris Wilson 25247979480SChris Wilson if (hweight32((*sync)->bitmap) != 1) { 25347979480SChris Wilson pr_err("First entry into leaf (context=%llx) does not contain a single entry, found %x (count=%d)!\n", 25447979480SChris Wilson context, (*sync)->bitmap, hweight32((*sync)->bitmap)); 25547979480SChris Wilson return -EINVAL; 25647979480SChris Wilson } 25747979480SChris Wilson 25847979480SChris Wilson err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno); 25947979480SChris Wilson if (err) 26047979480SChris Wilson return err; 26147979480SChris Wilson 26247979480SChris Wilson if (!i915_syncmap_is_later(sync, context, seqno)) { 26347979480SChris Wilson pr_err("Lookup of first entry context=%llx/seqno=%x failed!\n", 26447979480SChris Wilson context, seqno); 26547979480SChris Wilson return -EINVAL; 26647979480SChris Wilson } 26747979480SChris Wilson 26847979480SChris Wilson return 0; 26947979480SChris Wilson } 27047979480SChris Wilson 27147979480SChris Wilson static int igt_syncmap_join_above(void *arg) 27247979480SChris Wilson { 27347979480SChris Wilson struct i915_syncmap *sync; 27447979480SChris Wilson unsigned int pass, order; 27547979480SChris Wilson int err; 27647979480SChris Wilson 27747979480SChris Wilson i915_syncmap_init(&sync); 27847979480SChris Wilson 27947979480SChris Wilson /* 28047979480SChris Wilson * When we have a new id that doesn't fit inside the existing tree, 28147979480SChris Wilson * we need to add a new layer above. 28247979480SChris Wilson * 28347979480SChris Wilson * 1: 0x00000001 28447979480SChris Wilson * 2: 0x00000010 28547979480SChris Wilson * 3: 0x00000100 28647979480SChris Wilson * 4: 0x00001000 28747979480SChris Wilson * ... 28847979480SChris Wilson * Each pass the common prefix shrinks and we have to insert a join. 28947979480SChris Wilson * Each join will only contain two branches, the latest of which 29047979480SChris Wilson * is always a leaf. 29147979480SChris Wilson * 29247979480SChris Wilson * If we then reuse the same set of contexts, we expect to build an 29347979480SChris Wilson * identical tree. 29447979480SChris Wilson */ 29547979480SChris Wilson for (pass = 0; pass < 3; pass++) { 29647979480SChris Wilson for (order = 0; order < 64; order += SHIFT) { 29747979480SChris Wilson u64 context = BIT_ULL(order); 29847979480SChris Wilson struct i915_syncmap *join; 29947979480SChris Wilson 30047979480SChris Wilson err = check_leaf(&sync, context, 0); 30147979480SChris Wilson if (err) 30247979480SChris Wilson goto out; 30347979480SChris Wilson 30447979480SChris Wilson join = sync->parent; 30547979480SChris Wilson if (!join) /* very first insert will have no parents */ 30647979480SChris Wilson continue; 30747979480SChris Wilson 30847979480SChris Wilson if (!join->height) { 30947979480SChris Wilson pr_err("Parent with no height!\n"); 31047979480SChris Wilson err = -EINVAL; 31147979480SChris Wilson goto out; 31247979480SChris Wilson } 31347979480SChris Wilson 31447979480SChris Wilson if (hweight32(join->bitmap) != 2) { 31547979480SChris Wilson pr_err("Join does not have 2 children: %x (%d)\n", 31647979480SChris Wilson join->bitmap, hweight32(join->bitmap)); 31747979480SChris Wilson err = -EINVAL; 31847979480SChris Wilson goto out; 31947979480SChris Wilson } 32047979480SChris Wilson 32147979480SChris Wilson if (__sync_child(join)[__sync_branch_idx(join, context)] != sync) { 32247979480SChris Wilson pr_err("Leaf misplaced in parent!\n"); 32347979480SChris Wilson err = -EINVAL; 32447979480SChris Wilson goto out; 32547979480SChris Wilson } 32647979480SChris Wilson } 32747979480SChris Wilson } 32847979480SChris Wilson out: 32947979480SChris Wilson return dump_syncmap(sync, err); 33047979480SChris Wilson } 33147979480SChris Wilson 33247979480SChris Wilson static int igt_syncmap_join_below(void *arg) 33347979480SChris Wilson { 33447979480SChris Wilson struct i915_syncmap *sync; 33547979480SChris Wilson unsigned int step, order, idx; 33647979480SChris Wilson int err; 33747979480SChris Wilson 33847979480SChris Wilson i915_syncmap_init(&sync); 33947979480SChris Wilson 34047979480SChris Wilson /* 34147979480SChris Wilson * Check that we can split a compacted branch by replacing it with 34247979480SChris Wilson * a join. 34347979480SChris Wilson */ 34447979480SChris Wilson for (step = 0; step < KSYNCMAP; step++) { 34547979480SChris Wilson for (order = 64 - SHIFT; order > 0; order -= SHIFT) { 34647979480SChris Wilson u64 context = step * BIT_ULL(order); 34747979480SChris Wilson 34847979480SChris Wilson err = i915_syncmap_set(&sync, context, 0); 34947979480SChris Wilson if (err) 35047979480SChris Wilson goto out; 35147979480SChris Wilson 35247979480SChris Wilson if (sync->height) { 35347979480SChris Wilson pr_err("Inserting context=%llx (order=%d, step=%d) did not return leaf (height=%d, prefix=%llx\n", 35447979480SChris Wilson context, order, step, sync->height, sync->prefix); 35547979480SChris Wilson err = -EINVAL; 35647979480SChris Wilson goto out; 35747979480SChris Wilson } 35847979480SChris Wilson } 35947979480SChris Wilson } 36047979480SChris Wilson 36147979480SChris Wilson for (step = 0; step < KSYNCMAP; step++) { 36247979480SChris Wilson for (order = SHIFT; order < 64; order += SHIFT) { 36347979480SChris Wilson u64 context = step * BIT_ULL(order); 36447979480SChris Wilson 36547979480SChris Wilson if (!i915_syncmap_is_later(&sync, context, 0)) { 36647979480SChris Wilson pr_err("1: context %llx (order=%d, step=%d) not found\n", 36747979480SChris Wilson context, order, step); 36847979480SChris Wilson err = -EINVAL; 36947979480SChris Wilson goto out; 37047979480SChris Wilson } 37147979480SChris Wilson 37247979480SChris Wilson for (idx = 1; idx < KSYNCMAP; idx++) { 37347979480SChris Wilson if (i915_syncmap_is_later(&sync, context + idx, 0)) { 37447979480SChris Wilson pr_err("1: context %llx (order=%d, step=%d) should not exist\n", 37547979480SChris Wilson context + idx, order, step); 37647979480SChris Wilson err = -EINVAL; 37747979480SChris Wilson goto out; 37847979480SChris Wilson } 37947979480SChris Wilson } 38047979480SChris Wilson } 38147979480SChris Wilson } 38247979480SChris Wilson 38347979480SChris Wilson for (order = SHIFT; order < 64; order += SHIFT) { 38447979480SChris Wilson for (step = 0; step < KSYNCMAP; step++) { 38547979480SChris Wilson u64 context = step * BIT_ULL(order); 38647979480SChris Wilson 38747979480SChris Wilson if (!i915_syncmap_is_later(&sync, context, 0)) { 38847979480SChris Wilson pr_err("2: context %llx (order=%d, step=%d) not found\n", 38947979480SChris Wilson context, order, step); 39047979480SChris Wilson err = -EINVAL; 39147979480SChris Wilson goto out; 39247979480SChris Wilson } 39347979480SChris Wilson } 39447979480SChris Wilson } 39547979480SChris Wilson 39647979480SChris Wilson out: 39747979480SChris Wilson return dump_syncmap(sync, err); 39847979480SChris Wilson } 39947979480SChris Wilson 40047979480SChris Wilson static int igt_syncmap_neighbours(void *arg) 40147979480SChris Wilson { 40247979480SChris Wilson I915_RND_STATE(prng); 40347979480SChris Wilson IGT_TIMEOUT(end_time); 40447979480SChris Wilson struct i915_syncmap *sync; 40547979480SChris Wilson int err; 40647979480SChris Wilson 40747979480SChris Wilson /* 40847979480SChris Wilson * Each leaf holds KSYNCMAP seqno. Check that when we create KSYNCMAP 40947979480SChris Wilson * neighbouring ids, they all fit into the same leaf. 41047979480SChris Wilson */ 41147979480SChris Wilson 41247979480SChris Wilson i915_syncmap_init(&sync); 41347979480SChris Wilson do { 41447979480SChris Wilson u64 context = i915_prandom_u64_state(&prng) & ~MASK; 41547979480SChris Wilson unsigned int idx; 41647979480SChris Wilson 41747979480SChris Wilson if (i915_syncmap_is_later(&sync, context, 0)) /* Skip repeats */ 41847979480SChris Wilson continue; 41947979480SChris Wilson 42047979480SChris Wilson for (idx = 0; idx < KSYNCMAP; idx++) { 42147979480SChris Wilson err = i915_syncmap_set(&sync, context + idx, 0); 42247979480SChris Wilson if (err) 42347979480SChris Wilson goto out; 42447979480SChris Wilson 42547979480SChris Wilson if (sync->height) { 42647979480SChris Wilson pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n", 42747979480SChris Wilson context, sync->height, sync->prefix); 42847979480SChris Wilson err = -EINVAL; 42947979480SChris Wilson goto out; 43047979480SChris Wilson } 43147979480SChris Wilson 43247979480SChris Wilson if (sync->bitmap != BIT(idx + 1) - 1) { 43347979480SChris Wilson pr_err("Inserting neighbouring context=0x%llx+%d, did not fit into the same leaf bitmap=%x (%d), expected %lx (%d)\n", 43447979480SChris Wilson context, idx, 43547979480SChris Wilson sync->bitmap, hweight32(sync->bitmap), 43647979480SChris Wilson BIT(idx + 1) - 1, idx + 1); 43747979480SChris Wilson err = -EINVAL; 43847979480SChris Wilson goto out; 43947979480SChris Wilson } 44047979480SChris Wilson } 44147979480SChris Wilson } while (!__igt_timeout(end_time, NULL)); 44247979480SChris Wilson out: 44347979480SChris Wilson return dump_syncmap(sync, err); 44447979480SChris Wilson } 44547979480SChris Wilson 44647979480SChris Wilson static int igt_syncmap_compact(void *arg) 44747979480SChris Wilson { 44847979480SChris Wilson struct i915_syncmap *sync; 44947979480SChris Wilson unsigned int idx, order; 45047979480SChris Wilson int err; 45147979480SChris Wilson 45247979480SChris Wilson i915_syncmap_init(&sync); 45347979480SChris Wilson 45447979480SChris Wilson /* 45547979480SChris Wilson * The syncmap are "space efficient" compressed radix trees - any 45647979480SChris Wilson * branch with only one child is skipped and replaced by the child. 45747979480SChris Wilson * 45847979480SChris Wilson * If we construct a tree with ids that are neighbouring at a non-zero 45947979480SChris Wilson * height, we form a join but each child of that join is directly a 46047979480SChris Wilson * leaf holding the single id. 46147979480SChris Wilson */ 46247979480SChris Wilson for (order = SHIFT; order < 64; order += SHIFT) { 46347979480SChris Wilson err = check_syncmap_free(&sync); 46447979480SChris Wilson if (err) 46547979480SChris Wilson goto out; 46647979480SChris Wilson 46747979480SChris Wilson /* Create neighbours in the parent */ 46847979480SChris Wilson for (idx = 0; idx < KSYNCMAP; idx++) { 46947979480SChris Wilson u64 context = idx * BIT_ULL(order) + idx; 47047979480SChris Wilson 47147979480SChris Wilson err = i915_syncmap_set(&sync, context, 0); 47247979480SChris Wilson if (err) 47347979480SChris Wilson goto out; 47447979480SChris Wilson 47547979480SChris Wilson if (sync->height) { 47647979480SChris Wilson pr_err("Inserting context=%llx (order=%d, idx=%d) did not return leaf (height=%d, prefix=%llx\n", 47747979480SChris Wilson context, order, idx, 47847979480SChris Wilson sync->height, sync->prefix); 47947979480SChris Wilson err = -EINVAL; 48047979480SChris Wilson goto out; 48147979480SChris Wilson } 48247979480SChris Wilson } 48347979480SChris Wilson 48447979480SChris Wilson sync = sync->parent; 48547979480SChris Wilson if (sync->parent) { 48647979480SChris Wilson pr_err("Parent (join) of last leaf was not the sync!\n"); 48747979480SChris Wilson err = -EINVAL; 48847979480SChris Wilson goto out; 48947979480SChris Wilson } 49047979480SChris Wilson 49147979480SChris Wilson if (sync->height != order) { 49247979480SChris Wilson pr_err("Join does not have the expected height, found %d, expected %d\n", 49347979480SChris Wilson sync->height, order); 49447979480SChris Wilson err = -EINVAL; 49547979480SChris Wilson goto out; 49647979480SChris Wilson } 49747979480SChris Wilson 49847979480SChris Wilson if (sync->bitmap != BIT(KSYNCMAP) - 1) { 49947979480SChris Wilson pr_err("Join is not full!, found %x (%d) expected %lx (%d)\n", 50047979480SChris Wilson sync->bitmap, hweight32(sync->bitmap), 50147979480SChris Wilson BIT(KSYNCMAP) - 1, KSYNCMAP); 50247979480SChris Wilson err = -EINVAL; 50347979480SChris Wilson goto out; 50447979480SChris Wilson } 50547979480SChris Wilson 50647979480SChris Wilson /* Each of our children should be a leaf */ 50747979480SChris Wilson for (idx = 0; idx < KSYNCMAP; idx++) { 50847979480SChris Wilson struct i915_syncmap *leaf = __sync_child(sync)[idx]; 50947979480SChris Wilson 51047979480SChris Wilson if (leaf->height) { 51147979480SChris Wilson pr_err("Child %d is a not leaf!\n", idx); 51247979480SChris Wilson err = -EINVAL; 51347979480SChris Wilson goto out; 51447979480SChris Wilson } 51547979480SChris Wilson 51647979480SChris Wilson if (leaf->parent != sync) { 51747979480SChris Wilson pr_err("Child %d is not attached to us!\n", 51847979480SChris Wilson idx); 51947979480SChris Wilson err = -EINVAL; 52047979480SChris Wilson goto out; 52147979480SChris Wilson } 52247979480SChris Wilson 52347979480SChris Wilson if (!is_power_of_2(leaf->bitmap)) { 52447979480SChris Wilson pr_err("Child %d holds more than one id, found %x (%d)\n", 52547979480SChris Wilson idx, leaf->bitmap, hweight32(leaf->bitmap)); 52647979480SChris Wilson err = -EINVAL; 52747979480SChris Wilson goto out; 52847979480SChris Wilson } 52947979480SChris Wilson 53047979480SChris Wilson if (leaf->bitmap != BIT(idx)) { 53147979480SChris Wilson pr_err("Child %d has wrong seqno idx, found %d, expected %d\n", 53247979480SChris Wilson idx, ilog2(leaf->bitmap), idx); 53347979480SChris Wilson err = -EINVAL; 53447979480SChris Wilson goto out; 53547979480SChris Wilson } 53647979480SChris Wilson } 53747979480SChris Wilson } 53847979480SChris Wilson out: 53947979480SChris Wilson return dump_syncmap(sync, err); 54047979480SChris Wilson } 54147979480SChris Wilson 54247979480SChris Wilson static int igt_syncmap_random(void *arg) 54347979480SChris Wilson { 54447979480SChris Wilson I915_RND_STATE(prng); 54547979480SChris Wilson IGT_TIMEOUT(end_time); 54647979480SChris Wilson struct i915_syncmap *sync; 54747979480SChris Wilson unsigned long count, phase, i; 54847979480SChris Wilson u32 seqno; 54947979480SChris Wilson int err; 55047979480SChris Wilson 55147979480SChris Wilson i915_syncmap_init(&sync); 55247979480SChris Wilson 55347979480SChris Wilson /* 55447979480SChris Wilson * Having tried to test the individual operations within i915_syncmap, 55547979480SChris Wilson * run a smoketest exploring the entire u64 space with random 55647979480SChris Wilson * insertions. 55747979480SChris Wilson */ 55847979480SChris Wilson 55947979480SChris Wilson count = 0; 56047979480SChris Wilson phase = jiffies + HZ/100 + 1; 56147979480SChris Wilson do { 56247979480SChris Wilson u64 context = i915_prandom_u64_state(&prng); 56347979480SChris Wilson 56447979480SChris Wilson err = i915_syncmap_set(&sync, context, 0); 56547979480SChris Wilson if (err) 56647979480SChris Wilson goto out; 56747979480SChris Wilson 56847979480SChris Wilson count++; 56947979480SChris Wilson } while (!time_after(jiffies, phase)); 57047979480SChris Wilson seqno = 0; 57147979480SChris Wilson 57247979480SChris Wilson phase = 0; 57347979480SChris Wilson do { 57447979480SChris Wilson I915_RND_STATE(ctx); 57547979480SChris Wilson u32 last_seqno = seqno; 57647979480SChris Wilson bool expect; 57747979480SChris Wilson 57847979480SChris Wilson seqno = prandom_u32_state(&prng); 57947979480SChris Wilson expect = seqno_later(last_seqno, seqno); 58047979480SChris Wilson 58147979480SChris Wilson for (i = 0; i < count; i++) { 58247979480SChris Wilson u64 context = i915_prandom_u64_state(&ctx); 58347979480SChris Wilson 58447979480SChris Wilson if (i915_syncmap_is_later(&sync, context, seqno) != expect) { 58547979480SChris Wilson pr_err("context=%llu, last=%u this=%u did not match expectation (%d)\n", 58647979480SChris Wilson context, last_seqno, seqno, expect); 58747979480SChris Wilson err = -EINVAL; 58847979480SChris Wilson goto out; 58947979480SChris Wilson } 59047979480SChris Wilson 59147979480SChris Wilson err = i915_syncmap_set(&sync, context, seqno); 59247979480SChris Wilson if (err) 59347979480SChris Wilson goto out; 59447979480SChris Wilson } 59547979480SChris Wilson 59647979480SChris Wilson phase++; 59747979480SChris Wilson } while (!__igt_timeout(end_time, NULL)); 59847979480SChris Wilson pr_debug("Completed %lu passes, each of %lu contexts\n", phase, count); 59947979480SChris Wilson out: 60047979480SChris Wilson return dump_syncmap(sync, err); 60147979480SChris Wilson } 60247979480SChris Wilson 60347979480SChris Wilson int i915_syncmap_mock_selftests(void) 60447979480SChris Wilson { 60547979480SChris Wilson static const struct i915_subtest tests[] = { 60647979480SChris Wilson SUBTEST(igt_syncmap_init), 60747979480SChris Wilson SUBTEST(igt_syncmap_one), 60847979480SChris Wilson SUBTEST(igt_syncmap_join_above), 60947979480SChris Wilson SUBTEST(igt_syncmap_join_below), 61047979480SChris Wilson SUBTEST(igt_syncmap_neighbours), 61147979480SChris Wilson SUBTEST(igt_syncmap_compact), 61247979480SChris Wilson SUBTEST(igt_syncmap_random), 61347979480SChris Wilson }; 61447979480SChris Wilson 61547979480SChris Wilson return i915_subtests(tests, NULL); 61647979480SChris Wilson } 617