Changeset 12024

Timestamp:

Feb 24, 2011, 3:01:26 PM (12 years ago)

Author:

jordan

Message:

(2.2x) backport r11882, r11888 for #4016 "blocklists don't handle overlapping/unsorted rules"

File:

• branches/2.2x/libtransmission/blocklist.c (modified) (14 diffs)

branches/2.2x/libtransmission/blocklist.c

@@ -12 +12 @@
 
 #include <stdio.h>
-#include <stdlib.h> /* free() */
+#include <stdlib.h> /* qsort(), free() */
 #include <string.h>
 
@@ -47 +47 @@
 ***/
 
-struct tr_ip_range
+struct tr_ipv4_range
 {
     uint32_t    begin;
@@ -55 +55 @@
 struct tr_blocklist
 {
-    tr_bool               isEnabled;
-    int                   fd;
-    size_t                ruleCount;
-    size_t                byteCount;
-    char *                filename;
-    struct tr_ip_range *  rules;
+    tr_bool                isEnabled;
+    int                    fd;
+    size_t                 ruleCount;
+    size_t                 byteCount;
+    char *                 filename;
+    struct tr_ipv4_range * rules;
 };
 
@@ -108 +108 @@
     b->fd = fd;
     b->byteCount = byteCount;
-    b->ruleCount = byteCount / sizeof( struct tr_ip_range );
+    b->ruleCount = byteCount / sizeof( struct tr_ipv4_range );
 
     {
@@ -128 +128 @@
                        const void * vb )
 {
-    const uint32_t *           a = va;
-    const struct tr_ip_range * b = vb;
+    const uint32_t *             a = va;
+    const struct tr_ipv4_range * b = vb;
 
     if( *a < b->begin ) return -1;
@@ -207 +207 @@
                          const tr_address * addr )
 {
-    uint32_t                   needle;
-    const struct tr_ip_range * range;
+    uint32_t                     needle;
+    const struct tr_ipv4_range * range;
 
     assert( tr_isAddress( addr ) );
@@ -225 +225 @@
                      b->rules,
                      b->ruleCount,
-                     sizeof( struct tr_ip_range ),
+                     sizeof( struct tr_ipv4_range ),
                      compareAddressToRange );
 
@@ -237 +237 @@
  */
 static tr_bool
-parseLine1( const char * line, struct tr_ip_range * range )
+parseLine1( const char * line, struct tr_ipv4_range * range )
 {
     char * walk;
@@ -273 +273 @@
  */
 static tr_bool
-parseLine2( const char * line, struct tr_ip_range * range )
+parseLine2( const char * line, struct tr_ipv4_range * range )
 {
     int unk;
@@ -301 +301 @@
 
 static int
-parseLine( const char * line, struct tr_ip_range * range )
+parseLine( const char * line, struct tr_ipv4_range * range )
 {
     return parseLine1( line, range )
@@ -307 +307 @@
 }
 
+static int
+compareAddressRangesByFirstAddress( const void * va, const void * vb )
+{
+    const struct tr_ipv4_range * a = va;
+    const struct tr_ipv4_range * b = vb;
+    if( a->begin != b->begin )
+        return a->begin < b->begin ? -1 : 1;
+    return 0;
+}
+
 int
-_tr_blocklistSetContent( tr_blocklist * b,
-                         const char *   filename )
+_tr_blocklistSetContent( tr_blocklist * b, const char * filename )
 {
     FILE * in;
     FILE * out;
     int inCount = 0;
-    int outCount = 0;
     char line[2048];
     const char * err_fmt = _( "Couldn't read \"%1$s\": %2$s" );
+    struct tr_ipv4_range * ranges = NULL;
+    size_t ranges_alloc = 0;
+    size_t ranges_count = 0;
 
     if( !filename )
@@ -341 +352 @@
     }
 
+    /* load the rules into memory */
     while( fgets( line, sizeof( line ), in ) != NULL )
     {
         char * walk;
-        struct tr_ip_range range;
+        struct tr_ipv4_range range;
 
         ++inCount;
@@ -359 +371 @@
         }
 
-        if( fwrite( &range, sizeof( struct tr_ip_range ), 1, out ) != 1 )
+        if( ranges_alloc == ranges_count )
         {
-            tr_err( _( "Couldn't save file \"%1$s\": %2$s" ), b->filename,
-                   tr_strerror( errno ) );
-            break;
+            ranges_alloc += 4096; /* arbitrary */
+            ranges = tr_renew( struct tr_ipv4_range, ranges, ranges_alloc );
         }
 
-        ++outCount;
-    }
-
-    {
+        ranges[ranges_count++] = range;
+    }
+
+    if( ranges_count > 0 ) /* sort and merge */
+    {
+        struct tr_ipv4_range * r;
+        struct tr_ipv4_range * keep = ranges;
+        const struct tr_ipv4_range * end;
+
+        /* sort */
+        qsort( ranges, ranges_count, sizeof( struct tr_ipv4_range ),
+               compareAddressRangesByFirstAddress );
+
+        /* merge */
+        for( r=ranges+1, end=ranges+ranges_count; r!=end; ++r ) {
+            if( keep->end < r->begin )
+                *++keep = *r;
+            else if( keep->end < r->end )
+                keep->end = r->end;
+        }
+
+        ranges_count = keep + 1 - ranges;
+
+#ifndef NDEBUG
+        /* sanity checks: make sure the rules are sorted
+         * in ascending order and don't overlap */
+        {
+            size_t i;
+
+            for( i=0; i<ranges_count; ++i )
+                assert( ranges[i].begin <= ranges[i].end );
+
+            for( i=1; i<ranges_count; ++i )
+                assert( ranges[i-1].end < ranges[i].begin );
+        }
+#endif
+    }
+
+    if( fwrite( ranges, sizeof( struct tr_ipv4_range ), ranges_count, out ) != ranges_count )
+        tr_err( _( "Couldn't save file \"%1$s\": %2$s" ), b->filename, tr_strerror( errno ) );
+    else {
         char * base = tr_basename( b->filename );
-        tr_inf( _( "Blocklist \"%s\" updated with %d entries" ), base, outCount );
+        tr_inf( _( "Blocklist \"%s\" updated with %zu entries" ), base, ranges_count );
         tr_free( base );
     }
 
+    tr_free( ranges );
     fclose( out );
     fclose( in );
@@ -380 +429 @@
     blocklistLoad( b );
 
-    return outCount;
-}
-
+    return ranges_count;
+}