Implementing stat() with FindFirstFile()

Implementing stat() with FindFirstFile()

[Magnus Bäck]

Is there any reason why compat/win32.h uses GetFileAttributesEx()
instead of FindFirstFile() to implement the stat() call on Windows?
The current implementation requires each queried file to be opened
and closed while FindFirstFile() only reads the directory.

I made a couple of test programs that stat()ed the 176k files on my
disk and got the following best times with GetFileAttributesEx() and
FindFirstFile() respectively:

./getfattr.exe < filelist.txt  1.31s user 9.72s system 27% cpu 40.424 total
./findfirst.exe < filelist.txt  1.92s user 13.98s system 95% cpu 16.681 total

I searched the archive and found a couple of threads touching upon the
subject, but nothing conclusive.

I have a (trivial) patch ready if such a change would be interesting.

-- 
Magnus Bäck
baeck@swipnet.se

Re: Implementing stat() with FindFirstFile()

[Johannes Sixt]

On Samstag, 21. März 2009, Magnus Bäck wrote:
> Is there any reason why compat/win32.h uses GetFileAttributesEx()
> instead of FindFirstFile() to implement the stat() call on Windows?
> The current implementation requires each queried file to be opened
> and closed while FindFirstFile() only reads the directory.

There is: File times are extremely important for git. Unfortunately, MS's 
implementation of stat and utime are broken, and they do use FindFirstFile(). 
Read up on the topic here:

http://search.cpan.org/~shay/Win32-UTCFileTime-1.50/lib/Win32/UTCFileTime.pm

To quote the important sentence:

"The problem with Microsoft's stat(2) and utime(2) [...] is basically this: 
file times reported by stat(2) or stored by utime(2) may change by an hour as 
we move into or out of daylight saving time (DST) if the computer is set 
to "Automatically adjust clock for daylight saving changes" [...]."

Be sure to read section "Background Reference".

Besides that, our stat() implementation is already ca. twice as fast as 
MSVCRT's stat(). (Thank you, Marius!)

-- Hannes

Re: Implementing stat() with FindFirstFile()

[Magnus Bäck]

On Saturday, March 21, 2009 at 20:55 CET,
     Johannes Sixt <j6t@kdbg.org> wrote:

> On Samstag, 21. März 2009, Magnus Bäck wrote:
>
> > Is there any reason why compat/win32.h uses GetFileAttributesEx()
> > instead of FindFirstFile() to implement the stat() call on Windows?
> > The current implementation requires each queried file to be opened
> > and closed while FindFirstFile() only reads the directory.
> 
> There is: File times are extremely important for git. Unfortunately,
> MS's implementation of stat and utime are broken, and they do use
> FindFirstFile(). Read up on the topic here:
> 
> http://search.cpan.org/~shay/Win32-UTCFileTime-1.50/lib/Win32/UTCFileTime.pm

Quite interesting, thanks. As it often is, "obvious" changes that
haven't been made aren't that obvious after all.

From what I gather the problematic conversion takes place in the Win32
layer, in which case we might be able to call the ZwQueryDirectoryFile()
kernel routine directly via ntdll.dll to obtain the file times straight
from the file system. Has anyone explored that path, and would it be
acceptable to make such a change?

[...]

-- 
Magnus Bäck
baeck@swipnet.se

Re: Implementing stat() with FindFirstFile()

[Johannes Sixt]

Magnus Bäck schrieb:
> From what I gather the problematic conversion takes place in the Win32
> layer, in which case we might be able to call the ZwQueryDirectoryFile()
> kernel routine directly via ntdll.dll to obtain the file times straight
> from the file system. Has anyone explored that path, and would it be
> acceptable to make such a change?

It depends.

The disadvantages are that this function is only available on Windows XP
and later and that it is not present in the header files of MinGW gcc.
It's on you to prove that there are advantages that clearly outweigh these
disadvantages.

-- Hannes

Re: Implementing stat() with FindFirstFile()

[Magnus Bäck]

On Thursday, March 26, 2009 at 08:15 CET,
     Johannes Sixt <j.sixt@viscovery.net> wrote:

