PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Toralf Förster]

Happened today few times in a row at a stable 64 bit Gentoo hardened system:



Nov 27 10:23:09 t44 kernel: [41619.519921] PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238 cicus.107_102 max, count: 13, decl: block_len; num: 0; context: extent_map;
Nov 27 10:23:09 t44 kernel: [41619.519929] CPU: 2 PID: 3361 Comm: host_jskwgen Tainted: G        W       4.2.6-hardened-r6 #3
Nov 27 10:23:09 t44 kernel: [41619.519932] Hardware name: LENOVO 20AQCTO1WW/20AQCTO1WW, BIOS GJET83WW (2.33 ) 03/09/2015
Nov 27 10:23:09 t44 kernel: [41619.519934]  ffffffff81831343 0000000000000000 ffffffff8183132d ffffc9000298b6e8
Nov 27 10:23:09 t44 kernel: [41619.519939]  ffffffff815ee0ea ffff88033e30eec8 ffffffff81831343 ffffc9000298b718
Nov 27 10:23:09 t44 kernel: [41619.519943]  ffffffff811ade1b ffff8802fb611480 ffff88032b717510 ffff88032b74fae0
Nov 27 10:23:09 t44 kernel: [41619.519946] Call Trace:
Nov 27 10:23:09 t44 kernel: [41619.519955]  [<ffffffff815ee0ea>] dump_stack+0x45/0x5d
Nov 27 10:23:09 t44 kernel: [41619.519959]  [<ffffffff811ade1b>] report_size_overflow+0x3b/0x50
Nov 27 10:23:09 t44 kernel: [41619.519963]  [<ffffffff8128c701>] try_merge_map+0x1f1/0x310
Nov 27 10:23:09 t44 kernel: [41619.519966]  [<ffffffff8128ca82>] add_extent_mapping+0x132/0x1c0
Nov 27 10:23:09 t44 kernel: [41619.519968]  [<ffffffff81273ea9>] btrfs_get_extent+0x659/0xdd0
Nov 27 10:23:09 t44 kernel: [41619.519972]  [<ffffffff81197b72>] ? kmem_cache_alloc+0x32/0x140
Nov 27 10:23:09 t44 kernel: [41619.519975]  [<ffffffff81297292>] __do_readpage+0x6f2/0xc30
Nov 27 10:23:09 t44 kernel: [41619.519977]  [<ffffffff8129353e>] ? __set_extent_bit+0x14e/0x580
Nov 27 10:23:09 t44 kernel: [41619.519979]  [<ffffffff81273850>] ? btrfs_real_readdir+0x6f0/0x6f0
Nov 27 10:23:09 t44 kernel: [41619.519983]  [<ffffffff815f4869>] ? _raw_spin_unlock_irq+0x19/0x30
Nov 27 10:23:09 t44 kernel: [41619.519985]  [<ffffffff81290e92>] ? btrfs_lookup_ordered_extent+0xa2/0xe0
Nov 27 10:23:09 t44 kernel: [41619.519987]  [<ffffffff812979a6>] __extent_read_full_page+0x1d6/0x210
Nov 27 10:23:09 t44 kernel: [41619.519989]  [<ffffffff81273850>] ? btrfs_real_readdir+0x6f0/0x6f0
Nov 27 10:23:09 t44 kernel: [41619.519991]  [<ffffffff81273850>] ? btrfs_real_readdir+0x6f0/0x6f0
Nov 27 10:23:09 t44 kernel: [41619.519993]  [<ffffffff812990bf>] extent_read_full_page+0x4f/0x80
Nov 27 10:23:09 t44 kernel: [41619.519997]  [<ffffffff81155cf9>] ? lru_cache_add+0x19/0x30
Nov 27 10:23:09 t44 kernel: [41619.519999]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
Nov 27 10:23:09 t44 kernel: [41619.520000]  [<ffffffff81270af4>] btrfs_readpage+0x34/0x50
Nov 27 10:23:09 t44 kernel: [41619.520002]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
Nov 27 10:23:09 t44 kernel: [41619.520004]  [<ffffffff81147919>] do_read_cache_page+0x99/0x1b0
Nov 27 10:23:09 t44 kernel: [41619.520006]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
Nov 27 10:23:09 t44 kernel: [41619.520008]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
Nov 27 10:23:09 t44 kernel: [41619.520009]  [<ffffffff81147a68>] read_cache_page+0x38/0x50
Nov 27 10:23:09 t44 kernel: [41619.520012]  [<ffffffff811b4d4a>] page_getlink.isra.48.constprop.51+0x3a/0xa0
Nov 27 10:23:09 t44 kernel: [41619.520014]  [<ffffffff811b4ddb>] page_follow_link_light+0x2b/0x50
Nov 27 10:23:09 t44 kernel: [41619.520016]  [<ffffffff811b557f>] trailing_symlink+0x27f/0x2b0
Nov 27 10:23:09 t44 kernel: [41619.520019]  [<ffffffff811b85db>] path_openat+0x16b/0x1700
Nov 27 10:23:09 t44 kernel: [41619.520021]  [<ffffffff811bae21>] do_filp_open+0x81/0xf0
Nov 27 10:23:09 t44 kernel: [41619.520024]  [<ffffffff811a4cc3>] do_sys_open+0x133/0x280
Nov 27 10:23:09 t44 kernel: [41619.520026]  [<ffffffff811a4e41>] SyS_open+0x31/0x50
Nov 27 10:23:09 t44 kernel: [41619.520028]  [<ffffffff815f5119>] entry_SYSCALL_64_fastpath+0x12/0x83


