UBIFS in-place vs out-of-place GC

UBIFS in-place vs out-of-place GC

[Russ Dill]

I'm doing a bit of research on UBIFS and something I read from a few
sources has me confused regarding garbage collection:

http://osl.sed.hu/~havasi/ubifs/#gc

>> Out-place mode:
>>
>> This mode deletes the active nodes from the tree and inserts them
>> again into a new location. Because of the wandering algorithm it
>> makes dirty nodes as well. After garbage collection, it can be
>> possible that an erase block has more dirty space created than freed
>> up.In-place mode:
>>
>> This method copies the active nodes into an empty erase block
>> and creates a displacement table to its beginning. Afterwards, it
>> logically swaps these two erase blocks, so the active nodes will
>> be accessible at the same place as before, thus modifying other
>> parts of the tree is not necessary. A big advantage of this method
>> is that it can convert all dirty space in the erase block to free space.
>> Its disadvantage is that it can cause fragmentation.
>>
>> The default GC mode of the UBIFS is in-place mode and it will
>> use a heuristic method to detect fragmentation and call out-place
>> mode.

Looking at the source, I can find the code that does the out of place
updates, but I can't find any references to in place updates or
displacement tables. What gives?

Re: UBIFS in-place vs out-of-place GC

[Artem Bityutskiy]

Hi,

On Wed, 2010-09-01 at 09:08 -0700, Russ Dill wrote:
> I'm doing a bit of research on UBIFS and something I read from a few
> sources has me confused regarding garbage collection:
> 
> http://osl.sed.hu/~havasi/ubifs/#gc

You should contact Szeged guys and ask them to remove obsolete
information.

For much more up-to-date information, see
http://linux-mtd.infradead.org/doc/ubifs.html#L_documentation

> Looking at the source, I can find the code that does the out of place
> updates, but I can't find any references to in place updates or
> displacement tables. What gives?

We do not have displacement tables, that was some old idea which we
never implemented.

We do not have in-place GC in UBIFS. But we have so-called "in-the-gaps"
method which we use during commit to write the FS index when we do not
have extra empty LEBs. In the code it corresponds to the
'layout_in_gaps()' function.

-- 
Best Regards,
Artem Bityutskiy (Битюцкий Артём)

Re: UBIFS in-place vs out-of-place GC

[Russ Dill]

On Thu, Sep 2, 2010 at 4:45 AM, Artem Bityutskiy <dedekind1@gmail.com> wrote:
> Hi,
>
> On Wed, 2010-09-01 at 09:08 -0700, Russ Dill wrote:
>> I'm doing a bit of research on UBIFS and something I read from a few
>> sources has me confused regarding garbage collection:
>>
>> http://osl.sed.hu/~havasi/ubifs/#gc
>
> You should contact Szeged guys and ask them to remove obsolete
> information.
>
> For much more up-to-date information, see
> http://linux-mtd.infradead.org/doc/ubifs.html#L_documentation
>
>> Looking at the source, I can find the code that does the out of place
>> updates, but I can't find any references to in place updates or
>> displacement tables. What gives?
>
> We do not have displacement tables, that was some old idea which we
> never implemented.
>
> We do not have in-place GC in UBIFS. But we have so-called "in-the-gaps"
> method which we use during commit to write the FS index when we do not
> have extra empty LEBs. In the code it corresponds to the
> 'layout_in_gaps()' function.
>

Thanks much, I figured it was outdated information, I just wanted to
confirm that suspicion.