From 7759bda833c03f4c29500dce32b835a7aef8285b Mon Sep 17 00:00:00 2001 From: Mic Bowman Date: Wed, 20 Apr 2011 21:58:49 -0700 Subject: Added an "immediate" queue to the priority queue. This is per Melanie's very good suggestion. The immediate queue is serviced completely before all others, making it a very good place to put avatar updates & attachments. Moved the priority queue out of the LLUDP directory and into the framework. It is now a fairly general utility. --- OpenSim/Framework/PriorityQueue.cs | 258 +++++++++++++++++++++++++++++++++++++ 1 file changed, 258 insertions(+) create mode 100644 OpenSim/Framework/PriorityQueue.cs (limited to 'OpenSim/Framework/PriorityQueue.cs') diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs new file mode 100644 index 0000000..eec2a92 --- /dev/null +++ b/OpenSim/Framework/PriorityQueue.cs @@ -0,0 +1,258 @@ +/* + * Copyright (c) Contributors, http://opensimulator.org/ + * See CONTRIBUTORS.TXT for a full list of copyright holders. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of the OpenSimulator Project nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +using System; +using System.Collections; +using System.Collections.Generic; +using System.Reflection; + +using OpenSim.Framework; +using OpenSim.Framework.Client; +using log4net; + +namespace OpenSim.Framework +{ + public class PriorityQueue + { + private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); + + public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); + + // Heap[0] for self updates + // Heap[1..12] for entity updates + + public const uint NumberOfQueues = 12; + public const uint ImmediateQueue = 0; + + private MinHeap[] m_heaps = new MinHeap[NumberOfQueues]; + private Dictionary m_lookupTable; + private uint m_nextQueue = 0; + private UInt64 m_nextRequest = 0; + + private object m_syncRoot = new object(); + public object SyncRoot { + get { return this.m_syncRoot; } + } + + public PriorityQueue() : this(MinHeap.DEFAULT_CAPACITY) { } + + public PriorityQueue(int capacity) + { + m_lookupTable = new Dictionary(capacity); + + for (int i = 0; i < m_heaps.Length; ++i) + m_heaps[i] = new MinHeap(capacity); + } + + public int Count + { + get + { + int count = 0; + for (int i = 0; i < m_heaps.Length; ++i) + count += m_heaps[i].Count; + return count; + } + } + + public bool Enqueue(uint pqueue, IEntityUpdate value) + { + LookupItem lookup; + + uint localid = value.Entity.LocalId; + UInt64 entry = m_nextRequest++; + if (m_lookupTable.TryGetValue(localid, out lookup)) + { + entry = lookup.Heap[lookup.Handle].EntryOrder; + value.Update(lookup.Heap[lookup.Handle].Value); + lookup.Heap.Remove(lookup.Handle); + } + + pqueue = Util.Clamp(pqueue, 0, NumberOfQueues - 1); + lookup.Heap = m_heaps[pqueue]; + lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); + m_lookupTable[localid] = lookup; + + return true; + } + + public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) + { + // If there is anything in priority queue 0, return it first no + // matter what else. Breaks fairness. But very useful. + if (m_heaps[ImmediateQueue].Count > 0) + { + MinHeapItem item = m_heaps[ImmediateQueue].RemoveMin(); + m_lookupTable.Remove(item.Value.Entity.LocalId); + timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); + value = item.Value; + + return true; + } + + for (int i = 0; i < NumberOfQueues; ++i) + { + // To get the fair queing, we cycle through each of the + // queues when finding an element to dequeue, this code + // assumes that the distribution of updates in the queues + // is polynomial, probably quadractic (eg distance of PI * R^2) + uint h = (uint)((m_nextQueue + i) % NumberOfQueues); + if (m_heaps[h].Count > 0) + { + m_nextQueue = (uint)((h + 1) % NumberOfQueues); + + MinHeapItem item = m_heaps[h].RemoveMin(); + m_lookupTable.Remove(item.Value.Entity.LocalId); + timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); + value = item.Value; + + return true; + } + } + + timeinqueue = 0; + value = default(IEntityUpdate); + return false; + } + + public void Reprioritize(UpdatePriorityHandler handler) + { + MinHeapItem item; + foreach (LookupItem lookup in new List(this.m_lookupTable.Values)) + { + if (lookup.Heap.TryGetValue(lookup.Handle, out item)) + { + uint pqueue = item.PriorityQueue; + uint localid = item.Value.Entity.LocalId; + + if (handler(ref pqueue, item.Value.Entity)) + { + // unless the priority queue has changed, there is no need to modify + // the entry + pqueue = Util.Clamp(pqueue, 0, NumberOfQueues - 1); + if (pqueue != item.PriorityQueue) + { + lookup.Heap.Remove(lookup.Handle); + + LookupItem litem = lookup; + litem.Heap = m_heaps[pqueue]; + litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle); + m_lookupTable[localid] = litem; + } + } + else + { + // m_log.WarnFormat("[PQUEUE]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID); + lookup.Heap.Remove(lookup.Handle); + this.m_lookupTable.Remove(localid); + } + } + } + } + + public override string ToString() + { + string s = ""; + for (int i = 0; i < NumberOfQueues; i++) + { + if (s != "") s += ","; + s += m_heaps[i].Count.ToString(); + } + return s; + } + +#region MinHeapItem + private struct MinHeapItem : IComparable + { + private IEntityUpdate value; + internal IEntityUpdate Value { + get { + return this.value; + } + } + + private uint pqueue; + internal uint PriorityQueue { + get { + return this.pqueue; + } + } + + private Int32 entrytime; + internal Int32 EntryTime { + get { + return this.entrytime; + } + } + + private UInt64 entryorder; + internal UInt64 EntryOrder + { + get { + return this.entryorder; + } + } + + internal MinHeapItem(uint pqueue, MinHeapItem other) + { + this.entrytime = other.entrytime; + this.entryorder = other.entryorder; + this.value = other.value; + this.pqueue = pqueue; + } + + internal MinHeapItem(uint pqueue, UInt64 entryorder, IEntityUpdate value) + { + this.entrytime = Util.EnvironmentTickCount(); + this.entryorder = entryorder; + this.value = value; + this.pqueue = pqueue; + } + + public override string ToString() + { + return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId); + } + + public int CompareTo(MinHeapItem other) + { + // I'm assuming that the root part of an SOG is added to the update queue + // before the component parts + return Comparer.Default.Compare(this.EntryOrder, other.EntryOrder); + } + } +#endregion + +#region LookupItem + private struct LookupItem + { + internal MinHeap Heap; + internal IHandle Handle; + } +#endregion + } +} -- cgit v1.1 From 3534f4492ae747baff492f4bc10bf06994ee1bc6 Mon Sep 17 00:00:00 2001 From: Mic Bowman Date: Fri, 22 Apr 2011 14:01:12 -0700 Subject: Various clean ups. Removed some debugging code. Added a new "show pqueues" command to look at the entity update priority queue. Added a "name" parameter to show queues, show pqueues and show throttles to look at data for a specific user. --- OpenSim/Framework/PriorityQueue.cs | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'OpenSim/Framework/PriorityQueue.cs') diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs index eec2a92..ea718c4 100644 --- a/OpenSim/Framework/PriorityQueue.cs +++ b/OpenSim/Framework/PriorityQueue.cs @@ -174,14 +174,13 @@ namespace OpenSim.Framework } } + /// + /// public override string ToString() { string s = ""; for (int i = 0; i < NumberOfQueues; i++) - { - if (s != "") s += ","; - s += m_heaps[i].Count.ToString(); - } + s += String.Format("{0,7} ",m_heaps[i].Count); return s; } -- cgit v1.1 From a3bd769cb33ee59b883998205454bb340d44cb9e Mon Sep 17 00:00:00 2001 From: Mic Bowman Date: Fri, 22 Apr 2011 14:55:23 -0700 Subject: Added a second immediate queue to be used for the BestAvatar policy and currently used for all of an avatars attachments by the other policies. Also changed the way items are pulled from the update queues to bias close objects even more. --- OpenSim/Framework/PriorityQueue.cs | 99 +++++++++++++++++++++++++++++++------- 1 file changed, 82 insertions(+), 17 deletions(-) (limited to 'OpenSim/Framework/PriorityQueue.cs') diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs index ea718c4..8eeafd1 100644 --- a/OpenSim/Framework/PriorityQueue.cs +++ b/OpenSim/Framework/PriorityQueue.cs @@ -42,22 +42,40 @@ namespace OpenSim.Framework public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); - // Heap[0] for self updates - // Heap[1..12] for entity updates - + /// + /// Total number of queues (priorities) available + /// public const uint NumberOfQueues = 12; - public const uint ImmediateQueue = 0; + + /// + /// Number of queuest (priorities) that are processed immediately + /// [] m_heaps = new MinHeap[NumberOfQueues]; private Dictionary m_lookupTable; + + // internal state used to ensure the deqeues are spread across the priority + // queues "fairly". queuecounts is the amount to pull from each queue in + // each pass. weighted towards the higher priority queues private uint m_nextQueue = 0; + private uint m_countFromQueue = 0; + private uint[] m_queueCounts = { 8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1 }; + + // next request is a counter of the number of updates queued, it provides + // a total ordering on the updates coming through the queue and is more + // lightweight (and more discriminating) than tick count private UInt64 m_nextRequest = 0; + /// + /// Lock for enqueue and dequeue operations on the priority queue + /// private object m_syncRoot = new object(); public object SyncRoot { get { return this.m_syncRoot; } } +#region constructor public PriorityQueue() : this(MinHeap.DEFAULT_CAPACITY) { } public PriorityQueue(int capacity) @@ -66,8 +84,16 @@ namespace OpenSim.Framework for (int i = 0; i < m_heaps.Length; ++i) m_heaps[i] = new MinHeap(capacity); + + m_nextQueue = NumberOfImmediateQueues; + m_countFromQueue = m_queueCounts[m_nextQueue]; } +#endregion Constructor +#region PublicMethods + /// + /// Return the number of items in the queues + /// public int Count { get @@ -79,6 +105,9 @@ namespace OpenSim.Framework } } + /// + /// Enqueue an item into the specified priority queue + /// public bool Enqueue(uint pqueue, IEntityUpdate value) { LookupItem lookup; @@ -100,32 +129,62 @@ namespace OpenSim.Framework return true; } + /// + /// Remove an item from one of the queues. Specifically, it removes the + /// oldest item from the next queue in order to provide fair access to + /// all of the queues + /// public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) { // If there is anything in priority queue 0, return it first no // matter what else. Breaks fairness. But very useful. - if (m_heaps[ImmediateQueue].Count > 0) + for (int iq = 0; iq < NumberOfImmediateQueues; iq++) + { + if (m_heaps[iq].Count > 0) + { + MinHeapItem item = m_heaps[iq].RemoveMin(); + m_lookupTable.Remove(item.Value.Entity.LocalId); + timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); + value = item.Value; + + return true; + } + } + + // To get the fair queing, we cycle through each of the + // queues when finding an element to dequeue. + // We pull (NumberOfQueues - QueueIndex) items from each queue in order + // to give lower numbered queues a higher priority and higher percentage + // of the bandwidth. + + // Check for more items to be pulled from the current queue + if (m_heaps[m_nextQueue].Count > 0 && m_countFromQueue > 0) { - MinHeapItem item = m_heaps[ImmediateQueue].RemoveMin(); + m_countFromQueue--; + + MinHeapItem item = m_heaps[m_nextQueue].RemoveMin(); m_lookupTable.Remove(item.Value.Entity.LocalId); timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); value = item.Value; - + return true; } - - for (int i = 0; i < NumberOfQueues; ++i) + + // Find the next non-immediate queue with updates in it + for (int i = 1; i < NumberOfQueues; ++i) { - // To get the fair queing, we cycle through each of the - // queues when finding an element to dequeue, this code - // assumes that the distribution of updates in the queues - // is polynomial, probably quadractic (eg distance of PI * R^2) - uint h = (uint)((m_nextQueue + i) % NumberOfQueues); - if (m_heaps[h].Count > 0) + m_nextQueue = (uint)((m_nextQueue + i) % NumberOfQueues); + m_countFromQueue = m_queueCounts[m_nextQueue]; + + // if this is one of the immediate queues, just skip it + if (m_nextQueue < NumberOfImmediateQueues) + continue; + + if (m_heaps[m_nextQueue].Count > 0) { - m_nextQueue = (uint)((h + 1) % NumberOfQueues); + m_countFromQueue--; - MinHeapItem item = m_heaps[h].RemoveMin(); + MinHeapItem item = m_heaps[m_nextQueue].RemoveMin(); m_lookupTable.Remove(item.Value.Entity.LocalId); timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); value = item.Value; @@ -139,6 +198,10 @@ namespace OpenSim.Framework return false; } + /// + /// Reapply the prioritization function to each of the updates currently + /// stored in the priority queues. + /// { -- cgit v1.1 From e2c6ed236d45e91ffb354b1c59e9f5a5a5b7952d Mon Sep 17 00:00:00 2001 From: Mic Bowman Date: Sat, 23 Apr 2011 12:17:10 -0700 Subject: Fix a bug looping through the priority queues. This should fix the problem of not all prims being sent without reprioritization. --- OpenSim/Framework/PriorityQueue.cs | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'OpenSim/Framework/PriorityQueue.cs') diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs index 8eeafd1..3e6fdaa 100644 --- a/OpenSim/Framework/PriorityQueue.cs +++ b/OpenSim/Framework/PriorityQueue.cs @@ -101,6 +101,7 @@ namespace OpenSim.Framework int count = 0; for (int i = 0; i < m_heaps.Length; ++i) count += m_heaps[i].Count; + return count; } } @@ -171,9 +172,9 @@ namespace OpenSim.Framework } // Find the next non-immediate queue with updates in it - for (int i = 1; i < NumberOfQueues; ++i) + for (int i = 0; i < NumberOfQueues; ++i) { - m_nextQueue = (uint)((m_nextQueue + i) % NumberOfQueues); + m_nextQueue = (uint)((m_nextQueue + 1) % NumberOfQueues); m_countFromQueue = m_queueCounts[m_nextQueue]; // if this is one of the immediate queues, just skip it -- cgit v1.1