1/*
2 * Copyright 2009, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "Model.h"
8
9#include <new>
10
11#include <stdio.h>
12#include <stdlib.h>
13
14#include <AutoDeleter.h>
15
16#include <thread_defs.h>
17
18
19
20static const char* const kThreadStateNames[] = {
21	"running",
22	"still running",
23	"preempted",
24	"ready",
25	"waiting",
26	"unknown"
27};
28
29
30const char*
31thread_state_name(ThreadState state)
32{
33	return kThreadStateNames[state];
34}
35
36
37const char*
38wait_object_type_name(uint32 type)
39{
40	switch (type) {
41		case THREAD_BLOCK_TYPE_SEMAPHORE:
42			return "semaphore";
43		case THREAD_BLOCK_TYPE_CONDITION_VARIABLE:
44			return "condition";
45		case THREAD_BLOCK_TYPE_MUTEX:
46			return "mutex";
47		case THREAD_BLOCK_TYPE_RW_LOCK:
48			return "rw lock";
49		case THREAD_BLOCK_TYPE_USER:
50			return "user";
51		case THREAD_BLOCK_TYPE_OTHER:
52			return "other";
53		case THREAD_BLOCK_TYPE_SNOOZE:
54			return "snooze";
55		case THREAD_BLOCK_TYPE_SIGNAL:
56			return "signal";
57		default:
58			return "unknown";
59	}
60}
61
62
63// #pragma mark - CPU
64
65
66Model::CPU::CPU()
67	:
68	fIdleTime(0)
69{
70}
71
72
73void
74Model::CPU::SetIdleTime(nanotime_t time)
75{
76	fIdleTime = time;
77}
78
79
80// #pragma mark - IORequest
81
82
83Model::IORequest::IORequest(
84	system_profiler_io_request_scheduled* scheduledEvent,
85	system_profiler_io_request_finished* finishedEvent, size_t operationCount)
86	:
87	scheduledEvent(scheduledEvent),
88	finishedEvent(finishedEvent),
89	operationCount(operationCount)
90{
91}
92
93
94Model::IORequest::~IORequest()
95{
96}
97
98
99/*static*/ Model::IORequest*
100Model::IORequest::Create(system_profiler_io_request_scheduled* scheduledEvent,
101	system_profiler_io_request_finished* finishedEvent, size_t operationCount)
102{
103	void* memory = malloc(
104		sizeof(IORequest) + operationCount * sizeof(IOOperation));
105	if (memory == NULL)
106		return NULL;
107
108	return new(memory) IORequest(scheduledEvent, finishedEvent, operationCount);
109}
110
111
112void
113Model::IORequest::Delete()
114{
115	free(this);
116}
117
118
119// #pragma mark - IOScheduler
120
121
122Model::IOScheduler::IOScheduler(system_profiler_io_scheduler_added* event,
123	int32 index)
124	:
125	fAddedEvent(event),
126	fIndex(index)
127{
128}
129
130
131// #pragma mark - WaitObject
132
133
134Model::WaitObject::WaitObject(const system_profiler_wait_object_info* event)
135	:
136	fEvent(event),
137	fWaits(0),
138	fTotalWaitTime(0)
139{
140}
141
142
143Model::WaitObject::~WaitObject()
144{
145}
146
147
148void
149Model::WaitObject::AddWait(nanotime_t waitTime)
150{
151	fWaits++;
152	fTotalWaitTime += waitTime;
153}
154
155
156// #pragma mark - WaitObjectGroup
157
158
159Model::WaitObjectGroup::WaitObjectGroup(WaitObject* waitObject)
160	:
161	fWaits(-1),
162	fTotalWaitTime(-1)
163{
164	fWaitObjects.AddItem(waitObject);
165}
166
167
168Model::WaitObjectGroup::~WaitObjectGroup()
169{
170}
171
172
173int64
174Model::WaitObjectGroup::Waits()
175{
176	if (fWaits < 0)
177		_ComputeWaits();
178
179	return fWaits;
180}
181
182
183nanotime_t
184Model::WaitObjectGroup::TotalWaitTime()
185{
186	if (fTotalWaitTime < 0)
187		_ComputeWaits();
188
189	return fTotalWaitTime;
190}
191
192
193void
194Model::WaitObjectGroup::_ComputeWaits()
195{
196	fWaits = 0;
197	fTotalWaitTime = 0;
198
199	for (int32 i = fWaitObjects.CountItems(); i-- > 0;) {
200		WaitObject* waitObject = fWaitObjects.ItemAt(i);
201
202		fWaits += waitObject->Waits();
203		fTotalWaitTime += waitObject->TotalWaitTime();
204	}
205}
206
207
208// #pragma mark - ThreadWaitObject
209
210
211Model::ThreadWaitObject::ThreadWaitObject(WaitObject* waitObject)
212	:
213	fWaitObject(waitObject),
214	fWaits(0),
215	fTotalWaitTime(0)
216{
217}
218
219
220Model::ThreadWaitObject::~ThreadWaitObject()
221{
222}
223
224
225void
226Model::ThreadWaitObject::AddWait(nanotime_t waitTime)
227{
228	fWaits++;
229	fTotalWaitTime += waitTime;
230
231	fWaitObject->AddWait(waitTime);
232}
233
234
235// #pragma mark - ThreadWaitObjectGroup
236
237
238Model::ThreadWaitObjectGroup::ThreadWaitObjectGroup(
239	ThreadWaitObject* threadWaitObject)
240{
241	fWaitObjects.Add(threadWaitObject);
242}
243
244
245Model::ThreadWaitObjectGroup::~ThreadWaitObjectGroup()
246{
247}
248
249
250bool
251Model::ThreadWaitObjectGroup::GetThreadWaitObjects(
252	BObjectList<ThreadWaitObject>& objects)
253{
254	ThreadWaitObjectList::Iterator it = fWaitObjects.GetIterator();
255	while (ThreadWaitObject* object = it.Next()) {
256		if (!objects.AddItem(object))
257			return false;
258	}
259
260	return true;
261}
262
263
264// #pragma mark - Team
265
266
267Model::Team::Team(const system_profiler_team_added* event, nanotime_t time)
268	:
269	fCreationEvent(event),
270	fCreationTime(time),
271	fDeletionTime(-1),
272	fThreads(10)
273{
274}
275
276
277Model::Team::~Team()
278{
279}
280
281
282bool
283Model::Team::AddThread(Thread* thread)
284{
285	return fThreads.BinaryInsert(thread, &Thread::CompareByCreationTimeID);
286}
287
288
289// #pragma mark - Thread
290
291
292Model::Thread::Thread(Team* team, const system_profiler_thread_added* event,
293	nanotime_t time)
294	:
295	fEvents(NULL),
296	fEventCount(0),
297	fIORequests(NULL),
298	fIORequestCount(0),
299	fTeam(team),
300	fCreationEvent(event),
301	fCreationTime(time),
302	fDeletionTime(-1),
303	fRuns(0),
304	fTotalRunTime(0),
305	fMinRunTime(-1),
306	fMaxRunTime(-1),
307	fLatencies(0),
308	fTotalLatency(0),
309	fMinLatency(-1),
310	fMaxLatency(-1),
311	fReruns(0),
312	fTotalRerunTime(0),
313	fMinRerunTime(-1),
314	fMaxRerunTime(-1),
315	fWaits(0),
316	fTotalWaitTime(0),
317	fUnspecifiedWaitTime(0),
318	fIOCount(0),
319	fIOTime(0),
320	fPreemptions(0),
321	fIndex(-1),
322	fWaitObjectGroups(20, true)
323{
324}
325
326
327Model::Thread::~Thread()
328{
329	if (fIORequests != NULL) {
330		for (size_t i = 0; i < fIORequestCount; i++)
331			fIORequests[i]->Delete();
332
333		delete[] fIORequests;
334	}
335
336	delete[] fEvents;
337}
338
339
340void
341Model::Thread::SetEvents(system_profiler_event_header** events,
342	size_t eventCount)
343{
344	fEvents = events;
345	fEventCount = eventCount;
346}
347
348
349void
350Model::Thread::SetIORequests(IORequest** requests, size_t requestCount)
351{
352	fIORequests = requests;
353	fIORequestCount = requestCount;
354}
355
356
357size_t
358Model::Thread::ClosestRequestStartIndex(nanotime_t minRequestStartTime) const
359{
360	size_t lower = 0;
361	size_t upper = fIORequestCount;
362	while (lower < upper) {
363		size_t mid = (lower + upper) / 2;
364		IORequest* request = fIORequests[mid];
365
366		if (request->ScheduledTime() < minRequestStartTime)
367			lower = mid + 1;
368		else
369			upper = mid;
370	}
371
372	return lower;
373}
374
375
376Model::ThreadWaitObjectGroup*
377Model::Thread::ThreadWaitObjectGroupFor(uint32 type, addr_t object) const
378{
379	type_and_object key;
380	key.type = type;
381	key.object = object;
382
383	return fWaitObjectGroups.BinarySearchByKey(key,
384		&ThreadWaitObjectGroup::CompareWithTypeObject);
385}
386
387
388void
389Model::Thread::AddRun(nanotime_t runTime)
390{
391	fRuns++;
392	fTotalRunTime += runTime;
393
394	if (fMinRunTime < 0 || runTime < fMinRunTime)
395		fMinRunTime = runTime;
396	if (runTime > fMaxRunTime)
397		fMaxRunTime = runTime;
398}
399
400
401void
402Model::Thread::AddRerun(nanotime_t runTime)
403{
404	fReruns++;
405	fTotalRerunTime += runTime;
406
407	if (fMinRerunTime < 0 || runTime < fMinRerunTime)
408		fMinRerunTime = runTime;
409	if (runTime > fMaxRerunTime)
410		fMaxRerunTime = runTime;
411}
412
413
414void
415Model::Thread::AddLatency(nanotime_t latency)
416{
417	fLatencies++;
418	fTotalLatency += latency;
419
420	if (fMinLatency < 0 || latency < fMinLatency)
421		fMinLatency = latency;
422	if (latency > fMaxLatency)
423		fMaxLatency = latency;
424}
425
426
427void
428Model::Thread::AddPreemption(nanotime_t runTime)
429{
430	fPreemptions++;
431}
432
433
434void
435Model::Thread::AddWait(nanotime_t waitTime)
436{
437	fWaits++;
438	fTotalWaitTime += waitTime;
439}
440
441
442void
443Model::Thread::AddUnspecifiedWait(nanotime_t waitTime)
444{
445	fUnspecifiedWaitTime += waitTime;
446}
447
448
449Model::ThreadWaitObject*
450Model::Thread::AddThreadWaitObject(WaitObject* waitObject,
451	ThreadWaitObjectGroup** _threadWaitObjectGroup)
452{
453	// create a thread wait object
454	ThreadWaitObject* threadWaitObject
455		= new(std::nothrow) ThreadWaitObject(waitObject);
456	if (threadWaitObject == NULL)
457		return NULL;
458
459	// find the thread wait object group
460	ThreadWaitObjectGroup* threadWaitObjectGroup
461		= ThreadWaitObjectGroupFor(waitObject->Type(), waitObject->Object());
462	if (threadWaitObjectGroup == NULL) {
463		// doesn't exist yet -- create
464		threadWaitObjectGroup = new(std::nothrow) ThreadWaitObjectGroup(
465			threadWaitObject);
466		if (threadWaitObjectGroup == NULL) {
467			delete threadWaitObject;
468			return NULL;
469		}
470
471		// add to the list
472		if (!fWaitObjectGroups.BinaryInsert(threadWaitObjectGroup,
473				&ThreadWaitObjectGroup::CompareByTypeObject)) {
474			delete threadWaitObjectGroup;
475			return NULL;
476		}
477	} else {
478		// exists -- just add the object
479		threadWaitObjectGroup->AddWaitObject(threadWaitObject);
480	}
481
482	if (_threadWaitObjectGroup != NULL)
483		*_threadWaitObjectGroup = threadWaitObjectGroup;
484
485	return threadWaitObject;
486}
487
488
489void
490Model::Thread::SetIOs(int64 count, nanotime_t time)
491{
492	fIOCount = count;
493	fIOTime = time;
494}
495
496
497// #pragma mark - SchedulingState
498
499
500Model::SchedulingState::~SchedulingState()
501{
502	Clear();
503}
504
505
506status_t
507Model::SchedulingState::Init()
508{
509	status_t error = fThreadStates.Init();
510	if (error != B_OK)
511		return error;
512
513	return B_OK;
514}
515
516
517status_t
518Model::SchedulingState::Init(const CompactSchedulingState* state)
519{
520	status_t error = Init();
521	if (error != B_OK)
522		return error;
523
524	if (state == NULL)
525		return B_OK;
526
527	fLastEventTime = state->LastEventTime();
528	for (int32 i = 0; const CompactThreadSchedulingState* compactThreadState
529			= state->ThreadStateAt(i); i++) {
530		ThreadSchedulingState* threadState
531			= new(std::nothrow) ThreadSchedulingState(*compactThreadState);
532		if (threadState == NULL)
533			return B_NO_MEMORY;
534
535		fThreadStates.Insert(threadState);
536	}
537
538	return B_OK;
539}
540
541
542void
543Model::SchedulingState::Clear()
544{
545	ThreadSchedulingState* state = fThreadStates.Clear(true);
546	while (state != NULL) {
547		ThreadSchedulingState* next = state->next;
548		DeleteThread(state);
549		state = next;
550	}
551
552	fLastEventTime = -1;
553}
554
555void
556Model::SchedulingState::DeleteThread(ThreadSchedulingState* thread)
557{
558	delete thread;
559}
560
561
562// #pragma mark - CompactSchedulingState
563
564
565/*static*/ Model::CompactSchedulingState*
566Model::CompactSchedulingState::Create(const SchedulingState& state,
567	off_t eventOffset)
568{
569	nanotime_t lastEventTime = state.LastEventTime();
570
571	// count the active threads
572	int32 threadCount = 0;
573	for (ThreadSchedulingStateTable::Iterator it
574				= state.ThreadStates().GetIterator();
575			ThreadSchedulingState* threadState = it.Next();) {
576		Thread* thread = threadState->thread;
577		if (thread->CreationTime() <= lastEventTime
578			&& (thread->DeletionTime() == -1
579				|| thread->DeletionTime() >= lastEventTime)) {
580			threadCount++;
581		}
582	}
583
584	CompactSchedulingState* compactState = (CompactSchedulingState*)malloc(
585		sizeof(CompactSchedulingState)
586			+ threadCount * sizeof(CompactThreadSchedulingState));
587	if (compactState == NULL)
588		return NULL;
589
590	// copy the state info
591	compactState->fEventOffset = eventOffset;
592	compactState->fThreadCount = threadCount;
593	compactState->fLastEventTime = lastEventTime;
594
595	int32 threadIndex = 0;
596	for (ThreadSchedulingStateTable::Iterator it
597				= state.ThreadStates().GetIterator();
598			ThreadSchedulingState* threadState = it.Next();) {
599		Thread* thread = threadState->thread;
600		if (thread->CreationTime() <= lastEventTime
601			&& (thread->DeletionTime() == -1
602				|| thread->DeletionTime() >= lastEventTime)) {
603			compactState->fThreadStates[threadIndex++] = *threadState;
604		}
605	}
606
607	return compactState;
608}
609
610
611void
612Model::CompactSchedulingState::Delete()
613{
614	free(this);
615}
616
617
618// #pragma mark - Model
619
620
621Model::Model(const char* dataSourceName, void* eventData, size_t eventDataSize,
622	system_profiler_event_header** events, size_t eventCount)
623	:
624	fDataSourceName(dataSourceName),
625	fEventData(eventData),
626	fEvents(events),
627	fEventDataSize(eventDataSize),
628	fEventCount(eventCount),
629	fCPUCount(1),
630	fBaseTime(0),
631	fLastEventTime(0),
632	fIdleTime(0),
633	fCPUs(20, true),
634	fTeams(20, true),
635	fThreads(20, true),
636	fWaitObjectGroups(20, true),
637	fIOSchedulers(10, true),
638	fSchedulingStates(100)
639{
640}
641
642
643Model::~Model()
644{
645	for (int32 i = 0; CompactSchedulingState* state
646		= fSchedulingStates.ItemAt(i); i++) {
647		state->Delete();
648	}
649
650	delete[] fEvents;
651
652	free(fEventData);
653
654	for (int32 i = 0; void* data = fAssociatedData.ItemAt(i); i++)
655		free(data);
656}
657
658
659size_t
660Model::ClosestEventIndex(nanotime_t eventTime) const
661{
662	// The events themselves are unmodified and use an absolute time.
663	eventTime += fBaseTime;
664
665	// Binary search the event. Since not all events have a timestamp, we have
666	// to do a bit of iteration, too.
667	size_t lower = 0;
668	size_t upper = CountEvents();
669	while (lower < upper) {
670		size_t mid = (lower + upper) / 2;
671		while (mid < upper) {
672			system_profiler_event_header* header = fEvents[mid];
673			switch (header->event) {
674				case B_SYSTEM_PROFILER_THREAD_SCHEDULED:
675				case B_SYSTEM_PROFILER_THREAD_ENQUEUED_IN_RUN_QUEUE:
676				case B_SYSTEM_PROFILER_THREAD_REMOVED_FROM_RUN_QUEUE:
677					break;
678				default:
679					mid++;
680					continue;
681			}
682
683			break;
684		}
685
686		if (mid == upper) {
687			lower = mid;
688			break;
689		}
690
691		system_profiler_thread_scheduling_event* event
692			= (system_profiler_thread_scheduling_event*)(fEvents[mid] + 1);
693		if (event->time < eventTime)
694			lower = mid + 1;
695		else
696			upper = mid;
697	}
698
699	return lower;
700}
701
702
703bool
704Model::AddAssociatedData(void* data)
705{
706	return fAssociatedData.AddItem(data);
707}
708
709
710void
711Model::RemoveAssociatedData(void* data)
712{
713	fAssociatedData.RemoveItem(data);
714}
715
716
717void
718Model::LoadingFinished()
719{
720	// set the thread indices
721	for (int32 i = 0; Thread* thread = fThreads.ItemAt(i); i++)
722		thread->SetIndex(i);
723
724	// compute the total idle time
725	fIdleTime = 0;
726	for (int32 i = 0; CPU* cpu = CPUAt(i); i++)
727		fIdleTime += cpu->IdleTime();
728}
729
730
731void
732Model::SetBaseTime(nanotime_t time)
733{
734	fBaseTime = time;
735}
736
737
738void
739Model::SetLastEventTime(nanotime_t time)
740{
741	fLastEventTime = time;
742}
743
744
745bool
746Model::SetCPUCount(int32 count)
747{
748	fCPUCount = count;
749
750	fCPUs.MakeEmpty();
751
752	for (int32 i = 0; i < fCPUCount; i++) {
753		CPU* cpu = new(std::nothrow) CPU;
754		if (cpu == NULL || !fCPUs.AddItem(cpu)) {
755			delete cpu;
756			return false;
757		}
758	}
759
760	return true;
761}
762
763
764int32
765Model::CountTeams() const
766{
767		return fTeams.CountItems();
768}
769
770
771Model::Team*
772Model::TeamAt(int32 index) const
773{
774	return fTeams.ItemAt(index);
775}
776
777
778Model::Team*
779Model::TeamByID(team_id id) const
780{
781	return fTeams.BinarySearchByKey(id, &Team::CompareWithID);
782}
783
784
785Model::Team*
786Model::AddTeam(const system_profiler_team_added* event, nanotime_t time)
787{
788	Team* team = TeamByID(event->team);
789	if (team != NULL) {
790		fprintf(stderr, "Duplicate team: %" B_PRId32 "\n", event->team);
791		// TODO: User feedback!
792		return team;
793	}
794
795	team = new(std::nothrow) Team(event, time);
796	if (team == NULL)
797		return NULL;
798
799	if (!fTeams.BinaryInsert(team, &Team::CompareByID)) {
800		delete team;
801		return NULL;
802	}
803
804	return team;
805}
806
807
808int32
809Model::CountThreads() const
810{
811	return fThreads.CountItems();
812}
813
814
815Model::Thread*
816Model::ThreadAt(int32 index) const
817{
818	return fThreads.ItemAt(index);
819}
820
821
822Model::Thread*
823Model::ThreadByID(thread_id id) const
824{
825	return fThreads.BinarySearchByKey(id, &Thread::CompareWithID);
826}
827
828
829Model::Thread*
830Model::AddThread(const system_profiler_thread_added* event, nanotime_t time)
831{
832	// check whether we do already know the thread
833	Thread* thread = ThreadByID(event->thread);
834	if (thread != NULL) {
835		fprintf(stderr, "Duplicate thread: %" B_PRId32 "\n", event->thread);
836		// TODO: User feedback!
837		return thread;
838	}
839
840	// get its team
841	Team* team = TeamByID(event->team);
842	if (team == NULL) {
843		fprintf(stderr, "No team for thread: %" B_PRId32 "\n", event->thread);
844		return NULL;
845	}
846
847	// create the thread and add it
848	thread = new(std::nothrow) Thread(team, event, time);
849	if (thread == NULL)
850		return NULL;
851	ObjectDeleter<Thread> threadDeleter(thread);
852
853	if (!fThreads.BinaryInsert(thread, &Thread::CompareByID))
854		return NULL;
855
856	if (!team->AddThread(thread)) {
857		fThreads.RemoveItem(thread);
858		return NULL;
859	}
860
861	threadDeleter.Detach();
862	return thread;
863}
864
865
866Model::WaitObject*
867Model::AddWaitObject(const system_profiler_wait_object_info* event,
868	WaitObjectGroup** _waitObjectGroup)
869{
870	// create a wait object
871	WaitObject* waitObject = new(std::nothrow) WaitObject(event);
872	if (waitObject == NULL)
873		return NULL;
874
875	// find the wait object group
876	WaitObjectGroup* waitObjectGroup
877		= WaitObjectGroupFor(waitObject->Type(), waitObject->Object());
878	if (waitObjectGroup == NULL) {
879		// doesn't exist yet -- create
880		waitObjectGroup = new(std::nothrow) WaitObjectGroup(waitObject);
881		if (waitObjectGroup == NULL) {
882			delete waitObject;
883			return NULL;
884		}
885
886		// add to the list
887		if (!fWaitObjectGroups.BinaryInsert(waitObjectGroup,
888				&WaitObjectGroup::CompareByTypeObject)) {
889			delete waitObjectGroup;
890			return NULL;
891		}
892	} else {
893		// exists -- just add the object
894		waitObjectGroup->AddWaitObject(waitObject);
895	}
896
897	if (_waitObjectGroup != NULL)
898		*_waitObjectGroup = waitObjectGroup;
899
900	return waitObject;
901}
902
903
904int32
905Model::CountWaitObjectGroups() const
906{
907	return fWaitObjectGroups.CountItems();
908}
909
910
911Model::WaitObjectGroup*
912Model::WaitObjectGroupAt(int32 index) const
913{
914	return fWaitObjectGroups.ItemAt(index);
915}
916
917
918Model::WaitObjectGroup*
919Model::WaitObjectGroupFor(uint32 type, addr_t object) const
920{
921	type_and_object key;
922	key.type = type;
923	key.object = object;
924
925	return fWaitObjectGroups.BinarySearchByKey(key,
926		&WaitObjectGroup::CompareWithTypeObject);
927}
928
929
930Model::ThreadWaitObject*
931Model::AddThreadWaitObject(thread_id threadID, WaitObject* waitObject,
932	ThreadWaitObjectGroup** _threadWaitObjectGroup)
933{
934	Thread* thread = ThreadByID(threadID);
935	if (thread == NULL)
936		return NULL;
937
938	return thread->AddThreadWaitObject(waitObject, _threadWaitObjectGroup);
939}
940
941
942Model::ThreadWaitObjectGroup*
943Model::ThreadWaitObjectGroupFor(thread_id threadID, uint32 type, addr_t object) const
944{
945	Thread* thread = ThreadByID(threadID);
946	if (thread == NULL)
947		return NULL;
948
949	return thread->ThreadWaitObjectGroupFor(type, object);
950}
951
952
953int32
954Model::CountIOSchedulers() const
955{
956	return fIOSchedulers.CountItems();
957}
958
959
960Model::IOScheduler*
961Model::IOSchedulerAt(int32 index) const
962{
963	return fIOSchedulers.ItemAt(index);
964}
965
966
967Model::IOScheduler*
968Model::IOSchedulerByID(int32 id) const
969{
970	for (int32 i = 0; IOScheduler* scheduler = fIOSchedulers.ItemAt(i); i++) {
971		if (scheduler->ID() == id)
972			return scheduler;
973	}
974
975	return NULL;
976}
977
978
979Model::IOScheduler*
980Model::AddIOScheduler(system_profiler_io_scheduler_added* event)
981{
982	IOScheduler* scheduler = new(std::nothrow) IOScheduler(event,
983		fIOSchedulers.CountItems());
984	if (scheduler == NULL || !fIOSchedulers.AddItem(scheduler)) {
985		delete scheduler;
986		return NULL;
987	}
988
989	return scheduler;
990}
991
992
993bool
994Model::AddSchedulingStateSnapshot(const SchedulingState& state,
995	off_t eventOffset)
996{
997	CompactSchedulingState* compactState = CompactSchedulingState::Create(state,
998		eventOffset);
999	if (compactState == NULL)
1000		return false;
1001
1002	if (!fSchedulingStates.AddItem(compactState)) {
1003		compactState->Delete();
1004		return false;
1005	}
1006
1007	return true;
1008}
1009
1010
1011const Model::CompactSchedulingState*
1012Model::ClosestSchedulingState(nanotime_t eventTime) const
1013{
1014	int32 index = fSchedulingStates.BinarySearchIndexByKey(eventTime,
1015		&_CompareEventTimeSchedulingState);
1016	if (index >= 0)
1017		return fSchedulingStates.ItemAt(index);
1018
1019	// no exact match
1020	index = -index - 1;
1021	return index > 0 ? fSchedulingStates.ItemAt(index - 1) : NULL;
1022}
1023
1024
1025/*static*/ int
1026Model::_CompareEventTimeSchedulingState(const nanotime_t* time,
1027	const CompactSchedulingState* state)
1028{
1029	if (*time < state->LastEventTime())
1030		return -1;
1031	return *time == state->LastEventTime() ? 0 : 1;
1032}
1033
1034