lib/lmb.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Procedures for maintaining information about logical memory blocks.
   4  *
   5  * Peter Bergner, IBM Corp.     June 2001.
   6  * Copyright (C) 2001 Peter Bergner.
   7  */
   8
   9 #include <alist.h>
  10 #include <efi_loader.h>
  11 #include <event.h>
  12 #include <image.h>
  13 #include <mapmem.h>
  14 #include <lmb.h>
  15 #include <log.h>
  16 #include <malloc.h>
  17 #include <spl.h>
  18
  19 #include <asm/global_data.h>
  20 #include <asm/sections.h>
  21 #include <linux/kernel.h>
  22 #include <linux/sizes.h>
  23
  24 DECLARE_GLOBAL_DATA_PTR;
  25
  26 #define MAP_OP_RESERVE          (u8)0x1
  27 #define MAP_OP_FREE             (u8)0x2
  28 #define MAP_OP_ADD              (u8)0x3
  29
  30 /*
  31  * The following low level LMB functions must not access the global LMB memory
  32  * map since they are also used to manage IOVA memory maps in iommu drivers like
  33  * apple_dart.
  34  */
  35
  36 static long lmb_addrs_overlap(phys_addr_t base1, phys_size_t size1,
  37                               phys_addr_t base2, phys_size_t size2)
  38 {
  39         const phys_addr_t base1_end = base1 + size1 - 1;
  40         const phys_addr_t base2_end = base2 + size2 - 1;
  41
  42         return ((base1 <= base2_end) && (base2 <= base1_end));
  43 }
  44
  45 static long lmb_addrs_adjacent(phys_addr_t base1, phys_size_t size1,
  46                                phys_addr_t base2, phys_size_t size2)
  47 {
  48         if (base2 == base1 + size1)
  49                 return 1;
  50         else if (base1 == base2 + size2)
  51                 return -1;
  52
  53         return 0;
  54 }
  55
  56 static long lmb_regions_overlap(struct alist *lmb_rgn_lst, unsigned long r1,
  57                                 unsigned long r2)
  58 {
  59         struct lmb_region *rgn = lmb_rgn_lst->data;
  60         phys_addr_t base1 = rgn[r1].base;
  61         phys_size_t size1 = rgn[r1].size;
  62         phys_addr_t base2 = rgn[r2].base;
  63         phys_size_t size2 = rgn[r2].size;
  64
  65         return lmb_addrs_overlap(base1, size1, base2, size2);
  66 }
  67
  68 static long lmb_regions_adjacent(struct alist *lmb_rgn_lst, unsigned long r1,
  69                                  unsigned long r2)
  70 {
  71         struct lmb_region *rgn = lmb_rgn_lst->data;
  72         phys_addr_t base1 = rgn[r1].base;
  73         phys_size_t size1 = rgn[r1].size;
  74         phys_addr_t base2 = rgn[r2].base;
  75         phys_size_t size2 = rgn[r2].size;
  76
  77         return lmb_addrs_adjacent(base1, size1, base2, size2);
  78 }
  79
  80 static void lmb_remove_region(struct alist *lmb_rgn_lst, unsigned long r)
  81 {
  82         unsigned long i;
  83         struct lmb_region *rgn = lmb_rgn_lst->data;
  84
  85         for (i = r; i < lmb_rgn_lst->count - 1; i++) {
  86                 rgn[i].base = rgn[i + 1].base;
  87                 rgn[i].size = rgn[i + 1].size;
  88                 rgn[i].flags = rgn[i + 1].flags;
  89         }
  90         lmb_rgn_lst->count--;
  91 }
  92
  93 /* Assumption: base addr of region 1 < base addr of region 2 */
  94 static void lmb_coalesce_regions(struct alist *lmb_rgn_lst, unsigned long r1,
  95                                  unsigned long r2)
  96 {
  97         struct lmb_region *rgn = lmb_rgn_lst->data;
  98
  99         rgn[r1].size += rgn[r2].size;
 100         lmb_remove_region(lmb_rgn_lst, r2);
 101 }
 102
 103 /*Assumption : base addr of region 1 < base addr of region 2*/
 104 static void lmb_fix_over_lap_regions(struct alist *lmb_rgn_lst,
 105                                      unsigned long r1, unsigned long r2)
 106 {
 107         struct lmb_region *rgn = lmb_rgn_lst->data;
 108
 109         phys_addr_t base1 = rgn[r1].base;
 110         phys_size_t size1 = rgn[r1].size;
 111         phys_addr_t base2 = rgn[r2].base;
 112         phys_size_t size2 = rgn[r2].size;
 113
 114         if (base1 + size1 > base2 + size2) {
 115                 printf("This will not be a case any time\n");
 116                 return;
 117         }
 118         rgn[r1].size = base2 + size2 - base1;
 119         lmb_remove_region(lmb_rgn_lst, r2);
 120 }
 121
 122 static long lmb_resize_regions(struct alist *lmb_rgn_lst,
 123                                unsigned long idx_start,
 124                                phys_addr_t base, phys_size_t size)
 125 {
 126         phys_size_t rgnsize;
 127         unsigned long rgn_cnt, idx, idx_end;
 128         phys_addr_t rgnbase, rgnend;
 129         phys_addr_t mergebase, mergeend;
 130         struct lmb_region *rgn = lmb_rgn_lst->data;
 131
 132         rgn_cnt = 0;
 133         idx = idx_start;
 134         idx_end = idx_start;
 135
 136         /*
 137          * First thing to do is to identify how many regions
 138          * the requested region overlaps.
 139          * If the flags match, combine all these overlapping
 140          * regions into a single region, and remove the merged
 141          * regions.
 142          */
 143         while (idx <= lmb_rgn_lst->count - 1) {
 144                 rgnbase = rgn[idx].base;
 145                 rgnsize = rgn[idx].size;
 146
 147                 if (lmb_addrs_overlap(base, size, rgnbase,
 148                                       rgnsize)) {
 149                         if (rgn[idx].flags != LMB_NONE)
 150                                 return -1;
 151                         rgn_cnt++;
 152                         idx_end = idx;
 153                 }
 154                 idx++;
 155         }
 156
 157         /* The merged region's base and size */
 158         rgnbase = rgn[idx_start].base;
 159         mergebase = min(base, rgnbase);
 160         rgnend = rgn[idx_end].base + rgn[idx_end].size;
 161         mergeend = max(rgnend, (base + size));
 162
 163         rgn[idx_start].base = mergebase;
 164         rgn[idx_start].size = mergeend - mergebase;
 165
 166         /* Now remove the merged regions */
 167         while (--rgn_cnt)
 168                 lmb_remove_region(lmb_rgn_lst, idx_start + 1);
 169
 170         return 0;
 171 }
 172
 173 /**
 174  * lmb_add_region_flags() - Add an lmb region to the given list
 175  * @lmb_rgn_lst: LMB list to which region is to be added(free/used)
 176  * @base: Start address of the region
 177  * @size: Size of the region to be added
 178  * @flags: Attributes of the LMB region
 179  *
 180  * Add a region of memory to the list. If the region does not exist, add
 181  * it to the list. Depending on the attributes of the region to be added,
 182  * the function might resize an already existing region or coalesce two
 183  * adjacent regions.
 184  *
 185  * Return:
 186  * * %0         - Added successfully, or it's already added (only if LMB_NONE)
 187  * * %-EEXIST   - The region is already added, and flags != LMB_NONE
 188  * * %-1        - Failure
 189  */
 190 static long lmb_add_region_flags(struct alist *lmb_rgn_lst, phys_addr_t base,
 191                                  phys_size_t size, u32 flags)
 192 {
 193         unsigned long coalesced = 0;
 194         long ret, i;
 195         struct lmb_region *rgn = lmb_rgn_lst->data;
 196
 197         if (alist_err(lmb_rgn_lst))
 198                 return -1;
 199
 200         /* First try and coalesce this LMB with another. */
 201         for (i = 0; i < lmb_rgn_lst->count; i++) {
 202                 phys_addr_t rgnbase = rgn[i].base;
 203                 phys_size_t rgnsize = rgn[i].size;
 204                 u32 rgnflags = rgn[i].flags;
 205
 206                 ret = lmb_addrs_adjacent(base, size, rgnbase, rgnsize);
 207                 if (ret > 0) {
 208                         if (flags != rgnflags)
 209                                 break;
 210                         rgn[i].base -= size;
 211                         rgn[i].size += size;
 212                         coalesced++;
 213                         break;
 214                 } else if (ret < 0) {
 215                         if (flags != rgnflags)
 216                                 break;
 217                         rgn[i].size += size;
 218                         coalesced++;
 219                         break;
 220                 } else if (lmb_addrs_overlap(base, size, rgnbase, rgnsize)) {
 221                         if (flags != LMB_NONE)
 222                                 return -EEXIST;
 223
 224                         ret = lmb_resize_regions(lmb_rgn_lst, i, base, size);
 225                         if (ret < 0)
 226                                 return -1;
 227
 228                         coalesced++;
 229                         break;
 230
 231                         return -1;
 232                 }
 233         }
 234
 235         if (lmb_rgn_lst->count && i < lmb_rgn_lst->count - 1) {
 236                 rgn = lmb_rgn_lst->data;
 237                 if (rgn[i].flags == rgn[i + 1].flags) {
 238                         if (lmb_regions_adjacent(lmb_rgn_lst, i, i + 1)) {
 239                                 lmb_coalesce_regions(lmb_rgn_lst, i, i + 1);
 240                                 coalesced++;
 241                         } else if (lmb_regions_overlap(lmb_rgn_lst, i, i + 1)) {
 242                                 /* fix overlapping area */
 243                                 lmb_fix_over_lap_regions(lmb_rgn_lst, i, i + 1);
 244                                 coalesced++;
 245                         }
 246                 }
 247         }
 248
 249         if (coalesced)
 250                 return 0;
 251
 252         if (alist_full(lmb_rgn_lst) &&
 253             !alist_expand_by(lmb_rgn_lst, lmb_rgn_lst->alloc))
 254                 return -1;
 255         rgn = lmb_rgn_lst->data;
 256
 257         /* Couldn't coalesce the LMB, so add it to the sorted table. */
 258         for (i = lmb_rgn_lst->count; i >= 0; i--) {
 259                 if (i && base < rgn[i - 1].base) {
 260                         rgn[i] = rgn[i - 1];
 261                 } else {
 262                         rgn[i].base = base;
 263                         rgn[i].size = size;
 264                         rgn[i].flags = flags;
 265                         break;
 266                 }
 267         }
 268
 269         lmb_rgn_lst->count++;
 270
 271         return 0;
 272 }
 273
 274 static long _lmb_free(struct alist *lmb_rgn_lst, phys_addr_t base,
 275                       phys_size_t size)
 276 {
 277         struct lmb_region *rgn;
 278         phys_addr_t rgnbegin, rgnend;
 279         phys_addr_t end = base + size - 1;
 280         int i;
 281
 282         /* Suppress GCC warnings */
 283         rgnbegin = 0;
 284         rgnend = 0;
 285
 286         rgn = lmb_rgn_lst->data;
 287         /* Find the region where (base, size) belongs to */
 288         for (i = 0; i < lmb_rgn_lst->count; i++) {
 289                 rgnbegin = rgn[i].base;
 290                 rgnend = rgnbegin + rgn[i].size - 1;
 291
 292                 if (rgnbegin <= base && end <= rgnend)
 293                         break;
 294         }
 295
 296         /* Didn't find the region */
 297         if (i == lmb_rgn_lst->count)
 298                 return -1;
 299
 300         /* Check to see if we are removing entire region */
 301         if (rgnbegin == base && rgnend == end) {
 302                 lmb_remove_region(lmb_rgn_lst, i);
 303                 return 0;
 304         }
 305
 306         /* Check to see if region is matching at the front */
 307         if (rgnbegin == base) {
 308                 rgn[i].base = end + 1;
 309                 rgn[i].size -= size;
 310                 return 0;
 311         }
 312
 313         /* Check to see if the region is matching at the end */
 314         if (rgnend == end) {
 315                 rgn[i].size -= size;
 316                 return 0;
 317         }
 318
 319         /*
 320          * We need to split the entry -  adjust the current one to the
 321          * beginging of the hole and add the region after hole.
 322          */
 323         rgn[i].size = base - rgn[i].base;
 324         return lmb_add_region_flags(lmb_rgn_lst, end + 1, rgnend - end,
 325                                     rgn[i].flags);
 326 }
 327
 328 static long lmb_overlaps_region(struct alist *lmb_rgn_lst, phys_addr_t base,
 329                                 phys_size_t size)
 330 {
 331         unsigned long i;
 332         struct lmb_region *rgn = lmb_rgn_lst->data;
 333
 334         for (i = 0; i < lmb_rgn_lst->count; i++) {
 335                 phys_addr_t rgnbase = rgn[i].base;
 336                 phys_size_t rgnsize = rgn[i].size;
 337
 338                 if (lmb_addrs_overlap(base, size, rgnbase, rgnsize))
 339                         break;
 340         }
 341
 342         return (i < lmb_rgn_lst->count) ? i : -1;
 343 }
 344
 345 /*
 346  * IOVA LMB memory maps using lmb pointers instead of the global LMB memory map.
 347  */
 348
 349 int io_lmb_setup(struct lmb *io_lmb)
 350 {
 351         int ret;
 352
 353         ret = alist_init(&io_lmb->available_mem, sizeof(struct lmb_region),
 354                          (uint)LMB_ALIST_INITIAL_SIZE);
 355         if (!ret) {
 356                 log_debug("Unable to initialise the list for LMB free IOVA\n");
 357                 return -ENOMEM;
 358         }
 359
 360         ret = alist_init(&io_lmb->used_mem, sizeof(struct lmb_region),
 361                          (uint)LMB_ALIST_INITIAL_SIZE);
 362         if (!ret) {
 363                 log_debug("Unable to initialise the list for LMB used IOVA\n");
 364                 return -ENOMEM;
 365         }
 366
 367         io_lmb->test = false;
 368
 369         return 0;
 370 }
 371
 372 void io_lmb_teardown(struct lmb *io_lmb)
 373 {
 374         alist_uninit(&io_lmb->available_mem);
 375         alist_uninit(&io_lmb->used_mem);
 376 }
 377
 378 long io_lmb_add(struct lmb *io_lmb, phys_addr_t base, phys_size_t size)
 379 {
 380         return lmb_add_region_flags(&io_lmb->available_mem, base, size, LMB_NONE);
 381 }
 382
 383 /* derived and simplified from _lmb_alloc_base() */
 384 phys_addr_t io_lmb_alloc(struct lmb *io_lmb, phys_size_t size, ulong align)
 385 {
 386         long i, rgn;
 387         phys_addr_t base = 0;
 388         phys_addr_t res_base;
 389         struct lmb_region *lmb_used = io_lmb->used_mem.data;
 390         struct lmb_region *lmb_memory = io_lmb->available_mem.data;
 391
 392         for (i = io_lmb->available_mem.count - 1; i >= 0; i--) {
 393                 phys_addr_t lmbbase = lmb_memory[i].base;
 394                 phys_size_t lmbsize = lmb_memory[i].size;
 395
 396                 if (lmbsize < size)
 397                         continue;
 398                 base = ALIGN_DOWN(lmbbase + lmbsize - size, align);
 399
 400                 while (base && lmbbase <= base) {
 401                         rgn = lmb_overlaps_region(&io_lmb->used_mem, base, size);
 402                         if (rgn < 0) {
 403                                 /* This area isn't reserved, take it */
 404                                 if (lmb_add_region_flags(&io_lmb->used_mem, base,
 405                                                          size, LMB_NONE) < 0)
 406                                         return 0;
 407
 408                                 return base;
 409                         }
 410
 411                         res_base = lmb_used[rgn].base;
 412                         if (res_base < size)
 413                                 break;
 414                         base = ALIGN_DOWN(res_base - size, align);
 415                 }
 416         }
 417         return 0;
 418 }
 419
 420 long io_lmb_free(struct lmb *io_lmb, phys_addr_t base, phys_size_t size)
 421 {
 422         return _lmb_free(&io_lmb->used_mem, base, size);
 423 }
 424
 425 /*
 426  * Low level LMB functions are used to manage IOVA memory maps for the Apple
 427  * dart iommu. They must not access the global LMB memory map.
 428  * So keep the global LMB variable declaration unreachable from them.
 429  */
 430
 431 static struct lmb lmb;
 432
 433 static bool lmb_should_notify(u32 flags)
 434 {
 435         return !lmb.test && !(flags & LMB_NONOTIFY) &&
 436                 CONFIG_IS_ENABLED(EFI_LOADER);
 437 }
 438
 439 static int lmb_map_update_notify(phys_addr_t addr, phys_size_t size, u8 op,
 440                                  u32 flags)
 441 {
 442         u64 efi_addr;
 443         u64 pages;
 444         efi_status_t status;
 445
 446         if (op != MAP_OP_RESERVE && op != MAP_OP_FREE && op != MAP_OP_ADD) {
 447                 log_err("Invalid map update op received (%d)\n", op);
 448                 return -1;
 449         }
 450
 451         if (!lmb_should_notify(flags))
 452                 return 0;
 453
 454         efi_addr = (uintptr_t)map_sysmem(addr, 0);
 455         pages = efi_size_in_pages(size + (efi_addr & EFI_PAGE_MASK));
 456         efi_addr &= ~EFI_PAGE_MASK;
 457
 458         status = efi_add_memory_map_pg(efi_addr, pages,
 459                                        op == MAP_OP_RESERVE ?
 460                                        EFI_BOOT_SERVICES_DATA :
 461                                        EFI_CONVENTIONAL_MEMORY,
 462                                        false);
 463         if (status != EFI_SUCCESS) {
 464                 log_err("%s: LMB Map notify failure %lu\n", __func__,
 465                         status & ~EFI_ERROR_MASK);
 466                 return -1;
 467         }
 468         unmap_sysmem((void *)(uintptr_t)efi_addr);
 469
 470         return 0;
 471 }
 472
 473 static void lmb_print_region_flags(u32 flags)
 474 {
 475         const char * const flag_str[] = { "none", "no-map", "no-overwrite",
 476                                           "no-notify" };
 477         unsigned int pflags = flags &
 478                               (LMB_NOMAP | LMB_NOOVERWRITE | LMB_NONOTIFY);
 479
 480         if (flags != pflags) {
 481                 printf("invalid %#x\n", flags);
 482                 return;
 483         }
 484
 485         do {
 486                 int bitpos = pflags ? fls(pflags) - 1 : 0;
 487
 488                 printf("%s", flag_str[bitpos]);
 489                 pflags &= ~(1u << bitpos);
 490                 puts(pflags ? ", " : "\n");
 491         } while (pflags);
 492 }
 493
 494 static void lmb_dump_region(struct alist *lmb_rgn_lst, char *name)
 495 {
 496         struct lmb_region *rgn = lmb_rgn_lst->data;
 497         unsigned long long base, size, end;
 498         u32 flags;
 499         int i;
 500
 501         printf(" %s.count = %#x\n", name, lmb_rgn_lst->count);
 502
 503         for (i = 0; i < lmb_rgn_lst->count; i++) {
 504                 base = rgn[i].base;
 505                 size = rgn[i].size;
 506                 end = base + size - 1;
 507                 flags = rgn[i].flags;
 508
 509                 printf(" %s[%d]\t[%#llx-%#llx], %#llx bytes, flags: ",
 510                        name, i, base, end, size);
 511                 lmb_print_region_flags(flags);
 512         }
 513 }
 514
 515 void lmb_dump_all_force(void)
 516 {
 517         printf("lmb_dump_all:\n");
 518         lmb_dump_region(&lmb.available_mem, "memory");
 519         lmb_dump_region(&lmb.used_mem, "reserved");
 520 }
 521
 522 void lmb_dump_all(void)
 523 {
 524 #ifdef DEBUG
 525         lmb_dump_all_force();
 526 #endif
 527 }
 528
 529 static void lmb_reserve_uboot_region(void)
 530 {
 531         int bank;
 532         ulong end, bank_end;
 533         phys_addr_t rsv_start;
 534
 535         rsv_start = gd->start_addr_sp - CONFIG_STACK_SIZE;
 536         end = gd->ram_top;
 537
 538         /*
 539          * Reserve memory from aligned address below the bottom of U-Boot stack
 540          * until end of RAM area to prevent LMB from overwriting that memory.
 541          */
 542         debug("## Current stack ends at 0x%08lx ", (ulong)rsv_start);
 543
 544         for (bank = 0; bank < CONFIG_NR_DRAM_BANKS; bank++) {
 545                 if (!gd->bd->bi_dram[bank].size ||
 546                     rsv_start < gd->bd->bi_dram[bank].start)
 547                         continue;
 548                 /* Watch out for RAM at end of address space! */
 549                 bank_end = gd->bd->bi_dram[bank].start +
 550                         gd->bd->bi_dram[bank].size - 1;
 551                 if (rsv_start > bank_end)
 552                         continue;
 553                 if (bank_end > end)
 554                         bank_end = end - 1;
 555
 556                 lmb_reserve(rsv_start, bank_end - rsv_start + 1, LMB_NOOVERWRITE);
 557
 558                 if (gd->flags & GD_FLG_SKIP_RELOC)
 559                         lmb_reserve((phys_addr_t)(uintptr_t)_start,
 560                                     gd->mon_len, LMB_NOOVERWRITE);
 561
 562                 break;
 563         }
 564 }
 565
 566 static void lmb_reserve_common(void *fdt_blob)
 567 {
 568         lmb_reserve_uboot_region();
 569
 570         if (CONFIG_IS_ENABLED(OF_LIBFDT) && fdt_blob)
 571                 boot_fdt_add_mem_rsv_regions(fdt_blob);
 572 }
 573
 574 static __maybe_unused void lmb_reserve_common_spl(void)
 575 {
 576         phys_addr_t rsv_start;
 577         phys_size_t rsv_size;
 578
 579         /*
 580          * Assume a SPL stack of 16KB. This must be
 581          * more than enough for the SPL stage.
 582          */
 583         if (IS_ENABLED(CONFIG_SPL_STACK_R_ADDR)) {
 584                 rsv_start = gd->start_addr_sp - 16384;
 585                 rsv_size = 16384;
 586                 lmb_reserve(rsv_start, rsv_size, LMB_NOOVERWRITE);
 587         }
 588
 589         if (IS_ENABLED(CONFIG_SPL_SEPARATE_BSS)) {
 590                 /* Reserve the bss region */
 591                 rsv_start = (phys_addr_t)(uintptr_t)__bss_start;
 592                 rsv_size = (phys_addr_t)(uintptr_t)__bss_end -
 593                         (phys_addr_t)(uintptr_t)__bss_start;
 594                 lmb_reserve(rsv_start, rsv_size, LMB_NOOVERWRITE);
 595         }
 596 }
 597
 598 void lmb_add_memory(void)
 599 {
 600         int i;
 601         phys_addr_t bank_end;
 602         phys_size_t size;
 603         u64 ram_top = gd->ram_top;
 604         struct bd_info *bd = gd->bd;
 605
 606         if (CONFIG_IS_ENABLED(LMB_ARCH_MEM_MAP))
 607                 return lmb_arch_add_memory();
 608
 609         /* Assume a 4GB ram_top if not defined */
 610         if (!ram_top)
 611                 ram_top = 0x100000000ULL;
 612
 613         for (i = 0; i < CONFIG_NR_DRAM_BANKS; i++) {
 614                 size = bd->bi_dram[i].size;
 615                 bank_end = bd->bi_dram[i].start + size;
 616
 617                 if (size) {
 618                         lmb_add(bd->bi_dram[i].start, size);
 619
 620                         /*
 621                          * Reserve memory above ram_top as
 622                          * no-overwrite so that it cannot be
 623                          * allocated
 624                          */
 625                         if (bd->bi_dram[i].start >= ram_top)
 626                                 lmb_reserve(bd->bi_dram[i].start, size,
 627                                             LMB_NOOVERWRITE);
 628                         else if (bank_end > ram_top)
 629                                 lmb_reserve(ram_top, bank_end - ram_top,
 630                                             LMB_NOOVERWRITE);
 631                 }
 632         }
 633 }
 634
 635 /* This routine may be called with relocation disabled. */
 636 long lmb_add(phys_addr_t base, phys_size_t size)
 637 {
 638         long ret;
 639         struct alist *lmb_rgn_lst = &lmb.available_mem;
 640
 641         ret = lmb_add_region_flags(lmb_rgn_lst, base, size, LMB_NONE);
 642         if (ret)
 643                 return ret;
 644
 645         return lmb_map_update_notify(base, size, MAP_OP_ADD, LMB_NONE);
 646 }
 647
 648 long lmb_free_flags(phys_addr_t base, phys_size_t size,
 649                     uint flags)
 650 {
 651         long ret;
 652
 653         ret = _lmb_free(&lmb.used_mem, base, size);
 654         if (ret < 0)
 655                 return ret;
 656
 657         return lmb_map_update_notify(base, size, MAP_OP_FREE, flags);
 658 }
 659
 660 long lmb_free(phys_addr_t base, phys_size_t size)
 661 {
 662         return lmb_free_flags(base, size, LMB_NONE);
 663 }
 664
 665 long lmb_reserve(phys_addr_t base, phys_size_t size, u32 flags)
 666 {
 667         long ret = 0;
 668         struct alist *lmb_rgn_lst = &lmb.used_mem;
 669
 670         ret = lmb_add_region_flags(lmb_rgn_lst, base, size, flags);
 671         if (ret)
 672                 return ret;
 673
 674         return lmb_map_update_notify(base, size, MAP_OP_RESERVE, flags);
 675 }
 676
 677 static phys_addr_t _lmb_alloc_base(phys_size_t size, ulong align,
 678                                    phys_addr_t max_addr, u32 flags)
 679 {
 680         int ret;
 681         long i, rgn;
 682         phys_addr_t base = 0;
 683         phys_addr_t res_base;
 684         struct lmb_region *lmb_used = lmb.used_mem.data;
 685         struct lmb_region *lmb_memory = lmb.available_mem.data;
 686
 687         for (i = lmb.available_mem.count - 1; i >= 0; i--) {
 688                 phys_addr_t lmbbase = lmb_memory[i].base;
 689                 phys_size_t lmbsize = lmb_memory[i].size;
 690
 691                 if (lmbsize < size)
 692                         continue;
 693
 694                 if (max_addr == LMB_ALLOC_ANYWHERE) {
 695                         base = ALIGN_DOWN(lmbbase + lmbsize - size, align);
 696                 } else if (lmbbase < max_addr) {
 697                         base = lmbbase + lmbsize;
 698                         if (base < lmbbase)
 699                                 base = -1;
 700                         base = min(base, max_addr);
 701                         base = ALIGN_DOWN(base - size, align);
 702                 } else {
 703                         continue;
 704                 }
 705
 706                 while (base && lmbbase <= base) {
 707                         rgn = lmb_overlaps_region(&lmb.used_mem, base, size);
 708                         if (rgn < 0) {
 709                                 /* This area isn't reserved, take it */
 710                                 if (lmb_add_region_flags(&lmb.used_mem, base,
 711                                                          size, flags))
 712                                         return 0;
 713
 714                                 ret = lmb_map_update_notify(base, size,
 715                                                             MAP_OP_RESERVE,
 716                                                             flags);
 717                                 if (ret)
 718                                         return ret;
 719
 720                                 return base;
 721                         }
 722
 723                         res_base = lmb_used[rgn].base;
 724                         if (res_base < size)
 725                                 break;
 726                         base = ALIGN_DOWN(res_base - size, align);
 727                 }
 728         }
 729         return 0;
 730 }
 731
 732 phys_addr_t lmb_alloc(phys_size_t size, ulong align)
 733 {
 734         return lmb_alloc_base(size, align, LMB_ALLOC_ANYWHERE);
 735 }
 736
 737 phys_addr_t lmb_alloc_base(phys_size_t size, ulong align, phys_addr_t max_addr)
 738 {
 739         phys_addr_t alloc;
 740
 741         alloc = _lmb_alloc_base(size, align, max_addr, LMB_NONE);
 742
 743         if (alloc == 0)
 744                 printf("ERROR: Failed to allocate 0x%lx bytes below 0x%lx.\n",
 745                        (ulong)size, (ulong)max_addr);
 746
 747         return alloc;
 748 }
 749
 750 phys_addr_t lmb_alloc_base_flags(phys_size_t size, ulong align,
 751                                  phys_addr_t max_addr, uint flags)
 752 {
 753         phys_addr_t alloc;
 754
 755         alloc = _lmb_alloc_base(size, align, max_addr, flags);
 756
 757         if (alloc == 0)
 758                 printf("ERROR: Failed to allocate 0x%lx bytes below 0x%lx.\n",
 759                        (ulong)size, (ulong)max_addr);
 760
 761         return alloc;
 762 }
 763
 764 static phys_addr_t _lmb_alloc_addr(phys_addr_t base, phys_size_t size, u32 flags)
 765 {
 766         long rgn;
 767         struct lmb_region *lmb_memory = lmb.available_mem.data;
 768
 769         /* Check if the requested address is in one of the memory regions */
 770         rgn = lmb_overlaps_region(&lmb.available_mem, base, size);
 771         if (rgn >= 0) {
 772                 /*
 773                  * Check if the requested end address is in the same memory
 774                  * region we found.
 775                  */
 776                 if (lmb_addrs_overlap(lmb_memory[rgn].base,
 777                                       lmb_memory[rgn].size,
 778                                       base + size - 1, 1)) {
 779                         /* ok, reserve the memory */
 780                         if (!lmb_reserve(base, size, flags))
 781                                 return base;
 782                 }
 783         }
 784
 785         return 0;
 786 }
 787
 788 phys_addr_t lmb_alloc_addr(phys_addr_t base, phys_size_t size, uint flags)
 789 {
 790         return _lmb_alloc_addr(base, size, flags);
 791 }
 792
 793 /* Return number of bytes from a given address that are free */
 794 phys_size_t lmb_get_free_size(phys_addr_t addr)
 795 {
 796         int i;
 797         long rgn;
 798         struct lmb_region *lmb_used = lmb.used_mem.data;
 799         struct lmb_region *lmb_memory = lmb.available_mem.data;
 800
 801         /* check if the requested address is in the memory regions */
 802         rgn = lmb_overlaps_region(&lmb.available_mem, addr, 1);
 803         if (rgn >= 0) {
 804                 for (i = 0; i < lmb.used_mem.count; i++) {
 805                         if (addr < lmb_used[i].base) {
 806                                 /* first reserved range > requested address */
 807                                 return lmb_used[i].base - addr;
 808                         }
 809                         if (lmb_used[i].base +
 810                             lmb_used[i].size > addr) {
 811                                 /* requested addr is in this reserved range */
 812                                 return 0;
 813                         }
 814                 }
 815                 /* if we come here: no reserved ranges above requested addr */
 816                 return lmb_memory[lmb.available_mem.count - 1].base +
 817                        lmb_memory[lmb.available_mem.count - 1].size - addr;
 818         }
 819         return 0;
 820 }
 821
 822 int lmb_is_reserved_flags(phys_addr_t addr, int flags)
 823 {
 824         int i;
 825         struct lmb_region *lmb_used = lmb.used_mem.data;
 826
 827         for (i = 0; i < lmb.used_mem.count; i++) {
 828                 phys_addr_t upper = lmb_used[i].base +
 829                         lmb_used[i].size - 1;
 830                 if (addr >= lmb_used[i].base && addr <= upper)
 831                         return (lmb_used[i].flags & flags) == flags;
 832         }
 833         return 0;
 834 }
 835
 836 static int lmb_setup(bool test)
 837 {
 838         bool ret;
 839
 840         ret = alist_init(&lmb.available_mem, sizeof(struct lmb_region),
 841                          (uint)LMB_ALIST_INITIAL_SIZE);
 842         if (!ret) {
 843                 log_debug("Unable to initialise the list for LMB free memory\n");
 844                 return -ENOMEM;
 845         }
 846
 847         ret = alist_init(&lmb.used_mem, sizeof(struct lmb_region),
 848                          (uint)LMB_ALIST_INITIAL_SIZE);
 849         if (!ret) {
 850                 log_debug("Unable to initialise the list for LMB used memory\n");
 851                 return -ENOMEM;
 852         }
 853
 854         lmb.test = test;
 855
 856         return 0;
 857 }
 858
 859 int lmb_init(void)
 860 {
 861         int ret;
 862
 863         ret = lmb_setup(false);
 864         if (ret) {
 865                 log_info("Unable to init LMB\n");
 866                 return ret;
 867         }
 868
 869         lmb_add_memory();
 870
 871         /* Reserve the U-Boot image region once U-Boot has relocated */
 872         if (xpl_phase() == PHASE_SPL)
 873                 lmb_reserve_common_spl();
 874         else if (xpl_phase() == PHASE_BOARD_R)
 875                 lmb_reserve_common((void *)gd->fdt_blob);
 876
 877         return 0;
 878 }
 879
 880 struct lmb *lmb_get(void)
 881 {
 882         return &lmb;
 883 }
 884
 885 #if CONFIG_IS_ENABLED(UNIT_TEST)
 886 int lmb_push(struct lmb *store)
 887 {
 888         int ret;
 889
 890         *store = lmb;
 891         ret = lmb_setup(true);
 892         if (ret)
 893                 return ret;
 894
 895         return 0;
 896 }
 897
 898 void lmb_pop(struct lmb *store)
 899 {
 900         alist_uninit(&lmb.available_mem);
 901         alist_uninit(&lmb.used_mem);
 902         lmb = *store;
 903 }
 904 #endif /* UNIT_TEST */