New user self-registration is disabled due to spam. For an account please email bugs-admin@lists.llvm.org with your e-mail address and full name.

Bug 39167 - clang-tidy hangs with bugprone-exception-escape check
Summary: clang-tidy hangs with bugprone-exception-escape check
Status: RESOLVED FIXED
Alias: None
Product: clang-tools-extra
Classification: Unclassified
Component: clang-tidy (show other bugs)
Version: unspecified
Hardware: PC All
: P normal
Assignee: Ádám Balogh
URL:
Keywords:
: 39621 (view as bug list)
Depends on:
Blocks:
 
Reported: 2018-10-03 10:58 PDT by Chih-Hung Hsieh
Modified: 2019-01-23 11:00 PST (History)
7 users (show)

See Also:
Fixed By Commit(s):


Attachments
contains test input ref_count.cpp (689.21 KB, application/octet-stream)
2018-10-03 11:05 PDT, Chih-Hung Hsieh
Details
A potential patch, removes the endless loop at least (10.23 KB, patch)
2018-10-05 01:28 PDT, Jonas Toth
Details
Counting of the functions that are analyzed, sorted (997.08 KB, text/x-log)
2018-10-05 01:31 PDT, Jonas Toth
Details
Cleaned patch with actual "fix" (1.85 KB, patch)
2018-10-05 01:35 PDT, Jonas Toth
Details
Debugoutput with patch applied (976.34 KB, text/x-log)
2018-10-05 01:43 PDT, Jonas Toth
Details
Patch Attempt (1.40 KB, patch)
2018-10-11 06:29 PDT, Ádám Balogh
Details
Patch Attempt with Optimized Matcher Expression (2.19 KB, patch)
2018-10-11 06:41 PDT, Ádám Balogh
Details
Optimized Query (1.36 KB, patch)
2018-10-12 01:38 PDT, Ádám Balogh
Details
Counting of the functions with optimized query (227.73 KB, text/plain)
2018-10-12 01:39 PDT, Ádám Balogh
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Chih-Hung Hsieh 2018-10-03 10:58:36 PDT
To reproduce:

(1) Without exception escape check:
clang-tidy -checks=-*,bugprone-*,-bugprone-exception-escape \
/tmp/ref_count.cpp -- \ 
-target x86_64-linux-gnu \
-m64 -g -O0 \
-std=c++11 \
-fno-exceptions

423 warnings generated.
Suppressed 423 warnings (408 in non-user code, 15 with check filters).


(2) Hangs with exception escape check:
clang-tidy -checks=-*,bugprone-* \
/tmp/ref_count.cpp -- \ 
-target x86_64-linux-gnu \
-m64 -g -O0 \
-std=c++11 \
-fno-exceptions

The problem is reproducible with current source and r336997,
which added the exception escape checker.
The problem does not exist in r336996.
Comment 1 Chih-Hung Hsieh 2018-10-03 11:05:37 PDT
Created attachment 20955 [details]
contains test input ref_count.cpp
Comment 2 Jonas Toth 2018-10-04 03:54:58 PDT
Hi Chih-Hung,

thank you for reporting the bug. I can reproduce the problem. The fix is that the check will not do its work when `-fno-exceptions` is provided. 

A patch that solves the issue is here: https://reviews.llvm.org/D52880

Best Jonas
Comment 3 Chih-Hung Hsieh 2018-10-04 09:36:37 PDT
The test case is from one Android open source file.
Although -fno-exceptions is used for most files, some could be compiled with exceptions. I tried the change in D52880 and the test case again.
Now clang-tidy won't hang with `-fno-exceptions` but still hangs without -fno-exceptions.
Comment 4 Jonas Toth 2018-10-04 10:03:08 PDT
Ok, I start creducing the test-file now, if i have something i will upload the file.
Given that this is a massive file, do you know other files that trigger the problem?
Comment 5 Chih-Hung Hsieh 2018-10-04 11:38:18 PDT
Among thousands of AOSP source files, I only found two files failed with this clang-tidy check. So now I disabled this check for those two cases:

https://android-review.googlesource.com/c/platform/bionic/+/774478

https://android-review.googlesource.com/c/platform/frameworks/compile/slang/+/774546


Test input ref_count.cpp is preprocessed output from one of the cases.
The other case has about the same size and also takes about 8 to 10 seconds to run through clang-tidy when bugprone-exception-escape is disabled.
I hope it is easy enough for the writer of that check to find the infinite loop with ref_count.cpp. If there is any fix, I can test it quickly with other AOSP files and the real AOSP compilation flags.
Comment 6 Jonas Toth 2018-10-05 01:25:17 PDT
@adam.balogh I am investigating the issue, but it would help a lot if you take a look at it, too, as you know the internals.

Right now it seems that many functions are analyzed in an endless loop (maybe recursion, direct/indirect?). I added trivial recursive test-cases that did _NOT_ result in an endless loop.

