request-strategy/order.go

   1 package requestStrategy
   2
   3 import (
   4         "bytes"
   5         "expvar"
   6
   7         g "github.com/anacrolix/generics"
   8         "github.com/anacrolix/multiless"
   9
  10         "github.com/anacrolix/torrent/metainfo"
  11         "github.com/anacrolix/torrent/types"
  12 )
  13
  14 type (
  15         RequestIndex  uint32
  16         ChunkIndex    = RequestIndex
  17         Request       = types.Request
  18         pieceIndex    = types.PieceIndex
  19         piecePriority = types.PiecePriority
  20         // This can be made into a type-param later, will be great for testing.
  21         ChunkSpec = types.ChunkSpec
  22 )
  23
  24 func pieceOrderLess(i, j *pieceRequestOrderItem) multiless.Computation {
  25         return multiless.New().Int(
  26                 int(j.state.Priority), int(i.state.Priority),
  27                 // TODO: Should we match on complete here to prevent churn when availability changes?
  28         ).Bool(
  29                 j.state.Partial, i.state.Partial,
  30         ).Int(
  31                 // If this is done with relative availability, do we lose some determinism? If completeness
  32                 // is used, would that push this far enough down?
  33                 i.state.Availability, j.state.Availability,
  34         ).Int(
  35                 i.key.Index, j.key.Index,
  36         ).Lazy(func() multiless.Computation {
  37                 return multiless.New().Cmp(bytes.Compare(
  38                         i.key.InfoHash[:],
  39                         j.key.InfoHash[:],
  40                 ))
  41         })
  42 }
  43
  44 var packageExpvarMap = expvar.NewMap("request-strategy")
  45
  46 // Calls f with requestable pieces in order.
  47 func GetRequestablePieces(
  48         input Input, pro *PieceRequestOrder,
  49         f func(ih metainfo.Hash, pieceIndex int, orderState PieceRequestOrderState),
  50 ) {
  51         // Storage capacity left for this run, keyed by the storage capacity pointer on the storage
  52         // TorrentImpl. A nil value means no capacity limit.
  53         var storageLeft *int64
  54         if cap, ok := input.Capacity(); ok {
  55                 storageLeft = &cap
  56         }
  57         var allTorrentsUnverifiedBytes int64
  58         var lastItem g.Option[pieceRequestOrderItem]
  59         pro.tree.Scan(func(_i pieceRequestOrderItem) bool {
  60                 // Check that scan emits pieces in priority order.
  61                 if lastItem.Ok {
  62                         if _i.Less(&lastItem.Value) {
  63                                 panic("scan not in order")
  64                         }
  65                 }
  66                 lastItem.Set(_i)
  67
  68                 ih := _i.key.InfoHash
  69                 t := input.Torrent(ih)
  70                 pieceLength := t.PieceLength()
  71                 if storageLeft != nil {
  72                         if *storageLeft < pieceLength {
  73                                 return false
  74                         }
  75                         *storageLeft -= pieceLength
  76                 }
  77                 if t.IgnorePiece(_i.key.Index) {
  78                         // TODO: Clarify exactly what is verified. Stuff that's being hashed should be
  79                         // considered unverified and hold up further requests.
  80                         return true
  81                 }
  82                 if input.MaxUnverifiedBytes() != 0 && allTorrentsUnverifiedBytes+pieceLength > input.MaxUnverifiedBytes() {
  83                         return true
  84                 }
  85                 allTorrentsUnverifiedBytes += pieceLength
  86                 f(ih, _i.key.Index, _i.state)
  87                 return true
  88         })
  89         return
  90 }
  91
  92 type Input interface {
  93         Torrent(metainfo.Hash) Torrent
  94         // Storage capacity, shared among all Torrents with the same storage.TorrentCapacity pointer in
  95         // their storage.Torrent references.
  96         Capacity() (cap int64, capped bool)
  97         // Across all the Torrents. This might be partitioned by storage capacity key now.
  98         MaxUnverifiedBytes() int64
  99 }