Building Git: Part III

Yokosho watashino, part 3 of Building git. In the previous parts we build the gitgo capable of storing the flat directory structure and the files inside it. But having only single commit in the version control system, is not very useful. We have no relationships between the commits as of now, and it is not helpfull to have all the commits disoriented, with no way of going back to parent commit. Our first goal was to just commit the contents to get started with the miniature version of the git.

Now, we will be working to make history in this part. Let’s get to it.

The parent field

The git adds the new parent field in the commit object on the every subsequent commits to make a history, and to be able to trace all the history. Only the root-commit object does not have the parent field in the commit object, but every following commits contains a parent field telling git where this commit inherits from, for the case of merge the commit has two parents. The git uses this to sort all the commit and make a tree structure. Git do not uses the timestamp for sorting all the commits as it will be harder, and not feasable when working with the team. As two people can make a commit at same time, so timestamp it not a good parameter to sort the commits. For this we use the parent field, if a user wants the latest 5 commits, we can easily show the user all the commits by getting the latest commit from the .git/HEAD and then tracing the parent commit of all the commit till we have 5 commits.

It is more robust to put the idea that commit B is derived from commit A into data model; it makes calculating what changed on different people’s branches, and merging those changes together. We will see more on these when we will building the merge and branch commands.

Differences between trees

Let’s get the tree data of the two commits on the test file we made.

1
❯ git cat-file -p 88e3870
2
100644 blob ce013625030ba8dba906f756967f9e9ca394464a  hello.txt
3
100644 blob cc628ccd10742baea8241c5924df992b5c019f71  world.txt

This is the output of the first commit tree structure. Now let’s get the commit tree structure of the second commit

1
❯ git cat-file -p 040c6f3e
2
100644 blob e019be006cf33489e2d0177a3837a2384eddebc5  hello.txt
3
100644 blob cc628ccd10742baea8241c5924df992b5c019f71  world.txt

As we can see that the hash of the file hello.txt is different in the both tree object, because the first commits hello.txt holds the value hello and the second commits hello.txt holds the value second. So it has the different hash in the both commits tree structure.

As for the case of file world.txt its content remained the same in the both commits, so hash was not different, and git does not have to store two different compressed files storing the same file content. So git do not save the additional file for same content across the different commits, it just add the hash of the file. This is how, git saves the storage space for the codebase with millions of line of code and thousands of file.

Implementing the parent chain

So we do not have to modify our code of storing the blob and tree object, and keep updating the .git/HEAD to point to the latest commit. We have to add the parent hash to the new commits, we can know if the commit is root-commit or not by checking for the .git/HEAD file. If the file exists then the commit is not a root-commit and add the .git/HEAD files hash as the parent hash in the commit object. If we do not find the file, then the commit is a root-commit and we do not have to add a parent hash to the commit object.

We will introduce an abstraction to updating the HEAD file to update the HEAD file easily and safely.

refs.go

1
package gitgo
2

3
import (
4
    "os"
5
    "path/filepath"
6
)
7

8

9
type ref struct {
10
    pathname string
11
    headPath string
12
}
13

14
func RefInitialize(pathname string) ref {
15
    r := ref{pathname: pathname}
16
    r.headPath = filepath.Join(r.pathname, "HEAD")
17
    return r
18
}
19

20
func (r ref) UpdateHead(oid []byte) error {
21
    flags := os.O_WRONLY|os.O_CREATE
22
    refFile, err := os.OpenFile(r.headPath, flags, 0644)
23
    if err != nil {
24
        return err
25
    }
26
    defer refFile.Close()
27

28
    _, err = refFile.Write(oid)
29
    if err != nil {
30
        return err
31
    }
32

33
    return nil
34
}

Let’s add a function that will return the hash string that the HEAD file is storing if the file exist, else the function will return the empty string if the file do not exists. This will tell that the file do not exists, and this is root-commit.

1
func (r ref) ReadHead() string {
2
    _, err := os.Stat(r.headPath)
3
    if os.IsNotExist(err) {
4
        return ""
5
    }
6

7
    content, _ := os.ReadFile(r.headPath)
8
    return string(content)
9
}

Now we can use this in the commit handler.

cmd/gitgo/cmdHandler.go

1
  refs := gitgo.RefInitialize(gitgo.GITPATH)

Add this line after storing all the blob and tree object.

1
  author := gitgo.Author{
2
    Name:      name,
3
    Email:     email,
4
    Timestamp: time.Now(),
5
  }.New()
6
  message := gitgo.ReadStdinMsg()
7
  refs := gitgo.RefInitialize(gitgo.GITPATH)
8
    parent := refs.ReadHead()
