ReactOS  0.4.14-dev-384-g5b37caa
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 
56 struct FiberData
57 {
58  unsigned nMagic;
59  unsigned nId;
60  unsigned nPrio;
61  unsigned nRealPrio;
65  int nBoost;
66  struct FiberData * pfdPrev;
67  int bExitPrev;
68 };
69 
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);
81 void Fbt_Dispatch(struct FiberData *, int);
82 void Fbt_AfterSwitch(struct FiberData *);
83 
84 void 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 
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  {
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 */
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 
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 */
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 
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)
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 
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 
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  {
433  }
434 
435  for(i = 0; i < nFibers; ++ i)
436  Fbt_CreateFiber(i == 0);
437 
439 
440  return 0;
441 }
442 
443 /* EOF */
struct _LIST_ENTRY * PLIST_ENTRY
void Fbt_Dispatch(struct FiberData *, int)
Definition: fiber.c:162
struct FiberData * pfdPrev
Definition: fiber.c:66
static int argc
Definition: ServiceArgs.c:12
VOID WINAPI DECLSPEC_HOTPATCH Sleep(IN DWORD dwMilliseconds)
Definition: synch.c:790
void DoStuff(void)
Definition: fiber.c:391
static LIST_ENTRY a_leQueues[32]
Definition: fiber.c:70
#define free
Definition: debug_ros.c:5
#define CALLBACK
Definition: compat.h:27
void __cdecl srand(_In_ unsigned int _Seed)
GLdouble n
Definition: glext.h:7729
#define assert(x)
Definition: debug.h:53
__u16 time
Definition: mkdosfs.c:366
#define argv
Definition: mplay32.c:18
int nBoost
Definition: fiber.c:65
VOID CALLBACK Fbt_Startup(PVOID)
Definition: fiber.c:154
const GLfloat * m
Definition: glext.h:10848
struct FiberData * Fbt_GetCurrent(void)
Definition: fiber.c:86
#define RemoveHeadList(PLH__)
Definition: fiber.c:48
void Fbt_AfterSwitch(struct FiberData *)
Definition: fiber.c:113
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
long LONG
Definition: pedump.c:60
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
LIST_ENTRY leQueue
Definition: fiber.c:63
PVOID pFiber
Definition: fiber.c:62
LPVOID WINAPI ConvertThreadToFiber(_In_opt_ LPVOID lpParameter)
Definition: fiber.c:162
FORCEINLINE PVOID GetFiberData(void)
Definition: winnt_old.h:4158
unsigned nRealPrio
Definition: fiber.c:61
smooth NULL
Definition: ftsmooth.c:416
int _tmain(int argc, _TCHAR const *const *argv)
Definition: fiber.c:420
void Fbt_CreateFiber(int bInitial)
Definition: fiber.c:338
#define _ftprintf
Definition: tchar.h:518
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
#define b
Definition: ke_i.h:79
char _TCHAR
Definition: tchar.h:1392
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
int nQuantumQueued
Definition: fiber.c:64
unsigned nMagic
Definition: fiber.c:58
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define _T(x)
Definition: vfdio.h:22
#define IsListEmpty(PLH__)
Definition: fiber.c:15
VOID WINAPI DeleteFiber(_In_ LPVOID lpFiber)
Definition: fiber.c:290
void WINAPI SwitchToFiber(_In_ PVOID)
unsigned char UCHAR
Definition: xmlstorage.h:181
void Fbt_Yield(void)
Definition: fiber.c:96
#define _tcstoul
Definition: tchar.h:595
unsigned nPrio
Definition: fiber.c:60
#define InsertTailList(PLH__, PLE__)
Definition: fiber.c:33
unsigned Fbt_GetCurrentId(void)
Definition: fiber.c:91
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
Definition: typedefs.h:117
void Fbt_Create(int)
unsigned nId
Definition: fiber.c:59
#define UINT_MAX
Definition: limits.h:41
#define InterlockedIncrement
Definition: armddk.h:53
__kernel_time_t time_t
Definition: linux.h:252
int bExitPrev
Definition: fiber.c:67
#define InitializeListHead(PLH__)
Definition: fiber.c:11
static unsigned nQuantum
Definition: fiber.c:71
BOOL bExit
Definition: cmd.c:152
static struct FiberData * pfdLastStarveScan
Definition: fiber.c:72
void Fbt_Exit(void)
Definition: fiber.c:333
FILE * stderr
#define malloc
Definition: debug_ros.c:4
TW_UINT32 TW_UINT16 TW_UINT16 TW_MEMREF pData
Definition: twain.h:1827
#define RemoveEntryList(PLE__)
Definition: fiber.c:20
int k
Definition: mpi.c:3369
LPVOID WINAPI CreateFiber(_In_ SIZE_T dwStackSize, _In_ LPFIBER_START_ROUTINE lpStartAddress, _In_opt_ LPVOID lpParameter)
Definition: fiber.c:174
#define FIBERTEST_COUNT
Definition: fiber.c:54