The return of the return of crunch time (2.5 merge candidate list 1.6)
A message that is not in the archive (sent off-list or not yet received): [email protected]
Rob Landley <[email protected]> writes:
I have some patches to offer better than second resolution for stat. That is needed for parallel make on MP systems, because otherwise it cannot detect changes that need less than a second to execute. With CPUs being as fast as they are and getting even faster currently it is becomming a bigger problem. You don't hit it that easily with gcc because it's getting faster slower than cpus are getting faster so it's usually slower than a second, but some people use make rules with other compilers or other commands.
I see it in the same category as "necessary changes" similar to 32bit dev_t.
Linux already has several filesystems in tree that support ns or better than s resolution in their underlying formats (XFS,JFS,NFSv3,VFAT)
Patches available on request or older versions from ftp://ftp.firstfloor.org/pub/ak/v2.5/nsec*
They don't actually add ns resolution, but jiffies resolution, which is 1ms on 2.5 and should be good enough for now. It reuses reserved fields in struct stat and doesn't need any user interface changes.
It requires editing of a lot of file systems in a straight forward way, so should be better done before the stable series starts.
There are some minor compatbility issues with fs that only support second timestamps like ext2/ext3, see nsec.notes in the ftp directory or past threads on that on the list.
-Andi
Quoted 6 lines · Andi Kleen
Patches available on request or older versions from ftp://ftp.firstfloor.org/pub/ak/v2.5/nsec*
They don't actually add ns resolution, but jiffies resolution, which is 1ms on 2.5 and should be good enough for now. It reuses reserved fields in struct stat and doesn't need any user interface changes.
Quoted 6 lines
It requires editing of a lot of file systems in a straight forward way, so should be better done before the stable series starts.
There are some minor compatbility issues with fs that only support second timestamps like ext2/ext3, see nsec.notes in the ftp directory or past threads on that on the list.
Just as an FYI - this is "in the pipes" for ext2/ext3 also, which the (very basic) support for variable-sized inodes that Ted has already submitted is the groundwork for (among other things). We will then have space to add usec timestamps to ext2/ext3 inodes for people who choose to have larger inodes (new filesystems only, to start with), and when we get more efficient EA storage we will also be able to store the "large inode fields" into EAs for existing filesystems.
Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/
A message that is not in the archive (sent off-list or not yet received): [email protected]
[cc'ed back to linux-kernel in case other people are interested in the rationale again]
Quoted 10 lines · Andrew Pimlott
Quoted 3 lines · Andi Kleen
I have some patches to offer better than second resolution for stat. That is needed for parallel make on MP systems, because otherwise it cannot detect changes that need less than a second to execute.
Would you mind spelling out the problem case? It's ususally not a big deal, because when a target and dependency have the same timestamp, make considers the target to be newer. Is there a subtlety with parallel make that I am not seeing? (And does it really depend on MP?)
I assume you mean 'older', not 'newer'?
Any default action is wrong in some case when an rule can take less than a second, there is no replacement for an accurate time stamp. Either the rule gets rebuilt too often (=annoying for the user because it's slow) or not often enough (= broken result).
Parallel make makes it worse because parallel make processes need the timestamp to comunicate - make cannot know from internal data if it has already run a rule or not. On MP systems the parallelism is higher, making the problem show more often.
Quoted 10 lines
Quoted 3 lines
There are some minor compatbility issues with fs that only support second timestamps like ext2/ext3, see nsec.notes in the ftp directory or past threads on that on the list.
I really feel strongly that you should not export resolution finer that what the filesystem can store. There is too much risk of breakage (especially given the late date of submission), and if (as you said) all common filesystems will be able to store sub-second timestamps soon, this shouldn't be a significant drawback. If this requires a new hook into the filesystem, so be it.
You have to export in some unit and it is convenient to use the most finegrained available (ns). This matches what other Unixes like Solaris do too. The program can always chose to ignore the ns (which will most do at least initially) part or even round more.
What happens currently in my patch is that the inode in memory stores jiffies resolution. As long as you don't run out of inode cache and need to flush/reload an inode you always have the best resolution.
When an inode is flushed on an old fs with only second resolution the subsecond part is truncated. This has the drawback that an inode timestamp can jump backwards on reload as seen by user space. Another way would be to round on flush, but that also has some problems :- for example you can get timestamps which are ahead of the current wall clock. Neither of them is ideal. Rounding properly requires hooks.
In my current patchkit I just chose to truncate because that was the easiest and the other more complicated solutions didn't offer any compeling advantage. One can hope that nanosecond aware applications know how to deal with these problems. One possibility would be to do the same as Solaris here so that ns aware apps stay portable, but I don't have access to a Solaris 8 system and cannot test what they do. It's a kind of arbitary choice. Also I don't see it as a big problem.
Long term of course all the file systems should support fine grained properly so that these issues do not occur anymore. I hope no new file systems will make the same mistake as to limiting the timestamp to a second resolution.
-Andi
Quoted 6 lines · Andi Kleen
Quoted 3 lines · Andrew Pimlott
Would you mind spelling out the problem case? It's ususally not a big deal, because when a target and dependency have the same timestamp, make considers the target to be newer.
I assume you mean 'older', not 'newer'?
No (but maybe I phrased it badly):
% cat Makefile
foo: bar
echo did it
% touch foo bar
% ls --full-time foo bar
-rw-r--r-- 1 pimlott pimlott 0 Sun Oct 27 09:36:26 2002 bar
-rw-r--r-- 1 pimlott pimlott 0 Sun Oct 27 09:36:26 2002 foo
% make
make: `foo' is up to date.
Ie, foo is considered newer.
Quoted 2 lines
Any default action is wrong in some case when an rule can take less than a second,
I'm sure there is a case where this is true, but my imagination and googling failed to provide one. Even the messages to the GNU make mailing list when Paul Eggert implemented nanosecond support didn't include a specific rationale.
Quoted 1 line
there is no replacement for an accurate time stamp.
While I agree, I thought that a concrete example might help persuade others. (I think I've even run into instances where second resolution was a real problem, I just can't recall them.)
Quoted 12 lines
Quoted 6 lines
I really feel strongly that you should not export resolution finer that what the filesystem can store. There is too much risk of breakage (especially given the late date of submission), and if (as you said) all common filesystems will be able to store sub-second timestamps soon, this shouldn't be a significant drawback. If this requires a new hook into the filesystem, so be it.
You have to export in some unit and it is convenient to use the most finegrained available (ns). This matches what other Unixes like Solaris do too. The program can always chose to ignore the ns (which will most do at least initially) part or even round more.
Quoted 7 lines
What happens currently in my patch is that the inode in memory stores jiffies resolution. As long as you don't run out of inode cache and need to flush/reload an inode you always have the best resolution.
When an inode is flushed on an old fs with only second resolution the subsecond part is truncated. This has the drawback that an inode timestamp can jump backwards on reload as seen by user space.
Example problem case (assuming a fs that stores only seconds, and a make that uses nanoseconds):
- I run the "save and build" command while editing foo.c at T = 0.1.
- foo.o is built at T = 0.2.
- I do some read-only operations on foo.c (eg, checkin), such that foo.o gets flushed but foo.c stays in memory.
- I build again. foo.o is reloaded and has timestamp T = 0, and so gets spuriously rebuilt.
Quoted 3 lines
Another way would be to round on flush, but that also has some problems :- for example you can get timestamps which are ahead of the current wall clock.
Only if the flush is less than a second after the write, right? How likely is that in Linux?
I tend to prefer the proposal to set the nanosecond field to 10^9-1. At least my scenario above doesn't happen.
Andrew
Quoted 9 lines · Andrew Pimlott
Example problem case (assuming a fs that stores only seconds, and a make that uses nanoseconds):
- I run the "save and build" command while editing
foo.cat T = 0.1.
- foo.o is built at T = 0.2.
- I do some read-only operations onfoo.c(eg, checkin), such that foo.o gets flushed butfoo.cstays in memory.
- I build again. foo.o is reloaded and has timestamp T = 0, and so gets spuriously rebuilt.
If your system, and your disks, are so fast that they can not only finish the build in under a second but can also flush the cache and reload it from disk in under a second, then:
A) the spurious rebuild is still a tiny fraction of a second.
B) You're seeing a penalty for using a filesystem that's too old for your setup. This is a configuration problem in userspace.
C) How would having ALL times rounded to a second be an improvement?
Rob
Signature · 2 lines
http://penguicon.sf.net - Terry Pratchett, Eric Raymond, Pete Abrams, Illiad, CmdrTaco, liquid nitrogen ice cream, and caffienated jello. Well why not?
Quoted 1 line
A) the spurious rebuild is still a tiny fraction of a second.
It can trigger other rebuilds which can take much longer.
-Andi
Quoted 12 lines · Rob Landley
Quoted 9 lines · Andrew Pimlott
Example problem case (assuming a fs that stores only seconds, and a make that uses nanoseconds):
- I run the "save and build" command while editing
foo.cat T = 0.1.
- foo.o is built at T = 0.2.
- I do some read-only operations onfoo.c(eg, checkin), such that foo.o gets flushed butfoo.cstays in memory.
- I build again. foo.o is reloaded and has timestamp T = 0, and so gets spuriously rebuilt.
Quoted 3 lines
If your system, and your disks, are so fast that they can not only finish the build in under a second but can also flush the cache and reload it from disk in under a second
That is not required. The requirement is that, when the last step happens (which can be any time in the future), (the inode of) foo.o has been flushed, and foo.c hasn't. Step 3 argues that this is plausible.
Quoted 1 line
C) How would having ALL times rounded to a second be an improvement?
foo.c and foo.o would both have timestamps of 0. make considers the target foo.o newer in this case, so will not rebuild it.
Andrew
Quoted 4 lines
Quoted 1 line
C) How would having ALL times rounded to a second be an improvement?
foo.cand foo.o would both have timestamps of 0. make considers the target foo.o newer in this case, so will not rebuild it.
But other stuff could break because it sees mtime > gettimeofday (strictly make could trigger a "your clock is warping" warning)
It's a tradeoff, all has some disadvantages. The simple truncation wins here because it's the simplest (KISS)
-Andi
Quoted 3 lines · Andrew Pimlott
I'm sure there is a case where this is true, but my imagination and googling failed to provide one. Even the messages to the GNU make
foo: bar
action1 <something that takes less than a second>
frob: foo
action2 <something that takes a long time>
action1 is executed. foo and bar have the same time stamp. action2 is executed.
make runs again. Default rule sees foo.mtime == bar.mtime and starts action1 and action2 again. action2 takes a long time. But it's unnecessary, because bar has not really changed.
Quoted 9 lines
Example problem case (assuming a fs that stores only seconds, and a make that uses nanoseconds):
- I run the "save and build" command while editing
foo.cat T = 0.1.
- foo.o is built at T = 0.2.
- I do some read-only operations onfoo.c(eg, checkin), such that foo.o gets flushed butfoo.cstays in memory.
- I build again. foo.o is reloaded and has timestamp T = 0, and so gets spuriously rebuilt.
Yes, when you file system has only second resolution then you can get spurious rebuilds if your inodes get flushed. There is no way my patch can fix that. While some of the cases may be avoided by better rounding, it would be better to handle such heuristics in user space if you really wanted to be clever. Or just make sure you have enough ram.
The point of my patchkit is to allow the file systems
who support better resolution to handle it properly. Other filesystems are not worse than before when they flush inodes (and better off when they keep everything in ram for your build because then they will enjoy full time resolution)
My notes about possible problems with older fs were really not about make, but about other programs that could see inconsistencies
It's a fairly obscure case because the inode has to be flushed and reloaded in less than a second (so not likely to trigger often in practice)
Quoted 7 lines
Quoted 4 lines
Another way would be to round on flush, but that also has some problems :- for example you can get timestamps which are ahead of the current wall clock.
Only if the flush is less than a second after the write, right? How likely is that in Linux?
Not very, but could happen in extreme cases.
Quoted 3 lines
I tend to prefer the proposal to set the nanosecond field to 10^9-1. At least my scenario above doesn't happen.
If you really wanted that I would recommend to change make. When all nanosecond parts are 0 it is reasonable for make to assume that the fs doesn't support finegrained resolution. But I'm not sure it's worth it.
-Andi
Quoted 8 lines · Andi Kleen
Quoted 3 lines · Andrew Pimlott
I'm sure there is a case where this is true, but my imagination and googling failed to provide one. Even the messages to the GNU make
foo: bar
action1 <something that takes less than a second>
Quoted 6 lines
frob: foo
action2 <something that takes a long time>action1 is executed. foo and bar have the same time stamp. action2 is executed.
Try it:
% cat Makefile
foo: bar
touch foo
frob: foo
sleep 10
touch frob
% rm foo bar frob
% touch bar
% make frob
touch foo
sleep 10
touch frob
% make frob
make: `frob' is up to date.
No problem with this case.
Quoted 2 lines
make runs again. Default rule sees foo.mtime == bar.mtime and starts action1 and action2 again.
make is not that broken. (Well, according to one post I googled, it was in 1970, but it was noticed and fixed, and the fixed behavior has long been standardized.)
Quoted 10 lines
Quoted 9 lines
Example problem case (assuming a fs that stores only seconds, and a make that uses nanoseconds):
- I run the "save and build" command while editing
foo.cat T = 0.1.
- foo.o is built at T = 0.2.
- I do some read-only operations onfoo.c(eg, checkin), such that foo.o gets flushed butfoo.cstays in memory.
- I build again. foo.o is reloaded and has timestamp T = 0, and so gets spuriously rebuilt.
Quoted 3 lines
Yes, when you file system has only second resolution then you can get spurious rebuilds if your inodes get flushed. There is no way my patch can fix that.
I grant that second-resolution timestamps are broken. But you seem to misunderstand how make works--the current problem is not that severe. Whereas your change introduces a different problem that (in my estimation) is more likely to appear, and will cause mare pain.
I'm saying you're replacing a problem (bad graularity) that
- is well known
- is intuitive
- doesn't cause severe problems in practice (or at least, nobody has provided an example)
with one (timestamps jumping at unpredictable times) that
- is obscure
- requires knowledge of kernel internals to understand
- will bite people (I claim, and have provided a concrete example)
- will be wickedly hard to reproduce and diagnose
Quoted 2 lines
The point of my patchkit is to allow the file systems who support better resolution to handle it properly.
If that is the point, why not leave the behavior unchanged for other filesystems? (Other than that it would be a bit more work.) Doesn't it make sense, on general principles, to be conservative?
Quoted 3 lines
It's a fairly obscure case because the inode has to be flushed and reloaded in less than a second (so not likely to trigger often in practice)
If that were true, I would agree that it's probably not an issue in practice. But unless I misunderstand, in the example I gave, the flush and reload of foo.o can happen any time between the first and second builds, which could be arbitrarily far apart. So I believe it's a fairly plausible scenario.
Anyway, this isn't the biggest deal in the world. Maybe I'm wrong and nobody will ever notice. But it doesn't seem like a good risk to take.
Andrew
Hi!
Quoted 5 lines
The point of my patchkit is to allow the file systems
who support better resolution to handle it properly. Other filesystems are not worse than before when they flush inodes (and better off when they keep everything in ram for your build because then they will enjoy full time resolution)
What about always rounding down even when inode is in memory? That is both simple and consistent.
Quoted 4 lines
If you really wanted that I would recommend to change make. When all nanosecond parts are 0 it is reasonable for make to assume that the fs doesn't support finegrained resolution. But I'm not sure it's worth it.
Thats really ugly heuristics. What about filling
nanosecond part with ~0 when unavailable?
Psvel
Quoted 8 lines · Pavel Machek
Quoted 5 lines
The point of my patchkit is to allow the file systems
who support better resolution to handle it properly. Other filesystems are not worse than before when they flush inodes (and better off when they keep everything in ram for your build because then they will enjoy full time resolution)What about always rounding down even when inode is in memory? That is both simple and consistent.
I assume you mean, for filesystems that don't support high resolution. That is what I think should be done as well. People have gotten along with second resolution all these years, so it's no great tragedy to make them continue; plus, it seems like the common filesystems will support high resolution soon anyway.
Paul Eggert listed lots of programs that could be broken if timestamps jump around. They could all implement heuristic work-arounds, but that would be 1) a miracle and 2) a waste of effort.
The only issue (as far as I can tell) is knowing when to round. Hard-coding a list of filesystems seems reasonable (though even that could be wrong if I load a newer filesystem module). Ideally, though, you would add a simple hook into the filesystem that asks it to round the timestamp for you. This would also accommodate filesystems that don't store seconds or nanoseconds, but some other resolution.
Andrew