Linux from scratch to learn 06:16 structure diagrams, a thorough understanding of the underlying principles of [code relocation]

Author: Doug, 10+ years embedded development veteran.

Public account: [IOT Town], focusing on: C/C++, Linux operating system, application design, Internet of things, SCM and embedded development and other fields. The public account replies [books] to get classic books in the field of Linux and embedded.

Reprint: welcome to reprint the article, reprint should indicate the source.

In the previous article Linux Ab initio 05- A few mysterious addresses during the system boot process, do you know what it means? With a few important memory locations as clues, we introduce x86 systems after power-on:

How the CPU executes the first instruction;

How programs in the BIOS are executed;

The boot code of the operating system (bootloader) is read into physical memory and executed;

The next step is for the bootloader to read the operating system program into memory, and then jump to the first instruction of the operating system.

In this article, we continue to use the 8086 as a simple processor prototype to describe the process of loading the program. The key part of this is code relocation, and we graphically describe, to the best of my ability, the process of calculating the load and address relocation of the program.

PS: The program, the operating system file, is the same thing.

Program structure

In order to facilitate the following understanding, we need to load the operating system program file structure first introduced.

Of course, the file structure described here is a very simplified version of the operating system program, which is essentially the same as the application we write, so we can also think of it as a normal program file.

Operating system programs lie on the hard disk waiting to be read by the bootloader, which acts as a loader.

After all, they belong to two different things, and in order for the bootloader to know the length of the program, it needs some kind of “protocol” to communicate. This “protocol” is the Header of the program file.

In other words, at the beginning of the program, you will describe yourself in detail, including: how many bytes the program is, how many segments it has, where the entry address is, and so on.

Remember the ELF file format used on Linux? ELF files, the building blocks of Linux compilation and linking: Peel away the layers and explore the granularity of bytecode

The article takes a typical Linux ELF format executable file and breaks it down completely. You can see that the header of the ELF file describes each part of the file in detail.

In fact, the Windows program format (PE format) is similar, it and the ELF format from the same ancestor.

1. Description of the program Header

For the sake of description, let’s assume that the program consists of three segments: code, data, and stack, plus header information, for a total of four components. As follows:

Why is there a white space in the middle?

Since segments are not aligned next to each other, in order for segment addresses to be memory-aligned (16 bytes aligned), there may be a space between segments where the data is invalid.

In order for the bootloader to know as much about itself as possible, the program file describes itself in detail in its Header section:

With this description, the bootloader knows how many bytes of the program file to read and where to jump for the operating system instructions to start executing.

2. On assembly addresses

In the header information of the program, you can see such information as the assembly address and offset.

When the compiler compiles the source code, it does not know where in memory the bootloader will load the program.

The bootloader sees where there is enough space, finds a available location, and reads the operating system program to that location, which can be viewed as a dynamic process.

Therefore, the address that the compiler uses to locate variables, tags, etc., during compilation is calculated relative to the start address of the current segment.

Take the picture again:

Let’s assume that the Header section is 32 bytes long and that the three segments start at:

Code snippet addrCodeStart: 0x00020 (the first byte from the file is 32 Bytes);

Data segment addrDataStart: 0x01000 (the first byte from the file is 4K Bytes);

Stack segment addrStackStart: 0x01200 (the first byte from the file is 4K+512 Bytes);

In the code snippet, a label label_1 is defined that is 512 bytes (0x0200) from the beginning of the code snippet (0x00020).

Also, you can calculate that the first byte from the beginning of the file is 512 + 32 = 544 bytes, because the beginning address of the code snippet is 32 bytes from the head of the file.

In the code preceding label_1, this label is referred to.

Where it is used, 0x0200 will be filled in, indicating that the reference is 512 bytes from the start address of the code snippet.

The above addresses refer to assembly addresses.

Let’s take the offset from the program’s entry address, which is defined by the start tag:

Suppose: In the code snippet, the entry address label start is at the 0x0100 offset from the start of the code snippet, which is 256 bytes from the start of the code snippet.

So, in the program Header, the entry point offset should be 0x0100, so that the bootloader, after reading the program into memory, can get the entry point offset from here, and then go through a series of relocations. You can jump right to the first instruction of the program.

With the assumed address information, the program Header information looks like this:

The blue font on the far right indicates the number of bytes per item, which is 24 bytes in total.

As mentioned earlier, the beginning address of each segment is aligned with 16 Bytes, so after the Header, there should be 8 Bytes of space, and then the beginning address of the code segment (0x00020 = 32 Bytes).

The bootloader reads the program from the hard disk into memory

