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