gcmole.lua 16 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
-- Copyright 2011 the V8 project authors. All rights reserved.
-- Redistribution and use in source and binary forms, with or without
-- modification, are permitted provided that the following conditions are
-- met:
--
--     * Redistributions of source code must retain the above copyright
--       notice, this list of conditions and the following disclaimer.
--     * Redistributions in binary form must reproduce the above
--       copyright notice, this list of conditions and the following
--       disclaimer in the documentation and/or other materials provided
--       with the distribution.
--     * Neither the name of Google Inc. nor the names of its
--       contributors may be used to endorse or promote products derived
--       from this software without specific prior written permission.
--
-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-- OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-- LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

-- This is main driver for gcmole tool. See README for more details.
-- Usage: CLANG_BIN=clang-bin-dir lua tools/gcmole/gcmole.lua [arm|ia32|x64]

local DIR = arg[0]:match("^(.+)/[^/]+$")
32 33 34 35 36

local FLAGS = {
   -- Do not build gcsuspects file and reuse previously generated one.
   reuse_gcsuspects = false;

37 38 39
   -- Don't use parallel python runner.
   sequential = false;

40 41 42
   -- Print commands to console before executing them.
   verbose = false;

43 44
   -- Perform dead variable analysis.
   dead_vars = true;
45

46 47 48
   -- Enable verbose tracing from the plugin itself.
   verbose_trace = false;

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
   -- When building gcsuspects whitelist certain functions as if they
   -- can be causing GC. Currently used to reduce number of false
   -- positives in dead variables analysis. See TODO for WHITELIST
   -- below.
   whitelist = true;
}
local ARGS = {}

for i = 1, #arg do
   local flag = arg[i]:match "^%-%-([%w_-]+)$"
   if flag then
      local no, real_flag = flag:match "^(no)([%w_-]+)$"
      if real_flag then flag = real_flag end

      flag = flag:gsub("%-", "_")
      if FLAGS[flag] ~= nil then
         FLAGS[flag] = (no ~= "no")
      else
         error("Unknown flag: " .. flag)
      end
   else
      table.insert(ARGS, arg[i])
   end
end

74
local ARCHS = ARGS[1] and { ARGS[1] } or { 'ia32', 'arm', 'x64', 'arm64' }
75 76 77 78 79 80 81 82 83 84 85 86

local io = require "io"
local os = require "os"

function log(...)
   io.stderr:write(string.format(...))
   io.stderr:write "\n"
end

-------------------------------------------------------------------------------
-- Clang invocation

87
local CLANG_BIN = os.getenv "CLANG_BIN"
88
local CLANG_PLUGINS = os.getenv "CLANG_PLUGINS"
89 90 91

if not CLANG_BIN or CLANG_BIN == "" then
   error "CLANG_BIN not set"
92
end
93

94 95 96 97
if not CLANG_PLUGINS or CLANG_PLUGINS == "" then
   CLANG_PLUGINS = DIR
end

98 99
local function MakeClangCommandLine(
      plugin, plugin_args, triple, arch_define, arch_options)
100 101
   if plugin_args then
     for i = 1, #plugin_args do
102 103
        plugin_args[i] = "-Xclang -plugin-arg-" .. plugin
           .. " -Xclang " .. plugin_args[i]
104 105 106
     end
     plugin_args = " " .. table.concat(plugin_args, " ")
   end
107
   return CLANG_BIN .. "/clang++ -std=c++14 -c"
108 109
      .. " -Xclang -load -Xclang " .. CLANG_PLUGINS .. "/libgcmole.so"
      .. " -Xclang -plugin -Xclang "  .. plugin
110
      .. (plugin_args or "")
111
      .. " -Xclang -triple -Xclang " .. triple
112
      .. " -fno-exceptions"
113 114
      .. " -D" .. arch_define
      .. " -DENABLE_DEBUGGER_SUPPORT"
115
      .. " -DV8_INTL_SUPPORT"
116
      .. " -I./"
117
      .. " -Iinclude/"
118
      .. " -Iout/Release/gen"
119 120
      .. " -Ithird_party/icu/source/common"
      .. " -Ithird_party/icu/source/i18n"
121
      .. " " .. arch_options
122 123
end

124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
local function IterTable(t)
  return coroutine.wrap(function ()
    for i, v in ipairs(t) do
      coroutine.yield(v)
    end
  end)
