redfish_authorization/redfish_entity_trie.h

#ifndef THIRD_PARTY_MILOTIC_EXTERNAL_CC_AUTHZ_REDFISH_ENTITY_TRIE_H_
#define THIRD_PARTY_MILOTIC_EXTERNAL_CC_AUTHZ_REDFISH_ENTITY_TRIE_H_

#include <cstddef>
#include <memory>
#include <string>
#include <string_view>
#include <vector>

#include "absl/base/thread_annotations.h"
#include "absl/container/flat_hash_set.h"
#include "absl/status/status.h"
#include "absl/strings/substitute.h"
#include "absl/synchronization/mutex.h"
#include "authorizer_enums.h"
#include "redfish_entity_trie_node.h"
#include "redfish_privileges.h"
#include "redfish_subtree_privileges_trie_node.h"

namespace milotic::authz {

/*
Redfish Entity Trie intended to be used as a method to obtain an entity type
when given a redfish path regardless of if wildcards are inputted.

Sample usage:

"I know that /redfish/v1/Chassis/{ChassisId} has an entity type Chassis from the
schema". This can be entered using
trie.InsertUri("/redfish/v1/Chassis/{ChassisId}", "Chassis");

"I want to figure out the entity type for /redfish/v1/Chassis/test"
This can be found by
trie.GetEntityType("/redfish/v1/Chassis/test") -> "Chassis"

Another usage of this trie is to obtain all the privileges that is able to
access this URI via subtree mapping.

"I want privilege 'ChassisXOwner' to be able to access every URI with prefix
'/redfish/v1/Chassis/ChassisX'"

This can be entered using
trie.SetSubtreePrivilegeMappings({{"/redfish/v1/Chassis/ChassisX",
"ChassisXOwner"}});

"I want to see what additional OEM privileges can access
'/redfish/v1/Chassis/ChassisX/Sensors/sensorY"

This can be found by
trie.GetAdditionalSubtreePrivileges("/redfish/v1/Chassis/ChassisX/Sensors/sensorY");


ReplaceSubtreeMappings is done instead of exposing AddSubtreeMapping to public
and allowing modification after initialization to subtree privileges due to
duplication issues that can occur. If we had exposed AddSubtreeMapping to
public, then there are orders in which duplications can occur in subtrees that
make it hard for deduplication to occur.

AddPrivilegeForSubtree("/redfish/v1", "SubtreePrivileges1");
AddPrivilegeForSubtree("/redfish/v1/Chassis", "SubtreePrivileges1");

When performing the queries above, the second AddPrivilege doesn't mean
anything, so we ignore the second command as we see a duplicate when traversing
down the trie.

However if we perform

AddPrivilegeForSubtree("/redfish/v1/Chassis", "SubtreePrivileges1");
AddPrivilegeForSubtree("/redfish/v1", "SubtreePrivileges1");

Then, it is impossible to tell without iterating through the rest of the trie
that a duplication exists. The current workaround is to sort it first so we can
always find the duplicates, but an alternative that was deemed to complex for
the first iteration is lazy propagation.


NOTE: This class is only partially thread safe. Please check the method's
documentation to see if that method is thread safe or not
*/

// Struct to hold information regarding individual subtree privilege mapping
struct SubtreePrivilegeMapping {
  std::string url;
  ecclesia::Operation operation;
  RedfishPrivileges privileges;

  bool operator<(const SubtreePrivilegeMapping& other) const {
    return url < other.url;
  }

  std::string ToString() const {
    return absl::Substitute("URL: $0, Operation: $1 has privileges: $2", url,
                            ::ecclesia::OperationToString(operation),
                            privileges.GetDebugString());
  }
};

class RedfishEntityTrie {
 public:
  RedfishEntityTrie();

  // Inserts a URI into the entity trie. NOT THREAD SAFE.
  void InsertUri(std::string_view uri, ecclesia::ResourceEntity entity_tag,
                 std::size_t node_index_in_pattern_array);

  // Supports normal and fragmented URIs.
  // THREAD SAFE IF InsertUri IS NOT CALLED IN PARALLEL
  // TODO (edwarddl): Support ignoring query parameters
  ecclesia::ResourceEntity GetEntityType(std::string_view uri) const;

  // THREAD SAFE after all InsertUri is done.
  // Returns the index of the node in the pattern array. If the URI is not
  // found, returns std::numeric_limits<std::size_t>::max()
  std::size_t GetNodeIndexInPatternArray(std::string_view uri) const;

  // Replace subtree mappings for trie. This will clear the current mappings and
  // replace them with what is passed into the method. THREAD SAFE
  // TODO: Consider removing this if we ever decide to implement lazy
  // propagation
  void ReplaceSubtreePrivilegeMappings(
      std::vector<SubtreePrivilegeMapping>&& subtree_privilege_mappings);

  // Get privileges that can access to uri via additional subtree mappings
  // THREAD SAFE
  absl::flat_hash_set<RedfishPrivileges> GetAdditionalSubtreePrivileges(
      std::string_view uri, const ecclesia::Operation& operation) const;

 private:
  const internal::RedfishEntityTrieNode* GetTrieNode(
      std::string_view uri) const;
  // We only support setting and removing subtree mappings. We don't support
  // individual additions.
  absl::Status AddSubtreeMapping(
      SubtreePrivilegeMapping&& subtree_privilege_mapping)
      ABSL_SHARED_LOCKS_REQUIRED(subtree_privileges_mutex_);

  mutable absl::Mutex subtree_privileges_mutex_;
  std::unique_ptr<internal::RedfishEntityTrieNode> entity_trie_root_;

  std::unique_ptr<internal::RedfishSubtreePrivilegesTrieNode>
      subtree_privileges_trie_root_ ABSL_GUARDED_BY(subtree_privileges_mutex_);
};
}  // namespace milotic::authz

#endif  // THIRD_PARTY_MILOTIC_EXTERNAL_CC_AUTHZ_REDFISH_ENTITY_TRIE_H_