prog: implement complex len target support

This actually implements support for complex len targets
during program generation and mutation.

7 files changed, 138 insertions, 70 deletions

diff --git a/executor/defs.h b/executor/defs.h
index 9903d62db..4575527fa 100644
--- a/executor/defs.h
+++ b/executor/defs.h
@@ -165,7 +165,7 @@
 
 #if GOARCH_64
 #define GOARCH "64"
-#define SYZ_REVISION "33cd0beee631c76c13921b3578f75c508a5e6056"
+#define SYZ_REVISION "3218225be4c9aad40c39be2b8bcb3008fd76ff1e"
 #define SYZ_EXECUTOR_USES_FORK_SERVER 0
 #define SYZ_EXECUTOR_USES_SHMEM 0
 #define SYZ_PAGE_SIZE 4096
diff --git a/prog/checksum.go b/prog/checksum.go
index a64e6cf06..7a3208be2 100644
--- a/prog/checksum.go
+++ b/prog/checksum.go
@@ -121,6 +121,7 @@ func findCsummedArg(arg Arg, typ *CsumType, parentsMap map[Arg]Arg) Arg {
 		panic(fmt.Sprintf("parent for %v is not in parents map", typ.Name()))
 	} else {
 		for parent := parentsMap[arg]; parent != nil; parent = parentsMap[parent] {
+			// TODO(dvyukov): support template argument names as in size calculation.
 			if typ.Buf == parent.Type().Name() {
 				return parent
 			}
diff --git a/prog/encoding.go b/prog/encoding.go
index ba2cfb8ca..eb0fb79a9 100644
--- a/prog/encoding.go
+++ b/prog/encoding.go
@@ -570,7 +570,7 @@ func (p *parser) parseArgArray(typ Type) (Arg, error) {
 	p.Parse('[')
 	t1, ok := typ.(*ArrayType)
 	if !ok {
-		p.eatExcessive(false, "wrong array arg")
+		p.eatExcessive(false, "wrong array arg %T", typ)
 		p.Parse(']')
 		return typ.DefaultArg(), nil
 	}
diff --git a/prog/size.go b/prog/size.go
index 255fb7fa6..46afbd426 100644
--- a/prog/size.go
+++ b/prog/size.go
@@ -8,43 +8,7 @@ import (
 	"strings"
 )
 
-func (target *Target) generateSize(arg Arg, lenType *LenType) uint64 {
-	if arg == nil {
-		// Arg is an optional pointer, set size to 0.
-		return 0
-	}
-
-	bitSize := lenType.BitSize
-	if bitSize == 0 {
-		bitSize = 8
-	}
-	switch arg.Type().(type) {
-	case *VmaType:
-		a := arg.(*PointerArg)
-		return a.VmaSize * 8 / bitSize
-	case *ArrayType:
-		a := arg.(*GroupArg)
-		if lenType.BitSize != 0 {
-			return a.Size() * 8 / bitSize
-		}
-		return uint64(len(a.Inner))
-	default:
-		return arg.Size() * 8 / bitSize
-	}
-}
-
 func (target *Target) assignSizes(args []Arg, parentsMap map[Arg]Arg, autos map[Arg]bool) {
-	// Create a map from field names to args.
-	argsMap := make(map[string]Arg)
-	for _, arg := range args {
-		if IsPad(arg.Type()) {
-			continue
-		}
-		argsMap[arg.Type().FieldName()] = arg
-	}
-
-	// Fill in size arguments.
-nextArg:
 	for _, arg := range args {
 		if arg = InnerArg(arg); arg == nil {
 			continue // Pointer to optional len field, no need to fill in value.
@@ -60,39 +24,82 @@ nextArg:
 			delete(autos, arg)
 		}
 		a := arg.(*ConstArg)
+		target.assignSize(a, a, typ.Path, args, parentsMap)
+	}
+}
 
-		elem := typ.Path[0]
-		buf, ok := argsMap[elem]
-		if ok {
-			a.Val = target.generateSize(InnerArg(buf), typ)
+func (target *Target) assignSize(dst *ConstArg, pos Arg, path []string, args []Arg, parentsMap map[Arg]Arg) {
+	elem := path[0]
+	path = path[1:]
+	for _, buf := range args {
+		if elem != buf.Type().FieldName() {
 			continue
 		}
-
-		if elem == "parent" {
-			a.Val = parentsMap[arg].Size()
-			if typ.BitSize != 0 {
-				a.Val = a.Val * 8 / typ.BitSize
+		buf = InnerArg(buf)
+		if len(path) == 0 {
+			dst.Val = target.computeSize(buf, dst.Type().(*LenType))
+		} else {
+			target.assignSize(dst, buf, path, buf.(*GroupArg).Inner, parentsMap)
+		}
+		return
+	}
+	if elem == "parent" {
+		buf := parentsMap[pos]
+		if len(path) == 0 {
+			dst.Val = target.computeSize(buf, dst.Type().(*LenType))
+		} else {
+			if path[0] == "parent" {
+				buf = parentsMap[buf]
 			}
+			target.assignSize(dst, buf, path, buf.(*GroupArg).Inner, parentsMap)
+		}
+		return
+	}
+	for buf := parentsMap[pos]; buf != nil; buf = parentsMap[buf] {
+		parentName := buf.Type().Name()
+		if pos := strings.IndexByte(parentName, '['); pos != -1 {
+			// For template parents, strip arguments.
+			parentName = parentName[:pos]
+		}
+		if elem != parentName {
 			continue
 		}
+		if len(path) == 0 {
+			dst.Val = target.computeSize(buf, dst.Type().(*LenType))
+		} else {
+			target.assignSize(dst, buf, path, buf.(*GroupArg).Inner, parentsMap)
+		}
+		return
+	}
+	var argNames []string
+	for _, arg := range args {
+		argNames = append(argNames, arg.Type().FieldName())
+	}
+	panic(fmt.Sprintf("len field %q references non existent field %q, pos=%q/%q, argsMap: %+v",
+		dst.Type().FieldName(), elem, pos.Type().Name(), pos.Type().FieldName(), argNames))
+}
 
-		for parent := parentsMap[arg]; parent != nil; parent = parentsMap[parent] {
-			parentName := parent.Type().Name()
-			if pos := strings.IndexByte(parentName, '['); pos != -1 {
-				// For template parents, strip arguments.
-				parentName = parentName[:pos]
-			}
-			if elem != parentName {
-				continue
-			}
-			a.Val = parent.Size()
-			if typ.BitSize != 0 {
-				a.Val = a.Val * 8 / typ.BitSize
-			}
-			continue nextArg
+func (target *Target) computeSize(arg Arg, lenType *LenType) uint64 {
+	if arg == nil {
+		// Arg is an optional pointer, set size to 0.
+		return 0
+	}
+	bitSize := lenType.BitSize
+	if bitSize == 0 {
+		bitSize = 8
+	}
+	switch arg.Type().(type) {
+	case *VmaType:
+		a := arg.(*PointerArg)
+		return a.VmaSize * 8 / bitSize
+	case *ArrayType:
+		a := arg.(*GroupArg)
+		if lenType.BitSize != 0 {
+			return a.Size() * 8 / bitSize
 		}
-		panic(fmt.Sprintf("len field '%v' references non existent field '%v', argsMap: %+v",
-			typ.FieldName(), elem, argsMap))
+		return uint64(len(a.Inner))
+	default:
+		return arg.Size() * 8 / bitSize
 	}
 }
 
@@ -126,8 +133,8 @@ func (r *randGen) mutateSize(arg *ConstArg, parent []Arg) bool {
 	elemSize := typ.BitSize / 8
 	if elemSize == 0 {
 		elemSize = 1
+		// TODO(dvyukov): implement path support for size mutation.
 		if len(typ.Path) == 1 {
-			// TODO(dvyukov): implement path support for size mutation.
 			for _, field := range parent {
 				if typ.Path[0] != field.Type().FieldName() {
 					continue
diff --git a/prog/size_test.go b/prog/size_test.go
index 726f98d65..1962b3fc6 100644
--- a/prog/size_test.go
+++ b/prog/size_test.go
@@ -151,8 +151,11 @@ func TestAssignSize(t *testing.T) {
 			"test$length29(&(0x7f0000000000)={'./a\\x00', './b/c\\x00', 0x0, 0x0, 0x0})",
 			"test$length29(&(0x7f0000000000)={'./a\\x00', './b/c\\x00', 0xa, 0x14, 0x21})",
 		},
+		{
+			"test$length30(&(0x7f0000000000)={{{0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, {'a', 'aaa', 'aaaaa', 'aaaaaa'}, &(0x7f0000000000)={'a', 'aaa', 'aaaaa', 'aaaaaa'}, &(0x7f0000000000)=&(0x7f0000000000)={'a', 'aaa', 'aaaaa', 'aaaaaa'}, 0x0}}, 0x0, &(0x7f0000000000)=0x0, 0x0)",
+			"test$length30(&(0x7f0000000000)={{{0x0, 0x18, 0x1, 0x3, 0x5, 0x6}, {'a', 'aaa', 'aaaaa', 'aaaaaa'}, &(0x7f0000000000)={'a', 'aaa', 'aaaaa', 'aaaaaa'}, &(0x7f0000000000)=&(0x7f0000000000)={'a', 'aaa', 'aaaaa', 'aaaaaa'}, 0x2}}, 0x40, &(0x7f0000000000)=0x18, 0x2)",
+		},
 	}
-
 	for i, test := range tests {
 		p, err := target.Deserialize([]byte(test.unsizedProg), Strict)
 		if err != nil {
diff --git a/sys/test/gen/64.go b/sys/test/gen/64.go
index c00aa20a3..c07a033db 100644
--- a/sys/test/gen/64.go
+++ b/sys/test/gen/64.go
@@ -90,6 +90,33 @@ var structDescs_64 = []*KeyedStruct{
 	{Key: StructKey{Name: "explicitly_sized_union"}, Desc: &StructDesc{TypeCommon: TypeCommon{TypeName: "explicitly_sized_union", TypeSize: 42}, Fields: []Type{
 		&IntType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "int8", FldName: "f1", TypeSize: 1}}},
 	}}},
+	{Key: StructKey{Name: "len_expr1"}, Desc: &StructDesc{TypeCommon: TypeCommon{TypeName: "len_expr1", TypeSize: 64}, Fields: []Type{
+		&StructType{Key: StructKey{Name: "len_expr2"}, FldName: "f11"},
+	}}},
+	{Key: StructKey{Name: "len_expr2"}, Desc: &StructDesc{TypeCommon: TypeCommon{TypeName: "len_expr2", TypeSize: 64}, Fields: []Type{
+		&StructType{Key: StructKey{Name: "len_expr3"}, FldName: "f21"},
+		&StructType{Key: StructKey{Name: "len_expr4"}, FldName: "f22"},
+		&ConstType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "pad", TypeSize: 1}}, IsPad: true},
+		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "f23", TypeSize: 8}, Type: &StructType{Key: StructKey{Name: "len_expr4"}}},
+		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "f24", TypeSize: 8}, Type: &PtrType{TypeCommon: TypeCommon{TypeName: "ptr", TypeSize: 8}, Type: &StructType{Key: StructKey{Name: "len_expr4"}}}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "len", FldName: "f25", TypeSize: 4}}, Path: []string{"f21", "f31"}},
+		&ConstType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "pad", TypeSize: 4}}, IsPad: true},
+	}}},
+	{Key: StructKey{Name: "len_expr3"}, Desc: &StructDesc{TypeCommon: TypeCommon{TypeName: "len_expr3", TypeSize: 24}, Fields: []Type{
+		&IntType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "int16", FldName: "f31", TypeSize: 2}}},
+		&ConstType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "pad", TypeSize: 2}}, IsPad: true},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "f32", TypeSize: 4}}, BitSize: 8, Path: []string{"len_expr2", "f21"}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "f33", TypeSize: 4}}, BitSize: 8, Path: []string{"len_expr2", "f22", "f41"}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "f34", TypeSize: 4}}, BitSize: 8, Path: []string{"len_expr1", "f11", "f22", "f42"}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "f35", TypeSize: 4}}, BitSize: 8, Path: []string{"len_expr2", "f23", "f43"}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "f36", TypeSize: 4}}, BitSize: 8, Path: []string{"len_expr2", "f24", "f44"}},
+	}}},
+	{Key: StructKey{Name: "len_expr4"}, Desc: &StructDesc{TypeCommon: TypeCommon{TypeName: "len_expr4", TypeSize: 15}, Fields: []Type{
+		&BufferType{TypeCommon: TypeCommon{TypeName: "array", FldName: "f41", TypeSize: 1}, Kind: 1, RangeBegin: 1, RangeEnd: 1},
+		&BufferType{TypeCommon: TypeCommon{TypeName: "array", FldName: "f42", TypeSize: 3}, Kind: 1, RangeBegin: 3, RangeEnd: 3},
+		&BufferType{TypeCommon: TypeCommon{TypeName: "array", FldName: "f43", TypeSize: 5}, Kind: 1, RangeBegin: 5, RangeEnd: 5},
+		&BufferType{TypeCommon: TypeCommon{TypeName: "array", FldName: "f44", TypeSize: 6}, Kind: 1, RangeBegin: 6, RangeEnd: 6},
+	}}},
 	{Key: StructKey{Name: "len_nontemp4"}, Desc: &StructDesc{TypeCommon: TypeCommon{TypeName: "len_nontemp4", TypeSize: 4}, Fields: []Type{
 		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "len", FldName: "f1", TypeSize: 4}}, Path: []string{"len_temp3"}},
 	}}},
