From 6a8c9b954de14ccdceddfb7671ba0516f96438e5 Mon Sep 17 00:00:00 2001 From: Matt Joiner Date: Mon, 28 Apr 2025 10:33:59 +1000 Subject: [PATCH] Expose PieceRequestOrder.Iter and PieceRequestOrderItem for debugging --- request-strategy/ajwerner-btree.go | 10 ++-- request-strategy/order.go | 22 ++++----- request-strategy/piece-request-order.go | 49 ++++++++++++-------- request-strategy/piece-request-order_test.go | 10 ++-- request-strategy/tidwall-btree.go | 10 ++-- 5 files changed, 56 insertions(+), 45 deletions(-) diff --git a/request-strategy/ajwerner-btree.go b/request-strategy/ajwerner-btree.go index 183e2b92..73ace303 100644 --- a/request-strategy/ajwerner-btree.go +++ b/request-strategy/ajwerner-btree.go @@ -5,14 +5,14 @@ import ( ) type ajwernerBtree struct { - btree btree.Set[pieceRequestOrderItem] + btree btree.Set[PieceRequestOrderItem] } var _ Btree = (*ajwernerBtree)(nil) func NewAjwernerBtree() *ajwernerBtree { return &ajwernerBtree{ - btree: btree.MakeSet(func(t, t2 pieceRequestOrderItem) int { + btree: btree.MakeSet(func(t, t2 PieceRequestOrderItem) int { return pieceOrderLess(&t, &t2).OrderingInt() }), } @@ -24,16 +24,16 @@ func mustValue[V any](b bool, panicValue V) { } } -func (a *ajwernerBtree) Delete(item pieceRequestOrderItem) { +func (a *ajwernerBtree) Delete(item PieceRequestOrderItem) { mustValue(a.btree.Delete(item), item) } -func (a *ajwernerBtree) Add(item pieceRequestOrderItem) { +func (a *ajwernerBtree) Add(item PieceRequestOrderItem) { _, overwrote := a.btree.Upsert(item) mustValue(!overwrote, item) } -func (a *ajwernerBtree) Scan(f func(pieceRequestOrderItem) bool) { +func (a *ajwernerBtree) Scan(f func(PieceRequestOrderItem) bool) { it := a.btree.Iterator() it.First() for it.First(); it.Valid(); it.Next() { diff --git a/request-strategy/order.go b/request-strategy/order.go index 9f0295c6..6aa1b402 100644 --- a/request-strategy/order.go +++ b/request-strategy/order.go @@ -19,22 +19,22 @@ type ( ChunkSpec = types.ChunkSpec ) -func pieceOrderLess(i, j *pieceRequestOrderItem) multiless.Computation { +func pieceOrderLess(i, j *PieceRequestOrderItem) multiless.Computation { return multiless.New().Int( - int(j.state.Priority), int(i.state.Priority), + int(j.State.Priority), int(i.State.Priority), // TODO: Should we match on complete here to prevent churn when availability changes? ).Bool( - j.state.Partial, i.state.Partial, + j.State.Partial, i.State.Partial, ).Int( // If this is done with relative availability, do we lose some determinism? If completeness // is used, would that push this far enough down? - i.state.Availability, j.state.Availability, + i.State.Availability, j.State.Availability, ).Int( - i.key.Index, j.key.Index, + i.Key.Index, j.Key.Index, ).Lazy(func() multiless.Computation { return multiless.New().Cmp(bytes.Compare( - i.key.InfoHash[:], - j.key.InfoHash[:], + i.Key.InfoHash[:], + j.Key.InfoHash[:], )) }) } @@ -55,10 +55,10 @@ func GetRequestablePieces( allTorrentsUnverifiedBytes int64 maxUnverifiedBytes = input.MaxUnverifiedBytes() ) - pro.tree.Scan(func(item pieceRequestOrderItem) bool { - ih := item.key.InfoHash + pro.tree.Scan(func(item PieceRequestOrderItem) bool { + ih := item.Key.InfoHash var t = input.Torrent(ih) - var piece = t.Piece(item.key.Index) + var piece = t.Piece(item.Key.Index) pieceLength := t.PieceLength() // Storage limits will always apply against requestable pieces, since we need to keep the // highest priority pieces, even if they're complete or in an undesirable state. @@ -69,7 +69,7 @@ func GetRequestablePieces( *storageLeft -= pieceLength } if piece.Request() { - if !requestPiece(ih, item.key.Index, item.state) { + if !requestPiece(ih, item.Key.Index, item.State) { // No blocks are being considered from this piece, so it won't result in unverified // bytes. return true diff --git a/request-strategy/piece-request-order.go b/request-strategy/piece-request-order.go index 0e279772..7f271ee3 100644 --- a/request-strategy/piece-request-order.go +++ b/request-strategy/piece-request-order.go @@ -2,14 +2,15 @@ package requestStrategy import ( g "github.com/anacrolix/generics" + "iter" "github.com/anacrolix/torrent/metainfo" ) type Btree interface { - Delete(pieceRequestOrderItem) - Add(pieceRequestOrderItem) - Scan(func(pieceRequestOrderItem) bool) + Delete(PieceRequestOrderItem) + Add(PieceRequestOrderItem) + Scan(func(PieceRequestOrderItem) bool) } func NewPieceOrder(btree Btree, cap int) *PieceRequestOrder { @@ -35,16 +36,16 @@ type PieceRequestOrderState struct { Partial bool } -type pieceRequestOrderItem struct { - key PieceRequestOrderKey - state PieceRequestOrderState +type PieceRequestOrderItem struct { + Key PieceRequestOrderKey + State PieceRequestOrderState } -func (me *pieceRequestOrderItem) Less(otherConcrete *pieceRequestOrderItem) bool { +func (me *PieceRequestOrderItem) Less(otherConcrete *PieceRequestOrderItem) bool { return pieceOrderLess(me, otherConcrete).Less() } -// Returns the old state if the key was already present. +// Returns the old state if the key was already present. The Update method needs to look at it. func (me *PieceRequestOrder) Add( key PieceRequestOrderKey, state PieceRequestOrderState, @@ -53,9 +54,9 @@ func (me *PieceRequestOrder) Add( if state == old.Value { return } - me.tree.Delete(pieceRequestOrderItem{key, old.Value}) + me.tree.Delete(PieceRequestOrderItem{key, old.Value}) } - me.tree.Add(pieceRequestOrderItem{key, state}) + me.tree.Add(PieceRequestOrderItem{key, state}) me.keys[key] = state return } @@ -63,25 +64,27 @@ func (me *PieceRequestOrder) Add( func (me *PieceRequestOrder) Update( key PieceRequestOrderKey, state PieceRequestOrderState, -) { - if !me.Add(key, state).Ok { - panic("key should have been added already") +) (changed bool) { + old := me.Add(key, state) + if !old.Ok { + panic("Key should have been added already") } + return old.Value != state } -func (me *PieceRequestOrder) existingItemForKey(key PieceRequestOrderKey) pieceRequestOrderItem { - return pieceRequestOrderItem{ - key: key, - state: me.keys[key], +func (me *PieceRequestOrder) existingItemForKey(key PieceRequestOrderKey) PieceRequestOrderItem { + return PieceRequestOrderItem{ + Key: key, + State: me.keys[key], } } -func (me *PieceRequestOrder) Delete(key PieceRequestOrderKey) bool { +func (me *PieceRequestOrder) Delete(key PieceRequestOrderKey) (deleted bool) { state, ok := me.keys[key] if !ok { return false } - me.tree.Delete(pieceRequestOrderItem{key, state}) + me.tree.Delete(PieceRequestOrderItem{key, state}) delete(me.keys, key) return true } @@ -89,3 +92,11 @@ func (me *PieceRequestOrder) Delete(key PieceRequestOrderKey) bool { func (me *PieceRequestOrder) Len() int { return len(me.keys) } + +func (me *PieceRequestOrder) Iter() iter.Seq[PieceRequestOrderItem] { + return func(yield func(PieceRequestOrderItem) bool) { + me.tree.Scan(func(item PieceRequestOrderItem) bool { + return yield(item) + }) + } +} diff --git a/request-strategy/piece-request-order_test.go b/request-strategy/piece-request-order_test.go index 818b2414..b38e50d2 100644 --- a/request-strategy/piece-request-order_test.go +++ b/request-strategy/piece-request-order_test.go @@ -36,7 +36,7 @@ func benchmarkPieceRequestOrder[B Btree]( pro.Update(key, state) return true }) - pro.tree.Scan(func(item pieceRequestOrderItem) bool { + pro.tree.Scan(func(item PieceRequestOrderItem) bool { return true }) doPieces(func(key PieceRequestOrderKey) bool { @@ -44,8 +44,8 @@ func benchmarkPieceRequestOrder[B Btree]( pro.Update(key, state) return true }) - pro.tree.Scan(func(item pieceRequestOrderItem) bool { - return item.key.Index < 1000 + pro.tree.Scan(func(item PieceRequestOrderItem) bool { + return item.Key.Index < 1000 }) state.Priority = 0 state.Availability++ @@ -53,8 +53,8 @@ func benchmarkPieceRequestOrder[B Btree]( pro.Update(key, state) return true }) - pro.tree.Scan(func(item pieceRequestOrderItem) bool { - return item.key.Index < 1000 + pro.tree.Scan(func(item PieceRequestOrderItem) bool { + return item.Key.Index < 1000 }) state.Availability-- doPieces(func(key PieceRequestOrderKey) bool { diff --git a/request-strategy/tidwall-btree.go b/request-strategy/tidwall-btree.go index f7eabcdc..88bbafd2 100644 --- a/request-strategy/tidwall-btree.go +++ b/request-strategy/tidwall-btree.go @@ -5,25 +5,25 @@ import ( ) type tidwallBtree struct { - tree *btree.BTreeG[pieceRequestOrderItem] + tree *btree.BTreeG[PieceRequestOrderItem] PathHint *btree.PathHint } -func (me *tidwallBtree) Scan(f func(pieceRequestOrderItem) bool) { +func (me *tidwallBtree) Scan(f func(PieceRequestOrderItem) bool) { me.tree.Scan(f) } func NewTidwallBtree() *tidwallBtree { return &tidwallBtree{ tree: btree.NewBTreeGOptions( - func(a, b pieceRequestOrderItem) bool { + func(a, b PieceRequestOrderItem) bool { return a.Less(&b) }, btree.Options{NoLocks: true, Degree: 64}), } } -func (me *tidwallBtree) Add(item pieceRequestOrderItem) { +func (me *tidwallBtree) Add(item PieceRequestOrderItem) { if _, ok := me.tree.SetHint(item, me.PathHint); ok { panic("shouldn't already have this") } @@ -31,7 +31,7 @@ func (me *tidwallBtree) Add(item pieceRequestOrderItem) { type PieceRequestOrderPathHint = btree.PathHint -func (me *tidwallBtree) Delete(item pieceRequestOrderItem) { +func (me *tidwallBtree) Delete(item PieceRequestOrderItem) { _, deleted := me.tree.DeleteHint(item, me.PathHint) mustValue(deleted, item) } -- 2.48.1