12 "github.com/anacrolix/generics/heap"
13 "github.com/anacrolix/log"
14 "github.com/anacrolix/multiless"
16 requestStrategy "github.com/anacrolix/torrent/request-strategy"
17 typedRoaring "github.com/anacrolix/torrent/typed-roaring"
21 // Since we have to store all the requests in memory, we can't reasonably exceed what could be
22 // indexed with the memory space available.
26 func (t *Torrent) requestStrategyPieceOrderState(i int) requestStrategy.PieceRequestOrderState {
27 return requestStrategy.PieceRequestOrderState{
28 Priority: t.piece(i).purePriority(),
29 Partial: t.piecePartiallyDownloaded(i),
30 Availability: t.piece(i).availability(),
35 gob.Register(peerId{})
43 func (p peerId) Uintptr() uintptr {
47 func (p peerId) GobEncode() (b []byte, _ error) {
48 *(*reflect.SliceHeader)(unsafe.Pointer(&b)) = reflect.SliceHeader{
49 Data: uintptr(unsafe.Pointer(&p.ptr)),
50 Len: int(unsafe.Sizeof(p.ptr)),
51 Cap: int(unsafe.Sizeof(p.ptr)),
56 func (p *peerId) GobDecode(b []byte) error {
57 if uintptr(len(b)) != unsafe.Sizeof(p.ptr) {
60 ptr := unsafe.Pointer(&b[0])
61 p.ptr = *(*uintptr)(ptr)
63 dst := reflect.SliceHeader{
64 Data: uintptr(unsafe.Pointer(&p.Peer)),
65 Len: int(unsafe.Sizeof(p.Peer)),
66 Cap: int(unsafe.Sizeof(p.Peer)),
68 copy(*(*[]byte)(unsafe.Pointer(&dst)), b)
73 RequestIndex = requestStrategy.RequestIndex
74 chunkIndexType = requestStrategy.ChunkIndex
77 type desiredPeerRequests struct {
78 requestIndexes []RequestIndex
80 pieceStates []requestStrategy.PieceRequestOrderState
83 func (p *desiredPeerRequests) lessByValue(leftRequest, rightRequest RequestIndex) bool {
85 leftPieceIndex := t.pieceIndexOfRequestIndex(leftRequest)
86 rightPieceIndex := t.pieceIndexOfRequestIndex(rightRequest)
88 // Push requests that can't be served right now to the end. But we don't throw them away unless
89 // there's a better alternative. This is for when we're using the fast extension and get choked
90 // but our requests could still be good when we get unchoked.
91 if p.peer.peerChoking {
93 !p.peer.peerAllowedFast.Contains(leftPieceIndex),
94 !p.peer.peerAllowedFast.Contains(rightPieceIndex),
97 leftPiece := &p.pieceStates[leftPieceIndex]
98 rightPiece := &p.pieceStates[rightPieceIndex]
99 // Putting this first means we can steal requests from lesser-performing peers for our first few
101 priority := func() piecePriority {
102 // Technically we would be happy with the cached priority here, except we don't actually
103 // cache it anymore, and Torrent.piecePriority just does another lookup of *Piece to resolve
104 // the priority through Piece.purePriority, which is probably slower.
105 leftPriority := leftPiece.Priority
106 rightPriority := rightPiece.Priority
112 if leftPriority != rightPriority {
113 panic("expected equal")
121 leftRequestState := t.requestState[leftRequest]
122 rightRequestState := t.requestState[rightRequest]
123 leftPeer := leftRequestState.peer
124 rightPeer := rightRequestState.peer
125 // Prefer chunks already requested from this peer.
126 ml = ml.Bool(rightPeer == p.peer, leftPeer == p.peer)
127 // Prefer unrequested chunks.
128 ml = ml.Bool(rightPeer == nil, leftPeer == nil)
133 // The right peer should also be set, or we'd have resolved the computation by now.
135 rightPeer.requestState.Requests.GetCardinality(),
136 leftPeer.requestState.Requests.GetCardinality(),
138 // Could either of the lastRequested be Zero? That's what checking an existing peer is for.
139 leftLast := leftRequestState.when
140 rightLast := rightRequestState.when
141 if leftLast.IsZero() || rightLast.IsZero() {
142 panic("expected non-zero last requested times")
144 // We want the most-recently requested on the left. Clients like Transmission serve requests
145 // in received order, so the most recently-requested is the one that has the longest until
146 // it will be served and therefore is the best candidate to cancel.
147 ml = ml.CmpInt64(rightLast.Sub(leftLast).Nanoseconds())
150 leftPiece.Availability,
151 rightPiece.Availability)
152 if priority == PiecePriorityReadahead {
153 // TODO: For readahead in particular, it would be even better to consider distance from the
154 // reader position so that reads earlier in a torrent don't starve reads later in the
155 // torrent. This would probably require reconsideration of how readahead priority works.
156 ml = ml.Int(leftPieceIndex, rightPieceIndex)
158 ml = ml.Int(t.pieceRequestOrder[leftPieceIndex], t.pieceRequestOrder[rightPieceIndex])
163 type desiredRequestState struct {
164 Requests desiredPeerRequests
168 func (p *Peer) getDesiredRequestState() (desired desiredRequestState) {
173 if t.closed.IsSet() {
176 input := t.getRequestStrategyInput()
177 requestHeap := desiredPeerRequests{
179 pieceStates: t.requestPieceStates,
180 requestIndexes: t.requestIndexes,
182 // Caller-provided allocation for roaring bitmap iteration.
183 var it typedRoaring.Iterator[RequestIndex]
184 requestStrategy.GetRequestablePieces(
186 t.getPieceRequestOrder(),
187 func(ih InfoHash, pieceIndex int, pieceExtra requestStrategy.PieceRequestOrderState) {
188 if ih != t.infoHash {
191 if !p.peerHasPiece(pieceIndex) {
194 requestHeap.pieceStates[pieceIndex] = pieceExtra
195 allowedFast := p.peerAllowedFast.Contains(pieceIndex)
196 t.iterUndirtiedRequestIndexesInPiece(&it, pieceIndex, func(r requestStrategy.RequestIndex) {
198 // We must signal interest to request this. TODO: We could set interested if the
199 // peers pieces (minus the allowed fast set) overlap with our missing pieces if
200 // there are any readers, or any pending pieces.
201 desired.Interested = true
202 // We can make or will allow sustaining a request here if we're not choked, or
203 // have made the request previously (presumably while unchoked), and haven't had
204 // the peer respond yet (and the request was retained because we are using the
206 if p.peerChoking && !p.requestState.Requests.Contains(r) {
207 // We can't request this right now.
211 if p.requestState.Cancelled.Contains(r) {
212 // Can't re-request while awaiting acknowledgement.
215 requestHeap.requestIndexes = append(requestHeap.requestIndexes, r)
219 t.assertPendingRequests()
220 desired.Requests = requestHeap
224 func (p *Peer) maybeUpdateActualRequestState() {
225 if p.closed.IsSet() {
228 if p.needRequestUpdate == "" {
231 if p.needRequestUpdate == peerUpdateRequestsTimerReason {
232 since := time.Since(p.lastRequestUpdate)
233 if since < updateRequestsTimerDuration {
238 context.Background(),
239 pprof.Labels("update request", p.needRequestUpdate),
240 func(_ context.Context) {
241 next := p.getDesiredRequestState()
242 p.applyRequestState(next)
243 p.t.requestIndexes = next.Requests.requestIndexes[:0]
248 // Transmit/action the request state to the peer.
249 func (p *Peer) applyRequestState(next desiredRequestState) {
250 current := &p.requestState
251 if !p.setInterested(next.Interested) {
255 requestHeap := heap.InterfaceForSlice(&next.Requests.requestIndexes, next.Requests.lessByValue)
256 heap.Init(requestHeap)
259 originalRequestCount := current.Requests.GetCardinality()
260 // We're either here on a timer, or because we ran out of requests. Both are valid reasons to
261 // alter peakRequests.
262 if originalRequestCount != 0 && p.needRequestUpdate != peerUpdateRequestsTimerReason {
264 "expected zero existing requests (%v) for update reason %q",
265 originalRequestCount, p.needRequestUpdate))
267 for requestHeap.Len() != 0 && maxRequests(current.Requests.GetCardinality()+current.Cancelled.GetCardinality()) < p.nominalMaxRequests() {
268 req := heap.Pop(requestHeap)
269 existing := t.requestingPeer(req)
270 if existing != nil && existing != p {
271 // Don't steal from the poor.
272 diff := int64(current.Requests.GetCardinality()) + 1 - (int64(existing.uncancelledRequests()) - 1)
273 // Steal a request that leaves us with one more request than the existing peer
274 // connection if the stealer more recently received a chunk.
275 if diff > 1 || (diff == 1 && p.lastUsefulChunkReceived.Before(existing.lastUsefulChunkReceived)) {
280 more = p.mustRequest(req)
286 // This might fail if we incorrectly determine that we can fit up to the maximum allowed
287 // requests into the available write buffer space. We don't want that to happen because it
288 // makes our peak requests dependent on how much was already in the buffer.
290 "couldn't fill apply entire request state [newRequests=%v]",
291 current.Requests.GetCardinality()-originalRequestCount))
293 newPeakRequests := maxRequests(current.Requests.GetCardinality() - originalRequestCount)
295 // "requests %v->%v (peak %v->%v) reason %q (peer %v)",
296 // originalRequestCount, current.Requests.GetCardinality(), p.peakRequests, newPeakRequests, p.needRequestUpdate, p)
297 p.peakRequests = newPeakRequests
298 p.needRequestUpdate = ""
299 p.lastRequestUpdate = time.Now()
300 if enableUpdateRequestsTimer {
301 p.updateRequestsTimer.Reset(updateRequestsTimerDuration)
305 // This could be set to 10s to match the unchoke/request update interval recommended by some
306 // specifications. I've set it shorter to trigger it more often for testing for now.
308 updateRequestsTimerDuration = 3 * time.Second
309 enableUpdateRequestsTimer = false