Cache.cs 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587
  1. /*
  2. * Copyright (c) Contributors, http://opensimulator.org/
  3. * See CONTRIBUTORS.TXT for a full list of copyright holders.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. * * Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * * Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. * * Neither the name of the OpenSimulator Project nor the
  13. * names of its contributors may be used to endorse or promote products
  14. * derived from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
  17. * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19. * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
  20. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. using System;
  28. using System.Collections.Generic;
  29. using OpenMetaverse;
  30. namespace OpenSim.Framework
  31. {
  32. // The delegate we will use for performing fetch from backing store
  33. //
  34. public delegate Object FetchDelegate(string index);
  35. public delegate bool ExpireDelegate(string index);
  36. // Strategy
  37. //
  38. // Conservative = Minimize memory. Expire items quickly.
  39. // Balanced = Expire items with few hits quickly.
  40. // Aggressive = Keep cache full. Expire only when over 90% and adding
  41. //
  42. public enum CacheStrategy
  43. {
  44. Conservative = 0,
  45. Balanced = 1,
  46. Aggressive = 2
  47. }
  48. // Select classes to store data on different media
  49. //
  50. public enum CacheMedium
  51. {
  52. Memory = 0,
  53. File = 1
  54. }
  55. public enum CacheFlags
  56. {
  57. CacheMissing = 1,
  58. AllowUpdate = 2
  59. }
  60. // The base class of all cache objects. Implements comparison and sorting
  61. // by the string member.
  62. //
  63. // This is not abstract because we need to instantiate it briefly as a
  64. // method parameter
  65. //
  66. public class CacheItemBase : IEquatable<CacheItemBase>, IComparable<CacheItemBase>
  67. {
  68. public string uuid;
  69. public DateTime entered;
  70. public DateTime lastUsed;
  71. public DateTime expires = new DateTime(0);
  72. public int hits = 0;
  73. public virtual Object Retrieve()
  74. {
  75. return null;
  76. }
  77. public virtual void Store(Object data)
  78. {
  79. }
  80. public CacheItemBase(string index)
  81. {
  82. uuid = index;
  83. entered = DateTime.UtcNow;
  84. lastUsed = entered;
  85. }
  86. public CacheItemBase(string index, DateTime ttl)
  87. {
  88. uuid = index;
  89. entered = DateTime.UtcNow;
  90. lastUsed = entered;
  91. expires = ttl;
  92. }
  93. public virtual bool Equals(CacheItemBase item)
  94. {
  95. return uuid == item.uuid;
  96. }
  97. public virtual int CompareTo(CacheItemBase item)
  98. {
  99. return uuid.CompareTo(item.uuid);
  100. }
  101. public virtual bool IsLocked()
  102. {
  103. return false;
  104. }
  105. }
  106. // Simple in-memory storage. Boxes the object and stores it in a variable
  107. //
  108. public class MemoryCacheItem : CacheItemBase
  109. {
  110. private Object m_Data;
  111. public MemoryCacheItem(string index) :
  112. base(index)
  113. {
  114. }
  115. public MemoryCacheItem(string index, DateTime ttl) :
  116. base(index, ttl)
  117. {
  118. }
  119. public MemoryCacheItem(string index, Object data) :
  120. base(index)
  121. {
  122. Store(data);
  123. }
  124. public MemoryCacheItem(string index, DateTime ttl, Object data) :
  125. base(index, ttl)
  126. {
  127. Store(data);
  128. }
  129. public override Object Retrieve()
  130. {
  131. return m_Data;
  132. }
  133. public override void Store(Object data)
  134. {
  135. m_Data = data;
  136. }
  137. }
  138. // Simple persistent file storage
  139. //
  140. public class FileCacheItem : CacheItemBase
  141. {
  142. public FileCacheItem(string index) :
  143. base(index)
  144. {
  145. }
  146. public FileCacheItem(string index, DateTime ttl) :
  147. base(index, ttl)
  148. {
  149. }
  150. public FileCacheItem(string index, Object data) :
  151. base(index)
  152. {
  153. Store(data);
  154. }
  155. public FileCacheItem(string index, DateTime ttl, Object data) :
  156. base(index, ttl)
  157. {
  158. Store(data);
  159. }
  160. public override Object Retrieve()
  161. {
  162. //TODO: Add file access code
  163. return null;
  164. }
  165. public override void Store(Object data)
  166. {
  167. //TODO: Add file access code
  168. }
  169. }
  170. // The main cache class. This is the class you instantiate to create
  171. // a cache
  172. //
  173. public class Cache
  174. {
  175. /// <summary>
  176. /// Must only be accessed under lock.
  177. /// </summary>
  178. private List<CacheItemBase> m_Index = new List<CacheItemBase>();
  179. /// <summary>
  180. /// Must only be accessed under m_Index lock.
  181. /// </summary>
  182. private Dictionary<string, CacheItemBase> m_Lookup =
  183. new Dictionary<string, CacheItemBase>();
  184. private CacheStrategy m_Strategy;
  185. private CacheMedium m_Medium;
  186. private CacheFlags m_Flags = 0;
  187. private int m_Size = 1024;
  188. private TimeSpan m_DefaultTTL = new TimeSpan(0);
  189. private DateTime m_nextExpire;
  190. private TimeSpan m_expiresTime = new TimeSpan(0,0,30);
  191. public ExpireDelegate OnExpire;
  192. // Comparison interfaces
  193. //
  194. private class SortLRU : IComparer<CacheItemBase>
  195. {
  196. public int Compare(CacheItemBase a, CacheItemBase b)
  197. {
  198. if (a == null && b == null)
  199. return 0;
  200. if (a == null)
  201. return -1;
  202. if (b == null)
  203. return 1;
  204. return(a.lastUsed.CompareTo(b.lastUsed));
  205. }
  206. }
  207. // same as above, reverse order
  208. private class SortLRUrev : IComparer<CacheItemBase>
  209. {
  210. public int Compare(CacheItemBase a, CacheItemBase b)
  211. {
  212. if (a == null && b == null)
  213. return 0;
  214. if (a == null)
  215. return -1;
  216. if (b == null)
  217. return 1;
  218. return(b.lastUsed.CompareTo(a.lastUsed));
  219. }
  220. }
  221. // Convenience constructors
  222. //
  223. public Cache()
  224. {
  225. m_Strategy = CacheStrategy.Balanced;
  226. m_Medium = CacheMedium.Memory;
  227. m_Flags = 0;
  228. m_nextExpire = DateTime.UtcNow + m_expiresTime;
  229. m_Strategy = CacheStrategy.Aggressive;
  230. }
  231. public Cache(CacheMedium medium) :
  232. this(medium, CacheStrategy.Balanced)
  233. {
  234. }
  235. public Cache(CacheMedium medium, CacheFlags flags) :
  236. this(medium, CacheStrategy.Balanced, flags)
  237. {
  238. }
  239. public Cache(CacheMedium medium, CacheStrategy strategy) :
  240. this(medium, strategy, 0)
  241. {
  242. }
  243. public Cache(CacheStrategy strategy, CacheFlags flags) :
  244. this(CacheMedium.Memory, strategy, flags)
  245. {
  246. }
  247. public Cache(CacheFlags flags) :
  248. this(CacheMedium.Memory, CacheStrategy.Balanced, flags)
  249. {
  250. }
  251. public Cache(CacheMedium medium, CacheStrategy strategy,
  252. CacheFlags flags)
  253. {
  254. m_Strategy = strategy;
  255. m_Medium = medium;
  256. m_Flags = flags;
  257. }
  258. // Count of the items currently in cache
  259. //
  260. public int Count
  261. {
  262. get { lock (m_Index) { return m_Index.Count; } }
  263. }
  264. // Maximum number of items this cache will hold
  265. //
  266. public int Size
  267. {
  268. get { return m_Size; }
  269. set { SetSize(value); }
  270. }
  271. private void SetSize(int newSize)
  272. {
  273. lock (m_Index)
  274. {
  275. int target = newSize;
  276. if(m_Strategy == CacheStrategy.Aggressive)
  277. target = (int)(newSize * 0.9);
  278. if(Count > target)
  279. {
  280. m_Index.Sort(new SortLRUrev());
  281. m_Index.RemoveRange(newSize, Count - target);
  282. m_Lookup.Clear();
  283. foreach (CacheItemBase item in m_Index)
  284. m_Lookup[item.uuid] = item;
  285. }
  286. m_Size = newSize;
  287. }
  288. }
  289. public TimeSpan DefaultTTL
  290. {
  291. get { return m_DefaultTTL; }
  292. set { m_DefaultTTL = value; }
  293. }
  294. // Get an item from cache. Return the raw item, not it's data
  295. //
  296. protected virtual CacheItemBase GetItem(string index)
  297. {
  298. CacheItemBase item = null;
  299. lock (m_Index)
  300. {
  301. if (m_Lookup.ContainsKey(index))
  302. item = m_Lookup[index];
  303. if (item == null)
  304. {
  305. Expire(true);
  306. return null;
  307. }
  308. item.hits++;
  309. item.lastUsed = DateTime.UtcNow;
  310. Expire(true);
  311. }
  312. return item;
  313. }
  314. // Get an item from cache. Do not try to fetch from source if not
  315. // present. Just return null
  316. //
  317. public virtual Object Get(string index)
  318. {
  319. CacheItemBase item = GetItem(index);
  320. if (item == null)
  321. return null;
  322. return item.Retrieve();
  323. }
  324. // Fetch an object from backing store if not cached, serve from
  325. // cache if it is.
  326. //
  327. public virtual Object Get(string index, FetchDelegate fetch)
  328. {
  329. CacheItemBase item = GetItem(index);
  330. if (item != null)
  331. return item.Retrieve();
  332. Object data = fetch(index);
  333. if (data == null)
  334. {
  335. if((m_Flags & CacheFlags.CacheMissing) != 0)
  336. {
  337. lock (m_Index)
  338. {
  339. CacheItemBase missing = new CacheItemBase(index);
  340. if (!m_Index.Contains(missing))
  341. {
  342. m_Index.Add(missing);
  343. m_Lookup[index] = missing;
  344. }
  345. }
  346. }
  347. return null;
  348. }
  349. Store(index, data);
  350. return data;
  351. }
  352. // Find an object in cache by delegate.
  353. //
  354. public Object Find(Predicate<CacheItemBase> d)
  355. {
  356. CacheItemBase item;
  357. lock (m_Index)
  358. item = m_Index.Find(d);
  359. if (item == null)
  360. return null;
  361. return item.Retrieve();
  362. }
  363. public virtual void Store(string index, Object data)
  364. {
  365. Type container;
  366. switch (m_Medium)
  367. {
  368. case CacheMedium.Memory:
  369. container = typeof(MemoryCacheItem);
  370. break;
  371. case CacheMedium.File:
  372. return;
  373. default:
  374. return;
  375. }
  376. Store(index, data, container);
  377. }
  378. public virtual void Store(string index, Object data, Type container)
  379. {
  380. Store(index, data, container, new Object[] { index });
  381. }
  382. public virtual void Store(string index, Object data, Type container,
  383. Object[] parameters)
  384. {
  385. CacheItemBase item;
  386. lock (m_Index)
  387. {
  388. Expire(false);
  389. if (m_Index.Contains(new CacheItemBase(index)))
  390. {
  391. if ((m_Flags & CacheFlags.AllowUpdate) != 0)
  392. {
  393. item = GetItem(index);
  394. item.hits++;
  395. item.lastUsed = DateTime.UtcNow;
  396. if (m_DefaultTTL.Ticks != 0)
  397. item.expires = DateTime.UtcNow + m_DefaultTTL;
  398. item.Store(data);
  399. }
  400. return;
  401. }
  402. item = (CacheItemBase)Activator.CreateInstance(container,
  403. parameters);
  404. if (m_DefaultTTL.Ticks != 0)
  405. item.expires = DateTime.UtcNow + m_DefaultTTL;
  406. m_Index.Add(item);
  407. m_Lookup[index] = item;
  408. }
  409. item.Store(data);
  410. }
  411. /// <summary>
  412. /// Expire items as appropriate.
  413. /// </summary>
  414. /// <remarks>
  415. /// Callers must lock m_Index.
  416. /// </remarks>
  417. /// <param name='getting'></param>
  418. protected virtual void Expire(bool getting)
  419. {
  420. if (getting && (m_Strategy == CacheStrategy.Aggressive))
  421. return;
  422. DateTime now = DateTime.UtcNow;
  423. if(now < m_nextExpire)
  424. return;
  425. m_nextExpire = now + m_expiresTime;
  426. if (m_DefaultTTL.Ticks != 0)
  427. {
  428. foreach (CacheItemBase item in new List<CacheItemBase>(m_Index))
  429. {
  430. if (item.expires.Ticks == 0 ||
  431. item.expires <= now)
  432. {
  433. m_Index.Remove(item);
  434. m_Lookup.Remove(item.uuid);
  435. }
  436. }
  437. }
  438. switch (m_Strategy)
  439. {
  440. case CacheStrategy.Aggressive:
  441. int target = (int)((float)Size * 0.9);
  442. if (Count < target) // Cover ridiculous cache sizes
  443. return;
  444. target = (int)((float)Size * 0.8);
  445. m_Index.Sort(new SortLRUrev());
  446. ExpireDelegate doExpire = OnExpire;
  447. if (doExpire != null)
  448. {
  449. List<CacheItemBase> candidates =
  450. m_Index.GetRange(target, Count - target);
  451. foreach (CacheItemBase i in candidates)
  452. {
  453. if (doExpire(i.uuid))
  454. {
  455. m_Index.Remove(i);
  456. m_Lookup.Remove(i.uuid);
  457. }
  458. }
  459. }
  460. else
  461. {
  462. m_Index.RemoveRange(target, Count - target);
  463. m_Lookup.Clear();
  464. foreach (CacheItemBase item in m_Index)
  465. m_Lookup[item.uuid] = item;
  466. }
  467. break;
  468. default:
  469. break;
  470. }
  471. }
  472. public void Invalidate(string uuid)
  473. {
  474. lock (m_Index)
  475. {
  476. if (!m_Lookup.ContainsKey(uuid))
  477. return;
  478. CacheItemBase item = m_Lookup[uuid];
  479. m_Lookup.Remove(uuid);
  480. m_Index.Remove(item);
  481. }
  482. }
  483. public void Clear()
  484. {
  485. lock (m_Index)
  486. {
  487. m_Index.Clear();
  488. m_Lookup.Clear();
  489. }
  490. }
  491. }
  492. }