fuzz_test.go

     1  // Copyright 2024 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package maps implements Go's builtin map type.
     6  package maps_test
     7  
     8  import (
     9  	"bytes"
    10  	"encoding/binary"
    11  	"fmt"
    12  	"internal/runtime/maps"
    13  	"reflect"
    14  	"testing"
    15  	"unsafe"
    16  )
    17  
    18  // The input to FuzzTable is a binary-encoded array of fuzzCommand structs.
    19  //
    20  // Each fuzz call begins with an empty Map[uint16, uint32].
    21  //
    22  // Each command is then executed on the map in sequence. Operations with
    23  // output (e.g., Get) are verified against a reference map.
    24  type fuzzCommand struct {
    25  	Op fuzzOp
    26  
    27  	// Used for Get, Put, Delete.
    28  	Key uint16
    29  
    30  	// Used for Put.
    31  	Elem uint32
    32  }
    33  
    34  // Encoded size of fuzzCommand.
    35  var fuzzCommandSize = binary.Size(fuzzCommand{})
    36  
    37  type fuzzOp uint8
    38  
    39  const (
    40  	fuzzOpGet fuzzOp = iota
    41  	fuzzOpPut
    42  	fuzzOpDelete
    43  )
    44  
    45  func encode(fc []fuzzCommand) []byte {
    46  	var buf bytes.Buffer
    47  	if err := binary.Write(&buf, binary.LittleEndian, fc); err != nil {
    48  		panic(fmt.Sprintf("error writing %v: %v", fc, err))
    49  	}
    50  	return buf.Bytes()
    51  }
    52  
    53  func decode(b []byte) []fuzzCommand {
    54  	// Round b down to a multiple of fuzzCommand size. i.e., ignore extra
    55  	// bytes of input.
    56  	entries := len(b) / fuzzCommandSize
    57  	usefulSize := entries * fuzzCommandSize
    58  	b = b[:usefulSize]
    59  
    60  	fc := make([]fuzzCommand, entries)
    61  	buf := bytes.NewReader(b)
    62  	if err := binary.Read(buf, binary.LittleEndian, &fc); err != nil {
    63  		panic(fmt.Sprintf("error reading %v: %v", b, err))
    64  	}
    65  
    66  	return fc
    67  }
    68  
    69  func TestEncodeDecode(t *testing.T) {
    70  	fc := []fuzzCommand{
    71  		{
    72  			Op:   fuzzOpPut,
    73  			Key:  123,
    74  			Elem: 456,
    75  		},
    76  		{
    77  			Op:  fuzzOpGet,
    78  			Key: 123,
    79  		},
    80  	}
    81  
    82  	b := encode(fc)
    83  	got := decode(b)
    84  	if !reflect.DeepEqual(fc, got) {
    85  		t.Errorf("encode-decode roundtrip got %+v want %+v", got, fc)
    86  	}
    87  
    88  	// Extra trailing bytes ignored.
    89  	b = append(b, 42)
    90  	got = decode(b)
    91  	if !reflect.DeepEqual(fc, got) {
    92  		t.Errorf("encode-decode (extra byte) roundtrip got %+v want %+v", got, fc)
    93  	}
    94  }
    95  
    96  func FuzzTable(f *testing.F) {
    97  	// All of the ops.
    98  	f.Add(encode([]fuzzCommand{
    99  		{
   100  			Op:   fuzzOpPut,
   101  			Key:  123,
   102  			Elem: 456,
   103  		},
   104  		{
   105  			Op:  fuzzOpDelete,
   106  			Key: 123,
   107  		},
   108  		{
   109  			Op:  fuzzOpGet,
   110  			Key: 123,
   111  		},
   112  	}))
   113  
   114  	// Add enough times to trigger grow.
   115  	f.Add(encode([]fuzzCommand{
   116  		{
   117  			Op:   fuzzOpPut,
   118  			Key:  1,
   119  			Elem: 101,
   120  		},
   121  		{
   122  			Op:   fuzzOpPut,
   123  			Key:  2,
   124  			Elem: 102,
   125  		},
   126  		{
   127  			Op:   fuzzOpPut,
   128  			Key:  3,
   129  			Elem: 103,
   130  		},
   131  		{
   132  			Op:   fuzzOpPut,
   133  			Key:  4,
   134  			Elem: 104,
   135  		},
   136  		{
   137  			Op:   fuzzOpPut,
   138  			Key:  5,
   139  			Elem: 105,
   140  		},
   141  		{
   142  			Op:   fuzzOpPut,
   143  			Key:  6,
   144  			Elem: 106,
   145  		},
   146  		{
   147  			Op:   fuzzOpPut,
   148  			Key:  7,
   149  			Elem: 107,
   150  		},
   151  		{
   152  			Op:   fuzzOpPut,
   153  			Key:  8,
   154  			Elem: 108,
   155  		},
   156  		{
   157  			Op:  fuzzOpGet,
   158  			Key: 1,
   159  		},
   160  		{
   161  			Op:  fuzzOpDelete,
   162  			Key: 2,
   163  		},
   164  		{
   165  			Op:   fuzzOpPut,
   166  			Key:  2,
   167  			Elem: 42,
   168  		},
   169  		{
   170  			Op:  fuzzOpGet,
   171  			Key: 2,
   172  		},
   173  	}))
   174  
   175  	f.Fuzz(func(t *testing.T, in []byte) {
   176  		fc := decode(in)
   177  		if len(fc) == 0 {
   178  			return
   179  		}
   180  
   181  		m, typ := maps.NewTestMap[uint16, uint32](8)
   182  		ref := make(map[uint16]uint32)
   183  		for _, c := range fc {
   184  			switch c.Op {
   185  			case fuzzOpGet:
   186  				elemPtr, ok := m.Get(typ, unsafe.Pointer(&c.Key))
   187  				refElem, refOK := ref[c.Key]
   188  
   189  				if ok != refOK {
   190  					t.Errorf("Get(%d) got ok %v want ok %v", c.Key, ok, refOK)
   191  				}
   192  				if !ok {
   193  					continue
   194  				}
   195  				gotElem := *(*uint32)(elemPtr)
   196  				if gotElem != refElem {
   197  					t.Errorf("Get(%d) got %d want %d", c.Key, gotElem, refElem)
   198  				}
   199  			case fuzzOpPut:
   200  				m.Put(typ, unsafe.Pointer(&c.Key), unsafe.Pointer(&c.Elem))
   201  				ref[c.Key] = c.Elem
   202  			case fuzzOpDelete:
   203  				m.Delete(typ, unsafe.Pointer(&c.Key))
   204  				delete(ref, c.Key)
   205  			default:
   206  				// Just skip this command to keep the fuzzer
   207  				// less constrained.
   208  				continue
   209  			}
   210  		}
   211  	})
   212  }
   213
View as plain text