search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
27.94k stars 11.53k forks source link

[Coverage] false counter for branch coverage underflows when there's data race #105341

Open whentojump opened 3 weeks ago

whentojump commented 3 weeks ago

Compiler explorer [link](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:1,endLineNumber:30,positionColumn:1,positionLineNumber:30,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'%23include+%3Cstdio.h%3E%0A%23include+%3Cstdlib.h%3E%0A%23include+%3Cpthread.h%3E%0A%0A%23define+NUM_THREADS+10000%0A%0Aint+x%3B%0Aint+y%3B%0A%0Avoid*+f(void*+thread_id)+%7B%0A++++x%2B%2B%3B%0A++++for+(int+i+%3D+0%3B+i+%3C+100%3B+i+%2B%2B)%0A++++++++if+(x+%25+10000)%0A++++++++++++%2B%2By%3B%0A++++pthread_exit(NULL)%3B%0A%7D%0A%0Aint+main()+%7B%0A++++pthread_t+threads%5BNUM_THREADS%5D%3B%0A++++long+t%3B%0A%0A++++for(t+%3D+0%3B+t+%3C+NUM_THREADS%3B+t%2B%2B)%0A++++++++pthread_create(%26threads%5Bt%5D,+NULL,+f,+(void*)t)%3B%0A%0A++++for(t+%3D+0%3B+t+%3C+NUM_THREADS%3B+t%2B%2B)+%0A++++++++pthread_join(threads%5Bt%5D,+NULL)%3B+++%0A%0A++++return+0%3B%0A%7D%0A'),l:'5',n:'1',o:'C%2B%2B+source+%231',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:clang_trunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-fprofile-instr-generate+-fcoverage-mapping+-fprofile-update%3Dsingle',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+(trunk)+(Editor+%231)',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:tool,i:(args:'--show-branches%3Dcount',argsPanelShown:'0',compilerName:'x86-64+clang+(trunk)',editorid:1,fontScale:14,fontUsePx:'0',j:1,monacoEditorHasBeenAutoOpened:'1',monacoEditorOpen:'1',monacoStdin:'1',stdin:'',stdinPanelShown:'1',toolId:llvm-covtrunk,wrap:'1'),l:'5',n:'0',o:'llvm-cov+(clang-only)+x86-64+clang+(trunk)+(Editor+%231,+Compiler+%231)',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4). It's possible to get the following results:

   13|   986k|        if (x % 10000)
  ------------------
  |  Branch (13:13): [True: 986k, False: 18.4E]
  ------------------
   14|   986k|            ++y;

The cause is:

  1. Concurrent counter updates mov -- add -- mov interleave with each other
  2. The counter for "then" clause could be greater than the counter for "if" clause: $C\text{then} > C\text{if}$
  3. $C\text{else} = C\text{if} - C_\text{then} < 0$, resulting in 0xffffffffffffff.. thus 18.4E

I understand we can apply flag -fprofile-update=atomic. But otherwise, in the report we should probably report the negative value as is, which is also gcov's practice:

   997744:   13:        if (x % 10000)
branch  0 taken 997755 (fallthrough)
branch  1 taken -11
   997755:   14:            ++y;

or report 0, which is lcov's practice.

cc @evodius96

evodius96 commented 3 weeks ago

Branch coverage relies on the existing counter intrinsic and counter arithmetic. Wouldn't this race also apply to region coverage?

whentojump commented 3 weeks ago

I see. You are right. Adding an "else" clause to the example can result in

   10|   882k|void g() {
   11|   882k|    if (x % 10000)
  ------------------
  |  Branch (11:9): [True: 882k, False: 18.4E]
  ------------------
   12|   882k|        ++y;
   13|  18.4E|    else 
   14|  18.4E|        --y;  
   15|   882k|}

[Link](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:15,endLineNumber:14,positionColumn:15,positionLineNumber:14,selectionStartColumn:15,selectionStartLineNumber:14,startColumn:15,startLineNumber:14),source:'%23include+%3Cstdio.h%3E%0A%23include+%3Cstdlib.h%3E%0A%23include+%3Cpthread.h%3E%0A%0A%23define+NUM_THREADS+10000%0A%0Aint+x%3B%0Aint+y%3B%0A%0Avoid+g()+%7B%0A++++if+(x+%25+10000)%0A++++++++%2B%2By%3B%0A++++else+%0A++++++++--y%3B++%0A%7D%0A%0Avoid*+f(void*+thread_id)+%7B%0A++++x%2B%2B%3B%0A++++for+(int+i+%3D+0%3B+i+%3C+100%3B+i+%2B%2B)%0A++++++++g()%3B%0A++++pthread_exit(NULL)%3B%0A%7D%0A%0Aint+main()+%7B%0A++++pthread_t+threads%5BNUM_THREADS%5D%3B%0A++++long+t%3B%0A%0A++++for(t+%3D+0%3B+t+%3C+NUM_THREADS%3B+t%2B%2B)%0A++++++++pthread_create(%26threads%5Bt%5D,+NULL,+f,+(void*)t)%3B%0A%0A++++for(t+%3D+0%3B+t+%3C+NUM_THREADS%3B+t%2B%2B)+%0A++++++++pthread_join(threads%5Bt%5D,+NULL)%3B+++%0A%0A++++return+0%3B%0A%7D%0A'),l:'5',n:'1',o:'C%2B%2B+source+%231',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:clang_trunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'1',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-fprofile-instr-generate+-fcoverage-mapping+-fprofile-update%3Dsingle',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+(trunk)+(Editor+%231)',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:tool,i:(args:'--show-branches%3Dcount',argsPanelShown:'0',compilerName:'x86-64+clang+(trunk)',editorid:1,fontScale:14,fontUsePx:'0',j:1,monacoEditorHasBeenAutoOpened:'1',monacoEditorOpen:'1',monacoStdin:'1',stdin:'',stdinPanelShown:'1',toolId:llvm-covtrunk,wrap:'1'),l:'5',n:'0',o:'llvm-cov+(clang-only)+x86-64+clang+(trunk)+(Editor+%231,+Compiler+%231)',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)