Expand query: reimplement the way to do subqueries

For any expand query, the current implementation does all queries in a
single MultiAsyncResp, where the code sends a bunch of requests without
Query parameters. This makes it impossible to invoke efficient expand
handlers, since efficent handlers will only be invoked when a query has
$expand in its parameters. (Delegation only happens when the query
contains query parameters)

To solve it, in this commit, we proposed to send a bunch of requests
**WITH** Query parameters in MultiAsyncResp. This makes
"/redfish/v1/Chassis/chassis?expand=.($levels=2)" be able to invoke
efficient expand handlers that we developed for sensors, which existing
implementation can't do. This decreases latency by nearly 100 times (the
improvement that efficient sensor expand handler provides) on real
hardware which contains 5+ chassis and totally 220+ sensors.

This commit aligns with future $select support well, since the recursive
queries can add $select as part of the query parameters.

With this commit, though we create multiple MultiAsyncResp objects
memory doesn't increase significantly; part of the reason is that we are
not copying Query anymore in MultiAsyncResp.
No out-of-memory issues are found when 4 threads are querying
expand=levels=6 at the service root on a real large hardware which
contains 2+ sockets, 5+ chassis, 220+ sensors, 30+ DIMMs, etc.

Tested:
1. On real hardware, /redfish/v1/Chassis?$expand=.(level=3) is giving
the correct result and invokes efficient sensor Expand handler
2. stress test
```
for i in {1..4};
do
  echo "thread $i"
  wget -qO- 'http://localhost:18080/redfish/v1?$expand=*($levels=6)' > "/tmp/$i.log" &
done

for i in {1..1000};
do
  top -b -n 1 | grep bmcweb >> /tmp/bmcweb_ori.log
  sleep 1
done
```
Results
```
25878  2856 root     R     194m  20%   1  38% /tmp/bmcweb_after
19005  2856 root     R     215m  22%   1  36% /tmp/bmcweb_ori
```

Signed-off-by: Nan Zhou <nanzhoumails@gmail.com>
Change-Id: I0e661db0263f56dd0cab66047a0a5d4fff31b69a

2 files changed, 114 insertions, 79 deletions

diff --git a/redfish-core/include/utils/query_param.hpp b/redfish-core/include/utils/query_param.hpp
index 5c43255de9..9f17b7bdd6 100644
--- a/redfish-core/include/utils/query_param.hpp
+++ b/redfish-core/include/utils/query_param.hpp
@@ -414,14 +414,48 @@ inline void findNavigationReferencesRecursive(
 }
 
 inline std::vector<ExpandNode>
-    findNavigationReferences(ExpandType eType, nlohmann::json& jsonResponse,
-                             const nlohmann::json::json_pointer& root)
+    findNavigationReferences(ExpandType eType, nlohmann::json& jsonResponse)
 {
     std::vector<ExpandNode> ret;
+    const nlohmann::json::json_pointer root = nlohmann::json::json_pointer("");
     findNavigationReferencesRecursive(eType, jsonResponse, root, false, ret);
     return ret;
 }
 
+// Formats a query parameter string for the sub-query.
+// This function shall handle $select when it is added.
+// There is no need to handle parameters that's not campatible with $expand,
+// e.g., $only, since this function will only be called in side $expand handlers
+inline std::string formatQueryForExpand(const Query& query)
+{
+    // query.expandLevel<=1: no need to do subqueries
+    if (query.expandLevel <= 1)
+    {
+        return {};
+    }
+    std::string str = "?$expand=";
+    switch (query.expandType)
+    {
+        case ExpandType::None:
+            return {};
+        case ExpandType::Links:
+            str += '~';
+            break;
+        case ExpandType::NotLinks:
+            str += '.';
+            break;
+        case ExpandType::Both:
+            str += '*';
+            break;
+        default:
+            return {};
+    }
+    str += "($levels=";
+    str += std::to_string(query.expandLevel - 1);
+    str += ')';
+    return str;
+}
+
 class MultiAsyncResp : public std::enable_shared_from_this<MultiAsyncResp>
 {
   public:
@@ -436,58 +470,57 @@ class MultiAsyncResp : public std::enable_shared_from_this<MultiAsyncResp>
     {}
 
     void addAwaitingResponse(
-        Query query, std::shared_ptr<bmcweb::AsyncResp>& res,
+        std::shared_ptr<bmcweb::AsyncResp>& res,
         const nlohmann::json::json_pointer& finalExpandLocation)
     {
         res->res.setCompleteRequestHandler(std::bind_front(
-            onEndStatic, shared_from_this(), query, finalExpandLocation));
+            placeResultStatic, shared_from_this(), finalExpandLocation));
     }
 
