grub-core/lib/relocator.c

/*
 *  GRUB  --  GRand Unified Bootloader
 *  Copyright (C) 2009, 2010  Free Software Foundation, Inc.
 *  Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
 *
 *  GRUB is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  GRUB is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <grub/relocator.h>
#include <grub/relocator_private.h>
#include <grub/mm_private.h>
#include <grub/misc.h>
#include <grub/cache.h>
#include <grub/memory.h>
#include <grub/dl.h>

GRUB_MOD_LICENSE ("GPLv3+");

struct grub_relocator
{
  struct grub_relocator_chunk *chunks;
  grub_phys_addr_t postchunks;
  grub_phys_addr_t highestaddr;
  grub_phys_addr_t highestnonpostaddr;
  grub_size_t relocators_size;
};

struct grub_relocator_subchunk
{
  enum {CHUNK_TYPE_IN_REGION, CHUNK_TYPE_REGION_START,
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
    CHUNK_TYPE_FIRMWARE, CHUNK_TYPE_LEFTOVER
#endif
  } type;
  grub_mm_region_t reg;
  grub_phys_addr_t start;
  grub_size_t size;
  grub_size_t pre_size;
  struct grub_relocator_extra_block *extra;
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
  struct grub_relocator_fw_leftover *pre, *post;
#endif
};

struct grub_relocator_chunk
{
  struct grub_relocator_chunk *next;
  grub_phys_addr_t src;
  void *srcv;
  grub_phys_addr_t target;
  grub_size_t size;
  struct grub_relocator_subchunk *subchunks;
  unsigned nsubchunks;
};

struct grub_relocator_extra_block
{
  struct grub_relocator_extra_block *next;
  struct grub_relocator_extra_block **prev;
  grub_phys_addr_t start;
  grub_phys_addr_t end;
};

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
struct grub_relocator_fw_leftover
{
  struct grub_relocator_fw_leftover *next;
  struct grub_relocator_fw_leftover **prev;
  grub_phys_addr_t quantstart;
  grub_uint8_t freebytes[GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT / 8];
};

static struct grub_relocator_fw_leftover *leftovers;
#endif

static struct grub_relocator_extra_block *extra_blocks;

void *
get_virtual_current_address (grub_relocator_chunk_t in)
{
  return in->srcv;
}

grub_phys_addr_t
get_physical_target_address (grub_relocator_chunk_t in)
{
  return in->target;
}

struct grub_relocator *
grub_relocator_new (void)
{
  struct grub_relocator *ret;

  grub_cpu_relocator_init ();

  ret = grub_zalloc (sizeof (struct grub_relocator));
  if (!ret)
    return NULL;

  ret->postchunks = ~(grub_phys_addr_t) 0;
  ret->relocators_size = grub_relocator_jumper_size;
  grub_dprintf ("relocator", "relocators_size=%lu\n",
        (unsigned long) ret->relocators_size);
  return ret;
}

#define DIGITSORT_BITS 8
#define DIGITSORT_MASK ((1 << DIGITSORT_BITS) - 1)
#define BITS_IN_BYTE 8

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

static inline int
is_start (int type)
{
  return !(type & 1) && (type != COLLISION_START);
}

static void
allocate_regstart (grub_phys_addr_t addr, grub_size_t size, grub_mm_region_t rb,
           grub_mm_region_t *regancestor, grub_mm_header_t hancestor)
{
  grub_addr_t newreg_start, newreg_raw_start
    = (grub_addr_t) rb + (addr - grub_vtop (rb)) + size;
  grub_addr_t newreg_size, newreg_presize;
  grub_mm_header_t new_header;
  grub_mm_header_t hb = (grub_mm_header_t) (rb + 1);

#ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
  grub_dprintf ("relocator", "ra = %p, rb = %p\n", regancestor, rb);
#endif
  newreg_start = ALIGN_UP (newreg_raw_start, GRUB_MM_ALIGN);
  newreg_presize = newreg_start - newreg_raw_start;
  newreg_size = rb->size - (newreg_start - (grub_addr_t) rb);
  if ((hb->size << GRUB_MM_ALIGN_LOG2) >= newreg_start
      - (grub_addr_t) rb)
    {
      grub_mm_header_t newhnext = hb->next;
      grub_size_t newhsize = ((hb->size << GRUB_MM_ALIGN_LOG2)
                  - (newreg_start
                 - (grub_addr_t) rb)) >> GRUB_MM_ALIGN_LOG2;
      new_header = (void *) (newreg_start + sizeof (*rb));
      if (newhnext == hb)
    newhnext = new_header;
      new_header->next = newhnext;
      new_header->size = newhsize;
      new_header->magic = GRUB_MM_FREE_MAGIC;
    }
  else
    {
      new_header = hb->next;
      if (new_header == hb)
    new_header = (void *) (newreg_start + sizeof (*rb));
    }
  {
    struct grub_mm_header *newregfirst = rb->first;
    struct grub_mm_region *newregnext = rb->next;
    struct grub_mm_region *newreg = (void *) newreg_start;
    hancestor->next = new_header;
    if (newregfirst == hb)
      newregfirst = new_header;
    newreg->first = newregfirst;
    newreg->next = newregnext;
    newreg->pre_size = newreg_presize;
    newreg->size = newreg_size;
    *regancestor = newreg;
    {
      grub_mm_header_t h = newreg->first, hp = NULL;
      do
    {
      if ((void *) h < (void *) (newreg + 1))
        grub_fatal ("Failed to adjust memory region: %p, %p, %p, %p, %p",
            newreg, newreg->first, h, hp, hb);
#ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
      if ((void *) h == (void *) (newreg + 1))
        grub_dprintf ("relocator",
              "Free start memory region: %p, %p, %p, %p, %p",
              newreg, newreg->first, h, hp, hb);
#endif
      hp = h;
      h = h->next;
    }
      while (h != newreg->first);
    }
  }
}

static void
allocate_inreg (grub_phys_addr_t paddr, grub_size_t size,
        grub_mm_header_t hb, grub_mm_header_t hbp,
        grub_mm_region_t rb)
{
  struct grub_mm_header *foll = NULL;
  grub_addr_t vaddr = (grub_addr_t) hb + (paddr - grub_vtop (hb));

#ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
  grub_dprintf ("relocator", "inreg paddr = 0x%lx, size = %lu,"
        " hb = %p, hbp = %p, rb = %p, vaddr = 0x%lx\n",
        (unsigned long) paddr, (unsigned long) size, hb, hbp,
        rb, (unsigned long) vaddr);
#endif

  if (ALIGN_UP (vaddr + size, GRUB_MM_ALIGN) + GRUB_MM_ALIGN
      <= (grub_addr_t) (hb + hb->size))
    {
      foll = (void *) ALIGN_UP (vaddr + size, GRUB_MM_ALIGN);
      foll->magic = GRUB_MM_FREE_MAGIC;
      foll->size = hb + hb->size - foll;
#ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
      grub_dprintf ("relocator", "foll = %p, foll->size = %lu\n", foll,
            (unsigned long) foll->size);
#endif
    }

  if (vaddr - (grub_addr_t) hb >= sizeof (*hb))
    {
      hb->size = ((vaddr - (grub_addr_t) hb) >> GRUB_MM_ALIGN_LOG2);
      if (foll)
    {
      foll->next = hb;
      hbp->next = foll;
      if (rb->first == hb)
        {
          rb->first = foll;
        }
    }
    }
  else
    {
      if (foll)
    {
      foll->next = hb->next;
    }
      else
    foll = hb->next;

      hbp->next = foll;
      if (rb->first == hb)
    {
      rb->first = foll;
    }
      if (rb->first == hb)
    {
      rb->first = (void *) (rb + 1);
    }
    }
}

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
static void
check_leftover (struct grub_relocator_fw_leftover *lo)
{
  unsigned i;
  for (i = 0; i < sizeof (lo->freebytes); i++)
    if (lo->freebytes[i] != 0xff)
      return;
  grub_relocator_firmware_free_region (lo->quantstart,
                       GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
  *lo->prev = lo->next;
  if (lo->next)
    lo->next->prev = lo->prev;
}
#endif

static void
free_subchunk (const struct grub_relocator_subchunk *subchu)
{
  switch (subchu->type)
    {
    case CHUNK_TYPE_REGION_START:
      {
    grub_mm_region_t r1, r2, *rp;
    grub_mm_header_t h;
    grub_size_t pre_size;
    r1 = subchu->reg;
    r2 = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) subchu->reg
                      + (grub_vtop (subchu->reg)
                         - subchu->start) + subchu->size,
                      GRUB_MM_ALIGN);
    for (rp = &grub_mm_base; *rp && *rp != r2; rp = &((*rp)->next));
    pre_size = subchu->pre_size;

    if (*rp)
      {
        grub_mm_header_t h2, *hp;
        r1->first = r2->first;
        r1->next = r2->next;
        r1->pre_size = pre_size;
        r1->size = r2->size + (r2 - r1) * sizeof (*r2);
        *rp = r1;
        h = (grub_mm_header_t) (r1 + 1);
        h->next = r2->first;
        h->magic = GRUB_MM_FREE_MAGIC;
        h->size = (r2 - r1 - 1);
        for (hp = &r2->first, h2 = *hp; h2->next != r2->first;
         hp = &(h2->next), h2 = *hp)
          if (h2 == (grub_mm_header_t) (r2 + 1))
        break;
        if (h2 == (grub_mm_header_t) (r2 + 1))
          {
        h->size = h2->size + (h2 - h);
        h->next = h2->next;
        *hp = h;
        if (hp == &r2->first)
          {
            for (h2 = r2->first; h2->next != r2->first; h2 = h2->next);
            h2->next = h;
          }
          }
        else
          {
        h2->next = h;
          }
      }
    else
      {
        r1->pre_size = pre_size;
        r1->size = (r2 - r1) * sizeof (*r2);
        /* Find where to insert this region.
           Put a smaller one before bigger ones,
           to prevent fragmentation.  */
        for (rp = &grub_mm_base; *rp; rp = &((*rp)->next))
          if ((*rp)->size > r1->size)
        break;
        r1->next = *rp;
        *rp = r1->next;
        h = (grub_mm_header_t) (r1 + 1);
        r1->first = h;
        h->next = h;
        h->magic = GRUB_MM_FREE_MAGIC;
        h->size = (r2 - r1 - 1);
      }
    for (r2 = grub_mm_base; r2; r2 = r2->next)
      if ((grub_addr_t) r2 + r2->size == (grub_addr_t) r1)
        break;
    if (r2)
      {
        grub_mm_header_t hl2, hl, g;
        g = (grub_mm_header_t) ((grub_addr_t) r2 + r2->size);
        g->size = (grub_mm_header_t) r1 - g;
        r2->size += r1->size;
        for (hl = r2->first; hl->next != r2->first; hl = hl->next);
        for (hl2 = r1->first; hl2->next != r1->first; hl2 = hl2->next);
        hl2->next = r2->first;
        r2->first = r1->first;
        hl->next = r2->first;
        *rp = (*rp)->next;
        grub_free (g + 1);
      }
    break;
      }
    case CHUNK_TYPE_IN_REGION:
      {
    grub_mm_header_t h = (grub_mm_header_t) ALIGN_DOWN ((grub_addr_t) subchu->start,
                                GRUB_MM_ALIGN);
    h->size
      = ((subchu->start + subchu->size + GRUB_MM_ALIGN - 1) / GRUB_MM_ALIGN)
      - (subchu->start / GRUB_MM_ALIGN) - 1;
    h->next = h;
    h->magic = GRUB_MM_ALLOC_MAGIC;
    grub_free (h + 1);
    break;
      }
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
    case CHUNK_TYPE_FIRMWARE:
    case CHUNK_TYPE_LEFTOVER:
      {
    grub_addr_t fstart, fend;
    fstart = ALIGN_UP (subchu->start,
               GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
    fend = ALIGN_DOWN (subchu->start + subchu->size,
               GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
    if (fstart < fend)
      grub_relocator_firmware_free_region (fstart, fend - fstart);
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
    if (subchu->pre)
      {
        int off = subchu->start - fstart
          - GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
        grub_memset (subchu->pre->freebytes + off / 8 + 1,
             0xff, sizeof (subchu->pre->freebytes) - off / 8 - 1);
        subchu->pre->freebytes[off / 8] |= ~((1 << (off % 8)) - 1);
        check_leftover (subchu->pre);
      }
    if (subchu->post)
      {
        int off = subchu->start + subchu->size - fend;
        grub_memset (subchu->pre->freebytes,
             0xff, sizeof (subchu->pre->freebytes) - off / 8);
        subchu->pre->freebytes[off / 8] |= ((1 << (8 - (off % 8))) - 1);
        check_leftover (subchu->post);
      }
#endif
    *subchu->extra->prev = subchu->extra->next;
    grub_free (subchu->extra);
      }
      break;
#endif
    }
}

