js/src/jit-test/tests/v8-v5/check-richards.js

   1 // Copyright 2006-2008 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28
  29 // This is a JavaScript implementation of the Richards
  30 // benchmark from:
  31 //
  32 //    http://www.cl.cam.ac.uk/~mr10/Bench.html
  33 //
  34 // The benchmark was originally implemented in BCPL by
  35 // Martin Richards.
  36
  37
  38 //var Richards = new BenchmarkSuite('Richards', 34886, [
  39 //  new Benchmark("Richards", runRichards)
  40 //]);
  41
  42
  43 /**
  44  * The Richards benchmark simulates the task dispatcher of an
  45  * operating system.
  46  **/
  47 function runRichards() {
  48   var scheduler = new Scheduler();
  49   scheduler.addIdleTask(ID_IDLE, 0, null, COUNT);
  50
  51   var queue = new Packet(null, ID_WORKER, KIND_WORK);
  52   queue = new Packet(queue,  ID_WORKER, KIND_WORK);
  53   scheduler.addWorkerTask(ID_WORKER, 1000, queue);
  54
  55   queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE);
  56   queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
  57   queue = new Packet(queue,  ID_DEVICE_A, KIND_DEVICE);
  58   scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue);
  59
  60   queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE);
  61   queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
  62   queue = new Packet(queue,  ID_DEVICE_B, KIND_DEVICE);
  63   scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue);
  64
  65   scheduler.addDeviceTask(ID_DEVICE_A, 4000, null);
  66
  67   scheduler.addDeviceTask(ID_DEVICE_B, 5000, null);
  68
  69   scheduler.schedule();
  70
  71   assertEq(scheduler.queueCount, EXPECTED_QUEUE_COUNT);
  72   assertEq(scheduler.holdCount, EXPECTED_HOLD_COUNT);
  73 }
  74
  75 var COUNT = 1000;
  76
  77 /**
  78  * These two constants specify how many times a packet is queued and
  79  * how many times a task is put on hold in a correct run of richards.
  80  * They don't have any meaning a such but are characteristic of a
  81  * correct run so if the actual queue or hold count is different from
  82  * the expected there must be a bug in the implementation.
  83  **/
  84 var EXPECTED_QUEUE_COUNT = 2322;
  85 var EXPECTED_HOLD_COUNT = 928;
  86
  87
  88 /**
  89  * A scheduler can be used to schedule a set of tasks based on their relative
  90  * priorities.  Scheduling is done by maintaining a list of task control blocks
  91  * which holds tasks and the data queue they are processing.
  92  * @constructor
  93  */
  94 function Scheduler() {
  95   this.queueCount = 0;
  96   this.holdCount = 0;
  97   this.blocks = new Array(NUMBER_OF_IDS);
  98   this.list = null;
  99   this.currentTcb = null;
 100   this.currentId = null;
 101 }
 102
 103 var ID_IDLE       = 0;
 104 var ID_WORKER     = 1;
 105 var ID_HANDLER_A  = 2;
 106 var ID_HANDLER_B  = 3;
 107 var ID_DEVICE_A   = 4;
 108 var ID_DEVICE_B   = 5;
 109 var NUMBER_OF_IDS = 6;
 110
 111 var KIND_DEVICE   = 0;
 112 var KIND_WORK     = 1;
 113
 114 /**
 115  * Add an idle task to this scheduler.
 116  * @param {int} id the identity of the task
 117  * @param {int} priority the task's priority
 118  * @param {Packet} queue the queue of work to be processed by the task
 119  * @param {int} count the number of times to schedule the task
 120  */
 121 Scheduler.prototype.addIdleTask = function (id, priority, queue, count) {
 122   this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count));
 123 };
 124
 125 /**
 126  * Add a work task to this scheduler.
 127  * @param {int} id the identity of the task
 128  * @param {int} priority the task's priority
 129  * @param {Packet} queue the queue of work to be processed by the task
 130  */
 131 Scheduler.prototype.addWorkerTask = function (id, priority, queue) {
 132   this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0));
 133 };
 134
 135 /**
 136  * Add a handler task to this scheduler.
 137  * @param {int} id the identity of the task
 138  * @param {int} priority the task's priority
 139  * @param {Packet} queue the queue of work to be processed by the task
 140  */
 141 Scheduler.prototype.addHandlerTask = function (id, priority, queue) {
 142   this.addTask(id, priority, queue, new HandlerTask(this));
 143 };
 144
 145 /**
 146  * Add a handler task to this scheduler.
 147  * @param {int} id the identity of the task
 148  * @param {int} priority the task's priority
 149  * @param {Packet} queue the queue of work to be processed by the task
 150  */
 151 Scheduler.prototype.addDeviceTask = function (id, priority, queue) {
 152   this.addTask(id, priority, queue, new DeviceTask(this))
 153 };
 154
 155 /**
 156  * Add the specified task and mark it as running.
 157  * @param {int} id the identity of the task
 158  * @param {int} priority the task's priority
 159  * @param {Packet} queue the queue of work to be processed by the task
 160  * @param {Task} task the task to add
 161  */
 162 Scheduler.prototype.addRunningTask = function (id, priority, queue, task) {
 163   this.addTask(id, priority, queue, task);
 164   this.currentTcb.setRunning();
 165 };
 166
 167 /**
 168  * Add the specified task to this scheduler.
 169  * @param {int} id the identity of the task
 170  * @param {int} priority the task's priority
 171  * @param {Packet} queue the queue of work to be processed by the task
 172  * @param {Task} task the task to add
 173  */
 174 Scheduler.prototype.addTask = function (id, priority, queue, task) {
 175   this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task);
 176   this.list = this.currentTcb;
 177   this.blocks[id] = this.currentTcb;
 178 };
 179
 180 /**
 181  * Execute the tasks managed by this scheduler.
 182  */
 183 Scheduler.prototype.schedule = function () {
 184   this.currentTcb = this.list;
 185   while (this.currentTcb != null) {
 186     if (this.currentTcb.isHeldOrSuspended()) {
 187       this.currentTcb = this.currentTcb.link;
 188     } else {
 189       this.currentId = this.currentTcb.id;
 190       this.currentTcb = this.currentTcb.run();
 191     }
 192   }
 193 };
 194
 195 /**
 196  * Release a task that is currently blocked and return the next block to run.
 197  * @param {int} id the id of the task to suspend
 198  */
 199 Scheduler.prototype.release = function (id) {
 200   var tcb = this.blocks[id];
 201   if (tcb == null) return tcb;
 202   tcb.markAsNotHeld();
 203   if (tcb.priority > this.currentTcb.priority) {
 204     return tcb;
 205   } else {
 206     return this.currentTcb;
 207   }
 208 };
 209
 210 /**
 211  * Block the currently executing task and return the next task control block
 212  * to run.  The blocked task will not be made runnable until it is explicitly
 213  * released, even if new work is added to it.
 214  */
 215 Scheduler.prototype.holdCurrent = function () {
 216   this.holdCount++;
 217   this.currentTcb.markAsHeld();
 218   return this.currentTcb.link;
 219 };
 220
 221 /**
 222  * Suspend the currently executing task and return the next task control block
 223  * to run.  If new work is added to the suspended task it will be made runnable.
 224  */
 225 Scheduler.prototype.suspendCurrent = function () {
 226   this.currentTcb.markAsSuspended();
 227   return this.currentTcb;
 228 };
 229
 230 /**
 231  * Add the specified packet to the end of the worklist used by the task
 232  * associated with the packet and make the task runnable if it is currently
 233  * suspended.
 234  * @param {Packet} packet the packet to add
 235  */
 236 Scheduler.prototype.queue = function (packet) {
 237   var t = this.blocks[packet.id];
 238   if (t == null) return t;
 239   this.queueCount++;
 240   packet.link = null;
 241   packet.id = this.currentId;
 242   return t.checkPriorityAdd(this.currentTcb, packet);
 243 };
 244
 245 /**
 246  * A task control block manages a task and the queue of work packages associated
 247  * with it.
 248  * @param {TaskControlBlock} link the preceding block in the linked block list
 249  * @param {int} id the id of this block
 250  * @param {int} priority the priority of this block
 251  * @param {Packet} queue the queue of packages to be processed by the task
 252  * @param {Task} task the task
 253  * @constructor
 254  */
 255 function TaskControlBlock(link, id, priority, queue, task) {
 256   this.link = link;
 257   this.id = id;
 258   this.priority = priority;
 259   this.queue = queue;
 260   this.task = task;
 261   if (queue == null) {
 262     this.state = STATE_SUSPENDED;
 263   } else {
 264     this.state = STATE_SUSPENDED_RUNNABLE;
 265   }
 266 }
 267
 268 /**
 269  * The task is running and is currently scheduled.
 270  */
 271 var STATE_RUNNING = 0;
 272
 273 /**
 274  * The task has packets left to process.
 275  */
 276 var STATE_RUNNABLE = 1;
 277
 278 /**
 279  * The task is not currently running.  The task is not blocked as such and may
 280 * be started by the scheduler.
 281  */
 282 var STATE_SUSPENDED = 2;
 283
 284 /**
 285  * The task is blocked and cannot be run until it is explicitly released.
 286  */
 287 var STATE_HELD = 4;
 288
 289 var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
 290 var STATE_NOT_HELD = ~STATE_HELD;
 291
 292 TaskControlBlock.prototype.setRunning = function () {
 293   this.state = STATE_RUNNING;
 294 };
 295
 296 TaskControlBlock.prototype.markAsNotHeld = function () {
 297   this.state = this.state & STATE_NOT_HELD;
 298 };
 299
 300 TaskControlBlock.prototype.markAsHeld = function () {
 301   this.state = this.state | STATE_HELD;
 302 };
 303
 304 TaskControlBlock.prototype.isHeldOrSuspended = function () {
 305   return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
 306 };
 307
 308 TaskControlBlock.prototype.markAsSuspended = function () {
 309   this.state = this.state | STATE_SUSPENDED;
 310 };
 311
 312 TaskControlBlock.prototype.markAsRunnable = function () {
 313   this.state = this.state | STATE_RUNNABLE;
 314 };
 315
 316 /**
 317  * Runs this task, if it is ready to be run, and returns the next task to run.
 318  */
 319 TaskControlBlock.prototype.run = function () {
 320   var packet;
 321   if (this.state == STATE_SUSPENDED_RUNNABLE) {
 322     packet = this.queue;
 323     this.queue = packet.link;
 324     if (this.queue == null) {
 325       this.state = STATE_RUNNING;
 326     } else {
 327       this.state = STATE_RUNNABLE;
 328     }
 329   } else {
 330     packet = null;
 331   }
 332   return this.task.run(packet);
 333 };
 334
 335 /**
 336  * Adds a packet to the worklist of this block's task, marks this as runnable if
 337  * necessary, and returns the next runnable object to run (the one
 338  * with the highest priority).
 339  */
 340 TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) {
 341   if (this.queue == null) {
 342     this.queue = packet;
 343     this.markAsRunnable();
 344     if (this.priority > task.priority) return this;
 345   } else {
 346     this.queue = packet.addTo(this.queue);
 347   }
 348   return task;
 349 };
 350
 351 TaskControlBlock.prototype.toString = function () {
 352   return "tcb { " + this.task + "@" + this.state + " }";
 353 };
 354
 355 /**
 356  * An idle task doesn't do any work itself but cycles control between the two
 357  * device tasks.
 358  * @param {Scheduler} scheduler the scheduler that manages this task
 359  * @param {int} v1 a seed value that controls how the device tasks are scheduled
 360  * @param {int} count the number of times this task should be scheduled
 361  * @constructor
 362  */
 363 function IdleTask(scheduler, v1, count) {
 364   this.scheduler = scheduler;
 365   this.v1 = v1;
 366   this.count = count;
 367 }
 368
 369 IdleTask.prototype.run = function (packet) {
 370   this.count--;
 371   if (this.count == 0) return this.scheduler.holdCurrent();
 372   if ((this.v1 & 1) == 0) {
 373     this.v1 = this.v1 >> 1;
 374     return this.scheduler.release(ID_DEVICE_A);
 375   } else {
 376     this.v1 = (this.v1 >> 1) ^ 0xD008;
 377     return this.scheduler.release(ID_DEVICE_B);
 378   }
 379 };
 380
 381 IdleTask.prototype.toString = function () {
 382   return "IdleTask"
 383 };
 384
 385 /**
 386  * A task that suspends itself after each time it has been run to simulate
 387  * waiting for data from an external device.
 388  * @param {Scheduler} scheduler the scheduler that manages this task
 389  * @constructor
 390  */
 391 function DeviceTask(scheduler) {
 392   this.scheduler = scheduler;
 393   this.v1 = null;
 394 }
 395
 396 DeviceTask.prototype.run = function (packet) {
 397   if (packet == null) {
 398     if (this.v1 == null) return this.scheduler.suspendCurrent();
 399     var v = this.v1;
 400     this.v1 = null;
 401     return this.scheduler.queue(v);
 402   } else {
 403     this.v1 = packet;
 404     return this.scheduler.holdCurrent();
 405   }
 406 };
 407
 408 DeviceTask.prototype.toString = function () {
 409   return "DeviceTask";
 410 };
 411
 412 /**
 413  * A task that manipulates work packets.
 414  * @param {Scheduler} scheduler the scheduler that manages this task
 415  * @param {int} v1 a seed used to specify how work packets are manipulated
 416  * @param {int} v2 another seed used to specify how work packets are manipulated
 417  * @constructor
 418  */
 419 function WorkerTask(scheduler, v1, v2) {
 420   this.scheduler = scheduler;
 421   this.v1 = v1;
 422   this.v2 = v2;
 423 }
 424
 425 WorkerTask.prototype.run = function (packet) {
 426   if (packet == null) {
 427     return this.scheduler.suspendCurrent();
 428   } else {
 429     if (this.v1 == ID_HANDLER_A) {
 430       this.v1 = ID_HANDLER_B;
 431     } else {
 432       this.v1 = ID_HANDLER_A;
 433     }
 434     packet.id = this.v1;
 435     packet.a1 = 0;
 436     for (var i = 0; i < DATA_SIZE; i++) {
 437       this.v2++;
 438       if (this.v2 > 26) this.v2 = 1;
 439       packet.a2[i] = this.v2;
 440     }
 441     return this.scheduler.queue(packet);
 442   }
 443 };
 444
 445 WorkerTask.prototype.toString = function () {
 446   return "WorkerTask";
 447 };
 448
 449 /**
 450  * A task that manipulates work packets and then suspends itself.
 451  * @param {Scheduler} scheduler the scheduler that manages this task
 452  * @constructor
 453  */
 454 function HandlerTask(scheduler) {
 455   this.scheduler = scheduler;
 456   this.v1 = null;
 457   this.v2 = null;
 458 }
 459
 460 HandlerTask.prototype.run = function (packet) {
 461   if (packet != null) {
 462     if (packet.kind == KIND_WORK) {
 463       this.v1 = packet.addTo(this.v1);
 464     } else {
 465       this.v2 = packet.addTo(this.v2);
 466     }
 467   }
 468   if (this.v1 != null) {
 469     var count = this.v1.a1;
 470     var v;
 471     if (count < DATA_SIZE) {
 472       if (this.v2 != null) {
 473         v = this.v2;
 474         this.v2 = this.v2.link;
 475         v.a1 = this.v1.a2[count];
 476         this.v1.a1 = count + 1;
 477         return this.scheduler.queue(v);
 478       }
 479     } else {
 480       v = this.v1;
 481       this.v1 = this.v1.link;
 482       return this.scheduler.queue(v);
 483     }
 484   }
 485   return this.scheduler.suspendCurrent();
 486 };
 487
 488 HandlerTask.prototype.toString = function () {
 489   return "HandlerTask";
 490 };
 491
 492 /* --- *
 493  * P a c k e t
 494  * --- */
 495
 496 var DATA_SIZE = 4;
 497
 498 /**
 499  * A simple package of data that is manipulated by the tasks.  The exact layout
 500  * of the payload data carried by a packet is not importaint, and neither is the
 501  * nature of the work performed on packets by the tasks.
 502  *
 503  * Besides carrying data, packets form linked lists and are hence used both as
 504  * data and worklists.
 505  * @param {Packet} link the tail of the linked list of packets
 506  * @param {int} id an ID for this packet
 507  * @param {int} kind the type of this packet
 508  * @constructor
 509  */
 510 function Packet(link, id, kind) {
 511   this.link = link;
 512   this.id = id;
 513   this.kind = kind;
 514   this.a1 = 0;
 515   this.a2 = new Array(DATA_SIZE);
 516 }
 517
 518 /**
 519  * Add this packet to the end of a worklist, and return the worklist.
 520  * @param {Packet} queue the worklist to add this packet to
 521  */
 522 Packet.prototype.addTo = function (queue) {
 523   this.link = null;
 524   if (queue == null) return this;
 525   var peek, next = queue;
 526   while ((peek = next.link) != null)
 527     next = peek;
 528   next.link = this;
 529   return queue;
 530 };
 531
 532 Packet.prototype.toString = function () {
 533   return "Packet";
 534 };
 535
 536 runRichards();