Re: [9fans] correcting old failures, and NJ vs MA

Re: [9fans] correcting old failures, and NJ vs MA

[forsyth]

>>finally, as forsyth points out, questions of "completeness and correctness"
>>are most often self-assesment exercises. particularly correctness, when
>>designing or building something new. who's to say what the "correct"
>>behaviour of mv/rename in Plan 9 is (well, when it was being designed)?

i was really referring, slightly sarcastically, to the assessment of the `Cambridge' approach
as having such-and-such splendid characteristics as opposed to the `NJ' approach
when i might just as easily have changed the assignment of attributes to each camp,
for much the reasons that anothy suggests (if you aim for simplicity,
a closer approximation to correctness often follows, for instance).
unfortunately, it seems nothing can save us from the new camp, W3C and XML.

as regards the comment above, my prejudice is that `completeness' and
`correctness' (with respect to a specification) have meaning in
mathematics, and that places some bound on our sloppiness, even in
computing.  doing mathematics isn't purely formal, pace Hilbert, but
it isn't arbitrary either.  deciding the specification might well be
subjective, although there are often external constraints on its
choice (eg, it's usually bad for a computer-controlled train to leave
the ground, maglev systems and the like excepted, but it's expected of
computer-controlled airplanes).  having settled on a target, though, i
can make a reasonable attempt to decide whether i've hit it.

Re: [9fans] correcting old failures, and NJ vs MA

[andrey mirtchovski]

lack of internal documentation -- -10%
:)

Boyd Roberts wrote:

> #!/bin/rc
>

[snip]

Re: [9fans] correcting old failures, and NJ vs MA

[Boyd Roberts]

david presotto wrote:
> I'm happy just composing du -a, grep, sed, and `{}.

#!/bin/rc

