| 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 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 | |
| 18 | import ( |
| 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. |
| 29 | type intrinsic func(a *analysis, cgn *cgnode) |
| 30 | |
| 31 | // Initialized in explicit init() to defeat (spurious) initialization |
| 32 | // cycle error. |
| 33 | var intrinsicsByName = make(map[string]intrinsic) |
| 34 | |
| 35 | func 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 | func (a *analysis) findIntrinsic(fn *ssa.Function) intrinsic { |
| 163 | // Consult the *Function-keyed cache. |
| 164 | // A cached nil indicates a normal non-intrinsic function. |
| 165 | impl, ok := a.intrinsics[fn] |
| 166 | if !ok { |
| 167 | impl = intrinsicsByName[fn.String()] // may be nil |
| 168 | |
| 169 | if a.isReflect(fn) { |
| 170 | if !a.config.Reflection { |
| 171 | impl = ext۰NoEffect // reflection disabled |
| 172 | } else if impl == nil { |
| 173 | // Ensure all "reflect" code is treated intrinsically. |
| 174 | impl = ext۰NotYetImplemented |
| 175 | } |
| 176 | } else if impl == nil && fn.Pkg != nil && fn.Pkg.Pkg.Path() == "runtime" { |
| 177 | // Ignore "runtime" (except SetFinalizer): |
| 178 | // it has few interesting effects on aliasing |
| 179 | // and is full of unsafe code we can't analyze. |
| 180 | impl = ext۰NoEffect |
| 181 | } |
| 182 | |
| 183 | a.intrinsics[fn] = impl |
| 184 | } |
| 185 | return impl |
| 186 | } |
| 187 | |
| 188 | // isReflect reports whether fn belongs to the "reflect" package. |
| 189 | func (a *analysis) isReflect(fn *ssa.Function) bool { |
| 190 | if a.reflectValueObj == nil { |
| 191 | return false // "reflect" package not loaded |
| 192 | } |
| 193 | reflectPackage := a.reflectValueObj.Pkg() |
| 194 | if fn.Pkg != nil && fn.Pkg.Pkg == reflectPackage { |
| 195 | return true |
| 196 | } |
| 197 | // Synthetic wrappers have a nil Pkg, so they slip through the |
| 198 | // previous check. Check the receiver package. |
| 199 | // TODO(adonovan): should synthetic wrappers have a non-nil Pkg? |
| 200 | if recv := fn.Signature.Recv(); recv != nil { |
| 201 | if named, ok := deref(recv.Type()).(*types.Named); ok { |
| 202 | if named.Obj().Pkg() == reflectPackage { |
| 203 | return true // e.g. wrapper of (reflect.Value).f |
| 204 | } |
| 205 | } |
| 206 | } |
| 207 | return false |
| 208 | } |
| 209 | |
| 210 | // A trivial intrinsic suitable for any function that does not: |
| 211 | // 1) induce aliases between its arguments or any global variables; |
| 212 | // 2) call any functions; or |
| 213 | // 3) create any labels. |
| 214 | // |
| 215 | // Many intrinsics (such as CompareAndSwapInt32) have a fourth kind of |
| 216 | // effect: loading or storing through a pointer. Though these could |
| 217 | // be significant, we deliberately ignore them because they are |
| 218 | // generally not worth the effort. |
| 219 | // |
| 220 | // We sometimes violate condition #3 if the function creates only |
| 221 | // non-function labels, as the control-flow graph is still sound. |
| 222 | func ext۰NoEffect(a *analysis, cgn *cgnode) {} |
| 223 | |
| 224 | func ext۰NotYetImplemented(a *analysis, cgn *cgnode) { |
| 225 | fn := cgn.fn |
| 226 | a.warnf(fn.Pos(), "unsound: intrinsic treatment of %s not yet implemented", fn) |
| 227 | } |
| 228 | |
| 229 | // ---------- func runtime.SetFinalizer(x, f interface{}) ---------- |
| 230 | |
| 231 | // runtime.SetFinalizer(x, f) |
| 232 | type runtimeSetFinalizerConstraint struct { |
| 233 | targets nodeid // (indirect) |
| 234 | f nodeid // (ptr) |
| 235 | x nodeid |
| 236 | } |
| 237 | |
| 238 | func (c *runtimeSetFinalizerConstraint) ptr() nodeid { return c.f } |
| 239 | func (c *runtimeSetFinalizerConstraint) presolve(h *hvn) { |
| 240 | h.markIndirect(onodeid(c.targets), "SetFinalizer.targets") |
| 241 | } |
| 242 | func (c *runtimeSetFinalizerConstraint) renumber(mapping []nodeid) { |
| 243 | c.targets = mapping[c.targets] |
| 244 | c.f = mapping[c.f] |
| 245 | c.x = mapping[c.x] |
| 246 | } |
| 247 | |
| 248 | func (c *runtimeSetFinalizerConstraint) String() string { |
| 249 | return fmt.Sprintf("runtime.SetFinalizer(n%d, n%d)", c.x, c.f) |
| 250 | } |
| 251 | |
| 252 | func (c *runtimeSetFinalizerConstraint) solve(a *analysis, delta *nodeset) { |
| 253 | for _, fObj := range delta.AppendTo(a.deltaSpace) { |
| 254 | tDyn, f, indirect := a.taggedValue(nodeid(fObj)) |
| 255 | if indirect { |
| 256 | // TODO(adonovan): we'll need to implement this |
| 257 | // when we start creating indirect tagged objects. |
| 258 | panic("indirect tagged object") |
| 259 | } |
| 260 | |
| 261 | tSig, ok := tDyn.Underlying().(*types.Signature) |
| 262 | if !ok { |
| 263 | continue // not a function |
| 264 | } |
| 265 | if tSig.Recv() != nil { |
| 266 | panic(tSig) |
| 267 | } |
| 268 | if tSig.Params().Len() != 1 { |
| 269 | continue // not a unary function |
| 270 | } |
| 271 | |
| 272 | // Extract x to tmp. |
| 273 | tx := tSig.Params().At(0).Type() |
| 274 | tmp := a.addNodes(tx, "SetFinalizer.tmp") |
| 275 | a.typeAssert(tx, tmp, c.x, false) |
| 276 | |
| 277 | // Call f(tmp). |
| 278 | a.store(f, tmp, 1, a.sizeof(tx)) |
| 279 | |
| 280 | // Add dynamic call target. |
| 281 | if a.onlineCopy(c.targets, f) { |
| 282 | a.addWork(c.targets) |
| 283 | } |
| 284 | } |
| 285 | } |
| 286 | |
| 287 | func ext۰runtime۰SetFinalizer(a *analysis, cgn *cgnode) { |
| 288 | // This is the shared contour, used for dynamic calls. |
| 289 | targets := a.addOneNode(tInvalid, "SetFinalizer.targets", nil) |
| 290 | cgn.sites = append(cgn.sites, &callsite{targets: targets}) |
| 291 | params := a.funcParams(cgn.obj) |
| 292 | a.addConstraint(&runtimeSetFinalizerConstraint{ |
| 293 | targets: targets, |
| 294 | x: params, |
| 295 | f: params + 1, |
| 296 | }) |
| 297 | } |
| 298 | |
| 299 | // ---------- func time.startTimer(t *runtimeTimer) ---------- |
| 300 | |
| 301 | // time.StartTimer(t) |
| 302 | type timeStartTimerConstraint struct { |
| 303 | targets nodeid // (indirect) |
| 304 | t nodeid // (ptr) |
| 305 | } |
| 306 | |
| 307 | func (c *timeStartTimerConstraint) ptr() nodeid { return c.t } |
| 308 | func (c *timeStartTimerConstraint) presolve(h *hvn) { |
| 309 | h.markIndirect(onodeid(c.targets), "StartTimer.targets") |
| 310 | } |
| 311 | func (c *timeStartTimerConstraint) renumber(mapping []nodeid) { |
| 312 | c.targets = mapping[c.targets] |
| 313 | c.t = mapping[c.t] |
| 314 | } |
| 315 | |
| 316 | func (c *timeStartTimerConstraint) String() string { |
| 317 | return fmt.Sprintf("time.startTimer(n%d)", c.t) |
| 318 | } |
| 319 | |
| 320 | func (c *timeStartTimerConstraint) solve(a *analysis, delta *nodeset) { |
| 321 | for _, tObj := range delta.AppendTo(a.deltaSpace) { |
| 322 | t := nodeid(tObj) |
| 323 | |
| 324 | // We model startTimer as if it was defined thus: |
| 325 | // func startTimer(t *runtimeTimer) { t.f(t.arg) } |
| 326 | |
| 327 | // We hard-code the field offsets of time.runtimeTimer: |
| 328 | // type runtimeTimer struct { |
| 329 | // 0 __identity__ |
| 330 | // 1 i int32 |
| 331 | // 2 when int64 |
| 332 | // 3 period int64 |
| 333 | // 4 f func(int64, interface{}) |
| 334 | // 5 arg interface{} |
| 335 | // } |
| 336 | f := t + 4 |
| 337 | arg := t + 5 |
| 338 | |
| 339 | // store t.arg to t.f.params[0] |
| 340 | // (offset 1 => skip identity) |
| 341 | a.store(f, arg, 1, 1) |
| 342 | |
| 343 | // Add dynamic call target. |
| 344 | if a.onlineCopy(c.targets, f) { |
| 345 | a.addWork(c.targets) |
| 346 | } |
| 347 | } |
| 348 | } |
| 349 | |
| 350 | func ext۰time۰startTimer(a *analysis, cgn *cgnode) { |
| 351 | // This is the shared contour, used for dynamic calls. |
| 352 | targets := a.addOneNode(tInvalid, "startTimer.targets", nil) |
| 353 | cgn.sites = append(cgn.sites, &callsite{targets: targets}) |
| 354 | params := a.funcParams(cgn.obj) |
| 355 | a.addConstraint(&timeStartTimerConstraint{ |
| 356 | targets: targets, |
| 357 | t: params, |
| 358 | }) |
| 359 | } |
| 360 |
Members