| 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 |
| 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(buffer: &rand, numBytes: 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 * |
| 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 |
| 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 |
| 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 |
| 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 |
| 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, key: parent, NULL); /* this one cannot fail */ |
| 907 | } |
| 908 | |
| 909 | return 0; |
| 910 | } |
| 911 | |
| 912 | static void |
| 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(buffer: &rand, numBytes: 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 |
| 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(buffer: &rand, numBytes: sizeof(rand)); |
| 942 | rand %= NETEM_PSCALE; |
| 943 | |
| 944 | return rand < dup->duplication_p; |
| 945 | } |
| 946 | |
| 947 | static bool |
| 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(buffer: &rand, numBytes: sizeof(rand)); |
| 955 | rand %= NETEM_PSCALE; |
| 956 | return rand < reord->reordering_p; |
| 957 | } else { |
| 958 | return false; |
| 959 | } |
| 960 | } |
| 961 | |
| 962 | static uint64_t |
| 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(mean: l->latency_ms, stdvar: l->jitter_ms); |
| 980 | NETEM_LOG(LOG_DEBUG, "| total delay %dms", delay_ms); |
| 981 | clock_interval_to_absolutetime_interval(interval: delay_ms, |
| 982 | NSEC_PER_MSEC, result: &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 |
| 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(buffer: &rand, numBytes: 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 |
| 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(interval: ipg_ns, scale_factor: 1, result: &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 |
| 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: &pkt, start_abs_time: 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: &pkt); |
| 1119 | |
| 1120 | abs_time_to_send = latency_event(ne, now: abs_time_to_send); |
| 1121 | |
| 1122 | ret = heap_insert(h: ne->netem_heap, key: abs_time_to_send, pkt: &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 |
| 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 |
| 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(h: ne->netem_heap, key: &time_to_send, pkt: &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(h: ne->netem_heap, key: &time_to_send, pkt: &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 |
| 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(thread: 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, pp: &pkts[n_pkts], |
| 1244 | more: &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(interval: delay_ms, NSEC_PER_MSEC, result: &deadline); |
| 1266 | } |
| 1267 | (void) assert_wait_deadline(event: &ne->netem_flags, THREAD_UNINT, deadline); |
| 1268 | ne->netem_flags &= ~NETEMF_RUNNING; |
| 1269 | NETEM_MTX_UNLOCK(ne); |
| 1270 | (void) thread_block_parameter(continuation: netem_output_thread_cont, parameter: ne); |
| 1271 | /* NOTREACHED */ |
| 1272 | __builtin_unreachable(); |
| 1273 | } |
| 1274 | |
| 1275 | __attribute__((noreturn)) |
| 1276 | static void |
| 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(th: current_thread(), name: ne->netem_name); |
| 1285 | |
| 1286 | NETEM_MTX_LOCK(ne); |
| 1287 | VERIFY(!(ne->netem_flags & NETEMF_RUNNING)); |
| 1288 | clock_interval_to_deadline(interval: 1, NSEC_PER_MSEC, result: &wakeup); |
| 1289 | (void) assert_wait_deadline(event: &ne->netem_flags, THREAD_UNINT, deadline: wakeup); |
| 1290 | NETEM_MTX_UNLOCK(ne); |
| 1291 | thread_block_parameter(continuation: netem_output_thread_cont, parameter: ne); |
| 1292 | /* NOTREACHED */ |
| 1293 | __builtin_unreachable(); |
| 1294 | } |
| 1295 | |
| 1296 | static struct netem * |
| 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(lck: &ne->netem_lock, grp: &netem_lock_group, LCK_ATTR_NULL); |
| 1308 | |
| 1309 | ne->netem_heap = heap_create(limit: 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(dst: ne->netem_name, src: name, n: sizeof(ne->netem_name)); |
| 1319 | if (kernel_thread_start(continuation: netem_output_thread_func, parameter: ne, |
| 1320 | new_thread: &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 |
| 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(nanoseconds: (i++ == 0) ? f : s, result: &t); |
| 1351 | clock_absolutetime_interval_to_deadline(abstime: t, result: &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(event: &ne->netem_output_thread, |
| 1359 | THREAD_UNINT, deadline: 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(lck: &ne->netem_lock, grp: &netem_lock_group); |
| 1372 | |
| 1373 | while ((ret = heap_extract(h: ne->netem_heap, key: &key, pkt: &pkt)) == 0) { |
| 1374 | pktsched_free_pkt(&pkt); |
| 1375 | } |
| 1376 | heap_destroy(h: ne->netem_heap); |
| 1377 | |
| 1378 | |
| 1379 | kfree_type(struct netem, ne); |
| 1380 | } |
| 1381 | |
| 1382 | static int |
| 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 * |
| 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 |
| 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 |
| 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 |
| 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: output_func, output_max_batch_size); |
| 1645 | if (netem == NULL) { |
| 1646 | ret = ENOMEM; |
| 1647 | goto done; |
| 1648 | } |
| 1649 | os_atomic_store(ne, netem, release); |
| 1650 | } |
| 1651 | netem_set_params(ne: *ne, ifp, p); |
| 1652 | } else { |
| 1653 | NETEM_LOG(LOG_INFO, "| netem disable %s", name); |
| 1654 | if (*ne != NULL) { |
| 1655 | netem = *ne; |
| 1656 | os_atomic_store(ne, NULL, release); |
| 1657 | NETEM_LOG(LOG_INFO, "| netem destroy %s", name); |
| 1658 | netem_destroy(ne: 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 |
Generated on 2024-Jun-06 from project xnu revision 10063.121.3
Powered by 
Code Browser 2.1
Generator usage only permitted with license.