(short1-bal.rep)

[오후 3:24:40] 힙 초기화 완료: 프롤로그(16B), 대형 가용 블록(20,000B), 에필로그(0B)

Q. 현재 상태에서 프롤로그와 에필로그는 왜 내부 단편화가 없을까? A. 내부 단편화(Internal Fragmentation)의 정의는 "유저가 요청한 페이로드(Payload)보다 할당된 블록 크기가 더 커서 남는 버려진 공간.

버그나 누락이 아니라, 페이로드를 전혀 담지 않는 경계 메타데이터 블록이므로, 내부 단편화(패딩) 계산 대상에서 원천 배제되었기 때문.

• 프롤로그 블록 (PRO, 16 Bytes)

  • 내부 구성
    • 8바이트 헤더 + 8바이트 푸터 = 16바이트.
  • 페이로드(사용자 데이터 영역)
    • 아예 없음. 요청 크기 대비 남는 공간(패딩) 이라는 개념 자체가 성립하지 않음

• 에필로그 블록 (EPI, 0 Bytes)

  • 내부 구성
    • 힙의 끝을 표시하는 크기 0짜리 헤더 1개.
    • 전체 크기 자체가 0바이트: 블록 자체의 크기가 0바이트이므로 남는 공간(패딩)이 들어갈 자리도 없음

a 0 2040

[오후 3:50:20] 블록 분할 발생: [20000B] -> [할당 2064B] + [가용 자투리 17936B]

[오후 3:50:20] malloc(2040) 호출 -> 정렬/헤더 포함 요구 크기: 2064B

• 힙에 ptr[0] 과 8바이트 패딩이 안착된 상태.
• 헤더(8) + 페이로드(2040) + 푸터(8) = 2056바이트이지만, 16바이트 정렬 배수를 맞추기 위해 2064바이트로 올림 됨

a 1 2040

[오후 4:07:24] 블록 분할 발생: [17936B] -> [할당 2064B] + [가용 자투리 15872B]

[오후 4:07:24] malloc(2040) 호출 -> 정렬/헤더 포함 요구 크기: 2064B

f 1

• 방금 해제된 ptr[1] 자리가 뒤쪽 가용 공간과 즉시 합쳐져 거대한 녹색 가용 블록인 FB (17936B | a=0)으로 확장

[오후 4:15:36] Case 2: 다음 가용 블록과 병합 -> 새 크기: 17936B

[오후 4:15:36] free(ptr[1]) 호출: 크기 2064B 반납

a 2 48

[오후 4:22:48] 블록 분할 발생: [17936B] -> [할당 64B] + [가용 자투리 17872B]

[오후 4:22:48] malloc(48) 호출 -> 정렬/헤더 포함 요구 크기: 64B

a 3 4072

[오후 7:07:46] 블록 분할 발생: [17872B] -> [할당 4096B] + [가용 자투리 13776B]

[오후 7:07:46] malloc(4072) 호출 -> 정렬/헤더 포함 요구 크기: 4096B

f 3

[오후 7:20:36] Case 2: 다음 가용 블록과 병합 -> 새 크기: 17872B

[오후 7:20:36] free(ptr[3]) 호출: 크기 4096B 반납

a 4 4072

[오후 7:23:30] 블록 분할 발생: [17872B] -> [할당 4096B] + [가용 자투리 13776B]

[오후 7:23:30] malloc(4072) 호출 -> 정렬/헤더 포함 요구 크기: 4096B

f 0

[오후 7:30:29] Case 1: 인접 블록 모두 할당 상태 -> 병합 없음

[오후 7:30:29] free(ptr[0]) 호출: 크기 2064B 반납

f 2

[오후 7:30:57] Case 3: 이전 가용 블록과 병합 -> 새 크기: 2128B

[오후 7:30:57] free(ptr[2]) 호출: 크기 64B 반납

a 5 4072

[오후 7:37:18] 블록 분할 발생: [13776B] -> [할당 4096B] + [가용 자투리 9680B]

[오후 7:37:18] malloc(4072) 호출 -> 정렬/헤더 포함 요구 크기: 4096B

f 4

[오후 7:39:33] Case 3: 이전 가용 블록과 병합 -> 새 크기: 6224B

[오후 7:39:33] free(ptr[4]) 호출: 크기 4096B 반납

f 5

[오후 7:39:59] Case 4: 이전 및 다음 블록 동시 병합 -> 새 크기: 20000B

[오후 7:39:59] free(ptr[5]) 호출: 크기 4096B 반납

컴퓨터 시스템에서 버스는, CPU, 메모리, I/O 장치 간에 신호(데이터, 주소, 제어 신호)를 주고받는 물리적 통신 선로다. 바이트 단위 주소 지정 시스템을 기준으로, 주소 버스가 N 비트일 때, 접근 가능한 최대 메모리 용량은 2^N 바이트다.

예를 들어 32비트 버스는 최대 2^32바이트(4GB), 64비트 버스는 최대 2^64바이트(16EB)까지 직접 주소를 지정할 수 있다.

2. 스택(Stack)을 이용한 메모리 할당과 malloc을 이용한 동적 메모리 할당의 차이점을 설명하고, 각각의 장단점을 비교하여 서술하시오.

스택 메모리: 함수 호출 시 생성되는 지역 변수와 매개변수가 할당되는 영역이다. -장점: 스택 포인터의 단순 이동만으로 할당/해제가 이루어지기에 빠르며, 함수 종료 시 자동으로 정리되어 메모리 누수 위험이 없다. -단점: 컴파일 시점에 크기가 제한적이어서 (스택 오버플로우 위험) 대용량 데이터를 저장하기 어렵고, 함수의 생명주기를 벗어나 유지될 수 없다.

malloc(힙) 동적 메모리: 런타임에 프로그래머의 요청에 따라 동적으로 할당되는 영역이다. -장점: 실행 중에 필요한 만큼 유연하게 메모리를 할당할 수 있으며, 전역적으로 스코프에 구애받지 않고 생명주기를 수동 제어할 수 있다. -단점: 오버헤드가 크다. 가용 블록 탐색, 메타데이터 관리, 시스템 콜 비용으로 스택보다 속도가 느리다. 내부/외부 단편화가 발생할 수 있고, 메모리 누수나 댕글링 포인터 등의 관리 부담이 생긴다.

3. 스택이 고주소에서 저주소 방향으로 성장하도록 설계된 이유는 무엇인가? 프로세스의 전체 메모리 구조 관점에서 그 이유를 자신의 의견을 중심으로 서술하시오.

프로세스의 데이터 크기가 가변적인 두 영역은 힙과 스택이다. 힙은 저주소에서 고주소 방향으로 성장하고, 스택은 반대로 고주소에서 저주소 방향으로, 서로 마주보며 성장하도록 설계되었다.

두 영역이 양 끝에서 서로를 향해 자라도록 배치하면, 사전에 스택과 힙의 최대 크기를 고정 분할할 필요 없이, 남은 중간 유휴 공간을 동적으로 유연하게 공유할 수 있다. 즉, 한 쪽 영역의 낭비나 충돌(Overflow)을 최소화할 수 있다.

4. 메모리에는 다음과 같은 블록들이 있으며, 각 블록의 크기는 괄호 안에 표시되어 있다.

메모리 블록: A(10), B(50), C(25), D(30), E(40)

다음 순서로 메모리 요청이 들어온다.

요청 순서: 1(30), 2(25), 3(25), 4(10)

First-fit에 대한 예시를 보고, Next-fit과 Best-fit일 때요청에 대한 메모리 할당 순서를 기록하시오.

예) First-fit

1 - B 2 - C 3 - D 4 - A

Next-fit: 1-B, 2-C, 3-D, 4-E

Best-fit: 1-D, 2-C, 3-E, 4-A

5. 동적 메모리 할당 구현 시 경계 태그(boundary tag)를 사용할 때 가장 큰 장점은 무엇인가?

인접 이전 블록의 즉각적인 O(1) 시간 병합(Coalescing):

블록 끝(Footer)에 헤더와 동일한 크기/할당 정보를 복제해 둠으로써, 특정 블록을 해제할 때 물리적으로 바로 앞에 위치한 이전 블록의 가용 여부와 크기를, 리스트 역추적 없이 상수 시간(O(1))에 즉시 확인하고 병합할 수 있다. 그래서 외부 단편화를 빠르고 효율적으로 줄일 수 있다.

다음 블록 병합: 내 헤더의 크기 정보만 더하면 되므로 원래부터 O(1) 가능 이전 블록 병합: 내 앞 블록의 크기를 모르므로 원래는 O(N) -> 경계 태그 덕분에 O(1)로 단축 따라서 경계 태그의 핵심 가치는 "이전 블록까지 포함하여 양방향 모두를 O(1)에 병합할 수 있게 만든 것"

① "0, 음수, NULL" (경계값의 3대장)

• 함수가 인자(Argument)를 받을 때,
  • 입력될 수 있는 가장 극단적인 값을 기계적으로 대입해 보는 훈련
    • 포인터가 들어온다면: "만약 아무 주소도 가리키지 않는 0번지(NULL)가 들어오면?"
      • ptr == NULL일 때 역참조(*ptr)하면 즉시 세그멘테이션 폴트(프로그램 강제 종료)가 나므로 무조건 방어해야 함.
    • 크기/숫자가 들어온다면: "만약 크기가 0이 들어오면?"
    • 음수가 들어오면?
      • 0바이트를 달라고 하거나 0바이트로 줄이라는 엉뚱한 요청을 어떻게 처리할 것인가?

② 함수의 생명주기(Lifecycle) 뒤틀기

• 정상적인 흐름은 malloc $\rightarrow$ realloc $\rightarrow$ free 순서입니다.
• 하지만 사용자는 이 순서를 절대 지켜주지 않는다고 가정합니다:
  • 할당도 안 해놓고(ptr == NULL) 바로 늘려달라고 떼쓰면?
    • "아, 그냥 새로 만들어줘야겠네(malloc)."
  • 늘려달라면서 크기를 0으로 주면?
    • "아, 방을 빼겠다는 소리구나(free)."

③ 리눅스 man page(설명서) 확인하기

• 가장 현실적인 정답은 "머리로 상상하지 않고 스펙 문서를 읽는 것"입니다.
• 새로운 시스템 함수나 라이브러리 함수를 구현할 때, 개발자들은 머리를 쥐어짜지 않고 터미널에 man [함수이름]을 칩니다.
• 매뉴얼의 {RETURN VALUE, ERRORS, DESCRIPTION} 섹션
  • 어떤 비정상적인 입력이 들어올 수 있고 각각 어떻게 처리해야 하는지가 전부 적혀 있습니다.

📑 9.9 동적 메모리 할당

• 9.9.1 malloc과 free 함수
• 9.9.2 왜 동적 메모리 할당인가?
• 9.9.3 할당기 요구사항과 목표
• 9.9.4 단편화
• 9.9.5 구현 이슈
• 9.9.6 묵시적 가용 리스트
• 9.9.7 할당한 블록의 배치
• 9.9.8 가용 블록의 분할
• 9.9.9 추가적인 힙 메모리 획득하기
• 9.9.10 가용 블록 연결하기
• 9.9.11 경계 태그로 연결하기
• 9.9.12 종합 설계: 간단한 할당기의 구현
• 9.9.13 명시적 가용 리스트
• 9.9.14 분리 가용 리스트

