Re: [PATCH 02/10] mini-os: sort and sanitize e820 memory map

[Samuel Thibault <samuel.thibault@xxxxxxxxxxxx>]

Hello,

Juergen Gross, le lun. 06 déc. 2021 08:23:29 +0100, a ecrit:
> - align the entries to page boundaries

> +    /* Adjust map entries to page boundaries. */
> +    for ( i = 0; i < e820_entries; i++ )
> +    {
> +        end = (e820_map[i].addr + e820_map[i].size + PAGE_SIZE - 1) & 
> PAGE_MASK;
> +        e820_map[i].addr &= PAGE_MASK;
> +        e820_map[i].size = end - e820_map[i].addr;
> +    }

Mmm, what if the previous entry ends after the aligned start?

On real machines that does happen, and you'd rather round up the start
address of usable areas, rather than rounding it down (and conversely
for the end).

> +    /* Sort entries by start address. */
> +    for ( i = 0; i < e820_entries - 1; i++ )
> +    {
> +        if ( e820_map[i].addr > e820_map[i + 1].addr )
> +        {
> +            e820_swap_entries(i, i + 1);
> +            i = -1;
> +        }
> +    }

This looks O(n^3) to me? A bubble sort like this should be fine:

    /* Sort entries by start address. */
    for ( last = e820_entries; last > 1; last-- )
    {
        for ( i = 0; i < last - 1; i++ )
        {
            if ( e820_map[i].addr > e820_map[i + 1].addr )
            {
                e820_swap_entries(i, i + 1);
            }
        }
    }

Samuel