1 #include <assert.h>
2 #include <limits.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <time.h>
6
7 #include <tchar.h>
8 #include <windows.h>
9
10 #ifndef InitializeListHead
11 #define InitializeListHead(PLH__) ((PLH__)->Flink = (PLH__)->Blink = (PLH__))
12 #endif
13
14 #ifndef IsListEmpty
15 #define IsListEmpty(PLH__) ((PLH__)->Flink == (PVOID)(PLH__))
16 #endif
17
18 #ifndef RemoveEntryList
19
20 #define RemoveEntryList(PLE__) \
21 { \
22 PLIST_ENTRY pleBack__ = (PLIST_ENTRY)((PLE__)->Blink); \
23 PLIST_ENTRY pleForward__ = (PLIST_ENTRY)((PLE__)->Flink); \
24 \
25 pleBack__->Flink = pleForward__; \
26 pleForward__->Blink = pleBack__; \
27 }
28
29 #endif
30
31 #ifndef InsertTailList
32
33 #define InsertTailList(PLH__, PLE__) \
34 { \
35 PLIST_ENTRY pleListHead__ = (PLH__); \
36 PLIST_ENTRY pleBlink__ = (PLIST_ENTRY)((PLH__)->Blink); \
37 \
38 (PLE__)->Flink = pleListHead__; \
39 (PLE__)->Blink = pleBlink__; \
40 pleBlink__->Flink = (PLE__); \
41 pleListHead__->Blink = (PLE__); \
42 }
43
44 #endif
45
46 #ifndef RemoveHeadList
47
48 #define RemoveHeadList(PLH__) \
49 (PLIST_ENTRY)((PLH__)->Flink); \
50 RemoveEntryList((PLIST_ENTRY)((PLH__)->Flink));
51
52 #endif
53
54 #define FIBERTEST_COUNT 500
55
56 struct FiberData
57 {
58 unsigned nMagic;
59 unsigned nId;
60 unsigned nPrio;
61 unsigned nRealPrio;
62 PVOID pFiber;
63 LIST_ENTRY leQueue;
64 int nQuantumQueued;
65 int nBoost;
66 struct FiberData * pfdPrev;
67 int bExitPrev;
68 };
69
70 static LIST_ENTRY a_leQueues[32];
71 static unsigned nQuantum = 0;
72 static struct FiberData * pfdLastStarveScan = NULL;
73
74 void Fbt_Create(int);
75 void Fbt_Exit(void);
76 void Fbt_Yield(void);
77
78 struct FiberData * Fbt_GetCurrent(void);
79 unsigned Fbt_GetCurrentId(void);
80 VOID CALLBACK Fbt_Startup(PVOID);
81 void Fbt_Dispatch(struct FiberData *, int);
82 void Fbt_AfterSwitch(struct FiberData *);
83
84 void DoStuff(void);
85
Fbt_GetCurrent(VOID)86 struct FiberData * Fbt_GetCurrent(VOID)
87 {
88 return GetFiberData();
89 }
90
Fbt_GetCurrentId(VOID)91 unsigned Fbt_GetCurrentId(VOID)
92 {
93 return Fbt_GetCurrent()->nId;
94 }
95
Fbt_Yield(VOID)96 void Fbt_Yield(VOID)
97 {
98 struct FiberData * pfdCur;
99
100 pfdCur = Fbt_GetCurrent();
101
102 if(pfdCur->nBoost)
103 {
104 -- pfdCur->nBoost;
105
106 if(!pfdCur->nBoost)
107 pfdCur->nPrio = pfdCur->nRealPrio;
108 }
109 else if((rand() % 100) > 50 - (45 * pfdCur->nPrio) / 32)
110 Fbt_Dispatch(pfdCur, 0);
111 }
112
Fbt_AfterSwitch(struct FiberData * pfdCur)113 void Fbt_AfterSwitch(struct FiberData * pfdCur)
114 {
115 struct FiberData * pfdPrev;
116
117 pfdPrev = pfdCur->pfdPrev;
118
119 /* The previous fiber left some homework for us */
120 if(pfdPrev)
121 {
122 /* Kill the predecessor */
123 if(pfdCur->bExitPrev)
124 {
125 if(pfdLastStarveScan == pfdPrev)
126 pfdLastStarveScan = 0;
127
128 DeleteFiber(pfdPrev->pFiber);
129 free(pfdPrev);
130 }
131 /* Enqueue the previous fiber in the correct ready queue */
132 else
133 {
134 /* Remember the quantum in which the previous fiber was queued */
135 pfdPrev->nQuantumQueued = nQuantum;
136
137 /* Disable the anti-starvation boost */
138 if(pfdPrev->nBoost)
139 {
140 pfdPrev->nBoost = 0;
141 pfdPrev->nPrio = pfdPrev->nRealPrio;
142 }
143
144 /* Enqueue the previous fiber */
145 InsertTailList
146 (
147 &a_leQueues[pfdPrev->nPrio],
148 &pfdPrev->leQueue
149 );
150 }
151 }
152 }
153
Fbt_Startup(PVOID pParam)154 VOID CALLBACK Fbt_Startup(PVOID pParam)
155 {
156 assert(pParam == GetFiberData());
157 Fbt_AfterSwitch(pParam);
158 DoStuff();
159 Fbt_Exit();
160 }
161
Fbt_Dispatch(struct FiberData * pfdCur,int bExit)162 void Fbt_Dispatch(struct FiberData * pfdCur, int bExit)
163 {
164 UCHAR i;
165 UCHAR n;
166 struct FiberData * pfdNext;
167
168 assert(pfdCur == GetFiberData());
169
170 ++ nQuantum;
171
172 /* Every ten quantums check for starving threads */
173 /* FIXME: this implementation of starvation prevention isn't that great */
174 if(nQuantum % 10 == 0)
175 {
176 int j;
177 int k;
178 int b;
179 int bResume;
180 PLIST_ENTRY ple = NULL;
181
182 bResume = 0;
183 i = 0;
184
185 /* Pick up from where we left last time */
186 if(pfdLastStarveScan)
187 {
188 unsigned nPrio;
189
190 nPrio = pfdLastStarveScan->nPrio;
191
192 /* The last fiber we scanned for starvation isn't queued anymore */
193 if(IsListEmpty(&pfdLastStarveScan->leQueue))
194 /* Scan the ready queue for its priority */
195 i = nPrio;
196 /* Last fiber for its priority level */
197 else if(pfdLastStarveScan->leQueue.Flink == &a_leQueues[nPrio])
198 /* Scan the ready queue for the next priority level */
199 i = nPrio + 1;
200 /* Scan the next fiber in the ready queue */
201 else
202 {
203 i = nPrio;
204 ple = pfdLastStarveScan->leQueue.Flink;
205 bResume = 1;
206 }
207
208 /* Priority levels 15-31 are never checked for starvation */
209 if(i >= 15)
210 {
211 if(bResume)
212 bResume = 0;
213
214 i = 0;
215 }
216 }
217
218 /*
219 Scan at most 16 threads, in the priority range 0-14, applying in total at
220 most 10 boosts. This loop scales O(1)
221 */
222 for(j = 0, k = 0, b = 0; j < 16 && k < 15 && b < 10; ++ j)
223 {
224 unsigned nDiff;
225
226 /* No previous state to resume from */
227 if(!bResume)
228 {
229 int nQueue;
230
231 /* Get the first element in the current queue */
232 nQueue = (k + i) % 15;
233
234 if(IsListEmpty(&a_leQueues[nQueue]))
235 {
236 ++ k;
237 continue;
238 }
239
240 ple = (PLIST_ENTRY)a_leQueues[nQueue].Flink;
241 }
242 else
243 bResume = 0;
244
245 /* Get the current fiber */
246 pfdLastStarveScan = CONTAINING_RECORD(ple, struct FiberData, leQueue);
247 assert(pfdLastStarveScan->nMagic == 0x12345678);
248 assert(pfdLastStarveScan != pfdCur);
249
250 /* Calculate the number of quantums the fiber has been in the queue */
251 if(nQuantum > pfdLastStarveScan->nQuantumQueued)
252 nDiff = nQuantum - pfdLastStarveScan->nQuantumQueued;
253 else
254 nDiff = UINT_MAX - pfdLastStarveScan->nQuantumQueued + nQuantum;
255
256 /* The fiber has been ready for more than 30 quantums: it's starving */
257 if(nDiff > 30)
258 {
259 /* Plus one boost applied */
260 ++ b;
261
262 /* Apply the boost */
263 pfdLastStarveScan->nBoost = 1;
264 pfdLastStarveScan->nRealPrio = pfdLastStarveScan->nPrio;
265 pfdLastStarveScan->nPrio = 15;
266
267 /* Re-enqueue the fiber in the correct priority queue */
268 RemoveEntryList(&pfdLastStarveScan->leQueue);
269 InsertTailList(&a_leQueues[15], &pfdLastStarveScan->leQueue);
270 }
271 }
272 }
273
274 pfdNext = NULL;
275
276 /* This fiber is going to die: scan all ready queues */
277 if(bExit)
278 n = 1;
279 /*
280 Scan only ready queues for priorities greater than or equal to the priority of
281 the current thread (round-robin)
282 */
283 else
284 n = pfdCur->nPrio + 1;
285
286 /* This loop scales O(1) */
287 for(i = 32; i >= n; -- i)
288 {
289 PLIST_ENTRY pleNext;
290
291 /* No fiber ready for this priority level */
292 if(IsListEmpty(&a_leQueues[i - 1]))
293 continue;
294
295 /* Get the next ready fiber */
296 pleNext = RemoveHeadList(&a_leQueues[i - 1]);
297 InitializeListHead(pleNext);
298 pfdNext = CONTAINING_RECORD(pleNext, struct FiberData, leQueue);
299 assert(pfdNext->pFiber != GetCurrentFiber());
300 assert(pfdNext->nMagic == 0x12345678);
301 break;
302 }
303
304 /* Next fiber chosen */
305 if(pfdNext)
306 {
307 /* Give some homework to the next fiber */
308 pfdNext->pfdPrev = pfdCur;
309 pfdNext->bExitPrev = bExit;
310
311 /* Switch to the next fiber */
312 SwitchToFiber(pfdNext->pFiber);
313
314 /* Complete the switch back to this fiber */
315 Fbt_AfterSwitch(pfdCur);
316 }
317 /* No next fiber, and current fiber exiting */
318 else if(bExit)
319 {
320 PVOID pCurFiber;
321
322 /* Delete the current fiber. This kills the thread and stops the simulation */
323 if(pfdLastStarveScan == pfdCur)
324 pfdLastStarveScan = NULL;
325
326 pCurFiber = pfdCur->pFiber;
327 free(pfdCur);
328 DeleteFiber(pCurFiber);
329 }
330 /* No next fiber: continue running the current one */
331 }
332
Fbt_Exit(VOID)333 void Fbt_Exit(VOID)
334 {
335 Fbt_Dispatch(GetFiberData(), 1);
336 }
337
Fbt_CreateFiber(int bInitial)338 void Fbt_CreateFiber(int bInitial)
339 {
340 PVOID pFiber;
341 struct FiberData * pData;
342 static int s_bFiberPrioSeeded = 0;
343 static LONG s_nFiberIdSeed = 0;
344
345 pData = malloc(sizeof(struct FiberData));
346
347 assert(pData);
348
349 if(bInitial)
350 pFiber = ConvertThreadToFiber(pData);
351 else
352 pFiber = CreateFiber(0, Fbt_Startup, pData);
353
354 if(!s_bFiberPrioSeeded)
355 {
356 unsigned nFiberPrioSeed;
357 time_t tCurTime;
358
359 tCurTime = time(NULL);
360 memcpy(&nFiberPrioSeed, &tCurTime, sizeof(nFiberPrioSeed));
361 srand(nFiberPrioSeed);
362 s_bFiberPrioSeeded = 1;
363 }
364
365 assert(pFiber);
366
367 pData->nMagic = 0x12345678;
368 pData->nId = InterlockedIncrement(&s_nFiberIdSeed);
369 pData->nPrio = rand() % 32;
370 pData->pFiber = pFiber;
371 pData->nQuantumQueued = 0;
372 pData->nBoost = 0;
373 pData->nRealPrio = pData->nPrio;
374 pData->pfdPrev = NULL;
375 pData->bExitPrev = 0;
376
377 if(bInitial)
378 {
379 InitializeListHead(&pData->leQueue);
380 }
381 else
382 {
383 InsertTailList
384 (
385 &a_leQueues[pData->nPrio],
386 &pData->leQueue
387 );
388 }
389 }
390
DoStuff(void)391 void DoStuff(void)
392 {
393 unsigned i;
394 unsigned n;
395 unsigned nId;
396
397 n = rand() % 1000;
398 nId = Fbt_GetCurrentId();
399
400 _ftprintf(stderr, _T("[%u] BEGIN\n"), nId);
401
402 for(i = 0; i < n; ++ i)
403 {
404 unsigned j;
405 unsigned m;
406
407 _ftprintf(stderr, _T("[%u] [%u/%u]\n"), nId, i + 1, n);
408
409 m = rand() % 1000;
410
411 for(j = 0; j < m; ++ j)
412 Sleep(0);
413
414 Fbt_Yield();
415 }
416
417 _ftprintf(stderr, _T("[%u] END\n"), nId);
418 }
419
_tmain(int argc,_TCHAR const * const * argv)420 int _tmain(int argc, _TCHAR const * const * argv)
421 {
422 unsigned i;
423 unsigned nFibers;
424
425 if(argc > 1)
426 nFibers = _tcstoul(argv[1], NULL, 0);
427 else
428 nFibers = FIBERTEST_COUNT;
429
430 for(i = 0; i < 32; ++ i)
431 {
432 InitializeListHead(&a_leQueues[i]);
433 }
434
435 for(i = 0; i < nFibers; ++ i)
436 Fbt_CreateFiber(i == 0);
437
438 Fbt_Startup(GetFiberData());
439
440 return 0;
441 }
442
443 /* EOF */
444