UnackedPacketCollection.cs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252
  1. /*
  2. * Copyright (c) Contributors, http://opensimulator.org/
  3. * See CONTRIBUTORS.TXT for a full list of copyright holders.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. * * Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * * Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. * * Neither the name of the OpenSimulator Project nor the
  13. * names of its contributors may be used to endorse or promote products
  14. * derived from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
  17. * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19. * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
  20. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. using System;
  28. using System.Collections.Generic;
  29. using System.Net;
  30. using System.Threading;
  31. using OpenMetaverse;
  32. //using System.Reflection;
  33. //using log4net;
  34. namespace OpenSim.Region.ClientStack.LindenUDP
  35. {
  36. /// <summary>
  37. /// Special collection that is optimized for tracking unacknowledged packets
  38. /// </summary>
  39. public sealed class UnackedPacketCollection
  40. {
  41. /// <summary>
  42. /// Holds information about a pending acknowledgement
  43. /// </summary>
  44. private struct PendingAck
  45. {
  46. /// <summary>Sequence number of the packet to remove</summary>
  47. public uint SequenceNumber;
  48. /// <summary>Environment.TickCount value when the remove was queued.
  49. /// This is used to update round-trip times for packets</summary>
  50. public int RemoveTime;
  51. /// <summary>Whether or not this acknowledgement was attached to a
  52. /// resent packet. If so, round-trip time will not be calculated</summary>
  53. public bool FromResend;
  54. public PendingAck(uint sequenceNumber, int currentTime, bool fromResend)
  55. {
  56. SequenceNumber = sequenceNumber;
  57. RemoveTime = currentTime;
  58. FromResend = fromResend;
  59. }
  60. }
  61. //private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
  62. /// <summary>Holds the actual unacked packet data, sorted by sequence number</summary>
  63. private Dictionary<uint, OutgoingPacket> m_packets = new Dictionary<uint, OutgoingPacket>();
  64. /// <summary>Holds packets that need to be added to the unacknowledged list</summary>
  65. private LocklessQueue<OutgoingPacket> m_pendingAdds = new LocklessQueue<OutgoingPacket>();
  66. /// <summary>Holds information about pending acknowledgements</summary>
  67. private LocklessQueue<PendingAck> m_pendingAcknowledgements = new LocklessQueue<PendingAck>();
  68. /// <summary>Holds information about pending removals</summary>
  69. private LocklessQueue<uint> m_pendingRemoves = new LocklessQueue<uint>();
  70. public void Clear()
  71. {
  72. m_packets.Clear();
  73. m_pendingAdds = null;
  74. m_pendingAcknowledgements = null;
  75. m_pendingRemoves = null;
  76. }
  77. /// <summary>
  78. /// Add an unacked packet to the collection
  79. /// </summary>
  80. /// <param name="packet">Packet that is awaiting acknowledgement</param>
  81. /// <returns>True if the packet was successfully added, false if the
  82. /// packet already existed in the collection</returns>
  83. /// <remarks>This does not immediately add the ACK to the collection,
  84. /// it only queues it so it can be added in a thread-safe way later</remarks>
  85. public void Add(OutgoingPacket packet)
  86. {
  87. m_pendingAdds.Enqueue(packet);
  88. Interlocked.Add(ref packet.Client.UnackedBytes, packet.Buffer.DataLength);
  89. }
  90. /// <summary>
  91. /// Marks a packet as acknowledged
  92. /// This method is used when an acknowledgement is received from the network for a previously
  93. /// sent packet. Effects of removal this way are to update unacked byte count, adjust RTT
  94. /// and increase throttle to the coresponding client.
  95. /// </summary>
  96. /// <param name="sequenceNumber">Sequence number of the packet to
  97. /// acknowledge</param>
  98. /// <param name="currentTime">Current value of Environment.TickCount</param>
  99. /// <remarks>This does not immediately acknowledge the packet, it only
  100. /// queues the ack so it can be handled in a thread-safe way later</remarks>
  101. public void Acknowledge(uint sequenceNumber, int currentTime, bool fromResend)
  102. {
  103. m_pendingAcknowledgements.Enqueue(new PendingAck(sequenceNumber, currentTime, fromResend));
  104. }
  105. /// <summary>
  106. /// Marks a packet as no longer needing acknowledgement without a received acknowledgement.
  107. /// This method is called when a packet expires and we no longer need an acknowledgement.
  108. /// When some reliable packet types expire, they are handled in a way other than simply
  109. /// resending them. The only effect of removal this way is to update unacked byte count.
  110. /// </summary>
  111. /// <param name="sequenceNumber">Sequence number of the packet to
  112. /// acknowledge</param>
  113. /// <remarks>The does not immediately remove the packet, it only queues the removal
  114. /// so it can be handled in a thread safe way later</remarks>
  115. public void Remove(uint sequenceNumber)
  116. {
  117. m_pendingRemoves.Enqueue(sequenceNumber);
  118. }
  119. /// <summary>
  120. /// Returns a list of all of the packets with a TickCount older than
  121. /// the specified timeout
  122. /// </summary>
  123. /// <remarks>
  124. /// This function is not thread safe, and cannot be called
  125. /// multiple times concurrently
  126. /// </remarks>
  127. /// <param name="timeoutMS">Number of ticks (milliseconds) before a
  128. /// packet is considered expired
  129. /// </param>
  130. /// <returns>
  131. /// A list of all expired packets according to the given
  132. /// expiration timeout
  133. /// </returns>
  134. public List<OutgoingPacket> GetExpiredPackets(int timeoutMS)
  135. {
  136. ProcessQueues();
  137. List<OutgoingPacket> expiredPackets = null;
  138. if (m_packets.Count > 0)
  139. {
  140. int now = Environment.TickCount & Int32.MaxValue;
  141. foreach (OutgoingPacket packet in m_packets.Values)
  142. {
  143. // TickCount of zero means a packet is in the resend queue
  144. // but hasn't actually been sent over the wire yet
  145. if (packet.TickCount == 0)
  146. continue;
  147. if (now - packet.TickCount >= timeoutMS)
  148. {
  149. if (expiredPackets == null)
  150. expiredPackets = new List<OutgoingPacket>();
  151. // The TickCount will be set to the current time when the packet
  152. // is actually sent out again
  153. packet.TickCount = 0;
  154. // As with other network applications, assume that an expired packet is
  155. // an indication of some network problem, slow transmission
  156. packet.Client.FlowThrottle.ExpirePackets(1);
  157. expiredPackets.Add(packet);
  158. }
  159. }
  160. }
  161. // if (expiredPackets != null)
  162. // m_log.DebugFormat("[UNACKED PACKET COLLECTION]: Found {0} expired packets on timeout of {1}", expiredPackets.Count, timeoutMS);
  163. return expiredPackets;
  164. }
  165. private void ProcessQueues()
  166. {
  167. // Process all the pending adds
  168. OutgoingPacket pendingAdd;
  169. while (m_pendingAdds.TryDequeue(out pendingAdd))
  170. if (pendingAdd != null)
  171. m_packets[pendingAdd.SequenceNumber] = pendingAdd;
  172. // Process all the pending removes, including updating statistics and round-trip times
  173. PendingAck pendingAcknowledgement;
  174. while (m_pendingAcknowledgements.TryDequeue(out pendingAcknowledgement))
  175. {
  176. //m_log.DebugFormat("[UNACKED PACKET COLLECTION]: Processing ack {0}", pendingAcknowledgement.SequenceNumber);
  177. OutgoingPacket ackedPacket;
  178. if (m_packets.TryGetValue(pendingAcknowledgement.SequenceNumber, out ackedPacket))
  179. {
  180. if (ackedPacket != null)
  181. {
  182. m_packets.Remove(pendingAcknowledgement.SequenceNumber);
  183. // As with other network applications, assume that an acknowledged packet is an
  184. // indication that the network can handle a little more load, speed up the transmission
  185. ackedPacket.Client.FlowThrottle.AcknowledgePackets(1);
  186. // Update stats
  187. Interlocked.Add(ref ackedPacket.Client.UnackedBytes, -ackedPacket.Buffer.DataLength);
  188. if (!pendingAcknowledgement.FromResend)
  189. {
  190. // Calculate the round-trip time for this packet and its ACK
  191. int rtt = pendingAcknowledgement.RemoveTime - ackedPacket.TickCount;
  192. if (rtt > 0)
  193. ackedPacket.Client.UpdateRoundTrip(rtt);
  194. }
  195. }
  196. else
  197. {
  198. // m_log.WarnFormat("[UNACKED PACKET COLLECTION]: found null packet for sequence number {0} to ack",
  199. // pendingAcknowledgement.SequenceNumber);
  200. }
  201. }
  202. else
  203. {
  204. // m_log.WarnFormat("[UNACKED PACKET COLLECTION]: Could not find packet with sequence number {0} to ack",
  205. // pendingAcknowledgement.SequenceNumber);
  206. }
  207. }
  208. uint pendingRemove;
  209. while(m_pendingRemoves.TryDequeue(out pendingRemove))
  210. {
  211. OutgoingPacket removedPacket;
  212. if (m_packets.TryGetValue(pendingRemove, out removedPacket))
  213. {
  214. if (removedPacket != null)
  215. {
  216. m_packets.Remove(pendingRemove);
  217. // Update stats
  218. Interlocked.Add(ref removedPacket.Client.UnackedBytes, -removedPacket.Buffer.DataLength);
  219. }
  220. }
  221. }
  222. }
  223. }
  224. }