1/*
2 * blktrace output analysis: generate a timeline & gather statistics
3 *
4 * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle@hp.com>
5 *
6 *  This program is free software; you can redistribute it and/or modify
7 *  it under the terms of the GNU General Public License as published by
8 *  the Free Software Foundation; either version 2 of the License, or
9 *  (at your option) any later version.
10 *
11 *  This program is distributed in the hope that it will be useful,
12 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 *  GNU General Public License for more details.
15 *
16 *  You should have received a copy of the GNU General Public License
17 *  along with this program; if not, write to the Free Software
18 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19 *
20 */
21#include <string.h>
22
23#include "globals.h"
24
25struct pn_info {
26	struct rb_node rb_node;
27	struct p_info *pip;
28	union {
29		char *name;
30		__u32 pid;
31	}  u;
32};
33
34struct rb_root root_pid, root_name;
35
36static void __foreach(struct rb_node *n, void (*f)(struct p_info *, void *),
37			void *arg)
38{
39	if (n) {
40		__foreach(n->rb_left, f, arg);
41		f(rb_entry(n, struct pn_info, rb_node)->pip, arg);
42		__foreach(n->rb_right, f, arg);
43	}
44}
45
46static void __destroy(struct rb_node *n, int free_name, int free_pip)
47{
48	if (n) {
49		struct pn_info *pnp = rb_entry(n, struct pn_info, rb_node);
50
51		__destroy(n->rb_left, free_name, free_pip);
52		__destroy(n->rb_right, free_name, free_pip);
53
54		if (free_name)
55			free(pnp->u.name);
56		if (free_pip) {
57			free(pnp->pip->name);
58			region_exit(&pnp->pip->regions);
59			free(pnp->pip);
60		}
61		free(pnp);
62	}
63}
64
65struct p_info * __find_process_pid(__u32 pid)
66{
67	struct pn_info *this;
68	struct rb_node *n = root_pid.rb_node;
69
70	while (n) {
71		this = rb_entry(n, struct pn_info, rb_node);
72		if (pid < this->u.pid)
73			n = n->rb_left;
74		else if (pid > this->u.pid)
75			n = n->rb_right;
76		else
77			return this->pip;
78	}
79
80	return NULL;
81}
82
83struct p_info *__find_process_name(char *name)
84{
85	int cmp;
86	struct pn_info *this;
87	struct rb_node *n = root_name.rb_node;
88
89	while (n) {
90		this = rb_entry(n, struct pn_info, rb_node);
91		cmp = strcmp(name, this->u.name);
92		if (cmp < 0)
93			n = n->rb_left;
94		else if (cmp > 0)
95			n = n->rb_right;
96		else
97			return this->pip;
98	}
99
100	return NULL;
101}
102
103static void insert_pid(struct p_info *that, __u32 pid)
104{
105	struct pn_info *this;
106	struct rb_node *parent = NULL;
107	struct rb_node **p = &root_pid.rb_node;
108
109	while (*p) {
110		parent = *p;
111		this = rb_entry(parent, struct pn_info, rb_node);
112
113		if (pid < this->u.pid)
114			p = &(*p)->rb_left;
115		else if (pid > this->u.pid)
116			p = &(*p)->rb_right;
117		else
118			return;	// Already there
119	}
120
121	this = malloc(sizeof(struct pn_info));
122	this->u.pid = pid;
123	this->pip = that;
124
125	rb_link_node(&this->rb_node, parent, p);
126	rb_insert_color(&this->rb_node, &root_pid);
127}
128
129static void insert_name(struct p_info *that)
130{
131	int cmp;
132	struct pn_info *this;
133	struct rb_node *parent = NULL;
134	struct rb_node **p = &root_name.rb_node;
135
136	while (*p) {
137		parent = *p;
138		this = rb_entry(parent, struct pn_info, rb_node);
139		cmp = strcmp(that->name, this->u.name);
140
141		if (cmp < 0)
142			p = &(*p)->rb_left;
143		else if (cmp > 0)
144			p = &(*p)->rb_right;
145		else
146			return;	// Already there...
147	}
148
149	this = malloc(sizeof(struct pn_info));
150	this->u.name = strdup(that->name);
151	this->pip = that;
152
153	rb_link_node(&this->rb_node, parent, p);
154	rb_insert_color(&this->rb_node, &root_name);
155}
156
157static void insert(struct p_info *pip)
158{
159	insert_pid(pip, pip->pid);
160	insert_name(pip);
161}
162
163static inline struct p_info *pip_alloc(void)
164{
165	return memset(malloc(sizeof(struct p_info)), 0, sizeof(struct p_info));
166}
167
168struct p_info *find_process(__u32 pid, char *name)
169{
170	struct p_info *pip;
171
172	if (pid != ((__u32)-1)) {
173		if ((pip = __find_process_pid(pid)) != NULL)
174			return pip;
175		else if (name) {
176			pip = __find_process_name(name);
177
178			if (pip && pid != pip->pid) {
179				/*
180				 * This is a process with the same name
181				 * as another, but a different PID.
182				 *
183				 * We'll store a reference in the PID
184				 * tree...
185				 */
186				insert_pid(pip, pid);
187			}
188			return pip;
189		}
190
191		/*
192		 * We're here because we have a pid, and no name, but
193		 * we didn't find a process ...
194		 *
195		 * We'll craft one using the pid...
196		 */
197
198		name = alloca(256);
199		sprintf(name, "pid%09u", pid);
200		process_alloc(pid, name);
201		return __find_process_pid(pid);
202	}
203
204	return __find_process_name(name);
205}
206
207void process_alloc(__u32 pid, char *name)
208{
209	struct p_info *pip = find_process(pid, name);
210
211	if (pip == NULL) {
212		pip = pip_alloc();
213		pip->pid = pid;
214		region_init(&pip->regions);
215		pip->last_q = (__u64)-1;
216		pip->name = strdup(name);
217
218		insert(pip);
219	}
220}
221
222void pip_update_q(struct io *iop)
223{
224	if (iop->pip) {
225		if (remapper_dev(iop->dip->device))
226			update_lq(&iop->pip->last_q, &iop->pip->avgs.q2q_dm,
227								iop->t.time);
228		else
229			update_lq(&iop->pip->last_q, &iop->pip->avgs.q2q,
230								iop->t.time);
231		update_qregion(&iop->pip->regions, iop->t.time);
232	}
233}
234
235void pip_foreach_out(void (*f)(struct p_info *, void *), void *arg)
236{
237	if (exes == NULL)
238		__foreach(root_name.rb_node, f, arg);
239	else {
240		struct p_info *pip;
241		char *exe, *p, *next, *exes_save = strdup(exes);
242
243		p = exes_save;
244		while (exes_save != NULL) {
245			exe = exes_save;
246			if ((next = strchr(exes_save, ',')) != NULL) {
247				*next = '\0';
248				exes_save = next+1;
249			} else
250				exes_save = NULL;
251
252			pip = __find_process_name(exe);
253			if (pip)
254				f(pip, arg);
255		}
256	}
257}
258
259void pip_exit(void)
260{
261	__destroy(root_pid.rb_node, 0, 0);
262	__destroy(root_name.rb_node, 1, 1);
263}
264