Re: [PATCH v4 1/2] semihosting/arm-compat: replace heuristic for softmmu SYS_HEAPINFO

[Peter Maydell]

On Wed, 23 Jun 2021 at 14:47, Alex Bennée <alex.bennee@linaro.org> wrote:
>
> The previous numbers were a guess at best and rather arbitrary without
> taking into account anything that might be loaded. Instead of using
> guesses based on the state of registers implement a new function that:
>
>  a) scans the MemoryRegions for the largest RAM block
>  b) iterates through all "ROM" blobs looking for the biggest gap
>
> The "ROM" blobs include all code loaded via -kernel and the various
> -device loader techniques.
>
> Signed-off-by: Alex Bennée <alex.bennee@linaro.org>
> Cc: Andrew Strauss <astrauss11@gmail.com>
> Cc: Keith Packard <keithp@keithp.com>
> Message-Id: <20210601090715.22330-1-alex.bennee@linaro.org>

> @@ -349,4 +349,20 @@ int rom_add_option(const char *file, int32_t bootindex);
>   * overflow on real hardware too. */
>  #define UBOOT_MAX_GUNZIP_BYTES (64 << 20)
>
> +/**
> + * rom_find_largest_gap_between: return highest address of ROM in region
> + *
> + * This function is used to find the highest ROM address (or loaded
> + * blob) so we can advise where true heap memory may be.

This doc comment doesn't match the function name or implementation.
You probably want something like:

rom_find_largest_gap_between: return largest gap between ROMs in given range

Given a range of addresses, this function finds the largest
contiguous subrange which has no ROMs loaded to it. That is,
it finds the biggest gap which is free for use for other things.

> + *
> + * Returns: RomGap, describing the largest section not intersected by
> + * a ROM region.
> + */
> +typedef struct RomGap {
> +    hwaddr base;
> +    size_t size;
> +} RomGap;

I suspect if we ever run the doc-generator on this header it
would get confused by the doc comment not coming immediately
before the function prototype it is documenting.

