Reversing-golang Reversing Go - Part 3
Post
Cancel

Reversing Go - Part 3

Understanding Map

Creating a map

makemap, makemap_small, makemap64 are the three functions used for creating a map. Sometimes the map may be created on the stack (depends on escape analysis). The builtin function make has the following usage when creating a map

SyntaxDescription
make(T)map of type T
make(T, n)map of type T with initial space for approximately n elements

when n <= 8, makemap_small is used, otherwise makemap is called.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type sym struct {
    name   string
    weight int64
}

func main() {
    m1 := make(map[sym]string, 7)
    fmt.Printf("%v has hint %d\n", m1, 7)
    m1 = make(map[sym]string, 8)
    fmt.Printf("%v has hint %d\n", m1, 8)
    m1 = make(map[sym]string, 9)
    fmt.Printf("%v has hint %d\n", m1, 9)
    m1 = make(map[sym]string, uint64(len(os.Args)))
    m2 := map[string]string{
        "Alpha": "Beta",
        "Theta": "Phi",
        "Omega": "Epsilon",
    }
    if a, ok := m2["Gamma"]; !ok {
        fmt.Printf("No Gamma! %v\n", a)
    }
    m1[sym{"Epsilon", 4}] = "Gamma"
    fmt.Println(m1)
    fmt.Println(m2)
}

For the first two make functions, Go uses makemap_small, since the second param (n) <= 8. For the third make call, makemap is used.

1
2
3
4
5
6
7
8
9
10
11
.text:04A79E5    mov     rax, cs:os_Argc
.text:04A79EC    lea     rcx, mapmain_symstring
.text:04A79F3    mov     [rsp+110h+var_110], rcx
.text:04A79F7    mov     [rsp+110h+var_108], rax
.text:04A79FC    mov     [rsp+110h+var_100], 0
.text:04A7A05    call    runtime_makemap
.text:04A7A0A    mov     rax, [rsp+110h+var_F8]
.text:04A7A0F    mov     [rsp+110h+m1], rax
.text:04A7A14    call    runtime_makemap_small
.text:04A7A19    mov     rax, [rsp+110h+var_110]
.text:04A7A1D    mov     [rsp+110h+m2], rax

makemap takes three params - the mapType, hint, and a pointer to an existing map. If the pointer to an existing map is provided, the new map is created in that place. makemap family returns a pointer to hmap. This implies, maps are represented as *hmap. hmap is defined in part-1

To find out the type of the map being used, there are many ways. First is to look at the first param of makemap.

1
2
3
4
5
6
type mapType struct {
    rtype
    key    *rtype // map key type
    elem   *rtype // map element (value) type
    // ...
}

From this struct we can get the type of key and value being used. In the example, m1’s key has type sym and m1’s elem has type string which makes it map[sym]string

A second map is created using makemap_small and is assigned to m2.

Assigning values to keys

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.text:04A7A1D    mov     [rsp+110h+m2], rax
.text:04A7A22    lea     rcx, stru_4B7040
.text:04A7A29    mov     [rsp+110h+var_110], rcx
.text:04A7A2D    mov     [rsp+110h+var_108], rax
.text:04A7A32    lea     rdx, aAlpha     ; "Alpha"
.text:04A7A39    mov     [rsp+110h+var_100], rdx
.text:04A7A3E    mov     [rsp+110h+var_F8], 5
.text:04A7A47    call    runtime_mapassign_faststr
.text:04A7A4C    mov     rdi, [rsp+110h+var_F0]
.text:04A7A51    mov     qword ptr [rdi+8], 4
.text:04A7A59    cmp     cs:runtime_writeBarrier, 0
.text:04A7A60    jnz     loc_4A7D6A
.text:04A7A66    lea     rax, aBeta      ; "Beta"
.text:04A7A6D    mov     [rdi], rax

.rdata:04B7040 stru_4B7040     mapType <<8, 8, 29E7A159h, 2, 8, 8, MAP or 20h, 0, offset runtime_gcbits__, 4529h, 0>, offset string_autogen_2QFJSK, offset string_autogen_2QFJSK, offset map_bucketstringstring, offset off_4D5FF8, 10h, 10h, 10h, 1, 0Ch, 0, 0>