Furthermore  neither login into the KDE screen saver nor login at the console could be made, sys-rq keys didn't worked  - power off was my friend.



-- 
Toralf, pgp: C4EACDDE 0076E94E

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Filipe Manana]

On Fri, Nov 27, 2015 at 10:47 AM, Toralf Förster <toralf.foerster@gmx.de> wrote:
> Happened today few times in a row at a stable 64 bit Gentoo hardened system:
>
>
>
> Nov 27 10:23:09 t44 kernel: [41619.519921] PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238 cicus.107_102 max, count: 13, decl: block_len; num: 0; context: extent_map;
> Nov 27 10:23:09 t44 kernel: [41619.519929] CPU: 2 PID: 3361 Comm: host_jskwgen Tainted: G        W       4.2.6-hardened-r6 #3
> Nov 27 10:23:09 t44 kernel: [41619.519932] Hardware name: LENOVO 20AQCTO1WW/20AQCTO1WW, BIOS GJET83WW (2.33 ) 03/09/2015
> Nov 27 10:23:09 t44 kernel: [41619.519934]  ffffffff81831343 0000000000000000 ffffffff8183132d ffffc9000298b6e8
> Nov 27 10:23:09 t44 kernel: [41619.519939]  ffffffff815ee0ea ffff88033e30eec8 ffffffff81831343 ffffc9000298b718
> Nov 27 10:23:09 t44 kernel: [41619.519943]  ffffffff811ade1b ffff8802fb611480 ffff88032b717510 ffff88032b74fae0
> Nov 27 10:23:09 t44 kernel: [41619.519946] Call Trace:
> Nov 27 10:23:09 t44 kernel: [41619.519955]  [<ffffffff815ee0ea>] dump_stack+0x45/0x5d
> Nov 27 10:23:09 t44 kernel: [41619.519959]  [<ffffffff811ade1b>] report_size_overflow+0x3b/0x50
> Nov 27 10:23:09 t44 kernel: [41619.519963]  [<ffffffff8128c701>] try_merge_map+0x1f1/0x310
> Nov 27 10:23:09 t44 kernel: [41619.519966]  [<ffffffff8128ca82>] add_extent_mapping+0x132/0x1c0
> Nov 27 10:23:09 t44 kernel: [41619.519968]  [<ffffffff81273ea9>] btrfs_get_extent+0x659/0xdd0
> Nov 27 10:23:09 t44 kernel: [41619.519972]  [<ffffffff81197b72>] ? kmem_cache_alloc+0x32/0x140
> Nov 27 10:23:09 t44 kernel: [41619.519975]  [<ffffffff81297292>] __do_readpage+0x6f2/0xc30
> Nov 27 10:23:09 t44 kernel: [41619.519977]  [<ffffffff8129353e>] ? __set_extent_bit+0x14e/0x580
> Nov 27 10:23:09 t44 kernel: [41619.519979]  [<ffffffff81273850>] ? btrfs_real_readdir+0x6f0/0x6f0
> Nov 27 10:23:09 t44 kernel: [41619.519983]  [<ffffffff815f4869>] ? _raw_spin_unlock_irq+0x19/0x30
> Nov 27 10:23:09 t44 kernel: [41619.519985]  [<ffffffff81290e92>] ? btrfs_lookup_ordered_extent+0xa2/0xe0
> Nov 27 10:23:09 t44 kernel: [41619.519987]  [<ffffffff812979a6>] __extent_read_full_page+0x1d6/0x210
> Nov 27 10:23:09 t44 kernel: [41619.519989]  [<ffffffff81273850>] ? btrfs_real_readdir+0x6f0/0x6f0
> Nov 27 10:23:09 t44 kernel: [41619.519991]  [<ffffffff81273850>] ? btrfs_real_readdir+0x6f0/0x6f0
> Nov 27 10:23:09 t44 kernel: [41619.519993]  [<ffffffff812990bf>] extent_read_full_page+0x4f/0x80
> Nov 27 10:23:09 t44 kernel: [41619.519997]  [<ffffffff81155cf9>] ? lru_cache_add+0x19/0x30
> Nov 27 10:23:09 t44 kernel: [41619.519999]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
> Nov 27 10:23:09 t44 kernel: [41619.520000]  [<ffffffff81270af4>] btrfs_readpage+0x34/0x50
> Nov 27 10:23:09 t44 kernel: [41619.520002]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
> Nov 27 10:23:09 t44 kernel: [41619.520004]  [<ffffffff81147919>] do_read_cache_page+0x99/0x1b0
> Nov 27 10:23:09 t44 kernel: [41619.520006]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
> Nov 27 10:23:09 t44 kernel: [41619.520008]  [<ffffffff81270ac0>] ? inode_tree_add+0x150/0x150
> Nov 27 10:23:09 t44 kernel: [41619.520009]  [<ffffffff81147a68>] read_cache_page+0x38/0x50
> Nov 27 10:23:09 t44 kernel: [41619.520012]  [<ffffffff811b4d4a>] page_getlink.isra.48.constprop.51+0x3a/0xa0
> Nov 27 10:23:09 t44 kernel: [41619.520014]  [<ffffffff811b4ddb>] page_follow_link_light+0x2b/0x50
> Nov 27 10:23:09 t44 kernel: [41619.520016]  [<ffffffff811b557f>] trailing_symlink+0x27f/0x2b0
> Nov 27 10:23:09 t44 kernel: [41619.520019]  [<ffffffff811b85db>] path_openat+0x16b/0x1700
> Nov 27 10:23:09 t44 kernel: [41619.520021]  [<ffffffff811bae21>] do_filp_open+0x81/0xf0
> Nov 27 10:23:09 t44 kernel: [41619.520024]  [<ffffffff811a4cc3>] do_sys_open+0x133/0x280
> Nov 27 10:23:09 t44 kernel: [41619.520026]  [<ffffffff811a4e41>] SyS_open+0x31/0x50
> Nov 27 10:23:09 t44 kernel: [41619.520028]  [<ffffffff815f5119>] entry_SYSCALL_64_fastpath+0x12/0x83

