1// Copyright 2018 syzkaller project authors. All rights reserved. 2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. 3 4package prog 5 6import ( 7 "fmt" 8) 9 10// memAlloc keeps track of allocated objects in a program 11// and decides where to allocate new objects. 12// It has 2 main methods: noteAlloc which is called for existing allocations 13// in a program as we analyze it; and alloc which decides where to allocate 14// a new object. 15// The implementation is based on a 2-level bitmap where each bit represents 16// 64 bytes (memAllocGranule) of program memory. 17type memAlloc struct { 18 size uint64 19 mem [memAllocL1Size]*[memAllocL0Size]uint64 20 buf [memAllocL0Size]uint64 21} 22 23const ( 24 memAllocGranule = 64 // 1 bit per that many bytes (all allocations are rounded to this size) 25 memAllocMaxMem = 16 << 20 26 memAllocL0Size = 64 27 bitsPerUint64 = 8 * 8 28 memAllocL0Mem = memAllocL0Size * memAllocGranule * bitsPerUint64 29 memAllocL1Size = memAllocMaxMem / memAllocL0Mem 30) 31 32func newMemAlloc(totalMemSize uint64) *memAlloc { 33 if totalMemSize > memAllocMaxMem { 34 panic(fmt.Sprintf("newMemAlloc: too much mem %v (max: %v)", totalMemSize, memAllocMaxMem)) 35 } 36 if totalMemSize%memAllocL0Mem != 0 { 37 panic(fmt.Sprintf("newMemAlloc: unaligned size %v (align: %v)", totalMemSize, memAllocL0Mem)) 38 } 39 ma := &memAlloc{ 40 size: totalMemSize / memAllocGranule, 41 } 42 ma.mem[0] = &ma.buf 43 return ma 44} 45 46func (ma *memAlloc) noteAlloc(addr0, size0 uint64) { 47 addr := addr0 / memAllocGranule 48 size := (addr0+size0+memAllocGranule-1)/memAllocGranule - addr 49 for i := uint64(0); i < size; i++ { 50 ma.set(addr + i) 51 } 52} 53 54func (ma *memAlloc) alloc(r *randGen, size0 uint64) uint64 { 55 if size0 == 0 { 56 size0 = 1 57 } 58 size := (size0 + memAllocGranule - 1) / memAllocGranule 59 end := ma.size - size 60 for start := uint64(0); start < end; start++ { 61 empty := true 62 for i := uint64(0); i < size; i++ { 63 if ma.get(start + i) { 64 empty = false 65 break 66 } 67 } 68 if empty { 69 start0 := start * memAllocGranule 70 ma.noteAlloc(start0, size0) 71 return start0 72 } 73 } 74 ma.bankruptcy() 75 return ma.alloc(r, size0) 76} 77 78func (ma *memAlloc) bankruptcy() { 79 for i1 := uint64(0); i1 < ma.size/(memAllocL0Size*bitsPerUint64); i1++ { 80 if ma.mem[i1] == nil { 81 continue 82 } 83 for i0 := range ma.mem[i1] { 84 ma.mem[i1][i0] = 0 85 } 86 } 87} 88 89func (ma *memAlloc) pos(idx uint64) (i1, i0, bit uint64) { 90 i1 = idx / (memAllocL0Size * bitsPerUint64) 91 r1 := idx % (memAllocL0Size * bitsPerUint64) 92 i0 = r1 / bitsPerUint64 93 bit = 1 << (r1 % bitsPerUint64) 94 return 95} 96 97func (ma *memAlloc) set(idx uint64) { 98 i1, i0, bit := ma.pos(idx) 99 if ma.mem[i1] == nil { 100 ma.mem[i1] = new([memAllocL0Size]uint64) 101 } 102 ma.mem[i1][i0] |= bit 103} 104 105func (ma *memAlloc) get(idx uint64) bool { 106 i1, i0, bit := ma.pos(idx) 107 if ma.mem[i1] == nil { 108 return false 109 } 110 return ma.mem[i1][i0]&bit != 0 111} 112 113type vmaAlloc struct { 114 numPages uint64 115 used []uint64 116 m map[uint64]struct{} 117} 118 119func newVmaAlloc(totalPages uint64) *vmaAlloc { 120 return &vmaAlloc{ 121 numPages: totalPages, 122 m: make(map[uint64]struct{}), 123 } 124} 125 126func (va *vmaAlloc) noteAlloc(page, size uint64) { 127 for i := page; i < page+size; i++ { 128 if _, ok := va.m[i]; ok { 129 continue 130 } 131 va.m[i] = struct{}{} 132 va.used = append(va.used, i) 133 } 134} 135 136func (va *vmaAlloc) alloc(r *randGen, size uint64) uint64 { 137 if size > va.numPages { 138 panic(fmt.Sprintf("vmaAlloc: bad size=%v numPages=%v", size, va.numPages)) 139 } 140 var page uint64 141 if len(va.used) == 0 || r.oneOf(5) { 142 page = r.rand(4) 143 if !r.oneOf(100) { 144 page = va.numPages - page - size 145 } 146 } else { 147 page = va.used[r.rand(len(va.used))] 148 if size > 1 && r.bin() { 149 off := r.rand(int(size)) 150 if off > page { 151 off = page 152 } 153 page -= off 154 } 155 if page+size > va.numPages { 156 page = va.numPages - size 157 } 158 } 159 if page >= va.numPages || size > va.numPages || page+size > va.numPages { 160 panic(fmt.Sprintf("vmaAlloc: bad page=%v size=%v numPages=%v", page, size, va.numPages)) 161 } 162 va.noteAlloc(page, size) 163 return page 164} 165