mapassign family takes three params - type of map, the map instance (pointer to hmap), and the key. It returns a pointer to the slot where the value can be placed. In the above snippet, the value “Beta” is assigned to the key “Alpha” in m2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
.text:04A7B73    lea     rax, aEpsilon   ; "Epsilon"
.text:04A7B7A    mov     qword ptr [rsp+110h+var_80], rax
.text:04A7B82    mov     qword ptr [rsp+110h+var_80+8], 7
.text:04A7B8E    mov     [rsp+110h+var_70], 4
.text:04A7B9A    lea     rax, mapmain_symstring
.text:04A7BA1    mov     [rsp+110h+var_110], rax    ; mapType
.text:04A7BA5    mov     rcx, [rsp+110h+m1]
.text:04A7BAA    mov     [rsp+110h+var_108], rcx    ; map instance
.text:04A7BAF    lea     rdx, [rsp+110h+var_80]
.text:04A7BB7    mov     [rsp+110h+var_100], rdx    ; key
.text:04A7BBC    nop     dword ptr [rax+00h]
.text:04A7BC0    call    runtime_mapassign
.text:04A7BC5    mov     rdi, [rsp+110h+var_F8]
.text:04A7BCA    mov     qword ptr [rdi+8], 5
.text:04A7BD2    cmp     cs:runtime_writeBarrier, 0
.text:04A7BD9    jnz     loc_4A7CA5
.text:04A7BDF    lea     rax, aGamma     ; "Gamma"
.text:04A7BE6    mov     [rdi], rax

In this code, var_80 is a string with value “Epsilon”. The map m1 is indexed using var_80 as the key and assigns the string “Gamma” to it. Is var_80 a string?? Look at the map type - mapmain_symstring, it has the key of type main_sym which is a structType of two members - name and weight

Fetching values using key

mapaccess family has two variants

1
2
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

mapaccess1 returns pointer to the element that corresponds to the given key. If there is no such element, a pointer to zero is returned

mapaccess2 is same as mapaccess1, except it returns an additional boolean which says the given key exists or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
.text:04A7B16    lea     rax, stru_4B7040
.text:04A7B1D    mov     [rsp+110h+var_110], rax
.text:04A7B21    mov     rcx, [rsp+110h+m2]
.text:04A7B26    mov     [rsp+110h+var_108], rcx
.text:04A7B2B    lea     rdx, aGamma     ; "Gamma"
.text:04A7B32    mov     [rsp+110h+var_100], rdx
.text:04A7B37    mov     [rsp+110h+var_F8], 5
.text:04A7B40    call    runtime_mapaccess2_faststr
.text:04A7B45    mov     rax, [rsp+110h+var_F0]
.text:04A7B4A    mov     rcx, [rax]
.text:04A7B4D    mov     rax, [rax+8]
.text:04A7B51    cmp     byte ptr [rsp+110h+var_E8], 0
.text:04A7B56    jz      loc_4A7CB6

If “Gamma” exists in m2, then a pointer to the value is returned. var_F0 is the returned pointer, and var_e8 is the boolean. The jump at .text:04A7B56 is taken if “Gamma” does not exist in m2.

Iterating a Map

Let’s consider another small program

1
2
3
4
5
6
7
8
9
10
11
func main() {
    kv := make(map[string]string)
    for i, v := range os.Environ() {
        lst := strings.Split(v, "=")
        kv[lst[0]] = lst[1]
        fmt.Printf("%d => %q\n", i, v)
    }
    for key, value := range kv {
        fmt.Printf("%s => %s\n", key, value)
    }
}

Without wasting any time, let’s dig into it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.text:04A8A81    xorps   xmm0, xmm0
.text:04A8A84    movups  [rsp+288h+var_1A8], xmm0
.text:04A8A8C    movups  [rsp+288h+var_198], xmm0
.text:04A8A94    movups  [rsp+288h+var_188], xmm0
.text:04A8A9C    lea     rdi, [rsp+288h+var_118]
.text:04A8AA4    lea     rdi, [rdi-30h]
.text:04A8AA8    mov     [rsp+288h+var_298], rbp
.text:04A8AAD    lea     rbp, [rsp+288h+var_298]
.text:04A8AB2    call    sub_46515C
.text:04A8AB7    mov     rbp, [rbp+0]
.text:04A8ABB    lea     rax, [rsp+288h+var_118]
.text:04A8AC3    mov     qword ptr [rsp+288h+var_198], rax
.text:04A8ACB    call    runtime_fastrand
.text:04A8AD0    mov     eax, dword ptr [rsp+288h+var_288]
.text:04A8AD3    mov     dword ptr [rsp+288h+var_1A8+0Ch], eax

Oh! There isn’t any call to makemap! How do we find the map?? No need to panic. One way is to look at the second param of mapassign and mapaccessN. Let’s look at another way. Shall we ?

Recall from part-1 that the hmap struct is