1. Where in memory is it read?

Before the bootloader can read an operating system file from hard disk into memory, it must decide one thing: where to store the file contents in memory?

As we learned from the previous article, before reading the operating system, the memory layout model looks like this:

Note: This is the 1 MB address space that 20 address lines can address in an 8086 system.

Where the top 64 KB, mapped to the BIOS program in ROM.

The 1 KB address space at the bottom, starting at 0, stores 256 interrupt vectors (we’ll talk about interrupts in the next article).

The middle place, starting at address 0x07C00, is where the BIOS reads the bootloader program from the hard disk’s boot area.

The space in yellow is a total of 640 KB of space, which is mapped to RAM, so there is enough free address space to store operating system program files.

Hypothesis: The bootloader decides to start at address 0x20000 (128 KB) and store the operating system program files read from the hard disk.

2. The bootloader sets the base address of the data segment

When a file is read from a hard disk, it is read on a sector basis, that is, one sector (512 bytes) at a time.

How to read data from the hard disk by specifying sector numbers and sending port commands is another topic, but let’s focus on the bootloader instead of the table.

For the bootloader, reading operating system files is equivalent to reading normal data.

The bootloader will set the data segment register ds to 0x2000 if it has decided to start at address 0x20000. In this case, the bootloader will set the data segment register DS to 0x2000.

Physical address = Logical segment address x 16 + offset address

To get the correct physical address, for example:

The first sector is read at: 0x2000:0x0000;

The second sector is read at: 0x2000:0x0200;

The third sector is read at: 0x2000:0x0400;

.

The tenth sector is read at the: 0x2000:0x1200 address;

3. The bootloader reads all sectors

The bootloader needs to read all the contents of the operating system program into memory. What length does the bootloader need to read?

The program file Header contains this information, so the bootloader needs to read the first sector of the program file, which is 512 bytes, and place it at 0x20000.

Let’s continue to assume that the total length of the program is 5K bytes (0x01400), so the first 512 bytes (the first sector) of the program file are read into memory, as follows:

Note: This is the layout in which the contents of the file are read into memory, with low addresses at the bottom and high addresses at the top, in reverse order of the contents of static files described earlier.

After reading the first sector, we can fetch 4 bytes of data starting with 0x20000:0x01400, and get the total length of the program file: 5K bytes.

Each sector is 512 bytes, 5 K bytes equals 10 sectors.

The first sector has been read, so you need to continue reading the remaining nine sectors.

Therefore, the bootloader reads the data of all sectors in the following sequence: 0x2000:0x0000, 0x2000:0x0200, 0x2000:0x0400,… 0x2000:0x1200 address.

4. What if the program file exceeds 64 KB?

Here’s an extended question to think about:

Segment addressing in 8086, since the offset register is 16 bits long, can only represent 64 KB of space.

In our hypothetical example, the program file is only 5 KB and can be included in a data segment, so the bootloader can always read the file with the 0x2000: offset.

If the program is 100 KB long, what should the bootloader do to properly read 100 KB into memory?

Answer:

You can dynamically increase the logical address of the data segment during the process of reading the file.

For example, the segment register DS is set to 0x2000 when the preceding 64 KB of data (sectors 1 to 128) is read.

Before reading the 65th KB of data (sector 129), set the segment register DS to 0x3000, so that the data read starts at 0x3000-0x0000.

Code relocation

Now that the operating system program has been read into memory, the next step is to jump to the entry point of the operating system program to execute!

Program entry point relocation

The offset of the program entry point, which has been recorded in the Header (0x04 to 0x05 bytes, orange) :

The offset of the entry point start tag in the code segment recorded in the Header is 0x100, that is, the entry point is 256 bytes away from the start address of the code segment.

In the same way, all related addresses in a code segment are offset relative to the starting address of the code segment.

Therefore, if the bootloader puts the start address of the code snippet (not the start of the entire file) directly in memory at 0x00000, then all the addresses in the code snippet do not need to be changed and can be set directly: Cs = 0x0000, IP =0x0100, this will jump directly to the start TAB to start the execution.

Unfortunately, the bootloader reads the operating system program at address 0x20000. Therefore, you need to set the code segment register CS to the actual starting position of the current code segment in memory, which is the following pentangular star:

The above two paragraphs can be read several more times!

In the Header, 0x06, 0x07, 0x08, and 0x09 are four bytes of data 0x00020, which is the number of bytes from the beginning of the code segment to the beginning of the program file.

Just add this value (0x00020) to the start address of the file store (0x20000) to get the absolute physical memory address of the code snippet’s start address:

