Skip to content
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Commit 011ac6b

Browse files
whyrusleepingwhyrusleeping
committedJul 6, 2015
reintroduce indirect pinning, add enumerateChildren dag method
License: MIT Signed-off-by: Jeromy <jeromyj@gmail.com>
1 parent 8f716ae commit 011ac6b

File tree

6 files changed

+134
-89
lines changed

6 files changed

+134
-89
lines changed
 

‎blocks/key/key_set.go

+20-27
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,39 @@
11
package key
22

3-
import (
4-
"sync"
5-
)
6-
73
type KeySet interface {
84
Add(Key)
5+
Has(Key) bool
96
Remove(Key)
107
Keys() []Key
118
}
129

13-
type ks struct {
14-
lock sync.RWMutex
15-
data map[Key]struct{}
10+
type keySet struct {
11+
keys map[Key]struct{}
1612
}
1713

1814
func NewKeySet() KeySet {
19-
return &ks{
20-
data: make(map[Key]struct{}),
21-
}
15+
return &keySet{make(map[Key]struct{})}
2216
}
2317

24-
func (wl *ks) Add(k Key) {
25-
wl.lock.Lock()
26-
defer wl.lock.Unlock()
27-
28-
wl.data[k] = struct{}{}
18+
func (gcs *keySet) Add(k Key) {
19+
gcs.keys[k] = struct{}{}
2920
}
3021

31-
func (wl *ks) Remove(k Key) {
32-
wl.lock.Lock()
33-
defer wl.lock.Unlock()
34-
35-
delete(wl.data, k)
22+
func (gcs *keySet) Has(k Key) bool {
23+
_, has := gcs.keys[k]
24+
return has
3625
}
3726

38-
func (wl *ks) Keys() []Key {
39-
wl.lock.RLock()
40-
defer wl.lock.RUnlock()
41-
keys := make([]Key, 0)
42-
for k := range wl.data {
43-
keys = append(keys, k)
27+
func (ks *keySet) Keys() []Key {
28+
var out []Key
29+
for k, _ := range ks.keys {
30+
out = append(out, k)
4431
}
45-
return keys
32+
return out
4633
}
34+
35+
func (ks *keySet) Remove(k Key) {
36+
delete(ks.keys, k)
37+
}
38+
39+
// TODO: implement disk-backed keyset for working with massive DAGs

‎core/commands/pin.go

+34-14
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ import (
88
key "github.com/ipfs/go-ipfs/blocks/key"
99
cmds "github.com/ipfs/go-ipfs/commands"
1010
corerepo "github.com/ipfs/go-ipfs/core/corerepo"
11+
dag "github.com/ipfs/go-ipfs/merkledag"
1112
u "github.com/ipfs/go-ipfs/util"
1213
)
1314

@@ -153,24 +154,25 @@ var listPinCmd = &cmds.Command{
153154
Helptext: cmds.HelpText{
154155
Tagline: "List objects pinned to local storage",
155156
ShortDescription: `
156-
Returns a list of hashes of objects being pinned. Objects that are
157-
recursively pinned are not included in the list.
157+
Returns a list of hashes of objects being pinned. Objects that are indirectly
158+
or recursively pinned are not included in the list.
158159
`,
159160
LongDescription: `
160-
Returns a list of hashes of objects being pinned. Objects that are
161-
recursively pinned are not included in the list.
161+
Returns a list of hashes of objects being pinned. Objects that are indirectly
162+
or recursively pinned are not included in the list.
162163
163164
Use --type=<type> to specify the type of pinned keys to list. Valid values are:
164165
* "direct": pin that specific object.
165-
* "recursive": pin that specific object, and indirectly, all its descendants
166+
* "recursive": pin that specific object, and indirectly pin all its decendants
167+
* "indirect": pinned indirectly by an ancestor (like a refcount)
166168
* "all"
167169
168170
Defaults to "direct".
169171
`,
170172
},
171173

172174
Options: []cmds.Option{
173-
cmds.StringOption("type", "t", "The type of pinned keys to list. Can be \"direct\", \"recursive\", or \"all\". Defaults to \"direct\""),
175+
cmds.StringOption("type", "t", "The type of pinned keys to list. Can be \"direct\", \"indirect\", \"recursive\", or \"all\". Defaults to \"direct\""),
174176
cmds.BoolOption("quiet", "q", "Write just hashes of objects"),
175177
},
176178
Run: func(req cmds.Request, res cmds.Response) {
@@ -190,26 +192,45 @@ Defaults to "direct".
190192
}
191193

192194
switch typeStr {
193-
case "all", "direct", "recursive":
195+
case "all", "direct", "indirect", "recursive":
194196
default:
195-
err = fmt.Errorf("Invalid type '%s', must be one of {direct, recursive, all}", typeStr)
197+
err = fmt.Errorf("Invalid type '%s', must be one of {direct, indirect, recursive, all}", typeStr)
196198
res.SetError(err, cmds.ErrClient)
197199
}
198200

199201
keys := make(map[string]RefKeyObject)
200202
if typeStr == "direct" || typeStr == "all" {
201203
for _, k := range n.Pinning.DirectKeys() {
202204
keys[k.B58String()] = RefKeyObject{
203-
Type: "direct",
204-
Count: 1,
205+
Type: "direct",
206+
}
207+
}
208+
}
209+
if typeStr == "indirect" || typeStr == "all" {
210+
ks := key.NewKeySet()
211+
for _, k := range n.Pinning.RecursiveKeys() {
212+
nd, err := n.DAG.Get(n.Context(), k)
213+
if err != nil {
214+
res.SetError(err, cmds.ErrNormal)
215+
return
216+
}
217+
err = dag.EnumerateChildren(n.Context(), n.DAG, nd, ks)
218+
if err != nil {
219+
res.SetError(err, cmds.ErrNormal)
220+
return
221+
}
222+
223+
}
224+
for _, k := range ks.Keys() {
225+
keys[k.B58String()] = RefKeyObject{
226+
Type: "indirect",
205227
}
206228
}
207229
}
208230
if typeStr == "recursive" || typeStr == "all" {
209231
for _, k := range n.Pinning.RecursiveKeys() {
210232
keys[k.B58String()] = RefKeyObject{
211-
Type: "recursive",
212-
Count: 1,
233+
Type: "recursive",
213234
}
214235
}
215236
}
@@ -242,8 +263,7 @@ Defaults to "direct".
242263
}
243264

244265
type RefKeyObject struct {
245-
Type string
246-
Count uint64
266+
Type string
247267
}
248268

249269
type RefKeyList struct {

‎merkledag/merkledag.go

+21
Original file line numberDiff line numberDiff line change
@@ -313,3 +313,24 @@ func (np *nodePromise) Get(ctx context.Context) (*Node, error) {
313313
}
314314
return np.cache, nil
315315
}
316+
317+
// EnumerateChildren will walk the dag below the given root node and add all
318+
// unseen children to the passed in set.
319+
// TODO: parallelize to avoid disk latency perf hits?
320+
func EnumerateChildren(ctx context.Context, ds DAGService, root *Node, set key.KeySet) error {
321+
for _, lnk := range root.Links {
322+
k := key.Key(lnk.Hash)
323+
if !set.Has(k) {
324+
set.Add(k)
325+
child, err := ds.Get(ctx, k)
326+
if err != nil {
327+
return err
328+
}
329+
err = EnumerateChildren(ctx, ds, child, set)
330+
if err != nil {
331+
return err
332+
}
333+
}
334+
}
335+
return nil
336+
}

‎merkledag/merkledag_test.go

+38
Original file line numberDiff line numberDiff line change
@@ -252,3 +252,41 @@ func TestFetchGraphOther(t *testing.T) {
252252
t.Fatal(err)
253253
}
254254
}
255+
256+
func TestEnumerateChildren(t *testing.T) {
257+
bsi := bstest.Mocks(t, 1)
258+
ds := NewDAGService(bsi[0])
259+
260+
spl := &chunk.SizeSplitter{512}
261+
262+
read := io.LimitReader(u.NewTimeSeededRand(), 1024*1024)
263+
264+
root, err := imp.BuildDagFromReader(read, ds, spl)
265+
if err != nil {
266+
t.Fatal(err)
267+
}
268+
269+
ks := key.NewKeySet()
270+
err = EnumerateChildren(context.Background(), ds, root, ks)
271+
if err != nil {
272+
t.Fatal(err)
273+
}
274+
275+
var traverse func(n *Node)
276+
traverse = func(n *Node) {
277+
// traverse dag and check
278+
for _, lnk := range n.Links {
279+
k := key.Key(lnk.Hash)
280+
if !ks.Has(k) {
281+
t.Fatal("missing key in set!")
282+
}
283+
child, err := ds.Get(context.Background(), k)
284+
if err != nil {
285+
t.Fatal(err)
286+
}
287+
traverse(child)
288+
}
289+
}
290+
291+
traverse(root)
292+
}

‎pin/gc/gc.go

+19-40
Original file line numberDiff line numberDiff line change
@@ -14,42 +14,6 @@ import (
1414

1515
var log = eventlog.Logger("gc")
1616

17-
type GCSet struct {
18-
keys map[key.Key]struct{}
19-
}
20-
21-
func NewGCSet() *GCSet {
22-
return &GCSet{make(map[key.Key]struct{})}
23-
}
24-
25-
func (gcs *GCSet) Add(k key.Key) {
26-
gcs.keys[k] = struct{}{}
27-
}
28-
29-
func (gcs *GCSet) Has(k key.Key) bool {
30-
_, has := gcs.keys[k]
31-
return has
32-
}
33-
34-
func (gcs *GCSet) AddDag(ds dag.DAGService, root key.Key) error {
35-
ctx := context.Background()
36-
nd, err := ds.Get(ctx, root)
37-
if err != nil {
38-
return err
39-
}
40-
41-
gcs.Add(root)
42-
43-
for _, lnk := range nd.Links {
44-
k := key.Key(lnk.Hash)
45-
err := gcs.AddDag(ds, k)
46-
if err != nil {
47-
return err
48-
}
49-
}
50-
return nil
51-
}
52-
5317
// GC performs a mark and sweep garbage collection of the blocks in the blockstore
5418
// first, it creates a 'marked' set and adds to it the following:
5519
// - all recursively pinned blocks, plus all of their descendants (recursively)
@@ -68,11 +32,18 @@ func GC(ctx context.Context, bs bstore.GCBlockstore, pn pin.Pinner) (<-chan key.
6832
}
6933
ds := dag.NewDAGService(bsrv)
7034

71-
// GCSet currently implemented in memory, in the future, may be bloom filter or
35+
// KeySet currently implemented in memory, in the future, may be bloom filter or
7236
// disk backed to conserve memory.
73-
gcs := NewGCSet()
37+
gcs := key.NewKeySet()
7438
for _, k := range pn.RecursiveKeys() {
75-
err := gcs.AddDag(ds, k)
39+
gcs.Add(k)
40+
nd, err := ds.Get(ctx, k)
41+
if err != nil {
42+
return nil, err
43+
}
44+
45+
// EnumerateChildren recursively walks the dag and adds the keys to the given set
46+
err = dag.EnumerateChildren(ctx, ds, nd, gcs)
7647
if err != nil {
7748
return nil, err
7849
}
@@ -81,7 +52,15 @@ func GC(ctx context.Context, bs bstore.GCBlockstore, pn pin.Pinner) (<-chan key.
8152
gcs.Add(k)
8253
}
8354
for _, k := range pn.InternalPins() {
84-
err := gcs.AddDag(ds, k)
55+
gcs.Add(k)
56+
57+
nd, err := ds.Get(ctx, k)
58+
if err != nil {
59+
return nil, err
60+
}
61+
62+
// EnumerateChildren recursively walks the dag and adds the keys to the given set
63+
err = dag.EnumerateChildren(ctx, ds, nd, gcs)
8564
if err != nil {
8665
return nil, err
8766
}

‎test/sharness/t0080-repo.sh

+2-8
Original file line numberDiff line numberDiff line change
@@ -40,12 +40,8 @@ test_expect_success "'ipfs pin rm' output looks good" '
4040
'
4141

4242
test_expect_success "file no longer pinned" '
43-
# we expect the welcome files to show up here
44-
echo "$HASH_WELCOME_DOCS" >expected2 &&
45-
ipfs refs -r "$HASH_WELCOME_DOCS" >>expected2 &&
46-
echo QmUNLLsPACCz1vLxQVkXqqLX5R1X345qqfHbsf67hvA3Nn >> expected2 &&
4743
ipfs pin ls --type=recursive --quiet >actual2 &&
48-
test_sort_cmp expected2 actual2
44+
test_expect_code 1 grep $HASH actual2
4945
'
5046

5147
test_expect_success "recursively pin afile" '
@@ -97,8 +93,7 @@ test_expect_success "adding multiblock random file succeeds" '
9793
MBLOCKHASH=`ipfs add -q multiblock`
9894
'
9995

100-
# TODO: this starts to fail with the pinning rewrite, for unclear reasons
101-
test_expect_failure "'ipfs pin ls --type=indirect' is correct" '
96+
test_expect_success "'ipfs pin ls --type=indirect' is correct" '
10297
ipfs refs "$MBLOCKHASH" >refsout &&
10398
ipfs refs -r "$HASH_WELCOME_DOCS" >>refsout &&
10499
sed -i"~" "s/\(.*\)/\1 indirect/g" refsout &&
@@ -128,7 +123,6 @@ test_expect_success "'ipfs pin ls --type=recursive' is correct" '
128123
echo "$MBLOCKHASH" >rp_expected &&
129124
echo "$HASH_WELCOME_DOCS" >>rp_expected &&
130125
echo QmUNLLsPACCz1vLxQVkXqqLX5R1X345qqfHbsf67hvA3Nn >>rp_expected &&
131-
ipfs refs -r "$HASH_WELCOME_DOCS" >>rp_expected &&
132126
sed -i"~" "s/\(.*\)/\1 recursive/g" rp_expected &&
133127
ipfs pin ls --type=recursive >rp_actual &&
134128
test_sort_cmp rp_expected rp_actual

0 commit comments

Comments
 (0)
Please sign in to comment.