<div dir="ltr">Hi,<div><br></div><div>I would request you to help me understand how to make this patch work. Currently, it is giving _ARMV4_Exception_data_abort_default while debugging with qemu and gdb.</div><div><br></div><div>This happens because the scheduler tries to access the CPU[0].executing while trying to schedule the Init task, but the task executing on CPU 0 hasn't been scheduled using Strong APA (I am assuming it is a default task that the CPU gets when the BSP starts). This error was not there earlier since I directly used Per_CPU_Control->heir, which Mr. Huber advised against.</div><div><br></div><div>Please advise.</div><div><br></div><div>Differences as seen on GitHub : </div><div><br></div><div><a href="https://github.com/richidubey/rtems/blob/83b59a5aef901a5c6ecd916a9fc2d7a96470d088/cpukit/score/src/schedulerstrongapa.c#L330">https://github.com/richidubey/rtems/blob/83b59a5aef901a5c6ecd916a9fc2d7a96470d088/cpukit/score/src/schedulerstrongapa.c#L330</a></div><div>vs</div><div><a href="https://github.com/richidubey/rtems/blob/4bbf5d9abe1e16bd942b9806e0be7efcd0cbfe7f/cpukit/score/src/schedulerstrongapa.c#L356">https://github.com/richidubey/rtems/blob/4bbf5d9abe1e16bd942b9806e0be7efcd0cbfe7f/cpukit/score/src/schedulerstrongapa.c#L356</a></div><div><br></div><div><br></div><div>GDB Stack trace:</div><div>------------------------------------------------------------------------------------------------------</div><div>:~/quick-start/rtems/5/bin$ ./arm-rtems5-gdb --command=arm.gdb ~/quick-start/build/b3-realview/arm-rtems5/c/realview_pbx_a9_qemu/testsuites/smptests/smpstrongapa01.exe<br></div><div>...</div><div><br></div><div>Loading section .data, size 0x530 lma 0x200000<br>Start address 0x00100040, load size 137412<br>Transfer rate: 14910 KB/sec, 1808 bytes/write.<br>(gdb) continue<br>Continuing.<br><br>Thread 1 hit Breakpoint 2, _ARMV4_Exception_data_abort_default () at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/cpu/arm/armv4-exception-default.S:70<br>70 sub sp, #MORE_CONTEXT_SIZE<br>(gdb) bt<br>#0 _ARMV4_Exception_data_abort_default () at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/cpu/arm/armv4-exception-default.S:70<br>#1 0x00118db0 in _Scheduler_strong_APA_Get_lowest_reachable (self=0x200620 <_Configuration_Scheduler_strong_APA_dflt>, front=1, rear=2, cpu_to_preempt=0x207dc0 <_ISR_Stack_area_begin+2688>) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/schedulerstrongapa.c:468<br>Backtrace stopped: previous frame inner to this frame (corrupt stack?)<br>(gdb) reset<br>Loading section .start, size 0x8e0 lma 0x100000<br>...<br>Loading section .data, size 0x530 lma 0x200000<br>Start address 0x00100040, load size 137412<br>Transfer rate: 2439 KB/sec, 1808 bytes/write.<br>(gdb) b _Scheduler_strong_APA_Get_lowest_reachable<br>Breakpoint 7 at 0x118d6c: file /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/schedulerstrongapa.c, line 457.<br>(gdb) continue<br>Continuing.<br><br>Thread 1 hit Breakpoint 7, _Scheduler_strong_APA_Get_lowest_reachable (self=0x200620 <_Configuration_Scheduler_strong_APA_dflt>, front=0, rear=2, cpu_to_preempt=0x207dc0 <_ISR_Stack_area_begin+2688>) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/schedulerstrongapa.c:457<br>457 max_priority_num = 0; //Max (Lowest) priority encountered so far.<br>(gdb) ni<br>0x00118d70 457 max_priority_num = 0; //Max (Lowest) priority encountered so far.<br>(gdb) <br>458 CPU = self->CPU;<br>(gdb) <br>0x00118d76 458 CPU = self->CPU;<br>(gdb) <br>0x00118d78 458 CPU = self->CPU;<br>(gdb) <br>459 cpu_max = _SMP_Get_processor_maximum();<br>(gdb) <br>0x00118d7e 459 cpu_max = _SMP_Get_processor_maximum();<br>(gdb) <br>461 while( front <= rear ) {<br>(gdb) <br>461 while( front <= rear ) {<br>(gdb) <br>0x00118e82 461 while( front <= rear ) {<br>(gdb) <br>0x00118e84 461 while( front <= rear ) {<br>(gdb) <br>0x00118e86 461 while( front <= rear ) {<br>(gdb) <br>462 curr_CPU = CPU[ front ].cpu;<br>(gdb) <br>0x00118d84 462 curr_CPU = CPU[ front ].cpu;<br>(gdb) <br>0x00118d86 462 curr_CPU = CPU[ front ].cpu;<br>(gdb) <br>0x00118d88 462 curr_CPU = CPU[ front ].cpu;<br>(gdb) <br>0x00118d8a 462 curr_CPU = CPU[ front ].cpu;<br>(gdb) <br>0x00118d8c 462 curr_CPU = CPU[ front ].cpu;<br>(gdb) <br>463 front = front + 1;<br>(gdb) <br>0x00118d90 463 front = front + 1;<br>(gdb) <br>0x00118d92 463 front = front + 1;<br>(gdb) <br>465 curr_node = CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing;<br>(gdb) <br>0x00118d96 465 curr_node = CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing;<br>(gdb) _Per_CPU_Get_index( curr_CPU )<br>Undefined command: "_Per_CPU_Get_index". Try "help".<br>(gdb) p _Per_CPU_Get_index( curr_CPU )<br>$1 = 0<br>(gdb) p CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing;<br>Invalid character ';' in expression.<br>(gdb) p CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing<br>$2 = (Scheduler_Node *) 0x0<br>(gdb) p curr_CPU->heir<br>$3 = (struct _Thread_Control *) 0x200690 <_Thread_Objects><br>(gdb) bt<br>#0 0x00118d96 in _Scheduler_strong_APA_Get_lowest_reachable (self=0x200620 <_Configuration_Scheduler_strong_APA_dflt>, front=1, rear=2, cpu_to_preempt=0x207dc0 <_ISR_Stack_area_begin+2688>) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/schedulerstrongapa.c:465<br>#1 0x001190fc in _Scheduler_strong_APA_Enqueue (context=0x200620 <_Configuration_Scheduler_strong_APA_dflt>, node=0x201938 <_RTEMS_tasks_Objects+600>, insert_priority=3) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/schedulerstrongapa.c:640<br>#2 0x00118194 in _Scheduler_SMP_Unblock (context=0x200620 <_Configuration_Scheduler_strong_APA_dflt>, thread=0x2016e0 <_RTEMS_tasks_Objects>, node=0x201938 <_RTEMS_tasks_Objects+600>, update=0x118867 <_Scheduler_strong_APA_Do_update>, enqueue=0x11904b <_Scheduler_strong_APA_Enqueue>) at /home/richi/quick-start/src/rtems/cpukit/include/rtems/score/schedulersmpimpl.h:1279<br>#3 0x001192fa in _Scheduler_strong_APA_Unblock (scheduler=0x11ffc0 <_Scheduler_Table>, thread=0x2016e0 <_RTEMS_tasks_Objects>, node=0x201938 <_RTEMS_tasks_Objects+600>) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/schedulerstrongapa.c:777<br>#4 0x0010c500 in _Scheduler_Unblock (the_thread=0x2016e0 <_RTEMS_tasks_Objects>) at /home/richi/quick-start/src/rtems/cpukit/include/rtems/score/schedulerimpl.h:322<br>#5 0x0010c550 in _Thread_Clear_state_locked (the_thread=0x2016e0 <_RTEMS_tasks_Objects>, state=4294967295) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/threadclearstate.c:44<br>#6 0x0010f7de in _Thread_Start (the_thread=0x2016e0 <_RTEMS_tasks_Objects>, entry=0x207ed4 <_ISR_Stack_area_begin+2964>, lock_context=0x207ed0 <_ISR_Stack_area_begin+2960>) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/score/src/threadstart.c:43<br>#7 0x00108658 in rtems_task_start (id=167837697, entry_point=0x1012ab <Init>, argument=2113828) at /home/richi/quick-start/src/rtems/c/src/../../cpukit/rtems/src/taskstart.c:56<br>#8 0x00107b0c in _RTEMS_tasks_Initialize_user_task () at /home/richi/quick-start/src/rtems/c/src/../../cpukit/rtems/src/taskinitusers.c:52<br>#9 0x00116d08 in rtems_initialize_executive () at /home/richi/quick-start/src/rtems/c/src/../../cpukit/sapi/src/exinit.c:127<br>#10 0x00101ffc in boot_card (cmdline=0x0) at /home/richi/quick-start/src/rtems/c/src/lib/libbsp/arm/realview-pbx-a9/../../../../../../bsps/shared/start/bootcard.c:55<br>#11 0x0010014a in bsp_start_hook_0_done () at /home/richi/quick-start/src/rtems/c/src/lib/libbsp/arm/realview-pbx-a9/../../../../../../bsps/arm/shared/start/start.S:436<br>#12 0x0010014a in bsp_start_hook_0_done () at /home/richi/quick-start/src/rtems/c/src/lib/libbsp/arm/realview-pbx-a9/../../../../../../bsps/arm/shared/start/start.S:436<br>#13 0x0010014a in bsp_start_hook_0_done () at /home/richi/quick-start/src/rtems/c/src/lib/libbsp/arm/realview-pbx-a9/../../../../../../bsps/arm/shared/start/start.S:436</div>----------------------------------------------------------------------------------------------------------------------------------------<br><div>Thank you.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Aug 26, 2020 at 8:54 PM Richi Dubey <<a href="mailto:richidubey@gmail.com">richidubey@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">---<br>
cpukit/include/rtems/scheduler.h | 6 +-<br>
.../include/rtems/score/schedulerstrongapa.h | 154 ++-<br>
cpukit/score/src/schedulerstrongapa.c | 901 ++++++++++++++----<br>
3 files changed, 829 insertions(+), 232 deletions(-)<br>
<br>
diff --git a/cpukit/include/rtems/scheduler.h b/cpukit/include/rtems/scheduler.h<br>
index 955a83cfb4..6a05c2798a 100644<br>
--- a/cpukit/include/rtems/scheduler.h<br>
+++ b/cpukit/include/rtems/scheduler.h<br>
@@ -257,16 +257,14 @@<br>
#define RTEMS_SCHEDULER_STRONG_APA( name, prio_count ) \<br>
static struct { \<br>
Scheduler_strong_APA_Context Base; \<br>
- Chain_Control Ready[ ( prio_count ) ]; \<br>
+ Scheduler_strong_APA_CPU CPU[ CONFIGURE_MAXIMUM_PROCESSORS ]; \<br>
} SCHEDULER_STRONG_APA_CONTEXT_NAME( name )<br>
<br>
#define RTEMS_SCHEDULER_TABLE_STRONG_APA( name, obj_name ) \<br>
{ \<br>
&SCHEDULER_STRONG_APA_CONTEXT_NAME( name ).Base.Base.Base, \<br>
SCHEDULER_STRONG_APA_ENTRY_POINTS, \<br>
- RTEMS_ARRAY_SIZE( \<br>
- SCHEDULER_STRONG_APA_CONTEXT_NAME( name ).Ready \<br>
- ) - 1, \<br>
+ SCHEDULER_STRONG_APA_MAXIMUM_PRIORITY, \<br>
( obj_name ) \<br>
SCHEDULER_CONTROL_IS_NON_PREEMPT_MODE_SUPPORTED( false ) \<br>
}<br>
diff --git a/cpukit/include/rtems/score/schedulerstrongapa.h b/cpukit/include/rtems/score/schedulerstrongapa.h<br>
index 0ac28cb439..2476984cc4 100644<br>
--- a/cpukit/include/rtems/score/schedulerstrongapa.h<br>
+++ b/cpukit/include/rtems/score/schedulerstrongapa.h<br>
@@ -5,32 +5,48 @@<br>
*<br>
* @brief Strong APA Scheduler API<br>
*/<br>
-<br>
-/*<br>
- * Copyright (c) 2013, 2018 embedded brains GmbH. All rights reserved.<br>
+ <br>
+/* SPDX-License-Identifier: BSD-2-Clause <br>
+ *<br>
+ * Copyright (C) 2020 Richi Dubey<br>
+ * Copyright (c) 2013, 2018 embedded brains GmbH<br>
*<br>
- * embedded brains GmbH<br>
- * Dornierstr. 4<br>
- * 82178 Puchheim<br>
- * Germany<br>
- * <<a href="mailto:rtems@embedded-brains.de" target="_blank">rtems@embedded-brains.de</a>><br>
+ * Redistribution and use in source and binary forms, with or without<br>
+ * modification, are permitted provided that the following conditions<br>
+ * are met:<br>
+ * 1. Redistributions of source code must retain the above copyright<br>
+ * notice, this list of conditions and the following disclaimer.<br>
+ * 2. Redistributions in binary form must reproduce the above copyright<br>
+ * notice, this list of conditions and the following disclaimer in the<br>
+ * documentation and/or other materials provided with the distribution.<br>
*<br>
- * The license and distribution terms for this file may be<br>
- * found in the file LICENSE in this distribution or at<br>
- * <a href="http://www.rtems.org/license/LICENSE" rel="noreferrer" target="_blank">http://www.rtems.org/license/LICENSE</a>.<br>
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"<br>
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE<br>
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE<br>
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE<br>
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR<br>
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF<br>
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS<br>
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN<br>
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)<br>
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE<br>
+ * POSSIBILITY OF SUCH DAMAGE.<br>
*/<br>
<br>
#ifndef _RTEMS_SCORE_SCHEDULERSTRONGAPA_H<br>
#define _RTEMS_SCORE_SCHEDULERSTRONGAPA_H<br>
<br>
#include <rtems/score/scheduler.h><br>
-#include <rtems/score/schedulerpriority.h><br>
#include <rtems/score/schedulersmp.h><br>
+#include <rtems/score/percpu.h><br>
<br>
#ifdef __cplusplus<br>
extern "C" {<br>
#endif /* __cplusplus */<br>
<br>
+#define STRONG_SCHEDULER_NODE_OF_CHAIN( node ) \<br>
+ RTEMS_CONTAINER_OF( node, Scheduler_strong_APA_Node, Ready_node )<br>
+<br>
/**<br>
* @defgroup RTEMSScoreSchedulerStrongAPA Strong APA Scheduler<br>
*<br>
@@ -38,43 +54,97 @@ extern "C" {<br>
*<br>
* @brief Strong APA Scheduler<br>
*<br>
- * This is an implementation of the global fixed priority scheduler (G-FP). It<br>
- * uses one ready chain per priority to ensure constant time insert operations.<br>
- * The scheduled chain uses linear insert operations and has at most processor<br>
- * count entries. Since the processor and priority count are constants all<br>
- * scheduler operations complete in a bounded execution time.<br>
- *<br>
- * The the_thread preempt mode will be ignored.<br>
+ * This is an implementation of the Strong APA scheduler defined by<br>
+ * Cerqueira et al. in Linux's Processor Affinity API, Refined: <br>
+ * Shifting Real-Time Tasks Towards Higher Schedulability.<br>
*<br>
+ * The scheduled and ready nodes are accessed via the <br>
+ * Scheduler_strong_APA_Context::Ready which helps in backtracking when a <br>
+ * node which is executing on a CPU gets blocked. New node is allocated to<br>
+ * the cpu by checking all the executing nodes in the affinity set of the<br>
+ * node and the subsequent nodes executing on the processors in its <br>
+ * affinity set.<br>
* @{<br>
*/<br>
<br>
/**<br>
- * @brief Scheduler context specialization for Strong APA<br>
- * schedulers.<br>
- */<br>
-typedef struct {<br>
- Scheduler_SMP_Context Base;<br>
- Priority_bit_map_Control Bit_map;<br>
- Chain_Control Ready[ RTEMS_ZERO_LENGTH_ARRAY ];<br>
-} Scheduler_strong_APA_Context;<br>
-<br>
-/**<br>
- * @brief Scheduler node specialization for Strong APA<br>
- * schedulers.<br>
+ * @brief Scheduler node specialization for Strong APA schedulers.<br>
*/<br>
typedef struct {<br>
/**<br>
* @brief SMP scheduler node.<br>
*/<br>
Scheduler_SMP_Node Base;<br>
+ <br>
+ /**<br>
+ * @brief Chain node for Scheduler_strong_APA_Context::Ready.<br>
+ */<br>
+ Chain_Node Ready_node;<br>
+ <br>
+ /**<br>
+ * @brief CPU that this node would preempt in the backtracking part of<br>
+ * _Scheduler_strong_APA_Get_highest_ready and<br>
+ * _Scheduler_strong_APA_Do_Enqueue.<br>
+ */<br>
+ Per_CPU_Control *cpu_to_preempt;<br>
<br>
/**<br>
- * @brief The associated ready queue of this node.<br>
+ * @brief The associated affinity set of this node.<br>
*/<br>
- Scheduler_priority_Ready_queue Ready_queue;<br>
+ Processor_mask Affinity;<br>
} Scheduler_strong_APA_Node;<br>
<br>
+<br>
+/**<br>
+ * @brief CPU related variables and a CPU_Control to implement BFS.<br>
+ */<br>
+typedef struct<br>
+{<br>
+ /**<br>
+ * @brief CPU in a queue.<br>
+ */ <br>
+ Per_CPU_Control *cpu;<br>
+ <br>
+ /**<br>
+ * @brief The node that would preempt this CPU.<br>
+ */ <br>
+ Scheduler_Node *preempting_node;<br>
+ <br>
+ /**<br>
+ * @brief Whether or not this cpu has been added to the queue<br>
+ * (visited in BFS).<br>
+ */ <br>
+ bool visited;<br>
+ <br>
+ /**<br>
+ * @brief The node currently executing on this cpu<br>
+ */ <br>
+ Scheduler_Node *executing;<br>
+} Scheduler_strong_APA_CPU;<br>
+<br>
+ /**<br>
+ * @brief Scheduler context and node definition for Strong APA scheduler.<br>
+ */<br>
+typedef struct {<br>
+ /**<br>
+ * @brief @see Scheduler_SMP_Context.<br>
+ */<br>
+ Scheduler_SMP_Context Base;<br>
+ <br>
+ /**<br>
+ * @brief Chain of all the ready and scheduled nodes present in<br>
+ * the Strong APA scheduler.<br>
+ */<br>
+ Chain_Control Ready;<br>
+ <br>
+ /**<br>
+ * @brief Struct with important variables for each cpu.<br>
+ */<br>
+ Scheduler_strong_APA_CPU CPU[ RTEMS_ZERO_LENGTH_ARRAY ];<br>
+} Scheduler_strong_APA_Context;<br>
+<br>
+#define SCHEDULER_STRONG_APA_MAXIMUM_PRIORITY 255<br>
+<br>
/**<br>
* @brief Entry points for the Strong APA Scheduler.<br>
*/<br>
@@ -100,8 +170,8 @@ typedef struct {<br>
_Scheduler_default_Release_job, \<br>
_Scheduler_default_Cancel_job, \<br>
_Scheduler_default_Tick, \<br>
- _Scheduler_SMP_Start_idle \<br>
- SCHEDULER_OPERATION_DEFAULT_GET_SET_AFFINITY \<br>
+ _Scheduler_SMP_Start_idle, \<br>
+ _Scheduler_strong_APA_Set_affinity \<br>
}<br>
<br>
/**<br>
@@ -246,6 +316,20 @@ void _Scheduler_strong_APA_Yield(<br>
Scheduler_Node *node<br>
);<br>
<br>
+/**<br>
+ * @brief Sets the affinity .<br>
+ *<br>
+ * @param scheduler The scheduler control instance.<br>
+ * @param the_thread The thread to yield.<br>
+ * @param[in, out] node The node of @a the_thread.<br>
+ */<br>
+bool _Scheduler_strong_APA_Set_affinity(<br>
+ const Scheduler_Control *scheduler,<br>
+ Thread_Control *thread,<br>
+ Scheduler_Node *node_base,<br>
+ const Processor_mask *affinity<br>
+);<br>
+<br>
/** @} */<br>
<br>
#ifdef __cplusplus<br>
diff --git a/cpukit/score/src/schedulerstrongapa.c b/cpukit/score/src/schedulerstrongapa.c<br>
index 924cd86412..429bbacece 100644<br>
--- a/cpukit/score/src/schedulerstrongapa.c<br>
+++ b/cpukit/score/src/schedulerstrongapa.c<br>
@@ -6,18 +6,31 @@<br>
* @brief Strong APA Scheduler Implementation<br>
*/<br>
<br>
-/*<br>
- * Copyright (c) 2013, 2016 embedded brains GmbH. All rights reserved.<br>
+/* SPDX-License-Identifier: BSD-2-Clause<br>
+ *<br>
+ * Copyright (C) 2020 Richi Dubey<br>
+ * Copyright (c) 2013, 2018 embedded brains GmbH<br>
*<br>
- * embedded brains GmbH<br>
- * Dornierstr. 4<br>
- * 82178 Puchheim<br>
- * Germany<br>
- * <<a href="mailto:rtems@embedded-brains.de" target="_blank">rtems@embedded-brains.de</a>><br>
+ * Redistribution and use in source and binary forms, with or without<br>
+ * modification, are permitted provided that the following conditions<br>
+ * are met:<br>
+ * 1. Redistributions of source code must retain the above copyright<br>
+ * notice, this list of conditions and the following disclaimer.<br>
+ * 2. Redistributions in binary form must reproduce the above copyright<br>
+ * notice, this list of conditions and the following disclaimer in the<br>
+ * documentation and/or other materials provided with the distribution.<br>
*<br>
- * The license and distribution terms for this file may be<br>
- * found in the file LICENSE in this distribution or at<br>
- * <a href="http://www.rtems.org/license/LICENSE" rel="noreferrer" target="_blank">http://www.rtems.org/license/LICENSE</a>.<br>
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"<br>
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE<br>
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE<br>
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE<br>
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR<br>
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF<br>
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS<br>
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN<br>
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)<br>
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE<br>
+ * POSSIBILITY OF SUCH DAMAGE.<br>
*/<br>
<br>
#ifdef HAVE_CONFIG_H<br>
@@ -25,301 +38,754 @@<br>
#endif<br>
<br>
#include <rtems/score/schedulerstrongapa.h><br>
-#include <rtems/score/schedulerpriorityimpl.h><br>
#include <rtems/score/schedulersmpimpl.h><br>
+#include <rtems/score/assert.h><br>
<br>
-static Scheduler_strong_APA_Context *_Scheduler_strong_APA_Get_self(<br>
- Scheduler_Context *context<br>
-)<br>
+static inline Scheduler_strong_APA_Context *<br>
+_Scheduler_strong_APA_Get_context( const Scheduler_Control *scheduler )<br>
+{<br>
+ return (Scheduler_strong_APA_Context *) _Scheduler_Get_context( scheduler );<br>
+}<br>
+<br>
+static inline Scheduler_strong_APA_Context *<br>
+_Scheduler_strong_APA_Get_self( Scheduler_Context *context )<br>
{<br>
return (Scheduler_strong_APA_Context *) context;<br>
}<br>
<br>
-static Scheduler_strong_APA_Node *<br>
+static inline Scheduler_strong_APA_Node *<br>
_Scheduler_strong_APA_Node_downcast( Scheduler_Node *node )<br>
{<br>
return (Scheduler_strong_APA_Node *) node;<br>
}<br>
<br>
-static void _Scheduler_strong_APA_Move_from_scheduled_to_ready(<br>
+static inline void _Scheduler_strong_APA_Do_update(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *scheduled_to_ready<br>
+ Scheduler_Node *node,<br>
+ Priority_Control new_priority<br>
)<br>
{<br>
- Scheduler_strong_APA_Context *self =<br>
- _Scheduler_strong_APA_Get_self( context );<br>
- Scheduler_strong_APA_Node *node =<br>
- _Scheduler_strong_APA_Node_downcast( scheduled_to_ready );<br>
-<br>
- _Chain_Extract_unprotected( &node->Base.Base.Node.Chain );<br>
- _Scheduler_priority_Ready_queue_enqueue_first(<br>
- &node->Base.Base.Node.Chain,<br>
- &node->Ready_queue,<br>
- &self->Bit_map<br>
- );<br>
+ Scheduler_SMP_Node *smp_node;<br>
+ (void) context;<br>
+<br>
+ smp_node = _Scheduler_SMP_Node_downcast( node );<br>
+ _Scheduler_SMP_Node_update_priority( smp_node, new_priority );<br>
}<br>
<br>
-static void _Scheduler_strong_APA_Move_from_ready_to_scheduled(<br>
+/*<br>
+ * Returns true if the Strong APA scheduler has ready nodes<br>
+ * available for scheduling.<br>
+ */<br>
+static inline bool<br>
+ _Scheduler_strong_APA_Has_ready( Scheduler_Context *context )<br>
+{<br>
+ Scheduler_strong_APA_Context *self;<br>
+ const Chain_Node *tail;<br>
+ Chain_Node *next;<br>
+ Scheduler_strong_APA_Node *node;<br>
+<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ tail = _Chain_Immutable_tail( &self->Ready );<br>
+ next = _Chain_First( &self->Ready );<br>
+<br>
+ while ( next != tail ) {<br>
+ node = (Scheduler_strong_APA_Node *) STRONG_SCHEDULER_NODE_OF_CHAIN( next );<br>
+<br>
+ if (<br>
+ _Scheduler_SMP_Node_state( &node->Base.Base ) ==<br>
+ SCHEDULER_SMP_NODE_READY<br>
+ ) {<br>
+ return true;<br>
+ }<br>
+<br>
+ next = _Chain_Next( next );<br>
+ }<br>
+<br>
+ return false;<br>
+}<br>
+<br>
+static inline void _Scheduler_strong_APA_Allocate_processor(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *ready_to_scheduled<br>
+ Scheduler_Node *scheduled_base,<br>
+ Scheduler_Node *victim_base,<br>
+ Per_CPU_Control *victim_cpu<br>
)<br>
{<br>
+ Scheduler_strong_APA_Node *scheduled;<br>
Scheduler_strong_APA_Context *self;<br>
- Scheduler_strong_APA_Node *node;<br>
- Priority_Control insert_priority;<br>
<br>
+ (void) victim_base;<br>
+<br>
+ scheduled = _Scheduler_strong_APA_Node_downcast( scheduled_base );<br>
self = _Scheduler_strong_APA_Get_self( context );<br>
- node = _Scheduler_strong_APA_Node_downcast( ready_to_scheduled );<br>
<br>
- _Scheduler_priority_Ready_queue_extract(<br>
- &node->Base.Base.Node.Chain,<br>
- &node->Ready_queue,<br>
- &self->Bit_map<br>
+ self->CPU[ _Per_CPU_Get_index( victim_cpu ) ].executing = scheduled_base;<br>
+<br>
+ _Scheduler_SMP_Allocate_processor_exact(<br>
+ context,<br>
+ &(scheduled->Base.Base),<br>
+ NULL,<br>
+ victim_cpu<br>
);<br>
- insert_priority = _Scheduler_SMP_Node_priority( &node->Base.Base );<br>
+}<br>
+<br>
+/*<br>
+ * Finds and returns the highest ready node present by accessing the<br>
+ * _Strong_APA_Context->CPU with front and rear values.<br>
+ */<br>
+<br>
+static inline Scheduler_Node * _Scheduler_strong_APA_Find_highest_ready(<br>
+ Scheduler_strong_APA_Context *self,<br>
+ uint32_t front,<br>
+ uint32_t rear<br>
+)<br>
+{<br>
+ Scheduler_Node *highest_ready;<br>
+ Scheduler_strong_APA_CPU *CPU;<br>
+ const Chain_Node *tail;<br>
+ Chain_Node *next;<br>
+ uint32_t index_assigned_cpu;<br>
+ Scheduler_strong_APA_Node *node;<br>
+ Priority_Control min_priority_num;<br>
+ Priority_Control curr_priority;<br>
+ Per_CPU_Control *assigned_cpu;<br>
+ Scheduler_SMP_Node_state curr_state;<br>
+ Per_CPU_Control *curr_CPU;<br>
+ bool first_task;<br>
+<br>
+ CPU = self->CPU;<br>
+ /*<br>
+ * When the first task accessed has nothing to compare its priority against<br>
+ * So, it is the task with the highest priority witnessed so far.<br>
+ */<br>
+ first_task = true;<br>
+<br>
+ //Assert rear < sizeof(Context->CPU)<br>
+ _Assert( rear < CONFIGURE_MAXIMUM_PROCESSOR );<br>
+<br>
+ while( front <= rear ) {<br>
+ curr_CPU = CPU[ front ].cpu;<br>
+ front = front + 1;<br>
+<br>
+ tail = _Chain_Immutable_tail( &self->Ready );<br>
+ next = _Chain_First( &self->Ready );<br>
+<br>
+ while ( next != tail ) {<br>
+ node = (Scheduler_strong_APA_Node*) STRONG_SCHEDULER_NODE_OF_CHAIN( next );<br>
+ //Check if the curr_CPU is in the affinity set of the node.<br>
+ if (<br>
+ _Processor_mask_Is_set(&node->Affinity, _Per_CPU_Get_index(curr_CPU))<br>
+ ) {<br>
+ curr_state = _Scheduler_SMP_Node_state( &node->Base.Base );<br>
+<br>
+ if ( curr_state == SCHEDULER_SMP_NODE_SCHEDULED ) {<br>
+ assigned_cpu = _Thread_Get_CPU( node->Base.Base.user );<br>
+ index_assigned_cpu = _Per_CPU_Get_index( assigned_cpu );<br>
+<br>
+ if ( CPU[ index_assigned_cpu ].visited == false ) {<br>
+ rear = rear + 1;<br>
+ CPU[ rear ].cpu = assigned_cpu;<br>
+ CPU[ index_assigned_cpu ].visited = true;<br>
+ /*<br>
+ * The curr CPU of the queue invoked this node to add its CPU<br>
+ * that it is executing on to the queue. So this node might get<br>
+ * preempted because of the invoker curr_CPU and this curr_CPU<br>
+ * is the CPU that node should preempt in case this node<br>
+ * gets preempted.<br>
+ */<br>
+ node->cpu_to_preempt = curr_CPU;<br>
+ }<br>
+ }<br>
+ else if ( curr_state == SCHEDULER_SMP_NODE_READY ) {<br>
+ curr_priority = _Scheduler_Node_get_priority( &node->Base.Base );<br>
+ curr_priority = SCHEDULER_PRIORITY_PURIFY( curr_priority );<br>
+<br>
+ if ( first_task == true || curr_priority < min_priority_num ) {<br>
+ min_priority_num = curr_priority;<br>
+ highest_ready = &node->Base.Base;<br>
+ first_task = false;<br>
+ /*<br>
+ * In case curr_CPU is filter_CPU, we need to store the<br>
+ * cpu_to_preempt value so that we go back to SMP_*<br>
+ * function, rather than preempting the node ourselves.<br>
+ */<br>
+ node->cpu_to_preempt = curr_CPU;<br>
+ }<br>
+ }<br>
+ }<br>
+ next = _Chain_Next( next );<br>
+ }<br>
+ }<br>
+<br>
+ return highest_ready;<br>
+}<br>
+<br>
+static inline void _Scheduler_strong_APA_Move_from_ready_to_scheduled(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *ready_to_scheduled<br>
+)<br>
+{<br>
+ Priority_Control insert_priority;<br>
+<br>
+ insert_priority = _Scheduler_SMP_Node_priority( ready_to_scheduled );<br>
insert_priority = SCHEDULER_PRIORITY_APPEND( insert_priority );<br>
- _Chain_Insert_ordered_unprotected(<br>
- &self->Base.Scheduled,<br>
- &node->Base.Base.Node.Chain,<br>
- &insert_priority,<br>
- _Scheduler_SMP_Priority_less_equal<br>
+ _Scheduler_SMP_Insert_scheduled(<br>
+ context,<br>
+ ready_to_scheduled,<br>
+ insert_priority<br>
);<br>
}<br>
<br>
-static void _Scheduler_strong_APA_Insert_ready(<br>
+/*<br>
+ * Implement the BFS Algorithm for task departure to get the highest ready task<br>
+ * for a particular CPU, returns the highest ready Scheduler_Node<br>
+ * Scheduler_Node filter here pointst to the victim node that is blocked<br>
+ * resulting which this function is called.<br>
+ */<br>
+static inline Scheduler_Node *_Scheduler_strong_APA_Get_highest_ready(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *node_base,<br>
- Priority_Control insert_priority<br>
+ Scheduler_Node *filter<br>
)<br>
{<br>
Scheduler_strong_APA_Context *self;<br>
+ Per_CPU_Control *filter_cpu;<br>
Scheduler_strong_APA_Node *node;<br>
+ Scheduler_Node *highest_ready;<br>
+ Scheduler_Node *curr_node;<br>
+ Scheduler_Node *next_node;<br>
+ Scheduler_strong_APA_CPU *CPU;<br>
+ uint32_t front;<br>
+ uint32_t rear;<br>
+ uint32_t cpu_max;<br>
+ uint32_t cpu_index;<br>
<br>
self = _Scheduler_strong_APA_Get_self( context );<br>
- node = _Scheduler_strong_APA_Node_downcast( node_base );<br>
+ //Denotes front and rear of the queue.<br>
+ front = 0;<br>
+ rear = -1;<br>
<br>
- if ( SCHEDULER_PRIORITY_IS_APPEND( insert_priority ) ) {<br>
- _Scheduler_priority_Ready_queue_enqueue(<br>
- &node->Base.Base.Node.Chain,<br>
- &node->Ready_queue,<br>
- &self->Bit_map<br>
- );<br>
- } else {<br>
- _Scheduler_priority_Ready_queue_enqueue_first(<br>
- &node->Base.Base.Node.Chain,<br>
- &node->Ready_queue,<br>
- &self->Bit_map<br>
- );<br>
+ filter_cpu = _Thread_Get_CPU( filter->user );<br>
+ CPU = self->CPU;<br>
+ cpu_max = _SMP_Get_processor_maximum();<br>
+<br>
+ for ( cpu_index = 0 ; cpu_index < cpu_max ; ++cpu_index ) {<br>
+ CPU[ cpu_index ].visited = false;<br>
}<br>
+<br>
+ rear = rear + 1;<br>
+ CPU[ rear ].cpu = filter_cpu;<br>
+ CPU[ _Per_CPU_Get_index( filter_cpu ) ].visited = true;<br>
+<br>
+ highest_ready = _Scheduler_strong_APA_Find_highest_ready(<br>
+ self,<br>
+ front,<br>
+ rear<br>
+ );<br>
+<br>
+ if ( highest_ready != filter ) {<br>
+ /*<br>
+ * Backtrack on the path from<br>
+ * filter_cpu to highest_ready, shifting along every task.<br>
+ */<br>
+<br>
+ node = _Scheduler_strong_APA_Node_downcast( highest_ready );<br>
+ /*<br>
+ * Highest ready is not just directly reachable from the victim cpu<br>
+ * So there is need of task shifting .<br>
+ */<br>
+ while( node->cpu_to_preempt != filter_cpu ){<br>
+ curr_node = &node->Base.Base;<br>
+ next_node = CPU[ _Per_CPU_Get_index( node->cpu_to_preempt ) ].executing;<br>
+<br>
+ _Scheduler_SMP_Preempt(<br>
+ context,<br>
+ curr_node,<br>
+ next_node,<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
+ );<br>
+<br>
+ if( curr_node == highest_ready) {<br>
+ _Scheduler_strong_APA_Move_from_ready_to_scheduled(context, curr_node);<br>
+ }<br>
+<br>
+ node = _Scheduler_strong_APA_Node_downcast( next_node );<br>
+ }<br>
+ /*<br>
+ * To save the last node so that the caller SMP_* function<br>
+ * can do the allocation<br>
+ */<br>
+ curr_node = &node->Base.Base;<br>
+ highest_ready = curr_node;<br>
+ }<br>
+<br>
+ return highest_ready;<br>
}<br>
<br>
-static void _Scheduler_strong_APA_Extract_from_ready(<br>
+/*<br>
+ * Checks the lowest scheduled directly reachable task<br>
+ */<br>
+static inline Scheduler_Node *_Scheduler_strong_APA_Get_lowest_scheduled(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *the_thread<br>
+ Scheduler_Node *filter_base<br>
)<br>
{<br>
- Scheduler_strong_APA_Context *self =<br>
- _Scheduler_strong_APA_Get_self( context );<br>
- Scheduler_strong_APA_Node *node =<br>
- _Scheduler_strong_APA_Node_downcast( the_thread );<br>
-<br>
- _Scheduler_priority_Ready_queue_extract(<br>
- &node->Base.Base.Node.Chain,<br>
- &node->Ready_queue,<br>
- &self->Bit_map<br>
- );<br>
+ uint32_t cpu_max;<br>
+ uint32_t cpu_index;<br>
+ Scheduler_Node *curr_node;<br>
+ Scheduler_Node *lowest_scheduled;<br>
+ Priority_Control max_priority_num;<br>
+ Priority_Control curr_priority;<br>
+ Scheduler_strong_APA_Node *filter_strong_node;<br>
+ Scheduler_strong_APA_Context *self;<br>
+<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ lowest_scheduled = NULL; // To remove compiler warning.<br>
+ max_priority_num = 0; // Max (Lowest) priority encountered so far.<br>
+ filter_strong_node = _Scheduler_strong_APA_Node_downcast( filter_base );<br>
+<br>
+ //lowest_scheduled is NULL if affinty of a node is 0<br>
+ _Assert( !_Processor_mask_Zero( &filter_strong_node->Affinity ) );<br>
+ cpu_max = _SMP_Get_processor_maximum();<br>
+<br>
+ for ( cpu_index = 0 ; cpu_index < cpu_max ; ++cpu_index ) {<br>
+ //Checks if the CPU is in the affinity set of filter_strong_node<br>
+ if ( _Processor_mask_Is_set( &filter_strong_node->Affinity, cpu_index) ) {<br>
+ Per_CPU_Control *cpu = _Per_CPU_Get_by_index( cpu_index );<br>
+<br>
+ if ( _Per_CPU_Is_processor_online( cpu ) ) {<br>
+ curr_node = self->CPU[ _Per_CPU_Get_index( cpu ) ].executing;<br>
+ curr_priority = _Scheduler_Node_get_priority( curr_node );<br>
+ curr_priority = SCHEDULER_PRIORITY_PURIFY( curr_priority );<br>
+<br>
+ if ( curr_priority > max_priority_num ) {<br>
+ lowest_scheduled = curr_node;<br>
+ max_priority_num = curr_priority;<br>
+ }<br>
+ }<br>
+ }<br>
+ }<br>
+<br>
+ _Assert( lowest_scheduled != NULL );<br>
+ return lowest_scheduled;<br>
}<br>
<br>
-static void _Scheduler_strong_APA_Do_update(<br>
+static inline void _Scheduler_strong_APA_Extract_from_scheduled(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *node_to_update,<br>
- Priority_Control new_priority<br>
+ Scheduler_Node *node_to_extract<br>
)<br>
{<br>
- Scheduler_strong_APA_Context *self =<br>
- _Scheduler_strong_APA_Get_self( context );<br>
- Scheduler_strong_APA_Node *node =<br>
- _Scheduler_strong_APA_Node_downcast( node_to_update );<br>
-<br>
- _Scheduler_SMP_Node_update_priority( &node->Base, new_priority );<br>
- _Scheduler_priority_Ready_queue_update(<br>
- &node->Ready_queue,<br>
- SCHEDULER_PRIORITY_UNMAP( new_priority ),<br>
- &self->Bit_map,<br>
- &self->Ready[ 0 ]<br>
- );<br>
+ Scheduler_strong_APA_Context *self;<br>
+ Scheduler_strong_APA_Node *node;<br>
+<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ node = _Scheduler_strong_APA_Node_downcast( node_to_extract );<br>
+<br>
+ _Scheduler_SMP_Extract_from_scheduled( &self->Base.Base, &node->Base.Base );<br>
+ //Not removing it from Ready since the node could go in the READY state.<br>
}<br>
<br>
-static Scheduler_strong_APA_Context *<br>
-_Scheduler_strong_APA_Get_context( const Scheduler_Control *scheduler )<br>
+static inline void _Scheduler_strong_APA_Extract_from_ready(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *node_to_extract<br>
+)<br>
{<br>
- return (Scheduler_strong_APA_Context *) _Scheduler_Get_context( scheduler );<br>
+ Scheduler_strong_APA_Context *self;<br>
+ Scheduler_strong_APA_Node *node;<br>
+<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ node = _Scheduler_strong_APA_Node_downcast( node_to_extract );<br>
+<br>
+ _Assert( !_Chain_Is_empty(self->Ready) );<br>
+ _Assert( !_Chain_Is_node_off_chain( &node->Ready_node ) );<br>
+<br>
+ _Chain_Extract_unprotected( &node->Ready_node ); //Removed from Ready<br>
+ _Chain_Set_off_chain( &node->Ready_node );<br>
}<br>
<br>
-void _Scheduler_strong_APA_Initialize( const Scheduler_Control *scheduler )<br>
+static inline void _Scheduler_strong_APA_Insert_ready(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *node_base,<br>
+ Priority_Control insert_priority<br>
+)<br>
{<br>
- Scheduler_strong_APA_Context *self =<br>
- _Scheduler_strong_APA_Get_context( scheduler );<br>
+ Scheduler_strong_APA_Context *self;<br>
+ Scheduler_strong_APA_Node *node;<br>
<br>
- _Scheduler_SMP_Initialize( &self->Base );<br>
- _Priority_bit_map_Initialize( &self->Bit_map );<br>
- _Scheduler_priority_Ready_queue_initialize(<br>
- &self->Ready[ 0 ],<br>
- scheduler->maximum_priority<br>
- );<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ node = _Scheduler_strong_APA_Node_downcast( node_base );<br>
+<br>
+ if( _Chain_Is_node_off_chain( &node->Ready_node ) ) {<br>
+ _Chain_Append_unprotected( &self->Ready, &node->Ready_node );<br>
+ }<br>
}<br>
<br>
-void _Scheduler_strong_APA_Node_initialize(<br>
- const Scheduler_Control *scheduler,<br>
- Scheduler_Node *node,<br>
- Thread_Control *the_thread,<br>
- Priority_Control priority<br>
+static inline void _Scheduler_strong_APA_Move_from_scheduled_to_ready(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *scheduled_to_ready<br>
)<br>
{<br>
- Scheduler_Context *context;<br>
- Scheduler_strong_APA_Context *self;<br>
- Scheduler_strong_APA_Node *the_node;<br>
+ Priority_Control insert_priority;<br>
<br>
- the_node = _Scheduler_strong_APA_Node_downcast( node );<br>
- _Scheduler_SMP_Node_initialize(<br>
- scheduler,<br>
- &the_node->Base,<br>
- the_thread,<br>
- priority<br>
- );<br>
+ _Scheduler_SMP_Extract_from_scheduled( context, scheduled_to_ready );<br>
+ insert_priority = _Scheduler_SMP_Node_priority( scheduled_to_ready );<br>
<br>
- context = _Scheduler_Get_context( scheduler );<br>
- self = _Scheduler_strong_APA_Get_self( context );<br>
- _Scheduler_priority_Ready_queue_update(<br>
- &the_node->Ready_queue,<br>
- SCHEDULER_PRIORITY_UNMAP( priority ),<br>
- &self->Bit_map,<br>
- &self->Ready[ 0 ]<br>
+ _Scheduler_strong_APA_Insert_ready(<br>
+ context,<br>
+ scheduled_to_ready,<br>
+ insert_priority<br>
);<br>
}<br>
<br>
-static bool _Scheduler_strong_APA_Has_ready( Scheduler_Context *context )<br>
+static inline Scheduler_Node* _Scheduler_strong_APA_Get_lowest_reachable(<br>
+ Scheduler_strong_APA_Context *self,<br>
+ uint32_t front,<br>
+ uint32_t rear,<br>
+ Per_CPU_Control **cpu_to_preempt<br>
+)<br>
{<br>
- Scheduler_strong_APA_Context *self =<br>
- _Scheduler_strong_APA_Get_self( context );<br>
+ Scheduler_Node *lowest_reachable;<br>
+ Priority_Control max_priority_num;<br>
+ uint32_t cpu_max;<br>
+ uint32_t cpu_index;<br>
+ Thread_Control *curr_thread;<br>
+ Per_CPU_Control *curr_CPU;<br>
+ Priority_Control curr_priority;<br>
+ Scheduler_Node *curr_node;<br>
+ Scheduler_strong_APA_Node *curr_strong_node; //Current Strong_APA_Node<br>
+ Scheduler_strong_APA_CPU *CPU;<br>
+<br>
+ max_priority_num = 0; //Max (Lowest) priority encountered so far.<br>
+ CPU = self->CPU;<br>
+ cpu_max = _SMP_Get_processor_maximum();<br>
+<br>
+ while( front <= rear ) {<br>
+ curr_CPU = CPU[ front ].cpu;<br>
+ front = front + 1;<br>
+<br>
+ curr_node = CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing;<br>
+ curr_thread = curr_node->user;<br>
+<br>
+ curr_priority = _Scheduler_Node_get_priority( curr_node );<br>
+ curr_priority = SCHEDULER_PRIORITY_PURIFY( curr_priority );<br>
+<br>
+ curr_strong_node = _Scheduler_strong_APA_Node_downcast( curr_node );<br>
+<br>
+ if ( curr_priority > max_priority_num ) {<br>
+ lowest_reachable = curr_node;<br>
+ max_priority_num = curr_priority;<br>
+ *cpu_to_preempt = curr_CPU;<br>
+ }<br>
+<br>
+ if ( !curr_thread->is_idle ) {<br>
+ for ( cpu_index = 0 ; cpu_index < cpu_max ; ++cpu_index ) {<br>
+ if ( _Processor_mask_Is_set( &curr_strong_node->Affinity, cpu_index ) ) {<br>
+ //Checks if the thread_CPU is in the affinity set of the node<br>
+ Per_CPU_Control *cpu = _Per_CPU_Get_by_index( cpu_index );<br>
+ if ( _Per_CPU_Is_processor_online( cpu ) && CPU[ cpu_index ].visited == false ) {<br>
+ rear = rear + 1;<br>
+ CPU[ rear ].cpu = cpu;<br>
+ CPU[ cpu_index ].visited = true;<br>
+ CPU[ cpu_index ].preempting_node = curr_node;<br>
+ }<br>
+ }<br>
+ }<br>
+ }<br>
+ }<br>
<br>
- return !_Priority_bit_map_Is_empty( &self->Bit_map );<br>
+ return lowest_reachable;<br>
}<br>
<br>
-static Scheduler_Node *_Scheduler_strong_APA_Get_highest_ready(<br>
+static inline bool _Scheduler_strong_APA_Do_enqueue(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *node<br>
+ Scheduler_Node *lowest_reachable,<br>
+ Scheduler_Node *node,<br>
+ Priority_Control insert_priority,<br>
+ Per_CPU_Control *cpu_to_preempt<br>
)<br>
{<br>
- Scheduler_strong_APA_Context *self =<br>
- _Scheduler_strong_APA_Get_self( context );<br>
+ bool needs_help;<br>
+ Priority_Control node_priority;<br>
+ Priority_Control lowest_priority;<br>
+ Scheduler_strong_APA_CPU *CPU;<br>
+ Scheduler_Node *curr_node;<br>
+ Scheduler_strong_APA_Node *curr_strong_node; //Current Strong_APA_Node<br>
+ Per_CPU_Control *curr_CPU;<br>
+ Scheduler_strong_APA_Context *self;<br>
+ Scheduler_Node *next_node;<br>
+<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ CPU = self->CPU;<br>
+<br>
+ node_priority = _Scheduler_Node_get_priority( node );<br>
+ node_priority = SCHEDULER_PRIORITY_PURIFY( node_priority );<br>
+<br>
+ lowest_priority = _Scheduler_Node_get_priority( lowest_reachable );<br>
+ lowest_priority = SCHEDULER_PRIORITY_PURIFY( lowest_priority );<br>
+<br>
+ if( lowest_priority > node_priority ) {<br>
+ //Backtrack on the path from<br>
+ //_Thread_Get_CPU(lowest_reachable->user) to lowest_reachable, shifting<br>
+ //along every task<br>
+<br>
+ curr_node = CPU[ _Per_CPU_Get_index(cpu_to_preempt) ].preempting_node;<br>
+ curr_strong_node = _Scheduler_strong_APA_Node_downcast( curr_node );<br>
+ curr_strong_node->cpu_to_preempt = cpu_to_preempt;<br>
+<br>
+ //Save which cpu to preempt in cpu_to_preempt value of the node<br>
+ while ( curr_node != node ) {<br>
+ curr_CPU = _Thread_Get_CPU( curr_node->user );<br>
+ curr_node = CPU[ _Per_CPU_Get_index( curr_CPU ) ].preempting_node;<br>
+ curr_strong_node = _Scheduler_strong_APA_Node_downcast( curr_node );<br>
+ curr_strong_node->cpu_to_preempt = curr_CPU;<br>
+ }<br>
+<br>
+ curr_CPU = curr_strong_node->cpu_to_preempt;<br>
+ next_node = CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing;<br>
+<br>
+ node_priority = _Scheduler_Node_get_priority( curr_node );<br>
+ node_priority = SCHEDULER_PRIORITY_PURIFY( node_priority );<br>
+<br>
+ _Scheduler_SMP_Enqueue_to_scheduled(<br>
+ context,<br>
+ curr_node,<br>
+ node_priority,<br>
+ next_node,<br>
+ _Scheduler_SMP_Insert_scheduled,<br>
+ _Scheduler_strong_APA_Move_from_scheduled_to_ready,<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
+ );<br>
<br>
- (void) node;<br>
+ curr_node = next_node;<br>
+ curr_strong_node = _Scheduler_strong_APA_Node_downcast( curr_node );<br>
<br>
- return (Scheduler_Node *) _Scheduler_priority_Ready_queue_first(<br>
- &self->Bit_map,<br>
- &self->Ready[ 0 ]<br>
- );<br>
+ while( curr_node != lowest_reachable ) {<br>
+ curr_CPU = curr_strong_node->cpu_to_preempt;<br>
+ next_node = CPU[ _Per_CPU_Get_index( curr_CPU ) ].executing;<br>
+ //curr_node preempts the next_node;<br>
+ _Scheduler_SMP_Preempt(<br>
+ context,<br>
+ curr_node,<br>
+ next_node,<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
+ );<br>
+<br>
+ curr_node = next_node;<br>
+ curr_strong_node = _Scheduler_strong_APA_Node_downcast( curr_node );<br>
+ }<br>
+<br>
+ _Scheduler_strong_APA_Move_from_scheduled_to_ready( context, lowest_reachable );<br>
+<br>
+ needs_help = false;<br>
+ } else {<br>
+ needs_help = true;<br>
+ }<br>
+<br>
+ //Add it to Ready chain since it is now either scheduled or just ready.<br>
+ _Scheduler_strong_APA_Insert_ready(context,node,insert_priority);<br>
+<br>
+ return needs_help;<br>
}<br>
<br>
-void _Scheduler_strong_APA_Block(<br>
- const Scheduler_Control *scheduler,<br>
- Thread_Control *the_thread,<br>
- Scheduler_Node *node<br>
+/*<br>
+ * BFS Algorithm for task arrival<br>
+ * Enqueue node either in the scheduled chain or in the ready chain.<br>
+ * node is the newly arrived node and is currently not scheduled.<br>
+ */<br>
+static inline bool _Scheduler_strong_APA_Enqueue(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *node,<br>
+ Priority_Control insert_priority<br>
)<br>
{<br>
- Scheduler_Context *context = _Scheduler_Get_context( scheduler );<br>
+ Scheduler_strong_APA_Context *self;<br>
+ Scheduler_strong_APA_CPU *CPU;<br>
+ uint32_t cpu_max;<br>
+ uint32_t cpu_index;<br>
+ Per_CPU_Control *cpu_to_preempt;<br>
+ Scheduler_Node *lowest_reachable;<br>
+ Scheduler_strong_APA_Node *strong_node;<br>
<br>
- _Scheduler_SMP_Block(<br>
+ //Denotes front and rear of the queue<br>
+ uint32_t front;<br>
+ uint32_t rear;<br>
+<br>
+ front = 0;<br>
+ rear = -1;<br>
+<br>
+ self = _Scheduler_strong_APA_Get_self( context );<br>
+ strong_node = _Scheduler_strong_APA_Node_downcast( node );<br>
+ cpu_max = _SMP_Get_processor_maximum();<br>
+ CPU = self->CPU;<br>
+<br>
+ for ( cpu_index = 0 ; cpu_index < cpu_max ; ++cpu_index ) {<br>
+ CPU[ cpu_index ].visited = false;<br>
+<br>
+ //Checks if the thread_CPU is in the affinity set of the node<br>
+ if ( _Processor_mask_Is_set( &strong_node->Affinity, cpu_index) ) {<br>
+ Per_CPU_Control *cpu = _Per_CPU_Get_by_index( cpu_index );<br>
+<br>
+ if ( _Per_CPU_Is_processor_online( cpu ) ) {<br>
+ rear = rear + 1;<br>
+ CPU[ rear ].cpu = cpu;<br>
+ CPU[ cpu_index ].visited = true;<br>
+ CPU[ cpu_index ].preempting_node = node;<br>
+ }<br>
+ }<br>
+ }<br>
+<br>
+ //This assert makes sure that there always exist an element in the<br>
+ // Queue when we start the queue traversal.<br>
+ _Assert( !_Processor_mask_Zero( &strong_node->Affinity ) );<br>
+<br>
+ lowest_reachable = _Scheduler_strong_APA_Get_lowest_reachable(<br>
+ self,<br>
+ front,<br>
+ rear,<br>
+ &cpu_to_preempt<br>
+ );<br>
+<br>
+ return _Scheduler_strong_APA_Do_enqueue(<br>
+ context,<br>
+ lowest_reachable,<br>
+ node,<br>
+ insert_priority,<br>
+ cpu_to_preempt<br>
+ );<br>
+}<br>
+<br>
+static inline bool _Scheduler_strong_APA_Enqueue_scheduled(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *node,<br>
+ Priority_Control insert_priority<br>
+)<br>
+{<br>
+ return _Scheduler_SMP_Enqueue_scheduled(<br>
context,<br>
- the_thread,<br>
node,<br>
- _Scheduler_SMP_Extract_from_scheduled,<br>
+ insert_priority,<br>
+ _Scheduler_SMP_Priority_less_equal,<br>
_Scheduler_strong_APA_Extract_from_ready,<br>
_Scheduler_strong_APA_Get_highest_ready,<br>
+ _Scheduler_strong_APA_Insert_ready,<br>
+ _Scheduler_SMP_Insert_scheduled,<br>
_Scheduler_strong_APA_Move_from_ready_to_scheduled,<br>
- _Scheduler_SMP_Allocate_processor_exact<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
);<br>
}<br>
<br>
-static bool _Scheduler_strong_APA_Enqueue(<br>
+static inline bool _Scheduler_strong_APA_Do_ask_for_help(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *node,<br>
- Priority_Control insert_priority<br>
+ Thread_Control *the_thread,<br>
+ Scheduler_Node *node<br>
)<br>
{<br>
- return _Scheduler_SMP_Enqueue(<br>
+ return _Scheduler_SMP_Ask_for_help(<br>
context,<br>
+ the_thread,<br>
node,<br>
- insert_priority,<br>
_Scheduler_SMP_Priority_less_equal,<br>
_Scheduler_strong_APA_Insert_ready,<br>
_Scheduler_SMP_Insert_scheduled,<br>
_Scheduler_strong_APA_Move_from_scheduled_to_ready,<br>
- _Scheduler_SMP_Get_lowest_scheduled,<br>
- _Scheduler_SMP_Allocate_processor_exact<br>
+ _Scheduler_strong_APA_Get_lowest_scheduled,<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
);<br>
}<br>
<br>
-static bool _Scheduler_strong_APA_Enqueue_scheduled(<br>
+static inline void _Scheduler_strong_APA_Register_idle(<br>
Scheduler_Context *context,<br>
- Scheduler_Node *node,<br>
- Priority_Control insert_priority<br>
+ Scheduler_Node *idle_base,<br>
+ Per_CPU_Control *cpu<br>
)<br>
{<br>
- return _Scheduler_SMP_Enqueue_scheduled(<br>
+ (void) context;<br>
+ (void) idle_base;<br>
+ (void) cpu;<br>
+ /*<br>
+ * We do not maintain a variable to access the scheduled<br>
+ * node for a CPU. So this function does nothing.<br>
+ */<br>
+}<br>
+<br>
+static inline void _Scheduler_strong_APA_Do_set_affinity(<br>
+ Scheduler_Context *context,<br>
+ Scheduler_Node *node_base,<br>
+ void *arg<br>
+)<br>
+{<br>
+ Scheduler_strong_APA_Node *node;<br>
+<br>
+ node = _Scheduler_strong_APA_Node_downcast( node_base );<br>
+ node->Affinity = *(( const Processor_mask *) arg);<br>
+}<br>
+<br>
+void _Scheduler_strong_APA_Initialize( const Scheduler_Control *scheduler )<br>
+{<br>
+ Scheduler_strong_APA_Context *self =<br>
+ _Scheduler_strong_APA_Get_context( scheduler );<br>
+<br>
+ _Scheduler_SMP_Initialize( &self->Base );<br>
+ _Chain_Initialize_empty( &self->Ready );<br>
+}<br>
+<br>
+void _Scheduler_strong_APA_Yield(<br>
+ const Scheduler_Control *scheduler,<br>
+ Thread_Control *thread,<br>
+ Scheduler_Node *node<br>
+)<br>
+{<br>
+ Scheduler_Context *context = _Scheduler_Get_context( scheduler );<br>
+<br>
+ _Scheduler_SMP_Yield(<br>
context,<br>
+ thread,<br>
node,<br>
- insert_priority,<br>
- _Scheduler_SMP_Priority_less_equal,<br>
_Scheduler_strong_APA_Extract_from_ready,<br>
- _Scheduler_strong_APA_Get_highest_ready,<br>
- _Scheduler_strong_APA_Insert_ready,<br>
- _Scheduler_SMP_Insert_scheduled,<br>
- _Scheduler_strong_APA_Move_from_ready_to_scheduled,<br>
- _Scheduler_SMP_Allocate_processor_exact<br>
+ _Scheduler_strong_APA_Enqueue,<br>
+ _Scheduler_strong_APA_Enqueue_scheduled<br>
);<br>
}<br>
<br>
-void _Scheduler_strong_APA_Unblock(<br>
+void _Scheduler_strong_APA_Block(<br>
const Scheduler_Control *scheduler,<br>
- Thread_Control *the_thread,<br>
+ Thread_Control *thread,<br>
Scheduler_Node *node<br>
)<br>
{<br>
Scheduler_Context *context = _Scheduler_Get_context( scheduler );<br>
-<br>
- _Scheduler_SMP_Unblock(<br>
+ //The extract from ready automatically removes the node from Ready chain.<br>
+ _Scheduler_SMP_Block(<br>
context,<br>
- the_thread,<br>
+ thread,<br>
node,<br>
- _Scheduler_strong_APA_Do_update,<br>
- _Scheduler_strong_APA_Enqueue<br>
+ _Scheduler_strong_APA_Extract_from_scheduled,<br>
+ _Scheduler_strong_APA_Extract_from_ready,<br>
+ _Scheduler_strong_APA_Get_highest_ready,<br>
+ _Scheduler_strong_APA_Move_from_ready_to_scheduled,<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
);<br>
}<br>
<br>
-static bool _Scheduler_strong_APA_Do_ask_for_help(<br>
- Scheduler_Context *context,<br>
- Thread_Control *the_thread,<br>
- Scheduler_Node *node<br>
+void _Scheduler_strong_APA_Unblock(<br>
+ const Scheduler_Control *scheduler,<br>
+ Thread_Control *thread,<br>
+ Scheduler_Node *node<br>
)<br>
{<br>
- return _Scheduler_SMP_Ask_for_help(<br>
+ Scheduler_Context *context = _Scheduler_Get_context( scheduler );<br>
+<br>
+ _Scheduler_SMP_Unblock(<br>
context,<br>
- the_thread,<br>
+ thread,<br>
node,<br>
- _Scheduler_SMP_Priority_less_equal,<br>
- _Scheduler_strong_APA_Insert_ready,<br>
- _Scheduler_SMP_Insert_scheduled,<br>
- _Scheduler_strong_APA_Move_from_scheduled_to_ready,<br>
- _Scheduler_SMP_Get_lowest_scheduled,<br>
- _Scheduler_SMP_Allocate_processor_lazy<br>
+ _Scheduler_strong_APA_Do_update,<br>
+ _Scheduler_strong_APA_Enqueue<br>
);<br>
}<br>
<br>
void _Scheduler_strong_APA_Update_priority(<br>
const Scheduler_Control *scheduler,<br>
- Thread_Control *the_thread,<br>
+ Thread_Control *thread,<br>
Scheduler_Node *node<br>
)<br>
{<br>
@@ -327,7 +793,7 @@ void _Scheduler_strong_APA_Update_priority(<br>
<br>
_Scheduler_SMP_Update_priority(<br>
context,<br>
- the_thread,<br>
+ thread,<br>
node,<br>
_Scheduler_strong_APA_Extract_from_ready,<br>
_Scheduler_strong_APA_Do_update,<br>
@@ -345,7 +811,11 @@ bool _Scheduler_strong_APA_Ask_for_help(<br>
{<br>
Scheduler_Context *context = _Scheduler_Get_context( scheduler );<br>
<br>
- return _Scheduler_strong_APA_Do_ask_for_help( context, the_thread, node );<br>
+ return _Scheduler_strong_APA_Do_ask_for_help(<br>
+ context,<br>
+ the_thread,<br>
+ node<br>
+ );<br>
}<br>
<br>
void _Scheduler_strong_APA_Reconsider_help_request(<br>
@@ -381,7 +851,7 @@ void _Scheduler_strong_APA_Withdraw_node(<br>
_Scheduler_strong_APA_Extract_from_ready,<br>
_Scheduler_strong_APA_Get_highest_ready,<br>
_Scheduler_strong_APA_Move_from_ready_to_scheduled,<br>
- _Scheduler_SMP_Allocate_processor_lazy<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
);<br>
}<br>
<br>
@@ -416,20 +886,65 @@ Thread_Control *_Scheduler_strong_APA_Remove_processor(<br>
);<br>
}<br>
<br>
-void _Scheduler_strong_APA_Yield(<br>
+void _Scheduler_strong_APA_Node_initialize(<br>
const Scheduler_Control *scheduler,<br>
+ Scheduler_Node *node,<br>
Thread_Control *the_thread,<br>
- Scheduler_Node *node<br>
+ Priority_Control priority<br>
)<br>
{<br>
- Scheduler_Context *context = _Scheduler_Get_context( scheduler );<br>
+ Scheduler_SMP_Node *smp_node;<br>
+ Scheduler_strong_APA_Node *strong_node;<br>
<br>
- _Scheduler_SMP_Yield(<br>
- context,<br>
- the_thread,<br>
- node,<br>
- _Scheduler_strong_APA_Extract_from_ready,<br>
- _Scheduler_strong_APA_Enqueue,<br>
- _Scheduler_strong_APA_Enqueue_scheduled<br>
+ smp_node = _Scheduler_SMP_Node_downcast( node );<br>
+ strong_node = _Scheduler_strong_APA_Node_downcast( node );<br>
+<br>
+ _Scheduler_SMP_Node_initialize( scheduler, smp_node, the_thread, priority );<br>
+<br>
+ _Processor_mask_Assign(<br>
+ &strong_node->Affinity,<br>
+ _SMP_Get_online_processors()<br>
);<br>
}<br>
+<br>
+bool _Scheduler_strong_APA_Set_affinity(<br>
+ const Scheduler_Control *scheduler,<br>
+ Thread_Control *thread,<br>
+ Scheduler_Node *node_base,<br>
+ const Processor_mask *affinity<br>
+)<br>
+{<br>
+ Scheduler_Context *context;<br>
+ Scheduler_strong_APA_Node *node;<br>
+ Processor_mask local_affinity;<br>
+<br>
+ context = _Scheduler_Get_context( scheduler );<br>
+ _Processor_mask_And( &local_affinity, &context->Processors, affinity );<br>
+<br>
+ if ( _Processor_mask_Is_zero( &local_affinity ) ) {<br>
+ return false;<br>
+ }<br>
+<br>
+ node = _Scheduler_strong_APA_Node_downcast( node_base );<br>
+<br>
+ if ( _Processor_mask_Is_equal( &node->Affinity, affinity ) )<br>
+ return true; //Nothing to do. Return true.<br>
+<br>
+ _Processor_mask_Assign( &node->Affinity, &local_affinity );<br>
+<br>
+ _Scheduler_SMP_Set_affinity(<br>
+ context,<br>
+ thread,<br>
+ node_base,<br>
+ &local_affinity,<br>
+ _Scheduler_strong_APA_Do_set_affinity,<br>
+ _Scheduler_strong_APA_Extract_from_ready,<br>
+ _Scheduler_strong_APA_Get_highest_ready,<br>
+ _Scheduler_strong_APA_Move_from_ready_to_scheduled,<br>
+ _Scheduler_strong_APA_Enqueue,<br>
+ _Scheduler_strong_APA_Allocate_processor<br>
+ );<br>
+<br>
+ return true;<br>
+}<br>
+<br>
-- <br>
2.17.1<br>
<br>
</blockquote></div>