public inbox for ntfs3@lists.linux.dev
 help / color / mirror / Atom feed
* [PATCH] fs/ntfs3: Remove recursion in indx_insert_into_buffer
@ 2024-06-16 13:37 Abhinav Jain
  2024-06-16 17:42 ` kernel test robot
  2024-06-16 18:35 ` kernel test robot
  0 siblings, 2 replies; 3+ messages in thread
From: Abhinav Jain @ 2024-06-16 13:37 UTC (permalink / raw)
  To: almaz.alexandrovich, ntfs3, linux-kernel
  Cc: skhan, javier.carrasco.cruz, jain.abhinav177

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 <jain.abhinav177@gmail.com>
---
 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


^ permalink raw reply related	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2024-06-16 18:35 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-06-16 13:37 [PATCH] fs/ntfs3: Remove recursion in indx_insert_into_buffer Abhinav Jain
2024-06-16 17:42 ` kernel test robot
2024-06-16 18:35 ` kernel test robot

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox