Skip to contentSkip to conversation

delete unused nodes in ext2fs_extent_delete

PATCH In review Eric Sandeen 2 participants 4 messages May 20, 2008 – May 31, 2008

lore
Share & tools
lore

Eric Sandeen

author
#0 lore raw

PATCH 1/1 delete unused nodes in ext2fs_extent_delete

This patch causes ext2fs_extent_delete to remove an extent node if the last record in it has been deleted.

The parent node is also updated, and the inode block count is decremented.

Passing in the EXT2_EXTENT_DELETE_KEEP_EMPTY flag will allow the empty node to remain.

(A bit of a quick hack but seems to work for me)

Signed-off-by Eric Sandeen <[email protected]>

---

lib/ext2fs/ext2fs.h +4 -0
index c6ac317..d237bd3 100644
@@ -336,6 +336,10 @@ typedef struct ext2_extent_path *ext2_extent_path_t;
 #define EXT2_EXTENT_INSERT_NOSPLIT	0x0002 /* insert may not cause split */
 
 /*
+ * Flags used by ext2fs_extent_delete()
+ */
+#define EXT2_EXTENT_DELETE_KEEP_EMPTY	0x001 /* keep node if last extnt gone */
+/*
  * Data structure returned by ext2fs_extent_get_info()
  */
 struct ext2_extent_info {
lib/ext2fs/extent.c +23 -6
index 357ca34..f86bf0d 100644
@@ -1169,8 +1169,7 @@ done:
 	return retval;
 }
 
-errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, 
-			       int flags EXT2FS_ATTR((unused)))
+errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
 {
 	struct extent_path		*path;
 	char 				*cp;

@@ -1201,13 +1200,31 @@ errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle,
 		path->curr = ix;
 	}
 	path->entries--;
-	if (path->entries == 0)
+	/* if non-root node has no entries left, remove it & parent ptr to it */
+	if (path->entries == 0 && handle->level) {
 		path->curr = 0;
 
-	eh = (struct ext3_extent_header *) path->buf;
-	eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
+		if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) {
+			struct ext2fs_extent	extent;
 
-	retval = update_path(handle);
+			retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP,
+								&extent);
+			if (retval)
+				return retval;
+
+			retval = ext2fs_extent_delete(handle, 0);
+			handle->inode->i_blocks -= handle->fs->blocksize / 512;
+			retval = ext2fs_write_inode_full(handle->fs,
+					handle->ino, handle->inode,
+					EXT2_INODE_SIZE(handle->fs->super));
+			ext2fs_block_alloc_stats(handle->fs, extent.e_pblk, -1);
+		}
+	} else {
+		eh = (struct ext3_extent_header *) path->buf;
+		eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
+
+		retval = update_path(handle);
+	}
 
 	return retval;
 }
#1 lore raw
Quoted 2 lines · Eric Sandeen

This patch causes ext2fs_extent_delete to remove an extent node if the last record in it has been deleted.

I needed to apply this fix on top of your patch; otherwise, when deleting the last extent in the root node, the current extent pointer is left pointing at an invalid extent.

- Ted

lib/ext2fs/extent.c +3 -3
index c3863b5..19d7feb 100644
@@ -1225,11 +1225,11 @@ errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
 		ix--;
 		path->curr = ix;
 	}
-	path->entries--;
-	/* if non-root node has no entries left, remove it & parent ptr to it */
-	if (path->entries == 0 && handle->level) {
+	if (--path->entries == 0)
 		path->curr = 0;
 
+	/* if non-root node has no entries left, remove it & parent ptr to it */
+	if (path->entries == 0 && handle->level) {
 		if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) {
 			struct ext2fs_extent	extent;
 

@@ -1251,7 +1251,6 @@ errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
 
 		retval = update_path(handle);
 	}
author
#2 lore raw
Quoted 7 lines · Theodore Tso
Quoted 2 lines · Eric Sandeen

This patch causes ext2fs_extent_delete to remove an extent node if the last record in it has been deleted.

I needed to apply this fix on top of your patch; otherwise, when deleting the last extent in the root node, the current extent pointer is left pointing at an invalid extent.

Looks good, sorry for missing that!

-Eric

Quoted 29 lines

- Ted

lib/ext2fs/extent.c +3 -4
index c3863b5..19d7feb 100644
@@ -1225,11 +1225,11 @@ errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
 		ix--;
 		path->curr = ix;
 	}
-	path->entries--;
-	/* if non-root node has no entries left, remove it & parent ptr to it */
-	if (path->entries == 0 && handle->level) {
+	if (--path->entries == 0)
 		path->curr = 0;
 
+	/* if non-root node has no entries left, remove it & parent ptr to it */
+	if (path->entries == 0 && handle->level) {
 		if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) {
 			struct ext2fs_extent	extent;
 

@@ -1251,7 +1251,6 @@ errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
 
 		retval = update_path(handle);
 	}
-
 	return retval;
 }
#3 lore raw

One more addition. If we delete the last entry in the root inode, we need to set the depth of the tree to 0.

- Ted

lib/ext2fs/extent.c +0 -0
index 19d7feb..65b2003 100644
@@ -1248,7 +1248,8 @@ errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
 	} else {
 		eh = (struct ext3_extent_header *) path->buf;
 		eh->eh_entries = ext2fs_cpu_to_le16(path->entries);