이번에는 code optimization에 대해서 다뤄보겠습니다. 대부분의 compiler들은 CPU가 이해할 수 있는 machine code로 변환하기 위해 compile을 진행하는데, 이때 코드 그대로 단순히 변환하기 보다는 optimization을 통해 더 빠르게 실행될 수 있도록 만들어줍니다. compiler가 optimization을 진행하는 목표는 크게 다음과 같습니다.

• Minimize number of instructions 반복되는 연산을 한 번에 할 수 있도록 바꾸고, 불필요한 연산을 줄이고, slow instruction(multiplication, division 등)을 최소화

• Avoid waiting for memory 가능한 모든 data를 register에 유지시키고, cache friendly한 memory access로 변환

• Avoid branching 불필요한 branch를 줄이고, branch prediction을 용이하게 하도록 변환

위의 세 가지는 모두 code의 실행 속도를 빠르게 만들어주는 방향의 optimization입니다. 하지만 optimization을 진행할 때 다음과 같은 한계점도 존재합니다.

• Generally cannot improve algorithmic complexity constant factor만 바뀔 뿐 asymptotic analysis(big-O, big-theta)의 결과는 변하지 않음

• Must not cause any change in program behavior programmer가 의도한 대로 program이 실행되어야 하므로 logic이 바뀌지 않아야 함

• Usually only analyze one function at a time 전체 program을 한 번에 analyze하는 것은 expensive

Example of optimization

이제 앞서 언급한 전략에 맞춘 optimization에는 어떤 것이 있는지에 대해 그 예시를 들어 알아보겠습니다. code의 변화를 알아보기 쉽도록 assembly code가 아닌 c code를 통해 살펴보겠습니다.

• constant folding

// example 1
long mask = 0xFF << 8;
long mask = 0xFF00;

// example 2
size_t namelen = strlen("Harry Bovik");
size_t namelen = 11;

위의 code는 동일한 결과가 나타나는 두 가지 code입니다. 두 개의 공통점은 compile을 진행하기 이전에 이미 그 값을 결정할 수 있다는 점입니다. mask = 0xFF << 8과 namelen = strlen("Harry Bovik")그 결과가 이미 정해져 있으므로 이를 각각 mask = 0xFF00과 namelen = 11로 바꾸어 instruction의 수를 줄일 수 있습니다. 이와 같이 constant value로 정해진 연산을 compile time에 미리 수행해 optimize하는 방법을 constant folding이라 합니다.

• strength reduction

long a = b * 5;
long a = (b << 2) + b;

위의 두 code의 연산 결과는 a = b * 5로 동일합니다. 둘의 차이점은 multiplication을 사용한 것과 logical shift를 사용한 것에 있습니다. hardware에서 multiplication은 매우 느린 연산 중에 하나인 반면 shift는 빠르게 수행할 수 있으므로 아래 code의 속도가 더 빠르게 진행됩니다. 이와 같이 heavy한 연산을 더 빠른 연산으로 바꾸어 동일한 결과를 만들어내는 것을 strength reduction이라 합니다.

• dead code elimination

  // example 1
  if (0) { puts("Kilroy was here"); }
  if (1) { puts("Only bozos on this bus"); }
  

puts("Only bozos on this bus");

// example 2 x = 0; x = 23;

x = 23;

첫 번째 example에서 `if(0)`에 해당하는 line은 항상 false이므로 실행되지 않고, `if(1)`에 해당하는 line은 항상 true이므로 무조건 실행되어 결과적으로 `puts("Only bozos on this bus");`를 실행시키는 것과 동일한 결과를 나타냅니다. 두 번째 example에서는 `x = 0;`의 결과에 `x = 23;`을 overwrite하므로 `x = 0;`을 실행하지 않은 것과 동일한 결과를 나타냅니다. 이와 같이 실제로 실행하지 않아도 결과가 동일한 code를 compile 과정에서 지우는 것을 dead code elimination이라 합니다.

* __common subexpression elimination (CSE)__
```c
norm[i] = v[i].x * v[i].x + v[i].y * v[i].y;

elt = &v[i];
x = elt->x;
y = elt->y;
norm[i] = x*x + y*y;

위의 code는 norm[i]를 계산하기 위해 v[i]에 총 4번 access하는 반면 아래의 code는 새로운 변수 x와 y에 v[i].x와 v[i].y를 assign하여 결과적으로 v[i]에는 두 번 access하는 것을 알 수 있습니다. 이를 통해 memory에 access하는 횟수를 줄일 수 있어 성능 향상을 이룰 수 있습니다. 이와 같이 동일한 memory에 대한 access의 횟수를 줄이는 optimization을 common subexpression elimination(CSE)라 합니다.

• code motion

  // example 1
  long j;
  for (j = 0; j < n; j++) {
    a[n*i+j] = b[j];
  }
  

long j; int ni = n*i; for (j = 0; j < n; j++) { a[ni+j] = b[j]; }

// example 2 void lower(char *s) { size_t i; for (i = 0; i < strlen(s); i++ { if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a'); } }

void lower(char *s) { size_t i, n = strlen(s); for (i = 0; i < n; i++) { if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= ('A' - 'a'); } }

위의 두 example의 공통점은 loop 내에서 매 iteration마다 연산이 진행되는 부분을 loop의 밖으로 빼주었다는 점입니다. example 1에서는 `n * i`의 연산을 loop 밖에서 진행해 heavy한 연산을 매 iteration마다 진행하지 않고 실행하도록 했으며 example 2에서는 `strlen(s)`를 loop 밖에서 실행해 function call의 횟수를 줄이도록 한 것입니다. 이를 통해 instruction의 갯수와 불필요한 branch를 모두 줄일 수 있어 속도의 향상을 이룰 수 있습니다. 이와 같이 code를 옮겨 성능을 높이는 optimization을 code motion이라 합니다.

* __inlining__
```c
int pred(int x) {
    if (x == 0) return 0;
    else return x - 1;
}
int func(int y) {
    return pred(y) + pred(0) + pred(y + 1);
}


int func(int y) {
    int tmp;
    if (y == 0) tmp = 0; else tmp = y - 1;
    if (0 == 0) tmp += 0; else tmp += 0 - 1;
    if (y + 1 == 0) tmp += 0; else tmp += (y + 1) - 1;
    return tmp;
}


int func(int y) {
    int tmp;
    if (y != 0) tmp = y - 1;
    if (y != -1) tmp += y;
    return tmp;
}

첫 번째 code는 func()에서 pred()를 call하도록 구현한 것이며 두 번째는 pred()를 call하는 대신 func() 내에서 모두 해결하도록 구현한 것입니다. pred()를 call할 때마다 code에 branch가 생기고 이로 인해 branch prediction이 틀린 경우 overhead가 크게 나타나는 등 매우 느려질 수 있습니다. 반면 이를 기존 function 내에서 모두 구현한 경우 control path의 변화를 줄여 전체적인 속도의 향상을 이룰 수 있습니다. 이와 같이 function call 대신 callee의 동작을 caller 내부로 옮겨주는 것을 inlining이라 합니다. 여기에 추가적으로 dead line elimination까지 진행해 세 번째 code와 같이 optimize 한다면 if에 의한 branching까지 줄어들어 더 좋은 성능을 얻을 수 있습니다.

• loop unrolling

  for (size_t i = 0; i < nelts; i++) {
    A[i] = B[i]*k + c[i];
  }
  

for (size_t i = 0; i < nelts - 4; i += 4) { A[i] = B[i]k + c[i]; A[i+1] = B[i+1]k + c[i+1]; A[i+2] = B[i+2]k + c[i+2]; A[i+3] = B[i+3]k + c[i+3]; }

