resourceloader: Reduce width of module hash from 7 chars to 5
authorTimo Tijhof <krinklemail@gmail.com>
Mon, 29 Jul 2019 16:15:23 +0000 (17:15 +0100)
committerKrinkle <krinklemail@gmail.com>
Mon, 2 Sep 2019 01:25:48 +0000 (01:25 +0000)
In a nut shell:

* We very often (52% of modules on enwiki) pad the hash with a zero,
  which means the amount of bits we currently compute already fit in
  6 characters already for most modules. For some modules (3%) we
  even padded two zeroes.

* For the (now documented) use cases, the space of 78 Giga
  (78 billion, or 78 milliard) seems more than we need. The space of
  60 million should be enough.

  This follows-up dfd046412f from 2016, which previously shortened the hash
  down from 8 chars of base 64 (or 12 chars of hex) to 7 chars of base 32.
  Before that change, the space was 281 Tera (64^8, or 16^12).

For more details see the added inline comment for ResourceLoader::makeHash,
and also the data at <https://phabricator.wikimedia.org/T229245>.

Bug: T229245
Change-Id: I9ad11772a33b3a44cb625275b1d7353e1393ee49

includes/resourceloader/ResourceLoader.php
includes/resourceloader/ResourceLoaderStartUpModule.php
resources/src/startup/mediawiki.js
tests/phpunit/ResourceLoaderTestCase.php
tests/phpunit/includes/OutputPageTest.php
tests/phpunit/includes/resourceloader/ResourceLoaderClientHtmlTest.php
tests/phpunit/includes/resourceloader/ResourceLoaderStartUpModuleTest.php
tests/phpunit/includes/resourceloader/ResourceLoaderTest.php
tests/qunit/suites/resources/mediawiki/mediawiki.loader.test.js

