1 /*
2  * Copyright (C) 2022 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include "fillp_function.h"
17 #include "utils.h"
18 #include "log.h"
19 #include "timing_wheel.h"
20 
21 #ifdef __cplusplus
22 extern "C" {
23 #endif
24 
25 static void FillpTimingWheelAddTimerInner(struct FillpTimingWheel *ftWheel, FILLP_LLONG expireTime,
26     struct FillpTimingWheelTimerNode *timerNode);
27 
FillpTimingWheelRunPending(struct FillpTimingWheel * wheel,struct FillpTimingWheelTimerNode * timerNode)28 static void FillpTimingWheelRunPending(struct FillpTimingWheel *wheel, struct FillpTimingWheelTimerNode *timerNode)
29 {
30     if (FILLP_TIMING_WHEEL_IS_CLEAR(timerNode->status)) {
31         HlistAddTail(&wheel->curCbList, &timerNode->cbListNode);
32     }
33 }
34 
FillpTimingWheelHandHourTick(struct FillpTimingWheel * wheel,FILLP_LLONG tickDiff)35 static void FillpTimingWheelHandHourTick(struct FillpTimingWheel *wheel, FILLP_LLONG tickDiff)
36 {
37     FILLP_INT i;
38     struct FillpTimingWheelHand *hourHand = &wheel->hourHand;
39     struct HlistNode *hourNode = FILLP_NULL_PTR;
40     struct HlistNode *tmpNode = FILLP_NULL_PTR;
41     struct FillpTimingWheelTimerNode *timerNode = FILLP_NULL_PTR;
42     FILLP_INT tickLoop = (FILLP_INT)UTILS_MIN(tickDiff, FILLP_TIMING_WHEEL_SLOT_NUM - 1);
43     FILLP_INT tmpIndex = hourHand->curTick;
44 
45     if ((tmpIndex >= FILLP_TIMING_WHEEL_SLOT_NUM) || (tmpIndex < 0)) {
46         return;
47     }
48 
49     for (i = 0; i <= tickLoop; i++) {
50         /* Need to handle the current tick, because maybe some timer added after current tick triggled before */
51         hourNode = HLIST_FIRST(&hourHand->slotList[tmpIndex]);
52         while (hourNode != FILLP_NULL_PTR) {
53             timerNode = FillpTimingWheelHourNodeEntry(hourNode);
54             tmpNode = hourNode;
55             hourNode = hourNode->next;
56             if (wheel->curTime > timerNode->expireTime) {
57                 HlistDelete(&hourHand->slotList[tmpIndex], tmpNode);
58                 FILLP_TIMING_WHEEL_CLEAR_HOUR(timerNode->status);
59                 FillpTimingWheelRunPending(wheel, timerNode);
60             } else if (wheel->curTime + wheel->hourHand.handLength > timerNode->expireTime) {
61                 HlistAddTail(&wheel->hourCycleList, &timerNode->cycleNode);
62             }
63         }
64 
65         tmpIndex++;
66         if (tmpIndex == FILLP_TIMING_WHEEL_SLOT_NUM) {
67             tmpIndex = 0;
68         }
69     }
70 
71     hourHand->curTick = (FILLP_INT)((hourHand->curTick + tickDiff) % FILLP_TIMING_WHEEL_SLOT_NUM);
72 
73     tmpNode = HLIST_FIRST(&wheel->hourCycleList);
74     while (tmpNode != FILLP_NULL_PTR) {
75         timerNode = FillpTimingWheelCycleNodeEntry(tmpNode);
76         HlistDelNode(tmpNode);
77         FillpTimingWheelDelTimer(wheel, timerNode);
78         FillpTimingWheelAddTimerInner(wheel, timerNode->expireTime, timerNode);
79 
80         tmpNode = HLIST_FIRST(&wheel->hourCycleList);
81     }
82 }
83 
FillpTimingWheelHandMinTick(struct FillpTimingWheel * wheel,FILLP_LLONG tickDiff)84 static void FillpTimingWheelHandMinTick(struct FillpTimingWheel *wheel, FILLP_LLONG tickDiff)
85 {
86     FILLP_INT i;
87     struct FillpTimingWheelHand *minHand = &wheel->minHand;
88     struct HlistNode *minNode = FILLP_NULL_PTR;
89     struct HlistNode *tmpNode = FILLP_NULL_PTR;
90     FILLP_INT tmpIndex = minHand->curTick;
91     struct FillpTimingWheelTimerNode *timerNode = FILLP_NULL_PTR;
92     FILLP_INT tickLoop = (FILLP_INT)UTILS_MIN(tickDiff, FILLP_TIMING_WHEEL_SLOT_NUM - 1);
93     FILLP_INT minTick = (FILLP_INT)(tickDiff + minHand->curTick);
94     FILLP_INT hourTick = minTick / FILLP_TIMING_WHEEL_SLOT_NUM;
95 
96     if ((tmpIndex >= FILLP_TIMING_WHEEL_SLOT_NUM) || (tmpIndex < 0)) {
97         return;
98     }
99 
100     for (i = 0; i <= tickLoop; i++) {
101         /* Need to handle the current tick, because maybe some timer added after current tick triggled before */
102         minNode = HLIST_FIRST(&minHand->slotList[tmpIndex]);
103         while (minNode != FILLP_NULL_PTR) {
104             tmpNode = minNode->next;
105             timerNode = FillpTimingWheelMinNodeEntry(minNode);
106             HlistDelete(&minHand->slotList[tmpIndex], minNode);
107 
108             FILLP_TIMING_WHEEL_CLEAR_MIN(timerNode->status);
109             FillpTimingWheelRunPending(wheel, timerNode);
110 
111             minNode = tmpNode;
112         }
113 
114         tmpIndex++;
115         if (tmpIndex == FILLP_TIMING_WHEEL_SLOT_NUM) {
116             tmpIndex = 0;
117         }
118     }
119 
120     minHand->curTick = minTick % FILLP_TIMING_WHEEL_SLOT_NUM;
121     if (hourTick > 0) {
122         FillpTimingWheelHandHourTick(wheel, hourTick);
123     }
124 }
125 
FillpTimingWheelHandSecTick(struct FillpTimingWheel * wheel,FILLP_INT tickDiff)126 static void FillpTimingWheelHandSecTick(struct FillpTimingWheel *wheel, FILLP_INT tickDiff)
127 {
128     FILLP_INT i;
129     struct FillpTimingWheelHand *secHand = &wheel->secHand;
130     struct HlistNode *secNode = FILLP_NULL_PTR;
131     struct HlistNode *tmpNode = FILLP_NULL_PTR;
132     FILLP_INT tmpIndex = wheel->secHand.curTick;
133     struct FillpTimingWheelTimerNode *timerNode = FILLP_NULL_PTR;
134     FILLP_INT tickLoop = UTILS_MIN(tickDiff, FILLP_TIMING_WHEEL_SLOT_NUM - 1);
135     FILLP_INT secTick = (tickDiff + secHand->curTick);
136     FILLP_INT minTick = secTick / FILLP_TIMING_WHEEL_SLOT_NUM;
137 
138     if ((tmpIndex < 0) || (tmpIndex >= FILLP_TIMING_WHEEL_SLOT_NUM)) {
139         return;
140     }
141 
142     for (i = 0; i <= tickLoop; i++) {
143         /* Need to handle the current tick, because maybe some timer added after current tick triggled before */
144         secNode = HLIST_FIRST(&secHand->slotList[tmpIndex]);
145         while (secNode != FILLP_NULL_PTR) {
146             tmpNode = secNode->next;
147             timerNode = FillpTimingWheelSecNodeEntry(secNode);
148 
149             HlistDelete(&secHand->slotList[tmpIndex], secNode);
150 
151             FILLP_TIMING_WHEEL_CLEAR_SEC(timerNode->status);
152             FillpTimingWheelRunPending(wheel, timerNode);
153             secNode = tmpNode;
154         }
155 
156         tmpIndex++;
157         if (tmpIndex == FILLP_TIMING_WHEEL_SLOT_NUM) {
158             tmpIndex = 0;
159         }
160     }
161 
162     secHand->curTick = secTick % FILLP_TIMING_WHEEL_SLOT_NUM;
163     if (minTick > 0) {
164         FillpTimingWheelHandMinTick(wheel, minTick);
165     }
166 }
167 
FillpInitTimingWheelTimeHand(struct FillpTimingWheelHand * hand,FILLP_INT accuracy)168 static void FillpInitTimingWheelTimeHand(struct FillpTimingWheelHand *hand, FILLP_INT accuracy)
169 {
170     if (accuracy == 0) {
171         FILLP_LOGERR("accuracy can't be 0");
172         return;
173     }
174     FILLP_INT i;
175     hand->curTick = 0;
176     hand->accuracy = accuracy;
177     hand->curSlotTime = SYS_ARCH_GET_CUR_TIME_LONGLONG();
178     hand->handLength = accuracy * FILLP_TIMING_WHEEL_SLOT_NUM;
179 
180     for (i = 0; i < FILLP_TIMING_WHEEL_SLOT_NUM; i++) {
181         HLIST_INIT(&hand->slotList[i]);
182     }
183 }
184 
FillpTimingWheelInit(struct FillpTimingWheel * ftWheel,FILLP_LLONG accuracy)185 void FillpTimingWheelInit(struct FillpTimingWheel *ftWheel, FILLP_LLONG accuracy)
186 {
187     ftWheel->curTime = SYS_ARCH_GET_CUR_TIME_LONGLONG();
188     if (accuracy <= 0) {
189         accuracy = 1;
190     }
191     ftWheel->accuracy = accuracy;
192     ftWheel->inCbContext = FILLP_FALSE;
193     HLIST_INIT(&ftWheel->curCbList);
194     HLIST_INIT(&ftWheel->hourCycleList);
195     FillpInitTimingWheelTimeHand(&ftWheel->secHand, (FILLP_INT)accuracy);
196     FillpInitTimingWheelTimeHand(&ftWheel->minHand, (FILLP_INT)(accuracy * FILLP_TIMING_WHEEL_SLOT_NUM));
197     FillpInitTimingWheelTimeHand(&ftWheel->hourHand,
198         (FILLP_INT)(accuracy * FILLP_TIMING_WHEEL_SLOT_NUM * FILLP_TIMING_WHEEL_SLOT_NUM));
199     ftWheel->tickTime = 0;
200 }
201 
FillpTimingWheelAddTimerInner(struct FillpTimingWheel * ftWheel,FILLP_LLONG expireTime,struct FillpTimingWheelTimerNode * timerNode)202 static void FillpTimingWheelAddTimerInner(struct FillpTimingWheel *ftWheel, FILLP_LLONG expireTime,
203     struct FillpTimingWheelTimerNode *timerNode)
204 {
205     FILLP_LLONG timeDiff;
206     FILLP_INT tickDiff;
207     FILLP_INT secTick;
208     FILLP_INT minTick;
209     FILLP_INT hourTick;
210 
211     HLIST_INIT_NODE(&timerNode->hourNode);
212     HLIST_INIT_NODE(&timerNode->minNode);
213     HLIST_INIT_NODE(&timerNode->secNode);
214 
215     timerNode->status = 0;
216     timerNode->expireTime = expireTime;
217 
218     timeDiff = expireTime - ftWheel->curTime;
219     if ((timeDiff < 0) || (timeDiff < ftWheel->secHand.accuracy)) {
220         timeDiff = ftWheel->secHand.accuracy;
221     }
222 
223     tickDiff = (FILLP_INT)(timeDiff / ftWheel->secHand.accuracy);
224 
225     secTick = ftWheel->secHand.curTick + tickDiff;
226     HlistAddTail(&ftWheel->secHand.slotList[secTick % FILLP_TIMING_WHEEL_SLOT_NUM], &timerNode->secNode);
227     FILLP_TIMING_WHEEL_SET_SEC(timerNode->status);
228 
229     if (secTick >= FILLP_TIMING_WHEEL_SLOT_NUM) {
230         minTick = (secTick) / FILLP_TIMING_WHEEL_SLOT_NUM;
231 
232         minTick += ftWheel->minHand.curTick;
233         HlistAddTail(&ftWheel->minHand.slotList[minTick % FILLP_TIMING_WHEEL_SLOT_NUM], &timerNode->minNode);
234         FILLP_TIMING_WHEEL_SET_MIN(timerNode->status);
235 
236         hourTick = minTick / FILLP_TIMING_WHEEL_SLOT_NUM;
237         if (hourTick > 0) {
238             hourTick += ftWheel->hourHand.curTick;
239             HlistAddTail(&ftWheel->hourHand.slotList[hourTick % FILLP_TIMING_WHEEL_SLOT_NUM],
240                 &timerNode->hourNode);
241             FILLP_TIMING_WHEEL_SET_HOUR(timerNode->status);
242         }
243     }
244 
245     timerNode->wheel = ftWheel;
246 }
247 
FillpTimingWheelAddTimer(struct FillpTimingWheel * ftWheel,FILLP_LLONG expireTime,struct FillpTimingWheelTimerNode * timerNode)248 void FillpTimingWheelAddTimer(struct FillpTimingWheel *ftWheel, FILLP_LLONG expireTime,
249     struct FillpTimingWheelTimerNode *timerNode)
250 {
251     if (FILLP_TIMING_WHEEL_IS_NODE_ENABLED(timerNode)) {
252         return;
253     }
254 
255     FillpTimingWheelAddTimerInner(ftWheel, expireTime, timerNode);
256 }
257 
FillpTimingWheelDelTimer(struct FillpTimingWheel * ftWheel,struct FillpTimingWheelTimerNode * timerNode)258 void FillpTimingWheelDelTimer(struct FillpTimingWheel *ftWheel, struct FillpTimingWheelTimerNode *timerNode)
259 {
260     if (!FILLP_TIMING_WHEEL_IS_NODE_ENABLED(timerNode)) {
261         return;
262     }
263 
264     if (HLISTNODE_LINKED(&timerNode->cbListNode)) {
265         HlistDelete(&ftWheel->curCbList, &timerNode->cbListNode);
266     }
267 
268     if (!FILLP_TIMING_WHEEL_IS_SEC_CLEAR(timerNode->status)) {
269         HlistDelNode(&timerNode->secNode);
270         FILLP_TIMING_WHEEL_CLEAR_SEC(timerNode->status);
271     }
272 
273     if (!FILLP_TIMING_WHEEL_IS_MIN_CLEAR(timerNode->status)) {
274         HlistDelNode(&timerNode->minNode);
275         FILLP_TIMING_WHEEL_CLEAR_MIN(timerNode->status);
276     }
277 
278     if (!FILLP_TIMING_WHEEL_IS_HOUR_CLEAR(timerNode->status)) {
279         HlistDelNode(&timerNode->hourNode);
280         FILLP_TIMING_WHEEL_CLEAR_HOUR(timerNode->status);
281     }
282 
283     timerNode->wheel = FILLP_NULL_PTR;
284     return;
285 }
286 
FillpTimingWheelLoopCheck(struct FillpTimingWheel * ftWheel,FILLP_LLONG curTime)287 void FillpTimingWheelLoopCheck(struct FillpTimingWheel *ftWheel, FILLP_LLONG curTime)
288 {
289     FILLP_LLONG timeDiff = curTime - ftWheel->curTime;
290     FILLP_INT tickDiff;
291     struct HlistNode *node = FILLP_NULL_PTR;
292     if (timeDiff < 0) {
293         return;
294     }
295 
296     tickDiff = (FILLP_INT)(timeDiff / ftWheel->accuracy);
297     if (tickDiff == 0) {
298         return;
299     }
300 
301     /* should update before do all callbacks, or it may lead to dead loop */
302     ftWheel->curTime = curTime;
303     ftWheel->inCbContext = FILLP_TRUE;
304     ftWheel->nextMinimalExpireTime = 0;
305     FillpTimingWheelHandSecTick(ftWheel, tickDiff);
306 
307     node = HLIST_FIRST(&ftWheel->curCbList);
308     while (node != FILLP_NULL_PTR) {
309         struct FillpTimingWheelTimerNode *timerNode = FillpTimingWheelCblistNodeEntry(node);
310         HlistDelete(&ftWheel->curCbList, node);
311         if (timerNode->cbNode.cb != FILLP_NULL_PTR) {
312             timerNode->cbNode.cb(timerNode->cbNode.arg);
313         }
314         node = HLIST_FIRST(&ftWheel->curCbList);
315     }
316 
317     ftWheel->inCbContext = FILLP_FALSE;
318 }
319 
320 #ifdef __cplusplus
321 }
322 #endif
323