From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pg1-f174.google.com (mail-pg1-f174.google.com [209.85.215.174]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1BEFC27715 for ; Sun, 16 Jun 2024 13:37:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.174 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718545035; cv=none; b=tKAfxRPdJzQNwgLVJaq1FsiWfYx7Rc3FTuMid8TeaVngtPSxCIxfbPcuLmJdgU/54MbSoR/kCGDBz/CNK5KM64ImXBdkIAn5+5e7BFH2XN87W8iOzG2dE7gsWJwjlrv1sMTY92vNsmjIpJe0Zl4Dauayp6kOqNbCdHxkSjBNRws= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718545035; c=relaxed/simple; bh=5+SdQnZnG1y9HxR07OjoUs4P3c1JXSE8RHTxsbHXs1k=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=ucG1+OuCeHDHJ7rcwlJWO4gsOa/S1yOA/IQQI/8ahhX6rNpLf5/M5aPapObGta2Mo2dEZCh7jbvqXkZGnnxOofFcw4wFJWLTyy/W1RD+XwMs/+No3dfo0m076ZLMlDpYPO5634QUC1ob2TRV4UFAHrAj2rQK1d6ty0AzsRM6j+0= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=kEDsztoD; arc=none smtp.client-ip=209.85.215.174 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kEDsztoD" Received: by mail-pg1-f174.google.com with SMTP id 41be03b00d2f7-6e5fd488d9fso2729581a12.3 for ; Sun, 16 Jun 2024 06:37:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1718545033; x=1719149833; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=Vo6LewisGnKDZPN/HUntq5aJW2gPhK/j1eCzo1GB2/k=; b=kEDsztoDxelCH2ZD+LL48kA/llW2uw1NUFt2PQ/uiMZNpqfL2xCuQqPcACg6X8dfVf /sMN6/NPT5hHlMply9ouwY8xlAbDWQQXhne4dBIjnKY7oLqMT8ty5uYHZfKGkaNruP8X ps8MD6+jxjk3XeqhP4zT+eylxS/HEfRrMQHO7Baek7lEGG76maO6RGD5WaWM6duAruL3 q+ijed1t0MONCY1PaJsU3d99FzKm6J1kPWiaOp0l9MaK6AqxL7MB1B9kMFiL9uz1ThHH H5H5cKtipdp09EvncGamo4ES3YvCBudKFm7lRVAAo2+mktX03weGG0x5K41mAvpWRaql jqUA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1718545033; x=1719149833; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=Vo6LewisGnKDZPN/HUntq5aJW2gPhK/j1eCzo1GB2/k=; b=ol0DkS0Ialjnm6VaNmhAcN+9riE6++xqFjJ6WYLFdRUfP9mQSqVXlm/FD9/DplvUIY /2RqUGXXW0uOglPdkT0lApk2NgTHhjJyetScbAkUX46hmz/uSVF14JGwdYuB8RWhhf+A d3ypLwNz188MtAMSDV0uSLutmI7vhRUMGKC45hMmL13SHlFVjYj2dyue5WM4NDjGUJlR h5xZb6diFR1QR4jlD9PtSaz9NZEHPn6NzAuUlGRI5pIbqtUZFmC7qpv1pf9y0gNhr+9I bGaNwi2anZTCAfZpvZHICuraPDRn7IA6Njy2FKz+7AAgmTSZ856hn9T8sRz8Tni4N2tD GuEw== X-Forwarded-Encrypted: i=1; AJvYcCVysPeRd543lFJyTnr0HYMnfqrTfhayV/7bSHQBxqfWKam7JgAIjFtK7Br4G+kHPJNCSGbKr1exPTfiN9JmZnlwKckBqpY= X-Gm-Message-State: AOJu0YwOVbXEPpqyGGRnc49INrJ7H/EGgsUju3GC3L53KHbrLjzvTkoM ztoYR0R2RP5O+x/wjmCNVIQ15Izs7FXwsv9Sno/iy1ZoyZf9qmcu X-Google-Smtp-Source: AGHT+IHyKCYIIMXS1PzF7WjVg/51xGCgdvMjVfp92z+vEuJxUitlc9CwdsLpXLBEUtFpq4zoPA2AMQ== X-Received: by 2002:a17:902:e847:b0:1f8:49e0:4d19 with SMTP id d9443c01a7336-1f8629fed6dmr108963735ad.57.1718545033157; Sun, 16 Jun 2024 06:37:13 -0700 (PDT) Received: from dev0.. ([49.43.162.104]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-1f855ee6f01sm63756575ad.153.2024.06.16.06.37.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 16 Jun 2024 06:37:12 -0700 (PDT) From: Abhinav Jain To: almaz.alexandrovich@paragon-software.com, ntfs3@lists.linux.dev, linux-kernel@vger.kernel.org Cc: skhan@linuxfoundation.org, javier.carrasco.cruz@gmail.com, jain.abhinav177@gmail.com Subject: [PATCH] fs/ntfs3: Remove recursion in indx_insert_into_buffer Date: Sun, 16 Jun 2024 13:37:04 +0000 Message-Id: <20240616133704.45284-1-jain.abhinav177@gmail.com> X-Mailer: git-send-email 2.34.1 Precedence: bulk X-Mailing-List: ntfs3@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Remove recursion by using iteration. Decrement the level so that parent buffer can be handled in the next iteration. Update the header of the index buffer to point to the correct buffer. Set new_de to up_e so that the promoted entry is inserted into the parent buffer. Signed-off-by: Abhinav Jain --- fs/ntfs3/index.c | 204 ++++++++++++++++++++++++----------------------- 1 file changed, 106 insertions(+), 98 deletions(-) diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c index d0f15bbf78f6..09d5dcbfcc38 100644 --- a/fs/ntfs3/index.c +++ b/fs/ntfs3/index.c @@ -1802,122 +1802,130 @@ indx_insert_into_buffer(struct ntfs_index *indx, struct ntfs_inode *ni, u16 sp_size; void *hdr1_saved = NULL; - /* Try the most easy case. */ - e = fnd->level - 1 == level ? fnd->de[level] : NULL; - e = hdr_insert_de(indx, hdr1, new_de, e, ctx); - fnd->de[level] = e; - if (e) { - /* Just write updated index into disk. */ - indx_write(indx, ni, n1, 0); - return 0; - } + while (true) { + /* Try the most easy case. */ + e = fnd->level - 1 == level ? fnd->de[level] : NULL; + e = hdr_insert_de(indx, hdr1, new_de, e, ctx); + fnd->de[level] = e; + if (e) { + /* Just write updated index into disk. */ + indx_write(indx, ni, n1, 0); + return 0; + } - /* - * No space to insert into buffer. Split it. - * To split we: - * - Save split point ('cause index buffers will be changed) - * - Allocate NewBuffer and copy all entries <= sp into new buffer - * - Remove all entries (sp including) from TargetBuffer - * - Insert NewEntry into left or right buffer (depending on sp <=> - * NewEntry) - * - Insert sp into parent buffer (or root) - * - Make sp a parent for new buffer - */ - sp = hdr_find_split(hdr1); - if (!sp) - return -EINVAL; + /* + * No space to insert into buffer. Split it. + * To split we: + * - Save split point because index buffers will be changed + * - Allocate NewBuffer and copy all entries <= sp into new + * buffer + * - Remove all entries (sp including) from TargetBuffer + * - Insert NewEntry into left or right buffer + * (depending on sp <=> NewEntry) + * - Insert sp into parent buffer (or root) + * - Make sp a parent for new buffer + */ + sp = hdr_find_split(hdr1); + if (!sp) + return -EINVAL; - sp_size = le16_to_cpu(sp->size); - up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS); - if (!up_e) - return -ENOMEM; - memcpy(up_e, sp, sp_size); + sp_size = le16_to_cpu(sp->size); + up_e = kmalloc(sp_size + sizeof(u64), GFP_NOFS); + if (!up_e) + return -ENOMEM; + memcpy(up_e, sp, sp_size); - used1 = le32_to_cpu(hdr1->used); - hdr1_saved = kmemdup(hdr1, used1, GFP_NOFS); - if (!hdr1_saved) { - err = -ENOMEM; - goto out; - } + used1 = le32_to_cpu(hdr1->used); + hdr1_saved = kmemdup(hdr1, used1, GFP_NOFS); + if (!hdr1_saved) { + err = -ENOMEM; + goto out; + } - if (!hdr1->flags) { - up_e->flags |= NTFS_IE_HAS_SUBNODES; - up_e->size = cpu_to_le16(sp_size + sizeof(u64)); - sub_vbn = NULL; - } else { - t_vbn = de_get_vbn_le(up_e); - sub_vbn = &t_vbn; - } + if (!hdr1->flags) { + up_e->flags |= NTFS_IE_HAS_SUBNODES; + up_e->size = cpu_to_le16(sp_size + sizeof(u64)); + sub_vbn = NULL; + } else { + t_vbn = de_get_vbn_le(up_e); + sub_vbn = &t_vbn; + } - /* Allocate on disk a new index allocation buffer. */ - err = indx_add_allocate(indx, ni, &new_vbn); - if (err) - goto out; + /* Allocate on disk a new index allocation buffer. */ + err = indx_add_allocate(indx, ni, &new_vbn); + if (err) + goto out; - /* Allocate and format memory a new index buffer. */ - n2 = indx_new(indx, ni, new_vbn, sub_vbn); - if (IS_ERR(n2)) { - err = PTR_ERR(n2); - goto out; - } + /* Allocate and format memory a new index buffer. */ + n2 = indx_new(indx, ni, new_vbn, sub_vbn); + if (IS_ERR(n2)) { + err = PTR_ERR(n2); + goto out; + } - hdr2 = &n2->index->ihdr; + hdr2 = &n2->index->ihdr; - /* Make sp a parent for new buffer. */ - de_set_vbn(up_e, new_vbn); + /* Make sp a parent for new buffer. */ + de_set_vbn(up_e, new_vbn); - /* Copy all the entries <= sp into the new buffer. */ - de_t = hdr_first_de(hdr1); - to_copy = PtrOffset(de_t, sp); - hdr_insert_head(hdr2, de_t, to_copy); + /* Copy all the entries <= sp into the new buffer. */ + de_t = hdr_first_de(hdr1); + to_copy = PtrOffset(de_t, sp); + hdr_insert_head(hdr2, de_t, to_copy); - /* Remove all entries (sp including) from hdr1. */ - used = used1 - to_copy - sp_size; - memmove(de_t, Add2Ptr(sp, sp_size), used - le32_to_cpu(hdr1->de_off)); - hdr1->used = cpu_to_le32(used); + /* Remove all entries (sp including) from hdr1. */ + used = used1 - to_copy - sp_size; + memmove(de_t, Add2Ptr(sp, sp_size), + used - le32_to_cpu(hdr1->de_off)); + hdr1->used = cpu_to_le32(used); - /* - * Insert new entry into left or right buffer - * (depending on sp <=> new_de). - */ - hdr_insert_de(indx, - (*indx->cmp)(new_de + 1, le16_to_cpu(new_de->key_size), - up_e + 1, le16_to_cpu(up_e->key_size), - ctx) < 0 ? - hdr2 : - hdr1, - new_de, NULL, ctx); + /* + * Insert new entry into left or right buffer + * (depending on sp <=> new_de). + */ + hdr_insert_de(indx, + (*indx->cmp)(new_de + 1, + le16_to_cpu(new_de->key_size), + up_e + 1, le16_to_cpu(up_e->key_size), + ctx) < 0 ? hdr2 : hdr1, + new_de, NULL, ctx); - indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits); + indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits); - indx_write(indx, ni, n1, 0); - indx_write(indx, ni, n2, 0); + indx_write(indx, ni, n1, 0); + indx_write(indx, ni, n2, 0); - put_indx_node(n2); + put_indx_node(n2); - /* - * We've finished splitting everybody, so we are ready to - * insert the promoted entry into the parent. - */ - if (!level) { - /* Insert in root. */ - err = indx_insert_into_root(indx, ni, up_e, NULL, ctx, fnd, 0); - } else { /* - * The target buffer's parent is another index buffer. - * TODO: Remove recursion. + * We've finished splitting everybody, so we are ready to + * insert the promoted entry into the parent. */ - err = indx_insert_into_buffer(indx, ni, root, up_e, ctx, - level - 1, fnd); - } + if (!level) { + /* Insert in root. */ + err = indx_insert_into_root(indx, ni, up_e, + NULL, ctx, fnd, 0); + } else { + /* + * The target buffer's parent is another index + * buffer. Move to the parent buffer for next + * iteration. + */ + n1 = fnd->nodes[--level]; + hrd1 = &n1->index->ihdr; + new_de = up_e; + continue; + } - if (err) { - /* - * Undo critical operations. - */ - indx_mark_free(indx, ni, new_vbn >> indx->idx2vbn_bits); - memcpy(hdr1, hdr1_saved, used1); - indx_write(indx, ni, n1, 0); + if (err) { + /* + * Undo critical operations. + */ + indx_mark_free(indx, ni, + new_vbn >> indx->idx2vbn_bits); + memcpy(hdr1, hdr1_saved, used1); + indx_write(indx, ni, n1, 0); + } } out: -- 2.34.1