Applying the patch in the attachement does resolve the endless loop, but I can not evaluate if it makes sense. The tests _DO_ work with the patch applied!
Comment 7 Jonas Toth 2018-10-05 01:28:24 PDT
Created attachment 20962 [details]
A potential patch, removes the endless loop at least

This includes a recursive test case and some debug output I used to check. I could not use `Func->getName()` as it failed an assertion, so i just printed the pointer to debug a bit.
Comment 8 Jonas Toth 2018-10-05 01:30:41 PDT
Comment on attachment 20962 [details]
A potential patch, removes the endless loop at least

Please ignore the whitespace changes in the test, clang-format produced them!

The notable change is `llvm::dbgs() << ...` and the added test-case at the end of the test file.
Comment 9 Jonas Toth 2018-10-05 01:31:51 PDT
Created attachment 20963 [details]
Counting of the functions that are analyzed, sorted

This was produced by running the check 5 seconds, so its fast in what its doing :)
Comment 10 Jonas Toth 2018-10-05 01:35:54 PDT
Created attachment 20964 [details]
Cleaned patch with actual "fix"

Sorry, the last patch was too noisy. This one is better
Comment 11 Jonas Toth 2018-10-05 01:43:48 PDT
Created attachment 20965 [details]
Debugoutput with patch applied

Probably not very helpful, but the counts of the analyzed functions go down significantly.
Comment 12 Ádám Balogh 2018-10-08 04:48:04 PDT
Hello!

Of course I will investigate it, I was busy with another task, but I will continue with this one.
Comment 13 Jonas Toth 2018-10-09 02:12:31 PDT
Perfect, is it ok if I assign the bug to you again?
Comment 14 Ádám Balogh 2018-10-11 06:29:15 PDT
Created attachment 20990 [details]
Patch Attempt

