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, transferredBytes);
295
296	fCompletedOperations.Add(operation);
297	fFinishedOperationCondition.NotifyAll();
298}
299
300
301void
302IOSchedulerSimple::Dump() const
303{
304	kprintf("IOSchedulerSimple at %p\n", this);
305	kprintf("  DMA resource:   %p\n", fDMAResource);
306
307	kprintf("  active request owners:");
308	for (RequestOwnerList::ConstIterator it
309				= fActiveRequestOwners.GetIterator();
310			IORequestOwner* owner = it.Next();) {
311		kprintf(" %p", owner);
312	}
313	kprintf("\n");
314}
315
316
317/*!	Must not be called with the fLock held. */
318void
319IOSchedulerSimple::_Finisher()
320{
321	while (true) {
322		InterruptsSpinLocker locker(fFinisherLock);
323		IOOperation* operation = fCompletedOperations.RemoveHead();
324		if (operation == NULL)
325			return;
326
327		locker.Unlock();
328
329		TRACE("IOSchedulerSimple::_Finisher(): operation: %p\n", operation);
330
331		bool operationFinished = operation->Finish();
332
333		IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_OPERATION_FINISHED,
334			this, operation->Parent(), operation);
335			// Notify for every time the operation is passed to the I/O hook,
336			// not only when it is fully finished.
337
338		if (!operationFinished) {
339			TRACE("  operation: %p not finished yet\n", operation);
340			MutexLocker _(fLock);
341			operation->Parent()->Owner()->operations.Add(operation);
342			fPendingOperations--;
343			continue;
344		}
345
346		// notify request and remove operation
347		IORequest* request = operation->Parent();
348
349		request->OperationFinished(operation);
350
351		// recycle the operation
352		MutexLocker _(fLock);
353		if (fDMAResource != NULL)
354			fDMAResource->RecycleBuffer(operation->Buffer());
355
356		fPendingOperations--;
357		fUnusedOperations.Add(operation);
358
359		// If the request is done, we need to perform its notifications.
360		if (request->IsFinished()) {
361			if (request->Status() == B_OK && request->RemainingBytes() > 0) {
362				// The request has been processed OK so far, but it isn't really
363				// finished yet.
364				request->SetUnfinished();
365			} else {
366				// Remove the request from the request owner.
367				IORequestOwner* owner = request->Owner();
368				owner->requests.MoveFrom(&owner->completed_requests);
369				owner->requests.Remove(request);
370				request->SetOwner(NULL);
371
372				if (!owner->IsActive()) {
373					fActiveRequestOwners.Remove(owner);
374					fUnusedRequestOwners.Add(owner);
375				}
376
377				if (request->HasCallbacks()) {
378					// The request has callbacks that may take some time to
379					// perform, so we hand it over to the request notifier.
380					fFinishedRequests.Add(request);
381					fFinishedRequestCondition.NotifyAll();
382				} else {
383					// No callbacks -- finish the request right now.
384					IOSchedulerRoster::Default()->Notify(
385						IO_SCHEDULER_REQUEST_FINISHED, this, request);
386					request->NotifyFinished();
387				}
388			}
389		}
390	}
391}
392
393
394/*!	Called with \c fFinisherLock held.
395*/
396bool
397IOSchedulerSimple::_FinisherWorkPending()
398{
399	return !fCompletedOperations.IsEmpty();
400}
401
402
403bool
404IOSchedulerSimple::_PrepareRequestOperations(IORequest* request,
405	IOOperationList& operations, int32& operationsPrepared, off_t quantum,
406	off_t& usedBandwidth)
407{
408//dprintf("IOSchedulerSimple::_PrepareRequestOperations(%p)\n", request);
409	usedBandwidth = 0;
410
411	if (fDMAResource != NULL) {
412		while (quantum >= (off_t)fBlockSize && request->RemainingBytes() > 0) {
413			IOOperation* operation = fUnusedOperations.RemoveHead();
414			if (operation == NULL)
415				return false;
416
417			status_t status = fDMAResource->TranslateNext(request, operation,
418				quantum);
419			if (status != B_OK) {
420				operation->SetParent(NULL);
421				fUnusedOperations.Add(operation);
422
423				// B_BUSY means some resource (DMABuffers or
424				// DMABounceBuffers) was temporarily unavailable. That's OK,
425				// we'll retry later.
426				if (status == B_BUSY)
427					return false;
428
429				AbortRequest(request, status);
430				return true;
431			}
432//dprintf("  prepared operation %p\n", operation);
433
434			off_t bandwidth = operation->Length();
435			quantum -= bandwidth;
436			usedBandwidth += bandwidth;
437
438			operations.Add(operation);
439			operationsPrepared++;
440		}
441	} else {
442		// TODO: If the device has block size restrictions, we might need to use
443		// a bounce buffer.
444		IOOperation* operation = fUnusedOperations.RemoveHead();
445		if (operation == NULL)
446			return false;
447
448		status_t status = operation->Prepare(request);
449		if (status != B_OK) {
450			operation->SetParent(NULL);
451			fUnusedOperations.Add(operation);
452			AbortRequest(request, status);
453			return true;
454		}
455
456		operation->SetOriginalRange(request->Offset(), request->Length());
457		request->Advance(request->Length());
458
459		off_t bandwidth = operation->Length();
460		quantum -= bandwidth;
461		usedBandwidth += bandwidth;
462
463		operations.Add(operation);
464		operationsPrepared++;
465	}
466
467	return true;
468}
469
470
471off_t
472IOSchedulerSimple::_ComputeRequestOwnerBandwidth(int32 priority) const
473{
474// TODO: Use a priority dependent quantum!
475	return fMinOwnerBandwidth;
476}
477
478
479bool
480IOSchedulerSimple::_NextActiveRequestOwner(IORequestOwner*& owner,
481	off_t& quantum)
482{
483	while (true) {
484		if (fTerminating)
485			return false;
486
487		if (owner != NULL)
488			owner = fActiveRequestOwners.GetNext(owner);
489		if (owner == NULL)
490			owner = fActiveRequestOwners.Head();
491
492		if (owner != NULL) {
493			quantum = _ComputeRequestOwnerBandwidth(owner->priority);
494			return true;
495		}
496
497		// Wait for new requests owners. First check whether any finisher work
498		// has to be done.
499		InterruptsSpinLocker finisherLocker(fFinisherLock);
500		if (_FinisherWorkPending()) {
501			finisherLocker.Unlock();
502			mutex_unlock(&fLock);
503			_Finisher();
504			mutex_lock(&fLock);
505			continue;
506		}
507
508		// Wait for new requests.
509		ConditionVariableEntry entry;
510		fNewRequestCondition.Add(&entry);
511
512		finisherLocker.Unlock();
513		mutex_unlock(&fLock);
514
515		entry.Wait(B_CAN_INTERRUPT);
516		_Finisher();
517		mutex_lock(&fLock);
518	}
519}
520
521
522struct OperationComparator {
523	inline bool operator()(const IOOperation* a, const IOOperation* b)
524	{
525		off_t offsetA = a->Offset();
526		off_t offsetB = b->Offset();
527		return offsetA < offsetB
528			|| (offsetA == offsetB && a->Length() > b->Length());
529	}
530};
531
532
533void
534IOSchedulerSimple::_SortOperations(IOOperationList& operations,
535	off_t& lastOffset)
536{
537// TODO: _Scheduler() could directly add the operations to the array.
538	// move operations to an array and sort it
539	int32 count = 0;
540	while (IOOperation* operation = operations.RemoveHead())
541		fOperationArray[count++] = operation;
542
543	std::sort(fOperationArray, fOperationArray + count, OperationComparator());
544
545	// move the sorted operations to a temporary list we can work with
546//dprintf("operations after sorting:\n");
547	IOOperationList sortedOperations;
548	for (int32 i = 0; i < count; i++)
549//{
550//dprintf("  %3ld: %p: offset: %lld, length: %lu\n", i, fOperationArray[i], fOperationArray[i]->Offset(), fOperationArray[i]->Length());
551		sortedOperations.Add(fOperationArray[i]);
552//}
553
554	// Sort the operations so that no two adjacent operations overlap. This
555	// might result in several elevator runs.
556	while (!sortedOperations.IsEmpty()) {
557		IOOperation* operation = sortedOperations.Head();
558		while (operation != NULL) {
559			IOOperation* nextOperation = sortedOperations.GetNext(operation);
560			if (operation->Offset() >= lastOffset) {
561				sortedOperations.Remove(operation);
562//dprintf("  adding operation %p\n", operation);
563				operations.Add(operation);
564				lastOffset = operation->Offset() + operation->Length();
565			}
566
567			operation = nextOperation;
568		}
569
570		if (!sortedOperations.IsEmpty())
571			lastOffset = 0;
572	}
573}
574
575
576status_t
577IOSchedulerSimple::_Scheduler()
578{
579	IORequestOwner marker;
580	marker.thread = -1;
581	{
582		MutexLocker locker(fLock);
583		fActiveRequestOwners.Add(&marker, false);
584	}
585
586	off_t lastOffset = 0;
587
588	IORequestOwner* owner = NULL;
589	off_t quantum = 0;
590
591	while (!fTerminating) {
592//dprintf("IOSchedulerSimple::_Scheduler(): next iteration: request owner: %p, quantum: %lld\n", owner, quantum);
593		MutexLocker locker(fLock);
594
595		IOOperationList operations;
596		int32 operationCount = 0;
597		bool resourcesAvailable = true;
598		off_t iterationBandwidth = fIterationBandwidth;
599
600		if (owner == NULL) {
601			owner = fActiveRequestOwners.GetPrevious(&marker);
602			quantum = 0;
603			fActiveRequestOwners.Remove(&marker);
604		}
605
606		if (owner == NULL || quantum < (off_t)fBlockSize) {
607			if (!_NextActiveRequestOwner(owner, quantum)) {
608				// we've been asked to terminate
609				return B_OK;
610			}
611		}
612
613		while (resourcesAvailable && iterationBandwidth >= (off_t)fBlockSize) {
614//dprintf("IOSchedulerSimple::_Scheduler(): request owner: %p (thread %ld)\n",
615//owner, owner->thread);
616			// Prepare operations for the owner.
617
618			// There might still be unfinished ones.
619			while (IOOperation* operation = owner->operations.RemoveHead()) {
620				// TODO: We might actually grant the owner more bandwidth than
621				// it deserves.
622				// TODO: We should make sure that after the first read operation
623				// of a partial write, no other write operation to the same
624				// location is scheduled!
625				operations.Add(operation);
626				operationCount++;
627				off_t bandwidth = operation->Length();
628				quantum -= bandwidth;
629				iterationBandwidth -= bandwidth;
630
631				if (quantum < (off_t)fBlockSize
632					|| iterationBandwidth < (off_t)fBlockSize) {
633					break;
634				}
635			}
636
637			while (resourcesAvailable && quantum >= (off_t)fBlockSize
638					&& iterationBandwidth >= (off_t)fBlockSize) {
639				IORequest* request = owner->requests.Head();
640				if (request == NULL) {
641					resourcesAvailable = false;
642if (operationCount == 0)
643panic("no more requests for owner %p (thread %" B_PRId32 ")", owner, owner->thread);
644					break;
645				}
646
647				off_t bandwidth = 0;
648				resourcesAvailable = _PrepareRequestOperations(request,
649					operations, operationCount, quantum, bandwidth);
650				quantum -= bandwidth;
651				iterationBandwidth -= bandwidth;
652				if (request->RemainingBytes() == 0 || request->Status() <= 0) {
653					// If the request has been completed, move it to the
654					// completed list, so we don't pick it up again.
655					owner->requests.Remove(request);
656					owner->completed_requests.Add(request);
657				}
658			}
659
660			// Get the next owner.
661			if (resourcesAvailable)
662				_NextActiveRequestOwner(owner, quantum);
663		}
664
665		// If the current owner doesn't have anymore requests, we have to
666		// insert our marker, since the owner will be gone in the next
667		// iteration.
668		if (owner->requests.IsEmpty()) {
669			fActiveRequestOwners.InsertBefore(owner, &marker);
670			owner = NULL;
671		}
672
673		if (operations.IsEmpty())
674			continue;
675
676		fPendingOperations = operationCount;
677
678		locker.Unlock();
679
680		// sort the operations
681		_SortOperations(operations, lastOffset);
682
683		// execute the operations
684#ifdef TRACE_IO_SCHEDULER
685		int32 i = 0;
686#endif
687		while (IOOperation* operation = operations.RemoveHead()) {
688			TRACE("IOSchedulerSimple::_Scheduler(): calling callback for "
689				"operation %ld: %p\n", i++, operation);
690
691			IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_OPERATION_STARTED,
692				this, operation->Parent(), operation);
693
694			fIOCallback(fIOCallbackData, operation);
695
696			_Finisher();
697		}
698
699		// wait for all operations to finish
700		while (!fTerminating) {
701			locker.Lock();
702
703			if (fPendingOperations == 0)
704				break;
705
706			// Before waiting first check whether any finisher work has to be
707			// done.
708			InterruptsSpinLocker finisherLocker(fFinisherLock);
709			if (_FinisherWorkPending()) {
710				finisherLocker.Unlock();
711				locker.Unlock();
712				_Finisher();
713				continue;
714			}
715
716			// wait for finished operations
717			ConditionVariableEntry entry;
718			fFinishedOperationCondition.Add(&entry);
719
720			finisherLocker.Unlock();
721			locker.Unlock();
722
723			entry.Wait(B_CAN_INTERRUPT);
724			_Finisher();
725		}
726	}
727
728	return B_OK;
729}
730
731
732/*static*/ status_t
733IOSchedulerSimple::_SchedulerThread(void *_self)
734{
735	IOSchedulerSimple *self = (IOSchedulerSimple *)_self;
736	return self->_Scheduler();
737}
738
739
740status_t
741IOSchedulerSimple::_RequestNotifier()
742{
743	while (true) {
744		MutexLocker locker(fLock);
745
746		// get a request
747		IORequest* request = fFinishedRequests.RemoveHead();
748
749		if (request == NULL) {
750			if (fTerminating)
751				return B_OK;
752
753			ConditionVariableEntry entry;
754			fFinishedRequestCondition.Add(&entry);
755
756			locker.Unlock();
757
758			entry.Wait();
759			continue;
760		}
761
762		locker.Unlock();
763
764		IOSchedulerRoster::Default()->Notify(IO_SCHEDULER_REQUEST_FINISHED,
765			this, request);
766
767		// notify the request
768		request->NotifyFinished();
769	}
770
771	// never can get here
772	return B_OK;
773}
774
775
776/*static*/ status_t
777IOSchedulerSimple::_RequestNotifierThread(void *_self)
778{
779	IOSchedulerSimple *self = (IOSchedulerSimple*)_self;
780	return self->_RequestNotifier();
781}
782
783
784IORequestOwner*
785IOSchedulerSimple::_GetRequestOwner(team_id team, thread_id thread,
786	bool allocate)
787{
788	// lookup in table
789	IORequestOwner* owner = fRequestOwners->Lookup(thread);
790	if (owner != NULL && !owner->IsActive())
791		fUnusedRequestOwners.Remove(owner);
792	if (owner != NULL || !allocate)
793		return owner;
794
795	// not in table -- allocate an unused one
796	RequestOwnerList existingOwners;
797
798	while ((owner = fUnusedRequestOwners.RemoveHead()) != NULL) {
799		if (owner->thread < 0 || !Thread::IsAlive(owner->thread)) {
800			if (owner->thread >= 0)
801				fRequestOwners->RemoveUnchecked(owner);
802			owner->team = team;
803			owner->thread = thread;
804			owner->priority = B_IDLE_PRIORITY;
805			fRequestOwners->InsertUnchecked(owner);
806			break;
807		}
808
809		existingOwners.Add(owner);
810	}
811
812	fUnusedRequestOwners.MoveFrom(&existingOwners);
813	return owner;
814}
815