src/test/test_bwmgt.c

   1 /* Copyright (c) 2018-2020, 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 ridiculous amount of time passes.
 247   tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, INT32_MAX));
 248   tt_int_op(b.read_bucket.bucket, OP_EQ, b.cfg.burst);
 249
 250  done:
 251   ;
 252 }
 253
 254 /* Test some helper functions we use within the token bucket interface. */
 255 static void
 256 test_bwmgt_token_buf_helpers(void *arg)
 257 {
 258   uint32_t ret;
 259
 260   (void) arg;
 261
 262   /* The returned value will be OS specific but in any case, it should be
 263    * greater than 1 since we are passing 1GB/sec rate. */
 264   ret = rate_per_sec_to_rate_per_step(1 * GB);
 265   tt_u64_op(ret, OP_GT, 1);
 266
 267   /* We default to 1 in case rate is 0. */
 268   ret = rate_per_sec_to_rate_per_step(0);
 269   tt_u64_op(ret, OP_EQ, 1);
 270
 271  done:
 272   ;
 273 }
 274
 275 static void
 276 test_bwmgt_dir_conn_global_write_low(void *arg)
 277 {
 278   bool ret;
 279   int addr_family;
 280   connection_t *conn = NULL;
 281   routerstatus_t *rs = NULL; microdesc_t *md = NULL; routerinfo_t *ri = NULL;
 282   tor_addr_t relay_addr;
 283   dirauth_options_t *dirauth_opts = NULL;
 284
 285   (void) arg;
 286
 287   memset(&mock_options, 0, sizeof(or_options_t));
 288   MOCK(networkstatus_get_latest_consensus,
 289        mock_networkstatus_get_latest_consensus);
 290   MOCK(networkstatus_get_latest_consensus_by_flavor,
 291        mock_networkstatus_get_latest_consensus_by_flavor);
 292   MOCK(get_estimated_address_per_node,
 293        mock_get_estimated_address_per_node);
 294
 295   /*
 296    * The following is rather complex but that is what it takes to add a dummy
 297    * consensus with a valid routerlist which will populate our node address
 298    * set that we need to lookup to test the known relay code path.
 299    *
 300    * We MUST do that before we MOCK(get_options) else it is another world of
 301    * complexity.
 302    */
 303
 304   /* This will be the address of our relay. */
 305   tor_addr_parse(&relay_addr, "1.2.3.4");
 306
 307   /* We'll now add a relay into our routerlist and see if we let it. */
 308   dummy_ns = tor_malloc_zero(sizeof(*dummy_ns));
 309   dummy_ns->flavor = FLAV_MICRODESC;
 310   dummy_ns->routerstatus_list = smartlist_new();
 311
 312   md = tor_malloc_zero(sizeof(*md));
 313   ri = tor_malloc_zero(sizeof(*ri));
 314   rs = tor_malloc_zero(sizeof(*rs));
 315   crypto_rand(rs->identity_digest, sizeof(rs->identity_digest));
 316   crypto_rand(md->digest, sizeof(md->digest));
 317   memcpy(rs->descriptor_digest, md->digest, DIGEST256_LEN);
 318
 319   /* Set IP address. */
 320   tor_addr_copy(&rs->ipv4_addr, &relay_addr);
 321   tor_addr_copy(&ri->ipv4_addr, &rs->ipv4_addr);
 322   /* Add the rs to the consensus becoming a node_t. */
 323   smartlist_add(dummy_ns->routerstatus_list, rs);
 324
 325   /* Add all configured authorities (hardcoded) before we set the consensus so
 326    * the address set exists. */
 327   ret = consider_adding_dir_servers(&mock_options, &mock_options);
 328   tt_int_op(ret, OP_EQ, 0);
 329
 330   /* This will make the nodelist bloom filter very large
 331    * (the_nodelist->node_addrs) so we will fail the contain test rarely. */
 332   addr_per_node = 1024;
 333
 334   nodelist_set_consensus(dummy_ns);
 335
 336   dirauth_opts = tor_malloc_zero(sizeof(dirauth_options_t));
 337   dirauth_opts->AuthDirRejectRequestsUnderLoad = 0;
 338   dirauth_set_options(dirauth_opts);
 339
 340   /* Ok, now time to control which options we use. */
 341   MOCK(get_options, mock_get_options);
 342
 343   /* Set ourselves as an authoritative dir. */
 344   mock_options.AuthoritativeDir = 1;
 345   mock_options.V3AuthoritativeDir = 1;
 346   mock_options.UseDefaultFallbackDirs = 0;
 347
 348   /* This will set our global bucket to 1 byte and thus we will hit the
 349    * banwdith limit in our test. */
 350   mock_options.BandwidthRate = 1;
 351   mock_options.BandwidthBurst = 1;
 352
 353   /* Else an IPv4 address screams. */
 354   mock_options.ClientUseIPv4 = 1;
 355   mock_options.ClientUseIPv6 = 1;
 356
 357   /* Initialize the global buckets. */
 358   connection_bucket_init();
 359
 360   /* The address "127.0.0.1" is set with this helper. */
 361   conn = test_conn_get_connection(DIR_CONN_STATE_MIN_, CONN_TYPE_DIR,
 362                                   DIR_PURPOSE_MIN_);
 363   tt_assert(conn);
 364
 365   /* First try a non authority non relay IP thus a client but we are not
 366    * configured to reject requests under load so we should get a false value
 367    * that our limit is _not_ low. */
 368   addr_family = tor_addr_parse(&conn->addr, "1.1.1.1");
 369   tt_int_op(addr_family, OP_EQ, AF_INET);
 370   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 371   tt_int_op(ret, OP_EQ, 0);
 372
 373   /* Now, we will reject requests under load so try again a non authority non
 374    * relay IP thus a client. We should get a warning that our limit is too
 375    * low. */
 376   dirauth_opts->AuthDirRejectRequestsUnderLoad = 1;
 377
 378   addr_family = tor_addr_parse(&conn->addr, "1.1.1.1");
 379   tt_int_op(addr_family, OP_EQ, AF_INET);
 380   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 381   tt_int_op(ret, OP_EQ, 1);
 382
 383   /* Now, lets try with a connection address from moria1. It should always
 384    * pass even though our limit is too low. */
 385   addr_family = tor_addr_parse(&conn->addr, "128.31.0.39");
 386   tt_int_op(addr_family, OP_EQ, AF_INET);
 387   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 388   tt_int_op(ret, OP_EQ, 0);
 389
 390   /* IPv6 testing of gabelmoo. */
 391   addr_family = tor_addr_parse(&conn->addr, "[2001:638:a000:4140::ffff:189]");
 392   tt_int_op(addr_family, OP_EQ, AF_INET6);
 393   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 394   tt_int_op(ret, OP_EQ, 0);
 395
 396   /* Lets retry with a known relay address. It should pass. Possible due to
 397    * our consensus setting above. */
 398   memcpy(&conn->addr, &relay_addr, sizeof(tor_addr_t));
 399   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 400   tt_int_op(ret, OP_EQ, 0);
 401
 402   /* Lets retry with a random IP that is not an authority nor a relay. */
 403   addr_family = tor_addr_parse(&conn->addr, "1.2.3.4");
 404   tt_int_op(addr_family, OP_EQ, AF_INET);
 405   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 406   tt_int_op(ret, OP_EQ, 0);
 407
 408   /* Finally, just make sure it still denies an IP if we are _not_ a v3
 409    * directory authority. */
 410   mock_options.V3AuthoritativeDir = 0;
 411   addr_family = tor_addr_parse(&conn->addr, "1.2.3.4");
 412   tt_int_op(addr_family, OP_EQ, AF_INET);
 413   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 414   tt_int_op(ret, OP_EQ, 1);
 415
 416   /* Random IPv6 should not be allowed. */
 417   addr_family = tor_addr_parse(&conn->addr, "[CAFE::ACAB]");
 418   tt_int_op(addr_family, OP_EQ, AF_INET6);
 419   ret = connection_dir_is_global_write_low(conn, INT_MAX);
 420   tt_int_op(ret, OP_EQ, 1);
 421
 422  done:
 423   connection_free_minimal(conn);
 424   routerstatus_free(rs); routerinfo_free(ri); microdesc_free(md);
 425   smartlist_clear(dummy_ns->routerstatus_list);
 426   networkstatus_vote_free(dummy_ns);
 427
 428   UNMOCK(get_estimated_address_per_node);
 429   UNMOCK(networkstatus_get_latest_consensus);
 430   UNMOCK(networkstatus_get_latest_consensus_by_flavor);
 431   UNMOCK(get_options);
 432 }
 433
 434 #define BWMGT(name)                                          \
 435   { #name, test_bwmgt_ ## name , TT_FORK, NULL, NULL }
 436
 437 struct testcase_t bwmgt_tests[] = {
 438   BWMGT(token_buf_init),
 439   BWMGT(token_buf_adjust),
 440   BWMGT(token_buf_dec),
 441   BWMGT(token_buf_refill),
 442   BWMGT(token_buf_helpers),
 443
 444   BWMGT(dir_conn_global_write_low),
 445   END_OF_TESTCASES
 446 };