Where does the common ancestor of merged commits reside in Git (when there's criss-cross merge)?

Updated per comments (don't have time right now to research this, so I'm assuming what ET notes is accurate...)

First a quick aside that this is all premised on the recursive merge strategy, and on the rather specific circumstance that it will try to compute a merge base from multiple candidates.

With that, it's easiest to see what's happening if we contrive to have all these merges affecting a single file. "Easiest" is a relative term, but here we go...

O -- A - M2 <--(master)
 \     X
  ---B - M1 <--(dev)

In O we have a file named foo. A and B each change this file in a way that does not conflict. (That it not conflict may not be strictly necessary - apparently even a conflicted result can serve as the computed merge base in the recursive strategy - but it makes it easier to see what's going on if you want to reproduce these steps and look at the repo.)

M1 is an "evil merge" of A and B; although A and B would merge cleanly, an additional change to foo is made when creating M1.

Likewise, M2 is an "evil merge" of A and B; the added change to foo in M2 conflicts with the added change to foo in M1.

Now if we try to merge dev with master then foo is in conflict; and sure enough

git cat-file -p :1:foo

will show us a file that we never stored before - the result of a clean merge between the versions of foo in A and B.

So now to your question:

I found Git does not create any blob object for this new commit

That statement is a little confusing; commits are not represented by BLOB objects. It's true that there is no COMMIT object representing the calculated merge base.

But there is a new BLOB for :1:foo - just as there would be for any index entry[1]. There's also (in my test) a TREE object to contain the BLOB. In other words, the entire content of the calculated merge base is, in fact, stored in .git/objects.

Does it mean the base versions exist nowhere but in the working memory (the 1st slot of the index for Git)?

The base versions exist in the 1st slot of the index, but that is most definitely not "working memory". There generally isn't even a git process running during the time you're resolving conflicts - so no process whose working memory could be used to contain it.

As noted above, the index is made up of BLOB objects on disk.

And so, if my computer shuts down and I have an unresolved conflict, would the generated base commit be lost?

No.

But would it matter if it were? If somehow the automatically generated merge base were lost and you had to start over, git would just automatically generate it again.

[1] - Ok... sigh... not quite "any" index entry. There are "content-less" index entries for when you declare the intent to add a file. But that's not really related to all this and it just confuses matters. Only mentioning it to get ahead of the pedants and trolls.

I dug into this code in git merge-recursive at one point out of curiosity. Here are the terrifying details ("terrifying" per Edward Thomson's comment).

First, git merge-recursive or git merge-resolve, which share most of their code, gathers up all the merge base commit hash IDs. This forms a simple list (stored as a linked list when I looked, though the important thing is that it's an ordered list). If the length of the list is 1, we have a single merge base and we're done. Otherwise we have multiple merge bases:

• If we're git merge-resolve, we pick one "at random" (whatever is most convenient, probably head of list) and use it and we're done.

• Otherwise—when we're git merge-recursive—we use the following algorithm:

  • while there are at least two entries in the list:

    1. Merge the first two merge bases, with a recursive call. This produces a merge result (in the index). If there are merge conflicts, the conflicts appear in the index.¹
    2. Forcibly shove all the results into index slot zero. Make a new commit from this tree.
    3. Replace the pair of commit hash IDs with the single commit hash ID from step 2.

  At the end of this loop, there is only one hash ID in the list. This is the merge base.

Note that this algorithm is linear in the number of merge bases, when we could use a logarithmic strategy: if there are, say, 16 merge bases, we could merge each pair to get 8 merge bases, then merge each pair to get 4, then merge each pair to get 2, then merge the pair. Instead, we merge 2 to get 1, leaving 15 to merge; merge 2 to get 1, leaving 14; and so on.

This is probably totally reasonable. Criss-cross merges get you a two-merge-base setup, but they're rare. How you would ever manage to set up a 16-merge-base situation, I am not sure. Edit: And, as Raymond Chen notes, we wouldn't save any of the primary work anyway.

¹This explains why the conflicted object shows up in the repository. However, if we're doing the outermost merge—which the recursive code always knows—there was no need to put this object into the repository. Note that the merge.driver used for low level merges here is the defined driver when doing the outermost merge, and the recursive driver when doing any of the inner merges; that's why we know if this is the outermost merge. If it is the outermost merge, there was no need to create a blob in the Git repository database.