Received: by 2002:a05:6a10:2726:0:0:0:0 with SMTP id ib38csp5629407pxb; Mon, 28 Mar 2022 15:11:54 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwacBRz8BCXKzUb5OrZSEsd4Ut8hdBFvT11n7M8MjQb+BmUKnBtAH84es9aCPGHviisGYbC X-Received: by 2002:a05:6870:4792:b0:da:b3f:3220 with SMTP id c18-20020a056870479200b000da0b3f3220mr659643oaq.208.1648505514040; Mon, 28 Mar 2022 15:11:54 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1648505514; cv=none; d=google.com; s=arc-20160816; b=L0Cm1oOU09z797cdh0XOfASvyzIN6Cfb9LeqDpmBkYvWfi7olnc+RL1AkyAE7ZdkhN L5lWuJKKCYIc+LZmudEp5ZcyG2jahH75czjlN7DB40ky5/GAyixLE0twhBOlZdt+xmg0 ZckSMxl6IwLzIz3uFCLkbByS3V0eskumrxjMJrJflc+Yzwb7DDe1sG06ijgfZ7d2uLcB EtHeNJf4PTiSLLsFGZEYqQl0L2tJHIiYJMH2jtx1aSkCc2SFUfv5SXxgfyIPRlzbBMwb E3p20RSrJQHXKGJSy9ABTByP0riiJzFw5m9Tkx6+0E8le71T8GmGDqckTzDuiHAmJiTT WUpA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:mime-version:content-transfer-encoding :content-id:content-language:accept-language:message-id:date :thread-index:thread-topic:subject:to:from:dkim-signature; bh=rCbjTFMpcRj13qtucn7hA6OOvks+8DuwU+qIHhyS7vY=; b=sSSBQtdqbJ4gbUAO1Np7TiGks3Lqt71lWoJIpwucJMyvj+DMUNfGJDYN4PpQJeWfkw wAqor8ANhgK8E81xU6br0umTYbRy1+/VG09UEr5eZvi4TJzDDoMkBN5U7Phe5M0S2S+9 IJEBNHJm2niiLgqGA1N6rPMQvaMJDZBy/YRekCZil9VZnRCjZ5ltBbatqdRQgp4/9PpR hNci8k7CFdpWI2tR77k9dwR/bEgijgMU5/alZlAu8IXCX7RH+9X81UA3HwzShhREFSLK nqbi7XfQLPqLvjhmT/DECj4AmumDRn/jMnImAWXrFOGEDBTN0RXMFIIp64S5VNjfRyTk SVig== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@amazon.com header.s=amazon201209 header.b=SdnxVgrA; spf=pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) smtp.mailfrom=linux-ext4-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=amazon.com Return-Path: Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net. [2620:137:e000::1:18]) by mx.google.com with ESMTPS id a43-20020a056870d62b00b000dd9d6b2aa9si11144961oaq.229.2022.03.28.15.11.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Mar 2022 15:11:54 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18; Authentication-Results: mx.google.com; dkim=pass header.i=@amazon.com header.s=amazon201209 header.b=SdnxVgrA; spf=pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) smtp.mailfrom=linux-ext4-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=amazon.com Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id CAD4845780; Mon, 28 Mar 2022 14:31:55 -0700 (PDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S245450AbiC1TIF (ORCPT + 99 others); Mon, 28 Mar 2022 15:08:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43432 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245497AbiC1TIB (ORCPT ); Mon, 28 Mar 2022 15:08:01 -0400 Received: from smtp-fw-80006.amazon.com (smtp-fw-80006.amazon.com [99.78.197.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1B18D6661D for ; Mon, 28 Mar 2022 12:06:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1648494380; x=1680030380; h=from:to:subject:date:message-id:content-id: content-transfer-encoding:mime-version; bh=rCbjTFMpcRj13qtucn7hA6OOvks+8DuwU+qIHhyS7vY=; b=SdnxVgrA/EHhxURu27Fux5dnjzC9M1v81L6/7cNo3LMuuajDvLlJY1fB w27Va/fBkeoEAWz9M1bSfF/Ubo5libDXFQ62PJglcKRxb4Ca2NouAQ/wb NuKWfZ40smE9uJUYKM+ZXcja+FpA1b5XKQ+izICUWDNcSojP5crlrQka/ 4=; X-IronPort-AV: E=Sophos;i="5.90,218,1643673600"; d="scan'208";a="74646140" Received: from pdx4-co-svc-p1-lb2-vlan3.amazon.com (HELO email-inbound-relay-iad-1box-d-74e80b3c.us-east-1.amazon.com) ([10.25.36.214]) by smtp-border-fw-80006.pdx80.corp.amazon.com with ESMTP; 28 Mar 2022 19:06:19 +0000 Received: from EX13MTAUWB001.ant.amazon.com (iad12-ws-svc-p26-lb9-vlan3.iad.amazon.com [10.40.163.38]) by email-inbound-relay-iad-1box-d-74e80b3c.us-east-1.amazon.com (Postfix) with ESMTPS id 78EF6982C8 for ; Mon, 28 Mar 2022 19:06:18 +0000 (UTC) Received: from EX13D23UWA003.ant.amazon.com (10.43.160.194) by EX13MTAUWB001.ant.amazon.com (10.43.161.249) with Microsoft SMTP Server (TLS) id 15.0.1497.32; Mon, 28 Mar 2022 19:06:17 +0000 Received: from EX13D23UWA003.ant.amazon.com (10.43.160.194) by EX13D23UWA003.ant.amazon.com (10.43.160.194) with Microsoft SMTP Server (TLS) id 15.0.1497.32; Mon, 28 Mar 2022 19:06:17 +0000 Received: from EX13D23UWA003.ant.amazon.com ([10.43.160.194]) by EX13D23UWA003.ant.amazon.com ([10.43.160.194]) with mapi id 15.00.1497.033; Mon, 28 Mar 2022 19:06:17 +0000 From: "Kiselev, Oleg" To: linux-ext4 Subject: Resize of `-O bigalloc` filesystem uses a computation with O(n**2) complexity Thread-Topic: Resize of `-O bigalloc` filesystem uses a computation with O(n**2) complexity Thread-Index: AQHYQtbmSQUL74mXVEyq2+7VER15tw== Date: Mon, 28 Mar 2022 19:06:17 +0000 Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-exchange-messagesentrepresentingtype: 1 x-ms-exchange-transport-fromentityheader: Hosted x-originating-ip: [10.43.160.203] Content-Type: text/plain; charset="utf-8" Content-ID: Content-Transfer-Encoding: base64 MIME-Version: 1.0 X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RDNS_NONE,SPF_HELO_NONE,T_SCC_BODY_TEXT_LINE autolearn=no 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-ext4@vger.kernel.org V2UgYXJlIHZhbGlkYXRpbmcgdGhlIHVzZSBvZiBgLU8gYmlnYWxsb2NgIGZ1bmN0aW9uYWxpdHkg YW5kIGhhdmUgcnVuIGludG8gcHJvYmxlbXMgd2l0aCBpdC4NCg0KVGhpcyBpc3N1ZSByZXF1aXJl cyBhIGxhcmdlIGRldmljZSB0byByZXByb2R1Y2UuICBPbiB2ZXJ5IGxhcmdlIGZpbGVzeXN0ZW1z IGNyZWF0ZWQgd2l0aCBgLU8gYmlnYWxsb2MgLUMgMTZrYCB3ZSBzZWUgcmVzaXplIHRha2UgcHJv Z3Jlc3NpdmVseSBtb3JlIHRpbWUgYXMgdGhlIGZzIHNpemUgZ3Jvd3MuICBIZXJl4oCZcyB0aGUg dGltZSBpdCB0YWtlcyB0byByZXNpemUgYSBmaWxlc3lzdGVtIGNyZWF0ZWQgd2l0aCB0aGUgZGVm YXVsdCA0SyBibG9ja3M6DQo9PT09PT09PT09PQ0KU2l6ZSBvZiBsb2dpY2FsIHZvbHVtZSBkYmRh dGEwMS9sdmRiZGF0YTAxIGNoYW5nZWQgZnJvbSAzNy43OSBUaUIgKDk5MDY0NzYgZXh0ZW50cykg dG8gMzguODAgVGlCICgxMDE3MTQ5MyBleHRlbnRzKQ0KIA0KcmVhbCAgICAgMG0xMy42MDRzDQp1 c2VyICAgICAwbTAuMDEzcw0Kc3lzICAgICAgMG05LjU0OXMNCj09PT09PT09PT09PSANCnZzLiB0 aGUgdGltZSBpdCB0YWtlcyB3aXRoIDE2SyBjbHVzdGVyczoNCj09PT09PT09PT09PQ0KU2l6ZSBv ZiBsb2dpY2FsIHZvbHVtZSBkYmRhdGEwMS9sdmRiZGF0YTAxIGNoYW5nZWQgZnJvbSAzNi45OCBU aUIgKDk2OTQyNDUgZXh0ZW50cykgdG8gPDM4LjcxIFRpQiAoMTAxNDc0NzcgZXh0ZW50cykuDQog DQpyZWFsICAgIDE3OG0yMi41OTBzDQp1c2VyICAgIDBtMC4wMDVzDQpzeXMgICAgIDE3OG00LjAy N3MNCj09PT09PT09PT09PSANCldlIGhhdmUgdHJhY2tlZCB0aGlzIGRvd24gdG8gdGhlIGNvZGUg aW4gZnMvZXh0NC9zdXBlci5jIHdoaWNoIGRvZXMgTyhudW1iZXJfb2ZfYmxvY2tfZ3JvdXBzICoq IDIpIGl0ZXJhdGlvbnMgdGhyb3VnaCB0aGUgYWxsb2NhdGlvbiBncm91cHMgd2hpbGUgY29tcHV0 aW5nIG1ldGFkYXRhIG92ZXJoZWFkLiAgVGhlIGV4dHJhY3Rpb24gb2YgdGhlIGNvZGUgdGhhdCBz aG93cyB0aGlzDQpgYGANCjM5MjYgaW50IGV4dDRfY2FsY3VsYXRlX292ZXJoZWFkKHN0cnVjdCBz dXBlcl9ibG9jayAqc2IpDQozOTI3IHsNCiAgICAgICAgIFsuLi5dDQozOTUzICAgICBmb3IgKGkg PSAwOyBpIDwgbmdyb3VwczsgaSsrKSB7DQogICAgICAgICAgICAgWy4uLl0NCjM5NTYgICAgICAg ICBibGtzID0gY291bnRfb3ZlcmhlYWQoc2IsIGksIGJ1Zik7ICAgICAgPDw8PDwNCiAgICAgICAg ICAgICBbLi4uXQ0KMzk2MSAgICAgfQ0KICAgICAgICAgWy4uLl0NCjM5ODQgfSANClsuLi5dDQoz ODY1IHN0YXRpYyBpbnQgY291bnRfb3ZlcmhlYWQoc3RydWN0IHN1cGVyX2Jsb2NrICpzYiwgZXh0 NF9ncm91cF90IGdycCwNCjM4NTYgICAgICAgICAgY2hhciAqYnVmKQ0KMzg1NyB7DQogICAgICAg ICBbLi4uXQ0KMzg3NCAgICAgaWYgKCFleHQ0X2hhc19mZWF0dXJlX2JpZ2FsbG9jKHNiKSkgICAg ICAgICA8PDw8PCBub24tYmlnYWxsb2MgZXhpdHMgaGVyZSENCjM4NzUgICAgICAgICByZXR1cm4g KGV4dDRfYmdfaGFzX3N1cGVyKHNiLCBncnApICsgZXh0NF9iZ19udW1fZ2RiKHNiLCBncnApICsN CjM4NzYgICAgICAgICAgICAgc2JpLT5zX2l0Yl9wZXJfZ3JvdXAgKyAyKTsNCiAgICAgICAgIFsu Li5dDQozODgxICAgICBmb3IgKGkgPSAwOyBpIDwgbmdyb3VwczsgaSsrKSB7ICAgICAgICAgICAg IDw8PDw8DQogICAgICAgICAgICAgWy4uLl0NCjM5MTYgICAgIH0NCiAgICAgICAgWy4uLl0NCjM5 MjEgfQ0KYGBgIA0KVGhlIGNvbW1lbnQgb24gYGNvdW50X292ZXJoZWFkKClgIGNsZWFybHkgc3Rh dGVzIHRoYXQgdGhlIGNvbW1pdHRlcnMgd2hvIHdyb3RlIHRoaXMgY29kZSBrbmV3IHRoYXQgdGhp cyB3aWxsIGJlIGFuIG4qKjIgY29tcGxleGl0eSBjb21wdXRhdGlvbi4NCiANCldlIGFyZSBsb29r aW5nIGZvciB3YXlzIHRvIHJlZHVjZSB0aGUgY29tcHV0YXRpb24gdGltZSwgcGVyaGFwcyBieSBz a2lwcGluZyB0aGUgYWxyZWFkeSBleGlzdGluZyBncm91cHMsIHdob3NlIG92ZXJoZWFkIGlzIGFs cmVhZHkgY29tcHV0ZWQsIGFuZCB3aGljaCBhcmUgdW5saWtlbHkgdG8gaGF2ZSBhbnkgb2YgdGhl aXIgbWV0YWRhdGEgYWxsb2NhdGlvbnMgaW4gdGhlIGdyb3VwcyB3ZSBhcmUgYWRkaW5nLg0KDQo=