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.

19 files changed, 447 insertions, 346 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
+}
diff --git a/prog/alloc_test.go b/prog/alloc_test.go
new file mode 100644
index 000000000..261b18d0c
--- /dev/null
+++ b/prog/alloc_test.go
@@ -0,0 +1,72 @@
+// 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"
+	"testing"
+)
+
+func TestMemAlloc(t *testing.T) {
+	t.Parallel()
+	type op struct {
+		addr uint64
+		size int // if positive do noteAlloc, otherwise -- alloc
+	}
+	tests := [][]op{
+		[]op{
+			// Just sequential allocation.
+			{0, -1},
+			{64, -64},
+			{128, -65},
+			{256, -16},
+			{320, -8},
+		},
+		[]op{
+			// First reserve some memory and then allocate.
+			{0, 1},
+			{64, 63},
+			{128, 64},
+			{192, 65},
+			{320, -1},
+			{448, 1},
+			{384, -1},
+			{576, 1},
+			{640, -128},
+		},
+	}
+	for ti, test := range tests {
+		test := test
+		t.Run(fmt.Sprint(ti), func(t *testing.T) {
+			ma := newMemAlloc(16 << 20)
+			for i, op := range test {
+				if op.size > 0 {
+					t.Logf("#%v: noteAlloc(%v, %v)", i, op.addr, op.size)
+					ma.noteAlloc(op.addr, uint64(op.size))
+					continue
+				}
+				t.Logf("#%v: alloc(%v) = %v", i, -op.size, op.addr)
+				addr := ma.alloc(nil, uint64(-op.size))
+				if addr != op.addr {
+					t.Fatalf("bad result %v", addr)
+				}
+			}
+		})
+	}
+}
+
+func TestVmaAlloc(t *testing.T) {
+	t.Parallel()
+	target, err := GetTarget("test", "64")
+	if err != nil {
+		t.Fatal(err)
+	}
+	r := newRand(target, randSource(t))
+	va := newVmaAlloc(1000)
+	for i := 0; i < 30; i++ {
+		size := r.rand(4) + 1
+		page := va.alloc(r, size)
+		t.Logf("alloc(%v) = %3v-%3v\n", size, page, page+size)
+	}
+}
diff --git a/prog/analysis.go b/prog/analysis.go
index ea3a98dd0..c93a13e6c 100644
--- a/prog/analysis.go
+++ b/prog/analysis.go
@@ -12,17 +12,14 @@ import (
 	"fmt"
 )
 
-const (
-	maxPages = 4 << 10
-)
-
 type state struct {
 	target    *Target
 	ct        *ChoiceTable
 	files     map[string]bool
 	resources map[string][]Arg
 	strings   map[string]bool
-	pages     [maxPages]bool
+	ma        *memAlloc
+	va        *vmaAlloc
 }
 
 // analyze analyzes the program p up to but not including call c.
@@ -44,12 +41,24 @@ func newState(target *Target, ct *ChoiceTable) *state {
 		files:     make(map[string]bool),
 		resources: make(map[string][]Arg),
 		strings:   make(map[string]bool),
+		ma:        newMemAlloc(target.NumPages * target.PageSize),
+		va:        newVmaAlloc(target.NumPages),
 	}
 	return s
 }
 
 func (s *state) analyze(c *Call) {
 	ForeachArg(c, func(arg Arg, _ *ArgCtx) {
+		switch a := arg.(type) {
+		case *PointerArg:
+			switch {
+			case a.IsNull():
+			case a.VmaSize != 0:
+				s.va.noteAlloc(a.Address/s.target.PageSize, a.VmaSize/s.target.PageSize)
+			default:
+				s.ma.noteAlloc(a.Address, a.Res.Size())
+			}
+		}
 		switch typ := arg.Type().(type) {
 		case *ResourceType:
 			if typ.Dir() != DirIn {
@@ -68,16 +77,6 @@ func (s *state) analyze(c *Call) {
 			}
 		}
 	})
-	start, npages, mapped := s.target.AnalyzeMmap(c)
-	if npages != 0 {
-		if start+npages > uint64(len(s.pages)) {
-			panic(fmt.Sprintf("address is out of bounds: page=%v len=%v bound=%v",
-				start, npages, len(s.pages)))
-		}
-		for i := uint64(0); i < npages; i++ {
-			s.pages[start+i] = mapped
-		}
-	}
 }
 
 type ArgCtx struct {
diff --git a/prog/encoding.go b/prog/encoding.go
index 0261d4772..daa7eb71d 100644
--- a/prog/encoding.go
+++ b/prog/encoding.go
@@ -46,14 +46,14 @@ func (p *Prog) Serialize() []byte {
 			if i != 0 {
 				fmt.Fprintf(buf, ", ")
 			}
-			serialize(a, buf, vars, &varSeq)
+			p.Target.serialize(a, buf, vars, &varSeq)
 		}
 		fmt.Fprintf(buf, ")\n")
 	}
 	return buf.Bytes()
 }
 