end

local function SplitResults(lines, func)
   -- Splits the output of parallel.py and calls func on each result.
   -- Bails out in case of an error in one of the executions.
   local current = {}
   local filename = ""
   for line in lines do
      local new_file = line:match "^______________ (.*)$"
      local code = line:match "^______________ finish (%d+) ______________$"
      if code then
         if tonumber(code) > 0 then
            log(table.concat(current, "\n"))
            log("Failed to examine " .. filename)
            return false
         end
         log("-- %s", filename)
         func(filename, IterTable(current))
      elseif new_file then
         filename = new_file
         current = {}
      else
         table.insert(current, line)
      end
   end
   return true
end

158 159
function InvokeClangPluginForEachFile(filenames, cfg, func)
   local cmd_line = MakeClangCommandLine(cfg.plugin,
160 161
                                         cfg.plugin_args,
                                         cfg.triple,
162 163
                                         cfg.arch_define,
                                         cfg.arch_options)
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
   if FLAGS.sequential then
      log("** Sequential execution.")
      for _, filename in ipairs(filenames) do
         log("-- %s", filename)
         local action = cmd_line .. " " .. filename .. " 2>&1"
         if FLAGS.verbose then print('popen ', action) end
         local pipe = io.popen(action)
         func(filename, pipe:lines())
         local success = pipe:close()
         if not success then error("Failed to run: " .. action) end
      end
   else
      log("** Parallel execution.")
      local action = "python tools/gcmole/parallel.py \""
         .. cmd_line .. "\" " .. table.concat(filenames, " ")
179
      if FLAGS.verbose then print('popen ', action) end
180
      local pipe = io.popen(action)
181 182 183
      local success = SplitResults(pipe:lines(), func)
      local closed = pipe:close()
      if not (success and closed) then error("Failed to run: " .. action) end
184 185 186 187 188
   end
end

-------------------------------------------------------------------------------

189
local function ParseGNFile(for_test)
190
   local result = {}
191 192 193 194 195 196 197 198 199 200 201
   local gn_files
   if for_test then
      gn_files = {
         { "tools/gcmole/GCMOLE.gn",             '"([^"]-%.cc)"',      ""         }
      }
   else
      gn_files = {
         { "BUILD.gn",             '"([^"]-%.cc)"',      ""         },
         { "test/cctest/BUILD.gn", '"(test-[^"]-%.cc)"', "test/cctest/" }
      }
   end
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221

   for i = 1, #gn_files do
      local filename = gn_files[i][1]
      local pattern = gn_files[i][2]
      local prefix = gn_files[i][3]
      local gn_file = assert(io.open(filename), "failed to open GN file")
      local gn = gn_file:read('*a')
      for condition, sources in
         gn:gmatch "### gcmole%((.-)%) ###(.-)%]" do
         if result[condition] == nil then result[condition] = {} end
         for file in sources:gmatch(pattern) do
            table.insert(result[condition], prefix .. file)
         end
      end
      gn_file:close()
   end

   return result
end

222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
local function EvaluateCondition(cond, props)
   if cond == 'all' then return true end

   local p, v = cond:match "(%w+):(%w+)"

   assert(p and v, "failed to parse condition: " .. cond)
   assert(props[p] ~= nil, "undefined configuration property: " .. p)

   return props[p] == v
end

local function BuildFileList(sources, props)
   local list = {}
   for condition, files in pairs(sources) do
      if EvaluateCondition(condition, props) then
237
         for i = 1, #files do table.insert(list, files[i]) end
238 239 240 241 242
      end
   end
   return list
end

243

244 245
local gn_sources = ParseGNFile(false)
local gn_test_sources = ParseGNFile(true)
246

247
local function FilesForArch(arch)
248 249 250 251
   return BuildFileList(gn_sources, { os = 'linux',
                                      arch = arch,
                                      mode = 'debug',
                                      simulator = ''})
252 253
end

254 255 256 257 258 259 260
local function FilesForTest(arch)
   return BuildFileList(gn_test_sources, { os = 'linux',
                                      arch = arch,
                                      mode = 'debug',
                                      simulator = ''})
end

261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
local mtConfig = {}

mtConfig.__index = mtConfig

local function config (t) return setmetatable(t, mtConfig) end

