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->curTick = 0;
179 hand->handLength = accuracy * FILLP_TIMING_WHEEL_SLOT_NUM;
180
181 for (i = 0; i < FILLP_TIMING_WHEEL_SLOT_NUM; i++) {
182 HLIST_INIT(&hand->slotList[i]);
183 }
184 }
185
FillpTimingWheelInit(struct FillpTimingWheel * ftWheel,FILLP_LLONG accuracy)186 void FillpTimingWheelInit(struct FillpTimingWheel *ftWheel, FILLP_LLONG accuracy)
187 {
188 ftWheel->curTime = SYS_ARCH_GET_CUR_TIME_LONGLONG();
189 if (accuracy <= 0) {
190 accuracy = 1;
191 }
192 ftWheel->accuracy = accuracy;
193 ftWheel->inCbContext = FILLP_FALSE;
194 HLIST_INIT(&ftWheel->curCbList);
195 HLIST_INIT(&ftWheel->hourCycleList);
196 FillpInitTimingWheelTimeHand(&ftWheel->secHand, (FILLP_INT)accuracy);
197 FillpInitTimingWheelTimeHand(&ftWheel->minHand, (FILLP_INT)(accuracy * FILLP_TIMING_WHEEL_SLOT_NUM));
198 FillpInitTimingWheelTimeHand(&ftWheel->hourHand,
199 (FILLP_INT)(accuracy * FILLP_TIMING_WHEEL_SLOT_NUM * FILLP_TIMING_WHEEL_SLOT_NUM));
200 ftWheel->tickTime = 0;
201 }
202
FillpTimingWheelAddTimerInner(struct FillpTimingWheel * ftWheel,FILLP_LLONG expireTime,struct FillpTimingWheelTimerNode * timerNode)203 static void FillpTimingWheelAddTimerInner(struct FillpTimingWheel *ftWheel, FILLP_LLONG expireTime,
204 struct FillpTimingWheelTimerNode *timerNode)
205 {
206 FILLP_LLONG timeDiff;
207 FILLP_INT tickDiff;
208 FILLP_INT secTick;
209 FILLP_INT minTick;
210 FILLP_INT hourTick;
211
212 HLIST_INIT_NODE(&timerNode->hourNode);
213 HLIST_INIT_NODE(&timerNode->minNode);
214 HLIST_INIT_NODE(&timerNode->secNode);
215
216 timerNode->status = 0;
217 timerNode->expireTime = expireTime;
218
219 timeDiff = expireTime - ftWheel->curTime;
220 if ((timeDiff < 0) || (timeDiff < ftWheel->secHand.accuracy)) {
221 timeDiff = ftWheel->secHand.accuracy;
222 }
223
224 tickDiff = (FILLP_INT)(timeDiff / ftWheel->secHand.accuracy);
225
226 secTick = ftWheel->secHand.curTick + tickDiff;
227 HlistAddTail(&ftWheel->secHand.slotList[secTick % FILLP_TIMING_WHEEL_SLOT_NUM], &timerNode->secNode);
228 FILLP_TIMING_WHEEL_SET_SEC(timerNode->status);
229
230 if (secTick >= FILLP_TIMING_WHEEL_SLOT_NUM) {
231 minTick = (secTick) / FILLP_TIMING_WHEEL_SLOT_NUM;
232
233 minTick += ftWheel->minHand.curTick;
234 HlistAddTail(&ftWheel->minHand.slotList[minTick % FILLP_TIMING_WHEEL_SLOT_NUM], &timerNode->minNode);
235 FILLP_TIMING_WHEEL_SET_MIN(timerNode->status);
236
237 hourTick = minTick / FILLP_TIMING_WHEEL_SLOT_NUM;
238 if (hourTick > 0) {
239 hourTick += ftWheel->hourHand.curTick;
240 HlistAddTail(&ftWheel->hourHand.slotList[hourTick % FILLP_TIMING_WHEEL_SLOT_NUM],
241 &timerNode->hourNode);
242 FILLP_TIMING_WHEEL_SET_HOUR(timerNode->status);
243 }
244 }
245
246 timerNode->wheel = ftWheel;
247 }
248
FillpTimingWheelAddTimer(struct FillpTimingWheel * ftWheel,FILLP_LLONG expireTime,struct FillpTimingWheelTimerNode * timerNode)249 void FillpTimingWheelAddTimer(struct FillpTimingWheel *ftWheel, FILLP_LLONG expireTime,
250 struct FillpTimingWheelTimerNode *timerNode)
251 {
252 if (FILLP_TIMING_WHEEL_IS_NODE_ENABLED(timerNode)) {
253 return;
254 }
255
256 FillpTimingWheelAddTimerInner(ftWheel, expireTime, timerNode);
257 }
258
FillpTimingWheelDelTimer(struct FillpTimingWheel * ftWheel,struct FillpTimingWheelTimerNode * timerNode)259 void FillpTimingWheelDelTimer(struct FillpTimingWheel *ftWheel, struct FillpTimingWheelTimerNode *timerNode)
260 {
261 if (!FILLP_TIMING_WHEEL_IS_NODE_ENABLED(timerNode)) {
262 return;
263 }
264
265 if (HLISTNODE_LINKED(&timerNode->cbListNode)) {
266 HlistDelete(&ftWheel->curCbList, &timerNode->cbListNode);
267 }
268
269 if (!FILLP_TIMING_WHEEL_IS_SEC_CLEAR(timerNode->status)) {
270 HlistDelNode(&timerNode->secNode);
271 FILLP_TIMING_WHEEL_CLEAR_SEC(timerNode->status);
272 }
273
274 if (!FILLP_TIMING_WHEEL_IS_MIN_CLEAR(timerNode->status)) {
275 HlistDelNode(&timerNode->minNode);
276 FILLP_TIMING_WHEEL_CLEAR_MIN(timerNode->status);
277 }
278
279 if (!FILLP_TIMING_WHEEL_IS_HOUR_CLEAR(timerNode->status)) {
280 HlistDelNode(&timerNode->hourNode);
281 FILLP_TIMING_WHEEL_CLEAR_HOUR(timerNode->status);
282 }
283
284 timerNode->wheel = FILLP_NULL_PTR;
285 return;
286 }
287
FillpTimingWheelLoopCheck(struct FillpTimingWheel * ftWheel,FILLP_LLONG curTime)288 void FillpTimingWheelLoopCheck(struct FillpTimingWheel *ftWheel, FILLP_LLONG curTime)
289 {
290 FILLP_LLONG timeDiff = curTime - ftWheel->curTime;
291 FILLP_INT tickDiff;
292 struct HlistNode *node = FILLP_NULL_PTR;
293 if (timeDiff < 0) {
294 return;
295 }
296
297 tickDiff = (FILLP_INT)(timeDiff / ftWheel->accuracy);
298 if (tickDiff == 0) {
299 return;
300 }
301
302 /* should update before do all callbacks, or it may lead to dead loop */
303 ftWheel->curTime = curTime;
304 ftWheel->inCbContext = FILLP_TRUE;
305 ftWheel->nextMinimalExpireTime = 0;
306 FillpTimingWheelHandSecTick(ftWheel, tickDiff);
307
308 node = HLIST_FIRST(&ftWheel->curCbList);
309 while (node != FILLP_NULL_PTR) {
310 struct FillpTimingWheelTimerNode *timerNode = FillpTimingWheelCblistNodeEntry(node);
311 HlistDelete(&ftWheel->curCbList, node);
312 if (timerNode->cbNode.cb != FILLP_NULL_PTR) {
313 timerNode->cbNode.cb(timerNode->cbNode.arg);
314 }
315 node = HLIST_FIRST(&ftWheel->curCbList);
316 }
317
318 ftWheel->inCbContext = FILLP_FALSE;
319 }
320
321 #ifdef __cplusplus
322 }
323 #endif
324