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]; |
Craig Tiller | 317f68e | 2016-04-13 20:27:24 -0700 | [diff] [blame] | 73 | static bool g_initialized = false; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 74 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 75 | 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] | 76 | gpr_timespec *next, int success); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 77 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 78 | static gpr_timespec compute_min_deadline(shard_type *shard) { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 79 | return grpc_timer_heap_is_empty(&shard->heap) |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 80 | ? shard->queue_deadline_cap |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 81 | : grpc_timer_heap_top(&shard->heap)->deadline; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 82 | } |
| 83 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 84 | void grpc_timer_list_init(gpr_timespec now) { |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 85 | uint32_t i; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 86 | |
Craig Tiller | 3f72df9 | 2016-04-13 20:26:07 -0700 | [diff] [blame] | 87 | g_initialized = true; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 88 | gpr_mu_init(&g_mu); |
| 89 | gpr_mu_init(&g_checker_mu); |
Craig Tiller | 6a7626c | 2015-07-19 22:21:41 -0700 | [diff] [blame] | 90 | g_clock_type = now.clock_type; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 91 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 92 | for (i = 0; i < NUM_SHARDS; i++) { |
| 93 | shard_type *shard = &g_shards[i]; |
| 94 | gpr_mu_init(&shard->mu); |
| 95 | grpc_time_averaged_stats_init(&shard->stats, 1.0 / ADD_DEADLINE_SCALE, 0.1, |
| 96 | 0.5); |
| 97 | shard->queue_deadline_cap = now; |
| 98 | shard->shard_queue_index = i; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 99 | grpc_timer_heap_init(&shard->heap); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 100 | shard->list.next = shard->list.prev = &shard->list; |
| 101 | shard->min_deadline = compute_min_deadline(shard); |
| 102 | g_shard_queue[i] = shard; |
| 103 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 104 | } |
| 105 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 106 | void grpc_timer_list_shutdown(grpc_exec_ctx *exec_ctx) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 107 | int i; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 108 | 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] | 109 | for (i = 0; i < NUM_SHARDS; i++) { |
| 110 | shard_type *shard = &g_shards[i]; |
| 111 | gpr_mu_destroy(&shard->mu); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 112 | grpc_timer_heap_destroy(&shard->heap); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 113 | } |
| 114 | gpr_mu_destroy(&g_mu); |
| 115 | gpr_mu_destroy(&g_checker_mu); |
Craig Tiller | 3f72df9 | 2016-04-13 20:26:07 -0700 | [diff] [blame] | 116 | g_initialized = false; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 117 | } |
| 118 | |
| 119 | /* 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] | 120 | static size_t shard_idx(const grpc_timer *info) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 121 | size_t x = (size_t)info; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 122 | return ((x >> 4) ^ (x >> 9) ^ (x >> 14)) & (NUM_SHARDS - 1); |
| 123 | } |
| 124 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 125 | static double ts_to_dbl(gpr_timespec ts) { |
| 126 | return (double)ts.tv_sec + 1e-9 * ts.tv_nsec; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 127 | } |
| 128 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 129 | static gpr_timespec dbl_to_ts(double d) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 130 | gpr_timespec ts; |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 131 | ts.tv_sec = (int64_t)d; |
| 132 | ts.tv_nsec = (int32_t)(1e9 * (d - (double)ts.tv_sec)); |
Craig Tiller | 143e7bf | 2015-07-13 08:41:49 -0700 | [diff] [blame] | 133 | ts.clock_type = GPR_TIMESPAN; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 134 | return ts; |
| 135 | } |
| 136 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 137 | static void list_join(grpc_timer *head, grpc_timer *timer) { |
| 138 | timer->next = head; |
| 139 | timer->prev = head->prev; |
| 140 | timer->next->prev = timer->prev->next = timer; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 141 | } |
| 142 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 143 | static void list_remove(grpc_timer *timer) { |
| 144 | timer->next->prev = timer->prev; |
| 145 | timer->prev->next = timer->next; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 146 | } |
| 147 | |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 148 | static void swap_adjacent_shards_in_queue(uint32_t first_shard_queue_index) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 149 | shard_type *temp; |
| 150 | temp = g_shard_queue[first_shard_queue_index]; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 151 | g_shard_queue[first_shard_queue_index] = |
| 152 | g_shard_queue[first_shard_queue_index + 1]; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 153 | g_shard_queue[first_shard_queue_index + 1] = temp; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 154 | g_shard_queue[first_shard_queue_index]->shard_queue_index = |
| 155 | first_shard_queue_index; |
| 156 | g_shard_queue[first_shard_queue_index + 1]->shard_queue_index = |
| 157 | first_shard_queue_index + 1; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 158 | } |
| 159 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 160 | static void note_deadline_change(shard_type *shard) { |
| 161 | while (shard->shard_queue_index > 0 && |
| 162 | gpr_time_cmp( |
| 163 | shard->min_deadline, |
| 164 | g_shard_queue[shard->shard_queue_index - 1]->min_deadline) < 0) { |
| 165 | swap_adjacent_shards_in_queue(shard->shard_queue_index - 1); |
| 166 | } |
| 167 | while (shard->shard_queue_index < NUM_SHARDS - 1 && |
| 168 | gpr_time_cmp( |
| 169 | shard->min_deadline, |
| 170 | g_shard_queue[shard->shard_queue_index + 1]->min_deadline) > 0) { |
| 171 | swap_adjacent_shards_in_queue(shard->shard_queue_index); |
| 172 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 173 | } |
| 174 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 175 | void grpc_timer_init(grpc_exec_ctx *exec_ctx, grpc_timer *timer, |
| 176 | gpr_timespec deadline, grpc_iomgr_cb_func timer_cb, |
| 177 | void *timer_cb_arg, gpr_timespec now) { |
| 178 | int is_first_timer = 0; |
| 179 | shard_type *shard = &g_shards[shard_idx(timer)]; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 180 | GPR_ASSERT(deadline.clock_type == g_clock_type); |
| 181 | GPR_ASSERT(now.clock_type == g_clock_type); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 182 | grpc_closure_init(&timer->closure, timer_cb, timer_cb_arg); |
| 183 | timer->deadline = deadline; |
| 184 | timer->triggered = 0; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 185 | |
Craig Tiller | 3f72df9 | 2016-04-13 20:26:07 -0700 | [diff] [blame] | 186 | if (!g_initialized) { |
Craig Tiller | f3596c5 | 2016-04-14 08:08:38 -0700 | [diff] [blame] | 187 | timer->triggered = 1; |
Craig Tiller | 317f68e | 2016-04-13 20:27:24 -0700 | [diff] [blame] | 188 | grpc_exec_ctx_enqueue(exec_ctx, &timer->closure, false, NULL); |
Craig Tiller | 3f72df9 | 2016-04-13 20:26:07 -0700 | [diff] [blame] | 189 | return; |
| 190 | } |
| 191 | |
| 192 | if (gpr_time_cmp(deadline, now) <= 0) { |
Craig Tiller | f3596c5 | 2016-04-14 08:08:38 -0700 | [diff] [blame] | 193 | timer->triggered = 1; |
Craig Tiller | 317f68e | 2016-04-13 20:27:24 -0700 | [diff] [blame] | 194 | grpc_exec_ctx_enqueue(exec_ctx, &timer->closure, true, NULL); |
Craig Tiller | 3f72df9 | 2016-04-13 20:26:07 -0700 | [diff] [blame] | 195 | return; |
| 196 | } |
| 197 | |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 198 | /* TODO(ctiller): check deadline expired */ |
| 199 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 200 | gpr_mu_lock(&shard->mu); |
| 201 | grpc_time_averaged_stats_add_sample(&shard->stats, |
| 202 | ts_to_dbl(gpr_time_sub(deadline, now))); |
| 203 | if (gpr_time_cmp(deadline, shard->queue_deadline_cap) < 0) { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 204 | is_first_timer = grpc_timer_heap_add(&shard->heap, timer); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 205 | } else { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 206 | timer->heap_index = INVALID_HEAP_INDEX; |
| 207 | list_join(&shard->list, timer); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 208 | } |
| 209 | gpr_mu_unlock(&shard->mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 210 | |
| 211 | /* Deadline may have decreased, we need to adjust the master queue. Note |
| 212 | 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] | 213 | reordering of multiple grpc_timer_init calls, at this point, but the < test |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 214 | 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] | 215 | also be a race with grpc_timer_check, which might beat us to the lock. In |
| 216 | 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] | 217 | 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] | 218 | Finally, it's possible that the grpc_timer_check that intervened failed to |
| 219 | trigger the new timer because the min_deadline hadn't yet been reduced. |
| 220 | In that case, the timer will simply have to wait for the next |
| 221 | grpc_timer_check. */ |
| 222 | if (is_first_timer) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 223 | gpr_mu_lock(&g_mu); |
| 224 | if (gpr_time_cmp(deadline, shard->min_deadline) < 0) { |
| 225 | gpr_timespec old_min_deadline = g_shard_queue[0]->min_deadline; |
| 226 | shard->min_deadline = deadline; |
| 227 | note_deadline_change(shard); |
| 228 | if (shard->shard_queue_index == 0 && |
| 229 | gpr_time_cmp(deadline, old_min_deadline) < 0) { |
| 230 | grpc_kick_poller(); |
| 231 | } |
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 | gpr_mu_unlock(&g_mu); |
| 234 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 235 | } |
| 236 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 237 | void grpc_timer_cancel(grpc_exec_ctx *exec_ctx, grpc_timer *timer) { |
| 238 | shard_type *shard = &g_shards[shard_idx(timer)]; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 239 | gpr_mu_lock(&shard->mu); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 240 | if (!timer->triggered) { |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 241 | grpc_exec_ctx_enqueue(exec_ctx, &timer->closure, false, NULL); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 242 | timer->triggered = 1; |
| 243 | if (timer->heap_index == INVALID_HEAP_INDEX) { |
| 244 | list_remove(timer); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 245 | } else { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 246 | grpc_timer_heap_remove(&shard->heap, timer); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 247 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 248 | } |
| 249 | gpr_mu_unlock(&shard->mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 250 | } |
| 251 | |
| 252 | /* This is called when the queue is empty and "now" has reached the |
| 253 | 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] | 254 | 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] | 255 | longer empty. |
| 256 | REQUIRES: shard->mu locked */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 257 | static int refill_queue(shard_type *shard, gpr_timespec now) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 258 | /* Compute the new queue window width and bound by the limits: */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 259 | double computed_deadline_delta = |
| 260 | grpc_time_averaged_stats_update_average(&shard->stats) * |
| 261 | ADD_DEADLINE_SCALE; |
| 262 | double deadline_delta = |
| 263 | GPR_CLAMP(computed_deadline_delta, MIN_QUEUE_WINDOW_DURATION, |
| 264 | MAX_QUEUE_WINDOW_DURATION); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 265 | grpc_timer *timer, *next; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 266 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 267 | /* 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] | 268 | shard->queue_deadline_cap = gpr_time_add( |
| 269 | 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] | 270 | for (timer = shard->list.next; timer != &shard->list; timer = next) { |
| 271 | next = timer->next; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 272 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 273 | if (gpr_time_cmp(timer->deadline, shard->queue_deadline_cap) < 0) { |
| 274 | list_remove(timer); |
| 275 | grpc_timer_heap_add(&shard->heap, timer); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 276 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 277 | } |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 278 | return !grpc_timer_heap_is_empty(&shard->heap); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 279 | } |
| 280 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 281 | /* This pops the next non-cancelled timer with deadline <= now from the queue, |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 282 | or returns NULL if there isn't one. |
| 283 | REQUIRES: shard->mu locked */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 284 | static grpc_timer *pop_one(shard_type *shard, gpr_timespec now) { |
| 285 | grpc_timer *timer; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 286 | for (;;) { |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 287 | if (grpc_timer_heap_is_empty(&shard->heap)) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 288 | if (gpr_time_cmp(now, shard->queue_deadline_cap) < 0) return NULL; |
| 289 | if (!refill_queue(shard, now)) return NULL; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 290 | } |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 291 | timer = grpc_timer_heap_top(&shard->heap); |
| 292 | if (gpr_time_cmp(timer->deadline, now) > 0) return NULL; |
| 293 | timer->triggered = 1; |
| 294 | grpc_timer_heap_pop(&shard->heap); |
| 295 | return timer; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 296 | } |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 297 | } |
| 298 | |
| 299 | /* REQUIRES: shard->mu unlocked */ |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 300 | 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] | 301 | gpr_timespec now, gpr_timespec *new_min_deadline, |
| 302 | int success) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 303 | size_t n = 0; |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 304 | grpc_timer *timer; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 305 | gpr_mu_lock(&shard->mu); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 306 | while ((timer = pop_one(shard, now))) { |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 307 | grpc_exec_ctx_enqueue(exec_ctx, &timer->closure, success, NULL); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 308 | n++; |
| 309 | } |
| 310 | *new_min_deadline = compute_min_deadline(shard); |
| 311 | gpr_mu_unlock(&shard->mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 312 | return n; |
| 313 | } |
| 314 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 315 | 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] | 316 | gpr_timespec *next, int success) { |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 317 | size_t n = 0; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 318 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 319 | /* TODO(ctiller): verify that there are any timers (atomically) here */ |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 320 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 321 | if (gpr_mu_trylock(&g_checker_mu)) { |
| 322 | gpr_mu_lock(&g_mu); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 323 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 324 | while (gpr_time_cmp(g_shard_queue[0]->min_deadline, now) < 0) { |
| 325 | gpr_timespec new_min_deadline; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 326 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 327 | /* For efficiency, we pop as many available timers as we can from the |
| 328 | shard. This may violate perfect timer deadline ordering, but that |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 329 | 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] | 330 | 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] | 331 | success); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 332 | |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 333 | /* An grpc_timer_init() on the shard could intervene here, adding a new |
| 334 | timer that is earlier than new_min_deadline. However, |
| 335 | grpc_timer_init() will block on the master_lock before it can call |
| 336 | 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] | 337 | will reduce the min_deadline (perhaps unnecessarily). */ |
| 338 | g_shard_queue[0]->min_deadline = new_min_deadline; |
| 339 | note_deadline_change(g_shard_queue[0]); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 340 | } |
| 341 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 342 | if (next) { |
| 343 | *next = gpr_time_min(*next, g_shard_queue[0]->min_deadline); |
| 344 | } |
| 345 | |
| 346 | gpr_mu_unlock(&g_mu); |
| 347 | gpr_mu_unlock(&g_checker_mu); |
Craig Tiller | 9fb89ea | 2016-03-11 20:12:45 -0800 | [diff] [blame] | 348 | } else if (next != NULL) { |
Craig Tiller | 822f1d7 | 2016-03-12 06:54:47 -0800 | [diff] [blame] | 349 | /* TODO(ctiller): this forces calling code to do an short poll, and |
| 350 | then retry the timer check (because this time through the timer list was |
| 351 | contended). |
| 352 | |
| 353 | We could reduce the cost here dramatically by keeping a count of how many |
| 354 | currently active pollers got through the uncontended case above |
| 355 | successfully, and waking up other pollers IFF that count drops to zero. |
| 356 | |
| 357 | Once that count is in place, this entire else branch could disappear. */ |
Craig Tiller | 9fb89ea | 2016-03-11 20:12:45 -0800 | [diff] [blame] | 358 | *next = gpr_time_min( |
Craig Tiller | 822f1d7 | 2016-03-12 06:54:47 -0800 | [diff] [blame] | 359 | *next, gpr_time_add(now, gpr_time_from_millis(1, GPR_TIMESPAN))); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 360 | } |
| 361 | |
| 362 | return (int)n; |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 363 | } |
| 364 | |
Craig Tiller | 311445f | 2016-02-18 07:31:39 -0800 | [diff] [blame] | 365 | bool grpc_timer_check(grpc_exec_ctx *exec_ctx, gpr_timespec now, |
| 366 | gpr_timespec *next) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 367 | GPR_ASSERT(now.clock_type == g_clock_type); |
David Garcia Quintas | f747bbc | 2015-10-04 23:09:47 -0700 | [diff] [blame] | 368 | return run_some_expired_timers( |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 369 | exec_ctx, now, next, |
| 370 | gpr_time_cmp(now, gpr_inf_future(now.clock_type)) != 0); |
ctiller | 3bf466f | 2014-12-19 16:21:57 -0800 | [diff] [blame] | 371 | } |