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