------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- Cheddar is a GNU GPL real-time scheduling analysis tool. -- This program provides services to automatically check schedulability and -- other performance criteria of real-time architecture models. -- -- Copyright (C) 2002-2016, Frank Singhoff, Alain Plantec, Jerome Legrand -- -- The Cheddar project was started in 2002 by -- Frank Singhoff, Lab-STICC UMR 6285 laboratory, Université de Bretagne Occidentale -- -- Cheddar has been published in the "Agence de Protection des Programmes/France" in 2008. -- Since 2008, Ellidiss technologies also contributes to the development of -- Cheddar and provides industrial support. -- -- The full list of contributors and sponsors can be found in AUTHORS.txt and SPONSORS.txt -- -- This program 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; either version 2 of the License, or -- (at your option) any later version. -- -- This program 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. See the -- GNU General Public License for more details. -- -- You should have received a copy of the GNU General Public License -- along with this program; if not, write to the Free Software -- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -- -- -- Contact : cheddar@listes.univ-brest.fr -- ------------------------------------------------------------------------------ -- Last update : -- $Rev: 1249 $ -- $Date: 2014-08-28 07:02:15 +0200 (Fri, 28 Aug 2014) $ -- $Author: singhoff $ ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with Translate; use Translate; with Buffer_Set; use Buffer_Set; use Buffer_Set.Generic_Buffer_Set; with Resources; use Resources; use Resources.Resource_Accesses; with natural_util; use natural_util; package body Scheduling_Analysis.extended.resource_analysis is procedure Blocking_Time_From_Simulation (My_Task : in Generic_Task_Ptr; My_Resources : in Resources_Set; Sched : in Scheduling_Sequence_Ptr; Max : in out Natural; Min : in out Natural; Average : in out Double) is A_Resource : Generic_Resource_Ptr; Resource_Ite : Resources_Iterator; Nb_Blocking_Time, start_time, blocking_time : Natural; use_resource, has_wait : boolean; begin Max := 0; Min := Natural'Last; Average := 0.0; Nb_Blocking_Time := 0; if not is_empty(my_resources) then reset_iterator (My_Resources, Resource_Ite); loop current_element (My_Resources, A_Resource, Resource_Ite); -- Compute blocking time fo a given resource -- use_resource:=false; for i in 0..A_Resource.critical_sections.nb_entries-1 loop if (A_Resource.critical_sections.entries (i).item = My_Task.name) then use_resource:=true; end if; end loop; -- The task use this resource ... make the analysis -- has_wait:=false; if use_resource then for T in 0 .. Sched.nb_entries - 1 loop -- we store wait_for_resource events -- if not has_wait then if (Sched.entries (T).data.type_of_event = Wait_For_Resource) then if (Sched.entries (T).data.wait_for_resource_task.name=my_task.name) and (Sched.entries (T).data.wait_for_resource.name=a_resource.name) then start_time:= Sched.entries (T).item; has_wait:=true; end if; end if; end if; -- We look for an allocate event and then, we compute blocking time -- if (Sched.entries (T).data.type_of_event = allocate_Resource) then if (Sched.entries (T).data.allocate_task.name=my_task.name) and (Sched.entries (T).data.allocate_resource.name=a_resource.name) then if has_wait then -- compute maximum, minimum and average blocking time -- blocking_time := Sched.entries (T).item - start_time; Max := Natural'Max (Max, blocking_time); Min := Natural'Min (Min, blocking_time); Average := Average + Double (blocking_time); Nb_Blocking_Time := Nb_Blocking_Time + 1; has_wait:=false; end if; end if; end if; end loop; end if; exit when is_last_element (My_Resources, Resource_Ite); next_element (My_Resources, Resource_Ite); end loop; end if; if Min = Natural'Last then Min := 0; end if; if Nb_Blocking_Time /= 0 then Average := Average / Double (Nb_Blocking_Time); end if; end Blocking_Time_From_Simulation; function Deadlock_From_Simulation (My_Tasks : in Tasks_Set; My_Resources : in Resources_Set; Processor_Name : in Unbounded_String; Sched : in Scheduling_Sequence_Ptr) return Deadlock_List is Result : Deadlock_List; -- Variables required to scan the resource and task -- Item : Deadlock_Item_Ptr; Item_Task : Generic_Task_Ptr; Item_Resource : Generic_Resource_Ptr; -- To store number of Tasks -- Number_Of_Tasks : constant Tasks_Range := get_number_of_elements (My_Tasks); -- To store number of resource -- Number_Of_Resources : constant Resources_Range := get_number_of_elements (My_Resources); -- Stamp to represent the tree storing allocated resources and -- awaited resources -- Stamp_For_Allocate : array (Tasks_Range'Range, Resources_Range' Range) of Integer; Stamp_For_Wait : array (Tasks_Range'Range, Resources_Range' Range) of Integer; -- Tables of names of Tasks -- Table_Name_Tasks : array (Tasks_Range'Range) of Unbounded_String; -- Table of names of resources -- Table_Name_Resources : array (Resources_Range'Range) of Unbounded_String; -- Tables to store the indexes of the tasks and the resources -- Table_Index_Task : array (Natural range 0 .. Framework_Config.Max_Resources - 1) of Tasks_Range; Table_Index_Resource : array (Natural range 0 .. Framework_Config.Max_Resources - 1) of Resources_Range; -- Index -- Current_Time : Natural := 0; Index_Task : Tasks_Range := tasks_range'last; Index_Resource : Resources_Range := resources_range'last; -- booleen to say if there is deadlock -- Ok : Boolean; -- procedure being used to find the index of a task -- procedure Index_Of_Tasks (Name : in out Unbounded_String; Index : in out Tasks_Range) is begin for I in 0 .. Number_Of_Tasks - 1 loop if (Table_Name_Tasks (I) = Name) then Index := I; end if; end loop; end Index_Of_Tasks; -- procedure being used to find the index of a resource -- procedure Index_Of_Resources (Name : in out Unbounded_String; Index : in out Resources_Range) is begin for I in 0 .. Number_Of_Resources - 1 loop if (Table_Name_Resources (I) = Name) then Index := I; end if; end loop; end Index_Of_Resources; -- procedure being used to find if a resource is held by a task -- procedure Seek_Of_Task (R : in out Resources_Range; Index : in out Tasks_Range; found : out boolean) is begin found :=false; for I in 0 .. Number_Of_Tasks - 1 loop if (Stamp_For_Allocate (I, R) = 1) then Index := I; found:=true; end if; end loop; end Seek_Of_Task; -- procedure being used to find if a task awaits a resource -- procedure Seek_Of_Resource (T : in out Tasks_Range; Index : in out Resources_Range; found : out boolean) is begin found :=false; for I in 0 .. Number_Of_Resources - 1 loop if (Stamp_For_Wait (T, I) = 1) then Index := I; found:=true; end if; end loop; end Seek_Of_Resource; procedure Perform_Analysis_Of_Resources is Item2 : Deadlock_Item_Ptr; List_Ite : Deadlock_Iterator; Found : Boolean := False; seeked : Boolean := False; begin -- Initialization of stamps -- for I in 0 .. Number_Of_Tasks - 1 loop for J in 0 .. Number_Of_Resources - 1 loop Stamp_For_Allocate (I, J) := 0; Stamp_For_Wait (I, J) := 0; end loop; end loop; -- Analysis at scheduling time At_Time -- for At_Time in 0 .. Sched.entries (Sched.nb_entries - 1).item loop for J in 0 .. Sched.nb_entries - 1 loop -- construction of the tree -- if (Sched.entries (J).item = At_Time) then if (Sched.entries (J).data.type_of_event = Allocate_Resource) then Item_Task := Sched.entries (J).data.allocate_task; Item_Resource := Sched.entries (J).data.allocate_resource; Index_Of_Tasks (Item_Task.name, Index_Task); Index_Of_Resources (Item_Resource.name, Index_Resource); Stamp_For_Allocate (Index_Task, Index_Resource) := 1; Stamp_For_Wait (Index_Task, Index_Resource) := 0; end if; if (Sched.entries (J).data.type_of_event = Wait_For_Resource) then Item_Task := Sched.entries (J).data.wait_for_resource_task; Item_Resource := Sched.entries (J).data.wait_for_resource; Index_Of_Tasks (Item_Task.name, Index_Task); Index_Of_Resources (Item_Resource.name, Index_Resource); Stamp_For_Wait (Index_Task, Index_Resource) := 1; end if; if (Sched.entries (J).data.type_of_event = Release_Resource) then Item_Task := Sched.entries (J).data.release_task; Item_Resource := Sched.entries (J).data.release_resource; Index_Of_Tasks (Item_Task.name, Index_Task); Index_Of_Resources (Item_Resource.name, Index_Resource); Stamp_For_Allocate (Index_Task, Index_Resource) := 0; end if; end if; end loop; --analyse of stamps -- for K in 0 .. Number_Of_Resources - 1 loop Table_Index_Task := (others=>0); Table_Index_Resource := (others=>0); Current_Time := 0; -- Analysis of the resource K -- Index_Resource := K; loop Ok := False; seeked := False; Seek_Of_Task (Index_Resource, Index_Task, seeked); if Seeked then Table_Index_Task (Current_Time) := Index_Task; Table_Index_Resource (Current_Time) := Index_Resource; seeked := False; Seek_Of_Resource (Index_Task, Index_Resource, seeked); if Seeked then for P in 0 .. Current_Time loop if (Table_Index_Resource (P) = Index_Resource) then Ok := True; end if; end loop; if Ok then for P in 0 .. Current_Time loop Item := new Deadlock_Item; Item.time := At_Time; Item.task_name := Table_Name_Tasks (Table_Index_Task (P)); Item.resource_name := Table_Name_Resources (Table_Index_Resource (P)) ; Found := False; -- to check if data is already present in the -- list -- if not is_empty (Result) then reset_head_iterator (Result, List_Ite); loop current_element (Result, Item2, List_Ite); if ((Item2.task_name = Item.task_name) and (Item2.resource_name = Item.resource_name)) then Found := True; exit; end if; if is_tail_element (Result, List_Ite) then exit; end if; next_element (Result, List_Ite); end loop; end if; -- addition of data in the list -- if not Found then add (Result, Item); end if; end loop; exit; end if; else exit; end if; else exit; end if; Current_Time := Current_Time + 1; end loop; end loop; end loop; end Perform_Analysis_Of_Resources; begin -- Initialization of tables of tasks names -- for I in 0 .. Number_Of_Tasks - 1 loop get_element_number (My_Tasks, Item_Task, I); Table_Name_Tasks (I) := Item_Task.name; end loop; -- Initialization of tables of resources of names -- for I in 0 .. Number_Of_Resources - 1 loop get_element_number (My_Resources, Item_Resource, I); Table_Name_Resources (I) := Item_Resource.name; end loop; Perform_Analysis_Of_Resources; return Result; end Deadlock_From_Simulation; function Priority_Inversion_From_Simulation (My_Tasks : in Tasks_Set; My_Resources : in Resources_Set; Processor_Name : in Unbounded_String; Sched : in Scheduling_Sequence_Ptr) return Priority_Inversion_List is Result : Priority_Inversion_List; -- Variables required to scan the resource set -- Item : Priority_Inversion_Item_Ptr; A_Resource : Generic_Resource_Ptr; My_Iterator : Resources_Iterator; -- Store the event of the resource allocation -- Allocation : Time_Unit_Event_Ptr; -- Store all Wait_For_Resource events -- Wait_Events : array (Time_Unit_Range) of Time_Unit_Event_Ptr; -- Simulation time of the stored event -- Wait_Event_Time : array (Time_Unit_Range) of Natural; -- Index on Wait_Events and Indexes tables -- Index : Time_Unit_Range := 0; -- Index on the scheduling table -- Current_Time : Time_Unit_Range := 0; procedure Perform_Analysis_Of_One_Resource is begin Current_Time := 0; -- First, find an Allocation Event -- loop if (Current_Time >= Sched.nb_entries - 1) then return; end if; if (Sched.entries (Current_Time).data.type_of_event = Allocate_Resource) then if (Sched.entries (Current_Time).data.allocate_resource.name = A_Resource.name) then Allocation := Sched.entries (Current_Time).data; exit; end if; end if; Current_Time := Current_Time + 1; end loop; loop Current_Time := Current_Time + 1; -- Search all Wait_For_Resource events upto the next allocation -- if (Current_Time >= Sched.nb_entries - 1) then return; end if; if (Sched.entries (Current_Time).data.type_of_event = Allocate_Resource) then if (Sched.entries (Current_Time).data.allocate_resource.name = A_Resource.name) then -- The next Allocate event is found, stop collecting data -- and do analysis -- -- Check that between the two "Allocate" events when -- the priority of the first allocating task -- is less than -- 2nd one. -- if (Allocation.allocate_task.priority < Sched.entries (Current_Time).data.allocate_task.priority) then declare -- Start time of the priority inversion -- Start_Time : Natural := Sched.entries (Current_Time).item; begin -- look for the start time of the priority inversion -- for Z in reverse 0 .. Index - 1 loop if Wait_Events (Z).wait_for_resource_task.name = Sched.entries (Current_Time).data.allocate_task. name then Start_Time := Wait_Event_Time (Z); end if; end loop; -- Store the detected priority inversion -- if Start_Time < Sched.entries (Current_Time).item then Item := new Priority_Inversion_Item; Item.start_time := Start_Time; Item.end_time := Sched.entries (Current_Time).item; Item.task_name := Sched.entries (Current_Time).data.allocate_task. name; Item.resource_name := Sched.entries (Current_Time).data. allocate_resource.name; add (Result, Item); end if; end; end if; -- Ready for the next priority inversion analysis -- Index := 0; Allocation := Sched.entries (Current_Time).data; end if; end if; if (Sched.entries (Current_Time).data.type_of_event = Wait_For_Resource) then if (Sched.entries (Current_Time).data.wait_for_resource.name = A_Resource.name) then Wait_Events (Index) := Sched.entries (Current_Time).data; Wait_Event_Time (Index) := Sched.entries (Current_Time).item; Index := Index + 1; end if; end if; end loop; end Perform_Analysis_Of_One_Resource; begin reset_iterator (My_Resources, My_Iterator); initialize (Result); loop current_element (My_Resources, A_Resource, My_Iterator); if (Processor_Name = A_Resource.cpu_name) then Perform_Analysis_Of_One_Resource; end if; exit when is_last_element (My_Resources, My_Iterator); next_element (My_Resources, My_Iterator); end loop; return Result; end Priority_Inversion_From_Simulation; end Scheduling_Analysis.extended.resource_analysis;