0 写在前面

没有了textbook，写起笔记还挺不方便的，或者说显得不那么系统规范了

1 Number Representation

CSAPP讲得挺好

需要提及的是，这里再次说到了

You can add/subtract/multiply two’s complement numbers as if they were unsigned. You’ll magically get the right answer (Not really magical, just mathematical).

例如，以4位为例，计算-2+1，即1110 + 0001，按无符号数算(这里的意思应该是以位级表示去算)，得到1111，而-1的补码表示就是1111，这其实也是csapp里有时回避有时提及的问题，无论是直接对1110和0001作二进制加法，还是把它们看成无符号数14 + 1得到15再得到位级表示1111，最终结果截断成4位后，位级表示一定和把1110和0001按补码理解得到的结果的位级表示是一样的

Bias Notation
这种表示下，ww位数，0b000…00(0b表示二进制数)是最小的数，它表示biasbias，而0b111…11是最大的数，表示2w−1+bias2^w - 1 + bias

standard bias是−(2w−1−1)-(2^{w-1}-1)，以3位为例，0b001表示哪个十进制数？
0b001按unsigned理解是1，然后加上biasbias即可，即表示-2

反过来，问-2在standard bias下，它的3-bit biased notation是什么，那么先减去bias得到1，再用unsigned写出来，即0b001

2 C Basics

目前看了一节，还好学校学过C……这video的详细程度和语速都比CS61B不友好了不少啊……

2.1 Compilers (vs. Interpreters)

C, Java, Python: When Does Code Become Machine Instructions?

C

  • C compilers ultimately turn C code into architecture-specific machine code.
    • “Architecture-specific” means the machine code depends on the CPU type, like x86-64 vs. ARM.
    • Machine code is the actual 1s and 0s that the CPU can execute.
  • This happens before the program runs. This is called ahead-of-time compilation.
  • In everyday speech, “compiling a C program” means the whole process of turning C source code into an executable.
  • More precisely, the process has several steps:
    1. Compile .c files into assembly code.
    2. Assemble the assembly code into .o object files.
    3. Link the .o files together into an executable.
  • gcc hello.c -o hello runs all these steps for you.
  • A .o file already contains machine code, but it is not a complete runnable program yet. The linker combines the pieces into a full executable.

Java

  • Java source code is compiled into bytecode (.class files).
  • Bytecode is architecture-independent.
    • It is not machine code for a real CPU.
    • It is instructions for the Java Virtual Machine, or JVM.
  • At runtime, the JVM runs the bytecode.
  • A JIT compiler (just-in-time compiler) can compile frequently used bytecode into machine code while the program is running.
  • So Java often becomes real machine code at runtime, not before runtime.

Python

  • Python source code is compiled into bytecode at runtime.
  • Then the Python interpreter executes that bytecode.
  • Python is often called “interpreted,” but internally it still uses bytecode.
  • This bytecode is for the Python interpreter, not for the CPU directly.

Quick Comparison

Language Intermediate Form When Does It Become Machine Code? How It Runs
C Assembly, .o files, executable Before runtime CPU runs machine code directly
Java Bytecode At runtime, with JIT JVM + CPU
Python Bytecode At runtime Python interpreter + CPU

2.2 C vs. Java


内容有点杂，先记部分吧，或许之后的lab会详细些？

The C standard doesn’t define the absolute size of integer types, other than char.

It only guarantees relative sizes
sizeof(long long)≤\lesizeof(long)≤\lesizeof(int)≤\lesizeof(short)

int size depends on computer, what integer type is most efficient.

为了可移植性，使用C99引入的stdint.h

1
2
3
4
int8_t    uint8_t     // 8 位
int16_t   uint16_t    // 16 位
int32_t   uint32_t    // 32 位
int64_t   uint64_t    // 64 位

2.3 Pointer

想象内存是一个无限大的数组，每一个格子有一个编号，这就是它的地址，格子里面可以放值(value)，指针就是用来记录地址的

1
2
3
4
5
6
7
8
9
int *p; // Tells compiler that variable p is address of an int.

p = &y;
// Tells compiler to assign address of y to p.
// & called the "address operator" in this context.

z = *p;
// Tells compiler to assign value at address in p to z.
// * called the "dereference operator" in this context.

我们可以用指针做些事

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void addOne (int x) {
    x = x + 1;
}

void reallyAddOne(int *x) {
    *x = *x + 1;
}

int main() {
    int y = 3;
    addOne(y);
    printf("%d\n", y); // y is still 3.

    reallyAddOne(&y);
    // y is 4 now.
    return 0;
}

