x64 Virtual Address Translation

junyaU — Sun, 15 Dec 2024 11:21:31 +0000

Introduction to Paging

Paging is a memory management mechanism that maps virtual address space to physical address space. This mechanism divides virtual address space into fixed-size units called 'pages' and physical address space into 'frames', then maps pages to frames. The page size can be set to either 4KiB, 2MiB, or 1GiB. In this explanation, we'll use the 4KiB page size, which is the most commonly used configuration.

Pages can be mapped to frames independently, so they don't need to be contiguous in physical address space. This mapping is managed by page tables, which are structured in a hierarchical manner in x64 systems.

x64 Paging Structure

A page table is a data structure that stores the necessary information for mapping pages to frames.

In x64 4-Level Paging, four levels of page tables are used as follows:

PML4 (Page Map Level 4)
PDP (Page Directory Pointer)
PD (Page Directory)
PT (Page Table)

Each table consists of 512 entries, with each entry being 8 bytes in size. Each entry stores the base address of the next-level table and its attributes. As an exception, PT entries store the base address of the corresponding frame, which becomes the actual physical address.

The base address of the PML4 Table is obtained from the CR3 register. All page tables are placed in physical address space, and each table occupies 4KiB (512 entries × 8 bytes).

Each process requires its own page tables since each process has a unique virtual address space. The OS switches page tables by loading the base address of the process's page table into the CR3 register before execution.

The entries to be referenced in each table are determined by interpreting the structure of the virtual address during address translation.

Virtual Address Interpretation

The conversion from virtual to physical address requires proper interpretation of the virtual address. Let's use 0xFFFF80001E141F3C as an example virtual address to explain this process.

Canonical Address

In the x64 architecture, bits 63:48 of the virtual address are treated as sign extension bits. These bits must be filled with the value of bit 47.

Virtual addresses that satisfy this constraint are called 'canonical addresses', and the CPU raises an exception if an address not following this format is used.

Canonical addresses are classified into two ranges:

Negative canonical addresses (bits 63:48 are all 1s)
- 0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF
- Known as kernel space, used by the operating system kernel
Positive canonical addresses (bits 63:48 are all 0s)
- 0x0000000000000000 ~ 0x00007FFFFFFFFFFF
- Known as user space, used by user processes

Our example address 0xFFFF80001E141F3C is a negative canonical address.

Page Table Index and Page Offset

Bits 47:12 of the virtual address are divided into four 9-bit segments, each used as an index into a different page table:

Bits 47:39 - PML4 Table index
Bits 38:30 - PDP Table index
Bits 29:21 - PD Table index
Bits 20:12 - Page Table index

Bits 11:0 are used as the page offset, which is added to the frame address to obtain the final physical address.

Let's interpret our example address 0xFFFF80001E141F3C:

Bits 47:39 - 0x1E (30) → references PML4 Table[30]
Bits 38:30 - 0x14 (20) → references PDP Table[20]
Bits 29:21 - 0x1 (1) → references PD Table[1]
Bits 20:12 - 0xF (15) → references Page Table[15]
Bits 11:0 - 0x3C (60) → offset of 60 bytes from the frame address

If the frame address pointed to by the final Page Table entry is 0x200000, the physical address becomes 0x200000 + 0x3C = 0x20003C.

Why Both return and exit() Work in main()

junyaU — Wed, 06 Nov 2024 14:45:36 +0000

Introduction

In C programming, there are two ways to terminate a program from the main function: using return and using exit().

int main() {
    printf("Hello, World!");
    return 0;    // Method 1: Normal termination
}

int main() {
    printf("Hello, World!");
    exit(0);     // Method 2：Normal termination
}

Why can both methods terminate the program correctly, even though they appear completely different?
In this article, we'll unravel this mystery by understanding how C programs actually start and terminate.
Note that this article focuses on the implementation in GNU/Linux environments, specifically using glibc.

How exit() Works

First, let's examine how the exit function works to understand the program termination mechanism.
The exit function is a standard library function that properly terminates a program.
Internally, the _exit function, which is called by exit, is implemented in glibc as follows:

void
_exit (int status)
{
  while (1)
    {
      INLINE_SYSCALL (exit_group, 1, status);

#ifdef ABORT_INSTRUCTION
      ABORT_INSTRUCTION;
#endif
    }
}