I tried the most straightforward thing which is checking whether the function to be analyzed is already in the call stack (see attachment), but it still does not terminate. It seems that it has nothing to do with the recursion.
Comment 15 Ádám Balogh 2018-10-11 06:30:59 PDT
(In reply to Jonas Toth from comment #8)
> Comment on attachment 20962 [details]
> A potential patch, removes the endless loop at least
> 
> Please ignore the whitespace changes in the test, clang-format produced them!
> 
> The notable change is `llvm::dbgs() << ...` and the added test-case at the
> end of the test file.

How did it terminate for you? Even with my patch attempt it seems to run forever, but i do not know, why yet. How many minutes did it take?
Comment 16 Ádám Balogh 2018-10-11 06:41:03 PDT
Created attachment 20991 [details]
Patch Attempt with Optimized Matcher Expression

I optimized the matcher expression to first check whether a function is allowed to throw and only after that check whether it throws. The output became much shorter, but at some point it hangs silently.
Comment 17 Ádám Balogh 2018-10-11 06:46:44 PDT
Oh, `CallStack` is a `SmallSet` so disregard my first attempt. It does not fix anything.
Comment 18 Jonas Toth 2018-10-11 07:13:05 PDT
There is one codepath, that actually removes the analyzed function from the SmallSet, i just commented this line out (see https://bugs.llvm.org/attachment.cgi?id=20964) and it terminated "instantly" (i think 5 seconds but most of it is probably the frontend parsing this big file).

I added some direct and indirect test-cases as well, which did not end up in an endless loop even without the patch. But it might be the case, that this is only triggered in some special recursive setting.
Comment 19 Stephen Hines 2018-10-11 18:32:38 PDT
(In reply to Jonas Toth from comment #18)
> There is one codepath, that actually removes the analyzed function from the
> SmallSet, i just commented this line out (see
> https://bugs.llvm.org/attachment.cgi?id=20964) and it terminated "instantly"
> (i think 5 seconds but most of it is probably the frontend parsing this big
> file).
> 
> I added some direct and indirect test-cases as well, which did not end up in
> an endless loop even without the patch. But it might be the case, that this
> is only triggered in some special recursive setting.

There is a test-case attached at the beginning. We could reduce it down to figure out exactly what causes this problem.
Comment 20 Ádám Balogh 2018-10-12 01:38:10 PDT
Created attachment 20992 [details]
Optimized Query

It seems that optimization of the query is enough.
Comment 21 Ádám Balogh 2018-10-12 01:39:02 PDT
Created attachment 20993 [details]
Counting of the functions with optimized query

The numbers are much lower than before.
Comment 22 Ádám Balogh 2018-10-12 01:43:24 PDT
(In reply to Jonas Toth from comment #18)
> There is one codepath, that actually removes the analyzed function from the
> SmallSet, i just commented this line out (see
> https://bugs.llvm.org/attachment.cgi?id=20964) and it terminated "instantly"
> (i think 5 seconds but most of it is probably the frontend parsing this big
> file).
> 
> I added some direct and indirect test-cases as well, which did not end up in
> an endless loop even without the patch. But it might be the case, that this
> is only triggered in some special recursive setting.

There is probably no endless loop at all, just an insufferable execution time. The analyzed function must be removed from the SmallSet unless we want to loose some true positives: if A calls B then C, but B also calls C, C throws an exception which B catches but not A, and A should not throw then by not removing C from the SmallSet after visiting it after called from B we will not detect the exception it throws and A does not catch. Such an optimization could be done if we changed the whole call graph visit from depth-first to width-first.
Comment 23 Jonas Toth 2018-10-12 06:04:24 PDT
> There is probably no endless loop at all, just an insufferable execution
> time. The analyzed function must be removed from the SmallSet unless we want
> to loose some true positives: if A calls B then C, but B also calls C, C
> throws an exception which B catches but not A, and A should not throw then
> by not removing C from the SmallSet after visiting it after called from B we
> will not detect the exception it throws and A does not catch. Such an
> optimization could be done if we changed the whole call graph visit from
> depth-first to width-first.

I see, that makes sense.


> There is a test-case attached at the beginning. We could reduce it down to figure out exactly what causes this problem.

I was trying to do that. creduced didn't anymore proceed at some and it seemed like a logical issue.
Lets see if Adams fix is actually a fix ;)

@Chih-Hung Hsieh It would be awesome if you could try out the patch https://reviews.llvm.org/D53187 here and check if everything would be fine with it.
Comment 24 Chih-Hung Hsieh 2018-10-12 14:26:12 PDT
With patch D53187, I was able to compile all Android source code.

While it looks like a safe and correct optimization,
I don't think it fixes the important problem of repeated computation
inside throwsException. It now works with Android because Android code
has used little exception specifications, and the failed case I got probably                             has many and deep function calls but not much exception specification in those functions.

If the Func pointer is unique for each function,
earlier debug dump showed that some TypeVec was computed
for the same function too many times:

 276857 Insertion Function 0xca14368
 276857 Insertion Function 0xca14230
 270491 Insertion Function 0xc9b49c8

During this tidy check, isn't a function's TypeVec,
collected by throwsException constant?
If that's the case, the optimal solution should compute TypeVec
only once per function.

The CallStack does not prevent a function being checked multiple times
when it is called many times from another function.
Instead of using a CallStack, could you try to use a map to store
the check status of all Func to TypeVec?
Inside throwsException, if a function 
(1) is not in the map yet, add a 'checking' state to the map, and start checking.
(2) has 'checking' status, return an empty TypeVec, like the current code.
(3) has 'checked' status, return the saved TypeVec in the map.

After checking a function, save its TypeVec in the map and change its status
to 'checked' so it won't be checked again.
Comment 25 Ádám Balogh 2018-10-13 00:16:43 PDT
I think we should go step by step. So the question is whether this first optimization step is sound. I know it is incomplete, but I think it is far better then the current status.

There are two further possible optimizations and I think both should be done. The one is width-first searching for exceptions and ignoring subsequent calls to the same function. (This is based on the fact that an indirect call never throws more exceptions than a direct one.) This ensures that each function is visited only once per checked function (a function that should not throw).

The second possible optimization could be caching thrown (direct and indirect!) exceptions for each visited function globally. This is a bit difficult because matchers are usually stateless.
Comment 26 Ádám Balogh 2018-10-13 01:29:38 PDT
The gain from the two further steps I proposed (and I will do them eventually) are minor compared to this. The matcher expression was definitely wrong.
Comment 27 Jonas Toth 2018-10-13 01:54:10 PDT
Thanks for validating!

The optimizations require a prior refactoring on the matching logic which might take a while. For now this fix is a good start (as Adam stated) and the thousands of checks seem to be gone and now its more max ~150 (or so), which is 2 orders of magnitude less.
Comment 28 Chih-Hung Hsieh 2018-10-15 14:25:33 PDT
As said earlier, I think D53187 is fine for an incremental improvement.

As it showed effectiveness of the filter anyOf(isNoThrow(), ...)
to be done before the filter 'throw(unless(...)),
have you considered embedding the anyOf(...) filter as part of the
'throw' check or ExceptionEscapeCheck?

If all easy-to-check filters are applied before any recursive calls
inside ExceptionEscapeCheck, would there be any difference between
depth-first and breadth-first search? After all, every function that
passes those simple filters must be checked exactly once.
Comment 29 Ádám Balogh 2018-11-12 23:41:06 PST
*** Bug 39621 has been marked as a duplicate of this bug. ***
Comment 30 Jonas Toth 2019-01-23 11:00:04 PST
I am currently refactoring the check a bit and implemented `FunctionDecl` based caching. For your example there is no noticeable performance difference, _maybe_ for other cases it is slightly faster.