fs/jfs/jfs_dtree.h

   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         __le16 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         __le16 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         __le32 inumber;         /* 4: 4-byte aligned */
  87         s8 next;                /* 1: */
  88         u8 namlen;              /* 1: */
  89         __le16 name[11];        /* 22: 2-byte aligned */
  90         __le32 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         __le32 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                 __le32 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                 __le64 next;    /* 8: next sibling */
 196                 __le64 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 */