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 5package pointer 6 7// This package defines the treatment of intrinsics, i.e. library 8// functions requiring special analytical treatment. 9// 10// Most of these are C or assembly functions, but even some Go 11// functions require may special treatment if the analysis completely 12// replaces the implementation of an API such as reflection. 13 14// TODO(adonovan): support a means of writing analytic summaries in 15// the target code, so that users can summarise the effects of their 16// own C functions using a snippet of Go. 17 18import ( 19 "fmt" 20 "go/types" 21 22 "golang.org/x/tools/go/ssa" 23) 24 25// Instances of 'intrinsic' generate analysis constraints for calls to 26// intrinsic functions. 27// Implementations may exploit information from the calling site 28// via cgn.callersite; for shared contours this is nil. 29type intrinsic func(a *analysis, cgn *cgnode) 30 31// Initialized in explicit init() to defeat (spurious) initialization 32// cycle error. 33var intrinsicsByName = make(map[string]intrinsic) 34 35func init() { 36 // Key strings are from Function.String(). 37 // That little dot ۰ is an Arabic zero numeral (U+06F0), 38 // categories [Nd]. 39 for name, fn := range map[string]intrinsic{ 40 // Other packages. 41 "bytes.Equal": ext۰NoEffect, 42 "bytes.IndexByte": ext۰NoEffect, 43 "crypto/aes.decryptBlockAsm": ext۰NoEffect, 44 "crypto/aes.encryptBlockAsm": ext۰NoEffect, 45 "crypto/aes.expandKeyAsm": ext۰NoEffect, 46 "crypto/aes.hasAsm": ext۰NoEffect, 47 "crypto/md5.block": ext۰NoEffect, 48 "crypto/rc4.xorKeyStream": ext۰NoEffect, 49 "crypto/sha1.block": ext۰NoEffect, 50 "crypto/sha256.block": ext۰NoEffect, 51 "hash/crc32.castagnoliSSE42": ext۰NoEffect, 52 "hash/crc32.haveSSE42": ext۰NoEffect, 53 "math.Abs": ext۰NoEffect, 54 "math.Acos": ext۰NoEffect, 55 "math.Asin": ext۰NoEffect, 56 "math.Atan": ext۰NoEffect, 57 "math.Atan2": ext۰NoEffect, 58 "math.Ceil": ext۰NoEffect, 59 "math.Cos": ext۰NoEffect, 60 "math.Dim": ext۰NoEffect, 61 "math.Exp": ext۰NoEffect, 62 "math.Exp2": ext۰NoEffect, 63 "math.Expm1": ext۰NoEffect, 64 "math.Float32bits": ext۰NoEffect, 65 "math.Float32frombits": ext۰NoEffect, 66 "math.Float64bits": ext۰NoEffect, 67 "math.Float64frombits": ext۰NoEffect, 68 "math.Floor": ext۰NoEffect, 69 "math.Frexp": ext۰NoEffect, 70 "math.Hypot": ext۰NoEffect, 71 "math.Ldexp": ext۰NoEffect, 72 "math.Log": ext۰NoEffect, 73 "math.Log10": ext۰NoEffect, 74 "math.Log1p": ext۰NoEffect, 75 "math.Log2": ext۰NoEffect, 76 "math.Max": ext۰NoEffect, 77 "math.Min": ext۰NoEffect, 78 "math.Mod": ext۰NoEffect, 79 "math.Modf": ext۰NoEffect, 80 "math.Remainder": ext۰NoEffect, 81 "math.Sin": ext۰NoEffect, 82 "math.Sincos": ext۰NoEffect, 83 "math.Sqrt": ext۰NoEffect, 84 "math.Tan": ext۰NoEffect, 85 "math.Trunc": ext۰NoEffect, 86 "math/big.addMulVVW": ext۰NoEffect, 87 "math/big.addVV": ext۰NoEffect, 88 "math/big.addVW": ext۰NoEffect, 89 "math/big.bitLen": ext۰NoEffect, 90 "math/big.divWVW": ext۰NoEffect, 91 "math/big.divWW": ext۰NoEffect, 92 "math/big.mulAddVWW": ext۰NoEffect, 93 "math/big.mulWW": ext۰NoEffect, 94 "math/big.shlVU": ext۰NoEffect, 95 "math/big.shrVU": ext۰NoEffect, 96 "math/big.subVV": ext۰NoEffect, 97 "math/big.subVW": ext۰NoEffect, 98 "net.runtime_Semacquire": ext۰NoEffect, 99 "net.runtime_Semrelease": ext۰NoEffect, 100 "net.runtime_pollClose": ext۰NoEffect, 101 "net.runtime_pollOpen": ext۰NoEffect, 102 "net.runtime_pollReset": ext۰NoEffect, 103 "net.runtime_pollServerInit": ext۰NoEffect, 104 "net.runtime_pollSetDeadline": ext۰NoEffect, 105 "net.runtime_pollUnblock": ext۰NoEffect, 106 "net.runtime_pollWait": ext۰NoEffect, 107 "net.runtime_pollWaitCanceled": ext۰NoEffect, 108 "os.epipecheck": ext۰NoEffect, 109 // All other runtime functions are treated as NoEffect. 110 "runtime.SetFinalizer": ext۰runtime۰SetFinalizer, 111 "strings.IndexByte": ext۰NoEffect, 112 "sync.runtime_Semacquire": ext۰NoEffect, 113 "sync.runtime_Semrelease": ext۰NoEffect, 114 "sync.runtime_Syncsemacquire": ext۰NoEffect, 115 "sync.runtime_Syncsemcheck": ext۰NoEffect, 116 "sync.runtime_Syncsemrelease": ext۰NoEffect, 117 "sync.runtime_procPin": ext۰NoEffect, 118 "sync.runtime_procUnpin": ext۰NoEffect, 119 "sync.runtime_registerPool": ext۰NoEffect, 120 "sync/atomic.AddInt32": ext۰NoEffect, 121 "sync/atomic.AddInt64": ext۰NoEffect, 122 "sync/atomic.AddUint32": ext۰NoEffect, 123 "sync/atomic.AddUint64": ext۰NoEffect, 124 "sync/atomic.AddUintptr": ext۰NoEffect, 125 "sync/atomic.CompareAndSwapInt32": ext۰NoEffect, 126 "sync/atomic.CompareAndSwapUint32": ext۰NoEffect, 127 "sync/atomic.CompareAndSwapUint64": ext۰NoEffect, 128 "sync/atomic.CompareAndSwapUintptr": ext۰NoEffect, 129 "sync/atomic.LoadInt32": ext۰NoEffect, 130 "sync/atomic.LoadInt64": ext۰NoEffect, 131 "sync/atomic.LoadPointer": ext۰NoEffect, // ignore unsafe.Pointers 132 "sync/atomic.LoadUint32": ext۰NoEffect, 133 "sync/atomic.LoadUint64": ext۰NoEffect, 134 "sync/atomic.LoadUintptr": ext۰NoEffect, 135 "sync/atomic.StoreInt32": ext۰NoEffect, 136 "sync/atomic.StorePointer": ext۰NoEffect, // ignore unsafe.Pointers 137 "sync/atomic.StoreUint32": ext۰NoEffect, 138 "sync/atomic.StoreUintptr": ext۰NoEffect, 139 "syscall.Close": ext۰NoEffect, 140 "syscall.Exit": ext۰NoEffect, 141 "syscall.Getpid": ext۰NoEffect, 142 "syscall.Getwd": ext۰NoEffect, 143 "syscall.Kill": ext۰NoEffect, 144 "syscall.RawSyscall": ext۰NoEffect, 145 "syscall.RawSyscall6": ext۰NoEffect, 146 "syscall.Syscall": ext۰NoEffect, 147 "syscall.Syscall6": ext۰NoEffect, 148 "syscall.runtime_AfterFork": ext۰NoEffect, 149 "syscall.runtime_BeforeFork": ext۰NoEffect, 150 "syscall.setenv_c": ext۰NoEffect, 151 "time.Sleep": ext۰NoEffect, 152 "time.now": ext۰NoEffect, 153 "time.startTimer": ext۰time۰startTimer, 154 "time.stopTimer": ext۰NoEffect, 155 } { 156 intrinsicsByName[name] = fn 157 } 158} 159 160// findIntrinsic returns the constraint generation function for an 161// intrinsic function fn, or nil if the function should be handled normally. 162// 163func (a *analysis) findIntrinsic(fn *ssa.Function) intrinsic { 164 // Consult the *Function-keyed cache. 165 // A cached nil indicates a normal non-intrinsic function. 166 impl, ok := a.intrinsics[fn] 167 if !ok { 168 impl = intrinsicsByName[fn.String()] // may be nil 169 170 if a.isReflect(fn) { 171 if !a.config.Reflection { 172 impl = ext۰NoEffect // reflection disabled 173 } else if impl == nil { 174 // Ensure all "reflect" code is treated intrinsically. 175 impl = ext۰NotYetImplemented 176 } 177 } else if impl == nil && fn.Pkg != nil && fn.Pkg.Pkg.Path() == "runtime" { 178 // Ignore "runtime" (except SetFinalizer): 179 // it has few interesting effects on aliasing 180 // and is full of unsafe code we can't analyze. 181 impl = ext۰NoEffect 182 } 183 184 a.intrinsics[fn] = impl 185 } 186 return impl 187} 188 189// isReflect reports whether fn belongs to the "reflect" package. 190func (a *analysis) isReflect(fn *ssa.Function) bool { 191 if a.reflectValueObj == nil { 192 return false // "reflect" package not loaded 193 } 194 reflectPackage := a.reflectValueObj.Pkg() 195 if fn.Pkg != nil && fn.Pkg.Pkg == reflectPackage { 196 return true 197 } 198 // Synthetic wrappers have a nil Pkg, so they slip through the 199 // previous check. Check the receiver package. 200 // TODO(adonovan): should synthetic wrappers have a non-nil Pkg? 201 if recv := fn.Signature.Recv(); recv != nil { 202 if named, ok := deref(recv.Type()).(*types.Named); ok { 203 if named.Obj().Pkg() == reflectPackage { 204 return true // e.g. wrapper of (reflect.Value).f 205 } 206 } 207 } 208 return false 209} 210 211// A trivial intrinsic suitable for any function that does not: 212// 1) induce aliases between its arguments or any global variables; 213// 2) call any functions; or 214// 3) create any labels. 215// 216// Many intrinsics (such as CompareAndSwapInt32) have a fourth kind of 217// effect: loading or storing through a pointer. Though these could 218// be significant, we deliberately ignore them because they are 219// generally not worth the effort. 220// 221// We sometimes violate condition #3 if the function creates only 222// non-function labels, as the control-flow graph is still sound. 223// 224func ext۰NoEffect(a *analysis, cgn *cgnode) {} 225 226func ext۰NotYetImplemented(a *analysis, cgn *cgnode) { 227 fn := cgn.fn 228 a.warnf(fn.Pos(), "unsound: intrinsic treatment of %s not yet implemented", fn) 229} 230 231// ---------- func runtime.SetFinalizer(x, f interface{}) ---------- 232 233// runtime.SetFinalizer(x, f) 234type runtimeSetFinalizerConstraint struct { 235 targets nodeid // (indirect) 236 f nodeid // (ptr) 237 x nodeid 238} 239 240func (c *runtimeSetFinalizerConstraint) ptr() nodeid { return c.f } 241func (c *runtimeSetFinalizerConstraint) presolve(h *hvn) { 242 h.markIndirect(onodeid(c.targets), "SetFinalizer.targets") 243} 244func (c *runtimeSetFinalizerConstraint) renumber(mapping []nodeid) { 245 c.targets = mapping[c.targets] 246 c.f = mapping[c.f] 247 c.x = mapping[c.x] 248} 249 250func (c *runtimeSetFinalizerConstraint) String() string { 251 return fmt.Sprintf("runtime.SetFinalizer(n%d, n%d)", c.x, c.f) 252} 253 254func (c *runtimeSetFinalizerConstraint) solve(a *analysis, delta *nodeset) { 255 for _, fObj := range delta.AppendTo(a.deltaSpace) { 256 tDyn, f, indirect := a.taggedValue(nodeid(fObj)) 257 if indirect { 258 // TODO(adonovan): we'll need to implement this 259 // when we start creating indirect tagged objects. 260 panic("indirect tagged object") 261 } 262 263 tSig, ok := tDyn.Underlying().(*types.Signature) 264 if !ok { 265 continue // not a function 266 } 267 if tSig.Recv() != nil { 268 panic(tSig) 269 } 270 if tSig.Params().Len() != 1 { 271 continue // not a unary function 272 } 273 274 // Extract x to tmp. 275 tx := tSig.Params().At(0).Type() 276 tmp := a.addNodes(tx, "SetFinalizer.tmp") 277 a.typeAssert(tx, tmp, c.x, false) 278 279 // Call f(tmp). 280 a.store(f, tmp, 1, a.sizeof(tx)) 281 282 // Add dynamic call target. 283 if a.onlineCopy(c.targets, f) { 284 a.addWork(c.targets) 285 } 286 } 287} 288 289func ext۰runtime۰SetFinalizer(a *analysis, cgn *cgnode) { 290 // This is the shared contour, used for dynamic calls. 291 targets := a.addOneNode(tInvalid, "SetFinalizer.targets", nil) 292 cgn.sites = append(cgn.sites, &callsite{targets: targets}) 293 params := a.funcParams(cgn.obj) 294 a.addConstraint(&runtimeSetFinalizerConstraint{ 295 targets: targets, 296 x: params, 297 f: params + 1, 298 }) 299} 300 301// ---------- func time.startTimer(t *runtimeTimer) ---------- 302 303// time.StartTimer(t) 304type timeStartTimerConstraint struct { 305 targets nodeid // (indirect) 306 t nodeid // (ptr) 307} 308 309func (c *timeStartTimerConstraint) ptr() nodeid { return c.t } 310func (c *timeStartTimerConstraint) presolve(h *hvn) { 311 h.markIndirect(onodeid(c.targets), "StartTimer.targets") 312} 313func (c *timeStartTimerConstraint) renumber(mapping []nodeid) { 314 c.targets = mapping[c.targets] 315 c.t = mapping[c.t] 316} 317 318func (c *timeStartTimerConstraint) String() string { 319 return fmt.Sprintf("time.startTimer(n%d)", c.t) 320} 321 322func (c *timeStartTimerConstraint) solve(a *analysis, delta *nodeset) { 323 for _, tObj := range delta.AppendTo(a.deltaSpace) { 324 t := nodeid(tObj) 325 326 // We model startTimer as if it was defined thus: 327 // func startTimer(t *runtimeTimer) { t.f(t.arg) } 328 329 // We hard-code the field offsets of time.runtimeTimer: 330 // type runtimeTimer struct { 331 // 0 __identity__ 332 // 1 i int32 333 // 2 when int64 334 // 3 period int64 335 // 4 f func(int64, interface{}) 336 // 5 arg interface{} 337 // } 338 f := t + 4 339 arg := t + 5 340 341 // store t.arg to t.f.params[0] 342 // (offset 1 => skip identity) 343 a.store(f, arg, 1, 1) 344 345 // Add dynamic call target. 346 if a.onlineCopy(c.targets, f) { 347 a.addWork(c.targets) 348 } 349 } 350} 351 352func ext۰time۰startTimer(a *analysis, cgn *cgnode) { 353 // This is the shared contour, used for dynamic calls. 354 targets := a.addOneNode(tInvalid, "startTimer.targets", nil) 355 cgn.sites = append(cgn.sites, &callsite{targets: targets}) 356 params := a.funcParams(cgn.obj) 357 a.addConstraint(&timeStartTimerConstraint{ 358 targets: targets, 359 t: params, 360 }) 361} 362