cs61c-lab01

Lab1: Number Rep, C and CGDB

cs61c - Great Ideas in Computer Architecture (Machine Structures) lab 笔记第一篇

课程主页：https://inst.eecs.berkeley.edu/~cs61c/fa20/#by-week

个人仓库：https://github.com/2333monster/my-cs61c-lab

参考

gdb调试手册：https://blog.nowcoder.net/n/1957d46e0ee34168aee2289faf36ee5c#gdb_20

gdb调试指南：https://www.yanbinghu.com/2019/04/20/41283.html

Setup

获得skeleton code

1
2
$ git remote add starter https://github.com/61c-teach/fa20-lab-starter.git
$ git pull starter master

Compiling and Running a C Program

使用gcc 编译c程序，生成执行文件

1
$ gcc hello.c

使用执行文件a.out的名称运行c程序

1
$ ./a.out

或者使用-o命令，它能指定执行文件的名称

1
2
$ gcc -o hello hello.c
$ ./hello

Exercise 1: See what you can C

本练习中，将看到宏定义处理器的示例

更改V0 ~ V3 的宏定义，使其输出以下内容

1
2
3
4
5
Berkeley eccentrics:
====================
Happy Happy Happy
Yoshua
Go BEARS!

更改后（好像不要求完全不同，完全不同确实写不出来）

1
2
3
4
#define V0 2
#define V1 3
#define V2 3
#define V3 1

Exercise 2: Catch those bugs!

使用GDB进行Debug，GDB reference card

GDB stands for “GNU De-Bugger.”

使用-g调用 (c)gdb 

1
$ gcc -g -o hello hello.c

这会生成一个可被gdb识别的可执行文件

1
$ gdb hello

gdb常用调试指令

调试指令 作用
b（break） 行号 在源代码指定的某一行设置断点，其中行号用于指定具体打断点的位置。
r（run） 执行被调试的程序，其会自动在第一个断点处暂停执行。
n（next）(int) 令程序一行代码一行代码的执行。执行n次
p（print） 变量名 打印指定变量的值
l（list） 显示源程序代码的内容，包括各行代码所在的行号。
q（quit） 终止调试。

断点设置格式

1
2
(gdb) break location    //b 位置
(gdb) break ... if cond //b 表达式
  • location
location 的值 含 义
linenum linenum 是一个整数，表示要打断点处代码的行号。
filename:linenum filename 表示源程序文件名；linenum 为整数，表示具体行数。整体的意思是在指令文件 filename 中的第 linenum 行打断点。
+ offset offset 为整数，+offset 表示以当前程序暂停位置为准，向后数 offset 行处打断点
- offset offset 为整数，-offset 表示以当前程序暂停位置为准，向前数 offset 行处打断点
function function 表示程序中包含的函数的函数名，即 break 命令会在该函数内部的开头位置打断点，程序会执行到该函数第一行代码处暂停。
filename:function filename 表示远程文件名；function 表示程序中函数的函数名。整体的意思是在指定文件 filename 中 function 函数的开头位置打断点。
  • cond 表达式
1
(gdb) b 7 if num>10  //如果num>10 在第 7 行打断点

Action Item

  1. setting a breakpoint at main
1
(gdb) b hello.c: main
  1. using gdb’s run command
1
run
  1. using gdb’s single-step command
1
n

gdb questions

  1. While you’re in a gdb session, how do you set the arguments that will be passed to the program when it’s run?

    1
    set args 5

  2. How do you create a breakpoint?

    1
    b filename: linenum

  3. How do you execute the next line of C code in the program after stopping at a breakpoint?

    1
    n(next) / s(step)

  4. If the next line of code is a function call, you’ll execute the whole function call at once if you use your answer to #3. (If not, consider a different command for #3!) How do you tell GDB that you want to debug the code inside the function (i.e. step into the function) instead? (If you changed your answer to #3, then that answer is most likely now applicable here.)

    1
    step

  5. How do you continue the program after stopping at a breakpoint?

    1
    run

  6. How can you print the value of a variable (or even an expression like 1+2) in gdb?

    1
    2
    p 1+2
    p variable_name

  7. How do you configure gdb so it displays the value of a variable after every step?

    1
    display variable

  8. How do you show a list of all variables and their values in the current function?

    1
    info args

  9. How do you quit out of gdb?

    1
    q

Exercise 3: Debugging w/ YOU(ser input)

好像是关于redirection ，没懂

Exercise 4: Valgrind’ing away

有两种bug类型

  1. bohrbugs：在一致的稳定的情况下会重复出现的错误
  2. heisenbugs：在相同情况下不一定会重复出现，一般由于内存管理不当

使用Valgrind 找出”heisenbugs”

To help catch these “heisenbugs” we will use a tool called Valgrind. Valgrind is a program which emulates your CPU and tracks your memory accesses. This slows down the process you’re running (which is why we don’t, for example, always run all executables inside Valgrind) but also can expose bugs that may only display visible incorrect behavior under a unique set of circumstances.

安装valgrind （在ubuntu环境下）

1
$ sudo apt install valgrind

segfault_ex 出现错误的原因

1
2
3
4
5
6
int main() {
    int a[20];
    for (int i = 0; ; i++) {
        a[i] = i;
    }
}

