EffectiveGo学习笔记

格式化

在go中，为了避免各种格式化问题的争论而浪费时间，我可以用gofmt将go程序进行统一的格式化，使得所有人遵循标准风格。

使用命令：

1

gofmt -w program.go

该命令会将源代码格式化后再去覆盖原来的内容。

All GO code in the standard packages has been formatted with gofmt

注释

Go语言支持块注释**/* */和行注释/ /**。在golang中，因为godoc的提供，我们可以通过两种方式来查看文档。godoc既是一个程序，也是一个web服务器。

考虑这样一段代码：

1
2
3
4
5
6
7
8
9
10
11
12

/*
提供常用库，输出一个vim-go
*/
package main

import "fmt"

//只是一个main函数
//不知道说什么了
func main() {
	fmt.Println("vim-go")
}

go doc的使用可以接收包名作为参数，也可以不输入任何参数，那么显示觉得就是当前目录下的文档。

1
2

> go doc
> 提供常用库，输出一个vim-go

当然也可以打开web服务器去访问：

1

godoc -http=:6060

打开之后是官网的一个拷贝，但包的文档http://127.0.0.1:6060/pkg/会更丰富，因为它是基于电脑上GOROOT和GOPATH路径下的所有包生成的文档。

命名

命名在任何语言中都是非常重要的

包名

1

import "bytes"

一般来说，包名应该以小写的单个单词为命名；另一个约定俗成的是包名应为其源码目录的基本名称。

由于包名作为一个访问器，使得导出名称可以避免冲突。比如bufio.Reader和io.Reader就不会发生冲突。

接口名

按照约定，只包含一个方法的接口应该以该方法的名称加上-er后缀来命名，如Reader、Writer。

分号

和C一天，go的正式语法使用分号来结束语句，但这些分号不在源码中出现，而是此法解析器会在每行最后一个标记为标识符时，在后面加上分号。

另外，分号在闭合的大括号之前可以直接省略，所以尽量不要将大括号换行，以下是错误做法：

1
2
3
4

if i < f()
{
    g()
}

如果一行内写多个语句，也应该用分号隔开。

控制结构

Golang有几种控制结构，for，if，switch和select，没有圆括号，而且主体必须使用大括号。

if

一个简单的if语句：

1
2
3

if x > 0 {
    return y
}

另外，if可以接收初始化语句，设置局部变量：

1
2
3
4

if err := file.Chmod(0664); err != nil {
    log.Print(err)
    return err
}

重新声明与再次赋值

比如这样的例程：

1
2
3

f, err := os.Open(name)
//xxxxxx
d, err := f.Stat()

在满足下列条件时，已被声明的变量可以出现:=声明中：

• 本次声明与已声明的v处于同一作用域；（若v在外层作用域已经声明过，则此次声明会创建新的变量）
• 在初始化中与其类型相应的值才能赋予v，并且此次声明中至少另有一个变量是新声明的

for

golang的for循环有三种：

1
2
3
4
5

for init; condition; post { }

for condition { }

for { }

如果要遍历数组、切片、字符串或者映射，抑或是从channel中读取信息，可以使用range子句：

1
2
3

for key, value := range oldMap {
    
}

switch

golang的switch语句，其表达式无需为常量或整数。

1
2
3
4
5
6
7
8
9
10
11

func unhex(c byte) byte {
    switch {
    case '0' <= c && c <= '9':
        return c - '0'
    case 'a' <= c && c <= 'f':
        return c - 'a' + 10
    case 'A' <= c && c <= 'F':
        return c - 'A' + 10
    }
    return 0
}

这样就可以将一系列的if-else转为switch-case。

另外，switch的case可以使用逗号分隔来列举相同的处理条件：

1
2
3
4
5
6
7

func shouldEscape(c byte) bool {
    switch c {
    case ' ', '?', '&', '=', '#', '+', '%':
        return true
    }
    return false
}

跟C一样，我们往往会希望用break打破循环，在golang中，如果我们希望打破外层的循环，可以给break增加一个标签：

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

Loop:
	for n := 0; n < len(src); n += size {
		switch {
		case src[n] < sizeOne:
			if validateOnly {
				break
			}
			size = 1
			update(src[n])

		case src[n] < sizeTwo:
			if n+1 >= len(src) {
				err = errShortInput
				break Loop
			}
			if validateOnly {
				break
			}
			size = 2
			update(src[n] + src[n+1]<<shift)
		}
	}

命名的结果参数

Go函数的返回可以给定一个名字，在命名后，一旦函数开始执行，它们就会被初始化为与其类型响应的零值；若该函数执行了一条不带参数的return语句，该结果形参的当前值就会被返回。

