Pull bugzilla-5653 into release branch
[linux-2.6] / fs / xfs / xfs_attr_leaf.c
1 /*
2  * Copyright (c) 2000-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_bit.h"
22 #include "xfs_log.h"
23 #include "xfs_inum.h"
24 #include "xfs_trans.h"
25 #include "xfs_sb.h"
26 #include "xfs_ag.h"
27 #include "xfs_dir.h"
28 #include "xfs_dir2.h"
29 #include "xfs_dmapi.h"
30 #include "xfs_mount.h"
31 #include "xfs_da_btree.h"
32 #include "xfs_bmap_btree.h"
33 #include "xfs_alloc_btree.h"
34 #include "xfs_ialloc_btree.h"
35 #include "xfs_alloc.h"
36 #include "xfs_btree.h"
37 #include "xfs_dir_sf.h"
38 #include "xfs_dir2_sf.h"
39 #include "xfs_attr_sf.h"
40 #include "xfs_dinode.h"
41 #include "xfs_inode.h"
42 #include "xfs_inode_item.h"
43 #include "xfs_bmap.h"
44 #include "xfs_attr.h"
45 #include "xfs_attr_leaf.h"
46 #include "xfs_error.h"
47
48 /*
49  * xfs_attr_leaf.c
50  *
51  * Routines to implement leaf blocks of attributes as Btrees of hashed names.
52  */
53
54 /*========================================================================
55  * Function prototypes for the kernel.
56  *========================================================================*/
57
58 /*
59  * Routines used for growing the Btree.
60  */
61 STATIC int xfs_attr_leaf_create(xfs_da_args_t *args, xfs_dablk_t which_block,
62                                     xfs_dabuf_t **bpp);
63 STATIC int xfs_attr_leaf_add_work(xfs_dabuf_t *leaf_buffer, xfs_da_args_t *args,
64                                               int freemap_index);
65 STATIC void xfs_attr_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *leaf_buffer);
66 STATIC void xfs_attr_leaf_rebalance(xfs_da_state_t *state,
67                                                    xfs_da_state_blk_t *blk1,
68                                                    xfs_da_state_blk_t *blk2);
69 STATIC int xfs_attr_leaf_figure_balance(xfs_da_state_t *state,
70                                            xfs_da_state_blk_t *leaf_blk_1,
71                                            xfs_da_state_blk_t *leaf_blk_2,
72                                            int *number_entries_in_blk1,
73                                            int *number_usedbytes_in_blk1);
74
75 /*
76  * Routines used for shrinking the Btree.
77  */
78 STATIC int xfs_attr_node_inactive(xfs_trans_t **trans, xfs_inode_t *dp,
79                                   xfs_dabuf_t *bp, int level);
80 STATIC int xfs_attr_leaf_inactive(xfs_trans_t **trans, xfs_inode_t *dp,
81                                   xfs_dabuf_t *bp);
82 STATIC int xfs_attr_leaf_freextent(xfs_trans_t **trans, xfs_inode_t *dp,
83                                    xfs_dablk_t blkno, int blkcnt);
84
85 /*
86  * Utility routines.
87  */
88 STATIC void xfs_attr_leaf_moveents(xfs_attr_leafblock_t *src_leaf,
89                                          int src_start,
90                                          xfs_attr_leafblock_t *dst_leaf,
91                                          int dst_start, int move_count,
92                                          xfs_mount_t *mp);
93 STATIC int xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index);
94 STATIC int xfs_attr_put_listent(xfs_attr_list_context_t *context,
95                              attrnames_t *, char *name, int namelen,
96                              int valuelen);
97
98
99 /*========================================================================
100  * External routines when attribute fork size < XFS_LITINO(mp).
101  *========================================================================*/
102
103 /*
104  * Query whether the requested number of additional bytes of extended
105  * attribute space will be able to fit inline.
106  * Returns zero if not, else the di_forkoff fork offset to be used in the
107  * literal area for attribute data once the new bytes have been added.
108  *
109  * di_forkoff must be 8 byte aligned, hence is stored as a >>3 value;
110  * special case for dev/uuid inodes, they have fixed size data forks.
111  */
112 int
113 xfs_attr_shortform_bytesfit(xfs_inode_t *dp, int bytes)
114 {
115         int offset;
116         int minforkoff; /* lower limit on valid forkoff locations */
117         int maxforkoff; /* upper limit on valid forkoff locations */
118         xfs_mount_t *mp = dp->i_mount;
119
120         offset = (XFS_LITINO(mp) - bytes) >> 3; /* rounded down */
121
122         switch (dp->i_d.di_format) {
123         case XFS_DINODE_FMT_DEV:
124                 minforkoff = roundup(sizeof(xfs_dev_t), 8) >> 3;
125                 return (offset >= minforkoff) ? minforkoff : 0;
126         case XFS_DINODE_FMT_UUID:
127                 minforkoff = roundup(sizeof(uuid_t), 8) >> 3;
128                 return (offset >= minforkoff) ? minforkoff : 0;
129         }
130
131         if (!(mp->m_flags & XFS_MOUNT_ATTR2)) {
132                 if (bytes <= XFS_IFORK_ASIZE(dp))
133                         return mp->m_attroffset >> 3;
134                 return 0;
135         }
136
137         /* data fork btree root can have at least this many key/ptr pairs */
138         minforkoff = MAX(dp->i_df.if_bytes, XFS_BMDR_SPACE_CALC(MINDBTPTRS));
139         minforkoff = roundup(minforkoff, 8) >> 3;
140
141         /* attr fork btree root can have at least this many key/ptr pairs */
142         maxforkoff = XFS_LITINO(mp) - XFS_BMDR_SPACE_CALC(MINABTPTRS);
143         maxforkoff = maxforkoff >> 3;   /* rounded down */
144
145         if (offset >= minforkoff && offset < maxforkoff)
146                 return offset;
147         if (offset >= maxforkoff)
148                 return maxforkoff;
149         return 0;
150 }
151
152 /*
153  * Switch on the ATTR2 superblock bit (implies also FEATURES2)
154  */
155 STATIC void
156 xfs_sbversion_add_attr2(xfs_mount_t *mp, xfs_trans_t *tp)
157 {
158         unsigned long s;
159
160         if ((mp->m_flags & XFS_MOUNT_ATTR2) &&
161             !(XFS_SB_VERSION_HASATTR2(&mp->m_sb))) {
162                 s = XFS_SB_LOCK(mp);
163                 if (!XFS_SB_VERSION_HASATTR2(&mp->m_sb)) {
164                         XFS_SB_VERSION_ADDATTR2(&mp->m_sb);
165                         XFS_SB_UNLOCK(mp, s);
166                         xfs_mod_sb(tp, XFS_SB_VERSIONNUM | XFS_SB_FEATURES2);
167                 } else
168                         XFS_SB_UNLOCK(mp, s);
169         }
170 }
171
172 /*
173  * Create the initial contents of a shortform attribute list.
174  */
175 void
176 xfs_attr_shortform_create(xfs_da_args_t *args)
177 {
178         xfs_attr_sf_hdr_t *hdr;
179         xfs_inode_t *dp;
180         xfs_ifork_t *ifp;
181
182         dp = args->dp;
183         ASSERT(dp != NULL);
184         ifp = dp->i_afp;
185         ASSERT(ifp != NULL);
186         ASSERT(ifp->if_bytes == 0);
187         if (dp->i_d.di_aformat == XFS_DINODE_FMT_EXTENTS) {
188                 ifp->if_flags &= ~XFS_IFEXTENTS;        /* just in case */
189                 dp->i_d.di_aformat = XFS_DINODE_FMT_LOCAL;
190                 ifp->if_flags |= XFS_IFINLINE;
191         } else {
192                 ASSERT(ifp->if_flags & XFS_IFINLINE);
193         }
194         xfs_idata_realloc(dp, sizeof(*hdr), XFS_ATTR_FORK);
195         hdr = (xfs_attr_sf_hdr_t *)ifp->if_u1.if_data;
196         hdr->count = 0;
197         hdr->totsize = cpu_to_be16(sizeof(*hdr));
198         xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);
199 }
200
201 /*
202  * Add a name/value pair to the shortform attribute list.
203  * Overflow from the inode has already been checked for.
204  */
205 void
206 xfs_attr_shortform_add(xfs_da_args_t *args, int forkoff)
207 {
208         xfs_attr_shortform_t *sf;
209         xfs_attr_sf_entry_t *sfe;
210         int i, offset, size;
211         xfs_mount_t *mp;
212         xfs_inode_t *dp;
213         xfs_ifork_t *ifp;
214
215         dp = args->dp;
216         mp = dp->i_mount;
217         dp->i_d.di_forkoff = forkoff;
218         dp->i_df.if_ext_max =
219                 XFS_IFORK_DSIZE(dp) / (uint)sizeof(xfs_bmbt_rec_t);
220         dp->i_afp->if_ext_max =
221                 XFS_IFORK_ASIZE(dp) / (uint)sizeof(xfs_bmbt_rec_t);
222
223         ifp = dp->i_afp;
224         ASSERT(ifp->if_flags & XFS_IFINLINE);
225         sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
226         sfe = &sf->list[0];
227         for (i = 0; i < sf->hdr.count; sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
228 #ifdef DEBUG
229                 if (sfe->namelen != args->namelen)
230                         continue;
231                 if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
232                         continue;
233                 if (((args->flags & ATTR_SECURE) != 0) !=
234                     ((sfe->flags & XFS_ATTR_SECURE) != 0))
235                         continue;
236                 if (((args->flags & ATTR_ROOT) != 0) !=
237                     ((sfe->flags & XFS_ATTR_ROOT) != 0))
238                         continue;
239                 ASSERT(0);
240 #endif
241         }
242
243         offset = (char *)sfe - (char *)sf;
244         size = XFS_ATTR_SF_ENTSIZE_BYNAME(args->namelen, args->valuelen);
245         xfs_idata_realloc(dp, size, XFS_ATTR_FORK);
246         sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
247         sfe = (xfs_attr_sf_entry_t *)((char *)sf + offset);
248
249         sfe->namelen = args->namelen;
250         sfe->valuelen = args->valuelen;
251         sfe->flags = (args->flags & ATTR_SECURE) ? XFS_ATTR_SECURE :
252                         ((args->flags & ATTR_ROOT) ? XFS_ATTR_ROOT : 0);
253         memcpy(sfe->nameval, args->name, args->namelen);
254         memcpy(&sfe->nameval[args->namelen], args->value, args->valuelen);
255         sf->hdr.count++;
256         be16_add(&sf->hdr.totsize, size);
257         xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);
258
259         xfs_sbversion_add_attr2(mp, args->trans);
260 }
261
262 /*
263  * Remove an attribute from the shortform attribute list structure.
264  */
265 int
266 xfs_attr_shortform_remove(xfs_da_args_t *args)
267 {
268         xfs_attr_shortform_t *sf;
269         xfs_attr_sf_entry_t *sfe;
270         int base, size=0, end, totsize, i;
271         xfs_mount_t *mp;
272         xfs_inode_t *dp;
273
274         dp = args->dp;
275         mp = dp->i_mount;
276         base = sizeof(xfs_attr_sf_hdr_t);
277         sf = (xfs_attr_shortform_t *)dp->i_afp->if_u1.if_data;
278         sfe = &sf->list[0];
279         end = sf->hdr.count;
280         for (i = 0; i < end; sfe = XFS_ATTR_SF_NEXTENTRY(sfe),
281                                         base += size, i++) {
282                 size = XFS_ATTR_SF_ENTSIZE(sfe);
283                 if (sfe->namelen != args->namelen)
284                         continue;
285                 if (memcmp(sfe->nameval, args->name, args->namelen) != 0)
286                         continue;
287                 if (((args->flags & ATTR_SECURE) != 0) !=
288                     ((sfe->flags & XFS_ATTR_SECURE) != 0))
289                         continue;
290                 if (((args->flags & ATTR_ROOT) != 0) !=
291                     ((sfe->flags & XFS_ATTR_ROOT) != 0))
292                         continue;
293                 break;
294         }
295         if (i == end)
296                 return(XFS_ERROR(ENOATTR));
297
298         /*
299          * Fix up the attribute fork data, covering the hole
300          */
301         end = base + size;
302         totsize = be16_to_cpu(sf->hdr.totsize);
303         if (end != totsize)
304                 memmove(&((char *)sf)[base], &((char *)sf)[end], totsize - end);
305         sf->hdr.count--;
306         be16_add(&sf->hdr.totsize, -size);
307
308         /*
309          * Fix up the start offset of the attribute fork
310          */
311         totsize -= size;
312         if (totsize == sizeof(xfs_attr_sf_hdr_t) && !args->addname &&
313             (mp->m_flags & XFS_MOUNT_ATTR2)) {
314                 /*
315                  * Last attribute now removed, revert to original
316                  * inode format making all literal area available
317                  * to the data fork once more.
318                  */
319                 xfs_idestroy_fork(dp, XFS_ATTR_FORK);
320                 dp->i_d.di_forkoff = 0;
321                 dp->i_d.di_aformat = XFS_DINODE_FMT_EXTENTS;
322                 ASSERT(dp->i_d.di_anextents == 0);
323                 ASSERT(dp->i_afp == NULL);
324                 dp->i_df.if_ext_max =
325                         XFS_IFORK_DSIZE(dp) / (uint)sizeof(xfs_bmbt_rec_t);
326                 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE);
327         } else {
328                 xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);
329                 dp->i_d.di_forkoff = xfs_attr_shortform_bytesfit(dp, totsize);
330                 ASSERT(dp->i_d.di_forkoff);
331                 ASSERT(totsize > sizeof(xfs_attr_sf_hdr_t) || args->addname ||
332                         !(mp->m_flags & XFS_MOUNT_ATTR2));
333                 dp->i_afp->if_ext_max =
334                         XFS_IFORK_ASIZE(dp) / (uint)sizeof(xfs_bmbt_rec_t);
335                 dp->i_df.if_ext_max =
336                         XFS_IFORK_DSIZE(dp) / (uint)sizeof(xfs_bmbt_rec_t);
337                 xfs_trans_log_inode(args->trans, dp,
338                                         XFS_ILOG_CORE | XFS_ILOG_ADATA);
339         }
340
341         xfs_sbversion_add_attr2(mp, args->trans);
342
343         return(0);
344 }
345
346 /*
347  * Look up a name in a shortform attribute list structure.
348  */
349 /*ARGSUSED*/
350 int
351 xfs_attr_shortform_lookup(xfs_da_args_t *args)
352 {
353         xfs_attr_shortform_t *sf;
354         xfs_attr_sf_entry_t *sfe;
355         int i;
356         xfs_ifork_t *ifp;
357
358         ifp = args->dp->i_afp;
359         ASSERT(ifp->if_flags & XFS_IFINLINE);
360         sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
361         sfe = &sf->list[0];
362         for (i = 0; i < sf->hdr.count;
363                                 sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
364                 if (sfe->namelen != args->namelen)
365                         continue;
366                 if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
367                         continue;
368                 if (((args->flags & ATTR_SECURE) != 0) !=
369                     ((sfe->flags & XFS_ATTR_SECURE) != 0))
370                         continue;
371                 if (((args->flags & ATTR_ROOT) != 0) !=
372                     ((sfe->flags & XFS_ATTR_ROOT) != 0))
373                         continue;
374                 return(XFS_ERROR(EEXIST));
375         }
376         return(XFS_ERROR(ENOATTR));
377 }
378
379 /*
380  * Look up a name in a shortform attribute list structure.
381  */
382 /*ARGSUSED*/
383 int
384 xfs_attr_shortform_getvalue(xfs_da_args_t *args)
385 {
386         xfs_attr_shortform_t *sf;
387         xfs_attr_sf_entry_t *sfe;
388         int i;
389
390         ASSERT(args->dp->i_d.di_aformat == XFS_IFINLINE);
391         sf = (xfs_attr_shortform_t *)args->dp->i_afp->if_u1.if_data;
392         sfe = &sf->list[0];
393         for (i = 0; i < sf->hdr.count;
394                                 sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
395                 if (sfe->namelen != args->namelen)
396                         continue;
397                 if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
398                         continue;
399                 if (((args->flags & ATTR_SECURE) != 0) !=
400                     ((sfe->flags & XFS_ATTR_SECURE) != 0))
401                         continue;
402                 if (((args->flags & ATTR_ROOT) != 0) !=
403                     ((sfe->flags & XFS_ATTR_ROOT) != 0))
404                         continue;
405                 if (args->flags & ATTR_KERNOVAL) {
406                         args->valuelen = sfe->valuelen;
407                         return(XFS_ERROR(EEXIST));
408                 }
409                 if (args->valuelen < sfe->valuelen) {
410                         args->valuelen = sfe->valuelen;
411                         return(XFS_ERROR(ERANGE));
412                 }
413                 args->valuelen = sfe->valuelen;
414                 memcpy(args->value, &sfe->nameval[args->namelen],
415                                                     args->valuelen);
416                 return(XFS_ERROR(EEXIST));
417         }
418         return(XFS_ERROR(ENOATTR));
419 }
420
421 /*
422  * Convert from using the shortform to the leaf.
423  */
424 int
425 xfs_attr_shortform_to_leaf(xfs_da_args_t *args)
426 {
427         xfs_inode_t *dp;
428         xfs_attr_shortform_t *sf;
429         xfs_attr_sf_entry_t *sfe;
430         xfs_da_args_t nargs;
431         char *tmpbuffer;
432         int error, i, size;
433         xfs_dablk_t blkno;
434         xfs_dabuf_t *bp;
435         xfs_ifork_t *ifp;
436
437         dp = args->dp;
438         ifp = dp->i_afp;
439         sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
440         size = be16_to_cpu(sf->hdr.totsize);
441         tmpbuffer = kmem_alloc(size, KM_SLEEP);
442         ASSERT(tmpbuffer != NULL);
443         memcpy(tmpbuffer, ifp->if_u1.if_data, size);
444         sf = (xfs_attr_shortform_t *)tmpbuffer;
445
446         xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);
447         bp = NULL;
448         error = xfs_da_grow_inode(args, &blkno);
449         if (error) {
450                 /*
451                  * If we hit an IO error middle of the transaction inside
452                  * grow_inode(), we may have inconsistent data. Bail out.
453                  */
454                 if (error == EIO)
455                         goto out;
456                 xfs_idata_realloc(dp, size, XFS_ATTR_FORK);     /* try to put */
457                 memcpy(ifp->if_u1.if_data, tmpbuffer, size);    /* it back */
458                 goto out;
459         }
460
461         ASSERT(blkno == 0);
462         error = xfs_attr_leaf_create(args, blkno, &bp);
463         if (error) {
464                 error = xfs_da_shrink_inode(args, 0, bp);
465                 bp = NULL;
466                 if (error)
467                         goto out;
468                 xfs_idata_realloc(dp, size, XFS_ATTR_FORK);     /* try to put */
469                 memcpy(ifp->if_u1.if_data, tmpbuffer, size);    /* it back */
470                 goto out;
471         }
472
473         memset((char *)&nargs, 0, sizeof(nargs));
474         nargs.dp = dp;
475         nargs.firstblock = args->firstblock;
476         nargs.flist = args->flist;
477         nargs.total = args->total;
478         nargs.whichfork = XFS_ATTR_FORK;
479         nargs.trans = args->trans;
480         nargs.oknoent = 1;
481
482         sfe = &sf->list[0];
483         for (i = 0; i < sf->hdr.count; i++) {
484                 nargs.name = (char *)sfe->nameval;
485                 nargs.namelen = sfe->namelen;
486                 nargs.value = (char *)&sfe->nameval[nargs.namelen];
487                 nargs.valuelen = sfe->valuelen;
488                 nargs.hashval = xfs_da_hashname((char *)sfe->nameval,
489                                                 sfe->namelen);
490                 nargs.flags = (sfe->flags & XFS_ATTR_SECURE) ? ATTR_SECURE :
491                                 ((sfe->flags & XFS_ATTR_ROOT) ? ATTR_ROOT : 0);
492                 error = xfs_attr_leaf_lookup_int(bp, &nargs); /* set a->index */
493                 ASSERT(error == ENOATTR);
494                 error = xfs_attr_leaf_add(bp, &nargs);
495                 ASSERT(error != ENOSPC);
496                 if (error)
497                         goto out;
498                 sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
499         }
500         error = 0;
501
502 out:
503         if(bp)
504                 xfs_da_buf_done(bp);
505         kmem_free(tmpbuffer, size);
506         return(error);
507 }
508
509 STATIC int
510 xfs_attr_shortform_compare(const void *a, const void *b)
511 {
512         xfs_attr_sf_sort_t *sa, *sb;
513
514         sa = (xfs_attr_sf_sort_t *)a;
515         sb = (xfs_attr_sf_sort_t *)b;
516         if (sa->hash < sb->hash) {
517                 return(-1);
518         } else if (sa->hash > sb->hash) {
519                 return(1);
520         } else {
521                 return(sa->entno - sb->entno);
522         }
523 }
524
525 /*
526  * Copy out entries of shortform attribute lists for attr_list().
527  * Shortform attribute lists are not stored in hashval sorted order.
528  * If the output buffer is not large enough to hold them all, then we
529  * we have to calculate each entries' hashvalue and sort them before
530  * we can begin returning them to the user.
531  */
532 /*ARGSUSED*/
533 int
534 xfs_attr_shortform_list(xfs_attr_list_context_t *context)
535 {
536         attrlist_cursor_kern_t *cursor;
537         xfs_attr_sf_sort_t *sbuf, *sbp;
538         xfs_attr_shortform_t *sf;
539         xfs_attr_sf_entry_t *sfe;
540         xfs_inode_t *dp;
541         int sbsize, nsbuf, count, i;
542
543         ASSERT(context != NULL);
544         dp = context->dp;
545         ASSERT(dp != NULL);
546         ASSERT(dp->i_afp != NULL);
547         sf = (xfs_attr_shortform_t *)dp->i_afp->if_u1.if_data;
548         ASSERT(sf != NULL);
549         if (!sf->hdr.count)
550                 return(0);
551         cursor = context->cursor;
552         ASSERT(cursor != NULL);
553
554         xfs_attr_trace_l_c("sf start", context);
555
556         /*
557          * If the buffer is large enough, do not bother with sorting.
558          * Note the generous fudge factor of 16 overhead bytes per entry.
559          */
560         if ((dp->i_afp->if_bytes + sf->hdr.count * 16) < context->bufsize) {
561                 for (i = 0, sfe = &sf->list[0]; i < sf->hdr.count; i++) {
562                         attrnames_t     *namesp;
563
564                         if (((context->flags & ATTR_SECURE) != 0) !=
565                             ((sfe->flags & XFS_ATTR_SECURE) != 0) &&
566                             !(context->flags & ATTR_KERNORMALS)) {
567                                 sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
568                                 continue;
569                         }
570                         if (((context->flags & ATTR_ROOT) != 0) !=
571                             ((sfe->flags & XFS_ATTR_ROOT) != 0) &&
572                             !(context->flags & ATTR_KERNROOTLS)) {
573                                 sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
574                                 continue;
575                         }
576                         namesp = (sfe->flags & XFS_ATTR_SECURE) ? &attr_secure:
577                                 ((sfe->flags & XFS_ATTR_ROOT) ? &attr_trusted :
578                                   &attr_user);
579                         if (context->flags & ATTR_KERNOVAL) {
580                                 ASSERT(context->flags & ATTR_KERNAMELS);
581                                 context->count += namesp->attr_namelen +
582                                         sfe->namelen + 1;
583                         }
584                         else {
585                                 if (xfs_attr_put_listent(context, namesp,
586                                                    (char *)sfe->nameval,
587                                                    (int)sfe->namelen,
588                                                    (int)sfe->valuelen))
589                                         break;
590                         }
591                         sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
592                 }
593                 xfs_attr_trace_l_c("sf big-gulp", context);
594                 return(0);
595         }
596
597         /*
598          * It didn't all fit, so we have to sort everything on hashval.
599          */
600         sbsize = sf->hdr.count * sizeof(*sbuf);
601         sbp = sbuf = kmem_alloc(sbsize, KM_SLEEP);
602
603         /*
604          * Scan the attribute list for the rest of the entries, storing
605          * the relevant info from only those that match into a buffer.
606          */
607         nsbuf = 0;
608         for (i = 0, sfe = &sf->list[0]; i < sf->hdr.count; i++) {
609                 if (unlikely(
610                     ((char *)sfe < (char *)sf) ||
611                     ((char *)sfe >= ((char *)sf + dp->i_afp->if_bytes)))) {
612                         XFS_CORRUPTION_ERROR("xfs_attr_shortform_list",
613                                              XFS_ERRLEVEL_LOW,
614                                              context->dp->i_mount, sfe);
615                         xfs_attr_trace_l_c("sf corrupted", context);
616                         kmem_free(sbuf, sbsize);
617                         return XFS_ERROR(EFSCORRUPTED);
618                 }
619                 if (((context->flags & ATTR_SECURE) != 0) !=
620                     ((sfe->flags & XFS_ATTR_SECURE) != 0) &&
621                     !(context->flags & ATTR_KERNORMALS)) {
622                         sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
623                         continue;
624                 }
625                 if (((context->flags & ATTR_ROOT) != 0) !=
626                     ((sfe->flags & XFS_ATTR_ROOT) != 0) &&
627                     !(context->flags & ATTR_KERNROOTLS)) {
628                         sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
629                         continue;
630                 }
631                 sbp->entno = i;
632                 sbp->hash = xfs_da_hashname((char *)sfe->nameval, sfe->namelen);
633                 sbp->name = (char *)sfe->nameval;
634                 sbp->namelen = sfe->namelen;
635                 /* These are bytes, and both on-disk, don't endian-flip */
636                 sbp->valuelen = sfe->valuelen;
637                 sbp->flags = sfe->flags;
638                 sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
639                 sbp++;
640                 nsbuf++;
641         }
642
643         /*
644          * Sort the entries on hash then entno.
645          */
646         xfs_sort(sbuf, nsbuf, sizeof(*sbuf), xfs_attr_shortform_compare);
647
648         /*
649          * Re-find our place IN THE SORTED LIST.
650          */
651         count = 0;
652         cursor->initted = 1;
653         cursor->blkno = 0;
654         for (sbp = sbuf, i = 0; i < nsbuf; i++, sbp++) {
655                 if (sbp->hash == cursor->hashval) {
656                         if (cursor->offset == count) {
657                                 break;
658                         }
659                         count++;
660                 } else if (sbp->hash > cursor->hashval) {
661                         break;
662                 }
663         }
664         if (i == nsbuf) {
665                 kmem_free(sbuf, sbsize);
666                 xfs_attr_trace_l_c("blk end", context);
667                 return(0);
668         }
669
670         /*
671          * Loop putting entries into the user buffer.
672          */
673         for ( ; i < nsbuf; i++, sbp++) {
674                 attrnames_t     *namesp;
675
676                 namesp = (sbp->flags & XFS_ATTR_SECURE) ? &attr_secure :
677                         ((sbp->flags & XFS_ATTR_ROOT) ? &attr_trusted :
678                           &attr_user);
679
680                 if (cursor->hashval != sbp->hash) {
681                         cursor->hashval = sbp->hash;
682                         cursor->offset = 0;
683                 }
684                 if (context->flags & ATTR_KERNOVAL) {
685                         ASSERT(context->flags & ATTR_KERNAMELS);
686                         context->count += namesp->attr_namelen +
687                                                 sbp->namelen + 1;
688                 } else {
689                         if (xfs_attr_put_listent(context, namesp,
690                                         sbp->name, sbp->namelen,
691                                         sbp->valuelen))
692                                 break;
693                 }
694                 cursor->offset++;
695         }
696
697         kmem_free(sbuf, sbsize);
698         xfs_attr_trace_l_c("sf E-O-F", context);
699         return(0);
700 }
701
702 /*
703  * Check a leaf attribute block to see if all the entries would fit into
704  * a shortform attribute list.
705  */
706 int
707 xfs_attr_shortform_allfit(xfs_dabuf_t *bp, xfs_inode_t *dp)
708 {
709         xfs_attr_leafblock_t *leaf;
710         xfs_attr_leaf_entry_t *entry;
711         xfs_attr_leaf_name_local_t *name_loc;
712         int bytes, i;
713
714         leaf = bp->data;
715         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
716
717         entry = &leaf->entries[0];
718         bytes = sizeof(struct xfs_attr_sf_hdr);
719         for (i = 0; i < be16_to_cpu(leaf->hdr.count); entry++, i++) {
720                 if (entry->flags & XFS_ATTR_INCOMPLETE)
721                         continue;               /* don't copy partial entries */
722                 if (!(entry->flags & XFS_ATTR_LOCAL))
723                         return(0);
724                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, i);
725                 if (name_loc->namelen >= XFS_ATTR_SF_ENTSIZE_MAX)
726                         return(0);
727                 if (be16_to_cpu(name_loc->valuelen) >= XFS_ATTR_SF_ENTSIZE_MAX)
728                         return(0);
729                 bytes += sizeof(struct xfs_attr_sf_entry)-1
730                                 + name_loc->namelen
731                                 + be16_to_cpu(name_loc->valuelen);
732         }
733         if ((dp->i_mount->m_flags & XFS_MOUNT_ATTR2) &&
734             (bytes == sizeof(struct xfs_attr_sf_hdr)))
735                 return(-1);
736         return(xfs_attr_shortform_bytesfit(dp, bytes));
737 }
738
739 /*
740  * Convert a leaf attribute list to shortform attribute list
741  */
742 int
743 xfs_attr_leaf_to_shortform(xfs_dabuf_t *bp, xfs_da_args_t *args, int forkoff)
744 {
745         xfs_attr_leafblock_t *leaf;
746         xfs_attr_leaf_entry_t *entry;
747         xfs_attr_leaf_name_local_t *name_loc;
748         xfs_da_args_t nargs;
749         xfs_inode_t *dp;
750         char *tmpbuffer;
751         int error, i;
752
753         dp = args->dp;
754         tmpbuffer = kmem_alloc(XFS_LBSIZE(dp->i_mount), KM_SLEEP);
755         ASSERT(tmpbuffer != NULL);
756
757         ASSERT(bp != NULL);
758         memcpy(tmpbuffer, bp->data, XFS_LBSIZE(dp->i_mount));
759         leaf = (xfs_attr_leafblock_t *)tmpbuffer;
760         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
761         memset(bp->data, 0, XFS_LBSIZE(dp->i_mount));
762
763         /*
764          * Clean out the prior contents of the attribute list.
765          */
766         error = xfs_da_shrink_inode(args, 0, bp);
767         if (error)
768                 goto out;
769
770         if (forkoff == -1) {
771                 ASSERT(dp->i_mount->m_flags & XFS_MOUNT_ATTR2);
772
773                 /*
774                  * Last attribute was removed, revert to original
775                  * inode format making all literal area available
776                  * to the data fork once more.
777                  */
778                 xfs_idestroy_fork(dp, XFS_ATTR_FORK);
779                 dp->i_d.di_forkoff = 0;
780                 dp->i_d.di_aformat = XFS_DINODE_FMT_EXTENTS;
781                 ASSERT(dp->i_d.di_anextents == 0);
782                 ASSERT(dp->i_afp == NULL);
783                 dp->i_df.if_ext_max =
784                         XFS_IFORK_DSIZE(dp) / (uint)sizeof(xfs_bmbt_rec_t);
785                 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE);
786                 goto out;
787         }
788
789         xfs_attr_shortform_create(args);
790
791         /*
792          * Copy the attributes
793          */
794         memset((char *)&nargs, 0, sizeof(nargs));
795         nargs.dp = dp;
796         nargs.firstblock = args->firstblock;
797         nargs.flist = args->flist;
798         nargs.total = args->total;
799         nargs.whichfork = XFS_ATTR_FORK;
800         nargs.trans = args->trans;
801         nargs.oknoent = 1;
802         entry = &leaf->entries[0];
803         for (i = 0; i < be16_to_cpu(leaf->hdr.count); entry++, i++) {
804                 if (entry->flags & XFS_ATTR_INCOMPLETE)
805                         continue;       /* don't copy partial entries */
806                 if (!entry->nameidx)
807                         continue;
808                 ASSERT(entry->flags & XFS_ATTR_LOCAL);
809                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, i);
810                 nargs.name = (char *)name_loc->nameval;
811                 nargs.namelen = name_loc->namelen;
812                 nargs.value = (char *)&name_loc->nameval[nargs.namelen];
813                 nargs.valuelen = be16_to_cpu(name_loc->valuelen);
814                 nargs.hashval = be32_to_cpu(entry->hashval);
815                 nargs.flags = (entry->flags & XFS_ATTR_SECURE) ? ATTR_SECURE :
816                               ((entry->flags & XFS_ATTR_ROOT) ? ATTR_ROOT : 0);
817                 xfs_attr_shortform_add(&nargs, forkoff);
818         }
819         error = 0;
820
821 out:
822         kmem_free(tmpbuffer, XFS_LBSIZE(dp->i_mount));
823         return(error);
824 }
825
826 /*
827  * Convert from using a single leaf to a root node and a leaf.
828  */
829 int
830 xfs_attr_leaf_to_node(xfs_da_args_t *args)
831 {
832         xfs_attr_leafblock_t *leaf;
833         xfs_da_intnode_t *node;
834         xfs_inode_t *dp;
835         xfs_dabuf_t *bp1, *bp2;
836         xfs_dablk_t blkno;
837         int error;
838
839         dp = args->dp;
840         bp1 = bp2 = NULL;
841         error = xfs_da_grow_inode(args, &blkno);
842         if (error)
843                 goto out;
844         error = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp1,
845                                              XFS_ATTR_FORK);
846         if (error)
847                 goto out;
848         ASSERT(bp1 != NULL);
849         bp2 = NULL;
850         error = xfs_da_get_buf(args->trans, args->dp, blkno, -1, &bp2,
851                                             XFS_ATTR_FORK);
852         if (error)
853                 goto out;
854         ASSERT(bp2 != NULL);
855         memcpy(bp2->data, bp1->data, XFS_LBSIZE(dp->i_mount));
856         xfs_da_buf_done(bp1);
857         bp1 = NULL;
858         xfs_da_log_buf(args->trans, bp2, 0, XFS_LBSIZE(dp->i_mount) - 1);
859
860         /*
861          * Set up the new root node.
862          */
863         error = xfs_da_node_create(args, 0, 1, &bp1, XFS_ATTR_FORK);
864         if (error)
865                 goto out;
866         node = bp1->data;
867         leaf = bp2->data;
868         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
869         /* both on-disk, don't endian-flip twice */
870         node->btree[0].hashval =
871                 leaf->entries[be16_to_cpu(leaf->hdr.count)-1 ].hashval;
872         node->btree[0].before = cpu_to_be32(blkno);
873         node->hdr.count = cpu_to_be16(1);
874         xfs_da_log_buf(args->trans, bp1, 0, XFS_LBSIZE(dp->i_mount) - 1);
875         error = 0;
876 out:
877         if (bp1)
878                 xfs_da_buf_done(bp1);
879         if (bp2)
880                 xfs_da_buf_done(bp2);
881         return(error);
882 }
883
884
885 /*========================================================================
886  * Routines used for growing the Btree.
887  *========================================================================*/
888
889 /*
890  * Create the initial contents of a leaf attribute list
891  * or a leaf in a node attribute list.
892  */
893 STATIC int
894 xfs_attr_leaf_create(xfs_da_args_t *args, xfs_dablk_t blkno, xfs_dabuf_t **bpp)
895 {
896         xfs_attr_leafblock_t *leaf;
897         xfs_attr_leaf_hdr_t *hdr;
898         xfs_inode_t *dp;
899         xfs_dabuf_t *bp;
900         int error;
901
902         dp = args->dp;
903         ASSERT(dp != NULL);
904         error = xfs_da_get_buf(args->trans, args->dp, blkno, -1, &bp,
905                                             XFS_ATTR_FORK);
906         if (error)
907                 return(error);
908         ASSERT(bp != NULL);
909         leaf = bp->data;
910         memset((char *)leaf, 0, XFS_LBSIZE(dp->i_mount));
911         hdr = &leaf->hdr;
912         hdr->info.magic = cpu_to_be16(XFS_ATTR_LEAF_MAGIC);
913         hdr->firstused = cpu_to_be16(XFS_LBSIZE(dp->i_mount));
914         if (!hdr->firstused) {
915                 hdr->firstused = cpu_to_be16(
916                         XFS_LBSIZE(dp->i_mount) - XFS_ATTR_LEAF_NAME_ALIGN);
917         }
918
919         hdr->freemap[0].base = cpu_to_be16(sizeof(xfs_attr_leaf_hdr_t));
920         hdr->freemap[0].size = cpu_to_be16(be16_to_cpu(hdr->firstused) -
921                                            sizeof(xfs_attr_leaf_hdr_t));
922
923         xfs_da_log_buf(args->trans, bp, 0, XFS_LBSIZE(dp->i_mount) - 1);
924
925         *bpp = bp;
926         return(0);
927 }
928
929 /*
930  * Split the leaf node, rebalance, then add the new entry.
931  */
932 int
933 xfs_attr_leaf_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
934                                    xfs_da_state_blk_t *newblk)
935 {
936         xfs_dablk_t blkno;
937         int error;
938
939         /*
940          * Allocate space for a new leaf node.
941          */
942         ASSERT(oldblk->magic == XFS_ATTR_LEAF_MAGIC);
943         error = xfs_da_grow_inode(state->args, &blkno);
944         if (error)
945                 return(error);
946         error = xfs_attr_leaf_create(state->args, blkno, &newblk->bp);
947         if (error)
948                 return(error);
949         newblk->blkno = blkno;
950         newblk->magic = XFS_ATTR_LEAF_MAGIC;
951
952         /*
953          * Rebalance the entries across the two leaves.
954          * NOTE: rebalance() currently depends on the 2nd block being empty.
955          */
956         xfs_attr_leaf_rebalance(state, oldblk, newblk);
957         error = xfs_da_blk_link(state, oldblk, newblk);
958         if (error)
959                 return(error);
960
961         /*
962          * Save info on "old" attribute for "atomic rename" ops, leaf_add()
963          * modifies the index/blkno/rmtblk/rmtblkcnt fields to show the
964          * "new" attrs info.  Will need the "old" info to remove it later.
965          *
966          * Insert the "new" entry in the correct block.
967          */
968         if (state->inleaf)
969                 error = xfs_attr_leaf_add(oldblk->bp, state->args);
970         else
971                 error = xfs_attr_leaf_add(newblk->bp, state->args);
972
973         /*
974          * Update last hashval in each block since we added the name.
975          */
976         oldblk->hashval = xfs_attr_leaf_lasthash(oldblk->bp, NULL);
977         newblk->hashval = xfs_attr_leaf_lasthash(newblk->bp, NULL);
978         return(error);
979 }
980
981 /*
982  * Add a name to the leaf attribute list structure.
983  */
984 int
985 xfs_attr_leaf_add(xfs_dabuf_t *bp, xfs_da_args_t *args)
986 {
987         xfs_attr_leafblock_t *leaf;
988         xfs_attr_leaf_hdr_t *hdr;
989         xfs_attr_leaf_map_t *map;
990         int tablesize, entsize, sum, tmp, i;
991
992         leaf = bp->data;
993         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
994         ASSERT((args->index >= 0)
995                 && (args->index <= be16_to_cpu(leaf->hdr.count)));
996         hdr = &leaf->hdr;
997         entsize = xfs_attr_leaf_newentsize(args->namelen, args->valuelen,
998                            args->trans->t_mountp->m_sb.sb_blocksize, NULL);
999
1000         /*
1001          * Search through freemap for first-fit on new name length.
1002          * (may need to figure in size of entry struct too)
1003          */
1004         tablesize = (be16_to_cpu(hdr->count) + 1)
1005                                         * sizeof(xfs_attr_leaf_entry_t)
1006                                         + sizeof(xfs_attr_leaf_hdr_t);
1007         map = &hdr->freemap[XFS_ATTR_LEAF_MAPSIZE-1];
1008         for (sum = 0, i = XFS_ATTR_LEAF_MAPSIZE-1; i >= 0; map--, i--) {
1009                 if (tablesize > be16_to_cpu(hdr->firstused)) {
1010                         sum += be16_to_cpu(map->size);
1011                         continue;
1012                 }
1013                 if (!map->size)
1014                         continue;       /* no space in this map */
1015                 tmp = entsize;
1016                 if (be16_to_cpu(map->base) < be16_to_cpu(hdr->firstused))
1017                         tmp += sizeof(xfs_attr_leaf_entry_t);
1018                 if (be16_to_cpu(map->size) >= tmp) {
1019                         tmp = xfs_attr_leaf_add_work(bp, args, i);
1020                         return(tmp);
1021                 }
1022                 sum += be16_to_cpu(map->size);
1023         }
1024
1025         /*
1026          * If there are no holes in the address space of the block,
1027          * and we don't have enough freespace, then compaction will do us
1028          * no good and we should just give up.
1029          */
1030         if (!hdr->holes && (sum < entsize))
1031                 return(XFS_ERROR(ENOSPC));
1032
1033         /*
1034          * Compact the entries to coalesce free space.
1035          * This may change the hdr->count via dropping INCOMPLETE entries.
1036          */
1037         xfs_attr_leaf_compact(args->trans, bp);
1038
1039         /*
1040          * After compaction, the block is guaranteed to have only one
1041          * free region, in freemap[0].  If it is not big enough, give up.
1042          */
1043         if (be16_to_cpu(hdr->freemap[0].size)
1044                                 < (entsize + sizeof(xfs_attr_leaf_entry_t)))
1045                 return(XFS_ERROR(ENOSPC));
1046
1047         return(xfs_attr_leaf_add_work(bp, args, 0));
1048 }
1049
1050 /*
1051  * Add a name to a leaf attribute list structure.
1052  */
1053 STATIC int
1054 xfs_attr_leaf_add_work(xfs_dabuf_t *bp, xfs_da_args_t *args, int mapindex)
1055 {
1056         xfs_attr_leafblock_t *leaf;
1057         xfs_attr_leaf_hdr_t *hdr;
1058         xfs_attr_leaf_entry_t *entry;
1059         xfs_attr_leaf_name_local_t *name_loc;
1060         xfs_attr_leaf_name_remote_t *name_rmt;
1061         xfs_attr_leaf_map_t *map;
1062         xfs_mount_t *mp;
1063         int tmp, i;
1064
1065         leaf = bp->data;
1066         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1067         hdr = &leaf->hdr;
1068         ASSERT((mapindex >= 0) && (mapindex < XFS_ATTR_LEAF_MAPSIZE));
1069         ASSERT((args->index >= 0) && (args->index <= be16_to_cpu(hdr->count)));
1070
1071         /*
1072          * Force open some space in the entry array and fill it in.
1073          */
1074         entry = &leaf->entries[args->index];
1075         if (args->index < be16_to_cpu(hdr->count)) {
1076                 tmp  = be16_to_cpu(hdr->count) - args->index;
1077                 tmp *= sizeof(xfs_attr_leaf_entry_t);
1078                 memmove((char *)(entry+1), (char *)entry, tmp);
1079                 xfs_da_log_buf(args->trans, bp,
1080                     XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(*entry)));
1081         }
1082         be16_add(&hdr->count, 1);
1083
1084         /*
1085          * Allocate space for the new string (at the end of the run).
1086          */
1087         map = &hdr->freemap[mapindex];
1088         mp = args->trans->t_mountp;
1089         ASSERT(be16_to_cpu(map->base) < XFS_LBSIZE(mp));
1090         ASSERT((be16_to_cpu(map->base) & 0x3) == 0);
1091         ASSERT(be16_to_cpu(map->size) >=
1092                 xfs_attr_leaf_newentsize(args->namelen, args->valuelen,
1093                                          mp->m_sb.sb_blocksize, NULL));
1094         ASSERT(be16_to_cpu(map->size) < XFS_LBSIZE(mp));
1095         ASSERT((be16_to_cpu(map->size) & 0x3) == 0);
1096         be16_add(&map->size,
1097                 -xfs_attr_leaf_newentsize(args->namelen, args->valuelen,
1098                                           mp->m_sb.sb_blocksize, &tmp));
1099         entry->nameidx = cpu_to_be16(be16_to_cpu(map->base) +
1100                                      be16_to_cpu(map->size));
1101         entry->hashval = cpu_to_be32(args->hashval);
1102         entry->flags = tmp ? XFS_ATTR_LOCAL : 0;
1103         entry->flags |= (args->flags & ATTR_SECURE) ? XFS_ATTR_SECURE :
1104                         ((args->flags & ATTR_ROOT) ? XFS_ATTR_ROOT : 0);
1105         if (args->rename) {
1106                 entry->flags |= XFS_ATTR_INCOMPLETE;
1107                 if ((args->blkno2 == args->blkno) &&
1108                     (args->index2 <= args->index)) {
1109                         args->index2++;
1110                 }
1111         }
1112         xfs_da_log_buf(args->trans, bp,
1113                           XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
1114         ASSERT((args->index == 0) ||
1115                (be32_to_cpu(entry->hashval) >= be32_to_cpu((entry-1)->hashval)));
1116         ASSERT((args->index == be16_to_cpu(hdr->count)-1) ||
1117                (be32_to_cpu(entry->hashval) <= be32_to_cpu((entry+1)->hashval)));
1118
1119         /*
1120          * Copy the attribute name and value into the new space.
1121          *
1122          * For "remote" attribute values, simply note that we need to
1123          * allocate space for the "remote" value.  We can't actually
1124          * allocate the extents in this transaction, and we can't decide
1125          * which blocks they should be as we might allocate more blocks
1126          * as part of this transaction (a split operation for example).
1127          */
1128         if (entry->flags & XFS_ATTR_LOCAL) {
1129                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, args->index);
1130                 name_loc->namelen = args->namelen;
1131                 name_loc->valuelen = cpu_to_be16(args->valuelen);
1132                 memcpy((char *)name_loc->nameval, args->name, args->namelen);
1133                 memcpy((char *)&name_loc->nameval[args->namelen], args->value,
1134                                    be16_to_cpu(name_loc->valuelen));
1135         } else {
1136                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, args->index);
1137                 name_rmt->namelen = args->namelen;
1138                 memcpy((char *)name_rmt->name, args->name, args->namelen);
1139                 entry->flags |= XFS_ATTR_INCOMPLETE;
1140                 /* just in case */
1141                 name_rmt->valuelen = 0;
1142                 name_rmt->valueblk = 0;
1143                 args->rmtblkno = 1;
1144                 args->rmtblkcnt = XFS_B_TO_FSB(mp, args->valuelen);
1145         }
1146         xfs_da_log_buf(args->trans, bp,
1147              XFS_DA_LOGRANGE(leaf, XFS_ATTR_LEAF_NAME(leaf, args->index),
1148                                    xfs_attr_leaf_entsize(leaf, args->index)));
1149
1150         /*
1151          * Update the control info for this leaf node
1152          */
1153         if (be16_to_cpu(entry->nameidx) < be16_to_cpu(hdr->firstused)) {
1154                 /* both on-disk, don't endian-flip twice */
1155                 hdr->firstused = entry->nameidx;
1156         }
1157         ASSERT(be16_to_cpu(hdr->firstused) >=
1158                ((be16_to_cpu(hdr->count) * sizeof(*entry)) + sizeof(*hdr)));
1159         tmp = (be16_to_cpu(hdr->count)-1) * sizeof(xfs_attr_leaf_entry_t)
1160                                         + sizeof(xfs_attr_leaf_hdr_t);
1161         map = &hdr->freemap[0];
1162         for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; map++, i++) {
1163                 if (be16_to_cpu(map->base) == tmp) {
1164                         be16_add(&map->base, sizeof(xfs_attr_leaf_entry_t));
1165                         be16_add(&map->size,
1166                                  -((int)sizeof(xfs_attr_leaf_entry_t)));
1167                 }
1168         }
1169         be16_add(&hdr->usedbytes, xfs_attr_leaf_entsize(leaf, args->index));
1170         xfs_da_log_buf(args->trans, bp,
1171                 XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));
1172         return(0);
1173 }
1174
1175 /*
1176  * Garbage collect a leaf attribute list block by copying it to a new buffer.
1177  */
1178 STATIC void
1179 xfs_attr_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *bp)
1180 {
1181         xfs_attr_leafblock_t *leaf_s, *leaf_d;
1182         xfs_attr_leaf_hdr_t *hdr_s, *hdr_d;
1183         xfs_mount_t *mp;
1184         char *tmpbuffer;
1185
1186         mp = trans->t_mountp;
1187         tmpbuffer = kmem_alloc(XFS_LBSIZE(mp), KM_SLEEP);
1188         ASSERT(tmpbuffer != NULL);
1189         memcpy(tmpbuffer, bp->data, XFS_LBSIZE(mp));
1190         memset(bp->data, 0, XFS_LBSIZE(mp));
1191
1192         /*
1193          * Copy basic information
1194          */
1195         leaf_s = (xfs_attr_leafblock_t *)tmpbuffer;
1196         leaf_d = bp->data;
1197         hdr_s = &leaf_s->hdr;
1198         hdr_d = &leaf_d->hdr;
1199         hdr_d->info = hdr_s->info;      /* struct copy */
1200         hdr_d->firstused = cpu_to_be16(XFS_LBSIZE(mp));
1201         /* handle truncation gracefully */
1202         if (!hdr_d->firstused) {
1203                 hdr_d->firstused = cpu_to_be16(
1204                                 XFS_LBSIZE(mp) - XFS_ATTR_LEAF_NAME_ALIGN);
1205         }
1206         hdr_d->usedbytes = 0;
1207         hdr_d->count = 0;
1208         hdr_d->holes = 0;
1209         hdr_d->freemap[0].base = cpu_to_be16(sizeof(xfs_attr_leaf_hdr_t));
1210         hdr_d->freemap[0].size = cpu_to_be16(be16_to_cpu(hdr_d->firstused) -
1211                                              sizeof(xfs_attr_leaf_hdr_t));
1212
1213         /*
1214          * Copy all entry's in the same (sorted) order,
1215          * but allocate name/value pairs packed and in sequence.
1216          */
1217         xfs_attr_leaf_moveents(leaf_s, 0, leaf_d, 0,
1218                                 be16_to_cpu(hdr_s->count), mp);
1219         xfs_da_log_buf(trans, bp, 0, XFS_LBSIZE(mp) - 1);
1220
1221         kmem_free(tmpbuffer, XFS_LBSIZE(mp));
1222 }
1223
1224 /*
1225  * Redistribute the attribute list entries between two leaf nodes,
1226  * taking into account the size of the new entry.
1227  *
1228  * NOTE: if new block is empty, then it will get the upper half of the
1229  * old block.  At present, all (one) callers pass in an empty second block.
1230  *
1231  * This code adjusts the args->index/blkno and args->index2/blkno2 fields
1232  * to match what it is doing in splitting the attribute leaf block.  Those
1233  * values are used in "atomic rename" operations on attributes.  Note that
1234  * the "new" and "old" values can end up in different blocks.
1235  */
1236 STATIC void
1237 xfs_attr_leaf_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
1238                                        xfs_da_state_blk_t *blk2)
1239 {
1240         xfs_da_args_t *args;
1241         xfs_da_state_blk_t *tmp_blk;
1242         xfs_attr_leafblock_t *leaf1, *leaf2;
1243         xfs_attr_leaf_hdr_t *hdr1, *hdr2;
1244         int count, totallen, max, space, swap;
1245
1246         /*
1247          * Set up environment.
1248          */
1249         ASSERT(blk1->magic == XFS_ATTR_LEAF_MAGIC);
1250         ASSERT(blk2->magic == XFS_ATTR_LEAF_MAGIC);
1251         leaf1 = blk1->bp->data;
1252         leaf2 = blk2->bp->data;
1253         ASSERT(be16_to_cpu(leaf1->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1254         ASSERT(be16_to_cpu(leaf2->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1255         args = state->args;
1256
1257         /*
1258          * Check ordering of blocks, reverse if it makes things simpler.
1259          *
1260          * NOTE: Given that all (current) callers pass in an empty
1261          * second block, this code should never set "swap".
1262          */
1263         swap = 0;
1264         if (xfs_attr_leaf_order(blk1->bp, blk2->bp)) {
1265                 tmp_blk = blk1;
1266                 blk1 = blk2;
1267                 blk2 = tmp_blk;
1268                 leaf1 = blk1->bp->data;
1269                 leaf2 = blk2->bp->data;
1270                 swap = 1;
1271         }
1272         hdr1 = &leaf1->hdr;
1273         hdr2 = &leaf2->hdr;
1274
1275         /*
1276          * Examine entries until we reduce the absolute difference in
1277          * byte usage between the two blocks to a minimum.  Then get
1278          * the direction to copy and the number of elements to move.
1279          *
1280          * "inleaf" is true if the new entry should be inserted into blk1.
1281          * If "swap" is also true, then reverse the sense of "inleaf".
1282          */
1283         state->inleaf = xfs_attr_leaf_figure_balance(state, blk1, blk2,
1284                                                             &count, &totallen);
1285         if (swap)
1286                 state->inleaf = !state->inleaf;
1287
1288         /*
1289          * Move any entries required from leaf to leaf:
1290          */
1291         if (count < be16_to_cpu(hdr1->count)) {
1292                 /*
1293                  * Figure the total bytes to be added to the destination leaf.
1294                  */
1295                 /* number entries being moved */
1296                 count = be16_to_cpu(hdr1->count) - count;
1297                 space  = be16_to_cpu(hdr1->usedbytes) - totallen;
1298                 space += count * sizeof(xfs_attr_leaf_entry_t);
1299
1300                 /*
1301                  * leaf2 is the destination, compact it if it looks tight.
1302                  */
1303                 max  = be16_to_cpu(hdr2->firstused)
1304                                                 - sizeof(xfs_attr_leaf_hdr_t);
1305                 max -= be16_to_cpu(hdr2->count) * sizeof(xfs_attr_leaf_entry_t);
1306                 if (space > max) {
1307                         xfs_attr_leaf_compact(args->trans, blk2->bp);
1308                 }
1309
1310                 /*
1311                  * Move high entries from leaf1 to low end of leaf2.
1312                  */
1313                 xfs_attr_leaf_moveents(leaf1, be16_to_cpu(hdr1->count) - count,
1314                                 leaf2, 0, count, state->mp);
1315
1316                 xfs_da_log_buf(args->trans, blk1->bp, 0, state->blocksize-1);
1317                 xfs_da_log_buf(args->trans, blk2->bp, 0, state->blocksize-1);
1318         } else if (count > be16_to_cpu(hdr1->count)) {
1319                 /*
1320                  * I assert that since all callers pass in an empty
1321                  * second buffer, this code should never execute.
1322                  */
1323
1324                 /*
1325                  * Figure the total bytes to be added to the destination leaf.
1326                  */
1327                 /* number entries being moved */
1328                 count -= be16_to_cpu(hdr1->count);
1329                 space  = totallen - be16_to_cpu(hdr1->usedbytes);
1330                 space += count * sizeof(xfs_attr_leaf_entry_t);
1331
1332                 /*
1333                  * leaf1 is the destination, compact it if it looks tight.
1334                  */
1335                 max  = be16_to_cpu(hdr1->firstused)
1336                                                 - sizeof(xfs_attr_leaf_hdr_t);
1337                 max -= be16_to_cpu(hdr1->count) * sizeof(xfs_attr_leaf_entry_t);
1338                 if (space > max) {
1339                         xfs_attr_leaf_compact(args->trans, blk1->bp);
1340                 }
1341
1342                 /*
1343                  * Move low entries from leaf2 to high end of leaf1.
1344                  */
1345                 xfs_attr_leaf_moveents(leaf2, 0, leaf1,
1346                                 be16_to_cpu(hdr1->count), count, state->mp);
1347
1348                 xfs_da_log_buf(args->trans, blk1->bp, 0, state->blocksize-1);
1349                 xfs_da_log_buf(args->trans, blk2->bp, 0, state->blocksize-1);
1350         }
1351
1352         /*
1353          * Copy out last hashval in each block for B-tree code.
1354          */
1355         blk1->hashval = be32_to_cpu(
1356                 leaf1->entries[be16_to_cpu(leaf1->hdr.count)-1].hashval);
1357         blk2->hashval = be32_to_cpu(
1358                 leaf2->entries[be16_to_cpu(leaf2->hdr.count)-1].hashval);
1359
1360         /*
1361          * Adjust the expected index for insertion.
1362          * NOTE: this code depends on the (current) situation that the
1363          * second block was originally empty.
1364          *
1365          * If the insertion point moved to the 2nd block, we must adjust
1366          * the index.  We must also track the entry just following the
1367          * new entry for use in an "atomic rename" operation, that entry
1368          * is always the "old" entry and the "new" entry is what we are
1369          * inserting.  The index/blkno fields refer to the "old" entry,
1370          * while the index2/blkno2 fields refer to the "new" entry.
1371          */
1372         if (blk1->index > be16_to_cpu(leaf1->hdr.count)) {
1373                 ASSERT(state->inleaf == 0);
1374                 blk2->index = blk1->index - be16_to_cpu(leaf1->hdr.count);
1375                 args->index = args->index2 = blk2->index;
1376                 args->blkno = args->blkno2 = blk2->blkno;
1377         } else if (blk1->index == be16_to_cpu(leaf1->hdr.count)) {
1378                 if (state->inleaf) {
1379                         args->index = blk1->index;
1380                         args->blkno = blk1->blkno;
1381                         args->index2 = 0;
1382                         args->blkno2 = blk2->blkno;
1383                 } else {
1384                         blk2->index = blk1->index
1385                                     - be16_to_cpu(leaf1->hdr.count);
1386                         args->index = args->index2 = blk2->index;
1387                         args->blkno = args->blkno2 = blk2->blkno;
1388                 }
1389         } else {
1390                 ASSERT(state->inleaf == 1);
1391                 args->index = args->index2 = blk1->index;
1392                 args->blkno = args->blkno2 = blk1->blkno;
1393         }
1394 }
1395
1396 /*
1397  * Examine entries until we reduce the absolute difference in
1398  * byte usage between the two blocks to a minimum.
1399  * GROT: Is this really necessary?  With other than a 512 byte blocksize,
1400  * GROT: there will always be enough room in either block for a new entry.
1401  * GROT: Do a double-split for this case?
1402  */
1403 STATIC int
1404 xfs_attr_leaf_figure_balance(xfs_da_state_t *state,
1405                                     xfs_da_state_blk_t *blk1,
1406                                     xfs_da_state_blk_t *blk2,
1407                                     int *countarg, int *usedbytesarg)
1408 {
1409         xfs_attr_leafblock_t *leaf1, *leaf2;
1410         xfs_attr_leaf_hdr_t *hdr1, *hdr2;
1411         xfs_attr_leaf_entry_t *entry;
1412         int count, max, index, totallen, half;
1413         int lastdelta, foundit, tmp;
1414
1415         /*
1416          * Set up environment.
1417          */
1418         leaf1 = blk1->bp->data;
1419         leaf2 = blk2->bp->data;
1420         hdr1 = &leaf1->hdr;
1421         hdr2 = &leaf2->hdr;
1422         foundit = 0;
1423         totallen = 0;
1424
1425         /*
1426          * Examine entries until we reduce the absolute difference in
1427          * byte usage between the two blocks to a minimum.
1428          */
1429         max = be16_to_cpu(hdr1->count) + be16_to_cpu(hdr2->count);
1430         half  = (max+1) * sizeof(*entry);
1431         half += be16_to_cpu(hdr1->usedbytes) +
1432                 be16_to_cpu(hdr2->usedbytes) +
1433                 xfs_attr_leaf_newentsize(
1434                                 state->args->namelen,
1435                                 state->args->valuelen,
1436                                 state->blocksize, NULL);
1437         half /= 2;
1438         lastdelta = state->blocksize;
1439         entry = &leaf1->entries[0];
1440         for (count = index = 0; count < max; entry++, index++, count++) {
1441
1442 #define XFS_ATTR_ABS(A) (((A) < 0) ? -(A) : (A))
1443                 /*
1444                  * The new entry is in the first block, account for it.
1445                  */
1446                 if (count == blk1->index) {
1447                         tmp = totallen + sizeof(*entry) +
1448                                 xfs_attr_leaf_newentsize(
1449                                                 state->args->namelen,
1450                                                 state->args->valuelen,
1451                                                 state->blocksize, NULL);
1452                         if (XFS_ATTR_ABS(half - tmp) > lastdelta)
1453                                 break;
1454                         lastdelta = XFS_ATTR_ABS(half - tmp);
1455                         totallen = tmp;
1456                         foundit = 1;
1457                 }
1458
1459                 /*
1460                  * Wrap around into the second block if necessary.
1461                  */
1462                 if (count == be16_to_cpu(hdr1->count)) {
1463                         leaf1 = leaf2;
1464                         entry = &leaf1->entries[0];
1465                         index = 0;
1466                 }
1467
1468                 /*
1469                  * Figure out if next leaf entry would be too much.
1470                  */
1471                 tmp = totallen + sizeof(*entry) + xfs_attr_leaf_entsize(leaf1,
1472                                                                         index);
1473                 if (XFS_ATTR_ABS(half - tmp) > lastdelta)
1474                         break;
1475                 lastdelta = XFS_ATTR_ABS(half - tmp);
1476                 totallen = tmp;
1477 #undef XFS_ATTR_ABS
1478         }
1479
1480         /*
1481          * Calculate the number of usedbytes that will end up in lower block.
1482          * If new entry not in lower block, fix up the count.
1483          */
1484         totallen -= count * sizeof(*entry);
1485         if (foundit) {
1486                 totallen -= sizeof(*entry) +
1487                                 xfs_attr_leaf_newentsize(
1488                                                 state->args->namelen,
1489                                                 state->args->valuelen,
1490                                                 state->blocksize, NULL);
1491         }
1492
1493         *countarg = count;
1494         *usedbytesarg = totallen;
1495         return(foundit);
1496 }
1497
1498 /*========================================================================
1499  * Routines used for shrinking the Btree.
1500  *========================================================================*/
1501
1502 /*
1503  * Check a leaf block and its neighbors to see if the block should be
1504  * collapsed into one or the other neighbor.  Always keep the block
1505  * with the smaller block number.
1506  * If the current block is over 50% full, don't try to join it, return 0.
1507  * If the block is empty, fill in the state structure and return 2.
1508  * If it can be collapsed, fill in the state structure and return 1.
1509  * If nothing can be done, return 0.
1510  *
1511  * GROT: allow for INCOMPLETE entries in calculation.
1512  */
1513 int
1514 xfs_attr_leaf_toosmall(xfs_da_state_t *state, int *action)
1515 {
1516         xfs_attr_leafblock_t *leaf;
1517         xfs_da_state_blk_t *blk;
1518         xfs_da_blkinfo_t *info;
1519         int count, bytes, forward, error, retval, i;
1520         xfs_dablk_t blkno;
1521         xfs_dabuf_t *bp;
1522
1523         /*
1524          * Check for the degenerate case of the block being over 50% full.
1525          * If so, it's not worth even looking to see if we might be able
1526          * to coalesce with a sibling.
1527          */
1528         blk = &state->path.blk[ state->path.active-1 ];
1529         info = blk->bp->data;
1530         ASSERT(be16_to_cpu(info->magic) == XFS_ATTR_LEAF_MAGIC);
1531         leaf = (xfs_attr_leafblock_t *)info;
1532         count = be16_to_cpu(leaf->hdr.count);
1533         bytes = sizeof(xfs_attr_leaf_hdr_t) +
1534                 count * sizeof(xfs_attr_leaf_entry_t) +
1535                 be16_to_cpu(leaf->hdr.usedbytes);
1536         if (bytes > (state->blocksize >> 1)) {
1537                 *action = 0;    /* blk over 50%, don't try to join */
1538                 return(0);
1539         }
1540
1541         /*
1542          * Check for the degenerate case of the block being empty.
1543          * If the block is empty, we'll simply delete it, no need to
1544          * coalesce it with a sibling block.  We choose (arbitrarily)
1545          * to merge with the forward block unless it is NULL.
1546          */
1547         if (count == 0) {
1548                 /*
1549                  * Make altpath point to the block we want to keep and
1550                  * path point to the block we want to drop (this one).
1551                  */
1552                 forward = (info->forw != 0);
1553                 memcpy(&state->altpath, &state->path, sizeof(state->path));
1554                 error = xfs_da_path_shift(state, &state->altpath, forward,
1555                                                  0, &retval);
1556                 if (error)
1557                         return(error);
1558                 if (retval) {
1559                         *action = 0;
1560                 } else {
1561                         *action = 2;
1562                 }
1563                 return(0);
1564         }
1565
1566         /*
1567          * Examine each sibling block to see if we can coalesce with
1568          * at least 25% free space to spare.  We need to figure out
1569          * whether to merge with the forward or the backward block.
1570          * We prefer coalescing with the lower numbered sibling so as
1571          * to shrink an attribute list over time.
1572          */
1573         /* start with smaller blk num */
1574         forward = (be32_to_cpu(info->forw) < be32_to_cpu(info->back));
1575         for (i = 0; i < 2; forward = !forward, i++) {
1576                 if (forward)
1577                         blkno = be32_to_cpu(info->forw);
1578                 else
1579                         blkno = be32_to_cpu(info->back);
1580                 if (blkno == 0)
1581                         continue;
1582                 error = xfs_da_read_buf(state->args->trans, state->args->dp,
1583                                         blkno, -1, &bp, XFS_ATTR_FORK);
1584                 if (error)
1585                         return(error);
1586                 ASSERT(bp != NULL);
1587
1588                 leaf = (xfs_attr_leafblock_t *)info;
1589                 count  = be16_to_cpu(leaf->hdr.count);
1590                 bytes  = state->blocksize - (state->blocksize>>2);
1591                 bytes -= be16_to_cpu(leaf->hdr.usedbytes);
1592                 leaf = bp->data;
1593                 ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1594                 count += be16_to_cpu(leaf->hdr.count);
1595                 bytes -= be16_to_cpu(leaf->hdr.usedbytes);
1596                 bytes -= count * sizeof(xfs_attr_leaf_entry_t);
1597                 bytes -= sizeof(xfs_attr_leaf_hdr_t);
1598                 xfs_da_brelse(state->args->trans, bp);
1599                 if (bytes >= 0)
1600                         break;  /* fits with at least 25% to spare */
1601         }
1602         if (i >= 2) {
1603                 *action = 0;
1604                 return(0);
1605         }
1606
1607         /*
1608          * Make altpath point to the block we want to keep (the lower
1609          * numbered block) and path point to the block we want to drop.
1610          */
1611         memcpy(&state->altpath, &state->path, sizeof(state->path));
1612         if (blkno < blk->blkno) {
1613                 error = xfs_da_path_shift(state, &state->altpath, forward,
1614                                                  0, &retval);
1615         } else {
1616                 error = xfs_da_path_shift(state, &state->path, forward,
1617                                                  0, &retval);
1618         }
1619         if (error)
1620                 return(error);
1621         if (retval) {
1622                 *action = 0;
1623         } else {
1624                 *action = 1;
1625         }
1626         return(0);
1627 }
1628
1629 /*
1630  * Remove a name from the leaf attribute list structure.
1631  *
1632  * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
1633  * If two leaves are 37% full, when combined they will leave 25% free.
1634  */
1635 int
1636 xfs_attr_leaf_remove(xfs_dabuf_t *bp, xfs_da_args_t *args)
1637 {
1638         xfs_attr_leafblock_t *leaf;
1639         xfs_attr_leaf_hdr_t *hdr;
1640         xfs_attr_leaf_map_t *map;
1641         xfs_attr_leaf_entry_t *entry;
1642         int before, after, smallest, entsize;
1643         int tablesize, tmp, i;
1644         xfs_mount_t *mp;
1645
1646         leaf = bp->data;
1647         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1648         hdr = &leaf->hdr;
1649         mp = args->trans->t_mountp;
1650         ASSERT((be16_to_cpu(hdr->count) > 0)
1651                 && (be16_to_cpu(hdr->count) < (XFS_LBSIZE(mp)/8)));
1652         ASSERT((args->index >= 0)
1653                 && (args->index < be16_to_cpu(hdr->count)));
1654         ASSERT(be16_to_cpu(hdr->firstused) >=
1655                ((be16_to_cpu(hdr->count) * sizeof(*entry)) + sizeof(*hdr)));
1656         entry = &leaf->entries[args->index];
1657         ASSERT(be16_to_cpu(entry->nameidx) >= be16_to_cpu(hdr->firstused));
1658         ASSERT(be16_to_cpu(entry->nameidx) < XFS_LBSIZE(mp));
1659
1660         /*
1661          * Scan through free region table:
1662          *    check for adjacency of free'd entry with an existing one,
1663          *    find smallest free region in case we need to replace it,
1664          *    adjust any map that borders the entry table,
1665          */
1666         tablesize = be16_to_cpu(hdr->count) * sizeof(xfs_attr_leaf_entry_t)
1667                                         + sizeof(xfs_attr_leaf_hdr_t);
1668         map = &hdr->freemap[0];
1669         tmp = be16_to_cpu(map->size);
1670         before = after = -1;
1671         smallest = XFS_ATTR_LEAF_MAPSIZE - 1;
1672         entsize = xfs_attr_leaf_entsize(leaf, args->index);
1673         for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; map++, i++) {
1674                 ASSERT(be16_to_cpu(map->base) < XFS_LBSIZE(mp));
1675                 ASSERT(be16_to_cpu(map->size) < XFS_LBSIZE(mp));
1676                 if (be16_to_cpu(map->base) == tablesize) {
1677                         be16_add(&map->base,
1678                                  -((int)sizeof(xfs_attr_leaf_entry_t)));
1679                         be16_add(&map->size, sizeof(xfs_attr_leaf_entry_t));
1680                 }
1681
1682                 if ((be16_to_cpu(map->base) + be16_to_cpu(map->size))
1683                                 == be16_to_cpu(entry->nameidx)) {
1684                         before = i;
1685                 } else if (be16_to_cpu(map->base)
1686                         == (be16_to_cpu(entry->nameidx) + entsize)) {
1687                         after = i;
1688                 } else if (be16_to_cpu(map->size) < tmp) {
1689                         tmp = be16_to_cpu(map->size);
1690                         smallest = i;
1691                 }
1692         }
1693
1694         /*
1695          * Coalesce adjacent freemap regions,
1696          * or replace the smallest region.
1697          */
1698         if ((before >= 0) || (after >= 0)) {
1699                 if ((before >= 0) && (after >= 0)) {
1700                         map = &hdr->freemap[before];
1701                         be16_add(&map->size, entsize);
1702                         be16_add(&map->size,
1703                                  be16_to_cpu(hdr->freemap[after].size));
1704                         hdr->freemap[after].base = 0;
1705                         hdr->freemap[after].size = 0;
1706                 } else if (before >= 0) {
1707                         map = &hdr->freemap[before];
1708                         be16_add(&map->size, entsize);
1709                 } else {
1710                         map = &hdr->freemap[after];
1711                         /* both on-disk, don't endian flip twice */
1712                         map->base = entry->nameidx;
1713                         be16_add(&map->size, entsize);
1714                 }
1715         } else {
1716                 /*
1717                  * Replace smallest region (if it is smaller than free'd entry)
1718                  */
1719                 map = &hdr->freemap[smallest];
1720                 if (be16_to_cpu(map->size) < entsize) {
1721                         map->base = cpu_to_be16(be16_to_cpu(entry->nameidx));
1722                         map->size = cpu_to_be16(entsize);
1723                 }
1724         }
1725
1726         /*
1727          * Did we remove the first entry?
1728          */
1729         if (be16_to_cpu(entry->nameidx) == be16_to_cpu(hdr->firstused))
1730                 smallest = 1;
1731         else
1732                 smallest = 0;
1733
1734         /*
1735          * Compress the remaining entries and zero out the removed stuff.
1736          */
1737         memset(XFS_ATTR_LEAF_NAME(leaf, args->index), 0, entsize);
1738         be16_add(&hdr->usedbytes, -entsize);
1739         xfs_da_log_buf(args->trans, bp,
1740              XFS_DA_LOGRANGE(leaf, XFS_ATTR_LEAF_NAME(leaf, args->index),
1741                                    entsize));
1742
1743         tmp = (be16_to_cpu(hdr->count) - args->index)
1744                                         * sizeof(xfs_attr_leaf_entry_t);
1745         memmove((char *)entry, (char *)(entry+1), tmp);
1746         be16_add(&hdr->count, -1);
1747         xfs_da_log_buf(args->trans, bp,
1748             XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(*entry)));
1749         entry = &leaf->entries[be16_to_cpu(hdr->count)];
1750         memset((char *)entry, 0, sizeof(xfs_attr_leaf_entry_t));
1751
1752         /*
1753          * If we removed the first entry, re-find the first used byte
1754          * in the name area.  Note that if the entry was the "firstused",
1755          * then we don't have a "hole" in our block resulting from
1756          * removing the name.
1757          */
1758         if (smallest) {
1759                 tmp = XFS_LBSIZE(mp);
1760                 entry = &leaf->entries[0];
1761                 for (i = be16_to_cpu(hdr->count)-1; i >= 0; entry++, i--) {
1762                         ASSERT(be16_to_cpu(entry->nameidx) >=
1763                                be16_to_cpu(hdr->firstused));
1764                         ASSERT(be16_to_cpu(entry->nameidx) < XFS_LBSIZE(mp));
1765
1766                         if (be16_to_cpu(entry->nameidx) < tmp)
1767                                 tmp = be16_to_cpu(entry->nameidx);
1768                 }
1769                 hdr->firstused = cpu_to_be16(tmp);
1770                 if (!hdr->firstused) {
1771                         hdr->firstused = cpu_to_be16(
1772                                         tmp - XFS_ATTR_LEAF_NAME_ALIGN);
1773                 }
1774         } else {
1775                 hdr->holes = 1;         /* mark as needing compaction */
1776         }
1777         xfs_da_log_buf(args->trans, bp,
1778                           XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));
1779
1780         /*
1781          * Check if leaf is less than 50% full, caller may want to
1782          * "join" the leaf with a sibling if so.
1783          */
1784         tmp  = sizeof(xfs_attr_leaf_hdr_t);
1785         tmp += be16_to_cpu(leaf->hdr.count) * sizeof(xfs_attr_leaf_entry_t);
1786         tmp += be16_to_cpu(leaf->hdr.usedbytes);
1787         return(tmp < mp->m_attr_magicpct); /* leaf is < 37% full */
1788 }
1789
1790 /*
1791  * Move all the attribute list entries from drop_leaf into save_leaf.
1792  */
1793 void
1794 xfs_attr_leaf_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
1795                                        xfs_da_state_blk_t *save_blk)
1796 {
1797         xfs_attr_leafblock_t *drop_leaf, *save_leaf, *tmp_leaf;
1798         xfs_attr_leaf_hdr_t *drop_hdr, *save_hdr, *tmp_hdr;
1799         xfs_mount_t *mp;
1800         char *tmpbuffer;
1801
1802         /*
1803          * Set up environment.
1804          */
1805         mp = state->mp;
1806         ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC);
1807         ASSERT(save_blk->magic == XFS_ATTR_LEAF_MAGIC);
1808         drop_leaf = drop_blk->bp->data;
1809         save_leaf = save_blk->bp->data;
1810         ASSERT(be16_to_cpu(drop_leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1811         ASSERT(be16_to_cpu(save_leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1812         drop_hdr = &drop_leaf->hdr;
1813         save_hdr = &save_leaf->hdr;
1814
1815         /*
1816          * Save last hashval from dying block for later Btree fixup.
1817          */
1818         drop_blk->hashval = be32_to_cpu(
1819                 drop_leaf->entries[be16_to_cpu(drop_leaf->hdr.count)-1].hashval);
1820
1821         /*
1822          * Check if we need a temp buffer, or can we do it in place.
1823          * Note that we don't check "leaf" for holes because we will
1824          * always be dropping it, toosmall() decided that for us already.
1825          */
1826         if (save_hdr->holes == 0) {
1827                 /*
1828                  * dest leaf has no holes, so we add there.  May need
1829                  * to make some room in the entry array.
1830                  */
1831                 if (xfs_attr_leaf_order(save_blk->bp, drop_blk->bp)) {
1832                         xfs_attr_leaf_moveents(drop_leaf, 0, save_leaf, 0,
1833                              be16_to_cpu(drop_hdr->count), mp);
1834                 } else {
1835                         xfs_attr_leaf_moveents(drop_leaf, 0, save_leaf,
1836                                   be16_to_cpu(save_hdr->count),
1837                                   be16_to_cpu(drop_hdr->count), mp);
1838                 }
1839         } else {
1840                 /*
1841                  * Destination has holes, so we make a temporary copy
1842                  * of the leaf and add them both to that.
1843                  */
1844                 tmpbuffer = kmem_alloc(state->blocksize, KM_SLEEP);
1845                 ASSERT(tmpbuffer != NULL);
1846                 memset(tmpbuffer, 0, state->blocksize);
1847                 tmp_leaf = (xfs_attr_leafblock_t *)tmpbuffer;
1848                 tmp_hdr = &tmp_leaf->hdr;
1849                 tmp_hdr->info = save_hdr->info; /* struct copy */
1850                 tmp_hdr->count = 0;
1851                 tmp_hdr->firstused = cpu_to_be16(state->blocksize);
1852                 if (!tmp_hdr->firstused) {
1853                         tmp_hdr->firstused = cpu_to_be16(
1854                                 state->blocksize - XFS_ATTR_LEAF_NAME_ALIGN);
1855                 }
1856                 tmp_hdr->usedbytes = 0;
1857                 if (xfs_attr_leaf_order(save_blk->bp, drop_blk->bp)) {
1858                         xfs_attr_leaf_moveents(drop_leaf, 0, tmp_leaf, 0,
1859                                 be16_to_cpu(drop_hdr->count), mp);
1860                         xfs_attr_leaf_moveents(save_leaf, 0, tmp_leaf,
1861                                   be16_to_cpu(tmp_leaf->hdr.count),
1862                                   be16_to_cpu(save_hdr->count), mp);
1863                 } else {
1864                         xfs_attr_leaf_moveents(save_leaf, 0, tmp_leaf, 0,
1865                                 be16_to_cpu(save_hdr->count), mp);
1866                         xfs_attr_leaf_moveents(drop_leaf, 0, tmp_leaf,
1867                                 be16_to_cpu(tmp_leaf->hdr.count),
1868                                 be16_to_cpu(drop_hdr->count), mp);
1869                 }
1870                 memcpy((char *)save_leaf, (char *)tmp_leaf, state->blocksize);
1871                 kmem_free(tmpbuffer, state->blocksize);
1872         }
1873
1874         xfs_da_log_buf(state->args->trans, save_blk->bp, 0,
1875                                            state->blocksize - 1);
1876
1877         /*
1878          * Copy out last hashval in each block for B-tree code.
1879          */
1880         save_blk->hashval = be32_to_cpu(
1881                 save_leaf->entries[be16_to_cpu(save_leaf->hdr.count)-1].hashval);
1882 }
1883
1884 /*========================================================================
1885  * Routines used for finding things in the Btree.
1886  *========================================================================*/
1887
1888 /*
1889  * Look up a name in a leaf attribute list structure.
1890  * This is the internal routine, it uses the caller's buffer.
1891  *
1892  * Note that duplicate keys are allowed, but only check within the
1893  * current leaf node.  The Btree code must check in adjacent leaf nodes.
1894  *
1895  * Return in args->index the index into the entry[] array of either
1896  * the found entry, or where the entry should have been (insert before
1897  * that entry).
1898  *
1899  * Don't change the args->value unless we find the attribute.
1900  */
1901 int
1902 xfs_attr_leaf_lookup_int(xfs_dabuf_t *bp, xfs_da_args_t *args)
1903 {
1904         xfs_attr_leafblock_t *leaf;
1905         xfs_attr_leaf_entry_t *entry;
1906         xfs_attr_leaf_name_local_t *name_loc;
1907         xfs_attr_leaf_name_remote_t *name_rmt;
1908         int probe, span;
1909         xfs_dahash_t hashval;
1910
1911         leaf = bp->data;
1912         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
1913         ASSERT(be16_to_cpu(leaf->hdr.count)
1914                                         < (XFS_LBSIZE(args->dp->i_mount)/8));
1915
1916         /*
1917          * Binary search.  (note: small blocks will skip this loop)
1918          */
1919         hashval = args->hashval;
1920         probe = span = be16_to_cpu(leaf->hdr.count) / 2;
1921         for (entry = &leaf->entries[probe]; span > 4;
1922                    entry = &leaf->entries[probe]) {
1923                 span /= 2;
1924                 if (be32_to_cpu(entry->hashval) < hashval)
1925                         probe += span;
1926                 else if (be32_to_cpu(entry->hashval) > hashval)
1927                         probe -= span;
1928                 else
1929                         break;
1930         }
1931         ASSERT((probe >= 0) && 
1932                (!leaf->hdr.count
1933                || (probe < be16_to_cpu(leaf->hdr.count))));
1934         ASSERT((span <= 4) || (be32_to_cpu(entry->hashval) == hashval));
1935
1936         /*
1937          * Since we may have duplicate hashval's, find the first matching
1938          * hashval in the leaf.
1939          */
1940         while ((probe > 0) && (be32_to_cpu(entry->hashval) >= hashval)) {
1941                 entry--;
1942                 probe--;
1943         }
1944         while ((probe < be16_to_cpu(leaf->hdr.count)) &&
1945                (be32_to_cpu(entry->hashval) < hashval)) {
1946                 entry++;
1947                 probe++;
1948         }
1949         if ((probe == be16_to_cpu(leaf->hdr.count)) ||
1950             (be32_to_cpu(entry->hashval) != hashval)) {
1951                 args->index = probe;
1952                 return(XFS_ERROR(ENOATTR));
1953         }
1954
1955         /*
1956          * Duplicate keys may be present, so search all of them for a match.
1957          */
1958         for (  ; (probe < be16_to_cpu(leaf->hdr.count)) &&
1959                         (be32_to_cpu(entry->hashval) == hashval);
1960                         entry++, probe++) {
1961 /*
1962  * GROT: Add code to remove incomplete entries.
1963  */
1964                 /*
1965                  * If we are looking for INCOMPLETE entries, show only those.
1966                  * If we are looking for complete entries, show only those.
1967                  */
1968                 if ((args->flags & XFS_ATTR_INCOMPLETE) !=
1969                     (entry->flags & XFS_ATTR_INCOMPLETE)) {
1970                         continue;
1971                 }
1972                 if (entry->flags & XFS_ATTR_LOCAL) {
1973                         name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, probe);
1974                         if (name_loc->namelen != args->namelen)
1975                                 continue;
1976                         if (memcmp(args->name, (char *)name_loc->nameval,
1977                                              args->namelen) != 0)
1978                                 continue;
1979                         if (((args->flags & ATTR_SECURE) != 0) !=
1980                             ((entry->flags & XFS_ATTR_SECURE) != 0))
1981                                 continue;
1982                         if (((args->flags & ATTR_ROOT) != 0) !=
1983                             ((entry->flags & XFS_ATTR_ROOT) != 0))
1984                                 continue;
1985                         args->index = probe;
1986                         return(XFS_ERROR(EEXIST));
1987                 } else {
1988                         name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, probe);
1989                         if (name_rmt->namelen != args->namelen)
1990                                 continue;
1991                         if (memcmp(args->name, (char *)name_rmt->name,
1992                                              args->namelen) != 0)
1993                                 continue;
1994                         if (((args->flags & ATTR_SECURE) != 0) !=
1995                             ((entry->flags & XFS_ATTR_SECURE) != 0))
1996                                 continue;
1997                         if (((args->flags & ATTR_ROOT) != 0) !=
1998                             ((entry->flags & XFS_ATTR_ROOT) != 0))
1999                                 continue;
2000                         args->index = probe;
2001                         args->rmtblkno = be32_to_cpu(name_rmt->valueblk);
2002                         args->rmtblkcnt = XFS_B_TO_FSB(args->dp->i_mount,
2003                                                    be32_to_cpu(name_rmt->valuelen));
2004                         return(XFS_ERROR(EEXIST));
2005                 }
2006         }
2007         args->index = probe;
2008         return(XFS_ERROR(ENOATTR));
2009 }
2010
2011 /*
2012  * Get the value associated with an attribute name from a leaf attribute
2013  * list structure.
2014  */
2015 int
2016 xfs_attr_leaf_getvalue(xfs_dabuf_t *bp, xfs_da_args_t *args)
2017 {
2018         int valuelen;
2019         xfs_attr_leafblock_t *leaf;
2020         xfs_attr_leaf_entry_t *entry;
2021         xfs_attr_leaf_name_local_t *name_loc;
2022         xfs_attr_leaf_name_remote_t *name_rmt;
2023
2024         leaf = bp->data;
2025         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2026         ASSERT(be16_to_cpu(leaf->hdr.count)
2027                                         < (XFS_LBSIZE(args->dp->i_mount)/8));
2028         ASSERT(args->index < be16_to_cpu(leaf->hdr.count));
2029
2030         entry = &leaf->entries[args->index];
2031         if (entry->flags & XFS_ATTR_LOCAL) {
2032                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, args->index);
2033                 ASSERT(name_loc->namelen == args->namelen);
2034                 ASSERT(memcmp(args->name, name_loc->nameval, args->namelen) == 0);
2035                 valuelen = be16_to_cpu(name_loc->valuelen);
2036                 if (args->flags & ATTR_KERNOVAL) {
2037                         args->valuelen = valuelen;
2038                         return(0);
2039                 }
2040                 if (args->valuelen < valuelen) {
2041                         args->valuelen = valuelen;
2042                         return(XFS_ERROR(ERANGE));
2043                 }
2044                 args->valuelen = valuelen;
2045                 memcpy(args->value, &name_loc->nameval[args->namelen], valuelen);
2046         } else {
2047                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, args->index);
2048                 ASSERT(name_rmt->namelen == args->namelen);
2049                 ASSERT(memcmp(args->name, name_rmt->name, args->namelen) == 0);
2050                 valuelen = be32_to_cpu(name_rmt->valuelen);
2051                 args->rmtblkno = be32_to_cpu(name_rmt->valueblk);
2052                 args->rmtblkcnt = XFS_B_TO_FSB(args->dp->i_mount, valuelen);
2053                 if (args->flags & ATTR_KERNOVAL) {
2054                         args->valuelen = valuelen;
2055                         return(0);
2056                 }
2057                 if (args->valuelen < valuelen) {
2058                         args->valuelen = valuelen;
2059                         return(XFS_ERROR(ERANGE));
2060                 }
2061                 args->valuelen = valuelen;
2062         }
2063         return(0);
2064 }
2065
2066 /*========================================================================
2067  * Utility routines.
2068  *========================================================================*/
2069
2070 /*
2071  * Move the indicated entries from one leaf to another.
2072  * NOTE: this routine modifies both source and destination leaves.
2073  */
2074 /*ARGSUSED*/
2075 STATIC void
2076 xfs_attr_leaf_moveents(xfs_attr_leafblock_t *leaf_s, int start_s,
2077                         xfs_attr_leafblock_t *leaf_d, int start_d,
2078                         int count, xfs_mount_t *mp)
2079 {
2080         xfs_attr_leaf_hdr_t *hdr_s, *hdr_d;
2081         xfs_attr_leaf_entry_t *entry_s, *entry_d;
2082         int desti, tmp, i;
2083
2084         /*
2085          * Check for nothing to do.
2086          */
2087         if (count == 0)
2088                 return;
2089
2090         /*
2091          * Set up environment.
2092          */
2093         ASSERT(be16_to_cpu(leaf_s->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2094         ASSERT(be16_to_cpu(leaf_d->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2095         hdr_s = &leaf_s->hdr;
2096         hdr_d = &leaf_d->hdr;
2097         ASSERT((be16_to_cpu(hdr_s->count) > 0) &&
2098                (be16_to_cpu(hdr_s->count) < (XFS_LBSIZE(mp)/8)));
2099         ASSERT(be16_to_cpu(hdr_s->firstused) >=
2100                 ((be16_to_cpu(hdr_s->count)
2101                                         * sizeof(*entry_s))+sizeof(*hdr_s)));
2102         ASSERT(be16_to_cpu(hdr_d->count) < (XFS_LBSIZE(mp)/8));
2103         ASSERT(be16_to_cpu(hdr_d->firstused) >=
2104                 ((be16_to_cpu(hdr_d->count)
2105                                         * sizeof(*entry_d))+sizeof(*hdr_d)));
2106
2107         ASSERT(start_s < be16_to_cpu(hdr_s->count));
2108         ASSERT(start_d <= be16_to_cpu(hdr_d->count));
2109         ASSERT(count <= be16_to_cpu(hdr_s->count));
2110
2111         /*
2112          * Move the entries in the destination leaf up to make a hole?
2113          */
2114         if (start_d < be16_to_cpu(hdr_d->count)) {
2115                 tmp  = be16_to_cpu(hdr_d->count) - start_d;
2116                 tmp *= sizeof(xfs_attr_leaf_entry_t);
2117                 entry_s = &leaf_d->entries[start_d];
2118                 entry_d = &leaf_d->entries[start_d + count];
2119                 memmove((char *)entry_d, (char *)entry_s, tmp);
2120         }
2121
2122         /*
2123          * Copy all entry's in the same (sorted) order,
2124          * but allocate attribute info packed and in sequence.
2125          */
2126         entry_s = &leaf_s->entries[start_s];
2127         entry_d = &leaf_d->entries[start_d];
2128         desti = start_d;
2129         for (i = 0; i < count; entry_s++, entry_d++, desti++, i++) {
2130                 ASSERT(be16_to_cpu(entry_s->nameidx)
2131                                 >= be16_to_cpu(hdr_s->firstused));
2132                 tmp = xfs_attr_leaf_entsize(leaf_s, start_s + i);
2133 #ifdef GROT
2134                 /*
2135                  * Code to drop INCOMPLETE entries.  Difficult to use as we
2136                  * may also need to change the insertion index.  Code turned
2137                  * off for 6.2, should be revisited later.
2138                  */
2139                 if (entry_s->flags & XFS_ATTR_INCOMPLETE) { /* skip partials? */
2140                         memset(XFS_ATTR_LEAF_NAME(leaf_s, start_s + i), 0, tmp);
2141                         be16_add(&hdr_s->usedbytes, -tmp);
2142                         be16_add(&hdr_s->count, -1);
2143                         entry_d--;      /* to compensate for ++ in loop hdr */
2144                         desti--;
2145                         if ((start_s + i) < offset)
2146                                 result++;       /* insertion index adjustment */
2147                 } else {
2148 #endif /* GROT */
2149                         be16_add(&hdr_d->firstused, -tmp);
2150                         /* both on-disk, don't endian flip twice */
2151                         entry_d->hashval = entry_s->hashval;
2152                         /* both on-disk, don't endian flip twice */
2153                         entry_d->nameidx = hdr_d->firstused;
2154                         entry_d->flags = entry_s->flags;
2155                         ASSERT(be16_to_cpu(entry_d->nameidx) + tmp
2156                                                         <= XFS_LBSIZE(mp));
2157                         memmove(XFS_ATTR_LEAF_NAME(leaf_d, desti),
2158                                 XFS_ATTR_LEAF_NAME(leaf_s, start_s + i), tmp);
2159                         ASSERT(be16_to_cpu(entry_s->nameidx) + tmp
2160                                                         <= XFS_LBSIZE(mp));
2161                         memset(XFS_ATTR_LEAF_NAME(leaf_s, start_s + i), 0, tmp);
2162                         be16_add(&hdr_s->usedbytes, -tmp);
2163                         be16_add(&hdr_d->usedbytes, tmp);
2164                         be16_add(&hdr_s->count, -1);
2165                         be16_add(&hdr_d->count, 1);
2166                         tmp = be16_to_cpu(hdr_d->count)
2167                                                 * sizeof(xfs_attr_leaf_entry_t)
2168                                                 + sizeof(xfs_attr_leaf_hdr_t);
2169                         ASSERT(be16_to_cpu(hdr_d->firstused) >= tmp);
2170 #ifdef GROT
2171                 }
2172 #endif /* GROT */
2173         }
2174
2175         /*
2176          * Zero out the entries we just copied.
2177          */
2178         if (start_s == be16_to_cpu(hdr_s->count)) {
2179                 tmp = count * sizeof(xfs_attr_leaf_entry_t);
2180                 entry_s = &leaf_s->entries[start_s];
2181                 ASSERT(((char *)entry_s + tmp) <=
2182                        ((char *)leaf_s + XFS_LBSIZE(mp)));
2183                 memset((char *)entry_s, 0, tmp);
2184         } else {
2185                 /*
2186                  * Move the remaining entries down to fill the hole,
2187                  * then zero the entries at the top.
2188                  */
2189                 tmp  = be16_to_cpu(hdr_s->count) - count;
2190                 tmp *= sizeof(xfs_attr_leaf_entry_t);
2191                 entry_s = &leaf_s->entries[start_s + count];
2192                 entry_d = &leaf_s->entries[start_s];
2193                 memmove((char *)entry_d, (char *)entry_s, tmp);
2194
2195                 tmp = count * sizeof(xfs_attr_leaf_entry_t);
2196                 entry_s = &leaf_s->entries[be16_to_cpu(hdr_s->count)];
2197                 ASSERT(((char *)entry_s + tmp) <=
2198                        ((char *)leaf_s + XFS_LBSIZE(mp)));
2199                 memset((char *)entry_s, 0, tmp);
2200         }
2201
2202         /*
2203          * Fill in the freemap information
2204          */
2205         hdr_d->freemap[0].base = cpu_to_be16(sizeof(xfs_attr_leaf_hdr_t));
2206         be16_add(&hdr_d->freemap[0].base, be16_to_cpu(hdr_d->count) *
2207                         sizeof(xfs_attr_leaf_entry_t));
2208         hdr_d->freemap[0].size = cpu_to_be16(be16_to_cpu(hdr_d->firstused)
2209                               - be16_to_cpu(hdr_d->freemap[0].base));
2210         hdr_d->freemap[1].base = 0;
2211         hdr_d->freemap[2].base = 0;
2212         hdr_d->freemap[1].size = 0;
2213         hdr_d->freemap[2].size = 0;
2214         hdr_s->holes = 1;       /* leaf may not be compact */
2215 }
2216
2217 /*
2218  * Compare two leaf blocks "order".
2219  * Return 0 unless leaf2 should go before leaf1.
2220  */
2221 int
2222 xfs_attr_leaf_order(xfs_dabuf_t *leaf1_bp, xfs_dabuf_t *leaf2_bp)
2223 {
2224         xfs_attr_leafblock_t *leaf1, *leaf2;
2225
2226         leaf1 = leaf1_bp->data;
2227         leaf2 = leaf2_bp->data;
2228         ASSERT((be16_to_cpu(leaf1->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC) &&
2229                (be16_to_cpu(leaf2->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC));
2230         if ((be16_to_cpu(leaf1->hdr.count) > 0) &&
2231             (be16_to_cpu(leaf2->hdr.count) > 0) &&
2232             ((be32_to_cpu(leaf2->entries[0].hashval) <
2233               be32_to_cpu(leaf1->entries[0].hashval)) ||
2234              (be32_to_cpu(leaf2->entries[
2235                         be16_to_cpu(leaf2->hdr.count)-1].hashval) <
2236               be32_to_cpu(leaf1->entries[
2237                         be16_to_cpu(leaf1->hdr.count)-1].hashval)))) {
2238                 return(1);
2239         }
2240         return(0);
2241 }
2242
2243 /*
2244  * Pick up the last hashvalue from a leaf block.
2245  */
2246 xfs_dahash_t
2247 xfs_attr_leaf_lasthash(xfs_dabuf_t *bp, int *count)
2248 {
2249         xfs_attr_leafblock_t *leaf;
2250
2251         leaf = bp->data;
2252         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2253         if (count)
2254                 *count = be16_to_cpu(leaf->hdr.count);
2255         if (!leaf->hdr.count)
2256                 return(0);
2257         return be32_to_cpu(leaf->entries[be16_to_cpu(leaf->hdr.count)-1].hashval);
2258 }
2259
2260 /*
2261  * Calculate the number of bytes used to store the indicated attribute
2262  * (whether local or remote only calculate bytes in this block).
2263  */
2264 STATIC int
2265 xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index)
2266 {
2267         xfs_attr_leaf_name_local_t *name_loc;
2268         xfs_attr_leaf_name_remote_t *name_rmt;
2269         int size;
2270
2271         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2272         if (leaf->entries[index].flags & XFS_ATTR_LOCAL) {
2273                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, index);
2274                 size = XFS_ATTR_LEAF_ENTSIZE_LOCAL(name_loc->namelen,
2275                                                    be16_to_cpu(name_loc->valuelen));
2276         } else {
2277                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, index);
2278                 size = XFS_ATTR_LEAF_ENTSIZE_REMOTE(name_rmt->namelen);
2279         }
2280         return(size);
2281 }
2282
2283 /*
2284  * Calculate the number of bytes that would be required to store the new
2285  * attribute (whether local or remote only calculate bytes in this block).
2286  * This routine decides as a side effect whether the attribute will be
2287  * a "local" or a "remote" attribute.
2288  */
2289 int
2290 xfs_attr_leaf_newentsize(int namelen, int valuelen, int blocksize, int *local)
2291 {
2292         int size;
2293
2294         size = XFS_ATTR_LEAF_ENTSIZE_LOCAL(namelen, valuelen);
2295         if (size < XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX(blocksize)) {
2296                 if (local) {
2297                         *local = 1;
2298                 }
2299         } else {
2300                 size = XFS_ATTR_LEAF_ENTSIZE_REMOTE(namelen);
2301                 if (local) {
2302                         *local = 0;
2303                 }
2304         }
2305         return(size);
2306 }
2307
2308 /*
2309  * Copy out attribute list entries for attr_list(), for leaf attribute lists.
2310  */
2311 int
2312 xfs_attr_leaf_list_int(xfs_dabuf_t *bp, xfs_attr_list_context_t *context)
2313 {
2314         attrlist_cursor_kern_t *cursor;
2315         xfs_attr_leafblock_t *leaf;
2316         xfs_attr_leaf_entry_t *entry;
2317         xfs_attr_leaf_name_local_t *name_loc;
2318         xfs_attr_leaf_name_remote_t *name_rmt;
2319         int retval, i;
2320
2321         ASSERT(bp != NULL);
2322         leaf = bp->data;
2323         cursor = context->cursor;
2324         cursor->initted = 1;
2325
2326         xfs_attr_trace_l_cl("blk start", context, leaf);
2327
2328         /*
2329          * Re-find our place in the leaf block if this is a new syscall.
2330          */
2331         if (context->resynch) {
2332                 entry = &leaf->entries[0];
2333                 for (i = 0; i < be16_to_cpu(leaf->hdr.count); entry++, i++) {
2334                         if (be32_to_cpu(entry->hashval) == cursor->hashval) {
2335                                 if (cursor->offset == context->dupcnt) {
2336                                         context->dupcnt = 0;
2337                                         break;
2338                                 }
2339                                 context->dupcnt++;
2340                         } else if (be32_to_cpu(entry->hashval) >
2341                                         cursor->hashval) {
2342                                 context->dupcnt = 0;
2343                                 break;
2344                         }
2345                 }
2346                 if (i == be16_to_cpu(leaf->hdr.count)) {
2347                         xfs_attr_trace_l_c("not found", context);
2348                         return(0);
2349                 }
2350         } else {
2351                 entry = &leaf->entries[0];
2352                 i = 0;
2353         }
2354         context->resynch = 0;
2355
2356         /*
2357          * We have found our place, start copying out the new attributes.
2358          */
2359         retval = 0;
2360         for (  ; (i < be16_to_cpu(leaf->hdr.count))
2361              && (retval == 0); entry++, i++) {
2362                 attrnames_t     *namesp;
2363
2364                 if (be32_to_cpu(entry->hashval) != cursor->hashval) {
2365                         cursor->hashval = be32_to_cpu(entry->hashval);
2366                         cursor->offset = 0;
2367                 }
2368
2369                 if (entry->flags & XFS_ATTR_INCOMPLETE)
2370                         continue;               /* skip incomplete entries */
2371                 if (((context->flags & ATTR_SECURE) != 0) !=
2372                     ((entry->flags & XFS_ATTR_SECURE) != 0) &&
2373                     !(context->flags & ATTR_KERNORMALS))
2374                         continue;               /* skip non-matching entries */
2375                 if (((context->flags & ATTR_ROOT) != 0) !=
2376                     ((entry->flags & XFS_ATTR_ROOT) != 0) &&
2377                     !(context->flags & ATTR_KERNROOTLS))
2378                         continue;               /* skip non-matching entries */
2379
2380                 namesp = (entry->flags & XFS_ATTR_SECURE) ? &attr_secure :
2381                         ((entry->flags & XFS_ATTR_ROOT) ? &attr_trusted :
2382                           &attr_user);
2383
2384                 if (entry->flags & XFS_ATTR_LOCAL) {
2385                         name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, i);
2386                         if (context->flags & ATTR_KERNOVAL) {
2387                                 ASSERT(context->flags & ATTR_KERNAMELS);
2388                                 context->count += namesp->attr_namelen +
2389                                                 (int)name_loc->namelen + 1;
2390                         } else {
2391                                 retval = xfs_attr_put_listent(context, namesp,
2392                                         (char *)name_loc->nameval,
2393                                         (int)name_loc->namelen,
2394                                         be16_to_cpu(name_loc->valuelen));
2395                         }
2396                 } else {
2397                         name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, i);
2398                         if (context->flags & ATTR_KERNOVAL) {
2399                                 ASSERT(context->flags & ATTR_KERNAMELS);
2400                                 context->count += namesp->attr_namelen +
2401                                                 (int)name_rmt->namelen + 1;
2402                         } else {
2403                                 retval = xfs_attr_put_listent(context, namesp,
2404                                         (char *)name_rmt->name,
2405                                         (int)name_rmt->namelen,
2406                                         be32_to_cpu(name_rmt->valuelen));
2407                         }
2408                 }
2409                 if (retval == 0) {
2410                         cursor->offset++;
2411                 }
2412         }
2413         xfs_attr_trace_l_cl("blk end", context, leaf);
2414         return(retval);
2415 }
2416
2417 #define ATTR_ENTBASESIZE                /* minimum bytes used by an attr */ \
2418         (((struct attrlist_ent *) 0)->a_name - (char *) 0)
2419 #define ATTR_ENTSIZE(namelen)           /* actual bytes used by an attr */ \
2420         ((ATTR_ENTBASESIZE + (namelen) + 1 + sizeof(u_int32_t)-1) \
2421          & ~(sizeof(u_int32_t)-1))
2422
2423 /*
2424  * Format an attribute and copy it out to the user's buffer.
2425  * Take care to check values and protect against them changing later,
2426  * we may be reading them directly out of a user buffer.
2427  */
2428 /*ARGSUSED*/
2429 STATIC int
2430 xfs_attr_put_listent(xfs_attr_list_context_t *context,
2431                      attrnames_t *namesp, char *name, int namelen, int valuelen)
2432 {
2433         attrlist_ent_t *aep;
2434         int arraytop;
2435
2436         ASSERT(!(context->flags & ATTR_KERNOVAL));
2437         if (context->flags & ATTR_KERNAMELS) {
2438                 char *offset;
2439
2440                 ASSERT(context->count >= 0);
2441
2442                 arraytop = context->count + namesp->attr_namelen + namelen + 1;
2443                 if (arraytop > context->firstu) {
2444                         context->count = -1;    /* insufficient space */
2445                         return(1);
2446                 }
2447                 offset = (char *)context->alist + context->count;
2448                 strncpy(offset, namesp->attr_name, namesp->attr_namelen);
2449                 offset += namesp->attr_namelen;
2450                 strncpy(offset, name, namelen);                 /* real name */
2451                 offset += namelen;
2452                 *offset = '\0';
2453                 context->count += namesp->attr_namelen + namelen + 1;
2454                 return(0);
2455         }
2456
2457         ASSERT(context->count >= 0);
2458         ASSERT(context->count < (ATTR_MAX_VALUELEN/8));
2459         ASSERT(context->firstu >= sizeof(*context->alist));
2460         ASSERT(context->firstu <= context->bufsize);
2461
2462         arraytop = sizeof(*context->alist) +
2463                         context->count * sizeof(context->alist->al_offset[0]);
2464         context->firstu -= ATTR_ENTSIZE(namelen);
2465         if (context->firstu < arraytop) {
2466                 xfs_attr_trace_l_c("buffer full", context);
2467                 context->alist->al_more = 1;
2468                 return(1);
2469         }
2470
2471         aep = (attrlist_ent_t *)&(((char *)context->alist)[ context->firstu ]);
2472         aep->a_valuelen = valuelen;
2473         memcpy(aep->a_name, name, namelen);
2474         aep->a_name[ namelen ] = 0;
2475         context->alist->al_offset[ context->count++ ] = context->firstu;
2476         context->alist->al_count = context->count;
2477         xfs_attr_trace_l_c("add", context);
2478         return(0);
2479 }
2480
2481 /*========================================================================
2482  * Manage the INCOMPLETE flag in a leaf entry
2483  *========================================================================*/
2484
2485 /*
2486  * Clear the INCOMPLETE flag on an entry in a leaf block.
2487  */
2488 int
2489 xfs_attr_leaf_clearflag(xfs_da_args_t *args)
2490 {
2491         xfs_attr_leafblock_t *leaf;
2492         xfs_attr_leaf_entry_t *entry;
2493         xfs_attr_leaf_name_remote_t *name_rmt;
2494         xfs_dabuf_t *bp;
2495         int error;
2496 #ifdef DEBUG
2497         xfs_attr_leaf_name_local_t *name_loc;
2498         int namelen;
2499         char *name;
2500 #endif /* DEBUG */
2501
2502         /*
2503          * Set up the operation.
2504          */
2505         error = xfs_da_read_buf(args->trans, args->dp, args->blkno, -1, &bp,
2506                                              XFS_ATTR_FORK);
2507         if (error) {
2508                 return(error);
2509         }
2510         ASSERT(bp != NULL);
2511
2512         leaf = bp->data;
2513         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2514         ASSERT(args->index < be16_to_cpu(leaf->hdr.count));
2515         ASSERT(args->index >= 0);
2516         entry = &leaf->entries[ args->index ];
2517         ASSERT(entry->flags & XFS_ATTR_INCOMPLETE);
2518
2519 #ifdef DEBUG
2520         if (entry->flags & XFS_ATTR_LOCAL) {
2521                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf, args->index);
2522                 namelen = name_loc->namelen;
2523                 name = (char *)name_loc->nameval;
2524         } else {
2525                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, args->index);
2526                 namelen = name_rmt->namelen;
2527                 name = (char *)name_rmt->name;
2528         }
2529         ASSERT(be32_to_cpu(entry->hashval) == args->hashval);
2530         ASSERT(namelen == args->namelen);
2531         ASSERT(memcmp(name, args->name, namelen) == 0);
2532 #endif /* DEBUG */
2533
2534         entry->flags &= ~XFS_ATTR_INCOMPLETE;
2535         xfs_da_log_buf(args->trans, bp,
2536                          XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
2537
2538         if (args->rmtblkno) {
2539                 ASSERT((entry->flags & XFS_ATTR_LOCAL) == 0);
2540                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, args->index);
2541                 name_rmt->valueblk = cpu_to_be32(args->rmtblkno);
2542                 name_rmt->valuelen = cpu_to_be32(args->valuelen);
2543                 xfs_da_log_buf(args->trans, bp,
2544                          XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));
2545         }
2546         xfs_da_buf_done(bp);
2547
2548         /*
2549          * Commit the flag value change and start the next trans in series.
2550          */
2551         error = xfs_attr_rolltrans(&args->trans, args->dp);
2552
2553         return(error);
2554 }
2555
2556 /*
2557  * Set the INCOMPLETE flag on an entry in a leaf block.
2558  */
2559 int
2560 xfs_attr_leaf_setflag(xfs_da_args_t *args)
2561 {
2562         xfs_attr_leafblock_t *leaf;
2563         xfs_attr_leaf_entry_t *entry;
2564         xfs_attr_leaf_name_remote_t *name_rmt;
2565         xfs_dabuf_t *bp;
2566         int error;
2567
2568         /*
2569          * Set up the operation.
2570          */
2571         error = xfs_da_read_buf(args->trans, args->dp, args->blkno, -1, &bp,
2572                                              XFS_ATTR_FORK);
2573         if (error) {
2574                 return(error);
2575         }
2576         ASSERT(bp != NULL);
2577
2578         leaf = bp->data;
2579         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2580         ASSERT(args->index < be16_to_cpu(leaf->hdr.count));
2581         ASSERT(args->index >= 0);
2582         entry = &leaf->entries[ args->index ];
2583
2584         ASSERT((entry->flags & XFS_ATTR_INCOMPLETE) == 0);
2585         entry->flags |= XFS_ATTR_INCOMPLETE;
2586         xfs_da_log_buf(args->trans, bp,
2587                         XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
2588         if ((entry->flags & XFS_ATTR_LOCAL) == 0) {
2589                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, args->index);
2590                 name_rmt->valueblk = 0;
2591                 name_rmt->valuelen = 0;
2592                 xfs_da_log_buf(args->trans, bp,
2593                          XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));
2594         }
2595         xfs_da_buf_done(bp);
2596
2597         /*
2598          * Commit the flag value change and start the next trans in series.
2599          */
2600         error = xfs_attr_rolltrans(&args->trans, args->dp);
2601
2602         return(error);
2603 }
2604
2605 /*
2606  * In a single transaction, clear the INCOMPLETE flag on the leaf entry
2607  * given by args->blkno/index and set the INCOMPLETE flag on the leaf
2608  * entry given by args->blkno2/index2.
2609  *
2610  * Note that they could be in different blocks, or in the same block.
2611  */
2612 int
2613 xfs_attr_leaf_flipflags(xfs_da_args_t *args)
2614 {
2615         xfs_attr_leafblock_t *leaf1, *leaf2;
2616         xfs_attr_leaf_entry_t *entry1, *entry2;
2617         xfs_attr_leaf_name_remote_t *name_rmt;
2618         xfs_dabuf_t *bp1, *bp2;
2619         int error;
2620 #ifdef DEBUG
2621         xfs_attr_leaf_name_local_t *name_loc;
2622         int namelen1, namelen2;
2623         char *name1, *name2;
2624 #endif /* DEBUG */
2625
2626         /*
2627          * Read the block containing the "old" attr
2628          */
2629         error = xfs_da_read_buf(args->trans, args->dp, args->blkno, -1, &bp1,
2630                                              XFS_ATTR_FORK);
2631         if (error) {
2632                 return(error);
2633         }
2634         ASSERT(bp1 != NULL);
2635
2636         /*
2637          * Read the block containing the "new" attr, if it is different
2638          */
2639         if (args->blkno2 != args->blkno) {
2640                 error = xfs_da_read_buf(args->trans, args->dp, args->blkno2,
2641                                         -1, &bp2, XFS_ATTR_FORK);
2642                 if (error) {
2643                         return(error);
2644                 }
2645                 ASSERT(bp2 != NULL);
2646         } else {
2647                 bp2 = bp1;
2648         }
2649
2650         leaf1 = bp1->data;
2651         ASSERT(be16_to_cpu(leaf1->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2652         ASSERT(args->index < be16_to_cpu(leaf1->hdr.count));
2653         ASSERT(args->index >= 0);
2654         entry1 = &leaf1->entries[ args->index ];
2655
2656         leaf2 = bp2->data;
2657         ASSERT(be16_to_cpu(leaf2->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2658         ASSERT(args->index2 < be16_to_cpu(leaf2->hdr.count));
2659         ASSERT(args->index2 >= 0);
2660         entry2 = &leaf2->entries[ args->index2 ];
2661
2662 #ifdef DEBUG
2663         if (entry1->flags & XFS_ATTR_LOCAL) {
2664                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf1, args->index);
2665                 namelen1 = name_loc->namelen;
2666                 name1 = (char *)name_loc->nameval;
2667         } else {
2668                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf1, args->index);
2669                 namelen1 = name_rmt->namelen;
2670                 name1 = (char *)name_rmt->name;
2671         }
2672         if (entry2->flags & XFS_ATTR_LOCAL) {
2673                 name_loc = XFS_ATTR_LEAF_NAME_LOCAL(leaf2, args->index2);
2674                 namelen2 = name_loc->namelen;
2675                 name2 = (char *)name_loc->nameval;
2676         } else {
2677                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf2, args->index2);
2678                 namelen2 = name_rmt->namelen;
2679                 name2 = (char *)name_rmt->name;
2680         }
2681         ASSERT(be32_to_cpu(entry1->hashval) == be32_to_cpu(entry2->hashval));
2682         ASSERT(namelen1 == namelen2);
2683         ASSERT(memcmp(name1, name2, namelen1) == 0);
2684 #endif /* DEBUG */
2685
2686         ASSERT(entry1->flags & XFS_ATTR_INCOMPLETE);
2687         ASSERT((entry2->flags & XFS_ATTR_INCOMPLETE) == 0);
2688
2689         entry1->flags &= ~XFS_ATTR_INCOMPLETE;
2690         xfs_da_log_buf(args->trans, bp1,
2691                           XFS_DA_LOGRANGE(leaf1, entry1, sizeof(*entry1)));
2692         if (args->rmtblkno) {
2693                 ASSERT((entry1->flags & XFS_ATTR_LOCAL) == 0);
2694                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf1, args->index);
2695                 name_rmt->valueblk = cpu_to_be32(args->rmtblkno);
2696                 name_rmt->valuelen = cpu_to_be32(args->valuelen);
2697                 xfs_da_log_buf(args->trans, bp1,
2698                          XFS_DA_LOGRANGE(leaf1, name_rmt, sizeof(*name_rmt)));
2699         }
2700
2701         entry2->flags |= XFS_ATTR_INCOMPLETE;
2702         xfs_da_log_buf(args->trans, bp2,
2703                           XFS_DA_LOGRANGE(leaf2, entry2, sizeof(*entry2)));
2704         if ((entry2->flags & XFS_ATTR_LOCAL) == 0) {
2705                 name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf2, args->index2);
2706                 name_rmt->valueblk = 0;
2707                 name_rmt->valuelen = 0;
2708                 xfs_da_log_buf(args->trans, bp2,
2709                          XFS_DA_LOGRANGE(leaf2, name_rmt, sizeof(*name_rmt)));
2710         }
2711         xfs_da_buf_done(bp1);
2712         if (bp1 != bp2)
2713                 xfs_da_buf_done(bp2);
2714
2715         /*
2716          * Commit the flag value change and start the next trans in series.
2717          */
2718         error = xfs_attr_rolltrans(&args->trans, args->dp);
2719
2720         return(error);
2721 }
2722
2723 /*========================================================================
2724  * Indiscriminately delete the entire attribute fork
2725  *========================================================================*/
2726
2727 /*
2728  * Recurse (gasp!) through the attribute nodes until we find leaves.
2729  * We're doing a depth-first traversal in order to invalidate everything.
2730  */
2731 int
2732 xfs_attr_root_inactive(xfs_trans_t **trans, xfs_inode_t *dp)
2733 {
2734         xfs_da_blkinfo_t *info;
2735         xfs_daddr_t blkno;
2736         xfs_dabuf_t *bp;
2737         int error;
2738
2739         /*
2740          * Read block 0 to see what we have to work with.
2741          * We only get here if we have extents, since we remove
2742          * the extents in reverse order the extent containing
2743          * block 0 must still be there.
2744          */
2745         error = xfs_da_read_buf(*trans, dp, 0, -1, &bp, XFS_ATTR_FORK);
2746         if (error)
2747                 return(error);
2748         blkno = xfs_da_blkno(bp);
2749
2750         /*
2751          * Invalidate the tree, even if the "tree" is only a single leaf block.
2752          * This is a depth-first traversal!
2753          */
2754         info = bp->data;
2755         if (be16_to_cpu(info->magic) == XFS_DA_NODE_MAGIC) {
2756                 error = xfs_attr_node_inactive(trans, dp, bp, 1);
2757         } else if (be16_to_cpu(info->magic) == XFS_ATTR_LEAF_MAGIC) {
2758                 error = xfs_attr_leaf_inactive(trans, dp, bp);
2759         } else {
2760                 error = XFS_ERROR(EIO);
2761                 xfs_da_brelse(*trans, bp);
2762         }
2763         if (error)
2764                 return(error);
2765
2766         /*
2767          * Invalidate the incore copy of the root block.
2768          */
2769         error = xfs_da_get_buf(*trans, dp, 0, blkno, &bp, XFS_ATTR_FORK);
2770         if (error)
2771                 return(error);
2772         xfs_da_binval(*trans, bp);      /* remove from cache */
2773         /*
2774          * Commit the invalidate and start the next transaction.
2775          */
2776         error = xfs_attr_rolltrans(trans, dp);
2777
2778         return (error);
2779 }
2780
2781 /*
2782  * Recurse (gasp!) through the attribute nodes until we find leaves.
2783  * We're doing a depth-first traversal in order to invalidate everything.
2784  */
2785 STATIC int
2786 xfs_attr_node_inactive(xfs_trans_t **trans, xfs_inode_t *dp, xfs_dabuf_t *bp,
2787                                    int level)
2788 {
2789         xfs_da_blkinfo_t *info;
2790         xfs_da_intnode_t *node;
2791         xfs_dablk_t child_fsb;
2792         xfs_daddr_t parent_blkno, child_blkno;
2793         int error, count, i;
2794         xfs_dabuf_t *child_bp;
2795
2796         /*
2797          * Since this code is recursive (gasp!) we must protect ourselves.
2798          */
2799         if (level > XFS_DA_NODE_MAXDEPTH) {
2800                 xfs_da_brelse(*trans, bp);      /* no locks for later trans */
2801                 return(XFS_ERROR(EIO));
2802         }
2803
2804         node = bp->data;
2805         ASSERT(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC);
2806         parent_blkno = xfs_da_blkno(bp);        /* save for re-read later */
2807         count = be16_to_cpu(node->hdr.count);
2808         if (!count) {
2809                 xfs_da_brelse(*trans, bp);
2810                 return(0);
2811         }
2812         child_fsb = be32_to_cpu(node->btree[0].before);
2813         xfs_da_brelse(*trans, bp);      /* no locks for later trans */
2814
2815         /*
2816          * If this is the node level just above the leaves, simply loop
2817          * over the leaves removing all of them.  If this is higher up
2818          * in the tree, recurse downward.
2819          */
2820         for (i = 0; i < count; i++) {
2821                 /*
2822                  * Read the subsidiary block to see what we have to work with.
2823                  * Don't do this in a transaction.  This is a depth-first
2824                  * traversal of the tree so we may deal with many blocks
2825                  * before we come back to this one.
2826                  */
2827                 error = xfs_da_read_buf(*trans, dp, child_fsb, -2, &child_bp,
2828                                                 XFS_ATTR_FORK);
2829                 if (error)
2830                         return(error);
2831                 if (child_bp) {
2832                                                 /* save for re-read later */
2833                         child_blkno = xfs_da_blkno(child_bp);
2834
2835                         /*
2836                          * Invalidate the subtree, however we have to.
2837                          */
2838                         info = child_bp->data;
2839                         if (be16_to_cpu(info->magic) == XFS_DA_NODE_MAGIC) {
2840                                 error = xfs_attr_node_inactive(trans, dp,
2841                                                 child_bp, level+1);
2842                         } else if (be16_to_cpu(info->magic) == XFS_ATTR_LEAF_MAGIC) {
2843                                 error = xfs_attr_leaf_inactive(trans, dp,
2844                                                 child_bp);
2845                         } else {
2846                                 error = XFS_ERROR(EIO);
2847                                 xfs_da_brelse(*trans, child_bp);
2848                         }
2849                         if (error)
2850                                 return(error);
2851
2852                         /*
2853                          * Remove the subsidiary block from the cache
2854                          * and from the log.
2855                          */
2856                         error = xfs_da_get_buf(*trans, dp, 0, child_blkno,
2857                                 &child_bp, XFS_ATTR_FORK);
2858                         if (error)
2859                                 return(error);
2860                         xfs_da_binval(*trans, child_bp);
2861                 }
2862
2863                 /*
2864                  * If we're not done, re-read the parent to get the next
2865                  * child block number.
2866                  */
2867                 if ((i+1) < count) {
2868                         error = xfs_da_read_buf(*trans, dp, 0, parent_blkno,
2869                                 &bp, XFS_ATTR_FORK);
2870                         if (error)
2871                                 return(error);
2872                         child_fsb = be32_to_cpu(node->btree[i+1].before);
2873                         xfs_da_brelse(*trans, bp);
2874                 }
2875                 /*
2876                  * Atomically commit the whole invalidate stuff.
2877                  */
2878                 if ((error = xfs_attr_rolltrans(trans, dp)))
2879                         return (error);
2880         }
2881
2882         return(0);
2883 }
2884
2885 /*
2886  * Invalidate all of the "remote" value regions pointed to by a particular
2887  * leaf block.
2888  * Note that we must release the lock on the buffer so that we are not
2889  * caught holding something that the logging code wants to flush to disk.
2890  */
2891 STATIC int
2892 xfs_attr_leaf_inactive(xfs_trans_t **trans, xfs_inode_t *dp, xfs_dabuf_t *bp)
2893 {
2894         xfs_attr_leafblock_t *leaf;
2895         xfs_attr_leaf_entry_t *entry;
2896         xfs_attr_leaf_name_remote_t *name_rmt;
2897         xfs_attr_inactive_list_t *list, *lp;
2898         int error, count, size, tmp, i;
2899
2900         leaf = bp->data;
2901         ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_ATTR_LEAF_MAGIC);
2902
2903         /*
2904          * Count the number of "remote" value extents.
2905          */
2906         count = 0;
2907         entry = &leaf->entries[0];
2908         for (i = 0; i < be16_to_cpu(leaf->hdr.count); entry++, i++) {
2909                 if (be16_to_cpu(entry->nameidx) &&
2910                     ((entry->flags & XFS_ATTR_LOCAL) == 0)) {
2911                         name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, i);
2912                         if (name_rmt->valueblk)
2913                                 count++;
2914                 }
2915         }
2916
2917         /*
2918          * If there are no "remote" values, we're done.
2919          */
2920         if (count == 0) {
2921                 xfs_da_brelse(*trans, bp);
2922                 return(0);
2923         }
2924
2925         /*
2926          * Allocate storage for a list of all the "remote" value extents.
2927          */
2928         size = count * sizeof(xfs_attr_inactive_list_t);
2929         list = (xfs_attr_inactive_list_t *)kmem_alloc(size, KM_SLEEP);
2930
2931         /*
2932          * Identify each of the "remote" value extents.
2933          */
2934         lp = list;
2935         entry = &leaf->entries[0];
2936         for (i = 0; i < be16_to_cpu(leaf->hdr.count); entry++, i++) {
2937                 if (be16_to_cpu(entry->nameidx) &&
2938                     ((entry->flags & XFS_ATTR_LOCAL) == 0)) {
2939                         name_rmt = XFS_ATTR_LEAF_NAME_REMOTE(leaf, i);
2940                         if (name_rmt->valueblk) {
2941                                 lp->valueblk = be32_to_cpu(name_rmt->valueblk);
2942                                 lp->valuelen = XFS_B_TO_FSB(dp->i_mount,
2943                                                     be32_to_cpu(name_rmt->valuelen));
2944                                 lp++;
2945                         }
2946                 }
2947         }
2948         xfs_da_brelse(*trans, bp);      /* unlock for trans. in freextent() */
2949
2950         /*
2951          * Invalidate each of the "remote" value extents.
2952          */
2953         error = 0;
2954         for (lp = list, i = 0; i < count; i++, lp++) {
2955                 tmp = xfs_attr_leaf_freextent(trans, dp,
2956                                 lp->valueblk, lp->valuelen);
2957
2958                 if (error == 0)
2959                         error = tmp;    /* save only the 1st errno */
2960         }
2961
2962         kmem_free((xfs_caddr_t)list, size);
2963         return(error);
2964 }
2965
2966 /*
2967  * Look at all the extents for this logical region,
2968  * invalidate any buffers that are incore/in transactions.
2969  */
2970 STATIC int
2971 xfs_attr_leaf_freextent(xfs_trans_t **trans, xfs_inode_t *dp,
2972                                     xfs_dablk_t blkno, int blkcnt)
2973 {
2974         xfs_bmbt_irec_t map;
2975         xfs_dablk_t tblkno;
2976         int tblkcnt, dblkcnt, nmap, error;
2977         xfs_daddr_t dblkno;
2978         xfs_buf_t *bp;
2979
2980         /*
2981          * Roll through the "value", invalidating the attribute value's
2982          * blocks.
2983          */
2984         tblkno = blkno;
2985         tblkcnt = blkcnt;
2986         while (tblkcnt > 0) {
2987                 /*
2988                  * Try to remember where we decided to put the value.
2989                  */
2990                 nmap = 1;
2991                 error = xfs_bmapi(*trans, dp, (xfs_fileoff_t)tblkno, tblkcnt,
2992                                         XFS_BMAPI_ATTRFORK | XFS_BMAPI_METADATA,
2993                                         NULL, 0, &map, &nmap, NULL);
2994                 if (error) {
2995                         return(error);
2996                 }
2997                 ASSERT(nmap == 1);
2998                 ASSERT(map.br_startblock != DELAYSTARTBLOCK);
2999
3000                 /*
3001                  * If it's a hole, these are already unmapped
3002                  * so there's nothing to invalidate.
3003                  */
3004                 if (map.br_startblock != HOLESTARTBLOCK) {
3005
3006                         dblkno = XFS_FSB_TO_DADDR(dp->i_mount,
3007                                                   map.br_startblock);
3008                         dblkcnt = XFS_FSB_TO_BB(dp->i_mount,
3009                                                 map.br_blockcount);
3010                         bp = xfs_trans_get_buf(*trans,
3011                                         dp->i_mount->m_ddev_targp,
3012                                         dblkno, dblkcnt, XFS_BUF_LOCK);
3013                         xfs_trans_binval(*trans, bp);
3014                         /*
3015                          * Roll to next transaction.
3016                          */
3017                         if ((error = xfs_attr_rolltrans(trans, dp)))
3018                                 return (error);
3019                 }
3020
3021                 tblkno += map.br_blockcount;
3022                 tblkcnt -= map.br_blockcount;
3023         }
3024
3025         return(0);
3026 }
3027
3028
3029 /*
3030  * Roll from one trans in the sequence of PERMANENT transactions to the next.
3031  */
3032 int
3033 xfs_attr_rolltrans(xfs_trans_t **transp, xfs_inode_t *dp)
3034 {
3035         xfs_trans_t *trans;
3036         unsigned int logres, count;
3037         int     error;
3038
3039         /*
3040          * Ensure that the inode is always logged.
3041          */
3042         trans = *transp;
3043         xfs_trans_log_inode(trans, dp, XFS_ILOG_CORE);
3044
3045         /*
3046          * Copy the critical parameters from one trans to the next.
3047          */
3048         logres = trans->t_log_res;
3049         count = trans->t_log_count;
3050         *transp = xfs_trans_dup(trans);
3051
3052         /*
3053          * Commit the current transaction.
3054          * If this commit failed, then it'd just unlock those items that
3055          * are not marked ihold. That also means that a filesystem shutdown
3056          * is in progress. The caller takes the responsibility to cancel
3057          * the duplicate transaction that gets returned.
3058          */
3059         if ((error = xfs_trans_commit(trans, 0, NULL)))
3060                 return (error);
3061
3062         trans = *transp;
3063
3064         /*
3065          * Reserve space in the log for th next transaction.
3066          * This also pushes items in the "AIL", the list of logged items,
3067          * out to disk if they are taking up space at the tail of the log
3068          * that we want to use.  This requires that either nothing be locked
3069          * across this call, or that anything that is locked be logged in
3070          * the prior and the next transactions.
3071          */
3072         error = xfs_trans_reserve(trans, 0, logres, 0,
3073                                   XFS_TRANS_PERM_LOG_RES, count);
3074         /*
3075          *  Ensure that the inode is in the new transaction and locked.
3076          */
3077         if (!error) {
3078                 xfs_trans_ijoin(trans, dp, XFS_ILOCK_EXCL);
3079                 xfs_trans_ihold(trans, dp);
3080         }
3081         return (error);
3082
3083 }