函数指针

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

int foo(int x, int y) {
	return x + y;
}

void mutate_map(int arr[], int n, int(*fp)(int, int)) {
  for (int i = 0; i < n; ++i) {
    arr[i] = (*fp)(arr[i], arr[i]);
  }
}

int main() {
	int (*fn) (int, int) = &foo;
	int res = (*fn) (1, 2);
	printf("%d", res); // 3
	return 0;
}

Why use pointers?
If we want to pass a large struct or array, it’s easier / faster / etc. to pass a pointer than the whole thing. Otherwise we’d need to copy a huge amount of data. In general, pointers allow cleaner, more compact code.

However, pointers are probably the single largest source of bugs in C, so be careful anytime you deal with them.

Pointers and Structures

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct {
  int x;
  int y;
} Point;

Point p1;
Point p2;
Point *paddr;

paddr = &p2;

/* dot notation */
int h = p1.x;
p2.y = p1.y;

/* array notation */
int l = paddr->x; // int l = p2.x;
int m = (*paddr).x; // int m = p2.x;

/* Now p1's member are equal to p2's, but p1 and p2 don't share the same address. */
p1 = p2;

Word Alignment

sizeof(type) returns number of bytes in object, including any padding(填充的) needed for alignment.

By Standard C99 definition, sizeof(char) == 1

2.4 Arrays

1
2
3
4
5
int arr[] = {0, 1};
int arr2[2] = {0, 1};
int arr3[5] = {0, 1};

int x = arr[1]; // x = 1

An array variable is a “pointer” to the first element, it can’t be changed.

arr[0] is the same as *arr, arr[1] is the same as *(arr + 1) (当然，这里+2并不是说地址直接+2，即多2个bytes，而是根据类型来决定，例如上例中，假设arr的两个元素的地址是0x100和0x104，那么arr + 1其实得到的是0x104，即arr + 1 * sizeof(int))

Declared arrays are only allocated while the scope is valid.

1
2
3
4
5
6
7
8
9
10
char *foo() {
  char string[32];
  return string;
  /** 
   * Incorrect.
   * That space was only available in that subroutine.
   * While foo was alive was that string available.
   * The moment foo ends, the system might reuse that, so you don't have access to that. 
   */
}

2.5 Memory Management

void *malloc(size_t n) allocates a block of uninitialized memory:

  • size_t n is an unsigned integer type big enough to “count” memory bytes.
  • Returns void * pointer to block of memory on heap.
  • A return of NULL indicates no more memory (always check for it !).
1
2
3
4
5
6
7
8
typedef struct {
  ...
} TreeNode;
TreeNode *tp = (TreeNode *) malloc(sizeof(TreeNode));
// Typecast casts return value to (TreeNode *)
if (tp != NULL) {
  ... // Always check NULL after
}

void free(void *ptr) dynamically frees heap memory.
ptr is a pointer containing an address originally returned by malloc() or realloc().

When you free memory, be sure to pass the original address returned from malloc(). Otherwise, crash (or worse!)

void *realloc(void *ptr, size_t size) resizes a previously allocated block at ptr to a new size.

  • Returns new address of the memory block (In doing so, it may need to copy all data to a new location.).
  • realloc(NULL, size); behaves like malloc
  • realloc(ptr, 0); behaves like free
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
33
34
35
36
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int* p, * q, x;
  int a[4];

  p = malloc(sizeof(int));
  if (p == NULL) {
      fprintf(stderr, "malloc failed\n");
      return 1;
  }

  q = &x;

  *p = 1;
  printf("*p: %d, p: %p, &p: %p\n", *p, (void*)p, (void*)&p);

  *q = 2;
  printf("*q: %d, q: %p, &q: %p\n", *q, (void*)q, (void*)&q);

  *a = 3;
  printf("*a: %d, a: %p, &a: %p\n", *a, (void*)a, (void*)&a);

  free(p);
  return 0;
}

/*

*p: 1, p: 0000020C5A1D82A0, &p: 0000005BCC7FF688
*q: 2, q: 0000005BCC7FF6C4, &q: 0000005BCC7FF6A8
*a: 3, a: 0000005BCC7FF6E8, &a: 0000005BCC7FF6E8

&a获取地址时，a不会退化为指针常量，&a的值跟a是一样的，步长是数组总字节数
*/

举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node {
  char* value;
  struct Node* next; 
}

typedef struct Node* List;

