/*

Copyright (c) 2007 Carl Byington - 510 Software Group, released under
the GPL version 3 or any later version at your choice available at
http://www.gnu.org/licenses/gpl-3.0.txt

*/

#include "includes.h"
#include <fcntl.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <limits.h>
#include <set>
#include <vector>
#include <map>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>

char *token_announce;
char *token_file;
char *token_include;
char *token_index_ip;
char *token_index_length;
char *token_index_path;
char *token_index_value;
char *token_ip;
char *token_lbrace;
char *token_path;
char *token_rbrace;
char *token_reset;
char *token_semi;
char *token_slash;
char *token_withdraw;

const int   training           = 100;   // need 100 hours uptime before using the statistics
const float origin_threshold   = 2.9;   // a bit less than 1 + decay + decay^2
const float adjacent_threshold = 2.9;   // ""
const float decay              = 0.99;  // hourly exponential decay
const float threshold          = 0.01;  // when counts have decayed below threshold, discard the item
const int   ancient_smtp       = 3*3600;// suspicious smtp connections over 3 hours old are ignored

string_set  all_strings;        // owns all the strings, only modified by the config loader thread
const int maxlen = 1000;        // used for snprintf buffers
typedef pair<int,int>           adjacent;
typedef vector<int>             aspath;
typedef map<int,float>          o_history;  // as origin history
typedef map<adjacent,float>     a_history;  // as adjacency history
typedef set<adjacent>           a_set;      // set of current adjacency pairs
typedef map<uint32_t,time_t>    m_connect;  // smtp connections

class route_prefix {
    uint32_t    prefix_value;
    bool        announced;
    bool        trusted;    // cannot be suspicious
    aspath      path;
    o_history   origin_history;
    m_connect   smtp_connections;
public:
    route_prefix(uint32_t value);
    void add_route(aspath path_, a_history &adj_history);
    void remove_route(int prefix_length);
    uint32_t prefix() const         { return prefix_value;                         };
    bool active()          const    { return announced;                            };
    adjacent aspair(int i) const    { return adjacent(path[i], path[i+1]);         };
    bool selfpair(int i)   const    { return (path[1] == path[i+1]);               };
    bool empty()           const    { return !announced && origin_history.empty(); };
    void update_history(a_set &adj_set);
    suspicion suspicious(a_history &adj_history, bool debug = false, int prefix_length = 0, uint32_t ip = 0);
    void record_smtp(uint32_t ip);
    string name(int length) const;
};

struct ltrouteprefix {
    bool operator()(const route_prefix* r1, const route_prefix* r2) const {
        return r1->prefix() < r2->prefix();
    }
};

typedef set<route_prefix*, ltrouteprefix> route_prefixes;

class RIB {
    pthread_mutex_t rib_mutex;
    int             uptime;
    bool            stable;
    route_prefixes  prefixes[33];   // /0 to /32
    a_history       history;
    aspath          path;
public:
    RIB();
    void set_path(aspath path_) {path = path_;};
    void add_route(int prefix_length, uint32_t prefix_value);
    void remove_route(int prefix_length, uint32_t prefix_value);
    void update_history();
    suspicion suspicious(route_prefix *r, bool debug = false, int prefix_length = 0, uint32_t ip = 0);
    suspicion suspicious(uint32_t ip);
    void clear();
    void reset();
};


RIB route_base;

const uint32_t masks[33] = {
                       0x00000000,
                       0x80000000,
                       0xc0000000,
                       0xe0000000,
                       0xf0000000,
                       0xf8000000,
                       0xfc000000,
                       0xfe000000,
                       0xff000000,
                       0xff800000,
                       0xffc00000,
                       0xffe00000,
                       0xfff00000,
                       0xfff80000,
                       0xfffc0000,
                       0xfffe0000,
                       0xffff0000,
                       0xffff8000,
                       0xffffc000,
                       0xffffe000,
                       0xfffff000,
                       0xfffff800,
                       0xfffffc00,
                       0xfffffe00,
                       0xffffff00,
                       0xffffff80,
                       0xffffffc0,
                       0xffffffe0,
                       0xfffffff0,
                       0xfffffff8,
                       0xfffffffc,
                       0xfffffffe,
                       0xffffffff};


