NetBSD Problem Report #60521
From www@netbsd.org Thu Jul 30 20:49:54 2026
Return-Path: <www@netbsd.org>
Received: from mail.netbsd.org (mail.netbsd.org [199.233.217.200])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256
client-signature RSA-PSS (2048 bits) client-digest SHA256)
(Client CN "mail.netbsd.org", Issuer "YR2" (not verified))
by mollari.NetBSD.org (Postfix) with ESMTPS id BF00E1A923B
for <gnats-bugs@gnats.NetBSD.org>; Thu, 30 Jul 2026 20:49:54 +0000 (UTC)
Message-Id: <20260730204952.D265F1A923C@mollari.NetBSD.org>
Date: Thu, 30 Jul 2026 20:49:52 +0000 (UTC)
From: campbell+netbsd@mumble.net
Reply-To: campbell+netbsd@mumble.net
To: gnats-bugs@NetBSD.org
Subject: dump(8): mystery of Hanoi
X-Send-Pr-Version: www-1.0
X-From4GNATS: "campbell+netbsd@mumble.net via gnats" <gnats-admin@NetBSD.org>
>Number: 60521
>Category: bin
>Synopsis: dump(8): mystery of Hanoi
>Confidential: no
>Severity: serious
>Priority: medium
>Responsible: bin-bug-people
>State: open
>Class: doc-bug
>Submitter-Id: net
>Arrival-Date: Thu Jul 30 20:50:01 +0000 2026
>Last-Modified: Sat Aug 01 14:20:02 +0000 2026
>Originator: Taylor R Campbell
>Release: current, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0.9, 4.4, 4.3, 4.2, 4.1, ...
>Organization:
Acme Hanoi Backups LLC
>Environment:
>Description:
Since 1985, the dump(8) man page has had the following
mysterious description of a `modified Tower of Hanoi
algorithm':
> In the event of a catastrophic disk event, the time required to restore
> all the necessary backup tapes or files to disk can be kept to a minimum
> by staggering the incremental dumps. An efficient method of staggering
> incremental dumps to minimize the number of tapes follows:
>
> o Always start with a level 0 backup, for example:
>
> /sbin/dump -0u -f /dev/nrst1 /usr/src
>
> This should be done at set intervals, say once a month or once
> every two months, and on a set of fresh tapes that is saved
> forever.
>
> o After a level 0, dumps of active file systems are taken on a
> daily basis, using a modified Tower of Hanoi algorithm, with
> this sequence of dump levels:
>
> 3 2 5 4 7 6 9 8 9 9 ...
>
> For the daily dumps, it should be possible to use a fixed
> number of tapes for each day, used on a weekly basis. Each
> week, a level 1 dump is taken, and the daily Hanoi sequence
> repeats beginning with 3. For weekly dumps, another fixed set
> of tapes per dumped file system is used, also on a cyclical
> basis.
https://man.NetBSD.org/NetBSD-11.x/dump.8
https://github.com/robohack/ucb-csrg-bsd/commit/0be03f2e12c4019781356ef565553ecf1c3b2bd6
(The commit message from 1985 reads `manual page distributed
with 4.1BSD', but I don't know where to continue pursuing the
provenance of this text.)
It is not obvious from this text:
(a) what goes in the ellipsis (does it keep going on as nines
indefinitely, or what?),
(b) what objectives this sequence optimizes (total number of
tapes? number of tapes needed for recovery today? average
size of dumps? average time to restore? ...),
(c) what constraints the optimization is subject to (bound on
number of tapes? bound on retention period?),
(d) how many tapes are involved and how the levels correspond
to tapes different tapes,
(e) what the algorithm actually is, or
(f) where the algorithm came from.
FreeBSD's man page still has this text:
https://man.freebsd.org/cgi/man.cgi?query=dump&apropos=0&sektion=0&manpath=FreeBSD+15.1-RELEASE&format=html
OpenBSD replaced it back in 2007 by some simpler schedules and
criteria:
https://man.openbsd.org/OpenBSD-7.8/dump.8
On review of the literature via Google Scholar search, I failed
to find essentially any discussion of these questions.
Presumably it must have been common knowledge in 1985 for the
man page to describe it as `modified' Tower of Hanoi.
The Wikipedia article (which, as of 2026-07-30, has a `needs
more citations' warning at the top, and has essentially no
reliable sources, linking only to 1. a book that doesn't
mention Tower of Hanoi, 2. a local San Francisco computer
repair shop's 2008 web page on backup recommendations, and 3. a
Birmingham consultant's business web page) describes a sequence
based on counting in binary which bears no obvious resemblance
to the dump(8) man page sequence:
https://en.wikipedia.org/w/index.php?title=Backup_rotation_scheme&oldid=1307385008
On review of BSD and TUHS mailing list archives, and after
discussion on IRC, so far it seems that:
1. nobody knows what the algorithm actually is, and
2. every discussion of it boils down to one of:
(a) I'm confused, what the heck is this?
(b) This is too complicated, you should use something
simpler!
or
(c) This is the Right Thing because [explanation that makes
no sense on scrutiny].
Examples:
https://www.tuhs.org/Usenet/comp.unix.wizards/1985-July/011477.html
https://lists.freebsd.org/pipermail/freebsd-questions/2005-August/096345.html
>How-To-Repeat:
man dump
>Fix:
Ideally, the text would answer all of the questions I posed,
and cite relevant sources in the literature.
>Audit-Trail:
From: Taylor R Campbell <riastradh@NetBSD.org>
To: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
Cc:
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Thu, 30 Jul 2026 21:53:13 +0000
Some further digging into TUHS archives reveals that the text was
previously substantially different in 2.9BSD (and essentially the same
there as in V7 Unix), explaining the binary counting algorithm that
various other sources (like Wikipedia and its references) use -- it
also more clearly distinguishes which tapes are used for which dumps
at which levels when:
> Now a short suggestion on how to
> perform dumps.
> Start with a full level 0 dump:
> .PP
> \fIdump 0u\fP
> .PP
> Next,
> periodic level 9 dumps should be made on an
> exponential progression of tapes.
> (Sometimes called Tower of Hanoi \- 1 2 1 3 1 2 1 4 ...
> tape 1 used every other time,
> tape 2 used every fourth,
> tape 3 used every eighth, etc.):
> .PP
> \fIdump 9u\fP
> .PP
> When the level 9 incremental approaches a full
> tape (about 78000 512-byte blocks at 1600 BPI blocked 20,
> or 39000 1-kilobyte blocks),
> a level 1 dump should be made:
> .PP
> \fIdump 1u\fP
> .PP
> After this,
> the exponential series should progress as uninterrupted.
> These level 9 dumps are based on the level 1 dump which
> is based on the level 0 full dump.
> This progression of levels of dump can be carried
> as far as desired.
https://www.tuhs.org/cgi-bin/utree.pl?file=3D2.9BSD/usr/man/man8/dump.8
https://www.tuhs.org/cgi-bin/utree.pl?file=3DV7/usr/man/man1/dump.1m
Then it was rewritten some time between 2.9BSD and 2.11BSD to be
substantially similar to the present text, with the mysterious
unexplained sequence, though specifying exactly 10 tapes for dailies
and 5 tapes for weeklies:
> Now a short suggestion on how to perform dumps. Start with
> a full level 0 dump
>=20
> dump 0un
>=20
> Next, dumps of active file systems are taken on a daily
> basis, using a modified Tower of Hanoi algorithm, with this
> sequence of dump levels:
> 3 2 5 4 7 6 9 8 9 9 ...
> For the daily dumps, a set of 10 tapes per dumped file sys-
> tem is used on a cyclical basis. Each week, a level 1 dump
> is taken, and the daily Hanoi sequence repeats with 3. For
> weekly dumps, a set of 5 tapes per dumped file system is
> used, also on a cyclical basis. Each month, a level 0 dump
> is taken on a set of fresh tapes that is saved forever.
https://www.tuhs.org/cgi-bin/utree.pl?file=3D2.11BSD/man/cat8/dump.0
I wonder whether the intent was the following correspondence, with the
binary counting progression of tape numbers concept obliquely
concealed in the phrase `modified Tower of Hanoi algorithm'?
day 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
level 0 3 2 5 4 7 6 9 8 9 9 9 9 9 ... (mysterious sequence)
tape 0 1 2 1 3 1 2 1 4 1 2 1 3 1 ... (Tower of Hanoi)
Or was it just the following as the plain reading of the new language
suggests?
tape 0 1 2 3 4 5 6 7 8 9 0 1 2 3 ... (dailies)
tape 0 1 2 3 4 0 1 2 3 4 0 1 2 3 ... (weeklies)
In 1991, Cael Staelin replaced the exact numbers in UCB CSRG BSD's
dump(8) man page by the vague text `a fixed number of tapes', bringing
it to essentially what it is today:
-For the daily dumps, a set of 10 tapes per dumped file system
-is used on a cyclical basis.
+.Ed
+.Pp
+For the daily dumps, it should be possible to use a fixed number of tapes
+for each day, used on a weekly basis.
Each week, a level 1 dump is taken, and
-the daily Hanoi sequence repeats with 3.
-For weekly dumps, a set of 5 tapes per dumped file system is
+the daily Hanoi sequence repeats beginning with 3.
+For weekly dumps, another fixed set of tapes per dumped file system is
used, also on a cyclical basis.
-Each month, a level 0 dump is taken
-on a set of fresh tapes that is saved forever.
https://github.com/robohack/ucb-csrg-bsd/commit/cf93f1d76d4566948c9754282a7=
28d2f86b95a39#diff-1ebf0645f1a78aa421b8ee0b6f245358b9642f87037621aaec734343=
d2768f81
From: "Jeremy C. Reed" <reed@reedmedia.net>
To: gnats-bugs@netbsd.org
Cc:
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Thu, 30 Jul 2026 22:29:56 +0000 (UTC)
> (The commit message from 1985 reads `manual page distributed
> with 4.1BSD', but I don't know where to continue pursuing the
> provenance of this text.)
Also see 7th Edition of Unix:
https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/man/man1/dump.1m
and 4BSD (rewrite of dump for new file system):
https://www.tuhs.org/cgi-bin/utree.pl?file=4BSD/usr/man/man8/dump.8
(See how the sequence changes in the docs.)
From: Taylor R Campbell <riastradh@NetBSD.org>
To: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
Cc:
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Sat, 1 Aug 2026 04:28:14 +0000
Aha! Another Google Scholar search with slightly different query
(`hanoi backup tape') turned up a document that is...actually in our
source tree already(!), namely src/share/doc/smm/01.setup (installed
at /usr/share/doc/smm/setup), or the `Installing and Operating 4.4BSD
UNIX' manual, which has this excerpt:
> Dumping of the filesystems should be done regularly,
> since once the system is going it is easy to become compla-
> cent. Complete and incremental dumps are easily done with
> dump(8). You should arrange to do a towers-of-hanoi dump
> sequence; we tune ours so that almost all files are dumped
> on two tapes and kept for at least a week in most every
> case. We take full dumps every month (and keep these indef-
> initely). Operators can execute ``dump w'' at login that
> will tell them what needs to be dumped (based on the
> /etc/fstab information). Be sure to create a group operator
> in the file /etc/group so that dump can notify logged-in
> operators when it needs help.
> More precisely, we have three sets of dump tapes: 10
> daily tapes, 5 weekly sets of 2 tapes, and fresh sets of
> three tapes monthly. We do daily dumps circularly on the
> daily tapes with sequence `3 2 5 4 7 6 9 8 9 9 9 ...'. Each
> weekly is a level 1 and the daily dump sequence level
> restarts after each weekly dump. Full dumps are level 0 and
> the daily sequence restarts after each full dump also.
> Thus a typical dump sequence would be:
>=20
> tape name level number date opr size
> ----------------------------------------------------------
> FULL 0 Nov 24, 1992 operator 137K
> D1 3 Nov 28, 1992 operator 29K
> D2 2 Nov 29, 1992 operator 34K
> D3 5 Nov 30, 1992 operator 19K
> D4 4 Dec 1, 1992 operator 22K
> W1 1 Dec 2, 1992 operator 40K
> D5 3 Dec 4, 1992 operator 15K
> D6 2 Dec 5, 1992 operator 25K
> D7 5 Dec 6, 1992 operator 15K
> D8 4 Dec 7, 1992 operator 19K
> W2 1 Dec 9, 1992 operator 118K
> D9 3 Dec 11, 1992 operator 15K
> D10 2 Dec 12, 1992 operator 26K
> D1 5 Dec 15, 1992 operator 14K
> W3 1 Dec 17, 1992 operator 71K
> D2 3 Dec 18, 1992 operator 13K
> FULL 0 Dec 22, 1992 operator 135K
>=20
> We do weekly dumps often enough that daily dumps always fit
> on one tape.
This actually lays out the correspondence between tapes, levels, and
dates, and gives some criteria it is intended to satisfy:
- almost every file is dumped on at least two different tapes, and
- almost every file is kept for at least a week.
The algorithm for dump levels on successive tapes appears to be 0 3 -1
+3 -1 +3 -1 ... (clamped at 9), which is somewhat like the naive 0 +1
+1 +1 +1 ... except that every other day, on the -1 days, we dump all
the same files as were dumped on the previous day, plus whatever else
has changed since then -- that seems to be how almost every file is
dumped on at least two different tapes...well, except for changes done
between a +3 daily and a -1 daily, which only get saved once until the
next weekly or full.
I'm also confused by the omission of various dates in this sequence.
Perhaps Nov 25,26,27 are missing because Nov 26, 1992 was
Thanksgiving, but Nov 28 was a Saturday and Nov 29 was a Sunday, so
why are they included? Then Dec 3 is missing, a non-holiday Thursday.
The sequence matches a description I found in W. Curtis Preston, _Unix
Backup and Recovery_, O'Reilly, 1999, pp. 40--42, alongside a -1 +2
sequence (which repeats some dump levels as it goes, for reasons
unclear):
> One of the goals of most backup schedules is to get changed files on
> more than one volume, while reducing total volume usage. The Tower
> of Hanoi (TOH) accomplishes this better than any other schedule. If
> you use a TOH progression for your backup levels, most changed files
> will get backed up twice---but only twice.
>=20
> Here are two different versions of the progression. (They're
> related to the number of rings on the three pegs, by the way.)
>=20
> 0 3 2 5 4 7 6 9 8 9
> 0 3 2 4 3 5 4 6 5 7 6 8 7 9 8
>=20
> The mathematical progression is actually pretty easy. It's 0 2 3 4 5
> 6 7 8 9, intermixed with 3 4 5 6 7 8 9.
https://books.google.com/books?id=3D_i1sO47qNnMC&q=3Dhanoi#v=3Dsnippet&q=3D=
hanoi&f=3Dfalse
I don't really see any resemblance to the towers of Hanoi binary
progressions that are described elsewhere like in Wikipedia, though,
where the nth tape is recycled every 2^n days, i.e., on day d starting
at 1, you overwrite tape clz(d). As a result, for n1 > n0, tape n1
gets overwritten 2^{n1 - n0} times as often as tape n0. In contrast,
the sequence documented in the SMM overwrites every tape with the same
frequency.
So the term `towers of Hanoi' seems to be being used for two
completely different classes of schedules. The binary progression
strikes me as a closer analogy: if the tapes correspond to puzzle
discs numbered by size, and if moving a disc from one peg to another
in the standard towers of Hanoi algorithm means taking a backup with
the corresponding disc, the binary progression is what you get.
It also remains unclear what dump levels the intent is for binary
progression `towers of Hanoi' rotation schemes -- if any intent can be
ascribed to this.
One possibility is that you always do a full backup, so that with n
tapes, you can always recover 1, 2, 4, ..., 2^n days ago. But is that
actually done in practice?
Another possibility is that up to level L, on day d, you overwrite
tape clz(d) with a level-(L - clz(d)) backup. With five tapes,
labelled A/B/C/D for the incrementals (treated as if numbered 0/1/2/3
for the clz correspondence) and F for the full, that would lead to the
following day/tape/level schedule, corresponding sequences of tapes
needed to restore to the latest backup at each point between backups,
and which days you can roll back to at each point between backups (if
I haven't made any mistakes, which I probably have):
day 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
tape F A B A C A B A D A B A C A B A F
level 0 4 3 4 2 4 3 4 1 4 3 4 2 4 3 4 0
recovery F F F F F F F F F F F F F F F F F
A B B C C C C D D D D D D D D
A A B B A B B C C C C
A A A B B
A
rollback 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 2 2 2 4 4 4 4 4 4 8 8 8 8
2 3 3 4 5 6 6 6 8 8 10 10 12 12
4 5 6 7 7 8 9 10 11 12 13 14
8 9 10 11 12 13 14 15
I'm not sure what criteria this optimizes either! It approximates
being able to roll back 2^k days for each k up to the limit. One
might intuitively expect that with a clever binary progression
involving n levels, you need only fetch at most lg L tapes in tape
libary to recover at any given time, but this clearly doesn't achieve
that. Maybe something involving Gray codes reduces that metric.
From: Christos Zoulas <christos@zoulas.com>
To: gnats-bugs@netbsd.org
Cc: gnats-admin@netbsd.org, netbsd-bugs@netbsd.org,
campbell+netbsd@mumble.net
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Sat, 1 Aug 2026 14:40:53 +0300
Here is what chatgpt has to say:
The Tower of Hanoi backup scheme is used with tape backups because it provid=
es a good balance between three competing goals:
- Keeping many historical backup versions.
- Using a relatively small number of tapes.
- Ensuring older backups are retained for progressively longer periods.
It is based on the same mathematical pattern as the classic Tower of Hanoi p=
uzzle.
How it works
Suppose you have five tapes labeled A=E2=80=93E.
Instead of reusing tapes in a simple rotation, each tape is used at differen=
t intervals:
Tape A: every 2 backups
Tape B: every 4 backups
Tape C: every 8 backups
Tape D: every 16 backups
Tape E: every 32 backups
For daily backups, the schedule might look like this:
Day 1: Tape A
Day 2: Tape B
Day 3: Tape A
Day 4: Tape C
Day 5: Tape A
Day 6: Tape B
Day 7: Tape A
Day 8: Tape D
Day 9: Tape A
Day 10: Tape B
Day 11: Tape A
Day 12: Tape C
Day 13: Tape A
Day 14: Tape B
Day 15: Tape A
Day 16: Tape E
Notice that:
- Tape A is overwritten frequently.
- Tape E isn't overwritten until day 32.
- Some backups naturally become long-term recovery points.
Why this is useful
Imagine someone accidentally deletes a file.
- If they notice tomorrow, yesterday's backup (Tape A) is available.
- If they notice two weeks later, Tape D may still contain the data.
- If they notice a month later, Tape E may still have it.
A simple five-tape rotation would only let you go back five days before ever=
ything had been overwritten.
Advantages
- Excellent history with few tapes.
- Automatic aging. Older backups are naturally retained longer.
- No calendar required. The schedule is purely mathematical.
- Efficient for incremental backups.
Disadvantages
- The schedule is harder to understand than daily/weekly/monthly rotations.
- Finding the newest backup before a particular date can require consulting t=
he schedule.
- It doesn't align with business reporting periods (month-end, quarter-end, y=
ear-end).
- Modern disk-based backup systems with deduplication often make this approa=
ch unnecessary.
Comparison with Grandfather-Father-Son (GFS)
Tower of Hanoi
- Mathematical schedule
- Very tape-efficient
- Automatic exponential retention
- Best when tape count is limited
Grandfather-Father-Son
- Calendar schedule
- Easier to understand
- Explicit daily/weekly/monthly backups
- Better for compliance and auditing
Is it still used?
Today it's relatively uncommon because disk-based backup appliances and clou=
d storage allow organizations to keep many recovery points without carefully=
managing physical media. However, the Tower of Hanoi scheme can still be us=
eful when:
- using physical tapes,
- tape inventory is limited,
- and long retention is desired without purchasing many additional tapes.
It remains an elegant example of using exponential spacing to maximize the a=
ge of recoverable backups while minimizing the number of tapes required.
> On Aug 1, 2026, at 7:30=E2=80=AFAM, Taylor R Campbell via gnats <gnats-adm=
in@netbsd.org> wrote:
>=20
> =EF=BB=BFThe following reply was made to PR bin/60521; it has been noted b=
y GNATS.
>=20
> From: Taylor R Campbell <riastradh@NetBSD.org>
> To: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
> Cc:
> Subject: Re: bin/60521: dump(8): mystery of Hanoi
> Date: Sat, 1 Aug 2026 04:28:14 +0000
>=20
> Aha! Another Google Scholar search with slightly different query
> (`hanoi backup tape') turned up a document that is...actually in our
> source tree already(!), namely src/share/doc/smm/01.setup (installed
> at /usr/share/doc/smm/setup), or the `Installing and Operating 4.4BSD
> UNIX' manual, which has this excerpt:
>=20
>> Dumping of the filesystems should be done regularly,
>> since once the system is going it is easy to become compla-
>> cent. Complete and incremental dumps are easily done with
>> dump(8). You should arrange to do a towers-of-hanoi dump
>> sequence; we tune ours so that almost all files are dumped
>> on two tapes and kept for at least a week in most every
>> case. We take full dumps every month (and keep these indef-
>> initely). Operators can execute ``dump w'' at login that
>> will tell them what needs to be dumped (based on the
>> /etc/fstab information). Be sure to create a group operator
>> in the file /etc/group so that dump can notify logged-in
>> operators when it needs help.
>> More precisely, we have three sets of dump tapes: 10
>> daily tapes, 5 weekly sets of 2 tapes, and fresh sets of
>> three tapes monthly. We do daily dumps circularly on the
>> daily tapes with sequence `3 2 5 4 7 6 9 8 9 9 9 ...'. Each
>> weekly is a level 1 and the daily dump sequence level
>> restarts after each weekly dump. Full dumps are level 0 and
>> the daily sequence restarts after each full dump also.
>> Thus a typical dump sequence would be:
>> =3D20
>> tape name level number date opr size
>> ----------------------------------------------------------
>> FULL 0 Nov 24, 1992 operator 137K
>> D1 3 Nov 28, 1992 operator 29K
>> D2 2 Nov 29, 1992 operator 34K
>> D3 5 Nov 30, 1992 operator 19K
>> D4 4 Dec 1, 1992 operator 22K
>> W1 1 Dec 2, 1992 operator 40K
>> D5 3 Dec 4, 1992 operator 15K
>> D6 2 Dec 5, 1992 operator 25K
>> D7 5 Dec 6, 1992 operator 15K
>> D8 4 Dec 7, 1992 operator 19K
>> W2 1 Dec 9, 1992 operator 118K
>> D9 3 Dec 11, 1992 operator 15K
>> D10 2 Dec 12, 1992 operator 26K
>> D1 5 Dec 15, 1992 operator 14K
>> W3 1 Dec 17, 1992 operator 71K
>> D2 3 Dec 18, 1992 operator 13K
>> FULL 0 Dec 22, 1992 operator 135K
>> =3D20
>> We do weekly dumps often enough that daily dumps always fit
>> on one tape.
>=20
> This actually lays out the correspondence between tapes, levels, and
> dates, and gives some criteria it is intended to satisfy:
> - almost every file is dumped on at least two different tapes, and
> - almost every file is kept for at least a week.
>=20
> The algorithm for dump levels on successive tapes appears to be 0 3 -1
> +3 -1 +3 -1 ... (clamped at 9), which is somewhat like the naive 0 +1
> +1 +1 +1 ... except that every other day, on the -1 days, we dump all
> the same files as were dumped on the previous day, plus whatever else
> has changed since then -- that seems to be how almost every file is
> dumped on at least two different tapes...well, except for changes done
> between a +3 daily and a -1 daily, which only get saved once until the
> next weekly or full.
>=20
> I'm also confused by the omission of various dates in this sequence.
> Perhaps Nov 25,26,27 are missing because Nov 26, 1992 was
> Thanksgiving, but Nov 28 was a Saturday and Nov 29 was a Sunday, so
> why are they included? Then Dec 3 is missing, a non-holiday Thursday.
>=20
> The sequence matches a description I found in W. Curtis Preston, _Unix
> Backup and Recovery_, O'Reilly, 1999, pp. 40--42, alongside a -1 +2
> sequence (which repeats some dump levels as it goes, for reasons
> unclear):
>=20
>> One of the goals of most backup schedules is to get changed files on
>> more than one volume, while reducing total volume usage. The Tower
>> of Hanoi (TOH) accomplishes this better than any other schedule. If
>> you use a TOH progression for your backup levels, most changed files
>> will get backed up twice---but only twice.
>> =3D20
>> Here are two different versions of the progression. (They're
>> related to the number of rings on the three pegs, by the way.)
>> =3D20
>> 0 3 2 5 4 7 6 9 8 9
>> 0 3 2 4 3 5 4 6 5 7 6 8 7 9 8
>> =3D20
>> The mathematical progression is actually pretty easy. It's 0 2 3 4 5
>> 6 7 8 9, intermixed with 3 4 5 6 7 8 9.
>=20
> https://books.google.com/books?id=3D3D_i1sO47qNnMC&q=3D3Dhanoi#v=3D3Dsnipp=
et&q=3D3D=3D
> hanoi&f=3D3Dfalse
>=20
> I don't really see any resemblance to the towers of Hanoi binary
> progressions that are described elsewhere like in Wikipedia, though,
> where the nth tape is recycled every 2^n days, i.e., on day d starting
> at 1, you overwrite tape clz(d). As a result, for n1 > n0, tape n1
> gets overwritten 2^{n1 - n0} times as often as tape n0. In contrast,
> the sequence documented in the SMM overwrites every tape with the same
> frequency.
>=20
> So the term `towers of Hanoi' seems to be being used for two
> completely different classes of schedules. The binary progression
> strikes me as a closer analogy: if the tapes correspond to puzzle
> discs numbered by size, and if moving a disc from one peg to another
> in the standard towers of Hanoi algorithm means taking a backup with
> the corresponding disc, the binary progression is what you get.
>=20
> It also remains unclear what dump levels the intent is for binary
> progression `towers of Hanoi' rotation schemes -- if any intent can be
> ascribed to this.
>=20
> One possibility is that you always do a full backup, so that with n
> tapes, you can always recover 1, 2, 4, ..., 2^n days ago. But is that
> actually done in practice?
>=20
> Another possibility is that up to level L, on day d, you overwrite
> tape clz(d) with a level-(L - clz(d)) backup. With five tapes,
> labelled A/B/C/D for the incrementals (treated as if numbered 0/1/2/3
> for the clz correspondence) and F for the full, that would lead to the
> following day/tape/level schedule, corresponding sequences of tapes
> needed to restore to the latest backup at each point between backups,
> and which days you can roll back to at each point between backups (if
> I haven't made any mistakes, which I probably have):
>=20
> day 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
> tape F A B A C A B A D A B A C A B A F
> level 0 4 3 4 2 4 3 4 1 4 3 4 2 4 3 4 0
> recovery F F F F F F F F F F F F F F F F F
> A B B C C C C D D D D D D D D
> A A B B A B B C C C C
> A A A B B
> A
> rollback 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 1 1 2 2 2 4 4 4 4 4 4 8 8 8 8
> 2 3 3 4 5 6 6 6 8 8 10 10 12 12
> 4 5 6 7 7 8 9 10 11 12 13 14
> 8 9 10 11 12 13 14 15
>=20
> I'm not sure what criteria this optimizes either! It approximates
> being able to roll back 2^k days for each k up to the limit. One
> might intuitively expect that with a clever binary progression
> involving n levels, you need only fetch at most lg L tapes in tape
> libary to recover at any given time, but this clearly doesn't achieve
> that. Maybe something involving Gray codes reduces that metric.
>=20
From: Taylor R Campbell <riastradh@NetBSD.org>
To: Christos Zoulas <christos@zoulas.com>
Cc: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Sat, 1 Aug 2026 12:51:51 +0000
> Date: Sat, 1 Aug 2026 14:40:53 +0300
> From: Christos Zoulas <christos@zoulas.com>
>
> Here is what chatgpt has to say:
Thanks, but this just repeats the same information I noted above about
what _other_ references say `tower of Hanoi' means, and doesn't answer
any of the questions I posed. I already spent a lot of time filtering
through LLM slop to get here; if I wanted more I could have gotten it
myself.
From: Christos Zoulas <christos@zoulas.com>
To: gnats-bugs@netbsd.org
Cc: gnats-admin@netbsd.org, netbsd-bugs@netbsd.org,
campbell+netbsd@mumble.net
Subject: Re: bin/60521: dump(8): mystery of Hanoi
Date: Sat, 1 Aug 2026 17:17:02 +0300
Sorry, I thought the answer was clear: it trades more tape scheduling comple=
xity for better data retention, tape use, and anegdotically, going through f=
ewer tapes to recover a file, which is what I recall were the reasons we wer=
e doing it in the early 80's with 6250 tapes. In the end, we were always wor=
ried about making mistakes or having bad backups, so we ended up making more=
full backups than the algorithm required. Many variables have changed now, t=
he volume of data has skyrocketed, deduplication has become very important, t=
apes are not the dominant backup media, so perhaps noting the rationale for u=
sing the algorithm is just there for historical preservation.
christos
> On Aug 1, 2026, at 3:55=E2=80=AFPM, Taylor R Campbell via gnats <gnats-adm=
in@netbsd.org> wrote:
>=20
> =EF=BB=BFThe following reply was made to PR bin/60521; it has been noted b=
y GNATS.
>=20
> From: Taylor R Campbell <riastradh@NetBSD.org>
> To: Christos Zoulas <christos@zoulas.com>
> Cc: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
> Subject: Re: bin/60521: dump(8): mystery of Hanoi
> Date: Sat, 1 Aug 2026 12:51:51 +0000
>=20
>> Date: Sat, 1 Aug 2026 14:40:53 +0300
>> From: Christos Zoulas <christos@zoulas.com>
>>=20
>> Here is what chatgpt has to say:
>=20
> Thanks, but this just repeats the same information I noted above about
> what _other_ references say `tower of Hanoi' means, and doesn't answer
> any of the questions I posed. I already spent a lot of time filtering
> through LLM slop to get here; if I wanted more I could have gotten it
> myself.
>=20
(Contact us)
$NetBSD: query-full-pr,v 1.51 2026/08/10 02:28:17 riastradh Exp $
$NetBSD: gnats_config.sh,v 1.10 2026/05/13 22:00:09 riastradh Exp $
Copyright © 1994-2026
The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.
Home