request-strategy/order_test.go

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