GSoC Follow Ups

This is a quick follow up post to talk about the status of my project after GSoC has finished.

The Git community was very receptive and I definitely wanted to keep contributing to the project after GSoC ended. Besides, my project wasn’t complete yet and I had some ideas in mind I wanted to try. So it was time for a v2!

I also took some time to write a post talking about how to start contributing to Git based on the experiences I had during this period. I’m very happy that some people who wanted to start contributing reported it was helpful in some way :)

Where were we?

As a brief recap, the idea was to make object reading thread-safe (and with good parallel performance) so that we could re-enable threading in git-grep for the non-worktree case. Part of this goal was already accomplished during GSoC by allowing zlib inflation to be performed in parallel and protecting the other object reading section. However, the code for some of git-grep’s options (namely --textconv and --recurse-submodules) wasn’t fully protected yet, forcing git-grep to run sequentially when these options were given.

Main idea for v2

For this new version, I’ve rewritten the patches almost entirely from scratch. My main idea was to turn the mutex that would protect object reading into a recursive mutex. And then, make use of it at external places that needed to be protected against concurrent object reading operations. In particular, I wanted to use it to protect some of the code concerning git-grep’s --textconv and --recurse-submodules options.

The need for the mutex to be recursive comes from the fact that some of the external places it was used in this patchset also perform object reading behind the curtains (so if it weren’t recursive, the thread would try to double lock the mutex leading to possible errors).

I also realized that protecting only oid_object_info_extended() wouldn’t be enough for the desired usecase at git-grep. So, between other changes, another mutex was added to protect the operations at replace-object.c and some lazy initializers were forced to perform eagerly (before dispatching the worker threads, to avoid races). Namely, these were the .gitmodules file loading and the initialization of packed_git. The grep_submodule() function was also refactored to safelly perform as many parallel submodule operations as possible, aiming to increase performance.

Inspecting call graphs

To make sure we were race-free, before re-enabling threads for all git-grep cases, I decided to generate and inspect some call graphs. Especially, I was looking for paths in git-grep’s call graph that would lead to unprotected functions without acquiring locks. For this task, I tried many tools, such as:

My callpath script
The Cally tool
GNU’s Cflow

But none of them gave me the picture I wanted. The main problem I had with some of the tools was not being able to handle multiple valid functions with the same name, as I described in this issue.

At this point, I got a great help from Giuliano Belinassi, a friend of mine who contributes to GCC. He wrote a patch to make GCC dump the whole call graph for the program being compiled, in dot’s format. (He’s still improving the patch to send it upstream. I’ll try to remember to update this post with the patch link once he sends it.)

Then, I wrote a python script to filter only the paths starting from a group of functions A and ending in another group of functions B (making sure to include all paths, including recursive ones). I also added an option to exclude all paths that contained any function from a group C. With the patched GCC and the filter script, I began the journey of generating and analyzing git-grep’s call graph. This took me a lot longer than I thought it would, but I think it was worth the effort. I focused in searching for paths departing from cmd_grep() or run() (the worker threads’ start routine) and leading to any of the thread-unsafe functions that would also be present in object reading’s call chain (at least, the ones I know to be thread-unsafe).

As an example, I knew that parse_object() wasn’t thread-safe and that it was present at object reading call chains. So I wanted to check for other calls to it outside object reading (as these were already protected). With that in mind, I generated this graph.

I know, it’s a *huge* graph and too hard to be manually analyzed. But starting at cmd_grep()/run() and eliminating the paths we know that are protected (in the dot file, before generating the image), we are left with a smaller subgraph which indicates the currently unprotected (and racy) paths. As an example of unprotected and possibly racy path that can be found in the above graph, we have:

cmd_grep() > grep_objects() > deref_tag() > parse_object()

With this technique, I found other 5 spots in git-grep that were already in race condition, even for the worktree case. This lead to the 3 first patches of this new iteration:

(the other ones can be seen in the link bellow)

Results

The final patches can be seen here. They have been already picked up and are now cooking at pu.

Next Steps

I’m really glad to see git-grep running faster and with full threading support (even when --textconv and --recurse-submodules are used)! Now that the main goal was reached, I want to work on some side issues I found during the process of examining git-grep for this project. The first one is trying to make grep_submodule() stop adding the submodule’s odbs to the in-memory alternates list.

Another problem I stumble across during GSoC is the textconv cache been always written to (and read from) the_repository, even for submodules’ objects. That doesn’t perform well when we git-grep the superprobject and then go down to the subproject to further inspect it. I have told a friend about this issue and he is making progress trying to solve it :) I hope I can pair up with him to help.

I also have to finish writing the monograph for my college capstone project (whose theme is my GSoC project :).