ELF 文件格式浅析

2022-05-27

本文是作为 Rust 的练手项目 rself(https://github.com/chengzhycn/rself) 的背景知识记录。rself 使用 Rust 重新造了一个 readelf 的轮子。

ELF全称为Executable and Linkable Format，是Linux上可执行文件的通用文件格式。主要有三种类型的ELF文件：

Relocatable file: 存储用于和其它对象文件链接的代码和数据，创建一个可执行文件或者共享对象文件
Executable file: 存储的是用于执行的程序。它指定了exec如何创建一个程序的进程镜像
Shared object file: 存储了在两种语义下用于链接的代码和数据。第一种是让链接器将共享对象文件和其它的可重定位文件/共享对象文件一起创建一个新的对象文件；第二种是动态链接器将它和可执行文件以及其它的共享对象一起创建一个进程镜像。

ELF构成

ELF主要由如下几个部分组成：

ELF Header: 位于文件的起始，描述了整个文件的组织结构
Sections/Segments: 存储了指令、数据、符号表、可重定位信息等。sections 是这段数据在链接时的表现；segments 是数据在执行时的表现。
Program Header Table: 用于告诉系统如何创建一个进程镜像。对于可执行程序，Program Header Table是必须的，但是对于可重定位文件就不需要了。
Section Header Table: 存储描述文件中sections的信息。每个section都在这个表中有一个条目，存储了如section name, section size等信息。用于链接的文件必须得有Section Header Table，其它的对象文件可有可无。

d02c13c1fa4bd228f698cf355ec47377_MD5

上面的图中虽然描述文件各个部分的位置，但实际上只有ELF Header的位置是固定的，其它的部分在文件中的位置都在ELF Header中指定。

ELF Header

#define EI_NIDENT 16

typedef struct {
        unsigned char   e_ident[EI_NIDENT];
        Elf32_Half      e_type;
        Elf32_Half      e_machine;
        Elf32_Word      e_version;
        Elf32_Addr      e_entry;
        Elf32_Off       e_phoff;
        Elf32_Off       e_shoff;
        Elf32_Word      e_flags;
        Elf32_Half      e_ehsize;
        Elf32_Half      e_phentsize;
        Elf32_Half      e_phnum;
        Elf32_Half      e_shentsize;
        Elf32_Half      e_shnum;
        Elf32_Half      e_shstrndx;
} Elf32_Ehdr;

typedef struct {
        unsigned char   e_ident[EI_NIDENT];
        Elf64_Half      e_type;
        Elf64_Half      e_machine;
        Elf64_Word      e_version;
        Elf64_Addr      e_entry;
        Elf64_Off       e_phoff;
        Elf64_Off       e_shoff;
        Elf64_Word      e_flags;
        Elf64_Half      e_ehsize;
        Elf64_Half      e_phentsize;
        Elf64_Half      e_phnum;
        Elf64_Half      e_shentsize;
        Elf64_Half      e_shnum;
        Elf64_Half      e_shstrndx;
} Elf64_Ehdr;

ELF header通常由一个Elfxx_Ehdr结构体表示。它存储了当前二进制文件的一些元数据：

[Read more]

Linux 进程调度

2022-01-11

#Linux #Schedule

总体来说，调度主要解决两类问题：

什么时候调度
调度的目标是谁而一个优秀的调度系统，可以从如下几个指标判断：
fast process response time
good throughput for background jobs
avoidance of process starvation
reconciliation of the needs of low- and high- priority processes

Linux调度基于分时（Time-Sharing）：多个进程共享同一个CPU，CPU运行时切分成多个时间片。分时技术依赖于timer interrupt，对进程来说是透明的。

Linux进程是可抢占的。当进程切换到TASK_RUNNING状态，内核检查其动态优先级是否比当前运行的进程的优先级高。如果更高，当前执行的进程中断掉，调度器切入，选择另外一个进程运行（通常是刚刚切换成runnable的进程）。当进程的时间片消耗完毕时，进程也是可被抢占的。当前进程struct thread_info中的TIF_NEED_RESCHED被设置，timer interrupt handler终止后，scheduler切入。

一个被抢占的进程并不是被暂停，它还维持在TASK_RUNNING状态，只不过不再使用CPU。

调度算法

Linux 2.6版本之前的调度算法很简单，进程切换时，内核扫描runnable进程列表，计算它们的优先级，选择“最优”的进程运行。这种算法的问题是切换时的时间开销会随着进程数目的增多呈线性增长。

调度策略：

SCHED_FIFO
SCHED_RR
SCHED_NORMAL

O(1) Scheduler

基于Linux-2.6.12版本。

优先级

Linux 2.6.12 内核里，优先级表示分为用户态和内核态。用户态优先级就是我们常用的nice值。取值范围[-20, 19]。内核态优先级被称作静态优先级（static priority），取值范围是[0, 139]。其中，[0, 99]是Real-Time Process，[100, 139]对应用户态nice值。

在静态优先级外，真正发挥作用的是动态优先级（dynamic priority）。动态优先级实际上是静态优先级加上了一个运行时补偿（bonus）： $$ dynamic_priority = max(100, min((static_priority - 5 + bonus), 139)), bonus \in [0, 10] $$

[Read more]

Linux 进程

2021-11-30

#Linux

进程和轻量级进程

在Linux内核中，进程/线程对应的数据结构是task_struct，定义在include/linux/sched.h中。

线程在Linux中的实现是 Naive POSIX Thread Library 。在内核眼中，Linux的线程实际上也是一个进程（task_struct），区别是线程的“进程”共享了地址空间、文件描述符等，称作==轻量级进程==。因此，Linux的线程也是独立的调度单元，是可以分别在不同的CPU上同时运行的。原生的Linux 线程（2.6版本内核之前）因为只实现在了用户态，所以，即使是一个多线程程序，对于内核来说只能看到一个进程，这些线程就只能在一个CPU上运行，对于多核多线程来说是很致命的。

从实现的角度，Linux的线程（LWP）是通过pthread库创建/使用的。而进程和线程的创建都调用了clone()系统调用（kernel/fork.c ）。区别是两者使用了不同的flags。

进程管理

进程状态

TASK_RUNNING: The process is either executing on a CPU or waiting to be executed
TASK_INTERRUPTIBLE: The process is suspended (sleeping) until some condition becomes true.
TASK_UNINTERRUPTIBLE: Like TASK_INTERRUPTIBLE, except that delivering a signal to the sleeping process leaves its state unchanged.

PID

PID用来区分不同的进程结构体。Linux中最大PID数目可以在/proc/sys/kernel/pid_max中查看。

每个进程/轻量级进程都分配有一个唯一的PID。但是对于同一进程中的线程来说，我们拿到的是进程ID确是相同的，这是怎么实现的呢？

Linux为了兼容POSIX标准，利用了线程组（thread group）这一概念。所有的线程都会把线程组里面第一个线程的PID存在tgid字段内。==getpid()系统调用返回的实际上是tgid的值。==

/**
 * sys_getpid - return the thread group id of the current process
 *
 * Note, despite the name, this returns the tgid not the pid.  The tgid and
 * the pid are identical unless CLONE_THREAD was specified on clone() in
 * which case the tgid is the same in all threads of the same group.
 *
 * This is SMP safe as current->tgid does not change.
 */
SYSCALL_DEFINE0(getpid)
{
    return task_tgid_vnr(current);
}

bitmap管理PID

IDR管理PID

PID: replace pid bitmap implementation with IDR API commit, commit

进程切换

==TLDR：进程在调用schedule()方法时，将当前进程运行的寄存器信息保存在task_struct->thread_info内，同时从进程B中的task_struct->thread_info中加载B运行时的寄存器信息。==

[Read more]

Go channel 实现

2021-09-12

#Go

Go的Channel在runtime里面是一个hchan的结构体，每次我们make一个新的channel时，runtime从heap内分配一个hchan结构体管理channel。

type hchan struct {
    qcount   uint           // total data in the queue
    dataqsiz uint           // size of the circular queue
    buf      unsafe.Pointer // points to an array of dataqsiz elements
    elemsize uint16
    closed   uint32
    elemtype *_type // element type
    sendx    uint   // send index
    recvx    uint   // receive index
    recvq    waitq  // list of recv waiters
    sendq    waitq  // list of send waiters

    // lock protects all fields in hchan, as well as several
    // fields in sudogs blocked on this channel.
    //
    // Do not change another G's status while holding this lock
    // (in particular, do not ready a G), as this can deadlock
    // with stack shrinking.
    lock mutex
}

qcount：当前channel queue内的element数目，当qcount等于dataqsiz时，表示channel buffer已经满了，send channel会被阻塞；
dataqsiz：channel的buffer大小，也就是我们在make时设定的值。dataqsiz在channel创建后不会再变动，因此channel的buffer是不会动态扩容的；
buf：buffered channel缓存elements的内存地址。是一个数组实现的环形队列；
elemsize：element类型大小；
closed：channel是否已经被关闭，防止关闭已经关闭的channel；
elemtype：channel element 类型；
sendx：buffer中下一个生产的element的index；
recvx：buffer中下一个消费的element的index；
recvq：阻塞的接收channel，是一个sudog的链表
sendq：阻塞的发送channel，是一个sudog的链表

当buffer没有满时，send channel发送elements时直接把elements放在buf内，增加sendx和qcount；当buffer满时，send channel被阻塞，并加入到sendq链表内，等待被唤醒；

[Read more]

Rust: Concurrency

2021-06-27

#Rust

为什么Rust不做green threading

Send 和 Sync

Rust中几乎所有的并发特性都是标准库或者第三方库提供的，真正由Rust语言本身提供的很少。而std::marker中的traits Send和Sync算是其中一个。

**实现Send的类型值的所有权可以在线程间传递。**Rust中绝大多数类型都实现了Send，但也有些例外，如Rc<T>：因为如果将Rc<T>的拷贝值的所有权在多个线程中传递，Rust无法保证Rc<T>引用值的正确性。

实现Sync的类型表示该类型值可以在多个线程中被引用。也就是说，如果&T实现了Send，那么类型T就是Sync。

Send和Sync markers其实就是将其他语言中的一些潜规则显式地标明出来，让编译器提前检查出代码中的隐患。

线程原语

use std::thread;

fn main() {
    let v = vec![1, 2, 3];

    let handle = thread::spawn(move || {
        println!("Here's a vector: {:?}", v);
    });

    handle.join().unwrap();
}

thread::spawn新建一个线程，执行传递的闭包函数，返回一个JoinHandler，可以在主线程中调用join等待子线程结束。move用于强制闭包获取它使用的变量的所有权。

我们可以看看thread::spawn的实现：

#[stable(feature = "rust1", since = "1.0.0")]
pub fn spawn<F, T>(f: F) -> JoinHandle<T>
where
    F: FnOnce() -> T,
    F: Send + 'static,
    T: Send + 'static,
{
    Builder::new().spawn(f).expect("failed to spawn thread")
}

spawn的入参和返回值都实现Send，同时其生命周期为'static。这是因为在多线程中，每个线程的执行周期不是同步的。父线程或者子线程的结束都会导致入参或者返回值的生命周期不满足Rust的约束条件。

[Read more]

Posts for: #Learning

ELF 文件格式浅析

ELF构成

ELF Header

Linux 进程调度

调度算法

O(1) Scheduler

优先级

Linux 进程

进程和轻量级进程

进程管理

进程状态

PID

bitmap管理PID

IDR管理PID

进程切换

Go channel 实现

Rust: Concurrency

为什么Rust不做green threading

Send 和 Sync

线程原语