summaryrefslogtreecommitdiffstats
path: root/fs/jfs/jfs_dtree.h
diff options
context:
space:
mode:
Diffstat (limited to 'fs/jfs/jfs_dtree.h')
-rw-r--r--fs/jfs/jfs_dtree.h256
1 files changed, 256 insertions, 0 deletions
diff --git a/fs/jfs/jfs_dtree.h b/fs/jfs/jfs_dtree.h
new file mode 100644
index 000000000..175828964
--- /dev/null
+++ b/fs/jfs/jfs_dtree.h
@@ -0,0 +1,256 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ * Copyright (C) International Business Machines Corp., 2000-2002
+ */
+#ifndef _H_JFS_DTREE
+#define _H_JFS_DTREE
+
+/*
+ * jfs_dtree.h: directory B+-tree manager
+ */
+
+#include "jfs_btree.h"
+
+typedef union {
+ struct {
+ tid_t tid;
+ struct inode *ip;
+ u32 ino;
+ } leaf;
+ pxd_t xd;
+} ddata_t;
+
+
+/*
+ * entry segment/slot
+ *
+ * an entry consists of type dependent head/only segment/slot and
+ * additional segments/slots linked vi next field;
+ * N.B. last/only segment of entry is terminated by next = -1;
+ */
+/*
+ * directory page slot
+ */
+struct dtslot {
+ s8 next; /* 1: */
+ s8 cnt; /* 1: */
+ __le16 name[15]; /* 30: */
+}; /* (32) */
+
+
+#define DATASLOTSIZE 16
+#define L2DATASLOTSIZE 4
+#define DTSLOTSIZE 32
+#define L2DTSLOTSIZE 5
+#define DTSLOTHDRSIZE 2
+#define DTSLOTDATASIZE 30
+#define DTSLOTDATALEN 15
+
+/*
+ * internal node entry head/only segment
+ */
+struct idtentry {
+ pxd_t xd; /* 8: child extent descriptor */
+
+ s8 next; /* 1: */
+ u8 namlen; /* 1: */
+ __le16 name[11]; /* 22: 2-byte aligned */
+}; /* (32) */
+
+#define DTIHDRSIZE 10
+#define DTIHDRDATALEN 11
+
+/* compute number of slots for entry */
+#define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15))
+
+
+/*
+ * leaf node entry head/only segment
+ *
+ * For legacy filesystems, name contains 13 wchars -- no index field
+ */
+struct ldtentry {
+ __le32 inumber; /* 4: 4-byte aligned */
+ s8 next; /* 1: */
+ u8 namlen; /* 1: */
+ __le16 name[11]; /* 22: 2-byte aligned */
+ __le32 index; /* 4: index into dir_table */
+}; /* (32) */
+
+#define DTLHDRSIZE 6
+#define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */
+#define DTLHDRDATALEN 11
+
+/*
+ * dir_table used for directory traversal during readdir
+ */
+
+/*
+ * Keep persistent index for directory entries
+ */
+#define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)
+
+/*
+ * Maximum entry in inline directory table
+ */
+#define MAX_INLINE_DIRTABLE_ENTRY 13
+
+struct dir_table_slot {
+ u8 rsrvd; /* 1: */
+ u8 flag; /* 1: 0 if free */
+ u8 slot; /* 1: slot within leaf page of entry */
+ u8 addr1; /* 1: upper 8 bits of leaf page address */
+ __le32 addr2; /* 4: lower 32 bits of leaf page address -OR-
+ index of next entry when this entry was deleted */
+}; /* (8) */
+
+/*
+ * flag values
+ */
+#define DIR_INDEX_VALID 1
+#define DIR_INDEX_FREE 0
+
+#define DTSaddress(dir_table_slot, address64)\
+{\
+ (dir_table_slot)->addr1 = ((u64)address64) >> 32;\
+ (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
+}
+
+#define addressDTS(dts)\
+ ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )
+
+/* compute number of slots for entry */
+#define NDTLEAF_LEGACY(klen) (DIV_ROUND_UP((2 + (klen)), 15))
+#define NDTLEAF NDTINTERNAL
+
+
+/*
+ * directory root page (in-line in on-disk inode):
+ *
+ * cf. dtpage_t below.
+ */
+typedef union {
+ struct {
+ struct dasd DASD; /* 16: DASD limit/usage info */
+
+ u8 flag; /* 1: */
+ u8 nextindex; /* 1: next free entry in stbl */
+ s8 freecnt; /* 1: free count */
+ s8 freelist; /* 1: freelist header */
+
+ __le32 idotdot; /* 4: parent inode number */
+
+ s8 stbl[8]; /* 8: sorted entry index table */
+ } header; /* (32) */
+
+ struct dtslot slot[9];
+} dtroot_t;
+
+#define PARENT(IP) \
+ (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))
+
+#define DTROOTMAXSLOT 9
+
+#define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)
+
+
+/*
+ * directory regular page:
+ *
+ * entry slot array of 32 byte slot
+ *
+ * sorted entry slot index table (stbl):
+ * contiguous slots at slot specified by stblindex,
+ * 1-byte per entry
+ * 512 byte block: 16 entry tbl (1 slot)
+ * 1024 byte block: 32 entry tbl (1 slot)
+ * 2048 byte block: 64 entry tbl (2 slot)
+ * 4096 byte block: 128 entry tbl (4 slot)
+ *
+ * data area:
+ * 512 byte block: 16 - 2 = 14 slot
+ * 1024 byte block: 32 - 2 = 30 slot
+ * 2048 byte block: 64 - 3 = 61 slot
+ * 4096 byte block: 128 - 5 = 123 slot
+ *
+ * N.B. index is 0-based; index fields refer to slot index
+ * except nextindex which refers to entry index in stbl;
+ * end of entry stot list or freelist is marked with -1.
+ */
+typedef union {
+ struct {
+ __le64 next; /* 8: next sibling */
+ __le64 prev; /* 8: previous sibling */
+
+ u8 flag; /* 1: */
+ u8 nextindex; /* 1: next entry index in stbl */
+ s8 freecnt; /* 1: */
+ s8 freelist; /* 1: slot index of head of freelist */
+
+ u8 maxslot; /* 1: number of slots in page slot[] */
+ u8 stblindex; /* 1: slot index of start of stbl */
+ u8 rsrvd[2]; /* 2: */
+
+ pxd_t self; /* 8: self pxd */
+ } header; /* (32) */
+
+ struct dtslot slot[128];
+} dtpage_t;
+
+#define DTPAGEMAXSLOT 128
+
+#define DT8THPGNODEBYTES 512
+#define DT8THPGNODETSLOTS 1
+#define DT8THPGNODESLOTS 16
+
+#define DTQTRPGNODEBYTES 1024
+#define DTQTRPGNODETSLOTS 1
+#define DTQTRPGNODESLOTS 32
+
+#define DTHALFPGNODEBYTES 2048
+#define DTHALFPGNODETSLOTS 2
+#define DTHALFPGNODESLOTS 64
+
+#define DTFULLPGNODEBYTES 4096
+#define DTFULLPGNODETSLOTS 4
+#define DTFULLPGNODESLOTS 128
+
+#define DTENTRYSTART 1
+
+/* get sorted entry table of the page */
+#define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
+ ((dtroot_t *)(p))->header.stbl : \
+ (s8 *)&(p)->slot[(p)->header.stblindex] )
+
+/*
+ * Flags for dtSearch
+ */
+#define JFS_CREATE 1
+#define JFS_LOOKUP 2
+#define JFS_REMOVE 3
+#define JFS_RENAME 4
+
+/*
+ * Maximum file offset for directories.
+ */
+#define DIREND INT_MAX
+
+/*
+ * external declarations
+ */
+extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
+
+extern int dtSearch(struct inode *ip, struct component_name * key,
+ ino_t * data, struct btstack * btstack, int flag);
+
+extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
+ ino_t * ino, struct btstack * btstack);
+
+extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
+ ino_t * data, int flag);
+
+extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
+ ino_t * orig_ino, ino_t new_ino, int flag);
+
+extern int jfs_readdir(struct file *file, struct dir_context *ctx);
+#endif /* !_H_JFS_DTREE */