function mtConfig:extend(t)
   local e = {}
   for k, v in pairs(self) do e[k] = v end
   for k, v in pairs(t) do e[k] = v end
   return config(e)
end

local ARCHITECTURES = {
   ia32 = config { triple = "i586-unknown-linux",
276 277
                   arch_define = "V8_TARGET_ARCH_IA32",
                   arch_options = "-m32" },
278
   arm = config { triple = "i586-unknown-linux",
279 280
                  arch_define = "V8_TARGET_ARCH_ARM",
                  arch_options = "-m32" },
281
   x64 = config { triple = "x86_64-unknown-linux",
282 283
                  arch_define = "V8_TARGET_ARCH_X64",
                  arch_options = "" },
284
   arm64 = config { triple = "x86_64-unknown-linux",
285 286
                    arch_define = "V8_TARGET_ARCH_ARM64",
                    arch_options = "" },
287 288 289
}

-------------------------------------------------------------------------------
290 291 292 293
-- GCSuspects Generation

local gc, gc_caused, funcs

294 295 296 297 298
-- Note that the gcsuspects file lists functions in the form:
--  mangled_name,unmangled_function_name
--
-- This means that we can match just the function name by matching only
-- after a comma.
299 300
local WHITELIST = {
   -- The following functions call CEntryStub which is always present.
301
   "MacroAssembler.*,CallRuntime",
302
   "CompileCallLoadPropertyWithInterceptor",
303
   "CallIC.*,GenerateMiss",
304

305
   -- DirectCEntryStub is a special stub used on ARM.
306
   -- It is pinned and always present.
307
   "DirectCEntryStub.*,GenerateCall",
308

309 310 311
   -- TODO GCMole currently is sensitive enough to understand that certain
   --      functions only cause GC and return Failure simulataneously.
   --      Callsites of such functions are safe as long as they are properly
312 313
   --      check return value and propagate the Failure to the caller.
   --      It should be possible to extend GCMole to understand this.
314
   "Heap.*,TryEvacuateObject",
315 316 317 318 319

   -- Ignore all StateTag methods.
   "StateTag",

   -- Ignore printing of elements transition.
320 321 322 323
   "PrintElementsTransition",

   -- CodeCreateEvent receives AbstractCode (a raw ptr) as an argument.
   "CodeCreateEvent",
324
   "WriteField",
325 326 327 328 329 330 331 332 333 334
};

local function AddCause(name, cause)
   local t = gc_caused[name]
   if not t then
      t = {}
      gc_caused[name] = t
   end
   table.insert(t, cause)
end
335 336 337

local function resolve(name)
   local f = funcs[name]
338 339

   if not f then
340 341
      f = {}
      funcs[name] = f
342

343
      if name:match ",.*Collect.*Garbage" then
344 345 346 347 348 349 350 351 352 353 354
         gc[name] = true
         AddCause(name, "<GC>")
      end

      if FLAGS.whitelist then
         for i = 1, #WHITELIST do
            if name:match(WHITELIST[i]) then
               gc[name] = false
            end
         end
      end
355
   end
356

357 358 359 360 361 362 363 364
    return f
end

local function parse (filename, lines)
   local scope

   for funcname in lines do
      if funcname:sub(1, 1) ~= '\t' then
365 366
         resolve(funcname)
         scope = funcname
367
      else
368 369
         local name = funcname:sub(2)
         resolve(name)[scope] = true
370 371 372 373 374 375 376
      end
   end
end

local function propagate ()
   log "** Propagating GC information"

377 378 379 380 381 382 383
   local function mark(from, callers)
      for caller, _ in pairs(callers) do
         if gc[caller] == nil then
            gc[caller] = true
            mark(caller, funcs[caller])
         end
         AddCause(caller, from)
384 385 386 387
      end
   end

   for funcname, callers in pairs(funcs) do
388
      if gc[funcname] then mark(funcname, callers) end
389 390 391 392
   end
end

local function GenerateGCSuspects(arch, files, cfg)
393 394 395
   -- Reset the global state.
   gc, gc_caused, funcs = {}, {}, {}

396 397 398 399
   log ("** Building GC Suspects for %s", arch)
   InvokeClangPluginForEachFile (files,
                                 cfg:extend { plugin = "dump-callees" },
                                 parse)
400

