update uninitialized-block-groups.patch and mballoc-core.patch

Hi,

This contain fixes for making mballoc work with uninitialized block group.

The patches can be downloaded from

http://www.radian.org/~kvaneesh/ext4/oct-3-2007/

The diff is attached below to find out what changed.

Mingming,

Can you replace the patch in the patch queue with the above two patches ? -aneesh

index 321ad1e..47f70a8 100644
@@ -90,8 +90,19 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,

			bit_max += 1;
	}

- /* Last and first groups are always initialized */
- free_blocks = EXT4_BLOCKS_PER_GROUP(sb) - bit_max;
+ if (block_group == sbi->s_gdb_count - 1) {
+ /*
+ * Even though mke2fs always initialize first and last group
+ * if some other tool enabled the EXT4_BG_BLOCK_UNINIT we need
+ * to make sure we calculate the right free blocks
+ */
+ free_blocks = ext4_blocks_count(sbi->s_es) -
+ le32_to_cpu(sbi->s_es->s_first_data_block) -
+ (EXT4_BLOCKS_PER_GROUP(sb) * sbi->s_groups_count) -
+ bit_max;
+ } else {
+ free_blocks = EXT4_BLOCKS_PER_GROUP(sb) - bit_max;
+ }

	if (bh) {
		for (bit = 0; bit < bit_max; bit++)
@@ -106,11 +117,20 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
		for (bit = (ext4_inode_table(sb, gdp) - start),
		     bit_max = bit + sbi->s_itb_per_group; bit < bit_max; bit++)
			ext4_set_bit(bit, bh->b_data);

+
+ /*
+ * Also if the number of blocks within the group is less than the
+ * blocksize * 8 ( which is the size of bitmap ), set rest of the
+ * block bitmap to 1
+ */
+ mark_bitmap_end(EXT4_BLOCKS_PER_GROUP(sb),

+					sb->s_blocksize * 8, bh->b_data);
	}

	return free_blocks - sbi->s_itb_per_group - 2;
}

+
/*
* The free blocks are managed by bitmaps. A file system contains several
* blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap

index 9310979..1577910 100644
@@ -8,9 +8,6 @@
 

#ifndef _LINUX_EXT4_GROUP_H
#define _LINUX_EXT4_GROUP_H
-#if defined(CONFIG_CRC16)
-#include <linux/crc16.h>
-#endif

extern __le16 ext4_group_desc_csum(struct ext4_sb_info *sbi, __u32 group,

				   struct ext4_group_desc *gdp);
@@ -26,4 +23,5 @@ extern unsigned ext4_init_block_bitmap(struct super_block *sb,
extern unsigned ext4_init_inode_bitmap(struct super_block *sb,
				       struct buffer_head *bh, int group,
				       struct ext4_group_desc *desc);

+extern void mark_bitmap_end(int start_bit, int end_bit, char *bitmap); #endif /* _LINUX_EXT4_GROUP_H */

index 1fa418c..e4c421e 100644
@@ -49,7 +49,7 @@
 * need to use it within a single byte (to ensure we get endianness right).
 * We can use memset for the rest of the bitmap as there are no other users.
 */
-static void mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
+void mark_bitmap_end(int start_bit, int end_bit, char *bitmap)

