rosapps/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 */