| 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 */ |