Sign in

Search issue titles and bodies, change requests and comments. Private repositories you cannot read are not included.
vole
Clone

Read only, no credentials:

https://rodent.software/git/vole.git

Write over SSH with a registered key:

git clone ssh://git@0.0.0.0:2222/vole.git

A free and open-source forge that lives in your Git repo.

Code

392 commit(s) on main

Compare History
Merge change request 01M70WES5ZZDJ6RP226WB11BBZ: Let people rename and remove their own passkeys keenan · 18m ago 4b8c9e1d
history blame raw 10.6 KiB
1package git
2
3import (
4 "crypto/sha1"
5 "crypto/sha256"
6 "encoding/hex"
7 "fmt"
8 "hash"
9 "math/rand/v2"
10 "strings"
11 "time"
12)
13
14// FlatTree reads every blob under commit as a path -> content map. Callers mutate
15// the map and hand it back to CommitFiles, which is the simplest way to express
16// "update one file in a tree" without a worktree.
17func (r *Repo) FlatTree(commit string) (map[string][]byte, error) {
18 files, _, err := r.flatTree(commit)
19 return files, err
20}
21
22// flatTree reads the blobs and every entry, including directories, keyed by
23// path. A writer that starts from an existing commit needs the directory ids as
24// well as the content, because it reuses both for the parts it did not change.
25func (r *Repo) flatTree(commit string) (map[string][]byte, map[string]Entry, error) {
26 files := map[string][]byte{}
27 entries := map[string]Entry{}
28 if commit == "" {
29 return files, entries, nil
30 }
31 list, err := r.LsTreeRT(commit)
32 if err != nil {
33 return nil, nil, err
34 }
35 shas := make([]string, 0, len(list))
36 for _, e := range list {
37 entries[e.Name] = e
38 if e.Type == "blob" {
39 shas = append(shas, e.SHA)
40 }
41 }
42 blobs, err := r.BlobsBySHA(shas)
43 if err != nil {
44 return nil, nil, err
45 }
46 for _, e := range list {
47 if e.Type != "blob" {
48 continue
49 }
50 data, ok := blobs[e.SHA]
51 if !ok {
52 return nil, nil, fmt.Errorf("flat tree: %s has no content for %s", e.Name, e.SHA)
53 }
54 files[e.Name] = data
55 }
56 return files, entries, nil
57}
58
59// WriteFlatTree writes a nested tree from flat paths and returns its id. It
60// writes every blob it is given, so it is for a tree that does not exist yet;
61// CommitFiles reuses the parts of an existing tree that did not change.
62func WriteFlatTree(g *Repo, files map[string][]byte) (string, error) {
63 var entries []Entry
64 dirs := map[string]map[string][]byte{}
65 for path, content := range files {
66 parts := strings.SplitN(path, "/", 2)
67 if len(parts) == 1 {
68 blob, err := g.HashObject(content)
69 if err != nil {
70 return "", err
71 }
72 entries = append(entries, Entry{Mode: "100644", Type: "blob", SHA: blob, Name: parts[0]})
73 continue
74 }
75 if dirs[parts[0]] == nil {
76 dirs[parts[0]] = map[string][]byte{}
77 }
78 dirs[parts[0]][parts[1]] = content
79 }
80 for name, sub := range dirs {
81 sha, err := WriteFlatTree(g, sub)
82 if err != nil {
83 return "", err
84 }
85 entries = append(entries, Entry{Mode: "040000", Type: "tree", SHA: sha, Name: name})
86 }
87 return g.MkTree(entries)
88}
89
90// CommitFiles applies mutate to the tree behind ref and moves the ref with a
91// compare-and-swap, attributing the commit to author. It is the single write path
92// for metadata refs; a second implementation would eventually disagree about
93// ordering or retries, and that shows up as lost data.
94//
95// CommitFilesBy is the same write for a caller whose author is only known once the
96// tree has been read.
97func CommitFiles(g *Repo, ref string, mutate func(map[string][]byte) error, message, author string) (string, error) {
98 return CommitFilesBy(g, ref, func(files map[string][]byte) (string, error) {
99 return author, mutate(files)
100 }, message)
101}
102
103// CommitFilesBy applies mutate to the tree behind ref and moves the ref with a
104// compare-and-swap. mutate returns the name to record as the commit's author along
105// with its change, because a caller with no account name of its own — a library, or
106// an edit made offline against a clone — has only the author the file already names,
107// and that is the one thing a caller would otherwise read the branch twice to learn.
108// Both the author and the bytes are worked out again on a retry, which is what makes
109// losing a compare-and-swap harmless.
110//
111// Only the files that changed are hashed, and only the directories on the way to
112// them are written again. A comment on a branch with ten thousand unrelated
113// files therefore costs one blob and one tree per path segment, not one process
114// per file in the repository.
115//
116// Writers of the same ref take turns: the whole read-modify-write runs under
117// lockWrites, so a write that arrives while another is in flight waits instead of
118// reading a tree it is about to lose. The compare-and-swap and its retry are kept
119// for the writers that went around the lock — a push that moved the ref, a
120// hand-run git command, a second host — which is why losing one is still safe and
121// still finishes.
122//
123// mutate must be a decision about the tree it is handed, not a replay of one read
124// earlier, and it must not call CommitFiles: one writer holds the lock at a time.
125func CommitFilesBy(g *Repo, ref string, mutate func(map[string][]byte) (string, error), message string) (string, error) {
126 unlock, err := g.lockWrites(ref)
127 if err != nil {
128 return "", err
129 }
130 defer unlock()
131
132 const maxAttempts = 64
133 for attempt := 1; attempt <= maxAttempts; attempt++ {
134 if attempt > 1 {
135 // The writer that beat us did not hold the lock, so waiting is the only
136 // way to let it finish writing its objects. Jittered so the writers that
137 // lost the same race do not line up again.
138 if err := g.pause(backoff(attempt)); err != nil {
139 return "", err
140 }
141 }
142 old, err := g.RevParseRaw(ref)
143 if err != nil {
144 return "", err
145 }
146 files, entries, err := g.flatTree(old)
147 if err != nil {
148 return "", err
149 }
150 author, err := mutate(files)
151 if err != nil {
152 return "", err
153 }
154 tree, err := writeChangedTree(g, entries, files)
155 if err != nil {
156 return "", err
157 }
158 commit, err := g.CommitTreeAs(tree, old, message, author)
159 if err != nil {
160 return "", err
161 }
162 ok, err := g.UpdateRefCAS(ref, commit, old)
163 if err != nil {
164 return "", err
165 }
166 if ok {
167 return commit, nil
168 }
169 }
170 return "", fmt.Errorf("%s: gave up after %d attempts because another writer kept moving the branch; try again",
171 ref, maxAttempts)
172}
173
174// backoff is how long to wait after losing attempt n: it doubles from a
175// millisecond to a quarter of a second and is jittered by up to half its length,
176// so writers that were refused together do not all come back together.
177func backoff(attempt int) time.Duration {
178 d := time.Millisecond << uint(min(attempt-2, 8))
179 half := d / 2
180 return half + time.Duration(rand.Int64N(int64(half)+1))
181}
182
183// pause waits between attempts without ignoring a cancelled request: a page that
184// has gone away should not keep a writer waiting for a ref.
185func (r *Repo) pause(d time.Duration) error {
186 if r.ctx == nil {
187 time.Sleep(d)
188 return nil
189 }
190 t := time.NewTimer(d)
191 defer t.Stop()
192 select {
193 case <-t.C:
194 return nil
195 case <-r.ctx.Done():
196 return r.ctx.Err()
197 }
198}
199
200// writeChangedTree builds the tree for files, reusing the blob and subtree ids
201// in old for everything that still says the same thing.
202func writeChangedTree(g *Repo, old map[string]Entry, files map[string][]byte) (string, error) {
203 sha256IDs := usesSHA256(old)
204 changed := changedPaths(old, files, sha256IDs)
205 return writeTree(g, buildTree(files), "", old, changed, changedDirectories(changed))
206}
207
208// changedPaths reports the files a write adds, removes, or changes. Content is
209// hashed in memory rather than by a git process per file: the cost is the bytes
210// on the branch, while the number of files no longer decides it.
211func changedPaths(old map[string]Entry, files map[string][]byte, sha256IDs bool) map[string]bool {
212 changed := make(map[string]bool)
213 for path, content := range files {
214 e, ok := old[path]
215 if !ok || e.Type != "blob" || e.SHA != blobID(content, sha256IDs) {
216 changed[path] = true
217 }
218 }
219 for path, e := range old {
220 if e.Type != "blob" {
221 continue
222 }
223 if _, ok := files[path]; !ok {
224 changed[path] = true
225 }
226 }
227 return changed
228}
229
230// blobID is the id git would give content as a blob, without writing it. It only
231// decides whether a path needs a new blob; every changed blob is still written by
232// git. Vole creates SHA-1 repositories, but a tree whose ids are 64 characters
233// says the repository is SHA-256 and is answered in kind.
234func blobID(content []byte, sha256IDs bool) string {
235 var h hash.Hash
236 if sha256IDs {
237 h = sha256.New()
238 } else {
239 h = sha1.New()
240 }
241 fmt.Fprintf(h, "blob %d\x00", len(content))
242 h.Write(content)
243 return hex.EncodeToString(h.Sum(nil))
244}
245
246// usesSHA256 reads the object format from an existing tree id. An empty tree has
247// nothing to say, and a repository created by Vole is SHA-1.
248func usesSHA256(entries map[string]Entry) bool {
249 for _, e := range entries {
250 return len(e.SHA) == sha256.Size*2
251 }
252 return false
253}
254
255// treeNode is a directory while a flat path map is being turned back into trees.
256type treeNode struct {
257 files map[string][]byte
258 dirs map[string]*treeNode
259}
260
261func buildTree(files map[string][]byte) *treeNode {
262 root := &treeNode{files: map[string][]byte{}, dirs: map[string]*treeNode{}}
263 for path, content := range files {
264 parts := strings.Split(path, "/")
265 node := root
266 for _, part := range parts[:len(parts)-1] {
267 next := node.dirs[part]
268 if next == nil {
269 next = &treeNode{files: map[string][]byte{}, dirs: map[string]*treeNode{}}
270 node.dirs[part] = next
271 }
272 node = next
273 }
274 node.files[parts[len(parts)-1]] = content
275 }
276 return root
277}
278
279// changedDirectories names every directory above a changed file, so the writer
280// knows which subtrees have to be rebuilt.
281func changedDirectories(changed map[string]bool) map[string]bool {
282 dirs := map[string]bool{}
283 for path := range changed {
284 for {
285 i := strings.LastIndexByte(path, '/')
286 if i < 0 {
287 break
288 }
289 path = path[:i]
290 dirs[path] = true
291 }
292 }
293 return dirs
294}
295
296func writeTree(g *Repo, node *treeNode, prefix string, old map[string]Entry, changed, dirs map[string]bool) (string, error) {
297 entries := make([]Entry, 0, len(node.files)+len(node.dirs))
298 for name, content := range node.files {
299 path := joinPath(prefix, name)
300 mode := "100644"
301 previous, had := old[path]
302 if had && previous.Type == "blob" {
303 mode = previous.Mode
304 }
305 if !changed[path] && had && previous.Type == "blob" {
306 entries = append(entries, Entry{Mode: mode, Type: "blob", SHA: previous.SHA, Name: name})
307 continue
308 }
309 blob, err := g.HashObject(content)
310 if err != nil {
311 return "", err
312 }
313 entries = append(entries, Entry{Mode: mode, Type: "blob", SHA: blob, Name: name})
314 }
315 for name, child := range node.dirs {
316 path := joinPath(prefix, name)
317 if !dirs[path] {
318 if previous, ok := old[path]; ok && previous.Type == "tree" {
319 entries = append(entries, Entry{Mode: previous.Mode, Type: "tree", SHA: previous.SHA, Name: name})
320 continue
321 }
322 }
323 sha, err := writeTree(g, child, path, old, changed, dirs)
324 if err != nil {
325 return "", err
326 }
327 mode := "040000"
328 if previous, ok := old[path]; ok && previous.Type == "tree" {
329 mode = previous.Mode
330 }
331 entries = append(entries, Entry{Mode: mode, Type: "tree", SHA: sha, Name: name})
332 }
333 return g.MkTree(entries)
334}
335
336func joinPath(prefix, name string) string {
337 if prefix == "" {
338 return name
339 }
340 return prefix + "/" + name
341}
342