linux 0.11

linux-0.11

Theory course: https://www.bilibili.com/video/BV1d4411v7u7

Useful references ( linux-0.11 commented version): https://github.com/beride/linux0.11-1

main branch is linux-0.11 source code

View the code difference: Pull request Select the corresponding branch and compare it with main

✔️ lab0 Operating System Boot (branch lab0)

1. Rewriting bootsect.s mainly completes the following functions:

   • bootsect.s can print a message "XXX is booting..." on the screen.

2. Rewriting setup.s mainly completes the following functions:

   • bootsect.s can complete the loading of setup.s and jump to the setup.s start the execution address. and setup.s outputs a line "Now we are in SETUP" to the screen. setup.s can obtain at least one basic hardware parameter (such as memory parameters, graphics card parameters, hard disk parameters, etc.), store it in a specific address in memory, and output it to the screen. setup.s no longer loads the Linux kernel, just keep the above information displayed on the screen.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/568/document/

✔️ lab1 implements system calls (branch lab1)

1. The total number of system calls modified in kernel/system_call.s is 74.
2. Add a macro in include/unistd.h to indicate the call function table positioning.
3. Write two functions (sys_iam, sys_whoami) function definitions in include/linux/sys.h. And add two new functions to the function table after it.
4. Added kernel/who.c to implement two system calls.
5. Modify makefile
   • OBJS increases who dependency (who.o)
   • Add dependency generation conditions for who.s and who.o in Dependencies
6. make execute ./run to enter the linux subsystem, and add the macro definitions of iam and whoami in /usr/include/unistd.h (same as point 2).
7. Writing a test program in the user state tests whether it is successful.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/569/document/

✔️ lab2 implements the tracking of process operation trajectory (branch lab2)

1. process.c implements a scenario that simulates a hybrid CPU computing and io computing, and runs it in a multi-process manner.
2. Print out several states of kernel process switching (pid status time) to /var/process.log.
3. After the init() function in init/main enters the user state statement, associate file descriptor 3 to /var/process.log.
4. Implement the fprintk() function in kernel/printk to print out the output to the process.log log.
5. Find the state switching point and add fprintk() to write logs.
   • Process start kernel/system_call.s -> sys_fork (call copy_process)
   • Run, blocking state switch kernel/sched.c -> schedule sys_pause sleep_on interruptible_sleep_on wake_up
   • Exit kernel/exit.c -> do_exit sys_waitpid
6. Note: gcc in linux-0.11 cannot be compiled // commented.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/570/document/

✔️ lab3 replaces the original tss process in linux0.11 to switch to stack switching (branch lab3)

The original switching method is through tss, which is equivalent to a snapshot of the register. It is directly replaced on-site through the instructions provided by Intel, which is slower. Stack switching is more efficient.

kernel/sched.c

1. The original switch_to method is based on tss switch, and we want to comment out it in the header file.
2. New switch_to, requires two parameters (1: pointer to the next pcb 2: the position of the next task in the array is used to switch LDT).

kernel/system_call.s

1. Write switch_to assembly implementation
2. Switching of pcb
3. Rewrite the tss kernel stack position (tss is retained at this time, but there is only one tss in the world, and it is not used to do process switching.)
4. Switch the kernel stack
5. LDT switch

kernel/fork.c

1. Log out of the tss settings in pcb.
2. Add a new member variable - kernel stack to pcb, which is used to store kernel stack information.
3. Write stack information here and let pcb the member variable point to the pointer.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/571/document/

Reference: https://blog.csdn.net/qq_42518941/article/details/119182097

✔️ lab4 implements semaphore system calls in linux0.11 (branch lab4)

Pre-key knowledge points

1. kernel/sched.c sleep_on Pass the incoming waiting queue header, set current to blocking state, and actively execute schedule(). tmp stores the original blocking queue. When awakened, the blocking queues are all set to Runnable.
2. kernel/sched.c wake_up wakes up all blocked PCBs. Only the wake-up team leader can be seen in the program, but it must be read in combination with sleep_on. Once combined, you will find that the wake-up head will wake up all subsequently.

Write the application "pc.c" to solve the classic producer-consumer problem and complete the following functions:

• Establish a producer process, N consumer processes (N>1)
• Create a shared buffer with files
• The producer process writes integers 0, 1, 2,…, M, M>=500 to the buffer in turn
• The consumer process reads from the buffer, reads one at a time, and deletes the read numbers from the buffer, and then outputs the process ID and + numbers to the standard output
• The buffer can only save up to 10 numbers at the same time

Implement semaphore

 sem_t * sem_open ( const char * name , unsigned int value );
int sem_wait ( sem_t * sem );
int sem_post ( sem_t * sem );
int sem_unlink ( const char * name );

• sem_open opens a semaphore
• If the semaphore is currently equal to zero, blocking the process
• Add one semaphore
• Turn off a semaphore

The focus of wait and post

• wait
  • Call kernel/sched.c sleep_on to wait for blocking
  • Use the linux interrupt (linux0.11 single core) to protect the critical zone
  • minus one value of sem
• post
  • Add one to the value of sem. If the value is greater than 0, call kernel/sched.c wake_up to wake up the process blocked by this semaphore.
  • Use the linux interrupt (linux0.11 single core) to protect the critical zone

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/572/document/

✔️ Mapping and sharing of lab5 addresses (branch lab5)

Logical Address -> GDT -> LDT -> Page Table -> Physical Address