{
	int i;

index 5ffc80b..4409c0c 100644
@@ -34,6 +34,7 @@

#include <linux/pagemap.h>
#include <linux/seq_file.h>
#include <linux/version.h>
+#include "group.h"

/*
* MUSTDO:
@@ -893,6 +894,13 @@ static int ext4_mb_init_cache(struct page *page, char *incore)

			continue;
		}

+ if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
+ ext4_init_block_bitmap(sb, bh[i],
+ first_group + i, desc);
+ set_buffer_uptodate(bh[i]);
+ unlock_buffer(bh[i]);
+ continue;
+ }

		get_bh(bh[i]);
		bh[i]->b_end_io = end_buffer_read_sync;
		submit_bh(READ, bh[i]);

@@ -1702,11 +1710,10 @@ static void ext4_mb_scan_aligned(struct ext4_allocation_context *ac, static int ext4_mb_good_group(struct ext4_allocation_context *ac,
int group, int cr)
{
+ unsigned free, fragments;
+ unsigned i, bits;

+	struct ext4_group_desc *desc;
	struct ext4_group_info *grp = EXT4_GROUP_INFO(ac->ac_sb, group);

- unsigned free;
- unsigned fragments;
- unsigned i;
- unsigned bits;

	BUG_ON(cr < 0 || cr >= 4);
	BUG_ON(EXT4_MB_GRP_NEED_INIT(grp));
@@ -1721,6 +1728,11 @@ static int ext4_mb_good_group(struct ext4_allocation_context *ac,
	switch (cr) {
	case 0:
		BUG_ON(ac->ac_2order == 0);

+ /* If this group is uninitialized, skip it initially */
+ desc = ext4_get_group_desc(ac->ac_sb, group, NULL);
+ if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
+ return 0;
+

		bits = ac->ac_sb->s_blocksize_bits + 1;
		for (i = ac->ac_2order; i <= bits; i++)
			if (grp->bb_counters[i] > 0)
@@ -1805,6 +1817,7 @@ repeat:
		ac->ac_criteria = cr;
		for (i = 0; i < EXT4_SB(sb)->s_groups_count; group++, i++) {
			struct ext4_group_info *grp;

+ struct ext4_group_desc *desc;

			if (group == EXT4_SB(sb)->s_groups_count)
				group = 0;
@@ -1844,12 +1857,16 @@ repeat:
			}

			ac->ac_groups_scanned++;

- if (cr == 0)
+ desc = ext4_get_group_desc(sb, group, NULL);
+ if (cr == 0 || (desc->bg_flags &
+ cpu_to_le16(EXT4_BG_BLOCK_UNINIT) &&

+					ac->ac_2order != 0)) {
				ext4_mb_simple_scan_group(ac, &e4b);
-			else if (cr == 1 && ac->ac_g_ex.fe_len == sbi->s_stripe)
+			} else if (cr == 1 && ac->ac_g_ex.fe_len == sbi->s_stripe) {
				ext4_mb_scan_aligned(ac, &e4b);
-			else
+			} else {
				ext4_mb_complex_scan_group(ac, &e4b);

+ }

			ext4_unlock_group(sb, group);
			ext4_mb_release_desc(&e4b);

@@ -2267,11 +2284,8 @@ static void ext4_mb_store_history(struct ext4_allocation_context *ac)

static int ext4_mb_init_backend(struct super_block *sb) {
+ int i, j, len, metalen;

	struct ext4_sb_info *sbi = EXT4_SB(sb);
-	int i;
-	int j;
-	int len;
-	int metalen;
	int num_meta_group_infos =
		(sbi->s_groups_count + EXT4_DESC_PER_BLOCK(sb) - 1) >>
			EXT4_DESC_PER_BLOCK_BITS(sb);
@@ -2321,7 +2335,7 @@ static int ext4_mb_init_backend(struct super_block *sb)
			sbi->s_group_info[i >> EXT4_DESC_PER_BLOCK_BITS(sb)];
		j = i & (EXT4_DESC_PER_BLOCK(sb) - 1);

- meta_group_info[j] = kmalloc(len, GFP_KERNEL);

+		meta_group_info[j] = kzalloc(len, GFP_KERNEL);
		if (meta_group_info[j] == NULL) {
			printk(KERN_ERR "EXT4-fs: can't allocate buddy mem\n");
			i--;
@@ -2333,14 +2347,20 @@ static int ext4_mb_init_backend(struct super_block *sb)
				"EXT4-fs: can't read descriptor %u\n", i);
			goto err_freebuddy;
		}
-		memset(meta_group_info[j], 0, len);
		set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
			&meta_group_info[j]->bb_state);

