xfs_dir_leaf.c revision 218909
1153323Srodrigc/* 2159451Srodrigc * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc. 3159451Srodrigc * All Rights Reserved. 4153323Srodrigc * 5159451Srodrigc * This program is free software; you can redistribute it and/or 6159451Srodrigc * modify it under the terms of the GNU General Public License as 7153323Srodrigc * published by the Free Software Foundation. 8153323Srodrigc * 9159451Srodrigc * This program is distributed in the hope that it would be useful, 10159451Srodrigc * but WITHOUT ANY WARRANTY; without even the implied warranty of 11159451Srodrigc * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12159451Srodrigc * GNU General Public License for more details. 13153323Srodrigc * 14159451Srodrigc * You should have received a copy of the GNU General Public License 15159451Srodrigc * along with this program; if not, write the Free Software Foundation, 16159451Srodrigc * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17153323Srodrigc */ 18153323Srodrigc#include "xfs.h" 19159451Srodrigc#include "xfs_fs.h" 20153323Srodrigc#include "xfs_types.h" 21159451Srodrigc#include "xfs_log.h" 22153323Srodrigc#include "xfs_inum.h" 23153323Srodrigc#include "xfs_trans.h" 24153323Srodrigc#include "xfs_sb.h" 25153323Srodrigc#include "xfs_dir.h" 26153323Srodrigc#include "xfs_dir2.h" 27153323Srodrigc#include "xfs_dmapi.h" 28153323Srodrigc#include "xfs_mount.h" 29159451Srodrigc#include "xfs_da_btree.h" 30159451Srodrigc#include "xfs_bmap_btree.h" 31153323Srodrigc#include "xfs_alloc_btree.h" 32153323Srodrigc#include "xfs_ialloc_btree.h" 33153323Srodrigc#include "xfs_dir_sf.h" 34153323Srodrigc#include "xfs_dir2_sf.h" 35159451Srodrigc#include "xfs_attr_sf.h" 36153323Srodrigc#include "xfs_dinode.h" 37159451Srodrigc#include "xfs_inode.h" 38153323Srodrigc#include "xfs_inode_item.h" 39159451Srodrigc#include "xfs_alloc.h" 40159451Srodrigc#include "xfs_btree.h" 41153323Srodrigc#include "xfs_bmap.h" 42153323Srodrigc#include "xfs_dir_leaf.h" 43153323Srodrigc#include "xfs_error.h" 44153323Srodrigc 45153323Srodrigc/* 46153323Srodrigc * xfs_dir_leaf.c 47153323Srodrigc * 48153323Srodrigc * Routines to implement leaf blocks of directories as Btrees of hashed names. 49153323Srodrigc */ 50153323Srodrigc 51153323Srodrigc/*======================================================================== 52153323Srodrigc * Function prototypes for the kernel. 53153323Srodrigc *========================================================================*/ 54153323Srodrigc 55153323Srodrigc/* 56153323Srodrigc * Routines used for growing the Btree. 57153323Srodrigc */ 58153323SrodrigcSTATIC void xfs_dir_leaf_add_work(xfs_dabuf_t *leaf_buffer, xfs_da_args_t *args, 59153323Srodrigc int insertion_index, 60153323Srodrigc int freemap_index); 61153323SrodrigcSTATIC int xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *leaf_buffer, 62153323Srodrigc int musthave, int justcheck); 63153323SrodrigcSTATIC void xfs_dir_leaf_rebalance(xfs_da_state_t *state, 64153323Srodrigc xfs_da_state_blk_t *blk1, 65153323Srodrigc xfs_da_state_blk_t *blk2); 66153323SrodrigcSTATIC int xfs_dir_leaf_figure_balance(xfs_da_state_t *state, 67153323Srodrigc xfs_da_state_blk_t *leaf_blk_1, 68153323Srodrigc xfs_da_state_blk_t *leaf_blk_2, 69153323Srodrigc int *number_entries_in_blk1, 70153323Srodrigc int *number_namebytes_in_blk1); 71153323Srodrigc 72159451SrodrigcSTATIC int xfs_dir_leaf_create(struct xfs_da_args *args, 73159451Srodrigc xfs_dablk_t which_block, 74159451Srodrigc struct xfs_dabuf **bpp); 75159451Srodrigc 76153323Srodrigc/* 77153323Srodrigc * Utility routines. 78153323Srodrigc */ 79153323SrodrigcSTATIC void xfs_dir_leaf_moveents(xfs_dir_leafblock_t *src_leaf, 80153323Srodrigc int src_start, 81153323Srodrigc xfs_dir_leafblock_t *dst_leaf, 82153323Srodrigc int dst_start, int move_count, 83153323Srodrigc xfs_mount_t *mp); 84153323Srodrigc 85153323Srodrigc 86153323Srodrigc/*======================================================================== 87153323Srodrigc * External routines when dirsize < XFS_IFORK_DSIZE(dp). 88153323Srodrigc *========================================================================*/ 89153323Srodrigc 90153323Srodrigc 91153323Srodrigc/* 92153323Srodrigc * Validate a given inode number. 93153323Srodrigc */ 94153323Srodrigcint 95153323Srodrigcxfs_dir_ino_validate(xfs_mount_t *mp, xfs_ino_t ino) 96153323Srodrigc{ 97153323Srodrigc xfs_agblock_t agblkno; 98153323Srodrigc xfs_agino_t agino; 99153323Srodrigc xfs_agnumber_t agno; 100153323Srodrigc int ino_ok; 101153323Srodrigc int ioff; 102153323Srodrigc 103153323Srodrigc agno = XFS_INO_TO_AGNO(mp, ino); 104153323Srodrigc agblkno = XFS_INO_TO_AGBNO(mp, ino); 105153323Srodrigc ioff = XFS_INO_TO_OFFSET(mp, ino); 106153323Srodrigc agino = XFS_OFFBNO_TO_AGINO(mp, agblkno, ioff); 107153323Srodrigc ino_ok = 108153323Srodrigc agno < mp->m_sb.sb_agcount && 109153323Srodrigc agblkno < mp->m_sb.sb_agblocks && 110153323Srodrigc agblkno != 0 && 111153323Srodrigc ioff < (1 << mp->m_sb.sb_inopblog) && 112153323Srodrigc XFS_AGINO_TO_INO(mp, agno, agino) == ino; 113153323Srodrigc if (unlikely(XFS_TEST_ERROR(!ino_ok, mp, XFS_ERRTAG_DIR_INO_VALIDATE, 114153323Srodrigc XFS_RANDOM_DIR_INO_VALIDATE))) { 115153323Srodrigc xfs_fs_cmn_err(CE_WARN, mp, "Invalid inode number 0x%Lx", 116153323Srodrigc (unsigned long long) ino); 117153323Srodrigc XFS_ERROR_REPORT("xfs_dir_ino_validate", XFS_ERRLEVEL_LOW, mp); 118153323Srodrigc return XFS_ERROR(EFSCORRUPTED); 119153323Srodrigc } 120153323Srodrigc return 0; 121153323Srodrigc} 122153323Srodrigc 123153323Srodrigc/* 124153323Srodrigc * Create the initial contents of a shortform directory. 125153323Srodrigc */ 126153323Srodrigcint 127153323Srodrigcxfs_dir_shortform_create(xfs_da_args_t *args, xfs_ino_t parent) 128153323Srodrigc{ 129153323Srodrigc xfs_dir_sf_hdr_t *hdr; 130153323Srodrigc xfs_inode_t *dp; 131153323Srodrigc 132153323Srodrigc dp = args->dp; 133153323Srodrigc ASSERT(dp != NULL); 134153323Srodrigc ASSERT(dp->i_d.di_size == 0); 135153323Srodrigc if (dp->i_d.di_format == XFS_DINODE_FMT_EXTENTS) { 136153323Srodrigc dp->i_df.if_flags &= ~XFS_IFEXTENTS; /* just in case */ 137153323Srodrigc dp->i_d.di_format = XFS_DINODE_FMT_LOCAL; 138153323Srodrigc xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE); 139153323Srodrigc dp->i_df.if_flags |= XFS_IFINLINE; 140153323Srodrigc } 141153323Srodrigc ASSERT(dp->i_df.if_flags & XFS_IFINLINE); 142153323Srodrigc ASSERT(dp->i_df.if_bytes == 0); 143153323Srodrigc xfs_idata_realloc(dp, sizeof(*hdr), XFS_DATA_FORK); 144153323Srodrigc hdr = (xfs_dir_sf_hdr_t *)dp->i_df.if_u1.if_data; 145159451Srodrigc XFS_DIR_SF_PUT_DIRINO(&parent, &hdr->parent); 146153323Srodrigc 147159451Srodrigc hdr->count = 0; 148153323Srodrigc dp->i_d.di_size = sizeof(*hdr); 149153323Srodrigc xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA); 150159451Srodrigc return 0; 151153323Srodrigc} 152153323Srodrigc 153153323Srodrigc/* 154153323Srodrigc * Add a name to the shortform directory structure. 155153323Srodrigc * Overflow from the inode has already been checked for. 156153323Srodrigc */ 157153323Srodrigcint 158153323Srodrigcxfs_dir_shortform_addname(xfs_da_args_t *args) 159153323Srodrigc{ 160153323Srodrigc xfs_dir_shortform_t *sf; 161153323Srodrigc xfs_dir_sf_entry_t *sfe; 162153323Srodrigc int i, offset, size; 163153323Srodrigc xfs_inode_t *dp; 164153323Srodrigc 165153323Srodrigc dp = args->dp; 166153323Srodrigc ASSERT(dp->i_df.if_flags & XFS_IFINLINE); 167153323Srodrigc /* 168153323Srodrigc * Catch the case where the conversion from shortform to leaf 169153323Srodrigc * failed part way through. 170153323Srodrigc */ 171153323Srodrigc if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { 172153323Srodrigc ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); 173153323Srodrigc return XFS_ERROR(EIO); 174153323Srodrigc } 175153323Srodrigc ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); 176153323Srodrigc ASSERT(dp->i_df.if_u1.if_data != NULL); 177153323Srodrigc sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; 178153323Srodrigc sfe = &sf->list[0]; 179159451Srodrigc for (i = sf->hdr.count-1; i >= 0; i--) { 180153323Srodrigc if (sfe->namelen == args->namelen && 181153323Srodrigc args->name[0] == sfe->name[0] && 182153323Srodrigc memcmp(args->name, sfe->name, args->namelen) == 0) 183159451Srodrigc return XFS_ERROR(EEXIST); 184153323Srodrigc sfe = XFS_DIR_SF_NEXTENTRY(sfe); 185153323Srodrigc } 186153323Srodrigc 187153323Srodrigc offset = (int)((char *)sfe - (char *)sf); 188153323Srodrigc size = XFS_DIR_SF_ENTSIZE_BYNAME(args->namelen); 189153323Srodrigc xfs_idata_realloc(dp, size, XFS_DATA_FORK); 190153323Srodrigc sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; 191153323Srodrigc sfe = (xfs_dir_sf_entry_t *)((char *)sf + offset); 192153323Srodrigc 193159451Srodrigc XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sfe->inumber); 194153323Srodrigc sfe->namelen = args->namelen; 195153323Srodrigc memcpy(sfe->name, args->name, sfe->namelen); 196159451Srodrigc sf->hdr.count++; 197153323Srodrigc 198153323Srodrigc dp->i_d.di_size += size; 199153323Srodrigc xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA); 200153323Srodrigc 201159451Srodrigc return 0; 202153323Srodrigc} 203153323Srodrigc 204153323Srodrigc/* 205153323Srodrigc * Remove a name from the shortform directory structure. 206153323Srodrigc */ 207153323Srodrigcint 208153323Srodrigcxfs_dir_shortform_removename(xfs_da_args_t *args) 209153323Srodrigc{ 210153323Srodrigc xfs_dir_shortform_t *sf; 211153323Srodrigc xfs_dir_sf_entry_t *sfe; 212153323Srodrigc int base, size = 0, i; 213153323Srodrigc xfs_inode_t *dp; 214153323Srodrigc 215153323Srodrigc dp = args->dp; 216153323Srodrigc ASSERT(dp->i_df.if_flags & XFS_IFINLINE); 217153323Srodrigc /* 218153323Srodrigc * Catch the case where the conversion from shortform to leaf 219153323Srodrigc * failed part way through. 220153323Srodrigc */ 221153323Srodrigc if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { 222153323Srodrigc ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); 223153323Srodrigc return XFS_ERROR(EIO); 224153323Srodrigc } 225153323Srodrigc ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); 226153323Srodrigc ASSERT(dp->i_df.if_u1.if_data != NULL); 227153323Srodrigc base = sizeof(xfs_dir_sf_hdr_t); 228153323Srodrigc sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; 229153323Srodrigc sfe = &sf->list[0]; 230159451Srodrigc for (i = sf->hdr.count-1; i >= 0; i--) { 231153323Srodrigc size = XFS_DIR_SF_ENTSIZE_BYENTRY(sfe); 232153323Srodrigc if (sfe->namelen == args->namelen && 233153323Srodrigc sfe->name[0] == args->name[0] && 234153323Srodrigc memcmp(sfe->name, args->name, args->namelen) == 0) 235153323Srodrigc break; 236153323Srodrigc base += size; 237153323Srodrigc sfe = XFS_DIR_SF_NEXTENTRY(sfe); 238153323Srodrigc } 239153323Srodrigc if (i < 0) { 240153323Srodrigc ASSERT(args->oknoent); 241159451Srodrigc return XFS_ERROR(ENOENT); 242153323Srodrigc } 243153323Srodrigc 244153323Srodrigc if ((base + size) != dp->i_d.di_size) { 245153323Srodrigc memmove(&((char *)sf)[base], &((char *)sf)[base+size], 246153323Srodrigc dp->i_d.di_size - (base+size)); 247153323Srodrigc } 248159451Srodrigc sf->hdr.count--; 249153323Srodrigc 250153323Srodrigc xfs_idata_realloc(dp, -size, XFS_DATA_FORK); 251153323Srodrigc dp->i_d.di_size -= size; 252153323Srodrigc xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA); 253153323Srodrigc 254159451Srodrigc return 0; 255153323Srodrigc} 256153323Srodrigc 257153323Srodrigc/* 258153323Srodrigc * Look up a name in a shortform directory structure. 259153323Srodrigc */ 260153323Srodrigcint 261153323Srodrigcxfs_dir_shortform_lookup(xfs_da_args_t *args) 262153323Srodrigc{ 263153323Srodrigc xfs_dir_shortform_t *sf; 264153323Srodrigc xfs_dir_sf_entry_t *sfe; 265153323Srodrigc int i; 266153323Srodrigc xfs_inode_t *dp; 267153323Srodrigc 268153323Srodrigc dp = args->dp; 269153323Srodrigc ASSERT(dp->i_df.if_flags & XFS_IFINLINE); 270153323Srodrigc /* 271153323Srodrigc * Catch the case where the conversion from shortform to leaf 272153323Srodrigc * failed part way through. 273153323Srodrigc */ 274153323Srodrigc if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { 275153323Srodrigc ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); 276153323Srodrigc return XFS_ERROR(EIO); 277153323Srodrigc } 278153323Srodrigc ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); 279153323Srodrigc ASSERT(dp->i_df.if_u1.if_data != NULL); 280153323Srodrigc sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; 281153323Srodrigc if (args->namelen == 2 && 282153323Srodrigc args->name[0] == '.' && args->name[1] == '.') { 283159451Srodrigc XFS_DIR_SF_GET_DIRINO(&sf->hdr.parent, &args->inumber); 284153323Srodrigc return(XFS_ERROR(EEXIST)); 285153323Srodrigc } 286153323Srodrigc if (args->namelen == 1 && args->name[0] == '.') { 287153323Srodrigc args->inumber = dp->i_ino; 288153323Srodrigc return(XFS_ERROR(EEXIST)); 289153323Srodrigc } 290153323Srodrigc sfe = &sf->list[0]; 291159451Srodrigc for (i = sf->hdr.count-1; i >= 0; i--) { 292153323Srodrigc if (sfe->namelen == args->namelen && 293153323Srodrigc sfe->name[0] == args->name[0] && 294153323Srodrigc memcmp(args->name, sfe->name, args->namelen) == 0) { 295159451Srodrigc XFS_DIR_SF_GET_DIRINO(&sfe->inumber, &args->inumber); 296153323Srodrigc return(XFS_ERROR(EEXIST)); 297153323Srodrigc } 298153323Srodrigc sfe = XFS_DIR_SF_NEXTENTRY(sfe); 299153323Srodrigc } 300153323Srodrigc ASSERT(args->oknoent); 301153323Srodrigc return(XFS_ERROR(ENOENT)); 302153323Srodrigc} 303153323Srodrigc 304153323Srodrigc/* 305153323Srodrigc * Convert from using the shortform to the leaf. 306153323Srodrigc */ 307153323Srodrigcint 308153323Srodrigcxfs_dir_shortform_to_leaf(xfs_da_args_t *iargs) 309153323Srodrigc{ 310153323Srodrigc xfs_inode_t *dp; 311153323Srodrigc xfs_dir_shortform_t *sf; 312153323Srodrigc xfs_dir_sf_entry_t *sfe; 313153323Srodrigc xfs_da_args_t args; 314153323Srodrigc xfs_ino_t inumber; 315153323Srodrigc char *tmpbuffer; 316153323Srodrigc int retval, i, size; 317153323Srodrigc xfs_dablk_t blkno; 318153323Srodrigc xfs_dabuf_t *bp; 319153323Srodrigc 320153323Srodrigc dp = iargs->dp; 321153323Srodrigc /* 322153323Srodrigc * Catch the case where the conversion from shortform to leaf 323153323Srodrigc * failed part way through. 324153323Srodrigc */ 325153323Srodrigc if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { 326153323Srodrigc ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); 327153323Srodrigc return XFS_ERROR(EIO); 328153323Srodrigc } 329153323Srodrigc ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); 330153323Srodrigc ASSERT(dp->i_df.if_u1.if_data != NULL); 331153323Srodrigc size = dp->i_df.if_bytes; 332153323Srodrigc tmpbuffer = kmem_alloc(size, KM_SLEEP); 333153323Srodrigc ASSERT(tmpbuffer != NULL); 334153323Srodrigc 335153323Srodrigc memcpy(tmpbuffer, dp->i_df.if_u1.if_data, size); 336153323Srodrigc 337153323Srodrigc sf = (xfs_dir_shortform_t *)tmpbuffer; 338159451Srodrigc XFS_DIR_SF_GET_DIRINO(&sf->hdr.parent, &inumber); 339153323Srodrigc 340153323Srodrigc xfs_idata_realloc(dp, -size, XFS_DATA_FORK); 341153323Srodrigc dp->i_d.di_size = 0; 342153323Srodrigc xfs_trans_log_inode(iargs->trans, dp, XFS_ILOG_CORE); 343153323Srodrigc retval = xfs_da_grow_inode(iargs, &blkno); 344153323Srodrigc if (retval) 345153323Srodrigc goto out; 346153323Srodrigc 347153323Srodrigc ASSERT(blkno == 0); 348153323Srodrigc retval = xfs_dir_leaf_create(iargs, blkno, &bp); 349153323Srodrigc if (retval) 350153323Srodrigc goto out; 351153323Srodrigc xfs_da_buf_done(bp); 352153323Srodrigc 353153323Srodrigc args.name = "."; 354153323Srodrigc args.namelen = 1; 355153323Srodrigc args.hashval = xfs_dir_hash_dot; 356153323Srodrigc args.inumber = dp->i_ino; 357153323Srodrigc args.dp = dp; 358153323Srodrigc args.firstblock = iargs->firstblock; 359153323Srodrigc args.flist = iargs->flist; 360153323Srodrigc args.total = iargs->total; 361153323Srodrigc args.whichfork = XFS_DATA_FORK; 362153323Srodrigc args.trans = iargs->trans; 363153323Srodrigc args.justcheck = 0; 364153323Srodrigc args.addname = args.oknoent = 1; 365153323Srodrigc retval = xfs_dir_leaf_addname(&args); 366153323Srodrigc if (retval) 367153323Srodrigc goto out; 368153323Srodrigc 369153323Srodrigc args.name = ".."; 370153323Srodrigc args.namelen = 2; 371153323Srodrigc args.hashval = xfs_dir_hash_dotdot; 372153323Srodrigc args.inumber = inumber; 373153323Srodrigc retval = xfs_dir_leaf_addname(&args); 374153323Srodrigc if (retval) 375153323Srodrigc goto out; 376153323Srodrigc 377153323Srodrigc sfe = &sf->list[0]; 378159451Srodrigc for (i = 0; i < sf->hdr.count; i++) { 379153323Srodrigc args.name = (char *)(sfe->name); 380153323Srodrigc args.namelen = sfe->namelen; 381153323Srodrigc args.hashval = xfs_da_hashname((char *)(sfe->name), 382153323Srodrigc sfe->namelen); 383159451Srodrigc XFS_DIR_SF_GET_DIRINO(&sfe->inumber, &args.inumber); 384153323Srodrigc retval = xfs_dir_leaf_addname(&args); 385153323Srodrigc if (retval) 386153323Srodrigc goto out; 387153323Srodrigc sfe = XFS_DIR_SF_NEXTENTRY(sfe); 388153323Srodrigc } 389153323Srodrigc retval = 0; 390153323Srodrigc 391153323Srodrigcout: 392153323Srodrigc kmem_free(tmpbuffer, size); 393159451Srodrigc return retval; 394153323Srodrigc} 395153323Srodrigc 396153323SrodrigcSTATIC int 397153323Srodrigcxfs_dir_shortform_compare(const void *a, const void *b) 398153323Srodrigc{ 399153323Srodrigc const xfs_dir_sf_sort_t *sa, *sb; 400153323Srodrigc 401153323Srodrigc sa = (const xfs_dir_sf_sort_t *)a; 402153323Srodrigc sb = (const xfs_dir_sf_sort_t *)b; 403153323Srodrigc if (sa->hash < sb->hash) 404153323Srodrigc return -1; 405153323Srodrigc else if (sa->hash > sb->hash) 406153323Srodrigc return 1; 407153323Srodrigc else 408153323Srodrigc return sa->entno - sb->entno; 409153323Srodrigc} 410153323Srodrigc 411153323Srodrigc/* 412153323Srodrigc * Copy out directory entries for getdents(), for shortform directories. 413153323Srodrigc */ 414153323Srodrigc/*ARGSUSED*/ 415153323Srodrigcint 416153323Srodrigcxfs_dir_shortform_getdents(xfs_inode_t *dp, uio_t *uio, int *eofp, 417153323Srodrigc xfs_dirent_t *dbp, xfs_dir_put_t put) 418153323Srodrigc{ 419153323Srodrigc xfs_dir_shortform_t *sf; 420153323Srodrigc xfs_dir_sf_entry_t *sfe; 421153323Srodrigc int retval, i, sbsize, nsbuf, lastresid=0, want_entno; 422153323Srodrigc xfs_mount_t *mp; 423153323Srodrigc xfs_dahash_t cookhash, hash; 424153323Srodrigc xfs_dir_put_args_t p; 425153323Srodrigc xfs_dir_sf_sort_t *sbuf, *sbp; 426153323Srodrigc 427153323Srodrigc mp = dp->i_mount; 428153323Srodrigc sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; 429153323Srodrigc cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset); 430153323Srodrigc want_entno = XFS_DA_COOKIE_ENTRY(mp, uio->uio_offset); 431159451Srodrigc nsbuf = sf->hdr.count + 2; 432153323Srodrigc sbsize = (nsbuf + 1) * sizeof(*sbuf); 433153323Srodrigc sbp = sbuf = kmem_alloc(sbsize, KM_SLEEP); 434153323Srodrigc 435153323Srodrigc xfs_dir_trace_g_du("sf: start", dp, uio); 436153323Srodrigc 437153323Srodrigc /* 438153323Srodrigc * Collect all the entries into the buffer. 439153323Srodrigc * Entry 0 is . 440153323Srodrigc */ 441153323Srodrigc sbp->entno = 0; 442153323Srodrigc sbp->seqno = 0; 443153323Srodrigc sbp->hash = xfs_dir_hash_dot; 444153323Srodrigc sbp->ino = dp->i_ino; 445153323Srodrigc sbp->name = "."; 446153323Srodrigc sbp->namelen = 1; 447153323Srodrigc sbp++; 448153323Srodrigc 449153323Srodrigc /* 450153323Srodrigc * Entry 1 is .. 451153323Srodrigc */ 452153323Srodrigc sbp->entno = 1; 453153323Srodrigc sbp->seqno = 0; 454153323Srodrigc sbp->hash = xfs_dir_hash_dotdot; 455159451Srodrigc sbp->ino = XFS_GET_DIR_INO8(sf->hdr.parent); 456153323Srodrigc sbp->name = ".."; 457153323Srodrigc sbp->namelen = 2; 458153323Srodrigc sbp++; 459153323Srodrigc 460153323Srodrigc /* 461153323Srodrigc * Scan the directory data for the rest of the entries. 462153323Srodrigc */ 463159451Srodrigc for (i = 0, sfe = &sf->list[0]; i < sf->hdr.count; i++) { 464153323Srodrigc 465153323Srodrigc if (unlikely( 466153323Srodrigc ((char *)sfe < (char *)sf) || 467153323Srodrigc ((char *)sfe >= ((char *)sf + dp->i_df.if_bytes)))) { 468153323Srodrigc xfs_dir_trace_g_du("sf: corrupted", dp, uio); 469153323Srodrigc XFS_CORRUPTION_ERROR("xfs_dir_shortform_getdents", 470153323Srodrigc XFS_ERRLEVEL_LOW, mp, sfe); 471153323Srodrigc kmem_free(sbuf, sbsize); 472153323Srodrigc return XFS_ERROR(EFSCORRUPTED); 473153323Srodrigc } 474153323Srodrigc 475153323Srodrigc sbp->entno = i + 2; 476153323Srodrigc sbp->seqno = 0; 477153323Srodrigc sbp->hash = xfs_da_hashname((char *)sfe->name, sfe->namelen); 478159451Srodrigc sbp->ino = XFS_GET_DIR_INO8(sfe->inumber); 479153323Srodrigc sbp->name = (char *)sfe->name; 480153323Srodrigc sbp->namelen = sfe->namelen; 481153323Srodrigc sfe = XFS_DIR_SF_NEXTENTRY(sfe); 482153323Srodrigc sbp++; 483153323Srodrigc } 484153323Srodrigc 485153323Srodrigc /* 486153323Srodrigc * Sort the entries on hash then entno. 487153323Srodrigc */ 488159451Srodrigc xfs_sort(sbuf, nsbuf, sizeof(*sbuf), xfs_dir_shortform_compare); 489153323Srodrigc /* 490153323Srodrigc * Stuff in last entry. 491153323Srodrigc */ 492153323Srodrigc sbp->entno = nsbuf; 493153323Srodrigc sbp->hash = XFS_DA_MAXHASH; 494153323Srodrigc sbp->seqno = 0; 495153323Srodrigc /* 496153323Srodrigc * Figure out the sequence numbers in case there's a hash duplicate. 497153323Srodrigc */ 498153323Srodrigc for (hash = sbuf->hash, sbp = sbuf + 1; 499153323Srodrigc sbp < &sbuf[nsbuf + 1]; sbp++) { 500153323Srodrigc if (sbp->hash == hash) 501153323Srodrigc sbp->seqno = sbp[-1].seqno + 1; 502153323Srodrigc else 503153323Srodrigc hash = sbp->hash; 504153323Srodrigc } 505153323Srodrigc 506153323Srodrigc /* 507153323Srodrigc * Set up put routine. 508153323Srodrigc */ 509153323Srodrigc p.dbp = dbp; 510153323Srodrigc p.put = put; 511153323Srodrigc p.uio = uio; 512153323Srodrigc 513153323Srodrigc /* 514153323Srodrigc * Find our place. 515153323Srodrigc */ 516153323Srodrigc for (sbp = sbuf; sbp < &sbuf[nsbuf + 1]; sbp++) { 517153323Srodrigc if (sbp->hash > cookhash || 518153323Srodrigc (sbp->hash == cookhash && sbp->seqno >= want_entno)) 519153323Srodrigc break; 520153323Srodrigc } 521153323Srodrigc 522153323Srodrigc /* 523153323Srodrigc * Did we fail to find anything? We stop at the last entry, 524153323Srodrigc * the one we put maxhash into. 525153323Srodrigc */ 526153323Srodrigc if (sbp == &sbuf[nsbuf]) { 527153323Srodrigc kmem_free(sbuf, sbsize); 528153323Srodrigc xfs_dir_trace_g_du("sf: hash beyond end", dp, uio); 529153323Srodrigc uio->uio_offset = XFS_DA_MAKE_COOKIE(mp, 0, 0, XFS_DA_MAXHASH); 530153323Srodrigc *eofp = 1; 531153323Srodrigc return 0; 532153323Srodrigc } 533153323Srodrigc 534153323Srodrigc /* 535153323Srodrigc * Loop putting entries into the user buffer. 536153323Srodrigc */ 537153323Srodrigc while (sbp < &sbuf[nsbuf]) { 538153323Srodrigc /* 539153323Srodrigc * Save the first resid in a run of equal-hashval entries 540153323Srodrigc * so that we can back them out if they don't all fit. 541153323Srodrigc */ 542153323Srodrigc if (sbp->seqno == 0 || sbp == sbuf) 543153323Srodrigc lastresid = uio->uio_resid; 544153323Srodrigc XFS_PUT_COOKIE(p.cook, mp, 0, sbp[1].seqno, sbp[1].hash); 545153323Srodrigc p.ino = sbp->ino; 546153323Srodrigc#if XFS_BIG_INUMS 547153323Srodrigc p.ino += mp->m_inoadd; 548153323Srodrigc#endif 549153323Srodrigc p.name = sbp->name; 550153323Srodrigc p.namelen = sbp->namelen; 551153323Srodrigc retval = p.put(&p); 552153323Srodrigc if (!p.done) { 553153323Srodrigc uio->uio_offset = 554153323Srodrigc XFS_DA_MAKE_COOKIE(mp, 0, 0, sbp->hash); 555153323Srodrigc kmem_free(sbuf, sbsize); 556153323Srodrigc uio->uio_resid = lastresid; 557153323Srodrigc xfs_dir_trace_g_du("sf: E-O-B", dp, uio); 558153323Srodrigc return retval; 559153323Srodrigc } 560153323Srodrigc sbp++; 561153323Srodrigc } 562153323Srodrigc kmem_free(sbuf, sbsize); 563153323Srodrigc uio->uio_offset = p.cook.o; 564153323Srodrigc *eofp = 1; 565153323Srodrigc xfs_dir_trace_g_du("sf: E-O-F", dp, uio); 566153323Srodrigc return 0; 567153323Srodrigc} 568153323Srodrigc 569153323Srodrigc/* 570153323Srodrigc * Look up a name in a shortform directory structure, replace the inode number. 571153323Srodrigc */ 572153323Srodrigcint 573153323Srodrigcxfs_dir_shortform_replace(xfs_da_args_t *args) 574153323Srodrigc{ 575153323Srodrigc xfs_dir_shortform_t *sf; 576153323Srodrigc xfs_dir_sf_entry_t *sfe; 577153323Srodrigc xfs_inode_t *dp; 578153323Srodrigc int i; 579153323Srodrigc 580153323Srodrigc dp = args->dp; 581153323Srodrigc ASSERT(dp->i_df.if_flags & XFS_IFINLINE); 582153323Srodrigc /* 583153323Srodrigc * Catch the case where the conversion from shortform to leaf 584153323Srodrigc * failed part way through. 585153323Srodrigc */ 586153323Srodrigc if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { 587153323Srodrigc ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); 588153323Srodrigc return XFS_ERROR(EIO); 589153323Srodrigc } 590153323Srodrigc ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); 591153323Srodrigc ASSERT(dp->i_df.if_u1.if_data != NULL); 592153323Srodrigc sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; 593153323Srodrigc if (args->namelen == 2 && 594153323Srodrigc args->name[0] == '.' && args->name[1] == '.') { 595153323Srodrigc /* XXX - replace assert? */ 596159451Srodrigc XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sf->hdr.parent); 597153323Srodrigc xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA); 598159451Srodrigc return 0; 599153323Srodrigc } 600153323Srodrigc ASSERT(args->namelen != 1 || args->name[0] != '.'); 601153323Srodrigc sfe = &sf->list[0]; 602159451Srodrigc for (i = sf->hdr.count-1; i >= 0; i--) { 603153323Srodrigc if (sfe->namelen == args->namelen && 604153323Srodrigc sfe->name[0] == args->name[0] && 605153323Srodrigc memcmp(args->name, sfe->name, args->namelen) == 0) { 606153323Srodrigc ASSERT(memcmp((char *)&args->inumber, 607153323Srodrigc (char *)&sfe->inumber, sizeof(xfs_ino_t))); 608159451Srodrigc XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sfe->inumber); 609153323Srodrigc xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA); 610159451Srodrigc return 0; 611153323Srodrigc } 612153323Srodrigc sfe = XFS_DIR_SF_NEXTENTRY(sfe); 613153323Srodrigc } 614153323Srodrigc ASSERT(args->oknoent); 615159451Srodrigc return XFS_ERROR(ENOENT); 616153323Srodrigc} 617153323Srodrigc 618153323Srodrigc/* 619153323Srodrigc * Convert a leaf directory to shortform structure 620153323Srodrigc */ 621153323Srodrigcint 622153323Srodrigcxfs_dir_leaf_to_shortform(xfs_da_args_t *iargs) 623153323Srodrigc{ 624153323Srodrigc xfs_dir_leafblock_t *leaf; 625153323Srodrigc xfs_dir_leaf_hdr_t *hdr; 626153323Srodrigc xfs_dir_leaf_entry_t *entry; 627153323Srodrigc xfs_dir_leaf_name_t *namest; 628153323Srodrigc xfs_da_args_t args; 629153323Srodrigc xfs_inode_t *dp; 630159451Srodrigc xfs_ino_t parent = 0; 631153323Srodrigc char *tmpbuffer; 632153323Srodrigc int retval, i; 633153323Srodrigc xfs_dabuf_t *bp; 634153323Srodrigc 635153323Srodrigc dp = iargs->dp; 636153323Srodrigc tmpbuffer = kmem_alloc(XFS_LBSIZE(dp->i_mount), KM_SLEEP); 637153323Srodrigc ASSERT(tmpbuffer != NULL); 638153323Srodrigc 639153323Srodrigc retval = xfs_da_read_buf(iargs->trans, iargs->dp, 0, -1, &bp, 640153323Srodrigc XFS_DATA_FORK); 641153323Srodrigc if (retval) 642153323Srodrigc goto out; 643153323Srodrigc ASSERT(bp != NULL); 644153323Srodrigc memcpy(tmpbuffer, bp->data, XFS_LBSIZE(dp->i_mount)); 645153323Srodrigc leaf = (xfs_dir_leafblock_t *)tmpbuffer; 646159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 647153323Srodrigc memset(bp->data, 0, XFS_LBSIZE(dp->i_mount)); 648153323Srodrigc 649153323Srodrigc /* 650153323Srodrigc * Find and special case the parent inode number 651153323Srodrigc */ 652153323Srodrigc hdr = &leaf->hdr; 653153323Srodrigc entry = &leaf->entries[0]; 654153323Srodrigc for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) { 655153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); 656153323Srodrigc if ((entry->namelen == 2) && 657153323Srodrigc (namest->name[0] == '.') && 658153323Srodrigc (namest->name[1] == '.')) { 659159451Srodrigc XFS_DIR_SF_GET_DIRINO(&namest->inumber, &parent); 660159451Srodrigc entry->nameidx = 0; 661153323Srodrigc } else if ((entry->namelen == 1) && (namest->name[0] == '.')) { 662159451Srodrigc entry->nameidx = 0; 663153323Srodrigc } 664153323Srodrigc } 665153323Srodrigc retval = xfs_da_shrink_inode(iargs, 0, bp); 666153323Srodrigc if (retval) 667153323Srodrigc goto out; 668153323Srodrigc retval = xfs_dir_shortform_create(iargs, parent); 669153323Srodrigc if (retval) 670153323Srodrigc goto out; 671153323Srodrigc 672153323Srodrigc /* 673153323Srodrigc * Copy the rest of the filenames 674153323Srodrigc */ 675153323Srodrigc entry = &leaf->entries[0]; 676153323Srodrigc args.dp = dp; 677153323Srodrigc args.firstblock = iargs->firstblock; 678153323Srodrigc args.flist = iargs->flist; 679153323Srodrigc args.total = iargs->total; 680153323Srodrigc args.whichfork = XFS_DATA_FORK; 681153323Srodrigc args.trans = iargs->trans; 682153323Srodrigc args.justcheck = 0; 683153323Srodrigc args.addname = args.oknoent = 1; 684153323Srodrigc for (i = 0; i < INT_GET(hdr->count, ARCH_CONVERT); entry++, i++) { 685159451Srodrigc if (!entry->nameidx) 686153323Srodrigc continue; 687153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); 688153323Srodrigc args.name = (char *)(namest->name); 689153323Srodrigc args.namelen = entry->namelen; 690153323Srodrigc args.hashval = INT_GET(entry->hashval, ARCH_CONVERT); 691159451Srodrigc XFS_DIR_SF_GET_DIRINO(&namest->inumber, &args.inumber); 692153323Srodrigc xfs_dir_shortform_addname(&args); 693153323Srodrigc } 694153323Srodrigc 695153323Srodrigcout: 696153323Srodrigc kmem_free(tmpbuffer, XFS_LBSIZE(dp->i_mount)); 697159451Srodrigc return retval; 698153323Srodrigc} 699153323Srodrigc 700153323Srodrigc/* 701153323Srodrigc * Convert from using a single leaf to a root node and a leaf. 702153323Srodrigc */ 703153323Srodrigcint 704153323Srodrigcxfs_dir_leaf_to_node(xfs_da_args_t *args) 705153323Srodrigc{ 706153323Srodrigc xfs_dir_leafblock_t *leaf; 707153323Srodrigc xfs_da_intnode_t *node; 708153323Srodrigc xfs_inode_t *dp; 709153323Srodrigc xfs_dabuf_t *bp1, *bp2; 710153323Srodrigc xfs_dablk_t blkno; 711153323Srodrigc int retval; 712153323Srodrigc 713153323Srodrigc dp = args->dp; 714153323Srodrigc retval = xfs_da_grow_inode(args, &blkno); 715153323Srodrigc ASSERT(blkno == 1); 716153323Srodrigc if (retval) 717159451Srodrigc return retval; 718153323Srodrigc retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp1, 719153323Srodrigc XFS_DATA_FORK); 720153323Srodrigc if (retval) 721159451Srodrigc return retval; 722153323Srodrigc ASSERT(bp1 != NULL); 723153323Srodrigc retval = xfs_da_get_buf(args->trans, args->dp, 1, -1, &bp2, 724153323Srodrigc XFS_DATA_FORK); 725153323Srodrigc if (retval) { 726153323Srodrigc xfs_da_buf_done(bp1); 727159451Srodrigc return retval; 728153323Srodrigc } 729153323Srodrigc ASSERT(bp2 != NULL); 730153323Srodrigc memcpy(bp2->data, bp1->data, XFS_LBSIZE(dp->i_mount)); 731153323Srodrigc xfs_da_buf_done(bp1); 732153323Srodrigc xfs_da_log_buf(args->trans, bp2, 0, XFS_LBSIZE(dp->i_mount) - 1); 733153323Srodrigc 734153323Srodrigc /* 735153323Srodrigc * Set up the new root node. 736153323Srodrigc */ 737153323Srodrigc retval = xfs_da_node_create(args, 0, 1, &bp1, XFS_DATA_FORK); 738153323Srodrigc if (retval) { 739153323Srodrigc xfs_da_buf_done(bp2); 740159451Srodrigc return retval; 741153323Srodrigc } 742153323Srodrigc node = bp1->data; 743153323Srodrigc leaf = bp2->data; 744159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 745159451Srodrigc node->btree[0].hashval = cpu_to_be32( 746159451Srodrigc INT_GET(leaf->entries[ 747159451Srodrigc INT_GET(leaf->hdr.count, ARCH_CONVERT)-1].hashval, ARCH_CONVERT)); 748153323Srodrigc xfs_da_buf_done(bp2); 749159451Srodrigc node->btree[0].before = cpu_to_be32(blkno); 750159451Srodrigc node->hdr.count = cpu_to_be16(1); 751153323Srodrigc xfs_da_log_buf(args->trans, bp1, 752153323Srodrigc XFS_DA_LOGRANGE(node, &node->btree[0], sizeof(node->btree[0]))); 753153323Srodrigc xfs_da_buf_done(bp1); 754153323Srodrigc 755159451Srodrigc return retval; 756153323Srodrigc} 757153323Srodrigc 758153323Srodrigc 759153323Srodrigc/*======================================================================== 760153323Srodrigc * Routines used for growing the Btree. 761153323Srodrigc *========================================================================*/ 762153323Srodrigc 763153323Srodrigc/* 764153323Srodrigc * Create the initial contents of a leaf directory 765153323Srodrigc * or a leaf in a node directory. 766153323Srodrigc */ 767159451SrodrigcSTATIC int 768153323Srodrigcxfs_dir_leaf_create(xfs_da_args_t *args, xfs_dablk_t blkno, xfs_dabuf_t **bpp) 769153323Srodrigc{ 770153323Srodrigc xfs_dir_leafblock_t *leaf; 771153323Srodrigc xfs_dir_leaf_hdr_t *hdr; 772153323Srodrigc xfs_inode_t *dp; 773153323Srodrigc xfs_dabuf_t *bp; 774153323Srodrigc int retval; 775153323Srodrigc 776153323Srodrigc dp = args->dp; 777153323Srodrigc ASSERT(dp != NULL); 778153323Srodrigc retval = xfs_da_get_buf(args->trans, dp, blkno, -1, &bp, XFS_DATA_FORK); 779153323Srodrigc if (retval) 780159451Srodrigc return retval; 781153323Srodrigc ASSERT(bp != NULL); 782153323Srodrigc leaf = bp->data; 783153323Srodrigc memset((char *)leaf, 0, XFS_LBSIZE(dp->i_mount)); 784153323Srodrigc hdr = &leaf->hdr; 785159451Srodrigc hdr->info.magic = cpu_to_be16(XFS_DIR_LEAF_MAGIC); 786153323Srodrigc INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount)); 787159451Srodrigc if (!hdr->firstused) 788153323Srodrigc INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount) - 1); 789153323Srodrigc INT_SET(hdr->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t)); 790153323Srodrigc INT_SET(hdr->freemap[0].size, ARCH_CONVERT, INT_GET(hdr->firstused, ARCH_CONVERT) - INT_GET(hdr->freemap[0].base, ARCH_CONVERT)); 791153323Srodrigc 792153323Srodrigc xfs_da_log_buf(args->trans, bp, 0, XFS_LBSIZE(dp->i_mount) - 1); 793153323Srodrigc 794153323Srodrigc *bpp = bp; 795159451Srodrigc return 0; 796153323Srodrigc} 797153323Srodrigc 798153323Srodrigc/* 799153323Srodrigc * Split the leaf node, rebalance, then add the new entry. 800153323Srodrigc */ 801153323Srodrigcint 802153323Srodrigcxfs_dir_leaf_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk, 803153323Srodrigc xfs_da_state_blk_t *newblk) 804153323Srodrigc{ 805153323Srodrigc xfs_dablk_t blkno; 806153323Srodrigc xfs_da_args_t *args; 807153323Srodrigc int error; 808153323Srodrigc 809153323Srodrigc /* 810153323Srodrigc * Allocate space for a new leaf node. 811153323Srodrigc */ 812153323Srodrigc args = state->args; 813153323Srodrigc ASSERT(args != NULL); 814153323Srodrigc ASSERT(oldblk->magic == XFS_DIR_LEAF_MAGIC); 815153323Srodrigc error = xfs_da_grow_inode(args, &blkno); 816153323Srodrigc if (error) 817159451Srodrigc return error; 818153323Srodrigc error = xfs_dir_leaf_create(args, blkno, &newblk->bp); 819153323Srodrigc if (error) 820159451Srodrigc return error; 821153323Srodrigc newblk->blkno = blkno; 822153323Srodrigc newblk->magic = XFS_DIR_LEAF_MAGIC; 823153323Srodrigc 824153323Srodrigc /* 825153323Srodrigc * Rebalance the entries across the two leaves. 826153323Srodrigc */ 827153323Srodrigc xfs_dir_leaf_rebalance(state, oldblk, newblk); 828153323Srodrigc error = xfs_da_blk_link(state, oldblk, newblk); 829153323Srodrigc if (error) 830159451Srodrigc return error; 831153323Srodrigc 832153323Srodrigc /* 833153323Srodrigc * Insert the new entry in the correct block. 834153323Srodrigc */ 835153323Srodrigc if (state->inleaf) { 836153323Srodrigc error = xfs_dir_leaf_add(oldblk->bp, args, oldblk->index); 837153323Srodrigc } else { 838153323Srodrigc error = xfs_dir_leaf_add(newblk->bp, args, newblk->index); 839153323Srodrigc } 840153323Srodrigc 841153323Srodrigc /* 842153323Srodrigc * Update last hashval in each block since we added the name. 843153323Srodrigc */ 844153323Srodrigc oldblk->hashval = xfs_dir_leaf_lasthash(oldblk->bp, NULL); 845153323Srodrigc newblk->hashval = xfs_dir_leaf_lasthash(newblk->bp, NULL); 846159451Srodrigc return error; 847153323Srodrigc} 848153323Srodrigc 849153323Srodrigc/* 850153323Srodrigc * Add a name to the leaf directory structure. 851153323Srodrigc * 852153323Srodrigc * Must take into account fragmented leaves and leaves where spacemap has 853153323Srodrigc * lost some freespace information (ie: holes). 854153323Srodrigc */ 855153323Srodrigcint 856153323Srodrigcxfs_dir_leaf_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index) 857153323Srodrigc{ 858153323Srodrigc xfs_dir_leafblock_t *leaf; 859153323Srodrigc xfs_dir_leaf_hdr_t *hdr; 860153323Srodrigc xfs_dir_leaf_map_t *map; 861153323Srodrigc int tablesize, entsize, sum, i, tmp, error; 862153323Srodrigc 863153323Srodrigc leaf = bp->data; 864159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 865153323Srodrigc ASSERT((index >= 0) && (index <= INT_GET(leaf->hdr.count, ARCH_CONVERT))); 866153323Srodrigc hdr = &leaf->hdr; 867153323Srodrigc entsize = XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen); 868153323Srodrigc 869153323Srodrigc /* 870153323Srodrigc * Search through freemap for first-fit on new name length. 871153323Srodrigc * (may need to figure in size of entry struct too) 872153323Srodrigc */ 873153323Srodrigc tablesize = (INT_GET(hdr->count, ARCH_CONVERT) + 1) * (uint)sizeof(xfs_dir_leaf_entry_t) 874153323Srodrigc + (uint)sizeof(xfs_dir_leaf_hdr_t); 875153323Srodrigc map = &hdr->freemap[XFS_DIR_LEAF_MAPSIZE-1]; 876153323Srodrigc for (sum = 0, i = XFS_DIR_LEAF_MAPSIZE-1; i >= 0; map--, i--) { 877153323Srodrigc if (tablesize > INT_GET(hdr->firstused, ARCH_CONVERT)) { 878153323Srodrigc sum += INT_GET(map->size, ARCH_CONVERT); 879153323Srodrigc continue; 880153323Srodrigc } 881159451Srodrigc if (!map->size) 882153323Srodrigc continue; /* no space in this map */ 883153323Srodrigc tmp = entsize; 884153323Srodrigc if (INT_GET(map->base, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT)) 885153323Srodrigc tmp += (uint)sizeof(xfs_dir_leaf_entry_t); 886153323Srodrigc if (INT_GET(map->size, ARCH_CONVERT) >= tmp) { 887153323Srodrigc if (!args->justcheck) 888153323Srodrigc xfs_dir_leaf_add_work(bp, args, index, i); 889159451Srodrigc return 0; 890153323Srodrigc } 891153323Srodrigc sum += INT_GET(map->size, ARCH_CONVERT); 892153323Srodrigc } 893153323Srodrigc 894153323Srodrigc /* 895153323Srodrigc * If there are no holes in the address space of the block, 896153323Srodrigc * and we don't have enough freespace, then compaction will do us 897153323Srodrigc * no good and we should just give up. 898153323Srodrigc */ 899153323Srodrigc if (!hdr->holes && (sum < entsize)) 900159451Srodrigc return XFS_ERROR(ENOSPC); 901153323Srodrigc 902153323Srodrigc /* 903153323Srodrigc * Compact the entries to coalesce free space. 904153323Srodrigc * Pass the justcheck flag so the checking pass can return 905153323Srodrigc * an error, without changing anything, if it won't fit. 906153323Srodrigc */ 907153323Srodrigc error = xfs_dir_leaf_compact(args->trans, bp, 908153323Srodrigc args->total == 0 ? 909153323Srodrigc entsize + 910153323Srodrigc (uint)sizeof(xfs_dir_leaf_entry_t) : 0, 911153323Srodrigc args->justcheck); 912153323Srodrigc if (error) 913159451Srodrigc return error; 914153323Srodrigc /* 915153323Srodrigc * After compaction, the block is guaranteed to have only one 916153323Srodrigc * free region, in freemap[0]. If it is not big enough, give up. 917153323Srodrigc */ 918153323Srodrigc if (INT_GET(hdr->freemap[0].size, ARCH_CONVERT) < 919153323Srodrigc (entsize + (uint)sizeof(xfs_dir_leaf_entry_t))) 920159451Srodrigc return XFS_ERROR(ENOSPC); 921153323Srodrigc 922153323Srodrigc if (!args->justcheck) 923153323Srodrigc xfs_dir_leaf_add_work(bp, args, index, 0); 924159451Srodrigc return 0; 925153323Srodrigc} 926153323Srodrigc 927153323Srodrigc/* 928153323Srodrigc * Add a name to a leaf directory structure. 929153323Srodrigc */ 930153323SrodrigcSTATIC void 931153323Srodrigcxfs_dir_leaf_add_work(xfs_dabuf_t *bp, xfs_da_args_t *args, int index, 932153323Srodrigc int mapindex) 933153323Srodrigc{ 934153323Srodrigc xfs_dir_leafblock_t *leaf; 935153323Srodrigc xfs_dir_leaf_hdr_t *hdr; 936153323Srodrigc xfs_dir_leaf_entry_t *entry; 937153323Srodrigc xfs_dir_leaf_name_t *namest; 938153323Srodrigc xfs_dir_leaf_map_t *map; 939153323Srodrigc /* REFERENCED */ 940153323Srodrigc xfs_mount_t *mp; 941153323Srodrigc int tmp, i; 942153323Srodrigc 943153323Srodrigc leaf = bp->data; 944159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 945153323Srodrigc hdr = &leaf->hdr; 946153323Srodrigc ASSERT((mapindex >= 0) && (mapindex < XFS_DIR_LEAF_MAPSIZE)); 947153323Srodrigc ASSERT((index >= 0) && (index <= INT_GET(hdr->count, ARCH_CONVERT))); 948153323Srodrigc 949153323Srodrigc /* 950153323Srodrigc * Force open some space in the entry array and fill it in. 951153323Srodrigc */ 952153323Srodrigc entry = &leaf->entries[index]; 953153323Srodrigc if (index < INT_GET(hdr->count, ARCH_CONVERT)) { 954153323Srodrigc tmp = INT_GET(hdr->count, ARCH_CONVERT) - index; 955153323Srodrigc tmp *= (uint)sizeof(xfs_dir_leaf_entry_t); 956153323Srodrigc memmove(entry + 1, entry, tmp); 957153323Srodrigc xfs_da_log_buf(args->trans, bp, 958153323Srodrigc XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry))); 959153323Srodrigc } 960153323Srodrigc INT_MOD(hdr->count, ARCH_CONVERT, +1); 961153323Srodrigc 962153323Srodrigc /* 963153323Srodrigc * Allocate space for the new string (at the end of the run). 964153323Srodrigc */ 965153323Srodrigc map = &hdr->freemap[mapindex]; 966153323Srodrigc mp = args->trans->t_mountp; 967153323Srodrigc ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp)); 968153323Srodrigc ASSERT(INT_GET(map->size, ARCH_CONVERT) >= XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen)); 969153323Srodrigc ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp)); 970153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, -(XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen))); 971153323Srodrigc INT_SET(entry->nameidx, ARCH_CONVERT, INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT)); 972153323Srodrigc INT_SET(entry->hashval, ARCH_CONVERT, args->hashval); 973153323Srodrigc entry->namelen = args->namelen; 974153323Srodrigc xfs_da_log_buf(args->trans, bp, 975153323Srodrigc XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry))); 976153323Srodrigc 977153323Srodrigc /* 978153323Srodrigc * Copy the string and inode number into the new space. 979153323Srodrigc */ 980153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); 981159451Srodrigc XFS_DIR_SF_PUT_DIRINO(&args->inumber, &namest->inumber); 982153323Srodrigc memcpy(namest->name, args->name, args->namelen); 983153323Srodrigc xfs_da_log_buf(args->trans, bp, 984153323Srodrigc XFS_DA_LOGRANGE(leaf, namest, XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry))); 985153323Srodrigc 986153323Srodrigc /* 987153323Srodrigc * Update the control info for this leaf node 988153323Srodrigc */ 989153323Srodrigc if (INT_GET(entry->nameidx, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT)) 990153323Srodrigc INT_COPY(hdr->firstused, entry->nameidx, ARCH_CONVERT); 991153323Srodrigc ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr))); 992153323Srodrigc tmp = (INT_GET(hdr->count, ARCH_CONVERT)-1) * (uint)sizeof(xfs_dir_leaf_entry_t) 993153323Srodrigc + (uint)sizeof(xfs_dir_leaf_hdr_t); 994153323Srodrigc map = &hdr->freemap[0]; 995153323Srodrigc for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) { 996153323Srodrigc if (INT_GET(map->base, ARCH_CONVERT) == tmp) { 997153323Srodrigc INT_MOD(map->base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t)); 998153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t))); 999153323Srodrigc } 1000153323Srodrigc } 1001153323Srodrigc INT_MOD(hdr->namebytes, ARCH_CONVERT, args->namelen); 1002153323Srodrigc xfs_da_log_buf(args->trans, bp, 1003153323Srodrigc XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr))); 1004153323Srodrigc} 1005153323Srodrigc 1006153323Srodrigc/* 1007153323Srodrigc * Garbage collect a leaf directory block by copying it to a new buffer. 1008153323Srodrigc */ 1009153323SrodrigcSTATIC int 1010153323Srodrigcxfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *bp, int musthave, 1011153323Srodrigc int justcheck) 1012153323Srodrigc{ 1013153323Srodrigc xfs_dir_leafblock_t *leaf_s, *leaf_d; 1014153323Srodrigc xfs_dir_leaf_hdr_t *hdr_s, *hdr_d; 1015153323Srodrigc xfs_mount_t *mp; 1016153323Srodrigc char *tmpbuffer; 1017153323Srodrigc char *tmpbuffer2=NULL; 1018153323Srodrigc int rval; 1019153323Srodrigc int lbsize; 1020153323Srodrigc 1021153323Srodrigc mp = trans->t_mountp; 1022153323Srodrigc lbsize = XFS_LBSIZE(mp); 1023153323Srodrigc tmpbuffer = kmem_alloc(lbsize, KM_SLEEP); 1024153323Srodrigc ASSERT(tmpbuffer != NULL); 1025153323Srodrigc memcpy(tmpbuffer, bp->data, lbsize); 1026153323Srodrigc 1027153323Srodrigc /* 1028153323Srodrigc * Make a second copy in case xfs_dir_leaf_moveents() 1029153323Srodrigc * below destroys the original. 1030153323Srodrigc */ 1031153323Srodrigc if (musthave || justcheck) { 1032153323Srodrigc tmpbuffer2 = kmem_alloc(lbsize, KM_SLEEP); 1033153323Srodrigc memcpy(tmpbuffer2, bp->data, lbsize); 1034153323Srodrigc } 1035153323Srodrigc memset(bp->data, 0, lbsize); 1036153323Srodrigc 1037153323Srodrigc /* 1038153323Srodrigc * Copy basic information 1039153323Srodrigc */ 1040153323Srodrigc leaf_s = (xfs_dir_leafblock_t *)tmpbuffer; 1041153323Srodrigc leaf_d = bp->data; 1042153323Srodrigc hdr_s = &leaf_s->hdr; 1043153323Srodrigc hdr_d = &leaf_d->hdr; 1044153323Srodrigc hdr_d->info = hdr_s->info; /* struct copy */ 1045153323Srodrigc INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize); 1046159451Srodrigc if (!hdr_d->firstused) 1047153323Srodrigc INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize - 1); 1048159451Srodrigc hdr_d->namebytes = 0; 1049159451Srodrigc hdr_d->count = 0; 1050153323Srodrigc hdr_d->holes = 0; 1051153323Srodrigc INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t)); 1052153323Srodrigc INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT)); 1053153323Srodrigc 1054153323Srodrigc /* 1055153323Srodrigc * Copy all entry's in the same (sorted) order, 1056153323Srodrigc * but allocate filenames packed and in sequence. 1057153323Srodrigc * This changes the source (leaf_s) as well. 1058153323Srodrigc */ 1059153323Srodrigc xfs_dir_leaf_moveents(leaf_s, 0, leaf_d, 0, (int)INT_GET(hdr_s->count, ARCH_CONVERT), mp); 1060153323Srodrigc 1061153323Srodrigc if (musthave && INT_GET(hdr_d->freemap[0].size, ARCH_CONVERT) < musthave) 1062153323Srodrigc rval = XFS_ERROR(ENOSPC); 1063153323Srodrigc else 1064153323Srodrigc rval = 0; 1065153323Srodrigc 1066153323Srodrigc if (justcheck || rval == ENOSPC) { 1067153323Srodrigc ASSERT(tmpbuffer2); 1068153323Srodrigc memcpy(bp->data, tmpbuffer2, lbsize); 1069153323Srodrigc } else { 1070153323Srodrigc xfs_da_log_buf(trans, bp, 0, lbsize - 1); 1071153323Srodrigc } 1072153323Srodrigc 1073153323Srodrigc kmem_free(tmpbuffer, lbsize); 1074153323Srodrigc if (musthave || justcheck) 1075153323Srodrigc kmem_free(tmpbuffer2, lbsize); 1076159451Srodrigc return rval; 1077153323Srodrigc} 1078153323Srodrigc 1079153323Srodrigc/* 1080153323Srodrigc * Redistribute the directory entries between two leaf nodes, 1081153323Srodrigc * taking into account the size of the new entry. 1082153323Srodrigc * 1083153323Srodrigc * NOTE: if new block is empty, then it will get the upper half of old block. 1084153323Srodrigc */ 1085153323SrodrigcSTATIC void 1086153323Srodrigcxfs_dir_leaf_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1, 1087153323Srodrigc xfs_da_state_blk_t *blk2) 1088153323Srodrigc{ 1089153323Srodrigc xfs_da_state_blk_t *tmp_blk; 1090153323Srodrigc xfs_dir_leafblock_t *leaf1, *leaf2; 1091153323Srodrigc xfs_dir_leaf_hdr_t *hdr1, *hdr2; 1092153323Srodrigc int count, totallen, max, space, swap; 1093153323Srodrigc 1094153323Srodrigc /* 1095153323Srodrigc * Set up environment. 1096153323Srodrigc */ 1097153323Srodrigc ASSERT(blk1->magic == XFS_DIR_LEAF_MAGIC); 1098153323Srodrigc ASSERT(blk2->magic == XFS_DIR_LEAF_MAGIC); 1099153323Srodrigc leaf1 = blk1->bp->data; 1100153323Srodrigc leaf2 = blk2->bp->data; 1101159451Srodrigc ASSERT(be16_to_cpu(leaf1->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1102159451Srodrigc ASSERT(be16_to_cpu(leaf2->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1103153323Srodrigc 1104153323Srodrigc /* 1105153323Srodrigc * Check ordering of blocks, reverse if it makes things simpler. 1106153323Srodrigc */ 1107153323Srodrigc swap = 0; 1108153323Srodrigc if (xfs_dir_leaf_order(blk1->bp, blk2->bp)) { 1109153323Srodrigc tmp_blk = blk1; 1110153323Srodrigc blk1 = blk2; 1111153323Srodrigc blk2 = tmp_blk; 1112153323Srodrigc leaf1 = blk1->bp->data; 1113153323Srodrigc leaf2 = blk2->bp->data; 1114153323Srodrigc swap = 1; 1115153323Srodrigc } 1116153323Srodrigc hdr1 = &leaf1->hdr; 1117153323Srodrigc hdr2 = &leaf2->hdr; 1118153323Srodrigc 1119153323Srodrigc /* 1120153323Srodrigc * Examine entries until we reduce the absolute difference in 1121153323Srodrigc * byte usage between the two blocks to a minimum. Then get 1122153323Srodrigc * the direction to copy and the number of elements to move. 1123153323Srodrigc */ 1124153323Srodrigc state->inleaf = xfs_dir_leaf_figure_balance(state, blk1, blk2, 1125153323Srodrigc &count, &totallen); 1126153323Srodrigc if (swap) 1127153323Srodrigc state->inleaf = !state->inleaf; 1128153323Srodrigc 1129153323Srodrigc /* 1130153323Srodrigc * Move any entries required from leaf to leaf: 1131153323Srodrigc */ 1132153323Srodrigc if (count < INT_GET(hdr1->count, ARCH_CONVERT)) { 1133153323Srodrigc /* 1134153323Srodrigc * Figure the total bytes to be added to the destination leaf. 1135153323Srodrigc */ 1136153323Srodrigc count = INT_GET(hdr1->count, ARCH_CONVERT) - count; /* number entries being moved */ 1137153323Srodrigc space = INT_GET(hdr1->namebytes, ARCH_CONVERT) - totallen; 1138153323Srodrigc space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1); 1139153323Srodrigc space += count * (uint)sizeof(xfs_dir_leaf_entry_t); 1140153323Srodrigc 1141153323Srodrigc /* 1142153323Srodrigc * leaf2 is the destination, compact it if it looks tight. 1143153323Srodrigc */ 1144153323Srodrigc max = INT_GET(hdr2->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t); 1145153323Srodrigc max -= INT_GET(hdr2->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t); 1146153323Srodrigc if (space > max) { 1147153323Srodrigc xfs_dir_leaf_compact(state->args->trans, blk2->bp, 1148153323Srodrigc 0, 0); 1149153323Srodrigc } 1150153323Srodrigc 1151153323Srodrigc /* 1152153323Srodrigc * Move high entries from leaf1 to low end of leaf2. 1153153323Srodrigc */ 1154153323Srodrigc xfs_dir_leaf_moveents(leaf1, INT_GET(hdr1->count, ARCH_CONVERT) - count, 1155153323Srodrigc leaf2, 0, count, state->mp); 1156153323Srodrigc 1157153323Srodrigc xfs_da_log_buf(state->args->trans, blk1->bp, 0, 1158153323Srodrigc state->blocksize-1); 1159153323Srodrigc xfs_da_log_buf(state->args->trans, blk2->bp, 0, 1160153323Srodrigc state->blocksize-1); 1161153323Srodrigc 1162153323Srodrigc } else if (count > INT_GET(hdr1->count, ARCH_CONVERT)) { 1163153323Srodrigc /* 1164153323Srodrigc * Figure the total bytes to be added to the destination leaf. 1165153323Srodrigc */ 1166153323Srodrigc count -= INT_GET(hdr1->count, ARCH_CONVERT); /* number entries being moved */ 1167153323Srodrigc space = totallen - INT_GET(hdr1->namebytes, ARCH_CONVERT); 1168153323Srodrigc space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1); 1169153323Srodrigc space += count * (uint)sizeof(xfs_dir_leaf_entry_t); 1170153323Srodrigc 1171153323Srodrigc /* 1172153323Srodrigc * leaf1 is the destination, compact it if it looks tight. 1173153323Srodrigc */ 1174153323Srodrigc max = INT_GET(hdr1->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t); 1175153323Srodrigc max -= INT_GET(hdr1->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t); 1176153323Srodrigc if (space > max) { 1177153323Srodrigc xfs_dir_leaf_compact(state->args->trans, blk1->bp, 1178153323Srodrigc 0, 0); 1179153323Srodrigc } 1180153323Srodrigc 1181153323Srodrigc /* 1182153323Srodrigc * Move low entries from leaf2 to high end of leaf1. 1183153323Srodrigc */ 1184153323Srodrigc xfs_dir_leaf_moveents(leaf2, 0, leaf1, (int)INT_GET(hdr1->count, ARCH_CONVERT), 1185153323Srodrigc count, state->mp); 1186153323Srodrigc 1187153323Srodrigc xfs_da_log_buf(state->args->trans, blk1->bp, 0, 1188153323Srodrigc state->blocksize-1); 1189153323Srodrigc xfs_da_log_buf(state->args->trans, blk2->bp, 0, 1190153323Srodrigc state->blocksize-1); 1191153323Srodrigc } 1192153323Srodrigc 1193153323Srodrigc /* 1194153323Srodrigc * Copy out last hashval in each block for B-tree code. 1195153323Srodrigc */ 1196153323Srodrigc blk1->hashval = INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT); 1197153323Srodrigc blk2->hashval = INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT); 1198153323Srodrigc 1199153323Srodrigc /* 1200153323Srodrigc * Adjust the expected index for insertion. 1201153323Srodrigc * GROT: this doesn't work unless blk2 was originally empty. 1202153323Srodrigc */ 1203153323Srodrigc if (!state->inleaf) { 1204153323Srodrigc blk2->index = blk1->index - INT_GET(leaf1->hdr.count, ARCH_CONVERT); 1205153323Srodrigc } 1206153323Srodrigc} 1207153323Srodrigc 1208153323Srodrigc/* 1209153323Srodrigc * Examine entries until we reduce the absolute difference in 1210153323Srodrigc * byte usage between the two blocks to a minimum. 1211153323Srodrigc * GROT: Is this really necessary? With other than a 512 byte blocksize, 1212153323Srodrigc * GROT: there will always be enough room in either block for a new entry. 1213153323Srodrigc * GROT: Do a double-split for this case? 1214153323Srodrigc */ 1215153323SrodrigcSTATIC int 1216153323Srodrigcxfs_dir_leaf_figure_balance(xfs_da_state_t *state, 1217153323Srodrigc xfs_da_state_blk_t *blk1, 1218153323Srodrigc xfs_da_state_blk_t *blk2, 1219153323Srodrigc int *countarg, int *namebytesarg) 1220153323Srodrigc{ 1221153323Srodrigc xfs_dir_leafblock_t *leaf1, *leaf2; 1222153323Srodrigc xfs_dir_leaf_hdr_t *hdr1, *hdr2; 1223153323Srodrigc xfs_dir_leaf_entry_t *entry; 1224153323Srodrigc int count, max, totallen, half; 1225153323Srodrigc int lastdelta, foundit, tmp; 1226153323Srodrigc 1227153323Srodrigc /* 1228153323Srodrigc * Set up environment. 1229153323Srodrigc */ 1230153323Srodrigc leaf1 = blk1->bp->data; 1231153323Srodrigc leaf2 = blk2->bp->data; 1232153323Srodrigc hdr1 = &leaf1->hdr; 1233153323Srodrigc hdr2 = &leaf2->hdr; 1234153323Srodrigc foundit = 0; 1235153323Srodrigc totallen = 0; 1236153323Srodrigc 1237153323Srodrigc /* 1238153323Srodrigc * Examine entries until we reduce the absolute difference in 1239153323Srodrigc * byte usage between the two blocks to a minimum. 1240153323Srodrigc */ 1241153323Srodrigc max = INT_GET(hdr1->count, ARCH_CONVERT) + INT_GET(hdr2->count, ARCH_CONVERT); 1242153323Srodrigc half = (max+1) * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1); 1243153323Srodrigc half += INT_GET(hdr1->namebytes, ARCH_CONVERT) + INT_GET(hdr2->namebytes, ARCH_CONVERT) + state->args->namelen; 1244153323Srodrigc half /= 2; 1245153323Srodrigc lastdelta = state->blocksize; 1246153323Srodrigc entry = &leaf1->entries[0]; 1247153323Srodrigc for (count = 0; count < max; entry++, count++) { 1248153323Srodrigc 1249153323Srodrigc#define XFS_DIR_ABS(A) (((A) < 0) ? -(A) : (A)) 1250153323Srodrigc /* 1251153323Srodrigc * The new entry is in the first block, account for it. 1252153323Srodrigc */ 1253153323Srodrigc if (count == blk1->index) { 1254153323Srodrigc tmp = totallen + (uint)sizeof(*entry) 1255153323Srodrigc + XFS_DIR_LEAF_ENTSIZE_BYNAME(state->args->namelen); 1256153323Srodrigc if (XFS_DIR_ABS(half - tmp) > lastdelta) 1257153323Srodrigc break; 1258153323Srodrigc lastdelta = XFS_DIR_ABS(half - tmp); 1259153323Srodrigc totallen = tmp; 1260153323Srodrigc foundit = 1; 1261153323Srodrigc } 1262153323Srodrigc 1263153323Srodrigc /* 1264153323Srodrigc * Wrap around into the second block if necessary. 1265153323Srodrigc */ 1266153323Srodrigc if (count == INT_GET(hdr1->count, ARCH_CONVERT)) { 1267153323Srodrigc leaf1 = leaf2; 1268153323Srodrigc entry = &leaf1->entries[0]; 1269153323Srodrigc } 1270153323Srodrigc 1271153323Srodrigc /* 1272153323Srodrigc * Figure out if next leaf entry would be too much. 1273153323Srodrigc */ 1274153323Srodrigc tmp = totallen + (uint)sizeof(*entry) 1275153323Srodrigc + XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry); 1276153323Srodrigc if (XFS_DIR_ABS(half - tmp) > lastdelta) 1277153323Srodrigc break; 1278153323Srodrigc lastdelta = XFS_DIR_ABS(half - tmp); 1279153323Srodrigc totallen = tmp; 1280153323Srodrigc#undef XFS_DIR_ABS 1281153323Srodrigc } 1282153323Srodrigc 1283153323Srodrigc /* 1284153323Srodrigc * Calculate the number of namebytes that will end up in lower block. 1285153323Srodrigc * If new entry not in lower block, fix up the count. 1286153323Srodrigc */ 1287153323Srodrigc totallen -= 1288153323Srodrigc count * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1); 1289153323Srodrigc if (foundit) { 1290153323Srodrigc totallen -= (sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1) + 1291153323Srodrigc state->args->namelen; 1292153323Srodrigc } 1293153323Srodrigc 1294153323Srodrigc *countarg = count; 1295153323Srodrigc *namebytesarg = totallen; 1296159451Srodrigc return foundit; 1297153323Srodrigc} 1298153323Srodrigc 1299153323Srodrigc/*======================================================================== 1300153323Srodrigc * Routines used for shrinking the Btree. 1301153323Srodrigc *========================================================================*/ 1302153323Srodrigc 1303153323Srodrigc/* 1304153323Srodrigc * Check a leaf block and its neighbors to see if the block should be 1305153323Srodrigc * collapsed into one or the other neighbor. Always keep the block 1306153323Srodrigc * with the smaller block number. 1307153323Srodrigc * If the current block is over 50% full, don't try to join it, return 0. 1308153323Srodrigc * If the block is empty, fill in the state structure and return 2. 1309153323Srodrigc * If it can be collapsed, fill in the state structure and return 1. 1310153323Srodrigc * If nothing can be done, return 0. 1311153323Srodrigc */ 1312153323Srodrigcint 1313153323Srodrigcxfs_dir_leaf_toosmall(xfs_da_state_t *state, int *action) 1314153323Srodrigc{ 1315153323Srodrigc xfs_dir_leafblock_t *leaf; 1316153323Srodrigc xfs_da_state_blk_t *blk; 1317153323Srodrigc xfs_da_blkinfo_t *info; 1318153323Srodrigc int count, bytes, forward, error, retval, i; 1319153323Srodrigc xfs_dablk_t blkno; 1320153323Srodrigc xfs_dabuf_t *bp; 1321153323Srodrigc 1322153323Srodrigc /* 1323153323Srodrigc * Check for the degenerate case of the block being over 50% full. 1324153323Srodrigc * If so, it's not worth even looking to see if we might be able 1325153323Srodrigc * to coalesce with a sibling. 1326153323Srodrigc */ 1327153323Srodrigc blk = &state->path.blk[ state->path.active-1 ]; 1328153323Srodrigc info = blk->bp->data; 1329159451Srodrigc ASSERT(be16_to_cpu(info->magic) == XFS_DIR_LEAF_MAGIC); 1330153323Srodrigc leaf = (xfs_dir_leafblock_t *)info; 1331153323Srodrigc count = INT_GET(leaf->hdr.count, ARCH_CONVERT); 1332153323Srodrigc bytes = (uint)sizeof(xfs_dir_leaf_hdr_t) + 1333153323Srodrigc count * (uint)sizeof(xfs_dir_leaf_entry_t) + 1334153323Srodrigc count * ((uint)sizeof(xfs_dir_leaf_name_t)-1) + 1335153323Srodrigc INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); 1336153323Srodrigc if (bytes > (state->blocksize >> 1)) { 1337153323Srodrigc *action = 0; /* blk over 50%, don't try to join */ 1338159451Srodrigc return 0; 1339153323Srodrigc } 1340153323Srodrigc 1341153323Srodrigc /* 1342153323Srodrigc * Check for the degenerate case of the block being empty. 1343153323Srodrigc * If the block is empty, we'll simply delete it, no need to 1344159451Srodrigc * coalesce it with a sibling block. We choose (arbitrarily) 1345153323Srodrigc * to merge with the forward block unless it is NULL. 1346153323Srodrigc */ 1347153323Srodrigc if (count == 0) { 1348153323Srodrigc /* 1349153323Srodrigc * Make altpath point to the block we want to keep and 1350153323Srodrigc * path point to the block we want to drop (this one). 1351153323Srodrigc */ 1352159451Srodrigc forward = (info->forw != 0); 1353153323Srodrigc memcpy(&state->altpath, &state->path, sizeof(state->path)); 1354153323Srodrigc error = xfs_da_path_shift(state, &state->altpath, forward, 1355153323Srodrigc 0, &retval); 1356153323Srodrigc if (error) 1357159451Srodrigc return error; 1358153323Srodrigc if (retval) { 1359153323Srodrigc *action = 0; 1360153323Srodrigc } else { 1361153323Srodrigc *action = 2; 1362153323Srodrigc } 1363159451Srodrigc return 0; 1364153323Srodrigc } 1365153323Srodrigc 1366153323Srodrigc /* 1367153323Srodrigc * Examine each sibling block to see if we can coalesce with 1368153323Srodrigc * at least 25% free space to spare. We need to figure out 1369153323Srodrigc * whether to merge with the forward or the backward block. 1370153323Srodrigc * We prefer coalescing with the lower numbered sibling so as 1371153323Srodrigc * to shrink a directory over time. 1372153323Srodrigc */ 1373159451Srodrigc forward = (be32_to_cpu(info->forw) < be32_to_cpu(info->back)); /* start with smaller blk num */ 1374153323Srodrigc for (i = 0; i < 2; forward = !forward, i++) { 1375153323Srodrigc if (forward) 1376159451Srodrigc blkno = be32_to_cpu(info->forw); 1377153323Srodrigc else 1378159451Srodrigc blkno = be32_to_cpu(info->back); 1379153323Srodrigc if (blkno == 0) 1380153323Srodrigc continue; 1381153323Srodrigc error = xfs_da_read_buf(state->args->trans, state->args->dp, 1382153323Srodrigc blkno, -1, &bp, 1383153323Srodrigc XFS_DATA_FORK); 1384153323Srodrigc if (error) 1385159451Srodrigc return error; 1386153323Srodrigc ASSERT(bp != NULL); 1387153323Srodrigc 1388153323Srodrigc leaf = (xfs_dir_leafblock_t *)info; 1389153323Srodrigc count = INT_GET(leaf->hdr.count, ARCH_CONVERT); 1390153323Srodrigc bytes = state->blocksize - (state->blocksize>>2); 1391153323Srodrigc bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); 1392153323Srodrigc leaf = bp->data; 1393159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1394153323Srodrigc count += INT_GET(leaf->hdr.count, ARCH_CONVERT); 1395153323Srodrigc bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); 1396153323Srodrigc bytes -= count * ((uint)sizeof(xfs_dir_leaf_name_t) - 1); 1397153323Srodrigc bytes -= count * (uint)sizeof(xfs_dir_leaf_entry_t); 1398153323Srodrigc bytes -= (uint)sizeof(xfs_dir_leaf_hdr_t); 1399153323Srodrigc if (bytes >= 0) 1400153323Srodrigc break; /* fits with at least 25% to spare */ 1401153323Srodrigc 1402153323Srodrigc xfs_da_brelse(state->args->trans, bp); 1403153323Srodrigc } 1404153323Srodrigc if (i >= 2) { 1405153323Srodrigc *action = 0; 1406159451Srodrigc return 0; 1407153323Srodrigc } 1408153323Srodrigc xfs_da_buf_done(bp); 1409153323Srodrigc 1410153323Srodrigc /* 1411153323Srodrigc * Make altpath point to the block we want to keep (the lower 1412153323Srodrigc * numbered block) and path point to the block we want to drop. 1413153323Srodrigc */ 1414153323Srodrigc memcpy(&state->altpath, &state->path, sizeof(state->path)); 1415153323Srodrigc if (blkno < blk->blkno) { 1416153323Srodrigc error = xfs_da_path_shift(state, &state->altpath, forward, 1417153323Srodrigc 0, &retval); 1418153323Srodrigc } else { 1419153323Srodrigc error = xfs_da_path_shift(state, &state->path, forward, 1420153323Srodrigc 0, &retval); 1421153323Srodrigc } 1422153323Srodrigc if (error) 1423159451Srodrigc return error; 1424153323Srodrigc if (retval) { 1425153323Srodrigc *action = 0; 1426153323Srodrigc } else { 1427153323Srodrigc *action = 1; 1428153323Srodrigc } 1429159451Srodrigc return 0; 1430153323Srodrigc} 1431153323Srodrigc 1432153323Srodrigc/* 1433153323Srodrigc * Remove a name from the leaf directory structure. 1434153323Srodrigc * 1435153323Srodrigc * Return 1 if leaf is less than 37% full, 0 if >= 37% full. 1436153323Srodrigc * If two leaves are 37% full, when combined they will leave 25% free. 1437153323Srodrigc */ 1438153323Srodrigcint 1439153323Srodrigcxfs_dir_leaf_remove(xfs_trans_t *trans, xfs_dabuf_t *bp, int index) 1440153323Srodrigc{ 1441153323Srodrigc xfs_dir_leafblock_t *leaf; 1442153323Srodrigc xfs_dir_leaf_hdr_t *hdr; 1443153323Srodrigc xfs_dir_leaf_map_t *map; 1444153323Srodrigc xfs_dir_leaf_entry_t *entry; 1445153323Srodrigc xfs_dir_leaf_name_t *namest; 1446153323Srodrigc int before, after, smallest, entsize; 1447153323Srodrigc int tablesize, tmp, i; 1448153323Srodrigc xfs_mount_t *mp; 1449153323Srodrigc 1450153323Srodrigc leaf = bp->data; 1451159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1452153323Srodrigc hdr = &leaf->hdr; 1453153323Srodrigc mp = trans->t_mountp; 1454153323Srodrigc ASSERT((INT_GET(hdr->count, ARCH_CONVERT) > 0) && (INT_GET(hdr->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8))); 1455153323Srodrigc ASSERT((index >= 0) && (index < INT_GET(hdr->count, ARCH_CONVERT))); 1456153323Srodrigc ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr))); 1457153323Srodrigc entry = &leaf->entries[index]; 1458153323Srodrigc ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT)); 1459153323Srodrigc ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp)); 1460153323Srodrigc 1461153323Srodrigc /* 1462153323Srodrigc * Scan through free region table: 1463153323Srodrigc * check for adjacency of free'd entry with an existing one, 1464153323Srodrigc * find smallest free region in case we need to replace it, 1465153323Srodrigc * adjust any map that borders the entry table, 1466153323Srodrigc */ 1467153323Srodrigc tablesize = INT_GET(hdr->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t) 1468153323Srodrigc + (uint)sizeof(xfs_dir_leaf_hdr_t); 1469153323Srodrigc map = &hdr->freemap[0]; 1470153323Srodrigc tmp = INT_GET(map->size, ARCH_CONVERT); 1471153323Srodrigc before = after = -1; 1472153323Srodrigc smallest = XFS_DIR_LEAF_MAPSIZE - 1; 1473153323Srodrigc entsize = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry); 1474153323Srodrigc for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) { 1475153323Srodrigc ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp)); 1476153323Srodrigc ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp)); 1477153323Srodrigc if (INT_GET(map->base, ARCH_CONVERT) == tablesize) { 1478153323Srodrigc INT_MOD(map->base, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t))); 1479153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t)); 1480153323Srodrigc } 1481153323Srodrigc 1482153323Srodrigc if ((INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT)) == INT_GET(entry->nameidx, ARCH_CONVERT)) { 1483153323Srodrigc before = i; 1484153323Srodrigc } else if (INT_GET(map->base, ARCH_CONVERT) == (INT_GET(entry->nameidx, ARCH_CONVERT) + entsize)) { 1485153323Srodrigc after = i; 1486153323Srodrigc } else if (INT_GET(map->size, ARCH_CONVERT) < tmp) { 1487153323Srodrigc tmp = INT_GET(map->size, ARCH_CONVERT); 1488153323Srodrigc smallest = i; 1489153323Srodrigc } 1490153323Srodrigc } 1491153323Srodrigc 1492153323Srodrigc /* 1493153323Srodrigc * Coalesce adjacent freemap regions, 1494153323Srodrigc * or replace the smallest region. 1495153323Srodrigc */ 1496153323Srodrigc if ((before >= 0) || (after >= 0)) { 1497153323Srodrigc if ((before >= 0) && (after >= 0)) { 1498153323Srodrigc map = &hdr->freemap[before]; 1499153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, entsize); 1500153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, INT_GET(hdr->freemap[after].size, ARCH_CONVERT)); 1501159451Srodrigc hdr->freemap[after].base = 0; 1502159451Srodrigc hdr->freemap[after].size = 0; 1503153323Srodrigc } else if (before >= 0) { 1504153323Srodrigc map = &hdr->freemap[before]; 1505153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, entsize); 1506153323Srodrigc } else { 1507153323Srodrigc map = &hdr->freemap[after]; 1508153323Srodrigc INT_COPY(map->base, entry->nameidx, ARCH_CONVERT); 1509153323Srodrigc INT_MOD(map->size, ARCH_CONVERT, entsize); 1510153323Srodrigc } 1511153323Srodrigc } else { 1512153323Srodrigc /* 1513153323Srodrigc * Replace smallest region (if it is smaller than free'd entry) 1514153323Srodrigc */ 1515153323Srodrigc map = &hdr->freemap[smallest]; 1516153323Srodrigc if (INT_GET(map->size, ARCH_CONVERT) < entsize) { 1517153323Srodrigc INT_COPY(map->base, entry->nameidx, ARCH_CONVERT); 1518153323Srodrigc INT_SET(map->size, ARCH_CONVERT, entsize); 1519153323Srodrigc } 1520153323Srodrigc } 1521153323Srodrigc 1522153323Srodrigc /* 1523153323Srodrigc * Did we remove the first entry? 1524153323Srodrigc */ 1525153323Srodrigc if (INT_GET(entry->nameidx, ARCH_CONVERT) == INT_GET(hdr->firstused, ARCH_CONVERT)) 1526153323Srodrigc smallest = 1; 1527153323Srodrigc else 1528153323Srodrigc smallest = 0; 1529153323Srodrigc 1530153323Srodrigc /* 1531153323Srodrigc * Compress the remaining entries and zero out the removed stuff. 1532153323Srodrigc */ 1533153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); 1534153323Srodrigc memset((char *)namest, 0, entsize); 1535153323Srodrigc xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, namest, entsize)); 1536153323Srodrigc 1537153323Srodrigc INT_MOD(hdr->namebytes, ARCH_CONVERT, -(entry->namelen)); 1538153323Srodrigc tmp = (INT_GET(hdr->count, ARCH_CONVERT) - index) * (uint)sizeof(xfs_dir_leaf_entry_t); 1539153323Srodrigc memmove(entry, entry + 1, tmp); 1540153323Srodrigc INT_MOD(hdr->count, ARCH_CONVERT, -1); 1541153323Srodrigc xfs_da_log_buf(trans, bp, 1542153323Srodrigc XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry))); 1543153323Srodrigc entry = &leaf->entries[INT_GET(hdr->count, ARCH_CONVERT)]; 1544153323Srodrigc memset((char *)entry, 0, sizeof(xfs_dir_leaf_entry_t)); 1545153323Srodrigc 1546153323Srodrigc /* 1547153323Srodrigc * If we removed the first entry, re-find the first used byte 1548153323Srodrigc * in the name area. Note that if the entry was the "firstused", 1549153323Srodrigc * then we don't have a "hole" in our block resulting from 1550153323Srodrigc * removing the name. 1551153323Srodrigc */ 1552153323Srodrigc if (smallest) { 1553153323Srodrigc tmp = XFS_LBSIZE(mp); 1554153323Srodrigc entry = &leaf->entries[0]; 1555153323Srodrigc for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) { 1556153323Srodrigc ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT)); 1557153323Srodrigc ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp)); 1558153323Srodrigc if (INT_GET(entry->nameidx, ARCH_CONVERT) < tmp) 1559153323Srodrigc tmp = INT_GET(entry->nameidx, ARCH_CONVERT); 1560153323Srodrigc } 1561153323Srodrigc INT_SET(hdr->firstused, ARCH_CONVERT, tmp); 1562159451Srodrigc if (!hdr->firstused) 1563153323Srodrigc INT_SET(hdr->firstused, ARCH_CONVERT, tmp - 1); 1564153323Srodrigc } else { 1565153323Srodrigc hdr->holes = 1; /* mark as needing compaction */ 1566153323Srodrigc } 1567153323Srodrigc 1568153323Srodrigc xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr))); 1569153323Srodrigc 1570153323Srodrigc /* 1571153323Srodrigc * Check if leaf is less than 50% full, caller may want to 1572153323Srodrigc * "join" the leaf with a sibling if so. 1573153323Srodrigc */ 1574153323Srodrigc tmp = (uint)sizeof(xfs_dir_leaf_hdr_t); 1575153323Srodrigc tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t); 1576153323Srodrigc tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * ((uint)sizeof(xfs_dir_leaf_name_t) - 1); 1577153323Srodrigc tmp += INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); 1578153323Srodrigc if (tmp < mp->m_dir_magicpct) 1579159451Srodrigc return 1; /* leaf is < 37% full */ 1580159451Srodrigc return 0; 1581153323Srodrigc} 1582153323Srodrigc 1583153323Srodrigc/* 1584153323Srodrigc * Move all the directory entries from drop_leaf into save_leaf. 1585153323Srodrigc */ 1586153323Srodrigcvoid 1587153323Srodrigcxfs_dir_leaf_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk, 1588153323Srodrigc xfs_da_state_blk_t *save_blk) 1589153323Srodrigc{ 1590153323Srodrigc xfs_dir_leafblock_t *drop_leaf, *save_leaf, *tmp_leaf; 1591153323Srodrigc xfs_dir_leaf_hdr_t *drop_hdr, *save_hdr, *tmp_hdr; 1592153323Srodrigc xfs_mount_t *mp; 1593153323Srodrigc char *tmpbuffer; 1594153323Srodrigc 1595153323Srodrigc /* 1596153323Srodrigc * Set up environment. 1597153323Srodrigc */ 1598153323Srodrigc mp = state->mp; 1599153323Srodrigc ASSERT(drop_blk->magic == XFS_DIR_LEAF_MAGIC); 1600153323Srodrigc ASSERT(save_blk->magic == XFS_DIR_LEAF_MAGIC); 1601153323Srodrigc drop_leaf = drop_blk->bp->data; 1602153323Srodrigc save_leaf = save_blk->bp->data; 1603159451Srodrigc ASSERT(be16_to_cpu(drop_leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1604159451Srodrigc ASSERT(be16_to_cpu(save_leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1605153323Srodrigc drop_hdr = &drop_leaf->hdr; 1606153323Srodrigc save_hdr = &save_leaf->hdr; 1607153323Srodrigc 1608153323Srodrigc /* 1609153323Srodrigc * Save last hashval from dying block for later Btree fixup. 1610153323Srodrigc */ 1611153323Srodrigc drop_blk->hashval = INT_GET(drop_leaf->entries[ drop_leaf->hdr.count-1 ].hashval, ARCH_CONVERT); 1612153323Srodrigc 1613153323Srodrigc /* 1614153323Srodrigc * Check if we need a temp buffer, or can we do it in place. 1615153323Srodrigc * Note that we don't check "leaf" for holes because we will 1616153323Srodrigc * always be dropping it, toosmall() decided that for us already. 1617153323Srodrigc */ 1618153323Srodrigc if (save_hdr->holes == 0) { 1619153323Srodrigc /* 1620153323Srodrigc * dest leaf has no holes, so we add there. May need 1621153323Srodrigc * to make some room in the entry array. 1622153323Srodrigc */ 1623153323Srodrigc if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) { 1624153323Srodrigc xfs_dir_leaf_moveents(drop_leaf, 0, save_leaf, 0, 1625153323Srodrigc (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); 1626153323Srodrigc } else { 1627153323Srodrigc xfs_dir_leaf_moveents(drop_leaf, 0, 1628153323Srodrigc save_leaf, INT_GET(save_hdr->count, ARCH_CONVERT), 1629153323Srodrigc (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); 1630153323Srodrigc } 1631153323Srodrigc } else { 1632153323Srodrigc /* 1633153323Srodrigc * Destination has holes, so we make a temporary copy 1634153323Srodrigc * of the leaf and add them both to that. 1635153323Srodrigc */ 1636153323Srodrigc tmpbuffer = kmem_alloc(state->blocksize, KM_SLEEP); 1637153323Srodrigc ASSERT(tmpbuffer != NULL); 1638153323Srodrigc memset(tmpbuffer, 0, state->blocksize); 1639153323Srodrigc tmp_leaf = (xfs_dir_leafblock_t *)tmpbuffer; 1640153323Srodrigc tmp_hdr = &tmp_leaf->hdr; 1641153323Srodrigc tmp_hdr->info = save_hdr->info; /* struct copy */ 1642159451Srodrigc tmp_hdr->count = 0; 1643153323Srodrigc INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize); 1644159451Srodrigc if (!tmp_hdr->firstused) 1645153323Srodrigc INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize - 1); 1646159451Srodrigc tmp_hdr->namebytes = 0; 1647153323Srodrigc if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) { 1648153323Srodrigc xfs_dir_leaf_moveents(drop_leaf, 0, tmp_leaf, 0, 1649153323Srodrigc (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); 1650153323Srodrigc xfs_dir_leaf_moveents(save_leaf, 0, 1651153323Srodrigc tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT), 1652153323Srodrigc (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp); 1653153323Srodrigc } else { 1654153323Srodrigc xfs_dir_leaf_moveents(save_leaf, 0, tmp_leaf, 0, 1655153323Srodrigc (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp); 1656153323Srodrigc xfs_dir_leaf_moveents(drop_leaf, 0, 1657153323Srodrigc tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT), 1658153323Srodrigc (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); 1659153323Srodrigc } 1660153323Srodrigc memcpy(save_leaf, tmp_leaf, state->blocksize); 1661153323Srodrigc kmem_free(tmpbuffer, state->blocksize); 1662153323Srodrigc } 1663153323Srodrigc 1664153323Srodrigc xfs_da_log_buf(state->args->trans, save_blk->bp, 0, 1665153323Srodrigc state->blocksize - 1); 1666153323Srodrigc 1667153323Srodrigc /* 1668153323Srodrigc * Copy out last hashval in each block for B-tree code. 1669153323Srodrigc */ 1670153323Srodrigc save_blk->hashval = INT_GET(save_leaf->entries[ INT_GET(save_leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT); 1671153323Srodrigc} 1672153323Srodrigc 1673153323Srodrigc/*======================================================================== 1674153323Srodrigc * Routines used for finding things in the Btree. 1675153323Srodrigc *========================================================================*/ 1676153323Srodrigc 1677153323Srodrigc/* 1678153323Srodrigc * Look up a name in a leaf directory structure. 1679153323Srodrigc * This is the internal routine, it uses the caller's buffer. 1680153323Srodrigc * 1681153323Srodrigc * Note that duplicate keys are allowed, but only check within the 1682153323Srodrigc * current leaf node. The Btree code must check in adjacent leaf nodes. 1683153323Srodrigc * 1684153323Srodrigc * Return in *index the index into the entry[] array of either the found 1685153323Srodrigc * entry, or where the entry should have been (insert before that entry). 1686153323Srodrigc * 1687153323Srodrigc * Don't change the args->inumber unless we find the filename. 1688153323Srodrigc */ 1689153323Srodrigcint 1690153323Srodrigcxfs_dir_leaf_lookup_int(xfs_dabuf_t *bp, xfs_da_args_t *args, int *index) 1691153323Srodrigc{ 1692153323Srodrigc xfs_dir_leafblock_t *leaf; 1693153323Srodrigc xfs_dir_leaf_entry_t *entry; 1694153323Srodrigc xfs_dir_leaf_name_t *namest; 1695153323Srodrigc int probe, span; 1696153323Srodrigc xfs_dahash_t hashval; 1697153323Srodrigc 1698153323Srodrigc leaf = bp->data; 1699159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1700153323Srodrigc ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) < (XFS_LBSIZE(args->dp->i_mount)/8)); 1701153323Srodrigc 1702153323Srodrigc /* 1703153323Srodrigc * Binary search. (note: small blocks will skip this loop) 1704153323Srodrigc */ 1705153323Srodrigc hashval = args->hashval; 1706153323Srodrigc probe = span = INT_GET(leaf->hdr.count, ARCH_CONVERT) / 2; 1707153323Srodrigc for (entry = &leaf->entries[probe]; span > 4; 1708153323Srodrigc entry = &leaf->entries[probe]) { 1709153323Srodrigc span /= 2; 1710153323Srodrigc if (INT_GET(entry->hashval, ARCH_CONVERT) < hashval) 1711153323Srodrigc probe += span; 1712153323Srodrigc else if (INT_GET(entry->hashval, ARCH_CONVERT) > hashval) 1713153323Srodrigc probe -= span; 1714153323Srodrigc else 1715153323Srodrigc break; 1716153323Srodrigc } 1717153323Srodrigc ASSERT((probe >= 0) && \ 1718159451Srodrigc ((!leaf->hdr.count) || (probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)))); 1719153323Srodrigc ASSERT((span <= 4) || (INT_GET(entry->hashval, ARCH_CONVERT) == hashval)); 1720153323Srodrigc 1721153323Srodrigc /* 1722153323Srodrigc * Since we may have duplicate hashval's, find the first matching 1723153323Srodrigc * hashval in the leaf. 1724153323Srodrigc */ 1725153323Srodrigc while ((probe > 0) && (INT_GET(entry->hashval, ARCH_CONVERT) >= hashval)) { 1726153323Srodrigc entry--; 1727153323Srodrigc probe--; 1728153323Srodrigc } 1729153323Srodrigc while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) < hashval)) { 1730153323Srodrigc entry++; 1731153323Srodrigc probe++; 1732153323Srodrigc } 1733153323Srodrigc if ((probe == INT_GET(leaf->hdr.count, ARCH_CONVERT)) || (INT_GET(entry->hashval, ARCH_CONVERT) != hashval)) { 1734153323Srodrigc *index = probe; 1735153323Srodrigc ASSERT(args->oknoent); 1736159451Srodrigc return XFS_ERROR(ENOENT); 1737153323Srodrigc } 1738153323Srodrigc 1739153323Srodrigc /* 1740153323Srodrigc * Duplicate keys may be present, so search all of them for a match. 1741153323Srodrigc */ 1742153323Srodrigc while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) == hashval)) { 1743153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); 1744153323Srodrigc if (entry->namelen == args->namelen && 1745153323Srodrigc namest->name[0] == args->name[0] && 1746153323Srodrigc memcmp(args->name, namest->name, args->namelen) == 0) { 1747159451Srodrigc XFS_DIR_SF_GET_DIRINO(&namest->inumber, &args->inumber); 1748153323Srodrigc *index = probe; 1749159451Srodrigc return XFS_ERROR(EEXIST); 1750153323Srodrigc } 1751153323Srodrigc entry++; 1752153323Srodrigc probe++; 1753153323Srodrigc } 1754153323Srodrigc *index = probe; 1755153323Srodrigc ASSERT(probe == INT_GET(leaf->hdr.count, ARCH_CONVERT) || args->oknoent); 1756159451Srodrigc return XFS_ERROR(ENOENT); 1757153323Srodrigc} 1758153323Srodrigc 1759153323Srodrigc/*======================================================================== 1760153323Srodrigc * Utility routines. 1761153323Srodrigc *========================================================================*/ 1762153323Srodrigc 1763153323Srodrigc/* 1764153323Srodrigc * Move the indicated entries from one leaf to another. 1765153323Srodrigc * NOTE: this routine modifies both source and destination leaves. 1766153323Srodrigc */ 1767153323Srodrigc/* ARGSUSED */ 1768153323SrodrigcSTATIC void 1769153323Srodrigcxfs_dir_leaf_moveents(xfs_dir_leafblock_t *leaf_s, int start_s, 1770153323Srodrigc xfs_dir_leafblock_t *leaf_d, int start_d, 1771153323Srodrigc int count, xfs_mount_t *mp) 1772153323Srodrigc{ 1773153323Srodrigc xfs_dir_leaf_hdr_t *hdr_s, *hdr_d; 1774153323Srodrigc xfs_dir_leaf_entry_t *entry_s, *entry_d; 1775153323Srodrigc int tmp, i; 1776153323Srodrigc 1777153323Srodrigc /* 1778153323Srodrigc * Check for nothing to do. 1779153323Srodrigc */ 1780153323Srodrigc if (count == 0) 1781153323Srodrigc return; 1782153323Srodrigc 1783153323Srodrigc /* 1784153323Srodrigc * Set up environment. 1785153323Srodrigc */ 1786159451Srodrigc ASSERT(be16_to_cpu(leaf_s->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1787159451Srodrigc ASSERT(be16_to_cpu(leaf_d->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1788153323Srodrigc hdr_s = &leaf_s->hdr; 1789153323Srodrigc hdr_d = &leaf_d->hdr; 1790153323Srodrigc ASSERT((INT_GET(hdr_s->count, ARCH_CONVERT) > 0) && (INT_GET(hdr_s->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8))); 1791153323Srodrigc ASSERT(INT_GET(hdr_s->firstused, ARCH_CONVERT) >= 1792153323Srodrigc ((INT_GET(hdr_s->count, ARCH_CONVERT)*sizeof(*entry_s))+sizeof(*hdr_s))); 1793153323Srodrigc ASSERT(INT_GET(hdr_d->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)); 1794153323Srodrigc ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >= 1795153323Srodrigc ((INT_GET(hdr_d->count, ARCH_CONVERT)*sizeof(*entry_d))+sizeof(*hdr_d))); 1796153323Srodrigc 1797153323Srodrigc ASSERT(start_s < INT_GET(hdr_s->count, ARCH_CONVERT)); 1798153323Srodrigc ASSERT(start_d <= INT_GET(hdr_d->count, ARCH_CONVERT)); 1799153323Srodrigc ASSERT(count <= INT_GET(hdr_s->count, ARCH_CONVERT)); 1800153323Srodrigc 1801153323Srodrigc /* 1802153323Srodrigc * Move the entries in the destination leaf up to make a hole? 1803153323Srodrigc */ 1804153323Srodrigc if (start_d < INT_GET(hdr_d->count, ARCH_CONVERT)) { 1805153323Srodrigc tmp = INT_GET(hdr_d->count, ARCH_CONVERT) - start_d; 1806153323Srodrigc tmp *= (uint)sizeof(xfs_dir_leaf_entry_t); 1807153323Srodrigc entry_s = &leaf_d->entries[start_d]; 1808153323Srodrigc entry_d = &leaf_d->entries[start_d + count]; 1809153323Srodrigc memcpy(entry_d, entry_s, tmp); 1810153323Srodrigc } 1811153323Srodrigc 1812153323Srodrigc /* 1813153323Srodrigc * Copy all entry's in the same (sorted) order, 1814153323Srodrigc * but allocate filenames packed and in sequence. 1815153323Srodrigc */ 1816153323Srodrigc entry_s = &leaf_s->entries[start_s]; 1817153323Srodrigc entry_d = &leaf_d->entries[start_d]; 1818153323Srodrigc for (i = 0; i < count; entry_s++, entry_d++, i++) { 1819153323Srodrigc ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) >= INT_GET(hdr_s->firstused, ARCH_CONVERT)); 1820153323Srodrigc tmp = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry_s); 1821153323Srodrigc INT_MOD(hdr_d->firstused, ARCH_CONVERT, -(tmp)); 1822153323Srodrigc entry_d->hashval = entry_s->hashval; /* INT_: direct copy */ 1823153323Srodrigc INT_COPY(entry_d->nameidx, hdr_d->firstused, ARCH_CONVERT); 1824153323Srodrigc entry_d->namelen = entry_s->namelen; 1825153323Srodrigc ASSERT(INT_GET(entry_d->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp)); 1826153323Srodrigc memcpy(XFS_DIR_LEAF_NAMESTRUCT(leaf_d, INT_GET(entry_d->nameidx, ARCH_CONVERT)), 1827153323Srodrigc XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)), tmp); 1828153323Srodrigc ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp)); 1829153323Srodrigc memset((char *)XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)), 1830153323Srodrigc 0, tmp); 1831153323Srodrigc INT_MOD(hdr_s->namebytes, ARCH_CONVERT, -(entry_d->namelen)); 1832153323Srodrigc INT_MOD(hdr_d->namebytes, ARCH_CONVERT, entry_d->namelen); 1833153323Srodrigc INT_MOD(hdr_s->count, ARCH_CONVERT, -1); 1834153323Srodrigc INT_MOD(hdr_d->count, ARCH_CONVERT, +1); 1835153323Srodrigc tmp = INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t) 1836153323Srodrigc + (uint)sizeof(xfs_dir_leaf_hdr_t); 1837153323Srodrigc ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >= tmp); 1838153323Srodrigc 1839153323Srodrigc } 1840153323Srodrigc 1841153323Srodrigc /* 1842153323Srodrigc * Zero out the entries we just copied. 1843153323Srodrigc */ 1844153323Srodrigc if (start_s == INT_GET(hdr_s->count, ARCH_CONVERT)) { 1845153323Srodrigc tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t); 1846153323Srodrigc entry_s = &leaf_s->entries[start_s]; 1847153323Srodrigc ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp)); 1848153323Srodrigc memset((char *)entry_s, 0, tmp); 1849153323Srodrigc } else { 1850153323Srodrigc /* 1851153323Srodrigc * Move the remaining entries down to fill the hole, 1852153323Srodrigc * then zero the entries at the top. 1853153323Srodrigc */ 1854153323Srodrigc tmp = INT_GET(hdr_s->count, ARCH_CONVERT) - count; 1855153323Srodrigc tmp *= (uint)sizeof(xfs_dir_leaf_entry_t); 1856153323Srodrigc entry_s = &leaf_s->entries[start_s + count]; 1857153323Srodrigc entry_d = &leaf_s->entries[start_s]; 1858153323Srodrigc memcpy(entry_d, entry_s, tmp); 1859153323Srodrigc 1860153323Srodrigc tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t); 1861153323Srodrigc entry_s = &leaf_s->entries[INT_GET(hdr_s->count, ARCH_CONVERT)]; 1862153323Srodrigc ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp)); 1863153323Srodrigc memset((char *)entry_s, 0, tmp); 1864153323Srodrigc } 1865153323Srodrigc 1866153323Srodrigc /* 1867153323Srodrigc * Fill in the freemap information 1868153323Srodrigc */ 1869153323Srodrigc INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_hdr_t)); 1870153323Srodrigc INT_MOD(hdr_d->freemap[0].base, ARCH_CONVERT, INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t)); 1871153323Srodrigc INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT)); 1872159451Srodrigc INT_SET(hdr_d->freemap[1].base, ARCH_CONVERT, (hdr_d->freemap[2].base = 0)); 1873159451Srodrigc INT_SET(hdr_d->freemap[1].size, ARCH_CONVERT, (hdr_d->freemap[2].size = 0)); 1874153323Srodrigc hdr_s->holes = 1; /* leaf may not be compact */ 1875153323Srodrigc} 1876153323Srodrigc 1877153323Srodrigc/* 1878153323Srodrigc * Compare two leaf blocks "order". 1879153323Srodrigc */ 1880153323Srodrigcint 1881153323Srodrigcxfs_dir_leaf_order(xfs_dabuf_t *leaf1_bp, xfs_dabuf_t *leaf2_bp) 1882153323Srodrigc{ 1883153323Srodrigc xfs_dir_leafblock_t *leaf1, *leaf2; 1884153323Srodrigc 1885153323Srodrigc leaf1 = leaf1_bp->data; 1886153323Srodrigc leaf2 = leaf2_bp->data; 1887159451Srodrigc ASSERT((be16_to_cpu(leaf1->hdr.info.magic) == XFS_DIR_LEAF_MAGIC) && 1888159451Srodrigc (be16_to_cpu(leaf2->hdr.info.magic) == XFS_DIR_LEAF_MAGIC)); 1889153323Srodrigc if ((INT_GET(leaf1->hdr.count, ARCH_CONVERT) > 0) && (INT_GET(leaf2->hdr.count, ARCH_CONVERT) > 0) && 1890153323Srodrigc ((INT_GET(leaf2->entries[ 0 ].hashval, ARCH_CONVERT) < 1891153323Srodrigc INT_GET(leaf1->entries[ 0 ].hashval, ARCH_CONVERT)) || 1892153323Srodrigc (INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT) < 1893153323Srodrigc INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)))) { 1894159451Srodrigc return 1; 1895153323Srodrigc } 1896159451Srodrigc return 0; 1897153323Srodrigc} 1898153323Srodrigc 1899153323Srodrigc/* 1900153323Srodrigc * Pick up the last hashvalue from a leaf block. 1901153323Srodrigc */ 1902153323Srodrigcxfs_dahash_t 1903153323Srodrigcxfs_dir_leaf_lasthash(xfs_dabuf_t *bp, int *count) 1904153323Srodrigc{ 1905153323Srodrigc xfs_dir_leafblock_t *leaf; 1906153323Srodrigc 1907153323Srodrigc leaf = bp->data; 1908159451Srodrigc ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR_LEAF_MAGIC); 1909153323Srodrigc if (count) 1910153323Srodrigc *count = INT_GET(leaf->hdr.count, ARCH_CONVERT); 1911159451Srodrigc if (!leaf->hdr.count) 1912153323Srodrigc return(0); 1913153323Srodrigc return(INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)); 1914153323Srodrigc} 1915153323Srodrigc 1916153323Srodrigc/* 1917153323Srodrigc * Copy out directory entries for getdents(), for leaf directories. 1918153323Srodrigc */ 1919153323Srodrigcint 1920153323Srodrigcxfs_dir_leaf_getdents_int( 1921153323Srodrigc xfs_dabuf_t *bp, 1922153323Srodrigc xfs_inode_t *dp, 1923153323Srodrigc xfs_dablk_t bno, 1924153323Srodrigc uio_t *uio, 1925153323Srodrigc int *eobp, 1926153323Srodrigc xfs_dirent_t *dbp, 1927153323Srodrigc xfs_dir_put_t put, 1928153323Srodrigc xfs_daddr_t nextda) 1929153323Srodrigc{ 1930153323Srodrigc xfs_dir_leafblock_t *leaf; 1931153323Srodrigc xfs_dir_leaf_entry_t *entry; 1932153323Srodrigc xfs_dir_leaf_name_t *namest; 1933153323Srodrigc int entno, want_entno, i, nextentno; 1934153323Srodrigc xfs_mount_t *mp; 1935153323Srodrigc xfs_dahash_t cookhash; 1936153323Srodrigc xfs_dahash_t nexthash = 0; 1937153323Srodrigc#if (BITS_PER_LONG == 32) 1938153323Srodrigc xfs_dahash_t lasthash = XFS_DA_MAXHASH; 1939153323Srodrigc#endif 1940153323Srodrigc xfs_dir_put_args_t p; 1941153323Srodrigc 1942153323Srodrigc mp = dp->i_mount; 1943153323Srodrigc leaf = bp->data; 1944159451Srodrigc if (be16_to_cpu(leaf->hdr.info.magic) != XFS_DIR_LEAF_MAGIC) { 1945153323Srodrigc *eobp = 1; 1946159451Srodrigc return XFS_ERROR(ENOENT); /* XXX wrong code */ 1947153323Srodrigc } 1948153323Srodrigc 1949153323Srodrigc want_entno = XFS_DA_COOKIE_ENTRY(mp, uio->uio_offset); 1950153323Srodrigc 1951153323Srodrigc cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset); 1952153323Srodrigc 1953153323Srodrigc xfs_dir_trace_g_dul("leaf: start", dp, uio, leaf); 1954153323Srodrigc 1955153323Srodrigc /* 1956153323Srodrigc * Re-find our place. 1957153323Srodrigc */ 1958153323Srodrigc for (i = entno = 0, entry = &leaf->entries[0]; 1959153323Srodrigc i < INT_GET(leaf->hdr.count, ARCH_CONVERT); 1960153323Srodrigc entry++, i++) { 1961153323Srodrigc 1962153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, 1963153323Srodrigc INT_GET(entry->nameidx, ARCH_CONVERT)); 1964153323Srodrigc 1965153323Srodrigc if (unlikely( 1966153323Srodrigc ((char *)namest < (char *)leaf) || 1967153323Srodrigc ((char *)namest >= (char *)leaf + XFS_LBSIZE(mp)))) { 1968153323Srodrigc XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(1)", 1969153323Srodrigc XFS_ERRLEVEL_LOW, mp, leaf); 1970153323Srodrigc xfs_dir_trace_g_du("leaf: corrupted", dp, uio); 1971153323Srodrigc return XFS_ERROR(EFSCORRUPTED); 1972153323Srodrigc } 1973153323Srodrigc if (INT_GET(entry->hashval, ARCH_CONVERT) >= cookhash) { 1974153323Srodrigc if ( entno < want_entno 1975153323Srodrigc && INT_GET(entry->hashval, ARCH_CONVERT) 1976153323Srodrigc == cookhash) { 1977153323Srodrigc /* 1978153323Srodrigc * Trying to get to a particular offset in a 1979153323Srodrigc * run of equal-hashval entries. 1980153323Srodrigc */ 1981153323Srodrigc entno++; 1982153323Srodrigc } else if ( want_entno > 0 1983153323Srodrigc && entno == want_entno 1984153323Srodrigc && INT_GET(entry->hashval, ARCH_CONVERT) 1985153323Srodrigc == cookhash) { 1986153323Srodrigc break; 1987153323Srodrigc } else { 1988153323Srodrigc entno = 0; 1989153323Srodrigc break; 1990153323Srodrigc } 1991153323Srodrigc } 1992153323Srodrigc } 1993153323Srodrigc 1994153323Srodrigc if (i == INT_GET(leaf->hdr.count, ARCH_CONVERT)) { 1995153323Srodrigc xfs_dir_trace_g_du("leaf: hash not found", dp, uio); 1996159451Srodrigc if (!leaf->hdr.info.forw) 1997153323Srodrigc uio->uio_offset = 1998153323Srodrigc XFS_DA_MAKE_COOKIE(mp, 0, 0, XFS_DA_MAXHASH); 1999153323Srodrigc /* 2000153323Srodrigc * Don't set uio_offset if there's another block: 2001153323Srodrigc * the node code will be setting uio_offset anyway. 2002153323Srodrigc */ 2003153323Srodrigc *eobp = 0; 2004159451Srodrigc return 0; 2005153323Srodrigc } 2006153323Srodrigc xfs_dir_trace_g_due("leaf: hash found", dp, uio, entry); 2007153323Srodrigc 2008153323Srodrigc p.dbp = dbp; 2009153323Srodrigc p.put = put; 2010153323Srodrigc p.uio = uio; 2011153323Srodrigc 2012153323Srodrigc /* 2013153323Srodrigc * We're synchronized, start copying entries out to the user. 2014153323Srodrigc */ 2015153323Srodrigc for (; entno >= 0 && i < INT_GET(leaf->hdr.count, ARCH_CONVERT); 2016153323Srodrigc entry++, i++, (entno = nextentno)) { 2017153323Srodrigc int lastresid=0, retval; 2018153323Srodrigc xfs_dircook_t lastoffset; 2019153323Srodrigc xfs_dahash_t thishash; 2020153323Srodrigc 2021153323Srodrigc /* 2022153323Srodrigc * Check for a damaged directory leaf block and pick up 2023153323Srodrigc * the inode number from this entry. 2024153323Srodrigc */ 2025153323Srodrigc namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, 2026153323Srodrigc INT_GET(entry->nameidx, ARCH_CONVERT)); 2027153323Srodrigc 2028153323Srodrigc if (unlikely( 2029153323Srodrigc ((char *)namest < (char *)leaf) || 2030153323Srodrigc ((char *)namest >= (char *)leaf + XFS_LBSIZE(mp)))) { 2031153323Srodrigc XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(2)", 2032153323Srodrigc XFS_ERRLEVEL_LOW, mp, leaf); 2033153323Srodrigc xfs_dir_trace_g_du("leaf: corrupted", dp, uio); 2034153323Srodrigc return XFS_ERROR(EFSCORRUPTED); 2035153323Srodrigc } 2036153323Srodrigc 2037153323Srodrigc xfs_dir_trace_g_duc("leaf: middle cookie ", 2038153323Srodrigc dp, uio, p.cook.o); 2039153323Srodrigc 2040153323Srodrigc if (i < (INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1)) { 2041153323Srodrigc nexthash = INT_GET(entry[1].hashval, ARCH_CONVERT); 2042153323Srodrigc 2043153323Srodrigc if (nexthash == INT_GET(entry->hashval, ARCH_CONVERT)) 2044153323Srodrigc nextentno = entno + 1; 2045153323Srodrigc else 2046153323Srodrigc nextentno = 0; 2047153323Srodrigc XFS_PUT_COOKIE(p.cook, mp, bno, nextentno, nexthash); 2048153323Srodrigc xfs_dir_trace_g_duc("leaf: middle cookie ", 2049153323Srodrigc dp, uio, p.cook.o); 2050153323Srodrigc 2051159451Srodrigc } else if ((thishash = be32_to_cpu(leaf->hdr.info.forw))) { 2052153323Srodrigc xfs_dabuf_t *bp2; 2053153323Srodrigc xfs_dir_leafblock_t *leaf2; 2054153323Srodrigc 2055153323Srodrigc ASSERT(nextda != -1); 2056153323Srodrigc 2057153323Srodrigc retval = xfs_da_read_buf(dp->i_transp, dp, thishash, 2058153323Srodrigc nextda, &bp2, XFS_DATA_FORK); 2059153323Srodrigc if (retval) 2060159451Srodrigc return retval; 2061153323Srodrigc 2062153323Srodrigc ASSERT(bp2 != NULL); 2063153323Srodrigc 2064153323Srodrigc leaf2 = bp2->data; 2065153323Srodrigc 2066153323Srodrigc if (unlikely( 2067159451Srodrigc (be16_to_cpu(leaf2->hdr.info.magic) 2068153323Srodrigc != XFS_DIR_LEAF_MAGIC) 2069159451Srodrigc || (be32_to_cpu(leaf2->hdr.info.back) 2070153323Srodrigc != bno))) { /* GROT */ 2071153323Srodrigc XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(3)", 2072153323Srodrigc XFS_ERRLEVEL_LOW, mp, 2073153323Srodrigc leaf2); 2074153323Srodrigc xfs_da_brelse(dp->i_transp, bp2); 2075153323Srodrigc 2076159451Srodrigc return XFS_ERROR(EFSCORRUPTED); 2077153323Srodrigc } 2078153323Srodrigc 2079153323Srodrigc nexthash = INT_GET(leaf2->entries[0].hashval, 2080153323Srodrigc ARCH_CONVERT); 2081153323Srodrigc nextentno = -1; 2082153323Srodrigc XFS_PUT_COOKIE(p.cook, mp, thishash, 0, nexthash); 2083153323Srodrigc xfs_da_brelse(dp->i_transp, bp2); 2084153323Srodrigc xfs_dir_trace_g_duc("leaf: next blk cookie", 2085153323Srodrigc dp, uio, p.cook.o); 2086153323Srodrigc } else { 2087153323Srodrigc nextentno = -1; 2088153323Srodrigc XFS_PUT_COOKIE(p.cook, mp, 0, 0, XFS_DA_MAXHASH); 2089153323Srodrigc } 2090153323Srodrigc 2091153323Srodrigc /* 2092153323Srodrigc * Save off the cookie so we can fall back should the 2093153323Srodrigc * 'put' into the outgoing buffer fails. To handle a run 2094153323Srodrigc * of equal-hashvals, the off_t structure on 64bit 2095153323Srodrigc * builds has entno built into the cookie to ID the 2096153323Srodrigc * entry. On 32bit builds, we only have space for the 2097153323Srodrigc * hashval so we can't ID specific entries within a group 2098153323Srodrigc * of same hashval entries. For this, lastoffset is set 2099153323Srodrigc * to the first in the run of equal hashvals so we don't 2100153323Srodrigc * include any entries unless we can include all entries 2101153323Srodrigc * that share the same hashval. Hopefully the buffer 2102153323Srodrigc * provided is big enough to handle it (see pv763517). 2103153323Srodrigc */ 2104153323Srodrigc#if (BITS_PER_LONG == 32) 2105153323Srodrigc if ((thishash = INT_GET(entry->hashval, ARCH_CONVERT)) 2106153323Srodrigc != lasthash) { 2107153323Srodrigc XFS_PUT_COOKIE(lastoffset, mp, bno, entno, thishash); 2108153323Srodrigc lastresid = uio->uio_resid; 2109153323Srodrigc lasthash = thishash; 2110153323Srodrigc } else { 2111153323Srodrigc xfs_dir_trace_g_duc("leaf: DUP COOKIES, skipped", 2112153323Srodrigc dp, uio, p.cook.o); 2113153323Srodrigc } 2114153323Srodrigc#else 2115153323Srodrigc thishash = INT_GET(entry->hashval, ARCH_CONVERT); 2116153323Srodrigc XFS_PUT_COOKIE(lastoffset, mp, bno, entno, thishash); 2117153323Srodrigc lastresid = uio->uio_resid; 2118153323Srodrigc#endif /* BITS_PER_LONG == 32 */ 2119153323Srodrigc 2120153323Srodrigc /* 2121153323Srodrigc * Put the current entry into the outgoing buffer. If we fail 2122153323Srodrigc * then restore the UIO to the first entry in the current 2123153323Srodrigc * run of equal-hashval entries (probably one 1 entry long). 2124153323Srodrigc */ 2125159451Srodrigc p.ino = XFS_GET_DIR_INO8(namest->inumber); 2126153323Srodrigc#if XFS_BIG_INUMS 2127153323Srodrigc p.ino += mp->m_inoadd; 2128153323Srodrigc#endif 2129153323Srodrigc p.name = (char *)namest->name; 2130153323Srodrigc p.namelen = entry->namelen; 2131153323Srodrigc 2132153323Srodrigc retval = p.put(&p); 2133153323Srodrigc 2134153323Srodrigc if (!p.done) { 2135153323Srodrigc uio->uio_offset = lastoffset.o; 2136153323Srodrigc uio->uio_resid = lastresid; 2137153323Srodrigc 2138153323Srodrigc *eobp = 1; 2139153323Srodrigc 2140153323Srodrigc xfs_dir_trace_g_du("leaf: E-O-B", dp, uio); 2141153323Srodrigc 2142159451Srodrigc return retval; 2143153323Srodrigc } 2144153323Srodrigc } 2145153323Srodrigc 2146153323Srodrigc uio->uio_offset = p.cook.o; 2147153323Srodrigc 2148153323Srodrigc *eobp = 0; 2149153323Srodrigc 2150153323Srodrigc xfs_dir_trace_g_du("leaf: E-O-F", dp, uio); 2151153323Srodrigc 2152159451Srodrigc return 0; 2153153323Srodrigc} 2154153323Srodrigc 2155153323Srodrigc/* 2156218909Sbrucec * Format a dirent64 structure and copy it out the user's buffer. 2157153323Srodrigc */ 2158153323Srodrigcint 2159153323Srodrigcxfs_dir_put_dirent64_direct(xfs_dir_put_args_t *pa) 2160153323Srodrigc{ 2161153323Srodrigc iovec_t *iovp; 2162153323Srodrigc int reclen, namelen; 2163153323Srodrigc xfs_dirent_t *idbp; 2164153323Srodrigc uio_t *uio; 2165153323Srodrigc 2166153323Srodrigc namelen = pa->namelen; 2167153323Srodrigc reclen = DIRENTSIZE(namelen); 2168153323Srodrigc uio = pa->uio; 2169153323Srodrigc if (reclen > uio->uio_resid) { 2170153323Srodrigc pa->done = 0; 2171153323Srodrigc return 0; 2172153323Srodrigc } 2173153323Srodrigc iovp = uio->uio_iov; 2174153323Srodrigc idbp = (xfs_dirent_t *)iovp->iov_base; 2175153323Srodrigc iovp->iov_base = (char *)idbp + reclen; 2176153323Srodrigc iovp->iov_len -= reclen; 2177153323Srodrigc uio->uio_resid -= reclen; 2178153323Srodrigc idbp->d_reclen = reclen; 2179153323Srodrigc idbp->d_ino = pa->ino; 2180153323Srodrigc idbp->d_off = pa->cook.o; 2181153323Srodrigc idbp->d_name[namelen] = '\0'; 2182153323Srodrigc pa->done = 1; 2183153323Srodrigc memcpy(idbp->d_name, pa->name, namelen); 2184153323Srodrigc return 0; 2185153323Srodrigc} 2186153323Srodrigc 2187153323Srodrigc/* 2188218909Sbrucec * Format a dirent64 structure and copy it out the user's buffer. 2189153323Srodrigc */ 2190153323Srodrigcint 2191153323Srodrigcxfs_dir_put_dirent64_uio(xfs_dir_put_args_t *pa) 2192153323Srodrigc{ 2193153323Srodrigc int retval, reclen, namelen; 2194153323Srodrigc xfs_dirent_t *idbp; 2195153323Srodrigc uio_t *uio; 2196153323Srodrigc 2197153323Srodrigc namelen = pa->namelen; 2198153323Srodrigc reclen = DIRENTSIZE(namelen); 2199153323Srodrigc uio = pa->uio; 2200153323Srodrigc if (reclen > uio->uio_resid) { 2201153323Srodrigc pa->done = 0; 2202153323Srodrigc return 0; 2203153323Srodrigc } 2204153323Srodrigc idbp = pa->dbp; 2205153323Srodrigc idbp->d_reclen = reclen; 2206153323Srodrigc idbp->d_ino = pa->ino; 2207153323Srodrigc idbp->d_off = pa->cook.o; 2208153323Srodrigc idbp->d_name[namelen] = '\0'; 2209153323Srodrigc memcpy(idbp->d_name, pa->name, namelen); 2210153323Srodrigc retval = uio_read((caddr_t)idbp, reclen, uio); 2211153323Srodrigc pa->done = (retval == 0); 2212153323Srodrigc return retval; 2213153323Srodrigc} 2214153323Srodrigc 2215153323Srodrigc 2216