From cc0aeb97972ed2c8d5810845416eb697493726c6 Mon Sep 17 00:00:00 2001 From: Adrian Szyndela Date: Wed, 29 May 2019 16:17:49 +0200 Subject: [PATCH] internal: add send index This adds indexes: - main index for send rules; - additional index for send prefix rules; - indexes for send rules for each user; - additional indexes for send prefix rules for each user. Change-Id: I45a4b3625fe67a9fff7525d04ae6ebf8879e14f1 --- src/internal/policy.hpp | 2 + src/internal/storage_backend_serialized.cpp | 158 ++++++++++++++++++++++++---- 2 files changed, 142 insertions(+), 18 deletions(-) diff --git a/src/internal/policy.hpp b/src/internal/policy.hpp index 9f1575e..71fd8ae 100644 --- a/src/internal/policy.hpp +++ b/src/internal/policy.hpp @@ -167,6 +167,8 @@ namespace ldp_xml_parser const boost::string_ref &_name, bool _is_name_prefix, Decision decision) const; + + const KdbusBusNames &getNames() const { return names; } }; class MatchItemSend : public MatchItemSR { diff --git a/src/internal/storage_backend_serialized.cpp b/src/internal/storage_backend_serialized.cpp index d9439ce..ef0855b 100644 --- a/src/internal/storage_backend_serialized.cpp +++ b/src/internal/storage_backend_serialized.cpp @@ -23,12 +23,14 @@ #include #include #include +#include #include #include #include #include using namespace FB; +using ldp_xml_parser::MatchItemSend; namespace ldp_serialized { @@ -36,6 +38,8 @@ namespace ldp_serialized { // 1MB. Adjustable #define MAX_SFILE_SIZE (1024 * 1024) +typedef boost::tokenizer> tokenizer; + template struct type_helper; @@ -50,18 +54,136 @@ class StorageBackendSerialized::StorageBackendSerializedImpl { void releaseMMap(); void releaseFD(); + typedef std::pair ItemWithScore; // a pair: Item, index of Item + typedef std::vector ItemsWithScore; // items + typedef std::pair HighestScoreWithItems; // value for index map: highest index for items, items + typedef std::map MapIndex; + typedef std::vector SendPrefixIndex; + + MapIndex sendIndex; // context default + SendPrefixIndex sendPrefixIndex; // context default prefix rules + std::map userSendIndex; + std::map userSendPrefixIndex; + public: bool init(const char *filename, bool verify); bool init(const FB::File *f); bool initFromXML(const char *config_name); void release(); + void createSendIndex(); + ldp_xml_parser::DecisionItem getDecisionFromSendIndex(const MatchItemSend &item, const MapIndex &index, const SendPrefixIndex &prefixIndex); + ldp_xml_parser::DecisionItem getDecisionFromSendIndex(const MatchItemSend &item); + ldp_xml_parser::DecisionItem getDecisionFromSendIndex(const MatchItemSend &item, uid_t uid); + void printContent() const; template ::policy_set_type> const M *getPolicySet(); }; +inline boost::string_ref s(const flatbuffers::String *str) { + return boost::string_ref(str->c_str(), str->size()); +} + +template +bool match(const T &match, const I *i) { + return match.match(makeMessageType(i->type()), + s(i->interface()), + s(i->path()), + s(i->member()), + s(i->name()), + i->is_name_prefix(), + makeDecision(i->decision()->decision())); +} + +ldp_xml_parser::DecisionItem StorageBackendSerialized::StorageBackendSerializedImpl::getDecisionFromSendIndex(const MatchItemSend &item, + const MapIndex &index, const SendPrefixIndex &prefixIndex) { + ldp_xml_parser::DecisionItem decision(ldp_xml_parser::Decision::ANY); + + ItemWithScore currentBest(nullptr, 0); + + auto updateCurrentBest = [¤tBest, &item, &index](boost::string_ref name) { + // check if there are any rules for the name + auto fit = index.find(name); + if (fit == index.end()) + return; + + // check if there's any chance to get better score + // fit->second.first is the highest score from vector fit->second.second + if (fit->second.first <= currentBest.second) + return; + + // look for better score + for (const auto &it: fit->second.second) { + if (it.second > currentBest.second && match(item, it.first)) + currentBest = it; + } + }; + + // iterate over names + for (const auto &name: item.getNames()) { + // find and check the no-prefix rules + updateCurrentBest(name); + + // check the prefix rules + for (const auto &prefixItem: prefixIndex) { + if (prefixItem.second > currentBest.second && match(item, prefixItem.first)) + currentBest = prefixItem; + } + } + + // check no-name rules + updateCurrentBest(""); + + if (currentBest.first) + decision = makeDecisionItem(currentBest.first->decision()); + + return decision; +} + +ldp_xml_parser::DecisionItem StorageBackendSerialized::StorageBackendSerializedImpl::getDecisionFromSendIndex(const MatchItemSend &item) { + return getDecisionFromSendIndex(item, sendIndex, sendPrefixIndex); +} + +ldp_xml_parser::DecisionItem StorageBackendSerialized::StorageBackendSerializedImpl::getDecisionFromSendIndex(const MatchItemSend &item, uid_t uid) { + return getDecisionFromSendIndex(item, userSendIndex[uid], userSendPrefixIndex[uid]); +} + +void StorageBackendSerialized::StorageBackendSerializedImpl::createSendIndex() { + // helper for adding items to indexes + auto add = [](MapIndex &index, SendPrefixIndex &prefixIndex, boost::string_ref key, ItemWithScore value) { + if (value.first->is_name_prefix()) { + prefixIndex.push_back(value); + } else { + index[key].second.push_back(value); + // we insert items in increasing score order, so we just update the highest score on each add + index[key].first = value.second; + } + }; + + // context default index + const auto *policy = file->m_send_set()->context_default(); + unsigned cnt = 1; + + const auto *v = policy->items(); + for (auto it = v->begin(); it != v->end(); ++it) + add(sendIndex, sendPrefixIndex, + boost::string_ref(it->name()->c_str(), it->name()->size()), + ItemWithScore(*it, cnt++)); + + // users index + for (const auto &uidPolicy: *file->m_send_set()->user()) { + cnt = 1; + for (const auto it: *uidPolicy->policy()->items()) { + add(userSendIndex[uidPolicy->id()], + userSendPrefixIndex[uidPolicy->id()], + boost::string_ref(it->name()->c_str(), it->name()->size()), + ItemWithScore(it, cnt++)); + } + } +} + void StorageBackendSerialized::StorageBackendSerializedImpl::releaseMMap() { assert(MAP_FAILED != mem); assert(0 != length); @@ -138,13 +260,17 @@ bool StorageBackendSerialized::StorageBackendSerializedImpl::init(const char *fi mmapGuard.dismiss(); file = GetFile(mem); - return file != nullptr; + bool res = file != nullptr; + if (res) + createSendIndex(); + return res; } bool StorageBackendSerialized::StorageBackendSerializedImpl::init(const FB::File *f) { assert(nullptr == file); file = f; + createSendIndex(); return true; } @@ -206,21 +332,6 @@ void StorageBackendSerialized::printContent() const { pimpl->printContent(); } -inline boost::string_ref s(const flatbuffers::String *str) { - return boost::string_ref(str->c_str(), str->size()); -} - -template -bool match(const T &match, const I *i) { - return match.match(makeMessageType(i->type()), - s(i->interface()), - s(i->path()), - s(i->member()), - s(i->name()), - i->is_name_prefix(), - makeDecision(i->decision()->decision())); -} - template <> bool match(const ldp_xml_parser::MatchItemAccess &match, const FB::ItemAccess *item) { return match.match(makeBusAccessType(item->type()), item->uid(), item->gid()); } @@ -235,8 +346,6 @@ ldp_xml_parser::DecisionItem getDecisionItem(const T &item, const P *policy) { return ldp_xml_parser::Decision::ANY; } -typedef boost::tokenizer> tokenizer; - const DecisionItem *getDecisionItemFromTree(const FB::PolicyOwnNode *node, tokenizer &tokens, tokenizer::iterator &iterator) { @@ -288,6 +397,19 @@ ldp_xml_parser::DecisionItem StorageBackendSerialized::getDecisionItemContextMan return getDecisionItem(item, pimpl->getPolicySet()->context_mandatory()); } +template <> +ldp_xml_parser::DecisionItem StorageBackendSerialized::getDecisionItemContextDefault(const MatchItemSend &item) const { + return pimpl->getDecisionFromSendIndex(item); +} + +template <> +ldp_xml_parser::DecisionItem StorageBackendSerialized::getDecisionItemUser(uid_t uid, const MatchItemSend &item) const { + auto *policyPair = pimpl->getPolicySet()->user()->LookupByKey(uid); + if (nullptr == policyPair) + return ldp_xml_parser::Decision::ANY; + return pimpl->getDecisionFromSendIndex(item, uid); +} + template ldp_xml_parser::DecisionItem StorageBackendSerialized::getDecisionItemContextDefault(const T &item) const { return getDecisionItem(item, pimpl->getPolicySet()->context_default()); -- 2.7.4