Re: [Codel] [PATCH net-next] codel: use Newton method instead of sqrt() and divides

[Andrew McGregor <andrewmcgr@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 869 bytes --]

(netdev and linux developers removed from the cc: list)

Here's what I believe to be a matching patch for ns-3.

Unlike the first version, this should compile even if ns-3 has not been built first.

It includes a bunch of trace sources, allowing graphing of sojourn times and queue occupancy, for example.

Attach a CoDelQueue to a point-to-point interface (or anything that supports the SetQueue API) like this (C++ version, Python should be obvious):

      bottleneckchannel.SetQueue ("ns3::CoDelQueue",
                                  "Interval", StringValue(CoDelInterval),
                                  "Target", StringValue(CoDelTarget)
                                  );

As an example, a trace path for bytesInQueue will look something like "/NodeList/*/DeviceList/*/$ns3::PointToPointNetDevice/TxQueue/$ns3::CoDelQueue/bytesInQueue"


[-- Attachment #1.2: ns-3-codel.patch --]
[-- Type: application/octet-stream, Size: 18580 bytes --]

diff -r 2a669a0c452e -r a00e9e71bb24 src/network/utils/codel-queue.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/network/utils/codel-queue.cc	Mon May 14 17:35:24 2012 +1200
@@ -0,0 +1,476 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Andrew McGregor
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+ * Codel, the COntrolled DELay Queueing discipline
+ * Based on ns2 simulation code presented by Kathie Nichols
+ *
+ * This port based on linux kernel code by
+ * Authors:	Dave Täht <d@taht.net>
+ *		Eric Dumazet <edumazet@google.com>
+ *
+ * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
+*/
+
+#include "ns3/log.h"
+#include "ns3/enum.h"
+#include "ns3/uinteger.h"
+#include "ns3/abort.h"
+#include "codel-queue.h"
+
+NS_LOG_COMPONENT_DEFINE ("CoDelQueue");
+
+namespace ns3 {
+
+#define BITS_PER_LONG (8 * sizeof (unsigned long))
+
+/* borrowed from the linux kernel */
+#define do_div(n,base)						\
+({								\
+	int __res;						\
+	__res = ((unsigned long)n) % (unsigned int)base;	\
+	n = ((unsigned long)n) / (unsigned int)base;		\
+	__res;							\
+})
+
+static inline uint32_t reciprocal_divide(uint32_t A, uint32_t R)
+{
+	return (uint32_t)(((uint64_t)A * R) >> 32);
+}
+
+/* end kernel borrowings */
+
+static codel_time_t codel_get_time(void)
+{
+  Time time = Simulator::Now ();
+  uint64_t ns = time.GetNanoSeconds ();
+
+  return ns >> CODEL_SHIFT;
+}
+
+#define codel_time_after(a, b)	 ((int)(a) - (int)(b) > 0)
+#define codel_time_after_eq(a, b) ((int)(a) - (int)(b) >= 0)
+#define codel_time_before(a, b)	 ((int)(a) - (int)(b) < 0)
+#define codel_time_before_eq(a, b) ((int)(a) - (int)(b) <= 0)
+
+#define NSEC_PER_MSEC 1000000
+#define NSEC_PER_USEC 1000
+#define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
+#define US2TIME(a) ((a * NSEC_PER_USEC) >> CODEL_SHIFT)
+#define NS2TIME(a) ((a) >> CODEL_SHIFT)
+#define TIME2CODEL(a) NS2TIME(a.GetNanoSeconds())
+
+#define DEFAULT_CODEL_LIMIT 1000
+
+
+class CoDelTimestampTag : public Tag
+{
+public:
+  CoDelTimestampTag ();
+  static TypeId GetTypeId (void);
+  virtual TypeId GetInstanceTypeId (void) const;
+
+  virtual uint32_t GetSerializedSize (void) const;
+  virtual void Serialize (TagBuffer i) const;
+  virtual void Deserialize (TagBuffer i);
+  virtual void Print (std::ostream &os) const;
+
+  Time GetTxTime (void) const;
+private:
+  uint64_t m_creationTime;
+};
+
+CoDelTimestampTag::CoDelTimestampTag ()
+  : m_creationTime (Simulator::Now ().GetTimeStep ())
+{
+}
+
+TypeId
+CoDelTimestampTag::GetTypeId (void)
+{
+  static TypeId tid = TypeId ("anon::CoDelTimestampTag")
+    .SetParent<Tag> ()
+    .AddConstructor<CoDelTimestampTag> ()
+    .AddAttribute ("CreationTime",
+                   "The time at which the timestamp was created",
+                   StringValue ("0.0s"),
+                   MakeTimeAccessor (&CoDelTimestampTag::GetTxTime),
+                   MakeTimeChecker ())
+  ;
+  return tid;
+}
+TypeId
+CoDelTimestampTag::GetInstanceTypeId (void) const
+{
+  return GetTypeId ();
+}
+
+uint32_t
+CoDelTimestampTag::GetSerializedSize (void) const
+{
+  return 8;
+}
+void
+CoDelTimestampTag::Serialize (TagBuffer i) const
+{
+  i.WriteU64 (m_creationTime);
+}
+void
+CoDelTimestampTag::Deserialize (TagBuffer i)
+{
+  m_creationTime = i.ReadU64 ();
+}
+void
+CoDelTimestampTag::Print (std::ostream &os) const
+{
+  os << "CreationTime=" << m_creationTime;
+}
+Time
+CoDelTimestampTag::GetTxTime (void) const
+{
+  return TimeStep (m_creationTime);
+}
+
+NS_OBJECT_ENSURE_REGISTERED (CoDelQueue);
+
+TypeId CoDelQueue::GetTypeId (void) 
+{
+  static TypeId tid = TypeId ("ns3::CoDelQueue")
+    .SetParent<Queue> ()
+    .AddConstructor<CoDelQueue> ()
+    .AddAttribute ("Mode", 
+                   "Whether to use Bytes (see MaxBytes) or Packets (see MaxPackets) as the maximum queue size metric.",
+                   EnumValue (PACKETS),
+                   MakeEnumAccessor (&CoDelQueue::SetMode),
+                   MakeEnumChecker (BYTES, "Bytes",
+                                    PACKETS, "Packets"))
+    .AddAttribute ("MaxPackets", 
+                   "The maximum number of packets accepted by this CoDelQueue.",
+                   UintegerValue (DEFAULT_CODEL_LIMIT),
+                   MakeUintegerAccessor (&CoDelQueue::m_maxPackets),
+                   MakeUintegerChecker<uint32_t> ())
+    .AddAttribute ("MaxBytes", 
+                   "The maximum number of bytes accepted by this CoDelQueue.",
+                   UintegerValue (1500*DEFAULT_CODEL_LIMIT),
+                   MakeUintegerAccessor (&CoDelQueue::m_maxBytes),
+                   MakeUintegerChecker<uint32_t> ())
+    .AddAttribute ("MinBytes", 
+                   "The CoDel algorithm minbytes parameter.",
+                   UintegerValue (1500),
+                   MakeUintegerAccessor (&CoDelQueue::m_minbytes),
+                   MakeUintegerChecker<uint32_t> ())
+    .AddAttribute ("Interval",
+                   "The CoDel algorithm interval",
+                   StringValue ("100ms"),
+                   MakeTimeAccessor (&CoDelQueue::m_Interval),
+                   MakeTimeChecker ())
+    .AddAttribute ("Target",
+                   "The CoDel algorithm target queue delay",
+                   StringValue ("5ms"),
+                   MakeTimeAccessor (&CoDelQueue::m_Target),
+                   MakeTimeChecker ())
+    .AddTraceSource("count",
+                    "CoDel count",
+                    MakeTraceSourceAccessor(&CoDelQueue::m_count))
+    .AddTraceSource("drop_count",
+                    "CoDel drop count",
+                    MakeTraceSourceAccessor(&CoDelQueue::m_drop_count))
+    .AddTraceSource("bytesInQueue",
+                    "Number of bytes in the queue",
+                    MakeTraceSourceAccessor(&CoDelQueue::m_bytesInQueue))
+  ;
+
+  return tid;
+}
+
+CoDelQueue::CoDelQueue () :
+  Queue (),
+  m_packets (),
+  m_maxBytes(),
+  m_bytesInQueue(0),
+  m_count(0),
+  m_drop_count(0),
+  m_dropping(false),
+  m_rec_inv_sqrt(~0U >> REC_INV_SQRT_SHIFT),
+  m_first_above_time(0),
+  m_drop_next(0),
+  m_state1(0),
+  m_state2(0),
+  m_state3(0),
+  m_states(0),
+  m_drop_overlimit(0)  
+{
+  NS_LOG_FUNCTION_NOARGS ();
+}
+
+CoDelQueue::~CoDelQueue ()
+{
+  NS_LOG_FUNCTION_NOARGS ();
+}
+
+void
+CoDelQueue::NewtonStep(void)
+{
+  uint32_t invsqrt = ((uint32_t) m_rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
+  uint32_t invsqrt2 = ((uint64_t) invsqrt*invsqrt) >> 32;
+  uint64_t val = (3ll<<32) - ((uint64_t) m_count * invsqrt2);
+
+  val >>= 2; /* avoid overflow */
+  val = (val * invsqrt) >> (32-2+1);
+  m_rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
+}
+
+codel_time_t 
+CoDelQueue::ControlLaw(codel_time_t t)
+{
+  return t + reciprocal_divide(TIME2CODEL(m_Interval), m_rec_inv_sqrt << REC_INV_SQRT_SHIFT);
+}
+
+void
+CoDelQueue::SetMode (enum Mode mode)
+{
+  NS_LOG_FUNCTION (mode);
+  m_mode = mode;
+}
+
+CoDelQueue::Mode
+CoDelQueue::GetMode (void)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+  return m_mode;
+}
+
+bool 
+CoDelQueue::DoEnqueue (Ptr<Packet> p)
+{
+  NS_LOG_FUNCTION (this << p);
+
+  if (m_mode == PACKETS && (m_packets.size () >= m_maxPackets))
+    {
+      NS_LOG_LOGIC ("Queue full (at max packets) -- droppping pkt");
+      Drop (p);
+      ++m_drop_overlimit;
+      return false;
+    }
+
+  if (m_mode == BYTES && (m_bytesInQueue + p->GetSize () >= m_maxBytes))
+    {
+      NS_LOG_LOGIC ("Queue full (packet would exceed max bytes) -- droppping pkt");
+      Drop (p);
+      ++m_drop_overlimit;
+      return false;
+    }
+
+  CoDelTimestampTag tag;
+  p->AddByteTag (tag);
+  m_bytesInQueue += p->GetSize ();
+  m_packets.push (p);
+
+  NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+  NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+  return true;
+}
+
+bool
+CoDelQueue::ShouldDrop(Ptr<Packet> p, codel_time_t now)
+{
+  CoDelTimestampTag tag;
+  bool found;
+  bool drop;
+  found = p->FindFirstMatchingByteTag (tag);
+  Time delta = Simulator::Now () - tag.GetTxTime ();
+  NS_LOG_INFO ("Sojourn time "<<delta.GetSeconds ());
+  codel_time_t sojourn_time = TIME2CODEL(delta);
+  
+  if (codel_time_before(sojourn_time, TIME2CODEL(m_Target)) || 
+      m_bytesInQueue < m_minbytes)
+    {
+      /* went below so we'll stay below for at least q->interval */
+      m_first_above_time = 0;
+      return false;
+    }
+  drop = false;
+  if (m_first_above_time == 0) 
+    {
+      /* just went above from below. If we stay above
+       * for at least q->interval we'll say it's ok to drop
+       */
+      m_first_above_time = now + TIME2CODEL(m_Interval);
+    } 
+  else 
+    if (codel_time_after(now, m_first_above_time)) 
+      {
+        drop = true;
+        ++m_state1;
+      }
+  return drop;
+}
+
+Ptr<Packet>
+CoDelQueue::DoDequeue (void)
+{
+  NS_LOG_FUNCTION (this);
+
+  if (m_packets.empty ())
+    {
+      m_dropping = false;
+      m_first_above_time = 0;
+      NS_LOG_LOGIC ("Queue empty");
+      return 0;
+    }
+  codel_time_t now = codel_get_time();
+  Ptr<Packet> p = m_packets.front ();
+  m_packets.pop ();
+  m_bytesInQueue -= p->GetSize ();
+
+  NS_LOG_LOGIC ("Popped " << p);
+  NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+  NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+  bool drop = ShouldDrop(p, now);
+  if (m_dropping)
+    {
+      if (!drop)
+        {
+          /* sojourn time below target - leave dropping state */    
+          m_dropping = false;
+        }
+      else
+        if (codel_time_after_eq(now, m_drop_next))
+          {
+            m_state2++;
+            /* It's time for the next drop. Drop the current
+             * packet and dequeue the next. The dequeue might 
+             * take us out of dropping state. 
+             * If not, schedule the next drop.
+             * A large backlog might result in drop rates so high
+             * that the next drop should happen now, 
+             * hence the while loop.
+             */  
+            while (m_dropping && 
+                   codel_time_after_eq(now, m_drop_next)) {
+              Drop(p);
+              ++m_drop_count;
+              ++m_count;
+              NewtonStep();
+              if (m_packets.empty ())
+                {
+                  m_dropping = false;
+                  NS_LOG_LOGIC ("Queue empty");
+                  ++m_states;
+                  return 0;
+                }
+              p = m_packets.front ();
+              m_packets.pop ();
+              m_bytesInQueue -= p->GetSize ();
+
+              NS_LOG_LOGIC ("Popped " << p);
+              NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+              NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+              if (!ShouldDrop(p, now)) 
+                {
+                  /* leave dropping state */
+                  m_dropping = false;
+                }
+              else 
+                {
+                  /* and schedule the next drop */
+                  m_drop_next = ControlLaw(m_drop_next);
+                }
+            }
+          }
+    } 
+  else 
+    if (drop &&
+        (codel_time_before(now - m_drop_next,
+                           TIME2CODEL(m_Interval)) ||
+         codel_time_after_eq(now - m_first_above_time,
+                             TIME2CODEL(m_Interval)))) 
+      {
+        Drop(p);
+        ++m_drop_count;
+
+        NS_LOG_LOGIC ("Popped " << p);
+        NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+        NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+        drop = ShouldDrop(p, now);
+        m_dropping = true;
+        ++m_state3;
+        /* 
+         * if min went above target close to when we last went below it
+         * assume that the drop rate that controlled the queue on the
+         * last cycle is a good starting point to control it now.
+         */
+        if (codel_time_after(now - m_drop_next, TIME2CODEL(m_Interval))) 
+          {
+            //uint32_t c = m_count - 2;
+            //m_count = std::max(1U, c);
+            m_count = m_count>2U? (uint32_t)m_count-2U:1U;
+            NewtonStep();
+          } 
+        else
+          {
+            m_count = 1;
+            m_rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
+          }
+        m_drop_next = ControlLaw(now);
+      }
+  ++m_states;
+  return p;
+}
+
+uint32_t
+CoDelQueue::GetQueueSize (void)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+  if (GetMode () == BYTES)
+    {
+      return m_bytesInQueue;
+    }
+  else if (GetMode () == PACKETS)
+    {
+      return m_packets.size ();
+    }
+  else
+    {
+      NS_ABORT_MSG ("Unknown mode.");
+    }
+}
+
+Ptr<const Packet>
+CoDelQueue::DoPeek (void) const
+{
+  NS_LOG_FUNCTION (this);
+
+  if (m_packets.empty ())
+    {
+      NS_LOG_LOGIC ("Queue empty");
+      return 0;
+    }
+
+  Ptr<Packet> p = m_packets.front ();
+
+  NS_LOG_LOGIC ("Number packets " << m_packets.size ());
+  NS_LOG_LOGIC ("Number bytes " << m_bytesInQueue);
+
+  return p;
+}
+
+} // namespace ns3
+
diff -r 2a669a0c452e -r a00e9e71bb24 src/network/utils/codel-queue.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/network/utils/codel-queue.h	Mon May 14 17:35:24 2012 +1200
@@ -0,0 +1,126 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 Andrew McGregor
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * 
+ * Codel, the COntrolled DELay Queueing discipline
+ * Based on ns2 simulation code presented by Kathie Nichols
+ *
+ * This port based on linux kernel code by
+ * Authors:	Dave Täht <d@taht.net>
+ *		Eric Dumazet <edumazet@google.com>
+ *
+ * Ported to ns-3 by: Andrew McGregor <andrewmcgr@gmail.com>
+ */
+
+#ifndef CODEL_H
+#define CODEL_H
+
+#include <queue>
+#include "ns3/packet.h"
+#include "ns3/queue.h"
+#include "ns3/nstime.h"
+#include "ns3/simulator.h"
+#include "ns3/string.h"
+#include "ns3/traced-value.h"
+#include "ns3/trace-source-accessor.h"
+
+namespace ns3 {
+
+typedef uint32_t codel_time_t;
+typedef uint16_t rec_inv_sqrt_t;
+
+#define CODEL_SHIFT 10
+#define REC_INV_SQRT_BITS (8*sizeof(rec_inv_sqrt_t))
+#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
+
+class TraceContainer;
+
+/**
+ * \ingroup queue
+ *
+ * \brief A FIFO packet queue that drops tail-end packets on overflow
+ */
+class CoDelQueue : public Queue {
+public:
+  static TypeId GetTypeId (void);
+  /**
+   * \brief CoDelQueue Constructor
+   *
+   * Creates a codel queue with a maximum size of 100 packets by default
+   */
+  CoDelQueue ();
+
+  virtual ~CoDelQueue();
+
+  /**
+   * Enumeration of the modes supported in the class.
+   *
+   */
+  enum Mode {
+    ILLEGAL,     /**< Mode not set */
+    PACKETS,     /**< Use number of packets for maximum queue size */
+    BYTES,       /**< Use number of bytes for maximum queue size */
+  };
+
+  /**
+   * Set the operating mode of this device.
+   *
+   * \param mode The operating mode of this device.
+   *
+   */
+  void SetMode (CoDelQueue::Mode mode);
+
+  /**
+   * Get the encapsulation mode of this device.
+   *
+   * \returns The encapsulation mode of this device.
+   */
+  CoDelQueue::Mode  GetMode (void);
+
+  uint32_t GetQueueSize (void);
+
+private:
+  virtual bool DoEnqueue (Ptr<Packet> p);
+  virtual Ptr<Packet> DoDequeue (void);
+  virtual Ptr<const Packet> DoPeek (void) const;
+  void NewtonStep(void);
+  codel_time_t ControlLaw(codel_time_t t);
+  bool ShouldDrop(Ptr<Packet> p, codel_time_t now);
+
+  std::queue<Ptr<Packet> > m_packets;
+  uint32_t m_maxPackets;
+  uint32_t m_maxBytes;
+  TracedValue<uint32_t> m_bytesInQueue;
+  uint32_t m_minbytes;
+  Time m_Interval;
+  Time m_Target;
+  TracedValue<uint32_t> m_count;
+  TracedValue<uint32_t> m_drop_count;
+  bool m_dropping;
+  uint16_t m_rec_inv_sqrt;
+  codel_time_t m_first_above_time;
+  codel_time_t m_drop_next;
+  uint32_t m_state1;
+  uint32_t m_state2;
+  uint32_t m_state3;
+  uint32_t m_states;
+  uint32_t m_drop_overlimit;
+  Mode     m_mode;
+};
+
+} // namespace ns3
+
+#endif /* CODEL_H */
diff -r 2a669a0c452e -r a00e9e71bb24 src/network/wscript
--- a/src/network/wscript	Sun Apr 08 23:03:34 2012 -0700
+++ b/src/network/wscript	Mon May 14 17:35:24 2012 +1200
@@ -24,6 +24,7 @@
         'model/tag-buffer.cc',
         'model/trailer.cc',
 	'utils/address-utils.cc',
