From a4d576deb4f3ce744211ac4a973f1dd2b9f12a34 Mon Sep 17 00:00:00 2001 From: Eduard Bagdasaryan Date: Thu, 23 Apr 2020 05:12:27 +0000 Subject: [PATCH] Happy Eyeballs: Do not discard viable reforwarding destinations (#567) When HappyConnOpener starts opening two connections, both destinations are removed from the shared destinations list. As soon as one connection (X) succeeded, the other destination (Y) was essentially forgotten. If FwdState, after using X, decided to reforward the request, then the request was never reforwarded to Y. We now return Y to the list. Also abort the still-active ConnOpener job upon the termination of its "parent" HappyConnOpener job. Without an explicit termination, those abandoned child jobs wasted OS and Squid resources while the OS was trying to open the requested connection. They would terminate on a timeout or when the connection was finally opened (and discarded). Waiting for the child ConnOpener job to end is a useful optimization, but it remains a TODO. It requires complex accumulation avoidance logic. Also fixed retrying via FwdState::fail() which could reorder addresses. It incorrectly assumed that only the prime connections were retried. --- src/HappyConnOpener.cc | 32 +++++-- src/HappyConnOpener.h | 15 +++- src/ResolvedPeers.cc | 186 ++++++++++++++++++++++++++++++----------- src/ResolvedPeers.h | 50 +++++++++-- src/comm/forward.h | 2 - 5 files changed, 214 insertions(+), 71 deletions(-) diff --git a/src/HappyConnOpener.cc b/src/HappyConnOpener.cc index 12ec665172..6e5abd83ac 100644 --- a/src/HappyConnOpener.cc +++ b/src/HappyConnOpener.cc @@ -397,15 +397,11 @@ HappyConnOpener::swanSong() // TODO: Find an automated, faster way to kill no-longer-needed jobs. if (prime) { - if (prime.connector) - prime.connector->cancel("HappyConnOpener object destructed"); - prime.clear(); + cancelAttempt(prime, "job finished during a prime attempt"); } if (spare) { - if (spare.connector) - spare.connector->cancel("HappyConnOpener object destructed"); - spare.clear(); + cancelAttempt(spare, "job finished during a spare attempt"); if (gotSpareAllowance) { TheSpareAllowanceGiver.jobDroppedAllowance(); gotSpareAllowance = false; @@ -484,6 +480,15 @@ HappyConnOpener::sendSuccess(const Comm::ConnectionPointer &conn, bool reused, c callback_ = nullptr; } +/// cancels the in-progress attempt, making its path a future candidate +void +HappyConnOpener::cancelAttempt(Attempt &attempt, const char *reason) +{ + Must(attempt); + destinations->retryPath(attempt.path); // before attempt.cancel() clears path + attempt.cancel(reason); +} + /// inform the initiator about our failure to connect (if needed) void HappyConnOpener::sendFailure() @@ -563,6 +568,7 @@ HappyConnOpener::openFreshConnection(Attempt &attempt, Comm::ConnectionPointer & attempt.path = dest; attempt.connector = callConnect; + attempt.opener = cs; AsyncJob::Start(cs); } @@ -578,9 +584,9 @@ HappyConnOpener::connectDone(const CommConnectCbParams ¶ms) Must(itWasPrime != itWasSpare); if (itWasPrime) { - prime.clear(); + prime.finish(); } else { - spare.clear(); + spare.finish(); if (gotSpareAllowance) { TheSpareAllowanceGiver.jobUsedAllowance(); gotSpareAllowance = false; @@ -869,3 +875,13 @@ HappyConnOpener::ranOutOfTimeOrAttempts() const return false; } +void +HappyConnOpener::Attempt::cancel(const char *reason) +{ + if (connector) { + connector->cancel(reason); + CallJobHere(17, 3, opener, Comm::ConnOpener, noteAbort); + } + clear(); +} + diff --git a/src/HappyConnOpener.h b/src/HappyConnOpener.h index 4c0a0317d1..c1cb95bda3 100644 --- a/src/HappyConnOpener.h +++ b/src/HappyConnOpener.h @@ -157,10 +157,20 @@ private: class Attempt { public: explicit operator bool() const { return static_cast(path); } - void clear() { path = nullptr; connector = nullptr; } + + /// reacts to a natural attempt completion (successful or otherwise) + void finish() { clear(); } + + /// aborts an in-progress attempt + void cancel(const char *reason); Comm::ConnectionPointer path; ///< the destination we are connecting to - AsyncCall::Pointer connector; ///< our Comm::ConnOpener callback + AsyncCall::Pointer connector; ///< our opener callback + Comm::ConnOpener::Pointer opener; ///< connects to path and calls us + + private: + /// cleans up after the attempt ends (successfully or otherwise) + void clear() { path = nullptr; connector = nullptr; opener = nullptr; } }; /* AsyncJob API */ @@ -194,6 +204,7 @@ private: Answer *futureAnswer(const Comm::ConnectionPointer &); void sendSuccess(const Comm::ConnectionPointer &conn, bool reused, const char *connKind); void sendFailure(); + void cancelAttempt(Attempt &, const char *reason); const time_t fwdStart; ///< requestor start time diff --git a/src/ResolvedPeers.cc b/src/ResolvedPeers.cc index 8e496b5a06..d8f00cb443 100644 --- a/src/ResolvedPeers.cc +++ b/src/ResolvedPeers.cc @@ -24,59 +24,117 @@ ResolvedPeers::retryPath(const Comm::ConnectionPointer &path) { debugs(17, 4, path); assert(path); - paths_.emplace(paths_.begin(), path); + // Cannot use pathsToSkip for a faster (reverse) search because there + // may be unavailable paths past pathsToSkip. We could remember + // the last extraction index, but, to completely avoid a linear search, + // extract*() methods should return the path index. + const auto found = std::find_if(paths_.begin(), paths_.end(), + [path](const ResolvedPeerPath &candidate) { + return candidate.connection == path; // (refcounted) pointer comparison + }); + assert(found != paths_.end()); + assert(!found->available); + found->available = true; + increaseAvailability(); + + // if we restored availability of a path that we used to skip, update + const auto pathsToTheLeft = static_cast(found - paths_.begin()); + if (pathsToTheLeft < pathsToSkip) { + pathsToSkip = pathsToTheLeft; + } else { + // *found was unavailable so pathsToSkip could not end at it + Must(pathsToTheLeft != pathsToSkip); + } } void ResolvedPeers::addPath(const Comm::ConnectionPointer &path) { paths_.emplace_back(path); + Must(paths_.back().available); // no pathsToSkip updates are needed + increaseAvailability(); +} + +/// \returns the beginning iterator for any available-path search +ResolvedPeers::Paths::iterator +ResolvedPeers::start() +{ + Must(pathsToSkip <= paths_.size()); + return paths_.begin() + pathsToSkip; // may return end() +} + +/// finalizes the iterator part of the given preliminary find*() result +ResolvedPeers::Finding +ResolvedPeers::makeFinding(const Paths::iterator &path, bool foundOther) +{ + return std::make_pair((foundOther ? paths_.end() : path), foundOther); +} + +/// \returns the first available same-peer same-family Finding or +ResolvedPeers::Finding +ResolvedPeers::findPrime(const Comm::Connection ¤tPeer) +{ + const auto path = start(); + const auto foundNextOrSpare = path != paths_.end() && + (currentPeer.getPeer() != path->connection->getPeer() || // next peer + ConnectionFamily(currentPeer) != ConnectionFamily(*path->connection)); + return makeFinding(path, foundNextOrSpare); +} + +/// \returns the first available same-peer different-family Finding or +ResolvedPeers::Finding +ResolvedPeers::findSpare(const Comm::Connection ¤tPeer) +{ + const auto primeFamily = ConnectionFamily(currentPeer); + const auto primePeer = currentPeer.getPeer(); + const auto path = std::find_if(start(), paths_.end(), + [primeFamily, primePeer](const ResolvedPeerPath &candidate) { + if (!candidate.available) + return false; + if (primePeer != candidate.connection->getPeer()) + return true; // found next peer + if (primeFamily != ConnectionFamily(*candidate.connection)) + return true; // found spare + return false; + }); + const auto foundNext = path != paths_.end() && + primePeer != path->connection->getPeer(); + return makeFinding(path, foundNext); +} + +/// \returns the first available same-peer Finding or +ResolvedPeers::Finding +ResolvedPeers::findPeer(const Comm::Connection ¤tPeer) +{ + const auto path = start(); + const auto foundNext = path != paths_.end() && + currentPeer.getPeer() != path->connection->getPeer(); + return makeFinding(path, foundNext); } Comm::ConnectionPointer ResolvedPeers::extractFront() { Must(!empty()); - return extractFound("first: ", paths_.begin()); + return extractFound("first: ", start()); } Comm::ConnectionPointer ResolvedPeers::extractPrime(const Comm::Connection ¤tPeer) { - if (!empty()) { - const auto peerToMatch = currentPeer.getPeer(); - const auto familyToMatch = ConnectionFamily(currentPeer); - const auto &conn = paths_.front(); - if (conn->getPeer() == peerToMatch && familyToMatch == ConnectionFamily(*conn)) - return extractFound("same-peer same-family match: ", paths_.begin()); - } + const auto found = findPrime(currentPeer).first; + if (found != paths_.end()) + return extractFound("same-peer same-family match: ", found); debugs(17, 7, "no same-peer same-family paths"); return nullptr; } -/// If spare paths exist for currentPeer, returns the first spare path iterator. -/// Otherwise, if there are paths for other peers, returns one of those. -/// Otherwise, returns the end() iterator. -Comm::ConnectionList::iterator -ResolvedPeers::findSpareOrNextPeer(const Comm::Connection ¤tPeer) -{ - const auto peerToMatch = currentPeer.getPeer(); - const auto familyToAvoid = ConnectionFamily(currentPeer); - // Optimization: Also stop at the first mismatching peer because all - // same-peer paths are grouped together. - return std::find_if(paths_.begin(), paths_.end(), - [peerToMatch, familyToAvoid](const Comm::ConnectionPointer &conn) { - return peerToMatch != conn->getPeer() || - familyToAvoid != ConnectionFamily(*conn); - }); -} - Comm::ConnectionPointer ResolvedPeers::extractSpare(const Comm::Connection ¤tPeer) { - auto found = findSpareOrNextPeer(currentPeer); - if (found != paths_.end() && currentPeer.getPeer() == (*found)->getPeer()) + const auto found = findSpare(currentPeer).first; + if (found != paths_.end()) return extractFound("same-peer different-family match: ", found); debugs(17, 7, "no same-peer different-family paths"); @@ -85,48 +143,58 @@ ResolvedPeers::extractSpare(const Comm::Connection ¤tPeer) /// convenience method to finish a successful extract*() call Comm::ConnectionPointer -ResolvedPeers::extractFound(const char *description, const Comm::ConnectionList::iterator &found) +ResolvedPeers::extractFound(const char *description, const Paths::iterator &found) { - const auto path = *found; - paths_.erase(found); - debugs(17, 7, description << path); - return path; + auto &path = *found; + debugs(17, 7, description << path.connection); + assert(path.available); + path.available = false; + decreaseAvailability(); + + // if we extracted the left-most available path, find the next one + if (static_cast(found - paths_.begin()) == pathsToSkip) { + while (++pathsToSkip < paths_.size() && !paths_[pathsToSkip].available) {} + } + + return path.connection; } bool ResolvedPeers::haveSpare(const Comm::Connection ¤tPeer) { - const auto found = findSpareOrNextPeer(currentPeer); - return found != paths_.end() && - currentPeer.getPeer() == (*found)->getPeer(); + return findSpare(currentPeer).first != paths_.end(); +} + +/// whether paths_ have no (and will have no) Xs for the current peer based on +/// the given findX(current peer) result +bool +ResolvedPeers::doneWith(const Finding &findings) const +{ + if (findings.first != paths_.end()) + return false; // not done because the caller found a viable path X + + // The caller did not find any path X. If the caller found any "other" + // paths, then we are done with paths X. If there are no "other" paths, + // then destinationsFinalized is the answer. + return findings.second ? true : destinationsFinalized; } bool ResolvedPeers::doneWithSpares(const Comm::Connection ¤tPeer) { - const auto found = findSpareOrNextPeer(currentPeer); - if (found == paths_.end()) - return destinationsFinalized; - return currentPeer.getPeer() != (*found)->getPeer(); + return doneWith(findSpare(currentPeer)); } bool -ResolvedPeers::doneWithPrimes(const Comm::Connection ¤tPeer) const +ResolvedPeers::doneWithPrimes(const Comm::Connection ¤tPeer) { - const auto first = paths_.begin(); - if (first == paths_.end()) - return destinationsFinalized; - return currentPeer.getPeer() != (*first)->getPeer() || - ConnectionFamily(currentPeer) != ConnectionFamily(**first); + return doneWith(findPrime(currentPeer)); } bool -ResolvedPeers::doneWithPeer(const Comm::Connection ¤tPeer) const +ResolvedPeers::doneWithPeer(const Comm::Connection ¤tPeer) { - const auto first = paths_.begin(); - if (first == paths_.end()) - return destinationsFinalized; - return currentPeer.getPeer() != (*first)->getPeer(); + return doneWith(findPeer(currentPeer)); } int @@ -135,6 +203,22 @@ ResolvedPeers::ConnectionFamily(const Comm::Connection &conn) return conn.remote.isIPv4() ? AF_INET : AF_INET6; } +/// increments the number of available paths +void +ResolvedPeers::increaseAvailability() +{ + ++availablePaths; + assert(availablePaths <= paths_.size()); +} + +/// decrements the number of available paths +void +ResolvedPeers::decreaseAvailability() +{ + assert(availablePaths > 0); + --availablePaths; +} + std::ostream & operator <<(std::ostream &os, const ResolvedPeers &peers) { diff --git a/src/ResolvedPeers.h b/src/ResolvedPeers.h index d585cd30c7..f438c7373f 100644 --- a/src/ResolvedPeers.h +++ b/src/ResolvedPeers.h @@ -13,6 +13,16 @@ #include "comm/forward.h" #include +#include + +class ResolvedPeerPath +{ +public: + explicit ResolvedPeerPath(const Comm::ConnectionPointer &conn) : connection(conn), available(true) {} + + Comm::ConnectionPointer connection; ///< (the address of) a path + bool available; ///< whether this path may be used (i.e., has not been tried already) +}; /// cache_peer and origin server addresses (a.k.a. paths) /// selected and resolved by the peering code @@ -21,17 +31,20 @@ class ResolvedPeers: public RefCountable MEMPROXY_CLASS(ResolvedPeers); public: + // ResolvedPeerPaths in addPath() call order + typedef std::vector Paths; + using size_type = Paths::size_type; typedef RefCount Pointer; ResolvedPeers(); /// whether we lack any known candidate paths - bool empty() const { return paths_.empty(); } + bool empty() const { return !availablePaths; } /// add a candidate path to try after all the existing paths void addPath(const Comm::ConnectionPointer &); - /// add a candidate path to try before all the existing paths + /// re-inserts the previously extracted address into the same position void retryPath(const Comm::ConnectionPointer &); /// extracts and returns the first queued address @@ -49,16 +62,16 @@ public: bool haveSpare(const Comm::Connection ¤tPeer); /// whether extractPrime() returns and will continue to return nil - bool doneWithPrimes(const Comm::Connection ¤tPeer) const; + bool doneWithPrimes(const Comm::Connection ¤tPeer); /// whether extractSpare() returns and will continue to return nil bool doneWithSpares(const Comm::Connection ¤tPeer); /// whether doneWithPrimes() and doneWithSpares() are true for currentPeer - bool doneWithPeer(const Comm::Connection ¤tPeer) const; + bool doneWithPeer(const Comm::Connection ¤tPeer); /// the current number of candidate paths - Comm::ConnectionList::size_type size() const { return paths_.size(); } + size_type size() const { return availablePaths; } /// whether all of the available candidate paths received from DNS bool destinationsFinalized = false; @@ -67,13 +80,34 @@ public: bool notificationPending = false; private: + /// A find*() result: An iterator of the found path (or paths_.end()) and + /// whether the "other" path was found instead. + typedef std::pair Finding; + /// The protocol family of the given path, AF_INET or AF_INET6 static int ConnectionFamily(const Comm::Connection &conn); - Comm::ConnectionList::iterator findSpareOrNextPeer(const Comm::Connection ¤tPeer); - Comm::ConnectionPointer extractFound(const char *description, const Comm::ConnectionList::iterator &found); + Paths::iterator start(); + Finding findSpare(const Comm::Connection ¤tPeer); + Finding findPrime(const Comm::Connection ¤tPeer); + Finding findPeer(const Comm::Connection ¤tPeer); + Comm::ConnectionPointer extractFound(const char *description, const Paths::iterator &found); + Finding makeFinding(const Paths::iterator &found, bool foundOther); + + bool doneWith(const Finding &findings) const; + + void increaseAvailability(); + void decreaseAvailability(); + + Paths paths_; ///< resolved addresses in (peer, family) order + + /// the number of leading paths_ elements that are all currently unavailable + /// i.e. the size of the front paths_ segment comprised of unavailable items + /// i.e. the position of the first available path (or paths_.size()) + size_type pathsToSkip = 0; - Comm::ConnectionList paths_; + /// the total number of currently available elements in paths_ + size_type availablePaths = 0; }; /// summarized ResolvedPeers (for debugging) diff --git a/src/comm/forward.h b/src/comm/forward.h index 20c459dd44..042b6da9c8 100644 --- a/src/comm/forward.h +++ b/src/comm/forward.h @@ -26,8 +26,6 @@ class ConnOpener; typedef RefCount ConnectionPointer; -typedef std::vector ConnectionList; - bool IsConnOpen(const Comm::ConnectionPointer &conn); // callback handler to process an FD which is available for writing. -- 2.39.5