算法与数据结构资源收集

发表于 2017-08-24 | 分类于资料收集

查找

链表

如何判断链表中是否有环
补：
1、链表有环不代表头节点就在环中，应该考虑只有后半部分出现环的情况。对于后者，使用单指针进行遍历以判断是否有环会导致死循环，因为不知道环的入口点，应该使用两个指针。
2、计算环的长度应该由第一次相遇时开始，第二次相遇时结束。不能从一开始就计算，因为如果进入环之前的长度远大于环长度的话，计算出来的长度是环长度的N倍。
3、计算入口点思路：分别从碰撞点、头指针开始一步一步走，相遇的那个点就是连接点。
注意点1：当slow入环时，fast肯定在其前面或相遇，而fast每次1步的速度接近slow，所以在slow走完一圈前，fast肯定能碰上slow。即：首次相遇时，slow还没走完链表。
注意点2：假设链表长度L，头节点到入口点长度A，入口点到相遇点长度B，环长度R，相遇之时slow走了S步。
相遇之时，fast走了2S步，且fast走的2S步等于slow走的S步加上fast绕的N次环，即2S=S+N*R，即S=N*R，slow走的S步等于环长度Rfast绕的N次环。
相遇之时，slow走的S步=头节点到入口点长度A+入口点到相遇点长度B。头节点到入口点长度A+入口点到相遇点长度B=`环长度Rfast绕的N次环=(N-1)R+R=(N-1)R+链表长度L-头节点到入口点长度A，头节点到入口点长度A=(N-1)*R+链表长度L-头节点到入口点长度A-入口点到相遇点长度B。这说明从头节点到入口点长度等于从相遇点到入口点长度加上N-1次环长度`。
4、判断两个链表（不带环）是否相交：将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。

排列/组合

n*m矩阵求长方形
 字符串的全排列和组合算法
 排列组合中的不相邻问题
补：
关注其中的容斥原理和集合算法。

设计模式

C++实现线程安全的单例模式
 设计模式六大原则
补：
从类的角度出发：单一职责原则、最少知道原则、里氏替换原则。
从接口的角度出发：依赖倒置原则、接口隔离原则。
最终达到：开闭原则，即用抽象构建框架，用实现扩展细节。因为抽象灵活性好，适应性广，只要抽象的合理，可以基本保持软件架构的稳定。而软件中易变的细节，我们用从抽象派生的实现类来进行扩展，当软件需要发生变化时，我们只需要根据需求重新派生一个实现类来扩展就可以了。

图

判断无向图和有向图是否有回路

树

补：
二叉树二度节点和叶子节点的数量关系：
二叉树节点的度等于子树数目，只能是0、1、2。公式1：总节点数=叶子结点数+1度节点数+2度节点数。公式2：总度数=总节点数-1=1度节点数 + 2度节点数*2。可推出叶子节点个数=2度节点+1。
二叉树前序、中序、后序遍历非递归写法的透彻解析
补：
已知二叉树前序遍历和后序遍历如何求中序遍历？
TLR的第一个和LRT的最后一个一定是树根
TLR的第二个不是左子树的根就是右子树的根
如果TLR第二个与LRT的倒数第二个相同
则他是根的右子树
否则是根的左子树
将上面的方法递归
一步一图一代码，一定要让你真正彻底明白红黑树
 从B 树、B+ 树、B* 树谈到R 树
补：
一棵含有N个总关键字数的m阶的B树的最大高度是log_ceil(m/2)[(N+1)/2] + 1。(以ceil(m/2)为底)
m阶B树中每个结点含有子树满足：[ceil(m/2),m]，含有关键字满足[ceil(m/2)-1,m-1]。
红黑树-算法导论
补：
一棵有n个内结点的红黑树的高度至少为log(n)，至多为2lg(n+1)。
关于STL使用红黑树而不是AVL树的几点考虑:

1
2
3

1. 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。  
2. 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。  
3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。

动态规划

最长公共子序列与最长公共子串
 01背包问题和完全背包问题

数学算法

求最小公倍数和最大公约数三种算法
 求质数的几种算法
 STL 快速计算x的n次幂 power()的实现

位运算

x&(x-1):将x用二进制表示时最右边的一个1变为0

c/c++资源收集

发表于 2017-08-24 | 分类于资料收集

参考手册

ClassFoo / C++ 参考手册

基本概念

陈皓 - 深入理解C语言
 陈皓 - 64位平台C/C++开发注意事项
 C和C++中struct使用的区别
 new 和 malloc 的区别
补：
运算符/库函数、初始化、构造/析构函数、自动计算大小、返回指定类型指针。
C 中 static 的常见作用
 sizeof与strlen的区别与联系
 const static与static const的使用
 const常量与define宏定义的区别
 const的实现原理
补：
在C里，const常量总是会分配内存，位于只读数据段。
在C++中，对于基本类型的常量，编译器并不为其分配存储空间，而是放到符号表，在编译器里进行语法分析的时候，将常量表达式计算求值，并用求得的值来替换表达式，这就是C++的常量折叠。而一旦对const常量使用extern外部引用，或者&解地址等操作时，就会迫使C++编译器给这个const变量分配内存，编译器会重新在内存中创建一个它的拷贝，通过地址访问到的就是这个拷贝而非原始的符号常量；否则就是一个编译时的符号，不占用内存。
详解C中volatile关键字

指针

NULL指针、零指针、野指针
 std::auto_ptr智能指针
 C++ 智能指针详解
 函数指针 + 数组指针
 多维指针

内存布局

内存管理内幕
补：
几个基本的内存管理策略：malloc、引用计数、内存池、垃圾回收。
Glibc 内存管理
补：
关注要点：1、chunk组织方式；2、空闲chunk容器种类；3、内存分配步骤；4、内存回收步骤；5、mmap分配阈值动态调整时机；6、fast bins合并时机；7、避免glibc内存暴增方法。
长生命周期的大内存应使用mmap分配，如果使用sbrk分配，该内存块长期被占用会导致后续短生命周期内存释放后无法归还给操作系统。但是mmap效率低，mmap分配阈值动态调整正是为了使大于128K的短生命周期大内存尽量不会使用mmap分配。
C/C++内存管理详解
补：
堆和栈的区别：管理方式、空间大小、是否造成内存碎片、分配方式、分配效率、生长方式。
野指针的成因：初始化时没有设为NULL或指向合法的内存区、释放时没有设为NULL、操作时超出了变量作用域。
C/C++ 结构体字节对齐详解
 题 - c++ 类的内存布局
 陈皓 - C++ 虚函数表解析
 陈皓 - C++ 对象的内存布局
补：
1、多重虚拟继承时，子类独有的虚函数会放到第一个父类的虚函数表；g++实验证明，子类重写的其他父类的虚函数会放到第一个父类的虚函数表，但子类重写的第一个父类的虚函数不会放到其他父类的虚函数表（vc++标准可能不一样）。
2、多重继承且父类都虚拟继承同一个爷爷类时，构建顺序是【爷爷类->父类1->父类2->子类】，实例顺序是【父类1->父类2->子类->爷爷类】。
3、虚拟继承与虚函数之间没有任何绝对联系。虚函数是为了解决多态的问题，虚拟继承是为了解决重复继承中多个间接父类的问题。
4、g++实验证明，多重继承且父类都虚拟继承同一个爷爷类时，如果没有涉及虚函数，父类都有对应的虚拟表（父类实例的第一个位置存储表的地址），存储的是虚继承的内容，爷爷类没有对应的虚拟表；如果子类、父类、爷爷类都定义了对应的虚拟函数，则子类实例中父类和爷爷类都会有对应的虚拟表（虚拟表将优先存储虚拟函数内容，再存储虚继承的内容，但并不是每个虚拟表都这样，每个虚拟表如何处理虚继承的内容目前还不清晰），但“子类本身”没有虚拟表（子类独有的虚函数会放到第一个父类的虚拟表）。
多重继承和虚继承的内存布局
 父类virtual虚构函数（其他成员函数同）
补：
多继承的情况下，首先按照继承顺序调用类的构造函数，再调用子类的构造函数。
delete某个基类指针时,只看指针的声明类型的类中是否将析构函数声明为虚函数，如果是则成功按照调用构造函数的相反顺序调用析构函数（跟该类被继承的顺序没关系，且其他被继承类有无设置虚析构函数也没关系），如果不是则只调用该基类的析构函数。
delete基类指针时，始终按照调用构造函数的相反顺序调用析构函数。

数组

C/C++中的0长数组（柔性数组）
陈皓 - C语言结构体里的成员数组和指针
补：
使用0长数组而不是指针，是为了一次malloc就给一个结构体内的数据分配一个连续的内存，一次free就可以把所有的内存也给释放掉。
对于char s[0]来说，汇编代码用了lea指令，lea 0x04(%rax), %rdx。
对于char*s来说，汇编代码用了mov指令，mov 0x04(%rax), %rdx。
lea全称load effective address，是把地址放进去，而mov则是把地址里的内容放进去。访问成员数组名其实得到的是数组的相对地址，而访问成员指针其实是相对地址里的内容。

c++

C++异常机制的实现方式和开销分析
 区分浅/深拷贝操作和赋值操作
 通过初始化列表来初始化的成员变量(引用，const和没有默认构造函数的成员对象)
