request-strategy/order_test.go

   1 package request_strategy
   2
   3 import (
   4         "math"
   5         "testing"
   6
   7         "github.com/bradfitz/iter"
   8         qt "github.com/frankban/quicktest"
   9
  10         pp "github.com/anacrolix/torrent/peer_protocol"
  11 )
  12
  13 func r(i pieceIndex, begin int) Request {
  14         return Request{pp.Integer(i), ChunkSpec{pp.Integer(begin), 1}}
  15 }
  16
  17 func chunkIterRange(end int) func(func(ChunkSpec)) {
  18         return func(f func(ChunkSpec)) {
  19                 for offset := range iter.N(end) {
  20                         f(ChunkSpec{pp.Integer(offset), 1})
  21                 }
  22         }
  23 }
  24
  25 func chunkIter(offsets ...int) func(func(ChunkSpec)) {
  26         return func(f func(ChunkSpec)) {
  27                 for _, offset := range offsets {
  28                         f(ChunkSpec{pp.Integer(offset), 1})
  29                 }
  30         }
  31 }
  32
  33 func requestSetFromSlice(rs ...Request) (ret map[Request]struct{}) {
  34         ret = make(map[Request]struct{}, len(rs))
  35         for _, r := range rs {
  36                 ret[r] = struct{}{}
  37         }
  38         return
  39 }
  40
  41 type intPeerId int
  42
  43 func (i intPeerId) Uintptr() uintptr {
  44         return uintptr(i)
  45 }
  46
  47 func TestStealingFromSlowerPeer(t *testing.T) {
  48         c := qt.New(t)
  49         basePeer := Peer{
  50                 HasPiece: func(i pieceIndex) bool {
  51                         return true
  52                 },
  53                 MaxRequests:  math.MaxInt16,
  54                 DownloadRate: 2,
  55         }
  56         // Slower than the stealers, but has all requests already.
  57         stealee := basePeer
  58         stealee.DownloadRate = 1
  59         stealee.HasExistingRequest = func(r Request) bool {
  60                 return true
  61         }
  62         stealee.Id = intPeerId(1)
  63         firstStealer := basePeer
  64         firstStealer.Id = intPeerId(2)
  65         secondStealer := basePeer
  66         secondStealer.Id = intPeerId(3)
  67         results := Run(Input{Torrents: []Torrent{{
  68                 Pieces: []Piece{{
  69                         Request:           true,
  70                         NumPendingChunks:  5,
  71                         IterPendingChunks: chunkIterRange(5),
  72                 }},
  73                 Peers: []Peer{
  74                         stealee,
  75                         firstStealer,
  76                         secondStealer,
  77                 },
  78         }}})
  79
  80         c.Assert(results, qt.HasLen, 3)
  81         check := func(p PeerId, l int) {
  82                 c.Check(results[p].Requests, qt.HasLen, l)
  83                 c.Check(results[p].Interested, qt.Equals, l > 0)
  84         }
  85         check(stealee.Id, 1)
  86         check(firstStealer.Id, 2)
  87         check(secondStealer.Id, 2)
  88 }
  89
  90 func checkNumRequestsAndInterest(c *qt.C, next PeerNextRequestState, num int, interest bool) {
  91         c.Check(next.Requests, qt.HasLen, num)
  92         c.Check(next.Interested, qt.Equals, interest)
  93 }
  94
  95 func TestStealingFromSlowerPeersBasic(t *testing.T) {
  96         c := qt.New(t)
  97         basePeer := Peer{
  98                 HasPiece: func(i pieceIndex) bool {
  99                         return true
 100                 },
 101                 MaxRequests:  math.MaxInt16,
 102                 DownloadRate: 2,
 103         }
 104         stealee := basePeer
 105         stealee.DownloadRate = 1
 106         stealee.HasExistingRequest = func(r Request) bool {
 107                 return true
 108         }
 109         stealee.Id = intPeerId(1)
 110         firstStealer := basePeer
 111         firstStealer.Id = intPeerId(2)
 112         secondStealer := basePeer
 113         secondStealer.Id = intPeerId(3)
 114         results := Run(Input{Torrents: []Torrent{{
 115                 Pieces: []Piece{{
 116                         Request:           true,
 117                         NumPendingChunks:  2,
 118                         IterPendingChunks: chunkIter(0, 1),
 119                 }},
 120                 Peers: []Peer{
 121                         stealee,
 122                         firstStealer,
 123                         secondStealer,
 124                 },
 125         }}})
 126
 127         checkNumRequestsAndInterest(c, results[firstStealer.Id], 1, true)
 128         checkNumRequestsAndInterest(c, results[secondStealer.Id], 1, true)
 129         checkNumRequestsAndInterest(c, results[stealee.Id], 0, false)
 130 }
 131
 132 func TestPeerKeepsExistingIfReasonable(t *testing.T) {
 133         c := qt.New(t)
 134         basePeer := Peer{
 135                 HasPiece: func(i pieceIndex) bool {
 136                         return true
 137                 },
 138                 MaxRequests:  math.MaxInt16,
 139                 DownloadRate: 2,
 140         }
 141         // Slower than the stealers, but has all requests already.
 142         stealee := basePeer
 143         stealee.DownloadRate = 1
 144         keepReq := r(0, 0)
 145         stealee.HasExistingRequest = func(r Request) bool {
 146                 return r == keepReq
 147         }
 148         stealee.Id = intPeerId(1)
 149         firstStealer := basePeer
 150         firstStealer.Id = intPeerId(2)
 151         secondStealer := basePeer
 152         secondStealer.Id = intPeerId(3)
 153         results := Run(Input{Torrents: []Torrent{{
 154                 Pieces: []Piece{{
 155                         Request:           true,
 156                         NumPendingChunks:  4,
 157                         IterPendingChunks: chunkIter(0, 1, 3, 4),
 158                 }},
 159                 Peers: []Peer{
 160                         stealee,
 161                         firstStealer,
 162                         secondStealer,
 163                 },
 164         }}})
 165
 166         c.Assert(results, qt.HasLen, 3)
 167         check := func(p PeerId, l int) {
 168                 c.Check(results[p].Requests, qt.HasLen, l)
 169                 c.Check(results[p].Interested, qt.Equals, l > 0)
 170         }
 171         check(firstStealer.Id, 2)
 172         check(secondStealer.Id, 1)
 173         c.Check(results[stealee.Id], qt.ContentEquals, PeerNextRequestState{
 174                 Interested: true,
 175                 Requests:   requestSetFromSlice(keepReq),
 176         })
 177 }
 178
 179 func TestDontStealUnnecessarily(t *testing.T) {
 180         c := qt.New(t)
 181         basePeer := Peer{
 182                 HasPiece: func(i pieceIndex) bool {
 183                         return true
 184                 },
 185                 MaxRequests:  math.MaxInt16,
 186                 DownloadRate: 2,
 187         }
 188         // Slower than the stealers, but has all requests already.
 189         stealee := basePeer
 190         stealee.DownloadRate = 1
 191         keepReqs := requestSetFromSlice(
 192                 r(3, 2), r(3, 4), r(3, 6), r(3, 8),
 193                 r(4, 0), r(4, 1), r(4, 7), r(4, 8))
 194         stealee.HasExistingRequest = func(r Request) bool {
 195                 _, ok := keepReqs[r]
 196                 return ok
 197         }
 198         stealee.Id = intPeerId(1)
 199         firstStealer := basePeer
 200         firstStealer.Id = intPeerId(2)
 201         secondStealer := basePeer
 202         secondStealer.Id = intPeerId(3)
 203         secondStealer.HasPiece = func(i pieceIndex) bool {
 204                 switch i {
 205                 case 1, 3:
 206                         return true
 207                 default:
 208                         return false
 209                 }
 210         }
 211         results := Run(Input{Torrents: []Torrent{{
 212                 Pieces: []Piece{
 213                         {
 214                                 Request:           true,
 215                                 NumPendingChunks:  0,
 216                                 IterPendingChunks: chunkIterRange(9),
 217                         },
 218                         {
 219                                 Request:           true,
 220                                 NumPendingChunks:  7,
 221                                 IterPendingChunks: chunkIterRange(7),
 222                         },
 223                         {
 224                                 Request:           true,
 225                                 NumPendingChunks:  0,
 226                                 IterPendingChunks: chunkIterRange(0),
 227                         },
 228                         {
 229                                 Request:           true,
 230                                 NumPendingChunks:  9,
 231                                 IterPendingChunks: chunkIterRange(9),
 232                         },
 233                         {
 234                                 Request:           true,
 235                                 NumPendingChunks:  9,
 236                                 IterPendingChunks: chunkIterRange(9),
 237                         }},
 238                 Peers: []Peer{
 239                         firstStealer,
 240                         stealee,
 241                         secondStealer,
 242                 },
 243         }}})
 244
 245         c.Assert(results, qt.HasLen, 3)
 246         check := func(p PeerId, l int) {
 247                 c.Check(results[p].Requests, qt.HasLen, l)
 248                 c.Check(results[p].Interested, qt.Equals, l > 0)
 249         }
 250         check(firstStealer.Id, 5)
 251         check(secondStealer.Id, 7+9)
 252         c.Check(results[stealee.Id], qt.ContentEquals, PeerNextRequestState{
 253                 Interested: true,
 254                 Requests:   requestSetFromSlice(r(4, 0), r(4, 1), r(4, 7), r(4, 8)),
 255         })
 256 }
 257
 258 // This tests a situation where multiple peers had the same existing request, due to "actual" and
 259 // "next" request states being out of sync. This reasonable occurs when a peer hasn't fully updated
 260 // its actual request state since the last request strategy run.
 261 func TestDuplicatePreallocations(t *testing.T) {
 262         peer := func(id int, downloadRate float64) Peer {
 263                 return Peer{
 264                         HasExistingRequest: func(r Request) bool {
 265                                 return true
 266                         },
 267                         MaxRequests: 2,
 268                         HasPiece: func(i pieceIndex) bool {
 269                                 return true
 270                         },
 271                         Id:           intPeerId(id),
 272                         DownloadRate: downloadRate,
 273                 }
 274         }
 275         results := Run(Input{
 276                 Torrents: []Torrent{{
 277                         Pieces: []Piece{{
 278                                 Request:           true,
 279                                 NumPendingChunks:  1,
 280                                 IterPendingChunks: chunkIterRange(1),
 281                         }, {
 282                                 Request:           true,
 283                                 NumPendingChunks:  1,
 284                                 IterPendingChunks: chunkIterRange(1),
 285                         }},
 286                         Peers: []Peer{
 287                                 // The second peer was be marked as the preallocation, clobbering the first. The
 288                                 // first peer is preferred, and the piece isn't striped, so it gets preallocated a
 289                                 // request, and then gets reallocated from the peer the same request.
 290                                 peer(1, 2),
 291                                 peer(2, 1),
 292                         },
 293                 }},
 294         })
 295         c := qt.New(t)
 296         c.Assert(2, qt.Equals, len(results[intPeerId(1)].Requests)+len(results[intPeerId(2)].Requests))
 297 }