1 /* SPDX-License-Identifier: GPL-2.0-or-later */ 2 /* 3 * Copyright (C) International Business Machines Corp., 2000-2002 4 */ 5 #ifndef _H_JFS_DTREE 6 #define _H_JFS_DTREE 7 8 /* 9 * jfs_dtree.h: directory B+-tree manager 10 */ 11 12 #include "jfs_btree.h" 13 14 typedef union { 15 struct { 16 tid_t tid; 17 struct inode *ip; 18 u32 ino; 19 } leaf; 20 pxd_t xd; 21 } ddata_t; 22 23 24 /* 25 * entry segment/slot 26 * 27 * an entry consists of type dependent head/only segment/slot and 28 * additional segments/slots linked vi next field; 29 * N.B. last/only segment of entry is terminated by next = -1; 30 */ 31 /* 32 * directory page slot 33 */ 34 struct dtslot { 35 s8 next; /* 1: */ 36 s8 cnt; /* 1: */ 37 __le16 name[15]; /* 30: */ 38 }; /* (32) */ 39 40 41 #define DATASLOTSIZE 16 42 #define L2DATASLOTSIZE 4 43 #define DTSLOTSIZE 32 44 #define L2DTSLOTSIZE 5 45 #define DTSLOTHDRSIZE 2 46 #define DTSLOTDATASIZE 30 47 #define DTSLOTDATALEN 15 48 49 /* 50 * internal node entry head/only segment 51 */ 52 struct idtentry { 53 pxd_t xd; /* 8: child extent descriptor */ 54 55 s8 next; /* 1: */ 56 u8 namlen; /* 1: */ 57 __le16 name[11]; /* 22: 2-byte aligned */ 58 }; /* (32) */ 59 60 #define DTIHDRSIZE 10 61 #define DTIHDRDATALEN 11 62 63 /* compute number of slots for entry */ 64 #define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15)) 65 66 67 /* 68 * leaf node entry head/only segment 69 * 70 * For legacy filesystems, name contains 13 wchars -- no index field 71 */ 72 struct ldtentry { 73 __le32 inumber; /* 4: 4-byte aligned */ 74 s8 next; /* 1: */ 75 u8 namlen; /* 1: */ 76 __le16 name[11]; /* 22: 2-byte aligned */ 77 __le32 index; /* 4: index into dir_table */ 78 }; /* (32) */ 79 80 #define DTLHDRSIZE 6 81 #define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */ 82 #define DTLHDRDATALEN 11 83 84 /* 85 * dir_table used for directory traversal during readdir 86 */ 87 88 /* 89 * Keep persistent index for directory entries 90 */ 91 #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX) 92 93 /* 94 * Maximum entry in inline directory table 95 */ 96 #define MAX_INLINE_DIRTABLE_ENTRY 13 97 98 struct dir_table_slot { 99 u8 rsrvd; /* 1: */ 100 u8 flag; /* 1: 0 if free */ 101 u8 slot; /* 1: slot within leaf page of entry */ 102 u8 addr1; /* 1: upper 8 bits of leaf page address */ 103 __le32 addr2; /* 4: lower 32 bits of leaf page address -OR- 104 index of next entry when this entry was deleted */ 105 }; /* (8) */ 106 107 /* 108 * flag values 109 */ 110 #define DIR_INDEX_VALID 1 111 #define DIR_INDEX_FREE 0 112 113 #define DTSaddress(dir_table_slot, address64)\ 114 {\ 115 (dir_table_slot)->addr1 = ((u64)address64) >> 32;\ 116 (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\ 117 } 118 119 #define addressDTS(dts)\ 120 ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) ) 121 122 /* compute number of slots for entry */ 123 #define NDTLEAF_LEGACY(klen) (DIV_ROUND_UP((2 + (klen)), 15)) 124 #define NDTLEAF NDTINTERNAL 125 126 127 /* 128 * directory root page (in-line in on-disk inode): 129 * 130 * cf. dtpage_t below. 131 */ 132 typedef union { 133 struct { 134 struct dasd DASD; /* 16: DASD limit/usage info */ 135 136 u8 flag; /* 1: */ 137 u8 nextindex; /* 1: next free entry in stbl */ 138 s8 freecnt; /* 1: free count */ 139 s8 freelist; /* 1: freelist header */ 140 141 __le32 idotdot; /* 4: parent inode number */ 142 143 s8 stbl[8]; /* 8: sorted entry index table */ 144 } header; /* (32) */ 145 146 struct dtslot slot[9]; 147 } dtroot_t; 148 149 #define PARENT(IP) \ 150 (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot)) 151 152 #define DTROOTMAXSLOT 9 153 154 #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0) 155 156 157 /* 158 * directory regular page: 159 * 160 * entry slot array of 32 byte slot 161 * 162 * sorted entry slot index table (stbl): 163 * contiguous slots at slot specified by stblindex, 164 * 1-byte per entry 165 * 512 byte block: 16 entry tbl (1 slot) 166 * 1024 byte block: 32 entry tbl (1 slot) 167 * 2048 byte block: 64 entry tbl (2 slot) 168 * 4096 byte block: 128 entry tbl (4 slot) 169 * 170 * data area: 171 * 512 byte block: 16 - 2 = 14 slot 172 * 1024 byte block: 32 - 2 = 30 slot 173 * 2048 byte block: 64 - 3 = 61 slot 174 * 4096 byte block: 128 - 5 = 123 slot 175 * 176 * N.B. index is 0-based; index fields refer to slot index 177 * except nextindex which refers to entry index in stbl; 178 * end of entry stot list or freelist is marked with -1. 179 */ 180 typedef union { 181 struct { 182 __le64 next; /* 8: next sibling */ 183 __le64 prev; /* 8: previous sibling */ 184 185 u8 flag; /* 1: */ 186 u8 nextindex; /* 1: next entry index in stbl */ 187 s8 freecnt; /* 1: */ 188 s8 freelist; /* 1: slot index of head of freelist */ 189 190 u8 maxslot; /* 1: number of slots in page slot[] */ 191 u8 stblindex; /* 1: slot index of start of stbl */ 192 u8 rsrvd[2]; /* 2: */ 193 194 pxd_t self; /* 8: self pxd */ 195 } header; /* (32) */ 196 197 struct dtslot slot[128]; 198 } dtpage_t; 199 200 #define DTPAGEMAXSLOT 128 201 202 #define DT8THPGNODEBYTES 512 203 #define DT8THPGNODETSLOTS 1 204 #define DT8THPGNODESLOTS 16 205 206 #define DTQTRPGNODEBYTES 1024 207 #define DTQTRPGNODETSLOTS 1 208 #define DTQTRPGNODESLOTS 32 209 210 #define DTHALFPGNODEBYTES 2048 211 #define DTHALFPGNODETSLOTS 2 212 #define DTHALFPGNODESLOTS 64 213 214 #define DTFULLPGNODEBYTES 4096 215 #define DTFULLPGNODETSLOTS 4 216 #define DTFULLPGNODESLOTS 128 217 218 #define DTENTRYSTART 1 219 220 /* get sorted entry table of the page */ 221 #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\ 222 ((dtroot_t *)(p))->header.stbl : \ 223 (s8 *)&(p)->slot[(p)->header.stblindex] ) 224 225 /* 226 * Flags for dtSearch 227 */ 228 #define JFS_CREATE 1 229 #define JFS_LOOKUP 2 230 #define JFS_REMOVE 3 231 #define JFS_RENAME 4 232 233 /* 234 * Maximum file offset for directories. 235 */ 236 #define DIREND INT_MAX 237 238 /* 239 * external declarations 240 */ 241 extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot); 242 243 extern int dtSearch(struct inode *ip, struct component_name * key, 244 ino_t * data, struct btstack * btstack, int flag); 245 246 extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key, 247 ino_t * ino, struct btstack * btstack); 248 249 extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key, 250 ino_t * data, int flag); 251 252 extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key, 253 ino_t * orig_ino, ino_t new_ino, int flag); 254 255 extern int jfs_readdir(struct file *file, struct dir_context *ctx); 256 #endif /* !_H_JFS_DTREE */ 257