LEC 2

Build procss:
sum.c -> C preprocessor: cpp
-> compiler proper (cc1) translate to assemely: sum.s, s - source
-> assembler (AS): translate to machine code: sum.o, relocatable object file
-> linter (LD): excutable : a.out, sum.exe

  1. # -g: start debugger
  2. # -o: output filename
  3. # -Wall: turn on warnings
  4. # -E: will stop after the preprocessor runs
  5. # -S: assembley source file
  6. gcc -E -g -o sum.i demo.c -Wall # stop at the preprocessor
  7. gcc -S -g -o sum.s demo.c -Wall # stop at the compiler proper
  8. gcc -c -g -o sum.o demo,c -Wall # stop at the assembler, machine code
scp file.name yingwei@linux-best.cs.wisc.edu: cs354/
scp source dest

LEC 3

//From uppercase to lowercase
char_uppercase = char_lowercase - ('a' - 'b');

//arrays of characters
char str[] = "CS354"

LEC 4

variable names:

  • uppercase
  • lowercase
  • underscores(library variables)

  • digits - cannot be first

    primitive data type

  • integer - 4 byte

  • modifiers
  • char - 1 byte
  • short int - 2 byte >= char
  • int - 4 byte >=short
  • long int - 8 byte >= int
  • long long int - 8 byte >= long
  • float - 4 byte
  • double - 8 byte

  • long double - 10 byte

    sign + and -

  • unsigned char - 1 bit, 0-255

    C comment

  • // line coment

  • / / block comment
  • //*

comment codes
// */

Strings

  • no strings on char[]

    Boolean - no T/F

  • 0 -false

  • 1 - true
  • non-zero - true

C 参数

int main(int argc, char *argv[]){
    return 0;
}
$ ./mysort 2 8 9 1 4 5
argc = 7
argv[ 0 ] = ./mysort
argv[ 1 ] = 2
argv[ 2 ] = 8
argv[ 3 ] = 9
argv[ 4 ] = 1
argv[ 5 ] = 4
argv[ 6 ] = 5

C 语言没有切片操作：q[-1]是越界行为out of boundary,但是[-1]实际上上地址-1*sizeof(datatype)

Array

  1. array不能计算

    int a[] = {1,2,3};
a++;   -> false, cannot increment an array.

  2. pointer and array

    x == &x[0]
*x == x[0]

  3. Also, for any array or pointer p and index i the expressions p[i] and (p + i) are equivalent. ```c int p; p[0] == (p + 04); p[1] == (p + 14);

// same meaning int* myPointer = new int[100];

int firstValue = *(myPointer + 0); int secondValue = myPointer[1];

<a name="Qdg4A"></a>
## 

---

<a name="ilrNe"></a>
# struct
```c
struct student{
    char *name;
    int id;
}
struct person{
    char name[100];
    int id;
}
int main(){
    struct student s;
    s.id = 12;
    s.name = "mike";

    struct person p;
    p.id = 22;
    //p.name = "alice" // doesn't work. p.name is a variable in stack and unmutable
    // trying to assign a pointer to a string into a string.
    strncpy(p.id, "alice", 100);
}

Pointer 指针

  • asterisk, segmentation fault is runtime error
  • 表示定义一个指针变量，以和普通变量区分开，例如int a = 100; int *p = &a;。

  • 表示获取指针指向的数据，是一种间接操作，例如int a, b, p = &a; p = 100; b = *p;。

    int *p = NULL;
*p = 1;        // this will cause segmentation fault because cannot dereference a null pointer

  • pointer and 2d array

    • A[0][2] = *(A[0] + 2)
    • image.png
    • assign pointer to integer directly ```c double *p = 0;

double *p; p = 0; // by doing this, we assign the address p with 0, we never dereference the p


   - **functions to increment pointer and value **
```c
void increament_value(int *ptr){*ptr += 1;}
void increament_pointer(int **ptr){*ptr += 1;}

int main(){
    int arr[2] = {0, 1};
    int *ptr = arr;
    increament_pointer(&ptr); // this will change ptr to arr2[1]
    increament_value(ptr); // this will change value of arr2[1] as 2
}

Sizeof

  1. pointer 的sizeof 都是 8，不管是什么类型

  2. sizeof and len

    len("hello") -> 5
sizeof("hello") -> 6, which will include the last /0 character.

  3. whenever pass the Array to a function, sizeof(Array) will always return the pointer size - 8

i ++ and ++i

image.png

strcpy and memcpy

(dest, source)
两者都是复制ptr2 to ptr1， 而不改变ptr内存放的地址。memcpyx需要提供长度（唯一区别）

Memory Alloc

Address Space

image.png

Implicit and explicit

  • Implicit - programming language use internal garbage collection, java/python
  • Explicit - malloc / free, programmer responsible

Super Simple Memory Allocator

block - header(metadata), payload(user space), padding(wasted space)
image.png
address 0 - 4, store next pointer at the head of the heap
HOWEVER, if I wanna free p2, there is no way to get the size of p2, and this it the problem.

GOALS:

  1. Maxmize throughput
  2. Maxmize memory utlization, minimize padding, holes and metadata

Fragmentation

  1. Internal - wasted space inside of a block
    1. alignment
    2. minimize block size
    3. chose no to split
  2. External - have enough total free space to meet the request, but it’s broken into several pieces(object is bigger than hole)

image.png
structure: the address should divisible by 8
— metadata (next address / if-allocate)
— payload
— padding

free - coalescing
image.png

Math trick
image.png

  1. Fitness Policy
  2. splitness
  3. freeing
  4. coalessing
  5. boundary tags (footer) -> like double-linked list
    1. advanced boundary tags

Coalscing

  • immediate - block after (1 step)
  • deferred - block before (traverse)

image.png

coalscing after
image.png
before
image.png
H1 = size = sum_size / 0
F2 = copy of H1

Assembly

movl 0x1000, %eax
movl 1000, %eax    // atuomatically converts to hex address and reads memory
location 0x3E8

// register to hold the memory addressing
movl $0x1000, %eax
movl (%eax), %ebx // parentness here means dereference

movl 8(%eax), %ebx
0x1000 + 0x8 = 0x1008   stores 42 in %ebx