7 files changed, 242 insertions, 94 deletions

diff --git a/OpenSim/Framework/ClientManager.cs b/OpenSim/Framework/ClientManager.cs
index fd5f87f..367bc6a 100644
--- a/OpenSim/Framework/ClientManager.cs
+++ b/OpenSim/Framework/ClientManager.cs
@@ -121,20 +121,10 @@ namespace OpenSim.Framework
         /// <summary>
         /// Remove a client from the collection
         /// </summary>
-        /// <param name="value">Reference to the client object</param>
-        public void Remove(IClientAPI value)
-        {
-            lock (m_writeLock)
-            {
-                if (m_dict.ContainsKey(value.AgentId))
-                    m_dict = m_dict.Delete(value.AgentId);
-
-                if (m_dict2.ContainsKey(value.RemoteEndPoint))
-                    m_dict2 = m_dict2.Delete(value.RemoteEndPoint);
-            }
-        }
-
-        public void Remove(UUID key)
+        /// <param name="key">UUID of the client to remove</param>
+        /// <returns>True if a client was removed, or false if the given UUID
+        /// was not present in the collection</returns>
+        public bool Remove(UUID key)
         {
             lock (m_writeLock)
             {
@@ -144,6 +134,11 @@ namespace OpenSim.Framework
                 {
                     m_dict = m_dict.Delete(key);
                     m_dict2 = m_dict2.Delete(client.RemoteEndPoint);
+                    return true;
+                }
+                else
+                {
+                    return false;
                 }
             }
         }