- /* initialize bb_free to be able to skip
- * empty groups without initialization */
- meta_group_info[j]->bb_free =
- le16_to_cpu(desc->bg_free_blocks_count);
+ /*
+ * initialize bb_free to be able to skip
+ * empty groups without initialization
+ */
+ if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
+ meta_group_info[j]->bb_free =
+ ext4_free_blocks_after_init(sb, i, desc);
+ } else {
+ meta_group_info[j]->bb_free =
+ le16_to_cpu(desc->bg_free_blocks_count);
+ }

		INIT_LIST_HEAD(&meta_group_info[j]->bb_prealloc_list);

@@ -2919,9 +2939,17 @@ static int ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,

		    ac->ac_b_ex.fe_len);

	spin_lock(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group));

+ if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
+ gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
+ gdp->bg_free_blocks_count =
+ cpu_to_le16(ext4_free_blocks_after_init(sb,
+ ac->ac_b_ex.fe_group,
+ gdp));
+ }

	gdp->bg_free_blocks_count =
		cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count)
				- ac->ac_b_ex.fe_len);
+	gdp->bg_checksum = ext4_group_desc_csum(sbi, ac->ac_b_ex.fe_group, gdp);
	spin_unlock(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group));
	percpu_counter_mod(&sbi->s_freeblocks_counter, - ac->ac_b_ex.fe_len);

@@ -4066,7 +4094,7 @@ ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,

#if 0
		static int ext4_mballoc_warning = 0;
		if (ext4_mballoc_warning++ == 0)
-			printk(KERN_ERR "EXT3-fs: multiblock request with "
+			printk(KERN_ERR "EXT4-fs: multiblock request with "
					"mballoc disabled!\n");
		ar->len = 1;
#endif
@@ -4353,6 +4381,7 @@ do_more:
	spin_lock(sb_bgl_lock(sbi, block_group));
	gdp->bg_free_blocks_count =
		cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count) + count);
+	gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp);
	spin_unlock(sb_bgl_lock(sbi, block_group));
	percpu_counter_mod(&sbi->s_freeblocks_counter, count);

index 3359450..19ff743 100644
@@ -141,25 +141,6 @@ static struct buffer_head *bclean(handle_t *handle, struct super_block *sb,

}

/*
- * To avoid calling the atomic setbit hundreds or thousands of times, we only
- * need to use it within a single byte (to ensure we get endianness right).
- * We can use memset for the rest of the bitmap as there are no other users.
- */
-static void mark_bitmap_end(int start_bit, int end_bit, char *bitmap) -{
- int i;
-
- if (start_bit >= end_bit)
- return;
-
- ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
- for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
- ext4_set_bit(i, bitmap);
- if (i < end_bit)
- memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
-}
-
-/*
* Set up the block and inode bitmaps, and the inode table for the new group.
* This doesn't need to be part of the main transaction, since we are only
* changing blocks outside the actual filesystem. We still do journaling to

yes s_first_data_block is always decremented to find total number of blocks occupied by the reset of the group. But now looking at it again i guess i need to have

EXT4_BLOCKS_PER_GROUP(sb) * sbi->s_groups_count

as

EXT4_BLOCKS_PER_GROUP(sb) * (sbi->s_groups_count -1 )

Also for the last group i need to mark_end_bitmap_end from a lower value.

if ( last_group) {
group_block = ext4_blocks_count(sbi->s_es) - e32_to_cpu(sbi->s_es->s_first_data_block) -

             EXT4_BLOCKS_PER_GROUP(sb) * (sbi->s_groups_count - 1)

} else {
group_block = EXT4_BLOCKS_PER_GROUP(sb)

}

free_blocks = group_block - bit_max

mark_bitmap_end(group_block, ...)

-aneesh

index 8613914..34b1e11 100644
@@ -50,7 +50,7 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,

{
	unsigned long start;
	int bit, bit_max;
-	unsigned free_blocks;
+	unsigned free_blocks, group_blocks;
	struct ext4_sb_info *sbi = EXT4_SB(sb);

	if (bh) {

@@ -96,14 +96,15 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
* if some other tool enabled the EXT4_BG_BLOCK_UNINIT we need
* to make sure we calculate the right free blocks
*/
- free_blocks = ext4_blocks_count(sbi->s_es) -
- le32_to_cpu(sbi->s_es->s_first_data_block) -
- (EXT4_BLOCKS_PER_GROUP(sb) * sbi->s_groups_count) -
- bit_max;
+ group_blocks = ext4_blocks_count(sbi->s_es) -
+ le32_to_cpu(sbi->s_es->s_first_data_block) -

