Typical Cases #
Detect races in an open source project Memcached #
This tutorial assumes that you have gone through one of the three starter case tutorials and have successfully run Coderrect.
Coderrect detected 3 new races (2 of them were confirmed) in memcached. To detect the reported bugs using coderrect, download and checkout the buggy version of memcached using the following commands.
$ git clone https://github.com/memcached/memcached.git $ cd memcached $ git checkout 82029ecc9b3dd0f57b3f9ab9761f44714cceed6f
Detect the race
- Build memcached using coderrect
# install dependencies $ apt install libevent-dev # configure memcached $ ./autogen.sh && ./configure # build memcached using coderrect $ coderrect -t make
The coderrect -t make command will compile and analyze the program automatically.
- Detect races using coderrect
After compilation, coderrect automatically detects and lists all the potential targets to analyzed as follows:
1) timedrun 2) sizes 3) memcached-debug 4) memcached 5) testapp Please select binaries by entering their ordinal numbers (e.g. 1,2,6):
Select 3) memcached-debug as the target to detect races on the debug version of memcached.
Interpret the Results
The coderrect tool generates a comprehensive report that can be viewed in a browser.
HTML Report
To view the full report, open ‘.coderrect/report/index.html‘ in your browser.
The HTML report looks like the following picture.
Terminal Report
To get a quick overview of the detected races, coderrect can also report a summary of the most interesting races in the terminal (with -t flag, checkout all coderrect options). The terminal races report looks like the following:
==== Found a race between:
line 162, column 5 in crawler.c AND line 1464, column 16 in items.c
Shared variable:
at line 1577 of items.c
1577| calloc(1, sizeof(struct crawler_expired_data));
Thread 1:
160| pthread_mutex_lock(&d->lock);
161| d->crawlerstats[slab_cls].end_time = current_time;
>162| d->crawlerstats[slab_cls].run_complete = true;
163| pthread_mutex_unlock(&d->lock);
164|}
>>>Stacktrace:
>>>pthread_create [crawler.c:505]
>>> item_crawler_thread [crawler.c:505]
>>> lru_crawler_class_done [crawler.c:378]
>>> crawler_expired_doneclass [crawler.c:350]
Thread 2:
1462| crawlerstats_t *s = &cdata->crawlerstats[i];
1463| /* We've not successfully kicked off a crawl yet. */
>1464| if (s->run_complete) {
1465| char *lru_name = "na";
1466| pthread_mutex_lock(&cdata->lock);
>>>Stacktrace:
>>>pthread_create [items.c:1703]
>>> lru_maintainer_thread [items.c:1703]
>>> lru_maintainer_crawler_check [items.c:1647]
Each reported race starts with a summary of where the race was found.
==== Found a race between: line 162, column 5 in crawler.c AND line 1464, column 16 in items.c
Next the report shows the name and location of the variable on which the race occurs.
Shared variable: at line 1577 of items.c 1577| calloc(1, sizeof(struct crawler_expired_data));
For example, the above result shows that the race occurs on the variable allocated at line 1577 in items.c file.
Next the tool reports information about the two unsynchronized accesses to the shared variable. For each of the two accesses, the code snippet, and the stack trace is shown.
Since finding the reported location in the code may be a little tedious, the report shows a preview of the file at that location.
Thread 1: 160| pthread_mutex_lock(&d->lock); 161| d->crawlerstats[slab_cls].end_time = current_time; >162| d->crawlerstats[slab_cls].run_complete = true; 163| pthread_mutex_unlock(&d->lock); 164|}
The code snippet shows that the race is on variable crawlerstats[slab_cls].run_complete. Coderrect also shows the stack trace that triggers the race to make validation on the race simpler.
>>>Stacktrace: >>>pthread_create [crawler.c:505] >>> item_crawler_thread [crawler.c:505] >>> lru_crawler_class_done [crawler.c:378] >>> crawler_expired_doneclass [crawler.c:350]
Detecting Races in Redis #
Redis is a popular in-memory database that persists on disk. Redis has been heavily adopted and is widely used. The GitHub repository has over 43,000 stars, over 18,000 questions have been tagged with [redis] on StackOverflow, and there are various meetups and conferences for Redis every year.
This tutorial assumes that you have gone through one of the three starter case tutorials and have successfully run Coderrect.
Detect the race
Redis is easy to build. To detect races on redis, simply run the following:
git clone -b 6.0.0 https://github.com/antirez/redis.git cd redis coderrect -t -o report -e redis-server,redis-benchmark make -j
- First, we clone the buggy release (6.0.0).
- Next, we cd into the redis directory and run the Coderrect tool to detect races.
- The -t flag will print the race report to the terminal so that we can quickly investigate some of the races.
- The -o report flag tells the tool to generate a report and place it into a directory named “report”.
- Next, Redis builds multiple executables by default (redis-server, redis-benchmark, and redis-cli). Coderrect is capable of analyzing one or more targets at once. Here we specify that Coderrect should analyze both redis-server and red-benchmark with the flag -e redis-server,redis-benchmark.
- Lastly, we add the command make -j to build redis.
The analysis time for each project will be printed to the terminal as is shown below:
Analyzing /path/to/redis/src/redis-benchmark ... - ✔ [00m:01s] Loading IR From File - ✔ [00m:02s] Running Compiler Optimization Passes (Phase I) - ✔ [00m:00s] Canonicalizing Loops - ✔ [00m:00s] Propagating Constants - ✔ [00m:00s] Running Compiler Optimization Passes (Phase II) - ✔ [00m:00s] Running Pointer Analysis - ✔ [00m:09s] Building Static Happens-Before Graph - ✔ [00m:11s] Detecting Races - ✔ [00m:00s] Scanning for additional OpenMP Regions Analyzing /path/to/redis/src/redis-server ... - ✔ [00m:04s] Loading IR From File ... ----------------------------The summary of races in redis-server------------------------ 12 shared data races ----------------------------The summary of races in redis-benchmark------------------------ 3 shared data races
Coderrect provide an option to list all potential target binaries and specify which binaries should be analyzed with the following command.
coderrect make
Coderrect will automatically detect which binaries were built using make and list the potential targets to be analyzed as shown below.
The project creates multiple executables. Please select one from the list below
to detect races.
In the future, you can specify the executable using the option "-e" if you know
which ones you want to analyze.
coderrect -e your_executable_name1,your_executable_name2 your_build_command_line
1) src/redis-benchmark
2) src/redis-cli
3) src/redis-server
4) deps/lua/src/luac
5) deps/lua/src/lua
Please select binaries by entering their ordinal numbers (e.g. 1,2,6):1,2,3
In addition, Coderrect allow users to analyze all generated binaries by using -analyzeAllBinaries flag to command line. Coderrect will skip the asking stage and automatically analyze all binaries.
coderrect -analyzeAllBinaries make
Interpret the Results
The coderrect tool reports a quick summary of the most interesting races directly in the terminal for quick viewing when run with -t. The tool also generates a more comprehensive report that can be viewed in the browser.
Terminal Report
Next we will explain an example of a race reported in redis-server, as well as how to debug the race based on the provided information:
==== Found a race between:
line 888, column 9 in debug.c AND line 885, column 16 in debug.c
Shared variable:
at line 72 of server.c
72|struct redisServer server; /* Server global state */
Thread 1:
886| serverLogRaw(LL_WARNING|LL_RAW,
887| "nn=== REDIS BUG REPORT START: Cut & paste starting from here ===n");
>888| server.bug_report_start = 1;
889| }
890|}
>>>Stacktrace:
>>>pthread_create [bio.c:123]
>>> bioProcessBackgroundJobs [bio.c:123]
>>> lazyfreeFreeObjectFromBioThread [bio.c:209]
>>> decrRefCount [lazyfree.c:130]
>>> freeListObject [object.c:365]
>>> _serverPanic [object.c:291]
>>> bugReportStart [debug.c:873]
Thread 2:
883|
884|void bugReportStart(void) {
>885| if (server.bug_report_start == 0) {
886| serverLogRaw(LL_WARNING|LL_RAW,
887| "nn=== REDIS BUG REPORT START: Cut & paste starting from here ===n");
>>>Stacktrace:
>>>pthread_create [networking.c:2942]
>>> IOThreadMain [networking.c:2942]
>>> _serverAssert [networking.c:2891]
>>> bugReportStart [debug.c:791]
At a glance we can quickly see that the race is between the lines 885 and 888 in the debug.c file. Line 888 writes to server.bug_report_start and line 885 reads server.bug_report_start. To confirm this race we need to show 1) both accesses can be made in parallel, and 2) the parallel accesses are being made to the same server.bug_report_start object.
884|void bugReportStart(void) {
885| if (server.bug_report_start == 0) {
886| serverLogRaw(LL_WARNING|LL_RAW,
887| "nn=== REDIS BUG REPORT START: ...n");
888| server.bug_report_start = 1;
889| }
890|}
To prove that 1) both accesses can be made in parallel, we need to show that thread 1 and 2 can both call the bugReportStart function at the same time. We can check the stack trace to see if there are any synchronizations between the threads after they are spawned.
Thread 1 >>>Stacktrace: >>>pthread_create [bio.c:123] >>> bioProcessBackgroundJobs [bio.c:123] >>> lazyfreeFreeObjectFromBioThread [bio.c:209] >>> decrRefCount [lazyfree.c:130] >>> freeListObject [object.c:365] >>> _serverPanic [object.c:291] >>> bugReportStart [debug.c:873] Thread 2: >>>Stacktrace: >>>pthread_create [networking.c:2942] >>> IOThreadMain [networking.c:2942] >>> _serverAssert [networking.c:2891] >>> bugReportStart [debug.c:791]
The first stack trace shows that thread 1 is spawned at bio.c:123 inside of the bioInit function. The second stack trace shows that thread 2 is spawned at networking.c:2942 in the initThreadedIO function. By looking one level up the stack trace, we can see that both bioInit and initThreadedIO are called one after the other from InitServerLast in server.c.
void InitServerLast() {
bioInit();
initThreadedIO();
If we check the body of the bioInit function we see there are no synchronizations or joins after thread 1 is spawned. This means thread 1 will continue to execute even after the main thread has returned from bioInit and entered initThreadIO. Then, while in initThreadIO the main thread spawns thread 2 in parallel with thread 1. Thus we have shown that both threads do indeed run in parallel.
Next we must show that 2) the parallel accesses are being made to the same server.bug_report_start object. The report also shows us the creation site of the shared object on which the race occurs (in this case server).
Shared variable: at line 72 of server.c
By inspecting server.c:72 we see that server is actually a global variable! This means that that both threads are indeed accessing the same object in memory.
72| struct redisServer server; /* Server global state */
So, by showing that 1) both accesses can be made in parallel and 2) the parallel accesses are being made to the same server.bug_report_startobject we have confirmed this race in redis.
HTML Report
The terminal is great to get a quick idea about what races are reported, but a full and more detailed report can be viewed in the browser.
When we initially ran coderrect we included the -o report flag. This created a directory named report and a file named index.html within that directory. To view the full report open the index.html file in a browser.
Depending on your system this can be done through the terminal with some command. E.g. browse report/index.html on Gnome based systems or open report/index.html on Mac.
Detecting Races in RedisGraph #
RedisGraph is a popular graph database module of Redis that supports using linear algebra to query the graph. This tutorial shows how to run coderrect on RedisGraph for finding potential races step by step.
1. Download RedisGraph and setup dependency:
$ git clone --recurse-submodules https://github.com/RedisGraph/RedisGraph.git $ cd RedisGraph $ apt-get install build-essential cmake m4 automake peg libtool autoconf
2. Run coderrect:
$ coderrect -t make
Running coderrect -t make builds the RedisGraph module redisgraph.so, which is a dynamic library. To analyze the library, Coderrect prompts a list of APIs for users to select as entry points:
Analyzing /RedisGraph/src/redisgraph.so ... 1) AC_GetU32 2) AGPLN_AddAfter 3) AGPLN_AddBefore ... 122) CommandDispatch 123) ConcurrentCmdCtx_KeepRedisCtx 124) ConcurrentSearch_HandleRedisCommand Please select APIs by entering their numbers or names:
3. Select an entry point for analysis:
Enter “122” or type “CommandDispatch“. Coderrect then continues to analyze the library with “CommandDispatch” as an entry point:
- ▖ [00m:24s] Loading IR From File EntryPoints: CommandDispatch - ✔ [00m:24s] Loading IR From File - ✔ [00m:40s] Running Compiler Optimization Passes (Phase I) - ✔ [00m:00s] Canonicalizing Loops - ✔ [00m:00s] Propagating Constants - ✔ [03m:09s] Running Compiler Optimization Passes (Phase II) - ✔ [00m:00s] Running Pointer Analysis - ✔ [03m:32s] Building Static Happens-Before Graph - ✔ [00m:10s] Detecting Races - ✔ [03m:39s] Scanning for additional OpenMP Regions
4. Analysis results:
In a few minutes, Coderrect generates the following results:
----------------------The summary of races in redisgraph.so------------------
==== Found a race between:
line 389, column 21 in graph/graphcontext.c AND line 385, column 31 in graph/graphcontext.c
Shared variable:
at line 39 of module.c
39|GraphContext **graphs_in_keyspace; // Global array tracking all extant GraphContexts.
Thread 1:
387| if(graphs_in_keyspace[i] == gc) return;
388| }
>389| graphs_in_keyspace = array_append(graphs_in_keyspace, gc);
390|}
391|
>>>Stacktrace:
>>>CommandDispatch
>>> GraphContext_Retrieve [commands/cmd_dispatcher.c:68]
>>> _GraphContext_Create [graph/graphcontext.c:132]
>>> GraphContext_RegisterWithModule [graph/graphcontext.c:103]
Thread 2:
383|void GraphContext_RegisterWithModule(GraphContext *gc) {
384| // See if the graph context is not already in the keyspace.
>385| uint graph_count = array_len(graphs_in_keyspace);
386| for(uint i = 0; i < graph_count; i ++) {
387| if(graphs_in_keyspace[i] == gc) return;
>>>Stacktrace:
>>>CommandDispatch
>>> GraphContext_Retrieve [commands/cmd_dispatcher.c:68]
>>> _GraphContext_Create [graph/graphcontext.c:132]
>>> GraphContext_RegisterWithModule [graph/graphcontext.c:103]...
7 shared data races
22 OpenMP races
To check the race report, please open '/git/RedisGraph/.coderrect/report/index.html' in your browser
Coderrect detected 7 shared data races and 22 OpenMP races in total in RedisGraph. The full report can be viewed in the browser.
