LXR linux/fs/jfs/jfs

   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
  14typedef 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 */
  34struct 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 */
  52struct 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 */
  72struct 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
  98struct 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 */
 132typedef 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 */
 180typedef 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 */
 241extern void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot);
 242
 243extern int dtSearch(struct inode *ip, struct component_name * key,
 244                    ino_t * data, struct btstack * btstack, int flag);
 245
 246extern int dtInsert(tid_t tid, struct inode *ip, struct component_name * key,
 247                    ino_t * ino, struct btstack * btstack);
 248
 249extern int dtDelete(tid_t tid, struct inode *ip, struct component_name * key,
 250                    ino_t * data, int flag);
 251
 252extern int dtModify(tid_t tid, struct inode *ip, struct component_name * key,
 253                    ino_t * orig_ino, ino_t new_ino, int flag);
 254
 255extern int jfs_readdir(struct file *file, struct dir_context *ctx);
 256#endif                          /* !_H_JFS_DTREE */
 257