INFR100792023 LabCW2

Operating Systems Tutorial/Lab CW1

Operating Systems
Tutorial/Lab CW2

Semester 2 Academic year 23-24

Karim Manaouil, Antonio Barbalace

• Quick recap on Virtual Memory and PCB

• Page Table

• mm_struct

• VM areas

Some material from: https://linux-kernel-labs.github.io/refs/heads/master/labs/memory_mapping.html

https://linux-kernel-labs.github.io/refs/heads/master/labs/memory_mapping.html

Recap: Virtual Memory

In the old days (1970)

With virtual memory

Translation

load from 0x102030

load from 0x102030 0x102030 → 0x9080

Translation benefits

● Improved memory utilization
● Protection
● Demand paging
● Swapping (use disk)

Recap: Translation

Translation table
(a.k.a Page Table)

Physical memory pages
(each 4096 bytes)

Handled by

● The table can be very big
○ Each entry size is 8 bytes
○ Each entry maps a single 4KiB range
○ For 4 GiB virtual space we need (4 GiB / 4 KiB) * 8

bytes = 8 MiB
○ For 100 process, 800 MiB is metadata

index content

Recap: Multi-level Page Table

Multi-level PT benefit

● Size proportional to the used address space

Rem: struct task_struct

• struct task_struct in Linux is (born as) the Process Control Block
o Where in the code?
o Include/linux/sched.h (from line 737 to line 1546)

https://elixir.bootlin.com/linux/v6.1.75/source/include/linux/sched.h#L737

PCB and Page table relationship (1/2)

• struct task_struct.mm -> struct mm_struct.pgd -> page table
o Where in the code?
o struct task_struct https://elixir.bootlin.com/linux/latest/source/include/linux/sched.h#L877
o struct mm_struct https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h#L764

https://elixir.bootlin.com/linux/latest/source/include/linux/sched.h#L877
https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h#L764

PCB and Page table relationship (2/2)

task_struct

page table

virtual address

physical address

https://elixir.bootlin.com/linux/latest/source/include/linux/sched.h#L877
https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h#L764

Keeping track of what is used and what not

• Introducing struct page

physical page

struct page

struct page (1/2)

• struct page embeds information about physical pages in the system
• Kernel maintains a struct page for each pages in the system

• Where in the code?
• https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h#L74

https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h#L74

struct page (2/2)

• Many functions interact with struct page

• virt_to_page() returns the struct page associated with a virtual address
• pfn_to_page() returns the struct page desc associated with a page frame

• page_to_pfn() return the page frame number associated with a struct

• page_address() returns the virtual address of a struct page; this functions

can be called only for pages from lowmem
• kmap() creates a mapping in kernel for an arbitrary physical page (can be

from highmem) and returns a virtual address that can be used to directly
reference the page

Dump a process page table

• User-space programs that exploits the Linux /proc interface
• https://www.kernel.org/doc/html/v4.18/admin-guide/mm/pagemap.html

• https://elixir.bootlin.com/linux/latest/source/tools/mm/page-types.c
• Part of the Linux kernel source

• https://github.com/dwks/pagemap
• Independent project

• https://github.com/jethrogb/ptdump
• Independent project, multi OS

• You can also dump the kernel page table
• https://www.kernel.org/doc/html//next/arch/arm64/ptdump.html

https://www.kernel.org/doc/html/v4.18/admin-guide/mm/pagemap.html
https://elixir.bootlin.com/linux/latest/source/tools/mm/page-types.c
https://github.com/dwks/pagemap
https://github.com/jethrogb/ptdump
https://www.kernel.org/doc/html//next/arch/arm64/ptdump.html

Let’s write a kernel-level page table walker!

(while previous slides discuss a user-level dump tool)
Important data structures:

struct mm_struct *mm

struct vm_area_struct *vma

Important operations:
pmd_offset()

pmd_none()

pmd_huge()

pmd_present()

pte_offset_map()

pte_present()

pte_write()

p4d_offset()

p4d_none()

pgd_offset()

pgd_none()

Bring up the CW environment

• XRDP Connection
• On Windows use “Remote desktop Connection” application
• sXXXXXXX.remote.inf.ed.ac.uk

• Open a shell and connect to student.compute (or other machines)
• sXXXXXXX: ssh student.compute

