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