cs61c-lab02

Lab 2: Advanced C

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

Exercise 0: Makefiles

makefile教程：https://seisman.github.io/how-to-write-makefile/introduction.html

Exercise 1: Bit Operations

完成get_bit, set_bit, and flip_bit

独立完成后，查看别人的实现学习到了更简洁更直观的表达，就理下别人的思路

1
2
3
4
5
6
7
8
unsigned get_bit(unsigned x,
                 unsigned n) {
    // YOUR CODE HERE
    // Returning -1 is a placeholder (it makes
    // no sense, because get_bit only returns
    // 0 or 1)
    return (1&(x>>n));
}
  1. (x >> n)：首先，将整数 x 向右移动 n 位，以便将第 n 位移到最低位，这样我们可以轻松地从最低位提取出这个位的值。
  2. (1 & (x >> n))：然后，将移位后的结果与二进制数 0b00000001（即1）进行按位与操作。这将保留右移后的结果的最低位，也就是第 n 位。
  3. return (1 & (x >> n));：最后，将上述按位与操作的结果作为函数的返回值，即返回第 n 位的值（0 或 1）。
1
2
3
4
5
6
7
void set_bit(unsigned * x,
             unsigned n,
             unsigned v) {
    // YOUR CODE HERE
    unsigned mask = ~(1<<n);
    (*x) = ((*x) & mask)|(v << n);
}
  1. unsigned mask = ~(1<<n);：首先，创建一个掩码 mask，它的目的是将第 n 位设置为0，其他位都保持不变。这是通过将数字1左移 n 位然后取反得到的，实际上就是将第 n 位设置为0，其他位都设置为1。
  2. (*x) = ((*x) & mask)|(v << n);：然后，使用掩码和左移操作将指定的位设置为新的值 v。
    • (*x) & mask：这个步骤将保留 x 中除第 n 位以外的所有位，通过将 x 和掩码 mask 进行按位与操作。
    • v << n：将值 v 左移 n 位，将要设置的位放置在正确的位置。
    • ((*x) & mask) | (v << n)：将上述两个步骤的结果进行按位或操作，将保留的部分与设置的位合并，得到最终的结果。
1
2
3
4
5
void flip_bit(unsigned * x,
              unsigned n) {
    // YOUR CODE HERE
    (*x)^=(1<<n);
}
  1. (1 << n)：首先，将数字1左移 n 位，生成一个只有第 n 位为1，其他位为0的数。例如，如果 n 是3，则 1 << 3 的结果是二进制数 0b00001000。
  2. (*x) ^= (1 << n);：然后，将左移后的结果与原始值 x 进行按位异或操作（^= 表示按位异或赋值操作）。按位异或操作的性质是，对于两个操作数的每一位，如果两个操作数的对应位不同，则结果的该位为1，否则为0。因此，这个操作将会翻转 x 的第 n 位。

Exercise 2: Linear Feedback Shift Register

很简单的一个东西，由于makefile 设置的原因，不要调用bit_ops.c的函数在lfsr.c中

lfsr倒是蛮有意思

Exercise 3: Memory Management

最开始没想明白两个函数为什么有问题，只是觉得跟之前写的不一样，因为之前结构也要malloc分配空间。

贴上chatgpt的解释

bad_vector_new()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* Bad example of how to create a new vector */
vector_t *bad_vector_new() {
    /* Create the vector and a pointer to it */
    vector_t *retval, v;
    retval = &v;

    /* Initialize attributes */
    retval->size = 1;
    retval->data = malloc(sizeof(int));
    if (retval->data == NULL) {
        allocation_failed();
    }

    retval->data[0] = 0;
    return retval;
}

它试图返回一个指向局部变量的指针，这会导致悬空指针问题，而且在修改局部变量的成员时也会导致未定义行为。

具体来说，这段代码的问题在于：

  1. vector_t v;：在堆栈上创建了一个局部变量 v，它的生命周期仅限于 bad_vector_new() 函数的执行期间。
  2. retval = &v;：将局部变量 v 的地址赋给了 retval，使得 retval 指向了局部变量 v 所在的内存地址。
  3. retval->size = 1; 和 retval->data = malloc(sizeof(int));：试图在局部变量 v 上操作，但由于它是在堆栈上分配的，这会导致未定义行为。这意味着你正在修改一个局部变量的成员，而不是动态分配的内存。
  4. return retval;：返回了指向局部变量 v 的指针 retval。

