source: trunk/libtransmission/completion.c @ 11892

Last change on this file since 11892 was 11892, checked in by jordan, 11 years ago

(trunk libT) #3656 "endgame could be faster" -- fixed. Patch by harrydb.

  • Property svn:keywords set to Date Rev Author Id
File size: 13.7 KB
Line 
1/*
2 * This file Copyright (C) Mnemosyne LLC
3 *
4 * This file is licensed by the GPL version 2. Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id: completion.c 11892 2011-02-15 16:04:56Z jordan $
11 */
12
13#include <assert.h>
14#include <string.h>
15
16#include "transmission.h"
17#include "completion.h"
18#include "torrent.h"
19#include "torrent-magnet.h"
20#include "utils.h"
21
22static void
23tr_cpReset( tr_completion * cp )
24{
25    tr_bitfieldClear( &cp->pieceBitfield );
26    tr_bitfieldClear( &cp->blockBitfield );
27    memset( cp->completeBlocks, 0, sizeof( uint16_t ) * cp->tor->info.pieceCount );
28    cp->sizeNow = 0;
29    cp->sizeWhenDoneIsDirty = 1;
30    cp->blocksWantedIsDirty = 1;
31    cp->haveValidIsDirty = 1;
32}
33
34tr_completion *
35tr_cpConstruct( tr_completion * cp, tr_torrent * tor )
36{
37    cp->tor = tor;
38    cp->completeBlocks  = tr_new( uint16_t, tor->info.pieceCount );
39    tr_bitfieldConstruct( &cp->blockBitfield, tor->blockCount );
40    tr_bitfieldConstruct( &cp->pieceBitfield, tor->info.pieceCount );
41    tr_cpReset( cp );
42    return cp;
43}
44
45tr_completion*
46tr_cpDestruct( tr_completion * cp )
47{
48    tr_free( cp->completeBlocks );
49    tr_bitfieldDestruct( &cp->pieceBitfield );
50    tr_bitfieldDestruct( &cp->blockBitfield );
51    return cp;
52}
53
54void
55tr_cpInvalidateDND( tr_completion * cp )
56{
57    cp->sizeWhenDoneIsDirty = 1;
58    cp->blocksWantedIsDirty = 1;
59}
60
61tr_block_index_t
62tr_cpBlocksMissing( const tr_completion * ccp )
63{
64    if( ccp->blocksWantedIsDirty )
65    {
66        tr_completion *    cp = (tr_completion *) ccp; /* mutable */
67        const tr_torrent * tor = cp->tor;
68        const tr_info *    info = &tor->info;
69        tr_piece_index_t   i;
70        tr_block_index_t   wanted = 0;
71        tr_block_index_t   complete = 0;
72
73        for( i = 0; i < info->pieceCount; ++i )
74        {
75            if( info->pieces[i].dnd )
76                continue;
77
78            wanted += tr_torPieceCountBlocks( tor, i );
79            complete += cp->completeBlocks[i];
80        }
81
82        cp->blocksWantedLazy = wanted;
83        cp->blocksWantedCompleteLazy = complete;
84        cp->blocksWantedIsDirty = FALSE;
85    }
86
87    return ccp->blocksWantedLazy - ccp->blocksWantedCompleteLazy;
88}
89
90uint64_t
91tr_cpSizeWhenDone( const tr_completion * ccp )
92{
93    if( ccp->sizeWhenDoneIsDirty )
94    {
95        tr_completion *    cp = (tr_completion *) ccp; /* mutable */
96        const tr_torrent * tor = cp->tor;
97        const tr_info *    info = &tor->info;
98        tr_piece_index_t   i;
99        uint64_t           size = 0;
100
101        for( i = 0; i < info->pieceCount; ++i )
102        {
103            if( !info->pieces[i].dnd )
104            {
105                /* we want the piece... */
106                size += tr_torPieceCountBytes( tor, i );
107            }
108            else if( tr_cpPieceIsComplete( cp, i ) )
109            {
110                /* we have the piece... */
111                size += tr_torPieceCountBytes( tor, i );
112            }
113            else if( cp->completeBlocks[i] )
114            {
115                /* we have part of the piece... */
116                const tr_block_index_t b = tr_torPieceFirstBlock( tor, i );
117                const tr_block_index_t e = b + tr_torPieceCountBlocks( tor, i );
118                tr_block_index_t j;
119                for( j = b; j < e; ++j )
120                    if( tr_cpBlockIsCompleteFast( cp, j ) )
121                        size += tr_torBlockCountBytes( tor, j );
122            }
123        }
124
125        cp->sizeWhenDoneLazy = size;
126        cp->sizeWhenDoneIsDirty = 0;
127    }
128
129    assert( ccp->sizeWhenDoneLazy <= ccp->tor->info.totalSize );
130    assert( ccp->sizeWhenDoneLazy >= ccp->sizeNow );
131    return ccp->sizeWhenDoneLazy;
132}
133
134void
135tr_cpPieceAdd( tr_completion *  cp,
136               tr_piece_index_t piece )
137{
138    const tr_torrent *     tor = cp->tor;
139    const tr_block_index_t start = tr_torPieceFirstBlock( tor, piece );
140    const tr_block_index_t end = start + tr_torPieceCountBlocks( tor, piece );
141    tr_block_index_t       i;
142
143    for( i = start; i < end; ++i )
144        tr_cpBlockAdd( cp, i );
145}
146
147void
148tr_cpPieceRem( tr_completion *  cp,
149               tr_piece_index_t piece )
150{
151    const tr_torrent *     tor = cp->tor;
152    const tr_block_index_t start = tr_torPieceFirstBlock( tor, piece );
153    const tr_block_index_t end = start + tr_torPieceCountBlocks( tor, piece );
154    tr_block_index_t       block;
155
156    assert( cp );
157    assert( piece < tor->info.pieceCount );
158    assert( start < tor->blockCount );
159    assert( start <= end );
160    assert( end <= tor->blockCount );
161
162    for( block = start; block < end; ++block )
163        if( tr_cpBlockIsCompleteFast( cp, block ) )
164            cp->sizeNow -= tr_torBlockCountBytes( tor, block );
165
166    if( !tor->info.pieces[piece].dnd )
167        cp->blocksWantedCompleteLazy -= cp->completeBlocks[piece];
168
169    cp->sizeWhenDoneIsDirty = 1;
170    cp->haveValidIsDirty = 1;
171    cp->completeBlocks[piece] = 0;
172    tr_bitfieldRemRange ( &cp->blockBitfield, start, end );
173    tr_bitfieldRem( &cp->pieceBitfield, piece );
174}
175
176void
177tr_cpBlockAdd( tr_completion * cp, tr_block_index_t block )
178{
179    const tr_torrent * tor = cp->tor;
180
181    if( !tr_cpBlockIsComplete( cp, block ) )
182    {
183        const tr_piece_index_t piece = tr_torBlockPiece( tor, block );
184        const int              blockSize = tr_torBlockCountBytes( tor,
185                                                                  block );
186
187        ++cp->completeBlocks[piece];
188
189        if( tr_cpPieceIsComplete( cp, piece ) )
190            tr_bitfieldAdd( &cp->pieceBitfield, piece );
191
192        tr_bitfieldAdd( &cp->blockBitfield, block );
193
194        cp->sizeNow += blockSize;
195        if( !tor->info.pieces[piece].dnd )
196            cp->blocksWantedCompleteLazy++;
197
198        cp->haveValidIsDirty = 1;
199        cp->sizeWhenDoneIsDirty = 1;
200    }
201}
202
203
204void
205tr_cpSetHaveAll( tr_completion * cp )
206{
207    tr_piece_index_t i;
208    tr_torrent * tor = cp->tor;
209
210    tr_cpReset( cp );
211
212    cp->sizeNow = tor->info.totalSize;
213    tr_bitfieldAddRange( &cp->blockBitfield, 0, tor->blockCount );
214    tr_bitfieldAddRange( &cp->pieceBitfield, 0, tor->info.pieceCount );
215    for( i=0; i<tor->info.pieceCount; ++i )
216        cp->completeBlocks[i] = tr_torPieceCountBlocks( tor, i );
217    cp->sizeWhenDoneIsDirty = 1;
218    cp->blocksWantedIsDirty = 1;
219    cp->haveValidIsDirty = 1;
220}
221
222/* Initialize a completion object from a bitfield indicating which blocks we have */
223tr_bool
224tr_cpBlockBitfieldSet( tr_completion * cp, tr_bitfield * blockBitfield )
225{
226    tr_bool success = FALSE;
227
228    assert( cp );
229    assert( blockBitfield );
230
231    /* The bitfield of block flags is typically loaded from a resume file.
232       Test the bitfield's length in case the resume file somehow got corrupted */
233    if(( success = blockBitfield->byteCount == cp->blockBitfield.byteCount ))
234    {
235        tr_block_index_t b = 0;
236        tr_piece_index_t p = 0;
237        uint32_t pieceBlock = 0;
238        uint16_t completeBlocksInPiece = 0;
239        tr_block_index_t completeBlocksInTorrent = 0;
240        uint32_t blocksInCurrentPiece = tr_torPieceCountBlocks( cp->tor, p );
241
242        /* start cp with a state where it thinks we have nothing */
243        tr_cpReset( cp );
244
245        /* init our block bitfield from the one passed in */
246        memcpy( cp->blockBitfield.bits, blockBitfield->bits, blockBitfield->byteCount );
247
248        /* invalidate the fields that are lazy-evaluated */
249        cp->sizeWhenDoneIsDirty = TRUE;
250        cp->blocksWantedIsDirty = TRUE;
251        cp->haveValidIsDirty = TRUE;
252
253        /* to set the remaining fields, we walk through every block... */
254        while( b < cp->tor->blockCount )
255        {
256            if( tr_bitfieldHasFast( blockBitfield, b ) )
257                ++completeBlocksInPiece;
258
259            ++b;
260            ++pieceBlock;
261
262            /* by the time we reach the end of a piece, we have enough info
263               to update that piece's slot in cp.completeBlocks and cp.pieceBitfield */
264            if( pieceBlock == blocksInCurrentPiece )
265            {
266                cp->completeBlocks[p] = completeBlocksInPiece;
267                completeBlocksInTorrent += completeBlocksInPiece;
268                if( completeBlocksInPiece == blocksInCurrentPiece )
269                    tr_bitfieldAdd( &cp->pieceBitfield, p );
270
271                /* reset the per-piece counters because we're starting on a new piece now */
272                ++p;
273                completeBlocksInPiece = 0;
274                pieceBlock = 0;
275                blocksInCurrentPiece = tr_torPieceCountBlocks( cp->tor, p );
276            }
277        }
278
279        /* update sizeNow */
280        cp->sizeNow = completeBlocksInTorrent;
281        cp->sizeNow *= tr_torBlockCountBytes( cp->tor, 0 );
282        if( tr_bitfieldHasFast( &cp->blockBitfield, cp->tor->blockCount-1 ) ) {
283            /* the last block is usually smaller than the other blocks,
284               so handle that special case or cp->sizeNow might be too large */
285            cp->sizeNow -= tr_torBlockCountBytes( cp->tor, 0 );
286            cp->sizeNow += tr_torBlockCountBytes( cp->tor, cp->tor->blockCount-1 );
287        }
288    }
289
290    return success;
291}
292
293/***
294****
295***/
296
297tr_completeness
298tr_cpGetStatus( const tr_completion * cp )
299{
300    if( !tr_torrentHasMetadata( cp->tor ) ) return TR_LEECH;
301    if( cp->sizeNow == cp->tor->info.totalSize ) return TR_SEED;
302    if( cp->sizeNow == tr_cpSizeWhenDone( cp ) ) return TR_PARTIAL_SEED;
303    return TR_LEECH;
304}
305
306static uint64_t
307calculateHaveValid( const tr_completion * ccp )
308{
309    uint64_t                  b = 0;
310    tr_piece_index_t          i;
311    const tr_torrent        * tor            = ccp->tor;
312    const uint64_t            pieceSize      = tor->info.pieceSize;
313    const uint64_t            lastPieceSize  = tor->lastPieceSize;
314    const tr_piece_index_t    lastPiece      = tor->info.pieceCount - 1;
315
316    if( !tr_torrentHasMetadata( tor ) )
317        return 0;
318
319    for( i=0; i!=lastPiece; ++i )
320        if( tr_cpPieceIsComplete( ccp, i ) )
321            b += pieceSize;
322
323    if( tr_cpPieceIsComplete( ccp, lastPiece ) )
324        b += lastPieceSize;
325
326    return b;
327}
328
329uint64_t
330tr_cpHaveValid( const tr_completion * ccp )
331{
332    if( ccp->haveValidIsDirty )
333    {
334        tr_completion * cp = (tr_completion *) ccp; /* mutable */
335        cp->haveValidLazy = calculateHaveValid( ccp );
336        cp->haveValidIsDirty = 0;
337    }
338
339    return ccp->haveValidLazy;
340}
341
342void
343tr_cpGetAmountDone( const tr_completion * cp,
344                    float *               tab,
345                    int                   tabCount )
346{
347    int                i;
348    const tr_torrent * tor = cp->tor;
349    const float        interval = tor->info.pieceCount / (float)tabCount;
350    const int          isSeed = tr_cpGetStatus( cp ) == TR_SEED;
351
352    for( i = 0; i < tabCount; ++i )
353    {
354        const tr_piece_index_t piece = i * interval;
355
356        if( tor == NULL )
357            tab[i] = 0.0f;
358        else if( isSeed || tr_cpPieceIsComplete( cp, piece ) )
359            tab[i] = 1.0f;
360        else
361            tab[i] = (float)cp->completeBlocks[piece] /
362                     tr_torPieceCountBlocks( tor, piece );
363    }
364}
365
366int
367tr_cpMissingBlocksInPiece( const tr_completion * cp, tr_piece_index_t piece )
368{
369    return tr_torPieceCountBlocks( cp->tor, piece ) - cp->completeBlocks[piece];
370}
371
372
373tr_bool
374tr_cpPieceIsComplete( const tr_completion * cp, tr_piece_index_t piece )
375{
376    return cp->completeBlocks[piece] == tr_torPieceCountBlocks( cp->tor, piece );
377}
378
379tr_bool
380tr_cpFileIsComplete( const tr_completion * cp, tr_file_index_t fileIndex )
381{
382    tr_block_index_t block;
383
384    const tr_torrent * tor = cp->tor;
385    const tr_file * file = &tor->info.files[fileIndex];
386
387    if( file->firstPiece == file->lastPiece )
388    {
389        const tr_block_index_t firstBlock = file->offset / tor->blockSize;
390        const tr_block_index_t lastBlock = file->length ? ( ( file->offset + file->length - 1 ) / tor->blockSize ) : firstBlock;
391        for( block=firstBlock; block<=lastBlock; ++block )
392            if( !tr_cpBlockIsCompleteFast( cp, block ) )
393                return FALSE;
394    }
395    else
396    {
397        tr_piece_index_t piece;
398        tr_block_index_t firstBlock;
399        tr_block_index_t firstBlockInLastPiece;
400        tr_block_index_t lastBlock;
401        tr_block_index_t lastBlockInFirstPiece;
402        uint64_t lastByteInFirstPiece;
403        uint64_t firstByteInLastPiece;
404
405        /* go piece-by-piece in the middle pieces... it's faster than block-by-block */
406        for( piece=file->firstPiece+1; piece<file->lastPiece; ++piece )
407            if( !tr_cpPieceIsComplete( cp, piece ) )
408                return FALSE;
409
410        /* go block-by-block in the first piece */
411        firstBlock = file->offset / tor->blockSize;
412        lastByteInFirstPiece = ( (uint64_t)(file->firstPiece+1) * tor->info.pieceSize ) - 1;
413        lastBlockInFirstPiece = lastByteInFirstPiece / tor->blockSize;
414        assert( lastBlockInFirstPiece >= firstBlock );
415        assert( lastBlockInFirstPiece - firstBlock <= tr_torPieceCountBlocks( tor, file->firstPiece ) );
416        for( block=firstBlock; block<=lastBlockInFirstPiece; ++block )
417            if( !tr_cpBlockIsCompleteFast( cp, block ) )
418                return FALSE;
419
420        /* go block-by-block in the last piece */
421        lastBlock = file->length ? ( ( file->offset + file->length - 1 ) / tor->blockSize ) : firstBlock;
422        firstByteInLastPiece = (uint64_t)file->lastPiece * tor->info.pieceSize;
423        firstBlockInLastPiece = firstByteInLastPiece / tor->blockSize;
424        assert( firstBlockInLastPiece <= lastBlock );
425        assert( firstBlockInLastPiece >= firstBlock );
426        assert( firstBlockInLastPiece >= lastBlockInFirstPiece );
427        assert( lastBlock - firstBlockInLastPiece <= tr_torPieceCountBlocks( tor, file->lastPiece ) );
428        for( block=firstBlockInLastPiece; block<=lastBlock; ++block )
429            if( !tr_cpBlockIsCompleteFast( cp, block ) )
430                return FALSE;
431    }
432
433    return TRUE;
434
435}
Note: See TracBrowser for help on using the repository browser.