test_bwmgt.c (16021B)
1 /* Copyright (c) 2018-2021, The Tor Project, Inc. */ 2 /* See LICENSE for licensing information */ 3 4 /** 5 * \file test_bwmgt.c 6 * \brief tests for bandwidth management / token bucket functions 7 */ 8 9 #define CONFIG_PRIVATE 10 #define CONNECTION_PRIVATE 11 #define DIRAUTH_SYS_PRIVATE 12 #define TOKEN_BUCKET_PRIVATE 13 14 #include "core/or/or.h" 15 16 #include "app/config/config.h" 17 #include "core/mainloop/connection.h" 18 #include "feature/dirauth/dirauth_sys.h" 19 #include "feature/dircommon/directory.h" 20 #include "feature/nodelist/microdesc.h" 21 #include "feature/nodelist/networkstatus.h" 22 #include "feature/nodelist/nodelist.h" 23 #include "feature/nodelist/routerlist.h" 24 #include "lib/crypt_ops/crypto_rand.h" 25 #include "lib/evloop/token_bucket.h" 26 #include "test/test.h" 27 #include "test/test_helpers.h" 28 29 #include "app/config/or_options_st.h" 30 #include "core/or/connection_st.h" 31 #include "feature/dirauth/dirauth_options_st.h" 32 #include "feature/nodelist/microdesc_st.h" 33 #include "feature/nodelist/networkstatus_st.h" 34 #include "feature/nodelist/routerinfo_st.h" 35 #include "feature/nodelist/routerstatus_st.h" 36 37 // an imaginary time, in timestamp units. Chosen so it will roll over. 38 static const uint32_t START_TS = UINT32_MAX-10; 39 static const int32_t KB = 1024; 40 static const uint32_t GB = (UINT64_C(1) << 30); 41 42 static or_options_t mock_options; 43 44 static const or_options_t * 45 mock_get_options(void) 46 { 47 return &mock_options; 48 } 49 50 static networkstatus_t *dummy_ns = NULL; 51 static networkstatus_t * 52 mock_networkstatus_get_latest_consensus(void) 53 { 54 return dummy_ns; 55 } 56 57 static networkstatus_t * 58 mock_networkstatus_get_latest_consensus_by_flavor(consensus_flavor_t f) 59 { 60 tor_assert(f == FLAV_MICRODESC); 61 return dummy_ns; 62 } 63 64 /* Number of address a single node_t can have. Default to the production 65 * value. This is to control the size of the bloom filter. */ 66 static int addr_per_node = 2; 67 static int 68 mock_get_estimated_address_per_node(void) 69 { 70 return addr_per_node; 71 } 72 73 static void 74 test_bwmgt_token_buf_init(void *arg) 75 { 76 (void)arg; 77 token_bucket_rw_t b; 78 79 token_bucket_rw_init(&b, 16*KB, 64*KB, START_TS); 80 // Burst is correct 81 tt_uint_op(b.cfg.burst, OP_EQ, 64*KB); 82 // Rate is correct, within 1 percent. 83 { 84 uint32_t ticks_per_sec = 85 (uint32_t) monotime_msec_to_approx_coarse_stamp_units(1000); 86 uint32_t rate_per_sec = (b.cfg.rate * ticks_per_sec / TICKS_PER_STEP); 87 88 tt_uint_op(rate_per_sec, OP_GT, 16*KB-160); 89 tt_uint_op(rate_per_sec, OP_LT, 16*KB+160); 90 } 91 // Bucket starts out full: 92 tt_uint_op(b.last_refilled_at_timestamp, OP_EQ, START_TS); 93 tt_int_op(b.read_bucket.bucket, OP_EQ, 64*KB); 94 95 done: 96 ; 97 } 98 99 static void 100 test_bwmgt_token_buf_adjust(void *arg) 101 { 102 (void)arg; 103 token_bucket_rw_t b; 104 105 token_bucket_rw_init(&b, 16*KB, 64*KB, START_TS); 106 107 uint32_t rate_orig = b.cfg.rate; 108 // Increasing burst 109 token_bucket_rw_adjust(&b, 16*KB, 128*KB); 110 tt_uint_op(b.cfg.rate, OP_EQ, rate_orig); 111 tt_uint_op(b.read_bucket.bucket, OP_EQ, 64*KB); 112 tt_uint_op(b.cfg.burst, OP_EQ, 128*KB); 113 114 // Decreasing burst but staying above bucket 115 token_bucket_rw_adjust(&b, 16*KB, 96*KB); 116 tt_uint_op(b.cfg.rate, OP_EQ, rate_orig); 117 tt_uint_op(b.read_bucket.bucket, OP_EQ, 64*KB); 118 tt_uint_op(b.cfg.burst, OP_EQ, 96*KB); 119 120 // Decreasing burst below bucket, 121 token_bucket_rw_adjust(&b, 16*KB, 48*KB); 122 tt_uint_op(b.cfg.rate, OP_EQ, rate_orig); 123 tt_uint_op(b.read_bucket.bucket, OP_EQ, 48*KB); 124 tt_uint_op(b.cfg.burst, OP_EQ, 48*KB); 125 126 // Changing rate. 127 token_bucket_rw_adjust(&b, 32*KB, 48*KB); 128 tt_uint_op(b.cfg.rate, OP_GE, rate_orig*2 - 10); 129 tt_uint_op(b.cfg.rate, OP_LE, rate_orig*2 + 10); 130 tt_uint_op(b.read_bucket.bucket, OP_EQ, 48*KB); 131 tt_uint_op(b.cfg.burst, OP_EQ, 48*KB); 132 133 done: 134 ; 135 } 136 137 static void 138 test_bwmgt_token_buf_dec(void *arg) 139 { 140 (void)arg; 141 token_bucket_rw_t b; 142 token_bucket_rw_init(&b, 16*KB, 64*KB, START_TS); 143 144 // full-to-not-full. 145 tt_int_op(0, OP_EQ, token_bucket_rw_dec_read(&b, KB)); 146 tt_int_op(b.read_bucket.bucket, OP_EQ, 63*KB); 147 148 // Full to almost-not-full 149 tt_int_op(0, OP_EQ, token_bucket_rw_dec_read(&b, 63*KB - 1)); 150 tt_int_op(b.read_bucket.bucket, OP_EQ, 1); 151 152 // almost-not-full to empty. 153 tt_int_op(1, OP_EQ, token_bucket_rw_dec_read(&b, 1)); 154 tt_int_op(b.read_bucket.bucket, OP_EQ, 0); 155 156 // reset bucket, try full-to-empty 157 token_bucket_rw_init(&b, 16*KB, 64*KB, START_TS); 158 tt_int_op(1, OP_EQ, token_bucket_rw_dec_read(&b, 64*KB)); 159 tt_int_op(b.read_bucket.bucket, OP_EQ, 0); 160 161 // reset bucket, try underflow. 162 token_bucket_rw_init(&b, 16*KB, 64*KB, START_TS); 163 tt_int_op(1, OP_EQ, token_bucket_rw_dec_read(&b, 64*KB + 1)); 164 tt_int_op(b.read_bucket.bucket, OP_EQ, -1); 165 166 // A second underflow does not make the bucket empty. 167 tt_int_op(0, OP_EQ, token_bucket_rw_dec_read(&b, 1000)); 168 tt_int_op(b.read_bucket.bucket, OP_EQ, -1001); 169 170 done: 171 ; 172 } 173 174 static void 175 test_bwmgt_token_buf_refill(void *arg) 176 { 177 (void)arg; 178 token_bucket_rw_t b; 179 const uint32_t BW_SEC = 180 (uint32_t)monotime_msec_to_approx_coarse_stamp_units(1000); 181 token_bucket_rw_init(&b, 16*KB, 64*KB, START_TS); 182 183 /* Make the buffer much emptier, then let one second elapse. */ 184 token_bucket_rw_dec_read(&b, 48*KB); 185 tt_int_op(b.read_bucket.bucket, OP_EQ, 16*KB); 186 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, START_TS + BW_SEC)); 187 tt_int_op(b.read_bucket.bucket, OP_GT, 32*KB - 300); 188 tt_int_op(b.read_bucket.bucket, OP_LT, 32*KB + 300); 189 190 /* Another half second. */ 191 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, START_TS + BW_SEC*3/2)); 192 tt_int_op(b.read_bucket.bucket, OP_GT, 40*KB - 400); 193 tt_int_op(b.read_bucket.bucket, OP_LT, 40*KB + 400); 194 tt_uint_op(b.last_refilled_at_timestamp, OP_EQ, START_TS + BW_SEC*3/2); 195 196 /* No time: nothing happens. */ 197 { 198 const uint32_t bucket_orig = b.read_bucket.bucket; 199 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, START_TS + BW_SEC*3/2)); 200 tt_int_op(b.read_bucket.bucket, OP_EQ, bucket_orig); 201 } 202 203 /* Another 30 seconds: fill the bucket. */ 204 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, 205 START_TS + BW_SEC*3/2 + BW_SEC*30)); 206 tt_int_op(b.read_bucket.bucket, OP_EQ, b.cfg.burst); 207 tt_uint_op(b.last_refilled_at_timestamp, OP_EQ, 208 START_TS + BW_SEC*3/2 + BW_SEC*30); 209 210 /* Another 30 seconds: nothing happens. */ 211 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, 212 START_TS + BW_SEC*3/2 + BW_SEC*60)); 213 tt_int_op(b.read_bucket.bucket, OP_EQ, b.cfg.burst); 214 tt_uint_op(b.last_refilled_at_timestamp, OP_EQ, 215 START_TS + BW_SEC*3/2 + BW_SEC*60); 216 217 /* Empty the bucket, let two seconds pass, and make sure that a refill is 218 * noticed. */ 219 tt_int_op(1, OP_EQ, token_bucket_rw_dec_read(&b, b.cfg.burst)); 220 tt_int_op(0, OP_EQ, b.read_bucket.bucket); 221 tt_int_op(1, OP_EQ, token_bucket_rw_refill(&b, 222 START_TS + BW_SEC*3/2 + BW_SEC*61)); 223 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, 224 START_TS + BW_SEC*3/2 + BW_SEC*62)); 225 tt_int_op(b.read_bucket.bucket, OP_GT, 32*KB-400); 226 tt_int_op(b.read_bucket.bucket, OP_LT, 32*KB+400); 227 228 /* Underflow the bucket, make sure we detect when it has tokens again. */ 229 tt_int_op(1, OP_EQ, 230 token_bucket_rw_dec_read(&b, b.read_bucket.bucket+16*KB)); 231 tt_int_op(-16*KB, OP_EQ, b.read_bucket.bucket); 232 // half a second passes... 233 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, START_TS + BW_SEC*64)); 234 tt_int_op(b.read_bucket.bucket, OP_GT, -8*KB-300); 235 tt_int_op(b.read_bucket.bucket, OP_LT, -8*KB+300); 236 // a second passes 237 tt_int_op(1, OP_EQ, token_bucket_rw_refill(&b, START_TS + BW_SEC*65)); 238 tt_int_op(b.read_bucket.bucket, OP_GT, 8*KB-400); 239 tt_int_op(b.read_bucket.bucket, OP_LT, 8*KB+400); 240 241 // We step a second backwards, and nothing happens. 242 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, START_TS + BW_SEC*64)); 243 tt_int_op(b.read_bucket.bucket, OP_GT, 8*KB-400); 244 tt_int_op(b.read_bucket.bucket, OP_LT, 8*KB+400); 245 246 /* A large amount of time passes, but less than the threshold at which 247 * we start detecting an assumed rollover event. This might be about 20 248 * days on a system with stamp units equal to 1ms. */ 249 uint32_t ts_stamp = START_TS + UINT32_MAX / 5; 250 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, ts_stamp)); 251 tt_int_op(b.read_bucket.bucket, OP_EQ, b.cfg.burst); 252 253 /* Fully empty the bucket and make sure it's filling once again */ 254 token_bucket_rw_dec_read(&b, b.cfg.burst); 255 tt_int_op(b.read_bucket.bucket, OP_EQ, 0); 256 tt_int_op(1, OP_EQ, token_bucket_rw_refill(&b, ts_stamp += BW_SEC)); 257 tt_int_op(b.read_bucket.bucket, OP_GT, 16*KB - 300); 258 tt_int_op(b.read_bucket.bucket, OP_LT, 16*KB + 300); 259 260 /* An even larger amount of time passes, which we take to be a 32-bit 261 * rollover event. The individual update is ignored, but the timestamp 262 * is still updated and the very next update should be accounted properly. */ 263 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, ts_stamp += UINT32_MAX/2)); 264 tt_int_op(b.read_bucket.bucket, OP_GT, 16*KB - 600); 265 tt_int_op(b.read_bucket.bucket, OP_LT, 16*KB + 600); 266 tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, ts_stamp += BW_SEC)); 267 tt_int_op(b.read_bucket.bucket, OP_GT, 32*KB - 600); 268 tt_int_op(b.read_bucket.bucket, OP_LT, 32*KB + 600); 269 270 done: 271 ; 272 } 273 274 /* Test some helper functions we use within the token bucket interface. */ 275 static void 276 test_bwmgt_token_buf_helpers(void *arg) 277 { 278 uint32_t ret; 279 280 (void) arg; 281 282 /* The returned value will be OS specific but in any case, it should be 283 * greater than 1 since we are passing 1GB/sec rate. */ 284 ret = rate_per_sec_to_rate_per_step(1 * GB); 285 tt_u64_op(ret, OP_GT, 1); 286 287 /* We default to 1 in case rate is 0. */ 288 ret = rate_per_sec_to_rate_per_step(0); 289 tt_u64_op(ret, OP_EQ, 1); 290 291 done: 292 ; 293 } 294 295 static void 296 test_bwmgt_dir_conn_global_write_low(void *arg) 297 { 298 bool ret; 299 int addr_family; 300 connection_t *conn = NULL; 301 routerstatus_t *rs = NULL; microdesc_t *md = NULL; routerinfo_t *ri = NULL; 302 tor_addr_t relay_addr; 303 dirauth_options_t *dirauth_opts = NULL; 304 305 (void) arg; 306 307 memset(&mock_options, 0, sizeof(or_options_t)); 308 MOCK(networkstatus_get_latest_consensus, 309 mock_networkstatus_get_latest_consensus); 310 MOCK(networkstatus_get_latest_consensus_by_flavor, 311 mock_networkstatus_get_latest_consensus_by_flavor); 312 MOCK(get_estimated_address_per_node, 313 mock_get_estimated_address_per_node); 314 315 /* 316 * The following is rather complex but that is what it takes to add a dummy 317 * consensus with a valid routerlist which will populate our node address 318 * set that we need to lookup to test the known relay code path. 319 * 320 * We MUST do that before we MOCK(get_options) else it is another world of 321 * complexity. 322 */ 323 324 /* This will be the address of our relay. */ 325 tor_addr_parse(&relay_addr, "1.2.3.4"); 326 327 /* We'll now add a relay into our routerlist and see if we let it. */ 328 dummy_ns = tor_malloc_zero(sizeof(*dummy_ns)); 329 dummy_ns->flavor = FLAV_MICRODESC; 330 dummy_ns->routerstatus_list = smartlist_new(); 331 332 md = tor_malloc_zero(sizeof(*md)); 333 ri = tor_malloc_zero(sizeof(*ri)); 334 rs = tor_malloc_zero(sizeof(*rs)); 335 crypto_rand(rs->identity_digest, sizeof(rs->identity_digest)); 336 crypto_rand(md->digest, sizeof(md->digest)); 337 memcpy(rs->descriptor_digest, md->digest, DIGEST256_LEN); 338 339 /* Set IP address. */ 340 tor_addr_copy(&rs->ipv4_addr, &relay_addr); 341 tor_addr_copy(&ri->ipv4_addr, &rs->ipv4_addr); 342 /* Add the rs to the consensus becoming a node_t. */ 343 smartlist_add(dummy_ns->routerstatus_list, rs); 344 345 /* Add all configured authorities (hardcoded) before we set the consensus so 346 * the address set exists. */ 347 ret = consider_adding_dir_servers(&mock_options, &mock_options); 348 tt_int_op(ret, OP_EQ, 0); 349 350 /* This will make the nodelist bloom filter very large 351 * (the_nodelist->node_addrs) so we will fail the contain test rarely. */ 352 addr_per_node = 1024; 353 354 nodelist_set_consensus(dummy_ns); 355 356 dirauth_opts = tor_malloc_zero(sizeof(dirauth_options_t)); 357 dirauth_opts->AuthDirRejectRequestsUnderLoad = 0; 358 dirauth_set_options(dirauth_opts); 359 360 /* Ok, now time to control which options we use. */ 361 MOCK(get_options, mock_get_options); 362 363 /* Set ourselves as an authoritative dir. */ 364 mock_options.AuthoritativeDir = 1; 365 mock_options.V3AuthoritativeDir = 1; 366 mock_options.UseDefaultFallbackDirs = 0; 367 368 /* This will set our global bucket to 1 byte and thus we will hit the 369 * banwdith limit in our test. */ 370 mock_options.BandwidthRate = 1; 371 mock_options.BandwidthBurst = 1; 372 373 /* Else an IPv4 address screams. */ 374 mock_options.ClientUseIPv4 = 1; 375 mock_options.ClientUseIPv6 = 1; 376 377 /* Initialize the global buckets. */ 378 connection_bucket_init(); 379 380 /* The address "127.0.0.1" is set with this helper. */ 381 conn = test_conn_get_connection(DIR_CONN_STATE_MIN_, CONN_TYPE_DIR, 382 DIR_PURPOSE_MIN_); 383 tt_assert(conn); 384 385 /* First try a non authority non relay IP thus a client but we are not 386 * configured to reject requests under load so we should get a false value 387 * that our limit is _not_ low. */ 388 addr_family = tor_addr_parse(&conn->addr, "1.1.1.1"); 389 tt_int_op(addr_family, OP_EQ, AF_INET); 390 ret = connection_dir_is_global_write_low(conn, INT_MAX); 391 tt_int_op(ret, OP_EQ, 0); 392 393 /* Now, we will reject requests under load so try again a non authority non 394 * relay IP thus a client. We should get a warning that our limit is too 395 * low. */ 396 dirauth_opts->AuthDirRejectRequestsUnderLoad = 1; 397 398 addr_family = tor_addr_parse(&conn->addr, "1.1.1.1"); 399 tt_int_op(addr_family, OP_EQ, AF_INET); 400 ret = connection_dir_is_global_write_low(conn, INT_MAX); 401 tt_int_op(ret, OP_EQ, 1); 402 403 /* Now, lets try with a connection address from moria1. It should always 404 * pass even though our limit is too low. */ 405 addr_family = tor_addr_parse(&conn->addr, "128.31.0.39"); 406 tt_int_op(addr_family, OP_EQ, AF_INET); 407 ret = connection_dir_is_global_write_low(conn, INT_MAX); 408 tt_int_op(ret, OP_EQ, 0); 409 410 /* IPv6 testing of gabelmoo. */ 411 addr_family = tor_addr_parse(&conn->addr, "[2001:638:a000:4140::ffff:189]"); 412 tt_int_op(addr_family, OP_EQ, AF_INET6); 413 ret = connection_dir_is_global_write_low(conn, INT_MAX); 414 tt_int_op(ret, OP_EQ, 0); 415 416 /* Lets retry with a known relay address. It should pass. Possible due to 417 * our consensus setting above. */ 418 memcpy(&conn->addr, &relay_addr, sizeof(tor_addr_t)); 419 ret = connection_dir_is_global_write_low(conn, INT_MAX); 420 tt_int_op(ret, OP_EQ, 0); 421 422 /* Lets retry with a random IP that is not an authority nor a relay. */ 423 addr_family = tor_addr_parse(&conn->addr, "1.2.3.4"); 424 tt_int_op(addr_family, OP_EQ, AF_INET); 425 ret = connection_dir_is_global_write_low(conn, INT_MAX); 426 tt_int_op(ret, OP_EQ, 0); 427 428 /* Finally, just make sure it still denies an IP if we are _not_ a v3 429 * directory authority. */ 430 mock_options.V3AuthoritativeDir = 0; 431 addr_family = tor_addr_parse(&conn->addr, "1.2.3.4"); 432 tt_int_op(addr_family, OP_EQ, AF_INET); 433 ret = connection_dir_is_global_write_low(conn, INT_MAX); 434 tt_int_op(ret, OP_EQ, 1); 435 436 /* Random IPv6 should not be allowed. */ 437 addr_family = tor_addr_parse(&conn->addr, "[CAFE::ACAB]"); 438 tt_int_op(addr_family, OP_EQ, AF_INET6); 439 ret = connection_dir_is_global_write_low(conn, INT_MAX); 440 tt_int_op(ret, OP_EQ, 1); 441 442 done: 443 connection_free_minimal(conn); 444 routerstatus_free(rs); routerinfo_free(ri); microdesc_free(md); 445 smartlist_clear(dummy_ns->routerstatus_list); 446 networkstatus_vote_free(dummy_ns); 447 448 UNMOCK(get_estimated_address_per_node); 449 UNMOCK(networkstatus_get_latest_consensus); 450 UNMOCK(networkstatus_get_latest_consensus_by_flavor); 451 UNMOCK(get_options); 452 } 453 454 #define BWMGT(name) \ 455 { #name, test_bwmgt_ ## name , TT_FORK, NULL, NULL } 456 457 struct testcase_t bwmgt_tests[] = { 458 BWMGT(token_buf_init), 459 BWMGT(token_buf_adjust), 460 BWMGT(token_buf_dec), 461 BWMGT(token_buf_refill), 462 BWMGT(token_buf_helpers), 463 464 BWMGT(dir_conn_global_write_low), 465 END_OF_TESTCASES 466 };