发表于

Golang实现Json序列化

学习自：https://golang.org/pkg/encoding/json/#Marshal

先来看看api的使用：

1
func Marshal(v interface{}) ([]byte, error)

基本作用就是返回v的json编码

作用过程

Marshal递归地遍历v，如果遇到实现了Marshaler接口的值并且不是nil指针，Marshal会调用MarshalJSON方法来生成JSON。如果不存在MarshalJSON方法，但该值实现了encoding.TextMarshaler，则Marshal会调用MarshalText方法将结果编码为JSON字符。

编码结果

Marshal使用以下类型相关的默认编码：

  • bool值编码为JSON的布尔值；
  • 浮点数、整数和number值编码为JSON数字
  • 字符串值编码为有效的UTF-8的JSON字符串，并且会用Unicode替换无效字节

为了防止某些浏览器会将JSON输出解析为HTML，尖括号<和>被转义为03c和03e。基于相同的原因，符号&会被转义为026

可以使用调用了SetEscapeHTML(false)的编码器禁止此转义

  • 数组和切片值编码为JSON数组，但了[]字节会被编码为base64编码的字符串，而nil切片编码为空JSON值
  • 结构体则是编码为JSON对象，每个structure字段都会成为JSON对象的成员，并且会使用该字段名称作为对象值

关于structure编码为JSON

在golang的结构体中，每个成员变量都可以附带一个Tag说明，因此每个struct字段的编码可以通过存储在以Json为key的tag进行定制化。比如：

1
2
3
4
type User struct {
    UserId   int    `json:"user_id,omitempty" bson:"user_id"`
    UserName string `json:"user_name" bson:"user_name"`
}

这些格式化字符串给出了字符的名称，还可以通过逗号在后面加上一系列的选项。tag中如果带有”omitempty”选项，那么如果该字段值为空，就不会输出到JSON串中。

还有一种特别的情况，如果字段标记为“ - ”，则始终省略该字段。请注意，比较特别的是仍然可以使用标记“ - ，”生成名称为“ - ”的字段。比如：

1
2
3
4
5
// Field is ignored by this package.
Field int `json:"-"`

// Field appears in JSON as key "-".
Field int `json:"-,"`

“string”选项表示字段在JSON编码的字符串中存储为JSON。它仅适用于字符串，浮点，整数或布尔类型的字段。在与JavaScript程序通信时，有时会使用这种额外的编码级别。

其它

map

map被编码为JSON对象，而且map的key类型必须是字符串、整数或者实现了encoding.TextMarshaler。其中：

  • 字符串类型会被直接实现
  • encoding.TextMarshaler的会被marshaled
  • 整数则会转为字符串

接口

接口会被编码为接口中包含的值，nil接口值则被编码为null JSON值

另外：

Channel, complex, and function values cannot be encoded in JSON. Attempting to encode such a value causes Marshal to return an UnsupportedTypeError.

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

import (
	"encoding/json"
	"fmt"
	"os"
)

func main() {
	type ColorGroup struct {
		ID     int
		Name   string
		Colors []string
	}
	group := ColorGroup{
		ID:     1,
		Name:   "Reds",
		Colors: []string{"Crimson", "Red", "Ruby", "Maroon"},
	}
	b, err := json.Marshal(group)
	if err != nil {
		fmt.Println("error:", err)
	}
	os.Stdout.Write(b)
}

发表于

Pylint学习

Install Pylint

用virtualenv安装pylint：

1
2
3
pip install virtualenv
#超时的话可以这样试一下
pip --default-timeout=100 install virtualenv

创建一个虚拟环境：

1
2
virtualenv --no-site-packages venv
source venv/bin/activate

Invoking pylint

pylint可以在命令行使用，具体用法为：

1
pylint [options] modules_or_packages

从上面的用法可以得知，我们应该提供pylint要检查的python包或者模块的名称。而Pylint不会导入这些包，而是利用Python internals去进行定位。因此我们需要关注PYTHONPATH，防止它去检查已安装的模块版本，而不是开发版本。

如果传给pylint一个单文件，例如这样：

1
pylint mymodules.py

就要保证当前的工作目录为一个package（即目录下有__init__.py）。

另外，也可以在其它的python程序中调用pylint，比如：

1
2
3
4
from pylint import epylint as lint
(pylint_stdout, pylint_stderr) = lint.py_run('hello.py', return_std=True)
print pylint_stdout.getvalue()
print pylint_stderr.getvalue()

command line options

先来看两个基本的选项：

--version show program's version number and exit
-h, --help show help about the command line options 
1
2
3
4
5
6
(venv) ➜  py pylint --version
No config file found, using default configuration
pylint 1.9.3,
astroid 1.6.5
Python 2.7.10 (default, Jul 15 2017, 17:16:57)
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.31)]

接下来介绍一个message control的命令后选项：--disable和--enable，如果我们只是希望启动某些checker，可以先用--disable = all然后使用--enable = <symbol>，其中<symbol>是逗号分隔的检查器名称和消息符号列表。这样的使用方式对于仅仅希望启动少数的checkers非常有用。

举个例子，假如你只想启动相似性检查，可以增加选项：

1
–-disable=all –-enable=similarities

pylint提供的symbol，可以参考：https://docs.pylint.org/en/1.6.0/features.html#messages-control-options

Parallel execution

如果主机的CPU数量超过1个，可以使用-j选项加速pylint的运行，比如：

1
pylint -j 4 mymodule1.py mymodule2.py mymodule3.py mymodule4.py

这样就会产生4个子进程，其中每个提供的模块将被并行检查。checkers发现的问题不会立即显示。 完成检查模块后才会立即显示它们。当提供的参数为0时，将会使用主机上所有CPU的数量。

发表于

支持向量机

间隔与支持向量

考虑这样的训练样本\(D = {(x_1, y_1), (x_2, y_2), ... , (x_m, y_m)}, y_i \in {-1, +1}\)。分类学习最重要的基于训练集D找到一个划分超平面，使得不同类别的样本能够分考。虽然划分平面可能很多，但我们应该尽量找到"位于正中间"的平面，使得robust最好。

在样本空间中，划分超平面可以这样描述： \[ w^Tx + b = 0 \] 其中\(w=(w_1;w_2;...;w_d)\)为法向量，决定平面的方向，而b则是位移，决定的事平面与原点的距离。

样本空间中任意点x到平面的距离记为： \[ r = \frac {|w^Tx+b|} {||w||} \] 假设平面能够正确分类，那么对于 \[ w^T x_i + b \geq +1, y_i +1 \\ w^T x_i + b \leq -1, y_i -1 \] 根据这个公式可以得知，距离平面最近的点使得上式成立，那么这几个样本就成为支持向量，两个异类支持向量到平面的距离之和为： \[ \gamma = \frac {2} {||w||} \] 这就是间隔(margin)。