한 줄 요약: 이 절이 해결하려는 핵심 문제

메모리 구조/비트: 블록 레이아웃

팀 논의 질문: 이 구현에서 왜 이렇게 처리했을까?

9.9 동적 메모리 할당

• 물리메모리 vs. 가상메모리
• {mmap 함수, munmap 함수} 로도 가상메모리 영역을 생성/삭제 가능

808 각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk(break)를 사용한다 -> 스택에서 push/pop 을 위해서 스택의 꼭대기가 어디인지 추적하는 포인터가 있듯이, 변수 brk 는 힙의 꼭대기가 어디인지 추적하는 포인터인가? 808 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당되었거나 가용한 가상메모리의 연속적인 묶음이다. 808

• 명시적 할당기: ex) malloc 패키지 (할당: malloc 함수, 반환: free 함수)
• 묵시적 할당기: ex) 가비지 컬렉터 (언제 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 특정할 수 있어야 함) 808 메모리 할당은 다양한 문맥에서 일어나는 일반적인 아이디어다. (이번 절에서는 힙 메모리를 관리하는 할당기만을 논한다)

그림9.33 힙heap.

9.9.1 malloc과 free 함수

809 프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받는다.

#include <stdlib.h>
void *malloc(size_t size);
Returns: pointer to allocated block if OK, NULL on error

stdlib.h 를 불러온 뒤 malloc(원하는_바이트수) 를 호출하면, 성공 시 메모리의 시작 주소를 주고, 메모리가 부족해 실패하면 NULL 을 준다. 그래서 malloc() 을 호출한 뒤 if (p == NULL) 로 잘 할당되었는지 확인하는 에러 체크 코드를 항상 작성해야 한다. 809 malloc 함수는 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다** (malloc은 어떤 엄격한 데이터를 집어넣든 CPU가 최고 속도로 에러 없이 읽을 수 있도록, 8이나 16의 배수로 규격화된 주소에 요청한 크기 이상의 넉넉한 공간을 보장해서 넘겨준다)**

• 최소 size 바이트를 갖는

  • 요청한 것보다 절대 작게 주지 않는다. 만약 작게 주면 buffer overflow 가 발생하기 때문이다.
  • 더 크게는 줄 수 있다.
    • 힙 관리용 헤더/푸터 를 붙여야 하기 때문
    • 하드웨어 정렬 단위(8 or 16 바이트)의 배수로 블록 크기를 올림해야 하기 때문.

• 적절히 적렬된

  • CPU 는 메모리를 1바이트씩 찔끔찔끔 읽지 않는다. 데이터 버스 규격에 맞춰 8 or 16 바이트 단위의 경계선에 걸쳐서 한 번에 긁어옴
    • 32비트 모드: 주소가 항상 8의 배수(끝 3비트가 000)인 블록을 리턴
    • 64비트 모드: 주소가 항상 16의 배수(끝 4비트가 0000)인 블록을 리턴
  • CPU 가 메모리에 2번 접근해서 앞뒤를 잘라 합쳐야 한다면, 성능이 반토막난다.
  • 따라서 항상 하드웨어가 가장 빠르게 읽을 수 있도록 주소가 정렬되어 있다.

• 어떤 종류의 데이터 객체에 대해서

  • C언어는 다양한 자료형이 있고, 요구하는 정렬 규격이 다르다.
    • char: 1바이트 정렬 (어디에 있든 상관없음)
    • int: 4바이트 정렬 (주소가 4의 배수여야 함)
    • double, long, 포인터: 8바이트 정렬 (주소가 8의 배수여야 함)
    • long double / SIMD 벡터(__m128): 16바이트 정렬 필요
  • 가장 큰 정렬 기준(16바이트)이 들어오더라도 문제없도록 무조건 최상위 수준으로 정렬된 주소를 내어준다
    • 16 의 최소 공배수는 1, 2, 4, 8, 16이다.
    • 따라서 어떤 주소가 16의 배수라면, 그 주소는 반드시 1, 2, 4, 8의 배수이다.
    • 따라서 16바이트에 맞추면, 그 어떤 데이터 타입이 들어와도 정렬 규격을 반드시 만족한다.

8의 배수
- bin: 맨끝 3비트가 000
- hex: 맨끝은 0 또는 8 (0000 = 0, 1000 = 8)

16의 배수
- bin: 맨끝 4비트가 0000
- hex: 맨끝은 0

메모리 블록 크기를 나타내는 헤더(Header)를 저장할 때 이 규칙을 활용한다. 모든 블록의 크기와 주소가 8 또는 16의 배수로 정렬되면, 블록 크기를 2진수로 나타냈을 때, 하위 3개 비트(끝 3자리)는 항상 000으로 비어 있게 된다.

• 낭비되는 끝 3비트를 그냥 두지 않고
  • 맨 마지막 비트 1개를 할당 플래그(Allocated bit) 로 활용한다
    • 1 (이 블록이 현재 할당되었음)
    • 0 (이 블록이 빈 상태임)

동적 메모리 3형제

• malloc: 크기만 잡아서 주소 넘김 (쓰레기값 남아있음)
• calloc: 메모리 잡고 전부 0으로 덮어씀
  • 내부적으로 malloc 을 먼저 부른 다음, 그 자리에 memset(ptr, 0, size) 으로 0으로 초기화해서 반환함
• realloc: 기존의 데이터는 보존하면서, 메모리 크기를 늘리거나 줄임
  • 만약 바로 뒤에 연속된 빈 공간이 없다면, 데이터를 새 자리로 복사(memcpy)해 옮겨 심은 뒤, 이전 자리는 free 한다

heap 영역은 아래에서 위로 자란다.

• brk (break pointer) 은 맨 꼭대기 경계선(울타리)을 가리키는 포인터다.
  • brk 아래쪽은 이미 OS한테 허락받아 쓸 수 있다.
  • brk 위쪽은 아직 OS 소유다 (접근하면, Segmentation Falut 난다)

sbrk 시스템 콜 함수 (Space Break)

• sbkr(incr): 울타리를 몇 바이트 더 위로 밀어 올릴 것인가?

  • incr 가 양수인 경우: sbrk(4096) 을 호출하면, 커널이 brk(울타리)를 위로 4KB 밀어 올려준다. 그 결과 힙 영역이 4KB 커진다.
  • incr 가 0인 경우: sbrk(0) 을 호출하면, 지금 brk 가 어디인지 조회하는 용도로 쓴다.
  • incr 가 음수인 경우: sbrk(-100) 을 호출하면, brk(울타리)을 아래로 내려서 OS한테 반납한다 (합법)
    • 하지만 규칙대로, 이전의 brk 주소를 return 한다. 그래서 return 값 처리가 복잡해진다.

• sbrk() 는 왜 새로운 brk 주소가 아니라, 이전의 brk 주소를 return 할까?

  • 영역을 확장하기 전의 위치가, 방금 확장한 영역이 시작점 이기 때문.
    • 원래 울타리 위치: 0x1000
    • sbrk(100) 호출 -> 새 울타리 위치: 0x1064
    • 리턴값: 0x1000 (새로 얻은 100바이트 땅의 시작 주소)
  • malloc 입장에서는 sbrk() 가 돌려준 주소를 그대로 새 청크의 시작 주소로 쓰면 되기에 효율적이다.

• 메모리가 꽉차서 실패하면 (ENOMEM = Erro NO Memory) (void *)-1 을 return 한다

void free(void *ptr);
                        Returns: nothing

ptr 인자는 malloc, calloc, realloc 에서 획득한 할당된 블록의 시작을 가리켜야 한다

• free 는 size 를 인자로 받지 않는다. 인자 ptr 바로 앞에 헤더(메타데이터가 담김)를 숨겨두었다
• free 는 아무것도 return 하지 않는다. 그래서 뭔가 잘못되었다는 것을 알릴 수 없고, 런타임 에러 발생 여지가 있다.

free(ptr)의 내부 동작

• 크기를 모르기 때문에, 건네 받은 주소의 바로 앞(헤더)을 까봐야 크기를 알 수 있다.

  // ptr 바로 앞 주소로 4 or 8 바이트 이동해서 숨겨진 헤더를 읽음
  header = ptr - 8;
  size = get_size(header);    // "아, 이 블록이 N 바이트 짜리구나!"
  set_free(header);            // "이제 이 블록은 빈 블록(Free)으로 변경!"

규칙을 어기는 경우

• 블록 중간 주소를 넘기면? free(ptr + 4)
  • free는 무조건 인자 앞으로 8바이트 이동해서 메모리를 읽으려고 한다
  • 근데 이 경우, 진짜 헤더가 아니라, payload 의 한가운데다.
  • 엉뚱한 데이터를 블록 크기로 해석하면서, 힙 관리 구조가 깨지고, free(): invalide pointer 에러와 함께 SIGSEGV 가 터진다.
• 스택 변수나 엉뚱한 주소를 넘기면? int a; free(&a);
  • 힙 영역이 아닌 영역을 건드리면, 프로그램이 즉사한다.
• 이미 해제된 주소를 또 넘기면? Double Free
  • 힙 내부 연결 고리(List) 가 꼬이거나, 순환 참조 루프에 빠져, 보안 취약점의 통로가 된다.

811 그림 9.34 (상태 a~e) 812 더 큰 MAXN 값을 사용해서 다시 컴파일하는 것이다... 고정된 배열 크기아 있다는 것은, 수백만 라인의 코드와 수많은 사용자가 있는 큰 규모의 소프트웨어 제품에서는, 관리가 어렵다. 더 나은 방법은 n값을 알 수 있을 때, 배열을 런타임에 동적으로 할당하는 것이다. 이 방법으로, 배열의 최대 크기는 가용한 가상메모리의 양에 의해서만 제한된다.

int main()
{
    int *array, i, n;

    scanf("%d", &n);
    array = (int *)Malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
        scanf("%d", &array[i]);
    free(array);
    exit(0);
}

1. int *array, i, n; (컴파일 타임의 질서)

• 스택 프레임에 변수 3개가 자리잡는다.
  • n: 정수 4바이트
  • i: 정수 4바이트
  • array: 8바이트 주소표(포인터)
• 컴파일러는 array라는 이름이 스택의 베이스 포인터로부터 몇 바이트 아래에 있는지 미리 알고 있다.
• 하지만 그 주소표가 가리킬 데이터 본체는 아직 세상에 존재하지 않는다.

