1-- Copyright 2011 the V8 project authors. All rights reserved.
2-- Redistribution and use in source and binary forms, with or without
3-- modification, are permitted provided that the following conditions are
4-- met:
5--
6--     * Redistributions of source code must retain the above copyright
7--       notice, this list of conditions and the following disclaimer.
8--     * Redistributions in binary form must reproduce the above
9--       copyright notice, this list of conditions and the following
10--       disclaimer in the documentation and/or other materials provided
11--       with the distribution.
12--     * Neither the name of Google Inc. nor the names of its
13--       contributors may be used to endorse or promote products derived
14--       from this software without specific prior written permission.
15--
16-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17-- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18-- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19-- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20-- OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21-- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22-- LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23-- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24-- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25-- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26-- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28-- This is main driver for gcmole tool. See README for more details.
29-- Usage: CLANG_BIN=clang-bin-dir lua tools/gcmole/gcmole.lua [arm|ia32|x64]
30
31local DIR = arg[0]:match("^(.+)/[^/]+$")
32
33local FLAGS = {
34   -- Do not build gcsuspects file and reuse previously generated one.
35   reuse_gcsuspects = false;
36
37   -- Print commands to console before executing them.
38   verbose = false;
39
40   -- Perform dead variable analysis (generates many false positives).
41   -- TODO add some sort of whiteliste to filter out false positives.
42   dead_vars = false;
43
44   -- When building gcsuspects whitelist certain functions as if they
45   -- can be causing GC. Currently used to reduce number of false
46   -- positives in dead variables analysis. See TODO for WHITELIST
47   -- below.
48   whitelist = true;
49}
50local ARGS = {}
51
52for i = 1, #arg do
53   local flag = arg[i]:match "^%-%-([%w_-]+)$"
54   if flag then
55      local no, real_flag = flag:match "^(no)([%w_-]+)$"
56      if real_flag then flag = real_flag end
57
58      flag = flag:gsub("%-", "_")
59      if FLAGS[flag] ~= nil then
60         FLAGS[flag] = (no ~= "no")
61      else
62         error("Unknown flag: " .. flag)
63      end
64   else
65      table.insert(ARGS, arg[i])
66   end
67end
68
69local ARCHS = ARGS[1] and { ARGS[1] } or { 'ia32', 'arm', 'x64', 'arm64' }
70
71local io = require "io"
72local os = require "os"
73
74function log(...)
75   io.stderr:write(string.format(...))
76   io.stderr:write "\n"
77end
78
79-------------------------------------------------------------------------------
80-- Clang invocation
81
82local CLANG_BIN = os.getenv "CLANG_BIN"
83local CLANG_PLUGINS = os.getenv "CLANG_PLUGINS"
84
85if not CLANG_BIN or CLANG_BIN == "" then
86   error "CLANG_BIN not set"
87end
88
89if not CLANG_PLUGINS or CLANG_PLUGINS == "" then
90   CLANG_PLUGINS = DIR
91end
92
93local function MakeClangCommandLine(plugin, plugin_args, triple, arch_define)
94   if plugin_args then
95     for i = 1, #plugin_args do
96        plugin_args[i] = "-Xclang -plugin-arg-" .. plugin
97           .. " -Xclang " .. plugin_args[i]
98     end
99     plugin_args = " " .. table.concat(plugin_args, " ")
100   end
101   return CLANG_BIN .. "/clang++ -std=c++11 -c "
102      .. " -Xclang -load -Xclang " .. CLANG_PLUGINS .. "/libgcmole.so"
103      .. " -Xclang -plugin -Xclang "  .. plugin
104      .. (plugin_args or "")
105      .. " -Xclang -triple -Xclang " .. triple
106      .. " -D" .. arch_define
107      .. " -DENABLE_DEBUGGER_SUPPORT"
108      .. " -DV8_I18N_SUPPORT"
109      .. " -I./"
110      .. " -Ithird_party/icu/source/common"
111      .. " -Ithird_party/icu/source/i18n"
112end
113
114function InvokeClangPluginForEachFile(filenames, cfg, func)
115   local cmd_line = MakeClangCommandLine(cfg.plugin,
116                                         cfg.plugin_args,
117                                         cfg.triple,
118                                         cfg.arch_define)
119   for _, filename in ipairs(filenames) do
120      log("-- %s", filename)
121      local action = cmd_line .. " " .. filename .. " 2>&1"
122      if FLAGS.verbose then print('popen ', action) end
123      local pipe = io.popen(action)
124      func(filename, pipe:lines())
125      local success = pipe:close()
126      if not success then error("Failed to run: " .. action) end
127   end
128end
129
130-------------------------------------------------------------------------------
131-- GYP file parsing
132
133local function ParseGYPFile()
134   local gyp = ""
135   local gyp_files = { "tools/gyp/v8.gyp", "test/cctest/cctest.gyp" }
136   for i = 1, #gyp_files do
137      local f = assert(io.open(gyp_files[i]), "failed to open GYP file")
138      local t = f:read('*a')
139      gyp = gyp .. t
140      f:close()
141   end
142
143   local result = {}
144
145   for condition, sources in
146      gyp:gmatch "'sources': %[.-### gcmole%((.-)%) ###(.-)%]" do
147      if result[condition] == nil then result[condition] = {} end
148      for file in sources:gmatch "'%.%./%.%./src/([^']-%.cc)'" do
149         table.insert(result[condition], "src/" .. file)
150      end
151      for file in sources:gmatch "'(test-[^']-%.cc)'" do
152         table.insert(result[condition], "test/cctest/" .. file)
153      end
154   end
155
156   return result
157end
158
159local function EvaluateCondition(cond, props)
160   if cond == 'all' then return true end
161
162   local p, v = cond:match "(%w+):(%w+)"
163
164   assert(p and v, "failed to parse condition: " .. cond)
165   assert(props[p] ~= nil, "undefined configuration property: " .. p)
166
167   return props[p] == v
168end
169
170local function BuildFileList(sources, props)
171   local list = {}
172   for condition, files in pairs(sources) do
173      if EvaluateCondition(condition, props) then
174         for i = 1, #files do table.insert(list, files[i]) end
175      end
176   end
177   return list
178end
179
180local sources = ParseGYPFile()
181
182local function FilesForArch(arch)
183   return BuildFileList(sources, { os = 'linux',
184                                   arch = arch,
185                                   mode = 'debug',
186                                   simulator = ''})
187end
188
189local mtConfig = {}
190
191mtConfig.__index = mtConfig
192
193local function config (t) return setmetatable(t, mtConfig) end
194
195function mtConfig:extend(t)
196   local e = {}
197   for k, v in pairs(self) do e[k] = v end
198   for k, v in pairs(t) do e[k] = v end
199   return config(e)
200end
201
202local ARCHITECTURES = {
203   ia32 = config { triple = "i586-unknown-linux",
204                   arch_define = "V8_TARGET_ARCH_IA32" },
205   arm = config { triple = "i586-unknown-linux",
206                  arch_define = "V8_TARGET_ARCH_ARM" },
207   x64 = config { triple = "x86_64-unknown-linux",
208                  arch_define = "V8_TARGET_ARCH_X64" },
209   arm64 = config { triple = "x86_64-unknown-linux",
210                    arch_define = "V8_TARGET_ARCH_ARM64" },
211}
212
213-------------------------------------------------------------------------------
214-- GCSuspects Generation
215
216local gc, gc_caused, funcs
217
218local WHITELIST = {
219   -- The following functions call CEntryStub which is always present.
220   "MacroAssembler.*CallExternalReference",
221   "MacroAssembler.*CallRuntime",
222   "CompileCallLoadPropertyWithInterceptor",
223   "CallIC.*GenerateMiss",
224
225   -- DirectCEntryStub is a special stub used on ARM. 
226   -- It is pinned and always present.
227   "DirectCEntryStub.*GenerateCall",  
228
229   -- TODO GCMole currently is sensitive enough to understand that certain 
230   --      functions only cause GC and return Failure simulataneously. 
231   --      Callsites of such functions are safe as long as they are properly 
232   --      check return value and propagate the Failure to the caller.
233   --      It should be possible to extend GCMole to understand this.
234   "Heap.*AllocateFunctionPrototype",
235
236   -- Ignore all StateTag methods.
237   "StateTag",
238
239   -- Ignore printing of elements transition.
240   "PrintElementsTransition"
241};
242
243local function AddCause(name, cause)
244   local t = gc_caused[name]
245   if not t then
246      t = {}
247      gc_caused[name] = t
248   end
249   table.insert(t, cause)
250end
251
252local function resolve(name)
253   local f = funcs[name]
254
255   if not f then
256      f = {}
257      funcs[name] = f
258
259      if name:match "Collect.*Garbage" then
260         gc[name] = true
261         AddCause(name, "<GC>")
262      end
263
264      if FLAGS.whitelist then
265         for i = 1, #WHITELIST do
266            if name:match(WHITELIST[i]) then
267               gc[name] = false
268            end
269         end
270      end
271   end
272
273    return f
274end
275
276local function parse (filename, lines)
277   local scope
278
279   for funcname in lines do
280      if funcname:sub(1, 1) ~= '\t' then
281         resolve(funcname)
282         scope = funcname
283      else
284         local name = funcname:sub(2)
285         resolve(name)[scope] = true
286      end
287   end
288end
289
290local function propagate ()
291   log "** Propagating GC information"
292
293   local function mark(from, callers)
294      for caller, _ in pairs(callers) do
295         if gc[caller] == nil then
296            gc[caller] = true
297            mark(caller, funcs[caller])
298         end
299         AddCause(caller, from)
300      end
301   end
302
303   for funcname, callers in pairs(funcs) do
304      if gc[funcname] then mark(funcname, callers) end
305   end
306end
307
308local function GenerateGCSuspects(arch, files, cfg)
309   -- Reset the global state.
310   gc, gc_caused, funcs = {}, {}, {}
311
312   log ("** Building GC Suspects for %s", arch)
313   InvokeClangPluginForEachFile (files,
314                                 cfg:extend { plugin = "dump-callees" },
315                                 parse)
316
317   propagate()
318
319   local out = assert(io.open("gcsuspects", "w"))
320   for name, value in pairs(gc) do if value then out:write (name, '\n') end end
321   out:close()
322
323   local out = assert(io.open("gccauses", "w"))
324   out:write "GC = {"
325   for name, causes in pairs(gc_caused) do
326      out:write("['", name, "'] = {")
327      for i = 1, #causes do out:write ("'", causes[i], "';") end
328      out:write("};\n")
329   end
330   out:write "}"
331   out:close()
332
333   log ("** GCSuspects generated for %s", arch)
334end
335
336--------------------------------------------------------------------------------
337-- Analysis
338
339local function CheckCorrectnessForArch(arch)
340   local files = FilesForArch(arch)
341   local cfg = ARCHITECTURES[arch]
342
343   if not FLAGS.reuse_gcsuspects then
344      GenerateGCSuspects(arch, files, cfg)
345   end
346
347   local processed_files = 0
348   local errors_found = false
349   local function SearchForErrors(filename, lines)
350      processed_files = processed_files + 1
351      for l in lines do
352         errors_found = errors_found or
353            l:match "^[^:]+:%d+:%d+:" or
354            l:match "error" or
355            l:match "warning"
356         print(l)
357      end
358   end
359
360   log("** Searching for evaluation order problems%s for %s",
361       FLAGS.dead_vars and " and dead variables" or "",
362       arch)
363   local plugin_args
364   if FLAGS.dead_vars then plugin_args = { "--dead-vars" } end
365   InvokeClangPluginForEachFile(files,
366                                cfg:extend { plugin = "find-problems",
367                                             plugin_args = plugin_args },
368                                SearchForErrors)
369   log("** Done processing %d files. %s",
370       processed_files,
371       errors_found and "Errors found" or "No errors found")
372
373   return errors_found
374end
375
376local function SafeCheckCorrectnessForArch(arch)
377   local status, errors = pcall(CheckCorrectnessForArch, arch)
378   if not status then
379      print(string.format("There was an error: %s", errors))
380      errors = true
381   end
382   return errors
383end
384
385local errors = false
386
387for _, arch in ipairs(ARCHS) do
388   if not ARCHITECTURES[arch] then
389      error ("Unknown arch: " .. arch)
390   end
391
392   errors = SafeCheckCorrectnessForArch(arch, report) or errors
393end
394
395os.exit(errors and 1 or 0)
396