Re: [TUHS] [SPAM] Re: SCCS

Re: [TUHS] [SPAM] Re: SCCS

[Norman Wilson]

Peter Jeremy:

> NFS ran much faster when you turned off the UDP checksums as well.
> (Though there was still the Ethernet CRC32).

Dave Horsfall:

  Blerk...  That just tells you that the packet came across the wire more or
  less OK.

=====

UDP (and TCP) checksums are nearly useless against
the sort of corruption Larry described.  Since they
are a simple addition with carry wraparound, you
can insert or remove any number of word-aligned pairs
of zero octets without the checksum changing.

I discovered this the hard way, while tracking down
a kernel bug that caused exactly that sort of corruption.

Does IPv6 require a meaningful checksum, or just the
useless old ritual one?

Norman Wilson
Toronto ON

Re: [TUHS] [SPAM] Re: SCCS

[Dave Horsfall]

On Fri, 13 Sep 2019, Norman Wilson wrote:

> UDP (and TCP) checksums are nearly useless against the sort of 
> corruption Larry described.  Since they are a simple addition with carry 
> wraparound, you can insert or remove any number of word-aligned pairs of 
> zero octets without the checksum changing.

I was thinking of an intermediate router (probably one that you never knew 
about) corrupting the checksum-less UDP packet, recalculating the Ethernet 
checksum, and your kernel happily accepting it; you now have an 
application that fails for some unknown reason.

Never seen it in practice, but I've heard of it happening.

-- Dave

Re: [TUHS] [SPAM] Re: SCCS

[Tony Finch]

Dave Horsfall <dave@horsfall.org> wrote:
>
> I was thinking of an intermediate router (probably one that you never knew
> about) corrupting the checksum-less UDP packet, recalculating the Ethernet
> checksum, and your kernel happily accepting it; you now have an application
> that fails for some unknown reason.
>
> Never seen it in practice, but I've heard of it happening.

This paper has some examples:

http://conferences.sigcomm.org/sigcomm/2000/conf/paper/sigcomm2000-9-1.pdf

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
Forth, Tyne, West Dogger: Westerly 3 to 5 veering northwesterly 4 to 6. Slight
or moderate, becoming moderate or rough except in west Forth. Mainly fair.
Good.

Re: [TUHS] [SPAM] Re: SCCS

[Leah Neukirchen]

Norman Wilson <norman@oclsc.org> writes:

> Does IPv6 require a meaningful checksum, or just the
> useless old ritual one?

IPv6 has no checksum at all (for the header), and TCPv6 uses the same
checksum algorithm.

-- 
Leah Neukirchen  <leah@vuxu.org>  https://leahneukirchen.org/

Re: [TUHS] [SPAM] Re: SCCS

[Dave Horsfall]

On Mon, 16 Sep 2019, Leah Neukirchen wrote:

> IPv6 has no checksum at all (for the header), and TCPv6 uses the same 
> checksum algorithm.

Every time I've tried to read the IPv6 spec my eyes glazed over; it was 
plainly designed by a committee i.e. everybody wanted their mark on it.

-- Dave

Re: [TUHS] [SPAM] Re: SCCS

[George Michaelson]

Third mistake ever was host-only fragmentation and re-assembly. The
lack of pragmatism tells here, because it means intermediate systems
have no choice but to drop.

Second biggest mistake was keeping the order SRC, DST when if the DST
is first you can latch it into a buffer and do forwarding decisions
while the rest of the packet is in processing.

First biggest mistake was ignoring TUBA.

-G

On Tue, Sep 17, 2019 at 7:46 AM Dave Horsfall <dave@horsfall.org> wrote:
>
> On Mon, 16 Sep 2019, Leah Neukirchen wrote:
>
> > IPv6 has no checksum at all (for the header), and TCPv6 uses the same
> > checksum algorithm.
>
> Every time I've tried to read the IPv6 spec my eyes glazed over; it was
> plainly designed by a committee i.e. everybody wanted their mark on it.
>
> -- Dave

Re: [TUHS] [SPAM] Re: SCCS

[Larry McVoy]

On Sat, Sep 14, 2019 at 01:03:12AM +0200, Steffen Nurpmeso wrote:
> He is as convinced from SCCS and its interleaved deltas as you
> are, but he works on extending the plain original SCCS, which is
> pretty smaller; his presentation from the "Chemnitzer Linux Tage
> 2012" (linux days of former Karl-Marx-Stadt) [1] talks about this
> and also prominently mentions BitKeeper:
> 
>   . All modern distributed OSS version control systems base upon
>     BitKeeper in the end.