static int
malloc_in_range (struct grub_relocator *rel,
         grub_addr_t start, grub_addr_t end, grub_addr_t align,
         grub_size_t size, struct grub_relocator_chunk *res,
         int from_low_priv, int collisioncheck)
{
  grub_mm_region_t r, *ra, base_saved;
  struct grub_relocator_mmap_event *events = NULL, *eventt = NULL, *t;
  /* 128 is just in case of additional malloc (shouldn't happen).  */
  unsigned maxevents = 2 + 128;
  grub_mm_header_t p, pa;
  unsigned *counter;
  int nallocs = 0;
  unsigned j, N = 0;
  grub_addr_t target = 0;

  grub_dprintf ("relocator",
        "trying to allocate in 0x%lx-0x%lx aligned 0x%lx size 0x%lx\n",
        (unsigned long) start, (unsigned long) end,
        (unsigned long) align, (unsigned long) size);

  start = ALIGN_UP (start, align);
  end = ALIGN_DOWN (end - size, align) + size;

  if (end < start + size)
    return 0;

  /* We have to avoid any allocations when filling scanline events.
     Hence 2-stages.
   */
  for (r = grub_mm_base; r; r = r->next)
    {
      p = r->first;
      do
    {
      if ((grub_addr_t) p < (grub_addr_t) (r + 1)
          || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
        grub_fatal ("%d: out of range pointer: %p\n", __LINE__, p);
      maxevents += 2;
      p = p->next;
    }
      while (p != r->first);
      maxevents += 4;
    }

  if (collisioncheck && rel)
    {
      struct grub_relocator_chunk *chunk;
      for (chunk = rel->chunks; chunk; chunk = chunk->next)
    maxevents += 2;
    }

#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
  {
    struct grub_relocator_extra_block *cur;
    for (cur = extra_blocks; cur; cur = cur->next)
      maxevents += 2;
  }
  for (r = grub_mm_base; r; r = r->next)
    maxevents += 2;

  maxevents += grub_relocator_firmware_get_max_events ();
#endif

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
  {
    struct grub_relocator_fw_leftover *cur;
    for (cur = leftovers; cur; cur = cur->next)
      {
    int l = 0;
    unsigned i;
    for (i = 0; i < GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT; i++)
      {
        if (l != ((cur->freebytes[i / 8] >> (i % 8)) & 1))
          maxevents++;
        l = ((cur->freebytes[i / 8] >> (i % 8)) & 1);
      }
    if (l)
      maxevents++;
      }
  }
#endif

  events = grub_malloc (maxevents * sizeof (events[0]));
  eventt = grub_malloc (maxevents * sizeof (events[0]));
  counter = grub_malloc ((DIGITSORT_MASK + 2) * sizeof (counter[0]));
  if (!events || !eventt || !counter)
    {
      grub_dprintf ("relocator", "events or counter allocation failed %d\n",
            maxevents);
      grub_free (events);
      grub_free (eventt);
      grub_free (counter);
      return 0;
    }

  if (collisioncheck && rel)
    {
      struct grub_relocator_chunk *chunk;
      for (chunk = rel->chunks; chunk; chunk = chunk->next)
    {
      events[N].type = COLLISION_START;
      events[N].pos = chunk->target;
      N++;
      events[N].type = COLLISION_END;
      events[N].pos = chunk->target + chunk->size;
      N++;
    }
    }

#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
  for (r = grub_mm_base; r; r = r->next)
    {
      grub_dprintf ("relocator", "Blocking at 0x%lx-0x%lx\n",
            (unsigned long) r - r->pre_size,
            (unsigned long) (r + 1) + r->size);
      events[N].type = FIRMWARE_BLOCK_START;
      events[N].pos = (grub_addr_t) r - r->pre_size;
      N++;
      events[N].type = FIRMWARE_BLOCK_END;
      events[N].pos = (grub_addr_t) (r + 1) + r->size;
      N++;
    }
  {
    struct grub_relocator_extra_block *cur;
    for (cur = extra_blocks; cur; cur = cur->next)
      {
    grub_dprintf ("relocator", "Blocking at 0x%lx-0x%lx\n",
              (unsigned long) cur->start, (unsigned long) cur->end);
    events[N].type = FIRMWARE_BLOCK_START;
    events[N].pos = cur->start;
    N++;
    events[N].type = FIRMWARE_BLOCK_END;
    events[N].pos = cur->end;
    N++;
      }
  }

  N += grub_relocator_firmware_fill_events (events + N);

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
  {
    struct grub_relocator_fw_leftover *cur;
    for (cur = leftovers; cur; cur = cur->next)
      {
    unsigned i;
    int l = 0;
    for (i = 0; i < GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT; i++)
      {
        if (l != ((cur->freebytes[i / 8] >> (i % 8)) & 1))
          {
        events[N].type = l ? REG_LEFTOVER_END : REG_LEFTOVER_START;
        events[N].pos = cur->quantstart + i;
        events[N].leftover = cur;
        N++;
          }
        l = ((cur->freebytes[i / 8] >> (i % 8)) & 1);
      }
    if (l)
      {
        events[N].type = REG_LEFTOVER_END;
        events[N].pos = cur->quantstart + i;
        events[N].leftover = cur;
        N++;
      }
      }
  }
#endif
#endif

  /* No malloc from this point.  */
  base_saved = grub_mm_base;
  grub_mm_base = NULL;

  for (ra = &base_saved, r = *ra; r; ra = &(r->next), r = *ra)
    {
      pa = r->first;
      p = pa->next;
      if (p->magic == GRUB_MM_ALLOC_MAGIC)
    continue;
      do
    {
      if (p->magic != GRUB_MM_FREE_MAGIC)
        grub_fatal (__FILE__":%d free magic broken at %p (0x%x)\n",
            __LINE__, p, p->magic);
      if (p == (grub_mm_header_t) (r + 1))
        {
          events[N].type = REG_BEG_START;
          events[N].pos = grub_vtop (r) - r->pre_size;
          events[N].reg = r;
          events[N].regancestor = ra;
          events[N].head = p;
          events[N].hancestor = pa;
          N++;
          events[N].type = REG_BEG_END;
          events[N].pos = grub_vtop (p + p->size) - sizeof (*r)
        - sizeof (struct grub_mm_header);
          N++;
        }
      else
        {
          events[N].type = IN_REG_START;
          events[N].pos = grub_vtop (p);
          events[N].head = p;
          events[N].hancestor = pa;
          events[N].reg = r;
          N++;
          events[N].type = IN_REG_END;
          events[N].pos = grub_vtop (p + p->size);
          N++;
        }
      pa = p;
      p = pa->next;
    }
      while (pa != r->first);
    }

  /* Put ending events after starting events.  */
  {
    int st = 0, e = N / 2;
    for (j = 0; j < N; j++)
      if (is_start (events[j].type) || events[j].type == COLLISION_START)
    eventt[st++] = events[j];
      else
    eventt[e++] = events[j];
    t = eventt;
    eventt = events;
    events = t;
  }

  {
    unsigned i;
    for (i = 0; i < (BITS_IN_BYTE * sizeof (grub_addr_t) / DIGITSORT_BITS);
     i++)
      {
    memset (counter, 0, (1 + (1 << DIGITSORT_BITS)) * sizeof (counter[0]));
    for (j = 0; j < N; j++)
      counter[((events[j].pos >> (DIGITSORT_BITS * i))
           & DIGITSORT_MASK) + 1]++;
    for (j = 0; j <= DIGITSORT_MASK; j++)
      counter[j+1] += counter[j];
    for (j = 0; j < N; j++)
      eventt[counter[((events[j].pos >> (DIGITSORT_BITS * i))
              & DIGITSORT_MASK)]++] = events[j];
    t = eventt;
    eventt = events;
    events = t;
      }
  }

#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 retry:
#endif

  /* Now events are nicely sorted.  */
  {
    int nstarted = 0, ncollisions = 0, nstartedfw = 0, nblockfw = 0;
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
    int nlefto = 0;
#else
    const int nlefto = 0;
#endif
    grub_addr_t starta = 0;
    for (j = from_low_priv ? 0 : N - 1; from_low_priv ? j < N : (j + 1);
     from_low_priv ? j++ : j--)
      {
    int isinsidebefore, isinsideafter;
    isinsidebefore = (!ncollisions && (nstarted || (((nlefto || nstartedfw)
                             && !nblockfw))));
    switch (events[j].type)
      {
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
      case REG_FIRMWARE_START:
        nstartedfw++;
        break;

      case REG_FIRMWARE_END:
        nstartedfw--;
        break;

      case FIRMWARE_BLOCK_START:
        nblockfw++;
        break;

      case FIRMWARE_BLOCK_END:
        nblockfw--;
        break;
#endif

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
      case REG_LEFTOVER_START:
        nlefto++;
        break;

      case REG_LEFTOVER_END:
        nlefto--;
        break;
#endif

      case COLLISION_START:
        ncollisions++;
        break;

      case COLLISION_END:
        ncollisions--;
        break;

      case IN_REG_START:
      case REG_BEG_START:
        nstarted++;
        break;

      case IN_REG_END:
      case REG_BEG_END:
        nstarted--;
        break;
      }
    isinsideafter = (!ncollisions && (nstarted || ((nlefto || nstartedfw)
                               && !nblockfw)));
    if (!isinsidebefore && isinsideafter)
      starta = from_low_priv ? ALIGN_UP (events[j].pos, align)
        : ALIGN_DOWN (events[j].pos - size, align) + size;
    if (isinsidebefore && !isinsideafter && from_low_priv)
      {
        target = starta;
        if (target < start)
          target = start;
        if (target + size <= end && target + size <= events[j].pos)
          /* Found an usable address.  */
          goto found;
      }
    if (isinsidebefore && !isinsideafter && !from_low_priv)
      {
        target = starta - size;
        if (target > end - size)
          target = end - size;
        if (target >= start && target >= events[j].pos)
          goto found;
      }
      }
  }

  grub_mm_base = base_saved;
  grub_free (events);
  grub_free (eventt);
  grub_free (counter);
  return 0;

 found:
  {
    int inreg = 0, regbeg = 0, ncol = 0;
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
    int fwin = 0, fwb = 0, fwlefto = 0;
#endif
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
    int last_lo = 0;
#endif
    int last_start = 0;
    for (j = 0; j < N; j++)
      {
    int typepre;
    if (ncol)
      typepre = -1;
    else if (regbeg)
      typepre = CHUNK_TYPE_REGION_START;
    else if (inreg)
      typepre = CHUNK_TYPE_IN_REGION;
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
    else if (fwin && !fwb)
      typepre = CHUNK_TYPE_FIRMWARE;
    else if (fwlefto && !fwb)
      typepre = CHUNK_TYPE_LEFTOVER;
#endif
    else
      typepre = -1;

    if (j != 0 && events[j - 1].pos != events[j].pos)
      {
        grub_addr_t alloc_start, alloc_end;
        alloc_start = max (events[j - 1].pos, target);
        alloc_end = min (events[j].pos, target + size);
        if (alloc_end > alloc_start)
          {
        switch (typepre)
          {
          case CHUNK_TYPE_REGION_START:
            allocate_regstart (alloc_start, alloc_end - alloc_start,
                       events[last_start].reg,
                       events[last_start].regancestor,
                       events[last_start].hancestor);
            /* TODO: maintain a reverse lookup tree for hancestor.  */
            {
              unsigned k;
              for (k = 0; k < N; k++)
            if (events[k].hancestor == events[last_start].head)
              events[k].hancestor = events[last_start].hancestor;
            }
            break;
          case CHUNK_TYPE_IN_REGION:
            allocate_inreg (alloc_start, alloc_end - alloc_start,
                    events[last_start].head,
                    events[last_start].hancestor,
                    events[last_start].reg);
            {
              unsigned k;
              for (k = 0; k < N; k++)
            if (events[k].hancestor == events[last_start].head)
              events[k].hancestor = events[last_start].hancestor;
            }
            break;
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
          case CHUNK_TYPE_FIRMWARE:
            {
              grub_addr_t fstart, fend;
              fstart
            = ALIGN_DOWN (alloc_start,
                      GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
              fend
            = ALIGN_UP (alloc_end,
                    GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
#ifdef DEBUG_RELOCATOR_NOMEM_DPRINTF
              grub_dprintf ("relocator", "requesting %lx-%lx\n",
                    (unsigned long) fstart,
                    (unsigned long) fend);
#endif
              /* The failure here can be very expensive.  */
              if (!grub_relocator_firmware_alloc_region (fstart,
                                 fend - fstart))
            {
              if (from_low_priv)
                start = fend;
              else
                end = fstart;
              goto retry;
            }
              break;
            }
#endif

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
          case CHUNK_TYPE_LEFTOVER:
            {
              unsigned offstart = alloc_start
            % GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
              unsigned offend = alloc_end
            % GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
              struct grub_relocator_fw_leftover *lo
            = events[last_lo].leftover;
              lo->freebytes[offstart / 8]
            &= ((1 << (8 - (start % 8))) - 1);
              grub_memset (lo->freebytes + (offstart + 7) / 8, 0,
                   offend / 8 - (offstart + 7) / 8);
              lo->freebytes[offend / 8] &= ~((1 << (offend % 8)) - 1);
            }
            break;
#endif
          }
        nallocs++;
          }
      }

    switch (events[j].type)
      {
      case REG_BEG_START:
      case IN_REG_START:
        if (events[j].type == REG_BEG_START &&
        (grub_addr_t) (events[j].reg + 1) > target)
          regbeg++;
        else
          inreg++;
        last_start = j;
        break;

      case REG_BEG_END:
      case IN_REG_END:
        if (regbeg)
          regbeg--;
        else
          inreg--;
        break;

#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
      case REG_FIRMWARE_START:
        fwin++;
        break;

      case REG_FIRMWARE_END:
        fwin--;
        break;

      case FIRMWARE_BLOCK_START:
        fwb++;
        break;

      case FIRMWARE_BLOCK_END:
        fwb--;
        break;
#endif

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
      case REG_LEFTOVER_START:
        fwlefto++;
        last_lo = j;
        break;

      case REG_LEFTOVER_END:
        fwlefto--;
        break;
#endif
      case COLLISION_START:
        ncol++;
        break;
      case COLLISION_END:
        ncol--;
        break;
      }

      }
  }

  /* Malloc is available again.  */
  grub_mm_base = base_saved;

  {
    int last_start = 0;
    int inreg = 0, regbeg = 0, ncol = 0;
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
    int fwin = 0, fwlefto = 0, fwb = 0;
#endif
    unsigned cural = 0;
    int oom = 0;
    res->subchunks = grub_malloc (sizeof (res->subchunks[0]) * nallocs);
    if (!res->subchunks)
      oom = 1;
    res->nsubchunks = nallocs;

    for (j = 0; j < N; j++)
      {
    int typepre;
    if (ncol)
      typepre = -1;
    else if (regbeg)
      typepre = CHUNK_TYPE_REGION_START;
    else if (inreg)
      typepre = CHUNK_TYPE_IN_REGION;
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
    else if (fwin && !fwb)
      typepre = CHUNK_TYPE_FIRMWARE;
    else if (fwlefto && !fwb)
      typepre = CHUNK_TYPE_LEFTOVER;
#endif
    else
      typepre = -1;

    if (j != 0 && events[j - 1].pos != events[j].pos)
      {
        grub_addr_t alloc_start, alloc_end;
        struct grub_relocator_subchunk tofree;
        struct grub_relocator_subchunk *curschu = &tofree;
        if (!oom)
          curschu = &res->subchunks[cural];
        alloc_start = max (events[j - 1].pos, target);
        alloc_end = min (events[j].pos, target + size);
        if (alloc_end > alloc_start)
          {
        grub_dprintf ("relocator", "subchunk 0x%lx-0x%lx, %d\n",
                  (unsigned long) alloc_start,
                  (unsigned long) alloc_end, typepre);
        curschu->type = typepre;
        curschu->start = alloc_start;
        curschu->size = alloc_end - alloc_start;
        if (typepre == CHUNK_TYPE_REGION_START
            || typepre == CHUNK_TYPE_IN_REGION)
          {
            curschu->reg = events[last_start].reg;
            curschu->pre_size = alloc_start - events[j - 1].pos;
          }
        if (!oom && (typepre == CHUNK_TYPE_REGION_START
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
                 || typepre == CHUNK_TYPE_FIRMWARE
#endif
                 ))
          {
            struct grub_relocator_extra_block *ne;
            ne = grub_malloc (sizeof (*ne));
            if (!ne)
              {
            oom = 1;
            grub_memcpy (&tofree, curschu, sizeof (tofree));
              }
            else
              {
            ne->start = alloc_start;
            ne->end = alloc_end;
            ne->next = extra_blocks;
            ne->prev = &extra_blocks;
            if (extra_blocks)
              extra_blocks->prev = &(ne->next);
            extra_blocks = ne;
            curschu->extra = ne;
              }
          }

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
        if (!oom && typepre == CHUNK_TYPE_FIRMWARE)
          {
            grub_addr_t fstart, fend;

            fstart
              = ALIGN_DOWN (alloc_start,
                    GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
            fend
              = ALIGN_UP (alloc_end,
                  GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);

            {
              struct grub_relocator_fw_leftover *lo1 = NULL;
              struct grub_relocator_fw_leftover *lo2 = NULL;
              if (fstart != alloc_start)
            lo1 = grub_malloc (sizeof (*lo1));
              if (fend != alloc_end)
            lo2 = grub_malloc (sizeof (*lo2));
              if ((!lo1 && fstart != alloc_start)
              || (!lo2 && fend != alloc_end))
            {
              struct grub_relocator_extra_block *ne;
              grub_free (lo1);
              grub_free (lo2);
              lo1 = NULL;
              lo2 = NULL;
              oom = 1;
              grub_memcpy (&tofree, curschu, sizeof (tofree));
              ne = extra_blocks;
              extra_blocks = extra_blocks->next;
              grub_free (ne);
            }
              if (lo1)
            {
              lo1->quantstart = fstart;
              grub_memset (lo1->freebytes, 0xff,
                       (alloc_start - fstart) / 8);
              lo1->freebytes[(alloc_start - fstart) / 8]
                = (1 << ((alloc_start - fstart) % 8)) - 1;
              grub_memset (lo1->freebytes
                       + ((alloc_start - fstart) / 8) + 1, 0,
                       sizeof (lo1->freebytes)
                       - (alloc_start - fstart) / 8 - 1);
              lo1->next = leftovers;
              lo1->prev = &leftovers;
              if (leftovers)
                leftovers->prev = &lo1->next;
              leftovers = lo1;
            }
              if (lo2)
            {
              lo2->quantstart
                = fend - GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
              grub_memset (lo2->freebytes, 0,
                       (alloc_end - lo2->quantstart) / 8);
              lo2->freebytes[(alloc_end - lo2->quantstart) / 8]
                = ~((1 << ((alloc_end - lo2->quantstart) % 8)) - 1);
              grub_memset (lo2->freebytes
                       + ((alloc_end - lo2->quantstart) / 8)
                       + 1, 0, sizeof (lo2->freebytes)
                       - (alloc_end - lo2->quantstart) / 8 - 1);
              lo2->prev = &leftovers;
              if (leftovers)
                leftovers->prev = &lo2->next;
              lo2->next = leftovers;
              leftovers = lo2;
            }
              curschu->pre = lo1;
              curschu->post = lo2;
            }
          }

        if (typepre == CHUNK_TYPE_LEFTOVER)
          {
            curschu->pre = events[last_start].leftover;
            curschu->post = events[last_start].leftover;
          }
#endif

        if (!oom)
          cural++;
        else
          free_subchunk (&tofree);
          }
      }

    switch (events[j].type)
      {
      case REG_BEG_START:
      case IN_REG_START:
        if (events[j].type == REG_BEG_START &&
        (grub_addr_t) (events[j].reg + 1) > target)
          regbeg++;
        else
          inreg++;
        last_start = j;
        break;

      case REG_BEG_END:
      case IN_REG_END:
        inreg = regbeg = 0;
        break;

#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
      case REG_FIRMWARE_START:
        fwin++;
        break;

      case REG_FIRMWARE_END:
        fwin--;
        break;

      case FIRMWARE_BLOCK_START:
        fwb++;
        break;

      case FIRMWARE_BLOCK_END:
        fwb--;
        break;
#endif

#if GRUB_RELOCATOR_HAVE_LEFTOVERS
      case REG_LEFTOVER_START:
        fwlefto++;
        break;

      case REG_LEFTOVER_END:
        fwlefto--;
        break;
#endif
      case COLLISION_START:
        ncol++;
        break;
      case COLLISION_END:
        ncol--;
        break;
      }
      }
    if (oom)
      {
    unsigned i;
    for (i = 0; i < cural; i++)
      free_subchunk (&res->subchunks[i]);
    grub_free (res->subchunks);
    grub_dprintf ("relocator", "allocation failed with out-of-memory\n");
    return 0;
      }
  }

  res->src = target;
  res->size = size;
  grub_dprintf ("relocator", "allocated: 0x%lx+0x%lx\n", (unsigned long) target,
        (unsigned long) size);

  return 1;
}

static void
adjust_limits (struct grub_relocator *rel,
           grub_phys_addr_t *min_addr, grub_phys_addr_t *max_addr,
           grub_phys_addr_t in_min, grub_phys_addr_t in_max)
{
  struct grub_relocator_chunk *chunk;

  *min_addr = 0;
  *max_addr = rel->postchunks;

  /* Keep chunks in memory in the same order as they'll be after relocation.  */
  for (chunk = rel->chunks; chunk; chunk = chunk->next)
    {
      if (chunk->target > in_max && chunk->src < *max_addr
      && chunk->src < rel->postchunks)
    *max_addr = chunk->src;
      if (chunk->target + chunk->size <= in_min
      && chunk->src + chunk->size > *min_addr
      && chunk->src < rel->postchunks)
    *min_addr = chunk->src + chunk->size;
    }
}

grub_err_t
grub_relocator_alloc_chunk_addr (struct grub_relocator *rel,
                 grub_relocator_chunk_t *out,
                 grub_phys_addr_t target, grub_size_t size)
{
  struct grub_relocator_chunk *chunk;
  grub_phys_addr_t min_addr = 0, max_addr;

  if (target > ~size)
    return grub_error (GRUB_ERR_OUT_OF_RANGE, "address is out of range");

  adjust_limits (rel, &min_addr, &max_addr, target, target);

  for (chunk = rel->chunks; chunk; chunk = chunk->next)
    if ((chunk->target <= target && target < chunk->target + chunk->size)
    || (target <= chunk->target && chunk->target < target + size))
      return grub_error (GRUB_ERR_BAD_ARGUMENT, "overlap detected");

  chunk = grub_malloc (sizeof (struct grub_relocator_chunk));
  if (!chunk)
    return grub_errno;

  grub_dprintf ("relocator",
        "min_addr = 0x%llx, max_addr = 0x%llx, target = 0x%llx\n",
        (unsigned long long) min_addr, (unsigned long long) max_addr,
        (unsigned long long) target);

  do
    {
      /* A trick to improve Linux allocation.  */
#if defined (__i386__) || defined (__x86_64__)
      if (target < 0x100000)
    if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
                 size, chunk, 0, 1))
      {
        if (rel->postchunks > chunk->src)
          rel->postchunks = chunk->src;
        break;
      }
#endif
      if (malloc_in_range (rel, target, max_addr, 1, size, chunk, 1, 0))
    break;

      if (malloc_in_range (rel, min_addr, target, 1, size, chunk, 0, 0))
    break;

      if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
               size, chunk, 0, 1))
    {
      if (rel->postchunks > chunk->src)
        rel->postchunks = chunk->src;
      break;
    }

      grub_dprintf ("relocator", "not allocated\n");
      grub_free (chunk);
      return grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
    }
  while (0);

  grub_dprintf ("relocator", "allocated 0x%llx/0x%llx\n",
        (unsigned long long) chunk->src, (unsigned long long) target);

  if (rel->highestaddr < target + size)
    rel->highestaddr = target + size;

  if (rel->highestaddr < chunk->src + size)
    rel->highestaddr = chunk->src + size;

  if (chunk->src < rel->postchunks)
    {
      if (rel->highestnonpostaddr < target + size)
    rel->highestnonpostaddr = target + size;

      if (rel->highestnonpostaddr < chunk->src + size)
    rel->highestnonpostaddr = chunk->src + size;
    }

  grub_dprintf ("relocator", "relocators_size=%ld\n",
        (unsigned long) rel->relocators_size);

  if (chunk->src < target)
    rel->relocators_size += grub_relocator_backward_size;
  if (chunk->src > target)
    rel->relocators_size += grub_relocator_forward_size;

  grub_dprintf ("relocator", "relocators_size=%ld\n",
        (unsigned long) rel->relocators_size);

  chunk->target = target;
  chunk->size = size;
  chunk->next = rel->chunks;
  rel->chunks = chunk;
  grub_dprintf ("relocator", "cur = %p, next = %p\n", rel->chunks,
        rel->chunks->next);

  chunk->srcv = grub_map_memory (chunk->src, chunk->size);
  *out = chunk;
#ifdef DEBUG_RELOCATOR
  grub_memset (chunk->srcv, 0xfa, chunk->size);
  grub_mm_check ();
#endif
  return GRUB_ERR_NONE;
}

