source: trunk/libtransmission/peerutils.h @ 1

Last change on this file since 1 was 1, checked in by root, 15 years ago

Import from 2005-10-26

File size: 23.9 KB
Line 
1/******************************************************************************
2 * Copyright (c) 2005 Eric Petit
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 *****************************************************************************/
22
23static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer );
24
25/***********************************************************************
26 * peerInit
27 ***********************************************************************
28 * Returns NULL if we reached the maximum authorized number of peers.
29 * Otherwise, allocates a new tr_peer_t, add it to the peers list and
30 * returns a pointer to it.
31 **********************************************************************/
32static tr_peer_t * peerInit( tr_torrent_t * tor )
33{
34    tr_peer_t * peer;
35
36    if( tor->peerCount >= TR_MAX_PEER_COUNT )
37    {
38        return NULL;
39    }
40
41    peer              = calloc( sizeof( tr_peer_t ), 1 );
42    peer->amChoking   = 1;
43    peer->peerChoking = 1;
44    peer->date        = tr_date();
45    peer->keepAlive   = peer->date;
46
47    tor->peers[tor->peerCount++] = peer;
48    return peer;
49}
50
51static int peerCmp( tr_peer_t * peer1, tr_peer_t * peer2 )
52{
53    /* Wait until we got the peers' ids */
54    if( peer1->status < PEER_STATUS_CONNECTED ||
55        peer2->status < PEER_STATUS_CONNECTED )
56    {
57        return 1;
58    }
59
60    return memcmp( peer1->id, peer2->id, 20 );
61}
62
63/***********************************************************************
64 * addWithAddr
65 ***********************************************************************
66 * Does nothing if we already have a peer matching 'addr' and 'port'.
67 * Otherwise adds such a new peer.
68 **********************************************************************/
69static void addWithAddr( tr_torrent_t * tor, struct in_addr addr,
70                         in_port_t port )
71{
72    int i;
73    tr_peer_t * peer;
74
75    for( i = 0; i < tor->peerCount; i++ )
76    {
77        peer = tor->peers[i];
78        if( peer->addr.s_addr == addr.s_addr &&
79            peer->port        == port )
80        {
81            /* We are already connected to this peer */
82            return;
83        }
84    }
85
86    if( !( peer = peerInit( tor ) ) )
87    {
88        return;
89    }
90
91    peer->addr   = addr;
92    peer->port   = port;
93    peer->status = PEER_STATUS_IDLE;
94}
95
96static int checkPeer( tr_torrent_t * tor, int i )
97{
98    tr_peer_t * peer = tor->peers[i];
99
100    if( peer->status < PEER_STATUS_CONNECTED &&
101        tr_date() > peer->date + 8000 )
102    {
103        /* If it has been too long, don't wait for the socket
104           to timeout - forget about it now */
105        peer_dbg( "connection timeout" );
106        return 1;
107    }
108
109    /* Drop peers who haven't even sent a keep-alive within the
110       last 3 minutes */
111    if( tr_date() > peer->date + 180000 )
112    {
113        peer_dbg( "read timeout" );
114        return 1;
115    }
116
117    /* Drop peers which are supposed to upload but actually
118       haven't sent anything within the last minute */
119    if( peer->inRequestCount && tr_date() > peer->date + 60000 )
120    {
121        peer_dbg( "bad uploader" );
122        return 1;
123    }
124
125#if 0
126    /* Choke unchoked peers we are not sending anything to */
127    if( !peer->amChoking && tr_date() > peer->outDate + 10000 )
128    {
129        peer_dbg( "not worth the unchoke" );
130        if( sendChoke( peer, 1 ) )
131        {
132            goto dropPeer;
133        }
134        peer->outSlow = 1;
135        tr_uploadChoked( tor->upload );
136    }
137#endif
138
139    if( peer->status & PEER_STATUS_CONNECTED )
140    {
141        /* Send keep-alive every 2 minutes */
142        if( tr_date() > peer->keepAlive + 120000 )
143        {
144            sendKeepAlive( peer );
145            peer->keepAlive = tr_date();
146        }
147
148        /* Choke or unchoke some people */
149        /* TODO: prefer people who upload to us */
150        if( !peer->amChoking && !peer->peerInterested )
151        {
152            /* He doesn't need us */
153            sendChoke( peer, 1 );
154            tr_uploadChoked( tor->upload );
155        }
156        if( peer->amChoking && peer->peerInterested &&
157            !peer->outSlow && tr_uploadCanUnchoke( tor->upload ) )
158        {
159            sendChoke( peer, 0 );
160            tr_uploadUnchoked( tor->upload );
161        }
162    }
163
164    return 0;
165}
166
167static int parseMessage( tr_torrent_t * tor, tr_peer_t * peer,
168                         int newBytes )
169{
170    tr_info_t * inf = &tor->info;
171
172    int       i, j;
173    int       len;
174    char      id;
175    uint8_t * p   = peer->buf;
176    uint8_t * end = &p[peer->pos];
177   
178    for( ;; )
179    {
180        if( peer->pos < 4 )
181        {
182            break;
183        }
184
185        if( peer->status & PEER_STATUS_HANDSHAKE )
186        {
187            char * client;
188
189            if( p[0] != 19 || memcmp( &p[1], "Bit", 3 ) )
190            {
191                /* Don't wait until we get 68 bytes, this is wrong
192                   already */
193                peer_dbg( "GET  handshake, invalid" );
194                tr_netSend( peer->socket, (uint8_t *) "Nice try...\r\n", 13 );
195                return 1;
196            }
197
198            if( peer->pos < 68 )
199            {
200                break;
201            }
202
203            if( memcmp( &p[4], "Torrent protocol", 16 ) )
204            {
205                peer_dbg( "GET  handshake, invalid" );
206                return 1;
207            }
208
209            if( memcmp( &p[28], inf->hash, 20 ) )
210            {
211                peer_dbg( "GET  handshake, wrong torrent hash" );
212                return 1;
213            }
214
215            if( !memcmp( &p[48], tor->id, 20 ) )
216            {
217                /* We are connected to ourselves... */
218                peer_dbg( "GET  handshake, that is us" );
219                return 1;
220            }
221
222            peer->status  = PEER_STATUS_CONNECTED;
223            memcpy( peer->id, &p[48], 20 );
224            p            += 68;
225            peer->pos    -= 68;
226
227            for( i = 0; i < tor->peerCount; i++ )
228            {
229                if( tor->peers[i] == peer )
230                {
231                    continue;
232                }
233                if( !peerCmp( peer, tor->peers[i] ) )
234                {
235                    peer_dbg( "GET  handshake, duplicate" );
236                    return 1;
237                }
238            }
239
240            client = tr_clientForId( (uint8_t *) peer->id );
241            peer_dbg( "GET  handshake, ok (%s)", client );
242            free( client );
243
244            sendBitfield( tor, peer );
245
246            continue;
247        }
248       
249        /* Get payload size */
250        TR_NTOHL( p, len );
251        p += 4;
252
253        if( len > 9 + tor->blockSize )
254        {
255            /* This shouldn't happen. Forget about that peer */
256            peer_dbg( "message too large" );
257            return 1;
258        }
259
260        if( !len )
261        {
262            /* keep-alive */
263            peer_dbg( "GET  keep-alive" );
264            peer->pos -= 4;
265            continue;
266        }
267
268        /* That's a piece coming */
269        if( p < end && *p == 7 )
270        {
271            /* XXX */
272            tor->downloaded[9] += newBytes;
273            peer->inTotal      += newBytes;
274            newBytes            = 0;
275        }
276
277        if( &p[len] > end )
278        {
279            /* We do not have the entire message */
280            p -= 4;
281            break;
282        }
283
284        /* Remaining data after this message */
285        peer->pos -= 4 + len;
286
287        /* Type of the message */
288        id = *(p++);
289
290        switch( id )
291        {
292            case 0: /* choke */
293            {
294                tr_request_t * r;
295
296                if( len != 1 )
297                {
298                    peer_dbg( "GET  choke, invalid" );
299                    return 1;
300                }
301
302                peer_dbg( "GET  choke" );
303                peer->peerChoking    = 1;
304
305                for( i = 0; i < peer->inRequestCount; i++ )
306                {
307                    r = &peer->inRequests[i];
308                    if( tor->blockHave[tr_block(r->index,r->begin)] > 0 )
309                    {
310                        tor->blockHave[tr_block(r->index,r->begin)]--;
311                    }
312                }
313                peer->inRequestCount = 0;
314
315                break;
316            }
317            case 1: /* unchoke */
318                if( len != 1 )
319                {
320                    peer_dbg( "GET  unchoke, invalid" );
321                    return 1;
322                }
323                peer_dbg( "GET  unchoke" );
324                peer->peerChoking = 0;
325                break;
326            case 2: /* interested */
327                if( len != 1 )
328                {
329                    peer_dbg( "GET  interested, invalid" );
330                    return 1;
331                }
332                peer_dbg( "GET  interested" );
333                peer->peerInterested = 1;
334                break;
335            case 3: /* uninterested */
336                if( len != 1 )
337                {
338                    peer_dbg( "GET  uninterested, invalid" );
339                    return 1;
340                }
341                peer_dbg( "GET  uninterested" );
342                peer->peerInterested = 0;
343                break;
344            case 4: /* have */
345            {
346                uint32_t piece;
347                if( len != 5 )
348                {
349                    peer_dbg( "GET  have, invalid" );
350                    return 1;
351                }
352                TR_NTOHL( p, piece );
353                if( !peer->bitfield )
354                {
355                    peer->bitfield = calloc( ( inf->pieceCount + 7 ) / 8, 1 );
356                }
357                tr_bitfieldAdd( peer->bitfield, piece );
358
359                updateInterest( tor, peer );
360
361                peer_dbg( "GET  have %d", piece );
362                break;
363            }
364            case 5: /* bitfield */
365            {
366                int bitfieldSize;
367
368                bitfieldSize = ( inf->pieceCount + 7 ) / 8;
369               
370                if( len != 1 + bitfieldSize )
371                {
372                    peer_dbg( "GET  bitfield, wrong size" );
373                    return 1;
374                }
375
376                /* Make sure the spare bits are unset */
377                if( ( inf->pieceCount & 0x7 ) )
378                {
379                    uint8_t lastByte;
380                   
381                    lastByte   = p[bitfieldSize-1];
382                    lastByte <<= inf->pieceCount & 0x7;
383                    lastByte  &= 0xFF;
384
385                    if( lastByte )
386                    {
387                        peer_dbg( "GET  bitfield, spare bits set" );
388                        return 1;
389                    }
390                }
391
392                if( !peer->bitfield )
393                {
394                    peer->bitfield = malloc( bitfieldSize );
395                }
396                memcpy( peer->bitfield, p, bitfieldSize );
397
398                updateInterest( tor, peer );
399
400                peer_dbg( "GET  bitfield, ok" );
401                break;
402            }
403            case 6: /* request */
404            {
405                int index, begin, length;
406
407                if( peer->amChoking )
408                {
409                    /* Didn't he get it? */
410                    sendChoke( peer, 1 );
411                    break;
412                }
413               
414                TR_NTOHL( p,     index );
415                TR_NTOHL( &p[4], begin );
416                TR_NTOHL( &p[8], length );
417
418                peer_dbg( "GET  request %d/%d (%d bytes)",
419                          index, begin, length );
420
421                /* TODO sanity checks (do we have the piece, etc) */
422
423                if( length > 16384 )
424                {
425                    /* Sorry mate */
426                    return 1;
427                }
428
429                if( peer->outRequestCount < MAX_REQUEST_COUNT )
430                {
431                    tr_request_t * r;
432                   
433                    r         = &peer->outRequests[peer->outRequestCount];
434                    r->index  = index;
435                    r->begin  = begin;
436                    r->length = length;
437
438                    (peer->outRequestCount)++;
439                }
440                else
441                {
442                    tr_err( "Too many requests" );
443                    return 1;
444                }
445                break;
446            }
447            case 7: /* piece */
448            {
449                int index, begin;
450                int block;
451                tr_request_t * r;
452
453                TR_NTOHL( p,     index );
454                TR_NTOHL( &p[4], begin );
455
456                peer_dbg( "GET  piece %d/%d (%d bytes)",
457                          index, begin, len - 9 );
458
459                if( peer->inRequestCount < 1 )
460                {
461                    /* Our "cancel" was probably late */
462                    peer_dbg( "not expecting a block" );
463                    break;
464                }
465               
466                r = &peer->inRequests[0];
467                if( index != r->index || begin != r->begin )
468                {
469                    int suckyClient;
470
471                    /* Either our "cancel" was late, or this is a sucky
472                       client that cannot deal with multiple requests */
473                    suckyClient = 0;
474                    for( i = 0; i < peer->inRequestCount; i++ )
475                    {
476                        r = &peer->inRequests[i];
477
478                        if( index != r->index || begin != r->begin )
479                        {
480                            continue;
481                        }
482
483                        /* Sucky client, he dropped the previous requests */
484                        peer_dbg( "block was expected later" );
485                        for( j = 0; j < i; j++ )
486                        {
487                            r = &peer->inRequests[j];
488                            if( tor->blockHave[tr_block(r->index,r->begin)] > 0 )
489                            {
490                                tor->blockHave[tr_block(r->index,r->begin)]--;
491                            }
492                        }
493                        suckyClient = 1;
494                        peer->inRequestCount -= i;
495                        memmove( &peer->inRequests[0], &peer->inRequests[i],
496                                 peer->inRequestCount * sizeof( tr_request_t ) );
497                        r = &peer->inRequests[0];
498                        break;
499                    }
500
501                    if( !suckyClient )
502                    {
503                        r = &peer->inRequests[0];
504                        peer_dbg( "wrong block (expecting %d/%d)",
505                                  r->index, r->begin );
506                        break;
507                    }
508                }
509
510                if( len - 9 != r->length )
511                {
512                    peer_dbg( "wrong size (expecting %d)", r->length );
513                    return 1;
514                }
515
516                block = tr_block( r->index, r->begin );
517                if( tor->blockHave[block] < 0 )
518                {
519                    peer_dbg( "have this block already" );
520                    (peer->inRequestCount)--;
521                    memmove( &peer->inRequests[0], &peer->inRequests[1],
522                             peer->inRequestCount * sizeof( tr_request_t ) );
523                    break;
524                }
525
526                tor->blockHave[block]  = -1;
527                tor->blockHaveCount   +=  1;
528                tr_ioWrite( tor->io, index, begin, len - 9, &p[8] );
529
530                sendCancel( tor, block );
531
532                if( tr_bitfieldHas( tor->bitfield, index ) )
533                {
534                    tr_peer_t * otherPeer;
535
536                    for( i = 0; i < tor->peerCount; i++ )
537                    {
538                        otherPeer = tor->peers[i];
539
540                        if( otherPeer->status < PEER_STATUS_CONNECTED )
541                        {
542                            continue;
543                        }
544
545                        sendHave( otherPeer, index );
546                        updateInterest( tor, otherPeer );
547                    }
548                }
549
550                (peer->inRequestCount)--;
551                memmove( &peer->inRequests[0], &peer->inRequests[1],
552                         peer->inRequestCount * sizeof( tr_request_t ) );
553                break;
554            }
555            case 8: /* cancel */
556            {
557                int index, begin, length;
558                int i;
559                tr_request_t * r;
560
561                TR_NTOHL( p,     index );
562                TR_NTOHL( &p[4], begin );
563                TR_NTOHL( &p[8], length );
564
565                peer_dbg( "GET  cancel %d/%d (%d bytes)",
566                          index, begin, length );
567
568                for( i = 0; i < peer->outRequestCount; i++ )
569                {
570                    r = &peer->outRequests[i];
571                    if( r->index == index && r->begin == begin &&
572                        r->length == length )
573                    {
574                        (peer->outRequestCount)--;
575                        memmove( &r[0], &r[1], sizeof( tr_request_t ) *
576                                ( peer->outRequestCount - i ) );
577                        break;
578                    }
579                }
580
581                break;
582            }
583            case 9:
584            {
585                in_port_t port;
586
587                if( len != 3 )
588                {
589                    peer_dbg( "GET  port, invalid" );
590                    return 1;
591                }
592
593                port = *( (in_port_t *) p );
594                peer_dbg( "GET  port %d", ntohs( port ) );
595
596                break;
597            }
598            default:
599            {
600                peer_dbg( "Unknown message '%d'", id );
601                return 1;
602            }
603        }
604
605        p += len - 1;
606    }
607
608    memmove( peer->buf, p, peer->pos );
609
610    return 0;
611}
612
613/***********************************************************************
614 * isInteresting
615 ***********************************************************************
616 * Returns 1 if 'peer' has at least one piece that we haven't completed,
617 * or 0 otherwise.
618 **********************************************************************/
619static int isInteresting( tr_torrent_t * tor, tr_peer_t * peer )
620{
621    tr_info_t * inf = &tor->info;
622
623    int i;
624    int bitfieldSize = ( inf->pieceCount + 7 ) / 8;
625
626    if( !peer->bitfield )
627    {
628        /* We don't know what this peer has */
629        return 0;
630    }
631
632    for( i = 0; i < bitfieldSize; i++ )
633    {
634        if( ( peer->bitfield[i] & ~(tor->bitfield[i]) ) & 0xFF )
635        {
636            return 1;
637        }
638    }
639
640    return 0;
641}
642static void updateInterest( tr_torrent_t * tor, tr_peer_t * peer )
643{
644    int interested = isInteresting( tor, peer );
645
646    if( interested && !peer->amInterested )
647    {
648        sendInterest( peer, 1 );
649    }
650    if( !interested && peer->amInterested )
651    {
652        sendInterest( peer, 0 );
653    }
654}
655
656/***********************************************************************
657 * chooseBlock
658 ***********************************************************************
659 * At this point, we know the peer has at least one block we have an
660 * interest in. If he has more than one, we choose which one we are
661 * going to ask first.
662 * Our main goal is to complete pieces, so we look the pieces which are
663 * missing less blocks.
664 **********************************************************************/
665static int chooseBlock( tr_torrent_t * tor, tr_peer_t * peer )
666{
667    tr_info_t * inf = &tor->info;
668
669    int i, j;
670    int startBlock, endBlock, countBlocks;
671    int missingBlocks, minMissing;
672    int poolSize, * pool;
673    int block, minDownloading;
674
675    /* Choose a piece */
676    pool       = malloc( inf->pieceCount * sizeof( int ) );
677    poolSize   = 0;
678    minMissing = tor->blockCount + 1;
679    for( i = 0; i < inf->pieceCount; i++ )
680    {
681        if( !tr_bitfieldHas( peer->bitfield, i ) )
682        {
683            /* The peer doesn't have this piece */
684            continue;
685        }
686        if( tr_bitfieldHas( tor->bitfield, i ) )
687        {
688            /* We already have it */
689            continue;
690        }
691
692        /* Count how many blocks from this piece are missing */
693        startBlock    = tr_pieceStartBlock( i );
694        countBlocks   = tr_pieceCountBlocks( i );
695        endBlock      = startBlock + countBlocks;
696        missingBlocks = countBlocks;
697        for( j = startBlock; j < endBlock; j++ )
698        {
699            /* TODO: optimize */
700            if( tor->blockHave[j] )
701            {
702                missingBlocks--;
703            }
704            if( missingBlocks > minMissing )
705            {
706                break;
707            }
708        }
709
710        if( missingBlocks < 1 )
711        {
712            /* We are already downloading all blocks */
713            continue;
714        }
715
716        /* We are interested in this piece, remember it */
717        if( missingBlocks < minMissing )
718        {
719            minMissing = missingBlocks;
720            poolSize   = 0;
721        }
722        if( missingBlocks <= minMissing )
723        {
724            pool[poolSize++] = i;
725        }
726    }
727
728    if( poolSize )
729    {
730        /* All pieces in 'pool' have 'minMissing' missing blocks. Find
731           the rarest ones. */
732        uint8_t * bitfield;
733        int piece;
734        int min, foo, j;
735        int * pool2;
736        int   pool2Size;
737
738        pool2     = malloc( poolSize * sizeof( int ) );
739        pool2Size = 0;
740        min       = TR_MAX_PEER_COUNT + 1;
741        for( i = 0; i < poolSize; i++ )
742        {
743            foo = 0;
744            for( j = 0; j < tor->peerCount; j++ )
745            {
746                bitfield = tor->peers[j]->bitfield;
747                if( bitfield && tr_bitfieldHas( bitfield, pool[i] ) )
748                {
749                    foo++;
750                }
751            }
752            if( foo < min )
753            {
754                min       = foo;
755                pool2Size = 0;
756            }
757            if( foo <= min )
758            {
759                pool2[pool2Size++] = pool[i];
760            }
761        }
762        free( pool );
763
764        if( pool2Size < 1 )
765        {
766            /* Shouldn't happen */
767            free( pool2 );
768            return -1;
769        }
770
771        /* All pieces in pool2 have the same number of missing blocks,
772           and are availabme from the same number of peers. Pick a
773           random one */
774        piece = pool2[tr_rand(pool2Size)];
775        free( pool2 );
776
777        /* Pick a block in this piece */
778        startBlock = tr_pieceStartBlock( piece );
779        endBlock   = startBlock + tr_pieceCountBlocks( piece );
780        for( i = startBlock; i < endBlock; i++ )
781        {
782            if( !tor->blockHave[i] )
783            {
784                block = i;
785                goto check;
786            }
787        }
788
789        /* Shouldn't happen */
790        return -1;
791    }
792
793    free( pool );
794
795    /* "End game" mode */
796    block          = -1;
797    minDownloading = TR_MAX_PEER_COUNT + 1;
798    for( i = 0; i < tor->blockCount; i++ )
799    {
800        /* TODO: optimize */
801        if( tor->blockHave[i] > 0 && tor->blockHave[i] < minDownloading )
802        {
803            block          = i;
804            minDownloading = tor->blockHave[i];
805        }
806    }
807
808    if( block < 0 )
809    {
810        /* Shouldn't happen */
811        return -1;
812    }
813
814check:
815    for( i = 0; i < peer->inRequestCount; i++ )
816    {
817        tr_request_t * r;
818        r = &peer->inRequests[i];
819        if( tr_block( r->index, r->begin ) == block )
820        {
821            /* We are already asking this peer for this block */
822            return -1;
823        }
824    }
825
826    return block;
827}
Note: See TracBrowser for help on using the repository browser.