table.go

Documentation: github.com/tetratelabs/wazero/internal/wasm

     1  package wasm
     2  
     3  import (
     4  	"fmt"
     5  	"math"
     6  
     7  	"github.com/tetratelabs/wazero/api"
     8  	"github.com/tetratelabs/wazero/internal/leb128"
     9  )
    10  
    11  // Table describes the limits of elements and its type in a table.
    12  type Table struct {
    13  	Min  uint32
    14  	Max  *uint32
    15  	Type RefType
    16  }
    17  
    18  // RefType is either RefTypeFuncref or RefTypeExternref as of WebAssembly core 2.0.
    19  type RefType = byte
    20  
    21  const (
    22  	// RefTypeFuncref represents a reference to a function.
    23  	RefTypeFuncref = ValueTypeFuncref
    24  	// RefTypeExternref represents a reference to a host object, which is not currently supported in wazero.
    25  	RefTypeExternref = ValueTypeExternref
    26  )
    27  
    28  func RefTypeName(t RefType) (ret string) {
    29  	switch t {
    30  	case RefTypeFuncref:
    31  		ret = "funcref"
    32  	case RefTypeExternref:
    33  		ret = "externref"
    34  	default:
    35  		ret = fmt.Sprintf("unknown(0x%x)", t)
    36  	}
    37  	return
    38  }
    39  
    40  // ElementMode represents a mode of element segment which is either active, passive or declarative.
    41  //
    42  // https://www.w3.org/TR/2022/WD-wasm-core-2-20220419/syntax/modules.html#element-segments
    43  type ElementMode = byte
    44  
    45  const (
    46  	// ElementModeActive is the mode which requires the runtime to initialize table with the contents in .Init field combined with OffsetExpr.
    47  	ElementModeActive ElementMode = iota
    48  	// ElementModePassive is the mode which doesn't require the runtime to initialize table, and only used with OpcodeTableInitName.
    49  	ElementModePassive
    50  	// ElementModeDeclarative is introduced in reference-types proposal which can be used to declare function indexes used by OpcodeRefFunc.
    51  	ElementModeDeclarative
    52  )
    53  
    54  // ElementSegment are initialization instructions for a TableInstance
    55  //
    56  // See https://www.w3.org/TR/2019/REC-wasm-core-1-20191205/#syntax-elem
    57  type ElementSegment struct {
    58  	// OffsetExpr returns the table element offset to apply to Init indices.
    59  	// Note: This can be validated prior to instantiation unless it includes OpcodeGlobalGet (an imported global).
    60  	OffsetExpr ConstantExpression
    61  
    62  	// TableIndex is the table's index to which this element segment is applied.
    63  	// Note: This is used if and only if the Mode is active.
    64  	TableIndex Index
    65  
    66  	// Followings are set/used regardless of the Mode.
    67  
    68  	// Init indices are (nullable) table elements where each index is the function index by which the module initialize the table.
    69  	Init []Index
    70  
    71  	// Type holds the type of this element segment, which is the RefType in WebAssembly 2.0.
    72  	Type RefType
    73  
    74  	// Mode is the mode of this element segment.
    75  	Mode ElementMode
    76  }
    77  
    78  const (
    79  	// ElementInitNullReference represents the null reference in ElementSegment's Init.
    80  	// In Wasm spec, an init item represents either Function's Index or null reference,
    81  	// and in wazero, we limit the maximum number of functions available in a module to
    82  	// MaximumFunctionIndex. Therefore, it is safe to use 1 << 31 to represent the null
    83  	// reference in Element segments.
    84  	ElementInitNullReference Index = 1 << 31
    85  	// ElementInitImportedGlobalFunctionReference represents an init item which is resolved via an imported global constexpr.
    86  	// The actual function reference stored at Global is only known at instantiation-time, so we set this flag
    87  	// to items of ElementSegment.Init at binary decoding, and unwrap this flag at instantiation to resolve the value.
    88  	//
    89  	// This might collide the init element resolved via ref.func instruction which is resolved with the func index at decoding,
    90  	// but in practice, that is not allowed in wazero thanks to our limit MaximumFunctionIndex. Thus, it is safe to set this flag
    91  	// in init element to indicate as such.
    92  	ElementInitImportedGlobalFunctionReference Index = 1 << 30
    93  )
    94  
    95  // unwrapElementInitGlobalReference takes an item of the init vector of an ElementSegment,
    96  // and returns the Global index if it is supposed to get generated from a global.
    97  // ok is true if the given init item is as such.
    98  func unwrapElementInitGlobalReference(init Index) (_ Index, ok bool) {
    99  	if init&ElementInitImportedGlobalFunctionReference == ElementInitImportedGlobalFunctionReference {
   100  		return init &^ ElementInitImportedGlobalFunctionReference, true
   101  	}
   102  	return init, false
   103  }
   104  
   105  // IsActive returns true if the element segment is "active" mode which requires the runtime to initialize table
   106  // with the contents in .Init field.
   107  func (e *ElementSegment) IsActive() bool {
   108  	return e.Mode == ElementModeActive
   109  }
   110  
   111  // TableInstance represents a table of (RefTypeFuncref) elements in a module.
   112  //
   113  // See https://www.w3.org/TR/2019/REC-wasm-core-1-20191205/#table-instances%E2%91%A0
   114  type TableInstance struct {
   115  	// References holds references whose type is either RefTypeFuncref or RefTypeExternref (unsupported).
   116  	//
   117  	// Currently, only function references are supported.
   118  	References []Reference
   119  
   120  	// Min is the minimum (function) elements in this table and cannot grow to accommodate ElementSegment.
   121  	Min uint32
   122  
   123  	// Max if present is the maximum (function) elements in this table, or nil if unbounded.
   124  	Max *uint32
   125  
   126  	// Type is either RefTypeFuncref or RefTypeExternRef.
   127  	Type RefType
   128  }
   129  
   130  // ElementInstance represents an element instance in a module.
   131  //
   132  // See https://www.w3.org/TR/2022/WD-wasm-core-2-20220419/exec/runtime.html#element-instances
   133  type ElementInstance = []Reference
   134  
   135  // Reference is the runtime representation of RefType which is either RefTypeFuncref or RefTypeExternref.
   136  type Reference = uintptr
   137  
   138  // validateTable ensures any ElementSegment is valid. This caches results via Module.validatedActiveElementSegments.
   139  // Note: limitsType are validated by decoders, so not re-validated here.
   140  func (m *Module) validateTable(enabledFeatures api.CoreFeatures, tables []Table, maximumTableIndex uint32) error {
   141  	if len(tables) > int(maximumTableIndex) {
   142  		return fmt.Errorf("too many tables in a module: %d given with limit %d", len(tables), maximumTableIndex)
   143  	}
   144  
   145  	importedTableCount := m.ImportTableCount
   146  
   147  	// Create bounds checks as these can err prior to instantiation
   148  	funcCount := m.ImportFunctionCount + m.SectionElementCount(SectionIDFunction)
   149  	globalsCount := m.ImportGlobalCount + m.SectionElementCount(SectionIDGlobal)
   150  
   151  	// Now, we have to figure out which table elements can be resolved before instantiation and also fail early if there
   152  	// are any imported globals that are known to be invalid by their declarations.
   153  	for i := range m.ElementSection {
   154  		elem := &m.ElementSection[i]
   155  		idx := Index(i)
   156  		initCount := uint32(len(elem.Init))
   157  
   158  		if elem.Type == RefTypeFuncref {
   159  			// Any offset applied is to the element, not the function index: validate here if the funcidx is sound.
   160  			for ei, init := range elem.Init {
   161  				if init == ElementInitNullReference {
   162  					continue
   163  				}
   164  				index, ok := unwrapElementInitGlobalReference(init)
   165  				if ok {
   166  					if index >= globalsCount {
   167  						return fmt.Errorf("%s[%d].init[%d] globalidx %d out of range", SectionIDName(SectionIDElement), idx, ei, index)
   168  					}
   169  				} else {
   170  					if index >= funcCount {
   171  						return fmt.Errorf("%s[%d].init[%d] funcidx %d out of range", SectionIDName(SectionIDElement), idx, ei, index)
   172  					}
   173  				}
   174  			}
   175  		} else {
   176  			for j, elem := range elem.Init {
   177  				if elem != ElementInitNullReference {
   178  					return fmt.Errorf("%s[%d].init[%d] must be ref.null but was %v", SectionIDName(SectionIDElement), idx, j, elem)
   179  				}
   180  			}
   181  		}
   182  
   183  		if elem.IsActive() {
   184  			if len(tables) <= int(elem.TableIndex) {
   185  				return fmt.Errorf("unknown table %d as active element target", elem.TableIndex)
   186  			}
   187  
   188  			t := tables[elem.TableIndex]
   189  			if t.Type != elem.Type {
   190  				return fmt.Errorf("element type mismatch: table has %s but element has %s",
   191  					RefTypeName(t.Type), RefTypeName(elem.Type),
   192  				)
   193  			}
   194  
   195  			// global.get needs to be discovered during initialization
   196  			oc := elem.OffsetExpr.Opcode
   197  			if oc == OpcodeGlobalGet {
   198  				globalIdx, _, err := leb128.LoadUint32(elem.OffsetExpr.Data)
   199  				if err != nil {
   200  					return fmt.Errorf("%s[%d] couldn't read global.get parameter: %w", SectionIDName(SectionIDElement), idx, err)
   201  				} else if err = m.verifyImportGlobalI32(SectionIDElement, idx, globalIdx); err != nil {
   202  					return err
   203  				}
   204  			} else if oc == OpcodeI32Const {
   205  				// Per https://github.com/WebAssembly/spec/blob/wg-1.0/test/core/elem.wast#L117 we must pass if imported
   206  				// table has set its min=0. Per https://github.com/WebAssembly/spec/blob/wg-1.0/test/core/elem.wast#L142, we
   207  				// have to do fail if module-defined min=0.
   208  				if !enabledFeatures.IsEnabled(api.CoreFeatureReferenceTypes) && elem.TableIndex >= importedTableCount {
   209  					// Treat constants as signed as their interpretation is not yet known per /RATIONALE.md
   210  					o, _, err := leb128.LoadInt32(elem.OffsetExpr.Data)
   211  					if err != nil {
   212  						return fmt.Errorf("%s[%d] couldn't read i32.const parameter: %w", SectionIDName(SectionIDElement), idx, err)
   213  					}
   214  					offset := Index(o)
   215  					if err = checkSegmentBounds(t.Min, uint64(initCount)+uint64(offset), idx); err != nil {
   216  						return err
   217  					}
   218  				}
   219  			} else {
   220  				return fmt.Errorf("%s[%d] has an invalid const expression: %s", SectionIDName(SectionIDElement), idx, InstructionName(oc))
   221  			}
   222  		}
   223  	}
   224  	return nil
   225  }
   226  
   227  // buildTable returns TableInstances if the module defines or imports a table.
   228  //   - importedTables: returned as `tables` unmodified.
   229  //   - importedGlobals: include all instantiated, imported globals.
   230  //
   231  // If the result `init` is non-nil, it is the `tableInit` parameter of Engine.NewModuleEngine.
   232  //
   233  // Note: An error is only possible when an ElementSegment.OffsetExpr is out of range of the TableInstance.Min.
   234  func (m *ModuleInstance) buildTables(module *Module, skipBoundCheck bool) (err error) {
   235  	idx := module.ImportTableCount
   236  	for i := range module.TableSection {
   237  		tsec := &module.TableSection[i]
   238  		// The module defining the table is the one that sets its Min/Max etc.
   239  		m.Tables[idx] = &TableInstance{
   240  			References: make([]Reference, tsec.Min), Min: tsec.Min, Max: tsec.Max,
   241  			Type: tsec.Type,
   242  		}
   243  		idx++
   244  	}
   245  
   246  	if !skipBoundCheck {
   247  		for elemI := range module.ElementSection { // Do not loop over the value since elementSegments is a slice of value.
   248  			elem := &module.ElementSection[elemI]
   249  			table := m.Tables[elem.TableIndex]
   250  			var offset uint32
   251  			if elem.OffsetExpr.Opcode == OpcodeGlobalGet {
   252  				// Ignore error as it's already validated.
   253  				globalIdx, _, _ := leb128.LoadUint32(elem.OffsetExpr.Data)
   254  				global := m.Globals[globalIdx]
   255  				offset = uint32(global.Val)
   256  			} else { // i32.const
   257  				// Ignore error as it's already validated.
   258  				o, _, _ := leb128.LoadInt32(elem.OffsetExpr.Data)
   259  				offset = uint32(o)
   260  			}
   261  
   262  			// Check to see if we are out-of-bounds
   263  			initCount := uint64(len(elem.Init))
   264  			if err = checkSegmentBounds(table.Min, uint64(offset)+initCount, Index(elemI)); err != nil {
   265  				return
   266  			}
   267  		}
   268  	}
   269  	return
   270  }
   271  
   272  // checkSegmentBounds fails if the capacity needed for an ElementSegment.Init is larger than limitsType.Min
   273  //
   274  // WebAssembly 1.0 (20191205) doesn't forbid growing to accommodate element segments, and spectests are inconsistent.
   275  // For example, the spectests enforce elements within Table limitsType.Min, but ignore Import.DescTable min. What this
   276  // means is we have to delay offset checks on imported tables until we link to them.
   277  // e.g. https://github.com/WebAssembly/spec/blob/wg-1.0/test/core/elem.wast#L117 wants pass on min=0 for import
   278  // e.g. https://github.com/WebAssembly/spec/blob/wg-1.0/test/core/elem.wast#L142 wants fail on min=0 module-defined
   279  func checkSegmentBounds(min uint32, requireMin uint64, idx Index) error { // uint64 in case offset was set to -1
   280  	if requireMin > uint64(min) {
   281  		return fmt.Errorf("%s[%d].init exceeds min table size", SectionIDName(SectionIDElement), idx)
   282  	}
   283  	return nil
   284  }
   285  
   286  func (m *Module) verifyImportGlobalI32(sectionID SectionID, sectionIdx Index, idx uint32) error {
   287  	ig := uint32(math.MaxUint32) // +1 == 0
   288  	for i := range m.ImportSection {
   289  		imp := &m.ImportSection[i]
   290  		if imp.Type == ExternTypeGlobal {
   291  			ig++
   292  			if ig == idx {
   293  				if imp.DescGlobal.ValType != ValueTypeI32 {
   294  					return fmt.Errorf("%s[%d] (global.get %d): import[%d].global.ValType != i32", SectionIDName(sectionID), sectionIdx, idx, i)
   295  				}
   296  				return nil
   297  			}
   298  		}
   299  	}
   300  	return fmt.Errorf("%s[%d] (global.get %d): out of range of imported globals", SectionIDName(sectionID), sectionIdx, idx)
   301  }
   302  
   303  // Grow appends the `initialRef` by `delta` times into the References slice.
   304  // Returns -1 if the operation is not valid, otherwise the old length of the table.
   305  //
   306  // https://www.w3.org/TR/2022/WD-wasm-core-2-20220419/exec/instructions.html#xref-syntax-instructions-syntax-instr-table-mathsf-table-grow-x
   307  func (t *TableInstance) Grow(delta uint32, initialRef Reference) (currentLen uint32) {
   308  	currentLen = uint32(len(t.References))
   309  	if delta == 0 {
   310  		return
   311  	}
   312  
   313  	if newLen := int64(currentLen) + int64(delta); // adding as 64bit ints to avoid overflow.
   314  	newLen >= math.MaxUint32 || (t.Max != nil && newLen > int64(*t.Max)) {
   315  		return 0xffffffff // = -1 in signed 32-bit integer.
   316  	}
   317  	t.References = append(t.References, make([]uintptr, delta)...)
   318  
   319  	// Uses the copy trick for faster filling the new region with the initial value.
   320  	// https://gist.github.com/taylorza/df2f89d5f9ab3ffd06865062a4cf015d
   321  	newRegion := t.References[currentLen:]
   322  	newRegion[0] = initialRef
   323  	for i := 1; i < len(newRegion); i *= 2 {
   324  		copy(newRegion[i:], newRegion[:i])
   325  	}
   326  	return
   327  }
   328
View as plain text