617 lines · c
1/*2 * Copyright © 2017 Intel Corporation3 *4 * Permission is hereby granted, free of charge, to any person obtaining a5 * copy of this software and associated documentation files (the "Software"),6 * to deal in the Software without restriction, including without limitation7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,8 * and/or sell copies of the Software, and to permit persons to whom the9 * Software is furnished to do so, subject to the following conditions:10 *11 * The above copyright notice and this permission notice (including the next12 * paragraph) shall be included in all copies or substantial portions of the13 * Software.14 *15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS21 * 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 else45 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 bool89i915_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 transform139 * 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: 0x00000001284 * 2: 0x00000010285 * 3: 0x00000100286 * 4: 0x00001000287 * ...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 which290 * is always a leaf.291 *292 * If we then reuse the same set of contexts, we expect to build an293 * 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 with342 * 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 KSYNCMAP409 * 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 - any456 * 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-zero459 * height, we form a join but each child of that join is directly a460 * 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 random556 * 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