• Start QEMU first
• sXXXXXXX: qemu-system-x86_64 -m 4G -smp 4 -drive
file=/disk/scratch/sXXXXXXX/debian.qcow2 -nographic
-S -gdb tcp::YYYYY -kernel /disk/scratch/sXXXXXXX/linux-
6.1.75/arch/x86_64/boot/bzImage
-append “root=/dev/sda1 console=ttyS0 earlyprintk=ttyS0 nokaslr”

• Start gdb second – you need another console/terminal
• sXXXXXXX: cd /disk/scratch/sXXXXXXX/linux-6.1.75
• sXXXXXXX: gdb vmlinux
• (gdb) target remote localhost:YYYYY
• (gdb) source vmlinux-gdb.py

This is the kernel we
compiled before !!!

Same commands we
used before !!!

Make sure gcc is installed

• Commands must be typed INTO the VM
o Let’s make sure the VM is connected to the network

▪ # dhclient

▪ # ping 1.1.1.1

o If the ping works, continue
▪ # apt-get update

▪ # apt-get install gcc

o If asked, answer “yes”

A simple test program

• Commands must be typed INTO the VM
• Pick one of the followings!

getchar.c <<< edit it in nano or vim # gcc –o getchar getchar.c pause.c <<< edit it in nano or vim # gcc –o pause pause.c How a process address space looks like? (1/2) How a process address space looks like? (2/2) • Commands must be typed INTO the VM • Disable address space randomization • # echo 0 >
/proc/sys/kernel/randomize_va_space

• Launch the simple test program
• # ./pause &
• [123] 21345

• Check the address space layout
• # cat /proc/21345/maps

• Where 21345 in /proc//maps is PID
• You can also try

• # cat /proc/self/maps

File backed areas

Heap and Stack

I want more information! (1/3)

• pmap comes to help

I want more information! (2/3)

• pmap comes to help

I want more information! (3/3)

• pmap comes to help

# pmap –XX 1450 > pause.pmap

vm_area_struct (1/2)

Note: this picture refers to an older kernel,
mmap member doesn’t exist anymore,
instead there is mm_mt

vm_area_struct (2/2)

Note: this picture refers to an older kernel,
mmap member doesn’t exist anymore,
instead there is mm_mt

vm_area_struct source code

• Describes a virtual memory area, one per VM-area/task
• https://elixir.bootlin.com/linux/latest/source/include/linux/mm_types.h#

VM areas are saved on a Maple Tree

• https://elixir.bootlin.com/linux/latest/source/include/linux/mm_ty
pes.h#L1072

Maple Tree Intro https://blogs.oracle.com/linux/post/the-maple-tree-a-modern-data-structure-for-a-complex-problem

Maple Tree API https://docs.kernel.org/next/core-api/maple_tree.html

https://blogs.oracle.com/linux/post/the-maple-tree-a-modern-data-structure-for-a-complex-problem
https://docs.kernel.org/next/core-api/maple_tree.html

VM areas handling

• (Probably) the best example
• The source code of /proc//maps

• In the Linux kernel source tree fs/proc/task_mmu.c

• https://elixir.bootlin.com/linux/latest/source/fs/proc/task_mmu.c

https://elixir.bootlin.com/linux/latest/source/fs/proc/task_mmu.c#L129
https://elixir.bootlin.com/linux/latest/source/fs/proc/task_mmu.c#L129

Slide 1: Operating Systems Tutorial/Lab CW2
Slide 2: Today
Slide 3: Recap: Virtual Memory
Slide 4: Recap: Translation
Slide 5: Recap: Multi-level Page Table
Slide 6: Rem: struct task_struct
Slide 7: PCB and Page table relationship (1/2)
Slide 8: PCB and Page table relationship (2/2)
Slide 9: Keeping track of what is used and what not
Slide 10: struct page (1/2)
Slide 11: struct page (2/2)
Slide 12: Dump a process page table
Slide 13: Exercise
Slide 14: Bring up the CW environment
Slide 15: Make sure gcc is installed
Slide 16: A simple test program
Slide 17: How a process address space looks like? (1/2)
Slide 18: How a process address space looks like? (2/2)
Slide 21: I want more information! (1/3)
Slide 22: I want more information! (2/3)
Slide 23: I want more information! (3/3)
Slide 24: vm_area_struct (1/2)
Slide 25: vm_area_struct (2/2)
Slide 26: vm_area_struct source code
Slide 27: VM areas are saved on a Maple Tree
Slide 28: VM areas handling