suricata
util-mpm-ac-ks.c File Reference
#include "suricata-common.h"
#include "suricata.h"
#include "detect.h"
#include "detect-parse.h"
#include "detect-engine.h"
#include "conf.h"
#include "util-debug.h"
#include "util-unittest.h"
#include "util-unittest-helper.h"
#include "util-memcmp.h"
#include "util-memcpy.h"
#include "util-mpm-ac-ks.h"
#include "util-mpm-ac-ks-small.c"
Include dependency graph for util-mpm-ac-ks.c:

Go to the source code of this file.

Data Structures

struct  StateQueue_
 Helper structure used by AC during state table creation. More...
 

Macros

#define SC_AC_TILE_FAIL   (-1)
 
#define STATE_QUEUE_CONTAINER_SIZE   65536
 
#define SCHECK(x)   ((x) > 0)
 
#define BUF_TYPE   int32_t
 
#define BYTE0(x)   (((x) & 0x000000ff) >> 0)
 
#define BYTE1(x)   (((x) & 0x0000ff00) >> 8)
 
#define BYTE2(x)   (((x) & 0x00ff0000) >> 16)
 
#define BYTE3(x)   (((x) & 0xff000000) >> 24)
 
#define EXTRA   4
 
#define SINDEX_INTERNAL(y, x, log_mult, width)   ((1<<log_mult) * (x & ((1<<width) - 1)))
 
#define STYPE   int16_t
 
#define SLOAD(x)   *(STYPE * restrict)(x)
 
#define FUNC_NAME   SCACTileSearchSmall256
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 8, 15)
 
#define FUNC_NAME   SCACTileSearchSmall128
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 7, 15)
 
#define FUNC_NAME   SCACTileSearchSmall64
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 6, 15)
 
#define FUNC_NAME   SCACTileSearchSmall32
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 5, 15)
 
#define FUNC_NAME   SCACTileSearchSmall16
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 4, 15)
 
#define FUNC_NAME   SCACTileSearchSmall8
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 3, 15)
 
#define STYPE   int8_t
 
#define FUNC_NAME   SCACTileSearchTiny256
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 8, 7)
 
#define FUNC_NAME   SCACTileSearchTiny128
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 7, 7)
 
#define FUNC_NAME   SCACTileSearchTiny64
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 6, 7)
 
#define FUNC_NAME   SCACTileSearchTiny32
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 5, 7)
 
#define FUNC_NAME   SCACTileSearchTiny16
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 4, 7)
 
#define FUNC_NAME   SCACTileSearchTiny8
 
#define SINDEX(y, x)   SINDEX_INTERNAL(y, x, 3, 7)
 

Typedefs

typedef struct StateQueue_ StateQueue
 Helper structure used by AC during state table creation. More...
 

Functions

void SCACTileInitCtx (MpmCtx *mpm_ctx)
 Initialize the AC context. More...
 
