ReactOS 0.4.15-dev-7842-g558ab78
fiber.c File Reference
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <tchar.h>
#include <windows.h>
Include dependency graph for fiber.c:

Go to the source code of this file.

Classes

struct  FiberData
 

Macros

#define InitializeListHead(PLH__)   ((PLH__)->Flink = (PLH__)->Blink = (PLH__))
 
#define IsListEmpty(PLH__)   ((PLH__)->Flink == (PVOID)(PLH__))
 
#define RemoveEntryList(PLE__)
 
#define InsertTailList(PLH__, PLE__)
 
#define RemoveHeadList(PLH__)
 
#define FIBERTEST_COUNT   500
 

Functions

void Fbt_Create (int)
 
void Fbt_Exit (void)
 
void Fbt_Yield (void)
 
struct FiberDataFbt_GetCurrent (void)
 
unsigned Fbt_GetCurrentId (void)
 
VOID CALLBACK Fbt_Startup (PVOID)
 
void Fbt_Dispatch (struct FiberData *, int)
 
void Fbt_AfterSwitch (struct FiberData *)
 
void DoStuff (void)
 
void Fbt_CreateFiber (int bInitial)
 
int _tmain (int argc, _TCHAR const *const *argv)
 

Variables

static LIST_ENTRY a_leQueues [32]
 
static unsigned nQuantum = 0
 
static struct FiberDatapfdLastStarveScan = NULL
 

Macro Definition Documentation

◆ FIBERTEST_COUNT

#define FIBERTEST_COUNT   500

Definition at line 54 of file fiber.c.

◆ InitializeListHead

#define InitializeListHead (   PLH__)    ((PLH__)->Flink = (PLH__)->Blink = (PLH__))

Definition at line 11 of file fiber.c.

◆ InsertTailList

#define InsertTailList (   PLH__,
  PLE__ 
)
Value:
{ \
PLIST_ENTRY pleListHead__ = (PLH__); \
PLIST_ENTRY pleBlink__ = (PLIST_ENTRY)((PLH__)->Blink); \
\
(PLE__)->Flink = pleListHead__; \
(PLE__)->Blink = pleBlink__; \
pleBlink__->Flink = (PLE__); \
pleListHead__->Blink = (PLE__); \
}
Definition: typedefs.h:120
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
struct _LIST_ENTRY * PLIST_ENTRY

Definition at line 33 of file fiber.c.

◆ IsListEmpty

#define IsListEmpty (   PLH__)    ((PLH__)->Flink == (PVOID)(PLH__))

Definition at line 15 of file fiber.c.

◆ RemoveEntryList

#define RemoveEntryList (   PLE__)
Value:
{ \
PLIST_ENTRY pleBack__ = (PLIST_ENTRY)((PLE__)->Blink); \
PLIST_ENTRY pleForward__ = (PLIST_ENTRY)((PLE__)->Flink); \
\
pleBack__->Flink = pleForward__; \
pleForward__->Blink = pleBack__; \
}

Definition at line 20 of file fiber.c.

◆ RemoveHeadList

#define RemoveHeadList (   PLH__)
Value:
(PLIST_ENTRY)((PLH__)->Flink); \
RemoveEntryList((PLIST_ENTRY)((PLH__)->Flink));

Definition at line 48 of file fiber.c.

Function Documentation

◆ _tmain()

int _tmain ( int  argc,
_TCHAR const *const argv 
)

Definition at line 420 of file fiber.c.

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}
static int argc
Definition: ServiceArgs.c:12
#define NULL
Definition: types.h:112
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
#define _tcstoul
Definition: tchar.h:595
#define FIBERTEST_COUNT
Definition: fiber.c:54
#define InitializeListHead(PLH__)
Definition: fiber.c:11
VOID CALLBACK Fbt_Startup(PVOID)
Definition: fiber.c:154
static LIST_ENTRY a_leQueues[32]
Definition: fiber.c:70
void Fbt_CreateFiber(int bInitial)
Definition: fiber.c:338
#define argv
Definition: mplay32.c:18
FORCEINLINE PVOID GetFiberData(VOID)
Definition: winnt_old.h:4373

◆ DoStuff()

void DoStuff ( void  )

Definition at line 391 of file fiber.c.

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}
GLdouble n
Definition: glext.h:7729
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 GLint GLint j
Definition: glfuncs.h:250
#define stderr
Definition: stdio.h:100
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
#define _ftprintf
Definition: tchar.h:518
void Fbt_Yield(void)
Definition: fiber.c:96
unsigned Fbt_GetCurrentId(void)
Definition: fiber.c:91
VOID WINAPI DECLSPEC_HOTPATCH Sleep(IN DWORD dwMilliseconds)
Definition: synch.c:790
#define _T(x)
Definition: vfdio.h:22