> Magnus Bäck schrieb:
>
> > From what I gather the problematic conversion takes place in
> > the Win32 layer, in which case we might be able to call the
> > ZwQueryDirectoryFile() kernel routine directly via ntdll.dll
> > to obtain the file times straight from the file system. Has
> > anyone explored that path, and would it be acceptable to make
> > such a change?
>
> It depends.
>
> The disadvantages are that this function is only available on
> Windows XP and later and that it is not present in the header
> files of MinGW gcc.

I'd be very surprised if ZwQueryDirectoryFile() hasn't always
been around (I just verified ntdll.dll from NT 4.0), so that's
not a worry. Don't know why MSDN reports it as introduced in XP.

> It's on you to prove that there are advantages that clearly
> outweigh these disadvantages.

All right, I'll see if I can find time to take a look at this.
I just wanted to check that it wasn't a project policy or whatever
to bypass Win32.

-- 
Magnus Bäck
baeck@swipnet.se

Re: Implementing stat() with FindFirstFile()

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2024 bytes --]

Hi,

Magnus, it is the official policy to reply-to-all on this list.  This has 
been mentioned in the past quite often, and it will be mentioned in the 
future, too.

You actually forced me to manually look up and re-add Hannes' address.  I 
do not appreciate having to waste my time like that.

If that sounds negative, please understand that I am used to the ways of 
this list, and when I am annoyed by somebody not fitting in, then it is 
not totally _my_ mistake.

On Thu, 26 Mar 2009, Magnus Bäck wrote:

> On Thursday, March 26, 2009 at 08:15 CET,
>      Johannes Sixt <j.sixt@viscovery.net> wrote:
> 
> > Magnus Bäck schrieb:
> >
> > > From what I gather the problematic conversion takes place in the 
> > > Win32 layer, in which case we might be able to call the 
> > > ZwQueryDirectoryFile() kernel routine directly via ntdll.dll to 
> > > obtain the file times straight from the file system. Has anyone 
> > > explored that path, and would it be acceptable to make such a 
> > > change?
> >
> > It depends.
> >
> > The disadvantages are that this function is only available on Windows 
> > XP and later and that it is not present in the header files of MinGW 
> > gcc.
> 
> I'd be very surprised if ZwQueryDirectoryFile() hasn't always been 
> around (I just verified ntdll.dll from NT 4.0), so that's not a worry. 
> Don't know why MSDN reports it as introduced in XP.

As the current maintainer of msysGit, I refuse to have something in the 
installer I ship that relies on not-at-all guaranteed interfaces.

> > It's on you to prove that there are advantages that clearly outweigh 
> > these disadvantages.
> 
> All right, I'll see if I can find time to take a look at this. I just 
> wanted to check that it wasn't a project policy or whatever to bypass 
> Win32.

You can do whatever you want... This is Open Source.

However, I will try to stay with the officially supported functionality, 
even if that makes msysGit slower -- Windows will never reach the 
performance levels of Linux anyway.

Ciao,
Dscho

Re: Implementing stat() with FindFirstFile()

[Magnus Bäck]

On Friday, March 27, 2009 at 03:25 CET,
     Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

> Magnus, it is the official policy to reply-to-all on this list.  This
> has been mentioned in the past quite often, and it will be mentioned
> in the future, too.

Sorry, I was not aware. Doesn't seem to have been mentioned in the last
month or so. Perhaps it could be included in the list introduction
message? All people obviously won't read it, but some will.

> You actually forced me to manually look up and re-add Hannes' address.
> I do not appreciate having to waste my time like that.
>
> If that sounds negative, please understand that I am used to the ways
> of this list, and when I am annoyed by somebody not fitting in, then
> it is not totally _my_ mistake.

A plain "please use reply all" would've sufficed.

> On Thu, 26 Mar 2009, Magnus Bäck wrote:
>
> > I'd be very surprised if ZwQueryDirectoryFile() hasn't always been
> > around (I just verified ntdll.dll from NT 4.0), so that's not a
> > worry. Don't know why MSDN reports it as introduced in XP.
>
> As the current maintainer of msysGit, I refuse to have something in
> the installer I ship that relies on not-at-all guaranteed interfaces.

Although I do appreciate the importance of guaranteed interfaces,
I am also pragmatic. An incompatible change in ntdll.dll would break
vast amounts of programs, including cygwin. There is a lot to be said
about Microsoft and their APIs, but I don't think they have a habit of
changing ABIs or function semantics for userland libraries that have
been around for 15 years.

