1.1.1 谷歌镜像

1.1.2 github主页

1.1.3 b站

1.1.4 豆瓣

1.1.5 鸠摩搜书

1.1.6 c++ reference

1.1.7 baidu

1.1.8 google-c++-styleguide

1.2.1 linux同步机制

1. 自旋锁底层
   

   https://cloud.tencent.com/developer/article/1484022

2. futex
   

   https://www.xuebuyuan.com/952276.html http://download.oracle.com/docs/cd/E19455-01/806-5257/6je9h032r/index.html

3. 互斥锁怎么实现的
   

   https://www.zhihu.com/question/332113890/answer/762392859

4. 原子操作底层实现
   

   https://blog.csdn.net/u011244446/article/details/52574369 https://zhuanlan.zhihu.com/p/33445834?utm_source=wechat_session

5. 条件变量
   
6. 使用
   

   https://www.cnblogs.com/harlanc/p/8596211.html

7. 底层原理
   

   https://www.cnblogs.com/c-slmax/p/5853784.html

8. __{thread和pthreadkeyt}
   

   https://www.jianshu.com/p/e01c1a2a46e7?ref=myread

9. explicit
   

   https://blog.csdn.net/guoyunfei123/article/details/89003369

10. 自定义swap
    

    https://www.cnblogs.com/cposture/p/4939971.html

11. C++ 传参时传内置类型时用传值(pass by value)方式效率较高
    

    https://blog.csdn.net/zyq522376829/article/details/48160039

12. C++异常机制底层
    

    https://www.cnblogs.com/sgawscd/p/13870406.html http://www.baiy.cn/doc/cpp/inside_exception.htm

13. BST与堆的区别
    

    http://www.dovov.com/searchbst.html

1.2.2 网络

1. 如何正确关闭tcp连接
   

   https://www.zhihu.com/question/48871684

2. TODO TODO TODO TODO TODO TODO 网络底层知识总结 http://www.52im.net/thread-3247-1-1.html
   

1.2.3 分布式

1. protobuf
   

   http://www.52im.net/thread-323-1-1.html

1.3.1 C++ 汇编代码查看

1.3.2 在线画图

1.3.3 在线看源码的网站

2.2.1 值得推荐的工具:

2.2.2 c-c++ 补全配置:

1. TODO 1. 配置lsp
   

   lsp在master分支上没有，只在develop分支上有，具体怎么配置还不熟悉

   dotspacemacs-configuration-layers
   '(...
     lsp
     ...)
   

   1. 安装ccls

   https://github.com/MaskRay/ccls/wiki/Build

   brew update
   brew install ccls
   

2.2.3 使得能在org中执行c，c++代码

(org-babel-do-load-languages
 'org-babel-load-languages '((C . t)))

2.3.1 resource

2.3.2 第一天：准备开始

1. 交换ctrl键和caps lock键
   

   https://www.emacswiki.org/emacs/MovingTheCtrlKey

2. 基本操作
   

   ;; 移动 C-f 为前移一个字符， f 代表 forward。 C-b 为后移一个字符， b 代表 backward。 C-p 为上移至前一行， p 代表 previous。 C-n 为上移至下一行， n 代表 next。 C-a 为移至行首， a 代表 ahead。 C-e 为移至行尾， e 代表 end。

   ;; 文件操作 C-x C-f 为打开目标文件， f 代表 find/file C-x C-s 为保存当前缓冲区（Buffer）， s 代表 save ;; 帮助信息 C-h k 寻找快捷键的帮助信息 C-h v 寻找变量的帮助信息 C-h f 寻找函数的帮助信息 ;; 创建链接 C-c C-l 执行代码 C-x C-e（执行时光标必须处于要执行函数/代码的末尾） 如下面的lisp代码： (+ 2 2)[执行前光标必须位于这个位置] ;; mode C-h m 显示当前buffer的所有major mode和minor mode ;; gtd C-c C-t(odo) 当前标签变为TODO，再按一次变为DONE，再按一次取消

2.3.3 第二天:高级自定义