补：
const、引用、无默认构造函数的成员变量（调用拷贝构造函数初始化）
c++类中成员变量的初始化总结
 c++中临时变量不能作为非const的引用参数
 C++公有继承、保护继承、私有继承的区别
 友元函数
 C++继承中重载、重写、重定义的区别
补：

1 成员函数重载特征（c++类不能同时存在函数名和参数一样的静态函数和非静态函数）：
   a 相同的范围（在同一个类中） 
   b 函数名字相同
   c 参数不同 
2 重写（覆盖)是指派生类函数覆盖基类函数，特征是：
   a 不同的范围，分别位于基类和派生类中
   b 函数的名字相同
   c 参数相同
   d 基类函数必须有virtual关键字
3 重定义(隐藏)是指派生类的函数屏蔽了与其同名的基类函数，规则如下：
   a 如果派生类的函数和基类的函数同名，但是参数不同，但是基类函数没有vitual关键字，此时，基类的函数被隐藏。
   b 如果派生类的函数和基类的函数同名，但是参数不同，基类函数有vitual关键字，此时，基类的函数被隐藏。
   c 如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有vitual关键字，此时，基类的函数被隐藏。  
   d 可以在子类成员函数中通过[父类::]的方式调用被隐藏的函数，但是无法通过子类类型的子类实例调用到父类被隐藏的方法。

c++11

lambda 表达式解析
 C++11新特性学习笔记
 C++11中的右值引用

优化

Valgrind使用简介

预处理

C 语言预处理命令总结大全

函数区别

memmove 和 memcpy 的区别
补：
经实验，当dst在src后面且dst在src范围内时：
memmove和memcpy都能够正确复制，类似于实现时先复制到临时数组中；
strcpy无法确保正确复制，而且strcpy复制的个数算上了结束符（猜想strcpy的实现是先计算复制个数，算上结束符，但是没有先复制出数据）；
memccpy也无法确保正确复制，在复制过程中会覆盖原有内容，如果一直没有遇到匹配字符，将复制原先整个src的长度；如果遇到匹配字符，结束复制，匹配字符会被复制（猜想memccpy的实现是先计算复制个数，不算上结束符）。
strcat会直接走到dst末尾，然后连接上原先整个src的长度的数据（猜想strcat的实现是先计算复制个数，不算上结束符）。
标准C中字符串分割方法
 strcpy和strncpy用法和区别

STL

STL的线程安全解决方案

混合编程

C和C++混合编程

K&R Chapter 5. Pointers and Arrays

发表于 2017-08-24 | 分类于 C/C++

《5.1 Pointers and Addresses》

*ip += 1 将ip指向的内容加1，等同于 ++*ip 和 (*ip)++，其中 (*ip)++ 的括号是必须的，因为*和++都是由右往左联合。

《5.2 Pointers and Function Argument》

C使用按值传递的方式传递参数给函数。被调用函数 the called function 无法通过直接的方式改变调用函数 the calling function 的变量。

《5.3 Pointers and Arrays》

假设int a[10]和int *pa，pa = &a[O]，则pa和a的值一样。
因为数组的名字是最初的元素位置的同义词，所以pa = &a[O]可以写成pa = a。

a[i]可以写成(a+i)，**C会间接将a[i]转化为`(a+i)**。&a[i]等同于a+i。简单来讲， **array-and-index 的表达式等价于写成 a pointer and offset 的表达式**。[]优先级高于，X[ii][j]等价于((X+ii))[j]但不等价于*(X+ii)[j]`。

指针和数组名的区别：指针是变量，pa=a和pa++是合法的；数组名不是变量，a=pa和a++是不合法的。传递一个数组名给函数时，传递的是首元素的位置，对被调用函数而言，该函数参数就是一个指针，一个包含地址的变量。

int a[5]={1,2,3,4,5};int *ptr=(int *)(&a+1); 数组名就是数组0号元素的地址，a = &a[0]。&a是指向一个有5个整型元素的数组的地址，int *ptr=(int*)(&a+1) => int *ptr=(int*)(a地址 + sizeof(a));，sizeof(a) = 5*sizeof(int)。而printf("%p\n", iArry);和printf("%p\n", &iArry);输出的地址值是一致的，这说明底层实现并没有为二级指针创建临时变量什么的，而只是在计算一级指针和二级指针的方式上有所区别。

《5.4 Address Arithmetic》

指针和整数不能互换，0则是特例，指针可被赋值0，也可以和0作比较。C保证 0 永远不会是数据的合法地址，可以通过返回 0 (函数返回值为指针类型)来标识异常事件。符号常量NULL定义于stdio.h，代表一个指针的特殊值，经常用于代替0。

当两个指针指向不同的数组时，指针之间的运算或比较是未定义的。但存在一个特例：超出数组末端的第一个元素的地址可以用于指针运算，如：int array[10]; int* a = array + 10;

指针减法：指向相同数组的两个指针p和q，如果p < q，q-p+1将返回从p到q的元素个数。

《5.5 Character Pointers and Functions》

strcpy函数的实现：

array版本
/* strcpy: copy t to s; array subscript version */
void strcpy(char *s, char *t)
{
    int i;
    i = 0;
    while ((s[i] = t[i]) != '\0')
        i++;
}

pointers版本1
/* strcpy: copy t to s; pointer version 1 */
void strcpy(char *s, char *t)
{
    while ((*s = *t) != '\0') {
        s++;
        t++;
    }
}

pointers版本2
/* strcpy: copy t to s; pointer version 2 */
void strcpy(char *s, char *t)
{
    while (( *s++ = *t++) != '\0' )
        ;
}

pointers版本3
/* strcpy: copy t to s; pointer version 3 */
void strcpy(char *s, char *t)
{
    while (*s++ = *t++)
        ;
}

strcmp函数的实现：

array版本
/* strcmp: return <0 if s<t, 0 if s==t, >0 if s>t */
int strcmp(char *s, char *t)
{
    int i;
    for (i = 0; s[i] == t[i]; i++)
        if (s[i] == '\0')
            return 0;
    return s[i] - t[i];
}

pointers版本
/* strcmp: return <0 if s<t, 0 if s==t, >0 if s>t */
int strcmp(char *s, char *t)
{
    for ( ; *s == *t; s++, t++)
        if (*s == '\0' )
            return 0;
    return *s - *t;
}

练习

练习5-3：实现strcat(s,t)函数(Chapters 2)的指针版本，将字符串t复制到s的末端。

1
2
3

while(*s++); /* Get to the end of the string */
    s--;           /*get back to the end of the string.*/
while((*s++ = *t++));

练习5-4：实现strend(s,t)函数，如果字符串t出现在s的末端，返回1，否则返回0。

int strend(char *s, char *t)
{
        char *sc = s;
        char *tc = t;

        while (*s != '\0')
                s++;
        while (*t != '\0')
                t++;
        while (s > sc && t > tc && *s-- == *t--) ;
        return (t == tc && *s == *t ? 1 : 0);
}

练习5-5：实现strncpy(s,t,n)、strncat(s,t,n)、strncmp(s,t,n)函数，至多操作参数字符串的前n个字符。

char *_strncpy(char *s, const char *ct, size_t n) {
	char *p;

	p = s;
	for (; n > 0 && *ct != '\0'; --n)
		*p++ = *ct++;
	for (; n > 0; --n)
		*p++ = '\0';
	return s;
}
char *_strncat(char *s, const char *ct, size_t n) {
	char *p;

	p = s;
	while (*p != '\0')
		++p;
	for (; n > 0 && *ct != '\0'; --n)
		*p++ = *ct++;
	*p = '\0';
	return s;
}
//库函数strncmp("a", "b",0)会返回0
int _strncmp(char *s, char *t,int n)
{
    for ( ; n>0 && *s == *t; s++, t++,n--)
        if (*s == '\0' )
            return 0;
    if(n==0 ) return 0;
    return *s - *t;
}

K&R Chapter 2. Types, Operators, and Expressions

发表于 2017-08-24 | 分类于 C/C++

《2.9 Bitwise operators》

逻辑位移和算术位移

<< 是左移，>> 是右移，右操作数（right operand）必须为正数。
左移都是寄存器二进制位整体向左移动，并在右边补0。
右移的话，如果左操作数是无符号数，如unsigned int、unsigned char等，则整体向右移，并在左边补0。如果左操作数是有符号数，如int、char、short等，则整体向右移后，某些机器会在左边补上符号数（算术位移），而某些机器会在左边补上0（逻辑位移）。

在汇编指令中，SHL和SHR表示逻辑左移和逻辑右移，SAR和SAL表示算术左移和算术右移。一般的说法是：如果左操作数是有符号数，编译产生的汇编指令是算术位移指令；如果是无符号数，编译产生的汇编指令则是逻辑位移指令。而根据K&R的说法，应该是：如果左操作数是有符号数，某些机器会生成算术位移指令，而某些机器会生产逻辑位移指令；如果是无符号数，编译产生的汇编指令则是逻辑位移指令。

示例：编写函数getbits(x,p,n)，返回x从位置p开始的n bit（向右对齐）。假设最右端是位置0，n和p都是正数。getbits(x,4,3)返回三个bit，分别是位置4、3、2。

/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
    return (x >> (p+1-n)) & ~(~0 << n);
}

练习2-6：编写函数setbits(x,p,n,y)，将x中从第p位开始的n个(二进制)位设置为y中最右边n位的值，x的其余各位保持不变。
思路是：将x从第p位开始的n个位清零，x &~(~(~0<< n) << (p + 1 -n))；将y的最右边n位移到p位置，其他位清零，(y & ~(~0 <<n )) << (p + 1 - n)；两者相或。