但如果我们希望找到具有最大间隔的平面，应该要最大化\(\gamma\)，则使得\(\frac{1}{2}{||w||}^2\)最大化。

这就是support vector machine(SVM)的基本模型。

对偶问题

TODO

核函数

在现实生活中，很可能无法找到使得原始样本空间可分的超平面，比如抑或问题就是这样。但我们可以将样本从原始空间映射到一个更高维空间，使得样本在这个特征空间内是线性可分。

经过映射后，假设超平面模型为： \[ f(x) = w^T \Phi(x) + b \] 在利用对偶问题求解时会涉及得到计算内积——\(\Phi(x)^T\Phi(x)\)，由于映射后的特征空间可能维度很高，甚至是无穷维，要想直接计算通常是困难的。因此可以设计这样一个函数，即\(x_i\)与\(x_j\)在特征空间的内积等于它们在原始空间中通过函数k计算的结果。重写解为： \[ f(x) = w^T\Phi(x) + b \\ =\sum_{i=1}^{m}\alpha_iy_i\Phi(x_i)^T\Phi(x) + b \\ =\sum_{i=1}^{m}\alpha_iy_ik(x, x_i) + b \] 但这样还存在一个问题，在不知道$ (x) $形式时该怎么得到核函数呢？

有这么一个定理，如果有这么一个对称函数，它在输入空间中对应的核矩阵是半正定的，那么它就能作为核函数使用。（不懂？？）

以下为一些常见和核函数：

  • 线性核：\(k(x_i, x_j) = x_i^Tx_i\)
  • 多项式核：\(k(x_i, x_j) = (x_i^Tx_j)^d\)
  • 高斯核：\(k(x_i, x_j) = exp(- \frac{ || x_i - x_j ||^2 }{2\sigma^2})\)
  • 拉普拉斯核：\(k(x_i, x_j) = exp(- \frac{ || x_i - x_j ||^2 }{\sigma})\)
  • sigmoid核：\(k(x_i, x_j) = tanh(\beta x_i^T x_j + \theta)\)

软间隔与正则化

todo

支持向量回归

这样的训练样本\(D = {(x_1, y_1), (x_2, y_2), ... , (x_m, y_m)}\)，希望学得一个回归模型，使得f(x)与y尽可能接近，在传统的回归模型中，我们是基于模型输出f(x)与真实输出y之间的差别来计算损失，在这种情况中当且仅当f(x)与y完全相同时，损失才为零。

但是对于SVR，假设我们能容忍f(x)与y之间最多有\(\epsilon\)的偏差，这相当于以f(x)为中心，构建了一个宽度为\(2\epsilon\)的间隔带，若训练样本落入间隔带，则认为是被预测正确的。

于是，SVR问题可以转化为：

\[ min_{w, b} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}\ell_{\epsilon}(f(x_i)-y_i) \\ \]

\[ f(x)=\left\{ \begin{aligned} 0, if |z| \le \epsilon \\ |z| - \epsilon,otherwise \\ \end{aligned} \right. \]

引入松弛变量： \[ min_{w, b, \xi_{i2}, \xi_{i1}} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_{i2}+\xi_{i1}) \]

通过引入拉格朗日乘子，并对目标参数求偏导，最后得到SVR表示为： \[ f(x) = \sum_{i=1}^m (\alpha_{i1}-\alpha_{i2})k(x, x_i)+b \]

核方法

todo

发表于

页高速缓存和页回写

从访问速度来看，内存访问速度高于磁盘访问，而缓存访问速度又高于内存。

缓存手段

页高速缓存是由内存中的物理页面组成，对应的是磁盘上的物理块，可以动态扩大缩小。当内核开始读操作时，会先检查数据是否子啊缓存中，不命中采取磁盘找。

现在的缓存一般焊接在CPU上

写缓存

Linux在调用写操作时，使用的策略是——回写。这种策略是直接写到缓存中，而存储不是立刻更新，而是将页高速缓存中被写入的页面标记成脏页，表示缓存与磁盘不同步。延迟写磁盘，能方便后续对该页面的操作。

缓存回收

Linux实现的是一种改良LRU算法，则使用双链。Linux维护的是两个链表——活跃链表和非活跃链表，非活跃链表的页面是可以被换出的，而两个链表要保持数量平衡。

Linux页高速缓存

由于页高速缓存中的页可能包含多个不连续的物理磁盘块。Linux页高速缓存使用一个新的结构来管理缓存项和页面io操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct address_space {
        struct inode            *host;              /* owning inode */
        struct radix_tree_root  page_tree;          /* radix tree of all pages */
        spinlock_t              tree_lock;          /* page_tree lock */
        unsigned int            i_mmap_writable;    /* VM_SHARED ma count */
        struct prio_tree_root   i_mmap;             /* list of all mappings */
        struct list_head        i_mmap_nonlinear;   /* VM_NONLINEAR ma list */
        spinlock_t              i_mmap_lock;        /* i_mmap lock */
        atomic_t                truncate_count;     /* truncate re count */
        unsigned long           nrpages;            /* total number of pages */
        pgoff_t                 writeback_index;    /* writeback start offset */
        struct address_space_operations   *a_ops;   /* operations table */
        unsigned long           flags;              /* gfp_mask and error flags */
        struct backing_dev_info *backing_dev_info;  /* read-ahead information */
        spinlock_t              private_lock;       /* private lock */
        struct list_head        private_list;       /* private list */
        struct address_space    *assoc_mapping;     /* associated buffers */
};

其中i_mmap字段是一个优先搜索树，它包含了在该结构体中所有共享的与私有的映射页面。

address_space 操作

a_ops域指向地址空间对象中的操作函数表，由adress_space_operations结构体表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct address_space_operations {
        int (*writepage)(struct page *, struct writeback_control *);
        int (*readpage) (struct file *, struct page *);
        int (*sync_page) (struct page *);
        int (*writepages) (struct address_space *, struct writeback_control *);
        int (*set_page_dirty) (struct page *);
        int (*readpages) (struct file *, struct address_space *,struct list_head *, unsigned);
        int (*prepare_write) (struct file *, struct page *, unsigned, unsigned);
        int (*commit_write) (struct file *, struct page *, unsigned, unsigned);
        sector_t (*bmap)(struct address_space *, sector_t);
        int (*invalidatepage) (struct page *, unsigned long);
        int (*releasepage) (struct page *, int);
        int (*direct_IO) (int, struct kiocb *, const struct iovec *,loff_t, unsigned long);
};

