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