aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim
diff options
context:
space:
mode:
authorMic Bowman2011-03-28 10:00:53 -0700
committerMic Bowman2011-04-04 11:41:07 -0700
commit6885b7220c6f782034d7c0220762244adf00e3d3 (patch)
tree9ed211a2e7e615f7e227fb53dcbe4c9d541e0ebe /OpenSim
parentImplement rezzing coalesced objects (diff)
downloadopensim-SC_OLD-6885b7220c6f782034d7c0220762244adf00e3d3.zip
opensim-SC_OLD-6885b7220c6f782034d7c0220762244adf00e3d3.tar.gz
opensim-SC_OLD-6885b7220c6f782034d7c0220762244adf00e3d3.tar.bz2
opensim-SC_OLD-6885b7220c6f782034d7c0220762244adf00e3d3.tar.xz
Implements adaptive queue management and fair queueing for
improved networking performance. Reprioritization algorithms need to be ported still. One is in place.
Diffstat (limited to 'OpenSim')
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs353
-rw-r--r--OpenSim/Region/Framework/Scenes/Prioritizer.cs71
2 files changed, 304 insertions, 120 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index 2faffae..e9e1fa3 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
@@ -49,6 +49,8 @@ using Timer = System.Timers.Timer;
49using AssetLandmark = OpenSim.Framework.AssetLandmark; 49using AssetLandmark = OpenSim.Framework.AssetLandmark;
50using Nini.Config; 50using Nini.Config;
51 51
52using System.IO;
53
52namespace OpenSim.Region.ClientStack.LindenUDP 54namespace OpenSim.Region.ClientStack.LindenUDP
53{ 55{
54 public delegate bool PacketMethod(IClientAPI simClient, Packet packet); 56 public delegate bool PacketMethod(IClientAPI simClient, Packet packet);
@@ -298,6 +300,77 @@ namespace OpenSim.Region.ClientStack.LindenUDP
298 /// <summary>Used to adjust Sun Orbit values so Linden based viewers properly position sun</summary> 300 /// <summary>Used to adjust Sun Orbit values so Linden based viewers properly position sun</summary>
299 private const float m_sunPainDaHalfOrbitalCutoff = 4.712388980384689858f; 301 private const float m_sunPainDaHalfOrbitalCutoff = 4.712388980384689858f;
300 302
303 // First log file or time has expired, start writing to a new log file
304//<MIC>
305// -----------------------------------------------------------------
306// -----------------------------------------------------------------
307// THIS IS DEBUGGING CODE & SHOULD BE REMOVED
308// -----------------------------------------------------------------
309// -----------------------------------------------------------------
310 public class QueueLogger
311 {
312 public Int32 start = 0;
313 public StreamWriter Log = null;
314 private Dictionary<UUID,int> m_idMap = new Dictionary<UUID,int>();
315
316 public QueueLogger()
317 {
318 DateTime now = DateTime.Now;
319 String fname = String.Format("queue-{0}.log", now.ToString("yyyyMMddHHmmss"));
320 Log = new StreamWriter(fname);
321
322 start = Util.EnvironmentTickCount();
323 }
324
325 public int LookupID(UUID uuid)
326 {
327 int localid;
328 if (! m_idMap.TryGetValue(uuid,out localid))
329 {
330 localid = m_idMap.Count + 1;
331 m_idMap[uuid] = localid;
332 }
333
334 return localid;
335 }
336 }
337
338 public static QueueLogger QueueLog = null;
339
340 // -----------------------------------------------------------------
341 public void LogAvatarUpdateEvent(UUID client, UUID avatar, Int32 timeinqueue)
342 {
343 if (QueueLog == null)
344 QueueLog = new QueueLogger();
345
346 Int32 ticks = Util.EnvironmentTickCountSubtract(QueueLog.start);
347 lock(QueueLog)
348 {
349 int cid = QueueLog.LookupID(client);
350 int aid = QueueLog.LookupID(avatar);
351 QueueLog.Log.WriteLine("{0},AU,AV{1:D4},AV{2:D4},{3}",ticks,cid,aid,timeinqueue);
352 }
353 }
354
355 // -----------------------------------------------------------------
356 public void LogQueueProcessEvent(UUID client, PriorityQueue queue, uint maxup)
357 {
358 if (QueueLog == null)
359 QueueLog = new QueueLogger();
360
361 Int32 ticks = Util.EnvironmentTickCountSubtract(QueueLog.start);
362 lock(QueueLog)
363 {
364 int cid = QueueLog.LookupID(client);
365 QueueLog.Log.WriteLine("{0},PQ,AV{1:D4},{2},{3}",ticks,cid,maxup,queue.ToString());
366 }
367 }
368// -----------------------------------------------------------------
369// -----------------------------------------------------------------
370// -----------------------------------------------------------------
371// -----------------------------------------------------------------
372//</MIC>
373
301 private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); 374 private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
302 protected static Dictionary<PacketType, PacketMethod> PacketHandlers = new Dictionary<PacketType, PacketMethod>(); //Global/static handlers for all clients 375 protected static Dictionary<PacketType, PacketMethod> PacketHandlers = new Dictionary<PacketType, PacketMethod>(); //Global/static handlers for all clients
303 376
@@ -3547,18 +3620,23 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3547 3620
3548 #region Primitive Packet/Data Sending Methods 3621 #region Primitive Packet/Data Sending Methods
3549 3622
3623
3550 /// <summary> 3624 /// <summary>
3551 /// Generate one of the object update packets based on PrimUpdateFlags 3625 /// Generate one of the object update packets based on PrimUpdateFlags
3552 /// and broadcast the packet to clients 3626 /// and broadcast the packet to clients
3553 /// </summary> 3627 /// </summary>
3554 public void SendPrimUpdate(ISceneEntity entity, PrimUpdateFlags updateFlags) 3628 public void SendPrimUpdate(ISceneEntity entity, PrimUpdateFlags updateFlags)
3555 { 3629 {
3556 double priority = m_prioritizer.GetUpdatePriority(this, entity); 3630 //double priority = m_prioritizer.GetUpdatePriority(this, entity);
3631 uint priority = m_prioritizer.GetUpdatePriority(this, entity);
3557 3632
3558 lock (m_entityUpdates.SyncRoot) 3633 lock (m_entityUpdates.SyncRoot)
3559 m_entityUpdates.Enqueue(priority, new EntityUpdate(entity, updateFlags, m_scene.TimeDilation), entity.LocalId); 3634 m_entityUpdates.Enqueue(priority, new EntityUpdate(entity, updateFlags, m_scene.TimeDilation));
3560 } 3635 }
3561 3636
3637 private Int32 m_LastQueueFill = 0;
3638 private uint m_maxUpdates = 0;
3639
3562 private void ProcessEntityUpdates(int maxUpdates) 3640 private void ProcessEntityUpdates(int maxUpdates)
3563 { 3641 {
3564 OpenSim.Framework.Lazy<List<ObjectUpdatePacket.ObjectDataBlock>> objectUpdateBlocks = new OpenSim.Framework.Lazy<List<ObjectUpdatePacket.ObjectDataBlock>>(); 3642 OpenSim.Framework.Lazy<List<ObjectUpdatePacket.ObjectDataBlock>> objectUpdateBlocks = new OpenSim.Framework.Lazy<List<ObjectUpdatePacket.ObjectDataBlock>>();
@@ -3566,23 +3644,55 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3566 OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>> terseUpdateBlocks = new OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>>(); 3644 OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>> terseUpdateBlocks = new OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>>();
3567 OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>> terseAgentUpdateBlocks = new OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>>(); 3645 OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>> terseAgentUpdateBlocks = new OpenSim.Framework.Lazy<List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>>();
3568 3646
3569 if (maxUpdates <= 0) maxUpdates = Int32.MaxValue; 3647 if (maxUpdates <= 0)
3648 {
3649 m_maxUpdates = Int32.MaxValue;
3650 }
3651 else
3652 {
3653 if (m_maxUpdates == 0 || m_LastQueueFill == 0)
3654 {
3655 m_maxUpdates = (uint)maxUpdates;
3656 }
3657 else
3658 {
3659 if (Util.EnvironmentTickCountSubtract(m_LastQueueFill) < 200)
3660 m_maxUpdates += 5;
3661 else
3662 m_maxUpdates = m_maxUpdates >> 1;
3663 }
3664 m_maxUpdates = Util.Clamp<uint>(m_maxUpdates,10,500);
3665 }
3666 m_LastQueueFill = Util.EnvironmentTickCount();
3667
3570 int updatesThisCall = 0; 3668 int updatesThisCall = 0;
3571 3669
3670//<MIC>
3671// DEBUGGING CODE... REMOVE
3672// LogQueueProcessEvent(this.m_agentId,m_entityUpdates,m_maxUpdates);
3673//</MIC>
3572 // We must lock for both manipulating the kill record and sending the packet, in order to avoid a race 3674 // We must lock for both manipulating the kill record and sending the packet, in order to avoid a race
3573 // condition where a kill can be processed before an out-of-date update for the same object. 3675 // condition where a kill can be processed before an out-of-date update for the same object.
3574 lock (m_killRecord) 3676 lock (m_killRecord)
3575 { 3677 {
3576 float avgTimeDilation = 1.0f; 3678 float avgTimeDilation = 1.0f;
3577 EntityUpdate update; 3679 EntityUpdate update;
3578 while (updatesThisCall < maxUpdates) 3680 Int32 timeinqueue; // this is just debugging code & can be dropped later
3681
3682 while (updatesThisCall < m_maxUpdates)
3579 { 3683 {
3580 lock (m_entityUpdates.SyncRoot) 3684 lock (m_entityUpdates.SyncRoot)
3581 if (!m_entityUpdates.TryDequeue(out update)) 3685 if (!m_entityUpdates.TryDequeue(out update, out timeinqueue))
3582 break; 3686 break;
3583 avgTimeDilation += update.TimeDilation; 3687 avgTimeDilation += update.TimeDilation;
3584 avgTimeDilation *= 0.5f; 3688 avgTimeDilation *= 0.5f;
3585 3689
3690// <MIC>
3691// DEBUGGING CODE... REMOVE
3692// if (update.Entity is ScenePresence)
3693// LogAvatarUpdateEvent(this.m_agentId,update.Entity.UUID,timeinqueue);
3694// </MIC>
3695
3586 if (update.Entity is SceneObjectPart) 3696 if (update.Entity is SceneObjectPart)
3587 { 3697 {
3588 SceneObjectPart part = (SceneObjectPart)update.Entity; 3698 SceneObjectPart part = (SceneObjectPart)update.Entity;
@@ -3679,36 +3789,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3679 } 3789 }
3680 else 3790 else
3681 { 3791 {
3682 // if (update.Entity is SceneObjectPart && ((SceneObjectPart)update.Entity).IsAttachment) 3792 objectUpdateBlocks.Value.Add(CreatePrimUpdateBlock((SceneObjectPart)update.Entity, this.m_agentId));
3683 // {
3684 // SceneObjectPart sop = (SceneObjectPart)update.Entity;
3685 // string text = sop.Text;
3686 // if (text.IndexOf("\n") >= 0)
3687 // text = text.Remove(text.IndexOf("\n"));
3688 //
3689 // if (m_attachmentsSent.Contains(sop.ParentID))
3690 // {
3691 //// m_log.DebugFormat(
3692 //// "[CLIENT]: Sending full info about attached prim {0} text {1}",
3693 //// sop.LocalId, text);
3694 //
3695 // objectUpdateBlocks.Value.Add(CreatePrimUpdateBlock(sop, this.m_agentId));
3696 //
3697 // m_attachmentsSent.Add(sop.LocalId);
3698 // }
3699 // else
3700 // {
3701 // m_log.DebugFormat(
3702 // "[CLIENT]: Requeueing full update of prim {0} text {1} since we haven't sent its parent {2} yet",
3703 // sop.LocalId, text, sop.ParentID);
3704 //
3705 // m_entityUpdates.Enqueue(double.MaxValue, update, sop.LocalId);
3706 // }
3707 // }
3708 // else
3709 // {
3710 objectUpdateBlocks.Value.Add(CreatePrimUpdateBlock((SceneObjectPart)update.Entity, this.m_agentId));
3711 // }
3712 } 3793 }
3713 } 3794 }
3714 else if (!canUseImproved) 3795 else if (!canUseImproved)
@@ -3802,26 +3883,24 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3802 3883
3803 public void ReprioritizeUpdates() 3884 public void ReprioritizeUpdates()
3804 { 3885 {
3805 //m_log.Debug("[CLIENT]: Reprioritizing prim updates for " + m_firstName + " " + m_lastName);
3806
3807 lock (m_entityUpdates.SyncRoot) 3886 lock (m_entityUpdates.SyncRoot)
3808 m_entityUpdates.Reprioritize(UpdatePriorityHandler); 3887 m_entityUpdates.Reprioritize(UpdatePriorityHandler);
3809 } 3888 }
3810 3889
3811 private bool UpdatePriorityHandler(ref double priority, uint localID) 3890 private bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity)
3812 { 3891 {
3813 EntityBase entity; 3892 if (entity != null)
3814 if (m_scene.Entities.TryGetValue(localID, out entity))
3815 { 3893 {
3816 priority = m_prioritizer.GetUpdatePriority(this, entity); 3894 priority = m_prioritizer.GetUpdatePriority(this, entity);
3895 return true;
3817 } 3896 }
3818 3897
3819 return priority != double.NaN; 3898 return false;
3820 } 3899 }
3821 3900
3822 public void FlushPrimUpdates() 3901 public void FlushPrimUpdates()
3823 { 3902 {
3824 m_log.Debug("[CLIENT]: Flushing prim updates to " + m_firstName + " " + m_lastName); 3903 m_log.WarnFormat("[CLIENT]: Flushing prim updates to " + m_firstName + " " + m_lastName);
3825 3904
3826 while (m_entityUpdates.Count > 0) 3905 while (m_entityUpdates.Count > 0)
3827 ProcessEntityUpdates(-1); 3906 ProcessEntityUpdates(-1);
@@ -11713,86 +11792,85 @@ namespace OpenSim.Region.ClientStack.LindenUDP
11713 #region PriorityQueue 11792 #region PriorityQueue
11714 public class PriorityQueue 11793 public class PriorityQueue
11715 { 11794 {
11716 internal delegate bool UpdatePriorityHandler(ref double priority, uint local_id); 11795 internal delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity);
11796
11797 // Heap[0] for self updates
11798 // Heap[1..12] for entity updates
11717 11799
11718 private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[1]; 11800 internal const uint m_numberOfQueues = 12;
11801 private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[m_numberOfQueues];
11719 private Dictionary<uint, LookupItem> m_lookupTable; 11802 private Dictionary<uint, LookupItem> m_lookupTable;
11720 private Comparison<double> m_comparison;
11721 private object m_syncRoot = new object(); 11803 private object m_syncRoot = new object();
11722 11804 private uint m_nextQueue = 0;
11805 private UInt64 m_nextRequest = 0;
11806
11723 internal PriorityQueue() : 11807 internal PriorityQueue() :
11724 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, Comparer<double>.Default) { } 11808 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { }
11725 internal PriorityQueue(int capacity) : 11809 internal PriorityQueue(int capacity)
11726 this(capacity, Comparer<double>.Default) { }
11727 internal PriorityQueue(IComparer<double> comparer) :
11728 this(new Comparison<double>(comparer.Compare)) { }
11729 internal PriorityQueue(Comparison<double> comparison) :
11730 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, comparison) { }
11731 internal PriorityQueue(int capacity, IComparer<double> comparer) :
11732 this(capacity, new Comparison<double>(comparer.Compare)) { }
11733 internal PriorityQueue(int capacity, Comparison<double> comparison)
11734 { 11810 {
11735 m_lookupTable = new Dictionary<uint, LookupItem>(capacity); 11811 m_lookupTable = new Dictionary<uint, LookupItem>(capacity);
11736 11812
11737 for (int i = 0; i < m_heaps.Length; ++i) 11813 for (int i = 0; i < m_heaps.Length; ++i)
11738 m_heaps[i] = new MinHeap<MinHeapItem>(capacity); 11814 m_heaps[i] = new MinHeap<MinHeapItem>(capacity);
11739 this.m_comparison = comparison;
11740 } 11815 }
11741 11816
11742 public object SyncRoot { get { return this.m_syncRoot; } } 11817 public object SyncRoot { get { return this.m_syncRoot; } }
11818
11743 internal int Count 11819 internal int Count
11744 { 11820 {
11745 get 11821 get
11746 { 11822 {
11747 int count = 0; 11823 int count = 0;
11748 for (int i = 0; i < m_heaps.Length; ++i) 11824 for (int i = 0; i < m_heaps.Length; ++i)
11749 count = m_heaps[i].Count; 11825 count += m_heaps[i].Count;
11750 return count; 11826 return count;
11751 } 11827 }
11752 } 11828 }
11753 11829
11754 public bool Enqueue(double priority, EntityUpdate value, uint local_id) 11830 public bool Enqueue(uint pqueue, EntityUpdate value)
11755 { 11831 {
11756 LookupItem item; 11832 LookupItem lookup;
11757 11833
11758 if (m_lookupTable.TryGetValue(local_id, out item)) 11834 uint localid = value.Entity.LocalId;
11835 UInt64 entry = m_nextRequest++;
11836 if (m_lookupTable.TryGetValue(localid, out lookup))
11759 { 11837 {
11760 // Combine flags 11838 entry = lookup.Heap[lookup.Handle].EntryOrder;
11761 value.Flags |= item.Heap[item.Handle].Value.Flags; 11839 value.Flags |= lookup.Heap[lookup.Handle].Value.Flags;
11762 11840 lookup.Heap.Remove(lookup.Handle);
11763 item.Heap[item.Handle] = new MinHeapItem(priority, value, local_id, this.m_comparison);
11764 return false;
11765 }
11766 else
11767 {
11768 item.Heap = m_heaps[0];
11769 item.Heap.Add(new MinHeapItem(priority, value, local_id, this.m_comparison), ref item.Handle);
11770 m_lookupTable.Add(local_id, item);
11771 return true;
11772 } 11841 }
11773 }
11774 11842
11775 internal EntityUpdate Peek() 11843 pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1);
11776 { 11844 lookup.Heap = m_heaps[pqueue];
11777 for (int i = 0; i < m_heaps.Length; ++i) 11845 lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle);
11778 if (m_heaps[i].Count > 0) 11846 m_lookupTable[localid] = lookup;
11779 return m_heaps[i].Min().Value; 11847
11780 throw new InvalidOperationException(string.Format("The {0} is empty", this.GetType().ToString())); 11848 return true;
11781 } 11849 }
11782 11850
11783 internal bool TryDequeue(out EntityUpdate value) 11851 internal bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue)
11784 { 11852 {
11785 for (int i = 0; i < m_heaps.Length; ++i) 11853 for (int i = 0; i < m_numberOfQueues; ++i)
11786 { 11854 {
11787 if (m_heaps[i].Count > 0) 11855 // To get the fair queing, we cycle through each of the
11856 // queues when finding an element to dequeue, this code
11857 // assumes that the distribution of updates in the queues
11858 // is polynomial, probably quadractic (eg distance of PI * R^2)
11859 uint h = (uint)((m_nextQueue + i) % m_numberOfQueues);
11860 if (m_heaps[h].Count > 0)
11788 { 11861 {
11789 MinHeapItem item = m_heaps[i].RemoveMin(); 11862 m_nextQueue = (uint)((h + 1) % m_numberOfQueues);
11790 m_lookupTable.Remove(item.LocalID); 11863
11864 MinHeapItem item = m_heaps[h].RemoveMin();
11865 m_lookupTable.Remove(item.Value.Entity.LocalId);
11866 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
11791 value = item.Value; 11867 value = item.Value;
11868
11792 return true; 11869 return true;
11793 } 11870 }
11794 } 11871 }
11795 11872
11873 timeinqueue = 0;
11796 value = default(EntityUpdate); 11874 value = default(EntityUpdate);
11797 return false; 11875 return false;
11798 } 11876 }
@@ -11800,68 +11878,107 @@ namespace OpenSim.Region.ClientStack.LindenUDP
11800 internal void Reprioritize(UpdatePriorityHandler handler) 11878 internal void Reprioritize(UpdatePriorityHandler handler)
11801 { 11879 {
11802 MinHeapItem item; 11880 MinHeapItem item;
11803 double priority;
11804
11805 foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values)) 11881 foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values))
11806 { 11882 {
11807 if (lookup.Heap.TryGetValue(lookup.Handle, out item)) 11883 if (lookup.Heap.TryGetValue(lookup.Handle, out item))
11808 { 11884 {
11809 priority = item.Priority; 11885 uint pqueue = item.PriorityQueue;
11810 if (handler(ref priority, item.LocalID)) 11886 uint localid = item.Value.Entity.LocalId;
11887
11888 if (handler(ref pqueue, item.Value.Entity))
11811 { 11889 {
11812 if (lookup.Heap.ContainsHandle(lookup.Handle)) 11890 // unless the priority queue has changed, there is no need to modify
11813 lookup.Heap[lookup.Handle] = 11891 // the entry
11814 new MinHeapItem(priority, item.Value, item.LocalID, this.m_comparison); 11892 pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1);
11893 if (pqueue != item.PriorityQueue)
11894 {
11895 lookup.Heap.Remove(lookup.Handle);
11896
11897 LookupItem litem = lookup;
11898 litem.Heap = m_heaps[pqueue];
11899 litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle);
11900 m_lookupTable[localid] = litem;
11901 }
11815 } 11902 }
11816 else 11903 else
11817 { 11904 {
11818 m_log.Warn("[LLCLIENTVIEW]: UpdatePriorityHandler returned false, dropping update"); 11905 m_log.WarnFormat("[LLCLIENTVIEW]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID);
11819 lookup.Heap.Remove(lookup.Handle); 11906 lookup.Heap.Remove(lookup.Handle);
11820 this.m_lookupTable.Remove(item.LocalID); 11907 this.m_lookupTable.Remove(localid);
11821 } 11908 }
11822 } 11909 }
11823 } 11910 }
11824 } 11911 }
11825 11912
11913 public override string ToString()
11914 {
11915 string s = "";
11916 for (int i = 0; i < m_numberOfQueues; i++)
11917 {
11918 if (s != "") s += ",";
11919 s += m_heaps[i].Count.ToString();
11920 }
11921 return s;
11922 }
11923
11826 #region MinHeapItem 11924 #region MinHeapItem
11827 private struct MinHeapItem : IComparable<MinHeapItem> 11925 private struct MinHeapItem : IComparable<MinHeapItem>
11828 { 11926 {
11829 private double priority;
11830 private EntityUpdate value; 11927 private EntityUpdate value;
11831 private uint local_id; 11928 internal EntityUpdate Value {
11832 private Comparison<double> comparison; 11929 get {
11930 return this.value;
11931 }
11932 }
11933
11934 private uint pqueue;
11935 internal uint PriorityQueue {
11936 get {
11937 return this.pqueue;
11938 }
11939 }
11833 11940
11834 internal MinHeapItem(double priority, EntityUpdate value, uint local_id) : 11941 private Int32 entrytime;
11835 this(priority, value, local_id, Comparer<double>.Default) { } 11942 internal Int32 EntryTime {
11836 internal MinHeapItem(double priority, EntityUpdate value, uint local_id, IComparer<double> comparer) : 11943 get {
11837 this(priority, value, local_id, new Comparison<double>(comparer.Compare)) { } 11944 return this.entrytime;
11838 internal MinHeapItem(double priority, EntityUpdate value, uint local_id, Comparison<double> comparison) 11945 }
11946 }
11947
11948 private UInt64 entryorder;
11949 internal UInt64 EntryOrder
11839 { 11950 {
11840 this.priority = priority; 11951 get {
11952 return this.entryorder;
11953 }
11954 }
11955
11956 internal MinHeapItem(uint pqueue, MinHeapItem other)
11957 {
11958 this.entrytime = other.entrytime;
11959 this.entryorder = other.entryorder;
11960 this.value = other.value;
11961 this.pqueue = pqueue;
11962 }
11963
11964 internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value)
11965 {
11966 this.entrytime = Util.EnvironmentTickCount();
11967 this.entryorder = entryorder;
11841 this.value = value; 11968 this.value = value;
11842 this.local_id = local_id; 11969 this.pqueue = pqueue;
11843 this.comparison = comparison;
11844 } 11970 }
11845 11971
11846 internal double Priority { get { return this.priority; } }
11847 internal EntityUpdate Value { get { return this.value; } }
11848 internal uint LocalID { get { return this.local_id; } }
11849
11850 public override string ToString() 11972 public override string ToString()
11851 { 11973 {
11852 StringBuilder sb = new StringBuilder(); 11974 return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId);
11853 sb.Append("[");
11854 sb.Append(this.priority.ToString());
11855 sb.Append(",");
11856 if (this.value != null)
11857 sb.Append(this.value.ToString());
11858 sb.Append("]");
11859 return sb.ToString();
11860 } 11975 }
11861 11976
11862 public int CompareTo(MinHeapItem other) 11977 public int CompareTo(MinHeapItem other)
11863 { 11978 {
11864 return this.comparison(this.priority, other.priority); 11979 // I'm assuming that the root part of an SOG is added to the update queue
11980 // before the component parts
11981 return Comparer<UInt64>.Default.Compare(this.EntryOrder, other.EntryOrder);
11865 } 11982 }
11866 } 11983 }
11867 #endregion 11984 #endregion
diff --git a/OpenSim/Region/Framework/Scenes/Prioritizer.cs b/OpenSim/Region/Framework/Scenes/Prioritizer.cs
index f9599f5..2764b05 100644
--- a/OpenSim/Region/Framework/Scenes/Prioritizer.cs
+++ b/OpenSim/Region/Framework/Scenes/Prioritizer.cs
@@ -58,7 +58,7 @@ namespace OpenSim.Region.Framework.Scenes
58 58
59 public class Prioritizer 59 public class Prioritizer
60 { 60 {
61// private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType); 61 private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);
62 62
63 /// <summary> 63 /// <summary>
64 /// This is added to the priority of all child prims, to make sure that the root prim update is sent to the 64 /// This is added to the priority of all child prims, to make sure that the root prim update is sent to the
@@ -76,7 +76,74 @@ namespace OpenSim.Region.Framework.Scenes
76 m_scene = scene; 76 m_scene = scene;
77 } 77 }
78 78
79 public double GetUpdatePriority(IClientAPI client, ISceneEntity entity) 79//<mic>
80 public uint GetUpdatePriority(IClientAPI client, ISceneEntity entity)
81 {
82 if (entity == null)
83 {
84 m_log.WarnFormat("[PRIORITIZER] attempt to prioritize null entity");
85 throw new InvalidOperationException("Prioritization entity not defined");
86 }
87
88 // If this is an update for our own avatar give it the highest priority
89 if (client.AgentId == entity.UUID)
90 return 0;
91
92 // Get this agent's position
93 ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
94 if (presence == null)
95 {
96 m_log.WarnFormat("[PRIORITIZER] attempt to prioritize agent no longer in the scene");
97 throw new InvalidOperationException("Prioritization agent not defined");
98 }
99
100 // Use group position for child prims
101 Vector3 entityPos = entity.AbsolutePosition;
102 if (entity is SceneObjectPart)
103 {
104 SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup;
105 if (group != null)
106 entityPos = group.AbsolutePosition;
107 }
108
109 // Use the camera position for local agents and avatar position for remote agents
110 Vector3 presencePos = (presence.IsChildAgent) ?
111 presence.AbsolutePosition :
112 presence.CameraPosition;
113
114 // Compute the distance...
115 double distance = Vector3.Distance(presencePos, entityPos);
116
117 // And convert the distance to a priority queue, this computation gives queues
118 // at 10, 20, 40, 80, 160, 320, 640, and 1280m
119 uint pqueue = 1;
120 for (int i = 0; i < 8; i++)
121 {
122 if (distance < 10 * Math.Pow(2.0,i))
123 break;
124 pqueue++;
125 }
126
127 // If this is a root agent, then determine front & back
128 // Bump up the priority queue for any objects behind the avatar
129 if (! presence.IsChildAgent)
130 {
131 // Root agent, decrease priority for objects behind us
132 Vector3 camPosition = presence.CameraPosition;
133 Vector3 camAtAxis = presence.CameraAtAxis;
134
135 // Plane equation
136 float d = -Vector3.Dot(camPosition, camAtAxis);
137 float p = Vector3.Dot(camAtAxis, entityPos) + d;
138 if (p < 0.0f)
139 pqueue++;
140 }
141
142 return pqueue;
143 }
144//</mic>
145
146 public double bGetUpdatePriority(IClientAPI client, ISceneEntity entity)
80 { 147 {
81 double priority = 0; 148 double priority = 0;
82 149