Try the following (also pasted at
https://friendpaste.com/5O6o1cqWqJZDIKrH1YqG7y):

diff --git a/fs/btrfs/extent_map.c b/fs/btrfs/extent_map.c
index 6a98bdd..26b4c13 100644
--- a/fs/btrfs/extent_map.c
+++ b/fs/btrfs/extent_map.c
@@ -235,7 +235,8 @@ static void try_merge_map(struct extent_map_tree
*tree, struct extent_map *em)
                        em->start = merge->start;
                        em->orig_start = merge->orig_start;
                        em->len += merge->len;
-                       em->block_len += merge->block_len;
+                       if (em->block_start != EXTENT_MAP_HOLE)
+                               em->block_len += merge->block_len;
                        em->block_start = merge->block_start;
                        em->mod_len = (em->mod_len + em->mod_start) -
merge->mod_start;
                        em->mod_start = merge->mod_start;
@@ -252,7 +253,8 @@ static void try_merge_map(struct extent_map_tree
*tree, struct extent_map *em)
                merge = rb_entry(rb, struct extent_map, rb_node);
        if (rb && mergable_maps(em, merge)) {
                em->len += merge->len;
-               em->block_len += merge->block_len;
+               if (em->block_start != EXTENT_MAP_HOLE)
+                       em->block_len += merge->block_len;
                rb_erase(&merge->rb_node, &tree->map);
                RB_CLEAR_NODE(&merge->rb_node);
                em->mod_len = (merge->mod_start + merge->mod_len) -
em->mod_start;

>
>
> Furthermore  neither login into the KDE screen saver nor login at the console could be made, sys-rq keys didn't worked  - power off was my friend.
>
>
>
> --
> Toralf, pgp: C4EACDDE 0076E94E
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Filipe David Manana,

"Reasonable men adapt themselves to the world.
 Unreasonable men adapt the world to themselves.
 That's why all progress depends on unreasonable men."

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Toralf Förster]

On 11/27/2015 12:07 PM, Filipe Manana wrote:
> Try the following (also pasted at
> https://friendpaste.com/5O6o1cqWqJZDIKrH1YqG7y):

Doesn't apply neither against the used 4.2.6 kernel nor aginst current git HEAD :

t44 linux # patch -p1 --dry-run < /home/tfoerste/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
checking file fs/btrfs/extent_map.c
Hunk #1 FAILED at 235.
Hunk #2 FAILED at 252.
2 out of 2 hunks FAILED


tfoerste@t44 ~/devel/linux $ patch -p1 --dry-run < ~/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
checking file fs/btrfs/extent_map.c
Hunk #1 FAILED at 235.
Hunk #2 FAILED at 252.
2 out of 2 hunks FAILED

-- 
Toralf, pgp: C4EACDDE 0076E94E

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Filipe Manana]

On Fri, Nov 27, 2015 at 11:20 AM, Toralf Förster <toralf.foerster@gmx.de> wrote:
> On 11/27/2015 12:07 PM, Filipe Manana wrote:
>> Try the following (also pasted at
>> https://friendpaste.com/5O6o1cqWqJZDIKrH1YqG7y):
>
> Doesn't apply neither against the used 4.2.6 kernel nor aginst current git HEAD :

Quite probable, this was against the integration branch for btrfs.
You should be able to apply it manually, it's a trivial change and
extent_map.c did not change in any significant way.

>
> t44 linux # patch -p1 --dry-run < /home/tfoerste/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
> checking file fs/btrfs/extent_map.c
> Hunk #1 FAILED at 235.
> Hunk #2 FAILED at 252.
> 2 out of 2 hunks FAILED
>
>
> tfoerste@t44 ~/devel/linux $ patch -p1 --dry-run < ~/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
> checking file fs/btrfs/extent_map.c
> Hunk #1 FAILED at 235.
> Hunk #2 FAILED at 252.
> 2 out of 2 hunks FAILED
>
> --
> Toralf, pgp: C4EACDDE 0076E94E



-- 
Filipe David Manana,

"Reasonable men adapt themselves to the world.
 Unreasonable men adapt the world to themselves.
 That's why all progress depends on unreasonable men."

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Holger Hoffstätte]

On 11/27/15 12:20, Toralf Förster wrote:
> On 11/27/2015 12:07 PM, Filipe Manana wrote:
>> Try the following (also pasted at
>> https://friendpaste.com/5O6o1cqWqJZDIKrH1YqG7y):
> 
> Doesn't apply neither against the used 4.2.6 kernel nor aginst current git HEAD :
> 
> t44 linux # patch -p1 --dry-run < /home/tfoerste/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
> checking file fs/btrfs/extent_map.c
> Hunk #1 FAILED at 235.
> Hunk #2 FAILED at 252.
> 2 out of 2 hunks FAILED
> 
> 
> tfoerste@t44 ~/devel/linux $ patch -p1 --dry-run < ~/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
> checking file fs/btrfs/extent_map.c
> Hunk #1 FAILED at 235.
> Hunk #2 FAILED at 252.
> 2 out of 2 hunks FAILED
> 

Toralf,

try with --ignore-whitespace, that works for me. Seems the pastebin ate
some formatting.

-h

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Filipe Manana]

On Fri, Nov 27, 2015 at 11:51 AM, Holger Hoffstätte
<holger.hoffstaette@googlemail.com> wrote:
> On 11/27/15 12:20, Toralf Förster wrote:
>> On 11/27/2015 12:07 PM, Filipe Manana wrote:
>>> Try the following (also pasted at
>>> https://friendpaste.com/5O6o1cqWqJZDIKrH1YqG7y):
>>
>> Doesn't apply neither against the used 4.2.6 kernel nor aginst current git HEAD :
>>
>> t44 linux # patch -p1 --dry-run < /home/tfoerste/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
>> checking file fs/btrfs/extent_map.c
>> Hunk #1 FAILED at 235.
>> Hunk #2 FAILED at 252.
>> 2 out of 2 hunks FAILED
>>
>>
>> tfoerste@t44 ~/devel/linux $ patch -p1 --dry-run < ~/Downloads/5O6o1cqWqJZDIKrH1YqG7y.diff.patch
>> checking file fs/btrfs/extent_map.c
>> Hunk #1 FAILED at 235.
>> Hunk #2 FAILED at 252.
>> 2 out of 2 hunks FAILED
>>
>
> Toralf,
>
> try with --ignore-whitespace, that works for me. Seems the pastebin ate
> some formatting.

Indeed.
Try the following instead:  http://paste.opensuse.org/view/raw/58412382

thanks

>
> -h
>



-- 
Filipe David Manana,

"Reasonable men adapt themselves to the world.
 Unreasonable men adapt the world to themselves.
 That's why all progress depends on unreasonable men."

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Toralf Förster]

On 11/27/2015 12:53 PM, Filipe Manana wrote:
> Indeed.
> Try the following instead:  http://paste.opensuse.org/view/raw/58412382

white-space damaged too, but the hint with --ingore- made it.

Will see, if it helps now. But FWIW the mentioned spew happened the first time here AFAICT.

-- 
Toralf, pgp: C4EACDDE 0076E94E

Re: PAX: size overflow detected in function try_merge_map fs/btrfs/extent_map.c:238

[Tristan Mahé]

[-- Attachment #1.1: Type: text/plain, Size: 2799 bytes --]

Compiled the patch on 4.2.6-hardened-r8 on gentoo 64bit and it's still
failing :/

[  182.316487] PAX: size overflow detected in function try_merge_map
fs/btrfs/extent_map.c:241 cicus.108_106 max, count: 13, decl: block_len;
num: 0; context: extent_map;
[  182.316490] CPU: 3 PID: 11196 Comm: insserv Tainted: G     U     O   
4.2.6-hardened-r8 #2
[  182.316491] Hardware name: LENOVO 20ANCTO1WW/20ANCTO1WW, BIOS
GLET78WW (2.32 ) 03/03/2015
[  182.316492]  ffffffff81c3f37d 0000000000000000 ffffffff81c3f367
ffffc90010403678
[  182.316493]  ffffffff819b9f6c ffff88043e2cec30 ffffffff81c3f37d
ffffc900104036a8
[  182.316494]  ffffffff81226d26 ffff880351bf4390 ffff8800aa2e84c0
ffff88041c8c32e8
[  182.316496] Call Trace:
[  182.316500]  [<ffffffff819b9f6c>] dump_stack+0x45/0x5d
[  182.316502]  [<ffffffff81226d26>] report_size_overflow+0x36/0x40
[  182.316504]  [<ffffffff814b293a>] try_merge_map+0x2ca/0x340
[  182.316505]  [<ffffffff814b2bed>] add_extent_mapping+0x12d/0x1b0
[  182.316507]  [<ffffffff8149a162>] btrfs_get_extent+0x6b2/0xe40
[  182.316509]  [<ffffffff814bcaf9>] __do_readpage+0x249/0xb90
[  182.316511]  [<ffffffff81499ab0>] ? btrfs_direct_IO+0x380/0x380
[  182.316512]  [<ffffffff814bd91d>]
__extent_readpages.constprop.36+0x2dd/0x320
[  182.316515]  [<ffffffff811ad7b5>] ?
__add_to_page_cache_locked+0x155/0x200
[  182.316516]  [<ffffffff81499ab0>] ? btrfs_direct_IO+0x380/0x380
[  182.316518]  [<ffffffff814bf562>] extent_readpages+0x1c2/0x1d0
[  182.316519]  [<ffffffff81499ab0>] ? btrfs_direct_IO+0x380/0x380
[  182.316522]  [<ffffffff811fd6ad>] ? alloc_pages_current+0x8d/0x100
[  182.316523]  [<ffffffff81497f15>] btrfs_readpages+0x35/0x50
[  182.316525]  [<ffffffff811bc895>] __do_page_cache_readahead+0x1b5/0x230
[  182.316526]  [<ffffffff811bc9fc>] ondemand_readahead+0xec/0x2e0
[  182.316528]  [<ffffffff811bcd2a>] page_cache_sync_readahead+0x4a/0x80
[  182.316529]  [<ffffffff811afe59>] generic_file_read_iter+0x5f9/0x790
[  182.316531]  [<ffffffff8121eba9>] __vfs_read+0xd9/0x100
[  182.316532]  [<ffffffff8121f620>] vfs_read+0xd0/0x230
[  182.316533]  [<ffffffff81220866>] SyS_read+0x46/0xb0
[  182.316534]  [<ffffffff819c1850>] entry_SYSCALL_64_fastpath+0x12/0x78


Very easy to reproduce here:

1/ install docker with btrfs as the storage driver
2/ start a debian 7 container ( /sbin/init as the command, openssh to be
able to ssh in )
3/ attempt to use insserv ( for example insserv -r -f ntpd )

Till a reboot, anything launched that will try to access what was in use
and caused the crash will hang.

And quick question, sorry I am not familiar at all with btrfs code, but
if em->block_start == EXTENT_MAP_HOLE then em->block_len is not updated
to its new value, wouldn't that be a source of trouble ?



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: extent_map.c --]
[-- Type: text/x-csrc; name="extent_map.c", Size: 12608 bytes --]

#include <linux/err.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/hardirq.h>
#include "ctree.h"
#include "extent_map.h"


static struct kmem_cache *extent_map_cache;

int __init extent_map_init(void)
{
	extent_map_cache = kmem_cache_create("btrfs_extent_map",
			sizeof(struct extent_map), 0,
			SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
	if (!extent_map_cache)
		return -ENOMEM;
	return 0;
}

void extent_map_exit(void)
{
	if (extent_map_cache)
		kmem_cache_destroy(extent_map_cache);
}

/**
 * extent_map_tree_init - initialize extent map tree
 * @tree:		tree to initialize
 *
 * Initialize the extent tree @tree.  Should be called for each new inode
 * or other user of the extent_map interface.
 */
void extent_map_tree_init(struct extent_map_tree *tree)
{
	tree->map = RB_ROOT;
	INIT_LIST_HEAD(&tree->modified_extents);
	rwlock_init(&tree->lock);
}

/**
 * alloc_extent_map - allocate new extent map structure
 *
 * Allocate a new extent_map structure.  The new structure is
 * returned with a reference count of one and needs to be
 * freed using free_extent_map()
 */
struct extent_map *alloc_extent_map(void)
{
	struct extent_map *em;
	em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
	if (!em)
		return NULL;
	RB_CLEAR_NODE(&em->rb_node);
	em->flags = 0;
	em->compress_type = BTRFS_COMPRESS_NONE;
	em->generation = 0;
	atomic_set(&em->refs, 1);
	INIT_LIST_HEAD(&em->list);
	return em;
}

/**
 * free_extent_map - drop reference count of an extent_map
 * @em:		extent map beeing releasead
 *
 * Drops the reference out on @em by one and free the structure
 * if the reference count hits zero.
 */
void free_extent_map(struct extent_map *em)
{
	if (!em)
		return;
	WARN_ON(atomic_read(&em->refs) == 0);
	if (atomic_dec_and_test(&em->refs)) {
		WARN_ON(extent_map_in_tree(em));
		WARN_ON(!list_empty(&em->list));
		if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
			kfree(em->bdev);
		kmem_cache_free(extent_map_cache, em);
	}
}

/* simple helper to do math around the end of an extent, handling wrap */
static u64 range_end(u64 start, u64 len)
{
	if (start + len < start)
		return (u64)-1;
	return start + len;
}

static int tree_insert(struct rb_root *root, struct extent_map *em)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct extent_map *entry = NULL;
	struct rb_node *orig_parent = NULL;
	u64 end = range_end(em->start, em->len);

	while (*p) {
		parent = *p;
		entry = rb_entry(parent, struct extent_map, rb_node);

		if (em->start < entry->start)
			p = &(*p)->rb_left;
		else if (em->start >= extent_map_end(entry))
			p = &(*p)->rb_right;
		else
			return -EEXIST;
	}

	orig_parent = parent;
	while (parent && em->start >= extent_map_end(entry)) {
		parent = rb_next(parent);
		entry = rb_entry(parent, struct extent_map, rb_node);
	}
	if (parent)
		if (end > entry->start && em->start < extent_map_end(entry))
			return -EEXIST;

	parent = orig_parent;
	entry = rb_entry(parent, struct extent_map, rb_node);
	while (parent && em->start < entry->start) {
		parent = rb_prev(parent);
		entry = rb_entry(parent, struct extent_map, rb_node);
	}
	if (parent)
		if (end > entry->start && em->start < extent_map_end(entry))
			return -EEXIST;

	rb_link_node(&em->rb_node, orig_parent, p);
	rb_insert_color(&em->rb_node, root);
	return 0;
}

/*
 * search through the tree for an extent_map with a given offset.  If
 * it can't be found, try to find some neighboring extents
 */
static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
				     struct rb_node **prev_ret,
				     struct rb_node **next_ret)
{
	struct rb_node *n = root->rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *orig_prev = NULL;
	struct extent_map *entry;
	struct extent_map *prev_entry = NULL;

