Make index iterator thread safe - #2108

😍

Okay, so that last commit that adds some tests for running diffs concurrently in a threaded environment still has some outstanding issues.

I immediately saw crashes when the various threads competed to update the attr file cache. I added a basic lock around modifying the cache and added refcounting on the individual attr files so they could be removed from the cache and outstanding threads would not access freed memory. I am still seeing sporadic crashes from ignore files for the crash and my initial attempt to resolve them with refcounts did not seem to work out right - the lifecycle for ignore file objects is slightly different than for git attribute files and that seems to have screwed me up.

Additionally, I suspect that the reference counting I introduced has caused some memory leaks for certain cases with the attribute files. I'm putting that on the TODO list above, too.

This is not entirely on-topic, but is there a discussion somewhere about the intended threading model for libgit2? It seems that the current idea is that individual objects can be accessed, and in this case, modified simultaneously with concurrent readers. For example, I wouldn't necessarily expect to be able to safely iterate over an index object while modifying it in another thread. In this situation, I'd expect to one of the threads would need to copy the index object.

An alternative threading model that comes to mind is SQLite's where each connection object (or in the case of libgit2, a repository object) can only be accessed by a single thread at a time but a given database can have multiple connection objects.

@GrahamDennis That is a reasonable question and we should probably write it up in the docs directory or something because I think it has previously only be described in responses to some issues.

When libgit2 is compiled with THREADSAFE on, the intent is to enable a SQLite-like threading model where the library can be used in a threaded environment so long as each git_repository is only accessed by a single thread. We have some reasonable confidence that this is an okay usage pattern (with some minor caveats about making sure that git_threads_init is called before any concurrency actually starts).

There have been a couple smaller efforts to enable a more granular threading model where certain actions can be taken using multiple threads even with a shared git_repository object. The only area where I have much confidence in this is for simple usage of the ODB - i.e. using git_object_lookup and the like to do simple object access.

This PR is an effort to expand the options for multithread access to a single repository to include some other actions that are still purely read-only, such as running two diffs concurrently. Libgit2 diff is a read-only operation so this should work, but due to some decisions in the design of index access and in the layer that caches git ignore and attribute data, this does not yet work correctly.

There is no concerted effort to allow multiple threads to access a single git_repository and even where there has been some work done, it is usually still in a multiple-readers, single-writer type of model (i.e. so you would still have to explicitly serialize any write actions). The "one thread per git_repository" is really the only approved threading model at this point.

Maybe it's worth to note that the thread-safety of the ODB was internally required for efficient creation of packfiles (unless my memory is totally misleading me now :)

@arrbee OK that's the threading model I would have expected. For my benefit, is the issue here that searching the index for entries can mutate the index because it triggers a sort? Therefore 'read-only' operations can actually mutate the index?

If so, why make the index support concurrent 'read-only' operations by increasing the cost of index iteration in all use cases (as all index iterators would need to create a snapshot), vs documenting the 'volatile' nature of git_index and provide a git_index_copy API? Or, requiring users to obtain two git_index objects derived from different git_repository objects?

The "one thread per git_repository" is really the only approved threading model at this point.

@arrbee Just to clarify, does this actually have to be one thread, or do you just mean that all use of a git_repository should be serialized? In other words, does libgit2 use TLS or some mechanism which has an explicit association with threads?

@jspahrsummers Sorry for the delay in responding - as I think you now know, I was on vacation.

While libgit2 does use TLS, it only uses it for storing the last error message that occurred from an API invoked on that thread. Provided that libgit2 error message checks are made on the same thread that actually invoked the API, then yes, you only need to serialize git_repository access, not have a dedicated thread.

Just a quick note - I've continued to work on this, but it has proven quite tricky to actually provide true thread safety here without much more extensive changes to the index and attributes files.

My current thought is to drop the actual thread-safety tests for index diffs from this PR (and not claim that diffs are thread safe) and merge the PR nonetheless - not as a fix for the index diff threading problems, but as a first step and one that reduces the window of contention over index contents during diffs.

I did fix one memory leak from the additional refcounting the attributes / ignores code, but there is still another one that I'm chasing down...

