1 ------------------------------------------------------------------------------
3 -- GNAT RUN-TIME LIBRARY (GNARL) COMPONENTS --
5 -- S Y S T E M . T A S K I N G . Q U E U I N G --
9 -- Copyright (C) 1992-2020, Free Software Foundation, Inc. --
11 -- GNARL is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
19 -- additional permissions described in the GCC Runtime Library Exception, --
20 -- version 3.1, as published by the Free Software Foundation. --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
27 -- GNARL was developed by the GNARL team at Florida State University. --
28 -- Extensive contributions were provided by Ada Core Technologies, Inc. --
30 ------------------------------------------------------------------------------
32 -- This version of the body implements queueing policy according to the policy
33 -- specified by the pragma Queuing_Policy. When no such pragma is specified
34 -- FIFO policy is used as default.
36 with System.Task_Primitives.Operations;
37 with System.Tasking.Initialization;
38 with System.Parameters;
40 package body System.Tasking.Queuing is
43 use Task_Primitives.Operations;
44 use Protected_Objects;
45 use Protected_Objects.Entries;
47 -- Entry Queues implemented as doubly linked list
49 Queuing_Policy : Character;
50 pragma Import (C, Queuing_Policy, "__gl_queuing_policy");
52 Priority_Queuing : constant Boolean := Queuing_Policy = 'P';
54 procedure Send_Program_Error
56 Entry_Call : Entry_Call_Link);
57 -- Raise Program_Error in the caller of the specified entry call
59 function Check_Queue (E : Entry_Queue) return Boolean;
60 -- Check the validity of E.
61 -- Return True if E is valid, raise Assert_Failure if assertions are
62 -- enabled and False otherwise.
64 -----------------------------
65 -- Broadcast_Program_Error --
66 -----------------------------
68 procedure Broadcast_Program_Error
70 Object : Protection_Entries_Access;
71 Pending_Call : Entry_Call_Link;
72 RTS_Locked : Boolean := False)
74 Entry_Call : Entry_Call_Link;
76 if Single_Lock and then not RTS_Locked then
80 if Pending_Call /= null then
81 Send_Program_Error (Self_ID, Pending_Call);
84 for E in Object.Entry_Queues'Range loop
85 Dequeue_Head (Object.Entry_Queues (E), Entry_Call);
87 while Entry_Call /= null loop
88 pragma Assert (Entry_Call.Mode /= Conditional_Call);
90 Send_Program_Error (Self_ID, Entry_Call);
91 Dequeue_Head (Object.Entry_Queues (E), Entry_Call);
95 if Single_Lock and then not RTS_Locked then
98 end Broadcast_Program_Error;
104 function Check_Queue (E : Entry_Queue) return Boolean is
105 Valid : Boolean := True;
106 C, Prev : Entry_Call_Link;
109 if E.Head = null then
110 if E.Tail /= null then
112 pragma Assert (Valid);
116 or else E.Tail.Next /= E.Head
119 pragma Assert (Valid);
130 pragma Assert (Valid);
134 if Prev /= C.Prev then
136 pragma Assert (Valid);
140 exit when C = E.Head;
143 if Prev /= E.Tail then
145 pragma Assert (Valid);
157 -- Return number of calls on the waiting queue of E
159 function Count_Waiting (E : Entry_Queue) return Natural is
161 Temp : Entry_Call_Link;
164 pragma Assert (Check_Queue (E));
168 if E.Head /= null then
173 exit when E.Tail = Temp;
185 -- Dequeue call from entry_queue E
187 procedure Dequeue (E : in out Entry_Queue; Call : Entry_Call_Link) is
189 pragma Assert (Check_Queue (E));
190 pragma Assert (Call /= null);
192 -- If empty queue, simply return
194 if E.Head = null then
198 pragma Assert (Call.Prev /= null);
199 pragma Assert (Call.Next /= null);
201 Call.Prev.Next := Call.Next;
202 Call.Next.Prev := Call.Prev;
204 if E.Head = Call then
206 -- Case of one element
208 if E.Tail = Call then
212 -- More than one element
218 elsif E.Tail = Call then
222 -- Successfully dequeued
226 pragma Assert (Check_Queue (E));
233 procedure Dequeue_Call (Entry_Call : Entry_Call_Link) is
234 Called_PO : Protection_Entries_Access;
237 pragma Assert (Entry_Call /= null);
239 if Entry_Call.Called_Task /= null then
241 (Entry_Call.Called_Task.Entry_Queues
242 (Task_Entry_Index (Entry_Call.E)),
246 Called_PO := To_Protection (Entry_Call.Called_PO);
247 Dequeue (Called_PO.Entry_Queues
248 (Protected_Entry_Index (Entry_Call.E)),
257 -- Remove and return the head of entry_queue E
259 procedure Dequeue_Head
260 (E : in out Entry_Queue;
261 Call : out Entry_Call_Link)
263 Temp : Entry_Call_Link;
266 pragma Assert (Check_Queue (E));
267 -- If empty queue, return null pointer
269 if E.Head = null then
276 -- Case of one element
278 if E.Head = E.Tail then
282 -- More than one element
285 pragma Assert (Temp /= null);
286 pragma Assert (Temp.Next /= null);
287 pragma Assert (Temp.Prev /= null);
290 Temp.Prev.Next := Temp.Next;
291 Temp.Next.Prev := Temp.Prev;
294 -- Successfully dequeued
299 pragma Assert (Check_Queue (E));
306 -- Enqueue call at the end of entry_queue E, for FIFO queuing policy.
307 -- Enqueue call priority ordered, FIFO at same priority level, for
308 -- Priority queuing policy.
310 procedure Enqueue (E : in out Entry_Queue; Call : Entry_Call_Link) is
311 Temp : Entry_Call_Link := E.Head;
314 pragma Assert (Check_Queue (E));
315 pragma Assert (Call /= null);
319 if Priority_Queuing then
328 -- Find the entry that the new guy should precede
330 exit when Call.Prio > Temp.Prio;
333 if Temp = E.Head then
347 Call.Prev := Temp.Prev;
352 if Temp = E.Head then
357 pragma Assert (Call.Prev /= null);
358 pragma Assert (Call.Next /= null);
360 Call.Prev.Next := Call;
361 Call.Next.Prev := Call;
364 pragma Assert (Check_Queue (E));
370 if E.Head = null then
380 pragma Assert (Check_Queue (E));
387 procedure Enqueue_Call (Entry_Call : Entry_Call_Link) is
388 Called_PO : Protection_Entries_Access;
391 pragma Assert (Entry_Call /= null);
393 if Entry_Call.Called_Task /= null then
395 (Entry_Call.Called_Task.Entry_Queues
396 (Task_Entry_Index (Entry_Call.E)),
400 Called_PO := To_Protection (Entry_Call.Called_PO);
401 Enqueue (Called_PO.Entry_Queues
402 (Protected_Entry_Index (Entry_Call.E)),
411 -- Return the head of entry_queue E
413 function Head (E : Entry_Queue) return Entry_Call_Link is
415 pragma Assert (Check_Queue (E));
423 -- Return True if Call is on any entry_queue at all
425 function Onqueue (Call : Entry_Call_Link) return Boolean is
427 pragma Assert (Call /= null);
429 -- Utilize the fact that every queue is circular, so if Call
430 -- is on any queue at all, Call.Next must NOT be null.
432 return Call.Next /= null;
435 --------------------------------
436 -- Requeue_Call_With_New_Prio --
437 --------------------------------
439 procedure Requeue_Call_With_New_Prio
440 (Entry_Call : Entry_Call_Link; Prio : System.Any_Priority) is
442 pragma Assert (Entry_Call /= null);
444 -- Perform a queue reordering only when the policy being used is the
447 if Priority_Queuing then
448 if Onqueue (Entry_Call) then
449 Dequeue_Call (Entry_Call);
450 Entry_Call.Prio := Prio;
451 Enqueue_Call (Entry_Call);
454 end Requeue_Call_With_New_Prio;
456 ---------------------------------
457 -- Select_Protected_Entry_Call --
458 ---------------------------------
460 -- Select an entry of a protected object. Selection depends on the
461 -- queuing policy being used.
463 procedure Select_Protected_Entry_Call
465 Object : Protection_Entries_Access;
466 Call : out Entry_Call_Link)
468 Entry_Call : Entry_Call_Link;
469 Temp_Call : Entry_Call_Link;
470 Entry_Index : Protected_Entry_Index := Null_Entry; -- stop warning
476 -- Priority queuing case
478 if Priority_Queuing then
479 for J in Object.Entry_Queues'Range loop
480 Temp_Call := Head (Object.Entry_Queues (J));
485 (Object.Find_Body_Index
486 (Object.Compiler_Info, J)).
487 Barrier (Object.Compiler_Info, J)
490 or else Entry_Call.Prio < Temp_Call.Prio
492 Entry_Call := Temp_Call;
498 -- FIFO queueing case
501 for J in Object.Entry_Queues'Range loop
502 Temp_Call := Head (Object.Entry_Queues (J));
507 (Object.Find_Body_Index
508 (Object.Compiler_Info, J)).
509 Barrier (Object.Compiler_Info, J)
511 Entry_Call := Temp_Call;
520 Broadcast_Program_Error (Self_ID, Object, null);
523 -- If a call was selected, dequeue it and return it for service
525 if Entry_Call /= null then
526 Temp_Call := Entry_Call;
527 Dequeue_Head (Object.Entry_Queues (Entry_Index), Entry_Call);
528 pragma Assert (Temp_Call = Entry_Call);
532 end Select_Protected_Entry_Call;
534 ----------------------------
535 -- Select_Task_Entry_Call --
536 ----------------------------
538 -- Select an entry for rendezvous. Selection depends on the queuing policy
541 procedure Select_Task_Entry_Call
543 Open_Accepts : Accept_List_Access;
544 Call : out Entry_Call_Link;
545 Selection : out Select_Index;
546 Open_Alternative : out Boolean)
548 Entry_Call : Entry_Call_Link;
549 Temp_Call : Entry_Call_Link;
550 Entry_Index : Task_Entry_Index := Task_Entry_Index'First;
551 Temp_Entry : Task_Entry_Index;
554 Open_Alternative := False;
556 Selection := No_Rendezvous;
558 if Priority_Queuing then
559 -- Priority queueing case
561 for J in Open_Accepts'Range loop
562 Temp_Entry := Open_Accepts (J).S;
564 if Temp_Entry /= Null_Task_Entry then
565 Open_Alternative := True;
566 Temp_Call := Head (Acceptor.Entry_Queues (Temp_Entry));
569 and then (Entry_Call = null
570 or else Entry_Call.Prio < Temp_Call.Prio)
572 Entry_Call := Head (Acceptor.Entry_Queues (Temp_Entry));
573 Entry_Index := Temp_Entry;
582 for J in Open_Accepts'Range loop
583 Temp_Entry := Open_Accepts (J).S;
585 if Temp_Entry /= Null_Task_Entry then
586 Open_Alternative := True;
587 Temp_Call := Head (Acceptor.Entry_Queues (Temp_Entry));
589 if Temp_Call /= null then
590 Entry_Call := Head (Acceptor.Entry_Queues (Temp_Entry));
591 Entry_Index := Temp_Entry;
599 if Entry_Call /= null then
600 Dequeue_Head (Acceptor.Entry_Queues (Entry_Index), Entry_Call);
606 end Select_Task_Entry_Call;
608 ------------------------
609 -- Send_Program_Error --
610 ------------------------
612 procedure Send_Program_Error
614 Entry_Call : Entry_Call_Link)
618 Caller := Entry_Call.Self;
619 Entry_Call.Exception_To_Raise := Program_Error'Identity;
621 Initialization.Wakeup_Entry_Caller (Self_ID, Entry_Call, Done);
623 end Send_Program_Error;
625 end System.Tasking.Queuing;