401 402 403
   propagate()

   local out = assert(io.open("gcsuspects", "w"))
404 405 406 407 408 409 410 411 412 413 414
   for name, value in pairs(gc) do if value then out:write (name, '\n') end end
   out:close()

   local out = assert(io.open("gccauses", "w"))
   out:write "GC = {"
   for name, causes in pairs(gc_caused) do
      out:write("['", name, "'] = {")
      for i = 1, #causes do out:write ("'", causes[i], "';") end
      out:write("};\n")
   end
   out:write "}"
415
   out:close()
416

417 418 419
   log ("** GCSuspects generated for %s", arch)
end

420
--------------------------------------------------------------------------------
421 422
-- Analysis

423 424 425 426 427 428 429
local function CheckCorrectnessForArch(arch, for_test)
   local files
   if for_test then
      files = FilesForTest(arch)
   else
      files = FilesForArch(arch)
   end
430 431
   local cfg = ARCHITECTURES[arch]

432 433 434
   if not FLAGS.reuse_gcsuspects then
      GenerateGCSuspects(arch, files, cfg)
   end
435 436 437

   local processed_files = 0
   local errors_found = false
438
   local output = ""
439 440 441
   local function SearchForErrors(filename, lines)
      processed_files = processed_files + 1
      for l in lines do
442 443 444 445
         errors_found = errors_found or
            l:match "^[^:]+:%d+:%d+:" or
            l:match "error" or
            l:match "warning"
446 447 448 449 450
         if for_test then
            output = output.."\n"..l
         else
            print(l)
         end
451 452 453
      end
   end

454 455 456
   log("** Searching for evaluation order problems%s for %s",
       FLAGS.dead_vars and " and dead variables" or "",
       arch)
457 458 459
   local plugin_args = {}
   if FLAGS.dead_vars then table.insert(plugin_args, "--dead-vars") end
   if FLAGS.verbose_trace then table.insert(plugin_args, '--verbose') end
460
   InvokeClangPluginForEachFile(files,
461 462 463
                                cfg:extend { plugin = "find-problems",
                                             plugin_args = plugin_args },
                                SearchForErrors)
464 465 466 467
   log("** Done processing %d files. %s",
       processed_files,
       errors_found and "Errors found" or "No errors found")

468
   return errors_found, output
469 470
end

471 472
local function SafeCheckCorrectnessForArch(arch, for_test)
   local status, errors, output = pcall(CheckCorrectnessForArch, arch, for_test)
473 474 475 476
   if not status then
      print(string.format("There was an error: %s", errors))
      errors = true
   end
477 478 479
   return errors, output
end

480 481 482 483 484 485 486 487 488 489 490
-- Source: https://stackoverflow.com/a/41515925/1540248
local function StringDifference(str1,str2)
   for i = 1,#str1 do -- Loop over strings
         -- If that character is not equal to its counterpart
         if str1:sub(i,i) ~= str2:sub(i,i) then
            return i --Return that index
         end
   end
   return #str1+1 -- Return the index after where the shorter one ends as fallback.
end

491 492
local function TestRun()
   local errors, output = SafeCheckCorrectnessForArch('x64', true)
493
   if not errors then
494 495
      log("** Test file should produce errors, but none were found. Output:")
      log(output)
496 497
      return false
   end
498 499 500 501 502 503 504

   local filename = "tools/gcmole/test-expectations.txt"
   local exp_file = assert(io.open(filename), "failed to open test expectations file")
   local expectations = exp_file:read('*all')

   if output ~= expectations then
      log("** Output mismatch from running tests. Please run them manually.")
505 506 507 508 509 510 511 512 513 514
      local idx = StringDifference(output, expectations)

      log("Difference at byte "..idx)
      log("Expected: "..expectations:sub(idx-10,idx+10))
      log("Actual: "..output:sub(idx-10,idx+10))

      log("--- Full output ---")
      log(output)
      log("------")

515
      return false
516
   end
517

518 519 520
   log("** Tests ran successfully")
   return true
end
521

522
local errors = not TestRun()
523 524 525

for _, arch in ipairs(ARCHS) do
   if not ARCHITECTURES[arch] then
526
      error("Unknown arch: " .. arch)
527 528
   end

529
   errors = SafeCheckCorrectnessForArch(arch, false) or errors
530 531 532
end

os.exit(errors and 1 or 0)