podman

1
// Copyright 2013 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 obj
6

7
import (
8
	"github.com/twitchyliquid64/golang-asm/goobj"
9
	"encoding/binary"
10
	"log"
11
)
12

13
// funcpctab writes to dst a pc-value table mapping the code in func to the values
14
// returned by valfunc parameterized by arg. The invocation of valfunc to update the
15
// current value is, for each p,
16
//
17
//	val = valfunc(func, val, p, 0, arg);
18
//	record val as value at p->pc;
19
//	val = valfunc(func, val, p, 1, arg);
20
//
21
// where func is the function, val is the current value, p is the instruction being
22
// considered, and arg can be used to further parameterize valfunc.
23
func funcpctab(ctxt *Link, dst *Pcdata, func_ *LSym, desc string, valfunc func(*Link, *LSym, int32, *Prog, int32, interface{}) int32, arg interface{}) {
24
	dbg := desc == ctxt.Debugpcln
25

26
	dst.P = dst.P[:0]
27

28
	if dbg {
29
		ctxt.Logf("funcpctab %s [valfunc=%s]\n", func_.Name, desc)
30
	}
31

32
	val := int32(-1)
33
	oldval := val
34
	if func_.Func.Text == nil {
35
		return
36
	}
37

38
	pc := func_.Func.Text.Pc
39

40
	if dbg {
41
		ctxt.Logf("%6x %6d %v\n", uint64(pc), val, func_.Func.Text)
42
	}
43

44
	buf := make([]byte, binary.MaxVarintLen32)
45
	started := false
46
	for p := func_.Func.Text; p != nil; p = p.Link {
47
		// Update val. If it's not changing, keep going.
48
		val = valfunc(ctxt, func_, val, p, 0, arg)
49

50
		if val == oldval && started {
51
			val = valfunc(ctxt, func_, val, p, 1, arg)
52
			if dbg {
53
				ctxt.Logf("%6x %6s %v\n", uint64(p.Pc), "", p)
54
			}
55
			continue
56
		}
57

58
		// If the pc of the next instruction is the same as the
59
		// pc of this instruction, this instruction is not a real
60
		// instruction. Keep going, so that we only emit a delta
61
		// for a true instruction boundary in the program.
62
		if p.Link != nil && p.Link.Pc == p.Pc {
63
			val = valfunc(ctxt, func_, val, p, 1, arg)
64
			if dbg {
65
				ctxt.Logf("%6x %6s %v\n", uint64(p.Pc), "", p)
66
			}
67
			continue
68
		}
69

70
		// The table is a sequence of (value, pc) pairs, where each
71
		// pair states that the given value is in effect from the current position
72
		// up to the given pc, which becomes the new current position.
73
		// To generate the table as we scan over the program instructions,
74
		// we emit a "(value" when pc == func->value, and then
75
		// each time we observe a change in value we emit ", pc) (value".
76
		// When the scan is over, we emit the closing ", pc)".
77
		//
78
		// The table is delta-encoded. The value deltas are signed and
79
		// transmitted in zig-zag form, where a complement bit is placed in bit 0,
80
		// and the pc deltas are unsigned. Both kinds of deltas are sent
81
		// as variable-length little-endian base-128 integers,
82
		// where the 0x80 bit indicates that the integer continues.
83

84
		if dbg {
85
			ctxt.Logf("%6x %6d %v\n", uint64(p.Pc), val, p)
86
		}
87

88
		if started {
89
			pcdelta := (p.Pc - pc) / int64(ctxt.Arch.MinLC)
90
			n := binary.PutUvarint(buf, uint64(pcdelta))
91
			dst.P = append(dst.P, buf[:n]...)
92
			pc = p.Pc
93
		}
94

95
		delta := val - oldval
96
		n := binary.PutVarint(buf, int64(delta))
97
		dst.P = append(dst.P, buf[:n]...)
98
		oldval = val
99
		started = true
100
		val = valfunc(ctxt, func_, val, p, 1, arg)
101
	}
102

103
	if started {
104
		if dbg {
105
			ctxt.Logf("%6x done\n", uint64(func_.Func.Text.Pc+func_.Size))
106
		}
107
		v := (func_.Size - pc) / int64(ctxt.Arch.MinLC)
108
		if v < 0 {
109
			ctxt.Diag("negative pc offset: %v", v)
110
		}
111
		n := binary.PutUvarint(buf, uint64(v))
112
		dst.P = append(dst.P, buf[:n]...)
113
		// add terminating varint-encoded 0, which is just 0
114
		dst.P = append(dst.P, 0)
115
	}
116

117
	if dbg {
118
		ctxt.Logf("wrote %d bytes to %p\n", len(dst.P), dst)
119
		for _, p := range dst.P {
120
			ctxt.Logf(" %02x", p)
121
		}
122
		ctxt.Logf("\n")
123
	}
124
}
125