/* setbits : set n bits of x at position p with bits of y */
unsigned setbits ( unsigned x, int  p, int n, unsigned y)
{
    return x &~(~(~0<< n) << (p + 1 -n)) | (y & ~(~0 <<n )) << (p + 1 - n)
}

练习2-7：编写函数invert(x,p,n)，将x从位置p开始的n bit取反，其他位不变。

unsigned invert(unsigned x, int p, int n)
{
    return x ^ ((~(~0<<n))<< p+1-n);
}

练习2-8：编写函数rightrot(x,n)，将x向右循环n个位置后返回。

unsigned rightrot(unsigned x, unsigned n)
{
    while (n > 0) {
        if ((x & 1) == 1)
            x = (x >> 1) | ~(~0U >> 1);
        else
            x = (x >> 1);
        n--;
    }
    return x;
}

数组与指针笔记

发表于 2017-08-24 | 分类于 C/C++

程序

#include <stdio.h>
#include <stdlib.h>

void
f(void)
{
    int a[4];
    int *b = malloc(16);
    int *c;
    int i;

    printf("1: a = %p, b = %p, c = %p\n", a, b, c);

    c = a;
    for (i = 0; i < 4; i++)
        a[i] = 100 + i;
    c[0] = 200;
    printf("2: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

    c[1] = 300;
    *(c + 2) = 301;
    3[c] = 302; /* c 语言数组名和下标可以互换，c[3] 和 3[c] 是一样的*/
    printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

    c = c + 1;
    *c = 400;
    printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);

    c = (int *) ((char *) c + 1);
    *c = 500;
    printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
       a[0], a[1], a[2], a[3]);
    /*
        int 占 4 个字节，char 占 1 个字节，c 所指的 int 原来是 400，((char *) c + 1) 以后指向第二个字节，(int *) ((char *) c + 1)后
        占据原来 a[1] 的高 3 字节和 a[2] 的低 1 字节，*c = 500 以后，a[1] 的高 3 字节存储了 500，  a[1] 的低 1 字节保留原来 301 的单字节
        部分，  a[2] 的低 1 字节被置 0 .
    */

    b = (int *) a + 1;
    c = (int *) ((char *) a + 1);
    printf("6: a = %p, b = %p, c = %p\n", a, b, c);
}

int
main(int ac, char **av)
{
    f();
    return 0;
}

《c和指针》部分抄录

1	以下是《c和指针》关于指针的指针的部分抄录：

假设：
int a = 12;
int *b = &a;
int **c = &b;
他们在内存中的模样大概是：
指针的指针
利用上述中间的一级指针可以编写代码输出内存内容：

1
2
3

void** addr = (void**) begin;
for (i = 0; i < n; ++i)
    printf("VM at %x is %x\n", addr+i, addr[i]);

上述设计思想是：指针所加内容是指针存储的地址，所加范围是由指针指向的对象类型决定。因此，二级指针addr+i所加内容是二级指针存储的一级指针地址，所加范围是由二级指针所指向的一级指针决定，此处一级指针是void ，即每次加4个字节（若是有二级指针&a是指向一个有5个整型元素的数组的地址，&a+1就是从a向后跳过一个完整的数组所占用的内存空间）。addr[i]是`(addr+i)`，即一级指针的内容。因此，这里是将内存内容当作一级指针内容看待！

假设：
char ch = ‘a’;
char cp = &ch;
1、*++cp: 间接访问操作符作用于增值后的指针的拷贝上，所以它的右值是ch后面那个内存地址的值，而它的左值就是那个位置本身。
*++cp
2.*cp++: 使用后缀++操作符的右值和左值分别是变量ch的值和ch的内存位置，也就是cp原先所指。同样，后缀++操作符在周围的表达式中使用其原先操作数的值。后缀++操作符的优先级高于*操作符，但表达式的结果看上去像是先执行间接访问操作。事实上这里涉及三个步骤：（1）++操作符产生cp的一份拷贝，（2）然后++操作符增加cp的值，（3）最后在cp的拷贝上执行间接访问操作。这个表达式常常在循环中出现，首先用一个数组的地址初始化指针，然后使用这种表达式就可以依次访问该数组的内容了。
*cp++
3.++*cp: 由于这两个操作符的结合性都是从右往左，所以首先执行的是间接访问操作。然后cp所指向的位置的值增加1，表达式的结果是这个增值后的值的一份拷贝。
++*cp
4.(*cp)++: 使用后缀++操作符，我们必须加上括号，使它首先执行间接访问操作，这个表达式的计算过程与前一个表达式相似，但结果值是ch增值前的原先值。
(*cp)++
记住两个结论：1、++优先级大于*; 2、后缀++始终返回一份拷贝（可能是指针拷贝）。

c语言内存对齐

发表于 2017-08-24 | 分类于 C/C++

结构体对齐原因

结构体对齐原因有很大部分是因为计算机扫描的内存单元个数，也就是数据总线的大小。
内存对齐的问题主要存在于理解struct等复合结构在内存中的存储结构。
在C语言中，结构是一种复合数据类型，其构成元素既可以是基本数据类型（如int、long、float等）的变量，也可以是一些复合数据类型（如数组、结构、联合等）的数据单元。在结构中，编译器为结构的每个成员按其自然对界（alignment）条件分配空间。各个成员按照它们被声明的顺序在内存中顺序存储，但不一定是相邻存储，第一个成员的地址和整个结构的地址相同。

对齐的原则

原则1：数据成员对齐规则：结构（struct或联合union）的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员obj存储的起始位置要从该成员obj大小的整数倍开始（比如int在32位机为４字节，则要从4的整数倍地址开始存储）。
原则2：结构体作为成员：如果一个结构里有某些结构体成员，则结构体成员要从其内部最大元素大小的整数倍地址开始存储。（struct a里存有struct b，b里有char，int，double等元素，那b应该从8的整数倍开始存储。）
原则3：收尾工作：结构体的总大小，也就是sizeof的结果，必须是其内部最大成员的整数倍，不足的要补齐。如果是结构体B包含了结构体A对象a，判断最大成员时并不是a，而是a结构体的最大成员。
（补：上述取最大成员的大小后，实际上应该取[#pragma pack指定的数值]与[最大成员的数值]比较小的那个为准）

这三个原则具体怎样理解呢？我们看下面几个例子，通过实例来加深理解。
例1：

struct{
    short a1;
    short a2;
    short a3;
}A;
struct{
    long a1;
    short a2;
}B;

sizeof(A) = 6; 这个很好理解，三个short都为2。
sizeof(B) = 8; 这个比是不是比预想的大2个字节？long为4，short为2，整个为8，因为原则3。

例2：

struct A{
    int a;
    char b;
    short c;
};
struct B{
    char b;
    int a;
    short c;
};

sizeof(A) = 8; int为4，char为1，short为2，这里用到了原则1和原则3。
sizeof(B) = 12; 是否超出预想范围？char为1，int为4，short为2，怎么会是12？还是原则1和原则3。

深究一下，为什么是这样，我们可以看看内存里的布局情况。

             a         b        c
A的内存布局：1111,     1*,      11

             b         a        c
B的内存布局：1***,     1111,    11**

其中星号*表示填充的字节。
A中，b后面为何要补充一个字节？因为c为short，其起始位置要为2的倍数，就是原则1。c的后面没有补充，因为b和c正好占用4个字节，整个A占用空间为4的倍数，也就是最大成员int类型的倍数，所以不用补充。
B中，b是char为1，b后面补充了3个字节，因为a是int为4，根据原则1，起始位置要为4的倍数，所以b后面要补充3个字节。c后面补充两个字节，根据原则3，整个B占用空间要为4的倍数，c后面不补充，整个B的空间为10，不符，所以要补充2个字节。

再看两个结构中含有结构成员的例子：
例3：

struct A{
    int a;
    double b;
    float c;
};
struct B{
    char e[2];
    int f;
    double g;
    short h;
    struct A i;
};

sizeof(A) = 24; 这个比较好理解，int为4，double为8，float为4，总长为8的倍数，补齐，所以整个A为24。
sizeof(B) = 48; 看看B的内存布局。

1 2	e f g h i B的内存布局：11,1111, 11111111,11**,1111, 11111111, 1111**

例4：

struct A{
    int m1;
    int *m2;
}a;
struct B{
    int m1;
    struct A m2;
}b;
printf("%d\n",sizeof(a));
printf("%d\n",sizeof(b));

输出16 24。原则2，A的存储位置将由8开始，所以结构体B的成员b.m2.m1并不会与b.m1同存储于前八个字节中；原则3，结构体的总大小并不是取决于结构体A的大小，而是A结构体的最大成员，所以总大小是24而不是32。

为什么要设计内存对齐

考虑一个问题，为什么要设计内存对齐的处理方式呢？
引入内存对齐的原因一方面在于硬件取指的方便，例如在32位总线系统上，如果一个int变量（4字节）放在一个4的倍数开始的内存地址中，则CPU可以一次将其数值读出，否则的话就要分两次才能读出。另一个重要的原因在于移植性的要求，也就是说不是所有的硬件平台都能访问任意地址上的任意数据的，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。引入内存对齐的目的主要是为了可移植性以及最大限度提升硬件性能。详细可参看如下链接http://www.doc88.com/p-032414262099.html

设计结构体习惯

最后顺便提一点，在设计结构体的时候，一般会遵照一个习惯，就是把占用空间小的类型排在前面，占用空间大的类型排在后面，这样可以相对节约一些对齐空间。

另外，测试得知，假如结构体如下：

struct execcmd{
	int type;
	char *argv[10];
};
struct execcmd *cmd;
printf("%d %d\n",sizeof(cmd->argv),sizeof(*cmd));

将输出80,88，指针（占8个字节）数组argv开始位置并不是以整个数组为准，而是以数组元素为准。
内容引用于：c中的内存对齐

关于union大小的计算

union联合体是可以（在不同时刻）保存不同类型和长度的对象的变量，通过单块的存储区存放不同类型的数据，各个成员分享共同的存储空间，联合的长度由两点决定：（1)要满足大于等于最大的成员长度;(2)且是满足(1)条件下最大的成员类型（union的对齐大小）的最小倍数。
存放变量时将会从内存中的同一位置开始，后面的变量将会覆盖以前的变量，但是如果占用的内存小于前者，那么以前未被覆盖的内存存储对象将会保持不变。