-    void onEnd(Query query, const nlohmann::json::json_pointer& locationToPlace,
-               crow::Response& res)
+    void placeResult(const nlohmann::json::json_pointer& locationToPlace,
+                     crow::Response& res)
     {
         nlohmann::json& finalObj = finalRes->res.jsonValue[locationToPlace];
         finalObj = std::move(res.jsonValue);
+    }
 
-        if (query.expandLevel <= 0)
-        {
-            // Last level to expand, no need to go deeper
-            return;
-        }
-        // Now decrease the depth by one to account for the tree node we
-        // just resolved
-        query.expandLevel--;
-
-        std::vector<ExpandNode> nodes = findNavigationReferences(
-            query.expandType, finalObj, locationToPlace);
+    // Handles the very first level of Expand, and starts a chain of sub-queries
+    // for deeper levels.
+    void startQuery(const Query& query)
+    {
+        std::vector<ExpandNode> nodes =
+            findNavigationReferences(query.expandType, finalRes->res.jsonValue);
         BMCWEB_LOG_DEBUG << nodes.size() << " nodes to traverse";
+        const std::string queryStr = formatQueryForExpand(query);
         for (const ExpandNode& node : nodes)
         {
-            BMCWEB_LOG_DEBUG << "Expanding " << locationToPlace;
+            const std::string subQuery = node.uri + queryStr;
+            BMCWEB_LOG_DEBUG << "URL of subquery:  " << subQuery;
             std::error_code ec;
-            crow::Request newReq({boost::beast::http::verb::get, node.uri, 11},
+            crow::Request newReq({boost::beast::http::verb::get, subQuery, 11},
                                  ec);
             if (ec)
             {
-                messages::internalError(res);
+                messages::internalError(finalRes->res);
                 return;
             }
 
             auto asyncResp = std::make_shared<bmcweb::AsyncResp>();
             BMCWEB_LOG_DEBUG << "setting completion handler on "
                              << &asyncResp->res;
-            addAwaitingResponse(query, asyncResp, node.location);
+
+            addAwaitingResponse(asyncResp, node.location);
             app.handle(newReq, asyncResp);
         }
     }
 
   private:
-    static void onEndStatic(const std::shared_ptr<MultiAsyncResp>& multi,
-                            Query query,
-                            const nlohmann::json::json_pointer& locationToPlace,
-                            crow::Response& res)
+    static void
+        placeResultStatic(const std::shared_ptr<MultiAsyncResp>& multi,
+                          const nlohmann::json::json_pointer& locationToPlace,
+                          crow::Response& res)
     {
-        multi->onEnd(query, locationToPlace, res);
+        multi->placeResult(locationToPlace, res);
     }
 
     crow::App& app;
@@ -577,8 +610,7 @@ inline void
         asyncResp->res.jsonValue = std::move(intermediateResponse.jsonValue);
         auto multi = std::make_shared<MultiAsyncResp>(app, asyncResp);
 
-        // Start the chain by "ending" the root response
-        multi->onEnd(query, nlohmann::json::json_pointer(""), asyncResp->res);
+        multi->startQuery(query);
         return;
     }
     completionHandler(intermediateResponse);