> > All right, I'll see if I can find time to take a look at this. I
> > just wanted to check that it wasn't a project policy or whatever
> > to bypass Win32.
>
> You can do whatever you want... This is Open Source.
>
> However, I will try to stay with the officially supported functionality,
> even if that makes msysGit slower -- Windows will never reach the
> performance levels of Linux anyway.

Okay, thanks. Just like you I hate wasting time, in my case with patches
that'll be refused.

-- 
Magnus Bäck
baeck@swipnet.se

Re: Implementing stat() with FindFirstFile()

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3616 bytes --]

Hi,

On Mon, 30 Mar 2009, Magnus Bäck wrote:

> On Friday, March 27, 2009 at 03:25 CET,
>      Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> 
> > Magnus, it is the official policy to reply-to-all on this list.  This
> > has been mentioned in the past quite often, and it will be mentioned
> > in the future, too.
> 
> Sorry, I was not aware. Doesn't seem to have been mentioned in the last
> month or so. Perhaps it could be included in the list introduction
> message? All people obviously won't read it, but some will.
> 
> > You actually forced me to manually look up and re-add Hannes' address.
> > I do not appreciate having to waste my time like that.
> >
> > If that sounds negative, please understand that I am used to the ways
> > of this list, and when I am annoyed by somebody not fitting in, then
> > it is not totally _my_ mistake.
> 
> A plain "please use reply all" would've sufficed.

I do recognize that I was too harsh: I apologize!

> > On Thu, 26 Mar 2009, Magnus Bäck wrote:
> >
> > > I'd be very surprised if ZwQueryDirectoryFile() hasn't always been
> > > around (I just verified ntdll.dll from NT 4.0), so that's not a
> > > worry. Don't know why MSDN reports it as introduced in XP.
> >
> > As the current maintainer of msysGit, I refuse to have something in
> > the installer I ship that relies on not-at-all guaranteed interfaces.
> 
> Although I do appreciate the importance of guaranteed interfaces,
> I am also pragmatic. An incompatible change in ntdll.dll would break
> vast amounts of programs, including cygwin. There is a lot to be said
> about Microsoft and their APIs, but I don't think they have a habit of
> changing ABIs or function semantics for userland libraries that have
> been around for 15 years.

That does not give me the warm and fuzzy feeling I want to have when 
shipping a new Git for Windows.

Had you pointed to some document that states that the function has been in 
all NT-based versions, that would have done the trick.

> > > All right, I'll see if I can find time to take a look at this. I 
> > > just wanted to check that it wasn't a project policy or whatever to 
> > > bypass Win32.
> >
> > You can do whatever you want... This is Open Source.
> >
> > However, I will try to stay with the officially supported functionality,
> > even if that makes msysGit slower -- Windows will never reach the
> > performance levels of Linux anyway.
> 
> Okay, thanks. Just like you I hate wasting time, in my case with patches
> that'll be refused.

Sorry, that was not at all what I meant.

Of course, I wanted to avoid having time wasted: yours and mine.  But if 
you find said document, or another proof that the function was not 
introduced by pure chance in some of NT's service packs, then that's 
perfectly fine with me.

But if it is, say, only in NT when upgrading to Explorer 6 or newer, I do 
not want to take it: I personally know a machine running NT without 
service packs, and with Internet Explorer 5.5, because every attempt at 
upgrading freezes the complete machine 10 seconds into the login screen.  
And no, the machine cannot run with another setup, because there is a 
6-figure microscope plugged in that refuses to be controlled by anything 
else than the proprietary software that just happens to run only on said 
NT4, with said IE5.5.

