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