0x00020 + 0x20000 = 0x20020

That is, the starting address of the code segment, located at 0x20020 in physical memory.

For a physical address, we can use a number of different logical addresses, for example:

0x20020 = 0x2002:0x0000

0x20020 = 0x2000:0x0020

0x20020 = 0x1FF0:0x0120

Of these three choices, we choose the first, and only the first, because all address offsets within the code sniplet are compiled based on the 0 address (the assembly address above), or relative address.

With this in mind, you can set cs: IP to 0x2002:0x0100 and the CPU will execute at the start tag.

However, there are a few other things that need to be done before we can do this, so write the logical segment address 0x2002 back to the four bytes 0x06 ~ 0x09 in the Header (orange) :

Segment table relocation

At this point, the system is still under the control of the bootloader, and the data segment register DS is still 0x2000.

Because the bootloader wants to read the data to the physical address 0x20000 before reading the first sector of the operating system program, it moves one bit to the right to get the logical segment address 0x2000, and writes it to the data segment register DS.

We have been ignoring the stack space used by the bootloader because this part is independent of the file topic.

Operating system programs that want to be executed must use data and stack segments in their own program files.

However, the starting address of the two segments recorded in the Header is relative to the beginning of the program file.

And the operating system file does not know where in memory it was read by the bootloader.

Therefore, the bootloader also needs to recalculate the starting address of the two segments in memory, and then update them to the Header.

This way, when the operating system program starts executing, we can get the logical segment address of the data segment and the stack segment from the Header.

Of course, the example here has only three segments; a real program might include many segments, each of which needs to be relocated.

From the two bytes 0x0A to 0x0B in the Header, the bootloader can obtain the total number of segment addresses that need to be relocated.

Then read the offset address of each segment in sequence, add the loading address of the program file (0x20000), calculate the actual physical address, and then get the address of the logical segment, as follows:

Segment offset 0x00020:0x20000 + 0x00020 = 0x20020(physical address), shift one bit to the right to get the logical segment address: 0x2002;

Data segment offset 0x0x01000: 0x20000 + 0x01000 = 0x21000(physical address), right shift one bit to get logical segment address: 0x2100;

Stack segment offset 0x0x01200: 0x20000 + 0x01200 = 0x21200(physical address), shift right one bit to get logical segment address: 0x2120;

The orange part below:

We draw the layout model of code segment, data segment and stack segment in memory:

Jumps to the entry address of the program

Everything is ready except the east wind!

With everything in place, the final step is to enter the start entry point of the code snippet in the operating system program.

In the above preparation work, the bootloader has saved the logical segment address 0x2002 in the Header 0x06 ~ 0x09, and just assign it to the code segment register CS.

The program entry point is located at the start label, which is 0x100 offset from the start of the code segment, and the two bytes 0x04 ~ 0x05 are stored in the Header, as long as it is assigned to the instruction pointer register IP.

We can read it manually and then assign it.

You can also use the instruction JMP [0x04] in the 8086 CPU to assign cs: IP.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * This starts the first instruction of the operating system program.

The execution of an operating system program

When the first instruction of the operating system is executed, the values in the data segment register DS and stack segment register CS are still the values set by the bootloader.

Therefore, the operating system must first set the two segment registers to the values of its program file before it can begin the execution of subsequent instructions.

As mentioned above, the logical segment address of each segment in memory has been recalculated by the bootloader and updated to the Header.

Therefore, the operating system can read the new stack segment logical address 0x2120 from ds:0x14 and assign it to the stack segment register CS.

From this point on, all stack operations are the operating system program’s own.

Note: at this point, the data segment register DS remains unchanged and is still 0x2000 as used by the bootloader.

It then reads the new segment address 0x2100 from ds:0x10 and assigns it to the segment register DS.

From this point on, all data manipulation is the operating system program’s own.

Note: Cs and DS cannot be assigned in reverse order.

If you assign ds first, then when you go to the Header and read the cs logical segment, you’re not going to be able to locate it.

Because the ds register is already pointing to the new address (ds = 0x2100), there is no way to retrieve data from 0x2000:0x14.

Finally, for stack operations, in addition to setting the stack segment register SS, you also need to set the stack top pointer register SP.

We assume that the stack space is set to 512 bytes, and that the top pointer of the stack grows towards the lower address, so we need to initialize sp to 512.

At this point, the operating system program can finally begin to execute happily!

In this article, we have described the lowest level principles of code relocation.

As you learn about relocation in Linux, you’ll learn more about concepts and techniques, but the underlying principles are the same.

I hope this article can become a stepping stone on your way forward!