ReactOS 0.4.15-dev-8096-ga0eec98
fiber.c
Go to the documentation of this file.
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
57{
58 unsigned nMagic;
59 unsigned nId;
60 unsigned nPrio;
61 unsigned nRealPrio;
65 int nBoost;
68};
69
71static unsigned nQuantum = 0;
73
74void Fbt_Create(int);
75void Fbt_Exit(void);
76void Fbt_Yield(void);
77
78struct FiberData * Fbt_GetCurrent(void);
79unsigned Fbt_GetCurrentId(void);
81void Fbt_Dispatch(struct FiberData *, int);
82void Fbt_AfterSwitch(struct FiberData *);
83
84void DoStuff(void);
85
87{
88 return GetFiberData();
89}
90
92{
93 return Fbt_GetCurrent()->nId;
94}
95
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
113void 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 {
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 */
146 (
147 &a_leQueues[pfdPrev->nPrio],
148 &pfdPrev->leQueue
149 );
150 }
151 }
152}
153
155{
156 assert(pParam == GetFiberData());
157 Fbt_AfterSwitch(pParam);
158 DoStuff();
159 Fbt_Exit();
160}
161
162void 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;
181
182 bResume = 0;
183 i = 0;
184
185 /* Pick up from where we left last time */
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 */
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 */
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)
325
326 pCurFiber = pfdCur->pFiber;
327 free(pfdCur);
328 DeleteFiber(pCurFiber);
329 }
330 /* No next fiber: continue running the current one */
331}
332
334{
336}
337
338void Fbt_CreateFiber(int bInitial)
339{
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)
351 else
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 {
384 (
385 &a_leQueues[pData->nPrio],
386 &pData->leQueue
387 );
388 }
389}
390
391void DoStuff(void)
392{
393 unsigned i;
394 unsigned n;
395 unsigned nId;
396
397 n = rand() % 1000;
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
420int _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 {
433 }
434
435 for(i = 0; i < nFibers; ++ i)
436 Fbt_CreateFiber(i == 0);
437
439
440 return 0;
441}
442
443/* EOF */
static int argc
Definition: ServiceArgs.c:12
#define InterlockedIncrement
Definition: armddk.h:53
BOOL bExit
Definition: cmd.c:152
#define free
Definition: debug_ros.c:5
#define malloc
Definition: debug_ros.c:4
#define NULL
Definition: types.h:112
#define CALLBACK
Definition: compat.h:35
VOID WINAPI DeleteFiber(_In_ LPVOID lpFiber)
Definition: fiber.c:290
LPVOID WINAPI ConvertThreadToFiber(_In_opt_ LPVOID lpParameter)
Definition: fiber.c:162
LPVOID WINAPI CreateFiber(_In_ SIZE_T dwStackSize, _In_ LPFIBER_START_ROUTINE lpStartAddress, _In_opt_ LPVOID lpParameter)
Definition: fiber.c:174
#define assert(x)
Definition: debug.h:53
__kernel_time_t time_t
Definition: linux.h:252
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
#define InsertTailList(ListHead, Entry)
PSINGLE_LIST_ENTRY ple
GLdouble n
Definition: glext.h:7729
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLfloat * m
Definition: glext.h:10848
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define UINT_MAX
Definition: limits.h:41
#define stderr
Definition: stdio.h:100
void __cdecl srand(_In_ unsigned int _Seed)
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
#define _tcstoul
Definition: tchar.h:595
#define _tmain
Definition: tchar.h:497
#define _ftprintf
Definition: tchar.h:518
char _TCHAR
Definition: tchar.h:1392
#define b
Definition: ke_i.h:79
__u16 time
Definition: mkdosfs.c:8
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
#define RemoveHeadList(PLH__)
Definition: fiber.c:48
#define FIBERTEST_COUNT
Definition: fiber.c:54
void Fbt_Create(int)
#define InitializeListHead(PLH__)
Definition: fiber.c:11
void Fbt_Yield(void)
Definition: fiber.c:96
VOID CALLBACK Fbt_Startup(PVOID)
Definition: fiber.c:154
static LIST_ENTRY a_leQueues[32]
Definition: fiber.c:70
static struct FiberData * pfdLastStarveScan
Definition: fiber.c:72
void Fbt_Exit(void)
Definition: fiber.c:333
void DoStuff(void)
Definition: fiber.c:391
#define IsListEmpty(PLH__)
Definition: fiber.c:15
static unsigned nQuantum
Definition: fiber.c:71
struct FiberData * Fbt_GetCurrent(void)
Definition: fiber.c:86
void Fbt_AfterSwitch(struct FiberData *)
Definition: fiber.c:113
void Fbt_Dispatch(struct FiberData *, int)
Definition: fiber.c:162
unsigned Fbt_GetCurrentId(void)
Definition: fiber.c:91
void Fbt_CreateFiber(int bInitial)
Definition: fiber.c:338
int k
Definition: mpi.c:3369
#define argv
Definition: mplay32.c:18
long LONG
Definition: pedump.c:60
struct FiberData * pfdPrev
Definition: fiber.c:66
unsigned nMagic
Definition: fiber.c:58
LIST_ENTRY leQueue
Definition: fiber.c:63
int nQuantumQueued
Definition: fiber.c:64
unsigned nId
Definition: fiber.c:59
int bExitPrev
Definition: fiber.c:67
unsigned nRealPrio
Definition: fiber.c:61
int nBoost
Definition: fiber.c:65
PVOID pFiber
Definition: fiber.c:62
unsigned nPrio
Definition: fiber.c:60
Definition: typedefs.h:120
VOID WINAPI DECLSPEC_HOTPATCH Sleep(IN DWORD dwMilliseconds)
Definition: synch.c:790
TW_UINT32 TW_UINT16 TW_UINT16 TW_MEMREF pData
Definition: twain.h:1830
struct _LIST_ENTRY * PLIST_ENTRY
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
#define _T(x)
Definition: vfdio.h:22
void WINAPI SwitchToFiber(_In_ PVOID)
FORCEINLINE PVOID GetFiberData(VOID)
Definition: winnt_old.h:4373
unsigned char UCHAR
Definition: xmlstorage.h:181