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 return ne->netem_enqueue(ne, p, pdrop);
1162 }
1163
1164 static int
netem_dequeue_internal_locked(struct netem * ne,pktsched_pkt_t * pp,bool * more)1165 netem_dequeue_internal_locked(struct netem *ne, pktsched_pkt_t *pp,
1166 bool *more)
1167 {
1168 int ret = 0;
1169 uint64_t time_to_send;
1170 pktsched_pkt_t pkt;
1171
1172 ASSERT(ne != NULL);
1173 NETEM_MTX_LOCK_ASSERT_HELD(ne);
1174
1175 NETEM_LOG(LOG_DEBUG, "┌ begin");
1176
1177 ret = heap_peek(ne->netem_heap, &time_to_send, &pkt);
1178 if (ret != 0) {
1179 NETEM_LOG(LOG_DEBUG, "| heap empty");
1180 ret = ENOENT;
1181 goto done;
1182 }
1183
1184 if (time_to_send > mach_absolute_time()) {
1185 NETEM_LOG(LOG_DEBUG,
1186 "| TTS not yet reached: %llu now %llu",
1187 time_to_send, mach_absolute_time());
1188 *more = true;
1189 ret = EAGAIN;
1190 goto done;
1191 }
1192
1193 ret = heap_extract(ne->netem_heap, &time_to_send, &pkt);
1194 ASSERT(ret == 0);
1195 *pp = pkt;
1196
1197 done:
1198 NETEM_LOG(LOG_DEBUG, "└ end");
1199
1200 return ret;
1201 }
1202
1203 __attribute__((noreturn))
1204 static void
netem_output_thread_cont(void * v,wait_result_t w)1205 netem_output_thread_cont(void *v, wait_result_t w)
1206 {
1207 struct netem *__single ne = v;
1208 bool more = false;
1209 pktsched_pkt_t pkts[NETEM_MAX_BATCH_SIZE];
1210 uint32_t n_pkts = 0;
1211 int ret;
1212
1213 NETEM_MTX_LOCK(ne);
1214 ASSERT(!(ne->netem_flags & NETEMF_TERMINATED));
1215 ne->netem_flags |= NETEMF_RUNNING;
1216
1217 if (__improbable(w == THREAD_INTERRUPTED ||
1218 (ne->netem_flags & NETEMF_TERMINATING) != 0)) {
1219 ASSERT(!(ne->netem_flags & NETEMF_TERMINATED));
1220 ne->netem_flags &= ~(NETEMF_RUNNING | NETEMF_TERMINATING);
1221 ne->netem_flags |= NETEMF_TERMINATED;
1222
1223 NETEM_LOG(LOG_INFO, "%s output thread terminated",
1224 ne->netem_name);
1225
1226 if (ne->netem_flags & NETEMF_TERMINATEBLOCK) {
1227 thread_wakeup((caddr_t)&ne->netem_output_thread);
1228 }
1229
1230 NETEM_MTX_UNLOCK(ne);
1231
1232 /* for the extra refcnt from kernel_thread_start() */
1233 thread_deallocate(current_thread());
1234 /* this is the end */
1235 thread_terminate(current_thread());
1236 /* NOTREACHED */
1237 __builtin_unreachable();
1238 }
1239
1240 ASSERT(ne->netem_output != NULL);
1241 n_pkts = 0;
1242 for (;;) {
1243 ret = netem_dequeue_internal_locked(ne, &pkts[n_pkts],
1244 &more);
1245 if (__probable(ret == 0 &&
1246 ++n_pkts < ne->netem_output_max_batch_size)) {
1247 continue;
1248 }
1249
1250 if (__probable(n_pkts != 0)) {
1251 NETEM_MTX_UNLOCK(ne);
1252 (void) ne->netem_output(ne->netem_output_handle,
1253 pkts, n_pkts);
1254 NETEM_MTX_LOCK(ne);
1255 n_pkts = 0;
1256 }
1257 if (ret != 0) {
1258 break;
1259 }
1260 }
1261
1262 uint64_t deadline = TIMEOUT_WAIT_FOREVER;
1263 if (more || NETEM_OUTPUT_IVAL_ONLY(ne)) {
1264 uint32_t delay_ms = ne->netem_output_ival_ms;
1265 clock_interval_to_deadline(delay_ms, NSEC_PER_MSEC, &deadline);
1266 }
1267 (void) assert_wait_deadline(&ne->netem_flags, THREAD_UNINT, deadline);
1268 ne->netem_flags &= ~NETEMF_RUNNING;
1269 NETEM_MTX_UNLOCK(ne);
1270 (void) thread_block_parameter(netem_output_thread_cont, ne);
1271 /* NOTREACHED */
1272 __builtin_unreachable();
1273 }
1274
1275 __attribute__((noreturn))
1276 static void
netem_output_thread_func(void * v,wait_result_t w)1277 netem_output_thread_func(void *v, wait_result_t w)
1278 {
1279 #pragma unused(w)
1280 struct netem *__single ne = v;
1281 uint64_t wakeup;
1282
1283 ASSERT(ne->netem_output_thread == current_thread());
1284
1285 char *__null_terminated tname =
1286 __unsafe_null_terminated_from_indexable(ne->netem_name);
1287 thread_set_thread_name(current_thread(), tname);
1288
1289 NETEM_MTX_LOCK(ne);
1290 VERIFY(!(ne->netem_flags & NETEMF_RUNNING));
1291 clock_interval_to_deadline(1, NSEC_PER_MSEC, &wakeup);
1292 (void) assert_wait_deadline(&ne->netem_flags, THREAD_UNINT, wakeup);
1293 NETEM_MTX_UNLOCK(ne);
1294 thread_block_parameter(netem_output_thread_cont, ne);
1295 /* NOTREACHED */
1296 __builtin_unreachable();
1297 }
1298
1299 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)1300 netem_create(const char *name, struct ifnet *ifp, void *output_handle,
1301 netem_output_func_t output, uint32_t output_max_batch_size)
1302 {
1303 struct netem *ne;
1304
1305 _CASSERT(IF_NETEM_MODEL_NULL == NETEM_MODEL_NULL);
1306 _CASSERT(IF_NETEM_MODEL_NLC == NETEM_MODEL_NLC);
1307
1308 ne = kalloc_type(struct netem, Z_WAITOK | Z_ZERO);
1309
1310 lck_mtx_init(&ne->netem_lock, &netem_lock_group, LCK_ATTR_NULL);
1311
1312 ne->netem_heap = heap_create(netem_heap_size);
1313 ne->netem_flags = NETEMF_INITIALIZED;
1314 ne->netem_output_handle = output_handle;
1315 ne->netem_output = output;
1316 ne->netem_output_max_batch_size =
1317 MIN(output_max_batch_size, NETEM_MAX_BATCH_SIZE);
1318 ne->netem_output_thread = THREAD_NULL;
1319 ne->netem_ifp = ifp;
1320 if (output != NULL) {
1321 strlcpy(ne->netem_name, name, sizeof(ne->netem_name));
1322 if (kernel_thread_start(netem_output_thread_func, ne,
1323 &ne->netem_output_thread) != KERN_SUCCESS) {
1324 panic_plain("%s can't create thread", ne->netem_name);
1325 }
1326 }
1327
1328
1329 return ne;
1330 }
1331
1332 void
netem_destroy(struct netem * ne)1333 netem_destroy(struct netem *ne)
1334 {
1335 uint64_t f = (1 * NSEC_PER_MSEC); /* 1 ms */
1336 uint64_t s = (1000 * NSEC_PER_MSEC); /* 1 sec */
1337 uint32_t i = 0;
1338 int ret = 0;
1339 uint64_t key = 0;
1340 pktsched_pkt_t pkt;
1341
1342 ASSERT(ne != NULL);
1343
1344 if (ne->netem_output_thread != THREAD_NULL) {
1345 ASSERT(ne->netem_flags & NETEMF_INITIALIZED);
1346 /* signal thread to begin self-termination */
1347 NETEM_MTX_LOCK(ne);
1348 ne->netem_flags |= NETEMF_TERMINATING;
1349
1350 /* and wait for thread to terminate */
1351 while (!(ne->netem_flags & NETEMF_TERMINATED)) {
1352 uint64_t t = 0;
1353 nanoseconds_to_absolutetime((i++ == 0) ? f : s, &t);
1354 clock_absolutetime_interval_to_deadline(t, &t);
1355 ASSERT(t != 0);
1356
1357 ne->netem_flags |= NETEMF_TERMINATEBLOCK;
1358 if (!(ne->netem_flags & NETEMF_RUNNING)) {
1359 thread_wakeup((caddr_t)&ne->netem_flags);
1360 }
1361 (void) assert_wait_deadline(&ne->netem_output_thread,
1362 THREAD_UNINT, t);
1363 NETEM_MTX_UNLOCK(ne);
1364 (void) thread_block(THREAD_CONTINUE_NULL);
1365 NETEM_MTX_LOCK(ne);
1366 ne->netem_flags &= ~NETEMF_TERMINATEBLOCK;
1367 }
1368 ASSERT(ne->netem_flags & NETEMF_TERMINATED);
1369 NETEM_MTX_UNLOCK(ne);
1370 ne->netem_output_thread = THREAD_NULL;
1371 }
1372 ASSERT(ne->netem_output_thread == THREAD_NULL);
1373
1374 lck_mtx_destroy(&ne->netem_lock, &netem_lock_group);
1375
1376 while ((ret = heap_extract(ne->netem_heap, &key, &pkt)) == 0) {
1377 pktsched_free_pkt(&pkt);
1378 }
1379 heap_destroy(ne->netem_heap);
1380
1381
1382 kfree_type(struct netem, ne);
1383 }
1384
1385 static int
netem_check_params(const struct if_netem_params * p)1386 netem_check_params(const struct if_netem_params *p)
1387 {
1388 if (p->ifnetem_model != IF_NETEM_MODEL_NLC) {
1389 NETEM_LOG(LOG_ERR, "| error: invalid scheduler model %d",
1390 p->ifnetem_model);
1391 return EINVAL;
1392 }
1393
1394 if (p->ifnetem_corruption_p > NETEM_PSCALE) {
1395 NETEM_LOG(LOG_ERR, "| error: corruption_p %d > %d",
1396 p->ifnetem_corruption_p, NETEM_PSCALE);
1397 return EINVAL;
1398 }
1399
1400 if (p->ifnetem_duplication_p > NETEM_PSCALE) {
1401 NETEM_LOG(LOG_ERR, "| error: duplication_p %d > %d",
1402 p->ifnetem_duplication_p, NETEM_PSCALE);
1403 return EINVAL;
1404 }
1405
1406 if (p->ifnetem_duplication_p > 0 &&
1407 p->ifnetem_latency_ms == 0) {
1408 /* we need to insert dup'ed packet with latency */
1409 NETEM_LOG(LOG_ERR,
1410 "| error: duplication needs latency param");
1411 return EINVAL;
1412 }
1413
1414 if (p->ifnetem_latency_ms > 1000) {
1415 NETEM_LOG(LOG_ERR,
1416 "| error: latency %d too big (> 1 sec)",
1417 p->ifnetem_latency_ms);
1418 return EINVAL;
1419 }
1420
1421 if (p->ifnetem_jitter_ms * 3 > p->ifnetem_latency_ms) {
1422 NETEM_LOG(LOG_ERR,
1423 "| error: jitter %dms too big (latency %dms)",
1424 p->ifnetem_jitter_ms, p->ifnetem_latency_ms);
1425 return EINVAL;
1426 }
1427
1428 /* if gr_gl == 0 (no loss), other prob should all be zero */
1429 if (p->ifnetem_loss_p_gr_gl == 0 &&
1430 (p->ifnetem_loss_p_gr_bl != 0 ||
1431 p->ifnetem_loss_p_bl_br != 0 ||
1432 p->ifnetem_loss_p_bl_gr != 0 ||
1433 p->ifnetem_loss_p_br_bl != 0)) {
1434 NETEM_LOG(LOG_ERR,
1435 "| error: loss params not all zero when p_gr_gl is zero");
1436 return EINVAL;
1437 }
1438
1439 if (p->ifnetem_loss_recovery_ms > 1000) {
1440 NETEM_LOG(LOG_ERR,
1441 "| error: loss recovery %dms too big",
1442 p->ifnetem_loss_recovery_ms);
1443 }
1444
1445 /* check state machine transition prob integrity */
1446 if (p->ifnetem_loss_p_gr_gl > NETEM_PSCALE ||
1447 /* gr_gl = NETEM_PSCALE for total loss */
1448 p->ifnetem_loss_p_gr_bl > NETEM_PSCALE ||
1449 p->ifnetem_loss_p_bl_br > NETEM_PSCALE ||
1450 p->ifnetem_loss_p_bl_gr > NETEM_PSCALE ||
1451 p->ifnetem_loss_p_br_bl > NETEM_PSCALE ||
1452 p->ifnetem_loss_p_gr_gl + p->ifnetem_loss_p_gr_bl > NETEM_PSCALE ||
1453 p->ifnetem_loss_p_bl_br + p->ifnetem_loss_p_bl_gr > NETEM_PSCALE) {
1454 NETEM_LOG(LOG_ERR, "| error: loss params too big");
1455 return EINVAL;
1456 }
1457
1458 if (p->ifnetem_reordering_p > NETEM_PSCALE) {
1459 NETEM_LOG(LOG_ERR, "| error: reordering %d > %d",
1460 p->ifnetem_reordering_p, NETEM_PSCALE);
1461 return EINVAL;
1462 }
1463
1464 if (p->ifnetem_output_ival_ms > 1000) {
1465 NETEM_LOG(LOG_ERR,
1466 "| error: output interval %dms too big",
1467 p->ifnetem_output_ival_ms);
1468 return EINVAL;
1469 }
1470
1471 return 0;
1472 }
1473
1474 static char *
netem_model_str(netem_model_t model)1475 netem_model_str(netem_model_t model)
1476 {
1477 switch (model) {
1478 case IF_NETEM_MODEL_NLC:
1479 return "Network link conditioner";
1480 default:
1481 return "unknown";
1482 }
1483 }
1484
1485 static void
netem_set_params(struct netem * ne,__unused struct ifnet * ifp,const struct if_netem_params * p)1486 netem_set_params(struct netem *ne, __unused struct ifnet *ifp,
1487 const struct if_netem_params *p)
1488 {
1489 NETEM_MTX_LOCK(ne);
1490
1491 ne->netem_model = (netem_model_t)p->ifnetem_model;
1492 switch (ne->netem_model) {
1493 case NETEM_MODEL_NLC:
1494 ne->netem_enqueue = nlc_enqueue;
1495 break;
1496 default:
1497 ASSERT(0);
1498 __builtin_unreachable();
1499 }
1500
1501 struct bandwidth *bw = &ne->netem_bandwidth_model;
1502 bw->rate = p->ifnetem_bandwidth_bps;
1503
1504 struct corruption *corr = &ne->netem_corruption_model;
1505 corr->corruption_p = p->ifnetem_corruption_p;
1506
1507 struct duplication *dup = &ne->netem_duplication_model;
1508 dup->duplication_p = p->ifnetem_duplication_p;
1509
1510 struct latency *late = &ne->netem_latency_model;
1511 late->latency_ms = p->ifnetem_latency_ms;
1512 late->jitter_ms = p->ifnetem_jitter_ms;
1513
1514 struct loss *loss = &ne->netem_loss_model;
1515 loss->state = GAP_RX;
1516 loss->p_gr_gl = p->ifnetem_loss_p_gr_gl;
1517 loss->p_gr_bl = p->ifnetem_loss_p_gr_bl;
1518 loss->p_bl_gr = p->ifnetem_loss_p_bl_gr;
1519 loss->p_bl_br = p->ifnetem_loss_p_bl_br;
1520 loss->p_br_bl = p->ifnetem_loss_p_br_bl;
1521
1522 loss->recovery_ms = p->ifnetem_loss_recovery_ms;
1523
1524 struct reordering *r = &ne->netem_reordering_model;
1525 r->reordering_p = p->ifnetem_reordering_p;
1526
1527 if (p->ifnetem_output_ival_ms != 0) {
1528 ne->netem_output_ival_ms = p->ifnetem_output_ival_ms;
1529 ne->netem_flags |= NETEMF_OUTPUT_IVAL_ONLY;
1530 } else {
1531 ne->netem_output_ival_ms = netem_output_ival_ms;
1532 }
1533
1534 if (NETEM_OUTPUT_IVAL_ONLY(ne)) {
1535 if (__probable(ne->netem_output_thread != THREAD_NULL)) {
1536 if (!(ne->netem_flags & (NETEMF_RUNNING |
1537 NETEMF_TERMINATING | NETEMF_TERMINATED))) {
1538 NETEM_LOG(LOG_DEBUG, "| wakeup output thread");
1539 (void) thread_wakeup((caddr_t)&ne->netem_flags);
1540 }
1541 }
1542 }
1543
1544 NETEM_LOG(LOG_INFO, "| %s set_params success", ne->netem_name);
1545 NETEM_LOG(LOG_INFO, "| model %s", netem_model_str(ne->netem_model));
1546 NETEM_LOG(LOG_INFO, "| bandwidth %llu bps %s", bw->rate,
1547 bw->rate == UINT64_MAX ? "no limit" : "");
1548 NETEM_LOG(LOG_INFO, "| corruption %d%%",
1549 corr->corruption_p);
1550 NETEM_LOG(LOG_INFO, "| duplication %d%%",
1551 dup->duplication_p);
1552 NETEM_LOG(LOG_INFO, "| latency_ms %d jitter_ms %d",
1553 late->latency_ms, late->jitter_ms);
1554 NETEM_LOG(LOG_INFO, "| loss p_gr_gl %d%%", loss->p_gr_gl);
1555 NETEM_LOG(LOG_INFO, "| p_gr_bl %d%%", loss->p_gr_bl);
1556 NETEM_LOG(LOG_INFO, "| p_bl_gr %d%%", loss->p_bl_gr);
1557 NETEM_LOG(LOG_INFO, "| p_bl_br %d%%", loss->p_bl_br);
1558 NETEM_LOG(LOG_INFO, "| p_br_bl %d%%", loss->p_br_bl);
1559 NETEM_LOG(LOG_INFO, "| recovery_ms %dms", loss->recovery_ms);
1560 NETEM_LOG(LOG_INFO, "| reordering %d%% %d ms behind",
1561 r->reordering_p, r->reordering_ms);
1562 NETEM_LOG(LOG_INFO, "| output ival %d ms",
1563 ne->netem_output_ival_ms);
1564
1565 NETEM_MTX_UNLOCK(ne);
1566 }
1567
1568 void
netem_get_params(struct netem * ne,struct if_netem_params * p)1569 netem_get_params(struct netem *ne, struct if_netem_params *p)
1570 {
1571 ASSERT(ne != NULL);
1572 NETEM_MTX_LOCK(ne);
1573
1574 p->ifnetem_model = (if_netem_model_t)ne->netem_model;
1575
1576 struct bandwidth *bw = &ne->netem_bandwidth_model;
1577 p->ifnetem_bandwidth_bps = bw->rate;
1578
1579 struct corruption *corr = &ne->netem_corruption_model;
1580 p->ifnetem_corruption_p = corr->corruption_p;
1581
1582 struct duplication *dup = &ne->netem_duplication_model;
1583 p->ifnetem_duplication_p = dup->duplication_p;
1584
1585 struct latency *late = &ne->netem_latency_model;
1586 p->ifnetem_latency_ms = late->latency_ms;
1587 p->ifnetem_jitter_ms = late->jitter_ms;
1588
1589 struct loss *loss = &ne->netem_loss_model;
1590 p->ifnetem_loss_p_gr_gl = loss->p_gr_gl;
1591 p->ifnetem_loss_p_gr_bl = loss->p_gr_bl;
1592 p->ifnetem_loss_p_bl_gr = loss->p_bl_gr;
1593 p->ifnetem_loss_p_bl_br = loss->p_bl_br;
1594 p->ifnetem_loss_p_br_bl = loss->p_br_bl;
1595 p->ifnetem_loss_recovery_ms = loss->recovery_ms;
1596
1597 struct reordering *r = &ne->netem_reordering_model;
1598 p->ifnetem_reordering_p = r->reordering_p;
1599
1600 NETEM_MTX_UNLOCK(ne);
1601 }
1602
1603 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)1604 netem_config(struct netem **ne, const char *__null_terminated name, struct ifnet *ifp,
1605 const struct if_netem_params *p, void *output_handle,
1606 netem_output_func_t *output_func, uint32_t output_max_batch_size)
1607 {
1608 struct netem *netem = NULL;
1609 bool enable = true;
1610 int ret = 0;
1611
1612 NETEM_LOG(LOG_INFO, "┌ begin %s", name);
1613
1614 if (p == NULL || (
1615 p->ifnetem_model == IF_NETEM_MODEL_NULL &&
1616 p->ifnetem_bandwidth_bps == 0 &&
1617 p->ifnetem_corruption_p == 0 &&
1618 p->ifnetem_duplication_p == 0 &&
1619 p->ifnetem_latency_ms == 0 &&
1620 p->ifnetem_jitter_ms == 0 &&
1621 p->ifnetem_loss_p_gr_gl == 0 &&
1622 p->ifnetem_loss_p_gr_bl == 0 &&
1623 p->ifnetem_loss_p_bl_br == 0 &&
1624 p->ifnetem_loss_p_bl_gr == 0 &&
1625 p->ifnetem_loss_p_br_bl == 0 &&
1626 p->ifnetem_loss_recovery_ms == 0 &&
1627 p->ifnetem_reordering_p == 0 &&
1628 p->ifnetem_output_ival_ms == 0)) {
1629 enable = false;
1630 }
1631
1632 if (enable) {
1633 if (p->ifnetem_model == IF_NETEM_MODEL_NLC &&
1634 (ifp->if_xflags & IFXF_NO_TRAFFIC_SHAPING) != 0) {
1635 NETEM_LOG(LOG_INFO, "| netem no traffic shapping %s on %s", name, if_name(ifp));
1636 goto done;
1637 }
1638
1639 ret = netem_check_params(p);
1640 if (ret != 0) {
1641 goto done;
1642 }
1643
1644 if (*ne == NULL) {
1645 NETEM_LOG(LOG_INFO, "| netem create %s", name);
1646 netem = netem_create(name, ifp, output_handle,
1647 output_func, output_max_batch_size);
1648 if (netem == NULL) {
1649 ret = ENOMEM;
1650 goto done;
1651 }
1652 os_atomic_store(ne, netem, release);
1653 }
1654 netem_set_params(*ne, ifp, p);
1655 } else {
1656 NETEM_LOG(LOG_INFO, "| netem disable %s", name);
1657 if (*ne != NULL) {
1658 netem = *ne;
1659 os_atomic_store(ne, (void *__single)NULL, release);
1660 NETEM_LOG(LOG_INFO, "| netem destroy %s", name);
1661 netem_destroy(netem);
1662 }
1663 ret = 0;
1664 }
1665
1666 done:
1667 NETEM_LOG(LOG_INFO, "└ ret %d", ret);
1668 return ret;
1669 }
1670
1671 #else /* !CONFIG_NETEM */
1672 NETEM_STUB
1673 #endif /* !CONFIG_NETEM */
1674 #else /* !SKYWALK */
1675 NETEM_STUB
1676 #endif /* !SKYWALK */
1677