grub-core/mmap/mmap.c

   1 /* Mmap management. */
   2 /*
   3  *  GRUB  --  GRand Unified Bootloader
   4  *  Copyright (C) 2009  Free Software Foundation, Inc.
   5  *
   6  *  GRUB is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  GRUB is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <grub/memory.h>
  21 #include <grub/machine/memory.h>
  22 #include <grub/err.h>
  23 #include <grub/misc.h>
  24 #include <grub/mm.h>
  25 #include <grub/command.h>
  26 #include <grub/dl.h>
  27 #include <grub/i18n.h>
  28
  29 GRUB_MOD_LICENSE ("GPLv3+");
  30
  31 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  32
  33 struct grub_mmap_region *grub_mmap_overlays = 0;
  34 static int curhandle = 1;
  35
  36 #endif
  37
  38 static int current_priority = 1;
  39
  40 /* Scanline events. */
  41 struct grub_mmap_scan
  42 {
  43   /* At which memory address. */
  44   grub_uint64_t pos;
  45   /* 0 = region starts, 1 = region ends. */
  46   int type;
  47   /* Which type of memory region? */
  48   grub_memory_type_t memtype;
  49   /* Priority. 0 means coming from firmware.  */
  50   int priority;
  51 };
  52
  53 /* Context for grub_mmap_iterate.  */
  54 struct grub_mmap_iterate_ctx
  55 {
  56   struct grub_mmap_scan *scanline_events;
  57   int i;
  58 };
  59
  60 /* Helper for grub_mmap_iterate.  */
  61 static int
  62 count_hook (grub_uint64_t addr __attribute__ ((unused)),
  63             grub_uint64_t size __attribute__ ((unused)),
  64             grub_memory_type_t type __attribute__ ((unused)), void *data)
  65 {
  66   int *mmap_num = data;
  67
  68   (*mmap_num)++;
  69   return 0;
  70 }
  71
  72 /* Helper for grub_mmap_iterate.  */
  73 static int
  74 fill_hook (grub_uint64_t addr, grub_uint64_t size, grub_memory_type_t type,
  75            void *data)
  76 {
  77   struct grub_mmap_iterate_ctx *ctx = data;
  78
  79   if (type == GRUB_MEMORY_HOLE)
  80     {
  81       grub_dprintf ("mmap", "Unknown memory type %d. Assuming unusable\n",
  82                     type);
  83       type = GRUB_MEMORY_RESERVED;
  84     }
  85
  86   ctx->scanline_events[ctx->i].pos = addr;
  87   ctx->scanline_events[ctx->i].type = 0;
  88   ctx->scanline_events[ctx->i].memtype = type;
  89   ctx->scanline_events[ctx->i].priority = 0;
  90
  91   ctx->i++;
  92
  93   ctx->scanline_events[ctx->i].pos = addr + size;
  94   ctx->scanline_events[ctx->i].type = 1;
  95   ctx->scanline_events[ctx->i].memtype = type;
  96   ctx->scanline_events[ctx->i].priority = 0;
  97   ctx->i++;
  98
  99   return 0;
 100 }
 101
 102 struct mm_list
 103 {
 104   struct mm_list *next;
 105   grub_memory_type_t val;
 106   int present;
 107 };
 108
 109 grub_err_t
 110 grub_mmap_iterate (grub_memory_hook_t hook, void *hook_data)
 111 {
 112   /* This function resolves overlapping regions and sorts the memory map.
 113      It uses scanline (sweeping) algorithm.
 114   */
 115   struct grub_mmap_iterate_ctx ctx;
 116   int i, done;
 117
 118   struct grub_mmap_scan t;
 119
 120   /* Previous scanline event. */
 121   grub_uint64_t lastaddr;
 122   int lasttype;
 123   /* Current scanline event. */
 124   int curtype;
 125   /* How many regions of given type/priority overlap at current location? */
 126   /* Normally there shouldn't be more than one region per priority but be robust.  */
 127   struct mm_list *present;
 128   /* Number of mmap chunks. */
 129   int mmap_num;
 130
 131 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 132   struct grub_mmap_region *cur;
 133 #endif
 134
 135   mmap_num = 0;
 136
 137 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 138   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 139     mmap_num++;
 140 #endif
 141
 142   grub_machine_mmap_iterate (count_hook, &mmap_num);
 143
 144   /* Initialize variables. */
 145   ctx.scanline_events = (struct grub_mmap_scan *)
 146     grub_malloc (sizeof (struct grub_mmap_scan) * 2 * mmap_num);
 147
 148   present = grub_zalloc (sizeof (present[0]) * current_priority);
 149
 150   if (! ctx.scanline_events || !present)
 151     {
 152       grub_free (ctx.scanline_events);
 153       grub_free (present);
 154       return grub_errno;
 155     }
 156
 157   ctx.i = 0;
 158 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 159   /* Register scanline events. */
 160   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 161     {
 162       ctx.scanline_events[ctx.i].pos = cur->start;
 163       ctx.scanline_events[ctx.i].type = 0;
 164       ctx.scanline_events[ctx.i].memtype = cur->type;
 165       ctx.scanline_events[ctx.i].priority = cur->priority;
 166       ctx.i++;
 167
 168       ctx.scanline_events[ctx.i].pos = cur->end;
 169       ctx.scanline_events[ctx.i].type = 1;
 170       ctx.scanline_events[ctx.i].memtype = cur->type;
 171       ctx.scanline_events[ctx.i].priority = cur->priority;
 172       ctx.i++;
 173     }
 174 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 175
 176   grub_machine_mmap_iterate (fill_hook, &ctx);
 177
 178   /* Primitive bubble sort. It has complexity O(n^2) but since we're
 179      unlikely to have more than 100 chunks it's probably one of the
 180      fastest for one purpose. */
 181   done = 1;
 182   while (done)
 183     {
 184       done = 0;
 185       for (i = 0; i < 2 * mmap_num - 1; i++)
 186         if (ctx.scanline_events[i + 1].pos < ctx.scanline_events[i].pos
 187             || (ctx.scanline_events[i + 1].pos == ctx.scanline_events[i].pos
 188                 && ctx.scanline_events[i + 1].type == 0
 189                 && ctx.scanline_events[i].type == 1))
 190           {
 191             t = ctx.scanline_events[i + 1];
 192             ctx.scanline_events[i + 1] = ctx.scanline_events[i];
 193             ctx.scanline_events[i] = t;
 194             done = 1;
 195           }
 196     }
 197
 198   lastaddr = ctx.scanline_events[0].pos;
 199   lasttype = ctx.scanline_events[0].memtype;
 200   for (i = 0; i < 2 * mmap_num; i++)
 201     {
 202       /* Process event. */
 203       if (ctx.scanline_events[i].type)
 204         {
 205           if (present[ctx.scanline_events[i].priority].present)
 206             {
 207               if (present[ctx.scanline_events[i].priority].val == ctx.scanline_events[i].memtype)
 208                 {
 209                   if (present[ctx.scanline_events[i].priority].next)
 210                     {
 211                       struct mm_list *p = present[ctx.scanline_events[i].priority].next;
 212                       present[ctx.scanline_events[i].priority] = *p;
 213                       grub_free (p);
 214                     }
 215                   else
 216                     {
 217                       present[ctx.scanline_events[i].priority].present = 0;
 218                     }
 219                 }
 220               else
 221                 {
 222                   struct mm_list **q = &(present[ctx.scanline_events[i].priority].next), *p;
 223                   for (; *q; q = &((*q)->next))
 224                     if ((*q)->val == ctx.scanline_events[i].memtype)
 225                       {
 226                         p = *q;
 227                         *q = p->next;
 228                         grub_free (p);
 229                         break;
 230                       }
 231                 }
 232             }
 233         }
 234       else
 235         {
 236           if (!present[ctx.scanline_events[i].priority].present)
 237             {
 238               present[ctx.scanline_events[i].priority].present = 1;
 239               present[ctx.scanline_events[i].priority].val = ctx.scanline_events[i].memtype;
 240             }
 241           else
 242             {
 243               struct mm_list *n = grub_malloc (sizeof (*n));
 244               n->val = ctx.scanline_events[i].memtype;
 245               n->present = 1;
 246               n->next = present[ctx.scanline_events[i].priority].next;
 247               present[ctx.scanline_events[i].priority].next = n;
 248             }
 249         }
 250
 251       /* Determine current region type. */
 252       curtype = -1;
 253       {
 254         int k;
 255         for (k = current_priority - 1; k >= 0; k--)
 256           if (present[k].present)
 257             {
 258               curtype = present[k].val;
 259               break;
 260             }
 261       }
 262
 263       /* Announce region to the hook if necessary. */
 264       if ((curtype == -1 || curtype != lasttype)
 265           && lastaddr != ctx.scanline_events[i].pos
 266           && lasttype != -1
 267           && lasttype != GRUB_MEMORY_HOLE
 268           && hook (lastaddr, ctx.scanline_events[i].pos - lastaddr, lasttype,
 269                    hook_data))
 270         {
 271           grub_free (ctx.scanline_events);
 272           return GRUB_ERR_NONE;
 273         }
 274
 275       /* Update last values if necessary. */
 276       if (curtype == -1 || curtype != lasttype)
 277         {
 278           lasttype = curtype;
 279           lastaddr = ctx.scanline_events[i].pos;
 280         }
 281     }
 282
 283   grub_free (ctx.scanline_events);
 284   return GRUB_ERR_NONE;
 285 }
 286
 287 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 288 int
 289 grub_mmap_register (grub_uint64_t start, grub_uint64_t size, int type)
 290 {
 291   struct grub_mmap_region *cur;
 292
 293   grub_dprintf ("mmap", "registering\n");
 294
 295   cur = (struct grub_mmap_region *)
 296     grub_malloc (sizeof (struct grub_mmap_region));
 297   if (! cur)
 298     return 0;
 299
 300   cur->next = grub_mmap_overlays;
 301   cur->start = start;
 302   cur->end = start + size;
 303   cur->type = type;
 304   cur->handle = curhandle++;
 305   cur->priority = current_priority++;
 306   grub_mmap_overlays = cur;
 307
 308   if (grub_machine_mmap_register (start, size, type, curhandle))
 309     {
 310       grub_mmap_overlays = cur->next;
 311       grub_free (cur);
 312       return 0;
 313     }
 314
 315   return cur->handle;
 316 }
 317
 318 grub_err_t
 319 grub_mmap_unregister (int handle)
 320 {
 321   struct grub_mmap_region *cur, *prev;
 322
 323   for (cur = grub_mmap_overlays, prev = 0; cur; prev = cur, cur = cur->next)
 324     if (handle == cur->handle)
 325       {
 326         grub_err_t err;
 327         err = grub_machine_mmap_unregister (handle);
 328         if (err)
 329           return err;
 330
 331         if (prev)
 332           prev->next = cur->next;
 333         else
 334           grub_mmap_overlays = cur->next;
 335         grub_free (cur);
 336         return GRUB_ERR_NONE;
 337       }
 338   return grub_error (GRUB_ERR_BUG, "mmap overlay not found");
 339 }
 340
 341 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 342
 343 #define CHUNK_SIZE      0x400
 344
 345 struct badram_entry {
 346   grub_uint64_t addr, mask;
 347 };
 348
 349 static inline grub_uint64_t
 350 fill_mask (struct badram_entry *entry, grub_uint64_t iterator)
 351 {
 352   int i, j;
 353   grub_uint64_t ret = (entry->addr & entry->mask);
 354
 355   /* Find first fixed bit. */
 356   for (i = 0; i < 64; i++)
 357     if ((entry->mask & (1ULL << i)) != 0)
 358       break;
 359   j = 0;
 360   for (; i < 64; i++)
 361     if ((entry->mask & (1ULL << i)) == 0)
 362       {
 363         if ((iterator & (1ULL << j)) != 0)
 364           ret |= 1ULL << i;
 365         j++;
 366       }
 367   return ret;
 368 }
 369
 370 /* Helper for grub_cmd_badram.  */
 371 static int
 372 badram_iter (grub_uint64_t addr, grub_uint64_t size,
 373              grub_memory_type_t type __attribute__ ((unused)), void *data)
 374 {
 375   struct badram_entry *entry = data;
 376   grub_uint64_t iterator, low, high, cur;
 377   int tail, var;
 378   int i;
 379   grub_dprintf ("badram", "hook %llx+%llx\n", (unsigned long long) addr,
 380                 (unsigned long long) size);
 381
 382   /* How many trailing zeros? */
 383   for (tail = 0; ! (entry->mask & (1ULL << tail)); tail++);
 384
 385   /* How many zeros in mask? */
 386   var = 0;
 387   for (i = 0; i < 64; i++)
 388     if (! (entry->mask & (1ULL << i)))
 389       var++;
 390
 391   if (fill_mask (entry, 0) >= addr)
 392     iterator = 0;
 393   else
 394     {
 395       low = 0;
 396       high = ~0ULL;
 397       /* Find starting value. Keep low and high such that
 398          fill_mask (low) < addr and fill_mask (high) >= addr;
 399       */
 400       while (high - low > 1)
 401         {
 402           cur = (low + high) / 2;
 403           if (fill_mask (entry, cur) >= addr)
 404             high = cur;
 405           else
 406             low = cur;
 407         }
 408       iterator = high;
 409     }
 410
 411   for (; iterator < (1ULL << (var - tail))
 412          && (cur = fill_mask (entry, iterator)) < addr + size;
 413        iterator++)
 414     {
 415       grub_dprintf ("badram", "%llx (size %llx) is a badram range\n",
 416                     (unsigned long long) cur, (1ULL << tail));
 417       grub_mmap_register (cur, (1ULL << tail), GRUB_MEMORY_HOLE);
 418     }
 419   return 0;
 420 }
 421
 422 static grub_err_t
 423 grub_cmd_badram (grub_command_t cmd __attribute__ ((unused)),
 424                  int argc, char **args)
 425 {
 426   const char *str;
 427   struct badram_entry entry;
 428
 429   if (argc != 1)
 430     return grub_error (GRUB_ERR_BAD_ARGUMENT, N_("one argument expected"));
 431
 432   grub_dprintf ("badram", "executing badram\n");
 433
 434   str = args[0];
 435
 436   while (1)
 437     {
 438       /* Parse address and mask.  */
 439       entry.addr = grub_strtoull (str, &str, 16);
 440       if (*str == ',')
 441         str++;
 442       entry.mask = grub_strtoull (str, &str, 16);
 443       if (*str == ',')
 444         str++;
 445
 446       if (grub_errno == GRUB_ERR_BAD_NUMBER)
 447         {
 448           grub_errno = 0;
 449           return GRUB_ERR_NONE;
 450         }
 451
 452       /* When part of a page is tainted, we discard the whole of it.  There's
 453          no point in providing sub-page chunks.  */
 454       entry.mask &= ~(CHUNK_SIZE - 1);
 455
 456       grub_dprintf ("badram", "badram %llx:%llx\n",
 457                     (unsigned long long) entry.addr,
 458                     (unsigned long long) entry.mask);
 459
 460       grub_mmap_iterate (badram_iter, &entry);
 461     }
 462 }
 463
 464 static grub_uint64_t
 465 parsemem (const char *str)
 466 {
 467   grub_uint64_t ret;
 468   const char *ptr;
 469
 470   ret = grub_strtoul (str, &ptr, 0);
 471
 472   switch (*ptr)
 473     {
 474     case 'K':
 475       return ret << 10;
 476     case 'M':
 477       return ret << 20;
 478     case 'G':
 479       return ret << 30;
 480     case 'T':
 481       return ret << 40;
 482     }
 483   return ret;
 484 }
 485
 486 struct cutmem_range {
 487   grub_uint64_t from, to;
 488 };
 489
 490 /* Helper for grub_cmd_cutmem.  */
 491 static int
 492 cutmem_iter (grub_uint64_t addr, grub_uint64_t size,
 493              grub_memory_type_t type __attribute__ ((unused)), void *data)
 494 {
 495   struct cutmem_range *range = data;
 496   grub_uint64_t end = addr + size;
 497
 498   if (addr <= range->from)
 499     addr = range->from;
 500   if (end >= range->to)
 501     end = range->to;
 502
 503   if (end <= addr)
 504     return 0;
 505
 506   grub_mmap_register (addr, end - addr, GRUB_MEMORY_HOLE);
 507   return 0;
 508 }
 509
 510 static grub_err_t
 511 grub_cmd_cutmem (grub_command_t cmd __attribute__ ((unused)),
 512                  int argc, char **args)
 513 {
 514   struct cutmem_range range;
 515
 516   if (argc != 2)
 517     return grub_error (GRUB_ERR_BAD_ARGUMENT, N_("two arguments expected"));
 518
 519   range.from = parsemem (args[0]);
 520   if (grub_errno)
 521     return grub_errno;
 522
 523   range.to = parsemem (args[1]);
 524   if (grub_errno)
 525     return grub_errno;
 526
 527   grub_mmap_iterate (cutmem_iter, &range);
 528
 529   return GRUB_ERR_NONE;
 530 }
 531
 532 static grub_command_t cmd, cmd_cut;
 533
 534 \f
 535 GRUB_MOD_INIT(mmap)
 536 {
 537   cmd = grub_register_command ("badram", grub_cmd_badram,
 538                                N_("ADDR1,MASK1[,ADDR2,MASK2[,...]]"),
 539                                N_("Declare memory regions as faulty (badram)."));
 540   cmd_cut = grub_register_command ("cutmem", grub_cmd_cutmem,
 541                                    N_("FROM[K|M|G] TO[K|M|G]"),
 542                                    N_("Remove any memory regions in specified range."));
 543
 544 }
 545
 546 GRUB_MOD_FINI(mmap)
 547 {
 548   grub_unregister_command (cmd);
 549   grub_unregister_command (cmd_cut);
 550 }
 551