CSAPP-Lab1-DataLab环境部署及题解

计组 Lab 评论

1 介绍

该实验是《深入理解计算机系统》（英文缩写CSAPP）课程附带实验——Lab1：Data Lab。

大四下学期在做计组助教，需要部署Lab1，期间遇到了不少的问题，多亏了舍友的帮助，记录下。（🥦）

2 环境部署

部署时阅读README文件，包括子目录下的；项目使用Perl语言编写。

图片名称

2.1 网站运行

在项目主目录运行make start：

1
2
3
4
5
6
7
8
9
10
11
[root@VM-4-8-centos lab1]# sudo make start
######################################
# start Data lab Online contest
######################################
(cd contest; make start)
make[1]: Entering directory '/root/Lab/lab1/contest'
/bin/sh: ./contest-timer.pl: Permission denied
/bin/sh: ./contest.pl: Permission denied
make[1]: *** [Makefile:13: start] Error 1
make[1]: Leaving directory '/root/Lab/lab1/contest'
make: *** [Makefile:15: start] Error 2

出现报错，是因为pl脚本无执行权限，需要加权限：

1
2
cd ./contest
chmod +x *.pl

之后报错：

1
Can't locate CGI.pm in @INC (you may need to install the CGI module)

原因是缺少CGI模块，参考

1
sudo yum install perl-CGI

此时浏览器访问http://服务器IP:8080/，（注意服务器开启8080端口和8081端口)

1
2
3
4
Scoreboard for the Data Lab "Beat the Prof" Contest
Warning: The instructor (Tiger) must submit an entry before the results of the contest can be displayed.

To submit your instructor's entry: linux> ./src/driver.pl -u "The Prof"

这时候我们需要在后台执行提示的命令：

1
2
[root@VM-4-8-centos lab1]# ./src/driver.pl -u "The Prof"
-bash: ./src/driver.pl: Permission denied

报错显示需要加权限：

1
2
cd /root/Lab/lab1/src
chmod +x *.pl

之后再次报错：

1
2
3
[root@VM-4-8-centos lab1]# ./src/driver.pl -u "The Prof"
Can't locate Driverlib.pm in @INC (you may need to install the Driverlib module) (@INC contains: . /usr/local/lib64/perl5 /usr/local/share/perl5 /usr/lib64/perl5/vendor_perl /usr/share/perl5/vendor_perl /usr/lib64/perl5 /usr/share/perl5) at ./src/driver.pl line 19.
BEGIN failed--compilation aborted at ./src/driver.pl line 19.

这里的显示Driverlib.pm不存在，将往年Lab中的该文件复制到/usr/lib64/perl5（可变，只要在报错提示中的@INC中即可），然后再次执行：

1
2
3
4
5
[root@VM-4-8-centos lab1]# ./src/driver.pl -u "The Prof"
Can't locate Driverhdrs.pm in @INC (you may need to install the Driverhdrs module) (@INC contains: . /usr/local/lib64/perl5 /usr/local/share/perl5 /usr/lib64/perl5/vendor_perl /usr/share/perl5/vendor_perl /usr/lib64/perl5 /usr/share/perl5) at /usr/lib64/perl5/Driverlib.pm line 13.
BEGIN failed--compilation aborted at /usr/lib64/perl5/Driverlib.pm line 13.
Compilation failed in require at ./src/driver.pl line 20.
BEGIN failed--compilation aborted at ./src/driver.pl line 20.

Driverhdrs.pm文件与上面的Driverlib.pm文件同理，再次执行：

1
2
[root@VM-4-8-centos lab1]# ./src/driver.pl -u "The Prof"
./src/driver.pl: ERROR: No executable dlc binary.

进入src子目录下执行，出现报错：参考

1
2
[root@VM-4-8-centos src]# ./driver.pl -u "The Prof"
fatal error: gnu/stubs-32.h: No such file or directory" but stubs-64.h is present
1
sudo yum -y install glibc-devel.i686 glibc-devel

