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
36void
37IORequestOwner::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
70struct 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
82struct IOSchedulerSimple::RequestOwnerHashTable
83		: BOpenHashTable<RequestOwnerHashDefinition, false> {
84};
85
86
87IOSchedulerSimple::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
109IOSchedulerSimple::~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
143status_t
144IOSchedulerSimple::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
222status_t
223IOSchedulerSimple::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
276void
277IOSchedulerSimple::AbortRequest(IORequest* request, status_t status)
278{
279	// TODO:...
280//B_CANCELED
281}
282
283
284void
285IOSchedulerSimple::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
307void
308IOSchedulerSimple::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. */
324void
325IOSchedulerSimple::_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*/
409bool
410IOSchedulerSimple::_FinisherWorkPending()
411{
412	return !fCompletedOperations.IsEmpty();
413}
414
415
416bool
417IOSchedulerSimple::_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
484off_t
485IOSchedulerSimple::_ComputeRequestOwnerBandwidth(int32 priority) const
486{
487// TODO: Use a priority dependent quantum!
488	return fMinOwnerBandwidth;
489}
490
491
492bool
493IOSchedulerSimple::_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
535struct 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
546void
547IOSchedulerSimple::_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
589status_t
590IOSchedulerSimple::_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;
655if (operationCount == 0)
656panic("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
746IOSchedulerSimple::_SchedulerThread(void *_self)
747{
748	IOSchedulerSimple *self = (IOSchedulerSimple *)_self;
749	return self->_Scheduler();
750}
751
752
753status_t
754IOSchedulerSimple::_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
790IOSchedulerSimple::_RequestNotifierThread(void *_self)
791{
792	IOSchedulerSimple *self = (IOSchedulerSimple*)_self;
793	return self->_RequestNotifier();
794}
795
796
797IORequestOwner*
798IOSchedulerSimple::_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}
828