Instrument theory knowledge

Segment Selector

Access to the global descriptor table by GDTR is done through the "segment selector" (segment register in real mode)

15 3 2 1 0

| index | | RPL |

• 3-15 is the descriptor index, which indicates the descriptor of the required segment in the descriptor table.
• 2 To indicate whether the selector is selected in GDT or in LDT (0 represents GDT 1 represents LDT).
• 0-1 is the privilege level to select.

The segment selector includes three parts: descriptor index (index), TI, and request privilege level (RPL). Its index (descriptor index) part indicates the descriptor position of the required segment in the descriptor table. From this position, the corresponding descriptor can be found based on the descriptor table base address stored in GDTR. Then, the segment base address in the descriptor table plus the logical address (SEL:OFFSET) can be converted into a linear address. The TI value in the segment selector is only one 0 or 1. 0 means that the selector is selected in GDT, and 1 means that the selector is selected in LDT. The request privilege level (RPL) represents the privilege level of the selector, and there are 4 privilege levels (level 0, level 1, level 2, and level 3).

Note on the privilege level: Each segment in the task has a specific level. Whenever a program tries to access a segment, the privilege level that the program has is compared with the privilege level to be accessed to determine whether the segment can be accessed. The system convention is that the CPU can only access segments of the same privilege level or at a lower privilege level.

For example, give the logical address: 21h:12345678h converted to linear address

a. Selector SEL = 21h = 0000000000100 0 01(b) means: the index of the selector=4, that is, 0100, and the fourth descriptor in GDT is selected; TI=0 means that the selector is selected in GDT; the last 01 means privilege level RPL=1.

b. OFFSET=12345678h If the segment base address described in the fourth descriptor of GDT at this time is 1111111h, then the linear address = 111111h + 12345678h = 23456789h.

Visit GDT

1. First get the GDT base address from the GDTR register.
2. Then in GDT, the segment descriptor is valued at the segment selector high 13-bit position index.
3. Get the base address, add the offset to get the linear address.

Access LDT

1. First get the GDT base address from the GDTR register.
2. Get the position index of the segment where the LDT is located from the LDTR register (LDTR is 13 bits higher).
3. The LDT segment descriptor is obtained in GDT with this position index to obtain the LDT segment base address.
4. Use the segment selector to obtain the segment descriptor from the LDT segment.
5. Get the base address, add the offset to get the linear address.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/573/document/

✔️ lab6 terminal device control (branch lab6)

1. When the keyboard interrupt occurs, the keyboard scan code is removed and the scanning code is processed according to the key_table table.
2. Complete the function writing corresponding to the F12 key.
3. After processing, put the characters with the corresponding scan code into put_queue.
4. Call do_tty_interrupt for the final processing, where copy_to_cooked does the final preprocessing, and then call con_write to output to the graphics card.
5. write -> sys_write -> tty_write -> con_write.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/574/document/

✔️ Implementation of lab7 proc file system (branch lab7)

Theoretical knowledge

disk

Reading and writing mechanical disks requires three parameters to locate

1. Cylinder (C)
2. Head (H)
3. Sector (S)

 block = C * ( H * S ) + H * S + S ;

Dividing several sectors into one block to improve disk io efficiency (linux0.11 Dividing 2 sectors into one block). For a higher level, you only need to enter the read and write block number to perform disk io.

Division: Boot block | Super block | inode bitmap | Data bitmap | inode block | Data block

document

Use FCB (inode in linux0.11) to store file information, including different types of files (for example: device files, directory files...).

 struct m_inode 
 { 
 unsigned short i_mode ;      // 文件类型和属性(rwx 位)。 
 unsigned short i_uid ;       // 用户id（文件拥有者标识符）。 
 unsigned long i_size ;       // 文件大小（字节数）。 
 unsigned long i_mtime ;      // 修改时间（自1970.1.1:0 算起，秒）。 
 unsigned char i_gid ;        // 组id(文件拥有者所在的组)。 
 unsigned char i_nlinks ;     // 文件目录项链接数。 
 unsigned short i_zone [ 9 ];   // 直接(0-6)、间接(7)或双重间接(8)逻辑块号。 
 /* these are in memory also */ 
 struct task_struct * i_wait ; // 等待该i 节点的进程。 
 unsigned long i_atime ;      // 最后访问时间。 
 unsigned long i_ctime ;      // i 节点自身修改时间。 
 unsigned short i_dev ;       // i 节点所在的设备号。 
 unsigned short i_num ;       // i 节点号。 
 unsigned short i_count ;     // i 节点被使用的次数，0 表示该i 节点空闲。 
 unsigned char i_lock ;       // 锁定标志。 
 unsigned char i_dirt ;       // 已修改(脏)标志。 
 unsigned char i_pipe ;       // 管道标志。 
 unsigned char i_mount ;      // 安装标志。 
 unsigned char i_seek ;       // 搜寻标志(lseek 时)。 
 unsigned char i_update ;     // 更新标志。 
 }; 

The block number of the file on disk is stored in the inode and some other file description information. There can be multiple levels of disk block position guidance, which are divided into direct index and indirect index to obtain block position.

Table of contents

Find the data in the corresponding data disk block number according to the directory inode, which contains the inode disk block number of the subdirectory that exists in the directory. Search layer by layer and you can find the location of the final target directory.

Experimental instruction book: https://www.lanqiao.cn/courses/115/labs/575/document/