1*1a59d1b8SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-or-later */ 21da177e4SLinus Torvalds /* 363f83c9fSDave Kleikamp * Copyright (C) International Business Machines Corp., 2000-2002 41da177e4SLinus Torvalds */ 51da177e4SLinus Torvalds #ifndef _H_JFS_DTREE 61da177e4SLinus Torvalds #define _H_JFS_DTREE 71da177e4SLinus Torvalds 81da177e4SLinus Torvalds /* 91da177e4SLinus Torvalds * jfs_dtree.h: directory B+-tree manager 101da177e4SLinus Torvalds */ 111da177e4SLinus Torvalds 121da177e4SLinus Torvalds #include "jfs_btree.h" 131da177e4SLinus Torvalds 141da177e4SLinus Torvalds typedef union { 151da177e4SLinus Torvalds struct { 161da177e4SLinus Torvalds tid_t tid; 171da177e4SLinus Torvalds struct inode *ip; 181da177e4SLinus Torvalds u32 ino; 191da177e4SLinus Torvalds } leaf; 201da177e4SLinus Torvalds pxd_t xd; 211da177e4SLinus Torvalds } ddata_t; 221da177e4SLinus Torvalds 231da177e4SLinus Torvalds 241da177e4SLinus Torvalds /* 251da177e4SLinus Torvalds * entry segment/slot 261da177e4SLinus Torvalds * 271da177e4SLinus Torvalds * an entry consists of type dependent head/only segment/slot and 281da177e4SLinus Torvalds * additional segments/slots linked vi next field; 291da177e4SLinus Torvalds * N.B. last/only segment of entry is terminated by next = -1; 301da177e4SLinus Torvalds */ 311da177e4SLinus Torvalds /* 321da177e4SLinus Torvalds * directory page slot 331da177e4SLinus Torvalds */ 341da177e4SLinus Torvalds struct dtslot { 351da177e4SLinus Torvalds s8 next; /* 1: */ 361da177e4SLinus Torvalds s8 cnt; /* 1: */ 371da177e4SLinus Torvalds __le16 name[15]; /* 30: */ 381da177e4SLinus Torvalds }; /* (32) */ 391da177e4SLinus Torvalds 401da177e4SLinus Torvalds 411da177e4SLinus Torvalds #define DATASLOTSIZE 16 421da177e4SLinus Torvalds #define L2DATASLOTSIZE 4 431da177e4SLinus Torvalds #define DTSLOTSIZE 32 441da177e4SLinus Torvalds #define L2DTSLOTSIZE 5 451da177e4SLinus Torvalds #define DTSLOTHDRSIZE 2 461da177e4SLinus Torvalds #define DTSLOTDATASIZE 30 471da177e4SLinus Torvalds #define DTSLOTDATALEN 15 481da177e4SLinus Torvalds 491da177e4SLinus Torvalds /* 501da177e4SLinus Torvalds * internal node entry head/only segment 511da177e4SLinus Torvalds */ 521da177e4SLinus Torvalds struct idtentry { 531da177e4SLinus Torvalds pxd_t xd; /* 8: child extent descriptor */ 541da177e4SLinus Torvalds 551da177e4SLinus Torvalds s8 next; /* 1: */ 561da177e4SLinus Torvalds u8 namlen; /* 1: */ 571da177e4SLinus Torvalds __le16 name[11]; /* 22: 2-byte aligned */ 581da177e4SLinus Torvalds }; /* (32) */ 591da177e4SLinus Torvalds 601da177e4SLinus Torvalds #define DTIHDRSIZE 10 611da177e4SLinus Torvalds #define DTIHDRDATALEN 11 621da177e4SLinus Torvalds 631da177e4SLinus Torvalds /* compute number of slots for entry */ 64a7fe0ba7SShaun Zinck #define NDTINTERNAL(klen) (DIV_ROUND_UP((4 + (klen)), 15)) 651da177e4SLinus Torvalds 661da177e4SLinus Torvalds 671da177e4SLinus Torvalds /* 681da177e4SLinus Torvalds * leaf node entry head/only segment 691da177e4SLinus Torvalds * 701da177e4SLinus Torvalds * For legacy filesystems, name contains 13 wchars -- no index field 711da177e4SLinus Torvalds */ 721da177e4SLinus Torvalds struct ldtentry { 731da177e4SLinus Torvalds __le32 inumber; /* 4: 4-byte aligned */ 741da177e4SLinus Torvalds s8 next; /* 1: */ 751da177e4SLinus Torvalds u8 namlen; /* 1: */ 761da177e4SLinus Torvalds __le16 name[11]; /* 22: 2-byte aligned */ 771da177e4SLinus Torvalds __le32 index; /* 4: index into dir_table */ 781da177e4SLinus Torvalds }; /* (32) */ 791da177e4SLinus Torvalds 801da177e4SLinus Torvalds #define DTLHDRSIZE 6 811da177e4SLinus Torvalds #define DTLHDRDATALEN_LEGACY 13 /* Old (OS/2) format */ 821da177e4SLinus Torvalds #define DTLHDRDATALEN 11 831da177e4SLinus Torvalds 841da177e4SLinus Torvalds /* 851da177e4SLinus Torvalds * dir_table used for directory traversal during readdir 861da177e4SLinus Torvalds */ 871da177e4SLinus Torvalds 881da177e4SLinus Torvalds /* 891da177e4SLinus Torvalds * Keep persistent index for directory entries 901da177e4SLinus Torvalds */ 911da177e4SLinus Torvalds #define DO_INDEX(INODE) (JFS_SBI((INODE)->i_sb)->mntflag & JFS_DIR_INDEX) 921da177e4SLinus Torvalds 931da177e4SLinus Torvalds /* 941da177e4SLinus Torvalds * Maximum entry in inline directory table 951da177e4SLinus Torvalds */ 961da177e4SLinus Torvalds #define MAX_INLINE_DIRTABLE_ENTRY 13 971da177e4SLinus Torvalds 981da177e4SLinus Torvalds struct dir_table_slot { 991da177e4SLinus Torvalds u8 rsrvd; /* 1: */ 1001da177e4SLinus Torvalds u8 flag; /* 1: 0 if free */ 1011da177e4SLinus Torvalds u8 slot; /* 1: slot within leaf page of entry */ 1021da177e4SLinus Torvalds u8 addr1; /* 1: upper 8 bits of leaf page address */ 1031da177e4SLinus Torvalds __le32 addr2; /* 4: lower 32 bits of leaf page address -OR- 1041da177e4SLinus Torvalds index of next entry when this entry was deleted */ 1051da177e4SLinus Torvalds }; /* (8) */ 1061da177e4SLinus Torvalds 1071da177e4SLinus Torvalds /* 1081da177e4SLinus Torvalds * flag values 1091da177e4SLinus Torvalds */ 1101da177e4SLinus Torvalds #define DIR_INDEX_VALID 1 1111da177e4SLinus Torvalds #define DIR_INDEX_FREE 0 1121da177e4SLinus Torvalds 1131da177e4SLinus Torvalds #define DTSaddress(dir_table_slot, address64)\ 1141da177e4SLinus Torvalds {\ 1151da177e4SLinus Torvalds (dir_table_slot)->addr1 = ((u64)address64) >> 32;\ 1161da177e4SLinus Torvalds (dir_table_slot)->addr2 = __cpu_to_le32((address64) & 0xffffffff);\ 1171da177e4SLinus Torvalds } 1181da177e4SLinus Torvalds 1191da177e4SLinus Torvalds #define addressDTS(dts)\ 1201da177e4SLinus Torvalds ( ((s64)((dts)->addr1)) << 32 | __le32_to_cpu((dts)->addr2) ) 1211da177e4SLinus Torvalds 1221da177e4SLinus Torvalds /* compute number of slots for entry */ 123a7fe0ba7SShaun Zinck #define NDTLEAF_LEGACY(klen) (DIV_ROUND_UP((2 + (klen)), 15)) 1241da177e4SLinus Torvalds #define NDTLEAF NDTINTERNAL 1251da177e4SLinus Torvalds 1261da177e4SLinus Torvalds 1271da177e4SLinus Torvalds /* 1281da177e4SLinus Torvalds * directory root page (in-line in on-disk inode): 1291da177e4SLinus Torvalds * 1301da177e4SLinus Torvalds * cf. dtpage_t below. 1311da177e4SLinus Torvalds */ 1321da177e4SLinus Torvalds typedef union { 1331da177e4SLinus Torvalds struct { 1341da177e4SLinus Torvalds struct dasd DASD; /* 16: DASD limit/usage info */ 1351da177e4SLinus Torvalds 1361da177e4SLinus Torvalds u8 flag; /* 1: */ 1371da177e4SLinus Torvalds u8 nextindex; /* 1: next free entry in stbl */ 1381da177e4SLinus Torvalds s8 freecnt; /* 1: free count */ 1391da177e4SLinus Torvalds s8 freelist; /* 1: freelist header */ 1401da177e4SLinus Torvalds 1411da177e4SLinus Torvalds __le32 idotdot; /* 4: parent inode number */ 1421da177e4SLinus Torvalds 1431da177e4SLinus Torvalds s8 stbl[8]; /* 8: sorted entry index table */ 1441da177e4SLinus Torvalds } header; /* (32) */ 1451da177e4SLinus Torvalds 1461da177e4SLinus Torvalds struct dtslot slot[9]; 1471da177e4SLinus Torvalds } dtroot_t; 1481da177e4SLinus Torvalds 1491da177e4SLinus Torvalds #define PARENT(IP) \ 1501da177e4SLinus Torvalds (le32_to_cpu(JFS_IP(IP)->i_dtroot.header.idotdot)) 1511da177e4SLinus Torvalds 1521da177e4SLinus Torvalds #define DTROOTMAXSLOT 9 1531da177e4SLinus Torvalds 1541da177e4SLinus Torvalds #define dtEmpty(IP) (JFS_IP(IP)->i_dtroot.header.nextindex == 0) 1551da177e4SLinus Torvalds 1561da177e4SLinus Torvalds 1571da177e4SLinus Torvalds /* 1581da177e4SLinus Torvalds * directory regular page: 1591da177e4SLinus Torvalds * 1601da177e4SLinus Torvalds * entry slot array of 32 byte slot 1611da177e4SLinus Torvalds * 1621da177e4SLinus Torvalds * sorted entry slot index table (stbl): 1631da177e4SLinus Torvalds * contiguous slots at slot specified by stblindex, 1641da177e4SLinus Torvalds * 1-byte per entry 1651da177e4SLinus Torvalds * 512 byte block: 16 entry tbl (1 slot) 1661da177e4SLinus Torvalds * 1024 byte block: 32 entry tbl (1 slot) 1671da177e4SLinus Torvalds * 2048 byte block: 64 entry tbl (2 slot) 1681da177e4SLinus Torvalds * 4096 byte block: 128 entry tbl (4 slot) 1691da177e4SLinus Torvalds * 1701da177e4SLinus Torvalds * data area: 1711da177e4SLinus Torvalds * 512 byte block: 16 - 2 = 14 slot 1721da177e4SLinus Torvalds * 1024 byte block: 32 - 2 = 30 slot 1731da177e4SLinus Torvalds * 2048 byte block: 64 - 3 = 61 slot 1741da177e4SLinus Torvalds * 4096 byte block: 128 - 5 = 123 slot 1751da177e4SLinus Torvalds * 1761da177e4SLinus Torvalds * N.B. index is 0-based; index fields refer to slot index 1771da177e4SLinus Torvalds * except nextindex which refers to entry index in stbl; 1781da177e4SLinus Torvalds * end of entry stot list or freelist is marked with -1. 1791da177e4SLinus Torvalds */ 1801da177e4SLinus Torvalds typedef union { 1811da177e4SLinus Torvalds struct { 1821da177e4SLinus Torvalds __le64 next; /* 8: next sibling */ 1831da177e4SLinus Torvalds __le64 prev; /* 8: previous sibling */ 1841da177e4SLinus Torvalds 1851da177e4SLinus Torvalds u8 flag; /* 1: */ 1861da177e4SLinus Torvalds u8 nextindex; /* 1: next entry index in stbl */ 1871da177e4SLinus Torvalds s8 freecnt; /* 1: */ 1881da177e4SLinus Torvalds s8 freelist; /* 1: slot index of head of freelist */ 1891da177e4SLinus Torvalds 1901da177e4SLinus Torvalds u8 maxslot; /* 1: number of slots in page slot[] */ 1911da177e4SLinus Torvalds u8 stblindex; /* 1: slot index of start of stbl */ 1921da177e4SLinus Torvalds u8 rsrvd[2]; /* 2: */ 1931da177e4SLinus Torvalds 1941da177e4SLinus Torvalds pxd_t self; /* 8: self pxd */ 1951da177e4SLinus Torvalds } header; /* (32) */ 1961da177e4SLinus Torvalds 1971da177e4SLinus Torvalds struct dtslot slot[128]; 1981da177e4SLinus Torvalds } dtpage_t; 1991da177e4SLinus Torvalds 2001da177e4SLinus Torvalds #define DTPAGEMAXSLOT 128 2011da177e4SLinus Torvalds 2021da177e4SLinus Torvalds #define DT8THPGNODEBYTES 512 2031da177e4SLinus Torvalds #define DT8THPGNODETSLOTS 1 2041da177e4SLinus Torvalds #define DT8THPGNODESLOTS 16 2051da177e4SLinus Torvalds 2061da177e4SLinus Torvalds #define DTQTRPGNODEBYTES 1024 2071da177e4SLinus Torvalds #define DTQTRPGNODETSLOTS 1 2081da177e4SLinus Torvalds #define DTQTRPGNODESLOTS 32 2091da177e4SLinus Torvalds 2101da177e4SLinus Torvalds #define DTHALFPGNODEBYTES 2048 2111da177e4SLinus Torvalds #define DTHALFPGNODETSLOTS 2 2121da177e4SLinus Torvalds #define DTHALFPGNODESLOTS 64 2131da177e4SLinus Torvalds 2141da177e4SLinus Torvalds #define DTFULLPGNODEBYTES 4096 2151da177e4SLinus Torvalds #define DTFULLPGNODETSLOTS 4 2161da177e4SLinus Torvalds #define DTFULLPGNODESLOTS 128 2171da177e4SLinus Torvalds 2181da177e4SLinus Torvalds #define DTENTRYSTART 1 2191da177e4SLinus Torvalds 2201da177e4SLinus Torvalds /* get sorted entry table of the page */ 2211da177e4SLinus Torvalds #define DT_GETSTBL(p) ( ((p)->header.flag & BT_ROOT) ?\ 2221da177e4SLinus Torvalds ((dtroot_t *)(p))->header.stbl : \ 2231da177e4SLinus Torvalds (s8 *)&(p)->slot[(p)->header.stblindex] ) 2241da177e4SLinus Torvalds 2251da177e4SLinus Torvalds /* 2261da177e4SLinus Torvalds * Flags for dtSearch 2271da177e4SLinus Torvalds */ 2281da177e4SLinus Torvalds #define JFS_CREATE 1 2291da177e4SLinus Torvalds #define JFS_LOOKUP 2 2301da177e4SLinus Torvalds #define JFS_REMOVE 3 2311da177e4SLinus Torvalds #define JFS_RENAME 4 2321da177e4SLinus Torvalds 2331da177e4SLinus Torvalds /* 2341da177e4SLinus Torvalds * Maximum file offset for directories. 2351da177e4SLinus Torvalds */ 2361da177e4SLinus Torvalds #define DIREND INT_MAX 2371da177e4SLinus Torvalds 2381da177e4SLinus Torvalds /* 2391da177e4SLinus Torvalds * external declarations 2401da177e4SLinus Torvalds */ 2411da177e4SLinus Torvalds extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot); 2421da177e4SLinus Torvalds 2431da177e4SLinus Torvalds extern int dtSearch(struct inode *ip, struct component_name * key, 2441da177e4SLinus Torvalds ino_t * data, struct btstack * btstack, int flag); 2451da177e4SLinus Torvalds 2461da177e4SLinus Torvalds extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key, 2471da177e4SLinus Torvalds ino_t * ino, struct btstack * btstack); 2481da177e4SLinus Torvalds 2491da177e4SLinus Torvalds extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key, 2501da177e4SLinus Torvalds ino_t * data, int flag); 2511da177e4SLinus Torvalds 2521da177e4SLinus Torvalds extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key, 2531da177e4SLinus Torvalds ino_t * orig_ino, ino_t new_ino, int flag); 2541da177e4SLinus Torvalds 255070a0ebfSAl Viro extern int jfs_readdir(struct file *file, struct dir_context *ctx); 2561da177e4SLinus Torvalds #endif /* !_H_JFS_DTREE */ 257