1
2
3
4
5
6
7
8
9
10
11
type hmap struct {
    count     int               // +00
    flags     uint8             // +08
    B         uint8             // +09
    noverflow uint16            // +0A
    hash0     uint32 // hash seed, +0C
    buckets    unsafe.Pointer   // +10
    oldbuckets unsafe.Pointer   // +18
    nevacuate  uintptr          // +20
    extra *mapextra             // +28
}

The hash seed sounds something of a pseudorandom number. Also, we have a call to runtime_fastrand. fastrand assigns the return value to var_1A8+0Ch, also, we have offset of hash0 is 12. So, we can deduce var_1A8 contains the map instance. I will discuss the alignment and sizes in another post.

1
2
3
4
5
6
7
.text:04A8CF3    lea     rax, mapstringstring
.text:04A8CFA    mov     [rsp+288h+var_288], rax
.text:04A8CFE    lea     rax, [rsp+288h+var_1A8]
.text:04A8D06    mov     [rsp+288h+var_280], rax
.text:04A8D0B    lea     rax, [rsp+288h+var_178]
.text:04A8D13    mov     [rsp+288h+var_278], rax
.text:04A8D18    call    runtime_mapiterinit

The map var_1A8 has type map[string]string. runtime_mapiterinit initializes a structure for iterating through the map - hiter. The iterator hiter is stored in var_178

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type hiter struct {
    key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/internal/gc/range.go).
    elem        unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go).
    t           *maptype
    h           *hmap
    buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
    bptr        *bmap          // current bucket
    overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
    oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
    startBucket uintptr        // bucket iteration started at
    offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
    wrapped     bool           // already wrapped around from end of bucket array to beginning
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}

From the comment, key must be nil to indicate the end of iteration.

1
2
3
4
5
6
.text:04A8E25    mov     rax, [rsp+288h+var_178]
.text:04A8E2D    test    rax, rax               ; iter.key is nil ?
.text:04A8E30    jnz     loc_4A8D25
.text:04A8E36    mov     rbp, [rsp+288h+var_8]
.text:04A8E3E    add     rsp, 288h
.text:04A8E45    retn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
.text:04A8D25    mov     rcx, [rsp+288h+var_170]    ; iter.elem
.text:04A8D2D    mov     rdx, [rax]                 ; *iter.key
.text:04A8D30    mov     rbx, [rcx]                 ; *iter.elem
.text:04A8D33    mov     [rsp+288h+var_210], rbx
.text:04A8D38    mov     rax, [rax+8]
.text:04A8D3C    mov     rcx, [rcx+8]
.text:04A8D40    mov     [rsp+288h+var_230], rcx    ; len(*iter.elem)
.text:04A8D45    mov     [rsp+288h+var_288], rdx    ; *iter.key
.text:04A8D49    mov     [rsp+288h+var_280], rax    ; len(*iter.key)
.text:04A8D4E    call    runtime_convTstring
.text:04A8D53    mov     rax, [rsp+288h+var_278]
.text:04A8D58    mov     [rsp+288h+var_200], rax
.text:04A8D60    mov     rcx, [rsp+288h+var_210]
.text:04A8D65    mov     [rsp+288h+var_288], rcx    ; *iter.elem
.text:04A8D69    mov     rcx, [rsp+288h+var_230]
.text:04A8D6E    mov     [rsp+288h+var_280], rcx    ; len(*iter.elem)
.text:04A8D73    call    runtime_convTstring
.text:04A8D78    mov     rax, [rsp+288h+var_278]

var_200 contains *iter.key and rax contains *iter.elem. These values are printed using the format string “%s => %s\n”

1
2
3
4
.text:04A8E0F    lea     rax, [rsp+288h+var_178]
.text:04A8E17    mov     [rsp+288h+var_288], rax
.text:04A8E1B    nop     dword ptr [rax+rax+00h]
.text:04A8E20    call    runtime_mapiternext

runtime_mapiternext is used to advance the map iterator (hiter) to the next entry.

1
2
func mapiterinit(t *maptype, h *hmap, it *hiter)
func mapiternext(it *hiter)

Deleting entry

The mapdelete family takes three params - mapType, map instance and the key to delete

1
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

Deleting all entries

What if we had a loop that deleted all entries from a given map

1
2
3
4
5
6
7
8
9
10
11
12
func main() {
	kv := make(map[string]string)
	for i, v := range os.Environ() {
		lst := strings.Split(v, "=")
		kv[lst[0]] = lst[1]
		fmt.Printf("%d => %q\n", i, v)
	}
    // the following loop is optimized
	for key := range kv {
		delete(kv, key)
	}
}

In this case, the go compiler replaces the entire loop with runtime.mapclear

1
func mapclear(t *maptype, h *hmap)
This post is licensed under CC BY 4.0 by the author.