src/HappyConnOpener.cc

   1 /*
   2  * Copyright (C) 1996-2023 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 #include "squid.h"
  10 #include "AccessLogEntry.h"
  11 #include "base/AsyncCallbacks.h"
  12 #include "base/CodeContext.h"
  13 #include "CachePeer.h"
  14 #include "errorpage.h"
  15 #include "FwdState.h"
  16 #include "HappyConnOpener.h"
  17 #include "HttpRequest.h"
  18 #include "ip/QosConfig.h"
  19 #include "neighbors.h"
  20 #include "pconn.h"
  21 #include "PeerPoolMgr.h"
  22 #include "sbuf/Stream.h"
  23 #include "SquidConfig.h"
  24
  25 CBDATA_CLASS_INIT(HappyConnOpener);
  26
  27 // HappyOrderEnforcer optimizes enforcement of the "pause before opening a spare
  28 // connection" requirements. Its inefficient alternative would add hundreds of
  29 // concurrent events to the Squid event queue in many busy configurations, one
  30 // concurrent event per concurrent HappyConnOpener job.
  31 //
  32 // EventScheduler::schedule() uses linear search to find the right place for a
  33 // new event; having hundreds of concurrent events is prohibitively expensive.
  34 // Both alternatives may have comparable high rate of eventAdd() calls, but
  35 // HappyOrderEnforcer usually schedules the first or second event (as opposed to
  36 // events that would be fired after hundreds of already scheduled events, making
  37 // that linear search a lot longer).
  38 //
  39 // EventScheduler::cancel() also uses linear search. HappyOrderEnforcer does not
  40 // need to cancel scheduled events, while its inefficient alternative may cancel
  41 // events at a rate comparable to the high eventAdd() rate -- many events would
  42 // be scheduled in vain because external factors would speed up (or make
  43 // unnecessary) spare connection attempts, canceling the wait.
  44 //
  45 // This optimization is possible only where each job needs to pause for the same
  46 // amount of time, creating a naturally ordered list of jobs waiting to be
  47 // resumed. This is why two HappyOrderEnforcers are needed to efficiently honor
  48 // both happy_eyeballs_connect_timeout and happy_eyeballs_connect_gap
  49 // directives.
  50
  51 /// Efficiently drains a FIFO HappyConnOpener queue while delaying each "pop"
  52 /// event by the time determined by the top element currently in the queue. Its
  53 /// current cbdata-free implementation assumes static storage duration.
  54 class HappyOrderEnforcer
  55 {
  56 public:
  57     /// \param aName names scheduled events, for debugging
  58     HappyOrderEnforcer(const char *aName): name(aName) {}
  59
  60     /// resumes jobs that need resuming (if any)
  61     void checkpoint();
  62
  63     /// starts managing the job's wait; the job should expect a call back
  64     void enqueue(HappyConnOpener &);
  65
  66     /// stops managing the job's wait; cancels the pending callback, if any
  67     void dequeue(HappyConnOpener &);
  68
  69     const char * const name; ///< waiting event name, for debugging
  70
  71 protected:
  72     virtual bool readyNow(const HappyConnOpener &) const = 0;
  73     virtual AsyncCall::Pointer notify(const CbcPointer<HappyConnOpener> &) = 0;
  74
  75     bool waiting() const { return waitEnd_ > 0; }
  76     bool startedWaiting(const HappyAbsoluteTime lastStart, const int cfgTimeoutMsec) const;
  77
  78 private:
  79     static void NoteWaitOver(void *raw);
  80     void noteWaitOver();
  81
  82     HappySpareWaitList jobs_; ///< queued jobs waiting their turn
  83     mutable HappyAbsoluteTime waitEnd_ = 0; ///< expected NoteWaitOver() call time (or zero)
  84 };
  85
  86 std::ostream &operator <<(std::ostream &os, const HappyConnOpenerAnswer &answer)
  87 {
  88     if (answer.error.set())
  89         os << "bad ";
  90     if (answer.conn)
  91         os << (answer.reused ? "reused " : "new ") << answer.conn;
  92     if (answer.n_tries != 1)
  93         os << " after " << answer.n_tries;
  94     return os;
  95 }
  96
  97 /// enforces happy_eyeballs_connect_timeout
  98 class PrimeChanceGiver: public HappyOrderEnforcer
  99 {
 100 public:
 101     PrimeChanceGiver(): HappyOrderEnforcer("happy_eyeballs_connect_timeout enforcement") {}
 102
 103     /* HappyOrderEnforcer API */
 104     bool readyNow(const HappyConnOpener &job) const override;
 105
 106 private:
 107     /* HappyOrderEnforcer API */
 108     AsyncCall::Pointer notify(const CbcPointer<HappyConnOpener> &) override;
 109 };
 110
 111 /// enforces happy_eyeballs_connect_gap and happy_eyeballs_connect_limit
 112 class SpareAllowanceGiver: public HappyOrderEnforcer
 113 {
 114 public:
 115     SpareAllowanceGiver(): HappyOrderEnforcer("happy_eyeballs_connect_gap/happy_eyeballs_connect_limit enforcement") {}
 116
 117     /* HappyOrderEnforcer API */
 118     bool readyNow(const HappyConnOpener &job) const override;
 119
 120     /// reacts to HappyConnOpener discovering readyNow() conditions for a spare path
 121     /// the caller must attempt to open a spare connection immediately
 122     void jobGotInstantAllowance();
 123
 124     /// reacts to HappyConnOpener getting a spare connection opening result
 125     void jobUsedAllowance();
 126
 127     /// reacts to HappyConnOpener dropping its spare connection allowance
 128     void jobDroppedAllowance();
 129
 130 private:
 131     /* HappyOrderEnforcer API */
 132     AsyncCall::Pointer notify(const CbcPointer<HappyConnOpener> &) override;
 133
 134     bool concurrencyLimitReached() const;
 135     void recordAllowance();
 136     void forgetAllowance();
 137
 138     /// the time of the last noteSpareAllowance() call
 139     HappyAbsoluteTime lastAllowanceStart = 0;
 140
 141     /// the number of noteSpareAllowance() calls not already
 142     /// returned via jobUsedAllowance() or jobDroppedAllowance()
 143     int concurrencyLevel = 0;
 144 };
 145
 146 PrimeChanceGiver ThePrimeChanceGiver;
 147 SpareAllowanceGiver TheSpareAllowanceGiver;
 148
 149 /* HappyOrderEnforcer */
 150
 151 void
 152 HappyOrderEnforcer::enqueue(HappyConnOpener &job)
 153 {
 154     Must(!job.spareWaiting.callback);
 155     jobs_.emplace_back(&job);
 156     job.spareWaiting.position = std::prev(jobs_.end());
 157     job.spareWaiting.codeContext = CodeContext::Current();
 158 }
 159
 160 void
 161 HappyOrderEnforcer::dequeue(HappyConnOpener &job)
 162 {
 163     if (job.spareWaiting.callback) {
 164         job.spareWaiting.callback->cancel("HappyOrderEnforcer::dequeue");
 165         job.spareWaiting.callback = nullptr;
 166     } else {
 167         Must(!jobs_.empty());
 168         jobs_.erase(job.spareWaiting.position);
 169     }
 170 }
 171
 172 void
 173 HappyOrderEnforcer::checkpoint()
 174 {
 175     while (!jobs_.empty()) {
 176         if (const auto jobPtr = jobs_.front().valid()) {
 177             auto &job = *jobPtr;
 178             if (!readyNow(job))
 179                 break; // the next job cannot be ready earlier (FIFO)
 180             CallBack(job.spareWaiting.codeContext, [&] {
 181                 job.spareWaiting.callback = notify(jobPtr); // and fall through to the next job
 182             });
 183         }
 184         jobs_.pop_front();
 185     }
 186 }
 187
 188 bool
 189 HappyOrderEnforcer::startedWaiting(const HappyAbsoluteTime lastStart, const int cfgTimeoutMsec) const
 190 {
 191     // Normally, the job would not even be queued if there is no timeout. This
 192     // check handles reconfiguration that happened after this job was queued.
 193     if (cfgTimeoutMsec <= 0)
 194         return false;
 195
 196     // convert to seconds and adjust for SMP workers to keep aggregated load in
 197     // check despite the lack of coordination among workers
 198     const auto tout = static_cast<HappyAbsoluteTime>(cfgTimeoutMsec) * Config.workers / 1000.0;
 199     const auto newWaitEnd = std::min(lastStart, current_dtime) + tout;
 200     if (newWaitEnd <= current_dtime)
 201         return false; // no need to wait
 202
 203     // We cannot avoid event accumulation because calling eventDelete() is
 204     // unsafe, but any accumulation will be small because it can only be caused
 205     // by hot reconfiguration changes or current time jumps.
 206     if (!waiting() || newWaitEnd < waitEnd_) {
 207         const auto waitTime = newWaitEnd - current_dtime;
 208         eventAdd(name, &HappyOrderEnforcer::NoteWaitOver, const_cast<HappyOrderEnforcer*>(this), waitTime, 0, false);
 209         waitEnd_ = newWaitEnd;
 210         assert(waiting());
 211     }
 212
 213     return true;
 214 }
 215
 216 void
 217 HappyOrderEnforcer::NoteWaitOver(void *raw)
 218 {
 219     assert(raw);
 220     static_cast<HappyOrderEnforcer*>(raw)->noteWaitOver();
 221 }
 222
 223 void
 224 HappyOrderEnforcer::noteWaitOver()
 225 {
 226     Must(waiting());
 227     waitEnd_ = 0;
 228     checkpoint();
 229 }
 230
 231 /* PrimeChanceGiver */
 232
 233 bool
 234 PrimeChanceGiver::readyNow(const HappyConnOpener &job) const
 235 {
 236     return !startedWaiting(job.primeStart, Config.happyEyeballs.connect_timeout);
 237 }
 238
 239 AsyncCall::Pointer
 240 PrimeChanceGiver::notify(const CbcPointer<HappyConnOpener> &job)
 241 {
 242     return CallJobHere(17, 5, job, HappyConnOpener, noteGavePrimeItsChance);
 243 }
 244
 245 /* SpareAllowanceGiver */
 246
 247 bool
 248 SpareAllowanceGiver::readyNow(const HappyConnOpener &) const
 249 {
 250     return !concurrencyLimitReached() &&
 251            !startedWaiting(lastAllowanceStart, Config.happyEyeballs.connect_gap);
 252 }
 253
 254 AsyncCall::Pointer
 255 SpareAllowanceGiver::notify(const CbcPointer<HappyConnOpener> &job)
 256 {
 257     recordAllowance();
 258     return CallJobHere(17, 5, job, HappyConnOpener, noteSpareAllowance);
 259 }
 260
 261 void
 262 SpareAllowanceGiver::jobGotInstantAllowance()
 263 {
 264     recordAllowance();
 265 }
 266
 267 void
 268 SpareAllowanceGiver::jobUsedAllowance()
 269 {
 270     forgetAllowance();
 271 }
 272
 273 void
 274 SpareAllowanceGiver::jobDroppedAllowance()
 275 {
 276     // Without happy_eyeballs_connect_gap, lastAllowanceStart does not matter.
 277     // Otherwise, the dropped allowance ought to be the last one, and since it
 278     // was allowed, we would still observe the gap even if we do not wait now.
 279     lastAllowanceStart = 0;
 280
 281     forgetAllowance();
 282 }
 283
 284 /// account for the given allowance
 285 void
 286 SpareAllowanceGiver::recordAllowance()
 287 {
 288     ++concurrencyLevel;
 289     lastAllowanceStart = current_dtime;
 290     // not a checkpoint(): no other spare can become ready here
 291 }
 292
 293 void
 294 SpareAllowanceGiver::forgetAllowance()
 295 {
 296     Must(concurrencyLevel);
 297     --concurrencyLevel;
 298     checkpoint();
 299 }
 300
 301 /// whether opening a spare connection now would violate happy_eyeballs_connect_limit
 302 bool
 303 SpareAllowanceGiver::concurrencyLimitReached() const
 304 {
 305     if (Config.happyEyeballs.connect_limit < 0)
 306         return false; // no limit
 307
 308     if (Config.happyEyeballs.connect_limit == 0)
 309         return true; // concurrent spares prohibited regardless of spare level
 310
 311     // adjust for SMP workers to keep aggregated spare level in check despite
 312     // the lack of coordination among workers
 313     const auto aggregateLevel = concurrencyLevel * Config.workers;
 314     return aggregateLevel >= Config.happyEyeballs.connect_limit;
 315 }
 316
 317 /* HappyConnOpenerAnswer */
 318
 319 HappyConnOpenerAnswer::~HappyConnOpenerAnswer()
 320 {
 321     // XXX: When multiple copies of an answer exist, this delete in one copy
 322     // invalidates error in other copies -- their error.get() returns nil. The
 323     // current code "works", but probably only because the initiator gets the
 324     // error before any answer copies are deleted. Same in ~EncryptorAnswer.
 325     delete error.get();
 326 }
 327
 328 /* HappyConnOpener */
 329
 330 HappyConnOpener::HappyConnOpener(const ResolvedPeers::Pointer &dests, const AsyncCallback<Answer> &callback, const HttpRequest::Pointer &request, const time_t aFwdStart, const int tries, const AccessLogEntry::Pointer &anAle):
 331     AsyncJob("HappyConnOpener"),
 332     fwdStart(aFwdStart),
 333     callback_(callback),
 334     destinations(dests),
 335     prime(&HappyConnOpener::notePrimeConnectDone, "HappyConnOpener::notePrimeConnectDone"),
 336     spare(&HappyConnOpener::noteSpareConnectDone, "HappyConnOpener::noteSpareConnectDone"),
 337     ale(anAle),
 338     cause(request),
 339     n_tries(tries)
 340 {
 341     assert(destinations);
 342 }
 343
 344 HappyConnOpener::~HappyConnOpener()
 345 {
 346     safe_free(host_);
 347     delete lastError;
 348 }
 349
 350 void
 351 HappyConnOpener::setHost(const char *h)
 352 {
 353     safe_free(host_);
 354     if (h)
 355         host_ = xstrdup(h);
 356 }
 357
 358 void
 359 HappyConnOpener::start()
 360 {
 361     destinations->notificationPending = false;
 362     checkForNewConnection();
 363 }
 364
 365 bool
 366 HappyConnOpener::doneAll() const
 367 {
 368     if (!callback_)
 369         return true; // (probably found a good path and) informed the requestor
 370
 371     // TODO: Expose AsyncCall::canFire() instead so that code like this can
 372     // detect gone initiators without the need to explicitly cancel callbacks.
 373     if (callback_->canceled())
 374         return true; // the requestor is gone or has lost interest
 375
 376     if (prime || spare)
 377         return false;
 378
 379     if (ranOutOfTimeOrAttempts())
 380         return true; // trying new connection paths prohibited
 381
 382     if (destinations->empty() && destinations->destinationsFinalized)
 383         return true; // there are no more paths to try
 384
 385     return false;
 386 }
 387
 388 void
 389 HappyConnOpener::swanSong()
 390 {
 391     debugs(17, 5, this);
 392
 393     if (callback_ && !callback_->canceled())
 394         sendFailure();
 395
 396     if (spareWaiting)
 397         cancelSpareWait("HappyConnOpener object destructed");
 398
 399     // TODO: Find an automated, faster way to kill no-longer-needed jobs.
 400
 401     if (prime) {
 402         cancelAttempt(prime, "job finished during a prime attempt");
 403     }
 404
 405     if (spare) {
 406         cancelAttempt(spare, "job finished during a spare attempt");
 407         if (gotSpareAllowance) {
 408             TheSpareAllowanceGiver.jobDroppedAllowance();
 409             gotSpareAllowance = false;
 410         }
 411     }
 412
 413     AsyncJob::swanSong();
 414 }
 415
 416 /// HappyConnOpener::Attempt printer for debugging
 417 std::ostream &
 418 operator <<(std::ostream &os, const HappyConnOpener::Attempt &attempt)
 419 {
 420     if (!attempt.path)
 421         os << '-';
 422     else if (attempt.path->isOpen())
 423         os << "FD " << attempt.path->fd;
 424     else if (attempt.connWait)
 425         os << attempt.connWait;
 426     else // destination is known; connection closed (and we are not opening any)
 427         os << attempt.path->id;
 428     return os;
 429 }
 430
 431 const char *
 432 HappyConnOpener::status() const
 433 {
 434     // TODO: In a redesigned status() API, the caller may mimic this approach.
 435     static SBuf buf;
 436     buf.clear();
 437
 438     SBufStream os(buf);
 439
 440     os.write(" [", 2);
 441     if (stopReason)
 442         os << "Stopped:" << stopReason;
 443     if (prime)
 444         os << "prime:" << prime;
 445     if (spare)
 446         os << "spare:" << spare;
 447     if (n_tries)
 448         os << " tries:" << n_tries;
 449     os << " dst:" << *destinations;
 450     os << ' ' << id << ']';
 451
 452     buf = os.buf();
 453     return buf.c_str();
 454 }
 455
 456 /**
 457  * Create "503 Service Unavailable" or "504 Gateway Timeout" error depending
 458  * on whether this is a validation request.
 459  *
 460  * RFC 9111 section 5.2.2 Cache-Control response directives
 461  *
 462  * section 5.2.2.2 must-revalidate
 463  * " if a cache is disconnected, the cache MUST generate an error response
 464  *   rather than reuse the stale response.  The generated status code
 465  *   SHOULD be 504 (Gateway Timeout) unless another error status code is
 466  *   more applicable."
 467  *
 468  * section 5.2.2.8 proxy-revalidate
 469  * " analogous to must-revalidate "
 470  *
 471  * section 5.2.2.10 s-maxage
 472  * " incorporates the semantics of the
 473  *   proxy-revalidate response directive "
 474  */
 475 ErrorState *
 476 HappyConnOpener::makeError(const err_type type) const
 477 {
 478     const auto statusCode = cause->flags.needValidation ?
 479                             Http::scGatewayTimeout : Http::scServiceUnavailable;
 480     return new ErrorState(type, statusCode, cause.getRaw(), ale);
 481 }
 482
 483 /// \returns pre-filled Answer if the initiator needs an answer (or nil)
 484 HappyConnOpener::Answer *
 485 HappyConnOpener::futureAnswer(const PeerConnectionPointer &conn)
 486 {
 487     if (callback_ && !callback_->canceled()) {
 488         auto &answer = callback_.answer();
 489         answer.conn = conn;
 490         answer.n_tries = n_tries;
 491         return &answer;
 492     }
 493     (void)callback_.release();
 494     return nullptr;
 495 }
 496
 497 /// send a successful result to the initiator (if it still needs an answer)
 498 void
 499 HappyConnOpener::sendSuccess(const PeerConnectionPointer &conn, const bool reused, const char *connKind)
 500 {
 501     debugs(17, 4, connKind << ": " << conn);
 502     if (auto *answer = futureAnswer(conn)) {
 503         answer->reused = reused;
 504         assert(!answer->error);
 505         ScheduleCallHere(callback_.release());
 506     }
 507 }
 508
 509 /// cancels the in-progress attempt, making its path a future candidate
 510 void
 511 HappyConnOpener::cancelAttempt(Attempt &attempt, const char *reason)
 512 {
 513     Must(attempt);
 514     destinations->reinstatePath(attempt.path); // before attempt.cancel() clears path
 515     attempt.cancel(reason);
 516 }
 517
 518 /// inform the initiator about our failure to connect (if needed)
 519 void
 520 HappyConnOpener::sendFailure()
 521 {
 522     debugs(17, 3, lastFailedConnection);
 523     if (auto *answer = futureAnswer(lastFailedConnection)) {
 524         if (!lastError)
 525             lastError = makeError(ERR_GATEWAY_FAILURE);
 526         answer->error = lastError;
 527         assert(answer->error.valid());
 528         lastError = nullptr; // the answer owns it now
 529         ScheduleCallHere(callback_.release());
 530     }
 531 }
 532
 533 void
 534 HappyConnOpener::noteCandidatesChange()
 535 {
 536     destinations->notificationPending = false;
 537     checkForNewConnection();
 538 }
 539
 540 /// starts opening (or reusing) a connection to the given destination
 541 void
 542 HappyConnOpener::startConnecting(Attempt &attempt, PeerConnectionPointer &dest)
 543 {
 544     Must(!attempt.path);
 545     Must(!attempt.connWait);
 546     Must(dest);
 547
 548     const auto bumpThroughPeer = cause->flags.sslBumped && dest->getPeer();
 549     const auto canReuseOld = allowPconn_ && !bumpThroughPeer;
 550     if (!canReuseOld || !reuseOldConnection(dest))
 551         openFreshConnection(attempt, dest);
 552 }
 553
 554 /// reuses a persistent connection to the given destination (if possible)
 555 /// \returns true if and only if reuse was possible
 556 /// must be called via startConnecting()
 557 bool
 558 HappyConnOpener::reuseOldConnection(PeerConnectionPointer &dest)
 559 {
 560     assert(allowPconn_);
 561
 562     if (const auto pconn = fwdPconnPool->pop(dest, host_, retriable_)) {
 563         ++n_tries;
 564         dest.finalize(pconn);
 565         sendSuccess(dest, true, "reused connection");
 566         return true;
 567     }
 568
 569     return false;
 570 }
 571
 572 /// opens a fresh connection to the given destination
 573 /// must be called via startConnecting()
 574 void
 575 HappyConnOpener::openFreshConnection(Attempt &attempt, PeerConnectionPointer &dest)
 576 {
 577 #if URL_CHECKSUM_DEBUG
 578     entry->mem_obj->checkUrlChecksum();
 579 #endif
 580
 581     const auto conn = dest->cloneProfile();
 582     GetMarkingsToServer(cause.getRaw(), *conn);
 583
 584     typedef CommCbMemFunT<HappyConnOpener, CommConnectCbParams> Dialer;
 585     AsyncCall::Pointer callConnect = asyncCall(48, 5, attempt.callbackMethodName,
 586                                      Dialer(this, attempt.callbackMethod));
 587     const time_t connTimeout = dest->connectTimeout(fwdStart);
 588     auto cs = new Comm::ConnOpener(conn, callConnect, connTimeout);
 589     if (!conn->getPeer())
 590         cs->setHost(host_);
 591
 592     attempt.path = dest; // but not the being-opened conn!
 593     attempt.connWait.start(cs, callConnect);
 594 }
 595
 596 /// Comm::ConnOpener callback for the prime connection attempt
 597 void
 598 HappyConnOpener::notePrimeConnectDone(const CommConnectCbParams &params)
 599 {
 600     handleConnOpenerAnswer(prime, params, "new prime connection");
 601 }
 602
 603 /// Comm::ConnOpener callback for the spare connection attempt
 604 void
 605 HappyConnOpener::noteSpareConnectDone(const CommConnectCbParams &params)
 606 {
 607     if (gotSpareAllowance) {
 608         TheSpareAllowanceGiver.jobUsedAllowance();
 609         gotSpareAllowance = false;
 610     }
 611     handleConnOpenerAnswer(spare, params, "new spare connection");
 612 }
 613
 614 /// prime/spare-agnostic processing of a Comm::ConnOpener result
 615 void
 616 HappyConnOpener::handleConnOpenerAnswer(Attempt &attempt, const CommConnectCbParams &params, const char *what)
 617 {
 618     Must(params.conn);
 619
 620     // finalize the previously selected path before attempt.finish() forgets it
 621     auto handledPath = attempt.path;
 622     handledPath.finalize(params.conn); // closed on errors
 623     attempt.finish();
 624
 625     ++n_tries;
 626
 627     if (params.flag == Comm::OK) {
 628         sendSuccess(handledPath, false, what);
 629         return;
 630     }
 631
 632     debugs(17, 8, what << " failed: " << params.conn);
 633
 634     // remember the last failure (we forward it if we cannot connect anywhere)
 635     lastFailedConnection = handledPath;
 636     delete lastError;
 637     lastError = nullptr; // in case makeError() throws
 638     lastError = makeError(ERR_CONNECT_FAIL);
 639     lastError->xerrno = params.xerrno;
 640
 641     NoteOutgoingConnectionFailure(params.conn->getPeer(), lastError->httpStatus);
 642
 643     if (spareWaiting)
 644         updateSpareWaitAfterPrimeFailure();
 645
 646     checkForNewConnection();
 647 }
 648
 649 /// reacts to a prime attempt failure
 650 void
 651 HappyConnOpener::updateSpareWaitAfterPrimeFailure()
 652 {
 653     Must(currentPeer);
 654     Must(!prime);
 655     Must(spareWaiting);
 656
 657     if (destinations->doneWithPrimes(*currentPeer)) {
 658         cancelSpareWait("all primes failed");
 659         ignoreSpareRestrictions = true;
 660         return; // checkForNewConnection() will open a spare connection ASAP
 661     }
 662
 663     if (spareWaiting.toGivePrimeItsChance)
 664         stopGivingPrimeItsChance();
 665
 666     // may still be spareWaiting.forSpareAllowance or
 667     // may still be spareWaiting.forPrimesToFail
 668 }
 669
 670 /// called when the prime attempt has used up its chance for a solo victory
 671 void
 672 HappyConnOpener::stopGivingPrimeItsChance() {
 673     Must(spareWaiting.toGivePrimeItsChance);
 674     spareWaiting.toGivePrimeItsChance = false;
 675     ThePrimeChanceGiver.dequeue(*this);
 676 }
 677
 678 /// called when the spare attempt should no longer obey spare connection limits
 679 void
 680 HappyConnOpener::stopWaitingForSpareAllowance() {
 681     Must(spareWaiting.forSpareAllowance);
 682     spareWaiting.forSpareAllowance = false;
 683
 684     if (spareWaiting.callback)
 685         TheSpareAllowanceGiver.jobDroppedAllowance();
 686     TheSpareAllowanceGiver.dequeue(*this); // clears spareWaiting.callback
 687 }
 688
 689 /// stops waiting for the right conditions to open a spare connection
 690 void
 691 HappyConnOpener::cancelSpareWait(const char *reason)
 692 {
 693     debugs(17, 5, "because " << reason);
 694     Must(spareWaiting);
 695
 696     if (spareWaiting.toGivePrimeItsChance)
 697         stopGivingPrimeItsChance();
 698     else if (spareWaiting.forSpareAllowance)
 699         stopWaitingForSpareAllowance();
 700
 701     spareWaiting.clear();
 702 }
 703
 704 /** Called when an external event changes initiator interest, destinations,
 705  * prime, spare, or spareWaiting. Leaves HappyConnOpener in one of these
 706  * mutually exclusive "stable" states:
 707  *
 708  * 1. Processing a single peer: currentPeer && !done()
 709  *    1.1. Connecting: prime || spare
 710  *    1.2. Waiting for spare gap and/or paths: !prime && !spare
 711  * 2. Waiting for a new peer: destinations->empty() && !destinations->destinationsFinalized && !currentPeer && !done()
 712  * 3. Terminating: done()
 713  */
 714 void
 715 HappyConnOpener::checkForNewConnection()
 716 {
 717     debugs(17, 7, *destinations);
 718
 719     // The order of the top-level if-statements below is important.
 720
 721     if (done())
 722         return; // bail ASAP to minimize our waste and others delays (state #0)
 723
 724     if (ranOutOfTimeOrAttempts()) {
 725         Must(currentPeer); // or we would be done() already
 726         return; // will continue working (state #1.1)
 727     }
 728
 729     // update stale currentPeer and/or stale spareWaiting
 730     if (currentPeer && !spare && !prime && destinations->doneWithPeer(*currentPeer)) {
 731         debugs(17, 7, "done with peer; " << *currentPeer);
 732         if (spareWaiting.forNewPeer)
 733             cancelSpareWait("done with peer");
 734         else
 735             Must(!spareWaiting);
 736
 737         currentPeer = nullptr;
 738         ignoreSpareRestrictions = false;
 739         Must(!gotSpareAllowance);
 740     } else if (currentPeer && !spareWaiting.forNewPeer && spareWaiting && destinations->doneWithSpares(*currentPeer)) {
 741         cancelSpareWait("no spares are coming");
 742         spareWaiting.forNewPeer = true;
 743     }
 744
 745     if (!prime)
 746         maybeOpenPrimeConnection();
 747
 748     if (!spare && !done())
 749         maybeOpenSpareConnection();
 750
 751     // any state is possible at this point
 752 }
 753
 754 void
 755 HappyConnOpener::noteGavePrimeItsChance()
 756 {
 757     Must(spareWaiting.toGivePrimeItsChance);
 758     spareWaiting.clear();
 759     checkForNewConnection();
 760 }
 761
 762 void
 763 HappyConnOpener::noteSpareAllowance()
 764 {
 765     Must(spareWaiting.forSpareAllowance);
 766     spareWaiting.clear();
 767
 768     if (ranOutOfTimeOrAttempts()) {
 769         TheSpareAllowanceGiver.jobDroppedAllowance();
 770         return; // will quit or continue working on prime
 771     }
 772
 773     Must(!gotSpareAllowance);
 774     gotSpareAllowance = true;
 775
 776     auto dest = destinations->extractSpare(*currentPeer); // ought to succeed
 777     startConnecting(spare, dest);
 778 }
 779
 780 /// starts a prime connection attempt if possible or does nothing otherwise
 781 void
 782 HappyConnOpener::maybeOpenPrimeConnection()
 783 {
 784     Must(!prime);
 785
 786     if (destinations->empty())
 787         return;
 788
 789     if (!currentPeer) {
 790         auto newPrime = destinations->extractFront();
 791         currentPeer = newPrime;
 792         Must(currentPeer);
 793         debugs(17, 7, "new peer " << *currentPeer);
 794         primeStart = current_dtime;
 795         startConnecting(prime, newPrime);
 796         if (done()) // probably reused a pconn
 797             return;
 798
 799         Must(prime);
 800         maybeGivePrimeItsChance();
 801         return;
 802     }
 803
 804     // currentPeer implies there is a spare attempt; meanwhile, the previous
 805     // primary attempt has failed; do another attempt on the primary track
 806     if (auto dest = destinations->extractPrime(*currentPeer))
 807         startConnecting(prime, dest);
 808     // else wait for more prime paths or their exhaustion
 809 }
 810
 811 /// starts waiting for a spare permission (if spare connections may be possible)
 812 /// or does nothing (otherwise)
 813 void
 814 HappyConnOpener::maybeGivePrimeItsChance()
 815 {
 816     Must(currentPeer);
 817     Must(prime);
 818     Must(!spare);
 819     Must(!spareWaiting);
 820
 821     if (destinations->doneWithSpares(*currentPeer)) {
 822         debugs(17, 7, "no spares for " << *currentPeer);
 823         spareWaiting.forNewPeer = true;
 824         return;
 825     }
 826
 827     if (Config.happyEyeballs.connect_limit == 0) {
 828         debugs(17, 7, "concurrent spares are prohibited");
 829         spareWaiting.forPrimesToFail = true;
 830         return;
 831     }
 832
 833     if (ThePrimeChanceGiver.readyNow(*this)) {
 834         debugs(17, 7, "no happy_eyeballs_connect_timeout");
 835         return;
 836     }
 837
 838     ThePrimeChanceGiver.enqueue(*this);
 839     spareWaiting.toGivePrimeItsChance = true;
 840     // wait for a prime connect result or noteGavePrimeItsChance()
 841 }
 842
 843 /// if possible, starts a spare connection attempt
 844 void
 845 HappyConnOpener::maybeOpenSpareConnection()
 846 {
 847     Must(currentPeer);
 848     Must(!spare);
 849     Must(!gotSpareAllowance);
 850
 851     if (spareWaiting)
 852         return; // too early
 853
 854     if (ranOutOfTimeOrAttempts())
 855         return; // too late
 856
 857     if (destinations->empty())
 858         return;
 859
 860     // jobGotInstantAllowance() call conditions below rely on the readyNow() check here
 861     if (!ignoreSpareRestrictions && // we have to honor spare restrictions
 862             !TheSpareAllowanceGiver.readyNow(*this) && // all new spares must wait
 863             destinations->haveSpare(*currentPeer)) { // and we do have a new spare
 864         TheSpareAllowanceGiver.enqueue(*this);
 865         spareWaiting.forSpareAllowance = true;
 866         return;
 867     }
 868
 869     if (auto dest = destinations->extractSpare(*currentPeer)) {
 870
 871         if (!ignoreSpareRestrictions) {
 872             TheSpareAllowanceGiver.jobGotInstantAllowance();
 873             gotSpareAllowance = true;
 874         }
 875
 876         startConnecting(spare, dest);
 877         return;
 878     }
 879
 880     // wait for more spare paths or their exhaustion
 881 }
 882
 883 /// Check for maximum connection tries and forwarding time restrictions
 884 bool
 885 HappyConnOpener::ranOutOfTimeOrAttempts() const
 886 {
 887     if (ranOutOfTimeOrAttemptsEarlier_)
 888         return true;
 889
 890     if (n_tries >= Config.forward_max_tries) {
 891         debugs(17, 5, "maximum allowed tries exhausted");
 892         ranOutOfTimeOrAttemptsEarlier_ = "maximum tries";
 893         return true;
 894     }
 895
 896     if (FwdState::ForwardTimeout(fwdStart) <= 0) {
 897         debugs(17, 5, "forwarding timeout");
 898         ranOutOfTimeOrAttemptsEarlier_ = "forwarding timeout";
 899         return true;
 900     }
 901
 902     return false;
 903 }
 904
 905 HappyConnOpener::Attempt::Attempt(const CallbackMethod method, const char *methodName):
 906     callbackMethod(method),
 907     callbackMethodName(methodName)
 908 {
 909 }
 910
 911 void
 912 HappyConnOpener::Attempt::finish()
 913 {
 914     connWait.finish();
 915     path = nullptr;
 916 }
 917
 918 void
 919 HappyConnOpener::Attempt::cancel(const char *reason)
 920 {
 921     connWait.cancel(reason);
 922     path = nullptr;
 923 }
 924