mcs/class/referencesource/System.Data.Entity/System/Data/Common/QueryCache/QueryCacheManager.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="QueryCacheManager.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 // @backupOwner Microsoft
   8 //------------------------------------------------------------------------------
   9
  10 namespace System.Data.Common.QueryCache
  11 {
  12     using System;
  13     using System.Collections.Generic;
  14     using System.Data.EntityClient;
  15     using System.Data.Metadata.Edm;
  16     using System.Data.Objects.Internal;
  17     using System.Diagnostics;
  18     using System.Threading;
  19     using System.Data.Common.Internal.Materialization;
  20
  21     /// <summary>
  22     /// Provides Query Execution Plan Caching Service
  23     /// </summary>
  24     /// <remarks>
  25     /// Thread safe.
  26     /// Dispose <b>must</b> be called as there is no finalizer for this class
  27     /// </remarks>
  28     internal class QueryCacheManager : IDisposable
  29     {
  30         #region Constants/Default values for configuration parameters
  31
  32         /// <summary>
  33         /// Default Soft maximum number of entries in the cache
  34         /// Default value: 1000
  35         /// </summary>
  36         const int DefaultMaxNumberOfEntries = 1000;
  37
  38         /// <summary>
  39         /// Default high mark for starting sweeping process
  40         /// default value: 80% of MaxNumberOfEntries
  41         /// </summary>
  42         const float DefaultHighMarkPercentageFactor = 0.8f; // 80% of MaxLimit
  43
  44         /// <summary>
  45         /// Recycler timer period
  46         /// </summary>
  47         const int DefaultRecyclerPeriodInMilliseconds = 60 * 1000;
  48
  49         #endregion
  50
  51         #region Fields
  52
  53         /// <summary>
  54         /// cache lock object
  55         /// </summary>
  56         private readonly object _cacheDataLock = new object();
  57
  58         /// <summary>
  59         /// cache data
  60         /// </summary>
  61         private readonly Dictionary<QueryCacheKey, QueryCacheEntry> _cacheData = new Dictionary<QueryCacheKey, QueryCacheEntry>(32);
  62
  63         /// <summary>
  64         /// soft maximum number of entries in the cache
  65         /// </summary>
  66         private readonly int _maxNumberOfEntries;
  67
  68         /// <summary>
  69         /// high mark of the number of entries to trigger the sweeping process
  70         /// </summary>
  71         private readonly int _sweepingTriggerHighMark;
  72
  73         /// <summary>
  74         /// Eviction timer
  75         /// </summary>
  76         private readonly EvictionTimer _evictionTimer;
  77
  78         #endregion
  79
  80         #region Construction and Initialization
  81
  82         /// <summary>
  83         /// Constructs a new Query Cache Manager instance, with default values for all 'configurable' parameters.
  84         /// </summary>
  85         /// <returns>A new instance of <see cref="QueryCacheManager"/> configured with default entry count, load factor and recycle period</returns>
  86         internal static QueryCacheManager Create()
  87         {
  88             return new QueryCacheManager(DefaultMaxNumberOfEntries, DefaultHighMarkPercentageFactor, DefaultRecyclerPeriodInMilliseconds);
  89         }
  90
  91         /// <summary>
  92         /// Cache Constructor
  93         /// </summary>
  94         /// <param name="maximumSize">
  95         ///   Maximum number of entries that the cache should contain.
  96         /// </param>
  97         /// <param name="loadFactor">
  98         ///   The number of entries that must be present, as a percentage, before entries should be removed
  99         ///   according to the eviction policy.
 100         ///   Must be greater than 0 and less than or equal to 1.0
 101         /// </param>
 102         /// <param name="recycleMillis">
 103         ///   The interval, in milliseconds, at which the number of entries will be compared to the load factor
 104         ///   and eviction carried out if necessary.
 105         /// </param>
 106         private QueryCacheManager(int maximumSize, float loadFactor, int recycleMillis)
 107         {
 108             Debug.Assert(maximumSize > 0, "Maximum size must be greater than zero");
 109             Debug.Assert(loadFactor > 0 && loadFactor <= 1, "Load factor must be greater than 0.0 and less than or equal to 1.0");
 110             Debug.Assert(recycleMillis >= 0, "Recycle period in milliseconds must not be negative");
 111
 112             //
 113             // Load hardcoded defaults
 114             //
 115             this._maxNumberOfEntries = maximumSize;
 116
 117             //
 118             // set sweeping high mark trigger value
 119             //
 120             this._sweepingTriggerHighMark = (int)(_maxNumberOfEntries * loadFactor);
 121
 122             //
 123             // Initialize Recycler
 124             //
 125             this._evictionTimer = new EvictionTimer(this, recycleMillis);
 126         }
 127
 128         #endregion
 129
 130         #region 'External' interface
 131         /// <summary>
 132         /// Adds new entry to the cache using "abstract" cache context and
 133         /// value; returns an existing entry if the key is already in the
 134         /// dictionary.
 135         /// </summary>
 136         /// <param name="inQueryCacheEntry"></param>
 137         /// <param name="outQueryCacheEntry">
 138         /// The existing entry in the dicitionary if already there;
 139         /// inQueryCacheEntry if none was found and inQueryCacheEntry
 140         /// was added instead.
 141         /// </param>
 142         /// <returns>true if the output entry was already found; false if it had to be added.</returns>
 143         internal bool TryLookupAndAdd(QueryCacheEntry inQueryCacheEntry, out QueryCacheEntry outQueryCacheEntry)
 144         {
 145             Debug.Assert(null != inQueryCacheEntry, "qEntry must not be null");
 146
 147             outQueryCacheEntry = null;
 148
 149             lock (_cacheDataLock)
 150             {
 151                 if (!_cacheData.TryGetValue(inQueryCacheEntry.QueryCacheKey, out outQueryCacheEntry))
 152                 {
 153                     //
 154                     // add entry to cache data
 155                     //
 156                     _cacheData.Add(inQueryCacheEntry.QueryCacheKey, inQueryCacheEntry);
 157                     if (_cacheData.Count > _sweepingTriggerHighMark)
 158                     {
 159                         _evictionTimer.Start();
 160                     }
 161
 162                     return false;
 163                 }
 164                 else
 165                 {
 166                     outQueryCacheEntry.QueryCacheKey.UpdateHit();
 167
 168                     return true;
 169                 }
 170             }
 171         }
 172
 173         /// <summary>
 174         /// Lookup service for a cached value.
 175         /// </summary>
 176         internal bool TryCacheLookup<TK, TE>(TK key, out TE value)
 177             where TK : QueryCacheKey
 178         {
 179             Debug.Assert(null != key, "key must not be null");
 180
 181             value = default(TE);
 182
 183             //
 184             // invoke internal lookup
 185             //
 186             QueryCacheEntry qEntry = null;
 187             bool bHit = TryInternalCacheLookup(key, out qEntry);
 188
 189             //
 190             // if it is a hit, 'extract' the entry strong type cache value
 191             //
 192             if (bHit)
 193             {
 194                 value = (TE)qEntry.GetTarget();
 195             }
 196
 197             return bHit;
 198         }
 199
 200         /// <summary>
 201         /// Clears the Cache
 202         /// </summary>
 203         internal void Clear()
 204         {
 205             lock (_cacheDataLock)
 206             {
 207                 _cacheData.Clear();
 208             }
 209         }
 210         #endregion
 211
 212         #region Private Members
 213
 214         /// <summary>
 215         /// lookup service
 216         /// </summary>
 217         /// <param name="queryCacheKey"></param>
 218         /// <param name="queryCacheEntry"></param>
 219         /// <returns>true if cache hit, false if cache miss</returns>
 220         private bool TryInternalCacheLookup( QueryCacheKey queryCacheKey, out QueryCacheEntry queryCacheEntry )
 221         {
 222             Debug.Assert(null != queryCacheKey, "queryCacheKey must not be null");
 223
 224             queryCacheEntry = null;
 225
 226             bool bHit = false;
 227
 228             //
 229             // lock the cache for the minimal possible period
 230             //
 231             lock (_cacheDataLock)
 232             {
 233                 bHit = _cacheData.TryGetValue(queryCacheKey, out queryCacheEntry);
 234             }
 235
 236             //
 237             // if cache hit
 238             //
 239             if (bHit)
 240             {
 241                 //
 242                 // update hit mark in cache key
 243                 //
 244                 queryCacheEntry.QueryCacheKey.UpdateHit();
 245             }
 246
 247             return bHit;
 248         }
 249
 250
 251         /// <summary>
 252         /// Recycler handler. This method is called directly by the eviction timer.
 253         /// It should take no action beyond invoking the <see cref="SweepCache"/> method on the
 254         /// cache manager instance passed as <paramref name="state"/>.
 255         /// </summary>
 256         /// <param name="state">The cache manager instance on which the 'recycle' handler should be invoked</param>
 257         private static void CacheRecyclerHandler(object state)
 258         {
 259             ((QueryCacheManager)state).SweepCache();
 260         }
 261
 262         /// <summary>
 263         /// Aging factor
 264         /// </summary>
 265         private static readonly int[] _agingFactor = {1,1,2,4,8,16};
 266         private static readonly int AgingMaxIndex = _agingFactor.Length - 1;
 267
 268         /// <summary>
 269         /// Sweeps the cache removing old unused entries.
 270         /// This method implements the query cache eviction policy.
 271         /// </summary>
 272         private void SweepCache()
 273         {
 274             if (!this._evictionTimer.Suspend())
 275             {
 276                 // Return of false from .Suspend means that the manager and timer have been disposed.
 277                 return;
 278             }
 279
 280             bool disabledEviction = false;
 281             lock (_cacheDataLock)
 282             {
 283                 //
 284                 // recycle only if entries exceeds the high mark factor
 285                 //
 286                 if (_cacheData.Count > _sweepingTriggerHighMark)
 287                 {
 288                     //
 289                     // sweep the cache
 290                     //
 291                     uint evictedEntriesCount = 0;
 292                     List<QueryCacheKey> cacheKeys = new List<QueryCacheKey>(_cacheData.Count);
 293                     cacheKeys.AddRange(_cacheData.Keys);
 294                     for (int i = 0; i < cacheKeys.Count; i++)
 295                     {
 296                         //
 297                         // if entry was not used in the last time window, then evict the entry
 298                         //
 299                         if (0 == cacheKeys[i].HitCount)
 300                         {
 301                             _cacheData.Remove(cacheKeys[i]);
 302                             evictedEntriesCount++;
 303                         }
 304                         //
 305                         // otherwise, age the entry in a progressive scheme
 306                         //
 307                         else
 308                         {
 309                             int agingIndex = unchecked(cacheKeys[i].AgingIndex + 1);
 310                             if (agingIndex > AgingMaxIndex)
 311                             {
 312                                 agingIndex = AgingMaxIndex;
 313                             }
 314                             cacheKeys[i].AgingIndex = agingIndex;
 315                             cacheKeys[i].HitCount = cacheKeys[i].HitCount >> _agingFactor[agingIndex];
 316                         }
 317                     }
 318                 }
 319                 else
 320                 {
 321                     _evictionTimer.Stop();
 322                     disabledEviction = true;
 323                 }
 324             }
 325
 326             if (!disabledEviction)
 327             {
 328                 this._evictionTimer.Resume();
 329             }
 330         }
 331
 332         #endregion
 333
 334         #region IDisposable Members
 335
 336         /// <summary>
 337         /// Dispose instance
 338         /// </summary>
 339         /// <remarks>Dispose <b>must</b> be called as there are no finalizers for this class</remarks>
 340         public void Dispose()
 341         {
 342             // Technically, calling GC.SuppressFinalize is not required because the class does not
 343             // have a finalizer, but it does no harm, protects against the case where a finalizer is added
 344             // in the future, and prevents an FxCop warning.
 345             GC.SuppressFinalize(this);
 346             if (this._evictionTimer.Stop())
 347             {
 348                 this.Clear();
 349             }
 350         }
 351
 352         #endregion
 353
 354         /// <summary>
 355         /// Periodically invokes cache cleanup logic on a specified <see cref="QueryCacheManager"/> instance,
 356         /// and allows this periodic callback to be suspended, resumed or stopped in a thread-safe way.
 357         /// </summary>
 358         private sealed class EvictionTimer
 359         {
 360             /// <summary>Used to control multi-threaded accesses to this instance</summary>
 361             private readonly object _sync = new object();
 362
 363             /// <summary>The required interval between invocations of the cache cleanup logic</summary>
 364             private readonly int _period;
 365
 366             /// <summary>The underlying QueryCacheManger that the callback will act on</summary>
 367             private readonly QueryCacheManager _cacheManager;
 368
 369             /// <summary>The underlying <see cref="Timer"/> that implements the periodic callback</summary>
 370             private Timer _timer;
 371
 372             internal EvictionTimer(QueryCacheManager cacheManager, int recyclePeriod)
 373             {
 374                 this._cacheManager = cacheManager;
 375                 this._period = recyclePeriod;
 376             }
 377
 378             internal void Start()
 379             {
 380                 lock (_sync)
 381                 {
 382                     if (_timer == null)
 383                     {
 384                         this._timer = new Timer(QueryCacheManager.CacheRecyclerHandler, _cacheManager, _period, _period);
 385                     }
 386                 }
 387             }
 388
 389             /// <summary>
 390             /// Permanently stops the eviction timer.
 391             /// It will no longer generate periodic callbacks and further calls to <see cref="Suspend"/>, <see cref="Resume"/>, or <see cref="Stop"/>,
 392             /// though thread-safe, will have no effect.
 393             /// </summary>
 394             /// <returns>
 395             ///   If this eviction timer has already been stopped (using the <see cref="Stop"/> method), returns <c>false</c>;
 396             ///   otherwise, returns <c>true</c> to indicate that the call successfully stopped and cleaned up the underlying timer instance.
 397             /// </returns>
 398             /// <remarks>
 399             ///   Thread safe. May be called regardless of the current state of the eviction timer.
 400             ///   Once stopped, an eviction timer cannot be restarted with the <see cref="Resume"/> method.
 401             /// </remarks>
 402             internal bool Stop()
 403             {
 404                 lock (_sync)
 405                 {
 406                     if (this._timer != null)
 407                     {
 408                         this._timer.Dispose();
 409                         this._timer = null;
 410                         return true;
 411                     }
 412                     else
 413                     {
 414                         return false;
 415                     }
 416                 }
 417             }
 418
 419             /// <summary>
 420             /// Pauses the operation of the eviction timer.
 421             /// </summary>
 422             /// <returns>
 423             ///   If this eviction timer has already been stopped (using the <see cref="Stop"/> method), returns <c>false</c>;
 424             ///   otherwise, returns <c>true</c> to indicate that the call successfully suspended the inderlying <see cref="Timer"/>
 425             ///   and no further periodic callbacks will be generated until the <see cref="Resume"/> method is called.
 426             /// </returns>
 427             /// <remarks>
 428             ///   Thread-safe. May be called regardless of the current state of the eviction timer.
 429             ///   Once suspended, an eviction timer may be resumed or stopped.
 430             /// </remarks>
 431             internal bool Suspend()
 432             {
 433                 lock (_sync)
 434                 {
 435                     if (this._timer != null)
 436                     {
 437                         this._timer.Change(Timeout.Infinite, Timeout.Infinite);
 438                         return true;
 439                     }
 440                     else
 441                     {
 442                         return false;
 443                     }
 444                 }
 445             }
 446
 447             /// <summary>
 448             /// Causes this eviction timer to generate periodic callbacks, provided it has not been permanently stopped (using the <see cref="Stop"/> method).
 449             /// </summary>
 450             /// <remarks>
 451             ///   Thread-safe. May be called regardless of the current state of the eviction timer.
 452             /// </remarks>
 453             internal void Resume()
 454             {
 455                 lock (_sync)
 456                 {
 457                     if (this._timer != null)
 458                     {
 459                         this._timer.Change(this._period, this._period);
 460                     }
 461                 }
 462             }
 463         }
 464     }
 465 }