?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Upgraded GRUB2 to 2.00 release.
[AROS.git] / arch / all-pc / boot / grub2-aros / grub-core / lib / relocator.c
bloba45040a8c7d026a2083dc202ab9e397d5953e59d
1 /*
2 * GRUB -- GRand Unified Bootloader
3 * Copyright (C) 2009, 2010 Free Software Foundation, Inc.
4 *
5 * GRUB is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * GRUB is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with GRUB. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <grub/relocator.h>
20 #include <grub/relocator_private.h>
21 #include <grub/mm_private.h>
22 #include <grub/misc.h>
23 #include <grub/cache.h>
24 #include <grub/memory.h>
25 #include <grub/dl.h>
26 #include <grub/i18n.h>
27
28 GRUB_MOD_LICENSE ("GPLv3+");
29
30 struct grub_relocator
31 {
32 struct grub_relocator_chunk *chunks;
33 grub_phys_addr_t postchunks;
34 grub_phys_addr_t highestaddr;
35 grub_phys_addr_t highestnonpostaddr;
36 grub_size_t relocators_size;
37 };
38
39 struct grub_relocator_subchunk
40 {
41 enum {CHUNK_TYPE_IN_REGION, CHUNK_TYPE_REGION_START,
42 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
43 CHUNK_TYPE_FIRMWARE, CHUNK_TYPE_LEFTOVER
44 #endif
45 } type;
46 grub_mm_region_t reg;
47 grub_phys_addr_t start;
48 grub_size_t size;
49 grub_size_t pre_size;
50 struct grub_relocator_extra_block *extra;
51 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
52 struct grub_relocator_fw_leftover *pre, *post;
53 #endif
54 };
55
56 struct grub_relocator_chunk
57 {
58 struct grub_relocator_chunk *next;
59 grub_phys_addr_t src;
60 void *srcv;
61 grub_phys_addr_t target;
62 grub_size_t size;
63 struct grub_relocator_subchunk *subchunks;
64 unsigned nsubchunks;
65 };
66
67 struct grub_relocator_extra_block
68 {
69 struct grub_relocator_extra_block *next;
70 struct grub_relocator_extra_block **prev;
71 grub_phys_addr_t start;
72 grub_phys_addr_t end;
73 };
74
75 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
76 struct grub_relocator_fw_leftover
77 {
78 struct grub_relocator_fw_leftover *next;
79 struct grub_relocator_fw_leftover **prev;
80 grub_phys_addr_t quantstart;
81 grub_uint8_t freebytes[GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT / 8];
82 };
83
84 static struct grub_relocator_fw_leftover *leftovers;
85 #endif
86
87 static struct grub_relocator_extra_block *extra_blocks;
88
89 void *
90 get_virtual_current_address (grub_relocator_chunk_t in)
91 {
92 return in->srcv;
93 }
94
95 grub_phys_addr_t
96 get_physical_target_address (grub_relocator_chunk_t in)
97 {
98 return in->target;
99 }
100
101 struct grub_relocator *
102 grub_relocator_new (void)
103 {
104 struct grub_relocator *ret;
105
106 grub_cpu_relocator_init ();
107
108 ret = grub_zalloc (sizeof (struct grub_relocator));
109 if (!ret)
110 return NULL;
111
112 ret->postchunks = ~(grub_phys_addr_t) 0;
113 ret->relocators_size = grub_relocator_jumper_size;
114 grub_dprintf ("relocator", "relocators_size=%lu\n",
115 (unsigned long) ret->relocators_size);
116 return ret;
117 }
118
119 #define DIGITSORT_BITS 8
120 #define DIGITSORT_MASK ((1 << DIGITSORT_BITS) - 1)
121 #define BITS_IN_BYTE 8
122
123 #define max(a, b) (((a) > (b)) ? (a) : (b))
124 #define min(a, b) (((a) < (b)) ? (a) : (b))
125
126 static inline int
127 is_start (int type)
128 {
129 return !(type & 1) && (type != COLLISION_START);
130 }
131
132 static void
133 allocate_regstart (grub_phys_addr_t addr, grub_size_t size, grub_mm_region_t rb,
134 grub_mm_region_t *regancestor, grub_mm_header_t hancestor)
135 {
136 grub_addr_t newreg_start, newreg_raw_start
137 = (grub_addr_t) rb + (addr - grub_vtop (rb)) + size;
138 grub_addr_t newreg_size, newreg_presize;
139 grub_mm_header_t new_header;
140 grub_mm_header_t hb = (grub_mm_header_t) (rb + 1);
141
142 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
143 grub_dprintf ("relocator", "ra = %p, rb = %p\n", regancestor, rb);
144 #endif
145 newreg_start = ALIGN_UP (newreg_raw_start, GRUB_MM_ALIGN);
146 newreg_presize = newreg_start - newreg_raw_start;
147 newreg_size = rb->size - (newreg_start - (grub_addr_t) rb);
148 if ((hb->size << GRUB_MM_ALIGN_LOG2) >= newreg_start
149 - (grub_addr_t) rb)
150 {
151 grub_mm_header_t newhnext = hb->next;
152 grub_size_t newhsize = ((hb->size << GRUB_MM_ALIGN_LOG2)
153 - (newreg_start
154 - (grub_addr_t) rb)) >> GRUB_MM_ALIGN_LOG2;
155 new_header = (void *) (newreg_start + sizeof (*rb));
156 if (newhnext == hb)
157 newhnext = new_header;
158 new_header->next = newhnext;
159 new_header->size = newhsize;
160 new_header->magic = GRUB_MM_FREE_MAGIC;
161 }
162 else
163 {
164 new_header = hb->next;
165 if (new_header == hb)
166 new_header = (void *) (newreg_start + sizeof (*rb));
167 }
168 {
169 struct grub_mm_header *newregfirst = rb->first;
170 struct grub_mm_region *newregnext = rb->next;
171 struct grub_mm_region *newreg = (void *) newreg_start;
172 hancestor->next = new_header;
173 if (newregfirst == hb)
174 newregfirst = new_header;
175 newreg->first = newregfirst;
176 newreg->next = newregnext;
177 newreg->pre_size = newreg_presize;
178 newreg->size = newreg_size;
179 *regancestor = newreg;
180 {
181 grub_mm_header_t h = newreg->first, hp = NULL;
182 do
183 {
184 if ((void *) h < (void *) (newreg + 1))
185 grub_fatal ("Failed to adjust memory region: %p, %p, %p, %p, %p",
186 newreg, newreg->first, h, hp, hb);
187 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
188 if ((void *) h == (void *) (newreg + 1))
189 grub_dprintf ("relocator",
190 "Free start memory region: %p, %p, %p, %p, %p",
191 newreg, newreg->first, h, hp, hb);
192 #endif
193 hp = h;
194 h = h->next;
195 }
196 while (h != newreg->first);
197 }
198 }
199 }
200
201 static void
202 allocate_inreg (grub_phys_addr_t paddr, grub_size_t size,
203 grub_mm_header_t hb, grub_mm_header_t hbp,
204 grub_mm_region_t rb)
205 {
206 struct grub_mm_header *foll = NULL;
207 grub_addr_t vaddr = (grub_addr_t) hb + (paddr - grub_vtop (hb));
208
209 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
210 grub_dprintf ("relocator", "inreg paddr = 0x%lx, size = %lu,"
211 " hb = %p, hbp = %p, rb = %p, vaddr = 0x%lx\n",
212 (unsigned long) paddr, (unsigned long) size, hb, hbp,
213 rb, (unsigned long) vaddr);
214 #endif
215
216 if (ALIGN_UP (vaddr + size, GRUB_MM_ALIGN) + GRUB_MM_ALIGN
217 <= (grub_addr_t) (hb + hb->size))
218 {
219 foll = (void *) ALIGN_UP (vaddr + size, GRUB_MM_ALIGN);
220 foll->magic = GRUB_MM_FREE_MAGIC;
221 foll->size = hb + hb->size - foll;
222 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
223 grub_dprintf ("relocator", "foll = %p, foll->size = %lu\n", foll,
224 (unsigned long) foll->size);
225 #endif
226 }
227
228 if (vaddr - (grub_addr_t) hb >= sizeof (*hb))
229 {
230 hb->size = ((vaddr - (grub_addr_t) hb) >> GRUB_MM_ALIGN_LOG2);
231 if (foll)
232 {
233 foll->next = hb;
234 hbp->next = foll;
235 if (rb->first == hb)
236 {
237 rb->first = foll;
238 }
239 }
240 }
241 else
242 {
243 if (foll)
244 {
245 foll->next = hb->next;
246 }
247 else
248 foll = hb->next;
249
250 hbp->next = foll;
251 if (rb->first == hb)
252 {
253 rb->first = foll;
254 }
255 if (rb->first == hb)
256 {
257 rb->first = (void *) (rb + 1);
258 }
259 }
260 }
261
262 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
263 static void
264 check_leftover (struct grub_relocator_fw_leftover *lo)
265 {
266 unsigned i;
267 for (i = 0; i < sizeof (lo->freebytes); i++)
268 if (lo->freebytes[i] != 0xff)
269 return;
270 grub_relocator_firmware_free_region (lo->quantstart,
271 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
272 *lo->prev = lo->next;
273 if (lo->next)
274 lo->next->prev = lo->prev;
275 }
276 #endif
277
278 static void
279 free_subchunk (const struct grub_relocator_subchunk *subchu)
280 {
281 switch (subchu->type)
282 {
283 case CHUNK_TYPE_REGION_START:
284 {
285 grub_mm_region_t r1, r2, *rp;
286 grub_mm_header_t h;
287 grub_size_t pre_size;
288 r1 = subchu->reg;
289 r2 = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) subchu->reg
290 + (grub_vtop (subchu->reg)
291 - subchu->start) + subchu->size,
292 GRUB_MM_ALIGN);
293 for (rp = &grub_mm_base; *rp && *rp != r2; rp = &((*rp)->next));
294 pre_size = subchu->pre_size;
295
296 if (*rp)
297 {
298 grub_mm_header_t h2, *hp;
299 r1->first = r2->first;
300 r1->next = r2->next;
301 r1->pre_size = pre_size;
302 r1->size = r2->size + (r2 - r1) * sizeof (*r2);
303 *rp = r1;
304 h = (grub_mm_header_t) (r1 + 1);
305 h->next = r2->first;
306 h->magic = GRUB_MM_FREE_MAGIC;
307 h->size = (r2 - r1 - 1);
308 for (hp = &r2->first, h2 = *hp; h2->next != r2->first;
309 hp = &(h2->next), h2 = *hp)
310 if (h2 == (grub_mm_header_t) (r2 + 1))
311 break;
312 if (h2 == (grub_mm_header_t) (r2 + 1))
313 {
314 h->size = h2->size + (h2 - h);
315 h->next = h2->next;
316 *hp = h;
317 if (hp == &r2->first)
318 {
319 for (h2 = r2->first; h2->next != r2->first; h2 = h2->next);
320 h2->next = h;
321 }
322 }
323 else
324 {
325 h2->next = h;
326 }
327 }
328 else
329 {
330 r1->pre_size = pre_size;
331 r1->size = (r2 - r1) * sizeof (*r2);
332 /* Find where to insert this region.
333 Put a smaller one before bigger ones,
334 to prevent fragmentation. */
335 for (rp = &grub_mm_base; *rp; rp = &((*rp)->next))
336 if ((*rp)->size > r1->size)
337 break;
338 r1->next = *rp;
339 *rp = r1->next;
340 h = (grub_mm_header_t) (r1 + 1);
341 r1->first = h;
342 h->next = h;
343 h->magic = GRUB_MM_FREE_MAGIC;
344 h->size = (r2 - r1 - 1);
345 }
346 for (r2 = grub_mm_base; r2; r2 = r2->next)
347 if ((grub_addr_t) r2 + r2->size == (grub_addr_t) r1)
348 break;
349 if (r2)
350 {
351 grub_mm_header_t hl2, hl, g;
352 g = (grub_mm_header_t) ((grub_addr_t) r2 + r2->size);
353 g->size = (grub_mm_header_t) r1 - g;
354 r2->size += r1->size;
355 for (hl = r2->first; hl->next != r2->first; hl = hl->next);
356 for (hl2 = r1->first; hl2->next != r1->first; hl2 = hl2->next);
357 hl2->next = r2->first;
358 r2->first = r1->first;
359 hl->next = r2->first;
360 *rp = (*rp)->next;
361 grub_free (g + 1);
362 }
363 break;
364 }
365 case CHUNK_TYPE_IN_REGION:
366 {
367 grub_mm_header_t h = (grub_mm_header_t) ALIGN_DOWN ((grub_addr_t) subchu->start,
368 GRUB_MM_ALIGN);
369 h->size
370 = ((subchu->start + subchu->size + GRUB_MM_ALIGN - 1) / GRUB_MM_ALIGN)
371 - (subchu->start / GRUB_MM_ALIGN) - 1;
372 h->next = h;
373 h->magic = GRUB_MM_ALLOC_MAGIC;
374 grub_free (h + 1);
375 break;
376 }
377 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
378 case CHUNK_TYPE_FIRMWARE:
379 case CHUNK_TYPE_LEFTOVER:
380 {
381 grub_addr_t fstart, fend;
382 fstart = ALIGN_UP (subchu->start,
383 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
384 fend = ALIGN_DOWN (subchu->start + subchu->size,
385 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
386 if (fstart < fend)
387 grub_relocator_firmware_free_region (fstart, fend - fstart);
388 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
389 if (subchu->pre)
390 {
391 int off = subchu->start - fstart
392 - GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
393 grub_memset (subchu->pre->freebytes + off / 8 + 1,
394 0xff, sizeof (subchu->pre->freebytes) - off / 8 - 1);
395 subchu->pre->freebytes[off / 8] |= ~((1 << (off % 8)) - 1);
396 check_leftover (subchu->pre);
397 }
398 if (subchu->post)
399 {
400 int off = subchu->start + subchu->size - fend;
401 grub_memset (subchu->pre->freebytes,
402 0xff, sizeof (subchu->pre->freebytes) - off / 8);
403 subchu->pre->freebytes[off / 8] |= ((1 << (8 - (off % 8))) - 1);
404 check_leftover (subchu->post);
405 }
406 #endif
407 *subchu->extra->prev = subchu->extra->next;
408 grub_free (subchu->extra);
409 }
410 break;
411 #endif
412 }
413 }
414
415 static int
416 malloc_in_range (struct grub_relocator *rel,
417 grub_addr_t start, grub_addr_t end, grub_addr_t align,
418 grub_size_t size, struct grub_relocator_chunk *res,
419 int from_low_priv, int collisioncheck)
420 {
421 grub_mm_region_t r, *ra, base_saved;
422 struct grub_relocator_mmap_event *events = NULL, *eventt = NULL, *t;
423 /* 128 is just in case of additional malloc (shouldn't happen). */
424 unsigned maxevents = 2 + 128;
425 grub_mm_header_t p, pa;
426 unsigned *counter;
427 int nallocs = 0;
428 unsigned j, N = 0;
429 grub_addr_t target = 0;
430
431 grub_dprintf ("relocator",
432 "trying to allocate in 0x%lx-0x%lx aligned 0x%lx size 0x%lx\n",
433 (unsigned long) start, (unsigned long) end,
434 (unsigned long) align, (unsigned long) size);
435
436 start = ALIGN_UP (start, align);
437 end = ALIGN_DOWN (end - size, align) + size;
438
439 if (end < start + size)
440 return 0;
441
442 /* We have to avoid any allocations when filling scanline events.
443 Hence 2-stages.
444 */
445 for (r = grub_mm_base; r; r = r->next)
446 {
447 p = r->first;
448 do
449 {
450 if ((grub_addr_t) p < (grub_addr_t) (r + 1)
451 || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
452 grub_fatal ("%d: out of range pointer: %p\n", __LINE__, p);
453 maxevents += 2;
454 p = p->next;
455 }
456 while (p != r->first);
457 maxevents += 4;
458 }
459
460 if (collisioncheck && rel)
461 {
462 struct grub_relocator_chunk *chunk;
463 for (chunk = rel->chunks; chunk; chunk = chunk->next)
464 maxevents += 2;
465 }
466
467 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
468 {
469 struct grub_relocator_extra_block *cur;
470 for (cur = extra_blocks; cur; cur = cur->next)
471 maxevents += 2;
472 }
473 for (r = grub_mm_base; r; r = r->next)
474 maxevents += 2;
475
476 maxevents += grub_relocator_firmware_get_max_events ();
477 #endif
478
479 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
480 {
481 struct grub_relocator_fw_leftover *cur;
482 for (cur = leftovers; cur; cur = cur->next)
483 {
484 int l = 0;
485 unsigned i;
486 for (i = 0; i < GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT; i++)
487 {
488 if (l != ((cur->freebytes[i / 8] >> (i % 8)) & 1))
489 maxevents++;
490 l = ((cur->freebytes[i / 8] >> (i % 8)) & 1);
491 }
492 if (l)
493 maxevents++;
494 }
495 }
496 #endif
497
498 eventt = grub_malloc (maxevents * sizeof (events[0]));
499 counter = grub_malloc ((DIGITSORT_MASK + 2) * sizeof (counter[0]));
500 events = grub_malloc (maxevents * sizeof (events[0]));
501 if (!events || !eventt || !counter)
502 {
503 grub_dprintf ("relocator", "events or counter allocation failed %d\n",
504 maxevents);
505 grub_free (events);
506 grub_free (eventt);
507 grub_free (counter);
508 return 0;
509 }
510
511 if (collisioncheck && rel)
512 {
513 struct grub_relocator_chunk *chunk;
514 for (chunk = rel->chunks; chunk; chunk = chunk->next)
515 {
516 events[N].type = COLLISION_START;
517 events[N].pos = chunk->target;
518 N++;
519 events[N].type = COLLISION_END;
520 events[N].pos = chunk->target + chunk->size;
521 N++;
522 }
523 }
524
525 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
526 for (r = grub_mm_base; r; r = r->next)
527 {
528 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
529 grub_dprintf ("relocator", "Blocking at 0x%lx-0x%lx\n",
530 (unsigned long) r - r->pre_size,
531 (unsigned long) (r + 1) + r->size);
532 #endif
533 events[N].type = FIRMWARE_BLOCK_START;
534 events[N].pos = (grub_addr_t) r - r->pre_size;
535 N++;
536 events[N].type = FIRMWARE_BLOCK_END;
537 events[N].pos = (grub_addr_t) (r + 1) + r->size;
538 N++;
539 }
540 {
541 struct grub_relocator_extra_block *cur;
542 for (cur = extra_blocks; cur; cur = cur->next)
543 {
544 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
545 grub_dprintf ("relocator", "Blocking at 0x%lx-0x%lx\n",
546 (unsigned long) cur->start, (unsigned long) cur->end);
547 #endif
548 events[N].type = FIRMWARE_BLOCK_START;
549 events[N].pos = cur->start;
550 N++;
551 events[N].type = FIRMWARE_BLOCK_END;
552 events[N].pos = cur->end;
553 N++;
554 }
555 }
556
557 N += grub_relocator_firmware_fill_events (events + N);
558
559 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
560 {
561 struct grub_relocator_fw_leftover *cur;
562 for (cur = leftovers; cur; cur = cur->next)
563 {
564 unsigned i;
565 int l = 0;
566 for (i = 0; i < GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT; i++)
567 {
568 if (l != ((cur->freebytes[i / 8] >> (i % 8)) & 1))
569 {
570 events[N].type = l ? REG_LEFTOVER_END : REG_LEFTOVER_START;
571 events[N].pos = cur->quantstart + i;
572 events[N].leftover = cur;
573 N++;
574 }
575 l = ((cur->freebytes[i / 8] >> (i % 8)) & 1);
576 }
577 if (l)
578 {
579 events[N].type = REG_LEFTOVER_END;
580 events[N].pos = cur->quantstart + i;
581 events[N].leftover = cur;
582 N++;
583 }
584 }
585 }
586 #endif
587 #endif
588
589 /* No malloc from this point. */
590 base_saved = grub_mm_base;
591 grub_mm_base = NULL;
592
593 for (ra = &base_saved, r = *ra; r; ra = &(r->next), r = *ra)
594 {
595 pa = r->first;
596 p = pa->next;
597 if (p->magic == GRUB_MM_ALLOC_MAGIC)
598 continue;
599 do
600 {
601 if (p->magic != GRUB_MM_FREE_MAGIC)
602 grub_fatal (__FILE__":%d free magic broken at %p (0x%x)\n",
603 __LINE__, p, p->magic);
604 if (p == (grub_mm_header_t) (r + 1))
605 {
606 events[N].type = REG_BEG_START;
607 events[N].pos = grub_vtop (r) - r->pre_size;
608 events[N].reg = r;
609 events[N].regancestor = ra;
610 events[N].head = p;
611 events[N].hancestor = pa;
612 N++;
613 events[N].type = REG_BEG_END;
614 events[N].pos = grub_vtop (p + p->size) - sizeof (*r)
615 - sizeof (struct grub_mm_header);
616 N++;
617 }
618 else
619 {
620 events[N].type = IN_REG_START;
621 events[N].pos = grub_vtop (p);
622 events[N].head = p;
623 events[N].hancestor = pa;
624 events[N].reg = r;
625 N++;
626 events[N].type = IN_REG_END;
627 events[N].pos = grub_vtop (p + p->size);
628 N++;
629 }
630 pa = p;
631 p = pa->next;
632 }
633 while (pa != r->first);
634 }
635
636 /* Put ending events after starting events. */
637 {
638 int st = 0, e = N / 2;
639 for (j = 0; j < N; j++)
640 if (is_start (events[j].type) || events[j].type == COLLISION_START)
641 eventt[st++] = events[j];
642 else
643 eventt[e++] = events[j];
644 t = eventt;
645 eventt = events;
646 events = t;
647 }
648
649 {
650 unsigned i;
651 for (i = 0; i < (BITS_IN_BYTE * sizeof (grub_addr_t) / DIGITSORT_BITS);
652 i++)
653 {
654 memset (counter, 0, (1 + (1 << DIGITSORT_BITS)) * sizeof (counter[0]));
655 for (j = 0; j < N; j++)
656 counter[((events[j].pos >> (DIGITSORT_BITS * i))
657 & DIGITSORT_MASK) + 1]++;
658 for (j = 0; j <= DIGITSORT_MASK; j++)
659 counter[j+1] += counter[j];
660 for (j = 0; j < N; j++)
661 eventt[counter[((events[j].pos >> (DIGITSORT_BITS * i))
662 & DIGITSORT_MASK)]++] = events[j];
663 t = eventt;
664 eventt = events;
665 events = t;
666 }
667 }
668
669 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
670 retry:
671 #endif
672
673 /* Now events are nicely sorted. */
674 {
675 int nstarted = 0, ncollisions = 0, nstartedfw = 0, nblockfw = 0;
676 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
677 int nlefto = 0;
678 #else
679 const int nlefto = 0;
680 #endif
681 grub_addr_t starta = 0;
682 for (j = from_low_priv ? 0 : N - 1; from_low_priv ? j < N : (j + 1);
683 from_low_priv ? j++ : j--)
684 {
685 int isinsidebefore, isinsideafter;
686 isinsidebefore = (!ncollisions && (nstarted || (((nlefto || nstartedfw)
687 && !nblockfw))));
688 switch (events[j].type)
689 {
690 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
691 case REG_FIRMWARE_START:
692 nstartedfw++;
693 break;
694
695 case REG_FIRMWARE_END:
696 nstartedfw--;
697 break;
698
699 case FIRMWARE_BLOCK_START:
700 nblockfw++;
701 break;
702
703 case FIRMWARE_BLOCK_END:
704 nblockfw--;
705 break;
706 #endif
707
708 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
709 case REG_LEFTOVER_START:
710 nlefto++;
711 break;
712
713 case REG_LEFTOVER_END:
714 nlefto--;
715 break;
716 #endif
717
718 case COLLISION_START:
719 ncollisions++;
720 break;
721
722 case COLLISION_END:
723 ncollisions--;
724 break;
725
726 case IN_REG_START:
727 case REG_BEG_START:
728 nstarted++;
729 break;
730
731 case IN_REG_END:
732 case REG_BEG_END:
733 nstarted--;
734 break;
735 }
736 isinsideafter = (!ncollisions && (nstarted || ((nlefto || nstartedfw)
737 && !nblockfw)));
738 if (!isinsidebefore && isinsideafter)
739 starta = from_low_priv ? ALIGN_UP (events[j].pos, align)
740 : ALIGN_DOWN (events[j].pos - size, align) + size;
741 if (isinsidebefore && !isinsideafter && from_low_priv)
742 {
743 target = starta;
744 if (target < start)
745 target = start;
746 if (target + size <= end && target + size <= events[j].pos)
747 /* Found an usable address. */
748 goto found;
749 }
750 if (isinsidebefore && !isinsideafter && !from_low_priv)
751 {
752 target = starta - size;
753 if (target > end - size)
754 target = end - size;
755 if (target >= start && target >= events[j].pos)
756 goto found;
757 }
758 }
759 }
760
761 grub_mm_base = base_saved;
762 grub_free (events);
763 grub_free (eventt);
764 grub_free (counter);
765 return 0;
766
767 found:
768 {
769 int inreg = 0, regbeg = 0, ncol = 0;
770 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
771 int fwin = 0, fwb = 0, fwlefto = 0;
772 #endif
773 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
774 int last_lo = 0;
775 #endif
776 int last_start = 0;
777 for (j = 0; j < N; j++)
778 {
779 int typepre;
780 if (ncol)
781 typepre = -1;
782 else if (regbeg)
783 typepre = CHUNK_TYPE_REGION_START;
784 else if (inreg)
785 typepre = CHUNK_TYPE_IN_REGION;
786 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
787 else if (fwin && !fwb)
788 typepre = CHUNK_TYPE_FIRMWARE;
789 else if (fwlefto && !fwb)
790 typepre = CHUNK_TYPE_LEFTOVER;
791 #endif
792 else
793 typepre = -1;
794
795 if (j != 0 && events[j - 1].pos != events[j].pos)
796 {
797 grub_addr_t alloc_start, alloc_end;
798 alloc_start = max (events[j - 1].pos, target);
799 alloc_end = min (events[j].pos, target + size);
800 if (alloc_end > alloc_start)
801 {
802 switch (typepre)
803 {
804 case CHUNK_TYPE_REGION_START:
805 allocate_regstart (alloc_start, alloc_end - alloc_start,
806 events[last_start].reg,
807 events[last_start].regancestor,
808 events[last_start].hancestor);
809 /* TODO: maintain a reverse lookup tree for hancestor. */
810 {
811 unsigned k;
812 for (k = 0; k < N; k++)
813 if (events[k].hancestor == events[last_start].head)
814 events[k].hancestor = events[last_start].hancestor;
815 }
816 break;
817 case CHUNK_TYPE_IN_REGION:
818 allocate_inreg (alloc_start, alloc_end - alloc_start,
819 events[last_start].head,
820 events[last_start].hancestor,
821 events[last_start].reg);
822 {
823 unsigned k;
824 for (k = 0; k < N; k++)
825 if (events[k].hancestor == events[last_start].head)
826 events[k].hancestor = events[last_start].hancestor;
827 }
828 break;
829 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
830 case CHUNK_TYPE_FIRMWARE:
831 {
832 grub_addr_t fstart, fend;
833 fstart
834 = ALIGN_DOWN (alloc_start,
835 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
836 fend
837 = ALIGN_UP (alloc_end,
838 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
839 #ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
840 grub_dprintf ("relocator", "requesting %lx-%lx\n",
841 (unsigned long) fstart,
842 (unsigned long) fend);
843 #endif
844 /* The failure here can be very expensive. */
845 if (!grub_relocator_firmware_alloc_region (fstart,
846 fend - fstart))
847 {
848 if (from_low_priv)
849 start = fend;
850 else
851 end = fstart;
852 goto retry;
853 }
854 break;
855 }
856 #endif
857
858 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
859 case CHUNK_TYPE_LEFTOVER:
860 {
861 unsigned offstart = alloc_start
862 % GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
863 unsigned offend = alloc_end
864 % GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
865 struct grub_relocator_fw_leftover *lo
866 = events[last_lo].leftover;
867 lo->freebytes[offstart / 8]
868 &= ((1 << (8 - (start % 8))) - 1);
869 grub_memset (lo->freebytes + (offstart + 7) / 8, 0,
870 offend / 8 - (offstart + 7) / 8);
871 lo->freebytes[offend / 8] &= ~((1 << (offend % 8)) - 1);
872 }
873 break;
874 #endif
875 }
876 nallocs++;
877 }
878 }
879
880 switch (events[j].type)
881 {
882 case REG_BEG_START:
883 case IN_REG_START:
884 if (events[j].type == REG_BEG_START &&
885 (grub_addr_t) (events[j].reg + 1) > target)
886 regbeg++;
887 else
888 inreg++;
889 last_start = j;
890 break;
891
892 case REG_BEG_END:
893 case IN_REG_END:
894 if (regbeg)
895 regbeg--;
896 else
897 inreg--;
898 break;
899
900 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
901 case REG_FIRMWARE_START:
902 fwin++;
903 break;
904
905 case REG_FIRMWARE_END:
906 fwin--;
907 break;
908
909 case FIRMWARE_BLOCK_START:
910 fwb++;
911 break;
912
913 case FIRMWARE_BLOCK_END:
914 fwb--;
915 break;
916 #endif
917
918 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
919 case REG_LEFTOVER_START:
920 fwlefto++;
921 last_lo = j;
922 break;
923
924 case REG_LEFTOVER_END:
925 fwlefto--;
926 break;
927 #endif
928 case COLLISION_START:
929 ncol++;
930 break;
931 case COLLISION_END:
932 ncol--;
933 break;
934 }
935
936 }
937 }
938
939 /* Malloc is available again. */
940 grub_mm_base = base_saved;
941
942 grub_free (eventt);
943 grub_free (counter);
944
945 {
946 int last_start = 0;
947 int inreg = 0, regbeg = 0, ncol = 0;
948 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
949 int fwin = 0, fwlefto = 0, fwb = 0;
950 #endif
951 unsigned cural = 0;
952 int oom = 0;
953 res->subchunks = grub_malloc (sizeof (res->subchunks[0]) * nallocs);
954 if (!res->subchunks)
955 oom = 1;
956 res->nsubchunks = nallocs;
957
958 for (j = 0; j < N; j++)
959 {
960 int typepre;
961 if (ncol)
962 typepre = -1;
963 else if (regbeg)
964 typepre = CHUNK_TYPE_REGION_START;
965 else if (inreg)
966 typepre = CHUNK_TYPE_IN_REGION;
967 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
968 else if (fwin && !fwb)
969 typepre = CHUNK_TYPE_FIRMWARE;
970 else if (fwlefto && !fwb)
971 typepre = CHUNK_TYPE_LEFTOVER;
972 #endif
973 else
974 typepre = -1;
975
976 if (j != 0 && events[j - 1].pos != events[j].pos)
977 {
978 grub_addr_t alloc_start, alloc_end;
979 struct grub_relocator_subchunk tofree;
980 struct grub_relocator_subchunk *curschu = &tofree;
981 if (!oom)
982 curschu = &res->subchunks[cural];
983 alloc_start = max (events[j - 1].pos, target);
984 alloc_end = min (events[j].pos, target + size);
985 if (alloc_end > alloc_start)
986 {
987 grub_dprintf ("relocator", "subchunk 0x%lx-0x%lx, %d\n",
988 (unsigned long) alloc_start,
989 (unsigned long) alloc_end, typepre);
990 curschu->type = typepre;
991 curschu->start = alloc_start;
992 curschu->size = alloc_end - alloc_start;
993 if (typepre == CHUNK_TYPE_REGION_START
994 || typepre == CHUNK_TYPE_IN_REGION)
995 {
996 curschu->reg = events[last_start].reg;
997 curschu->pre_size = alloc_start - events[j - 1].pos;
998 }
999 if (!oom && (typepre == CHUNK_TYPE_REGION_START
1000 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
1001 || typepre == CHUNK_TYPE_FIRMWARE
1002 #endif
1003 ))
1004 {
1005 struct grub_relocator_extra_block *ne;
1006 ne = grub_malloc (sizeof (*ne));
1007 if (!ne)
1008 {
1009 oom = 1;
1010 grub_memcpy (&tofree, curschu, sizeof (tofree));
1011 }
1012 else
1013 {
1014 ne->start = alloc_start;
1015 ne->end = alloc_end;
1016 ne->next = extra_blocks;
1017 ne->prev = &extra_blocks;
1018 if (extra_blocks)
1019 extra_blocks->prev = &(ne->next);
1020 extra_blocks = ne;
1021 curschu->extra = ne;
1022 }
1023 }
1024
1025 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
1026 if (!oom && typepre == CHUNK_TYPE_FIRMWARE)
1027 {
1028 grub_addr_t fstart, fend;
1029
1030 fstart
1031 = ALIGN_DOWN (alloc_start,
1032 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
1033 fend
1034 = ALIGN_UP (alloc_end,
1035 GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
1036
1037 {
1038 struct grub_relocator_fw_leftover *lo1 = NULL;
1039 struct grub_relocator_fw_leftover *lo2 = NULL;
1040 if (fstart != alloc_start)
1041 lo1 = grub_malloc (sizeof (*lo1));
1042 if (fend != alloc_end)
1043 lo2 = grub_malloc (sizeof (*lo2));
1044 if ((!lo1 && fstart != alloc_start)
1045 || (!lo2 && fend != alloc_end))
1046 {
1047 struct grub_relocator_extra_block *ne;
1048 grub_free (lo1);
1049 grub_free (lo2);
1050 lo1 = NULL;
1051 lo2 = NULL;
1052 oom = 1;
1053 grub_memcpy (&tofree, curschu, sizeof (tofree));
1054 ne = extra_blocks;
1055 extra_blocks = extra_blocks->next;
1056 grub_free (ne);
1057 }
1058 if (lo1)
1059 {
1060 lo1->quantstart = fstart;
1061 grub_memset (lo1->freebytes, 0xff,
1062 (alloc_start - fstart) / 8);
1063 lo1->freebytes[(alloc_start - fstart) / 8]
1064 = (1 << ((alloc_start - fstart) % 8)) - 1;
1065 grub_memset (lo1->freebytes
1066 + ((alloc_start - fstart) / 8) + 1, 0,
1067 sizeof (lo1->freebytes)
1068 - (alloc_start - fstart) / 8 - 1);
1069 lo1->next = leftovers;
1070 lo1->prev = &leftovers;
1071 if (leftovers)
1072 leftovers->prev = &lo1->next;
1073 leftovers = lo1;
1074 }
1075 if (lo2)
1076 {
1077 lo2->quantstart
1078 = fend - GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
1079 grub_memset (lo2->freebytes, 0,
1080 (alloc_end - lo2->quantstart) / 8);
1081 lo2->freebytes[(alloc_end - lo2->quantstart) / 8]
1082 = ~((1 << ((alloc_end - lo2->quantstart) % 8)) - 1);
1083 grub_memset (lo2->freebytes
1084 + ((alloc_end - lo2->quantstart) / 8)
1085 + 1, 0, sizeof (lo2->freebytes)
1086 - (alloc_end - lo2->quantstart) / 8 - 1);
1087 lo2->prev = &leftovers;
1088 if (leftovers)
1089 leftovers->prev = &lo2->next;
1090 lo2->next = leftovers;
1091 leftovers = lo2;
1092 }
1093 curschu->pre = lo1;
1094 curschu->post = lo2;
1095 }
1096 }
1097
1098 if (typepre == CHUNK_TYPE_LEFTOVER)
1099 {
1100 curschu->pre = events[last_start].leftover;
1101 curschu->post = events[last_start].leftover;
1102 }
1103 #endif
1104
1105 if (!oom)
1106 cural++;
1107 else
1108 free_subchunk (&tofree);
1109 }
1110 }
1111
1112 switch (events[j].type)
1113 {
1114 case REG_BEG_START:
1115 case IN_REG_START:
1116 if (events[j].type == REG_BEG_START &&
1117 (grub_addr_t) (events[j].reg + 1) > target)
1118 regbeg++;
1119 else
1120 inreg++;
1121 last_start = j;
1122 break;
1123
1124 case REG_BEG_END:
1125 case IN_REG_END:
1126 inreg = regbeg = 0;
1127 break;
1128
1129 #if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
1130 case REG_FIRMWARE_START:
1131 fwin++;
1132 break;
1133
1134 case REG_FIRMWARE_END:
1135 fwin--;
1136 break;
1137
1138 case FIRMWARE_BLOCK_START:
1139 fwb++;
1140 break;
1141
1142 case FIRMWARE_BLOCK_END:
1143 fwb--;
1144 break;
1145 #endif
1146
1147 #if GRUB_RELOCATOR_HAVE_LEFTOVERS
1148 case REG_LEFTOVER_START:
1149 fwlefto++;
1150 break;
1151
1152 case REG_LEFTOVER_END:
1153 fwlefto--;
1154 break;
1155 #endif
1156 case COLLISION_START:
1157 ncol++;
1158 break;
1159 case COLLISION_END:
1160 ncol--;
1161 break;
1162 }
1163 }
1164 if (oom)
1165 {
1166 unsigned i;
1167 for (i = 0; i < cural; i++)
1168 free_subchunk (&res->subchunks[i]);
1169 grub_free (res->subchunks);
1170 grub_dprintf ("relocator", "allocation failed with out-of-memory\n");
1171 grub_free (events);
1172
1173 return 0;
1174 }
1175 }
1176
1177 res->src = target;
1178 res->size = size;
1179
1180 grub_free (events);
1181
1182 grub_dprintf ("relocator", "allocated: 0x%lx+0x%lx\n", (unsigned long) target,
1183 (unsigned long) size);
1184
1185 return 1;
1186 }
1187
1188 static void
1189 adjust_limits (struct grub_relocator *rel,
1190 grub_phys_addr_t *min_addr, grub_phys_addr_t *max_addr,
1191 grub_phys_addr_t in_min, grub_phys_addr_t in_max)
1192 {
1193 struct grub_relocator_chunk *chunk;
1194
1195 *min_addr = 0;
1196 *max_addr = rel->postchunks;
1197
1198 /* Keep chunks in memory in the same order as they'll be after relocation. */
1199 for (chunk = rel->chunks; chunk; chunk = chunk->next)
1200 {
1201 if (chunk->target > in_max && chunk->src < *max_addr
1202 && chunk->src < rel->postchunks)
1203 *max_addr = chunk->src;
1204 if (chunk->target + chunk->size <= in_min
1205 && chunk->src + chunk->size > *min_addr
1206 && chunk->src < rel->postchunks)
1207 *min_addr = chunk->src + chunk->size;
1208 }
1209 }
1210
1211 grub_err_t
1212 grub_relocator_alloc_chunk_addr (struct grub_relocator *rel,
1213 grub_relocator_chunk_t *out,
1214 grub_phys_addr_t target, grub_size_t size)
1215 {
1216 struct grub_relocator_chunk *chunk;
1217 grub_phys_addr_t min_addr = 0, max_addr;
1218
1219 if (target > ~size)
1220 return grub_error (GRUB_ERR_BUG, "address is out of range");
1221
1222 adjust_limits (rel, &min_addr, &max_addr, target, target);
1223
1224 for (chunk = rel->chunks; chunk; chunk = chunk->next)
1225 if ((chunk->target <= target && target < chunk->target + chunk->size)
1226 || (target <= chunk->target && chunk->target < target + size))
1227 return grub_error (GRUB_ERR_BUG, "overlap detected");
1228
1229 chunk = grub_malloc (sizeof (struct grub_relocator_chunk));
1230 if (!chunk)
1231 return grub_errno;
1232
1233 grub_dprintf ("relocator",
1234 "min_addr = 0x%llx, max_addr = 0x%llx, target = 0x%llx\n",
1235 (unsigned long long) min_addr, (unsigned long long) max_addr,
1236 (unsigned long long) target);
1237
1238 do
1239 {
1240 /* A trick to improve Linux allocation. */
1241 #if defined (__i386__) || defined (__x86_64__)
1242 if (target < 0x100000)
1243 if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
1244 size, chunk, 0, 1))
1245 {
1246 if (rel->postchunks > chunk->src)
1247 rel->postchunks = chunk->src;
1248 break;
1249 }
1250 #endif
1251 if (malloc_in_range (rel, target, max_addr, 1, size, chunk, 1, 0))
1252 break;
1253
1254 if (malloc_in_range (rel, min_addr, target, 1, size, chunk, 0, 0))
1255 break;
1256
1257 if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
1258 size, chunk, 0, 1))
1259 {
1260 if (rel->postchunks > chunk->src)
1261 rel->postchunks = chunk->src;
1262 break;
1263 }
1264
1265 grub_dprintf ("relocator", "not allocated\n");
1266 grub_free (chunk);
1267 return grub_error (GRUB_ERR_OUT_OF_MEMORY, N_("out of memory"));
1268 }
1269 while (0);
1270
1271 grub_dprintf ("relocator", "allocated 0x%llx/0x%llx\n",
1272 (unsigned long long) chunk->src, (unsigned long long) target);
1273
1274 if (rel->highestaddr < target + size)
1275 rel->highestaddr = target + size;
1276
1277 if (rel->highestaddr < chunk->src + size)
1278 rel->highestaddr = chunk->src + size;
1279
1280 if (chunk->src < rel->postchunks)
1281 {
1282 if (rel->highestnonpostaddr < target + size)
1283 rel->highestnonpostaddr = target + size;
1284
1285 if (rel->highestnonpostaddr < chunk->src + size)
1286 rel->highestnonpostaddr = chunk->src + size;
1287 }
1288
1289 grub_dprintf ("relocator", "relocators_size=%ld\n",
1290 (unsigned long) rel->relocators_size);
1291
1292 if (chunk->src < target)
1293 rel->relocators_size += grub_relocator_backward_size;
1294 if (chunk->src > target)
1295 rel->relocators_size += grub_relocator_forward_size;
1296
1297 grub_dprintf ("relocator", "relocators_size=%ld\n",
1298 (unsigned long) rel->relocators_size);
1299
1300 chunk->target = target;
1301 chunk->size = size;
1302 chunk->next = rel->chunks;
1303 rel->chunks = chunk;
1304 grub_dprintf ("relocator", "cur = %p, next = %p\n", rel->chunks,
1305 rel->chunks->next);
1306
1307 chunk->srcv = grub_map_memory (chunk->src, chunk->size);
1308 *out = chunk;
1309 #ifdef DEBUG_RELOCATOR
1310 grub_memset (chunk->srcv, 0xfa, chunk->size);
1311 grub_mm_check ();
1312 #endif
1313 return GRUB_ERR_NONE;
1314 }
1315
1316 grub_err_t
1317 grub_relocator_alloc_chunk_align (struct grub_relocator *rel,
1318 grub_relocator_chunk_t *out,
1319 grub_phys_addr_t min_addr,
1320 grub_phys_addr_t max_addr,
1321 grub_size_t size, grub_size_t align,
1322 int preference,
1323 int avoid_efi_boot_services)
1324 {
1325 grub_addr_t min_addr2 = 0, max_addr2;
1326 struct grub_relocator_chunk *chunk;
1327
1328 if (max_addr > ~size)
1329 max_addr = ~size;
1330
1331 #ifdef GRUB_MACHINE_PCBIOS
1332 if (min_addr < 0x1000)
1333 min_addr = 0x1000;
1334 #endif
1335
1336 grub_dprintf ("relocator", "chunks = %p\n", rel->chunks);
1337
1338 chunk = grub_malloc (sizeof (struct grub_relocator_chunk));
1339 if (!chunk)
1340 return grub_errno;
1341
1342 if (malloc_in_range (rel, min_addr, max_addr, align,
1343 size, chunk,
1344 preference != GRUB_RELOCATOR_PREFERENCE_HIGH, 1))
1345 {
1346 grub_dprintf ("relocator", "allocated 0x%llx/0x%llx\n",
1347 (unsigned long long) chunk->src,
1348 (unsigned long long) chunk->src);
1349 grub_dprintf ("relocator", "chunks = %p\n", rel->chunks);
1350 chunk->target = chunk->src;
1351 chunk->size = size;
1352 chunk->next = rel->chunks;
1353 rel->chunks = chunk;
1354 chunk->srcv = grub_map_memory (chunk->src, chunk->size);
1355 *out = chunk;
1356 return GRUB_ERR_NONE;
1357 }
1358
1359 adjust_limits (rel, &min_addr2, &max_addr2, min_addr, max_addr);
1360 grub_dprintf ("relocator", "Adjusted limits from %lx-%lx to %lx-%lx\n",
1361 (unsigned long) min_addr, (unsigned long) max_addr,
1362 (unsigned long) min_addr2, (unsigned long) max_addr2);
1363
1364 do
1365 {
1366 if (malloc_in_range (rel, min_addr2, max_addr2, align,
1367 size, chunk, 1, 1))
1368 break;
1369
1370 if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
1371 size, chunk, 0, 1))
1372 {
1373 if (rel->postchunks > chunk->src)
1374 rel->postchunks = chunk->src;
1375 break;
1376 }
1377
1378 return grub_error (GRUB_ERR_OUT_OF_MEMORY, N_("out of memory"));
1379 }
1380 while (0);
1381
1382 {
1383 int found = 0;
1384 auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t,
1385 grub_memory_type_t);
1386 int NESTED_FUNC_ATTR hook (grub_uint64_t addr, grub_uint64_t sz,
1387 grub_memory_type_t type)
1388 {
1389 grub_uint64_t candidate;
1390 if (type != GRUB_MEMORY_AVAILABLE)
1391 return 0;
1392 candidate = ALIGN_UP (addr, align);
1393 if (candidate < min_addr)
1394 candidate = ALIGN_UP (min_addr, align);
1395 if (candidate + size > addr + sz
1396 || candidate > ALIGN_DOWN (max_addr, align))
1397 return 0;
1398 if (preference == GRUB_RELOCATOR_PREFERENCE_HIGH)
1399 candidate = ALIGN_DOWN (min (addr + sz - size, max_addr), align);
1400 if (!found || (preference == GRUB_RELOCATOR_PREFERENCE_HIGH
1401 && candidate > chunk->target))
1402 chunk->target = candidate;
1403 if (!found || (preference == GRUB_RELOCATOR_PREFERENCE_LOW
1404 && candidate < chunk->target))
1405 chunk->target = candidate;
1406 found = 1;
1407 return 0;
1408 }
1409
1410 #ifdef GRUB_MACHINE_EFI
1411 grub_efi_mmap_iterate (hook, avoid_efi_boot_services);
1412 #elif defined (__powerpc__)
1413 (void) avoid_efi_boot_services;
1414 grub_machine_mmap_iterate (hook);
1415 #else
1416 (void) avoid_efi_boot_services;
1417 grub_mmap_iterate (hook);
1418 #endif
1419 if (!found)
1420 return grub_error (GRUB_ERR_BAD_OS, "couldn't find suitable memory target");
1421 }
1422 while (1)
1423 {
1424 struct grub_relocator_chunk *chunk2;
1425 for (chunk2 = rel->chunks; chunk2; chunk2 = chunk2->next)
1426 if ((chunk2->target <= chunk->target
1427 && chunk->target < chunk2->target + chunk2->size)
1428 || (chunk->target <= chunk2->target && chunk2->target
1429 < chunk->target + size))
1430 {
1431 if (preference == GRUB_RELOCATOR_PREFERENCE_HIGH)
1432 chunk->target = ALIGN_DOWN (chunk2->target, align);
1433 else
1434 chunk->target = ALIGN_UP (chunk2->target + chunk2->size, align);
1435 break;
1436 }
1437 if (!chunk2)
1438 break;
1439 }
1440
1441 grub_dprintf ("relocator", "relocators_size=%ld\n",
1442 (unsigned long) rel->relocators_size);
1443
1444 if (chunk->src < chunk->target)
1445 rel->relocators_size += grub_relocator_backward_size;
1446 if (chunk->src > chunk->target)
1447 rel->relocators_size += grub_relocator_forward_size;
1448
1449 grub_dprintf ("relocator", "relocators_size=%ld\n",
1450 (unsigned long) rel->relocators_size);
1451
1452 chunk->size = size;
1453 chunk->next = rel->chunks;
1454 rel->chunks = chunk;
1455 grub_dprintf ("relocator", "cur = %p, next = %p\n", rel->chunks,
1456 rel->chunks->next);
1457 chunk->srcv = grub_map_memory (chunk->src, chunk->size);
1458 *out = chunk;
1459 #ifdef DEBUG_RELOCATOR
1460 grub_memset (chunk->srcv, 0xfa, chunk->size);
1461 grub_mm_check ();
1462 #endif
1463 return GRUB_ERR_NONE;
1464 }
1465
1466 void
1467 grub_relocator_unload (struct grub_relocator *rel)
1468 {
1469 struct grub_relocator_chunk *chunk, *next;
1470 if (!rel)
1471 return;
1472 for (chunk = rel->chunks; chunk; chunk = next)
1473 {
1474 unsigned i;
1475 for (i = 0; i < chunk->nsubchunks; i++)
1476 free_subchunk (&chunk->subchunks[i]);
1477 grub_unmap_memory (chunk->srcv, chunk->size);
1478 next = chunk->next;
1479 grub_free (chunk->subchunks);
1480 grub_free (chunk);
1481 }
1482 grub_free (rel);
1483 }
1484
1485 grub_err_t
1486 grub_relocator_prepare_relocs (struct grub_relocator *rel, grub_addr_t addr,
1487 void **relstart, grub_size_t *relsize)
1488 {
1489 grub_uint8_t *rels;
1490 grub_uint8_t *rels0;
1491 struct grub_relocator_chunk *sorted;
1492 grub_size_t nchunks = 0;
1493 unsigned j;
1494 struct grub_relocator_chunk movers_chunk;
1495
1496 grub_dprintf ("relocator", "Preparing relocs (size=%ld)\n",
1497 (unsigned long) rel->relocators_size);
1498
1499 if (!malloc_in_range (rel, 0, ~(grub_addr_t)0 - rel->relocators_size + 1,
1500 grub_relocator_align,
1501 rel->relocators_size, &movers_chunk, 1, 1))
1502 return grub_error (GRUB_ERR_OUT_OF_MEMORY, N_("out of memory"));
1503 movers_chunk.srcv = rels = rels0
1504 = grub_map_memory (movers_chunk.src, movers_chunk.size);
1505
1506 if (relsize)
1507 *relsize = rel->relocators_size;
1508
1509 grub_dprintf ("relocator", "Relocs allocated at %p\n", movers_chunk.srcv);
1510
1511 {
1512 unsigned i;
1513 grub_size_t count[257];
1514 struct grub_relocator_chunk *from, *to, *tmp;
1515
1516 grub_memset (count, 0, sizeof (count));
1517
1518 {
1519 struct grub_relocator_chunk *chunk;
1520 for (chunk = rel->chunks; chunk; chunk = chunk->next)
1521 {
1522 grub_dprintf ("relocator", "chunk %p->%p, 0x%lx\n",
1523 (void *) chunk->src, (void *) chunk->target,
1524 (unsigned long) chunk->size);
1525 nchunks++;
1526 count[(chunk->src & 0xff) + 1]++;
1527 }
1528 }
1529 from = grub_malloc (nchunks * sizeof (sorted[0]));
1530 to = grub_malloc (nchunks * sizeof (sorted[0]));
1531 if (!from || !to)
1532 {
1533 grub_free (from);
1534 grub_free (to);
1535 return grub_errno;
1536 }
1537
1538 for (j = 0; j < 256; j++)
1539 count[j+1] += count[j];
1540
1541 {
1542 struct grub_relocator_chunk *chunk;
1543 for (chunk = rel->chunks; chunk; chunk = chunk->next)
1544 from[count[chunk->src & 0xff]++] = *chunk;
1545 }
1546
1547 for (i = 1; i < GRUB_CPU_SIZEOF_VOID_P; i++)
1548 {
1549 grub_memset (count, 0, sizeof (count));
1550 for (j = 0; j < nchunks; j++)
1551 count[((from[j].src >> (8 * i)) & 0xff) + 1]++;
1552 for (j = 0; j < 256; j++)
1553 count[j+1] += count[j];
1554 for (j = 0; j < nchunks; j++)
1555 to[count[(from[j].src >> (8 * i)) & 0xff]++] = from[j];
1556 tmp = to;
1557 to = from;
1558 from = tmp;
1559 }
1560 sorted = from;
1561 grub_free (to);
1562 }
1563
1564 for (j = 0; j < nchunks; j++)
1565 {
1566 grub_dprintf ("relocator", "sorted chunk %p->%p, 0x%lx\n",
1567 (void *) sorted[j].src, (void *) sorted[j].target,
1568 (unsigned long) sorted[j].size);
1569 if (sorted[j].src < sorted[j].target)
1570 {
1571 grub_cpu_relocator_backward ((void *) rels,
1572 sorted[j].srcv,
1573 grub_map_memory (sorted[j].target,
1574 sorted[j].size),
1575 sorted[j].size);
1576 rels += grub_relocator_backward_size;
1577 }
1578 if (sorted[j].src > sorted[j].target)
1579 {
1580 grub_cpu_relocator_forward ((void *) rels,
1581 sorted[j].srcv,
1582 grub_map_memory (sorted[j].target,
1583 sorted[j].size),
1584 sorted[j].size);
1585 rels += grub_relocator_forward_size;
1586 }
1587 if (sorted[j].src == sorted[j].target)
1588 grub_arch_sync_caches (sorted[j].srcv, sorted[j].size);
1589 }
1590 grub_cpu_relocator_jumper ((void *) rels, (grub_addr_t) addr);
1591 *relstart = rels0;
1592 grub_free (sorted);
1593 return GRUB_ERR_NONE;
1594 }
1595
1596 void
1597 grub_mm_check_real (char *file, int line)
1598 {
1599 grub_mm_region_t r;
1600 grub_mm_header_t p, pa;
1601
1602 for (r = grub_mm_base; r; r = r->next)
1603 {
1604 pa = r->first;
1605 p = pa->next;
1606 if (p->magic == GRUB_MM_ALLOC_MAGIC)
1607 continue;
1608 do
1609 {
1610 if ((grub_addr_t) p < (grub_addr_t) (r + 1)
1611 || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
1612 grub_fatal ("%s:%d: out of range pointer: %p\n", file, line, p);
1613 if (p->magic != GRUB_MM_FREE_MAGIC)
1614 grub_fatal ("%s:%d free magic broken at %p (0x%x)\n", file,
1615 line, p, p->magic);
1616 pa = p;
1617 p = pa->next;
1618 }
1619 while (pa != r->first);
1620 }
1621 }
Mirror of AROS' svn.