Extent of the "as-if" rule

[Sidney Cadot]

Hi all,
In a discussion with Tak-Shing Chan the question came up whether the
as-if rule can cover I/O functions. Basically, he maintains it can, and
I think it doesn't.

Consider two programs:

/*** a.c ***/
#include <stdio.h>
int main(void)
{
fopen("somefile ","rb");
return 0;
}

/*** b.c ***/
in main(void)
{
return 0;
}

Would it be legal for a compiler (through optimization), to emit the
same code for program a.c and b.c ?

I'd welcome a reference from the standard.

Best regards,

Sidney

[Keith Thompson]

Sidney Cadot <si****@jigsaw. nl> writes:
[...]

Another thing is that I think the standard's way of defining a "side
effect" (by enumeration of cases) is flawed. This is a bit like
defining mammals as "primates, whales, furry animals, ... (and so
on)", which works fine until you find a platypus.
A good example, only slightly damaged by the fact that platypuses do
have fur.
Surely, there has to be a more generic way of defining a side effect.

If the definition is too generic, it could include modifying memory
(which could be observed even if the program isn't running under a
debugger).

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Keith Thompson]

Keith Thompson <ks***@mib.or g> writes:

Da*****@cern.ch (Dan Pop) writes:

In <NL************ ********@comcas t.com> "Douglas A. Gwyn"
<DA****@null.ne t> writes:

Jack Klein wrote:
> Given your reasoning, and I see nothing to argue with, optimizing away
> the fopen() is a perfectly acceptable application of the as-if rule on
> the typical *NIX system, where opening a file leaves no trace in the
> system.

But that is *not* the way that Unix (POSIX) works!
Opening a file *does* have side effects in the environment.

But not according to the C standard (unless you can provide a
chapter and verse). Therefore, removing the fopen() call does not
affect the implementation' s conformance to the C standard (which
provides a complete list of what it considers side effects).

Side effects include "modifying a file". In a Unix filesystem, a
directory can be treated as a file; so can the physical device
containing the filesystem.

This is admittedly stretching the point.

After I posted this, I realized that a swap file or partition (if
there is one) can also be treated as a file, so modifying a variable
could conceivably "modify a file".

Intuitively, I think an fopen() call that updates a timestamp should
be considered a side effect, but modifying a non-volatile variable
shouldn't, even if it causes a write to a swap file. The trick is
figuring out how to state it.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Niklas Matthies]

On 2004-01-20 14:05, James Kuyper wrote:

Jack Klein wrote:
...

Doh! I probably knew that, although I haven't had anything running
Linux in quite a while. It's time of creation that they don't keep
separately, right?

No - seperate times are kept for the creation date, last access, and
the last modification.

The first one is not the creation date, but the last inode change date.
See `man 2 stat`.

-- Niklas Matthies

[Dan Pop]

In <ln************ @nuthaus.mib.or g> Keith Thompson <ks***@mib.or g> writes:

Da*****@cern.c h (Dan Pop) writes:

In <NL************ ********@comcas t.com> "Douglas A. Gwyn"
<DA****@null.ne t> writes:

>Jack Klein wrote:
>> Given your reasoning, and I see nothing to argue with, optimizing away
>> the fopen() is a perfectly acceptable application of the as-if rule on
>> the typical *NIX system, where opening a file leaves no trace in the
>> system.
>
>But that is *not* the way that Unix (POSIX) works!
>Opening a file *does* have side effects in the environment.

But not according to the C standard (unless you can provide a
chapter and verse). Therefore, removing the fopen() call does not
affect the implementation' s conformance to the C standard (which
provides a complete list of what it considers side effects).

Side effects include "modifying a file".

In the context of the C standard, opening a file for read access and
closing it doesn't modify its contents. The C standard blissfully
ignores any timestamping issues.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dan Pop]

In <ln************ @nuthaus.mib.or g> Keith Thompson <ks***@mib.or g> writes:

Keith Thompson <ks***@mib.or g> writes:

Da*****@cern.ch (Dan Pop) writes:

> In <NL************ ********@comcas t.com> "Douglas A. Gwyn"
> <DA****@null.ne t> writes:
> >Jack Klein wrote:
> >> Given your reasoning, and I see nothing to argue with, optimizing away
> >> the fopen() is a perfectly acceptable application of the as-if rule on
> >> the typical *NIX system, where opening a file leaves no trace in the
> >> system.
> >
> >But that is *not* the way that Unix (POSIX) works!
> >Opening a file *does* have side effects in the environment.
>
> But not according to the C standard (unless you can provide a
> chapter and verse). Therefore, removing the fopen() call does not
> affect the implementation' s conformance to the C standard (which
> provides a complete list of what it considers side effects).

Side effects include "modifying a file". In a Unix filesystem, a
directory can be treated as a file; so can the physical device
containing the filesystem.

This is admittedly stretching the point.

After I posted this, I realized that a swap file or partition (if
there is one) can also be treated as a file, so modifying a variable
could conceivably "modify a file".

A swap file or partition is not a file, in the sense of the C standard.
A program with no side effects can cause the contents of the swap file
to be changed by the mere fact that it is partly or totally swapped out.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dan Pop]

In <40************ ***@saicmodis.c om> James Kuyper <ku****@saicmod is.com> writes:

Jack Klein wrote:
...

Doh! I probably knew that, although I haven't had anything running
Linux in quite a while. It's time of creation that they don't keep
separately, right?

No - seperate times are kept for the creation date, last access, and the
last modification.

Nope, the creation date is not stored anywhere. There are three
timestamps associated to each file:

