[XFS] endianess annotations for xfs_dir2_block_tail_t
[linux-2.6.git] / fs / xfs / xfs_dir2_data.c
1 /*
2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
3  * All Rights Reserved.
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License as
7  * published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it would be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write the Free Software Foundation,
16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17  */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_log.h"
22 #include "xfs_inum.h"
23 #include "xfs_trans.h"
24 #include "xfs_sb.h"
25 #include "xfs_dir.h"
26 #include "xfs_dir2.h"
27 #include "xfs_dmapi.h"
28 #include "xfs_mount.h"
29 #include "xfs_da_btree.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_dir_sf.h"
32 #include "xfs_dir2_sf.h"
33 #include "xfs_attr_sf.h"
34 #include "xfs_dinode.h"
35 #include "xfs_inode.h"
36 #include "xfs_dir_leaf.h"
37 #include "xfs_dir2_data.h"
38 #include "xfs_dir2_leaf.h"
39 #include "xfs_dir2_block.h"
40 #include "xfs_error.h"
41
42 #ifdef DEBUG
43 /*
44  * Check the consistency of the data block.
45  * The input can also be a block-format directory.
46  * Pop an assert if we find anything bad.
47  */
48 void
49 xfs_dir2_data_check(
50         xfs_inode_t             *dp,            /* incore inode pointer */
51         xfs_dabuf_t             *bp)            /* data block's buffer */
52 {
53         xfs_dir2_dataptr_t      addr;           /* addr for leaf lookup */
54         xfs_dir2_data_free_t    *bf;            /* bestfree table */
55         xfs_dir2_block_tail_t   *btp=NULL;      /* block tail */
56         int                     count;          /* count of entries found */
57         xfs_dir2_data_t         *d;             /* data block pointer */
58         xfs_dir2_data_entry_t   *dep;           /* data entry */
59         xfs_dir2_data_free_t    *dfp;           /* bestfree entry */
60         xfs_dir2_data_unused_t  *dup;           /* unused entry */
61         char                    *endp;          /* end of useful data */
62         int                     freeseen;       /* mask of bestfrees seen */
63         xfs_dahash_t            hash;           /* hash of current name */
64         int                     i;              /* leaf index */
65         int                     lastfree;       /* last entry was unused */
66         xfs_dir2_leaf_entry_t   *lep=NULL;      /* block leaf entries */
67         xfs_mount_t             *mp;            /* filesystem mount point */
68         char                    *p;             /* current data position */
69         int                     stale;          /* count of stale leaves */
70
71         mp = dp->i_mount;
72         d = bp->data;
73         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
74                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
75         bf = d->hdr.bestfree;
76         p = (char *)d->u;
77         if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
78                 btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d);
79                 lep = XFS_DIR2_BLOCK_LEAF_P(btp);
80                 endp = (char *)lep;
81         } else
82                 endp = (char *)d + mp->m_dirblksize;
83         count = lastfree = freeseen = 0;
84         /*
85          * Account for zero bestfree entries.
86          */
87         if (!bf[0].length) {
88                 ASSERT(!bf[0].offset);
89                 freeseen |= 1 << 0;
90         }
91         if (!bf[1].length) {
92                 ASSERT(!bf[1].offset);
93                 freeseen |= 1 << 1;
94         }
95         if (!bf[2].length) {
96                 ASSERT(!bf[2].offset);
97                 freeseen |= 1 << 2;
98         }
99         ASSERT(be16_to_cpu(bf[0].length) >= be16_to_cpu(bf[1].length));
100         ASSERT(be16_to_cpu(bf[1].length) >= be16_to_cpu(bf[2].length));
101         /*
102          * Loop over the data/unused entries.
103          */
104         while (p < endp) {
105                 dup = (xfs_dir2_data_unused_t *)p;
106                 /*
107                  * If it's unused, look for the space in the bestfree table.
108                  * If we find it, account for that, else make sure it
109                  * doesn't need to be there.
110                  */
111                 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
112                         ASSERT(lastfree == 0);
113                         ASSERT(be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)) ==
114                                (char *)dup - (char *)d);
115                         dfp = xfs_dir2_data_freefind(d, dup);
116                         if (dfp) {
117                                 i = (int)(dfp - bf);
118                                 ASSERT((freeseen & (1 << i)) == 0);
119                                 freeseen |= 1 << i;
120                         } else {
121                                 ASSERT(be16_to_cpu(dup->length) <=
122                                        be16_to_cpu(bf[2].length));
123                         }
124                         p += be16_to_cpu(dup->length);
125                         lastfree = 1;
126                         continue;
127                 }
128                 /*
129                  * It's a real entry.  Validate the fields.
130                  * If this is a block directory then make sure it's
131                  * in the leaf section of the block.
132                  * The linear search is crude but this is DEBUG code.
133                  */
134                 dep = (xfs_dir2_data_entry_t *)p;
135                 ASSERT(dep->namelen != 0);
136                 ASSERT(xfs_dir_ino_validate(mp, INT_GET(dep->inumber, ARCH_CONVERT)) == 0);
137                 ASSERT(INT_GET(*XFS_DIR2_DATA_ENTRY_TAG_P(dep), ARCH_CONVERT) ==
138                        (char *)dep - (char *)d);
139                 count++;
140                 lastfree = 0;
141                 if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
142                         addr = XFS_DIR2_DB_OFF_TO_DATAPTR(mp, mp->m_dirdatablk,
143                                 (xfs_dir2_data_aoff_t)
144                                 ((char *)dep - (char *)d));
145                         hash = xfs_da_hashname((char *)dep->name, dep->namelen);
146                         for (i = 0; i < be32_to_cpu(btp->count); i++) {
147                                 if (INT_GET(lep[i].address, ARCH_CONVERT) == addr &&
148                                     INT_GET(lep[i].hashval, ARCH_CONVERT) == hash)
149                                         break;
150                         }
151                         ASSERT(i < be32_to_cpu(btp->count));
152                 }
153                 p += XFS_DIR2_DATA_ENTSIZE(dep->namelen);
154         }
155         /*
156          * Need to have seen all the entries and all the bestfree slots.
157          */
158         ASSERT(freeseen == 7);
159         if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
160                 for (i = stale = 0; i < be32_to_cpu(btp->count); i++) {
161                         if (INT_GET(lep[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
162                                 stale++;
163                         if (i > 0)
164                                 ASSERT(INT_GET(lep[i].hashval, ARCH_CONVERT) >= INT_GET(lep[i - 1].hashval, ARCH_CONVERT));
165                 }
166                 ASSERT(count == be32_to_cpu(btp->count) - be32_to_cpu(btp->stale));
167                 ASSERT(stale == be32_to_cpu(btp->stale));
168         }
169 }
170 #endif
171
172 /*
173  * Given a data block and an unused entry from that block,
174  * return the bestfree entry if any that corresponds to it.
175  */
176 xfs_dir2_data_free_t *
177 xfs_dir2_data_freefind(
178         xfs_dir2_data_t         *d,             /* data block */
179         xfs_dir2_data_unused_t  *dup)           /* data unused entry */
180 {
181         xfs_dir2_data_free_t    *dfp;           /* bestfree entry */
182         xfs_dir2_data_aoff_t    off;            /* offset value needed */
183 #if defined(DEBUG) && defined(__KERNEL__)
184         int                     matched;        /* matched the value */
185         int                     seenzero;       /* saw a 0 bestfree entry */
186 #endif
187
188         off = (xfs_dir2_data_aoff_t)((char *)dup - (char *)d);
189 #if defined(DEBUG) && defined(__KERNEL__)
190         /*
191          * Validate some consistency in the bestfree table.
192          * Check order, non-overlapping entries, and if we find the
193          * one we're looking for it has to be exact.
194          */
195         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
196                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
197         for (dfp = &d->hdr.bestfree[0], seenzero = matched = 0;
198              dfp < &d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT];
199              dfp++) {
200                 if (!dfp->offset) {
201                         ASSERT(!dfp->length);
202                         seenzero = 1;
203                         continue;
204                 }
205                 ASSERT(seenzero == 0);
206                 if (be16_to_cpu(dfp->offset) == off) {
207                         matched = 1;
208                         ASSERT(dfp->length == dup->length);
209                 } else if (off < be16_to_cpu(dfp->offset))
210                         ASSERT(off + be16_to_cpu(dup->length) <= be16_to_cpu(dfp->offset));
211                 else
212                         ASSERT(be16_to_cpu(dfp->offset) + be16_to_cpu(dfp->length) <= off);
213                 ASSERT(matched || be16_to_cpu(dfp->length) >= be16_to_cpu(dup->length));
214                 if (dfp > &d->hdr.bestfree[0])
215                         ASSERT(be16_to_cpu(dfp[-1].length) >= be16_to_cpu(dfp[0].length));
216         }
217 #endif
218         /*
219          * If this is smaller than the smallest bestfree entry,
220          * it can't be there since they're sorted.
221          */
222         if (be16_to_cpu(dup->length) <
223             be16_to_cpu(d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT - 1].length))
224                 return NULL;
225         /*
226          * Look at the three bestfree entries for our guy.
227          */
228         for (dfp = &d->hdr.bestfree[0];
229              dfp < &d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT];
230              dfp++) {
231                 if (!dfp->offset)
232                         return NULL;
233                 if (be16_to_cpu(dfp->offset) == off)
234                         return dfp;
235         }
236         /*
237          * Didn't find it.  This only happens if there are duplicate lengths.
238          */
239         return NULL;
240 }
241
242 /*
243  * Insert an unused-space entry into the bestfree table.
244  */
245 xfs_dir2_data_free_t *                          /* entry inserted */
246 xfs_dir2_data_freeinsert(
247         xfs_dir2_data_t         *d,             /* data block pointer */
248         xfs_dir2_data_unused_t  *dup,           /* unused space */
249         int                     *loghead)       /* log the data header (out) */
250 {
251         xfs_dir2_data_free_t    *dfp;           /* bestfree table pointer */
252         xfs_dir2_data_free_t    new;            /* new bestfree entry */
253
254 #ifdef __KERNEL__
255         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
256                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
257 #endif
258         dfp = d->hdr.bestfree;
259         new.length = dup->length;
260         new.offset = cpu_to_be16((char *)dup - (char *)d);
261         /*
262          * Insert at position 0, 1, or 2; or not at all.
263          */
264         if (be16_to_cpu(new.length) > be16_to_cpu(dfp[0].length)) {
265                 dfp[2] = dfp[1];
266                 dfp[1] = dfp[0];
267                 dfp[0] = new;
268                 *loghead = 1;
269                 return &dfp[0];
270         }
271         if (be16_to_cpu(new.length) > be16_to_cpu(dfp[1].length)) {
272                 dfp[2] = dfp[1];
273                 dfp[1] = new;
274                 *loghead = 1;
275                 return &dfp[1];
276         }
277         if (be16_to_cpu(new.length) > be16_to_cpu(dfp[2].length)) {
278                 dfp[2] = new;
279                 *loghead = 1;
280                 return &dfp[2];
281         }
282         return NULL;
283 }
284
285 /*
286  * Remove a bestfree entry from the table.
287  */
288 STATIC void
289 xfs_dir2_data_freeremove(
290         xfs_dir2_data_t         *d,             /* data block pointer */
291         xfs_dir2_data_free_t    *dfp,           /* bestfree entry pointer */
292         int                     *loghead)       /* out: log data header */
293 {
294 #ifdef __KERNEL__
295         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
296                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
297 #endif
298         /*
299          * It's the first entry, slide the next 2 up.
300          */
301         if (dfp == &d->hdr.bestfree[0]) {
302                 d->hdr.bestfree[0] = d->hdr.bestfree[1];
303                 d->hdr.bestfree[1] = d->hdr.bestfree[2];
304         }
305         /*
306          * It's the second entry, slide the 3rd entry up.
307          */
308         else if (dfp == &d->hdr.bestfree[1])
309                 d->hdr.bestfree[1] = d->hdr.bestfree[2];
310         /*
311          * Must be the last entry.
312          */
313         else
314                 ASSERT(dfp == &d->hdr.bestfree[2]);
315         /*
316          * Clear the 3rd entry, must be zero now.
317          */
318         d->hdr.bestfree[2].length = 0;
319         d->hdr.bestfree[2].offset = 0;
320         *loghead = 1;
321 }
322
323 /*
324  * Given a data block, reconstruct its bestfree map.
325  */
326 void
327 xfs_dir2_data_freescan(
328         xfs_mount_t             *mp,            /* filesystem mount point */
329         xfs_dir2_data_t         *d,             /* data block pointer */
330         int                     *loghead,       /* out: log data header */
331         char                    *aendp)         /* in: caller's endp */
332 {
333         xfs_dir2_block_tail_t   *btp;           /* block tail */
334         xfs_dir2_data_entry_t   *dep;           /* active data entry */
335         xfs_dir2_data_unused_t  *dup;           /* unused data entry */
336         char                    *endp;          /* end of block's data */
337         char                    *p;             /* current entry pointer */
338
339 #ifdef __KERNEL__
340         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
341                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
342 #endif
343         /*
344          * Start by clearing the table.
345          */
346         memset(d->hdr.bestfree, 0, sizeof(d->hdr.bestfree));
347         *loghead = 1;
348         /*
349          * Set up pointers.
350          */
351         p = (char *)d->u;
352         if (aendp)
353                 endp = aendp;
354         else if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) {
355                 btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d);
356                 endp = (char *)XFS_DIR2_BLOCK_LEAF_P(btp);
357         } else
358                 endp = (char *)d + mp->m_dirblksize;
359         /*
360          * Loop over the block's entries.
361          */
362         while (p < endp) {
363                 dup = (xfs_dir2_data_unused_t *)p;
364                 /*
365                  * If it's a free entry, insert it.
366                  */
367                 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
368                         ASSERT((char *)dup - (char *)d ==
369                                be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)));
370                         xfs_dir2_data_freeinsert(d, dup, loghead);
371                         p += be16_to_cpu(dup->length);
372                 }
373                 /*
374                  * For active entries, check their tags and skip them.
375                  */
376                 else {
377                         dep = (xfs_dir2_data_entry_t *)p;
378                         ASSERT((char *)dep - (char *)d ==
379                                INT_GET(*XFS_DIR2_DATA_ENTRY_TAG_P(dep), ARCH_CONVERT));
380                         p += XFS_DIR2_DATA_ENTSIZE(dep->namelen);
381                 }
382         }
383 }
384
385 /*
386  * Initialize a data block at the given block number in the directory.
387  * Give back the buffer for the created block.
388  */
389 int                                             /* error */
390 xfs_dir2_data_init(
391         xfs_da_args_t           *args,          /* directory operation args */
392         xfs_dir2_db_t           blkno,          /* logical dir block number */
393         xfs_dabuf_t             **bpp)          /* output block buffer */
394 {
395         xfs_dabuf_t             *bp;            /* block buffer */
396         xfs_dir2_data_t         *d;             /* pointer to block */
397         xfs_inode_t             *dp;            /* incore directory inode */
398         xfs_dir2_data_unused_t  *dup;           /* unused entry pointer */
399         int                     error;          /* error return value */
400         int                     i;              /* bestfree index */
401         xfs_mount_t             *mp;            /* filesystem mount point */
402         xfs_trans_t             *tp;            /* transaction pointer */
403         int                     t;              /* temp */
404
405         dp = args->dp;
406         mp = dp->i_mount;
407         tp = args->trans;
408         /*
409          * Get the buffer set up for the block.
410          */
411         error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, blkno), -1, &bp,
412                 XFS_DATA_FORK);
413         if (error) {
414                 return error;
415         }
416         ASSERT(bp != NULL);
417         /*
418          * Initialize the header.
419          */
420         d = bp->data;
421         d->hdr.magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
422         d->hdr.bestfree[0].offset = cpu_to_be16(sizeof(d->hdr));
423         for (i = 1; i < XFS_DIR2_DATA_FD_COUNT; i++) {
424                 d->hdr.bestfree[i].length = 0;
425                 d->hdr.bestfree[i].offset = 0;
426         }
427         /*
428          * Set up an unused entry for the block's body.
429          */
430         dup = &d->u[0].unused;
431         dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
432
433         t=mp->m_dirblksize - (uint)sizeof(d->hdr);
434         d->hdr.bestfree[0].length = cpu_to_be16(t);
435         dup->length = cpu_to_be16(t);
436         *XFS_DIR2_DATA_UNUSED_TAG_P(dup) = cpu_to_be16((char *)dup - (char *)d);
437         /*
438          * Log it and return it.
439          */
440         xfs_dir2_data_log_header(tp, bp);
441         xfs_dir2_data_log_unused(tp, bp, dup);
442         *bpp = bp;
443         return 0;
444 }
445
446 /*
447  * Log an active data entry from the block.
448  */
449 void
450 xfs_dir2_data_log_entry(
451         xfs_trans_t             *tp,            /* transaction pointer */
452         xfs_dabuf_t             *bp,            /* block buffer */
453         xfs_dir2_data_entry_t   *dep)           /* data entry pointer */
454 {
455         xfs_dir2_data_t         *d;             /* data block pointer */
456
457         d = bp->data;
458         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
459                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
460         xfs_da_log_buf(tp, bp, (uint)((char *)dep - (char *)d),
461                 (uint)((char *)(XFS_DIR2_DATA_ENTRY_TAG_P(dep) + 1) -
462                        (char *)d - 1));
463 }
464
465 /*
466  * Log a data block header.
467  */
468 void
469 xfs_dir2_data_log_header(
470         xfs_trans_t             *tp,            /* transaction pointer */
471         xfs_dabuf_t             *bp)            /* block buffer */
472 {
473         xfs_dir2_data_t         *d;             /* data block pointer */
474
475         d = bp->data;
476         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
477                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
478         xfs_da_log_buf(tp, bp, (uint)((char *)&d->hdr - (char *)d),
479                 (uint)(sizeof(d->hdr) - 1));
480 }
481
482 /*
483  * Log a data unused entry.
484  */
485 void
486 xfs_dir2_data_log_unused(
487         xfs_trans_t             *tp,            /* transaction pointer */
488         xfs_dabuf_t             *bp,            /* block buffer */
489         xfs_dir2_data_unused_t  *dup)           /* data unused pointer */
490 {
491         xfs_dir2_data_t         *d;             /* data block pointer */
492
493         d = bp->data;
494         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
495                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
496         /*
497          * Log the first part of the unused entry.
498          */
499         xfs_da_log_buf(tp, bp, (uint)((char *)dup - (char *)d),
500                 (uint)((char *)&dup->length + sizeof(dup->length) -
501                        1 - (char *)d));
502         /*
503          * Log the end (tag) of the unused entry.
504          */
505         xfs_da_log_buf(tp, bp,
506                 (uint)((char *)XFS_DIR2_DATA_UNUSED_TAG_P(dup) - (char *)d),
507                 (uint)((char *)XFS_DIR2_DATA_UNUSED_TAG_P(dup) - (char *)d +
508                        sizeof(xfs_dir2_data_off_t) - 1));
509 }
510
511 /*
512  * Make a byte range in the data block unused.
513  * Its current contents are unimportant.
514  */
515 void
516 xfs_dir2_data_make_free(
517         xfs_trans_t             *tp,            /* transaction pointer */
518         xfs_dabuf_t             *bp,            /* block buffer */
519         xfs_dir2_data_aoff_t    offset,         /* starting byte offset */
520         xfs_dir2_data_aoff_t    len,            /* length in bytes */
521         int                     *needlogp,      /* out: log header */
522         int                     *needscanp)     /* out: regen bestfree */
523 {
524         xfs_dir2_data_t         *d;             /* data block pointer */
525         xfs_dir2_data_free_t    *dfp;           /* bestfree pointer */
526         char                    *endptr;        /* end of data area */
527         xfs_mount_t             *mp;            /* filesystem mount point */
528         int                     needscan;       /* need to regen bestfree */
529         xfs_dir2_data_unused_t  *newdup;        /* new unused entry */
530         xfs_dir2_data_unused_t  *postdup;       /* unused entry after us */
531         xfs_dir2_data_unused_t  *prevdup;       /* unused entry before us */
532
533         mp = tp->t_mountp;
534         d = bp->data;
535         /*
536          * Figure out where the end of the data area is.
537          */
538         if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC)
539                 endptr = (char *)d + mp->m_dirblksize;
540         else {
541                 xfs_dir2_block_tail_t   *btp;   /* block tail */
542
543                 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
544                 btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d);
545                 endptr = (char *)XFS_DIR2_BLOCK_LEAF_P(btp);
546         }
547         /*
548          * If this isn't the start of the block, then back up to
549          * the previous entry and see if it's free.
550          */
551         if (offset > sizeof(d->hdr)) {
552                 xfs_dir2_data_off_t     *tagp;  /* tag just before us */
553
554                 tagp = (xfs_dir2_data_off_t *)((char *)d + offset) - 1;
555                 prevdup = (xfs_dir2_data_unused_t *)((char *)d + INT_GET(*tagp, ARCH_CONVERT));
556                 if (be16_to_cpu(prevdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
557                         prevdup = NULL;
558         } else
559                 prevdup = NULL;
560         /*
561          * If this isn't the end of the block, see if the entry after
562          * us is free.
563          */
564         if ((char *)d + offset + len < endptr) {
565                 postdup =
566                         (xfs_dir2_data_unused_t *)((char *)d + offset + len);
567                 if (be16_to_cpu(postdup->freetag) != XFS_DIR2_DATA_FREE_TAG)
568                         postdup = NULL;
569         } else
570                 postdup = NULL;
571         ASSERT(*needscanp == 0);
572         needscan = 0;
573         /*
574          * Previous and following entries are both free,
575          * merge everything into a single free entry.
576          */
577         if (prevdup && postdup) {
578                 xfs_dir2_data_free_t    *dfp2;  /* another bestfree pointer */
579
580                 /*
581                  * See if prevdup and/or postdup are in bestfree table.
582                  */
583                 dfp = xfs_dir2_data_freefind(d, prevdup);
584                 dfp2 = xfs_dir2_data_freefind(d, postdup);
585                 /*
586                  * We need a rescan unless there are exactly 2 free entries
587                  * namely our two.  Then we know what's happening, otherwise
588                  * since the third bestfree is there, there might be more
589                  * entries.
590                  */
591                 needscan = (d->hdr.bestfree[2].length != 0);
592                 /*
593                  * Fix up the new big freespace.
594                  */
595                 be16_add(&prevdup->length, len + be16_to_cpu(postdup->length));
596                 *XFS_DIR2_DATA_UNUSED_TAG_P(prevdup) =
597                         cpu_to_be16((char *)prevdup - (char *)d);
598                 xfs_dir2_data_log_unused(tp, bp, prevdup);
599                 if (!needscan) {
600                         /*
601                          * Has to be the case that entries 0 and 1 are
602                          * dfp and dfp2 (don't know which is which), and
603                          * entry 2 is empty.
604                          * Remove entry 1 first then entry 0.
605                          */
606                         ASSERT(dfp && dfp2);
607                         if (dfp == &d->hdr.bestfree[1]) {
608                                 dfp = &d->hdr.bestfree[0];
609                                 ASSERT(dfp2 == dfp);
610                                 dfp2 = &d->hdr.bestfree[1];
611                         }
612                         xfs_dir2_data_freeremove(d, dfp2, needlogp);
613                         xfs_dir2_data_freeremove(d, dfp, needlogp);
614                         /*
615                          * Now insert the new entry.
616                          */
617                         dfp = xfs_dir2_data_freeinsert(d, prevdup, needlogp);
618                         ASSERT(dfp == &d->hdr.bestfree[0]);
619                         ASSERT(dfp->length == prevdup->length);
620                         ASSERT(!dfp[1].length);
621                         ASSERT(!dfp[2].length);
622                 }
623         }
624         /*
625          * The entry before us is free, merge with it.
626          */
627         else if (prevdup) {
628                 dfp = xfs_dir2_data_freefind(d, prevdup);
629                 be16_add(&prevdup->length, len);
630                 *XFS_DIR2_DATA_UNUSED_TAG_P(prevdup) =
631                         cpu_to_be16((char *)prevdup - (char *)d);
632                 xfs_dir2_data_log_unused(tp, bp, prevdup);
633                 /*
634                  * If the previous entry was in the table, the new entry
635                  * is longer, so it will be in the table too.  Remove
636                  * the old one and add the new one.
637                  */
638                 if (dfp) {
639                         xfs_dir2_data_freeremove(d, dfp, needlogp);
640                         (void)xfs_dir2_data_freeinsert(d, prevdup, needlogp);
641                 }
642                 /*
643                  * Otherwise we need a scan if the new entry is big enough.
644                  */
645                 else {
646                         needscan = be16_to_cpu(prevdup->length) >
647                                    be16_to_cpu(d->hdr.bestfree[2].length);
648                 }
649         }
650         /*
651          * The following entry is free, merge with it.
652          */
653         else if (postdup) {
654                 dfp = xfs_dir2_data_freefind(d, postdup);
655                 newdup = (xfs_dir2_data_unused_t *)((char *)d + offset);
656                 newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
657                 newdup->length = cpu_to_be16(len + be16_to_cpu(postdup->length));
658                 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
659                         cpu_to_be16((char *)newdup - (char *)d);
660                 xfs_dir2_data_log_unused(tp, bp, newdup);
661                 /*
662                  * If the following entry was in the table, the new entry
663                  * is longer, so it will be in the table too.  Remove
664                  * the old one and add the new one.
665                  */
666                 if (dfp) {
667                         xfs_dir2_data_freeremove(d, dfp, needlogp);
668                         (void)xfs_dir2_data_freeinsert(d, newdup, needlogp);
669                 }
670                 /*
671                  * Otherwise we need a scan if the new entry is big enough.
672                  */
673                 else {
674                         needscan = be16_to_cpu(newdup->length) >
675                                    be16_to_cpu(d->hdr.bestfree[2].length);
676                 }
677         }
678         /*
679          * Neither neighbor is free.  Make a new entry.
680          */
681         else {
682                 newdup = (xfs_dir2_data_unused_t *)((char *)d + offset);
683                 newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
684                 newdup->length = cpu_to_be16(len);
685                 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
686                         cpu_to_be16((char *)newdup - (char *)d);
687                 xfs_dir2_data_log_unused(tp, bp, newdup);
688                 (void)xfs_dir2_data_freeinsert(d, newdup, needlogp);
689         }
690         *needscanp = needscan;
691 }
692
693 /*
694  * Take a byte range out of an existing unused space and make it un-free.
695  */
696 void
697 xfs_dir2_data_use_free(
698         xfs_trans_t             *tp,            /* transaction pointer */
699         xfs_dabuf_t             *bp,            /* data block buffer */
700         xfs_dir2_data_unused_t  *dup,           /* unused entry */
701         xfs_dir2_data_aoff_t    offset,         /* starting offset to use */
702         xfs_dir2_data_aoff_t    len,            /* length to use */
703         int                     *needlogp,      /* out: need to log header */
704         int                     *needscanp)     /* out: need regen bestfree */
705 {
706         xfs_dir2_data_t         *d;             /* data block */
707         xfs_dir2_data_free_t    *dfp;           /* bestfree pointer */
708         int                     matchback;      /* matches end of freespace */
709         int                     matchfront;     /* matches start of freespace */
710         int                     needscan;       /* need to regen bestfree */
711         xfs_dir2_data_unused_t  *newdup;        /* new unused entry */
712         xfs_dir2_data_unused_t  *newdup2;       /* another new unused entry */
713         int                     oldlen;         /* old unused entry's length */
714
715         d = bp->data;
716         ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC ||
717                be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC);
718         ASSERT(be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG);
719         ASSERT(offset >= (char *)dup - (char *)d);
720         ASSERT(offset + len <= (char *)dup + be16_to_cpu(dup->length) - (char *)d);
721         ASSERT((char *)dup - (char *)d == be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)));
722         /*
723          * Look up the entry in the bestfree table.
724          */
725         dfp = xfs_dir2_data_freefind(d, dup);
726         oldlen = be16_to_cpu(dup->length);
727         ASSERT(dfp || oldlen <= be16_to_cpu(d->hdr.bestfree[2].length));
728         /*
729          * Check for alignment with front and back of the entry.
730          */
731         matchfront = (char *)dup - (char *)d == offset;
732         matchback = (char *)dup + oldlen - (char *)d == offset + len;
733         ASSERT(*needscanp == 0);
734         needscan = 0;
735         /*
736          * If we matched it exactly we just need to get rid of it from
737          * the bestfree table.
738          */
739         if (matchfront && matchback) {
740                 if (dfp) {
741                         needscan = (d->hdr.bestfree[2].offset != 0);
742                         if (!needscan)
743                                 xfs_dir2_data_freeremove(d, dfp, needlogp);
744                 }
745         }
746         /*
747          * We match the first part of the entry.
748          * Make a new entry with the remaining freespace.
749          */
750         else if (matchfront) {
751                 newdup = (xfs_dir2_data_unused_t *)((char *)d + offset + len);
752                 newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
753                 newdup->length = cpu_to_be16(oldlen - len);
754                 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
755                         cpu_to_be16((char *)newdup - (char *)d);
756                 xfs_dir2_data_log_unused(tp, bp, newdup);
757                 /*
758                  * If it was in the table, remove it and add the new one.
759                  */
760                 if (dfp) {
761                         xfs_dir2_data_freeremove(d, dfp, needlogp);
762                         dfp = xfs_dir2_data_freeinsert(d, newdup, needlogp);
763                         ASSERT(dfp != NULL);
764                         ASSERT(dfp->length == newdup->length);
765                         ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)d);
766                         /*
767                          * If we got inserted at the last slot,
768                          * that means we don't know if there was a better
769                          * choice for the last slot, or not.  Rescan.
770                          */
771                         needscan = dfp == &d->hdr.bestfree[2];
772                 }
773         }
774         /*
775          * We match the last part of the entry.
776          * Trim the allocated space off the tail of the entry.
777          */
778         else if (matchback) {
779                 newdup = dup;
780                 newdup->length = cpu_to_be16(((char *)d + offset) - (char *)newdup);
781                 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
782                         cpu_to_be16((char *)newdup - (char *)d);
783                 xfs_dir2_data_log_unused(tp, bp, newdup);
784                 /*
785                  * If it was in the table, remove it and add the new one.
786                  */
787                 if (dfp) {
788                         xfs_dir2_data_freeremove(d, dfp, needlogp);
789                         dfp = xfs_dir2_data_freeinsert(d, newdup, needlogp);
790                         ASSERT(dfp != NULL);
791                         ASSERT(dfp->length == newdup->length);
792                         ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)d);
793                         /*
794                          * If we got inserted at the last slot,
795                          * that means we don't know if there was a better
796                          * choice for the last slot, or not.  Rescan.
797                          */
798                         needscan = dfp == &d->hdr.bestfree[2];
799                 }
800         }
801         /*
802          * Poking out the middle of an entry.
803          * Make two new entries.
804          */
805         else {
806                 newdup = dup;
807                 newdup->length = cpu_to_be16(((char *)d + offset) - (char *)newdup);
808                 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) =
809                         cpu_to_be16((char *)newdup - (char *)d);
810                 xfs_dir2_data_log_unused(tp, bp, newdup);
811                 newdup2 = (xfs_dir2_data_unused_t *)((char *)d + offset + len);
812                 newdup2->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
813                 newdup2->length = cpu_to_be16(oldlen - len - be16_to_cpu(newdup->length));
814                 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup2) =
815                         cpu_to_be16((char *)newdup2 - (char *)d);
816                 xfs_dir2_data_log_unused(tp, bp, newdup2);
817                 /*
818                  * If the old entry was in the table, we need to scan
819                  * if the 3rd entry was valid, since these entries
820                  * are smaller than the old one.
821                  * If we don't need to scan that means there were 1 or 2
822                  * entries in the table, and removing the old and adding
823                  * the 2 new will work.
824                  */
825                 if (dfp) {
826                         needscan = (d->hdr.bestfree[2].length != 0);
827                         if (!needscan) {
828                                 xfs_dir2_data_freeremove(d, dfp, needlogp);
829                                 (void)xfs_dir2_data_freeinsert(d, newdup,
830                                         needlogp);
831                                 (void)xfs_dir2_data_freeinsert(d, newdup2,
832                                         needlogp);
833                         }
834                 }
835         }
836         *needscanp = needscan;
837 }