2. scanf("%d, &n); (카오스의 시작)

• 런타임에 유저가 키보드로 숫자를 입력한다.
• 유저가 5를 넣을지, 100만을 넣을지, 프로그램을 실행하기 전까지는 CPU와 컴파일러는 전혀 알 수 없다.
• 이 순간 정적 배열(int arr[n]) 대신, 동적 메모리 할당이 필요해진다.

3. array = (int *)Malloc(n * sizeof(int)); (주차권 발급) (대문자 Malloc 은 malloc 이 실패해 NULL을 뱉었을 때, 에러를 출력하고 프로그램을 안전하게 종료시키는 얇은 래퍼 함수다.)

• 바이트 계산: sizeof(int) 는 4바이트이므로, 만약 n = 10 이라면 총 40바이트의 연속된 공간이 필요하다.
• 할당자 내부 동작
  • 힙 영역의 빈 청크들을 뒤져서 40바이트를 담을 수 있는 자리를 찾는다.
  • 이때 40바이트 딱 맞게 주는 게 아니다. 앞쪽에 메타데이터(헤더 4 or 8바이트)를 붙이고, 하드웨어 4 or 16바이트 정렬 규칙에 맞춘 블록을 마련한다.
  • 주소표 반환: 할당자는 헤더를 건너뛴, 실제 데이터가 들어갈 페이로드의 첫번째 바이트 주소(0x5555...)를 &rax(8바이트 레지스터)에 담아 돌려준다.
  • 대입: 스택에 있던 8바이트 변수 array에 그 주소값이 복사된다. 이제 array는 힙의 그 거대한 공간을 통제하는 유일한 핸들이 된다.

4. for (i = 0; i < n; i++) scanf("%d", &array[i]); (포인터 연산)

• array[i] 는 C문법 설탕이고, 본질은 *(array + i) 이다.
• array 의 타입이 int * (4바이트 단위)이므로, CPU는 주소 연산을 다음과 같이 한다:
  • 실제 주소 = array + (4 X i)
• 힙의 베이스 주소에서 4바이트씩 전진하며 유저가 입력한 정수를 차곡차곡 채워 넣는다.

5. free(array); (주차권 반납과 헤더)

• free 함수에는 오직 array 주소만 던진다. 배열 크기 n 이나 40바이트 라는 정보를 전혀 전달하지 않는다.
• free는 전달받은 array - 8 (array 주소에서 앞으로 8바이트 이동) 해서 숨겨진 헤더를 까본다.
• 헤더에서 "아, 이 블록은 x바이트 크기구나!" 라는 사실을 알아내고, 해당 블록의 할당 비트를 0으로 바꿔 Free List 에 편입시킨다.
• 만약 앞뒤에 다른 빈 블록이 있다면 병합(Coalescing) 작업까지 수행한다.
• 스택의 변수 array는 여전히 그 힙 주소값이 그대로 남아 있다 (Dangling Pointer)

6. exit(0); (자원 정리)

• 운영체제에게 정상 종료(0) 신호를 보내며 프로세스의 모든 가상 주소 공간(스택, 힙, 코드)이 일괄 해제된다.

RAM 메모리는 1차원 배열이다. 스택과 힙도 1차원이다.

• (논리적으로) 가상 메모리 공간은 0x0000000000000000 번지부터 바이트 단위로 인덱스가 매겨진 거대한 1차원 char memory[] 배열과 같다.
• Stack, Heap, BSS, Data, Code(Text) 영역은 그저 하나의 1차원 주소선 위에 구역(Segment)만 나눠둔 것이다.
  • Heap 은 낮은 주소에서 높은 주소 방향으로 자라고,
  • Stack 은 높은 주소에서 낮은 주소 방향으로 자라고,
  • 둘다 동인한 1차원 수직선 위를 오르내릴 뿐이다.

malloc() 은 항상 "연속된" 공간을 할당하는가?

• 소프트웨어 (가상 메모리) 관점
  • malloc(4) 을 호출했을 때, 20바이트는 0x1000 에 주고 나머지 20바이트는 0x5000 에 떨어뜨려서 주는 일은 절대 없다.
  • 이유: C언어의 핵심인 포인터 연산(*(ptr + i)) 때문이다.
    • array[3] 을 읽으려면 CPU는 단순히 시작 주소에 오프셋을 더하는 단일 덧셈 연산(array + 3 * 4)을 수행한다.
    • 공간의 중간이 끊겨 있다면, 덧셈 한 번으로 다음 원소를 찾아갈 수 없으므로, C언어의 배열 문법과 포인터 연산 전체가 성립하지 않는다.
• 하드웨어 (물리 메모리) 관점
  • 실제 물리 RAM: 페이지 테이블(MMU)이 중간에서 매핑해주기 때문에, 물리적으로 4KB 단위 페이지들이 흩어져 있어도 상관없다. 하지만 CPU 와 프로그램은 이를 인지하지 못하며, 연속된 주소 공간으로만 인식하고 사용한다.

813 프로그래머들은 할당기를 정확하고 효율적으로 사용하기 위해서 어떻게 이들이 동작하는지 이해할 필요가 있다. 9.11절에서 할당기의 잘못된 사용으로 발생할 수 있는 위험한 에러들에 대해 설명할 것이다.

9.9.3 할당기 요구사항과 목표

요구사항

• 임의의 요청 순서 처리하기
• 요청 즉시 응답하기
• 힙만 사용하기
• 블록 정렬하기 (정렬 요건)
• 할당된 블록을 수정하지 않기

813 일반적으로, 할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화한다. 813 한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한된다. 814 $U_k = \frac{\max_{i \le k} P_i}{H_k}$

• 비율 0~1
  • 분모: OS 한테 뜯어낸 전체 땅
  • 분자: 진짜로 쓴 알맹이 데이터
• 비율 1 (100%) 로 꽉 채우는 것은 불가능하다.
  • 헤더도 붙여아하고, 8 or 16 바이트 정렬도 맞춰야 하고, 단편화(중간에 쪼개진 빈 공간)도 생기기 때문에, 분모는 분자보다 항상 크다.
• Malloc Lab 점수 산출 기준:
  • 과제 채점기(mdriver)를 돌리면 두 가지 점수가 나옵니다:
    • Throughput (처리량): 초당 malloc/free를 얼마나 빠르게 처리하는가?
    • Memory Utilization (메모리 이용도): 바로 $U_{n-1}$ 값. 땅을 낭비하지 않고 얼마나 알뜰하게 썼는가?
• 트레이드오프(긴장 관계):
  • 처리량을 늘리려고 대충 빈곳에 던져주면 이용도가 개판이 되고,
  • 이용도를 극대화하려고 빈틈없이 맞추려다 보면 탐색 속도가 느려진다.

9.9.4 단편화

2종류의 단편화가 있다. 외부 단편화는 측정하기 어렵고 예측 불가능하기 때문에 할당기들은 대개 많은 수의 더 작은 가용 블록들보다는, 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법들을 채택하고 있다.

내부 단편화는 현재의 힙 공간으로 감당 가능하지만, 외부 단편화는 현재의 힙 공간으로 감당 불가능하다. 그래서 OS 에게 추가 힙 공간을 요청(sbrk)해야 한다.

• 내부 단편화
  • 정량화가 단순하다. 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이다.
    • 시간상 어디서든 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존한다.
• 외부 단편화
  • 할당된 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
    • 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라, 미래의 요청 패턴에도 의존한다.

9.9.5 구현 이슈

815 이 초보적인 할당기는 디자인 공간에서 극단점에 해당한다. 815 처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다:

• 가용 블록 구성: 어떻게 가용 블록을 지속적으로 추적하는가?
• 배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
• 분할: 새롭게 할당된 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?
• 연결: 방금 반환된 블록으로 무엇을 할 것인가?

배치, 분할, 연결은 서로 다른 가용 블록 구조와 관련된다. 묵시적 가용 리스트로 알려진, 간단한 가용 블록 구조의 맥락에서 소개할 것이다.

반납된 빈 땅을 재활용 하면서도, 속도 저하를 최소화하기 위해 4가지 설계 변수를 결정해야 한다. 4가지 각각을 어떻게 조합하느냐에 따라 과제의 Throughput(처리 속도)과 Utilization(메모리 이용도) 점수 판도가 완전히 갈리게 된다.

4가지 핵심 설계

• 1) 가용 블록 구성 (Free Block Organization): 힙 안에 블록들(할당/가용)이 마구 섞여 있을 때, 가용 블록을 어떻게 지속적으로 추적하는가?
  • 암묵적 가용 리스트 (Implicit List)
    • 빈 블록만을 위한 별도의 장부 없이, 헤더의 크기 정보를 이용해서, 힙의 모든 블록(할당/가용)을 차례대로 탐색
  • 명시적 가용 리스트 (Explicit List)
    • 빈 블록 내부의 페이로드 공간 (어차피 비어있으므로 유저 데이터가 없음)에 next, prev 포인터를 심어서, 빈 블록들끼리만 이중 연결 리스트(Doubly Linked List)로 엮어둔다.
    • 할당된 블록은 건너뛰고, 빈 블록들만 순회하므로, 탐색 속도가 크게 오른다.
  • 분리 가용 리스트 (Segregated Free List)
    • 크기별로 리스트를 여러 개 만든다 (ex. 1632바이트 용, 3364바이트 용, 65~128바이트 용)
    • 현대 상용 할당기(ptmalloc, jemalloc)가 채택하는 방식으로, 탐색 시간이 거의 $O(1)$ 에 가까워진다.
• 2) 배치 (Placement): 가용 블록이 여러 개 있을 때, 어떻게 선택하는가?
  • First-Fit
    • 리스트의 처음부터 탐색하다가, 요청 크기를 수용할 수 있는 가장 첫 번째 빈 블록을 바로 선택
    • 탐색 속도가 비교적 빠르지만, 리스트 앞쪽에 자투리 조각들이 쌓이는 경향이 있다.
  • Next-Fit
    • 직전 탐색이 끝난 위치부터 다음 탐색을 시작
    • First-Fit 보다 속도가 빠를 수 있으나, 메모리 이용도가 떨어지는 경우가 많을 수 있다.
  • Best-Fit
    • 들어갈 수 있는 모든 빈 블록을 검사한 뒤, 최적의 (크기 차이가 가장 작은) 블록을 고름
    • 단편화를 줄여 메모리 이용도는 최고 수준이지만, 매번 리스트 전체를 뒤져야 하므로 처리량이 급감한다.
• 3) 분할 (Splitting): 가용 블록의 나머지 부분들로 무엇을 할 것인가?
  • 분할 하지 않음
    • 100바이트를 통째로 할당 및 사용
    • 구현은 편하지만, 무려 80바이트의 심각한 내부 단편화
  • 분할 (내부 단편화를 획기적으로 줄이는 필수(?) 테크닉)
    • 예를 들어, 20바이트가 필요한데, 찾아낸 빈 블록이 100바이트 크기라면, 어떻게 처리할 것인가?
    • 100바이트를 쪼개서 앞쪽 24바이트 (헤더 포함)는 할당 블록으로 만들고,
    • 남은 76바이트는 새로운 작은 가용 블록으로 헤더/푸터 를 다시 세팅해서 가용 리스트에 남겨둔다.
• 4) 연결 (Coalescing): 방금 반환된 블록으로 무엇을 할 것인가?
  • 연결하지 않음
    • 작은 빈 조각들을 방치: 외부 단편화가 폭발, 전체 빈 공간은 넉넉하지만, 시스템 호출 sbrk() 을 할 경우가 아주 많아질 수 있음
  • 즉시 연결 (Immediate Coalescing)
    • free 가 불리자마자 앞 블록의 푸터 와 뒤 블록의 헤더 를 확인하여, 비어있는 이웃이 있다면, 즉시 하나의 거대한 빈 블록으로 병합
  • 지연 연결 (Deferred Coalescing)
    • free 때는 그냥 두고, 나중에 malloc 이 빈 공간을 찾다가 실패했을 때, 힙 전체를 한 번에 싹 훑으며 병합

