includes/libs/MapCacheLRU.php

   1 <?php
   2 /**
   3  * Per-process memory cache for storing items.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  * @ingroup Cache
  22  */
  23 use Wikimedia\Assert\Assert;
  24
  25 /**
  26  * Handles a simple LRU key/value map with a maximum number of entries
  27  *
  28  * The last-modification timestamp of entries is internally tracked so that callers can
  29  * specify the maximum acceptable age of entries in calls to the has() method. As a convenience,
  30  * the hasField(), getField(), and setField() methods can be used for entries that are field/value
  31  * maps themselves; such fields will have their own internally tracked last-modification timestamp.
  32  *
  33  * @see ProcessCacheLRU
  34  * @ingroup Cache
  35  * @since 1.23
  36  */
  37 class MapCacheLRU implements IExpiringStore, Serializable {
  38         /** @var array Map of (key => value) */
  39         private $cache = [];
  40         /** @var array Map of (key => (UNIX timestamp, (field => UNIX timestamp))) */
  41         private $timestamps = [];
  42         /** @var float Default entry timestamp if not specified */
  43         private $epoch;
  44
  45         /** @var int Max number of entries */
  46         private $maxCacheKeys;
  47
  48         /** @var float|null */
  49         private $wallClockOverride;
  50
  51         const RANK_TOP = 1.0;
  52
  53         /** @var int Array key that holds the entry's main timestamp (flat key use) */
  54         const SIMPLE = 0;
  55         /** @var int Array key that holds the entry's field timestamps (nested key use) */
  56         const FIELDS = 1;
  57
  58         /**
  59          * @param int $maxKeys Maximum number of entries allowed (min 1)
  60          * @throws Exception When $maxKeys is not an int or not above zero
  61          */
  62         public function __construct( $maxKeys ) {
  63                 Assert::parameterType( 'integer', $maxKeys, '$maxKeys' );
  64                 Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
  65
  66                 $this->maxCacheKeys = $maxKeys;
  67                 // Use the current time as the default "as of" timestamp of entries
  68                 $this->epoch = $this->getCurrentTime();
  69         }
  70
  71         /**
  72          * @param array $values Key/value map in order of increasingly recent access
  73          * @param int $maxKeys
  74          * @return MapCacheLRU
  75          * @since 1.30
  76          */
  77         public static function newFromArray( array $values, $maxKeys ) {
  78                 $mapCache = new self( $maxKeys );
  79                 $mapCache->cache = ( count( $values ) > $maxKeys )
  80                         ? array_slice( $values, -$maxKeys, null, true )
  81                         : $values;
  82
  83                 return $mapCache;
  84         }
  85
  86         /**
  87          * @return array Key/value map in order of increasingly recent access
  88          * @since 1.30
  89          */
  90         public function toArray() {
  91                 return $this->cache;
  92         }
  93
  94         /**
  95          * Set a key/value pair.
  96          * This will prune the cache if it gets too large based on LRU.
  97          * If the item is already set, it will be pushed to the top of the cache.
  98          *
  99          * To reduce evictions due to one-off use of many new keys, $rank can be
 100          * set to have keys start at the top of a bottom fraction of the list. A value
 101          * of 3/8 means values start at the top of the bottom 3/8s of the list and are
 102          * moved to the top of the list when accessed a second time.
 103          *
 104          * @param string $key
 105          * @param mixed $value
 106          * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0]
 107          * @return void
 108          */
 109         public function set( $key, $value, $rank = self::RANK_TOP ) {
 110                 if ( $this->has( $key ) ) {
 111                         $this->ping( $key );
 112                 } elseif ( count( $this->cache ) >= $this->maxCacheKeys ) {
 113                         reset( $this->cache );
 114                         $evictKey = key( $this->cache );
 115                         unset( $this->cache[$evictKey] );
 116                         unset( $this->timestamps[$evictKey] );
 117                 }
 118
 119                 if ( $rank < 1.0 && $rank > 0 ) {
 120                         $offset = intval( $rank * count( $this->cache ) );
 121                         $this->cache = array_slice( $this->cache, 0, $offset, true )
 122                                 + [ $key => $value ]
 123                                 + array_slice( $this->cache, $offset, null, true );
 124                 } else {
 125                         $this->cache[$key] = $value;
 126                 }
 127
 128                 $this->timestamps[$key] = [
 129                         self::SIMPLE => $this->getCurrentTime(),
 130                         self::FIELDS => []
 131                 ];
 132         }
 133
 134         /**
 135          * Check if a key exists
 136          *
 137          * @param string $key
 138          * @param float $maxAge Ignore items older than this many seconds [optional] (since 1.32)
 139          * @return bool
 140          */
 141         public function has( $key, $maxAge = 0.0 ) {
 142                 if ( !is_int( $key ) && !is_string( $key ) ) {
 143                         throw new UnexpectedValueException(
 144                                 __METHOD__ . ': invalid key; must be string or integer.' );
 145                 }
 146
 147                 if ( !array_key_exists( $key, $this->cache ) ) {
 148                         return false;
 149                 }
 150
 151                 return ( $maxAge <= 0 || $this->getAge( $key ) <= $maxAge );
 152         }
 153
 154         /**
 155          * Get the value for a key.
 156          * This returns null if the key is not set.
 157          * If the item is already set, it will be pushed to the top of the cache.
 158          *
 159          * @param string $key
 160          * @param float $maxAge Ignore items older than this many seconds [optional] (since 1.32)
 161          * @return mixed Returns null if the key was not found or is older than $maxAge
 162          */
 163         public function get( $key, $maxAge = 0.0 ) {
 164                 if ( !$this->has( $key, $maxAge ) ) {
 165                         return null;
 166                 }
 167
 168                 $this->ping( $key );
 169
 170                 return $this->cache[$key];
 171         }
 172
 173         /**
 174          * @param string|int $key
 175          * @param string|int $field
 176          * @param mixed $value
 177          * @param float $initRank
 178          */
 179         public function setField( $key, $field, $value, $initRank = self::RANK_TOP ) {
 180                 if ( $this->has( $key ) ) {
 181                         $this->ping( $key );
 182                 } else {
 183                         $this->set( $key, [], $initRank );
 184                 }
 185
 186                 if ( !is_int( $field ) && !is_string( $field ) ) {
 187                         throw new UnexpectedValueException(
 188                                 __METHOD__ . ": invalid field for '$key'; must be string or integer." );
 189                 }
 190
 191                 if ( !is_array( $this->cache[$key] ) ) {
 192                         $type = gettype( $this->cache[$key] );
 193
 194                         throw new UnexpectedValueException( "The value of '$key' ($type) is not an array." );
 195                 }
 196
 197                 $this->cache[$key][$field] = $value;
 198                 $this->timestamps[$key][self::FIELDS][$field] = $this->getCurrentTime();
 199         }
 200
 201         /**
 202          * @param string|int $key
 203          * @param string|int $field
 204          * @param float $maxAge Ignore items older than this many seconds [optional] (since 1.32)
 205          * @return bool
 206          */
 207         public function hasField( $key, $field, $maxAge = 0.0 ) {
 208                 $value = $this->get( $key );
 209
 210                 if ( !is_int( $field ) && !is_string( $field ) ) {
 211                         throw new UnexpectedValueException(
 212                                 __METHOD__ . ": invalid field for '$key'; must be string or integer." );
 213                 }
 214
 215                 if ( !is_array( $value ) || !array_key_exists( $field, $value ) ) {
 216                         return false;
 217                 }
 218
 219                 return ( $maxAge <= 0 || $this->getAge( $key, $field ) <= $maxAge );
 220         }
 221
 222         /**
 223          * @param string|int $key
 224          * @param string|int $field
 225          * @param float $maxAge Ignore items older than this many seconds [optional] (since 1.32)
 226          * @return mixed Returns null if the key was not found or is older than $maxAge
 227          */
 228         public function getField( $key, $field, $maxAge = 0.0 ) {
 229                 if ( !$this->hasField( $key, $field, $maxAge ) ) {
 230                         return null;
 231                 }
 232
 233                 return $this->cache[$key][$field];
 234         }
 235
 236         /**
 237          * @return array
 238          * @since 1.25
 239          */
 240         public function getAllKeys() {
 241                 return array_keys( $this->cache );
 242         }
 243
 244         /**
 245          * Get an item with the given key, producing and setting it if not found.
 246          *
 247          * If the callback returns false, then nothing is stored.
 248          *
 249          * @since 1.28
 250          * @param string $key
 251          * @param callable $callback Callback that will produce the value
 252          * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0]
 253          * @param float $maxAge Ignore items older than this many seconds [Default: 0.0] (since 1.32)
 254          * @return mixed The cached value if found or the result of $callback otherwise
 255          */
 256         public function getWithSetCallback(
 257                 $key, callable $callback, $rank = self::RANK_TOP, $maxAge = 0.0
 258         ) {
 259                 if ( $this->has( $key, $maxAge ) ) {
 260                         $value = $this->get( $key );
 261                 } else {
 262                         $value = call_user_func( $callback );
 263                         if ( $value !== false ) {
 264                                 $this->set( $key, $value, $rank );
 265                         }
 266                 }
 267
 268                 return $value;
 269         }
 270
 271         /**
 272          * Clear one or several cache entries, or all cache entries
 273          *
 274          * @param string|array|null $keys
 275          * @return void
 276          */
 277         public function clear( $keys = null ) {
 278                 if ( func_num_args() == 0 ) {
 279                         $this->cache = [];
 280                         $this->timestamps = [];
 281                 } else {
 282                         foreach ( (array)$keys as $key ) {
 283                                 unset( $this->cache[$key] );
 284                                 unset( $this->timestamps[$key] );
 285                         }
 286                 }
 287         }
 288
 289         /**
 290          * Get the maximum number of keys allowed
 291          *
 292          * @return int
 293          * @since 1.32
 294          */
 295         public function getMaxSize() {
 296                 return $this->maxCacheKeys;
 297         }
 298
 299         /**
 300          * Resize the maximum number of cache entries, removing older entries as needed
 301          *
 302          * @param int $maxKeys Maximum number of entries allowed (min 1)
 303          * @return void
 304          * @throws Exception When $maxKeys is not an int or not above zero
 305          * @since 1.32
 306          */
 307         public function setMaxSize( $maxKeys ) {
 308                 Assert::parameterType( 'integer', $maxKeys, '$maxKeys' );
 309                 Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
 310
 311                 $this->maxCacheKeys = $maxKeys;
 312                 while ( count( $this->cache ) > $this->maxCacheKeys ) {
 313                         reset( $this->cache );
 314                         $evictKey = key( $this->cache );
 315                         unset( $this->cache[$evictKey] );
 316                         unset( $this->timestamps[$evictKey] );
 317                 }
 318         }
 319
 320         /**
 321          * Push an entry to the top of the cache
 322          *
 323          * @param string $key
 324          */
 325         private function ping( $key ) {
 326                 $item = $this->cache[$key];
 327                 unset( $this->cache[$key] );
 328                 $this->cache[$key] = $item;
 329         }
 330
 331         /**
 332          * @param string|int $key
 333          * @param string|int|null $field [optional]
 334          * @return float UNIX timestamp; the age of the given entry or entry field
 335          */
 336         private function getAge( $key, $field = null ) {
 337                 if ( $field !== null ) {
 338                         $mtime = $this->timestamps[$key][self::FIELDS][$field] ?? $this->epoch;
 339                 } else {
 340                         $mtime = $this->timestamps[$key][self::SIMPLE] ?? $this->epoch;
 341                 }
 342
 343                 return ( $this->getCurrentTime() - $mtime );
 344         }
 345
 346         public function serialize() {
 347                 return serialize( [
 348                         'entries' => $this->cache,
 349                         'timestamps' => $this->timestamps
 350                 ] );
 351         }
 352
 353         public function unserialize( $serialized ) {
 354                 $data = unserialize( $serialized );
 355                 $this->cache = $data['entries'] ?? [];
 356                 $this->timestamps = $data['timestamps'] ?? [];
 357                 $this->epoch = $this->getCurrentTime();
 358         }
 359
 360         /**
 361          * @return float UNIX timestamp
 362          * @codeCoverageIgnore
 363          */
 364         protected function getCurrentTime() {
 365                 return $this->wallClockOverride ?: microtime( true );
 366         }
 367
 368         /**
 369          * @param float|null &$time Mock UNIX timestamp for testing
 370          * @codeCoverageIgnore
 371          */
 372         public function setMockTime( &$time ) {
 373                 $this->wallClockOverride =& $time;
 374         }
 375 }