From patchwork Wed Jun 1 15:51:40 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Feifei Xu X-Patchwork-Id: 9147727 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 3641D60761 for ; Wed, 1 Jun 2016 15:53:18 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0DD2A24B5B for ; Wed, 1 Jun 2016 15:53:18 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0250E26992; Wed, 1 Jun 2016 15:53:17 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E9A0124B5B for ; Wed, 1 Jun 2016 15:53:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754718AbcFAPxD (ORCPT ); Wed, 1 Jun 2016 11:53:03 -0400 Received: from e19.ny.us.ibm.com ([129.33.205.209]:58078 "EHLO e19.ny.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751648AbcFAPxB (ORCPT ); Wed, 1 Jun 2016 11:53:01 -0400 Received: from localhost by e19.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Wed, 1 Jun 2016 11:53:00 -0400 Received: from d01dlp01.pok.ibm.com (9.56.250.166) by e19.ny.us.ibm.com (146.89.104.206) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Wed, 1 Jun 2016 11:52:58 -0400 X-IBM-Helo: d01dlp01.pok.ibm.com X-IBM-MailFrom: xufeifei@linux.vnet.ibm.com X-IBM-RcptTo: jbacik@fb.com; feifeixu.sh@gmail.com; steve.capper@linaro.org; chandan@mykolab.com; dsterba@suse.com; linux-btrfs@vger.kernel.org Received: from b01cxnp22034.gho.pok.ibm.com (b01cxnp22034.gho.pok.ibm.com [9.57.198.24]) by d01dlp01.pok.ibm.com (Postfix) with ESMTP id DC1FA38C8078; Wed, 1 Jun 2016 11:52:24 -0400 (EDT) Received: from b01ledav006.gho.pok.ibm.com (b01ledav006.gho.pok.ibm.com [9.57.199.111]) by b01cxnp22034.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id u51FqNtA52101250; Wed, 1 Jun 2016 15:52:23 GMT Received: from b01ledav006.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 93B96AC041; Wed, 1 Jun 2016 11:52:23 -0400 (EDT) Received: from ip9-114-219-65.stglabs.ibm.com (unknown [9.114.219.66]) by b01ledav006.gho.pok.ibm.com (Postfix) with ESMTP id 7C3B9AC03C; Wed, 1 Jun 2016 11:52:23 -0400 (EDT) From: Feifei Xu To: linux-btrfs@vger.kernel.org Cc: steve.capper@linaro.org, chandan@mykolab.com, jbacik@fb.com, dsterba@suse.com, chandan@linux.vnet.ibm.com, feifeixu.sh@gmail.com, Feifei Xu Subject: [PATCH V2 1/8] Btrfs: test_check_exists: Fix infinite loop when searching for free space entries Date: Wed, 1 Jun 2016 15:51:40 +0000 Message-Id: <1464796307-67173-2-git-send-email-xufeifei@linux.vnet.ibm.com> X-Mailer: git-send-email 2.4.0 In-Reply-To: <1464796307-67173-1-git-send-email-xufeifei@linux.vnet.ibm.com> References: <1464796307-67173-1-git-send-email-xufeifei@linux.vnet.ibm.com> X-TM-AS-GCONF: 00 X-Content-Scanned: Fidelis XPS MAILER x-cbid: 16060115-0057-0000-0000-0000047C1F5B X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP On a ppc64 machine using 64K as the block size, assume that the RB tree at btrfs_free_space_ctl->free_space_offset contains following two entries: 1. A bitmap entry having an offset value of 0 and having the bits corresponding to the address range [128M+512K, 128M+768K] set. 2. An extent entry corresponding to the address range [128M-256K, 128M-128K] In such a scenario, test_check_exists() invoked for checking the existence of address range [128M+768K, 256M] can lead to an infinite loop as explained below: - Checking for the extent entry fails. - Checking for a bitmap entry results in the free space info in range [128M+512K, 128M+768K] beng returned. - rb_prev(info) returns NULL because the bitmap entry starting from offset 0 comes first in the RB tree. - current_node = bitmap node. - while (current_node) tmp = rb_next(bitmap_node);/*tmp is extent based free space entry*/ Since extent based free space entry's last address is smaller than the address being searched for (i.e. 128M+768K) we incorrectly again obtain the extent node as the "next right node" of the RB tree and thus end up looping infinitely. This patch fixes the issue by checking the "tmp" variable which point to the most recently searched free space node. Reviewed-by: Chandan Rajendra Signed-off-by: Feifei Xu --- fs/btrfs/free-space-cache.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c index c6dc118..fa62335 100644 --- a/fs/btrfs/free-space-cache.c +++ b/fs/btrfs/free-space-cache.c @@ -3662,7 +3662,7 @@ have_info: if (tmp->offset + tmp->bytes < offset) break; if (offset + bytes < tmp->offset) { - n = rb_prev(&info->offset_index); + n = rb_prev(&tmp->offset_index); continue; } info = tmp; @@ -3676,7 +3676,7 @@ have_info: if (offset + bytes < tmp->offset) break; if (tmp->offset + tmp->bytes < offset) { - n = rb_next(&info->offset_index); + n = rb_next(&tmp->offset_index); continue; } info = tmp;