```

위의 예시는 loop invariant의 increment를 늘리고 한 iteration에서 더 많은 연산을 진행해 전체적인 iteration을 1/4로 줄이도록 바꾼 code입니다. 위와 같은 optimization을 통해 먼저 loop의 횟수를 줄일 수 있으므로 backward branch의 갯수가 줄어드는 효과를 얻을 수 있으며, 현재 예시에는 드러나지 않았지만 CSE, code motion 등 추가적인 optimization 까지 가능하다는 장점이 있습니다. 이와 같은 optimization을 loop unrolling이라 합니다.

reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

Memory Access

우리가 사용하는 컴퓨터는 기본적으로 폰 노이만 아키텍처를 따르고 있기 때문에 연산을 처리하기 위한 부분인 CPU와 data를 저장하기 위한 memory가 서로 구분되어 있습니다. 따라서 CPU에서 memory에 있는 data를 가져오거나 memory로 data를 저장하려 할 때에는 bus라는 일종의 통로를 통해서 접근해야 합니다. bus의 자세한 동작 원리에 대해서는 나중에 더 자세히 다뤄보도록 하고 지금은 CPU와 memory 사이에 data가 어떻게 오가는지에 대해 간략히 살펴보겠습니다.

아래 그림은 CPU와 memory 사이에 data를 주고 받는 bus structure를 표현한 예시입니다. CPU에서 register 내의 data를 이용한 연산을 처리하는 것은 register file과 ALU 사이의 transaction만 필요하기 때문에 동작을 구현하기 어렵지 않지만 main memory와 transaction 해야 하는 경우는 그렇지 않습니다. 그림에서와 같이 system bus와 memory bus를 통한 transaction이 수행되어야 memory에 access할 수 있기 때문에 그 동작이 더 복잡합니다. 또한 I/O bridge에는 memory 뿐만 아니라 키보드, 마우스 등의 다른 device와도 transaction이 진행되기 때문에 이를 고려해야 합니다. 지금은 main memory와의 transaction만을 살펴보도록 하겠습니다.

- Read transaction

먼저 movq A, %rax라는 instruction을 수행하는 것을 생각해 보겠습니다. 이는 %rax register에 address A의 data를 load하는 instruction으로 memory에서 data를 가져오도록 해야 합니다. 이를 read transaction이라 합니다. memory read transaction의 과정은 아래 그림과 같이 진행됩니다. 먼저 system bus와 memory bus를 통해 main memory로 address A를 전달합니다. main memory는 address signal을 받아 A에 저장된 data x를 반대로 CPU로 보내줍니다. bus를 통해 전달받은 data x는 %rax register에 저장되면서 read transaction이 마무리됩니다.

- Write transaction

다음으로 movq %rax, A instruction을 보겠습니다. 앞의 예시와는 반대로 %rax register에서 main memory의 address A로 data를 store하는 instruction으로, write transaction에 해당합니다. 이는 아래 그림과 같이 진행됩니다. read transaction과 마찬가지로 먼저 main memory에 address A를 전달합니다. address를 전달받은 main memory는 data를 전달받기 위해 기다립니다. CPU에서는 %rax에 저장된 data x를 copy해 bus로 전달해주고 최종적으로 main memory에서 data를 전달받아 address A에 x를 저장합니다.

Locality

위의 CPU-memory transaction에서 잠시 본 것과 같이 memory에서 data를 가져오거나 저장하는 transaction은 register file 내에 저장된 data를 활용하는 것에 비해 매우 큰 overhead가 존재합니다. 또한 main memory에 사용되는 DRAM의 경우 data를 read, write하기 위한 속도가 SRAM에 비해 매우 느려 이에 대한 overhead도 존재합니다. 하지만 overhead가 어느 정도 완화될 수 있는데, 이는 principle of locality 때문입니다. program이 실행될 때 data와 instruction은 최근 사용한 것과 가까운 위치 또는 동일한 경우가 많다는 것이 principle of locality이며, 비슷한 위치의 data 또는 instruction을 자주 사용하는 program 일수록 locality가 높다고 말합니다. locality에는 다음의 두 가지 종류가 있습니다.

• temporal locality 가장 최근에 reference된 item은 가까운 시간 내에 다시 사용될 가능성이 높다.
• spatial locality 근처의 address에 있는 item은 연이어 reference될 가능성이 높다.

아래의 code를 예시로 두 locality에 대해 자세히 알아보겠습니다.

sum = 0;
for (i = 0; i < n; i++)
    sum += a[i];
return sum;

위의 code는 array a의 n개의 element를 더하는 code입니다. 여기서 data reference의 경우 a의 element가 순차적으로 reference되는 것은 spatial locality에 해당하며, sum이 매 iteration마다 reference되는 것은 temporal locality에 해당합니다. instruction의 경우 instruction들이 순차적으로 실행되는 것이 spatial locality에 해당하며 loop을 통해 동일한 code를 반복해서 실행하는 것을 temporal locality라 합니다.

locality를 고려하여 code를 작성하는 것과 그렇지 않은 것에는 code 동작 시간에 큰 차이를 보여줍니다. 예시로 아래 두 code를 먼저 보겠습니다.

// code1: row majer
int rowmajor(int array[M][N]) {
    int i, j, sum = 0;

    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            sum += array[i][j];
        }
    }

    return sum;
}

// code2: column major
int columnmajor(int array[M][N]) {
    int i, j, sum = 0;

    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            sum += array[j][i];
        }
    }

    return sum;
}

두 code는 array에 access하는 방식에 차이를 가지고 있습니다. asymtotic analysis로는 두 code의 동작 시간에 차이가 없지만 실제로 code를 실행해보면 rowmajor()가 훨씬 빨리 실행되는 것을 확인할 수 있습니다. 간단하게 M = 3, N = 3인 경우에 두 함수의 access order를 살펴보면 다음과 같습니다.

rowmajor()는 memory address 순서에 맞춰 access하는 반면 columnmajor()는 비슷한 address를 연속적으로 access하는 경우가 없는 것을 볼 수 있습니다. M, N의 크기가 커질수록 columnmajor()에서 access하는 address의 stride가 더 커져 spatial locality가 더 나빠지게 되고, 이는 후에 설명한 cache memory에 관련해 성능을 크게 떨어뜨리는 요인이 됩니다.

Memory hierarchy

위의 그림은 일반적인 컴퓨터의 memory hierarchy에 대한 모식도입니다. 그림에서 위로 갈수록(high level) 더 빠르지만 값이 비싸 많이 사용할 수 없는 memory이고, 반대로 아래로 갈수록(low level) 값이 싸 많은 용량을 구축할 수 있지만 그 속도가 느린 memory입니다. 이 중에서 이번에는 cache에 대해 집중적으로 파악해 보겠습니다.

- Caching in the memory hierarchy

cache는 SRAM으로 만들어지며 access하기 위해 수 cycle이 필요합니다. 수십에서 수백 cycle이 필요한 DRAM에 비해 속도가 빠른 대신 MB 단위의 data만 저장할 수 있기 때문에 processor에서 access하기 위한 data를 DRAM에서 가져와 저장해두는 식으로 활용합니다. 마찬가지로 L2 cache와 L1 cache 사이에도 동일하게 data를 가져와 저장합니다. 이렇게 느린 저장공간의 data object를 빠른 저장공간에 가져와 저장해두는 행위를 caching이라 합니다. 아래 그림과 같이 더 느린 level k+1 storage의 data를 더 빠른 level k storage에 저장하고, 최종적으로 가장 높은 level의 storage인 register에 가져와 process에서 연산을 진행합니다.

data를 lower level의 memory unit에서 가져올 때 해당 memory에 data가 존재하는 지의 여부에 따라 동작이 달라야 할 것입니다. 예를 들어 위의 그림에서 k = 1, 즉 L1 cache라 생각할 때 process에서 3을 가져오려 한다면 L1 cache에서 data를 바로 가져올 수 있습니다. 이와 같이 원하는 data가 cache에 존재할 때 cache hit이라 합니다. 반면 process에서 1을 가져오려 한다면 이는 L1 cache에 없으므로 L1 cache에서 data 하나를 evict하고 L2 cache에서 1을 가져와야 합니다. 이와 같이 원하는 data가 cache에 없는 경우를 cache miss라 합니다. cache miss는 다음과 같은 이유로 발생할 수 있습니다.

• cold miss (compulsory miss) 비어있는 cache block에 access해 cache miss가 발생하는 경우

• conflict miss placement policy에 의해 cache miss가 발생하는 경우 (같은 cache block에 mapping된 data를 access하려 할 때 발생)

• capacity miss program의 working set이 cache size보다 커 cache miss가 발생하는 경우

cache miss가 발생하는 경우 더 느린 memory unit에 access해 data를 가져와야 하기 때문에 그 penalty가 매우 큽니다. 따라서 cache miss를 줄이는 것은 processor의 성능을 높이는 데 매우 중요합니다. 실제로 program을 실행시키면 cache miss가 자주 일어나지 않는 것을 볼 수 있는데, 이는 locality에 의한 영향입니다. locality가 높은 경우 같은 address에 자주 access하게 되며 cache에 해당 data가 존재할 확률이 높기 때문에 cache hit이 더 자주 일어나게 됩니다.

앞서 rowmajor()와 columnmajor()를 다시 살펴보면, rowmajor()는 연속된 address의 data를 access하는 반면 columnmajor()는 그 간격이 매우 커질 수 있습니다. 일반적으로 cache에 data를 저장할 때에는 여러 data를 모은 block 단위로 저장하기 때문에 첫 번째 address에 access한 경우 그 다음 몇 개의 address에 저장된 data 또한 cache에 같이 올라오게 됩니다. 이로 인해 rowmajor()로 구현된 code가 더 빠르게 실행되는 결과를 볼 수 있게 됩니다.

reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

컴퓨터에 대해서 공부를 하면서 한 번쯤은 buffer overflow라는 말에 대해서 들어본 적이 있을 것입니다. buffer overflow는 out-of-bound array element를 write하는 과정에서 stack에 저장된 data가 corrupted되는 것을 말합니다. stack에는 local variable, return address 등 stack frame에서 필요한 data들을 저장하고 있는데, 해당 data들을 corrupt하면서 process의 동작에 매우 큰 문제를 불러 일으킬 수 있습니다.

아래의 code를 예시로 buffer overflow가 일어나는 이유에 대해 살펴보겠습니다.

char *gets(char *s) {
    int c;
    char *dest = s;
    while ((c = getchar()) != '\n' && c != EOF)
        *dest++ = c;
    if (c == EOF && dest == s)
        /* No characters read */
        return NULL;

    *dest++ = '\0'; /* Terminate string */
}

/* Read input line and write it back */
void echo() {
    char buf[8]; /* Way too small! */
    gets(buf);
    puts(buf);
}

위의 code에서 gets function은 예전의 library에 존재하던 standard input을 read하는 역할을 하며, echo function에서 buf array에 input을 저장해 다시 출력하는 역할을 하고 있습니다. 여기서 문제가 되는 것은, gets function에 정해진 input size의 bound가 없어 buf array의 size를 넘어가는 input을 받을 수도 있다는 점입니다. 아래 그림은 echo function의 stack frame을 그림으로 나타낸 것입니다. buf는 local variable이므로 echo의 stack frame에 존재하며 stack의 top에서부터 순서대로 input char가 저장됩니다. 만약 input size가 buf의 size보다 매우 크게 들어오면 이전 function의 frame에 존재하는 return address나 local variable을 corrupt하게 됩니다.

- Stack smashing attack

위의 code와 그림을 다시 보면 echo의 stack frame에 buf를 가지고 있는 address는 caller의 stack frame으로부터 어느 정도 간격을 둔 후에 존재하는 것을 알 수 있습니다. 그림에서는 16byte의 빈 공간을 둔 상태에서 8byte의 buf array가 있는 것을 볼 수 있습니다. 따라서 23byte input(null character \n을 포함해 24byte)이 주어지면 return address는 input에 영향을 받지 않을 것이고, 그보다 큰 input이 들어오면 return address를 corrupt할 수 있습니다. 만약 attack을 위해 목표로 하는 return address를 알고 있다면, 임의의 24byte input에 return address를 붙여 input으로 주면 return address를 원하는 대로 바꿀 수 있을 것입니다. 이와 같이 buffer overflow를 통해 stack에 저장된 data를 corrupt하는 방법으로 이루어지는 attack을 stack smashing attack이라 합니다.

여기서 더 나아가서, return address 뒤에는 caller가 가지고 있는 local variable이 저장되어 있거나, echo를 call하기 이전에 register의 값을 push한 data가 존재하기 때문에, 만약 input string을 더 길게 만들어준다면 이를 modify할 수도 있습니다.

- Code injection attack

stack smashing을 통해 return address를 바꾸는 attack에 대해서 살펴보았는데, 이를 활용하여 attacker가 원하는 code를 실행할 수 있도록 하는 attack이 가능해집니다. executable code의 binary code를 가지고 있다면, 해당 code를 input string으로 주면서 return address를 code의 시작점을 가리키는 address로 바꿈으로써 executable code를 실행할 수 있게 됩니다. 이렇게 input으로 입력한 code를 exploit code라 하며, exploit code로 jump해 code를 실행하도록 하는 attack을 code injection attack이라 합니다.

Thwarting buffer overflow attacks

앞서 설명한 buffer overflow attack이 있다면 이를 막기 위한 여러 가지 장치들이 존재할 것입니다. 이에 대해서 몇 가지 살펴보도록 하겠습니다.

- Stack randomization

exploit code를 활용한 code injection attack을 위해서는 exploit code가 쓰여지는 address가 stack 내에 존재하기 때문에 해당 code로 jump하기 위해 stack의 address를 알고 있어야 합니다. 즉, stack address를 user가 모르게 하는 것은 code injection attack을 막기 위한 하나의 방법이 될 수 있습니다. 만약 program이 실행될 때마다 stack address의 위치가 달라진다면 user 입장에서 정확한 address를 찾기 어려울 것이므로 attack을 막을 수 있습니다. 아래의 virtual memory를 나타낸 그림으로 더 자세히 설명하자면, 그림에서는 stack이 kernal 영역 바로 밑에 붙어 address가 정해진 것으로 나타났지만 그 사이 간격을 randomize하여 stack의 address가 매 실행마다 바뀌도록 만들어줄 수 있습니다. stack 뿐만 아니라 나머지 영역들도 사이의 gap을 randomize하여 user가 address를 알지 못하도록 할 수 있습니다. 이는 attacker의 입장에서 정확한 address를 알지 못하도록 만들기 때문에 attack이 더 어려워지도록 할 수 있습니다.

stack randomization을 뚫고 attack이 이루어지도록 한 attack의 방법으로 nop를 활용한 exploit code를 심어주는 것이 있습니다. nop는 x86-64 ISA에서 아무 operation도 하지 않는 명령어이지만 1byte의 memory를 차지합니다. stack address가 random한 값이어도 어느 정도는 range가 존재하기 때문에, exploit code를 작성하기에 앞서 무수히 많은 nop를 추가해준 후(nop sled) 목표로 하는 return address가 nop sled 내에 항상 위치할 수 있도록 설정해주면 exploit code를 항상 실행할 수 있을 것입니다.

- Stack corruption detection

이번에는 stack corruption이 일어나는 상황을 detect하기 위한 방법에 대해 살펴보겠습니다. detection을 위한 idea는 stack frame이 변화할 때 그 사이에 canary value(or guard value)라는 특수한 값을 저장해주는 것입니다. canary value는 program이 실행될 때마다 random하게 결정되며 input을 입력받는 array와 기존에 저장된 data 사이에 위치하게 됩니다. 아래 그림은 위의 echo function의 stack frame에 canary가 추가된 것을 나타낸 것입니다. canary가 중간에 위치하면서 buffer overflow가 일어나게 되면 canary value에 input으로 주어진 string이 overwrite됩니다. canary는 항상 stack에 저장된 data보다 top에 가까운 위치에 있으므로 stack에 저장된 data보다 canary value가 먼저 변화하게 됩니다. program이 진행됨에 따라 stack에 저장된 data를 활용하기 전에 canary를 확인해 canary의 값이 변화한 것을 감지하면 program이 error message를 보내 abort시킬 수 있습니다. 이를 통해 buffer overflow를 통해 stack에 저장된 data들이 corrupt되는 것을 막을 수 있습니다.

- Limiting executable code regions

마지막으로 살펴볼 방법은 executable code를 가질 수 있는 region을 제한하는 것입니다. code injection attack은 input으로 exploit code를 주어 stack에서 code를 실행하는 것으로 이루어집니다. 이를 막기 위해 실행할 수 있는 code가 저장된 memory region을 제한하는 방법이 있습니다. 위의 virtual memory 그림을 다시 보면, program을 compile했을 때 실제 실행되는 code가 존재하는 영역은 .text 부분입니다. 따라서, 해당 부분을 제외한 나머지 영역을 read, write만 할 수 있도록 flag bit을 추가해 표시한다면 code를 실행하려 할 때 해당 flag를 보면서 실행할 수 있는 영역의 data인지 파악할 수 있습니다. 따라서, stack 영역을 read/write만 가능하도록 제한한다면 code injection attack으로부터 보호할 수 있습니다.

reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

이번에는 data structure 중에서 tree에 대해 알아보겠습니다. tree는 기본적으로 linked list와 같이 여러 개의 node들을 연결한 형태를 가지고 있는 data structure입니다. 여기서 tree structure가 되기 위한 몇 가지 rule이 있습니다.

• first node(a.k.a. root node)가 하나 존재한다.
• 각 node는 여러 개의 node를 point할 수 있다.
• root node를 제외한 모든 node는 자신을 가리키는 node를 정확히 한 개 가질 수 있다.

다음 그림은 위의 세 가지 규칙을 모두 만족하는 tree의 예시입니다. A가 위의 정의에서 root node에 해당하며, 각 node가 가리키는 다른 node의 수는 각각 다른 것을 볼 수 있습니다. 또한 A를 제외한 모든 node는 자신을 가리키는 node가 정확히 하나 존재하는 것을 볼 수 있습니다.

- Terminology

tree에 대해 이야기하기 전에 tree에 적용되는 몇 가지 용어에 대해서 살펴볼 필요가 있습니다. 이에 대해서 먼저 알아봅시다.

• Parent, Children, Sibling 앞선 정의에서 각 node는 여러 node를 point할 수 있고 root를 제외한 모든 node는 자신을 가리키는 node를 오직 하나만 가질 수 있다고 설명했습니다. 여기서 각 node가 가리키는 다른 node들을 children(child) node, 자신을 기리키고 있는 node를 parent node라 합니다. 또한 동일한 parent를 가지고 있는 node들을 sibling이라 합니다. 아래 그림은 node B의 parent, children, sibling을 각각 표시한 것입니다.

• Degree 각 node마다 가지고 있는 children의 수를 해당 node의 degree라 합니다. 예를 들어, 위의 그림에서 node A의 degree는 3, node D의 degree는 1이며 node C의 degree는 0입니다.

• Leaf nodes, Internal nodes node C와 같이 degree가 0인 node를 모두 leaf node라 하고, root node를 포함해 그 외의 node들은 모두 internal node라 합니다. 위의 그림에서는 node C, E, F, H, I가 모두 leaf node이며 node A, B, D, G는 모두 internal node입니다.

• Path, Depth, Height 한 node로부터 다른 node까지 자신의 child만을 point하면서 이동할 수 있는 경로가 존재하는 경우, 이를 두 node 사이의 path라 한다. 예를 들어, 위의 tree에서 node D와 node I의 경우 D $\rarr$ G $\rarr$ I로 child를 pointing하며 이동하는 path가 존재합니다. path는 존재하지 않거나 유일하게 존재하며, 예시의 경우 (D, G, I)의 sequence를 제외하고는 다른 path가 존재하지 않습니다. 또한 path에서 다른 node를 찾아 이동하는 횟수를 path의 length라 하며 위의 예시는 length가 2입니다. 또한 자기 자신으로 향하는 path의 경우 그 length는 0으로 정의합니다. root node는 항상 다른 node로 향하는 path가 unique하게 존재합니다. root에서 임의의 node X로 향하는 path를 찾을 때 해당 path의 length를 X의 depth라 합니다. 예를 들어 위의 tree에서 node E는 root로부터 (A, B, E)의 path를 통해 찾을 수 있으므로 node E의 depth는 2입니다. 모든 node의 depth를 구했을 때 depth들의 maximum을 구할 수 있을 것입니다. depth의 maximum value를 해당 tree의 height로 정의합니다. 위의 tree는 maximum depth가 node H, I에서 3이므로 height 3의 tree입니다. 단일 node만으로 구성된 tree의 경우 자기 자신으로 향하는 path의 length가 0이므로 해당 tree는 height가 0입니다.

• Ancestor, Descendent 두 node X, Y에 대해 X에서 Y로 향하는 path가 존재하는 경우 X를 Y의 ancestor, Y를 X의 descendent라 합니다. 예를 들어, 위의 tree에서 path (D, G, I)의 경우 D는 I의 ancestor이며 I는 D의 descendent입니다. 정의에 의해 자기 자신으로 향하는 path의 경우 자기 자신이 ancestor이자 descendent가 됨을 알 수 있습니다. 이를 피하기 위해 자기 자신을 ancestor 또는 descendent group에서 제외하는 strict ancestor, strict descendent를 정의하기도 합니다.

• Subtree 임의의 node X에 대해서, 해당 node와 그 node의 모든 descendent를 모은 것은 X를 root로 하는 하나의 tree를 형성합니다. 이와 같이 tree의 어떤 node를 root로 해 모든 descendent를 포함하는 tree를 subtree라 합니다. 위의 tree에서는 node D를 root로 했을 때 그 descendent인 node G, H, I를 포함하는 tree가 하나의 subtree가 될 수 있습니다.

- Implementation of abstract tree

다른 tree들을 알아보기 이전에 먼저 abstract tree를 code로 구현해보도록 하겠습니다. abstract tree는 다음 요소들을 포함하고 있습니다.

• value
• pointer of parent node
• pointers of children nodes in linked list

따라서, tree class의 definition은 다음과 같습니다.

template <typename T>
class SimpleTree {
public:
    SimpleTree(T const& = T(), SimpleTree *= nullptr);

    T get_value() const;
    SimpleTree<T> *get_parent() const;
    int get_degree() const;
    bool is_root() const;
    bool is_leaf() const;
    SimpleTree<T> *get_child(int n) const;
    SimpleTree<T> *attach(T const &obj);

    int size() const;
    int height() const;

private:
    T value;
    SimpleTree *parent;
    List<SimpleTree *> children;
};

define해야 할 함수가 많기 때문에 나누어 작성하도록 하겠습니다. 먼저 비교적 간단하게 구현할 수 있는 is_leaf() 함수까지의 구현을 먼저 살펴보겠습니다.

template <typename T>
SimpleTree<T>::SimpleTree(T const &obj, SimpleTree *p)
    : value(obj), parent(p) {
    // empty constructor
}

template <typename T>
T SimpleTree<T>::get_value() const{
    return value;
}

template <typename T>
SimpleTree<T> *SimpleTree<T>::get_parent() const{
    return parent;
}

template <typename T>
int SimpleTree<T>::get_degree() const{
    return children.size();
}

template <typename T>
bool SimpleTree<T>::is_root() const{
    return get_parent() == nullptr;
}

template <typename T>
bool SimpleTree<T>::is_leaf() const{
    return get_degree() == 0;
}

위의 function들은 모두 class에서 정의한 member variable을 return하거나 function call의 결과를 활용해 간단하게 구현할 수 있습니다. 다음으로 구현이 까다로울 수 있는 부분인 children node를 찾고 child를 attach하는 function을 보겠습니다.

template <typename T>
SimpleTree<T> *SimpleTree<T>::get_child(int n) const {
    if (n < 0 || n >= get_degree()) return nullptr;

    auto it = children.begin();
    for (int i = 1; i < n; ++i) ++it;

    return *it;
}

template <typename T>
SimpleTree<T> *SimpleTree<T>::attach(T const &obj) {
    auto child = new SimpleTree(obj, this);
    children.push_back(child);
    return child;
}

child를 find할 때 child pointer가 linked list의 형태로 저장되어 있으므로 loop를 활용해 iterator를 찾아 return하는 방식으로 구현한 것을 볼 수 있습니다. 또한 child를 attach하는 것도 새로운 node를 만들어 이를 linked list에 push하는 것으로 구현할 수 있습니다. tree의 size와 height를 구하는 function은 다음 topic에 대한 설명을 이어나간 다음에 다시 돌아와 살펴보겠습니다.

Tree traversal

tree structure를 활용할 때 tree 내의 모든 object를 search해야 하는 경우가 자주 있을 것입니다. 그러기 위해서는 tree에서 linked list의 형태로 저장되어 있는 child들을 효율적으로, 그리고 빠짐없이 search하는 algorithm이 필요할 것입니다. 이번에는 tree의 object를 search하는 두 가지 방법에 대해서 살펴보도록 하겠습니다.

- Breadth-first traversal

breadth-first traversal, 한국어로 너비 우선 탐색은 한 node의 모든 child를 먼저 search한 후 child node들의 child를 탐색하도록 구현한 algorithm입니다. 즉, depth가 0인 node(root node)를 시작으로 depth가 1, 2, ..., $k$인 node를 차례대로 탐색해 나가는 방법을 사용합니다.

breadth-first traversal은 queue를 활용하면 쉽게 구현이 가능합니다. root node를 시작으로 한 node를 방문할 때 그 node의 모든 children을 queue에 push합니다. 모든 children을 push한 후 해당 node에 대한 search가 끝나면 다음으로 search할 node를 queue의 front node로 선택합니다. 이 algorithm은 depth k의 node를 search할 때 모든 depth $k$+1의 node를 push하게 하고 결국 depth k의 모든 node를 search한 후에 depth $k$+1의 node를 search하도록 만듭니다.

- Depth-first traversal

depth-first traversal, 한국어로 깊이 우선 탐색은 node의 한 child를 root로 하는 subtree를 모두 search한 후에 그 다음 child를 root로 하는 subtree를 모두 search하는 것을 반복하는 방법입니다. 즉, root를 시작으로 leaf node에 도달할 때까지 child 하나를 방문하는 것을 recursive하게 반복하며 search를 진행합니다. 이러한 algorithm을 backtracking이라 합니다.

depth-first traversal은 recursive function을 통해 구현할 수 있습니다. node에서 각 child에 access할 때마다 function을 recursive하게 실행해 해당 child의 하위 child를 search할 수 있도록 구현하면 위의 그림과 같은 순서대로 search가 가능합니다. 혹은 stack을 활용하여 child를 모두 stack에 push하고 stack의 top에 access하는 형태로도 구현할 수 있다. stack의 특성으로 인해 항상 child 하나를 root로 하는 subtree를 모두 탐색하기 전에는 다른 child를 탐색할 수 없게 되어 depth-first search가 가능해진다.

breadth-first와 depth-first 모두 node를 각각 한 번씩만 search하게 되므로 time complexity는 $\Theta(n)$이 된다. 하지만 space complexity에는 차이가 있는데, breadth-first search는 어떤 depth $k$에 해당하는 node가 매우 많아진다면 이를 모두 queue에 push해야 하기 때문에 그만큼의 memory가 필요해진다. 따라서 node가 가장 많은 depth의 node 수를 $m$이라 하면 $\Theta(m)$의 space complexity를 가진다. depth-first search의 경우 한 node에서 항상 다음 depth의 node를 search하고 다시 돌아오기 전까지는 이를 memory에 저장해야 하므로 tree의 height만큼의 data를 저장해야 한다. 따라서 height가 $h$인 tree의 경우 $\Theta(h)$의 space complexity를 가진다.

- Recall: Implementation of abstract tree

앞에서 구현한 abstract tree에서 tree의 size와 height를 구하는 function을 살펴보겠습니다. 아래의 code가 size와 height를 구하는 function의 implementation 예시이며, 두 code 모두 depth-first search로 구현되어 있습니다.

template <typename T>
int SmipleTree<T>::size() const{
    int tree_size = 1;

    for (auto child = children.begin(); child != children.end(); child++) {
        tree_size += (*child)->size();
    }

    return tree_size;
}

template <typename T>
int SimpleTree<T>::height() const{
    int tree_height = 0;

    for (auto child = children.begin(); child != children.end(); child++) {
        tree_height = std::max(tree_height, 1 + (*child)->height();
    }

    return tree_height;
}

reference "Data Structure & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss

이번에는 abstract data type 중에서 stack에 대해 살펴보겠습니다. stack은 기본적으로 push, pop을 기본적인 operation으로 수행하는 data structure로, push는 stack에 object를 추가하는 operation, pop은 반대로 object를 stack에서 빼내는 operation입니다. 이 두 operation은 모두 stack의 한 쪽 끝인 top에서 수행하기 때문에 항상 마지막으로 들어온 object가 pop을 수행할 때 가장 먼저 나오게 됩니다. 이러한 성질을 LIFO(last-in first-out) behavior라고 합니다.

stack은 기본적으로 linear한 구조를 가지고 있기 때문에 앞서 살펴봤던 linear data structure인 linked list와 array를 통해서 구현해줄 수 있습니다. 구현할 때 유의할 점은, stack의 operation을 수행할 때 되도록 $\Theta(1)$ time에 수행할 수 있도록 해야 stack을 활용할 때 좋은 성능을 보장할 수 있습니다. 이를 고려하여 linked list와 array를 통해 stack을 구현한 것을 살펴보도록 하겠습니다.

- Stack implementation using linked list

stack을 구현하기 이전에 singly linked list의 operation들에 대한 property를 먼저 살펴보겠습니다. 아래 표는 singly linked list의 find, insert, erase operation에 대해 front와 back에서의 수행 시간을 정리한 것입니다. 우리가 stack을 구현할 때 top에 있는 object를 find하거나 top에 push, pop을 진행하는 operation이 중요하기 때문에 한 쪽 끝에서의 property가 우수해야 합니다. singly linked list의 경우 front에서의 operation time이 모두 $\Theta(1)$이지만, back에서의 operation은 erase에 $\Theta(1)$ time이 필요하므로 front를 stack의 top으로 하여 구현하는 것이 적합합니다.

위의 사실을 이용하여 다음과 같이 stack을 구현할 수 있습니다.

template <typename T>
class stack {
public:
    stack() {};
    bool empty() const;
    T top() const;
    void push(T const &);
    T pop();

private:
    Single_list<T> next;
};

template <typename T>
bool stack<T>::empty() const {
    return list.empty();
}

template <typename T>
T stack<T>::top() const {
    if (empty()) {
        throw underflow();
    }
    return list.front();
}

template <typename T>
void push(T const &obj) {
    list.push_front(obj);
}

template <typename T>
T stack<T>::pop() {
    if (empty()) {
        throw underflow();
    }
    return list.pop_front();
}

위와 같이 기존 c++에 내장된 singly linked list의 function을 가져와서 stack의 functionality를 간편하게 구현할 수 있습니다. 이와 같이 이미 구현된 function을 가져와 새로운 function을 구현하는 것을 function wrapping이라 합니다. 위의 방법 외에도 직접 node를 define해 singly linked list와 같이 동작하도록 function을 직접 만들어 구현할 수도 있습니다.

- Stack implementation using array

아래 표는 array의 operation에 대한 property를 정리한 것입니다. linked list와 달리 front에서의 insert, erase에 대한 성능이 좋지 못한 반면, back에서의 operation은 모두 $\Theta(1)$ time으로 수행할 수 있습니다. 따라서 array로 stack을 구현할 때에는 back을 stack의 top으로 하여 구현하는 것이 적합합니다.

위의 property를 활용해 array로 구현한 stack은 다음과 같습니다.

template <typename T>
class stack {
public:
    stack(int = 10);
    ~stack();
    bool empty() const;
    T top() const;
    void push(T const &);
    T pop();

private:
    int stack_size;
    int array_capacity;
    T *array;
};

template <typename T>
stack<T>::stack(int n) :
stack_size(0),
array_capacity(std::max(1, n)),
array(new T[array_capacity])
{
    // empty constructor
}

template <typename T>
stack<T>::~stack() {
    delete[] array;
}

template <typename T>
bool stack<T>::empty() const{
    return (stack_size == 0)
}

template <typename T>
T stack<T>::top() const{
    if (empty()) {
        throw underflow();
    }
    return array[stack_size - 1];
}

template <typename T>
void stack<T>::push(T const &obj) {
    if (stack_size == array_capacity) {
        throw overflow();
    }

    array[stack_size] = obj;
    ++stack_size;
}

template <typename T>
T stack<T>::pop() {
    if (empty()) {
        throw underflow();
    }

    --stack_size;
    return array[stack_size];
}

linked list를 통해 구현한 것과 가장 두드러지게 나타나는 차이점은 array로 구현할 때에는 array size가 정의되어야 한다는 점입니다. array size를 미리 정의해야 array를 사용할 수 있으므로, array size를 넘는 data를 push하기 위해서는 exception 처리가 필요합니다. exception 방법에는 push 명령을 무시하거나, stack에 공간이 생길 때까지 sleep 시키는 등 여러 가지 방법이 있으나, stack의 functionality를 해치지 않기 위해 array capacity를 증가시키는 구현을 살펴보겠습니다.

array size를 증가시키는 방법에는 다음과 같은 방법이 있습니다.

• constant value만큼 증가 (array_capacity += c;)
• array size를 multiplicate (array_capacity *= c;)

결론부터 말씀드리면 두 번째 방법이 더 좋은 성능을 이끌어내는 방법입니다. array의 size를 증가시키기 위해서는 새로운 array를 allocate받고 기존의 array에서 새로운 array로 data를 copy and paste를 해야 합니다. 이는 기존 array가 가득 차있을 때 진행하게 되므로 $\Theta(n)$ 만큼의 시간이 필요합니다. 하지만, 이를 단순히 하나의 $n$에 대해서 분석하기에는 array size를 증가시키기 위한 operation을 모든 push에 대해 수행하는 것이 아니기 때문에 $n$의 값에 따라 수행하지 않는 경우가 존재하기 때문입니다. 따라서 이를 정확히 분석하기 위한 것이 amortized time analysis입니다.

amortized analysis는 n번의 operation을 진행한 것에 대한 평균을 구하는 것, 즉 $(\sum _{k=1} ^{n} f(k))/n$을 구해 비교하는 것입니다. 위의 두 그림을 통해 더 자세히 알아보겠습니다. 왼쪽의 그림은 size를 1만큼 증가시키는 경우이며 오른쪽 그림은 size를 doubling 경우입니다. size를 1씩 증가시키는 경우 매 push마다 size를 증가시키게 되며 시간 또한 n에 비례하여 증가하게 됩니다. 따라서 amortized tkme은 $(\sum _{k=1} ^{n} k)/n = \Theta(n)$이 됩니다. 반면 size를 doubling 경우는 size가 2의 거듭제곰인 경우에만 array size만큼 data를 copy하게 되므로 $n=2^q$일 때 amortized time은 $(\sum _{k=1} ^{q} 2^k)/2^q = 2^{q+1} / 2^q = \Theta(1)$이 됩니다. 따라서 array size를 배수로 증가시키는 것이 더 efficient한 구현이 됩니다.

Queue

다음은 queue에 대해서 알아보겠습니다. queue는 stack과 비슷하게 push와 pop을 기본 operation으로 하는 linear data structure입니다. 하지만 두 data structure의 두드러지는 차이점은 queue는 push, pop을 하는 위치가 서로 반대쪽 끝에 위치한다는 점입니다. 따라서 마지막으로 push한 object는 가장 마지막에 pop이 이루어지며 이러한 특성을 FIFO(first-in first-out) behavior라고 합니다. queue 또한 linear data structure이므로 linked list와 array를 통한 구현이 가능하며, 마찬가지로 push와 pop operation의 time이 $\Theta(1)$이 되도록 구현해야 efficient하다고 할 수 있습니다.

- Queue implementation using linked list

queue를 구현하기 위해 앞의 singly linked list의 property를 다시 살펴보겠습니다. 구현에서 고려할 수 있는 두 가지 option으로 push를 front, pop을 back에서 하도록 하는 것과 push를 back에서, pop을 front에서 하도록 하는 것이 있습니다. 여기서 첫 번째 option은 pop을 진행할 때 $\Theta(n)$ time이 필요하므로 두 번재 option이 더 efficient한 구현이 될 것입니다.

마찬가지로 linked list를 활용해 queue를 구현한 code는 다음과 같습니다. stack과 마찬가지로 function wrapping을 활용해 구현해 주었으며 node를 define하는 구현도 list의 functionality를 활용해 만들어줄 수 있습니다.

template <typename T>
class queue{
public:
    bool empty() const;
    T front() const;
    void push(T const &);
    T pop();
private:
    single_list<T> list;
};

template <typename T>
bool queue<T>::empty() const{
    return list.empty();
}

template <typename T>
T queue<T>::front() const{
    if (empty()) {
        throw underflow();
    }
    return list.front();
}

template <typename T>
void queue<T>::push(T const &obj) {
    list.push_back(obj);
}

template <typename T>
T queue<T>::pop() {
    if (empty()) {
        throw underflow();
    }
    return list.pop_front();
}

- Queue implementation using array

마찬가지로 앞의 array의 property를 살펴보면, array의 front에서의 insert, erase가 모두 $\Theta(n)$ time이 필요하므로 단순한 array로는 efficient한 구현이 어렵습니다. 따라서 front와 back에서의 property를 모두 우수하게 만들기 위해서는 double ended array로 구현하는 것이 좋습니다.

• array

• double ended array

double ended array를 통해 구현한 queue는 다음과 같습니다.

template <typename T>
class queue{
public:
    queue(int = 10);
    ~queue();
    bool empty() const;
    T front() const;
    void push(T const &);
    T pop();
private:
    int queue_size;
    int array_capacity;
    int ifront;
    int iback;
    T *array;
};

template <typename T>
queue<T>::queue(int n) :
queue_size(0),
array_capacity(std::max(1, n)),
ifront(0),
iback(-1),
array(new T[array_capacity])
{
    // empty constructor
}

template <typename T>
queue<T>::~queue() {
    delete[] array;
}

template <typename T>
bool queue<T>::empty() const{
    return (queue_size == 0)
}

template <typename T>
T queue<T>::front() const{
    if (empty()) {
        throw underflow();
    }
    return array[ifront];
}

template <typename T>
void queue<T>::push(T const &obj) {
    if (queue_size == array_capacity) {
        throw overflow();
    }
    if (iback == array_capacity) iback = -1;
    ++iback;
    array[iback] = obj;
    ++queue_size;
}

template <typename T>
T queue<T>::pop() {
    if (empty()) {
        throw underflow();
    }
    if (ifront == array_capacity) ifront = 0;
    --queue_size;
    ++ifront;
    return array[ifront - 1];

위의 code에서 주의깊게 볼 점은 ifront와 iback의 존재와 push, pop에서의 예외 처리 부분이다. ifront는 queue의 front에 해당하는 index이고 iback은 queue의 back에 해당하는 index이다. 일반적인 array라면 이들이 index를 벗어날 경우 overflow가 발생해 원하는 동작이 나타나지 않을 것이다. 이를 방지하기 위해 circular array를 적용시킨 구현이다. circular array는 array의 양 끝을 연결해 마지막 index의 다음 index를 array의 맨 처음으로 만들어주는 structure로 queue에서 index에 의한 overflow가 발생하지 않도록 방지해주는 역할을 해준다.

stack의 구현과 마찬가지로 queue 또한 array가 가득 차면 size를 증가시켜야 한다. 여기서 queue를 circular array로 구현했기 때문에 단순히 size를 증가시키고 data를 copy and paste하면 queue 내의 data 사이에 빈 공간이 생겨 올바른 동작을 하지 못하게 된다. 이를 해결하는 데에는 두 가지 방법이 있다. 하나는 front를 array의 index가 0인 곳으로 위치하도록 조정하는 방법이며 다른 하나는 front가 포함된 block을 array의 뒤쪽에 꽉 차도록 하는 방법이다. 어떤 방법을 선택하는 지는 design에 대한 차이이며 두 방법 모두 올바른 queue의 동작이 진행되도록 만들어준다.

Reference "Data Structure & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss

이번에는 process에서 function call을 진행할 때의 mechanism을 설명드리고자 합니다. function call을 진행할 때 해당 function이 있는 address로 단순히 jump를 하게 되면 여러 문제가 발생합니다. 하나는 called function이 모두 진행된 후 return하려 할 때 어느 address로 jump해야 하는지 알 수 없다는 점입니다. 단순히 register에 저장할 수도 있겠지만 function을 recursive하게 여러 번 call하게 되면 return address가 overwrite되어 돌아가지 못할 수 있을 것입니다. 또 다른 문제로는 이전에 사용하던 variable이 register에 남아있는 경우 또한 overwrite되어 사라질 수 있다는 점입니다. 이러한 문제가 발생하지 않도록 function call은 다음과 같은 mechanism이 필요합니다.

1. Passing control
   • procedure code(function)를 시작하고 return point로 돌아오는 것을 control
2. Passing data
   • argument를 전달하고 value를 return
3. Memory management
   • prodecure를 수행하는 중에 memory allocate하고 return 시 deallocate

이와 같은 mechanism은 desiner의 choice에 따라 여러 형태로 나타날 수 있습니다. 이를 Application Binary Interface(ABI)라고 합니다.

Stack structure

C를 포함한 여러 programming language에서는 위와 같은 mechansim을 구현하기 위해 stack data structure를 사용합니다. function을 call하고 return하는 과정에서 가장 마지막에 call된 function이 가장 먼저 return을 수행하는 convention을 따르기 때문에 LIFO(Last-in First-out) 구조를 가지는 stack을 주로 사용합니다.

memory space에서 stack을 설명하기 위해 잠시 virtual memory 에 대해 간략히 설명하고자 합니다. virtual memory는 architecture의 memory layout이라고 볼 수 있습니다. 각각의 address는 기본적으로 아래 그림의 구조로 구성되어 있으며 각 memory 영역의 간격을 결정해주는 randomized value는 OS에 의해 결정됩니다. 이중 stack은 kernal의 바로 아래 부분에 위치해 있으며 address가 감소하는 방향으로 grow합니다. stack의 가장 작은 address 부분(stack이 grow하는 방향의 경계)을 stack top이라 하며, stack을 제어하기 위해서 stack pointer(%rsp)가 그 위치를 가리킵니다.

stack의 동작 원리를 살펴보기 위해 간단히 pushq instruction과 popq instruction의 동작에 대해 살펴보겠습니다. pushq instruction을 진행하는 과정은 먼저 %rsp를 8 감소시킨 후(word size가 8byte이므로) %rsp의 위치에 operand를 write하도록 이루어집니다. popq는 그 반대로 %rsp의 value를 read한 후 %rsp를 8 증가시키는 과정이 진행됩니다. 이때 stack에 남아있는 data는 따로 지우지 않고 나중에 해당 address로 다시 stack이 grow할 때 overwrite하는 형식으로 동작합니다.

Calling conventions

function call을 수행할 때는 일종의 convention이 존재합니다. 예를 들어 parameter는 어떻게 pass할 것인지(register or stack), old register value를 누가 care할 것인지(caller or callee) 등은 designer가 결정하는 영역입니다. 아래에서는 x86-64 architecture에서의 calling convention에 대해서 살펴보고자 합니다. 이후의 설명은 모두 procedure P에서 procedure Q를 call하는 상황를 가정하겠습니다.

x86-64 architecture에서 procedure가 register의 value를 저장할 공간을 필요로 할 때, stack의 memory space를 allocate 받아 저장할 수 있습니다. 해당 procedure가 allocate 받는 영역은 연속적으로 연결되어 있으며, 이를 stack frame이라 합니다. 현재 executing하는 procedure에 해당하는 stack frame은 항상 stack의 top에 위치합니다. 즉, 현재 procedure P를 수행하고 있으면 stack의 top에는 P의 stack frame이 존재하며 Q를 call하면 stack이 grow해 top이 Q의 stack frame으로 채워지게 됩니다. stack frame에는 register의 value를 저장하고 local variable을 allocate하고 argument를 set up할 수 있습니다.

Control transfer

P에서 Q로 passing control을 하는 것은 program counter(%rip)를 Q의 시작점으로 바꾸는 것 이외에도 여러 가지 처리가 필요합니다. 먼저 Q의 code가 모두 실행되고 return하는 상황에 %rip를 P의 code로 다시 돌려주어야 하기 때문에 이에 대한 record가 필요합니다. 만약 Q에서 P로 return 해야 하는 address를 A라고 한다면 function call 과정에서 stack에 A를 push 해주어야 할 것입니다. 이때 A를 return address라고 합니다. A를 push하는 것은 call instruction 수행에 즉시 following 되어야 합니다. 이후 Q에서 ret instruction 수행 시 A가 pop되어 %rip에 write 하는 동작을 진행합니다. 아래의 code를 통해 더 자세히 살펴보겠습니다.

0x400540 <multistore>:
    ...
    400544:    callq 400550 <mult2>
    400541: mov %rax, (%rbx)
    ...

0x400550 <mult2>:
    400550: mov %rdi, %rax
    ...
    400557: retq 

위의 두 function에서 <multistore>는 address 0x400544의 code를 실행할 때 <mult2>를 call할 것입니다. callq instruction을 실행하기 전 stack pointer %rsp의 value가 0x120이라 하면 callq 실행과 동시에 8만큼 decrease해 0x118로 변화할 것입니다. 이후 %rsp에 return address인 0x400549를 저장하고 program counter %rip는 <mult2>의 가장 첫 부분인 0x400550이 되어 다음 cycle에 <mult2>를 실행할 것입니다. 이후 <mult2>의 instruction들을 수행해 %rsp가 다시 0x118로 돌아온 이후에 retq instruction을 실행하면 %rip에 return address를 write해주고 %rsp는 8만큼 increase해 다시 0x120이 될 것입니다. 따라서 function call 전과 return 후를 비교하면 %rsp가 원래대로 돌아오고 %rip 또한 <multistore>의 다음 instruction을 가리키고 있음을 확인할 수 있습니다.

Data transfer

procedure를 call할 때 control transfer 외에도 data를 argument로 passing하고 return value를 받아야 하기도 합니다. x86-64 architecture에서 이들 data는 대부분 register를 통해서 전달됩니다. argument를 passing할 때에는 %rdi, %rsi, %rdx, %rcx, %r8, %r9의 총 6개의 register를 우선적으로 사용하여 전달하고, return value는 %rax를 활용하여 전달해줍니다.

특수한 경우로 procedure P가 Q를 call하면서 6개를 넘는 argument를 전달해야 하기도 합니다. 이 경우에는 argument를 전달하기 위해 stack을 활용합니다. 6개의 argument는 위에서 언급한 6개의 register를 활용하고, 7번째 argument부터는 stack의 top에 push해 저장합니다. argument가 push된 이후에 program이 call instruction을 수행하기 때문에 해당 argument들은 P의 stack frame에 위치하게 됩니다.

Managing local data

대부분의 경우 procedure들은 local storage 없이 register에 모두 data를 저장할 수 있지만, 다음과 같은 경우는 local data를 memory에 저장할 필요가 있습니다.

• local data를 모두 저장할 충분한 register가 남아있지 않은 경우
• local variable에 address operator &가 적용되어 그 address를 생성할 수 있어야 하는 경우
• array 또는 structure로 저장된 data가 필요한 경우

이 경우 procedure는 stack frame에서 space를 할당받아 local variable을 저장해야 합니다. 이 중 두 번째 것을 예시로 보기 위해 아래 code를 살펴보겠습니다.

long caller() {
    long arg1 = 534;
    long arg2 = 1057;
    long sum = swap_add(&arg1, &arg2);
    long diff = arg1 - arg2;
    return sum * diff;
}

caller:
    subq    $16, %rsp            # allocate 16 byte for stack frame
    movq    $534, (%rsp)        # store 534 in arg1
    movq    $1057, 8(%rsp)        # store 1057 in arg2
    leaq    8(%rsp), %rsi        # compute &arg2
    movq    %rsp, %rdi            # compute &arg1
    call    swap_add
    movq    (%rsp), %rdx
    subq    8(%rsp), %rdx
    imulq    %rdx, %rax
    addq    $16, %rsp            # deallocate stack frame
    ret

caller라는 function에서 swap_add라는 function에 &arg1, &arg2라는 argument를 전달하기 위해 caller가 stack에서 memory를 allocate 받아 arg1, arg2를 저장하고 %rsi, %rdi에 address를 저장하는 것을 볼 수 있습니다. 이와 같이 address를 전달해야 하는 경우 local variable을 stack frame에 저장할 필요가 있습니다.

이 외의 경우는 local data를 register에 저장하는 것이 일반적입니다. 여기서 다른 function을 call할 때 이 local data를 잃지 않도록 저장하는 것이 필요한데, 여기에 두 가지 convention(caller-save, callee save)이 적용될 수 있습니다. caller-save는 callee function을 call하기 전에 미리 data를 저장해 caller가 이를 관리하는 것이고, callee-save는 callee가 caller의 local data가 저장된 register를 관리하는 것입니다.

x86-64 convention에 따라 %rbx, %rbp, %r12 ~ %r15는 callee-saved register로 분류됩니다. procedure P가 Q를 call할 때 Q는 해당 register를 보호하기 위해 이를 수정하지 않거나, register를 사용하기 위해 stack에 push하는 등의 행위를 하고 return 전에 이를 복구하는 행위를 합니다. 위의 register와 %rsp를 제외한 나머지 register들은 모두 caller-saved register로 분류됩니다. 이들은 다른 function에서 자유롭게 사용할 수 있기 때문에 caller가 다른 function을 call하기 이전에 미리 save해야 합니다.

Recursive procedures

앞서 define된 calling convention에 의해, stack frame을 활용한 recursive procedure 또한 자연스럽게 진행될 수 있습니다. 각각의 procedure가 private한 stack frame을 가지고 있고, stack이 local storage를 allocate / deallocate하는 policy를 구축하고 있기 때문에 여러 번 같은 function을 call하더라도 서로 다른 stack frame을 사용해 이를 온전하게 보호할 수 있습니다. 아래의 code를 예시로 해 더 자세히 살펴보겠습니다.

long rfact(long n) {
    long result;
    if (n <= 1) result = 1;
    else result = n * rfact(n - 1);
    return result;
}

rfact:
    pushq    %rbx                # save %rbx
    movq    %rdi, %rbx            # store n in callee-saved register
    movl    $1, %eax
    cmpq    $1, %rdi
    jle        .L35                # if n <= 1, goto **done:**
    leaq    -1(%rdi), %rdi        # compute n - 1
    call    rfact                # call rfact(n - 1)
    imulq    %rbx, %rax
.L35                            # **done:**
    popq    %rbx                # restore %rbx
    ret

recursive하게 구현된 factorial을 계산하는 function의 예시입니다. assembly code를 살펴보면 function의 맨 첫 줄에 %rbx를 stack에 push하고 마지막에 pop을 해 caller function의 %rbx가 callee를 수행하는 동안 보호되도록 동작하고 있습니다. 이는 rfact를 여러 번 recursive하게 call하더라도 stack에 계속 저장되기 때문에 value를 잃지 않고 올바르게 수행시킬 수 있습니다.

reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

CPU의 register에는 앞선 게시물에서 작성했던 64-bit size의 register 외에도 single bit condition code가 존재합니다. x86-64 architecture에는 다음과 같은 4가지 condition code가 있습니다.

• CF: carry flag. arithmetic operation에 의해 발생하는 MSB(Most Significant Bit)의 carry/borrow out을 감지. unsigned overflow를 감지하기 위한 flag
• ZF: zero flag. operation의 결과가 zero인 경우를 감지.
• SF: sign flag. operation의 결과가 negative value인 경우를 감지.
• OF: overflow flag: 2's complement operation의 arithmetic operation에 의해 발생하는 overflow를 감지.

condition codes는 implicit, explicit하게 setting될 수 있습니다. implicit하게 setting되는 경우는 arithmetic operation이 진행된 이후입니다. 예를 들어, t = a + b의 operation이 진행된다고 했을 때, t == 0이면 ZF가, t < 0이면 SF가, overflow가 발생하면 a, b의 data type에 따라 CF, OF가 setting됩니다.

explicit하게 setting은 compare instruction이 수행될 때 진행됩니다. 예를 들어, cmpq b, a instruction은 a - b 연산이 수반되는 logical operation이므로 해당 연산의 결과에 맞는 condition code setting이 진행됩니다. 또 주로 사용되는 instruction으로 두 operand의 and 연산을 진행하는 testq b, a가 있으며 특히 testq %rax, %rax와 같이 %rax의 value가 0인지 check하기 위해 주로 사용합니다.

Condition codes는 set instruction을 이용해 explicit하게 read할 수도 있습니다. setX Dest instruction은 condition code를 Dest의 low-order byte에 저장합니다. setX instruction의 종류는 다음과 같습니다.

Conditional branches

x86-64 architecture에서 conditional branch에는 jX instruction을 사용합니다. jump는 condition code의 값에 따라서 code의 다른 부분으로 %rip를 바꾸는 역할을 합니다. jX address의 형식으로 작성하며 해당 jX instruction에 해당하는 condition code가 1이면 해당 code로 jump하고 그렇지 않으면 다음 code line을 수행합니다. jX instruction의 종류는 다음과 같습니다.

condition code와 conditional branch의 이해를 돕기 위해 example을 보겠습니다. 아래 c code는 x와 y의 차이를 구하기 위한 code이며 이를 assembly code로 만들면 그 아래의 code와 같이 나타납니다.

long absdiff(long x, long y) {
    long result;
    if (x > y) result = x - y;
    else result = y - x;
    return result;
}

absdiff:
    cmpq    %rsi, %rdi    # x:y
    jle        .L4
    movq    %rdi, %rax
    subq    %rsi, %rax
    ret
.L4:        # x <= y
    movq    %rsi, %rax
    subq    %rdi, %rax
    ret

실제로는 return 구문 하나로 나타나는 것이 일반적이지만, 이해를 돕기 위해 naive하게 작성했습니다. c에서는 주석을 // 뒤에 작성하는 것과 달리 assembly file에서는 # 뒤에 작성하는 것을 유의하고 보겠습니다. assembly code에서 cmpq instruction을 수행하면 %rsi와 %rdi의 value에 따라 condition code가 결정될 것입니다. 이후 jle instruction에서 위의 표에서의 definition에 나타낸 condition code가 1인 경우 .L4로 jump할 것이고, 그렇지 않은 경우 그 다음 line을 수행하게 될 것입니다.

Loop

assembly에서 loop의 구현은 앞선 conditional branch를 활용합니다. loop의 condition을 check하는 부분을 condition code로 확인해 조건이 맞는 경우 loop의 맨 앞으로 jump하는 형태로 구현할 수 있습니다. c의 loop는 do-while, while, for의 세 가지 형태가 존재하며, 각각이 어떻게 assembly로 작성되는지 확인해보겠습니다.

Do-While loop

do-while loop는 구문의 형태가 goto와 매우 유사합니다. 아래 code는 동일한 것을 c code, goto version, assembly로 나타낸 것입니다.

// C code
long pcount(unsigned long x) {
    long result = 0;
    do {
        result += x & 0x1;
        x >>= 1;
    } while (x);
    return result;
}

// goto version
long pcount(unsigned long x) {
    long result = 0;
loop:
    result += x & 0x1;
    x >>= 1;
    if(x) goto loop;
    return result;
}

pcount:
    xorq    %rax, %rax    # result
    .L2                    # loop:
    movq    %rdi, %rdx
    andl    $1, %edx    # t = x & 0x1
    addq    %rdx, %rax    # result += t
    shrq    %rdi        # x >>= 1
    jne        .L2            # if(x) goto loop
    ret

assembly와 goto 구문을 비교하면 매우 유사함을 확인할 수 있습니다. goto의 loop:와 if 문이 각각 assembly의 .L2와 jne instruction으로 대응시킬 수 있습니다.

While

while문의 경우 goto와는 다르게 처음부터 condition check를 진행해야 합니다. 따라서 goto version으로 변형 시 중간에 test point를 설정해 loop 시작 지점에서 해당 지점으로 jump하는 구문이 필요합니다. 이를 code로 표현하면 다음과 같습니다.

// c code
long fact(long n) {
    long result = 1;
    while (n > 1) {
        result *= n;
        n = n - 1;
    }
    return result;
}

// goto version
long fact(long n) {
    long result = 1;
    goto test;
loop:
    result *= n;
    n = n - 1;
test:
    if (n > 1) goto loop;
    return result;
}

fact:
    movl    $1 %rax        # result
    jmp        .L5            # goto test
    .L6                    # loop:
    imulq    %rdi, %rax    # result *= n
    subq    $1, %rdi    # n = n - 1
    .L5                    # test:
    cmpq    $1, %rdi    # compare n:1
    jg        .L6            # if(n > 1) goto loop
    ret

앞의 do-while과는 다르게 loop의 시작부터 test:로 jump하는 것을 볼 수 있습니다. condition check를 먼저 확인하는 것으로 loop를 시작하기 위해 다음과 같은 code가 작성되는 것을 볼 수 있습니다.

For

for 구문은 loop에 initialize, test, update가 모두 혼합되어 있는 형태로 작성됩니다. 여기서 initialize는 loop에 들어가기 이전에 먼저 진행하는 것으로 구현이 가능하며, test는 while과 마찬가지로 test point 설정을 통해 구현할 수 있습니다. 또한 update 구문은 test 지점 직전에 추가함으로써 loop body가 모두 수행된 이후에 update가 진행되고 이를 기반으로 test가 진행될 수 있도록 작성할 수 있습니다. 즉, 기본적인 뼈대는 while과 동일하고 적절한 위치에 init, update가 추가된 형태로 볼 수 있어 while과 비슷하게 구현이 가능합니다.

Reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

우리가 code를 작성할 때는 user level에서 이해하기 쉬운 programming language(ex. C, C++, python, java, etc)를 활용합니다. 하지만, CPU와 같은 machine level에서는 우리가 보는 language의 형태로 연산을 진행할 수 없고 0과 1로 이루어진 binary machine code를 통해 처리합니다. 따라서, computer에 대해 이해하기 위해서는 CPU 등의 logic에서 binary를 어떻게 처리하는 지 이해하는 것이 필요합니다.

본격적으로 들어가기에 앞서 몇 가지 용어에 대해 설명하려 합니다.

• Architecture(ISA: instruction set architecture): programmer의 관점에서 바라본 system의 description, system의 functionality를 정의한 것
  • Ex) instruction set specification, registers
• Microarchitecture: architecture의 hardware level implementation
  • Ex) cache sizes, core frequency, pipelines
• Machine code: processor가 실행할 수 있는 byte-level programs
• Assembly code: machine code의 text representation
• Programmer-Visible State: programmer의 관점에서 본 processor의 현재 상태를 표현한 것
  • Ex) PC(Program Counter), register file, condition codes, memory

현재 작성하고 있는 System Programming 시리즈는 Intel의 x86-64 architecture를 기반으로 하여 작성하고 있습니다.

Assembly characteristics

Registers

x86-64 architecture에서 사용하는 register는 다음과 같습니다. 표 위의 숫자는 각 register의 size를 표시한 것이고, 오른쪽은 각 register들의 주요 옹도를 표시한 것입니다. 이들은 빠른 data 연산을 위해 DRAM이나 cache에 포함되지 않고 독립적으로 존재합니다.

register 중에서 특수한 목적으로 사용되는 register로는 %rsp와 %rip(그림에는 표시되지 않은 register)가 있습니다. %rsp는 stack pointer로, 나중에 설명할 virtual memory 개념에서 stack의 위치를 표시하기 위한 stack pointer로 사용합니다. %rip는 program counter로, 다음에 수행할 instruction이 있는 address를 저장하는 register입니다. 그 외의 대부분의 register는 temporary data를 저장하거나 function의 return value를 저장하는 등의 용도로 사용합니다.

Operations

assembly에서 사용하는 operation은 크게 다음과 같이 분류할 수 있습니다.

• memory와 register 사이의 data transfer
  • Load: memory로부터 register로 data를 이동
  • Store: register로부터 memory로 data를 이동
• register, memory data를 이용한 arithmetic / logical function의 수행
• Transfer control
  • unconditional jump
  • conditional jump
  • indirect branch

x86-64 architecture에서 예를 들면, load와 store를 수행하는 instruction으로 mov 등, arithmetic function을 수행하는 instruction으로 add, sub 등, transfer control로 jmp, je 등이 있습니다. x86-64의 특징으로 instruction에 suffix가 붙는 경우가 있는데(movl, movq 등), 이는 instruction의 operand가 가지는 data type을 의미합니다. 예를 들어 l은 4-byte word를, q는 8-byte word를 의미합니다.

assembly language에서 operand를 작성할 때에는 기본적으로 Command, Source, Destination의 순서로 작성합니다. 또한, constant value를 작성할 때에는 $ 기호를 이용하며 register name을 작성할 때에는 %를 활용합니다. 주어진 value를 address로 가지는 memory 내의 value를 호출하고자 할 때에는 소괄호를 활용해 표현해줍니다. 단, system에서 memory-to-memory로 data를 move하는 operation은 작성할 수 없다는 점을 주의해야 합니다. 예시로 아래 5개의 movq operation을 C language로 표현하면 각각 다음과 같은 의미를 가지고 있습니다.

위의 code에 이어서, 더 general한 memory addressing form은 D(Rb, Ri, S)의 형태입니다. 이는 Mem[Reg[Rb]+S*Reg[Ri]+D]를 의미합니다. 이해를 돕기 위해 %rdx의 value가 0xf000이고, %rcx의 value가 0x100일 때의 address comutation 결과를 작성해 두었습니다.

Arithmetic operation 중 addq, subq 등은 동작을 쉽게 연상할 수 있기 때문에 추가적인 설명을 하지 않고 한 가지만 짚어보고자 합니다. 먼저 x86-64 architecture에는 lea라는 operation이 있습니다. lea는 source의 address를 destination에 넣어주기 위한 operation입니다. assembly code의 form이 mov와 유사하기 때문에 혼동을 일으킬 여지가 있기 때문에 예시를 통해 동작을 살펴보겠습니다.

// value of %rdi is $0x100
movq (%rdi, %rdi, 2), %rax        // %rax = Mem[%rdi + 2*%rdi] = Mem[$0x300]
leaq (%rdi, %rdi, 2), %rax        // %rax = %rdi + 2*%rdi = $0x300

예시에서 볼 수 있는 차이점은, mov는 memory에서 data를 가져와 %rax에 넣어주는 동작을 하지만 lea는 %rdi의 value를 연산한 결과를 %rax에 넣는, 즉 memory의 address를 넣어주는 동작을 한다는 것입니다. 따라서 register의 value에 addition, multiplication을 진행한 결과를 구하기 위해서 lea를 사용할 수 있습니다.

Turning C into object code

이번에는 C code로 작성한 파일을 compile할 때 진행되는 과정에 대해 살펴보고자 합니다. 두 개의 c file p1.c, p2.c 에 대해서 이를 gcc로 compile할 때 진행되는 과정은 다음 그림과 같습니다.

먼저 두 개의 c code를 각각 compiler가 compile하여 assembly code(p1.s, p2.s)로 변환해준 후, 이를 다시 assembler가 object program(p1.o, p2.o)로 변환해줍니다. 마지막으로 code에서 include한 library와 두 개의 object program을 linker가 묶어줘 하나의 executable program을 만들어줍니다. c code와 assembly code는 text file이며 object와 executable program은 binary file입니다. linker에 관한 부분은 다음에 짚어보도록 하고 지금은 compiler와 assembler에 의한 결과를 살펴볼 것입니다.

c code를 assembly code로 변환하는 것은 gcc compiler에 의해 수행됩니다. compile 결과를 이해하기 쉽도록 하기 위해 다음과 같은 sum.c file에 대한 결과를 보고자 합니다.

long plus(long x, long y);

void sumstore(long x, long y, long *dest) {
    long t = plus(x, y);
    *dest = t;
}

위의 code를 compile하기 위해 linux command에 gcc -Og -S sum.c를 입력해주면 gcc compiler에 의해 다음과 같은 assemblly code(sum.s)를 얻을 수 있습니다.

    .globl    sumstore
    .type    sumstore, @function
sumstore:
.LFB35:
    .cfi_startproc
    pushq    %rbx
    .cfi_def_cfa_offset 16
    .cfi_offset 3, -16
    movq    %rdx, %rbx
    call    plus
    movq    %rax, (%rbx)
    popq    %rbx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE35:
    .size    sumstore, .-sumstore

위의 assembly code는 gcc version과 compiler setting에 따라 다르게 나타날 수 있다는 점은 유의해야 합니다. code에서 '.'으로 시작하는 line은 assembler와 linker를 위한 guide를 목적으로 만들어진 directive입니다. 이들을 제외한 나머지 line들이 assembly code로 작성된 부분들입니다. 해당 assembly code를 assembler를 통해 다시 object code로 변환해주면 다음과 같은 형태의 object file(sum.o)를 얻을 수 있습니다.

0x0000000: 53 48 89 d3 e8 00 00 00 00 48 89 03 5b c3

맨 앞의 0x0000000는 memory address이며, 해당 address부터 code가 작성되어 있음을 알립니다. object code 내에서는 아직 address가 배정되지 않았지만, 후에 linker를 통해 executable file로 만들어주면 address가 지정됩니다. instruction 각각 1, 3, 5 byte로 구성되어 있으며 이는 architecture 내에서 정의되어 있는 binary encoding을 따릅니다. 위의 object file을 역으로 해석하기 위해 disassemble을 진행하기도 합니다. disassemble은 object file 뿐만 아니라 executable program에 대해서도 진행해줄 수 있습니다. 아래 code는 위의 object code와 linker를 통해 만들어진 executable file의 <sumstore> 부분을 disassemble한 결과입니다.

// disassembly of object file
0000000000000000 <sumstore>:
    0:    53                push    %rbx
    1:    48 89 d3        mov    %rdx, %rbx
    4:    e8 00 00 00 00    callq 9 <sumstore+0x9>
                5:    R_X86_64_PLT32        plus-0x4
    9:    48 89 03        mov    %rax, (%rbx)
    c:    5b                pop    %rbx
    d:    c3                retq

// disassembly of executable file
0000000000400595 <sumstore>:
    400595:    53                push    %rbx
    400596:    48 89 d3        mov        %rdx, %rbx
    400599: e8 f2 ff ff ff    callq    400590 <plus>
    40059e: 48 89 03        mov        %rax, (%rbx)
    4005a1:    5b                pop        %rbx
    4005a2:    c3                retq

object file에서는 정해지지 않았던 <sumstore>와 <plus>의 address가 executable file에서는 결정되어 있는 것을 확인해볼 수 있습니다. 이러한 linking 과정은 후에 더 자세히 살펴보도록 하겠습니다.

Reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

가장 먼저 살펴볼 data structure는 list입니다. abstract list(or list ADT $^\dag$ )는 programmer가 ordering을 define한 linearly ordered data로 정의됩니다. 즉, data들이 linear한 order를 가져 일렬로 나열된 형태의 data structure를 말합니다. list ADT는 기본적으로 다음 operation들을 포함할 수 있으며, 필요에 따라 더 다양한 functionality를 부여할 수 있습니다.

• access to the object (find)
• erase an object (remove)
• insertion of a new object (insert)
• replacement of the object (replace)

list를 구현하기 위한 가장 obvious한 implementation으로는 array와 linked list가 있습니다.

Array

- Definition

array는 contiguous한 memory space를 allocate해 address 순서대로 정렬된 index를 활용하는 data structure입니다. 모든 entry가 index를 이용해 그 위치가 정해져있기 때문에 data를 find하기에 매우 용이하고 data를 저장하기 위한 memory space가 정확히 data size와 동일하다는 장점을 가지고 있지만, array의 중간 지점에 data를 insert하거나 erase하기 위해서 그 뒤의 data들을 모두 copy해 다른 index로 옮겨주어야 한다는 단점이 있습니다.

// image - array //

- Run time of array operation

array에서 각 operation을 특정 위치에서 수행하기 위한 time complexity는 다음과 같습니다.

_<sup>*</sup> only if the array is not full_

표에서 볼 수 있는 특징은 array에서 find와 관련된 operation(Find, Replace, Next, Previous)은 모두 $\Theta(1)$ time으로 수행할 수 있다는 점입니다. insert와 erase는 해당 array index 뒤에 얼마나 많은 entry를 copy해야 하는지에 따라 변하므로, 평균적으로 $O(n)$ time이 필요합니다. 여기에 더해, array에 할당된 memory가 가득 찼을 때, n<sup>th</sup> entry에서 insert를 수행하는 것은 새로운 memory를 할당받는 operation이 필요하고, 할당받은 memory space에 모든 entry를 copy하여 옮겨주어야 하기 때문에 $\Theta(n)$ 만큼의 시간이 필요합니다.

- Two-ended array

표에서 나타난 것과 같이 array의 first entry에 가까울수록 insert와 erase에 불리한 특징을 가지고 있습니다. 이를 해소하기 위해 등장한 개념이 바로 two-ended array입니다. 기존의 array가 한 방향으로만 grow할 수 있는 것과 달리 two-ended array는 양 방향으로 모두 grow할 수 있도록 설계한 형태의 data structure입니다. 이로 인해 first entry에서 insert와 erase를 수행하더라도 $\Theta(1)$ time에 이를 수행할 수 있고, arbitrary position에 대해서도 평균적으로 더 빠르게 수행할 수 있게 됩니다. 하지만, 중간 지점에서 여전히 insert, erase operation에 $O(n)$ time이 필요하며 first entry 방향의 grow를 implement하기 위해 last entry를 가리키는 pointer가 추가적으로 필요합니다.

Linked list

- Definition

linked list는 각 data를 node에 저장하고 한 node가 다른 node를 가리키도록 pointer를 같이 저장해 series of node를 형성하는 data structure입니다. 가장 기본적인 형태의 linked list는 한 방향으로 다음 node를 point하도록 구현한 singly linked list입니다. singly linked list에서 front node를 가리키는 pointer를 head, last node를 가리키는 pointer를 tail이라고 하며, 마지막 node는 어떠한 node도 point하고 있지 않습니다(c++에서 nullptr 활용).

singly linked list는 data의 insert와 erase에 대해 장점을 가지고 있습니다. 모든 data를 node의 형태로 저장하고 있고, 두 data 간의 ordering을 pointer로 지정하고 있기 때문에 insert는 이전 node가 새로운 node를 가리키고 또 새로운 node가 다음 node를 가리키도록 modify하는 것으로 수행할 수 있습니다. 그 외에도 두 linked list를 concatenation하는 것 또한 각 list의 front node와 last node를 연결해주는 것으로 수행할 수 있기 때문에 빠르게 수행할 수 있다는 장점이 있습니다. 반면 arbitrary position에 대해 find operation을 수행하는 것은 항상 맨 첫 node에서부터 pointing하는 다음 node들을 차례로 탐색해야 하기 때문에 수행 시간이 길고, next node의 address를 각 node에 저장해야 하기 때문에 array에 비해 더 많은 memory space를 사용해야 한다는 단점이 있습니다.

- Run time of linked list operation

singly linked list에서 각 operation을 수행하기 위한 time complexity는 다음과 같습니다.

_<sup>*</sup> These assume we have already accessed the k<sup>th</sup> entry - $O(n) operation_ _<sup>**</sup> By replacing the value in the node, we can speed up_

singly linked list의 특징으로는 front node에서의 operation이 모두 $\Theta(1)$ time으로 수행할 수 있어 그 특성이 매우 좋다는 점입니다. 단, arbitrary position에서 operation을 수행하기 위해서는 find operation이 선행되어야 하기 때문에 대부분의 상황에서 $O(n)$ time이 필요합니다. 하지만 code 작성에서 한 번 search한 entry에 대해 여러 operation을 수행한다고 했을 때, find operation을 재차 수행할 필요가 없기 때문에 표에서와 같이 구분할 필요가 있습니다.

arbitrary position에서의 erase operation에 대해 잠시 설명하자면, 이전 node의 주소를 알지 못하기 때문에 이전 node가 다음 node를 point하기 위해서는 일반적으로 $O(n)$ time이 필요합니다. 하지만, 만약 다음 node의 data를 copy해 현재 node를 replace한 후, 다음 node를 erase하는 operation으로 수정한다면 결과는 동일하지만 operation time을 $\Theta(1)$으로 줄일 수 있습니다.

- Doubly linked list

singly linked list는 front node에서의 operation이 매우 빠른 반면, last node에서의 erase operation에 $\Theta(n)$ time이 필요하다는 단점이 있습니다. last node에 대해서도 front node의 좋은 특성을 활용하기 위한 data structure로 doubly linked list가 있습니다. doubly linked list는 한 node에서 두 개의 pointer로 이전 node와 다음 node를 모두 point해 양 방향으로 모두 search하도록 구현한 data structure입니다. last node에서 다음 node에 해당하는 pointer를 nullptr로 정한 것과 같이 front node의 이전 node를 nullptr로 가리키는 것이 필요합니다. doubly linked list는 last node와 first node가 동일한 특성을 가진다는 점과 여전히 concatenation에 유리하다는 장점을 가지고 있으나, singly linked list보다도 더 많은 memory space가 필요하다는 단점이 있습니다.

How to choose appropriate data structure?

지금까지 list를 구현할 수 있는 두 가지 방법인 array와 linked list에 대해 살펴보았다. 실제 data를 list의 형태로 저장하고자 할 때, 두 형태의 data structure 중 하나를 선택할 것이다. 여기서 어떤 structure를 사용할 지는 실제 code에서 어떤 oepration을 자주 사용하게 되는지가 매우 중요할 것이다. 만약 작성한 algorithm이 arbitrary position의 data search를 자주 수행해야 한다면 array가 적합한 data structure가 될 것이다. array는 find operation을 $\Theta(1)$ time에 수행할 수 있지만 linked list는 $O(n)$ time이 필요하기 때문이다. 하지만 algorithm이 data insert와 erase를 자주 수행한다면 여기에 $\Theta(1)$ time으로 수행 가능한 linked list가 더 적합할 것이다.

$^\dag$ ADT(Abstract Data Structure) : models of the storage and access of information

reference "Data Structure & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss

우리가 사용하는 컴퓨터가 어떤 방식으로 동작하는지 궁금했던 적이 있나요? 내가 컴퓨터를 켤 때, 프로그램을 실행시킬 때, hardware와 software가 어떻게 서로 상호작용하는지 등 컴퓨터의 동작에 대해 이해하고자 하는 과목이 바로 system programming입니다. 이번 시리즈에서는 컴퓨터를 system level에서 이해하고 architecture level에서부터 OS, compiler까지 전반적인 구성과 원리 등에 대해 다루려 합니다.

Reference Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

두 알고리즘 A, B가 주어졌을 때, 둘 중 어느 알고리즘이 더 좋다고 판단할 수 있을까요? 단순히 두 알고리즘을 모두 implement하여 실행하는 것으로 비교할 수도 있지만, 이는 얼마나 길게, 얼마나 많이 실행할 지, input data의 size는 어떻게 정해줄 지에 따라 그 결과가 천차만별일 것입니다. 따라서 어떤 것이 좋은 알고리즘인지 분석하기 위해서는 더 general한 방법이 필요합니다.

두 알고리즘을 비교하는 데 가장 주요한 방법은 수학적인 접근입니다. 예를 들어, 두 알고리즘에 모두 size가 $N$인 input이 주어졌을 때 A는 $N$에 비례한 시간이 걸리고, B는 $N^2$에 비례한 시간이 걸린다고 했을 때, 시간 효율성의 측면에서 A가 더 좋은 알고리즘이라고 평가할 수 있습니다.

Asymptotic notation

앞선 예시에서 두 알고리즘의 수행 시간을 각각 input size $N$을 활용하여 나타내주었으며, 대체로 알고리즘의 수행시간은 input size가 증가함에 따라 같이 증가하는 경향을 보입니다. 여기서 우리가 관심있게 봐야 하는 부분은 $N$이 매우 큰 수인 영역입니다. $N$이 작은 경우는 수행시간이 아무리 길어도 수 ms 이내에 끝날 확률이 높아 분석하는 의미가 없으며, 주로 우리가 해결해야 하는 문제는 매우 큰 input size를 필요로 하기 때문입니다.

이를 간단한 식으로 표현하기 위해서 Asymptotic notation을 주로 사용합니다. Asymptotic notation은 $o(n)$, $O(n)$, $\Theta(n)$, $\Omega(n)$, $\omega(n)$의 총 5가지의 symbol을 사용합니다. 각각이 의미하는 것을 수식으로 표현하면 다음과 같습니다.

$$ \begin{aligned} f(n)=o(g(n)) \quad :& \quad \displaystyle\lim_{n\rarr\infin} \frac{f(n)}{g(n)} = 0\ f(n)=O(g(n)) \quad :& \quad \displaystyle\lim_{n\rarr\infin} \frac{f(n)}{g(n)} \lt \infin\ f(n)=\Theta(g(n)) \quad :& \quad 0 \lt \displaystyle\lim_{n\rarr\infin} \frac{f(n)}{g(n)} \lt \infin\ f(n)=\Omega(g(n)) \quad :& \quad \displaystyle\lim_{n\rarr\infin} \frac{f(n)}{g(n)} \gt 0\ f(n)=\omega(g(n)) \quad :& \quad \displaystyle\lim_{n\rarr\infin} \frac{f(n)}{g(n)} = \infin \end{aligned} $$

5개의 symbol 중에서 가장 strong한 조건을 가지고 있는 것은 $\Theta$(big-Theta) notation입니다. $f(n)=\Theta(g(n))$은 $f(n)$과 $g(n)$이 충분히 큰 n에 대해서 같은 rate로 증가한다는 것을 의미하며, 이는 두 수식의 leading term이 동일하다는 것을 의미하기도 합니다. 또한 동일한 $\Theta(f(n))$을 가진 수식은 동일한 class에 속한다고 이야기하기도 하며, class 사이의 관계를 weak ordering(또는 asymptotic larger / smaller)으로 나타내 $\Theta(n) \lt \Theta(n^2)$와 같이 표현하기도 합니다.

또 주로 사용하는 symbol은 $O$(big-O) notation입니다. 이는 어떤 수식의 upper bound를 표현하기 위해 사용하는 경우가 많으며, 어떤 알고리즘이 다른 알고리즘보다 더 efficient하다는 것을 보이기 위해 주로 사용합니다.

Example of asymptotic analysis

asymptotic analysis의 적용을 보여주기 위해 몇 가지 code를 살펴보겠습니다.

// code 1 : swap variables a and b
int tmp = a;
a = b;
b = tmp;

위의 code는 3개의 assignment operation으로 이루어져 있습니다. 일반적으로 integer, logical, bitwise, relational operation이나 memory allocation / deallocation 등은 일정 cycle 내에 수행될 수 있는 operation이고, time complexity는 모두 $\Theta(1)$에 해당합니다. 따라서 위의 code 또한 $\Theta(1)$의 time complexity를 가지는 것을 알 수 있습니다.

// code 2 : loops
int sum_1 = 0;
for (int i = 0; i < n; ++i) {
    sum_1 += i;            // Theta(1)
}

int sum_b = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        sum_2 += 1;        // Theta(1)
    }
}

for (int i = 0; i < n; ++i) {
    // search through an array of size m
    // O(m) algorithm
}

code 2의 첫 번째 for loop을 보면, loop 내의 statement의 time complexity가 $\Theta(1)$임을 알 수 있습니다. for loop에 의해 해당 statement가 n번 반복하기 때문에 n에 비례한 수행시간이 나타나므로 총 time complexity는 $\Theta(n)$이 됩니다.

두 번째 for loop은 두 개의 for loop으로 구성되어 있는 것을 볼 수 있습니다. 앞선 예시를 통해 안쪽의 for loop의 time complexity가 $\Theta(n)$임을 확인했으므로, 이를 n번 반복하는 code이기 때문에 총 time complexity는 $\Theta(n \times n) = \Theta(n^2)$이 됩니다.

마지막 for loop은 안쪽의 statement의 time complexity가 $O(m)$입니다. big-Theta notation이 되지 않은 이유는 best case의 경우 constant time에 수행될 수 있어 경우에 따라 수행시간이 달라지고 그 maximum이 m에 비례하기 때문입니다. 이 경우 다시 for loop에 의해 n회 반복되므로 총 time complexity는 $O(nm)$이 됩니다.

// code 3 : control statements
void func(int arg, int n) {
    if (arg == 0) return;

    for (int i = 0; i < n; ++i) {
        // Theta(1) statement
    }
}

다음으로 control statement에 대해 보겠습니다. 위의 code 3에 해당하는 function을 보면 arg의 값이 0인 경우 true path를 따라 return하며, 그렇지 않은 경우 false path를 따라 for loop을 수행하게 됩니다. 전자의 경우 time complexity가 $\Theta(1)$이고 후자의 경우 앞서 살펴본 바와 같이 $\Theta(n)$이 될 것입니다. 따라서 control statement의 경우 경우에 따라 time complexity가 변화하게 됩니다.

// case 4 : recursive function
int factorial(int n) {
    if (n <= 1) return 1;
    else return n * factorial(n - 1);
}

마지막으로 recursive function의 경우를 보겠습니다. recursive function은 함수 자기 자신을 다시 호출하게 되는데, 앞의 for loop과 비슷하게 함수를 호출한 횟수만큼 안의 statement를 수행하게 됩니다. code 4의 예시는 함수를 n회 만큼 호출하는 경우이며, 내부의 statement가 $\Theta(1)$의 time complexity를 가지므로 전체 time complexity는 $\Theta(n)$임을 알 수 있습니다.

Reference "Data Structure & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss

Data Structure(자료구조)는 컴퓨터에서 data를 효율적으로 관리하고 구조화시키는 방법입니다. data의 종류에 따라서 어떤 자료구조를 사용하는 지에 따라 problem solving에서 효율적인 algorithm을 구현하거나 memory space를 효율적으로 관리할 수 있게 될 것입니다. Data Structure 시리즈에는 list, stack, tree 등의 자료구조가 어떻게 구성되어 있는지, 어떻게 구현할 수 있는지(C++)를 위주로 다뤄볼 예정입니다.

velog에서 첫 게시물로 자료구조를 시작한 이유는 지금 듣고 있는 학부 수업에 자료구조가 있어서...ㅎㅎ 이번 게시물을 시작으로 자료구조에 대해 수업으로 배운 내용을 정리하려 합니다. 지금 듣고 있는 System Programming도 곧 작성하려 하고 이전에 배웠던 Algorithm, Computer Architecture(가능하면,,)와 후에 수강할 DB, Network, 개인적으로 공부할 java와 개발 framework 관련 내용도 차근차근 정리할 생각입니다 : )

Reference "Data Structures & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss