src/lib/memrange.c

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2
   3 #include <assert.h>
   4 #include <stdlib.h>
   5 #include <commonlib/helpers.h>
   6 #include <console/console.h>
   7 #include <memrange.h>
   8
   9 static inline void range_entry_link(struct range_entry **prev_ptr,
  10                                     struct range_entry *r)
  11 {
  12         r->next = *prev_ptr;
  13         *prev_ptr = r;
  14 }
  15
  16 static inline void range_entry_unlink(struct range_entry **prev_ptr,
  17                                       struct range_entry *r)
  18 {
  19         *prev_ptr = r->next;
  20         r->next = NULL;
  21 }
  22
  23 static inline void range_entry_unlink_and_free(struct memranges *ranges,
  24                                                struct range_entry **prev_ptr,
  25                                                struct range_entry *r)
  26 {
  27         range_entry_unlink(prev_ptr, r);
  28         range_entry_link(&ranges->free_list, r);
  29 }
  30
  31 static struct range_entry *alloc_range(struct memranges *ranges)
  32 {
  33         if (ranges->free_list != NULL) {
  34                 struct range_entry *r;
  35
  36                 r = ranges->free_list;
  37                 range_entry_unlink(&ranges->free_list, r);
  38                 return r;
  39         }
  40         if (ENV_PAYLOAD_LOADER)
  41                 return malloc(sizeof(struct range_entry));
  42         return NULL;
  43 }
  44
  45 static inline struct range_entry *
  46 range_list_add(struct memranges *ranges, struct range_entry **prev_ptr,
  47                resource_t begin, resource_t end, unsigned long tag)
  48 {
  49         struct range_entry *new_entry;
  50
  51         new_entry = alloc_range(ranges);
  52         if (new_entry == NULL) {
  53                 printk(BIOS_ERR, "Could not allocate range_entry!\n");
  54                 return NULL;
  55         }
  56         new_entry->begin = begin;
  57         new_entry->end = end;
  58         new_entry->tag = tag;
  59         range_entry_link(prev_ptr, new_entry);
  60
  61         return new_entry;
  62 }
  63
  64 static void merge_neighbor_entries(struct memranges *ranges)
  65 {
  66         struct range_entry *cur;
  67         struct range_entry *prev;
  68
  69         prev = NULL;
  70         /* Merge all neighbors and delete/free the leftover entry. */
  71         for (cur = ranges->entries; cur != NULL; cur = cur->next) {
  72                 /* First entry. Just set prev. */
  73                 if (prev == NULL) {
  74                         prev = cur;
  75                         continue;
  76                 }
  77
  78                 /* If the previous entry merges with the current update the
  79                  * previous entry to cover full range and delete current from
  80                  * the list. */
  81                 if (prev->end + 1 >= cur->begin && prev->tag == cur->tag) {
  82                         prev->end = cur->end;
  83                         range_entry_unlink_and_free(ranges, &prev->next, cur);
  84                         /* Set cur to prev so cur->next is valid since cur
  85                          * was just unlinked and free. */
  86                         cur = prev;
  87                         continue;
  88                 }
  89
  90                 prev = cur;
  91         }
  92 }
  93
  94 static void remove_memranges(struct memranges *ranges,
  95                              resource_t begin, resource_t end,
  96                              unsigned long unused)
  97 {
  98         struct range_entry *cur;
  99         struct range_entry *next;
 100         struct range_entry **prev_ptr;
 101
 102         prev_ptr = &ranges->entries;
 103         for (cur = ranges->entries; cur != NULL; cur = next) {
 104                 resource_t tmp_end;
 105
 106                 /* Cache the next value to handle unlinks. */
 107                 next = cur->next;
 108
 109                 /* No other ranges are affected. */
 110                 if (end < cur->begin)
 111                         break;
 112
 113                 /* The removal range starts after this one. */
 114                 if (begin > cur->end) {
 115                         prev_ptr = &cur->next;
 116                         continue;
 117                 }
 118
 119                 /* The removal range overlaps with the current entry either
 120                  * partially or fully. However, we need to adjust the removal
 121                  * range for any holes. */
 122                 if (begin <= cur->begin) {
 123                         begin = cur->begin;
 124
 125                         /* Full removal. */
 126                         if (end >= cur->end) {
 127                                 begin = cur->end + 1;
 128                                 range_entry_unlink_and_free(ranges, prev_ptr,
 129                                                             cur);
 130                                 continue;
 131                         }
 132                 }
 133
 134                 /* prev_ptr can be set now that the unlink path wasn't taken. */
 135                 prev_ptr = &cur->next;
 136
 137                 /* Clip the end fragment to do proper splitting. */
 138                 tmp_end = end;
 139                 if (end > cur->end)
 140                         tmp_end = cur->end;
 141
 142                 /* Hole punched in middle of entry. */
 143                 if (begin > cur->begin && tmp_end < cur->end) {
 144                         range_list_add(ranges, &cur->next, end + 1, cur->end,
 145                                        cur->tag);
 146                         cur->end = begin - 1;
 147                         break;
 148                 }
 149
 150                 /* Removal at beginning. */
 151                 if (begin == cur->begin)
 152                         cur->begin = tmp_end + 1;
 153
 154                 /* Removal at end. */
 155                 if (tmp_end == cur->end)
 156                         cur->end = begin - 1;
 157         }
 158 }
 159
 160 static void merge_add_memranges(struct memranges *ranges,
 161                                 resource_t begin, resource_t end,
 162                                 unsigned long tag)
 163 {
 164         struct range_entry *cur;
 165         struct range_entry **prev_ptr;
 166
 167         prev_ptr = &ranges->entries;
 168
 169         /* Remove all existing entries covered by the range. */
 170         remove_memranges(ranges, begin, end, -1);
 171
 172         /* Find the entry to place the new entry after. Since
 173          * remove_memranges() was called above there is a guaranteed
 174          * spot for this new entry. */
 175         for (cur = ranges->entries; cur != NULL; cur = cur->next) {
 176                 /* Found insertion spot before current entry. */
 177                 if (end < cur->begin)
 178                         break;
 179
 180                 /* Keep track of previous entry to insert new entry after it. */
 181                 prev_ptr = &cur->next;
 182
 183                 /* The new entry starts after this one. */
 184                 if (begin > cur->end)
 185                         continue;
 186
 187         }
 188
 189         /* Add new entry and merge with neighbors. */
 190         range_list_add(ranges, prev_ptr, begin, end, tag);
 191         merge_neighbor_entries(ranges);
 192 }
 193
 194 void memranges_update_tag(struct memranges *ranges, unsigned long old_tag,
 195                           unsigned long new_tag)
 196 {
 197         struct range_entry *r;
 198
 199         memranges_each_entry(r, ranges) {
 200                 if (range_entry_tag(r) == old_tag)
 201                         range_entry_update_tag(r, new_tag);
 202         }
 203
 204         merge_neighbor_entries(ranges);
 205 }
 206
 207 typedef void (*range_action_t)(struct memranges *ranges,
 208                                resource_t begin, resource_t end,
 209                                unsigned long tag);
 210
 211 static void do_action(struct memranges *ranges,
 212                       resource_t base, resource_t size, unsigned long tag,
 213                        range_action_t action)
 214 {
 215         resource_t end;
 216         resource_t begin;
 217
 218         if (size == 0)
 219                 return;
 220
 221         /* The addresses are aligned to (1ULL << ranges->align): the begin address is
 222          * aligned down while the end address is aligned up to be conservative
 223          * about the full range covered. */
 224         begin = ALIGN_DOWN(base, POWER_OF_2(ranges->align));
 225         end = begin + size + (base - begin);
 226         end = ALIGN_UP(end, POWER_OF_2(ranges->align)) - 1;
 227         action(ranges, begin, end, tag);
 228 }
 229
 230 void memranges_create_hole(struct memranges *ranges,
 231                            resource_t base, resource_t size)
 232 {
 233         do_action(ranges, base, size, -1, remove_memranges);
 234 }
 235
 236 void memranges_insert(struct memranges *ranges,
 237                       resource_t base, resource_t size, unsigned long tag)
 238 {
 239         do_action(ranges, base, size, tag, merge_add_memranges);
 240 }
 241
 242 struct collect_context {
 243         struct memranges *ranges;
 244         unsigned long tag;
 245         memrange_filter_t filter;
 246 };
 247
 248 static void collect_ranges(void *gp, struct device *dev, struct resource *res)
 249 {
 250         struct collect_context *ctx = gp;
 251
 252         if (res->size == 0)
 253                 return;
 254
 255         if (ctx->filter == NULL || ctx->filter(dev, res))
 256                 memranges_insert(ctx->ranges, res->base, res->size, ctx->tag);
 257 }
 258
 259 void memranges_add_resources_filter(struct memranges *ranges,
 260                                     unsigned long mask, unsigned long match,
 261                                     unsigned long tag,
 262                                     memrange_filter_t filter)
 263 {
 264         struct collect_context context;
 265
 266         /* Only deal with MEM resources. */
 267         mask |= IORESOURCE_MEM;
 268         match |= IORESOURCE_MEM;
 269
 270         context.ranges = ranges;
 271         context.tag = tag;
 272         context.filter = filter;
 273         search_global_resources(mask, match, collect_ranges, &context);
 274 }
 275
 276 void memranges_add_resources(struct memranges *ranges,
 277                              unsigned long mask, unsigned long match,
 278                              unsigned long tag)
 279 {
 280         memranges_add_resources_filter(ranges, mask, match, tag, NULL);
 281 }
 282
 283 void memranges_init_empty_with_alignment(struct memranges *ranges,
 284                                          struct range_entry *to_free,
 285                                          size_t num_free, unsigned char align)
 286 {
 287         size_t i;
 288
 289         ranges->entries = NULL;
 290         ranges->free_list = NULL;
 291         ranges->align = align;
 292
 293         for (i = 0; i < num_free; i++)
 294                 range_entry_link(&ranges->free_list, &to_free[i]);
 295 }
 296
 297 void memranges_init_with_alignment(struct memranges *ranges,
 298                                    unsigned long mask, unsigned long match,
 299                                    unsigned long tag, unsigned char align)
 300 {
 301         memranges_init_empty_with_alignment(ranges, NULL, 0, align);
 302         memranges_add_resources(ranges, mask, match, tag);
 303 }
 304
 305 /* Clone a memrange. The new memrange has the same entries as the old one. */
 306 void memranges_clone(struct memranges *newranges, struct memranges *oldranges)
 307 {
 308         struct range_entry *r, *cur;
 309         struct range_entry **prev_ptr;
 310
 311         memranges_init_empty_with_alignment(newranges, NULL, 0, oldranges->align);
 312
 313         prev_ptr = &newranges->entries;
 314         memranges_each_entry(r, oldranges) {
 315                 cur = range_list_add(newranges, prev_ptr, r->begin, r->end,
 316                                      r->tag);
 317                 prev_ptr = &cur->next;
 318         }
 319 }
 320
 321 void memranges_teardown(struct memranges *ranges)
 322 {
 323         while (ranges->entries != NULL) {
 324                 range_entry_unlink_and_free(ranges, &ranges->entries,
 325                                             ranges->entries);
 326         }
 327 }
 328
 329 void memranges_fill_holes_up_to(struct memranges *ranges,
 330                                 resource_t limit, unsigned long tag)
 331 {
 332         struct range_entry *cur;
 333         struct range_entry *prev;
 334
 335         prev = NULL;
 336         for (cur = ranges->entries; cur != NULL; cur = cur->next) {
 337                 /* First entry. Just set prev. */
 338                 if (prev == NULL) {
 339                         prev = cur;
 340                         continue;
 341                 }
 342
 343                 /* If the previous entry does not directly precede the current
 344                  * entry then add a new entry just after the previous one. */
 345                 if (range_entry_end(prev) != cur->begin) {
 346                         resource_t end;
 347
 348                         end = cur->begin - 1;
 349                         if (end >= limit)
 350                                 end = limit - 1;
 351                         range_list_add(ranges, &prev->next,
 352                                        range_entry_end(prev), end, tag);
 353                 }
 354
 355                 prev = cur;
 356
 357                 /* Hit the requested range limit. No other entries after this
 358                  * are affected. */
 359                 if (cur->begin >= limit)
 360                         break;
 361         }
 362
 363         /* Handle the case where the limit was never reached. A new entry needs
 364          * to be added to cover the range up to the limit. */
 365         if (prev != NULL && range_entry_end(prev) < limit)
 366                 range_list_add(ranges, &prev->next, range_entry_end(prev),
 367                                limit - 1, tag);
 368
 369         /* Merge all entries that were newly added. */
 370         merge_neighbor_entries(ranges);
 371 }
 372
 373 struct range_entry *memranges_next_entry(struct memranges *ranges,
 374                                          const struct range_entry *r)
 375 {
 376         return r->next;
 377 }
 378
 379 /* Find a range entry that satisfies the given constraints to fit a hole that matches the
 380  * required alignment, is big enough, does not exceed the limit and has a matching tag. */
 381 static const struct range_entry *
 382 memranges_find_entry(struct memranges *ranges, resource_t limit, resource_t size,
 383                      unsigned char align, unsigned long tag, bool last)
 384 {
 385         const struct range_entry *r, *last_entry = NULL;
 386         resource_t base, end;
 387
 388         if (size == 0)
 389                 return NULL;
 390
 391         memranges_each_entry(r, ranges) {
 392
 393                 if (r->tag != tag)
 394                         continue;
 395
 396                 base = ALIGN_UP(r->begin, POWER_OF_2(align));
 397                 end = base + size - 1;
 398
 399                 if (end > r->end)
 400                         continue;
 401
 402                 /*
 403                  * If end for the hole in the current range entry goes beyond the requested
 404                  * limit, then none of the following ranges can satisfy this request because all
 405                  * range entries are maintained in increasing order.
 406                  */
 407                 if (end > limit)
 408                         break;
 409
 410                 if (!last)
 411                         return r;
 412
 413                 last_entry = r;
 414         }
 415
 416         return last_entry;
 417 }
 418
 419 bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size,
 420                         unsigned char align, unsigned long tag, resource_t *stolen_base,
 421                         bool from_top)
 422 {
 423         const struct range_entry *r;
 424
 425         r = memranges_find_entry(ranges, limit, size, align, tag, from_top);
 426         if (r == NULL)
 427                 return false;
 428
 429         if (from_top) {
 430                 limit = MIN(limit, r->end);
 431                 /* Ensure we're within the range, even aligned down.
 432                    Proof is simple: If ALIGN_UP(r->begin) would be
 433                    higher, the stolen range wouldn't fit.*/
 434                 assert(r->begin <= ALIGN_DOWN(limit - size + 1, POWER_OF_2(align)));
 435                 *stolen_base = ALIGN_DOWN(limit - size + 1, POWER_OF_2(align));
 436         } else {
 437                 *stolen_base = ALIGN_UP(r->begin, POWER_OF_2(align));
 438         }
 439         memranges_create_hole(ranges, *stolen_base, size);
 440
 441         return true;
 442 }