* Replaced the UnackedPacketCollection with a lockless implementation. The tiny amount of time spent in the locks turned into a lot of time when the rest of the LLUDP implementation went lockless

* Changed the timer tracking numbers for each client to not have "memory". It will no longer queue up calls to functions like ResendUnacked
* Reverted Jim's WaitHandle code. Although it was technically more correct, it exhibited the exact same behavior as the old code but spent more cycles. The 20ms has been replaced with the minimum amount of time before a token bucket could receive a drip, and an else { sleep(0); } was added to make sure the outgoing packet handler always yields at least a minimum amount

1 files changed, 71 insertions, 76 deletions

diff --git a/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs b/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
index 87c7df4..12f0c0a 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
@@ -37,97 +37,57 @@ namespace OpenSim.Region.ClientStack.LindenUDP
     /// </summary>
     public sealed class UnackedPacketCollection
     {
-        /// <summary>Synchronization primitive. A lock must be acquired on this
-        /// object before calling any of the unsafe methods</summary>
-        public object SyncRoot = new object();
-
-        /// <summary>Holds the actual unacked packet data, sorted by sequence number</summary>
-        private SortedDictionary<uint, OutgoingPacket> packets = new SortedDictionary<uint, OutgoingPacket>();
-
-        /// <summary>Gets the total number of unacked packets</summary>
-        public int Count { get { return packets.Count; } }
-
         /// <summary>
-        /// Default constructor
+        /// Holds information about a pending acknowledgement
         /// </summary>
-        public UnackedPacketCollection()
+        private struct PendingAck
         {
-        }
+            /// <summary>Sequence number of the packet to remove</summary>
+            public uint SequenceNumber;
+            /// <summary>Environment.TickCount value when the remove was queued.
+            /// This is used to update round-trip times for packets</summary>
+            public int RemoveTime;
+            /// <summary>Whether or not this acknowledgement was attached to a
+            /// resent packet. If so, round-trip time will not be calculated</summary>
+            public bool FromResend;
 
-        /// <summary>
-        /// Add an unacked packet to the collection
-        /// </summary>
-        /// <param name="packet">Packet that is awaiting acknowledgement</param>
-        /// <returns>True if the packet was successfully added, false if the
-        /// packet already existed in the collection</returns>
-        public bool Add(OutgoingPacket packet)
-        {
-            lock (SyncRoot)
+            public PendingAck(uint sequenceNumber, int currentTime, bool fromResend)
             {
-                if (!packets.ContainsKey(packet.SequenceNumber))
-                {
-                    packets.Add(packet.SequenceNumber, packet);
-                    return true;
-                }
-                return false;
+                SequenceNumber = sequenceNumber;
+                RemoveTime = currentTime;
+                FromResend = fromResend;
             }
         }
 
-        /// <summary>
-        /// Removes a packet from the collection without attempting to obtain a
-        /// lock first
-        /// </summary>
-        /// <param name="sequenceNumber">Sequence number of the packet to remove</param>
-        /// <returns>True if the packet was found and removed, otherwise false</returns>
-        public bool RemoveUnsafe(uint sequenceNumber)
-        {
-            return packets.Remove(sequenceNumber);
-        }
-
-        /// <summary>
-        /// Removes a packet from the collection without attempting to obtain a
-        /// lock first
-        /// </summary>
-        /// <param name="sequenceNumber">Sequence number of the packet to remove</param>
-        /// <param name="packet">Returns the removed packet</param>
-        /// <returns>True if the packet was found and removed, otherwise false</returns>
-        public bool RemoveUnsafe(uint sequenceNumber, out OutgoingPacket packet)
-        {
-            if (packets.TryGetValue(sequenceNumber, out packet))
-            {
-                packets.Remove(sequenceNumber);
-                return true;
-            }
-
-            return false;
-        }
+        /// <summary>Holds the actual unacked packet data, sorted by sequence number</summary>
+        private SortedDictionary<uint, OutgoingPacket> m_packets = new SortedDictionary<uint, OutgoingPacket>();
+        /// <summary>Holds packets that need to be added to the unacknowledged list</summary>
+        private LocklessQueue<OutgoingPacket> m_pendingAdds = new LocklessQueue<OutgoingPacket>();
+        /// <summary>Holds information about pending acknowledgements</summary>
+        private LocklessQueue<PendingAck> m_pendingRemoves = new LocklessQueue<PendingAck>();
 
         /// <summary>
-        /// Removes all elements from the collection
+        /// Add an unacked packet to the collection
         /// </summary>
-        public void Clear()
+        /// <param name="packet">Packet that is awaiting acknowledgement</param>
+        /// <returns>True if the packet was successfully added, false if the
+        /// packet already existed in the collection</returns>
+        /// <remarks>This does not immediately add the ACK to the collection,
+        /// it only queues it so it can be added in a thread-safe way later</remarks>
+        public void Add(OutgoingPacket packet)
         {
-            lock (SyncRoot)
-                packets.Clear();
+            m_pendingAdds.Enqueue(packet);
         }
 
         /// <summary>
-        /// Gets the packet with the lowest sequence number
+        /// Marks a packet as acknowledged
         /// </summary>
-        /// <returns>The packet with the lowest sequence number, or null if the
-        /// collection is empty</returns>
-        public OutgoingPacket GetOldest()
+        /// <param name="sequenceNumber">Sequence number of the packet to
+        /// acknowledge</param>
+        /// <param name="currentTime">Current value of Environment.TickCount</param>
+        public void Remove(uint sequenceNumber, int currentTime, bool fromResend)
         {
-            lock (SyncRoot)
-            {
-                using (SortedDictionary<uint, OutgoingPacket>.ValueCollection.Enumerator e = packets.Values.GetEnumerator())
-                {
-                    if (e.MoveNext())
-                        return e.Current;
-                    else
-                        return null;
-                }
-            }
+            m_pendingRemoves.Enqueue(new PendingAck(sequenceNumber, currentTime, fromResend));
         }
 
         /// <summary>
@@ -138,14 +98,19 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// packet is considered expired</param>
         /// <returns>A list of all expired packets according to the given
         /// expiration timeout</returns>
+        /// <remarks>This function is not thread safe, and cannot be called
+        /// multiple times concurrently</remarks>
         public List<OutgoingPacket> GetExpiredPackets(int timeoutMS)
         {
+            ProcessQueues();
+
             List<OutgoingPacket> expiredPackets = null;
 
-            lock (SyncRoot)
+            if (m_packets.Count > 0)
             {
                 int now = Environment.TickCount;
-                foreach (OutgoingPacket packet in packets.Values)
+
+                foreach (OutgoingPacket packet in m_packets.Values)
                 {
                     // TickCount of zero means a packet is in the resend queue 
                     // but hasn't actually been sent over the wire yet
@@ -167,5 +132,35 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
             return expiredPackets;
         }
+
+        private void ProcessQueues()
+        {
+            // Process all the pending adds
+            OutgoingPacket pendingAdd;
+            while (m_pendingAdds.Dequeue(out pendingAdd))
+                m_packets[pendingAdd.SequenceNumber] = pendingAdd;
+
+            // Process all the pending removes, including updating statistics and round-trip times
+            PendingAck pendingRemove;
+            OutgoingPacket ackedPacket;
+            while (m_pendingRemoves.Dequeue(out pendingRemove))
+            {
+                if (m_packets.TryGetValue(pendingRemove.SequenceNumber, out ackedPacket))
+                {
+                    m_packets.Remove(pendingRemove.SequenceNumber);
+
+                    // Update stats
+                    System.Threading.Interlocked.Add(ref ackedPacket.Client.UnackedBytes, -ackedPacket.Buffer.DataLength);
+
+                    if (!pendingRemove.FromResend)
+                    {
+                        // Calculate the round-trip time for this packet and its ACK
+                        int rtt = pendingRemove.RemoveTime - ackedPacket.TickCount;
+                        if (rtt > 0)
+                            ackedPacket.Client.UpdateRoundTrip(rtt);
+                    }
+                }
+            }
+        }
     }
 }