////////////////////////////////////////////////
//
char *suspicious_name(suspicion s)
{
    char *ss = "";
    switch (s) {
        case suspicious_none:      ss = "none";      break;
        case suspicious_origin:    ss = "origin";    break;
        case suspicious_adjacency: ss = "adjacency"; break;
        default: break;
    }
    return ss;
}


////////////////////////////////////////////////
//
route_prefix::route_prefix(uint32_t value)
{
    prefix_value = value;
    announced    = false;
    trusted      = false;
}


void route_prefix::add_route(aspath path_, a_history &adj_history)
{
    suspicion s = suspicious(adj_history);
    int oldorig = path.empty()  ? 0 : path [path.size()  - 1];
    int neworig = path_.empty() ? 0 : path_[path_.size() - 1];
    trusted   = announced && (s == suspicious_none) && (oldorig == neworig);
    announced = true;
    path      = path_;
}


void route_prefix::remove_route(int prefix_length)
{
    if (announced) {
        for (m_connect::iterator i = smtp_connections.begin(); i != smtp_connections.end(); i++) {
            const uint32_t &ip = (*i).first;
            time_t   &t  = (*i).second;
            uint32_t nip = htonl(ip);
            char buf[maxlen];
            char adr[sizeof "255.255.255.255   "];
            adr[0] = '\0';
            inet_ntop(AF_INET, (const u_char *)&nip, adr, sizeof(adr));
            char ctbuf[maxlen];
            ctime_r(&t, ctbuf);
            int ii = strlen(ctbuf);
            if (ii > 1) ctbuf[ii-1] = '\0';   // remove trailing newline
            snprintf(buf, sizeof(buf), "*** smtp connection at %s from %s via prefix %s/%d being removed", ctbuf, adr, name(prefix_length).c_str(), prefix_length);
            my_syslog(buf);
        }
    }
    announced = false;
    smtp_connections.clear();
}


void route_prefix::update_history(a_set &adj_set)
{
    // decay origin history
    for (o_history::iterator i = origin_history.begin(); i != origin_history.end(); i++) {
        float &count = (*i).second;
        count *= decay;
    }
    if (announced) {
        // remove old suspicious smtp connections
        time_t cutoff = time(NULL) - ancient_smtp;
        for (m_connect::iterator i = smtp_connections.begin(); i != smtp_connections.end(); ) {
            time_t   &t  = (*i).second;
            if (t > cutoff) i++;
            else            smtp_connections.erase(i++);
        }

        // update origin history
        int n = path.size() - 1;
        int origin = path[n];
        o_history::iterator j = origin_history.find(origin);
        if (j == origin_history.end()) {
            origin_history[origin] = 1.0;
        }
        else {
            float &count = (*j).second;
            count++;
        }
        // update current adjacency set
        for (int k=0; k<n; k++) {
            if (!selfpair(k)) adj_set.insert(aspair(k));
        }
    }

    // remove origin history entries below the threshold
    for (o_history::iterator i = origin_history.begin(); i != origin_history.end();) {
        float &count = (*i).second;
        if (count > threshold) i++;
        else origin_history.erase(i++);
    }
}


suspicion route_prefix::suspicious(a_history &adj_history, bool debug, int prefix_length, uint32_t ip)
{
    if (!announced || trusted) return suspicious_none;
    debug &= (debug_syslog > 2);

    // check origin stability
    int n = path.size() - 1;
    int origin = path[n];
    o_history::const_iterator o = origin_history.find(origin);
    if (o == origin_history.end()) {
        if (debug) {
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "debug suspicious origin %d missing count %s",
                                        origin, name(prefix_length).c_str());
            my_syslog(buf);
        }
        record_smtp(ip);
        return suspicious_origin;
    }
    const float &count = (*o).second;
    if (count < origin_threshold) {
        if (debug) {
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "debug suspicious origin %d count %5.2f vs %5.2f %s",
                                        origin, count, origin_threshold, name(prefix_length).c_str());
            my_syslog(buf);
        }
        record_smtp(ip);
        return suspicious_origin;
    }

    // check as adjacency stability
    for (int k=0; k<n; k++) {
        if (!selfpair(k)) {
            adjacent aa = aspair(k);
            a_history::iterator a = adj_history.find(aa);
            if (a == adj_history.end()) {
                if (debug) {
                    char buf[maxlen];
                    snprintf(buf, sizeof(buf), "debug suspicious adjacency (%d,%d) missing count %s",
                                                aa.first, aa.second, name(prefix_length).c_str());
                    my_syslog(buf);
                }
                record_smtp(ip);
                return suspicious_adjacency;
            }
            float &count = (*a).second;
            if (count < adjacent_threshold) {
                if (debug) {
                    char buf[maxlen];
                    snprintf(buf, sizeof(buf), "debug suspicious adjacency (%d,%d) count %5.2f vs %5.2f %s",
                                                aa.first, aa.second, count, adjacent_threshold, name(prefix_length).c_str());
                    my_syslog(buf);
                }
                record_smtp(ip);
                return suspicious_adjacency;
            }
        }
    }
    return suspicious_none;
}


