Cache.cs 15 KB

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