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/anacrolix/log"
  13         "github.com/anacrolix/multiless"
  14         "github.com/lispad/go-generics-tools/binheap"
  15
  16         request_strategy "github.com/anacrolix/torrent/request-strategy"
  17 )
  18
  19 func (t *Torrent) requestStrategyPieceOrderState(i int) request_strategy.PieceRequestOrderState {
  20         return request_strategy.PieceRequestOrderState{
  21                 Priority:     t.piece(i).purePriority(),
  22                 Partial:      t.piecePartiallyDownloaded(i),
  23                 Availability: t.piece(i).availability(),
  24         }
  25 }
  26
  27 func init() {
  28         gob.Register(peerId{})
  29 }
  30
  31 type peerId struct {
  32         *Peer
  33         ptr uintptr
  34 }
  35
  36 func (p peerId) Uintptr() uintptr {
  37         return p.ptr
  38 }
  39
  40 func (p peerId) GobEncode() (b []byte, _ error) {
  41         *(*reflect.SliceHeader)(unsafe.Pointer(&b)) = reflect.SliceHeader{
  42                 Data: uintptr(unsafe.Pointer(&p.ptr)),
  43                 Len:  int(unsafe.Sizeof(p.ptr)),
  44                 Cap:  int(unsafe.Sizeof(p.ptr)),
  45         }
  46         return
  47 }
  48
  49 func (p *peerId) GobDecode(b []byte) error {
  50         if uintptr(len(b)) != unsafe.Sizeof(p.ptr) {
  51                 panic(len(b))
  52         }
  53         ptr := unsafe.Pointer(&b[0])
  54         p.ptr = *(*uintptr)(ptr)
  55         log.Printf("%p", ptr)
  56         dst := reflect.SliceHeader{
  57                 Data: uintptr(unsafe.Pointer(&p.Peer)),
  58                 Len:  int(unsafe.Sizeof(p.Peer)),
  59                 Cap:  int(unsafe.Sizeof(p.Peer)),
  60         }
  61         copy(*(*[]byte)(unsafe.Pointer(&dst)), b)
  62         return nil
  63 }
  64
  65 type (
  66         RequestIndex   = request_strategy.RequestIndex
  67         chunkIndexType = request_strategy.ChunkIndex
  68 )
  69
  70 type desiredPeerRequests struct {
  71         requestIndexes []RequestIndex
  72         peer           *Peer
  73         pieceStates    []request_strategy.PieceRequestOrderState
  74 }
  75
  76 func (p *desiredPeerRequests) Len() int {
  77         return len(p.requestIndexes)
  78 }
  79
  80 func (p *desiredPeerRequests) Less(i, j int) bool {
  81         return p.lessByValue(p.requestIndexes[i], p.requestIndexes[j])
  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                 // TODO: To prevent unnecessarily requesting from disparate pieces, and to ensure pieces are
 160                 // selected randomly when availability is even, there should be some fixed ordering of
 161                 // pieces.
 162         }
 163         return ml.Less()
 164 }
 165
 166 func (p *desiredPeerRequests) Swap(i, j int) {
 167         p.requestIndexes[i], p.requestIndexes[j] = p.requestIndexes[j], p.requestIndexes[i]
 168 }
 169
 170 func (p *desiredPeerRequests) Push(x interface{}) {
 171         p.requestIndexes = append(p.requestIndexes, x.(RequestIndex))
 172 }
 173
 174 func (p *desiredPeerRequests) Pop() interface{} {
 175         last := len(p.requestIndexes) - 1
 176         x := p.requestIndexes[last]
 177         p.requestIndexes = p.requestIndexes[:last]
 178         return x
 179 }
 180
 181 type desiredRequestState struct {
 182         Requests   desiredPeerRequests
 183         Interested bool
 184 }
 185
 186 func (p *Peer) getDesiredRequestState() (desired desiredRequestState) {
 187         t := p.t
 188         if !t.haveInfo() {
 189                 return
 190         }
 191         if t.closed.IsSet() {
 192                 return
 193         }
 194         input := t.getRequestStrategyInput()
 195         requestHeap := desiredPeerRequests{
 196                 peer:           p,
 197                 pieceStates:    t.requestPieceStates,
 198                 requestIndexes: t.requestIndexes,
 199         }
 200         request_strategy.GetRequestablePieces(
 201                 input,
 202                 t.getPieceRequestOrder(),
 203                 func(ih InfoHash, pieceIndex int, pieceExtra request_strategy.PieceRequestOrderState) {
 204                         if ih != t.infoHash {
 205                                 return
 206                         }
 207                         if !p.peerHasPiece(pieceIndex) {
 208                                 return
 209                         }
 210                         requestHeap.pieceStates[pieceIndex] = pieceExtra
 211                         allowedFast := p.peerAllowedFast.Contains(pieceIndex)
 212                         p.t.piece(pieceIndex).undirtiedChunksIter.Iter(func(ci request_strategy.ChunkIndex) {
 213                                 r := p.t.pieceRequestIndexOffset(pieceIndex) + ci
 214                                 if !allowedFast {
 215                                         // We must signal interest to request this. TODO: We could set interested if the
 216                                         // peers pieces (minus the allowed fast set) overlap with our missing pieces if
 217                                         // there are any readers, or any pending pieces.
 218                                         desired.Interested = true
 219                                         // We can make or will allow sustaining a request here if we're not choked, or
 220                                         // have made the request previously (presumably while unchoked), and haven't had
 221                                         // the peer respond yet (and the request was retained because we are using the
 222                                         // fast extension).
 223                                         if p.peerChoking && !p.requestState.Requests.Contains(r) {
 224                                                 // We can't request this right now.
 225                                                 return
 226                                         }
 227                                 }
 228                                 if p.requestState.Cancelled.Contains(r) {
 229                                         // Can't re-request while awaiting acknowledgement.
 230                                         return
 231                                 }
 232                                 requestHeap.requestIndexes = append(requestHeap.requestIndexes, r)
 233                         })
 234                 },
 235         )
 236         t.assertPendingRequests()
 237         desired.Requests = requestHeap
 238         return
 239 }
 240
 241 func (p *Peer) maybeUpdateActualRequestState() {
 242         if p.closed.IsSet() {
 243                 return
 244         }
 245         if p.needRequestUpdate == "" {
 246                 return
 247         }
 248         if p.needRequestUpdate == peerUpdateRequestsTimerReason {
 249                 since := time.Since(p.lastRequestUpdate)
 250                 if since < updateRequestsTimerDuration {
 251                         panic(since)
 252                 }
 253         }
 254         pprof.Do(
 255                 context.Background(),
 256                 pprof.Labels("update request", p.needRequestUpdate),
 257                 func(_ context.Context) {
 258                         next := p.getDesiredRequestState()
 259                         p.applyRequestState(next)
 260                         p.t.requestIndexes = next.Requests.requestIndexes[:0]
 261                 },
 262         )
 263 }
 264
 265 // Transmit/action the request state to the peer.
 266 func (p *Peer) applyRequestState(next desiredRequestState) {
 267         current := &p.requestState
 268         if !p.setInterested(next.Interested) {
 269                 panic("insufficient write buffer")
 270         }
 271         more := true
 272         requestHeap := binheap.FromSlice(next.Requests.requestIndexes, next.Requests.lessByValue)
 273         t := p.t
 274         originalRequestCount := current.Requests.GetCardinality()
 275         // We're either here on a timer, or because we ran out of requests. Both are valid reasons to
 276         // alter peakRequests.
 277         if originalRequestCount != 0 && p.needRequestUpdate != peerUpdateRequestsTimerReason {
 278                 panic(fmt.Sprintf(
 279                         "expected zero existing requests (%v) for update reason %q",
 280                         originalRequestCount, p.needRequestUpdate))
 281         }
 282         for requestHeap.Len() != 0 && maxRequests(current.Requests.GetCardinality()+current.Cancelled.GetCardinality()) < p.nominalMaxRequests() {
 283                 req := requestHeap.Pop()
 284                 existing := t.requestingPeer(req)
 285                 if existing != nil && existing != p {
 286                         // Don't steal from the poor.
 287                         diff := int64(current.Requests.GetCardinality()) + 1 - (int64(existing.uncancelledRequests()) - 1)
 288                         // Steal a request that leaves us with one more request than the existing peer
 289                         // connection if the stealer more recently received a chunk.
 290                         if diff > 1 || (diff == 1 && p.lastUsefulChunkReceived.Before(existing.lastUsefulChunkReceived)) {
 291                                 continue
 292                         }
 293                         t.cancelRequest(req)
 294                 }
 295                 more = p.mustRequest(req)
 296                 if !more {
 297                         break
 298                 }
 299         }
 300         if !more {
 301                 // This might fail if we incorrectly determine that we can fit up to the maximum allowed
 302                 // requests into the available write buffer space. We don't want that to happen because it
 303                 // makes our peak requests dependent on how much was already in the buffer.
 304                 panic(fmt.Sprintf(
 305                         "couldn't fill apply entire request state [newRequests=%v]",
 306                         current.Requests.GetCardinality()-originalRequestCount))
 307         }
 308         newPeakRequests := maxRequests(current.Requests.GetCardinality() - originalRequestCount)
 309         // log.Printf(
 310         //      "requests %v->%v (peak %v->%v) reason %q (peer %v)",
 311         //      originalRequestCount, current.Requests.GetCardinality(), p.peakRequests, newPeakRequests, p.needRequestUpdate, p)
 312         p.peakRequests = newPeakRequests
 313         p.needRequestUpdate = ""
 314         p.lastRequestUpdate = time.Now()
 315         p.updateRequestsTimer.Reset(updateRequestsTimerDuration)
 316 }
 317
 318 // This could be set to 10s to match the unchoke/request update interval recommended by some
 319 // specifications. I've set it shorter to trigger it more often for testing for now.
 320 const updateRequestsTimerDuration = 3 * time.Second