126
// pctofileline computes either the file number (arg == 0)
127
// or the line number (arg == 1) to use at p.
128
// Because p.Pos applies to p, phase == 0 (before p)
129
// takes care of the update.
130
func pctofileline(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
131
	if p.As == ATEXT || p.As == ANOP || p.Pos.Line() == 0 || phase == 1 {
132
		return oldval
133
	}
134
	f, l := getFileIndexAndLine(ctxt, p.Pos)
135
	if arg == nil {
136
		return l
137
	}
138
	pcln := arg.(*Pcln)
139
	pcln.UsedFiles[goobj.CUFileIndex(f)] = struct{}{}
140
	return int32(f)
141
}
142

143
// pcinlineState holds the state used to create a function's inlining
144
// tree and the PC-value table that maps PCs to nodes in that tree.
145
type pcinlineState struct {
146
	globalToLocal map[int]int
147
	localTree     InlTree
148
}
149

150
// addBranch adds a branch from the global inlining tree in ctxt to
151
// the function's local inlining tree, returning the index in the local tree.
152
func (s *pcinlineState) addBranch(ctxt *Link, globalIndex int) int {
153
	if globalIndex < 0 {
154
		return -1
155
	}
156

157
	localIndex, ok := s.globalToLocal[globalIndex]
158
	if ok {
159
		return localIndex
160
	}
161

162
	// Since tracebacks don't include column information, we could
163
	// use one node for multiple calls of the same function on the
164
	// same line (e.g., f(x) + f(y)). For now, we use one node for
165
	// each inlined call.
166
	call := ctxt.InlTree.nodes[globalIndex]
167
	call.Parent = s.addBranch(ctxt, call.Parent)
168
	localIndex = len(s.localTree.nodes)
169
	s.localTree.nodes = append(s.localTree.nodes, call)
170
	s.globalToLocal[globalIndex] = localIndex
171
	return localIndex
172
}
173

174
func (s *pcinlineState) setParentPC(ctxt *Link, globalIndex int, pc int32) {
175
	localIndex, ok := s.globalToLocal[globalIndex]
176
	if !ok {
177
		// We know where to unwind to when we need to unwind a body identified
178
		// by globalIndex. But there may be no instructions generated by that
179
		// body (it's empty, or its instructions were CSEd with other things, etc.).
180
		// In that case, we don't need an unwind entry.
181
		// TODO: is this really right? Seems to happen a whole lot...
182
		return
183
	}
184
	s.localTree.setParentPC(localIndex, pc)
185
}
186

187
// pctoinline computes the index into the local inlining tree to use at p.
188
// If p is not the result of inlining, pctoinline returns -1. Because p.Pos
189
// applies to p, phase == 0 (before p) takes care of the update.
190
func (s *pcinlineState) pctoinline(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
191
	if phase == 1 {
192
		return oldval
193
	}
194

195
	posBase := ctxt.PosTable.Pos(p.Pos).Base()
196
	if posBase == nil {
197
		return -1
198
	}
199

200
	globalIndex := posBase.InliningIndex()
201
	if globalIndex < 0 {
202
		return -1
203
	}
204

205
	if s.globalToLocal == nil {
206
		s.globalToLocal = make(map[int]int)
207
	}
208

209
	return int32(s.addBranch(ctxt, globalIndex))
210
}
211