1
2
3
4
5
6
7
8
9

func ReadFull(r Reader, buf []byte) (n int, err error) {
    for len(buf) > 0 && err == nil {
        var nr int
        nr, err = r.Read(buf)
        n += nr
        buf = buf[nr:]
    }
    return
}

defer

Go的defer语句可以预设一个函数调用，让它在执行defer的函数返回之前立即执行，这可以用来执行一些释放资源的函数：

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

// Contents returns the file's contents as a string.
func Contents(filename string) (string, error) {
    f, err := os.Open(filename)
    if err != nil {
        return "", err
    }
    defer f.Close()  // f.Close will run when we're finished.

    var result []byte
    buf := make([]byte, 100)
    for {
        n, err := f.Read(buf[0:])
        result = append(result, buf[0:n]...) // append is discussed later.
        if err != nil {
            if err == io.EOF {
                break
            }
            return "", err  // f will be closed if we return here.
        }
    }
    return string(result), nil // f will be closed if we return here.
}

被defer的函数调用按照LIFO的顺序执行，比如这样的代码：

1
2
3
4

for i := 0; i < 5; i++ {
    defer fmt.Printf("%d ", i)
}
//4 3 2 1 0

data

golang提供了两种分配方法，即内建函数make和new，它们做的事情不同，但可能引起混淆。

new分配

这个内建函数会分配内存，并且将内存置为0，但不会初始化内存。在分配完已置为0的内存之后，会返回它的地址，比如new(T)会返回*T，即一个指向新分配的，类型为T的零值。

因此使用者只需要用new就可以创建一个新的对象，例如：零值bytes.Buffer就是已准备就绪的缓冲区，而零值的sync.Mutex就是已解锁的互斥锁。

另外这种零值属性是具有传递性的，考虑这样的structure：

1
2
3
4

type SyncedBuffer struct {
    lock    sync.Mutex
    buffer  bytes.Buffer
}

那么在后续的声明时，对于SyncedBuffer类型，只要声明分配好内存就可以直接使用：

1
2

p := new(SyncedBuffer)  // type *SyncedBuffer
var v SyncedBuffer      // type  SyncedBuffer

构造函数与复合字面量

在很多情况下，我们声明一个对象不单单是要零值，还希望初始化成员，但总不能逐个赋值这么丑陋的做法嘛：

1
2
3
4
5
6
7
8
9
10
11

func NewFile(fd int, name string) *File {
    if fd < 0 {
        return nil
    }
    f := new(File)
    f.fd = fd
    f.name = name
    f.dirinfo = nil
    f.nepipe = 0
    return f
}

而golang的做法是这样的：

1
2
3
4
5
6
7

func NewFile(fd int, name string) *File {
    if fd < 0 {
        return nil
    }
    //return &File{fd, name, nil, 0}
    return &File{fd: fd, name: name} //此时其它字段默认为零值
}

与C不同的是，golang返回一个局部变量地址是有效的，因此可以直接合并上面的语句。当然也可以以key：value的方式标出长远，如上。

make分配

内建函数make(T, args) 的目的不同于 new(T)。它只用于创建切片、映射和信道，并返回类型为 T（而非 *T）的一个已初始化 （而非置零）的值。例如：

1

make([]int, 10, 100) //分配一个100个int的数组空间，接着创建一个长度为10，容量为100并且指向该数组前10个元素的切片结构

若要返回指针，请用new分配内存

slice

切片是对数组的封装，保存了对底层数组的引用。若某个函数将一个切片作为参数传入时，函数对切片的修改对调用者而言是可见的。

1

func (file *File) Read(buf []byte) (n int, err error)

若要从更大的缓冲区 b 中读取前 32 个字节，只需对其进行切片即可。

1

n, err := f.Read(buf[0:32])

map

map的key可以是任何相等性操作符支持的类型， 如整数、浮点数、复数、字符串、指针、接口，结构以及数组，但不能是切片。

若试图通过map中不存在的键来取值，就会返回与该映射中项的类型对应的零值。

但这种设计我们不知道到底是不是因为不存在该项而得到零值，因此可以使用这种做法来检查：

1
2
3

var seconds int
var ok bool
seconds, ok = timeZone[tz]

初始化

常量

Golang中的常量在编译时创建，而且只能是数字，字符，字符串或者布尔量。

init函数

init函数会在每个包完成初始化后自动执行，并且执行优先级会比main函数高，一般用来：

• 对变量进行初始化；
• 检查或者修复程序的状态；
• 注册；
• 进行一次计算；