Again, I am sorry for my harsh reaction, but please understand that I 
_need_ better proof that nobody will be bitten by your change (chances are 
that I'd have to clean it up...).

After all, in the short time since the release of 1.6.2.1, we had over 
4000 downloads already.

Ciao,
Dscho

Re: Implementing stat() with FindFirstFile()

[Björn Steinbrink]

On 2009.03.30 02:52:47 +0200, Johannes Schindelin wrote:
> On Mon, 30 Mar 2009, Magnus Bäck wrote:
> > On Friday, March 27, 2009 at 03:25 CET,
> > Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > > On Thu, 26 Mar 2009, Magnus Bäck wrote:
> > > > I'd be very surprised if ZwQueryDirectoryFile() hasn't always been
> > > > around (I just verified ntdll.dll from NT 4.0), so that's not a
> > > > worry. Don't know why MSDN reports it as introduced in XP.
> > >
> > > As the current maintainer of msysGit, I refuse to have something in
> > > the installer I ship that relies on not-at-all guaranteed interfaces.
> > 
> > Although I do appreciate the importance of guaranteed interfaces,
> > I am also pragmatic. An incompatible change in ntdll.dll would break
> > vast amounts of programs, including cygwin. There is a lot to be said
> > about Microsoft and their APIs, but I don't think they have a habit of
> > changing ABIs or function semantics for userland libraries that have
> > been around for 15 years.
> 
> Had you pointed to some document that states that the function has been in 
> all NT-based versions, that would have done the trick.

Not official documentation, but at least from some MS guy it seems:
http://www.osronline.com/showThread.cfm?link=73086 (last message).

Apparently, it was in NT3.x, but they document only what's actually
defined in the header.

Björn, feeling weird for trying to help with some Windows issue...

Re: Implementing stat() with FindFirstFile()

[Heiko Voigt]

On Mon, Mar 30, 2009 at 07:11:18AM +0200, Björn Steinbrink wrote:
> On 2009.03.30 02:52:47 +0200, Johannes Schindelin wrote:
> > On Mon, 30 Mar 2009, Magnus Bäck wrote:
> > > On Friday, March 27, 2009 at 03:25 CET,
> > > Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > > > On Thu, 26 Mar 2009, Magnus Bäck wrote:
> > > > > I'd be very surprised if ZwQueryDirectoryFile() hasn't always been
> > > > > around (I just verified ntdll.dll from NT 4.0), so that's not a
> > > > > worry. Don't know why MSDN reports it as introduced in XP.
> > > >
> > > > As the current maintainer of msysGit, I refuse to have something in
> > > > the installer I ship that relies on not-at-all guaranteed interfaces.
> > > 
> > > Although I do appreciate the importance of guaranteed interfaces,
> > > I am also pragmatic. An incompatible change in ntdll.dll would break
> > > vast amounts of programs, including cygwin. There is a lot to be said
> > > about Microsoft and their APIs, but I don't think they have a habit of
> > > changing ABIs or function semantics for userland libraries that have
> > > been around for 15 years.
> > 
> > Had you pointed to some document that states that the function has been in 
> > all NT-based versions, that would have done the trick.
> 
> Not official documentation, but at least from some MS guy it seems:
> http://www.osronline.com/showThread.cfm?link=73086 (last message).
> 
> Apparently, it was in NT3.x, but they document only what's actually
> defined in the header.

How about runtime checking? You could do GetProcAddress(...) and if you
don't get it use the old behaviour. I mean if it really is faster why
not let Users of recent systems benefit from it.

cheers Heiko

Re: Implementing stat() with FindFirstFile()

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1989 bytes --]

Hi,

On Tue, 31 Mar 2009, Heiko Voigt wrote:

> On Mon, Mar 30, 2009 at 07:11:18AM +0200, Björn Steinbrink wrote:
> > On 2009.03.30 02:52:47 +0200, Johannes Schindelin wrote:
> > > On Mon, 30 Mar 2009, Magnus Bäck wrote:
> > > > On Friday, March 27, 2009 at 03:25 CET, Johannes Schindelin 
> > > > <Johannes.Schindelin@gmx.de> wrote:
> > > > > On Thu, 26 Mar 2009, Magnus Bäck wrote:
> > > > > > I'd be very surprised if ZwQueryDirectoryFile() hasn't always 
> > > > > > been around (I just verified ntdll.dll from NT 4.0), so that's 
> > > > > > not a worry. Don't know why MSDN reports it as introduced in 
> > > > > > XP.
> > > > >
> > > > > As the current maintainer of msysGit, I refuse to have something 
> > > > > in the installer I ship that relies on not-at-all guaranteed 
> > > > > interfaces.
> > > > 
> > > > Although I do appreciate the importance of guaranteed interfaces, 
> > > > I am also pragmatic. An incompatible change in ntdll.dll would 
> > > > break vast amounts of programs, including cygwin. There is a lot 
> > > > to be said about Microsoft and their APIs, but I don't think they 
> > > > have a habit of changing ABIs or function semantics for userland 
> > > > libraries that have been around for 15 years.
> > > 
> > > Had you pointed to some document that states that the function has 
> > > been in all NT-based versions, that would have done the trick.
> > 
> > Not official documentation, but at least from some MS guy it seems: 
> > http://www.osronline.com/showThread.cfm?link=73086 (last message).
> > 
> > Apparently, it was in NT3.x, but they document only what's actually 
> > defined in the header.
> 
> How about runtime checking? You could do GetProcAddress(...) and if you 
> don't get it use the old behaviour. I mean if it really is faster why 
> not let Users of recent systems benefit from it.

