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/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
;
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_uint32_t type
__attribute__ ((unused
)))
277 mmap_reserved_size
++;
281 // the place for memory used by efiemu itself
282 mmap_reserved_size
= GRUB_EFI_MAX_MEMORY_TYPE
+ 1;
285 grub_machine_mmap_iterate (bounds_hook
);
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
)
303 grub_error (GRUB_ERR_INVALID_COMMAND
,
304 "you need to first launch efiemu_prepare");
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
);
314 *memory_map_size
= mmap_num
* sizeof (grub_efi_memory_descriptor_t
);
315 grub_memcpy (memory_map
, efiemu_mmap
, *memory_map_size
);
317 *descriptor_size
= sizeof (grub_efi_memory_descriptor_t
);
318 if (descriptor_version
)
319 *descriptor_version
= 1;
326 /* Free everything */
328 grub_efiemu_mm_unload (void)
330 struct grub_efiemu_memrequest
*cur
, *d
;
331 for (cur
= memrequests
; cur
;)
338 grub_memset (&requested_memory
, 0, sizeof (requested_memory
));
339 grub_free (resident_memory
);
341 grub_free (efiemu_mmap
);
343 mmap_reserved_size
= mmap_num
= 0;
344 return GRUB_ERR_NONE
;
347 /* This function should be called before doing any requests */
349 grub_efiemu_mm_init (void)
353 err
= grub_efiemu_mm_unload ();
357 grub_efiemu_mmap_init ();
359 return GRUB_ERR_NONE
;
362 /* Copy host memory map */
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
,
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
);
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
);
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
);
398 grub_machine_mmap_iterate (fill_hook
);
401 return GRUB_ERR_NONE
;
405 grub_efiemu_mmap_iterate (int NESTED_FUNC_ATTR (*hook
) (grub_uint64_t
,
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
);
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
);
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
);
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
);
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
);
454 /* This function resolves overlapping regions and sorts the memory map
455 It uses scanline (sweeping) algorithm
458 grub_efiemu_mmap_sort_and_uniq (void)
460 /* If same page is used by multiple types it's resolved
461 according to priority
463 1 - memory immediately usable after ExitBootServices
464 2 - memory usable after loading ACPI tables
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
488 /* Scanline events */
489 struct grub_efiemu_mmap_scan
491 /* At which memory address*/
493 /* 0 = region starts, 1 = region ends */
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
;
504 /* Current scanline event */
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
)
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 */
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
;
556 /* Pointer in resulting memory map */
558 lastaddr
= scanline_events
[0].pos
;
559 lasttype
= scanline_events
[0].memtype
;
560 for (i
= 0; i
< 2 * mmap_num
; i
++)
563 if (scanline_events
[i
].type
)
564 present
[scanline_events
[i
].memtype
]--;
566 present
[scanline_events
[i
].memtype
]++;
568 /* Determine current region type */
570 for (k
= 0; k
< GRUB_EFI_MAX_MEMORY_TYPE
; k
++)
571 if (present
[k
] && (curtype
== -1 || priority
[k
] > priority
[curtype
]))
574 /* Add memory region to resulting map if necessary */
575 if ((curtype
== -1 || curtype
!= lasttype
)
576 && lastaddr
!= scanline_events
[i
].pos
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 */
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",
592 result
[j
].physical_start
, result
[j
].num_pages
);
596 /* Update last values if necessary */
597 if (curtype
== -1 || curtype
!= lasttype
)
600 lastaddr
= scanline_events
[i
].pos
;
604 grub_free (scanline_events
);
606 /* Shrink resulting memory map to really used size and replace efiemu_mmap
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 */
615 grub_efiemu_mm_do_alloc (void)
619 /* Preallocate mmap */
620 efiemu_mmap
= (grub_efi_memory_descriptor_t
*)
621 grub_malloc (mmap_reserved_size
* sizeof (grub_efi_memory_descriptor_t
));
624 grub_efiemu_unload ();
625 return grub_error (GRUB_ERR_OUT_OF_MEMORY
, "Couldn't initialize mmap");
628 if ((err
= efiemu_alloc_requests ()))
630 if ((err
= grub_efiemu_mmap_fill ()))
632 return grub_efiemu_mmap_sort_and_uniq ();