void route_prefix::record_smtp(uint32_t ip)
{
    if (ip) smtp_connections[ip] = time(NULL);
}


string route_prefix::name(int length) const
{
    char buf[maxlen];
    char adr[sizeof "255.255.255.255   "];
    adr[0] = '\0';
    uint32_t nip = htonl(prefix_value);
    inet_ntop(AF_INET, (const u_char *)&nip, adr, sizeof(adr));
    snprintf(buf, sizeof(buf), "%s/%d", adr, length);
    int n = path.size();
    for (int i=0; i<n; i++) {
        snprintf(adr, sizeof(adr), " %d", path[i]);
        strncat(buf, adr, max(0, maxlen-1-(int)strlen(adr)));
    }
    return string(buf);
}


////////////////////////////////////////////////
//

RIB::RIB()
{
    pthread_mutex_init(&rib_mutex, 0);
    uptime = 0;
    stable = false;
}


void RIB::add_route(int prefix_length, uint32_t prefix_value)
{
    if (prefix_length < 0) return;
    if (prefix_length > 32) return;
    pthread_mutex_lock(&rib_mutex);
        prefix_value &= masks[prefix_length];
        route_prefix rr(prefix_value);
        route_prefixes &p = prefixes[prefix_length];
        route_prefixes::iterator i = p.find(&rr);
        route_prefix *r = NULL;
        if (i == p.end()) {
            // new prefix
            r = new route_prefix(prefix_value);
            p.insert(r);
        }
        else {
            // existing prefix
            r = *i;
        }
        r->add_route(path, history);
        suspicion s;
        if (debug_syslog > 2) s = suspicious(r);
        if ((debug_syslog > 2) && (s != suspicious_none) && (prefix_length < 22)) {
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "add suspicious %s route %s", suspicious_name(s), r->name(prefix_length).c_str());
            my_syslog(buf);
        }
        else if (debug_syslog > 3) {
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "add route %s", r->name(prefix_length).c_str());
            my_syslog(buf);
        }
    pthread_mutex_unlock(&rib_mutex);
}


void RIB::remove_route(int prefix_length, uint32_t prefix_value)
{
    if (prefix_length < 0) return;
    if (prefix_length > 32) return;
    pthread_mutex_lock(&rib_mutex);
        uint32_t mask = masks[prefix_length];
        prefix_value &= mask;
        route_prefix r(prefix_value);
        route_prefixes &p = prefixes[prefix_length];
        route_prefixes::iterator i = p.find(&r);
        if (i != p.end()) {
            // existing prefix
            route_prefix* r = *i;
            if (debug_syslog > 3) {
                char buf[maxlen];
                snprintf(buf, sizeof(buf), "remove route %s", r->name(prefix_length).c_str());
                my_syslog(buf);
            }
            r->remove_route(prefix_length);
            if (r->empty()) {
                p.erase(r);
                delete r;
            };
        }
    pthread_mutex_unlock(&rib_mutex);
}