dot=`{pwd}
incs=-I^($dot/Plan9 $dot/Include)
cpp=(pcc -I/sys/include $incs -E)
line='^#line [0-9]+ "'
mkfile=mkfile
mkdeps=mkdeps
except=$dot/Plan9/except

# refuse to deal with unecessary/replaced files/directories
fn except {
	echo $1 | grep -s -f $except && echo $1: ignored >[1=2]
}

# generate a prototype mkfile
fn mkproto {
	echo '</$objtype/mkfile'
	echo 'CC=$CC -p'
	echo 'CFLAGS='$"incs
	echo '<'$mkdeps
	echo '</sys/src/cmd/mkone'
	echo '</sys/src/cmd/mklib'
	echo '</sys/src/cmd/mksyslib'
}

# indent mkfile dependancies
fn mkindent {
	tr ' ' '
' | sed -e 's/$/ \\/' -e '2,$s/^/	/' -e '$s/ \\$//'
}

for (d in `{du | awk '{print substr($2, 3)}'}) {
	if (! except $d) @{
		cd $d
		echo $d $all >[1=2]

		rm -f $mkdeps

		all=`{ls *.c >[2] /dev/null}

		for (c in $all) {
			if (! except $d/$c) {
				o=`{basename $c .c}^'.$O'
				ofiles=($ofiles $o)
			}
		}
		
		if (! ~ $ofiles '') {
			echo 'OFILES= '$"ofiles | mkindent
			ofiles=()
		} >> $mkdeps

		for (c in $all) {
			if (! except $d/$c) {
				echo $c >[1=2]
	
				o=`{basename $c .c}^'.$O'
				hfiles=()
	
				for (h in `{$cpp $c | sed -n -e 's;'$line'(.*\.h)"$;\1;p' | sort -u}) {
					switch ($h) {
					case $d/*
						hfiles=($hfiles `{basename $h})
	
					case $dot/*
						hfiles=($hfiles $h)
					}
				}
	
				if (! ~ $hfiles '') {
					{
						echo
						echo $o': '$"hfiles | mkindent
				} >> $mkdeps

				hfiles=()
				}
			}
		}

		if (test -f $mkdeps) {
			if (! test -f $mkfile) {
				mkproto > $mkfile
			}
		}	
	}
}

Re: [9fans] correcting old failures, and NJ vs MA

[david presotto]

> presotto@closedmind.org writes:
>
> > Moving a directory doesn't fall into any of these categories, though
> > some parts of the operation do.  The move itself should be in a library
> > if it's going to be used by more than one program.
>
> Moving a directory can *NOT* be done in constant time without special
> kernel support.  Even a Version 7 style unlink/link if it allowed
> links to directories would at least allow it to be possible (though
> with additional race conditions).

Plan 9 directory moves can't be done in constant time since, at the very
least,
the name space has to first be walked to see if it can be done quickly.  The
only way to do it would be to change how mounting works in the kernel,
perhaps adopting something like Sprite's prefix matches.  That would change
the system to be something very different than it currently is, just to get
a constant
time directory move.  Perhaps a worthwhile experiment, in fact one I'ld like
to do sometime for different reasons, but the result would be a very
different
system.

I said that there were some parts of the operation that should
be done in the kernel.  Doing  the whole thing in the kernel is sub
optimal, mostly because handling all the edge conditions would
involve doing file copies, etc, things that are easier to clean up after
failure at user level..

Were you just violently agreeing with me or is this some sort of
psychology experiment?

> > As for find, this isn't rocket science.  Quit yapping and implement it
> > if you want it.
>
> Alas, while I'm interested in the design and ideas of Plan 9, I'm not
> interested in contributing to someone's commercial (non-free-software)
> project unless I get remunerated.
>
> Thomas

Your loss though you weren't the only one asking for find.
I'm happy just composing du -a, grep, sed, and `{}.

Re: [9fans] correcting old failures, and NJ vs MA

[forsyth]

>>Moving a directory can *NOT* be done in constant time without special
>>kernel support.  Even a Version 7 style unlink/link if it allowed
>>links to directories would at least allow it to be possible (though
>>with additional race conditions).

i see this rumbles on.  what i tried to point out in my video file example
(using a file not a directory but the point is the same)
is that unix doesn't do mv in constant time for either files or directories,
except in the particular case that both names point into the same physical file system.
otherwise it can only do what plan 9 does.

now, on all the out-of-the-box unix systems i looked at before
posting, of the set {/, /var, /tmp, /usr, /home} at least two were
always on different physical file systems, particularly /tmp and /usr
or /home.  i don't know why they do that when it's not necessary but
they do.  it would be worse if any possessed the chaos of automounted
NFS links i've seen on most large unix installations in the past.

i'd say all that makes it worse for the user because now i need to
understand the underlying file system topology to take advantage of the
optimisation and arguably it would be easier to understand under windows
which requires you to see all the device and partition boundaries!

Re: [9fans] correcting old failures, and NJ vs MA

[Thomas Bushnell, BSG]

viro@math.psu.edu (Alexander Viro) writes:

> I don't recall anybody complaining about the stuff find _misses_. It's
> stuff that it finds in places where it shouldn't have looked that is
> a problem.

Sure enough.  Perhaps it's clear that lots of problems are going to
happen when the semantics of a system are designed from the assumption
that it has a stable directory hierarchy, and then badda bing badda
boom, suddenly it doesn't: lots of userland stuff will break. 

 From the standpoint of designing a new system, that's not so much a
serious worry, because a new system, with no relation to Unix (unlike
Plan 9, say, or GNU) isn't going to have a big slew of utilities and
programmer assumptions that the hierarchy is static.

I'm not really so much interested in whether Plan 9 should have an
mvdir syscall or not, per se.  I'm more interested in pushing at the
design (hard!) in order to explore its strengths and weaknesses, for
more general interest, particularly with reference to a different
operating system I'm thinking about (not the Hurd) which has no
particular relation to Unix at all.

Plan 9 attracted interest because of its interesting approach to user
namespaces.  

What do people think of what I said on a different thread, about
having basically the entire structure of the hierarchy be per-user,
rather than just selected mounts?

Re: [9fans] correcting old failures, and NJ vs MA

[Thomas Bushnell, BSG]

presotto@closedmind.org writes:

> Moving a directory doesn't fall into any of these categories, though
> some parts of the operation do.  The move itself should be in a library
> if it's going to be used by more than one program.

Moving a directory can *NOT* be done in constant time without special
kernel support.  Even a Version 7 style unlink/link if it allowed
links to directories would at least allow it to be possible (though
with additional race conditions).

> As for find, this isn't rocket science.  Quit yapping and implement it
> if you want it.  

Alas, while I'm interested in the design and ideas of Plan 9, I'm not
interested in contributing to someone's commercial (non-free-software)
project unless I get remunerated.

Thomas

Re: [9fans] correcting old failures, and NJ vs MA

[Alexander Viro]

On Wed, 10 Oct 2001, Thomas Bushnell, BSG wrote:

> That's an important point that I think got lost.  For example, someone
> asks "what about find?  won't it miss stuff if you move a directory?"
> And the answer is "yes, it will--and it will miss stuff whether you
> move things with a quick syscall or with a long tedious file-by-file
> copy-and-delete."  

I don't recall anybody complaining about the stuff find _misses_. It's
stuff that it finds in places where it shouldn't have looked that is
a problem.

Let me try again: full-blow rename() makes several userland programs
simpler at the cost of many userland programs becoming much more complex
or outright broken.  It's not just the kernel complexity that goes up -
that can be done, even though result will not be nice.  It's userland
that really pays a lot and that's much harder to handle.

Symlinks are actually a nice example of the same effect.  Resulting kernel
complexity is nothing compared to complexity added to userland to prevent
symlink attacks.  Notice that correct tree-walker must reimplement a large
chunk of VFS if it's ever going to be used in the area writable to attacker.
Every time when tar(1) does open() it has to do very ugly stuff.  Example:
tar in Solaris 2.6 and GNU tar earlier than 1.12 [1] do stat() followed by
open().  Then they proceed to write the metadata from stat and data read from
file into the archive.  Think what will happen if file gets replaced with
symlink to /var/spool/mail/boss between the stat() and open() during the system
backup.  Yes, missing fstat().  But even putting fstat() there doesn't solve
the problem - we have to deal with the fact that open() on some devices
may have nontrivial side effects.  O_NDELAY removes most of them, but not
all.

Worse yet, _anything_ that does unlink("foo/bar") is open to an attack -
all "when should I follow the symlinks" logics applies only to the last
component.  And there's nothing kernel could do about that.  As the result,
anything that may be used in hostile environment has to reimplement
namei(9), doing the series of open()/fstat()/fchdir() just to walk the
friggin' path.  And you'd better have a working O_NOFOLLOW or do lstat()
first; otherwise things will get very ugly.

I wouldn't describe reimplementing namei() in a lot of basic utilities
as making the life easier for userland. YMMV.

[1] BTW, it's not just GNU or Sun being sloppy - that would be business
as usual, sad as it is.  OpenBSD pax(1) is vulnerable to exactly that
attack - there is a window between stat() and open() that can be used
to replace the file you own with a symlink to a file you should be
unable to read.  And yes, it _is_ exploitable.  Attack would take a
while, but potential results of getting a look at the contents of
right mailbox may be more than worth attacker's time and efforts.

Re: [9fans] correcting old failures, and NJ vs MA

[presotto]

[-- Attachment #1: Type: text/plain, Size: 2229 bytes --]

Composing the viewpoints I've seen:

>But Plan 9 has been advertised as a superior alternative to the
>usual developer's interactive computing environment.  A good Web
>browser is another essential tool, these days.  Why should one
>be forced to buy a second computer to do something that ought to
>be right up the alley of the first one?

and

>People have noted (quite rightly) that the kernel code for moving
>directories is tricky and easy to get wrong and complex.  But what
>they haven't noted is that the user-space solution is even more tricky
>(if you expect it to solve the same problems), and even easier to get
>wrong, and even more complex.

...I guess we should write a web browser and stick it in the
kernel.

We are indeed driven by kernel simplicity more than anything else
because it has to survive a more varied load than individual commands.
A failure of the kernel is deadly to everything on the system.  It also
has the most persistent state of any part of the system so that leaks
and stray memory references that wouldn't bother a program tend to
eventually bring the kernel down.  Because of that, we try to put
things in kernel only if they significantly improve performance, are needed
to enforce some policy, or just can't be done outside the kernel.
Moving a directory doesn't fall into any of these categories, though
some parts of the operation do.  The move itself should be in a library
if it's going to be used by more than one program.

I find moving directories often useful, though orders of magnitude less
so than compiling, reading mail, buying wrenches on the web, ...
Making moving directories fast and convenient is as useful as
doing the same for rearranging furniture.  The current mv does let
you move directories and doesn't do it any less correctly than
the kernel could. I've spent more time reading the messages about
moving directories here than I ever would have saved by
had they been implemented.

As for find, this isn't rocket science.  Quit yapping and implement it
if you want it.  To be safe from graph cycles, you can keep 
track of qids of directories or, if you're lazy, use fd2path and give
up when the tree gets too deep.

[-- Attachment #2: Type: message/rfc822, Size: 2024 bytes --]

From: Boyd Roberts <boyd@strakt.com>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] correcting old failures, and NJ vs MA
Date: Wed, 10 Oct 2001 11:16:10 +0200
Message-ID: <3BC411DA.3B191015@strakt.com>

"Thomas Bushnell, BSG" wrote:
> People have noted (quite rightly) that the kernel code for moving
> directories is tricky and easy to get wrong and complex.  But what
> they haven't noted is that the user-space solution is even more tricky
> (if you expect it to solve the same problems), and even easier to get
> wrong, and even more complex.

A user mode bug won't crash the machine.

Re: [9fans] correcting old failures, and NJ vs MA

[Boyd Roberts]

"Thomas Bushnell, BSG" wrote:
> People have noted (quite rightly) that the kernel code for moving
> directories is tricky and easy to get wrong and complex.  But what
> they haven't noted is that the user-space solution is even more tricky
> (if you expect it to solve the same problems), and even easier to get
> wrong, and even more complex.

A user mode bug won't crash the machine.

Re: [9fans] correcting old failures, and NJ vs MA

[Thomas Bushnell, BSG]

I don't have much to respond to anothy's discussion of rpg's article
which I alluded too, except to say that rpg himself has changed his
mind over and over about exactly what's going on, so I don't think
he's an idiot. :)

But one thing caught my eye particularly

anothy@cosym.net writes:

> as a fundamental design principle (for new things - this is obviously
> different if you're porting, rewriting, or emulating something) causes one
> to ignore these tradeoffs in favor of whatever pre-concieved notions one
> has about how something should work. this leads to systems or apps that
> sacrifice one or more of the other three design goals - most often
> simplicity - in favor of some ill-concieved notion of "correctness", which
> quite likely a different notion of "correctness" than others have.

By correctness I meant that plan 9 *does* have a way to move directory
trees, of course, it's just slow and tedious and fails more often than
the other way.

That's an important point that I think got lost.  For example, someone
asks "what about find?  won't it miss stuff if you move a directory?"
And the answer is "yes, it will--and it will miss stuff whether you
move things with a quick syscall or with a long tedious file-by-file
copy-and-delete."  

That's why I alluded to rpg: he suggests that the NJ way prefers
simplicity of *kernel* and kernel interfaces, even if it makes the
total way to get something done more complex.

People have noted (quite rightly) that the kernel code for moving
directories is tricky and easy to get wrong and complex.  But what
they haven't noted is that the user-space solution is even more tricky
(if you expect it to solve the same problems), and even easier to get
wrong, and even more complex.

Thomas

Re: [9fans] correcting old failures, and NJ vs MA

[bwc]

I'm amazed at how long the ``ITS is better than CTSS'' debate can survive.

Would we be having this thread if undergrads at MIT were allowed more access
to CTSS accounts?

  Brantley

[9fans] correcting old failures, and NJ vs MA

[anothy]

// I'm not expert in Plan 9, but it seems to me that it [plan 9's rename
// behaviour] breaks it for the user.

i believe viro was talking specifically about the fact that changing this
awkward behaviour in Unix would break a bunch of user-level code
and user-created scripts, whereas in Plan 9 no user-level code or
user-created scripts existed to break yet. thus, when designing Plan 9,
the simpler approach to mv/rename was taken.

the remainder of this post is a bit of a rant. skip it if you're short on time.

// Is this just an example of the "New Jersey" preference for simplicity
// of implementation over the "Cambridge" preference for correctness
// and completeness?

the first time i was exposed to this distinction was in an appendix to "the
Unix-haters Handbook", appendix C, an article called "The Rise of Worse
is Better", by Richard P. Gabriel. the delibrate mis-representation of Unix
(and, by extention, Plan 9 and Inferno) design principles, and thus the
false distinction and conclusions, continually annoy me. here's why.

Gabriel characterized "the MIT/Stanford style of design" in four points
(taken from the above-mentioned source):

	• Simplicity - the design must be simple, both in implementation and
	interface. It is more important for the interface to be simple than that
	the implementation be simple.
	• Correctness - the design must be correct in all observable aspects.
	Incorrectness is simple not allowed.
	• Consistency - the design must not be inconsistent. A design is
	allowed to be slightly less simple and less complete to avoid
	inconsistency. Consistency is as important as correctness.
	• Completeness - the design must cover as many important situations
	as is practical. All reasonably expected cases must be covered.
	Simplicity is not allowed to overly reduce completeness.

Gabriel asserts that, for MIT/Stanford style programmers, all of these points
must be met. failure to meet any one is unacceptable (nevermind that he
contradicts that in the "Consistency" point, ironically). Gabriel contrasts this
with "the New Jersey approach" in the following ways (paraphrased for
simplicity and brevity):

	• Simplicity - it is more imporant for the implementation to be simple
	than the interface. simplicity is the most imporant design element.
	• Correctness - things still need to be correct, but it's slightly better to
	be simple than correct.
	• Consistency - can be sacrificed for simplicity, but it's better to drop
	completeness to save both consistency and simplicity
	• Completeness - the design must be as complete as is practical, but
	this can be sacrificed for any above quality, particularly simplicity. of
	particularly low value is consistancy of interface.

Gabriel is, however, an idiot (at least here).

first of all, the example he cites to show this difference uses a "famous
person" from Berkeley as an example of the NJ approach. problem one, as,
in my opinion, Berkeley mostly just missed the point. he then goes on to
talk about the difference between the MIT and "NJ" (really Berkeley)
approach to a specific problem ("PC losering" in Unix and ITS).

Gabriel is correct, in my opinion, that the NJ approach takes simplicity to be
the most important design constraint. Gabriel, however, sees this as in
conflict with the other three listed goals, whereas i believe the NJ approach
uses simplicity to achieve the other goals.

take windowing systems as an example. MIT produced X Windows, NJ
produced /dev/draw and rio. the NJ approach focuses on simplicity, and in
particular, simplicity and consistancy of interfaces. as a result, upon
designing the graphics system around 9P (a simple protocol consistantly
used to interface to the entire system), you get networked, remote displays
for free. focusing on simplicity (and consistancy of interace) helps achieve
the other goals in a much better manner. MIT, by contrast, focused, i think,
primarialy on completeness and correctness, and the result was a
complicated, often incorrect, inconsistant, and incomplete system.

it's worth noting that the same simple, consistant interface that made that
possible for Plan 9 gave us networked file systems that are more complete,
more correct, more consistant, and far simpler than NFS or SMB. look at
all the crap the X folks introduce to do things like remote audio.

finally, as forsyth points out, questions of "completeness and correctness"
are most often self-assesment exercises. particularly correctness, when
designing or building something new. who's to say what the "correct"
behaviour of mv/rename in Plan 9 is (well, when it was being designed)?
different definitions of "correct" carry different costs. having "correctness"
as a fundamental design principle (for new things - this is obviously
different if you're porting, rewriting, or emulating something) causes one
to ignore these tradeoffs in favor of whatever pre-concieved notions one
has about how something should work. this leads to systems or apps that
sacrifice one or more of the other three design goals - most often
simplicity - in favor of some ill-concieved notion of "correctness", which
quite likely a different notion of "correctness" than others have.

okay, rant off.
-α.