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