Merge branch 'for-linus' of master.kernel.org:/pub/scm/linux/kernel/git/roland/infiniband
[linux-2.6] / fs / xfs / xfs_dir.c
1 /*
2  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
3  * All Rights Reserved.
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License as
7  * published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it would be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write the Free Software Foundation,
16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17  */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_log.h"
22 #include "xfs_inum.h"
23 #include "xfs_trans.h"
24 #include "xfs_sb.h"
25 #include "xfs_dir.h"
26 #include "xfs_dir2.h"
27 #include "xfs_dmapi.h"
28 #include "xfs_mount.h"
29 #include "xfs_da_btree.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_alloc_btree.h"
32 #include "xfs_ialloc_btree.h"
33 #include "xfs_alloc.h"
34 #include "xfs_btree.h"
35 #include "xfs_dir_sf.h"
36 #include "xfs_dir2_sf.h"
37 #include "xfs_attr_sf.h"
38 #include "xfs_dinode.h"
39 #include "xfs_inode.h"
40 #include "xfs_bmap.h"
41 #include "xfs_dir_leaf.h"
42 #include "xfs_error.h"
43
44 /*
45  * xfs_dir.c
46  *
47  * Provide the external interfaces to manage directories.
48  */
49
50 /*========================================================================
51  * Function prototypes for the kernel.
52  *========================================================================*/
53
54 /*
55  * Functions for the dirops interfaces.
56  */
57 static void     xfs_dir_mount(struct xfs_mount *mp);
58
59 static int      xfs_dir_isempty(struct xfs_inode *dp);
60
61 static int      xfs_dir_init(struct xfs_trans *trans,
62                              struct xfs_inode *dir,
63                              struct xfs_inode *parent_dir);
64
65 static int      xfs_dir_createname(struct xfs_trans *trans,
66                                    struct xfs_inode *dp,
67                                    char *name_string,
68                                    int name_len,
69                                    xfs_ino_t inode_number,
70                                    xfs_fsblock_t *firstblock,
71                                    xfs_bmap_free_t *flist,
72                                    xfs_extlen_t total);
73
74 static int      xfs_dir_lookup(struct xfs_trans *tp,
75                                struct xfs_inode *dp,
76                                char *name_string,
77                                int name_length,
78                                xfs_ino_t *inode_number);
79
80 static int      xfs_dir_removename(struct xfs_trans *trans,
81                                    struct xfs_inode *dp,
82                                    char *name_string,
83                                    int name_length,
84                                    xfs_ino_t ino,
85                                    xfs_fsblock_t *firstblock,
86                                    xfs_bmap_free_t *flist,
87                                    xfs_extlen_t total);
88
89 static int      xfs_dir_getdents(struct xfs_trans *tp,
90                                  struct xfs_inode *dp,
91                                  struct uio *uiop,
92                                  int *eofp);
93
94 static int      xfs_dir_replace(struct xfs_trans *tp,
95                                 struct xfs_inode *dp,
96                                 char *name_string,
97                                 int name_length,
98                                 xfs_ino_t inode_number,
99                                 xfs_fsblock_t *firstblock,
100                                 xfs_bmap_free_t *flist,
101                                 xfs_extlen_t total);
102
103 static int      xfs_dir_canenter(struct xfs_trans *tp,
104                                  struct xfs_inode *dp,
105                                  char *name_string,
106                                  int name_length);
107
108 static int      xfs_dir_shortform_validate_ondisk(xfs_mount_t *mp,
109                                                   xfs_dinode_t *dip);
110
111 xfs_dirops_t xfsv1_dirops = {
112         .xd_mount                       = xfs_dir_mount,
113         .xd_isempty                     = xfs_dir_isempty,
114         .xd_init                        = xfs_dir_init,
115         .xd_createname                  = xfs_dir_createname,
116         .xd_lookup                      = xfs_dir_lookup,
117         .xd_removename                  = xfs_dir_removename,
118         .xd_getdents                    = xfs_dir_getdents,
119         .xd_replace                     = xfs_dir_replace,
120         .xd_canenter                    = xfs_dir_canenter,
121         .xd_shortform_validate_ondisk   = xfs_dir_shortform_validate_ondisk,
122         .xd_shortform_to_single         = xfs_dir_shortform_to_leaf,
123 };
124
125 /*
126  * Internal routines when dirsize == XFS_LBSIZE(mp).
127  */
128 STATIC int xfs_dir_leaf_lookup(xfs_da_args_t *args);
129 STATIC int xfs_dir_leaf_removename(xfs_da_args_t *args, int *number_entries,
130                                                  int *total_namebytes);
131 STATIC int xfs_dir_leaf_getdents(xfs_trans_t *trans, xfs_inode_t *dp,
132                                              uio_t *uio, int *eofp,
133                                              xfs_dirent_t *dbp,
134                                              xfs_dir_put_t put);
135 STATIC int xfs_dir_leaf_replace(xfs_da_args_t *args);
136
137 /*
138  * Internal routines when dirsize > XFS_LBSIZE(mp).
139  */
140 STATIC int xfs_dir_node_addname(xfs_da_args_t *args);
141 STATIC int xfs_dir_node_lookup(xfs_da_args_t *args);
142 STATIC int xfs_dir_node_removename(xfs_da_args_t *args);
143 STATIC int xfs_dir_node_getdents(xfs_trans_t *trans, xfs_inode_t *dp,
144                                              uio_t *uio, int *eofp,
145                                              xfs_dirent_t *dbp,
146                                              xfs_dir_put_t put);
147 STATIC int xfs_dir_node_replace(xfs_da_args_t *args);
148
149 #if defined(XFS_DIR_TRACE)
150 ktrace_t *xfs_dir_trace_buf;
151 #endif
152
153
154 /*========================================================================
155  * Overall external interface routines.
156  *========================================================================*/
157
158 xfs_dahash_t    xfs_dir_hash_dot, xfs_dir_hash_dotdot;
159
160 /*
161  * One-time startup routine called from xfs_init().
162  */
163 void
164 xfs_dir_startup(void)
165 {
166         xfs_dir_hash_dot = xfs_da_hashname(".", 1);
167         xfs_dir_hash_dotdot = xfs_da_hashname("..", 2);
168 }
169
170 /*
171  * Initialize directory-related fields in the mount structure.
172  */
173 static void
174 xfs_dir_mount(xfs_mount_t *mp)
175 {
176         uint shortcount, leafcount, count;
177
178         mp->m_dirversion = 1;
179         if (mp->m_flags & XFS_MOUNT_COMPAT_ATTR) {
180                 shortcount = (mp->m_attroffset -
181                                 (uint)sizeof(xfs_dir_sf_hdr_t)) /
182                                  (uint)sizeof(xfs_dir_sf_entry_t);
183                 leafcount = (XFS_LBSIZE(mp) -
184                                 (uint)sizeof(xfs_dir_leaf_hdr_t)) /
185                                  ((uint)sizeof(xfs_dir_leaf_entry_t) +
186                                   (uint)sizeof(xfs_dir_leaf_name_t));
187         } else {
188                 shortcount = (XFS_BMDR_SPACE_CALC(MINABTPTRS) -
189                               (uint)sizeof(xfs_dir_sf_hdr_t)) /
190                                (uint)sizeof(xfs_dir_sf_entry_t);
191                 leafcount = (XFS_LBSIZE(mp) -
192                             (uint)sizeof(xfs_dir_leaf_hdr_t)) /
193                              ((uint)sizeof(xfs_dir_leaf_entry_t) +
194                               (uint)sizeof(xfs_dir_leaf_name_t));
195         }
196         count = shortcount > leafcount ? shortcount : leafcount;
197         mp->m_dircook_elog = xfs_da_log2_roundup(count + 1);
198         ASSERT(mp->m_dircook_elog <= mp->m_sb.sb_blocklog);
199         mp->m_dir_node_ents = mp->m_attr_node_ents =
200                 (XFS_LBSIZE(mp) - (uint)sizeof(xfs_da_node_hdr_t)) /
201                 (uint)sizeof(xfs_da_node_entry_t);
202         mp->m_dir_magicpct = (XFS_LBSIZE(mp) * 37) / 100;
203         mp->m_dirblksize = mp->m_sb.sb_blocksize;
204         mp->m_dirblkfsbs = 1;
205 }
206
207 /*
208  * Return 1 if directory contains only "." and "..".
209  */
210 static int
211 xfs_dir_isempty(xfs_inode_t *dp)
212 {
213         xfs_dir_sf_hdr_t *hdr;
214
215         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
216         if (dp->i_d.di_size == 0)
217                 return(1);
218         if (dp->i_d.di_size > XFS_IFORK_DSIZE(dp))
219                 return(0);
220         hdr = (xfs_dir_sf_hdr_t *)dp->i_df.if_u1.if_data;
221         return(hdr->count == 0);
222 }
223
224 /*
225  * Initialize a directory with its "." and ".." entries.
226  */
227 static int
228 xfs_dir_init(xfs_trans_t *trans, xfs_inode_t *dir, xfs_inode_t *parent_dir)
229 {
230         xfs_da_args_t args;
231         int error;
232
233         memset((char *)&args, 0, sizeof(args));
234         args.dp = dir;
235         args.trans = trans;
236
237         ASSERT((dir->i_d.di_mode & S_IFMT) == S_IFDIR);
238         if ((error = xfs_dir_ino_validate(trans->t_mountp, parent_dir->i_ino)))
239                 return error;
240
241         return(xfs_dir_shortform_create(&args, parent_dir->i_ino));
242 }
243
244 /*
245  * Generic handler routine to add a name to a directory.
246  * Transitions directory from shortform to Btree as necessary.
247  */
248 static int                                                      /* error */
249 xfs_dir_createname(xfs_trans_t *trans, xfs_inode_t *dp, char *name,
250                    int namelen, xfs_ino_t inum, xfs_fsblock_t *firstblock,
251                    xfs_bmap_free_t *flist, xfs_extlen_t total)
252 {
253         xfs_da_args_t args;
254         int retval, newsize, done;
255
256         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
257
258         if ((retval = xfs_dir_ino_validate(trans->t_mountp, inum)))
259                 return (retval);
260
261         XFS_STATS_INC(xs_dir_create);
262         /*
263          * Fill in the arg structure for this request.
264          */
265         args.name = name;
266         args.namelen = namelen;
267         args.hashval = xfs_da_hashname(name, namelen);
268         args.inumber = inum;
269         args.dp = dp;
270         args.firstblock = firstblock;
271         args.flist = flist;
272         args.total = total;
273         args.whichfork = XFS_DATA_FORK;
274         args.trans = trans;
275         args.justcheck = 0;
276         args.addname = args.oknoent = 1;
277
278         /*
279          * Decide on what work routines to call based on the inode size.
280          */
281         done = 0;
282         if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) {
283                 newsize = XFS_DIR_SF_ENTSIZE_BYNAME(args.namelen);
284                 if ((dp->i_d.di_size + newsize) <= XFS_IFORK_DSIZE(dp)) {
285                         retval = xfs_dir_shortform_addname(&args);
286                         done = 1;
287                 } else {
288                         if (total == 0)
289                                 return XFS_ERROR(ENOSPC);
290                         retval = xfs_dir_shortform_to_leaf(&args);
291                         done = retval != 0;
292                 }
293         }
294         if (!done && xfs_bmap_one_block(dp, XFS_DATA_FORK)) {
295                 retval = xfs_dir_leaf_addname(&args);
296                 done = retval != ENOSPC;
297                 if (!done) {
298                         if (total == 0)
299                                 return XFS_ERROR(ENOSPC);
300                         retval = xfs_dir_leaf_to_node(&args);
301                         done = retval != 0;
302                 }
303         }
304         if (!done) {
305                 retval = xfs_dir_node_addname(&args);
306         }
307         return(retval);
308 }
309
310 /*
311  * Generic handler routine to check if a name can be added to a directory,
312  * without adding any blocks to the directory.
313  */
314 static int                                                      /* error */
315 xfs_dir_canenter(xfs_trans_t *trans, xfs_inode_t *dp, char *name, int namelen)
316 {
317         xfs_da_args_t args;
318         int retval, newsize;
319
320         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
321         /*
322          * Fill in the arg structure for this request.
323          */
324         args.name = name;
325         args.namelen = namelen;
326         args.hashval = xfs_da_hashname(name, namelen);
327         args.inumber = 0;
328         args.dp = dp;
329         args.firstblock = NULL;
330         args.flist = NULL;
331         args.total = 0;
332         args.whichfork = XFS_DATA_FORK;
333         args.trans = trans;
334         args.justcheck = args.addname = args.oknoent = 1;
335
336         /*
337          * Decide on what work routines to call based on the inode size.
338          */
339         if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) {
340                 newsize = XFS_DIR_SF_ENTSIZE_BYNAME(args.namelen);
341                 if ((dp->i_d.di_size + newsize) <= XFS_IFORK_DSIZE(dp))
342                         retval = 0;
343                 else
344                         retval = XFS_ERROR(ENOSPC);
345         } else if (xfs_bmap_one_block(dp, XFS_DATA_FORK)) {
346                 retval = xfs_dir_leaf_addname(&args);
347         } else {
348                 retval = xfs_dir_node_addname(&args);
349         }
350         return(retval);
351 }
352
353 /*
354  * Generic handler routine to remove a name from a directory.
355  * Transitions directory from Btree to shortform as necessary.
356  */
357 static int                                                      /* error */
358 xfs_dir_removename(xfs_trans_t *trans, xfs_inode_t *dp, char *name,
359                    int namelen, xfs_ino_t ino, xfs_fsblock_t *firstblock,
360                    xfs_bmap_free_t *flist, xfs_extlen_t total)
361 {
362         xfs_da_args_t args;
363         int count, totallen, newsize, retval;
364
365         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
366         XFS_STATS_INC(xs_dir_remove);
367         /*
368          * Fill in the arg structure for this request.
369          */
370         args.name = name;
371         args.namelen = namelen;
372         args.hashval = xfs_da_hashname(name, namelen);
373         args.inumber = ino;
374         args.dp = dp;
375         args.firstblock = firstblock;
376         args.flist = flist;
377         args.total = total;
378         args.whichfork = XFS_DATA_FORK;
379         args.trans = trans;
380         args.justcheck = args.addname = args.oknoent = 0;
381
382         /*
383          * Decide on what work routines to call based on the inode size.
384          */
385         if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) {
386                 retval = xfs_dir_shortform_removename(&args);
387         } else if (xfs_bmap_one_block(dp, XFS_DATA_FORK)) {
388                 retval = xfs_dir_leaf_removename(&args, &count, &totallen);
389                 if (retval == 0) {
390                         newsize = XFS_DIR_SF_ALLFIT(count, totallen);
391                         if (newsize <= XFS_IFORK_DSIZE(dp)) {
392                                 retval = xfs_dir_leaf_to_shortform(&args);
393                         }
394                 }
395         } else {
396                 retval = xfs_dir_node_removename(&args);
397         }
398         return(retval);
399 }
400
401 static int                                                      /* error */
402 xfs_dir_lookup(xfs_trans_t *trans, xfs_inode_t *dp, char *name, int namelen,
403                                    xfs_ino_t *inum)
404 {
405         xfs_da_args_t args;
406         int retval;
407
408         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
409
410         XFS_STATS_INC(xs_dir_lookup);
411         /*
412          * Fill in the arg structure for this request.
413          */
414         args.name = name;
415         args.namelen = namelen;
416         args.hashval = xfs_da_hashname(name, namelen);
417         args.inumber = 0;
418         args.dp = dp;
419         args.firstblock = NULL;
420         args.flist = NULL;
421         args.total = 0;
422         args.whichfork = XFS_DATA_FORK;
423         args.trans = trans;
424         args.justcheck = args.addname = 0;
425         args.oknoent = 1;
426
427         /*
428          * Decide on what work routines to call based on the inode size.
429          */
430         if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) {
431                 retval = xfs_dir_shortform_lookup(&args);
432         } else if (xfs_bmap_one_block(dp, XFS_DATA_FORK)) {
433                 retval = xfs_dir_leaf_lookup(&args);
434         } else {
435                 retval = xfs_dir_node_lookup(&args);
436         }
437         if (retval == EEXIST)
438                 retval = 0;
439         *inum = args.inumber;
440         return(retval);
441 }
442
443 /*
444  * Implement readdir.
445  */
446 static int                                                      /* error */
447 xfs_dir_getdents(xfs_trans_t *trans, xfs_inode_t *dp, uio_t *uio, int *eofp)
448 {
449         xfs_dirent_t *dbp;
450         int  alignment, retval;
451         xfs_dir_put_t put;
452
453         XFS_STATS_INC(xs_dir_getdents);
454         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
455
456         /*
457          * If our caller has given us a single contiguous memory buffer,
458          * just work directly within that buffer.  If it's in user memory,
459          * lock it down first.
460          */
461         alignment = sizeof(xfs_off_t) - 1;
462         if ((uio->uio_iovcnt == 1) &&
463             (((__psint_t)uio->uio_iov[0].iov_base & alignment) == 0) &&
464             ((uio->uio_iov[0].iov_len & alignment) == 0)) {
465                 dbp = NULL;
466                 put = xfs_dir_put_dirent64_direct;
467         } else {
468                 dbp = kmem_alloc(sizeof(*dbp) + MAXNAMELEN, KM_SLEEP);
469                 put = xfs_dir_put_dirent64_uio;
470         }
471
472         /*
473          * Decide on what work routines to call based on the inode size.
474          */
475         *eofp = 0;
476
477         if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) {
478                 retval = xfs_dir_shortform_getdents(dp, uio, eofp, dbp, put);
479         } else if (xfs_bmap_one_block(dp, XFS_DATA_FORK)) {
480                 retval = xfs_dir_leaf_getdents(trans, dp, uio, eofp, dbp, put);
481         } else {
482                 retval = xfs_dir_node_getdents(trans, dp, uio, eofp, dbp, put);
483         }
484         if (dbp != NULL)
485                 kmem_free(dbp, sizeof(*dbp) + MAXNAMELEN);
486
487         return(retval);
488 }
489
490 static int                                                      /* error */
491 xfs_dir_replace(xfs_trans_t *trans, xfs_inode_t *dp, char *name, int namelen,
492                                     xfs_ino_t inum, xfs_fsblock_t *firstblock,
493                                     xfs_bmap_free_t *flist, xfs_extlen_t total)
494 {
495         xfs_da_args_t args;
496         int retval;
497
498         ASSERT((dp->i_d.di_mode & S_IFMT) == S_IFDIR);
499
500         if ((retval = xfs_dir_ino_validate(trans->t_mountp, inum)))
501                 return retval;
502
503         /*
504          * Fill in the arg structure for this request.
505          */
506         args.name = name;
507         args.namelen = namelen;
508         args.hashval = xfs_da_hashname(name, namelen);
509         args.inumber = inum;
510         args.dp = dp;
511         args.firstblock = firstblock;
512         args.flist = flist;
513         args.total = total;
514         args.whichfork = XFS_DATA_FORK;
515         args.trans = trans;
516         args.justcheck = args.addname = args.oknoent = 0;
517
518         /*
519          * Decide on what work routines to call based on the inode size.
520          */
521         if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) {
522                 retval = xfs_dir_shortform_replace(&args);
523         } else if (xfs_bmap_one_block(dp, XFS_DATA_FORK)) {
524                 retval = xfs_dir_leaf_replace(&args);
525         } else {
526                 retval = xfs_dir_node_replace(&args);
527         }
528
529         return(retval);
530 }
531
532 static int
533 xfs_dir_shortform_validate_ondisk(xfs_mount_t *mp, xfs_dinode_t *dp)
534 {
535         xfs_ino_t               ino;
536         int                     namelen_sum;
537         int                     count;
538         xfs_dir_shortform_t     *sf;
539         xfs_dir_sf_entry_t      *sfe;
540         int                     i;
541
542
543
544         if ((INT_GET(dp->di_core.di_mode, ARCH_CONVERT) & S_IFMT) != S_IFDIR) {
545                 return 0;
546         }
547         if (INT_GET(dp->di_core.di_format, ARCH_CONVERT) != XFS_DINODE_FMT_LOCAL) {
548                 return 0;
549         }
550         if (INT_GET(dp->di_core.di_size, ARCH_CONVERT) < sizeof(sf->hdr)) {
551                 xfs_fs_cmn_err(CE_WARN, mp, "Invalid shortform size: dp 0x%p",
552                         dp);
553                 return 1;
554         }
555         sf = (xfs_dir_shortform_t *)(&dp->di_u.di_dirsf);
556         ino = XFS_GET_DIR_INO8(sf->hdr.parent);
557         if (xfs_dir_ino_validate(mp, ino))
558                 return 1;
559
560         count = sf->hdr.count;
561         if ((count < 0) || ((count * 10) > XFS_LITINO(mp))) {
562                 xfs_fs_cmn_err(CE_WARN, mp,
563                         "Invalid shortform count: dp 0x%p", dp);
564                 return(1);
565         }
566
567         if (count == 0) {
568                 return 0;
569         }
570
571         namelen_sum = 0;
572         sfe = &sf->list[0];
573         for (i = sf->hdr.count - 1; i >= 0; i--) {
574                 ino = XFS_GET_DIR_INO8(sfe->inumber);
575                 xfs_dir_ino_validate(mp, ino);
576                 if (sfe->namelen >= XFS_LITINO(mp)) {
577                         xfs_fs_cmn_err(CE_WARN, mp,
578                                 "Invalid shortform namelen: dp 0x%p", dp);
579                         return 1;
580                 }
581                 namelen_sum += sfe->namelen;
582                 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
583         }
584         if (namelen_sum >= XFS_LITINO(mp)) {
585                 xfs_fs_cmn_err(CE_WARN, mp,
586                         "Invalid shortform namelen: dp 0x%p", dp);
587                 return 1;
588         }
589
590         return 0;
591 }
592
593 /*========================================================================
594  * External routines when dirsize == XFS_LBSIZE(dp->i_mount).
595  *========================================================================*/
596
597 /*
598  * Add a name to the leaf directory structure
599  * This is the external routine.
600  */
601 int
602 xfs_dir_leaf_addname(xfs_da_args_t *args)
603 {
604         int index, retval;
605         xfs_dabuf_t *bp;
606
607         retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp,
608                                               XFS_DATA_FORK);
609         if (retval)
610                 return(retval);
611         ASSERT(bp != NULL);
612
613         retval = xfs_dir_leaf_lookup_int(bp, args, &index);
614         if (retval == ENOENT)
615                 retval = xfs_dir_leaf_add(bp, args, index);
616         xfs_da_buf_done(bp);
617         return(retval);
618 }
619
620 /*
621  * Remove a name from the leaf directory structure
622  * This is the external routine.
623  */
624 STATIC int
625 xfs_dir_leaf_removename(xfs_da_args_t *args, int *count, int *totallen)
626 {
627         xfs_dir_leafblock_t *leaf;
628         int index, retval;
629         xfs_dabuf_t *bp;
630
631         retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp,
632                                               XFS_DATA_FORK);
633         if (retval)
634                 return(retval);
635         ASSERT(bp != NULL);
636         leaf = bp->data;
637         ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
638         retval = xfs_dir_leaf_lookup_int(bp, args, &index);
639         if (retval == EEXIST) {
640                 (void)xfs_dir_leaf_remove(args->trans, bp, index);
641                 *count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
642                 *totallen = INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
643                 retval = 0;
644         }
645         xfs_da_buf_done(bp);
646         return(retval);
647 }
648
649 /*
650  * Look up a name in a leaf directory structure.
651  * This is the external routine.
652  */
653 STATIC int
654 xfs_dir_leaf_lookup(xfs_da_args_t *args)
655 {
656         int index, retval;
657         xfs_dabuf_t *bp;
658
659         retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp,
660                                               XFS_DATA_FORK);
661         if (retval)
662                 return(retval);
663         ASSERT(bp != NULL);
664         retval = xfs_dir_leaf_lookup_int(bp, args, &index);
665         xfs_da_brelse(args->trans, bp);
666         return(retval);
667 }
668
669 /*
670  * Copy out directory entries for getdents(), for leaf directories.
671  */
672 STATIC int
673 xfs_dir_leaf_getdents(xfs_trans_t *trans, xfs_inode_t *dp, uio_t *uio,
674                                   int *eofp, xfs_dirent_t *dbp, xfs_dir_put_t put)
675 {
676         xfs_dabuf_t *bp;
677         int retval, eob;
678
679         retval = xfs_da_read_buf(dp->i_transp, dp, 0, -1, &bp, XFS_DATA_FORK);
680         if (retval)
681                 return(retval);
682         ASSERT(bp != NULL);
683         retval = xfs_dir_leaf_getdents_int(bp, dp, 0, uio, &eob, dbp, put, -1);
684         xfs_da_brelse(trans, bp);
685         *eofp = (eob == 0);
686         return(retval);
687 }
688
689 /*
690  * Look up a name in a leaf directory structure, replace the inode number.
691  * This is the external routine.
692  */
693 STATIC int
694 xfs_dir_leaf_replace(xfs_da_args_t *args)
695 {
696         int index, retval;
697         xfs_dabuf_t *bp;
698         xfs_ino_t inum;
699         xfs_dir_leafblock_t *leaf;
700         xfs_dir_leaf_entry_t *entry;
701         xfs_dir_leaf_name_t *namest;
702
703         inum = args->inumber;
704         retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp,
705                                               XFS_DATA_FORK);
706         if (retval)
707                 return(retval);
708         ASSERT(bp != NULL);
709         retval = xfs_dir_leaf_lookup_int(bp, args, &index);
710         if (retval == EEXIST) {
711                 leaf = bp->data;
712                 entry = &leaf->entries[index];
713                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
714                 /* XXX - replace assert? */
715                 XFS_DIR_SF_PUT_DIRINO(&inum, &namest->inumber);
716                 xfs_da_log_buf(args->trans, bp,
717                     XFS_DA_LOGRANGE(leaf, namest, sizeof(namest->inumber)));
718                 xfs_da_buf_done(bp);
719                 retval = 0;
720         } else
721                 xfs_da_brelse(args->trans, bp);
722         return(retval);
723 }
724
725
726 /*========================================================================
727  * External routines when dirsize > XFS_LBSIZE(mp).
728  *========================================================================*/
729
730 /*
731  * Add a name to a Btree-format directory.
732  *
733  * This will involve walking down the Btree, and may involve splitting
734  * leaf nodes and even splitting intermediate nodes up to and including
735  * the root node (a special case of an intermediate node).
736  */
737 STATIC int
738 xfs_dir_node_addname(xfs_da_args_t *args)
739 {
740         xfs_da_state_t *state;
741         xfs_da_state_blk_t *blk;
742         int retval, error;
743
744         /*
745          * Fill in bucket of arguments/results/context to carry around.
746          */
747         state = xfs_da_state_alloc();
748         state->args = args;
749         state->mp = args->dp->i_mount;
750         state->blocksize = state->mp->m_sb.sb_blocksize;
751         state->node_ents = state->mp->m_dir_node_ents;
752
753         /*
754          * Search to see if name already exists, and get back a pointer
755          * to where it should go.
756          */
757         error = xfs_da_node_lookup_int(state, &retval);
758         if (error)
759                 retval = error;
760         if (retval != ENOENT)
761                 goto error;
762         blk = &state->path.blk[ state->path.active-1 ];
763         ASSERT(blk->magic == XFS_DIR_LEAF_MAGIC);
764         retval = xfs_dir_leaf_add(blk->bp, args, blk->index);
765         if (retval == 0) {
766                 /*
767                  * Addition succeeded, update Btree hashvals.
768                  */
769                 if (!args->justcheck)
770                         xfs_da_fixhashpath(state, &state->path);
771         } else {
772                 /*
773                  * Addition failed, split as many Btree elements as required.
774                  */
775                 if (args->total == 0) {
776                         ASSERT(retval == ENOSPC);
777                         goto error;
778                 }
779                 retval = xfs_da_split(state);
780         }
781 error:
782         xfs_da_state_free(state);
783
784         return(retval);
785 }
786
787 /*
788  * Remove a name from a B-tree directory.
789  *
790  * This will involve walking down the Btree, and may involve joining
791  * leaf nodes and even joining intermediate nodes up to and including
792  * the root node (a special case of an intermediate node).
793  */
794 STATIC int
795 xfs_dir_node_removename(xfs_da_args_t *args)
796 {
797         xfs_da_state_t *state;
798         xfs_da_state_blk_t *blk;
799         int retval, error;
800
801         state = xfs_da_state_alloc();
802         state->args = args;
803         state->mp = args->dp->i_mount;
804         state->blocksize = state->mp->m_sb.sb_blocksize;
805         state->node_ents = state->mp->m_dir_node_ents;
806
807         /*
808          * Search to see if name exists, and get back a pointer to it.
809          */
810         error = xfs_da_node_lookup_int(state, &retval);
811         if (error)
812                 retval = error;
813         if (retval != EEXIST) {
814                 xfs_da_state_free(state);
815                 return(retval);
816         }
817
818         /*
819          * Remove the name and update the hashvals in the tree.
820          */
821         blk = &state->path.blk[ state->path.active-1 ];
822         ASSERT(blk->magic == XFS_DIR_LEAF_MAGIC);
823         retval = xfs_dir_leaf_remove(args->trans, blk->bp, blk->index);
824         xfs_da_fixhashpath(state, &state->path);
825
826         /*
827          * Check to see if the tree needs to be collapsed.
828          */
829         error = 0;
830         if (retval) {
831                 error = xfs_da_join(state);
832         }
833
834         xfs_da_state_free(state);
835         if (error)
836                 return(error);
837         return(0);
838 }
839
840 /*
841  * Look up a filename in a int directory.
842  * Use an internal routine to actually do all the work.
843  */
844 STATIC int
845 xfs_dir_node_lookup(xfs_da_args_t *args)
846 {
847         xfs_da_state_t *state;
848         int retval, error, i;
849
850         state = xfs_da_state_alloc();
851         state->args = args;
852         state->mp = args->dp->i_mount;
853         state->blocksize = state->mp->m_sb.sb_blocksize;
854         state->node_ents = state->mp->m_dir_node_ents;
855
856         /*
857          * Search to see if name exists,
858          * and get back a pointer to it.
859          */
860         error = xfs_da_node_lookup_int(state, &retval);
861         if (error) {
862                 retval = error;
863         }
864
865         /*
866          * If not in a transaction, we have to release all the buffers.
867          */
868         for (i = 0; i < state->path.active; i++) {
869                 xfs_da_brelse(args->trans, state->path.blk[i].bp);
870                 state->path.blk[i].bp = NULL;
871         }
872
873         xfs_da_state_free(state);
874         return(retval);
875 }
876
877 STATIC int
878 xfs_dir_node_getdents(xfs_trans_t *trans, xfs_inode_t *dp, uio_t *uio,
879                                   int *eofp, xfs_dirent_t *dbp, xfs_dir_put_t put)
880 {
881         xfs_da_intnode_t *node;
882         xfs_da_node_entry_t *btree;
883         xfs_dir_leafblock_t *leaf = NULL;
884         xfs_dablk_t bno, nextbno;
885         xfs_dahash_t cookhash;
886         xfs_mount_t *mp;
887         int error, eob, i;
888         xfs_dabuf_t *bp;
889         xfs_daddr_t nextda;
890
891         /*
892          * Pick up our context.
893          */
894         mp = dp->i_mount;
895         bp = NULL;
896         bno = XFS_DA_COOKIE_BNO(mp, uio->uio_offset);
897         cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset);
898
899         xfs_dir_trace_g_du("node: start", dp, uio);
900
901         /*
902          * Re-find our place, even if we're confused about what our place is.
903          *
904          * First we check the block number from the magic cookie, it is a
905          * cache of where we ended last time.  If we find a leaf block, and
906          * the starting hashval in that block is less than our desired
907          * hashval, then we run with it.
908          */
909         if (bno > 0) {
910                 error = xfs_da_read_buf(trans, dp, bno, -2, &bp, XFS_DATA_FORK);
911                 if ((error != 0) && (error != EFSCORRUPTED))
912                         return(error);
913                 if (bp)
914                         leaf = bp->data;
915                 if (bp && INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) != XFS_DIR_LEAF_MAGIC) {
916                         xfs_dir_trace_g_dub("node: block not a leaf",
917                                                    dp, uio, bno);
918                         xfs_da_brelse(trans, bp);
919                         bp = NULL;
920                 }
921                 if (bp && INT_GET(leaf->entries[0].hashval, ARCH_CONVERT) > cookhash) {
922                         xfs_dir_trace_g_dub("node: leaf hash too large",
923                                                    dp, uio, bno);
924                         xfs_da_brelse(trans, bp);
925                         bp = NULL;
926                 }
927                 if (bp &&
928                     cookhash > INT_GET(leaf->entries[INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1].hashval, ARCH_CONVERT)) {
929                         xfs_dir_trace_g_dub("node: leaf hash too small",
930                                                    dp, uio, bno);
931                         xfs_da_brelse(trans, bp);
932                         bp = NULL;
933                 }
934         }
935
936         /*
937          * If we did not find a leaf block from the blockno in the cookie,
938          * or we there was no blockno in the cookie (eg: first time thru),
939          * the we start at the top of the Btree and re-find our hashval.
940          */
941         if (bp == NULL) {
942                 xfs_dir_trace_g_du("node: start at root" , dp, uio);
943                 bno = 0;
944                 for (;;) {
945                         error = xfs_da_read_buf(trans, dp, bno, -1, &bp,
946                                                        XFS_DATA_FORK);
947                         if (error)
948                                 return(error);
949                         if (bp == NULL)
950                                 return(XFS_ERROR(EFSCORRUPTED));
951                         node = bp->data;
952                         if (INT_GET(node->hdr.info.magic, ARCH_CONVERT) != XFS_DA_NODE_MAGIC)
953                                 break;
954                         btree = &node->btree[0];
955                         xfs_dir_trace_g_dun("node: node detail", dp, uio, node);
956                         for (i = 0; i < INT_GET(node->hdr.count, ARCH_CONVERT); btree++, i++) {
957                                 if (INT_GET(btree->hashval, ARCH_CONVERT) >= cookhash) {
958                                         bno = INT_GET(btree->before, ARCH_CONVERT);
959                                         break;
960                                 }
961                         }
962                         if (i == INT_GET(node->hdr.count, ARCH_CONVERT)) {
963                                 xfs_da_brelse(trans, bp);
964                                 xfs_dir_trace_g_du("node: hash beyond EOF",
965                                                           dp, uio);
966                                 uio->uio_offset = XFS_DA_MAKE_COOKIE(mp, 0, 0,
967                                                              XFS_DA_MAXHASH);
968                                 *eofp = 1;
969                                 return(0);
970                         }
971                         xfs_dir_trace_g_dub("node: going to block",
972                                                    dp, uio, bno);
973                         xfs_da_brelse(trans, bp);
974                 }
975         }
976         ASSERT(cookhash != XFS_DA_MAXHASH);
977
978         /*
979          * We've dropped down to the (first) leaf block that contains the
980          * hashval we are interested in.  Continue rolling upward thru the
981          * leaf blocks until we fill up our buffer.
982          */
983         for (;;) {
984                 leaf = bp->data;
985                 if (unlikely(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) != XFS_DIR_LEAF_MAGIC)) {
986                         xfs_dir_trace_g_dul("node: not a leaf", dp, uio, leaf);
987                         xfs_da_brelse(trans, bp);
988                         XFS_CORRUPTION_ERROR("xfs_dir_node_getdents(1)",
989                                              XFS_ERRLEVEL_LOW, mp, leaf);
990                         return XFS_ERROR(EFSCORRUPTED);
991                 }
992                 xfs_dir_trace_g_dul("node: leaf detail", dp, uio, leaf);
993                 if ((nextbno = INT_GET(leaf->hdr.info.forw, ARCH_CONVERT))) {
994                         nextda = xfs_da_reada_buf(trans, dp, nextbno,
995                                                   XFS_DATA_FORK);
996                 } else
997                         nextda = -1;
998                 error = xfs_dir_leaf_getdents_int(bp, dp, bno, uio, &eob, dbp,
999                                                   put, nextda);
1000                 xfs_da_brelse(trans, bp);
1001                 bno = nextbno;
1002                 if (eob) {
1003                         xfs_dir_trace_g_dub("node: E-O-B", dp, uio, bno);
1004                         *eofp = 0;
1005                         return(error);
1006                 }
1007                 if (bno == 0)
1008                         break;
1009                 error = xfs_da_read_buf(trans, dp, bno, nextda, &bp,
1010                                         XFS_DATA_FORK);
1011                 if (error)
1012                         return(error);
1013                 if (unlikely(bp == NULL)) {
1014                         XFS_ERROR_REPORT("xfs_dir_node_getdents(2)",
1015                                          XFS_ERRLEVEL_LOW, mp);
1016                         return(XFS_ERROR(EFSCORRUPTED));
1017                 }
1018         }
1019         *eofp = 1;
1020         xfs_dir_trace_g_du("node: E-O-F", dp, uio);
1021         return(0);
1022 }
1023
1024 /*
1025  * Look up a filename in an int directory, replace the inode number.
1026  * Use an internal routine to actually do the lookup.
1027  */
1028 STATIC int
1029 xfs_dir_node_replace(xfs_da_args_t *args)
1030 {
1031         xfs_da_state_t *state;
1032         xfs_da_state_blk_t *blk;
1033         xfs_dir_leafblock_t *leaf;
1034         xfs_dir_leaf_entry_t *entry;
1035         xfs_dir_leaf_name_t *namest;
1036         xfs_ino_t inum;
1037         int retval, error, i;
1038         xfs_dabuf_t *bp;
1039
1040         state = xfs_da_state_alloc();
1041         state->args = args;
1042         state->mp = args->dp->i_mount;
1043         state->blocksize = state->mp->m_sb.sb_blocksize;
1044         state->node_ents = state->mp->m_dir_node_ents;
1045         inum = args->inumber;
1046
1047         /*
1048          * Search to see if name exists,
1049          * and get back a pointer to it.
1050          */
1051         error = xfs_da_node_lookup_int(state, &retval);
1052         if (error) {
1053                 retval = error;
1054         }
1055
1056         if (retval == EEXIST) {
1057                 blk = &state->path.blk[state->path.active - 1];
1058                 ASSERT(blk->magic == XFS_DIR_LEAF_MAGIC);
1059                 bp = blk->bp;
1060                 leaf = bp->data;
1061                 entry = &leaf->entries[blk->index];
1062                 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1063                 /* XXX - replace assert ? */
1064                 XFS_DIR_SF_PUT_DIRINO(&inum, &namest->inumber);
1065                 xfs_da_log_buf(args->trans, bp,
1066                     XFS_DA_LOGRANGE(leaf, namest, sizeof(namest->inumber)));
1067                 xfs_da_buf_done(bp);
1068                 blk->bp = NULL;
1069                 retval = 0;
1070         } else {
1071                 i = state->path.active - 1;
1072                 xfs_da_brelse(args->trans, state->path.blk[i].bp);
1073                 state->path.blk[i].bp = NULL;
1074         }
1075         for (i = 0; i < state->path.active - 1; i++) {
1076                 xfs_da_brelse(args->trans, state->path.blk[i].bp);
1077                 state->path.blk[i].bp = NULL;
1078         }
1079
1080         xfs_da_state_free(state);
1081         return(retval);
1082 }
1083
1084 #if defined(XFS_DIR_TRACE)
1085 /*
1086  * Add a trace buffer entry for an inode and a uio.
1087  */
1088 void
1089 xfs_dir_trace_g_du(char *where, xfs_inode_t *dp, uio_t *uio)
1090 {
1091         xfs_dir_trace_enter(XFS_DIR_KTRACE_G_DU, where,
1092                      (void *)dp, (void *)dp->i_mount,
1093                      (void *)((unsigned long)(uio->uio_offset >> 32)),
1094                      (void *)((unsigned long)(uio->uio_offset & 0xFFFFFFFF)),
1095                      (void *)(unsigned long)uio->uio_resid,
1096                      NULL, NULL, NULL, NULL, NULL, NULL, NULL);
1097 }
1098
1099 /*
1100  * Add a trace buffer entry for an inode and a uio.
1101  */
1102 void
1103 xfs_dir_trace_g_dub(char *where, xfs_inode_t *dp, uio_t *uio, xfs_dablk_t bno)
1104 {
1105         xfs_dir_trace_enter(XFS_DIR_KTRACE_G_DUB, where,
1106                      (void *)dp, (void *)dp->i_mount,
1107                      (void *)((unsigned long)(uio->uio_offset >> 32)),
1108                      (void *)((unsigned long)(uio->uio_offset & 0xFFFFFFFF)),
1109                      (void *)(unsigned long)uio->uio_resid,
1110                      (void *)(unsigned long)bno,
1111                      NULL, NULL, NULL, NULL, NULL, NULL);
1112 }
1113
1114 /*
1115  * Add a trace buffer entry for an inode and a uio.
1116  */
1117 void
1118 xfs_dir_trace_g_dun(char *where, xfs_inode_t *dp, uio_t *uio,
1119                         xfs_da_intnode_t *node)
1120 {
1121         int     last = INT_GET(node->hdr.count, ARCH_CONVERT) - 1;
1122
1123         xfs_dir_trace_enter(XFS_DIR_KTRACE_G_DUN, where,
1124                      (void *)dp, (void *)dp->i_mount,
1125                      (void *)((unsigned long)(uio->uio_offset >> 32)),
1126                      (void *)((unsigned long)(uio->uio_offset & 0xFFFFFFFF)),
1127                      (void *)(unsigned long)uio->uio_resid,
1128                      (void *)(unsigned long)
1129                         INT_GET(node->hdr.info.forw, ARCH_CONVERT),
1130                      (void *)(unsigned long)
1131                         INT_GET(node->hdr.count, ARCH_CONVERT),
1132                      (void *)(unsigned long)
1133                         INT_GET(node->btree[0].hashval, ARCH_CONVERT),
1134                      (void *)(unsigned long)
1135                         INT_GET(node->btree[last].hashval, ARCH_CONVERT),
1136                      NULL, NULL, NULL);
1137 }
1138
1139 /*
1140  * Add a trace buffer entry for an inode and a uio.
1141  */
1142 void
1143 xfs_dir_trace_g_dul(char *where, xfs_inode_t *dp, uio_t *uio,
1144                         xfs_dir_leafblock_t *leaf)
1145 {
1146         int     last = INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1;
1147
1148         xfs_dir_trace_enter(XFS_DIR_KTRACE_G_DUL, where,
1149                      (void *)dp, (void *)dp->i_mount,
1150                      (void *)((unsigned long)(uio->uio_offset >> 32)),
1151                      (void *)((unsigned long)(uio->uio_offset & 0xFFFFFFFF)),
1152                      (void *)(unsigned long)uio->uio_resid,
1153                      (void *)(unsigned long)
1154                         INT_GET(leaf->hdr.info.forw, ARCH_CONVERT),
1155                      (void *)(unsigned long)
1156                         INT_GET(leaf->hdr.count, ARCH_CONVERT),
1157                      (void *)(unsigned long)
1158                         INT_GET(leaf->entries[0].hashval, ARCH_CONVERT),
1159                      (void *)(unsigned long)
1160                         INT_GET(leaf->entries[last].hashval, ARCH_CONVERT),
1161                      NULL, NULL, NULL);
1162 }
1163
1164 /*
1165  * Add a trace buffer entry for an inode and a uio.
1166  */
1167 void
1168 xfs_dir_trace_g_due(char *where, xfs_inode_t *dp, uio_t *uio,
1169                         xfs_dir_leaf_entry_t *entry)
1170 {
1171         xfs_dir_trace_enter(XFS_DIR_KTRACE_G_DUE, where,
1172                      (void *)dp, (void *)dp->i_mount,
1173                      (void *)((unsigned long)(uio->uio_offset >> 32)),
1174                      (void *)((unsigned long)(uio->uio_offset & 0xFFFFFFFF)),
1175                      (void *)(unsigned long)uio->uio_resid,
1176                      (void *)(unsigned long)
1177                         INT_GET(entry->hashval, ARCH_CONVERT),
1178                      NULL, NULL, NULL, NULL, NULL, NULL);
1179 }
1180
1181 /*
1182  * Add a trace buffer entry for an inode and a uio.
1183  */
1184 void
1185 xfs_dir_trace_g_duc(char *where, xfs_inode_t *dp, uio_t *uio, xfs_off_t cookie)
1186 {
1187         xfs_dir_trace_enter(XFS_DIR_KTRACE_G_DUC, where,
1188                      (void *)dp, (void *)dp->i_mount,
1189                      (void *)((unsigned long)(uio->uio_offset >> 32)),
1190                      (void *)((unsigned long)(uio->uio_offset & 0xFFFFFFFF)),
1191                      (void *)(unsigned long)uio->uio_resid,
1192                      (void *)((unsigned long)(cookie >> 32)),
1193                      (void *)((unsigned long)(cookie & 0xFFFFFFFF)),
1194                      NULL, NULL, NULL, NULL, NULL);
1195 }
1196
1197 /*
1198  * Add a trace buffer entry for the arguments given to the routine,
1199  * generic form.
1200  */
1201 void
1202 xfs_dir_trace_enter(int type, char *where,
1203                         void * a0, void * a1,
1204                         void * a2, void * a3,
1205                         void * a4, void * a5,
1206                         void * a6, void * a7,
1207                         void * a8, void * a9,
1208                         void * a10, void * a11)
1209 {
1210         ASSERT(xfs_dir_trace_buf);
1211         ktrace_enter(xfs_dir_trace_buf, (void *)(unsigned long)type,
1212                                         (void *)where,
1213                                         (void *)a0, (void *)a1, (void *)a2,
1214                                         (void *)a3, (void *)a4, (void *)a5,
1215                                         (void *)a6, (void *)a7, (void *)a8,
1216                                         (void *)a9, (void *)a10, (void *)a11,
1217                                         NULL, NULL);
1218 }
1219 #endif  /* XFS_DIR_TRACE */