redfish_authorization/redfish_entity_trie.cc

#include "redfish_entity_trie.h"

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <limits>
#include <memory>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

#include "absl/container/flat_hash_set.h"
#include "absl/log/log.h"
#include "absl/status/status.h"
#include "absl/status/statusor.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_split.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 {

using ::milotic::authz::internal::RedfishEntityTrieNode;
using ::milotic::authz::internal::RedfishSubtreePrivilegesTrieNode;

namespace {

// When authorizing we can ignore URI fragments. Authorizing /uri#fragment is
// the same as authorizing /uri
std::string_view IgnoreFragment(std::string_view uri) {
  return uri.substr(0, uri.find('#'));
}

bool ValidUri(std::string_view uri) {
  return !uri.empty() && uri.front() == '/';
}

absl::StatusOr<std::vector<std::string>> SplitUri(std::string_view uri) {
  if (!ValidUri(uri)) {
    return absl::InvalidArgumentError(absl::StrCat("Invalid URI: ", uri));
  }

  // Depending on if uri ends with /, then the last element of uri_split could
  // be empty
  std::vector<std::string> uri_split = absl::StrSplit(IgnoreFragment(uri), '/');

  if (!uri_split.empty() && uri_split.back().empty()) {
    uri_split.pop_back();
  }

  return uri_split;
}

}  // namespace

RedfishEntityTrie::RedfishEntityTrie()
    : entity_trie_root_(std::make_unique<RedfishEntityTrieNode>()),
      subtree_privileges_trie_root_(
          std::make_unique<RedfishSubtreePrivilegesTrieNode>()) {}

void RedfishEntityTrie::InsertUri(std::string_view uri,
                                  ecclesia::ResourceEntity entity_tag,
                                  std::size_t node_index_in_pattern_array) {
  absl::StatusOr<std::vector<std::string>> uri_split = SplitUri(uri);
  if (!uri_split.ok()) {
    return;
  }

  RedfishEntityTrieNode* cur = entity_trie_root_.get();

  // Every URI starts with a / so the first element is always empty
  for (size_t i = 1; i < uri_split->size(); ++i) {
    RedfishEntityTrieNode* child = cur->GetOrDefaultChild((*uri_split)[i]);

    // If the child is a wildcard path, set cur to IsCollection
    // Collection must be set after because collection is checked in
    // GetOrDefaultChild
    cur->SetCollection((*uri_split)[i].front() == '{');

    cur = child;
  }
  cur->SetEntityTag(entity_tag);
  cur->SetNodeIndexInPatternArray(node_index_in_pattern_array);
}

const RedfishEntityTrieNode* RedfishEntityTrie::GetTrieNode(
    std::string_view uri) const {
  absl::StatusOr<std::vector<std::string>> uri_split = SplitUri(uri);
  if (!uri_split.ok()) {
    return nullptr;
  }
  const RedfishEntityTrieNode* cur = entity_trie_root_.get();

  for (size_t i = 1; i < uri_split->size(); ++i) {
    const RedfishEntityTrieNode* child = cur->GetChild((*uri_split)[i]);

    if (child == nullptr) {
      return nullptr;
    }

    cur = child;
  }
  return cur;
}

ecclesia::ResourceEntity RedfishEntityTrie::GetEntityType(
    std::string_view uri) const {
  const RedfishEntityTrieNode* cur = GetTrieNode(uri);
  if (cur == nullptr) {
    return ecclesia::ResourceEntity::kUndefined;
  }
  return cur->GetEntityTag();
}

std::size_t RedfishEntityTrie::GetNodeIndexInPatternArray(
    std::string_view uri) const {
  const RedfishEntityTrieNode* cur = GetTrieNode(uri);
  if (cur == nullptr) {
    return std::numeric_limits<std::size_t>::max();
  }
  return cur->GetNodeIndexInPatternArray();
}

absl::Status RedfishEntityTrie::AddSubtreeMapping(
    SubtreePrivilegeMapping&& subtree_privilege_mapping) {
  absl::StatusOr<std::vector<std::string>> uri_split =
      SplitUri(subtree_privilege_mapping.url);
  if (!uri_split.ok()) {
    return uri_split.status();
  }

  RedfishSubtreePrivilegesTrieNode* cur = subtree_privileges_trie_root_.get();

  // Every URI starts with a / so the first element is always empty
  for (size_t i = 1; i < uri_split->size(); ++i) {
    RedfishSubtreePrivilegesTrieNode* child =
        cur->GetOrDefaultChild((*uri_split)[i]);
    if (child->ContainsPrivilegeForSubtree(
            subtree_privilege_mapping.operation,
            subtree_privilege_mapping.privileges)) {
      return absl::AlreadyExistsError(absl::Substitute(
          "URI: $0 already exists in the trie", subtree_privilege_mapping.url));
    }
    cur = child;
  }
  cur->AddPrivilegeForSubtree(subtree_privilege_mapping.operation,
                              std::move(subtree_privilege_mapping.privileges));

  return absl::OkStatus();
}

void RedfishEntityTrie::ReplaceSubtreePrivilegeMappings(
    std::vector<SubtreePrivilegeMapping>&& subtree_privilege_mappings) {
  // Sort based on strings as order of addition of subtree mappings into the
  // trie matters.
  // TODO: Lazy propagation can be done to eliminate the need for this sort
  std::sort(subtree_privilege_mappings.begin(),
            subtree_privilege_mappings.end());

  absl::MutexLock lock(&subtree_privileges_mutex_);

  // Clear the subtree_privileges trie
  subtree_privileges_trie_root_->Clear();

  for (auto& mapping : subtree_privilege_mappings) {
    // Have to get mapping string first before moving struct.
    std::string mapping_string = mapping.ToString();
    absl::Status status = AddSubtreeMapping(std::move(mapping));
    // Log all failures but continue to add mappings
    if (!status.ok()) {
      LOG(ERROR) << mapping_string << " was not added due to error: " << status;
    }
  }
}

absl::flat_hash_set<RedfishPrivileges>
RedfishEntityTrie::GetAdditionalSubtreePrivileges(
    std::string_view uri, const ecclesia::Operation& operation) const {
  absl::flat_hash_set<RedfishPrivileges> privileges_list;
  absl::StatusOr<std::vector<std::string>> uri_split = SplitUri(uri);
  if (!uri_split.ok()) {
    return privileges_list;
  }

  absl::MutexLock lock(&subtree_privileges_mutex_);
  RedfishSubtreePrivilegesTrieNode* cur = subtree_privileges_trie_root_.get();

  // increment cur_uri_len to incorporate the / per for loop iteration
  for (size_t i = 1; i < uri_split->size(); ++i) {
    RedfishSubtreePrivilegesTrieNode* child = cur->GetChild((*uri_split)[i]);

    // If the URI does not exist in the trie, return current privileges we
    // have gotten
    if (child == nullptr) {
      return privileges_list;
    }

    std::vector<RedfishPrivileges> privileges_for_subtree =
        child->GetPrivilegesForSubtree(operation);

    privileges_list.insert(
        std::make_move_iterator(privileges_for_subtree.begin()),
        std::make_move_iterator(privileges_for_subtree.end()));

    cur = child;
  }

  return privileges_list;
}

}  // namespace milotic::authz