src/test/test_bwmgt.c

   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 };