fs/jfs/jfs_dtree.h

0001 /* SPDX-License-Identifier: GPL-2.0-or-later */
0002 /*
0003  *   Copyright (C) International Business Machines Corp., 2000-2002
0004  */
0005 #ifndef _H_JFS_DTREE
0006 #define _H_JFS_DTREE
0007
0008 /*
0009  *  jfs_dtree.h: directory B+-tree manager
0010  */
0011
0012 #include "jfs_btree.h"
0013
0014 typedef union {
0015     struct {
0016         tid_t tid;
0017         struct inode *ip;
0018         u32 ino;
0019     } leaf;
0020     pxd_t xd;
0021 } ddata_t;
0022
0023
0024 /*
0025  *  entry segment/slot
0026  *
0027  * an entry consists of type dependent head/only segment/slot and
0028  * additional segments/slots linked vi next field;
0029  * N.B. last/only segment of entry is terminated by next = -1;
0030  */
0031 /*
0032  *  directory page slot
0033  */
0034 struct dtslot {
0035     s8 next;        /* 1: */
0036     s8 cnt;         /* 1: */
0037     __le16 name[15];    /* 30: */
0038 };              /* (32) */
0039
0040
0041 #define DATASLOTSIZE    16
0042 #define L2DATASLOTSIZE  4
0043 #define DTSLOTSIZE  32
0044 #define L2DTSLOTSIZE    5
0045 #define DTSLOTHDRSIZE   2
0046 #define DTSLOTDATASIZE  30
0047 #define DTSLOTDATALEN   15
0048
0049 /*
0050  *   internal node entry head/only segment
0051  */
0052 struct idtentry {
0053     pxd_t xd;       /* 8: child extent descriptor */
0054
0055     s8 next;        /* 1: */
0056     u8 namlen;      /* 1: */
0057     __le16 name[11];    /* 22: 2-byte aligned */
0058 };              /* (32) */
0059
0060 #define DTIHDRSIZE  10
0061 #define DTIHDRDATALEN   11
0062
0063 /* compute number of slots for entry */
0064 #define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15))
0065
0066
0067 /*
0068  *  leaf node entry head/only segment
0069  *
0070  *  For legacy filesystems, name contains 13 wchars -- no index field
0071  */
0072 struct ldtentry {
0073     __le32 inumber;     /* 4: 4-byte aligned */
0074     s8 next;        /* 1: */
0075     u8 namlen;      /* 1: */
0076     __le16 name[11];    /* 22: 2-byte aligned */
0077     __le32 index;       /* 4: index into dir_table */
0078 };              /* (32) */
0079
0080 #define DTLHDRSIZE  6
0081 #define DTLHDRDATALEN_LEGACY    13  /* Old (OS/2) format */
0082 #define DTLHDRDATALEN   11
0083
0084 /*
0085  * dir_table used for directory traversal during readdir
0086  */
0087
0088 /*
0089  * Keep persistent index for directory entries
0090  */
0091 #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX)
0092
0093 /*
0094  * Maximum entry in inline directory table
0095  */
0096 #define MAX_INLINE_DIRTABLE_ENTRY 13
0097
0098 struct dir_table_slot {
0099     u8 rsrvd;       /* 1: */
0100     u8 flag;        /* 1: 0 if free */
0101     u8 slot;        /* 1: slot within leaf page of entry */
0102     u8 addr1;       /* 1: upper 8 bits of leaf page address */
0103     __le32 addr2;       /* 4: lower 32 bits of leaf page address -OR-
0104                    index of next entry when this entry was deleted */
0105 };              /* (8) */
0106
0107 /*
0108  * flag values
0109  */
0110 #define DIR_INDEX_VALID 1
0111 #define DIR_INDEX_FREE 0
0112
0113 #define DTSaddress(dir_table_slot, address64)\
0114 {\
0115     (dir_table_slot)->addr1 = ((u64)address64) >> 32;\
0116     (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\
0117 }
0118
0119 #define addressDTS(dts)\
0120     ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) )
0121
0122 /* compute number of slots for entry */
0123 #define NDTLEAF_LEGACY(klen)    (DIV_ROUND_UP((2 + (klen)), 15))
0124 #define NDTLEAF NDTINTERNAL
0125
0126
0127 /*
0128  *  directory root page (in-line in on-disk inode):
0129  *
0130  * cf. dtpage_t below.
0131  */
0132 typedef union {
0133     struct {
0134         struct dasd DASD; /* 16: DASD limit/usage info */
0135
0136         u8 flag;    /* 1: */
0137         u8 nextindex;   /* 1: next free entry in stbl */
0138         s8 freecnt; /* 1: free count */
0139         s8 freelist;    /* 1: freelist header */
0140
0141         __le32 idotdot; /* 4: parent inode number */
0142
0143         s8 stbl[8]; /* 8: sorted entry index table */
0144     } header;       /* (32) */
0145
0146     struct dtslot slot[9];
0147 } dtroot_t;
0148
0149 #define PARENT(IP) \
0150     (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot))
0151
0152 #define DTROOTMAXSLOT   9
0153
0154 #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0)
0155
0156
0157 /*
0158  *  directory regular page:
0159  *
0160  *  entry slot array of 32 byte slot
0161  *
0162  * sorted entry slot index table (stbl):
0163  * contiguous slots at slot specified by stblindex,
0164  * 1-byte per entry
0165  *   512 byte block:  16 entry tbl (1 slot)
0166  *  1024 byte block:  32 entry tbl (1 slot)
0167  *  2048 byte block:  64 entry tbl (2 slot)
0168  *  4096 byte block: 128 entry tbl (4 slot)
0169  *
0170  * data area:
0171  *   512 byte block:  16 - 2 =  14 slot
0172  *  1024 byte block:  32 - 2 =  30 slot
0173  *  2048 byte block:  64 - 3 =  61 slot
0174  *  4096 byte block: 128 - 5 = 123 slot
0175  *
0176  * N.B. index is 0-based; index fields refer to slot index
0177  * except nextindex which refers to entry index in stbl;
0178  * end of entry stot list or freelist is marked with -1.
0179  */
0180 typedef union {
0181     struct {
0182         __le64 next;    /* 8: next sibling */
0183         __le64 prev;    /* 8: previous sibling */
0184
0185         u8 flag;    /* 1: */
0186         u8 nextindex;   /* 1: next entry index in stbl */
0187         s8 freecnt; /* 1: */
0188         s8 freelist;    /* 1: slot index of head of freelist */
0189
0190         u8 maxslot; /* 1: number of slots in page slot[] */
0191         u8 stblindex;   /* 1: slot index of start of stbl */
0192         u8 rsrvd[2];    /* 2: */
0193
0194         pxd_t self; /* 8: self pxd */
0195     } header;       /* (32) */
0196
0197     struct dtslot slot[128];
0198 } dtpage_t;
0199
0200 #define DTPAGEMAXSLOT        128
0201
0202 #define DT8THPGNODEBYTES     512
0203 #define DT8THPGNODETSLOTS      1
0204 #define DT8THPGNODESLOTS      16
0205
0206 #define DTQTRPGNODEBYTES    1024
0207 #define DTQTRPGNODETSLOTS      1
0208 #define DTQTRPGNODESLOTS      32
0209
0210 #define DTHALFPGNODEBYTES   2048
0211 #define DTHALFPGNODETSLOTS     2
0212 #define DTHALFPGNODESLOTS     64
0213
0214 #define DTFULLPGNODEBYTES   4096
0215 #define DTFULLPGNODETSLOTS     4
0216 #define DTFULLPGNODESLOTS    128
0217
0218 #define DTENTRYSTART    1
0219
0220 /* get sorted entry table of the page */
0221 #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\
0222     ((dtroot_t *)(p))->header.stbl : \
0223     (s8 *)&(p)->slot[(p)->header.stblindex] )
0224
0225 /*
0226  * Flags for dtSearch
0227  */
0228 #define JFS_CREATE 1
0229 #define JFS_LOOKUP 2
0230 #define JFS_REMOVE 3
0231 #define JFS_RENAME 4
0232
0233 /*
0234  * Maximum file offset for directories.
0235  */
0236 #define DIREND  INT_MAX
0237
0238 /*
0239  *  external declarations
0240  */
0241 extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
0242
0243 extern int dtSearch(struct inode *ip, struct component_name * key,
0244             ino_t * data, struct btstack * btstack, int flag);
0245
0246 extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
0247             ino_t * ino, struct btstack * btstack);
0248
0249 extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
0250             ino_t * data, int flag);
0251
0252 extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
0253             ino_t * orig_ino, ino_t new_ino, int flag);
0254
0255 extern int jfs_readdir(struct file *file, struct dir_context *ctx);
0256 #endif              /* !_H_JFS_DTREE */