+			(EXT4_BLOCKS_PER_GROUP(sb) * (sbi->s_groups_count -1));
	} else {
-		free_blocks = EXT4_BLOCKS_PER_GROUP(sb) - bit_max;
+		group_blocks = EXT4_BLOCKS_PER_GROUP(sb);
	}

+ free_blocks = group_blocks - bit_max;
+

	if (bh) {
		for (bit = 0; bit < bit_max; bit++)
			ext4_set_bit(bit, bh->b_data);

@@ -123,8 +124,7 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
* blocksize * 8 ( which is the size of bitmap ), set rest of the
* block bitmap to 1
*/
- mark_bitmap_end(EXT4_BLOCKS_PER_GROUP(sb),
- sb->s_blocksize * 8, bh->b_data);

+		mark_bitmap_end(group_blocks, sb->s_blocksize * 8, bh->b_data);
	}

	return free_blocks - sbi->s_itb_per_group - 2;

Updated ext4 patch queue with your updated uninit blk group and mballoc patch.

Mingming

That is correct. Thanks for catching this.

Did you test the patch in the patch queue. It actually changes the above line slightly differently.

Updated patch attached.

-aneesh

Ext4: Uninitialized Block Groups

From: Andreas Dilger <[email protected]>

In pass1 of e2fsck, every inode table in the fileystem is scanned and checked, regardless of whether it is in use. This is this the most time consuming part of the filesystem check. The unintialized block group feature can greatly reduce e2fsck time by eliminating checking of uninitialized inodes.

With this feature, there is a a high water mark of used inodes for each block group. Block and inode bitmaps can be uninitialized on disk via a flag in the group descriptor to avoid reading or scanning them at e2fsck time. A checksum of each group descriptor is used to ensure that corruption in the group descriptor's bit flags does not cause incorrect operation.

The feature is enabled through a mkfs option

mke2fs /dev/ -O uninit_groups

A patch adding support for uninitialized block groups to e2fsprogs tools has been posted to the linux-ext4 mailing list.

The patches have been stress tested with fsstress and fsx. In performance tests testing e2fsck time, we have seen that e2fsck time on ext3 grows linearly with the total number of inodes in the filesytem. In ext4 with the uninitialized block groups feature, the e2fsck time is constant, based solely on the number of used inodes rather than the total inode count. Since typical ext4 filesystems only use 1-10% of their inodes, this feature can greatly reduce e2fsck time for users. With performance improvement of 2-20 times, depending on how full the filesystem is.

The attached graph shows the major improvements in e2fsck times in filesystems with a large total inode count, but few inodes in use.

In each group descriptor if we have

EXT4_BG_INODE_UNINIT set in bg_flags:
Inode table is not initialized/used in this group. So we can skip the consistency check during fsck.
EXT4_BG_BLOCK_UNINIT set in bg_flags:
No block in the group is used. So we can skip the block bitmap verification for this group.

We also add two new fields to group descriptor as a part of uninitialized group patch.

        __le16  bg_itable_unused;       /* Unused inodes count */
        __le16  bg_checksum;            /* crc16(sb_uuid+group+desc) */

