pkg/compiler: fix bitfield layout bug

Fixes #1542

Found thanks to syz-check. Update #590

1 files changed, 105 insertions, 51 deletions

diff --git a/pkg/compiler/gen.go b/pkg/compiler/gen.go
index 5e8267994..631ea5299 100644
--- a/pkg/compiler/gen.go
+++ b/pkg/compiler/gen.go
@@ -200,8 +200,8 @@ func (ctx *structGen) walkStruct(t *prog.StructType) {
 		}
 	}
 	packed, sizeAttr, alignAttr := comp.parseStructAttrs(structNode)
-	t.Fields = comp.layoutStruct(t.Fields, varlen, packed, alignAttr)
 	t.AlignAttr = alignAttr
+	comp.layoutStruct(t, varlen, packed)
 	t.TypeSize = 0
 	if !varlen {
 		for _, f := range t.Fields {
@@ -258,82 +258,130 @@ func (comp *compiler) genStructDesc(res *prog.StructDesc, n *ast.Struct, dir pro
 	}
 }
 
-func (comp *compiler) layoutStruct(fields []prog.Type, varlen, packed bool, alignAttr uint64) []prog.Type {
+func (comp *compiler) layoutStruct(t *prog.StructType, varlen, packed bool) {
 	var newFields []prog.Type
-	var align, off, bfOffset uint64
-	for i, f := range fields {
-		if f.IsBitfield() {
-			off, middle := bfOffset, true
-			bfOffset += f.BitfieldLength()
-			// Last bitfield in a group, if last field of the struct...
-			if i == len(fields)-1 ||
-				// or next field is not a bitfield...
-				fields[i+1].BitfieldLength() == 0 ||
-				// or next field is of different size...
-				f.Size() != fields[i+1].Size() ||
-				// or next field does not fit into the current group.
-				bfOffset+fields[i+1].BitfieldLength() > f.Size()*8 {
-				middle, bfOffset = false, 0
+	var structAlign, byteOffset, bitOffset uint64
+	for i, f := range t.Fields {
+		fieldAlign := uint64(1)
+		if !packed {
+			fieldAlign = comp.typeAlign(f)
+			if structAlign < fieldAlign {
+				structAlign = fieldAlign
 			}
-			setBitfieldOffset(f, off, middle)
-		}
-		needPadding := true
-		if i != 0 {
-			prev := fields[i-1]
-			needPadding = !prev.Varlen() && prev.Size() != 0
 		}
-		if needPadding && !packed {
-			a := comp.typeAlign(f)
-			if align < a {
-				align = a
+		fullBitOffset := byteOffset*8 + bitOffset
+		var fieldOffset uint64
+
+		if f.IsBitfield() {
+			unitAlign := f.UnitSize()
+			if packed {
+				unitAlign = 1
+			}
+			fieldOffset = rounddown(fullBitOffset/8, unitAlign)
+			unitBits := f.UnitSize() * 8
+			occupiedBits := fullBitOffset - fieldOffset*8
+			remainBits := unitBits - occupiedBits
+
+			if remainBits < f.BitfieldLength() {
+				fieldOffset = roundup(roundup(fullBitOffset, 8)/8, unitAlign)
+				fullBitOffset, bitOffset = 0, 0
+			} else if fieldOffset*8 >= fullBitOffset {
+				fullBitOffset, bitOffset = fieldOffset*8, 0
 			}
-			// Append padding if the last field is not a bitfield or it's the last bitfield in a set.
-			if !packed && off%a != 0 {
-				pad := a - off%a
-				off += pad
+			fieldBitOffset := (fullBitOffset - fieldOffset*8) % unitBits
+			setBitfieldOffset(f, fieldBitOffset)
+		} else {
+			fieldOffset = roundup(roundup(fullBitOffset, 8)/8, fieldAlign)
+			bitOffset = 0
+		}
+		if fieldOffset > byteOffset {
+			pad := fieldOffset - byteOffset
+			byteOffset += pad
+			if i != 0 && t.Fields[i-1].IsBitfield() {
+				setBitfieldTypeSize(t.Fields[i-1], pad)
+			} else {
 				newFields = append(newFields, genPad(pad))
 			}
 		}
+		if f.IsBitfield() {
+			if byteOffset > fieldOffset {
+				unitOffset := byteOffset - fieldOffset
+				setBitfieldUnitOffset(f, unitOffset)
+			}
+		}
 		newFields = append(newFields, f)
-		if !f.Varlen() {
+		if f.IsBitfield() {
+			bitOffset += f.BitfieldLength()
+		} else if !f.Varlen() {
 			// Increase offset if the current field except when it's
 			// the last field in a struct and has variable length.
-			off += f.Size()
+			byteOffset += f.Size()
+		}
+	}
+	if bitOffset != 0 {
+		pad := roundup(bitOffset, 8) / 8
+		byteOffset += pad
+		i := len(t.Fields)
+		if i != 0 && t.Fields[i-1].IsBitfield() {
+			setBitfieldTypeSize(t.Fields[i-1], pad)
+		} else {
+			newFields = append(newFields, genPad(pad))
 		}
 	}
-	if alignAttr != 0 {
-		align = alignAttr
+
+	if t.AlignAttr != 0 {
+		structAlign = t.AlignAttr
 	}
-	if align != 0 && off%align != 0 && !varlen {
-		pad := align - off%align
-		off += pad
+	if !varlen && structAlign != 0 && byteOffset%structAlign != 0 {
+		pad := structAlign - byteOffset%structAlign
 		newFields = append(newFields, genPad(pad))
 	}
-	return newFields
+	t.Fields = newFields
+}
+
+func roundup(v, a uint64) uint64 {
+	return rounddown(v+a-1, a)
 }
 
-func setBitfieldOffset(t0 prog.Type, offset uint64, middle bool) {
-	size := t0.Size()
-	unit := size
-	if middle {
-		size = 0
+func rounddown(v, a uint64) uint64 {
+	if (a & (a - 1)) != 0 {
+		panic(fmt.Sprintf("rounddown(%v)", a))
 	}
+	return v & ^(a - 1)
+}
+
+func bitfieldFields(t0 prog.Type) (*uint64, *uint64, *uint64) {
 	switch t := t0.(type) {
 	case *prog.IntType:
-		t.BitfieldOff, t.BitfieldUnit, t.TypeSize = offset, unit, size
+		return &t.TypeSize, &t.BitfieldOff, &t.BitfieldUnitOff
 	case *prog.ConstType:
-		t.BitfieldOff, t.BitfieldUnit, t.TypeSize = offset, unit, size
+		return &t.TypeSize, &t.BitfieldOff, &t.BitfieldUnitOff
 	case *prog.LenType:
-		t.BitfieldOff, t.BitfieldUnit, t.TypeSize = offset, unit, size
+		return &t.TypeSize, &t.BitfieldOff, &t.BitfieldUnitOff
 	case *prog.FlagsType:
-		t.BitfieldOff, t.BitfieldUnit, t.TypeSize = offset, unit, size
+		return &t.TypeSize, &t.BitfieldOff, &t.BitfieldUnitOff
 	case *prog.ProcType:
-		t.BitfieldOff, t.BitfieldUnit, t.TypeSize = offset, unit, size
+		return &t.TypeSize, &t.BitfieldOff, &t.BitfieldUnitOff
 	default:
 		panic(fmt.Sprintf("type %#v can't be a bitfield", t))
 	}
 }
 
+func setBitfieldTypeSize(t prog.Type, v uint64) {
+	p, _, _ := bitfieldFields(t)
+	*p = v
+}
+
+func setBitfieldOffset(t prog.Type, v uint64) {
+	_, p, _ := bitfieldFields(t)
+	*p = v
+}
+
+func setBitfieldUnitOffset(t prog.Type, v uint64) {
+	_, _, p := bitfieldFields(t)
+	*p = v
+}
+
 func (comp *compiler) typeAlign(t0 prog.Type) uint64 {
 	switch t0.Format() {
 	case prog.FormatNative, prog.FormatBigEndian:
@@ -426,10 +474,16 @@ func genIntCommon(com prog.TypeCommon, bitLen uint64, bigEndian bool) prog.IntTy
 	if bigEndian {
 		bf = prog.FormatBigEndian
 	}
+	bfUnit := uint64(0)
+	if bitLen != 0 {
+		bfUnit = com.TypeSize
+		com.TypeSize = 0
+	}
 	return prog.IntTypeCommon{
-		TypeCommon:  com,
-		ArgFormat:   bf,
-		BitfieldLen: bitLen,
+		TypeCommon:   com,
+		ArgFormat:    bf,
+		BitfieldLen:  bitLen,
+		BitfieldUnit: bfUnit,
 	}
 }