-func serialize(arg Arg, buf *bytes.Buffer, vars map[Arg]int, varSeq *int) {
+func (target *Target) serialize(arg Arg, buf *bytes.Buffer, vars map[Arg]int, varSeq *int) {
 	if arg == nil {
 		fmt.Fprintf(buf, "nil")
 		return
@@ -67,14 +67,14 @@ func serialize(arg Arg, buf *bytes.Buffer, vars map[Arg]int, varSeq *int) {
 	case *ConstArg:
 		fmt.Fprintf(buf, "0x%x", a.Val)
 	case *PointerArg:
-		if a.Res == nil && a.PagesNum == 0 {
+		if a.IsNull() {
 			fmt.Fprintf(buf, "0x0")
 			break
 		}
-		fmt.Fprintf(buf, "&%v", serializeAddr(arg))
-		if a.Res == nil || !isDefaultArg(a.Res) {
+		fmt.Fprintf(buf, "&%v", target.serializeAddr(a))
+		if a.Res == nil || !target.isDefaultArg(a.Res) {
 			fmt.Fprintf(buf, "=")
-			serialize(a.Res, buf, vars, varSeq)
+			target.serialize(a.Res, buf, vars, varSeq)
 		}
 	case *DataArg:
 		if a.Type().Dir() == DirOut {
@@ -104,7 +104,7 @@ func serialize(arg Arg, buf *bytes.Buffer, vars map[Arg]int, varSeq *int) {
 		lastNonDefault := len(a.Inner) - 1
 		if a.fixedInnerSize() {
 			for ; lastNonDefault >= 0; lastNonDefault-- {
-				if !isDefaultArg(a.Inner[lastNonDefault]) {
+				if !target.isDefaultArg(a.Inner[lastNonDefault]) {
 					break
 				}
 			}
@@ -117,14 +117,14 @@ func serialize(arg Arg, buf *bytes.Buffer, vars map[Arg]int, varSeq *int) {
 			if i != 0 {
 				fmt.Fprintf(buf, ", ")
 			}
-			serialize(arg1, buf, vars, varSeq)
+			target.serialize(arg1, buf, vars, varSeq)
 		}
 		buf.Write([]byte{delims[1]})
 	case *UnionArg:
 		fmt.Fprintf(buf, "@%v", a.Option.Type().FieldName())
-		if !isDefaultArg(a.Option) {
+		if !target.isDefaultArg(a.Option) {
 			fmt.Fprintf(buf, "=")
-			serialize(a.Option, buf, vars, varSeq)
+			target.serialize(a.Option, buf, vars, varSeq)
 		}
 	case *ResultArg:
 		if a.Res == nil {
@@ -198,7 +198,7 @@ func (target *Target) Deserialize(data []byte) (prog *Prog, err error) {
 		}
 		if len(c.Args) < len(meta.Args) {
 			for i := len(c.Args); i < len(meta.Args); i++ {
-				c.Args = append(c.Args, defaultArg(meta.Args[i]))
+				c.Args = append(c.Args, target.defaultArg(meta.Args[i]))
 			}
 		}
 		if len(c.Args) != len(meta.Args) {
@@ -241,10 +241,8 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 			arg = MakeConstArg(typ, v)
 		case *ResourceType:
 			arg = MakeResultArg(typ, nil, v)
-		case *PtrType:
-			arg = MakePointerArg(typ, 0, 0, 0, nil)
-		case *VmaType:
-			arg = MakePointerArg(typ, 0, 0, 0, nil)
+		case *PtrType, *VmaType:
+			arg = MakeNullPointerArg(typ)
 		default:
 			return nil, fmt.Errorf("bad const type %+v", typ)
 		}
@@ -288,7 +286,7 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 			return nil, fmt.Errorf("& arg is not a pointer: %#v", typ)
 		}
 		p.Parse('&')
-		page, off, size, err := parseAddr(p, true)
+		addr, vmaSize, err := target.parseAddr(p)
 		if err != nil {
 			return nil, err
 		}
@@ -300,17 +298,13 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 				return nil, err
 			}
 		} else {
-			inner = defaultArg(typ1)
+			inner = target.defaultArg(typ1)
 		}
-		arg = MakePointerArg(typ, page, off, size, inner)
-	case '(':
-		// This used to parse length of VmaType and return ArgPageSize, which is now removed.
-		// Leaving this for now for backwards compatibility.
-		pages, _, _, err := parseAddr(p, false)
-		if err != nil {
-			return nil, err
+		if typ1 != nil {
+			arg = MakePointerArg(typ, addr, inner)
+		} else {
+			arg = MakeVmaPointerArg(typ, addr, vmaSize)
 		}
-		arg = MakeConstArg(typ, pages*target.PageSize)
 	case '"', '\'':
 		data, err := deserializeData(p)
 		if err != nil {
@@ -366,7 +360,7 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 		}
 		p.Parse('}')
 		for len(inner) < len(t1.Fields) {
-			inner = append(inner, defaultArg(t1.Fields[len(inner)]))
+			inner = append(inner, target.defaultArg(t1.Fields[len(inner)]))
 		}
 		arg = MakeGroupArg(typ, inner)
 	case '[':
@@ -389,7 +383,7 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 		p.Parse(']')
 		if t1.Kind == ArrayRangeLen && t1.RangeBegin == t1.RangeEnd {
 			for uint64(len(inner)) < t1.RangeBegin {
-				inner = append(inner, defaultArg(t1.Type))
+				inner = append(inner, target.defaultArg(t1.Type))
 			}
 			inner = inner[:t1.RangeBegin]
 		}
@@ -420,7 +414,7 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 				return nil, err
 			}
 		} else {
-			opt = defaultArg(optType)
+			opt = target.defaultArg(optType)
 		}
 		arg = MakeUnionArg(typ, opt)
 	case 'n':
@@ -441,58 +435,29 @@ func (target *Target) parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, e
 
 const (
 	encodingAddrBase = 0x7f0000000000
-	encodingPageSize = 4 << 10
 	maxLineLen       = 256 << 10
 )
 
-func serializeAddr(arg Arg) string {
-	var pageIndex, pagesNum uint64
-	var pageOffset int
-	switch a := arg.(type) {
-	case *PointerArg:
-		pageIndex = a.PageIndex
-		pageOffset = a.PageOffset
-		pagesNum = a.PagesNum
-	default:
-		panic("bad addr arg")
-	}
-	page := pageIndex * encodingPageSize
-	page += encodingAddrBase
-	soff := ""
-	if off := pageOffset; off != 0 {
-		sign := "+"
-		if off < 0 {
-			sign = "-"
-			off = -off
-			page += encodingPageSize
-		}
-		soff = fmt.Sprintf("%v0x%x", sign, off)
-	}
+func (target *Target) serializeAddr(arg *PointerArg) string {
 	ssize := ""
-	if size := pagesNum; size != 0 {
-		size *= encodingPageSize
-		ssize = fmt.Sprintf("/0x%x", size)
+	if arg.VmaSize != 0 {
+		ssize = fmt.Sprintf("/0x%x", arg.VmaSize)
 	}
-	return fmt.Sprintf("(0x%x%v%v)", page, soff, ssize)
+	return fmt.Sprintf("(0x%x%v)", encodingAddrBase+arg.Address, ssize)
 }
 
-func parseAddr(p *parser, base bool) (uint64, int, uint64, error) {
+func (target *Target) parseAddr(p *parser) (uint64, uint64, error) {
 	p.Parse('(')
 	pstr := p.Ident()
-	page, err := strconv.ParseUint(pstr, 0, 64)
+	addr, err := strconv.ParseUint(pstr, 0, 64)
 	if err != nil {
-		return 0, 0, 0, fmt.Errorf("failed to parse addr page: '%v'", pstr)
-	}
-	if page%encodingPageSize != 0 {
-		return 0, 0, 0, fmt.Errorf("address base is not page size aligned: '%v'", pstr)
+		return 0, 0, fmt.Errorf("failed to parse addr: %q", pstr)
 	}
-	if base {
-		if page < encodingAddrBase {
-			return 0, 0, 0, fmt.Errorf("address without base offset: '%v'", pstr)
-		}
-		page -= encodingAddrBase
+	if addr < encodingAddrBase {
+		return 0, 0, fmt.Errorf("address without base offset: %q", pstr)
 	}
-	var off int64
+	addr -= encodingAddrBase
+	// This is not used anymore, but left here to parse old programs.
 	if p.Char() == '+' || p.Char() == '-' {
 		minus := false
 		if p.Char() == '-' {
@@ -502,28 +467,38 @@ func parseAddr(p *parser, base bool) (uint64, int, uint64, error) {
 			p.Parse('+')
 		}
 		ostr := p.Ident()
-		off, err = strconv.ParseInt(ostr, 0, 64)
+		off, err := strconv.ParseUint(ostr, 0, 64)
 		if err != nil {
-			return 0, 0, 0, fmt.Errorf("failed to parse addr offset: '%v'", ostr)
+			return 0, 0, fmt.Errorf("failed to parse addr offset: %q", ostr)
 		}
 		if minus {
-			page -= encodingPageSize
 			off = -off
 		}
+		addr += off
 	}
-	var size uint64
+	maxMem := target.NumPages * target.PageSize
+	var vmaSize uint64
 	if p.Char() == '/' {
 		p.Parse('/')
 		pstr := p.Ident()
-		size, err = strconv.ParseUint(pstr, 0, 64)
+		size, err := strconv.ParseUint(pstr, 0, 64)
 		if err != nil {
-			return 0, 0, 0, fmt.Errorf("failed to parse addr size: '%v'", pstr)
+			return 0, 0, fmt.Errorf("failed to parse addr size: %q", pstr)
+		}
+		addr = addr & ^(target.PageSize - 1)
+		vmaSize = (size + target.PageSize - 1) & ^(target.PageSize - 1)
+		if vmaSize == 0 {
+			vmaSize = target.PageSize
+		}
+		if vmaSize > maxMem {
+			vmaSize = maxMem
+		}
+		if addr > maxMem-vmaSize {
+			addr = maxMem - vmaSize
 		}
 	}
 	p.Parse(')')
-	page /= encodingPageSize
-	size /= encodingPageSize
-	return page, int(off), size, nil
+	return addr, vmaSize, nil
 }
 
 func serializeData(buf *bytes.Buffer, data []byte) {
diff --git a/prog/encodingexec.go b/prog/encodingexec.go
index ae885d3b1..27fa63350 100644
--- a/prog/encodingexec.go
+++ b/prog/encodingexec.go
@@ -194,16 +194,10 @@ func (p *Prog) SerializeForExec(buffer []byte) (int, error) {
 }
 
 func (target *Target) PhysicalAddr(arg *PointerArg) uint64 {
-	if arg.Res == nil && arg.PagesNum == 0 {
+	if arg.IsNull() {
 		return 0
 	}
-	addr := arg.PageIndex*target.PageSize + target.DataOffset
-	if arg.PageOffset >= 0 {
-		addr += uint64(arg.PageOffset)
-	} else {
-		addr += target.PageSize - uint64(-arg.PageOffset)
-	}
-	return addr
+	return target.DataOffset + arg.Address
 }
 
 type execContext struct {
diff --git a/prog/export_test.go b/prog/export_test.go
index 10dc6dbe5..e22c903f4 100644
--- a/prog/export_test.go
+++ b/prog/export_test.go
@@ -30,16 +30,19 @@ func initTargetTest(t *testing.T, os, arch string) *Target {
 	return target
 }
 
+func randSource(t *testing.T) rand.Source {
+	seed := int64(time.Now().UnixNano())
+	t.Logf("seed=%v", seed)
+	return rand.NewSource(seed)
+}
+
 func initRandomTargetTest(t *testing.T, os, arch string) (*Target, rand.Source, int) {
 	target := initTargetTest(t, os, arch)
 	iters := 10000
 	if testing.Short() {
 		iters = 100
 	}
-	seed := int64(time.Now().UnixNano())
-	rs := rand.NewSource(seed)
-	t.Logf("seed=%v", seed)
-	return target, rs, iters
+	return target, randSource(t), iters
 }
 
 func initTest(t *testing.T) (*Target, rand.Source, int) {
@@ -53,9 +56,7 @@ func testEachTargetRandom(t *testing.T, fn func(t *testing.T, target *Target, rs
 	}
 	targets := AllTargets()
 	iters /= len(targets)
-	seed := int64(time.Now().UnixNano())
-	rs0 := rand.NewSource(seed)
-	t.Logf("seed=%v", seed)
+	rs0 := randSource(t)
 	for _, target := range targets {
 		target := target
 		rs := rand.NewSource(rs0.Int63())
diff --git a/prog/hints.go b/prog/hints.go
index e6406124b..88cb6b029 100644
--- a/prog/hints.go
+++ b/prog/hints.go
@@ -64,9 +64,6 @@ func (m CompMap) String() string {
 // Mutates the program using the comparison operands stored in compMaps.
 // For each of the mutants executes the exec callback.
 func (p *Prog) MutateWithHints(callIndex int, comps CompMap, exec func(p *Prog)) {
-	if p.Calls[callIndex].Meta == p.Target.MmapSyscall {
-		return
-	}
 	p = p.Clone()
 	c := p.Calls[callIndex]
 	execValidate := func() {
diff --git a/prog/hints_test.go b/prog/hints_test.go
index 9a87d3014..a3fd94c62 100644
--- a/prog/hints_test.go
+++ b/prog/hints_test.go
@@ -421,7 +421,7 @@ func TestHintsData(t *testing.T) {
 			Target: target,
 			Calls: []*Call{{
 				Meta: call,
-				Args: []Arg{MakePointerArg(call.Args[0], 0, 0, 0,
+				Args: []Arg{MakePointerArg(call.Args[0], 0,
 					MakeDataArg(call.Args[0].(*PtrType).Type, input))},
 				Ret: MakeReturnArg(call.Ret),
 			}},
diff --git a/prog/minimization.go b/prog/minimization.go
index 8a77eec03..f74ad0252 100644
--- a/prog/minimization.go
+++ b/prog/minimization.go
@@ -29,44 +29,6 @@ func Minimize(p0 *Prog, callIndex0 int, crash bool, pred0 func(*Prog, int) bool)
 		name0 = p0.Calls[callIndex0].Meta.Name
 	}
 
-	// Try to glue all mmap's together.
-	s := analyze(nil, p0, nil)
-	hi := -1
-	lo := -1
-	for i := 0; i < maxPages; i++ {
-		if s.pages[i] {
-			hi = i
-			if lo == -1 {
-				lo = i
-			}
-		}
-	}
-	if hi != -1 {
-		p := p0.Clone()
-		callIndex := callIndex0
-		// Remove all mmaps.
-		for i := 0; i < len(p.Calls); i++ {
-			c := p.Calls[i]
-			if i != callIndex && c.Meta == p.Target.MmapSyscall {
-				p.removeCall(i)
-				if i < callIndex {
-					callIndex--
-				}
-				i--
-			}
-		}
-		// Prepend uber-mmap.
-		mmap := p0.Target.MakeMmap(uint64(lo), uint64(hi-lo)+1)
-		p.Calls = append([]*Call{mmap}, p.Calls...)
-		if callIndex != -1 {
-			callIndex++
-		}
-		if pred(p, callIndex) {
-			p0 = p
-			callIndex0 = callIndex
-		}
-	}
-
 	// Try to remove all calls except the last one one-by-one.
 	for i := len(p0.Calls) - 1; i >= 0; i-- {
 		if i == callIndex0 {
diff --git a/prog/minimization_test.go b/prog/minimization_test.go
index 641b9a9b9..5979ce7a2 100644
--- a/prog/minimization_test.go
+++ b/prog/minimization_test.go
@@ -99,22 +99,6 @@ func TestMinimize(t *testing.T) {
 				"sched_yield()\n",
 			-1,
 		},
-		// Glue several mmaps together.
-		{
-			"sched_yield()\n" +
-				"mmap(&(0x7f0000010000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" +
-				"mmap(&(0x7f0000011000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" +
-				"getpid()\n" +
-				"mmap(&(0x7f0000015000/0x5000)=nil, 0x2000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n",
-			3,
-			func(p *Prog, callIndex int) bool {
-				return p.String() == "mmap-sched_yield-getpid"
-			},
-			"mmap(&(0x7f0000010000/0x7000)=nil, 0x7000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" +
-				"sched_yield()\n" +
-				"getpid()\n",
-			2,
-		},
 	}
 	target, _, _ := initTest(t)
 	for ti, test := range tests {
diff --git a/prog/mutation.go b/prog/mutation.go
index 5bb839f04..dff40a8ec 100644
--- a/prog/mutation.go
+++ b/prog/mutation.go
@@ -57,11 +57,6 @@ outer:
 				retry = true
 				continue
 			}
-			// Mutating mmap() arguments almost certainly doesn't give us new coverage.
-			if c.Meta == p.Target.MmapSyscall && r.nOutOf(99, 100) {
-				retry = true
-				continue
-			}
 			s := analyze(ct, p, c)
 			updateSizes := true
 			retryArg := false
@@ -200,17 +195,8 @@ func (target *Target) mutateArg(r *randGen, s *state, arg Arg, ctx ArgCtx, updat
 		}
 		// TODO: swap elements of the array
 	case *PtrType:
-		a, ok := arg.(*PointerArg)
-		if !ok {
-			break
-		}
-		// TODO: we don't know size for out args
-		size := uint64(1)
-		if a.Res != nil {
-			size = a.Res.Size()
-		}
-		var newArg Arg
-		newArg, calls = r.addr(s, t, size, a.Res)
+		a := arg.(*PointerArg)
+		newArg := r.allocAddr(s, t, a.Res.Size(), a.Res)
 		replaceArg(arg, newArg)
 	case *StructType:
 		gen := target.SpecialTypes[t.Name()]
@@ -260,12 +246,8 @@ func (target *Target) mutateArg(r *randGen, s *state, arg Arg, ctx ArgCtx, updat
 	// Update base pointer if size has increased.
 	if base := ctx.Base; base != nil {
 		if baseSize < base.Res.Size() {
-			newArg, newCalls := r.addr(s, base.Type(), base.Res.Size(), base.Res)
-			calls = append(calls, newCalls...)
-			a1 := newArg.(*PointerArg)
-			base.PageIndex = a1.PageIndex
-			base.PageOffset = a1.PageOffset
-			base.PagesNum = a1.PagesNum
+			newArg := r.allocAddr(s, base.Type(), base.Res.Size(), base.Res)
+			*base = *newArg
 		}
 	}
 	for _, c := range calls {
@@ -309,6 +291,11 @@ func (ma *mutationArgs) collectArg(arg Arg, ctx *ArgCtx) {
 		if typ.Kind == BufferString && len(typ.Values) == 1 {
 			return // string const
 		}
+	case *PtrType:
+		if arg.(*PointerArg).IsNull() {
+			// TODO: we ought to mutate this, but we don't have code for this yet.
+			return
+		}
 	}
 	typ := arg.Type()
 	if typ == nil || typ.Dir() == DirOut || !typ.Varlen() && typ.Size() == 0 {
diff --git a/prog/mutation_test.go b/prog/mutation_test.go
index 5c5ac232a..2267dd254 100644
--- a/prog/mutation_test.go
+++ b/prog/mutation_test.go
@@ -135,7 +135,6 @@ mutate5(&(0x7f0000001000)="2e2f66696c653100", 0x22c0)
 		{`
 mutate3(&(0x7f0000000000)=[0x1, 0x1], 0x2)
 `, `
-mmap(&(0x7f0000000000/0x1000)=nil, 0x1000)
 mutate3(&(0x7f0000000000)=[0x1, 0x1, 0x1], 0x3)
 `},
 		// Mutate size from it's natural value.
@@ -206,3 +205,22 @@ func BenchmarkMutate(b *testing.B) {
 		}
 	})
 }
+
+func BenchmarkGenerate(b *testing.B) {
+	olddebug := debug
+	debug = false
+	defer func() { debug = olddebug }()
+	target, err := GetTarget("linux", "amd64")
+	if err != nil {
+		b.Fatal(err)
+	}
+	prios := target.CalculatePriorities(nil)
+	ct := target.BuildChoiceTable(prios, nil)
+	const progLen = 30
+	b.RunParallel(func(pb *testing.PB) {
+		rs := rand.NewSource(0)
+		for pb.Next() {
+			target.Generate(rs, progLen, ct)
+		}
+	})
+}
diff --git a/prog/prio.go b/prog/prio.go
index 832234dde..35eb6e9d9 100644
--- a/prog/prio.go
+++ b/prog/prio.go
@@ -140,11 +140,6 @@ func (target *Target) calcDynamicPrio(corpus []*Prog) [][]float32 {
 			for _, c1 := range p.Calls {
 				id0 := c0.Meta.ID
 				id1 := c1.Meta.ID
-				// There are too many mmap's anyway.
-				if id0 == id1 || c0.Meta == target.MmapSyscall ||
-					c1.Meta == target.MmapSyscall {
-					continue
-				}
 				prios[id0][id1] += 1.0
 			}
 		}
diff --git a/prog/prog.go b/prog/prog.go
index 68179541c..dc6121662 100644
--- a/prog/prog.go
+++ b/prog/prog.go
@@ -91,23 +91,38 @@ func (arg *ConstArg) Value() (uint64, uint64, bool) {
 }
 
 // Used for PtrType and VmaType.
-// Even if these are always constant (for reproducibility), we use a separate
-// type because they are represented in an abstract (base+page+offset) form.
 type PointerArg struct {
 	ArgCommon
-	PageIndex  uint64
-	PageOffset int    // offset within a page
-	PagesNum   uint64 // number of available pages
-	Res        Arg    // pointee
+	Address uint64
+	VmaSize uint64 // size of the referenced region for vma args
+	Res     Arg    // pointee (nil for vma)
 }
 
-func MakePointerArg(t Type, page uint64, off int, npages uint64, obj Arg) Arg {
+func MakePointerArg(t Type, addr uint64, data Arg) *PointerArg {
+	if data == nil {
+		panic("nil pointer data arg")
+	}
 	return &PointerArg{
-		ArgCommon:  ArgCommon{typ: t},
-		PageIndex:  page,
-		PageOffset: off,
-		PagesNum:   npages,
-		Res:        obj,
+		ArgCommon: ArgCommon{typ: t},
+		Address:   addr,
+		Res:       data,
+	}
+}
+
+func MakeVmaPointerArg(t Type, addr, size uint64) *PointerArg {
+	if addr%1024 != 0 {
+		panic("unaligned vma address")
+	}
+	return &PointerArg{
+		ArgCommon: ArgCommon{typ: t},
+		Address:   addr,
+		VmaSize:   size,
+	}
+}
+
+func MakeNullPointerArg(t Type) *PointerArg {
+	return &PointerArg{
+		ArgCommon: ArgCommon{typ: t},
 	}
 }
 
@@ -115,6 +130,10 @@ func (arg *PointerArg) Size() uint64 {
 	return arg.typ.Size()
 }
 
+func (arg *PointerArg) IsNull() bool {
+	return arg.Address == 0 && arg.VmaSize == 0 && arg.Res == nil
+}
+
 // Used for BufferType.
 type DataArg struct {
 	ArgCommon
@@ -291,7 +310,7 @@ func InnerArg(arg Arg) Arg {
 	return arg // Not a pointer.
 }
 
-func defaultArg(t Type) Arg {
+func (target *Target) defaultArg(t Type) Arg {
 	switch typ := t.(type) {
 	case *IntType, *ConstType, *FlagsType, *LenType, *ProcType, *CsumType:
 		return MakeConstArg(t, t.Default())
@@ -314,32 +333,31 @@ func defaultArg(t Type) Arg {
 		var elems []Arg
 		if typ.Kind == ArrayRangeLen && typ.RangeBegin == typ.RangeEnd {
 			for i := uint64(0); i < typ.RangeBegin; i++ {
-				elems = append(elems, defaultArg(typ.Type))
+				elems = append(elems, target.defaultArg(typ.Type))
 			}
 		}
 		return MakeGroupArg(t, elems)
 	case *StructType:
 		var inner []Arg
 		for _, field := range typ.Fields {
-			inner = append(inner, defaultArg(field))
+			inner = append(inner, target.defaultArg(field))
 		}
 		return MakeGroupArg(t, inner)
 	case *UnionType:
-		return MakeUnionArg(t, defaultArg(typ.Fields[0]))
+		return MakeUnionArg(t, target.defaultArg(typ.Fields[0]))
 	case *VmaType:
-		return MakePointerArg(t, 0, 0, 1, nil)
+		return MakeVmaPointerArg(t, 0, target.PageSize)
 	case *PtrType:
-		var res Arg
-		if !t.Optional() && t.Dir() != DirOut {
-			res = defaultArg(typ.Type)
+		if t.Optional() {
+			return MakeNullPointerArg(t)
 		}
-		return MakePointerArg(t, 0, 0, 0, res)
+		return MakePointerArg(t, 0, target.defaultArg(typ.Type))
 	default:
 		panic("unknown arg type")
 	}
 }
 
-func isDefaultArg(arg Arg) bool {
+func (target *Target) isDefaultArg(arg Arg) bool {
 	if IsPad(arg.Type()) {
 		return true
 	}
@@ -356,7 +374,7 @@ func isDefaultArg(arg Arg) bool {
 			return false
 		}
 		for _, elem := range a.Inner {
-			if !isDefaultArg(elem) {
+			if !target.isDefaultArg(elem) {
 				return false
 			}
 		}
@@ -364,7 +382,7 @@ func isDefaultArg(arg Arg) bool {
 	case *UnionArg:
 		t := a.Type().(*UnionType)
 		return a.Option.Type().FieldName() == t.Fields[0].Name() &&
-			isDefaultArg(a.Option)
+			target.isDefaultArg(a.Option)
 	case *DataArg:
 		if a.Size() == 0 {
 			return true
@@ -384,11 +402,12 @@ func isDefaultArg(arg Arg) bool {
 	case *PointerArg:
 		switch t := a.Type().(type) {
 		case *PtrType:
-			return a.PageIndex == 0 && a.PageOffset == 0 && a.PagesNum == 0 &&
-				(((t.Optional() || t.Dir() == DirOut) && a.Res == nil) ||
-					(!t.Optional() && t.Dir() != DirOut && a.Res != nil && isDefaultArg(a.Res)))
+			if t.Optional() {
+				return a.IsNull()
+			}
+			return a.Address == 0 && target.isDefaultArg(a.Res)
 		case *VmaType:
-			return a.PageIndex == 0 && a.PageOffset == 0 && a.PagesNum == 1 && a.Res == nil
+			return a.Address == 0 && a.VmaSize == target.PageSize
 		default:
 			panic("unknown pointer type")
 		}
diff --git a/prog/prog_test.go b/prog/prog_test.go
index 146694f45..1dc310456 100644
--- a/prog/prog_test.go
+++ b/prog/prog_test.go
@@ -25,7 +25,7 @@ func TestDefault(t *testing.T) {
 	target, _, _ := initTest(t)
 	for _, meta := range target.SyscallMap {
 		for _, t := range meta.Args {
-			defaultArg(t)
+			target.defaultArg(t)
 		}
 	}
 }
@@ -91,16 +91,18 @@ func TestVmaType(t *testing.T) {
 			if !ok {
 				t.Fatalf("len has bad type: %v", l)
 			}
-			if va.PagesNum < min || va.PagesNum > max {
-				t.Fatalf("vma has bad number of pages: %v, want [%v-%v]", va.PagesNum, min, max)
+			if va.VmaSize < min || va.VmaSize > max {
+				t.Fatalf("vma has bad size: %v, want [%v-%v]",
+					va.VmaSize, min, max)
 			}
-			if la.Val/pageSize < min || la.Val/pageSize > max {
-				t.Fatalf("len has bad number of pages: %v, want [%v-%v]", la.Val/pageSize, min, max)
+			if la.Val < min || la.Val > max {
+				t.Fatalf("len has bad value: %v, want [%v-%v]",
+					la.Val, min, max)
 			}
 		}
-		check(c.Args[0], c.Args[1], 1, 1e5)
-		check(c.Args[2], c.Args[3], 5, 5)
-		check(c.Args[4], c.Args[5], 7, 9)
+		check(c.Args[0], c.Args[1], 1*pageSize, 1e5*pageSize)
+		check(c.Args[2], c.Args[3], 5*pageSize, 5*pageSize)
+		check(c.Args[4], c.Args[5], 7*pageSize, 9*pageSize)
 	}
 }
 
diff --git a/prog/rand.go b/prog/rand.go
index 5afd00c9d..b9aa77a8a 100644
--- a/prog/rand.go
+++ b/prog/rand.go
@@ -9,13 +9,10 @@ import (
 	"math"
 	"math/rand"
 	"strings"
-	"sync"
 
 	"github.com/google/syzkaller/pkg/ifuzz"
 )
 
-var pageStartPool = sync.Pool{New: func() interface{} { return new([]uint64) }}
-
 type randGen struct {
 	*rand.Rand
 	target           *Target
@@ -132,7 +129,7 @@ func (r *randGen) randPageCount() (n uint64) {
 	case r.nOutOf(5, 6):
 		n = r.rand(20) + 1
 	default:
-		n = (r.rand(3) + 1) * 1024
+		n = (r.rand(3) + 1) * 512
 	}
 	return
 }
@@ -217,82 +214,13 @@ func (r *randGen) randString(s *state, t *BufferType) []byte {
 	return buf.Bytes()
 }
 
-func (r *randGen) addr1(s *state, typ Type, size uint64, data Arg) (Arg, []*Call) {
-	npages := (size + r.target.PageSize - 1) / r.target.PageSize
-	if npages == 0 {
-		npages = 1
-	}
-	if r.bin() {
-		return r.randPageAddr(s, typ, npages, data, false), nil
-	}
-	for i := uint64(0); i < maxPages-npages; i++ {
-		free := true
-		for j := uint64(0); j < npages; j++ {
-			if s.pages[i+j] {
-				free = false
-				break
-			}
-		}
-		if !free {
-			continue
-		}
-		c := r.target.MakeMmap(i, npages)
-		return MakePointerArg(typ, i, 0, 0, data), []*Call{c}
-	}
-	return r.randPageAddr(s, typ, npages, data, false), nil
+func (r *randGen) allocAddr(s *state, typ Type, size uint64, data Arg) *PointerArg {
+	return MakePointerArg(typ, s.ma.alloc(r, size), data)
 }
 
-func (r *randGen) addr(s *state, typ Type, size uint64, data Arg) (Arg, []*Call) {
-	arg, calls := r.addr1(s, typ, size, data)
-	a, ok := arg.(*PointerArg)
-	if !ok {
-		panic("bad")
-	}
-	// Patch offset of the address.
-	switch {
-	case r.nOutOf(50, 102):
-	case r.nOutOf(50, 52):
-		a.PageOffset = -int(size)
-	case r.nOutOf(1, 2):
-		a.PageOffset = r.Intn(int(r.target.PageSize))
-	default:
-		if size > 0 {
-			a.PageOffset = -r.Intn(int(size))
-		}
-	}
-	return arg, calls
-}
-
-func (r *randGen) randPageAddr(s *state, typ Type, npages uint64, data Arg, vma bool) Arg {
-	poolPtr := pageStartPool.Get().(*[]uint64)
-	starts := (*poolPtr)[:0]
-	for i := uint64(0); i < maxPages-npages; i++ {
-		busy := true
-		for j := uint64(0); j < npages; j++ {
-			if !s.pages[i+j] {
-				busy = false
-				break
-			}
-		}
-		// TODO: it does not need to be completely busy,
-		// for example, mmap addr arg can be new memory.
-		if !busy {
-			continue
-		}
-		starts = append(starts, i)
-	}
-	var page uint64
-	if len(starts) != 0 {
-		page = starts[r.rand(len(starts))]
-	} else {
-		page = r.rand(int(maxPages - npages))
-	}
-	if !vma {
-		npages = 0
-	}
-	*poolPtr = starts
-	pageStartPool.Put(poolPtr)
-	return MakePointerArg(typ, page, 0, npages, data)
+func (r *randGen) allocVMA(s *state, typ Type, numPages uint64) *PointerArg {
+	page := s.va.alloc(r, numPages)
+	return MakeVmaPointerArg(typ, page*r.target.PageSize, numPages*r.target.PageSize)
 }
 
 func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls []*Call) {
@@ -348,6 +276,9 @@ func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls []
 			return arg, calls
 		}
 		// Discard unsuccessful calls.
+		// Note: s.ma/va have already noted allocations of the new objects
+		// in discarded syscalls, ideally we should recreate state
+		// by analyzing the program again.
 		for _, c := range calls {
 			ForeachArg(c, func(arg Arg, _ *ArgCtx) {
 				if a, ok := arg.(*ResultArg); ok && a.Res != nil {
@@ -429,22 +360,14 @@ func (r *randGen) nOutOf(n, outOf int) bool {
 }
 
 func (r *randGen) generateCall(s *state, p *Prog) []*Call {
-	call := -1
-	if len(p.Calls) != 0 {
-		for i := 0; i < 5; i++ {
-			c := p.Calls[r.Intn(len(p.Calls))].Meta
-			call = c.ID
-			// There is roughly half of mmap's so ignore them.
-			if c != r.target.MmapSyscall {
-				break
-			}
-		}
-	}
-
 	idx := 0
 	if s.ct == nil {
 		idx = r.Intn(len(r.target.Syscalls))
 	} else {
+		call := -1
+		if len(p.Calls) != 0 {
+			call = p.Calls[r.Intn(len(p.Calls))].Meta.ID
+		}
 		idx = s.ct.Choose(r.Rand, call)
 	}
 	meta := r.target.Syscalls[idx]
@@ -495,7 +418,14 @@ func (target *Target) GenerateAllSyzProg(rs rand.Source) *Prog {
 func (target *Target) GenerateSimpleProg() *Prog {
 	return &Prog{
 		Target: target,
-		Calls:  []*Call{target.MakeMmap(0, 1)},
+		Calls:  []*Call{target.MakeMmap(0, target.PageSize)},
+	}
+}
+
+func (target *Target) GenerateUberMmapProg() *Prog {
+	return &Prog{
+		Target: target,
+		Calls:  []*Call{target.MakeMmap(0, target.NumPages*target.PageSize)},
 	}
 }
 
@@ -529,12 +459,12 @@ func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg A
 		switch typ.(type) {
 		case *IntType, *FlagsType, *ConstType, *ProcType,
 			*VmaType, *ResourceType:
-			return defaultArg(typ), nil
+			return r.target.defaultArg(typ), nil
 		}
 	}
 
 	if typ.Optional() && r.oneOf(5) {
-		return defaultArg(typ), nil
+		return r.target.defaultArg(typ), nil
 	}
 
 	// Allow infinite recursion for optional pointers.
@@ -548,7 +478,7 @@ func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg A
 				}
 			}()
 			if r.recDepth[str.Name()] >= 3 {
-				return MakePointerArg(typ, 0, 0, 0, nil), nil
+				return MakeNullPointerArg(typ), nil
 			}
 		}
 	}
@@ -629,7 +559,7 @@ func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg A
 		if a.RangeBegin != 0 || a.RangeEnd != 0 {
 			npages = a.RangeBegin + uint64(r.Intn(int(a.RangeEnd-a.RangeBegin+1)))
 		}
-		arg := r.randPageAddr(s, a, npages, nil, true)
+		arg := r.allocVMA(s, a, npages)
 		return arg, nil
 	case *FlagsType:
 		return MakeConstArg(a, r.flags(a.Vals)), nil
@@ -697,11 +627,10 @@ func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg A
 			// So try to reuse a previously used address.
 			addrs := s.resources["iocbptr"]
 			addr := addrs[r.Intn(len(addrs))].(*PointerArg)
-			arg = MakePointerArg(a, addr.PageIndex, addr.PageOffset, addr.PagesNum, inner)
+			arg = MakePointerArg(a, addr.Address, inner)
 			return arg, calls
 		}
-		arg, calls1 := r.addr(s, a, inner.Size(), inner)
-		calls = append(calls, calls1...)
+		arg := r.allocAddr(s, a, inner.Size(), inner)
 		return arg, calls
 	case *LenType:
 		// Return placeholder value of 0 while generating len arg.
diff --git a/prog/size.go b/prog/size.go
index 9f2258c82..ab8d97717 100644
--- a/prog/size.go
+++ b/prog/size.go
@@ -21,7 +21,7 @@ func (target *Target) generateSize(arg Arg, lenType *LenType) uint64 {
 	switch arg.Type().(type) {
 	case *VmaType:
 		a := arg.(*PointerArg)
-		return a.PagesNum * target.PageSize * 8 / bitSize
+		return a.VmaSize * 8 / bitSize
 	case *ArrayType:
 		a := arg.(*GroupArg)
 		if lenType.BitSize != 0 {
diff --git a/prog/target.go b/prog/target.go
index 946839159..2b044977c 100644
--- a/prog/target.go
+++ b/prog/target.go
@@ -17,6 +17,7 @@ type Target struct {
 	Revision   string // unique hash representing revision of the descriptions
 	PtrSize    uint64
 	PageSize   uint64
+	NumPages   uint64
 	DataOffset uint64
 
 	Syscalls  []*Syscall
@@ -24,17 +25,8 @@ type Target struct {
 	Structs   []*KeyedStruct
 	Consts    []ConstValue
 
-	// Syscall used by MakeMmap.
-	// It has some special meaning because there are usually too many of them.
-	MmapSyscall *Syscall
-
-	// MakeMmap creates call that maps [start, start+npages) page range.
-	MakeMmap func(start, npages uint64) *Call
-
-	// AnalyzeMmap analyzes the call c regarding mapping/unmapping memory.
-	// If it maps/unmaps any memory returns [start, start+npages) range,
-	// otherwise returns npages = 0.
-	AnalyzeMmap func(c *Call) (start, npages uint64, mapped bool)
+	// MakeMmap creates call that maps [addr, addr+size) memory range.
+	MakeMmap func(addr, size uint64) *Call
 
 	// SanitizeCall neutralizes harmful calls.
 	SanitizeCall func(c *Call)
@@ -175,7 +167,7 @@ func (g *Gen) NOutOf(n, outOf int) bool {
 }
 
 func (g *Gen) Alloc(ptrType Type, data Arg) (Arg, []*Call) {
-	return g.r.addr(g.s, ptrType, data.Size(), data)
+	return g.r.allocAddr(g.s, ptrType, data.Size(), data), nil
 }
 
 func (g *Gen) GenerateArg(typ Type, pcalls *[]*Call) Arg {
diff --git a/prog/validation.go b/prog/validation.go
index 400b13140..8f01d6df5 100644
--- a/prog/validation.go
+++ b/prog/validation.go
@@ -17,7 +17,7 @@ type validCtx struct {
 func (p *Prog) validate() error {
 	ctx := &validCtx{make(map[Arg]bool), make(map[Arg]Arg)}
 	for _, c := range p.Calls {
-		if err := c.validate(ctx); err != nil {
+		if err := p.validateCall(ctx, c); err != nil {
 			return err
 		}
 	}
@@ -29,7 +29,7 @@ func (p *Prog) validate() error {
 	return nil
 }
 
-func (c *Call) validate(ctx *validCtx) error {
+func (p *Prog) validateCall(ctx *validCtx, c *Call) error {
 	if c.Meta == nil {
 		return fmt.Errorf("call does not have meta information")
 	}
@@ -157,13 +157,23 @@ func (c *Call) validate(ctx *validCtx) error {
 		switch a := arg.(type) {
 		case *ConstArg:
 		case *PointerArg:
+			maxMem := p.Target.NumPages * p.Target.PageSize
+			size := a.VmaSize
+			if size == 0 && a.Res != nil {
+				size = a.Res.Size()
+			}
+			if a.Address >= maxMem || a.Address+size > maxMem {
+				return fmt.Errorf("syscall %v: ptr %v has bad address %v/%v/%v",
+					c.Meta.Name, a.Type().Name(), a.Address, a.VmaSize, size)
+			}
 			switch t := a.Type().(type) {
 			case *VmaType:
 				if a.Res != nil {
 					return fmt.Errorf("syscall %v: vma arg '%v' has data", c.Meta.Name, a.Type().Name())
 				}
-				if a.PagesNum == 0 && t.Dir() != DirOut && !t.Optional() {
-					return fmt.Errorf("syscall %v: vma arg '%v' has size 0", c.Meta.Name, a.Type().Name())
+				if a.VmaSize == 0 && t.Dir() != DirOut && !t.Optional() {
+					return fmt.Errorf("syscall %v: vma arg '%v' has size 0",
+						c.Meta.Name, a.Type().Name())
 				}
 			case *PtrType:
 				if a.Res != nil {
@@ -171,8 +181,9 @@ func (c *Call) validate(ctx *validCtx) error {
 						return err
 					}
 				}
-				if a.PagesNum != 0 {
-					return fmt.Errorf("syscall %v: pointer arg '%v' has nonzero size", c.Meta.Name, a.Type().Name())
+				if a.VmaSize != 0 {
+					return fmt.Errorf("syscall %v: pointer arg '%v' has nonzero size",
+						c.Meta.Name, a.Type().Name())
 				}
 			default:
 				return fmt.Errorf("syscall %v: pointer arg '%v' has bad meta type %+v", c.Meta.Name, arg.Type().Name(), arg.Type())