这里面最重要的是读写——readpage()和writepage()。

对于readpage，Linux内核试图在页高速缓存中使用find_get_page(mapping, index)找到需要的数据，将一个adress_space对象和一个偏移量传给该方法。如果找不到会返回一个NULL，并且内核新分配一个页面，并之前搜索的页面加入到页高速缓存。

对于writepage，首先在cache中搜索需要的页，如果需要的页不在，则新分配一个空闲项；下一步，内核会创建一个写请求，接着数据被从用户空间拷贝到内核缓冲，最后写入磁盘。

基树

每个address_page对象都有唯一的基树，保存在page_tree结构体中。只要指定了文件偏移量，就可以在基树中迅速检索到希望的页面。

flusher线程

在内存中累积起来的脏页最终会被写回磁盘，当下列3种情况发生时，脏页被写回磁盘：

  • 当空闲内存低于阈值时；
  • 当脏页在内存中驻留时间过长；
  • 当用户进程调用sync()和fsync()时；

在Linux内核中由一群flusher线程执行这三种工作，flusher线程会被周期性唤醒，或者因为空闲内存过低被唤醒。

发表于

Golang测试覆盖率

最近实习在做一些CI/CD的工作，用到了go的一些测试工具，学习记录一下。都是官网博客找的来源：https://blog.golang.org/cover

golang1.2引进了一种新的测试覆盖工具，采用一种特别的方法来生成覆盖率统计数据。

覆盖率测试

代码覆盖率测试是指，通过运行一个测试来查看有多少代码被执行了。如果使用的测试样例导致80%的源代码语句运行，我们就认为代码覆盖率为80%。

go语言引进了一个轻量级的测试框架testing和自带的go test命令来实现单元测试和性能测试。这套框架的原理很简单，就是在2变异之前重写package的源代码以添加检测、编译和运行修改后的源代码，并且将统计信息转移。

golang的覆盖率测试

假设有这样一个源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package size

func Size(a int) string {
    switch {
    case a < 0:
        return "negative"
    case a == 0:
        return "zero"
    case a < 10:
        return "small"
    case a < 100:
        return "big"
    case a < 1000:
        return "huge"
    }
    return "enormous"
}

和这样的一个测试样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package size

import "testing"

type Test struct {
    in  int
    out string
}

var tests = []Test{
    {-1, "negative"},
    {5, "small"},
}

func TestSize(t *testing.T) {
    for i, test := range tests {
        size := Size(test.in)
        if size != test.out {
            t.Errorf("#%d: Size(%d)=%s; want %s", i, test.in, size, test.out)
        }
    }
}

然后使用go test命令加上-cover选项来测试代码覆盖率，产生结果如下：

1
2
3
PASS
coverage: 42.9% of statements
ok  	_/Users/lucien/Study/gosrc	0.006s
  • 由于go test命令只能在一个相应的目录下执行所有文件，注意这两个文件需要在同一个目录下。
  • 另外测试文件必须要以_test.go结尾，这样在执行go test的时候才能执行到相应的代码。
  • 在测试文件中必须要import testing这个包，另外所有测试函数都以Test开头，并且参数是testing.T，用来记录错误或者测试状态；格式为：
1
func TestXxx (t *testing.T) //Xxx开头必须大写

上面的结果显示，我们代码的测试覆盖率为42.9%，这个数字怎么来的呢？当启用测试覆盖的时候，go test会用cover工具在编译之前重写源代码，在原始代码中寻找分支，然后在每个分支"种下"锚点。 等所有的case都跑完后，通过统计执行锚点的数量来计算覆盖率。比如变成这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func Size(a int) string {
    GoCover.Count[0] = 1
    switch {
    case a < 0:
        GoCover.Count[2] = 1
        return "negative"
    case a == 0:
        GoCover.Count[3] = 1
        return "zero"
    case a < 10:
        GoCover.Count[4] = 1
        return "small"
    case a < 100:
        GoCover.Count[5] = 1
        return "big"
    case a < 1000:
        GoCover.Count[6] = 1
        return "huge"
    }
    GoCover.Count[1] = 1
    return "enormous"
}

虽然这样重写代码的方式开销看起来比较昂贵，但实际上它会被编译为单个的move指令，在实际测试时开销仅仅增加3%。

Although that annotating assignment might look expensive, it compiles to a single "move" instruction. Its run-time overhead is therefore modest, adding only about 3% when running a typical (more realistic) test. That makes it reasonable to include test coverage as part of the standard development pipeline.

查看结果

实际上，刚刚那种测试结果看起来比较简陋，我们需要了解更加详细的测试内容，因此我们可以使用go test来输出一个coverage profile，该文件保存着收集的统计信息的文件，使得我们研究它们更加方便。

1
2
3
4
5
% go test -coverprofile=coverage.out 
PASS
coverage: 42.9% of statements
ok      size    0.030s
%

输出结果为：

1
2
3
4
5
6
7
8
mode: set
_/Users/lucien/Study/gosrc/test.go:3.25,4.12 1 1
_/Users/lucien/Study/gosrc/test.go:16.5,16.22 1 0
_/Users/lucien/Study/gosrc/test.go:5.16,6.26 1 1
_/Users/lucien/Study/gosrc/test.go:7.17,8.22 1 0
_/Users/lucien/Study/gosrc/test.go:9.17,10.23 1 1
_/Users/lucien/Study/gosrc/test.go:11.18,12.21 1 0
_/Users/lucien/Study/gosrc/test.go:13.19,14.22 1 0

有了这么一个文件，我们可以不进行测试，直接查看测试结果：

1
2
3
4
% go tool cover -func=coverage.out
size.go:    Size          42.9%
total:      (statements)  42.9%
%

热图

我们可以以多种方式来检测代码覆盖率，go test接受-covermode标志来将覆盖模式设置为以下三种：

  • set：每个语句都运行了吗
  • count：每个语句运行了多少次
  • atomic：跟count一样，但能平行程序中精确计算（使用了来自sync/atomic的原子操作）

运行这样一行命令，会打开一个浏览器，注意查看绿色的强度如何变化。更明亮的绿色表示具有更高的执行次数。将鼠标停留在语句上，会显示具体的执行次数

1
go tool cover -html=count.out

发表于

进程地址空间

在Linux中，所有进程之间都以虚拟方式共享内存。

地址空间

进程地址空间由进程可寻址的虚拟内存组成，使得每个进程都能有一个32bit或者64bit的连续地址空间。

进程只能访问有效内存内的物理内存区域，如果访问非法的内存区域，内核将会终止该进程，返回段错误。

