-
Notifications
You must be signed in to change notification settings - Fork 1
/
gc.go
130 lines (116 loc) · 3.58 KB
/
gc.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Package gc implements garbage collection for blob stores.
package gc
import (
"context"
"github.com/pkg/errors"
"github.com/bobg/bs"
)
// Keep is a set of refs to protect from garbage collection.
type Keep interface {
Add(context.Context, bs.Ref) error
Contains(context.Context, bs.Ref) (bool, error)
}
// ProtectPair is the type of an item returned by a ProtectFunc.
// It is a ref to add to a Keep,
// plus an optional ProtectFunc for traversing the ref and finding additional refs to protect.
type ProtectPair struct {
Ref bs.Ref
F ProtectFunc
}
// ProtectFunc is the type of the callback passed to Protect.
// It is responsible for traversing a given ref to other refs that must also be protected.
// It should not do this recursively:
// that's handled within Protect itself.
// (However, it safely may, as long as it does its own loop detection.
// [Assuming loops are even a thing in content-addressable storage systems, which they probably aren't.])
// It produces the refs it finds, along with their own ProtectFuncs.
type ProtectFunc = func(context.Context, bs.Getter, bs.Ref) ([]ProtectPair, error)
// Protect adds a given Ref, and all Refs reachable from it, to a Keep.
// An optional callback is responsible for traversing the given Ref
// and reporting its child Refs (if any), plus their own optional traversal functions.
func Protect(ctx context.Context, g bs.Getter, k Keep, ref bs.Ref, traverse ProtectFunc) error {
ok, err := k.Contains(ctx, ref)
if err != nil {
return errors.Wrapf(err, "checking for %s", ref)
}
if ok {
return nil
}
err = k.Add(ctx, ref)
if err != nil {
return errors.Wrapf(err, "adding %s", ref)
}
if traverse == nil {
return nil
}
pairs, err := traverse(ctx, g, ref)
if err != nil {
return errors.Wrapf(err, "traversing %s", ref)
}
for _, pair := range pairs {
err = Protect(ctx, g, k, pair.Ref, pair.F)
if err != nil {
return err
}
}
return nil
}
// Run runs a garbage collection on store,
// deleting all refs not protected by k.
// See Protect.
func Run(ctx context.Context, store bs.DeleterStore, k Keep) error {
var (
repeat = errors.New("repeat") // sentinel for ListRefs call
lastRef bs.Ref
)
for {
// We need a new ListRefs call after each Delete
// because bs.Store does not guarantee that deletions don't affect the iteration in ListRefs.
err := store.ListRefs(ctx, lastRef, func(ref bs.Ref) error {
ok, err := k.Contains(ctx, ref)
if err != nil {
return errors.Wrapf(err, "checking ref %s", ref)
}
if ok {
return nil
}
err = store.Delete(ctx, ref)
if err != nil {
return errors.Wrapf(err, "deleting ref %s", ref)
}
lastRef = ref
return repeat
})
if errors.Is(err, repeat) {
continue
}
return err
}
}
var _ bs.DeleterStore = (*Store)(nil)
// Store is a DeleterStore that delegates calls to a nested DeleterStore
// and can count refs and deletions during a call to Run.
type Store struct {
S bs.DeleterStore
Refs, Deletions int
}
// Get implements bs.Getter.Get.
func (s *Store) Get(ctx context.Context, ref bs.Ref) (bs.Blob, error) {
return s.S.Get(ctx, ref)
}
// Put implements bs.Store.Put.
func (s *Store) Put(ctx context.Context, blob bs.Blob) (bs.Ref, bool, error) {
return s.S.Put(ctx, blob)
}
// ListRefs implements bs.Getter.ListRefs.
func (s *Store) ListRefs(ctx context.Context, start bs.Ref, f func(bs.Ref) error) error {
return s.S.ListRefs(ctx, start, func(ref bs.Ref) error {
s.Refs++
return f(ref)
})
}
// Delete implements bs.DeleterStore.
func (s *Store) Delete(ctx context.Context, ref bs.Ref) error {
s.Deletions++
return s.S.Delete(ctx, ref)
}