*빈 조각들을 최적으로 채워 넣는 빈 패킹(Bin Packing) 문제는 유한한 경우의 수를 다룸에도 불구하고 다항 시간 안에 완벽한 답을 낼 수 없는 대표적인 난제다. 할당기를 설계한다는 것은 거대한 조합 속에서 '수학적 완벽성'을 찾는 것이 아니라, 경험적 휴리스틱 (First-fit, Segregated list 등) 을 통해 유한한 자원 내에서 실패 확률 (외부 단편화, 지연 시간) 을 실용적인 수준으로 억제하는 작업이다. *

9.9.6 묵시적 가용 리스트 (헤더 내 필드에 의해 묵시적으로 연결됌)

모든 실용적인 할당기는 블록 경계를 구분하고, 할당/가용 블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당기는 이 정보를 블록 내에 저장한다.

1워드 헤더, 데이터, 추가적인 패딩

• 헤더가 인코딩하는 정보
  • 블록 크기 (헤더, 패딩 포함)
  • 블록 할당 여부

패딩을 하는 이유는 여러 가지다.

• Minimum Block Size 충족: 해제 시 next / prev 포인터를 담을 수 있는 최저 바이트(16 or 24) 확보

• 외부 단편화 극복 전략: 할당기 정책상, 블록 분할 후 남는 자투리가 너무 작아 못 쓰게 될 바엔, 기존 블록 패딩으로 흡수

• 정렬 요구사항 충족: CPU의 4/8/16 바이트 단위 메모리 버스 정렬 규칙 만족

• 캐시 라인(64바이트) 정렬: 캐시 라인 분할 접근 방지 -> CPU 메모리 읽기 사이클 최소화

• 멀티스레드 환경의 False Sharing 방지: 코어 간 불필요한 캐시 무효화 핑퐁 방지

할당기는 간접적으로 가용 블록 전체 집합을, 힙 내의 전체 블록을 다니면서 방문할 수 있다. (가용 블록들끼리 직접 이어주는 연결 고리(포인터)가 없다.

• 블록 A의 헤더를 읽어서, 크기가 S 바이트임을 확인한다.
• 주소에 S 를 더해서(ptr + S ) 다음 블록 B의 헤더로 이동한다.
• 빈 공간을 찾을 때까지, 이 작업을 힙의 끝(에플로그 블록)까지 징검다리 건너듯 반복한다. 가용 블록으로 곧장 점프할 수 없고, 중간에 놓인 할당 블록들을 전부 밟고 지나가야 하므로, "간접적"이라고 표현했다.

장점: 단순성 단점: 연산(할당된 블록 배치, 가용 리스트 탐색) 비용은 힙에 있는 전체 할당/가용 블록의 수에 비례한다.

9.9.7 할당된 블록의 배치

• First fit
  • 장점: 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다.
  • 단점: 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있다.
    • 큰 블록을 찾는 경우, 검색 시간이 늘어난다.
• Next fit
  • 이전 검색에서 가용 블록을 발견했다면, 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 희망
  • 장점: 리스트의 앞부분에 많은 작은 크기의 조각들로 구성되는 경우, First fit 에 비해서 아주 빠른 속도
  • 단점: First fit 에 비해서 나쁜 메모리 이용도를 가지는 경향
• Best fit
  • 장점: 대체로 더 좋은 메모리 이용도
  • 단점: 묵시적 가용 리스트에서는, 힙을 싹다 검색해야 한다.
    • 대안: 정책을 단순화해서, 힙을 모두 검색하지 않는, segregated free list

9.9.8 가용 블록의 분할

9.9.9 추가적인 힙 메모리 획득하기

9.9.10 가용 블록 연결하기

빠른 할당기들은 종종 지연 연결의 형태를 선택한다는 것을 알아야 한다.

9.9.11 경계 태그로 연결하기

9.9.12 종합 설계: 간단한 할당기의 구현

필요해보이는 개념: 청크, 페이지, OS 간에 상호작용

malloc 에 대한 현재 내 생각

• 문제의식:
  • 컴파일 타임에 증명할 수 없는 데이터를 담기 위한 그릇이 필요하다. 현실은 아마도 카오스 세계일 것이기에 런타임의 데이터를 100% 예측할 수 없을 것이고, 단 하나의 완벽한 malloc 함수는 없을 것이다. 그래서 수십 년동안 IT 에서 이 난제를 풀기 위해 고민해왔다.
    • 불확실한 상황에서 하드웨어 리소스를 어떻게 사용할 것인가?
      • 메모리 활용도 높이기 (트레이드오프: Latency)
      • 처리 속도 높이기 (트레이드오프: Fragmentation)
  • 당연히 다양한 맥락이 있을 것이고, 특정한 맥락이 조금씩 바뀔지라도, 경향성이 패턴으로 포착되는 한, 나름의 적당한 해법(특정한 malloc 알고리즘)이 있을 것이다.

의문: malloc() 은 왜 void* 를 return 하는가?

• 할당해준 메모리에 호출자가 어떤 타입의 데이터를 담을지 미리 알 수 없기 때문
  • malloc() 입장에서 타입을 몰라도 모든 타입에 대해 범용적으로 메모리를 할당
    • 만약 C언어에서 void*가 없었다면, 타입마다 함수를 따로 만들어야 했을 것임
      • malloc_int()
      • malloc_char()
      • malloc_struct_node()
      • 등등...
  • C언어 규칙상 void* 는 어떤 포인터 타입으로든 명시적인 캐스팅 없이 암묵적으로 형변환된다 (Implicit Conversion). 반환값을 임의의 특정 포인터 변수에 그대로 대입할 수 있다.
    • int *arr = malloc(sizeof(int) * 10);
    • char *str = malloc(sizeof(char) * 32);
    • struct Node *node = malloc(sizeof(struct Node));
  • malloc() 은 타입 정보가 없기에 데이터 해석 규칙이나 크기 정보를 모른다. 순수하게 물리적 메모리 시작 위치만 건네준다.
    • 특정 포인터의 타입은 컴파일러에게 "이 주소에서 몇 바이트를 읽어야 하는가", "포인터 연산(p + 1) 시 몇 바이트를 건너뛰어야 하는가" 를 알려준다.
      • int *p; -> p + 1 은 4바이트 이동
      • double *p; -> p + 1 은 8바이트 이동
      • void *p; -> 가리키는 대상의 크기 정보가 없음

결론: 성공해서 정상적인 주소를 주든, 실패해서 NULL을 주든, 기계어 관점에서는 8바이트 주소 레지스터(%rax)를 쓰는 void * 타입 포인터를 반환하는 것은 고정이다.

진리표(Truth table)는 공리다: 인간이 합리적으로 생각하는 기준으로 정했다

P -> Q : 결과

T -> T : T [증명 패턴] ··· (1) T -> F : F [반례 패턴] ··· (2) F -> T : T [공허참 패턴] ··· (3) F -> F : T [공허참 패턴] ··· (4)

수학에서는 오직 (1) 만 내용적 정보를 준다. (3)과 (4)는 내용적 정보를 주지 않는다.

반증 불가능하면 과학이 아니다. (3)과 (4)는 과학이 아니다.

공허참 패턴 예시

• ex1: SF소설을 쓸 수 있다. 애시당초 뻥이기 때문.
• ex2: 어떤 집합에 조건적으로 이름 지을 때, 공집합은 어떤 조건도 만족하지 않기에, 어떤 이름을 붙여도 항상 참이다.

C언어에서 UB 는 공허하게 참이다. 항상 참이다. 애시당초 뻥이기 때문.

C 언어 표준은 프로그래머와 컴파일러 사이의 거대한 조건 명제(P -> Q)로 이루어져 있다.

전제 P: ** **프로그래머는 유효하지 않은 메모리를 참조하지 않고, 오버플로우를 내지 않으며, 언어 규격을 엄격히 준수한다. (대담한 선언이다. 왜냐면 꼼꼼한 수학자조차 실수를 하기 때문이다.)

결론 Q: 컴파일러는 프로그래머의 의도대로 정확히 동작하는 기계어 코드를 생성한다.

우리가 기대하는 정상적인 프로그래밍 세계는 P가 참(T)인 세계다. 프로그래머가 규칙을 지켰으니(P = T), 컴파일러도 약속된 기계어를 안전하게 번역해낸다(Q = T).

프로그래머가 이미 해제된 스택 주소를 역참조하거나(Dangling Pointer), 유효하지 않은 메모리를 건드리는 순간, 전제 조건 P는 거짓(F)이 된다.

• ** F -> T** (컴파일러가 코드를 우연히 정상 작동시킴): 논리적으로 문제없음 (참).
• ** F -> F** (컴파일러가 프로그램을 강제 종료시키거나 하드디스크를 포맷함): 논리적으로 문제없음 (참).

C 언어에서 Undefined Behavior(UB)를 발생시키는 것은, *시스템의 전제가 깨져 *어떤 헛소리를 해도 논리적으로 '참'이 되어버리는 공허참의 늪에 빠지는 것이다.

하드웨어는 항상 물리 법칙에 따라 특정 전압을 읽지만, 언어의 논리 체계 안에서는 이미 공리계가 붕괴되어 어떤 결과도 보장할 수 없게 된다.

실행 전: a = 10, b = 999 실행 후: a = 10, b = 10

원본(a) 은 원래 값을 유지한다.

move 라는 단어는 Ctrl+X, Ctrl+V 라는 뉘앙스인데, 실제로는 Ctrl+C, Ctrl+V 이다.

#include <stdio.h>

int main(void) {
    int a = 10;
    int b = 999;

    printf("=== movl 실행 전 ===\n");
    printf("a = %d (주소: %p)\n", a, (void*)&a);
    printf("b = %d (주소: %p)\n\n", b, (void*)&b);

    // 인라인 어셈블리로 movl 직접 실행
    // GCC / Clang 기본 AT&T문법: movl [출발지], [목적지]
    __asm__ (
        "movl %1, %0\n\t"  // %1(출발지 a)의 값을 %0(목적지 b)로 복사
        : "=r" (b)         // 출력(Output): 수정되는 목적이 변수 b (%0)
        : "r" (a)          // 입력(Input): 읽기만 하는 출발지 변수 a (%1)
    );

    printf("=== movl 실행 후 ===\n");
    printf("a = %d (여전히 10으로 온전히 유지됌)\n", a);
    printf("b = %d (999에서 10으로 덮어씌워짐)\n\n", b);

    // 원본 a를 이후에도 정상적으로 재사용할 수 있는지 확인
    int c = a + 5;
    printf("a를 재사용한 계산 (a + 5) = %d\n", c);

    return 0;
}

./test_mov
=== movl 실행 전 ===
a = 10 (주소: 0x7fffff6bf00c)
b = 999 (주소: 0x7fffff6bf010)

=== movl 실행 후 ===
a = 10 (여전히 10으로 온전히 유지됌)
b = 10 (999에서 10으로 덮어씌워짐)

a를 재사용한 계산 (a + 5) = 15

movl을 수행하더라도 원본 레지스터/변수 a에는 아무런 부작용(쓰레기 값 발생, 비워짐 등)이 없으며, 단순 Read & Copy 동작임을 직접 확인했다.

Axiom 1: The Machine State as a Tuple

A 64-bit x86-64 CPU is a discrete deterministic state machine. Its core state at any discrete clock step $t$ is a mathematical tuple:

$$\mathcal{S}_t = \langle \mathcal{R}, \mathcal{M}, \text{rip} \rangle$$

1. Registers ($\mathcal{R}$): A finite set of sixteen named 64-bit words:

$$\mathcal{R} = { \text{rax}, \text{rbx}, \text{rcx}, \text{rdx}, \text{rsi}, \text{rdi}, \text{rbp}, \text{rsp}, \text{r8} \dots \text{r15} }$$

Each register is a function mapping a register name to an integer in ${0, \dots, 2^{64}-1}$:

$$\mathcal{R}: \text{Name} \to \mathbb{W}_{64}$$

2. Memory ($\mathcal{M}$): A contiguous byte-addressable array:

$$\mathcal{M}: \mathbb{W}{64} \to \mathbb{W}{8}$$

Reading an 8-byte word (64 bits) from address $a$ means fetching the 8 consecutive bytes starting at address $a$:

$$\mathcal{M}{64}[a] = \sum{k=0}^{7} \mathcal{M}[a+k] \cdot 2^{8k} \quad (\text{Little-Endian representation})$$

3. Instruction Pointer ($\text{rip}$): A single 64-bit scalar holding the memory address of the next instruction to execute:

$$\text{rip} \in \mathbb{W}_{64}$$

Axiom 2: Operand Syntax (Source $\to$ Destination)

In x86-64 AT&T syntax, an instruction is a transition function $\mathcal{T}: \mathcal{S}t \to \mathcal{S}{t+1}$.The general syntax is strictly:

$$\text{OPCODE} \quad \text{Source}, \quad \text{Destination}$$

• Rule of Data Flow:

The value is read from $\text{Source}$, modified by $\text{OPCODE}$, and written to $\text{Destination}$.

• The Dollar Sign Prefix ($):

Denotes an immediate constant (a pure mathematical scalar $c \in \mathbb{Z}$).

$$0 \implies \text{Value } 0$ $$4 \implies \text{Value } 4$

• The Percent Sign Prefix (%):

Denotes a register name in $\mathcal{R}$.

%rax

Concrete Evidence:

$$\text{Instruction: } \texttt{movq $0, %rax}$$

• Mathematical Definition: $$\mathcal{R}_{t+1}[\text{rax}] \leftarrow 0$$
• Proof of Direction: The source is $0 (left). The destination is %rax (right). The scalar 0 is placed into register rax.

Axiom 3: Address Calculation via Parentheses

Parentheses denote Memory Dereferencing (pointer arithmetic). If $k \in \mathbb{Z}$ is an integer literal and $\text{reg} \in \mathcal{R}$, the notation:

$$k(\text{%reg})$$

evaluates to the physical memory location at the address:

$$\text{Effective Address} = \mathcal{R}[\text{reg}] + k$$

Therefore:

$$\texttt{movq } \text{Source}, \quad k(\text{%reg}) \implies \mathcal{M}_{64}[\mathcal{R}[\text{reg}] + k] \leftarrow \text{Value}(\text{Source})$$

Concrete Evidence for -8(%rbp) and -24(%rbp):

Suppose %rbp currently holds the address $1000$ (i.e., $\mathcal{R}[\text{rbp}] = 1000$).

• Case 1: -8(%rbp)

$$\text{Effective Address} = 1000 + (-8) = 992$$

The instruction movq $0, -8(%rbp) does:

$$\mathcal{M}_{64}[992] \leftarrow 0$$

• Case 2: -24(%rbp)

$$\text{Effective Address} = 1000 + (-24) = 976$$

The instruction subq $1, -24(%rbp) does:

$$\mathcal{M}{64}[976] \leftarrow \mathcal{M}{64}[976] - 1$$

Why did the compiler pick $992$ and $976$?

Because each 64-bit integer takes 8 bytes.

• Byte interval for slot 1: $[992, 999]$ (8 bytes wide $\implies$ called sum in C).
• Byte interval for slot 2: $[976, 983]$ (8 bytes wide $\implies$ called n in C).

Axiom 4: Arithmetic Transformation Rules

Let us formalize the four basic arithmetic instructions:

*Crucial Detail on cmpq S2, S1: *

The comparison computes Destination minus Source ($\text{Second} - \text{First}$). Therefore, cmpq $0, %rax computes:

If $\mathcal{R}[\text{rax}] > 0$, the result is positive, and the machine records "Greater Than".

Step-by-Step Mathematical Trace of 3 Instructions Let the initial state at step $t=0$ be:

• $\mathcal{R}[\text{rbp}] = 1000$
• $\mathcal{M}_{64}[992] = 5$ (the value at -8(%rbp))
• $\mathcal{R}[\text{rax}] = 10$

Step 1: movq $0, -8(%rbp)

• Input State: $\mathcal{M}_{64}[992] = 5$
• Transformation: Write immediate constant $0$ to address $1000 - 8 = 992$.
• Output State: $\mathcal{M}_{64}[992] = 0$.

Step 2: addq $7, %rax

• Input State: $\mathcal{R}[\text{rax}] = 10$
• Transformation: $\mathcal{R}[\text{rax}] \leftarrow \mathcal{R}[\text{rax}] + 7 = 10 + 7 = 17$.
• Output State: $\mathcal{R}[\text{rax}] = 17$.

Step 3: subq $1, -8(%rbp)

• Input State: $\mathcal{M}_{64}[992] = 0$
• Transformation: $\mathcal{M}{64}[992] \leftarrow \mathcal{M}{64}[992] - 1 = 0 - 1 = -1$.
• Output State: $\mathcal{M}_{64}[992] = -1$ (stored as two's complement 0xFFFFFFFFFFFFFFFF).

How control flow is mathematically mapped to hardware?

1. The Human Desire vs. The Physical Axiom

• The Desire: Conditional branching.

  • $$\text{If condition } P \text{ is true, execute block } A\text{; otherwise, execute block } B.$$

• The Physical Axiom (Axiom 4 — Monotonic Execution):

  • The Program Counter (%rip) naturally increments monotonically from one instruction to the next:

  $$%rip \leftarrow %rip + \text{sizeof}(\text{current_instruction})$$

The CPU cannot "choose" a block of code directly. It can only do one of two things:

1) Continue to the next sequential address. 2) Overwrite %rip with a target address (a Jump).

