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

[Juergen Gross <jgross@xxxxxxxx>]

On 12.12.21 01:05, Samuel Thibault wrote:
> 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).
I think you are partially right. :-)

Entries for resources managed by Mini-OS (RAM, maybe NVME?) should be
rounded to cover only complete pages (start rounded up, end rounded
down), but all other entries should be rounded to cover the complete
area (start rounded down, end rounded up) in order not to use any
partial used page for e.g. mapping foreign pages.

> > +    /* 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);
>              }
>          }
>      }
Hmm, depends.

Assuming a rather well sorted map my version is O(n), while yours
is still O(n^2).

In the end it won't matter that much, because a normal map will have
only very few entries (usually 5 before merging consecutive entries).

I'm fine both ways, whatever you prefer.


Juergen

Attachment: OpenPGP_0xB0DE9DD628BF132F.asc
Description: OpenPGP public key

Attachment: OpenPGP_signature
Description: OpenPGP digital signature