From 31c20c515d96c7311aa3483287202a48dd39cefb Mon Sep 17 00:00:00 2001 From: erdgeist <> Date: Tue, 12 Dec 2006 02:37:19 +0000 Subject: This is a complete rewrite... assume nothing works. --- opentracker.c | 4 +- trackerlogic.c | 356 +++++++++++++++++++++++---------------------------------- trackerlogic.h | 55 +++++---- 3 files changed, 179 insertions(+), 236 deletions(-) diff --git a/opentracker.c b/opentracker.c index f3a7a29..9c76f7f 100644 --- a/opentracker.c +++ b/opentracker.c @@ -141,8 +141,8 @@ e400: case 8: if( byte_diff(data,8,"announce")) goto e404; - byte_copy( peer.ip, 4, h->ip ); - peer.port = 6881; + byte_copy( &peer.ip, 4, h->ip ); + peer.port_flags = 6881 << 16; numwant = 50; compact = 1; scanon = 1; diff --git a/trackerlogic.c b/trackerlogic.c index 03e7bd8..c57d1a9 100644 --- a/trackerlogic.c +++ b/trackerlogic.c @@ -8,12 +8,19 @@ #include #include #include +#include #include +#include +#include "scan.h" +#include "byte.h" + // Helper functions for binary_find // int compare_hash( const void *hash1, const void *hash2 ) { return memcmp( hash1, hash2, sizeof( ot_hash )); } -int compare_ip_port( const void *peer1, const void *peer2 ) { return memcmp( &((ot_peer)peer1)->ip, &((ot_peer)peer2)->ip, 6); } +int compare_ip_port( const void *peer1, const void *peer2 ) { +if( ((ot_peer)peer1)->ip != ((ot_peer)peer2)->ip ) return ((ot_peer)peer1)->ip - ((ot_peer)peer2)->ip; +return ((ot_peer)peer1)->port_flags - ((ot_peer)peer2)->port_flags; } void *binary_search( const void *key, const void *base, unsigned long member_count, const unsigned long member_size, @@ -40,235 +47,169 @@ void *binary_search( const void *key, const void *base, // Converter function from memory to human readable hex strings // * definitely not thread safe!!! // -char ths[1+2*20];char *to_hex(ot_byte*s){char*m="0123456789ABCDEF";char*e=ths+40;char*t=ths;while(t>4];*t++=m[*s++&15];}*t=0;return ths;} +char ths[1+2*20];char*to_hex(ot_byte*s){char*m="0123456789ABCDEF";char*e=ths+40;char*t=ths;while(t>4];*t++=m[*s++&15];}*t=0;return ths;} // GLOBAL VARIABLES // -unsigned long torrents_count = 0; -ot_torrent torrents_list = 0; -ot_byte *scratch_space = 0; +struct ot_vector all_torrents[256]; + +void *vector_find_or_insert( ot_vector vector, void *key, size_t member_size, int(*compare_func)(const void*, const void*), int *exactmatch ) { + ot_byte *end = ((ot_byte*)vector->data) + member_size * vector->size; + ot_byte *match = BINARY_FIND( key, vector->data, vector->size, member_size, compare_func, exactmatch ); + + if( exactmatch ) return match; + + if( vector->size + 1 >= vector->space ) { + void *new_data = realloc( vector->data, vector->space ? 2 * vector->space : 1024 ); + if( !new_data ) return NULL; + vector->data = new_data; + vector->space = vector->space ? vector->space * 2 : 1024; + } + MEMMOVE( match + member_size, match, end - match ); + vector->size++; + return match; +} + +int vector_remove_peer( ot_vector vector, ot_peer peer ) { + int exactmatch; + ot_peer end = ((ot_peer)vector->data) + vector->size; + ot_peer match; + + if( !vector->size ) return 0; + match = BINARY_FIND( peer, vector->data, vector->size, sizeof( struct ot_peer ), compare_ip_port, &exactmatch ); + + if( !exactmatch ) return 0; + exactmatch = match->port_flags & PEER_FLAG_SEEDING ? 2 : 1; + MEMMOVE( match, match + 1, end - match - 1 ); + vector->size--; + return exactmatch; +} + +void free_peerlist( ot_peerlist peer_list ) { + int i; + for( i=0; ipeers[i].data ) + free( peer_list->peers[i].data ); + free( peer_list ); +} + +int vector_remove_torrent( ot_vector vector, ot_hash *hash ) { + int exactmatch; + ot_torrent end = ((ot_torrent)vector->data) + vector->size; + ot_torrent match = BINARY_FIND( hash, vector->data, vector->size, sizeof( struct ot_torrent ), compare_hash, &exactmatch ); + + if( !exactmatch ) return -1; + free_peerlist( match->peer_list ); + MEMMOVE( match, match + 1, end - match - 1 ); + vector->size--; + if( ( 3*vector->size < vector->space ) && ( vector->space > 1024 ) ) { + realloc( vector->data, vector->space >> 1 ); + vector->space >>= 1; + } + return 0; +} -#define SETINVALID( i ) (scratch_space[index] = 3); -#define SETSELECTED( i ) (scratch_space[index] = 1); -#define TESTSELECTED( i ) (scratch_space[index] == 1 ) -#define TESTSET( i ) (scratch_space[index]) -#define RANDOM random() +void clean_peerlist( ot_peerlist peer_list ) { + exit( 1 ); +} ot_torrent add_peer_to_torrent( ot_hash *hash, ot_peer peer ) { + int exactmatch; ot_torrent torrent; ot_peer peer_dest; - int exactmatch; + ot_vector torrents_list = all_torrents + *hash[0], peer_pool; - torrent = BINARY_FIND( hash, torrents_list, torrents_count, sizeof( *torrent ), compare_hash, &exactmatch ); - if( !exactmatch ) { - // Assume, OS will provide us with space, after all, this is file backed - MEMMOVE( torrent + 1, torrent, ( torrents_list + torrents_count ) - torrent ); + torrent = vector_find_or_insert( torrents_list, (void*)hash, sizeof( struct ot_torrent ), compare_hash, &exactmatch ); + if( !torrent ) return NULL; + if( !exactmatch ) { // Create a new torrent entry, then + torrent->peer_list = malloc( sizeof (struct ot_peerlist) ); + if( !torrent->peer_list ) { + vector_remove_torrent( torrents_list, hash ); + return NULL; + } MEMMOVE( &torrent->hash, hash, sizeof( ot_hash ) ); - torrent->peer_list = map_file( to_hex( *hash ) ); - torrent->peer_count = 0; - torrent->seed_count = 0; - } - peer_dest = BINARY_FIND( peer, torrent->peer_list, torrent->peer_count, sizeof( *peer_dest ), compare_ip_port, &exactmatch ); - if( exactmatch ) { - // If peer was a seeder but isn't anymore, decrease seeder count - if( ( peer_dest->flags & PEER_FLAG_SEEDING ) && !( peer->flags & PEER_FLAG_SEEDING ) ) - torrent->seed_count--; - if( !( peer_dest->flags & PEER_FLAG_SEEDING ) && ( peer->flags & PEER_FLAG_SEEDING ) ) - torrent->seed_count++; - } else { - // Assume, OS will provide us with space, after all, this is file backed - MEMMOVE( peer_dest + 1, peer_dest, ( torrent->peer_list + torrent->peer_count ) - peer_dest ); + byte_zero( torrent->peer_list, sizeof( struct ot_peerlist )); + torrent->peer_list->base = NOW; + } else + clean_peerlist( torrent->peer_list ); - // Create a new peer entry, then - MEMMOVE( peer_dest, peer, sizeof( ot_peer ) ); + peer_pool = &torrent->peer_list->peers[0]; + peer_dest = vector_find_or_insert( peer_pool, (void*)peer, sizeof( struct ot_peer ), compare_ip_port, &exactmatch ); - torrent->peer_count++; - torrent->seed_count+= ( peer->flags & PEER_FLAG_SEEDING ) ? 1 : 0; + // If we hadn't had a match in current pool, create peer there and + // remove it from all older pools + if( !exactmatch ) { + int i; + MEMMOVE( peer_dest, peer, sizeof( struct ot_peer ) ); + if( peer->port_flags & PEER_FLAG_SEEDING ) + torrent->peer_list->seed_count[0]++; + for( i=1; ipeer_list->peers[i], peer ) ) { + case 0: continue; + case 2: torrent->peer_list->seed_count[i]--; + case 1: default: return torrent; + } + } + } else { + if( (peer_dest->port_flags & PEER_FLAG_SEEDING ) && !(peer->port_flags & PEER_FLAG_SEEDING ) ) + torrent->peer_list->seed_count[0]--; + if( !(peer_dest->port_flags & PEER_FLAG_SEEDING ) && (peer->port_flags & PEER_FLAG_SEEDING ) ) + torrent->peer_list->seed_count[0]++; } - // Set new time out time - peer_dest->death = NOW + OT_TIMEOUT; - return torrent; } -inline int TESTVALIDPEER( ot_peer p ) { return p->death > NOW; } - // Compiles a list of random peers for a torrent -// * scratch space keeps track of death or already selected peers -// * reply must have enough space to hold 1+(1+16+2+1)*amount+1 bytes +// * reply must have enough space to hold 24+6*amount bytes // * Selector function can be anything, maybe test for seeds, etc. -// * that RANDOM may return huge values +// * RANDOM may return huge values // * does not yet check not to return self -// * it is not guaranteed to see all peers, so no assumptions on active seeders/peers may be done -// * since compact format cannot handle v6 addresses, it must be enabled by OT_COMPACT_ONLY // size_t return_peers_for_torrent( ot_torrent torrent, unsigned long amount, char *reply ) { - register ot_peer peer_base = torrent->peer_list; - char *r = reply; - unsigned long peer_count = torrent->peer_count; - unsigned long selected_count = 0, invalid_count = 0; - unsigned long index = 0; - - // optimize later ;) - BZERO( scratch_space, peer_count ); - - while( ( selected_count < amount ) && ( selected_count + invalid_count < peer_count ) ) { - // skip to first non-flagged peer - while( TESTSET(index) ) index = ( index + 1 ) % peer_count; - - if( TESTVALIDPEER( peer_base + index ) ) { - SETINVALID(index); invalid_count++; - } else { - SETSELECTED(index); selected_count++; - index = ( index + RANDOM ) % peer_count; + char *r = reply; + unsigned long peer_count, index; + unsigned long pool_offset = 0, pool_index = 0; + signed long wert = -1; + + for( peer_count=index=0; indexpeer_list->peers[index].size; + if( peer_count < amount ) amount = peer_count; + + r += FORMAT_FORMAT_STRING( r, "d5:peers%li:",6*amount ); + for( index = 0; index < amount; ++index ) { + double step = 1.8*((double)( peer_count - wert - 1 ))/((double)( amount - index )); + int off = random() % (int)floor( step ); + off = 1 + ( off % ( peer_count - wert - 1 )); + wert += off; + + while( pool_offset + off > torrent->peer_list->peers[pool_index].size ) { + off -= torrent->peer_list->peers[pool_index].size - pool_offset; + pool_offset = 0; pool_index++; } - } - // Now our scratchspace contains a list of selected_count valid peers - // Collect them into a reply string - index = 0; - -#ifndef OT_COMPACT_ONLY - r += FORMAT_FIXED_STRING( r, "d5:peersl" ); -#else - r += FORMAT_FORMAT_STRING( r, "d5:peers%li:",6*selected_count ); -#endif - - while( selected_count-- ) { - ot_peer peer; - while( !TESTSELECTED( index ) ) ++index; - peer = peer_base + index; -#ifdef OT_COMPACT_ONLY - MEMMOVE( r, &peer->ip, 4 ); - MEMMOVE( r+4, &peer->port, 2 ); + MEMMOVE( r, ((ot_peer*)torrent->peer_list->peers[pool_index].data)[pool_offset], 6 ); r += 6; -#else - r += FORMAT_FORMAT_STRING( r, "d2:ip%d:%s7:peer id20:%20c4:porti%ie", - peer->flags & PEER_IP_LENGTH_MASK, - peer->ip, - peer->id, - peer->port ); -#endif } -#ifndef OT_COMPACT_ONLY - r += FORMAT_FIXED_STRING( r, "ee" ); -#else - r += FORMAT_FIXED_STRING( r, "e" ); -#endif + *r++ = 'e'; return r - reply; } -// Compacts a torrents peer list -// * torrents older than OT_TIMEOUT are being kicked -// * is rather expensive -// * if this fails, torrent file is invalid, should add flag -// -void heal_torrent( ot_torrent torrent ) { - unsigned long index = 0, base = 0, end, seed_count = 0, now = NOW; - - // Initialize base to first dead peer. - while( ( base < torrent->peer_count ) && torrent->peer_list[base].death <= now ) { - seed_count += ( torrent->peer_list[base].flags & PEER_FLAG_SEEDING ) ? 1 : 0; - base++; - } - - // No dead peers? Home. - if( base == torrent->peer_count ) return; - - // From now index always looks to the next living peer while base keeps track of - // the dead peer that marks the beginning of insert space. - index = base + 1; - - while( 1 ) { - // Let index search for next living peer - while( ( index < torrent->peer_count ) && torrent->peer_list[index].death > now ) index++; - - // No further living peers found - base is our new peer count - if( index == torrent->peer_count ) { - torrent->peer_count = base; - torrent->seed_count = seed_count; - return; - } - - end = index + 1; - - // Let end search for next dead peer (end of living peers) - while( ( end < torrent->peer_count ) && torrent->peer_list[end].death <= now ) { - seed_count += ( torrent->peer_list[end].flags & PEER_FLAG_SEEDING ) ? 1 : 0; - end++; - } - - // We either hit a dead peer or the end of our peers - // In both cases: move block towards base - MEMMOVE( torrent->peer_list + base, torrent->peer_list + index, ( end - index ) * sizeof( struct ot_peer ) ); - base += end - index; - - index = end; - } -} - -void dispose_torrent( ot_torrent torrent ) { - unmap_file( NULL, torrent->peer_list, 0 ); - unlink( to_hex( torrent->hash ) ); - MEMMOVE( torrent, torrent + 1, ( torrents_list + torrents_count ) - ( torrent + 1 ) ); - torrents_count--; -} - -// This function maps a "huge" file into process space -// * giving no name will aqcuire anonymous growable memory -// * memory will not be "freed" from systems vm if once used, until unmap_file -// * I guess, we should be checking for more errors... -// -void *map_file( char *file_name ) { - char *map; - if( file_name ) { - int file_desc=open(file_name,O_RDWR|O_CREAT|O_NDELAY,0644); -printf( "%s\n", file_name ); - if( file_desc < 0) return 0; - lseek( file_desc, OT_HUGE_FILESIZE, SEEK_SET ); - write( file_desc, "_", 1 ); - map=mmap(0,OT_HUGE_FILESIZE,PROT_READ|PROT_WRITE,MAP_SHARED,file_desc,0); - close(file_desc); - } else - map=mmap(0,OT_HUGE_FILESIZE,PROT_READ|PROT_WRITE,MAP_ANON|MAP_PRIVATE,-1,0); - - return (map == (char*)-1) ? 0 : map; -} - -void unmap_file( char *file_name, void *map, unsigned long real_size ) { - munmap( map, OT_HUGE_FILESIZE ); - if( file_name) - truncate( file_name, real_size ); -} - -void count_peers_and_seeds( ot_peer peer_list, unsigned long *peers, unsigned long *seeds ) { - *peers = *seeds = 0; - if( peer_list[*peers].ip ) - do { - *seeds += peer_list[*peers++].flags & PEER_FLAG_SEEDING ? 1 : 0; - } while( compare_ip_port( peer_list + *peers, peer_list + *peers - 1 ) < 0 ); -} - int init_logic( char *directory ) { glob_t globber; int i; - if( directory ) - chdir( directory ); + if( directory ) { + if( chdir( directory )) + return -1; + } - scratch_space = map_file( NULL ); - torrents_list = map_file( NULL ); - torrents_count = 0; + srandom( time(NULL)); - if( !scratch_space || !torrents_list ) { - if( scratch_space || torrents_list ) - unmap_file( NULL, scratch_space ? (void*)scratch_space : (void*)torrents_list, 0 ); - return -1; - } + // Initialize control structures + byte_zero( all_torrents, sizeof (all_torrents)); // Scan directory for filenames in the form [0-9A-F]{20} // * I know this looks ugly, but I've seen A-F to match umlauts as well in strange locales @@ -286,19 +227,8 @@ int init_logic( char *directory ) { "[0-9ABCDEFabcdef][0-9ABCDEFabcdef][0-9ABCDEFabcdef][0-9ABCDEFabcdef]" , GLOB_NOCHECK, 0, &globber) ) { - for( i=0; i +#include /* Should be called BYTE, WORD, DWORD - but some OSs already have that and there's no #iftypedef */ /* They mark memory used as data instead of integer or human readable string - @@ -10,15 +11,9 @@ typedef unsigned char ot_byte; typedef unsigned short ot_word; typedef unsigned long ot_dword; -typedef unsigned long ot_time; typedef ot_byte ot_hash[20]; -typedef ot_byte ot_ip[ 4/*0*/ ]; -// tunables -static const unsigned long OT_TIMEOUT = 2700; -static const unsigned long OT_HUGE_FILESIZE = 1024*1024*256; // Thats 256MB per file, enough for 204800 peers of 128 bytes - -// We will not service v6, yes -#define OT_COMPACT_ONLY +typedef ot_dword ot_ip; +typedef time_t ot_time; #define MEMMOVE memmove #define BZERO bzero @@ -27,28 +22,41 @@ static const unsigned long OT_HUGE_FILESIZE = 1024*1024*256; // Thats 256MB p #define BINARY_FIND binary_search #define NOW time(NULL) +// We maintain a list of 256 pointers to sorted list of ot_torrent structs +// Sort key is, of course, its hash + +// This list points to 9 pools of peers each grouped in five-minute-intervals +// thus achieving a timeout of 2700s or 45 minutes +// These pools are sorted by its binary content + +#define OT_POOLS_COUNT 9 +#define OT_POOLS_TIMEOUT 300 + +typedef struct ot_vector { + void *data; + size_t size; + size_t space; +} *ot_vector; + typedef struct ot_peer { -#ifndef OT_COMPACT_ONLY - ot_hash id; - ot_hash key; -#endif - ot_ip ip; - ot_word port; - ot_time death; - ot_byte flags; + ot_ip ip; + ot_dword port_flags; } *ot_peer; static const ot_byte PEER_FLAG_SEEDING = 0x80; -static const ot_byte PEER_IP_LENGTH_MASK = 0x3f; -typedef struct { +typedef struct ot_peerlist { + ot_time base; + unsigned long seed_count[ OT_POOLS_COUNT ]; + struct ot_vector peers[ OT_POOLS_COUNT ]; +} *ot_peerlist; + +typedef struct ot_torrent { ot_hash hash; - ot_peer peer_list; - unsigned long peer_count; - unsigned long seed_count; + ot_peerlist peer_list; } *ot_torrent; -void *map_file( char *file_name ); -void unmap_file( char *file_name, void *map, unsigned long real_size ); +void *map_file( char *file_name, size_t map_size ); +void unmap_file( char *file_name, void *map, size_t mapped_size, unsigned long real_size ); // This behaves quite like bsearch but allows to find // the insertion point for inserts after unsuccessful searches @@ -68,6 +76,5 @@ void deinit_logic( ); ot_torrent add_peer_to_torrent( ot_hash *hash, ot_peer peer ); size_t return_peers_for_torrent( ot_torrent torrent, unsigned long amount, char *reply ); -void heal_torrent( ot_torrent torrent ); #endif -- cgit v1.2.3