1/*
2 * Copyright 2008-2009, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6#include <errno.h>
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11#include <algorithm>
12
13#include <OS.h>
14
15#include <AutoDeleter.h>
16
17#include <scheduler_defs.h>
18#include <syscalls.h>
19#include <thread_defs.h>
20
21#include "time_stats.h"
22
23
24struct wait_object_group {
25	scheduling_analysis_thread_wait_object**	objects;
26	int32										count;
27	bigtime_t									wait_time;
28	int64										waits;
29};
30
31
32struct ThreadRunTimeComparator {
33	inline bool operator()(const scheduling_analysis_thread* a,
34		const scheduling_analysis_thread* b)
35	{
36		return a->total_run_time > b->total_run_time;
37	}
38};
39
40
41struct WaitObjectGroupingComparator {
42	inline bool operator()(const scheduling_analysis_thread_wait_object* a,
43		const scheduling_analysis_thread_wait_object* b)
44	{
45		return a->wait_object->type < b->wait_object->type
46			|| (a->wait_object->type == b->wait_object->type
47				&& strcmp(a->wait_object->name, b->wait_object->name) < 0);
48	}
49};
50
51
52struct WaitObjectTimeComparator {
53	inline bool operator()(const scheduling_analysis_thread_wait_object* a,
54		const scheduling_analysis_thread_wait_object* b)
55	{
56		return a->wait_time > b->wait_time;
57	}
58};
59
60
61struct WaitObjectGroupTimeComparator {
62	inline bool operator()(const wait_object_group& a,
63		const wait_object_group& b)
64	{
65		return a.wait_time > b.wait_time;
66	}
67};
68
69
70static const char*
71wait_object_to_string(scheduling_analysis_wait_object* waitObject, char* buffer,
72	bool nameOnly = false)
73{
74	uint32 type = waitObject->type;
75	void* object = waitObject->object;
76
77	switch (type) {
78		case THREAD_BLOCK_TYPE_SEMAPHORE:
79			if (nameOnly) {
80				sprintf(buffer, "sem \"%s\"", waitObject->name);
81			} else {
82				sprintf(buffer, "sem %ld (%s)", (sem_id)(addr_t)object,
83					waitObject->name);
84			}
85			break;
86		case THREAD_BLOCK_TYPE_CONDITION_VARIABLE:
87			if (nameOnly) {
88				sprintf(buffer, "cvar \"%s\"", waitObject->name);
89			} else {
90				sprintf(buffer, "cvar %p (%s %p)", object, waitObject->name,
91					waitObject->referenced_object);
92			}
93			break;
94		case THREAD_BLOCK_TYPE_SNOOZE:
95			strcpy(buffer, "snooze");
96			break;
97		case THREAD_BLOCK_TYPE_SIGNAL:
98			strcpy(buffer, "signal");
99			break;
100		case THREAD_BLOCK_TYPE_MUTEX:
101			if (nameOnly)
102				sprintf(buffer, "mutex \"%s\"", waitObject->name);
103			else
104				sprintf(buffer, "mutex %p (%s)", object, waitObject->name);
105			break;
106		case THREAD_BLOCK_TYPE_RW_LOCK:
107			if (nameOnly)
108				sprintf(buffer, "rwlock \"%s\"", waitObject->name);
109			else
110				sprintf(buffer, "rwlock %p (%s)", object, waitObject->name);
111			break;
112		case THREAD_BLOCK_TYPE_USER:
113			strcpy(buffer, "user");
114			break;
115		case THREAD_BLOCK_TYPE_OTHER:
116			sprintf(buffer, "other %p (%s)", object, waitObject->name);
117			break;
118		case THREAD_BLOCK_TYPE_OTHER_OBJECT:
119			sprintf(buffer, "other object %p", object);
120			break;
121		default:
122			sprintf(buffer, "unknown %p", object);
123			break;
124	}
125
126	return buffer;
127}
128
129
130void
131do_scheduling_analysis(bigtime_t startTime, bigtime_t endTime,
132	size_t bufferSize)
133{
134	printf("\n");
135
136	// allocate a chunk of memory for the scheduling analysis
137	void* buffer = malloc(bufferSize);
138	if (buffer == NULL) {
139		fprintf(stderr, "Error: Failed to allocate memory for the scheduling "
140			"analysis.\n");
141		exit(1);
142	}
143	MemoryDeleter _(buffer);
144
145	// do the scheduling analysis
146	scheduling_analysis analysis;
147	status_t error = _kern_analyze_scheduling(startTime, endTime, buffer,
148		bufferSize, &analysis);
149	if (error != B_OK) {
150		fprintf(stderr, "Error: Scheduling analysis failed: %s\n",
151			strerror(error));
152		exit(1);
153	}
154
155	// allocate arrays for grouping and sorting the wait objects
156	scheduling_analysis_thread_wait_object** waitObjects
157		= new(std::nothrow) scheduling_analysis_thread_wait_object*[
158			analysis.thread_wait_object_count];
159	ArrayDeleter<scheduling_analysis_thread_wait_object*> _2(waitObjects);
160
161	wait_object_group* waitObjectGroups = new(std::nothrow) wait_object_group[
162		analysis.thread_wait_object_count];
163	ArrayDeleter<wait_object_group> _3(waitObjectGroups);
164
165	if (waitObjects == NULL || waitObjectGroups == NULL) {
166		fprintf(stderr, "Error: Out of memory\n");
167		exit(1);
168	}
169
170	printf("scheduling analysis: %lu threads, %llu wait objects, "
171		"%llu thread wait objects\n", analysis.thread_count,
172		analysis.wait_object_count, analysis.thread_wait_object_count);
173
174	// sort the thread by run time
175	std::sort(analysis.threads, analysis.threads + analysis.thread_count,
176		ThreadRunTimeComparator());
177
178	for (uint32 i = 0; i < analysis.thread_count; i++) {
179		scheduling_analysis_thread* thread = analysis.threads[i];
180
181		// compute total wait time and prepare the objects for sorting
182		int32 waitObjectCount = 0;
183		bigtime_t waitTime = 0;
184		scheduling_analysis_thread_wait_object* threadWaitObject
185			= thread->wait_objects;
186		while (threadWaitObject != NULL) {
187			waitObjects[waitObjectCount++] = threadWaitObject;
188			waitTime += threadWaitObject->wait_time;
189			threadWaitObject = threadWaitObject->next_in_list;
190		}
191
192		// sort the wait objects by type + name
193		std::sort(waitObjects, waitObjects + waitObjectCount,
194			WaitObjectGroupingComparator());
195
196		// create the groups
197		wait_object_group* group = NULL;
198		int32 groupCount = 0;
199		for (int32 i = 0; i < waitObjectCount; i++) {
200			scheduling_analysis_thread_wait_object* threadWaitObject
201				= waitObjects[i];
202			scheduling_analysis_wait_object* waitObject
203				= threadWaitObject->wait_object;
204
205			if (groupCount == 0 || strcmp(waitObject->name, "?") == 0
206				|| waitObject->type != group->objects[0]->wait_object->type
207				|| strcmp(waitObject->name,
208						group->objects[0]->wait_object->name) != 0) {
209				// create a new group
210				group = &waitObjectGroups[groupCount++];
211				group->objects = waitObjects + i;
212				group->count = 0;
213				group->wait_time = 0;
214				group->waits = 0;
215			}
216
217			group->count++;
218			group->wait_time += threadWaitObject->wait_time;
219			group->waits += threadWaitObject->waits;
220		}
221
222		// sort the groups by wait time
223		std::sort(waitObjectGroups, waitObjectGroups + groupCount,
224			WaitObjectGroupTimeComparator());
225
226		printf("\nthread %ld \"%s\":\n", thread->id, thread->name);
227		printf("  run time:    %lld us (%lld runs)\n", thread->total_run_time,
228			thread->runs);
229		printf("  wait time:   %lld us\n", waitTime);
230		printf("  latencies:   %lld us (%lld)\n", thread->total_latency,
231			thread->latencies);
232		printf("  preemptions: %lld us (%lld)\n", thread->total_rerun_time,
233			thread->reruns);
234		printf("  unspecified: %lld us\n", thread->unspecified_wait_time);
235
236		printf("  waited on:\n");
237		for (int32 i = 0; i < groupCount; i++) {
238			wait_object_group& group = waitObjectGroups[i];
239			char buffer[1024];
240
241			if (group.count == 1) {
242				// only one element -- just print it
243				scheduling_analysis_thread_wait_object* threadWaitObject
244					= group.objects[0];
245				scheduling_analysis_wait_object* waitObject
246					= threadWaitObject->wait_object;
247				wait_object_to_string(waitObject, buffer);
248				printf("    %s: %lld us (%lld)\n", buffer,
249					threadWaitObject->wait_time, threadWaitObject->waits);
250			} else {
251				// sort the wait objects by wait time
252				std::sort(group.objects, group.objects + group.count,
253					WaitObjectTimeComparator());
254
255				// print the group line
256				wait_object_to_string(group.objects[0]->wait_object, buffer,
257					true);
258				printf("    group %s: %lld us (%lld)\n", buffer,
259					group.wait_time, group.waits);
260
261				// print the wait objects
262				for (int32 k = 0; k < group.count; k++) {
263					scheduling_analysis_thread_wait_object* threadWaitObject
264						= group.objects[k];
265					scheduling_analysis_wait_object* waitObject
266						= threadWaitObject->wait_object;
267					wait_object_to_string(waitObject, buffer);
268					printf("      %s: %lld us (%lld)\n", buffer,
269						threadWaitObject->wait_time, threadWaitObject->waits);
270				}
271			}
272		}
273	}
274}
275