written primarily in python with a bit of C code in speed-sensitive places.
Here are the most important things to know:
- - bup (symlinked to main.py) is the main program that runs when you type
- 'bup'.
-
- - cmd/bup-* (mostly symlinked to cmd/*-cmd.py) are the individual
- subcommands, in a way similar to how git breaks all its subcommands into
- separate programs. Not all the programs have to be written in python;
- they could be in any language, as long as they end up named cmd/bup-*.
- We might end up re-coding large parts of bup in C eventually so that it
- can be even faster and (perhaps) more portable.
-
- - lib/bup/*.py are python library files used by the cmd/*.py commands.
+ - The main program is a fairly small C program that mostly just
+ initializes the correct Python interpreter and then runs
+ bup.main.main(). This arrangement was chosen in order to give us
+ more flexibility. For example:
+
+ - It allows us to avoid
+ [crashing on some Unicode-unfriendly command line arguments](https://bugs.python.org/issue35883)
+ which is critical, given that paths can be arbitrary byte
+ sequences.
+
+ - It allows more flexibility in dealing with upstream changes
+ like the breakage of our ability to manipulate the
+ processes arguement list on platforms that support it during
+ the Python 3.9 series.
+
+ - It means that we'll no longer be affected by any changes to the
+ `#!/...` path, i.e. if `/usr/bin/python`, or
+ `/usr/bin/python3`, or whatever we'd previously selected during
+ `./configure` were to change from 2 to 3, or 3.5 to 3.20.
+
+ The version of python bup uses is determined by the `python-config`
+ program selected by `./configure`. It tries to find a suitable
+ default unless `BUP_PYTHON_CONFIG` is set in the environment.
+
+ - bup supports both internal and external subcommands. The former
+ are the most common, and are all located in lib/bup/cmd/. They
+ must be python modules named lib/bup/cmd/COMMAND.py, and must
+ contain a `main(argv)` function that will be passed the *binary*
+ command line arguments (bytes, not strings). The filename must
+ have underscores for any dashes in the subcommand name. The
+ external subcommands are in lib/cmd/.
+
+ - The python code is all in lib/bup.
+
+ - lib/bup/\*.py contains the python code (modules) that bup depends on.
That directory name seems a little silly (and worse, redundant) but there
seemed to be no better way to let programs write "from bup import
index" and have it work. Putting bup in the top level conflicted with
you'd have to store the same data all over again. But with hashsplitting,
no matter how much data you add, modify, or remove in the middle of the
file, all the chunks *before* and *after* the affected chunk are absolutely
-the same. All that matters to the hashsplitting algorithm is the 32-byte
+the same. All that matters to the hashsplitting algorithm is the
"separator" sequence, and a single change can only affect, at most, one
separator sequence or the bytes between two separator sequences. And
because of rollsum, about one in 8192 possible 64-byte sequences is a
What we do instead is we extend the hashsplit algorithm a little further
using what we call "fanout." Instead of checking just the last 13 bits of
-the checksum, we use additional checksum bits to produce additional splits.
-For example, let's say we use a 4-bit fanout. That means we'll break a
-series of chunks into its own tree object whenever the last 13+4 = 17 bits
-of the rolling checksum are 1. Naturally, whenever the lowest 17 bits are
-1, the lowest 13 bits are *also* 1, so the boundary of a chunk group is
-always also the boundary of a particular chunk.
+the checksum, we use additional checksum bits to produce additional splits.
+Note that (most likely due to an implementation bug), the next higher bit
+after the 13 bits (marked 'x'):
+
+ ...... '..x1'1111'1111'1111
+
+is actually ignored next. Now, let's say we use a 4-bit fanout. That means
+we'll break a series of chunks into its own tree object whenever the next
+4 bits of the rolling checksum are 1, in addition to the 13 lowest ones.
+Since the 13 lowest bits already have to be 1, the boundary of a group of
+chunks is necessarily also always the boundary of a particular chunk.
And so on. Eventually you'll have too many chunk groups, but you can group
them into supergroups by using another 4 bits, and continue from there.
version of that file; instead, your new backup set just contains the
most-recently-known valid version of that file. This is a good trick if you
want to do frequent backups of smallish files and infrequent backups of
-large ones (as in 'bup save --smaller'). Each of your backups will be
-"complete," in that they contain all the small files and the large ones, but
-intermediate ones will just contain out-of-date copies of the large files.
+large ones. Each of your backups will be "complete," in that they contain
+all the small files and the large ones, but intermediate ones will just
+contain out-of-date copies of the large files. Note that this isn't done
+right now, and 'bup save --smaller' doesn't store bigger files _at all_.
A final game we can play with the bupindex involves restoring: when you
restore a directory from a previous backup, you can update the bupindex
are formatted. So don't get confused!
+Handling Python 3's insistence on strings
+=========================================
+
+In Python 2 strings were bytes, and bup used them for all kinds of
+data. Python 3 made a pervasive backward-incompatible change to treat
+all strings as Unicode, i.e. in Python 2 'foo' and b'foo' were the
+same thing, while u'foo' was a Unicode string. In Python 3 'foo'
+became synonymous with u'foo', completely changing the type and
+potential content, depending on the locale.
+
+In addition, and particularly bad for bup, Python 3 also (initially)
+insisted that all kinds of things were strings that just aren't (at
+least not on many platforms), i.e. user names, groups, filesystem
+paths, etc. There's no guarantee that any of those are always
+representable in Unicode.
+
+Over the years, Python 3 has gradually backed away from that initial
+position, adding alternate interfaces like os.environb or allowing
+bytes arguments to many functions like open(b'foo'...), so that in
+those cases it's at least possible to accurately retrieve the system
+data.
+
+After a while, they devised the concept of
+[bytesmuggling](https://www.python.org/dev/peps/pep-0383/) as a more
+comprehensive solution. In theory, this might be sufficient, but our
+initial randomized testing discovered that some binary arguments would
+crash Python during startup[1]. Eventually Johannes Berg tracked down
+the [cause](https://sourceware.org/bugzilla/show_bug.cgi?id=26034),
+and we hope that the problem will be fixed eventually in glibc or
+worked around by Python, but in either case, it will be a long time
+before any fix is widely available.
+
+Before we tracked down that bug we were pursuing an approach that
+would let us side step the issue entirely by manipulating the
+LC_CTYPE, but that approach was somewhat complicated, and once we
+understood what was causing the crashes, we decided to just let Python
+3 operate "normally", and work around the issues.
+
+Consequently, we've had to wrap a number of things ourselves that
+incorrectly return Unicode strings (libacl, libreadline, hostname,
+etc.) and we've had to come up with a way to avoid the fatal crashes
+caused by some command line arguments (sys.argv) described above. To
+fix the latter, for the time being, we just use a trivial sh wrapper
+to redirect all of the command line arguments through the environment
+in BUP_ARGV_{0,1,2,...} variables, since the variables are unaffected,
+and we can access them directly in Python 3 via environb.
+
+[1] Our randomized argv testing found that the byte smuggling approach
+ was not working correctly for some values (initially discovered in
+ Python 3.7, and observed in other versions). The interpreter
+ would just crash while starting up like this:
+
+ Fatal Python error: _PyMainInterpreterConfig_Read: memory allocation failed
+ ValueError: character U+134bd2 is not in range [U+0000; U+10ffff]
+
+ Current thread 0x00007f2f0e1d8740 (most recent call first):
+ Traceback (most recent call last):
+ File "t/test-argv", line 28, in <module>
+ out = check_output(cmd)
+ File "/usr/lib/python3.7/subprocess.py", line 395, in check_output
+ **kwargs).stdout
+ File "/usr/lib/python3.7/subprocess.py", line 487, in run
+ output=stdout, stderr=stderr)
+
We hope you'll enjoy bup. Looking forward to your patches!
-- apenwarr and the rest of the bup team
Local Variables:
-mode: text
+mode: markdown
End:
projects / bup.git / blobdiff