笔记021 - Lab5: File system, Spawn and Shell

发表于 2017-08-20 | 分类于 MIT6.828 Operating System Engineering

File system preliminaries

jos实现的文件系统要比大多数文件系统简单（包括xv6），主要在分层目录结构的管理下实现文件的增删查改。
jos操作系统是单用户的，不提供多用户的保护。因此，jos文件系统不支持UNIX文件所有权和权限的概念，不支持硬链接、符号链接、时间戳或特殊设备文件。

On-Disk File System Structure

大多数unix文件系统将磁盘空间分为两种区域类型：inode regions和data regions。unix文件系统为每个文件分配一个inode，文件的inode保存了文件的关键元数据（meta-data）：如stat属性和指向data blocks的指针。data regions被分为8KB或更大的数据块data blocks，用于保存文件数据和目录元数据（directory meta-data）。目录项directory entries包含文件名和指向inodes的指针。假如有多个目录项指向了同一个文件的inodes，说明该文件被hard-linked。由于jos文件系统不支持hard links，所以不需要这种级别的“间接寻址”，jos文件系统不会使用inodes，而是在描述文件的相关目录项中保存文件/子目录的元数据。
文件和目录在逻辑上都会关联到一系列data blocks，这些data blocks可能是分散在磁盘上，就好比虚拟地址空间关联到一系列分散的物理页。文件系统隐藏了数据块分布的细节，提供在文件内任意偏移处读写字节序列的接口。对于创建和删除文件等操作，文件系统内部处理了所有相关的目录修改。jos文件系统允许用户进程直接读取目录元数据（e.g., read），用户进程可以自己实现目录浏览（e.g. 实现ls），而不必依赖于特定的文件系统调用接口。这种方法的缺点是应用程序依赖于目录元数据的格式，一旦修改了文件系统的内部布局，应用程序需要作出修改或重新编译。

Sectors and Blocks

大多数磁盘无法支持字节粒度的读写，取而代之的是sector粒度的读写，通常是512字节。文件系统分配和使用磁盘存储的单元是block。sector和block的术语区别是：sector size是磁盘硬件的一个属性，block size则是操作系统使用磁盘所使用的一个概念。文件系统的block size必须是sector size的整数倍。
xv6将block size定义为512字节。由于存储空间越来越便宜，而且更大粒度有利于存储管理，所以大多数现代文件系统使用了更大的block size。jos文件系统使用了4096字节大小的block size，方便于匹配页大小。

Superblocks

文件系统通常在磁盘某个容易寻找的位置保留特定的磁盘块，用于存储文件系统的元数据描述属性。比如：block size、disk size、查找root目录所需的元数据、文件系统上次挂载时间、上次检查磁盘错误的时间等。这些特殊的磁盘块称为superblocks。
jos文件系统有一块superblock，位于磁盘的block 1，它的定义是inc/fs.h的struct Super。block 0用于保留启动引导程序和分区表，所以文件系统没有使用它。许多现代的文件系统维护了多个superblocks，并在磁盘的多个位置进行复制，一旦某一个损坏了或其他原因，就可以使用下一个superblock。

磁盘布局如下：
disk布局

File Meta-data

inc/fs.h的struct File定义了描述文件的元数据布局。jos的文件元数据包括文件名、大小、类型（常规文件还是目录）、指向blocks的指针。jos没有inodes，所以文件元数据直接存储在磁盘的目录项中。不像其他文件系统，无论是在磁盘上还是在内存上，jos使用File数据结构来代表文件元数据。

File元数据的格式如下：

struct File的f_direct数组的前十个成员存储了文件前10个blocks的block numbers，这10个blocks被称为文件的direct blocks。对于小于10*4096 = 40KB的文件，意味着该文件所有blocks的block numbers将直接在File结构上直接匹配。对于更大的文件，则另外分配一个磁盘块以保存4096/4 = 1024个blocks的block number，该磁盘块称为文件的indirect block。因此，文件大小的上限是1034 blocks，大于4M。为了支持更大的文件，其他文件系统通常支持double-indirect和triple-indirect blocks。

Directories versus Regular Files

jos的File结构体既可以代表常规文件，也可以代表目录。文件系统以同样的方式管理常规文件和目录文件，除了：文件系统不解析常规文件相关联的数据块内容，但会将目录文件的内容解析为一系列的File结构，用于描述目录中的文件和子目录。
superblock包含了一个File结构（struct Super的root区域），用于保存root目录的元数据。该目录文件的内容是一系列File结构，用于描述root目录中的文件和子目录。

The File System

我们主要实现以下关键功能：读取blocks到block cache中、刷新block cache到磁盘中、分配磁盘块、映射文件偏移到磁盘块、实现read/write/open的IPC接口。

Disk Access

操作系统需要能够访问磁盘，传统的monolithic操作系统策略是在内核中添加IDE磁盘驱动并且提供文件系统访问磁盘所需的系统调用接口，而jos的做法是将IDE磁盘驱动作为用户级别文件系统进程的一部分。需要对内核作轻微修改，确保文件系统进程拥有实现磁盘访问所需的相关特权。
依赖轮询和基于可编程输入输出（”programmed I/O” - PIO）的磁盘访问，可以很方便在用户空间实现磁盘访问。jos不使用中断来实现磁盘访问，虽然在用户模式下也可以实现以中断驱动的设备驱动程序，但是内核必须识别设备中断并分配到正确的用户模式进程，难度更大。
x86处理器使用了EFLAGS的IOPL位来决定是否允许保护模式代码使用device I/O指令（如IN和OUT指令）。device I/O指令需要访问的所有IDE磁盘寄存器都在x86的I/O space上而不是被内存映射，为了允许文件系统可以访问这些寄存器，我们只需要提供I/O privilege即可。EFLAGS的IOPL位使得内核可以简单地使用”all-or-nothing”方法来控制用户代码是否可以访问I/O space。在jos中，我们将文件系统实现为一个用户进程，其他进程使用IPC与文件系统进程通信，并且只允许文件系统进程访问I/O space，但不允许其他进程访问I/O space。

I/O space请参考 I/O space。

1	Exercise 1. i386_init使用了ENV_TYPE_FS来标识文件系统进程，修改env.c的env_create函数，使其能根据ENV_TYPE_FS向文件系统进程给出相关的I/O权限。

//env.c的env_create函数

void
env_create(uint8_t *binary, enum EnvType type)
{
	// LAB 3: Your code here.  
	struct Env *newEnv;
	//Allocates a new env 
	int i = env_alloc(&newEnv,0);
	if(i<0) panic("env_create");
	//loads the named elf binary into
	load_icode(newEnv,binary);
	//set env_type
	newEnv->env_type = type;
	
	// If this is the file server (type == ENV_TYPE_FS) give it I/O privileges.
	// LAB 5: Your code here.
	if (type == ENV_TYPE_FS){ 
		// Give I/O privileges while in file environment. 
		newEnv->env_tf.tf_eflags |= FL_IOPL_MASK;
	}
}

1	Question. 是否需要对内核作出什么修改，确保在进行进程切换时相关的I/O权限设置能够正常地保存和恢复？

不需要。进程切换时硬件会自动保存elfags，而在执行新进程时，env_pop_tf的iret指令会恢复eflags。

本实验的GNUmakefile将obj/kern/kernel.img作为disk 0的镜像，将obj/fs/fs.img作为disk 1的镜像。在本实验中，文件系统只能访问disk 1，而disk 0用于启动内核。
disk 0,disk 1

Challenge! JOS目前用的是最简单的PIO（Programming I/O）方式与磁盘交互。请实现中断驱动的IDE磁盘访问（可借助DMA（直接存储器存取））。可以考虑该设备驱动移植到内核中，或者移植到用户空间中、与文件系统进程在一块，或者移植到单独的进程中。

???

The Block Cache