grub_err_t
grub_relocator_alloc_chunk_align (struct grub_relocator *rel,
                  grub_relocator_chunk_t *out,
                  grub_phys_addr_t min_addr,
                  grub_phys_addr_t max_addr,
                  grub_size_t size, grub_size_t align,
                  int preference)
{
  grub_addr_t min_addr2 = 0, max_addr2;
  struct grub_relocator_chunk *chunk;

  if (max_addr > ~size)
    max_addr = ~size;

  if (min_addr < 0x1000)
    min_addr = 0x1000;

  grub_dprintf ("relocator", "chunks = %p\n", rel->chunks);

  chunk = grub_malloc (sizeof (struct grub_relocator_chunk));
  if (!chunk)
    return grub_errno;

  if (malloc_in_range (rel, min_addr, max_addr, align,
               size, chunk,
               preference != GRUB_RELOCATOR_PREFERENCE_HIGH, 1))
    {
      grub_dprintf ("relocator", "allocated 0x%llx/0x%llx\n",
            (unsigned long long) chunk->src,
            (unsigned long long) chunk->src);
      grub_dprintf ("relocator", "chunks = %p\n", rel->chunks);
      chunk->target = chunk->src;
      chunk->size = size;
      chunk->next = rel->chunks;
      rel->chunks = chunk;
      chunk->srcv = grub_map_memory (chunk->src, chunk->size);
      *out = chunk;
      return GRUB_ERR_NONE;
    }

  adjust_limits (rel, &min_addr2, &max_addr2, min_addr, max_addr);
  grub_dprintf ("relocator", "Adjusted limits from %lx-%lx to %lx-%lx\n",
        (unsigned long) min_addr, (unsigned long) max_addr,
        (unsigned long) min_addr2, (unsigned long) max_addr2);

  do
    {
      if (malloc_in_range (rel, min_addr2, max_addr2, align,
               size, chunk, 1, 1))
    break;

      if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
               size, chunk, 0, 1))
    {
      if (rel->postchunks > chunk->src)
        rel->postchunks = chunk->src;
      break;
    }

      return grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
    }
  while (0);

  {
    int found = 0;
    auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t,
                    grub_memory_type_t);
    int NESTED_FUNC_ATTR hook (grub_uint64_t addr, grub_uint64_t sz,
                   grub_memory_type_t type)
    {
      grub_uint64_t candidate;
      if (type != GRUB_MEMORY_AVAILABLE)
    return 0;
      candidate = ALIGN_UP (addr, align);
      if (candidate < min_addr)
    candidate = ALIGN_UP (min_addr, align);
      if (candidate + size > addr + sz
      || candidate > ALIGN_DOWN (max_addr, align))
    return 0;
      if (preference == GRUB_RELOCATOR_PREFERENCE_HIGH)
    candidate = ALIGN_DOWN (min (addr + sz - size, max_addr), align);
      if (!found || (preference == GRUB_RELOCATOR_PREFERENCE_HIGH
             && candidate > chunk->target))
    chunk->target = candidate;
      if (!found || (preference == GRUB_RELOCATOR_PREFERENCE_LOW
             && candidate < chunk->target))
    chunk->target = candidate;
      found = 1;
      return 0;
    }

    grub_machine_mmap_iterate (hook);
    if (!found)
      return grub_error (GRUB_ERR_BAD_OS, "couldn't find suitable memory target");
  }
  while (1)
    {
      struct grub_relocator_chunk *chunk2;
      for (chunk2 = rel->chunks; chunk2; chunk2 = chunk2->next)
    if ((chunk2->target <= chunk->target
         && chunk->target < chunk2->target + chunk2->size)
        || (chunk2->target <= chunk->target + size
        && chunk->target + size < chunk2->target + chunk2->size)
        || (chunk->target <= chunk2->target && chunk2->target
        < chunk->target + size)
        || (chunk->target <= chunk2->target + chunk2->size
        && chunk2->target + chunk2->size < chunk->target + size))
      {
        if (preference == GRUB_RELOCATOR_PREFERENCE_HIGH)
          chunk->target = ALIGN_DOWN (chunk2->target, align);
        else
          chunk->target = ALIGN_UP (chunk2->target + chunk2->size, align);
        break;
      }
      if (!chunk2)
    break;
    }

  grub_dprintf ("relocator", "relocators_size=%ld\n",
        (unsigned long) rel->relocators_size);

  if (chunk->src < chunk->target)
    rel->relocators_size += grub_relocator_backward_size;
  if (chunk->src > chunk->target)
    rel->relocators_size += grub_relocator_forward_size;

  grub_dprintf ("relocator", "relocators_size=%ld\n",
        (unsigned long) rel->relocators_size);

  chunk->size = size;
  chunk->next = rel->chunks;
  rel->chunks = chunk;
  grub_dprintf ("relocator", "cur = %p, next = %p\n", rel->chunks,
        rel->chunks->next);
  chunk->srcv = grub_map_memory (chunk->src, chunk->size);
  *out = chunk;