diff --git a/OpenSim/Framework/LocklessQueue.cs b/OpenSim/Framework/LocklessQueue.cs
new file mode 100644
index 0000000..dd3d201
--- /dev/null
+++ b/OpenSim/Framework/LocklessQueue.cs
@@ -0,0 +1,130 @@
+/*
+ * Copyright (c) 2009, openmetaverse.org
+ * All rights reserved.
+ *
+ * - 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.
+ * - Neither the name of the openmetaverse.org 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 COPYRIGHT HOLDERS AND CONTRIBUTORS "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 COPYRIGHT OWNER OR 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.Threading;
+
+namespace OpenSim.Framework
+{
+    public sealed class LocklessQueue<T>
+    {
+        private sealed class SingleLinkNode
+        {
+            public SingleLinkNode Next;
+            public T Item;
+        }
+
+        SingleLinkNode head;
+        SingleLinkNode tail;
+        int count;
+
+        public int Count { get { return count; } }
+
+        public LocklessQueue()
+        {
+            Init();
+        }
+
+        public void Enqueue(T item)
+        {
+            SingleLinkNode oldTail = null;
+            SingleLinkNode oldTailNext;
+
+            SingleLinkNode newNode = new SingleLinkNode();
+            newNode.Item = item;
+
+            bool newNodeWasAdded = false;
+
+            while (!newNodeWasAdded)
+            {
+                oldTail = tail;
+                oldTailNext = oldTail.Next;
+
+                if (tail == oldTail)
+                {
+                    if (oldTailNext == null)
+                        newNodeWasAdded = CAS(ref tail.Next, null, newNode);
+                    else
+                        CAS(ref tail, oldTail, oldTailNext);
+                }
+            }
+
+            CAS(ref tail, oldTail, newNode);
+            Interlocked.Increment(ref count);
+        }
+
+        public bool Dequeue(out T item)
+        {
+            item = default(T);
+            SingleLinkNode oldHead = null;
+            bool haveAdvancedHead = false;
+
+            while (!haveAdvancedHead)
+            {
+                oldHead = head;
+                SingleLinkNode oldTail = tail;
+                SingleLinkNode oldHeadNext = oldHead.Next;
+
+                if (oldHead == head)
+                {
+                    if (oldHead == oldTail)
+                    {
+                        if (oldHeadNext == null)
+                            return false;
+
+                        CAS(ref tail, oldTail, oldHeadNext);
+                    }
+                    else
+                    {
+                        item = oldHeadNext.Item;
+                        haveAdvancedHead = CAS(ref head, oldHead, oldHeadNext);
+                    }
+                }
+            }
+
+            Interlocked.Decrement(ref count);
+            return true;
+        }
+
+        public void Clear()
+        {
+            Init();
+        }
+
+        private void Init()
+        {
+            count = 0;
+            head = tail = new SingleLinkNode();
+        }
+
+        private static bool CAS(ref SingleLinkNode location, SingleLinkNode comparand, SingleLinkNode newValue)
+        {
+            return
+                (object)comparand ==
+                (object)Interlocked.CompareExchange<SingleLinkNode>(ref location, newValue, comparand);
+        }
+    }
+}
\ No newline at end of file
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index 0acf6e8..ac558ff 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
@@ -433,13 +433,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             // Remove ourselves from the scene
             m_scene.RemoveClient(AgentId);
 
-            //m_log.InfoFormat("[CLIENTVIEW] Memory pre  GC {0}", System.GC.GetTotalMemory(false));
-            //GC.Collect();
-            //m_log.InfoFormat("[CLIENTVIEW] Memory post GC {0}", System.GC.GetTotalMemory(true));
-
-            // FIXME: Is this still necessary?
-            //Thread.Sleep(2000);
-
             // Shut down timers. Thread Context of this method is murky.   Lock all timers
             if (m_avatarTerseUpdateTimer.Enabled)
                 lock (m_avatarTerseUpdateTimer)
@@ -461,6 +454,10 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
             // Disable UDP handling for this client
             m_udpClient.Shutdown();
+
+            //m_log.InfoFormat("[CLIENTVIEW] Memory pre  GC {0}", System.GC.GetTotalMemory(false));
+            //GC.Collect();
+            //m_log.InfoFormat("[CLIENTVIEW] Memory post GC {0}", System.GC.GetTotalMemory(true));
         }
 
         public void Kick(string message)
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLImageManager.cs b/OpenSim/Region/ClientStack/LindenUDP/LLImageManager.cs
index 8469ba6..8410ee9 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLImageManager.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLImageManager.cs
@@ -213,13 +213,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
             lock (m_syncRoot)
             {
-
                 if (m_priorityQueue.Count > 0)
                 {
-                    try
-                    {
-                        image = m_priorityQueue.FindMax();
-                    }
+                    try { image = m_priorityQueue.FindMax(); }
                     catch (Exception) { }
                 }
             }
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs b/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs
index e5b2594..b27d8d6 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLUDPClient.cs
@@ -80,7 +80,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// <summary>Packets we have sent that need to be ACKed by the client</summary>
         public readonly UnackedPacketCollection NeedAcks = new UnackedPacketCollection();
         /// <summary>ACKs that are queued up, waiting to be sent to the client</summary>
-        public readonly LocklessQueue<uint> PendingAcks = new LocklessQueue<uint>();
+        public readonly OpenSim.Framework.LocklessQueue<uint> PendingAcks = new OpenSim.Framework.LocklessQueue<uint>();
 
         /// <summary>Current packet sequence number</summary>
         public int CurrentSequence;
@@ -127,13 +127,16 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         /// <summary>Throttle rate defaults and limits</summary>
         private readonly ThrottleRates defaultThrottleRates;
         /// <summary>Outgoing queues for throttled packets</summary>
-        private readonly LocklessQueue<OutgoingPacket>[] packetOutboxes = new LocklessQueue<OutgoingPacket>[THROTTLE_CATEGORY_COUNT];
+        private readonly OpenSim.Framework.LocklessQueue<OutgoingPacket>[] packetOutboxes = new OpenSim.Framework.LocklessQueue<OutgoingPacket>[THROTTLE_CATEGORY_COUNT];
         /// <summary>A container that can hold one packet for each outbox, used to store
         /// dequeued packets that are being held for throttling</summary>
         private readonly OutgoingPacket[] nextPackets = new OutgoingPacket[THROTTLE_CATEGORY_COUNT];
         /// <summary>An optimization to store the length of dequeued packets being held
         /// for throttling. This avoids expensive calls to Packet.Length</summary>
         private readonly int[] nextPacketLengths = new int[THROTTLE_CATEGORY_COUNT];
+        /// <summary>Flags to prevent queue empty callbacks from repeatedly firing
+        /// before the callbacks have a chance to put packets in the queue</summary>
+        private readonly bool[] queueEmptySent = new bool[THROTTLE_CATEGORY_COUNT];
         /// <summary>A reference to the LLUDPServer that is managing this client</summary>
         private readonly LLUDPServer udpServer;
 
@@ -156,7 +159,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             defaultThrottleRates = rates;
 
             for (int i = 0; i < THROTTLE_CATEGORY_COUNT; i++)
-                packetOutboxes[i] = new LocklessQueue<OutgoingPacket>();
+                packetOutboxes[i] = new OpenSim.Framework.LocklessQueue<OutgoingPacket>();
 
             throttle = new TokenBucket(parentThrottle, 0, 0);
             throttleCategories = new TokenBucket[THROTTLE_CATEGORY_COUNT];
@@ -182,6 +185,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         public void Shutdown()
         {
             IsConnected = false;
+            NeedAcks.Clear();
+            for (int i = 0; i < THROTTLE_CATEGORY_COUNT; i++)
+            {
+                packetOutboxes[i].Clear();
+                nextPackets[i] = null;
+            }
+            OnPacketStats = null;
+            OnQueueEmpty = null;
         }
 
         /// <summary>
@@ -322,7 +333,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
             if (category >= 0 && category < packetOutboxes.Length)
             {
-                LocklessQueue<OutgoingPacket> queue = packetOutboxes[category];
+                OpenSim.Framework.LocklessQueue<OutgoingPacket> queue = packetOutboxes[category];
                 TokenBucket bucket = throttleCategories[category];
 
                 if (throttleCategories[category].RemoveTokens(packet.Buffer.DataLength))
@@ -354,7 +365,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         public bool DequeueOutgoing()
         {
             OutgoingPacket packet;
-            LocklessQueue<OutgoingPacket> queue;
+            OpenSim.Framework.LocklessQueue<OutgoingPacket> queue;
             TokenBucket bucket;
             bool packetSent = false;
 
@@ -382,6 +393,10 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                     queue = packetOutboxes[i];
                     if (queue.Dequeue(out packet))
                     {
+                        // Reset the flag for firing this queue's OnQueueEmpty callback
+                        // now that we have dequeued a packet
+                        queueEmptySent[i] = false;
+
                         // A packet was pulled off the queue. See if we have
                         // enough tokens in the bucket to send it out
                         if (bucket.RemoveTokens(packet.Buffer.DataLength))
@@ -397,13 +412,18 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                             nextPackets[i] = packet;
                             nextPacketLengths[i] = packet.Buffer.DataLength;
                         }
+
+                        // If the queue is empty after this dequeue, fire the queue
+                        // empty callback now so it has a chance to fill before we 
+                        // get back here
+                        if (queue.Count == 0)
+                            FireQueueEmpty(i);
                     }
                     else
                     {
                         // No packets in this queue. Fire the queue empty callback
-                        QueueEmpty callback = OnQueueEmpty;
-                        if (callback != null)
-                            callback((ThrottleOutPacketType)i);
+                        // if it has not been called recently
+                        FireQueueEmpty(i);
                     }
                 }
             }
@@ -432,8 +452,20 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
             // Always round retransmission timeout up to two seconds
             RTO = Math.Max(2000, (int)(SRTT + Math.Max(G, K * RTTVAR)));
-            //Logger.Debug("Setting agent " + this.Agent.FullName + "'s RTO to " + RTO + "ms with an RTTVAR of " +
+            //m_log.Debug("[LLUDPCLIENT]: Setting agent " + this.Agent.FullName + "'s RTO to " + RTO + "ms with an RTTVAR of " +
             //    RTTVAR + " based on new RTT of " + r + "ms");
         }
+
+        private void FireQueueEmpty(int queueIndex)
+        {
+            if (!queueEmptySent[queueIndex])
+            {
+                queueEmptySent[queueIndex] = true;
+
+                QueueEmpty callback = OnQueueEmpty;
+                if (callback != null)
+                    Util.FireAndForget(delegate(object o) { callback((ThrottleOutPacketType)(int)o); }, queueIndex);
+            }
+        }
     }
 }
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs b/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs
index 8689af3..57fee59 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLUDPServer.cs
@@ -332,8 +332,19 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
         public void ResendUnacked(LLUDPClient udpClient)
         {
-            if (udpClient.NeedAcks.Count > 0)
+            if (udpClient.IsConnected && udpClient.NeedAcks.Count > 0)
             {
+                // Disconnect an agent if no packets are received for some time
+                //FIXME: Make 60 an .ini setting
+                if (Environment.TickCount - udpClient.TickLastPacketReceived > 1000 * 60)
+                {
+                    m_log.Warn("[LLUDPSERVER]: Ack timeout, disconnecting " + udpClient.AgentID);
+
+                    RemoveClient(udpClient);
+                    return;
+                }
+
+                // Get a list of all of the packets that have been sitting unacked longer than udpClient.RTO
                 List<OutgoingPacket> expiredPackets = udpClient.NeedAcks.GetExpiredPackets(udpClient.RTO);
 
                 if (expiredPackets != null)
@@ -343,48 +354,24 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                     {
                         OutgoingPacket outgoingPacket = expiredPackets[i];
 
-                        // FIXME: Make this an .ini setting
-                        if (outgoingPacket.ResendCount < 3)
-                        {
-                            //Logger.Debug(String.Format("Resending packet #{0} (attempt {1}), {2}ms have passed",
-                            //    outgoingPacket.SequenceNumber, outgoingPacket.ResendCount, Environment.TickCount - outgoingPacket.TickCount));
+                        //m_log.DebugFormat("[LLUDPSERVER]: Resending packet #{0} (attempt {1}), {2}ms have passed",
+                        //    outgoingPacket.SequenceNumber, outgoingPacket.ResendCount, Environment.TickCount - outgoingPacket.TickCount);
 
-                            // Set the resent flag
-                            outgoingPacket.Buffer.Data[0] = (byte)(outgoingPacket.Buffer.Data[0] | Helpers.MSG_RESENT);
-                            outgoingPacket.Category = ThrottleOutPacketType.Resend;
+                        // Set the resent flag
+                        outgoingPacket.Buffer.Data[0] = (byte)(outgoingPacket.Buffer.Data[0] | Helpers.MSG_RESENT);
+                        outgoingPacket.Category = ThrottleOutPacketType.Resend;
 
-                            // The TickCount will be set to the current time when the packet
-                            // is actually sent out again
-                            outgoingPacket.TickCount = 0;
+                        // The TickCount will be set to the current time when the packet
+                        // is actually sent out again
+                        outgoingPacket.TickCount = 0;
 
-                            // Bump up the resend count on this packet
-                            Interlocked.Increment(ref outgoingPacket.ResendCount);
-                            //Interlocked.Increment(ref Stats.ResentPackets);
+                        // Bump up the resend count on this packet
+                        Interlocked.Increment(ref outgoingPacket.ResendCount);
+                        //Interlocked.Increment(ref Stats.ResentPackets);
 
-                            // Queue or (re)send the packet
-                            if (!outgoingPacket.Client.EnqueueOutgoing(outgoingPacket))
-                                SendPacketFinal(outgoingPacket);
-                        }
-                        else
-                        {
-                            m_log.DebugFormat("[LLUDPSERVER]: Dropping packet #{0} for agent {1} after {2} failed attempts",
-                                outgoingPacket.SequenceNumber, outgoingPacket.Client.RemoteEndPoint, outgoingPacket.ResendCount);
-
-                            lock (udpClient.NeedAcks.SyncRoot)
-                                udpClient.NeedAcks.RemoveUnsafe(outgoingPacket.SequenceNumber);
-
-                            //Interlocked.Increment(ref Stats.DroppedPackets);
-
-                            // Disconnect an agent if no packets are received for some time
-                            //FIXME: Make 60 an .ini setting
-                            if (Environment.TickCount - udpClient.TickLastPacketReceived > 1000 * 60)
-                            {
-                                m_log.Warn("[LLUDPSERVER]: Ack timeout, disconnecting " + udpClient.AgentID);
-
-                                RemoveClient(udpClient);
-                                return;
-                            }
-                        }
+                        // Requeue or resend the packet
+                        if (!outgoingPacket.Client.EnqueueOutgoing(outgoingPacket))
+                            SendPacketFinal(outgoingPacket);
                     }
                 }
             }
@@ -403,6 +390,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             bool isReliable = (flags & Helpers.MSG_RELIABLE) != 0;
             LLUDPClient udpClient = outgoingPacket.Client;
 
+            if (!udpClient.IsConnected)
+                return;
+
             // Keep track of when this packet was sent out (right now)
             outgoingPacket.TickCount = Environment.TickCount;
 
@@ -481,14 +471,15 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             }
             catch (MalformedDataException)
             {
-                m_log.ErrorFormat("[LLUDPSERVER]: Malformed data, cannot parse packet:\n{0}",
-                    Utils.BytesToHexString(buffer.Data, buffer.DataLength, null));
+                m_log.ErrorFormat("[LLUDPSERVER]: Malformed data, cannot parse packet from {0}:\n{1}",
+                    buffer.RemoteEndPoint, Utils.BytesToHexString(buffer.Data, buffer.DataLength, null));
             }
 
             // Fail-safe check
             if (packet == null)
             {
-                m_log.Warn("[LLUDPSERVER]: Couldn't build a message from the incoming data");
+                m_log.Warn("[LLUDPSERVER]: Couldn't build a message from incoming data " + buffer.DataLength +
+                    " bytes long from " + buffer.RemoteEndPoint);
                 return;
             }
 
@@ -513,6 +504,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
             udpClient = ((LLClientView)client).UDPClient;
 
+            if (!udpClient.IsConnected)
+                return;
+
             #endregion Packet to Client Mapping
 
             // Stats tracking
@@ -643,7 +637,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                 // Create the LLClientView
                 LLClientView client = new LLClientView(remoteEndPoint, m_scene, this, udpClient, sessionInfo, agentID, sessionID, circuitCode);
                 client.OnLogout += LogoutHandler;
-                client.OnConnectionClosed += ConnectionClosedHandler;
 
                 // Start the IClientAPI
                 client.Start();
@@ -745,17 +738,20 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                         {
                             LLUDPClient udpClient = ((LLClientView)client).UDPClient;
 
-                            if (udpClient.DequeueOutgoing())
-                                packetSent = true;
-                            if (resendUnacked)
-                                ResendUnacked(udpClient);
-                            if (sendAcks)
+                            if (udpClient.IsConnected)
                             {
-                                SendAcks(udpClient);
-                                udpClient.SendPacketStats();
+                                if (udpClient.DequeueOutgoing())
+                                    packetSent = true;
+                                if (resendUnacked)
+                                    ResendUnacked(udpClient);
+                                if (sendAcks)
+                                {
+                                    SendAcks(udpClient);
+                                    udpClient.SendPacketStats();
+                                }
+                                if (sendPings)
+                                    SendPing(udpClient);
                             }
-                            if (sendPings)
-                                SendPing(udpClient);
                         }
                     }
                 );
@@ -808,14 +804,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
 
         private void LogoutHandler(IClientAPI client)
         {
-            client.OnLogout -= LogoutHandler;
             client.SendLogoutPacket();
         }
-
-        private void ConnectionClosedHandler(IClientAPI client)
-        {
-            client.OnConnectionClosed -= ConnectionClosedHandler;
-            RemoveClient(((LLClientView)client).UDPClient);
-        }
     }
 }
diff --git a/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs b/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
index 195ca57..f3242c1 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/UnackedPacketCollection.cs
@@ -103,6 +103,15 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         }
 
         /// <summary>
+        /// Removes all elements from the collection
+        /// </summary>
+        public void Clear()
+        {
+            lock (SyncRoot)
+                packets.Clear();
+        }
+
+        /// <summary>
         /// Gets the packet with the lowest sequence number
         /// </summary>
         /// <returns>The packet with the lowest sequence number, or null if the