1. 70:45分开始：org-mode Agenda的使用
   

   ;; 设置默认 Org Agenda 文件目录 (setq org-agenda-files '("~/org"))

   你只需将你的 *.org 文件放入上面所指定的文件夹中就可以开始使用 Agenda 模式了。

   C-c C-s 选择想要开始的时间 C-c C-d 选择想要结束的时间 C-c a 可以打开 Agenda 模式菜单并选择不同的可视方式（ r ）(需要保存org文件才会更新agenda)

2.3.4 第十一天: Spacemacs 简介及安装

1. 换monokai主题（46:00）
   

   主题预览：https://themegallery.robdor.com 出现的问题：https://emacs-china.org/t/spacemacs/885 ， 解决方法：在addition-packets中加上monokai-theme

   dotspacemacs-additional-packages '(youdao-dictionary monokai-theme)
   

2. 插入结构块
   
   • C-c C-, 插入包括代码块在内的各种块.
   • org-mode <s tab 插入代码块不可用的问题 https://emacs-china.org/t/spacemacs-org-mode-s/8366/4
   • , ' 打开代码块缓冲编辑代码
   • C-c C-c 执行代码块(C/C++ 必须大写)

2.3.5 第十二天: 创建你的第一个 Spacemacs Layer

1. 更换状态栏样式(09:27)
   

   ;; (setq powerline-default-separator 'alternate)
   ;; 更换状态栏格式
   (setq powerline-default-separator 'bar)
   

2.3.6 agenda 使用

3.1.1 初始化问题

1. 类内初始化
   

   c++11标准规定，可以为数据成员提供类内初始值，这个初始值可以放在花括号(列表初始化)里，也可以 放在等于号右边，但是 不能使用圆括号

2. 初始化要注意的地方
   
   1. 使用拷贝初始化时，只能提供一个初始值
   2. 类内初始值只能由拷贝初始化或使用花括号初始化
   3. 如果以提供初始元素值列表的形式初始化，只能用花括号，不能使用圆括号

   4. 如果初始化时使用了花括号形式但是不能用于列表初始化，那就只能考虑用这些值来匹配构造函数 也就是说花括号形式不等于列表初始化，如：

      vector<string> v{10, "hi"};    //v有10个值为“hi”的元素
      

3.1.2 左值引用与右值引用

3.1.3 extern

3.1.4 引用与指针

class A {
public:
  int aa;
};

int main() {
  auto a = new A();
  auto &b = *a;  
  auto *c = a;
  return a->aa;
}

main:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $32, %rsp
        movl    $4, %edi
        call    operator new(unsigned long)
        movl    $0, (%rax)
        movq    %rax, -8(%rbp)
        movq    -8(%rbp), %rax
        movq    %rax, -16(%rbp)
        movq    -8(%rbp), %rax
        movq    %rax, -24(%rbp)
        movq    -8(%rbp), %rax
        movl    (%rax), %eax
        leave
        ret

3.1.5 const注意点页

3.1.6 constexpr(58页）

3.1.7 auto类型说明符(61页)

3.1.8 decltype类型说明符(62页）

3.1.9 内置数组与vector的区别

3.1.10 sizeof运算符(139页)

#include <vector>
#include <iostream>
using namespace std;
int main() {
  vector<int> v(100, 0);
  cout << sizeof(v) << endl;
  return 0;
}

3.1.11 隐式类型转换 (141页）

3.1.12 运算符优先级表(147页)

3.1.13 函数重载(208页)

1. 几种视为相同的函数声明
   
   void A(int &) void A(int &i)

   typedef phone telno int lookup(phone&) int lookup(telno&) 3.顶层const int lookup(phone) int lookup(const phone)

3.1.14 值初始化(88页)和默认初始化

3.1.15 类的静态成员

3.1.16 智能指针

1. shared_ptr初始化
   
   • 如果不初始化一个智能指针，它就会被初始化为一个空指针
   • 接受指针参数的智能指针的构造函数是explicit的,所以我们不能将一个内置指针隐式转换为一个智能指针
2. 注意点(陷阱)
   
   • 不要混合使用普通指针和智能指针
   • 不要用get初始化另一个智能指针或为智能指针赋值
   • 不使用相同的内置指针初始化（或reset）多个智能指针
   • 不delete get（）返回的指针
   • 当智能指针销毁后，get（）返回的该智能指针的普通指针就无效了
   • 如果智能指针管理的资源不是new分配的内存，记住传递一个自定义的删除器

3.1.17 TODO allocator

3.1.18 13章 拷贝控制

1. 拷贝构造函数
   
   • 和默认构造函数不同，即使我们定义了其他构造函数，编译器也会为我们合成一个拷贝构造函数
   • 拷贝构造函数的第一个参数必须是一个引用类型，而且这个参数几乎总是const的
   • 拷贝构造函数通常不应该是explicit的，因为它会被隐式使用
   • 每个成员的类型决定了它如何拷贝，对类类型的成员会使用其拷贝构造函数，内置类型直接拷贝
2. 拷贝初始化和直接初始化
   
   • 拷贝初始化使用等号，直接初始化不使用等号
   • 直接初始化实际上是要求编译器使用普通的函数匹配来选择与我们提供的参数最匹配的构造函数， 拷贝初始化要求编译器将=右侧的运算对象拷贝到正在创建的对象中，如果需要的话还要进行类型 转换
3. 拷贝构造函数和拷贝赋值运算符怎么区别
   

   • 拷贝构造函数是在初始化时调用，而赋值运算符是在初始化后的赋值时调用

     // 拷贝构造函数
     string s = "emacs";
     
     // 拷贝赋值运算符
     string s;
     s = "emacs";
     

4. 析构函数
   
   • 认识到析构函数自身并不直接销毁成员是非常重要的，成员是在析构函数体之后隐含的析构阶段中 被销毁的
5. 三五法则
   
   1. 需要析构函数的类也需要拷贝和赋值操作
      

      因为需要析构函数说明需要自定义资源管理，那么拷贝和赋值也都需要,比如析构函数销毁指针所指 资源，如果用合成的拷贝和赋值操作的话，会使两个对象的该指针指向同一地址，引发错误

   2. 需要拷贝操作的类也需要赋值操作，反之亦然
      

      作为例子，考虑一个类为每个对象分配一个唯一的序号，这个时候就需要自定义拷贝和赋值操作而 不能用合成的，拷贝和赋值实现的效果其实是相同的，所以一个需要自定义的话，另一个也需要, 但是上面这个例子其实不需要自定义析构函数，因为没有资源需要管理。

   3. 一般来说，如果一个类定义了任何一个拷贝操作，他就应该定义所有五个操作
      

      因为如果必须自定义拷贝构造函数，拷贝赋值运算符和析构函数，那么这个类通常会涉及资源的管理问题， 而拷贝成员必须拷贝这些资源。这会导致额外的开销，所以一般要定义移动构造函数和移动赋值运算符来 避免这种开销

6. 移动构造函数
   
   • 除了完成资源的移动，移动构造函数还必须保证源对象处于析构安全状态,也就是说析构它是无害的, 而且也必须是可以被析构的(还是存在的，可以进行操作)
   • 由于移动操作通常不分配任何资源，所以通常不抛出任何异常
   • 只有当一个类没有定义任何直接版本的拷贝控制成员，且类的每个非static数据成员都可以 移动时，编译器才会为它合成移动构造函数或移动赋值运算符
   • 定义了一个移动构造函数或移动赋值运算符的类必须也定义自己的拷贝操作，否则，这些成员 默认地被定义为删除的
7. TODO 移动迭代器
   
8. 右值引用和成员函数
   

   区分移动和拷贝的重载函数通常有一个版本接受一个const T&， 而另一个版本接受一个T&&, 因为一般 来说，当我们希望移动数据时实参不能是const的，因为这样才能保证移动源可以被改变成析构安全的。

9. TODO 函数重载与const， &， &&
   

3.1.19 14章 重载运算和类型转换

1. 重载运算符
   
   • 重载运算符实质是具有特殊名字的函数，由关键字operator和要定义的运算符共同组成。一元运算符有一个 参数，二元运算符有两个参数：运算符左侧对象传递给第一个参数，右侧传给第二个。
   • 除了operator()之外，其他重载运算符都不能有默认实参
   • 一个运算符函数，要么是类的成员，要么至少含有一个类类型的参数(因为内置类型的运算符已经预定了)
   • 当一个重载运算符是成员函数时，this绑定到左侧运算对象，所以显式参数比运算对象少一个
   • 不能被重载的运算符(:: .* . ?:)
   • 通常情况下不应该被重载的运算符(, & && ||), 因为重载本质是函数，无法保留求值顺序/短路求值属性
   1. 重载运算符是否定义为成员函数的准则：
      

      

      • 输入运算符必须处理输入可能失败的情况，而输出符不需要(496页)
      • 如果定义了算术运算符和相应的复合赋值运算符，通常应使用后者实现前者
      • 赋值运算符必须是类的成员，复合赋值运算符通常情况下(难道不是必须吗？TODO，不是成员的话 不能访问类并对它赋值吧？）也是如此(500页)
      • 下标运算符必须是成员函数，下标运算符通常需要两个版本：一个返回普通引用，一个返回const引用
      • 递增递减运算符应该同时定义前置和后置版本，且通常被定义为类的成员,前置返回引用，后置返回值。 后置版本需要接受一个额外的不被使用的int形参来和前置区分
      • ->运算符必须是类的成员，解引用运算符通常也是类的成员
2. 函数调用运算符
   
   • 函数调用运算符必须是成员函数，一个类可以定义多个不同版本的调用运算符，它们应该在参数数量或 类型上有所区别
   • 定义了调用运算符的类叫函数对象，这些对象的行为就像函数一样,函数对象常常作为泛型算法的实参
3. TODO lambda(508页)
   
4. 可调用对象与function
   

   c++有几种可调用的对象：函数、函数指针、lambda表达式、bind创建的对象以及重载了函数调用运算符的 类。他们的调用形式可以是相同的，但是却有着不同的类型，所以在很多地方受到约束。比如下面的例子， 我们想定义一个简单的计算器：

   int add(int i, int j) {return i+j;}
   auto mod = [](int i, int j) {return i%j;}
   
   map<string, int(*)(int,int)> binops;
   // 正确
   binops.insert({"+", add});
   //错误, mod不是函数指针
   binops.insert({"%", mod});
   

   c++11新标准库function类型解决了这个问题:

   map<string, function<int(int,int)>> binops;
   
   binops.insert("+", add);
   binops.insert("%", mod);
   

   当然，如果add函数被重载的话，上面的方法就行不通了，但是可以用函数指针来解决

5. 重载，类型转换与运算符
   
   1. 类型转换运算符
      

      转换构造函数和类型转换运算符共同定义了类类型转换，与标准类型转换相对，这种转换也叫用户 定义的类型转换。 类型转换函数的一般形式为：

      operator type() const
      

      一个类型转换函数必须是类的成员函数；它不能声明返回类型，形参列表也必须为空。类型转换函数通常 应该是const的，因为它不应该改变待转换对象的内容。 为了防止隐式类型转换引发意想不到的结果，c++11标准引入了显示的类型转换运算符：

      explicit operator int() const {};
      

      和显示构造函数一样，编译器不会将一个显式的类型转换运算符用于隐式类型转换，除了下边这个例外：

      正因为这个例外，operator bool一般定义为explicit的

   2. TODO 类型转换的二义性
      

      通常情况下，不要为类定义相同的类型转换，也不要在类中定义两个及两个以上转换源或转换目标是 算术类型的转换

   3. TODO 函数匹配与重载运算符
      

3.1.20 15章 面向对象程序设计

class A : public B, protected C, private D {

};

1. 类型转换与继承
   
   • 静态类型和动态类型 静态类型：声明时指定的类型，编译时确定 动态类型：内存中实际对象的类型，运行时才能确定 如果一个表达式不是引用也不是指针，那它的静态和动态类型永远一致 引用或指针的静态类型与动态类型不同这一事实正是c++语言支持多态性的根本所在
   • 智能指针类也支持派生类向基类的类型转换，这意味着我们可以将一个派生类对象的指针存储在一个基 类的智能指针内

   • 要理解在具有继承关系的类之间的类型转换，三点非常重要：

   

2. 虚函数
   
   • 覆盖
     1. 一个派生类的函数要覆盖某个继承来的虚函数，那么它的形参类型必须与被它覆盖的基类函数 完全一致
     2. c++11可以使用override关键字来说明派生类的虚函数，这使得程序员的意图更加清晰。因为 如果程序员本来想覆盖父类虚函数但是参数写错了，就会导致程序偏离意图。这时如果加上override 编译器就会报错。
   • 虚函数默认实参 如果虚函数使用了默认实参，则基类和派生类中定义的默认实参最好一致，因为如果 函数调用使用了默认实参，则实参由本次调用的静态类型决定,也就是说如果静态类型是基类的， 就算调用动态绑定到了继承类定义的函数，实参值还是基类的。

   • 可以使用作用域运算符来回避虚函数机制 派生类重新定义继承来的虚函数时，可能需要调用基类的虚函数版本，这就需要回避虚函数机制，不然 会导致派生类虚函数自己调用自己而无限循环：

     double undisconted = baseP->Quote::net_price(42);
     

3. 抽象基类
   
   • 在函数体的位置写 =0 就可以将虚函数说明为纯虚函数，我们不能在类的内部为一个纯虚函数提供 结构体

   • 含有（或未经覆盖直接继承）纯虚函数的类是抽象基类。不能直接创建一个抽象基类的对象 如下面的例子：

     // Type your code here, or load an example.
     #include <memory>
     using namespace std;
     struct A{
       //A(A &fk) { a = fk.a;}
       virtual int foo() = 0;
       int a;   
     };
     int A::foo() {return 0;}
     
     class B : public A {
     
     };
     int main() {
       B  aa;
       return 0;
     }
     

     虽然A的foo已经在类外定义好了，但是倒数第三行的B aa这个代码还是报错： error: cannot declare variable 'aa' to be of abstract type 'B'

4. 访问控制
   

   • 每个类都负责控制自己的成员的访问权限：

     	public	protected	private
     用户	☑️	️	️
     派生类	☑️	☑️
     友元	☑️	☑️	☑️

   • 派生类通过派生访问说明符来控制它的成员访问权限，派生访问说明符对于派生类的成员（及友元） 能否访问其直接基类的成员没有任何影响，其目的只是控制该派生类的用户（包括派生类的派生类） 对该派生类的访问权限，其规则是：

     1. 如果继承是公有的，则派生类成员的访问权限直接继承基类的权限说明
     2. 如果是protected继承，则基类中的public成员都会被声明成protected
     3. 如果是private继承，则所有成员都变成private的

     如：

     #include <memory>
     using namespace std;
     class B {
     private:
       int pri_mem;
     protected:
       int prot_mem;
     };
     
     class S : private B {
       friend void c(S&);
       friend void c(B&);
       int j;
     
       int f1() const {return prot_mem;} //不报错
     };
     
     class G : public S {
       int g() {return prot_mem;}  //报错
       int g1() {return pri_mem;}  //报错，
     };
     
     void c(S &s) {
       s.j = s.prot_mem = 0; //不报错
     }
     
     int main() {
     
       return 0;
     }
     

     虽然S的派生访问符是private，但是c函数和f1函数能访问B的成员；而g和g1函数报错， 这个例子证明的上面的说法

   • 派生类向基类转换的可访问性 如果基类的公有成员是可访问的，则派生类向基类的类型转换也是可访问的
   • 友元关系不能继承

   • 派生类可以为那些它可以访问的名字通过using声明来改变可访问性:

     class Base {
     public:
       int pub;
     protected:
       int pro;
     private:
       int pri;
     };
     
     class D : private Base {
       using Base::pub;
       using Base::pro;
       // 错，D不能访问pri，所以不能用using
       // using Base::pri;
     }
     

5. 继承中的类作用域
   
   • 派生类的作用域是嵌套在其基类的作用域之内的。
   • 一个对象、引用或指针的静态类型决定了该对象的哪些成员是可见的，即使静态类型和动态类型 不一致，也就是说，如果一个对、引用、指针象的静态类型是基类的类型，那么它就不能访问 基类没有定义的成员，就是继承类定义了这个成员
   • 派生类的成员将隐藏基类的成员，即使基类成员函数的参数列表和派生类不一样，因为名字查找优先于 类型检查，这也说明了为什么基类和派生类的虚函数必须有相同的形参列表，因为如果不这样，基类 的虚函数就会被 隐藏 而不是 覆盖
   • TODO 隐藏、覆盖、重写 虚函数也可以被重写
6. TODO(深入对象模型重点理解) 构造函数与拷贝控制的继承
   

3.1.21 16章 模版与泛型编程

1. 函数模版
   

   • 定义模版 模版定义以关键字template开始，后跟一个用 <> 包围起来的模版参数列表, 参数列表中的参数分为 类型模版参数 和 非类型模版参数 ， 每个 类型参数前必须使用关键字 class或typename, class和typename没有什么区别，只是c++早期只有class关键字，其实typename 更加直观：

     //类型模版参数
     template <typename T>
     int compare(const T &v1, const T &v2)
     {
       if (v1 < v2) return -1;
       if (v2 < v1) return 1;
       return 0;
     }
     
     //非类型模版参数
     /* 非参数类型可以是一个整数，或者是一个指向对象或函数类型的指针或引用
      * 而且，绑定到整数的必须是常量表达式，绑定到指针或引用类型的必须具有
      * 静态生存期
     **/
     template<unsigned N, unsigned M>
     int compare(const char (&p1)[N], const char (&p2)[M])
     {
       return strcmp(p1, p2);
     }
     

     从上面代码可以说明编写泛型代码的两个重要原则：

     1. 模版中的函数参数是const的引用，这样保证函数可以用于不能拷贝的类型
     2. 函数体条件判断仅使用 < 比较运算符

     也就是说，模版程序应该尽可能减少对实参的要求

   • 实例化模版与头文件 编译器不会直接为模版定义生成代码，只有当我们调用一个函数模版时，编译器才用函数实参 来为我们推断模版实参并生成一个模版的实例代码，这个过程叫实例化。 通常，当我们调用一个函数时，编译器只需要掌握函数的声明；当我们使用一个类类型的对象时 ，类定义必须是可用的，但成员函数的定义不必已经出现；这是因为编译器编译过程中，只需要 知道对象的名字就可以了(具体定义由连接器负责)，函数只要声明了就可以知道它的名字，而类 必须要有了定义才能知道它的成员的名字。 模版则不同，为了生成一个实例化的版本代码，编译器需要掌握函数模版或类模版成员函数的定义。 这些区别也导致了与头文件相关的一些不同：
     1. 我们将类定义和函数声明放在头文件中，而普通函数和类的成员函数的定义放在源文件中
     2. 与非模版代码不同，模版的头文件通常即包含声明也包含定义(因为编译器需要)
2. 类模版
   
   • 定义 类模版是用来指导编译器生成类的。一个类模版的每个实例都形成一个独立的类 与函数模版不同，编译器不能为类模版推断模版参数类型 定义在类模版内的成员函数被隐式声明为内联函数
   • 实例化 一个实例化了的类模版，其成员只有在使用时才被实例化。 在一个类模版的作用域内，我们可以直接使用模版名而不必指定模版实参
   • TODO 模版与友元

   • 模版类作用域运算符 当编译器遇到类似T::mem这样的代码时，它不会知道meme是一个类型成员还是一个static数据成员 ，直到实例化才会直到。比如编译器遇到如下形式的语句：

     T::size_type * p;
     

     它需要知道我们是正在定义一个名为p的变量还是将一个名为size_{type的static数据成员与名} 为p的变量相乘。默认情况下，c++假定通过作用域运算符访问的名字不是类型，所以如果我们希望 使用一个模版类型参数的类型成员，必须用typename关键字显示告诉编译器该名称是一个类型:

     typename T::size_type * p;
     

     这样才表示我们正在定义一个名为p的T::size_type * 类型的变量

3. 成员模版
   

   一个类（无论是普通类还是类模版）可以包含本身是模版的成员函数。这种成员被称为成员模版。 成员模版不能是虚函数 ,类模版和成员模版各自有各自独立的模版参数。 当我们在类模版外定义一个成员模版时,必须同时为类模版和成员模版提供模版参数列表。 类模版的参数列表在前，成员模版的参数列表在后。

   template <typename T>  //类的类型参数
   template <typename It> //构造函数的类型参数
   

4. 控制实例化
   

   当两个或多个独立编译的源文件使用了相同的模版，并提供了相同的模版参数时，每个文件中就都会有该 模版的实例。在大系统中，这种额外开销可能非常严重。在c++11新标准中，我们可以通过显式实例化 来避免这种开销：

   extern template declaration;  // 实例化声明
   template declaration;         // 实例化定义
   

   对于一个给定的实例化版本，可能有多个extern声明，但必须只有一个定义

   一个类模版的实例化定义会实例化该模版的所有成员，包括内联的成员函数。因为当编译器遇到一个 实例化定义时，它不知道程序你用哪些成员函数。 所以，我们用来显式实例化一个类模版的类型， 必须能用于模版的所有成员

5. 效率与灵活性
   

   通过编译时绑定删除器，unique_{ptr避免了间接调用删除器的运行时开销}。通过在运行时绑定删除器， shared_{ptr使用户重载删除器更方便}，就是说模版可以在效率和灵活性之间做trade off。

6. 模版实参推断
   

   有些特殊情况类型推导并不那么顺利：

   • 模版类型参数的类型转换 能应用于函数模版的类型转换只有两种：
     1. const转换：将一个非const对象的引用或指针传递给一个const的引用形参

     2. (TODO:类型转换整理)数组或函数指针转换：

        

   • 使用相同模版参数类型

     long lng;
     compare(lng, 1024);
     

     compare接受两个const T&参数，所以上面的调用使错误的, 因为推断出来的long和int不是 同一类型，这种情况可以通过显示指定参数类型解决：

     long lng;
     compare<long>(lng, 1024);
     

     上面的例子实例化为compare(long,long)

   • 函数模版中可以有 用普通类型定义的参数

     

   • 显式实参

     

     

   • 尾置返回类型 当我们希望用户确定返回类型时：

     由于编译器在遇到参数列表之前，beg是不存在的，所以我们必须使用尾置类型来定义此函数：

     

   • 用于进行类型转换的标准库模版类

     

   • 函数指针类型推导 当参数是一个函数模版实例的地址时，程序上下文必须满足：对每个模版参数都能唯一确定 其类型或值

   • 引用的推断

     1. 绑定到常量时引用的汇编层面

        • const左值引用

          int main() {
            const int & a = 10;
            return 0;
          }
          

            main:
                    pushq   %rbp
                    movq    %rsp, %rbp
                    movl    $10, %eax
                    movl    %eax, -12(%rbp)
                    leaq    -12(%rbp), %rax
                    movq    %rax, -8(%rbp)
                    movq    -8(%rbp), %rax
                    movl    0, %eax
                    popq    %rbp
                    ret
          
          rbp-----> -----------
          
                        a
          rbp-8---> -----------
                        10
          rbp-12--> -----------
          

        • 右值引用

          int main() {
            int && a = 10;
            a = 11;
            return 0;
          }
          

          main:
                  pushq   %rbp
                  movq    %rsp, %rbp
                  movl    $10, %eax
                  movl    %eax, -12(%rbp)
                  leaq    -12(%rbp), %rax
                  movq    %rax, -8(%rbp)
                  movq    -8(%rbp), %rax
                  movl    $11, (%rax)
                  movl    $0, %eax
                  popq    %rbp
                  ret
          

     可以看到，绑定到常量时，无论左值引用和右值引用，编译出的代码都一样，编译器会把常量放到 引用所在定义域的一个位置。 TODO ： 为什么左值可以绑定到常量?

7. 重载与模版
   
   1. 函数匹配规则（209页）遇到模版时(615页)
      

3.2.1 3 迭代器与traits编程技法

1. 迭代器分类
   

   

   

2. traits机制
   

   因为c++不是强类型语言，没有typeof之类的操作来获取类的类型，即使有个RTTI的 typeid也只能获得类型的别名，而不能用来声明变量。 针对上面的问题，SGI通过利用function template的参数类型推导来间接获取 泛型的类型。

   

3.2.2 4 序列化容器

3.2.3 5 关联式容器

1. set
   
   1. 不能通过set的迭代器改变set的元素，因为set元素的值关系到排序规则. set<T>::iterator被定义为RB tree的const_iterator
   2. 操作之前的所有迭代器在操作完后依然有效(除了erase删除的)
2. hashtable
   
   1. SGI的hashtable迭代器为forward_{iteratortag迭代器}，所以只能单向遍历 也没有逆向迭代器(rbegin()等)
   2. hashtable重载因子为1,并且用链地址法来解决冲突

3.2.4 6 算法

1. numeric数值算法
   

   #include <numeric>
   #include <vector>
   #include <functional>
   #include <iostream>
   #include <iterator>
   using namespace std;
   
   int main()
   {
     int ia[5] = { 1, 2, 3, 4, 5};
     vector<int> iv(ia, ia+5);
     cout << accumulate(iv.begin(), iv.end(), 0) << endl;
     cout << accumulate(iv.begin(), iv.end(), 0, minus<int>()) << endl;
   
     ostream_iterator<int> oit(cout, " ");
   
     partial_sum(iv.begin(), iv.end(), oit);
     cout << endl;
     partial_sum(iv.begin(), iv.end(), oit, minus<int>());
     cout << endl;
   
     adjacent_difference(iv.begin(), iv.end(), oit);
     cout << endl;
     adjacent_difference(iv.begin(), iv.end(), oit, plus<int>());
     cout << endl;
   
     //  cout << power(10, 3) << endl;
     //  cout << power(10, 3, plus<int>()) << endl;
   
   }
   
   

2. 基本算法
   

   #include <algorithm>
   #include <vector>
   #include <functional>
   #include <iostream>
   #include <iterator>
   #include <string>
   using namespace std;
   
   int main()
   {
     int ia[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
     vector<int> iv1(ia, ia+5);
     iv1.push_back(-1);
     vector<int> iv2(ia, ia+9);
   
     ostream_iterator<int> oit(cout, " ");
   
     // 判断两个区间的第一个匹配点，返回一个由两个迭代器组成的pair
     // 其中第一个迭代器指向第一个区间的不匹配点，
     //    第二个迭代器指向第二个区间的不匹配点
     cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin())).first << endl;
     cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin())).second << endl;
   
     // equel
     // 如果俩个序列在[first, last) 区间内相等，equal返回true
     cout << equal(iv1.begin(), iv1.end(), iv2.begin()) << endl;
     cout << equal(iv2.begin(), iv2.end(), iv1.begin()) << endl;
     cout << equal(iv1.begin(), iv1.end(), &ia[3]) << endl;
     cout << equal(iv1.begin(), iv1.end(), &ia[3], less<int>()) << endl;
   
     fill(iv1.begin(), iv1.end(), 9);
     for (auto e : iv1) cout << e << ' ';
     cout << endl;
   
     fill_n(iv1.begin(), 3, 7);
     for (auto e : iv1) cout << e << ' ';
     cout << endl;
   
     auto it1 = iv1.begin();
     auto it2 = it1;
     advance(it2, 3);
     iter_swap(it1, it2);
     for (auto e : iv1) cout << e << ' ';
     cout << endl;
     for (auto e : iv2) cout << e << ' ';
     cout << endl;
   
     swap(*iv1.begin(), *iv2.begin());
     for (auto e : iv1) cout << e << ' ';
     cout << endl;
     for (auto e : iv2) cout << e << ' ';
     cout << endl;
   
     string s1[] = { "abc", "def", "gh"};
     string s2[] = { "bc", "adc", "jungle"};
     // 以字典序对两个序列进行排序
     cout << lexicographical_compare(s1, s1+2, s2, s2+2) << endl;
     cout << lexicographical_compare(s1, s1+2, s2, s2+2, greater<string>()) << endl;
   }
   
   

3.2.5 7 仿函数

3.3.1 绪论

1. 左值与右值
   

   检查能否取得表达式的地址。如果能取到，那么该表达式基本可以断定是左值； 如果不可以，则通常为右值。

   根据上面的定义，表达式的型别与它是左值还是右值没有关系：

   class A{
     int x = 7;
   };
   
   void foo(A &&a) {
     A &&b = A(); //b是左值, 意思是虽然b引用的对象没有名字，
     //是个右值，但是b是有名字的，所以他是个
     //左值
     //同样的道理，a也是个左值
     A c;
     b = c;
     //foo(b);
   }
   
   

3.3.2 类型推导

1. 1 了解模版型别推导
   

   一个函数模版的声明和调用大致如下：

   template<typename T>
   void f(ParamType param);
   
   f(expr);
   

   在编译期，编译器会通过expr推导两个型别：T和PrarmType。 这两个型别往往是不一样的，因为ParamType常常会包含一些修饰词， 如const或引用符。实际情况是，T的推导结果，不仅依赖于expr的 型别，还依赖于ParamType的形式。要分为三种不同情况来讨论：

   1. 1. ParamType是个指针或引用，但不是万能引用
      

      推导规则如下：

      1. 若expr具有引用型别，先将引用部分忽略
      2. 然后，对expr的型别和ParamType的型别执行模式匹配，来决定T的型别

      例如，

      我们的模式如下：
      template<typename T>
      void f(T &param);
      
      template<typename T>
      void f1(const T& param);
      
      template<typename T>
      void f2(T *param);
      
      又声明了下列变量：
      int x = 27;
      const int cx = x;
      const int &rx = x;
      const int *px = &x;
      
      那么下面的调用中，推导结果如下：
      f(x);      // T是int， param是int&
      f(cx);     // T是const int， param是const int&
      f(rx);     // T是const int， param是const int&
      
      f1(x);      // T是int， param是const int&
      f1(cx);     // T是int， param是const int&
      f1(rx);     // T是int， param是const int&
      
      f2(&x);     // T是int， param是int*
      f2(px);     // T是const int， param是const int*
      

   2. 2. ParamType是个万能引用
      

      推导规则如下：

      1. 如果expr是个左值，T和ParamType都会被推导为左值引用。 这是T被推导为引用的唯一情形，而且尽管语法是右值引用的， 但结果却是左值引用。
      2. 如果expr是个右值，则应用“情况1”中的规则

      例子：

      template<typename T>
      void f(T &&param);      //param现在是个万能引用
      
      int x = 27;
      const int cx = x;
      const int &rx = x;
      
      f(x);                  // x是个左值，所以T为int&，param为int&
      f(cx);                 // cx是个左值，所以T为const int&，param也为const int&
      f(rx);                 // rx是个左值，所以T为const int&，param也为const int&
      f(27);                 // 27是个右值，所以T为int，param为int&&
      

   3. 3. ParamType既非指针也非引用
      

      这种情况下，param会是个全新的对象，而且是expr的副本，所以推导规则为：

      1. 如果expr具有引用型别，则忽略其引用部分
      2. 忽略expr的引用性之后，若expr是个const对象，也忽略它，这是因为 现在是值传递，不像情形1是个引用传递。所以expr是const，并不表 示param也要是一个const。他们是独立的。 如果expr是个volatile对象，也忽略它。

      template<typename T>
      void f(T param);
      
      int x = 27;
      const int cx = x;
      const int &rx = x;
      const char *const ptr = "Fun with pointers";
      
      f(x);               // T和param的类型都是int
      f(cx);              // T和param的型别仍都是int
      f(rx);              // 同上
      f(ptr);             // T和param为const char *，
      

      1. 有两个特殊情况需要考虑：数组或函数型别的实参会退化成对应的指针， 除非它们被用来初始化引用。 TODO : 例子p22
2. 2 理解auto型别推导
   
   1. 一般情况下，auto型别推导和模版型别推导是一模一样的，但是 auto型别推导会假定用大括号括起来的初始化表达式代表一个 std::initializer_{list,但模板型别推导不会}。 当某变量采用auto来声明时，auto就扮演了T的角色，而变量的型别 修饰词扮演了ParamType的角色。
   2. 在参数返回值或lambda式的形参中使用auto，意思是使用模板型别推导 而不是auto。
3. 3 理解decltype
   
4. 14 TODO throw 的汇编层实现
   

3.4.1 第一章 关于对象

1. C++相比C的布局及存取时间上的主要额外负担
   

   主要包括两个点：

   1. virtual function机制
   2. virtual class

   此外还有一些

   1. 多重继承下的额外负担 发生在“一个derived class和其第二或后继的base class之间的转换”
2. C++对象模型
   

   Stroustrup当初设计的（目前仍然是主流）的C++对象模型可以看作是 简单对象模型 和 表格驱动对象模型 的结合: 在此模型中，Nonstatic data members被配置于每一个class object之内， static data members，static及nonstatic function members则 被存放在个别的class object之外。

   virtual function 则以两个步骤支持：

   1. 每一个class产生出一堆指向virtual functions的指针，放在表格之中。 这个表格被成为virtual table（ vtbl ）。
   2. 每一个class object被安插一个指针，指向相关的virtual table。通常 这个指针被称为 vptr 。vptr的设定和重置都由每个class的constructor、 destructor和copy assignment运算符自动完成。每一个class所关联 的type_info object（用来支持runtime type identification， RTTI）也经由virtual table被指出来，通常放在表格的第一个slot。

   virtual base class 则由和virtual function异曲同工的 btal*和*bptr 支持。

3. C++对象大小
   
   • 非静态数据成员的大小总和
   • 加上内存对齐
   • 加上为了支持virtual而产生的额外负担

3.4.2 第二章 构造函数语意学

1. （编译器合成默认构造函数时机）nontrivail default construct
   

   简单理解就是：下面的情况都进入了part of c++的领域，而不再是part of c，所以需要 合成默认构造函数

   1. 带有default construct的member class object 什么时候带有默认构造函数？答案是 当用户自定义了一个默认构造函数或编译器会为他合成一个的时候。例如下面代码：

      class Foo {
      public:
        Foo();
      };
      class Bar {
      public:
        Foo foo;
        char *str;
      };
      
      void foo_bar() {
        Bar bar;
      }
      

      其汇编代码为：

      Bar::Bar() [base object constructor]:
              pushq   %rbp
              movq    %rsp, %rbp
              subq    $16, %rsp
              movq    %rdi, -8(%rbp)
              movq    -8(%rbp), %rax
              movq    %rax, %rdi
              call    Foo::Foo() [complete object constructor]
              nop
              leave
              ret
      foo_bar():
              pushq   %rbp
              movq    %rsp, %rbp
              subq    $16, %rsp
              leaq    -16(%rbp), %rax
              movq    %rax, %rdi
              call    Bar::Bar() [complete object constructor]
              nop
              leave
              ret
      

      上面的例子中，由于Foo定义了一个默认构造函数，所以编译器为Bar函数也 定义了一个默认构造函数. 如果Foo没有定义默认构造函数的话:

      class Foo {
      public:
      };
      class Bar {
      public:
        Foo foo;
        char *str;
      };
      
      void foo_bar() {
        Bar bar;
      
      

      那么编译器也就不会为Bar合成一个默认构造函数：

      foo_bar():
              pushq   %rbp
              movq    %rsp, %rbp
              nop
              popq    %rbp
              ret
      

      当用户自定义了其他的construct就不会没有default constrcut,如下面 的代码会报错没有默认构造函数：

      class Foo {
      public:
        Foo(int);
      };
      class Bar {
      public:
        Foo foo;
        char *str;
      };
      
      void foo_bar() {
        Bar bar;
      
      

   2. 带有default constrcut的Base Class
   3. 带有一个virtual function的Class
   4. 带有一个virtual base class的Class

   如果用户自定义了默认构造函数，那么编译器会根据他的需要扩张这个构造函数

2. 拷贝构造函数
   
   1. 拷贝函数被调用的三种情况：
      

      1. 显示初始化

         X x;
         X xx = x;
         

      2. 函数参数传递

         extern void foo(X x);
         
         void bar() {
           X xx;
           foo(xx);
         }
         

      3. 参数返回值

         X foo_bar()
         {
           X xx;
           return xx;
         }
         

   2. defult memberwise initialization和bitwise copy
      

      当一个类对象a以相同class的另一个对象b作为初值初始化时，用的是 default memberwise initialisztion手法完成的： 把每一个基本内置类型和复合类型的data member，从b拷贝一份到a； 但是对于类成员对象，则会递归对这些类对象实施memberwise initialization.

      所以memberwise initialization只会对类中的成员进行操作， 也就是说不会考虑 到vptr和vbptr.

      而bitwise是把一个类的内存对象的整个模型（包括vptr和vbptr）考虑进去了。

      也就是说，一个类的memberwise initialization不一定是bitwise的, 特别是加入了多态性之后，肯定就不是了。

      下面的理解有问题，看上面的

      当一个类对象a以相同class的另一个对象b作为初值初始化时，用的是 default memberwise initialisztion手法完成的： 把每一个基本内置类型和复合类型的data member，从b拷贝一份到a； 但是对于类成员对象，则会递归对这些类对象实施memberwise initialization.

      而bitwise copy就是可以理解为：当类中的所有成员的memberwise initialization 最终都表现为直接复制其基本内置类型和复合类型成员（也叫默认复制语意)。 以下面的例子来理解： 首先看非bitwise copy：

      class str {
      public:
        str(const str&);
      private:
      };
      
      class Word {
      public:
        Word( const str&);
      private:
        int cnt;
        str a;
      };
      
      void foo_bar(const Word &wd) {
        Word w = wd;
      
      

      其汇编为：

      Word::Word(Word const&):
              pushq   %rbp
              movq    %rsp, %rbp
              subq    $16, %rsp
              movq    %rdi, -8(%rbp)
              movq    %rsi, -16(%rbp)
              movq    -16(%rbp), %rax
              movl    (%rax), %edx
              movq    -8(%rbp), %rax
              movl    %edx, (%rax)
              movq    -8(%rbp), %rax
              addq    $4, %rax
              movq    -16(%rbp), %rdx
              addq    $4, %rdx
              movq    %rdx, %rsi
              movq    %rax, %rdi
              call    str::str(str const&)
              nop
              leave
              ret
      foo_bar(Word const&):
              pushq   %rbp
              movq    %rsp, %rbp
              subq    $32, %rsp
              movq    %rdi, -24(%rbp)
              movq    -24(%rbp), %rdx
              leaq    -8(%rbp), %rax
              movq    %rdx, %rsi
              movq    %rax, %rdi
              call    Word::Word(Word const&)
              nop
              leave
              ret
      

      可以看到，str自定义了一个拷贝构造函数，所以str和含有str的Word都不再有默认 复制语意.所以编译器会为Word合成一个拷贝构造函数。

      而bitwise copy的话：

      class str {
      public:
        // str(const str&);
      private:
      };
      
      class Word {
      public:
        Word( const str&);
      private:
        int cnt;
        str a;
      };
      
      void foo_bar(const Word &wd) {
        Word w = wd;
      
      

      重点注意到被注释掉的代码，也就是说str并没有自定义的copy，所以可以说str 符合默认复制语意。 其汇编为：

      foo_bar(Word const&):
              pushq   %rbp
              movq    %rsp, %rbp
              movq    %rdi, -24(%rbp)
              movq    -24(%rbp), %rax
              movq    (%rax), %rax
              movq    %rax, -8(%rbp)
              nop
              popq    %rbp
              ret
      

   3. 不展现bitwise copy semantics的情况：
      
      1. 当class内含有一个member object，而后者的class声明中有一个拷贝构造函数时 （不管是显式声明还是编译器合成）
      2. 当class继承自一个base class而后者存在一个拷贝构造函数时 （不管是显式声明还是编译器合成）
      3. 当class声明了一个或多个virtual functions时
      4. 当class派生自一个继承链，其中一个或多个为virtual base calss时
3. NRV优化
   

   即named return value优化：

   X bar(){
     X xx;
     处理xx
     return xx;
   }
   
   void
   bar(X &__result)
   {
     __result.X::X();
     直接处理__result
     return ;
   }
   

4. TODO 什么时候必须使用成员初始化列表(p.75)
   

   todo 为什么虚拟继承需要到执行期才能确定去哪？ 感觉可以用虚函数做类比，因为其动态类型是执行期才 确定的，而虚拟继承和虚函数一样，其偏移或者地址是知道动态类型 才能确定的。

3.7.1 头文件配置

3.7.2 charpter3

1. lseek
   

   在比较lseek的返回值时应该谨慎，不要测试是否小于0，而要测试是否等于-1

2. 内核用3种数据结构来表示打开的文件
   
   1. 每个进程在进程表中都有一个记录项，记录项中包含一张打开文件描述符表，与每个文件描述符关联的是： a. 文件描述符标志 b. 指向一个文件表项的指针
   2. 内核为所有打开文件维持一张全局文件表。每个文件表项包含： a. 文件状态标志（读，写，添写，同步，非阻塞等） b. 当前文件偏移量 c. 指向该文件v节点表项的指针
   3. 每个打开的文件（或设备）都有一个v节点结构，包含了： a. 文件类型 b. 对此文件进行各种操作的函数的指针
3. dup和dup2的区别
   
   • dup返回的文件描述符，一定是当前可用文件描述符中的最小值， dup2可以指定
4. fcntl
   

   #include <fcntl.h>
   int fcntl(int fd, int cmd, .../* int arg */ );
   出错返回-1
   

   fcntl函数有5种功能

   1. 复制一个已有的描述符
   2. 获取/设置文件描述符标志
   3. 获取/设置文件状态标志
   4. 获取/设置异步io所有权
   5. 获取/设置记录锁
5. /dev/fd的作用
   

   /dev/fd文件主要由shell使用，能用处理其他路径名同样的方式处理标准输入和输出

3.7.3 charpter4

3.7.4 charpter5 标准io库

3.7.5 chapter6 系统数据文件和信息

1. unix系统中有大量与系统有关的数据文件，他们都有一套例程来访问这些系统数据文件
   

   如图：

   

2. 系统标示uname
   

   uname返回与主机和操作系统相关的信息

   TODO
   

3. 时间和日期例程
   
   1. 有一套函数来获取时间，他们的关系如图：
      

      

      其中的设计的数据结构有：

      time_t // 从1970年1月1日以来的秒数
      
      struct timeval {
        time_t       tv_sec;   /* seconds since Jan. 1, 1970 */
        suseconds_t  tv_usec;  /* and microseconds */
      };
      
      struct timespec {
        time_t  tv_sec;     /* seconds */
        long    tv_nsec;    /* and nanoseconds */
      };
      
      struct tm {
        int tm_sec;     /* seconds (0 - 60) */
        int tm_min;     /* minutes (0 - 59) */
        int tm_hour;    /* hours (0 - 23) */
        int tm_mday;    /* day of month (1 - 31) */
        int tm_mon;     /* month of year (0 - 11) */
        int tm_year;    /* year - 1900 */
        int tm_wday;    /* day of week (Sunday = 0) */
        int tm_yday;    /* day of year (0 - 365) */
        int tm_isdst;   /* is summer time in effect? */
        char *tm_zone;  /* abbreviation of timezone name */
        long tm_gmtoff; /* offset from UTC in seconds */
      }
      

      一般获取时间的流程是：用相关函数获取前三个结构体后，通常要调用相关函数转换为 第四个结构struct tm, 最后还可以把tm格式化输出

4. 进程环境
   

3.7.6 chapter7 进程环境

1. 进程启动
   
   • 启动例程 C程序总是从main函数开始执行，当内核执行C程序时(exec函数),在调用main函数前先调用一个 特殊的启动例程。该例程从内核取得命令行参数和环境变量值，为调用main函数做好准备。 连接器将该启动例程指定为C程序的起始地址。
2. 进程终止
   

   • 有8种方法来使进程终止，其中五种为正常终止：

     1. 从main返回
     2. 调用exit
     3. 调用_exit或Exit
     4. 最后一个线程从其启动例程返回
     5. 从最后一个线程调用pthread_exit

     另外三种为异常终止:

     1. 调用abort
     2. 接到一个信号
     3. 最后一个线程对取消请求做出响应

   • exit与_exit/_Exit

     1. exit总是执行一个标准I/O库的清理关闭操作：对所有打开流调用fclose函数。而_exit和Exit 则直接进入内核
     2. exit和_Exit是ISO C说明的，而exit是POSIX.1说明的,所以他们的头文件不一样

     #include <stdlib.h>
     
     void
     exit(int status);
     
     void
     _Exit(int status);
     
     
     
     #include <unistd.h>
     
     void
     _exit(int status);
     

   • return与exit main函数返回一个整型值与用该值调用exit是等价的。于是main函数中exit(0)等价于return(0)， 所以一般在main中使用return而不是exit。但是某些情况也需要exit:

     

   • atexit 进程可以通过atexit函数来注册终止处理函数 main调用exit后，exit会自动调用调用进程 登记的终止处理函数:

     NAME
     atexit -- register a function to be called on exit
     
     SYNOPSIS
     #include <stdlib.h>
     
     int
     atexit(void (*function)(void));
     
     int
     atexit_b(void (^function)(void));
     

     有一个要注意的点是：atexit注册的顺序和exit调用的顺序相反,如：

     #include "apue.h"
     
     static void my_exit1(void);
     static void my_exit2(void);
     
     int
     main()
     {
       if (atexit(my_exit1) != 0)
         err_sys("can't register myexit1 ");
       if (atexit(my_exit2) != 0)
         err_sys("can't register myexit2 ");
       if (atexit(my_exit2) != 0)
         err_sys("can't register myexit2 ");
     
       printf("main is done\n");
       return 0;
     }
     
     static void my_exit1() 
     {
       printf("my_exit1\n") ;
     }
     
     static void my_exit2() 
     {
       printf("my_exit2\n") ;
     }
     
     

   • 一个C程序的启动和终止过程可以表示为下图：

     可以看到，exit会首先调用各种终止处理程序，然后关闭所有打开流。而且，所有的程序都是从 exec开始的，也就是说，内核使得程序执行的唯一方法是调用一个exec函数。进程自愿终止的唯一 方法是显示或隐式的(通过_exit)调用_exit或Exit。当然，进程也可以非自愿地由一个信号 使其终止

3. 进程环境表
   
   • 每个程序都接收到一张环境表，全局变量environ指向了这张表：

   与环境表相关的函数有如下：

   #include <stdlib.h>
   
   char *
   getenv(const char *name);
   
   int
   setenv(const char *name, const char *value, int overwrite);
   
   int
   putenv(char *string);
   
   int
   unsetenv(const char *name);
   
   

   

   这些函数的执行细节如下：

   

   

4. TODO 内存布局
   

   典型的进程内存布局如图：

   

   可以用size命令来查看：

5. TODO 共享库
   
6. 内存分配
   

   ISO C说明了3个用于存储空间动态分配的函数:

   #include <stdlib.h>
   
   void *
   calloc(size_t count, size_t size);
   
   void
   free(void *ptr);
   
   void *
   malloc(size_t size);
   
   void *
   realloc(void *ptr, size_t size);
   
   void *
   reallocf(void *ptr, size_t size);
   
   void *
   valloc(size_t size);
   
   void *
   aligned_alloc(size_t alignment, size_t size);
   

   还有很多替代品:

   

7. TODO setjmp和longjmp
   
8. 资源限制相关函数
   
   • 每个进程都有一组资源限制,相关函数和数据结构有:

   #include <sys/resource.h>
   
   int
   getrlimit(int resource, struct rlimit *rlp);
   
   int
   setrlimit(int resource, const struct rlimit *rlp);
   
   struct rlimit {
     rlim_t  rlim_cur;       /* current (soft) limit */
     rlim_t  rlim_max;       /* hard limit */
   };
   

   其规则是：cur不能高于max;max不能小于cur;普通用户只用往少了调.

   • 资源限制会继承到子进程

3.7.7 chapter8 进程控制

1. fork
   

   #include "apue.h"
   
   int globvar = 6;
   char buf[] = "a write to stdout\n";
   
   int
   main()
   {
     int var;
     pid_t pid;
   
     var = 88;
     if (write(STDOUT_FILENO, buf, sizeof(buf)) != sizeof(buf))
       err_sys("write error");
     printf("before fork\n");
   
     if ((pid = fork()) < 0)
       err_sys("fork error");
     else if (pid == 0) {
       buf[0] = 'b';
       globvar++;
       var++;
     } else {
       sleep(2);
     }
   
     printf("pid = %ld, globvar = %d, var = %d\n", (long)getpid(), globvar, var);
     printf("%s\n", buf);
     sleep(2);
     return 0;
   }
   

   ~/l/a/a/m/chapter8 ❯❯❯ ./a.out                                          14:43:18
   a write to stdout
   before fork
   pid = 68796, globvar = 7, var = 89
   pid = 68795, globvar = 6, var = 88
   
   ~/l/a/a/m/chapter8 ❯❯❯ ./a.out > temp.out                               14:43:24
   ~/l/a/a/m/chapter8 ❯❯❯ cat temp.out                                     14:43:49
   a write to stdout
   before fork
   pid = 68799, globvar = 7, var = 89
   before fork
   pid = 68798, globvar = 6, var = 88
   
   # 俩个结果不同是因为重定向标准输出后变为全缓冲了，所以子进程
   # 该io缓冲中还有before fork
   

   • fork中，父进程的很多属性由子进程继承：

     但也有很多区别：

     

2. exit和终止状态
   

   chapter7说到终止进程的方法有8种，5种正常终止和3种异常终止。不管进程以8种中的哪种终止， 最后都会执行到内核中的同一段代码，这段代码为进程关闭所有的打开描述符，释放它使用的内存。 不仅如此，任何一种终止方法都实现了把终止进程的终止状态通知给父进程机制的机制。在正常终止 的情况下，main函数中return 语句返回的那个status叫退出状态，退出状态会传递给_exit函数， 最后由_{exit函数返回}。父进程可以使用wait或waitpid函数取得这个状态。posix.1还规定了一些 宏来查看终止状态：

   

3. wait和waitpid
   

   #include <sys/wait.h>
   
   pid_t
   wait(int *stat_loc);
   
   pid_t
   wait3(int *stat_loc, int options, struct rusage *rusage);
   
   pid_t
   wait4(pid_t pid, int *stat_loc, int options, struct rusage *rusage);
   
   pid_t
   waitpid(pid_t pid, int *stat_loc, int options);
   
   成功返回进程ID,出错返回0或-1
   

   waitpid与wait的主要不同是：

   wait3和wait4比上面两个函数多了一个功能：允许内核返回由终止进程及其所有子进程使用的资源情况

4. TODO 孤儿进程和僵尸进程
   

   如果想fork一个子进程，但是又不想调用wait来等待它终止，那么可以调用两次fork来达到这种效果(193页)

5. exec函数
   

   #include <unistd.h>
   
   extern char **environ;
   
   int
   execl(const char *path, const char *arg0, ... /*, (char *)0 */);
   
   int
   execle(const char *path, const char *arg0, ...
          /*, (char *)0, char *const envp[] */);
   
   int
   execlp(const char *file, const char *arg0, ... /*, (char *)0 */);
   
   int
   execv(const char *path, char *const argv[]);
   
   int
   execvp(const char *file, char *const argv[]);
   
   int
   execvP(const char *file, const char *search_path, char *const argv[]);
   

   各个函数之间的关系如下：

   

   • 注意事项：
     1. file参数:
        • 如果file包含/，就将其视为路径名
        • 否则就按PATH环境变量指定的目录找名为file的可执行文件
     2. 助记：
        • 字母p(ath)表示取filename作为参数，并且用PATH环境变量寻找可执行文件。
        • 字母l(ist)表示该函数取一个参数表，与互斥
        • 字母(arg)v表示取一个argv[]矢量
        • 字母e(nvp)表示该函数取envp[]数组，而不使用当前环境

   • 调用exec并不创建新进程，所以前后的进程ID并没有改变，只是用磁盘上的一个新程序替换了当前进程 的正文段，数据段，堆栈段。新进程从调用进程继承了下列属性：

     对打开文件的处理与每个描述符的执行时关闭标志值有关。

6. TODO 更改用户ID和更改组ID
   
7. TODO 解释器与system
   
8. TODO 进程时间(程序8-31)
   

3.7.8 TODO chapter9 进程关系 PASS

3.7.9 chapter10 信号

1. 概念
   
   • 中断 操作系统中一个非常重要的概念就是中断，中断可以让程序执行异步操作。异步和同步相对，同步一般 意味着需要等待，所以异步可以带来很多好处。中断是指计算机在执行期间，系统内发生任何非寻常的 或非预期的急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待 处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。引起中断发生的事件被称为中断 源。中断源向CPU发出的请求中断处理信号称为中断请求，而CPU收到中断请求后转到相应的事件处理 程序称为中断响应。中断分为：
     1. 硬中断 通过硬件产生相应的中断请求，称为硬中断。
     2. 软中断
   • 软中断 软中断的概念主要来源于UNIX系统。软中断是对应于硬中断而言的。它是在通信进程之间通过模拟硬中断 而实现的一种通信方式。中断源发出软中断信号后，CPU或者接收进程在“适当的时机”进行中断处理或者 完成软中断信号所对应的功能。这里“适当的时机”，表示接收软中断信号的进程须等到该接收进程得到 处理器之后才能进行如果该接收进程是占据处理器的，那么，该接收进程在接收到软中断信号后将立即 转去执行该软中断信号所对应的功能。
   • 信号
     1. 本质 信号是在软件层次上对中断机制的一种模拟，在原理上，一个进程收到一个信号与处理器收到一个 中断请求可以说是一样的。
     2. 来源
        • 硬件来源 比如我们按下了键盘或者其它硬件故障
        • 软件来源 最常用发送信号的系统函数是kill, raise, alarm和setitimer以及sigqueue函数， 软件来源还包括一些非法运算等操作。
     3. 分类
        • 按可靠性：可靠和不可靠
        • 按实时性：实时和非实时
2. 信号产生条件
   
   1. 按下某些终端键
   2. 硬件异常产生信号：除0、无效的内存引用
   3. kill系统调用
   4. kill命令行命令
   5. 当检测到某种软件条件已经发生
3. 处理信号的三种方式
   
   1. 忽略 有两种不能忽略SIGKILL SIGSTOP
   2. 捕捉信号 收到信号时，调用预先设定好的用户函数

   3. 执行系统默认动作

      

4. signal函数
   

   signal函数表示为sig信号设置信号处理函数

   #include <signal.h>
   
   void (*signal(int sig, void (*func)(int)))(int);
   
   or in the equivalent but easier to read typedef'd version:
   
   typedef void (*sig_t) (int);
   
   sig_t
   signal(int sig, sig_t func);
   

   参数sig：信号名 func：新的信号调用函数, 可以是自定义的用户空间函数， 也可以是SIG_IGN(ignore),SIG_DFL(default) 返回值：旧的信号处理函数,或SIG_{ERR表示出错}

5. fork和exec时信号的继承
   
   • fork 当一个进程调用fork时，其子进程继承父进程的信号处理方式。因为子进程在开始时复制了父进程 的内存映像，所以信号捕捉函数的地址在子进程中是有意义的。
   • exec 当调用exec运行新程序时，除非 调用 exec的进程忽略该信号，否则所有信号都被设置为它们 的默认动作
6. 可靠信号与信号阻塞
   

   早期的unix中，信号是不可靠的,这里的不可靠指的是：

   1. 信号可能会丢失，因为没有保存(阻塞)信号的能力
   2. 进程每次接到信号对其进行处理时，随机该信号动作的动作重置为默认值

   4.2BSD对信号进行了改动，提供了可靠的信号机制：

   1. 可靠信号
      
      • 产生信号 当造成信号的事件发生时，为进程产生一个信号
      • 递送信号 当内核在进程表中以某种形式设置标志表明产生信号时，称为递送了信号
      • 阻塞信号的递送 进程可以设置信号为阻塞的，这种情况下，信号的递送被阻塞，
      • 未决pending 产生信号开始，到递送信号完成之前；或者是信号被进程阻塞(而且进程对该信号的动作是系统默认 动作或捕捉该信号),则该进程为未决状态
      • 多次递送信号 如果在进程解除对某个信号的阻塞之前，信号递送了多次，则称信号进行了排队。除非支持posix实时 扩展，否则大多数uinx并不对信号排队，而是只递送这种信号一次
7. 被信号中断的系统调用
   

   早期unix系统的一个特性是：如果进程执行一个 低速系统调用 而阻塞期间捕捉到一个 信号，则该系统调用就被中断而不再继续执行。该系统调用返回出错并且errno设置为 EINTR。TODO: 非低速系统调用自动重启吗？ 其中低速系统调用是指可能会使进程永远阻塞的一类系统调用，包括以下几类：

   为了帮助应用程序，使得其不必处理被中断的系统调用，4.2BSD开始引入的中断系统调用的自动重启, 下面为几种实现所提供的与信号有关的函数与语义：

   

8. TODO 可重入函数
   
9. kill和raise
   

   #include <signal.h>
   
   /* 将信号发送给进程或进程组 */
   int
   kill(pid_t pid, int sig);
   
   
   
   /* 进程向自己发送信号 */
   #include <signal.h>
   
   int
   raise(int sig);
   

   kill的pid参数有如下几种情况：

   1. pid > 0 将信号发送给进程id为pid的进程
   2. pid == 0 发送给该进程所在进程组的所有进程,发送进程必须有权限
   3. pid < 0 发送给进程中ID为-pid的所有进程，调用进程必须有权限
   4. pid == -1 发送给调用进程有权限发送信号的所有进程

   注：上面所说的所有进程，不包括系统进程集(内核进程和init进程(pid为1))

10. alarm和pause
    

    #include <unistd.h>
    
    /* 设置一个定时器，当超时时产生一个SIGALRM信号 */
    unsigned
    alarm(unsigned seconds);
    
    
    /* 使调用进程挂起直到捕捉到一个信号 */
    #include <unistd.h>
    
    int
    pause(void);
    

11. 信号集
    

    用来表示信号的数据结构为信号集(sigset), posix定义了下列五个处理信号集的函数:

    #include <signal.h>
    
    int
    sigaddset(sigset_t *set, int signo);
    
    int
    sigdelset(sigset_t *set, int signo);
    
    int
    sigemptyset(sigset_t *set);
    
    int
    sigfillset(sigset_t *set);
    
    int
    sigismember(const sigset_t *set, int signo);
    

12. sigpending
    

    sigpending返回当前未决的信号

    #include <signal.h>
    
    int
    sigpending(sigset_t *set);
    

    10-15.c

13. sigaction函数
    

    sigaction函数的功能是检查或修改(或检查并修改)与指定信号相关联的处理动作。

    #include <signal.h>
    
    /* 复制自macos 下的man，与书上有区别 */
    struct  sigaction {
      union __sigaction_u __sigaction_u;  /* signal handler */
      /* 如果sa_handler包含自定义的捕捉函数，则sa_mask字段说明了一个信号集
       * 在调用捕捉函数之前阻塞这些信号，调用完后再恢复
       */
      sigset_t sa_mask;               /* signal mask to apply */
      /* 对信号sig进行处理的各种选项,具体见代码下的图 */
      int     sa_flags;               /* see signal options below */
    };
    
    union __sigaction_u {
      void    (*__sa_handler)(int);
      void    (*__sa_sigaction)(int, siginfo_t *,
                                void *);
    };
    
    #define sa_handler      __sigaction_u.__sa_handler
    #define sa_sigaction    __sigaction_u.__sa_sigaction
    
    /* 要修改的动作存在act，上一个动作返回到oact */
    int
    sigaction(int sig, const struct sigaction *restrict act,
              struct sigaction *restrict oact);
    

    

14. TODO sigsetjmp和siglongjmp
    
15. sigsuspend
    

    当我们希望保护代码临界区不被某些信号中断，可以用sigsuspend函数

    #include <signal.h>
    
    int
    sigsuspend(const sigset_t *sigmask);
    

    它的作用是在执行完临界区代码后原子地恢复信号屏蔽字，然后使得进程休眠。 这样就可以防止sigprocmask函数恢复屏蔽字和调用pause接受进程之间的空档

16. TODO abort
    

    #include <stdlib.h>
    
    void
    abort(void);
    

17. TODO system
    
18. TODO sleep
    

    sleep函数是通过alarm和信号实现的

19. sigqueue
    

    可以对信号实现排队

20. 小结
    

    信号用于大多数复制的应用程序中，理解进行信号处理的原因和方式对于高级unix编程 极其重要

3.7.10 TODO chapter11 线程

1. 线程的优点
   

   典型的unix进程在某一时刻只能做一件事情。有了线程后，程序设计就可以把程序设计成 在某一时刻能够做不止一件事，每个线程处理各自独立的任务。这中方法有很多好处：

   1. 可以简化处理异步事件的代码。
   2. 多个线程可以自动地访问相同的存储地址空间和文件描述符,不像进程那么复杂
   3. 有些问题可以分解从而提高整个程序的吞吐量
   4. 可以改善交互程序的响应时间

   单cpu也能得到多线程编程模型的好处

2. 创建线程
   

   每个线程都有一个线程ID pthread_t，线程创建相关函数有：

   #include <pthread.h>
   
   /* 创建新线程 */
   int
   pthread_create(pthread_t *thread,       //保存新线程的id
                  const pthread_attr_t *attr,  // 定制各种不同的线程属性
                  void *(*start_routine)(void *), //新线程从start_rtn函数开始运行
                  void *arg); //start_rtn参数
   
   // 判断线程id是否相等, 不能直接==，因为pthread_t可能是结构体(具体实现)
   int pthread_equal(pthread_t tid1, pthread_t tid2);
   
   // 获得自身的线程ID
   pthread_t
   pthread_self(void);
   

   新创建的线程可以访问进程的地址空间，并且继承调用线程的浮点环境和信号屏蔽字，但线程的 挂起信号集被清除

3. 终止线程
   

   下列方式会终止整个进程：

   1. 进程中任意线程调用了exit、_exit或Exit
   2. 线程收到信号，并且动作是终止进程

   下列三个方法能在不终止整个进程的情况下停止单个线程：

   1. 线程可以简单地从启动例程返回(return)，返回值是线程的退出码

      #include <pthread.h>
      
      void
      pthread_exit(void *value_ptr);
      

      进程的其他线程通过pthread_{join等待线程结束并访问valueptr}

      #include <pthread.h>
      
      int
      pthread_join(pthread_t thread, void **value_ptr);
      

   2. 线程可以被同一进程的其他线程取消：

      #include <pthread.h>
      
      int
      pthread_cancel(pthread_t thread);
      

   3. 线程调用pthread_exit
4. 分离线程
   

   #include <pthread.h>
   
   int
   pthread_detach(pthread_t thread);
   

   默认情况下，线程的终止状态会保存知道对线程调用pthread_join, 调用pthread_detach后， 线程会被分离，线程的底层存储资源可以在线程终止时立即回收。分离后不能再对该线程调用 pthread_join.

5. TODO 线程清理处理程序
   
6. 线程同步
   
   1. 自旋锁
      
      • 概念 自旋锁是通过在获取锁前一直处于忙等状态的一种锁。
      • 适用情况
        1. 自旋锁适用于锁被持有的时间短，而且线程并不希望在重新调度上化太多成本
        2. 自旋锁用在非抢占式内核中是很有用的：除了提供互斥机制，他们还会阻塞中断
        3. 自旋锁在用户层并不一定非常有用，因为获取自旋锁的线程可能会被取消调度而 进入休眠状态，那么阻塞在锁上的其他线程自旋的时间就可能会比预期的更长
      • 实现 一般可以通过使用 测试并设置 指令实现
   2. 互斥量
      

      互斥量保证同一时间只有一个线程访问数据。如果释放互斥量时有一个以上的线程阻塞，那么所有 该锁上的阻塞线程都会变成可运行状态，第一个变为运行的线程可以对互斥量加锁

      #include <pthread.h>
      
      int
      pthread_mutex_init(pthread_mutex_t *mutex,
                         const pthread_mutexattr_t *attr);
      
      int
      pthread_mutex_destroy(pthread_mutex_t *mutex);
      
      int
      pthread_mutex_lock(pthread_mutex_t *mutex);
      
      int
      pthread_mutex_trylock(pthread_mutex_t *mutex);
      
      int
      pthread_mutex_unlock(pthread_mutex_t *mutex);
      

   3. 读写锁
      
   4. 条件变量
      
   5. 屏障
      
7. TODO 线程控制
   

3.7.11 TODO chapter12

3.7.12 守护进程(daemon)

1. 编程规则(创建过程)
   
   1. 调用umask将文件模式创建屏蔽字设置为一个固定值（通常是0）。 因为继承来的屏蔽字可能被设置为拒绝某些权限
   2. 调用fork，然后使父进程exit。 理由：
      • 当守护进程由一条简单的shell命令启动，父进程exit会让shell认为这条命令已经 执行完毕。
      • fork保证子进程不是一个进程组的组长（继承了父进程的进程组ID，但是获得了新的进程ID）, 为第三步做准备
   3. 调用setsid创建一个新的会话。 作用：
      • 成为新会话的首进程
      • 成为一个新进程组的组长进程
      • 没有控制终端
   4. 将当前工作目录改为根目录 因为父进程的当前工作目录可能在一个挂载的文件系统中，如果不改变，那么这个文件系统在 守护进程运行过程中都不能被卸载
   5. 关闭不再需要的文件描述符。 和父进程脱离联系
   6. 将0，1，2文件描述符重定向到/dev/null
2. 出错(日志)记录
   

   守护进程存在的一个问题是如何处理出错信息,首先守护进程肯定不能把日志直接输出控制台，然后， 我们也不希望每个守护进程一个日志文件，这样太难管理。为此，大多数守护进程都使用syslog设施：

   可以看到，有三种途径产生日志消息：

   

3. 单例守护进程
   

   使用文件和记录锁

4. 守护进程惯例
   

   

3.8.1 第四章

3.8.2 5

3.8.3 ipc

3.9.1 进程管理与调度

1. task_struct
   

   struct task_struct {
      - TASK_RUNNING： 可运行状态。该状态确保进程可以立即运行，而无需等待外部条件
      - TASK_INTERRRUPTIBLE：针对等待某事件或其他资源的睡眠进程设置的。在内核发送信号给
        进程表明事件已经发生时，进程状态变为TASK_RUNNING。
      - TASK_UNINTERRRUPTIBLE：因内核指示而停用的进程，不能由外部信号唤醒，只能由内核亲自唤醒
      - TASK_STOPPED ：特意停止运行，如调试
      - TASK_TRACED：区分停止的进程中被调试的进程和常规的进程
      - EXIT_ZOMEIE 僵尸进程
      - EXIT_DEAD wait系统调用已经发出，在进程完全从系统中移除之前的状态，只在多个进程对同一进程
        发出wait调用时才有意义
     volatile long state;  /* -1 unrunnable, 0 runnable, >0 stopped */
     void *stack;
     atomic_t usage;
     unsigned int flags; /* per process flags, defined below */
     unsigned int ptrace;
   
     int lock_depth;   /* BKL lock depth */
   
   #ifdef CONFIG_SMP
   #ifdef __ARCH_WANT_UNLOCKED_CTXSW
     int oncpu;
   #endif
   #endif
   
     int prio, static_prio, normal_prio;
     struct list_head run_list;
     const struct sched_class *sched_class;
     struct sched_entity se;
   
   #ifdef CONFIG_PREEMPT_NOTIFIERS
     /* list of struct preempt_notifier: */
     struct hlist_head preempt_notifiers;
   #endif
   
     unsigned short ioprio;
     /*
      * fpu_counter contains the number of consecutive context switches
      * that the FPU is used. If this is over a threshold, the lazy fpu
      * saving becomes unlazy to save the trap. This is an unsigned char
      * so that after 256 times the counter wraps and the behavior turns
      * lazy again; this to deal with bursty apps that only use FPU for
      * a short time
      */
     unsigned char fpu_counter;
     s8 oomkilladj; /* OOM kill score adjustment (bit shift). */
   #ifdef CONFIG_BLK_DEV_IO_TRACE
     unsigned int btrace_seq;
   #endif
   
     unsigned int policy;
     cpumask_t cpus_allowed;
     unsigned int time_slice;
   
   #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
     struct sched_info sched_info;
   #endif
   
     struct list_head tasks;
     /*
      * ptrace_list/ptrace_children forms the list of my children
      * that were stolen by a ptracer.
      */
     struct list_head ptrace_children;
     struct list_head ptrace_list;
   
     struct mm_struct *mm, *active_mm;
   
   /* task state */
     struct linux_binfmt *binfmt;
     int exit_state;
     int exit_code, exit_signal;
     int pdeath_signal;  /*  The signal sent when the parent dies  */
     /* ??? */
     unsigned int personality;
     unsigned did_exec:1;
     pid_t pid;
     pid_t tgid;
   
   #ifdef CONFIG_CC_STACKPROTECTOR
     /* Canary value for the -fstack-protector gcc feature */
     unsigned long stack_canary;
   #endif
     /* 
      * pointers to (original) parent process, youngest child, younger sibling,
      * older sibling, respectively.  (p->father can be replaced with 
      * p->parent->pid)
      */
     struct task_struct *real_parent; /* real parent process (when being debugged) */
     struct task_struct *parent; /* parent process */
     /*
      * children/sibling forms the list of my children plus the
      * tasks I'm ptracing.
      */
     struct list_head children;  /* list of my children */
     struct list_head sibling; /* linkage in my parent's children list */
     struct task_struct *group_leader; /* threadgroup leader */
   
     /* PID/PID hash table linkage. */
     struct pid_link pids[PIDTYPE_MAX];
     struct list_head thread_group;
   
     struct completion *vfork_done;    /* for vfork() */
     int __user *set_child_tid;    /* CLONE_CHILD_SETTID */
     int __user *clear_child_tid;    /* CLONE_CHILD_CLEARTID */
   
     unsigned int rt_priority;
     cputime_t utime, stime, utimescaled, stimescaled;
     cputime_t gtime;
     cputime_t prev_utime, prev_stime;
     unsigned long nvcsw, nivcsw; /* context switch counts */
     struct timespec start_time;     /* monotonic time */
     struct timespec real_start_time;  /* boot based time */
   /* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */
     unsigned long min_flt, maj_flt;
   
       cputime_t it_prof_expires, it_virt_expires;
     unsigned long long it_sched_expires;
     struct list_head cpu_timers[3];
   
   /* process credentials */
     uid_t uid,euid,suid,fsuid;
     gid_t gid,egid,sgid,fsgid;
     struct group_info *group_info;
     kernel_cap_t   cap_effective, cap_inheritable, cap_permitted;
     unsigned keep_capabilities:1;
     struct user_struct *user;
   #ifdef CONFIG_KEYS
     struct key *request_key_auth; /* assumed request_key authority */
     struct key *thread_keyring; /* keyring private to this thread */
     unsigned char jit_keyring;  /* default keyring to attach requested keys to */
   #endif
     char comm[TASK_COMM_LEN]; /* executable name excluding path
                - access with [gs]et_task_comm (which lock
                  it with task_lock())
                - initialized normally by flush_old_exec */
   /* file system info */
     int link_count, total_link_count;
   #ifdef CONFIG_SYSVIPC
   /* ipc stuff */
     struct sysv_sem sysvsem;
   #endif
   /* CPU-specific state of this task */
     struct thread_struct thread;
   /* filesystem information */
     struct fs_struct *fs;
   /* open file information */
     struct files_struct *files;
   /* namespaces */
     struct nsproxy *nsproxy;
   /* signal handlers */
     struct signal_struct *signal;
     struct sighand_struct *sighand;
   
     sigset_t blocked, real_blocked;
     sigset_t saved_sigmask;   /* To be restored with TIF_RESTORE_SIGMASK */
     struct sigpending pending;
   
     unsigned long sas_ss_sp;
     size_t sas_ss_size;
     int (*notifier)(void *priv);
     void *notifier_data;
     sigset_t *notifier_mask;
   #ifdef CONFIG_SECURITY
     void *security;
   #endif
     struct audit_context *audit_context;
     seccomp_t seccomp;
   
   /* Thread group tracking */
       u32 parent_exec_id;
       u32 self_exec_id;
   /* Protection of (de-)allocation: mm, files, fs, tty, keyrings */
     spinlock_t alloc_lock;
   
     /* Protection of the PI data structures: */
     spinlock_t pi_lock;
   
   #ifdef CONFIG_RT_MUTEXES
     /* PI waiters blocked on a rt_mutex held by this task */
     struct plist_head pi_waiters;
     /* Deadlock detection and priority inheritance handling */
     struct rt_mutex_waiter *pi_blocked_on;
   #endif
   
   #ifdef CONFIG_DEBUG_MUTEXES
     /* mutex deadlock detection */
     struct mutex_waiter *blocked_on;
   #endif
   #ifdef CONFIG_TRACE_IRQFLAGS
     unsigned int irq_events;
     int hardirqs_enabled;
     unsigned long hardirq_enable_ip;
     unsigned int hardirq_enable_event;
     unsigned long hardirq_disable_ip;
     unsigned int hardirq_disable_event;
     int softirqs_enabled;
     unsigned long softirq_disable_ip;
     unsigned int softirq_disable_event;
     unsigned long softirq_enable_ip;
     unsigned int softirq_enable_event;
     int hardirq_context;
     int softirq_context;
   #endif
   #ifdef CONFIG_LOCKDEP
   # define MAX_LOCK_DEPTH 30UL
     u64 curr_chain_key;
     int lockdep_depth;
     struct held_lock held_locks[MAX_LOCK_DEPTH];
     unsigned int lockdep_recursion;
   #endif
   
   /* journalling filesystem info */
     void *journal_info;
   
   /* stacked block device info */
     struct bio *bio_list, **bio_tail;
   
   /* VM state */
     struct reclaim_state *reclaim_state;
   
     struct backing_dev_info *backing_dev_info;
   
     struct io_context *io_context;
   
     unsigned long ptrace_message;
     siginfo_t *last_siginfo; /* For ptrace use.  */
   #ifdef CONFIG_TASK_XACCT
   /* i/o counters(bytes read/written, #syscalls */
     u64 rchar, wchar, syscr, syscw;
   #endif
     struct task_io_accounting ioac;
   #if defined(CONFIG_TASK_XACCT)
     u64 acct_rss_mem1;  /* accumulated rss usage */
     u64 acct_vm_mem1; /* accumulated virtual memory usage */
     cputime_t acct_stimexpd;/* stime since last update */
   #endif
   #ifdef CONFIG_NUMA
       struct mempolicy *mempolicy;
     short il_next;
   #endif
   #ifdef CONFIG_CPUSETS
     nodemask_t mems_allowed;
     int cpuset_mems_generation;
     int cpuset_mem_spread_rotor;
   #endif
   #ifdef CONFIG_CGROUPS
     /* Control Group info protected by css_set_lock */
     struct css_set *cgroups;
     /* cg_list protected by css_set_lock and tsk->alloc_lock */
     struct list_head cg_list;
   #endif
   #ifdef CONFIG_FUTEX
     struct robust_list_head __user *robust_list;
   #ifdef CONFIG_COMPAT
     struct compat_robust_list_head __user *compat_robust_list;
   #endif
     struct list_head pi_state_list;
     struct futex_pi_state *pi_state_cache;
   #endif
     atomic_t fs_excl; /* holding fs exclusive resources */
     struct rcu_head rcu;
   
     /*
      * cache last used pipe for splice
      */
     struct pipe_inode_info *splice_pipe;
   #ifdef  CONFIG_TASK_DELAY_ACCT
     struct task_delay_info *delays;
   #endif
   #ifdef CONFIG_FAULT_INJECTION
     int make_it_fail;
   #endif
     struct prop_local_single dirties;
   }
   

2. 命名空间
   
   1. 概念
      

      传统上，在linux以及其他衍生的unix变体中，很多资源是全局管理的。比如内核必须管理一个全局pid 列表来唯一标识一个进程。这种数据管理方式在有些情况下会有一些限制。如果提供云计算服务的供应商 打算向用户提供linux计算机的root权限，这种管理方式一般需要使用kvm或vmware提供的虚拟化环境， 但是这些方法的资源分配做的不是非常好。 而命名空间提供了一种不同的解决方案，所需的资源较少，它 只使用一个内核在一台物理机上运作，前面那种全局管理的资源都使用命名空间抽象隔离起来。 本质上，命名空间建立了系统的不同视图:

      1. 
         

         

         如上图所示，系统上有3个命名空间，一个父命名空间和两个子命名空间，每个空间都有各自的1，2，3号 进程，而子命名空间在父命名空间也有其进程的映射，如左边的字命名空间的1号映射为父进程空间中的4号

   2. 创建
      

      有两种方法可以创建新的命名空间

      1. fork或clone
      2. unshare系统调用
   3. 实现
      

      命名空间的实现需要两个部分：

      1. 每个子系统的命名空间结构
      2. 将给定进程关联到所属各个命名空间的机制
      1. 
         

         

3. 进程ID
   
   1. 进程ID类型
      
      • PID
      • 线程组ID（TGID）
      • 进程组ID（GID） 简化了向一个组所有成员发送信号
      • 会话ID（SID）
   2. 支持命名空间的PID
      
      • 全局ID 内核本身和初始命名空间中的唯一ID号，每个ID都有一个唯一的全局ID
      • 局部ID 某个特定命名空间的ID，不同的命名空间可能不唯一
   3. 相关数据结构（图）
      

      

      

      本质上，这两张图就为了完成两件事情：

      1. 给出局部数字ID和对应的命名空间，找到对应的task_struct 这是通过pid_{hash出发来完成的}: pid_hash->struct upid->(container_of机制)struct pid->task_struct
      2. 给出task_{struct和命名空间}，找upid task_struct->struct pid->numbers[ns.level]->upid
   4. 创建一个pid的过程
      

      从建立进程的命名空间开始，一直到初始的全局命名空间，内核会为此间的每个命名空间分别创建一个 局部PID（struct upid), 并把upid全映射到pid_hash中

4. 进程管理相关系统调用
   
   1. 进程复制
      
      1. 进程复制主要的系统调用是fork和clone，vfork在fork使用了COW后速度不再有优势
         

         • COW(copy-on-write) 该技术利用了下述事实：进程通常只使用了内存页的一小部分。在调用fork时，一般来说内核需要 对父进程的每个内存页都为子进程创建一个副本。这有样有两个缺点：

           1. 使用了大量的内存
           2. 复制操作耗费了很长的时间

           COW机制使得内核可以尽可能延迟内存页的复制，更重要的是，在很多情况下根本不需要复制，这 节省了大量的内存和时间

         • fork, 创建子进程, 该子进程是父进程的完整副本

           asmlinkage int sys_fork(struct pt_regs regs)
           {
             return do_fork(SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
           }
           

         • clone 产生线程，可以对父子进程的共享、复制进行精确控制

           asmlinkage int sys_clone(struct pt_regs regs)
           {
             unsigned long clone_flags;
             unsigned long newsp;
             int __user *parent_tidptr, *child_tidptr;
           
             clone_flags = regs.ebx;
             newsp = regs.ecx;
             parent_tidptr = (int __user *)regs.edx;
             child_tidptr = (int __user *)regs.edi;
             if (!newsp)
               newsp = regs.esp;
             return do_fork(clone_flags, newsp, &regs, 0, parent_tidptr, child_tidptr);
           }
           

         • 从上面代码中看到，clone和fork的区别主要在于：
           1. clone的标志不再是硬编码的,而是通过各种寄存器把参数传递到系统调用，
           2. clone不再复制父进程的栈地址，而是可以指定新的栈地址。在创建线程时可能需要这样做，
      2. do_fork
         
         • fork和clone处理完准备工作后都调用了do_fork函数:

         /*
          *  Ok, this is the main fork-routine.
          *
          * It copies the process, and if successful kick-starts
          * it and waits for it to finish using the VM if required.
          */
         long do_fork(
                      // 控制复制过程中的一些属性，最低字节指定了在子进程终止时
                      // 发给父进程的信号
                      unsigned long clone_flags,
                      // 用户状态下栈的起始地址,必须保证父子进程栈地址一样
                      unsigned long stack_start,
                      // 调用参数
                      struct pt_regs *regs,
                      // 用户状态下栈的大小，通常为0
                      unsigned long stack_size,
                      int __user *parent_tidptr,
                      int __user *child_tidptr)
         

         1. 实现
            

            do_{fork流程图如下}:

            1. do_{fork流程图}
               

               其中，主要工作由copy_{process完成}，copy_{process执行生成新进程的实际工作,同时根据指定的} 标志重用父进程的数据，copy_{process的主要流程图如下}：

               1. copy_{process流程图}
                  

                  

                  • 首先检查标志，特别是捕获一些没有意义的标志组合，比如CLONE_{NEWNS和CLONEFS就不} 能组合在一起；而有些标志是必须结合在一起用的，比如CLONE_{THREAD和CLONESIGHAND}、 CLONE_VM，因为创建线程必须激活信号共享,而且创建线程时也必须与父进程共享地址空间。

                  • 在检查完标志集后，调用dup_{taskstruct来建立父进程taskstruct的副本}。父子进程 的task_{struct实例只有一个成员不同}：子进程分配了新的内核栈，即task_struct->stack:

                    union thread_union {
                      struct thread_info thread_info;
                      unsigned long stack[THREAD_SIZE/sizeof(long)];
                    };
                    

                    内核栈大小默认为8K，也可配置成4K，thread_{info保存了特定与体系结构的汇编代码需要} 访问的那部分进程数据：

                    struct thread_info {
                      struct task_struct  *task;    /* main task structure */
                      struct exec_domain  *exec_domain; /* execution domain */
                      /*
                       * 我们只关注其中两个，因为其他都是硬件相关的：
                       * 1. 如果进程有待决信号则置位TIF_SIGPENDING
                       * 2. TIF_NEED_RESCHED表示该进程应该或想要调度器选择另一个进程替换本进程执行
                       */
                      __u32     flags;    /* low level flags */
                      /* 线程同步标志 */
                      __u32     status;   /* thread synchronous flags */
                      /* 当前cpu，翻译的有问题？ */
                      __u32     cpu;    /* current CPU */
                      /* 实现内核抢占 */
                      int       preempt_count;  /* 0 => preemptable, <0 => BUG */
                    
                      /* 进程可以使用的虚拟地址上限 */
                      mm_segment_t    addr_limit; 
                      /* 用于实现信号机制 */
                      struct restart_block    restart_block;
                    };
                    

                    thread_{info布局图}

                  

                  • 构建完task_struct后，内核会检查当前用户(task_struct->user)已经创建的进程数 是否超出了限制，若超出，则放弃创建进程
                  • 确定可以创建进程后，初始化一些子进程task_{struct的一些数据}
                  • 接下来会调用sched_fork。本质上，该函数会初始化一些统计字段， 并均衡下调度器负载，并把子进程设置为TASK_RUNNING(TODO:why?）
                  • 再下来就是根据标志来复制或者共享父进程的资源: ❑ copy_semundo uses the System V semaphores of the parent process if COPY_SYSVSEM is set (see Chapter 5). ❑ copy_files uses the file descriptors of the parent process if CLONE_FILES is set. Otherwise, a new files structure is generated (see Chapter 8) that contains the same information as the parent process. This information can be modified independently of the original structure. ❑ copy_fs uses the filesystem context (task_struct->fs) of the parent process if CLONE_FS is set. This is an fs_struct type structure that holds, for example, the root directory and the current working directory of the process (see Chapter 8 for detailed information). ❑ copy_sighand uses the signal handlers of the parent process (task_struct->sighand) if CLONE_SIGHAND or CLONE_THREAD is set. Chapter 5 discusses the struct sighand_struct structure used in more detail. ❑ copy_signal uses the non-handler-specific part of signal handling (task_struct->signal, see Chapter 5) together with the parent process if CLONE_THREAD is set. ❑ copy_mm causes the parent process and child process to share the same address space if COPY_MM is set. In this case, both processes use the same instance of mm_struct (see Chapter 4) to which task_struct->mm points. If copy_mm is not set, it does not mean that the entire address space of the parent process is copied. The kernel does, in fact, create a copy of the page tables but does not copy the actual contents of the pages. This is done using the COW mechanism only if one of the two processes writes to one of the pages. ❑ copy_namespaces has special call semantics. It is used to set up namespaces for the child process. Recall that several CLONE_NEWxyz flags control which namespaces are shared with the parent. However, the semantics are opposite to all other flags: If CLONE_NEWxyz is not specified, then the specific namespace is shared with the parent. Otherwise, a new namespace is generated. copy_namespace is a dispatcher that executes a copy routine for each possible namespace. The individual copy routines, however, are not too interesting because they essentially copy data or make already existing instances shared by means of reference counter management, so I will not discuss their implementation in detail. ❑ copy_thread is — in contrast to all other copy operations discussed here — an architecture- specific function that copies the thread-specific data of a process.
                  • 最后，填好子进程与父进程不同的各个成员,包括task_{struct包含的各个链表元素} cpu_{timers,待决信号列表pending}

                  copy_{process执行完毕后}，do_{fork还必须执行一些收尾工作,如前面的dofork流程图}：

                  • TODO:
   2. 内核线程
      

      内核线程是直接由内核本身启动的进程。它们并行于内核的执行，通常称为守护进程。

      1. 分类
         

         内核线程基本可以分为两类

         1. 启动后自动按特定周期间隔运行，检测特定资源的使用情况，超出或低于时采取行动
         2. 只有内核请求时才执行
      2. 主要任务
         

         内核线程主要用于执行以下任务：

         • 周期性地将修改的内存页与页来源块设备同步
         • 将很少使用的内存页写入交换区
         • 管理延时动作
         • 实现文件系统的事务日志
      3. 创建
         
         • 创建内核线程的传统方法是kernel_thread函数

         long kernel_thread(int (*fn)(void *), void *arg, unsigned long flags)
         {
           struct pt_regs regs;
         
           memset(&regs, 0, sizeof(regs));
         
           regs.regs[4] = (unsigned long) arg;
           regs.regs[5] = (unsigned long) fn;
           regs.cp0_epc = (unsigned long) kernel_thread_helper;
           regs.cp0_status = read_c0_status();
         #if defined(CONFIG_CPU_R3000) || defined(CONFIG_CPU_TX39XX)
           regs.cp0_status = (regs.cp0_status & ~(ST0_KUP | ST0_IEP | ST0_IEC)) |
             ((regs.cp0_status & (ST0_KUC | ST0_IEC)) << 2);
         #else
           regs.cp0_status |= ST0_EXL;
         #endif
         
           /* Ok, create the new process.. */
           return do_fork(flags | CLONE_VM | CLONE_UNTRACED, 0, &regs, 0, NULL, NULL);
         
         

         其中，fn函数负责帮助内核调用daemonize以转换为守护进程。步骤如下：

         1. 该函数从内核线程释放其父进程（用户进程）的所有资源（内存上下文，文件描述符），因为 不然的话这些资源会锁定到线程结束（通常时运行到关机）。而线程又不需要这些资源
         2. daemonize阻塞信号的接受
         3. 将init作为守护线程的父进程

         • 更现代的方法是辅助函数kthread_{create,kthreadrun和kthreadcreatecpu}(可指定cpu)

           struct task_struct *kthread_create(int (*threadfn)(void *data),
                                              void *data,
                                              const char namefmt[],
                                              ...)
           {
             struct kthread_create_info create;
           
             create.threadfn = threadfn;
             create.data = data;
             init_completion(&create.started);
             init_completion(&create.done);
           
             spin_lock(&kthread_create_lock);
             list_add_tail(&create.list, &kthread_create_list);
             wake_up_process(kthreadd_task);
             spin_unlock(&kthread_create_lock);
           
             wait_for_completion(&create.done);
           
             if (!IS_ERR(create.result)) {
               va_list args;
               va_start(args, namefmt);
               vsnprintf(create.result->comm, sizeof(create.result->comm),
                         namefmt, args);
               va_end(args);
             }
             return create.result;
           }
           

   3. 启动新程序
      
      • execve

      linux提供execve系统调用来通过新代码替换现存程序启动新程序，该系统调用的 入口是sys_execve函数，该函数很快将工作委托给do_execve例程。

      int do_execve(char * filename,
                    char __user *__user *argv,
                    char __user *__user *envp,
                    struct pt_regs * regs)
      

      其代码流程图如下：

      

      1. 首先，内核找到要执行文件的inode并生成一个文件描述符来打开此文件;
      2. 接下来bprm_{init处理一些管理任务}，包括：
         • mm_{alloc生成新的mmstruct地址空间}
         • init_{newcontext初始化mmstruct}
         • __{bprmmminit建立初始的栈}
      3. 然后，prepare_{binprm用于提供一些linuxbinprm结构中父进程相关的值}(特别是有效UID和GID)。 其中，linux_{binprm结构保存的是新进程的各个参数}
      4. 接下来就是复制环境和参数数组的内容

      5. 最后，search_{binaryhandler在doexecve结束时根据所要执行的文件查找适当的二进制格式}, 如果找到合适的格式，则相应的二进制处理程序负责将新程序的数据加载到旧的地址空间中(TODO 那mm_{struct有什么用}),二进制格式用下面的结构体描述：

         /*
          * This structure defines the functions that are used to load the binary formats that
          * linux accepts.
          */
           struct linux_binfmt {
             struct list_head lh;
             struct module *module;
             // 加载普通程序
             int (*load_binary)(struct linux_binprm *, struct  pt_regs * regs);
             // 加载共享库，即动态库
             int (*load_shlib)(struct file *);
             // 输出内存转储
             int (*core_dump)(long signr, struct pt_regs *regs, struct file *file, unsigned long limit);
             unsigned long min_coredump; /* minimal dump size */
             int hasvdso;
           };
         

   4. TODO 退出程序
      
5. 调度器
   
   1. 概览
      
      • 调度器主要完成两件事
        1. 调度策略
        2. 切换上下文

      • 就绪队列 调度器每次调度时，会挑选具有最高等待时间的进程，把CPU提供给该进程。调度器记录了每个进程已经 等待的时长并用红黑树从大到小排序，由于可运行进程是排队的，该结构称之为就绪队列：

      

      • 虚拟时钟 就绪队列中还有个虚拟时钟的概念，它表示的是就绪队列中的每个进程*平均*推进(分配到)的时间的度量
   2. 数据结构
      

      • 调度器系统概观 调度器使用一系列数据结构来完成器调度任务，他的各组件关系如下：

      可以看到，图中主要由两个调度器组成：

      1. 主调度器 主要用于进程打算睡眠或出于其他原因放弃CPU
      2. 周期性调度器 以固定的频率周期性运行，检测是否有必要进行进程切换

      • 调度器类 调度器通过查询调度器类来选择进程运行，调度器类用于判断接下来运行哪个进程，而且不同的类 具有不同的调度策略，每个进程都属于一个调度器类

      • task_{struct中有关成员}

        struct task_struct {
        ...
        /*
         * static_prio: 静态优先级进程启动时分配，进程运行期间保持恒定，除非用nice/sched_setscheduler
         * 系统调用修改
         * normal_prio: 普通优先级。基于进程的静态优先级和调度策略计算而来，所以即使实时进程和普通进程
         * 的静态优先级一样，他们的普通优先级页不同
         * prio: 动态优先级。调度器直接用的优先级，由于某些情况内核需要暂时提高进程的优先级，因此需要这
         * 第三个成员来表示
         */
          int prio, static_prio, normal_prio;
          /* 实时进程的优先级, 0-99, 值越大优先级越高 */
          unsigned int rt_priority; 
          struct list_head run_list;
          /* 所属调度器类 */
          const struct sched_class *sched_class;
          /* 调度实体 */
          struct sched_entity se; 
          /* 调度策略 */
          unsigned int policy;
          cpumask_t cpus_allowed;
          unsigned int time_slice;
        ...
        }
        

        1. 优先级

           • 用户空间 进程在用户空间表示为-20到+19（包含），值越低，优先级越高

           • 内核表示 内核使用0到139来表示内部优先级，nice值映射到范围100到139，0到99专用于实时进程, 也是值越低优先级越高:

             三个优先级中，静态优先级由用户设置好，其他两个则由内核计算得来,计算的时机是

             1. 新建进程用wake_{upnewtask唤醒时}
             2. 调用nice系统调用改变静态优先级时

             计算过程如下表：

           

        2. 调度策略 linux支持5种调度策略，
           • 映射到完全公平调度器类：SCHED_NORMAL􏲹SCHED_BATCH􏰓SCHED_IDLE
           • 映射到实时调度器类：SCHED_RR􏰓SCHED_FIFO

        3. 调度器类 调度的实际工作主要由具体的调度器类来执行，调度器类可以提供以下操作：

           struct sched_class {
             const struct sched_class *next;
             /* 向就绪队列添加一个进程，当进程从睡眠状态变为可执行状态时发生该操作 */
             void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
             /* enqueue_task的逆向操作， */
             void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
             /* 进程调用sched_yield主动放弃处理器时，内核会调用此函数 */
             void (*yield_task) (struct rq *rq);
             /* 用新唤醒的进程来抢占当前进程，如wake_up_new_task唤醒新进程时会调用 */
             void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
             /* 选择下一个要运行的进程，需要执行上下文切换 */
             struct task_struct * (*pick_next_task) (struct rq *rq);
             void (*put_prev_task) (struct rq *rq, struct task_struct *p);
             void (*set_curr_task) (struct rq *rq);
             void (*task_tick) (struct rq *rq, struct task_struct *p);
             /* 建立fork与调度器直接的关联 */
             void (*task_new) (struct rq *rq, struct task_struct *p);
           };
           

      • 就绪队列 内核为每个CPU维护一个就绪队列runqueues，这是调度器最重要的数据结构,每个进程都出现在某一个队列中。

        static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
        

        这个就绪队列并不直接管理进程，而是把特定于调度器类的子就绪队列嵌入它的结构体中：

        /*
         * This is the main, per-CPU runqueue data structure.
         *
         * Locking rule: those places that want to lock multiple runqueues
         * (such as the load balancing or the thread migration code), lock
         * acquire operations must be ordered by ascending &runqueue.
         */
        struct rq {
          /* runqueue lock: */
          spinlock_t lock;
        
          /*
           * nr_running and cpu_load should be in the same cacheline because
           * remote CPUs use both these fields when doing load calculation.
           * 队列上可运行的进程数目
           */
          unsigned long nr_running;
        #define CPU_LOAD_IDX_MAX 5
          /* 该队列的cpu之前的负荷状态 */
          unsigned long cpu_load[CPU_LOAD_IDX_MAX];
          struct load_weight load;
          struct cfs_rq cfs;
        #ifdef CONFIG_FAIR_GROUP_SCHED
          /* list of leaf cfs_rq on this cpu: */
          struct list_head leaf_cfs_rq_list;
        #endif
          struct rt_rq rt;
        
          /*
           * This is part of a global counter where only the total sum
           * over all CPUs matters. A task can increase this counter on
           * one CPU and if it got migrated afterwards it may decrease
           * it on another CPU. Always updated under the runqueue lock:
           */
          unsigned long nr_uninterruptible;
        
          struct task_struct *curr, *idle;
          /* 该就绪队列自身的时钟,每次调用周期性调度器都会更新clock */
          u64 clock, prev_clock_raw;
        ...
        }
        

      • 调度实体 之前一直说的是调度器调度的是进程，其实这是一种简化的说法，其实每个进程的task_struct中 都嵌入了一个sched_entity结构, 所以调度器调度的不是进程，而是这个被称为调度实体的更一般 化的概念,其定义如下：

        struct sched_entity {
          struct load_weight load; /* 用于负载均衡*/
          struct rb_node run_node;
          unsigned int on_rq;
          u64 exec_start;
          u64 sum_exec_runtime;
          u64 vruntime;
          u64 prev_sum_exec_runtime;
        ...
        }
        

      • 负荷权重 进程的重要性不是直接由优先级(nice)指定的，而是要由优先级和进程调度策略计算得来的 task_struct->se.load的负荷权重。具体计算概念是：进程没降低一个nice值，就多获得10%的CPU 时间，美升高一个nice值就放弃10%的CPU时间。具体对应关系为:

        

   3. 两个调度器的调度过程
      

      • 周期性调度器 周期性调度器在scheduler_{tick中实现}。如果系统正在活动中，内核会按照频率HZ自动调用该函数 它主要完成两个任务：

        1. 管理内核中与整个系统和各个进程的调度相关的统计量

        void scheduler_tick(void)
        {
          1. 管理内核中与整个系统和各个进程的调度相关的统计量
          int cpu = smp_processor_id();
          struct rq *rq = cpu_rq(cpu);
          struct task_struct *curr = rq->curr;
        
        ...
            /*更新当前cpu strut rq的时钟时间戳*/
          __update_rq_clock(rq)
          /* 更新cpu load[]数组 */
            update_cpu_load(rq);
        
        
         2. 激活负责当前进程的调度器类的周期性调度方法scheduler_tick
        /*
         * task_tick在当前进程需要被重新调度时，设置该进程的
         * TIF_NEED_RESCHED标志,内核会在返回用户态前检查该
         * 标志，如果该标志置位了，调用主调度器的schedule()函数
         */
         if (curr != rq->idle)
           curr->sched_class->task_tick(rq, curr);
        }
        

      • 主调度器 内核中有许多地方会调用主调度器函数schedule()：

        1. 从系统调用返回用户态前链接
        2. 进程主动放弃cpu使用权

        他的主要流程为：

        asmlinkage void __sched schedule(void)
        {
          struct task_struct *prev, *next;
          struct rq *rq;
          int cpu;
         need_resched:
          cpu = smp_processor_id();
          rq = cpu_rq(cpu);
          prev = rq->curr;
        ...
         __update_rq_clock(rq);
         clear_tsk_need_resched(prev);
        ...
         TODO  /* TASK_INTERRUPTIBLE 的进程为什么能是cur进程 */
         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
           if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
             unlikely(signal_pending(prev)))) {
             prev->state = TASK_RUNNING;
           } else {
             deactivate_task(rq, prev, 1);
           }
           switch_count = &prev->nvcsw;
         }
        
        ...
          prev->sched_class->put_prev_task(rq, prev);
          next = pick_next_task(rq, prev);
        ...
            if (likely(prev != next)) {
              rq->nr_switches++;
              rq->curr = next;
              ++*switch_count;
        
              context_switch(rq, prev, next); /* unlocks the rq */
            }
        }
        

        当需要切换进程时，调用context_switch():

        /*
         * context_switch - switch to the new MM and the new
         * thread's register state.
         */
        static inline void
        context_switch(struct rq *rq, struct task_struct *prev,
                 struct task_struct *next)
        {
          struct mm_struct *mm, *oldmm;
        
          prepare_task_switch(rq, prev, next);
          mm = next->mm;
          oldmm = prev->active_mm;
          /*
           * For paravirt, this is coupled with an exit in switch_to to
           * combine the page table reload and the switch backend into
           * one hypercall.
           */
          arch_enter_lazy_cpu_mode();
        
          if (unlikely(!mm)) {
            /* 内核线程没有用户空间内存上下文，会借用prev的地址空间， */
            next->active_mm = oldmm;
            atomic_inc(&oldmm->mm_count);
            /* 惰性 TLB */
            enter_lazy_tlb(oldmm, next);
          } else
            1./* 更换内存管理上下文 */
            switch_mm(oldmm, mm, next);
        
          if (unlikely(!prev->mm)) {
            prev->active_mm = NULL;
            rq->prev_mm = oldmm;
          }
          /*
           * Since the runqueue lock will be released by the next
           * task (which is an invalid locking op but in the case
           * of the scheduler it's an obvious special-case), so we
           * do an early lockdep release here:
           */
        #ifndef __ARCH_WANT_UNLOCKED_CTXSW
          spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
        #endif
        
          2./* 切换处理器寄存器内容和内核栈 */
          /* Here we just switch the register state and the stack. */
          switch_to(prev, next, prev);
        
          barrier();
          3./*
           * this_rq must be evaluated again because prev may have moved
           * CPUs since it called schedule(), thus the 'rq' on its stack
           * frame will be invalid.
           */
          finish_task_switch(this_rq(), prev);
        }
        

        其中，switch_{to比较复杂}，如下图：

        如图中右上角所示，在每个switch_{to调用之前}，next和prev指针位于 当前进程的内核栈 上， prev指向当前运行的进程，而next指向将要运行的下一个进程，如图中第一个A所示，但是，经过 几次切换然后控制权再返回至switch_to之后，也就是第二个A的状态，如果不做特殊处理， 那么prev和next应该和第一个图一样，next=B，prev=A，而实际上上一个运行的进程是图中的 C。所以，switch_{to做了特殊处理}，使得prev=C，而不是A，如图右上角所示。

   4. 完全公平调度CFS
      

      • 数据结构

        struct cfs_rq {
          /* 当前队列所有进程的负荷值 */
          struct load_weight load;
          /* 可运行进程数 */
          unsigned long nr_running;
        
          /* 队列上所有进程的最小虚拟运行时间 */
          u64 min_vruntime;
        
          /* 按时间排序进程的红黑树 */
          struct rb_root tasks_timeline;
          struct rb_node *rb_leftmost;
        
          /* 当前执行进程的可调度实体 */
          struct sched_entity *curr
        }
        

      • 调度算法

        1. 虚拟时钟(时间) CFS并没有直接保存虚拟时钟，而是每次调度器运行时都计算一次，相关函数为update_curr

           static void update_curr(struct cfs_rq *cfs_rq)
           {
             /* 当前运行进程*/
             struct sched_entity *curr = cfs_rq->curr;
             /* 当前cpu等待队列中获取当前实际时钟,每次调度都会更新 */
             u64 now = rq_of(cfs_rq)->clock;
             unsigned long delta_exec;
           
             /* 无事可做，退出 */
             if (unlikely(!curr))
               return;
           
             /*
              * Get the amount of time the current task was running
              * since the last time we changed load (this cannot
              * overflow on 32 bits):
              */
             /* exec_start为进程这轮调度运行的开始时间 */
             delta_exec = (unsigned long)(now - curr->exec_start);
           
             /* 更新当前进程在CPU上执行花费的物理时间和虚拟时间 */
             __update_curr(cfs_rq, curr, delta_exec);
             /* 更新进程运行开始时间 */
             curr->exec_start = now;
           
             if (entity_is_task(curr)) {
               struct task_struct *curtask = task_of(curr);
           
               cpuacct_charge(curtask, delta_exec);
             }
           }
           
           /*
            * Update the current task's runtime statistics. Skip current tasks that
            * are not in our scheduling class.
            */
           static inline void
           __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
                   unsigned long delta_exec)
           {
             unsigned long delta_exec_weighted;
             u64 vruntime;
           
             schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
           
             /* 进程物理时钟 */
             curr->sum_exec_runtime += delta_exec;
             schedstat_add(cfs_rq, exec_clock, delta_exec);
             delta_exec_weighted = delta_exec;
             /* 公式： delta_exec_weighted = delta_exec * NICE_0_LOAD / curr->load.weight*/
             if (unlikely(curr->load.weight != NICE_0_LOAD)) {
               delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
                         &curr->load);
             }
             /* 虚拟时钟*/
             curr->vruntime += delta_exec_weighted;
           
             /*
              * maintain cfs_rq->min_vruntime to be a monotonic increasing
              * value tracking the leftmost vruntime in the tree.
              */
             /* 如果等待树上最左边有进程在等待，取当前进程与这个最左等待进程的虚拟时间的最小值 */
             if (first_fair(cfs_rq)) {
               vruntime = min_vruntime(curr->vruntime,
                   __pick_next_entity(cfs_rq)->vruntime);
             } else
               /* 树上没有进程等待的话，最小值就直接等于当前进程的虚拟时间 */
               vruntime = curr->vruntime;
           
             /* 每个队列的min_vruntime只有被所有进程超出时才更新,确保min_vruntime单调增加 */
             cfs_rq->min_vruntime =
               max_vruntime(cfs_rq->min_vruntime, vruntime);
           }
           

           代码流程图为：

           

           • 关键思想 虚拟时间在完全公平调度器中的关键点是，红黑树的排序过程按照下面的键来排序：

             static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
             {
               return se->vruntime - cfs_rq->min_vruntime;
             }
             

             键值越小，排序位置就越靠左，因此会被更快地调度，所以进程在树上的移动规则为：

             1. 进程运行时，它的vruntime一定会增加，所以在树中会向右移动 而且优先级值越小（重要性越高）的进程vruntime增加越慢，因此向右移动的速度也越慢 被调度的机会就要大于次要进程，也就是能分配更多的时间
             2. 如果进程进入睡眠，那么它就会从就绪队列中脱离出来，其vruntime保持不变。因为每个队列的 min_{vruntime会单调增加为等待队列中进程虚拟时间的最小值}，当进程再次醒来进入等待队列 的时候，导致进程虚拟时间vruntime小于等待队列min_vruntime，那么它在红黑树中的位置 会更靠左，因为其键值变得更小了。由此也可以看出，进程的vruntime是有可能小于队列的 min_vruntime的.

        2. 延迟跟踪 几个重要的时间控制参数变量：

           • 进程每次调度的保证最小运行时间 sysctl_{schedmingranularity} /proc/sys/kernel/sched_{mingranularityns间接控制,默认为4毫秒}.
           • 延迟数 sched_nrlatency 控制一个周期中处理的最大活动进程数目，如果超出这个限制，那么延迟周期也成比例的线性扩展, 可以通过sysctl_{schedmingranularity间接控制}，

           • sysctl_schedlatency ： 保证每个可运行进程都至少运行一次的时间间隔，可以通过/proc/sys/kernel/sched_latencyns 控制默认为20毫秒。每次前两个之一改变，都会从新计算:

             __{schedperoid确定延迟周期的长度}，通常来说就是sys_{schedlatency,但如果延迟数超了的话}， 改值就会线性扩展：sysctl_schedlatency * nr_running / sched_nrlatency。 一个延迟周期 会根据进程的 相对 权重在进程间分配: 物理时间：

             虚拟时间：

           

           可以看到，每个进程在一个延迟周期中分配到的虚拟时间是一样的.

        3. 加入队列

           static void
           place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
           {
             u64 vruntime;
           
             vruntime = cfs_rq->min_vruntime;
           
             if (sched_feat(TREE_AVG)) {
               struct sched_entity *last = __pick_last_entity(cfs_rq);
               if (last) {
                 vruntime += last->vruntime;
                 vruntime >>= 1;
               }
             } else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
               vruntime += sched_vslice(cfs_rq)/2;
           
             /*
              * The 'current' period is already promised to the current tasks,
              * however the extra weight of the new task will slow them down a
              * little, place the new task so that it fits in the slot that
              * stays open at the end.
              */
             /* initial表示se是新进程,如果se是新进程，se_vruntime加一个时间段，表示
             从下一个时间周期才开始调度这个新进程*/
             if (initial && sched_feat(START_DEBIT))
               vruntime += sched_vslice_add(cfs_rq, se);
           
             if (!initial) {
               /*如果se不是新进程，那么为了补偿它的睡眠，给他的vruntime-20ms，使得它能更快(马上？)被调度*/
               /* sleeps upto a single latency don't count. */
               if (sched_feat(NEW_FAIR_SLEEPERS) && entity_is_task(se))
                 vruntime -= sysctl_sched_latency;
           
               /* ensure we never gain time by being placed backwards. */
               vruntime = max_vruntime(se->vruntime, vruntime);
             }
           
             se->vruntime = vruntime;
           }
           

        4. 选择下一个进程

           static struct task_struct *pick_next_task_fair(struct rq *rq)
           {
             struct cfs_rq *cfs_rq = &rq->cfs;
             struct sched_entity *se;
           
             if (unlikely(!cfs_rq->nr_running))
               return NULL;
           
             do {
               se = pick_next_entity(cfs_rq);
               cfs_rq = group_cfs_rq(se);
             } while (cfs_rq);
           
             return task_of(se);
           }
           
           static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
           {
             struct sched_entity *se = NULL;
           
             if (first_fair(cfs_rq)) {
               se = __pick_next_entity(cfs_rq);
               /* 将当前执行进程退队,并检查是不是超过该时间周期可以运行的时间 */
               set_next_entity(cfs_rq, se);
             }
           
             return se;
           }
           

        5. 处理周期调度调度器
        6. 唤醒抢占
        7. 实时调度器类
        8. TODO 主调度器和周期调度器的整个流程

3.9.2 内存管理

1. 概述
   

   内存管理是内核中最复杂同时也是最重要的一部分，涵盖了许多领域：

   1. 内存中物理内存的管理
   2. 分配大块内存的伙伴系统
   3. 分配较小块内存的slab、slub和slob分配器
   4. 分配非连续内存块的vmalloc机制
   5. 进程的地址空间

   按管理内存方法的不同，可以将计算机分为两类：

   1. UMA计算机（一致内存访问 uniform memory access),内存以连续的方式组织起来， 特点是每个处理器访问每个内存区 都是同样快
   2. NUMA计算机。每个CPU都有本地内存，可支持快速的访问。每个CPU也可以访问其他CPU的本地内存， 但是速度会慢一些

   

   两种计算机都可以有不同的内存布局：

   简单描述就是：UMA内存模型除了可以是一个NUMA的内存模型（一般内存有比较大的洞时配置）以外，还可以 配置为平坦内存模型

   我们主要集中于理解UMA的平坦内存模型，因为一般的计算机都是这种模型

   • 分配阶 内存区中页的数分配目的度量，阶0为2⁰ = 1, 阶1的分配包括2¹ = 2…
2. 内存组织
   
   1. 概述
      
      • NUMA linux把内存分为有层次的几个概念。
        1. 首先，内存被分为多个节点，每个节点关联到一个处理器，在,内核中表示为pg_datat
        2. 节点又被分为多个内存域
        3. 内存域关联了一个struct page数组，用来组织该内存域中的物理内存页(页帧)

      

      • UMA UMA可以看作是只有一个节点的NUMA(不是平坦内存模型时应该看作多个节点)
   2. 数据结构
      

      1. 节点

         typedef struct pglist_data {
           /* 节点中各个内存域的数据结构 */
           struct zone node_zones[MAX_NR_ZONES];
           /* 备用节点及其内存域的列表 */
           struct zonelist node_zonelists[MAX_ZONELISTS];
           /* 节点内存域数目 */
           int nr_zones;
         #ifdef CONFIG_FLAT_NODE_MEM_MAP
           /* page实例数组的指针，用于描述所有物理内存页 */
           struct page *node_mem_map;
         #endif
           /* 自举分配器的实例 */
           struct bootmem_data *bdata;
         #ifdef CONFIG_MEMORY_HOTPLUG
           /*
            * Must be held any time you expect node_start_pfn, node_present_pages
            * or node_spanned_pages stay constant.  Holding this will also
            * guarantee that any pfn_valid() stays that way.
            *
            * Nests above zone->lock and zone->size_seqlock.
            */
           spinlock_t node_size_lock;
         #endif
           /* 第一个页帧的逻辑编号，全局唯一 */
           unsigned long node_start_pfn;
           unsigned long node_present_pages; /* total number of physical pages */
           unsigned long node_spanned_pages; /* total size of physical page
                                                range, including holes */
           /* 节点全局ID */
           int node_id;
           /* 交换守护进程的等待队列 */
           wait_queue_head_t kswapd_wait;
           /* 负责该节点的交互守护进程 */
           struct task_struct *kswapd;
           int kswapd_max_order;
         } pg_data_t;
         

      2. 内存域

         struct zone {
           /* Fields commonly accessed by the page allocator */
           unsigned long   pages_min, pages_low, pages_high; /* 水印,用于页换出 */
           /*
            * We don't know if the memory that we're going to allocate will be freeable
            * or/and it will be released eventually, so to avoid totally wasting several
            * GB of ram we must reserve some of the lower zone memory (otherwise we risk
            * to run OOM on the lower zones despite there's tons of freeable ram
            * on the higher zones). This array is recalculated at runtime if the
            * sysctl_lowmem_reserve_ratio sysctl changes.
            */
           unsigned long   lowmem_reserve[MAX_NR_ZONES]; /* 用于无论如何都不能失败的关键内存分配 */
         
         #ifdef CONFIG_NUMA
           int node;
           /*
            * zone reclaim becomes active if more unmapped pages exist.
            */
           unsigned long   min_unmapped_pages;
           unsigned long   min_slab_pages;
           struct per_cpu_pageset  *pageset[NR_CPUS];
         #else
           struct per_cpu_pageset  pageset[NR_CPUS]; /* 每个CPU的冷热页帧列表 */
         #endif
           /*
            * free areas of different sizes
            */
           spinlock_t    lock;
         #ifdef CONFIG_MEMORY_HOTPLUG
           /* see spanned/present_pages for more description */
           seqlock_t   span_seqlock;
         #endif
           struct free_area  free_area[MAX_ORDER]; /* 用于实现伙伴系统 */
         
         #ifndef CONFIG_SPARSEMEM
           /*
            * Flags for a pageblock_nr_pages block. See pageblock-flags.h.
            * In SPARSEMEM, this map is stored in struct mem_section
            */
           unsigned long   *pageblock_flags;
         #endif /* CONFIG_SPARSEMEM */
         
         
           ZONE_PADDING(_pad1_)
         
           /* Fields commonly accessed by the page reclaim scanner */
           spinlock_t    lru_lock; 
           struct list_head  active_list;  /* 活动页 */
           struct list_head  inactive_list; /* 不活动页 */
           unsigned long   nr_scan_active;
           unsigned long   nr_scan_inactive;
           unsigned long   pages_scanned;     /* since last reclaim */
           unsigned long   flags;       /* zone flags, see below */
         
           /* Zone statistics */
           atomic_long_t   vm_stat[NR_VM_ZONE_STAT_ITEMS]; /* 统计信息 */
         
           /*
            * prev_priority holds the scanning priority for this zone.  It is
            * defined as the scanning priority at which we achieved our reclaim
            * target at the previous try_to_free_pages() or balance_pgdat()
            * invokation.
            *
            * We use prev_priority as a measure of how much stress page reclaim is
            * under - it drives the swappiness decision: whether to unmap mapped
            * pages.
            *
            * Access to both this field is quite racy even on uniprocessor.  But
            * it is expected to average out OK.
            */
           int prev_priority; /* 扫描优先级 */
         
         
           ZONE_PADDING(_pad2_)
           /* Rarely used or read-mostly fields */
         
           /*
            * wait_table   -- the array holding the hash table
            * wait_table_hash_nr_entries -- the size of the hash table array
            * wait_table_bits  -- wait_table_size == (1 << wait_table_bits)
            *
            * The purpose of all these is to keep track of the people
            * waiting for a page to become available and make them
            * runnable again when possible. The trouble is that this
            * consumes a lot of space, especially when so few things
            * wait on pages at a given time. So instead of using
            * per-page waitqueues, we use a waitqueue hash table.
            *
            * The bucket discipline is to sleep on the same queue when
            * colliding and wake all in that wait queue when removing.
            * When something wakes, it must check to be sure its page is
            * truly available, a la thundering herd. The cost of a
            * collision is great, but given the expected load of the
            * table, they should be so rare as to be outweighed by the
            * benefits from the saved space.
            *
            * __wait_on_page_locked() and unlock_page() in mm/filemap.c, are the
            * primary users of these fields, and in mm/page_alloc.c
            * free_area_init_core() performs the initialization of them.
            */
           /* 实现一个等待队列，供等待某一页变为可用的进程使用 */
           wait_queue_head_t * wait_table;
           unsigned long   wait_table_hash_nr_entries;
           unsigned long   wait_table_bits;
         
           /*
            * Discontig memory support fields.
            */
           struct pglist_data  *zone_pgdat; /* 内存域所在节点 */
           /* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
           unsigned long   zone_start_pfn;  /* 内存域中第一个页帧的索引 */
         
           /*
            * zone_start_pfn, spanned_pages and present_pages are all
            * protected by span_seqlock.  It is a seqlock because it has
            * to be read outside of zone->lock, and it is done in the main
            * allocator path.  But, it is written quite infrequently.
            *
            * The lock is declared along with zone->lock because it is
            * frequently read in proximity to zone->lock.  It's good to
            * give them a chance of being in the same cacheline.
            */
           unsigned long   spanned_pages;  /* total size, including holes */
           unsigned long   present_pages;  /* amount of memory (excluding holes) */
         
           /*
            * rarely used fields:
            */
           const char    *name;
         } ____cacheline_internodealigned_in_smp;
         

         该结构被访问的非常频繁，而且可能同时被多个处理器访问，所以结构体中有两个自旋锁。 为了确保每个自旋锁都在自己的缓存行中，该结构由ZONE_{PADDING分隔为几个部分},

      3. TODO 水印的计算

      4. 冷热页 内核说的页是热的，意味着页已经加载到CPU高速缓存。其数据结构如下：

         struct zone {
         ...
         struct per_cpu_pageset pageset[NR_CPUS];
         ...
         };
         
         
         struct per_cpu_pageset {
           struct per_cpu_pages pcp[2]; /* 0对于热页，1对应冷页 */
         } ____cacheline_aligned_in_smp;
         
         
         
         struct per_cpu_pages {
           int count;    /* number of pages in the list */
           int high;   /* high watermark, emptying needed */
           int batch;    /* chunk size for buddy add/remove */
           struct list_head list;  /* the list of pages */
         }
         

         

      5. 页帧 页帧代表系统内存的最小单位，对于内存中的每个页都会创建struct page的一个实例。所以 该结构应该尽可能小以节约内存

         struct page {
           unsigned long flags;    /* Atomic flags, some possibly
                    * updated asynchronously */
           atomic_t _count;    /* Usage count, see below. */
           union {
             atomic_t _mapcount; /* Count of ptes mapped in mms,
                    * to show when page is mapped
                    * & limit reverse map searches.
                    */
             unsigned int inuse; /* SLUB: Nr of objects */
           };
           union {
               struct {
             unsigned long private;    /* Mapping-private opaque data:
                      * usually used for buffer_heads
                      * if PagePrivate set; used for
                      * swp_entry_t if PageSwapCache;
                      * indicates order in the buddy
                      * system if PG_buddy is set.
                      */
             struct address_space *mapping;  /* If low bit clear, points to
                      * inode address_space, or NULL.
                      * If page mapped as anonymous
                      * memory, low bit is set, and
                      * it points to anon_vma object:
                      * see PAGE_MAPPING_ANON below.
                      */
               };
         #if NR_CPUS >= CONFIG_SPLIT_PTLOCK_CPUS
               spinlock_t ptl;
         #endif
               struct kmem_cache *slab;  /* SLUB: Pointer to slab */
               struct page *first_page;  /* Compound tail pages */
           };
           union {
             pgoff_t index;    /* Our offset within mapping. */
             void *freelist;   /* SLUB: freelist req. slab lock */
           };
           struct list_head lru;   /* Pageout list, eg. active_list
                    * protected by zone->lru_lock !
                    */
           /*
            * On machines where all RAM is mapped into kernel address space,
            * we can simply calculate the virtual address. On machines with
            * highmem some memory is mapped into kernel virtual memory
            * dynamically, so we need a place to store that address.
            * Note that this field could be 16 bits on x86 ... ;)
            *
            * Architectures with slow multiplication can define
            * WANT_PAGE_VIRTUAL in asm/page.h
            */
         #if defined(WANT_PAGE_VIRTUAL)
           void *virtual;      /* Kernel virtual address (NULL if
                      not kmapped, ie. highmem) */
         #endif /* WANT_PAGE_VIRTUAL */
         };
         

3. TODO 页表
   
4. 初始化内存管理
   

   linux内存的初始化过程，首先会执行一些特定于处理器的操作，这些操作主要用于确定系统中内存的总数量， 及其在各个节点和内存域之间的分配情况。之后是关键的pg_{datat数据结构的初始化}

   1. 建立数据结构
      

      对于数据结构的初始化从全局启动例程start_{kernel开始的}，它在加载内核并激活各个子系统之后执行。 其代码流程如下：

      

      • setup_arch：负责初始化自举分配器
      • set_percpuareas: 初始化静态per-cpu变量

      • build_allzonelists: 建立节点和内存域的数据结构 主要是建立节点的备用列表，用于在节点本身没有空闲空间时按先后顺序在备用列表中分配:

        其中，

      

      • mem_init：停用bootmem分配器并迁移到实际的内存管理函数
      • kmem_cacheinit:初始化内核内部用于小块内存区的分配器
      • set_{percpupageset}:
      1. 
         

         1. 内核的内存布局 我们只考虑默认情况，即内核被装载到物理内存中的一个固定位置。当然这也是可以配置的。 内核占据的内存大概分为几个段：

            下面是linux在I-32下的布局：

            这里内核从第一兆字节开始, AMD64下则会从第二兆字节开始

         2. 在内核已经载入内存在内存管理方面后会执行一些特定于系统的步骤：

            

            • machine_{specificmemorysetup}: 创建一个包括系统占用内存区和空闲内存区的的列表，会用到BIOS提供的信息
            • parse_earlyparam: 分析命令行，用于手工划分内存区（因为BIOS提供的值可能不正确）
            • setup_memory:
              1. 确定每个结点可用的物理内存数目
              2. 初始化bootmem分配器
              3. 分配各种内存区

            • paging_init: 初始化内核页表并启动内存分页。

              值的注意的是，低端内存中的所有页帧都直接映射到PAGE_{OFFSET之上的虚拟内存区}。 这使得内核无需通过页表就可以直接寻址相当一部分内存

            • zone_sizesinit： 初始化系统中所有结点的pgdat_t实例

              AMD64下有所改变，但做的事都差不多，主要的区别就是AMD64的init_{memorymapping函数} 可以把所有物理内存直接映射到内核虚拟内存区,而不仅限于低端内存:

            

         3. 分页机制初始化(64位) paging_{init负责建立只能用于内核的也表,用户空间无法访问} 我们主要关注AMD64的虚拟内存和分页：

            • 虚拟地址到物理地址空间的映射方式：

              因为现在AMD64处理器物理地址限制在48位，所以linux的虚拟地址映射分了非规范区，这个区域 是不会访问到的,只有上半部(内核空间)和下半部(用户空间)能访问。 如下图：

            

         4. bootmem分配器 bootmem分配器用于在启动阶段早期分配内存,因为只在初始化时使用，不难想到，它的需求集中 在简单性方面，而不是性能和通用性，所以该分配器使用一个位图来管理页，一个位表示一个物理页。 分配算法采用最先适配算法(first-best)。

            • 数据结构：

            typedef struct bootmem_data {
              /* 系统中第一页的编号 */
              unsigned long node_boot_start;
              /* ZONE_NORMAL的结束页 */
              unsigned long node_low_pfn;
              /* 位图指针 */
              void *node_bootmem_map;
              unsigned long last_offset;
              unsigned long last_pos;
              unsigned long last_success; /* Previous allocation point.  To speed
                                           * up searching */
              struct list_head list;
            } bootmem_data_t;
            

            所有的分配器(UMA系统只有一个)都保存在一个全局bdata_list中

            • 初始化(AMD64)
              1. bootmem_{bootmapbitmap利用BIOS在e820映射的信息计算bootmem位图所需页的数目}。
              2. init_{bootmem将该信息填充到bootmem数据结构中}。
            • API(TODO)
         5. 释放初始化数据 许多内核代码快和数据表只在系统初始化阶段需要，所以内核提供了两个属性(_{init和initcall}) 用于标记初始化函数和数据。它们被编译器安排在一个特别的段中(.init.data, .init.text)， 在启动过程刚好结束时会调用free_{initmem函数来释放这些区域}，并将其返回伙伴系统。紧接其后 init作为系统中第一个进程启动.
5. 物理内存的管理(伙伴系统)
   

   内核初始完成后，内存管理交给伙伴系统。它结合了分配器的两个关键特征:速度和效率

   1. 数据结构
      

      管理伙伴系统的数据存在于内存域结构体中:

      struct zone{
        ...
        /* 不同阶的内存区域, MAX_ORDER一般为11 */
        struct free_area free_area[MAX_ORDER];
        ...
      };
      
      struct free_area {
        struct list_head free_list[MIGRATE_TYPES];
        /* 空闲内存块的数目 */
        unsigned long nr_free;
      };
      

      可以图示如下：

      可以看到，伙伴系统相当简介，所以管理工作也非常少，这也是它的一个主要优点.

      就像前面说的，内存域有备用列表，所以伙伴系统也通过备用列表连接起来了：

      

   2. 避免碎片
      

      在系统长期运行后，物理内存会产生很多的碎片:

      如上图，左边是有碎片的情况，内核才会涉及内存碎片(用户态在分配巨型页的情况下也会涉及), 内核会有内存碎片问题的原因：

      1. 有些底层指令（如lcr3）需要用到物理地址，所以直接映射不需要经过页表就能直接算出物理地址，
      2. 确实需要连续的物理内存

      所以内核加入了两种机制来尽量防止碎片：

      1. 将内存域内部的空闲内存按能不能移动分类 具体来说，内核将已分配的页分为下面3种不同类型：

         • 不可移动页
         • 可回收页 不能移动，但可以删除来重新装其他内容。映射自文件的数据属于这种类型。 kswapd守护进程会周期性释放此类内存
         • 可移动页 可以随意移动的页。 属于用户空间的应用程序的页属于该类别

         正如我们看到的，在伙伴系统中:

         struct free_area {
             struct list_head free_list[MIGRATE_TYPES];
             /* 空闲内存块的数目 */
             unsigned long nr_free;
           };
         

         空闲列表分为了MIGRSTE_{TYPES的列表}，MIGRATE_{TYPES也就是上面说的页的分类类型数} 与内存域之间的备用列表一样，这些不同类型内存间也有备用列表：

         当然，如果各迁移类型链表中如果没有一块较大的连续内存的话，这种分类没有任何好处，因此在可用 内存太少时内核会关闭该特性。

         分类后的一个问题是：既然分类了，那分配内存时必须指定要分配哪种类型的内存。这是通过分配掩码 来指定的。如果停用了分类特性，那所有页都是不可移动的。

         值得注意的是，内核并未在一开始划分内存为可移动性不同的区。

      2. TODO : 虚拟内存域 ZONE_MOVABLE 好像与第一种有点冲突？可以同时激活吗？
   3. 初始化内存域和结点数据结构
      

      我们已经知道，体系结构特定 的初始化步骤前四步已经在启动过程中建立以下信息：

      • 各个内存域的页帧边界,max_zonepfn
      • 各个结点页帧的分配情况,early_nodemap

      现在需要做最后一步来完成内存域和结点数据结构的初始化: 该步骤由free_{areainitnodes完成}：

      

      • calculate_{nodetotalpages}：计算结点中页的总数
      • alloc_{nodememmap负责初始化每个物理页对应的struct} page实例
      • free_areainitcore:初始化zone结构各个表头，并将所有成员初始化为0,所以这里也会把zone中 的nr_{free设置为0}。直到停用bootmem分配器，伙伴系统生效，才会设置正确的值
   4. 分配器API
      
      1. API
         

         分配最终都归于alloc_{pagesnode函数}：

         

         释放最终都归于__{freepages函数}：

         

      2. 分配掩码
         

         上面的所以函数都强制使用了分配掩码mask参数:

         他们的定义为：

         /*
          * GFP bitmasks..
          *
          * Zone modifiers (see linux/mmzone.h - low three bits)
          *
          * Do not put any conditional on these. If necessary modify the definitions
          * without the underscores and use the consistently. The definitions here may
          * be used in bit comparisons.
          */
         #define __GFP_DMA ((__force gfp_t)0x01u)
         #define __GFP_HIGHMEM ((__force gfp_t)0x02u)
         #define __GFP_DMA32 ((__force gfp_t)0x04u)
         
         /*
          * Action modifiers - doesn't change the zoning
          *
          * __GFP_REPEAT: Try hard to allocate the memory, but the allocation attempt
          * _might_ fail.  This depends upon the particular VM implementation.
          *
          * __GFP_NOFAIL: The VM implementation _must_ retry infinitely: the caller
          * cannot handle allocation failures.
          *
          * __GFP_NORETRY: The VM implementation must not retry indefinitely.
          *
          * __GFP_MOVABLE: Flag that this page will be movable by the page migration
          * mechanism or reclaimed
          */
         #define __GFP_WAIT  ((__force gfp_t)0x10u)  /* Can wait and reschedule? */
         #define __GFP_HIGH  ((__force gfp_t)0x20u)  /* Should access emergency pools? */
         #define __GFP_IO  ((__force gfp_t)0x40u)  /* Can start physical IO? */
         #define __GFP_FS  ((__force gfp_t)0x80u)  /* Can call down to low-level FS? */
         #define __GFP_COLD  ((__force gfp_t)0x100u) /* Cache-cold page required */
         #define __GFP_NOWARN  ((__force gfp_t)0x200u) /* Suppress page allocation failure warning */
         #define __GFP_REPEAT  ((__force gfp_t)0x400u) /* Retry the allocation.  Might fail */
         #define __GFP_NOFAIL  ((__force gfp_t)0x800u) /* Retry for ever.  Cannot fail */
         #define __GFP_NORETRY ((__force gfp_t)0x1000u)/* Do not retry.  Might fail */
         #define __GFP_COMP  ((__force gfp_t)0x4000u)/* Add compound page metadata */
         #define __GFP_ZERO  ((__force gfp_t)0x8000u)/* Return zeroed page on success */
         #define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u) /* Don't use emergency reserves */
         #define __GFP_HARDWALL   ((__force gfp_t)0x20000u) /* Enforce hardwall cpuset memory allocs */
         #define __GFP_THISNODE  ((__force gfp_t)0x40000u)/* No fallback, no policies */
         #define __GFP_RECLAIMABLE ((__force gfp_t)0x80000u) /* Page is reclaimable */
         /* 不会影响内核的决策，除非它与__GFP_HIGHMEM同时指定。这中情况下，会使用特殊的虚拟
         *  内存域ZONE_MOVABLE满足内存分配要求 */
         #define __GFP_MOVABLE ((__force gfp_t)0x100000u)  /* Page is movable */
         
         #define __GFP_BITS_SHIFT 21 /* Room for 21 __GFP_FOO bits */
         #define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))
         
         /* This equals 0, but use constants in case they ever change */
         #define GFP_NOWAIT  (GFP_ATOMIC & ~__GFP_HIGH)
         /* GFP_ATOMIC means both !wait (__GFP_WAIT not set) and use emergency pool */
         #define GFP_ATOMIC  (__GFP_HIGH)
         #define GFP_NOIO  (__GFP_WAIT)
         #define GFP_NOFS  (__GFP_WAIT | __GFP_IO)
         #define GFP_KERNEL  (__GFP_WAIT | __GFP_IO | __GFP_FS)
         #define GFP_TEMPORARY (__GFP_WAIT | __GFP_IO | __GFP_FS | \
                __GFP_RECLAIMABLE)
         #define GFP_USER  (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
         #define GFP_HIGHUSER  (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | \
                __GFP_HIGHMEM)
         #define GFP_HIGHUSER_MOVABLE  (__GFP_WAIT | __GFP_IO | __GFP_FS | \
                  __GFP_HARDWALL | __GFP_HIGHMEM | \
                  __GFP_MOVABLE)
         #define GFP_NOFS_PAGECACHE  (__GFP_WAIT | __GFP_IO | __GFP_MOVABLE)
         #define GFP_USER_PAGECACHE  (__GFP_WAIT | __GFP_IO | __GFP_FS | \
                  __GFP_HARDWALL | __GFP_MOVABLE)
         #define GFP_HIGHUSER_PAGECACHE  (__GFP_WAIT | __GFP_IO | __GFP_FS | \
                  __GFP_HARDWALL | __GFP_HIGHMEM | \
                  __GFP_MOVABLE)
         
         #ifdef CONFIG_NUMA
         #define GFP_THISNODE  (__GFP_THISNODE | __GFP_NOWARN | __GFP_NORETRY)
         #else
         #define GFP_THISNODE  ((__force gfp_t)0)
         #endif
         
         /* This mask makes up all the page movable related flags */
         #define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)
         
         /* Control page allocator reclaim behavior */
         #define GFP_RECLAIM_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS|\
               __GFP_NOWARN|__GFP_REPEAT|__GFP_NOFAIL|\
               __GFP_NORETRY|__GFP_NOMEMALLOC)
         
         /* Control allocation constraints */
         #define GFP_CONSTRAINT_MASK (__GFP_HARDWALL|__GFP_THISNODE)
         
         /* Do not use these with a slab allocator */
         #define GFP_SLAB_BUG_MASK (__GFP_DMA32|__GFP_HIGHMEM|~__GFP_BITS_MASK)
         
         /* Flag - indicates that the buffer will be suitable for DMA.  Ignored on some
            platforms, used as appropriate on others */
         
         #define GFP_DMA   __GFP_DMA
         
         /* 4GB DMA on some platforms */
         #define GFP_DMA32 __GFP_DMA32
         

      3. 伙伴系统入口 alloc_pagesnode和__allocpages
         

         所有的API函数都追溯到alloc_pagesnode，它相当于伙伴系统的总入口.

         static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
                                                     unsigned int order)
         {
           /* 避免分配过大的内存块 */
           if (unlikely(order >= MAX_ORDER))
             return NULL;
         
           /* Unknown node is current node */
           if (nid < 0)
             nid = numa_node_id();
         
           return __alloc_pages(gfp_mask, order,
                                NODE_DATA(nid)->node_zonelists + gfp_zone(gfp_mask));
         }
         
         
         /* 选择内存域 */
         static inline enum zone_type gfp_zone(gfp_t flags)
         {
           int base = 0;
         
         #ifdef CONFIG_NUMA
           if (flags & __GFP_THISNODE)
             base = MAX_NR_ZONES;
         #endif
         
         #ifdef CONFIG_ZONE_DMA
           if (flags & __GFP_DMA)
             return base + ZONE_DMA;
         #endif
         #ifdef CONFIG_ZONE_DMA32
           if (flags & __GFP_DMA32)
             return base + ZONE_DMA32;
         #endif
           if ((flags & (__GFP_HIGHMEM | __GFP_MOVABLE)) ==
               (__GFP_HIGHMEM | __GFP_MOVABLE))
             return base + ZONE_MOVABLE;
         #ifdef CONFIG_HIGHMEM
           if (flags & __GFP_HIGHMEM)
             return base + ZONE_HIGHMEM;
         #endif
           return base + ZONE_NORMAL;
         }
         
         
         
         

         可以看到，该函数在执行避免分配分配过大内存块的检查后，马上把委托给__{allocpages函数}。 从它前面的两个 __ 就不难猜到，这个函数才是完成整个分配任务最核心的后台函数：

         #define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */
         #define ALLOC_WMARK_MIN   0x02 /* use pages_min watermark */
         #define ALLOC_WMARK_LOW   0x04 /* use pages_low watermark */
         #define ALLOC_WMARK_HIGH  0x08 /* use pages_high watermark */
         #define ALLOC_HARDER    0x10 /* try to alloc harder */
         #define ALLOC_HIGH    0x20 /* __GFP_HIGH set */
         #define ALLOC_CPUSET    0x40 /* check for correct cpuset */
         
         /*
          * This is the 'heart' of the zoned buddy allocator.
          */
         struct page * fastcall
         __alloc_pages(gfp_t gfp_mask, unsigned int order,
             struct zonelist *zonelist)
         {
           const gfp_t wait = gfp_mask & __GFP_WAIT;
           struct zone **z;
           struct page *page;
           struct reclaim_state reclaim_state;
           struct task_struct *p = current;
           int do_retry;
           int alloc_flags;
           int did_some_progress;
         
           might_sleep_if(wait);
         
           if (should_fail_alloc_page(gfp_mask, order))
             return NULL;
         
         restart:
           z = zonelist->zones;  /* the list of zones suitable for gfp_mask */
         
           if (unlikely(*z == NULL)) {
             /*
              * Happens if we have an empty zonelist as a result of
              * GFP_THISNODE being used on a memoryless node
              */
             return NULL;
           }
         
           /* 1.最简单的情形，空闲内存足够 */
           page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
                 zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);
           if (page)
             goto got_pg;
         
           /*
            * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
            * __GFP_NOWARN set) should not cause reclaim since the subsystem
            * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
            * using a larger set of nodes after it has established that the
            * allowed per node queues are empty and that nodes are
            * over allocated.
            */
           if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
             goto nopage;
         
           /* 2.第一次没有取得内存，说明内存不太够了，内核再次遍历备用列表中的所有
           *    内存域，每次都调用wakeup_kswapd来唤醒换出页守护进程*/
           for (z = zonelist->zones; *z; z++)
             wakeup_kswapd(*z, order);
         
           /*
            * OK, we're below the kswapd watermark and have kicked background
            * reclaim. Now things get more complex, so set up alloc_flags according
            * to how we want to proceed.
            *
            * The caller may dip into page reserves a bit more if the caller
            * cannot run direct reclaim, or if the caller has realtime scheduling
            * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
            * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
            */
           /* 并且会调整分配标志，使的分配更容易成功，将水印降低到最小值 */
           alloc_flags = ALLOC_WMARK_MIN;
           if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
             alloc_flags |= ALLOC_HARDER;
           if (gfp_mask & __GFP_HIGH)
             alloc_flags |= ALLOC_HIGH;
           if (wait)
             alloc_flags |= ALLOC_CPUSET;
         
           /*
            * Go through the zonelist again. Let __GFP_HIGH and allocations
            * coming from realtime tasks go deeper into reserves.
            *
            * This is the last chance, in general, before the goto nopage.
            * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
            * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
            */
           page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);
           if (page)
             goto got_pg;
         
           /* This allocation should allow future memory freeing. */
         
           /* 3.如果再次失败，内核会采取更强有力的措施,这次完全忽略水印 */
         rebalance:
           if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
               && !in_interrupt()) {
             if (!(gfp_mask & __GFP_NOMEMALLOC)) {
         nofail_alloc:
               /* go through the zonelist yet again, ignoring mins */
               page = get_page_from_freelist(gfp_mask, order,
                 zonelist, ALLOC_NO_WATERMARKS);
               if (page)
                 goto got_pg;
               if (gfp_mask & __GFP_NOFAIL) {
                 congestion_wait(WRITE, HZ/50);
                 goto nofail_alloc;
               }
             }
             goto nopage;
           }
         
           /* Atomic allocations - we can't balance anything */
           if (!wait)
             goto nopage;
         
           cond_resched();
         
           /* We now go into synchronous reclaim */
           /* 4.同步回收状态,和换出守护进程的区别？ */
           cpuset_memory_pressure_bump();
           p->flags |= PF_MEMALLOC;
           reclaim_state.reclaimed_slab = 0;
           p->reclaim_state = &reclaim_state;
         
           did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);
         
           p->reclaim_state = NULL;
           p->flags &= ~PF_MEMALLOC;
         
           cond_resched();
         
           /* 如果分配多页，缓存中的页也会被拿回伙伴系统 */
           if (order != 0)
             drain_all_local_pages();
         
           /* 如果try_to_free_pages释放了一些页，再次尝试获取 */
           if (likely(did_some_progress)) {
             page = get_page_from_freelist(gfp_mask, order,
                     zonelist, alloc_flags);
             if (page)
               goto got_pg;
           } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
             if (!try_set_zone_oom(zonelist)) {
               schedule_timeout_uninterruptible(1);
               goto restart;
             }
         
             /*
              * Go through the zonelist yet one more time, keep
              * very high watermark here, this is only to catch
              * a parallel oom killing, we must fail if we're still
              * under heavy pressure.
              */
             /* 5.out_of_memory，选择一个内核认为犯有分配过多内存“罪行”的进程，并杀掉该进程 */
             page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
                 zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
             if (page) {
               clear_zonelist_oom(zonelist);
               goto got_pg;
             }
         
             /* The OOM killer will not help higher order allocs so fail */
             /* 如果要分配大页，那么内核会选择放过选择的“罪行”进程 */
             if (order > PAGE_ALLOC_COSTLY_ORDER) {
               clear_zonelist_oom(zonelist);
               goto nopage;
             }
         
             out_of_memory(zonelist, gfp_mask, order);
             clear_zonelist_oom(zonelist);
             goto restart;
           }
         
           /*
            * Don't let big-order allocations loop unless the caller explicitly
            * requests that.  Wait for some write requests to complete then retry.
            *
            * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
            * <= 3, but that may not be true in other implementations.
            */
           do_retry = 0;
           if (!(gfp_mask & __GFP_NORETRY)) {
             if ((order <= PAGE_ALLOC_COSTLY_ORDER) ||
                     (gfp_mask & __GFP_REPEAT))
               do_retry = 1;
             if (gfp_mask & __GFP_NOFAIL)
               do_retry = 1;
           }
           if (do_retry) {
             congestion_wait(WRITE, HZ/50);
             goto rebalance;
           }
         
         nopage:
           if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
             printk(KERN_WARNING "%s: page allocation failure."
               " order:%d, mode:0x%x\n",
               p->comm, order, gfp_mask);
             dump_stack();
             show_mem();
           }
         got_pg:
           return page;
         }
         
         
         
         
         
         
         /*
          * get_page_from_freelist goes through the zonelist trying to allocate
          * a page.
          */
         /* 重要的辅助函数，通过标志集和分配阶来判断是否能进行分配 */
         static struct page *
         get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
             struct zonelist *zonelist, int alloc_flags)
         {
           struct zone **z;
           struct page *page = NULL;
           int classzone_idx = zone_idx(zonelist->zones[0]);
           struct zone *zone;
           nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
           int zlc_active = 0;   /* set if using zonelist_cache */
           int did_zlc_setup = 0;    /* just call zlc_setup() one time */
           enum zone_type highest_zoneidx = -1; /* Gets set for policy zonelists */
         
         zonelist_scan:
           /*
            * Scan zonelist, looking for a zone with enough free.
            * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
            */
           z = zonelist->zones;
         
           /* 遍历备用列表的所有内存域，用最简单的方式查找一个适当的空闲内存块 */
           do {
             /*
              * In NUMA, this could be a policy zonelist which contains
              * zones that may not be allowed by the current gfp_mask.
              * Check the zone is allowed by the current flags
              */
             if (unlikely(alloc_should_filter_zonelist(zonelist))) {
               if (highest_zoneidx == -1)
                 highest_zoneidx = gfp_zone(gfp_mask);
               if (zone_idx(*z) > highest_zoneidx)
                 continue;
             }
         
             if (NUMA_BUILD && zlc_active &&
               !zlc_zone_worth_trying(zonelist, z, allowednodes))
                 continue;
             zone = *z;
             if ((alloc_flags & ALLOC_CPUSET) &&
                 /* 辅助函数，用于检查给定内存域是否属于该进程允许允许的cpu */
               !cpuset_zone_allowed_softwall(zone, gfp_mask))
                 goto try_next_zone;
         
             if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
               unsigned long mark;
               if (alloc_flags & ALLOC_WMARK_MIN)
                 mark = zone->pages_min;
               else if (alloc_flags & ALLOC_WMARK_LOW)
                 mark = zone->pages_low;
               else
                 mark = zone->pages_high;
               /* 重要的辅助函数，检查所遍历到的内存域是否有足够的空闲页，并试图
               *  分配一个连续的内存块*/
               if (!zone_watermark_ok(zone, order, mark,
                     classzone_idx, alloc_flags)) {
                 if (!zone_reclaim_mode ||
                     !zone_reclaim(zone, gfp_mask, order))
                   goto this_zone_full;
               }
             }
         
             /**** 重要的核心函数，伙伴系统的核心 */
             page = buffered_rmqueue(zonelist, zone, order, gfp_mask);
             if (page)
               break;
         this_zone_full:
             if (NUMA_BUILD)
               zlc_mark_zone_full(zonelist, z);
         try_next_zone:
             if (NUMA_BUILD && !did_zlc_setup) {
               /* we do zlc_setup after the first zone is tried */
               allowednodes = zlc_setup(zonelist, alloc_flags);
               zlc_active = 1;
               did_zlc_setup = 1;
             }
           } while (*(++z) != NULL);
         
           if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
             /* Disable zlc cache for second zonelist scan */
             zlc_active = 0;
             goto zonelist_scan;
           }
           return page;
         }
         

      4. 伙伴系统核心 buffered_rmqueue
         

         到目前为止，我们只知道，如果判断出内存域中有足够的空闲页就会委托给buffered_rmqueue，但是 足够的空闲页是包括所有的阶的总量，所以不一定能保证分配成功。

         buffered_{rmqueue的任务主要有两个}：

         1. 检查这些页是否是连续的
         2. 从free_{lists移除这些页}，这可能需要分解并重排内存区

         其主要流程图为：

         

         /*
          * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
          * we cheat by calling it from here, in the order > 0 path.  Saves a branch
          * or two.
          */
         static struct page *buffered_rmqueue(struct zonelist *zonelist,
               struct zone *zone, int order, gfp_t gfp_flags)
         {
           unsigned long flags;
           struct page *page;
           /* 设置了COLD标志，那么必须从per-CPU缓存中取得冷页,
           *  专门设置冷页的目的是：有些页被访问的次数很少，所以把他
           *  放到catch中太浪费了 */
           /* 两次取反确保cold为0或1 */
           int cold = !!(gfp_flags & __GFP_COLD);
           int cpu;
           /* 根据标志确定迁移列表, (重要)页的迁移类型存储在struct page的private成员中*/
           int migratetype = allocflags_to_migratetype(gfp_flags);
         
         again:
           cpu  = get_cpu();
           /* 如果只请求一页，内核会借助per-CPU缓存加速请求的处理 */
           if (likely(order == 0)) {
             struct per_cpu_pages *pcp;
         
             pcp = &zone_pcp(zone, cpu)->pcp[cold];
             local_irq_save(flags);
             if (!pcp->count) {
               /* 重新用伙伴系统中的页填充缓存 */
               pcp->count = rmqueue_bulk(zone, 0,
                   pcp->batch, &pcp->list, migratetype);
               if (unlikely(!pcp->count))
                 goto failed;
             }
         
             /* Find a page of the appropriate migrate type */
             /* 检查是否有指定迁移类型的页可用，如果前一次用其他迁移类型的页填充了缓存，
             *  可能找不到，*/
             list_for_each_entry(page, &pcp->list, lru)
               if (page_private(page) == migratetype)
                 break;
         
             /* Allocate more to the pcp list if necessary */
             /* 找不到的话就要向缓存中添加一些符合当前迁移类型要求的页 */
             if (unlikely(&page->lru == &pcp->list)) {
               pcp->count += rmqueue_bulk(zone, 0,
                   pcp->batch, &pcp->list, migratetype);
               page = list_entry(pcp->list.next, struct page, lru);
             }
         
             list_del(&page->lru);
             pcp->count--;
         
             /* 需要分配多页 */
           } else {
             spin_lock_irqsave(&zone->lock, flags);
             /* (伙伴系统核心函数)从伙伴系统获得内存块，如有必要会自动分解大块内存 */
             page = __rmqueue(zone, order, migratetype);
             spin_unlock(&zone->lock);
             if (!page)
               goto failed;
           }
         
           __count_zone_vm_events(PGALLOC, zone, 1 << order);
           zone_statistics(zonelist, zone);
           local_irq_restore(flags);
           put_cpu();
         
           VM_BUG_ON(bad_range(zone, page));
           /* 对页进行必要的检查，并将第一页的引用计数置为初始值1 */
           if (prep_new_page(page, order, gfp_flags))
             goto again;
           return page;
         
         failed:
           local_irq_restore(flags);
           put_cpu();
           return NULL;
         }
         
         /*
          * Do the hard work of removing an element from the buddy allocator.
          * Call me with the zone->lock already held.
          */
         static struct page *__rmqueue(struct zone *zone, unsigned int order,
                                       int migratetype)
         {
           struct page *page;
         
           /* 根据传递进来的分配阶，用于获取页的内存域，迁移类型，
            扫描页的列表，知道找到适当的连续内存块*/
           page = __rmqueue_smallest(zone, order, migratetype);
         
           if (unlikely(!page))
             /* 如果指定的迁移列表不能满足分配请求，则调用__rmqueue_fallback尝试
             *  其他迁移列表，作为应急措施*/
             page = __rmqueue_fallback(zone, order, migratetype);
         
           return page;
         }
         
         /*
          * Go through the free lists for the given migratetype and remove
          * the smallest available page from the freelists
          */
         static struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                                                int migratetype)
         {
           unsigned int current_order;
           struct free_area * area;
           struct page *page;
         
           /* Find a page of the appropriate size in the preferred list */
           /* 遍历每个大于等于当前分配阶的正确迁移列表 */
           for (current_order = order; current_order < MAX_ORDER; ++current_order) {
             area = &(zone->free_area[current_order]);
             if (list_empty(&area->free_list[migratetype]))
               continue;
         
             page = list_entry(area->free_list[migratetype].next,
                               struct page, lru);
             list_del(&page->lru);
             /* 从页中删除PG_buddy标志位,并将struct page的private成员设置为0(存的不是迁移类型吗?) */
             rmv_page_order(page);
             area->nr_free--;
             /* 更新当前内存域的统计量 */
             __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
             /* 如果取到的内存块的页数大于请求的数， 拆分该内存块 */
             expand(zone, page, order, current_order, area, migratetype);
             return page;
           }
         
           return NULL;
         }
         
         /* Remove an element from the buddy allocator from the fallback list */
         /* 备用次序中分配 */
         static struct page *__rmqueue_fallback(struct zone *zone, int order,
                     int start_migratetype)
         {
           struct free_area * area;
           int current_order;
           struct page *page;
           int migratetype, i;
         
           /* Find the largest possible block of pages in the other list */
           /* 遍历备用列表的不同迁移类型，（重要）按阶从大到小遍历，因为
              这样能尽可能得到大块的内存，从而减少向其他类型引入碎片*/
           for (current_order = MAX_ORDER-1; current_order >= order;
                     --current_order) {
             for (i = 0; i < MIGRATE_TYPES - 1; i++) {
               migratetype = fallbacks[start_migratetype][i];
         
               /* MIGRATE_RESERVE handled later if necessary */
               if (migratetype == MIGRATE_RESERVE)
                 continue;
         
               area = &(zone->free_area[current_order]);
               if (list_empty(&area->free_list[migratetype]))
                 continue;
         
               page = list_entry(area->free_list[migratetype].next,
                   struct page, lru);
               area->nr_free--;
         
               /*
                * If breaking a large block of pages, move all free
                * pages to the preferred allocation list. If falling
                * back for a reclaimable kernel allocation, be more
                * agressive about taking ownership of free pages
                */
               /* 这样做是因为如果剩余部分也是一个比较大的内存块，那么将整个内存块
               *  都转移到当前分配类型对应的迁移列表是有意义的,这样可以减少碎片*/
               if (unlikely(current_order >= (pageblock_order >> 1)) ||
                   start_migratetype == MIGRATE_RECLAIMABLE) {
                 unsigned long pages;
                 pages = move_freepages_block(zone, page,
                         start_migratetype);
         
                 /* Claim the whole block if over half of it is free */
                 if (pages >= (1 << (pageblock_order-1)))
                   set_pageblock_migratetype(page,
                         start_migratetype);
         
                 migratetype = start_migratetype;
               }
         
               /* Remove the page from the freelists */
               list_del(&page->lru);
               rmv_page_order(page);
               __mod_zone_page_state(zone, NR_FREE_PAGES,
                       -(1UL << order));
         
               if (current_order == pageblock_order)
                 set_pageblock_migratetype(page,
                       start_migratetype);
         
               expand(zone, page, order, current_order, area, migratetype);
               return page;
             }
           }
         
           /* Use MIGRATE_RESERVE rather than fail an allocation */
           /* 如果所以备用列表也都分配失败，尝试从保留类型中分配 */
           return __rmqueue_smallest(zone, order, MIGRATE_RESERVE);
         }
         /*
          * This array describes the order lists are fallen back to when
          * the free lists for the desirable migrate type are depleted
          */
         static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
           [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
           [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
           [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
           [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
         };
         
         
         
         
         
         /*
          * This page is about to be returned from the page allocator
          */
         static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
         {
           if (unlikely(page_mapcount(page) |
             (page->mapping != NULL)  |
             (page_count(page) != 0)  |
             (page->flags & (
               1 << PG_lru |
               1 << PG_private |
               1 << PG_locked  |
               1 << PG_active  |
               1 << PG_dirty |
               1 << PG_slab    |
               1 << PG_swapcache |
               1 << PG_writeback |
               1 << PG_reserved |
               1 << PG_buddy ))))
             bad_page(page);
         
           /*
            * For now, we report if PG_reserved was found set, but do not
            * clear it, and do not allocate the page: as a safety net.
            */
           if (PageReserved(page))
             return 1;
         
           page->flags &= ~(1 << PG_uptodate | 1 << PG_error | 1 << PG_readahead |
               1 << PG_referenced | 1 << PG_arch_1 |
               1 << PG_owner_priv_1 | 1 << PG_mappedtodisk);
           set_page_private(page, 0);
           set_page_refcounted(page);
         
           arch_alloc_page(page, order);
           kernel_map_pages(page, 1 << order, 1);
         
           if (gfp_flags & __GFP_ZERO)
             prep_zero_page(page, order, gfp_flags);
         
           /* 将请求的多页组成复合页，详见下文 */
           if (order && (gfp_flags & __GFP_COMP))
             prep_compound_page(page, order);
         
           return 0;
         }
         

         复合页：

         

      5. 释放页 __freepages
         

         __{freepages是释放内存的基础函数,其代码流程如下}：

         

         fastcall void __free_pages(struct page *page, unsigned int order)
         {
           if (put_page_testzero(page)) {
             if (order == 0)    /* 如果分配单页 */
               free_hot_page(page);
             else               /* 分配多页 */
               __free_pages_ok(page, order);
           }
         }
         
         static void fastcall free_hot_cold_page(struct page *page, int cold)
         {
           struct zone *zone = page_zone(page);
           struct per_cpu_pages *pcp;
           unsigned long flags;
         
           if (PageAnon(page))
             page->mapping = NULL;
           if (free_pages_check(page))
             return;
         
           if (!PageHighMem(page))
             debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
           arch_free_page(page, 0);
           kernel_map_pages(page, 1, 0);
         
           pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
           local_irq_save(flags);
           __count_vm_event(PGFREE);
           list_add(&page->lru, &pcp->list);
           /* 将private设置为迁移类型 */
           set_page_private(page, get_pageblock_migratetype(page));
           pcp->count++;
           /* 懒惰合并,能减少合并次数而节约时间 */
           if (pcp->count >= pcp->high) {  /* 如果缓存中的页超出范围，将batch个内存页还给伙伴系统 */
             free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
             pcp->count -= pcp->batch;
           }
           local_irq_restore(flags);
           put_cpu();
         }
         
         static void __free_pages_ok(struct page *page, unsigned int order)
         {
           unsigned long flags;
           int i;
           int reserved = 0;
         
           for (i = 0 ; i < (1 << order) ; ++i)
             reserved += free_pages_check(page + i);
           if (reserved)
             return;
         
           if (!PageHighMem(page))
             debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
           arch_free_page(page, order);
           kernel_map_pages(page, 1 << order, 0);
         
           local_irq_save(flags);
           __count_vm_events(PGFREE, 1 << order);
           /* 相关内存区被添加到伙伴系统中适当的free_area列表中,并递归合并,具体
           *   例子看下图*/
           free_one_page(page_zone(page), page, order);
           local_irq_restore(flags);
         }
         

         

         

      6. 内核不连续页的分配vmalloc
         

         我们知道，物理上连续的映射对内核是最好的：

         1. 有些求地址操作可以直接线性求出，不需要经过页表计算，也不需要复杂的数据结构
         2. 减少TLB占用
         3. catch命中率更高，所以速度更快

         但是这并不总是能成功，特别是开机很久之后，因为这时内存可能已经比较碎片化了。 所以内核也需要使用像用户态一样的技术：通过处理器的分页机制，分配物理上不连续但虚拟空间 连续的内存。当然这会降低速度并占用TLB.

         内核分配了其虚拟空间的一部分用于建立这种连续映射(32和64位都有)。并提供vmalloc接口函数 来为内核建立连续映射。

         vmalloc最著名的实例是内核对模块的实现。还有设备和声音驱动中。vmalloc内存页总是优先使用 高端内存。 其实现对应的数据结构是：

         struct vm_struct {
           /* keep next,addr,size together to speedup lookups */
           struct vm_struct  *next;
           void      *addr;
           unsigned long   size;
           unsigned long   flags;
           struct page   **pages;
           unsigned int    nr_pages;
           unsigned long   phys_addr;
         };
         

         书中给除了该结构的一个实例：

         

         • vmalloc分配流程：

           1. get_{vmarea在vmalloc地址空间中找到适当的区域}
           2. 从伙伴系统中分配各个物理页，重点是注意他是一页一页分配的，而不是一次分配一大块， 确保在物理内存有严重碎片的情况下，vmalloc依然可以工作。

           3， map_{vmarea将这些页连续地映射到vmalloc区域中,并正确设置相关的页表项}

           

         • 内核虚拟映射内存的释放：

           

      7. 内核其他映射类型
         

         尽管vmalloc可以用于从高端内存域向内核映射页帧，但是内核还提供了其他函数用于将ZONE_HIGHMEM 页帧显式映射到内核地址空间中：

         1. 持久映射kmap
         2. 固定映射kmap_atomic

         因为现在用的基本是64位机器，已经没有了ZONE_HIGMEM，所以这里不详细了解这些映射了，因为 64下这些操作就是一些很简单的宏：

         static inline void *kmap(struct page *page)
         {
           might_sleep();
           return page_address(page);
         }
         
         #define kunmap(page) do { (void) (page); } while (0)
         
         #include <asm/kmap_types.h>
         
         static inline void *kmap_atomic(struct page *page, enum km_type idx)
         {
           pagefault_disable();
           return page_address(page);
         }
         #define kmap_atomic_prot(page, idx, prot) kmap_atomic(page, idx)
         
         #define kunmap_atomic(addr, idx)  do { pagefault_enable(); } while (0)
         #define kmap_atomic_pfn(pfn, idx) kmap_atomic(pfn_to_page(pfn), (idx))
         #define kmap_atomic_to_page(ptr)  virt_to_page(ptr)
         
         #define kmap_flush_unused() do {} while(0)
         #endif
         

6. slab分配器
   

   伙伴系统只支持页级别的内存分配，这个单位太大了，我们需要一个可以以字节为单位的分配器。 它的实现应该尽可能紧凑，以便不要对处理器的高速缓存和TLB带来显著的影响。linux实现了 一个这样的分配器slab。它不仅可以用来分配小内存，而且也用做一个缓存。

   1. slab相对直接使用伙伴系统的优势：
      
      1. 由于内核不必使用伙伴系统算法，分配内存处理时间会变短
      2. slab作为缓存将释放的内存保存在它的内部列表中，并不马上还给伙伴系统，所以再次使用 该内存块时，它依然在cpu高速缓存中的概率较高
      3. 有助于防止不受欢迎的缓存“污染”。因为调用伙伴系统的操作对系统的数据和指令的高速 缓存有相当的影响。
      4. 实现缓存的均匀利用。伙伴系统取的内存，其地址总是在2的幂次的整数倍附近。这种地址 分布使得某些缓存行过度使用，而其他的则几乎为空。多处理器下还可能因为不同内存地址 在不同的总线上传输，使得有些总线拥塞，而其他几乎没有使用。 slab通过slab着色能够 实现均匀地利用cpu缓存。

      slab着色： http://www.360doc.com/content/12/0828/15/7982302_232808690.shtml

   2. slob和slub
      

      这两个函数用于特定的硬件，实现的功能和slab差不多，slob用于小型的嵌入式系统，slub 用于大型系统上

   3. 三个函数提供的标准接口
      

      不管slab，slob还是slub，都实现了一组特定的函数，用于内存分配和缓存。它们与分配器 的关系如图：

      

   4. slab数据结构
      

      slab主要由struct kmem_{cache结构来表示,其中}，每个kmem_{cache只缓存一种对象}。 多个对象会合并成一个组，覆盖一个或多个连续页帧。这种组称作slab；每个kmem_cache 由多个slab组成。其概览图如下：

      

      struct kmem_{cache主要成员有}:

      struct kmem_cache {
      /* 1) per-cpu data, touched during every alloc/free */
        struct array_cache *array[NR_CPUS];  /* 每次分配/释放期间都会访问, 其具体结构在下面代码给出 */
      /* 2) Cache tunables. Protected by cache_chain_mutex */
        /* 可调整的缓存参数 */
        unsigned int batchcount; /* per-CPU列表为空时，从缓存的slab中获取对象的数目,
                                  还表示 在缓存增长时分配的对象数目*/
        unsigned int limit;      /* 指定per-CPU列表中保存的对象的最大数目, 如果超出该值，
                                  内核会将batchcount个对象返回给slab */
        unsigned int shared;
      
        unsigned int buffer_size;  /* 缓存中管理的对象的长度 */
        u32 reciprocal_buffer_size;  /* 用来加快除法的计算 */
      /* 3) touched by every alloc & free from the backend */
      
        unsigned int flags;   /* constant flags */
        /* 表示最多可有多少对象能放入slab */
        unsigned int num;   /* # of objs per slab */
      
      /* 4) cache_grow/shrink */
        /* order of pgs per slab (2^n) */
        unsigned int gfporder;   /* 表示每个slab包含2^gfproder页 */
      
        /* force GFP flags, e.g. GFP_DMA */
        gfp_t gfpflags;
      
        size_t colour;      /* cache colouring range */ /* 着色相关 */
        unsigned int colour_off;  /* colour offset */
        struct kmem_cache *slabp_cache;
        unsigned int slab_size;
        unsigned int dflags;    /* dynamic flags */
      
        /* constructor func */
        void (*ctor)(struct kmem_cache *, void *);
      
      /* 5) cache creation/removal */
        const char *name;    /* /proc/slabinfo中的名称 */
        struct list_head next; /* 将所有实例保存在全局链表cache_chain上 */
      
      /* 6) statistics */
      #if STATS
        unsigned long num_active;
        unsigned long num_allocations;
        unsigned long high_mark;
        unsigned long grown;
        unsigned long reaped;
        unsigned long errors;
        unsigned long max_freeable;
        unsigned long node_allocs;
        unsigned long node_frees;
        unsigned long node_overflow;
        atomic_t allochit;
        atomic_t allocmiss;
        atomic_t freehit;
        atomic_t freemiss;
      #endif
      #if DEBUG
        /*
         * If debugging is enabled, then the allocator can add additional
         * fields and/or padding to every object. buffer_size contains the total
         * object size including these internal fields, the following two
         * variables contain the offset to the user object and its size.
         */
        int obj_offset;
        int obj_size;
      #endif
        /*
         * We put nodelists[] at the end of kmem_cache, because we want to size
         * this array to nr_node_ids slots instead of MAX_NUMNODES
         * (see kmem_cache_init())
         * We still use [MAX_NUMNODES] and not [1] or [0] because cache_cache
         * is statically defined, so we reserve the max number of nodes.
         */
        struct kmem_list3 *nodelists[MAX_NUMNODES]; /* 每个数组项对应于系统中一个可能的
                                                     内存结点，具体结构在下面讨论*/
        /*
         * Do not add fields after nodelists[]
         */
      };
      
      
      /*
       * struct array_cache
       *
       * Purpose:
       * - LIFO ordering, to hand out cache-warm objects from _alloc
       * - reduce the number of linked list operations
       * - reduce spinlock operations
       *
       * The limit is stored in the per-cpu structure to reduce the data cache
       * footprint.
       *
       */
      struct array_cache {
        unsigned int avail;  /* 当前可用对象的数目 */
        unsigned int limit;
        unsigned int batchcount;
        unsigned int touched;  /* 在从缓存移除一个对象时，将touched置为1；缓存收缩时，置为0 */
        spinlock_t lock;
        void *entry[];  /*
                         * Must have this definition in here for the proper
                         * alignment of array_cache. Also simplifies accessing
                         * the entries.
                         */
      };
      
      /*
       * The slab lists for all objects.
       */
      struct kmem_list3 {
        /* 部分空闲，全满，全空闲slab链表 */
        struct list_head slabs_partial; /* partial list first, better asm code */
        struct list_head slabs_full;
        struct list_head slabs_free;
        unsigned long free_objects;  /* slabs_partial和slabs_free的所有slab中空闲对象的总数 */
        unsigned int free_limit;     /* 空闲对象的最大数目限制 */
        unsigned int colour_next; /* Per-node cache coloring */
        spinlock_t list_lock;
        struct array_cache *shared; /* shared per node */
        struct array_cache **alien; /* on other nodes */
        unsigned long next_reap;  /* updated without locking */
        /* 表示缓存是否是活动的 */
        int free_touched;   /* updated without locking */
      };
      

      

      可以看到，该结构不是直接从slab中取对象的，而是针对每个cpu有一个per-CPU指针，指向slab 中的未使用对象。这样做是为了更好地利用CPU高速缓存。它在分配和释放对象时，采用后进先出的 原理(LIFO)。其背后的原理是，刚释放的对象很可能仍然处于CPU高速缓存中。更进一步，slab 对象分配体系按分配成本和操作对CPU高速缓存及TLB的负面影响从低到高可以排序为三层：

      1. 仍然处于CPU高速缓存中的per-CPU对象
      2. 现存slab中未使用的对象
      3. 刚使用伙伴系统分配的新slab中未使用的对象

      一个slab组的精细结构：

      其中，它的头部管理数据中有一个数组，每个数组项对于一个对象，用来记录下一个空闲对象的索引， 所以只有在对象没有分配时，相应的数组项才有意义。如下图：

      

      最后，内核有时候需要从对象自身识别对象所在的slab，内核利用如下机制来完成该任务：

      1. 根据对象的物理内存地址，可以找到相关的页，因此可以在全局mem_{map数组中找到对应的page} 实例
      2. slab缓存中的页面而言，page结构中的链表是没有用到的，所以可以复用它来完成该任务： page->lru.next 指向页驻留的缓存的管理结构 page->lru.prev 指向保存该页的slab的管理结构
   5. API
      
      1. TODO 初始化（自举）
         
      2. 创建缓存 kmem_cachecreate
         

         

      3. 分配对象
         

         其中，cache_{grow代表缓存的增长}：

         

      4. 释放对象
         

         

      5. 销毁缓存 kmem_cachedestroy
         
      6. 通用缓存
         

         如果不涉及对象缓存，则必须调用kmalloc和kfree函数,这两个函数相当于用户空间C 标准库malloc和free函数的内核等价物

         /* 每次调用kmalloc时，内核找到最适合的缓存，并从中分配一个对象来满足要求
            最合适的意思是：如果没有刚刚适合大小的缓存，则分配稍大的*/
         void *kmalloc(size, flags);
         
         void kfree(*ptr);
         

         kmalloc的基础是一个数组，数组项是cache_sizes结构，其中是一些分别用于不同内存长度的slab缓存，

         /* Size description struct for general caches. */
         struct cache_sizes {
           /* 该数组项负责的内存区的长度 */
           size_t      cs_size;
           struct kmem_cache *cs_cachep;
         #ifdef CONFIG_ZONE_DMA
           struct kmem_cache *cs_dmacachep;
         #endif
         };
         

   6. TODO 处理器高速缓存和TLB控制