内存区域可以包含：

  • text section；
  • data section；
  • 未初始化的全局变量，bss段；
  • 进程空间栈；
  • 内存映射文件，包括匿名的内存映射，比如由malloc()分配的内存；

内存描述符

内核使用内存描述符结构体来表示进程的地址空间——mm_struct。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
struct mm_struct {
    struct vm_area_struct * mmap;    //指向虚拟区间(VMA)的链表
    struct rb_root mm_rb;            //指向线性区对象红黑树的根
    struct vm_area_struct * mmap_cache;     //指向最近找到的虚拟区间
    unsigned long(*get_unmapped_area) (struct file *filp,
    unsigned long addr, unsigned long len,
    unsigned long pgoff, unsigned long flags);//在进程地址空间中搜索有效线性地址区
    unsigned long(*get_unmapped_exec_area) (struct file *filp,
        unsigned long addr, unsigned long len,
        unsigned long pgoff, unsigned long flags);
    void(*unmap_area) (struct mm_struct *mm, unsigned long addr);//释放线性地址区间时调用的方法
    unsigned long mmap_base;                /* base of mmap area */
    unsigned long task_size;                /* size of task vm space */

    unsigned long cached_hole_size;
    unsigned long free_area_cache;          //内核从这个地址开始搜索进程地址空间中线性地址的空闲区域
    pgd_t * pgd;                            //指向页全局目录
    atomic_t mm_users;                      //次使用计数器，使用这块空间的个数    
    atomic_t mm_count;                      //主使用计数器
    int map_count;                          //线性的个数
    struct rw_semaphore mmap_sem;           //线性区的读/写信号量
    spinlock_t page_table_lock;             //线性区的自旋锁和页表的自旋锁

    struct list_head mmlist;              //指向内存描述符链表中的相邻元素

    /* Special counters, in some configurations protected by the
    * page_table_lock, in other configurations by being atomic.
    */
    mm_counter_t _file_rss; //mm_counter_t代表的类型实际是typedef atomic_long_t
    mm_counter_t _anon_rss;  
    mm_counter_t _swap_usage;

    unsigned long hiwater_rss;    //进程所拥有的最大页框数
    unsigned long hiwater_vm;     //进程线性区中最大页数

    unsigned long total_vm, locked_vm, shared_vm, exec_vm;
    //total_vm 进程地址空间的大小(页数）
    //locked_vm 锁住而不能换出的页的个数
    //shared_vm 共享文件内存映射中的页数

    unsigned long stack_vm, reserved_vm, def_flags, nr_ptes;
    //stack_vm 用户堆栈中的页数
    //reserved_vm 在保留区中的页数或者在特殊线性区中的页数
    //def_flags 线性区默认的访问标志
    //nr_ptes 进程的页表数

    unsigned long start_code, end_code, start_data, end_data;
    //start_code 可执行代码的起始地址
    //end_code 可执行代码的最后地址
    //start_data已初始化数据的起始地址
    // end_data已初始化数据的最后地址

    unsigned long start_brk, brk, start_stack;
    //start_stack堆的起始位置
    //brk堆的当前的最后地址
    //用户堆栈的起始地址

    unsigned long arg_start, arg_end, env_start, env_end;
    //arg_start 命令行参数的起始地址
    //arg_end命令行参数的起始地址
    //env_start环境变量的起始地址
    //env_end环境变量的最后地址

    unsigned long saved_auxv[AT_VECTOR_SIZE]; /* for /proc/PID/auxv */

    struct linux_binfmt *binfmt;

    cpumask_t cpu_vm_mask; //用于惰性TLB交换的位掩码
    /* Architecture-specific MM context */
    mm_context_t context; //指向有关特定结构体系信息的表


    unsigned int faultstamp;
    unsigned int token_priority;
    unsigned int last_interval;

    unsigned long flags; /* Must use atomic bitops to access the bits */

    struct core_state *core_state; /* coredumping support */
#ifdef CONFIG_AIO
    spinlock_t              ioctx_lock;  //用于保护异步I/O上下文链表的锁
    struct hlist_head       ioctx_list;//异步I/O上下文
#endif
#ifdef CONFIG_MM_OWNER
    struct task_struct *owner;
#endif

#ifdef CONFIG_PROC_FS
    unsigned long num_exe_file_vmas;
#endif
#ifdef CONFIG_MMU_NOTIFIER
    struct mmu_notifier_mm *mmu_notifier_mm;
#endif
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
    pgtable_t pmd_huge_pte; /* protected by page_table_lock */
#endif
#ifdef __GENKSYMS__
    unsigned long rh_reserved[2];
#else
    //有多少任务分享这个mm OOM_DISABLE
    union {
        unsigned long rh_reserved_aux;
        atomic_t oom_disable_count;
    };

    /* base of lib map area (ASCII armour) */
    unsigned long shlib_base;
#endif
};

在该结构体中，mm_users记录着使用该地址的进程数目，而mm_count则是mm_struct的主引用计数。比如有9个线程共享改地址，那么mm_users为9，mm_count为1。当mm_count为0时，需要销毁该结构体。

mmap和mm_rb描述相同的对象，该地址空间的全部内存区域，但前者是以链表形式存储，后者则是红黑树形式。一种用来高效遍历，另一种则是为了查询特定内存。

所有的mm_struct都通过自身mmlist连接在一个双向链表中。

分配内存描述符

在task_struct中的mm域存放着该进程的内存描述符，如果父子进程共享内存，需要设置CLONE_VM标识，这样的进程称作线程，在Linux内核中，线程就是共享资源的进程。

1
2
3
4
if (clone_flags & CLONE_VM){
    atomic_inc(&current->mm->mm_users);
    tsk->mm = current->mm;
}

撤销内存描述符

进程退出时，内核会调用exit_mm()函数，进程撤销工作。

mm_struct与内核线程

内核线程没有进程地址空间，也没有内存描述符，所以内核线程的mm域为空。

当一个进程被调度时，该进程的mm域指向的地址空间会被装载到内存。

虚拟内存区域