diff --git a/redfish-core/include/utils/query_param_test.cpp b/redfish-core/include/utils/query_param_test.cpp
index 93013c2f3f..a87d954d6b 100644
--- a/redfish-core/include/utils/query_param_test.cpp
+++ b/redfish-core/include/utils/query_param_test.cpp
@@ -111,6 +111,41 @@ TEST(Delegate, SkipPositive)
     EXPECT_EQ(query.skip, 42);
 }
 
+TEST(FormatQueryForExpand, NoSubQueryWhenQueryIsEmpty)
+{
+    EXPECT_EQ(formatQueryForExpand(Query{}), "");
+}
+
+TEST(FormatQueryForExpand, NoSubQueryWhenExpandLevelsLeOne)
+{
+    EXPECT_EQ(formatQueryForExpand(
+                  Query{.expandLevel = 1, .expandType = ExpandType::Both}),
+              "");
+    EXPECT_EQ(formatQueryForExpand(Query{.expandType = ExpandType::Links}), "");
+    EXPECT_EQ(formatQueryForExpand(Query{.expandType = ExpandType::NotLinks}),
+              "");
+}
+
+TEST(FormatQueryForExpand, NoSubQueryWhenExpandTypeIsNone)
+{
+    EXPECT_EQ(formatQueryForExpand(
+                  Query{.expandLevel = 2, .expandType = ExpandType::None}),
+              "");
+}
+
+TEST(FormatQueryForExpand, DelegatedSubQueriesHaveSameTypeAndOneLessLevels)
+{
+    EXPECT_EQ(formatQueryForExpand(
+                  Query{.expandLevel = 3, .expandType = ExpandType::Both}),
+              "?$expand=*($levels=2)");
+    EXPECT_EQ(formatQueryForExpand(
+                  Query{.expandLevel = 4, .expandType = ExpandType::Links}),
+              "?$expand=~($levels=3)");
+    EXPECT_EQ(formatQueryForExpand(
+                  Query{.expandLevel = 2, .expandType = ExpandType::NotLinks}),
+              "?$expand=.($levels=1)");
+}
+
 } // namespace
 } // namespace redfish::query_param
 
@@ -295,37 +330,29 @@ TEST(QueryParams, FindNavigationReferencesNonLink)
     json singleTreeNode = R"({"Foo" : {"@odata.id": "/foobar"}})"_json;
 
     // Parsing as the root should net one entry
