On Tue, May 02, 2017 at 19:19 +0200, Mike Belopuhov wrote:
> On Tue, May 02, 2017 at 11:14 -0600, Todd C. Miller wrote:
> > On Tue, 02 May 2017 11:12:58 -0600, "Todd C. Miller" wrote:
> >
> > > On Tue, 02 May 2017 18:59:44 +0200, Mike Belopuhov wrote:
> > >
> > > > After switching the ph_timestamp to int64_t, the implementation
> > > > can be re-adjusted to use int64_t timestamps throughout.
> > > >
> > > > I think I've got all of the conversion right, but will double-
> > > > check everything before getting this in.
> > >
> > > Would it be worth converting codel_intervals from us to ns so you
> > > don't need to multiply by 1000 in so many places?
> >
> > Nevermind, I see that most of codel is in terms of us not ns, so
> > it is probably simplest to leave it that way for now.
> >
> > - todd
>
> The trade off is basically the double the size of the table.
> It's a bit above 1.5Kb right now and if I convert everything
> to ns, it'll be just below 4K. Which is also OK I guess.
I think I'm wrong here, actually. I can still fit a reasonable
value into the uint32_t so that no extra memory is needed.
Like with the diff below (it requires some pfctl changes to talk
to the kernel in nanoseconds instead of microseconds).
Does this look better?
diff --git sys/net/fq_codel.c sys/net/fq_codel.c
index feaaf83201a..fd0283cfad4 100644
--- sys/net/fq_codel.c
+++ sys/net/fq_codel.c
@@ -165,57 +165,74 @@ static const unsigned int fqcodel_threshold = 64;
/*
* CoDel implementation
*/
/* Delay target, 5ms */
-static const unsigned int codel_target = 5000;
+static const int64_t codel_target = 5000000;
/* Grace period after last drop, 16 * 100ms RTT */
static const int64_t codel_grace = 1600000000;
-/* First 399 "100 / sqrt(x)" intervarls, us precision */
+/* First 399 "100 / sqrt(x)" intervarls, ns precision */
static const uint32_t codel_intervals[] = {
- 100000, 70711, 57735, 50000, 44721, 40825, 37796, 35355, 33333, 31623,
- 30151, 28868, 27735, 26726, 25820, 25000, 24254, 23570, 22942, 22361,
- 21822, 21320, 20851, 20412, 20000, 19612, 19245, 18898, 18570, 18257,
- 17961, 17678, 17408, 17150, 16903, 16667, 16440, 16222, 16013, 15811,
- 15617, 15430, 15250, 15076, 14907, 14744, 14586, 14434, 14286, 14142,
- 14003, 13868, 13736, 13608, 13484, 13363, 13245, 13131, 13019, 12910,
- 12804, 12700, 12599, 12500, 12403, 12309, 12217, 12127, 12039, 11952,
- 11868, 11785, 11704, 11625, 11547, 11471, 11396, 11323, 11251, 11180,
- 11111, 11043, 10976, 10911, 10847, 10783, 10721, 10660, 10600, 10541,
- 10483, 10426, 10370, 10314, 10260, 10206, 10153, 10102, 10050, 10000,
- 9950, 9901, 9853, 9806, 9759, 9713, 9667, 9623, 9578, 9535,
- 9492, 9449, 9407, 9366, 9325, 9285, 9245, 9206, 9167, 9129,
- 9091, 9054, 9017, 8980, 8944, 8909, 8874, 8839, 8805, 8771,
- 8737, 8704, 8671, 8639, 8607, 8575, 8544, 8513, 8482, 8452,
- 8422, 8392, 8362, 8333, 8305, 8276, 8248, 8220, 8192, 8165,
- 8138, 8111, 8085, 8058, 8032, 8006, 7981, 7956, 7931, 7906,
- 7881, 7857, 7833, 7809, 7785, 7762, 7738, 7715, 7692, 7670,
- 7647, 7625, 7603, 7581, 7559, 7538, 7516, 7495, 7474, 7454,
- 7433, 7412, 7392, 7372, 7352, 7332, 7313, 7293, 7274, 7255,
- 7236, 7217, 7198, 7180, 7161, 7143, 7125, 7107, 7089, 7071,
- 7053, 7036, 7019, 7001, 6984, 6967, 6950, 6934, 6917, 6901,
- 6884, 6868, 6852, 6836, 6820, 6804, 6788, 6773, 6757, 6742,
- 6727, 6712, 6696, 6682, 6667, 6652, 6637, 6623, 6608, 6594,
- 6580, 6565, 6551, 6537, 6523, 6509, 6496, 6482, 6468, 6455,
- 6442, 6428, 6415, 6402, 6389, 6376, 6363, 6350, 6337, 6325,
- 6312, 6299, 6287, 6275, 6262, 6250, 6238, 6226, 6214, 6202,
- 6190, 6178, 6166, 6155, 6143, 6131, 6120, 6108, 6097, 6086,
- 6075, 6063, 6052, 6041, 6030, 6019, 6008, 5998, 5987, 5976,
- 5965, 5955, 5944, 5934, 5923, 5913, 5903, 5893, 5882, 5872,
- 5862, 5852, 5842, 5832, 5822, 5812, 5803, 5793, 5783, 5774,
- 5764, 5754, 5745, 5735, 5726, 5717, 5707, 5698, 5689, 5680,
- 5670, 5661, 5652, 5643, 5634, 5625, 5617, 5608, 5599, 5590,
- 5581, 5573, 5564, 5556, 5547, 5538, 5530, 5522, 5513, 5505,
- 5496, 5488, 5480, 5472, 5464, 5455, 5447, 5439, 5431, 5423,
- 5415, 5407, 5399, 5392, 5384, 5376, 5368, 5361, 5353, 5345,
- 5338, 5330, 5322, 5315, 5307, 5300, 5293, 5285, 5278, 5270,
- 5263, 5256, 5249, 5241, 5234, 5227, 5220, 5213, 5206, 5199,
- 5192, 5185, 5178, 5171, 5164, 5157, 5150, 5143, 5137, 5130,
- 5123, 5116, 5110, 5103, 5096, 5090, 5083, 5077, 5070, 5064,
- 5057, 5051, 5044, 5038, 5032, 5025, 5019, 5013, 5006
+ 100000000, 70710678, 57735027, 50000000, 44721360, 40824829, 37796447,
+ 35355339, 33333333, 31622777, 30151134, 28867513, 27735010, 26726124,
+ 25819889, 25000000, 24253563, 23570226, 22941573, 22360680, 21821789,
+ 21320072, 20851441, 20412415, 20000000, 19611614, 19245009, 18898224,
+ 18569534, 18257419, 17960530, 17677670, 17407766, 17149859, 16903085,
+ 16666667, 16439899, 16222142, 16012815, 15811388, 15617376, 15430335,
+ 15249857, 15075567, 14907120, 14744196, 14586499, 14433757, 14285714,
+ 14142136, 14002801, 13867505, 13736056, 13608276, 13483997, 13363062,
+ 13245324, 13130643, 13018891, 12909944, 12803688, 12700013, 12598816,
+ 12500000, 12403473, 12309149, 12216944, 12126781, 12038585, 11952286,
+ 11867817, 11785113, 11704115, 11624764, 11547005, 11470787, 11396058,
+ 11322770, 11250879, 11180340, 11111111, 11043153, 10976426, 10910895,
+ 10846523, 10783277, 10721125, 10660036, 10599979, 10540926, 10482848,
+ 10425721, 10369517, 10314212, 10259784, 10206207, 10153462, 10101525,
+ 10050378, 10000000, 9950372, 9901475, 9853293, 9805807, 9759001,
+ 9712859, 9667365, 9622504, 9578263, 9534626, 9491580, 9449112,
+ 9407209, 9365858, 9325048, 9284767, 9245003, 9205746, 9166985,
+ 9128709, 9090909, 9053575, 9016696, 8980265, 8944272, 8908708,
+ 8873565, 8838835, 8804509, 8770580, 8737041, 8703883, 8671100,
+ 8638684, 8606630, 8574929, 8543577, 8512565, 8481889, 8451543,
+ 8421519, 8391814, 8362420, 8333333, 8304548, 8276059, 8247861,
+ 8219949, 8192319, 8164966, 8137885, 8111071, 8084521, 8058230,
+ 8032193, 8006408, 7980869, 7955573, 7930516, 7905694, 7881104,
+ 7856742, 7832604, 7808688, 7784989, 7761505, 7738232, 7715167,
+ 7692308, 7669650, 7647191, 7624929, 7602859, 7580980, 7559289,
+ 7537784, 7516460, 7495317, 7474351, 7453560, 7432941, 7412493,
+ 7392213, 7372098, 7352146, 7332356, 7312724, 7293250, 7273930,
+ 7254763, 7235746, 7216878, 7198158, 7179582, 7161149, 7142857,
+ 7124705, 7106691, 7088812, 7071068, 7053456, 7035975, 7018624,
+ 7001400, 6984303, 6967330, 6950480, 6933752, 6917145, 6900656,
+ 6884284, 6868028, 6851887, 6835859, 6819943, 6804138, 6788442,
+ 6772855, 6757374, 6741999, 6726728, 6711561, 6696495, 6681531,
+ 6666667, 6651901, 6637233, 6622662, 6608186, 6593805, 6579517,
+ 6565322, 6551218, 6537205, 6523281, 6509446, 6495698, 6482037,
+ 6468462, 6454972, 6441566, 6428243, 6415003, 6401844, 6388766,
+ 6375767, 6362848, 6350006, 6337243, 6324555, 6311944, 6299408,
+ 6286946, 6274558, 6262243, 6250000, 6237829, 6225728, 6213698,
+ 6201737, 6189845, 6178021, 6166264, 6154575, 6142951, 6131393,
+ 6119901, 6108472, 6097108, 6085806, 6074567, 6063391, 6052275,
+ 6041221, 6030227, 6019293, 6008418, 5997601, 5986843, 5976143,
+ 5965500, 5954913, 5944383, 5933908, 5923489, 5913124, 5902813,
+ 5892557, 5882353, 5872202, 5862104, 5852057, 5842062, 5832118,
+ 5822225, 5812382, 5802589, 5792844, 5783149, 5773503, 5763904,
+ 5754353, 5744850, 5735393, 5725983, 5716620, 5707301, 5698029,
+ 5688801, 5679618, 5670480, 5661385, 5652334, 5643326, 5634362,
+ 5625440, 5616560, 5607722, 5598925, 5590170, 5581456, 5572782,
+ 5564149, 5555556, 5547002, 5538488, 5530013, 5521576, 5513178,
+ 5504819, 5496497, 5488213, 5479966, 5471757, 5463584, 5455447,
+ 5447347, 5439283, 5431254, 5423261, 5415304, 5407381, 5399492,
+ 5391639, 5383819, 5376033, 5368281, 5360563, 5352877, 5345225,
+ 5337605, 5330018, 5322463, 5314940, 5307449, 5299989, 5292561,
+ 5285164, 5277798, 5270463, 5263158, 5255883, 5248639, 5241424,
+ 5234239, 5227084, 5219958, 5212860, 5205792, 5198752, 5191741,
+ 5184758, 5177804, 5170877, 5163978, 5157106, 5150262, 5143445,
+ 5136655, 5129892, 5123155, 5116445, 5109761, 5103104, 5096472,
+ 5089866, 5083286, 5076731, 5070201, 5063697, 5057217, 5050763,
+ 5044333, 5037927, 5031546, 5025189, 5018856, 5012547, 5006262
};
void
codel_initparams(struct codel_params *cp, unsigned int target,
unsigned int interval, int quantum)
@@ -226,24 +243,25 @@ codel_initparams(struct codel_params *cp, unsigned int
target,
/*
* Update tracking intervals according to the the user-supplied value
*/
if (interval > codel_intervals[0]) {
/* Select either specified target or 5% of an interval */
- cp->target = MAX(target, interval / 5) * 1000;
- cp->interval = interval * 1000;
+ cp->target = MAX(target, interval / 5);
+ cp->interval = interval;
- /* The coefficient is scaled up by a 1000 due to conversion */
- mult = cp->interval / codel_intervals[0];
+ /* The coefficient is scaled up by a 1000 */
+ mult = ((uint64_t)cp->interval * 1000) / codel_intervals[0];
/* Prepare table of intervals */
cp->intervals = mallocarray(nitems(codel_intervals),
sizeof(codel_intervals[0]), M_DEVBUF, M_WAITOK | M_ZERO);
for (i = 0; i < nitems(codel_intervals); i++)
- cp->intervals[i] = (codel_intervals[i] * mult) / 1000;
+ cp->intervals[i] = ((uint64_t)codel_intervals[i] *
+ mult) / 1000;
} else {
- cp->target = MAX(target, codel_target) * 1000;
- cp->interval = codel_intervals[0] * 1000;
+ cp->target = MAX(target, codel_target);
+ cp->interval = codel_intervals[0];
cp->intervals = (uint32_t *)codel_intervals;
}
cp->quantum = quantum;
}
@@ -295,11 +313,11 @@ static inline void
control_law(struct codel *cd, struct codel_params *cp, int64_t rts)
{
unsigned int idx;
idx = min(cd->drops, nitems(codel_intervals) - 1);
- cd->next = rts + cp->intervals[idx] * 1000;
+ cd->next = rts + cp->intervals[idx];
}
/*
* Pick the next enqueued packet and determine the queueing delay
* as well as whether or not it's a good candidate for dropping