> +RomGap rom_find_largest_gap_between(hwaddr base, size_t size);
> +
>  #endif
> diff --git a/hw/core/loader.c b/hw/core/loader.c
> index 5b34869a54..d4893fa8d8 100644
> --- a/hw/core/loader.c
> +++ b/hw/core/loader.c
> @@ -1310,6 +1310,80 @@ static Rom *find_rom(hwaddr addr, size_t size)
>      return NULL;
>  }
>
> +typedef struct RomSec {
> +    hwaddr base;
> +    int se; /* start/end flag */
> +} RomSec;
> +
> +
> +static gint sort_secs(gconstpointer a, gconstpointer b)
> +{
> +    RomSec *ra = (RomSec *) a;
> +    RomSec *rb = (RomSec *) b;

/*
 * Sort into address order. We break ties between rom-startpoints
 * and rom-endpoints in favour of the startpoint, by sorting the 0->1
 * transition before the 1->0 transition. Either way round would
 * work, but this way saves a little work later by avoiding
 * dealing with "gaps" of 0 length.
 */

> +
> +    if (ra->base == rb->base) {
> +        return ra->se > rb->se ? -1 : 1;
> +    }
> +    return ra->base > rb->base ? 1 : -1;

This has forgotten the "equality" case, which you will
see if two blobs start at the same address (at least in
theory; at the moment the rom blob loader will try to
reject overlaps, though it might not do so forever).

> +}
> +
> +RomGap rom_find_largest_gap_between(hwaddr base, size_t size)
> +{
> +    Rom *rom;
> +    RomSec *cand;
> +    RomGap res = {0, 0};
> +    hwaddr gapstart = base;
> +    GList *it, *secs = NULL;
> +    int count = 0;
> +
> +    QTAILQ_FOREACH(rom, &roms, next) {
> +        /* ignore real rom blobs */

They're all real rom blobs (arguably a fw_file blob is less real!). Maybe
  /* Ignore blobs being loaded to special places */
?

> +        if (rom->mr || rom->fw_file) {
> +            continue;
> +        }
> +        /* ignore anything finishing bellow base */

"below"

> +        if (rom->addr + rom->romsize < base) {

  <=
(we can ignore a rom that's 0x1000, size 0x1000 if our range starts at 0x2000,
because it covers [0x1000..0x1fff])

> +            continue;
> +        }
> +        /* ignore anything starting above the region */
> +        if (rom->addr > base + size) {

 >=
(if our region is 0x1000, size 0x1000, we can ignore a rom starting at 0x2000)

> +            continue;
> +        }
> +
> +        /* Save the start and end of each relevant ROM */
> +        cand = g_new(RomSec, 1);
> +        cand->base = rom->addr;

  cand->base = MAX(rom->addr, base);

(otherwise you can get exciting special cases like
"cand->base - gapstart" being negative in the loop below)

> +        cand->se = 1;
> +        secs = g_list_append(secs, cand);

The glib docs
https://developer.gnome.org/glib/stable/glib-Doubly-Linked-Lists.html#g-list-append
say that g_list_append() has to traverse the entire list to find the
tail in order to append the new item, making this algorithm
accidentally-quadratic. Since we're about to sort the list, we don't
care about its order now and can use g_list_prepend() instead.

> +
> +        if (rom->addr + rom->romsize < base + size) {
> +            cand = g_new(RomSec, 1);
> +            cand->base = rom->addr + rom->romsize;
> +            cand->se = -1;
> +            secs = g_list_append(secs, cand);
> +        }
> +    }

We need to append a sentinel to the list to avoid having
to special case for "the big gap goes all the way to the end
of the range":
     cand = g_new(RomSec, 1);
     cand->base = base + size;
     cand->se = 1;
     secs = g_list_prepend(secs, cand);

(Maybe a helper function so you can write
   add_romsec_to_list(secs, base, se);
rather than having variants on these four lines in three places?)

> +
> +    secs = g_list_sort(secs, sort_secs);
> +

I would favour initializing gapstart here, just because this
tail end of the function is the only place where it's used, and
it makes the algorithm a bit easier to understand if you don't
have to look 30 lines back up the function to see what its
initial value is.

> +    for (it = g_list_first(secs); it; it = g_list_next(it)) {
> +        cand = (RomSec *) it->data;
> +        if (count == 0 && count + cand->se == 1) {
> +            size_t gap = cand->base - gapstart;
> +            if (gap > res.size) {
> +                res.base = gapstart;
> +                res.size = gap;
> +            }
> +        } else if (count == 1 && count + cand->se == 0) {
> +            gapstart = cand->base;
> +        }
> +        count += cand->se;
> +    }
> +
> +    g_list_free_full(secs, g_free);
> +    return res;
> +}

> +static LayoutInfo common_semi_find_bases(CPUState *cs)
>  {
> -    MemoryRegion *subregion;
> +    FlatView *fv;
> +    LayoutInfo info = { 0, 0, 0, 0 };
> +
> +    RCU_READ_LOCK_GUARD();
> +
> +    fv = address_space_to_flatview(cs->as);
> +    flatview_for_each_range(fv, find_ram_cb, &info);
>
>      /*
> -     * Find the chunk of R/W memory containing the address.  This is
> -     * used for the SYS_HEAPINFO semihosting call, which should
> -     * probably be using information from the loaded application.
> +     * If we have found the RAM lets iterate through the ROM blobs to
> +     * workout the best place for the remainder of RAM and split it
> +     * equally between stack and heap.
>       */
> -    QTAILQ_FOREACH(subregion, &get_system_memory()->subregions,
> -                   subregions_link) {
> -        if (subregion->ram && !subregion->readonly) {
> -            Int128 top128 = int128_add(int128_make64(subregion->addr),
> -                                       subregion->size);
> -            Int128 addr128 = int128_make64(addr);
> -            if (subregion->addr <= addr && int128_lt(addr128, top128)) {
> -                return subregion->addr;
> -            }
> -        }
> +    if (info.rambase && info.ramsize) {
> +        RomGap gap = rom_find_largest_gap_between(info.rambase, 
> info.ramsize);
> +        info.heapbase = gap.base;
> +        info.heaplimit = gap.base + gap.size;
>      }

You don't want to ignore info.rambase == 0 -- it could well be that
the RAM in the system starts at address zero. It's only size of 0
that would indicate we failed entirely to find any RAM.

thanks
-- PMM