1
0

UnackedPacketCollection.cs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261
  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 SortedDictionary<uint, OutgoingPacket> m_packets = new SortedDictionary<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. private uint m_older;
  71. public void Clear()
  72. {
  73. m_packets.Clear();
  74. m_pendingAdds = null;
  75. m_pendingAcknowledgements = null;
  76. m_pendingRemoves = null;
  77. m_older = 0;
  78. }
  79. public int Count()
  80. {
  81. return m_packets.Count + m_pendingAdds.Count - m_pendingAcknowledgements.Count - m_pendingRemoves.Count;
  82. }
  83. public uint Oldest()
  84. {
  85. return m_older;
  86. }
  87. /// <summary>
  88. /// Add an unacked packet to the collection
  89. /// </summary>
  90. /// <param name="packet">Packet that is awaiting acknowledgement</param>
  91. /// <returns>True if the packet was successfully added, false if the
  92. /// packet already existed in the collection</returns>
  93. /// <remarks>This does not immediately add the ACK to the collection,
  94. /// it only queues it so it can be added in a thread-safe way later</remarks>
  95. public void Add(OutgoingPacket packet)
  96. {
  97. m_pendingAdds.Enqueue(packet);
  98. Interlocked.Add(ref packet.Client.UnackedBytes, packet.Buffer.DataLength);
  99. }
  100. /// <summary>
  101. /// Marks a packet as acknowledged
  102. /// This method is used when an acknowledgement is received from the network for a previously
  103. /// sent packet. Effects of removal this way are to update unacked byte count, adjust RTT
  104. /// and increase throttle to the coresponding client.
  105. /// </summary>
  106. /// <param name="sequenceNumber">Sequence number of the packet to
  107. /// acknowledge</param>
  108. /// <param name="currentTime">Current value of Environment.TickCount</param>
  109. /// <remarks>This does not immediately acknowledge the packet, it only
  110. /// queues the ack so it can be handled in a thread-safe way later</remarks>
  111. public void Acknowledge(uint sequenceNumber, int currentTime, bool fromResend)
  112. {
  113. m_pendingAcknowledgements.Enqueue(new PendingAck(sequenceNumber, currentTime, fromResend));
  114. }
  115. /// <summary>
  116. /// Marks a packet as no longer needing acknowledgement without a received acknowledgement.
  117. /// This method is called when a packet expires and we no longer need an acknowledgement.
  118. /// When some reliable packet types expire, they are handled in a way other than simply
  119. /// resending them. The only effect of removal this way is to update unacked byte count.
  120. /// </summary>
  121. /// <param name="sequenceNumber">Sequence number of the packet to
  122. /// acknowledge</param>
  123. /// <remarks>The does not immediately remove the packet, it only queues the removal
  124. /// so it can be handled in a thread safe way later</remarks>
  125. public void Remove(uint sequenceNumber)
  126. {
  127. m_pendingRemoves.Enqueue(sequenceNumber);
  128. }
  129. /// <summary>
  130. /// Returns a list of all of the packets with a TickCount older than
  131. /// the specified timeout
  132. /// </summary>
  133. /// <remarks>
  134. /// This function is not thread safe, and cannot be called
  135. /// multiple times concurrently
  136. /// </remarks>
  137. /// <param name="timeoutMS">Number of ticks (milliseconds) before a
  138. /// packet is considered expired
  139. /// </param>
  140. /// <returns>
  141. /// A list of all expired packets according to the given
  142. /// expiration timeout
  143. /// </returns>
  144. public List<OutgoingPacket> GetExpiredPackets(int timeoutMS)
  145. {
  146. ProcessQueues();
  147. List<OutgoingPacket> expiredPackets = null;
  148. bool doolder = true;
  149. if (m_packets.Count > 0)
  150. {
  151. int now = Environment.TickCount & Int32.MaxValue;
  152. foreach (OutgoingPacket packet in m_packets.Values)
  153. {
  154. if(packet.Buffer == null)
  155. {
  156. Remove(packet.SequenceNumber);
  157. continue;
  158. }
  159. if(doolder)
  160. {
  161. m_older = packet.SequenceNumber;
  162. doolder = false;
  163. }
  164. // TickCount of zero means a packet is in the resend queue
  165. // but hasn't actually been sent over the wire yet
  166. int ptime = Interlocked.Exchange(ref packet.TickCount, 0);
  167. if (ptime == 0)
  168. continue;
  169. if(now - ptime < timeoutMS)
  170. {
  171. int t = Interlocked.Exchange(ref packet.TickCount, ptime);
  172. if (t > ptime)
  173. Interlocked.Exchange(ref packet.TickCount, t);
  174. continue;
  175. }
  176. if (expiredPackets == null)
  177. expiredPackets = new List<OutgoingPacket>();
  178. // As with other network applications, assume that an expired packet is
  179. // an indication of some network problem, slow transmission
  180. packet.Client.FlowThrottle.ExpirePackets(1);
  181. expiredPackets.Add(packet);
  182. }
  183. }
  184. // if (expiredPackets != null)
  185. // m_log.DebugFormat("[UNACKED PACKET COLLECTION]: Found {0} expired packets on timeout of {1}", expiredPackets.Count, timeoutMS);
  186. return expiredPackets;
  187. }
  188. private void ProcessQueues()
  189. {
  190. while (m_pendingRemoves.TryDequeue(out uint pendingRemove))
  191. {
  192. if (m_packets.TryGetValue(pendingRemove, out OutgoingPacket removedPacket))
  193. {
  194. m_packets.Remove(pendingRemove);
  195. if (removedPacket != null && removedPacket.Buffer != null)
  196. {
  197. // Update stats
  198. Interlocked.Add(ref removedPacket.Client.UnackedBytes, -removedPacket.Buffer.DataLength);
  199. removedPacket.Client.FreeUDPBuffer(removedPacket.Buffer);
  200. removedPacket.Buffer = null;
  201. }
  202. }
  203. }
  204. // Process all the pending adds
  205. while (m_pendingAdds.TryDequeue(out OutgoingPacket pendingAdd))
  206. {
  207. if (pendingAdd != null)
  208. m_packets[pendingAdd.SequenceNumber] = pendingAdd;
  209. }
  210. // Process all the pending removes, including updating statistics and round-trip times
  211. while (m_pendingAcknowledgements.TryDequeue(out PendingAck pendingAcknowledgement))
  212. {
  213. //m_log.DebugFormat("[UNACKED PACKET COLLECTION]: Processing ack {0}", pendingAcknowledgement.SequenceNumber);
  214. if (m_packets.TryGetValue(pendingAcknowledgement.SequenceNumber, out OutgoingPacket ackedPacket))
  215. {
  216. m_packets.Remove(pendingAcknowledgement.SequenceNumber);
  217. if (ackedPacket != null)
  218. {
  219. // Update stats
  220. if(ackedPacket.Buffer != null)
  221. {
  222. Interlocked.Add(ref ackedPacket.Client.UnackedBytes, -ackedPacket.Buffer.DataLength);
  223. ackedPacket.Client.FreeUDPBuffer(ackedPacket.Buffer);
  224. ackedPacket.Buffer = null;
  225. }
  226. // As with other network applications, assume that an acknowledged packet is an
  227. // indication that the network can handle a little more load, speed up the transmission
  228. ackedPacket.Client.FlowThrottle.AcknowledgePackets(1);
  229. }
  230. }
  231. }
  232. }
  233. }
  234. }