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