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