1. 개념 요약

맵은 키로 값을 찾는 자료구조다. Go에서 make(map[K]V)로 만들고 m[k] = v로 넣고 m[k]로 읽는다.

freestanding 커널에는 완성된 Go 런타임이 없으므로 맵 연산에 필요한 런타임 함수를 직접 구현해야 한다. go-os는 해시 테이블 대신 키와 값 배열을 선형 탐색하는 최소 구현으로 map[int]int를 지원한다.

2. 왜 필요한가

새 자료를 쌓다 보면 "이 키에 해당하는 값"을 빠르게 찾고 싶을 때가 있다. 배열을 매번 처음부터 뒤지는 대신 키로 바로 접근하는 맵이 그 일을 맡는다.

make, m[k] = v, m[k]는 컴파일 과정에서 런타임 맵 함수 호출로 변환된다. freestanding 커널에 해당 함수가 정의돼 있지 않으면 링크 과정에서 undefined symbol 오류가 발생한다.

3. 등장 배경

메모리 할당기에서 heap을 열어 new와 슬라이스를 쓸 수 있게 됐다. 슬라이스는 인덱스(정수 위치)로 접근하지만 임의의 키로 값을 찾지는 못한다.

맵 연산을 추가하면 gccgo가 runtime.makemap__small 등의 심볼을 참조한다. 이 심볼을 커널의 맵 구현과 연결해야 빌드를 완료할 수 있다.

4. 필요한 조건

조건설명
heap 할당기맵의 키·값 배열에 사용할 메모리를 동적으로 할당한다.
맵 함수 제공makemap_small, mapassign_fast64, mapaccess1_fast64를 구현한다.
서술자 제공키 타입 서술자가 참조하는 memequal8..f, memhash64..f를 정의한다.
심볼 이름 일치gccgo가 밑줄을 둘로 바꾸므로 //go:linkname 대상을 그 형태로 적어야 한다.

5. 핵심 구성 요소

gccgo는 키의 종류와 폭에 따라 특화된 함수를 부른다. 64비트 키는 __fast64 변형이다.

구성 요소역할
makemap_smallmake(map[K]V)가 호출하며 빈 맵의 주소를 반환한다.
mapassign_fast64m[k] = v가 호출하며 값을 저장할 영역의 주소를 반환한다.
mapaccess1_fast64v := m[k]가 호출하며 저장된 값의 주소를 반환한다.
hmap(자체 정의)키 배열·값 배열·개수를 담는다. 호출자는 내부를 보지 않는다.

호출 코드는 make가 반환한 맵 포인터를 런타임 함수에 전달하고, mapassign_fast64와 mapaccess1_fast64가 반환한 값 영역의 주소를 사용한다. 이 호출 규약을 지키는 범위에서 내부 저장 구조를 별도로 정의할 수 있다.

6. 동작 흐름

flowchart TD
    A["m[k] = v"]
    B["gccgo가 mapassign_fast64 호출"]
    C["키를 선형 탐색"]
    D{"키가 있나"}
    E["기존 값 슬롯 주소 반환"]
    F["새 슬롯 만들고 주소 반환"]
    G["호출자가 그 주소에 v 저장"]

    A --> B --> C --> D
    D -- 있음 --> E --> G
    D -- 없음 --> F --> G

m[k] = v는 두 단계로 처리된다. mapassign_fast64가 키에 해당하는 값 영역의 주소를 반환하면 호출 코드가 그 위치에 값을 저장한다. 조회 시에는 mapaccess1_fast64가 반환한 주소에서 값을 읽는다.

7. 상태 변화

단계맵 상태
make 직후개수 0. 빈 키·값 배열만 있다.
새 키 저장키·값 배열 끝에 추가하고 개수를 1 늘린다.
기존 키 저장개수는 그대로. 찾은 슬롯의 값만 덮어쓴다.
없는 키 조회값 타입의 0을 저장한 공통 영역의 주소를 반환하며 맵은 변경하지 않는다.

8. 코드나 설정에서 나타나는 형태

맵 함수를 //go:linkname으로 묶는다. 대상 이름은 밑줄을 둘로 적는다. gccgo가 Go 이름의 밑줄 하나를 심볼에서 둘로 바꾸기 때문이다.

//go:linkname mapassign_fast64 runtime.mapassign__fast64
func mapassign_fast64(t unsafe.Pointer, h *hmap, key uint64) unsafe.Pointer {
	// 키를 선형 탐색해 값 영역의 주소를 반환한다
}

이 코드는 m[k] = v의 앞부분, 즉 값을 쓸 자리를 정하는 단계에 해당한다. 실제 저장은 호출자가 돌려받은 주소에 한다.

9. 자주 헷갈리는 지점

//go:linkname의 대상 이름은 변환 없이 심볼이 된다. 반면 gccgo는 Go 함수 이름의 밑줄 하나를 심볼에서 둘로 바꾼다. 따라서 mapassign_fast64를 대상으로 지정하면 호출자가 찾는 mapassign__fast64와 일치하지 않는다. 밑줄이 없는 newobject 같은 함수가 동작했던 이유는 변환 전후의 이름이 같았기 때문이다.

gccgo는 키 종류마다 다른 함수를 부른다. 64비트 키는 __fast64, 문자열 키는 __faststr 식이다. map[int]int만 지원하려면 __fast64 함수만 채우면 되지만 다른 키 타입을 쓰면 그에 맞는 함수가 더 필요하다.

Go에서 존재하지 않는 키를 조회하면 값 타입의 0이 반환된다. 이 동작을 맞추기 위해 mapaccess는 키를 찾지 못했을 때 0을 저장한 공통 영역의 주소를 반환한다.

10. 확인 방법

확인 대상확인 방법
맵 생성·저장맵에 값을 넣고 다시 읽어 같은 값이 나오는지 본다.
덮어쓰기같은 키에 다른 값을 넣고 나중 값이 읽히는지 본다.
없는 키넣지 않은 키를 읽어 0이 나오는지 본다.

go-os는 부팅 자체 검증에서 맵을 만들고 저장·덮어쓰기·없는 키 조회를 거친 뒤 결과를 시리얼로 보낸다. heap self-test: OK (new/slice/append/map)가 나오면 맵 경로까지 동작한 것이다.

11. 다음에 볼 개념

지금 맵은 8바이트 키와 값(map[int]int)만 다루고 선형으로 탐색한다. 키·값 크기를 맵 타입 서술자에서 읽어 일반화하는 것, 문자열 키(__faststr)를 지원하는 것, delete와 range를 더하는 것이 다음 과제다. 항목이 많아질 때를 대비한 정식 해시 테이블도 그 뒤에 온다.

참고 자료