2019-05-24 12:04:05 +02:00
|
|
|
|
2021-05-06 18:06:44 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-11-26 12:44:15 +01:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 14:55:01 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-03-03 17:12:09 +08:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
|
|
|
|
|
2008-03-03 17:12:09 +08:00
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2010-03-26 10:08:07 +08:00
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
ocfs2: throttle back local alloc when low on disk space
Ocfs2's local allocator disables itself for the duration of a mount point
when it has trouble allocating a large enough area from the primary bitmap.
That can cause performance problems, especially for disks which were only
temporarily full or fragmented. This patch allows for the allocator to
shrink it's window first, before being disabled. Later, it can also be
re-enabled so that any performance drop is minimized.
To do this, we allow the value of osb->local_alloc_bits to be shrunk when
needed. The default value is recorded in a mostly read-only variable so that
we can re-initialize when required.
Locking had to be updated so that we could protect changes to
local_alloc_bits. Mostly this involves protecting various local alloc values
with the osb spinlock. A new state is also added, OCFS2_LA_THROTTLED, which
is used when the local allocator is has shrunk, but is not disabled. If the
available space dips below 1 megabyte, the local alloc file is disabled. In
either case, local alloc is re-enabled 30 seconds after the event, or when
an appropriate amount of bits is seen in the primary bitmap.
Signed-off-by: Mark Fasheh <mfasheh@suse.com>
2008-07-28 18:02:53 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2007-10-18 15:30:42 -07:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2016-01-22 15:40:57 -05:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2008-10-07 14:25:16 -07:00
|
|
|
|
|
|
|
|
|
2009-12-07 13:16:07 -08:00
|
|
|
|
2015-09-04 15:44:54 -07:00
|
|
|
|
|
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
2010-03-03 11:26:27 +08:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2026-04-01 10:16:22 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-03 11:26:27 +08:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
2026-05-24 19:12:48 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
2026-05-24 19:12:48 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2026-05-24 19:12:48 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2010-03-03 11:26:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2008-11-13 14:49:13 -08:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 14:55:01 -07:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
2008-10-17 14:55:01 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 14:55:01 -07:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 14:55:01 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
2008-10-17 14:55:01 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-10 20:00:41 -08:00
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:19 -08:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-09-13 15:13:50 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
2010-09-13 15:13:50 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-11-26 12:44:15 +01:00
|
|
|
|
2018-04-05 16:18:33 -07:00
|
|
|
|
2010-04-13 14:38:06 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-11-12 15:06:54 -08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-18 16:47:55 -07:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2012-04-13 12:30:02 -04:00
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:10:08 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-02-27 17:02:49 -08:00
|
|
|
|
2010-03-26 10:10:08 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-11-12 15:06:54 -08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-09 17:26:22 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:29 +08:00
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2010-04-13 14:26:32 +08:00
|
|
|
|
2010-07-08 11:11:11 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2007-03-22 16:53:23 -07:00
|
|
|
|
2014-04-03 14:47:08 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2006-10-09 16:48:10 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-07 14:25:16 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
2008-03-03 17:12:09 +08:00
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2016-01-22 15:40:57 -05:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2007-10-18 15:30:42 -07:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2016-01-22 15:40:57 -05:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-03-03 17:12:30 +08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-11-13 14:49:12 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2008-03-03 17:12:09 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-07 14:25:16 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-08-06 23:18:02 -07:00
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2020-08-06 23:18:02 -07:00
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-08-18 17:11:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2026-02-21 16:37:42 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-08-18 17:11:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2008-03-03 17:12:09 +08:00
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2010-02-24 13:34:09 -08:00
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-08-18 17:11:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2026-02-21 16:37:42 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:40 -07:00
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2008-09-03 20:03:40 -07:00
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
|
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-01-25 14:11:06 +08:00
|
|
|
|
2008-03-05 16:11:46 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:25 +08:00
|
|
|
|
2008-03-03 17:12:09 +08:00
|
|
|
|
2017-11-15 17:31:55 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2016-08-02 14:02:10 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2026-02-21 16:37:42 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-16 21:01:00 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-08-02 14:02:10 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2016-08-02 14:02:10 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 14:44:33 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-08-02 14:02:10 -07:00
|
|
|
|
2016-09-19 14:44:33 -07:00
|
|
|
|
2016-08-02 14:02:10 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-09-19 14:44:33 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-08-02 14:02:10 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:24 +08:00
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-02-03 17:33:42 +02:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-08-09 14:42:32 +02:00
|
|
|
|
2022-01-29 13:41:27 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-06-19 14:45:54 -07:00
|
|
|
|
2022-01-29 13:41:27 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2022-01-29 13:41:27 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-06-19 14:45:54 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:15 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2024-03-14 10:17:13 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-01-21 15:48:33 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
2024-03-28 20:52:01 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-11-13 14:49:15 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-10-05 15:53:06 -07:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-10-05 15:53:06 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2024-03-28 20:52:01 +08:00
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:15 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
|
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
2013-07-03 15:01:00 -07:00
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
|
|
|
|
|
2013-07-03 15:01:00 -07:00
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
|
|
|
|
|
2013-07-03 15:01:00 -07:00
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
2013-07-03 15:01:00 -07:00
|
|
|
|
|
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
2008-11-13 14:49:15 -08:00
|
|
|
|
2013-07-03 15:00:59 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-07-03 15:01:00 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
ocfs2: throttle back local alloc when low on disk space
Ocfs2's local allocator disables itself for the duration of a mount point
when it has trouble allocating a large enough area from the primary bitmap.
That can cause performance problems, especially for disks which were only
temporarily full or fragmented. This patch allows for the allocator to
shrink it's window first, before being disabled. Later, it can also be
re-enabled so that any performance drop is minimized.
To do this, we allow the value of osb->local_alloc_bits to be shrunk when
needed. The default value is recorded in a mostly read-only variable so that
we can re-initialize when required.
Locking had to be updated so that we could protect changes to
local_alloc_bits. Mostly this involves protecting various local alloc values
with the osb spinlock. A new state is also added, OCFS2_LA_THROTTLED, which
is used when the local allocator is has shrunk, but is not disabled. If the
available space dips below 1 megabyte, the local alloc file is disabled. In
either case, local alloc is re-enabled 30 seconds after the event, or when
an appropriate amount of bits is seen in the primary bitmap.
Signed-off-by: Mark Fasheh <mfasheh@suse.com>
2008-07-28 18:02:53 -07:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-30 22:57:33 -03:00
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
|
|
|
|
|
2018-04-05 16:18:33 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2006-05-03 17:46:50 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-09-03 20:03:39 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-01-21 15:48:33 -08:00
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
2008-10-17 19:25:01 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-04-03 14:47:10 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2012-04-13 12:30:02 -04:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
2014-04-03 14:47:10 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2014-04-03 14:47:10 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2008-10-07 14:25:16 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-03-26 10:08:27 +08:00
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-02-27 17:02:49 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:16 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2014-04-03 14:47:10 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-10-07 14:25:16 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:07 +08:00
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:12 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2015-09-04 15:44:17 -07:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
tree-wide: fix comment/printk typos
"gadget", "through", "command", "maintain", "maintain", "controller", "address",
"between", "initiali[zs]e", "instead", "function", "select", "already",
"equal", "access", "management", "hierarchy", "registration", "interest",
"relative", "memory", "offset", "already",
Signed-off-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
Signed-off-by: Jiri Kosina <jkosina@suse.cz>
2010-11-01 15:38:34 -04:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2025-12-01 18:37:11 +05:30
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
ocfs2: improve performance for localalloc
Currently cluster allocation is always trying to find a victim chain (a
chian has most space), and this may lead to poor performance because of
discontiguous allocation in some scenarios.
Our test case is block size 4k, cluster size 1M and mount option with
localalloc=2048 (2G), since a gd is 32256M (about 31.5G) and a localalloc
window is only 2G, creating 50G file will result in 2G from gd0, 2G from
gd1, ...
One way to improve performance is enlarge localalloc window size (max
31104M), but this will make end user feel that about 30G is suddenly
"missing", and localalloc currently do not support steal, which means one
node cannot use another node's localalloc even it is not used in fact. So
using the last gd to record the allocation and continues with the gd if it
has enough space for a localalloc window can make the allocation as more
contiguous as possible.
Our test result is below (evaluated in IOPS), which is using iometer
running in VM, dynamic vhd virtual disk stored in ocfs2.
IO model Original After Improved(%)
16K60%Write100%Random 703 876 24.59%
8K90%Write100%Random 735 827 12.59%
4K100%Write100%Random 859 915 6.52%
4K100%Read100%Random 2092 2600 24.30%
Signed-off-by: Joseph Qi <joseph.qi@huawei.com>
Tested-by: Norton Zhu <norton.zhu@huawei.com>
Cc: Mark Fasheh <mfasheh@suse.de>
Cc: Joel Becker <jlbec@evilplan.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2015-11-05 18:43:58 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2013-02-27 17:02:49 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2024-03-28 20:52:02 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-08-26 13:06:50 -07:00
|
|
|
|
2006-06-05 16:41:00 -04:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:07 +08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
2010-04-27 08:30:36 +08:00
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
|
|
|
|
|
2010-04-27 08:30:36 +08:00
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-27 08:30:36 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
treewide: Replace kmalloc with kmalloc_obj for non-scalar types
This is the result of running the Coccinelle script from
scripts/coccinelle/api/kmalloc_objs.cocci. The script is designed to
avoid scalar types (which need careful case-by-case checking), and
instead replace kmalloc-family calls that allocate struct or union
object instances:
Single allocations: kmalloc(sizeof(TYPE), ...)
are replaced with: kmalloc_obj(TYPE, ...)
Array allocations: kmalloc_array(COUNT, sizeof(TYPE), ...)
are replaced with: kmalloc_objs(TYPE, COUNT, ...)
Flex array allocations: kmalloc(struct_size(PTR, FAM, COUNT), ...)
are replaced with: kmalloc_flex(*PTR, FAM, COUNT, ...)
(where TYPE may also be *VAR)
The resulting allocations no longer return "void *", instead returning
"TYPE *".
Signed-off-by: Kees Cook <kees@kernel.org>
2026-02-20 23:49:23 -08:00
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2014-04-03 14:47:08 -07:00
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
2014-04-03 14:47:10 -07:00
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2010-08-13 15:15:17 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:07 +08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-03-26 10:09:15 +08:00
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2009-02-25 00:53:23 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2007-12-18 15:47:03 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2007-09-16 20:10:16 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2007-09-16 20:10:16 -07:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-04-14 14:01:23 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-02-24 13:34:09 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2007-12-20 14:58:11 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-26 10:08:07 +08:00
|
|
|
|
2006-10-06 18:34:35 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-03-26 10:08:59 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-04-13 14:30:19 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-04-22 14:09:15 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2007-09-16 20:10:16 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-05-06 13:59:06 +08:00
|
|
|
|
2007-09-16 20:10:16 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2019-08-09 14:42:32 +02:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-11-13 14:49:15 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2019-08-09 14:42:32 +02:00
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
2019-08-09 14:42:32 +02:00
|
|
|
|
|
|
|
|
|
2009-06-19 14:45:54 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-10-05 15:53:06 -07:00
|
|
|
|
2018-01-31 16:15:29 -08:00
|
|
|
|
2019-08-09 14:42:32 +02:00
|
|
|
|
2015-09-04 15:44:51 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-10-05 15:53:06 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
2019-08-09 14:42:32 +02:00
|
|
|
|
2009-06-19 14:45:54 -07:00
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: fix cached cluster count after suballocator reclaim
When reclaiming a suballocator block group, first reduce the on-disk
cluster count by cl_cpg. The current code then subtracts that new count
(fe->i_clusters) from the old cached count
(OCFS2_I(alloc_inode)->ip_clusters).
For an allocator with N block groups, that leaves the cache at
N * cl_cpg - (N * cl_cpg - cl_cpg) = cl_cpg
i.e. ip_clusters -= (fe->i_clusters - cl_cpg) leaves ip_clusters equal to
cl_cpg regardless of N. This happens to be correct when reclaiming from
two block groups, but undercounts the clusters from three block groups
onwards. The incorrect cache value is also used immediately to update
i_blocks.
Assign the updated on-disk count to the cache, matching the allocation and
inode refresh paths.
In a QEMU test using a clean 256 MiB OCFS2 image and a 10,000-file
create/delete workload, the first buggy reclaim left the on-disk
(fe->i_clusters) and cached (ip_clusters) counts at 2048 and 512 clusters
respectively; later reclaims underflowed the cache. With this change, the
cache matched the on-disk count across all four reclaims: 2048, 1536,
1024, and 512 clusters.
Link: https://lore.kernel.org/20260805113920.385959-1-matthias.goergens@gmail.com
Fixes: 4a54331616b3 ("ocfs2: give ocfs2 the ability to reclaim suballocator free bg")
Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Mark Fasheh <mark@fasheh.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Heming Zhao <heming.zhao@suse.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2026-08-05 19:39:20 +08:00
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-11-13 14:49:12 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-30 22:57:33 -03:00
|
|
|
|
2008-11-13 14:49:12 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-11-13 14:49:14 -08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-02-12 16:41:25 -08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2015-04-14 15:43:27 -07:00
|
|
|
|
ocfs2: improve write IO performance when fragmentation is high
The group_search function ocfs2_cluster_group_search() should
bypass groups with insufficient space to avoid unnecessary
searches.
This patch is particularly useful when ocfs2 is handling huge
number small files, and volume fragmentation is very high.
In this case, ocfs2 is busy with looking up available la window
from //global_bitmap.
This patch introduces a new member in the Group Description (gd)
struct called 'bg_contig_free_bits', representing the max
contigous free bits in this gd. When ocfs2 allocates a new
la window from //global_bitmap, 'bg_contig_free_bits' helps
expedite the search process.
Let's image below path.
1. la state (->local_alloc_state) is set THROTTLED or DISABLED.
2. when user delete a large file and trigger
ocfs2_local_alloc_seen_free_bits set osb->local_alloc_state
unconditionally.
3. a write IOs thread run and trigger the worst performance path
```
ocfs2_reserve_clusters_with_limit
ocfs2_reserve_local_alloc_bits
ocfs2_local_alloc_slide_window //[1]
+ ocfs2_local_alloc_reserve_for_window //[2]
+ ocfs2_local_alloc_new_window //[3]
ocfs2_recalc_la_window
```
[1]:
will be called when la window bits used up.
[2]:
under la state is ENABLED, and this func only check global_bitmap
free bits, it will succeed in general.
[3]:
will use the default la window size to search clusters then fail.
ocfs2_recalc_la_window attempts other la window sizes.
the timing complexity is O(n^4), resulting in a significant time
cost for scanning global bitmap. This leads to a dramatic slowdown
in write I/Os (e.g., user space 'dd').
i.e.
an ocfs2 partition size: 1.45TB, cluster size: 4KB,
la window default size: 106MB.
The partition is fragmentation by creating & deleting huge mount of
small files.
before this patch, the timing of [3] should be
(the number got from real world):
- la window size change order (size: MB):
106, 53, 26.5, 13, 6.5, 3.25, 1.6, 0.8
only 0.8MB succeed, 0.8MB also triggers la window to disable.
ocfs2_local_alloc_new_window retries 8 times, first 7 times totally
runs in worst case.
- group chain number: 242
ocfs2_claim_suballoc_bits calls for-loop 242 times
- each chain has 49 block group
ocfs2_search_chain calls while-loop 49 times
- each bg has 32256 blocks
ocfs2_block_group_find_clear_bits calls while-loop for 32256 bits.
for ocfs2_find_next_zero_bit uses ffz() to find zero bit, let's use
(32256/64) (this is not worst value) for timing calucation.
the loop times: 7*242*49*(32256/64) = 41835024 (~42 million times)
In the worst case, user space writes 1MB data will trigger 42M scanning
times.
under this patch, the timing is '7*242*49 = 83006', reduced by three
orders of magnitude.
Link: https://lkml.kernel.org/r/20240328125203.20892-2-heming.zhao@suse.com
Signed-off-by: Heming Zhao <heming.zhao@suse.com>
Reviewed-by: Joseph Qi <joseph.qi@linux.alibaba.com>
Cc: Changwei Ge <gechangwei@live.cn>
Cc: Gang He <ghe@suse.com>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: Jun Piao <piaojun@huawei.com>
Cc: Junxiao Bi <junxiao.bi@oracle.com>
Cc: Mark Fasheh <mark@fasheh.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
2024-03-28 20:52:00 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
2010-03-19 14:13:52 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2025-12-12 15:45:03 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2008-10-07 14:25:16 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2006-10-09 18:11:45 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-22 14:20:18 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-21 11:10:44 +08:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2018-01-31 16:14:40 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ocfs2: throttle back local alloc when low on disk space
Ocfs2's local allocator disables itself for the duration of a mount point
when it has trouble allocating a large enough area from the primary bitmap.
That can cause performance problems, especially for disks which were only
temporarily full or fragmented. This patch allows for the allocator to
shrink it's window first, before being disabled. Later, it can also be
re-enabled so that any performance drop is minimized.
To do this, we allow the value of osb->local_alloc_bits to be shrunk when
needed. The default value is recorded in a mostly read-only variable so that
we can re-initialize when required.
Locking had to be updated so that we could protect changes to
local_alloc_bits. Mostly this involves protecting various local alloc values
with the osb spinlock. A new state is also added, OCFS2_LA_THROTTLED, which
is used when the local allocator is has shrunk, but is not disabled. If the
available space dips below 1 megabyte, the local alloc file is disabled. In
either case, local alloc is re-enabled 30 seconds after the event, or when
an appropriate amount of bits is seen in the primary bitmap.
Signed-off-by: Mark Fasheh <mfasheh@suse.com>
2008-07-28 18:02:53 -07:00
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
ocfs2: throttle back local alloc when low on disk space
Ocfs2's local allocator disables itself for the duration of a mount point
when it has trouble allocating a large enough area from the primary bitmap.
That can cause performance problems, especially for disks which were only
temporarily full or fragmented. This patch allows for the allocator to
shrink it's window first, before being disabled. Later, it can also be
re-enabled so that any performance drop is minimized.
To do this, we allow the value of osb->local_alloc_bits to be shrunk when
needed. The default value is recorded in a mostly read-only variable so that
we can re-initialize when required.
Locking had to be updated so that we could protect changes to
local_alloc_bits. Mostly this involves protecting various local alloc values
with the osb spinlock. A new state is also added, OCFS2_LA_THROTTLED, which
is used when the local allocator is has shrunk, but is not disabled. If the
available space dips below 1 megabyte, the local alloc file is disabled. In
either case, local alloc is re-enabled 30 seconds after the event, or when
an appropriate amount of bits is seen in the primary bitmap.
Signed-off-by: Mark Fasheh <mfasheh@suse.com>
2008-07-28 18:02:53 -07:00
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
ocfs2: throttle back local alloc when low on disk space
Ocfs2's local allocator disables itself for the duration of a mount point
when it has trouble allocating a large enough area from the primary bitmap.
That can cause performance problems, especially for disks which were only
temporarily full or fragmented. This patch allows for the allocator to
shrink it's window first, before being disabled. Later, it can also be
re-enabled so that any performance drop is minimized.
To do this, we allow the value of osb->local_alloc_bits to be shrunk when
needed. The default value is recorded in a mostly read-only variable so that
we can re-initialize when required.
Locking had to be updated so that we could protect changes to
local_alloc_bits. Mostly this involves protecting various local alloc values
with the osb spinlock. A new state is also added, OCFS2_LA_THROTTLED, which
is used when the local allocator is has shrunk, but is not disabled. If the
available space dips below 1 megabyte, the local alloc file is disabled. In
either case, local alloc is re-enabled 30 seconds after the event, or when
an appropriate amount of bits is seen in the primary bitmap.
Signed-off-by: Mark Fasheh <mfasheh@suse.com>
2008-07-28 18:02:53 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2005-12-15 14:31:24 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-03-11 18:31:09 -08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-08-18 17:38:44 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-08-20 19:36:33 -07:00
|
|
|
|
|
|
|
|
|
2008-08-18 17:38:44 +08:00
|
|
|
|
|
|
|
|
|
2008-08-20 19:36:33 -07:00
|
|
|
|
2008-08-18 17:38:44 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2017-09-06 16:19:11 -07:00
|
|
|
|
2008-08-18 17:38:44 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2008-08-20 19:36:33 -07:00
|
|
|
|
2008-08-18 17:38:44 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-04-21 16:31:20 -07:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-04-21 16:31:20 -07:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-03-19 05:08:43 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
2009-04-21 16:31:20 -07:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
2010-04-27 08:30:36 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:04 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
2010-04-27 08:30:36 +08:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
2010-04-27 08:30:36 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:04 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-04-21 16:31:20 -07:00
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:04 +08:00
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:04 +08:00
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2011-02-22 08:22:33 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2020-06-25 20:29:37 -07:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2016-01-22 15:40:57 -05:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
2016-01-22 15:40:57 -05:00
|
|
|
|
2014-04-03 14:47:12 -07:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2010-09-02 13:10:10 +08:00
|
|
|
|
2025-12-12 15:45:04 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
2016-01-22 15:40:57 -05:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2025-12-12 15:45:04 +08:00
|
|
|
|
2011-03-07 16:43:21 +08:00
|
|
|
|
2009-03-06 21:29:10 +08:00
|
|
|
|
|
|
|
|
|