path: root/contrib/libs/hyperscan/src/som/slot_manager.cpp

/*
 * Copyright (c) 2015-2017, Intel Corporation
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *  * Neither the name of Intel Corporation nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 * \brief SOM Slot Manager.
 */

#include "slot_manager.h"

#include "slot_manager_internal.h"
#include "ue2common.h"
#include "nfagraph/ng_holder.h"
#include "nfagraph/ng_is_equal.h"
#include "nfagraph/ng_som_util.h"
#include "nfagraph/ng_region.h"
#include "util/charreach.h"
#include "util/hash.h"
#include "util/make_unique.h"
#include "util/dump_charclass.h"
#include "util/verify_types.h"

#include <cassert>
#include <deque>
#include <utility>

using namespace std;

namespace ue2 {

/** \brief Define this to disable the cache and have everyone get their own
 * SOM slot. */
//#define NO_SLOT_CACHING

SlotCacheEntry::SlotCacheEntry(const NGHolder &prefix_in,
                               const CharReach &escapes_in, u32 parent_in,
                               bool is_reset_in, u32 slot_in)
    : prefix(cloneHolder(prefix_in)), escapes(escapes_in),
      parent_slot(parent_in), is_reset(is_reset_in), slot(slot_in) {}

size_t SlotEntryHasher::operator()(const SlotCacheEntry &e) const {
    assert(e.prefix);

    size_t v = hash_all(hash_holder(*e.prefix), e.parent_slot,
                        e.is_reset, e.escapes);

    DEBUG_PRINTF("%zu vertices, parent_slot=%u, escapes=%s, is_reset=%d "
                 "hashes to %zx\n", num_vertices(*e.prefix), e.parent_slot,
                 describeClass(e.escapes, 10, CC_OUT_TEXT).c_str(),
                 (int)e.is_reset, v);
    return v;
}

bool SlotEntryEqual::operator()(const SlotCacheEntry &a,
                                const SlotCacheEntry &b) const {
    assert(a.prefix);
    assert(b.prefix);
    return a.parent_slot == b.parent_slot
        && a.is_reset == b.is_reset
        && a.escapes == b.escapes
        && is_equal(*a.prefix, *b.prefix);
    // NOTE: slot not compared.
}

void SlotCache::insert(const NGHolder &prefix, const CharReach &escapes,
                       u32 parent_slot, bool is_reset, u32 slot) {
    store.emplace(prefix, escapes, parent_slot, is_reset, slot);
}

const SlotCacheEntry *SlotCache::find(const NGHolder &prefix,
                                      const CharReach &escapes, u32 parent_slot,
                                      bool is_reset) {
    SlotCacheEntry entry(prefix, escapes, parent_slot, is_reset,
                         0 /* unused for searching with SlotEntryEqual */);
    CacheStore::const_iterator it = store.find(entry);
    if (it != store.end()) {
        return &(*it);
    }
    return nullptr;
}

SomSlotManager::SomSlotManager(u8 p)
    : nextSomSlot(0), cache(ue2::make_unique<SlotCache>()), historyRequired(0),
      precision(p) {}

SomSlotManager::~SomSlotManager() { }

u32 SomSlotManager::getSomSlot(const NGHolder &prefix,
                               const CharReach &escapes, bool is_reset,
                               u32 parent_slot) {
    assert(parent_slot == NO_PARENT || parent_slot < nextSomSlot);

    DEBUG_PRINTF("prefix with %zu vertices, parent_slot=%u\n",
                 num_vertices(prefix), parent_slot);
    DEBUG_PRINTF("nextSomSlot=%u\n", nextSomSlot);

#ifdef NO_SLOT_CACHING
    return nextSomSlot++;
#endif

    const SlotCacheEntry *entry =
        cache->find(prefix, escapes, parent_slot, is_reset);
    if (entry) {
        DEBUG_PRINTF("cache hit: slot %u\n", entry->slot);
        return entry->slot;
    }

    DEBUG_PRINTF("cache miss: handing out new slot %u\n", nextSomSlot);
    cache->insert(prefix, escapes, parent_slot, is_reset, nextSomSlot);
    return nextSomSlot++;
}

u32 SomSlotManager::getInitialResetSomSlot(const NGHolder &prefix,
                const NGHolder &g,
                const unordered_map<NFAVertex, u32> &region_map,
                u32 last_sent_region, bool *prefix_already_implemented) {
    DEBUG_PRINTF("getting initial reset; last sent region %u\n",
                 last_sent_region);
    assert(last_sent_region);
    assert(!hasBigCycles(prefix));
    *prefix_already_implemented = false;

#ifdef NO_SLOT_CACHING
    return nextSomSlot++;
#endif

    shared_ptr<const NGHolder> pp = cloneHolder(prefix);
    assert(hash_holder(*pp) == hash_holder(prefix));

    auto hs_it = cache->initial_prefixes.find(pp);
    if (hs_it != cache->initial_prefixes.end()) {
        DEBUG_PRINTF("pulling from cache\n");
        pp = *hs_it;
    } else {
        DEBUG_PRINTF("storing in cache entry %zu, hash=%llu\n",
                     cache->initial_prefixes.size(), hash_holder(*pp));
        cache->initial_prefixes.insert(pp);
    }

    // Clone a copy of g (and its region map) that we will be able to store
    // later on.
    shared_ptr<NGHolder> gg = make_shared<NGHolder>();
    unordered_map<NFAVertex, NFAVertex> orig_to_copy;
    cloneHolder(*gg, g, &orig_to_copy);
    unordered_map<NFAVertex, u32> gg_region_map;
    for (const auto &m : region_map) {
        assert(contains(region_map, m.first));
        gg_region_map.emplace(orig_to_copy.at(m.first), m.second);
    }

    u32 first_bad_region = ~0U;
    UNUSED bool rv = sentClearsTail(g, region_map, *pp, last_sent_region,
                                    &first_bad_region);
    assert(!rv || first_bad_region == ~0U);

    InitialResetInfo *ir = nullptr;

    for (auto &reset : cache->initial_resets) {
        /* is this prefix already in our list? */
        auto has_prefix_func =
            [&pp](const InitialResetEntry &e) { return e.sent == pp; };
        bool already_seen_prefix =
            find_if(reset.entries.begin(), reset.entries.end(),
                    has_prefix_func) != reset.entries.end();

        for (auto &e : reset.entries) {
            u32 temp = 0;
            /* we don't need to test against sentinels which are identical to
             * our current one as races don't matter and we know it clears
             * sufficiently. */
            if (e.sent != pp &&
                !sentClearsTail(g, region_map, *e.sent, last_sent_region - 1,
                                &temp) &&
                (temp < first_bad_region || first_bad_region == ~0U)) {
                goto try_next;
            }

            /* if we have already seen the prefix it must be fine */
            if (!already_seen_prefix &&
                !sentClearsTail(*e.body, e.body_regions, prefix,
                                e.sent_region - 1, &temp) &&
                (temp < e.first_bad_region || e.first_bad_region == ~0U)) {
                goto try_next;
            }
        }
        DEBUG_PRINTF("sharing\n");
        if (already_seen_prefix) {
            /* if we have already created this prefix using this som slot, we
             * can avoid creating another copy of the prefix. */
            *prefix_already_implemented = true;
        }
        ir = &reset;
        goto found;
    try_next:;
    }

    cache->initial_resets.emplace_back(nextSomSlot++);
    ir = &cache->initial_resets.back();

found:
    ir->entries.emplace_back(pp, gg, gg_region_map, last_sent_region,
                             first_bad_region);
    return ir->slot;
}

u32 SomSlotManager::getPrivateSomSlot(void) {
    return nextSomSlot++;
}

void SomSlotManager::rollbackSomTo(u32 num) {
    assert(nextSomSlot >= num);
    nextSomSlot = num;
}

u32 SomSlotManager::numSomSlots() const {
    return nextSomSlot;
}

u32 SomSlotManager::addRevNfa(bytecode_ptr<NFA> nfa, u32 maxWidth) {
    u32 rv = verify_u32(rev_nfas.size());
    rev_nfas.push_back(move(nfa));

    // A rev nfa commits us to having enough history around to handle its
    // max width.
    historyRequired = max(historyRequired, maxWidth);

    return rv;
}

} // namespace ue2