prog: add concept of "special pointers"

Currently we only generate either valid user-space pointers or NULL.
Extend NULL to a set of special pointers that we will use in programs.
All targets now contain 3 special values:
 - NULL
 - 0xfffffffffffffff (invalid kernel pointer)
 - 0x999999999999999 (non-canonical address)
Each target can add additional special pointers on top of this.

Also generate NULL/special pointers for non-opt ptr's.
This restriction was always too restrictive. We may want to generate
them with very low probability, but we do want to generate them.

Also change pointers to NULL/special during mutation
(but still not in the opposite direction).

13 files changed, 161 insertions, 67 deletions

diff --git a/prog/analysis.go b/prog/analysis.go
index 3ebfbda61..c26e14014 100644
--- a/prog/analysis.go
+++ b/prog/analysis.go
@@ -57,7 +57,7 @@ func (s *state) analyzeImpl(c *Call, resources bool) {
 		switch a := arg.(type) {
 		case *PointerArg:
 			switch {
-			case a.IsNull():
+			case a.IsSpecial():
 			case a.VmaSize != 0:
 				s.va.noteAlloc(a.Address/s.target.PageSize, a.VmaSize/s.target.PageSize)
 			default:
@@ -273,7 +273,7 @@ func extractArgSignal(arg Arg, callID, flags int, inf *CallInfo, resources map[*
 		}
 	case *PointerArg:
 		flags <<= 1
-		if a.IsNull() {
+		if a.IsSpecial() {
 			flags |= 1
 		}
 	}
diff --git a/prog/encoding.go b/prog/encoding.go
index 92e2c47f0..c968fa0b7 100644
--- a/prog/encoding.go
+++ b/prog/encoding.go
@@ -85,8 +85,8 @@ func (a *ConstArg) serialize(ctx *serializer) {
 }
 
 func (a *PointerArg) serialize(ctx *serializer) {
-	if a.IsNull() {
-		ctx.printf("0x0")
+	if a.IsSpecial() {
+		ctx.printf("0x%x", a.Address)
 		return
 	}
 	target := ctx.target
@@ -345,10 +345,8 @@ func (target *Target) parseArgInt(typ Type, p *parser) (Arg, error) {
 	case *ResourceType:
 		return MakeResultArg(typ, nil, v), nil
 	case *PtrType, *VmaType:
-		if typ.Optional() {
-			return MakeNullPointerArg(typ), nil
-		}
-		return typ.makeDefaultArg(), nil
+		index := -v % uint64(len(target.SpecialPointers))
+		return MakeSpecialPointerArg(typ, index), nil
 	default:
 		eatExcessive(p, true)
 		return typ.makeDefaultArg(), nil
diff --git a/prog/encoding_test.go b/prog/encoding_test.go
index 0b3364e63..1bb22228f 100644
--- a/prog/encoding_test.go
+++ b/prog/encoding_test.go
@@ -12,6 +12,8 @@ import (
 	"sort"
 	"strings"
 	"testing"
+
+	"github.com/google/go-cmp/cmp"
 )
 
 func setToArray(s map[string]struct{}) []string {
@@ -160,7 +162,7 @@ func TestDeserialize(t *testing.T) {
 		},
 		{
 			input:  `test$excessive_fields1(0x0)`,
-			output: `test$excessive_fields1(&(0x7f0000000000))`,
+			output: `test$excessive_fields1(0x0)`,
 		},
 		{
 			input:  `test$excessive_fields1(r0)`,
@@ -206,6 +208,26 @@ func TestDeserialize(t *testing.T) {
 			input:  `test$excessive_fields1(&(0x7f0000000000)=0x0)`,
 			output: `test$excessive_fields1(&(0x7f0000000000))`,
 		},
+		{
+			input:  `test$excessive_fields1(0x0)`,
+			output: `test$excessive_fields1(0x0)`,
+		},
+		{
+			input:  `test$excessive_fields1(0xffffffffffffffff)`,
+			output: `test$excessive_fields1(0xffffffffffffffff)`,
+		},
+		{
+			input:  `test$excessive_fields1(0xfffffffffffffffe)`,
+			output: `test$excessive_fields1(0xfffffffffffffffe)`,
+		},
+		{
+			input:  `test$excessive_fields1(0xfffffffffffffffd)`,
+			output: `test$excessive_fields1(0x0)`,
+		},
+		{
+			input:  `test$excessive_fields1(0xfffffffffffffffc)`,
+			output: `test$excessive_fields1(0xffffffffffffffff)`,
+		},
 	}
 	buf := make([]byte, ExecBufferSize)
 	for _, test := range tests {
@@ -276,8 +298,18 @@ func TestSerializeDeserializeRandom(t *testing.T) {
 			})
 			ok, n0, n1 := testSerializeDeserialize(t, p0, data0, data1)
 			if ok {
-				t.Fatal("flaky?")
+				t.Log("flaky?")
+			}
+			decoded0, err := target.DeserializeExec(data0[:n0])
+			if err != nil {
+				t.Fatal(err)
+			}
+			decoded1, err := target.DeserializeExec(data1[:n1])
+			if err != nil {
+				t.Fatal(err)
 			}
+			diff := cmp.Diff(decoded0, decoded1)
+			t.Logf("decoded diff: %v", diff)
 			t.Fatalf("was: %q\ngot: %q\nprogram:\n%s",
 				data0[:n0], data1[:n1], p0.Serialize())
 		}
diff --git a/prog/encodingexec.go b/prog/encodingexec.go
index 659f4be3f..651ecef51 100644
--- a/prog/encodingexec.go
+++ b/prog/encodingexec.go
@@ -100,13 +100,6 @@ func (w *execContext) serializeCall(c *Call) {
 	w.writeCopyout(c)
 }
 
-func (target *Target) PhysicalAddr(arg *PointerArg) uint64 {
-	if arg.IsNull() {
-		return 0
-	}
-	return target.DataOffset + arg.Address
-}
-
 type execContext struct {
 	target     *Target
 	buf        []byte
diff --git a/prog/encodingexec_test.go b/prog/encodingexec_test.go
index 94064c317..5a0e35750 100644
--- a/prog/encodingexec_test.go
+++ b/prog/encodingexec_test.go
@@ -403,6 +403,30 @@ func TestSerializeForExec(t *testing.T) {
 			},
 			nil,
 		},
+		{
+			"test$excessive_fields1(0x0)",
+			[]uint64{
+				callID("test$excessive_fields1"), ExecNoCopyout, 1, execArgConst, ptrSize, 0x0,
+				execInstrEOF,
+			},
+			nil,
+		},
+		{
+			"test$excessive_fields1(0xffffffffffffffff)",
+			[]uint64{
+				callID("test$excessive_fields1"), ExecNoCopyout, 1, execArgConst, ptrSize, 0xffffffffffffffff,
+				execInstrEOF,
+			},
+			nil,
+		},
+		{
+			"test$excessive_fields1(0xfffffffffffffffe)",
+			[]uint64{
+				callID("test$excessive_fields1"), ExecNoCopyout, 1, execArgConst, ptrSize, 0x9999999999999999,
+				execInstrEOF,
+			},
+			nil,
+		},
 	}
 
 	buf := make([]byte, ExecBufferSize)
diff --git a/prog/mutation.go b/prog/mutation.go
index ee25fb14a..86cf487aa 100644
--- a/prog/mutation.go
+++ b/prog/mutation.go
@@ -308,6 +308,13 @@ func (t *ArrayType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*
 
 func (t *PtrType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) {
 	a := arg.(*PointerArg)
+	if r.oneOf(1000) {
+		removeArg(a.Res)
+		index := r.rand(len(r.target.SpecialPointers))
+		newArg := MakeSpecialPointerArg(t, index)
+		replaceArg(arg, newArg)
+		return
+	}
 	newArg := r.allocAddr(s, t, a.Res.Size(), a.Res)
 	replaceArg(arg, newArg)
 	return
@@ -401,7 +408,7 @@ func (ma *mutationArgs) collectArg(arg Arg, ctx *ArgCtx) {
 			return // string const
 		}
 	case *PtrType:
-		if arg.(*PointerArg).IsNull() {
+		if arg.(*PointerArg).IsSpecial() {
 			// TODO: we ought to mutate this, but we don't have code for this yet.
 			return
 		}
diff --git a/prog/prog.go b/prog/prog.go
index 8d0e0f525..b7304ba5d 100644
--- a/prog/prog.go
+++ b/prog/prog.go
@@ -106,9 +106,13 @@ func MakeVmaPointerArg(t Type, addr, size uint64) *PointerArg {
 	}
 }
 
-func MakeNullPointerArg(t Type) *PointerArg {
+func MakeSpecialPointerArg(t Type, index uint64) *PointerArg {
+	if index >= maxSpecialPointers {
+		panic("bad special pointer index")
+	}
 	return &PointerArg{
 		ArgCommon: ArgCommon{typ: t},
+		Address:   -index,
 	}
 }
 
@@ -116,8 +120,15 @@ func (arg *PointerArg) Size() uint64 {
 	return arg.typ.Size()
 }
 
-func (arg *PointerArg) IsNull() bool {
-	return arg.Address == 0 && arg.VmaSize == 0 && arg.Res == nil
+func (arg *PointerArg) IsSpecial() bool {
+	return arg.VmaSize == 0 && arg.Res == nil && -arg.Address < maxSpecialPointers
+}
+
+func (target *Target) PhysicalAddr(arg *PointerArg) uint64 {
+	if arg.IsSpecial() {
+		return target.SpecialPointers[-arg.Address]
+	}
+	return target.DataOffset + arg.Address
 }
 
 // Used for BufferType.
@@ -262,17 +273,12 @@ func (arg *ResultArg) Size() uint64 {
 
 // Returns inner arg for pointer args.
 func InnerArg(arg Arg) Arg {
-	if t, ok := arg.Type().(*PtrType); ok {
-		if a, ok := arg.(*PointerArg); ok {
-			if a.Res == nil {
-				if !t.Optional() {
-					panic(fmt.Sprintf("non-optional pointer is nil\narg: %+v\ntype: %+v", a, t))
-				}
-				return nil
-			}
-			return InnerArg(a.Res)
+	if _, ok := arg.Type().(*PtrType); ok {
+		res := arg.(*PointerArg).Res
+		if res == nil {
+			return nil
 		}
-		return nil // *ConstArg.
+		return InnerArg(res)
 	}
 	return arg // Not a pointer.
 }
diff --git a/prog/rand.go b/prog/rand.go
index 7bded23c6..7f5597f82 100644
--- a/prog/rand.go
+++ b/prog/rand.go
@@ -515,7 +515,7 @@ func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg A
 				}
 			}()
 			if r.recDepth[name] >= 3 {
-				return MakeNullPointerArg(typ), nil
+				return MakeSpecialPointerArg(typ, 0), nil
 			}
 		}
 	}
@@ -673,6 +673,10 @@ func (a *UnionType) generate(r *randGen, s *state) (arg Arg, calls []*Call) {
 }
 
 func (a *PtrType) generate(r *randGen, s *state) (arg Arg, calls []*Call) {
+	if r.oneOf(1000) {
+		index := r.rand(len(r.target.SpecialPointers))
+		return MakeSpecialPointerArg(a, index), nil
+	}
 	inner, calls := r.generateArg(s, a.Type)
 	arg = r.allocAddr(s, a, inner.Size(), inner)
 	return arg, calls
diff --git a/prog/target.go b/prog/target.go
index 80a2665ae..631b756e8 100644
--- a/prog/target.go
+++ b/prog/target.go
@@ -44,6 +44,9 @@ type Target struct {
 	// Used as fallback when string type does not have own dictionary.
 	StringDictionary []string
 
+	// Additional special invalid pointer values besides NULL to use.
+	SpecialPointers []uint64
+
 	// Filled by prog package:
 	init        sync.Once
 	initArch    func(target *Target)
@@ -55,6 +58,8 @@ type Target struct {
 	any           anyTypes
 }
 
+const maxSpecialPointers = 16
+
 var targets = make(map[string]*Target)
 
 func RegisterTarget(target *Target, initArch func(target *Target)) {
@@ -101,6 +106,15 @@ func (target *Target) lazyInit() {
 	target.initTarget()
 	target.initArch(target)
 	target.ConstMap = nil // currently used only by initArch
+	// Give these 2 known addresses fixed positions and prepend target-specific ones at the end.
+	target.SpecialPointers = append([]uint64{
+		0x0000000000000000, // NULL pointer (keep this first because code uses special index=0 as NULL)
+		0xffffffffffffffff, // unmapped kernel address (keep second because serialized value will match actual pointer value)
+		0x9999999999999999, // non-canonical address
+	}, target.SpecialPointers...)
+	if len(target.SpecialPointers) > maxSpecialPointers {
+		panic("too many special pointers")
+	}
 }
 
 func (target *Target) initTarget() {
diff --git a/prog/types.go b/prog/types.go
index 68c80e23c..3bb2fdbb4 100644
--- a/prog/types.go
+++ b/prog/types.go
@@ -321,11 +321,12 @@ func (t *VmaType) String() string {
 }
 
 func (t *VmaType) makeDefaultArg() Arg {
-	return MakeNullPointerArg(t)
+	return MakeSpecialPointerArg(t, 0)
 }
 
 func (t *VmaType) isDefaultArg(arg Arg) bool {
-	return arg.(*PointerArg).IsNull()
+	a := arg.(*PointerArg)
+	return a.IsSpecial() && a.Address == 0
 }
 
 type BufferKind int
@@ -450,7 +451,7 @@ func (t *PtrType) String() string {
 
 func (t *PtrType) makeDefaultArg() Arg {
 	if t.Optional() {
-		return MakeNullPointerArg(t)
+		return MakeSpecialPointerArg(t, 0)
 	}
 	return MakePointerArg(t, 0, t.Type.makeDefaultArg())
 }
@@ -458,9 +459,9 @@ func (t *PtrType) makeDefaultArg() Arg {
 func (t *PtrType) isDefaultArg(arg Arg) bool {
 	a := arg.(*PointerArg)
 	if t.Optional() {
-		return a.IsNull()
+		return a.IsSpecial() && a.Address == 0
 	}
-	return a.Address == 0 && isDefault(a.Res)
+	return a.Address == 0 && a.Res != nil && isDefault(a.Res)
 }
 
 type StructType struct {
diff --git a/prog/validation.go b/prog/validation.go
index eaffac9b8..632f84509 100644
--- a/prog/validation.go
+++ b/prog/validation.go
@@ -241,9 +241,6 @@ func (arg *PointerArg) validate(ctx *validCtx) error {
 			return fmt.Errorf("vma arg '%v' has data", typ.Name())
 		}
 	case *PtrType:
-		if arg.Res == nil && !arg.Type().Optional() {
-			return fmt.Errorf("non optional pointer arg '%v' is nil", typ.Name())
-		}
 		if arg.Res != nil {
 			if err := ctx.validateArg(arg.Res, typ.Type); err != nil {
 				return err
@@ -258,14 +255,20 @@ func (arg *PointerArg) validate(ctx *validCtx) error {
 	default:
 		return fmt.Errorf("ptr arg %v has bad type %v", arg, typ.Name())
 	}
-	maxMem := ctx.target.NumPages * ctx.target.PageSize
-	size := arg.VmaSize
-	if size == 0 && arg.Res != nil {
-		size = arg.Res.Size()
-	}
-	if arg.Address >= maxMem || arg.Address+size > maxMem {
-		return fmt.Errorf("ptr %v has bad address %v/%v/%v",
-			arg.Type().Name(), arg.Address, arg.VmaSize, size)
+	if arg.IsSpecial() {
+		if -arg.Address >= uint64(len(ctx.target.SpecialPointers)) {
+			return fmt.Errorf("special ptr arg %v has bad value 0x%x", arg.Type().Name(), arg.Address)
+		}
+	} else {
+		maxMem := ctx.target.NumPages * ctx.target.PageSize
+		size := arg.VmaSize
+		if size == 0 && arg.Res != nil {
+			size = arg.Res.Size()
+		}
+		if arg.Address >= maxMem || arg.Address+size > maxMem {
+			return fmt.Errorf("ptr %v has bad address %v/%v/%v",
+				arg.Type().Name(), arg.Address, arg.VmaSize, size)
+		}
 	}
 	return nil
 }
diff --git a/sys/linux/init.go b/sys/linux/init.go
index 035ffee2f..1400ce182 100644
--- a/sys/linux/init.go
+++ b/sys/linux/init.go
@@ -10,16 +10,6 @@ import (
 	"github.com/google/syzkaller/sys/targets"
 )
 
-/*
-func init() {
-	prog.RegisterTarget(gen.Target_amd64, initTarget)
-	prog.RegisterTarget(gen.Target_386, initTarget)
-	prog.RegisterTarget(gen.Target_arm64, initTarget)
-	prog.RegisterTarget(gen.Target_arm, initTarget)
-	prog.RegisterTarget(gen.Target_ppc64le, initTarget)
-}
-*/
-
 func InitTarget(target *prog.Target) {
 	arch := &arch{
 		unix:                      targets.MakeUnixSanitizer(target),
@@ -54,7 +44,26 @@ func InitTarget(target *prog.Target) {
 		"arpt_replace":       arch.generateArptables,
 		"ebt_replace":        arch.generateEbtables,
 	}
-	target.StringDictionary = stringDictionary
+	// TODO(dvyukov): get rid of this, this must be in descriptions.
+	target.StringDictionary = []string{
+		"user", "keyring", "trusted", "system", "security", "selinux",
+		"posix_acl_access", "mime_type", "md5sum", "nodev", "self",
+		"bdev", "proc", "cgroup", "cpuset",
+		"lo", "eth0", "eth1", "em0", "em1", "wlan0", "wlan1", "ppp0", "ppp1",
+		"vboxnet0", "vboxnet1", "vmnet0", "vmnet1", "GPL",
+	}
+	switch target.Arch {
+	case "amd64":
+		target.SpecialPointers = []uint64{
+			0xffffffff81000000, // kernel text
+		}
+	case "386":
+	case "arm64":
+	case "arm":
+	case "ppc64le":
+	default:
+		panic("unknown arch")
+	}
 
 	if target.Arch == runtime.GOARCH {
 		KCOV_INIT_TRACE = uintptr(target.ConstMap["KCOV_INIT_TRACE"])
@@ -70,13 +79,6 @@ var (
 	KCOV_ENABLE     uintptr
 	KCOV_DISABLE    uintptr
 	KCOV_TRACE_CMP  uintptr
-
-	// TODO(dvyukov): get rid of this, this must be in descriptions.
-	stringDictionary = []string{"user", "keyring", "trusted", "system", "security", "selinux",
-		"posix_acl_access", "mime_type", "md5sum", "nodev", "self",
-		"bdev", "proc", "cgroup", "cpuset",
-		"lo", "eth0", "eth1", "em0", "em1", "wlan0", "wlan1", "ppp0", "ppp1",
-		"vboxnet0", "vboxnet1", "vmnet0", "vmnet1", "GPL"}
 )
 
 type arch struct {
diff --git a/sys/linux/init_iptables.go b/sys/linux/init_iptables.go
index 231bcfb77..2a49bffe4 100644
--- a/sys/linux/init_iptables.go
+++ b/sys/linux/init_iptables.go
@@ -126,6 +126,9 @@ func (arch *arch) generateEbtables(g *prog.Gen, typ prog.Type, old prog.Arg) (
 	}
 	tableArg := arg.(*prog.UnionArg).Option.(*prog.GroupArg)
 	entriesPtr := tableArg.Inner[entriesField].(*prog.PointerArg)
+	if entriesPtr.Res == nil {
+		return
+	}
 	entriesArray := entriesPtr.Res.(*prog.GroupArg)
 	offsets := make([]uint64, len(entriesArray.Inner))
 	var pos, totalEntries uint64
@@ -165,8 +168,15 @@ func (arch *arch) sanitizeEbtables(c *prog.Call) {
 	// This is very hacky... just as netfilter interfaces.
 	// setsockopt's len argument must be equal to size of ebt_replace + entries size.
 	lenArg := c.Args[4].(*prog.ConstArg)
-	tableArg := c.Args[3].(*prog.PointerArg).Res.(*prog.UnionArg).Option.(*prog.GroupArg)
+	tablePtr := c.Args[3].(*prog.PointerArg).Res
+	if tablePtr == nil {
+		return
+	}
+	tableArg := tablePtr.(*prog.UnionArg).Option.(*prog.GroupArg)
 	entriesField := len(tableArg.Inner) - 1
 	entriesArg := tableArg.Inner[entriesField].(*prog.PointerArg).Res
+	if entriesArg == nil {
+		return
+	}
 	lenArg.Val = tableArg.Size() + entriesArg.Size()
 }