index 0785225..ca83ff3 100644 (file)
@@ -547,13 +547,81 @@ class ResourceLoader implements LoggerAwareInterface {
        }
 
        /**
+        * @internal For use by ResourceLoaderStartUpModule only.
+        */
+       const HASH_LENGTH = 5;
+
+       /**
+        * Create a hash for module versioning purposes.
+        *
+        * This hash is used in three ways:
+        *
+        * - To differentiate between the current version and a past version
+        *   of a module by the same name.
+        *
+        *   In the cache key of localStorage in the browser (mw.loader.store).
+        *   This store keeps only one version of any given module. As long as the
+        *   next version the client encounters has a different hash from the last
+        *   version it saw, it will correctly discard it in favour of a network fetch.
+        *
+        *   A browser may evict a site's storage container for any reason (e.g. when
+        *   the user hasn't visited a site for some time, and/or when the device is
+        *   low on storage space). Anecdotally it seems devices rarely keep unused
+        *   storage beyond 2 weeks on mobile devices and 4 weeks on desktop.
+        *   But, there is no hard limit or expiration on localStorage.
+        *   ResourceLoader's Client also clears localStorage when the user changes
+        *   their language preference or when they (temporarily) use Debug Mode.
+        *
+        *   The only hard factors that reduce the range of possible versions are
+        *   1) the name and existence of a given module, and
+        *   2) the TTL for mw.loader.store, and
+        *   3) the `$wgResourceLoaderStorageVersion` configuration variable.
+        *
+        * - To identify a batch response of modules from load.php in an HTTP cache.
+        *
+        *   When fetching modules in a batch from load.php, a combined hash
+        *   is created by the JS code, and appended as query parameter.
+        *
+        *   In cache proxies (e.g. Varnish, Nginx) and in the browser's HTTP cache,
+        *   these urls are used to identify other previously cached responses.
+        *   The range of possible versions a given version has to be unique amongst
+        *   is determined by the maximum duration each response is stored for, which
+        *   is controlled by `$wgResourceLoaderMaxage['versioned']`.
+        *
+        * - To detect race conditions between multiple web servers in a MediaWiki
+        *   deployment of which some have the newer version and some still the older
+        *   version.
+        *
+        *   An HTTP request from a browser for the Startup manifest may be responded
+        *   to by a server with the newer version. The browser may then use that to
+        *   request a given module, which may then be responded to by a server with
+        *   the older version. To avoid caching this for too long (which would pollute
+        *   all other users without repairing itself), the combined hash that the JS
+        *   client adds to the url is verified by the server (in ::sendResponseHeaders).
+        *   If they don't match, we instruct cache proxies and clients to not cache
+        *   this response as long as they normally would. This is also the reason
+        *   that the algorithm used here in PHP must match the one used in JS.
+        *
+        * The fnv132 digest creates a 32-bit integer, which goes upto 4 Giga and
+        * needs up to 7 chars in base 36.
+        * Within 7 characters, base 36 can count up to 78,364,164,096 (78 Giga),
+        * (but with fnv132 we'd use very little of this range, mostly padding).
+        * Within 6 characters, base 36 can count up to 2,176,782,336 (2 Giga).
+        * Within 5 characters, base 36 can count up to 60,466,176 (60 Mega).
+        *
         * @since 1.26
         * @param string $value
         * @return string Hash
         */
        public static function makeHash( $value ) {
                $hash = hash( 'fnv132', $value );
-               return Wikimedia\base_convert( $hash, 16, 36, 7 );
+               // The base_convert will pad it (if too short),
+               // then substr() will trim it (if too long).
+               return substr(
+                       Wikimedia\base_convert( $hash, 16, 36, self::HASH_LENGTH ),
+                       0,
+                       self::HASH_LENGTH
+               );
        }
 
        /**
index 58c9ee5..9cb8c4b 100644 (file)
@@ -291,7 +291,7 @@ class ResourceLoaderStartUpModule extends ResourceLoaderModule {
                                $states[$name] = 'error';
                        }
 
-                       if ( $versionHash !== '' && strlen( $versionHash ) !== 7 ) {
+                       if ( $versionHash !== '' && strlen( $versionHash ) !== ResourceLoader::HASH_LENGTH ) {
                                $e = new RuntimeException( "Badly formatted module version hash" );
                                $resourceLoader->outputErrorAndLog( $e,
                                                "Module '{module}' produced an invalid version hash: '{version}'.",
index a4ee488..bbe503d 100644 (file)
@@ -37,8 +37,8 @@
                        hash ^= str.charCodeAt( i );
                }
 
-               hash = ( hash >>> 0 ).toString( 36 );
-               while ( hash.length < 7 ) {
+               hash = ( hash >>> 0 ).toString( 36 ).slice( 0, 5 );
+               while ( hash.length < 5 ) {
                        hash = '0' + hash;
                }
                /* eslint-enable no-bitwise */
 
                                                // In addition to currReqBase, doRequest() will also add 'modules' and 'version'.
                                                // > '&modules='.length === 9
-                                               // > '&version=1234567'.length === 16
-                                               // > 9 + 16 = 25
-                                               currReqBaseLength = makeQueryString( currReqBase ).length + 25;
+                                               // > '&version=12345'.length === 14
+                                               // > 9 + 14 = 23
+                                               currReqBaseLength = makeQueryString( currReqBase ).length + 23;
 
                                                // We may need to split up the request to honor the query string length limit,
                                                // so build it piece by piece.
