1 /*
2 * Copyright (c) 2018 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #include <kern/thread.h>
30 #include <kern/sched_prim.h>
31 #include <dev/random/randomdev.h>
32
33 #include <net/if.h>
34 #include <net/classq/classq.h>
35 #include <net/pktsched/pktsched.h>
36 #include <net/pktsched/pktsched_netem.h>
37
38 #define NETEM_STUB \
39 int \
40 netem_config(__unused struct netem **ne, __unused const char *__null_terminated name, \
41 __unused struct ifnet *ifp, __unused const struct if_netem_params *p,\
42 __unused void *output_handle, __unused netem_output_func_t *output_func, \
43 __unused uint32_t output_max_batch_size) \
44 { \
45 printf("%s error: unavailable on this platform\n", __func__); \
46 return ENOTSUP; \
47 } \
48 \
49 void \
50 __attribute__((noreturn)) \
51 netem_get_params(__unused struct netem *ne, \
52 __unused struct if_netem_params *p) \
53 { \
54 panic("unexpected netem call"); \
55 } \
56 \
57 void \
58 __attribute__((noreturn)) \
59 netem_destroy(__unused struct netem *ne) \
60 { \
61 panic("unexpected netem call"); \
62 } \
63 \
64 int \
65 netem_enqueue(__unused struct netem *ne, __unused classq_pkt_t *p, \
66 __unused bool *pdrop) \
67 { \
68 panic("unexpected netem call"); \
69 return 0; \
70 }
71
72 #if SKYWALK
73
74 #include <skywalk/os_skywalk_private.h>
75
76 /*
77 * The NetEm pktsched is designed with time-to-send scheduler model, scheduling
78 * decision are made at enqueue time only and the dequeue happens in a fixed
79 * routine, which determines wheter to send the next packet based on it's
80 * Time-To-Send (TTS) property.
81 *
82 * ##Enqueue##
83 * The enqueue model looks at various parameters of the
84 * current NetEm settings and calculates the packet's TTS:
85 * 1. Bandwidth regulator
86 * TTS is spaced out into future time based on the (pkt_len/rate).
87 * 2. Latency
88 * which is linearly added on top of TTS.
89 * 3. Reorder
90 * is done by making non-monotonic TTS.
91 * 4. Loss recovery (applies to IOD and FPD only)
92 * by adding recovery interval on top of TTS.
93 *
94 * ##Dequeue##
95 * The dequeue model has only one parameter, the output thread wakeup interval,
96 * which controls the granularity of packet scheduling. The output thread is
97 * created if the NetEm is created with a output handler and function (thus
98 * NetEm managed dequeue model). The thread wakes up periodically based on the
99 * interval. Upon wakeup, it dequeues all packets whose TTS is older than now
100 * and sends them to output handler.
101 *
102 */
103
104 #if __LP64__
105 #define CONFIG_NETEM 1
106 #else
107 #define CONFIG_NETEM 0
108 #endif
109
110 #if CONFIG_NETEM
111
112 #define NETEM_PSCALE IF_NETEM_PARAMS_PSCALE
113
114 #define NETEM_LOG(_level, _fmt, ...) \
115 do { \
116 if (pktsched_verbose >= _level) { \
117 log(_level, "NETEM: %-30s "_fmt "\n", \
118 __FUNCTION__, ##__VA_ARGS__); \
119 } \
120 } while (0);
121
122 SYSCTL_NODE(_net_pktsched, OID_AUTO, netem, CTLFLAG_RW | CTLFLAG_LOCKED, 0,
123 "netem");
124
125 static unsigned int netem_output_ival_ms = 1;
126 SYSCTL_UINT(_net_pktsched_netem, OID_AUTO, sched_output_ival_ms,
127 CTLFLAG_RW | CTLFLAG_LOCKED, &netem_output_ival_ms, 0,
128 "Netem packet output interval");
129
130 #define NETEM_HEAP_SIZE_DEFAULT 2048
131 static unsigned int netem_heap_size = NETEM_HEAP_SIZE_DEFAULT;
132 SYSCTL_UINT(_net_pktsched_netem, OID_AUTO, heap_size,
133 CTLFLAG_RW | CTLFLAG_LOCKED, &netem_heap_size, 0,
134 "Netem heap size");
135
136 extern kern_return_t thread_terminate(thread_t);
137
138 static LCK_GRP_DECLARE(netem_lock_group, "pktsched_netem_lock");
139
140 static const int32_t NORM_DIST_SCALE = 8192;
141 /* normal distribution lookup table */
142 static int32_t norm_dist_table[] =
143 {
144 -32768, -28307, -26871, -25967, -25298, -24765, -24320, -23937,
145 -23600, -23298, -23025, -22776, -22546, -22333, -22133, -21946,
146 -21770, -21604, -21445, -21295, -21151, -21013, -20882, -20755,
147 -20633, -20516, -20403, -20293, -20187, -20084, -19984, -19887,
148 -19793, -19702, -19612, -19526, -19441, -19358, -19277, -19198,
149 -19121, -19045, -18971, -18899, -18828, -18758, -18690, -18623,
150 -18557, -18492, -18429, -18366, -18305, -18245, -18185, -18127,
151 -18070, -18013, -17957, -17902, -17848, -17794, -17741, -17690,
152 -17638, -17588, -17538, -17489, -17440, -17392, -17345, -17298,
153 -17252, -17206, -17160, -17116, -17071, -17028, -16984, -16942,
154 -16899, -16857, -16816, -16775, -16735, -16694, -16654, -16615,
155 -16576, -16538, -16499, -16461, -16424, -16386, -16350, -16313,
156 -16277, -16241, -16205, -16170, -16135, -16100, -16066, -16031,
157 -15998, -15964, -15931, -15897, -15865, -15832, -15800, -15768,
158 -15736, -15704, -15673, -15642, -15611, -15580, -15550, -15519,
159 -15489, -15460, -15430, -15401, -15371, -15342, -15313, -15285,
160 -15256, -15228, -15200, -15172, -15144, -15116, -15089, -15062,
161 -15035, -15008, -14981, -14954, -14928, -14902, -14875, -14850,
162 -14823, -14798, -14772, -14747, -14722, -14696, -14671, -14647,
163 -14622, -14597, -14573, -14549, -14524, -14500, -14476, -14453,
164 -14429, -14405, -14382, -14359, -14335, -14312, -14289, -14266,
165 -14243, -14221, -14198, -14176, -14153, -14131, -14109, -14087,
166 -14065, -14043, -14021, -14000, -13978, -13957, -13935, -13914,
167 -13893, -13872, -13851, -13830, -13809, -13788, -13768, -13747,
168 -13727, -13706, -13686, -13666, -13646, -13626, -13606, -13586,
169 -13566, -13547, -13527, -13507, -13488, -13468, -13449, -13430,
170 -13411, -13392, -13373, -13354, -13335, -13316, -13297, -13278,
171 -13260, -13242, -13223, -13204, -13186, -13168, -13150, -13131,
172 -13113, -13095, -13077, -13060, -13042, -13024, -13006, -12988,
173 -12971, -12954, -12936, -12918, -12901, -12884, -12867, -12850,
174 -12832, -12815, -12798, -12781, -12764, -12748, -12731, -12714,
175 -12697, -12681, -12664, -12648, -12631, -12615, -12598, -12582,
176 -12566, -12549, -12533, -12517, -12501, -12485, -12469, -12453,
177 -12437, -12422, -12406, -12390, -12374, -12358, -12343, -12327,
178 -12312, -12296, -12281, -12265, -12250, -12235, -12220, -12204,
179 -12189, -12174, -12159, -12144, -12129, -12114, -12099, -12084,
180 -12069, -12054, -12039, -12025, -12010, -11995, -11981, -11966,
181 -11952, -11937, -11923, -11908, -11894, -11879, -11865, -11851,
182 -11837, -11822, -11808, -11794, -11780, -11766, -11752, -11737,
183 -11724, -11710, -11696, -11682, -11668, -11654, -11640, -11627,
184 -11613, -11599, -11586, -11572, -11559, -11545, -11531, -11518,
185 -11504, -11491, -11478, -11464, -11451, -11438, -11425, -11411,
186 -11398, -11385, -11372, -11359, -11346, -11332, -11319, -11306,
187 -11293, -11280, -11268, -11255, -11242, -11229, -11216, -11203,
188 -11191, -11178, -11165, -11153, -11140, -11127, -11114, -11102,
189 -11090, -11077, -11065, -11052, -11040, -11027, -11015, -11002,
190 -10990, -10978, -10965, -10953, -10941, -10929, -10917, -10904,
191 -10892, -10880, -10868, -10856, -10844, -10832, -10820, -10808,
192 -10796, -10784, -10772, -10760, -10748, -10736, -10725, -10713,
193 -10701, -10689, -10677, -10666, -10654, -10643, -10631, -10619,
194 -10607, -10596, -10584, -10573, -10562, -10550, -10539, -10527,
195 -10516, -10504, -10493, -10481, -10470, -10459, -10447, -10436,
196 -10425, -10414, -10402, -10391, -10380, -10369, -10358, -10346,
197 -10335, -10324, -10313, -10302, -10291, -10280, -10269, -10258,
198 -10247, -10236, -10225, -10214, -10203, -10192, -10181, -10171,
199 -10160, -10149, -10138, -10127, -10117, -10106, -10095, -10085,
200 -10074, -10063, -10052, -10042, -10031, -10021, -10010, -10000,
201 -9989, -9978, -9968, -9957, -9947, -9936, -9926, -9916,
202 -9905, -9895, -9884, -9874, -9864, -9853, -9843, -9833,
203 -9822, -9812, -9802, -9791, -9781, -9771, -9761, -9751,
204 -9741, -9730, -9720, -9710, -9700, -9690, -9680, -9670,
205 -9660, -9650, -9640, -9630, -9619, -9610, -9600, -9590,
206 -9580, -9570, -9560, -9550, -9540, -9530, -9520, -9511,
207 -9501, -9491, -9481, -9472, -9462, -9452, -9442, -9432,
208 -9423, -9413, -9403, -9394, -9384, -9374, -9365, -9355,
209 -9345, -9336, -9326, -9317, -9307, -9298, -9288, -9278,
210 -9269, -9259, -9250, -9241, -9231, -9221, -9212, -9202,
211 -9193, -9184, -9175, -9165, -9156, -9146, -9137, -9128,
212 -9119, -9109, -9100, -9090, -9081, -9072, -9063, -9053,
213 -9044, -9035, -9026, -9017, -9008, -8998, -8989, -8980,
214 -8971, -8962, -8953, -8944, -8934, -8925, -8916, -8907,
215 -8898, -8889, -8880, -8871, -8862, -8853, -8844, -8835,
216 -8826, -8817, -8808, -8799, -8790, -8781, -8772, -8764,
217 -8755, -8746, -8737, -8728, -8719, -8711, -8702, -8693,
218 -8684, -8675, -8667, -8658, -8649, -8640, -8632, -8623,
219 -8614, -8605, -8597, -8588, -8579, -8570, -8562, -8553,
220 -8545, -8536, -8527, -8519, -8510, -8502, -8493, -8484,
221 -8476, -8467, -8459, -8450, -8442, -8433, -8425, -8416,
222 -8408, -8399, -8391, -8382, -8374, -8365, -8357, -8348,
223 -8340, -8332, -8323, -8315, -8306, -8298, -8290, -8281,
224 -8273, -8264, -8256, -8248, -8240, -8231, -8223, -8215,
225 -8206, -8198, -8190, -8182, -8174, -8165, -8157, -8149,
226 -8140, -8132, -8124, -8116, -8108, -8099, -8091, -8083,
227 -8075, -8067, -8059, -8051, -8042, -8034, -8027, -8018,
228 -8010, -8002, -7994, -7986, -7978, -7970, -7962, -7954,
229 -7946, -7938, -7930, -7922, -7913, -7906, -7897, -7890,
230 -7882, -7874, -7866, -7858, -7850, -7842, -7834, -7826,
231 -7818, -7810, -7802, -7795, -7787, -7779, -7771, -7763,
232 -7755, -7748, -7739, -7732, -7724, -7716, -7708, -7700,
233 -7693, -7685, -7677, -7669, -7662, -7654, -7646, -7638,
234 -7630, -7623, -7615, -7608, -7600, -7592, -7584, -7577,
235 -7569, -7561, -7553, -7546, -7538, -7530, -7523, -7515,
236 -7508, -7500, -7492, -7485, -7477, -7469, -7462, -7454,
237 -7447, -7439, -7432, -7424, -7417, -7409, -7401, -7394,
238 -7386, -7379, -7372, -7364, -7356, -7349, -7341, -7334,
239 -7327, -7319, -7311, -7304, -7297, -7289, -7281, -7274,
240 -7267, -7259, -7252, -7245, -7237, -7230, -7222, -7215,
241 -7208, -7200, -7193, -7186, -7178, -7171, -7163, -7156,
242 -7149, -7141, -7134, -7127, -7119, -7112, -7105, -7098,
243 -7090, -7083, -7075, -7068, -7061, -7054, -7046, -7039,
244 -7032, -7025, -7018, -7010, -7003, -6996, -6989, -6981,
245 -6974, -6967, -6960, -6953, -6946, -6938, -6931, -6924,
246 -6917, -6910, -6903, -6895, -6888, -6881, -6874, -6867,
247 -6860, -6853, -6845, -6838, -6831, -6824, -6817, -6810,
248 -6803, -6796, -6789, -6782, -6775, -6767, -6760, -6753,
249 -6747, -6740, -6732, -6725, -6718, -6711, -6704, -6697,
250 -6690, -6683, -6676, -6669, -6662, -6655, -6648, -6641,
251 -6634, -6627, -6620, -6613, -6607, -6600, -6593, -6586,
252 -6579, -6572, -6565, -6558, -6551, -6544, -6538, -6531,
253 -6524, -6517, -6510, -6503, -6496, -6489, -6482, -6476,
254 -6469, -6462, -6455, -6448, -6441, -6434, -6428, -6421,
255 -6414, -6407, -6400, -6394, -6387, -6380, -6373, -6366,
256 -6360, -6353, -6346, -6339, -6333, -6326, -6319, -6312,
257 -6306, -6299, -6292, -6286, -6279, -6272, -6265, -6259,
258 -6252, -6245, -6239, -6232, -6225, -6219, -6212, -6205,
259 -6198, -6192, -6185, -6178, -6172, -6165, -6158, -6152,
260 -6145, -6139, -6132, -6125, -6119, -6112, -6105, -6099,
261 -6092, -6085, -6079, -6072, -6066, -6059, -6053, -6046,
262 -6040, -6033, -6026, -6019, -6013, -6006, -6000, -5993,
263 -5987, -5980, -5974, -5967, -5961, -5954, -5948, -5941,
264 -5935, -5928, -5922, -5915, -5908, -5902, -5895, -5889,
265 -5883, -5876, -5870, -5863, -5857, -5850, -5844, -5837,
266 -5831, -5825, -5818, -5811, -5805, -5799, -5792, -5786,
267 -5779, -5773, -5766, -5760, -5754, -5747, -5741, -5734,
268 -5728, -5722, -5715, -5709, -5702, -5696, -5690, -5683,
269 -5677, -5671, -5664, -5658, -5651, -5645, -5639, -5632,
270 -5626, -5620, -5613, -5607, -5600, -5594, -5588, -5582,
271 -5575, -5569, -5563, -5556, -5550, -5544, -5537, -5531,
272 -5525, -5519, -5512, -5506, -5500, -5494, -5487, -5481,
273 -5475, -5468, -5462, -5456, -5450, -5443, -5437, -5431,
274 -5425, -5418, -5412, -5406, -5400, -5393, -5387, -5381,
275 -5375, -5369, -5362, -5356, -5350, -5344, -5337, -5331,
276 -5325, -5319, -5313, -5306, -5300, -5294, -5288, -5282,
277 -5276, -5270, -5263, -5257, -5251, -5245, -5239, -5233,
278 -5226, -5220, -5214, -5208, -5202, -5196, -5190, -5183,
279 -5177, -5171, -5165, -5159, -5153, -5147, -5140, -5135,
280 -5129, -5122, -5116, -5110, -5104, -5098, -5092, -5086,
281 -5080, -5074, -5068, -5061, -5055, -5050, -5043, -5037,
282 -5031, -5025, -5019, -5013, -5007, -5001, -4995, -4989,
283 -4983, -4977, -4971, -4965, -4959, -4953, -4947, -4941,
284 -4935, -4929, -4923, -4917, -4911, -4905, -4899, -4893,
285 -4887, -4881, -4875, -4869, -4863, -4857, -4851, -4845,
286 -4839, -4833, -4827, -4821, -4815, -4809, -4803, -4797,
287 -4791, -4785, -4779, -4773, -4767, -4762, -4755, -4750,
288 -4744, -4738, -4732, -4726, -4720, -4714, -4708, -4702,
289 -4696, -4690, -4685, -4678, -4673, -4667, -4661, -4655,
290 -4649, -4643, -4637, -4631, -4626, -4620, -4614, -4608,
291 -4602, -4596, -4590, -4585, -4579, -4573, -4567, -4561,
292 -4555, -4549, -4544, -4538, -4532, -4526, -4520, -4514,
293 -4508, -4503, -4497, -4491, -4485, -4479, -4474, -4468,
294 -4462, -4456, -4450, -4445, -4439, -4433, -4427, -4421,
295 -4415, -4410, -4404, -4398, -4392, -4386, -4381, -4375,
296 -4369, -4363, -4358, -4352, -4346, -4340, -4334, -4329,
297 -4323, -4317, -4311, -4306, -4300, -4294, -4289, -4283,
298 -4277, -4271, -4266, -4260, -4254, -4248, -4243, -4237,
299 -4231, -4225, -4220, -4214, -4208, -4202, -4197, -4191,
300 -4185, -4180, -4174, -4168, -4162, -4157, -4151, -4146,
301 -4140, -4134, -4128, -4123, -4117, -4111, -4105, -4100,
302 -4094, -4089, -4083, -4077, -4071, -4066, -4060, -4055,
303 -4049, -4043, -4037, -4032, -4026, -4021, -4015, -4009,
304 -4003, -3998, -3992, -3987, -3981, -3975, -3970, -3964,
305 -3958, -3953, -3947, -3942, -3936, -3930, -3925, -3919,
306 -3913, -3908, -3902, -3897, -3891, -3885, -3880, -3874,
307 -3869, -3863, -3857, -3852, -3846, -3840, -3835, -3829,
308 -3824, -3818, -3813, -3807, -3801, -3796, -3790, -3785,
309 -3779, -3774, -3768, -3762, -3757, -3751, -3746, -3740,
310 -3734, -3729, -3723, -3718, -3712, -3707, -3701, -3696,
311 -3690, -3684, -3679, -3673, -3668, -3662, -3657, -3651,
312 -3646, -3640, -3635, -3629, -3624, -3618, -3613, -3607,
313 -3602, -3596, -3591, -3585, -3579, -3574, -3568, -3563,
314 -3557, -3552, -3546, -3541, -3535, -3530, -3524, -3519,
315 -3514, -3508, -3502, -3497, -3491, -3486, -3480, -3475,
316 -3469, -3464, -3459, -3453, -3448, -3442, -3437, -3431,
317 -3425, -3420, -3415, -3409, -3404, -3398, -3393, -3387,
318 -3382, -3376, -3371, -3366, -3360, -3355, -3349, -3344,
319 -3338, -3333, -3328, -3322, -3317, -3311, -3305, -3300,
320 -3295, -3289, -3284, -3278, -3273, -3268, -3262, -3257,
321 -3251, -3246, -3240, -3235, -3230, -3224, -3219, -3213,
322 -3208, -3203, -3197, -3192, -3186, -3181, -3176, -3170,
323 -3165, -3159, -3154, -3149, -3143, -3138, -3132, -3127,
324 -3122, -3116, -3111, -3105, -3100, -3095, -3089, -3084,
325 -3079, -3073, -3068, -3062, -3057, -3052, -3046, -3041,
326 -3036, -3030, -3025, -3019, -3014, -3009, -3003, -2998,
327 -2993, -2987, -2982, -2977, -2971, -2966, -2961, -2955,
328 -2950, -2944, -2939, -2934, -2928, -2923, -2918, -2912,
329 -2907, -2902, -2896, -2891, -2886, -2880, -2875, -2870,
330 -2864, -2859, -2854, -2848, -2843, -2838, -2832, -2827,
331 -2822, -2816, -2811, -2806, -2800, -2795, -2790, -2784,
332 -2779, -2774, -2768, -2763, -2758, -2753, -2747, -2742,
333 -2737, -2732, -2726, -2721, -2716, -2710, -2705, -2700,
334 -2694, -2689, -2684, -2678, -2673, -2668, -2663, -2657,
335 -2652, -2647, -2642, -2636, -2631, -2626, -2620, -2615,
336 -2610, -2605, -2599, -2594, -2589, -2583, -2578, -2573,
337 -2568, -2562, -2557, -2552, -2546, -2542, -2536, -2531,
338 -2526, -2520, -2515, -2510, -2505, -2499, -2494, -2489,
339 -2483, -2478, -2473, -2468, -2463, -2457, -2452, -2447,
340 -2442, -2436, -2431, -2426, -2421, -2415, -2410, -2405,
341 -2400, -2395, -2389, -2384, -2379, -2374, -2368, -2363,
342 -2358, -2353, -2347, -2342, -2337, -2332, -2327, -2321,
343 -2316, -2311, -2306, -2300, -2295, -2290, -2285, -2279,
344 -2275, -2269, -2264, -2259, -2254, -2248, -2243, -2238,
345 -2233, -2227, -2222, -2217, -2212, -2207, -2202, -2196,
346 -2191, -2186, -2181, -2175, -2170, -2165, -2160, -2155,
347 -2150, -2144, -2139, -2134, -2129, -2124, -2118, -2113,
348 -2108, -2103, -2098, -2093, -2087, -2082, -2077, -2072,
349 -2067, -2062, -2056, -2051, -2046, -2041, -2036, -2030,
350 -2025, -2020, -2015, -2010, -2005, -2000, -1994, -1989,
351 -1984, -1979, -1974, -1969, -1963, -1958, -1953, -1948,
352 -1943, -1937, -1932, -1927, -1922, -1917, -1912, -1907,
353 -1901, -1896, -1891, -1886, -1881, -1876, -1871, -1865,
354 -1860, -1855, -1850, -1845, -1840, -1835, -1829, -1824,
355 -1819, -1814, -1809, -1804, -1799, -1794, -1788, -1783,
356 -1778, -1773, -1768, -1763, -1758, -1752, -1747, -1742,
357 -1737, -1732, -1727, -1722, -1717, -1711, -1706, -1701,
358 -1696, -1691, -1686, -1681, -1676, -1670, -1665, -1660,
359 -1655, -1650, -1645, -1640, -1635, -1629, -1624, -1619,
360 -1614, -1609, -1604, -1599, -1594, -1589, -1584, -1579,
361 -1573, -1568, -1563, -1558, -1553, -1548, -1543, -1538,
362 -1532, -1527, -1522, -1517, -1512, -1507, -1502, -1497,
363 -1492, -1486, -1482, -1477, -1471, -1466, -1461, -1456,
364 -1451, -1446, -1441, -1436, -1431, -1425, -1420, -1415,
365 -1410, -1405, -1400, -1395, -1390, -1385, -1380, -1375,
366 -1370, -1364, -1359, -1354, -1349, -1344, -1339, -1334,
367 -1329, -1324, -1319, -1314, -1309, -1303, -1298, -1294,
368 -1288, -1283, -1278, -1273, -1268, -1263, -1258, -1253,
369 -1248, -1243, -1237, -1232, -1228, -1222, -1217, -1212,
370 -1207, -1202, -1197, -1192, -1187, -1182, -1177, -1171,
371 -1167, -1162, -1156, -1151, -1146, -1141, -1136, -1131,
372 -1126, -1121, -1116, -1111, -1106, -1101, -1096, -1091,
373 -1085, -1081, -1076, -1070, -1065, -1060, -1055, -1050,
374 -1045, -1040, -1035, -1030, -1025, -1020, -1015, -1010,
375 -1005, -1000, -995, -990, -985, -979, -974, -970,
376 -964, -959, -954, -949, -944, -939, -934, -929,
377 -924, -919, -914, -909, -904, -899, -894, -889,
378 -884, -879, -874, -868, -863, -859, -853, -848,
379 -843, -838, -833, -828, -823, -818, -813, -808,
380 -803, -798, -793, -788, -783, -778, -773, -768,
381 -763, -758, -752, -748, -743, -738, -732, -727,
382 -723, -717, -712, -707, -702, -697, -692, -687,
383 -682, -677, -672, -667, -662, -657, -652, -647,
384 -642, -637, -632, -627, -622, -617, -612, -607,
385 -602, -597, -591, -587, -582, -577, -571, -566,
386 -562, -557, -551, -546, -541, -537, -531, -526,
387 -521, -516, -511, -506, -501, -496, -491, -486,
388 -481, -476, -471, -466, -461, -456, -451, -446,
389 -441, -436, -431, -426, -421, -416, -411, -406,
390 -401, -396, -391, -386, -381, -376, -371, -366,
391 -360, -356, -351, -346, -340, -335, -331, -326,
392 -320, -315, -310, -306, -300, -295, -290, -285,
393 -281, -275, -270, -265, -261, -255, -250, -245,
394 -240, -235, -230, -225, -220, -215, -210, -205,
395 -200, -195, -190, -185, -180, -175, -170, -165,
396 -160, -155, -150, -145, -140, -135, -130, -125,
397 -120, -115, -110, -105, -100, -95, -90, -85,
398 -80, -75, -70, -65, -60, -55, -50, -45,
399 -40, -35, -29, -25, -20, -15, -9, -5,
400 0, 5, 11, 16, 20, 25, 30, 36,
401 41, 45, 50, 56, 61, 66, 70, 76,
402 81, 86, 91, 96, 101, 106, 111, 116,
403 121, 126, 131, 136, 141, 146, 151, 156,
404 161, 166, 171, 176, 181, 186, 191, 196,
405 201, 206, 211, 216, 221, 226, 231, 236,
406 241, 246, 251, 256, 261, 266, 271, 276,
407 281, 286, 291, 296, 301, 306, 311, 316,
408 322, 326, 331, 336, 342, 347, 351, 356,
409 362, 367, 372, 376, 382, 387, 392, 396,
410 402, 407, 412, 417, 422, 427, 432, 437,
411 442, 447, 452, 457, 462, 467, 472, 477,
412 482, 487, 492, 497, 502, 507, 512, 517,
413 522, 527, 532, 537, 542, 547, 552, 557,
414 562, 567, 572, 578, 582, 587, 593, 598,
415 603, 607, 613, 618, 623, 628, 633, 638,
416 643, 648, 653, 658, 663, 668, 673, 678,
417 683, 688, 693, 698, 703, 708, 713, 718,
418 723, 728, 733, 739, 743, 748, 754, 759,
419 763, 768, 774, 779, 784, 789, 794, 799,
420 804, 809, 814, 819, 824, 829, 834, 839,
421 844, 849, 854, 859, 864, 869, 874, 879,
422 884, 890, 895, 899, 905, 910, 915, 920,
423 925, 930, 935, 940, 945, 950, 955, 960,
424 965, 970, 975, 980, 985, 990, 995, 1001,
425 1006, 1010, 1016, 1021, 1026, 1031, 1036, 1041,
426 1046, 1051, 1056, 1061, 1066, 1071, 1076, 1081,
427 1086, 1092, 1096, 1102, 1107, 1112, 1117, 1122,
428 1127, 1132, 1137, 1142, 1147, 1152, 1157, 1162,
429 1167, 1173, 1178, 1183, 1188, 1193, 1198, 1203,
430 1208, 1213, 1218, 1223, 1228, 1233, 1238, 1244,
431 1248, 1254, 1259, 1264, 1269, 1274, 1279, 1284,
432 1289, 1294, 1299, 1304, 1309, 1314, 1320, 1325,
433 1330, 1335, 1340, 1345, 1350, 1355, 1360, 1365,
434 1371, 1375, 1381, 1386, 1391, 1396, 1401, 1406,
435 1411, 1416, 1421, 1426, 1432, 1436, 1442, 1447,
436 1452, 1457, 1462, 1467, 1472, 1477, 1482, 1488,
437 1493, 1497, 1503, 1508, 1513, 1518, 1523, 1528,
438 1534, 1538, 1543, 1549, 1554, 1559, 1564, 1569,
439 1574, 1579, 1584, 1590, 1595, 1600, 1605, 1610,
440 1615, 1620, 1625, 1630, 1636, 1640, 1646, 1651,
441 1656, 1661, 1666, 1671, 1676, 1681, 1687, 1692,
442 1697, 1702, 1707, 1712, 1717, 1722, 1728, 1733,
443 1738, 1743, 1748, 1753, 1758, 1764, 1769, 1774,
444 1779, 1784, 1789, 1794, 1799, 1805, 1810, 1815,
445 1820, 1825, 1831, 1835, 1841, 1846, 1851, 1856,
446 1861, 1866, 1871, 1877, 1882, 1887, 1892, 1897,
447 1902, 1908, 1913, 1918, 1923, 1928, 1933, 1939,
448 1944, 1949, 1954, 1959, 1964, 1969, 1975, 1980,
449 1985, 1990, 1995, 2000, 2005, 2011, 2016, 2021,
450 2026, 2031, 2037, 2042, 2047, 2052, 2057, 2062,
451 2068, 2073, 2078, 2083, 2088, 2093, 2099, 2104,
452 2109, 2114, 2119, 2125, 2130, 2135, 2140, 2145,
453 2150, 2156, 2161, 2166, 2171, 2177, 2182, 2187,
454 2192, 2197, 2202, 2208, 2213, 2218, 2223, 2229,
455 2234, 2239, 2244, 2249, 2254, 2260, 2265, 2270,
456 2275, 2281, 2286, 2291, 2296, 2302, 2306, 2312,
457 2317, 2322, 2327, 2333, 2338, 2343, 2348, 2354,
458 2359, 2364, 2369, 2374, 2380, 2385, 2390, 2395,
459 2401, 2406, 2411, 2416, 2422, 2427, 2432, 2437,
460 2442, 2448, 2453, 2458, 2463, 2469, 2474, 2479,
461 2485, 2490, 2495, 2500, 2506, 2511, 2516, 2521,
462 2526, 2532, 2537, 2542, 2548, 2553, 2558, 2563,
463 2569, 2574, 2579, 2585, 2589, 2595, 2600, 2605,
464 2611, 2616, 2621, 2627, 2632, 2637, 2642, 2648,
465 2653, 2658, 2664, 2669, 2674, 2680, 2685, 2690,
466 2695, 2700, 2706, 2711, 2716, 2722, 2727, 2732,
467 2738, 2743, 2748, 2754, 2759, 2764, 2769, 2775,
468 2780, 2785, 2791, 2796, 2801, 2807, 2812, 2817,
469 2823, 2828, 2833, 2839, 2844, 2849, 2855, 2860,
470 2865, 2870, 2876, 2881, 2886, 2892, 2897, 2902,
471 2908, 2913, 2918, 2924, 2929, 2935, 2940, 2945,
472 2951, 2956, 2961, 2967, 2972, 2977, 2983, 2988,
473 2993, 2999, 3004, 3010, 3015, 3020, 3026, 3031,
474 3036, 3042, 3047, 3052, 3058, 3063, 3069, 3074,
475 3079, 3085, 3090, 3095, 3101, 3106, 3112, 3117,
476 3122, 3128, 3133, 3139, 3144, 3149, 3155, 3160,
477 3166, 3171, 3176, 3182, 3187, 3193, 3198, 3203,
478 3209, 3214, 3220, 3225, 3231, 3236, 3242, 3247,
479 3252, 3258, 3263, 3269, 3274, 3279, 3285, 3290,
480 3296, 3301, 3307, 3312, 3317, 3323, 3328, 3334,
481 3339, 3345, 3350, 3355, 3361, 3367, 3372, 3378,
482 3383, 3388, 3394, 3399, 3405, 3410, 3416, 3421,
483 3427, 3432, 3437, 3443, 3448, 3454, 3459, 3465,
484 3471, 3476, 3481, 3487, 3492, 3498, 3503, 3509,
485 3514, 3520, 3525, 3531, 3536, 3542, 3548, 3553,
486 3558, 3564, 3569, 3575, 3580, 3586, 3591, 3597,
487 3602, 3608, 3613, 3619, 3625, 3630, 3636, 3641,
488 3647, 3652, 3658, 3663, 3669, 3675, 3680, 3686,
489 3691, 3697, 3702, 3708, 3713, 3719, 3724, 3730,
490 3736, 3741, 3747, 3752, 3758, 3763, 3769, 3774,
491 3780, 3786, 3791, 3797, 3802, 3808, 3813, 3819,
492 3825, 3830, 3836, 3842, 3847, 3853, 3858, 3864,
493 3869, 3875, 3881, 3886, 3892, 3898, 3903, 3909,
494 3915, 3920, 3926, 3931, 3937, 3942, 3948, 3954,
495 3960, 3965, 3971, 3976, 3982, 3987, 3993, 3999,
496 4005, 4010, 4016, 4021, 4027, 4033, 4039, 4044,
497 4050, 4055, 4061, 4067, 4073, 4078, 4084, 4089,
498 4095, 4101, 4107, 4112, 4118, 4123, 4129, 4135,
499 4141, 4146, 4152, 4158, 4164, 4169, 4175, 4181,
500 4187, 4192, 4198, 4203, 4209, 4215, 4221, 4226,
501 4232, 4238, 4243, 4249, 4255, 4261, 4266, 4272,
502 4278, 4284, 4289, 4295, 4301, 4307, 4313, 4318,
503 4324, 4330, 4336, 4341, 4347, 4353, 4359, 4364,
504 4370, 4376, 4382, 4388, 4393, 4399, 4405, 4411,
505 4417, 4422, 4428, 4434, 4440, 4445, 4452, 4457,
506 4463, 4469, 4474, 4481, 4486, 4492, 4498, 4504,
507 4510, 4515, 4521, 4527, 4533, 4539, 4545, 4551,
508 4556, 4562, 4568, 4574, 4580, 4585, 4592, 4597,
509 4603, 4609, 4615, 4621, 4627, 4633, 4638, 4644,
510 4650, 4656, 4662, 4668, 4674, 4680, 4686, 4692,
511 4697, 4703, 4709, 4715, 4721, 4727, 4733, 4739,
512 4745, 4751, 4757, 4762, 4769, 4774, 4780, 4786,
513 4792, 4798, 4804, 4810, 4816, 4822, 4828, 4834,
514 4840, 4846, 4852, 4858, 4864, 4870, 4876, 4882,
515 4888, 4894, 4900, 4906, 4912, 4918, 4924, 4930,
516 4936, 4942, 4948, 4954, 4960, 4966, 4972, 4978,
517 4984, 4990, 4996, 5002, 5008, 5014, 5020, 5026,
518 5032, 5038, 5045, 5050, 5057, 5063, 5069, 5075,
519 5081, 5087, 5093, 5099, 5105, 5111, 5118, 5123,
520 5129, 5136, 5142, 5148, 5154, 5160, 5166, 5172,
521 5179, 5185, 5191, 5197, 5203, 5209, 5215, 5221,
522 5227, 5233, 5240, 5246, 5252, 5258, 5265, 5271,
523 5277, 5283, 5289, 5295, 5301, 5308, 5314, 5320,
524 5326, 5333, 5339, 5345, 5351, 5357, 5363, 5369,
525 5376, 5382, 5388, 5394, 5401, 5407, 5413, 5419,
526 5426, 5432, 5438, 5444, 5451, 5457, 5463, 5469,
527 5476, 5482, 5488, 5494, 5501, 5507, 5513, 5520,
528 5526, 5532, 5539, 5545, 5551, 5557, 5564, 5570,
529 5576, 5583, 5589, 5596, 5602, 5608, 5614, 5621,
530 5627, 5634, 5640, 5646, 5652, 5659, 5665, 5672,
531 5678, 5684, 5691, 5697, 5704, 5710, 5716, 5723,
532 5729, 5736, 5742, 5748, 5755, 5761, 5768, 5774,
533 5780, 5787, 5793, 5800, 5806, 5813, 5819, 5826,
534 5832, 5838, 5845, 5852, 5858, 5864, 5871, 5877,
535 5884, 5890, 5897, 5903, 5910, 5916, 5923, 5929,
536 5936, 5942, 5949, 5956, 5962, 5968, 5975, 5981,
537 5988, 5994, 6001, 6008, 6014, 6021, 6027, 6034,
538 6041, 6047, 6054, 6060, 6067, 6074, 6080, 6087,
539 6093, 6100, 6107, 6113, 6120, 6126, 6133, 6140,
540 6146, 6153, 6160, 6167, 6173, 6180, 6186, 6193,
541 6200, 6206, 6213, 6220, 6226, 6233, 6240, 6246,
542 6253, 6260, 6266, 6273, 6280, 6287, 6294, 6300,
543 6307, 6314, 6321, 6327, 6334, 6341, 6348, 6354,
544 6361, 6368, 6375, 6382, 6388, 6395, 6402, 6409,
545 6416, 6422, 6429, 6436, 6443, 6450, 6457, 6463,
546 6470, 6477, 6484, 6491, 6497, 6504, 6511, 6518,
547 6525, 6532, 6539, 6546, 6553, 6559, 6566, 6573,
548 6580, 6587, 6594, 6601, 6608, 6615, 6622, 6629,
549 6636, 6643, 6650, 6657, 6664, 6671, 6678, 6685,
550 6692, 6699, 6706, 6713, 6719, 6727, 6734, 6741,
551 6748, 6755, 6762, 6769, 6776, 6783, 6790, 6797,
552 6804, 6811, 6818, 6826, 6833, 6840, 6847, 6854,
553 6861, 6868, 6875, 6883, 6889, 6897, 6904, 6911,
554 6918, 6925, 6932, 6939, 6947, 6954, 6961, 6969,
555 6975, 6983, 6990, 6997, 7005, 7012, 7019, 7026,
556 7033, 7041, 7048, 7055, 7062, 7070, 7077, 7084,
557 7091, 7099, 7106, 7114, 7121, 7128, 7135, 7143,
558 7150, 7157, 7165, 7172, 7179, 7187, 7194, 7202,
559 7209, 7216, 7224, 7231, 7238, 7246, 7253, 7261,
560 7268, 7276, 7283, 7290, 7298, 7306, 7313, 7320,
561 7328, 7336, 7343, 7350, 7358, 7365, 7373, 7381,
562 7388, 7395, 7403, 7410, 7418, 7426, 7433, 7441,
563 7448, 7456, 7463, 7471, 7479, 7486, 7494, 7501,
564 7509, 7517, 7524, 7532, 7540, 7547, 7555, 7563,
565 7571, 7578, 7586, 7594, 7601, 7609, 7617, 7624,
566 7632, 7640, 7648, 7655, 7663, 7671, 7679, 7687,
567 7694, 7702, 7710, 7718, 7725, 7733, 7741, 7749,
568 7757, 7765, 7773, 7780, 7788, 7796, 7804, 7812,
569 7820, 7828, 7836, 7843, 7852, 7859, 7868, 7875,
570 7883, 7891, 7899, 7907, 7915, 7923, 7931, 7939,
571 7947, 7955, 7963, 7971, 7979, 7988, 7995, 8004,
572 8012, 8020, 8028, 8036, 8044, 8052, 8061, 8069,
573 8076, 8085, 8093, 8101, 8109, 8117, 8126, 8134,
574 8142, 8150, 8158, 8167, 8175, 8183, 8192, 8200,
575 8208, 8217, 8225, 8233, 8241, 8250, 8258, 8266,
576 8275, 8283, 8292, 8300, 8308, 8317, 8325, 8333,
577 8342, 8350, 8359, 8367, 8376, 8384, 8392, 8401,
578 8409, 8418, 8426, 8435, 8443, 8452, 8461, 8469,
579 8477, 8486, 8495, 8503, 8512, 8520, 8529, 8538,
580 8546, 8555, 8564, 8573, 8581, 8590, 8598, 8607,
581 8616, 8625, 8633, 8642, 8651, 8659, 8668, 8677,
582 8686, 8695, 8704, 8712, 8721, 8730, 8739, 8748,
583 8756, 8765, 8774, 8783, 8792, 8801, 8810, 8819,
584 8828, 8837, 8846, 8855, 8864, 8873, 8882, 8891,
585 8900, 8909, 8918, 8927, 8936, 8945, 8954, 8964,
586 8973, 8982, 8991, 9000, 9009, 9019, 9028, 9037,
587 9046, 9055, 9064, 9074, 9083, 9092, 9102, 9111,
588 9120, 9130, 9139, 9148, 9157, 9167, 9176, 9186,
589 9195, 9205, 9214, 9223, 9233, 9242, 9252, 9261,
590 9271, 9280, 9290, 9300, 9309, 9318, 9328, 9338,
591 9347, 9357, 9367, 9376, 9386, 9395, 9405, 9415,
592 9424, 9434, 9444, 9454, 9464, 9473, 9483, 9493,
593 9503, 9513, 9522, 9532, 9542, 9552, 9562, 9572,
594 9582, 9592, 9602, 9612, 9622, 9632, 9642, 9652,
595 9662, 9672, 9682, 9692, 9702, 9712, 9722, 9733,
596 9743, 9753, 9763, 9773, 9783, 9794, 9804, 9814,
597 9825, 9835, 9845, 9855, 9866, 9876, 9887, 9897,
598 9907, 9918, 9928, 9939, 9949, 9960, 9970, 9981,
599 9991, 10002, 10012, 10023, 10034, 10044, 10055, 10066,
600 10076, 10087, 10097, 10108, 10119, 10130, 10140, 10152,
601 10162, 10173, 10184, 10195, 10206, 10217, 10227, 10238,
602 10249, 10260, 10271, 10282, 10293, 10304, 10315, 10326,
603 10337, 10349, 10360, 10371, 10382, 10394, 10405, 10416,
604 10427, 10438, 10450, 10461, 10472, 10484, 10495, 10507,
605 10518, 10530, 10541, 10553, 10564, 10575, 10587, 10598,
606 10610, 10622, 10633, 10645, 10657, 10668, 10680, 10692,
607 10704, 10715, 10727, 10739, 10751, 10763, 10775, 10786,
608 10798, 10811, 10822, 10834, 10847, 10858, 10870, 10883,
609 10895, 10907, 10919, 10931, 10944, 10956, 10968, 10981,
610 10993, 11005, 11017, 11030, 11042, 11055, 11067, 11080,
611 11092, 11105, 11117, 11130, 11142, 11155, 11168, 11180,
612 11193, 11206, 11219, 11232, 11245, 11257, 11270, 11283,
613 11296, 11309, 11322, 11335, 11348, 11361, 11375, 11388,
614 11401, 11414, 11427, 11441, 11454, 11467, 11481, 11494,
615 11508, 11521, 11534, 11548, 11561, 11575, 11589, 11602,
616 11616, 11630, 11644, 11657, 11671, 11685, 11699, 11713,
617 11727, 11741, 11755, 11769, 11783, 11797, 11811, 11826,
618 11839, 11854, 11868, 11882, 11897, 11911, 11926, 11940,
619 11955, 11969, 11984, 11998, 12013, 12028, 12043, 12057,
620 12072, 12087, 12102, 12117, 12132, 12147, 12162, 12177,
621 12193, 12208, 12223, 12238, 12254, 12269, 12284, 12299,
622 12315, 12331, 12346, 12362, 12378, 12393, 12409, 12425,
623 12441, 12457, 12473, 12489, 12505, 12521, 12537, 12553,
624 12569, 12586, 12602, 12619, 12635, 12651, 12668, 12684,
625 12701, 12718, 12734, 12751, 12768, 12785, 12802, 12819,
626 12836, 12853, 12870, 12888, 12905, 12922, 12940, 12957,
627 12975, 12993, 13010, 13028, 13046, 13064, 13081, 13099,
628 13117, 13135, 13154, 13172, 13190, 13209, 13227, 13246,
629 13264, 13283, 13301, 13320, 13339, 13358, 13377, 13396,
630 13415, 13434, 13454, 13473, 13492, 13512, 13532, 13551,
631 13571, 13591, 13611, 13631, 13651, 13671, 13691, 13711,
632 13732, 13752, 13773, 13793, 13814, 13835, 13856, 13877,
633 13898, 13919, 13940, 13962, 13983, 14005, 14026, 14048,
634 14070, 14092, 14114, 14136, 14159, 14181, 14203, 14226,
635 14249, 14272, 14294, 14318, 14341, 14364, 14387, 14411,
636 14434, 14458, 14482, 14506, 14530, 14554, 14578, 14603,
637 14628, 14653, 14677, 14703, 14728, 14753, 14778, 14804,
638 14830, 14855, 14882, 14908, 14934, 14961, 14987, 15014,
639 15041, 15068, 15095, 15123, 15151, 15179, 15206, 15235,
640 15263, 15291, 15320, 15349, 15378, 15408, 15437, 15466,
641 15496, 15527, 15557, 15587, 15618, 15649, 15680, 15712,
642 15743, 15775, 15808, 15840, 15872, 15906, 15939, 15972,
643 16006, 16040, 16074, 16108, 16143, 16178, 16214, 16249,
644 16285, 16322, 16358, 16395, 16433, 16470, 16508, 16547,
645 16586, 16624, 16664, 16704, 16744, 16785, 16826, 16867,
646 16910, 16952, 16995, 17038, 17082, 17126, 17171, 17217,
647 17263, 17309, 17356, 17403, 17452, 17501, 17550, 17600,
648 17651, 17702, 17754, 17807, 17861, 17915, 17970, 18026,
649 18083, 18141, 18200, 18259, 18320, 18382, 18444, 18508,
650 18573, 18639, 18706, 18775, 18845, 18917, 18989, 19064,
651 19140, 19217, 19297, 19378, 19461, 19547, 19634, 19724,
652 19816, 19911, 20009, 20109, 20213, 20319, 20430, 20544,
653 20663, 20786, 20914, 21047, 21186, 21331, 21484, 21644,
654 21813, 21991, 22181, 22384, 22601, 22836, 23091, 23370,
655 23679, 24027, 24424, 24888, 25450, 26164, 27159, 28858,
656 };
657 #define NORM_DIST_TABLE_SIZE \
658 (sizeof (norm_dist_table) / sizeof (norm_dist_table[0]))
659
660 static uint32_t
norm_dist(uint32_t mean,uint32_t stdvar)661 norm_dist(uint32_t mean, uint32_t stdvar)
662 {
663 int32_t ret, var;
664
665 ret = mean;
666 var = 0;
667 if (stdvar != 0) {
668 int32_t rand, x, t, s = stdvar;
669 read_frandom(&rand, sizeof(rand));
670 t = norm_dist_table[rand % NORM_DIST_TABLE_SIZE];
671 x = (s % NORM_DIST_SCALE) * t;
672 if (x >= 0) {
673 x += NORM_DIST_SCALE / 2;
674 } else {
675 x -= NORM_DIST_SCALE / 2;
676 }
677 var = x / NORM_DIST_SCALE + (s * t / NORM_DIST_SCALE);
678 }
679
680 ret += var;
681 ret = MAX(ret, 0);
682
683 return ret;
684 }
685
686 struct heap_elem {
687 uint64_t key;
688 pktsched_pkt_t pkt;
689 };
690
691 struct heap {
692 size_t limit; /* max size */
693 size_t size; /* current size */
694 struct heap_elem __counted_by(limit) p[];
695 };
696
697 static struct heap *heap_create(size_t size);
698 static int heap_insert(struct heap *h, uint64_t k, pktsched_pkt_t *p);
699 static int heap_peek(struct heap *h, uint64_t *k, pktsched_pkt_t *p);
700 static int heap_extract(struct heap *h, uint64_t *k, pktsched_pkt_t *p);
701
702 typedef enum {
703 NETEM_MODEL_NULL = IF_NETEM_MODEL_NULL,
704 NETEM_MODEL_NLC = IF_NETEM_MODEL_NLC,
705 } netem_model_t;
706
707 typedef int (*netem_enqueue_fn_t)(struct netem *, classq_pkt_t *, bool *);
708
709 struct netem {
710 decl_lck_mtx_data(, netem_lock);
711
712 /************************ Init Time Constants *************************/
713 char netem_name[MAXTHREADNAMESIZE];
714 uint32_t netem_flags;
715 struct ifnet *netem_ifp;
716 struct thread *netem_output_thread;
717
718 void *netem_output_handle;
719 int (*netem_output)(void *handle,
720 pktsched_pkt_t *pkts, uint32_t n_pkts);
721 uint32_t netem_output_max_batch_size;
722 uint32_t netem_output_ival_ms;
723
724 struct heap *netem_heap;
725
726 /*********************** Parameters variables *************************/
727 netem_model_t netem_model;
728 netem_enqueue_fn_t netem_enqueue;
729
730 /* bandwidth token bucket limit */
731 #define TOKEN_INVALID UINT64_MAX
732 struct bandwidth {
733 uint64_t rate;
734 uint64_t prev_time_to_send;
735 } netem_bandwidth_model;
736
737 /* XXX (need correlated) naive corruption model */
738 struct corruption {
739 uint32_t corruption_p;
740 } netem_corruption_model;
741
742 /* naive duplication model */
743 struct duplication {
744 uint32_t duplication_p;
745 } netem_duplication_model;
746
747 /* latency (with jitter following random distribution) */
748 struct latency {
749 uint32_t latency_ms;
750 uint32_t jitter_ms;
751 uint64_t prev_time_to_send;
752 } netem_latency_model;
753
754 /* 4 state Markov packet loss model */
755 struct loss {
756 enum _4state_markov_packet_loss_state {
757 __NO_LOSS = 0,
758 GAP_RX = 1,
759 GAP_LOSS,
760 BURST_RX,
761 BURST_LOSS,
762 } state;
763
764 uint32_t p_gr_gl; /* P( gap_loss | gap_rx ) */
765 uint32_t p_gr_bl; /* P( burst_loss | gap_rx ) */
766 uint32_t p_bl_br; /* P( burst_rx | burst_loss ) */
767 uint32_t p_bl_gr; /* P( gap_rx | burst_loss ) */
768 uint32_t p_br_bl; /* P( burst_loss | burst_rx ) */
769
770 uint32_t recovery_ms; /* time to recovery from loss */
771 uint64_t recovery_window;/* time recovery will finish */
772 } netem_loss_model;
773
774 /*
775 * Reordering Model --
776 * randomly select packets and re-inject with additional delay
777 */
778 struct reordering {
779 uint32_t reordering_p;
780 uint32_t reordering_ms;
781 } netem_reordering_model;
782 };
783
784 #define NETEMF_INITIALIZED 0x00000001 /* has been initialized */
785 #define NETEMF_RUNNING 0x00000002 /* thread is running */
786 #define NETEMF_OUTPUT_IVAL_ONLY 0x00000004 /* output on intervals only */
787 #define NETEMF_TERMINATEBLOCK 0x20000000 /* block waiting terminate */
788 #define NETEMF_TERMINATING 0x40000000 /* thread is terminating */
789 #define NETEMF_TERMINATED 0x80000000 /* thread is terminated */
790
791 #define NETEM_MTX_LOCK(_ne) \
792 lck_mtx_lock(&(_ne)->netem_lock)
793 #define NETEM_MTX_LOCK_ASSERT_HELD(_ne) \
794 LCK_MTX_ASSERT(&(_ne)->netem_lock, LCK_ASSERT_OWNED)
795 #define NETEM_MTX_LOCK_ASSERT_NOTHELD(_ne) \
796 LCK_MTX_ASSERT(&(_ne)->netem_lock, LCK_ASSERT_NOTOWNED)
797 #define NETEM_MTX_UNLOCK(_ne) \
798 lck_mtx_unlock(&(_ne)->netem_lock)
799 #define NETEM_OUTPUT_IVAL_ONLY(_ne) \
800 ((_ne->netem_flags & NETEMF_OUTPUT_IVAL_ONLY) != 0)
801
802 static struct heap *
heap_create(size_t limit)803 heap_create(size_t limit)
804 {
805 struct heap *h = NULL;
806
807 // verify limit
808 h = kalloc_type(struct heap, struct heap_elem, limit, Z_WAITOK | Z_ZERO);
809 if (h == NULL) {
810 return NULL;
811 }
812
813 h->limit = limit;
814 h->size = 0;
815
816 return h;
817 }
818
819 static void
heap_destroy(struct heap * h)820 heap_destroy(struct heap *h)
821 {
822 ASSERT(h->size == 0);
823
824 kfree_type(struct heap, struct heap_elem, h->limit, h);
825 }
826
827 #define HEAP_FATHER(child) (((child) - 1) / 2)
828 #define HEAP_SWAP(a, b, tmp) { tmp = a; a = b; b = tmp; }
829 #define HEAP_LEFT(x) (2 * (x) + 1)
830
831 static int
heap_insert(struct heap * h,uint64_t key,pktsched_pkt_t * pkt)832 heap_insert(struct heap *h, uint64_t key, pktsched_pkt_t *pkt)
833 {
834 ASSERT(h != NULL);
835
836 if (h->size == h->limit) {
837 return ENOBUFS;
838 }
839
840 uint64_t child, parent;
841 if (pkt == NULL) {
842 child = key;
843 ASSERT(child < h->size);
844 } else {
845 child = h->size;
846 h->p[child].key = key;
847 h->p[child].pkt = *pkt;
848 h->size++;
849 }
850
851 while (child > 0) {
852 struct heap_elem tmp;
853 parent = HEAP_FATHER(child);
854 if (h->p[parent].key < h->p[child].key) {
855 break;
856 }
857 HEAP_SWAP(h->p[child], h->p[parent], tmp);
858 child = parent;
859 }
860
861 return 0;
862 }
863
864 static int
heap_peek(struct heap * h,uint64_t * key,pktsched_pkt_t * pkt)865 heap_peek(struct heap *h, uint64_t *key, pktsched_pkt_t *pkt)
866 {
867 if (h->size == 0) {
868 return ENOENT;
869 }
870
871 *key = h->p[0].key;
872 *pkt = h->p[0].pkt;
873 return 0;
874 }
875
876 static int
heap_extract(struct heap * h,uint64_t * key,pktsched_pkt_t * pkt)877 heap_extract(struct heap *h, uint64_t *key, pktsched_pkt_t *pkt)
878 {
879 uint64_t child, parent, max;
880
881 if (h->size == 0) {
882 return ENOENT;
883 }
884
885 *key = h->p[0].key;
886 *pkt = h->p[0].pkt;
887
888 /* re-heapify */
889 parent = 0;
890 child = HEAP_LEFT(parent); /* start from left child */
891 max = h->size - 1;
892 while (child <= max) {
893 if (child != max && h->p[child + 1].key < h->p[child].key) {
894 child = child + 1; /* right child */
895 }
896 h->p[parent] = h->p[child];
897 parent = child;
898 child = HEAP_LEFT(child); /* left child for next loop */
899 }
900
901 h->size--;
902 if (parent != max) {
903 /* Fill hole with last entry, bubble up reusing insert code */
904 h->p[parent] = h->p[max];
905 _PKTSCHED_PKT_INIT(&h->p[max].pkt);
906 heap_insert(h, parent, NULL); /* this one cannot fail */
907 }
908
909 return 0;
910 }
911
912 static void
corruption_event(struct netem * ne,pktsched_pkt_t * pkt)913 corruption_event(struct netem *ne, pktsched_pkt_t *pkt)
914 {
915 struct corruption *corr = &ne->netem_corruption_model;
916 uint32_t rand;
917
918 if (corr->corruption_p == 0) {
919 return;
920 }
921
922 read_frandom(&rand, sizeof(rand));
923 rand %= NETEM_PSCALE;
924
925 if (rand < corr->corruption_p) {
926 NETEM_LOG(LOG_DEBUG, "| corrupted");
927 pktsched_corrupt_packet(pkt);
928 }
929 }
930
931 static bool
duplication_event(struct netem * ne)932 duplication_event(struct netem *ne)
933 {
934 struct duplication *dup = &ne->netem_duplication_model;
935 uint32_t rand;
936
937 if (dup->duplication_p == 0) {
938 return false;
939 }
940
941 read_frandom(&rand, sizeof(rand));
942 rand %= NETEM_PSCALE;
943
944 return rand < dup->duplication_p;
945 }
946
947 static bool
reordering_event(struct netem * ne)948 reordering_event(struct netem *ne)
949 {
950 struct reordering *reord = &ne->netem_reordering_model;
951 uint32_t rand;
952
953 if (reord->reordering_p != 0) {
954 read_frandom(&rand, sizeof(rand));
955 rand %= NETEM_PSCALE;
956 return rand < reord->reordering_p;
957 } else {
958 return false;
959 }
960 }
961
962 static uint64_t
latency_event(struct netem * ne,uint64_t now)963 latency_event(struct netem *ne, uint64_t now)
964 {
965 struct reordering *reord = &ne->netem_reordering_model;
966 struct latency *l = &ne->netem_latency_model;
967 bool reorder = false;
968 int32_t delay_ms = 0;
969 uint64_t abs_time_to_send = now, abs_interval;
970
971 if (reordering_event(ne)) {
972 reorder = true;
973 delay_ms += reord->reordering_ms;
974 NETEM_LOG(LOG_DEBUG, "| reorder %dms behind",
975 reord->reordering_ms);
976 }
977
978 if (l->latency_ms != 0 || l->jitter_ms != 0) {
979 delay_ms += norm_dist(l->latency_ms, l->jitter_ms);
980 NETEM_LOG(LOG_DEBUG, "| total delay %dms", delay_ms);
981 clock_interval_to_absolutetime_interval(delay_ms,
982 NSEC_PER_MSEC, &abs_interval);
983 abs_time_to_send += abs_interval;
984 }
985
986 if (l->prev_time_to_send != 0) {
987 /* make sure packet time to send is monotonic */
988 if (abs_time_to_send < l->prev_time_to_send) {
989 /* send this one immediately after previous packet */
990 abs_time_to_send = l->prev_time_to_send + 1;
991 }
992 }
993
994 if (!reorder) {
995 l->prev_time_to_send = abs_time_to_send;
996 }
997
998 return abs_time_to_send;
999 }
1000
1001 static bool
loss_event(struct netem * ne)1002 loss_event(struct netem *ne)
1003 {
1004 struct loss *loss = &ne->netem_loss_model;
1005 uint32_t rand;
1006
1007 if (loss->state == __NO_LOSS) {
1008 return false;
1009 }
1010
1011 read_frandom(&rand, sizeof(rand));
1012 rand %= NETEM_PSCALE;
1013
1014 switch (loss->state) {
1015 case GAP_RX:
1016 if (rand < loss->p_gr_gl) {
1017 loss->state = GAP_RX;
1018 return true;
1019 } else if (loss->p_gr_gl < rand &&
1020 rand < loss->p_gr_gl + loss->p_gr_bl) {
1021 loss->state = BURST_LOSS;
1022 return true;
1023 } else {
1024 loss->state = GAP_RX;
1025 return false;
1026 }
1027 case BURST_LOSS:
1028 if (rand < loss->p_bl_br) {
1029 loss->state = BURST_RX;
1030 return false;
1031 } else if (loss->p_bl_br < rand &&
1032 rand < loss->p_bl_br + loss->p_bl_gr) {
1033 loss->state = GAP_RX;
1034 return false;
1035 } else {
1036 loss->state = BURST_LOSS;
1037 return true;
1038 }
1039 case BURST_RX:
1040 if (rand < loss->p_br_bl) {
1041 loss->state = BURST_LOSS;
1042 return true;
1043 } else {
1044 loss->state = BURST_RX;
1045 return false;
1046 }
1047 case GAP_LOSS:
1048 /* This is instantaneous (stateless), should not be reached */
1049 default:
1050 VERIFY(0);
1051 break;
1052 }
1053
1054 /* not reached */
1055 VERIFY(0);
1056 return false;
1057 }
1058
1059 static uint64_t
rate_limiter(struct netem * ne,pktsched_pkt_t * pkt,uint64_t start_abs_time)1060 rate_limiter(struct netem *ne, pktsched_pkt_t *pkt, uint64_t start_abs_time)
1061 {
1062 struct bandwidth *bw = &ne->netem_bandwidth_model;
1063 uint32_t ipg_ns; /* inter-packet-gap */
1064 uint64_t abs_interval, abs_time_to_send;
1065
1066 if (bw->rate == UINT64_MAX) {
1067 return start_abs_time;
1068 }
1069
1070 if (bw->rate == 0) {
1071 return UINT64_MAX; /* INF to block traffic */
1072 }
1073
1074 ipg_ns = (pkt->pktsched_plen * 8 * NSEC_PER_SEC) / bw->rate;
1075 clock_interval_to_absolutetime_interval(ipg_ns, 1, &abs_interval);
1076 start_abs_time = MAX(start_abs_time, bw->prev_time_to_send);
1077 abs_time_to_send = bw->prev_time_to_send = start_abs_time + abs_interval;
1078
1079 return abs_time_to_send;
1080 }
1081
1082 static int
nlc_enqueue(struct netem * ne,classq_pkt_t * p,bool * pdrop)1083 nlc_enqueue(struct netem *ne, classq_pkt_t *p, bool *pdrop)
1084 {
1085 int ret = 0;
1086 int pkt_count = 1;
1087 uint64_t now, abs_time_to_send;
1088 pktsched_pkt_t pkt;
1089
1090 pktsched_pkt_encap(&pkt, p);
1091
1092 ASSERT(ne != NULL);
1093 ASSERT(pdrop != NULL);
1094 NETEM_MTX_LOCK(ne);
1095
1096 now = mach_absolute_time();
1097
1098 NETEM_LOG(LOG_DEBUG, "┌ begin p %p len %u, now %llu", p->cp_mbuf,
1099 pkt.pktsched_plen, now);
1100
1101 abs_time_to_send = rate_limiter(ne, &pkt, now);
1102 if (abs_time_to_send == UINT64_MAX) {
1103 NETEM_LOG(LOG_DEBUG, "| zero-bw blocked");
1104 goto done_no_output;
1105 }
1106
1107 if (loss_event(ne)) {
1108 NETEM_LOG(LOG_DEBUG, "| lost");
1109 goto done_no_output;
1110 }
1111
1112 if (duplication_event(ne)) {
1113 NETEM_LOG(LOG_DEBUG, "| dup'ed");
1114 pkt_count++;
1115 }
1116
1117 do {
1118 corruption_event(ne, &pkt);
1119
1120 abs_time_to_send = latency_event(ne, abs_time_to_send);
1121
1122 ret = heap_insert(ne->netem_heap, abs_time_to_send, &pkt);
1123 if (ret != 0) {
1124 NETEM_LOG(LOG_WARNING,
1125 "| heap_insert p %p err(%d), freeing pkt",
1126 p->cp_mbuf, ret);
1127 pktsched_free_pkt(&pkt);
1128 goto done;
1129 }
1130 NETEM_LOG(LOG_DEBUG, "| %p enqueued TTS %llu",
1131 pkt.pktsched_pkt_mbuf, abs_time_to_send);
1132 } while (--pkt_count > 0 &&
1133 __probable((ret = pktsched_clone_pkt(&pkt, &pkt)) == 0));
1134
1135 done:
1136 if (__probable(ne->netem_output_thread != THREAD_NULL)) {
1137 if (!(ne->netem_flags & (NETEMF_RUNNING |
1138 NETEMF_TERMINATING | NETEMF_TERMINATED)) &&
1139 !NETEM_OUTPUT_IVAL_ONLY(ne)) {
1140 NETEM_LOG(LOG_DEBUG, "| wakeup output thread");
1141 (void) thread_wakeup((caddr_t)&ne->netem_flags);
1142 }
1143 }
1144
1145 NETEM_MTX_UNLOCK(ne);
1146 NETEM_LOG(LOG_DEBUG, "└ %p end", p->cp_mbuf);
1147 return ret;
1148
1149 done_no_output:
1150 pktsched_free_pkt(&pkt);
1151 *pdrop = true;
1152 NETEM_MTX_UNLOCK(ne);
1153 NETEM_LOG(LOG_DEBUG, "└ %p end", p->cp_mbuf);
1154 return ret;
1155 }
1156
1157
1158 int
netem_enqueue(struct netem * ne,classq_pkt_t * p,bool * pdrop)1159 netem_enqueue(struct netem *ne, classq_pkt_t *p, bool *pdrop)
1160 {
1161 switch (p->cp_ptype) {
1162 case QP_MBUF: {
1163 struct pkthdr *pkth = &(p->cp_mbuf->m_pkthdr);
1164 pkth->pkt_flags &= ~PKTF_FLOW_ADV;
1165 break;
1166 }
1167 case QP_PACKET: {
1168 struct __kern_packet *kp = p->cp_kpkt;
1169 kp->pkt_pflags32 &= ~PKT_F_FLOW_ADV;
1170 break;
1171 }
1172 default:
1173 VERIFY(0);
1174 /* NOTREACHED */
1175 __builtin_unreachable();
1176 }
1177 return ne->netem_enqueue(ne, p, pdrop);
1178 }
1179
1180 static int
netem_dequeue_internal_locked(struct netem * ne,pktsched_pkt_t * pp,bool * more)1181 netem_dequeue_internal_locked(struct netem *ne, pktsched_pkt_t *pp,
1182 bool *more)
1183 {
1184 int ret = 0;
1185 uint64_t time_to_send;
1186 pktsched_pkt_t pkt;
1187
1188 ASSERT(ne != NULL);
1189 NETEM_MTX_LOCK_ASSERT_HELD(ne);
1190
1191 NETEM_LOG(LOG_DEBUG, "┌ begin");
1192
1193 ret = heap_peek(ne->netem_heap, &time_to_send, &pkt);
1194 if (ret != 0) {
1195 NETEM_LOG(LOG_DEBUG, "| heap empty");
1196 ret = ENOENT;
1197 goto done;
1198 }
1199
1200 if (time_to_send > mach_absolute_time()) {
1201 NETEM_LOG(LOG_DEBUG,
1202 "| TTS not yet reached: %llu now %llu",
1203 time_to_send, mach_absolute_time());
1204 *more = true;
1205 ret = EAGAIN;
1206 goto done;
1207 }
1208
1209 ret = heap_extract(ne->netem_heap, &time_to_send, &pkt);
1210 ASSERT(ret == 0);
1211 *pp = pkt;
1212
1213 done:
1214 NETEM_LOG(LOG_DEBUG, "└ end");
1215
1216 return ret;
1217 }
1218
1219 __attribute__((noreturn))
1220 static void
netem_output_thread_cont(void * v,wait_result_t w)1221 netem_output_thread_cont(void *v, wait_result_t w)
1222 {
1223 struct netem *__single ne = v;
1224 bool more = false;
1225 pktsched_pkt_t pkts[NETEM_MAX_BATCH_SIZE];
1226 uint32_t n_pkts = 0;
1227 int ret;
1228
1229 NETEM_MTX_LOCK(ne);
1230 ASSERT(!(ne->netem_flags & NETEMF_TERMINATED));
1231 ne->netem_flags |= NETEMF_RUNNING;
1232
1233 if (__improbable(w == THREAD_INTERRUPTED ||
1234 (ne->netem_flags & NETEMF_TERMINATING) != 0)) {
1235 ASSERT(!(ne->netem_flags & NETEMF_TERMINATED));
1236 ne->netem_flags &= ~(NETEMF_RUNNING | NETEMF_TERMINATING);
1237 ne->netem_flags |= NETEMF_TERMINATED;
1238
1239 NETEM_LOG(LOG_INFO, "%s output thread terminated",
1240 ne->netem_name);
1241
1242 if (ne->netem_flags & NETEMF_TERMINATEBLOCK) {
1243 thread_wakeup((caddr_t)&ne->netem_output_thread);
1244 }
1245
1246 NETEM_MTX_UNLOCK(ne);
1247
1248 /* for the extra refcnt from kernel_thread_start() */
1249 thread_deallocate(current_thread());
1250 /* this is the end */
1251 thread_terminate(current_thread());
1252 /* NOTREACHED */
1253 __builtin_unreachable();
1254 }
1255
1256 ASSERT(ne->netem_output != NULL);
1257 n_pkts = 0;
1258 for (;;) {
1259 ret = netem_dequeue_internal_locked(ne, &pkts[n_pkts],
1260 &more);
1261 if (__probable(ret == 0 &&
1262 ++n_pkts < ne->netem_output_max_batch_size)) {
1263 continue;
1264 }
1265
1266 if (__probable(n_pkts != 0)) {
1267 NETEM_MTX_UNLOCK(ne);
1268 (void) ne->netem_output(ne->netem_output_handle,
1269 pkts, n_pkts);
1270 NETEM_MTX_LOCK(ne);
1271 n_pkts = 0;
1272 }
1273 if (ret != 0) {
1274 break;
1275 }
1276 }
1277
1278 uint64_t deadline = TIMEOUT_WAIT_FOREVER;
1279 if (more || NETEM_OUTPUT_IVAL_ONLY(ne)) {
1280 uint32_t delay_ms = ne->netem_output_ival_ms;
1281 clock_interval_to_deadline(delay_ms, NSEC_PER_MSEC, &deadline);
1282 }
1283 (void) assert_wait_deadline(&ne->netem_flags, THREAD_UNINT, deadline);
1284 ne->netem_flags &= ~NETEMF_RUNNING;
1285 NETEM_MTX_UNLOCK(ne);
1286 (void) thread_block_parameter(netem_output_thread_cont, ne);
1287 /* NOTREACHED */
1288 __builtin_unreachable();
1289 }
1290
1291 __attribute__((noreturn))
1292 static void
netem_output_thread_func(void * v,wait_result_t w)1293 netem_output_thread_func(void *v, wait_result_t w)
1294 {
1295 #pragma unused(w)
1296 struct netem *__single ne = v;
1297 uint64_t wakeup;
1298
1299 ASSERT(ne->netem_output_thread == current_thread());
1300
1301 char *__null_terminated tname =
1302 __unsafe_null_terminated_from_indexable(ne->netem_name);
1303 thread_set_thread_name(current_thread(), tname);
1304
1305 NETEM_MTX_LOCK(ne);
1306 VERIFY(!(ne->netem_flags & NETEMF_RUNNING));
1307 clock_interval_to_deadline(1, NSEC_PER_MSEC, &wakeup);
1308 (void) assert_wait_deadline(&ne->netem_flags, THREAD_UNINT, wakeup);
1309 NETEM_MTX_UNLOCK(ne);
1310 thread_block_parameter(netem_output_thread_cont, ne);
1311 /* NOTREACHED */
1312 __builtin_unreachable();
1313 }
1314
1315 static struct netem *
netem_create(const char * name,struct ifnet * ifp,void * output_handle,netem_output_func_t output,uint32_t output_max_batch_size)1316 netem_create(const char *name, struct ifnet *ifp, void *output_handle,
1317 netem_output_func_t output, uint32_t output_max_batch_size)
1318 {
1319 struct netem *ne;
1320
1321 static_assert(IF_NETEM_MODEL_NULL == NETEM_MODEL_NULL);
1322 static_assert(IF_NETEM_MODEL_NLC == NETEM_MODEL_NLC);
1323
1324 ne = kalloc_type(struct netem, Z_WAITOK | Z_ZERO);
1325
1326 lck_mtx_init(&ne->netem_lock, &netem_lock_group, LCK_ATTR_NULL);
1327
1328 ne->netem_heap = heap_create(netem_heap_size);
1329 ne->netem_flags = NETEMF_INITIALIZED;
1330 ne->netem_output_handle = output_handle;
1331 ne->netem_output = output;
1332 ne->netem_output_max_batch_size =
1333 MIN(output_max_batch_size, NETEM_MAX_BATCH_SIZE);
1334 ne->netem_output_thread = THREAD_NULL;
1335 ne->netem_ifp = ifp;
1336 if (output != NULL) {
1337 strlcpy(ne->netem_name, name, sizeof(ne->netem_name));
1338 if (kernel_thread_start(netem_output_thread_func, ne,
1339 &ne->netem_output_thread) != KERN_SUCCESS) {
1340 panic_plain("%s can't create thread", ne->netem_name);
1341 }
1342 }
1343
1344
1345 return ne;
1346 }
1347
1348 void
netem_destroy(struct netem * ne)1349 netem_destroy(struct netem *ne)
1350 {
1351 uint64_t f = (1 * NSEC_PER_MSEC); /* 1 ms */
1352 uint64_t s = (1000 * NSEC_PER_MSEC); /* 1 sec */
1353 uint32_t i = 0;
1354 int ret = 0;
1355 uint64_t key = 0;
1356 pktsched_pkt_t pkt;
1357
1358 ASSERT(ne != NULL);
1359
1360 if (ne->netem_output_thread != THREAD_NULL) {
1361 ASSERT(ne->netem_flags & NETEMF_INITIALIZED);
1362 /* signal thread to begin self-termination */
1363 NETEM_MTX_LOCK(ne);
1364 ne->netem_flags |= NETEMF_TERMINATING;
1365
1366 /* and wait for thread to terminate */
1367 while (!(ne->netem_flags & NETEMF_TERMINATED)) {
1368 uint64_t t = 0;
1369 nanoseconds_to_absolutetime((i++ == 0) ? f : s, &t);
1370 clock_absolutetime_interval_to_deadline(t, &t);
1371 ASSERT(t != 0);
1372
1373 ne->netem_flags |= NETEMF_TERMINATEBLOCK;
1374 if (!(ne->netem_flags & NETEMF_RUNNING)) {
1375 thread_wakeup((caddr_t)&ne->netem_flags);
1376 }
1377 (void) assert_wait_deadline(&ne->netem_output_thread,
1378 THREAD_UNINT, t);
1379 NETEM_MTX_UNLOCK(ne);
1380 (void) thread_block(THREAD_CONTINUE_NULL);
1381 NETEM_MTX_LOCK(ne);
1382 ne->netem_flags &= ~NETEMF_TERMINATEBLOCK;
1383 }
1384 ASSERT(ne->netem_flags & NETEMF_TERMINATED);
1385 NETEM_MTX_UNLOCK(ne);
1386 ne->netem_output_thread = THREAD_NULL;
1387 }
1388 ASSERT(ne->netem_output_thread == THREAD_NULL);
1389
1390 lck_mtx_destroy(&ne->netem_lock, &netem_lock_group);
1391
1392 while ((ret = heap_extract(ne->netem_heap, &key, &pkt)) == 0) {
1393 pktsched_free_pkt(&pkt);
1394 }
1395 heap_destroy(ne->netem_heap);
1396
1397
1398 kfree_type(struct netem, ne);
1399 }
1400
1401 static int
netem_check_params(const struct if_netem_params * p)1402 netem_check_params(const struct if_netem_params *p)
1403 {
1404 if (p->ifnetem_model != IF_NETEM_MODEL_NLC) {
1405 NETEM_LOG(LOG_ERR, "| error: invalid scheduler model %d",
1406 p->ifnetem_model);
1407 return EINVAL;
1408 }
1409
1410 if (p->ifnetem_corruption_p > NETEM_PSCALE) {
1411 NETEM_LOG(LOG_ERR, "| error: corruption_p %d > %d",
1412 p->ifnetem_corruption_p, NETEM_PSCALE);
1413 return EINVAL;
1414 }
1415
1416 if (p->ifnetem_duplication_p > NETEM_PSCALE) {
1417 NETEM_LOG(LOG_ERR, "| error: duplication_p %d > %d",
1418 p->ifnetem_duplication_p, NETEM_PSCALE);
1419 return EINVAL;
1420 }
1421
1422 if (p->ifnetem_duplication_p > 0 &&
1423 p->ifnetem_latency_ms == 0) {
1424 /* we need to insert dup'ed packet with latency */
1425 NETEM_LOG(LOG_ERR,
1426 "| error: duplication needs latency param");
1427 return EINVAL;
1428 }
1429
1430 if (p->ifnetem_latency_ms > 1000) {
1431 NETEM_LOG(LOG_ERR,
1432 "| error: latency %d too big (> 1 sec)",
1433 p->ifnetem_latency_ms);
1434 return EINVAL;
1435 }
1436
1437 if (p->ifnetem_jitter_ms * 3 > p->ifnetem_latency_ms) {
1438 NETEM_LOG(LOG_ERR,
1439 "| error: jitter %dms too big (latency %dms)",
1440 p->ifnetem_jitter_ms, p->ifnetem_latency_ms);
1441 return EINVAL;
1442 }
1443
1444 /* if gr_gl == 0 (no loss), other prob should all be zero */
1445 if (p->ifnetem_loss_p_gr_gl == 0 &&
1446 (p->ifnetem_loss_p_gr_bl != 0 ||
1447 p->ifnetem_loss_p_bl_br != 0 ||
1448 p->ifnetem_loss_p_bl_gr != 0 ||
1449 p->ifnetem_loss_p_br_bl != 0)) {
1450 NETEM_LOG(LOG_ERR,
1451 "| error: loss params not all zero when p_gr_gl is zero");
1452 return EINVAL;
1453 }
1454
1455 if (p->ifnetem_loss_recovery_ms > 1000) {
1456 NETEM_LOG(LOG_ERR,
1457 "| error: loss recovery %dms too big",
1458 p->ifnetem_loss_recovery_ms);
1459 }
1460
1461 /* check state machine transition prob integrity */
1462 if (p->ifnetem_loss_p_gr_gl > NETEM_PSCALE ||
1463 /* gr_gl = NETEM_PSCALE for total loss */
1464 p->ifnetem_loss_p_gr_bl > NETEM_PSCALE ||
1465 p->ifnetem_loss_p_bl_br > NETEM_PSCALE ||
1466 p->ifnetem_loss_p_bl_gr > NETEM_PSCALE ||
1467 p->ifnetem_loss_p_br_bl > NETEM_PSCALE ||
1468 p->ifnetem_loss_p_gr_gl + p->ifnetem_loss_p_gr_bl > NETEM_PSCALE ||
1469 p->ifnetem_loss_p_bl_br + p->ifnetem_loss_p_bl_gr > NETEM_PSCALE) {
1470 NETEM_LOG(LOG_ERR, "| error: loss params too big");
1471 return EINVAL;
1472 }
1473
1474 if (p->ifnetem_reordering_p > NETEM_PSCALE) {
1475 NETEM_LOG(LOG_ERR, "| error: reordering %d > %d",
1476 p->ifnetem_reordering_p, NETEM_PSCALE);
1477 return EINVAL;
1478 }
1479
1480 if (p->ifnetem_output_ival_ms > 1000) {
1481 NETEM_LOG(LOG_ERR,
1482 "| error: output interval %dms too big",
1483 p->ifnetem_output_ival_ms);
1484 return EINVAL;
1485 }
1486
1487 return 0;
1488 }
1489
1490 static char *
netem_model_str(netem_model_t model)1491 netem_model_str(netem_model_t model)
1492 {
1493 switch (model) {
1494 case IF_NETEM_MODEL_NLC:
1495 return "Network link conditioner";
1496 default:
1497 return "unknown";
1498 }
1499 }
1500
1501 static void
netem_set_params(struct netem * ne,__unused struct ifnet * ifp,const struct if_netem_params * p)1502 netem_set_params(struct netem *ne, __unused struct ifnet *ifp,
1503 const struct if_netem_params *p)
1504 {
1505 NETEM_MTX_LOCK(ne);
1506
1507 ne->netem_model = (netem_model_t)p->ifnetem_model;
1508 switch (ne->netem_model) {
1509 case NETEM_MODEL_NLC:
1510 ne->netem_enqueue = nlc_enqueue;
1511 break;
1512 default:
1513 ASSERT(0);
1514 __builtin_unreachable();
1515 }
1516
1517 struct bandwidth *bw = &ne->netem_bandwidth_model;
1518 bw->rate = p->ifnetem_bandwidth_bps;
1519
1520 struct corruption *corr = &ne->netem_corruption_model;
1521 corr->corruption_p = p->ifnetem_corruption_p;
1522
1523 struct duplication *dup = &ne->netem_duplication_model;
1524 dup->duplication_p = p->ifnetem_duplication_p;
1525
1526 struct latency *late = &ne->netem_latency_model;
1527 late->latency_ms = p->ifnetem_latency_ms;
1528 late->jitter_ms = p->ifnetem_jitter_ms;
1529
1530 struct loss *loss = &ne->netem_loss_model;
1531 loss->state = GAP_RX;
1532 loss->p_gr_gl = p->ifnetem_loss_p_gr_gl;
1533 loss->p_gr_bl = p->ifnetem_loss_p_gr_bl;
1534 loss->p_bl_gr = p->ifnetem_loss_p_bl_gr;
1535 loss->p_bl_br = p->ifnetem_loss_p_bl_br;
1536 loss->p_br_bl = p->ifnetem_loss_p_br_bl;
1537
1538 loss->recovery_ms = p->ifnetem_loss_recovery_ms;
1539
1540 struct reordering *r = &ne->netem_reordering_model;
1541 r->reordering_p = p->ifnetem_reordering_p;
1542
1543 if (p->ifnetem_output_ival_ms != 0) {
1544 ne->netem_output_ival_ms = p->ifnetem_output_ival_ms;
1545 ne->netem_flags |= NETEMF_OUTPUT_IVAL_ONLY;
1546 } else {
1547 ne->netem_output_ival_ms = netem_output_ival_ms;
1548 }
1549
1550 if (NETEM_OUTPUT_IVAL_ONLY(ne)) {
1551 if (__probable(ne->netem_output_thread != THREAD_NULL)) {
1552 if (!(ne->netem_flags & (NETEMF_RUNNING |
1553 NETEMF_TERMINATING | NETEMF_TERMINATED))) {
1554 NETEM_LOG(LOG_DEBUG, "| wakeup output thread");
1555 (void) thread_wakeup((caddr_t)&ne->netem_flags);
1556 }
1557 }
1558 }
1559
1560 NETEM_LOG(LOG_INFO, "| %s set_params success", ne->netem_name);
1561 NETEM_LOG(LOG_INFO, "| model %s", netem_model_str(ne->netem_model));
1562 NETEM_LOG(LOG_INFO, "| bandwidth %llu bps %s", bw->rate,
1563 bw->rate == UINT64_MAX ? "no limit" : "");
1564 NETEM_LOG(LOG_INFO, "| corruption %d%%",
1565 corr->corruption_p);
1566 NETEM_LOG(LOG_INFO, "| duplication %d%%",
1567 dup->duplication_p);
1568 NETEM_LOG(LOG_INFO, "| latency_ms %d jitter_ms %d",
1569 late->latency_ms, late->jitter_ms);
1570 NETEM_LOG(LOG_INFO, "| loss p_gr_gl %d%%", loss->p_gr_gl);
1571 NETEM_LOG(LOG_INFO, "| p_gr_bl %d%%", loss->p_gr_bl);
1572 NETEM_LOG(LOG_INFO, "| p_bl_gr %d%%", loss->p_bl_gr);
1573 NETEM_LOG(LOG_INFO, "| p_bl_br %d%%", loss->p_bl_br);
1574 NETEM_LOG(LOG_INFO, "| p_br_bl %d%%", loss->p_br_bl);
1575 NETEM_LOG(LOG_INFO, "| recovery_ms %dms", loss->recovery_ms);
1576 NETEM_LOG(LOG_INFO, "| reordering %d%% %d ms behind",
1577 r->reordering_p, r->reordering_ms);
1578 NETEM_LOG(LOG_INFO, "| output ival %d ms",
1579 ne->netem_output_ival_ms);
1580
1581 NETEM_MTX_UNLOCK(ne);
1582 }
1583
1584 void
netem_get_params(struct netem * ne,struct if_netem_params * p)1585 netem_get_params(struct netem *ne, struct if_netem_params *p)
1586 {
1587 ASSERT(ne != NULL);
1588 NETEM_MTX_LOCK(ne);
1589
1590 p->ifnetem_model = (if_netem_model_t)ne->netem_model;
1591
1592 struct bandwidth *bw = &ne->netem_bandwidth_model;
1593 p->ifnetem_bandwidth_bps = bw->rate;
1594
1595 struct corruption *corr = &ne->netem_corruption_model;
1596 p->ifnetem_corruption_p = corr->corruption_p;
1597
1598 struct duplication *dup = &ne->netem_duplication_model;
1599 p->ifnetem_duplication_p = dup->duplication_p;
1600
1601 struct latency *late = &ne->netem_latency_model;
1602 p->ifnetem_latency_ms = late->latency_ms;
1603 p->ifnetem_jitter_ms = late->jitter_ms;
1604
1605 struct loss *loss = &ne->netem_loss_model;
1606 p->ifnetem_loss_p_gr_gl = loss->p_gr_gl;
1607 p->ifnetem_loss_p_gr_bl = loss->p_gr_bl;
1608 p->ifnetem_loss_p_bl_gr = loss->p_bl_gr;
1609 p->ifnetem_loss_p_bl_br = loss->p_bl_br;
1610 p->ifnetem_loss_p_br_bl = loss->p_br_bl;
1611 p->ifnetem_loss_recovery_ms = loss->recovery_ms;
1612
1613 struct reordering *r = &ne->netem_reordering_model;
1614 p->ifnetem_reordering_p = r->reordering_p;
1615
1616 NETEM_MTX_UNLOCK(ne);
1617 }
1618
1619 int
netem_config(struct netem ** ne,const char * __null_terminated name,struct ifnet * ifp,const struct if_netem_params * p,void * output_handle,netem_output_func_t * output_func,uint32_t output_max_batch_size)1620 netem_config(struct netem **ne, const char *__null_terminated name, struct ifnet *ifp,
1621 const struct if_netem_params *p, void *output_handle,
1622 netem_output_func_t *output_func, uint32_t output_max_batch_size)
1623 {
1624 struct netem *netem = NULL;
1625 bool enable = true;
1626 int ret = 0;
1627
1628 NETEM_LOG(LOG_INFO, "┌ begin %s", name);
1629
1630 if (p == NULL || (
1631 p->ifnetem_model == IF_NETEM_MODEL_NULL &&
1632 p->ifnetem_bandwidth_bps == 0 &&
1633 p->ifnetem_corruption_p == 0 &&
1634 p->ifnetem_duplication_p == 0 &&
1635 p->ifnetem_latency_ms == 0 &&
1636 p->ifnetem_jitter_ms == 0 &&
1637 p->ifnetem_loss_p_gr_gl == 0 &&
1638 p->ifnetem_loss_p_gr_bl == 0 &&
1639 p->ifnetem_loss_p_bl_br == 0 &&
1640 p->ifnetem_loss_p_bl_gr == 0 &&
1641 p->ifnetem_loss_p_br_bl == 0 &&
1642 p->ifnetem_loss_recovery_ms == 0 &&
1643 p->ifnetem_reordering_p == 0 &&
1644 p->ifnetem_output_ival_ms == 0)) {
1645 enable = false;
1646 }
1647
1648 if (enable) {
1649 if (p->ifnetem_model == IF_NETEM_MODEL_NLC &&
1650 (ifp->if_xflags & IFXF_NO_TRAFFIC_SHAPING) != 0) {
1651 NETEM_LOG(LOG_INFO, "| netem no traffic shapping %s on %s", name, if_name(ifp));
1652 goto done;
1653 }
1654
1655 ret = netem_check_params(p);
1656 if (ret != 0) {
1657 goto done;
1658 }
1659
1660 if (*ne == NULL) {
1661 NETEM_LOG(LOG_INFO, "| netem create %s", name);
1662 netem = netem_create(name, ifp, output_handle,
1663 output_func, output_max_batch_size);
1664 if (netem == NULL) {
1665 ret = ENOMEM;
1666 goto done;
1667 }
1668 os_atomic_store(ne, netem, release);
1669 }
1670 netem_set_params(*ne, ifp, p);
1671 } else {
1672 NETEM_LOG(LOG_INFO, "| netem disable %s", name);
1673 if (*ne != NULL) {
1674 netem = *ne;
1675 os_atomic_store(ne, (void *__single)NULL, release);
1676 NETEM_LOG(LOG_INFO, "| netem destroy %s", name);
1677 netem_destroy(netem);
1678 }
1679 ret = 0;
1680 }
1681
1682 done:
1683 NETEM_LOG(LOG_INFO, "└ ret %d", ret);
1684 return ret;
1685 }
1686
1687 #else /* !CONFIG_NETEM */
1688 NETEM_STUB
1689 #endif /* !CONFIG_NETEM */
1690 #else /* !SKYWALK */
1691 NETEM_STUB
1692 #endif /* !SKYWALK */
1693