Lab5-1课上实验

exam

// fs.h
// 1st part
int time_read();
// 2nd part
void raid0_write(u_int secno, void *src, u_int nsecs);
void raid0_read(u_int secno, void *dst, u_int nsecs);

第一部分获取系统时间

这一部分较为简单，与ide_read, ide_write思路相同，都是调用syscall_read_dev, syscall_write_dev这两个函数，对设备的相关地址进行读写。

int time_read() {
    int ret, update = 0, time;

    ret = syscall_read_dev(&time, 0x15000010, 4);
    // 这里用了循环是因为题目中说到获取的时间可能“始终”为0
    // 也许一次更新就行了，上机时没试过
    while(ret == 0 && time == 0) {
        ret = syscall_write_dev(&update, 0x15000000, 4);
        if(ret < 0)
            user_panic("time_read error!");
        ret = syscall_read_dev(&time, 0x15000010, 4);
    }
    if(ret < 0) user_panic("time_read error!");
    if(time) return time;
    else user_panic("time_read error!");
}

第二部分简易磁盘阵列

这部分两个函数主要是对ide_read, ide_write两个函数的调用，这也是后面Extra题目的基础level。

void raid0_write(u_int secno, void *src, u_int nsecs) {
    int curno = secno, endno = secno + nsecs, diskno;
    int offset = 0;
    while(curno < endno) {
        if(curno & 1) diskno = 2;
        else diskno = 1;
        ide_write(diskno, curno / 2, src + offset, 1);
        curno++;
        offset += 0x200;
    }
}

void raid0_read(u_int secno, void *dst, u_int nsecs) {
    int curno = secno, endno = secno + nsecs, diskno;
    int offset = 0;
    while(curno < endno) {
        if(curno & 1) diskno = 2;
        else diskno = 1;
        ide_read(diskno, curno / 2, dst + offset, 1);
        curno++;
        offset += 0x200;
    }
}

Extra

// fs.h
int raid4_valid(u_int diskno);
int raid4_write(u_int blockno, void *src);
int raid4_read(u_int blockno, void *dst);

前面第二部分的进阶版，个人觉得主要难点在于校验码的读取，计算与比较。

大致思路

先根据题目背景理清磁盘的结构：

用 $B_i$ 表示第 $i$ 个数据块，其中 $i\geq 0$
用 $D_{j-k}$ 表示第 $j$ 个磁盘的第 $k$ 个扇区，其中 $j=1,2,3,4,5;k \geq 0$
磁盘由多个扇区构成(在题目图中扇区画成了圆柱体，也许有点容易误解)，每个磁盘中扇区的编号 $k$ 与数据块编号 $i$ 的关系为 $i=floor(k/2)$
前四个磁盘中，每两个扇区同属一块数据块，这样一共八个扇区构成了一个完整的数据块
第五个磁盘中，每个扇区存储的是校验码，由前四个磁盘中 $k$ 值相同的扇区里的数据异或得到
通过计算我们可以得到，每一个扇区大小为512字节，即128个int型数据，这部分数据可以用int data[8][128]这样一个二维数组表示；而校验码则可以用int check[2][128]这样一个二维数组表示(这是我看了提供的Extra测试程序后才明白的，对于理清思路以及后面计算校验码还是挺有帮助的)
因此用int **data统一代指题目中的参数src, dst，那么对于 $D_{j-k}, j \leq 4$
- 若k&1=0，则该扇区对应的内存首地址int *entry = *(data + (j - 1) * 128)，即data[j-1]；
  
  否则，其对应的内存首地址为entry = *(data + (j - 1) * 128 + halfpg / 4)，即data[j-1+4]，
  
  其中halfpg = 0x800 = 128 * 4 * 4，这里对应的内存地址也就是我们与磁盘交互时写入或者读出的内存虚地址
- 那么确定完首地址后，我们可以把其看成一个长度为128的int型一维数组，再去读取其中第 $n$ 个整数时，只需要用*(entry + n)，其中 $0\leq n < 128$

其余注意事项：

由于data区域是一个页大小，实际上是没有内存空间给到第五个磁盘的，所以在读取和写入时，都是在函数内部开局部数组，这个在注意事项中也有提到
对于单个非校验码磁盘损坏恢复数据时，我的思路是先记下损坏磁盘的编号invalid，然后将五个磁盘读取的数据都异或一遍，其中有一块损坏了，那么并没有真正读取其内部的数据，在对应内存的数据是不确定的，不过不影响，再异或一遍损坏磁盘对应内存的数据。由于两个相同值异或结果为0，而所有数异或上0还是本身，这样就可以计算出正确值了

源代码

与上述思路有所出入，在读取单个整数时可以优化如思路所说，但是考试时来不及了…

int raid4_valid(u_int diskno) {
    int ret;
    int offset = 0, read = 0;
    ret = syscall_write_dev(&diskno, 0x13000010, 4);
    if(ret < 0) user_panic("raid4_valid error!");

    ret = syscall_write_dev(&offset, 0x13000000, 4);
    if(ret < 0) user_panic("raid4_valid error!");

    ret = syscall_write_dev(&read, 0x13000020, 4);
    if(ret < 0) user_panic("raid4_valid error!");

    if(syscall_read_dev(&ret, 0x13000030, 4) < 0)
        user_panic("raid4_valid error!");

    return ret;
}

