(trafficserver) branch master updated: Fix an infinite loop in Histogram (#11752)

[mo...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

mochen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git


The following commit(s) were added to refs/heads/master by this push:
     new 36da45475d Fix an infinite loop in Histogram (#11752)
36da45475d is described below

commit 36da45475db02790b95d615a690b91170aa2f06c
Author: Mo Chen <mo...@apache.org>
AuthorDate: Fri Aug 30 14:12:00 2024 -0500

    Fix an infinite loop in Histogram (#11752)
    
    The loop in Histogram::operator() is infinite if R = 7, S = 2, and sample = 512.  When this happens, the histogram will not find a matching bit and will loop forever with mask at 0.  This change lowers OVERFLOW_BOUND so that every sample is guaranteed to have a 1-bit within the range of histogram buckets.
---
 include/tsutil/Histogram.h              | 2 +-
 src/tscore/unit_tests/test_Histogram.cc | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/tsutil/Histogram.h b/include/tsutil/Histogram.h
index 1bcdd38a21..f5c0c679e9 100644
--- a/include/tsutil/Histogram.h
+++ b/include/tsutil/Histogram.h
@@ -75,7 +75,7 @@ public:
   /// Samples less than this go in the underflow range.
   static constexpr raw_type UNDERFLOW_BOUND = static_cast<raw_type>(1) << N_SPAN_BITS;
   /// Sample equal or greater than this  go in the overflow bucket.
-  static constexpr raw_type OVERFLOW_BOUND = static_cast<raw_type>(1) << (N_RANGE_BITS + N_SPAN_BITS + 1);
+  static constexpr raw_type OVERFLOW_BOUND = static_cast<raw_type>(1) << (N_RANGE_BITS + N_SPAN_BITS);
 
   /** Add @sample to the histogram.
    *
diff --git a/src/tscore/unit_tests/test_Histogram.cc b/src/tscore/unit_tests/test_Histogram.cc
index 54941540d2..9d9382f35e 100644
--- a/src/tscore/unit_tests/test_Histogram.cc
+++ b/src/tscore/unit_tests/test_Histogram.cc
@@ -45,7 +45,7 @@ TEST_CASE("Histogram Basic", "[libts][histogram]")
   REQUIRE(h.min_for_bucket(16) == 32);
   REQUIRE(h.min_for_bucket(17) == 40);
 
-  for (auto x : {0, 1, 4, 6, 19, 27, 36, 409, 16000, 1097}) {
+  for (auto x : {0, 1, 4, 6, 19, 27, 36, 409, 16000, 1097, 512}) {
     h(x);
   }
   REQUIRE(h[0] == 1);