+        'utils/codel-queue.cc',
         'utils/data-rate.cc',
         'utils/drop-tail-queue.cc',
         'utils/error-model.cc',
@@ -93,6 +94,7 @@
         'model/tag-buffer.h',
         'model/trailer.h',
       	'utils/address-utils.h',
+        'utils/codel-queue.h',
         'utils/data-rate.h',
         'utils/drop-tail-queue.h',
         'utils/error-model.h',

[-- Attachment #1.3: Type: text/plain, Size: 5414 bytes --]



On 13/05/2012, at 7:23 PM, Eric Dumazet wrote:

> From: Eric Dumazet <edumazet@google.com>
> 
> On Sat, 2012-05-12 at 17:52 -0400, David Miller wrote:
> 
>> Ok, fair enough.
> 
> Oh well, I sent my mail too late. The error made no sense after a good
> night. Also, when Van says something, you can be fairly sure its right,
> and if it's not, then you didn't understand what Van said ;)
> 
> 16bit precision is OK, once the maths are correctly done in the userland
> program I wrote yesterday...
> 
> count=16525, precision=16 bits, sqrt(scaled_count)=4113, reciprocal(sq)=1fde240, Newton=1fd0000
>  interval/sqrt(16525) = 
> 	777909 (float compute)  // (u32)(interval/sqrt(count))
> 	778020 (integer approx) // reciprocal_divide(interval, rec)
> 	777926 (int_sqrt_div)   // int_sqrt_div(interval, count)
> 	776672 (Newton approx)  // reciprocal_divide(interval, previnv << shift)
> 
> count=9889134, precision=16 bits, sqrt(scaled_count)=50315,
> reciprocal(sq)=14d720, Newton=140000
>  interval/sqrt(9889134) = 
> 	31799 (float compute)
> 	31799 (integer approx)
> 	31799 (int_sqrt_div)
> 	30517 (Newton approx)
> 
> 
> And kernel code using u16 :
> 
> 6a1:	0f b7 72 0a          	movzwl 0xa(%rdx),%esi
> 6a5:	8b 3a                	mov    (%rdx),%edi
> 6a7:	83 c7 01             	add    $0x1,%edi
> 6aa:	c1 e6 10             	shl    $0x10,%esi
> 6ad:	89 3a                	mov    %edi,(%rdx)  vars->count++
> 6af:	89 ff                	mov    %edi,%edi
> 6b1:	89 f6                	mov    %esi,%esi
> 6b3:	48 89 f1             	mov    %rsi,%rcx
> 6b6:	48 0f af ce          	imul   %rsi,%rcx
> 6ba:	48 c1 e9 20          	shr    $0x20,%rcx
> 6be:	48 0f af cf          	imul   %rdi,%rcx
> 6c2:	48 bf 00 00 00 00 03 	mov    $0x300000000,%rdi
> 6c9:	00 00 00 
> 6cc:	48 29 cf             	sub    %rcx,%rdi
> 6cf:	48 89 f9             	mov    %rdi,%rcx
> 6d2:	48 c1 e9 02          	shr    $0x2,%rcx
> 6d6:	48 0f af ce          	imul   %rsi,%rcx
> 6da:	48 c1 e9 2f          	shr    $0x2f,%rcx
> 6de:	66 89 4a 0a          	mov    %cx,0xa(%rdx)
> 
> 
> Fell free to add following cleanup patch, if you like it ;)
> 
> Thanks
> 
> [PATCH net-next] codel: use u16 field instead of 31bits for rec_inv_sqrt
> 
> David pointed out gcc might generate poor code with 31bit fields.
> 
> Using u16 is more than enough and permits a better code output.
> 
> Also make the code intent more readable using constants, fixed point arithmetic
> not being trivial for everybody.
> 
> Suggested-by: David Miller <davem@davemloft.net>
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> ---
> include/net/codel.h |   25 +++++++++++++++----------
> 1 file changed, 15 insertions(+), 10 deletions(-)
> 
> diff --git a/include/net/codel.h b/include/net/codel.h
> index bd8747c..7546517 100644
> --- a/include/net/codel.h
> +++ b/include/net/codel.h
> @@ -133,13 +133,17 @@ struct codel_params {
> struct codel_vars {
> 	u32		count;
> 	u32		lastcount;
> -	bool		dropping:1;
> -	u32		rec_inv_sqrt:31;
> +	bool		dropping;
> +	u16		rec_inv_sqrt;
> 	codel_time_t	first_above_time;
> 	codel_time_t	drop_next;
> 	codel_time_t	ldelay;
> };
> 
> +#define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */
> +/* needed shift to get a Q0.32 number from rec_inv_sqrt */
> +#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
> +
> /**
>  * struct codel_stats - contains codel shared variables and stats
>  * @maxpacket:	largest packet we've seen so far
> @@ -173,17 +177,18 @@ static void codel_stats_init(struct codel_stats *stats)
>  * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
>  * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
>  *
> - * Here, invsqrt is a fixed point number (< 1.0), 31bit mantissa)
> + * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
>  */
> static void codel_Newton_step(struct codel_vars *vars)
> {
> -	u32 invsqrt = vars->rec_inv_sqrt;
> -	u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 31;
> -	u64 val = (3LL << 31) - ((u64)vars->count * invsqrt2);
> +	u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
> +	u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
> +	u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
> 
> -	val = (val * invsqrt) >> 32;
> +	val >>= 2; /* avoid overflow in following multiply */
> +	val = (val * invsqrt) >> (32 - 2 + 1);
> 
> -	vars->rec_inv_sqrt = val;
> +	vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
> }
> 
> /*
> @@ -195,7 +200,7 @@ static codel_time_t codel_control_law(codel_time_t t,
> 				      codel_time_t interval,
> 				      u32 rec_inv_sqrt)
> {
> -	return t + reciprocal_divide(interval, rec_inv_sqrt << 1);
> +	return t + reciprocal_divide(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
> }
> 
> 
> @@ -326,7 +331,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
> 			codel_Newton_step(vars);
> 		} else {
> 			vars->count = 1;
> -			vars->rec_inv_sqrt = 0x7fffffff;
> +			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> 		}
> 		vars->lastcount = vars->count;
> 		vars->drop_next = codel_control_law(now, params->interval,
> 
> 
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel


[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2330 bytes --]