bg_itable_unused:

If we have EXT4_BG_INODE_UNINIT not set in bg_flags then bg_itable_unused will give the offset within the inode table till the inodes are used. This can be used by fsck to skip list of inodes that are marked unused.

bg_checksum:
Now that we depend on bg_flags and bg_itable_unused to determine the block and inode usage, we need to make sure group descriptor is not corrupt. We add checksum to group descriptor to detect corruption. If the descriptor is found to be corrupt, we mark all the blocks and inodes in the group used.

---

 fs/Kconfig              |    1 
 fs/ext4/balloc.c        |  112 +++++++++++++++++++++++++++++++++++-
 fs/ext4/group.h         |   27 +++++++++
 fs/ext4/ialloc.c        |  146 ++++++++++++++++++++++++++++++++++++++++++++---
 fs/ext4/resize.c        |   21 +------
 fs/ext4/super.c         |   47 +++++++++++++++
 include/linux/ext4_fs.h |   16 ++++-
 7 files changed, 335 insertions(+), 35 deletions(-)
 create mode 100644 fs/ext4/group.h

index f9eed6d..97eef97 100644
@@ -140,6 +140,7 @@ config EXT4DEV_FS
 	tristate "Ext4dev/ext4 extended fs support development (EXPERIMENTAL)"
 	depends on EXPERIMENTAL
 	select JBD2
+	select CRC16
 	help
 	  Ext4dev is a predecessor filesystem of the next generation
 	  extended fs ext4, based on ext3 filesystem code. It will be

new file mode 100644
index 0000000..1577910
@@ -0,0 +1,27 @@
+/*
+ *  linux/fs/ext4/group.h
+ *
+ * Copyright (C) 2007 Cluster File Systems, Inc
+ *
+ * Author: Andreas Dilger <[email protected]>
+ */
+
+#ifndef _LINUX_EXT4_GROUP_H
+#define _LINUX_EXT4_GROUP_H
+
+extern __le16 ext4_group_desc_csum(struct ext4_sb_info *sbi, __u32 group,
+				   struct ext4_group_desc *gdp);
+extern int ext4_group_desc_csum_verify(struct ext4_sb_info *sbi, __u32 group,
+				       struct ext4_group_desc *gdp);
+struct buffer_head *read_block_bitmap(struct super_block *sb,
+				      unsigned int block_group);
+extern unsigned ext4_init_block_bitmap(struct super_block *sb,
+				       struct buffer_head *bh, int group,
+				       struct ext4_group_desc *desc);
+#define ext4_free_blocks_after_init(sb, group, desc)			\
+		ext4_init_block_bitmap(sb, NULL, group, desc)
+extern unsigned ext4_init_inode_bitmap(struct super_block *sb,
+				       struct buffer_head *bh, int group,
+				       struct ext4_group_desc *desc);
+extern void mark_bitmap_end(int start_bit, int end_bit, char *bitmap);
+#endif /* _LINUX_EXT4_GROUP_H */

index aa11d7d..19ff743 100644
@@ -16,6 +16,7 @@
 #include <linux/errno.h>
 #include <linux/slab.h>
 
+#include "group.h"
 
 #define outside(b, first, last)	((b) < (first) || (b) >= (last))
 #define inside(b, first, last)	((b) >= (first) && (b) < (last))

