Received: by 2002:a05:6359:c8b:b0:c7:702f:21d4 with SMTP id go11csp1262304rwb; Thu, 22 Sep 2022 12:23:40 -0700 (PDT) X-Google-Smtp-Source: AMsMyM42kPS/sNVI/G1QWIIFtXkTMaKpIPmDZZwq7Mf43MA3CpiQPZMOJM1xcEuJZgHldQVOaajk X-Received: by 2002:a17:906:fe0b:b0:730:3646:d177 with SMTP id wy11-20020a170906fe0b00b007303646d177mr3885717ejb.688.1663874620479; Thu, 22 Sep 2022 12:23:40 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1663874620; cv=none; d=google.com; s=arc-20160816; b=sLevV85I0v/WxZqXrvq4bY4/q5nwTRueAnGgaw7z3yAbbRD79cmGTzHdrhi8TihR9I p2i3ZgrYedIxu9o6IjMHpmhP0kY5mJdG/bqW5cFjJpKpPJ59ZXpxEqQyvrdWlMKKm1I2 6mk3bxo2rJOoZD9rxipLHFv4KWSJ9B0Xu+joZaK863BqS6slMXXkfdJqWyeA+OOkZtyJ w+BI63rxz4W50c84Cky27+lg3iN78WEuUsH87eZAPT78GxXJUfW1yTJbDAdjjVrRDiCW CDejC25Fs+2rVT/iVJqyqyJUUR4/u5hxl9ZAztPLkTwbenWdK5s+ki4hKkEHQjDytOjZ gg2A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:in-reply-to:from :references:cc:to:subject:user-agent:mime-version:date:message-id :dkim-signature; bh=Il1n+p4EYijj6sMX+qTskkavLcV+LCxu/c4N5YGuAz8=; b=BrP9mNtcgt9Sa6aSp67om8WkXlxIq2KiIwTkLCRCu3PQ2qgIgmPWPIKgCzh8kwlh5K nG/+6vQK2qpUWUkpm+2rY66rUXkO/Q9BItYjRqXjmv1M192mF3QaC8f8Ds7P6YOR4WTN ZfaKGyBQkzdhcwHC6PhjaGxMrm49MKaDupoOgVqs3QO+fmP1xwMvfXkCmWtmoMDCgr8P 0ZKsE15jJ//aVOTySrkX8JiSHNbdrJ2fBj21ZJqwxtOgGumHB64M25z2lWs6kuPdz8Ou foq/swXw4FnTtSLp9v7h9KrFpPLOT6spx4vQHIrxku3MN8iUXlRhTFH/gfcilg90H5+9 HgJw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b="2K4/5gRH"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Return-Path: Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id cs17-20020a170906dc9100b0077e9417b5a7si5623826ejc.938.2022.09.22.12.23.14; Thu, 22 Sep 2022 12:23:40 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b="2K4/5gRH"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231645AbiIVSw2 (ORCPT + 99 others); Thu, 22 Sep 2022 14:52:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59418 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231508AbiIVSw0 (ORCPT ); Thu, 22 Sep 2022 14:52:26 -0400 Received: from mail-pg1-x529.google.com (mail-pg1-x529.google.com [IPv6:2607:f8b0:4864:20::529]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AC67DE62D6 for ; Thu, 22 Sep 2022 11:52:25 -0700 (PDT) Received: by mail-pg1-x529.google.com with SMTP id v4so10004051pgi.10 for ; Thu, 22 Sep 2022 11:52:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date; bh=Il1n+p4EYijj6sMX+qTskkavLcV+LCxu/c4N5YGuAz8=; b=2K4/5gRHOw+nUVM6Q0jlqIaxrwXepL/8XbhbHtaGBxUIxiEIS3jSiRB6a7G3n4aX6s SwqblsFwJZxCUCnK6vPdKIBm071K9yD7o5Ib4nKbD99l37gftYjkjNaGV+IxZA6X/uKM cdlmS3FOvAtL0IkjVAJv5Bek2QUSSS4BKxgie8P7lpntt8PNNj/fnzzWqmdQm/gQCH7X IQg+s4k6vKpnvJQo8IqtyHl0jsLDhBMCh8BI0zDCSdBbIAt0ssXBR9ezhs+WckhQkvED QVavzuyE+YzR1ebk7P7YMDYh//duMfSjordbUO7Clid1RNVbpBbarVwzqT4Nxy8jKmaQ EI9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date; bh=Il1n+p4EYijj6sMX+qTskkavLcV+LCxu/c4N5YGuAz8=; b=doV4qyFobIBRPpXPDz2kiifYHQ14tFxXJsis0u+hPMMZUczMh37B/pMwB4lLqpTcuU F5oSLaOzjSG8e1VfmmZ1zJRCBRccrUrMMNkm5De2RUJAVtus+O7qmRRiSoCJ0X+Blanp /XiFzo6K5po54WUfbwMD7EQIMXcRDr19LVN4u876V0EyPRhVx7Tsvxx9ab71tsNhV1ke M7Qv/t6xeZEbxAQjrP1bvhxSShVlWfx7jqb7am2fqeIPn0ne1VKzed6tyEnEc4kZYPPI dKUgbhpt10WpoSvCz4O5v7vkuD4inmJjHvrGvvKGAVvwc6kDVz8FAH7RDBMyajV/Xsbi okhg== X-Gm-Message-State: ACrzQf3C1923Poi+nOe15uq/LXhvVMunTovAo/dpmo7oO7Rytl2j3Vl4 /SKoT+e9j7/GxnaYYy2h7hChQA== X-Received: by 2002:a63:5a5e:0:b0:434:b739:206f with SMTP id k30-20020a635a5e000000b00434b739206fmr4188149pgm.82.1663872745268; Thu, 22 Sep 2022 11:52:25 -0700 (PDT) Received: from [10.255.231.119] ([139.177.225.235]) by smtp.gmail.com with ESMTPSA id b7-20020a170902650700b001754fa42065sm4441763plk.143.2022.09.22.11.52.22 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 22 Sep 2022 11:52:24 -0700 (PDT) Message-ID: Date: Fri, 23 Sep 2022 02:52:19 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.3.0 Subject: Re: [RESEND PATCH v3] iommu/iova: Optimize alloc_iova with rbtree_augmented To: joro@8bytes.org, will@kernel.org Cc: wangjie125@huawei.com, iommu@lists.linux.dev, linux-kernel@vger.kernel.org, robin.murphy@arm.com, haifeng.zhao@linux.intel.com, john.garry@huawei.com References: <20220922183114.15135-1-zhangpeng.00@bytedance.com> From: Peng Zhang In-Reply-To: <20220922183114.15135-1-zhangpeng.00@bytedance.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-3.8 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,NICE_REPLY_A,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello everyone, Compared with v2, v3 mainly updated the commit message, and set the upper limit when scanning the linked list. In the normal case, the performance of this algorithm is almost the same as before. In extreme cases, this algorithm is much better than before. And this algorithm does not bring additional memory overhead. Comments welcome. Thanks. Peng