f2fs: trigger GC when there are prefree segments

Previously, f2fs conducts SSR when free_sections() < overprovision_sections.
But, even though there are a lot of prefree segments, it can consider SSR only.
So, let's consider the number of prefree segments too for triggering SSR.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit c34e333fd5ca41317c3dab69ed8a212acacd4aeb)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: avoid an overflow during utilization calculation

The current f2fs uses all the block counts with 32 bit numbers, which is able to
cover about 15TB volume.

But in calculation of utilization, f2fs multiplies the count by 100 which can
induce overflow.
This patch fixes this.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 222cbdc4835f8151b886b049d6ad56b18f88d470)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: merge more bios of node block writes

Previously, we experience bio traces as follows when running simple sequential
write test.

 f2fs_do_submit_bio: type = NODE, io = no sync, sector = 500104928, size = 4K
 f2fs_do_submit_bio: type = NODE, io = no sync, sector = 499922208, size = 368K
 f2fs_do_submit_bio: type = NODE, io = no sync, sector = 499914752, size = 140K

 -> total 512K

The first one is to write an indirect node block, and the others are to write
direct node blocks.

The reason why there are two separate bios for direct node blocks is:
0. initial state
------------------    ------------------
|                |    |xxxxxxxx        |
------------------    ------------------

1. write 368K
------------------    ------------------
|                |    |xxxxxxxxWWWWWWWW|
------------------    ------------------

2. write 140K
------------------    ------------------
|WWWWWWW         |    |xxxxxxxxWWWWWWWW|
------------------    ------------------

This is because f2fs_write_node_pages tries to write just 512K totally, so that
we can lose the chance to merge more bios nicely.

After this patch is applied, we can get the following bio traces.

  f2fs_do_submit_bio: type = NODE, io = no sync, sector = 500103168, size = 8K
  f2fs_do_submit_bio: type = NODE, io = no sync, sector = 500111368, size = 4K
  f2fs_do_submit_bio: type = NODE, io = no sync, sector = 500107272, size = 512K
  f2fs_do_submit_bio: type = NODE, io = no sync, sector = 500108296, size = 512K
  f2fs_do_submit_bio: type = NODE, io = no sync, sector = 500109320, size = 500K

And finally, we can improve the sequential write performance,
    from 458.775 MB/s to 479.945 MB/s on SSD.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 423e95ccbe2e2612ed9fe41667acfc338f3af07b)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: optimize gc for better performance

This patch improves the gc efficiency by optimizing the victim
selection policy. With this optimization, the random re-write
performance could increase up to 20%.

For f2fs, when disk is in shortage of free spaces, gc will selects
dirty segments and moves valid blocks around for making more space
available. The gc cost of a segment is determined by the valid blocks
in the segment. The less the valid blocks, the higher the efficiency.
The ideal victim segment is the one that has the most garbage blocks.

Currently, it searches up to 20 dirty segments for a victim segment.
The selected victim is not likely the best victim for gc when there
are much more dirty segments. Why not searching more dirty segments
for a better victim? The cost of searching dirty segments is
negligible in comparison to moving blocks.

In this patch, it enlarges the MAX_VICTIM_SEARCH to 4096 to make
the search more aggressively for a possible better victim. Since
it also applies to victim selection for SSR, it will likely improve
the SSR efficiency as well.

The test case is simple. It creates as many files until the disk full.
The size for each file is 32KB. Then it writes as many as 100000
records of 4KB size to random offsets of random files in sync mode.
The testing was done on a 2GB partition of a SDHC card. Let's see the
test result of f2fs without and with the patch.

---------------------------------------
2GB partition, SDHC
create 52023 files of size 32768 bytes
random re-write 100000 records of 4KB
---------------------------------------
| file creation (s) | rewrite time (s) | gc count | gc garbage blocks |
[no patch]  341         4227             1174          174840
[patched]   324         2958             645           106682

It's obvious that, with the patch, f2fs finishes the test in 20+% less
time than without the patch. And internally it does much less gc with
higher efficiency than before.

