request-strategy/order_test.go

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