From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <andrewmcgr@gmail.com>
Received: from mail-pb0-f43.google.com (mail-pb0-f43.google.com
	[209.85.160.43]) (using TLSv1 with cipher RC4-MD5 (128/128 bits))
	(Client CN "smtp.gmail.com",
	Issuer "Google Internet Authority" (verified OK))
	by huchra.bufferbloat.net (Postfix) with ESMTPS id D23B6200B29
	for <codel@lists.bufferbloat.net>; Sun, 13 May 2012 22:46:57 -0700 (PDT)
Received: by pbcwz7 with SMTP id wz7so10121443pbc.16
	for <codel@lists.bufferbloat.net>; Sun, 13 May 2012 22:46:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=subject:mime-version:content-type:from:in-reply-to:date:cc
	:message-id:references:to:x-mailer;
	bh=GZ/vte7JdM7S+EK5uwqcIOzwxW13skl44g52p6FTTAg=;
	b=Afwg9jqbyDBlwTj16w+EIL2fF455Qf+ZQWp/YXwkNZedHzTeMBp7nolVafe1B54fmp
	U85MLKvK36R8jZVPhqB08PkDNyKoPitq1dSFcHHcQXFKitjGDvz9mndZmDO+lgRY2QrL
	ACQlf0U3NWwJ92EHj7yV/nhVRTzIGfEGA52L7bUCZXF6ugQBPHf6UZDdYJBxC1qJoRup
	tDYzJlVWixyWTjZUBXHjXd3CkgRH0TjeE8fEyij+tCmS0NK+DRXaSlwP6JJLmfvEMS4N
	09A4aLZf+N75GBB8Rqz8uGkjxOM46vkhmQogXLXrVzYxgDu55xf9VshAzWL+yTECwsGV
	0fww==
Received: by 10.68.138.196 with SMTP id qs4mr1513132pbb.149.1336974416919;
	Sun, 13 May 2012 22:46:56 -0700 (PDT)
Received: from andrewm-lo.ws.atlnz.lc (gate1.alliedtelesyn.co.nz.
	[202.49.72.36])
	by mx.google.com with ESMTPS id ub8sm3600906pbc.44.2012.05.13.22.46.52
	(version=TLSv1/SSLv3 cipher=OTHER);
	Sun, 13 May 2012 22:46:55 -0700 (PDT)
Mime-Version: 1.0 (Apple Message framework v1278)
Content-Type: multipart/signed;
	boundary="Apple-Mail=_865BBF00-8DFB-4F87-BC65-3DA8731CABA2";
	protocol="application/pkcs7-signature"; micalg=sha1
From: Andrew McGregor <andrewmcgr@gmail.com>
In-Reply-To: <1336893803.8512.43.camel@edumazet-glaptop>
Date: Mon, 14 May 2012 17:46:48 +1200
Message-Id: <AE51D0C6-6ED2-42E3-A8E2-41572E187D07@gmail.com>
References: <1336855256.31653.1329.camel@edumazet-glaptop>
	<20120512.164513.1156706853054390966.davem@davemloft.net>
	<1336859324.31653.1385.camel@edumazet-glaptop>
	<20120512.175217.1632102067268101115.davem@davemloft.net>
	<1336893803.8512.43.camel@edumazet-glaptop>
To: Eric Dumazet <eric.dumazet@gmail.com>
X-Mailer: Apple Mail (2.1278)
Cc: Nandita Dukkipati <nanditad@google.com>,
	Matt Mathis <mattmathis@google.com>, codel@lists.bufferbloat.net,
	ycheng@google.com, Dave Taht <dave.taht@bufferbloat.net>
Subject: Re: [Codel] [PATCH net-next] codel: use Newton method instead of
	sqrt() and divides
X-BeenThere: codel@lists.bufferbloat.net
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: CoDel AQM discussions <codel.lists.bufferbloat.net>
List-Unsubscribe: <https://lists.bufferbloat.net/options/codel>,
	<mailto:codel-request@lists.bufferbloat.net?subject=unsubscribe>
