query: $select : use trie
The previous implementation has a downside: it stores all intermediate
paths in a hashset. This increases the space complexity. This commit
implements a more efficient (both time and space) algorithm: Trie.
The commit contructs a trie from the values of $select. Upon delegation,
it delegates the whole trie for now. When doing recursive select, now we
only need to keep the current JSON node and corresponding TrieNode.
Given the following assumption:
1. size of the JSON tree (#nodes) is N
2. length of the $select properties is M
3. average length of a single $select property is K
The previous implementation has the following complexity:
1. time: worst case O(N + M * K), when a property is like /a/a/a/a/a
2. space: O(N + M * K^2), when a property is like /a/a/a/a/a
The current implementation improves complexity to:
1. time: O(N + M * K)
2. space: O(N + M * K)
The total image (squashfs) decreases 4096 bytes. The binaray size
also decreases 4096 bytes.
Tested:
1. $select works on real hardware
2. No new service validator failures
3. Added more unit tests
Signed-off-by: Nan Zhou <nanzhoumails@gmail.com>
Change-Id: If9f09db8c76e4e1abb6fa9b760be3816d9eb9f96
diff --git a/redfish-core/include/query.hpp b/redfish-core/include/query.hpp
index d9401bc..fd5d189 100644
--- a/redfish-core/include/query.hpp
+++ b/redfish-core/include/query.hpp
@@ -71,11 +71,13 @@
delegated = query_param::delegate(queryCapabilities, *queryOpt);
std::function<void(crow::Response&)> handler =
asyncResp->res.releaseCompleteRequestHandler();
+
asyncResp->res.setCompleteRequestHandler(
[&app, handler(std::move(handler)),
- query{*queryOpt}](crow::Response& resIn) mutable {
+ query{std::move(*queryOpt)}](crow::Response& resIn) mutable {
processAllParams(app, query, handler, resIn);
});
+
return true;
}
diff --git a/redfish-core/include/utils/query_param.hpp b/redfish-core/include/utils/query_param.hpp
index 48d184b..184043b 100644
--- a/redfish-core/include/utils/query_param.hpp
+++ b/redfish-core/include/utils/query_param.hpp
@@ -15,7 +15,6 @@
#include <boost/beast/http/message.hpp> // IWYU pragma: keep
#include <boost/beast/http/status.hpp>
#include <boost/beast/http/verb.hpp>
-#include <boost/url/error.hpp>
#include <boost/url/params_view.hpp>
#include <boost/url/string.hpp>
#include <nlohmann/json.hpp>
@@ -24,6 +23,7 @@
#include <array>
#include <cctype>
#include <charconv>
+#include <compare>
#include <cstdint>
#include <functional>
#include <iterator>
@@ -31,11 +31,9 @@
#include <map>
#include <memory>
#include <optional>
-#include <span>
#include <string>
#include <string_view>
#include <system_error>
-#include <unordered_set>
#include <utility>
#include <vector>
@@ -61,6 +59,113 @@
Both,
};
+// A simple implementation of Trie to help |recursiveSelect|.
+class SelectTrieNode
+{
+ public:
+ SelectTrieNode() = default;
+
+ const SelectTrieNode* find(const std::string& jsonKey) const
+ {
+ auto it = children.find(jsonKey);
+ if (it == children.end())
+ {
+ return nullptr;
+ }
+ return &it->second;
+ }
+
+ // Creates a new node if the key doesn't exist, returns the reference to the
+ // newly created node; otherwise, return the reference to the existing node
+ SelectTrieNode* emplace(std::string_view jsonKey)
+ {
+ auto [it, _] = children.emplace(jsonKey, SelectTrieNode{});
+ return &it->second;
+ }
+
+ bool empty() const
+ {
+ return children.empty();
+ }
+
+ void clear()
+ {
+ children.clear();
+ }
+
+ void setToSelected()
+ {
+ selected = true;
+ }
+
+ bool isSelected() const
+ {
+ return selected;
+ }
+
+ private:
+ std::map<std::string, SelectTrieNode, std::less<>> children;
+ bool selected = false;
+};
+
+// Validates the property in the $select parameter. Every character is among
+// [a-zA-Z0-9#@_.] (taken from Redfish spec, section 9.6 Properties)
+inline bool isSelectedPropertyAllowed(std::string_view property)
+{
+ // These a magic number, but with it it's less likely that this code
+ // introduces CVE; e.g., too large properties crash the service.
+ constexpr int maxPropertyLength = 60;
+ if (property.empty() || property.size() > maxPropertyLength)
+ {
+ return false;
+ }
+ for (char ch : property)
+ {
+ if (std::isalnum(static_cast<unsigned char>(ch)) == 0 && ch != '#' &&
+ ch != '@' && ch != '.')
+ {
+ return false;
+ }
+ }
+ return true;
+}
+
+struct SelectTrie
+{
+ SelectTrie() = default;
+
+ // Inserts a $select value; returns false if the nestedProperty is illegal.
+ bool insertNode(std::string_view nestedProperty)
+ {
+ if (nestedProperty.empty())
+ {
+ return false;
+ }
+ SelectTrieNode* currNode = &root;
+ size_t index = nestedProperty.find_first_of('/');
+ while (!nestedProperty.empty())
+ {
+ std::string_view property = nestedProperty.substr(0, index);
+ if (!isSelectedPropertyAllowed(property))
+ {
+ return false;
+ }
+ currNode = currNode->emplace(property);
+ if (index == std::string::npos)
+ {
+ break;
+ }
+ nestedProperty.remove_prefix(index + 1);
+ index = nestedProperty.find_first_of('/');
+ }
+
+ currNode->setToSelected();
+ return true;
+ }
+
+ SelectTrieNode root;
+};
+
// The struct stores the parsed query parameters of the default Redfish route.
struct Query
{
@@ -74,11 +179,10 @@
std::optional<size_t> skip = std::nullopt;
// Top
-
std::optional<size_t> top = std::nullopt;
// Select
- std::unordered_set<std::string> selectedProperties = {};
+ SelectTrie selectTrie = {};
};
// The struct defines how resource handlers in redfish-core/lib/ can handle
@@ -139,11 +243,10 @@
}
// delegate select
- if (!query.selectedProperties.empty() &&
- queryCapabilities.canDelegateSelect)
+ if (!query.selectTrie.root.empty() && queryCapabilities.canDelegateSelect)
{
- delegated.selectedProperties = std::move(query.selectedProperties);
- query.selectedProperties.clear();
+ delegated.selectTrie = std::move(query.selectTrie);
+ query.selectTrie.root.clear();
}
return delegated;
}
@@ -240,28 +343,6 @@
return QueryError::Ok;
}
-// Validates the property in the $select parameter. Every character is among
-// [a-zA-Z0-9\/#@_.] (taken from Redfish spec, section 9.6 Properties)
-inline bool isSelectedPropertyAllowed(std::string_view property)
-{
- // These a magic number, but with it it's less likely that this code
- // introduces CVE; e.g., too large properties crash the service.
- constexpr int maxPropertyLength = 60;
- if (property.empty() || property.size() > maxPropertyLength)
- {
- return false;
- }
- for (char ch : property)
- {
- if (std::isalnum(static_cast<unsigned char>(ch)) == 0 && ch != '/' &&
- ch != '#' && ch != '@' && ch != '.')
- {
- return false;
- }
- }
- return true;
-}
-
// Parses and validates the $select parameter.
// As per OData URL Conventions and Redfish Spec, the $select values shall be
// comma separated Resource Path
@@ -284,24 +365,20 @@
{
return false;
}
- for (std::string& property : properties)
+ for (const auto& property : properties)
{
- if (!isSelectedPropertyAllowed(property))
+ if (!query.selectTrie.insertNode(property))
{
return false;
}
- property.insert(property.begin(), '/');
}
- query.selectedProperties = {std::make_move_iterator(properties.begin()),
- std::make_move_iterator(properties.end())};
// Per the Redfish spec section 7.3.3, the service shall select certain
// properties as if $select was omitted.
constexpr std::array<std::string_view, 5> reservedProperties = {
- "/@odata.id", "/@odata.type", "/@odata.context", "/@odata.etag",
- "/error"};
+ "@odata.id", "@odata.type", "@odata.context", "@odata.etag", "error"};
for (auto const& str : reservedProperties)
{
- query.selectedProperties.emplace(std::string(str));
+ query.selectTrie.insertNode(str.data());
}
return true;
}
@@ -389,7 +466,7 @@
}
}
- if (ret.expandType != ExpandType::None && !ret.selectedProperties.empty())
+ if (ret.expandType != ExpandType::None && !ret.selectTrie.root.empty())
{
messages::queryCombinationInvalid(res);
return std::nullopt;
@@ -719,92 +796,53 @@
}
}
-// Given a JSON subtree |currRoot|, and its JSON pointer |currRootPtr| to the
-// |root| JSON in the async response, this function erases leaves whose keys are
-// not in the |shouldSelect| set.
-// |shouldSelect| contains all the properties that needs to be selected.
-inline void
- recursiveSelect(nlohmann::json& currRoot,
- const nlohmann::json::json_pointer& currRootPtr,
- const std::unordered_set<std::string>& intermediatePaths,
- const std::unordered_set<std::string>& properties)
+// Given a JSON subtree |currRoot|, this function erases leaves whose keys are
+// not in the |currNode| Trie node.
+inline void recursiveSelect(nlohmann::json& currRoot,
+ const SelectTrieNode& currNode)
{
nlohmann::json::object_t* object =
currRoot.get_ptr<nlohmann::json::object_t*>();
if (object != nullptr)
{
- BMCWEB_LOG_DEBUG << "Current JSON is an object: " << currRootPtr;
+ BMCWEB_LOG_DEBUG << "Current JSON is an object";
auto it = currRoot.begin();
while (it != currRoot.end())
{
auto nextIt = std::next(it);
- nlohmann::json::json_pointer childPtr = currRootPtr / it.key();
- BMCWEB_LOG_DEBUG << "childPtr=" << childPtr;
- if (properties.contains(childPtr))
+ BMCWEB_LOG_DEBUG << "key=" << it.key();
+ const SelectTrieNode* nextNode = currNode.find(it.key());
+ if (nextNode != nullptr && nextNode->isSelected())
{
it = nextIt;
continue;
}
- if (intermediatePaths.contains(childPtr))
+ if (nextNode != nullptr)
{
- BMCWEB_LOG_DEBUG << "Recursively select: " << childPtr;
- recursiveSelect(*it, childPtr, intermediatePaths, properties);
+ BMCWEB_LOG_DEBUG << "Recursively select: " << it.key();
+ recursiveSelect(*it, *nextNode);
it = nextIt;
continue;
}
- BMCWEB_LOG_DEBUG << childPtr << " is getting removed!";
+ BMCWEB_LOG_DEBUG << it.key() << " is getting removed!";
it = currRoot.erase(it);
}
}
}
-inline std::unordered_set<std::string>
- getIntermediatePaths(const std::unordered_set<std::string>& properties)
-{
- std::unordered_set<std::string> res;
- std::vector<std::string> segments;
-
- for (auto const& property : properties)
- {
- // Omit the root "/" and split all other segments
- boost::split(segments, property.substr(1), boost::is_any_of("/"));
- std::string path;
- if (!segments.empty())
- {
- segments.pop_back();
- }
- for (auto const& segment : segments)
- {
- path += '/';
- path += segment;
- res.insert(path);
- }
- }
- return res;
-}
-
-inline void performSelect(nlohmann::json& root,
- const std::unordered_set<std::string>& properties)
-{
- std::unordered_set<std::string> intermediatePaths =
- getIntermediatePaths(properties);
- recursiveSelect(root, nlohmann::json::json_pointer(""), intermediatePaths,
- properties);
-}
-
// The current implementation of $select still has the following TODOs due to
// ambiguity and/or complexity.
// 1. select properties in array of objects;
// https://github.com/DMTF/Redfish/issues/5188 was created for clarification.
// 2. combined with $expand; https://github.com/DMTF/Redfish/issues/5058 was
// created for clarification.
-// 2. respect the full odata spec; e.g., deduplication, namespace, star (*),
+// 3. respect the full odata spec; e.g., deduplication, namespace, star (*),
// etc.
inline void processSelect(crow::Response& intermediateResponse,
- const std::unordered_set<std::string>& shouldSelect)
+ const SelectTrieNode& trieRoot)
{
BMCWEB_LOG_DEBUG << "Process $select quary parameter";
- performSelect(intermediateResponse.jsonValue, shouldSelect);
+ recursiveSelect(intermediateResponse.jsonValue, trieRoot);
}
inline void
@@ -852,9 +890,9 @@
// According to Redfish Spec Section 7.3.1, $select is the last parameter to
// to process
- if (!query.selectedProperties.empty())
+ if (!query.selectTrie.root.empty())
{
- processSelect(intermediateResponse, query.selectedProperties);
+ processSelect(intermediateResponse, query.selectTrie.root);
}
completionHandler(intermediateResponse);
diff --git a/redfish-core/include/utils/query_param_test.cpp b/redfish-core/include/utils/query_param_test.cpp
index a852246..ddc7e33 100644
--- a/redfish-core/include/utils/query_param_test.cpp
+++ b/redfish-core/include/utils/query_param_test.cpp
@@ -7,6 +7,7 @@
#include <nlohmann/json.hpp>
#include <new>
+#include <span>
#include <gmock/gmock.h> // IWYU pragma: keep
#include <gtest/gtest.h> // IWYU pragma: keep
@@ -23,7 +24,6 @@
namespace
{
-using ::testing::Eq;
using ::testing::UnorderedElementsAre;
TEST(Delegate, OnlyPositive)
@@ -165,6 +165,7 @@
EXPECT_FALSE(isSelectedPropertyAllowed("?"));
EXPECT_FALSE(isSelectedPropertyAllowed("!"));
EXPECT_FALSE(isSelectedPropertyAllowed("-"));
+ EXPECT_FALSE(isSelectedPropertyAllowed("/"));
}
TEST(IsSelectedPropertyAllowed, EmptyStringReturnsFalse)
@@ -189,7 +190,7 @@
EXPECT_TRUE(isSelectedPropertyAllowed("@odata.type"));
EXPECT_TRUE(isSelectedPropertyAllowed("#ComputerSystem.Reset"));
EXPECT_TRUE(isSelectedPropertyAllowed(
- "Boot/BootSourceOverrideTarget@Redfish.AllowableValues"));
+ "BootSourceOverrideTarget@Redfish.AllowableValues"));
}
TEST(GetSelectParam, EmptyValueReturnsError)
@@ -212,79 +213,104 @@
EXPECT_FALSE(getSelectParam("%%%", query));
}
-TEST(GetSelectParam, PropertyReturnsOk)
+TEST(GetSelectParam, TrieNodesRespectAllProperties)
{
Query query;
ASSERT_TRUE(getSelectParam("foo/bar,bar", query));
- EXPECT_THAT(query.selectedProperties,
- UnorderedElementsAre(Eq("/foo/bar"), Eq("/bar"),
- Eq("/@odata.id"), Eq("/@odata.type"),
- Eq("/@odata.context"), Eq("/@odata.etag"),
- Eq("/error")));
+ ASSERT_FALSE(query.selectTrie.root.empty());
+
+ ASSERT_NE(query.selectTrie.root.find("bar"), nullptr);
+ EXPECT_TRUE(query.selectTrie.root.find("bar")->isSelected());
+
+ ASSERT_NE(query.selectTrie.root.find("@odata.id"), nullptr);
+ EXPECT_TRUE(query.selectTrie.root.find("@odata.id")->isSelected());
+
+ ASSERT_NE(query.selectTrie.root.find("@odata.type"), nullptr);
+ EXPECT_TRUE(query.selectTrie.root.find("@odata.type")->isSelected());
+
+ ASSERT_NE(query.selectTrie.root.find("@odata.context"), nullptr);
+ EXPECT_TRUE(query.selectTrie.root.find("@odata.context")->isSelected());
+
+ ASSERT_NE(query.selectTrie.root.find("@odata.etag"), nullptr);
+ EXPECT_TRUE(query.selectTrie.root.find("@odata.etag")->isSelected());
+
+ ASSERT_NE(query.selectTrie.root.find("error"), nullptr);
+ EXPECT_TRUE(query.selectTrie.root.find("error")->isSelected());
+
+ const SelectTrieNode* child = query.selectTrie.root.find("foo");
+ ASSERT_NE(child, nullptr);
+ EXPECT_FALSE(child->isSelected());
+ ASSERT_NE(child->find("bar"), nullptr);
+ EXPECT_TRUE(child->find("bar")->isSelected());
}
-TEST(GetIntermediatePaths, AllIntermediatePathsAreReturned)
+SelectTrie getTrie(std::span<std::string_view> properties)
{
- std::unordered_set<std::string> properties = {"/foo/bar/213"};
- EXPECT_THAT(getIntermediatePaths(properties),
- UnorderedElementsAre(Eq("/foo/bar"), Eq("/foo")));
+ SelectTrie trie;
+ for (auto const& property : properties)
+ {
+ EXPECT_TRUE(trie.insertNode(property));
+ }
+ return trie;
}
TEST(RecursiveSelect, ExpectedKeysAreSelectInSimpleObject)
{
- std::unordered_set<std::string> shouldSelect = {"/select_me"};
- nlohmann::json root = R"({"select_me" : "foo", "omit_me" : "bar"})"_json;
- nlohmann::json expected = R"({"select_me" : "foo"})"_json;
- performSelect(root, shouldSelect);
+ std::vector<std::string_view> properties = {"SelectMe"};
+ SelectTrie trie = getTrie(properties);
+ nlohmann::json root = R"({"SelectMe" : "foo", "OmitMe" : "bar"})"_json;
+ nlohmann::json expected = R"({"SelectMe" : "foo"})"_json;
+ recursiveSelect(root, trie.root);
EXPECT_EQ(root, expected);
}
TEST(RecursiveSelect, ExpectedKeysAreSelectInNestedObject)
{
- std::unordered_set<std::string> shouldSelect = {
- "/select_me", "/prefix0/explicit_select_me", "/prefix1", "/prefix2"};
+ std::vector<std::string_view> properties = {
+ "SelectMe", "Prefix0/ExplicitSelectMe", "Prefix1", "Prefix2"};
+ SelectTrie trie = getTrie(properties);
nlohmann::json root = R"(
{
- "select_me":[
+ "SelectMe":[
"foo"
],
- "omit_me":"bar",
- "prefix0":{
- "explicit_select_me":"123",
- "omit_me":"456"
+ "OmitMe":"bar",
+ "Prefix0":{
+ "ExplicitSelectMe":"123",
+ "OmitMe":"456"
},
- "prefix1":{
- "implicit_select_me":"123"
+ "Prefix1":{
+ "ImplicitSelectMe":"123"
},
- "prefix2":[
+ "Prefix2":[
{
- "implicit_select_me":"123"
+ "ImplicitSelectMe":"123"
}
],
- "prefix3":[
- "omit_me"
+ "Prefix3":[
+ "OmitMe"
]
}
)"_json;
nlohmann::json expected = R"(
{
- "select_me":[
+ "SelectMe":[
"foo"
],
- "prefix0":{
- "explicit_select_me":"123"
+ "Prefix0":{
+ "ExplicitSelectMe":"123"
},
- "prefix1":{
- "implicit_select_me":"123"
+ "Prefix1":{
+ "ImplicitSelectMe":"123"
},
- "prefix2":[
+ "Prefix2":[
{
- "implicit_select_me":"123"
+ "ImplicitSelectMe":"123"
}
]
}
)"_json;
- performSelect(root, shouldSelect);
+ recursiveSelect(root, trie.root);
EXPECT_EQ(root, expected);
}
@@ -292,19 +318,19 @@
{
nlohmann::json root = R"(
{
- "omit_me":"bar",
+ "OmitMe":"bar",
"@odata.id":1,
"@odata.type":2,
"@odata.context":3,
"@odata.etag":4,
"prefix1":{
- "omit_me":"bar",
+ "OmitMe":"bar",
"@odata.id":1
},
- "prefix2":[1, 2, 3],
- "prefix3":[
+ "Prefix2":[1, 2, 3],
+ "Prefix3":[
{
- "omit_me":"bar",
+ "OmitMe":"bar",
"@odata.id":1
}
]
@@ -325,7 +351,7 @@
if constexpr (bmcwebInsecureEnableQueryParams)
{
ASSERT_NE(query, std::nullopt);
- performSelect(root, query->selectedProperties);
+ recursiveSelect(root, query->selectTrie.root);
EXPECT_EQ(root, expected);
}
else