src/linkgraph/linkgraphschedule.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD 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, version 2.
   4  * OpenTTD 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.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file linkgraphschedule.cpp Definition of link graph schedule used for cargo distribution. */
   9
  10 #include "../stdafx.h"
  11 #include "linkgraphschedule.h"
  12 #include "init.h"
  13 #include "demands.h"
  14 #include "mcf.h"
  15 #include "flowmapper.h"
  16 #include "../framerate_type.h"
  17 #include "../command_func.h"
  18 #include "../network/network.h"
  19 #include "../misc_cmd.h"
  20
  21 #include "../safeguards.h"
  22
  23 /**
  24  * Static instance of LinkGraphSchedule.
  25  * Note: This instance is created on task start.
  26  *       Lazy creation on first usage results in a data race between the CDist threads.
  27  */
  28 /* static */ LinkGraphSchedule LinkGraphSchedule::instance;
  29
  30 /**
  31  * Start the next job in the schedule.
  32  */
  33 void LinkGraphSchedule::SpawnNext()
  34 {
  35         if (this->schedule.empty()) return;
  36         LinkGraph *next = this->schedule.front();
  37         LinkGraph *first = next;
  38         while (next->Size() < 2) {
  39                 this->schedule.splice(this->schedule.end(), this->schedule, this->schedule.begin());
  40                 next = this->schedule.front();
  41                 if (next == first) return;
  42         }
  43         assert(next == LinkGraph::Get(next->index));
  44         this->schedule.pop_front();
  45         if (LinkGraphJob::CanAllocateItem()) {
  46                 LinkGraphJob *job = new LinkGraphJob(*next);
  47                 job->SpawnThread();
  48                 this->running.push_back(job);
  49         } else {
  50                 NOT_REACHED();
  51         }
  52 }
  53
  54 /**
  55  * Check if the next job is supposed to be finished, but has not yet completed.
  56  * @return True if job should be finished by now but is still running, false if not.
  57  */
  58 bool LinkGraphSchedule::IsJoinWithUnfinishedJobDue() const
  59 {
  60         if (this->running.empty()) return false;
  61         const LinkGraphJob *next = this->running.front();
  62         return next->IsScheduledToBeJoined() && !next->IsJobCompleted();
  63 }
  64
  65 /**
  66  * Join the next finished job, if available.
  67  */
  68 void LinkGraphSchedule::JoinNext()
  69 {
  70         if (this->running.empty()) return;
  71         LinkGraphJob *next = this->running.front();
  72         if (!next->IsScheduledToBeJoined()) return;
  73         this->running.pop_front();
  74         LinkGraphID id = next->LinkGraphIndex();
  75         delete next; // implicitly joins the thread
  76         if (LinkGraph::IsValidID(id)) {
  77                 LinkGraph *lg = LinkGraph::Get(id);
  78                 this->Unqueue(lg); // Unqueue to avoid double-queueing recycled IDs.
  79                 this->Queue(lg);
  80         }
  81 }
  82
  83 /**
  84  * Run all handlers for the given Job.
  85  * @param job Pointer to a link graph job.
  86  */
  87 /* static */ void LinkGraphSchedule::Run(LinkGraphJob *job)
  88 {
  89         for (const auto &handler : instance.handlers) {
  90                 if (job->IsJobAborted()) return;
  91                 handler->Run(*job);
  92         }
  93
  94         /*
  95          * Readers of this variable in another thread may see an out of date value.
  96          * However this is OK as this will only happen just as a job is completing,
  97          * and the real synchronisation is provided by the thread join operation.
  98          * In the worst case the main thread will be paused for longer than
  99          * strictly necessary before joining.
 100          * This is just a hint variable to avoid performing the join excessively
 101          * early and blocking the main thread.
 102          */
 103
 104         job->job_completed.store(true, std::memory_order_release);
 105 }
 106
 107 /**
 108  * Start all threads in the running list. This is only useful for save/load.
 109  * Usually threads are started when the job is created.
 110  */
 111 void LinkGraphSchedule::SpawnAll()
 112 {
 113         for (auto &it : this->running) {
 114                 it->SpawnThread();
 115         }
 116 }
 117
 118 /**
 119  * Clear all link graphs and jobs from the schedule.
 120  */
 121 /* static */ void LinkGraphSchedule::Clear()
 122 {
 123         for (auto &it : instance.running) {
 124                 it->AbortJob();
 125         }
 126         instance.running.clear();
 127         instance.schedule.clear();
 128 }
 129
 130 /**
 131  * Shift all dates (join dates and edge annotations) of link graphs and link
 132  * graph jobs by the number of days given.
 133  * @param interval Number of days to be added or subtracted.
 134  */
 135 void LinkGraphSchedule::ShiftDates(TimerGameEconomy::Date interval)
 136 {
 137         for (LinkGraph *lg : LinkGraph::Iterate()) lg->ShiftDates(interval);
 138         for (LinkGraphJob *lgj : LinkGraphJob::Iterate()) lgj->ShiftJoinDate(interval);
 139 }
 140
 141 /**
 142  * Create a link graph schedule and initialize its handlers.
 143  */
 144 LinkGraphSchedule::LinkGraphSchedule()
 145 {
 146         this->handlers[0] = std::make_unique<InitHandler>();
 147         this->handlers[1] = std::make_unique<DemandHandler>();
 148         this->handlers[2] = std::make_unique<MCFHandler<MCF1stPass>>();
 149         this->handlers[3] = std::make_unique<FlowMapper>(false);
 150         this->handlers[4] = std::make_unique<MCFHandler<MCF2ndPass>>();
 151         this->handlers[5] = std::make_unique<FlowMapper>(true);
 152 }
 153
 154 /**
 155  * Delete a link graph schedule and its handlers.
 156  */
 157 LinkGraphSchedule::~LinkGraphSchedule()
 158 {
 159         this->Clear();
 160 }
 161
 162 /**
 163  * Pause the game if in 2 TimerGameEconomy::date_fract ticks, we would do a join with the next
 164  * link graph job, but it is still running.
 165  * The check is done 2 TimerGameEconomy::date_fract ticks early instead of 1, as in multiplayer
 166  * calls to DoCommandP are executed after a delay of 1 TimerGameEconomy::date_fract tick.
 167  * If we previously paused, unpause if the job is now ready to be joined with.
 168  */
 169 void StateGameLoop_LinkGraphPauseControl()
 170 {
 171         if (_pause_mode & PM_PAUSED_LINK_GRAPH) {
 172                 /* We are paused waiting on a job, check the job every tick. */
 173                 if (!LinkGraphSchedule::instance.IsJoinWithUnfinishedJobDue()) {
 174                         Command<CMD_PAUSE>::Post(PM_PAUSED_LINK_GRAPH, false);
 175                 }
 176         } else if (_pause_mode == PM_UNPAUSED &&
 177                         TimerGameEconomy::date_fract == LinkGraphSchedule::SPAWN_JOIN_TICK - 2 &&
 178                         TimerGameEconomy::date.base() % (_settings_game.linkgraph.recalc_interval / EconomyTime::SECONDS_PER_DAY) == (_settings_game.linkgraph.recalc_interval / EconomyTime::SECONDS_PER_DAY) / 2 &&
 179                         LinkGraphSchedule::instance.IsJoinWithUnfinishedJobDue()) {
 180                 /* Perform check two TimerGameEconomy::date_fract ticks before we would join, to make
 181                  * sure it also works in multiplayer. */
 182                 Command<CMD_PAUSE>::Post(PM_PAUSED_LINK_GRAPH, true);
 183         }
 184 }
 185
 186 /**
 187  * Pause the game on load if we would do a join with the next link graph job,
 188  * but it is still running, and it would not be caught by a call to
 189  * StateGameLoop_LinkGraphPauseControl().
 190  */
 191 void AfterLoad_LinkGraphPauseControl()
 192 {
 193         if (LinkGraphSchedule::instance.IsJoinWithUnfinishedJobDue()) {
 194                 _pause_mode |= PM_PAUSED_LINK_GRAPH;
 195         }
 196 }
 197
 198 /**
 199  * Spawn or join a link graph job or compress a link graph if any link graph is
 200  * due to do so.
 201  */
 202 void OnTick_LinkGraph()
 203 {
 204         if (TimerGameEconomy::date_fract != LinkGraphSchedule::SPAWN_JOIN_TICK) return;
 205         TimerGameEconomy::Date offset = TimerGameEconomy::date.base() % (_settings_game.linkgraph.recalc_interval / EconomyTime::SECONDS_PER_DAY);
 206         if (offset == 0) {
 207                 LinkGraphSchedule::instance.SpawnNext();
 208         } else if (offset == (_settings_game.linkgraph.recalc_interval / EconomyTime::SECONDS_PER_DAY) / 2) {
 209                 if (!_networking || _network_server) {
 210                         PerformanceMeasurer::SetInactive(PFE_GL_LINKGRAPH);
 211                         LinkGraphSchedule::instance.JoinNext();
 212                 } else {
 213                         PerformanceMeasurer framerate(PFE_GL_LINKGRAPH);
 214                         LinkGraphSchedule::instance.JoinNext();
 215                 }
 216         }
 217 }
 218
 219