List list_add(List list, char* string) {
  struct Node* node = malloc(sizeof(struct Node));
  node->value = malloc(strlen(string) + 1); // 这里选择让每个节点申请内存后拷贝string，理论上node->value = string;也可以
  strcpy(node->value, string);
  node->next = list;
  return node;
}

2.6 Memory Location

Struct declaration doesn’t allocate memory. Variable declaration does allocate memory.

So far we’ve talked about several different ways to allocate memory for data:

  • Declaration of a local variable
    int i; struct Node list; char* string; int arr[5];
  • Dynamic allocation at runtime by calling allocation funcion
    ptr = malloc(sizeof(struct Node) * n);
  • One more possibility is that data declared outside of any procedure. It has “global” scope.
1
2
3
4
int myGlobal;
int main() {
  return 0;
}

C has 3 pools of memory for variables

  • Static Storage: global/static variable storage, basically permanent, entire program run.
  • The Stack: local variable storage, parameters, return address.
  • The Heap (dynamic malloc storage): data lives until deallocated by programmer.

Where are variables allocated?

Global: If declared outside a function, allocated in data (static) storage.

Local: If declared inside function, allocated on the stack and freed when function returns. In C, a local variable has automatic storage duration, which means that its lifetime begins when execution enters the block where it is declared and its lifetime ends when execution leaves that block or function.

For both these memory types, the management is automatic. You don’t need to worry about deallocating when you’re no longer using them. But a variable doesn’t exist anymore once a function ends.

2.7 Stack and The Heap

In a typical RISC-V-style calling convention:

  • The stack grows downward.

  • On function entry, the function decreases the stack pointer sp to allocate a new stack frame.

  • On function exit, it increases sp back to restore the caller’s frame.

When a function returns, its stack frame is “freed” in the sense that the stack pointer moves back to the caller’s frame. The memory is now considered available for future function calls.

But the old bytes are usually still there.

They are no longer valid for your program to use, but they may still physically exist in the stack memory until something else overwrites them.

So after the function returns, the local variable is logically dead. The memory location may still contain the old bit pattern. But the program no longer has the right to access it through that variable or through a pointer to it.

The heap is dynamic memory – memory that can be allocated, resized, and freed during program runtime.

  • Useful for persistent memory across function calls.
  • But biggest source of pointer bugs, memory leaks, …
  • Similar to Java new command allocates memory…but with key differences below.
  • Huge pool of mem (usually >> stack), but not allocated in contiguous order.
  • Back-to-back (紧接的) requests for heap memory could result in blocks very far apart

A Simple Head Allocator (K&R Section 8.7)

Each block of memory is preceded by a header that has two fields: size of the block and a pointer to the next block.

1
2
3
4
5
6
7
8
        Header                  User data
+--------+--------+----------------------------+
| size   | next   |  bytes returned by malloc  |
+--------+--------+----------------------------+
^                  ^
Header              pointer given to the caller

next is used only when the block is free, to link it into the free list.

All free blocks are kept in a circular linked list. In an allocated block, the header’s pointer field is unused.

malloc() searches the free list for a block that is big enough(如果剩余部分比较大，会自己分割). If none is found, more memory is requested from the operating system. If what it gets can’t satisfy the request, it fails.

free() checks if the blocks adjacent to the freed block are also free.

  • If so, adjacent free blocks are merged (coalesced) into a single, larger free block.
  • Otherwise, freed block is just added to the free list.

If there are multiple free blocks of memory that are big enough
for some request, how do we choose which one to use?

  • best-fit: choose the smallest block that is big enough for the request.
  • first-fit: choose the first block we see that is big enough.
  • next-fit: like first-fit, but remember where we finished searching and resume searching from there.

2.8 When Memory Goes Bad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int* ptr() {
	int y = 3;
	return &y;
}

int main() {
  int* stackAddr = ptr();
	int content;
	content = *stackAddr;
	printf("Now on the stackAddr is %d\n", content);
	content = *stackAddr;
	printf("After we called printf, on the stackAddr is %d\n", content);
	return 0;
}

/*
Output:

Now on the stackAddr is 3
After we called printf, on the stackAddr is -858993460

*/

What Happens

  1. y is a local variable. It lives in ptr’s stack frame.

  2. When ptr returns, its stack frame is deallocated: the stack pointer moves back.

  3. Deallocation does not erase memory. The bytes for y may still contain 3.

  4. So the first *stackAddr may print 3.

