This repository has been archived by the owner on Jun 27, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 54
/
hamt.go
678 lines (561 loc) · 15.8 KB
/
hamt.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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
// Package hamt implements a Hash Array Mapped Trie over ipfs merkledag nodes.
// It is implemented mostly as described in the wikipedia article on HAMTs,
// however the table size is variable (usually 256 in our usages) as opposed to
// 32 as suggested in the article. The hash function used is currently
// Murmur3, but this value is configurable (the datastructure reports which
// hash function its using).
//
// The one algorithmic change we implement that is not mentioned in the
// wikipedia article is the collapsing of empty shards.
// Given the following tree: ( '[' = shards, '{' = values )
// [ 'A' ] -> [ 'B' ] -> { "ABC" }
// | L-> { "ABD" }
// L-> { "ASDF" }
// If we simply removed "ABC", we would end up with a tree where shard 'B' only
// has a single child. This causes two issues, the first, is that now we have
// an extra lookup required to get to "ABD". The second issue is that now we
// have a tree that contains only "ABD", but is not the same tree that we would
// get by simply inserting "ABD" into a new tree. To address this, we always
// check for empty shard nodes upon deletion and prune them to maintain a
// consistent tree, independent of insertion order.
package hamt
import (
"context"
"fmt"
"os"
bitfield "github.com/Stebalien/go-bitfield"
cid "github.com/ipfs/go-cid"
ipld "github.com/ipfs/go-ipld-format"
dag "github.com/ipfs/go-merkledag"
format "github.com/ipfs/go-unixfs"
)
const (
// HashMurmur3 is the multiformats identifier for Murmur3
HashMurmur3 uint64 = 0x22
)
func (ds *Shard) isValueNode() bool {
return ds.key != "" && ds.val != nil
}
// A Shard represents the HAMT. It should be initialized with NewShard().
type Shard struct {
cid cid.Cid
childer *childer
tableSize int
tableSizeLg2 int
builder cid.Builder
hashFunc uint64
prefixPadStr string
maxpadlen int
dserv ipld.DAGService
// leaf node
key string
val *ipld.Link
}
// NewShard creates a new, empty HAMT shard with the given size.
func NewShard(dserv ipld.DAGService, size int) (*Shard, error) {
ds, err := makeShard(dserv, size)
if err != nil {
return nil, err
}
ds.hashFunc = HashMurmur3
return ds, nil
}
func makeShard(ds ipld.DAGService, size int) (*Shard, error) {
lg2s, err := logtwo(size)
if err != nil {
return nil, err
}
maxpadding := fmt.Sprintf("%X", size-1)
s := &Shard{
tableSizeLg2: lg2s,
prefixPadStr: fmt.Sprintf("%%0%dX", len(maxpadding)),
maxpadlen: len(maxpadding),
childer: newChilder(ds, size),
tableSize: size,
dserv: ds,
}
s.childer.sd = s
return s, nil
}
// NewHamtFromDag creates new a HAMT shard from the given DAG.
func NewHamtFromDag(dserv ipld.DAGService, nd ipld.Node) (*Shard, error) {
pbnd, ok := nd.(*dag.ProtoNode)
if !ok {
return nil, dag.ErrNotProtobuf
}
fsn, err := format.FSNodeFromBytes(pbnd.Data())
if err != nil {
return nil, err
}
if fsn.Type() != format.THAMTShard {
return nil, fmt.Errorf("node was not a dir shard")
}
if fsn.HashType() != HashMurmur3 {
return nil, fmt.Errorf("only murmur3 supported as hash function")
}
size := int(fsn.Fanout())
ds, err := makeShard(dserv, size)
if err != nil {
return nil, err
}
ds.childer.makeChilder(fsn.Data(), pbnd.Links())
ds.cid = pbnd.Cid()
ds.hashFunc = fsn.HashType()
ds.builder = pbnd.CidBuilder()
return ds, nil
}
// SetCidBuilder sets the CID Builder
func (ds *Shard) SetCidBuilder(builder cid.Builder) {
ds.builder = builder
}
// CidBuilder gets the CID Builder, may be nil if unset
func (ds *Shard) CidBuilder() cid.Builder {
return ds.builder
}
// Node serializes the HAMT structure into a merkledag node with unixfs formatting
func (ds *Shard) Node() (ipld.Node, error) {
out := new(dag.ProtoNode)
out.SetCidBuilder(ds.builder)
sliceIndex := 0
// TODO: optimized 'for each set bit'
for childIndex := 0; childIndex < ds.tableSize; childIndex++ {
if !ds.childer.has(childIndex) {
continue
}
ch := ds.childer.child(sliceIndex)
if ch != nil {
clnk, err := ch.Link()
if err != nil {
return nil, err
}
err = out.AddRawLink(ds.linkNamePrefix(childIndex)+ch.key, clnk)
if err != nil {
return nil, err
}
} else {
// child unloaded, just copy in link with updated name
lnk := ds.childer.link(sliceIndex)
label := lnk.Name[ds.maxpadlen:]
err := out.AddRawLink(ds.linkNamePrefix(childIndex)+label, lnk)
if err != nil {
return nil, err
}
}
sliceIndex++
}
data, err := format.HAMTShardData(ds.childer.bitfield.Bytes(), uint64(ds.tableSize), HashMurmur3)
if err != nil {
return nil, err
}
out.SetData(data)
err = ds.dserv.Add(context.TODO(), out)
if err != nil {
return nil, err
}
return out, nil
}
func (ds *Shard) makeShardValue(lnk *ipld.Link) (*Shard, error) {
lnk2 := *lnk
s, err := makeShard(ds.dserv, ds.tableSize)
if err != nil {
return nil, err
}
s.key = lnk.Name[ds.maxpadlen:]
s.val = &lnk2
return s, nil
}
// Set sets 'name' = nd in the HAMT
func (ds *Shard) Set(ctx context.Context, name string, nd ipld.Node) error {
hv := &hashBits{b: hash([]byte(name))}
err := ds.dserv.Add(ctx, nd)
if err != nil {
return err
}
lnk, err := ipld.MakeLink(nd)
if err != nil {
return err
}
lnk.Name = ds.linkNamePrefix(0) + name
return ds.modifyValue(ctx, hv, name, lnk)
}
// Remove deletes the named entry if it exists. Otherwise, it returns
// os.ErrNotExist.
func (ds *Shard) Remove(ctx context.Context, name string) error {
hv := &hashBits{b: hash([]byte(name))}
return ds.modifyValue(ctx, hv, name, nil)
}
// Find searches for a child node by 'name' within this hamt
func (ds *Shard) Find(ctx context.Context, name string) (*ipld.Link, error) {
hv := &hashBits{b: hash([]byte(name))}
var out *ipld.Link
err := ds.getValue(ctx, hv, name, func(sv *Shard) error {
out = sv.val
return nil
})
if err != nil {
return nil, err
}
return out, nil
}
type linkType int
const (
invalidLink linkType = iota
shardLink
shardValueLink
)
func (ds *Shard) childLinkType(lnk *ipld.Link) (linkType, error) {
if len(lnk.Name) < ds.maxpadlen {
return invalidLink, fmt.Errorf("invalid link name '%s'", lnk.Name)
}
if len(lnk.Name) == ds.maxpadlen {
return shardLink, nil
}
return shardValueLink, nil
}
// Link returns a merklelink to this shard node
func (ds *Shard) Link() (*ipld.Link, error) {
if ds.isValueNode() {
return ds.val, nil
}
nd, err := ds.Node()
if err != nil {
return nil, err
}
err = ds.dserv.Add(context.TODO(), nd)
if err != nil {
return nil, err
}
return ipld.MakeLink(nd)
}
func (ds *Shard) getValue(ctx context.Context, hv *hashBits, key string, cb func(*Shard) error) error {
childIndex, err := hv.Next(ds.tableSizeLg2)
if err != nil {
return err
}
if ds.childer.has(childIndex) {
child, err := ds.childer.get(ctx, ds.childer.sliceIndex(childIndex))
if err != nil {
return err
}
if child.isValueNode() {
if child.key == key {
return cb(child)
}
} else {
return child.getValue(ctx, hv, key, cb)
}
}
return os.ErrNotExist
}
// EnumLinks collects all links in the Shard.
func (ds *Shard) EnumLinks(ctx context.Context) ([]*ipld.Link, error) {
var links []*ipld.Link
linkResults := ds.EnumLinksAsync(ctx)
for linkResult := range linkResults {
if linkResult.Err != nil {
return links, linkResult.Err
}
links = append(links, linkResult.Link)
}
return links, nil
}
// ForEachLink walks the Shard and calls the given function.
func (ds *Shard) ForEachLink(ctx context.Context, f func(*ipld.Link) error) error {
return ds.walkTrie(ctx, func(sv *Shard) error {
lnk := sv.val
lnk.Name = sv.key
return f(lnk)
})
}
// EnumLinksAsync returns a channel which will receive Links in the directory
// as they are enumerated, where order is not guaranteed
func (ds *Shard) EnumLinksAsync(ctx context.Context) <-chan format.LinkResult {
linkResults := make(chan format.LinkResult)
ctx, cancel := context.WithCancel(ctx)
go func() {
defer close(linkResults)
defer cancel()
getLinks := makeAsyncTrieGetLinks(ds.dserv, linkResults)
cset := cid.NewSet()
err := dag.Walk(ctx, getLinks, ds.cid, cset.Visit, dag.Concurrent())
if err != nil {
emitResult(ctx, linkResults, format.LinkResult{Link: nil, Err: err})
}
}()
return linkResults
}
// makeAsyncTrieGetLinks builds a getLinks function that can be used with EnumerateChildrenAsync
// to iterate a HAMT shard. It takes an IPLD Dag Service to fetch nodes, and a call back that will get called
// on all links to leaf nodes in a HAMT tree, so they can be collected for an EnumLinks operation
func makeAsyncTrieGetLinks(dagService ipld.DAGService, linkResults chan<- format.LinkResult) dag.GetLinks {
return func(ctx context.Context, currentCid cid.Cid) ([]*ipld.Link, error) {
node, err := dagService.Get(ctx, currentCid)
if err != nil {
return nil, err
}
directoryShard, err := NewHamtFromDag(dagService, node)
if err != nil {
return nil, err
}
childShards := make([]*ipld.Link, 0, directoryShard.childer.length())
links := directoryShard.childer.links
for idx := range directoryShard.childer.children {
lnk := links[idx]
lnkLinkType, err := directoryShard.childLinkType(lnk)
if err != nil {
return nil, err
}
if lnkLinkType == shardLink {
childShards = append(childShards, lnk)
} else {
sv, err := directoryShard.makeShardValue(lnk)
if err != nil {
return nil, err
}
formattedLink := sv.val
formattedLink.Name = sv.key
emitResult(ctx, linkResults, format.LinkResult{Link: formattedLink, Err: nil})
}
}
return childShards, nil
}
}
func emitResult(ctx context.Context, linkResults chan<- format.LinkResult, r format.LinkResult) {
// make sure that context cancel is processed first
// the reason is due to the concurrency of EnumerateChildrenAsync
// it's possible for EnumLinksAsync to complete and close the linkResults
// channel before this code runs
select {
case <-ctx.Done():
return
default:
}
select {
case linkResults <- r:
case <-ctx.Done():
}
}
func (ds *Shard) walkTrie(ctx context.Context, cb func(*Shard) error) error {
return ds.childer.each(ctx, func(s *Shard) error {
if s.isValueNode() {
if err := cb(s); err != nil {
return err
}
} else {
if err := s.walkTrie(ctx, cb); err != nil {
return err
}
}
return nil
})
}
func (ds *Shard) modifyValue(ctx context.Context, hv *hashBits, key string, val *ipld.Link) error {
idx, err := hv.Next(ds.tableSizeLg2)
if err != nil {
return err
}
if !ds.childer.has(idx) {
return ds.childer.insert(key, val, idx)
}
i := ds.childer.sliceIndex(idx)
child, err := ds.childer.get(ctx, i)
if err != nil {
return err
}
if child.isValueNode() {
if child.key == key {
// value modification
if val == nil {
return ds.childer.rm(idx)
}
child.val = val
return nil
}
if val == nil {
return os.ErrNotExist
}
// replace value with another shard, one level deeper
ns, err := NewShard(ds.dserv, ds.tableSize)
if err != nil {
return err
}
ns.builder = ds.builder
chhv := &hashBits{
b: hash([]byte(child.key)),
consumed: hv.consumed,
}
err = ns.modifyValue(ctx, hv, key, val)
if err != nil {
return err
}
err = ns.modifyValue(ctx, chhv, child.key, child.val)
if err != nil {
return err
}
ds.childer.set(ns, i)
return nil
} else {
err := child.modifyValue(ctx, hv, key, val)
if err != nil {
return err
}
if val == nil {
switch child.childer.length() {
case 0:
// empty sub-shard, prune it
// Note: this shouldnt normally ever happen
// in the event of another implementation creates flawed
// structures, this will help to normalize them.
return ds.childer.rm(idx)
case 1:
nchild := child.childer.children[0]
if nchild.isValueNode() {
// sub-shard with a single value element, collapse it
ds.childer.set(nchild, i)
}
return nil
}
}
return nil
}
}
// linkNamePrefix takes in the bitfield index of an entry and returns its hex prefix
func (ds *Shard) linkNamePrefix(idx int) string {
return fmt.Sprintf(ds.prefixPadStr, idx)
}
// childer wraps the links, children and bitfield
// and provides basic operation (get, rm, insert and set) of manipulating children.
// The slices `links` and `children` are always coordinated to have the entries
// in the same index. A `childIndex` belonging to one of the original `Shard.size`
// entries corresponds to a `sliceIndex` in `links` and `children` (the conversion
// is done through `bitfield`).
type childer struct {
sd *Shard
dserv ipld.DAGService
bitfield bitfield.Bitfield
links []*ipld.Link
children []*Shard
}
func newChilder(ds ipld.DAGService, size int) *childer {
return &childer{
dserv: ds,
bitfield: bitfield.NewBitfield(size),
}
}
func (s *childer) makeChilder(data []byte, links []*ipld.Link) *childer {
s.children = make([]*Shard, len(links))
s.bitfield.SetBytes(data)
if len(links) > 0 {
s.links = make([]*ipld.Link, len(links))
copy(s.links, links)
}
return s
}
// Return the `sliceIndex` associated with a child.
func (s *childer) sliceIndex(childIndex int) (sliceIndex int) {
return s.bitfield.OnesBefore(childIndex)
}
func (s *childer) child(sliceIndex int) *Shard {
return s.children[sliceIndex]
}
func (s *childer) link(sliceIndex int) *ipld.Link {
return s.links[sliceIndex]
}
func (s *childer) insert(key string, lnk *ipld.Link, idx int) error {
if lnk == nil {
return os.ErrNotExist
}
lnk.Name = s.sd.linkNamePrefix(idx) + key
i := s.sliceIndex(idx)
sd := &Shard{key: key, val: lnk}
s.children = append(s.children[:i], append([]*Shard{sd}, s.children[i:]...)...)
s.links = append(s.links[:i], append([]*ipld.Link{nil}, s.links[i:]...)...)
// Add a `nil` placeholder in `links` so the rest of the entries keep the same
// index as `children`.
s.bitfield.SetBit(idx)
return nil
}
func (s *childer) set(sd *Shard, i int) {
s.children[i] = sd
}
func (s *childer) rm(childIndex int) error {
i := s.sliceIndex(childIndex)
if err := s.check(i); err != nil {
return err
}
copy(s.children[i:], s.children[i+1:])
s.children = s.children[:len(s.children)-1]
copy(s.links[i:], s.links[i+1:])
s.links = s.links[:len(s.links)-1]
s.bitfield.UnsetBit(childIndex)
return nil
}
// get returns the i'th child of this shard. If it is cached in the
// children array, it will return it from there. Otherwise, it loads the child
// node from disk.
func (s *childer) get(ctx context.Context, sliceIndex int) (*Shard, error) {
if err := s.check(sliceIndex); err != nil {
return nil, err
}
c := s.child(sliceIndex)
if c != nil {
return c, nil
}
return s.loadChild(ctx, sliceIndex)
}
// loadChild reads the i'th child node of this shard from disk and returns it
// as a 'child' interface
func (s *childer) loadChild(ctx context.Context, sliceIndex int) (*Shard, error) {
lnk := s.link(sliceIndex)
lnkLinkType, err := s.sd.childLinkType(lnk)
if err != nil {
return nil, err
}
var c *Shard
if lnkLinkType == shardLink {
nd, err := lnk.GetNode(ctx, s.dserv)
if err != nil {
return nil, err
}
cds, err := NewHamtFromDag(s.dserv, nd)
if err != nil {
return nil, err
}
c = cds
} else {
s, err := s.sd.makeShardValue(lnk)
if err != nil {
return nil, err
}
c = s
}
s.set(c, sliceIndex)
return c, nil
}
func (s *childer) has(childIndex int) bool {
return s.bitfield.Bit(childIndex)
}
func (s *childer) length() int {
return len(s.children)
}
func (s *childer) each(ctx context.Context, cb func(*Shard) error) error {
for i := range s.children {
c, err := s.get(ctx, i)
if err != nil {
return err
}
if err := cb(c); err != nil {
return err
}
}
return nil
}
func (s *childer) check(sliceIndex int) error {
if sliceIndex >= len(s.children) || sliceIndex < 0 {
return fmt.Errorf("invalid index passed to operate children (likely corrupt bitfield)")
}
if len(s.children) != len(s.links) {
return fmt.Errorf("inconsistent lengths between children array and Links array")
}
return nil
}