OpenTTD Source  20241108-master-g80f628063a
linkgraphschedule.cpp
Go to the documentation of this file.
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 
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 
29 
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();
46  LinkGraphJob *job = new LinkGraphJob(*next);
47  job->SpawnThread();
48  this->running.push_back(job);
49  } else {
50  NOT_REACHED();
51  }
52 }
53 
59 {
60  if (this->running.empty()) return false;
61  const LinkGraphJob *next = this->running.front();
62  return next->IsScheduledToBeJoined() && !next->IsJobCompleted();
63 }
64 
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 
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 
112 {
113  for (auto &it : this->running) {
114  it->SpawnThread();
115  }
116 }
117 
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 
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 
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 
158 {
159  this->Clear();
160 }
161 
170 {
172  /* We are paused waiting on a job, check the job every tick. */
173  if (!LinkGraphSchedule::instance.IsJoinWithUnfinishedJobDue()) {
175  }
176  } else if (_pause_mode == PM_UNPAUSED &&
180  /* Perform check two TimerGameEconomy::date_fract ticks before we would join, to make
181  * sure it also works in multiplayer. */
183  }
184 }
185 
192 {
193  if (LinkGraphSchedule::instance.IsJoinWithUnfinishedJobDue()) {
195  }
196 }
197 
203 {
206  if (offset == 0) {
209  if (!_networking || _network_server) {
212  } else {
215  }
216  }
217 }
218 
219 
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:29
std::atomic< bool > job_completed
Is the job still running. This is accessed by multiple threads and reads may be stale.
Definition: linkgraphjob.h:168
LinkGraphID LinkGraphIndex() const
Get the ID of the underlying link graph.
Definition: linkgraphjob.h:263
bool IsJobAborted() const
Check if job has been aborted.
Definition: linkgraphjob.h:200
void SpawnThread()
Spawn a thread if possible and run the link graph job in the thread.
bool IsScheduledToBeJoined() const
Check if job is supposed to be finished.
Definition: linkgraphjob.h:214
bool IsJobCompleted() const
Check if job has actually finished.
Definition: linkgraphjob.h:193
LinkGraphSchedule()
Create a link graph schedule and initialize its handlers.
GraphList schedule
Queue for new jobs.
void SpawnNext()
Start the next job in the schedule.
static LinkGraphSchedule instance
Static instance of LinkGraphSchedule.
static void Clear()
Clear all link graphs and jobs from the schedule.
void ShiftDates(TimerGameEconomy::Date interval)
Shift all dates (join dates and edge annotations) of link graphs and link graph jobs by the number of...
~LinkGraphSchedule()
Delete a link graph schedule and its handlers.
bool IsJoinWithUnfinishedJobDue() const
Check if the next job is supposed to be finished, but has not yet completed.
static const uint SPAWN_JOIN_TICK
Tick when jobs are spawned or joined every day.
void Unqueue(LinkGraph *lg)
Remove a link graph from the execution queue.
void Queue(LinkGraph *lg)
Queue a link graph for execution.
static void Run(LinkGraphJob *job)
Run all handlers for the given Job.
void JoinNext()
Join the next finished job, if available.
std::array< std::unique_ptr< ComponentHandler >, 6 > handlers
Handlers to be run for each job.
JobList running
Currently running jobs.
void SpawnAll()
Start all threads in the running list.
A connected component of a link graph.
Definition: linkgraph.h:37
NodeID Size() const
Get the current size of the component.
Definition: linkgraph.h:230
RAII class for measuring simple elements of performance.
static void SetInactive(PerformanceElement elem)
Mark a performance element as not currently in use.
static constexpr int SECONDS_PER_DAY
approximate seconds per day, not for precise calculations
static Date date
Current date in days (day counter).
static DateFract date_fract
Fractional part of the day.
Declaration of demand calculating link graph handler.
Declaration of flow mapper; maps paths into flows at nodes.
@ PFE_GL_LINKGRAPH
Time spent waiting for link graph background jobs.
PauseMode _pause_mode
The current pause mode.
Definition: gfx.cpp:50
Declaration of initializing link graph handler.
void OnTick_LinkGraph()
Spawn or join a link graph job or compress a link graph if any link graph is due to do so.
void StateGameLoop_LinkGraphPauseControl()
Pause the game if in 2 TimerGameEconomy::date_fract ticks, we would do a join with the next link grap...
void AfterLoad_LinkGraphPauseControl()
Pause the game on load if we would do a join with the next link graph job, but it is still running,...
Declaration of link graph schedule used for cargo distribution.
Declaration of Multi-Commodity-Flow solver.
bool _networking
are we in networking mode?
Definition: network.cpp:65
bool _network_server
network-server is active
Definition: network.cpp:66
@ PM_UNPAUSED
A normal unpaused game.
Definition: openttd.h:69
@ PM_PAUSED_LINK_GRAPH
A game paused due to the link graph schedule lagging.
Definition: openttd.h:76
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:57
LinkGraphSettings linkgraph
settings for link graph calculations
uint16_t recalc_interval
time (in days) between subsequent checks for link graphs to be calculated.
Tindex index
Index of this pool item.
Definition: pool_type.hpp:238
static Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:339
static bool IsValidID(size_t index)
Tests whether given index can be used to get valid (non-nullptr) Titem.
Definition: pool_type.hpp:328
static bool CanAllocateItem(size_t n=1)
Helper functions so we can use PoolItem::Function() instead of _poolitem_pool.Function()
Definition: pool_type.hpp:309
static Pool::IterateWrapper< Titem > Iterate(size_t from=0)
Returns an iterable ensemble of all valid Titem.
Definition: pool_type.hpp:388