Okay, well, there is an issue - the memory leak fix for pop ignores in bd6265e causes a double free in the threaded tests, but if I take it out, a leak in the non threaded tests. A'debugging I will go. Other than that, I think this is shaping up.

@arrbee: this just got stale. If you could rebase it, I'd like to merge it right away.

I have a rebased version of this, but I'm struggling a bit to clear up memory leaks with ignore files. If I remove the leaks from the unthreaded code, then the threaded tests leak. If I remove the leaks from the threaded code, then I see a double-free in the unthreaded code. The ignores and attributes caching is overly messy but I'm trying hard not to make refactoring that a prerequisite for getting this wrapped up.

I've been hacking on this off and on over the past couple of days and wrote a much simpler threaded test that causes the leak. This allowed me to find the race condition that causes the problem, but unfortunately, I don't see a great fix other than changing how the attribute/ignore file caching code works. The current logic is too complicated and mixes together too many situations (loading a file for the first time, finding a file is not present, updating an existing file, clearing a file that has been deleted). I'm about 75% of the way through reorganizing the code to make this all simpler and hopefully repair the race condition.

Okay, so I pushed up a kind of big refactoring of the attribute cache. It compiles but the tests are still pretty broken - I think there is still some initialization order stuff that I've left borked. I'll fix it up tomorrow...

Okay, so I was still seeing issues with the threaded tests that could lead to crashes. I worked around them by making two changes, neither of which I love, but they seem like pragmatic solutions. I'll be curious if you hate them @vmg too much...

Specifically, I was seeing a problem where an index entry could end up inserted twice into the index (which would result in a double free). This appeared to be due to some race between finding the item in the index and inserting it. I switched to using git_vector_insert_sorted (which I know you dislike) to keep the index sorted even across inserts so we can maintain "findability" at all times. Because we must search the index before every insertion anyhow, I don't think this is slower than inserting at the end and re-sorting the list every time. If anything, I suspect it will provide a minor performance improvement.

The second fix is for a remaining race condition when a gitattribute file or gitignore file is considered out-of-date. Even though I rewrote the file caching layer to eliminate races, it was still possible for two threads to both fetch the file from the cache and both decide that it was out of date and needed to be reloaded. This could be fixed by moving the reloading logic into the code that checks the file out of the cache, but I didn't want to hold the cache lock during a file parse. Instead, I added a lock to the attribute file structure and just lock the one file while it is being reloaded. This is okay if git_mutex items are not a scarce resource.

After these changes, I need to check again for memory leaks to make sure I haven't introduced any new ones...

Okay - a little rebase there to meld this with some of the merged ignore bug fixes.

I don't see either change being particularly gross. I like them both. :)

What I'm not starting to like is the size of this PR. I don't even know what changed since the last time I read through all of it. :'(

Is there any chance we could merge this soon and maybe iron out the kinks later?

What I'm not starting to like is the size of this PR

Yes, this has grown quite a bit more than I expected. It now includes major changes to the attributes and ignore code that are separate from the index changes (although necessary to actually get the threading benefits).

I think the only thing left is to check this further for memory leaks. I was planning to work on that this afternoon, but if you want to merge now and clean up leaks, etc., I'm okay with that.

FWIW, just the last 4 commits in the PR are actually new code, although 987651d alone is pretty gigantic.

@vmg If this PR has become too much to swallow, I'm willing to split it into multiple smaller PRs. There could be, conceptually, three PRs in this one: one to rework attribute/ignore file caching to be thread safe, one to rework the index to be more thread safe + provide thread safe snapshots + use them for diffs, and one with various code cleanups that are not directly related to the other two.

Okay, I've spent the afternoon tracking down memory leaks and there are a couple of problems I've found with updating timestamp data so that a file won't always be reloaded and then with managing reference counts correctly when an existing file does need to reloaded. It won't be too big a fix, but I'd like to fix it up before we think about merging this.

Ok, so I'm getting a clean valgrind with the latest fixes here and I also rebased to deal with the conflicts that had been merged into development (which were my own fixes for some attribute stuff that I backported).

There isn't anything else that I intend to do with this PR.

This is a huge improvement. Particularly love the threaded tests. :)))))))