imd.c
1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 3 #include <assert.h> 4 #include <cbmem.h> 5 #include <console/console.h> 6 #include <imd.h> 7 #include <string.h> 8 #include <types.h> 9 #include <imd_private.h> 10 11 12 /* For more details on implementation and usage please see the imd.h header. */ 13 14 static void *relative_pointer(void *base, ssize_t offset) 15 { 16 intptr_t b = (intptr_t)base; 17 b += offset; 18 return (void *)b; 19 } 20 21 static bool imd_root_pointer_valid(const struct imd_root_pointer *rp) 22 { 23 return !!(rp->magic == IMD_ROOT_PTR_MAGIC); 24 } 25 26 static struct imd_root *imdr_root(const struct imdr *imdr) 27 { 28 return imdr->r; 29 } 30 31 /* 32 * The root pointer is relative to the upper limit of the imd. i.e. It sits 33 * just below the upper limit. 34 */ 35 static struct imd_root_pointer *imdr_get_root_pointer(const struct imdr *imdr) 36 { 37 struct imd_root_pointer *rp; 38 39 rp = relative_pointer((void *)imdr->limit, -sizeof(*rp)); 40 41 return rp; 42 } 43 44 static void imd_link_root(struct imd_root_pointer *rp, struct imd_root *r) 45 { 46 rp->magic = IMD_ROOT_PTR_MAGIC; 47 rp->root_offset = (int32_t)((intptr_t)r - (intptr_t)rp); 48 } 49 50 static struct imd_entry *root_last_entry(struct imd_root *r) 51 { 52 return &r->entries[r->num_entries - 1]; 53 } 54 55 static size_t root_num_entries(size_t root_size) 56 { 57 size_t entries_size; 58 59 entries_size = root_size; 60 entries_size -= sizeof(struct imd_root_pointer); 61 entries_size -= sizeof(struct imd_root); 62 63 return entries_size / sizeof(struct imd_entry); 64 } 65 66 static size_t imd_root_data_left(struct imd_root *r) 67 { 68 struct imd_entry *last_entry; 69 70 last_entry = root_last_entry(r); 71 72 if (r->max_offset != 0) 73 return last_entry->start_offset - r->max_offset; 74 75 return ~(size_t)0; 76 } 77 78 static bool root_is_locked(const struct imd_root *r) 79 { 80 return !!(r->flags & IMD_FLAG_LOCKED); 81 } 82 83 static void imd_entry_assign(struct imd_entry *e, uint32_t id, 84 ssize_t offset, size_t size) 85 { 86 e->magic = IMD_ENTRY_MAGIC; 87 e->start_offset = offset; 88 e->size = size; 89 e->id = id; 90 } 91 92 static void imdr_init(struct imdr *ir, void *upper_limit) 93 { 94 uintptr_t limit = (uintptr_t)upper_limit; 95 /* Upper limit is aligned down to 4KiB */ 96 ir->limit = ALIGN_DOWN(limit, LIMIT_ALIGN); 97 ir->r = NULL; 98 } 99 100 static int imdr_create_empty(struct imdr *imdr, size_t root_size, 101 size_t entry_align) 102 { 103 struct imd_root_pointer *rp; 104 struct imd_root *r; 105 struct imd_entry *e; 106 ssize_t root_offset; 107 108 if (!imdr->limit) 109 return -1; 110 111 /* root_size and entry_align should be a power of 2. */ 112 assert(IS_POWER_OF_2(root_size)); 113 assert(IS_POWER_OF_2(entry_align)); 114 115 /* 116 * root_size needs to be large enough to accommodate root pointer and 117 * root book keeping structure. Furthermore, there needs to be a space 118 * for at least one entry covering root region. The caller needs to 119 * ensure there's enough room for tracking individual allocations. 120 */ 121 if (root_size < (sizeof(*rp) + sizeof(*r) + sizeof(*e))) 122 return -1; 123 124 /* For simplicity don't allow sizes or alignments to exceed LIMIT_ALIGN. 125 */ 126 if (root_size > LIMIT_ALIGN || entry_align > LIMIT_ALIGN) 127 return -1; 128 129 /* Additionally, don't handle an entry alignment > root_size. */ 130 if (entry_align > root_size) 131 return -1; 132 133 rp = imdr_get_root_pointer(imdr); 134 135 root_offset = -(ssize_t)root_size; 136 /* Set root pointer. */ 137 imdr->r = relative_pointer((void *)imdr->limit, root_offset); 138 r = imdr_root(imdr); 139 imd_link_root(rp, r); 140 141 memset(r, 0, sizeof(*r)); 142 r->entry_align = entry_align; 143 144 /* Calculate size left for entries. */ 145 r->max_entries = root_num_entries(root_size); 146 147 /* Fill in first entry covering the root region. */ 148 r->num_entries = 1; 149 e = &r->entries[0]; 150 imd_entry_assign(e, CBMEM_ID_IMD_ROOT, 0, root_size); 151 152 printk(BIOS_DEBUG, "IMD: root @ %p %u entries.\n", r, r->max_entries); 153 154 return 0; 155 } 156 157 static int imdr_recover(struct imdr *imdr) 158 { 159 struct imd_root_pointer *rp; 160 struct imd_root *r; 161 uintptr_t low_limit; 162 size_t i; 163 164 if (!imdr->limit) 165 return -1; 166 167 rp = imdr_get_root_pointer(imdr); 168 169 if (!imd_root_pointer_valid(rp)) 170 return -1; 171 172 r = relative_pointer(rp, rp->root_offset); 173 174 /* Ensure that root is just under the root pointer */ 175 if ((intptr_t)rp - (intptr_t)&r->entries[r->max_entries] > sizeof(struct imd_entry)) 176 return -1; 177 178 if (r->num_entries > r->max_entries) 179 return -1; 180 181 /* Entry alignment should be power of 2. */ 182 if (!IS_POWER_OF_2(r->entry_align)) 183 return -1; 184 185 low_limit = (uintptr_t)relative_pointer(r, r->max_offset); 186 187 /* If no max_offset then lowest limit is 0. */ 188 if (low_limit == (uintptr_t)r) 189 low_limit = 0; 190 191 for (i = 0; i < r->num_entries; i++) { 192 uintptr_t start_addr; 193 const struct imd_entry *e = &r->entries[i]; 194 195 if (e->magic != IMD_ENTRY_MAGIC) 196 return -1; 197 198 start_addr = (uintptr_t)relative_pointer(r, e->start_offset); 199 if (start_addr < low_limit) 200 return -1; 201 if (start_addr >= imdr->limit || 202 (start_addr + e->size) > imdr->limit) 203 return -1; 204 } 205 206 /* Set root pointer. */ 207 imdr->r = r; 208 209 return 0; 210 } 211 212 static const struct imd_entry *imdr_entry_find(const struct imdr *imdr, 213 uint32_t id) 214 { 215 struct imd_root *r; 216 struct imd_entry *e; 217 size_t i; 218 219 r = imdr_root(imdr); 220 221 if (r == NULL) 222 return NULL; 223 224 e = NULL; 225 /* Skip first entry covering the root. */ 226 for (i = 1; i < r->num_entries; i++) { 227 if (id != r->entries[i].id) 228 continue; 229 e = &r->entries[i]; 230 break; 231 } 232 233 return e; 234 } 235 236 static int imdr_limit_size(struct imdr *imdr, size_t max_size) 237 { 238 struct imd_root *r; 239 ssize_t smax_size; 240 size_t root_size; 241 242 r = imdr_root(imdr); 243 if (r == NULL) 244 return -1; 245 246 root_size = imdr->limit - (uintptr_t)r; 247 248 if (max_size < root_size) 249 return -1; 250 251 /* Take into account the root size. */ 252 smax_size = max_size - root_size; 253 smax_size = -smax_size; 254 255 r->max_offset = smax_size; 256 257 return 0; 258 } 259 260 static size_t imdr_entry_size(const struct imd_entry *e) 261 { 262 return e->size; 263 } 264 265 static void *imdr_entry_at(const struct imdr *imdr, const struct imd_entry *e) 266 { 267 return relative_pointer(imdr_root(imdr), e->start_offset); 268 } 269 270 static struct imd_entry *imd_entry_add_to_root(struct imd_root *r, uint32_t id, 271 size_t size) 272 { 273 struct imd_entry *entry; 274 struct imd_entry *last_entry; 275 ssize_t e_offset; 276 size_t used_size; 277 278 if (r->num_entries == r->max_entries) 279 return NULL; 280 281 /* Determine total size taken up by entry. */ 282 used_size = ALIGN_UP(size, r->entry_align); 283 284 /* See if size overflows imd total size. */ 285 if (used_size > imd_root_data_left(r)) 286 return NULL; 287 288 /* 289 * Determine if offset field overflows. All offsets should be lower 290 * than the previous one. 291 */ 292 last_entry = root_last_entry(r); 293 e_offset = last_entry->start_offset; 294 e_offset -= (ssize_t)used_size; 295 if (e_offset >= last_entry->start_offset) 296 return NULL; 297 298 entry = root_last_entry(r) + 1; 299 r->num_entries++; 300 301 imd_entry_assign(entry, id, e_offset, size); 302 303 return entry; 304 } 305 306 static const struct imd_entry *imdr_entry_add(const struct imdr *imdr, 307 uint32_t id, size_t size) 308 { 309 struct imd_root *r; 310 311 r = imdr_root(imdr); 312 313 if (r == NULL) 314 return NULL; 315 316 if (root_is_locked(r)) 317 return NULL; 318 319 return imd_entry_add_to_root(r, id, size); 320 } 321 322 static bool imdr_has_entry(const struct imdr *imdr, const struct imd_entry *e) 323 { 324 struct imd_root *r; 325 size_t idx; 326 327 r = imdr_root(imdr); 328 if (r == NULL) 329 return false; 330 331 /* Determine if the entry is within this root structure. */ 332 idx = e - &r->entries[0]; 333 if (idx >= r->num_entries) 334 return false; 335 336 return true; 337 } 338 339 static const struct imdr *imd_entry_to_imdr(const struct imd *imd, 340 const struct imd_entry *entry) 341 { 342 if (imdr_has_entry(&imd->lg, entry)) 343 return &imd->lg; 344 345 if (imdr_has_entry(&imd->sm, entry)) 346 return &imd->sm; 347 348 return NULL; 349 } 350 351 /* Initialize imd handle. */ 352 void imd_handle_init(struct imd *imd, void *upper_limit) 353 { 354 imdr_init(&imd->lg, upper_limit); 355 imdr_init(&imd->sm, NULL); 356 } 357 358 void imd_handle_init_partial_recovery(struct imd *imd) 359 { 360 const struct imd_entry *e; 361 struct imd_root_pointer *rp; 362 struct imdr *imdr; 363 364 if (imd->lg.limit == 0) 365 return; 366 367 imd_handle_init(imd, (void *)imd->lg.limit); 368 369 /* Initialize root pointer for the large regions. */ 370 imdr = &imd->lg; 371 rp = imdr_get_root_pointer(imdr); 372 imdr->r = relative_pointer(rp, rp->root_offset); 373 374 e = imdr_entry_find(imdr, SMALL_REGION_ID); 375 376 if (e == NULL) 377 return; 378 379 imd->sm.limit = (uintptr_t)imdr_entry_at(imdr, e); 380 imd->sm.limit += imdr_entry_size(e); 381 imdr = &imd->sm; 382 rp = imdr_get_root_pointer(imdr); 383 imdr->r = relative_pointer(rp, rp->root_offset); 384 } 385 386 int imd_create_empty(struct imd *imd, size_t root_size, size_t entry_align) 387 { 388 return imdr_create_empty(&imd->lg, root_size, entry_align); 389 } 390 391 int imd_create_tiered_empty(struct imd *imd, 392 size_t lg_root_size, size_t lg_entry_align, 393 size_t sm_root_size, size_t sm_entry_align) 394 { 395 size_t sm_region_size; 396 const struct imd_entry *e; 397 struct imdr *imdr; 398 399 imdr = &imd->lg; 400 401 if (imdr_create_empty(imdr, lg_root_size, lg_entry_align) != 0) 402 return -1; 403 404 /* Calculate the size of the small region to request. */ 405 sm_region_size = root_num_entries(sm_root_size) * sm_entry_align; 406 sm_region_size += sm_root_size; 407 sm_region_size = ALIGN_UP(sm_region_size, lg_entry_align); 408 409 /* Add a new entry to the large region to cover the root and entries. */ 410 e = imdr_entry_add(imdr, SMALL_REGION_ID, sm_region_size); 411 412 if (e == NULL) 413 goto fail; 414 415 imd->sm.limit = (uintptr_t)imdr_entry_at(imdr, e); 416 imd->sm.limit += sm_region_size; 417 418 if (imdr_create_empty(&imd->sm, sm_root_size, sm_entry_align) != 0 || 419 imdr_limit_size(&imd->sm, sm_region_size)) 420 goto fail; 421 422 return 0; 423 fail: 424 imd_handle_init(imd, (void *)imdr->limit); 425 return -1; 426 } 427 428 int imd_recover(struct imd *imd) 429 { 430 const struct imd_entry *e; 431 uintptr_t small_upper_limit; 432 struct imdr *imdr; 433 434 imdr = &imd->lg; 435 if (imdr_recover(imdr) != 0) 436 return -1; 437 438 /* Determine if small region is present. */ 439 e = imdr_entry_find(imdr, SMALL_REGION_ID); 440 441 if (e == NULL) 442 return 0; 443 444 small_upper_limit = (uintptr_t)imdr_entry_at(imdr, e); 445 small_upper_limit += imdr_entry_size(e); 446 447 imd->sm.limit = small_upper_limit; 448 449 /* Tear down any changes on failure. */ 450 if (imdr_recover(&imd->sm) != 0) { 451 imd_handle_init(imd, (void *)imd->lg.limit); 452 return -1; 453 } 454 455 return 0; 456 } 457 458 int imd_limit_size(struct imd *imd, size_t max_size) 459 { 460 return imdr_limit_size(&imd->lg, max_size); 461 } 462 463 int imd_lockdown(struct imd *imd) 464 { 465 struct imd_root *r; 466 467 r = imdr_root(&imd->lg); 468 if (r == NULL) 469 return -1; 470 471 r->flags |= IMD_FLAG_LOCKED; 472 473 r = imdr_root(&imd->sm); 474 if (r != NULL) 475 r->flags |= IMD_FLAG_LOCKED; 476 477 return 0; 478 } 479 480 int imd_region_used(struct imd *imd, void **base, size_t *size) 481 { 482 struct imd_root *r; 483 struct imd_entry *e; 484 void *low_addr; 485 size_t sz_used; 486 487 if (!imd->lg.limit) 488 return -1; 489 490 r = imdr_root(&imd->lg); 491 492 if (r == NULL) 493 return -1; 494 495 /* Use last entry to obtain lowest address. */ 496 e = root_last_entry(r); 497 498 low_addr = relative_pointer(r, e->start_offset); 499 500 /* Total size used is the last entry's base up to the limit. */ 501 sz_used = imd->lg.limit - (uintptr_t)low_addr; 502 503 *base = low_addr; 504 *size = sz_used; 505 506 return 0; 507 } 508 509 const struct imd_entry *imd_entry_add(const struct imd *imd, uint32_t id, 510 size_t size) 511 { 512 struct imd_root *r; 513 const struct imdr *imdr; 514 const struct imd_entry *e = NULL; 515 516 /* 517 * Determine if requested size is less than 1/4 of small data 518 * region is left. 519 */ 520 imdr = &imd->sm; 521 r = imdr_root(imdr); 522 523 /* No small region. Use the large region. */ 524 if (r == NULL) 525 return imdr_entry_add(&imd->lg, id, size); 526 else if (size <= r->entry_align || size <= imd_root_data_left(r) / 4) 527 e = imdr_entry_add(imdr, id, size); 528 529 /* Fall back on large region allocation. */ 530 if (e == NULL) 531 e = imdr_entry_add(&imd->lg, id, size); 532 533 return e; 534 } 535 536 const struct imd_entry *imd_entry_find(const struct imd *imd, uint32_t id) 537 { 538 const struct imd_entry *e; 539 540 /* Many of the smaller allocations are used a lot. Therefore, try 541 * the small region first. */ 542 e = imdr_entry_find(&imd->sm, id); 543 544 if (e == NULL) 545 e = imdr_entry_find(&imd->lg, id); 546 547 return e; 548 } 549 550 const struct imd_entry *imd_entry_find_or_add(const struct imd *imd, 551 uint32_t id, size_t size) 552 { 553 const struct imd_entry *e; 554 555 e = imd_entry_find(imd, id); 556 557 if (e != NULL) 558 return e; 559 560 return imd_entry_add(imd, id, size); 561 } 562 563 size_t imd_entry_size(const struct imd_entry *entry) 564 { 565 return imdr_entry_size(entry); 566 } 567 568 void *imd_entry_at(const struct imd *imd, const struct imd_entry *entry) 569 { 570 const struct imdr *imdr; 571 572 imdr = imd_entry_to_imdr(imd, entry); 573 574 if (imdr == NULL) 575 return NULL; 576 577 return imdr_entry_at(imdr, entry); 578 } 579 580 uint32_t imd_entry_id(const struct imd_entry *entry) 581 { 582 return entry->id; 583 } 584 585 int imd_entry_remove(const struct imd *imd, const struct imd_entry *entry) 586 { 587 struct imd_root *r; 588 const struct imdr *imdr; 589 590 imdr = imd_entry_to_imdr(imd, entry); 591 592 if (imdr == NULL) 593 return -1; 594 595 r = imdr_root(imdr); 596 597 if (root_is_locked(r)) 598 return -1; 599 600 if (entry != root_last_entry(r)) 601 return -1; 602 603 /* Don't remove entry covering root region */ 604 if (r->num_entries == 1) 605 return -1; 606 607 r->num_entries--; 608 609 return 0; 610 } 611 612 static void imdr_print_entries(const struct imdr *imdr, const char *indent, 613 const struct imd_lookup *lookup, size_t size) 614 { 615 struct imd_root *r; 616 size_t i; 617 size_t j; 618 619 if (imdr == NULL) 620 return; 621 622 r = imdr_root(imdr); 623 624 for (i = 0; i < r->num_entries; i++) { 625 const char *name = NULL; 626 const struct imd_entry *e = &r->entries[i]; 627 628 for (j = 0; j < size; j++) { 629 if (lookup[j].id == e->id) { 630 name = lookup[j].name; 631 break; 632 } 633 } 634 635 printk(BIOS_DEBUG, "%s", indent); 636 637 if (name == NULL) 638 printk(BIOS_DEBUG, "%08x ", e->id); 639 else 640 printk(BIOS_DEBUG, "%s", name); 641 printk(BIOS_DEBUG, "%2zu. ", i); 642 printk(BIOS_DEBUG, "%p ", imdr_entry_at(imdr, e)); 643 printk(BIOS_DEBUG, "0x%08zx\n", imdr_entry_size(e)); 644 } 645 } 646 647 int imd_print_entries(const struct imd *imd, const struct imd_lookup *lookup, 648 size_t size) 649 { 650 if (imdr_root(&imd->lg) == NULL) 651 return -1; 652 653 imdr_print_entries(&imd->lg, "", lookup, size); 654 if (imdr_root(&imd->sm) != NULL) { 655 printk(BIOS_DEBUG, "IMD small region:\n"); 656 imdr_print_entries(&imd->sm, " ", lookup, size); 657 } 658 659 return 0; 660 } 661 662 int imd_cursor_init(const struct imd *imd, struct imd_cursor *cursor) 663 { 664 if (imd == NULL || cursor == NULL) 665 return -1; 666 667 memset(cursor, 0, sizeof(*cursor)); 668 669 cursor->imdr[0] = &imd->lg; 670 cursor->imdr[1] = &imd->sm; 671 672 return 0; 673 } 674 675 const struct imd_entry *imd_cursor_next(struct imd_cursor *cursor) 676 { 677 struct imd_root *r; 678 const struct imd_entry *e; 679 680 if (cursor->current_imdr >= ARRAY_SIZE(cursor->imdr)) 681 return NULL; 682 683 r = imdr_root(cursor->imdr[cursor->current_imdr]); 684 685 if (r == NULL) 686 return NULL; 687 688 if (cursor->current_entry >= r->num_entries) { 689 /* Try next imdr. */ 690 cursor->current_imdr++; 691 cursor->current_entry = 0; 692 return imd_cursor_next(cursor); 693 } 694 695 e = &r->entries[cursor->current_entry]; 696 cursor->current_entry++; 697 698 return e; 699 }