jos将借助处理器的虚拟内存实现一个简单的buffer cache（block cache），见fs/bc.c。
jos文件系统能够处理的磁盘大小被限制在3GB以内。文件系统进程的地址空间[DISKMAP,DISKMAP+DISKMAX)，即[0x10000000,0xD0000000)被保留，用于磁盘的内存映射，如：block 0映射到0x10000000，block 1映射到0x10001000。fs/bc.c的diskaddr函数实现了磁盘块到虚拟地址的映射。
由于文件系统进程的虚拟地址空间完全独立于其他进程，且文件系统进程唯一要完成的工作是实现文件访问，所以通过上述方式保留大部分进程地址空间的做法是合理的；但是对于32位机子上真正实现的文件系统而言，上述方式并不合适，因为现代磁盘大于3G。不过，类似的buffer cache管理方法仍然适用于64位地址空间的机器。
为了避免将整个磁盘读取内存，jos实现了一种请求分页demand paging的形式，当在某个磁盘映射区域发生页错误时，分配相关的页并且读取相关的block。

Exercise 2. 实现fs/bc.c的bc_pgfault和flush_block函数。
bc_pgfault用于在页错误时从磁盘中加载页，注意给定的addr可能没有对齐block边界、ide_read操作的是sectors而不是blocks。
flush_block函数根据需要将block写入到磁盘。如果block没有在block cache中（该页没被映射）或者block不是dirty的，flush_block函数什么都不做。
jos将使用VM hardware来追踪一个磁盘块自从上次读取或写入磁盘之后是否被修改过。使用PTE_D标志位标记block是否dirty。处理器写页时，设置PTE_D位；将block写入到磁盘后，清除PTE_D位。

//fs/bc.c的bc_pgfault
// Allocate a page in the disk map region, read the contents
	// of the block from the disk into that page.
	// Hint: first round addr to page boundary. fs/ide.c has code to read
	// the disk.
	//
	// LAB 5: you code here:
	addr = ROUNDDOWN(addr, PGSIZE);
	if ((r = sys_page_alloc(0, addr, PTE_P|PTE_U|PTE_W)) < 0)
		panic("in bc_pgfault, sys_page_alloc: %e", r); 
	if ((r = ide_read(blockno*BLKSECTS, addr, BLKSECTS)) < 0)
		panic("in bc_pgfault, ide_write: %e", r);


	// Clear the dirty bit for the disk block page since we just read the
	// block from disk
	if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
		panic("in bc_pgfault, sys_page_map: %e", r);

注意：flush_block函数的参数是文件系统进程中映射到磁盘块的虚拟地址。

//fs/bc.c的flush_block
	addr = ROUNDDOWN(addr, PGSIZE);
	int r; 
	if(va_is_mapped(addr) && va_is_dirty(addr)){
		if ((r = ide_write(blockno*BLKSECTS, addr, BLKSECTS)) < 0)
			panic("in flush_block, ide_write: %e", r);
		if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
			panic("in flush_block, sys_page_map: %e", r);
	}

fs/fs.c的fs_init是使用block cache的一个例子。初始化block cache之后（设置页错误处理函数，尝试读取super block的映射内存，该动作会导致页错误并最终读取super block到内存中），fs_init函数将全局结构体指针变量super指向了磁盘disk 1的内存映射区域，之后就可以读取super结构体。

Challenge! 一旦block出错，block cache将不会移除相应内容，并且会永远保存在内存中。请给block cache添加回收策略。使用PTE_A访问位，对任何页的访问，硬件都会设置该位。

1
2
3

???
包括bc_pgfault检查block是否为空的原因？
http://wenku.baidu.com/link?url=oANF8V6KZIkGoabt_gkRjWaqoq1nkOq9U7XPMxHRVaeSXjMubzS8I5bNzDCnEYNli0BPrbs0Zc0OJ7vDHBVPnsj8YZ1BHELOSOWWEI0J64i

The Block Bitmap

fs_init设置了bitmap指针指向block 2的起始位置（但不一定就是说只有block 2被用于block map），bitmap是一个uint32_t *类型的指针，用于判断磁盘块是否已被分配使用，每一个bit位代表一个block，置0代表对应的block已被用。在fs被制成镜像时已经默认将block 0、block 1以及被用于bitmap的块对应的bit位置0。

Exercise 3. 实现alloc_block，在bitmap中查找可用的block，一旦找到，更新对应的bit位，并将该bit位所在的bitmap block更新到磁盘中（注意不一定是block 2），返回对应的block number。

//fs.c
int
alloc_block(void)
{
	// The bitmap consists of one or more blocks.  A single bitmap block
	// contains the in-use bits for BLKBITSIZE blocks.  There are
	// super->s_nblocks blocks in the disk altogether.

	// LAB 5: Your code here.
	//panic("alloc_block not implemented");
	uint32_t i;  
	for (i = 0; i < super->s_nblocks; i++){
		if(bitmap[i/32] & 1<<(i%32)){
			bitmap[i/32] &= ~(1<<(i%32));
			flush_block((void *) &bitmap[i / 32]);
			return i;
		}
	}
	return -E_NO_DISK;
}

File Operations

fs/fs.c提供了一系列函数用于解析和管理File结构、浏览和管理目录文件项、由根目录开始解析一个绝对路径等。

1	Exercise 4. 完成file_block_walk和file_get_block函数。

file_block_walk函数的原型是file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)，指定File f和该文件的某个逻辑block number，在f_direct[NDIRECT]或f_indirect对应的间接块中寻找对应存储磁盘block number的项，将该项地址存储到ppdiskbno，如果alloc为true则允许创建间接块（并清0）。
file_get_block函数的原型是file_get_block(struct File *f, uint32_t filebno, char **blk)，指定File f和该文件的某个逻辑block number，在f_direct[NDIRECT]或f_indirect对应的间接块中找到逻辑block number对应的磁盘block存储位置pdiskbno，如果该位置数据为空，则分配一个新的磁盘block并将磁盘block number存到pdiskbno上。将新分配的磁盘block对应的虚拟地址存储到blk中。注意到：每个磁盘块都有对应的虚拟地址，但是此时新分配的磁盘块并未读入到内存中。

static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{ 
	int r;
	if(filebno < NDIRECT){
		*ppdiskbno = &f->f_direct[filebno];
		return 0;
	}
	filebno -= NDIRECT;

	if(filebno < NINDIRECT){
		if(!f->f_indirect){
			if (!alloc) return -E_NOT_FOUND;
			//alloc indirect block
			if((r=alloc_block()) < 0) return r;//-E_NO_DISK
			f->f_indirect = r;
			memset(diskaddr(f->f_indirect),0,BLKSIZE);
		} 
		*ppdiskbno = &(((uint32_t *)diskaddr(f->f_indirect))[filebno]);
		return 0;
	}
	return -E_INVAL;
}

int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{ 
	int r;
	uint32_t *pdiskbno;
	//ok to alloc indirect block
	if((r = file_block_walk(f,filebno,&pdiskbno,true)) < 0) return r;
	if(pdiskbno == NULL || *pdiskbno == 0){ // target block hasnot been allocated
		if((r=alloc_block()) < 0) return r;//-E_NO_DISK
		*pdiskbno = r;
	}
	*blk = (char *)(diskaddr(*pdiskbno));
	return 0;
}

Challenge! 如果某些文件操作执行一半的时候，由于崩溃或重启可能导致文件系统损坏。尝试实现软更新或日志文件系统，使得文件系统损坏是可恢复的。

???

The file system interface

客户端进程不能直接调用文件系统进程的函数，而是通过远程过程调用（RPC - remote procedure call）的形式，jos的RPC基于IPC机制。以读取文件为例，RPC过程如下：

      Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

read根据文件描述符号找出对应的文件描述符，然后将请求分配给正确的设备读取函数devfile_read（可以有更多的设备类型如管道）。devfile_read负责构造ipc请求参数，并调用fsipc函数发送ipc请求，解压返回结果并返回。fsipc函数负责发送ipc请求并接收响应结果。
文件系统服务代码为fs/serv.c。在serve函数循环体中，阻塞等待接收文件操作ipc请求，并分发到对应的处理函数如serve_read，然后将处理结果通过ipc回送。serve_read根据请求中的文件信息寻找对应的OpenFile结构，然后调用file_read函数读取磁盘文件，并更新文件偏移。
jos的ipc允许发送一个32-bit数和一个共享页地址。客户端发送给文件系统服务端的请求中，使用了32-bit数来传递请求类型，并将请求参数存放在union Fsipc中，该结构的数据存于ipc共享页中。在客户端进程中，固定的共享地址是fsipcbuf；在服务端进程中，固定将接收的共享页映射到fsreq(0x0ffff000)。
文件系统进程使用ipc回送结果，使用了32-bit数来传递返回码。FSREQ_READ和FSREQ_STAT会返回数据，数据将写到共享页中。进行文件读取时，客户端进程发送buffer映射页，ipc send会将该页映射到文件系统进程中，文件系统填充该页后，发送执行结果到客户端，并解除映射。文件系统进程不需要将映射页发送给客户端，因为两者已经共享内存了。而对于FSREQ_OPEN，它会向客户端共享一个新的“Fd page”，该文件描述符页地址会作为ipc结果返回。

ipc可支持并发访问文件系统，文件系统进程每次ipc recv时阻塞，假设有多个进程并发向文件系统发送请求，由于内核锁的原因，某个时刻只能有一个进程导致进入内核模式且对文件系统进程的阻塞状态进行解除；等执行下一个进程导致进入内核模式时，文件系统已经不再是阻塞状态了，因此后续所有进程都需要循环尝试ipc send直到文件系统进程再次阻塞。文件系统进程处理完一个进程的请求之后才会再次陷入阻塞。
注意到：文件操作涉及的ipc调用时，可能会出现客户端调用ipc_recv并指定期望接收到响应页的虚拟地址，而文件系统进程则是根据情况返回响应页虚拟地址或0。如果客户端指定接收的虚拟地址，文件系统进程返回的地址却为0，我们会在ipc_send中将值为0的地址重新设为一个标志”no page”的特定值，但在sys_ipc_try_send中我们又尝试对发送的地址进行页对齐检查。因此，鉴于以上情况，标志”no page”的特定值必须页对齐，可设为KERNBASE。