	while (n) {
		entry = rb_entry(n, struct extent_map, rb_node);
		prev = n;
		prev_entry = entry;

		if (offset < entry->start)
			n = n->rb_left;
		else if (offset >= extent_map_end(entry))
			n = n->rb_right;
		else
			return n;
	}

	if (prev_ret) {
		orig_prev = prev;
		while (prev && offset >= extent_map_end(prev_entry)) {
			prev = rb_next(prev);
			prev_entry = rb_entry(prev, struct extent_map, rb_node);
		}
		*prev_ret = prev;
		prev = orig_prev;
	}

	if (next_ret) {
		prev_entry = rb_entry(prev, struct extent_map, rb_node);
		while (prev && offset < prev_entry->start) {
			prev = rb_prev(prev);
			prev_entry = rb_entry(prev, struct extent_map, rb_node);
		}
		*next_ret = prev;
	}
	return NULL;
}

/* check to see if two extent_map structs are adjacent and safe to merge */
static int mergable_maps(struct extent_map *prev, struct extent_map *next)
{
	if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
		return 0;

	/*
	 * don't merge compressed extents, we need to know their
	 * actual size
	 */
	if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
		return 0;

	if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) ||
	    test_bit(EXTENT_FLAG_LOGGING, &next->flags))
		return 0;

	/*
	 * We don't want to merge stuff that hasn't been written to the log yet
	 * since it may not reflect exactly what is on disk, and that would be
	 * bad.
	 */
	if (!list_empty(&prev->list) || !list_empty(&next->list))
		return 0;

	if (extent_map_end(prev) == next->start &&
	    prev->flags == next->flags &&
	    prev->bdev == next->bdev &&
	    ((next->block_start == EXTENT_MAP_HOLE &&
	      prev->block_start == EXTENT_MAP_HOLE) ||
	     (next->block_start == EXTENT_MAP_INLINE &&
	      prev->block_start == EXTENT_MAP_INLINE) ||
	     (next->block_start == EXTENT_MAP_DELALLOC &&
	      prev->block_start == EXTENT_MAP_DELALLOC) ||
	     (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
	      next->block_start == extent_map_block_end(prev)))) {
		return 1;
	}
	return 0;
}

