首页
关于
Search
1
2023 年保研经验贴 [计算机-末九Rank50%-入北计清深-北计直博]
1,115 阅读
2
FreeBSD Kernel-编译环境搭建
424 阅读
3
Linux Kernel-THP阅读分析[Hang up]
407 阅读
4
Linux Kernel-编译调试环境搭建
326 阅读
5
Linux Kernel-源码阅读环境搭建
312 阅读
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
论文
技术之外
开发
rcore-arm
登录
Search
yyi
累计撰写
49
篇文章
累计收到
2
条评论
首页
栏目
内核
源码分析
阅读笔记
Rust
语法
习题
读书笔记
深入理解计算机系统
论文
技术之外
开发
rcore-arm
页面
关于
搜索到
49
篇与
的结果
2023-08-13
Rust入门笔记 4.流程控制
Rust 入门笔记 —— 流程控制1. 分支rust 的 if/else 和 go 的类似即使是单句也不能缺少大括号条件可以不用括号包裹// Fill in the blanks fn main() { let n = 5; if n < 0 { println!("{} is negative", n); } else if n > 0 { println!("{} is positive", n); } else { println!("{} is zero", n); } } rust 的 if/else 结构可以用来赋值// Fix the errors fn main() { let n = 5; let big_n = if n < 10 && n > -10 { println!(", and is a small number, increase ten-fold"); 10 * n } else { println!(", and is a big number, halve the number"); n / 2 }; println!("{} -> {}", n, big_n); } 2 循环2.1 for这个 for 和 py 的 for 比较类似,是一个 foreach 型的fn main() { for n in 1..100 { // modify this line to make the code work if n == 100 { panic!("NEVER LET THIS RUN") } } println!("Success!"); } 当遍历数组的时候,循环变量会获得被遍历的所有权(但是基本类型还是复制的) let names = [String::from("liming"),String::from("hanmeimei")]; for name in names { // Do something with name... } println!("{:?}", names); // wrong! borrow of moved value: `names`所以我们可以用切片来遍历引用 let names = [String::from("liming"),String::from("hanmeimei")]; for name in &names { // Do something with name... } println!("{:?}", names);通过数组的iter.enumrate方法,可以获得(index, value)的 tuplefn main() { let a = [4, 3, 2, 1]; // Iterate the indexing and value in 'a' for (i,v) in a.iter().enumerate() { println!("The {}th element is {}",i+1,v); } }2.2 whilewhile 循环和 C 的 while 是一样的,不过条件还是可以不加括号// Fill in the blanks to make the last println! work ! fn main() { // A counter variable let mut n = 1; // Loop while the condition is true while n < 10 { if n % 15 == 0 { println!("fizzbuzz"); } else if n % 3 == 0 { println!("fizz"); } else if n % 5 == 0 { println!("buzz"); } else { println!("{}", n); } n += 1; } println!("n reached {}, so loop is over",n); } Rust也有 continue 和 break 关键字Rust 使用 loop 代替 while true// Fill in the blanks fn main() { let mut count = 0u32; println!("Let's count until infinity!"); // Infinite loop loop { count += 1; if count == 3 { println!("three"); // Skip the rest of this iteration continue; } println!("{}", count); if count == 5 { println!("OK, that's enough"); break; } } assert_eq!(count, 5); println!("Success!"); }loop是一个表达式,所以 break 可以用来返回值// Fill in the blank fn main() { let mut counter = 0; let result = loop { counter += 1; if counter == 10 { break counter * 2; } }; assert_eq!(result, 20); println!("Success!"); } 通过 label 的方式,可以精确地 break 或 continue 嵌套循环// Fill in the blank fn main() { let mut count = 0; 'outer: loop { 'inner1: loop { if count >= 20 { // This would break only the inner1 loop break 'inner1; // `break` is also works. } count += 2; } count += 5; 'inner2: loop { if count >= 30 { // This breaks the outer loop break 'outer; } // This will continue the outer loop continue 'outer; } } assert!(count == 30); println!("Success!"); } 3 模式匹配3.1 matchmatch有点类似于 C 的 switch,其基本形式如下match target { pattern1 => experssion1, pattern2 => { sth; expression }, _ => expression }match需要穷举出所有的可能,用_代表所有未列出的可能(类似于 default)match 的分支必须是表达式,且分支表达式的类型必须相同pattern 可以用 X|Y的形式表示,代表 X 或 Y// 填空 enum Direction { East, West, North, South, } fn main() { let dire = Direction::South; match dire { Direction::East => println!("East"), Direction::South|Direction::North => { // 在这里匹配 South 或 North println!("South or North"); }, _ => println!("West"), }; }match 本身也是一个表达式,因此可以用来赋值fn main() { let boolean = true; // 使用 match 表达式填空,并满足以下条件 // // boolean = true => binary = 1 // boolean = false => binary = 0 let binary = match boolean { true => 1, false => 0, }; assert_eq!(binary, 1); }match可以取出模式中绑定的值,还记得我们的 enum 类型么// 填空 enum Message { Quit, Move { x: i32, y: i32 }, Write(String), ChangeColor(i32, i32, i32), } fn main() { let msgs = [ Message::Quit, Message::Move{x:1, y:3}, Message::ChangeColor(255,255,0) ]; for msg in msgs { show_message(msg) } } fn show_message(msg: Message) { match msg { Message::Move{x: a, y: b} => { // 这里匹配 Message::Move assert_eq!(a, 1); assert_eq!(b, 3); }, Message::ChangeColor(_, g, b) => { assert_eq!(g, 255); assert_eq!(b, 0); } __ => println!("no data in these variants") } } 3.2 if letif let 对应于只有一个模式需要处理的情况,这时候用 match 需要写一个无用的 default下面两份代码等价fn main() { let o = Some(7); // 移除整个 `match` 语句块,使用 `if let` 替代 match o { Some(i) => { println!("This is a really long string and `{:?}`", i); } _ => {} }; } fn main() { let o = Some(7); if let Some(i) = o { println!("This is a really long string and `{:?}`", i); } }3.3 matches!Rust提供了一个宏 matches,把表达式和模式进行匹配,返回是否匹配let foo = 'f'; println!("{}", matches!(foo, 'A'..='Z' | 'a' ..= 'z')) // trueenum MyEnum { Foo, Bar } fn main() { let mut count = 0; let v = vec![MyEnum::Foo,MyEnum::Bar,MyEnum::Foo]; for e in v { // if e == MyEnum::Foo { // 修复错误,只能修改本行代码 if matches!(e, MyEnum::Foo) { count += 1; } } assert_eq!(count, 2); }
2023年08月13日
164 阅读
0 评论
0 点赞
2023-08-12
CSAPP 7.链接
本章的知识在《程序员的自我修养——链接、装载与库》中都有所提到,复习为主。可能有些说法和本书不同,如段Segment和节Section,希望读者自行甄别。链接:把各种代码和数据片段组合为一个单一文件的过程,这个单一文件可以被加载到内存并执行当下的链接主要分为静态链接和动态链接,静态链接于编译时执行,动态链接由装载或运行时执行。链接的重要意义之一就是增量编译、分离版本控制。我们需要更新部件的时候无需编译其他部分1 编译器驱动程序本章将以如下两段代码作为示例// main.c int sum(int *a, int n); int arr[2] = {1, 2}; int main() { int val = sum(arr, 2); return val; } // sum.c int sum(int *a, int n) { int i, s = 0; for(i = 0; i < n; i ++) { s += a[i]; } return s; }编译器驱动程序可以理解为编译各部分的封装控制器,对于gcc:gcc -o prog main.c sum.c它首先调用预处理器cpp,把源程序c文件翻译为ASCII码中间文件i文件main.i接下来,它调用C编译器cc1,把main.i翻译为一个ASCII汇编语言文件main.s然后运行汇编器as,把main.s翻译为目标文件main.o,同样的过程生成sum.o,它们是可重定位目标文件最后运行链接程序ld,把main.o、sum.o和一些其他的系统目标文件链接起来,创建一个可执行目标文件prog我们运行prog,shell会调用操作系统中的加载器,把prog的代码和数据复制到内存,把控制转移到prog的起始2 静态链接静态链接以可重定位目标文件和参数作为输入,生成一个链接后的可执行目标文件静态链接主要完成两个任务:符号解析:目标文件中会定义和引用符号,如全局变量,跳转的label、函数,连接器把它们的定义和引用进行关联重定位:链接器重排布代码和数据段的位置,并对符号引用进行修改,使他们真正指向对应的虚拟内存位置3 目标文件目标文件主要分为三种,前两种在上面提到过了,它们是可重定位目标文件:包含二进制的代码和数据,额可以在链接时与其它可重定位目标文件合并可执行目标文件:可以直接被复制到内存并执行共享目标文件:Shared Object so,可以在加载或运行时被动态加载进内存并链接Windows下使用PE格式,Mac系统使用Mach-O格式,Linux和Unix使用ELF格式4 可重定位目标文件ELF由ELF头、段表和各段组成ELF头中包括一些关键描述信息,如字大小、ELF版本、架构、字节顺序等,还有段表的条目大小和数量,帮助我们索引段表。一个典型的ELF包含如下几个段:.text: 已编译程序的机器码.rodata: 只读数据,比如switch的jt.data: 已初始化的全局和静态变量.bss: 未初始化、初始化为0的全局和静态变量,它们在目标文件中不占实际空间.symtab: 符号表,存放引用的全局变量和函数信息(但是对执行没有影响,可以通过strip去掉).rel.text:text中需要重定位的位置列表.rel.data: 同理.debug:调试符号表5 符号和符号表符号表包含文件定义和引用符号信息,包括如下三种:由模块定义、能被其它模块引用的全局符号,对应C的非静态函数和全局变量由其它模块定义、本模块引用的全局符号,也被称为外部符号,对应其它C文件的非静态函数和全局变量只被当前模块定义和引用的局部符号,包括static修饰的函数和全局变量,只在模块内部可见符号表存在于.symtab段,由Elf64_Symbol(显然,也会有32)数组组成typedef struct { int name; char type:4, binding:4; char reserved; short section; long value; long size; } Elf64_Symbol;name时字符串表中的字节偏移value是符号的地址,是距定义目标的setcion的起始位置的偏移size是目标的大小type区别数据和函数,binding标识符号是本地还是全局的此外还有三个特殊的伪节,在段表中不存在ABS:不该被重定位的符号UNDEF:未定义的符号COMMON:未初始化的全局变量,bss是未初始化的静态、初始化为0的全局或静态6 符号解析把每个引用与目标文件符号表中的符号定义关联起来局部符号:每个模块每个局部符号只能有一个定义,静态局部变量名字唯一全局符号:遇到不在当前模块定义的符号时,假设其它模块定义该符号,生成一个链接器符号表条目,由链接器处理6.1 多重定义的全局符号全局符号分强弱,函数和已初始化的全局变量是强符号,未初始化的全局变量是弱符号如下三条规则处理:不允许有重名强符号如果一个强符号和其它弱符号重名,选择强符号如果多个弱符号重名,随机选择一个显然,第二条和第三条规则将带来一些我们不想看到的错误,也正是由于这两条规则,才带来了bss和COMMON微小的区别,对于初始化为0或者静态变量,不会存在歧义,编译器会放在bss,对于没有初始化的全局变量,由链接器决定选择COMMON段的哪个。6.2 静态库链接编译系统提供一种机制:把相关的目标模块打包成一个文件,称为静态库,linux中后缀为.a的文件就是一系列目标模块的打包。相关库函数被编译为独立的目标模块,以供链接时使用,当用户目标文件和静态库链接时,链接器复制需要的模块来链接,这避免了程序员手动链接所有目标文件的复杂性,也避免了一次链接所有文件导致的空间浪费。举个例子,一个带printf调用的main.c,编译时gcc会自动给链接器加上libc.a的参数,ld会从libc.a中扫描到printf.o和其它printf.o引用的模块进行链接。6.3 链接器如何使用静态库链接器按顺序从左到右扫描目标文件和存档(archive, .a)文件,维护一个目标文件的结合E、一个未解析符号集合U、一个已定义符号集合D对于输入文件f,判断f是目标文件还是存档文件,如果是目标文件,添加到E,根据f修改U和D对于存档文件f,尝试匹配U中未解析符号,如果某个成员m定义了U中需要的符号,把m加到E中,修改U和D。如果完成之后,U非空,输出错误,否则合并、重定位E中的文件。注意,链接器按从左到右的顺序,意味着输入顺序很重要,库可以在命令行参数中重复,以满足依赖。7 重定位重定位以合并后的文件作为输入,为符号分配运行时地址重定位节和符号定义:相同的节进行合并,作为输出文件的对应节。将运行时的内存地址赋给对应的节和符号重定位符号引用:基于重定位条目修改所有的符号引用, 使得引用指向正确的运行时地址7.1 重定位条目汇编器生成目标文件,遇到不能确定最终地址的引用时,即生成一个重定位条目,代码的条目放在.rel.text,数据的放在.rel.datastruct { long offset; long type:32, symbol:32; long addend; }Elf64_Rela;上面这个数据结构就是重定位条目,每个条目表示一个需要重定位的引用。Elf有很多种重定位类型,我们只关心两种。offset:被修改的引用的段偏移symbol:被修改的引用指向的符号type:如何修改新的引用R_X86_64_PC32:32位PC相对地址的引用,比如call指令,PC地址是下条指令的起始地址R_X86_64_32:32位绝对地址的引用这两种类型支持“小型代码模型”,假设代码和数据的总体大小小于2G,因此可以使用32位相对地址访问。Gcc默认使用小代码模型。addend:一个常数,部分重定位需要使用它对被修改引用的值进行调整。7.2 重定位符号引用遍历需要重定位的节对于所有当前节对应的重定位条目,根据节地址和条目offset取出需要重定位代码的地址根据条目type,进入不同的分支若为相对引用,首先获取当前指令的运行时地址这里其实有点问题,取的到底是当前指令地址、当前指令的引用数据部分地址,还是下条指令的地址?根据代码的行为,我推测应该是当前指令的引用数据部分地址,再根据addend修正到下条指令的地址(事实上也是这样的)然后修改需要重定位的字节序列为符号地址+addend-当前指令运行时地址若为绝对引用,修改重定位的字节序列为符号地址+addend8 可执行目标文件对于可执行目标文件,其头部还包括了程序的入口点(Entry Point),记录了程序第一条指令的地址。程序头部表:描述可执行文件映射到内存的关系,记录了段在目标文件中的偏移、内存地址、对齐、目标文件中的段大小、内存中的段大小和访问权限(rwx)。9 可执行文件的加载shell通过execve函数调用加载器,将ELF的代码和数据从磁盘复制到内存(实际上,应该只是简单建立映射,复制的工作似乎会由访问时的页错误完成,书中可能会在后面提到)然后跳转到程序的第一条指令或者入口点。Linux程序都会有一个运行时内存镜像,其结构我们在第三章中应该介绍过了。10. 动态链接库静态库有一些缺点:静态库更新时,程序员需要显式的重新链接比如printf这种函数,会在上百个进程的text段中分别存放,造成极大的浪费在内存加载时,共享库加载到内存的任意地址,并和内存中程序链接起来。Linux中为so(shared object),Win下为DLL(Dynamic Link Lib),Mac下为dylib在给定的文件系统中,一个库只有一个so文件,所有引用该库的文件共享这个so的代码和数据(可读写的数据似乎应该是进程独立的,不知道这里书上这么说是指什么,可能是只代表只读数据)。动态链接的过程会发生在加载时、加载器首先运行动态链接器、之后再由动态链接器把控制交还应用程序11 应用程序中加载和链接共享库Linux提供了一个接口,允许程序运行时加载链接库#include <dlfcn.h> void *dlopen(const char *filename, int flag); void *dlsym(void* handle, char* symbol); int dlclose(void *handle);dlopen函数加载共享库filename,根据flag的标志决定何时进行符号解析。成功返回一个handle指针,出错为NULLdlsym根据handle和符号名字返回符号地址dlclose在共享库空闲时卸载该共享库。12 位置无关代码(每次读这块都头疼)PIC位置无关代码:可以加载而无需重定位的代码。共享库需要通过这种方式来实现“加载到任意内存位置”,因为重定位时我们需要知道符号地址,而共享库是运行时才能确定地址的。12.1 数据引用全局偏移量表GOT:这个表在数据段开始的地方,每个被模块引用的全局数据目标都会在GOT表中有一个8字节条目,加载时动态链接器重定位GOT表中的每个条目,使得它包含目标正确的绝对地址。由于代码段和数据段之间距离不变,编译器产生的代码引用GOT中的条目对数据进行间接访问。12.2 函数调用延迟绑定:把过程地址绑定推迟到低依次调用过程时。延迟绑定可以很好的避免加载时进行不必要的重定位,GNU通过GOT和过程链接表PLT实现这个机制。GOT时数据段的一部分,PLT时代码段的一部分。PLT:PLT的每个条目是16字节代码,PLT[0]跳转到动态链接器中。每个条目负责一个具体的函数在这里,GOT除了前几个为动态链接器保留的条目外,每个条目对应一个函数,也对应一个PLT条目。GOT条目初始时指向对应的PLT条目的第二条指令。PLT的一个条目是这样的:4005a0: pushq *GOT[1] 4005a6: jmpq *GOT[2] ---- 4005c0: jmpq *GOT[4] 4005c6: pushq $0x1 4005cb: jmpq 4005a0GOT4对应这下面这条PLT(下面称为PLT2)。GOT0和GOT1包含动态链接器模块的地址,GOT2是动态链接器在ld-linux.so的入口点当发生第一次调用时,程序进入PLT2,PLT2对应我们要调用的函数f第一条PLT通过GOT4进行跳转,初始时GOT对应PLT的第二条指令,因此又跳到下面那条pushq指令上把函数f的ID(1)压入栈之后,跳转到PLT0,PLT0通过GOT1间接的把动态链接器的参数压栈,通过GOT2跳转到动态链接器中,动态链接器利用这两个栈上参数确定f的运行时位置,把这个地址重写给GOT4,再把控制交还给f在这之后,控制第二次传递到PLT2时,它会跳转到GOT4上保存的地址,而这个地址正是f的地址。13 库打桩机制我理解就是hook,可以截获调用,执行自己的代码,Hook可以发生在编译、链接和运行时。其实就是把调用函数替换成我们自己的实现嘛。这里不赘述了14 处理目标文件的工具AR:创建静态库、插入删除列举提取成员strings:列出目标文件中可打印字符串strip:删除符号表信息nm:列出符号表中的符号size:列出节的名字和大小readelf:显示目标文件的完整结构objdump:显示目标文件所有信息,尤其是可以反汇编text中的指令。ldd:列出需要的共享库
2023年08月12日
146 阅读
0 评论
0 点赞
2023-08-11
Rust入门笔记 3.切片、向量与字符串
Rust入门笔记——切片、向量与字符串我在第一节中写了关于元组和数组的笔记,这章来扩充一些其他的复合类型1 切片还记得刚学 Go 的时候,我对切片和数组感到非常迷惑。切片和数组类似,但它本质上是对数据值的部分引用。切片的长度在编译时未知。切片是一个两个字的对象,第一个字是指向数据的指针,第二个是切片的长度,可用于借用数组的一部分。// 修复代码中的错误,不要新增代码行! fn main() { let arr = [1, 2, 3]; let s1: [i32] = arr[0..2]; let s2: str = "hello, world" as str; } // Sol : fn main() { let arr = [1, 2, 3]; let s1: &[i32] = &arr[0..2]; let s2: &str = "hello, world" as &str; }原来的[i32]和str都是切片类型,复习一下:切片是对数据值的引用。因此,切片不拥有数据的所有权,所以在尝试把切片赋值给变量的时候,变量的类型必须是对切片的引用。fn main() { let arr: [char; 3] = ['中', '国', '人']; let slice = &arr[..2]; // 修改数字 `8` 让代码工作 // 小提示: 切片和数组不一样,它是引用。如果是数组的话,那下面的 `assert!` 将会通过: '中'和'国'是char类型,char类型是Unicode编码,大小固定为4字节,两个字符为8字节。 assert!(std::mem::size_of_val(&slice) == 16); // orig : 8 }64 位系统下,一个字是 8bytes,所以一个切片是 16.fn main() { let arr: [i32; 5] = [1, 2, 3, 4, 5]; // 填空让代码工作起来 // let slice: __ = __; let slice: &[i32] = &arr[1..4]; assert_eq!(slice, &[2, 3, 4]); }2 字符串和字符串切片字符串字面量的类型是&str,标准库中的 String也是 Rust 的字符串类型str 就是字符串切片,我们前面声明字符串都是用String::from而不是直接写字符串,就是因为 let s = "hello" 中这个 s 会成为一个 &str 类型的变量。String 使用 UTF-8 编码,底层存储是 Vec<u8> 本节后面会提到 Vec。// 基础类型转换为字符串 let one = 1.to_string(); let slice = "slice".to_string(); let slice1 = String::from("this is &str") // 字符串追加 let mut s1 = String::from("base"); s1.push_str("str"); s1.push('c'); // 用 + 拼接 let s1 = String::from("Hello, "); let s2 = String::from("world!"); let s3 = s1 + "-" + &s2; // 字符串长度 let len = s1.len(); // 字符串截取 let sub = &s1[..2]; // 字符串替换 let s = String::from("Hello, dogs"); let s1 = s.replace("dogs", "world");// 修复所有错误,并且不要新增代码行 fn main() { let s = String::from("hello"); s.push(','); s.push(" world"); s += "!".to_string(); println!("{}", s) } // Sol fn main() { let mut s = String::from("hello"); s.push(','); s.push_str(" world"); s += &"!".to_string(); println!("{}", s) }// String只能和 &str进行拼接,并且会移动 String 的所有权。 fn main() { let s1 = String::from("hello,"); let s2 = String::from("world!"); // let s3 = s1 + s2; let s3 = s1.clone() + &s2; assert_eq!(s3,"hello,world!"); println!("{}",s1); }/* 填空并修复所有错误 */ fn main() { // 和其他语言一样,使用 \ 来转义 let raw_str = "Escapes don't work here: \x3F \u{211D}"; assert_eq!(raw_str, "Escapes don't work here: ? ℝ"); // 使用成对的 #" 、"# 来标定字符串,这样字符串中间就可以有"了 let quotes = r#"And then I said: "There is no escape!""#; println!("{}", quotes); // 如果希望在字符串中使用 # 号,可以如下使用: let delimiter = r###"A string with "# in it. And even "##!"###; println!("{}", delimiter); // 填空 let long_delimiter = r###"Hello, "##""###; assert_eq!(long_delimiter, "Hello, \"##\"") }str、&str 和 String 都是 UTF-8 字符串,可以用 u8 数组实现字节数组使用切片而不是索引访问字符串中的某个字符fn main() { let s1 = String::from("hi,中国"); // let h = s1[0]; let h = &s1[..1]; assert_eq!(h, "h"); // let h1 = &s1[3..5]; let h1 = &s1[3..6]; assert_eq!(h1, "中"); }3 向量向量是线性表,用Vec<T>表示,其中 T 是向量中存放的数据类型使用 push 方法追加单个元素使用 append 拼接。let vec: Vec<i32> = Vec::new(); let mut vec1 = vec![1, 2, 4, 8]; let vec2 = vec![32, 64]; vec1.push(16); vec1.append(&mut vec2); println!("{:?}", vec1); // 1, 2, 4, 8, 16, 32, 64使用 get 方法取出向量中的值let v = vec![1, 2, 4, 8]; v.get(0); // 这是一个 Option,后面流程控制会讲到当然也可以直接用索引let tmp1 = v[2]; let tmp2 = v[4]; // panic : index out of bounds
2023年08月11日
227 阅读
0 评论
0 点赞
2023-08-11
Linux Kernel-THP阅读分析[Hang up]
THP阅读分析[WIP]本文由于工作优先级原因暂时搁置,专心转向zswap// TODO[x] 配置源码阅读环境 第三部分-Linux源码阅读环境[ ] 理清如下几个先决问题[x] 什么是THP?THP要做什么?[ ] 为什么在虚拟化和嵌套页表的情况下,THP对TLB和TLB miss的优化更明显[x] THP和HP的相关性与区别[ ] THP和HugeTLB的相关性与区别[ ] 梳理THP相关核心流程[x] khugepaged守护进程如何工作?[x] khugepaged与huge_memory关系如何?[ ] huge_memory如何管理大页面,更一般的,理清下面两个问题[ ] 一次内存访问中发生了什么[ ] 一次页错误中发生了什么[ ] 梳理THP相关核心数据结构[ ] 理清如下几个逻辑问题[ ] 一个mm是管理一个进程内存空间的数据结构?核心代码:huge_memory.ckhugepaged.c官方文档:Transparent Hugepage Support概述 (暂时性的,不一定正确)Hugepage:现代操作系统使用的页式内存管理通常以4K为一个标准页面。在内存越来越大的今天,4K大小的页面对于使用大量内存的应用会产生一些问题,即大量产生的缺页中断。大量的缺页中断会带来两个问题 1. 进入内核的次数更多,带来更多的切换上下文开销。 2. 带来更多的TLB Miss,这也是Hugepage优化的主要问题。 对于问题a,大页带来的性能优化可能较低。一方面更大的页面要求在一次页错误中复制更多的内容。另一方面,进出内核的频率降低只在内存映射的生命周期内第一次访存时才重要。对于问题b,因为TLB的容量是有限的,更大的页面也代表着更少的页面,这会带来两点好处 1. TLB miss会变快 2. 一个TLB表项可以映射更大的内存,来减少TLB miss THP:THP和Hugepage的区别是:Hugepage是一个操作系统管理的、用户显式请求的机制,THP是操作系统自动的,对用户透明的行为。THP无需用户修改代码,具有更高的普适性。khugepaged负责合并,huge_memory.c中的函数负责管理透过现象看本质,这是一种用单页面大小和扫描时间换系统整体效率的机制部分概念/缩写介绍[WIP]页表条目现在的Linux内核采用四级页表目录的方式,分别为PGD :Page Global DirectoryPUD :Page Upper DirectoryPMD :Page Middle DirectoryPTE :Page Table Entry来复习下基础:每个进程都有自己独立的PGD,虚拟地址的从高到底的k位(典型的是9,最低12位是页框内地址,共48位的地址)分别用来索引PGD(在PGD中找到这个地址对应的PUD)、索引PUD、索引PMD、索引PTE进而找到自己对应的物理页框,最低几位在该页框中索引具体的内存地址。PUD、PMD和PTE的最低位是存储是否有效的标志位。其中PTE指示页框的是48...12这36位。THP运转流程-合并概述在系统启动时,内核会启动khugepaged守护进程,该进程启动一个核心循环,扫描系统中的页面,检测是否有多个连续的页面可以合并为一个透明大页(事实上,我认为不是任意连续2M页面,而必须是已经存在的PMD表项所对应的2M页面,待确认)。当它发现了可以合并的页面后进行大量的检查操作,然后进入合并函数。先进行申请和double-check,移除CPU中的TLB对应表项,复制巨页内容,更新相关参数。khugepaged如何初始化在hugememory.c中,有一个被subsys_initcall注册的初始化函数:hugepage_init, 该函数调用了两个khugepaged相关的函数:khugepaged_init 和 start_stop_khugepaged,在此处,我们暂时先不关心其他的初始化流程,把它们放到管理中去考虑,先只看khugepaged相关的部分khugepaged_init申请一段slab内存,初始化四个参数常量 HPAGE_PMD_NR 根据它的定义,我推测它在数量上和一个HPAGE所含的一般页面数量相等(512)khugepaged_pages_to_scan : 每次扫描页面的数量,默认为 512 * 8khugepaged_max_ptes_none:最多有多少个页表项是空页面(存疑)khugepaged_max_ptes_swap:最多有多少个页面在swap中未被映射,默认是512/8khugepaged_max_ptes_shared:最多有多少页面是被共享的,默认是512/2start_stop_khugepaged获取互斥锁,检测hugepage是否开启了,若开启了则检查static变量khugepaged_thread,存在则关闭该线程启动一个内核线程,目标函数为khugepaged函数,该函数为khugepaged扫描的核心循环若有错误,清理并释放锁khugepaged如何扫描khugepaged设置一些状态,把当前线程优先级变低,进入循环如果收到KTHREAD_SHOULD_STOP,则退出调用khugepaged_do_scan函数调用khugepaged_wait_work函数,进入等待根据khugepaged_scan_sleep_millisecs,转换成中断次数,进入等待获取自旋锁,进行一些清理工作,释放锁khugepaged_do_scan该函数有一个参数:khugepaged_collapse_control,只透传给下层初始化一些变量progress:记录THP扫描进度pages:读取init中初始化的khugepaged_pages_to_scanwait:布尔量,用于下面过程的重试result:记录扫描结果的状态调用lru_add_drain_all函数,把脏页从LRU列表干掉(加到写回缓冲区)进入一个无限循环,降低自己的优先级检查是否要退出获取一个自旋锁如果当前kugepaged_scan的mm_slot字段为空,累加“pass_through_head”计数器如果kugepaged_scan的mm_head不为空,且pass_through_head < 2(我理解就是第一次进入,记录一个TODO,为什么要把0的情况算进去,即什么情况下存在刚进入do_scan函数但是mm_slot不为空)调用kugepaged_scan_mm_slot函数,并把结果累加给progress变量,更新result变量kugepaged_scan_mm_slotstatic unsigned int khugepaged_scan_mm_slot(unsigned int pages, int *result, struct collapse_control *cc) __releases(&khugepaged_mm_lock) __acquires(&khugepaged_mm_lock)该函数是scan步骤的关键函数,它接受的参数包括:pages:要扫描的页数result:结果指针cc:透传来的 collapse_control结构该函数首先进行一些初始化与验证操作,包括对参数与锁的断言,对 result 的初始化检测是否已经有正在进行的扫描,如果有,获取相应的 mm_slot和 slot(扫描当前头部未扫描完的进程),如果没有,初始化一组新的 slot 和 mm_slot(扫描下一个进程)khugepaged如何合并kugepaged_collapse_pte_mapped_thps进行一些验证操作与锁的获取便利当前 slot 的所有 Hugepage 的页表项,调用collapse_pte_mapped_thp函数对这些页表项进行合并操作。collapse_pte_mapped_thpint collapse_pte_mapped_thp(struct mm_struct *mm, unsigned long addr, bool install_pmd)该函数有三个参数● mm:将要被聚合的进程地址空间● addr:要发生聚合的地址● install_pmd:布尔,决定是否应当设置一个 PMD 表项该函数检测是否一个 PMD 中的所有 PTE 表项都指向了正确的 THP,如果是的话,撤销相关的页表项,这样 THP 可以触发一个新的页错误,使得使用一个 huge PMD 映射这个 THP把地址按掩码对齐,获取当前地址对应的 vma,获取锁。调用find_pmd_or_thp_or_none 查找页表中对应当前地址的 PMD 或是 THP 或是空指针。如果当前页面已经被 PMD 映射,返回。如果所有检测都没有命中,返回 SCAN_SUCCEED。// TODO:这些检测都是什么检查获取的 vma 是否正确,如果不正确,返回 VMA_CHECK,表示需要检查虚拟内存区域到此为止,我门已经成功的把页缓存中的本地页面替换成了单个的 hugepage,如果 mm 触发缺页错误,当前 hugepage 就会被一个 PMD 映射,而不考虑 sysfs 中对 THP 的设置是什么样的。检查是否存在使用 userfaultfd_wp的情况,如果是,返回通过 find_lock_page 尝试获取页面,且验证页面是一个 Hugepage,并且检测页面是否为一个复合页面。如果不是 Hugepage 或者页面复合阶数和 HPAGE_PMD_ORDER不相等,则 drop_hpage。接下来操作页表,首先获取当前 vma 的锁、当前文件映射的锁、当前虚拟地址对应 PTE 的锁。STEP1:检测是否所有的已映射页表项指向了期望的 Hugepage● 遍历当前 PMD 对应的所有 PTE● 如果当前 PTE 是空,跳过● 如果当前 PTE 没有物理页映射,发生了非法情况,终止(swapped out)● 获取 PTE 指向的物理页面 ● 检测是否是设备内存,如果是,WARN,并设置页面指针为 NULL● 检测 PTE 指向的页面和期望的巨页对应的小页面是否一致,不一致则终止● 累加计数器STEP2:对小页面的反向映射进行调整● 遍历当前 HugePage 的页表项● 如果当前 PTE 是空的,跳过● 获取当前物理页,检测是否是设备内存,若是 WARN 并 abort● 调用 page_remove_rmap,从页的反向映射表中移除页面与 VMA 的映射关系● 解锁 PTE 的映射STEP3、4:设置正确的引用计数、移除 PTE 条目● 如果 count 不是 0,说明签名的步骤中找到了一些映射到 hpage 的 PTE 条目,折叠后会删除 PTE,所以更新 hpage 的引用计数、把 vma 的 mm 计数器也减掉相应的数量● 如果有匿名 vma,获取锁,然后调用 collapse_and_free_pmd折叠并释放 haddr 处的 PMD 条目STEP5:● 根据 install_pmd 参数的情况,决定是否要安装 PMD,若 PMD 安装成功或者不需要,则返回 SCAN_SUCCEEDcollapse_and_free_pmdhugepage_vma_checkkhugepaged的重要数据结构khugepagd_scanstruct khugepaged_scan { struct list_head mm_head; struct khugepaged_mm_slot *mm_slot; unsigned long address; }; 这个数据结构是一个指引扫描的“光标”,跟踪khugepaged扫描时的状态。该数据结构只会有一个全局实例。mm_head:要扫描的mm的头部,维护需要扫描内存区的链表mm_slot:指向当前正在扫描的kuhugepaged_mm_slotaddress:是mm_slot内下一个即将被扫描的地址khugepaged_mm_slotstruct khugepaged_mm_slot { struct mm_slot slot; /* pte-mapped THP in this mm */ int nr_pte_mapped_thp; unsigned long pte_mapped_thp[MAX_PTE_MAPPED_THP]; };这个数据结构用来跟踪正在扫描的每个内存区域slot:依赖的一个外部数据结构,实现了从mm到mm_slot的哈希查找nr_pte_mapped_thp:表示在该mm中已经被映射的THP的数量pte_mapped_thp:存放该mm中已映射的THP的地址在我的理解中,khugepaged_scan指导scan工作,而其中的mm_slot指向当前正在被扫描的那个进程的mm_slot,(一个进程通常只有一个kugepaged_mm_slot, 暂不确定什么情况下会有多个)THP运转流程-管理
2023年08月11日
407 阅读
0 评论
1 点赞
2023-08-11
Rust入门笔记 2.函数、所有权与复合类型
Rust入门笔记 —— 函数,所有权与复合类型1 结构体与枚举1.1 结构体先讲结构体是因为后面方法需要结构体做支撑,其实这种用例子解释语法的方式,还是需要学过其他语言。因为前期肯定会用到后面才讲的东西结构体主要有三种类型tuple : struct Pair(i32, f32)经典的 C struct,当然,结构体也是可以复合的struct Point { x: f32, y: f32 }单元(Unit)结构体:没有字段结构体和 C 一样,用.+field_name引用变量let point: Point = Point{ x: 10.3, y: 0.4 }; // 这里的 x 和 y 并不能省略 println!("coord : {}, {}", point.x, point.y); let point_ext: Point = Point{ x: 1.2, ..point}; // 使用这种方法继承字段 let pair = Pair(1, 0.1) // 元组类型的就可以省略啦(不省略也没名字)1.2 枚举用 enum 关键字声明一个枚举,相比与 C,rust 的枚举有更多功能,任何对于结构体合法的内容也可以用于 enumenum WebEvent { PageLoad, PageUnload, // Unit KeyPress(char), Paste(String), // Tuple Click { x: i64, y: i64}, // 标准的结构 } // 使用这种 match 结构就可以引用枚举字段及其内容 fn inspect(event: WebEvent) { match event { WebEvent::PageLoad => println!("page loaded"), WebEvent::PageUnload => println!("page unloaded"), // Destructure `c` from inside the `enum` variant. WebEvent::KeyPress(c) => println!("pressed '{}'.", c), WebEvent::Paste(s) => println!("pasted \"{}\".", s), // Destructure `Click` into `x` and `y`. WebEvent::Click { x, y } => { println!("clicked at x={}, y={}.", x, y); }, } }2 函数2.1 函数与返回值Rust的函数以 fn fn_name(arg_list) -> ret_type {body} 定义,函数的最后一行是返回值Rust函数名称风格是snake_case(区别于Go的CamelCase)Rust不要求被调用的函数必须在调用者之前定义,只要有定义即可Rust的函数返回值可以是函数体尾部的表达式,也可以显式的使用return语句返回()类型的函数,返回值类型声明可以省略fn main() { // 不要修改下面两行代码! let (x, y) = (1, 2); let s = sum(x, y); assert_eq!(s, 3); } fn sum(x : i32, y:i32) -> i32 { // original : (x, y:i32) { return x + y; // original : x + y; } 上述答案中第10行可以是 x + y,可以是return x + y;,但是不能是 x + y; 因为分号会让表达式变为语句,语句的值是()// 用两种方法求解 fn main() { never_return(); } fn never_return() -> ! { // 实现这个函数,不要修改函数签名! }这题没有想到答案,两种方法分别可以是fn never_return() -> ! { panic!("I return nothing!") } fn never_return() -> ! { loop{} }其实感觉有点扯淡还有类似于成员函数的概念:把函数和类型加以关联,Rust 中用关联函数和方法实现,我门后面再讲2.2 函数体表达式我斗胆猜测这就是 Rust 中匿名函数的表现,Rust 使用大括号来编写一个较为复杂的表达式let y = { let x = 3; x + 1 }; // y == 4可以看到,大括号中的内容和函数中的内容一致,但是函数体表达式不能使用 return3 所有权、引用和借用C 使用手动管理内存,开发者申请释放,这常常造成资源浪费和内存泄漏。Java 的 JVM 会负责在运行时回收内存,然而 GC 会导致运行效率的下降。Rust 采用所有权机制,让它在编译阶段能更有效的分析内存资源。Rust 中的每个值都有一个变量,称为其所有者一个值同时只能有一个所有者当所有者不在程序运行范围内时,该值会被删除3.1 变量范围{ // 无效,未声明 let s = "str"; // 可用 } // 无效上面这段代码描述了 s 这个变量的作用范围,它代表变量的可行域,默认从声明变量开始有效,直到变量域结束。变量和数据的交互方式主要有移动 Move 和克隆 Clone3.2 所有权移动与克隆移动,即直接复制,对于基本数据类型(bool,整形、浮点等)Rust 会在栈上复制一份。let x = 5; let y = x;在这样的操作后,栈上会有两个 5但是如果数据在堆上,只会复制指针,类似于浅拷贝。let s1 = String::from("str"); let s2 = s1; println!("{}", s1); // Wrong! borrow of moved value: `s1`当 s2 被绑定到堆上的 "str" 时,s1 就已经失效。为了降低程序运行成本,默认的情况下非基本类型采用移动,但是如果需要复制一份数据,需要使用克隆let s1 = String::from("str"); let s2 = s1.clone(); println!("{}, {}", s1, s2);此时堆中会有两个 str,分别绑定给 s1 和 s2,释放的时候也会分别释放。对于练习:fn main() { // 使用尽可能多的方法来通过编译 let x = String::from("hello, world"); let y = x; println!("{},{}",x,y); } // 显然,编译会因为 x 失效而失败 // Sol1 : let y = x.clone(); // Sol2 : let x = "hello, world"; // 在栈上,会移动所有权转移的时候,可变性也会跟着改变fn main() { let s = String::from("hello"); let mut s1 = s; s1.push_str(" world"); println!("{}", s1); }涉及函数的情况调用函数传入的参数,其所有权会被传递给 callee,因此会失效。但是基本类型不会失效,道理和上面一样。换句话说,传参和移动的效果是一样的。// 不要修改 main 中的代码 fn main() { let s1 = String::from("hello, world"); let s2 = take_ownership(s1); // s1 在此处失效 println!("{}", s2); } // 只能修改下面的代码! fn take_ownership(s: String) { println!("{}", s); } // Sol1 fn take_ownership(s: String) -> String { println!("{}", s); s } 对于返回值,其所有权会被移动出函数,返回到调用函数的地方,不会被释放fn main() { let s = give_ownership(); println!("{}", s); } // 只能修改下面的代码! fn give_ownership() -> String { let s = String::from("hello, world"); // 将 String 转换成 Vec 类型 let _s = s.into_bytes(); s } // sol1 : let _s = s.clone().into_bytes(); // sol2 : let _s = s.as_bytes();上面这道题中,s 的所有权在into_bytes方法中被移动,因此不能在返回处使用。但是修改之后,s 的所有权被移交回 main,所以 main 中可以使用。引用和租借引用类似于取指针,和 C++ 里面的引用感觉差不多fn main() { let s = String::from("hello, world"); print_str(&s); // print_str(s); println!("{}", s); } fn print_str(s: &String) { // fn print_str(s: String) { println!("{}",s); }在变量的值被引用的时候,变量不会被认定为无效。引用不会获得值的所有权,只会 租借 值的所有权,未显式声明可变租借的所有权不可以修改数据引用本身也是一个类型,它存的值其实就是被引用的值的地址。fn main() { let s1 = String::from("hello"); let s2 = &s1; let s3 = s1; println!("{}", s2); } // 错误,s2 只租借了 s1 的所有权,当 s1 的所有权失效,s2 租借的也失效了fn main() { let s1 = String::from("run"); let s2 = &s1; println!("{}", s2); s2.push_str("oob"); // 错误,禁止修改租借的值 println!("{}", s2); }fn main() { let mut s1 = String::from("run"); // s1 是可变的 let s2 = &mut s1; // s2 是可变的引用 s2.push_str("oob"); println!("{}", s2); }可变引用不允许多重引用,但是不可变引用可以。
2023年08月11日
198 阅读
0 评论
0 点赞
1
...
7
8
9
10