1	Exercise 5. 实现fs/serv.c的serve_read。serve_read调用file_read函数读取磁盘文件，serve_read本身只需要提供文件读取的RPC接口。

int
serve_read(envid_t envid, union Fsipc *ipc)
{
	struct Fsreq_read *req = &ipc->read;
	struct Fsret_read *ret = &ipc->readRet;

	if (debug)
		cprintf("serve_read %08x %08x %08x\n", envid, req->req_fileid, req->req_n);

	// Lab 5: Your code here:
	int r;
	struct OpenFile *o;
	if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0)
		return r;
	if ((r = file_read(o->o_file,ret->ret_buf,req->req_n,o->o_fd->fd_offset)) < 0)
		return r;
	o->o_fd->fd_offset += r;
	return r;
}

1	Exercise 6. 实现fs/serv.c的serve_write、lib/file.c的devfile_write。

// lib/file.c的devfile_write

static ssize_t
devfile_write(struct Fd *fd, const void *buf, size_t n)
{
	// Make an FSREQ_WRITE request to the file system server.  Be
	// careful: fsipcbuf.write.req_buf is only so large, but
	// remember that write is always allowed to write *fewer*
	// bytes than requested.
	// LAB 5: Your code here
	//panic("devfile_write not implemented");
	uint32_t max = PGSIZE - (sizeof(int) + sizeof(size_t));//see fs.h
	if (n > max) n = max;

	fsipcbuf.write.req_fileid = fd->fd_file.id;
	fsipcbuf.write.req_n = n; 
	memmove(fsipcbuf.write.req_buf, buf, n);
	return fsipc(FSREQ_WRITE, NULL);	  
}

//fs/serv.c的serve_write

// Write req->req_n bytes from req->req_buf to req_fileid, starting at
// the current seek position, and update the seek position
// accordingly.  Extend the file if necessary.  Returns the number of
// bytes written, or < 0 on error.
int
serve_write(envid_t envid, struct Fsreq_write *req)
{
	if (debug)
		cprintf("serve_write %08x %08x %08x\n", envid, req->req_fileid, req->req_n);

	// LAB 5: Your code here.
	//panic("serve_write not implemented");
	int r;
	struct OpenFile *o;
	if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0)
		return r;
	if ((r = file_write(o->o_file,req->req_buf,req->req_n,o->o_fd->fd_offset)) < 0)
		return r;
	o->o_fd->fd_offset += r;
	return r;
}

Spawning Processes

lib/spawn.c用于创建新进程（设置进程内核空间部分的页目录、复制父进程的trapframe等，但没有映射用户地址空间），设置子进程的trapframe（如修改eip入口为程序入口），初始化子进程用户栈（分配空间、存储传递的参数），从文件系统加载程序文件到新进程中（分配新物理页存储），然后让子进程开始执行该程序。spawn类似于UNIX的fork，在子进程中直接跟进exec。

1
2

Exercise 7. spawn函数需要设置子进程的trapframe。实现sys_env_set_trapframe系统调用，需要检查给出的trapframe地址是否可写，并且需要确保子进程执行期间能够触发中断。
注意到：系统调用过程中传递struct Trapframe *地址的方式是调用前先转换为uint32_t类型，调用后再转换为struct Trapframe *。

static int
sys_env_set_trapframe(envid_t envid, struct Trapframe *tf)
{ 
	struct Env *e; 
	// check whether the current environment has permission to set envid's trapframe. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(envid,&e,true);
	if(r<0) return r;//-E_BAD_ENV 
	// check whether the user has supplied us with a good address!
	user_mem_assert(e, tf, sizeof(struct Trapframe), PTE_U | PTE_W);//see in kern/pmap.c
	e->env_tf = *tf;
	// Enable interrupts while in user mode. 
	e->env_tf.tf_cs = GD_UT | 3;
	e->env_tf.tf_eflags |= FL_IF;
	return 0;
}

1	Challenge! 实现unix形式的exec。

xv6创建子线程并执行新程序的流程大致是：1、用户态调用fork创建子进程，包括复制物理页。2、用户态执行用户子进程，调用exec尝试执行新程序。3、内核态读取新程序内容，映射到新的地址空间中。4、内核态更换子进程的地址空间，释放旧地址空间。
jos使用spawn创建子线程并执行新程序的流程大致是：1、用户态spawn创建子线程，只设置进程内核空间部分的页目录、复制父进程的trapframe等，但没有映射用户地址空间。2、用户态spawn读取程序文件到子进程地址空间中（调用系统调用函数分配、映射物理页）。3、用户态spawn设置子进程用户栈和trapframe（包括执行入口），调用系统调用函数更新子进程trapframe。4、用户态spawn设置子进程为可执行。
jos使用exec创建子线程并执行新程序的流程大致是：1、用户态exec调用fork创建子线程，地址空间映射为写时复制。2、用户态exec读取程序文件到子进程地址空间中，但注意应该是临时的空间（如段地址都加上一段临时位移）。3、用户态exec设置子进程用户栈和trapframe（包括执行入口），调用系统调用函数更新子进程trapframe。4、用户态exec调用系统调用函数更换地址空间映射。5、用户态exec设置子进程为可执行。（此流程的正确性待验证）

1	Challenge! 实现mmap-style的内存映射文件，修改spawn，支持直接从ELF镜像文件中映射物理页。

unix文件描述符是一个综合概念，包括文件、管道、console I/O等设备类型。在jos中，每一个设备类型都有相关联的struct Dev，以及读写相关的函数指针。每一个struct Fd指明了它的设备类型，lib/fd.c的大多数函数只是负责分发处理函数到对应的struct Dev。
lib/fd.c同时负责维护每个应用进程的文件描述符表区域，该区域从FSTABLE开始，每个文件描述符对应一个页，一个进程一次最多可以打开32个文件描述符。当且仅当文件描述符被使用时，其相关的文件描述符表页才被映射。每个文件描述符还有一个可选的数据页，从FILEDATA地址开始。
我们希望通过fork和spawn来共享文件描述符状态，但是文件描述符状态是保存在用户空间中的。目前，fork将内存映射为写时复制，文件描述符状态会被复制而不是共享（意味着进程不能seek这些不是由它们本身打开的文件，也不能使用管道）；spawn则完全不处理这些相关内存，因此创建的新进程没有打开任何文件描述符。
因此，我们将标记特定部分的内存区域是共享的。采取的方法是使用页表项中的一个未使用位（如PTE_COW的做法一样）。具体使用的位是定义于inc/lib.h的PTE_SHARE位，Intel和AMD保留了三个软件可用的PTE位，这是其中之一。一旦页表项设置了PTE_SHARE位，则fork和spawn需要直接复制物理页到子进程中。

1	Exercise 8. 修改lib/fork.c的duppage和lib/spawn.c的copy_shared_pages，实现PTE_SHARE。

static int
duppage(envid_t envid, unsigned pn)
{
	int r;

	// LAB 4: Your code here.
	//panic("duppage not implemented"); 
	void *addr = (void *)(pn*PGSIZE);
	if ( (uvpt[pn] & PTE_SHARE) == PTE_SHARE ) { 
		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, uvpt[pn] & PTE_SYSCALL)) < 0)
			panic("sys_page_map: %e\n", r);
	} else if( (uvpt[pn] & PTE_W) == PTE_W || 
	    (uvpt[pn] & PTE_COW) == PTE_COW){ 
 		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, PTE_P|PTE_U|PTE_COW)) < 0){
			panic("sys_page_map: %e", r);
 		} 
 		if ((r = sys_page_map(0, (void *)addr, 0, (void *)addr, PTE_P|PTE_U|PTE_COW)) < 0){
			panic("sys_page_map: %e", r);
 		} 
	}else{
		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, PTE_P|PTE_U)) < 0){
			panic("sys_page_map: %e", r);
 		}
	}
	return 0;
}