之后就可以成功执行了，但是前端页面仍然不变，需要提交如下指令：（非常坑，还是看文档不仔细，🥦

1
[root@VM-4-8-centos src]# ./driver.pl -u "Tiger"

在配置文件./contest/Contest.pm中可以查看：

1
2
3
4
5
6
$SERVER_NAME = "10.0.2.15";  # 需要修改成自己的服务器
$BASE_USERID = "Tiger";  # 初始用户名
$UPDATE_PERIOD = 10;  # 每10s刷新数据
$REQUESTD_PORT = 8080;  # Request server's port
$RESULTD_PORT = 8081;   # Result server's port
# ... 还有好多其他配置信息

到此前端可以正常显示了。

2.2 出题

具体操作参考./src/dlcdir/README

  1. ./src/puzzles目录下存放试题，新出的题目需要放在此处，由于本次实验出题主要更改原试题的名称，比较简单，魔改即可（包括文件名、函数名、注释等）

  2. 将新出的题目名称添加到./src/dlcdir/legallist.c中的legallist中，魔改：

    1
    {{"isZero"}, 0, 3, {'~', '&', '!', '^', '|', '+', LS, RS, 0}},

  3. 然后在./src/dlcdir目录下重新编译：

    1
    2
    make superclean
    make

  4. 此时如果成功执行，./src/dlcdir目录下会生成dlc可执行文件，并将其复制到上级目录中；

  5. 在./src/selections.c文件中存有你要选择出题的题目列表，默认13个，根据需求进行修改。

下面是make过程中出现的报错记录：

1
2
3
4
[root@VM-4-8-centos dlcdir]# make
bison -y -dv ANSI-C.y
make: bison: Command not found
make: *** [Makefile:40: y.tab.h] Error 127

原因是未安装bison，进行安装：参考

1
yum install -y bison

然后继续报错：

1
2
3
4
5
6
7
8
9
10
11
12
[root@VM-4-8-centos dlcdir]# make
bison -y -dv ANSI-C.y
ANSI-C.y:653.15-16: error: $$ for the midrule at $4 of ‘declaring.list’ has no declared type
              $$ = AppendDecl($1, $3, Redecl);
               ^^
ANSI-C.y:708.15-16: error: $$ for the midrule at $4 of ‘default.declaring.list’ has no declared type
             { $$ = AppendDecl($1, $3, NoRedecl); }
               ^^
ANSI-C.y:1408.14-15: error: $$ for the midrule at $3 of ‘labeled.statement’ has no declared type
            { $$ = BuildLabel($1, NULL); }
              ^^
make: *** [Makefile:40: y.tab.h] Error 1

原因是bison版本太新，需要更换版本：参考

查看版本：

1
2
3
4
5
6
7
[root@VM-4-8-centos dlcdir]# bison -V
bison (GNU Bison) 3.0.4
Written by Robert Corbett and Richard Stallman.

Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

删除bison：

1
yum remove bison.x86_64

下面更换bison版本：参考

  1. 下载bison的压缩包，版本要低于1.75，链接

  2. 安装：

    1
    2
    3
    4
    cd bison-x.x
    ./configure
    make
    sudo make install

bison版本正确后，下面继续做make，但是报了一大堆warning，然后报错：

1
2
3
4
5
6
7
heap.h:69:21: warning: inline function ‘HeapAllocate’ declared but never defined
 GLOBAL inline void *HeapAllocate(int number, int size);
...
/root/Lab/lab1/src/dlcdir/check.c:339: undefined reference to `MakeConstSlong'
/root/Lab/lab1/src/dlcdir/check.c:339: undefined reference to `MakeReturnCoord'
collect2: error: ld returned 1 exit status
make: *** [Makefile:36: dlc] Error 1

注意：这里搜索最后的报错部分无果，搜索warning部分可以解决。

