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 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  30
  31 struct grub_mmap_region *grub_mmap_overlays = 0;
  32 static int curhandle = 1;
  33
  34 #endif
  35
  36 grub_err_t
  37 grub_mmap_iterate (grub_memory_hook_t hook)
  38 {
  39
  40   /* This function resolves overlapping regions and sorts the memory map.
  41      It uses scanline (sweeping) algorithm.
  42   */
  43   /* If same page is used by multiple types it's resolved
  44      according to priority:
  45      1 - free memory
  46      2 - memory usable by firmware-aware code
  47      3 - unusable memory
  48      4 - a range deliberately empty
  49   */
  50   int priority[] =
  51     {
  52       [GRUB_MEMORY_AVAILABLE] = 1,
  53       [GRUB_MEMORY_RESERVED] = 3,
  54       [GRUB_MEMORY_ACPI] = 2,
  55       [GRUB_MEMORY_CODE] = 3,
  56       [GRUB_MEMORY_NVS] = 3,
  57       [GRUB_MEMORY_HOLE] = 4,
  58     };
  59
  60   int i, done;
  61
  62   /* Scanline events. */
  63   struct grub_mmap_scan
  64   {
  65     /* At which memory address. */
  66     grub_uint64_t pos;
  67     /* 0 = region starts, 1 = region ends. */
  68     int type;
  69     /* Which type of memory region? */
  70     int memtype;
  71   };
  72   struct grub_mmap_scan *scanline_events;
  73   struct grub_mmap_scan t;
  74
  75   /* Previous scanline event. */
  76   grub_uint64_t lastaddr;
  77   int lasttype;
  78   /* Current scanline event. */
  79   int curtype;
  80   /* How many regions of given type overlap at current location? */
  81   int present[ARRAY_SIZE (priority)];
  82   /* Number of mmap chunks. */
  83   int mmap_num;
  84
  85 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  86   struct grub_mmap_region *cur;
  87 #endif
  88
  89   auto int NESTED_FUNC_ATTR count_hook (grub_uint64_t, grub_uint64_t,
  90                                         grub_uint32_t);
  91   int NESTED_FUNC_ATTR count_hook (grub_uint64_t addr __attribute__ ((unused)),
  92                                    grub_uint64_t size __attribute__ ((unused)),
  93                                    grub_memory_type_t type __attribute__ ((unused)))
  94   {
  95     mmap_num++;
  96     return 0;
  97   }
  98
  99   auto int NESTED_FUNC_ATTR fill_hook (grub_uint64_t, grub_uint64_t,
 100                                         grub_uint32_t);
 101   int NESTED_FUNC_ATTR fill_hook (grub_uint64_t addr,
 102                                   grub_uint64_t size,
 103                                   grub_memory_type_t type)
 104   {
 105     scanline_events[i].pos = addr;
 106     scanline_events[i].type = 0;
 107     if (type < ARRAY_SIZE (priority) && priority[type])
 108       scanline_events[i].memtype = type;
 109     else
 110       {
 111         grub_dprintf ("mmap", "Unknown memory type %d. Assuming unusable\n",
 112                       type);
 113         scanline_events[i].memtype = GRUB_MEMORY_RESERVED;
 114       }
 115     i++;
 116
 117     scanline_events[i].pos = addr + size;
 118     scanline_events[i].type = 1;
 119     scanline_events[i].memtype = scanline_events[i - 1].memtype;
 120     i++;
 121
 122     return 0;
 123   }
 124
 125   mmap_num = 0;
 126
 127 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 128   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 129     mmap_num++;
 130 #endif
 131
 132   grub_machine_mmap_iterate (count_hook);
 133
 134   /* Initialize variables. */
 135   grub_memset (present, 0, sizeof (present));
 136   scanline_events = (struct grub_mmap_scan *)
 137     grub_malloc (sizeof (struct grub_mmap_scan) * 2 * mmap_num);
 138
 139   if (! scanline_events)
 140     {
 141       return grub_error (GRUB_ERR_OUT_OF_MEMORY,
 142                          "couldn't allocate space for new memory map");
 143     }
 144
 145   i = 0;
 146 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 147   /* Register scanline events. */
 148   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 149     {
 150       scanline_events[i].pos = cur->start;
 151       scanline_events[i].type = 0;
 152       if (cur->type < ARRAY_SIZE (priority) && priority[cur->type])
 153         scanline_events[i].memtype = cur->type;
 154       else
 155         scanline_events[i].memtype = GRUB_MEMORY_RESERVED;
 156       i++;
 157
 158       scanline_events[i].pos = cur->end;
 159       scanline_events[i].type = 1;
 160       scanline_events[i].memtype = scanline_events[i - 1].memtype;
 161       i++;
 162     }
 163 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 164
 165   grub_machine_mmap_iterate (fill_hook);
 166
 167   /* Primitive bubble sort. It has complexity O(n^2) but since we're
 168      unlikely to have more than 100 chunks it's probably one of the
 169      fastest for one purpose. */
 170   done = 1;
 171   while (done)
 172     {
 173       done = 0;
 174       for (i = 0; i < 2 * mmap_num - 1; i++)
 175         if (scanline_events[i + 1].pos < scanline_events[i].pos
 176             || (scanline_events[i + 1].pos == scanline_events[i].pos
 177                 && scanline_events[i + 1].type == 0
 178                 && scanline_events[i].type == 1))
 179           {
 180             t = scanline_events[i + 1];
 181             scanline_events[i + 1] = scanline_events[i];
 182             scanline_events[i] = t;
 183             done = 1;
 184           }
 185     }
 186
 187   lastaddr = scanline_events[0].pos;
 188   lasttype = scanline_events[0].memtype;
 189   for (i = 0; i < 2 * mmap_num; i++)
 190     {
 191       unsigned k;
 192       /* Process event. */
 193       if (scanline_events[i].type)
 194         present[scanline_events[i].memtype]--;
 195       else
 196         present[scanline_events[i].memtype]++;
 197
 198       /* Determine current region type. */
 199       curtype = -1;
 200       for (k = 0; k < ARRAY_SIZE (priority); k++)
 201         if (present[k] && (curtype == -1 || priority[k] > priority[curtype]))
 202           curtype = k;
 203
 204       /* Announce region to the hook if necessary. */
 205       if ((curtype == -1 || curtype != lasttype)
 206           && lastaddr != scanline_events[i].pos
 207           && lasttype != -1
 208           && lasttype != GRUB_MEMORY_HOLE
 209           && hook (lastaddr, scanline_events[i].pos - lastaddr, lasttype))
 210         {
 211           grub_free (scanline_events);
 212           return GRUB_ERR_NONE;
 213         }
 214
 215       /* Update last values if necessary. */
 216       if (curtype == -1 || curtype != lasttype)
 217         {
 218           lasttype = curtype;
 219           lastaddr = scanline_events[i].pos;
 220         }
 221     }
 222
 223   grub_free (scanline_events);
 224   return GRUB_ERR_NONE;
 225 }
 226
 227 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 228 int
 229 grub_mmap_register (grub_uint64_t start, grub_uint64_t size, int type)
 230 {
 231   struct grub_mmap_region *cur;
 232
 233   grub_dprintf ("mmap", "registering\n");
 234
 235   cur = (struct grub_mmap_region *)
 236     grub_malloc (sizeof (struct grub_mmap_region));
 237   if (! cur)
 238     {
 239       grub_error (GRUB_ERR_OUT_OF_MEMORY,
 240                   "couldn't allocate memory map overlay");
 241       return 0;
 242     }
 243
 244   cur->next = grub_mmap_overlays;
 245   cur->start = start;
 246   cur->end = start + size;
 247   cur->type = type;
 248   cur->handle = curhandle++;
 249   grub_mmap_overlays = cur;
 250
 251   if (grub_machine_mmap_register (start, size, type, curhandle))
 252     {
 253       grub_mmap_overlays = cur->next;
 254       grub_free (cur);
 255       return 0;
 256     }
 257
 258   return cur->handle;
 259 }
 260
 261 grub_err_t
 262 grub_mmap_unregister (int handle)
 263 {
 264   struct grub_mmap_region *cur, *prev;
 265
 266   for (cur = grub_mmap_overlays, prev = 0; cur; prev= cur, cur = cur->next)
 267     if (handle == cur->handle)
 268       {
 269         grub_err_t err;
 270         if ((err = grub_machine_mmap_unregister (handle)))
 271           return err;
 272
 273         if (prev)
 274           prev->next = cur->next;
 275         else
 276           grub_mmap_overlays = cur->next;
 277         grub_free (cur);
 278         return GRUB_ERR_NONE;
 279       }
 280   return grub_error (GRUB_ERR_BAD_ARGUMENT, "mmap overlay not found");
 281 }
 282
 283 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 284
 285 #define CHUNK_SIZE      0x400
 286
 287 static inline grub_uint64_t
 288 fill_mask (grub_uint64_t addr, grub_uint64_t mask, grub_uint64_t iterator)
 289 {
 290   int i, j;
 291   grub_uint64_t ret = (addr & mask);
 292
 293   /* Find first fixed bit. */
 294   for (i = 0; i < 64; i++)
 295     if ((mask & (1ULL << i)) != 0)
 296       break;
 297   j = 0;
 298   for (; i < 64; i++)
 299     if ((mask & (1ULL << i)) == 0)
 300       {
 301         if ((iterator & (1ULL << j)) != 0)
 302           ret |= 1ULL << i;
 303         j++;
 304       }
 305   return ret;
 306 }
 307
 308 static grub_err_t
 309 grub_cmd_badram (grub_command_t cmd __attribute__ ((unused)),
 310                  int argc, char **args)
 311 {
 312   char * str;
 313   grub_uint64_t badaddr, badmask;
 314
 315   auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t,
 316                                  grub_memory_type_t);
 317   int NESTED_FUNC_ATTR hook (grub_uint64_t addr,
 318                              grub_uint64_t size,
 319                              grub_memory_type_t type __attribute__ ((unused)))
 320   {
 321     grub_uint64_t iterator, low, high, cur;
 322     int tail, var;
 323     int i;
 324     grub_dprintf ("badram", "hook %llx+%llx\n", (unsigned long long) addr,
 325                   (unsigned long long) size);
 326
 327     /* How many trailing zeros? */
 328     for (tail = 0; ! (badmask & (1ULL << tail)); tail++);
 329
 330     /* How many zeros in mask? */
 331     var = 0;
 332     for (i = 0; i < 64; i++)
 333       if (! (badmask & (1ULL << i)))
 334         var++;
 335
 336     if (fill_mask (badaddr, badmask, 0) >= addr)
 337       iterator = 0;
 338     else
 339       {
 340         low = 0;
 341         high = ~0ULL;
 342         /* Find starting value. Keep low and high such that
 343            fill_mask (low) < addr and fill_mask (high) >= addr;
 344         */
 345         while (high - low > 1)
 346           {
 347             cur = (low + high) / 2;
 348             if (fill_mask (badaddr, badmask, cur) >= addr)
 349               high = cur;
 350             else
 351               low = cur;
 352           }
 353         iterator = high;
 354       }
 355
 356     for (; iterator < (1ULL << (var - tail))
 357            && (cur = fill_mask (badaddr, badmask, iterator)) < addr + size;
 358          iterator++)
 359       {
 360         grub_dprintf ("badram", "%llx (size %llx) is a badram range\n",
 361                       (unsigned long long) cur, (1ULL << tail));
 362         grub_mmap_register (cur, (1ULL << tail), GRUB_MEMORY_HOLE);
 363       }
 364     return 0;
 365   }
 366
 367   if (argc != 1)
 368     return grub_error (GRUB_ERR_BAD_ARGUMENT, "badram string required");
 369
 370   grub_dprintf ("badram", "executing badram\n");
 371
 372   str = args[0];
 373
 374   while (1)
 375     {
 376       /* Parse address and mask.  */
 377       badaddr = grub_strtoull (str, &str, 16);
 378       if (*str == ',')
 379         str++;
 380       badmask = grub_strtoull (str, &str, 16);
 381       if (*str == ',')
 382         str++;
 383
 384       if (grub_errno == GRUB_ERR_BAD_NUMBER)
 385         {
 386           grub_errno = 0;
 387           return GRUB_ERR_NONE;
 388         }
 389
 390       /* When part of a page is tainted, we discard the whole of it.  There's
 391          no point in providing sub-page chunks.  */
 392       badmask &= ~(CHUNK_SIZE - 1);
 393
 394       grub_dprintf ("badram", "badram %llx:%llx\n",
 395                     (unsigned long long) badaddr, (unsigned long long) badmask);
 396
 397       grub_mmap_iterate (hook);
 398     }
 399 }
 400
 401 static grub_command_t cmd;
 402
 403 \f
 404 GRUB_MOD_INIT(mmap)
 405 {
 406   cmd = grub_register_command ("badram", grub_cmd_badram,
 407                                N_("ADDR1,MASK1[,ADDR2,MASK2[,...]]"),
 408                                N_("Declare memory regions as badram."));
 409 }
 410
 411 GRUB_MOD_FINI(mmap)
 412 {
 413   grub_unregister_command (cmd);
 414 }
 415