/*
- * DEBUG: section 28 Access Control
- * AUTHOR: Duane Wessels
+ * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
*
- * SQUID Web Proxy Cache http://www.squid-cache.org/
- * ----------------------------------------------------------
- *
- * Squid is the result of efforts by numerous individuals from
- * the Internet community; see the CONTRIBUTORS file for full
- * details. Many organizations have provided support for Squid's
- * development; see the SPONSORS file for full details. Squid is
- * Copyrighted (C) 2001 by the Regents of the University of
- * California; see the COPYRIGHT file for full details. Squid
- * incorporates software developed and/or copyrighted by other
- * sources; see the CREDITS file for full details.
- *
- * 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, USA.
- *
- * Copyright (c) 2003, Robert Collins <robertc@squid-cache.org>
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
*/
+/* DEBUG: section 28 Access Control */
+
#include "squid.h"
#include "acl/Checklist.h"
+#include "acl/Tree.h"
#include "Debug.h"
#include "profiler/Profiler.h"
-void
-ACLChecklist::matchNonBlocking()
+#include <algorithm>
+
+/// common parts of nonBlockingCheck() and resumeNonBlockingCheck()
+bool
+ACLChecklist::prepNonBlocking()
{
- if (checking())
- return;
+ assert(accessList);
if (callerGone()) {
checkCallback(ACCESS_DUNNO); // the answer does not really matter
- return;
- }
-
- /** The ACL List should NEVER be NULL when calling this method.
- * Always caller should check for NULL and handle appropriate to its needs first.
- * We cannot select a sensible default for all callers here. */
- if (accessList == NULL) {
- debugs(28, DBG_CRITICAL, "SECURITY ERROR: ACL " << this << " checked with nothing to match against!!");
- checkCallback(ACCESS_DUNNO);
- return;
+ return false;
}
- allow_t lastSeenKeyword = ACCESS_DUNNO;
- /* NOTE: This holds a cbdata reference to the current access_list
- * entry, not the whole list.
+ /** \par
+ * If the accessList is no longer valid (i.e. its been
+ * freed because of a reconfigure), then bail with ACCESS_DUNNO.
*/
- while (accessList != NULL) {
- /** \par
- * If the _acl_access is no longer valid (i.e. its been
- * freed because of a reconfigure), then bail with ACCESS_DUNNO.
- */
-
- if (!cbdataReferenceValid(accessList)) {
- cbdataReferenceDone(accessList);
- debugs(28, 4, "ACLChecklist::check: " << this << " accessList is invalid");
- checkCallback(ACCESS_DUNNO);
- return;
- }
-
- checking (true);
- checkAccessList();
- checking (false);
-
- if (asyncInProgress()) {
- return;
- }
-
- if (finished()) {
- /** \par
- * Either the request is allowed, denied, requires authentication.
- */
- debugs(28, 3, "ACLChecklist::check: " << this << " match found, calling back with " << currentAnswer());
- cbdataReferenceDone(accessList); /* A */
- checkCallback(currentAnswer());
- /* From here on in, this may be invalid */
- return;
- }
-
- lastSeenKeyword = accessList->allow;
- /*
- * Reference the next access entry
- */
- const acl_access *A = accessList;
-
- assert (A);
-
- accessList = cbdataReference(A->next);
-
- cbdataReferenceDone(A);
+ if (!cbdataReferenceValid(accessList)) {
+ cbdataReferenceDone(accessList);
+ debugs(28, 4, "ACLChecklist::check: " << this << " accessList is invalid");
+ checkCallback(ACCESS_DUNNO);
+ return false;
}
- calcImplicitAnswer(lastSeenKeyword);
- checkCallback(currentAnswer());
-}
-
-bool
-ACLChecklist::asyncNeeded() const
-{
- return state_ != NullState::Instance();
-}
-
-bool
-ACLChecklist::asyncInProgress() const
-{
- return async_;
+ return true;
}
void
-ACLChecklist::asyncInProgress(bool const newAsync)
+ACLChecklist::completeNonBlocking()
{
- assert (!finished() && !(asyncInProgress() && newAsync));
- async_ = newAsync;
- debugs(28, 3, "ACLChecklist::asyncInProgress: " << this <<
- " async set to " << async_);
-}
+ assert(!asyncInProgress());
-bool
-ACLChecklist::finished() const
-{
- return finished_;
+ if (!finished())
+ calcImplicitAnswer();
+
+ cbdataReferenceDone(accessList);
+ checkCallback(currentAnswer());
}
void
ACLChecklist::preCheck(const char *what)
{
debugs(28, 3, HERE << this << " checking " << what);
- finished_ = false;
-}
-void
-ACLChecklist::checkAccessList()
-{
- debugs(28, 3, HERE << this << " checking '" << accessList->cfgline << "'");
- /* does the current AND clause match */
- if (matchAclList(accessList->aclList, false))
- markFinished(accessList->allow, "first matching rule won");
-
- // If we are not finished() here, the caller must distinguish between
- // slow async calls and pure rule mismatches using asyncInProgress().
-}
+ // concurrent checks using the same Checklist are not supported
+ assert(!occupied_);
+ occupied_ = true;
+ asyncLoopDepth_ = 0;
-void
-ACLChecklist::checkForAsync()
-{
- asyncState()->checkForAsync(this);
+ AclMatchedName = NULL;
+ finished_ = false;
}
-// ACLFilledChecklist overwrites this to unclock something before we
-// "delete this"
-void
-ACLChecklist::checkCallback(allow_t answer)
+bool
+ACLChecklist::matchChild(const Acl::InnerNode *current, Acl::Nodes::const_iterator pos, const ACL *child)
{
- ACLCB *callback_;
- void *cbdata_;
- debugs(28, 3, "ACLChecklist::checkCallback: " << this << " answer=" << answer);
-
- callback_ = callback;
- callback = NULL;
-
- if (cbdataReferenceValidDone(callback_data, &cbdata_))
- callback_(answer, cbdata_);
+ assert(current && child);
+
+ // Remember the current tree location to prevent "async loop" cases where
+ // the same child node wants to go async more than once.
+ matchLoc_ = Breadcrumb(current, pos);
+ asyncLoopDepth_ = 0;
+
+ // if there are any breadcrumbs left, then follow them on the way down
+ bool result = false;
+ if (matchPath.empty()) {
+ result = child->matches(this);
+ } else {
+ const Breadcrumb top(matchPath.top());
+ assert(child == top.parent);
+ matchPath.pop();
+ result = top.parent->resumeMatchingAt(this, top.position);
+ }
- delete this;
-}
+ if (asyncInProgress()) {
+ // We get here for node N that called goAsync() and then, as the call
+ // stack unwinds, for the nodes higher in the ACL tree that led to N.
+ matchPath.push(Breadcrumb(current, pos));
+ } else {
+ asyncLoc_.clear();
+ }
-/// An ACLChecklist::matchNodes() wrapper to simplify profiling.
-bool
-ACLChecklist::matchAclList(const ACLList * head, bool const fast)
-{
- // TODO: remove by using object con/destruction-based PROF_* macros.
- PROF_start(aclMatchAclList);
- const bool result = matchNodes(head, fast);
- PROF_stop(aclMatchAclList);
+ matchLoc_.clear();
return result;
}
-/** Returns true if and only if there was a match. If false is returned:
- finished() indicates an error or exception of some kind, while
- !finished() means there was a mismatch or an allowed slow async call.
- If async calls are allowed (i.e. 'fast' was false), then those last
- two cases can be distinguished using asyncInProgress().
-*/
bool
-ACLChecklist::matchNodes(const ACLList * head, bool const fast)
+ACLChecklist::goAsync(AsyncState *state)
{
- assert(!finished());
-
- for (const ACLList *node = head; node; node = node->next) {
-
- const NodeMatchingResult resultBeforeAsync = matchNode(*node, fast);
+ assert(state);
+ assert(!asyncInProgress());
+ assert(matchLoc_.parent);
- if (resultBeforeAsync == nmrMatch)
- continue;
+ // TODO: add a once-in-a-while WARNING about fast directive using slow ACL?
+ if (!asyncCaller_) {
+ debugs(28, 2, this << " a fast-only directive uses a slow ACL!");
+ return false;
+ }
- if (resultBeforeAsync == nmrMismatch || resultBeforeAsync == nmrFinished)
+ // TODO: add a once-in-a-while WARNING about async loops?
+ if (matchLoc_ == asyncLoc_) {
+ debugs(28, 2, this << " a slow ACL resumes by going async again! (loop #" << asyncLoopDepth_ << ")");
+ // external_acl_type may cause async auth lookup plus its own async check
+ // which has the appearance of a loop. Allow some retries.
+ // TODO: make it configurable and check BH retry attempts vs this check?
+ if (asyncLoopDepth_ > 5)
return false;
+ }
- assert(resultBeforeAsync == nmrNeedsAsync);
-
- // Ideally, this should be inside match() itself, but that requires
- // prohibiting slow ACLs in options that do not support them.
- // TODO: rename to maybeStartAsync()?
- checkForAsync();
-
- // Some match() code claims that an async lookup is needed, but then
- // fails to start an async lookup when given a chance. We catch such
- // cases here and call matchNode() again, hoping that some cached data
- // prevents us from going async again.
- // This is inefficient and ugly, but fixing all match() code, including
- // the code it calls, such as ipcache_nbgethostbyname(), takes time.
- if (!asyncInProgress()) { // failed to start an async operation
-
- if (finished()) {
- debugs(28, 3, HERE << this << " finished after failing to go async: " << currentAnswer());
- return false; // an exceptional case
- }
-
- const NodeMatchingResult resultAfterAsync = matchNode(*node, true);
- // the second call disables slow checks so we cannot go async again
- assert(resultAfterAsync != nmrNeedsAsync);
- if (resultAfterAsync == nmrMatch)
- continue;
-
- assert(resultAfterAsync == nmrMismatch || resultAfterAsync == nmrFinished);
- return false;
- }
+ asyncLoc_ = matchLoc_; // prevent async loops
+ ++asyncLoopDepth_;
- assert(!finished()); // async operation is truly asynchronous
- debugs(28, 3, HERE << this << " awaiting async operation");
+ asyncStage_ = asyncStarting;
+ changeState(state);
+ state->checkForAsync(this); // this is supposed to go async
+
+ // Did AsyncState object actually go async? If not, tell the caller.
+ if (asyncStage_ != asyncStarting) {
+ assert(asyncStage_ == asyncFailed);
+ asyncStage_ = asyncNone; // sanity restored
return false;
}
- debugs(28, 3, HERE << this << " success: all ACLs matched");
+ // yes, we must pause until the async callback calls resumeNonBlockingCheck
+ asyncStage_ = asyncRunning;
return true;
}
-/// Check whether a single ACL matches, returning NodeMatchingResult
-ACLChecklist::NodeMatchingResult
-ACLChecklist::matchNode(const ACLList &node, bool const fast)
+// ACLFilledChecklist overwrites this to unclock something before we
+// "delete this"
+void
+ACLChecklist::checkCallback(allow_t answer)
{
- const bool nodeMatched = node.matches(this);
- const bool needsAsync = asyncNeeded();
- const bool matchFinished = finished();
-
- debugs(28, 3, HERE << this <<
- " matched=" << nodeMatched <<
- " async=" << needsAsync <<
- " finished=" << matchFinished);
-
- /* There are eight possible outcomes of the matches() call based on
- (matched, async, finished) permutations. We support these four:
- matched,!async,!finished: a match (must check next rule node)
- !matched,!async,!finished: a mismatch (whole rule fails to match)
- !matched,!async,finished: error or special condition (propagate)
- !matched,async,!finished: ACL needs to make an async call (pause)
- */
-
- if (nodeMatched) {
- // matches() should return false in all special cases
- assert(!needsAsync && !matchFinished);
- return nmrMatch;
- }
-
- if (matchFinished) {
- // we cannot be done and need an async call at the same time
- assert(!needsAsync);
- debugs(28, 3, HERE << this << " exception: " << currentAnswer());
- return nmrFinished;
- }
+ ACLCB *callback_;
+ void *cbdata_;
+ debugs(28, 3, "ACLChecklist::checkCallback: " << this << " answer=" << answer);
- if (!needsAsync) {
- debugs(28, 3, HERE << this << " simple mismatch");
- return nmrMismatch;
- }
+ callback_ = callback;
+ callback = NULL;
- /* we need an async call */
+ if (cbdataReferenceValidDone(callback_data, &cbdata_))
+ callback_(answer, cbdata_);
- if (fast) {
- changeState(NullState::Instance()); // disable async checks
- markFinished(ACCESS_DUNNO, "async required but prohibited");
- debugs(28, 3, HERE << this << " DUNNO because cannot async");
- return nmrFinished;
- }
+ // not really meaningful just before delete, but here for completeness sake
+ occupied_ = false;
- debugs(28, 3, HERE << this << " going async");
- return nmrNeedsAsync;
+ delete this;
}
ACLChecklist::ACLChecklist() :
- accessList (NULL),
- callback (NULL),
- callback_data (NULL),
- async_(false),
- finished_(false),
- allow_(ACCESS_DENIED),
- state_(NullState::Instance())
+ accessList (NULL),
+ callback (NULL),
+ callback_data (NULL),
+ asyncCaller_(false),
+ occupied_(false),
+ finished_(false),
+ allow_(ACCESS_DENIED),
+ asyncStage_(asyncNone),
+ state_(NullState::Instance()),
+ asyncLoopDepth_(0)
{
}
{
assert (!asyncInProgress());
- cbdataReferenceDone(accessList);
+ changeAcl(nullptr);
debugs(28, 4, "ACLChecklist::~ACLChecklist: destroyed " << this);
}
-void
-ACLChecklist::AsyncState::changeState (ACLChecklist *checklist, AsyncState *newState) const
-{
- checklist->changeState(newState);
-}
-
ACLChecklist::NullState *
ACLChecklist::NullState::Instance()
{
void
ACLChecklist::NullState::checkForAsync(ACLChecklist *) const
-{}
+{
+ assert(false); // or the Checklist will never get out of the async state
+}
ACLChecklist::NullState ACLChecklist::NullState::_instance;
preCheck("slow rules");
callback = callback_;
callback_data = cbdataReference(callback_data_);
- matchNonBlocking();
+ asyncCaller_ = true;
+
+ /** The ACL List should NEVER be NULL when calling this method.
+ * Always caller should check for NULL and handle appropriate to its needs first.
+ * We cannot select a sensible default for all callers here. */
+ if (accessList == NULL) {
+ debugs(28, DBG_CRITICAL, "SECURITY ERROR: ACL " << this << " checked with nothing to match against!!");
+ checkCallback(ACCESS_DUNNO);
+ return;
+ }
+
+ if (prepNonBlocking()) {
+ matchAndFinish(); // calls markFinished() on success
+ if (!asyncInProgress())
+ completeNonBlocking();
+ } // else checkCallback() has been called
+}
+
+void
+ACLChecklist::resumeNonBlockingCheck(AsyncState *state)
+{
+ assert(asyncState() == state);
+ changeState(NullState::Instance());
+
+ if (asyncStage_ == asyncStarting) { // oops, we did not really go async
+ asyncStage_ = asyncFailed; // goAsync() checks for that
+ // Do not fall through to resume checks from the async callback. Let
+ // the still-pending(!) goAsync() notice and notify its caller instead.
+ return;
+ }
+ assert(asyncStage_ == asyncRunning);
+ asyncStage_ = asyncNone;
+
+ assert(!matchPath.empty());
+
+ if (!prepNonBlocking())
+ return; // checkCallback() has been called
+
+ if (!finished())
+ matchAndFinish();
+
+ if (asyncInProgress())
+ assert(!matchPath.empty()); // we have breadcrumbs to resume matching
+ else
+ completeNonBlocking();
+}
+
+/// performs (or resumes) an ACL tree match and, if successful, sets the action
+void
+ACLChecklist::matchAndFinish()
+{
+ bool result = false;
+ if (matchPath.empty()) {
+ result = accessList->matches(this);
+ } else {
+ const Breadcrumb top(matchPath.top());
+ matchPath.pop();
+ result = top.parent->resumeMatchingAt(this, top.position);
+ }
+
+ if (result) // the entire tree matched
+ markFinished(accessList->winningAction(), "match");
}
allow_t const &
-ACLChecklist::fastCheck(const ACLList * list)
+ACLChecklist::fastCheck(const Acl::Tree * list)
{
PROF_start(aclCheckFast);
preCheck("fast ACLs");
+ asyncCaller_ = false;
+
+ // Concurrent checks are not supported, but sequential checks are, and they
+ // may use a mixture of fastCheck(void) and fastCheck(list) calls.
+ const Acl::Tree * const savedList = changeAcl(list);
+
+ // assume DENY/ALLOW on mis/matches due to action-free accessList
+ // matchAndFinish() takes care of the ALLOW case
+ if (accessList && cbdataReferenceValid(accessList))
+ matchAndFinish(); // calls markFinished() on success
+ if (!finished())
+ markFinished(ACCESS_DENIED, "ACLs failed to match");
- // assume DENY/ALLOW on mis/matches due to not having acl_access object
- if (matchAclList(list, true))
- markFinished(ACCESS_ALLOWED, "all ACLs matched");
- else if (!finished())
- markFinished(ACCESS_DENIED, "ACL mismatched");
+ changeAcl(savedList);
+ occupied_ = false;
PROF_stop(aclCheckFast);
return currentAnswer();
}
PROF_start(aclCheckFast);
preCheck("fast rules");
+ asyncCaller_ = false;
- allow_t lastSeenKeyword = ACCESS_DUNNO;
debugs(28, 5, "aclCheckFast: list: " << accessList);
- const acl_access *acl = cbdataReference(accessList);
- while (acl != NULL && cbdataReferenceValid(acl)) {
- // on a match, finish
- if (matchAclList(acl->aclList, true))
- markFinished(acl->allow, "first matching rule won");
+ const Acl::Tree *acl = cbdataReference(accessList);
+ if (acl != NULL && cbdataReferenceValid(acl)) {
+ matchAndFinish(); // calls markFinished() on success
// if finished (on a match or in exceptional cases), stop
if (finished()) {
cbdataReferenceDone(acl);
+ occupied_ = false;
PROF_stop(aclCheckFast);
return currentAnswer();
}
- // on a mismatch, try the next access rule
- lastSeenKeyword = acl->allow;
- const acl_access *A = acl;
- acl = cbdataReference(acl->next);
- cbdataReferenceDone(A);
+ // fall through for mismatch handling
}
// There were no rules to match or no rules matched
- calcImplicitAnswer(lastSeenKeyword);
+ calcImplicitAnswer();
+ cbdataReferenceDone(acl);
+ occupied_ = false;
PROF_stop(aclCheckFast);
return currentAnswer();
}
-/// When no rules matched, the answer is the inversion of the last seen rule
-/// action (or ACCESS_DUNNO if the reversal is not possible). The caller
-/// should set lastSeenAction to ACCESS_DUNNO if there were no rules to see.
+/// When no rules matched, the answer is the inversion of the last rule
+/// action (or ACCESS_DUNNO if the reversal is not possible).
void
-ACLChecklist::calcImplicitAnswer(const allow_t &lastSeenAction)
+ACLChecklist::calcImplicitAnswer()
{
+ const allow_t lastAction = (accessList && cbdataReferenceValid(accessList)) ?
+ accessList->lastAction() : allow_t(ACCESS_DUNNO);
allow_t implicitRuleAnswer = ACCESS_DUNNO;
- if (lastSeenAction == ACCESS_DENIED) // reverse last seen "deny"
+ if (lastAction == ACCESS_DENIED) // reverse last seen "deny"
implicitRuleAnswer = ACCESS_ALLOWED;
- else if (lastSeenAction == ACCESS_ALLOWED) // reverse last seen "allow"
+ else if (lastAction == ACCESS_ALLOWED) // reverse last seen "allow"
implicitRuleAnswer = ACCESS_DENIED;
// else we saw no rules and will respond with ACCESS_DUNNO
debugs(28, 3, HERE << this << " NO match found, last action " <<
- lastSeenAction << " so returning " << implicitRuleAnswer);
+ lastAction << " so returning " << implicitRuleAnswer);
markFinished(implicitRuleAnswer, "implicit rule won");
}
bool
-ACLChecklist::checking() const
+ACLChecklist::callerGone()
{
- return checking_;
+ return !cbdataReferenceValid(callback_data);
}
-void
-ACLChecklist::checking (bool const newValue)
+bool
+ACLChecklist::bannedAction(const allow_t &action) const
{
- checking_ = newValue;
+ const bool found = std::find(bannedActions_.begin(), bannedActions_.end(), action) != bannedActions_.end();
+ debugs(28, 5, "Action '" << action << "/" << action.kind << (found ? "' is " : "' is not") << " banned");
+ return found;
}
-bool
-ACLChecklist::callerGone()
+void
+ACLChecklist::banAction(const allow_t &action)
{
- return !cbdataReferenceValid(callback_data);
+ bannedActions_.push_back(action);
}
+