bin/60521: dump(8): mystery of Hanoi

["campbell+netbsd%mumble.net@localhost via gnats" <gnats-admin%NetBSD.org@localhost>]

>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
>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.