@@ -140,25 +141,6 @@ static struct buffer_head *bclean(handle_t *handle, struct super_block *sb,
 }
 
 /*
- * To avoid calling the atomic setbit hundreds or thousands of times, we only
- * need to use it within a single byte (to ensure we get endianness right).
- * We can use memset for the rest of the bitmap as there are no other users.
- */
-static void mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
-{
-	int i;
-
-	if (start_bit >= end_bit)
-		return;
-
-	ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
-	for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
-		ext4_set_bit(i, bitmap);
-	if (i < end_bit)
-		memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
-}
-
-/*
  * Set up the block and inode bitmaps, and the inode table for the new group.
  * This doesn't need to be part of the main transaction, since we are only
  * changing blocks outside the actual filesystem.  We still do journaling to

@@ -842,6 +824,7 @@ int ext4_group_add(struct super_block *sb, struct ext4_new_group_data *input)
 	ext4_inode_table_set(sb, gdp, input->inode_table); /* LV FIXME */
 	gdp->bg_free_blocks_count = cpu_to_le16(input->free_blocks_count);
 	gdp->bg_free_inodes_count = cpu_to_le16(EXT4_INODES_PER_GROUP(sb));
+	gdp->bg_checksum = ext4_group_desc_csum(sbi, input->group, gdp);
 
 	/*
 	 * Make the new blocks and inodes valid next.  We do this before

index 151738a..b77b59f 100644
@@ -105,19 +105,25 @@
  */
 struct ext4_group_desc
 {
-	__le32	bg_block_bitmap;		/* Blocks bitmap block */
-	__le32	bg_inode_bitmap;		/* Inodes bitmap block */
+	__le32	bg_block_bitmap;	/* Blocks bitmap block */
+	__le32	bg_inode_bitmap;	/* Inodes bitmap block */
 	__le32	bg_inode_table;		/* Inodes table block */
 	__le16	bg_free_blocks_count;	/* Free blocks count */
 	__le16	bg_free_inodes_count;	/* Free inodes count */
 	__le16	bg_used_dirs_count;	/* Directories count */
-	__u16	bg_flags;
-	__u32	bg_reserved[3];
+	__le16	bg_flags;		/* EXT4_BG_flags (INODE_UNINIT, etc) */
+	__u32	bg_reserved[2];		/* Likely block/inode bitmap checksum */
+	__le16  bg_itable_unused;	/* Unused inodes count */
+	__le16  bg_checksum;		/* crc16(sb_uuid+group+desc) */
 	__le32	bg_block_bitmap_hi;	/* Blocks bitmap block MSB */
 	__le32	bg_inode_bitmap_hi;	/* Inodes bitmap block MSB */
 	__le32	bg_inode_table_hi;	/* Inodes table block MSB */
 };
 
+#define EXT4_BG_INODE_UNINIT	0x0001 /* Inode table/bitmap not in use */
+#define EXT4_BG_BLOCK_UNINIT	0x0002 /* Block bitmap not in use */
+#define EXT4_BG_INODE_ZEROED	0x0004 /* On-disk itable initialized to zero */
+
 #ifdef __KERNEL__
 #include <linux/ext4_fs_i.h>
 #include <linux/ext4_fs_sb.h>

@@ -665,6 +671,7 @@ static inline int ext4_valid_inum(struct super_block *sb, unsigned long ino)
 #define EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER	0x0001
 #define EXT4_FEATURE_RO_COMPAT_LARGE_FILE	0x0002
 #define EXT4_FEATURE_RO_COMPAT_BTREE_DIR	0x0004
+#define EXT4_FEATURE_RO_COMPAT_GDT_CSUM		0x0010
 #define EXT4_FEATURE_RO_COMPAT_DIR_NLINK	0x0020
 #define EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE	0x0040
 

@@ -684,6 +691,7 @@ static inline int ext4_valid_inum(struct super_block *sb, unsigned long ino)
 					 EXT4_FEATURE_INCOMPAT_64BIT)
 #define EXT4_FEATURE_RO_COMPAT_SUPP	(EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER| \
 					 EXT4_FEATURE_RO_COMPAT_LARGE_FILE| \
+					 EXT4_FEATURE_RO_COMPAT_GDT_CSUM| \
 					 EXT4_FEATURE_RO_COMPAT_DIR_NLINK | \
 					 EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE | \
 					 EXT4_FEATURE_RO_COMPAT_BTREE_DIR)