includes/cache/BacklinkCache.php

   1 <?php
   2 /**
   3  * Class for fetching backlink lists, approximate backlink counts and
   4  * partitions.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; if not, write to the Free Software Foundation, Inc.,
  18  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  * http://www.gnu.org/copyleft/gpl.html
  20  *
  21  * @file
  22  * @author Tim Starling
  23  * @copyright © 2009, Tim Starling, Domas Mituzas
  24  * @copyright © 2010, Max Sem
  25  * @copyright © 2011, Antoine Musso
  26  */
  27
  28 use Wikimedia\Rdbms\ResultWrapper;
  29 use Wikimedia\Rdbms\FakeResultWrapper;
  30 use Wikimedia\Rdbms\IDatabase;
  31
  32 /**
  33  * Class for fetching backlink lists, approximate backlink counts and
  34  * partitions. This is a shared cache.
  35  *
  36  * Instances of this class should typically be fetched with the method
  37  * $title->getBacklinkCache().
  38  *
  39  * Ideally you should only get your backlinks from here when you think
  40  * there is some advantage in caching them. Otherwise it's just a waste
  41  * of memory.
  42  *
  43  * Introduced by r47317
  44  */
  45 class BacklinkCache {
  46         /** @var BacklinkCache */
  47         protected static $instance;
  48
  49         /**
  50          * Multi dimensions array representing batches. Keys are:
  51          *  > (string) links table name
  52          *   > (int) batch size
  53          *    > 'numRows' : Number of rows for this link table
  54          *    > 'batches' : [ $start, $end ]
  55          *
  56          * @see BacklinkCache::partitionResult()
  57          *
  58          * Cleared with BacklinkCache::clear()
  59          * @var array[]
  60          */
  61         protected $partitionCache = [];
  62
  63         /**
  64          * Contains the whole links from a database result.
  65          * This is raw data that will be partitioned in $partitionCache
  66          *
  67          * Initialized with BacklinkCache::getLinks()
  68          * Cleared with BacklinkCache::clear()
  69          * @var ResultWrapper[]
  70          */
  71         protected $fullResultCache = [];
  72
  73         /**
  74          * Local copy of a database object.
  75          *
  76          * Accessor: BacklinkCache::getDB()
  77          * Mutator : BacklinkCache::setDB()
  78          * Cleared with BacklinkCache::clear()
  79          */
  80         protected $db;
  81
  82         /**
  83          * Local copy of a Title object
  84          */
  85         protected $title;
  86
  87         const CACHE_EXPIRY = 3600;
  88
  89         /**
  90          * Create a new BacklinkCache
  91          *
  92          * @param Title $title : Title object to create a backlink cache for
  93          */
  94         public function __construct( Title $title ) {
  95                 $this->title = $title;
  96         }
  97
  98         /**
  99          * Create a new BacklinkCache or reuse any existing one.
 100          * Currently, only one cache instance can exist; callers that
 101          * need multiple backlink cache objects should keep them in scope.
 102          *
 103          * @param Title $title Title object to get a backlink cache for
 104          * @return BacklinkCache
 105          */
 106         public static function get( Title $title ) {
 107                 if ( !self::$instance || !self::$instance->title->equals( $title ) ) {
 108                         self::$instance = new self( $title );
 109                 }
 110                 return self::$instance;
 111         }
 112
 113         /**
 114          * Serialization handler, diasallows to serialize the database to prevent
 115          * failures after this class is deserialized from cache with dead DB
 116          * connection.
 117          *
 118          * @return array
 119          */
 120         function __sleep() {
 121                 return [ 'partitionCache', 'fullResultCache', 'title' ];
 122         }
 123
 124         /**
 125          * Clear locally stored data and database object.
 126          */
 127         public function clear() {
 128                 $this->partitionCache = [];
 129                 $this->fullResultCache = [];
 130                 unset( $this->db );
 131         }
 132
 133         /**
 134          * Set the Database object to use
 135          *
 136          * @param IDatabase $db
 137          */
 138         public function setDB( $db ) {
 139                 $this->db = $db;
 140         }
 141
 142         /**
 143          * Get the replica DB connection to the database
 144          * When non existing, will initialize the connection.
 145          * @return IDatabase
 146          */
 147         protected function getDB() {
 148                 if ( !isset( $this->db ) ) {
 149                         $this->db = wfGetDB( DB_REPLICA );
 150                 }
 151
 152                 return $this->db;
 153         }
 154
 155         /**
 156          * Get the backlinks for a given table. Cached in process memory only.
 157          * @param string $table
 158          * @param int|bool $startId
 159          * @param int|bool $endId
 160          * @param int $max
 161          * @return TitleArrayFromResult
 162          */
 163         public function getLinks( $table, $startId = false, $endId = false, $max = INF ) {
 164                 return TitleArray::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) );
 165         }
 166
 167         /**
 168          * Get the backlinks for a given table. Cached in process memory only.
 169          * @param string $table
 170          * @param int|bool $startId
 171          * @param int|bool $endId
 172          * @param int $max
 173          * @param string $select 'all' or 'ids'
 174          * @return ResultWrapper
 175          */
 176         protected function queryLinks( $table, $startId, $endId, $max, $select = 'all' ) {
 177
 178                 $fromField = $this->getPrefix( $table ) . '_from';
 179
 180                 if ( !$startId && !$endId && is_infinite( $max )
 181                         && isset( $this->fullResultCache[$table] )
 182                 ) {
 183                         wfDebug( __METHOD__ . ": got results from cache\n" );
 184                         $res = $this->fullResultCache[$table];
 185                 } else {
 186                         wfDebug( __METHOD__ . ": got results from DB\n" );
 187                         $conds = $this->getConditions( $table );
 188                         // Use the from field in the condition rather than the joined page_id,
 189                         // because databases are stupid and don't necessarily propagate indexes.
 190                         if ( $startId ) {
 191                                 $conds[] = "$fromField >= " . intval( $startId );
 192                         }
 193                         if ( $endId ) {
 194                                 $conds[] = "$fromField <= " . intval( $endId );
 195                         }
 196                         $options = [ 'ORDER BY' => $fromField ];
 197                         if ( is_finite( $max ) && $max > 0 ) {
 198                                 $options['LIMIT'] = $max;
 199                         }
 200
 201                         if ( $select === 'ids' ) {
 202                                 // Just select from the backlink table and ignore the page JOIN
 203                                 $res = $this->getDB()->select(
 204                                         $table,
 205                                         [ $this->getPrefix( $table ) . '_from AS page_id' ],
 206                                         array_filter( $conds, function ( $clause ) { // kind of janky
 207                                                 return !preg_match( '/(\b|=)page_id(\b|=)/', $clause );
 208                                         } ),
 209                                         __METHOD__,
 210                                         $options
 211                                 );
 212                         } else {
 213                                 // Select from the backlink table and JOIN with page title information
 214                                 $res = $this->getDB()->select(
 215                                         [ $table, 'page' ],
 216                                         [ 'page_namespace', 'page_title', 'page_id' ],
 217                                         $conds,
 218                                         __METHOD__,
 219                                         array_merge( [ 'STRAIGHT_JOIN' ], $options )
 220                                 );
 221                         }
 222
 223                         if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) {
 224                                 // The full results fit within the limit, so cache them
 225                                 $this->fullResultCache[$table] = $res;
 226                         } else {
 227                                 wfDebug( __METHOD__ . ": results from DB were uncacheable\n" );
 228                         }
 229                 }
 230
 231                 return $res;
 232         }
 233
 234         /**
 235          * Get the field name prefix for a given table
 236          * @param string $table
 237          * @throws MWException
 238          * @return null|string
 239          */
 240         protected function getPrefix( $table ) {
 241                 static $prefixes = [
 242                         'pagelinks' => 'pl',
 243                         'imagelinks' => 'il',
 244                         'categorylinks' => 'cl',
 245                         'templatelinks' => 'tl',
 246                         'redirect' => 'rd',
 247                 ];
 248
 249                 if ( isset( $prefixes[$table] ) ) {
 250                         return $prefixes[$table];
 251                 } else {
 252                         $prefix = null;
 253                         Hooks::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] );
 254                         if ( $prefix ) {
 255                                 return $prefix;
 256                         } else {
 257                                 throw new MWException( "Invalid table \"$table\" in " . __CLASS__ );
 258                         }
 259                 }
 260         }
 261
 262         /**
 263          * Get the SQL condition array for selecting backlinks, with a join
 264          * on the page table.
 265          * @param string $table
 266          * @throws MWException
 267          * @return array|null
 268          */
 269         protected function getConditions( $table ) {
 270                 $prefix = $this->getPrefix( $table );
 271
 272                 switch ( $table ) {
 273                         case 'pagelinks':
 274                         case 'templatelinks':
 275                                 $conds = [
 276                                         "{$prefix}_namespace" => $this->title->getNamespace(),
 277                                         "{$prefix}_title" => $this->title->getDBkey(),
 278                                         "page_id={$prefix}_from"
 279                                 ];
 280                                 break;
 281                         case 'redirect':
 282                                 $conds = [
 283                                         "{$prefix}_namespace" => $this->title->getNamespace(),
 284                                         "{$prefix}_title" => $this->title->getDBkey(),
 285                                         $this->getDB()->makeList( [
 286                                                 "{$prefix}_interwiki" => '',
 287                                                 "{$prefix}_interwiki IS NULL",
 288                                         ], LIST_OR ),
 289                                         "page_id={$prefix}_from"
 290                                 ];
 291                                 break;
 292                         case 'imagelinks':
 293                         case 'categorylinks':
 294                                 $conds = [
 295                                         "{$prefix}_to" => $this->title->getDBkey(),
 296                                         "page_id={$prefix}_from"
 297                                 ];
 298                                 break;
 299                         default:
 300                                 $conds = null;
 301                                 Hooks::run( 'BacklinkCacheGetConditions', [ $table, $this->title, &$conds ] );
 302                                 if ( !$conds ) {
 303                                         throw new MWException( "Invalid table \"$table\" in " . __CLASS__ );
 304                                 }
 305                 }
 306
 307                 return $conds;
 308         }
 309
 310         /**
 311          * Check if there are any backlinks
 312          * @param string $table
 313          * @return bool
 314          */
 315         public function hasLinks( $table ) {
 316                 return ( $this->getNumLinks( $table, 1 ) > 0 );
 317         }
 318
 319         /**
 320          * Get the approximate number of backlinks
 321          * @param string $table
 322          * @param int $max Only count up to this many backlinks
 323          * @return int
 324          */
 325         public function getNumLinks( $table, $max = INF ) {
 326                 global $wgUpdateRowsPerJob;
 327
 328                 $cache = ObjectCache::getMainWANInstance();
 329                 // 1) try partition cache ...
 330                 if ( isset( $this->partitionCache[$table] ) ) {
 331                         $entry = reset( $this->partitionCache[$table] );
 332
 333                         return min( $max, $entry['numRows'] );
 334                 }
 335
 336                 // 2) ... then try full result cache ...
 337                 if ( isset( $this->fullResultCache[$table] ) ) {
 338                         return min( $max, $this->fullResultCache[$table]->numRows() );
 339                 }
 340
 341                 $memcKey = $cache->makeKey(
 342                         'numbacklinks',
 343                         md5( $this->title->getPrefixedDBkey() ),
 344                         $table
 345                 );
 346
 347                 // 3) ... fallback to memcached ...
 348                 $count = $cache->get( $memcKey );
 349                 if ( $count ) {
 350                         return min( $max, $count );
 351                 }
 352
 353                 // 4) fetch from the database ...
 354                 if ( is_infinite( $max ) ) { // no limit at all
 355                         // Use partition() since it will batch the query and skip the JOIN.
 356                         // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
 357                         $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
 358                         return $this->partitionCache[$table][$wgUpdateRowsPerJob]['numRows'];
 359                 } else { // probably some sane limit
 360                         // Fetch the full title info, since the caller will likely need it next
 361                         $count = $this->getLinks( $table, false, false, $max )->count();
 362                         if ( $count < $max ) { // full count
 363                                 $cache->set( $memcKey, $count, self::CACHE_EXPIRY );
 364                         }
 365                 }
 366
 367                 return min( $max, $count );
 368         }
 369
 370         /**
 371          * Partition the backlinks into batches.
 372          * Returns an array giving the start and end of each range. The first
 373          * batch has a start of false, and the last batch has an end of false.
 374          *
 375          * @param string $table The links table name
 376          * @param int $batchSize
 377          * @return array
 378          */
 379         public function partition( $table, $batchSize ) {
 380                 // 1) try partition cache ...
 381                 if ( isset( $this->partitionCache[$table][$batchSize] ) ) {
 382                         wfDebug( __METHOD__ . ": got from partition cache\n" );
 383
 384                         return $this->partitionCache[$table][$batchSize]['batches'];
 385                 }
 386
 387                 $cache = ObjectCache::getMainWANInstance();
 388                 $this->partitionCache[$table][$batchSize] = false;
 389                 $cacheEntry =& $this->partitionCache[$table][$batchSize];
 390
 391                 // 2) ... then try full result cache ...
 392                 if ( isset( $this->fullResultCache[$table] ) ) {
 393                         $cacheEntry = $this->partitionResult( $this->fullResultCache[$table], $batchSize );
 394                         wfDebug( __METHOD__ . ": got from full result cache\n" );
 395
 396                         return $cacheEntry['batches'];
 397                 }
 398
 399                 $memcKey = $cache->makeKey(
 400                         'backlinks',
 401                         md5( $this->title->getPrefixedDBkey() ),
 402                         $table,
 403                         $batchSize
 404                 );
 405
 406                 // 3) ... fallback to memcached ...
 407                 $memcValue = $cache->get( $memcKey );
 408                 if ( is_array( $memcValue ) ) {
 409                         $cacheEntry = $memcValue;
 410                         wfDebug( __METHOD__ . ": got from memcached $memcKey\n" );
 411
 412                         return $cacheEntry['batches'];
 413                 }
 414
 415                 // 4) ... finally fetch from the slow database :(
 416                 $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result
 417                 // Do the selects in batches to avoid client-side OOMs (T45452).
 418                 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
 419                 $selectSize = max( $batchSize, 200000 - ( 200000 % $batchSize ) );
 420                 $start = false;
 421                 do {
 422                         $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
 423                         $partitions = $this->partitionResult( $res, $batchSize, false );
 424                         // Merge the link count and range partitions for this chunk
 425                         $cacheEntry['numRows'] += $partitions['numRows'];
 426                         $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
 427                         if ( count( $partitions['batches'] ) ) {
 428                                 list( , $lEnd ) = end( $partitions['batches'] );
 429                                 $start = $lEnd + 1; // pick up after this inclusive range
 430                         }
 431                 } while ( $partitions['numRows'] >= $selectSize );
 432                 // Make sure the first range has start=false and the last one has end=false
 433                 if ( count( $cacheEntry['batches'] ) ) {
 434                         $cacheEntry['batches'][0][0] = false;
 435                         $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
 436                 }
 437
 438                 // Save partitions to memcached
 439                 $cache->set( $memcKey, $cacheEntry, self::CACHE_EXPIRY );
 440
 441                 // Save backlink count to memcached
 442                 $memcKey = $cache->makeKey(
 443                         'numbacklinks',
 444                         md5( $this->title->getPrefixedDBkey() ),
 445                         $table
 446                 );
 447                 $cache->set( $memcKey, $cacheEntry['numRows'], self::CACHE_EXPIRY );
 448
 449                 wfDebug( __METHOD__ . ": got from database\n" );
 450
 451                 return $cacheEntry['batches'];
 452         }
 453
 454         /**
 455          * Partition a DB result with backlinks in it into batches
 456          * @param ResultWrapper $res Database result
 457          * @param int $batchSize
 458          * @param bool $isComplete Whether $res includes all the backlinks
 459          * @throws MWException
 460          * @return array
 461          */
 462         protected function partitionResult( $res, $batchSize, $isComplete = true ) {
 463                 $batches = [];
 464                 $numRows = $res->numRows();
 465                 $numBatches = ceil( $numRows / $batchSize );
 466
 467                 for ( $i = 0; $i < $numBatches; $i++ ) {
 468                         if ( $i == 0 && $isComplete ) {
 469                                 $start = false;
 470                         } else {
 471                                 $rowNum = $i * $batchSize;
 472                                 $res->seek( $rowNum );
 473                                 $row = $res->fetchObject();
 474                                 $start = (int)$row->page_id;
 475                         }
 476
 477                         if ( $i == ( $numBatches - 1 ) && $isComplete ) {
 478                                 $end = false;
 479                         } else {
 480                                 $rowNum = min( $numRows - 1, ( $i + 1 ) * $batchSize - 1 );
 481                                 $res->seek( $rowNum );
 482                                 $row = $res->fetchObject();
 483                                 $end = (int)$row->page_id;
 484                         }
 485
 486                         # Sanity check order
 487                         if ( $start && $end && $start > $end ) {
 488                                 throw new MWException( __METHOD__ . ': Internal error: query result out of order' );
 489                         }
 490
 491                         $batches[] = [ $start, $end ];
 492                 }
 493
 494                 return [ 'numRows' => $numRows, 'batches' => $batches ];
 495         }
 496
 497         /**
 498          * Get a Title iterator for cascade-protected template/file use backlinks
 499          *
 500          * @return TitleArray
 501          * @since 1.25
 502          */
 503         public function getCascadeProtectedLinks() {
 504                 $dbr = $this->getDB();
 505
 506                 // @todo: use UNION without breaking tests that use temp tables
 507                 $resSets = [];
 508                 $resSets[] = $dbr->select(
 509                         [ 'templatelinks', 'page_restrictions', 'page' ],
 510                         [ 'page_namespace', 'page_title', 'page_id' ],
 511                         [
 512                                 'tl_namespace' => $this->title->getNamespace(),
 513                                 'tl_title' => $this->title->getDBkey(),
 514                                 'tl_from = pr_page',
 515                                 'pr_cascade' => 1,
 516                                 'page_id = tl_from'
 517                         ],
 518                         __METHOD__,
 519                         [ 'DISTINCT' ]
 520                 );
 521                 if ( $this->title->getNamespace() == NS_FILE ) {
 522                         $resSets[] = $dbr->select(
 523                                 [ 'imagelinks', 'page_restrictions', 'page' ],
 524                                 [ 'page_namespace', 'page_title', 'page_id' ],
 525                                 [
 526                                         'il_to' => $this->title->getDBkey(),
 527                                         'il_from = pr_page',
 528                                         'pr_cascade' => 1,
 529                                         'page_id = il_from'
 530                                 ],
 531                                 __METHOD__,
 532                                 [ 'DISTINCT' ]
 533                         );
 534                 }
 535
 536                 // Combine and de-duplicate the results
 537                 $mergedRes = [];
 538                 foreach ( $resSets as $res ) {
 539                         foreach ( $res as $row ) {
 540                                 $mergedRes[$row->page_id] = $row;
 541                         }
 542                 }
 543
 544                 return TitleArray::newFromResult(
 545                         new FakeResultWrapper( array_values( $mergedRes ) ) );
 546         }
 547 }