static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
{
	struct extent_map *merge = NULL;
	struct rb_node *rb;

	if (em->start != 0) {
		rb = rb_prev(&em->rb_node);
		if (rb)
			merge = rb_entry(rb, struct extent_map, rb_node);
		if (rb && mergable_maps(merge, em)) {
			em->start = merge->start;
			em->orig_start = merge->orig_start;
			em->len += merge->len;
			// BREAKPOINT TRY TO PATCH BTRFS bug
			// em->block_len += merge->block_len;
			if (em->block_start != EXTENT_MAP_HOLE)
                        	em->block_len += merge->block_len;
			em->block_start = merge->block_start;
			em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
			em->mod_start = merge->mod_start;
			em->generation = max(em->generation, merge->generation);

			rb_erase(&merge->rb_node, &tree->map);
			RB_CLEAR_NODE(&merge->rb_node);
			free_extent_map(merge);
		}
	}

	rb = rb_next(&em->rb_node);
	if (rb)
		merge = rb_entry(rb, struct extent_map, rb_node);
	if (rb && mergable_maps(em, merge)) {
		em->len += merge->len;
		// BREAKPOINT TRY TO PATCH BTRFS bug
		// em->block_len += merge->block_len;
		if (em->block_start != EXTENT_MAP_HOLE)
			em->block_len += merge->block_len;
		rb_erase(&merge->rb_node, &tree->map);
		RB_CLEAR_NODE(&merge->rb_node);
		em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
		em->generation = max(em->generation, merge->generation);
		free_extent_map(merge);
	}
}

