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

[Samuel Thibault <samuel.thibault@xxxxxxxxxxxx>]

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 :)

Samuel