From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 99EB0C43219 for ; Sat, 4 May 2019 00:57:07 +0000 (UTC) Received: from shelob.surriel.com (shelob.surriel.com [96.67.55.147]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 5928B206E0 for ; Sat, 4 May 2019 00:57:07 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 5928B206E0 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=vt.edu Authentication-Results: mail.kernel.org; spf=fail smtp.mailfrom=kernelnewbies-bounces@kernelnewbies.org Received: from localhost ([::1] helo=shelob.surriel.com) by shelob.surriel.com with esmtp (Exim 4.91) (envelope-from ) id 1hMiz4-0002nc-EI; Fri, 03 May 2019 20:56:58 -0400 Received: from omr1.cc.ipv6.vt.edu ([2607:b400:92:8300:0:c6:2117:b0e] helo=omr1.cc.vt.edu) by shelob.surriel.com with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.91) (envelope-from ) id 1hMiz2-0002nV-Od for kernelnewbies@kernelnewbies.org; Fri, 03 May 2019 20:56:56 -0400 Received: from mr5.cc.vt.edu (mr5.cc.ipv6.vt.edu [IPv6:2607:b400:92:8400:0:72:232:758b]) by omr1.cc.vt.edu (8.14.4/8.14.4) with ESMTP id x440usvd022076 for ; Fri, 3 May 2019 20:56:55 -0400 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by mr5.cc.vt.edu (8.14.7/8.14.7) with ESMTP id x440unIK009156 for ; Fri, 3 May 2019 20:56:54 -0400 Received: by mail-qt1-f199.google.com with SMTP id k20so7909573qtk.13 for ; Fri, 03 May 2019 17:56:54 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:in-reply-to:references :mime-version:content-transfer-encoding:date:message-id; bh=gkMzHyADikDYcgzv404ujyzc+siKXxwr/gYA7yHKFrU=; b=MM+FT2QdmZWdXnZqXHZBoY+dhSvcjElHkO2g7gs7jFv+54swAkaj4YgtiUwoyjU4jr KmBJLcT9jcAo2alsWhGdnRNGKYPsdO6nwYVrnMvPUBER/hNqAq12HlHD3SR7SvlsGYUr luv0HKloRGwY9n0L8o3PPoV3jE8O0CSYUN30oeXdLay5szmYWXjkvMMIZAufppThkQ3s 0RRJwu7HqxW/GPphY6+DuAD7xXlTZlWAM6mtfjL67wTRDdw4I987a3/WYJAiiEG5R5bQ pbuY0STHbfC+/thyOFY53WXP0TTnzeBeSdtiOug4q0RSO/WvEqN+UslPF/Kd6++IFFrN bY+g== X-Gm-Message-State: APjAAAXSJStFuQodYebsa/p36IaqudsnIM6xb9MPfMzx6nhzrMX+Pigi IQIs5bii7oFkkmJGr3d+1E3Gw1d8UCwjIpf/ExrcF64ArOZ6mJYy0ZepERYIisc8kAZDM+zuWon gEAMmTQKMIj7gHJzHIlH5a0xAhSpt9Zmn2822Ik0= X-Received: by 2002:a37:4bc3:: with SMTP id y186mr4751387qka.169.1556931409426; Fri, 03 May 2019 17:56:49 -0700 (PDT) X-Google-Smtp-Source: APXvYqwsUKfgQBmvs6eZNTy44r0LJ5eEjrMOR4C/9TC/S5ituLhtRgS92xLIqvOla88WQG3OTlVRoA== X-Received: by 2002:a37:4bc3:: with SMTP id y186mr4751373qka.169.1556931409138; Fri, 03 May 2019 17:56:49 -0700 (PDT) Received: from turing-police ([2601:5c0:c001:4341:5952:f06b:5958:9b7c]) by smtp.gmail.com with ESMTPSA id f127sm3241353qkb.53.2019.05.03.17.56.47 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 03 May 2019 17:56:47 -0700 (PDT) From: "Valdis Kl=?utf-8?Q?=c4=93?=tnieks" X-Google-Original-From: "Valdis Kl=?utf-8?Q?=c4=93?=tnieks" X-Mailer: exmh version 2.9.0 11/07/2018 with nmh-1.7+dev To: Probir Roy Subject: Re: radix_tree_next_chunk: redundant search for next slot in hole In-Reply-To: References: <6489.1556923119@turing-police> Mime-Version: 1.0 Date: Fri, 03 May 2019 20:56:46 -0400 Message-ID: <22886.1556931406@turing-police> Cc: kernelnewbies@kernelnewbies.org X-BeenThere: kernelnewbies@kernelnewbies.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Learn about the Linux kernel List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: multipart/mixed; boundary="===============1420140959496194958==" Errors-To: kernelnewbies-bounces@kernelnewbies.org --===============1420140959496194958== Content-Type: multipart/signed; boundary="==_Exmh_1556931406_11736P"; micalg=pgp-sha1; protocol="application/pgp-signature" Content-Transfer-Encoding: 7bit --==_Exmh_1556931406_11736P Content-Type: text/plain; charset=us-ascii On Fri, 03 May 2019 19:00:26 -0500, Probir Roy said: > > > While searching for next slot in a hole, it walks through the same > > > slots over n over. > > > > How did you determine this? > > I am working on a tool that identifies repeated load of an address. > Often these repeated loads are redundant and can be avoided with data > structure modification. The tool points me to this line. Is this doing static analysis, or actually doing run-time tracing? > > Looks to me like the ++offset will walk through each potential slot once, > > and break out if it finds one. > > > This function is being called by the radix_tree_for_each_slot > iterator, defined as follows: > > #define radix_tree_for_each_slot(slot, root, iter, start) \ > for (slot = radix_tree_iter_init(iter, start) ; \ > slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \ > // <<<<-------^^^ > slot = radix_tree_next_slot(slot, iter, 0)) > > Here is the calling context I get: > |_ depth: 1 :0, method: ext4_block_write_begin+0x335/0x4f0(), > |_ depth: 2 :0, method: alloc_buffer_head+0x21/0x60(), > |_ depth: 3 :0, method: ext4_da_get_block_prep+0x1a6/0x490(), > |_ depth: 4 :0, method: clean_bdev_aliases+0x9a/0x210(), > |_ depth: 5 :0, method: pagevec_lookup_range+0x24/0x30(), > |_ depth: 6 :0, method: find_get_pages_range+0x151/0x2d0(), > |_ depth: 7 :0, method: radix_tree_next_chunk+0x10f/0x360() > > Does it explain the case? Actually, that calling context doesn't tell us much of anything till depth 7. Yes, next_chunk() and next_slot() can get called repeatedly, especially if it's a large radix tree. The important question is: Is it being called with the *same value* of 'slot' repeatedly? Looking at the code, it's pretty obvious that 'slot' will be updated at least once through every pass through the for_each_slot(), unless the radix tree is corrupted. If you're trying to do static analysis, your code may be confused by either the 'slot || next_chunk()' iterator, or the fact that 'slot' is assigned both in the for loops iterator and in the body of the loop, and thus failing to detect that slot is updated. --==_Exmh_1556931406_11736P Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Comment: Exmh version 2.9.0 11/07/2018 iQIVAwUBXMzjTQdmEQWDXROgAQK4/RAAhqt41cAW6mWfMn0IkHqhIA48O7b5SLvr ThY1JGMM8fWyq0acwfpYkyf8VDs+PnMgSmwqo48p3s/5H3xiOoP5oeSMfvGhKnAS Vk3hOgo7HS9CS3HOc+y3GZ5uGikl9R1dIF0rZ+8qJFnAwko3JLywkyfZAaZaY1F3 MY9odWTFjSd9AVuHvDXi64a/3OFxLoyj+E7UiGmNmX9rnlPZuOjVDe5C58WNsiDH e9jugAo//1RVCtds7svHJ7vxS69SpnCFWN8KDyqpIZhzVhZcAoQ8YXVAZqX0KMbv FjbLWZF9GyuYI9ZDCgry9rSrnfR3f3MZCyVZLCMb/i69Fy09X/juGq+AT9bsN/Xx VAlGiWGmxO3OgH2o7NdL68qHu3QSGN2i+IAiMXyXPNuUQt2FQWm9zST4+ttaL0V6 clqrSaBJglneVYzgEz4SHRiI4VKmZ//+li+dLXkiPpj8uB0hMaZSs+67GZUwIZ8s 90u7/bIlF0TfwrLXoO5w1cmwYmjiKjCwy/3NWFh3d/Do/bQvUczBIx9lD27WLD62 /tEjomOp4plZViNcmB1egdjcrgXNcJzDnPW3vHyoxMG/ik6OkLOit+RubSbYjGtR 4fynnO+uPg2RzFqWEGJkocqXfDl1PWtUdjZp7xDFWuyXRekZ55W3R+nropufRoU/ W3wQAFuCe7U= =HFLV -----END PGP SIGNATURE----- --==_Exmh_1556931406_11736P-- --===============1420140959496194958== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies --===============1420140959496194958==--