链接
Linux source code (0.01) - Bootlin !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! LINUX初版!!
马洛克教程 (danluu.com) malloc教程!!!
Build Your Own Text Editor (viewsourcecode.org) 宝藏!!! 手把手叫你些编译器
第2章信息的表示和处理
正码、反码、补码
大端序和小端序
日常生活多为小端序, 0x000011为例:
小端序: 110000
大端序: 000011
浮点计算
#define DEMO_1
int main()
{
#ifdef DEMO_1
assert(+0.==-0.); // V
assert(1.0/+0.==1.0/-0.); // 正无穷 !=无穷 // X
#endif
return 0;
}
注意:浮点数加法和乘法不满足结合律
c union 共用体
C/C++ union 使用教程 (常见操作与缺陷) - 知乎 (zhihu.com)
旁路攻击
不是直接攻击系统,而是通过一些间接的信息来得到一些数据。
例如:
你访问一个需要权限的东西,现代cpu在等待权限结果下来时先进行部分操作但不给你,后来发现你无权访问,再将这些数据删除。
而有人可以通过缓存得到这些信息
你尝试了几个密码,您能精确的发现处理函数的执行时间不一样,可以得到哪几位错误
第3章程序的机械级表达
ISA:指令集架构 intel、ARM、RISC-V
Mircoarchitecture:指令集架构的具体表现形式
Machine Code:
Assembly Code:
冯诺依曼架构:
代码、数据、栈,从机器的角度来看,都一样,都是被编码的字节序列,即程序存储型计算机。
Prologue(进入函数)和EPilogue(退出函数)
Code Injection Attacks(代码注入攻击)和gets()漏洞
char buf[64];
gets(buf); // 如果用户输入一个超出范围的数,他会写入后面的地址,如果控制精确,刚好后面的返回地址被有意设为某个函数的地址。就会跳入哪个函数
虚拟地址可以防止
ret2libc攻击
编译器层面:缓冲区溢出的检测,金丝雀
ROP攻击
第4章 处理器体系结构
RISC和CISC(精简指令集和复杂指令集)
粉丝前端,蓝色后端
最开始拿到指令时,还是CISC的风格,处理后到蓝色部分后端,已经是SISC-like风格了。
大小核技术
big.LITTLE
结构冒险、数据冒险、控制冒险
第5章 优化程序性能
编译器聪明且保守,有时候你写的程序会阻止编译器做优化
影响性能的因素
算法
编程语言
编译器
指令集架构
提示:没有什么可以修正一个愚蠢的算法,所以算法是至关重要的
编译器优化
Front End、Middle End、Back End
编译器不敢帮你做这个优化
int fn (int *a, int *b)
{
*a = 3;
*b = 4;
return (*a + 5);
}
// 编译器会把以上代码优化成下面的样子么?不会!谁知道程序员会不会这么调用 f(&x,&x);
int fn (int *a, int *b)
{
*a = 3;
*b = 4;
return (3 + 5);
}
// 但是你可以帮助编译器,使用C99的restrict类型限定符,但还是需要开发者确保两个指针不指向同一数据
// https://gcc.gnu.org/onlinedocs/gcc/Restricted-Pointers.html
int fn (int *__restrict__ a, int *__restrict__ b)
{
*a = 3;
*b = 4;
return (*a + 5); // 这里会被优化为 return (3 + 5)
}
第6章存储器层次结构
CPU的处理速度和内存的访问速度差距越来越大,如何跨越CPU和内存之间的鸿沟?
基于SRAM技术的缓存
固态硬盘SSD
可以用来部分弥补磁盘和内存之间的速度瓶颈,它利用了Flash闪存技术,闪存就是一种特殊的、以块擦写的EEPROM
为什么缓存会有用呢?
时间局部性:最近被访问的数据很可能再次被访问
空间局部性:被访问数据的附件空间也很可能被访问
随着数据越来越大,增加一级缓存大小的性价比已经很低
一级缓存(L1 Cache)和内存之间又增加一层访问速度和成本介于两者之间的二级缓存(L2 Cache),后来又增加了三级缓存(L3 Cache),甚至是四级缓存(L4 Cache),最后形成了金字塔形的存储器层次结构(缓存命中率已经达到惊人的95%以上!!!)
真实的Intel Core i7 CPU的缓存结构示意图
Cache是如何存放数据?
Direct Mapped(直接映射),Fully Associative(任意的映射),,n-way associative
Cache不命中的场景?
Compulsory miss(强制性不命中),如:首次访问
Capacity miss(容量原因的不命中),缓存行太小不足以存储内容
Conflict miss(冲突原因不命中)
由于会发生冲突,某些时候就需要把一部分缓存行驱逐出去缓存,那么到底选哪个倒霉蛋呢?最常见的Cache替换算法有:随机(Random),先进先出(FIFO),最近最少使用(LRU)
提示:需要考虑缓存行的大小,现代CPU的缓存行一般是64个字节(也有使用128个字节的),在Cache的总容量固定且使用组关联的的情况下,缓存行越大,那么能够存放的组就越少,这里需要做一个权衡。
Cache 的写策略有哪些?
Cache命中时的写策略 ① 写穿透(Write Through):数据同时写入Cache和主存 ② 写返回(Write Back):数据只写入Cache(标记为dirty),仅当该数据块被替换时才将数据写回主存
Cache不命中时的写策略 ① 写不分配(Write Non-Allocate):直接将数据写入主存 ② 写分配(Write Allocate):将该数据所在的块读入Cache后,再将数据写入Cache
典型情况:① Write-‐through + No-‐write-‐allocate ② Write-‐back + Write-‐allocate
第7章链接
静态链接和动态链接
第8章 异常控制流
导读
从高层角度理解一些重要概念:
Process Management/Scheduling,
Memory Management,
File System,
Interrupts,
Device drivers,
Networking,
IPC ...
推荐学习Linux操作系统。
设计调度器的时候会考虑哪些问题?
如何利用资源?
一个资源一个资源,还是以时间片的方式
任务怎么样组织?
以一个全局队列加锁的方式
以一个单独的队列
数据结构怎么设置?
算法
round robin
CFS(完全公平)
内核分类
微内核
宏内核
混合内核
程序和进程
用户空间和内核空间
第9章虚拟内存
为什么需要虚拟内存?
内存碎片化的问题
有内存保护,物理内存有缺点,可能被用户空间肆意滥用,而虚拟内存不会
内存空间不够用
(计算机科学的任何问题都可以通过增加间接层解决)
有足够的空间却不能放下
LAZY Allocation(延迟分配)
你申请内存马上用的可能性很低,到用的时候在分配空间性能更好
Linux的内核空间
内核的逻辑地址
内核的虚拟地址
MMU(Memery Management Unit内存管理单元)
OOM机制:会对每个进程打分,如果系统真的繁忙到swapping都满足不了,就会杀掉一些分高的进程。
Page FAULT (缺页)
Basic TLB Mappings基础的TLB映射
Page Tables
Swapping
页表是放在主存中,所以虚拟内存你要访问内存实际上是要访问2次才能到真正的空间
多级页表
地址随机化(安全性考虑)
优化页表的访问
就是TLB,虚拟1内存很好,但成本也很高
TLB不在内存,在高速缓存
页面大,页表项少,寻址块,但容易产生的碎片多
页面小,碎片少,但寻址速度有影响
ITLB、STLB、Data TLB
STLB可以共享的TLB
Intel Core i7 内存系统
行访问和列访问
__restrict_
在该指针的生命周期内,其指向的对象不会被别的指针所引用
C语言进阶——likely和unlikely
1 #define likely(x) __builtin_expect(!!(x), 1)
2 #define unlikely(x) __builtin_expect(!!(x), 0)
__builtin_expect是编译器内建函数,原型为long __builtin_expect (long exp, long c)。该函数并不会改变exp的值,但是可以对if-else分支或者if分支结构进行优化。likely代表if分支大概率会发生,unlikely代表if分支大概率不会发生。
Prefetch(预分支,有硬件和软件2种)
Linux测试工具
虚拟内存的优点
可以使用磁盘交换空间
虚拟地址到物理地址的灵活映射
进程地址的空间隔离
虚拟内存到物理内存设计哪些软硬件?(MMU、TLB、Page Fault、Lazy allocation)
Linux Kernel Space(Kmalloc、vmalloc)和User Space(malloc)
内存管理无非3个层面
用户管理层层面
c运行时库的层面
操作系统层面
内存管理的设计假设Ptmalloc
具有长生命周期的大内存分配使用 mmap。
特别大的内存分配总是使用 mmap。
具有短生命周期的内存分配使用 brk,因为用 mmap 映射匿名页,当发生缺页异常 时,linux 内核为缺页分配一个新物理页,并将该物理页清 0,一个 mmap 的内存块 需要映射多个物理页,导致多次清 0 操作,很浪费系统资源,所以引入了 mmap 分配阈值动态调整机制,保证在必要的情况下才使用 mmap 分配内存。
尽量只缓存临时使用的空闲小内存块,对大内存块或是长生命周期的大内存块在释 放时都直接归还给操作系统。
对空闲的小内存块只会在 malloc 和 free 的时候进行合并,free 时空闲内存块可能 放入 pool 中,不一定归还给操作系统。
收缩堆的条件是当前 free 的块大小加上前后能合并 chunk 的大小大于 64KB、,并且 堆顶的大小达到阈值,才有可能收缩堆,把堆最顶端的空闲内存返回给操作系统。
需要保持长期存储的程序不适合用 ptmalloc 来管理内存。
为了支持多线程,多个线程可以从同一个分配区(arena)中分配内存,ptmalloc 假设线程 A 释放掉一块内存后,线程 B 会申请类似大小的内存,但是 A 释放的内 存跟 B 需要的内存不一定完全相等,可能有一个小的误差,就需要不停地对内存块 作切割和合并,这个过程中可能产生内存碎片。 由于学习 ptmalloc 源代码的目的是要解决项目中遇到的内存暴增问题,所以主要关注了 ptmalloc 可能造成内存管理问题的假设,所以不免有点鸡蛋里挑骨头的味道。
chunk的组织
1.Chunk 格式 ptmalloc 在给用户分配的空间的前后加上了一些控制信息,用这样的方法来记录分配的 信息,以便完成分配和释放工作。一个使用中的 chunk(使用中,就是指还没有被 free 掉) 在内存中的样子如图所示:
mem 指针才是真正返回给用户的内存指针
P表示前一个块是否在使用中
0 则表示前一个 chunk 为空闲,这时 chunk 的第一个域 prev_size 才有效,prev_size 表示前一个 chunk 的 size,程序可以使用这个 值来找到前一个 chunk 的开始地址。
1 时,表示前一个 chunk 正在使用中,prev_size 无效,程序也就不可以得到前一个chunk的大小。不能对前一个chunk进行任何操作
M:表示当前 chunk 是从哪个内存区域获得的虚 拟内存
M 为 1 表示该 chunk 是从 mmap 映射区域分配的,
0是从 heap 区域分配的。
A:表示该 chunk 属于主分配区或者非主分配区
如 果属于非主分配区,将该位置为 1,否则置为 0
解决方法
glibc 内存暴增,现象是程序已经把内存返回给了 Glibc 库,但 Glibc 库却没 有把内存归还给操作系统,最终导致系统内存耗尽,程序因为 OOM 被系统杀掉。
你可能要知道的
malloc/calloc/realloc
free
sbrk
payload
fragmentation
coalescing
第10章 系统级I/O
标准io是对系统的封装,使其对用户更友好