1
0

UnackedPacketCollection.cs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232
  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. namespace OpenSim.Region.ClientStack.LindenUDP
  33. {
  34. /// <summary>
  35. /// Special collection that is optimized for tracking unacknowledged packets
  36. /// </summary>
  37. public sealed class UnackedPacketCollection
  38. {
  39. /// <summary>
  40. /// Holds information about a pending acknowledgement
  41. /// </summary>
  42. private struct PendingAck
  43. {
  44. /// <summary>Sequence number of the packet to remove</summary>
  45. public uint SequenceNumber;
  46. /// <summary>Environment.TickCount value when the remove was queued.
  47. /// This is used to update round-trip times for packets</summary>
  48. public int RemoveTime;
  49. /// <summary>Whether or not this acknowledgement was attached to a
  50. /// resent packet. If so, round-trip time will not be calculated</summary>
  51. public bool FromResend;
  52. public PendingAck(uint sequenceNumber, int currentTime, bool fromResend)
  53. {
  54. SequenceNumber = sequenceNumber;
  55. RemoveTime = currentTime;
  56. FromResend = fromResend;
  57. }
  58. }
  59. /// <summary>Holds the actual unacked packet data, sorted by sequence number</summary>
  60. private Dictionary<uint, OutgoingPacket> m_packets = new Dictionary<uint, OutgoingPacket>();
  61. /// <summary>Holds packets that need to be added to the unacknowledged list</summary>
  62. private LocklessQueue<OutgoingPacket> m_pendingAdds = new LocklessQueue<OutgoingPacket>();
  63. /// <summary>Holds information about pending acknowledgements</summary>
  64. private LocklessQueue<PendingAck> m_pendingAcknowledgements = new LocklessQueue<PendingAck>();
  65. /// <summary>Holds information about pending removals</summary>
  66. private LocklessQueue<uint> m_pendingRemoves = new LocklessQueue<uint>();
  67. /// <summary>
  68. /// Add an unacked packet to the collection
  69. /// </summary>
  70. /// <param name="packet">Packet that is awaiting acknowledgement</param>
  71. /// <returns>True if the packet was successfully added, false if the
  72. /// packet already existed in the collection</returns>
  73. /// <remarks>This does not immediately add the ACK to the collection,
  74. /// it only queues it so it can be added in a thread-safe way later</remarks>
  75. public void Add(OutgoingPacket packet)
  76. {
  77. m_pendingAdds.Enqueue(packet);
  78. Interlocked.Add(ref packet.Client.UnackedBytes, packet.Buffer.DataLength);
  79. }
  80. /// <summary>
  81. /// Marks a packet as acknowledged
  82. /// This method is used when an acknowledgement is received from the network for a previously
  83. /// sent packet. Effects of removal this way are to update unacked byte count, adjust RTT
  84. /// and increase throttle to the coresponding client.
  85. /// </summary>
  86. /// <param name="sequenceNumber">Sequence number of the packet to
  87. /// acknowledge</param>
  88. /// <param name="currentTime">Current value of Environment.TickCount</param>
  89. /// <remarks>This does not immediately acknowledge the packet, it only
  90. /// queues the ack so it can be handled in a thread-safe way later</remarks>
  91. public void Acknowledge(uint sequenceNumber, int currentTime, bool fromResend)
  92. {
  93. m_pendingAcknowledgements.Enqueue(new PendingAck(sequenceNumber, currentTime, fromResend));
  94. }
  95. /// <summary>
  96. /// Marks a packet as no longer needing acknowledgement without a received acknowledgement.
  97. /// This method is called when a packet expires and we no longer need an acknowledgement.
  98. /// When some reliable packet types expire, they are handled in a way other than simply
  99. /// resending them. The only effect of removal this way is to update unacked byte count.
  100. /// </summary>
  101. /// <param name="sequenceNumber">Sequence number of the packet to
  102. /// acknowledge</param>
  103. /// <remarks>The does not immediately remove the packet, it only queues the removal
  104. /// so it can be handled in a thread safe way later</remarks>
  105. public void Remove(uint sequenceNumber)
  106. {
  107. m_pendingRemoves.Enqueue(sequenceNumber);
  108. }
  109. /// <summary>
  110. /// Returns a list of all of the packets with a TickCount older than
  111. /// the specified timeout
  112. /// </summary>
  113. /// <remarks>
  114. /// This function is not thread safe, and cannot be called
  115. /// multiple times concurrently
  116. /// </remarks>
  117. /// <param name="timeoutMS">Number of ticks (milliseconds) before a
  118. /// packet is considered expired
  119. /// </param>
  120. /// <returns>
  121. /// A list of all expired packets according to the given
  122. /// expiration timeout
  123. /// </returns>
  124. public List<OutgoingPacket> GetExpiredPackets(int timeoutMS)
  125. {
  126. ProcessQueues();
  127. List<OutgoingPacket> expiredPackets = null;
  128. if (m_packets.Count > 0)
  129. {
  130. int now = Environment.TickCount & Int32.MaxValue;
  131. foreach (OutgoingPacket packet in m_packets.Values)
  132. {
  133. // TickCount of zero means a packet is in the resend queue
  134. // but hasn't actually been sent over the wire yet
  135. if (packet.TickCount == 0)
  136. continue;
  137. if (now - packet.TickCount >= timeoutMS)
  138. {
  139. if (expiredPackets == null)
  140. expiredPackets = new List<OutgoingPacket>();
  141. // The TickCount will be set to the current time when the packet
  142. // is actually sent out again
  143. packet.TickCount = 0;
  144. // As with other network applications, assume that an expired packet is
  145. // an indication of some network problem, slow transmission
  146. packet.Client.FlowThrottle.ExpirePackets(1);
  147. expiredPackets.Add(packet);
  148. }
  149. }
  150. }
  151. //if (expiredPackets != null)
  152. // m_log.DebugFormat("[UNACKED PACKET COLLECTION]: Found {0} expired packets on timeout of {1}", expiredPackets.Count, timeoutMS);
  153. return expiredPackets;
  154. }
  155. private void ProcessQueues()
  156. {
  157. // Process all the pending adds
  158. OutgoingPacket pendingAdd;
  159. while (m_pendingAdds.TryDequeue(out pendingAdd))
  160. if (pendingAdd != null)
  161. m_packets[pendingAdd.SequenceNumber] = pendingAdd;
  162. // Process all the pending removes, including updating statistics and round-trip times
  163. PendingAck pendingAcknowledgement;
  164. while (m_pendingAcknowledgements.TryDequeue(out pendingAcknowledgement))
  165. {
  166. //m_log.DebugFormat("[UNACKED PACKET COLLECTION]: Processing ack {0}", pendingAcknowledgement.SequenceNumber);
  167. OutgoingPacket ackedPacket;
  168. if (m_packets.TryGetValue(pendingAcknowledgement.SequenceNumber, out ackedPacket))
  169. {
  170. if (ackedPacket != null)
  171. {
  172. m_packets.Remove(pendingAcknowledgement.SequenceNumber);
  173. // As with other network applications, assume that an acknowledged packet is an
  174. // indication that the network can handle a little more load, speed up the transmission
  175. ackedPacket.Client.FlowThrottle.AcknowledgePackets(ackedPacket.Buffer.DataLength);
  176. // Update stats
  177. Interlocked.Add(ref ackedPacket.Client.UnackedBytes, -ackedPacket.Buffer.DataLength);
  178. if (!pendingAcknowledgement.FromResend)
  179. {
  180. // Calculate the round-trip time for this packet and its ACK
  181. int rtt = pendingAcknowledgement.RemoveTime - ackedPacket.TickCount;
  182. if (rtt > 0)
  183. ackedPacket.Client.UpdateRoundTrip(rtt);
  184. }
  185. }
  186. else
  187. {
  188. //m_log.WarnFormat("[UNACKED PACKET COLLECTION]: Could not find packet with sequence number {0} to ack", pendingAcknowledgement.SequenceNumber);
  189. }
  190. }
  191. }
  192. uint pendingRemove;
  193. while(m_pendingRemoves.TryDequeue(out pendingRemove))
  194. {
  195. OutgoingPacket removedPacket;
  196. if (m_packets.TryGetValue(pendingRemove, out removedPacket))
  197. {
  198. if (removedPacket != null)
  199. {
  200. m_packets.Remove(pendingRemove);
  201. // Update stats
  202. Interlocked.Add(ref removedPacket.Client.UnackedBytes, -removedPacket.Buffer.DataLength);
  203. }
  204. }
  205. }
  206. }
  207. }
  208. }