/**
 * unpin_extent_cache - unpin an extent from the cache
 * @tree:	tree to unpin the extent in
 * @start:	logical offset in the file
 * @len:	length of the extent
 * @gen:	generation that this extent has been modified in
 *
 * Called after an extent has been written to disk properly.  Set the generation
 * to the generation that actually added the file item to the inode so we know
 * we need to sync this extent when we call fsync().
 */
int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
		       u64 gen)
{
	int ret = 0;
	struct extent_map *em;
	bool prealloc = false;

	write_lock(&tree->lock);
	em = lookup_extent_mapping(tree, start, len);

	WARN_ON(!em || em->start != start);

	if (!em)
		goto out;

	em->generation = gen;
	clear_bit(EXTENT_FLAG_PINNED, &em->flags);
	em->mod_start = em->start;
	em->mod_len = em->len;

	if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
		prealloc = true;
		clear_bit(EXTENT_FLAG_FILLING, &em->flags);
	}

	try_merge_map(tree, em);

	if (prealloc) {
		em->mod_start = em->start;
		em->mod_len = em->len;
	}

	free_extent_map(em);
out:
	write_unlock(&tree->lock);
	return ret;

}

void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
{
	clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
	if (extent_map_in_tree(em))
		try_merge_map(tree, em);
}

