Theoyu

『 CS61C 』 Labs

  • Theoyu
  • Sep 10, 2022

Lab 1: C & CGDB

Learning Goals

  1. 练习使用指针、字符串和结构体。
  2. 学会基础的调试技巧：编译警告消除、断言以及 GDB 。

Exercise 1 是一个 C 语言的 Warm Up，实现几个简易函数即可。

Exercise 2 需要我们使用 GDB，发现并修改程序中的一些逻辑 BUG，这里我使用的是 CGDB，相比于 GDB 来说可以更加方便的在源码上下断点跟进。

image-20220926083553611

注意，如果我们需要用 CGDB 在源码层面上进行调试，需要在编译时指定 -g 参数，gcc 会在编译时做以下额外操作：

  1. 创建调试符号表，符号表包含了程序中使用的变量名称等信息。
  2. 关闭所有的优化机制，以便程序严格按照源码流程执行。

下面是CGDB的一些常用指令

空格      断点
run r    运行
start    从第一行开始单步运行
next n   单步调试 F8
step s   进入内部 F10
until u  快速运行完循环、until localtion 运行到目的行
continue 运行到下一个断点 F6
finish   跳出当前栈帧 F7
info locals 打印本地变量
print p  显示变量
display  持续打印某个变量
watch 
o        打开文件列表

Exercise 3 还是对 CGDB 的练习，需要我们通过调试，找到并修改链表中的一个 segfaults （段错误）。

Exercise 4 需要我们实现一个链表有环的判断，用双指针即可。

int ll_has_cycle(node *head) {
    /* TODO: Implement ll_has_cycle */
    node * fast = head;
    node * slow = head;
    while (fast && fast->next){
        slow = slow ->next;
        fast = fast->next->next;
        if(fast == slow){
            return 1;
        }
    }
    return 0;
}

Lab 2: C Memory Management, Valgrind

Learning Goals

  1. 练习简单的位操作。
  2. 学会使用 Valgrind 进行内存泄漏检查。
  3. 练习编写安全的程序。

Exercise 1: Bit Operations

需要我们只通过简单的位运算符实现以下三个函数：

/* Returns the Nth bit of X. Assumes 0 <= N <= 31. */
unsigned get_bit(unsigned x, unsigned n) {
    /* YOUR CODE HERE */
    return -1; /* UPDATE WITH THE CORRECT RETURN VALUE*/
}

/* Set the nth bit of the value of x to v. Assumes 0 <= N <= 31, and V is 0 or 1 */
void set_bit(unsigned *x, unsigned n, unsigned v) {
    /* YOUR CODE HERE */
}

/* Flips the Nth bit in X. Assumes 0 <= N <= 31.*/
void flip_bit(unsigned *x, unsigned n) {
    /* YOUR CODE HERE */
}

这一关和 CSAPP 里位运算的那一个 lab 很类似，算是简化版，稍微想一下就能很快写出来。

Exercise 2: Valgrind

Valgrind 是一款用于程序调试和分析的开源工具，可以用于检测和追溯内存泄漏。

在编译时，指定 -g 参数，可有助于调试时定位到具体代码行，这里我们以一个创建链表为例：

int main(int argc, char **argv) {
      for (int i = 0; i < 5; ++i) {
        add_to_front(&head, i);
    }
}

运行 valgrind --leak-check=full ./linked_list

输出：

