1
2 #include <stddef.h>
3 #include <stdbool.h>
4 #include <stdint.h>
5
6 #include <sys/kassert.h>
7 #include <sys/queue.h>
8 #include <sys/spinlock.h>
9 #include <sys/kmem.h>
10 #include <sys/mp.h>
11 #include <sys/ktime.h>
12 #include <sys/ktimer.h>
13
14 #define TIMER_WHEEL_LENGTH 256
15
16 static int timerHead = 0;
17 static uint64_t timerNow = 0;
18 static LIST_HEAD(TimerWheelHead, KTimerEvent) timerSlot[TIMER_WHEEL_LENGTH];
19 static Spinlock timerLock;
20 static Slab timerSlab;
21
22 DEFINE_SLAB(KTimerEvent, &timerSlab);
23
24 void
KTimer_Init()25 KTimer_Init()
26 {
27 int i;
28
29 Spinlock_Init(&timerLock, "KTimer Lock", SPINLOCK_TYPE_NORMAL);
30 Slab_Init(&timerSlab, "KTimerEvent Slab", sizeof(KTimerEvent), 16);
31
32 // Initialize wheel
33 timerHead = 0;
34 timerNow = KTime_GetEpoch();
35 for (i = 0; i < TIMER_WHEEL_LENGTH; i++) {
36 LIST_INIT(&timerSlot[i]);
37 }
38 }
39
40 KTimerEvent *
KTimer_Create(uint64_t timeout,KTimerCB cb,void * arg)41 KTimer_Create(uint64_t timeout, KTimerCB cb, void *arg)
42 {
43 int slot;
44 KTimerEvent *evt = KTimerEvent_Alloc();
45
46 evt->refCount = 2; // One for the wheel and one for the callee
47 evt->timeout = timerNow + timeout;
48 evt->cb = cb;
49 evt->arg = arg;
50
51 Spinlock_Lock(&timerLock);
52 slot = (timerHead + timeout + TIMER_WHEEL_LENGTH - 1) % TIMER_WHEEL_LENGTH;
53 // XXX: should insert into tail
54 LIST_INSERT_HEAD(&timerSlot[slot], evt, timerQueue);
55 Spinlock_Unlock(&timerLock);
56
57 return evt;
58 }
59
60 void
KTimer_Retain(KTimerEvent * evt)61 KTimer_Retain(KTimerEvent *evt)
62 {
63 ASSERT(evt->refCount != 0);
64 __sync_fetch_and_add(&evt->refCount, 1);
65 }
66
67 void
KTimer_Release(KTimerEvent * evt)68 KTimer_Release(KTimerEvent *evt)
69 {
70 ASSERT(evt->refCount != 0);
71 if (__sync_fetch_and_sub(&evt->refCount, 1) == 1) {
72 KTimerEvent_Free(evt);
73 }
74 }
75
76 void
KTimer_Cancel(KTimerEvent * evt)77 KTimer_Cancel(KTimerEvent *evt)
78 {
79 Spinlock_Lock(&timerLock);
80
81 LIST_REMOVE(evt, timerQueue);
82 KTimer_Release(evt);
83
84 Spinlock_Unlock(&timerLock);
85 }
86
87 void
KTimer_Process()88 KTimer_Process()
89 {
90 uint64_t now;
91
92 if (CPU() != 0) {
93 return;
94 }
95
96 now = KTime_GetEpoch();
97
98 Spinlock_Lock(&timerLock);
99
100 while (now > timerNow) {
101 KTimerEvent *it, *tmp;
102
103 // Dispatch pending timer events
104 LIST_FOREACH_SAFE(it, &timerSlot[timerHead], timerQueue, tmp) {
105 if (it->timeout <= now) {
106 (it->cb)(it->arg);
107 LIST_REMOVE(it, timerQueue);
108 KTimer_Release(it);
109 }
110 }
111
112 // Rotate wheel forward
113 timerNow = timerNow + 1;
114 timerHead = (timerHead + 1) % TIMER_WHEEL_LENGTH;
115 }
116
117 Spinlock_Unlock(&timerLock);
118 }
119
120