void RIB::update_history()
{
    pthread_mutex_lock(&rib_mutex);
        a_set adj_set;
        uptime++;
        stable = (uptime > training);
        int total    = 0;
        int inactive = 0;
        int suspic   = 0;
        for (int i=0; i<=32; i++) {
            bool debug = true;  // show first suspicious prefix
            route_prefixes &p = prefixes[i];
            for (route_prefixes::iterator j = p.begin(); j != p.end();) {
                route_prefix *r = *j;
                r->update_history(adj_set);
                total++;
                if (r->active()) {
                    if (suspicious(r, debug, i) != suspicious_none) {
                        suspic++;
                        debug = false;
                    }
                }
                else {
                    inactive++;
                }
                if (r->empty()) {
                    p.erase(j++);
                    delete r;
                }
                else j++;
            }
        }
        if (debug_syslog > 2) {
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "total %d inactive %d suspicious %d", total, inactive, suspic);
            my_syslog(buf);
        }
        // decay adjacency history
        for (a_history::iterator i = history.begin(); i != history.end(); i++) {
            float &count = (*i).second;
            count *= decay;
        }
        // update adjacency history from the current adjacency set
        for (a_set::iterator i = adj_set.begin(); i != adj_set.end(); i++) {
            a_history::iterator a = history.find(*i);
            if (a == history.end()) {
                // new adjacency
                history[*i] = 1.0;
            }
            else {
                float &count = (*a).second;
                count++;
            }
        }
        // remove adjacency history entries below the threshold
        for (a_history::iterator i = history.begin(); i != history.end();) {
            float &count = (*i).second;
            if (count > threshold) i++;
            else history.erase(i++);
        }
    pthread_mutex_unlock(&rib_mutex);
}


suspicion RIB::suspicious(route_prefix *r, bool debug, int prefix_length, uint32_t ip)
{
    if (!stable) return suspicious_none;
    if (!r) return suspicious_none;
    return r->suspicious(history, debug, prefix_length, ip);
}


suspicion RIB::suspicious(uint32_t ip)
{
    if (!stable) return suspicious_none;
    suspicion rc = suspicious_none;
    route_prefix *r1 = NULL;
    int pl;
    pthread_mutex_lock(&rib_mutex);
        for (int i=32; i>=0; i--) {
            route_prefixes &p = prefixes[i];
            uint32_t network = ip & masks[i];
            route_prefix r(network);
            route_prefixes::iterator j = p.find(&r);
            if (j != p.end()) {
                // existing prefix
                route_prefix* r = *j;
                if (r->active()) {
                    r1 = r;
                    pl = i;
                    break;
                }
            }
        }
        rc = suspicious(r1, true, pl, ip);
    pthread_mutex_unlock(&rib_mutex);
    return rc;
}


void RIB::clear()
{
    pthread_mutex_lock(&rib_mutex);
        for (int i=0; i<=32; i++) {
            route_prefixes &p = prefixes[i];
            for (route_prefixes::iterator j = p.begin(); j != p.end();) {
                route_prefix *r = *j;
                p.erase(j++);
                delete r;
            }
        }
        history.clear();
    pthread_mutex_unlock(&rib_mutex);
}


void RIB::reset()
{
    pthread_mutex_lock(&rib_mutex);
        for (int i=0; i<=32; i++) {
            route_prefixes &p = prefixes[i];
            for (route_prefixes::iterator j = p.begin(); j != p.end(); j++) {
                route_prefix *r = *j;
                r->remove_route(i);
            }
        }
    pthread_mutex_unlock(&rib_mutex);
}


////////////////////////////////////////////////
//
CONFIG::CONFIG() {
    reference_count    = 0;
    generation         = 0;
    load_time          = 0;
}


CONFIG::~CONFIG() {
    for (routeconfig_list::iterator i=routeconfigs.begin(); i!=routeconfigs.end(); i++) {
        ROUTECONFIG *c = *i;
        delete c;
    }
}


void CONFIG::dump() {
    for (routeconfig_list::iterator i=routeconfigs.begin(); i!=routeconfigs.end(); i++) {
        ROUTECONFIG *c = *i;
        c->dump(0);
    }
}


void CONFIG::read() {
    while (true) {
        bool have = false;
        for (routeconfig_list::iterator i=routeconfigs.begin(); i!=routeconfigs.end(); i++) {
            ROUTECONFIGP c = *i;
            have |= c->read(*this);
        }
        if (!have) break;
    }
}



////////////////////////////////////////////////
//
ROUTECONFIG::ROUTECONFIG(TOKEN &tok, char *file_name_) {
    tokp      = &tok;
    file_name = file_name_;
    open(true);
}


ROUTECONFIG::~ROUTECONFIG() {
    close();
    for (pattern_list::iterator i=patterns.begin(); i!=patterns.end(); i++) {
        PATTERN *p = *i;
        delete p;
    }
}