Congrats! All of the test cases passed!
==58781== 
==58781== HEAP SUMMARY:
==58781==     in use at exit: 80 bytes in 5 blocks
==58781==   total heap usage: 6 allocs, 1 frees, 1,104 bytes allocated
==58781== 
==58781== 80 (16 direct, 64 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==58781==    at 0x4849D8C: malloc (in /usr/lib/aarch64-linux-gnu/valgrind/vgpreload_memcheck-arm64-linux.so)
==58781==    by 0x1089BF: create_node (linked_list.c:8)
==58781==    by 0x108A67: add_to_front (linked_list.c:35)
==58781==    by 0x108C77: main (test_linked_list.c:14)
==58781== 
==58781== LEAK SUMMARY:
==58781==    definitely lost: 16 bytes in 1 blocks
==58781==    indirectly lost: 64 bytes in 4 blocks
==58781==      possibly lost: 0 bytes in 0 blocks
==58781==    still reachable: 0 bytes in 0 blocks
==58781==         suppressed: 0 bytes in 0 blocks
==58781== 
==58781== For lists of detected and suppressed errors, rerun with: -s
==58781== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

从上面信息可以定位到一共有 5 个内存泄漏点，其中 1 个为直接泄漏，即 head 指向的那一个节点；4 个为间接泄漏，即之后四个节点。

下面通过几个案例进一步学习 Valgrind的使用。

访问未初始化的内存：

int main(void){
    int *p;
    int a = *p;
}

image-20220927182400743

内存释放后读写

#include "malloc.h"
int main(void){
    int *a = malloc(sizeof(int));
    *a = 10;
    free(a);
    int *b = malloc(sizeof(int));
    *a = 20;
}

image-20220927195638840

动态内存越界读写

image-20220927201108831

double free

#include "malloc.h"
int main(void){
    int *p = malloc(0x4);
    free(p);
    free(p);
}

image-20220927202554310

Exercise 3: Memory Management

这部分需要我们补充一个缺陷的 vector，非常的基础，可以结合之前所学的 CGDB 调试以及 Valgrind 检测内存情况。

Lab 3: RISC-V Assembly

Learning Goals

  1. 熟悉使用 Venus 模拟 RISC-V 的运行。
  2. 了解 C 代码和 RISC -V 之间的相互转化。
  3. 编写正确的 RISC -V 函数调用。

Exercise 1 需要我们配置好 venus 的环境，简单来说就是把虚拟机或者 docker 里的 lab 文件夹映射到某个 web 路径下，然后通过 venus 的网站 进行访问，从而对本地文件进行调试分析。

但是后来发现 vscode 自身就有相关的插件，也还不错，效果如下：

image-20220929222126647

Exercise 2 通过一个斐波那契的例子，熟悉 Venus 对 RISC-V 调试分析。

Exercise 3 还是一个阅读理解，通过给出的 c 和 RISC-V 代码，找到两者的联系。

Exercise 4 需要我们使用 RISC-V 来实现阶乘，算是对之前所学的函数调用以及循环控制的一个练习。

Exercise 5: RISC-V function calling with map

这一小节需要我们完善一个链表以及 map 函数，该函数可以穿入一个链表以及函数指针来修改链表的内容。

struct node {
    int value;
    struct node *next;
};

void map(struct node *head, int (*f)(int))
{
    if (!head) { return; }
    head->value = f(head->value);
    map(head->next,f);
}

这里提一下链表，我们在 C 语言中如果想创建一个9->8->7...->2->1 的链表，一般是按顺序创建结点和修改指向

node_9->data=9;
node_9->next=node_8;
node_8->data=8;
node_8->next=node_7...
node_1->data=1;
node_1->next=NULL;

按照这个思路，我们需要把头节点暂存，然后每次把尾节点指向一个 malloc 分配的空间，重复操作，再返回头节点，这些许有些麻烦。

代码框架是从用从 1 到 9 的创建顺序，这样可以省去很多寄存器的使用，并且最后返回的就是头节点。

    li a0, 8            #     molloc 8 bytes on heap
    jal ra, malloc      #     Allocate memory for the next node
    sw s1, 0(a0)        #     node->value = i
    sw s0, 4(a0)        #     node->next = last
    add s0, a0, x0      #     last = node
    addi s1, s1, 1      #     i++
    addi t0, x0, 10
    bne s1, t0, loop    # ... while i!= 10

Lab 4: RISC-V Functions, Pointers

Exercise 1 需要我们补充 f 函数，使得调用传入数组和不同的 key ，输出不同的 value。

Exercise 2 需要我们修复 cc_test.s 中的访问错误，主要涉及到 s 寄存器的保存。

Exercise 3 要去我们使用规定的寄存器完成对以下 node 的遍历以及修改。

struct node {
    int *arr;
    int size;
    struct node *next;
};

这一节的坑点还是挺多的，主要是需要灵活的在不同场景使用不同寄存器。

Lab 5: Logisim

这一节算是给 project3 去做一个铺垫，也是终于进入了硬件部分，实验采用了 logisim 软件模拟和仿真数字电路。

Exercise 2: Sub-Circuits

需要我们只用 AND, OR,NOT 三种门电路实现NAND、NOR、XOR、MUX，前面几个比较简单，最后一个需要我们实现 4-to-1 Multiplexor，需要我们复用用上一个实现的 2-to-1 Multiplexor。

image-20221017181928848

Exercise 3: Storing State 这一节照着示意图做就可以，让我们用寄存器和加法器去理解存储的这个中间状态。

Exercise 4: Rotate Right

这一节需要我们实现算术右移 RotRight，根据输入的 INPUT0 ，将其整体右移 AMOUNT 位。

这里我们可以先分别实现右移1位、2位、4位、8位，再用 MUX 组合起来。

单个的 rot 可以利用 Splitters 组件简单实现 bit 交换。

image-20221019220418880

Lab 6: CPU, Pipelining

Exercise 1 - Constructing Immediates

这一节需要我们生成 S型指令中的立即数，S型指令结构如下图：

image-20221113133558814

最后还需要进行一个 12 位到 32 位的符号拓展：

image-20221113142854106

Exercise 2 - Constructing the BrUn Control Signal

这一节需要我们根据 B型指令中的 funct3 属性判断 branch 的跳转比较是有符号还是无符号，如下图：

image-20221113145135873

如果是无符号 BrUn 输出1，有符号则输出0，这里直接拿第13位进行：

image-20221113150537288

官网的提示想让我们用比较器，去综合比较 funct3 的值，如下也可以：

image-20221113150853508

Exercise 4 初步引入了 pipeline 的概念，如果一条指令依赖于前一条指令的输出，可以采用流水线的理念分层进行。

image-20221113153900852

Lab 7: Caches

Lab 8: SIMD Instructions

Lab 9: Thread-Level Parallelism

Lab 10: Virtual Memory

Search