drivers/gpu/drm/i915/selftests/i915_syncmap.c

   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 }