1
0

Cache.cs 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562
  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.Now;
  84. lastUsed = entered;
  85. }
  86. public CacheItemBase(string index, DateTime ttl)
  87. {
  88. uuid = index;
  89. entered = DateTime.Now;
  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. public ExpireDelegate OnExpire;
  190. // Comparison interfaces
  191. //
  192. private class SortLRU : IComparer<CacheItemBase>
  193. {
  194. public int Compare(CacheItemBase a, CacheItemBase b)
  195. {
  196. if (a == null && b == null)
  197. return 0;
  198. if (a == null)
  199. return -1;
  200. if (b == null)
  201. return 1;
  202. return(a.lastUsed.CompareTo(b.lastUsed));
  203. }
  204. }
  205. // Convenience constructors
  206. //
  207. public Cache()
  208. {
  209. m_Strategy = CacheStrategy.Balanced;
  210. m_Medium = CacheMedium.Memory;
  211. m_Flags = 0;
  212. }
  213. public Cache(CacheMedium medium) :
  214. this(medium, CacheStrategy.Balanced)
  215. {
  216. }
  217. public Cache(CacheMedium medium, CacheFlags flags) :
  218. this(medium, CacheStrategy.Balanced, flags)
  219. {
  220. }
  221. public Cache(CacheMedium medium, CacheStrategy strategy) :
  222. this(medium, strategy, 0)
  223. {
  224. }
  225. public Cache(CacheStrategy strategy, CacheFlags flags) :
  226. this(CacheMedium.Memory, strategy, flags)
  227. {
  228. }
  229. public Cache(CacheFlags flags) :
  230. this(CacheMedium.Memory, CacheStrategy.Balanced, flags)
  231. {
  232. }
  233. public Cache(CacheMedium medium, CacheStrategy strategy,
  234. CacheFlags flags)
  235. {
  236. m_Strategy = strategy;
  237. m_Medium = medium;
  238. m_Flags = flags;
  239. }
  240. // Count of the items currently in cache
  241. //
  242. public int Count
  243. {
  244. get { lock (m_Index) { return m_Index.Count; } }
  245. }
  246. // Maximum number of items this cache will hold
  247. //
  248. public int Size
  249. {
  250. get { return m_Size; }
  251. set { SetSize(value); }
  252. }
  253. private void SetSize(int newSize)
  254. {
  255. lock (m_Index)
  256. {
  257. if (Count <= Size)
  258. return;
  259. m_Index.Sort(new SortLRU());
  260. m_Index.Reverse();
  261. m_Index.RemoveRange(newSize, Count - newSize);
  262. m_Size = newSize;
  263. m_Lookup.Clear();
  264. foreach (CacheItemBase item in m_Index)
  265. m_Lookup[item.uuid] = item;
  266. }
  267. }
  268. public TimeSpan DefaultTTL
  269. {
  270. get { return m_DefaultTTL; }
  271. set { m_DefaultTTL = value; }
  272. }
  273. // Get an item from cache. Return the raw item, not it's data
  274. //
  275. protected virtual CacheItemBase GetItem(string index)
  276. {
  277. CacheItemBase item = null;
  278. lock (m_Index)
  279. {
  280. if (m_Lookup.ContainsKey(index))
  281. item = m_Lookup[index];
  282. if (item == null)
  283. {
  284. Expire(true);
  285. return null;
  286. }
  287. item.hits++;
  288. item.lastUsed = DateTime.Now;
  289. Expire(true);
  290. }
  291. return item;
  292. }
  293. // Get an item from cache. Do not try to fetch from source if not
  294. // present. Just return null
  295. //
  296. public virtual Object Get(string index)
  297. {
  298. CacheItemBase item = GetItem(index);
  299. if (item == null)
  300. return null;
  301. return item.Retrieve();
  302. }
  303. // Fetch an object from backing store if not cached, serve from
  304. // cache if it is.
  305. //
  306. public virtual Object Get(string index, FetchDelegate fetch)
  307. {
  308. Object item = Get(index);
  309. if (item != null)
  310. return item;
  311. Object data = fetch(index);
  312. if (data == null)
  313. {
  314. if ((m_Flags & CacheFlags.CacheMissing) != 0)
  315. {
  316. lock (m_Index)
  317. {
  318. CacheItemBase missing = new CacheItemBase(index);
  319. if (!m_Index.Contains(missing))
  320. {
  321. m_Index.Add(missing);
  322. m_Lookup[index] = missing;
  323. }
  324. }
  325. }
  326. return null;
  327. }
  328. Store(index, data);
  329. return data;
  330. }
  331. // Find an object in cache by delegate.
  332. //
  333. public Object Find(Predicate<CacheItemBase> d)
  334. {
  335. CacheItemBase item;
  336. lock (m_Index)
  337. item = m_Index.Find(d);
  338. if (item == null)
  339. return null;
  340. return item.Retrieve();
  341. }
  342. public virtual void Store(string index, Object data)
  343. {
  344. Type container;
  345. switch (m_Medium)
  346. {
  347. case CacheMedium.Memory:
  348. container = typeof(MemoryCacheItem);
  349. break;
  350. case CacheMedium.File:
  351. return;
  352. default:
  353. return;
  354. }
  355. Store(index, data, container);
  356. }
  357. public virtual void Store(string index, Object data, Type container)
  358. {
  359. Store(index, data, container, new Object[] { index });
  360. }
  361. public virtual void Store(string index, Object data, Type container,
  362. Object[] parameters)
  363. {
  364. CacheItemBase item;
  365. lock (m_Index)
  366. {
  367. Expire(false);
  368. if (m_Index.Contains(new CacheItemBase(index)))
  369. {
  370. if ((m_Flags & CacheFlags.AllowUpdate) != 0)
  371. {
  372. item = GetItem(index);
  373. item.hits++;
  374. item.lastUsed = DateTime.Now;
  375. if (m_DefaultTTL.Ticks != 0)
  376. item.expires = DateTime.Now + m_DefaultTTL;
  377. item.Store(data);
  378. }
  379. return;
  380. }
  381. item = (CacheItemBase)Activator.CreateInstance(container,
  382. parameters);
  383. if (m_DefaultTTL.Ticks != 0)
  384. item.expires = DateTime.Now + m_DefaultTTL;
  385. m_Index.Add(item);
  386. m_Lookup[index] = item;
  387. }
  388. item.Store(data);
  389. }
  390. /// <summary>
  391. /// Expire items as appropriate.
  392. /// </summary>
  393. /// <remarks>
  394. /// Callers must lock m_Index.
  395. /// </remarks>
  396. /// <param name='getting'></param>
  397. protected virtual void Expire(bool getting)
  398. {
  399. if (getting && (m_Strategy == CacheStrategy.Aggressive))
  400. return;
  401. if (m_DefaultTTL.Ticks != 0)
  402. {
  403. DateTime now= DateTime.Now;
  404. foreach (CacheItemBase item in new List<CacheItemBase>(m_Index))
  405. {
  406. if (item.expires.Ticks == 0 ||
  407. item.expires <= now)
  408. {
  409. m_Index.Remove(item);
  410. m_Lookup.Remove(item.uuid);
  411. }
  412. }
  413. }
  414. switch (m_Strategy)
  415. {
  416. case CacheStrategy.Aggressive:
  417. if (Count < Size)
  418. return;
  419. m_Index.Sort(new SortLRU());
  420. m_Index.Reverse();
  421. int target = (int)((float)Size * 0.9);
  422. if (target == Count) // Cover ridiculous cache sizes
  423. return;
  424. ExpireDelegate doExpire = OnExpire;
  425. if (doExpire != null)
  426. {
  427. List<CacheItemBase> candidates =
  428. m_Index.GetRange(target, Count - target);
  429. foreach (CacheItemBase i in candidates)
  430. {
  431. if (doExpire(i.uuid))
  432. {
  433. m_Index.Remove(i);
  434. m_Lookup.Remove(i.uuid);
  435. }
  436. }
  437. }
  438. else
  439. {
  440. m_Index.RemoveRange(target, Count - target);
  441. m_Lookup.Clear();
  442. foreach (CacheItemBase item in m_Index)
  443. m_Lookup[item.uuid] = item;
  444. }
  445. break;
  446. default:
  447. break;
  448. }
  449. }
  450. public void Invalidate(string uuid)
  451. {
  452. lock (m_Index)
  453. {
  454. if (!m_Lookup.ContainsKey(uuid))
  455. return;
  456. CacheItemBase item = m_Lookup[uuid];
  457. m_Lookup.Remove(uuid);
  458. m_Index.Remove(item);
  459. }
  460. }
  461. public void Clear()
  462. {
  463. lock (m_Index)
  464. {
  465. m_Index.Clear();
  466. m_Lookup.Clear();
  467. }
  468. }
  469. }
  470. }