Referenced by Fbt_Startup().

◆ Fbt_AfterSwitch()

void Fbt_AfterSwitch ( struct FiberData pfdCur)

Definition at line 113 of file fiber.c.

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}
#define free
Definition: debug_ros.c:5
VOID WINAPI DeleteFiber(_In_ LPVOID lpFiber)
Definition: fiber.c:290
#define InsertTailList(ListHead, Entry)
static struct FiberData * pfdLastStarveScan
Definition: fiber.c:72
static unsigned nQuantum
Definition: fiber.c:71
struct FiberData * pfdPrev
Definition: fiber.c:66
int bExitPrev
Definition: fiber.c:67

Referenced by Fbt_Dispatch(), and Fbt_Startup().

◆ Fbt_Create()

void Fbt_Create ( int  )

◆ Fbt_CreateFiber()

void Fbt_CreateFiber ( int  bInitial)

Definition at line 338 of file fiber.c.

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}
#define InterlockedIncrement
Definition: armddk.h:53
#define malloc
Definition: debug_ros.c:4
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
void __cdecl srand(_In_ unsigned int _Seed)
__u16 time
Definition: mkdosfs.c:8
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
long LONG
Definition: pedump.c:60
PVOID pFiber
Definition: fiber.c:62
TW_UINT32 TW_UINT16 TW_UINT16 TW_MEMREF pData
Definition: twain.h:1830

Referenced by _tmain().

◆ Fbt_Dispatch()

void Fbt_Dispatch ( struct FiberData pfdCur,
int  bExit 
)

Definition at line 162 of file fiber.c.

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}
BOOL bExit
Definition: cmd.c:152
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
PSINGLE_LIST_ENTRY ple
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define UINT_MAX
Definition: limits.h:41
#define b
Definition: ke_i.h:79
#define RemoveHeadList(PLH__)
Definition: fiber.c:48
#define IsListEmpty(PLH__)
Definition: fiber.c:15
void Fbt_AfterSwitch(struct FiberData *)
Definition: fiber.c:113
int k
Definition: mpi.c:3369
unsigned nMagic
Definition: fiber.c:58
LIST_ENTRY leQueue
Definition: fiber.c:63
unsigned nPrio
Definition: fiber.c:60
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
void WINAPI SwitchToFiber(_In_ PVOID)
unsigned char UCHAR
Definition: xmlstorage.h:181

Referenced by Fbt_Exit(), and Fbt_Yield().

◆ Fbt_Exit()

void Fbt_Exit ( void  )

Definition at line 333 of file fiber.c.

334{
336}
void Fbt_Dispatch(struct FiberData *, int)
Definition: fiber.c:162

Referenced by Fbt_Startup().

◆ Fbt_GetCurrent()

struct FiberData * Fbt_GetCurrent ( void  )

Definition at line 86 of file fiber.c.

87{
88 return GetFiberData();
89}

Referenced by Fbt_GetCurrentId(), and Fbt_Yield().

◆ Fbt_GetCurrentId()

unsigned Fbt_GetCurrentId ( void  )

Definition at line 91 of file fiber.c.

92{
93 return Fbt_GetCurrent()->nId;
94}
struct FiberData * Fbt_GetCurrent(void)
Definition: fiber.c:86

Referenced by DoStuff().

◆ Fbt_Startup()

VOID CALLBACK Fbt_Startup ( PVOID  pParam)

Definition at line 154 of file fiber.c.

155{
156 assert(pParam == GetFiberData());
157 Fbt_AfterSwitch(pParam);
158 DoStuff();
159 Fbt_Exit();
160}
void Fbt_Exit(void)
Definition: fiber.c:333
void DoStuff(void)
Definition: fiber.c:391

Referenced by _tmain(), and Fbt_CreateFiber().

◆ Fbt_Yield()

void Fbt_Yield ( void  )

Definition at line 96 of file fiber.c.

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}
unsigned nRealPrio
Definition: fiber.c:61
int nBoost
Definition: fiber.c:65

Referenced by DoStuff().

Variable Documentation

◆ a_leQueues

LIST_ENTRY a_leQueues[32]
static

Definition at line 70 of file fiber.c.

Referenced by _tmain(), Fbt_AfterSwitch(), Fbt_CreateFiber(), and Fbt_Dispatch().

◆ nQuantum

unsigned nQuantum = 0
static

Definition at line 71 of file fiber.c.

Referenced by Fbt_AfterSwitch(), and Fbt_Dispatch().

◆ pfdLastStarveScan

struct FiberData* pfdLastStarveScan = NULL
static

Definition at line 72 of file fiber.c.

Referenced by Fbt_AfterSwitch(), and Fbt_Dispatch().