index 2a21351..6b4b4d4 100644 (file)
@@ -7,7 +7,10 @@ abstract class ResourceLoaderTestCase extends MediaWikiTestCase {
        // Version hash for a blank file module.
        // Result of ResourceLoader::makeHash(), ResourceLoaderTestModule
        // and ResourceLoaderFileModule::getDefinitionSummary().
-       const BLANK_VERSION = '09p30q0';
+       const BLANK_VERSION = '9p30q';
+       // Result of ResoureLoader::makeVersionQuery() for a blank file module.
+       // In other words, result of ResourceLoader::makeHash( BLANK_VERSION );
+       const BLANK_COMBI = 'rbml8';
 
        /**
         * @param array|string $options Language code or options array
index 6520fc5..aa6e494 100644 (file)
@@ -2606,7 +2606,7 @@ class OutputPageTest extends MediaWikiTestCase {
                        [
                                [ 'test.quux', ResourceLoaderModule::TYPE_COMBINED ],
                                "<script nonce=\"secret\">(RLQ=window.RLQ||[]).push(function(){"
-                                       . "mw.loader.implement(\"test.quux@1ev0ijv\",function($,jQuery,require,module){"
+                                       . "mw.loader.implement(\"test.quux@1ev0i\",function($,jQuery,require,module){"
                                        . "mw.test.baz({token:123});},{\"css\":[\".mw-icon{transition:none}"
                                        . "\"]});});</script>"
                        ],
@@ -2669,6 +2669,9 @@ class OutputPageTest extends MediaWikiTestCase {
 
                $op = TestingAccessWrapper::newFromObject( $op );
                $op->rlExemptStyleModules = $exemptStyleModules;
+               $expect = strtr( $expect, [
+                       '{blankCombi}' => ResourceLoaderTestCase::BLANK_COMBI,
+               ] );
                $this->assertEquals(
                        $expect,
                        strval( $op->buildExemptModules() )
@@ -2695,7 +2698,7 @@ class OutputPageTest extends MediaWikiTestCase {
                                'exemptStyleModules' => [ 'site' => [ 'site.styles' ], 'user' => [ 'user.styles' ] ],
                                '<meta name="ResourceLoaderDynamicStyles" content=""/>' . "\n" .
                                '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=site.styles&amp;only=styles"/>' . "\n" .
-                               '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=user.styles&amp;only=styles&amp;version=1ai9g6t"/>',
+                               '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=user.styles&amp;only=styles&amp;version=15pue"/>',
                        ],
                        'custom modules' => [
                                'exemptStyleModules' => [
@@ -2705,8 +2708,8 @@ class OutputPageTest extends MediaWikiTestCase {
                                '<meta name="ResourceLoaderDynamicStyles" content=""/>' . "\n" .
                                '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=example.site.a%2Cb&amp;only=styles"/>' . "\n" .
                                '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=site.styles&amp;only=styles"/>' . "\n" .
-                               '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=example.user&amp;only=styles&amp;version=0a56zyi"/>' . "\n" .
-                               '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=user.styles&amp;only=styles&amp;version=1ai9g6t"/>',
+                               '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=example.user&amp;only=styles&amp;version={blankCombi}"/>' . "\n" .
+                               '<link rel="stylesheet" href="/w/load.php?lang=en&amp;modules=user.styles&amp;only=styles&amp;version=15pue"/>',
                        ],
                ];
                // phpcs:enable
index e1ee324..072468a 100644 (file)
@@ -242,14 +242,14 @@ Deprecation message.' ]
                                'modules' => [ 'test.scripts.user' ],
                                'only' => ResourceLoaderModule::TYPE_SCRIPTS,
                                'extra' => [],
-                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.load("/w/load.php?lang=nl\u0026modules=test.scripts.user\u0026only=scripts\u0026user=Example\u0026version=0a56zyi");});</script>',
+                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.load("/w/load.php?lang=nl\u0026modules=test.scripts.user\u0026only=scripts\u0026user=Example\u0026version={blankCombi}");});</script>',
                        ],
                        [
                                'context' => [],
                                'modules' => [ 'test.user' ],
                                'only' => ResourceLoaderModule::TYPE_COMBINED,
                                'extra' => [],
-                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.load("/w/load.php?lang=nl\u0026modules=test.user\u0026user=Example\u0026version=0a56zyi");});</script>',
+                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.load("/w/load.php?lang=nl\u0026modules=test.user\u0026user=Example\u0026version={blankCombi}");});</script>',
                        ],
                        [
                                'context' => [ 'debug' => 'true' ],
@@ -278,7 +278,7 @@ Deprecation message.' ]
                                'modules' => [ 'test.shouldembed' ],
                                'only' => ResourceLoaderModule::TYPE_COMBINED,
                                'extra' => [],
-                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.implement("test.shouldembed@09p30q0",null,{"css":[]});});</script>',
+                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.implement("test.shouldembed@{blankVer}",null,{"css":[]});});</script>',
                        ],
                        [
                                'context' => [],
@@ -299,7 +299,7 @@ Deprecation message.' ]
                                'modules' => [ 'test', 'test.shouldembed' ],
                                'only' => ResourceLoaderModule::TYPE_COMBINED,
                                'extra' => [],
-                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.load("/w/load.php?lang=nl\u0026modules=test");mw.loader.implement("test.shouldembed@09p30q0",null,{"css":[]});});</script>',
+                               'output' => '<script>(RLQ=window.RLQ||[]).push(function(){mw.loader.load("/w/load.php?lang=nl\u0026modules=test");mw.loader.implement("test.shouldembed@{blankVer}",null,{"css":[]});});</script>',
                        ],
                        [
                                'context' => [],
@@ -351,6 +351,7 @@ Deprecation message.' ]
 
        private static function expandVariables( $text ) {
                return strtr( $text, [
+                       '{blankCombi}' => ResourceLoaderTestCase::BLANK_COMBI,
                        '{blankVer}' => ResourceLoaderTestCase::BLANK_VERSION
                ] );
        }
index d4462e9..9bbf14d 100644 (file)
@@ -261,7 +261,7 @@ mw.loader.state({
                                                'factory' => function () {
                                                        $mock = $this->getMockBuilder( ResourceLoaderTestModule::class )
                                                                ->setMethods( [ 'getVersionHash' ] )->getMock();
-                                                       $mock->method( 'getVersionHash' )->willReturn( '1234567' );
+                                                       $mock->method( 'getVersionHash' )->willReturn( '12345' );
                                                        return $mock;
                                                }
                                        ]
@@ -273,7 +273,7 @@ mw.loader.addSource({
 mw.loader.register([
     [
         "test.version",
-        "1234567"
+        "12345"
     ]
 ]);',
                        ] ],
@@ -296,7 +296,7 @@ mw.loader.addSource({
 mw.loader.register([
     [
         "test.version",
-        "016es8l"
+        "16es8"
     ]
 ]);',
                        ] ],
index 428778e..94e3461 100644 (file)
@@ -725,7 +725,7 @@ END
                );
 
                $this->assertEquals(
-                       ResourceLoader::makeHash( self::BLANK_VERSION ),
+                       self::BLANK_COMBI,
                        $rl->getCombinedVersion( $context, [ 'foo' ] ),
                        'compute foo'
                );
index 3258f8e..4c6e7c9 100644 (file)
                                require( 'testUrlIncDump' ).query,
                                {
                                        modules: 'testUrlIncDump',
-                                       // Expected: Wrapped hash just for this one module
-                                       //   $hash = hash( 'fnv132', 'dump');
-                                       //   base_convert( $hash, 16, 36 ); // "13e9zzn"
-                                       // Previously: Wrapped hash for both modules, despite being in separate requests
-                                       //   $hash = hash( 'fnv132', 'urldump' );
-                                       //   base_convert( $hash, 16, 36 ); // "18kz9ca"
-                                       version: '13e9zzn'
+                                       // Expected: Combine hashes only for the module in the specific HTTP request
+                                       //   hash fnv132 => "13e9zzn"
+                                       // Wrong: Combine hashes for all requested modules, before request-splitting
+                                       //   hash fnv132 => "18kz9ca"
+                                       version: '13e9z'
                                },
                                'Query parameters'
                        );
                                require( 'testUrlOrderDump' ).query,
                                {
                                        modules: 'testUrlOrder,testUrlOrderDump|testUrlOrder.a,b',
-                                       // Expected: Combined in order after string packing
-                                       //   $hash = hash( 'fnv132', 'urldump12' );
-                                       //   base_convert( $hash, 16, 36 ); // "1knqzan"
-                                       // Previously: Combined in order of before string packing
-                                       //   $hash = hash( 'fnv132', 'url12dump' );
-                                       //   base_convert( $hash, 16, 36 ); // "11eo3in"
-                                       version: '1knqzan'
+                                       // Expected: Combined by sorting names after string packing
+                                       //   hash fnv132 = "1knqzan"
+                                       // Wrong: Combined by sorting names before string packing
+                                       //   hash fnv132 => "11eo3in"
+                                       version: '1knqz'
                                },
                                'Query parameters'
                        );