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