int raid4_write(u_int blockno, void *src) {
    int res = 0;    // invalid num
    int offset = 0, diskno = 1, halfpg = 0x800; 
    int check[2][128], i;
    while (diskno <= 4)
    {
        if(raid4_valid(diskno)) {
            ide_write(diskno, 2 * blockno, src + offset, 1);
            ide_write(diskno, 2 * blockno + 1, src + offset + halfpg, 1);
        } else res++;
        diskno++;
        offset += 0x200;
    }
    if(raid4_valid(diskno)) {
        user_bzero(check, 1024);
        for(i = 0; i < 128; i++) {
            check[0][i] = *(int *)(src + 4 * i);
            check[1][i] = *(int *)(src + halfpg + 4 * i);
            for(offset = 0x200; offset < 0x800; offset += 0x200) {
                check[0][i] ^= *(int *)(src + offset + 4 * i);
                check[1][i] ^= *(int *)(src + offset + halfpg + 4 * i);
            }
        }
        ide_write(diskno, 2 * blockno, (void *)check[0], 1);
        ide_write(diskno, 2 * blockno + 1, (void *)check[1], 1);
    } else res++;
    return res;
}

int raid4_read(u_int blockno, void *dst) {
	int res = 0;	// invalid num
	int invalid = 0;
	int offset = 0, diskno = 1, halfpg = 0x800; 
	int check[2][128], i;
	int check0, check1;
	while (diskno <= 5) {
		if(!raid4_valid(diskno)) res++;
		diskno++;
	}
	if(res > 1) return res;
	else {
        // 读取前四块磁盘数据
        diskno = 1;
		while (diskno <= 4)
		{
			if(raid4_valid(diskno)) {
				ide_read(diskno, 2 * blockno, dst + offset, 1);
				ide_read(diskno, 2 * blockno + 1, dst + offset + halfpg, 1);
			} else invalid = diskno;
			diskno++;
			offset += 0x200;
		}
		if(res == 1 && invalid == 0) return 1;	// invalid为0说明是5号磁盘损坏，可以直接返回1
		else {
			user_bzero(check, 1024);
            // 读取第五块磁盘数据到局部数组
			ide_read(diskno, 2 * blockno, (void *)check[0], 1);
			ide_read(diskno, 2 * blockno + 1, (void *)check[1], 1);
			if(res == 0) {
				for(i = 0; i < 128; i++) {
					check0 = *(int *)(dst + 4 * i);
					check1 = *(int *)(dst + halfpg + 4 * i);
					for(offset = 0x200; offset < 0x800; offset += 0x200) {
						check0 ^= *(int *)(dst + offset + 4 * i);
						check1 ^= *(int *)(dst + offset + halfpg + 4 * i);
					}
					if(check0 != check[0][i] || check1 != check[1][i]) return -1;
				}
				return 0;
			} else {
				for(i = 0; i < 128; i++) {
					check0 = check[0][i];
					check1 = check[1][i];
					for(offset = 0; offset < 0x800; offset += 0x200) {
						check0 ^= *(int *)(dst + offset + 4 * i);
						check1 ^= *(int *)(dst + offset + halfpg + 4 * i);
					}
					check0 ^= *(int *)(dst + (invalid - 1) * 0x200 + 4 * i);
					check1 ^= *(int *)(dst + (invalid - 1) * 0x200 + halfpg + 4 * i);
					*(int *)(dst + (invalid - 1) * 0x200 + 4 * i) = check0;
					*(int *)(dst + (invalid - 1) * 0x200 + halfpg + 4 * i) = check1;
				}
				return 1;
			}
		}
	}
}

优化

如果按照思路所写，那么也许可以优化成以下这样(没提交过，咱也不确定)

// 以raid4_write为例
int raid4_write(u_int blockno, void *src) {
    int res = 0;    // invalid num
    int offset = 0, diskno = 1, halfpg = 0x800; 
    int check[2][128], i, j;
    int (*data)[][128] = src;
	while (diskno <= 4)
	{
		if(raid4_valid(diskno)) {
			ide_write(diskno, 2 * blockno, src + offset, 1);
			ide_write(diskno, 2 * blockno + 1, src + offset + halfpg, 1);
		} else res++;
		diskno++;
		offset += 0x200;
	}
	if(raid4_valid(diskno)) {
		user_bzero(check, 1024);
		for(i = 0; i < 128; i++) {
			check[0][i] = (*data)[0][i];
			check[1][i] = (*data)[4][i];
			for(j = 1; j <= 3; j++) {
				check[0][i] ^= (*data)[j][i];
				check[1][i] ^= (*data)[4 + j][i];
			}
		}
		ide_write(diskno, 2 * blockno, (void *)check[0], 1);
		ide_write(diskno, 2 * blockno + 1, (void *)check[1], 1);
	} else res++;
	return res;
}

MOS

#MOS

Token Analysis Previous

第七次作业第4题 Next