Are reflinks always O(n)?

Are reflinks always O(n)?

[Demi Marie Obenour]

[-- Attachment #1: Type: text/plain, Size: 618 bytes --]

In bcachefs, is creating a reflink O(n) in the size of the file, or in
the number of currently unshared extents that need to be moved into the
reflink btree?  The former would be annoying, but the latter is
proportional to the number of modifications to the file since it was
last reflinked, which is fine for my use-case so long as unlinking a
heavily reflinked file is also fast.  My reading of “bcachefs:
Principles of Operation” suggests the latter.

Basically, if a file is already reflinked, is reflinking it *again*
cheap?
-- 
Sincerely,
Demi Marie Obenour (she/her/hers)
Invisible Things Lab

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: Are reflinks always O(n)?

[Kent Overstreet]

On Thu, Jun 30, 2022 at 01:00:29AM -0400, Demi Marie Obenour wrote:
> In bcachefs, is creating a reflink O(n) in the size of the file, or in
> the number of currently unshared extents that need to be moved into the
> reflink btree?  The former would be annoying, but the latter is
> proportional to the number of modifications to the file since it was
> last reflinked, which is fine for my use-case so long as unlinking a
> heavily reflinked file is also fast.  My reading of “bcachefs:
> Principles of Operation” suggests the latter.
> 
> Basically, if a file is already reflinked, is reflinking it *again*
> cheap?

It's about the same. Reflinking a file doesn't change the number of extents, it
just makes them indirect, and then to reflink the file a second time we have to
bump the refcount on all those indirect extents.

Re: Are reflinks always O(n)?

[Demi Marie Obenour]

[-- Attachment #1: Type: text/plain, Size: 1594 bytes --]

On Mon, Jul 04, 2022 at 10:56:08AM -0400, Kent Overstreet wrote:
> On Thu, Jun 30, 2022 at 01:00:29AM -0400, Demi Marie Obenour wrote:
> > In bcachefs, is creating a reflink O(n) in the size of the file, or in
> > the number of currently unshared extents that need to be moved into the
> > reflink btree?  The former would be annoying, but the latter is
> > proportional to the number of modifications to the file since it was
> > last reflinked, which is fine for my use-case so long as unlinking a
> > heavily reflinked file is also fast.  My reading of “bcachefs:
> > Principles of Operation” suggests the latter.
> > 
> > Basically, if a file is already reflinked, is reflinking it *again*
> > cheap?
> 
> It's about the same. Reflinking a file doesn't change the number of extents, it
> just makes them indirect, and then to reflink the file a second time we have to
> bump the refcount on all those indirect extents.

Thanks for the information.  This could be annoying for large, heavily
fragmented files that are frequently reflinked.  What makes this tricky
is that at the time of snapshot creation, Qubes OS does not know if the
snapshot will be sparse or dense.  For instance, renaming a qube (VM)
is done by cloning the qube and then deleting the original.  That the
clone will be sparse is only known when the deletion API call is made,
which is too late to use a different method of cloning the file.
Therefore, something that performs well in both cases is highly
desirable.
-- 
Sincerely,
Demi Marie Obenour (she/her/hers)
Invisible Things Lab

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]