Commit | Line | Data |
---|---|---|
5225e788 AB |
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 "globals.h" | |
22 | ||
6eb42155 | 23 | static struct file_info *seek_files = NULL; |
b2ecdd0f | 24 | |
5225e788 | 25 | struct seek_bkt { |
6eb42155 | 26 | struct rb_node rb_node; |
5225e788 AB |
27 | long long sectors; |
28 | int nseeks; | |
29 | }; | |
30 | ||
31 | struct seeki { | |
32 | FILE *rfp, *wfp; | |
6eb42155 ADB |
33 | struct rb_root root; |
34 | long long tot_seeks; | |
5225e788 AB |
35 | double total_sectors; |
36 | long long last_start, last_end; | |
37 | }; | |
38 | ||
6eb42155 | 39 | static FILE *seek_open(__u32 device, char rw) |
5225e788 AB |
40 | { |
41 | FILE *fp; | |
42 | char *oname; | |
43 | int mjr, mnr; | |
44 | ||
45 | if (seek_name == NULL) return NULL; | |
46 | ||
47 | mjr = device >> MINORBITS; | |
48 | mnr = device & ((1 << MINORBITS) - 1); | |
49 | ||
b2ecdd0f | 50 | oname = malloc(strlen(seek_name)+32); |
5225e788 AB |
51 | sprintf(oname, "%s_%03d,%03d_%c.dat", seek_name, mjr, mnr, rw); |
52 | if ((fp = fopen(oname, "w")) == NULL) | |
53 | perror(oname); | |
b2ecdd0f | 54 | else |
6eb42155 | 55 | add_file(&seek_files, fp, oname); |
5225e788 AB |
56 | |
57 | return fp; | |
58 | } | |
59 | ||
6eb42155 ADB |
60 | static void __insert(struct rb_root *root, long long sectors) |
61 | { | |
62 | struct seek_bkt *sbp; | |
63 | struct rb_node *parent = NULL; | |
64 | struct rb_node **p = &root->rb_node; | |
65 | ||
66 | while (*p) { | |
67 | parent = *p; | |
68 | sbp = rb_entry(parent, struct seek_bkt, rb_node); | |
69 | if (sectors < sbp->sectors) | |
70 | p = &(*p)->rb_left; | |
71 | else if (sectors > sbp->sectors) | |
72 | p = &(*p)->rb_right; | |
73 | else { | |
74 | sbp->nseeks++; | |
75 | return; | |
76 | } | |
77 | } | |
78 | ||
79 | sbp = malloc(sizeof(struct seek_bkt)); | |
80 | sbp->nseeks = 1; | |
81 | sbp->sectors = sectors; | |
82 | ||
83 | rb_link_node(&sbp->rb_node, parent, p); | |
84 | rb_insert_color(&sbp->rb_node, root); | |
85 | } | |
86 | ||
b2ecdd0f ADB |
87 | void seek_clean(void) |
88 | { | |
6eb42155 | 89 | clean_files(&seek_files); |
b2ecdd0f ADB |
90 | } |
91 | ||
5225e788 AB |
92 | long long seek_dist(struct seeki *sip, struct io *iop) |
93 | { | |
94 | long long dist; | |
95 | long long start = BIT_START(iop), end = BIT_END(iop); | |
96 | ||
97 | /* Some overlap means no seek */ | |
98 | if (((sip->last_start <= start) && (start <= sip->last_end)) || | |
99 | ((sip->last_start <= end) && (end <= sip->last_end))) | |
100 | dist = 0; | |
101 | else if (start > sip->last_end) | |
102 | dist = start - sip->last_end; | |
103 | else | |
104 | dist = start - sip->last_start; | |
105 | ||
106 | sip->last_start = start; | |
107 | sip->last_end = end; | |
108 | return dist; | |
109 | } | |
110 | ||
111 | void *seeki_init(__u32 device) | |
112 | { | |
113 | struct seeki *sip = malloc(sizeof(struct seeki)); | |
114 | ||
115 | sip->rfp = seek_open(device, 'r'); | |
116 | sip->wfp = seek_open(device, 'w'); | |
6eb42155 | 117 | sip->tot_seeks = 0; |
5225e788 AB |
118 | sip->total_sectors = 0.0; |
119 | sip->last_start = sip->last_end = 0; | |
6eb42155 | 120 | memset(&sip->root, 0, sizeof(sip->root)); |
5225e788 AB |
121 | |
122 | return sip; | |
123 | } | |
124 | ||
125 | void seeki_add(void *handle, struct io *iop) | |
126 | { | |
5225e788 AB |
127 | struct seeki *sip = handle; |
128 | long long dist = seek_dist(sip, iop); | |
129 | FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp; | |
130 | ||
131 | if (fp) | |
132 | fprintf(fp, "%15.9lf %13lld\n", BIT_TIME(iop->t.time), dist); | |
133 | ||
134 | dist = llabs(dist); | |
6eb42155 | 135 | sip->tot_seeks++; |
5225e788 | 136 | sip->total_sectors += dist; |
6eb42155 | 137 | __insert(&sip->root, dist); |
5225e788 AB |
138 | } |
139 | ||
140 | long long seeki_nseeks(void *handle) | |
141 | { | |
6eb42155 | 142 | return ((struct seeki *)handle)->tot_seeks; |
5225e788 AB |
143 | } |
144 | ||
145 | double seeki_mean(void *handle) | |
146 | { | |
147 | struct seeki *sip = handle; | |
6eb42155 ADB |
148 | return sip->total_sectors / sip->tot_seeks; |
149 | } | |
150 | ||
151 | int __median(struct rb_node *n, long long sofar, long long target, long | |
152 | long *rvp) | |
153 | { | |
154 | struct seek_bkt *sbp; | |
155 | ||
156 | sbp = rb_entry(n, struct seek_bkt, rb_node); | |
157 | if ((sofar + sbp->nseeks) >= target) { | |
158 | *rvp = sbp->sectors; | |
159 | return 1; | |
160 | } | |
161 | ||
162 | if (n->rb_left && __median(n->rb_left, sofar, target, rvp)) | |
163 | return 1; | |
164 | ||
165 | if (n->rb_right && __median(n->rb_right, sofar, target, rvp)) | |
166 | return 1; | |
167 | ||
168 | return 0; | |
169 | ||
5225e788 AB |
170 | } |
171 | ||
172 | long long seeki_median(void *handle) | |
173 | { | |
6eb42155 | 174 | long long rval = 0LL; |
5225e788 | 175 | struct seeki *sip = handle; |
5225e788 | 176 | |
6eb42155 ADB |
177 | if (sip->root.rb_node) |
178 | (void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2, | |
179 | &rval); | |
5225e788 | 180 | |
6eb42155 | 181 | return rval; |
5225e788 AB |
182 | } |
183 | ||
6eb42155 ADB |
184 | void __mode(struct rb_node *n, struct mode *mp) |
185 | { | |
186 | struct seek_bkt *sbp; | |
187 | ||
188 | if (n->rb_left) __mode(n->rb_left, mp); | |
189 | if (n->rb_right) __mode(n->rb_right, mp); | |
190 | ||
191 | sbp = rb_entry(n, struct seek_bkt, rb_node); | |
192 | if (mp->modes == NULL) { | |
193 | mp->modes = malloc(sizeof(long long)); | |
194 | mp->nmds = 0; | |
195 | } | |
196 | else if (sbp->nseeks > mp->most_seeks) | |
197 | mp->nmds = 0; | |
198 | else if (sbp->nseeks == mp->most_seeks) | |
199 | mp->modes = realloc(mp->modes, (mp->nmds + 1) * | |
200 | sizeof(long long)); | |
201 | else | |
202 | return; | |
203 | ||
204 | mp->most_seeks = sbp->nseeks; | |
205 | mp->modes[mp->nmds++] = sbp->sectors; | |
206 | } | |
207 | ||
208 | int seeki_mode(void *handle, struct mode *mp) | |
5225e788 | 209 | { |
5225e788 | 210 | struct seeki *sip = handle; |
6eb42155 ADB |
211 | struct rb_root *root = &sip->root; |
212 | ||
213 | memset(mp, 0, sizeof(struct mode)); | |
214 | if (root->rb_node) | |
215 | __mode(root->rb_node, mp); | |
5225e788 | 216 | |
6eb42155 | 217 | return mp->nmds; |
5225e788 | 218 | } |