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

[Juergen Gross <jgross@xxxxxxxx>]

On 13.12.21 22:19, Samuel Thibault wrote:
> Juergen Gross, le lun. 13 déc. 2021 15:56:21 +0100, a ecrit:
> > 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.
> Right!
>
> > > > +    /* 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).
> Right, I was a bit lazy :)
>
> This should be fine:
>
> /* Sort entries by start address. */
> for ( i = 1; i < e820_entries; i++ )
>      for ( j = i; j > 0 && e820_map[j-1].addr > e820_map[j].addr ) ; j-- )
>          e820_swap_entries(j - 1, j);
>
> > I'm fine both ways, whatever you prefer.
> I really prefer for loops which don't unexpectedly modify their loop
> index, that's much less scary :)
Agreed, I'll take your version.


Juergen

Attachment: OpenPGP_0xB0DE9DD628BF132F.asc
Description: OpenPGP public key

Attachment: OpenPGP_signature
Description: OpenPGP digital signature