Home | History | Annotate | Download | only in iomgr 
      1 /*
      2  *
      3  * Copyright 2015 gRPC authors.
      4  *
      5  * Licensed under the Apache License, Version 2.0 (the "License");
      6  * you may not use this file except in compliance with the License.
      7  * You may obtain a copy of the License at
      8  *
      9  *     http://www.apache.org/licenses/LICENSE-2.0
     10  *
     11  * Unless required by applicable law or agreed to in writing, software
     12  * distributed under the License is distributed on an "AS IS" BASIS,
     13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14  * See the License for the specific language governing permissions and
     15  * limitations under the License.
     16  *
     17  */
     18 
     19 #include "src/core/lib/iomgr/port.h"
     20 
     21 #include "src/core/lib/iomgr/timer_heap.h"
     22 
     23 #include <stdlib.h>
     24 #include <string.h>
     25 
     26 #include <grpc/support/alloc.h>
     27 #include <grpc/support/log.h>
     28 
     29 #include "src/core/lib/gpr/useful.h"
     30 #include "test/core/util/test_config.h"
     31 
     32 static gpr_atm random_deadline(void) { return rand(); }
     33 
     34 static grpc_timer* create_test_elements(size_t num_elements) {
     35   grpc_timer* elems =
     36       static_cast<grpc_timer*>(gpr_malloc(num_elements * sizeof(grpc_timer)));
     37   size_t i;
     38   for (i = 0; i < num_elements; i++) {
     39     elems[i].deadline = random_deadline();
     40   }
     41   return elems;
     42 }
     43 
     44 static int contains(grpc_timer_heap* pq, grpc_timer* el) {
     45   size_t i;
     46   for (i = 0; i < pq->timer_count; i++) {
     47     if (pq->timers[i] == el) return 1;
     48   }
     49   return 0;
     50 }
     51 
     52 static void check_valid(grpc_timer_heap* pq) {
     53   size_t i;
     54   for (i = 0; i < pq->timer_count; ++i) {
     55     size_t left_child = 1u + 2u * i;
     56     size_t right_child = left_child + 1u;
     57     if (left_child < pq->timer_count) {
     58       GPR_ASSERT(pq->timers[i]->deadline <= pq->timers[left_child]->deadline);
     59     }
     60     if (right_child < pq->timer_count) {
     61       GPR_ASSERT(pq->timers[i]->deadline <= pq->timers[right_child]->deadline);
     62     }
     63   }
     64 }
     65 
     66 /*******************************************************************************
     67  * test1
     68  */
     69 
     70 static void test1(void) {
     71   grpc_timer_heap pq;
     72   const size_t num_test_elements = 200;
     73   const size_t num_test_operations = 10000;
     74   size_t i;
     75   grpc_timer* test_elements = create_test_elements(num_test_elements);
     76   uint8_t* inpq = static_cast<uint8_t*>(gpr_malloc(num_test_elements));
     77 
     78   gpr_log(GPR_INFO, "test1");
     79 
     80   grpc_timer_heap_init(&pq);
     81   memset(inpq, 0, num_test_elements);
     82   GPR_ASSERT(grpc_timer_heap_is_empty(&pq));
     83   check_valid(&pq);
     84   for (i = 0; i < num_test_elements; ++i) {
     85     GPR_ASSERT(!contains(&pq, &test_elements[i]));
     86     grpc_timer_heap_add(&pq, &test_elements[i]);
     87     check_valid(&pq);
     88     GPR_ASSERT(contains(&pq, &test_elements[i]));
     89     inpq[i] = 1;
     90   }
     91   for (i = 0; i < num_test_elements; ++i) {
     92     /* Test that check still succeeds even for element that wasn't just
     93        inserted. */
     94     GPR_ASSERT(contains(&pq, &test_elements[i]));
     95   }
     96 
     97   GPR_ASSERT(pq.timer_count == num_test_elements);
     98 
     99   check_valid(&pq);
    100 
    101   for (i = 0; i < num_test_operations; ++i) {
    102     size_t elem_num = static_cast<size_t>(rand()) % num_test_elements;
    103     grpc_timer* el = &test_elements[elem_num];
    104     if (!inpq[elem_num]) { /* not in pq */
    105       GPR_ASSERT(!contains(&pq, el));
    106       el->deadline = random_deadline();
    107       grpc_timer_heap_add(&pq, el);
    108       GPR_ASSERT(contains(&pq, el));
    109       inpq[elem_num] = 1;
    110       check_valid(&pq);
    111     } else {
    112       GPR_ASSERT(contains(&pq, el));
    113       grpc_timer_heap_remove(&pq, el);
    114       GPR_ASSERT(!contains(&pq, el));
    115       inpq[elem_num] = 0;
    116       check_valid(&pq);
    117     }
    118   }
    119 
    120   grpc_timer_heap_destroy(&pq);
    121   gpr_free(test_elements);
    122   gpr_free(inpq);
    123 }
    124 
    125 /*******************************************************************************
    126  * test2
    127  */
    128 
    129 typedef struct {
    130   grpc_timer elem;
    131   bool inserted;
    132 } elem_struct;
    133 
    134 static elem_struct* search_elems(elem_struct* elems, size_t count,
    135                                  bool inserted) {
    136   size_t* search_order =
    137       static_cast<size_t*>(gpr_malloc(count * sizeof(*search_order)));
    138   for (size_t i = 0; i < count; i++) {
    139     search_order[i] = i;
    140   }
    141   for (size_t i = 0; i < count * 2; i++) {
    142     size_t a = static_cast<size_t>(rand()) % count;
    143     size_t b = static_cast<size_t>(rand()) % count;
    144     GPR_SWAP(size_t, search_order[a], search_order[b]);
    145   }
    146   elem_struct* out = nullptr;
    147   for (size_t i = 0; out == nullptr && i < count; i++) {
    148     if (elems[search_order[i]].inserted == inserted) {
    149       out = &elems[search_order[i]];
    150     }
    151   }
    152   gpr_free(search_order);
    153   return out;
    154 }
    155 
    156 static void test2(void) {
    157   gpr_log(GPR_INFO, "test2");
    158 
    159   grpc_timer_heap pq;
    160 
    161   static const size_t elems_size = 1000;
    162   elem_struct* elems =
    163       static_cast<elem_struct*>(gpr_malloc(elems_size * sizeof(elem_struct)));
    164   size_t num_inserted = 0;
    165 
    166   grpc_timer_heap_init(&pq);
    167   memset(elems, 0, elems_size);
    168 
    169   for (size_t round = 0; round < 10000; round++) {
    170     int r = rand() % 1000;
    171     if (r <= 550) {
    172       /* 55% of the time we try to add something */
    173       elem_struct* el = search_elems(elems, GPR_ARRAY_SIZE(elems), false);
    174       if (el != nullptr) {
    175         el->elem.deadline = random_deadline();
    176         grpc_timer_heap_add(&pq, &el->elem);
    177         el->inserted = true;
    178         num_inserted++;
    179         check_valid(&pq);
    180       }
    181     } else if (r <= 650) {
    182       /* 10% of the time we try to remove something */
    183       elem_struct* el = search_elems(elems, GPR_ARRAY_SIZE(elems), true);
    184       if (el != nullptr) {
    185         grpc_timer_heap_remove(&pq, &el->elem);
    186         el->inserted = false;
    187         num_inserted--;
    188         check_valid(&pq);
    189       }
    190     } else {
    191       /* the remaining times we pop */
    192       if (num_inserted > 0) {
    193         grpc_timer* top = grpc_timer_heap_top(&pq);
    194         grpc_timer_heap_pop(&pq);
    195         for (size_t i = 0; i < elems_size; i++) {
    196           if (top == &elems[i].elem) {
    197             GPR_ASSERT(elems[i].inserted);
    198             elems[i].inserted = false;
    199           }
    200         }
    201         num_inserted--;
    202         check_valid(&pq);
    203       }
    204     }
    205 
    206     if (num_inserted) {
    207       grpc_millis* min_deadline = nullptr;
    208       for (size_t i = 0; i < elems_size; i++) {
    209         if (elems[i].inserted) {
    210           if (min_deadline == nullptr) {
    211             min_deadline = &elems[i].elem.deadline;
    212           } else {
    213             if (elems[i].elem.deadline < *min_deadline) {
    214               min_deadline = &elems[i].elem.deadline;
    215             }
    216           }
    217         }
    218       }
    219       GPR_ASSERT(grpc_timer_heap_top(&pq)->deadline == *min_deadline);
    220     }
    221   }
    222 
    223   grpc_timer_heap_destroy(&pq);
    224   gpr_free(elems);
    225 }
    226 
    227 static void shrink_test(void) {
    228   gpr_log(GPR_INFO, "shrink_test");
    229 
    230   grpc_timer_heap pq;
    231   size_t i;
    232   size_t expected_size;
    233 
    234   /* A large random number to allow for multiple shrinkages, at least 512. */
    235   const size_t num_elements = static_cast<size_t>(rand()) % 2000 + 512;
    236 
    237   grpc_timer_heap_init(&pq);
    238 
    239   /* Create a priority queue with many elements.  Make sure the Size() is
    240      correct. */
    241   for (i = 0; i < num_elements; ++i) {
    242     GPR_ASSERT(i == pq.timer_count);
    243     grpc_timer_heap_add(&pq, create_test_elements(1));
    244   }
    245   GPR_ASSERT(num_elements == pq.timer_count);
    246 
    247   /* Remove elements until the Size is 1/4 the original size. */
    248   while (pq.timer_count > num_elements / 4) {
    249     grpc_timer* const te = pq.timers[pq.timer_count - 1];
    250     grpc_timer_heap_remove(&pq, te);
    251     gpr_free(te);
    252   }
    253   GPR_ASSERT(num_elements / 4 == pq.timer_count);
    254 
    255   /* Expect that Capacity is in the right range:
    256      Size * 2 <= Capacity <= Size * 4 */
    257   GPR_ASSERT(pq.timer_count * 2 <= pq.timer_capacity);
    258   GPR_ASSERT(pq.timer_capacity <= pq.timer_count * 4);
    259   check_valid(&pq);
    260 
    261   /* Remove the rest of the elements.  Check that the Capacity is not more than
    262      4 times the Size and not less than 2 times, but never goes below 16. */
    263   expected_size = pq.timer_count;
    264   while (pq.timer_count > 0) {
    265     const size_t which = static_cast<size_t>(rand()) % pq.timer_count;
    266     grpc_timer* te = pq.timers[which];
    267     grpc_timer_heap_remove(&pq, te);
    268     gpr_free(te);
    269     expected_size--;
    270     GPR_ASSERT(expected_size == pq.timer_count);
    271     GPR_ASSERT(pq.timer_count * 2 <= pq.timer_capacity);
    272     if (pq.timer_count >= 8) {
    273       GPR_ASSERT(pq.timer_capacity <= pq.timer_count * 4);
    274     } else {
    275       GPR_ASSERT(16 <= pq.timer_capacity);
    276     }
    277     check_valid(&pq);
    278   }
    279 
    280   GPR_ASSERT(0 == pq.timer_count);
    281   GPR_ASSERT(pq.timer_capacity >= 16 && pq.timer_capacity < 32);
    282 
    283   grpc_timer_heap_destroy(&pq);
    284 }
    285 
    286 int main(int argc, char** argv) {
    287   int i;
    288 
    289   grpc_test_init(argc, argv);
    290 
    291   for (i = 0; i < 5; i++) {
    292     test1();
    293     test2();
    294     shrink_test();
    295   }
    296 
    297   return 0;
    298 }
    299