@@ -835,9 +862,11 @@ var syscalls_64 = []*Syscall{
 	{Name: "test$length3", CallName: "test", MissingArgs: 5, Args: []Type{
 		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "a0", TypeSize: 8}, Type: &StructType{Key: StructKey{Name: "syz_length_len_struct"}}},
 	}},
-	{Name: "test$length30", CallName: "test", MissingArgs: 4, Args: []Type{
-		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "a0", TypeSize: 8}, Type: &StructType{Key: StructKey{Name: "syz_length_int_struct"}}},
-		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "a1", TypeSize: 8}}, BitSize: 8, Path: []string{"a0", "f0"}},
+	{Name: "test$length30", CallName: "test", MissingArgs: 2, Args: []Type{
+		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "a0", TypeSize: 8}, Type: &StructType{Key: StructKey{Name: "len_expr1"}}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "a1", TypeSize: 8}}, BitSize: 8, Path: []string{"a0", "f11"}},
+		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "a2", TypeSize: 8}, Type: &LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", TypeSize: 4}}, BitSize: 8, Path: []string{"a0", "f11", "f21"}}},
+		&LenType{IntTypeCommon: IntTypeCommon{TypeCommon: TypeCommon{TypeName: "bytesize", FldName: "a3", TypeSize: 8}}, BitSize: 8, Path: []string{"a0", "f11", "f21", "f31"}},
 	}},
 	{Name: "test$length4", CallName: "test", MissingArgs: 5, Args: []Type{
 		&PtrType{TypeCommon: TypeCommon{TypeName: "ptr", FldName: "a0", TypeSize: 8}, Type: &StructType{Key: StructKey{Name: "syz_length_len2_struct"}}},
@@ -974,4 +1003,4 @@ var consts_64 = []ConstValue{
 	{Name: "SYS_unsupported"},
 }
 
-const revision_64 = "33cd0beee631c76c13921b3578f75c508a5e6056"
+const revision_64 = "3218225be4c9aad40c39be2b8bcb3008fd76ff1e"
diff --git a/sys/test/test.txt b/sys/test/test.txt
index 764f4422d..9fd037bf3 100644
--- a/sys/test/test.txt
+++ b/sys/test/test.txt
@@ -430,7 +430,35 @@ test$length27(a0 ptr[in, explicitly_sized], a1 len[a0])
 test$length28(a0 ptr[in, explicitly_sized_union], a1 len[a0])
 test$length29(a ptr[in, static_filename])
 
-test$length30(a0 ptr[in, syz_length_int_struct], a1 bytesize[a0:f0])
+len_expr1 {
+	f11	len_expr2
+}
+
+len_expr2 {
+	f21	len_expr3
+	f22	len_expr4
+	f23	ptr[in, len_expr4]
+	f24	ptr[in, ptr[in, len_expr4]]
+	f25	len[f21:f31, int32]
+}
+
+len_expr3 {
+	f31	int16
+	f32	bytesize[len_expr2:f21, int32]
+	f33	bytesize[len_expr2:f22:f41, int32]
+	f34	bytesize[len_expr1:f11:f22:f42, int32]
+	f35	bytesize[len_expr2:f23:f43, int32]
+	f36	bytesize[len_expr2:f24:f44, int32]
+}
+
+len_expr4 {
+	f41	array[int8, 1]
+	f42	array[int8, 3]
+	f43	array[int8, 5]
+	f44	array[int8, 6]
+}
+
+test$length30(a0 ptr[in, len_expr1], a1 bytesize[a0:f11], a2 ptr[in, bytesize[a0:f11:f21, int32]], a3 bytesize[a0:f11:f21:f31])
 
 # Big endian