1 /* $NetBSD: i915_syncmap.c,v 1.2 2021/12/18 23:45:31 riastradh Exp $ */ 2 3 /* 4 * Copyright 2017 Intel Corporation 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the "Software"), 8 * to deal in the Software without restriction, including without limitation 9 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 10 * and/or sell copies of the Software, and to permit persons to whom the 11 * Software is furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice (including the next 14 * paragraph) shall be included in all copies or substantial portions of the 15 * Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 22 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 23 * IN THE SOFTWARE. 24 * 25 */ 26 27 #include <sys/cdefs.h> 28 __KERNEL_RCSID(0, "$NetBSD: i915_syncmap.c,v 1.2 2021/12/18 23:45:31 riastradh Exp $"); 29 30 #include "../i915_selftest.h" 31 #include "i915_random.h" 32 33 static char * 34 __sync_print(struct i915_syncmap *p, 35 char *buf, unsigned long *sz, 36 unsigned int depth, 37 unsigned int last, 38 unsigned int idx) 39 { 40 unsigned long len; 41 unsigned int i, X; 42 43 if (depth) { 44 unsigned int d; 45 46 for (d = 0; d < depth - 1; d++) { 47 if (last & BIT(depth - d - 1)) 48 len = scnprintf(buf, *sz, "| "); 49 else 50 len = scnprintf(buf, *sz, " "); 51 buf += len; 52 *sz -= len; 53 } 54 len = scnprintf(buf, *sz, "%x-> ", idx); 55 buf += len; 56 *sz -= len; 57 } 58 59 /* We mark bits after the prefix as "X" */ 60 len = scnprintf(buf, *sz, "0x%016llx", p->prefix << p->height << SHIFT); 61 buf += len; 62 *sz -= len; 63 X = (p->height + SHIFT) / 4; 64 scnprintf(buf - X, *sz + X, "%*s", X, "XXXXXXXXXXXXXXXXX"); 65 66 if (!p->height) { 67 for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) { 68 len = scnprintf(buf, *sz, " %x:%x,", 69 i, __sync_seqno(p)[i]); 70 buf += len; 71 *sz -= len; 72 } 73 buf -= 1; 74 *sz += 1; 75 } 76 77 len = scnprintf(buf, *sz, "\n"); 78 buf += len; 79 *sz -= len; 80 81 if (p->height) { 82 for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) { 83 buf = __sync_print(__sync_child(p)[i], buf, sz, 84 depth + 1, 85 last << 1 | !!(p->bitmap >> (i + 1)), 86 i); 87 } 88 } 89 90 return buf; 91 } 92 93 static bool 94 i915_syncmap_print_to_buf(struct i915_syncmap *p, char *buf, unsigned long sz) 95 { 96 if (!p) 97 return false; 98 99 while (p->parent) 100 p = p->parent; 101 102 __sync_print(p, buf, &sz, 0, 1, 0); 103 return true; 104 } 105 106 static int check_syncmap_free(struct i915_syncmap **sync) 107 { 108 i915_syncmap_free(sync); 109 if (*sync) { 110 pr_err("sync not cleared after free\n"); 111 return -EINVAL; 112 } 113 114 return 0; 115 } 116 117 static int dump_syncmap(struct i915_syncmap *sync, int err) 118 { 119 char *buf; 120 121 if (!err) 122 return check_syncmap_free(&sync); 123 124 buf = kmalloc(PAGE_SIZE, GFP_KERNEL); 125 if (!buf) 126 goto skip; 127 128 if (i915_syncmap_print_to_buf(sync, buf, PAGE_SIZE)) 129 pr_err("%s", buf); 130 131 kfree(buf); 132 133 skip: 134 i915_syncmap_free(&sync); 135 return err; 136 } 137 138 static int igt_syncmap_init(void *arg) 139 { 140 struct i915_syncmap *sync = (void *)~0ul; 141 142 /* 143 * Cursory check that we can initialise a random pointer and transform 144 * it into the root pointer of a syncmap. 145 */ 146 147 i915_syncmap_init(&sync); 148 return check_syncmap_free(&sync); 149 } 150 151 static int check_seqno(struct i915_syncmap *leaf, unsigned int idx, u32 seqno) 152 { 153 if (leaf->height) { 154 pr_err("%s: not a leaf, height is %d\n", 155 __func__, leaf->height); 156 return -EINVAL; 157 } 158 159 if (__sync_seqno(leaf)[idx] != seqno) { 160 pr_err("%s: seqno[%d], found %x, expected %x\n", 161 __func__, idx, __sync_seqno(leaf)[idx], seqno); 162 return -EINVAL; 163 } 164 165 return 0; 166 } 167 168 static int check_one(struct i915_syncmap **sync, u64 context, u32 seqno) 169 { 170 int err; 171 172 err = i915_syncmap_set(sync, context, seqno); 173 if (err) 174 return err; 175 176 if ((*sync)->height) { 177 pr_err("Inserting first context=%llx did not return leaf (height=%d, prefix=%llx\n", 178 context, (*sync)->height, (*sync)->prefix); 179 return -EINVAL; 180 } 181 182 if ((*sync)->parent) { 183 pr_err("Inserting first context=%llx created branches!\n", 184 context); 185 return -EINVAL; 186 } 187 188 if (hweight32((*sync)->bitmap) != 1) { 189 pr_err("First bitmap does not contain a single entry, found %x (count=%d)!\n", 190 (*sync)->bitmap, hweight32((*sync)->bitmap)); 191 return -EINVAL; 192 } 193 194 err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno); 195 if (err) 196 return err; 197 198 if (!i915_syncmap_is_later(sync, context, seqno)) { 199 pr_err("Lookup of first context=%llx/seqno=%x failed!\n", 200 context, seqno); 201 return -EINVAL; 202 } 203 204 return 0; 205 } 206 207 static int igt_syncmap_one(void *arg) 208 { 209 I915_RND_STATE(prng); 210 IGT_TIMEOUT(end_time); 211 struct i915_syncmap *sync; 212 unsigned long max = 1; 213 int err; 214 215 /* 216 * Check that inserting a new id, creates a leaf and only that leaf. 217 */ 218 219 i915_syncmap_init(&sync); 220 221 do { 222 u64 context = i915_prandom_u64_state(&prng); 223 unsigned long loop; 224 225 err = check_syncmap_free(&sync); 226 if (err) 227 goto out; 228 229 for (loop = 0; loop <= max; loop++) { 230 err = check_one(&sync, context, 231 prandom_u32_state(&prng)); 232 if (err) 233 goto out; 234 } 235 max++; 236 } while (!__igt_timeout(end_time, NULL)); 237 pr_debug("%s: Completed %lu single insertions\n", 238 __func__, max * (max - 1) / 2); 239 out: 240 return dump_syncmap(sync, err); 241 } 242 243 static int check_leaf(struct i915_syncmap **sync, u64 context, u32 seqno) 244 { 245 int err; 246 247 err = i915_syncmap_set(sync, context, seqno); 248 if (err) 249 return err; 250 251 if ((*sync)->height) { 252 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n", 253 context, (*sync)->height, (*sync)->prefix); 254 return -EINVAL; 255 } 256 257 if (hweight32((*sync)->bitmap) != 1) { 258 pr_err("First entry into leaf (context=%llx) does not contain a single entry, found %x (count=%d)!\n", 259 context, (*sync)->bitmap, hweight32((*sync)->bitmap)); 260 return -EINVAL; 261 } 262 263 err = check_seqno((*sync), ilog2((*sync)->bitmap), seqno); 264 if (err) 265 return err; 266 267 if (!i915_syncmap_is_later(sync, context, seqno)) { 268 pr_err("Lookup of first entry context=%llx/seqno=%x failed!\n", 269 context, seqno); 270 return -EINVAL; 271 } 272 273 return 0; 274 } 275 276 static int igt_syncmap_join_above(void *arg) 277 { 278 struct i915_syncmap *sync; 279 unsigned int pass, order; 280 int err; 281 282 i915_syncmap_init(&sync); 283 284 /* 285 * When we have a new id that doesn't fit inside the existing tree, 286 * we need to add a new layer above. 287 * 288 * 1: 0x00000001 289 * 2: 0x00000010 290 * 3: 0x00000100 291 * 4: 0x00001000 292 * ... 293 * Each pass the common prefix shrinks and we have to insert a join. 294 * Each join will only contain two branches, the latest of which 295 * is always a leaf. 296 * 297 * If we then reuse the same set of contexts, we expect to build an 298 * identical tree. 299 */ 300 for (pass = 0; pass < 3; pass++) { 301 for (order = 0; order < 64; order += SHIFT) { 302 u64 context = BIT_ULL(order); 303 struct i915_syncmap *join; 304 305 err = check_leaf(&sync, context, 0); 306 if (err) 307 goto out; 308 309 join = sync->parent; 310 if (!join) /* very first insert will have no parents */ 311 continue; 312 313 if (!join->height) { 314 pr_err("Parent with no height!\n"); 315 err = -EINVAL; 316 goto out; 317 } 318 319 if (hweight32(join->bitmap) != 2) { 320 pr_err("Join does not have 2 children: %x (%d)\n", 321 join->bitmap, hweight32(join->bitmap)); 322 err = -EINVAL; 323 goto out; 324 } 325 326 if (__sync_child(join)[__sync_branch_idx(join, context)] != sync) { 327 pr_err("Leaf misplaced in parent!\n"); 328 err = -EINVAL; 329 goto out; 330 } 331 } 332 } 333 out: 334 return dump_syncmap(sync, err); 335 } 336 337 static int igt_syncmap_join_below(void *arg) 338 { 339 struct i915_syncmap *sync; 340 unsigned int step, order, idx; 341 int err = -ENODEV; 342 343 i915_syncmap_init(&sync); 344 345 /* 346 * Check that we can split a compacted branch by replacing it with 347 * a join. 348 */ 349 for (step = 0; step < KSYNCMAP; step++) { 350 for (order = 64 - SHIFT; order > 0; order -= SHIFT) { 351 u64 context = step * BIT_ULL(order); 352 353 err = i915_syncmap_set(&sync, context, 0); 354 if (err) 355 goto out; 356 357 if (sync->height) { 358 pr_err("Inserting context=%llx (order=%d, step=%d) did not return leaf (height=%d, prefix=%llx\n", 359 context, order, step, sync->height, sync->prefix); 360 err = -EINVAL; 361 goto out; 362 } 363 } 364 } 365 366 for (step = 0; step < KSYNCMAP; step++) { 367 for (order = SHIFT; order < 64; order += SHIFT) { 368 u64 context = step * BIT_ULL(order); 369 370 if (!i915_syncmap_is_later(&sync, context, 0)) { 371 pr_err("1: context %llx (order=%d, step=%d) not found\n", 372 context, order, step); 373 err = -EINVAL; 374 goto out; 375 } 376 377 for (idx = 1; idx < KSYNCMAP; idx++) { 378 if (i915_syncmap_is_later(&sync, context + idx, 0)) { 379 pr_err("1: context %llx (order=%d, step=%d) should not exist\n", 380 context + idx, order, step); 381 err = -EINVAL; 382 goto out; 383 } 384 } 385 } 386 } 387 388 for (order = SHIFT; order < 64; order += SHIFT) { 389 for (step = 0; step < KSYNCMAP; step++) { 390 u64 context = step * BIT_ULL(order); 391 392 if (!i915_syncmap_is_later(&sync, context, 0)) { 393 pr_err("2: context %llx (order=%d, step=%d) not found\n", 394 context, order, step); 395 err = -EINVAL; 396 goto out; 397 } 398 } 399 } 400 401 out: 402 return dump_syncmap(sync, err); 403 } 404 405 static int igt_syncmap_neighbours(void *arg) 406 { 407 I915_RND_STATE(prng); 408 IGT_TIMEOUT(end_time); 409 struct i915_syncmap *sync; 410 int err = -ENODEV; 411 412 /* 413 * Each leaf holds KSYNCMAP seqno. Check that when we create KSYNCMAP 414 * neighbouring ids, they all fit into the same leaf. 415 */ 416 417 i915_syncmap_init(&sync); 418 do { 419 u64 context = i915_prandom_u64_state(&prng) & ~MASK; 420 unsigned int idx; 421 422 if (i915_syncmap_is_later(&sync, context, 0)) /* Skip repeats */ 423 continue; 424 425 for (idx = 0; idx < KSYNCMAP; idx++) { 426 err = i915_syncmap_set(&sync, context + idx, 0); 427 if (err) 428 goto out; 429 430 if (sync->height) { 431 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n", 432 context, sync->height, sync->prefix); 433 err = -EINVAL; 434 goto out; 435 } 436 437 if (sync->bitmap != BIT(idx + 1) - 1) { 438 pr_err("Inserting neighbouring context=0x%llx+%d, did not fit into the same leaf bitmap=%x (%d), expected %lx (%d)\n", 439 context, idx, 440 sync->bitmap, hweight32(sync->bitmap), 441 BIT(idx + 1) - 1, idx + 1); 442 err = -EINVAL; 443 goto out; 444 } 445 } 446 } while (!__igt_timeout(end_time, NULL)); 447 out: 448 return dump_syncmap(sync, err); 449 } 450 451 static int igt_syncmap_compact(void *arg) 452 { 453 struct i915_syncmap *sync; 454 unsigned int idx, order; 455 int err = -ENODEV; 456 457 i915_syncmap_init(&sync); 458 459 /* 460 * The syncmap are "space efficient" compressed radix trees - any 461 * branch with only one child is skipped and replaced by the child. 462 * 463 * If we construct a tree with ids that are neighbouring at a non-zero 464 * height, we form a join but each child of that join is directly a 465 * leaf holding the single id. 466 */ 467 for (order = SHIFT; order < 64; order += SHIFT) { 468 err = check_syncmap_free(&sync); 469 if (err) 470 goto out; 471 472 /* Create neighbours in the parent */ 473 for (idx = 0; idx < KSYNCMAP; idx++) { 474 u64 context = idx * BIT_ULL(order) + idx; 475 476 err = i915_syncmap_set(&sync, context, 0); 477 if (err) 478 goto out; 479 480 if (sync->height) { 481 pr_err("Inserting context=%llx (order=%d, idx=%d) did not return leaf (height=%d, prefix=%llx\n", 482 context, order, idx, 483 sync->height, sync->prefix); 484 err = -EINVAL; 485 goto out; 486 } 487 } 488 489 sync = sync->parent; 490 if (sync->parent) { 491 pr_err("Parent (join) of last leaf was not the sync!\n"); 492 err = -EINVAL; 493 goto out; 494 } 495 496 if (sync->height != order) { 497 pr_err("Join does not have the expected height, found %d, expected %d\n", 498 sync->height, order); 499 err = -EINVAL; 500 goto out; 501 } 502 503 if (sync->bitmap != BIT(KSYNCMAP) - 1) { 504 pr_err("Join is not full!, found %x (%d) expected %lx (%d)\n", 505 sync->bitmap, hweight32(sync->bitmap), 506 BIT(KSYNCMAP) - 1, KSYNCMAP); 507 err = -EINVAL; 508 goto out; 509 } 510 511 /* Each of our children should be a leaf */ 512 for (idx = 0; idx < KSYNCMAP; idx++) { 513 struct i915_syncmap *leaf = __sync_child(sync)[idx]; 514 515 if (leaf->height) { 516 pr_err("Child %d is a not leaf!\n", idx); 517 err = -EINVAL; 518 goto out; 519 } 520 521 if (leaf->parent != sync) { 522 pr_err("Child %d is not attached to us!\n", 523 idx); 524 err = -EINVAL; 525 goto out; 526 } 527 528 if (!is_power_of_2(leaf->bitmap)) { 529 pr_err("Child %d holds more than one id, found %x (%d)\n", 530 idx, leaf->bitmap, hweight32(leaf->bitmap)); 531 err = -EINVAL; 532 goto out; 533 } 534 535 if (leaf->bitmap != BIT(idx)) { 536 pr_err("Child %d has wrong seqno idx, found %d, expected %d\n", 537 idx, ilog2(leaf->bitmap), idx); 538 err = -EINVAL; 539 goto out; 540 } 541 } 542 } 543 out: 544 return dump_syncmap(sync, err); 545 } 546 547 static int igt_syncmap_random(void *arg) 548 { 549 I915_RND_STATE(prng); 550 IGT_TIMEOUT(end_time); 551 struct i915_syncmap *sync; 552 unsigned long count, phase, i; 553 u32 seqno; 554 int err; 555 556 i915_syncmap_init(&sync); 557 558 /* 559 * Having tried to test the individual operations within i915_syncmap, 560 * run a smoketest exploring the entire u64 space with random 561 * insertions. 562 */ 563 564 count = 0; 565 phase = jiffies + HZ/100 + 1; 566 do { 567 u64 context = i915_prandom_u64_state(&prng); 568 569 err = i915_syncmap_set(&sync, context, 0); 570 if (err) 571 goto out; 572 573 count++; 574 } while (!time_after(jiffies, phase)); 575 seqno = 0; 576 577 phase = 0; 578 do { 579 I915_RND_STATE(ctx); 580 u32 last_seqno = seqno; 581 bool expect; 582 583 seqno = prandom_u32_state(&prng); 584 expect = seqno_later(last_seqno, seqno); 585 586 for (i = 0; i < count; i++) { 587 u64 context = i915_prandom_u64_state(&ctx); 588 589 if (i915_syncmap_is_later(&sync, context, seqno) != expect) { 590 pr_err("context=%llu, last=%u this=%u did not match expectation (%d)\n", 591 context, last_seqno, seqno, expect); 592 err = -EINVAL; 593 goto out; 594 } 595 596 err = i915_syncmap_set(&sync, context, seqno); 597 if (err) 598 goto out; 599 } 600 601 phase++; 602 } while (!__igt_timeout(end_time, NULL)); 603 pr_debug("Completed %lu passes, each of %lu contexts\n", phase, count); 604 out: 605 return dump_syncmap(sync, err); 606 } 607 608 int i915_syncmap_mock_selftests(void) 609 { 610 static const struct i915_subtest tests[] = { 611 SUBTEST(igt_syncmap_init), 612 SUBTEST(igt_syncmap_one), 613 SUBTEST(igt_syncmap_join_above), 614 SUBTEST(igt_syncmap_join_below), 615 SUBTEST(igt_syncmap_neighbours), 616 SUBTEST(igt_syncmap_compact), 617 SUBTEST(igt_syncmap_random), 618 }; 619 620 return i915_subtests(tests, NULL); 621 } 622
Indexes created Sat Sep 20 22:09:52 GMT 2025