这会导致类似前面提到的问题，当函数 bad_vector_new() 结束时，局部变量 v 将被销毁，但是 retval 仍然指向了该内存地址，从而导致悬空指针。同时，试图在局部变量上进行成员访问也会导致未定义行为。

also_bad_vector_new()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Another suboptimal way of creating a vector */
vector_t also_bad_vector_new() {
    /* Create the vector */
    vector_t v;

    /* Initialize attributes */
    v.size = 1;
    v.data = malloc(sizeof(int));
    if (v.data == NULL) {
        allocation_failed();
    }
    v.data[0] = 0;
    return v;
}

它试图返回一个局部变量 v，它在函数结束时将会被销毁，导致悬空指针问题。

具体问题如下：

  1. vector_t v;：在堆栈上创建了一个局部变量 v，它的生命周期仅限于 also_bad_vector_new() 函数的执行期间。
  2. v.size = 1; 和 v.data = malloc(sizeof(int));：在局部变量 v 上操作，分配了内存并将指针存储在 v.data 中。由于 v 是在堆栈上分配的，当函数 also_bad_vector_new() 结束时，局部变量 v 将被销毁，导致 v.data 指向的内存变成了悬空指针。
  3. return v;：试图返回局部变量 v。

这会导致悬空指针问题，因为在函数结束后，局部变量 v 将被销毁，但是返回的 v 中的指针 v.data 仍然指向了之前分配的内存地址

综上，就是malloc这个应该在heap上调用的函数，不应用到stack上，导致的一系列问题

vector_new()

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
vector_t *vector_new() {
    /* Declare what this function will return */
    vector_t *retval;

    /* First, we need to allocate memory on the heap for the struct */
    retval = (vector_t*) malloc(sizeof(vector_t));
  

    /* Check our return value to make sure we got memory */
    if (retval == NULL) {
        allocation_failed();
    }

    /* Now we need to initialize our data.
       Since retval->data should be able to dynamically grow,
       what do you need to do? */
    retval->size = 1/* YOUR CODE HERE */;
    retval->data = (int*) malloc(sizeof(int)); /* YOUR CODE HERE */;

    /* Check the data attribute of our vector to make sure we got memory */
    if (retval->data == NULL) {
        free(retval);				//Why is this line necessary?
        allocation_failed();
    }

    /* Complete the initialization by setting the single component to zero */
    /* YOUR CODE HERE */ 
    retval->data[0] = 0;

    /* and return... */
    return retval;
}

正常思路，给struct 手动分配内存就好

vector_set()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void vector_set(vector_t *v, size_t loc, int value) {
    /* What do you need to do if the location is greater than the size we have
     * allocated?  Remember that unset locations should contain a value of 0.
     */

    /* YOUR SOLUTION HERE */
    if(loc >= v->size){
        size_t new_size = loc + 1;
        int* new_data = (int *) realloc(v->data,new_size*sizeof(int));
        if(new_data == NULL){
            allocation_failed();
        }
        for(size_t i = v->size ; i < new_size; i++){

            v->data[i] = 0;
        }
        v->size = new_size;
        v->data = new_data;
    }
    v->data[loc] = value;
}

注意设0时，别覆盖了之前设置过值就好

makefile test

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Calling vector_new()
Calling vector_delete()
vector_new() again
These should all return 0 (vector_get()): 0 0 0
Doing a bunch of vector_set()s
These should be equal:
98 = 98
15 = 15
65 = 65
-123 = -123
21 = 21
43 = 43
0 = 0
0 = 0
0 = 0
3 = 3
Test complete.

注意：

  1. 在 makefile 中为 vector-test 目标实施规则。
  2. 在 vector.h 中添加函数声明
Architecture
#cs61c
cs61c-lab02
https://2333monster.github.io/2023/08/10/cs61c-lab02/
作者
John Titor
发布于
2023年8月10日
许可协议