src/system/kernel/device_manager/IOSchedulerSimple.cpp

   1 /*
   2  * Copyright 2008-2011, Ingo Weinhold, ingo_weinhold@gmx.de.
   3  * Copyright 2004-2010, Axel Dörfler, axeld@pinc-software.de.
   4  * Distributed under the terms of the MIT License.
   5  */
   6
   7
   8 #include "IOSchedulerSimple.h"
   9
  10 #include <unistd.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 #include <algorithm>
  16
  17 #include <lock.h>
  18 #include <thread_types.h>
  19 #include <thread.h>
  20 #include <util/AutoLock.h>
  21
  22 #include "IOSchedulerRoster.h"
  23
  24
  25 //#define TRACE_IO_SCHEDULER
  26 #ifdef TRACE_IO_SCHEDULER
  27 #       define TRACE(x...) dprintf(x)
  28 #else
  29 #       define TRACE(x...) ;
  30 #endif
  31
  32
  33 // #pragma mark -
  34
  35
  36 void
  37 IORequestOwner::Dump() const
  38 {
  39         kprintf("IORequestOwner at %p\n", this);
  40         kprintf("  team:     %" B_PRId32 "\n", team);
  41         kprintf("  thread:   %" B_PRId32 "\n", thread);
  42         kprintf("  priority: %" B_PRId32 "\n", priority);
  43
  44         kprintf("  requests:");
  45         for (IORequestList::ConstIterator it = requests.GetIterator();
  46                         IORequest* request = it.Next();) {
  47                 kprintf(" %p", request);
  48         }
  49         kprintf("\n");
  50
  51         kprintf("  completed requests:");
  52         for (IORequestList::ConstIterator it = completed_requests.GetIterator();
  53                         IORequest* request = it.Next();) {
  54                 kprintf(" %p", request);
  55         }
  56         kprintf("\n");
  57
  58         kprintf("  operations:");
  59         for (IOOperationList::ConstIterator it = operations.GetIterator();
  60                         IOOperation* operation = it.Next();) {
  61                 kprintf(" %p", operation);
  62         }
  63         kprintf("\n");
  64 }
  65
  66
  67 // #pragma mark -
  68
  69
  70 struct IOSchedulerSimple::RequestOwnerHashDefinition {
  71         typedef thread_id               KeyType;
  72         typedef IORequestOwner  ValueType;
  73
  74         size_t HashKey(thread_id key) const                             { return key; }
  75         size_t Hash(const IORequestOwner* value) const  { return value->thread; }
  76         bool Compare(thread_id key, const IORequestOwner* value) const
  77                 { return value->thread == key; }
  78         IORequestOwner*& GetLink(IORequestOwner* value) const
  79                 { return value->hash_link; }
  80 };
  81
  82 struct IOSchedulerSimple::RequestOwnerHashTable
  83                 : BOpenHashTable<RequestOwnerHashDefinition, false> {
  84 };
  85
  86
  87 IOSchedulerSimple::IOSchedulerSimple(DMAResource* resource)
  88         :
  89         IOScheduler(resource),
  90         fSchedulerThread(-1),
  91         fRequestNotifierThread(-1),
  92         fOperationArray(NULL),
  93         fAllocatedRequestOwners(NULL),
  94         fRequestOwners(NULL),
  95         fBlockSize(0),
  96         fPendingOperations(0),
  97         fTerminating(false)
  98 {
  99         mutex_init(&fLock, "I/O scheduler");
 100         B_INITIALIZE_SPINLOCK(&fFinisherLock);
 101
 102         fNewRequestCondition.Init(this, "I/O new request");
 103         fFinishedOperationCondition.Init(this, "I/O finished operation");
 104         fFinishedRequestCondition.Init(this, "I/O finished request");
 105
 106 }
 107
 108
 109 IOSchedulerSimple::~IOSchedulerSimple()
 110 {
 111         // shutdown threads
 112         MutexLocker locker(fLock);
 113         InterruptsSpinLocker finisherLocker(fFinisherLock);
 114         fTerminating = true;
 115
 116         fNewRequestCondition.NotifyAll();
 117         fFinishedOperationCondition.NotifyAll();
 118         fFinishedRequestCondition.NotifyAll();
 119
 120         finisherLocker.Unlock();
 121         locker.Unlock();
 122
 123         if (fSchedulerThread >= 0)
 124                 wait_for_thread(fSchedulerThread, NULL);
 125
 126         if (fRequestNotifierThread >= 0)
 127                 wait_for_thread(fRequestNotifierThread, NULL);
 128
 129         // destroy our belongings
 130         mutex_lock(&fLock);
 131         mutex_destroy(&fLock);
 132
 133         while (IOOperation* operation = fUnusedOperations.RemoveHead())
 134                 delete operation;
 135
 136         delete[] fOperationArray;
 137
 138         delete fRequestOwners;
 139         delete[] fAllocatedRequestOwners;
 140 }
 141
 142
 143 status_t
 144 IOSchedulerSimple::Init(const char* name)
 145 {
 146         status_t error = IOScheduler::Init(name);
 147         if (error != B_OK)
 148                 return error;
 149
 150         size_t count = fDMAResource != NULL ? fDMAResource->BufferCount() : 16;
 151         for (size_t i = 0; i < count; i++) {
 152                 IOOperation* operation = new(std::nothrow) IOOperation;
 153                 if (operation == NULL)
 154                         return B_NO_MEMORY;
 155
 156                 fUnusedOperations.Add(operation);
 157         }
 158
 159         fOperationArray = new(std::nothrow) IOOperation*[count];
 160
 161         if (fDMAResource != NULL)
 162                 fBlockSize = fDMAResource->BlockSize();
 163         if (fBlockSize == 0)
 164                 fBlockSize = 512;
 165
 166         fAllocatedRequestOwnerCount = thread_max_threads();
 167         fAllocatedRequestOwners
 168                 = new(std::nothrow) IORequestOwner[fAllocatedRequestOwnerCount];
 169         if (fAllocatedRequestOwners == NULL)
 170                 return B_NO_MEMORY;
 171
 172         for (int32 i = 0; i < fAllocatedRequestOwnerCount; i++) {
 173                 IORequestOwner& owner = fAllocatedRequestOwners[i];
 174                 owner.team = -1;
 175                 owner.thread = -1;
 176                 owner.priority = B_IDLE_PRIORITY;
 177                 fUnusedRequestOwners.Add(&owner);
 178         }
 179
 180         fRequestOwners = new(std::nothrow) RequestOwnerHashTable;
 181         if (fRequestOwners == NULL)
 182                 return B_NO_MEMORY;
 183
 184         error = fRequestOwners->Init(fAllocatedRequestOwnerCount);
 185         if (error != B_OK)
 186                 return error;
 187
 188         // TODO: Use a device speed dependent bandwidths!
 189         fIterationBandwidth = fBlockSize * 8192;
 190         fMinOwnerBandwidth = fBlockSize * 1024;
 191         fMaxOwnerBandwidth = fBlockSize * 4096;
 192
 193         // start threads
 194         char buffer[B_OS_NAME_LENGTH];
 195         strlcpy(buffer, name, sizeof(buffer));
 196         strlcat(buffer, " scheduler ", sizeof(buffer));
 197         size_t nameLength = strlen(buffer);
 198         snprintf(buffer + nameLength, sizeof(buffer) - nameLength, "%" B_PRId32,
 199                 fID);
 200         fSchedulerThread = spawn_kernel_thread(&_SchedulerThread, buffer,
 201                 B_NORMAL_PRIORITY + 2, (void *)this);
 202         if (fSchedulerThread < B_OK)
 203                 return fSchedulerThread;
 204
 205         strlcpy(buffer, name, sizeof(buffer));
 206         strlcat(buffer, " notifier ", sizeof(buffer));
 207         nameLength = strlen(buffer);
 208         snprintf(buffer + nameLength, sizeof(buffer) - nameLength, "%" B_PRId32,
 209                 fID);
 210         fRequestNotifierThread = spawn_kernel_thread(&_RequestNotifierThread,
 211                 buffer, B_NORMAL_PRIORITY + 2, (void *)this);
 212         if (fRequestNotifierThread < B_OK)
 213                 return fRequestNotifierThread;
 214
 215         resume_thread(fSchedulerThread);
 216         resume_thread(fRequestNotifierThread);
 217
 218         return B_OK;
 219 }
 220
 221
 222 status_t
 223 IOSchedulerSimple::ScheduleRequest(IORequest* request)
 224 {
 225         TRACE("%p->IOSchedulerSimple::ScheduleRequest(%p)\n", this, request);
 226
 227         IOBuffer* buffer = request->Buffer();
 228
 229         // TODO: it would be nice to be able to lock the memory later, but we can't
 230         // easily do it in the I/O scheduler without being able to asynchronously
 231         // lock memory (via another thread or a dedicated call).
 232
 233         if (buffer->IsVirtual()) {
 234                 status_t status = buffer->LockMemory(request->TeamID(),
 235                         request->IsWrite());
 236                 if (status != B_OK) {
 237                         request->SetStatusAndNotify(status);
 238                         return status;
 239                 }
 240         }
 241
 242         MutexLocker locker(fLock);
 243
 244         IORequestOwner* owner = _GetRequestOwner(request->TeamID(),
 245                 request->ThreadID(), true);
 246         if (owner == NULL) {
 247                 panic("IOSchedulerSimple: Out of request owners!\n");
 248                 locker.Unlock();
 249                 if (buffer->IsVirtual())
 250                         buffer->UnlockMemory(request->TeamID(), request->IsWrite());
 251                 request->SetStatusAndNotify(B_NO_MEMORY);
 252                 return B_NO_MEMORY;
 253         }
 254
 255         bool wasActive = owner->IsActive();
 256         request->SetOwner(owner);
 257         owner->requests.Add(request);
 258
 259         int32 priority = thread_get_io_priority(request->ThreadID());
 260         if (priority >= 0)
 261                 owner->priority = priority;
 262 //dprintf("  request %p -> owner %p (thread %ld, active %d)\n", request, owner, owner->thread, wasActive);
 263
 264         if (!wasActive)
 265                 fActiveRequestOwners.Add(owner);
 266
 267         IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_REQUEST_SCHEDULED, this,
 268                 request);
 269
 270         fNewRequestCondition.NotifyAll();
 271
 272         return B_OK;
 273 }
 274
 275
 276 void
 277 IOSchedulerSimple::AbortRequest(IORequest* request, status_t status)
 278 {
 279         // TODO:...
 280 //B_CANCELED
 281 }
 282
 283
 284 void
 285 IOSchedulerSimple::OperationCompleted(IOOperation* operation, status_t status,
 286         generic_size_t transferredBytes)
 287 {
 288         InterruptsSpinLocker _(fFinisherLock);
 289
 290         // finish operation only once
 291         if (operation->Status() <= 0)
 292                 return;
 293
 294         operation->SetStatus(status);
 295
 296         // set the bytes transferred (of the net data)
 297         generic_size_t partialBegin
 298                 = operation->OriginalOffset() - operation->Offset();
 299         operation->SetTransferredBytes(
 300                 transferredBytes > partialBegin ? transferredBytes - partialBegin : 0);
 301
 302         fCompletedOperations.Add(operation);
 303         fFinishedOperationCondition.NotifyAll();
 304 }
 305
 306
 307 void
 308 IOSchedulerSimple::Dump() const
 309 {
 310         kprintf("IOSchedulerSimple at %p\n", this);
 311         kprintf("  DMA resource:   %p\n", fDMAResource);
 312
 313         kprintf("  active request owners:");
 314         for (RequestOwnerList::ConstIterator it
 315                                 = fActiveRequestOwners.GetIterator();
 316                         IORequestOwner* owner = it.Next();) {
 317                 kprintf(" %p", owner);
 318         }
 319         kprintf("\n");
 320 }
 321
 322
 323 /*!     Must not be called with the fLock held. */
 324 void
 325 IOSchedulerSimple::_Finisher()
 326 {
 327         while (true) {
 328                 InterruptsSpinLocker locker(fFinisherLock);
 329                 IOOperation* operation = fCompletedOperations.RemoveHead();
 330                 if (operation == NULL)
 331                         return;
 332
 333                 locker.Unlock();
 334
 335                 TRACE("IOSchedulerSimple::_Finisher(): operation: %p\n", operation);
 336
 337                 bool operationFinished = operation->Finish();
 338
 339                 IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_OPERATION_FINISHED,
 340                         this, operation->Parent(), operation);
 341                         // Notify for every time the operation is passed to the I/O hook,
 342                         // not only when it is fully finished.
 343
 344                 if (!operationFinished) {
 345                         TRACE("  operation: %p not finished yet\n", operation);
 346                         MutexLocker _(fLock);
 347                         operation->SetTransferredBytes(0);
 348                         operation->Parent()->Owner()->operations.Add(operation);
 349                         fPendingOperations--;
 350                         continue;
 351                 }
 352
 353                 // notify request and remove operation
 354                 IORequest* request = operation->Parent();
 355
 356                 generic_size_t operationOffset
 357                         = operation->OriginalOffset() - request->Offset();
 358                 request->OperationFinished(operation, operation->Status(),
 359                         operation->TransferredBytes() < operation->OriginalLength(),
 360                         operation->Status() == B_OK
 361                                 ? operationOffset + operation->OriginalLength()
 362                                 : operationOffset);
 363
 364                 // recycle the operation
 365                 MutexLocker _(fLock);
 366                 if (fDMAResource != NULL)
 367                         fDMAResource->RecycleBuffer(operation->Buffer());
 368
 369                 fPendingOperations--;
 370                 fUnusedOperations.Add(operation);
 371
 372                 // If the request is done, we need to perform its notifications.
 373                 if (request->IsFinished()) {
 374                         if (request->Status() == B_OK && request->RemainingBytes() > 0) {
 375                                 // The request has been processed OK so far, but it isn't really
 376                                 // finished yet.
 377                                 request->SetUnfinished();
 378                         } else {
 379                                 // Remove the request from the request owner.
 380                                 IORequestOwner* owner = request->Owner();
 381                                 owner->requests.MoveFrom(&owner->completed_requests);
 382                                 owner->requests.Remove(request);
 383                                 request->SetOwner(NULL);
 384
 385                                 if (!owner->IsActive()) {
 386                                         fActiveRequestOwners.Remove(owner);
 387                                         fUnusedRequestOwners.Add(owner);
 388                                 }
 389
 390                                 if (request->HasCallbacks()) {
 391                                         // The request has callbacks that may take some time to
 392                                         // perform, so we hand it over to the request notifier.
 393                                         fFinishedRequests.Add(request);
 394                                         fFinishedRequestCondition.NotifyAll();
 395                                 } else {
 396                                         // No callbacks -- finish the request right now.
 397                                         IOSchedulerRoster::Default()->Notify(
 398                                                 IO_SCHEDULER_REQUEST_FINISHED, this, request);
 399                                         request->NotifyFinished();
 400                                 }
 401                         }
 402                 }
 403         }
 404 }
 405
 406
 407 /*!     Called with \c fFinisherLock held.
 408 */
 409 bool
 410 IOSchedulerSimple::_FinisherWorkPending()
 411 {
 412         return !fCompletedOperations.IsEmpty();
 413 }
 414
 415
 416 bool
 417 IOSchedulerSimple::_PrepareRequestOperations(IORequest* request,
 418         IOOperationList& operations, int32& operationsPrepared, off_t quantum,
 419         off_t& usedBandwidth)
 420 {
 421 //dprintf("IOSchedulerSimple::_PrepareRequestOperations(%p)\n", request);
 422         usedBandwidth = 0;
 423
 424         if (fDMAResource != NULL) {
 425                 while (quantum >= (off_t)fBlockSize && request->RemainingBytes() > 0) {
 426                         IOOperation* operation = fUnusedOperations.RemoveHead();
 427                         if (operation == NULL)
 428                                 return false;
 429
 430                         status_t status = fDMAResource->TranslateNext(request, operation,
 431                                 quantum);
 432                         if (status != B_OK) {
 433                                 operation->SetParent(NULL);
 434                                 fUnusedOperations.Add(operation);
 435
 436                                 // B_BUSY means some resource (DMABuffers or
 437                                 // DMABounceBuffers) was temporarily unavailable. That's OK,
 438                                 // we'll retry later.
 439                                 if (status == B_BUSY)
 440                                         return false;
 441
 442                                 AbortRequest(request, status);
 443                                 return true;
 444                         }
 445 //dprintf("  prepared operation %p\n", operation);
 446
 447                         off_t bandwidth = operation->Length();
 448                         quantum -= bandwidth;
 449                         usedBandwidth += bandwidth;
 450
 451                         operations.Add(operation);
 452                         operationsPrepared++;
 453                 }
 454         } else {
 455                 // TODO: If the device has block size restrictions, we might need to use
 456                 // a bounce buffer.
 457                 IOOperation* operation = fUnusedOperations.RemoveHead();
 458                 if (operation == NULL)
 459                         return false;
 460
 461                 status_t status = operation->Prepare(request);
 462                 if (status != B_OK) {
 463                         operation->SetParent(NULL);
 464                         fUnusedOperations.Add(operation);
 465                         AbortRequest(request, status);
 466                         return true;
 467                 }
 468
 469                 operation->SetOriginalRange(request->Offset(), request->Length());
 470                 request->Advance(request->Length());
 471
 472                 off_t bandwidth = operation->Length();
 473                 quantum -= bandwidth;
 474                 usedBandwidth += bandwidth;
 475
 476                 operations.Add(operation);
 477                 operationsPrepared++;
 478         }
 479
 480         return true;
 481 }
 482
 483
 484 off_t
 485 IOSchedulerSimple::_ComputeRequestOwnerBandwidth(int32 priority) const
 486 {
 487 // TODO: Use a priority dependent quantum!
 488         return fMinOwnerBandwidth;
 489 }
 490
 491
 492 bool
 493 IOSchedulerSimple::_NextActiveRequestOwner(IORequestOwner*& owner,
 494         off_t& quantum)
 495 {
 496         while (true) {
 497                 if (fTerminating)
 498                         return false;
 499
 500                 if (owner != NULL)
 501                         owner = fActiveRequestOwners.GetNext(owner);
 502                 if (owner == NULL)
 503                         owner = fActiveRequestOwners.Head();
 504
 505                 if (owner != NULL) {
 506                         quantum = _ComputeRequestOwnerBandwidth(owner->priority);
 507                         return true;
 508                 }
 509
 510                 // Wait for new requests owners. First check whether any finisher work
 511                 // has to be done.
 512                 InterruptsSpinLocker finisherLocker(fFinisherLock);
 513                 if (_FinisherWorkPending()) {
 514                         finisherLocker.Unlock();
 515                         mutex_unlock(&fLock);
 516                         _Finisher();
 517                         mutex_lock(&fLock);
 518                         continue;
 519                 }
 520
 521                 // Wait for new requests.
 522                 ConditionVariableEntry entry;
 523                 fNewRequestCondition.Add(&entry);
 524
 525                 finisherLocker.Unlock();
 526                 mutex_unlock(&fLock);
 527
 528                 entry.Wait(B_CAN_INTERRUPT);
 529                 _Finisher();
 530                 mutex_lock(&fLock);
 531         }
 532 }
 533
 534
 535 struct OperationComparator {
 536         inline bool operator()(const IOOperation* a, const IOOperation* b)
 537         {
 538                 off_t offsetA = a->Offset();
 539                 off_t offsetB = b->Offset();
 540                 return offsetA < offsetB
 541                         || (offsetA == offsetB && a->Length() > b->Length());
 542         }
 543 };
 544
 545
 546 void
 547 IOSchedulerSimple::_SortOperations(IOOperationList& operations,
 548         off_t& lastOffset)
 549 {
 550 // TODO: _Scheduler() could directly add the operations to the array.
 551         // move operations to an array and sort it
 552         int32 count = 0;
 553         while (IOOperation* operation = operations.RemoveHead())
 554                 fOperationArray[count++] = operation;
 555
 556         std::sort(fOperationArray, fOperationArray + count, OperationComparator());
 557
 558         // move the sorted operations to a temporary list we can work with
 559 //dprintf("operations after sorting:\n");
 560         IOOperationList sortedOperations;
 561         for (int32 i = 0; i < count; i++)
 562 //{
 563 //dprintf("  %3ld: %p: offset: %lld, length: %lu\n", i, fOperationArray[i], fOperationArray[i]->Offset(), fOperationArray[i]->Length());
 564                 sortedOperations.Add(fOperationArray[i]);
 565 //}
 566
 567         // Sort the operations so that no two adjacent operations overlap. This
 568         // might result in several elevator runs.
 569         while (!sortedOperations.IsEmpty()) {
 570                 IOOperation* operation = sortedOperations.Head();
 571                 while (operation != NULL) {
 572                         IOOperation* nextOperation = sortedOperations.GetNext(operation);
 573                         if (operation->Offset() >= lastOffset) {
 574                                 sortedOperations.Remove(operation);
 575 //dprintf("  adding operation %p\n", operation);
 576                                 operations.Add(operation);
 577                                 lastOffset = operation->Offset() + operation->Length();
 578                         }
 579
 580                         operation = nextOperation;
 581                 }
 582
 583                 if (!sortedOperations.IsEmpty())
 584                         lastOffset = 0;
 585         }
 586 }
 587
 588
 589 status_t
 590 IOSchedulerSimple::_Scheduler()
 591 {
 592         IORequestOwner marker;
 593         marker.thread = -1;
 594         {
 595                 MutexLocker locker(fLock);
 596                 fActiveRequestOwners.Add(&marker, false);
 597         }
 598
 599         off_t lastOffset = 0;
 600
 601         IORequestOwner* owner = NULL;
 602         off_t quantum = 0;
 603
 604         while (!fTerminating) {
 605 //dprintf("IOSchedulerSimple::_Scheduler(): next iteration: request owner: %p, quantum: %lld\n", owner, quantum);
 606                 MutexLocker locker(fLock);
 607
 608                 IOOperationList operations;
 609                 int32 operationCount = 0;
 610                 bool resourcesAvailable = true;
 611                 off_t iterationBandwidth = fIterationBandwidth;
 612
 613                 if (owner == NULL) {
 614                         owner = fActiveRequestOwners.GetPrevious(&marker);
 615                         quantum = 0;
 616                         fActiveRequestOwners.Remove(&marker);
 617                 }
 618
 619                 if (owner == NULL || quantum < (off_t)fBlockSize) {
 620                         if (!_NextActiveRequestOwner(owner, quantum)) {
 621                                 // we've been asked to terminate
 622                                 return B_OK;
 623                         }
 624                 }
 625
 626                 while (resourcesAvailable && iterationBandwidth >= (off_t)fBlockSize) {
 627 //dprintf("IOSchedulerSimple::_Scheduler(): request owner: %p (thread %ld)\n",
 628 //owner, owner->thread);
 629                         // Prepare operations for the owner.
 630
 631                         // There might still be unfinished ones.
 632                         while (IOOperation* operation = owner->operations.RemoveHead()) {
 633                                 // TODO: We might actually grant the owner more bandwidth than
 634                                 // it deserves.
 635                                 // TODO: We should make sure that after the first read operation
 636                                 // of a partial write, no other write operation to the same
 637                                 // location is scheduled!
 638                                 operations.Add(operation);
 639                                 operationCount++;
 640                                 off_t bandwidth = operation->Length();
 641                                 quantum -= bandwidth;
 642                                 iterationBandwidth -= bandwidth;
 643
 644                                 if (quantum < (off_t)fBlockSize
 645                                         || iterationBandwidth < (off_t)fBlockSize) {
 646                                         break;
 647                                 }
 648                         }
 649
 650                         while (resourcesAvailable && quantum >= (off_t)fBlockSize
 651                                         && iterationBandwidth >= (off_t)fBlockSize) {
 652                                 IORequest* request = owner->requests.Head();
 653                                 if (request == NULL) {
 654                                         resourcesAvailable = false;
 655 if (operationCount == 0)
 656 panic("no more requests for owner %p (thread %" B_PRId32 ")", owner, owner->thread);
 657                                         break;
 658                                 }
 659
 660                                 off_t bandwidth = 0;
 661                                 resourcesAvailable = _PrepareRequestOperations(request,
 662                                         operations, operationCount, quantum, bandwidth);
 663                                 quantum -= bandwidth;
 664                                 iterationBandwidth -= bandwidth;
 665                                 if (request->RemainingBytes() == 0 || request->Status() <= 0) {
 666                                         // If the request has been completed, move it to the
 667                                         // completed list, so we don't pick it up again.
 668                                         owner->requests.Remove(request);
 669                                         owner->completed_requests.Add(request);
 670                                 }
 671                         }
 672
 673                         // Get the next owner.
 674                         if (resourcesAvailable)
 675                                 _NextActiveRequestOwner(owner, quantum);
 676                 }
 677
 678                 // If the current owner doesn't have anymore requests, we have to
 679                 // insert our marker, since the owner will be gone in the next
 680                 // iteration.
 681                 if (owner->requests.IsEmpty()) {
 682                         fActiveRequestOwners.Insert(owner, &marker);
 683                         owner = NULL;
 684                 }
 685
 686                 if (operations.IsEmpty())
 687                         continue;
 688
 689                 fPendingOperations = operationCount;
 690
 691                 locker.Unlock();
 692
 693                 // sort the operations
 694                 _SortOperations(operations, lastOffset);
 695
 696                 // execute the operations
 697 #ifdef TRACE_IO_SCHEDULER
 698                 int32 i = 0;
 699 #endif
 700                 while (IOOperation* operation = operations.RemoveHead()) {
 701                         TRACE("IOSchedulerSimple::_Scheduler(): calling callback for "
 702                                 "operation %ld: %p\n", i++, operation);
 703
 704                         IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_OPERATION_STARTED,
 705                                 this, operation->Parent(), operation);
 706
 707                         fIOCallback(fIOCallbackData, operation);
 708
 709                         _Finisher();
 710                 }
 711
 712                 // wait for all operations to finish
 713                 while (!fTerminating) {
 714                         locker.Lock();
 715
 716                         if (fPendingOperations == 0)
 717                                 break;
 718
 719                         // Before waiting first check whether any finisher work has to be
 720                         // done.
 721                         InterruptsSpinLocker finisherLocker(fFinisherLock);
 722                         if (_FinisherWorkPending()) {
 723                                 finisherLocker.Unlock();
 724                                 locker.Unlock();
 725                                 _Finisher();
 726                                 continue;
 727                         }
 728
 729                         // wait for finished operations
 730                         ConditionVariableEntry entry;
 731                         fFinishedOperationCondition.Add(&entry);
 732
 733                         finisherLocker.Unlock();
 734                         locker.Unlock();
 735
 736                         entry.Wait(B_CAN_INTERRUPT);
 737                         _Finisher();
 738                 }
 739         }
 740
 741         return B_OK;
 742 }
 743
 744
 745 /*static*/ status_t
 746 IOSchedulerSimple::_SchedulerThread(void *_self)
 747 {
 748         IOSchedulerSimple *self = (IOSchedulerSimple *)_self;
 749         return self->_Scheduler();
 750 }
 751
 752
 753 status_t
 754 IOSchedulerSimple::_RequestNotifier()
 755 {
 756         while (true) {
 757                 MutexLocker locker(fLock);
 758
 759                 // get a request
 760                 IORequest* request = fFinishedRequests.RemoveHead();
 761
 762                 if (request == NULL) {
 763                         if (fTerminating)
 764                                 return B_OK;
 765
 766                         ConditionVariableEntry entry;
 767                         fFinishedRequestCondition.Add(&entry);
 768
 769                         locker.Unlock();
 770
 771                         entry.Wait();
 772                         continue;
 773                 }
 774
 775                 locker.Unlock();
 776
 777                 IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_REQUEST_FINISHED,
 778                         this, request);
 779
 780                 // notify the request
 781                 request->NotifyFinished();
 782         }
 783
 784         // never can get here
 785         return B_OK;
 786 }
 787
 788
 789 /*static*/ status_t
 790 IOSchedulerSimple::_RequestNotifierThread(void *_self)
 791 {
 792         IOSchedulerSimple *self = (IOSchedulerSimple*)_self;
 793         return self->_RequestNotifier();
 794 }
 795
 796
 797 IORequestOwner*
 798 IOSchedulerSimple::_GetRequestOwner(team_id team, thread_id thread,
 799         bool allocate)
 800 {
 801         // lookup in table
 802         IORequestOwner* owner = fRequestOwners->Lookup(thread);
 803         if (owner != NULL && !owner->IsActive())
 804                 fUnusedRequestOwners.Remove(owner);
 805         if (owner != NULL || !allocate)
 806                 return owner;
 807
 808         // not in table -- allocate an unused one
 809         RequestOwnerList existingOwners;
 810
 811         while ((owner = fUnusedRequestOwners.RemoveHead()) != NULL) {
 812                 if (owner->thread < 0 || !Thread::IsAlive(owner->thread)) {
 813                         if (owner->thread >= 0)
 814                                 fRequestOwners->RemoveUnchecked(owner);
 815                         owner->team = team;
 816                         owner->thread = thread;
 817                         owner->priority = B_IDLE_PRIORITY;
 818                         fRequestOwners->InsertUnchecked(owner);
 819                         break;
 820                 }
 821
 822                 existingOwners.Add(owner);
 823         }
 824
 825         fUnusedRequestOwners.MoveFrom(&existingOwners);
 826         return owner;
 827 }