[thirdparty/squid.git] / src / acl / RegexData.cc

/*
 * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
 *
 * Squid software is distributed under GPLv2+ license and includes
 * contributions from numerous individuals and organizations.
 * Please see the COPYING and CONTRIBUTORS files for details.
 */

/*
 * Portions of this code are copyrighted and released under GPLv2+ by:
 * Copyright (c) 2011, Marcus Kool
 * Please add new claims to the CONTRIBUTORS file instead.
 */

/* DEBUG: section 28    Access Control */

#include "squid.h"
#include "acl/Acl.h"
#include "acl/Checklist.h"
#include "acl/RegexData.h"
#include "base/RegexPattern.h"
#include "ConfigParser.h"
#include "Debug.h"
#include "sbuf/Algorithms.h"
#include "sbuf/List.h"

ACLRegexData::~ACLRegexData()
{
}

const Acl::ParameterFlags &
ACLRegexData::supportedFlags() const
{
    static const Acl::ParameterFlags flags = { "-i", "+i" };
    return flags;
}

bool
ACLRegexData::match(char const *word)
{
    if (!word)
        return 0;

    debugs(28, 3, "checking '" << word << "'");

    // walk the list of patterns to see if one matches
    for (auto &i : data) {
        if (i.match(word)) {
            debugs(28, 2, '\'' << i.c_str() << "' found in '" << word << '\'');
            // TODO: old code also popped the pattern to second place of the list
            // in order to reduce patterns search times.
            return 1;
        }
    }

    return 0;
}

SBufList
ACLRegexData::dump() const
{
    SBufList sl;
    int flags = REG_EXTENDED | REG_NOSUB;

    // walk and dump the list
    // keeping the flags values consistent
    for (auto &i : data) {
        if (i.flags != flags) {
            if ((i.flags&REG_ICASE) != 0) {
                sl.emplace_back("-i");
            } else {
                sl.emplace_back("+i");
            }
            flags = i.flags;
        }

        sl.emplace_back(i.c_str());
    }

    return sl;
}

static const char *
removeUnnecessaryWildcards(char * t)
{
    char * orig = t;

    if (strncmp(t, "^.*", 3) == 0)
        t += 3;

    /* NOTE: an initial '.' might seem unnessary but is not;
     * it can be a valid requirement that cannot be optimised
     */
    while (*t == '.'  &&  *(t+1) == '*') {
        t += 2;
    }

    if (*t == '\0') {
        debugs(28, DBG_IMPORTANT, cfg_filename << " line " << config_lineno << ": " << config_input_line);
        debugs(28, DBG_IMPORTANT, "WARNING: regular expression '" << orig << "' has only wildcards and matches all strings. Using '.*' instead.");
        return ".*";
    }
    if (t != orig) {
        debugs(28, DBG_IMPORTANT, cfg_filename << " line " << config_lineno << ": " << config_input_line);
        debugs(28, DBG_IMPORTANT, "WARNING: regular expression '" << orig << "' has unnecessary wildcard(s). Using '" << t << "' instead.");
    }

    return t;
}

static bool
compileRE(std::list<RegexPattern> &curlist, const char * RE, int flags)
{
    if (RE == NULL || *RE == '\0')
        return curlist.empty(); // XXX: old code did this. It looks wrong.

    regex_t comp;
    if (int errcode = regcomp(&comp, RE, flags)) {
        char errbuf[256];
        regerror(errcode, &comp, errbuf, sizeof errbuf);
        debugs(28, DBG_CRITICAL, cfg_filename << " line " << config_lineno << ": " << config_input_line);
        debugs(28, DBG_CRITICAL, "ERROR: invalid regular expression: '" << RE << "': " << errbuf);
        return false;
    }
    debugs(28, 2, "compiled '" << RE << "' with flags " << flags);

    curlist.emplace_back(flags, RE);
    curlist.back().regex = comp;

    return true;
}

