| Message ID | 20210623134756.30930-2-alex.bennee@linaro.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | semihosting/next (SYS_HEAPINFO) | expand |
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
Peter Maydell <peter.maydell@linaro.org> writes: > 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) >> <snip> >> +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). I'm confused what you mean by equality case. If both RomSecs have the same base and the same se flag we need to pick one of them. Are you saying when ra->se == ra->sb we should take ra?
On Wed, 9 Feb 2022 at 16:31, Alex Bennée <alex.bennee@linaro.org> wrote: > > > Peter Maydell <peter.maydell@linaro.org> writes: > > > On Wed, 23 Jun 2021 at 14:47, Alex Bennée <alex.bennee@linaro.org> wrote: > >> +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). > > I'm confused what you mean by equality case. If both RomSecs have the > same base and the same se flag we need to pick one of them. Are you > saying when ra->se == ra->sb we should take ra? I'm saying that a sort comparison should give a consistent answer. At the moment if you pass it two items A and B which happen to have the same base and se values, then if you call sort_secs(A, B) it will claim "B is greater than A", but if you call sort_secs(B, A) it will claim "A is greater than B". The GCompareFunc API provides a way to say "these are the same" -- return 0. -- PMM
diff --git a/include/hw/loader.h b/include/hw/loader.h index cbfc184873..f2cdb82b59 100644 --- a/include/hw/loader.h +++ b/include/hw/loader.h @@ -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. + * + * Returns: RomGap, describing the largest section not intersected by + * a ROM region. + */ +typedef struct RomGap { + hwaddr base; + size_t size; +} RomGap; + +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; + + if (ra->base == rb->base) { + return ra->se > rb->se ? -1 : 1; + } + return ra->base > rb->base ? 1 : -1; +} + +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 */ + if (rom->mr || rom->fw_file) { + continue; + } + /* ignore anything finishing bellow base */ + if (rom->addr + rom->romsize < base) { + continue; + } + /* ignore anything starting above the region */ + if (rom->addr > base + size) { + continue; + } + + /* Save the start and end of each relevant ROM */ + cand = g_new(RomSec, 1); + cand->base = rom->addr; + cand->se = 1; + secs = g_list_append(secs, cand); + + 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); + } + } + + secs = g_list_sort(secs, sort_secs); + + 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; +} + /* * Copies memory from registered ROMs to dest. Any memory that is contained in * a ROM between addr and addr + size is copied. Note that this can involve diff --git a/semihosting/arm-compat-semi.c b/semihosting/arm-compat-semi.c index 1c29146dcf..f50c1474bc 100644 --- a/semihosting/arm-compat-semi.c +++ b/semihosting/arm-compat-semi.c @@ -44,6 +44,7 @@ #else #include "exec/gdbstub.h" #include "qemu/cutils.h" +#include "hw/loader.h" #ifdef TARGET_ARM #include "hw/arm/boot.h" #endif @@ -144,33 +145,69 @@ typedef struct GuestFD { static GArray *guestfd_array; #ifndef CONFIG_USER_ONLY -#include "exec/address-spaces.h" -/* - * Find the base of a RAM region containing the specified address + +/** + * common_semi_find_bases: find information about ram and heap base + * + * This function attempts to provide meaningful numbers for RAM and + * HEAP base addresses. The rambase is simply the lowest addressable + * RAM position. For the heapbase we ask the loader to scan the + * address space and the largest available gap by querying the "ROM" + * regions. + * + * Returns: a structure with the numbers we need. */ -static inline hwaddr -common_semi_find_region_base(hwaddr addr) + +typedef struct LayoutInfo { + target_ulong rambase; + size_t ramsize; + hwaddr heapbase; + hwaddr heaplimit; +} LayoutInfo; + +static bool find_ram_cb(Int128 start, Int128 len, const MemoryRegion *mr, + hwaddr offset_in_region, void *opaque) +{ + LayoutInfo *info = (LayoutInfo *) opaque; + uint64_t size = int128_get64(len); + + if (!mr->ram || mr->readonly) { + return false; + } + + if (size > info->ramsize) { + info->rambase = int128_get64(start); + info->ramsize = size; + } + + /* search exhaustively for largest RAM */ + return false; +} + +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; } - return 0; + + return info; } + #endif #ifdef TARGET_ARM @@ -204,28 +241,6 @@ common_semi_sys_exit_extended(CPUState *cs, int nr) return (nr == TARGET_SYS_EXIT_EXTENDED || is_a64(cs->env_ptr)); } -#ifndef CONFIG_USER_ONLY -#include "hw/arm/boot.h" -static inline target_ulong -common_semi_rambase(CPUState *cs) -{ - CPUArchState *env = cs->env_ptr; - const struct arm_boot_info *info = env->boot_info; - target_ulong sp; - - if (info) { - return info->loader_start; - } - - if (is_a64(env)) { - sp = env->xregs[31]; - } else { - sp = env->regs[13]; - } - return common_semi_find_region_base(sp); -} -#endif - #endif /* TARGET_ARM */ #ifdef TARGET_RISCV @@ -251,17 +266,6 @@ common_semi_sys_exit_extended(CPUState *cs, int nr) return (nr == TARGET_SYS_EXIT_EXTENDED || sizeof(target_ulong) == 8); } -#ifndef CONFIG_USER_ONLY - -static inline target_ulong -common_semi_rambase(CPUState *cs) -{ - RISCVCPU *cpu = RISCV_CPU(cs); - CPURISCVState *env = &cpu->env; - return common_semi_find_region_base(env->gpr[xSP]); -} -#endif - #endif /* @@ -1165,12 +1169,12 @@ target_ulong do_common_semihosting(CPUState *cs) case TARGET_SYS_HEAPINFO: { target_ulong retvals[4]; - target_ulong limit; int i; #ifdef CONFIG_USER_ONLY TaskState *ts = cs->opaque; + target_ulong limit; #else - target_ulong rambase = common_semi_rambase(cs); + LayoutInfo info = common_semi_find_bases(cs); #endif GET_ARG(0); @@ -1201,12 +1205,15 @@ target_ulong do_common_semihosting(CPUState *cs) retvals[2] = ts->stack_base; retvals[3] = 0; /* Stack limit. */ #else - limit = current_machine->ram_size; - /* TODO: Make this use the limit of the loaded application. */ - retvals[0] = rambase + limit / 2; - retvals[1] = rambase + limit; - retvals[2] = rambase + limit; /* Stack base */ - retvals[3] = rambase; /* Stack limit. */ + /* + * Reporting 0 indicates we couldn't calculate the real + * values which should force most software to fall back to + * using information it has. + */ + retvals[0] = info.heapbase; /* Heap Base */ + retvals[1] = info.heaplimit; /* Heap Limit */ + retvals[2] = info.heaplimit; /* Stack base */ + retvals[3] = info.heapbase; /* Stack limit. */ #endif for (i = 0; i < ARRAY_SIZE(retvals); i++) {
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> --- v2 - report some known information (limits) - reword the commit message v3 - rework to use the ROM blob scanning suggested by Peter - drop arch specific wrappers - dropped rb/tb tags as it's a rework v4 - search for the largest RAM which should be the main RAM - implement the biggest gap algorithm - make stackbase the inverse of heap info --- include/hw/loader.h | 16 +++++ hw/core/loader.c | 74 +++++++++++++++++++ semihosting/arm-compat-semi.c | 129 ++++++++++++++++++---------------- 3 files changed, 158 insertions(+), 61 deletions(-)