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