From patchwork Sat Apr 13 21:50:49 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pierre Bourdon X-Patchwork-Id: 1085223 X-Patchwork-Delegate: trini@ti.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=lists.denx.de (client-ip=81.169.180.215; helo=lists.denx.de; envelope-from=u-boot-bounces@lists.denx.de; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="DTI8/Wda"; dkim-atps=neutral Received: from lists.denx.de (dione.denx.de [81.169.180.215]) by ozlabs.org (Postfix) with ESMTP id 44hT3c0vhhz9s70 for ; Sun, 14 Apr 2019 07:51:08 +1000 (AEST) Received: by lists.denx.de (Postfix, from userid 105) id BE763C21D9A; Sat, 13 Apr 2019 21:51:02 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on lists.denx.de X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=FREEMAIL_FROM, T_DKIM_INVALID autolearn=unavailable autolearn_force=no version=3.4.0 Received: from lists.denx.de (localhost [IPv6:::1]) by lists.denx.de (Postfix) with ESMTP id 7382DC21C93; Sat, 13 Apr 2019 21:51:00 +0000 (UTC) Received: by lists.denx.de (Postfix, from userid 105) id 05B1BC21C93; Sat, 13 Apr 2019 21:50:58 +0000 (UTC) Received: from mail-ed1-f68.google.com (mail-ed1-f68.google.com [209.85.208.68]) by lists.denx.de (Postfix) with ESMTPS id A54D5C21C4A for ; Sat, 13 Apr 2019 21:50:58 +0000 (UTC) Received: by mail-ed1-f68.google.com with SMTP id s39so11392532edb.2 for ; Sat, 13 Apr 2019 14:50:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=ltbkCN2/nFyZa+K/xE+nOboQFOLDog6sGQtlaOJL7CI=; b=DTI8/WdaM3gWmOtOdzPpaDMmi+VXqPr0JHEgO8VLRockoCkpCz7N9nWoOioaRsVw96 36ZLntQDhzuwE0nHZB0ppxxfxE7NpSGqzv1oITV73ybPqC3feami3qyUXgC+i2am6qQ4 lZlu1SYaHfFECkXRHONQm79H6NyDmTRczoEf0m2dBRnndgThwkARY2vtSWx262amrBhb CvD1uA0buJ/pEpW2CwOPw7JIRMVGoRBioyIpuntpdXc9XnaIKRYtpHx3jLSvRPfIgBOv MGKKP0bnW6otNOvI0plx6/ALvBuNFmYqsBquOrmdKjRL9xQBgOX3NxfbVkAXklcEYZY1 zBOw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=ltbkCN2/nFyZa+K/xE+nOboQFOLDog6sGQtlaOJL7CI=; b=rg3Z4Ie2qODp6fWZm7l7+ZWWIq/JjXquaxXEYNM8FzguhTDA70RfAMNtZo7xzmmK9x 6l8a6gFI3jNL7DBV7zGFCoU+tXXpDjxCOBPiVrzbEc9Hguv1RaPwXXvzhKkXiT4U9PFs mKNZVIpCfHNofzCaxoVqrfQBFyK/ZK/kVwarAYaGGKQ2Yq1N7ebbhomI6tmDDgpVKNue m5hsW5aguZ6jZA8qWJgKABHxlu6L2cOUNewvMn9pfE6xWNZ3KvURqcoLpEPJKpg4lS81 p+IFsVi07qS2HITqiqIFszrcY2fd4EIpeTV8GJn4gbPcz0AvUwbqSTuwEZquxc5ier4x Npsw== X-Gm-Message-State: APjAAAUOR17Q+4nYF/STQOqmfhuFbaJuHRJGYHPpXIzmEwBX8ezWTMJ9 wFJuhyP2AXD4blNqkTb9Xosk5LY9c2Q= X-Google-Smtp-Source: APXvYqx6ZXHxoXAzNr+hTEqAbx6RaLy28Z3PwdFoO3lcbYUKbsB7DDBO/JGrLLTEpKYc6aUkc7xdew== X-Received: by 2002:aa7:c610:: with SMTP id h16mr24451997edq.5.1555192257961; Sat, 13 Apr 2019 14:50:57 -0700 (PDT) Received: from lowell.delroth.net ([2a02:168:6426::bb2]) by smtp.gmail.com with ESMTPSA id h57sm192425eda.90.2019.04.13.14.50.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 13 Apr 2019 14:50:57 -0700 (PDT) From: Pierre Bourdon To: u-boot@lists.denx.de Date: Sat, 13 Apr 2019 23:50:49 +0200 Message-Id: <20190413215049.15305-1-delroth@gmail.com> X-Mailer: git-send-email 2.19.2 MIME-Version: 1.0 Subject: [U-Boot] [PATCH] fs: btrfs: fix false negatives in ROOT_ITEM search X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.18 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" ROOT_ITEMs in btrfs are referenced without knowing their actual "offset" value. To perform these searches using only two items from the key, the btrfs driver uses a special "btrfs_search_tree_key_type" function. The algorithm used by that function to transform a 3-tuple search into a 2-tuple search was subtly broken, leading to items not being found if they were the first in their tree node. This commit fixes btrfs_search_tree_key_type to properly behave in these situations. Signed-off-by: Pierre Bourdon Cc: Marek Behun --- fs/btrfs/ctree.h | 44 ++++++++++++++++++++++++++++++++++++++------ 1 file changed, 38 insertions(+), 6 deletions(-) diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 65c152a52f..ca44a2404d 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -292,20 +292,52 @@ btrfs_search_tree_key_type(const struct btrfs_root *root, u64 objectid, { struct btrfs_key key, *res; + /* + * In some cases (e.g. tree roots), we need to look for a given + * objectid and type without knowing the offset value (3rd element of a + * btrfs tree node key). We can rely on the fact that btrfs_search_tree + * returns the first element with key >= search_key, and then perform + * our own comparison between the returned element and the search key. + * + * It is tempting to use a search key with offset 0 to perform this + * "fuzzy search". This would return the first item with the (objectid, + * type) we're looking for. However, using offset 0 has the wrong + * behavior when the wanted item is the first in a leaf: since our + * search key will be lower than the wanted item, the recursive search + * will explore the wrong branch of the tree. + * + * Instead, use the largest possible offset (-1). The result of this + * search will either be: + * 1. An element with the (objectid, type) we're looking for, if it + * has offset -1 or if it is the last element in its leaf. + * 2. The first element *after* an element with the (objectid, type) + */ key.objectid = objectid; key.type = type; - key.offset = 0; + key.offset = -1; if (btrfs_search_tree(root, &key, path)) return NULL; - res = btrfs_path_leaf_key(path); - if (btrfs_comp_keys_type(&key, res)) { - btrfs_free_path(path); - return NULL; + /* + * Compare with the previous element first -- this is the likely case + * since the result of the search is only what we want if it had offset + * == -1 or if it was last in its leaf. + */ + if (path->slots[0] > 0) { + path->slots[0]--; + res = btrfs_path_leaf_key(path); + if (!btrfs_comp_keys_type(&key, res)) + return res; + path->slots[0]++; } - return res; + res = btrfs_path_leaf_key(path); + if (!btrfs_comp_keys_type(&key, res)) + return res; + + btrfs_free_path(path); + return NULL; } static inline u32 btrfs_path_item_size(struct btrfs_path *p)