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