Sort of.  Monotone, Darcs, and one other one I can't remember did not
draw from BitKeeper.  Mercurial, Git, and the Australian one that I
can't remember definitely do.

>   . BitKeeper bases upon the ideas of TeamWare.

Only in that I am the primary author of both.  It does support the idea
that SCCS is the basis for both, though Teamware used the real SCCS and
I rewrote SCCS from scratch and then extended it quite a bit.  BitKeeper's
SCCS tracks a lot more than SCCS does, pathnames, permissions, hostnames,
etc.

>   . TeamWare bases upon the ideas of NSE.

That's absolutely false.  TeamWare, which is the productized version
of NSElite, which I wrote all of, was a reaction to how absolute shiite
NSE was.  I had friends in the Sun kernel group that quit because they
were forced to use NSE.  It was awful.  I got into source management 
because I was well known at Sun as the guy that could fix performance
problems so I was asked to look at NSE.  One look told me that I couldn't
fix NSE but the source management problem space needed some help.

>   . NSE is a frontend to SCCS.

That's true.

>   . Therewith all modern systems ultimately base upon SCCS.

That is a big stretch, it's just not true.  I love the SCCS file 
format but to say all modern systems are based on SCCS is 100%
false.  BitKeeper is.  That's it.

>   . Distributed operate TeamWare, BitKeeper, git, Mercurial.

Git and Mercurial were going for append only data structures. 
That's not SCCS.

All this comes from Jorg, isn't he the guy who has a track record of
being on the outside of Sun and trying to argue with me about what Sun
was doing when I was a well known guy in the most important group at Sun,
the kernel group.  If so, I'd salt his stuff heavily.

I think he means well but is a little out there.  Though some people
might say the same about me.

--lm

Re: [TUHS] [SPAM] Re: SCCS

[Dave Horsfall]

On Fri, 13 Sep 2019, Peter Jeremy wrote:

>> Giggle...  I found I could actually *edit* an SCCS file, provided I reset
>> the checksum to zero (it was then recalculated).
>
> I think that was deliberate.  ISTR editing SCCS files and repairing the
> checksum as well, though I don't recally exactly how.

I don't recall why I had to edit the SCCS file (this was decades ago) but
it was just a plain ASCII file, with the checksum as a string of digits
up near the front somewhere.

It *may* be because I screwed up an update, and didn't want to own up to
it :-)  I don't recall whether SCCS allowed updates to be backed out.

>> I believe that NFS is much more reliable now (yes, it used to be awful).
>
> NFS ran much faster when you turned off the UDP checksums as well.
> (Though there was still the Ethernet CRC32).

Blerk...  That just tells you that the packet came across the wire more or
less OK.

-- Dave

Re: [TUHS] [SPAM] Re: SCCS

[Larry McVoy]

On Fri, Sep 13, 2019 at 06:00:09PM +1000, Peter Jeremy wrote:
> On 2019-Sep-13 15:54:32 +1000, Dave Horsfall <dave@horsfall.org> wrote:
> >On Thu, 12 Sep 2019, Larry McVoy wrote:
> >> But here is an SCCS win.  SCCS has a 16 bit ignore the carry bit 
> >> checksum over the whole file.  RCS has none of that.
> >
> >Giggle...  I found I could actually *edit* an SCCS file, provided I reset 
> >the checksum to zero (it was then recalculated).
> 
> I think that was deliberate.  ISTR editing SCCS files and repairing the
> checksum as well, though I don't recally exactly how.

bk admin -z file.c

and I'm pretty sure that is sccs compat.

> >> B) NFS errors.  So all NFS implementations, Suns included, had a bad 
> >> habit of returning a block of nulls.  I dunno why but that is a thing. 
> >> The SCCS checksum would detect that.  RCS and CVS did not have a 
> >> checksum so when NFS returned garbage, they were happy to return that to 
> >> you.
> >
> >I believe that NFS is much more reliable now (yes, it used to be awful).
> 
> NFS ran much faster when you turned off the UDP checksums as well.
> (Though there was still the Ethernet CRC32).

Living dangerously.

Re: [TUHS] [SPAM] Re: SCCS

[Peter Jeremy]

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