这是内联函数inline引发的warning，添加编译选项-fgnu89-inline来修复，修改./src/Makefile，参考

1
_CFLAGS = -g  -O2 -fgnu89-inline

下面继续编译，之前需要清理下：

1
2
make clean
make

现在就可以成功编译了，但是此时是dlc是64位可执行程序，在我们学生默认的32位debian虚拟机是无法运行的：

1
2
3
4
liuzhenlong@debian:~/Lab_new/lab1-handout$ ./dlc bits.c
-bash: ./dlc: cannot execute binary file: Exec format error
liuzhenlong@debian:~/Lab_new/lab1-handout$ file dlc
dlc: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=1dcd289bac34aee0dde34abd43a959588d79b382, with debug_info, not stripped

所以需要修改成32位编译：参考

1
_CFLAGS = -g  -O2 -fgnu89-inline -m32

下面继续编译，之前需要清理下：

1
2
3
4
make clean
make 
liuzhenlong@debian:~/Lab_new/lab1-handout$ file dlc
dlc: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=ec898c28449afe1d16254e2cbe67617c1874b026, with debug_info, not stripped

现在dlc可执行程序已经生成。

2.3 导出实验

在项目主目录下执行：

1
2
3
4
5
6
7
8
9
10
11
[root@VM-4-8-centos lab1]# make all
[root@VM-4-8-centos lab1]# ll
total 1232
drwxr-xr-x 2 root root    4096 Apr  9 22:20 contest
drwxr-xr-x 4 root root    4096 Apr  8 10:58 grade
drwxr-xr-x 2 root root    4096 Apr 13 00:13 lab1-handout
-rw-r--r-- 1 root root 1228800 Apr 13 00:13 lab1-handout.tar
-rw-r--r-- 1 root root    2436 Apr  7 23:06 Makefile
-rw-r--r-- 1 root root    8097 Apr  7 23:06 README
drwxr-xr-x 5 root root    4096 Apr 13 00:13 src
drwxr-xr-x 2 root root    4096 Apr  7 23:04 writeup

lab1-handout.tar是生成的实验，将其分发给同学们即可进行实验了。

3 题解

3.1 lsbZero.c

注释：

1
2
3
4
5
6
7
/*
 *   lsbZero - set 0 to the least significant bit of x
 *   Example: lsbZero(0x87654321) = 0x87654320
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 1
 */

题目：

给定一个int型整数x，将其最低一位有效位置0。

  • 例如：lsbZero(0x87654321) = 0x87654320

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 法1（标准答案-3'）
/* */
int lsbZero(int x) {
  return (x | 1) + ~0;
}

// 法2（目前最佳答案-2'）
/* 右移一位再左移一位实现把最低一位有效位置0 */
int lsbZero(int x) {
  return x >> 1 << 1;
}

// 法3（来自学生-2'）
/* 和 0xfffffffe 相与即可 */
int lsbZero(int x) {
  return x & (~1);
}

3.2 byteNot.c

注释：

1
2
3
4
5
6
7
8
/*
 *   byteNot.c - bit-inversion to byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByteNot(0x12345678,1) = 0x1234A978
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */

题目：

给定一个int型整数x，将其第n个字节实现取反。

  • 例如：byteNot(0x12345678,1) = 0x1234A978

实现：

1
2
3
4
5
6
7
8
9
// 法1（标准答案-3'）
/* 将0xFF移动到对应字节，然后取按位异或 */
int nuaa_question2(int x, int n) {
  /* Shift x n*8 positions right */
  int shift = n << 3;
  /* Mask byte */
  int mask = 0xFF << shift;
  return x ^ mask;
}

3.3 byteXor.c

注释：

1
2
3
4
5
6
7
8
/*
 *   byteXor - compare the nth byte of x and y, if it is same, return 0, if not, return 1
 *   example: byteXor(0x12345678, 0x87654321, 1) = 1
 *            byteXor(0x12345678, 0x87344321, 2) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 2
 */