static bool
compileRE(std::list<RegexPattern> &curlist, const SBufList &RE, int flags)
{
    if (RE.empty())
        return curlist.empty(); // XXX: old code did this. It looks wrong.
    SBuf regexp;
    static const SBuf openparen("("), closeparen(")"), separator(")|(");
    JoinContainerIntoSBuf(regexp, RE.begin(), RE.end(), separator, openparen,
                          closeparen);
    return compileRE(curlist, regexp.c_str(), flags);
}

/** Compose and compile one large RE from a set of (small) REs.
 * The ultimate goal is to have only one RE per ACL so that match() is
 * called only once per ACL.
 */
static int
compileOptimisedREs(std::list<RegexPattern> &curlist, const SBufList &sl)
{
    std::list<RegexPattern> newlist;
    SBufList accumulatedRE;
    int numREs = 0, reSize = 0;
    int flags = REG_EXTENDED | REG_NOSUB;

    for (const SBuf & configurationLineWord : sl) {
        static const SBuf minus_i("-i");
        static const SBuf plus_i("+i");
        if (configurationLineWord == minus_i) {
            if (flags & REG_ICASE) {
                /* optimisation of  -i ... -i */
                debugs(28, 2, "optimisation of -i ... -i" );
            } else {
                debugs(28, 2, "-i" );
                if (!compileRE(newlist, accumulatedRE, flags))
                    return 0;
                flags |= REG_ICASE;
                accumulatedRE.clear();
                reSize = 0;
            }
            continue;
        } else if (configurationLineWord == plus_i) {
            if ((flags & REG_ICASE) == 0) {
                /* optimisation of  +i ... +i */
                debugs(28, 2, "optimisation of +i ... +i");
            } else {
                debugs(28, 2, "+i");
                if (!compileRE(newlist, accumulatedRE, flags))
                    return 0;
                flags &= ~REG_ICASE;
                accumulatedRE.clear();
                reSize = 0;
            }
            continue;
        }

        debugs(28, 2, "adding RE '" << configurationLineWord << "'");
        accumulatedRE.push_back(configurationLineWord);
        ++numREs;
        reSize += configurationLineWord.length();

        if (reSize > 1024) { // must be < BUFSIZ everything included
            debugs(28, 2, "buffer full, generating new optimised RE..." );
            if (!compileRE(newlist, accumulatedRE, flags))
                return 0;
            accumulatedRE.clear();
            reSize = 0;
            continue;    /* do the loop again to add the RE to largeRE */
        }
    }

    if (!compileRE(newlist, accumulatedRE, flags))
        return 0;

    accumulatedRE.clear();
    reSize = 0;

    /* all was successful, so put the new list at the tail */
    curlist.splice(curlist.end(), newlist);

    debugs(28, 2, numREs << " REs are optimised into one RE.");
    if (numREs > 100) {
        debugs(28, (opt_parse_cfg_only?DBG_IMPORTANT:2), cfg_filename << " line " << config_lineno << ": " << config_input_line);
        debugs(28, (opt_parse_cfg_only?DBG_IMPORTANT:2), "WARNING: there are more than 100 regular expressions. " <<
               "Consider using less REs or use rules without expressions like 'dstdomain'.");
    }

    return 1;
}

static void
compileUnoptimisedREs(std::list<RegexPattern> &curlist, const SBufList &sl)
{
    int flags = REG_EXTENDED | REG_NOSUB;

    static const SBuf minus_i("-i"), plus_i("+i");
    for (auto configurationLineWord : sl) {
        if (configurationLineWord == minus_i) {
            flags |= REG_ICASE;
        } else if (configurationLineWord == plus_i) {
            flags &= ~REG_ICASE;
        } else {
            if (!compileRE(curlist, configurationLineWord.c_str(), flags))
                debugs(28, DBG_CRITICAL, "ERROR: Skipping regular expression. "
                       "Compile failed: '" << configurationLineWord << "'");
        }
    }
}