static int
copy_shared_pages(envid_t child)
{
	// LAB 5: Your code here. 
	unsigned addr;
	int r;
	for (addr = 0; addr < USTACKTOP; addr += PGSIZE){
		if ((uvpd[PDX(addr)] & PTE_P) == PTE_P
			&& (uvpt[PGNUM(addr)] & PTE_SHARE) == PTE_SHARE
		    && (uvpt[PGNUM(addr)] & PTE_U) == PTE_U) {
		    if ((r = sys_page_map(0, (void *)addr, child, (void *)addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
				panic("sys_page_map: %e\n", r);
		} 
	}
	return 0;
}

注意：user/testpteshare.c中先在父进程的0xA0000000上分配页并设为共享页，然后调用fork创建子进程。在lab4中，我们映射的地址范围是[UTEXT,end[])，然而在user/testpteshare.c这种情况中，0xA0000000地址是大于end的，所以该共享页不会被映射到子进程中，后续子进程往0xA0000000写入数据会造成页错误，但是该页没被设为写时复制，会直接panic。因此，我们需要修正映射的地址范围，改为[0,USTACKTOP)，但需要判断是否有对应的页目录项和页表项。

The keyboard interface

QEMU显示输出到CGA和串行口，但目前为止我们只在嵌入内核监控的时候进行输入。在QEMU图形窗口中的键入表现为键盘键入，在控制台的键入表现为串行口的特性。kern/console.c包含了内核监控所使用的键盘和串行驱动。

1	Exercise 9. 在kern/trap.c中，调用kbd_intr处理IRQ_OFFSET+IRQ_KBD中断，调用serial_intr来处理IRQ_OFFSET+IRQ_SERIAL中断。

lib/console.c实现了控制台input/output文件类型，当控制台文件类型消耗缓冲区的时候（drains the buffer），kbd_intr和serial_intr将最新读取的输入填充到一个缓冲区中。（控制台文件类型默认被stdin/stdout使用，除非用户对其重定向）

The Shell

user/icode调用spawn执行init，init程序将控制台设为文件描述符0和1，然后调用spawn执行shell。注意到库函数cprintf直接向控制台输出，没有借助任何文件描述符代码。这种做法有利于debug但不利于使用管道与其他程序通信。使用类似fprintf(1, “…”, …)的形式向特定的文件描述符进行输出。printf(“…”, …)是输出到文件描述符1的简略形式。

1	Exercise 10. 在user/sh.c中添加相关内容，使之支持重定向。

void runcmd(char* s)

		case '<':	// Input redirection
			// Grab the filename from the argument list
			if (gettoken(0, &t) != 'w') {
				cprintf("syntax error: < not followed by word\n");
				exit();
			}
			// Open 't' for reading as file descriptor 0
			// (which environments use as standard input).
			// We can't open a file onto a particular descriptor,
			// so open the file as 'fd',
			// then check whether 'fd' is 0.
			// If not, dup 'fd' onto file descriptor 0,
			// then close the original 'fd'.

			// LAB 5: Your code here.
			//panic("< redirection not implemented");			
			if ((fd = open(t, O_RDONLY)) < 0) {
				cprintf("open %s for read: %e", t, fd);
				exit();
			}
			if (fd != 0) {
				dup(fd, 0);
				close(fd);
			}
			break;

Challenge! 为shell添加更多功能，使之支持：
backgrounding commands (ls &)
multiple commands per line (ls; echo hi)
command grouping ((ls; echo hi) | cat > out)
environment variable expansion (echo $hello)
quoting (echo "a | b")
command-line history and/or editing
tab completion
directories, cd, and a PATH for command-lookup.
file creation
ctl-c to kill the running environment

fd、dev、file

jos的文件系统进程负责维护File数据结构、fd与file之间的关系，并以fd与其他进程进行交互。其他进程并不操作File数据结构，而是以fd与文件系统进程进行交互，具体是共享填充fd数据结构的页面。
jos的文件描述符包括文件、管道、console I/O三种设备dev类型，每种类型都有相应的文件读写接口，定义一致。用户进程在使用时，具体指定一种dev类型。每个类型的dev都有对应的id，并存在fd中，然后调用库函数与文件系统交互。在上述三种文件类型中，只有涉及文件类型时才会与文件系统进程进程交互。
File的定义如下：

struct File {
	char f_name[MAXNAMELEN];	// filename
	off_t f_size;			// file size in bytes
	uint32_t f_type;		// file type

	// Block pointers.
	// A block is allocated iff its value is != 0.
	uint32_t f_direct[NDIRECT];	// direct blocks
	uint32_t f_indirect;		// indirect block

	// Pad out to 256 bytes; must do arithmetic in case we're compiling
	// fsformat on a 64-bit machine.
	uint8_t f_pad[256 - MAXNAMELEN - 8 - 4*NDIRECT - 4];
} __attribute__((packed));	// required only on some 64-bit machines

fd的定义如下：

struct FdFile {
	int id;
};

struct Fd {
	int fd_dev_id;
	off_t fd_offset;
	int fd_omode;
	union {
		// File server files
		struct FdFile fd_file;
	};
};

dev的定义如下：

struct Dev {
	int dev_id;
	const char *dev_name;
	ssize_t (*dev_read)(struct Fd *fd, void *buf, size_t len);
	ssize_t (*dev_write)(struct Fd *fd, const void *buf, size_t len);
	int (*dev_close)(struct Fd *fd);
	int (*dev_stat)(struct Fd *fd, struct Stat *stat);
	int (*dev_trunc)(struct Fd *fd, off_t length);
};
 
extern struct Dev devfile;
extern struct Dev devcons;
extern struct Dev devpipe;

文件类型的交互

文件系统进程使用OpenFile关联file和fd，OpenFile定义如下：

struct OpenFile {
	uint32_t o_fileid;	// file id
	struct File *o_file;	// mapped descriptor for open file
	int o_mode;		// open mode
	struct Fd *o_fd;	// Fd page
};

OpenFile的fd关联着一个页地址，当具体分配fd时，会分配相应的物理页用于存储fd数据。进行文件读写时，fd用于保存文件的偏移、dev的id、文件id等信息，文件读写时是根据文件的偏移来计算逻辑块编号的；file则用于根据逻辑块编号查找存储的磁盘块编号。jos文件系统的磁盘块和文件系统进程的内存映射是固定的，根据file和逻辑块编号找到磁盘块编号之后，可得到对应的内存虚拟地址，在文件系统进程地址空间中读取该虚拟地址时，若发生页错误，文件系统进程注册的页错误处理函数会先读取磁盘内容到文件系统进程的地址空间中；用户进程写入内容到fd时，会在fd结构中找到对应的fileid并发送给文件系统进程，文件系统进程根据fileid找到对应的openfile，进而找到对应的file，并根据文件偏移计算逻辑块编号，再得到磁盘块编号和内存虚拟地址，最终填充数据到对应的内存空间中，支持close的时候会执行刷新动作，将脏内存内容更新到磁盘。

File数据结构既用于管理Dir，又用于管理File。File数据结构本身存储于文件系统进程的block diskmap内存空间中[0x10000000,0xD0000000)，dir关联的每一个block存储着若干直接子目录dir/file结构的数据，dir的size大小为存储直接子目录dir/file结构的所有block的总大小。

文件系统进程最多一次性支持1024个openfile，对应1024个fd，fd页地址从0xD0000000开始。用户进程发送文件open请求时，文件系统进程将寻找可用的fd并返回对应索引的openfile。open成功的情况是找到可用的fd和根据路径找到正确的file结构，然后使用ipc发送返回fd页地址，这种情况下fd页引用为2：一次是分配fd的时候，一次是ipc发送返回的时候映射到目标进程的地址空间；查找可用fd的过程中，如果fd页引用为0，会分配对应的物理页，使得fd页引用为1，此后如果出现其他错误，返回的fd页地址尚未被设置，则ipc发送返回的时候fd页不会映射到目标进程的地址空间，fd页引用保持为1；这说明，当fd页引用为0或1时，代表fd可用；下次查找可用fd的时候仍然会使用引用为1的fd，但省略分配新物理页的步骤，而只是累加fileid。

open成功时使用ipc返回fd页地址，存储着fileid、devid等信息（devid初始化为文件类型对应的id）。之后，用户进程从fd中读取fileid等信息，与文件系统进程继续进行交互，也可以编码改变文件偏移等信息，因为文件系统进程与用户进程共享该fd页。

用户进程一次最多可以打开32个fd，具体相关的库函数见lib/fd.c。用户进程的fd页地址从0xD0000000开始，file设备的open函数（见file.c）的功能是在用户进程中分配空闲的fd页虚拟地址，然后向文件系统进程发送open文件的ipc请求，表示希望在该fd页虚拟地址上接收文件系统进程共享的fd页，open函数转换为相应的fd索引返回，此后使用fd索引即可在用户进程中找到对应的fd页和数据。

库函数fd.c负责管理fd索引和fd页之间的转换，以及由小到大分配用户fd。file.c、pipe.c、console.c为具体的设备文件，三者的访问接口一致，但具体实现细节不同。用户进程调用fd.c的相关函数进行文件读写时传递fd索引参数，fd.c的函数根据fd索引找到fd实例，然后找到具体的dev并调用对应的设备函数。

关于fd的释放，用户进程调用fd.c的close函数一方面会调用相关设备的close函数（文件设备的close函数会发送请求到文件系统进程，刷新内存脏页到磁盘），并解除用户进程在fd上的页映射，该做法会导致fd页的引用变为1，从而文件系统进程可复用该fd页。

管道的交互

pipe的定义如下：

struct Pipe {
	off_t p_rpos;		// read position
	off_t p_wpos;		// write position
	uint8_t p_buf[PIPEBUFSIZ];	// data buffer
};

jos的管道大概实现是：在用户进程中分配两个fd页（权限设置为共享），fd0权限设为只读，fd1权限设为只写；这两个fd还有对应的data虚拟地址，两者映射到同一张物理页（权限设置为共享）表示管道共享这一张物理页，该物理页存储着pipe数据结构，包括读写指针和缓冲区。user/testpipe.c的大概过程是：主进程调用pipe分配两个fd，然后调用fork创建子进程，fork会将共享页之外的可写页/写时复制页映射为写时复制；此时父子进程都有相同的fd页映射和fd data页映射；之后子进程关闭fd1，解除fd1页映射，然后尝试从fd0中读取；父进程关闭fd0，解除fd0页映射，然后尝试往fd1中写入。由于父进程的fd0、fd1共享一张data物理页，fork的过程会将对应页访问权限映射到子进程中（fork中并没有将子进程对应的页权限也设为PTE_SHARE，这表示父进程共享给子进程的页不一定能共享给子进程创建的子子进程），所以子进程的fd0与父进程的fd1共享同一张data物理页。管道读写时实际上是操作data物理页，写时：对于每一个即将写入到缓冲区的字节，若写指针>=读指针+缓冲区大小，说明缓冲区已满，调用sys_yield尝试切换执行其他进程，否则写入缓冲区并写指针加1（写入时写指针取余数）；读时：循环即将读取的字节大小，若读指针=写指针，说明缓冲区为空，调用sys_yield尝试切换执行其他进程，否则从缓冲区读取一个字节，读指针加1（读取时读指针取余数）。

注意到，jos的管道没有涉及到文件系统进程。

笔记020 - HW11: xv6 log

发表于 2017-08-20 | 分类于 MIT6.828 Operating System Engineering

笔记019 - HW10: bigger files for xv6

发表于 2017-08-20 | 分类于 MIT6.828 Operating System Engineering

题意

xv6的inode包括12个直接的block number和1个间接的block，间接的block存储128个block number，最大支持的文件长度为12+128=140个sectors。
修改xv6，将其中一个block number修改为双层间接的block，使得最大支持的文件长度为11+128+128x128=16523个sectors。

解决思路

Makefile

CPUS := 1
QEMUOPTS : 添加 -snapshot

1	下载big.c，添加到Makefile的UPROGS。

param.h 修改FSSIZE

//#define FSSIZE       1000  // size of file system in blocks
#define FSSIZE       21113  // size of file system in blocks

fs.h 修改NDIRECT、MAXFILE、dinode.addrs，添加NDBINDIRECT

//#define NDIRECT 12
#define NDIRECT 11 
#define NDBINDIRECT (NINDIRECT * NINDIRECT)

#define NINDIRECT (BSIZE / sizeof(uint)) // 512/4=128
//#define MAXFILE (NDIRECT + NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT +NDBINDIRECT)

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  //uint addrs[NDIRECT+1];   // Data block addresses
  uint addrs[NDIRECT+2];   // Data block addresses
};

file.h 修改inode.addrs

struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock;
  int flags;          // I_VALID

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  //uint addrs[NDIRECT+1];
  uint addrs[NDIRECT+2];
};

fs.c的bmap()函数负责根据逻辑block number返回对应的物理block（若对应的记录为空，则先分配）。原先的bmap()函数先检查逻辑block number是否在NDIRECT范围内（直接的block）；否则，逻辑block number减去NDIRECT，检查新的逻辑block number是否在NINDIRECT范围内（间接的block）。新添加的处理过程是：逻辑block number再减去NINDIRECT，检查新的逻辑block number是否在NDBINDIRECT范围内（双层间接的block）。如果符合要求，则根据需要获取间接block内容或分配最终的block。

xv6 inode的标准格式如下：

扩展后的xv6 inode的格式如下：

编译并运行：

$ make qemu
$ big
``` 
{% asset_img 3.JPG 编译并运行 %}
可以看到，系统支持的size和nblocks都更新了，支持的最大文件长度为16523个sectors。

# 源代码

//fs.c

static uint
bmap(struct inode ip, uint bn)
{
uint addr, a;
struct buf *bp;

if(bn < NDIRECT){
if((addr = ip->addrs[bn]) == 0)
ip->addrs[bn] = addr = balloc(ip->dev);
return addr;
}
bn -= NDIRECT;

if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
if((addr = ip->addrs[NDIRECT]) == 0)
ip->addrs[NDIRECT] = addr = balloc(ip->dev);
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
if((addr = a[bn]) == 0){
a[bn] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return addr;
}

//homework10
bn -= NINDIRECT;
if(bn < NDBINDIRECT){
if((addr = ip->addrs[NINDIRECT+1]) == 0)
ip->addrs[NINDIRECT+1] = addr = balloc(ip->dev);
bp = bread(ip->dev, addr);
a = (uint*)bp->data;
int first_block_index = bn/NINDIRECT;
if((addr = a[first_block_index]) == 0){
a[first_block_index] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);

bp = bread(ip->dev, addr);
a = (uint*)bp->data;
int second_block_index = bn%NINDIRECT;
if((addr = a[second_block_index]) == 0){
  a[second_block_index] = addr = balloc(ip->dev);
  log_write(bp);
} 
brelse(bp);
return addr;

}

panic(“bmap: out of range”);
}
`

笔记018 - HW9: Barriers

发表于 2017-08-20 | 分类于 MIT6.828 Operating System Engineering

题意

启动多个进程，每个进程执行20000个循环。对于每一个循环周期，确保多个进程都执行到同一个点，然后继续下一次循环。

解决思路

条件变量是利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待“条件变量的条件成立”而挂起；另一个线程使“条件成立”（给出条件成立信号）。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。

可参考的函数使用：

1
2
3

条件变量的使用：
pthread_cond_wait(&cond, &mutex);  // go to sleep on cond, releasing lock mutex
pthread_cond_broadcast(&cond);     // wake up every thread sleeping on cond

pthread_cond_wait会先解除之前的pthread_mutex_lock锁定的mutex，然后阻塞在等待对列里休眠，直到再次被唤醒（大多数情况下是等待的条件成立而被唤醒，唤醒后，该进程会先锁定先pthread_mutex_lock(&mtx);，再读取资源。

在barrier()函数中加入互斥锁和条件变量的控制：

static void 
barrier()
{
    pthread_mutex_lock(&bstate.barrier_mutex);
    bstate.nthread++;
    if(bstate.nthread != nthread){
      pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
      pthread_mutex_unlock(&bstate.barrier_mutex); 
    }else{
      pthread_cond_broadcast(&bstate.barrier_cond);
      bstate.round++;
      bstate.nthread = 0;
      pthread_mutex_unlock(&bstate.barrier_mutex);  
    }
}

bstate.nthread变量的累加用于决定：由最后一个进入barrier()的线程来进行broadcast。注意到pthread_cond_wait函数本身先释放锁、休眠、被唤醒、加锁的流程；执行broadcast之后，该线程会累加周期数bstate.round并清空bstate.nthread，然后释放锁，只有当该线程释放锁，其他线程才真正能在pthread_cond_wait中加锁。

编译并运行：

$ gcc -g -O2 -pthread barrier.c
$ ./a.out 2
``` 
{% asset_img 1.JPG 编译并运行 %}

# 源代码

#include <stdlib.h>

#include <unistd.h>

#include <stdio.h>

#include <assert.h>

#include <pthread.h>

// #define SOL

static int nthread = 1;
static int round = 0;

struct barrier {
pthread_mutex_t barrier_mutex;
pthread_cond_t barrier_cond;
int nthread; // Number of threads that have reached this round of the barrier
int round; // Barrier round
} bstate;

static void
barrier_init(void)
{
assert(pthread_mutex_init(&bstate.barrier_mutex, NULL) == 0);
assert(pthread_cond_init(&bstate.barrier_cond, NULL) == 0);
bstate.nthread = 0;
}

static void
barrier()
{
pthread_mutex_lock(&bstate.barrier_mutex);
bstate.nthread++;
if(bstate.nthread != nthread){
pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
pthread_mutex_unlock(&bstate.barrier_mutex);
}else{
pthread_cond_broadcast(&bstate.barrier_cond);
bstate.round++;
bstate.nthread = 0;
pthread_mutex_unlock(&bstate.barrier_mutex);
}
}

static void
thread(void xa)
{
long n = (long) xa;
long delay;
int i;

for (i = 0; i < 20000; i++) {
int t = bstate.round;
assert (i == t);
barrier();
usleep(random() % 100);
}
}

int
main(int argc, char argv[])
{
pthread_t tha;
void *value;
long i;
double t1, t0;

if (argc < 2) {
fprintf(stderr, “%s: %s nthread\n”, argv[0], argv[0]);
exit(-1);
}
nthread = atoi(argv[1]);
tha = malloc(sizeof(pthread_t) * nthread);
srandom(0);

barrier_init();

for(i = 0; i < nthread; i++) {
assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0);
}
for(i = 0; i < nthread; i++) {
assert(pthread_join(tha[i], &value) == 0);
}
printf(“OK; passed\n”);
}
`

查找

链表

排列/组合

设计模式

图

树

动态规划

数学算法

位运算

参考手册

基本概念

指针

内存布局

数组

c++

c++11

优化

预处理

函数区别

STL

混合编程

《5.1 Pointers and Addresses》

《5.2 Pointers and Function Argument》

《5.3 Pointers and Arrays》

《5.4 Address Arithmetic》

《5.5 Character Pointers and Functions》

练习

《2.9 Bitwise operators》

逻辑位移和算术位移

程序

《c和指针》部分抄录

结构体对齐原因

对齐的原则

为什么要设计内存对齐

设计结构体习惯

关于union大小的计算

File system preliminaries

On-Disk File System Structure

Sectors and Blocks

Superblocks

File Meta-data

Directories versus Regular Files

The File System

Disk Access

The Block Cache

The Block Bitmap

File Operations

The file system interface

Spawning Processes

Sharing library state across fork and spawn

The keyboard interface

The Shell

fd、dev、file

文件类型的交互

管道的交互

题意

解决思路

题意

解决思路