Re: [tlug] about sanitize_e820_map()

[Josh Glover <jmglov@example.com>]

On 15/01/06, Stephen J. Turnbull <stephen@example.com> wrote:

> >>>>> "Toshiyuki" == Toshiyuki Ishii <psbfan@example.com> writes:
>
>     Toshiyuki> I am a beginner of kernel source code, so sorry if I am
>     Toshiyuki> misunderstanding.
>
> This isn't exactly a kernel hackers group.  There are a few such here,
> but it's unlikely that they're familiar with every little bit.

I for one would like to see more hardcore C questions on this list, so
I will endeavor to help you out here.

You should, however, take Steve's advise about what info you need to
provide so that we can help you.

I will assume that you are concerned with the 2.6 kernel.

I first made an identifier search on LXR against the 2.6.11 source
tree to find the relevant code:

http://lxr.linux.no/ident?i=sanitize_e820_map

Then I performed a search on Safari[1] for 'e820', which led me to an
excellent section in "Understanding the Linux Kernel (3rd
Edition)"[2]: "A.3. Middle Ages: the setup( ) Function". I promptly
added the book to my Safari bookshelf so that I could read the whole
section (don't worry, I wanted to evaluate this book before buying
it[2] anyway).

A-ha! Now I know that sanitize_e820_map() has something to do with
ACPI, for the BIOS e820 map is a table describing the layout of a
system's physical memory, according to UtLK3e:

"setup( ) performs essentially the following operations:

   1.

      In ACPI -compliant systems, it invokes a BIOS routine that
builds a table in RAM describing the layout of the system's physical
memory (the table can be seen in the boot kernel messages by looking
for the "BIOS-e820" label). In older systems, it invokes a BIOS
routine that just returns the amount of RAM available in the system."

OK, back to the code. arch/i386/kernel/setup.c looks like the logical
place to start, based on the results of my LXR identifier search. It
looks like the section that you are referring to in your email starts
at line 517, right?

http://lxr.linux.no/source/arch/i386/kernel/setup.c#L517

Again, as Steve pointed out, tell us *where*: version of code, source
filename, line! And if there exists online a browseable version of the
code, link to it.

OK, for a little context, the BIOS e820 map (which is a map of
physical memory locations as reported by an ACPI-compliant BIOS) may
contain overlapping entries. The Linux kernel hates this, so it wants
to reconfigure the map as shown by the comment at lines 446-480[3]:

446         /*
447                 Visually we're performing the following (1,2,3,4 =
memory types)...
448
449                 Sample memory map (w/overlaps):
450                    ____22__________________
451                    ______________________4_
452                    ____1111________________
453                    _44_____________________
454                    11111111________________
455                    ____________________33__
456                    ___________44___________
457                    __________33333_________
458                    ______________22________
459                    ___________________2222_
460                    _________111111111______
461                    _____________________11_
462                    _________________4______
463
464                 Sanitized equivalent (no overlap):
465                    1_______________________
466                    _44_____________________
467                    ___1____________________
468                    ____22__________________
469                    ______11________________
470                    _________1______________
471                    __________3_____________
472                    ___________44___________
473                    _____________33_________
474                    _______________2________
475                    ________________1_______
476                    _________________4______
477                    ___________________2____
478                    ____________________33__
479                    ______________________4_
480         */

OK, so the section of code relevant to your question is:

514                 for (i=1; i < chg_nr; i++)  {
515                         /* if <current_addr> > <last_addr>, swap */
516                         /* or, if current=<start_addr> &
last=<end_addr>, swap */
517                         if ((change_point[i]->addr <
change_point[i-1]->addr) ||
518                                 ((change_point[i]->addr ==
change_point[i-1]->addr) &&
519                                  (change_point[i]->addr ==
change_point[i]->pbios->addr) &&
520                                  (change_point[i-1]->addr !=
change_point[i-1]->pbios->addr))
521                            )
522                         {
523                                 change_tmp = change_point[i];
524                                 change_point[i] = change_point[i-1];
525                                 change_point[i-1] = change_tmp;
526                                 still_changing=1;
527                         }
528                 }

We also need to know a little about the structures contained in the
change_point[] array[4]:

426 struct change_member {
427         struct e820entry *pbios; /* pointer to original bios entry */
428         unsigned long long addr; /* address for this change point */
429 };

So the 'addr' field of the struct refers to the address in our new
map, and pbios->addr is the address in the original e820 map.

I read this conditional as follows:

1) Line 517 checks to see if the address at the current index in our
map is less than the address at the previous index in our map. This
would be the most obvious way to detect an overlap. Short circuit,
jump to lines 523-526, where the overlap is repaired.
2a) Line 518 is the beginning of a logical condition with three parts;
the first part being: is the address (new) at the current index of the
map the same as the address (new) at the previous part? If not,
short-circuit, move to the next iteration of the for loop.
2b) Line 519 is the second part of the three-part condition. Is the
address (new) at the current index of the map the same as the address
(*old*; in the original e820 BIOS map) at the *current index*? If not,
short-circuit, move to the next iteration of the for loop.
2c) Line 520 is the third and final part of the condition. Is the
address (new) at the previous index different from the address (old)
at the previous index? If so, repair the overlap in the body of the if
condition.

So, let me try to show this in some sort of visual way. Note that
memory addresses are obviously wrong (I wanted a simple example, not
an accurate one). :)

Case 1 (covered by line 517):

change_point[]
                                    0        1        ...        i-1  
     i        ...        n
addr                                                           0x81    0x80
pbios->addr                                             ???      ???

In this case, we don't care what the addresses in the original e820
map are, since the address at index [i] is lower than the address at
index [i-1] (an obvious overlap).

But what if the addresses are the same? That is why we need case 2
(lines 518-520):

change_point[]
                                    0        1        ...        i-1  
     i        ...        n
addr                                                           0x80   
0x80                  <== (2a)
pbios->addr                                                         
0x80                  <== (2b)

The addresses at [i] and [i-1] in the current map are the same (2a),
so we have to look at the second line. Sure enough, the address at [i]
in the current map is the same as the address in the original BIOS map
(2b). And now to reveal the final bit of the diagram to evaluate
condition (2c):

change_point[]
                                    0        1        ...        i-1  
     i        ...        n
addr                                                           0x80    0x80
pbios->addr                            (2c) ==>  0x79    0x80

The address at [i-1] in the current map is *not* the same as the
address at [i-1] in the original BIOS map, so we have detected an
overlap and must repair it.

I hope this helped to answer your question.

Cheers,
Josh

[1] http://safari.oreilly.com/
[2] http://www.amazon.com/gp/product/0596005652/ref=wl_it_dp/103-0893130-9345430?%5Fencoding=UTF8&colid=220Z673P6NRWV&coliid=I38BV9O3U0AU2Y&v=glance&n=283155
[3] http://lxr.linux.no/source/arch/i386/kernel/setup.c#L446
[4] http://lxr.linux.no/source/arch/i386/kernel/setup.c#L426