1/*
2 * Copyright 2009, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "ModelLoader.h"
8
9#include <stdio.h>
10#include <string.h>
11
12#include <algorithm>
13#include <new>
14
15#include <AutoDeleter.h>
16#include <AutoLocker.h>
17#include <DebugEventStream.h>
18
19#include <system_profiler_defs.h>
20#include <thread_defs.h>
21
22#include "DataSource.h"
23#include "MessageCodes.h"
24#include "Model.h"
25
26
27// add a scheduling state snapshot every x events
28static const uint32 kSchedulingSnapshotInterval = 1024;
29
30static const uint32 kMaxCPUCount = 1024;
31
32
33struct SimpleWaitObjectInfo : system_profiler_wait_object_info {
34	SimpleWaitObjectInfo(uint32 type)
35	{
36		this->type = type;
37		object = 0;
38		referenced_object = 0;
39		name[0] = '\0';
40	}
41};
42
43
44static const SimpleWaitObjectInfo kSnoozeWaitObjectInfo(
45	THREAD_BLOCK_TYPE_SNOOZE);
46static const SimpleWaitObjectInfo kSignalWaitObjectInfo(
47	THREAD_BLOCK_TYPE_SIGNAL);
48
49
50// #pragma mark - CPUInfo
51
52
53struct ModelLoader::CPUInfo {
54	nanotime_t	idleTime;
55
56	CPUInfo()
57		:
58		idleTime(0)
59	{
60	}
61};
62
63
64// #pragma mark - IOOperation
65
66
67struct ModelLoader::IOOperation : DoublyLinkedListLinkImpl<IOOperation> {
68	io_operation_started*	startedEvent;
69	io_operation_finished*	finishedEvent;
70
71	IOOperation(io_operation_started* startedEvent)
72		:
73		startedEvent(startedEvent),
74		finishedEvent(NULL)
75	{
76	}
77};
78
79
80// #pragma mark - IORequest
81
82
83struct ModelLoader::IORequest : DoublyLinkedListLinkImpl<IORequest> {
84	io_request_scheduled*	scheduledEvent;
85	io_request_finished*	finishedEvent;
86	IOOperationList			operations;
87	size_t					operationCount;
88	IORequest*				hashNext;
89
90	IORequest(io_request_scheduled* scheduledEvent)
91		:
92		scheduledEvent(scheduledEvent),
93		finishedEvent(NULL),
94		operationCount(0)
95	{
96	}
97
98	~IORequest()
99	{
100		while (IOOperation* operation = operations.RemoveHead())
101			delete operation;
102	}
103
104	void AddOperation(IOOperation* operation)
105	{
106		operations.Add(operation);
107		operationCount++;
108	}
109
110	IOOperation* FindOperation(void* address) const
111	{
112		for (IOOperationList::ConstReverseIterator it
113				= operations.GetReverseIterator();
114			IOOperation* operation = it.Next();) {
115			if (operation->startedEvent->operation == address)
116				return operation;
117		}
118
119		return NULL;
120	}
121
122	Model::IORequest* CreateModelRequest() const
123	{
124		size_t operationCount = operations.Count();
125
126		Model::IORequest* modelRequest = Model::IORequest::Create(
127			scheduledEvent, finishedEvent, operationCount);
128		if (modelRequest == NULL)
129			return NULL;
130
131		size_t index = 0;
132		for (IOOperationList::ConstIterator it = operations.GetIterator();
133				IOOperation* operation = it.Next();) {
134			Model::IOOperation& modelOperation
135				= modelRequest->operations[index++];
136			modelOperation.startedEvent = operation->startedEvent;
137			modelOperation.finishedEvent = operation->finishedEvent;
138		}
139
140		return modelRequest;
141	}
142};
143
144
145// #pragma mark - IORequestHashDefinition
146
147
148struct ModelLoader::IORequestHashDefinition {
149	typedef void*		KeyType;
150	typedef	IORequest	ValueType;
151
152	size_t HashKey(KeyType key) const
153		{ return (size_t)key; }
154
155	size_t Hash(const IORequest* value) const
156		{ return HashKey(value->scheduledEvent->request); }
157
158	bool Compare(KeyType key, const IORequest* value) const
159		{ return key == value->scheduledEvent->request; }
160
161	IORequest*& GetLink(IORequest* value) const
162		{ return value->hashNext; }
163};
164
165
166// #pragma mark - ExtendedThreadSchedulingState
167
168
169struct ModelLoader::ExtendedThreadSchedulingState
170		: Model::ThreadSchedulingState {
171
172	ExtendedThreadSchedulingState(Model::Thread* thread)
173		:
174		Model::ThreadSchedulingState(thread),
175		fEvents(NULL),
176		fEventIndex(0),
177		fEventCount(0)
178	{
179	}
180
181	~ExtendedThreadSchedulingState()
182	{
183		delete[] fEvents;
184
185		while (IORequest* request = fIORequests.RemoveHead())
186			delete request;
187		while (IORequest* request = fPendingIORequests.RemoveHead())
188			delete request;
189	}
190
191	system_profiler_event_header** Events() const
192	{
193		return fEvents;
194	}
195
196	size_t CountEvents() const
197	{
198		return fEventCount;
199	}
200
201	system_profiler_event_header** DetachEvents()
202	{
203		system_profiler_event_header** events = fEvents;
204		fEvents = NULL;
205		return events;
206	}
207
208	void IncrementEventCount()
209	{
210		fEventCount++;
211	}
212
213	void AddEvent(system_profiler_event_header* event)
214	{
215		fEvents[fEventIndex++] = event;
216	}
217
218	bool AllocateEventArray()
219	{
220		if (fEventCount == 0)
221			return true;
222
223		fEvents = new(std::nothrow) system_profiler_event_header*[fEventCount];
224		if (fEvents == NULL)
225			return false;
226
227		return true;
228	}
229
230	void AddIORequest(IORequest* request)
231	{
232		fPendingIORequests.Add(request);
233	}
234
235	void IORequestFinished(IORequest* request)
236	{
237		fPendingIORequests.Remove(request);
238		fIORequests.Add(request);
239	}
240
241	bool PrepareThreadIORequests(Model::IORequest**& _requests,
242		size_t& _requestCount)
243	{
244		fIORequests.MoveFrom(&fPendingIORequests);
245		size_t requestCount = fIORequests.Count();
246
247		if (requestCount == 0) {
248			_requests = NULL;
249			_requestCount = 0;
250			return true;
251		}
252
253		Model::IORequest** requests
254			= new(std::nothrow) Model::IORequest*[requestCount];
255		if (requests == NULL)
256			return false;
257
258		size_t index = 0;
259		while (IORequest* request = fIORequests.RemoveHead()) {
260			ObjectDeleter<IORequest> requestDeleter(request);
261
262			Model::IORequest* modelRequest = request->CreateModelRequest();
263			if (modelRequest == NULL) {
264				for (size_t i = 0; i < index; i++)
265					requests[i]->Delete();
266				delete[] requests;
267				return false;
268			}
269
270			requests[index++] = modelRequest;
271		}
272
273		_requests = requests;
274		_requestCount = requestCount;
275		return true;
276	}
277
278private:
279	system_profiler_event_header**	fEvents;
280	size_t							fEventIndex;
281	size_t							fEventCount;
282	IORequestList					fIORequests;
283	IORequestList					fPendingIORequests;
284};
285
286
287// #pragma mark - ExtendedSchedulingState
288
289
290struct ModelLoader::ExtendedSchedulingState : Model::SchedulingState {
291	inline ExtendedThreadSchedulingState* LookupThread(thread_id threadID) const
292	{
293		Model::ThreadSchedulingState* thread
294			= Model::SchedulingState::LookupThread(threadID);
295		return thread != NULL
296			? static_cast<ExtendedThreadSchedulingState*>(thread) : NULL;
297	}
298
299
300protected:
301	virtual void DeleteThread(Model::ThreadSchedulingState* thread)
302	{
303		delete static_cast<ExtendedThreadSchedulingState*>(thread);
304	}
305};
306
307
308// #pragma mark - ModelLoader
309
310
311inline void
312ModelLoader::_UpdateLastEventTime(nanotime_t time)
313{
314	if (fBaseTime < 0) {
315		fBaseTime = time;
316		fModel->SetBaseTime(time);
317	}
318
319	fState->SetLastEventTime(time - fBaseTime);
320}
321
322
323ModelLoader::ModelLoader(DataSource* dataSource,
324	const BMessenger& target, void* targetCookie)
325	:
326	AbstractModelLoader(target, targetCookie),
327	fModel(NULL),
328	fDataSource(dataSource),
329	fCPUInfos(NULL),
330	fState(NULL),
331	fIORequests(NULL)
332{
333}
334
335
336ModelLoader::~ModelLoader()
337{
338	delete[] fCPUInfos;
339	delete fDataSource;
340	delete fModel;
341	delete fState;
342	delete fIORequests;
343}
344
345
346Model*
347ModelLoader::DetachModel()
348{
349	AutoLocker<BLocker> locker(fLock);
350
351	if (fModel == NULL || fLoading)
352		return NULL;
353
354	Model* model = fModel;
355	fModel = NULL;
356
357	return model;
358}
359
360
361status_t
362ModelLoader::PrepareForLoading()
363{
364	if (fModel != NULL || fDataSource == NULL)
365		return B_BAD_VALUE;
366
367	// create and init the state
368	fState = new(std::nothrow) ExtendedSchedulingState;
369	if (fState == NULL)
370		return B_NO_MEMORY;
371
372	status_t error = fState->Init();
373	if (error != B_OK)
374		return error;
375
376	// create CPU info array
377	fCPUInfos = new(std::nothrow) CPUInfo[kMaxCPUCount];
378	if (fCPUInfos == NULL)
379		return B_NO_MEMORY;
380
381	// create IORequest hash table
382	fIORequests = new(std::nothrow) IORequestTable;
383	if (fIORequests == NULL || fIORequests->Init() != B_OK)
384		return B_NO_MEMORY;
385
386	return B_OK;
387}
388
389
390status_t
391ModelLoader::Load()
392{
393	try {
394		return _Load();
395	} catch(...) {
396		return B_ERROR;
397	}
398}
399
400
401void
402ModelLoader::FinishLoading(bool success)
403{
404	delete fState;
405	fState = NULL;
406
407	if (!success) {
408		delete fModel;
409		fModel = NULL;
410	}
411
412	delete[] fCPUInfos;
413	fCPUInfos = NULL;
414
415	delete fIORequests;
416	fIORequests = NULL;
417}
418
419
420status_t
421ModelLoader::_Load()
422{
423	// read the complete data into memory
424	void* eventData;
425	size_t eventDataSize;
426	status_t error = _ReadDebugEvents(&eventData, &eventDataSize);
427	if (error != B_OK)
428		return error;
429	MemoryDeleter eventDataDeleter(eventData);
430
431	// create a debug event array
432	system_profiler_event_header** events;
433	size_t eventCount;
434	error = _CreateDebugEventArray(eventData, eventDataSize, events,
435		eventCount);
436	if (error != B_OK)
437		return error;
438	ArrayDeleter<system_profiler_event_header*> eventsDeleter(events);
439
440	// get the data source name
441	BString dataSourceName;
442	fDataSource->GetName(dataSourceName);
443
444	// create a model
445	fModel = new(std::nothrow) Model(dataSourceName.String(), eventData,
446		eventDataSize, events, eventCount);
447	if (fModel == NULL)
448		return B_NO_MEMORY;
449	eventDataDeleter.Detach();
450	eventsDeleter.Detach();
451
452	// create a debug input stream
453	BDebugEventInputStream input;
454	error = input.SetTo(eventData, eventDataSize, false);
455	if (error != B_OK)
456		return error;
457
458	// add the snooze and signal wait objects to the model
459	if (fModel->AddWaitObject(&kSnoozeWaitObjectInfo, NULL) == NULL
460		|| fModel->AddWaitObject(&kSignalWaitObjectInfo, NULL) == NULL) {
461		return B_NO_MEMORY;
462	}
463
464	// process the events
465	fMaxCPUIndex = 0;
466	fState->Clear();
467	fBaseTime = -1;
468	uint64 count = 0;
469
470	while (true) {
471		// get next event
472		uint32 event;
473		uint32 cpu;
474		const void* buffer;
475		off_t offset;
476		ssize_t bufferSize = input.ReadNextEvent(&event, &cpu, &buffer,
477			&offset);
478		if (bufferSize < 0)
479			return bufferSize;
480		if (buffer == NULL)
481			break;
482
483		// process the event
484		status_t error = _ProcessEvent(event, cpu, buffer, bufferSize);
485		if (error != B_OK)
486			return error;
487
488		if (cpu > fMaxCPUIndex) {
489			if (cpu + 1 > kMaxCPUCount)
490				return B_BAD_DATA;
491			fMaxCPUIndex = cpu;
492		}
493
494		// periodically check whether we're supposed to abort
495		if (++count % 32 == 0) {
496			AutoLocker<BLocker> locker(fLock);
497			if (fAborted)
498				return B_ERROR;
499		}
500
501		// periodically add scheduling snapshots
502		if (count % kSchedulingSnapshotInterval == 0)
503			fModel->AddSchedulingStateSnapshot(*fState, offset);
504	}
505
506	if (!fModel->SetCPUCount(fMaxCPUIndex + 1))
507		return B_NO_MEMORY;
508
509	for (uint32 i = 0; i <= fMaxCPUIndex; i++)
510		fModel->CPUAt(i)->SetIdleTime(fCPUInfos[i].idleTime);
511
512	fModel->SetLastEventTime(fState->LastEventTime());
513
514	if (!_SetThreadEvents() || !_SetThreadIORequests())
515		return B_NO_MEMORY;
516
517	fModel->LoadingFinished();
518
519	return B_OK;
520}
521
522
523status_t
524ModelLoader::_ReadDebugEvents(void** _eventData, size_t* _size)
525{
526	// get a BDataIO from the data source
527	BDataIO* io;
528	status_t error = fDataSource->CreateDataIO(&io);
529	if (error != B_OK)
530		return error;
531	ObjectDeleter<BDataIO> dataIOtDeleter(io);
532
533	// First we need to find out how large a buffer to allocate.
534	size_t size;
535
536	if (BPositionIO* positionIO = dynamic_cast<BPositionIO*>(io)) {
537		// it's a BPositionIO -- this makes things easier, since we know how
538		// many bytes to read
539		off_t currentPos = positionIO->Position();
540		if (currentPos < 0)
541			return currentPos;
542
543		off_t fileSize;
544		error = positionIO->GetSize(&fileSize);
545		if (error != B_OK)
546			return error;
547
548		size = fileSize - currentPos;
549	} else {
550		// no BPositionIO -- we need to determine the total size by iteratively
551		// reading the whole data one time
552
553		// allocate a dummy buffer for reading
554		const size_t kBufferSize = 1024 * 1024;
555		void* buffer = malloc(kBufferSize);
556		if (buffer == NULL)
557			return B_NO_MEMORY;
558		MemoryDeleter bufferDeleter(buffer);
559
560		size = 0;
561		while (true) {
562			ssize_t bytesRead = io->Read(buffer, kBufferSize);
563			if (bytesRead < 0)
564				return bytesRead;
565			if (bytesRead == 0)
566				break;
567
568			size += bytesRead;
569		}
570
571		// we've got the size -- recreate the BDataIO
572		dataIOtDeleter.Delete();
573		error = fDataSource->CreateDataIO(&io);
574		if (error != B_OK)
575			return error;
576		dataIOtDeleter.SetTo(io);
577	}
578
579	// allocate the data buffer
580	void* data = malloc(size);
581	if (data == NULL)
582		return B_NO_MEMORY;
583	MemoryDeleter dataDeleter(data);
584
585	// read the data
586	ssize_t bytesRead = io->Read(data, size);
587	if (bytesRead < 0)
588		return bytesRead;
589	if ((size_t)bytesRead != size)
590		return B_FILE_ERROR;
591
592	dataDeleter.Detach();
593	*_eventData = data;
594	*_size = size;
595	return B_OK;
596}
597
598
599status_t
600ModelLoader::_CreateDebugEventArray(void* eventData, size_t eventDataSize,
601	system_profiler_event_header**& _events, size_t& _eventCount)
602{
603	// count the events
604	BDebugEventInputStream input;
605	status_t error = input.SetTo(eventData, eventDataSize, false);
606	if (error != B_OK)
607		return error;
608
609	size_t eventCount = 0;
610	while (true) {
611		// get next event
612		uint32 event;
613		uint32 cpu;
614		const void* buffer;
615		ssize_t bufferSize = input.ReadNextEvent(&event, &cpu, &buffer, NULL);
616		if (bufferSize < 0)
617			return bufferSize;
618		if (buffer == NULL)
619			break;
620
621		eventCount++;
622	}
623
624	// create the array
625	system_profiler_event_header** events = new(std::nothrow)
626		system_profiler_event_header*[eventCount];
627	if (events == NULL)
628		return B_NO_MEMORY;
629
630	// populate the array
631	error = input.SetTo(eventData, eventDataSize, false);
632	if (error != B_OK) {
633		delete[] events;
634		return error;
635	}
636
637	size_t eventIndex = 0;
638	while (true) {
639		// get next event
640		uint32 event;
641		uint32 cpu;
642		const void* buffer;
643		off_t offset;
644		input.ReadNextEvent(&event, &cpu, &buffer, &offset);
645		if (buffer == NULL)
646			break;
647
648		events[eventIndex++]
649			= (system_profiler_event_header*)((uint8*)eventData + offset);
650	}
651
652	_events = events;
653	_eventCount = eventCount;
654	return B_OK;
655}
656
657
658status_t
659ModelLoader::_ProcessEvent(uint32 event, uint32 cpu, const void* buffer,
660	size_t size)
661{
662	switch (event) {
663		case B_SYSTEM_PROFILER_TEAM_ADDED:
664			_HandleTeamAdded((system_profiler_team_added*)buffer);
665			break;
666
667		case B_SYSTEM_PROFILER_TEAM_REMOVED:
668			_HandleTeamRemoved((system_profiler_team_removed*)buffer);
669			break;
670
671		case B_SYSTEM_PROFILER_TEAM_EXEC:
672			_HandleTeamExec((system_profiler_team_exec*)buffer);
673			break;
674
675		case B_SYSTEM_PROFILER_THREAD_ADDED:
676			_HandleThreadAdded((system_profiler_thread_added*)buffer);
677			break;
678
679		case B_SYSTEM_PROFILER_THREAD_REMOVED:
680			_HandleThreadRemoved((system_profiler_thread_removed*)buffer);
681			break;
682
683		case B_SYSTEM_PROFILER_THREAD_SCHEDULED:
684			_HandleThreadScheduled(cpu,
685				(system_profiler_thread_scheduled*)buffer);
686			break;
687
688		case B_SYSTEM_PROFILER_THREAD_ENQUEUED_IN_RUN_QUEUE:
689			_HandleThreadEnqueuedInRunQueue(
690				(thread_enqueued_in_run_queue*)buffer);
691			break;
692
693		case B_SYSTEM_PROFILER_THREAD_REMOVED_FROM_RUN_QUEUE:
694			_HandleThreadRemovedFromRunQueue(cpu,
695				(thread_removed_from_run_queue*)buffer);
696			break;
697
698		case B_SYSTEM_PROFILER_WAIT_OBJECT_INFO:
699			_HandleWaitObjectInfo((system_profiler_wait_object_info*)buffer);
700			break;
701
702		case B_SYSTEM_PROFILER_IO_SCHEDULER_ADDED:
703			_HandleIOSchedulerAdded(
704				(system_profiler_io_scheduler_added*)buffer);
705			break;
706
707		case B_SYSTEM_PROFILER_IO_SCHEDULER_REMOVED:
708			// not so interesting
709			break;
710
711		case B_SYSTEM_PROFILER_IO_REQUEST_SCHEDULED:
712			_HandleIORequestScheduled((io_request_scheduled*)buffer);
713			break;
714		case B_SYSTEM_PROFILER_IO_REQUEST_FINISHED:
715			_HandleIORequestFinished((io_request_finished*)buffer);
716			break;
717		case B_SYSTEM_PROFILER_IO_OPERATION_STARTED:
718			_HandleIOOperationStarted((io_operation_started*)buffer);
719			break;
720		case B_SYSTEM_PROFILER_IO_OPERATION_FINISHED:
721			_HandleIOOperationFinished((io_operation_finished*)buffer);
722			break;
723
724		default:
725			printf("unsupported event type %" B_PRIu32 ", size: %" B_PRIuSIZE
726				"\n", event, size);
727			return B_BAD_DATA;
728	}
729
730	return B_OK;
731}
732
733
734bool
735ModelLoader::_SetThreadEvents()
736{
737	// allocate the threads' events arrays
738	for (int32 i = 0; Model::Thread* thread = fModel->ThreadAt(i); i++) {
739		ExtendedThreadSchedulingState* state
740			= fState->LookupThread(thread->ID());
741		if (!state->AllocateEventArray())
742			return false;
743	}
744
745	// fill the threads' event arrays
746	system_profiler_event_header** events = fModel->Events();
747	size_t eventCount = fModel->CountEvents();
748	for (size_t i = 0; i < eventCount; i++) {
749		system_profiler_event_header* header = events[i];
750		void* buffer = header + 1;
751
752		switch (header->event) {
753			case B_SYSTEM_PROFILER_THREAD_ADDED:
754			{
755				system_profiler_thread_added* event
756					= (system_profiler_thread_added*)buffer;
757				fState->LookupThread(event->thread)->AddEvent(header);
758				break;
759			}
760
761			case B_SYSTEM_PROFILER_THREAD_REMOVED:
762			{
763				system_profiler_thread_removed* event
764					= (system_profiler_thread_removed*)buffer;
765				fState->LookupThread(event->thread)->AddEvent(header);
766				break;
767			}
768
769			case B_SYSTEM_PROFILER_THREAD_SCHEDULED:
770			{
771				system_profiler_thread_scheduled* event
772					= (system_profiler_thread_scheduled*)buffer;
773				fState->LookupThread(event->thread)->AddEvent(header);
774
775				if (event->thread != event->previous_thread) {
776					fState->LookupThread(event->previous_thread)
777						->AddEvent(header);
778				}
779				break;
780			}
781
782			case B_SYSTEM_PROFILER_THREAD_ENQUEUED_IN_RUN_QUEUE:
783			{
784				thread_enqueued_in_run_queue* event
785					= (thread_enqueued_in_run_queue*)buffer;
786				fState->LookupThread(event->thread)->AddEvent(header);
787				break;
788			}
789
790			case B_SYSTEM_PROFILER_THREAD_REMOVED_FROM_RUN_QUEUE:
791			{
792				thread_removed_from_run_queue* event
793					= (thread_removed_from_run_queue*)buffer;
794				fState->LookupThread(event->thread)->AddEvent(header);
795				break;
796			}
797
798			default:
799				break;
800		}
801	}
802
803	// transfer the events arrays from the scheduling states to the thread
804	// objects
805	for (int32 i = 0; Model::Thread* thread = fModel->ThreadAt(i); i++) {
806		ExtendedThreadSchedulingState* state
807			= fState->LookupThread(thread->ID());
808		thread->SetEvents(state->Events(), state->CountEvents());
809		state->DetachEvents();
810	}
811
812	return true;
813}
814
815
816bool
817ModelLoader::_SetThreadIORequests()
818{
819	for (int32 i = 0; Model::Thread* thread = fModel->ThreadAt(i); i++) {
820		ExtendedThreadSchedulingState* state
821			= fState->LookupThread(thread->ID());
822		Model::IORequest** requests;
823		size_t requestCount;
824		if (!state->PrepareThreadIORequests(requests, requestCount))
825			return false;
826		if (requestCount > 0)
827			_SetThreadIORequests(thread, requests, requestCount);
828	}
829
830	return true;
831}
832
833
834void
835ModelLoader::_SetThreadIORequests(Model::Thread* thread,
836	Model::IORequest** requests, size_t requestCount)
837{
838	// compute some totals
839	int64 ioCount = 0;
840	nanotime_t ioTime = 0;
841
842	// sort requests by scheduler and start time
843	std::sort(requests, requests + requestCount,
844		Model::IORequest::SchedulerTimeLess);
845
846	nanotime_t endTime = fBaseTime + fModel->LastEventTime();
847
848	// compute the summed up I/O times
849	nanotime_t ioStart = requests[0]->scheduledEvent->time;
850	nanotime_t previousEnd = requests[0]->finishedEvent != NULL
851		? requests[0]->finishedEvent->time : endTime;
852	int32 scheduler = requests[0]->scheduledEvent->scheduler;
853
854	for (size_t i = 1; i < requestCount; i++) {
855		system_profiler_io_request_scheduled* scheduledEvent
856			= requests[i]->scheduledEvent;
857		if (scheduledEvent->scheduler != scheduler
858			|| scheduledEvent->time >= previousEnd) {
859			ioCount++;
860			ioTime += previousEnd - ioStart;
861			ioStart = scheduledEvent->time;
862		}
863
864		previousEnd = requests[i]->finishedEvent != NULL
865			? requests[i]->finishedEvent->time : endTime;
866	}
867
868	ioCount++;
869	ioTime += previousEnd - ioStart;
870
871	// sort requests by start time
872	std::sort(requests, requests + requestCount, Model::IORequest::TimeLess);
873
874	// set the computed values
875	thread->SetIORequests(requests, requestCount);
876	thread->SetIOs(ioCount, ioTime);
877}
878
879
880void
881ModelLoader::_HandleTeamAdded(system_profiler_team_added* event)
882{
883	if (fModel->AddTeam(event, fState->LastEventTime()) == NULL)
884		throw std::bad_alloc();
885}
886
887
888void
889ModelLoader::_HandleTeamRemoved(system_profiler_team_removed* event)
890{
891	if (Model::Team* team = fModel->TeamByID(event->team))
892		team->SetDeletionTime(fState->LastEventTime());
893	else {
894		printf("Warning: Removed event for unknown team: %" B_PRId32 "\n",
895			event->team);
896	}
897}
898
899
900void
901ModelLoader::_HandleTeamExec(system_profiler_team_exec* event)
902{
903	// TODO:...
904}
905
906
907void
908ModelLoader::_HandleThreadAdded(system_profiler_thread_added* event)
909{
910	_AddThread(event)->IncrementEventCount();
911}
912
913
914void
915ModelLoader::_HandleThreadRemoved(system_profiler_thread_removed* event)
916{
917	ExtendedThreadSchedulingState* thread = fState->LookupThread(event->thread);
918	if (thread == NULL) {
919		printf("Warning: Removed event for unknown thread: %" B_PRId32 "\n",
920			event->thread);
921		thread = _AddUnknownThread(event->thread);
922	}
923
924	thread->thread->SetDeletionTime(fState->LastEventTime());
925	thread->IncrementEventCount();
926}
927
928
929void
930ModelLoader::_HandleThreadScheduled(uint32 cpu,
931	system_profiler_thread_scheduled* event)
932{
933	_UpdateLastEventTime(event->time);
934
935	ExtendedThreadSchedulingState* thread = fState->LookupThread(event->thread);
936	if (thread == NULL) {
937		printf("Warning: Schedule event for unknown thread: %" B_PRId32 "\n",
938			event->thread);
939		thread = _AddUnknownThread(event->thread);
940		return;
941	}
942
943	nanotime_t diffTime = fState->LastEventTime() - thread->lastTime;
944
945	if (thread->state == READY) {
946		// thread scheduled after having been woken up
947		thread->thread->AddLatency(diffTime);
948	} else if (thread->state == PREEMPTED) {
949		// thread scheduled after having been preempted before
950		thread->thread->AddRerun(diffTime);
951	}
952
953	if (thread->state == STILL_RUNNING) {
954		// Thread was running and continues to run.
955		thread->state = RUNNING;
956	}
957
958	if (thread->state != RUNNING) {
959		thread->lastTime = fState->LastEventTime();
960		thread->state = RUNNING;
961	}
962
963	thread->IncrementEventCount();
964
965	// unscheduled thread
966
967	if (event->thread == event->previous_thread)
968		return;
969
970	thread = fState->LookupThread(event->previous_thread);
971	if (thread == NULL) {
972		printf("Warning: Schedule event for unknown previous thread: %" B_PRId32
973			"\n", event->previous_thread);
974		thread = _AddUnknownThread(event->previous_thread);
975	}
976
977	diffTime = fState->LastEventTime() - thread->lastTime;
978
979	if (thread->state == STILL_RUNNING) {
980		// thread preempted
981		thread->thread->AddPreemption(diffTime);
982		thread->thread->AddRun(diffTime);
983		if (thread->priority == 0)
984			_AddIdleTime(cpu, diffTime);
985
986		thread->lastTime = fState->LastEventTime();
987		thread->state = PREEMPTED;
988	} else if (thread->state == RUNNING) {
989		// thread starts waiting (it hadn't been added to the run
990		// queue before being unscheduled)
991		thread->thread->AddRun(diffTime);
992		if (thread->priority == 0)
993			_AddIdleTime(cpu, diffTime);
994
995		if (event->previous_thread_state == B_THREAD_WAITING) {
996			addr_t waitObject = event->previous_thread_wait_object;
997			switch (event->previous_thread_wait_object_type) {
998				case THREAD_BLOCK_TYPE_SNOOZE:
999				case THREAD_BLOCK_TYPE_SIGNAL:
1000					waitObject = 0;
1001					break;
1002				case THREAD_BLOCK_TYPE_SEMAPHORE:
1003				case THREAD_BLOCK_TYPE_CONDITION_VARIABLE:
1004				case THREAD_BLOCK_TYPE_MUTEX:
1005				case THREAD_BLOCK_TYPE_RW_LOCK:
1006				case THREAD_BLOCK_TYPE_OTHER:
1007				case THREAD_BLOCK_TYPE_OTHER_OBJECT:
1008				default:
1009					break;
1010			}
1011
1012			_AddThreadWaitObject(thread,
1013				event->previous_thread_wait_object_type, waitObject);
1014		}
1015
1016		thread->lastTime = fState->LastEventTime();
1017		thread->state = WAITING;
1018	} else if (thread->state == UNKNOWN) {
1019		uint32 threadState = event->previous_thread_state;
1020		if (threadState == B_THREAD_WAITING
1021			|| threadState == B_THREAD_SUSPENDED) {
1022			thread->lastTime = fState->LastEventTime();
1023			thread->state = WAITING;
1024		} else if (threadState == B_THREAD_READY) {
1025			thread->lastTime = fState->LastEventTime();
1026			thread->state = PREEMPTED;
1027		}
1028	}
1029
1030	thread->IncrementEventCount();
1031}
1032
1033
1034void
1035ModelLoader::_HandleThreadEnqueuedInRunQueue(
1036	thread_enqueued_in_run_queue* event)
1037{
1038	_UpdateLastEventTime(event->time);
1039
1040	ExtendedThreadSchedulingState* thread = fState->LookupThread(event->thread);
1041	if (thread == NULL) {
1042		printf("Warning: Enqueued in run queue event for unknown thread: %"
1043			B_PRId32 "\n", event->thread);
1044		thread = _AddUnknownThread(event->thread);
1045	}
1046
1047	if (thread->state == RUNNING || thread->state == STILL_RUNNING) {
1048		// Thread was running and is reentered into the run queue. This
1049		// is done by the scheduler, if the thread remains ready.
1050		thread->state = STILL_RUNNING;
1051	} else {
1052		// Thread was waiting and is ready now.
1053		nanotime_t diffTime = fState->LastEventTime() - thread->lastTime;
1054		if (thread->waitObject != NULL) {
1055			thread->waitObject->AddWait(diffTime);
1056			thread->waitObject = NULL;
1057			thread->thread->AddWait(diffTime);
1058		} else if (thread->state != UNKNOWN)
1059			thread->thread->AddUnspecifiedWait(diffTime);
1060
1061		thread->lastTime = fState->LastEventTime();
1062		thread->state = READY;
1063	}
1064
1065	thread->priority = event->priority;
1066
1067	thread->IncrementEventCount();
1068}
1069
1070
1071void
1072ModelLoader::_HandleThreadRemovedFromRunQueue(uint32 cpu,
1073	thread_removed_from_run_queue* event)
1074{
1075	_UpdateLastEventTime(event->time);
1076
1077	ExtendedThreadSchedulingState* thread = fState->LookupThread(event->thread);
1078	if (thread == NULL) {
1079		printf("Warning: Removed from run queue event for unknown thread: "
1080			"%" B_PRId32 "\n", event->thread);
1081		thread = _AddUnknownThread(event->thread);
1082	}
1083
1084	// This really only happens when the thread priority is changed
1085	// while the thread is ready.
1086
1087	nanotime_t diffTime = fState->LastEventTime() - thread->lastTime;
1088	if (thread->state == RUNNING) {
1089		// This should never happen.
1090		thread->thread->AddRun(diffTime);
1091		if (thread->priority == 0)
1092			_AddIdleTime(cpu, diffTime);
1093	} else if (thread->state == READY || thread->state == PREEMPTED) {
1094		// Not really correct, but the case is rare and we keep it
1095		// simple.
1096		thread->thread->AddUnspecifiedWait(diffTime);
1097	}
1098
1099	thread->lastTime = fState->LastEventTime();
1100	thread->state = WAITING;
1101
1102	thread->IncrementEventCount();
1103}
1104
1105
1106void
1107ModelLoader::_HandleWaitObjectInfo(system_profiler_wait_object_info* event)
1108{
1109	if (fModel->AddWaitObject(event, NULL) == NULL)
1110		throw std::bad_alloc();
1111}
1112
1113
1114void
1115ModelLoader::_HandleIOSchedulerAdded(system_profiler_io_scheduler_added* event)
1116{
1117	Model::IOScheduler* scheduler = fModel->IOSchedulerByID(event->scheduler);
1118	if (scheduler != NULL) {
1119		printf("Warning: Duplicate added event for I/O scheduler %" B_PRId32
1120			"\n", event->scheduler);
1121		return;
1122	}
1123
1124	if (fModel->AddIOScheduler(event) == NULL)
1125		throw std::bad_alloc();
1126}
1127
1128
1129void
1130ModelLoader::_HandleIORequestScheduled(io_request_scheduled* event)
1131{
1132	IORequest* request = fIORequests->Lookup(event->request);
1133	if (request != NULL) {
1134		printf("Warning: Duplicate schedule event for I/O request %p\n",
1135			event->request);
1136		return;
1137	}
1138
1139	ExtendedThreadSchedulingState* thread = fState->LookupThread(event->thread);
1140	if (thread == NULL) {
1141		printf("Warning: I/O request for unknown thread %" B_PRId32 "\n",
1142			event->thread);
1143		thread = _AddUnknownThread(event->thread);
1144	}
1145
1146	if (fModel->IOSchedulerByID(event->scheduler) == NULL) {
1147		printf("Warning: I/O requests for unknown scheduler %" B_PRId32 "\n",
1148			event->scheduler);
1149		// TODO: Add state for unknown scheduler, as we do for threads.
1150		return;
1151	}
1152
1153	request = new(std::nothrow) IORequest(event);
1154	if (request == NULL)
1155		throw std::bad_alloc();
1156
1157	fIORequests->Insert(request);
1158	thread->AddIORequest(request);
1159}
1160
1161
1162void
1163ModelLoader::_HandleIORequestFinished(io_request_finished* event)
1164{
1165	IORequest* request = fIORequests->Lookup(event->request);
1166	if (request == NULL)
1167		return;
1168
1169	request->finishedEvent = event;
1170
1171	fIORequests->Remove(request);
1172	fState->LookupThread(request->scheduledEvent->thread)
1173		->IORequestFinished(request);
1174}
1175
1176
1177void
1178ModelLoader::_HandleIOOperationStarted(io_operation_started* event)
1179{
1180	IORequest* request = fIORequests->Lookup(event->request);
1181	if (request == NULL) {
1182		printf("Warning: I/O request for operation %p not found\n",
1183			event->operation);
1184		return;
1185	}
1186
1187	IOOperation* operation = new(std::nothrow) IOOperation(event);
1188	if (operation == NULL)
1189		throw std::bad_alloc();
1190
1191	request->AddOperation(operation);
1192}
1193
1194
1195void
1196ModelLoader::_HandleIOOperationFinished(io_operation_finished* event)
1197{
1198	IORequest* request = fIORequests->Lookup(event->request);
1199	if (request == NULL) {
1200		printf("Warning: I/O request for operation %p not found\n",
1201			event->operation);
1202		return;
1203	}
1204
1205	IOOperation* operation = request->FindOperation(event->operation);
1206	if (operation == NULL) {
1207		printf("Warning: operation %p not found\n", event->operation);
1208		return;
1209	}
1210
1211	operation->finishedEvent = event;
1212}
1213
1214
1215ModelLoader::ExtendedThreadSchedulingState*
1216ModelLoader::_AddThread(system_profiler_thread_added* event)
1217{
1218	// do we know the thread already?
1219	ExtendedThreadSchedulingState* info = fState->LookupThread(event->thread);
1220	if (info != NULL) {
1221		printf("Warning: Duplicate thread added event for thread %" B_PRId32
1222			"\n", event->thread);
1223		return info;
1224	}
1225
1226	// add the thread to the model
1227	Model::Thread* thread = fModel->AddThread(event, fState->LastEventTime());
1228	if (thread == NULL)
1229		throw std::bad_alloc();
1230
1231	// create and add a ThreadSchedulingState
1232	info = new(std::nothrow) ExtendedThreadSchedulingState(thread);
1233	if (info == NULL)
1234		throw std::bad_alloc();
1235
1236	// TODO: The priority is missing from the system_profiler_thread_added
1237	// struct. For now guess at least whether this is an idle thread.
1238	if (strncmp(event->name, "idle thread", strlen("idle thread")) == 0)
1239		info->priority = 0;
1240	else
1241		info->priority = B_NORMAL_PRIORITY;
1242
1243	fState->InsertThread(info);
1244
1245	return info;
1246}
1247
1248
1249ModelLoader::ExtendedThreadSchedulingState*
1250ModelLoader::_AddUnknownThread(thread_id threadID)
1251{
1252	// create a dummy "add thread" event
1253	system_profiler_thread_added* event = (system_profiler_thread_added*)
1254		malloc(sizeof(system_profiler_thread_added));
1255	if (event == NULL)
1256		throw std::bad_alloc();
1257
1258	if (!fModel->AddAssociatedData(event)) {
1259		free(event);
1260		throw std::bad_alloc();
1261	}
1262
1263	try {
1264		event->team = _AddUnknownTeam()->ID();
1265		event->thread = threadID;
1266		snprintf(event->name, sizeof(event->name), "unknown thread %" B_PRId32,
1267			threadID);
1268
1269		// add the thread to the model
1270		ExtendedThreadSchedulingState* state = _AddThread(event);
1271		return state;
1272	} catch (...) {
1273		throw;
1274	}
1275}
1276
1277Model::Team*
1278ModelLoader::_AddUnknownTeam()
1279{
1280	team_id teamID = 0;
1281	Model::Team* team = fModel->TeamByID(teamID);
1282	if (team != NULL)
1283		return team;
1284
1285	// create a dummy "add team" event
1286	static const char* const kUnknownThreadsTeamName = "unknown threads";
1287	size_t nameLength = strlen(kUnknownThreadsTeamName);
1288
1289	system_profiler_team_added* event = (system_profiler_team_added*)
1290		malloc(sizeof(system_profiler_team_added) + nameLength);
1291	if (event == NULL)
1292		throw std::bad_alloc();
1293
1294	event->team = teamID;
1295	event->args_offset = nameLength;
1296	strlcpy(event->name, kUnknownThreadsTeamName, nameLength + 1);
1297
1298	// add the team to the model
1299	team = fModel->AddTeam(event, fState->LastEventTime());
1300	if (team == NULL)
1301		throw std::bad_alloc();
1302
1303	return team;
1304}
1305
1306
1307void
1308ModelLoader::_AddThreadWaitObject(ExtendedThreadSchedulingState* thread,
1309	uint32 type, addr_t object)
1310{
1311	Model::WaitObjectGroup* waitObjectGroup
1312		= fModel->WaitObjectGroupFor(type, object);
1313	if (waitObjectGroup == NULL) {
1314		// The algorithm should prevent this case.
1315		printf("ModelLoader::_AddThreadWaitObject(): Unknown wait object: type:"
1316			" %" B_PRIu32 ", " "object: %#" B_PRIxADDR "\n", type, object);
1317		return;
1318	}
1319
1320	Model::WaitObject* waitObject = waitObjectGroup->MostRecentWaitObject();
1321
1322	Model::ThreadWaitObjectGroup* threadWaitObjectGroup
1323		= fModel->ThreadWaitObjectGroupFor(thread->ID(), type, object);
1324
1325	if (threadWaitObjectGroup == NULL
1326		|| threadWaitObjectGroup->MostRecentWaitObject() != waitObject) {
1327		Model::ThreadWaitObject* threadWaitObject
1328			= fModel->AddThreadWaitObject(thread->ID(), waitObject,
1329				&threadWaitObjectGroup);
1330		if (threadWaitObject == NULL)
1331			throw std::bad_alloc();
1332	}
1333
1334	thread->waitObject = threadWaitObjectGroup->MostRecentThreadWaitObject();
1335}
1336
1337
1338void
1339ModelLoader::_AddIdleTime(uint32 cpu, nanotime_t time)
1340{
1341	fCPUInfos[cpu].idleTime += time;
1342}
1343