void ROUTECONFIG::open(bool msg) {
    fd        = ::open(file_name, O_RDONLY);
    len       = 0;
    if (fd == -1) {
        if (msg) {
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "syslog file %s not readable", file_name);
            tokp->token_error(buf);
        }
    }
    else {
        if (debug_syslog > 1) {
            snprintf(buf, sizeof(buf), "syslog file %s opened", file_name);
            my_syslog(buf);
        }
        if (msg) lseek(fd, 0, SEEK_END);
        if (fstat(fd, &openfdstat)) {
            close();
            snprintf(buf, sizeof(buf), "syslog file %s cannot stat after open", file_name);
            tokp->token_error(buf);
        }
        // specify that this fd gets closed on exec, so that selinux
        // won't complain
        int oldflags = fcntl(fd, F_GETFD, 0);
        if (oldflags >= 0) {
            fcntl(fd, F_SETFD, oldflags | FD_CLOEXEC);
        }
    }
}


bool ROUTECONFIG::read(CONFIG &con) {
    if (failed()) {
        open(false);
        if (failed()) return false;
    }
    int n = ::read(fd, buf+len, buflen-len);
    bool have = (n > 0);
    if (have) {
        len += n;
        while (true) {
            char *p = (char*)memchr(buf, '\n', len);
            if (!p) break;
            n = p-buf;
            *p = '\0';
            process(con);       // process null terminated string
            len -= n+1;
            memmove(buf, p+1, len);
        }
        // no <lf> in a full buffer
        if (len == buflen) len = 0;
    }
    else {
        // check for file close
        struct stat filenamest;
        if (0 == stat(file_name, &filenamest)) {
            if ((filenamest.st_dev != openfdstat.st_dev) ||
                (filenamest.st_ino != openfdstat.st_ino)) {
                close();
            }
        }
        else {
            // filename no longer exists
            close();
        }
    }
    return have;
}


void ROUTECONFIG::close() {
    if (debug_syslog > 1) {
        snprintf(buf, sizeof(buf), "syslog file %s closed", file_name);
        my_syslog(buf);
    }
    if (fd != -1) ::close(fd);
    fd = -1;
}


void ROUTECONFIG::add_pattern(PATTERNP pat) {
    patterns.push_back(pat);
}


void ROUTECONFIG::process(CONFIG &con) {
    int pi=0;
    for (pattern_list::iterator i=patterns.begin(); i!=patterns.end(); i++) {
        PATTERN *p = *i;
        if (p->process(buf, con, file_name, pi)) break;
        pi++;
    }
}


void ROUTECONFIG::dump(int level) {
    char indent[maxlen];
    int i = min(maxlen-1, level*4);
    memset(indent, ' ', i);
    indent[i] = '\0';
    printf("%s file \"%s\" {\n", indent, file_name);
    for (pattern_list::iterator i=patterns.begin(); i!=patterns.end(); i++) {
        PATTERN *p = *i;
        p->dump(level+1);
    }
    printf("%s }; \n", indent);
}


////////////////////////////////////////////////
//
int ip_address(char *have);
int ip_address(char *have) {
    int ipaddr = 0;
    in_addr ip;
    if (inet_aton(have, &ip)) ipaddr = ip.s_addr;
    else {
        struct hostent *host = gethostbyname(have);
        if (host && host->h_addrtype == AF_INET) memcpy(&ipaddr, host->h_addr, sizeof(ipaddr));
    }
    return ntohl(ipaddr);
}


////////////////////////////////////////////////
//

PATTERN::PATTERN(TOKEN &tok, pattern_style style_, char *pattern_, int index1_, int index2_)
{
    style   = style_;
    pattern = pattern_;
    index1  = index1_;
    index2  = index2_;
    if (pattern) {
        int rc = regcomp(&re, pattern, REG_ICASE | REG_EXTENDED);
        if (rc) {
            char bu[maxlen];
            regerror(rc, &re, bu, maxlen);
            char buf[maxlen];
            snprintf(buf, sizeof(buf), "pattern %s not valid - %s", pattern, bu);
            tok.token_error(buf);
            pattern = NULL;
        }
    }
}


PATTERN::~PATTERN() {
    regfree(&re);
}


