diff options
Diffstat (limited to '')
| -rw-r--r-- | tests/ngtcp2_rob_test.c | 552 |
1 files changed, 552 insertions, 0 deletions
diff --git a/tests/ngtcp2_rob_test.c b/tests/ngtcp2_rob_test.c new file mode 100644 index 0000000..93a2641 --- /dev/null +++ b/tests/ngtcp2_rob_test.c @@ -0,0 +1,552 @@ +/* + * ngtcp2 + * + * Copyright (c) 2017 ngtcp2 contributors + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ +#include "ngtcp2_rob_test.h" + +#include <CUnit/CUnit.h> + +#include "ngtcp2_rob.h" +#include "ngtcp2_test_helper.h" +#include "ngtcp2_mem.h" + +void test_ngtcp2_rob_push(void) { + const ngtcp2_mem *mem = ngtcp2_mem_default(); + ngtcp2_rob rob; + int rv; + uint8_t data[256]; + ngtcp2_rob_gap *g; + ngtcp2_ksl_it it; + + /* Check range overlapping */ + ngtcp2_rob_init(&rob, 64, mem); + + rv = ngtcp2_rob_push(&rob, 34567, data, 145); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(0 == g->range.begin); + CU_ASSERT(34567 == g->range.end); + + ngtcp2_ksl_it_next(&it); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(34567 + 145 == g->range.begin); + CU_ASSERT(UINT64_MAX == g->range.end); + + ngtcp2_ksl_it_next(&it); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + rv = ngtcp2_rob_push(&rob, 34565, data, 1); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(0 == g->range.begin); + CU_ASSERT(34565 == g->range.end); + + ngtcp2_ksl_it_next(&it); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(34566 == g->range.begin); + CU_ASSERT(34567 == g->range.end); + + rv = ngtcp2_rob_push(&rob, 34563, data, 1); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(0 == g->range.begin); + CU_ASSERT(34563 == g->range.end); + + ngtcp2_ksl_it_next(&it); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(34564 == g->range.begin); + CU_ASSERT(34565 == g->range.end); + + rv = ngtcp2_rob_push(&rob, 34561, data, 151); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(0 == g->range.begin); + CU_ASSERT(34561 == g->range.end); + + ngtcp2_ksl_it_next(&it); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(34567 + 145 == g->range.begin); + CU_ASSERT(UINT64_MAX == g->range.end); + + ngtcp2_ksl_it_next(&it); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + ngtcp2_rob_free(&rob); + + /* Check removing prefix */ + ngtcp2_rob_init(&rob, 64, mem); + + rv = ngtcp2_rob_push(&rob, 0, data, 123); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(123 == g->range.begin); + CU_ASSERT(UINT64_MAX == g->range.end); + + ngtcp2_ksl_it_next(&it); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + ngtcp2_rob_free(&rob); + + /* Check removing suffix */ + ngtcp2_rob_init(&rob, 64, mem); + + rv = ngtcp2_rob_push(&rob, UINT64_MAX - 123, data, 123); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(0 == g->range.begin); + CU_ASSERT(UINT64_MAX - 123 == g->range.end); + + ngtcp2_ksl_it_next(&it); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + ngtcp2_rob_free(&rob); +} + +static ngtcp2_range randkeys[] = { + {25996, 26260}, {9431, 9555}, {9113, 9417}, {2992, 3408}, + {35761, 36019}, {38891, 39113}, {30074, 30325}, {9525, 9953}, + {31708, 31944}, {24554, 24864}, {13097, 13472}, {47253, 47400}, + {18424, 18742}, {4618, 4889}, {40871, 41076}, {17642, 18068}, + {47496, 47588}, {1226, 1283}, {17904, 18248}, {9221, 9488}, + {8621, 8773}, {27912, 28344}, {5878, 6121}, {37336, 37545}, + {15403, 15557}, {29314, 29450}, {2342, 2595}, {34000, 34356}, + {46428, 46828}, {40624, 40703}, {47014, 47319}, {13353, 13635}, + {14466, 14682}, {22446, 22654}, {10035, 10140}, {1005, 1410}, + {3741, 4133}, {45734, 46053}, {7954, 8214}, {32666, 32796}, + {45236, 45531}, {32100, 32501}, {25466, 25850}, {2845, 3179}, + {23525, 23991}, {46367, 46459}, {37712, 38164}, {8506, 8680}, + {31702, 31752}, {33364, 33825}, {14284, 14614}, {22928, 23344}, + {29058, 29155}, {36639, 37014}, {29133, 29445}, {31071, 31478}, + {40074, 40370}, {1263, 1383}, {7908, 8181}, {40426, 40716}, + {4830, 5053}, {38241, 38645}, {51197, 51401}, {36180, 36301}, + {14920, 15262}, {5707, 5882}, {32697, 32948}, {42324, 42791}, + {1543, 1732}, {11037, 11395}, {36534, 36707}, {26093, 26322}, + {41862, 42213}, {1373, 1745}, {31322, 31706}, {45474, 45851}, + {19333, 19701}, {49172, 49524}, {10641, 10932}, {17459, 17630}, + {5560, 5936}, {7657, 7988}, {3300, 3357}, {2496, 2600}, + {46018, 46173}, {43127, 43239}, {48949, 49036}, {45094, 45412}, + {8405, 8738}, {8687, 9168}, {41405, 41759}, {22014, 22474}, + {16097, 16426}, {29611, 29931}, {46054, 46250}, {26305, 26545}, + {13696, 13964}, {26899, 26981}, {30797, 30936}, {34125, 34235}, + {50016, 50058}, {46775, 47005}, {4891, 5106}, {12720, 12994}, + {44623, 44967}, {33597, 34060}, {50796, 51295}, {18862, 19242}, + {36166, 36249}, {22237, 22583}, {18188, 18586}, {21376, 21447}, + {49563, 49800}, {10121, 10272}, {39156, 39275}, {17609, 17866}, + {47609, 47829}, {34311, 34631}, {2144, 2433}, {34692, 34824}, + {8309, 8476}, {26969, 27447}, {40651, 40952}, {11906, 12116}, + {22467, 22864}, {35535, 35941}, {33061, 33259}, {21006, 21364}, + {15212, 15504}, {6954, 7356}, {6126, 6405}, {29268, 29514}, + {35221, 35505}, {4163, 4350}, {17374, 17519}, {16170, 16511}, + {37142, 37440}, {6288, 6556}, {27795, 28092}, {35381, 35476}, + {1186, 1455}, {39834, 40197}, {3471, 3906}, {46871, 47242}, + {40258, 40406}, {0, 306}, {31852, 32133}, {23314, 23408}, + {37494, 37625}, {48742, 48990}, {37616, 37905}, {18615, 18991}, + {2561, 2921}, {47767, 48139}, {39616, 39792}, {44791, 45046}, + {2770, 3067}, {16697, 17083}, {9216, 9427}, {37661, 37774}, + {14666, 14976}, {31547, 31819}, {36052, 36356}, {34989, 35285}, + {1651, 2028}, {36264, 36515}, {10257, 10551}, {24381, 24628}, + {28428, 28726}, {4242, 4576}, {44972, 45107}, {12970, 13213}, + {19539, 19828}, {42541, 42763}, {20349, 20630}, {20138, 20418}, + {10884, 11138}, {2717, 2908}, {8292, 8399}, {712, 1101}, + {44451, 44741}, {28660, 28946}, {40955, 41253}, {29424, 29864}, + {14177, 14446}, {30219, 30632}, {24757, 25012}, {47991, 48306}, + {42054, 42252}, {3984, 4419}, {42304, 42506}, {7160, 7543}, + {2004, 2152}, {9777, 10105}, {15724, 16008}, {11263, 11573}, + {15066, 15239}, {12108, 12336}, {17138, 17570}, {30472, 30714}, + {41197, 41294}, {24294, 24496}, {17371, 17514}, {11426, 11749}, + {25223, 25474}, {18083, 18345}, {27611, 27919}, {8116, 8261}, + {40317, 40373}, {46652, 47026}, {18082, 18151}, {19808, 19970}, + {46627, 46885}, {11646, 11789}, {1498, 1687}, {35907, 36081}, + {36340, 36593}, {1255, 1311}, {43485, 43551}, {6586, 6895}, + {10331, 10467}, {26803, 26998}, {14007, 14360}, {35951, 36120}, + {37327, 37592}, {35419, 35724}, {50379, 50514}, {37251, 37489}, + {27313, 27752}, {27502, 27845}, {36608, 36732}, {41751, 42057}, + {19118, 19267}, {16529, 16926}, {49794, 50066}, {37378, 37699}, + {7440, 7552}, {10418, 10650}, {50184, 50635}, {44350, 44579}, + {8178, 8502}, {33838, 34017}, {11582, 11864}, {11756, 11785}, + {42136, 42328}, {39404, 39545}, {13924, 14209}, {29411, 29627}, + {10836, 11139}, {40332, 40598}, {26097, 26561}, {5422, 5512}, + {30687, 30849}, {4399, 4726}, {50679, 50762}, {41224, 41439}, + {46023, 46129}, {22690, 23010}, {37920, 38085}, {25885, 26249}, + {51047, 51185}, {21508, 21904}, {6731, 7010}, {38144, 38493}, + {47648, 47886}, {120, 603}, {49964, 50182}, {43503, 43765}, + {24092, 24436}, {19204, 19509}, {19668, 19930}, {6815, 6963}, + {10552, 10775}, {949, 1239}, {36976, 37348}, {34806, 34901}, + {19939, 20308}, {42245, 42329}, {42700, 43067}, {13821, 14054}, + {28109, 28331}, {32929, 33212}, {23736, 24036}, {31969, 32240}, + {12326, 12612}, {5999, 6132}, {42871, 43283}, {33204, 33496}, + {5757, 5991}, {46826, 46927}, {4994, 5278}, {47371, 47713}, + {20886, 21106}, {38457, 38794}, {48451, 48789}, {34146, 34343}, + {45911, 46248}, {48215, 48615}, {43970, 44131}, {30886, 31216}, + {50135, 50292}, {3726, 3854}, {39041, 39408}, {48617, 48756}, + {46205, 46590}, {39766, 39923}, {20835, 21106}, {43716, 44066}, + {45665, 45789}, {12549, 12755}, {23366, 23752}, {17864, 17942}, + {28288, 28528}, {2744, 2941}, {49355, 49605}, {34527, 34816}, + {23092, 23447}, {5832, 5912}, {21146, 21478}, {30784, 30884}, + {28221, 28469}, {34944, 35047}, {23956, 24126}, {7538, 7890}, + {32496, 32803}, {16404, 16607}, {37968, 38277}, {7399, 7574}, + {28605, 28842}, {50454, 50851}, {20581, 20845}, {21395, 21705}, + {50726, 50871}, {11953, 12278}, {533, 822}, {5298, 5658}, + {48707, 48914}, {21760, 22223}, {1889, 2146}, {6409, 6842}, + {44094, 44473}, {18003, 18336}, {41550, 41926}, {50042, 50136}, + {38646, 38835}, {5425, 5693}, {48967, 49383}, {376, 596}, + {47514, 47704}, {43238, 43663}, {25440, 25655}, {25652, 26050}, + {16909, 17232}, {41312, 41490}, {5909, 6049}, {3153, 3523}, + {27877, 28046}, {26715, 26810}, {10031, 10108}, {32282, 32620}, + {8934, 9219}, {5133, 5493}, {26666, 26787}, {45324, 45630}, + {34880, 35008}, {20823, 20920}, {39571, 39704}, {15523, 15869}, + {4360, 4637}, {46199, 46384}, {35991, 36242}, {46852, 46931}, + {39218, 39644}, {11785, 12029}, {27225, 27366}, {29820, 30097}, + {36778, 37072}, {9871, 10255}, {51065, 51208}, {38775, 39102}, + {39446, 39712}, {33856, 34083}, {28853, 29289}, {526, 666}, + {37510, 37697}, {13455, 13855}, {25648, 25691}, {10694, 11041}, + {26441, 26889}, {18821, 19058}, {3357, 3590}, {15915, 16276}, + {37706, 37934}, {24970, 25281}, {43951, 44124}, {35874, 36128}, +}; + +void test_ngtcp2_rob_push_random(void) { + const ngtcp2_mem *mem = ngtcp2_mem_default(); + ngtcp2_rob rob; + int rv; + uint8_t data[512]; + size_t i; + + ngtcp2_rob_init(&rob, 1024 * 1024, mem); + for (i = 0; i < ngtcp2_arraylen(randkeys); ++i) { + rv = ngtcp2_rob_push(&rob, randkeys[i].begin, &data[0], + (size_t)ngtcp2_range_len(&randkeys[i])); + + CU_ASSERT(0 == rv); + } + + CU_ASSERT(51401 == ngtcp2_rob_first_gap_offset(&rob)); + + ngtcp2_rob_free(&rob); +} + +void test_ngtcp2_rob_data_at(void) { + const ngtcp2_mem *mem = ngtcp2_mem_default(); + ngtcp2_rob rob; + int rv; + uint8_t data[256]; + size_t i; + const uint8_t *p; + size_t len; + ngtcp2_rob_data *d; + ngtcp2_ksl_it it; + ngtcp2_rob_gap *g; + + for (i = 0; i < sizeof(data); ++i) { + data[i] = (uint8_t)i; + } + + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 3, &data[3], 13); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(0 == len); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 3); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(16 == len); + + for (i = 0; i < len; ++i) { + CU_ASSERT((uint8_t)i == *(p + i)); + } + + ngtcp2_rob_pop(&rob, 0, len); + + rv = ngtcp2_rob_push(&rob, 16, &data[16], 5); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 16); + + CU_ASSERT(5 == len); + + for (i = 16; i < len; ++i) { + CU_ASSERT((uint8_t)i == *(p + i)); + } + + ngtcp2_rob_free(&rob); + + /* Verify the case where data spans over multiple chunks */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 47); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(16 == len); + + ngtcp2_rob_pop(&rob, 0, len); + len = ngtcp2_rob_data_at(&rob, &p, 16); + + CU_ASSERT(16 == len); + + ngtcp2_rob_pop(&rob, 16, len); + len = ngtcp2_rob_data_at(&rob, &p, 32); + + CU_ASSERT(15 == len); + + ngtcp2_rob_pop(&rob, 32, len); + ngtcp2_rob_free(&rob); + + /* Verify the case where new offset comes before the existing + chunk */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 17, &data[17], 2); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(0 == len); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 3); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(3 == len); + + ngtcp2_rob_pop(&rob, 0, len); + + len = ngtcp2_rob_data_at(&rob, &p, 3); + + CU_ASSERT(0 == len); + + ngtcp2_rob_free(&rob); + + /* Verify the case where new offset comes after the existing + chunk */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 3); + + CU_ASSERT(0 == rv); + + rv = ngtcp2_rob_push(&rob, 16, &data[16], 32); + + CU_ASSERT(0 == rv); + + it = ngtcp2_ksl_begin(&rob.dataksl); + ngtcp2_ksl_it_next(&it); + d = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(16 == d->range.begin); + + ngtcp2_ksl_it_next(&it); + d = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(32 == d->range.begin); + + ngtcp2_ksl_it_next(&it); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + ngtcp2_rob_free(&rob); + + /* Severely scattered data */ + ngtcp2_rob_init(&rob, 16, mem); + + for (i = 0; i < sizeof(data); i += 2) { + rv = ngtcp2_rob_push(&rob, i, &data[i], 1); + + CU_ASSERT(0 == rv); + } + + for (i = 1; i < sizeof(data); i += 2) { + rv = ngtcp2_rob_push(&rob, i, &data[i], 1); + + CU_ASSERT(0 == rv); + } + + for (i = 0; i < sizeof(data) / 16; ++i) { + len = ngtcp2_rob_data_at(&rob, &p, i * 16); + + CU_ASSERT(16 == len); + + ngtcp2_rob_pop(&rob, i * 16, len); + } + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(256 == g->range.begin); + + it = ngtcp2_ksl_begin(&rob.dataksl); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + ngtcp2_rob_free(&rob); + + /* Verify the case where chunk is reused if it is not fully used */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 5); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(5 == len); + + ngtcp2_rob_pop(&rob, 0, len); + + rv = ngtcp2_rob_push(&rob, 2, &data[2], 8); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 5); + + CU_ASSERT(5 == len); + + ngtcp2_rob_pop(&rob, 5, len); + + ngtcp2_rob_free(&rob); + + /* Verify the case where 2nd push covers already processed region */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 16); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 0); + + CU_ASSERT(16 == len); + + ngtcp2_rob_pop(&rob, 0, len); + + rv = ngtcp2_rob_push(&rob, 0, &data[0], 32); + + CU_ASSERT(0 == rv); + + len = ngtcp2_rob_data_at(&rob, &p, 16); + + CU_ASSERT(16 == len); + + ngtcp2_rob_pop(&rob, 16, len); + + ngtcp2_rob_free(&rob); +} + +void test_ngtcp2_rob_remove_prefix(void) { + const ngtcp2_mem *mem = ngtcp2_mem_default(); + ngtcp2_rob rob; + ngtcp2_rob_gap *g; + ngtcp2_rob_data *d; + ngtcp2_ksl_it it; + uint8_t data[256]; + int rv; + + /* Removing data which spans multiple chunks */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 1, &data[1], 32); + + CU_ASSERT(0 == rv); + + ngtcp2_rob_remove_prefix(&rob, 33); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(33 == g->range.begin); + + it = ngtcp2_ksl_begin(&rob.dataksl); + d = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(32 == d->range.begin); + + ngtcp2_rob_free(&rob); + + /* Remove an entire gap */ + ngtcp2_rob_init(&rob, 16, mem); + + rv = ngtcp2_rob_push(&rob, 1, &data[1], 3); + + CU_ASSERT(0 == rv); + + rv = ngtcp2_rob_push(&rob, 5, &data[5], 2); + + CU_ASSERT(0 == rv); + + ngtcp2_rob_remove_prefix(&rob, 16); + + it = ngtcp2_ksl_begin(&rob.gapksl); + g = ngtcp2_ksl_it_get(&it); + + CU_ASSERT(16 == g->range.begin); + + ngtcp2_ksl_it_next(&it); + + CU_ASSERT(ngtcp2_ksl_it_end(&it)); + + ngtcp2_rob_free(&rob); +} |