题目：

给定三个int整数 x 、 y和 n ，比较 x 和 y 的第 n 字节，如果相同则返回 0 ，不同则返回 1。

  • 例如：byteXor(0x12345678, 0x87654321, 1) = 1
  • 例如：byteXor(0x12345678, 0x87344321, 2) = 0

实现：

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
// 法1（标准答案-9'）
/* 移位取指定字节，异或，两次取逻辑非 */
int byteXor(int x, int y, int n) {
  int shift = n << 3;
  int xs = x >> shift;
  int ys = y >> shift;
  int cmp = (xs & 0xFF) ^ (ys & 0xFF);
  return !!cmp & 1 ;
}

// 法2（目前最佳答案-8'）
/* 法1最后的&1是多余的操作 */
int byteXor(int x, int y, int n) {
  int shift = n << 3;
  int xs = x >> shift;
  int ys = y >> shift;
  int cmp = (xs & 0xFF) ^ (ys & 0xFF);
  return !!cmp;
}

// 法3（来自学生-6'）
/* 把⽬标位移到最低位然后⽤异或⽐较⼀下是否相等即可 */
int lsbZero(int x) {
    _ = n << 3;
  __ = ((x ^ y) >> _) & 0xff;
  return !!(__);
}

3.4 logicalAnd

注释：

1
2
3
4
5
6
/*
 *   logicalAnd - x && y
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */

题目：

实现逻辑与&&，当两个操作数都是ture的时候，才返回true，否则返回false。

  • 例如：logicalAnd(1, 0) = 0
  • 例如：logicalAnd(2, 3) = 1

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 法1（标准答案-8'）
/* */
int logicalAnd(int x, int y) {
  int z = ~!x & ~!y;
  return ~(z + 1) & 1;
}

// 法2（其他思路-5'）
/* 把x和y分别转换为逻辑的0和1，再相与 */
int logicalAnd(int x, int y) {
   return (!(!x))&(!(!y));
}

// 法3（目前最佳答案-4'）
/* 把x和y分别取NOT，二者相或后再取NOT，即可得到逻辑与 */
int logicalAnd(int x, int y) {
   return !((!x)|(!y));
}

3.5 logicalOr

注释：

1
2
3
4
5
6
/*
 *   logicalOr - x || y
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */

题目：

实现逻辑或||，当两个操作数有一个为ture的时候，就返回true。

  • 例如：logicalOr(0, 0) = 0
  • 例如：logicalOr(2, 0) = 1

实现：

1
2
3
4
5
6
7
8
9
10
11
// 法1（标准答案）
/* */
int logicalOr(int x, int y) {
  return ~(!x & !y) & 1;
}

// 法2（目前最佳答案）
/* 把x和y分别转换为逻辑的0和1，再相或 */
int logicalOr(int x, int y) {
  return (!(!x))|(!(!y));
}

3.6 rotateLeft

注释：

1
2
3
4
5
6
7
8
/*
 *   rotateLeft - Rotate x to the left by n
 *   Can assume that 0 <= n <= 31
 *   Examples: rotateLeft(0x87654321,4) = 0x76543218
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 25
 *   Rating: 3
 */

题目：

给定一个int型整数x，实现循环左移，也就是把x的前n位移到末尾。

  • 例如：rotateLeft(0x87654321,4) = 0x76543218

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 法1（标准答案-16'）
/* */
int rotateLeft(int x, int n) {
    /* Create mask for n = 0 */
    int zmask = (~!n)+1;
    int left = x << n;
    /* Arithmetic shift right by 32-n */
    int right = x >> (33 + ~n);
    /* Mask off upper 1's */
    int lmask = ~0 << n;
    right &= ~lmask;
    return (zmask&x) | (~zmask&(left|right));
}