Since the performance improvement is related to gc, it might not be so
obvious for other tests that do not trigger gc as often as this one (
This is because f2fs selects dirty segments for SSR use most of the
time when free space is in shortage). The well-known iozone test tool
was not used for benchmarking the patch becuase it seems do not have
a test case that performs random re-write on a full disk.

This patch is the revised version based on the suggestion from
Jaegeuk Kim.

Signed-off-by: Jin Xu <jinuxstyle@gmail.com>
[Jaegeuk Kim: suggested simpler solution]
Reviewed-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>

(cherry picked from commit a26b7c8a0149ce1e3b6a10f2801aada6e447e4e7)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: optimize fs_lock for better performance

There is a performance problem: when all sbi->fs_lock are holded, then
all the following threads may get the same next_lock value from sbi->next_lock_num
in function mutex_lock_op, and wait for the same lock(fs_lock[next_lock]),
it may cause performance reduce.
So we move the sbi->next_lock_num++ before getting lock, this will average the
following threads if all sbi->fs_lock are holded.

v1-->v2:
	Drop the needless spin_lock as Jaegeuk suggested.

Suggested-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
Signed-off-by: Yu Chao <chao2.yu@samsung.com>
Signed-off-by: Gu Zheng <guz.fnst@cn.fujitsu.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit e76eebee70948060d80b5f9edd2d97062049df53)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: optimize the victim searching loop slightly

Since the MAX_VICTIM_SEARCH has been enlarged from 20 to 4096,
the victim searching overhead will be increased much than before,
especially for SSR that searches victim for use quiet often.
This patch intends to reduce the overhead a little bit by:
- make the get_gc_cost a inline routine to reduce function call
  overhead
- reduce multiplication and division operations
- reduce unnecessary comparison operation

Signed-off-by: Jin Xu <jinuxstyle@gmail.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit a57e564d14d9d123b2dd4ff1c933da0d900e0b1d)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: avoid allocating failure in bio_alloc

This patch add macro MAX_BIO_BLOCKS to limit value of npages in
f2fs_bio_alloc, it can avoid allocating failure in bio_alloc caused by
npages is larger than BIO_MAX_PAGES.

Signed-off-by: Yu Chao <chao2.yu@samsung.com>
Reviewed-by: Gu Zheng <guz.fnst@cn.fujitsu.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit cc7b1bb173676621b092b61d22d8d12b05efb5e8)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: remove unneeded write checkpoint in recover_fsync_data

Previously, recover_fsync_data still to write checkpoint when there is
nothing to recover with normal umount image.
It may reduce mount performance and flash memory lifetime, so let's remove
it.

Signed-off-by: Tan Shu <shu.tan@samsung.com>
Signed-off-by: Yu Chao <chao2.yu@samsung.com>
Reviewed-by: Gu Zheng <guz.fnst@cn.fujitsu.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(backported from commit 691c6fd2a2d6b6db08b17beec5e42ab0687058c7)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>

Conflicts:
	fs/f2fs/recovery.c
f2fs: don't let the orphan inode counter underflow

Accounting errors from buggy code calling the acquire/release/remove
orphan inode interfaces can cause n_orphans to underflow, which will
then cause acquire_orphan_inode() to return -ENOSPC on the next
operation.  This commit guards against that condition.

Signed-off-by: Russ Knize <rknize@motorola.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(backported from commit 885166c03c1d0ea6d79d707229340e3161ed1316)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>

Conflicts:
	fs/f2fs/checkpoint.c
f2fs: handle remount options correctly

The current f2fs code errors if the xattr or acl options are passed when
remounting.  This is important in a typical scenario where f2fs is mounted
as a "ro" root file-system by the boot loader and then the init process wants
to remount it "rw" with the "remount,rw" option.

Signed-off-by: Kelly Anderson <kelly@xilka.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 4058c5117d6d8a94002fb308615c7442ed3a3896)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: avoid unnecessary checkpoints

During the f2fs_put_super procedure, we don't need to conduct checkpoint all
the time, since we don't need to do that if superblock is clean.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 5887d291d792773368f6eaf1759aad109bcd78eb)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: fix writing incorrect orphan blocks