2. The Bridge: Condition Codes ($\mathcal{C}$)

To decide whether to jump, the CPU maintains a special 1-bit register collection called Condition Codes (or the EFLAGS register):

$$\mathcal{C} = \langle \text{CF}, \text{ZF}, \text{SF}, \text{OF} \rangle$$

Whenever the ALU executes an operation (like sub, add, cmp), these 1-bit flags are updated automatically as side effects:

Crucial Rule: leaq does not alter condition codes. Pure arithmetic (addq, subq, cmpq, testq) does.

3. The 3-Step Machine Recipe for Any if or Loop

Every conditional construct in C is compiled into this exact 3-step sequence:

[Step 1: Set Flags]   ───>   cmpq %rsi, %rdi      (Compute %rdi - %rsi, discard result, set flags)
[Step 2: Read Flags]  ───>   jg   .L_greater      (Jump if ZF=0 and SF=OF)
[Step 3: Fallthrough] ───>   ...                  (Code executed if false)

test3_6.c

long max(long a, long b) {
    if (a > b) return a;
    else return b;
}

compiled -O0

cat test3_6.s

        .file   "test3_6.c"
        .text
        .globl  max
        .type   max, @function
max:
.LFB0:
        .cfi_startproc
        endbr64
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movq    %rdi, -8(%rbp)
        movq    %rsi, -16(%rbp)
        movq    -8(%rbp), %rax
        cmpq    -16(%rbp), %rax
        jle     .L2
        movq    -8(%rbp), %rax
        jmp     .L3
.L2:
        movq    -16(%rbp), %rax
.L3:
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   max, .-max
        .ident  "GCC: (Ubuntu 13.3.0-ubuntu2~24.04.1) 13.3.0"
        .section        .note.GNU-tack,"",@progbits
        .section        .note.gnu.property,"a"
        .align 8
        .long   1f - 0f
        .long   4f - 1f
        .long   5
0:
        .string "GNU"
1:
        .align 8
        .long   0xc0000002
        .long   3f - 2f
2:
        .long   0x3
3:
        .align 8
4: 

                  +-----------------------------------+
                  |           Function Entry          |
                  |  pushq   %rbp                     |
                  |  movq    %rsp, %rbp               |
                  |  movq    %rdi, -8(%rbp)   (save a)|
                  |  movq    %rsi, -16(%rbp)  (save b)|
                  +-----------------------------------+
                                    |
                                    v
                  +-----------------------------------+
                  |             Condition             |
                  |  movq    -8(%rbp), %rax   (%rax=a)|
                  |  cmpq    -16(%rbp), %rax  (a - b) |
                  +-----------------------------------+
                                    |
                            jle .L2 (a <= b)
                           /                 \
                 [ True ] /                   \ [ False ]
                         /                     \
                        v                       v
      +----------------------------+  +----------------------------+
      |      .L2 (Else Block)      |  |      Then-Fallthrough      |
      |  movq  -16(%rbp), %rax     |  |  movq  -8(%rbp), %rax      |
      |        (%rax = b)          |  |        (%rax = a)          |
      +----------------------------+  |  jmp   .L3                 |
                    |                 +----------------------------+
                    \                               /
                     \                             /
                      ----->        .L3       <----
                                     |
                                     v
                  +-----------------------------------+
                  |             Function Exit         |
                  |  popq    %rbp                     |
                  |  ret                              |
                  +-----------------------------------+

Step-by-Step Flow

                  [Input Registers] ──────────> [%rdi = a]   [%rsi = b]
                                   │            │
                                   ▼            ▼
[Stack Memory Frame] ───────> [-8(%rbp)]   [-16(%rbp)]
                                   │            │
                                   ▼            ▼
[ALU Operation] ────────────> cmpq calculates: (%rax - %rsi) = (a - b)
                                   │
                                   ▼
[Flags Register EFLAGS] ────> Updates ZF, SF, OF, CF
                                   │
                                   ▼
[Decision Point] ───────────> Does a <= b hold? ((SF ^ OF) | ZF == 1)
                              ├── YES ──> Jump to .L2 ──> Load b into %rax
                              └── NO  ──> Fallthrough ──> Load a into %rax ──> Jump to .L3

compiled -O2

cat test3_6_opt.s 
        .file   "test3_6.c"
        .text
        .p2align 4
        .globl  max
        .type   max, @function