time_t st_atime; /* time of last access */
time_t st_mtime; /* time of last modification */
time_t st_ctime; /* time of last inode change */

The field st_atime is changed by file accesses, e.g. by
exec(2), mknod(2), pipe(2), utime(2) and read(2) (of more
than zero bytes). Other routines, like mmap(2), may or may
not update st_atime.

Note, in the context of this discussion, that open() doesn't change
st_atime, a genuine read() call is needed for that.

The field st_mtime is changed by file modifications, e.g.
by mknod(2), truncate(2), utime(2) and write(2) (of more
than zero bytes). Moreover, st_mtime of a directory is
changed by the creation or deletion of files in that
directory. The st_mtime field is not changed for changes
in owner, group, hard link count, or mode.

The field st_ctime is changed by writing or by setting
inode information (i.e., owner, group, link count, mode,
etc.).

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Michael Wojcik]

In article <bu********@ene ws1.newsguy.com >, Chris Torek <no****@torek.n et> writes:

Jack Klein <ja*******@spam cop.net> writes:

Given your reasoning, and I see nothing to argue with, optimizing away
the fopen() is a perfectly acceptable application of the as-if rule on
the typical *NIX system, where opening a file leaves no trace in the
system.

In article <87************ @pfaff.stanford .edu>,
Ben Pfaff <bl*@cs.stanfor d.edu> wrote:

Most Unix-like kernel, including Linux, also maintain "last
accessed" times. I don't know why you think they don't.

Moreover, if the file name corresponds to a fifo or named-pipe,
simply opening the file for reading can have an effect.

Opening a file for reading can have an effect even for regular files.
Consider a stock SysV kernel as described by Bach. A file-open
request can result in allocation of one or more in-core inodes and
so forth, and will (if successful) alter the process's file
descriptor table and so on.

These are implementation details of which a conforming program is
unaware, but they could have consequences in the environment. So
I think the original question still stands: does the as-if rule
apply to changes the program causes in the environment which are
not visible to a conforming program?

--
Michael Wojcik mi************@ microfocus.com

But I still wouldn't count out the monkey - modern novelists being as
unpredictable as they are at times. -- Marilyn J. Miller

[Michael Wojcik]

In article <be************ **************@ posting.google. com>, ro***********@y ahoo.com (Robert Wessel) writes:

The point is that the change your describing (the last accessed date)
is *not* visible to a standard C program, and an implementation could
therefore claim to be conforming even if it removed the open. I think
we'd all agree that such an implementation would have serious QoI
issues.

However, it's entirely possible to imagine an implementation where a
conforming program could indirectly detect an effect of opening a
file for reading.

For example, consider an implementation which creates a file (in the
sense of "a filesystem object which can be opened using fopen") in a
temporary area for each file a program opens. These temporary files
are named using a predictable convention. A conforming program
could potentially determine how many files it had opened by attempting
to fopen (and then immediately fclose) these temporary files and seeing
how many such fopens succeeded.

That ought to work on a Linux system with the proc filesystem mounted,
for example, though I haven't actually tried it.

Such a program would get a different result before and after the
hypothetical fopen if that fopen were not optimized away. If it were
optimized away, of course, the program would get the same result
before and after the fopen. (Unless the implementation were clever
enough to understand the operation of the count-my-open-files
function and simulate the correct result - that is, extend the as-if
behavior to cover this aspect as well.)

Such a program would not be strictly conforming, since (to be useful)
it would have to produce output that depended on unspecified behavior,
but it could be conforming, as far as I can tell.

--
Michael Wojcik mi************@ microfocus.com

Please enjoy the stereo action fully that will surprise you. -- Pizzicato Five

[Dan Pop]

In <bu*********@en ews4.newsguy.co m> mw*****@newsguy .com (Michael Wojcik) writes:

In article <bu********@ene ws1.newsguy.com >, Chris Torek <no****@torek.n et> writes:

>Jack Klein <ja*******@spam cop.net> writes:
>> Given your reasoning, and I see nothing to argue with, optimizing away
>> the fopen() is a perfectly acceptable application of the as-if rule on
>> the typical *NIX system, where opening a file leaves no trace in the
>> system.

In article <87************ @pfaff.stanford .edu>,
Ben Pfaff <bl*@cs.stanfor d.edu> wrote:

>Most Unix-like kernel, including Linux, also maintain "last
>accessed" times. I don't know why you think they don't.

Moreover, if the file name corresponds to a fifo or named-pipe,
simply opening the file for reading can have an effect.

Opening a file for reading can have an effect even for regular files.
Consider a stock SysV kernel as described by Bach. A file-open
request can result in allocation of one or more in-core inodes and
so forth, and will (if successful) alter the process's file
descriptor table and so on.

These are implementation details of which a conforming program is
unaware, but they could have consequences in the environment. So
I think the original question still stands: does the as-if rule
apply to changes the program causes in the environment which are
not visible to a conforming program?

Nope, the as-if rule is defined exclusively in terms of the C abstract
machine, where the semantics of a file are as defined in the C standard.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Douglas A. Gwyn]

Sidney Cadot wrote:

Another thing is that I think the standard's way of defining a "side
effect" (by enumeration of cases) is flawed. This is a bit like defining
mammals as "primates, whales, furry animals, ... (and so on)", which
works fine until you find a platypus.
Surely, there has to be a more generic way of defining a side effect.

The problem is, there are numerous actual side effects, not all
of which are deemed essential for conformance purposes. I
alluded to some of them (timing, code size, etc.) in my previous
posting.