内存区域由vm_area_struct结构体描述，描述了指定地址空间内连续区间的一个独立内存范围。每个VMA对其mm_struct来说是唯一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
* This struct defines a memory VMM memory area. */
vm_area_struct {
    struct mm_struct * vm_mm; /* VM area parameters */
    unsigned long vm_start;
    unsigned long vm_end;

    /* linked list of VM areas per task, sorted by address */
    struct vm_area_struct *vm_next;

    pgprot_t vm_page_prot;
    unsigned long vm_flags;

    /* AVL tree of VM areas per task, sorted by address */
    short vm_avl_height;
    struct vm_area_struct * vm_avl_left;
    struct vm_area_struct * vm_avl_right;

    /* For areas with an address space and backing store,
    * font-size: 10px;">vm_area_struct *vm_next_share;
    struct vm_area_struct **vm_pprev_share;
    struct vm_operations_struct * vm_ops;
    unsigned long vm_pgoff; /* offset in PAGE_SIZE units, *not* PAGE_CACHE_SIZE */
    struct file * vm_file;
    unsigned long vm_raend;
    void * vm_private_data; /* was vm_pte (shared mem) */
};

VMA标志

VMA是一种位标志，包含在vm_flags内，标记了该内存区域所包含的页面的行为和信息，不同于物理访问权限，反应的是内核处理要遵守的行为标准。

比如可读，写，执行，可共享

VMA操作

vm_area_struct结构体中的vm_ops域指向与指定内存区域相关的操作函数表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

struct vm_operations_struct {
	void (*open)(struct vm_area_struct * area);
	void (*close)(struct vm_area_struct * area);
	int (*fault)(struct vm_area_struct *vma, struct vm_fault *vmf);

	/* notification that a previously read-only page is about to become
	 * writable, if an error is returned it will cause a SIGBUS */
	int (*page_mkwrite)(struct vm_area_struct *vma, struct page *page);

	/* called by access_process_vm when get_user_pages() fails, typically
	 * for use by special VMAs that can switch between memory and hardware
	 */
	int (*access)(struct vm_area_struct *vma, unsigned long addr,
		      void *buf, int len, int write);
#ifdef CONFIG_NUMA
	/*
	 * set_policy() op must add a reference to any non-NULL @new mempolicy
	 * to hold the policy upon return.  Caller should pass NULL @new to
	 * remove a policy and fall back to surrounding context--i.e. do not
	 * install a MPOL_DEFAULT policy, nor the task or system default
	 * mempolicy.
	 */
	int (*set_policy)(struct vm_area_struct *vma, struct mempolicy *new);

	/*
	 * get_policy() op must add reference [mpol_get()] to any policy at
	 * (vma,addr) marked as MPOL_SHARED.  The shared policy infrastructure
	 * in mm/mempolicy.c will do this automatically.
	 * get_policy() must NOT add a ref if the policy at (vma,addr) is not
	 * marked as MPOL_SHARED. vma policies are protected by the mmap_sem.
	 * If no [shared/vma] mempolicy exists at the addr, get_policy() op
	 * must return NULL--i.e., do not "fallback" to task or system default
	 * policy.
	 */
	struct mempolicy *(*get_policy)(struct vm_area_struct *vma,
					unsigned long addr);
	int (*migrate)(struct vm_area_struct *vma, const nodemask_t *from,
		const nodemask_t *to, unsigned long flags);
#endif
};

  • 指定内存区域被加入到一个地址空间时，open函数被调用
  • 指定内存区域被删除时，close函数被调用

内存区域的树型结构和内存区域的链表结构

mmap域使用单独链表连接所有的内存区域对象，每个vm_area_struct结构体通过自身vm_next域连入链表。

而mm_rb则是用红黑树连接所有的内存区域。

操作内存区域

内核经常需要在某个内存区域上执行一些操作。

find_vma()

1
struct vm_area_struct * find_vma(strcut mm_struct *mm, unsigned long addr);

该函数在指定的地址空间中搜搜第一个vm_end大于addr的内存区域，如果找不到则返回NULL。并且该返回结果会被缓存在mmap_cache中，查找时会先从缓存找，搜不到则通过红黑树搜索。

find_vma_prev()

该函数返回第一个小于addr的内存区域。

find_vma_intersection()

该函数返回第一个和指定地址区间相交的VMA。

mmap()和do_mmap()：创建地址区间

内核使用do_mmap()创建一个新的线性地址区间，不过不同的是，如果新创建的地址区间与一个已经存在的地址区间相邻，并且它们具有相邻的访问权限时，两个区间就会合并为一个。

1
2
3
4
5
6
7
8
9
10
11
12
static inline unsigned long do_mmap(struct file *file, 			unsigned long addr,
        unsigned long len, unsigned long prot,
        	unsigned long flag, unsigned long offset)
{
         unsigned long ret = -EINVAL;
         if ((offset + PAGE_ALIGN(len)) < offset)
                   goto out;
         if (!(offset & ~PAGE_MASK))
                   ret = do_mmap_pgoff(file, addr, len, prot, flag, offset >> PAGE_SHIFT);
out:
         return ret;
}

该函数映射由file指定的文件。

mummap()和do_mummap()：删除地址区间

1
int do_mummap(struct mm_struct *mm, unsigned long start, size_t len);

该函数从特定的进程地址空间中删除从地址start开始，长度为len字节的空间。

而mummap()则是对do)mummap()函数的一个简单封装。

页表

应用程序虽然面对的是虚拟内存，但真实操作的是物理内存，因此需要一个从虚拟内存到物理内存的转化机制。

在Linux中，是通过三级页表来实现的，顶级页表是页全局目录——PGD，包含了一个pgd_t的数组；而二级页表则是中间页目录——PMD，是一个pmd_t数组；最后一级则是页表项指向物理内存的页表。

为了提高效率，还引入了一个TLB的高速缓存器，在查询物理地址时首先在TLB中查询，找不到时采取内存中查找页表。

发表于

GO入门学习

why

  • 语法简单；
  • 性能好；

常用类型

主要讲三种类型：

slice

go里面有数组类型。但开发过程中使用比较少。因为其元素类型确定，长度不可变，并且传递参数时是值拷贝；

slice是对底层数组的一段内容的引用：

1
2
data := [...]int{0,1,2,3,4,5,6}
slice := data[1:4:5] //[low:high:max]

避免在两个变量中修改同一个底层数组；可以这样修改：

1
2
3
4
v2 := make([]int, 6)
copy(v2, v1[0:6])
v3 := make([]int, 3)
copy(v3, v1[2:5])

channel

1
ch := make(chan int, 10)

创造一个长度为10，元素类型为int的管道；

  • 读 v := <- ch
  • 写 ch <- v
  • 关闭 close(ch)

目的是保证协程之间交换数据时，并发安全；

  • 长度为0的channel为不带buffer的channel
1
ch := make(chan int)

同时读写的时候，读会在写之前发生。也不会发生额外的数据拷贝。

  • 长度不为0的

写会在读之前发生；

interface

定义一个抽象的方法：

1
2
3
type Gun interface{
    Shoot()
}
  • 作用：解耦，抽象

并发