-    EXPECT_THAT(findNavigationReferences(ExpandType::Both, singleTreeNode,
-                                         json::json_pointer("")),
+    EXPECT_THAT(findNavigationReferences(ExpandType::Both, singleTreeNode),
                 UnorderedElementsAre(redfish::query_param::ExpandNode{
                     json::json_pointer("/Foo"), "/foobar"}));
-    // Parsing at a depth should net one entry at depth
-    EXPECT_THAT(findNavigationReferences(ExpandType::Both, singleTreeNode,
-                                         json::json_pointer("/baz")),
-                UnorderedElementsAre(redfish::query_param::ExpandNode{
-                    json::json_pointer("/baz/Foo"), "/foobar"}));
 
     // Parsing in Non-hyperlinks mode should net one entry
-    EXPECT_THAT(findNavigationReferences(ExpandType::NotLinks, singleTreeNode,
-                                         json::json_pointer("")),
+    EXPECT_THAT(findNavigationReferences(ExpandType::NotLinks, singleTreeNode),
                 UnorderedElementsAre(redfish::query_param::ExpandNode{
                     json::json_pointer("/Foo"), "/foobar"}));
 
-    // Parsing non-hyperlinks at depth should net one entry at depth
-    EXPECT_THAT(findNavigationReferences(ExpandType::NotLinks, singleTreeNode,
-                                         json::json_pointer("/baz")),
-                UnorderedElementsAre(redfish::query_param::ExpandNode{
-                    json::json_pointer("/baz/Foo"), "/foobar"}));
-
     // Searching for not types should return empty set
-    EXPECT_TRUE(findNavigationReferences(ExpandType::None, singleTreeNode,
-                                         json::json_pointer(""))
-                    .empty());
+    EXPECT_TRUE(
+        findNavigationReferences(ExpandType::None, singleTreeNode).empty());
 
     // Searching for hyperlinks only should return empty set
-    EXPECT_TRUE(findNavigationReferences(ExpandType::Links, singleTreeNode,
-                                         json::json_pointer(""))
-                    .empty());
+    EXPECT_TRUE(
+        findNavigationReferences(ExpandType::Links, singleTreeNode).empty());
+
+    json multiTreeNodes =
+        R"({"Links": {"@odata.id": "/links"}, "Foo" : {"@odata.id": "/foobar"}})"_json;
+    // Should still find Foo
+    EXPECT_THAT(findNavigationReferences(ExpandType::NotLinks, multiTreeNodes),
+                UnorderedElementsAre(redfish::query_param::ExpandNode{
+                    json::json_pointer("/Foo"), "/foobar"}));
 }
 
 TEST(QueryParams, FindNavigationReferencesLink)
@@ -338,43 +365,19 @@ TEST(QueryParams, FindNavigationReferencesLink)
         R"({"Links" : {"Sessions": {"@odata.id": "/foobar"}}})"_json;
 
     // Parsing as the root should net one entry
-    EXPECT_THAT(findNavigationReferences(ExpandType::Both, singleLinkNode,
-                                         json::json_pointer("")),
+    EXPECT_THAT(findNavigationReferences(ExpandType::Both, singleLinkNode),
                 UnorderedElementsAre(redfish::query_param::ExpandNode{
                     json::json_pointer("/Links/Sessions"), "/foobar"}));
-    // Parsing at a depth should net one entry at depth
-    EXPECT_THAT(findNavigationReferences(ExpandType::Both, singleLinkNode,
-                                         json::json_pointer("/baz")),
-                UnorderedElementsAre(redfish::query_param::ExpandNode{
-                    json::json_pointer("/baz/Links/Sessions"), "/foobar"}));
-
     // Parsing in hyperlinks mode should net one entry
-    EXPECT_THAT(findNavigationReferences(ExpandType::Links, singleLinkNode,
-                                         json::json_pointer("")),
+    EXPECT_THAT(findNavigationReferences(ExpandType::Links, singleLinkNode),
                 UnorderedElementsAre(redfish::query_param::ExpandNode{
                     json::json_pointer("/Links/Sessions"), "/foobar"}));
 
-    // Parsing hyperlinks at depth should net one entry at depth
-    EXPECT_THAT(findNavigationReferences(ExpandType::Links, singleLinkNode,
-                                         json::json_pointer("/baz")),
-                UnorderedElementsAre(redfish::query_param::ExpandNode{
-                    json::json_pointer("/baz/Links/Sessions"), "/foobar"}));
-
     // Searching for not types should return empty set
-    EXPECT_TRUE(findNavigationReferences(ExpandType::None, singleLinkNode,
-                                         json::json_pointer(""))
-                    .empty());
+    EXPECT_TRUE(
+        findNavigationReferences(ExpandType::None, singleLinkNode).empty());
 
     // Searching for non-hyperlinks only should return empty set
-    EXPECT_TRUE(findNavigationReferences(ExpandType::NotLinks, singleLinkNode,
-                                         json::json_pointer(""))
-                    .empty());
-
-    json multiTreeNodes =
-        R"({"Links": {"@odata.id": "/links"}, "Foo" : {"@odata.id": "/foobar"}})"_json;
-    // Should still find Foo
-    EXPECT_THAT(findNavigationReferences(ExpandType::NotLinks, multiTreeNodes,
-                                         json::json_pointer("")),
-                UnorderedElementsAre(redfish::query_param::ExpandNode{
-                    json::json_pointer("/Foo"), "/foobar"}));
+    EXPECT_TRUE(
+        findNavigationReferences(ExpandType::NotLinks, singleLinkNode).empty());
 }