fs/jfs/jfs_dtree.h

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