On 2019-Sep-13 15:54:32 +1000, Dave Horsfall <dave@horsfall.org> wrote:
>On Thu, 12 Sep 2019, Larry McVoy wrote:
>> But here is an SCCS win.  SCCS has a 16 bit ignore the carry bit 
>> checksum over the whole file.  RCS has none of that.
>
>Giggle...  I found I could actually *edit* an SCCS file, provided I reset 
>the checksum to zero (it was then recalculated).

I think that was deliberate.  ISTR editing SCCS files and repairing the
checksum as well, though I don't recally exactly how.

>> B) NFS errors.  So all NFS implementations, Suns included, had a bad 
>> habit of returning a block of nulls.  I dunno why but that is a thing. 
>> The SCCS checksum would detect that.  RCS and CVS did not have a 
>> checksum so when NFS returned garbage, they were happy to return that to 
>> you.
>
>I believe that NFS is much more reliable now (yes, it used to be awful).

NFS ran much faster when you turned off the UDP checksums as well.
(Though there was still the Ethernet CRC32).

-- 
Peter Jeremy

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 963 bytes --]

Re: [TUHS] [SPAM] Re: SCCS

[Dave Horsfall]

On Thu, 12 Sep 2019, Larry McVoy wrote:

> But here is an SCCS win.  SCCS has a 16 bit ignore the carry bit 
> checksum over the whole file.  RCS has none of that.

Giggle...  I found I could actually *edit* an SCCS file, provided I reset 
the checksum to zero (it was then recalculated).

> B) NFS errors.  So all NFS implementations, Suns included, had a bad 
> habit of returning a block of nulls.  I dunno why but that is a thing. 
> The SCCS checksum would detect that.  RCS and CVS did not have a 
> checksum so when NFS returned garbage, they were happy to return that to 
> you.

I believe that NFS is much more reliable now (yes, it used to be awful).

-- Dave

Re: [TUHS] [SPAM] Re: SCCS

[Larry McVoy]

On Thu, Sep 12, 2019 at 02:44:45PM +0100, Tony Finch wrote:
> Larry McVoy <lm@mcvoy.com> wrote:
> 
> > If you have actual data that shows RCS to be faster I would like to
> > see that.  RCS read the whole file.  It could have been faster, it could
> > have put the offset into the file where the most recent version begain.
> > But it didn't.  It read the entire file.
> 
> In RCS the most recent version of the file is near the start of the ,v
> file after a list of revisions, so it doesn't have to read the deltas for
> the common case of checking out the current version of a file. I think
> there must be a similar optimization to copy the deltas without processing
> them when committing a new revision. But yes, as soon as you get away from
> working on the latest revision of the main branch, RCS becomes
> quadratically slow.

Yeah, you are right. The most recent version should be fast.  SCCS reads
the whole file and RCS does not in the common case.

But here is an SCCS win.  SCCS has a 16 bit ignore the carry bit checksum
over the whole file.  RCS has none of that.

You can argue that a 16 bit checksum is not good enough in this day of
md5sums, sha1 hashes, crcs, etc.

There are two places where it is great.

A) Memory errors.  Memory chips errors are none, parity, or ECC.
Parity has gone the way of the doodoo bird so we have none or ECC.  I can
pretty much promise you that the machine you are reading this on has no
error detection or correction.  Only high end servers have ECC.

That SCCS checksum is awesome because we can print out what the checksum
should be and what we got.  If it differs in a power of two then it is
a single bit error and that is your memory sucks.  I can't tell you how
many times customers said something was wrong and I made them run a 
memory check and it was their memory.  100's is too small, 1000's 
at least.

B) NFS errors.  So all NFS implementations, Suns included, had a bad
habit of returning a block of nulls.  I dunno why but that is a thing.
The SCCS checksum would detect that.  RCS and CVS did not have a checksum
so when NFS returned garbage, they were happy to return that to you.

It's really surprising how well the SCCS checksum has worked.  When we
went to a binary format we did CRC on each block and XOR so we could
put stuff back together.  I still have a lot of respect for that little
checksum.  It served us well.

--lm

Re: [TUHS] [SPAM] Re: SCCS

[Tony Finch]

Larry McVoy <lm@mcvoy.com> wrote:

> If you have actual data that shows RCS to be faster I would like to
> see that.  RCS read the whole file.  It could have been faster, it could
> have put the offset into the file where the most recent version begain.
> But it didn't.  It read the entire file.

In RCS the most recent version of the file is near the start of the ,v
file after a list of revisions, so it doesn't have to read the deltas for
the common case of checking out the current version of a file. I think
there must be a similar optimization to copy the deltas without processing
them when committing a new revision. But yes, as soon as you get away from
working on the latest revision of the main branch, RCS becomes
quadratically slow.