#ifdef DEBUG_RELOCATOR
  grub_memset (chunk->srcv, 0xfa, chunk->size);
  grub_mm_check ();
#endif
  return GRUB_ERR_NONE;
}

void
grub_relocator_unload (struct grub_relocator *rel)
{
  struct grub_relocator_chunk *chunk, *next;
  if (!rel)
    return;
  for (chunk = rel->chunks; chunk; chunk = next)
    {
      unsigned i;
      for (i = 0; i < chunk->nsubchunks; i++)
    free_subchunk (&chunk->subchunks[i]);
      grub_unmap_memory (chunk->srcv, chunk->size);
      next = chunk->next;
      grub_free (chunk->subchunks);
      grub_free (chunk);
    }
  grub_free (rel);
}

grub_err_t
grub_relocator_prepare_relocs (struct grub_relocator *rel, grub_addr_t addr,
                   void **relstart, grub_size_t *relsize)
{
  grub_uint8_t *rels;
  grub_uint8_t *rels0;
  struct grub_relocator_chunk *sorted;
  grub_size_t nchunks = 0;
  unsigned j;
  struct grub_relocator_chunk movers_chunk;

  grub_dprintf ("relocator", "Preparing relocs (size=%ld)\n",
        (unsigned long) rel->relocators_size);

  if (!malloc_in_range (rel, 0, ~(grub_addr_t)0 - rel->relocators_size + 1,
            grub_relocator_align,
            rel->relocators_size, &movers_chunk, 1, 1))
    return grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
  movers_chunk.srcv = rels = rels0
    = grub_map_memory (movers_chunk.src, movers_chunk.size);

  if (relsize)
    *relsize = rel->relocators_size;

  grub_dprintf ("relocator", "Relocs allocated at %p\n", movers_chunk.srcv);

  {
    unsigned i;
    grub_size_t count[257];
    struct grub_relocator_chunk *from, *to, *tmp;

    grub_memset (count, 0, sizeof (count));

    {
        struct grub_relocator_chunk *chunk;
    for (chunk = rel->chunks; chunk; chunk = chunk->next)
      {
        grub_dprintf ("relocator", "chunk %p->%p, 0x%lx\n",
              (void *) chunk->src, (void *) chunk->target,
              (unsigned long) chunk->size);
        nchunks++;
        count[(chunk->src & 0xff) + 1]++;
      }
    }
    from = grub_malloc (nchunks * sizeof (sorted[0]));
    to = grub_malloc (nchunks * sizeof (sorted[0]));
    if (!from || !to)
      {
    grub_free (from);
    grub_free (to);
    return grub_errno;
      }

    for (j = 0; j < 256; j++)
      count[j+1] += count[j];

    {
      struct grub_relocator_chunk *chunk;
      for (chunk = rel->chunks; chunk; chunk = chunk->next)
    from[count[chunk->src & 0xff]++] = *chunk;
    }

    for (i = 1; i < GRUB_CPU_SIZEOF_VOID_P; i++)
      {
    grub_memset (count, 0, sizeof (count));
    for (j = 0; j < nchunks; j++)
      count[((from[j].src >> (8 * i)) & 0xff) + 1]++;
    for (j = 0; j < 256; j++)
      count[j+1] += count[j];
    for (j = 0; j < nchunks; j++)
      to[count[(from[j].src >> (8 * i)) & 0xff]++] = from[j];
    tmp = to;
    to = from;
    from = tmp;
      }
    sorted = from;
    grub_free (to);
  }

  for (j = 0; j < nchunks; j++)
    {
      grub_dprintf ("relocator", "sorted chunk %p->%p, 0x%lx\n",
            (void *) sorted[j].src, (void *) sorted[j].target,
            (unsigned long) sorted[j].size);
      if (sorted[j].src < sorted[j].target)
    {
      grub_cpu_relocator_backward ((void *) rels,
                       sorted[j].srcv,
                       grub_map_memory (sorted[j].target,
                            sorted[j].size),
                       sorted[j].size);
      rels += grub_relocator_backward_size;
    }
      if (sorted[j].src > sorted[j].target)
    {
      grub_cpu_relocator_forward ((void *) rels,
                      sorted[j].srcv,
                      grub_map_memory (sorted[j].target,
                               sorted[j].size),
                      sorted[j].size);
      rels += grub_relocator_forward_size;
    }
      if (sorted[j].src == sorted[j].target)
    grub_arch_sync_caches (sorted[j].srcv, sorted[j].size);
    }
  grub_cpu_relocator_jumper ((void *) rels, (grub_addr_t) addr);
  *relstart = rels0;
  grub_free (sorted);
  return GRUB_ERR_NONE;
}

void
grub_mm_check_real (char *file, int line)
{
  grub_mm_region_t r;
  grub_mm_header_t p, pa;

  for (r = grub_mm_base; r; r = r->next)
    {
      pa = r->first;
      p = pa->next;
      if (p->magic == GRUB_MM_ALLOC_MAGIC)
    continue;
      do
    {
      if ((grub_addr_t) p < (grub_addr_t) (r + 1)
          || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
        grub_fatal ("%s:%d: out of range pointer: %p\n", file, line, p);
      if (p->magic != GRUB_MM_FREE_MAGIC)
        grub_fatal ("%s:%d free magic broken at %p (0x%x)\n", file,
            line, p, p->magic);
      pa = p;
      p = pa->next;
    }
      while (pa != r->first);
    }
}