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 <sys/mman.h>
 #include <unistd.h>
 #include <time.h>
+#include <math.h>
 #include <glob.h>
 
+#include <errno.h>
+#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<e){*t++=m[*s>>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<e){*t++=m[*s>>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; i<OT_POOLS_COUNT; ++i )
+    if( peer_list->peers[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; i<OT_POOLS_COUNT; ++i ) {
+      switch( vector_remove_peer( &torrent->peer_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; index<OT_POOLS_COUNT; ++index) peer_count += torrent->peer_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<globber.gl_matchc; ++i ) {
-#ifdef _DEBUG
-      printf( "Found dir: %s\n", globber.gl_pathv[i] );
-#endif
-
-      if( ( torrents_list[torrents_count].peer_list = map_file( globber.gl_pathv[i] ) ) ) {
-        MEMMOVE( &torrents_list[torrents_count].hash, globber.gl_pathv[i], sizeof( ot_hash ) );
-        count_peers_and_seeds( torrents_list[torrents_count].peer_list,
-                              &torrents_list[torrents_count].peer_count,
-                              &torrents_list[torrents_count].seed_count );
-        torrents_count++;        
-      }
-    }
+    for( i=0; i<globber.gl_matchc; ++i )
+      printf( "Found: %s\n", globber.gl_pathv[i] );
   }
 
   globfree( &globber );
@@ -306,9 +236,15 @@ int init_logic( char *directory ) {
 }
 
 void deinit_logic( ) {
-  // For all torrents... blablabla
-  while( torrents_count-- )
-    unmap_file( to_hex(torrents_list[torrents_count].hash), torrents_list[torrents_count].peer_list, torrents_list[torrents_count].peer_count * sizeof(struct ot_peer) );
-  unmap_file( NULL, torrents_list, 0 );
-  unmap_file( NULL, scratch_space, 0 );
+  int i, j;
+  // Free all torrents...
+  for(i=0; i<256; ++i ) {
+    if( all_torrents[i].size ) {
+      ot_torrent torrents_list = (ot_torrent)all_torrents[i].data;
+      for( j=0; j<all_torrents[i].size; ++j )
+        free_peerlist( torrents_list[j].peer_list );
+      free( all_torrents[i].data );
+    }
+  }
+  byte_zero( all_torrents, sizeof (all_torrents));
 }
diff --git a/trackerlogic.h b/trackerlogic.h
index ad18cba..73f5d16 100644
--- a/trackerlogic.h
+++ b/trackerlogic.h
@@ -2,6 +2,7 @@
 #define __TRACKERLOGIC_H__
 
 #include <sys/types.h>
+#include <sys/time.h>
 
 /* 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