requesting.go

   1 package torrent
   2
   3 import (
   4         "context"
   5         "encoding/gob"
   6         "fmt"
   7         "reflect"
   8         "runtime/pprof"
   9         "time"
  10         "unsafe"
  11
  12         "github.com/RoaringBitmap/roaring"
  13         "github.com/anacrolix/generics/heap"
  14         "github.com/anacrolix/log"
  15         "github.com/anacrolix/multiless"
  16
  17         requestStrategy "github.com/anacrolix/torrent/request-strategy"
  18         typedRoaring "github.com/anacrolix/torrent/typed-roaring"
  19 )
  20
  21 type (
  22         // Since we have to store all the requests in memory, we can't reasonably exceed what could be
  23         // indexed with the memory space available.
  24         maxRequests = int
  25 )
  26
  27 func (t *Torrent) requestStrategyPieceOrderState(i int) requestStrategy.PieceRequestOrderState {
  28         return requestStrategy.PieceRequestOrderState{
  29                 Priority:     t.piece(i).purePriority(),
  30                 Partial:      t.piecePartiallyDownloaded(i),
  31                 Availability: t.piece(i).availability(),
  32         }
  33 }
  34
  35 func init() {
  36         gob.Register(peerId{})
  37 }
  38
  39 type peerId struct {
  40         *Peer
  41         ptr uintptr
  42 }
  43
  44 func (p peerId) Uintptr() uintptr {
  45         return p.ptr
  46 }
  47
  48 func (p peerId) GobEncode() (b []byte, _ error) {
  49         *(*reflect.SliceHeader)(unsafe.Pointer(&b)) = reflect.SliceHeader{
  50                 Data: uintptr(unsafe.Pointer(&p.ptr)),
  51                 Len:  int(unsafe.Sizeof(p.ptr)),
  52                 Cap:  int(unsafe.Sizeof(p.ptr)),
  53         }
  54         return
  55 }
  56
  57 func (p *peerId) GobDecode(b []byte) error {
  58         if uintptr(len(b)) != unsafe.Sizeof(p.ptr) {
  59                 panic(len(b))
  60         }
  61         ptr := unsafe.Pointer(&b[0])
  62         p.ptr = *(*uintptr)(ptr)
  63         log.Printf("%p", ptr)
  64         dst := reflect.SliceHeader{
  65                 Data: uintptr(unsafe.Pointer(&p.Peer)),
  66                 Len:  int(unsafe.Sizeof(p.Peer)),
  67                 Cap:  int(unsafe.Sizeof(p.Peer)),
  68         }
  69         copy(*(*[]byte)(unsafe.Pointer(&dst)), b)
  70         return nil
  71 }
  72
  73 type (
  74         RequestIndex   = requestStrategy.RequestIndex
  75         chunkIndexType = requestStrategy.ChunkIndex
  76 )
  77
  78 type desiredPeerRequests struct {
  79         requestIndexes []RequestIndex
  80         peer           *Peer
  81         pieceStates    []requestStrategy.PieceRequestOrderState
  82 }
  83
  84 func (p *desiredPeerRequests) lessByValue(leftRequest, rightRequest RequestIndex) bool {
  85         t := p.peer.t
  86         leftPieceIndex := t.pieceIndexOfRequestIndex(leftRequest)
  87         rightPieceIndex := t.pieceIndexOfRequestIndex(rightRequest)
  88         ml := multiless.New()
  89         // Push requests that can't be served right now to the end. But we don't throw them away unless
  90         // there's a better alternative. This is for when we're using the fast extension and get choked
  91         // but our requests could still be good when we get unchoked.
  92         if p.peer.peerChoking {
  93                 ml = ml.Bool(
  94                         !p.peer.peerAllowedFast.Contains(leftPieceIndex),
  95                         !p.peer.peerAllowedFast.Contains(rightPieceIndex),
  96                 )
  97         }
  98         leftPiece := &p.pieceStates[leftPieceIndex]
  99         rightPiece := &p.pieceStates[rightPieceIndex]
 100         // Putting this first means we can steal requests from lesser-performing peers for our first few
 101         // new requests.
 102         priority := func() piecePriority {
 103                 // Technically we would be happy with the cached priority here, except we don't actually
 104                 // cache it anymore, and Torrent.piecePriority just does another lookup of *Piece to resolve
 105                 // the priority through Piece.purePriority, which is probably slower.
 106                 leftPriority := leftPiece.Priority
 107                 rightPriority := rightPiece.Priority
 108                 ml = ml.Int(
 109                         -int(leftPriority),
 110                         -int(rightPriority),
 111                 )
 112                 if !ml.Ok() {
 113                         if leftPriority != rightPriority {
 114                                 panic("expected equal")
 115                         }
 116                 }
 117                 return leftPriority
 118         }()
 119         if ml.Ok() {
 120                 return ml.MustLess()
 121         }
 122         leftRequestState := t.requestState[leftRequest]
 123         rightRequestState := t.requestState[rightRequest]
 124         leftPeer := leftRequestState.peer
 125         rightPeer := rightRequestState.peer
 126         // Prefer chunks already requested from this peer.
 127         ml = ml.Bool(rightPeer == p.peer, leftPeer == p.peer)
 128         // Prefer unrequested chunks.
 129         ml = ml.Bool(rightPeer == nil, leftPeer == nil)
 130         if ml.Ok() {
 131                 return ml.MustLess()
 132         }
 133         if leftPeer != nil {
 134                 // The right peer should also be set, or we'd have resolved the computation by now.
 135                 ml = ml.Uint64(
 136                         rightPeer.requestState.Requests.GetCardinality(),
 137                         leftPeer.requestState.Requests.GetCardinality(),
 138                 )
 139                 // Could either of the lastRequested be Zero? That's what checking an existing peer is for.
 140                 leftLast := leftRequestState.when
 141                 rightLast := rightRequestState.when
 142                 if leftLast.IsZero() || rightLast.IsZero() {
 143                         panic("expected non-zero last requested times")
 144                 }
 145                 // We want the most-recently requested on the left. Clients like Transmission serve requests
 146                 // in received order, so the most recently-requested is the one that has the longest until
 147                 // it will be served and therefore is the best candidate to cancel.
 148                 ml = ml.CmpInt64(rightLast.Sub(leftLast).Nanoseconds())
 149         }
 150         ml = ml.Int(
 151                 leftPiece.Availability,
 152                 rightPiece.Availability)
 153         if priority == PiecePriorityReadahead {
 154                 // TODO: For readahead in particular, it would be even better to consider distance from the
 155                 // reader position so that reads earlier in a torrent don't starve reads later in the
 156                 // torrent. This would probably require reconsideration of how readahead priority works.
 157                 ml = ml.Int(leftPieceIndex, rightPieceIndex)
 158         } else {
 159                 ml = ml.Int(t.pieceRequestOrder[leftPieceIndex], t.pieceRequestOrder[rightPieceIndex])
 160         }
 161         return ml.Less()
 162 }
 163
 164 type desiredRequestState struct {
 165         Requests   desiredPeerRequests
 166         Interested bool
 167 }
 168
 169 func (p *Peer) getDesiredRequestState() (desired desiredRequestState) {
 170         t := p.t
 171         if !t.haveInfo() {
 172                 return
 173         }
 174         if t.closed.IsSet() {
 175                 return
 176         }
 177         if t.dataDownloadDisallowed.Bool() {
 178                 return
 179         }
 180         input := t.getRequestStrategyInput()
 181         requestHeap := desiredPeerRequests{
 182                 peer:           p,
 183                 pieceStates:    t.requestPieceStates,
 184                 requestIndexes: t.requestIndexes,
 185         }
 186         // Caller-provided allocation for roaring bitmap iteration.
 187         var it typedRoaring.Iterator[RequestIndex]
 188         requestStrategy.GetRequestablePieces(
 189                 input,
 190                 t.getPieceRequestOrder(),
 191                 func(ih InfoHash, pieceIndex int, pieceExtra requestStrategy.PieceRequestOrderState) {
 192                         if ih != *t.canonicalShortInfohash() {
 193                                 return
 194                         }
 195                         if !p.peerHasPiece(pieceIndex) {
 196                                 return
 197                         }
 198                         requestHeap.pieceStates[pieceIndex] = pieceExtra
 199                         allowedFast := p.peerAllowedFast.Contains(pieceIndex)
 200                         t.iterUndirtiedRequestIndexesInPiece(&it, pieceIndex, func(r requestStrategy.RequestIndex) {
 201                                 if !allowedFast {
 202                                         // We must signal interest to request this. TODO: We could set interested if the
 203                                         // peers pieces (minus the allowed fast set) overlap with our missing pieces if
 204                                         // there are any readers, or any pending pieces.
 205                                         desired.Interested = true
 206                                         // We can make or will allow sustaining a request here if we're not choked, or
 207                                         // have made the request previously (presumably while unchoked), and haven't had
 208                                         // the peer respond yet (and the request was retained because we are using the
 209                                         // fast extension).
 210                                         if p.peerChoking && !p.requestState.Requests.Contains(r) {
 211                                                 // We can't request this right now.
 212                                                 return
 213                                         }
 214                                 }
 215                                 cancelled := &p.requestState.Cancelled
 216                                 if !cancelled.IsEmpty() && cancelled.Contains(r) {
 217                                         // Can't re-request while awaiting acknowledgement.
 218                                         return
 219                                 }
 220                                 requestHeap.requestIndexes = append(requestHeap.requestIndexes, r)
 221                         })
 222                 },
 223         )
 224         t.assertPendingRequests()
 225         desired.Requests = requestHeap
 226         return
 227 }
 228
 229 func (p *Peer) maybeUpdateActualRequestState() {
 230         if p.closed.IsSet() {
 231                 return
 232         }
 233         if p.needRequestUpdate == "" {
 234                 return
 235         }
 236         if p.needRequestUpdate == peerUpdateRequestsTimerReason {
 237                 since := time.Since(p.lastRequestUpdate)
 238                 if since < updateRequestsTimerDuration {
 239                         panic(since)
 240                 }
 241         }
 242         pprof.Do(
 243                 context.Background(),
 244                 pprof.Labels("update request", p.needRequestUpdate),
 245                 func(_ context.Context) {
 246                         next := p.getDesiredRequestState()
 247                         p.applyRequestState(next)
 248                         p.t.cacheNextRequestIndexesForReuse(next.Requests.requestIndexes)
 249                 },
 250         )
 251 }
 252
 253 func (t *Torrent) cacheNextRequestIndexesForReuse(slice []RequestIndex) {
 254         // The incoming slice can be smaller when getDesiredRequestState short circuits on some
 255         // conditions.
 256         if cap(slice) > cap(t.requestIndexes) {
 257                 t.requestIndexes = slice[:0]
 258         }
 259 }
 260
 261 // Whether we should allow sending not interested ("losing interest") to the peer. I noticed
 262 // qBitTorrent seems to punish us for sending not interested when we're streaming and don't
 263 // currently need anything.
 264 func (p *Peer) allowSendNotInterested() bool {
 265         // Except for caching, we're not likely to lose pieces very soon.
 266         if p.t.haveAllPieces() {
 267                 return true
 268         }
 269         all, known := p.peerHasAllPieces()
 270         if all || !known {
 271                 return false
 272         }
 273         // Allow losing interest if we have all the pieces the peer has.
 274         return roaring.AndNot(p.peerPieces(), &p.t._completedPieces).IsEmpty()
 275 }
 276
 277 // Transmit/action the request state to the peer.
 278 func (p *Peer) applyRequestState(next desiredRequestState) {
 279         current := &p.requestState
 280         // Make interest sticky
 281         if !next.Interested && p.requestState.Interested {
 282                 if !p.allowSendNotInterested() {
 283                         next.Interested = true
 284                 }
 285         }
 286         if !p.setInterested(next.Interested) {
 287                 return
 288         }
 289         more := true
 290         orig := next.Requests.requestIndexes
 291         requestHeap := heap.InterfaceForSlice(
 292                 &next.Requests.requestIndexes,
 293                 next.Requests.lessByValue,
 294         )
 295         heap.Init(requestHeap)
 296
 297         t := p.t
 298         originalRequestCount := current.Requests.GetCardinality()
 299         for {
 300                 if requestHeap.Len() == 0 {
 301                         break
 302                 }
 303                 numPending := maxRequests(current.Requests.GetCardinality() + current.Cancelled.GetCardinality())
 304                 if numPending >= p.nominalMaxRequests() {
 305                         break
 306                 }
 307                 req := heap.Pop(requestHeap)
 308                 if cap(next.Requests.requestIndexes) != cap(orig) {
 309                         panic("changed")
 310                 }
 311                 existing := t.requestingPeer(req)
 312                 if existing != nil && existing != p {
 313                         // Don't steal from the poor.
 314                         diff := int64(current.Requests.GetCardinality()) + 1 - (int64(existing.uncancelledRequests()) - 1)
 315                         // Steal a request that leaves us with one more request than the existing peer
 316                         // connection if the stealer more recently received a chunk.
 317                         if diff > 1 || (diff == 1 && p.lastUsefulChunkReceived.Before(existing.lastUsefulChunkReceived)) {
 318                                 continue
 319                         }
 320                         t.cancelRequest(req)
 321                 }
 322                 more = p.mustRequest(req)
 323                 if !more {
 324                         break
 325                 }
 326         }
 327         if !more {
 328                 // This might fail if we incorrectly determine that we can fit up to the maximum allowed
 329                 // requests into the available write buffer space. We don't want that to happen because it
 330                 // makes our peak requests dependent on how much was already in the buffer.
 331                 panic(fmt.Sprintf(
 332                         "couldn't fill apply entire request state [newRequests=%v]",
 333                         current.Requests.GetCardinality()-originalRequestCount))
 334         }
 335         newPeakRequests := maxRequests(current.Requests.GetCardinality() - originalRequestCount)
 336         // log.Printf(
 337         //      "requests %v->%v (peak %v->%v) reason %q (peer %v)",
 338         //      originalRequestCount, current.Requests.GetCardinality(), p.peakRequests, newPeakRequests, p.needRequestUpdate, p)
 339         p.peakRequests = newPeakRequests
 340         p.needRequestUpdate = ""
 341         p.lastRequestUpdate = time.Now()
 342         if enableUpdateRequestsTimer {
 343                 p.updateRequestsTimer.Reset(updateRequestsTimerDuration)
 344         }
 345 }
 346
 347 // This could be set to 10s to match the unchoke/request update interval recommended by some
 348 // specifications. I've set it shorter to trigger it more often for testing for now.
 349 const (
 350         updateRequestsTimerDuration = 3 * time.Second
 351         enableUpdateRequestsTimer   = false
 352 )