212
// pctospadj computes the sp adjustment in effect.
213
// It is oldval plus any adjustment made by p itself.
214
// The adjustment by p takes effect only after p, so we
215
// apply the change during phase == 1.
216
func pctospadj(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
217
	if oldval == -1 { // starting
218
		oldval = 0
219
	}
220
	if phase == 0 {
221
		return oldval
222
	}
223
	if oldval+p.Spadj < -10000 || oldval+p.Spadj > 1100000000 {
224
		ctxt.Diag("overflow in spadj: %d + %d = %d", oldval, p.Spadj, oldval+p.Spadj)
225
		ctxt.DiagFlush()
226
		log.Fatalf("bad code")
227
	}
228

229
	return oldval + p.Spadj
230
}
231

232
// pctopcdata computes the pcdata value in effect at p.
233
// A PCDATA instruction sets the value in effect at future
234
// non-PCDATA instructions.
235
// Since PCDATA instructions have no width in the final code,
236
// it does not matter which phase we use for the update.
237
func pctopcdata(ctxt *Link, sym *LSym, oldval int32, p *Prog, phase int32, arg interface{}) int32 {
238
	if phase == 0 || p.As != APCDATA || p.From.Offset != int64(arg.(uint32)) {
239
		return oldval
240
	}
241
	if int64(int32(p.To.Offset)) != p.To.Offset {
242
		ctxt.Diag("overflow in PCDATA instruction: %v", p)
243
		ctxt.DiagFlush()
244
		log.Fatalf("bad code")
245
	}
246

247
	return int32(p.To.Offset)
248
}
249

250
func linkpcln(ctxt *Link, cursym *LSym) {
251
	pcln := &cursym.Func.Pcln
252
	pcln.UsedFiles = make(map[goobj.CUFileIndex]struct{})
253

254
	npcdata := 0
255
	nfuncdata := 0
256
	for p := cursym.Func.Text; p != nil; p = p.Link {
257
		// Find the highest ID of any used PCDATA table. This ignores PCDATA table
258
		// that consist entirely of "-1", since that's the assumed default value.
259
		//   From.Offset is table ID
260
		//   To.Offset is data
261
		if p.As == APCDATA && p.From.Offset >= int64(npcdata) && p.To.Offset != -1 { // ignore -1 as we start at -1, if we only see -1, nothing changed
262
			npcdata = int(p.From.Offset + 1)
263
		}
264
		// Find the highest ID of any FUNCDATA table.
265
		//   From.Offset is table ID
266
		if p.As == AFUNCDATA && p.From.Offset >= int64(nfuncdata) {
267
			nfuncdata = int(p.From.Offset + 1)
268
		}
269
	}
270

271
	pcln.Pcdata = make([]Pcdata, npcdata)
272
	pcln.Pcdata = pcln.Pcdata[:npcdata]
273
	pcln.Funcdata = make([]*LSym, nfuncdata)
274
	pcln.Funcdataoff = make([]int64, nfuncdata)
275
	pcln.Funcdataoff = pcln.Funcdataoff[:nfuncdata]
276

277
	funcpctab(ctxt, &pcln.Pcsp, cursym, "pctospadj", pctospadj, nil)
278
	funcpctab(ctxt, &pcln.Pcfile, cursym, "pctofile", pctofileline, pcln)
279
	funcpctab(ctxt, &pcln.Pcline, cursym, "pctoline", pctofileline, nil)
280

281
	// Check that all the Progs used as inline markers are still reachable.
282
	// See issue #40473.
283
	inlMarkProgs := make(map[*Prog]struct{}, len(cursym.Func.InlMarks))
284
	for _, inlMark := range cursym.Func.InlMarks {
285
		inlMarkProgs[inlMark.p] = struct{}{}
286
	}
287
	for p := cursym.Func.Text; p != nil; p = p.Link {
288
		if _, ok := inlMarkProgs[p]; ok {
289
			delete(inlMarkProgs, p)
290
		}
291
	}
292
	if len(inlMarkProgs) > 0 {
293
		ctxt.Diag("one or more instructions used as inline markers are no longer reachable")
294
	}
295

296
	pcinlineState := new(pcinlineState)
297
	funcpctab(ctxt, &pcln.Pcinline, cursym, "pctoinline", pcinlineState.pctoinline, nil)
298
	for _, inlMark := range cursym.Func.InlMarks {
299
		pcinlineState.setParentPC(ctxt, int(inlMark.id), int32(inlMark.p.Pc))
300
	}
301
	pcln.InlTree = pcinlineState.localTree
302
	if ctxt.Debugpcln == "pctoinline" && len(pcln.InlTree.nodes) > 0 {
303
		ctxt.Logf("-- inlining tree for %s:\n", cursym)
304
		dumpInlTree(ctxt, pcln.InlTree)
305
		ctxt.Logf("--\n")
306
	}
307

308
	// tabulate which pc and func data we have.
309
	havepc := make([]uint32, (npcdata+31)/32)
310
	havefunc := make([]uint32, (nfuncdata+31)/32)
311
	for p := cursym.Func.Text; p != nil; p = p.Link {
312
		if p.As == AFUNCDATA {
313
			if (havefunc[p.From.Offset/32]>>uint64(p.From.Offset%32))&1 != 0 {
314
				ctxt.Diag("multiple definitions for FUNCDATA $%d", p.From.Offset)
315
			}
316
			havefunc[p.From.Offset/32] |= 1 << uint64(p.From.Offset%32)
317
		}
318

319
		if p.As == APCDATA && p.To.Offset != -1 {
320
			havepc[p.From.Offset/32] |= 1 << uint64(p.From.Offset%32)
321
		}
322
	}
323

324
	// pcdata.
325
	for i := 0; i < npcdata; i++ {
326
		if (havepc[i/32]>>uint(i%32))&1 == 0 {
327
			continue
328
		}
329
		funcpctab(ctxt, &pcln.Pcdata[i], cursym, "pctopcdata", pctopcdata, interface{}(uint32(i)))
330
	}
331

332
	// funcdata
333
	if nfuncdata > 0 {
334
		for p := cursym.Func.Text; p != nil; p = p.Link {
335
			if p.As != AFUNCDATA {
336
				continue
337
			}
338
			i := int(p.From.Offset)
339
			pcln.Funcdataoff[i] = p.To.Offset
340
			if p.To.Type != TYPE_CONST {
341
				// TODO: Dedup.
342
				//funcdata_bytes += p->to.sym->size;
343
				pcln.Funcdata[i] = p.To.Sym
344
			}
345
		}
346
	}
347
}
348