通过通信来共享数据，而不是通过共享数据来通信。

context

这是一个接口，内部有几个方法。context是在多个协程之间传递，如何保证数据安全。

web服务端模型

接受一个请求，创建一个新的协程用于读写该连接上的数据，但这种方式在请求处理阻塞的情况下，容易引发协程爆炸。

性能分析

go提供了一些性能分析的工具

profile

  • cpu分析：每隔一段时间，记录当前正在运行的协程的栈，出现频率比较高的函数就是占用CPU比较多的；
  • mem分析：分析堆上申请内存的情况；

一般都是通过采样实现。

高效的go代码

  • 减少对象创建，减少内存分配；
  • sync.Pool
  • sync/atomic

发表于

虚拟文件系统

虚拟文件系统为用户空间提供了文件和不同文件系统相关的通用接口。

通用文件系统接口

VFS使得用户可以直接使用诸如open()，read()和write()的系统调用接口，而不需要考虑具体的文件系统和物理介质。它把不同的文件系统抽象后采用统一的方式。

文件系统抽象层

由于内核在底层的文件系统接口之上建立了一个抽象层，底层文件系统通过实现VFS期望的抽象接口和数据接口，这样用户空间就可以调用统一的系统调用。

以write()为例，这个系统调用会被一个sys_write()进行处理，sys_write会找到文件描述符fd对应的真实文件系统调用该文件系统的写方法。

Unix文件系统

Unix使用了四种和文件系统相关的抽象概念：文件、目录项、索引节点和挂载点。

这是一种分层存储结构的结构。在unix中，文件系统挂载在一个特定的挂载点，相当于是一个命名空间，所有已安装的文件系统都作为根文件系统树的树叶出现在系统上。

文件通过目录组织起来，但VFS把目录也看做一种文件。Unix会把文件的相关信息诸如权限，创建时间，创建者这些元数据和文件区分对待，这些元数据存储在inode结点中，这是一个单独的数据结构。

文件的元数据和文件系统的控制信息息息相关，文件系统的控制信息存储在超级块，这样一个数据结构上。

VFS对象及其数据结构

VFS主要有四种对象类型：

  • 超级块对象，一个具体的已安装文件系统；
  • 索引节点对象，一个具体的文件；
  • 目录项对象，代表一个目录项，是路径的一个组成成分；
  • 文件对象，由进程打开的文件（注意目录也是一种文件）

超级块对象

每个文件系统都必须要实现超级块对象，用来存储特定文件系统的信息。超级块对象由super_block结构体表示。

索引结点对象

索引节点对象包含了内核在操作文件时所需要的全部信息，如果一个文件系统没有索引结点，这些文件系统会将文件描述的信息作为文件的一部分存放。无论如何，索引结点信息必须要创建。

索引结点对象由结构体inode表示

目录项对象

考虑这一个路径/bin/vi，那么/，bin和vi都属于目录项对象，前两个是目录，后一个是普通文件。由于路径中每个部分都是目录项对象，为了路径查找方便，就引入了目录项对象。目录项对象由结构体dentry表示。目录项对象没有对应的磁盘数据结构，因为目录项对象不是保存在物理硬盘中的。

目录项状态

目录项对象有三种状态：被使用、未被使用和负状态。

一个被使用的目录项对应一个有效的索引结点，并且该对象存在使用者；一个未被使用的目录项对应一个有效的索引结点，但未被使用；而负状态的目录项则没有对应的有效索引点，只是目录项还存在。

目录项缓存

由于VFS层遍历路径并解析其成dentry对象非常耗时，因此可以使用目录项缓存：

  • 被使用的目录项链表
  • 最近被使用的双向链表；
  • 散列表用来快速将给定路径解析成目录项对象；

这样VFS会现在缓存中查找路径，如果找不到了，就必须要自己解析路径，找到dentry对象并将其假如到dcache中。

文件对象

文件对象表示的是进程已经打开的文件在内存中的表示，涉及到诸如访问模式，位偏移等信息。一个文件对应的文件对象不是唯一的，但对应的目录项和索引结点是唯一的。

文件对象由结构体file表示。

文件操作由结构体file_operations表示，内定义了大量的函数指针。

和进程相关的数据结构

有三个结构体将VFS和系统的进程紧密地联系在一起：file_struct, fs_struct和namespace。

file_struct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct files_struct {

    atomic_t count; /* 共享该表的进程数 */

    rwlock_t file_lock; /* 保护以下的所有域,以免在tsk->alloc_lock中的嵌套*/

    int max_fds; /*当前文件对象的最大数*/

    int max_fdset; /*当前文件描述符的最大数*/

    int next_fd; ／*已分配的文件描述符加1*/

    struct file ** fd; /* 指向文件对象指针数组的指针 */

    fd_set *close_on_exec; /*指向执行exec( )时需要关闭的文件描述符*/

    fd_set *open_fds; /*指向打开文件描述符的指针*/

    fd_set close_on_exec_init;/* 执行exec( )时需要关闭的文件描述符的初 值集合*/

    fd_set open_fds_init; /*文件描述符的初值集合*/

    struct file * fd_array[32];/* 文件对象指针的初始化数组*/

};

进程描述符的files域指向该结构体，包含了所有与单个进程相关的文件信息。

fs_struct

1
2
3
4
5
6
7
8
struct fs_struct{
	int users; //用户数目
    rwlock_t lock //锁
    int umask; //掩码
    int in_exec; //正在执行的文件
    struct path root; //根目录路径
    struct path pws; //当前工作目录的路径
};

该结构体包含了进程与文件系统的相关信息，由fs域指向的；

namespace结构体

1
2
3
4
5
6
7
struct mmt_namespace {
  	atomic_t count; //结构体的使用计数
    struct vfsmount *root; //根目录的安装点对象
    struct list_head list; //安装点链表
    wait_queue_head_t poll; //轮询的等待队列
    int event; //事件计数
};

该结构体使得进程在系统中看到唯一的安装文件系统，由进程描述符的mmt_namespace域指向。

发表于

内存管理

内核的内存分配是比较复杂的，内核是不能休眠，另外内核也不好处理内存分配错误。

页

内核使用页作为内存管理的基本单位，这是因为内存管理单元（MMU，管理内存并把虚拟地址转换为物理地址的硬件设备）通常以页作为单位进行处理。大多数32位体系结构支持4kb的页，而64位体系结构则支持8kb的页。

内核用以下结构表示物理页：

