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