bool PATTERN::process(char *buf, CONFIG &con, char *file_name, int pattern_index)
{
    if (pattern) {
        const int nmatch = max(index1, index2) + 1;
        regmatch_t match[nmatch];
        if (0 == regexec(&re, buf, nmatch, match, 0)) {
            int sp1 = match[index1].rm_so;
            int ep1 = match[index1].rm_eo;
            int sp2 = match[index2].rm_so;
            int ep2 = match[index2].rm_eo;
            if ((sp1 != -1) && (sp2 != -1)) {
                if (debug_syslog > 13) {
                    my_syslog(buf); // show lines with matches
                }
                buf[ep1] = '\0';
                buf[ep2] = '\0';
                uint32_t ip;
                int pl;
                suspicion s;
                switch (style) {
                    case style_reset:
                        route_base.reset();
                        break;
                    case style_path:
                        {
                            aspath path;
                            char *p = buf+sp1;
                            char *e;
                            long l;
                            while (true) {
                                l = strtol(p, &e, 10);
                                if (e == p) break;
                                p = e;
                                path.push_back((int)l);
                            }
                            route_base.set_path(path);
                        }
                        break;
                    case style_announce:
                        ip = ip_address(buf+sp1);
                        pl = atoi(buf+sp2);
                        if (ip) route_base.add_route(pl, ip);
                        break;
                    case style_withdraw:
                        ip = ip_address(buf+sp1);
                        pl = atoi(buf+sp2);
                        if (ip) route_base.remove_route(pl, ip);
                        break;
                    case style_ip:
                        ip = ip_address(buf+sp1);
                        s  = route_base.suspicious(ip);
                        if (s != suspicious_none) {
                            char adr[sizeof "255.255.255.255   "];
                            adr[0] = '\0';
                            uint32_t nip = htonl(ip);
                            inet_ntop(AF_INET, (const u_char *)&nip, adr, sizeof(adr));
                            char buf[maxlen];
                            snprintf(buf, sizeof(buf), "*** suspicious %s ip %s", suspicious_name(s), adr);
                            my_syslog(buf);
                        }
                        break;
                }
                return true;
            }
        }
    }
    return false;
}


void PATTERN::dump(int level, int index, char *token)
{
    char indent[maxlen];
    int i = min(maxlen-1, level*4);
    memset(indent, ' ', i);
    indent[i] = '\0';
    printf("%s %s %d; \n", indent, token, index);
}


void PATTERN::dump(int level)
{
    char indent[maxlen];
    int i = min(maxlen-1, level*4);
    memset(indent, ' ', i);
    indent[i] = '\0';
    switch (style) {
        case style_reset:
            printf("%s %s \"%s\" { \n", indent, token_reset, pattern);
            break;
        case style_path:
            printf("%s %s \"%s\" { \n", indent, token_path, pattern);
            dump(level+1, index1, token_index_path);
            break;
        case style_announce:
            printf("%s %s \"%s\" { \n", indent, token_announce, pattern);
            dump(level+1, index1, token_index_value);
            dump(level+1, index2, token_index_length);
            break;
        case style_withdraw:
            printf("%s %s \"%s\" { \n", indent, token_withdraw, pattern);
            dump(level+1, index1, token_index_value);
            dump(level+1, index2, token_index_length);
            break;
        case style_ip:
            printf("%s %s \"%s\" { \n", indent, token_ip, pattern);
            dump(level+1, index1, token_index_ip);
            break;
    }
    printf("%s }; \n", indent);
}


////////////////////////////////////////////////
// helper to discard the strings held by a string_set
//
void discard(string_set &s) {
    for (string_set::iterator i=s.begin(); i!=s.end(); i++) {
        free(*i);
    }
    s.clear();
}


////////////////////////////////////////////////
// helper to register a string in a string set
//
char* register_string(string_set &s, char *name) {
    string_set::iterator i = s.find(name);
    if (i != s.end()) return *i;
    char *x = strdup(name);
    s.insert(x);
    return x;
}


////////////////////////////////////////////////
// register a global string
//
char* register_string(char *name) {
    return register_string(all_strings, name);
}


////////////////////////////////////////////////
// clear all global strings, helper for valgrind checking
//
void clear_strings() {
	discard(all_strings);
}


////////////////////////////////////////////////
// clear the rib, helper for valgrind checking
//
void clear_rib() {
	route_base.clear();
}


////////////////////////////////////////////////
//
bool tsa(TOKEN &tok, char *token);
bool tsa(TOKEN &tok, char *token) {
    char *have = tok.next();
    if (have == token) return true;
    tok.token_error(token, have);
    return false;
}