max:
.LFB0:
        .cfi_startproc
        endbr64
        cmpq    %rsi, %rdi
        movq    %rsi, %rax
        cmovge  %rdi, %rax
        ret
        .cfi_endproc
.LFE0:
        .size   max, .-max
        .ident  "GCC: (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0"
        .section        .note.GNU-stack,"",@progbits
        .section        .note.gnu.property,"a"
        .align 8
        .long   1f - 0f
        .long   4f - 1f
        .long   5
0:
        .string "GNU"
1:
        .align 8
        .long   0xc0000002
        .long   3f - 2f
2:
        .long   0x3
3:
        .align 8
4:

               +----------------------------------------+
               |              Function Entry            |
               |  (No stack setup, no memory writes)    |
               |  Arguments already in registers:       |
               |      %rdi = a,  %rsi = b               |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |             1. Comparison              |
               |  cmpq   %rsi, %rdi                     |
               |  Computes: (%rdi - %rsi) = (a - b)     |
               |  Sets flags: SF, OF, ZF in %rflags     |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |        2. Default Assignment           |
               |  movq   %rsi, %rax                     |
               |  State: %rax = b                       |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |         3. Conditional Move            |
               |  cmovge %rdi, %rax                     |
               |  Condition: (SF ^ OF) == 0 (i.e. a>=b) |
               |                                        |
               |  [ a >= b ]: %rax <-- %rdi (value a)   |
               |  [ a <  b ]: %rax unchanged (value b)  |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |             Function Exit              |
               |  ret (Returns value in %rax)           |
               +----------------------------------------+

-O2 Shape (Strictly Linear / Monotonic Pipeline):

[Compare] ──> [Speculative Load] ──> [Conditional Select] ──> [Return]

The instruction stream never branches. The CPU pipeline executes in a straight line without stalling.

A1. Yes—in fact, every founding figure of computer science studied this way because they had no choice.

When Alan Turing, John von Neumann, Edsger Dijkstra, and Donald Knuth built the foundations of modern computing, high-level languages like Python, Java, or even early C did not exist. To them, programming was never "memorizing coding syntax." It was the physical implementation of mathematical logic.

Q2. Should We Review All Physical Axioms Beforehand?

A2. Review a minimal core set of axioms first, but do not try to catalog every obscure edge case upfront.

If you attempt to memorize all x86_64 architecture rules, micro-architectural quirks, and IEEE-754 floating-point edge cases before touching code, you will hit the same abstract *cognitive overload *you felt earlier.

The most effective strategy is:

Establish the 5 Fundamental Axioms that govern 95% of machine execution (Registers, Memory Mapping, Condition Flags, the Call Stack, and Alignment).

Step sequentially through Chapter 3, pulling in any specialized lemma only when that specific chapter section demands it.

[The 5 Physical Axioms of x86_64 Hardware]

Axiom 1: The Principle of Flat, Byte-Addressable Memory

The Rule: The system memory is modeled as an array of 8-bit bytes: $$\mathcal{M}: [0, 2^{64}-1] \to {0, 1}^8$$

The Hardware Constraint: Memory itself has no types, no variable names, and no boundaries. It only knows numerical addresses and raw bit patterns. A pointer is simply an integer in $\mathbb{Z}_{2^{64}}$ used as an index into this massive array.

Axiom 2: The Virtual Memory Page Boundary

The Rule: The hardware Memory Management Unit (MMU) does not manage individual bytes; it manages chunks called pages (standard size: $4096 \text{ bytes} = 4 \text{ KB}$).

The Hardware Constraint: Every page has a permission bitmask: $$\text{Permissions} \in \mathcal{P}({ \text{Read}, \text{Write}, \text{Execute} })$$

The Zero Page Invariant: The page spanning addresses $[0, 4095]$ is explicitly unmapped ($\text{Permissions} = \emptyset$). Any instruction attempting to read, write, or execute within this set triggers an immediate CPU hardware interrupt ($\text{Page Fault} \implies \text{SIGSEGV}$).

Axiom 3: The Register Set as Discrete State Storage

The Rule: Registers are tiny, ultra-fast storage cells located directly inside the CPU core. In x86_64, there are 16 general-purpose 64-bit integer registers:

$$\mathcal{R} = { \text{RAX}, \text{RBX}, \text{RCX}, \text{RDX}, \text{RSI}, \text{RDI}, \text{RBP}, \text{RSP}, \text{R8} \dots \text{R15} }$$

The Hardware Constraint: Arithmetic and logical operations cannot operate directly between two arbitrary memory addresses. Data must be loaded from $\mathcal{M}$ into $\mathcal{R}$, computed inside the ALU, and written back to $\mathcal{M}$.

Axiom 4: Monotonic Execution & The Flag Vector

The Rule: The Instruction Pointer ($\text{RIP}$) advances monotonically through code:

$$\text{RIP}_{t+1} \leftarrow \text{RIP}_t + \text{sizeof}(\text{Current Instruction})$$

The Hardware Constraint: The CPU can only alter this linear vector if an instruction conditionally or unconditionally modifies $\text{RIP}$. Conditional jumps read a dedicated 1-bit status register—the Condition Codes:

$$\mathcal{C} = \langle \text{ZF (Zero)}, , \text{SF (Sign)}, , \text{CF (Carry)}, , \text{OF (Overflow)} \rangle$$

Axiom 5: The LIFO Stack FrontierThe Rule: The register $\text{RSP}$ (Stack Pointer) holds the memory address of the top of the runtime call stack.

The Hardware Constraint: The stack grows downward (toward lower numerical memory addresses)

$\text{push } X \implies \text{RSP} \leftarrow \text{RSP} - 8; \quad \mathcal{M}[\text{RSP}] \leftarrow X$

$\text{pop } X \implies X \leftarrow \mathcal{M}[\text{RSP}]; \quad \text{RSP} \leftarrow \text{RSP} + 8$

$\text{call } T \implies \text{push } \text{RIP}_{\text{next}}; \quad \text{RIP} \leftarrow T$

$\text{ret} \implies \text{pop } \text{RIP}$

Comparing what the code intended with the result observed by the runtime tool is

This is the fastest way to identify logical contradictions.

[Your Desktop (Host Machine)]
   VS Code UI (The "Head")
         │
         │ talks to localhost (127.0.0.1) on Port 44693
         ▼
[Port Forwarding Bridge]
         │
         ▼
[Inside Docker Container]
   `vscode-server` (Headless Server / Node.js)
   Reads files, runs bash, drives GCC / GDB / Valgrind

There are newer editors exploring the native route—such as Zed (written entirely in Rust) —which achieve lower memory footprints and faster startup times. But for an orchestration server handling basic text and process spawning, Node.js stays well within the "millisecond" thresholds needed for human typing.

building the system that manages the raw heap bytes.

gcc  -O0  -g  -fsanitize=address,undefined  -fno-omit-frame-pointer  bug.c  -o bug_san
 │    │    │              │                          │                │        │
 │    │    │              │                          │                │        └─ Output binary name
 │    │    │              │                          │                └─ Input source file
 │    │    │              │                          └─ Keep stack anchors (clean backtraces)
 │    │    │              └─ Inject ASan & UBSan runtime checks
 │    │    └─ Add source file/line debug symbols
 │    └─ Disable optimization (keep code literal for debugging)
 └─ The compiler (GNU Compiler Collection)

Every stack frame saves the address of the previous function's RBP right at the base of its own frame. This creates an exact singly-linked list embedded directly in the stack.

Room 0x000000000000  ───┐
Room 0x000000000001     │  "The Zero Page"
...                     │  (Rooms 0 to 4095) (4KB block)
Room 0x000000000FFF  ───┘  [LOCKED by the OS with a giant padlock]
------------------------------------------------------------------
Room 0x000000001000  ───┐
...                     │  Normal Usable Memory
Room 0x7FFFFFFFFFFF  ───┘  (Your variables, strings, buffers)

An LLM is a model that predicts the next token. Just give good guidance from the start. If you provide high-quality prompts and instructions from the start, It works cleverly by detecting patterns in far smarter areas.

A1. Yes, at an abstract level, every software bug is a mismatch between two formal specifications:

The Intended Logic (what the programmer believed or designed the system to do).

The Actual Logic (what the exact syntax, hardware architecture, and execution environment strictly mandate).

Computers are deterministic state machines; they never make "mistakes" or behave randomly on their own. They follow their instructions faithfully.

(The only edge cases that sit outside pure logical contradiction are physical hardware defects—like cosmic ray bit-flips, overheating circuits, or electrical faults—where physical reality violates the machine's underlying physical assumptions.)

Q2. Is a computer a deterministic state machine? Then why can Undefined Behavior occur randomly(?) in C language?

A2. A physical computer is indeed a deterministic state machine (barring hardware faults or external noise), but in C, Undefined Behavior (UB) exists at the level of the programming language specification, not the silicon.

The reason UB appears "random" or erratic comes down to a fundamental clash between 3 layers:

1) the C Language Standard, 2) the Optimizing Compiler, and 3) the Physical Hardware.

Summary: Pseudo-Randomness vs. Strict Determinism

1) The CPU is deterministic:

Given the exact same machine code, register values, memory contents, cache states, and OS scheduling, it will produce the exact same result every microsecond.

2) Undefined Behavior breaks the translation:

the optimizer operates under an absolute axiom: "The programmer never wrote Undefined Behavior." Because the compiler assumes UB is impossible, if a branch of code can only be reached via UB, the compiler concludes that branch is dead code and eliminates it entirely.

3) The environment provides invisible inputs:

Memory layout, compiler optimization levels (-O0 vs -O3), compiler versions, stack residue from prior calls, and OS memory paging all act as hidden inputs.

To the programmer looking only at the C text, it looks like magic or bad luck ("it worked on my machine!"). In reality, the machine is executing a deterministic path through an unintended, corrupted state.

A1. Nearly all memory safety bugs boil down to spatial or temporal violations, which map directly to the core principles Rust formalizes at compile time:

• Spatial Safety (Bounds / Invariants): Accessing memory outside the allocated boundary. Examples: buffer overflows, off-by-one errors, and out-of-bounds array indexing.

• Temporal Safety (Lifespan): Accessing or freeing memory at the wrong point in time. Examples: Use-After-Free (UAF), double-free, and stack-use-after-return.

• Protocol & Invariants (Ownership): Who is responsible for allocating, modifying, and deallocating a resource? When ownership is ambiguous, two subsystems assume the other is managing the memory, leading to aliasing bugs, leaks, or premature destruction.

The only additions at the systems level that don't fit neatly into these three are hardware/architecture invariants:

• Alignment faults: Trying to read a 64-bit integer from an unaligned address on architectures that enforce strict alignment (raises SIGBUS).

• Concurrency races: Multiple threads accessing the same memory without synchronization (data races).

• Type punning/aliasing rule violations: Violating strict aliasing rules, causing the compiler optimizer to emit incorrect machine code.

Q2. GDB vs. Valgrind vs. Sanitizers: When to Use What In VSCode, you can measure data movement at the assembly level in the memory and register areas on the right side, but it's important to figure out how to use that and to build a mental model for understanding the program at the OS/memory level, right?