// 法2(其他方法-10’)
/* 先构造y为高（32-n）位为0的y，再与x右移（32-n）的x相与，相当于储存了x的高n位数，最后再与x左移n位相加即可。 */
int rotateLeft(int x, int n) {
    int y;
    y=~((~0)<<n);
    x=(x<<n)+((x>>(32+(~n+1)))&y);
    return x;
}

3.7 float_abs.c

注释：

1
2
3
4
5
6
7
8
9
10
11
/*
 *   float_abs - Return bit-level equivalent of absolute value of f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument..
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */

题目：

给予⼀个无符号整数表示的浮点数 uf (你可以认为 uf 具有浮点数的比特级结构) ，函数返回它的绝对值，即 |uf| (返回的结果也是⼀个无符号整数表示的浮点数)，如果这个数是 NaN ，请返回它本身。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 法1（标准答案）
/* */
unsigned float_abs(unsigned uf) {
  unsigned mask = 1 << 31;
  unsigned abs = uf & ~mask;
  if (abs > 0x7F800000)
    return uf;
  return abs;
}

// 法2（目前最佳答案）
/* https://blog.csdn.net/qq_43544682/article/details/102874816 */
unsigned float_abs(unsigned uf) {
    int x=uf&0x7fffffff;
    if(x>0x7f800000)
        return uf;//NaN
    else
        return x;
}

3.8 float_f2i

注释：

1
2
3
4
5
6
7
8
9
10
11
12
/*
 *   float_f2i - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */

题目：

给予⼀个无符号整数表示的浮点数 uf (你可以认为 uf 具有浮点数的比特级结构) ，函数返回它对应的强制类型转换后的整数（具有整数的比特级结构），即实现表达式 (int)uf ，如果这个数超过整数表示的范围（包括 NaN 和无穷），请返回 0x80000000u。

实现：

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
// 法1（标准答案）
/* */
int float_f2i(unsigned uf) {
  unsigned sign = uf >> 31;
  unsigned exp = (uf >> 23) & 0xFF;
  unsigned frac = uf & 0x7FFFFF;
  /* Create normalized value with leading one inserted,
     and rest of significand in bits 8--30.
  */
  unsigned val = 0x80000000u + (frac << 8);
  if (exp < 127) {
    /* Absolute value is < 1 */
    return 0;
  }
  if (exp > 158)
    /* Overflow */
    return 0x80000000u;
  /* Shift val right */
  val = val >> (158 - exp);
  /* Check if out of range */
  if (sign) {
    /* Negative */
    return val > 0x80000000u ? 0x80000000u : -val;
  } else {
    /* Positive */
    return val > 0x7FFFFFFF ? 0x80000000u : val;
  }
}

// 法2（目前最佳答案）
/*  */

4 其他

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
liuzhenlong@debian:~/Lab_new/lab1-handout$ ./driver.pl
1. Running './dlc -z' to identify coding rules violations.

2. Compiling and running './btest -g' to determine correctness score.
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
btest.c: In function ‘test_function’:
btest.c:332:23: warning: ‘arg_test_range[1]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (arg_test_range[1] < 1)
         ~~~~~~~~~~~~~~^~~

3. Running './dlc -Z' to identify operator count violations.

4. Compiling and running './btest -g -r 2' to determine performance score.
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
btest.c: In function ‘test_function’:
btest.c:332:23: warning: ‘arg_test_range[1]’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (arg_test_range[1] < 1)
         ~~~~~~~~~~~~~~^~~


5. Running './dlc -e' to get operator count of each function.

运行./driver.pl会报warning，批改学生作业时，有一个同学提出了解答：👍

关于 ./driver.pl 中的预警问题，是因为 ./btest.c 在299行申请的变量没有进行初始化赋值，后面的程序检测到这个位置可能会被访问而提出的预警，给其付个初始值即可解决

X 参考

Dragon's BlogsDevelopment

Life is painting a picture, not doing a sum.