In-place patching: rebuilding the new version inside the storage that holds the basis, without a second copy, following Rasch and Burns, In-Place Rsync (USENIX 2003).
A delta lists its commands in output order, and output positions follow from the command lengths. Applied in that order over the basis itself, a copy may read bytes that an earlier command has already overwritten. Copies are therefore applied in a dependency order instead: copy i must run before copy j when i reads bytes that j writes. Literal commands read nothing from the basis and are written last.
Dependencies can form cycles, for example two blocks that swap places. No
order satisfies a cycle, so the sender breaks each one by turning a copy on
it into a literal carrying the same bytes, choosing the shortest copy on the
cycle. The result is an ordinary delta: rdiff patch and Rexd.patch/3
apply it as usual, and patch/4 can apply it in place.
- Sender:
make_safe/2, orRexd.delta(signature, new, in_place: true). - Receiver:
patch/4, with functions that read and write the storage.
A copy that overlaps its own destination is applied in the direction that
never reads a byte after writing it, like memmove.
Interruption
In-place patching overwrites the basis. If it stops part-way, through a crash or a failing write function, the storage holds a mixture of both versions and neither can be rebuilt from it. Use it where the new version can be obtained again in full, or where the storage offers its own journaling.
Cost
The dependency order is computed from the copy commands alone, in O(c log c) time for c copies, whatever their read ranges; a hostile delta cannot make it quadratic. The receiver holds the command list, including literal data, in memory.
Summary
Types
Reads length bytes of the storage starting at offset.
Writes data into the storage starting at offset.
Types
@type error() :: {:copy_out_of_range, non_neg_integer(), non_neg_integer()} | :not_in_place_safe
Reasons patch/4 can fail. Nothing has been written when they are returned.
@type read_fun() :: (non_neg_integer(), pos_integer() -> binary())
Reads length bytes of the storage starting at offset.
@type write_fun() :: (non_neg_integer(), binary() -> term())
Writes data into the storage starting at offset.
Functions
@spec make_safe(Rexd.Delta.t(), binary() | read_fun()) :: Rexd.Delta.t()
Returns an equivalent delta that patch/4 can apply in place.
Copies that close a dependency cycle are replaced by literals holding the
same bytes, read from new: the new version as a binary, or a function
fn offset, length -> binary end reading it. On each cycle the shortest
copy is converted, the earliest in output order among equals. The rebuilt
data is unchanged.
iex> basis = "AAAAAAAA" <> "BBBBBBBBBBBB"
iex> new = "BBBBBBBBBBBB" <> "AAAAAAAA"
iex> swapped = %Rexd.Delta{commands: [{:copy, 8, 12}, {:copy, 0, 8}]}
iex> safe = Rexd.InPlace.make_safe(swapped, new)
iex> safe.commands
[{:copy, 8, 12}, {:literal, "AAAAAAAA"}]
iex> Rexd.patch(basis, safe)
{:ok, "BBBBBBBBBBBBAAAAAAAA"}@spec patch(Rexd.Delta.t(), non_neg_integer(), read_fun(), write_fun()) :: {:ok, non_neg_integer()} | {:error, error()}
Applies delta to storage that holds the basis, overwriting it with the new
version.
basis_size is the size of the basis in the storage. read and write
access the storage, reading and writing at most 64 KiB at a time. On success
returns {:ok, new_size}; when the new version is shorter than the basis,
the caller truncates the storage to new_size.
Everything that can be checked is checked before the first write: every
copy must lie inside the basis, and the copies must have a dependency order
(the delta was produced by make_safe/2 or has no cycles to begin with).
iex> basis = "0123456789"
iex> new = "456789" <> "0123"
iex> sig = Rexd.signature(basis, block_len: 2)
iex> delta = Rexd.delta(sig, new, in_place: true)
iex> {:ok, storage} = Agent.start_link(fn -> basis end)
iex> read = fn offset, len -> Agent.get(storage, &binary_part(&1, offset, len)) end
iex> write = fn offset, data ->
...> Agent.update(storage, fn bin ->
...> <<head::binary-size(offset), _::binary-size(byte_size(data)), tail::binary>> = bin
...> head <> data <> tail
...> end)
...> end
iex> Rexd.InPlace.patch(delta, byte_size(basis), read, write)
{:ok, 10}
iex> Agent.get(storage, & &1)
"4567890123"