A few years ago I converted a decades-old SCCS working tree to git.
Because there are very good tools for converting from CVS to git, I
decided to convert SCCS to RCS (which is mostly a trivial file-at-a-time
format conversion, in the absence of branches and tags) to CVS (which is
just moving the RCS files to the right place) to git.

The most annoying part of this was the accidentally quadratic process of
dealing with all the old revisions in RCS files. I could mostly avoid
slowness if I arranged never to check out old revisions, aiming to treat
RCS as append-only until the final cvs-fast-export stage. This kept things
acceptably fast (closer to linear in the size of the file rather than
quadratic) even for that one very large frequently updated file.

Detailed write-up at https://fanf.dreamwidth.org/105694.html
(I subsequently re-used a lot of the machinery for converting another
much smaller SCCS repository. It was a lot easier the second time!)

[ PS. https://accidentallyquadratic.tumblr.com is great ]

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
Lough Foyle to Carlingford Lough: Southwesterly at first in southeast,
otherwise westerly or northwesterly 4 or 5, occasionally 6 at first. Moderate
or rough in north, otherwise slight or moderate, becoming smooth or slight in
east. Rain at first. Moderate or poor, becoming good.

Re: [TUHS] [SPAM] Re: SCCS

[Larry McVoy]

If you have actual data that shows RCS to be faster I would like to
see that.  RCS read the whole file.  It could have been faster, it could
have put the offset into the file where the most recent version begain.
But it didn't.  It read the entire file.

RCS was not faster and I am happy to go get the code and prove that.

"because running forward edits on a base state of 1000 edits is slow."

means you don't get how SCCS works.  

On Thu, Sep 12, 2019 at 11:20:08AM +0700, George Michaelson wrote:
> If you want to be trendy, call this an event stream, and say its
> eventually consistent.
> 
> What Larry and the other RCS haters forget is that back in the day,
> when we all had more hair, RCS was --->FAST<--- and SCCS was S.L.O.W.
> 
> because running forward edits on a base state of 1000 edits is slow.
> Since the majority action is increment +1 on the head state the RCS
> model, whilst broken in many ways
> was FAST
> 
> -G
> 
> On Thu, Sep 12, 2019 at 10:44 AM Larry McVoy <lm@mcvoy.com> wrote:
> >
> > On Thu, Sep 12, 2019 at 08:49:35AM +1000, Dave Horsfall wrote:
> > > On Wed, 11 Sep 2019, Larry McVoy wrote:
> > >
> > > >SCCS is awesome, I'll post why in a different thread.  It is light years
> > > >better than RCS, Tichy lied.
> > >
> > > Agreed; I used it for years, then was forced to use RCS in my next job :-(
> >
> > Marc Rochkind is on the list, I believe I invited him, but he can spell
> > check what I'm about to say.
> >
> > SCCS is awesome.  People have no idea how good it is as a version control
> > system because Walter Tichy got his PhD for writing RCS and claiming it
> > was better (don't get me started on how wrong that was).
> >
> > Let me start with how RCS works.  You all know about diff and patch,
> > someone does a diff, produces a patch, and Larry Wall wrote patch(1)
> > that takes the patch and file and applies it.  In a straight line
> > history here is how RCS works.  The most recent version of the file
> > is stored in whole, the delta behind that is a reverse patch to get
> > to that, same for the next delta behind that and so on.
> >
> > Branches in RCS are forward patches.  Sort of.  You start with the
> > whole file that is the most recent version, reverse patch your way
> > back to the branch point, and then forward patch your way down to
> > the most recent version on the branch.
> >
> > Yeah, branches in RCS suck, very expensive.
> >
> > So why is SCCS awesome?  It is an entirely different approach.
> > SCCS is a set based system, for any version, there is a set
> > of deltas that are in that version and you apply them to the
> > file part of the data.
> >
> > Huh?  What does that mean?  OK, you've all seen SCCS revisions, 1.1,
> > 1.2, 1.3, 1.3.1.1, etc.  Yeah, that's for humans (and truth be told those
> > revs are not that great).  For SCCS internally there are serial numbers.
> > All those are are a monotonically increasing number, doesn't matter
> > if you are on the trunk or on a branch, each time you add a delta the
> > internal number, or serial, is the last serial plus 1.
> >
> > When you go to check out a version of the file, that's the set.
> > It's the set of serials that make up that file.  If you wanted
> > 1.3 and there are no branches, the set is the serial of 1.3 (3)
> > and the parent of 1.3 which is 1.2 (2) and 1.1 (1).  So your set
> > is 1,2,3.
> >
> > Here is the awesome part.  The way the data is stored in SCCS
> > is nothing like patches, it's what we call a weave.  All versions
> > of the file are woven together in the following way.  There are
> > 3 operators:
> >
> > insert: ^AI <serial>
> > delete: ^AD <serial>
> > end: ^AE <serial>
> >
> > So if you checked in a file that looked like
> >
> > I
> > love
> > TUHS
> >
> > The weave would be
> >
> > ^AI 1
> > I
> > love
> > TUHS
> > ^AE 1
> >
> > Lets say that Clem changed that to
> >
> > I
> > really
> > love
> > TUHS
> >
> > The new weave would look like:
> >
> > ^AI 1
> > I
> > ^AI 2
> > really
> > ^AE 2
> > love
> > TUHS
> > ^AE 1
> >
> > and if I changed it to
> >
> > I
> > *really*
> > love
> > TUHS
> >
> > the weave looks like
> >
> > ^AI 1
> > I
> > ^AD 3
> > ^AI 2
> > really
> > ^AE 2
> > ^AE 3
> > ^AI 3
> > *really*
> > ^AE 3
> > love
> > TUHS
> > ^AE 1
> >
> > So a checkout is 2 things, build up the set of serials that need to be
> > active for this checkout, and walk the weave.  For each serial you see
> > you are either in this set and I need to do what it says, or this is
> > not in my set and I need to do the opposite of what it says.
> >
> > So that is really really fast compared to RCS.  RCS reads the whole
> > file and has to do compute, SCCS reads the whole file and does a
> > very tiny fraction of that compute, so tiny that you can't measure
> > it compared to reading the file.
> >
> > But wait, it gets better, much better.  Lets talk about branches
> > and merges.  RCS is copy by value across a merge, SCCS is copy by
> > reference.  Marc thought about the set stuff enough to realize
> > wouldn't be cool if you could manipulate the set.  He added include
> > and exclude operators.
> >
> > Imagine if you and I were having an argument about some video being
> > checked in.  You checked it in, I deleted it, you checked it in, I deleted
> > it.  Suppose that was a 1GB video.  In RCS, each time we argued that is
> > another GB, we did that 4 times, there 4GB of diffs in the history.
> >
> > In SCCS, you could do that with includes and excludes, those 4 times
> > would be about 30 bytes because all they are doing is saying "In the
> > set", "Not in the set".
> >
> > Cool I guess but what is the real life win?  Merges.  In a weave based
> > system like SCCS you can add 1GB on a branch and I can merge that onto
> > the trunk and all I did was say "include your serials".  I didn't copy
> > your work, I referenced it.  Tiny meta data to do so.
> >
> > That has more implications than you might think.  Think annotations.
> > git blame, know that?  It shows who did what?  Yeah, well git is
> > copy by value just like RCS.  It's not just about the space used,
> > it is also about who did what.  If bwk did one thing and dmr did
> > another thing and little old lm merged dmr's stuff into the bwk
> > trunk, in a copy by value system, all of dmr's work will look like
> > I wrote it in bwk's trunk.
> >
> > SCCS avoids that.  If I merged dmr's work into bwk's tree, if it
> > all automerged, annotations would show it all as dmr's work, yeah,
> > I did the merge but I didn't do anything so I don't show up in
> > annotations.  If there was a conflict and I had to resolve that
> > conflict, then that, and that alone, would show up as my work.
> >
> > For Marc, I worked with Rick Smith, he found me after I had done a
> > reimplentation of SCCS.  He has forgotten more about weaves than I will
> > ever know.  But he was really impressed with my code (which you can
> > go see at bitkeeper.org, and it is not my code, it is my teams code,
> > Rick bugfixed all my mistakes) because I embraced the set thing and the
> > way I wrote the code you could have N of my data structures and pulled
> > out N versions of the file in one pass.  He had not seen that before,
> > to me it just seemed the most natural way to do it.
> >
> > SCCS is awesome, Marc should be held up as a hero for that.  Most people
> > have no idea how much better it is as a format, to this day people still
> > do it wrong.  The hg people at facebook sort of got it, they did an
> > import of SCCS (it was BitKeeper which is SCCS on super steriods).
> > But it is rare that someone gets it.  I wanted Marc to know we got it.
> >
> > --lm

-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm