FWIW, online_movable works in any order on memory blocks from memory0 to memory31. From memory32 up, the reported problem is exhibited.

Issue is not virt specific, baremetal also should be affected, to reproduce
one need physically hotplug a memory module. (i.e. prereq to trigger issue
is that memory module is not present at boot time).

Here is what happens:

  echo online_movable > memoryXX/online

triggers following code path:

memory_subsys_online -> memory_block_change_state -> memory_block_action ->
      online_pages():
        if (online_type == MMOP_ONLINE_MOVABLE &&
            zone_idx(zone) == ZONE_MOVABLE - 1) {
                if (move_pfn_range_right(zone, zone + 1, pfn, pfn + nr_pages))
                        return -EINVAL;
        }

where move_pfn_range_right() fails following check:

        /* the move out part mast at the right most of @z1 */
        if (zone_end_pfn(z1) >  end_pfn)
                goto out_fail;

since we are trying to online as movable not the last section in
ZONE_NORMAL.

Here is what makes hotplugged memory end up in ZONE_NORMAL:
 acpi_memory_enable_device() -> add_memory -> add_memory_resource ->
   -> arch/x86/mm/init_64.c  
     :w
/*
      * Memory is added always to NORMAL zone. This means you will never get
      * additional DMA/DMA32 memory.
      */

     int arch_add_memory(int nid, u64 start, u64 size, bool for_device)
     {
        struct pglist_data *pgdat = NODE_DATA(nid);
        struct zone *zone = pgdat->node_zones +
                zone_for_memory(nid, start, size, ZONE_NORMAL, for_device);

i.e. all hot-plugged memory modules always go to ZONE_NORMAL.

Issue here is not in current movable zone design and that it design allows to move only memory section on border between zones.

Issue is that if movable zone doesn't exists in hotplug time, zone_for_memory()
defaults to ZONE_NORMAL. As result all all hotplugged memory sections go to
ZONE_NORMAL except the last one for which valid_zones == "NORMAL MOVABLE". i.e.
it is also in ZONE_NORMAL but could be moved to ZONE_MOVABLE.

Idea I've have had to fix it is to allow caller of add_memory() to specify default zone. That way ACPI hotplug acpi_memory_enable_device() could pick
to which zone hotplugged memory goes in.
Like if corresponding ACPI node is removable /has _EJ0 method/, pass to ad_memory() as default ZONE_MOVABLE, if hotplugged memory is not removable
set default to ZONE_NORMAL. That way removable memory goes by default to
ZONE_MOVABLE and onlining with echo [online|online_movable] > memoryXX/online makes it go to ZONE_MOVABLE by default without failing onlining memory sections.

Since I've been preemted and don't have time to work on this bug in near future, I'll attach WIP patch that does above and fixes this particular issue.
Whoever picks this up post something upstream pls CC me on it so I could help with review.

Created attachment 1146332 [details]
PATCH add removable memory sections to ZONE_MOVABLE by default.

it's just a proof of concept [i.e. on t ready to post upstream as is]