File : s-bbthqu.ads
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT RUN-TIME LIBRARY (GNARL) COMPONENTS --
4 -- --
5 -- S Y S T E M . B B . T H R E A D S . Q U E U E S --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 1999-2002 Universidad Politecnica de Madrid --
10 -- Copyright (C) 2003-2004 The European Space Agency --
11 -- Copyright (C) 2003-2016, AdaCore --
12 -- --
13 -- GNARL is free software; you can redistribute it and/or modify it under --
14 -- terms of the GNU General Public License as published by the Free Soft- --
15 -- ware Foundation; either version 3, or (at your option) any later ver- --
16 -- sion. GNARL is distributed in the hope that it will be useful, but WITH- --
17 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
18 -- or FITNESS FOR A PARTICULAR PURPOSE. --
19 -- --
20 -- --
21 -- --
22 -- --
23 -- --
24 -- You should have received a copy of the GNU General Public License and --
25 -- a copy of the GCC Runtime Library Exception along with this program; --
26 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
27 -- <http://www.gnu.org/licenses/>. --
28 -- --
29 -- GNARL was developed by the GNARL team at Florida State University. --
30 -- Extensive contributions were provided by Ada Core Technologies, Inc. --
31 -- --
32 -- The port of GNARL to bare board targets was initially developed by the --
33 -- Real-Time Systems Group at the Technical University of Madrid. --
34 -- --
35 ------------------------------------------------------------------------------
36
37 with System.BB.Time;
38 with System.BB.CPU_Primitives.Multiprocessors;
39 with System.Multiprocessors;
40
41 package System.BB.Threads.Queues is
42 pragma Preelaborate;
43
44 use type System.BB.Time.Time;
45 package CPRMU renames System.BB.CPU_Primitives.Multiprocessors;
46
47 ----------------
48 -- Ready list --
49 ----------------
50
51 procedure Insert (Thread : Thread_Id) with
52 -- Insert the thread into the ready queue. The thread is always inserted
53 -- at the tail of its active priority because these are the semantics of
54 -- FIFO_Within_Priorities dispatching policy when a task becomes ready to
55 -- execute.
56 --
57 -- There is one case in which the ready queue does not change after the
58 -- insertion. It can happen only when there is no ready thread to execute,
59 -- in which case the currently running thread was inserted in the queue
60 -- (keeping its state as non-runnable). If the state of the thread changes
61 -- (after an interrupt), the reinsertion of the thread will not change the
62 -- ready queue.
63
64 Pre =>
65 Thread /= Null_Thread_Id
66
67 -- Normal insertion
68
69 and then (Thread.State = Runnable
70
71 -- Insertion in the queue of the thread that was executing
72 -- before (even when it is no longer runnable) because we
73 -- need to have an execution context for the interrupts
74 -- that may arrive.
75
76 or else First_Thread = Null_Thread_Id),
77
78 Post =>
79
80 -- Insertions in the queue when there is no thread ready to execute
81 -- means that there can be no other ready thread.
82
83 (if Thread.State'Old /= Runnable then
84 First_Thread = Thread
85 and then Running_Thread = Thread
86 and then Running_Thread.Next = Null_Thread_Id
87
88 -- Insertions at the tail of its active priority must guarantee that
89 -- any thread after this one must have a priority which is strictly
90 -- lower than the one just inserted.
91
92 else Thread.Next = Null_Thread_Id
93 or else Thread.Active_Priority > Thread.Next.Active_Priority),
94
95 Inline => True;
96
97 procedure Extract (Thread : Thread_Id) with
98 -- Remove the thread from the ready queue. We can only extract the one
99 -- which is first in the ready queue.
100
101 Pre =>
102
103 -- The only thread that can be extracted from the ready list is the
104 -- one that is currently executing (as a result of a delay or a
105 -- protected operation).
106
107 Thread = Running_Thread
108 and then Thread = First_Thread
109 and then Thread.State /= Runnable,
110
111 Post =>
112 -- The next thread to execute is the one just next in the ready queue
113
114 First_Thread = Thread.Next'Old
115 and then Thread.all.Next = Null_Thread_Id,
116
117 Inline => True;
118
119 procedure Change_Priority (Thread : Thread_Id; Priority : Integer) with
120 -- Move the thread to a new priority within the ready queue
121
122 Pre =>
123 Thread /= Null_Thread_Id
124
125 -- We can only change the priority of the thread that is currently
126 -- executing.
127
128 and then Thread = Running_Thread
129
130 -- The new priority can never be lower than the base priority,
131
132 and then Priority >= Thread.Base_Priority,
133
134 Post =>
135 -- Priority has changed
136
137 Thread.Active_Priority = Priority
138
139 -- Queue is still ordered and has the same elements (weaken form: has
140 -- the same length).
141
142 and Queue_Ordered
143 and Queue_Length = Queue_Length'Old;
144
145 function Current_Priority
146 (CPU_Id : System.Multiprocessors.CPU) return Integer with
147 -- Return the active priority of the current thread or
148 -- System.Any_Priority'First if no threads are running.
149
150 Post =>
151
152 -- When no thread is ready to execute then return the lowest priority
153
154 (if Running_Thread_Table (CPU_Id) = Null_Thread_Id
155 or else Running_Thread_Table (CPU_Id).State /= Runnable
156 then
157 Current_Priority'Result = System.Any_Priority'First
158
159 -- Otherwise, return the active priority of the running thread
160
161 else
162 Current_Priority'Result =
163 Running_Thread_Table (CPU_Id).Active_Priority),
164
165 Inline => True;
166
167 procedure Yield (Thread : Thread_Id) with
168 -- Move the thread to the tail of its current priority
169
170 Pre =>
171
172 -- The only thread that can yield is the one that is currently
173 -- executing.
174
175 Thread = Running_Thread
176 and then Thread = First_Thread
177 and then Thread.State = Runnable,
178
179 Post =>
180
181 Queue_Ordered
182 and then
183
184 -- The next thread to execute is the one just next in the ready queue
185 -- if it has the same priority of the currently running thread.
186
187 (Thread.Next = Null_Thread_Id
188 or else Thread.Next.Active_Priority < Thread.Active_Priority)
189
190 -- In any case, the thread must remain runnable, and no context switch
191 -- is possible within this procedure.
192
193 and then Thread = Running_Thread
194 and then Thread.all.State = Runnable;
195
196 Running_Thread_Table : array (System.Multiprocessors.CPU) of Thread_Id :=
197 (others => Null_Thread_Id);
198 pragma Volatile_Components (Running_Thread_Table);
199 pragma Export (Asm, Running_Thread_Table, "__gnat_running_thread_table");
200 -- Identifier of the thread that is currently executing in the given CPU.
201 -- This shared variable is used by the debugger to know which is the
202 -- currently running thread. This variable is exported to be visible in the
203 -- assembly code to allow its value to be used when necessary (by the
204 -- low-level routines).
205
206 First_Thread_Table : array (System.Multiprocessors.CPU) of Thread_Id :=
207 (others => Null_Thread_Id);
208 pragma Volatile_Components (First_Thread_Table);
209 pragma Export (Asm, First_Thread_Table, "first_thread_table");
210 -- Pointers to the first thread of the priority queue for each CPU. This is
211 -- the thread that will be next to execute in the given CPU (if not already
212 -- executing). This variable is exported to be visible in the assembly code
213 -- to allow its value to be used when necessary (by the low-level
214 -- routines).
215
216 function Running_Thread return Thread_Id with
217 -- Returns the running thread of the current CPU
218
219 Post => Running_Thread'Result /= Null_Thread_Id,
220
221 Inline => True;
222
223 function First_Thread return Thread_Id with
224 -- Returns the first thread in the priority queue of the current CPU
225
226 Inline => True;
227
228 function Context_Switch_Needed return Boolean with
229 -- This function returns True if the task (or interrupt handler) that is
230 -- executing is no longer the highest priority one. This function can also
231 -- be called by the interrupt handlers' epilogue.
232
233 Pre =>
234 First_Thread /= Null_Thread_Id
235 and then Running_Thread /= Null_Thread_Id,
236
237 Post =>
238 Context_Switch_Needed'Result = (First_Thread /= Running_Thread),
239
240 Inline => True,
241
242 Export => True,
243 Convention => Asm,
244 External_Name => "context_switch_needed";
245
246 ----------------
247 -- Alarm list --
248 ----------------
249
250 procedure Insert_Alarm
251 (T : System.BB.Time.Time;
252 Thread : Thread_Id;
253 Is_First : out Boolean) with
254 -- This procedure inserts the Thread inside the alarm queue ordered by
255 -- Time. If the alarm is the next to be served then the procedure returns
256 -- True in the Is_First argument, and False otherwise.
257
258 Pre =>
259
260 -- We can only insert in the alarm queue threads whose state is
261 -- Delayed.
262
263 Thread /= Null_Thread_Id
264 and then Thread.State = Delayed,
265
266 Post =>
267
268 -- The alarm time is always inserted in the thread descriptor
269
270 Thread.all.Alarm_Time = T
271
272 -- Always inserted by expiration time
273
274 and then (Thread.all.Next_Alarm = Null_Thread_Id
275 or else
276 Thread.all.Alarm_Time <= Thread.all.Next_Alarm.Alarm_Time)
277
278 -- Next alarm can never be later than the currently inserted one
279
280 and then Get_Next_Alarm_Time (Get_CPU (Thread)) <= T
281
282 -- Inserted first in the queue if there is not a more recent alarm
283
284 and then (if Is_First then Get_Next_Alarm_Time (Get_CPU (Thread)) = T);
285
286 function Extract_First_Alarm return Thread_Id with
287 -- Extract the first element in the alarm queue and return its identifier
288
289 Post =>
290
291 -- All threads extracted from the alarm queue must be waiting in a
292 -- delay statement.
293
294 -- Note: we use AND instead of AND THEN in the conjunctions here
295 -- because otherwise the use of OLD in the last test violates the
296 -- rule about use of OLD in potentially unevaluated expressions.
297
298 -- Could we instead use pragma Unevaluated_Use_Of_Old (Allow)???
299
300 Extract_First_Alarm'Result.State = Delayed
301
302 -- After extraction the Alarm_Time field is set to Time'Last
303
304 and Extract_First_Alarm'Result.Alarm_Time = System.BB.Time.Time'Last
305
306 -- After extraction the Next_Alarm field is set to Null_Thread_Id
307
308 and Extract_First_Alarm'Result.Next_Alarm = Null_Thread_Id
309
310 -- The extracted thread must be the one with the smallest value of
311 -- Alarm_Time.
312
313 and Get_Next_Alarm_Time (CPRMU.Current_CPU)'Old <=
314 Get_Next_Alarm_Time (CPRMU.Current_CPU),
315
316 Inline => True;
317
318 function Get_Next_Alarm_Time
319 (CPU_Id : System.Multiprocessors.CPU) return System.BB.Time.Time;
320 pragma Inline (Get_Next_Alarm_Time);
321 -- Return the time when the next alarm should be set. This function does
322 -- not modify the queue.
323
324 procedure Wakeup_Expired_Alarms (Now : Time.Time) with
325 -- Wakeup all expired alarms and set the alarm timer if needed
326
327 Post =>
328 Get_Next_Alarm_Time (CPRMU.Current_CPU) > Now;
329
330 -----------------
331 -- Global_List --
332 -----------------
333
334 Global_List : Thread_Id := Null_Thread_Id;
335 -- This variable is the starting point of the list containing all threads
336 -- in the system. No protection (for concurrent access) is needed for
337 -- this variable because task creation is serialized.
338
339 function Queue_Length return Natural with Ghost;
340 -- Return the length of the thread list headed by HEAD, following the
341 -- next link.
342
343 function Queue_Ordered return Boolean with Ghost;
344 -- Return True iff thread list headed by HEAD is correctly ordered by
345 -- priority.
346
347 end System.BB.Threads.Queues;