Looking at this implementation, we can see that the _exit function receives an exit status as its argument and calls exit_group (system call number 231).

This system call performs the following operations:

Sends a program termination notification to the kernel
The kernel performs cleanup operations:
- Releases resources used by the process
- Updates the process table
- Performs additional cleanup procedures

Through these operations, the program terminates properly.

So, why does returning from main() also properly terminate the program?

C Program's Hidden Entry Point

To understand this, we need to know an important fact: C programs don't actually start from main.

Let's check the default settings of the linker (ld) to see the actual entry point:

$ ld --verbose | grep "ENTRY"
ENTRY(_start)

As this output shows, the actual entry point of a C program is the _start function. main is called after _start.
The _start function is implemented in the standard library, and in glibc, it looks like this:

_start:
    # Initialize stack pointer
    xorl %ebp, %ebp
    popq %rsi        # Get argc
    movq %rsp, %rdx  # Get argv

    # Setup arguments for main
    pushq %rsi       # Push argc
    pushq %rdx       # Push argv

    # Call __libc_start_main
    call __libc_start_main

The _start function has two main roles:

Initializes the stack frame required for program execution
Sets up command-line arguments (argc, argv) for the main function

After these initializations are complete, __libc_start_main is called.
This function is responsible for calling the main function.

Now, let's examine how __libc_start_main works in detail.

How __libc_start_main Makes return Work

__libc_start_call_main, which is called by __libc_start_main, is implemented as follows:

_Noreturn static void
__libc_start_call_main (int (*main) (int, char **, char ** MAIN_AUXVEC_DECL),
                        int argc, char **argv
#ifdef LIBC_START_MAIN_AUXVEC_ARG
                            , ElfW(auxv_t) *auxvec
#endif
                        )
{
  int result;

  /* Memory for the cancellation buffer.  */
  struct pthread_unwind_buf unwind_buf;

  int not_first_call;
  DIAG_PUSH_NEEDS_COMMENT;
#if __GNUC_PREREQ (7, 0)
  /* This call results in a -Wstringop-overflow warning because struct
     pthread_unwind_buf is smaller than jmp_buf.  setjmp and longjmp
     do not use anything beyond the common prefix (they never access
     the saved signal mask), so that is a false positive.  */
  DIAG_IGNORE_NEEDS_COMMENT (11, "-Wstringop-overflow=");
#endif
  not_first_call = setjmp ((struct __jmp_buf_tag *) unwind_buf.cancel_jmp_buf);
  DIAG_POP_NEEDS_COMMENT;
  if (__glibc_likely (! not_first_call))
    {
      struct pthread *self = THREAD_SELF;

      /* Store old info.  */
      unwind_buf.priv.data.prev = THREAD_GETMEM (self, cleanup_jmp_buf);
      unwind_buf.priv.data.cleanup = THREAD_GETMEM (self, cleanup);

      /* Store the new cleanup handler info.  */
      THREAD_SETMEM (self, cleanup_jmp_buf, &unwind_buf);

      /* Run the program.  */
      result = main (argc, argv, __environ MAIN_AUXVEC_PARAM);
    }
  else
    {
      /* Remove the thread-local data.  */
      __nptl_deallocate_tsd ();

      /* One less thread.  Decrement the counter.  If it is zero we
         terminate the entire process.  */
      result = 0;
      if (atomic_fetch_add_relaxed (&__nptl_nthreads, -1) != 1)
        /* Not much left to do but to exit the thread, not the process.  */
    while (1)
      INTERNAL_SYSCALL_CALL (exit, 0);
    }

  exit (result);
}

In this implementation, the key parts to focus on are as follows:

result = main (argc, argv, __environ MAIN_AUXVEC_PARAM);
exit(result);

Here, the important point is how the main function is executed and its return value is handled:

Executes the main function and stores its return value in result
Uses the return value from main as an argument for exit

Through this mechanism:

When using return in main → The return value is passed to __libc_start_main, which then passes it to exit
When exit() is called directly in main → The program terminates immediately

In either case, exit is ultimately called, ensuring proper program termination.

Conclusion

C programs have the following mechanism in place:

The program starts from _start
_start prepares for main's execution
main is executed through __libc_start_main
Receives main's return value and uses it as an argument for exit