////////////////////////////////////////////////
//
bool parse_path(TOKEN &tok, ROUTECONFIG &con, char *tokk, pattern_style style);
bool parse_path(TOKEN &tok, ROUTECONFIG &con, char *tokk, pattern_style style) {
    char *pattern = tok.next();
    int  index = 0;
    if (!tsa(tok, token_lbrace)) return false;
    while (true) {
        char *have = tok.next();
        if (!have) break;
        if (have == token_rbrace) break;
        if (have == tokk) {
            index = tok.nextint();
            if (!tsa(tok, token_semi)) return false;
        }
        else return false;
    }
    if (!tsa(tok, token_semi)) return false;
    PATTERNP p = new PATTERN(tok, style, pattern, index, 0);
    con.add_pattern(p);
    return true;
}


bool parse_announce_withdraw(TOKEN &tok, ROUTECONFIG &con, pattern_style style);
bool parse_announce_withdraw(TOKEN &tok, ROUTECONFIG &con, pattern_style style) {
    char *pattern = tok.next();
    int  index1 = 0;
    int  index2 = 0;
    if (!tsa(tok, token_lbrace)) return false;
    while (true) {
        char *have = tok.next();
        if (!have) break;
        if (have == token_rbrace) break;
        if (have == token_index_value) {
            index1 = tok.nextint();
            if (!tsa(tok, token_semi)) return false;
        }
        else if (have == token_index_length) {
            index2 = tok.nextint();
            if (!tsa(tok, token_semi)) return false;
        }
        else return false;
    }
    if (!tsa(tok, token_semi)) return false;
    PATTERNP p = new PATTERN(tok, style, pattern, index1, index2);
    con.add_pattern(p);
    return true;
}


bool parse_routeconfig(TOKEN &tok, CONFIG &dc);
bool parse_routeconfig(TOKEN &tok, CONFIG &dc) {
    char *name = tok.next();
    if (!tsa(tok, token_lbrace)) return false;
    ROUTECONFIGP con = new ROUTECONFIG(tok, name);
    if (con->failed()) {
        delete con;
        return false;
    }
    dc.add_routeconfig(con);
    while (true) {
        char *have = tok.next();
        if (!have) break;
        if (have == token_rbrace) break;
        if (have == token_reset) {
            if (!parse_path(tok, *con, NULL, style_reset)) return false;
        }
        else if (have == token_path) {
            if (!parse_path(tok, *con, token_index_path, style_path)) return false;
        }
        else if (have == token_ip) {
            if (!parse_path(tok, *con, token_index_ip, style_ip)) return false;
        }
        else if (have == token_announce) {
            if (!parse_announce_withdraw(tok, *con, style_announce)) return false;
        }
        else if (have == token_withdraw) {
            if (!parse_announce_withdraw(tok, *con, style_withdraw)) return false;
        }
        else {
            tok.token_error("path/announce/withdraw", have);
            return false;
        }
    }
    if (!tsa(tok, token_semi)) return false;
    return true;
}


////////////////////////////////////////////////
// parse a config file
//
bool load_conf(CONFIG &dc, char *fn) {
    int count = 0;
    TOKEN tok(fn, &dc.config_files);
    while (true) {
        char *have = tok.next();
        if (!have) break;
        if (have == token_file) {
            if (!parse_routeconfig(tok, dc)) return false;
            count++;
        }
        else {
            tok.token_error("file", have);
            return false;
        }
    }
    tok.token_error("load_conf() found %d syslog files in %s", count, fn);
    return (!dc.routeconfigs.empty());
}


////////////////////////////////////////////////
//
void routing_hourly_update() {
    route_base.update_history();
}


////////////////////////////////////////////////
// init the tokens
//
void token_init() {
    token_announce              = register_string("announce");
    token_file                  = register_string("file");
    token_include               = register_string("include");
    token_index_ip              = register_string("index_ip");
    token_index_length          = register_string("index_length");
    token_index_path            = register_string("index_path");
    token_index_value           = register_string("index_value");
    token_ip                    = register_string("ip");
    token_lbrace                = register_string("{");
    token_path                  = register_string("path");
    token_rbrace                = register_string("}");
    token_reset                 = register_string("reset");
    token_semi                  = register_string(";");
    token_slash                 = register_string("/");
    token_withdraw              = register_string("withdraw");
}