List-Archive: <https://lists.bufferbloat.net/pipermail/codel>
List-Post: <mailto:codel@lists.bufferbloat.net>
List-Help: <mailto:codel-request@lists.bufferbloat.net?subject=help>
List-Subscribe: <https://lists.bufferbloat.net/listinfo/codel>,
	<mailto:codel-request@lists.bufferbloat.net?subject=subscribe>
X-List-Received-Date: Mon, 14 May 2012 05:46:58 -0000


--Apple-Mail=_865BBF00-8DFB-4F87-BC65-3DA8731CABA2
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_FFC13AEF-3115-4EDF-9717-9B18B4D2BE6A"


--Apple-Mail=_FFC13AEF-3115-4EDF-9717-9B18B4D2BE6A
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

(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::CoDelQ=
ueue/bytesInQueue"


--Apple-Mail=_FFC13AEF-3115-4EDF-9717-9B18B4D2BE6A
Content-Disposition: attachment;
	filename=ns-3-codel.patch
Content-Type: application/octet-stream;
	name="ns-3-codel.patch"
Content-Transfer-Encoding: quoted-printable

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

--Apple-Mail=_FFC13AEF-3115-4EDF-9717-9B18B4D2BE6A
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii



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

> From: Eric Dumazet <edumazet@google.com>
>=20
> On Sat, 2012-05-12 at 17:52 -0400, David Miller wrote:
>=20
>> Ok, fair enough.
>=20
> 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 ;)
>=20
> 16bit precision is OK, once the maths are correctly done in the =
userland
> program I wrote yesterday...
>=20
> count=3D16525, precision=3D16 bits, sqrt(scaled_count)=3D4113, =
reciprocal(sq)=3D1fde240, Newton=3D1fd0000
>  interval/sqrt(16525) =3D=20
> 	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)
>=20
> count=3D9889134, precision=3D16 bits, sqrt(scaled_count)=3D50315,
> reciprocal(sq)=3D14d720, Newton=3D140000
>  interval/sqrt(9889134) =3D=20
> 	31799 (float compute)
> 	31799 (integer approx)
> 	31799 (int_sqrt_div)
> 	30517 (Newton approx)
>=20
>=20
> And kernel code using u16 :
>=20
> 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=20
> 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)
>=20
>=20
> Fell free to add following cleanup patch, if you like it ;)
>=20
> Thanks
>=20
> [PATCH net-next] codel: use u16 field instead of 31bits for =
rec_inv_sqrt
>=20
> David pointed out gcc might generate poor code with 31bit fields.
>=20
> Using u16 is more than enough and permits a better code output.
>=20
> Also make the code intent more readable using constants, fixed point =
arithmetic
> not being trivial for everybody.
>=20
> 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(-)
>=20
> 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;
> };
>=20
> +#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_m=
ethods_for_reciprocal_square_roots
>  * new_invsqrt =3D (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 =3D vars->rec_inv_sqrt;
> -	u32 invsqrt2 =3D ((u64)invsqrt * invsqrt) >> 31;
> -	u64 val =3D (3LL << 31) - ((u64)vars->count * invsqrt2);
> +	u32 invsqrt =3D ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
> +	u32 invsqrt2 =3D ((u64)invsqrt * invsqrt) >> 32;
> +	u64 val =3D (3LL << 32) - ((u64)vars->count * invsqrt2);
>=20
> -	val =3D (val * invsqrt) >> 32;
> +	val >>=3D 2; /* avoid overflow in following multiply */
> +	val =3D (val * invsqrt) >> (32 - 2 + 1);
>=20
> -	vars->rec_inv_sqrt =3D val;
> +	vars->rec_inv_sqrt =3D val >> REC_INV_SQRT_SHIFT;
> }
>=20
> /*
> @@ -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);
> }
>=20
>=20
> @@ -326,7 +331,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc =
*sch,
> 			codel_Newton_step(vars);
> 		} else {
> 			vars->count =3D 1;
> -			vars->rec_inv_sqrt =3D 0x7fffffff;
> +			vars->rec_inv_sqrt =3D ~0U >> =
REC_INV_SQRT_SHIFT;
> 		}
> 		vars->lastcount =3D vars->count;
> 		vars->drop_next =3D codel_control_law(now, =
params->interval,
>=20
>=20
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel


--Apple-Mail=_FFC13AEF-3115-4EDF-9717-9B18B4D2BE6A--

--Apple-Mail=_865BBF00-8DFB-4F87-BC65-3DA8731CABA2
Content-Disposition: attachment;
	filename=smime.p7s
Content-Type: application/pkcs7-signature;
	name=smime.p7s
Content-Transfer-Encoding: base64

MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIFLjCCBSow
ggQSoAMCAQICEQDMQ2ZKvgsUYA5oQg5SjWfVMA0GCSqGSIb3DQEBBQUAMIGTMQswCQYDVQQGEwJH
QjEbMBkGA1UECBMSR3JlYXRlciBNYW5jaGVzdGVyMRAwDgYDVQQHEwdTYWxmb3JkMRowGAYDVQQK
ExFDT01PRE8gQ0EgTGltaXRlZDE5MDcGA1UEAxMwQ09NT0RPIENsaWVudCBBdXRoZW50aWNhdGlv
biBhbmQgU2VjdXJlIEVtYWlsIENBMB4XDTExMTAwMTAwMDAwMFoXDTEyMDkzMDIzNTk1OVowJTEj
MCEGCSqGSIb3DQEJARYUYW5kcmV3bWNnckBnbWFpbC5jb20wggEiMA0GCSqGSIb3DQEBAQUAA4IB
DwAwggEKAoIBAQC+buTRxzSXTQmMyUqaokLJit3xU5WVudxHijhKbGRSTgJ867L/v8+rNhSoFwCV
MdKIu/M7apWgGkkA+MT/LjDFj63jLT+4nTTLIojXZdoezbpp/rQ2ViSbi54AjhZBQ5X+yH2xcXmG
KpDhZjeZC1bvKNvBtdOHCAcrx1Ys1BNj+AhwridEX/KD0cq5xSsJhjDggF6XSUOsaiqBHR6fiQMi
7gH8EuFBh83oklb/pdreg1fQ7gKJk/Me/atIbE1gtbIR88oaCtXoHfZxgkFwagwMtBHdkxN+wcZy
9xx78el9Lxrjx2nMq50hRlj/bqg/m4rSox7//DKfx7bfKNZAiSMDAgMBAAGjggHkMIIB4DAfBgNV
HSMEGDAWgBR6E04AdFvGeGNkJ8Ev4qBbvHnFezAdBgNVHQ4EFgQUXOXqNkq6sNbrD8B41dPko8Gs
JucwDgYDVR0PAQH/BAQDAgWgMAwGA1UdEwEB/wQCMAAwIAYDVR0lBBkwFwYIKwYBBQUHAwQGCysG
AQQBsjEBAwUCMBEGCWCGSAGG+EIBAQQEAwIFIDBGBgNVHSAEPzA9MDsGDCsGAQQBsjEBAgEBATAr
MCkGCCsGAQUFBwIBFh1odHRwczovL3NlY3VyZS5jb21vZG8ubmV0L0NQUzBXBgNVHR8EUDBOMEyg
SqBIhkZodHRwOi8vY3JsLmNvbW9kb2NhLmNvbS9DT01PRE9DbGllbnRBdXRoZW50aWNhdGlvbmFu
ZFNlY3VyZUVtYWlsQ0EuY3JsMIGIBggrBgEFBQcBAQR8MHowUgYIKwYBBQUHMAKGRmh0dHA6Ly9j
cnQuY29tb2RvY2EuY29tL0NPTU9ET0NsaWVudEF1dGhlbnRpY2F0aW9uYW5kU2VjdXJlRW1haWxD
QS5jcnQwJAYIKwYBBQUHMAGGGGh0dHA6Ly9vY3NwLmNvbW9kb2NhLmNvbTAfBgNVHREEGDAWgRRh
bmRyZXdtY2dyQGdtYWlsLmNvbTANBgkqhkiG9w0BAQUFAAOCAQEAgmf81vnsAnbcmIAyyqvEKxAK
jRHerfreN10DK1ISkUJ//U4uffQV8sAGDtyIErzVFsW6NYRmFCMSE20M1ffbFpWUmXCtm/YTlkf1
5STVjTMNshDzMDhpjx99Z2J5RBJPZpXjwmpQnfKwB7zft9TcUSIb9FvZm33EKdF/XlS12U4Q9fsj
2shZf88RituX2+fCWfHoTWiFEhFUkLRtWf1YpgHpEXr82nqROxs/aWNlqtLnwTTu2ULr/WpUaRDs
kom8gFZkMgw5kRfLpSXRrCFSORsZzkH2ooRxaJY7wMwZaCUS1am9DuwVy7gehoc3ZsjsDkMObZeu
kx7Cg7GxIkgo+zGCA64wggOqAgEBMIGpMIGTMQswCQYDVQQGEwJHQjEbMBkGA1UECBMSR3JlYXRl
ciBNYW5jaGVzdGVyMRAwDgYDVQQHEwdTYWxmb3JkMRowGAYDVQQKExFDT01PRE8gQ0EgTGltaXRl
ZDE5MDcGA1UEAxMwQ09NT0RPIENsaWVudCBBdXRoZW50aWNhdGlvbiBhbmQgU2VjdXJlIEVtYWls
IENBAhEAzENmSr4LFGAOaEIOUo1n1TAJBgUrDgMCGgUAoIIB2TAYBgkqhkiG9w0BCQMxCwYJKoZI
hvcNAQcBMBwGCSqGSIb3DQEJBTEPFw0xMjA1MTQwNTQ2NDlaMCMGCSqGSIb3DQEJBDEWBBTGOJ02
HircFkzPoT3glSEKRKaRODCBugYJKwYBBAGCNxAEMYGsMIGpMIGTMQswCQYDVQQGEwJHQjEbMBkG
A1UECBMSR3JlYXRlciBNYW5jaGVzdGVyMRAwDgYDVQQHEwdTYWxmb3JkMRowGAYDVQQKExFDT01P
RE8gQ0EgTGltaXRlZDE5MDcGA1UEAxMwQ09NT0RPIENsaWVudCBBdXRoZW50aWNhdGlvbiBhbmQg
U2VjdXJlIEVtYWlsIENBAhEAzENmSr4LFGAOaEIOUo1n1TCBvAYLKoZIhvcNAQkQAgsxgayggakw
gZMxCzAJBgNVBAYTAkdCMRswGQYDVQQIExJHcmVhdGVyIE1hbmNoZXN0ZXIxEDAOBgNVBAcTB1Nh
bGZvcmQxGjAYBgNVBAoTEUNPTU9ETyBDQSBMaW1pdGVkMTkwNwYDVQQDEzBDT01PRE8gQ2xpZW50
IEF1dGhlbnRpY2F0aW9uIGFuZCBTZWN1cmUgRW1haWwgQ0ECEQDMQ2ZKvgsUYA5oQg5SjWfVMA0G
CSqGSIb3DQEBAQUABIIBAH3aqbSep+dhgpw2tamltUW6q3zM5o32ILxlRc9SWLrlclZiUvAcKhdI
gNnQExVxw7mUBpteJS1VLqmYKxgjVijTqNMZ0pC0WF1lkJaoejSJPVXa82lQLgZ89iVt+N4bxVje
wJJw86zrajZQkBvnMTxQbNmTKTb00kE9OWTIhti6F+w8W1qYfGZXn3/9l9k2Nn8NvrOzTRhvuNE5
W+4DlaIzAs68ekKavordZbKEG+GiZThVUlSVJHu2sZYaWX2IUXGPzUkyrCiLPA+Gp6XnilnmKrYN
UYkXJRbuYIAe11eoT1zpi/v4uRnMWW8TLYWES4QxGkHNpdqloLk5ZjvLM74AAAAAAAA=

--Apple-Mail=_865BBF00-8DFB-4F87-BC65-3DA8731CABA2--