ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 1 | /* |
| 2 | * |
Craig Tiller | 6169d5f | 2016-03-31 07:46:18 -0700 | [diff] [blame] | 3 | * Copyright 2015, Google Inc. |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 4 | * All rights reserved. |
| 5 | * |
| 6 | * Redistribution and use in source and binary forms, with or without |
| 7 | * modification, are permitted provided that the following conditions are |
| 8 | * met: |
| 9 | * |
| 10 | * * Redistributions of source code must retain the above copyright |
| 11 | * notice, this list of conditions and the following disclaimer. |
| 12 | * * Redistributions in binary form must reproduce the above |
| 13 | * copyright notice, this list of conditions and the following disclaimer |
| 14 | * in the documentation and/or other materials provided with the |
| 15 | * distribution. |
| 16 | * * Neither the name of Google Inc. nor the names of its |
| 17 | * contributors may be used to endorse or promote products derived from |
| 18 | * this software without specific prior written permission. |
| 19 | * |
| 20 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 21 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 22 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 23 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 24 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 25 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 26 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 27 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 28 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 29 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 30 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 31 | * |
| 32 | */ |
| 33 | |
Craig Tiller | 9533d04 | 2016-03-25 17:11:06 -0700 | [diff] [blame] | 34 | #include "src/core/lib/iomgr/timer.h" |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 35 | |
Craig Tiller | 6a7626c | 2015-07-19 22:21:41 -0700 | [diff] [blame] | 36 | #include <grpc/support/log.h> |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 37 | #include <grpc/support/sync.h> |
| 38 | #include <grpc/support/useful.h> |
Craig Tiller | 9533d04 | 2016-03-25 17:11:06 -0700 | [diff] [blame] | 39 | #include "src/core/lib/iomgr/time_averaged_stats.h" |
| 40 | #include "src/core/lib/iomgr/timer_heap.h" |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 41 | |
| 42 | #define INVALID_HEAP_INDEX 0xffffffffu |
| 43 | |
| 44 | #define LOG2_NUM_SHARDS 5 |
| 45 | #define NUM_SHARDS (1 << LOG2_NUM_SHARDS) |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 46 | #define ADD_DEADLINE_SCALE 0.33 |
| 47 | #define MIN_QUEUE_WINDOW_DURATION 0.01 |
| 48 | #define MAX_QUEUE_WINDOW_DURATION 1 |
| 49 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 50 | typedef struct { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 51 | gpr_mu mu; |
| 52 | grpc_time_averaged_stats stats; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 53 | /* All and only timers with deadlines <= this will be in the heap. */ |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 54 | gpr_timespec queue_deadline_cap; |
| 55 | gpr_timespec min_deadline; |
| 56 | /* Index in the g_shard_queue */ |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 57 | uint32_t shard_queue_index; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 58 | /* This holds all timers with deadlines < queue_deadline_cap. Timers in this |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 59 | list have the top bit of their deadline set to 0. */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 60 | grpc_timer_heap heap; |
| 61 | /* This holds timers whose deadline is >= queue_deadline_cap. */ |
| 62 | grpc_timer list; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 63 | } shard_type; |
| 64 | |
| 65 | /* Protects g_shard_queue */ |
| 66 | static gpr_mu g_mu; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 67 | /* Allow only one run_some_expired_timers at once */ |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 68 | static gpr_mu g_checker_mu; |
Craig Tiller | 6a7626c | 2015-07-19 22:21:41 -0700 | [diff] [blame] | 69 | static gpr_clock_type g_clock_type; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 70 | static shard_type g_shards[NUM_SHARDS]; |
| 71 | /* Protected by g_mu */ |
| 72 | static shard_type *g_shard_queue[NUM_SHARDS]; |
| 73 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 74 | static int run_some_expired_timers(grpc_exec_ctx *exec_ctx, gpr_timespec now, |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 75 | gpr_timespec *next, int success); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 76 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 77 | static gpr_timespec compute_min_deadline(shard_type *shard) { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 78 | return grpc_timer_heap_is_empty(&shard->heap) |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 79 | ? shard->queue_deadline_cap |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 80 | : grpc_timer_heap_top(&shard->heap)->deadline; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 81 | } |
| 82 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 83 | void grpc_timer_list_init(gpr_timespec now) { |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 84 | uint32_t i; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 85 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 86 | gpr_mu_init(&g_mu); |
| 87 | gpr_mu_init(&g_checker_mu); |
Craig Tiller | 6a7626c | 2015-07-19 22:21:41 -0700 | [diff] [blame] | 88 | g_clock_type = now.clock_type; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 89 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 90 | for (i = 0; i < NUM_SHARDS; i++) { |
| 91 | shard_type *shard = &g_shards[i]; |
| 92 | gpr_mu_init(&shard->mu); |
| 93 | grpc_time_averaged_stats_init(&shard->stats, 1.0 / ADD_DEADLINE_SCALE, 0.1, |
| 94 | 0.5); |
| 95 | shard->queue_deadline_cap = now; |
| 96 | shard->shard_queue_index = i; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 97 | grpc_timer_heap_init(&shard->heap); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 98 | shard->list.next = shard->list.prev = &shard->list; |
| 99 | shard->min_deadline = compute_min_deadline(shard); |
| 100 | g_shard_queue[i] = shard; |
| 101 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 102 | } |
| 103 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 104 | void grpc_timer_list_shutdown(grpc_exec_ctx *exec_ctx) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 105 | int i; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 106 | run_some_expired_timers(exec_ctx, gpr_inf_future(g_clock_type), NULL, 0); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 107 | for (i = 0; i < NUM_SHARDS; i++) { |
| 108 | shard_type *shard = &g_shards[i]; |
| 109 | gpr_mu_destroy(&shard->mu); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 110 | grpc_timer_heap_destroy(&shard->heap); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 111 | } |
| 112 | gpr_mu_destroy(&g_mu); |
| 113 | gpr_mu_destroy(&g_checker_mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 114 | } |
| 115 | |
| 116 | /* This is a cheap, but good enough, pointer hash for sharding the tasks: */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 117 | static size_t shard_idx(const grpc_timer *info) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 118 | size_t x = (size_t)info; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 119 | return ((x >> 4) ^ (x >> 9) ^ (x >> 14)) & (NUM_SHARDS - 1); |
| 120 | } |
| 121 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 122 | static double ts_to_dbl(gpr_timespec ts) { |
| 123 | return (double)ts.tv_sec + 1e-9 * ts.tv_nsec; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 124 | } |
| 125 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 126 | static gpr_timespec dbl_to_ts(double d) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 127 | gpr_timespec ts; |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 128 | ts.tv_sec = (int64_t)d; |
| 129 | ts.tv_nsec = (int32_t)(1e9 * (d - (double)ts.tv_sec)); |
Craig Tiller | 143e7bf | 2015-07-13 08:41:49 -0700 | [diff] [blame] | 130 | ts.clock_type = GPR_TIMESPAN; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 131 | return ts; |
| 132 | } |
| 133 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 134 | static void list_join(grpc_timer *head, grpc_timer *timer) { |
| 135 | timer->next = head; |
| 136 | timer->prev = head->prev; |
| 137 | timer->next->prev = timer->prev->next = timer; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 138 | } |
| 139 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 140 | static void list_remove(grpc_timer *timer) { |
| 141 | timer->next->prev = timer->prev; |
| 142 | timer->prev->next = timer->next; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 143 | } |
| 144 | |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 145 | static void swap_adjacent_shards_in_queue(uint32_t first_shard_queue_index) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 146 | shard_type *temp; |
| 147 | temp = g_shard_queue[first_shard_queue_index]; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 148 | g_shard_queue[first_shard_queue_index] = |
| 149 | g_shard_queue[first_shard_queue_index + 1]; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 150 | g_shard_queue[first_shard_queue_index + 1] = temp; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 151 | g_shard_queue[first_shard_queue_index]->shard_queue_index = |
| 152 | first_shard_queue_index; |
| 153 | g_shard_queue[first_shard_queue_index + 1]->shard_queue_index = |
| 154 | first_shard_queue_index + 1; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 155 | } |
| 156 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 157 | static void note_deadline_change(shard_type *shard) { |
| 158 | while (shard->shard_queue_index > 0 && |
| 159 | gpr_time_cmp( |
| 160 | shard->min_deadline, |
| 161 | g_shard_queue[shard->shard_queue_index - 1]->min_deadline) < 0) { |
| 162 | swap_adjacent_shards_in_queue(shard->shard_queue_index - 1); |
| 163 | } |
| 164 | while (shard->shard_queue_index < NUM_SHARDS - 1 && |
| 165 | gpr_time_cmp( |
| 166 | shard->min_deadline, |
| 167 | g_shard_queue[shard->shard_queue_index + 1]->min_deadline) > 0) { |
| 168 | swap_adjacent_shards_in_queue(shard->shard_queue_index); |
| 169 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 170 | } |
| 171 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 172 | void grpc_timer_init(grpc_exec_ctx *exec_ctx, grpc_timer *timer, |
| 173 | gpr_timespec deadline, grpc_iomgr_cb_func timer_cb, |
| 174 | void *timer_cb_arg, gpr_timespec now) { |
| 175 | int is_first_timer = 0; |
| 176 | shard_type *shard = &g_shards[shard_idx(timer)]; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 177 | GPR_ASSERT(deadline.clock_type == g_clock_type); |
| 178 | GPR_ASSERT(now.clock_type == g_clock_type); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 179 | grpc_closure_init(&timer->closure, timer_cb, timer_cb_arg); |
| 180 | timer->deadline = deadline; |
| 181 | timer->triggered = 0; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 182 | |
| 183 | /* TODO(ctiller): check deadline expired */ |
| 184 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 185 | gpr_mu_lock(&shard->mu); |
| 186 | grpc_time_averaged_stats_add_sample(&shard->stats, |
| 187 | ts_to_dbl(gpr_time_sub(deadline, now))); |
| 188 | if (gpr_time_cmp(deadline, shard->queue_deadline_cap) < 0) { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 189 | is_first_timer = grpc_timer_heap_add(&shard->heap, timer); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 190 | } else { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 191 | timer->heap_index = INVALID_HEAP_INDEX; |
| 192 | list_join(&shard->list, timer); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 193 | } |
| 194 | gpr_mu_unlock(&shard->mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 195 | |
| 196 | /* Deadline may have decreased, we need to adjust the master queue. Note |
| 197 | that there is a potential racy unlocked region here. There could be a |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 198 | reordering of multiple grpc_timer_init calls, at this point, but the < test |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 199 | below should ensure that we err on the side of caution. There could |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 200 | also be a race with grpc_timer_check, which might beat us to the lock. In |
| 201 | that case, it is possible that the timer that we added will have already |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 202 | run by the time we hold the lock, but that too is a safe error. |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 203 | Finally, it's possible that the grpc_timer_check that intervened failed to |
| 204 | trigger the new timer because the min_deadline hadn't yet been reduced. |
| 205 | In that case, the timer will simply have to wait for the next |
| 206 | grpc_timer_check. */ |
| 207 | if (is_first_timer) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 208 | gpr_mu_lock(&g_mu); |
| 209 | if (gpr_time_cmp(deadline, shard->min_deadline) < 0) { |
| 210 | gpr_timespec old_min_deadline = g_shard_queue[0]->min_deadline; |
| 211 | shard->min_deadline = deadline; |
| 212 | note_deadline_change(shard); |
| 213 | if (shard->shard_queue_index == 0 && |
| 214 | gpr_time_cmp(deadline, old_min_deadline) < 0) { |
| 215 | grpc_kick_poller(); |
| 216 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 217 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 218 | gpr_mu_unlock(&g_mu); |
| 219 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 220 | } |
| 221 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 222 | void grpc_timer_cancel(grpc_exec_ctx *exec_ctx, grpc_timer *timer) { |
| 223 | shard_type *shard = &g_shards[shard_idx(timer)]; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 224 | gpr_mu_lock(&shard->mu); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 225 | if (!timer->triggered) { |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 226 | grpc_exec_ctx_enqueue(exec_ctx, &timer->closure, false, NULL); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 227 | timer->triggered = 1; |
| 228 | if (timer->heap_index == INVALID_HEAP_INDEX) { |
| 229 | list_remove(timer); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 230 | } else { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 231 | grpc_timer_heap_remove(&shard->heap, timer); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 232 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 233 | } |
| 234 | gpr_mu_unlock(&shard->mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 235 | } |
| 236 | |
| 237 | /* This is called when the queue is empty and "now" has reached the |
| 238 | queue_deadline_cap. We compute a new queue deadline and then scan the map |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 239 | for timers that fall at or under it. Returns true if the queue is no |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 240 | longer empty. |
| 241 | REQUIRES: shard->mu locked */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 242 | static int refill_queue(shard_type *shard, gpr_timespec now) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 243 | /* Compute the new queue window width and bound by the limits: */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 244 | double computed_deadline_delta = |
| 245 | grpc_time_averaged_stats_update_average(&shard->stats) * |
| 246 | ADD_DEADLINE_SCALE; |
| 247 | double deadline_delta = |
| 248 | GPR_CLAMP(computed_deadline_delta, MIN_QUEUE_WINDOW_DURATION, |
| 249 | MAX_QUEUE_WINDOW_DURATION); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 250 | grpc_timer *timer, *next; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 251 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 252 | /* Compute the new cap and put all timers under it into the queue: */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 253 | shard->queue_deadline_cap = gpr_time_add( |
| 254 | gpr_time_max(now, shard->queue_deadline_cap), dbl_to_ts(deadline_delta)); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 255 | for (timer = shard->list.next; timer != &shard->list; timer = next) { |
| 256 | next = timer->next; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 257 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 258 | if (gpr_time_cmp(timer->deadline, shard->queue_deadline_cap) < 0) { |
| 259 | list_remove(timer); |
| 260 | grpc_timer_heap_add(&shard->heap, timer); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 261 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 262 | } |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 263 | return !grpc_timer_heap_is_empty(&shard->heap); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 264 | } |
| 265 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 266 | /* This pops the next non-cancelled timer with deadline <= now from the queue, |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 267 | or returns NULL if there isn't one. |
| 268 | REQUIRES: shard->mu locked */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 269 | static grpc_timer *pop_one(shard_type *shard, gpr_timespec now) { |
| 270 | grpc_timer *timer; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 271 | for (;;) { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 272 | if (grpc_timer_heap_is_empty(&shard->heap)) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 273 | if (gpr_time_cmp(now, shard->queue_deadline_cap) < 0) return NULL; |
| 274 | if (!refill_queue(shard, now)) return NULL; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 275 | } |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 276 | timer = grpc_timer_heap_top(&shard->heap); |
| 277 | if (gpr_time_cmp(timer->deadline, now) > 0) return NULL; |
| 278 | timer->triggered = 1; |
| 279 | grpc_timer_heap_pop(&shard->heap); |
| 280 | return timer; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 281 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 282 | } |
| 283 | |
| 284 | /* REQUIRES: shard->mu unlocked */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 285 | static size_t pop_timers(grpc_exec_ctx *exec_ctx, shard_type *shard, |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 286 | gpr_timespec now, gpr_timespec *new_min_deadline, |
| 287 | int success) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 288 | size_t n = 0; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 289 | grpc_timer *timer; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 290 | gpr_mu_lock(&shard->mu); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 291 | while ((timer = pop_one(shard, now))) { |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 292 | grpc_exec_ctx_enqueue(exec_ctx, &timer->closure, success, NULL); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 293 | n++; |
| 294 | } |
| 295 | *new_min_deadline = compute_min_deadline(shard); |
| 296 | gpr_mu_unlock(&shard->mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 297 | return n; |
| 298 | } |
| 299 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 300 | static int run_some_expired_timers(grpc_exec_ctx *exec_ctx, gpr_timespec now, |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 301 | gpr_timespec *next, int success) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 302 | size_t n = 0; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 303 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 304 | /* TODO(ctiller): verify that there are any timers (atomically) here */ |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 305 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 306 | if (gpr_mu_trylock(&g_checker_mu)) { |
| 307 | gpr_mu_lock(&g_mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 308 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 309 | while (gpr_time_cmp(g_shard_queue[0]->min_deadline, now) < 0) { |
| 310 | gpr_timespec new_min_deadline; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 311 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 312 | /* For efficiency, we pop as many available timers as we can from the |
| 313 | shard. This may violate perfect timer deadline ordering, but that |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 314 | shouldn't be a big deal because we don't make ordering guarantees. */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 315 | n += pop_timers(exec_ctx, g_shard_queue[0], now, &new_min_deadline, |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 316 | success); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 317 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 318 | /* An grpc_timer_init() on the shard could intervene here, adding a new |
| 319 | timer that is earlier than new_min_deadline. However, |
| 320 | grpc_timer_init() will block on the master_lock before it can call |
| 321 | set_min_deadline, so this one will complete first and then the Addtimer |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 322 | will reduce the min_deadline (perhaps unnecessarily). */ |
| 323 | g_shard_queue[0]->min_deadline = new_min_deadline; |
| 324 | note_deadline_change(g_shard_queue[0]); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 325 | } |
| 326 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 327 | if (next) { |
| 328 | *next = gpr_time_min(*next, g_shard_queue[0]->min_deadline); |
| 329 | } |
| 330 | |
| 331 | gpr_mu_unlock(&g_mu); |
| 332 | gpr_mu_unlock(&g_checker_mu); |
Craig Tiller | 9fb89ea | 2016-03-11 20:12:45 -0800 | [diff] [blame] | 333 | } else if (next != NULL) { |
Craig Tiller | 822f1d7 | 2016-03-12 06:54:47 -0800 | [diff] [blame] | 334 | /* TODO(ctiller): this forces calling code to do an short poll, and |
| 335 | then retry the timer check (because this time through the timer list was |
| 336 | contended). |
| 337 | |
| 338 | We could reduce the cost here dramatically by keeping a count of how many |
| 339 | currently active pollers got through the uncontended case above |
| 340 | successfully, and waking up other pollers IFF that count drops to zero. |
| 341 | |
| 342 | Once that count is in place, this entire else branch could disappear. */ |
Craig Tiller | 9fb89ea | 2016-03-11 20:12:45 -0800 | [diff] [blame] | 343 | *next = gpr_time_min( |
Craig Tiller | 822f1d7 | 2016-03-12 06:54:47 -0800 | [diff] [blame] | 344 | *next, gpr_time_add(now, gpr_time_from_millis(1, GPR_TIMESPAN))); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 345 | } |
| 346 | |
| 347 | return (int)n; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 348 | } |
| 349 | |
Craig Tiller | 311445f | 2016-02-18 07:31:39 -0800 | [diff] [blame] | 350 | bool grpc_timer_check(grpc_exec_ctx *exec_ctx, gpr_timespec now, |
| 351 | gpr_timespec *next) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 352 | GPR_ASSERT(now.clock_type == g_clock_type); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 353 | return run_some_expired_timers( |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 354 | exec_ctx, now, next, |
| 355 | gpr_time_cmp(now, gpr_inf_future(now.clock_type)) != 0); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 356 | } |