You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by zw...@apache.org on 2022/05/16 15:22:05 UTC
[trafficserver] branch 9.2.x updated: Fix overflow conditions in prefetch plugin (#8660)
This is an automated email from the ASF dual-hosted git repository.
zwoop pushed a commit to branch 9.2.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/9.2.x by this push:
new 041e55fcc Fix overflow conditions in prefetch plugin (#8660)
041e55fcc is described below
commit 041e55fcc8a1ec617a14d53c6b601227acda15fa
Author: Mo Chen <un...@gmail.com>
AuthorDate: Mon May 9 18:48:22 2022 -0500
Fix overflow conditions in prefetch plugin (#8660)
* Prefetch plugin: improve over/underflow handling
1. Specify integer size limitations.
2. Specify underflow/overflow behavior.
3. Refactor and add unit tests for evaluate().
* Use superscript for exponent
* Add end-of-line to evaluate.h
(cherry picked from commit bd155584f45f8676239baeea3046b19b6eb37236)
---
doc/admin-guide/plugins/prefetch.en.rst | 8 ++-
plugins/prefetch/Makefile.inc | 8 ++-
plugins/prefetch/evaluate.cc | 94 +++++++++++++++++++++++++++++++++
plugins/prefetch/evaluate.h | 27 ++++++++++
plugins/prefetch/plugin.cc | 48 +----------------
plugins/prefetch/test/test_evaluate.cc | 66 +++++++++++++++++++++++
6 files changed, 202 insertions(+), 49 deletions(-)
diff --git a/doc/admin-guide/plugins/prefetch.en.rst b/doc/admin-guide/plugins/prefetch.en.rst
index 7afcb4b9d..74312d934 100644
--- a/doc/admin-guide/plugins/prefetch.en.rst
+++ b/doc/admin-guide/plugins/prefetch.en.rst
@@ -162,7 +162,13 @@ the following URLs will be requested to be prefetched ::
Note ``--fetch-path-pattern`` is a PCRE regex/capture pattern and
``{$2+2}`` is a mechanism to calculate the next path by adding or
-subtracting integer numbers.
+subtracting integer numbers. The operands will be treated as unsigned
+32-bit integers. Invalid numbers are treated as zeroes, and numbers
+too large will be interpreted as 2\ :sup:`32`\ -1. If subtraction results in
+a negative number, 0 is returned instead. An output width may be
+specified with an integer followed by a colon, e.g. ``{8:$2+2}``,
+causing the resulting number to be padded with leading zeroes if it
+has fewer digits than the width.
Overhead from **next object** prefetch
diff --git a/plugins/prefetch/Makefile.inc b/plugins/prefetch/Makefile.inc
index cdfdf3066..e2e562938 100644
--- a/plugins/prefetch/Makefile.inc
+++ b/plugins/prefetch/Makefile.inc
@@ -24,4 +24,10 @@ prefetch_prefetch_la_SOURCES = \
prefetch/pattern.cc \
prefetch/fetch_policy.cc \
prefetch/fetch_policy_simple.cc \
- prefetch/fetch_policy_lru.cc
+ prefetch/fetch_policy_lru.cc \
+ prefetch/evaluate.cc
+
+check_PROGRAMS += prefetch/test_evaluate
+
+prefetch_test_evaluate_CPPFLAGS = $(AM_CPPFLAGS) -I$(abs_top_srcdir)/tests/include -DPREFETCH_UNIT_TEST
+prefetch_test_evaluate_SOURCES = prefetch/test/test_evaluate.cc prefetch/evaluate.cc prefetch/common.cc
diff --git a/plugins/prefetch/evaluate.cc b/plugins/prefetch/evaluate.cc
new file mode 100644
index 000000000..4a39269ae
--- /dev/null
+++ b/plugins/prefetch/evaluate.cc
@@ -0,0 +1,94 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+*/
+
+/**
+ * @file evaluate.h
+ * @brief Prefetch formula evaluation (header file).
+ */
+
+#include "evaluate.h"
+#include <sstream>
+#include <istream>
+#include <iomanip>
+#include <cstdint>
+#include <cinttypes>
+
+/**
+ * @brief Evaluate a math addition or subtraction expression.
+ *
+ * @param v string containing an expression, i.e. "3 + 4"
+ * @return string containing the result, i.e. "7"
+ */
+String
+evaluate(const String &v)
+{
+ if (v.empty()) {
+ return String("");
+ }
+
+ /* Find out if width is specified (hence leading zeros are required if the width is bigger then the result width) */
+ String stmt;
+ uint32_t len = 0;
+ size_t pos = v.find_first_of(':');
+ if (String::npos != pos) {
+ stmt.assign(v.substr(0, pos));
+ std::istringstream iss(stmt);
+ iss >> len;
+ stmt.assign(v.substr(pos + 1));
+ } else {
+ stmt.assign(v);
+ }
+ PrefetchDebug("statement: '%s', formatting length: %" PRIu32, stmt.c_str(), len);
+
+ uint64_t result = 0;
+ pos = stmt.find_first_of("+-");
+
+ if (String::npos == pos) {
+ uint32_t tmp;
+ std::istringstream iss(stmt);
+ iss >> tmp;
+ result = tmp;
+
+ PrefetchDebug("Single-operand expression: %s -> %" PRIu64, stmt.c_str(), result);
+ } else {
+ String leftOperand = stmt.substr(0, pos);
+ std::istringstream liss(leftOperand);
+ uint32_t a;
+ liss >> a;
+
+ String rightOperand = stmt.substr(pos + 1);
+ std::istringstream riss(rightOperand);
+ uint32_t b;
+ riss >> b;
+
+ if ('+' == stmt[pos]) {
+ result = static_cast<uint64_t>(a) + static_cast<uint64_t>(b);
+ } else {
+ if (a <= b) {
+ result = 0;
+ } else {
+ result = a - b;
+ }
+ }
+ }
+
+ std::ostringstream convert;
+ convert << std::setw(len) << std::setfill('0') << result;
+ PrefetchDebug("evaluation of '%s' resulted in '%s'", v.c_str(), convert.str().c_str());
+ return convert.str();
+}
diff --git a/plugins/prefetch/evaluate.h b/plugins/prefetch/evaluate.h
new file mode 100644
index 000000000..8a70d9490
--- /dev/null
+++ b/plugins/prefetch/evaluate.h
@@ -0,0 +1,27 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+*/
+
+/**
+ * @file evaluate.h
+ * @brief Prefetch formula evaluation (header file).
+ */
+
+#pragma once
+#include "common.h"
+
+String evaluate(const String &v);
diff --git a/plugins/prefetch/plugin.cc b/plugins/prefetch/plugin.cc
index 975c5d53c..f4fedef68 100644
--- a/plugins/prefetch/plugin.cc
+++ b/plugins/prefetch/plugin.cc
@@ -33,6 +33,7 @@
#include "fetch.h"
#include "fetch_policy.h"
#include "headers.h"
+#include "evaluate.h"
static const char *
getEventName(TSEvent event)
@@ -180,53 +181,6 @@ public:
String _body; /* body to return to the UA */
};
-/**
- * @brief Evaluate a math addition or subtraction expression.
- *
- * @param v string containing an expression, i.e. "3 + 4"
- * @return string containing the result, i.e. "7"
- */
-static String
-evaluate(const String &v)
-{
- if (v.empty()) {
- return String("");
- }
-
- /* Find out if width is specified (hence leading zeros are required if the width is bigger then the result width) */
- String stmt;
- size_t len = 0;
- size_t pos = v.find_first_of(':');
- if (String::npos != pos) {
- stmt.assign(v.substr(0, pos));
- len = getValue(v.substr(pos + 1));
- } else {
- stmt.assign(v);
- }
- PrefetchDebug("statement: '%s', formatting length: %zu", stmt.c_str(), len);
-
- int result = 0;
- pos = stmt.find_first_of("+-");
-
- if (String::npos == pos) {
- result = getValue(stmt);
- } else {
- unsigned a = getValue(stmt.substr(0, pos));
- unsigned b = getValue(stmt.substr(pos + 1));
-
- if ('+' == stmt[pos]) {
- result = a + b;
- } else {
- result = a - b;
- }
- }
-
- std::ostringstream convert;
- convert << std::setw(len) << std::setfill('0') << result;
- PrefetchDebug("evaluation of '%s' resulted in '%s'", v.c_str(), convert.str().c_str());
- return convert.str();
-}
-
/**
* @brief Expand+evaluate (in place) an expression surrounded with "{" and "}" and uses evaluate() to evaluate the math expression.
*
diff --git a/plugins/prefetch/test/test_evaluate.cc b/plugins/prefetch/test/test_evaluate.cc
new file mode 100644
index 000000000..e94b53fb0
--- /dev/null
+++ b/plugins/prefetch/test/test_evaluate.cc
@@ -0,0 +1,66 @@
+/*
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+*/
+
+/**
+ * @file test_plugin.cc
+ * @brief Unit tests for plugin.cc
+ */
+
+#define CATCH_CONFIG_MAIN
+#include <catch.hpp>
+#include "../evaluate.h"
+
+TEST_CASE("Basic computation works", "[evaluate]")
+{
+ REQUIRE(evaluate("1+3") == "4");
+ REQUIRE(evaluate("5-2") == "3");
+}
+
+TEST_CASE("Empty expression", "[empty]")
+{
+ REQUIRE(evaluate("") == "");
+}
+
+TEST_CASE("64-bit result works", "[evaluate64]")
+{
+ REQUIRE(evaluate("4294967295+4294967295") == "8589934590");
+}
+
+TEST_CASE("Larger number saturation", "[saturation]")
+{
+ REQUIRE(evaluate("3842948374928374982374982374") == "4294967295");
+ REQUIRE(evaluate("3248739487239847298374738924-4294967295") == "0");
+}
+
+TEST_CASE("Negative subtraction", "[negative]")
+{
+ REQUIRE(evaluate("24-498739847") == "0");
+}
+
+TEST_CASE("Treat invalid number as zero", "[invalid]")
+{
+ REQUIRE(evaluate("foobar") == "0");
+ REQUIRE(evaluate("foo+bar") == "0");
+ REQUIRE(evaluate("3+bar") == "3");
+}
+
+TEST_CASE("Padding with leading zeroes", "[padding]")
+{
+ REQUIRE(evaluate("5:1+2") == "00003");
+ REQUIRE(evaluate("2:123+123") == "246");
+}