349
// PCIter iterates over encoded pcdata tables.
350
type PCIter struct {
351
	p       []byte
352
	PC      uint32
353
	NextPC  uint32
354
	PCScale uint32
355
	Value   int32
356
	start   bool
357
	Done    bool
358
}
359

360
// newPCIter creates a PCIter with a scale factor for the PC step size.
361
func NewPCIter(pcScale uint32) *PCIter {
362
	it := new(PCIter)
363
	it.PCScale = pcScale
364
	return it
365
}
366

367
// Next advances it to the Next pc.
368
func (it *PCIter) Next() {
369
	it.PC = it.NextPC
370
	if it.Done {
371
		return
372
	}
373
	if len(it.p) == 0 {
374
		it.Done = true
375
		return
376
	}
377

378
	// Value delta
379
	val, n := binary.Varint(it.p)
380
	if n <= 0 {
381
		log.Fatalf("bad Value varint in pciterNext: read %v", n)
382
	}
383
	it.p = it.p[n:]
384

385
	if val == 0 && !it.start {
386
		it.Done = true
387
		return
388
	}
389

390
	it.start = false
391
	it.Value += int32(val)
392

393
	// pc delta
394
	pc, n := binary.Uvarint(it.p)
395
	if n <= 0 {
396
		log.Fatalf("bad pc varint in pciterNext: read %v", n)
397
	}
398
	it.p = it.p[n:]
399

400
	it.NextPC = it.PC + uint32(pc)*it.PCScale
401
}
402

403
// init prepares it to iterate over p,
404
// and advances it to the first pc.
405
func (it *PCIter) Init(p []byte) {
406
	it.p = p
407
	it.PC = 0
408
	it.NextPC = 0
409
	it.Value = -1
410
	it.start = true
411
	it.Done = false
412
	it.Next()
413
}
414