xref: /openbmc/bmcweb/http/routing.hpp (revision d78572018fc2022091ff8b8eb5a7fef2172ba3d6) 
1 // SPDX-License-Identifier: Apache-2.0
2 // SPDX-FileCopyrightText: Copyright OpenBMC Authors
3 #pragma once
4 
5 #include "async_resp.hpp"
6 #include "dbus_privileges.hpp"
7 #include "http_request.hpp"
8 #include "http_response.hpp"
9 #include "logging.hpp"
10 #include "routing/baserule.hpp"
11 #include "routing/dynamicrule.hpp"
12 #include "routing/taggedrule.hpp"
13 #include "verb.hpp"
14 
15 #include <boost/beast/http/field.hpp>
16 #include <boost/beast/http/status.hpp>
17 #include <boost/container/flat_map.hpp>
18 #include <boost/container/small_vector.hpp>
19 
20 #include <algorithm>
21 #include <array>
22 #include <cerrno>
23 #include <cstdint>
24 #include <cstdlib>
25 #include <format>
26 #include <functional>
27 #include <memory>
28 #include <optional>
29 #include <stdexcept>
30 #include <string>
31 #include <string_view>
32 #include <tuple>
33 #include <utility>
34 #include <vector>
35 
36 namespace crow
37 {
38 
39 class Trie
40 {
41   public:
42     struct Node
43     {
44         unsigned ruleIndex = 0U;
45 
46         size_t stringParamChild = 0U;
47         size_t pathParamChild = 0U;
48 
49         using ChildMap = boost::container::flat_map<
50             std::string, unsigned, std::less<>,
51             boost::container::small_vector<std::pair<std::string, unsigned>,
52                                            1>>;
53         ChildMap children;
54 
isSimpleNodecrow::Trie::Node55         bool isSimpleNode() const
56         {
57             return ruleIndex == 0 && stringParamChild == 0 &&
58                    pathParamChild == 0;
59         }
60     };
61 
Trie()62     Trie() : nodes(1) {}
63 
64   private:
optimizeNode(Node & node)65     void optimizeNode(Node& node)
66     {
67         if (node.stringParamChild != 0U)
68         {
69             optimizeNode(nodes[node.stringParamChild]);
70         }
71         if (node.pathParamChild != 0U)
72         {
73             optimizeNode(nodes[node.pathParamChild]);
74         }
75 
76         if (node.children.empty())
77         {
78             return;
79         }
80         while (true)
81         {
82             bool didMerge = false;
83             Node::ChildMap merged;
84             for (const Node::ChildMap::value_type& kv : node.children)
85             {
86                 Node& child = nodes[kv.second];
87                 if (child.isSimpleNode())
88                 {
89                     for (const Node::ChildMap::value_type& childKv :
90                          child.children)
91                     {
92                         merged[kv.first + childKv.first] = childKv.second;
93                         didMerge = true;
94                     }
95                 }
96                 else
97                 {
98                     merged[kv.first] = kv.second;
99                 }
100             }
101             node.children = std::move(merged);
102             if (!didMerge)
103             {
104                 break;
105             }
106         }
107 
108         for (const Node::ChildMap::value_type& kv : node.children)
109         {
110             optimizeNode(nodes[kv.second]);
111         }
112     }
113 
optimize()114     void optimize()
115     {
116         optimizeNode(head());
117     }
118 
119   public:
validate()120     void validate()
121     {
122         optimize();
123     }
124 
findRouteIndexesHelper(std::string_view reqUrl,std::vector<unsigned> & routeIndexes,const Node & node) const125     void findRouteIndexesHelper(std::string_view reqUrl,
126                                 std::vector<unsigned>& routeIndexes,
127                                 const Node& node) const
128     {
129         for (const Node::ChildMap::value_type& kv : node.children)
130         {
131             const std::string& fragment = kv.first;
132             const Node& child = nodes[kv.second];
133             if (reqUrl.empty())
134             {
135                 if (child.ruleIndex != 0 && fragment != "/")
136                 {
137                     routeIndexes.push_back(child.ruleIndex);
138                 }
139                 findRouteIndexesHelper(reqUrl, routeIndexes, child);
140             }
141             else
142             {
143                 if (reqUrl.starts_with(fragment))
144                 {
145                     findRouteIndexesHelper(reqUrl.substr(fragment.size()),
146                                            routeIndexes, child);
147                 }
148             }
149         }
150     }
151 
findRouteIndexes(const std::string & reqUrl,std::vector<unsigned> & routeIndexes) const152     void findRouteIndexes(const std::string& reqUrl,
153                           std::vector<unsigned>& routeIndexes) const
154     {
155         findRouteIndexesHelper(reqUrl, routeIndexes, head());
156     }
157 
158     struct FindResult
159     {
160         unsigned ruleIndex;
161         std::vector<std::string> params;
162     };
163 
164   private:
findHelper(const std::string_view reqUrl,const Node & node,std::vector<std::string> & params) const165     FindResult findHelper(const std::string_view reqUrl, const Node& node,
166                           std::vector<std::string>& params) const
167     {
168         if (reqUrl.empty())
169         {
170             return {node.ruleIndex, params};
171         }
172 
173         if (node.stringParamChild != 0U)
174         {
175             size_t epos = 0;
176             for (; epos < reqUrl.size(); epos++)
177             {
178                 if (reqUrl[epos] == '/')
179                 {
180                     break;
181                 }
182             }
183 
184             if (epos != 0)
185             {
186                 params.emplace_back(reqUrl.substr(0, epos));
187                 FindResult ret = findHelper(
188                     reqUrl.substr(epos), nodes[node.stringParamChild], params);
189                 if (ret.ruleIndex != 0U)
190                 {
191                     return {ret.ruleIndex, std::move(ret.params)};
192                 }
193                 params.pop_back();
194             }
195         }
196 
197         if (node.pathParamChild != 0U)
198         {
199             params.emplace_back(reqUrl);
200             FindResult ret = findHelper("", nodes[node.pathParamChild], params);
201             if (ret.ruleIndex != 0U)
202             {
203                 return {ret.ruleIndex, std::move(ret.params)};
204             }
205             params.pop_back();
206         }
207 
208         for (const Node::ChildMap::value_type& kv : node.children)
209         {
210             const std::string& fragment = kv.first;
211             const Node& child = nodes[kv.second];
212 
213             if (reqUrl.starts_with(fragment))
214             {
215                 FindResult ret =
216                     findHelper(reqUrl.substr(fragment.size()), child, params);
217                 if (ret.ruleIndex != 0U)
218                 {
219                     return {ret.ruleIndex, std::move(ret.params)};
220                 }
221             }
222         }
223 
224         return {0U, std::vector<std::string>()};
225     }
226 
227   public:
find(const std::string_view reqUrl) const228     FindResult find(const std::string_view reqUrl) const
229     {
230         std::vector<std::string> start;
231         return findHelper(reqUrl, head(), start);
232     }
233 
add(std::string_view urlIn,unsigned ruleIndex)234     void add(std::string_view urlIn, unsigned ruleIndex)
235     {
236         size_t idx = 0;
237 
238         std::string_view url = urlIn;
239 
240         while (!url.empty())
241         {
242             char c = url[0];
243             if (c == '<')
244             {
245                 bool found = false;
246                 for (const std::string_view str1 :
247                      {"<str>", "<string>", "<path>"})
248                 {
249                     if (!url.starts_with(str1))
250                     {
251                         continue;
252                     }
253                     found = true;
254                     Node& node = nodes[idx];
255                     size_t* param = &node.stringParamChild;
256                     if (str1 == "<path>")
257                     {
258                         param = &node.pathParamChild;
259                     }
260                     if (*param == 0U)
261                     {
262                         *param = newNode();
263                     }
264                     idx = *param;
265 
266                     url.remove_prefix(str1.size());
267                     break;
268                 }
269                 if (found)
270                 {
271                     continue;
272                 }
273 
274                 BMCWEB_LOG_CRITICAL("Can't find tag for {}", urlIn);
275                 return;
276             }
277             std::string piece(&c, 1);
278             if (!nodes[idx].children.contains(piece))
279             {
280                 unsigned newNodeIdx = newNode();
281                 nodes[idx].children.emplace(piece, newNodeIdx);
282             }
283             idx = nodes[idx].children[piece];
284             url.remove_prefix(1);
285         }
286         Node& node = nodes[idx];
287         if (node.ruleIndex != 0U)
288         {
289             BMCWEB_LOG_CRITICAL("handler already exists for \"{}\"", urlIn);
290             throw std::runtime_error(
291                 std::format("handler already exists for \"{}\"", urlIn));
292         }
293         node.ruleIndex = ruleIndex;
294     }
295 
296   private:
debugNodePrint(Node & n,size_t level)297     void debugNodePrint(Node& n, size_t level)
298     {
299         std::string spaces(level, ' ');
300         if (n.stringParamChild != 0U)
301         {
302             BMCWEB_LOG_DEBUG("{}<str>", spaces);
303             debugNodePrint(nodes[n.stringParamChild], level + 5);
304         }
305         if (n.pathParamChild != 0U)
306         {
307             BMCWEB_LOG_DEBUG("{} <path>", spaces);
308             debugNodePrint(nodes[n.pathParamChild], level + 6);
309         }
310         for (const Node::ChildMap::value_type& kv : n.children)
311         {
312             BMCWEB_LOG_DEBUG("{}{}", spaces, kv.first);
313             debugNodePrint(nodes[kv.second], level + kv.first.size());
314         }
315     }
316 
317   public:
debugPrint()318     void debugPrint()
319     {
320         debugNodePrint(head(), 0U);
321     }
322 
323   private:
head() const324     const Node& head() const
325     {
326         return nodes.front();
327     }
328 
head()329     Node& head()
330     {
331         return nodes.front();
332     }
333 
newNode()334     unsigned newNode()
335     {
336         nodes.resize(nodes.size() + 1);
337         return static_cast<unsigned>(nodes.size() - 1);
338     }
339 
340     std::vector<Node> nodes;
341 };
342 
343 class Router
344 {
345   public:
346     Router() = default;
347 
newRuleDynamic(const std::string & rule)348     DynamicRule& newRuleDynamic(const std::string& rule)
349     {
350         std::unique_ptr<DynamicRule> ruleObject =
351             std::make_unique<DynamicRule>(rule);
352         DynamicRule* ptr = ruleObject.get();
353         allRules.emplace_back(std::move(ruleObject));
354 
355         return *ptr;
356     }
357 
358     template <uint64_t NumArgs>
newRuleTagged(const std::string & rule)359     auto& newRuleTagged(const std::string& rule)
360     {
361         if constexpr (NumArgs == 0)
362         {
363             using RuleT = TaggedRule<>;
364             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
365             RuleT* ptr = ruleObject.get();
366             allRules.emplace_back(std::move(ruleObject));
367             return *ptr;
368         }
369         else if constexpr (NumArgs == 1)
370         {
371             using RuleT = TaggedRule<std::string>;
372             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
373             RuleT* ptr = ruleObject.get();
374             allRules.emplace_back(std::move(ruleObject));
375             return *ptr;
376         }
377         else if constexpr (NumArgs == 2)
378         {
379             using RuleT = TaggedRule<std::string, std::string>;
380             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
381             RuleT* ptr = ruleObject.get();
382             allRules.emplace_back(std::move(ruleObject));
383             return *ptr;
384         }
385         else if constexpr (NumArgs == 3)
386         {
387             using RuleT = TaggedRule<std::string, std::string, std::string>;
388             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
389             RuleT* ptr = ruleObject.get();
390             allRules.emplace_back(std::move(ruleObject));
391             return *ptr;
392         }
393         else if constexpr (NumArgs == 4)
394         {
395             using RuleT =
396                 TaggedRule<std::string, std::string, std::string, std::string>;
397             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
398             RuleT* ptr = ruleObject.get();
399             allRules.emplace_back(std::move(ruleObject));
400             return *ptr;
401         }
402         else
403         {
404             using RuleT = TaggedRule<std::string, std::string, std::string,
405                                      std::string, std::string>;
406             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
407             RuleT* ptr = ruleObject.get();
408             allRules.emplace_back(std::move(ruleObject));
409             return *ptr;
410         }
411         static_assert(NumArgs <= 5, "Max number of args supported is 5");
412     }
413 
414     struct PerMethod
415     {
416         std::vector<BaseRule*> rules;
417         Trie trie;
418         // rule index 0 has special meaning; preallocate it to avoid
419         // duplication.
PerMethodcrow::Router::PerMethod420         PerMethod() : rules(1) {}
421 
internalAddcrow::Router::PerMethod422         void internalAdd(std::string_view rule, BaseRule* ruleObject)
423         {
424             rules.emplace_back(ruleObject);
425             trie.add(rule, static_cast<unsigned>(rules.size() - 1U));
426             // directory case:
427             //   request to `/about' url matches `/about/' rule
428             if (rule.size() > 2 && rule.back() == '/')
429             {
430                 trie.add(rule.substr(0, rule.size() - 1),
431                          static_cast<unsigned>(rules.size() - 1));
432             }
433         }
434     };
435 
internalAddRuleObject(const std::string & rule,BaseRule * ruleObject)436     void internalAddRuleObject(const std::string& rule, BaseRule* ruleObject)
437     {
438         if (ruleObject == nullptr)
439         {
440             return;
441         }
442         for (size_t method = 0; method <= maxVerbIndex; method++)
443         {
444             size_t methodBit = 1 << method;
445             if ((ruleObject->methodsBitfield & methodBit) > 0U)
446             {
447                 perMethods[method].internalAdd(rule, ruleObject);
448             }
449         }
450 
451         if (ruleObject->isNotFound)
452         {
453             notFoundRoutes.internalAdd(rule, ruleObject);
454         }
455 
456         if (ruleObject->isMethodNotAllowed)
457         {
458             methodNotAllowedRoutes.internalAdd(rule, ruleObject);
459         }
460 
461         if (ruleObject->isUpgrade)
462         {
463             upgradeRoutes.internalAdd(rule, ruleObject);
464         }
465     }
466 
validate()467     void validate()
468     {
469         for (std::unique_ptr<BaseRule>& rule : allRules)
470         {
471             if (rule)
472             {
473                 std::unique_ptr<BaseRule> upgraded = rule->upgrade();
474                 if (upgraded)
475                 {
476                     rule = std::move(upgraded);
477                 }
478                 rule->validate();
479                 internalAddRuleObject(rule->rule, rule.get());
480             }
481         }
482         for (PerMethod& perMethod : perMethods)
483         {
484             perMethod.trie.validate();
485         }
486     }
487 
488     struct FindRoute
489     {
490         BaseRule* rule = nullptr;
491         std::vector<std::string> params;
492     };
493 
494     struct FindRouteResponse
495     {
496         std::string allowHeader;
497         FindRoute route;
498     };
499 
findRouteByPerMethod(std::string_view url,const PerMethod & perMethod)500     static FindRoute findRouteByPerMethod(std::string_view url,
501                                           const PerMethod& perMethod)
502     {
503         FindRoute route;
504 
505         Trie::FindResult found = perMethod.trie.find(url);
506         if (found.ruleIndex >= perMethod.rules.size())
507         {
508             throw std::runtime_error("Trie internal structure corrupted!");
509         }
510         // Found a 404 route, switch that in
511         if (found.ruleIndex != 0U)
512         {
513             route.rule = perMethod.rules[found.ruleIndex];
514             route.params = std::move(found.params);
515         }
516         return route;
517     }
518 
findRoute(const Request & req) const519     FindRouteResponse findRoute(const Request& req) const
520     {
521         FindRouteResponse findRoute;
522 
523         // Check to see if this url exists at any verb
524         for (size_t perMethodIndex = 0; perMethodIndex <= maxVerbIndex;
525              perMethodIndex++)
526         {
527             // Make sure it's safe to deference the array at that index
528             static_assert(
529                 maxVerbIndex < std::tuple_size_v<decltype(perMethods)>);
530             FindRoute route = findRouteByPerMethod(req.url().encoded_path(),
531                                                    perMethods[perMethodIndex]);
532             if (route.rule == nullptr)
533             {
534                 continue;
535             }
536             if (!findRoute.allowHeader.empty())
537             {
538                 findRoute.allowHeader += ", ";
539             }
540             HttpVerb thisVerb = static_cast<HttpVerb>(perMethodIndex);
541             findRoute.allowHeader += httpVerbToString(thisVerb);
542         }
543 
544         std::optional<HttpVerb> verb = httpVerbFromBoost(req.method());
545         if (!verb)
546         {
547             return findRoute;
548         }
549         size_t reqMethodIndex = static_cast<size_t>(*verb);
550         if (reqMethodIndex >= perMethods.size())
551         {
552             return findRoute;
553         }
554 
555         FindRoute route = findRouteByPerMethod(req.url().encoded_path(),
556                                                perMethods[reqMethodIndex]);
557         if (route.rule != nullptr)
558         {
559             findRoute.route = route;
560         }
561 
562         return findRoute;
563     }
564 
565     template <typename Adaptor>
handleUpgrade(const std::shared_ptr<Request> & req,const std::shared_ptr<bmcweb::AsyncResp> & asyncResp,Adaptor && adaptor)566     void handleUpgrade(const std::shared_ptr<Request>& req,
567                        const std::shared_ptr<bmcweb::AsyncResp>& asyncResp,
568                        Adaptor&& adaptor)
569     {
570         PerMethod& perMethod = upgradeRoutes;
571         Trie& trie = perMethod.trie;
572         std::vector<BaseRule*>& rules = perMethod.rules;
573 
574         Trie::FindResult found = trie.find(req->url().encoded_path());
575         unsigned ruleIndex = found.ruleIndex;
576         if (ruleIndex == 0U)
577         {
578             BMCWEB_LOG_DEBUG("Cannot match rules {}",
579                              req->url().encoded_path());
580             asyncResp->res.result(boost::beast::http::status::not_found);
581             return;
582         }
583 
584         if (ruleIndex >= rules.size())
585         {
586             throw std::runtime_error("Trie internal structure corrupted!");
587         }
588 
589         BaseRule& rule = *rules[ruleIndex];
590 
591         BMCWEB_LOG_DEBUG("Matched rule (upgrade) '{}'", rule.rule);
592 
593         // TODO(ed) This should be able to use std::bind_front, but it doesn't
594         // appear to work with the std::move on adaptor.
595         validatePrivilege(
596             req, asyncResp, rule,
597             [req, &rule, asyncResp,
598              adaptor = std::forward<Adaptor>(adaptor)]() mutable {
599                 rule.handleUpgrade(*req, asyncResp, std::move(adaptor));
600             });
601     }
602 
handle(const std::shared_ptr<Request> & req,const std::shared_ptr<bmcweb::AsyncResp> & asyncResp)603     void handle(const std::shared_ptr<Request>& req,
604                 const std::shared_ptr<bmcweb::AsyncResp>& asyncResp)
605     {
606         FindRouteResponse foundRoute = findRoute(*req);
607 
608         if (foundRoute.route.rule == nullptr)
609         {
610             // Couldn't find a normal route with any verb, try looking for a 404
611             // route
612             if (foundRoute.allowHeader.empty())
613             {
614                 foundRoute.route = findRouteByPerMethod(
615                     req->url().encoded_path(), notFoundRoutes);
616             }
617             else
618             {
619                 // See if we have a method not allowed (405) handler
620                 foundRoute.route = findRouteByPerMethod(
621                     req->url().encoded_path(), methodNotAllowedRoutes);
622             }
623         }
624 
625         // Fill in the allow header if it's valid
626         if (!foundRoute.allowHeader.empty())
627         {
628             asyncResp->res.addHeader(boost::beast::http::field::allow,
629                                      foundRoute.allowHeader);
630         }
631 
632         // If we couldn't find a real route or a 404 route, return a generic
633         // response
634         if (foundRoute.route.rule == nullptr)
635         {
636             if (foundRoute.allowHeader.empty())
637             {
638                 asyncResp->res.result(boost::beast::http::status::not_found);
639             }
640             else
641             {
642                 asyncResp->res.result(
643                     boost::beast::http::status::method_not_allowed);
644             }
645             return;
646         }
647 
648         BaseRule& rule = *foundRoute.route.rule;
649         std::vector<std::string> params = std::move(foundRoute.route.params);
650 
651         BMCWEB_LOG_DEBUG("Matched rule '{}' {} / {}", rule.rule,
652                          req->methodString(), rule.getMethods());
653 
654         if (req->session == nullptr)
655         {
656             rule.handle(*req, asyncResp, params);
657             return;
658         }
659         validatePrivilege(
660             req, asyncResp, rule,
661             [req, asyncResp, &rule, params = std::move(params)]() {
662                 rule.handle(*req, asyncResp, params);
663             });
664     }
665 
debugPrint()666     void debugPrint()
667     {
668         for (size_t i = 0; i < perMethods.size(); i++)
669         {
670             BMCWEB_LOG_DEBUG("{}", httpVerbToString(static_cast<HttpVerb>(i)));
671             perMethods[i].trie.debugPrint();
672         }
673     }
674 
getRoutes(const std::string & parent)675     std::vector<const std::string*> getRoutes(const std::string& parent)
676     {
677         std::vector<const std::string*> ret;
678 
679         for (const PerMethod& pm : perMethods)
680         {
681             std::vector<unsigned> x;
682             pm.trie.findRouteIndexes(parent, x);
683             for (unsigned index : x)
684             {
685                 ret.push_back(&pm.rules[index]->rule);
686             }
687         }
688         return ret;
689     }
690 
691   private:
692     std::array<PerMethod, static_cast<size_t>(HttpVerb::Max)> perMethods;
693 
694     PerMethod notFoundRoutes;
695     PerMethod upgradeRoutes;
696     PerMethod methodNotAllowedRoutes;
697 
698     std::vector<std::unique_ptr<BaseRule>> allRules;
699 };
700 } // namespace crow
701