支持多线程AC自动机

/* ** ** $Id$ ** ** Multi-Pattern Search Engine ** ** Aho-Corasick State Machine - uses a Deterministic Finite Automata - DFA ** ** Copyright (C) 2002 Sourcefire,Inc. ** Marc Norton ** ** ** This program is free software; you can redistribute it and/or modify ** it under the terms of the GNU General Public License as published by ** the Free Software Foundation; either version 2 of the License, or ** (at your option) any later version. ** ** This program is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** GNU General Public License for more details. ** ** You should have received a copy of the GNU General Public License ** along with this program; if not, write to the Free Software ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ** ** ** Reference - Efficient String matching: An Aid to Bibliographic Search ** Alfred V Aho and Margaret J Corasick ** Bell Labratories ** Copyright(C) 1975 Association for Computing Machinery,Inc ** ** Implemented from the 4 algorithms in the paper by Aho & Corasick ** and some implementation ideas from 'Practical Algorithms in C' ** ** Notes: ** 1) This version uses about 1024 bytes per pattern character - heavy on the memory. ** 2) This algorithm finds all occurrences of all patterns within a ** body of text. ** 3) Support is included to handle upper and lower case matching. ** 4) Some comopilers optimize the search routine well, others don't, this makes all the difference. ** 5) Aho inspects all bytes of the search text, but only once so it's very efficient, ** if the patterns are all large than the Modified Wu-Manbar method is often faster. ** 6) I don't subscribe to any one method is best for all searching needs, ** the data decides which method is best, ** and we don't know until after the search method has been tested on the specific data sets. ** ** ** May 2002 : Marc Norton 1st Version ** June 2002 : Modified interface for SNORT, added case support ** Aug 2002 : Cleaned up comments, and removed dead code. ** Nov 2,2002: Fixed queue_init() , added count=0 ** ** */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <pthread.h> #include "acsmx.h" #define MEMASSERT(p,s) if(!p){fprintf(stderr,"ACSM-No Memory: %s!\n",s);exit(0);} #ifdef DEBUG_AC static int max_memory = 0; #endif /*static void Print_DFA( ACSM_STRUCT * acsm );*/ /* * */ static void * AC_MALLOC (int n) { void *p; p = malloc (n); #ifdef DEBUG_AC if (p) max_memory += n; #endif return p; } /* * */ static void AC_FREE (void *p) { if (p) free (p); } /* * Simple QUEUE NODE */ typedef struct _qnode { int state; struct _qnode *next; } QNODE; /* * Simple QUEUE Structure */ typedef struct _queue { QNODE * head, *tail; int count; } QUEUE; /* * */ static void queue_init (QUEUE * s) { s->head = s->tail = 0; s->count = 0; } /* * Add Tail Item to queue */ static void queue_add (QUEUE * s, int state) { QNODE * q; if (!s->head) { q = s->tail = s->head = (QNODE *) AC_MALLOC (sizeof (QNODE)); MEMASSERT (q, "queue_add"); q->state = state; q->next = 0; } else { q = (QNODE *) AC_MALLOC (sizeof (QNODE)); MEMASSERT (q, "queue_add"); q->state = state; q->next = 0; s->tail->next = q; s->tail = q; } s->count++; } /* * Remove Head Item from queue */ static int queue_remove (QUEUE * s) { int state = 0; QNODE * q; if (s->head) { q = s->head; state = q->state; s->head = s->head->next; s->count--; if (!s->head) { s->tail = 0; s->count = 0; } AC_FREE (q); } return state; } /* * */ static int queue_count (QUEUE * s) { return s->count; } /* * */ static void queue_free (QUEUE * s) { while (queue_count (s)) { queue_remove (s); } } /* ** Case Translation Table */ static unsigned char xlatcase[256]; /* * */ static void init_xlatcase () { int i; for (i = 0; i < 256; i++) { xlatcase[i] = toupper (i); } } /* * */ static inline void ConvertCase (unsigned char *s, int m) { int i; for (i = 0; i < m; i++) { s[i] = xlatcase[s[i]]; } } /* * */ static inline void ConvertCaseEx (unsigned char *d, unsigned char *s, int m) { int i; for (i = 0; i < m; i++) { d[i] = xlatcase[s[i]]; } } /* * */ static ACSM_PATTERN * CopyMatchListEntry (ACSM_PATTERN * px) { ACSM_PATTERN * p; p = (ACSM_PATTERN *) AC_MALLOC (sizeof (ACSM_PATTERN)); MEMASSERT (p, "CopyMatchListEntry"); memcpy (p, px, sizeof (ACSM_PATTERN)); p->next = 0; return p; } /* * Add a pattern to the list of patterns terminated at this state. * Insert at front of list. */ static void AddMatchListEntry (ACSM_STRUCT * acsm, int state, ACSM_PATTERN * px) { ACSM_PATTERN * p; p = (ACSM_PATTERN *) AC_MALLOC (sizeof (ACSM_PATTERN)); MEMASSERT (p, "AddMatchListEntry"); memcpy (p, px, sizeof (ACSM_PATTERN)); p->next = acsm->acsmStateTable[state].MatchList; acsm->acsmStateTable[state].MatchList = p; } /* Add Pattern States */ static void AddPatternStates (ACSM_STRUCT * acsm, ACSM_PATTERN * p) { unsigned char *pattern; int state=0, next, n; n = p->n; pattern = p->patrn; /* * Match up pattern with existing states */ for (; n > 0; pattern++, n--) { next = acsm->acsmStateTable[state].NextState[*pattern]; if (next == ACSM_FAIL_STATE) break; state = next; } /* * Add new states for the rest of the pattern bytes, 1 state per byte */ for (; n > 0; pattern++, n--) { acsm->acsmNumStates++; acsm->acsmStateTable[state].NextState[*pattern] = acsm->acsmNumStates; state = acsm->acsmNumStates; } AddMatchListEntry (acsm, state, p); } /* * Build Non-Deterministic Finite Automata */ static void Build_NFA (ACSM_STRUCT * acsm) { int r, s; int i; QUEUE q, *queue = &q; ACSM_PATTERN * mlist=0; ACSM_PATTERN * px=0; /* Init a Queue */ queue_init (queue); /* Add the state 0 transitions 1st */ for (i = 0; i < ALPHABET_SIZE; i++) { s = acsm->acsmStateTable[0].NextState[i]; if (s) { queue_add (queue, s); acsm->acsmStateTable[s].FailState = 0; } } /* Build the fail state transitions for each valid state */ while (queue_count (queue) > 0) { r = queue_remove (queue); /* Find Final States for any Failure */ for (i = 0; i < ALPHABET_SIZE; i++) { int fs, next; if ((s = acsm->acsmStateTable[r].NextState[i]) != ACSM_FAIL_STATE) { queue_add (queue, s); fs = acsm->acsmStateTable[r].FailState; /* * Locate the next valid state for 'i' starting at s */ while ((next=acsm->acsmStateTable[fs].NextState[i]) == ACSM_FAIL_STATE) { fs = acsm->acsmStateTable[fs].FailState; } /* * Update 's' state failure state to point to the next valid state */ acsm->acsmStateTable[s].FailState = next; /* * Copy 'next'states MatchList to 's' states MatchList, * we copy them so each list can be AC_FREE'd later, * else we could just manipulate pointers to fake the copy. */ for (mlist = acsm->acsmStateTable[next].MatchList; mlist != NULL ; mlist = mlist->next) { px = CopyMatchListEntry (mlist); if( !px ) { printf("*** Out of memory Initializing Aho Corasick in acsmx.c ****"); } /* Insert at front of MatchList */ px->next = acsm->acsmStateTable[s].MatchList; acsm->acsmStateTable[s].MatchList = px; } } } } /* Clean up the q