Ordered writes in HekaFS encryption layer
DRAFT
Transparent encryption layer brings in specific problems
inherent for stackable file systems (i.e. intermediary layers
between user and local fs). One of such problems is that such
layers are not aware about metadata of local file systems that
indicates "holes". So if such holes exists, then it will be
represented to user as a "garbage" (decrypted set of zeros),
and this would mean posix non-compliance.
The single reasonable way for us is to not allow holes at local
fs, i.e. to detect all moments of hole creation and mandatory
convert it to a set of (encrypted) zeros.
A hole is created every time when local file system is asked
to write from offset, which is larger than file size. So the
first idea is to compare file size and offset that user wants
to write from. If the offset is larger than file size, we
convert hole before write. However, it wouldn't be enough only
to follow user's instructions.
Encryption layer writes data by chunks (usually of atom size).
This means that in a common case we (encryption layer) must
split a user request into many chunks and writes them separately.
This is because:
1) Linux VFS doesn't accept too large chunks (write of chunk
larger than MAX_INT will be incomplete, and we can not allow
such "truncation" in encryption layer).
2) splitting large writes will improve things in the case of
concurrent access, as writing to different parts of file
requires to acquire different "shared locks".
However, splitting writes without any additional efforts from
encryption layer is prone to appearing short-lived holes on a
local fs. For example, user asks to append 20K to 10K file.
Suppose we write by 4K chunks and the first chunk that hits
local fs has offset 12K. It means that 2K hole will be created
on the local fs.
We need to avoid such short-lived holes even in spite of their
short lifespan: after a system crash we'll have already
persistent holes (and everything will be consistent from the
standpoint of local fs).
We avoid such short-lived holes by using so-called ordering
technique: the encryption layer provides a guarantee that any
"appending" sequence of requests will be written in ordered
fashion.
Glossary
---------
Chunk of data is a sequence of (logical) bytes
B = {b1, b2, ..., bm} in a file at some offset off. For every
chunk B we'll denote offset(B) = off, size(B) = m.
Request is an order for a local fs to write some chunk of
data (see above).
Submit a request means to ask an upper server-side manager
(oplock xlator in our case) to write a respective chunk of
data.
Sequence of requests {R0, R1, ..., Rn} is any sequence of
chunks so that offset(R_i) + size(R_i) == offset (R_(i+1)).
Request R_i is direct parent of R_(i+1). Request R_s, (s < i)
is indirect parent of R_(i+1).
Sequence of requests {R0, R1, ..., Rn} is appending iff
offset(R_i) > file_size for some i, 0 <= i <= n.
In particular, appending sequence changes file size.
Sequence of requests is overwriting, iff it is not appending.
Appending sequence is minimal, iff offset(R0) > file_size
Lemma
--------
Every sequence can be split into an overwriting and a minimal
appending sub-sequences.
So we split every sequence of requests into 2 sub-sequences
(overwriting and appending ones). An overwriting sub-sequence
is written in parallel fashion. An appending subsequence is
written in ordered fashion (see below for definitions).
Every sequence has
. block of HEAD_ATOM type (<= 1),
. block of TAIL_ATOM type (<= 1),
. blocks of FULL_ATOM type (>= 0).
We define a linear order on a set of blocks of any sequence by
the following rule:
(A < B) iff (offset(A) < offset(B)).
All requests {R1, R2, ...} of appending sequence are written in
ordered ("parent first") fashion. This means that:
A1. On a client side
R_(i+1) is written by the callback function ->writev_cbk()
of ->writev() spawned to write its direct parent (R_i).
Since we acquire an exclusive access to write the whole
appending sequence, all its requests are written immediately
in ordered fashion (we don't ask server-side manager to write a
separate R_j). See do_ordered_submit().
B1. On a server side
A special server-side manager (oplock xlator) queues requests
and grants (or decline) exclusive access to write the whole
appending sequence.
All requests {R1, R2, ...} of overwriting sequence are written
in parallel fashion. This means that:
A2. On a client side
We submit all R_j in a loop (see do_parallel_submit). I.e. for
every request R_j we ask the server-side manager (oplock xlator)
for "shared access". If the shared access is not granted, then
we try again.
B2. On a server side
A special server-side manager (oplock xlator) queues requests
and grants (or decline) shared access to write a separate request
R_j of overwriting sequence. (Definitions of exclusive and shared
access, and the policy of their granting will be defined separately).
Such technique allows to simplify things (i.e. to not involve
additional sorting means at server side).
Implementation details.
The order HEAD_ATOM < FULL_BLOCK_ATOM < HEAD_ATOM is hardcoded
(see function do_ordered_submit). The order on blocks of the
same FULL_BLOCK_ATOM type is provided by maintaining a special
cursor at local area (see crypt_local_t, avec_config).
Recap
-----
We ask for exclusive access for the whole appending sequence.
Once it is granted, all requests of the sequence are written
one-by-one in ordered fashion.
All requests of any overwrite sequence are submitted in
parallel fashion. We ask for shared access for every separate
request of an overwrite sequence.
All comments, suggestions are welcome.
Edward.