The rootkeys included in the ChangeSet weave occur multiple times so they are only stored once in the heapfile. This is done using a linked list of rootkeys in the heap. The field s→rkeyHead is loaded from the sccs_perfile() section of the s.ChangeSet file and points at the most recently added rootkey in the file. The rootkeys are stored in the heap as a u32 binary offset to the next key followed by the actual null terminated key. As follows:

The last key in the list has a 0 for the nextkey pointer.

When a new file is to be added for a commit, list is walked to find the existing rootkey. See the HEAPFILE for more information on how this information is optimized.

The original binary weave format is known as BWEAVEv2 and includes a repository feature bit. The heap at that offset contains at list of rootkey/deltakey pairs, the rootkeys are stored as offsets to the heap so they can be deduplicated. The deltakeys are stored null-terminated directly in the heap. The end of the list is marked by a 0 rootkey offset.

The rootkey offset in the weave points at the 'nextkey' field of the rootkey linked list. So the actual rootkey is at HEAP(s, off+4).

This format shipped in bk-6 .

In v3 the format of the binary weave changes. Now both the rootkeys and the delta keys are stored loose in the heap and the actual weave data is just rk/dk pairs written as 32-bit offsets.

In this version both offsets point directly at the keys and so for the rootkey the offset is right after the 'nextkey' field.

This is larger than BWEAVEv2 as it uses 4 more byte per line in the weave. It also means that when reading the entire weave we stride two regions of memory instead of just one. But in the case where the cset weave needs to be scanned for certain rootkeys, the size of the data to be traversed is significantly smaller.

The difference between BWEAVEv2 and BWEAVEv3 can be see by looking at the heap usage on the ChangeSet file on the linux-2.6 repository.

For traditional ascii and BWEAVEv2, sfiles the upgrade path in identical. Clone with --upgrade will write a BKFILE s.ChangeSet file and enable BWEAVEv3.

To revert to an ascii repository bk clone --compat continues to work. To revert to a BWEAVEv2 repository the user would need to use --compat with the new bk and then --upgrade with bk-6.x.

For ascii ChangeSet files the existing ascii weave is walked unconditionally at the end of sccs_init(). Then the weave is built on the fly into the in-memory copy of the heap. When writing an ascii ChangeSet weave the sccs_nextdata() function produces the old ascii weave on the fly. This means the BitKeeper is actually slower when reading ascii repositories with big ChangeSet files. This is most noticeable when running commands that read information from the delta table of the ChangeSet file, like in the GUI tools.

The reading and write v2 vs. v3 is hidden in the RKDKOFF macro on the read side and weave_set() function on the write side.

If the format that is read differs from the format written, then weave_cvt() will be called to generate v3 and weave_cvt2() will be called to generate v2.

Commands like rset can be made faster if the cset weave indicated when a new file was created. Currently you have to walk the entire weave to know that a given rootkey will not be used again.

As part of the BWEAVEv3 code, the weave encoding can also include markers like this:

So the last time each rootkey appears in the weave we have an additional weave line that mark this. This always code looking for information about a certain file to stop processing the weave when no more history for that file appears.

This information is added to the weave by commit, takepatch and repack. At the moment the information is advisory. The marker isn’t always present, but if it is present it is correct. Check verifies that.