2009-11-21 Samuel Thibault <samuel.thibault@ens-lyon.org>
[grub2.git] / efiemu / mm.c
blob8b032294242b43ec389fa788b75f1fcc11be39b1
1 /* Memory management for efiemu */
2 /*
3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2009 Free Software Foundation, Inc.
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.
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.
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/>.
20 To keep efiemu runtime contiguous this mm is special.
21 It uses deferred allocation.
22 In the first stage you may request memory with grub_efiemu_request_memalign
23 It will give you a handle with which in the second phase you can access your
24 memory with grub_efiemu_mm_obtain_request (handle). It's guaranteed that
25 subsequent calls with the same handle return the same result. You can't request any additional memory once you're in the second phase
28 #include <grub/err.h>
29 #include <grub/normal.h>
30 #include <grub/mm.h>
31 #include <grub/misc.h>
32 #include <grub/machine/memory.h>
33 #include <grub/efiemu/efiemu.h>
35 struct grub_efiemu_memrequest
37 struct grub_efiemu_memrequest *next;
38 grub_efi_memory_type_t type;
39 grub_size_t size;
40 grub_size_t align_overhead;
41 int handle;
42 void *val;
44 /* Linked list of requested memory. */
45 static struct grub_efiemu_memrequest *memrequests = 0;
46 /* Memory map. */
47 static grub_efi_memory_descriptor_t *efiemu_mmap = 0;
48 /* Pointer to allocated memory */
49 static void *resident_memory = 0;
50 /* Size of requested memory per type */
51 static grub_size_t requested_memory[GRUB_EFI_MAX_MEMORY_TYPE];
52 /* How many slots is allocated for memory_map and how many are already used */
53 static int mmap_reserved_size = 0, mmap_num = 0;
55 /* Add a memory region to map*/
56 static grub_err_t
57 grub_efiemu_add_to_mmap (grub_uint64_t start, grub_uint64_t size,
58 grub_efi_memory_type_t type)
60 grub_uint64_t page_start, npages;
62 /* Extend map if necessary*/
63 if (mmap_num >= mmap_reserved_size)
65 efiemu_mmap = (grub_efi_memory_descriptor_t *)
66 grub_realloc (efiemu_mmap, (++mmap_reserved_size)
67 * sizeof (grub_efi_memory_descriptor_t));
68 if (!efiemu_mmap)
69 return grub_error (GRUB_ERR_OUT_OF_MEMORY,
70 "Not enough space for memory map");
73 /* Fill slot*/
74 page_start = start - (start % GRUB_EFIEMU_PAGESIZE);
75 npages = (size + (start % GRUB_EFIEMU_PAGESIZE) + GRUB_EFIEMU_PAGESIZE - 1)
76 / GRUB_EFIEMU_PAGESIZE;
77 efiemu_mmap[mmap_num].physical_start = page_start;
78 efiemu_mmap[mmap_num].virtual_start = page_start;
79 efiemu_mmap[mmap_num].num_pages = npages;
80 efiemu_mmap[mmap_num].type = type;
81 mmap_num++;
83 return GRUB_ERR_NONE;
86 /* Request a resident memory of type TYPE of size SIZE aligned at ALIGN
87 ALIGN must be a divisor of page size (if it's a divisor of 4096
88 it should be ok on all platforms)
90 int
91 grub_efiemu_request_memalign (grub_size_t align, grub_size_t size,
92 grub_efi_memory_type_t type)
94 grub_size_t align_overhead;
95 struct grub_efiemu_memrequest *ret, *cur, *prev;
96 /* Check that the request is correct */
97 if (type >= GRUB_EFI_MAX_MEMORY_TYPE || type <= GRUB_EFI_LOADER_CODE)
98 return -2;
100 /* Add new size to requested size */
101 align_overhead = align - (requested_memory[type]%align);
102 if (align_overhead == align)
103 align_overhead = 0;
104 requested_memory[type] += align_overhead + size;
106 /* Remember the request */
107 ret = grub_zalloc (sizeof (*ret));
108 if (!ret)
109 return -1;
110 ret->type = type;
111 ret->size = size;
112 ret->align_overhead = align_overhead;
113 prev = 0;
115 /* Add request to the end of the chain.
116 It should be at the end because otherwise alignment isn't guaranteed */
117 for (cur = memrequests; cur; prev = cur, cur = cur->next);
118 if (prev)
120 ret->handle = prev->handle + 1;
121 prev->next = ret;
123 else
125 ret->handle = 1; /* Avoid 0 handle*/
126 memrequests = ret;
128 return ret->handle;
131 /* Really allocate the memory */
132 static grub_err_t
133 efiemu_alloc_requests (void)
135 grub_size_t align_overhead = 0;
136 grub_uint8_t *curptr, *typestart;
137 struct grub_efiemu_memrequest *cur;
138 grub_size_t total_alloc = 0;
139 unsigned i;
140 /* Order of memory regions */
141 grub_efi_memory_type_t reqorder[] =
143 /* First come regions usable by OS*/
144 GRUB_EFI_LOADER_CODE,
145 GRUB_EFI_LOADER_DATA,
146 GRUB_EFI_BOOT_SERVICES_CODE,
147 GRUB_EFI_BOOT_SERVICES_DATA,
148 GRUB_EFI_CONVENTIONAL_MEMORY,
149 GRUB_EFI_ACPI_RECLAIM_MEMORY,
151 /* Then memory used by runtime */
152 /* This way all our regions are in a single block */
153 GRUB_EFI_RUNTIME_SERVICES_CODE,
154 GRUB_EFI_RUNTIME_SERVICES_DATA,
155 GRUB_EFI_ACPI_MEMORY_NVS,
157 /* And then unavailable memory types. This is more for a completeness.
158 You should double think before allocating memory of any of these types
160 GRUB_EFI_UNUSABLE_MEMORY,
161 GRUB_EFI_MEMORY_MAPPED_IO,
162 GRUB_EFI_MEMORY_MAPPED_IO_PORT_SPACE,
163 GRUB_EFI_PAL_CODE
166 /* Compute total memory needed */
167 for (i = 0; i < sizeof (reqorder) / sizeof (reqorder[0]); i++)
169 align_overhead = GRUB_EFIEMU_PAGESIZE
170 - (requested_memory[reqorder[i]] % GRUB_EFIEMU_PAGESIZE);
171 if (align_overhead == GRUB_EFIEMU_PAGESIZE)
172 align_overhead = 0;
173 total_alloc += requested_memory[reqorder[i]] + align_overhead;
176 /* Allocate the whole memory in one block */
177 resident_memory = grub_memalign (GRUB_EFIEMU_PAGESIZE, total_alloc);
178 if (!resident_memory)
179 return grub_error (GRUB_ERR_OUT_OF_MEMORY,
180 "couldn't allocate resident memory");
182 /* Split the memory into blocks by type */
183 curptr = resident_memory;
184 for (i = 0; i < sizeof (reqorder) / sizeof (reqorder[0]); i++)
186 if (!requested_memory[reqorder[i]])
187 continue;
188 typestart = curptr;
190 /* Write pointers to requests */
191 for (cur = memrequests; cur; cur = cur->next)
192 if (cur->type == reqorder[i])
194 curptr = ((grub_uint8_t *)curptr) + cur->align_overhead;
195 cur->val = curptr;
196 curptr = ((grub_uint8_t *)curptr) + cur->size;
199 /* Ensure that the regions are page-aligned */
200 align_overhead = GRUB_EFIEMU_PAGESIZE
201 - (requested_memory[reqorder[i]] % GRUB_EFIEMU_PAGESIZE);
202 if (align_overhead == GRUB_EFIEMU_PAGESIZE)
203 align_overhead = 0;
204 curptr = ((grub_uint8_t *)curptr) + align_overhead;
206 /* Add the region to memory map */
207 grub_efiemu_add_to_mmap (PTR_TO_UINT64 (typestart),
208 curptr - typestart, reqorder[i]);
211 return GRUB_ERR_NONE;
214 /* Get a pointer to requested memory from handle */
215 void *
216 grub_efiemu_mm_obtain_request (int handle)
218 struct grub_efiemu_memrequest *cur;
219 for (cur = memrequests; cur; cur = cur->next)
220 if (cur->handle == handle)
221 return cur->val;
222 return 0;
225 /* Get type of requested memory by handle */
226 grub_efi_memory_type_t
227 grub_efiemu_mm_get_type (int handle)
229 struct grub_efiemu_memrequest *cur;
230 for (cur = memrequests; cur; cur = cur->next)
231 if (cur->handle == handle)
232 return cur->type;
233 return 0;
236 /* Free a request */
237 void
238 grub_efiemu_mm_return_request (int handle)
240 struct grub_efiemu_memrequest *cur, *prev;
242 /* Remove head if necessary */
243 while (memrequests && memrequests->handle == handle)
245 cur = memrequests->next;
246 grub_free (memrequests);
247 memrequests = cur;
249 if (!memrequests)
250 return;
252 /* Remove request from a middle of chain*/
253 for (prev = memrequests, cur = prev->next; cur;)
254 if (cur->handle == handle)
256 prev->next = cur->next;
257 grub_free (cur);
258 cur = prev->next;
260 else
262 prev = cur;
263 cur = prev->next;
267 /* Reserve space for memory map */
268 static grub_err_t
269 grub_efiemu_mmap_init (void)
271 auto int NESTED_FUNC_ATTR bounds_hook (grub_uint64_t, grub_uint64_t,
272 grub_uint32_t);
273 int NESTED_FUNC_ATTR bounds_hook (grub_uint64_t addr __attribute__ ((unused)),
274 grub_uint64_t size __attribute__ ((unused)),
275 grub_uint32_t type __attribute__ ((unused)))
277 mmap_reserved_size++;
278 return 0;
281 // the place for memory used by efiemu itself
282 mmap_reserved_size = GRUB_EFI_MAX_MEMORY_TYPE + 1;
284 #ifndef GRUB_UTIL
285 grub_machine_mmap_iterate (bounds_hook);
286 #endif
288 return GRUB_ERR_NONE;
291 /* This is a drop-in replacement of grub_efi_get_memory_map */
292 /* Get the memory map as defined in the EFI spec. Return 1 if successful,
293 return 0 if partial, or return -1 if an error occurs. */
295 grub_efiemu_get_memory_map (grub_efi_uintn_t *memory_map_size,
296 grub_efi_memory_descriptor_t *memory_map,
297 grub_efi_uintn_t *map_key,
298 grub_efi_uintn_t *descriptor_size,
299 grub_efi_uint32_t *descriptor_version)
301 if (!efiemu_mmap)
303 grub_error (GRUB_ERR_INVALID_COMMAND,
304 "you need to first launch efiemu_prepare");
305 return -1;
308 if (*memory_map_size < mmap_num * sizeof (grub_efi_memory_descriptor_t))
310 *memory_map_size = mmap_num * sizeof (grub_efi_memory_descriptor_t);
311 return 0;
314 *memory_map_size = mmap_num * sizeof (grub_efi_memory_descriptor_t);
315 grub_memcpy (memory_map, efiemu_mmap, *memory_map_size);
316 if (descriptor_size)
317 *descriptor_size = sizeof (grub_efi_memory_descriptor_t);
318 if (descriptor_version)
319 *descriptor_version = 1;
320 if (map_key)
321 *map_key = 0;
323 return 1;
326 /* Free everything */
327 grub_err_t
328 grub_efiemu_mm_unload (void)
330 struct grub_efiemu_memrequest *cur, *d;
331 for (cur = memrequests; cur;)
333 d = cur->next;
334 grub_free (cur);
335 cur = d;
337 memrequests = 0;
338 grub_memset (&requested_memory, 0, sizeof (requested_memory));
339 grub_free (resident_memory);
340 resident_memory = 0;
341 grub_free (efiemu_mmap);
342 efiemu_mmap = 0;
343 mmap_reserved_size = mmap_num = 0;
344 return GRUB_ERR_NONE;
347 /* This function should be called before doing any requests */
348 grub_err_t
349 grub_efiemu_mm_init (void)
351 grub_err_t err;
353 err = grub_efiemu_mm_unload ();
354 if (err)
355 return err;
357 grub_efiemu_mmap_init ();
359 return GRUB_ERR_NONE;
362 /* Copy host memory map */
363 static grub_err_t
364 grub_efiemu_mmap_fill (void)
366 auto int NESTED_FUNC_ATTR fill_hook (grub_uint64_t, grub_uint64_t, grub_uint32_t);
367 int NESTED_FUNC_ATTR fill_hook (grub_uint64_t addr,
368 grub_uint64_t size,
369 grub_uint32_t type)
371 switch (type)
373 case GRUB_MACHINE_MEMORY_AVAILABLE:
374 return grub_efiemu_add_to_mmap (addr, size,
375 GRUB_EFI_CONVENTIONAL_MEMORY);
377 #ifdef GRUB_MACHINE_MEMORY_ACPI
378 case GRUB_MACHINE_MEMORY_ACPI:
379 return grub_efiemu_add_to_mmap (addr, size,
380 GRUB_EFI_ACPI_RECLAIM_MEMORY);
381 #endif
383 #ifdef GRUB_MACHINE_MEMORY_NVS
384 case GRUB_MACHINE_MEMORY_NVS:
385 return grub_efiemu_add_to_mmap (addr, size,
386 GRUB_EFI_ACPI_MEMORY_NVS);
387 #endif
389 default:
390 grub_printf ("Unknown memory type %d. Marking as unusable\n", type);
391 case GRUB_MACHINE_MEMORY_RESERVED:
392 return grub_efiemu_add_to_mmap (addr, size,
393 GRUB_EFI_UNUSABLE_MEMORY);
397 #ifndef GRUB_UTIL
398 grub_machine_mmap_iterate (fill_hook);
399 #endif
401 return GRUB_ERR_NONE;
404 grub_err_t
405 grub_efiemu_mmap_iterate (int NESTED_FUNC_ATTR (*hook) (grub_uint64_t,
406 grub_uint64_t,
407 grub_uint32_t))
409 unsigned i;
411 for (i = 0; i < (unsigned) mmap_num; i++)
412 switch (efiemu_mmap[i].type)
414 case GRUB_EFI_RUNTIME_SERVICES_CODE:
415 hook (efiemu_mmap[i].physical_start, efiemu_mmap[i].num_pages * 4096,
416 GRUB_EFIEMU_MEMORY_CODE);
417 break;
419 case GRUB_EFI_RESERVED_MEMORY_TYPE:
420 case GRUB_EFI_RUNTIME_SERVICES_DATA:
421 case GRUB_EFI_UNUSABLE_MEMORY:
422 case GRUB_EFI_MEMORY_MAPPED_IO:
423 case GRUB_EFI_MEMORY_MAPPED_IO_PORT_SPACE:
424 case GRUB_EFI_PAL_CODE:
425 case GRUB_EFI_MAX_MEMORY_TYPE:
426 hook (efiemu_mmap[i].physical_start, efiemu_mmap[i].num_pages * 4096,
427 GRUB_EFIEMU_MEMORY_RESERVED);
428 break;
430 case GRUB_EFI_LOADER_CODE:
431 case GRUB_EFI_LOADER_DATA:
432 case GRUB_EFI_BOOT_SERVICES_CODE:
433 case GRUB_EFI_BOOT_SERVICES_DATA:
434 case GRUB_EFI_CONVENTIONAL_MEMORY:
435 hook (efiemu_mmap[i].physical_start, efiemu_mmap[i].num_pages * 4096,
436 GRUB_EFIEMU_MEMORY_AVAILABLE);
437 break;
439 case GRUB_EFI_ACPI_RECLAIM_MEMORY:
440 hook (efiemu_mmap[i].physical_start, efiemu_mmap[i].num_pages * 4096,
441 GRUB_EFIEMU_MEMORY_ACPI);
442 break;
444 case GRUB_EFI_ACPI_MEMORY_NVS:
445 hook (efiemu_mmap[i].physical_start, efiemu_mmap[i].num_pages * 4096,
446 GRUB_EFIEMU_MEMORY_NVS);
447 break;
450 return 0;
454 /* This function resolves overlapping regions and sorts the memory map
455 It uses scanline (sweeping) algorithm
457 static grub_err_t
458 grub_efiemu_mmap_sort_and_uniq (void)
460 /* If same page is used by multiple types it's resolved
461 according to priority
462 0 - free memory
463 1 - memory immediately usable after ExitBootServices
464 2 - memory usable after loading ACPI tables
465 3 - efiemu memory
466 4 - unusable memory
468 int priority[GRUB_EFI_MAX_MEMORY_TYPE] =
470 [GRUB_EFI_RESERVED_MEMORY_TYPE] = 4,
471 [GRUB_EFI_LOADER_CODE] = 1,
472 [GRUB_EFI_LOADER_DATA] = 1,
473 [GRUB_EFI_BOOT_SERVICES_CODE] = 1,
474 [GRUB_EFI_BOOT_SERVICES_DATA] = 1,
475 [GRUB_EFI_RUNTIME_SERVICES_CODE] = 3,
476 [GRUB_EFI_RUNTIME_SERVICES_DATA] = 3,
477 [GRUB_EFI_CONVENTIONAL_MEMORY] = 0,
478 [GRUB_EFI_UNUSABLE_MEMORY] = 4,
479 [GRUB_EFI_ACPI_RECLAIM_MEMORY] = 2,
480 [GRUB_EFI_ACPI_MEMORY_NVS] = 3,
481 [GRUB_EFI_MEMORY_MAPPED_IO] = 4,
482 [GRUB_EFI_MEMORY_MAPPED_IO_PORT_SPACE] = 4,
483 [GRUB_EFI_PAL_CODE] = 4
486 int i, j, k, done;
488 /* Scanline events */
489 struct grub_efiemu_mmap_scan
491 /* At which memory address*/
492 grub_uint64_t pos;
493 /* 0 = region starts, 1 = region ends */
494 int type;
495 /* Which type of memory region */
496 grub_efi_memory_type_t memtype;
498 struct grub_efiemu_mmap_scan *scanline_events;
499 struct grub_efiemu_mmap_scan t;
501 /* Previous scanline event */
502 grub_uint64_t lastaddr;
503 int lasttype;
504 /* Current scanline event */
505 int curtype;
506 /* how many regions of given type overlap at current location */
507 int present[GRUB_EFI_MAX_MEMORY_TYPE];
508 /* Here is stored the resulting memory map*/
509 grub_efi_memory_descriptor_t *result;
511 /* Initialize variables*/
512 grub_memset (present, 0, sizeof (int) * GRUB_EFI_MAX_MEMORY_TYPE);
513 scanline_events = (struct grub_efiemu_mmap_scan *)
514 grub_malloc (sizeof (struct grub_efiemu_mmap_scan) * 2 * mmap_num);
516 /* Number of chunks can't increase more than by factor of 2 */
517 result = (grub_efi_memory_descriptor_t *)
518 grub_malloc (sizeof (grub_efi_memory_descriptor_t) * 2 * mmap_num);
519 if (!result || !scanline_events)
521 grub_free (result);
522 grub_free (scanline_events);
523 return grub_error (GRUB_ERR_OUT_OF_MEMORY,
524 "couldn't allocate space for new memory map");
527 /* Register scanline events */
528 for (i = 0; i < mmap_num; i++)
530 scanline_events[2 * i].pos = efiemu_mmap[i].physical_start;
531 scanline_events[2 * i].type = 0;
532 scanline_events[2 * i].memtype = efiemu_mmap[i].type;
533 scanline_events[2 * i + 1].pos = efiemu_mmap[i].physical_start
534 + efiemu_mmap[i].num_pages * GRUB_EFIEMU_PAGESIZE;
535 scanline_events[2 * i + 1].type = 1;
536 scanline_events[2 * i + 1].memtype = efiemu_mmap[i].type;
539 /* Primitive bubble sort. It has complexity O(n^2) but since we're
540 unlikely to have more than 100 chunks it's probably one of the
541 fastest for one purpose */
542 done = 1;
543 while (done)
545 done = 0;
546 for (i = 0; i < 2 * mmap_num - 1; i++)
547 if (scanline_events[i + 1].pos < scanline_events[i].pos)
549 t = scanline_events[i + 1];
550 scanline_events[i + 1] = scanline_events[i];
551 scanline_events[i] = t;
552 done = 1;
556 /* Pointer in resulting memory map */
557 j = 0;
558 lastaddr = scanline_events[0].pos;
559 lasttype = scanline_events[0].memtype;
560 for (i = 0; i < 2 * mmap_num; i++)
562 /* Process event */
563 if (scanline_events[i].type)
564 present[scanline_events[i].memtype]--;
565 else
566 present[scanline_events[i].memtype]++;
568 /* Determine current region type */
569 curtype = -1;
570 for (k = 0; k < GRUB_EFI_MAX_MEMORY_TYPE; k++)
571 if (present[k] && (curtype == -1 || priority[k] > priority[curtype]))
572 curtype = k;
574 /* Add memory region to resulting map if necessary */
575 if ((curtype == -1 || curtype != lasttype)
576 && lastaddr != scanline_events[i].pos
577 && lasttype != -1)
579 result[j].virtual_start = result[j].physical_start = lastaddr;
580 result[j].num_pages = (scanline_events[i].pos - lastaddr)
581 / GRUB_EFIEMU_PAGESIZE;
582 result[j].type = lasttype;
584 /* We set runtime attribute on pages we need to be mapped */
585 result[j].attribute
586 = (lasttype == GRUB_EFI_RUNTIME_SERVICES_CODE
587 || lasttype == GRUB_EFI_RUNTIME_SERVICES_DATA)
588 ? GRUB_EFI_MEMORY_RUNTIME : 0;
589 grub_dprintf ("efiemu",
590 "mmap entry: type %d start 0x%llx 0x%llx pages\n",
591 result[j].type,
592 result[j].physical_start, result[j].num_pages);
593 j++;
596 /* Update last values if necessary */
597 if (curtype == -1 || curtype != lasttype)
599 lasttype = curtype;
600 lastaddr = scanline_events[i].pos;
604 grub_free (scanline_events);
606 /* Shrink resulting memory map to really used size and replace efiemu_mmap
607 by new value */
608 grub_free (efiemu_mmap);
609 efiemu_mmap = grub_realloc (result, j * sizeof (*result));
610 return GRUB_ERR_NONE;
613 /* This function is called to switch from first to second phase */
614 grub_err_t
615 grub_efiemu_mm_do_alloc (void)
617 grub_err_t err;
619 /* Preallocate mmap */
620 efiemu_mmap = (grub_efi_memory_descriptor_t *)
621 grub_malloc (mmap_reserved_size * sizeof (grub_efi_memory_descriptor_t));
622 if (!efiemu_mmap)
624 grub_efiemu_unload ();
625 return grub_error (GRUB_ERR_OUT_OF_MEMORY, "Couldn't initialize mmap");
628 if ((err = efiemu_alloc_requests ()))
629 return err;
630 if ((err = grub_efiemu_mmap_fill ()))
631 return err;
632 return grub_efiemu_mmap_sort_and_uniq ();