From d6d5d21c0af5b4e739cf3cfa35f64ceaa92424be Mon Sep 17 00:00:00 2001 From: ncteisen Date: Fri, 19 Oct 2018 12:25:19 -0700 Subject: Add bin search to gettopchannels and getservers --- src/core/lib/channel/channelz_registry.cc | 23 +++++++++++++---------- src/core/lib/channel/channelz_registry.h | 4 +++- test/core/channel/channelz_test.cc | 21 +++++++++++++++++++++ 3 files changed, 37 insertions(+), 11 deletions(-) diff --git a/src/core/lib/channel/channelz_registry.cc b/src/core/lib/channel/channelz_registry.cc index 218e3e2094..89d0573280 100644 --- a/src/core/lib/channel/channelz_registry.cc +++ b/src/core/lib/channel/channelz_registry.cc @@ -79,12 +79,13 @@ void ChannelzRegistry::MaybePerformCompactionLocked() { } } -int ChannelzRegistry::FindByUuidLocked(intptr_t target_uuid) { - size_t left = 0; - size_t right = entities_.size() - 1; +int ChannelzRegistry::FindByUuidLocked(intptr_t target_uuid, + bool direct_hit_needed) { + int left = 0; + int right = int(entities_.size() - 1); while (left <= right) { - size_t true_middle = left + (right - left) / 2; - size_t first_non_null = true_middle; + int true_middle = left + (right - left) / 2; + int first_non_null = true_middle; while (first_non_null < right && entities_[first_non_null] == nullptr) { first_non_null++; } @@ -102,14 +103,14 @@ int ChannelzRegistry::FindByUuidLocked(intptr_t target_uuid) { right = true_middle - 1; } } - return -1; + return direct_hit_needed ? -1 : right; } void ChannelzRegistry::InternalUnregister(intptr_t uuid) { GPR_ASSERT(uuid >= 1); MutexLock lock(&mu_); GPR_ASSERT(uuid <= uuid_generator_); - int idx = FindByUuidLocked(uuid); + int idx = FindByUuidLocked(uuid, true); GPR_ASSERT(idx >= 0); entities_[idx] = nullptr; num_empty_slots_++; @@ -121,7 +122,7 @@ BaseNode* ChannelzRegistry::InternalGet(intptr_t uuid) { if (uuid < 1 || uuid > uuid_generator_) { return nullptr; } - int idx = FindByUuidLocked(uuid); + int idx = FindByUuidLocked(uuid, true); return idx < 0 ? nullptr : entities_[idx]; } @@ -132,7 +133,8 @@ char* ChannelzRegistry::InternalGetTopChannels(intptr_t start_channel_id) { grpc_json* json_iterator = nullptr; InlinedVector top_level_channels; bool reached_pagination_limit = false; - for (size_t i = 0; i < entities_.size(); ++i) { + int start_idx = GPR_MAX(FindByUuidLocked(start_channel_id, false), 0); + for (size_t i = start_idx; i < entities_.size(); ++i) { if (entities_[i] != nullptr && entities_[i]->type() == grpc_core::channelz::BaseNode::EntityType::kTopLevelChannel && @@ -173,7 +175,8 @@ char* ChannelzRegistry::InternalGetServers(intptr_t start_server_id) { grpc_json* json_iterator = nullptr; InlinedVector servers; bool reached_pagination_limit = false; - for (size_t i = 0; i < entities_.size(); ++i) { + int start_idx = GPR_MAX(FindByUuidLocked(start_server_id, false), 0); + for (size_t i = start_idx; i < entities_.size(); ++i) { if (entities_[i] != nullptr && entities_[i]->type() == grpc_core::channelz::BaseNode::EntityType::kServer && diff --git a/src/core/lib/channel/channelz_registry.h b/src/core/lib/channel/channelz_registry.h index ea6ab6c8e5..326f0201c7 100644 --- a/src/core/lib/channel/channelz_registry.h +++ b/src/core/lib/channel/channelz_registry.h @@ -92,7 +92,9 @@ class ChannelzRegistry { void MaybePerformCompactionLocked(); // Performs binary search on entities_ to find the index with that uuid. - int FindByUuidLocked(intptr_t uuid); + // If direct_hit_needed, then will return -1 in case of absence. + // Else, will return idx of the first uuid higher than the target. + int FindByUuidLocked(intptr_t uuid, bool direct_hit_needed); // protects members gpr_mu mu_; diff --git a/test/core/channel/channelz_test.cc b/test/core/channel/channelz_test.cc index 48e558dfc0..4a1f53b924 100644 --- a/test/core/channel/channelz_test.cc +++ b/test/core/channel/channelz_test.cc @@ -402,6 +402,27 @@ TEST_F(ChannelzRegistryBasedTest, GetTopChannelsMiddleUuidCheck) { gpr_free(json_str); } +TEST_F(ChannelzRegistryBasedTest, GetTopChannelsNoHitUuid) { + grpc_core::ExecCtx exec_ctx; + ChannelFixture pre_channels[40]; // will take uuid[1, 40] + (void)pre_channels; // suppress unused variable error + ServerFixture servers[10]; // will take uuid[41, 50] + (void)servers; // suppress unused variable error + ChannelFixture channels[10]; // will take uuid[51, 60] + (void)channels; // suppress unused variable error + // query in the middle of the server channels + char* json_str = ChannelzRegistry::GetTopChannels(45); + grpc_json* parsed_json = grpc_json_parse_string(json_str); + ValidateJsonArraySize(parsed_json, "channel", 10); + grpc_json* json_channels = GetJsonChild(parsed_json, "channel"); + std::vector uuids = GetUuidListFromArray(json_channels); + for (size_t i = 0; i < uuids.size(); ++i) { + EXPECT_EQ(static_cast(51 + i), uuids[i]); + } + grpc_json_destroy(parsed_json); + gpr_free(json_str); +} + TEST_F(ChannelzRegistryBasedTest, GetTopChannelsUuidAfterCompaction) { const intptr_t kLoopIterations = 50; grpc_core::ExecCtx exec_ctx; -- cgit v1.2.3