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. --- trackerlogic.c | 356 +++++++++++++++++++++++---------------------------------- 1 file changed, 146 insertions(+), 210 deletions(-) (limited to 'trackerlogic.c') 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