A2. it is standard industry practice. Each tool operates at a different point in the debugging lifecycle:

• GDB

  • Execution control & state inspection (ptrace)
  • Post-mortem inspection (bt), live stepping, inspecting registers/memory at a exact crash point.
  • Does not automatically notify you when memory is corrupted before the crash happens.

• AddressSanitizer (ASan)

  • Compiler instrumentation (-fsanitize=address)
  • Real-time crash interception at the exact line of bad write/read (near-zero runtime overhead).
  • Requires recompilation; not available in locked-down production binaries.

• Valgrind (Memcheck)

  • Dynamic binary translation (simulated CPU)
  • Tracking memory leaks, uninitialized memory reads (Use of uninitialised value).
  • Slows execution down by 10x–30x; cannot catch global variable overflows easily.

The Workflow: Run tests under ASan/Valgrind to detect invisible corruptions early; drop into GDB when you need to step through logic or inspect raw registers and stack frames at the moment of failure.

[Registers, Memory, and the OS Mental Model] Watching registers in VS Code is useful only if you understand what the hardware expects. To build a clean mental model, keep these abstractions separated:

• Virtual Address Space: Every process lives in an illusion of 64-bit addresses managed by the OS page table:

  • Text (Code): Read-only instructions.
  • Data / BSS: Global and static variables.
  • Heap: Dynamic allocations (malloc), growing upwards.
  • Stack: Function stack frames, local variables, return addresses, growing downwards.

• The Register Role Model (x86-64 System V ABI):

  • RSP: Points to the top of the active stack frame.
  • RBP: Base frame pointer (when -fno-omit-frame-pointer is active).
  • RIP: The instruction pointer (the next instruction to execute).
  • RAX: Function return value.
  • RDI, RSI, RDX, RCX, R8, R9: Function call arguments (1 through 6).

  When you see SIGSEGV, it usually means RIP tried to read or write an address not mapped in the page table, or tried to write to a read-only page. When you see SIGABRT with stack smashing, GCC's stack canary detected that a local buffer wrote past its bounds and clobbered the saved frame pointer or return address.

Q3. When a bug occurs in a complex manner and sequentially from each of its causes, is the order of solving the problem important?

A3. Yes. Always solve the earliest cause in the execution timeline.

In C, memory bugs create latent undefined behavior. A corruption that occurs in Step A might not crash the program until Step D:

• Step A writes 1 byte past an array.
• Step B allocates a new chunk from malloc.
• Step C modifies another variable.
• Step D crashes inside free() because malloc metadata was altered in Step A.

If you try to fix Step D, you are treating a symptom of a poisoned heap. Rule of thumb: Trace backwards to the earliest invalid read/write operation. Once the first violation is eliminated, secondary crashes frequently disappear.

Q4. I only know a little C language syntax, have almost no debugging experience, and my understanding of the OS/memory concepts is weak. What mindset and tools are needed to understand mechanisms accurately at a professional level?

A4. Transitioning from knowing syntax to understanding system mechanisms requires treating the machine as deterministic:

• Mindset: "Memory is just a byte array with rules." Everything—code, pointers, integers, data structures—is simply bytes stored at a specific address. A pointer is not magic; it is an unsigned 64-bit integer whose value happens to be an address in virtual memory.

• Distinguish Syntax from Semantics:

  • int *p; allocates 8 bytes on the stack for a pointer. It allocates zero bytes for an integer until initialized.
  • char arr[10]; allocates 10 bytes on the stack.

• Verify, Don't Guess: Whenever code crashes, form an explicit hypothesis: "Variable buf has size 8, but memcpy writes 16 bytes, overwriting the adjacent pointer." Use GDB to confirm the addresses before changing a single line of code.

• Inspect Memory Directly:

  • In GDB, use x/gx (examine 8 bytes hex) and p &variable (address of variable).
  • Check boundaries: p (void)ptr - (void)base.

int main() 과 int moveMaxToFront(ListNode **ptrHead) 를 설명할테니까 제대로 이해했는지 판별해봐.

실행파일을 실행하면, int main() 함수부터 읽기 시작해. 인수를 아무것도 전달하지 않고 함수가 stack 에 쌓여. main() 프레임에서 지역변수 int c, i, j 가 sizeof(int) 만큼 할당돼. 값은 기존에 메모리에 남아있던 쓰레기 값이 그대로 있어. 단, c의 경우, 값이 1이 저장돼. 그리고 ll 구조체가 선언되니까 16바이트만큼 stack 에 할당돼. 그 16바이트 중에서, ll 의 head 필드는 8바이트 내부에 NULL 값(0x0)으로, ll 의 size 필드는 4바이트 내부에 0 값(0x0 과 구분되지 않음. 비트 레벨에서는 동일함.)으로 저장돼.

*#define NULL ((void)0) **매크로 상수 NULL 은 메모리 주소 0을 나타내는 상수다.

*return; 에서 return type 은 void return NULL; 에서 return type 은 void\ (왜냐하면 NULL 은 값이 0x0 이고, 타입이 void*(메모리 주소)이기 때문.)

(구체적으로, NULL은 값이 0x0000000000000000. 여기서 0은 16개. 왜냐하면 64비트 CPU 에서 포인터의 크기는 64비트, 2^64 = 16^16)**

c = 1 이니까 c != 0 이므로, while문의 첫 반복이 시작돼. 사용자가 20, 50, 10, 30 순으로 insert 했다고 가정할게. 그리고 2 을 입력했어. 그러면 case 2 와 매치되므로, moveMaxToFront(&(ll.head)); 가 실행돼. 그래서 함수로 진입하지.

moveMaxToFront(&(ll.head)) 가 stack 에서 main() 위에 쌓여. moveMaxToFront(&(ll.head)) 프레임에서 지역변수로 4개의 포인터가 자리를 차지해(아직 값은 없어).

1. 노드가 없거나 1개뿐인 경우는 아니므로, return 0; 을 무시하고,
2. 초기화를 해. maxNode 포인터 변수에 &20 가 할당돼. 1번째 노드를 최댓값으로 가정한 셈. maxPre 포인터 변수에 NULL 이 할당돼. 1번째 노드의 앞에는 아무것도 없어.

pre 포인터 변수에 &20 가 할당돼. cur 포인터 변수에 &50 가 할당돼. pre와 cur가 각각 1칸씩 이동한 셈.

cur 의 값이 &50 이니까 while 문 내부가 실행돼. 50 > 20 이므로, if문 내부가 실행돼. maxNode 포인터 변수에 &50 가 할당돼. maxPre 포인터 변수에 &20 가 할당돼.

그리고 pre 포인터 변수에 &50 가 할당돼. cur 포인터 변수에 &10 가 할당돼. pre와 cur가 각각 1칸씩 이동한 셈.

cur 의 값은 &10 이니까, NULL 이 아니므로, while 문 내부가 실행돼. 10 > 50 은 False 이므로, if문 내부가 실행 안돼.

그리고 pre 포인터 변수에 &10 가 할당돼. cur 포인터 변수에 &30 가 할당돼. pre와 cur가 각각 1칸씩 이동한 셈.

cur 의 값이 &30 이니까 while문 내부가 실행돼. 30 > 50 은 False 이므로, if 문 내부가 실행 안돼.

그리고 pre 포인터 변수에 &30 가 할당돼. cur 포인터 변수에 NULL 가 할당돼.

cur 의 값은 NULL 이니까, while 문의 조건은 False 이고, while 문 내부가 실행 안돼.

maxPre 값은 NULL 가 아니므로, if문 내부가 실행 안돼.

&20 다음에 &10을 연결해: [20 -> 10 -> 30] &50 다음에 &20을 연결해: [50 -> 20 -> 10 -> 30] *ptrHead 변수(ll.head)에 &50 을 할당해.

return 0 이 되면서, moveMaxToFront() 함수를 빠져나가고, stack 에서 해당 함수의 스택 프레임이 제거되고, 다시 main() 스택 프레임으로 진입해.

printf 함수가 실행되고, printList(&ll) 가 실행되고, removeAllItems(&ll) 가 실행되고, break; 로 switch문을 빠져나가면서, while문의 조건식인 c != 0 을 판별해. 현재 c = 2 이므로 True 라서 while문 내부로 들어가고, printf() 가 실행되고, scanf() 가 실행되고, 사용자가 0 을 입력했다고 가정하면, 변수 c 에 0 값이 대입되고, swich문에서 case 0 에 match 가 되면서, removeAllItems(&ll); 가 실행되고, break 로 switch문을 탈출하고, while문의 조건식인 c != 0 가 False 가 되면서 while문을 탈출하고, main() 본문의 다음줄인 return 0; 가 실행되고, main() 함수를 탈출하면서, 스택 프레임에서 main() 함수가 제거되고, 끝나.

1. The Kernel, File Descriptors, and the Open File Table

In C and POSIX systems, I/O operations do not operate on high-level objects or automatic streams; they rely directly on integer handles and kernel data structures.

• File Descriptors as Array Indices: A file descriptor (FD) is simply an integer index into a process's per-process file descriptor table.
• Standard descriptors are fixed by convention: 0 (stdin), 1 (stdout), and 2 (stderr).
• When opening a custom file via open(), the OS assigns the lowest available integer (typically 3).

• Kernel File Table vs. Process Table: While the file descriptor integer remains constant throughout the file's lifecycle, the kernel maintains an underlying struct file entry. This struct tracks access modes, pointers to the filesystem inode, and critically, the file offset (f_pos).

Process Space                         Kernel Space
┌────────────────────────┐            ┌───────────────────────────────┐
│ FD Table               │            │ Open File Table Entry         │
│  [0] -> stdin          │            │  struct file {                │
│  [1] -> stdout         │            │      uint64_t f_pos; (Offset) │
│  [2] -> stderr         │            │      struct inode *f_inode;   │
│  [3] -> file.txt       │ ─────────► │  };                           │
└────────────────────────┘            └───────────────────────────────┘

2. Direct Offset Manipulation with lseek

Reading sequentially with read() advances f_pos implicitly. However, jumping to specific disk locations requires direct repositioning via the lseek() system call:

off_t lseek(int fd, off_t offset, int whence);

• The Mechanics of whence:
• SEEK_SET: Absolute byte offset from the start of the file (0 to file size). Requires non-negative values.
• SEEK_END: Signed offset relative to the End-of-File (EOF). Passing negative numbers moves backward from the end (e.g., lseek(fd, -1024, SEEK_END)). Passing 0 positions the cursor at EOF and returns the total byte length of the file in O(1) time without reading the entire dataset.
• SEEK_CUR: Signed offset relative to the current cursor position.

• Why This Matters for Utilities like tail: Rather than reading a multi-gigabyte file sequentially from byte 0 to read the trailing lines, lseek repositions the kernel's internal offset directly to the end of the file, completely bypassing unnecessary disk I/O.

3. Buffering, System Calls, and Memory Traversal

At the hardware and OS interface, reading and memory access have fundamentally different constraints:

• Forward Kernel Reads: The read(fd, buf, count) system call reads sequentially forward from storage into a memory buffer. It does not natively read backward.
• Backward Analysis via Pointer Arithmetic: To implement reverse line scanning (as in tail), the data must be read forward in fixed-size chunks (e.g., 8 KB blocks) into a memory buffer (stack array or heap), after which the program walks the buffer in reverse using pointer arithmetic or reverse indexing: Target Byte = Base Address + Index Accessing elements in this memory buffer runs in O(1) time, keeping processing speeds bound to the CPU cache and memory bus rather than disk latency.

4. Edge Cases: Guardrails and Newline Semantics

Writing robust C-level file scanners requires accounting for low-level edge cases:

• Underflow and Clamping: When seeking backward in chunks (offset = current - chunk_size), files smaller than the chunk size will result in negative numbers. Seeking to negative offsets yields an EINVAL (Invalid Argument) error. The jump must be clamped: Seek Target = max(0, Length - Chunk Size)
• The Trailing Delimiter Trap: Text files commonly end with a trailing newline terminator (\n). A reverse byte scanner must recognize and skip this final character; otherwise, it will treat the empty space between the trailing \n and EOF as a distinct, empty line.
• EOF Detection via read(): The read() system call returns the number of bytes read. It does not throw an exception on EOF; it returns 0. A loop reading until completion must strictly check for bytes_read <= 0 as its termination condition.

Key Takeaway

Programming at this level makes it clear that files are treated simply as contiguous byte arrays on storage. Managing them efficiently requires coordinating kernel-level system calls (open, read, lseek, close), understanding how pointers and arrays map across stack and heap memory, and applying explicit boundary clamping to avoid underflows and invalid syscall arguments.

• 하드웨어 아키텍처 불일치: 최신 Mac(Apple Silicon(ARM64))에서 도커 컨테이너를 빌드한 후, Intel(x86_64) 칩이 탑재된 구형 클라우드 서버에서 실행하려고 할 때, 컨테이너 내부의 컴파일된 바이너리가 제대로 크로스 컴파일되지 않은 경우, 충돌할 수 있다.

• 커널 의존적 코드: 컨테이너는 호스트 머신의 리눅스 커널을 공유한다. 코드가, 호스트의 구형 OS에서 지원하지 않는, 최신 커널 기능에 의존하는 경우, 오류가 발생한다.

도커 컨테이너는 리눅스 커널 위에서 실행된다. 리눅스 커널에 내장되어 있는 기능을 이용한다.

• 네임스페이스 기능 (프로세스, 네트워크, 파일 시스템 등을 격리)
• 컨트롤 그룹 기능 (Cgroups, CPU/Memory 사용량을 제한)

윈도우에는 Windows NT 커널이, 맥OS에는 XNU 커널이 있다. 근데 어떻게 Docker를 실행할 수 있을까? 백그라운드에서 리눅스 VM 을 가동하기 때문이다.

• 윈도우의 경우: Hyper-V 또는 WSL 2
• 맥OS의 경우: 하이퍼바이저 프레임워크

맥에서 Docker 컨테이너를 실행할 때, 백그라운드의 리눅스 VM 안에서 실행된다. 컨테이너는 맥OS와 직접 통신하지 않는다.

"리눅스가 아닌" 컨테이너도 있다. 윈도우 컨테이너. Windows Server 에서 Docker 를 실행하는 경우, 윈도우 컨테이너를 생성할 수 있다. 그 컨테이너는 Windows 커널을 공유하며 네이티브 Windows APP(ex. .NET Framework, IIS 웹 서버)를 실행한다.

하지만 리눅스 호스트에서 윈도우 컨테이너를 실행할 수는 없다.

로컬 docker 캐시

현실은 카오스 세계인데, CPU cache 에서 temporal/spatial locality 경향성이 발견된다는 게 신기하다.

세상에 당연한 게 있는가? 언뜻 결과가 당연해 보여도, 그 과정은 당연하지 않다. 논리적인 과정이 있으며, 사유의 기본인 논리 3법칙(동일률, 모순율, 배중률)마저 철학자에게는 치열한 의심의 대상이다. 물리법칙도 당연하지 않다. 물리법칙은 세계 그 자체(물자체)를 인간의 사유로 추상화해낸 결과다. 알고리즘의 결과는 과연 당연한가? 그 결과를 하드웨어 작동 관점에서 설명하지 못하면, 당연하다고 말하는 건 오류다.

현대수학에 관한 책을 쓰며 사람들과 치열하게 토론했던 과거의 경험이 갑자기 소중하게 느껴진다. 수학자가 최초에 그러했듯, "무한이라는 거대한 대상을 유한의 문제로 어떻게 끌어내릴 것인가" 라는 질문을 받았을 때, 나는 엄청난 짜증과 불쾌함을 느꼈다. '순수수학으로 먹고 살 것도 아닌데 왜 그런 골치 아픈 고민까지 해야 하지?' 하던 반발심이었다. 하지만 그 시절 고뇌했던 경험이 지금은 새삼 소중하다. 무엇에도 얽매이지 않고 끝까지 파고드는 자유로운 감성이기 때문이다.

불쾌함을 솔직하게 드러내고 단순한 요소로 끝까지 파고들었을 때 비로소 이해했다고 말할 수 있다고 생각한다.

나도 알고 있다. 이 감성을 유지하기 위해서는 상당한 에너지가 들며, 일상생활에서 마찰이 굉장히 커진다는 것을. 하지만 기본 원리에 대한 이해에 이르기 위해서 불가피하다고 생각한다. 자연과 세상은 인내력이 많은 관찰자에게만 놀라운 모습을 보여준다고 믿는다.

기계어는 전기 전압 상태를 나타내는, 0과 1로 구성된 원시 이진 비트 스트림 이다. CPU 는 고정 배선된 logic gate (트랜지스터로 구성된 AND/OR/NOT 게이트) 를 통해 전류를 전달받을 뿐이다. 트랜지스터는 숫자를 이해하지 못한다. 오직 전류만 이해한다.

• 고전압 (ex. 5V) 이 회로를 흐르면, 1로 해석한다.
• 저전압/무전압 (ex. 0V) 은, 0으로 해석한다.

에뮬레이터는 전기로 on/off 되는 물리적 스위치의 동작을 모방한다.

때로는 제가 다른 사람들의 생각이 잠시 머물다 가는 그릇 같다는 생각을 한다. 생각이 이 그릇에서 저 그릇으로 옮겨 다니며 점차 풍성해지는 것이 신기하다. 마음이 맑은 날에는 제가 거대한 구조의 아주 작은 일부라는 것이 잘 느껴진다. 공동 연구가 훨씬 더 멀리 갈 수 있고 훨씬 더 깊이 갈 수 있다.

나는 문제가 안 풀리면 포기한다. 일종의 직관인데 ‘내가 이걸 조금 노력하면 몇 달 안에 풀겠다, 아니다’처럼 판단이 필요하다. 잘 포기하는 것도 굉장히 중요한 재능이라고 생각한다. 어떤 종류의 문제들은 개인이 이해할 준비가 안 됐거나 인류가 이해할 준비가 안 된 것일 수도 있다. 그걸 붙잡고 있는 것은 생산적이지 않다. 문제를 해결하고 풀어내는 것은 사실 우연이라고 생각한다. 지난주에는 전혀 이해하지 못하고 해법을 상상할 수 없었는데 오늘 갑자기 생각이 나는 경우가 있다

수학의 매력은 자유로움이다. 수학엔 논리가 맞아야 한다는 규칙이 있다. 그런데 그 규칙의 엄격함 때문에 다른 면에서 자유롭다. 어떤 대상을 연구할 것인지, 어떻게 이해하고 풀어야 하는지 정해진 규칙이 하나도 없다. 수학은 자유로움을 학습하는 일이다. 그래서 어렸을 땐 얽매이지 않고 많은 생각을 자유롭게 하는 훈련을 하면 좋을 것 같다

트리 탐색이란? 모든 노드를 체계적인 순서대로 순회하는 과정이다. 트리는 비선형적이어서, 탐색 방법은 여러 가지다.

각각의 방법은 어떤 문제를 어떻게 해결하는가?

depth: (Stack/Recursive) Search all possible paths

breadth: (Queue/Iterative) Search the shortest path, Connectivity Check, AI & Search Problems

ㅇ너비 우선 탐색 (BFS): Breadth First, layer by layer ㅇ깊이 우선 탐색 (DFS): Depth First, Backtracking 대표 3가지

1. 선순서(Preorder): Top-Down (복제, 저장/직렬화)
2. 후순서(Postorder): Bottom-Up (삭제, 폴더 크기 계산)
3. 중순서(Inorder): Left-to-Right (BST 이진 탐색 트리의 데이터를 정렬 및 추출)

1. 선순서 (Top-Down)

• 문제: 파일은 1차원, 트리는 2차원
  • 하드 드라이브에 있는 파일은 선형적인 바이트 시퀀스다.
  • 트리를 파일로 직렬화하려면, 2차원 분기 구조를 1차원 데이터로 만들어야 한다.

일반적으로, 자식은 부모의 주소를 저장하지 않는다 (예외: red-black tree 등등) 그래서 파일 로딩은 선순서가 타당하다.

2. 후순서 (Bottom-Up) "폴더의 크기를 계산할 때, 폴더 하위의 모든 파일의 크기를 합산하는 게 먼저다"
3. 중순서 (Left-to-Right)

linked-list 에서 head 가 포인터를 잃어버리면, 메모리 누수가 발생할 수 있는 것처럼, tree 에서 root 를 잃어버리면, 메모리 누수가 발생할 수 있는 건가봐? -> 그렇다. 프로그램은 유일한 진입점을 잃어버린 상태다. tree 를 안전하게 free() 하고 그 메모리를 OS에 반환하려면, tree 를 순회하며 모든 노드에 대해 free() 를 호출해야 한다. 만약 root 변수가, 덮어쓰이거나, NULL 로 설정되거나, free() 를 호출하지 않고 범위 밖으로 빠져나가면, 그 하위 노드들에 접근할 수 없다. 그 노드들은 프로그램이 실행되는 동안 RAM 에서 고립된다. 더이상 사용할 수도 없고, 주소를 잃어버려서 삭제할 수도 없다. 최신 OS 는 프로그램이 최종적으로 종료되고 셧다운될 때 프로세스가 할당한 모든 메모리를 자동으로 회수하지만, 오래 실행되는 서버 APP 의 경우, 사용 가능한 RAM 을 소모하여 시스템이 다운될 여지가 있다. 그래서 malloc 에 대응해서 결국에는 free 해야 하며, 항상 진입점 (head 또는 root) 을 보호해야 한다.

지금 말하는 tree는 main.rs 진입, main() 진입이랑 연관 있어? -> 맞다.

Q. 메모리 전수조사가 가능하다고 치자. 10 GB 메모리를 스캔하는 데에 몇 초 걸려? A. 현대 RAM의 순차 읽기 속도는 초당 30~60 GB 다. OS를 우회해서 바이트를 스캔했다고 하더라도, 어떤 바이트가 head 인지, 어떻게 알 수 있을까? 고유한 시그니처나 메타데이터가 없다면, head 를 특정할 수 없다. * 프로그래밍 언어가 참조와 포인터에 의존하는 이유다. 정확한 좌표이기 때문이다. *