request-strategy/order.go

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