static inline void setup_extent_mapping(struct extent_map_tree *tree,
					struct extent_map *em,
					int modified)
{
	atomic_inc(&em->refs);
	em->mod_start = em->start;
	em->mod_len = em->len;

	if (modified)
		list_move(&em->list, &tree->modified_extents);
	else
		try_merge_map(tree, em);
}

/**
 * add_extent_mapping - add new extent map to the extent tree
 * @tree:	tree to insert new map in
 * @em:		map to insert
 *
 * Insert @em into @tree or perform a simple forward/backward merge with
 * existing mappings.  The extent_map struct passed in will be inserted
 * into the tree directly, with an additional reference taken, or a
 * reference dropped if the merge attempt was successful.
 */
int add_extent_mapping(struct extent_map_tree *tree,
		       struct extent_map *em, int modified)
{
	int ret = 0;

	ret = tree_insert(&tree->map, em);
	if (ret)
		goto out;

	setup_extent_mapping(tree, em, modified);
out:
	return ret;
}

static struct extent_map *
__lookup_extent_mapping(struct extent_map_tree *tree,
			u64 start, u64 len, int strict)
{
	struct extent_map *em;
	struct rb_node *rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *next = NULL;
	u64 end = range_end(start, len);

	rb_node = __tree_search(&tree->map, start, &prev, &next);
	if (!rb_node) {
		if (prev)
			rb_node = prev;
		else if (next)
			rb_node = next;
		else
			return NULL;
	}

	em = rb_entry(rb_node, struct extent_map, rb_node);

	if (strict && !(end > em->start && start < extent_map_end(em)))
		return NULL;

	atomic_inc(&em->refs);
	return em;
}