1
2
3
4
5
6
7
8
9
10
11
//部分域
struct page{
    unsigned long flags; //存放页的状态（脏页，锁定内存的页面）
    atomic_t _count; //引用计数，没有引用时为-1
    atomic_t _mapcount;
    unsigned long private; //作为私有数据
    struct address_space *mapping; //由页缓存使用
    pgofff_t index;
    struct list_head lru;
    void *virtual; //页的虚拟地址
};

区

由于硬件的显示，位于不同物理地址的页可能不能执行一些特定的任务，内核需要把页分为不同的区进行管理。linux主要使用了四种区；

  • ZONE_DMA——这里的页可以被特定硬件进行DMA操作（直接访问）
  • ZONE_DNA32——与上面的类似，但只能被32位设备访问
  • ZONE_NORMAL——正常映射的页
  • ZONE_HIGNEM——这个区为“高端内存”所在区域，不能永久映射内核地址空间

LINUX把系统的页分为不同区，形成了不同的内存池。但不是说取页就只能从特定的区域里取。例如有一些普通的内存既可以从ZONE_DMA分配，也可以从ZONE_NORMAL。

获得页

内核提供了一种请求内存的底层，有那么几种接口：

1
struct page * alloc_pages(gfp_t gfp_mask, unsigned int order);//分配2^order个连续的物理页面，指针指向第一个page结构体

也可以获得填充为0的页，避免随机产生了垃圾信息或者敏感信息，保证安全：

1
unsigned long get_zeroed_page(unsigned int gfp_mask);

释放页面，释放页需要谨慎，因为传递了错误的struct page或者地址会导致系统，因为内核是完全相信自己的：

1
2
void free_pages(unsigned long addr, unsigned int order);
void free_page(unsigned long addr);

kmalloc()

kmalloc()函数与用户控件malloc()类似，都是以字节为单位进行分配，只是多了一个flags参数。

1
2
#include <linux/slab.h>
void *kmalloc(size_t size, gfp_t flags);

在返回指针之后，需要检查返回的是不是NULL，如果是，需要处理该错误。

gfp_mask标志

这些分配器标志可以分为三类：行为修饰符、区修饰符以及类型

行为修饰符

常见的行为修饰符，比如__GFP_WAIT（分配器可以睡眠），__GFP_HIGH（分配器可以访问紧急时间缓冲池），还有一些其它的修饰符。

区修饰符

区修饰符则是表示内存区应当从何处分配：

  • __GFA_DMA：从ZONE_DMA分配；
  • __GFA_DMA32：从ZONE_DMA32分配；
  • __GFA_HIGNMEN：从ZONE_HIGNMEM或ZONE_NORMAL分配；

类型标识

类型标识更像是结合上面两种修饰符来完成特定类型的处理。

比如用于中断程序，不能睡眠时：GFP_ATOMIC；分配让分配器睡眠，交换、一些页到硬盘，可以用GFP_KERNEL。

kfree()

释放由kmalloc()分配的内存块，kfree(NULL)是安全的。

vmalloc()

vmalloc类似kmalloc，只不过kmalloc分配的是物理地址连续的内存，而vmalloc分配的是虚拟地址连续的内存。

虽然一般只有硬件设备才需要物理地址连续的内存，但内核多数也是使用kmalloc进行分配，基于性能的考虑，vmalloc获得的页必须要逐个映射到虚拟地址，这会导致大量TLB抖动。当然，为了获取大内存，一般使用vmalloc

slab层

为了避免频繁地分配和回收，linux内核提供了slab分配器，作为通用数据结构缓存层。

slab层的设计

slab层把不同的对象划分为不同的高速缓存组，因此可能一个高速缓存组存放着进程描述符，另一个高速缓存存放着索引结点。

一般来说，每个高速缓存由若干个slab组成，而slab可能仅仅由一个页面组成，因此每个slab都包含一些对象成员。对于slab来说，只有三种状态：满、部分满或者空。在分配时，先从部分满的分配，再考虑空的slab，最后再考虑创建一个slab。

每个高速缓存都使用kmem_cache结构表示，其中有三个链表：slabs_full，slabs_partial和slabs_empty。链表中含有以下的slab结构：

1
2
3
4
5
6
7
struct slab {
  	struct list_head list;
    unsigned long colouroff; //slab着色偏移量
    void *s_mem; //slab中第一个对象
    unsigned int inuse; //slab中已分配的对象数
    kmem_bufctl_t free; //第一个空闲对象
};

slab分配器可以创建新的slab，这是通过函数__get_free_pages()实现的，分配的页大小为2的幂次方。

slab分配器的接口

一个新的高速缓存通过函数kmem_cache_create()创建。需要指定高速缓存中每个元素的大小和第一个对象的偏移以保证对齐。

在栈上的静态分配

每个进程的内核栈大小依赖于体系结构，用户空间能够负担起非常大的栈，并且栈可以动态正增长。

单页内核栈

在2.6系列的内核早期，可以设置一个单页内核栈，即进程的内核栈只有一页大小。一方面可以减少内存消耗，另一方面可以避免因为内存碎片的增多，难以寻找未分配的连续的页。

在栈上光明正大的工作

在栈上进行大量的静态分配是很危险的，因为会发送栈溢出，导致邻堆末端的东西被覆盖。因此尽量使用动态分配，让函数所有的局部变量所占空间之和不超过几百字节。

高端内存的映射

高端内存，就是不会永久映射到内核地址空间上的内存，在x86体系上，所有高于896MB的物理内存多是高端内存。

永久映射

要映射一个给定的page结构到内核地址空间：

1
void *kmap(struct page* page);

这个函数在高端内存或者地段内存中都能使用

临时映射

临时映射（原子映射）是为了创建一个映射而当前上下文又不能睡眠时提供的，内核可以原子地把高端内存中的一个页映射到某个保留的映射中。

1
void *kmap_atomic(struct page *page, enum km_type type);

分配函数的选择

上面我们讲了多种分配函数，但如何选择呢？

如果内核需要连续的物理内存，应该使用kmalloc；

如果需要连续的虚拟内存，应该使用vmalloc，但性能相对于kmalloc会低一点；

对于高端内存，可以使用alloc_pages，返回一个struct page的结构指针；如果要得到真正的指针，应该使用kmap()，将高端内存映射到内核逻辑地址；

如果要频繁创建和撤销大的数据结构，slab高速缓存是一种更好的选择，slab层通过维持一个对象高速缓存，避免频繁地分配和释放内存，只需要根据需要从缓存中得到对象就可以了。

发表于

内核同步方法

原子操作

原子操作的意义在于要么就完整地执行所有的指令，要么就都不执行。在内核中提供了两组原子操作的接口——原子整数和原子位。

原子整数操作

原子整数操作提供了一种新的数据类型，以避免原子操作函数与非原子操作函数使用相同的函数，同时也能屏蔽不同体系结构之间的差异：