9
    is_root := ""
10
    if parent == "" {
11
        is_root = "(root-commit) "
12
    }
13

14
    commitData := gitgo.Commit{
15
        Parent: parent, // we will add this field to struct
16
        TreeOID: treeHash,
17
        Author: author,
18
        Message: message,
19
    }.New()
20
    cHash, err := gitgo.StoreCommitObject(commitData)
21
    if err != nil {
22
        return err
23
    }
24

25
    refs.UpdateHead([]byte(cHash))
26

27
    fmt.Printf("%s %s %s", is_root, cHash, message)
28
    return nil

Remove the code where we are creating the HEAD file in the Handler. Now we need to adjust the Commit struct to add the Parent hash string.

database.go

1
type Commit struct {
2
    Parent  string
3
    TreeOID string
4
    Author  string
5
    Message string
6
}

And now update the Commit structs New() function.

1
func (c Commit) New() string {
2
    lines := []string{}
3
    lines = append(lines, fmt.Sprintf("tree %s", c.TreeOID))
4
    if c.Parent != "" {
5
        lines = append(lines, fmt.Sprintf("parent %s", c.Parent))
6
    }
7
    lines = append(lines, fmt.Sprintf("author %s", c.Author))
8
    lines = append(lines, fmt.Sprintf("committer %s", c.Author))
9
    lines = append(lines, "")
10
    lines = append(lines, c.Message)
11

12
    return strings.Join(lines, "\n")
13
}

With these changes in place we can now build the executable file from the cmd/gitgo, and run the gitgo to create a new commit. We can verify that the new commit has the parent field in it.

Rename .gitgo folder to .git, and now use the git’s command hehehe…

1
❯ git cat-file -p 51db7c69
2
tree 040c6f3e807f0d433870584bc91e06b6046b955d
3
parent 706f942675c04ef7cd637022b6ec236b2a98e6da
4
author  <> 1740759443 +0530
5
comitter  <> 1740759443 +0530
6

7
Second Commit

So our new commit has the parent field in it. Great.

Safely updating .git/HEAD

When we were creating our code to store the blob object we where first writing to a temp file and then renaming it to the permanent filename. Because there might be a case where we are writing to a file, and at the same time another program is reading that file, so the reading program will see the uncomplete content written to file. So for it not to happen we first write to a temp file and when the writing is complete we rename the file to the permanent filename.

In case of .git/HEAD this means that while we are updating the file, other program might try to read it, and it might see an empty string or a partial hash of the commit.

Files in .git/objects never change; because the names of the object files are determined by the file’s content, under the assumption that SHA1 is doing its job. So for us it does not matter that which of the two different program wins because they are writing the same content. All we care that this process appears to be atomic and when we read the file they have the full content in them. For this purpose it’s sufficient to pick a random filename to write the data out to, and then rename this file.

This is not the case for .git/HEAD and other refernces - their while purpose is to have stable, predictable names and change their content over time, enabling us to find the latest commit without the need to know its ID. Writes to them must still appear atomic, but we must not preassume that two process are trying to write the same thing to the file. In fact we should preassume that both are trying to write different references to the file is an error, because unless those process are explicity co-ordinating with each other. They will probably disagree about the state of the system and the final value of reference will depend on whichever process finish last.

Such race condition become even more important when data must be read from a file, then modified or transformed in some way before being written back to the file. Or, when we need to check the file’s current value before deciding whether to overwrite it - we need to know that the value won’t be changed by another process while we’re making this decision.

So what can we do? We can solve this problem by introducting a new abstraction called a Lockfile. This will be initialised with the path of the file we want to change, and it will attemp to open a file to write to by appending .lock to the original pathname. We need to pick a well-know name rather than generating a random pathname, because the whole point is to prevent two processes from getting access to the same resource at once. And this is easier if they’re both trying to access the same file.

Let’s begin writing.

lockfile.go

1
package gitgo
2

3
import (
4
    "errors"
5
    "log"
6
    "os"
7
    "sync"
8
)
9

10
var (
11
    ErrMissingParent = errors.New("Missing Parent")
12
    ErrNoPermission = errors.New("No Permission")
13
    ErrStaleLock = errors.New("Stale Lock")
14
)
15

16
type lockFile struct {
17
    FilePath string
18
    LockPath string
19
    Lock     *os.File
20
    mu       sync.Mutex
21
}
22

23
func lockInitialize(path string) *lockFile {
24
    lockpath := path + ".lock"
25
    return &lockFile{
26
        FilePath: path,
27
        LockPath: lockpath,
28
    }
29
}
30

