i915/selftests/i915_syncmap.c

0001 /*
0002  * Copyright © 2017 Intel Corporation
0003  *
0004  * Permission is hereby granted, free of charge, to any person obtaining a
0005  * copy of this software and associated documentation files (the "Software"),
0006  * to deal in the Software without restriction, including without limitation
0007  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
0008  * and/or sell copies of the Software, and to permit persons to whom the
0009  * Software is furnished to do so, subject to the following conditions:
0010  *
0011  * The above copyright notice and this permission notice (including the next
0012  * paragraph) shall be included in all copies or substantial portions of the
0013  * Software.
0014  *
0015  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0016  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0017  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
0018  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0019  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
0020  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
0021  * IN THE SOFTWARE.
0022  *
0023  */
0024
0025 #include "../i915_selftest.h"
0026 #include "i915_random.h"
0027
0028 static char *
0029 __sync_print(struct i915_syncmap *p,
0030          char *buf, unsigned long *sz,
0031          unsigned int depth,
0032          unsigned int last,
0033          unsigned int idx)
0034 {
0035     unsigned long len;
0036     unsigned int i, X;
0037
0038     if (depth) {
0039         unsigned int d;
0040
0041         for (d = 0; d < depth - 1; d++) {
0042             if (last & BIT(depth - d - 1))
0043                 len = scnprintf(buf, *sz, "|   ");
0044             else
0045                 len = scnprintf(buf, *sz, "    ");
0046             buf += len;
0047             *sz -= len;
0048         }
0049         len = scnprintf(buf, *sz, "%x-> ", idx);
0050         buf += len;
0051         *sz -= len;
0052     }
0053
0054     /* We mark bits after the prefix as "X" */
0055     len = scnprintf(buf, *sz, "0x%016llx", p->prefix << p->height << SHIFT);
0056     buf += len;
0057     *sz -= len;
0058     X = (p->height + SHIFT) / 4;
0059     scnprintf(buf - X, *sz + X, "%*s", X, "XXXXXXXXXXXXXXXXX");
0060
0061     if (!p->height) {
0062         for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
0063             len = scnprintf(buf, *sz, " %x:%x,",
0064                     i, __sync_seqno(p)[i]);
0065             buf += len;
0066             *sz -= len;
0067         }
0068         buf -= 1;
0069         *sz += 1;
0070     }
0071
0072     len = scnprintf(buf, *sz, "\n");
0073     buf += len;
0074     *sz -= len;
0075
0076     if (p->height) {
0077         for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
0078             buf = __sync_print(__sync_child(p)[i], buf, sz,
0079                        depth + 1,
0080                        last << 1 | !!(p->bitmap >> (i + 1)),
0081                        i);
0082         }
0083     }
0084
0085     return buf;
0086 }
0087
0088 static bool
0089 i915_syncmap_print_to_buf(struct i915_syncmap *p, char *buf, unsigned long sz)
0090 {
0091     if (!p)
0092         return false;
0093
0094     while (p->parent)
0095         p = p->parent;
0096
0097     __sync_print(p, buf, &sz, 0, 1, 0);
0098     return true;
0099 }
0100
0101 static int check_syncmap_free(struct i915_syncmap **sync)
0102 {
0103     i915_syncmap_free(sync);
0104     if (*sync) {
0105         pr_err("sync not cleared after free\n");
0106         return -EINVAL;
0107     }
0108
0109     return 0;
0110 }
0111
0112 static int dump_syncmap(struct i915_syncmap *sync, int err)
0113 {
0114     char *buf;
0115
0116     if (!err)
0117         return check_syncmap_free(&sync);
0118
0119     buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
0120     if (!buf)
0121         goto skip;
0122
0123     if (i915_syncmap_print_to_buf(sync, buf, PAGE_SIZE))
0124         pr_err("%s", buf);
0125
0126     kfree(buf);
0127
0128 skip:
0129     i915_syncmap_free(&sync);
0130     return err;
0131 }
0132
0133 static int igt_syncmap_init(void *arg)
0134 {
0135     struct i915_syncmap *sync = (void *)~0ul;
0136
0137     /*
0138      * Cursory check that we can initialise a random pointer and transform
0139      * it into the root pointer of a syncmap.
0140      */
0141
0142     i915_syncmap_init(&sync);
0143     return check_syncmap_free(&sync);
0144 }
0145
0146 static int check_seqno(struct i915_syncmap *leaf, unsigned int idx, u32 seqno)
0147 {
0148     if (leaf->height) {
0149         pr_err("%s: not a leaf, height is %d\n",
0150                __func__, leaf->height);
0151         return -EINVAL;
0152     }
0153
0154     if (__sync_seqno(leaf)[idx] != seqno) {
0155         pr_err("%s: seqno[%d], found %x, expected %x\n",
0156                __func__, idx, __sync_seqno(leaf)[idx], seqno);
0157         return -EINVAL;
0158     }
0159
0160     return 0;
0161 }
0162
0163 static int check_one(struct i915_syncmap **sync, u64 context, u32 seqno)
0164 {
0165     int err;
0166
0167     err = i915_syncmap_set(sync, context, seqno);
0168     if (err)
0169         return err;
0170
0171     if ((*sync)->height) {
0172         pr_err("Inserting first context=%llx did not return leaf (height=%d, prefix=%llx\n",
0173                context, (*sync)->height, (*sync)->prefix);
0174         return -EINVAL;
0175     }
0176
0177     if ((*sync)->parent) {
0178         pr_err("Inserting first context=%llx created branches!\n",
0179                context);
0180         return -EINVAL;
0181     }
0182
0183     if (hweight32((*sync)->bitmap) != 1) {
0184         pr_err("First bitmap does not contain a single entry, found %x (count=%d)!\n",
0185                (*sync)->bitmap, hweight32((*sync)->bitmap));
0186         return -EINVAL;
0187     }
0188
0189     err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno);
0190     if (err)
0191         return err;
0192
0193     if (!i915_syncmap_is_later(sync, context, seqno)) {
0194         pr_err("Lookup of first context=%llx/seqno=%x failed!\n",
0195                context, seqno);
0196         return -EINVAL;
0197     }
0198
0199     return 0;
0200 }
0201
0202 static int igt_syncmap_one(void *arg)
0203 {
0204     I915_RND_STATE(prng);
0205     IGT_TIMEOUT(end_time);
0206     struct i915_syncmap *sync;
0207     unsigned long max = 1;
0208     int err;
0209
0210     /*
0211      * Check that inserting a new id, creates a leaf and only that leaf.
0212      */
0213
0214     i915_syncmap_init(&sync);
0215
0216     do {
0217         u64 context = i915_prandom_u64_state(&prng);
0218         unsigned long loop;
0219
0220         err = check_syncmap_free(&sync);
0221         if (err)
0222             goto out;
0223
0224         for (loop = 0; loop <= max; loop++) {
0225             err = check_one(&sync, context,
0226                     prandom_u32_state(&prng));
0227             if (err)
0228                 goto out;
0229         }
0230         max++;
0231     } while (!__igt_timeout(end_time, NULL));
0232     pr_debug("%s: Completed %lu single insertions\n",
0233          __func__, max * (max - 1) / 2);
0234 out:
0235     return dump_syncmap(sync, err);
0236 }
0237
0238 static int check_leaf(struct i915_syncmap **sync, u64 context, u32 seqno)
0239 {
0240     int err;
0241
0242     err = i915_syncmap_set(sync, context, seqno);
0243     if (err)
0244         return err;
0245
0246     if ((*sync)->height) {
0247         pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n",
0248                context, (*sync)->height, (*sync)->prefix);
0249         return -EINVAL;
0250     }
0251
0252     if (hweight32((*sync)->bitmap) != 1) {
0253         pr_err("First entry into leaf (context=%llx) does not contain a single entry, found %x (count=%d)!\n",
0254                context, (*sync)->bitmap, hweight32((*sync)->bitmap));
0255         return -EINVAL;
0256     }
0257
0258     err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno);
0259     if (err)
0260         return err;
0261
0262     if (!i915_syncmap_is_later(sync, context, seqno)) {
0263         pr_err("Lookup of first entry context=%llx/seqno=%x failed!\n",
0264                context, seqno);
0265         return -EINVAL;
0266     }
0267
0268     return 0;
0269 }
0270
0271 static int igt_syncmap_join_above(void *arg)
0272 {
0273     struct i915_syncmap *sync;
0274     unsigned int pass, order;
0275     int err;
0276
0277     i915_syncmap_init(&sync);
0278
0279     /*
0280      * When we have a new id that doesn't fit inside the existing tree,
0281      * we need to add a new layer above.
0282      *
0283      * 1: 0x00000001
0284      * 2: 0x00000010
0285      * 3: 0x00000100
0286      * 4: 0x00001000
0287      * ...
0288      * Each pass the common prefix shrinks and we have to insert a join.
0289      * Each join will only contain two branches, the latest of which
0290      * is always a leaf.
0291      *
0292      * If we then reuse the same set of contexts, we expect to build an
0293      * identical tree.
0294      */
0295     for (pass = 0; pass < 3; pass++) {
0296         for (order = 0; order < 64; order += SHIFT) {
0297             u64 context = BIT_ULL(order);
0298             struct i915_syncmap *join;
0299
0300             err = check_leaf(&sync, context, 0);
0301             if (err)
0302                 goto out;
0303
0304             join = sync->parent;
0305             if (!join) /* very first insert will have no parents */
0306                 continue;
0307
0308             if (!join->height) {
0309                 pr_err("Parent with no height!\n");
0310                 err = -EINVAL;
0311                 goto out;
0312             }
0313
0314             if (hweight32(join->bitmap) != 2) {
0315                 pr_err("Join does not have 2 children: %x (%d)\n",
0316                        join->bitmap, hweight32(join->bitmap));
0317                 err = -EINVAL;
0318                 goto out;
0319             }
0320
0321             if (__sync_child(join)[__sync_branch_idx(join, context)] != sync) {
0322                 pr_err("Leaf misplaced in parent!\n");
0323                 err = -EINVAL;
0324                 goto out;
0325             }
0326         }
0327     }
0328 out:
0329     return dump_syncmap(sync, err);
0330 }
0331
0332 static int igt_syncmap_join_below(void *arg)
0333 {
0334     struct i915_syncmap *sync;
0335     unsigned int step, order, idx;
0336     int err = -ENODEV;
0337
0338     i915_syncmap_init(&sync);
0339
0340     /*
0341      * Check that we can split a compacted branch by replacing it with
0342      * a join.
0343      */
0344     for (step = 0; step < KSYNCMAP; step++) {
0345         for (order = 64 - SHIFT; order > 0; order -= SHIFT) {
0346             u64 context = step * BIT_ULL(order);
0347
0348             err = i915_syncmap_set(&sync, context, 0);
0349             if (err)
0350                 goto out;
0351
0352             if (sync->height) {
0353                 pr_err("Inserting context=%llx (order=%d, step=%d) did not return leaf (height=%d, prefix=%llx\n",
0354                        context, order, step, sync->height, sync->prefix);
0355                 err = -EINVAL;
0356                 goto out;
0357             }
0358         }
0359     }
0360
0361     for (step = 0; step < KSYNCMAP; step++) {
0362         for (order = SHIFT; order < 64; order += SHIFT) {
0363             u64 context = step * BIT_ULL(order);
0364
0365             if (!i915_syncmap_is_later(&sync, context, 0)) {
0366                 pr_err("1: context %llx (order=%d, step=%d) not found\n",
0367                        context, order, step);
0368                 err = -EINVAL;
0369                 goto out;
0370             }
0371
0372             for (idx = 1; idx < KSYNCMAP; idx++) {
0373                 if (i915_syncmap_is_later(&sync, context + idx, 0)) {
0374                     pr_err("1: context %llx (order=%d, step=%d) should not exist\n",
0375                            context + idx, order, step);
0376                     err = -EINVAL;
0377                     goto out;
0378                 }
0379             }
0380         }
0381     }
0382
0383     for (order = SHIFT; order < 64; order += SHIFT) {
0384         for (step = 0; step < KSYNCMAP; step++) {
0385             u64 context = step * BIT_ULL(order);
0386
0387             if (!i915_syncmap_is_later(&sync, context, 0)) {
0388                 pr_err("2: context %llx (order=%d, step=%d) not found\n",
0389                        context, order, step);
0390                 err = -EINVAL;
0391                 goto out;
0392             }
0393         }
0394     }
0395
0396 out:
0397     return dump_syncmap(sync, err);
0398 }
0399
0400 static int igt_syncmap_neighbours(void *arg)
0401 {
0402     I915_RND_STATE(prng);
0403     IGT_TIMEOUT(end_time);
0404     struct i915_syncmap *sync;
0405     int err = -ENODEV;
0406
0407     /*
0408      * Each leaf holds KSYNCMAP seqno. Check that when we create KSYNCMAP
0409      * neighbouring ids, they all fit into the same leaf.
0410      */
0411
0412     i915_syncmap_init(&sync);
0413     do {
0414         u64 context = i915_prandom_u64_state(&prng) & ~MASK;
0415         unsigned int idx;
0416
0417         if (i915_syncmap_is_later(&sync, context, 0)) /* Skip repeats */
0418             continue;
0419
0420         for (idx = 0; idx < KSYNCMAP; idx++) {
0421             err = i915_syncmap_set(&sync, context + idx, 0);
0422             if (err)
0423                 goto out;
0424
0425             if (sync->height) {
0426                 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n",
0427                        context, sync->height, sync->prefix);
0428                 err = -EINVAL;
0429                 goto out;
0430             }
0431
0432             if (sync->bitmap != BIT(idx + 1) - 1) {
0433                 pr_err("Inserting neighbouring context=0x%llx+%d, did not fit into the same leaf bitmap=%x (%d), expected %lx (%d)\n",
0434                        context, idx,
0435                        sync->bitmap, hweight32(sync->bitmap),
0436                        BIT(idx + 1) - 1, idx + 1);
0437                 err = -EINVAL;
0438                 goto out;
0439             }
0440         }
0441     } while (!__igt_timeout(end_time, NULL));
0442 out:
0443     return dump_syncmap(sync, err);
0444 }
0445
0446 static int igt_syncmap_compact(void *arg)
0447 {
0448     struct i915_syncmap *sync;
0449     unsigned int idx, order;
0450     int err = -ENODEV;
0451
0452     i915_syncmap_init(&sync);
0453
0454     /*
0455      * The syncmap are "space efficient" compressed radix trees - any
0456      * branch with only one child is skipped and replaced by the child.
0457      *
0458      * If we construct a tree with ids that are neighbouring at a non-zero
0459      * height, we form a join but each child of that join is directly a
0460      * leaf holding the single id.
0461      */
0462     for (order = SHIFT; order < 64; order += SHIFT) {
0463         err = check_syncmap_free(&sync);
0464         if (err)
0465             goto out;
0466
0467         /* Create neighbours in the parent */
0468         for (idx = 0; idx < KSYNCMAP; idx++) {
0469             u64 context = idx * BIT_ULL(order) + idx;
0470
0471             err = i915_syncmap_set(&sync, context, 0);
0472             if (err)
0473                 goto out;
0474
0475             if (sync->height) {
0476                 pr_err("Inserting context=%llx (order=%d, idx=%d) did not return leaf (height=%d, prefix=%llx\n",
0477                        context, order, idx,
0478                        sync->height, sync->prefix);
0479                 err = -EINVAL;
0480                 goto out;
0481             }
0482         }
0483
0484         sync = sync->parent;
0485         if (sync->parent) {
0486             pr_err("Parent (join) of last leaf was not the sync!\n");
0487             err = -EINVAL;
0488             goto out;
0489         }
0490
0491         if (sync->height != order) {
0492             pr_err("Join does not have the expected height, found %d, expected %d\n",
0493                    sync->height, order);
0494             err = -EINVAL;
0495             goto out;
0496         }
0497
0498         if (sync->bitmap != BIT(KSYNCMAP) - 1) {
0499             pr_err("Join is not full!, found %x (%d) expected %lx (%d)\n",
0500                    sync->bitmap, hweight32(sync->bitmap),
0501                    BIT(KSYNCMAP) - 1, KSYNCMAP);
0502             err = -EINVAL;
0503             goto out;
0504         }
0505
0506         /* Each of our children should be a leaf */
0507         for (idx = 0; idx < KSYNCMAP; idx++) {
0508             struct i915_syncmap *leaf = __sync_child(sync)[idx];
0509
0510             if (leaf->height) {
0511                 pr_err("Child %d is a not leaf!\n", idx);
0512                 err = -EINVAL;
0513                 goto out;
0514             }
0515
0516             if (leaf->parent != sync) {
0517                 pr_err("Child %d is not attached to us!\n",
0518                        idx);
0519                 err = -EINVAL;
0520                 goto out;
0521             }
0522
0523             if (!is_power_of_2(leaf->bitmap)) {
0524                 pr_err("Child %d holds more than one id, found %x (%d)\n",
0525                        idx, leaf->bitmap, hweight32(leaf->bitmap));
0526                 err = -EINVAL;
0527                 goto out;
0528             }
0529
0530             if (leaf->bitmap != BIT(idx)) {
0531                 pr_err("Child %d has wrong seqno idx, found %d, expected %d\n",
0532                        idx, ilog2(leaf->bitmap), idx);
0533                 err = -EINVAL;
0534                 goto out;
0535             }
0536         }
0537     }
0538 out:
0539     return dump_syncmap(sync, err);
0540 }
0541
0542 static int igt_syncmap_random(void *arg)
0543 {
0544     I915_RND_STATE(prng);
0545     IGT_TIMEOUT(end_time);
0546     struct i915_syncmap *sync;
0547     unsigned long count, phase, i;
0548     u32 seqno;
0549     int err;
0550
0551     i915_syncmap_init(&sync);
0552
0553     /*
0554      * Having tried to test the individual operations within i915_syncmap,
0555      * run a smoketest exploring the entire u64 space with random
0556      * insertions.
0557      */
0558
0559     count = 0;
0560     phase = jiffies + HZ/100 + 1;
0561     do {
0562         u64 context = i915_prandom_u64_state(&prng);
0563
0564         err = i915_syncmap_set(&sync, context, 0);
0565         if (err)
0566             goto out;
0567
0568         count++;
0569     } while (!time_after(jiffies, phase));
0570     seqno = 0;
0571
0572     phase = 0;
0573     do {
0574         I915_RND_STATE(ctx);
0575         u32 last_seqno = seqno;
0576         bool expect;
0577
0578         seqno = prandom_u32_state(&prng);
0579         expect = seqno_later(last_seqno, seqno);
0580
0581         for (i = 0; i < count; i++) {
0582             u64 context = i915_prandom_u64_state(&ctx);
0583
0584             if (i915_syncmap_is_later(&sync, context, seqno) != expect) {
0585                 pr_err("context=%llu, last=%u this=%u did not match expectation (%d)\n",
0586                        context, last_seqno, seqno, expect);
0587                 err = -EINVAL;
0588                 goto out;
0589             }
0590
0591             err = i915_syncmap_set(&sync, context, seqno);
0592             if (err)
0593                 goto out;
0594         }
0595
0596         phase++;
0597     } while (!__igt_timeout(end_time, NULL));
0598     pr_debug("Completed %lu passes, each of %lu contexts\n", phase, count);
0599 out:
0600     return dump_syncmap(sync, err);
0601 }
0602
0603 int i915_syncmap_mock_selftests(void)
0604 {
0605     static const struct i915_subtest tests[] = {
0606         SUBTEST(igt_syncmap_init),
0607         SUBTEST(igt_syncmap_one),
0608         SUBTEST(igt_syncmap_join_above),
0609         SUBTEST(igt_syncmap_join_below),
0610         SUBTEST(igt_syncmap_neighbours),
0611         SUBTEST(igt_syncmap_compact),
0612         SUBTEST(igt_syncmap_random),
0613     };
0614
0615     return i915_subtests(tests, NULL);
0616 }