/**
 * lookup_extent_mapping - lookup extent_map
 * @tree:	tree to lookup in
 * @start:	byte offset to start the search
 * @len:	length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.  There may be additional objects in the tree that
 * intersect, so check the object returned carefully to make sure that no
 * additional lookups are needed.
 */
struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{
	return __lookup_extent_mapping(tree, start, len, 1);
}

/**
 * search_extent_mapping - find a nearby extent map
 * @tree:	tree to lookup in
 * @start:	byte offset to start the search
 * @len:	length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.
 *
 * If one can't be found, any nearby extent may be returned
 */
struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{
	return __lookup_extent_mapping(tree, start, len, 0);
}

/**
 * remove_extent_mapping - removes an extent_map from the extent tree
 * @tree:	extent tree to remove from
 * @em:		extent map beeing removed
 *
 * Removes @em from @tree.  No reference counts are dropped, and no checks
 * are done to see if the range is in use
 */
int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
{
	int ret = 0;

	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
	rb_erase(&em->rb_node, &tree->map);
	if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
		list_del_init(&em->list);
	RB_CLEAR_NODE(&em->rb_node);
	return ret;
}

void replace_extent_mapping(struct extent_map_tree *tree,
			    struct extent_map *cur,
			    struct extent_map *new,
			    int modified)
{
	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags));
	ASSERT(extent_map_in_tree(cur));
	if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags))
		list_del_init(&cur->list);
	rb_replace_node(&cur->rb_node, &new->rb_node, &tree->map);
	RB_CLEAR_NODE(&cur->rb_node);

	setup_extent_mapping(tree, new, modified);
}

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]