31
func (l *lockFile) holdForUpdate() (bool, error) {
32
    l.mu.Lock()
33
    defer l.mu.Unlock()
34
    if l.Lock != nil {
35
        return true, nil // lock already aquired
36
    }
37

38
    file, err := os.OpenFile(l.LockPath, os.O_RDWR|os.O_CREATE|os.O_EXCL, 0644)
39
    if err != nil {
40
        if os.IsExist(err) {
41
            return false, nil
42
        } else if os.IsNotExist(err) {
43
            return false, ErrMissingParent
44
        } else if os.IsPermission(err) {
45
            return false, ErrNoPermission
46
        }
47
        return false, err
48
    }
49

50
    l.lock = file
51
    return true, nil
52
}
53

54
func (l *lockFile) write(data []byte) {
55
    l.mu.Lock()
56
    defer l.mu.Unlock()
57

58
    l.errOnStaleLock()
59
    _, err := l.Lock.Write(data)
60
    if err != nil {
61
        log.Fatalf("Write error: %s\n", err)
62
    }
63
}
64

65
func (l *lockFile) commit() {
66
    l.mu.Lock()
67
    defer l.mu.Unlock()
68

69
    l.errOnStaleLock()
70

71
    err := l.Lock.Close()
72
    if err != nil {
73
        log.Fatalf("Err closing file: %s\n", err)
74
    }
75

76
    err = os.Rename(l.LockPath, l.FilePath)
77
    if err != nil {
78
        log.Fatalf("Err renaming file: %s\n", err)
79
    }
80

81
    l.Lock = nil
82
}
83

84
func (l *lockFile) errOnStaleLock() {
85
    if l.Lock == nil {
86
        log.Fatalf("Err: %s\nNot holding lock of file: %s\n", ErrStaleLock, l.LockPath)
87
    }
88
}

The purpose of the holdForUpdate function is to let the caller attemp to acquire a lock for writing to the file, and to be told whether they were successful. This is done by attempting to open the .lock file with the CREATE and EXCL flags, which means the file will be created if it does not exist, and an error will result if it already exists.

If the OpenFile call succeeds, then we store the file handle in the lockFile.Lock and return true. If the file already exists, we return the error.

After aquiring the lock we need two further methods write and commit. The write method builds up data to be written to the original file, by writing to the file with .lock. Then after the writing will be done, the commit function will rename the file to the original filename, and will update the lockFile.Lock to null, so that no more data can be written. Both of these function will stop when lockFile.Lock does not exists, since that indicates either that the lock has been released, or that the caller never acquired it in the first place.

Now we can use this in the ref.UpdateHead() function, to prevent the two instances of gitgo to move the .gitgo/HEAD at the same time.

refs.go

1
import (
2
    // ...
3
    "errors"
4
    "fmt"
5
)
6

7
var ErrLockDenied = errors.New("Lock Denied")
8

9
// ...
10

11
func (r ref) UpdateHead(oid []byte) error {
12
    lockfile := lockInitialize(r.headPath)
13
    if lock, _ := lockfile.holdForUpdate(); !lock {
14
        return fmt.Errorf("Err: %s\nCould not aquire lock on file: %s", ErrLockDenied, r.headPath)
15
    }
16

17
    oid = append(oid, '\n')
18
    lockfile.write(oid)
19
    lockfile.commit()
20

21
    return nil
22
}

This modification to refs.go ensures that the chain of commits is properly recorded, since it prevents .gitgo/HEAD from being inconsistenlty updated. The lockfile abstraction will find further use later, as we introduce more types of record-keeping into the repository.

Don’t overwrite objects

Before move to the next feature, there’s a small improvement we need to make. When we first wrote the cmdHandler we were writing all the objects whether commit, tree or commit object to disk.

Now on the every subsequent commit, there will be files that will be unchanged, particularly blob object. It’s wasteful to re-write these files, so we’d like to avoid it if possible.

database.go

1
func StoreObject(data bytes.Buffer,
2
    prefix, folderPath, PermPath string
3
) error {
4
    err := os.MkdirAll(folderPath, 0755)
5
    if err != nil {
6
        return err
7
    }
8

9
    // if the file exists exit
10
    _, err = os.Stat(PermPath)
11
    if os.IsExist(err) {
12
        return nil
13
    }
14

15
    // ...
16
}

Now we are skipping the files that already exists on the disk.

Afterwords

And voila… there we have it. In this part we created

• A link to the past, meaning storing the previous commits hash to the subsequent commits as the parent field.

• Safely updating the .gitgo/HEAD file.

• Not overwriting the blob object to the disk.

Great work…

Code Link: Github

Just know this,

Reinvent the wheel, so that you can learn how to invent wheel

– a nobody