void SCACTileInitThreadCtx (MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
 Init the mpm thread context. More...
 
void SCACTileDestroyCtx (MpmCtx *mpm_ctx)
 Destroy the mpm context. More...
 
void SCACTileDestroyThreadCtx (MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
 Destroy the mpm thread context. More...
 
int SCACTileAddPatternCI (MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
 Add a case insensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case. More...
 
int SCACTileAddPatternCS (MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
 Add a case sensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case. More...
 
int SCACTilePreparePatterns (MpmCtx *mpm_ctx)
 Process the patterns added to the mpm, and create the internal tables. More...
 
uint32_t SCACTileSearch (const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 The aho corasick search function. More...
 
void SCACTilePrintInfo (MpmCtx *mpm_ctx)
 
void SCACTilePrintSearchStats (MpmThreadCtx *mpm_thread_ctx)
 
void SCACTileRegisterTests (void)
 
uint32_t SCACTileSearchLarge (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchSmall256 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchSmall128 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchSmall64 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchSmall32 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchSmall16 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchSmall8 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchTiny256 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchTiny128 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchTiny64 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchTiny32 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchTiny16 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
uint32_t SCACTileSearchTiny8 (const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 
void MpmACTileRegister (void)
 Register the aho-corasick mpm 'ks' originally developed by Ken Steele for Tilera Tile-Gx processor. More...
 

Detailed Description

Author
Ken Steele suric.nosp@m.ata@.nosp@m.tiler.nosp@m.a.co.nosp@m.m
Anoop Saldanha anoop.nosp@m.sald.nosp@m.anha@.nosp@m.gmai.nosp@m.l.com
    Aho-corasick MPM optimized for the Tilera Tile-Gx architecture.

    Efficient String Matching: An Aid to Bibliographic Search
    Alfred V. Aho and Margaret J. Corasick

    - Started with util-mpm-ac.c:
        - Uses the delta table for calculating transitions,
          instead of having separate goto and failure
          transitions.
        - If we cross 2 ** 16 states, we use 4 bytes in the
          transition table to hold each state, otherwise we use
          2 bytes.
        - This version of the MPM is heavy on memory, but it
          performs well.  If you can fit the ruleset with this
          mpm on your box without hitting swap, this is the MPM
          to go for.

    - Added these optimizations:
        - Compress the input alphabet from 256 characters down
          to the actual characters used in the patterns, plus
          one character for all the unused characters.
        - Reduce the size of the delta table so that each state
          is the smallest power of two that is larger than the
          size of the compressed alphabet.
        - Specialized the search function based on state count
          (small for 8-bit large for 16-bit) and the size of
          the alphabet, so that it is constant inside the
          function for better optimization.
Todo:
  • Do a proper analyis of our existing MPMs and suggest a good one based on the pattern distribution and the expected traffic(say http).
  - Irrespective of whether we cross 2 ** 16 states or
    not,shift to using uint32_t for state type, so that we can
    integrate it's status as a final state or not in the
    topmost byte.  We are already doing it if state_count is >
    2 ** 16.
  - Test case-senstive patterns if they have any ascii chars.
    If they don't treat them as nocase.
  - Reorder the compressed alphabet to put the most common characters
    first.

Definition in file util-mpm-ac-ks.c.

Macro Definition Documentation

#define BUF_TYPE   int32_t

Definition at line 1161 of file util-mpm-ac-ks.c.

#define BYTE0 (   x)    (((x) & 0x000000ff) >> 0)

Definition at line 1163 of file util-mpm-ac-ks.c.

#define BYTE1 (   x)    (((x) & 0x0000ff00) >> 8)

Definition at line 1164 of file util-mpm-ac-ks.c.

#define BYTE2 (   x)    (((x) & 0x00ff0000) >> 16)

Definition at line 1165 of file util-mpm-ac-ks.c.

#define BYTE3 (   x)    (((x) & 0xff000000) >> 24)

Definition at line 1166 of file util-mpm-ac-ks.c.

#define EXTRA   4

Definition at line 1167 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchSmall256

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchSmall128

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchSmall64

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchSmall32

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchSmall16

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchSmall8

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchTiny256

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchTiny128

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchTiny64

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchTiny32

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchTiny16

Definition at line 1374 of file util-mpm-ac-ks.c.

#define FUNC_NAME   SCACTileSearchTiny8

Definition at line 1374 of file util-mpm-ac-ks.c.

#define SC_AC_TILE_FAIL   (-1)

Definition at line 147 of file util-mpm-ac-ks.c.

#define SCHECK (   x)    ((x) > 0)

Definition at line 1160 of file util-mpm-ac-ks.c.

Referenced by SCACTileSearchLarge().

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 8, 15)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 7, 15)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 6, 15)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 5, 15)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 4, 15)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 3, 15)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 8, 7)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 7, 7)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 6, 7)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 5, 7)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 4, 7)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX (   y,
 
)    SINDEX_INTERNAL(y, x, 3, 7)

Definition at line 1376 of file util-mpm-ac-ks.c.

#define SINDEX_INTERNAL (   y,
  x,
  log_mult,
  width 
)    ((1<<log_mult) * (x & ((1<<width) - 1)))

Definition at line 1273 of file util-mpm-ac-ks.c.

#define SLOAD (   x)    *(STYPE * restrict)(x)

Definition at line 1278 of file util-mpm-ac-ks.c.

#define STATE_QUEUE_CONTAINER_SIZE   65536

Definition at line 149 of file util-mpm-ac-ks.c.

#define STYPE   int16_t

Definition at line 1330 of file util-mpm-ac-ks.c.

#define STYPE   int8_t

Definition at line 1330 of file util-mpm-ac-ks.c.

Typedef Documentation

