opensim-development – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | eva | 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 | |||
28 | using System; |
||
29 | using System.Collections.Generic; |
||
30 | using OpenMetaverse; |
||
31 | |||
32 | namespace OpenSim.Framework |
||
33 | { |
||
34 | // The delegate we will use for performing fetch from backing store |
||
35 | // |
||
36 | public delegate Object FetchDelegate(string index); |
||
37 | public delegate bool ExpireDelegate(string index); |
||
38 | |||
39 | // Strategy |
||
40 | // |
||
41 | // Conservative = Minimize memory. Expire items quickly. |
||
42 | // Balanced = Expire items with few hits quickly. |
||
43 | // Aggressive = Keep cache full. Expire only when over 90% and adding |
||
44 | // |
||
45 | public enum CacheStrategy |
||
46 | { |
||
47 | Conservative = 0, |
||
48 | Balanced = 1, |
||
49 | Aggressive = 2 |
||
50 | } |
||
51 | |||
52 | // Select classes to store data on different media |
||
53 | // |
||
54 | public enum CacheMedium |
||
55 | { |
||
56 | Memory = 0, |
||
57 | File = 1 |
||
58 | } |
||
59 | |||
60 | public enum CacheFlags |
||
61 | { |
||
62 | CacheMissing = 1, |
||
63 | AllowUpdate = 2 |
||
64 | } |
||
65 | |||
66 | // The base class of all cache objects. Implements comparison and sorting |
||
67 | // by the string member. |
||
68 | // |
||
69 | // This is not abstract because we need to instantiate it briefly as a |
||
70 | // method parameter |
||
71 | // |
||
72 | public class CacheItemBase : IEquatable<CacheItemBase>, IComparable<CacheItemBase> |
||
73 | { |
||
74 | public string uuid; |
||
75 | public DateTime entered; |
||
76 | public DateTime lastUsed; |
||
77 | public DateTime expires = new DateTime(0); |
||
78 | public int hits = 0; |
||
79 | |||
80 | public virtual Object Retrieve() |
||
81 | { |
||
82 | return null; |
||
83 | } |
||
84 | |||
85 | public virtual void Store(Object data) |
||
86 | { |
||
87 | } |
||
88 | |||
89 | public CacheItemBase(string index) |
||
90 | { |
||
91 | uuid = index; |
||
92 | entered = DateTime.Now; |
||
93 | lastUsed = entered; |
||
94 | } |
||
95 | |||
96 | public CacheItemBase(string index, DateTime ttl) |
||
97 | { |
||
98 | uuid = index; |
||
99 | entered = DateTime.Now; |
||
100 | lastUsed = entered; |
||
101 | expires = ttl; |
||
102 | } |
||
103 | |||
104 | public virtual bool Equals(CacheItemBase item) |
||
105 | { |
||
106 | return uuid == item.uuid; |
||
107 | } |
||
108 | |||
109 | public virtual int CompareTo(CacheItemBase item) |
||
110 | { |
||
111 | return uuid.CompareTo(item.uuid); |
||
112 | } |
||
113 | |||
114 | public virtual bool IsLocked() |
||
115 | { |
||
116 | return false; |
||
117 | } |
||
118 | } |
||
119 | |||
120 | // Simple in-memory storage. Boxes the object and stores it in a variable |
||
121 | // |
||
122 | public class MemoryCacheItem : CacheItemBase |
||
123 | { |
||
124 | private Object m_Data; |
||
125 | |||
126 | public MemoryCacheItem(string index) : |
||
127 | base(index) |
||
128 | { |
||
129 | } |
||
130 | |||
131 | public MemoryCacheItem(string index, DateTime ttl) : |
||
132 | base(index, ttl) |
||
133 | { |
||
134 | } |
||
135 | |||
136 | public MemoryCacheItem(string index, Object data) : |
||
137 | base(index) |
||
138 | { |
||
139 | Store(data); |
||
140 | } |
||
141 | |||
142 | public MemoryCacheItem(string index, DateTime ttl, Object data) : |
||
143 | base(index, ttl) |
||
144 | { |
||
145 | Store(data); |
||
146 | } |
||
147 | |||
148 | public override Object Retrieve() |
||
149 | { |
||
150 | return m_Data; |
||
151 | } |
||
152 | |||
153 | public override void Store(Object data) |
||
154 | { |
||
155 | m_Data = data; |
||
156 | } |
||
157 | } |
||
158 | |||
159 | // Simple persistent file storage |
||
160 | // |
||
161 | public class FileCacheItem : CacheItemBase |
||
162 | { |
||
163 | public FileCacheItem(string index) : |
||
164 | base(index) |
||
165 | { |
||
166 | } |
||
167 | |||
168 | public FileCacheItem(string index, DateTime ttl) : |
||
169 | base(index, ttl) |
||
170 | { |
||
171 | } |
||
172 | |||
173 | public FileCacheItem(string index, Object data) : |
||
174 | base(index) |
||
175 | { |
||
176 | Store(data); |
||
177 | } |
||
178 | |||
179 | public FileCacheItem(string index, DateTime ttl, Object data) : |
||
180 | base(index, ttl) |
||
181 | { |
||
182 | Store(data); |
||
183 | } |
||
184 | |||
185 | public override Object Retrieve() |
||
186 | { |
||
187 | //TODO: Add file access code |
||
188 | return null; |
||
189 | } |
||
190 | |||
191 | public override void Store(Object data) |
||
192 | { |
||
193 | //TODO: Add file access code |
||
194 | } |
||
195 | } |
||
196 | |||
197 | // The main cache class. This is the class you instantiate to create |
||
198 | // a cache |
||
199 | // |
||
200 | public class Cache |
||
201 | { |
||
202 | /// <summary> |
||
203 | /// Must only be accessed under lock. |
||
204 | /// </summary> |
||
205 | private List<CacheItemBase> m_Index = new List<CacheItemBase>(); |
||
206 | |||
207 | /// <summary> |
||
208 | /// Must only be accessed under m_Index lock. |
||
209 | /// </summary> |
||
210 | private Dictionary<string, CacheItemBase> m_Lookup = |
||
211 | new Dictionary<string, CacheItemBase>(); |
||
212 | |||
213 | private CacheStrategy m_Strategy; |
||
214 | private CacheMedium m_Medium; |
||
215 | private CacheFlags m_Flags = 0; |
||
216 | private int m_Size = 1024; |
||
217 | private TimeSpan m_DefaultTTL = new TimeSpan(0); |
||
218 | public ExpireDelegate OnExpire; |
||
219 | |||
220 | // Comparison interfaces |
||
221 | // |
||
222 | private class SortLRU : IComparer<CacheItemBase> |
||
223 | { |
||
224 | public int Compare(CacheItemBase a, CacheItemBase b) |
||
225 | { |
||
226 | if (a == null && b == null) |
||
227 | return 0; |
||
228 | if (a == null) |
||
229 | return -1; |
||
230 | if (b == null) |
||
231 | return 1; |
||
232 | |||
233 | return(a.lastUsed.CompareTo(b.lastUsed)); |
||
234 | } |
||
235 | } |
||
236 | |||
237 | // Convenience constructors |
||
238 | // |
||
239 | public Cache() |
||
240 | { |
||
241 | m_Strategy = CacheStrategy.Balanced; |
||
242 | m_Medium = CacheMedium.Memory; |
||
243 | m_Flags = 0; |
||
244 | } |
||
245 | |||
246 | public Cache(CacheMedium medium) : |
||
247 | this(medium, CacheStrategy.Balanced) |
||
248 | { |
||
249 | } |
||
250 | |||
251 | public Cache(CacheMedium medium, CacheFlags flags) : |
||
252 | this(medium, CacheStrategy.Balanced, flags) |
||
253 | { |
||
254 | } |
||
255 | |||
256 | public Cache(CacheMedium medium, CacheStrategy strategy) : |
||
257 | this(medium, strategy, 0) |
||
258 | { |
||
259 | } |
||
260 | |||
261 | public Cache(CacheStrategy strategy, CacheFlags flags) : |
||
262 | this(CacheMedium.Memory, strategy, flags) |
||
263 | { |
||
264 | } |
||
265 | |||
266 | public Cache(CacheFlags flags) : |
||
267 | this(CacheMedium.Memory, CacheStrategy.Balanced, flags) |
||
268 | { |
||
269 | } |
||
270 | |||
271 | public Cache(CacheMedium medium, CacheStrategy strategy, |
||
272 | CacheFlags flags) |
||
273 | { |
||
274 | m_Strategy = strategy; |
||
275 | m_Medium = medium; |
||
276 | m_Flags = flags; |
||
277 | } |
||
278 | |||
279 | // Count of the items currently in cache |
||
280 | // |
||
281 | public int Count |
||
282 | { |
||
283 | get { lock (m_Index) { return m_Index.Count; } } |
||
284 | } |
||
285 | |||
286 | // Maximum number of items this cache will hold |
||
287 | // |
||
288 | public int Size |
||
289 | { |
||
290 | get { return m_Size; } |
||
291 | set { SetSize(value); } |
||
292 | } |
||
293 | |||
294 | private void SetSize(int newSize) |
||
295 | { |
||
296 | lock (m_Index) |
||
297 | { |
||
298 | if (Count <= Size) |
||
299 | return; |
||
300 | |||
301 | m_Index.Sort(new SortLRU()); |
||
302 | m_Index.Reverse(); |
||
303 | |||
304 | m_Index.RemoveRange(newSize, Count - newSize); |
||
305 | m_Size = newSize; |
||
306 | |||
307 | m_Lookup.Clear(); |
||
308 | |||
309 | foreach (CacheItemBase item in m_Index) |
||
310 | m_Lookup[item.uuid] = item; |
||
311 | } |
||
312 | } |
||
313 | |||
314 | public TimeSpan DefaultTTL |
||
315 | { |
||
316 | get { return m_DefaultTTL; } |
||
317 | set { m_DefaultTTL = value; } |
||
318 | } |
||
319 | |||
320 | // Get an item from cache. Return the raw item, not it's data |
||
321 | // |
||
322 | protected virtual CacheItemBase GetItem(string index) |
||
323 | { |
||
324 | CacheItemBase item = null; |
||
325 | |||
326 | lock (m_Index) |
||
327 | { |
||
328 | if (m_Lookup.ContainsKey(index)) |
||
329 | item = m_Lookup[index]; |
||
330 | |||
331 | if (item == null) |
||
332 | { |
||
333 | Expire(true); |
||
334 | return null; |
||
335 | } |
||
336 | |||
337 | item.hits++; |
||
338 | item.lastUsed = DateTime.Now; |
||
339 | |||
340 | Expire(true); |
||
341 | } |
||
342 | |||
343 | return item; |
||
344 | } |
||
345 | |||
346 | // Get an item from cache. Do not try to fetch from source if not |
||
347 | // present. Just return null |
||
348 | // |
||
349 | public virtual Object Get(string index) |
||
350 | { |
||
351 | CacheItemBase item = GetItem(index); |
||
352 | |||
353 | if (item == null) |
||
354 | return null; |
||
355 | |||
356 | return item.Retrieve(); |
||
357 | } |
||
358 | |||
359 | // Fetch an object from backing store if not cached, serve from |
||
360 | // cache if it is. |
||
361 | // |
||
362 | public virtual Object Get(string index, FetchDelegate fetch) |
||
363 | { |
||
364 | Object item = Get(index); |
||
365 | if (item != null) |
||
366 | return item; |
||
367 | |||
368 | Object data = fetch(index); |
||
369 | if (data == null) |
||
370 | { |
||
371 | if ((m_Flags & CacheFlags.CacheMissing) != 0) |
||
372 | { |
||
373 | lock (m_Index) |
||
374 | { |
||
375 | CacheItemBase missing = new CacheItemBase(index); |
||
376 | if (!m_Index.Contains(missing)) |
||
377 | { |
||
378 | m_Index.Add(missing); |
||
379 | m_Lookup[index] = missing; |
||
380 | } |
||
381 | } |
||
382 | } |
||
383 | return null; |
||
384 | } |
||
385 | |||
386 | Store(index, data); |
||
387 | |||
388 | return data; |
||
389 | } |
||
390 | |||
391 | // Find an object in cache by delegate. |
||
392 | // |
||
393 | public Object Find(Predicate<CacheItemBase> d) |
||
394 | { |
||
395 | CacheItemBase item; |
||
396 | |||
397 | lock (m_Index) |
||
398 | item = m_Index.Find(d); |
||
399 | |||
400 | if (item == null) |
||
401 | return null; |
||
402 | |||
403 | return item.Retrieve(); |
||
404 | } |
||
405 | |||
406 | public virtual void Store(string index, Object data) |
||
407 | { |
||
408 | Type container; |
||
409 | |||
410 | switch (m_Medium) |
||
411 | { |
||
412 | case CacheMedium.Memory: |
||
413 | container = typeof(MemoryCacheItem); |
||
414 | break; |
||
415 | case CacheMedium.File: |
||
416 | return; |
||
417 | default: |
||
418 | return; |
||
419 | } |
||
420 | |||
421 | Store(index, data, container); |
||
422 | } |
||
423 | |||
424 | public virtual void Store(string index, Object data, Type container) |
||
425 | { |
||
426 | Store(index, data, container, new Object[] { index }); |
||
427 | } |
||
428 | |||
429 | public virtual void Store(string index, Object data, Type container, |
||
430 | Object[] parameters) |
||
431 | { |
||
432 | CacheItemBase item; |
||
433 | |||
434 | lock (m_Index) |
||
435 | { |
||
436 | Expire(false); |
||
437 | |||
438 | if (m_Index.Contains(new CacheItemBase(index))) |
||
439 | { |
||
440 | if ((m_Flags & CacheFlags.AllowUpdate) != 0) |
||
441 | { |
||
442 | item = GetItem(index); |
||
443 | |||
444 | item.hits++; |
||
445 | item.lastUsed = DateTime.Now; |
||
446 | if (m_DefaultTTL.Ticks != 0) |
||
447 | item.expires = DateTime.Now + m_DefaultTTL; |
||
448 | |||
449 | item.Store(data); |
||
450 | } |
||
451 | return; |
||
452 | } |
||
453 | |||
454 | item = (CacheItemBase)Activator.CreateInstance(container, |
||
455 | parameters); |
||
456 | |||
457 | if (m_DefaultTTL.Ticks != 0) |
||
458 | item.expires = DateTime.Now + m_DefaultTTL; |
||
459 | |||
460 | m_Index.Add(item); |
||
461 | m_Lookup[index] = item; |
||
462 | } |
||
463 | |||
464 | item.Store(data); |
||
465 | } |
||
466 | |||
467 | /// <summary> |
||
468 | /// Expire items as appropriate. |
||
469 | /// </summary> |
||
470 | /// <remarks> |
||
471 | /// Callers must lock m_Index. |
||
472 | /// </remarks> |
||
473 | /// <param name='getting'></param> |
||
474 | protected virtual void Expire(bool getting) |
||
475 | { |
||
476 | if (getting && (m_Strategy == CacheStrategy.Aggressive)) |
||
477 | return; |
||
478 | |||
479 | if (m_DefaultTTL.Ticks != 0) |
||
480 | { |
||
481 | DateTime now= DateTime.Now; |
||
482 | |||
483 | foreach (CacheItemBase item in new List<CacheItemBase>(m_Index)) |
||
484 | { |
||
485 | if (item.expires.Ticks == 0 || |
||
486 | item.expires <= now) |
||
487 | { |
||
488 | m_Index.Remove(item); |
||
489 | m_Lookup.Remove(item.uuid); |
||
490 | } |
||
491 | } |
||
492 | } |
||
493 | |||
494 | switch (m_Strategy) |
||
495 | { |
||
496 | case CacheStrategy.Aggressive: |
||
497 | if (Count < Size) |
||
498 | return; |
||
499 | |||
500 | m_Index.Sort(new SortLRU()); |
||
501 | m_Index.Reverse(); |
||
502 | |||
503 | int target = (int)((float)Size * 0.9); |
||
504 | if (target == Count) // Cover ridiculous cache sizes |
||
505 | return; |
||
506 | |||
507 | ExpireDelegate doExpire = OnExpire; |
||
508 | |||
509 | if (doExpire != null) |
||
510 | { |
||
511 | List<CacheItemBase> candidates = |
||
512 | m_Index.GetRange(target, Count - target); |
||
513 | |||
514 | foreach (CacheItemBase i in candidates) |
||
515 | { |
||
516 | if (doExpire(i.uuid)) |
||
517 | { |
||
518 | m_Index.Remove(i); |
||
519 | m_Lookup.Remove(i.uuid); |
||
520 | } |
||
521 | } |
||
522 | } |
||
523 | else |
||
524 | { |
||
525 | m_Index.RemoveRange(target, Count - target); |
||
526 | |||
527 | m_Lookup.Clear(); |
||
528 | |||
529 | foreach (CacheItemBase item in m_Index) |
||
530 | m_Lookup[item.uuid] = item; |
||
531 | } |
||
532 | |||
533 | break; |
||
534 | |||
535 | default: |
||
536 | break; |
||
537 | } |
||
538 | } |
||
539 | |||
540 | public void Invalidate(string uuid) |
||
541 | { |
||
542 | lock (m_Index) |
||
543 | { |
||
544 | if (!m_Lookup.ContainsKey(uuid)) |
||
545 | return; |
||
546 | |||
547 | CacheItemBase item = m_Lookup[uuid]; |
||
548 | m_Lookup.Remove(uuid); |
||
549 | m_Index.Remove(item); |
||
550 | } |
||
551 | } |
||
552 | |||
553 | public void Clear() |
||
554 | { |
||
555 | lock (m_Index) |
||
556 | { |
||
557 | m_Index.Clear(); |
||
558 | m_Lookup.Clear(); |
||
559 | } |
||
560 | } |
||
561 | } |
||
562 | } |