1/*
2 * Copyright (c) 2023-2023 Huawei Device Co., Ltd. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without modification,
5 * are permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice, this list of
8 *    conditions and the following disclaimer.
9 *
10 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
11 *    of conditions and the following disclaimer in the documentation and/or other materials
12 *    provided with the distribution.
13 *
14 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
15 *    to endorse or promote products derived from this software without specific prior written
16 *    permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
20 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "los_sched_pri.h"
32#include "los_task_pri.h"
33#include "los_process_pri.h"
34#include "los_hook.h"
35#include "los_tick_pri.h"
36#include "los_sys_pri.h"
37
38STATIC EDFRunqueue g_schedEDF;
39
40STATIC VOID EDFDequeue(SchedRunqueue *rq, LosTaskCB *taskCB);
41STATIC VOID EDFEnqueue(SchedRunqueue *rq, LosTaskCB *taskCB);
42STATIC UINT64 EDFWaitTimeGet(LosTaskCB *taskCB);
43STATIC UINT32 EDFWait(LosTaskCB *runTask, LOS_DL_LIST *list, UINT32 ticks);
44STATIC VOID EDFWake(LosTaskCB *resumedTask);
45STATIC BOOL EDFSchedParamModify(LosTaskCB *taskCB, const SchedParam *param);
46STATIC UINT32 EDFSchedParamGet(const LosTaskCB *taskCB, SchedParam *param);
47STATIC UINT32 EDFDelay(LosTaskCB *runTask, UINT64 waitTime);
48STATIC VOID EDFYield(LosTaskCB *runTask);
49STATIC VOID EDFExit(LosTaskCB *taskCB);
50STATIC UINT32 EDFSuspend(LosTaskCB *taskCB);
51STATIC UINT32 EDFResume(LosTaskCB *taskCB, BOOL *needSched);
52STATIC UINT64 EDFTimeSliceGet(const LosTaskCB *taskCB);
53STATIC VOID EDFTimeSliceUpdate(SchedRunqueue *rq, LosTaskCB *taskCB, UINT64 currTime);
54STATIC INT32 EDFParamCompare(const SchedPolicy *sp1, const SchedPolicy *sp2);
55STATIC VOID EDFPriorityInheritance(LosTaskCB *owner, const SchedParam *param);
56STATIC VOID EDFPriorityRestore(LosTaskCB *owner, const LOS_DL_LIST *list, const SchedParam *param);
57
58const STATIC SchedOps g_deadlineOps = {
59    .dequeue = EDFDequeue,
60    .enqueue = EDFEnqueue,
61    .waitTimeGet = EDFWaitTimeGet,
62    .wait = EDFWait,
63    .wake = EDFWake,
64    .schedParamModify = EDFSchedParamModify,
65    .schedParamGet = EDFSchedParamGet,
66    .delay = EDFDelay,
67    .yield = EDFYield,
68    .start = EDFDequeue,
69    .exit = EDFExit,
70    .suspend = EDFSuspend,
71    .resume = EDFResume,
72    .deadlineGet = EDFTimeSliceGet,
73    .timeSliceUpdate = EDFTimeSliceUpdate,
74    .schedParamCompare = EDFParamCompare,
75    .priorityInheritance = EDFPriorityInheritance,
76    .priorityRestore = EDFPriorityRestore,
77};
78
79STATIC VOID EDFTimeSliceUpdate(SchedRunqueue *rq, LosTaskCB *taskCB, UINT64 currTime)
80{
81    SchedEDF *sched = (SchedEDF *)&taskCB->sp;
82
83    LOS_ASSERT(currTime >= taskCB->startTime);
84
85    if (taskCB->timeSlice <= 0) {
86        taskCB->irqUsedTime = 0;
87        return;
88    }
89
90    INT32 incTime = (currTime - taskCB->startTime - taskCB->irqUsedTime);
91    LOS_ASSERT(incTime >= 0);
92
93#ifdef LOSCFG_SCHED_EDF_DEBUG
94    taskCB->schedStat.timeSliceRealTime += incTime;
95    taskCB->schedStat.allRuntime += (currTime - taskCB->startTime);
96#endif
97
98    taskCB->timeSlice -= incTime;
99    taskCB->irqUsedTime = 0;
100    taskCB->startTime = currTime;
101
102    if ((sched->finishTime > currTime) && (taskCB->timeSlice > 0)) {
103        return;
104    }
105
106    rq->schedFlag |= INT_PEND_RESCH;
107    if (sched->finishTime <= currTime) {
108#ifdef LOSCFG_SCHED_EDF_DEBUG
109        EDFDebugRecord((UINTPTR *)taskCB, sched->finishTime);
110#endif
111
112        taskCB->timeSlice = 0;
113        PrintExcInfo("EDF task %u is timeout, runTime: %d us period: %llu us\n", taskCB->taskID,
114                     (INT32)OS_SYS_CYCLE_TO_US((UINT64)sched->runTime), OS_SYS_CYCLE_TO_US(sched->period));
115    }
116}
117
118STATIC UINT64 EDFTimeSliceGet(const LosTaskCB *taskCB)
119{
120    SchedEDF *sched = (SchedEDF *)&taskCB->sp;
121    UINT64 endTime = taskCB->startTime + taskCB->timeSlice;
122    return (endTime > sched->finishTime) ? sched->finishTime : endTime;
123}
124
125STATIC VOID DeadlineQueueInsert(EDFRunqueue *rq, LosTaskCB *taskCB)
126{
127    LOS_DL_LIST *root = &rq->root;
128    if (LOS_ListEmpty(root)) {
129        LOS_ListTailInsert(root, &taskCB->pendList);
130        return;
131    }
132
133    LOS_DL_LIST *list = root->pstNext;
134    do {
135        LosTaskCB *readyTask = LOS_DL_LIST_ENTRY(list, LosTaskCB, pendList);
136        if (EDFParamCompare(&readyTask->sp, &taskCB->sp) > 0) {
137            LOS_ListHeadInsert(list, &taskCB->pendList);
138            return;
139        }
140        list = list->pstNext;
141    } while (list != root);
142
143    LOS_ListHeadInsert(list, &taskCB->pendList);
144}
145
146STATIC VOID EDFEnqueue(SchedRunqueue *rq, LosTaskCB *taskCB)
147{
148    LOS_ASSERT(!(taskCB->taskStatus & OS_TASK_STATUS_READY));
149
150    EDFRunqueue *erq = rq->edfRunqueue;
151    SchedEDF *sched = (SchedEDF *)&taskCB->sp;
152    if (taskCB->timeSlice <= 0) {
153#ifdef LOSCFG_SCHED_EDF_DEBUG
154        UINT64 oldFinish = sched->finishTime;
155#endif
156        UINT64 currTime = OsGetCurrSchedTimeCycle();
157        if (sched->flags == EDF_INIT) {
158            sched->finishTime = currTime;
159        } else if (sched->flags != EDF_NEXT_PERIOD) {
160            /* The start time of the next period */
161            sched->finishTime = (sched->finishTime - sched->deadline) + sched->period;
162        }
163
164        /* Calculate the start time of the next period */
165        while (1) {
166            /* The deadline of the next period */
167            UINT64 finishTime = sched->finishTime + sched->deadline;
168            if ((finishTime <= currTime) || ((sched->finishTime + sched->runTime) > finishTime)) {
169                /* This period cannot meet the minimum running time, so it is migrated to the next period */
170                sched->finishTime += sched->period;
171                continue;
172            }
173            break;
174        }
175
176        if (sched->finishTime > currTime) {
177            /* Wait for the next period to start */
178            LOS_ListTailInsert(&erq->waitList, &taskCB->pendList);
179            taskCB->waitTime = OS_SCHED_MAX_RESPONSE_TIME;
180            if (!OsTaskIsRunning(taskCB)) {
181                OsSchedTimeoutQueueAdd(taskCB, sched->finishTime);
182            }
183#ifdef LOSCFG_SCHED_EDF_DEBUG
184            if (oldFinish != sched->finishTime) {
185                EDFDebugRecord((UINTPTR *)taskCB, oldFinish);
186                taskCB->schedStat.allRuntime = 0;
187                taskCB->schedStat.timeSliceRealTime = 0;
188                taskCB->schedStat.pendTime = 0;
189            }
190#endif
191            taskCB->taskStatus |= OS_TASK_STATUS_PEND_TIME;
192            sched->flags = EDF_NEXT_PERIOD;
193            return;
194        }
195
196        sched->finishTime += sched->deadline;
197        taskCB->timeSlice = sched->runTime;
198        sched->flags = EDF_UNUSED;
199    }
200
201    DeadlineQueueInsert(erq, taskCB);
202    taskCB->taskStatus &= ~(OS_TASK_STATUS_BLOCKED | OS_TASK_STATUS_TIMEOUT);
203    taskCB->taskStatus |= OS_TASK_STATUS_READY;
204}
205
206STATIC VOID EDFDequeue(SchedRunqueue *rq, LosTaskCB *taskCB)
207{
208    (VOID)rq;
209    LOS_ListDelete(&taskCB->pendList);
210    taskCB->taskStatus &= ~OS_TASK_STATUS_READY;
211}
212
213STATIC VOID EDFExit(LosTaskCB *taskCB)
214{
215    if (taskCB->taskStatus & OS_TASK_STATUS_READY) {
216        EDFDequeue(OsSchedRunqueue(), taskCB);
217    } else if (taskCB->taskStatus & OS_TASK_STATUS_PENDING) {
218        LOS_ListDelete(&taskCB->pendList);
219        taskCB->taskStatus &= ~OS_TASK_STATUS_PENDING;
220    }
221    if (taskCB->taskStatus & (OS_TASK_STATUS_DELAY | OS_TASK_STATUS_PEND_TIME)) {
222        OsSchedTimeoutQueueDelete(taskCB);
223        taskCB->taskStatus &= ~(OS_TASK_STATUS_DELAY | OS_TASK_STATUS_PEND_TIME);
224    }
225}
226
227STATIC VOID EDFYield(LosTaskCB *runTask)
228{
229    SchedRunqueue *rq = OsSchedRunqueue();
230    runTask->timeSlice = 0;
231
232    runTask->startTime = OsGetCurrSchedTimeCycle();
233    EDFEnqueue(rq, runTask);
234    OsSchedResched();
235}
236
237STATIC UINT32 EDFDelay(LosTaskCB *runTask, UINT64 waitTime)
238{
239    runTask->taskStatus |= OS_TASK_STATUS_DELAY;
240    runTask->waitTime = waitTime;
241    OsSchedResched();
242    return LOS_OK;
243}
244
245STATIC UINT64 EDFWaitTimeGet(LosTaskCB *taskCB)
246{
247    const SchedEDF *sched = (const SchedEDF *)&taskCB->sp;
248    if (sched->flags != EDF_WAIT_FOREVER) {
249        taskCB->waitTime += taskCB->startTime;
250    }
251    return (taskCB->waitTime >= sched->finishTime) ? sched->finishTime : taskCB->waitTime;
252}
253
254STATIC UINT32 EDFWait(LosTaskCB *runTask, LOS_DL_LIST *list, UINT32 ticks)
255{
256    SchedEDF *sched = (SchedEDF *)&runTask->sp;
257    runTask->taskStatus |= (OS_TASK_STATUS_PENDING | OS_TASK_STATUS_PEND_TIME);
258    LOS_ListTailInsert(list, &runTask->pendList);
259
260    if (ticks != LOS_WAIT_FOREVER) {
261        runTask->waitTime = OS_SCHED_TICK_TO_CYCLE(ticks);
262    } else {
263        sched->flags = EDF_WAIT_FOREVER;
264        runTask->waitTime = OS_SCHED_MAX_RESPONSE_TIME;
265    }
266
267    if (OsPreemptableInSched()) {
268        OsSchedResched();
269        if (runTask->taskStatus & OS_TASK_STATUS_TIMEOUT) {
270            runTask->taskStatus &= ~OS_TASK_STATUS_TIMEOUT;
271            return LOS_ERRNO_TSK_TIMEOUT;
272        }
273    }
274
275    return LOS_OK;
276}
277
278STATIC VOID EDFWake(LosTaskCB *resumedTask)
279{
280    LOS_ListDelete(&resumedTask->pendList);
281    resumedTask->taskStatus &= ~OS_TASK_STATUS_PENDING;
282
283    if (resumedTask->taskStatus & OS_TASK_STATUS_PEND_TIME) {
284        OsSchedTimeoutQueueDelete(resumedTask);
285        resumedTask->taskStatus &= ~OS_TASK_STATUS_PEND_TIME;
286    }
287
288    if (!(resumedTask->taskStatus & OS_TASK_STATUS_SUSPENDED)) {
289#ifdef LOSCFG_SCHED_EDF_DEBUG
290        resumedTask->schedStat.pendTime += OsGetCurrSchedTimeCycle() - resumedTask->startTime;
291        resumedTask->schedStat.pendCount++;
292#endif
293        EDFEnqueue(OsSchedRunqueue(), resumedTask);
294    }
295}
296
297STATIC BOOL EDFSchedParamModify(LosTaskCB *taskCB, const SchedParam *param)
298{
299    SchedRunqueue *rq = OsSchedRunqueue();
300    SchedEDF *sched = (SchedEDF *)&taskCB->sp;
301
302    taskCB->timeSlice = 0;
303    sched->runTime = (INT32)OS_SYS_US_TO_CYCLE(param->runTimeUs);
304    sched->period = OS_SYS_US_TO_CYCLE(param->periodUs);
305
306    if (taskCB->taskStatus & OS_TASK_STATUS_READY) {
307        EDFDequeue(rq, taskCB);
308        sched->deadline = OS_SYS_US_TO_CYCLE(param->deadlineUs);
309        EDFEnqueue(rq, taskCB);
310        return TRUE;
311    }
312
313    sched->deadline = OS_SYS_US_TO_CYCLE(param->deadlineUs);
314    if (taskCB->taskStatus & OS_TASK_STATUS_INIT) {
315        EDFEnqueue(rq, taskCB);
316        return TRUE;
317    }
318
319    if (taskCB->taskStatus & OS_TASK_STATUS_RUNNING) {
320        return TRUE;
321    }
322
323    return FALSE;
324}
325
326STATIC UINT32 EDFSchedParamGet(const LosTaskCB *taskCB, SchedParam *param)
327{
328    SchedEDF *sched = (SchedEDF *)&taskCB->sp;
329    param->policy = sched->policy;
330    param->runTimeUs = (INT32)OS_SYS_CYCLE_TO_US((UINT64)sched->runTime);
331    param->deadlineUs = OS_SYS_CYCLE_TO_US(sched->deadline);
332    param->periodUs = OS_SYS_CYCLE_TO_US(sched->period);
333    return LOS_OK;
334}
335
336STATIC UINT32 EDFSuspend(LosTaskCB *taskCB)
337{
338    return LOS_EOPNOTSUPP;
339}
340
341STATIC UINT32 EDFResume(LosTaskCB *taskCB, BOOL *needSched)
342{
343    return LOS_EOPNOTSUPP;
344}
345
346STATIC INT32 EDFParamCompare(const SchedPolicy *sp1, const SchedPolicy *sp2)
347{
348    const SchedEDF *param1 = (const SchedEDF *)sp1;
349    const SchedEDF *param2 = (const SchedEDF *)sp2;
350
351    return (INT32)(param1->finishTime - param2->finishTime);
352}
353
354STATIC VOID EDFPriorityInheritance(LosTaskCB *owner, const SchedParam *param)
355{
356    (VOID)owner;
357    (VOID)param;
358}
359
360STATIC VOID EDFPriorityRestore(LosTaskCB *owner, const LOS_DL_LIST *list, const SchedParam *param)
361{
362    (VOID)owner;
363    (VOID)list;
364    (VOID)param;
365}
366
367UINT32 EDFTaskSchedParamInit(LosTaskCB *taskCB, UINT16 policy,
368                             const SchedParam *parentParam,
369                             const LosSchedParam *param)
370{
371    (VOID)parentParam;
372    SchedEDF *sched = (SchedEDF *)&taskCB->sp;
373    sched->flags = EDF_INIT;
374    sched->policy = policy;
375    sched->runTime = (INT32)OS_SYS_US_TO_CYCLE((UINT64)param->runTimeUs);
376    sched->deadline = OS_SYS_US_TO_CYCLE(param->deadlineUs);
377    sched->period = OS_SYS_US_TO_CYCLE(param->periodUs);
378    sched->finishTime = 0;
379    taskCB->timeSlice = 0;
380    taskCB->ops = &g_deadlineOps;
381    return LOS_OK;
382}
383
384VOID EDFProcessDefaultSchedParamGet(SchedParam *param)
385{
386    param->runTimeUs = OS_SCHED_EDF_MIN_RUNTIME;
387    param->deadlineUs = OS_SCHED_EDF_MAX_DEADLINE;
388    param->periodUs = param->deadlineUs;
389}
390
391VOID EDFSchedPolicyInit(SchedRunqueue *rq)
392{
393    if (ArchCurrCpuid() > 0) {
394        rq->edfRunqueue = &g_schedEDF;
395        return;
396    }
397
398    EDFRunqueue *erq = &g_schedEDF;
399    erq->period = OS_SCHED_MAX_RESPONSE_TIME;
400    LOS_ListInit(&erq->root);
401    LOS_ListInit(&erq->waitList);
402    rq->edfRunqueue = erq;
403}
404