Why the Second Print Changes

  1. Calling printf creates a new stack frame.

  2. This new frame reuses the same stack memory where y used to be.

  3. printf overwrites that memory with its own data.

  4. So the second *stackAddr reads garbage, e.g. -858993460.

  5. -858993460 is 0xCCCCCCCC, a common debug fill pattern in MSVC, but it is not guaranteed (printf返回后填充了0xCCCCCCCC).

补充：

  • 整个程序（每个线程）只有一个栈。

  • 函数调用是在同一个栈上叠加栈帧 (stack frame)，不是创建新栈。

  • 栈帧里只有返回地址、保存的寄存器、参数、局部变量。

  • 堆、数据段、代码段是进程级别的独立区域，不属于栈帧。

  • 函数可以访问堆和数据段，但它们是全局共享的。

常见问题：

  1. free两次
  2. realloc可能移动位置，不能再用原来的地址了
  3. p是malloc得来的，p++而不备份p原来的地址，没法free了

3 C Generics

A function pointer is a variable storing the starting address of a function. Functions live in the code/text area. Function pointers allow us to define higher-order functions, such as map, filter, and generic sort.

Generics is short for generic functions.

3.1 Why Generic Functions?

We want to write general-purpose code.

  • Generic code reduces code duplication and means you can make improvements and fix bugs in one place rather than many.
  • Generics are used throughout C for functions to sort any array, search any array, free arbitrary memory, and more.

In general, generics:

  • Should generally work regardless of argument type.
  • Update blocks of memory, regardless of data type stored in those blocks.

3.2 Writing Generics

1
2
3
4
5
6
7
8
9
10
11
void swap_int(int* p1, int* p2) {
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

void swap_string(char** p1, char** p2) {
  char* tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

解引用指针时，我们必须在compile time时就知道需要从内存访问的字节数

1
2
3
4
5
int main() {
  int a = 0;
  void* p = &a;
  int b = *p;
}

void 是无类型，编译器不知道 p 指向的数据有多大、是什么类型，所以 不允许 *p

1
2
/* Copy n bytes from memory area src to memory area dest. */
void* memcpy(void* dest, const void* src, size_t n);
  • void* dest 目标内存地址，指向要写入的地方。void* 表示“任意类型指针”，因为 memcpy 只按字节复制，不关心数据类型。
  • const void* src 源内存地址，指向要读出的地方。const 表示 memcpy 不会修改 src 指向的数据。
  • size_t n 要复制的字节数。size_t 是无符号整数类型，通常用来表示大小、长度

要复制的源数据块，和你写入的目标数据块，不能有任何一部分是同一块内存。如果它们有交集，就叫 overlap（重叠）

1
2
3
4
5
6
7
8
void f(const int* p); // p指向一个const int，所以函数内不能修改*p

void f(int const* p); // 和上面一样

void f(int* const p); // p指向一个int，但p是常值不能修改

// 技巧：从右往左读，比如最后的f，
// 先读到const说明const修饰的是p

如果memory areas overlap了，就要使用memmove，但memcpy是更快的

1
2
3
4
5
6
7
/* 
Copy n bytes from memory area src to memory area dest. 

Copying takes place as though the bytes in src are first 
copied into a temporary array ... then copied ... to dest.
*/
void* memmove(void* dest, const void* src, size_t n);

这样我们就能写出通用的swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void swap(void* ptr1, void* ptr2, size_t nbytes) {
  // 1. Store a copy of data1 in temporary storage.
  // In C, sizeof(char) == 1 byte, regardless of architecture.
  // To create temporary "generic" storage, declare a local character array.
  char* temp = malloc(nbytes);
  if (temp == NULL) {
    return;
  }
  memcpy(temp, ptr1, nbytes);

  // 2. Copy data2 to location of data1.
  memcpy(ptr1, ptr2, nbytes);

  // 3. Copy data in temp to location of data2.
  memcpy(ptr2, temp, nbytes);
}

int main() {
  int data1 = 2;
  int data2 = 3;
  swap(&data1, &data2, sizeof(data1));
  return 0;
}

下面我们实现一个函数，它接受一个数组并交换数组的第一个元素和最后一个元素

1
2
3
4
5
6
7
8
9
10
void swap(void* ptr1, void* ptr2, size_t nbytes);
void swap_ends(void* arr, size_t n, size_t elementSize) {
  swap(arr, (char*)arr + (n-1)*elementSize, elementSize);
}

/*
 * Pointer arithmetic in generics must be bytewise (按字节) arithmetic.
 * 1. Cast void* pointer to char*
 * 2. Pointer arithmetic is then effectively byte-wise
 */