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.
=========================================
In Python 2 strings were bytes, and bup used them for all kinds of
-data. Python 3 made a pervasive backward-incompatible change to make
-all strings 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.
+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
paths, etc. There's no guarantee that any of those are always
representable in Unicode.
-Over the years, Python 3 has gradually backed off from that initial
-aggressive stance, 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 [byte smuggling](https://www.python.org/dev/peps/pep-0383/)
-as a more comprehensive solution, though at least currently, we've
-found that it doesn't always work (see below), and at least for bulk
-data, it's more expensive, converting the data back and forth when you
-just wanted the original bytes, exactly as provided by the system
-APIs.
-
-At least one case where we've found that the byte smuggling approach
-it doesn't work is with respect to sys.argv (initially discovered in
-Python 3.7). The claim is that we should be able to retrieve the
-original bytes via fsdecode(sys.argv[n]), but after adding some
-randomized argument testing, we quickly discovered that this isn't
-true with (at least) the default UTF-8 environment. The interpreter
-just crashes while starting up with some random binary arguments:
+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]
File "/usr/lib/python3.7/subprocess.py", line 487, in run
output=stdout, stderr=stderr)
-To fix that, at least for now, the plan is to *always* force the
-LC_CTYPE to ISO-8859-1 before launching Python, which does "fix" the
-problem.
-
-The reason we want to require ISO-8859-1 is that it's a (common)
-8-byte encoding, which means that there are no invalid byte sequences
-with respect to encoding/decoding, and so the mapping between it and
-Unicode is one-to-one. i.e. any sequence of bytes is a valid
-ISO-8859-1 string and has a valid representation in Unicode. Whether
-or not the end result in Unicode represents what was originally
-intended is another question entirely, but the key thing is that the
-round-trips between ISO-8859-1 bytes and Unicode should be completely
-safe.
-
-We're requiring this encoding so that *hopefully* Python 3 will then
-allow us to get the unmangled bytes from os interfaces where it
-doesn't provide an explicit or implicit binary version like environb
-or open(b'foo', ...).
-
-In the longer run we might consider wrapping these APIs ourselves in
-C, and have them just return Py_bytes objects to begin with, which
-would be more efficient and make the process completely independent of
-the system encoding, and/or less potentially fragile with respect to
-whatever the Python upstream might decide to try next.
-
-But for now, this approach will hopefully save us some work.
-
-
We hope you'll enjoy bup. Looking forward to your patches!
-- apenwarr and the rest of the bup team
projects / bup.git / blobdiff