Shrink UBIFS

[Artem Bityutskiy]

On Sat, 2017-09-30 at 20:09 +0200, Richard Weinberger wrote:
> Ryan,
> 
> On Thu, Sep 28, 2017 at 1:43 PM, Ryan Meulenkamp
> <Ryan.Meulenkamp at nedap.com> wrote:
> > Hi,
> > 
> > 
> > I'm planning to write an ioctl for shrinking a UBIFS to be able to
> > resize the volume its on and create another
> > 
> > volume because it is essential for our upgrade/migration flow. Do
> > you guys have any advice for me? The
> > 
> > hard part is that LEB's that would fall outside the new size should
> > be moved inside the new size. From what
> > 
> > I read, the garbage collection code could be used to  accomplish
> > this, but it is not really possible to define
> > 
> > which LEB's to put where.
> > 
> > 
> > Thanks in advance!
> 
> So, you want to implement _online_ shrinking?
> This is a way more complicated, think of power-cuts.
> I strongly suggest thinking about offline shrinking first.
> 
> You are right, the garbage collector might be useful, you could
> modify
> it in a way
> to move blocks away from to-be-removed LEBs.
> But again, do you *really* need online shrinking?

Yeah, offline would be way easier


But still just thinking aloud about online shrinking...

Suppose we have UBIFS which looks like this.

FDDDEFDFDFFFFFDDDFDFFEEEDFDDDFDFDFDFDFDDDDDDFFFFFFDDDDDDDDDDDFFDFF

F - full eraseblock
D - eraseblock with dirty space.
E - empty eraseblock.

To shrink, we need to turn it into something like this.

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDDDDEEEEEEEEEEEEEEEEEEEE

Currently GC selects the dirtiest eraseblock as the victim for
cleaning, because this is the most efficient strategy. But you could
introduce a special 'shrinking  mode', where you'd tell GC to try hard
picking the victims from the end, Probably also try hard not to re-use
the empty eraseblocks at the end.

Then while being in this mode, GC is used from a background thread to
make enough empty eraseblocks at the end. Well, it is possible that GC
will stop making progress before enough eraseblocks at the end are made
empty, which would mean that further shrinking is impossible.

Just thoughts.