* [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() @ 2021-12-09 11:10 Jia-Ju Bai 2021-12-09 17:00 ` Theodore Y. Ts'o 0 siblings, 1 reply; 5+ messages in thread From: Jia-Ju Bai @ 2021-12-09 11:10 UTC (permalink / raw) To: tytso, adilger.kernel; +Cc: linux-ext4, linux-kernel Hello, My static analysis tool reports a possible ABBA deadlock in the ext4 module in Linux 5.10: ext4_inline_data_truncate() down_write(&EXT4_I(inode)->i_data_sem); --> Line 1895 (Lock A) ext4_xattr_ibody_get() ext4_xattr_inode_get() ext4_xattr_inode_iget() inode_lock(inode); --> Line 427 (Lock B) ext4_punch_hole() inode_lock(inode); --> Line 4018 (Lock B) ext4_update_disksize_before_punch() ext4_update_i_disksize() down_write(&EXT4_I(inode)->i_data_sem); --> Line 3248 (Lock A) When ext4_inline_data_truncate() and ext4_punch_hole() are concurrently executed, the deadlock can occur. I am not quite sure whether this possible deadlock is real and how to fix it if it is real. Any feedback would be appreciated, thanks :) Reported-by: TOTE Robot <oslab@tsinghua.edu.cn> Best wishes, Jia-Ju Bai ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() 2021-12-09 11:10 [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() Jia-Ju Bai @ 2021-12-09 17:00 ` Theodore Y. Ts'o 2021-12-10 2:03 ` Jia-Ju Bai 0 siblings, 1 reply; 5+ messages in thread From: Theodore Y. Ts'o @ 2021-12-09 17:00 UTC (permalink / raw) To: Jia-Ju Bai; +Cc: adilger.kernel, linux-ext4, linux-kernel On Thu, Dec 09, 2021 at 07:10:44PM +0800, Jia-Ju Bai wrote: > Hello, > > My static analysis tool reports a possible ABBA deadlock in the ext4 module > in Linux 5.10: > > ext4_inline_data_truncate() > down_write(&EXT4_I(inode)->i_data_sem); --> Line 1895 (Lock A) > ext4_xattr_ibody_get() > ext4_xattr_inode_get() > ext4_xattr_inode_iget() > inode_lock(inode); --> Line 427 (Lock B) > > ext4_punch_hole() > inode_lock(inode); --> Line 4018 (Lock B) > ext4_update_disksize_before_punch() > ext4_update_i_disksize() > down_write(&EXT4_I(inode)->i_data_sem); --> Line 3248 (Lock A) > > When ext4_inline_data_truncate() and ext4_punch_hole() are concurrently > executed, the deadlock can occur. > > I am not quite sure whether this possible deadlock is real and how to fix it > if it is real. Hi, Thanks for the report. I don't believe this is deadlock is possible, because the first thing ext4_punch_hole() does is to check to see if the inode has inline data --- and if so, it calls ext4_convert_inline_data() to convert it to a normal file. In ext4_convert_inline_data(), we take the xattr lock, and then do the conversion, and then drop the xattr lock. So by the time ext4_punch_hole() starts doing its work, the inode is not an inline data file. In ext4_inline_data_truncate(), we take the xattr lock, and once we have the xattr lock, we check to see if inode is still an inline data file. If it has been converted, we then bail out. Hence, the ABBA deadlock that your static analysis tool has pointed shouldn't happen in practice. Cheers, - Ted ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() 2021-12-09 17:00 ` Theodore Y. Ts'o @ 2021-12-10 2:03 ` Jia-Ju Bai 2021-12-10 18:05 ` Theodore Y. Ts'o 0 siblings, 1 reply; 5+ messages in thread From: Jia-Ju Bai @ 2021-12-10 2:03 UTC (permalink / raw) To: Theodore Y. Ts'o; +Cc: adilger.kernel, linux-ext4, linux-kernel On 2021/12/10 1:00, Theodore Y. Ts'o wrote: > On Thu, Dec 09, 2021 at 07:10:44PM +0800, Jia-Ju Bai wrote: >> Hello, >> >> My static analysis tool reports a possible ABBA deadlock in the ext4 module >> in Linux 5.10: >> >> ext4_inline_data_truncate() >> down_write(&EXT4_I(inode)->i_data_sem); --> Line 1895 (Lock A) >> ext4_xattr_ibody_get() >> ext4_xattr_inode_get() >> ext4_xattr_inode_iget() >> inode_lock(inode); --> Line 427 (Lock B) >> >> ext4_punch_hole() >> inode_lock(inode); --> Line 4018 (Lock B) >> ext4_update_disksize_before_punch() >> ext4_update_i_disksize() >> down_write(&EXT4_I(inode)->i_data_sem); --> Line 3248 (Lock A) >> >> When ext4_inline_data_truncate() and ext4_punch_hole() are concurrently >> executed, the deadlock can occur. >> >> I am not quite sure whether this possible deadlock is real and how to fix it >> if it is real. > Hi, > > Thanks for the report. I don't believe this is deadlock is possible, > because the first thing ext4_punch_hole() does is to check to see if > the inode has inline data --- and if so, it calls > ext4_convert_inline_data() to convert it to a normal file. In > ext4_convert_inline_data(), we take the xattr lock, and then do the > conversion, and then drop the xattr lock. So by the time > ext4_punch_hole() starts doing its work, the inode is not an inline > data file. > > In ext4_inline_data_truncate(), we take the xattr lock, and once we > have the xattr lock, we check to see if inode is still an inline data > file. If it has been converted, we then bail out. > > Hence, the ABBA deadlock that your static analysis tool has pointed > shouldn't happen in practice. Hi Ted, Thank you very much for the detailed explanation! I will improve my static analysis tool for this point. Best wishes, Jia-Ju Bai ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() 2021-12-10 2:03 ` Jia-Ju Bai @ 2021-12-10 18:05 ` Theodore Y. Ts'o 2021-12-12 12:56 ` Jia-Ju Bai 0 siblings, 1 reply; 5+ messages in thread From: Theodore Y. Ts'o @ 2021-12-10 18:05 UTC (permalink / raw) To: Jia-Ju Bai; +Cc: adilger.kernel, linux-ext4, linux-kernel On Fri, Dec 10, 2021 at 10:03:37AM +0800, Jia-Ju Bai wrote: > > Thank you very much for the detailed explanation! > I will improve my static analysis tool for this point. I'm not sure it will be possible to programatically detect why the ABBA deadlock isn't possible without having the static analyzer having a semantic understanding how the code works (so it can understand that that code path which leads to the ABBA deadlock won't get executed). It may very well be that being able to understand why the ABBA deadlock can't happen in that case is equivalent to solving the halting problem. But if you do come up with a clever way of improving your static analysis tool, I'll be excited to see it! Cheers, - Ted ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() 2021-12-10 18:05 ` Theodore Y. Ts'o @ 2021-12-12 12:56 ` Jia-Ju Bai 0 siblings, 0 replies; 5+ messages in thread From: Jia-Ju Bai @ 2021-12-12 12:56 UTC (permalink / raw) To: Theodore Y. Ts'o; +Cc: adilger.kernel, linux-ext4, linux-kernel On 2021/12/11 2:05, Theodore Y. Ts'o wrote: > On Fri, Dec 10, 2021 at 10:03:37AM +0800, Jia-Ju Bai wrote: >> Thank you very much for the detailed explanation! >> I will improve my static analysis tool for this point. > I'm not sure it will be possible to programatically detect why the > ABBA deadlock isn't possible without having the static analyzer having > a semantic understanding how the code works (so it can understand that > that code path which leads to the ABBA deadlock won't get executed). > > It may very well be that being able to understand why the ABBA > deadlock can't happen in that case is equivalent to solving the > halting problem. But if you do come up with a clever way of improving > your static analysis tool, I'll be excited to see it! Hi Ted, Thanks a lot for your advice! According to your last message, ext4_punch_hole() and ext4_inline_data_truncate() both call ext4_has_inline_data() to check whether the inode has inline data. In ext4_inline_data_truncate(), when ext4_has_inline_data() returns zero, the function returns. In ext4_punch_hole(), when ext4_has_inline_data() returns zero, the function continues. Thus, I think I can add such "concurrency" path conditions in my tool to filter out false positives, by assuming that the same function calls or data structure fields should return/store the same value in concurrency code paths without race conditions. In fact, my tool can validate path conditions of each sequential code path. I can find ways to validate "concurrency" path conditions in my tool :) Best wishes, Jia-Ju Bai ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2021-12-12 12:57 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-12-09 11:10 [BUG] fs: ext4: possible ABBA deadlock in ext4_inline_data_truncate() and ext4_punch_hole() Jia-Ju Bai 2021-12-09 17:00 ` Theodore Y. Ts'o 2021-12-10 2:03 ` Jia-Ju Bai 2021-12-10 18:05 ` Theodore Y. Ts'o 2021-12-12 12:56 ` Jia-Ju Bai
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).