typedef struct StateQueue_ StateQueue

Helper structure used by AC during state table creation.

Function Documentation

int SCACTileAddPatternCI ( MpmCtx mpm_ctx,
uint8_t *  pat,
uint16_t  patlen,
uint16_t  offset,
uint16_t  depth,
uint32_t  pid,
SigIntId  sid,
uint8_t  flags 
)

Add a case insensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case.

Parameters
mpm_ctxPointer to the mpm context.
patThe pattern to add.
patnenThe pattern length.
offsetIgnored.
depthIgnored.
pidThe pattern id.
sidIgnored.
flagsFlags associated with this pattern.
Return values
0On success.
-1On failure.

Definition at line 1397 of file util-mpm-ac-ks.c.

References MPM_PATTERN_FLAG_NOCASE, and MpmAddPattern().

Referenced by MpmACTileRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

int SCACTileAddPatternCS ( MpmCtx mpm_ctx,
uint8_t *  pat,
uint16_t  patlen,
uint16_t  offset,
uint16_t  depth,
uint32_t  pid,
SigIntId  sid,
uint8_t  flags 
)

Add a case sensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case.

Parameters
mpm_ctxPointer to the mpm context.
patThe pattern to add.
patnenThe pattern length.
offsetIgnored.
depthIgnored.
pidThe pattern id.
sidIgnored.
flagsFlags associated with this pattern.
Return values
0On success.
-1On failure.

Definition at line 1423 of file util-mpm-ac-ks.c.

References MpmAddPattern().

Referenced by MpmACTileRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCACTileDestroyCtx ( MpmCtx mpm_ctx)
void SCACTileDestroyThreadCtx ( MpmCtx mpm_ctx,
MpmThreadCtx mpm_thread_ctx 
)
void SCACTileInitCtx ( MpmCtx mpm_ctx)

Initialize the AC context.

Parameters
mpm_ctxMpm context.

Definition at line 996 of file util-mpm-ac-ks.c.

References MpmCtx_::ctx, SCACTileSearchCtx_::init_ctx, MpmCtx_::init_hash, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, and SCMalloc.

Referenced by MpmACTileRegister().

Here is the caller graph for this function:

void SCACTileInitThreadCtx ( MpmCtx mpm_ctx,
MpmThreadCtx mpm_thread_ctx 
)

Init the mpm thread context.

Parameters
mpm_ctxPointer to the mpm context.
mpm_thread_ctxPointer to the mpm thread context.

Definition at line 978 of file util-mpm-ac-ks.c.

References MpmThreadCtx_::ctx, MpmThreadCtx_::memory_cnt, MpmThreadCtx_::memory_size, and SCMalloc.

Referenced by MpmACTileRegister().

Here is the caller graph for this function:

void SCACTilePrintInfo ( MpmCtx mpm_ctx)
void SCACTilePrintSearchStats ( MpmThreadCtx mpm_thread_ctx)

Definition at line 1431 of file util-mpm-ac-ks.c.

References MpmThreadCtx_::ctx, SCACTileThreadCtx_::total_calls, and SCACTileThreadCtx_::total_matches.

Referenced by MpmACTileRegister(), and SCACTileDestroyThreadCtx().

Here is the caller graph for this function:

void SCACTileRegisterTests ( void  )

Definition at line 2512 of file util-mpm-ac-ks.c.

References MpmACTileRegister(), and UtRegisterTest().

Referenced by MpmACTileRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t SCACTileSearch ( const MpmCtx mpm_ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)

The aho corasick search function.

Parameters
mpm_ctxPointer to the mpm context.
mpm_thread_ctxPointer to the mpm thread context.
pmqPointer to the Pattern Matcher Queue to hold search matches.
bufBuffer to be searched.
buflenBuffer length.
Return values
matchesMatch count.

Definition at line 1232 of file util-mpm-ac-ks.c.

References MpmCtx_::ctx, and SCACTileSearchCtx_::Search.

Referenced by MpmACTileRegister().

Here is the caller graph for this function:

uint32_t SCACTileSearchLarge ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchSmall128 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchSmall16 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchSmall256 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchSmall32 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchSmall64 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchSmall8 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchTiny128 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchTiny16 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchTiny256 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchTiny32 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchTiny64 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)
uint32_t SCACTileSearchTiny8 ( const SCACTileSearchCtx ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)