While my first reaction was negative, I have to admit that thinking about 
it longer, it does seem to make a whole lot of sense.

Thanks,
Dscho

Re: Implementing stat() with FindFirstFile()

[Magnus Bäck]

On Tuesday, March 31, 2009 at 01:29 CEST,
     Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

> On Tue, 31 Mar 2009, Heiko Voigt wrote:
> 
> > On Mon, Mar 30, 2009 at 07:11:18AM +0200, Björn Steinbrink wrote:
> >
> > > Not official documentation, but at least from some MS guy it seems: 
> > > http://www.osronline.com/showThread.cfm?link=73086 (last message).
> > > 
> > > Apparently, it was in NT3.x, but they document only what's actually 
> > > defined in the header.
> > 
> > How about runtime checking? You could do GetProcAddress(...) and if
> > you don't get it use the old behaviour. I mean if it really is
> > faster why not let Users of recent systems benefit from it.
> 
> While my first reaction was negative, I have to admit that thinking
> about it longer, it does seem to make a whole lot of sense.

If anything worries me it's forward compatibility should Microsoft
change the function signature. Backwards compatibility can always
be guaranteed by using GetProcAddress(). Again, I would be very
surprised but IF it could be quite fatal.

Anyway, we don't know for sure if it's faster or if it fixes the DST
problem of FindFirstFile(). I'll write some code to try it out.

-- 
Magnus Bäck
baeck@swipnet.se

Re: Implementing stat() with FindFirstFile()

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1351 bytes --]

Hi,

On Tue, 31 Mar 2009, Magnus Bäck wrote:

> On Tuesday, March 31, 2009 at 01:29 CEST,
>      Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> 
> > On Tue, 31 Mar 2009, Heiko Voigt wrote:
> > 
> > > On Mon, Mar 30, 2009 at 07:11:18AM +0200, Björn Steinbrink wrote:
> > >
> > > > Not official documentation, but at least from some MS guy it seems: 
> > > > http://www.osronline.com/showThread.cfm?link=73086 (last message).
> > > > 
> > > > Apparently, it was in NT3.x, but they document only what's actually 
> > > > defined in the header.
> > > 
> > > How about runtime checking? You could do GetProcAddress(...) and if
> > > you don't get it use the old behaviour. I mean if it really is
> > > faster why not let Users of recent systems benefit from it.
> > 
> > While my first reaction was negative, I have to admit that thinking
> > about it longer, it does seem to make a whole lot of sense.
> 
> If anything worries me it's forward compatibility should Microsoft
> change the function signature. Backwards compatibility can always
> be guaranteed by using GetProcAddress(). Again, I would be very
> surprised but IF it could be quite fatal.
> 
> Anyway, we don't know for sure if it's faster or if it fixes the DST
> problem of FindFirstFile(). I'll write some code to try it out.

Thank you very much, I appreciate it!

Ciao,
Dscho

Re: Implementing stat() with FindFirstFile()

[Nazri Ramliy]

On Sat, Mar 21, 2009 at 11:47 PM, Magnus Bäck <baeck@swipnet.se> wrote:
> Is there any reason why compat/win32.h uses GetFileAttributesEx()
> instead of FindFirstFile() to implement the stat() call on Windows?

This blog post explains checking file existence using GetFileAttributes(Ex) vs.
FindFirstFile quite nicely:

    http://blogs.msdn.com/oldnewthing/archive/2007/10/23/5612082.aspx

nazri.