// // // Copyright 2015 gRPC authors. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // // #include <grpc/support/port_platform.h> #include <inttypes.h> #include <string> #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" #include <grpc/support/alloc.h> #include <grpc/support/cpu.h> #include <grpc/support/log.h> #include <grpc/support/sync.h> #include "src/core/lib/debug/trace.h" #include "src/core/lib/gpr/spinlock.h" #include "src/core/lib/gpr/useful.h" #include "src/core/lib/gprpp/crash.h" #include "src/core/lib/gprpp/manual_constructor.h" #include "src/core/lib/gprpp/time.h" #include "src/core/lib/gprpp/time_averaged_stats.h" #include "src/core/lib/iomgr/exec_ctx.h" #include "src/core/lib/iomgr/port.h" #include "src/core/lib/iomgr/timer.h" #include "src/core/lib/iomgr/timer_heap.h" #define INVALID_HEAP_INDEX … #define ADD_DEADLINE_SCALE … #define MIN_QUEUE_WINDOW_DURATION … #define MAX_QUEUE_WINDOW_DURATION … grpc_core::TraceFlag grpc_timer_trace(false, "timer"); grpc_core::TraceFlag grpc_timer_check_trace(false, "timer_check"); // A "timer shard". Contains a 'heap' and a 'list' of timers. All timers with // deadlines earlier than 'queue_deadline_cap' are maintained in the heap and // others are maintained in the list (unordered). This helps to keep the number // of elements in the heap low. // // The 'queue_deadline_cap' gets recomputed periodically based on the timer // stats maintained in 'stats' and the relevant timers are then moved from the // 'list' to 'heap'. // struct timer_shard { … }; static size_t g_num_shards; // Array of timer shards. Whenever a timer (grpc_timer *) is added, its address // is hashed to select the timer shard to add the timer to static timer_shard* g_shards; // Maintains a sorted list of timer shards (sorted by their min_deadline, i.e // the deadline of the next timer in each shard). // Access to this is protected by g_shared_mutables.mu static timer_shard** g_shard_queue; #ifndef NDEBUG // == DEBUG ONLY: hash table for duplicate timer detection == #define NUM_HASH_BUCKETS … static gpr_mu g_hash_mu[NUM_HASH_BUCKETS]; // One mutex per bucket static grpc_timer* g_timer_ht[NUM_HASH_BUCKETS] = …; static void init_timer_ht() { … } static void destroy_timer_ht() { … } static bool is_in_ht(grpc_timer* t) { … } static void add_to_ht(grpc_timer* t) { … } static void remove_from_ht(grpc_timer* t) { … } // If a timer is added to a timer shard (either heap or a list), it must // be pending. A timer is added to hash table only-if it is added to the // timer shard. // Therefore, if timer->pending is false, it cannot be in hash table static void validate_non_pending_timer(grpc_timer* t) { … } #define INIT_TIMER_HASH_TABLE() … #define DESTROY_TIMER_HASH_TABLE() … #define ADD_TO_HASH_TABLE(t) … #define REMOVE_FROM_HASH_TABLE(t) … #define VALIDATE_NON_PENDING_TIMER(t) … #else #define INIT_TIMER_HASH_TABLE … #define DESTROY_TIMER_HASH_TABLE … #define ADD_TO_HASH_TABLE … #define REMOVE_FROM_HASH_TABLE … #define VALIDATE_NON_PENDING_TIMER … #endif // Thread local variable that stores the deadline of the next timer the thread // has last-seen. This is an optimization to prevent the thread from checking // shared_mutables.min_timer (which requires acquiring shared_mutables.mu lock, // an expensive operation) static thread_local int64_t g_last_seen_min_timer; struct shared_mutables { … } GPR_ALIGN_STRUCT(…); static struct shared_mutables g_shared_mutables; static grpc_timer_check_result run_some_expired_timers( grpc_core::Timestamp now, grpc_core::Timestamp* next, grpc_error_handle error); static grpc_core::Timestamp compute_min_deadline(timer_shard* shard) { … } static void timer_list_init() { … } static void timer_list_shutdown() { … } // returns true if the first element in the list static void list_join(grpc_timer* head, grpc_timer* timer) { … } static void list_remove(grpc_timer* timer) { … } static void swap_adjacent_shards_in_queue(uint32_t first_shard_queue_index) { … } static void note_deadline_change(timer_shard* shard) { … } void grpc_timer_init_unset(grpc_timer* timer) { … } static void timer_init(grpc_timer* timer, grpc_core::Timestamp deadline, grpc_closure* closure) { … } static void timer_consume_kick(void) { … } static void timer_cancel(grpc_timer* timer) { … } // Rebalances the timer shard by computing a new 'queue_deadline_cap' and moving // all relevant timers in shard->list (i.e timers with deadlines earlier than // 'queue_deadline_cap') into into shard->heap. // Returns 'true' if shard->heap has at least ONE element // REQUIRES: shard->mu locked static bool refill_heap(timer_shard* shard, grpc_core::Timestamp now) { … } // This pops the next non-cancelled timer with deadline <= now from the // queue, or returns NULL if there isn't one. // REQUIRES: shard->mu locked static grpc_timer* pop_one(timer_shard* shard, grpc_core::Timestamp now) { … } // REQUIRES: shard->mu unlocked static size_t pop_timers(timer_shard* shard, grpc_core::Timestamp now, grpc_core::Timestamp* new_min_deadline, grpc_error_handle error) { … } static grpc_timer_check_result run_some_expired_timers( grpc_core::Timestamp now, grpc_core::Timestamp* next, grpc_error_handle error) { … } static grpc_timer_check_result timer_check(grpc_core::Timestamp* next) { … } grpc_timer_vtable grpc_generic_timer_vtable = …;
Codebase Browser
chromium