void
ACLRegexData::parse()
{
    debugs(28, 2, "new Regex line or file");

    SBufList sl;
    while (char *t = ConfigParser::RegexStrtokFile()) {
        const char *clean = removeUnnecessaryWildcards(t);
        if (strlen(clean) > BUFSIZ-1) {
            debugs(28, DBG_CRITICAL, cfg_filename << " line " << config_lineno << ": " << config_input_line);
            debugs(28, DBG_CRITICAL, "ERROR: Skipping regular expression. Larger than " << BUFSIZ-1 << " characters: '" << clean << "'");
        } else {
            debugs(28, 3, "buffering RE '" << clean << "'");
            sl.emplace_back(clean);
        }
    }

    if (!compileOptimisedREs(data, sl)) {
        debugs(28, DBG_IMPORTANT, "WARNING: optimisation of regular expressions failed; using fallback method without optimisation");
        compileUnoptimisedREs(data, sl);
    }
}

bool
ACLRegexData::empty() const
{
    return data.empty();
}

ACLData<char const *> *
ACLRegexData::clone() const
{
    /* Regex's don't clone yet. */
    assert(data.empty());
    return new ACLRegexData;
}
Commit	Line	Data
	1	/*
	2	* Copyright (C) 1996-2021 The Squid Software Foundation and contributors
	3	*
	4	* Squid software is distributed under GPLv2+ license and includes
	5	* contributions from numerous individuals and organizations.
	6	* Please see the COPYING and CONTRIBUTORS files for details.
	7	*/
	8
	9	/*
	10	* Portions of this code are copyrighted and released under GPLv2+ by:
	11	* Copyright (c) 2011, Marcus Kool
	12	* Please add new claims to the CONTRIBUTORS file instead.
	13	*/
	14
	15	/* DEBUG: section 28 Access Control */
	16
	17	#include "squid.h"
	18	#include "acl/Acl.h"
	19	#include "acl/Checklist.h"
	20	#include "acl/RegexData.h"
	21	#include "base/RegexPattern.h"
	22	#include "ConfigParser.h"
	23	#include "Debug.h"
	24	#include "sbuf/Algorithms.h"
	25	#include "sbuf/List.h"
	26
	27	ACLRegexData::~ACLRegexData()
	28	{
	29	}
	30
	31	const Acl::ParameterFlags &
	32	ACLRegexData::supportedFlags() const
	33	{
	34	static const Acl::ParameterFlags flags = { "-i", "+i" };
	35	return flags;
	36	}
	37
	38	bool
	39	ACLRegexData::match(char const *word)
	40	{
	41	if (!word)
	42	return 0;
	43
	44	debugs(28, 3, "checking '" << word << "'");
	45
	46	// walk the list of patterns to see if one matches
	47	for (auto &i : data) {
	48	if (i.match(word)) {
	49	debugs(28, 2, '\'' << i.c_str() << "' found in '" << word << '\'');
	50	// TODO: old code also popped the pattern to second place of the list
	51	// in order to reduce patterns search times.
	52	return 1;
	53	}
	54	}
	55
	56	return 0;
	57	}
	58
	59	SBufList
	60	ACLRegexData::dump() const
	61	{
	62	SBufList sl;
	63	int flags = REG_EXTENDED \| REG_NOSUB;
	64
	65	// walk and dump the list
	66	// keeping the flags values consistent
	67	for (auto &i : data) {
	68	if (i.flags != flags) {
	69	if ((i.flags&REG_ICASE) != 0) {
	70	sl.emplace_back("-i");
	71	} else {
	72	sl.emplace_back("+i");
	73	}
	74	flags = i.flags;
	75	}
	76
	77	sl.emplace_back(i.c_str());
	78	}
	79
	80	return sl;
	81	}
	82
	83	static const char *
	84	removeUnnecessaryWildcards(char * t)
	85	{
	86	char * orig = t;
	87
	88	if (strncmp(t, "^.*", 3) == 0)
	89	t += 3;
	90
	91	/* NOTE: an initial '.' might seem unnessary but is not;
	92	* it can be a valid requirement that cannot be optimised
	93	*/
	94	while (t == '.' && (t+1) == '*') {
	95	t += 2;
	96	}
	97
	98	if (*t == '\0') {
	99	debugs(28, DBG_IMPORTANT, cfg_filename << " line " << config_lineno << ": " << config_input_line);
	100	debugs(28, DBG_IMPORTANT, "WARNING: regular expression '" << orig << "' has only wildcards and matches all strings. Using '.*' instead.");
	101	return ".*";
	102	}
	103	if (t != orig) {
	104	debugs(28, DBG_IMPORTANT, cfg_filename << " line " << config_lineno << ": " << config_input_line);
	105	debugs(28, DBG_IMPORTANT, "WARNING: regular expression '" << orig << "' has unnecessary wildcard(s). Using '" << t << "' instead.");
	106	}
	107
	108	return t;
	109	}
	110
	111	static bool
	112	compileRE(std::list<RegexPattern> &curlist, const char * RE, int flags)
	113	{
	114	if (RE == NULL \|\| *RE == '\0')
	115	return curlist.empty(); // XXX: old code did this. It looks wrong.
	116
	117	regex_t comp;
	118	if (int errcode = regcomp(&comp, RE, flags)) {
	119	char errbuf[256];
	120	regerror(errcode, &comp, errbuf, sizeof errbuf);
	121	debugs(28, DBG_CRITICAL, cfg_filename << " line " << config_lineno << ": " << config_input_line);
	122	debugs(28, DBG_CRITICAL, "ERROR: invalid regular expression: '" << RE << "': " << errbuf);
	123	return false;
	124	}
	125	debugs(28, 2, "compiled '" << RE << "' with flags " << flags);
	126
	127	curlist.emplace_back(flags, RE);
	128	curlist.back().regex = comp;
	129
	130	return true;
	131	}
	132
	133	static bool
	134	compileRE(std::list<RegexPattern> &curlist, const SBufList &RE, int flags)
	135	{
	136	if (RE.empty())
	137	return curlist.empty(); // XXX: old code did this. It looks wrong.
	138	SBuf regexp;
	139	static const SBuf openparen("("), closeparen(")"), separator(")\|(");
	140	JoinContainerIntoSBuf(regexp, RE.begin(), RE.end(), separator, openparen,
	141	closeparen);
	142	return compileRE(curlist, regexp.c_str(), flags);
	143	}
	144
	145	/** Compose and compile one large RE from a set of (small) REs.
	146	* The ultimate goal is to have only one RE per ACL so that match() is
	147	* called only once per ACL.
	148	*/
	149	static int
	150	compileOptimisedREs(std::list<RegexPattern> &curlist, const SBufList &sl)
	151	{
	152	std::list<RegexPattern> newlist;
	153	SBufList accumulatedRE;
	154	int numREs = 0, reSize = 0;
	155	int flags = REG_EXTENDED \| REG_NOSUB;
	156
	157	for (const SBuf & configurationLineWord : sl) {
	158	static const SBuf minus_i("-i");
	159	static const SBuf plus_i("+i");
	160	if (configurationLineWord == minus_i) {
	161	if (flags & REG_ICASE) {
	162	/* optimisation of -i ... -i */
	163	debugs(28, 2, "optimisation of -i ... -i" );
	164	} else {
	165	debugs(28, 2, "-i" );
	166	if (!compileRE(newlist, accumulatedRE, flags))
	167	return 0;
	168	flags \|= REG_ICASE;
	169	accumulatedRE.clear();
	170	reSize = 0;
	171	}
	172	continue;
	173	} else if (configurationLineWord == plus_i) {
	174	if ((flags & REG_ICASE) == 0) {
	175	/* optimisation of +i ... +i */
	176	debugs(28, 2, "optimisation of +i ... +i");
	177	} else {
	178	debugs(28, 2, "+i");
	179	if (!compileRE(newlist, accumulatedRE, flags))
	180	return 0;
	181	flags &= ~REG_ICASE;
	182	accumulatedRE.clear();
	183	reSize = 0;
	184	}
	185	continue;
	186	}
	187
	188	debugs(28, 2, "adding RE '" << configurationLineWord << "'");
	189	accumulatedRE.push_back(configurationLineWord);
	190	++numREs;
	191	reSize += configurationLineWord.length();
	192
	193	if (reSize > 1024) { // must be < BUFSIZ everything included
	194	debugs(28, 2, "buffer full, generating new optimised RE..." );
	195	if (!compileRE(newlist, accumulatedRE, flags))
	196	return 0;
	197	accumulatedRE.clear();
	198	reSize = 0;
	199	continue; /* do the loop again to add the RE to largeRE */
	200	}
	201	}
	202
	203	if (!compileRE(newlist, accumulatedRE, flags))
	204	return 0;
	205
	206	accumulatedRE.clear();
	207	reSize = 0;
	208
	209	/* all was successful, so put the new list at the tail */
	210	curlist.splice(curlist.end(), newlist);
	211
	212	debugs(28, 2, numREs << " REs are optimised into one RE.");
	213	if (numREs > 100) {
	214	debugs(28, (opt_parse_cfg_only?DBG_IMPORTANT:2), cfg_filename << " line " << config_lineno << ": " << config_input_line);
	215	debugs(28, (opt_parse_cfg_only?DBG_IMPORTANT:2), "WARNING: there are more than 100 regular expressions. " <<
	216	"Consider using less REs or use rules without expressions like 'dstdomain'.");
	217	}
	218
	219	return 1;
	220	}
	221
	222	static void
	223	compileUnoptimisedREs(std::list<RegexPattern> &curlist, const SBufList &sl)
	224	{
	225	int flags = REG_EXTENDED \| REG_NOSUB;
	226
	227	static const SBuf minus_i("-i"), plus_i("+i");
	228	for (auto configurationLineWord : sl) {
	229	if (configurationLineWord == minus_i) {
	230	flags \|= REG_ICASE;
	231	} else if (configurationLineWord == plus_i) {
	232	flags &= ~REG_ICASE;
	233	} else {
	234	if (!compileRE(curlist, configurationLineWord.c_str(), flags))
	235	debugs(28, DBG_CRITICAL, "ERROR: Skipping regular expression. "
	236	"Compile failed: '" << configurationLineWord << "'");
	237	}
	238	}
	239	}
	240
	241	void
	242	ACLRegexData::parse()
	243	{
	244	debugs(28, 2, "new Regex line or file");
	245
	246	SBufList sl;
	247	while (char *t = ConfigParser::RegexStrtokFile()) {
	248	const char *clean = removeUnnecessaryWildcards(t);
	249	if (strlen(clean) > BUFSIZ-1) {
	250	debugs(28, DBG_CRITICAL, cfg_filename << " line " << config_lineno << ": " << config_input_line);
	251	debugs(28, DBG_CRITICAL, "ERROR: Skipping regular expression. Larger than " << BUFSIZ-1 << " characters: '" << clean << "'");
	252	} else {
	253	debugs(28, 3, "buffering RE '" << clean << "'");
	254	sl.emplace_back(clean);
	255	}
	256	}
	257
	258	if (!compileOptimisedREs(data, sl)) {
	259	debugs(28, DBG_IMPORTANT, "WARNING: optimisation of regular expressions failed; using fallback method without optimisation");
	260	compileUnoptimisedREs(data, sl);
	261	}
	262	}
	263
	264	bool
	265	ACLRegexData::empty() const
	266	{
	267	return data.empty();
	268	}
	269
	270	ACLData<char const >
	271	ACLRegexData::clone() const
	272	{
	273	/* Regex's don't clone yet. */
	274	assert(data.empty());
	275	return new ACLRegexData;
	276	}
	277