接口

golang的接口为指定对象的行为提供了一种途径，如果某个类型可以完成这个，那么它就可以被用在这里。通过实现 String 方法，我们可以自定义打印函数，而通过 Write 方法，Fprintf 则能对任何对象产生输出。

例如一个实现了 sort.Interface 接口的集合就可通过 sort 包中的例程进行排序。该接口包括 Len()、Less(i, j int) bool 以及 Swap(i, j int)。

1
2
3
4
5
6
7
8
9
10
11
12
13

type Sequence []int

// Methods required by sort.Interface.
// sort.Interface 所需的方法。
func (s Sequence) Len() int {
    return len(s)
}
func (s Sequence) Less(i, j int) bool {
    return s[i] < s[j]
}
func (s Sequence) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

接口转换和类型断言

类型选择是类型转换的一种形式：它接受一个接口，通过switch判断选择读经的case，并在某种意义上将其转换为该种类型。以下代码为 fmt.Printf 通过类型选择将值转换为字符串的简化版。

1
2
3
4
5
6
7
8
9
10
11

type Stringer interface {
    String() string
}

var value interface{} // Value provided by caller.
switch str := value.(type) {
case string:
    return str
case Stringer:
    return str.String()
}

一个接口类型的变量可能包含任何类型的值，因此我们需要用类型断言来检查其动态类型，即运行时在变量中存储的值的实际类型。例如我们可以测试某个时刻接口varI是否包含类型T的值：

1
2
3
4
5

if v, ok := varI.(T); ok {  // checked type assertion
    Process(v)
    return
}
// varI is not of type T

如果转换合法，那么v就是varI转换到类型T的值。

空白标识符

空白标识符可被赋予为任何类型的任何值，它表示只写的值，作为占位符。

另外，空白标识符能使得那些未使用的导入和变量不受影响，能顺利通过编译，比如这样的程序，由于有两个未使用的导入和一个未使用的变量fd，因此不能编译。

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

package main

import (
    "fmt"
    "io"
    "log"
    "os"
)

func main() {
    fd, err := os.Open("test.go")
    if err != nil {
        log.Fatal(err)
    }
    // TODO: use fd.
}

通过引入空白标识符，则可以顺利通过编译：

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

package main

import (
    "fmt"
    "io"
    "log"
    "os"
)

var _ = fmt.Printf // For debugging; delete when done. // 用于调试，结束时删除。
var _ io.Reader    // For debugging; delete when done. // 用于调试，结束时删除。

func main() {
    fd, err := os.Open("test.go")
    if err != nil {
        log.Fatal(err)
    }
    // TODO: use fd.
    _ = fd
}

还有一种用法，是为了使用其副作用而引入包，比如在 net/http/pprof 包的 init 函数中记录了 HTTP 处理程序的调试信息。它有个可导出的 API， 但大部分客户端只需要该处理程序的记录和通过 Web 页面访问数据。那么可以这样使用：

1

import _ "net/http/pprof"

错误

由于golang的多值返回，我们可以很轻易地返回各种类型的错误提示，按照约定，错误的类型通常为 error，这是一个内建的简单接口。

1
2
3

type error interface {
    Error() string
}

Panic

内建的panic函数，会产生一个运行时错误并终止程序，还会在程序终止时打印。比如这样：

1
2
3
4
5
6
7
8
9
10
11
12

func CubeRoot(x float64) float64 {
    z := x/3   // Arbitrary initial value
    for i := 0; i < 1e6; i++ {
        prevz := z
        z -= (z*z*z-x) / (3*z*z)
        if veryClose(z, prevz) {
            return z
        }
    }
    // A million iterations has not converged; something is wrong.
    panic(fmt.Sprintf("CubeRoot(%g) did not converge", x))
}

由于panic被调用后，程序会终止当前函数的执行，并开始回溯goroutine的栈，当到达栈顶时，程序就会终止。不过我们可以用内建的 recover 函数来重新取回 goroutine 的控制权限并使其恢复正常执行。

由于在回溯时只有被推迟函数中的代码在运行，因此 recover 只能在被推迟的函数中才有效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func server(workChan <-chan *Work) {
    for work := range workChan {
        go safelyDo(work)
    }
}

func safelyDo(work *Work) {
    defer func() {
        if err := recover(); err != nil {
            log.Println("work failed:", err)
        }
    }()
    do(work)
}

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

先来看两个基本的选项：

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层通过维持一个对象高速缓存，避免频繁地分配和释放内存，只需要根据需要从缓存中得到对象就可以了。