Some Learning Notes of CS110L, based on course in 2020 spring that provides video as well as slides.

Exercise

1. Memory Safety Pre-class exercise

Link
Code here

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// There are at least 7 bugs relating to memory on this snippet.
// Find them all!

// Vec is short for "vector", a common term for a resizable array.
// For simplicity, our vector type can only hold ints.
typedef struct {
  int* data;     // Pointer to our array on the heap
  int  length;   // How many elements are in our array
  int  capacity; // How many elements our array can hold
} Vec;

Vec* vec_new() {
  Vec vec;
  vec.data = NULL;
  vec.length = 0;
  vec.capacity = 0;
  return &vec;
}

void vec_push(Vec* vec, int n) {
  if (vec->length == vec->capacity) {
    int new_capacity = vec->capacity * 2;
    int* new_data = (int*) malloc(new_capacity);
    assert(new_data != NULL);

    for (int i = 0; i < vec->length; ++i) {
      new_data[i] = vec->data[i];
    }

    vec->data = new_data;
    vec->capacity = new_capacity;
  }

  vec->data[vec->length] = n;
  ++vec->length;
}

void vec_free(Vec* vec) {
  free(vec);
  free(vec->data);
}

void main() {
  Vec* vec = vec_new();
  vec_push(vec, 107);

  int* n = &vec->data[0];
  vec_push(vec, 110);
  printf("%d\n", *n);

  free(vec->data);
  vec_free(vec);
}

Find 7 bugs：

1. The whole `vec_push` function does not check if `vec` is `NULL`

Similarly, vec_free does not check it, which cause accessing a null pointer

Additional information:
From here we knows that malloc(0) returns either a null pointer or a unique pointer, so it might works.
Also, free(NULL) has no problem at least because for free, if ptr is a null pointer, no action shall occur.
In linux glibc, malloc(0) always returns a returns a unique pointer value that can later be successfully passed to free(). (See man 3 free)

2. capacity growth fails on initial capacity = 0

Vec* vec_new() {
  Vec vec;
  vec.data = NULL;
  vec.length = 0;
  vec.capacity = 0;
  return &vec;
}

if (vec->length == vec->capacity) {
    int new_capacity = vec->capacity * 2;
    int* new_data = (int*) malloc(new_capacity);
    assert(new_data != NULL);
}

So that the capacity is always 0, and never malloc any size of memory.

3. Wrong allocation size

1 2	int new_capacity = vec->capacity * 2; int* new_data = (int*) malloc(new_capacity);

The right size of new_data should be new_capacity * sizeof(int)

4. old `vec->data` is never freed

5. free order

void vec_free(Vec* vec) {
  free(vec);
  free(vec->data);
}

vec is freed before freeing its data

6. `vec_push` does not actually checks the size limit

1
2
3

if (vec->length == vec->capacity) 
...
vec->data[vec->length] = n;

The length is lastIndex + 1, but it is used as the last index, exceeding the size limit

7. `vec_new` returned `vec` lives too short

Vec* vec_new() {
  Vec vec; // <- On heap temporary variable
  vec.data = NULL;
  vec.length = 0;
  vec.capacity = 0;
  return &vec;
} // <- Gone

CS110L 笔记

Exercise

1. Memory Safety Pre-class exercise

1. The whole vec_push function does not check if vec is NULL