访问数组外未定义的内存，典型的heisenbug。

使用valgrind

1
2
$ gcc -o segfault_ex.exe segfault_ex.c
$ valgrind ./segfault_ex.exe

输出结果：

1
2
3
==15931== 	Invalid write of size 4
==15931==   at 0x10914F: main (in /home/moxilai/cs61c-lab/lab01/segfault.exe)
==15931== 		Address 0x1fff001000 is not stack'd, malloc'd or (recently) free'd

no_segfalut 的问题

1
2
3
4
5
6
7
8
9
#include <stdio.h>
int main() {
    int a[5] = {1, 2, 3, 4, 5};
    unsigned total = 0;
    for (int j = 0; j < sizeof(a); j++) {
        total += a[j];
    }
    printf("sum of array is %d\n", total);
}

for (int j = 0; j < sizeof(a); j++) 使用sizeof(a) a 是一个包含五个元素的整型数组，sizeof的结果是5*4=20，而不是5，导致访问未定义的内存，从而产生未知的结果。这是一个典型的Heisenbug问题，因为其结果取决于内存中未定义的值，可能会导致程序崩溃或输出错误的结果。

使用valgrind

1
2
$ gcc -o no_segfault.exe no_segfault_ex.c
$ valgrind ./no_segfault.exe

结果

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
==16089== Conditional jump or move depends on uninitialised value(s)
==16089==    at 0x48D9B56: __vfprintf_internal (vfprintf-internal.c:1516)
==16089==    by 0x48C381E: printf (printf.c:33)
==16089==    by 0x1091E7: main (in /home/moxilai/cs61c-lab/lab01/no_segfault.exe)
==16089==
==16089== Use of uninitialised value of size 8
==16089==    at 0x48BD33B: _itoa_word (_itoa.c:177)
==16089==    by 0x48D8B3D: __vfprintf_internal (vfprintf-internal.c:1516)
==16089==    by 0x48C381E: printf (printf.c:33)
==16089==    by 0x1091E7: main (in /home/moxilai/cs61c-lab/lab01/no_segfault.exe)
==16089==
==16089== Conditional jump or move depends on uninitialised value(s)
==16089==    at 0x48BD34C: _itoa_word (_itoa.c:177)
==16089==    by 0x48D8B3D: __vfprintf_internal (vfprintf-internal.c:1516)
==16089==    by 0x48C381E: printf (printf.c:33)
==16089==    by 0x1091E7: main (in /home/moxilai/cs61c-lab/lab01/no_segfault.exe)
==16089==
==16089== Conditional jump or move depends on uninitialised value(s)
==16089==    at 0x48D9643: __vfprintf_internal (vfprintf-internal.c:1516)
==16089==    by 0x48C381E: printf (printf.c:33)
==16089==    by 0x1091E7: main (in /home/moxilai/cs61c-lab/lab01/no_segfault.exe)
==16089==
==16089== Conditional jump or move depends on uninitialised value(s)
==16089==    at 0x48D8C85: __vfprintf_internal (vfprintf-internal.c:1516)
==16089==    by 0x48C381E: printf (printf.c:33)
==16089==    by 0x1091E7: main (in /home/moxilai/cs61c-lab/lab01/no_segfault.exe)

关键词：uninitialised value

分析上面两个程序

  1. Why didn’t the no_segfault_ex program segfault?
    首先c以这种形式分配数组内存是stack中给了一个指针，随着j的增大，会访问a[5]~a[19]这实际是a+5 ~ a+19 的内存，这些内存是存在的，由于这不是分配给a 的内存，且没有初始化，其中会存储着脏数据，导致不可确定的。不过由于没有超出stack的容量，不会造成segfault（程序崩溃）

  2. Why does the no_segfault_ex produce inconsistent outputs?
    同上，不确定的数据导致不确定的输出

  3. Why is sizeof incorrect? How could you still use sizeof but make the code correct?
    同上，更改

    1
    2
    3
    4
    ...
    arraylength = sizeof(a)/sizeof(a[0]);
    for(int j=0;j<arraylength;j++)
        ...

Exercise 5: Pointers and Structures in C

在ll_cycle.c中，完成函数ll_has_cycle()来实现以下检查单向链表是否有环的算法。

  1. Start with two pointers at the head of the list. We’ll call the first one tortoise and the second one hare.
  2. Advance hare by two nodes. If this is not possible because of a null pointer, we have found the end of the list, and therefore the list is acyclic.
  3. Advance tortoise by one node.
  4. If tortoise and hare point to the same node, the list is cyclic. Otherwise, go back to step 2.

ll_cycle.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stddef.h>
#include "ll_cycle.h"

int ll_has_cycle(node *head) {
    /* your code here */
    if(head == NULL){
        return 0;
    }
    node *tortoise = head;
    node *hare = head->next;
    while(tortoise != NULL && hare != NULL && hare->next != NULL){
        if(tortoise == hare){
            return 1;
        }
        tortoise = tortoise->next;
        hare = hare->next->next;
    }   
    return 0;
}

解释算法原理Wikipedia article

Architecture
#cs61c
cs61c-lab01
https://2333monster.github.io/2023/08/04/cs61c-lab01/
作者
John Titor
发布于
2023年8月4日
许可协议