prog: rework address allocation

1. mmap all memory always, without explicit mmap calls in the program.
This makes lots of things much easier and removes lots of code.
Makes mmap not a special syscall and allows to fuzz without mmap enabled.

2. Change address assignment algorithm.
Current algorithm allocates unmapped addresses too frequently
and allows collisions between arguments of a single syscall.
The new algorithm analyzes actual allocations in the program
and places new arguments at unused locations.

1 files changed, 164 insertions, 0 deletions

diff --git a/prog/alloc.go b/prog/alloc.go
new file mode 100644
index 000000000..c47fc703d
--- /dev/null
+++ b/prog/alloc.go
@@ -0,0 +1,164 @@
+// Copyright 2018 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package prog
+
+import (
+	"fmt"
+)
+
+// memAlloc keeps track of allocated objects in a program
+// and decides where to allocate new objects.
+// It has 2 main methods: noteAlloc which is called for existing allocations
+// in a program as we analyze it; and alloc which decides where to allocate
+// a new object.
+// The implementation is based on a 2-level bitmap where each bit represents
+// 64 bytes (memAllocGranule) of program memory.
+type memAlloc struct {
+	size uint64
+	mem  [memAllocL1Size]*[memAllocL0Size]uint64
+	buf  [memAllocL0Size]uint64
+}
+
+const (
+	memAllocGranule = 64 // 1 bit per that many bytes (all allocations are rounded to this size)
+	memAllocMaxMem  = 16 << 20
+	memAllocL0Size  = 64
+	bitsPerUint64   = 8 * 8
+	memAllocL0Mem   = memAllocL0Size * memAllocGranule * bitsPerUint64
+	memAllocL1Size  = memAllocMaxMem / memAllocL0Mem
+)
+
+func newMemAlloc(totalMemSize uint64) *memAlloc {
+	if totalMemSize > memAllocMaxMem {
+		panic(fmt.Sprintf("newMemAlloc: too much mem %v (max: %v)", totalMemSize, memAllocMaxMem))
+	}
+	if totalMemSize%memAllocL0Mem != 0 {
+		panic(fmt.Sprintf("newMemAlloc: unaligned size %v (align: %v)", totalMemSize, memAllocL0Mem))
+	}
+	ma := &memAlloc{
+		size: totalMemSize / memAllocGranule,
+	}
+	ma.mem[0] = &ma.buf
+	return ma
+}
+
+func (ma *memAlloc) noteAlloc(addr0, size0 uint64) {
+	addr := addr0 / memAllocGranule
+	size := (addr0+size0+memAllocGranule-1)/memAllocGranule - addr
+	for i := uint64(0); i < size; i++ {
+		ma.set(addr + i)
+	}
+}
+
+func (ma *memAlloc) alloc(r *randGen, size0 uint64) uint64 {
+	if size0 == 0 {
+		size0 = 1
+	}
+	size := (size0 + memAllocGranule - 1) / memAllocGranule
+	end := ma.size - size
+	for start := uint64(0); start < end; start++ {
+		empty := true
+		for i := uint64(0); i < size; i++ {
+			if ma.get(start + i) {
+				empty = false
+				break
+			}
+		}
+		if empty {
+			start0 := start * memAllocGranule
+			ma.noteAlloc(start0, size0)
+			return start0
+		}
+	}
+	ma.bankruptcy()
+	return ma.alloc(r, size0)
+}
+
+func (ma *memAlloc) bankruptcy() {
+	for i1 := uint64(0); i1 < ma.size/(memAllocL0Size*bitsPerUint64); i1++ {
+		if ma.mem[i1] == nil {
+			continue
+		}
+		for i0 := range ma.mem[i1] {
+			ma.mem[i1][i0] = 0
+		}
+	}
+}
+
+func (ma *memAlloc) pos(idx uint64) (i1, i0, bit uint64) {
+	i1 = idx / (memAllocL0Size * bitsPerUint64)
+	r1 := idx % (memAllocL0Size * bitsPerUint64)
+	i0 = r1 / bitsPerUint64
+	bit = 1 << (r1 % bitsPerUint64)
+	return
+}
+
+func (ma *memAlloc) set(idx uint64) {
+	i1, i0, bit := ma.pos(idx)
+	if ma.mem[i1] == nil {
+		ma.mem[i1] = new([memAllocL0Size]uint64)
+	}
+	ma.mem[i1][i0] |= bit
+}
+
+func (ma *memAlloc) get(idx uint64) bool {
+	i1, i0, bit := ma.pos(idx)
+	if ma.mem[i1] == nil {
+		return false
+	}
+	return ma.mem[i1][i0]&bit != 0
+}
+
+type vmaAlloc struct {
+	numPages uint64
+	used     []uint64
+	m        map[uint64]struct{}
+}
+
+func newVmaAlloc(totalPages uint64) *vmaAlloc {
+	return &vmaAlloc{
+		numPages: totalPages,
+		m:        make(map[uint64]struct{}),
+	}
+}
+
+func (va *vmaAlloc) noteAlloc(page, size uint64) {
+	for i := page; i < page+size; i++ {
+		if _, ok := va.m[i]; ok {
+			continue
+		}
+		va.m[i] = struct{}{}
+		va.used = append(va.used, i)
+	}
+}
+
+func (va *vmaAlloc) alloc(r *randGen, size uint64) uint64 {
+	if size > va.numPages {
+		panic(fmt.Sprintf("vmaAlloc: bad size=%v numPages=%v", size, va.numPages))
+	}
+	var page uint64
+	if len(va.used) == 0 || r.oneOf(5) {
+		page = r.rand(4)
+		if !r.oneOf(100) {
+			page = va.numPages - page - size
+		}
+	} else {
+		page = va.used[r.rand(len(va.used))]
+		if size > 1 && r.bin() {
+			off := r.rand(int(size))
+			if off > page {
+				off = page
+			}
+			page -= off
+		}
+		if page+size > va.numPages {
+			page = va.numPages - size
+		}
+	}
+	if page >= va.numPages || size > va.numPages || page+size > va.numPages {
+		panic(fmt.Sprintf("vmaAlloc: bad page=%v size=%v numPages=%v", page, size, va.numPages))
+	}
+	va.noteAlloc(page, size)
+	return page
+}