1 /* Memory management for efiemu */
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
29 #include <grub/normal.h>
31 #include <grub/misc.h>
32 #include <grub/efiemu/efiemu.h>
33 #include <grub/memory.h>
35 struct grub_efiemu_memrequest
37 struct grub_efiemu_memrequest
*next
;
38 grub_efi_memory_type_t type
;
40 grub_size_t align_overhead
;
44 /* Linked list of requested memory. */
45 static struct grub_efiemu_memrequest
*memrequests
= 0;
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*/
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
));
69 return grub_error (GRUB_ERR_OUT_OF_MEMORY
,
70 "not enough space for memory map");
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
;
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)
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
)
100 /* Add new size to requested size */
101 align_overhead
= align
- (requested_memory
[type
]%align
);
102 if (align_overhead
== align
)
104 requested_memory
[type
] += align_overhead
+ size
;
106 /* Remember the request */
107 ret
= grub_zalloc (sizeof (*ret
));
112 ret
->align_overhead
= align_overhead
;
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
);
120 ret
->handle
= prev
->handle
+ 1;
125 ret
->handle
= 1; /* Avoid 0 handle*/
131 /* Really allocate the memory */
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;
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
,
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
)
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
]])
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
;
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
)
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 */
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
)
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
)
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
);
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
;
267 /* Reserve space for memory map */
269 grub_efiemu_mmap_init (void)
271 auto int NESTED_FUNC_ATTR
bounds_hook (grub_uint64_t
, grub_uint64_t
,
273 int NESTED_FUNC_ATTR
bounds_hook (grub_uint64_t addr
__attribute__ ((unused
)),
274 grub_uint64_t size
__attribute__ ((unused
)),
275 grub_memory_type_t type
276 __attribute__ ((unused
)))
278 mmap_reserved_size
++;
282 // the place for memory used by efiemu itself
283 mmap_reserved_size
= GRUB_EFI_MAX_MEMORY_TYPE
+ 1;
285 #ifndef GRUB_MACHINE_EMU
286 grub_machine_mmap_iterate (bounds_hook
);
289 return GRUB_ERR_NONE
;
292 /* This is a drop-in replacement of grub_efi_get_memory_map */
293 /* Get the memory map as defined in the EFI spec. Return 1 if successful,
294 return 0 if partial, or return -1 if an error occurs. */
296 grub_efiemu_get_memory_map (grub_efi_uintn_t
*memory_map_size
,
297 grub_efi_memory_descriptor_t
*memory_map
,
298 grub_efi_uintn_t
*map_key
,
299 grub_efi_uintn_t
*descriptor_size
,
300 grub_efi_uint32_t
*descriptor_version
)
304 grub_error (GRUB_ERR_INVALID_COMMAND
,
305 "you need to first launch efiemu_prepare");
309 if (*memory_map_size
< mmap_num
* sizeof (grub_efi_memory_descriptor_t
))
311 *memory_map_size
= mmap_num
* sizeof (grub_efi_memory_descriptor_t
);
315 *memory_map_size
= mmap_num
* sizeof (grub_efi_memory_descriptor_t
);
316 grub_memcpy (memory_map
, efiemu_mmap
, *memory_map_size
);
318 *descriptor_size
= sizeof (grub_efi_memory_descriptor_t
);
319 if (descriptor_version
)
320 *descriptor_version
= 1;
328 grub_efiemu_finish_boot_services (grub_efi_uintn_t
*memory_map_size
,
329 grub_efi_memory_descriptor_t
*memory_map
,
330 grub_efi_uintn_t
*map_key
,
331 grub_efi_uintn_t
*descriptor_size
,
332 grub_efi_uint32_t
*descriptor_version
)
334 int val
= grub_efiemu_get_memory_map (memory_map_size
,
339 return GRUB_ERR_NONE
;
342 return grub_error (GRUB_ERR_IO
, "memory map buffer is too small");
346 /* Free everything */
348 grub_efiemu_mm_unload (void)
350 struct grub_efiemu_memrequest
*cur
, *d
;
351 for (cur
= memrequests
; cur
;)
358 grub_memset (&requested_memory
, 0, sizeof (requested_memory
));
359 grub_free (resident_memory
);
361 grub_free (efiemu_mmap
);
363 mmap_reserved_size
= mmap_num
= 0;
364 return GRUB_ERR_NONE
;
367 /* This function should be called before doing any requests */
369 grub_efiemu_mm_init (void)
373 err
= grub_efiemu_mm_unload ();
377 grub_efiemu_mmap_init ();
379 return GRUB_ERR_NONE
;
382 /* Copy host memory map */
384 grub_efiemu_mmap_fill (void)
386 auto int NESTED_FUNC_ATTR
fill_hook (grub_uint64_t
, grub_uint64_t
,
388 int NESTED_FUNC_ATTR
fill_hook (grub_uint64_t addr
,
390 grub_memory_type_t type
)
394 case GRUB_MEMORY_AVAILABLE
:
395 return grub_efiemu_add_to_mmap (addr
, size
,
396 GRUB_EFI_CONVENTIONAL_MEMORY
);
398 case GRUB_MEMORY_ACPI
:
399 return grub_efiemu_add_to_mmap (addr
, size
,
400 GRUB_EFI_ACPI_RECLAIM_MEMORY
);
402 case GRUB_MEMORY_NVS
:
403 return grub_efiemu_add_to_mmap (addr
, size
,
404 GRUB_EFI_ACPI_MEMORY_NVS
);
407 grub_printf ("Unknown memory type %d. Assuming unusable\n", type
);
408 case GRUB_MEMORY_RESERVED
:
409 return grub_efiemu_add_to_mmap (addr
, size
,
410 GRUB_EFI_UNUSABLE_MEMORY
);
414 #ifndef GRUB_MACHINE_EMU
415 grub_machine_mmap_iterate (fill_hook
);
418 return GRUB_ERR_NONE
;
422 grub_efiemu_mmap_iterate (grub_memory_hook_t hook
)
426 for (i
= 0; i
< (unsigned) mmap_num
; i
++)
427 switch (efiemu_mmap
[i
].type
)
429 case GRUB_EFI_RUNTIME_SERVICES_CODE
:
430 hook (efiemu_mmap
[i
].physical_start
, efiemu_mmap
[i
].num_pages
* 4096,
434 case GRUB_EFI_UNUSABLE_MEMORY
:
435 hook (efiemu_mmap
[i
].physical_start
, efiemu_mmap
[i
].num_pages
* 4096,
439 case GRUB_EFI_RESERVED_MEMORY_TYPE
:
440 case GRUB_EFI_RUNTIME_SERVICES_DATA
:
441 case GRUB_EFI_MEMORY_MAPPED_IO
:
442 case GRUB_EFI_MEMORY_MAPPED_IO_PORT_SPACE
:
443 case GRUB_EFI_PAL_CODE
:
444 case GRUB_EFI_MAX_MEMORY_TYPE
:
445 hook (efiemu_mmap
[i
].physical_start
, efiemu_mmap
[i
].num_pages
* 4096,
446 GRUB_MEMORY_RESERVED
);
449 case GRUB_EFI_LOADER_CODE
:
450 case GRUB_EFI_LOADER_DATA
:
451 case GRUB_EFI_BOOT_SERVICES_CODE
:
452 case GRUB_EFI_BOOT_SERVICES_DATA
:
453 case GRUB_EFI_CONVENTIONAL_MEMORY
:
454 hook (efiemu_mmap
[i
].physical_start
, efiemu_mmap
[i
].num_pages
* 4096,
455 GRUB_MEMORY_AVAILABLE
);
458 case GRUB_EFI_ACPI_RECLAIM_MEMORY
:
459 hook (efiemu_mmap
[i
].physical_start
, efiemu_mmap
[i
].num_pages
* 4096,
463 case GRUB_EFI_ACPI_MEMORY_NVS
:
464 hook (efiemu_mmap
[i
].physical_start
, efiemu_mmap
[i
].num_pages
* 4096,
473 /* This function resolves overlapping regions and sorts the memory map
474 It uses scanline (sweeping) algorithm
477 grub_efiemu_mmap_sort_and_uniq (void)
479 /* If same page is used by multiple types it's resolved
480 according to priority
482 1 - memory immediately usable after ExitBootServices
483 2 - memory usable after loading ACPI tables
487 int priority
[GRUB_EFI_MAX_MEMORY_TYPE
] =
489 [GRUB_EFI_RESERVED_MEMORY_TYPE
] = 4,
490 [GRUB_EFI_LOADER_CODE
] = 1,
491 [GRUB_EFI_LOADER_DATA
] = 1,
492 [GRUB_EFI_BOOT_SERVICES_CODE
] = 1,
493 [GRUB_EFI_BOOT_SERVICES_DATA
] = 1,
494 [GRUB_EFI_RUNTIME_SERVICES_CODE
] = 3,
495 [GRUB_EFI_RUNTIME_SERVICES_DATA
] = 3,
496 [GRUB_EFI_CONVENTIONAL_MEMORY
] = 0,
497 [GRUB_EFI_UNUSABLE_MEMORY
] = 4,
498 [GRUB_EFI_ACPI_RECLAIM_MEMORY
] = 2,
499 [GRUB_EFI_ACPI_MEMORY_NVS
] = 3,
500 [GRUB_EFI_MEMORY_MAPPED_IO
] = 4,
501 [GRUB_EFI_MEMORY_MAPPED_IO_PORT_SPACE
] = 4,
502 [GRUB_EFI_PAL_CODE
] = 4
507 /* Scanline events */
508 struct grub_efiemu_mmap_scan
510 /* At which memory address*/
512 /* 0 = region starts, 1 = region ends */
514 /* Which type of memory region */
515 grub_efi_memory_type_t memtype
;
517 struct grub_efiemu_mmap_scan
*scanline_events
;
518 struct grub_efiemu_mmap_scan t
;
520 /* Previous scanline event */
521 grub_uint64_t lastaddr
;
523 /* Current scanline event */
525 /* how many regions of given type overlap at current location */
526 int present
[GRUB_EFI_MAX_MEMORY_TYPE
];
527 /* Here is stored the resulting memory map*/
528 grub_efi_memory_descriptor_t
*result
;
530 /* Initialize variables*/
531 grub_memset (present
, 0, sizeof (int) * GRUB_EFI_MAX_MEMORY_TYPE
);
532 scanline_events
= (struct grub_efiemu_mmap_scan
*)
533 grub_malloc (sizeof (struct grub_efiemu_mmap_scan
) * 2 * mmap_num
);
535 /* Number of chunks can't increase more than by factor of 2 */
536 result
= (grub_efi_memory_descriptor_t
*)
537 grub_malloc (sizeof (grub_efi_memory_descriptor_t
) * 2 * mmap_num
);
538 if (!result
|| !scanline_events
)
541 grub_free (scanline_events
);
542 return grub_error (GRUB_ERR_OUT_OF_MEMORY
,
543 "couldn't allocate space for new memory map");
546 /* Register scanline events */
547 for (i
= 0; i
< mmap_num
; i
++)
549 scanline_events
[2 * i
].pos
= efiemu_mmap
[i
].physical_start
;
550 scanline_events
[2 * i
].type
= 0;
551 scanline_events
[2 * i
].memtype
= efiemu_mmap
[i
].type
;
552 scanline_events
[2 * i
+ 1].pos
= efiemu_mmap
[i
].physical_start
553 + efiemu_mmap
[i
].num_pages
* GRUB_EFIEMU_PAGESIZE
;
554 scanline_events
[2 * i
+ 1].type
= 1;
555 scanline_events
[2 * i
+ 1].memtype
= efiemu_mmap
[i
].type
;
558 /* Primitive bubble sort. It has complexity O(n^2) but since we're
559 unlikely to have more than 100 chunks it's probably one of the
560 fastest for one purpose */
565 for (i
= 0; i
< 2 * mmap_num
- 1; i
++)
566 if (scanline_events
[i
+ 1].pos
< scanline_events
[i
].pos
)
568 t
= scanline_events
[i
+ 1];
569 scanline_events
[i
+ 1] = scanline_events
[i
];
570 scanline_events
[i
] = t
;
575 /* Pointer in resulting memory map */
577 lastaddr
= scanline_events
[0].pos
;
578 lasttype
= scanline_events
[0].memtype
;
579 for (i
= 0; i
< 2 * mmap_num
; i
++)
582 if (scanline_events
[i
].type
)
583 present
[scanline_events
[i
].memtype
]--;
585 present
[scanline_events
[i
].memtype
]++;
587 /* Determine current region type */
589 for (k
= 0; k
< GRUB_EFI_MAX_MEMORY_TYPE
; k
++)
590 if (present
[k
] && (curtype
== -1 || priority
[k
] > priority
[curtype
]))
593 /* Add memory region to resulting map if necessary */
594 if ((curtype
== -1 || curtype
!= lasttype
)
595 && lastaddr
!= scanline_events
[i
].pos
598 result
[j
].virtual_start
= result
[j
].physical_start
= lastaddr
;
599 result
[j
].num_pages
= (scanline_events
[i
].pos
- lastaddr
)
600 / GRUB_EFIEMU_PAGESIZE
;
601 result
[j
].type
= lasttype
;
603 /* We set runtime attribute on pages we need to be mapped */
605 = (lasttype
== GRUB_EFI_RUNTIME_SERVICES_CODE
606 || lasttype
== GRUB_EFI_RUNTIME_SERVICES_DATA
)
607 ? GRUB_EFI_MEMORY_RUNTIME
: 0;
608 grub_dprintf ("efiemu",
609 "mmap entry: type %d start 0x%llx 0x%llx pages\n",
611 result
[j
].physical_start
, result
[j
].num_pages
);
615 /* Update last values if necessary */
616 if (curtype
== -1 || curtype
!= lasttype
)
619 lastaddr
= scanline_events
[i
].pos
;
623 grub_free (scanline_events
);
625 /* Shrink resulting memory map to really used size and replace efiemu_mmap
627 grub_free (efiemu_mmap
);
628 efiemu_mmap
= grub_realloc (result
, j
* sizeof (*result
));
629 return GRUB_ERR_NONE
;
632 /* This function is called to switch from first to second phase */
634 grub_efiemu_mm_do_alloc (void)
638 /* Preallocate mmap */
639 efiemu_mmap
= (grub_efi_memory_descriptor_t
*)
640 grub_malloc (mmap_reserved_size
* sizeof (grub_efi_memory_descriptor_t
));
643 grub_efiemu_unload ();
644 return grub_error (GRUB_ERR_OUT_OF_MEMORY
, "couldn't initialize mmap");
647 if ((err
= efiemu_alloc_requests ()))
649 if ((err
= grub_efiemu_mmap_fill ()))
651 return grub_efiemu_mmap_sort_and_uniq ();