Previously, there was a erroneous scenario like below.
thread 1:                       thread 2:
 f2fs_unlink
  - acquire_orphan_inode
    : sbi->n_orphans++           write_checkpoint
                                 - block_operations
                                  : f2fs_lock_all
                                 - do_checkpoint
                                  : write orphan blocks with sbi->n_orphans
                                 - unblock_operations
  - f2fs_lock_op
  - release_orphan_inode
  - f2fs_unlock_op

During the checkpoint by thread 2, f2fs stores a wrong orphan block according
to the wrong sbi->n_orphans.
To avoid this, simply we should make cover acquire_orphan_inode too with
f2fs_lock_op.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(backported from commit ccaaca25919a2cdeccd8fdce5f546e3ed7f6a9e9)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>

Conflicts:
	fs/f2fs/namei.c
f2fs: fix to store and retrieve i_rdev correctly

When storing i_rdev, we should check its file type.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 3d1e38073b3f33d31df1ae09aaccab3dfd9fb61e)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: introduce function read_raw_super_block()

Introduce function read_raw_super_block() to hide reading raw super block and
the retry routine if the first sb is invalid.

Signed-off-by: Gu Zheng <guz.fnst@cn.fujitsu.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 9076a75f8e0f23ab64e2f34eb6be144e81f00a3e)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: avoid wait if IO end up when do_checkpoint for better performance

Previously, do_checkpoint() will call congestion_wait() for waiting the pages
(previous submitted node/meta/data pages) to be written back.
Because congestion_wait() will set a regular period (e.g. HZ / 50 ) for waiting, and
no additional wake up mechanism was introduced if IO ends up before regular period costed.
Yuan Zhong found there is a situation that after the pages have been written back,
but the checkpoint thread still wait for congestion_wait to exit.

So here we store checkpoint task into f2fs_sb when doing checkpoint, it'll wait for IO completes
if there's IO going on, and in the end IO path, wake up checkpoint task when IO ends up.

Thanks to Yuan Zhong's pre work about this problem.

Reported-by: Yuan Zhong <yuan.mark.zhong@samsung.com>
Signed-off-by: Gu Zheng <guz.fnst@cn.fujitsu.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit e234088758fca3a669ebb1a02d8bf7bf60f0e4ff)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: use true and false for boolean value

Signed-off-by: Haicheng Li <haicheng.li@linux.intel.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit cffbfa66485e4940091d7e64024e802314d24c09)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: no need to check other dirty_segmap when the seg has been found

Because one dirty seg can only be mapped to one dirty_type. Otherwise, it's a bug.

Signed-off-by: Haicheng Li <haicheng.li@linux.intel.com>
[Jaegeuk Kim: modify a comment related to this patch]
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>

(cherry picked from commit 435f2a1b58ac8f50894f23549c97791085f7cba2)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: introduce f2fs_kmem_cache_alloc to hide the unfailed, kmem cache allocation

Introduce the unfailed version of kmem_cache_alloc named f2fs_kmem_cache_alloc
to hide the retry routine and make the code a bit cleaner.

v2:
   Fix the wrong use of 'retry' tag pointed out by Gao feng.
   Use more neat code to remove redundant tag suggested by Haicheng Li.

Signed-off-by: Gu Zheng <guz.fnst@cn.fujitsu.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit 7bd59381c82defe19875284c48b1ac9dacd16e8f)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: clean up several status-related operations

This patch cleans up improper definitions that update some status information.

Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(cherry picked from commit dcdfff65276fdc6dfe5eb1d0aff802dfa7a95e15)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>
f2fs: use bool for booleans

Signed-off-by: Haicheng Li <haicheng.li@linux.intel.com>
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
(backported from commit aabe51364f44681cbd83fb1c27ef7d3dbe567c45)
Signed-off-by: Wen-chien Jesse Sung <jesse@cola.voip.idv.tw>

Conflicts:
	fs/f2fs/f2fs.h