sched: Move blk_schedule_flush_plug() out of __schedule()
[linux-2.6.git] / kernel / timeconst.pl
1 #!/usr/bin/perl
2 # -----------------------------------------------------------------------
3 #
4 #   Copyright 2007-2008 rPath, Inc. - All Rights Reserved
5 #
6 #   This file is part of the Linux kernel, and is made available under
7 #   the terms of the GNU General Public License version 2 or (at your
8 #   option) any later version; incorporated herein by reference.
9 #
10 # -----------------------------------------------------------------------
11 #
12
13 #
14 # Usage: timeconst.pl HZ > timeconst.h
15 #
16
17 # Precomputed values for systems without Math::BigInt
18 # Generated by:
19 # timeconst.pl --can 24 32 48 64 100 122 128 200 250 256 300 512 1000 1024 1200
20 %canned_values = (
21         24 => [
22                 '0xa6aaaaab','0x2aaaaaa',26,
23                 125,3,
24                 '0xc49ba5e4','0x1fbe76c8b4',37,
25                 3,125,
26                 '0xa2c2aaab','0xaaaa',16,
27                 125000,3,
28                 '0xc9539b89','0x7fffbce4217d',47,
29                 3,125000,
30         ], 32 => [
31                 '0xfa000000','0x6000000',27,
32                 125,4,
33                 '0x83126e98','0xfdf3b645a',36,
34                 4,125,
35                 '0xf4240000','0x0',17,
36                 31250,1,
37                 '0x8637bd06','0x3fff79c842fa',46,
38                 1,31250,
39         ], 48 => [
40                 '0xa6aaaaab','0x6aaaaaa',27,
41                 125,6,
42                 '0xc49ba5e4','0xfdf3b645a',36,
43                 6,125,
44                 '0xa2c2aaab','0x15555',17,
45                 62500,3,
46                 '0xc9539b89','0x3fffbce4217d',46,
47                 3,62500,
48         ], 64 => [
49                 '0xfa000000','0xe000000',28,
50                 125,8,
51                 '0x83126e98','0x7ef9db22d',35,
52                 8,125,
53                 '0xf4240000','0x0',18,
54                 15625,1,
55                 '0x8637bd06','0x1fff79c842fa',45,
56                 1,15625,
57         ], 100 => [
58                 '0xa0000000','0x0',28,
59                 10,1,
60                 '0xcccccccd','0x733333333',35,
61                 1,10,
62                 '0x9c400000','0x0',18,
63                 10000,1,
64                 '0xd1b71759','0x1fff2e48e8a7',45,
65                 1,10000,
66         ], 122 => [
67                 '0x8325c53f','0xfbcda3a',28,
68                 500,61,
69                 '0xf9db22d1','0x7fbe76c8b',35,
70                 61,500,
71                 '0x8012e2a0','0x3ef36',18,
72                 500000,61,
73                 '0xffda4053','0x1ffffbce4217',45,
74                 61,500000,
75         ], 128 => [
76                 '0xfa000000','0x1e000000',29,
77                 125,16,
78                 '0x83126e98','0x3f7ced916',34,
79                 16,125,
80                 '0xf4240000','0x40000',19,
81                 15625,2,
82                 '0x8637bd06','0xfffbce4217d',44,
83                 2,15625,
84         ], 200 => [
85                 '0xa0000000','0x0',29,
86                 5,1,
87                 '0xcccccccd','0x333333333',34,
88                 1,5,
89                 '0x9c400000','0x0',19,
90                 5000,1,
91                 '0xd1b71759','0xfff2e48e8a7',44,
92                 1,5000,
93         ], 250 => [
94                 '0x80000000','0x0',29,
95                 4,1,
96                 '0x80000000','0x180000000',33,
97                 1,4,
98                 '0xfa000000','0x0',20,
99                 4000,1,
100                 '0x83126e98','0x7ff7ced9168',43,
101                 1,4000,
102         ], 256 => [
103                 '0xfa000000','0x3e000000',30,
104                 125,32,
105                 '0x83126e98','0x1fbe76c8b',33,
106                 32,125,
107                 '0xf4240000','0xc0000',20,
108                 15625,4,
109                 '0x8637bd06','0x7ffde7210be',43,
110                 4,15625,
111         ], 300 => [
112                 '0xd5555556','0x2aaaaaaa',30,
113                 10,3,
114                 '0x9999999a','0x1cccccccc',33,
115                 3,10,
116                 '0xd0555556','0xaaaaa',20,
117                 10000,3,
118                 '0x9d495183','0x7ffcb923a29',43,
119                 3,10000,
120         ], 512 => [
121                 '0xfa000000','0x7e000000',31,
122                 125,64,
123                 '0x83126e98','0xfdf3b645',32,
124                 64,125,
125                 '0xf4240000','0x1c0000',21,
126                 15625,8,
127                 '0x8637bd06','0x3ffef39085f',42,
128                 8,15625,
129         ], 1000 => [
130                 '0x80000000','0x0',31,
131                 1,1,
132                 '0x80000000','0x0',31,
133                 1,1,
134                 '0xfa000000','0x0',22,
135                 1000,1,
136                 '0x83126e98','0x1ff7ced9168',41,
137                 1,1000,
138         ], 1024 => [
139                 '0xfa000000','0xfe000000',32,
140                 125,128,
141                 '0x83126e98','0x7ef9db22',31,
142                 128,125,
143                 '0xf4240000','0x3c0000',22,
144                 15625,16,
145                 '0x8637bd06','0x1fff79c842f',41,
146                 16,15625,
147         ], 1200 => [
148                 '0xd5555556','0xd5555555',32,
149                 5,6,
150                 '0x9999999a','0x66666666',31,
151                 6,5,
152                 '0xd0555556','0x2aaaaa',22,
153                 2500,3,
154                 '0x9d495183','0x1ffcb923a29',41,
155                 3,2500,
156         ]
157 );
158
159 $has_bigint = eval 'use Math::BigInt qw(bgcd); 1;';
160
161 sub bint($)
162 {
163         my($x) = @_;
164         return Math::BigInt->new($x);
165 }
166
167 #
168 # Constants for division by reciprocal multiplication.
169 # (bits, numerator, denominator)
170 #
171 sub fmul($$$)
172 {
173         my ($b,$n,$d) = @_;
174
175         $n = bint($n);
176         $d = bint($d);
177
178         return scalar (($n << $b)+$d-bint(1))/$d;
179 }
180
181 sub fadj($$$)
182 {
183         my($b,$n,$d) = @_;
184
185         $n = bint($n);
186         $d = bint($d);
187
188         $d = $d/bgcd($n, $d);
189         return scalar (($d-bint(1)) << $b)/$d;
190 }
191
192 sub fmuls($$$) {
193         my($b,$n,$d) = @_;
194         my($s,$m);
195         my($thres) = bint(1) << ($b-1);
196
197         $n = bint($n);
198         $d = bint($d);
199
200         for ($s = 0; 1; $s++) {
201                 $m = fmul($s,$n,$d);
202                 return $s if ($m >= $thres);
203         }
204         return 0;
205 }
206
207 # Generate a hex value if the result fits in 64 bits;
208 # otherwise skip.
209 sub bignum_hex($) {
210         my($x) = @_;
211         my $s = $x->as_hex();
212
213         return (length($s) > 18) ? undef : $s;
214 }
215
216 # Provides mul, adj, and shr factors for a specific
217 # (bit, time, hz) combination
218 sub muladj($$$) {
219         my($b, $t, $hz) = @_;
220         my $s = fmuls($b, $t, $hz);
221         my $m = fmul($s, $t, $hz);
222         my $a = fadj($s, $t, $hz);
223         return (bignum_hex($m), bignum_hex($a), $s);
224 }
225
226 # Provides numerator, denominator values
227 sub numden($$) {
228         my($n, $d) = @_;
229         my $g = bgcd($n, $d);
230         return ($n/$g, $d/$g);
231 }
232
233 # All values for a specific (time, hz) combo
234 sub conversions($$) {
235         my ($t, $hz) = @_;
236         my @val = ();
237
238         # HZ_TO_xx
239         push(@val, muladj(32, $t, $hz));
240         push(@val, numden($t, $hz));
241
242         # xx_TO_HZ
243         push(@val, muladj(32, $hz, $t));
244         push(@val, numden($hz, $t));
245
246         return @val;
247 }
248
249 sub compute_values($) {
250         my($hz) = @_;
251         my @val = ();
252         my $s, $m, $a, $g;
253
254         if (!$has_bigint) {
255                 die "$0: HZ == $hz not canned and ".
256                     "Math::BigInt not available\n";
257         }
258
259         # MSEC conversions
260         push(@val, conversions(1000, $hz));
261
262         # USEC conversions
263         push(@val, conversions(1000000, $hz));
264
265         return @val;
266 }
267
268 sub outputval($$)
269 {
270         my($name, $val) = @_;
271         my $csuf;
272
273         if (defined($val)) {
274             if ($name !~ /SHR/) {
275                 $val = "U64_C($val)";
276             }
277             printf "#define %-23s %s\n", $name.$csuf, $val.$csuf;
278         }
279 }
280
281 sub output($@)
282 {
283         my($hz, @val) = @_;
284         my $pfx, $bit, $suf, $s, $m, $a;
285
286         print "/* Automatically generated by kernel/timeconst.pl */\n";
287         print "/* Conversion constants for HZ == $hz */\n";
288         print "\n";
289         print "#ifndef KERNEL_TIMECONST_H\n";
290         print "#define KERNEL_TIMECONST_H\n";
291         print "\n";
292
293         print "#include <linux/param.h>\n";
294         print "#include <linux/types.h>\n";
295
296         print "\n";
297         print "#if HZ != $hz\n";
298         print "#error \"kernel/timeconst.h has the wrong HZ value!\"\n";
299         print "#endif\n";
300         print "\n";
301
302         foreach $pfx ('HZ_TO_MSEC','MSEC_TO_HZ',
303                       'HZ_TO_USEC','USEC_TO_HZ') {
304                 foreach $bit (32) {
305                         foreach $suf ('MUL', 'ADJ', 'SHR') {
306                                 outputval("${pfx}_$suf$bit", shift(@val));
307                         }
308                 }
309                 foreach $suf ('NUM', 'DEN') {
310                         outputval("${pfx}_$suf", shift(@val));
311                 }
312         }
313
314         print "\n";
315         print "#endif /* KERNEL_TIMECONST_H */\n";
316 }
317
318 # Pretty-print Perl values
319 sub perlvals(@) {
320         my $v;
321         my @l = ();
322
323         foreach $v (@_) {
324                 if (!defined($v)) {
325                         push(@l, 'undef');
326                 } elsif ($v =~ /^0x/) {
327                         push(@l, "\'".$v."\'");
328                 } else {
329                         push(@l, $v.'');
330                 }
331         }
332         return join(',', @l);
333 }
334
335 ($hz) = @ARGV;
336
337 # Use this to generate the %canned_values structure
338 if ($hz eq '--can') {
339         shift(@ARGV);
340         @hzlist = sort {$a <=> $b} (@ARGV);
341
342         print "# Precomputed values for systems without Math::BigInt\n";
343         print "# Generated by:\n";
344         print "# timeconst.pl --can ", join(' ', @hzlist), "\n";
345         print "\%canned_values = (\n";
346         my $pf = "\t";
347         foreach $hz (@hzlist) {
348                 my @values = compute_values($hz);
349                 print "$pf$hz => [\n";
350                 while (scalar(@values)) {
351                         my $bit;
352                         foreach $bit (32) {
353                                 my $m = shift(@values);
354                                 my $a = shift(@values);
355                                 my $s = shift(@values);
356                                 print "\t\t", perlvals($m,$a,$s), ",\n";
357                         }
358                         my $n = shift(@values);
359                         my $d = shift(@values);
360                         print "\t\t", perlvals($n,$d), ",\n";
361                 }
362                 print "\t]";
363                 $pf = ', ';
364         }
365         print "\n);\n";
366 } else {
367         $hz += 0;                       # Force to number
368         if ($hz < 1) {
369                 die "Usage: $0 HZ\n";
370         }
371
372         @val = @{$canned_values{$hz}};
373         if (!defined(@val)) {
374                 @val = compute_values($hz);
375         }
376         output($hz, @val);
377 }
378 exit 0;