rostests/tests/fiber/fiber.c

   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
  86 struct FiberData * Fbt_GetCurrent(VOID)
  87 {
  88  return GetFiberData();
  89 }
  90
  91 unsigned Fbt_GetCurrentId(VOID)
  92 {
  93  return Fbt_GetCurrent()->nId;
  94 }
  95
  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
 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
 154 VOID CALLBACK Fbt_Startup(PVOID pParam)
 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 */
 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
 333 void Fbt_Exit(VOID)
 334 {
 335  Fbt_Dispatch(GetFiberData(), 1);
 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)
 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
 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  {
 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 */