1
2
3
typedef struct {
    volatile int counter;
} atomic_t;

在<asm/atomic.h>中提供了一系列原子整数操作的接口：

1
2
3
4
5
6
atomic_t v;
atomic_t u = ATOMIC_INIT(0);

atomic_set(&v, 4); //v=4
atomic_add(2, &v); //v = v+4
atomic_inc(&v); //v = v+1

原子整数操作最常见的应用就是计数器，例如可以在c++的智能指针中增加原子整数作为计数器。能用原子操作就尽量不用锁机制，增加效率。

64位原子操作

随着64位系统的发展，内核开发者也引入了64位的atomic64_t。

1
2
3
typedef struct {
    volatile long counter;
} atomic64_t;

原子位操作

与原子整数操作不同，原子位操作是在普通的内存地址上进行操作，因此原子位操作没有特定的类型，针对的只是普通指针类型。

1
2
3
unsigned long word = 0;
set_bit(0, &word);//设置第0位
set_bit(1, &word);//设置第1位

自旋锁

临界区的情况可能非常复杂，不能像上面那样只是简单声明原子变量就可以保证同步，因此就引入更为复杂的同步方法——锁。

Linux内核中最常见的锁是自旋锁（spin lock）——这种锁最多只能被一个可执行线程持有。一个可争用的自旋锁会使得请求线程busy wait，不断消耗处理器的时间。当然有方法可以让线程先行睡眠，待锁可用时再唤醒。但考虑到上下文切换的消耗，如果持有锁的时间比较短，自旋锁是一个比较好的选择。

如果持有自旋锁的时间小于两次上下文切换，那么可以选用自旋锁。

自旋锁方法

自旋锁的实现是和体系结构相关的，代码往往通过汇编来实现。基本的使用形式如下：

1
2
3
4
DEFINE_SPINLOCK(mr_lock);
spin_lock(&mr_lock);
/*临界区*/
spin_unlock(&my_lock);

自旋锁不可递归，如果一个线程试图去获取一个自己已经拥有的自旋锁，就会陷入死锁

其它针对自旋锁的操作

可以使用spin_lock_init()来初始化动态创建的自旋锁（此时返回一个指向spinlock_t类型的指针）。spin_try_lock()会试图获取某个特定的自旋锁，而spin_is_locked()方法则只是判断特定锁是否被占用。

自旋锁和下半部

与下半部配合使用时，我们在获取锁的时候需要禁止所有下半部的执行，因为下半部可以抢占进程上下文中的代码，此时可以使用方法——spin_lock_bh()。

读－写自旋锁

由于锁的用途可以明确分为读取和写入两个场景，因此提供了读－写自旋锁进行保护。一个或者多个任务可以并发地拥有读者锁，但写者锁只能被一个写任务拥有。

1
2
3
4
5
6
7
8
9
DEFINE_SPINLOCK(mr_rwlock);
read_lock(&mr_rwlock);
/*临界区，只读*/
read_unlock(&mr_rwlock);

/*写者分支*/
write_lock(&mr_rwlock);
/*临界区*/
write_unlock(&mr_rwlock);

注意这样的一种死锁情况，写者锁不断自旋，等待读者锁释放

1
2
read_lock(&mr_lock);
write_lock(&mr_lock);

信号量

linux中的信号量实际上是一种睡眠锁，则任务试图获得一个不可用的信号量时，就会进入一个等待队列，然后处于休眠状态，此时处理器就可以释放。与自旋锁不同，信号量在等待锁时会睡眠，所以信号量适用于锁被长时间占有的情况。如果占有锁时间较短，那么维护队列，切换上下文的开销就不值得了。另外，在占有信号量时，不能同时占用自旋锁，因为拥有自旋锁时不允许睡眠。

计数信号量和二值信号量

信号量可以允许持有计数器，如果一个时刻只允许一个锁持有者，那就是二值信号量，如果计数可以大于1，那就是计数信号量。

由于引入了计数机制，因此信号量支持两个原子操作P()和V()。一个将信号量计数减一来请求一个信号量，另一个则是讲信号加一来释放信号量。

创建和初始化信号量

1
2
3
4
struct semaphore name;
sema_init(&name, count);
//动态创建信号量
init_MUTEX(sem);

使用信号量

函数down_interruptible()会试图获取指定信号量，如果信号量不可用，它会将进程置成TASK_INTERRUPTLE状态，进入睡眠。

读－写信号量

读写信号量与读写自旋锁差别不大，但是读写信号量相比读写自旋锁多一种特有的操作——downgrade_write()，这个函数可以动态地将获取的写锁转换为读锁。

互斥体

互斥体(mutex)是指任何可以睡眠的强制互斥锁，就像计数是1的信号量。互斥体在内核中对应的数据结构为mutex：

1
2
3
4
5
6
7
//静态创建
DEFINE_MUTEX(name);
//动态
mutex_init(&mutex);
//加锁、解锁
mutex_lock(&mutex);
mutex_unlock(&mutex);

相比信号量，mutex的限制更多：

  • 只有一个任务可以拥有mutex；
  • 给mutex上锁的任务必须负责解锁；
  • 不能递归地上锁和解锁；
  • mutex不能在中断或者下半部使用；
  • mutex只能通过官方API管理；

尽量使用mutex，除非mutex的限制影响了你；除非是低开销的加锁、或者短期锁定，又或者需要在中断上下文加锁，某人都用mutex；

顺序锁

在2.6版本内核中引进了一种新型锁，顺序锁(seq)，通过一个序列计数器，在有数据写入的时候，就会得到一个锁，并且序列值增加。在读取数据之前和之后，会比较序列号，相同才证明数据没有被修改。

1
2
3
4
unsigned long seq;
do{
    seq = read_seqbegin(&mr_seq_lock);
}while (read_seqretry(&mr_seq_lock, seq));

seq锁对于写者更有利，如果有写者，那么读数据就会不断进入循环。

禁止抢占

由于内核是抢占性的，内核中的进程在任何时刻都可能停下了，另一个进程运行，这就可能出现临界区有两个进程。自旋锁可以避免这个问题，但某些情况不需要自旋锁，可以通过禁止抢占来实现：

1
2
3
preempt_disable();
/*抢占被禁止...*/
preempt_enable();

顺序和屏障

当处理多处理器之间的同步问题时，我们可能需要在代码中指定读内存和写内存的指令，这种确保顺序的指令就叫屏障(barriers)。

  • rmb()提供了读内存屏障，它确保跨越rmb()的载入动作不会发送重排；
  • wmb()提供的是写内存屏障；