opensim-development – Blame information for rev 1

Subversion Repositories:
Rev:
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 }