diff options
author | Mic Bowman | 2011-03-28 10:00:53 -0700 |
---|---|---|
committer | Mic Bowman | 2011-04-10 16:57:02 -0700 |
commit | 77cf9405de10f016d85d67b6016ed27d28ed898f (patch) | |
tree | 79b6561b1f9a5d70b40d59147bb2cc155a397b78 /OpenSim/Region/ClientStack | |
parent | minor: remove mono compiler warnings (diff) | |
download | opensim-SC_OLD-77cf9405de10f016d85d67b6016ed27d28ed898f.zip opensim-SC_OLD-77cf9405de10f016d85d67b6016ed27d28ed898f.tar.gz opensim-SC_OLD-77cf9405de10f016d85d67b6016ed27d28ed898f.tar.bz2 opensim-SC_OLD-77cf9405de10f016d85d67b6016ed27d28ed898f.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 '')
-rw-r--r-- | OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs | 353 |
1 files changed, 235 insertions, 118 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs index 34d72ac..a3f2c15 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs | |||
@@ -49,6 +49,8 @@ using Timer = System.Timers.Timer; | |||
49 | using AssetLandmark = OpenSim.Framework.AssetLandmark; | 49 | using AssetLandmark = OpenSim.Framework.AssetLandmark; |
50 | using Nini.Config; | 50 | using Nini.Config; |
51 | 51 | ||
52 | using System.IO; | ||
53 | |||
52 | namespace OpenSim.Region.ClientStack.LindenUDP | 54 | namespace 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); |
@@ -11729,86 +11808,85 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
11729 | #region PriorityQueue | 11808 | #region PriorityQueue |
11730 | public class PriorityQueue | 11809 | public class PriorityQueue |
11731 | { | 11810 | { |
11732 | internal delegate bool UpdatePriorityHandler(ref double priority, uint local_id); | 11811 | internal delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); |
11812 | |||
11813 | // Heap[0] for self updates | ||
11814 | // Heap[1..12] for entity updates | ||
11733 | 11815 | ||
11734 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[1]; | 11816 | internal const uint m_numberOfQueues = 12; |
11817 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[m_numberOfQueues]; | ||
11735 | private Dictionary<uint, LookupItem> m_lookupTable; | 11818 | private Dictionary<uint, LookupItem> m_lookupTable; |
11736 | private Comparison<double> m_comparison; | ||
11737 | private object m_syncRoot = new object(); | 11819 | private object m_syncRoot = new object(); |
11738 | 11820 | private uint m_nextQueue = 0; | |
11821 | private UInt64 m_nextRequest = 0; | ||
11822 | |||
11739 | internal PriorityQueue() : | 11823 | internal PriorityQueue() : |
11740 | this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, Comparer<double>.Default) { } | 11824 | this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { } |
11741 | internal PriorityQueue(int capacity) : | 11825 | internal PriorityQueue(int capacity) |
11742 | this(capacity, Comparer<double>.Default) { } | ||
11743 | internal PriorityQueue(IComparer<double> comparer) : | ||
11744 | this(new Comparison<double>(comparer.Compare)) { } | ||
11745 | internal PriorityQueue(Comparison<double> comparison) : | ||
11746 | this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, comparison) { } | ||
11747 | internal PriorityQueue(int capacity, IComparer<double> comparer) : | ||
11748 | this(capacity, new Comparison<double>(comparer.Compare)) { } | ||
11749 | internal PriorityQueue(int capacity, Comparison<double> comparison) | ||
11750 | { | 11826 | { |
11751 | m_lookupTable = new Dictionary<uint, LookupItem>(capacity); | 11827 | m_lookupTable = new Dictionary<uint, LookupItem>(capacity); |
11752 | 11828 | ||
11753 | for (int i = 0; i < m_heaps.Length; ++i) | 11829 | for (int i = 0; i < m_heaps.Length; ++i) |
11754 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); | 11830 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); |
11755 | this.m_comparison = comparison; | ||
11756 | } | 11831 | } |
11757 | 11832 | ||
11758 | public object SyncRoot { get { return this.m_syncRoot; } } | 11833 | public object SyncRoot { get { return this.m_syncRoot; } } |
11834 | |||
11759 | internal int Count | 11835 | internal int Count |
11760 | { | 11836 | { |
11761 | get | 11837 | get |
11762 | { | 11838 | { |
11763 | int count = 0; | 11839 | int count = 0; |
11764 | for (int i = 0; i < m_heaps.Length; ++i) | 11840 | for (int i = 0; i < m_heaps.Length; ++i) |
11765 | count = m_heaps[i].Count; | 11841 | count += m_heaps[i].Count; |
11766 | return count; | 11842 | return count; |
11767 | } | 11843 | } |
11768 | } | 11844 | } |
11769 | 11845 | ||
11770 | public bool Enqueue(double priority, EntityUpdate value, uint local_id) | 11846 | public bool Enqueue(uint pqueue, EntityUpdate value) |
11771 | { | 11847 | { |
11772 | LookupItem item; | 11848 | LookupItem lookup; |
11773 | 11849 | ||
11774 | if (m_lookupTable.TryGetValue(local_id, out item)) | 11850 | uint localid = value.Entity.LocalId; |
11851 | UInt64 entry = m_nextRequest++; | ||
11852 | if (m_lookupTable.TryGetValue(localid, out lookup)) | ||
11775 | { | 11853 | { |
11776 | // Combine flags | 11854 | entry = lookup.Heap[lookup.Handle].EntryOrder; |
11777 | value.Flags |= item.Heap[item.Handle].Value.Flags; | 11855 | value.Flags |= lookup.Heap[lookup.Handle].Value.Flags; |
11778 | 11856 | lookup.Heap.Remove(lookup.Handle); | |
11779 | item.Heap[item.Handle] = new MinHeapItem(priority, value, local_id, this.m_comparison); | ||
11780 | return false; | ||
11781 | } | ||
11782 | else | ||
11783 | { | ||
11784 | item.Heap = m_heaps[0]; | ||
11785 | item.Heap.Add(new MinHeapItem(priority, value, local_id, this.m_comparison), ref item.Handle); | ||
11786 | m_lookupTable.Add(local_id, item); | ||
11787 | return true; | ||
11788 | } | 11857 | } |
11789 | } | ||
11790 | 11858 | ||
11791 | internal EntityUpdate Peek() | 11859 | pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1); |
11792 | { | 11860 | lookup.Heap = m_heaps[pqueue]; |
11793 | for (int i = 0; i < m_heaps.Length; ++i) | 11861 | lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); |
11794 | if (m_heaps[i].Count > 0) | 11862 | m_lookupTable[localid] = lookup; |
11795 | return m_heaps[i].Min().Value; | 11863 | |
11796 | throw new InvalidOperationException(string.Format("The {0} is empty", this.GetType().ToString())); | 11864 | return true; |
11797 | } | 11865 | } |
11798 | 11866 | ||
11799 | internal bool TryDequeue(out EntityUpdate value) | 11867 | internal bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue) |
11800 | { | 11868 | { |
11801 | for (int i = 0; i < m_heaps.Length; ++i) | 11869 | for (int i = 0; i < m_numberOfQueues; ++i) |
11802 | { | 11870 | { |
11803 | if (m_heaps[i].Count > 0) | 11871 | // To get the fair queing, we cycle through each of the |
11872 | // queues when finding an element to dequeue, this code | ||
11873 | // assumes that the distribution of updates in the queues | ||
11874 | // is polynomial, probably quadractic (eg distance of PI * R^2) | ||
11875 | uint h = (uint)((m_nextQueue + i) % m_numberOfQueues); | ||
11876 | if (m_heaps[h].Count > 0) | ||
11804 | { | 11877 | { |
11805 | MinHeapItem item = m_heaps[i].RemoveMin(); | 11878 | m_nextQueue = (uint)((h + 1) % m_numberOfQueues); |
11806 | m_lookupTable.Remove(item.LocalID); | 11879 | |
11880 | MinHeapItem item = m_heaps[h].RemoveMin(); | ||
11881 | m_lookupTable.Remove(item.Value.Entity.LocalId); | ||
11882 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | ||
11807 | value = item.Value; | 11883 | value = item.Value; |
11884 | |||
11808 | return true; | 11885 | return true; |
11809 | } | 11886 | } |
11810 | } | 11887 | } |
11811 | 11888 | ||
11889 | timeinqueue = 0; | ||
11812 | value = default(EntityUpdate); | 11890 | value = default(EntityUpdate); |
11813 | return false; | 11891 | return false; |
11814 | } | 11892 | } |
@@ -11816,68 +11894,107 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
11816 | internal void Reprioritize(UpdatePriorityHandler handler) | 11894 | internal void Reprioritize(UpdatePriorityHandler handler) |
11817 | { | 11895 | { |
11818 | MinHeapItem item; | 11896 | MinHeapItem item; |
11819 | double priority; | ||
11820 | |||
11821 | foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values)) | 11897 | foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values)) |
11822 | { | 11898 | { |
11823 | if (lookup.Heap.TryGetValue(lookup.Handle, out item)) | 11899 | if (lookup.Heap.TryGetValue(lookup.Handle, out item)) |
11824 | { | 11900 | { |
11825 | priority = item.Priority; | 11901 | uint pqueue = item.PriorityQueue; |
11826 | if (handler(ref priority, item.LocalID)) | 11902 | uint localid = item.Value.Entity.LocalId; |
11903 | |||
11904 | if (handler(ref pqueue, item.Value.Entity)) | ||
11827 | { | 11905 | { |
11828 | if (lookup.Heap.ContainsHandle(lookup.Handle)) | 11906 | // unless the priority queue has changed, there is no need to modify |
11829 | lookup.Heap[lookup.Handle] = | 11907 | // the entry |
11830 | new MinHeapItem(priority, item.Value, item.LocalID, this.m_comparison); | 11908 | pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1); |
11909 | if (pqueue != item.PriorityQueue) | ||
11910 | { | ||
11911 | lookup.Heap.Remove(lookup.Handle); | ||
11912 | |||
11913 | LookupItem litem = lookup; | ||
11914 | litem.Heap = m_heaps[pqueue]; | ||
11915 | litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle); | ||
11916 | m_lookupTable[localid] = litem; | ||
11917 | } | ||
11831 | } | 11918 | } |
11832 | else | 11919 | else |
11833 | { | 11920 | { |
11834 | m_log.Warn("[LLCLIENTVIEW]: UpdatePriorityHandler returned false, dropping update"); | 11921 | m_log.WarnFormat("[LLCLIENTVIEW]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID); |
11835 | lookup.Heap.Remove(lookup.Handle); | 11922 | lookup.Heap.Remove(lookup.Handle); |
11836 | this.m_lookupTable.Remove(item.LocalID); | 11923 | this.m_lookupTable.Remove(localid); |
11837 | } | 11924 | } |
11838 | } | 11925 | } |
11839 | } | 11926 | } |
11840 | } | 11927 | } |
11841 | 11928 | ||
11929 | public override string ToString() | ||
11930 | { | ||
11931 | string s = ""; | ||
11932 | for (int i = 0; i < m_numberOfQueues; i++) | ||
11933 | { | ||
11934 | if (s != "") s += ","; | ||
11935 | s += m_heaps[i].Count.ToString(); | ||
11936 | } | ||
11937 | return s; | ||
11938 | } | ||
11939 | |||
11842 | #region MinHeapItem | 11940 | #region MinHeapItem |
11843 | private struct MinHeapItem : IComparable<MinHeapItem> | 11941 | private struct MinHeapItem : IComparable<MinHeapItem> |
11844 | { | 11942 | { |
11845 | private double priority; | ||
11846 | private EntityUpdate value; | 11943 | private EntityUpdate value; |
11847 | private uint local_id; | 11944 | internal EntityUpdate Value { |
11848 | private Comparison<double> comparison; | 11945 | get { |
11946 | return this.value; | ||
11947 | } | ||
11948 | } | ||
11949 | |||
11950 | private uint pqueue; | ||
11951 | internal uint PriorityQueue { | ||
11952 | get { | ||
11953 | return this.pqueue; | ||
11954 | } | ||
11955 | } | ||
11849 | 11956 | ||
11850 | internal MinHeapItem(double priority, EntityUpdate value, uint local_id) : | 11957 | private Int32 entrytime; |
11851 | this(priority, value, local_id, Comparer<double>.Default) { } | 11958 | internal Int32 EntryTime { |
11852 | internal MinHeapItem(double priority, EntityUpdate value, uint local_id, IComparer<double> comparer) : | 11959 | get { |
11853 | this(priority, value, local_id, new Comparison<double>(comparer.Compare)) { } | 11960 | return this.entrytime; |
11854 | internal MinHeapItem(double priority, EntityUpdate value, uint local_id, Comparison<double> comparison) | 11961 | } |
11962 | } | ||
11963 | |||
11964 | private UInt64 entryorder; | ||
11965 | internal UInt64 EntryOrder | ||
11855 | { | 11966 | { |
11856 | this.priority = priority; | 11967 | get { |
11968 | return this.entryorder; | ||
11969 | } | ||
11970 | } | ||
11971 | |||
11972 | internal MinHeapItem(uint pqueue, MinHeapItem other) | ||
11973 | { | ||
11974 | this.entrytime = other.entrytime; | ||
11975 | this.entryorder = other.entryorder; | ||
11976 | this.value = other.value; | ||
11977 | this.pqueue = pqueue; | ||
11978 | } | ||
11979 | |||
11980 | internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value) | ||
11981 | { | ||
11982 | this.entrytime = Util.EnvironmentTickCount(); | ||
11983 | this.entryorder = entryorder; | ||
11857 | this.value = value; | 11984 | this.value = value; |
11858 | this.local_id = local_id; | 11985 | this.pqueue = pqueue; |
11859 | this.comparison = comparison; | ||
11860 | } | 11986 | } |
11861 | 11987 | ||
11862 | internal double Priority { get { return this.priority; } } | ||
11863 | internal EntityUpdate Value { get { return this.value; } } | ||
11864 | internal uint LocalID { get { return this.local_id; } } | ||
11865 | |||
11866 | public override string ToString() | 11988 | public override string ToString() |
11867 | { | 11989 | { |
11868 | StringBuilder sb = new StringBuilder(); | 11990 | return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId); |
11869 | sb.Append("["); | ||
11870 | sb.Append(this.priority.ToString()); | ||
11871 | sb.Append(","); | ||
11872 | if (this.value != null) | ||
11873 | sb.Append(this.value.ToString()); | ||
11874 | sb.Append("]"); | ||
11875 | return sb.ToString(); | ||
11876 | } | 11991 | } |
11877 | 11992 | ||
11878 | public int CompareTo(MinHeapItem other) | 11993 | public int CompareTo(MinHeapItem other) |
11879 | { | 11994 | { |
11880 | return this.comparison(this.priority, other.priority); | 11995 | // I'm assuming that the root part of an SOG is added to the update queue |
11996 | // before the component parts | ||
11997 | return Comparer<UInt64>.Default.Compare(this.EntryOrder, other.EntryOrder); | ||
11881 | } | 11998 | } |
11882 | } | 11999 | } |
11883 | #endregion | 12000 | #endregion |