xfs/libxfs/xfs_da_btree.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /*
0003  * Copyright (c) 2000,2002,2005 Silicon Graphics, Inc.
0004  * Copyright (c) 2013 Red Hat, Inc.
0005  * All Rights Reserved.
0006  */
0007 #ifndef __XFS_DA_BTREE_H__
0008 #define __XFS_DA_BTREE_H__
0009
0010 struct xfs_inode;
0011 struct xfs_trans;
0012
0013 /*
0014  * Directory/attribute geometry information. There will be one of these for each
0015  * data fork type, and it will be passed around via the xfs_da_args. Global
0016  * structures will be attached to the xfs_mount.
0017  */
0018 struct xfs_da_geometry {
0019     unsigned int    blksize;    /* da block size in bytes */
0020     unsigned int    fsbcount;   /* da block size in filesystem blocks */
0021     uint8_t     fsblog;     /* log2 of _filesystem_ block size */
0022     uint8_t     blklog;     /* log2 of da block size */
0023     unsigned int    node_hdr_size;  /* danode header size in bytes */
0024     unsigned int    node_ents;  /* # of entries in a danode */
0025     unsigned int    magicpct;   /* 37% of block size in bytes */
0026     xfs_dablk_t datablk;    /* blockno of dir data v2 */
0027     unsigned int    leaf_hdr_size;  /* dir2 leaf header size */
0028     unsigned int    leaf_max_ents;  /* # of entries in dir2 leaf */
0029     xfs_dablk_t leafblk;    /* blockno of leaf data v2 */
0030     unsigned int    free_hdr_size;  /* dir2 free header size */
0031     unsigned int    free_max_bests; /* # of bests entries in dir2 free */
0032     xfs_dablk_t freeblk;    /* blockno of free data v2 */
0033     xfs_extnum_t    max_extents;    /* Max. extents in corresponding fork */
0034
0035     xfs_dir2_data_aoff_t data_first_offset;
0036     size_t      data_entry_offset;
0037 };
0038
0039 /*========================================================================
0040  * Btree searching and modification structure definitions.
0041  *========================================================================*/
0042
0043 /*
0044  * Search comparison results
0045  */
0046 enum xfs_dacmp {
0047     XFS_CMP_DIFFERENT,  /* names are completely different */
0048     XFS_CMP_EXACT,      /* names are exactly the same */
0049     XFS_CMP_CASE        /* names are same but differ in case */
0050 };
0051
0052 /*
0053  * Structure to ease passing around component names.
0054  */
0055 typedef struct xfs_da_args {
0056     struct xfs_da_geometry *geo;    /* da block geometry */
0057     const uint8_t       *name;      /* string (maybe not NULL terminated) */
0058     int     namelen;    /* length of string (maybe no NULL) */
0059     uint8_t     filetype;   /* filetype of inode for directories */
0060     void        *value;     /* set of bytes (maybe contain NULLs) */
0061     int     valuelen;   /* length of value */
0062     unsigned int    attr_filter;    /* XFS_ATTR_{ROOT,SECURE,INCOMPLETE} */
0063     unsigned int    attr_flags; /* XATTR_{CREATE,REPLACE} */
0064     xfs_dahash_t    hashval;    /* hash value of name */
0065     xfs_ino_t   inumber;    /* input/output inode number */
0066     struct xfs_inode *dp;       /* directory inode to manipulate */
0067     struct xfs_trans *trans;    /* current trans (changes over time) */
0068     xfs_extlen_t    total;      /* total blocks needed, for 1st bmap */
0069     int     whichfork;  /* data or attribute fork */
0070     xfs_dablk_t blkno;      /* blkno of attr leaf of interest */
0071     int     index;      /* index of attr of interest in blk */
0072     xfs_dablk_t rmtblkno;   /* remote attr value starting blkno */
0073     int     rmtblkcnt;  /* remote attr value block count */
0074     int     rmtvaluelen;    /* remote attr value length in bytes */
0075     xfs_dablk_t blkno2;     /* blkno of 2nd attr leaf of interest */
0076     int     index2;     /* index of 2nd attr in blk */
0077     xfs_dablk_t rmtblkno2;  /* remote attr value starting blkno */
0078     int     rmtblkcnt2; /* remote attr value block count */
0079     int     rmtvaluelen2;   /* remote attr value length in bytes */
0080     uint32_t    op_flags;   /* operation flags */
0081     enum xfs_dacmp  cmpresult;  /* name compare result for lookups */
0082 } xfs_da_args_t;
0083
0084 /*
0085  * Operation flags:
0086  */
0087 #define XFS_DA_OP_JUSTCHECK (1u << 0) /* check for ok with no space */
0088 #define XFS_DA_OP_REPLACE   (1u << 1) /* this is an atomic replace op */
0089 #define XFS_DA_OP_ADDNAME   (1u << 2) /* this is an add operation */
0090 #define XFS_DA_OP_OKNOENT   (1u << 3) /* lookup op, ENOENT ok, else die */
0091 #define XFS_DA_OP_CILOOKUP  (1u << 4) /* lookup returns CI name if found */
0092 #define XFS_DA_OP_NOTIME    (1u << 5) /* don't update inode timestamps */
0093 #define XFS_DA_OP_REMOVE    (1u << 6) /* this is a remove operation */
0094 #define XFS_DA_OP_RECOVERY  (1u << 7) /* Log recovery operation */
0095 #define XFS_DA_OP_LOGGED    (1u << 8) /* Use intent items to track op */
0096
0097 #define XFS_DA_OP_FLAGS \
0098     { XFS_DA_OP_JUSTCHECK,  "JUSTCHECK" }, \
0099     { XFS_DA_OP_REPLACE,    "REPLACE" }, \
0100     { XFS_DA_OP_ADDNAME,    "ADDNAME" }, \
0101     { XFS_DA_OP_OKNOENT,    "OKNOENT" }, \
0102     { XFS_DA_OP_CILOOKUP,   "CILOOKUP" }, \
0103     { XFS_DA_OP_NOTIME, "NOTIME" }, \
0104     { XFS_DA_OP_REMOVE, "REMOVE" }, \
0105     { XFS_DA_OP_RECOVERY,   "RECOVERY" }, \
0106     { XFS_DA_OP_LOGGED, "LOGGED" }
0107
0108 /*
0109  * Storage for holding state during Btree searches and split/join ops.
0110  *
0111  * Only need space for 5 intermediate nodes.  With a minimum of 62-way
0112  * fanout to the Btree, we can support over 900 million directory blocks,
0113  * which is slightly more than enough.
0114  */
0115 typedef struct xfs_da_state_blk {
0116     struct xfs_buf  *bp;        /* buffer containing block */
0117     xfs_dablk_t blkno;      /* filesystem blkno of buffer */
0118     xfs_daddr_t disk_blkno; /* on-disk blkno (in BBs) of buffer */
0119     int     index;      /* relevant index into block */
0120     xfs_dahash_t    hashval;    /* last hash value in block */
0121     int     magic;      /* blk's magic number, ie: blk type */
0122 } xfs_da_state_blk_t;
0123
0124 typedef struct xfs_da_state_path {
0125     int         active;     /* number of active levels */
0126     xfs_da_state_blk_t  blk[XFS_DA_NODE_MAXDEPTH];
0127 } xfs_da_state_path_t;
0128
0129 typedef struct xfs_da_state {
0130     xfs_da_args_t       *args;      /* filename arguments */
0131     struct xfs_mount    *mp;        /* filesystem mount point */
0132     xfs_da_state_path_t path;       /* search/split paths */
0133     xfs_da_state_path_t altpath;    /* alternate path for join */
0134     unsigned char       inleaf;     /* insert into 1->lf, 0->splf */
0135     unsigned char       extravalid; /* T/F: extrablk is in use */
0136     unsigned char       extraafter; /* T/F: extrablk is after new */
0137     xfs_da_state_blk_t  extrablk;   /* for double-splits on leaves */
0138                         /* for dirv2 extrablk is data */
0139 } xfs_da_state_t;
0140
0141 /*
0142  * In-core version of the node header to abstract the differences in the v2 and
0143  * v3 disk format of the headers. Callers need to convert to/from disk format as
0144  * appropriate.
0145  */
0146 struct xfs_da3_icnode_hdr {
0147     uint32_t        forw;
0148     uint32_t        back;
0149     uint16_t        magic;
0150     uint16_t        count;
0151     uint16_t        level;
0152
0153     /*
0154      * Pointer to the on-disk format entries, which are behind the
0155      * variable size (v4 vs v5) header in the on-disk block.
0156      */
0157     struct xfs_da_node_entry *btree;
0158 };
0159
0160 /*
0161  * Utility macros to aid in logging changed structure fields.
0162  */
0163 #define XFS_DA_LOGOFF(BASE, ADDR)   ((char *)(ADDR) - (char *)(BASE))
0164 #define XFS_DA_LOGRANGE(BASE, ADDR, SIZE)   \
0165         (uint)(XFS_DA_LOGOFF(BASE, ADDR)), \
0166         (uint)(XFS_DA_LOGOFF(BASE, ADDR)+(SIZE)-1)
0167
0168 /*========================================================================
0169  * Function prototypes.
0170  *========================================================================*/
0171
0172 /*
0173  * Routines used for growing the Btree.
0174  */
0175 int xfs_da3_node_create(struct xfs_da_args *args, xfs_dablk_t blkno,
0176                 int level, struct xfs_buf **bpp, int whichfork);
0177 int xfs_da3_split(xfs_da_state_t *state);
0178
0179 /*
0180  * Routines used for shrinking the Btree.
0181  */
0182 int xfs_da3_join(xfs_da_state_t *state);
0183 void    xfs_da3_fixhashpath(struct xfs_da_state *state,
0184                 struct xfs_da_state_path *path_to_to_fix);
0185
0186 /*
0187  * Routines used for finding things in the Btree.
0188  */
0189 int xfs_da3_node_lookup_int(xfs_da_state_t *state, int *result);
0190 int xfs_da3_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path,
0191                      int forward, int release, int *result);
0192 /*
0193  * Utility routines.
0194  */
0195 int xfs_da3_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk,
0196                        xfs_da_state_blk_t *new_blk);
0197 int xfs_da3_node_read(struct xfs_trans *tp, struct xfs_inode *dp,
0198             xfs_dablk_t bno, struct xfs_buf **bpp, int whichfork);
0199 int xfs_da3_node_read_mapped(struct xfs_trans *tp, struct xfs_inode *dp,
0200             xfs_daddr_t mappedbno, struct xfs_buf **bpp,
0201             int whichfork);
0202
0203 /*
0204  * Utility routines.
0205  */
0206
0207 #define XFS_DABUF_MAP_HOLE_OK   (1u << 0)
0208
0209 int xfs_da_grow_inode(xfs_da_args_t *args, xfs_dablk_t *new_blkno);
0210 int xfs_da_grow_inode_int(struct xfs_da_args *args, xfs_fileoff_t *bno,
0211                   int count);
0212 int xfs_da_get_buf(struct xfs_trans *trans, struct xfs_inode *dp,
0213         xfs_dablk_t bno, struct xfs_buf **bp, int whichfork);
0214 int xfs_da_read_buf(struct xfs_trans *trans, struct xfs_inode *dp,
0215         xfs_dablk_t bno, unsigned int flags, struct xfs_buf **bpp,
0216         int whichfork, const struct xfs_buf_ops *ops);
0217 int xfs_da_reada_buf(struct xfs_inode *dp, xfs_dablk_t bno,
0218         unsigned int flags, int whichfork,
0219         const struct xfs_buf_ops *ops);
0220 int xfs_da_shrink_inode(xfs_da_args_t *args, xfs_dablk_t dead_blkno,
0221                       struct xfs_buf *dead_buf);
0222
0223 uint xfs_da_hashname(const uint8_t *name_string, int name_length);
0224 enum xfs_dacmp xfs_da_compname(struct xfs_da_args *args,
0225                 const unsigned char *name, int len);
0226
0227
0228 struct xfs_da_state *xfs_da_state_alloc(struct xfs_da_args *args);
0229 void xfs_da_state_free(xfs_da_state_t *state);
0230 void xfs_da_state_reset(struct xfs_da_state *state, struct xfs_da_args *args);
0231
0232 void    xfs_da3_node_hdr_from_disk(struct xfs_mount *mp,
0233         struct xfs_da3_icnode_hdr *to, struct xfs_da_intnode *from);
0234 void    xfs_da3_node_hdr_to_disk(struct xfs_mount *mp,
0235         struct xfs_da_intnode *to, struct xfs_da3_icnode_hdr *from);
0236
0237 extern struct kmem_cache    *xfs_da_state_cache;
0238
0239 #endif  /* __XFS_DA_BTREE_H__ */