?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 2.6.14.1
[linux/fpc-iii.git] / fs / xfs / xfs_dir2_leaf.c
blob056f5283904b981184b968e75944112ee109d20c
1 /*
2 * Copyright (c) 2000-2003 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_leaf.c
35 * XFS directory version 2 implementation - single leaf form
36 * see xfs_dir2_leaf.h for data structures.
37 * These directories have multiple XFS_DIR2_DATA blocks and one
38 * XFS_DIR2_LEAF1 block containing the hash table and freespace map.
39 */
40
41 #include "xfs.h"
42
43 #include "xfs_macros.h"
44 #include "xfs_types.h"
45 #include "xfs_inum.h"
46 #include "xfs_log.h"
47 #include "xfs_trans.h"
48 #include "xfs_sb.h"
49 #include "xfs_ag.h"
50 #include "xfs_dir.h"
51 #include "xfs_dir2.h"
52 #include "xfs_dmapi.h"
53 #include "xfs_mount.h"
54 #include "xfs_bmap_btree.h"
55 #include "xfs_attr_sf.h"
56 #include "xfs_dir_sf.h"
57 #include "xfs_dir2_sf.h"
58 #include "xfs_dinode.h"
59 #include "xfs_inode.h"
60 #include "xfs_bmap.h"
61 #include "xfs_da_btree.h"
62 #include "xfs_dir2_data.h"
63 #include "xfs_dir2_leaf.h"
64 #include "xfs_dir2_block.h"
65 #include "xfs_dir2_node.h"
66 #include "xfs_dir2_trace.h"
67 #include "xfs_error.h"
68 #include "xfs_bit.h"
69
70 /*
71 * Local function declarations.
72 */
73 #ifdef DEBUG
74 static void xfs_dir2_leaf_check(xfs_inode_t *dp, xfs_dabuf_t *bp);
75 #else
76 #define xfs_dir2_leaf_check(dp, bp)
77 #endif
78 static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, xfs_dabuf_t **lbpp,
79 int *indexp, xfs_dabuf_t **dbpp);
80 static void xfs_dir2_leaf_log_bests(struct xfs_trans *tp, struct xfs_dabuf *bp,
81 int first, int last);
82 static void xfs_dir2_leaf_log_tail(struct xfs_trans *tp, struct xfs_dabuf *bp);
83
84
85 /*
86 * Convert a block form directory to a leaf form directory.
87 */
88 int /* error */
89 xfs_dir2_block_to_leaf(
90 xfs_da_args_t *args, /* operation arguments */
91 xfs_dabuf_t *dbp) /* input block's buffer */
92 {
93 xfs_dir2_data_off_t *bestsp; /* leaf's bestsp entries */
94 xfs_dablk_t blkno; /* leaf block's bno */
95 xfs_dir2_block_t *block; /* block structure */
96 xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
97 xfs_dir2_block_tail_t *btp; /* block's tail */
98 xfs_inode_t *dp; /* incore directory inode */
99 int error; /* error return code */
100 xfs_dabuf_t *lbp; /* leaf block's buffer */
101 xfs_dir2_db_t ldb; /* leaf block's bno */
102 xfs_dir2_leaf_t *leaf; /* leaf structure */
103 xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
104 xfs_mount_t *mp; /* filesystem mount point */
105 int needlog; /* need to log block header */
106 int needscan; /* need to rescan bestfree */
107 xfs_trans_t *tp; /* transaction pointer */
108
109 xfs_dir2_trace_args_b("block_to_leaf", args, dbp);
110 dp = args->dp;
111 mp = dp->i_mount;
112 tp = args->trans;
113 /*
114 * Add the leaf block to the inode.
115 * This interface will only put blocks in the leaf/node range.
116 * Since that's empty now, we'll get the root (block 0 in range).
117 */
118 if ((error = xfs_da_grow_inode(args, &blkno))) {
119 return error;
120 }
121 ldb = XFS_DIR2_DA_TO_DB(mp, blkno);
122 ASSERT(ldb == XFS_DIR2_LEAF_FIRSTDB(mp));
123 /*
124 * Initialize the leaf block, get a buffer for it.
125 */
126 if ((error = xfs_dir2_leaf_init(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC))) {
127 return error;
128 }
129 ASSERT(lbp != NULL);
130 leaf = lbp->data;
131 block = dbp->data;
132 xfs_dir2_data_check(dp, dbp);
133 btp = XFS_DIR2_BLOCK_TAIL_P(mp, block);
134 blp = XFS_DIR2_BLOCK_LEAF_P(btp);
135 /*
136 * Set the counts in the leaf header.
137 */
138 INT_COPY(leaf->hdr.count, btp->count, ARCH_CONVERT); /* INT_: type change */
139 INT_COPY(leaf->hdr.stale, btp->stale, ARCH_CONVERT); /* INT_: type change */
140 /*
141 * Could compact these but I think we always do the conversion
142 * after squeezing out stale entries.
143 */
144 memcpy(leaf->ents, blp, INT_GET(btp->count, ARCH_CONVERT) * sizeof(xfs_dir2_leaf_entry_t));
145 xfs_dir2_leaf_log_ents(tp, lbp, 0, INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1);
146 needscan = 0;
147 needlog = 1;
148 /*
149 * Make the space formerly occupied by the leaf entries and block
150 * tail be free.
151 */
152 xfs_dir2_data_make_free(tp, dbp,
153 (xfs_dir2_data_aoff_t)((char *)blp - (char *)block),
154 (xfs_dir2_data_aoff_t)((char *)block + mp->m_dirblksize -
155 (char *)blp),
156 &needlog, &needscan);
157 /*
158 * Fix up the block header, make it a data block.
159 */
160 INT_SET(block->hdr.magic, ARCH_CONVERT, XFS_DIR2_DATA_MAGIC);
161 if (needscan)
162 xfs_dir2_data_freescan(mp, (xfs_dir2_data_t *)block, &needlog,
163 NULL);
164 /*
165 * Set up leaf tail and bests table.
166 */
167 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
168 INT_SET(ltp->bestcount, ARCH_CONVERT, 1);
169 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
170 INT_COPY(bestsp[0], block->hdr.bestfree[0].length, ARCH_CONVERT);
171 /*
172 * Log the data header and leaf bests table.
173 */
174 if (needlog)
175 xfs_dir2_data_log_header(tp, dbp);
176 xfs_dir2_leaf_check(dp, lbp);
177 xfs_dir2_data_check(dp, dbp);
178 xfs_dir2_leaf_log_bests(tp, lbp, 0, 0);
179 xfs_da_buf_done(lbp);
180 return 0;
181 }
182
183 /*
184 * Add an entry to a leaf form directory.
185 */
186 int /* error */
187 xfs_dir2_leaf_addname(
188 xfs_da_args_t *args) /* operation arguments */
189 {
190 xfs_dir2_data_off_t *bestsp; /* freespace table in leaf */
191 int compact; /* need to compact leaves */
192 xfs_dir2_data_t *data; /* data block structure */
193 xfs_dabuf_t *dbp; /* data block buffer */
194 xfs_dir2_data_entry_t *dep; /* data block entry */
195 xfs_inode_t *dp; /* incore directory inode */
196 xfs_dir2_data_unused_t *dup; /* data unused entry */
197 int error; /* error return value */
198 int grown; /* allocated new data block */
199 int highstale; /* index of next stale leaf */
200 int i; /* temporary, index */
201 int index; /* leaf table position */
202 xfs_dabuf_t *lbp; /* leaf's buffer */
203 xfs_dir2_leaf_t *leaf; /* leaf structure */
204 int length; /* length of new entry */
205 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
206 int lfloglow; /* low leaf logging index */
207 int lfloghigh; /* high leaf logging index */
208 int lowstale; /* index of prev stale leaf */
209 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
210 xfs_mount_t *mp; /* filesystem mount point */
211 int needbytes; /* leaf block bytes needed */
212 int needlog; /* need to log data header */
213 int needscan; /* need to rescan data free */
214 xfs_dir2_data_off_t *tagp; /* end of data entry */
215 xfs_trans_t *tp; /* transaction pointer */
216 xfs_dir2_db_t use_block; /* data block number */
217
218 xfs_dir2_trace_args("leaf_addname", args);
219 dp = args->dp;
220 tp = args->trans;
221 mp = dp->i_mount;
222 /*
223 * Read the leaf block.
224 */
225 error = xfs_da_read_buf(tp, dp, mp->m_dirleafblk, -1, &lbp,
226 XFS_DATA_FORK);
227 if (error) {
228 return error;
229 }
230 ASSERT(lbp != NULL);
231 /*
232 * Look up the entry by hash value and name.
233 * We know it's not there, our caller has already done a lookup.
234 * So the index is of the entry to insert in front of.
235 * But if there are dup hash values the index is of the first of those.
236 */
237 index = xfs_dir2_leaf_search_hash(args, lbp);
238 leaf = lbp->data;
239 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
240 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
241 length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
242 /*
243 * See if there are any entries with the same hash value
244 * and space in their block for the new entry.
245 * This is good because it puts multiple same-hash value entries
246 * in a data block, improving the lookup of those entries.
247 */
248 for (use_block = -1, lep = &leaf->ents[index];
249 index < INT_GET(leaf->hdr.count, ARCH_CONVERT) && INT_GET(lep->hashval, ARCH_CONVERT) == args->hashval;
250 index++, lep++) {
251 if (INT_GET(lep->address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
252 continue;
253 i = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
254 ASSERT(i < INT_GET(ltp->bestcount, ARCH_CONVERT));
255 ASSERT(INT_GET(bestsp[i], ARCH_CONVERT) != NULLDATAOFF);
256 if (INT_GET(bestsp[i], ARCH_CONVERT) >= length) {
257 use_block = i;
258 break;
259 }
260 }
261 /*
262 * Didn't find a block yet, linear search all the data blocks.
263 */
264 if (use_block == -1) {
265 for (i = 0; i < INT_GET(ltp->bestcount, ARCH_CONVERT); i++) {
266 /*
267 * Remember a block we see that's missing.
268 */
269 if (INT_GET(bestsp[i], ARCH_CONVERT) == NULLDATAOFF && use_block == -1)
270 use_block = i;
271 else if (INT_GET(bestsp[i], ARCH_CONVERT) >= length) {
272 use_block = i;
273 break;
274 }
275 }
276 }
277 /*
278 * How many bytes do we need in the leaf block?
279 */
280 needbytes =
281 (leaf->hdr.stale ? 0 : (uint)sizeof(leaf->ents[0])) +
282 (use_block != -1 ? 0 : (uint)sizeof(leaf->bests[0]));
283 /*
284 * Now kill use_block if it refers to a missing block, so we
285 * can use it as an indication of allocation needed.
286 */
287 if (use_block != -1 && INT_GET(bestsp[use_block], ARCH_CONVERT) == NULLDATAOFF)
288 use_block = -1;
289 /*
290 * If we don't have enough free bytes but we can make enough
291 * by compacting out stale entries, we'll do that.
292 */
293 if ((char *)bestsp - (char *)&leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT)] < needbytes &&
294 INT_GET(leaf->hdr.stale, ARCH_CONVERT) > 1) {
295 compact = 1;
296 }
297 /*
298 * Otherwise if we don't have enough free bytes we need to
299 * convert to node form.
300 */
301 else if ((char *)bestsp - (char *)&leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT)] <
302 needbytes) {
303 /*
304 * Just checking or no space reservation, give up.
305 */
306 if (args->justcheck || args->total == 0) {
307 xfs_da_brelse(tp, lbp);
308 return XFS_ERROR(ENOSPC);
309 }
310 /*
311 * Convert to node form.
312 */
313 error = xfs_dir2_leaf_to_node(args, lbp);
314 xfs_da_buf_done(lbp);
315 if (error)
316 return error;
317 /*
318 * Then add the new entry.
319 */
320 return xfs_dir2_node_addname(args);
321 }
322 /*
323 * Otherwise it will fit without compaction.
324 */
325 else
326 compact = 0;
327 /*
328 * If just checking, then it will fit unless we needed to allocate
329 * a new data block.
330 */
331 if (args->justcheck) {
332 xfs_da_brelse(tp, lbp);
333 return use_block == -1 ? XFS_ERROR(ENOSPC) : 0;
334 }
335 /*
336 * If no allocations are allowed, return now before we've
337 * changed anything.
338 */
339 if (args->total == 0 && use_block == -1) {
340 xfs_da_brelse(tp, lbp);
341 return XFS_ERROR(ENOSPC);
342 }
343 /*
344 * Need to compact the leaf entries, removing stale ones.
345 * Leave one stale entry behind - the one closest to our
346 * insertion index - and we'll shift that one to our insertion
347 * point later.
348 */
349 if (compact) {
350 xfs_dir2_leaf_compact_x1(lbp, &index, &lowstale, &highstale,
351 &lfloglow, &lfloghigh);
352 }
353 /*
354 * There are stale entries, so we'll need log-low and log-high
355 * impossibly bad values later.
356 */
357 else if (INT_GET(leaf->hdr.stale, ARCH_CONVERT)) {
358 lfloglow = INT_GET(leaf->hdr.count, ARCH_CONVERT);
359 lfloghigh = -1;
360 }
361 /*
362 * If there was no data block space found, we need to allocate
363 * a new one.
364 */
365 if (use_block == -1) {
366 /*
367 * Add the new data block.
368 */
369 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
370 &use_block))) {
371 xfs_da_brelse(tp, lbp);
372 return error;
373 }
374 /*
375 * Initialize the block.
376 */
377 if ((error = xfs_dir2_data_init(args, use_block, &dbp))) {
378 xfs_da_brelse(tp, lbp);
379 return error;
380 }
381 /*
382 * If we're adding a new data block on the end we need to
383 * extend the bests table. Copy it up one entry.
384 */
385 if (use_block >= INT_GET(ltp->bestcount, ARCH_CONVERT)) {
386 bestsp--;
387 memmove(&bestsp[0], &bestsp[1],
388 INT_GET(ltp->bestcount, ARCH_CONVERT) * sizeof(bestsp[0]));
389 INT_MOD(ltp->bestcount, ARCH_CONVERT, +1);
390 xfs_dir2_leaf_log_tail(tp, lbp);
391 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
392 }
393 /*
394 * If we're filling in a previously empty block just log it.
395 */
396 else
397 xfs_dir2_leaf_log_bests(tp, lbp, use_block, use_block);
398 data = dbp->data;
399 INT_COPY(bestsp[use_block], data->hdr.bestfree[0].length, ARCH_CONVERT);
400 grown = 1;
401 }
402 /*
403 * Already had space in some data block.
404 * Just read that one in.
405 */
406 else {
407 if ((error =
408 xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, use_block),
409 -1, &dbp, XFS_DATA_FORK))) {
410 xfs_da_brelse(tp, lbp);
411 return error;
412 }
413 data = dbp->data;
414 grown = 0;
415 }
416 xfs_dir2_data_check(dp, dbp);
417 /*
418 * Point to the biggest freespace in our data block.
419 */
420 dup = (xfs_dir2_data_unused_t *)
421 ((char *)data + INT_GET(data->hdr.bestfree[0].offset, ARCH_CONVERT));
422 ASSERT(INT_GET(dup->length, ARCH_CONVERT) >= length);
423 needscan = needlog = 0;
424 /*
425 * Mark the initial part of our freespace in use for the new entry.
426 */
427 xfs_dir2_data_use_free(tp, dbp, dup,
428 (xfs_dir2_data_aoff_t)((char *)dup - (char *)data), length,
429 &needlog, &needscan);
430 /*
431 * Initialize our new entry (at last).
432 */
433 dep = (xfs_dir2_data_entry_t *)dup;
434 INT_SET(dep->inumber, ARCH_CONVERT, args->inumber);
435 dep->namelen = args->namelen;
436 memcpy(dep->name, args->name, dep->namelen);
437 tagp = XFS_DIR2_DATA_ENTRY_TAG_P(dep);
438 INT_SET(*tagp, ARCH_CONVERT, (xfs_dir2_data_off_t)((char *)dep - (char *)data));
439 /*
440 * Need to scan fix up the bestfree table.
441 */
442 if (needscan)
443 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
444 /*
445 * Need to log the data block's header.
446 */
447 if (needlog)
448 xfs_dir2_data_log_header(tp, dbp);
449 xfs_dir2_data_log_entry(tp, dbp, dep);
450 /*
451 * If the bests table needs to be changed, do it.
452 * Log the change unless we've already done that.
453 */
454 if (INT_GET(bestsp[use_block], ARCH_CONVERT) != INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT)) {
455 INT_COPY(bestsp[use_block], data->hdr.bestfree[0].length, ARCH_CONVERT);
456 if (!grown)
457 xfs_dir2_leaf_log_bests(tp, lbp, use_block, use_block);
458 }
459 /*
460 * Now we need to make room to insert the leaf entry.
461 * If there are no stale entries, we just insert a hole at index.
462 */
463 if (!leaf->hdr.stale) {
464 /*
465 * lep is still good as the index leaf entry.
466 */
467 if (index < INT_GET(leaf->hdr.count, ARCH_CONVERT))
468 memmove(lep + 1, lep,
469 (INT_GET(leaf->hdr.count, ARCH_CONVERT) - index) * sizeof(*lep));
470 /*
471 * Record low and high logging indices for the leaf.
472 */
473 lfloglow = index;
474 lfloghigh = INT_GET(leaf->hdr.count, ARCH_CONVERT);
475 INT_MOD(leaf->hdr.count, ARCH_CONVERT, +1);
476 }
477 /*
478 * There are stale entries.
479 * We will use one of them for the new entry.
480 * It's probably not at the right location, so we'll have to
481 * shift some up or down first.
482 */
483 else {
484 /*
485 * If we didn't compact before, we need to find the nearest
486 * stale entries before and after our insertion point.
487 */
488 if (compact == 0) {
489 /*
490 * Find the first stale entry before the insertion
491 * point, if any.
492 */
493 for (lowstale = index - 1;
494 lowstale >= 0 &&
495 INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) !=
496 XFS_DIR2_NULL_DATAPTR;
497 lowstale--)
498 continue;
499 /*
500 * Find the next stale entry at or after the insertion
501 * point, if any. Stop if we go so far that the
502 * lowstale entry would be better.
503 */
504 for (highstale = index;
505 highstale < INT_GET(leaf->hdr.count, ARCH_CONVERT) &&
506 INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) !=
507 XFS_DIR2_NULL_DATAPTR &&
508 (lowstale < 0 ||
509 index - lowstale - 1 >= highstale - index);
510 highstale++)
511 continue;
512 }
513 /*
514 * If the low one is better, use it.
515 */
516 if (lowstale >= 0 &&
517 (highstale == INT_GET(leaf->hdr.count, ARCH_CONVERT) ||
518 index - lowstale - 1 < highstale - index)) {
519 ASSERT(index - lowstale - 1 >= 0);
520 ASSERT(INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) ==
521 XFS_DIR2_NULL_DATAPTR);
522 /*
523 * Copy entries up to cover the stale entry
524 * and make room for the new entry.
525 */
526 if (index - lowstale - 1 > 0)
527 memmove(&leaf->ents[lowstale],
528 &leaf->ents[lowstale + 1],
529 (index - lowstale - 1) * sizeof(*lep));
530 lep = &leaf->ents[index - 1];
531 lfloglow = MIN(lowstale, lfloglow);
532 lfloghigh = MAX(index - 1, lfloghigh);
533 }
534 /*
535 * The high one is better, so use that one.
536 */
537 else {
538 ASSERT(highstale - index >= 0);
539 ASSERT(INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) ==
540 XFS_DIR2_NULL_DATAPTR);
541 /*
542 * Copy entries down to copver the stale entry
543 * and make room for the new entry.
544 */
545 if (highstale - index > 0)
546 memmove(&leaf->ents[index + 1],
547 &leaf->ents[index],
548 (highstale - index) * sizeof(*lep));
549 lep = &leaf->ents[index];
550 lfloglow = MIN(index, lfloglow);
551 lfloghigh = MAX(highstale, lfloghigh);
552 }
553 INT_MOD(leaf->hdr.stale, ARCH_CONVERT, -1);
554 }
555 /*
556 * Fill in the new leaf entry.
557 */
558 INT_SET(lep->hashval, ARCH_CONVERT, args->hashval);
559 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_DB_OFF_TO_DATAPTR(mp, use_block, INT_GET(*tagp, ARCH_CONVERT)));
560 /*
561 * Log the leaf fields and give up the buffers.
562 */
563 xfs_dir2_leaf_log_header(tp, lbp);
564 xfs_dir2_leaf_log_ents(tp, lbp, lfloglow, lfloghigh);
565 xfs_dir2_leaf_check(dp, lbp);
566 xfs_da_buf_done(lbp);
567 xfs_dir2_data_check(dp, dbp);
568 xfs_da_buf_done(dbp);
569 return 0;
570 }
571
572 #ifdef DEBUG
573 /*
574 * Check the internal consistency of a leaf1 block.
575 * Pop an assert if something is wrong.
576 */
577 void
578 xfs_dir2_leaf_check(
579 xfs_inode_t *dp, /* incore directory inode */
580 xfs_dabuf_t *bp) /* leaf's buffer */
581 {
582 int i; /* leaf index */
583 xfs_dir2_leaf_t *leaf; /* leaf structure */
584 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
585 xfs_mount_t *mp; /* filesystem mount point */
586 int stale; /* count of stale leaves */
587
588 leaf = bp->data;
589 mp = dp->i_mount;
590 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC);
591 /*
592 * This value is not restrictive enough.
593 * Should factor in the size of the bests table as well.
594 * We can deduce a value for that from di_size.
595 */
596 ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) <= XFS_DIR2_MAX_LEAF_ENTS(mp));
597 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
598 /*
599 * Leaves and bests don't overlap.
600 */
601 ASSERT((char *)&leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT)] <=
602 (char *)XFS_DIR2_LEAF_BESTS_P(ltp));
603 /*
604 * Check hash value order, count stale entries.
605 */
606 for (i = stale = 0; i < INT_GET(leaf->hdr.count, ARCH_CONVERT); i++) {
607 if (i + 1 < INT_GET(leaf->hdr.count, ARCH_CONVERT))
608 ASSERT(INT_GET(leaf->ents[i].hashval, ARCH_CONVERT) <=
609 INT_GET(leaf->ents[i + 1].hashval, ARCH_CONVERT));
610 if (INT_GET(leaf->ents[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
611 stale++;
612 }
613 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) == stale);
614 }
615 #endif /* DEBUG */
616
617 /*
618 * Compact out any stale entries in the leaf.
619 * Log the header and changed leaf entries, if any.
620 */
621 void
622 xfs_dir2_leaf_compact(
623 xfs_da_args_t *args, /* operation arguments */
624 xfs_dabuf_t *bp) /* leaf buffer */
625 {
626 int from; /* source leaf index */
627 xfs_dir2_leaf_t *leaf; /* leaf structure */
628 int loglow; /* first leaf entry to log */
629 int to; /* target leaf index */
630
631 leaf = bp->data;
632 if (!leaf->hdr.stale) {
633 return;
634 }
635 /*
636 * Compress out the stale entries in place.
637 */
638 for (from = to = 0, loglow = -1; from < INT_GET(leaf->hdr.count, ARCH_CONVERT); from++) {
639 if (INT_GET(leaf->ents[from].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
640 continue;
641 /*
642 * Only actually copy the entries that are different.
643 */
644 if (from > to) {
645 if (loglow == -1)
646 loglow = to;
647 leaf->ents[to] = leaf->ents[from];
648 }
649 to++;
650 }
651 /*
652 * Update and log the header, log the leaf entries.
653 */
654 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) == from - to);
655 INT_MOD(leaf->hdr.count, ARCH_CONVERT, -(INT_GET(leaf->hdr.stale, ARCH_CONVERT)));
656 leaf->hdr.stale = 0;
657 xfs_dir2_leaf_log_header(args->trans, bp);
658 if (loglow != -1)
659 xfs_dir2_leaf_log_ents(args->trans, bp, loglow, to - 1);
660 }
661
662 /*
663 * Compact the leaf entries, removing stale ones.
664 * Leave one stale entry behind - the one closest to our
665 * insertion index - and the caller will shift that one to our insertion
666 * point later.
667 * Return new insertion index, where the remaining stale entry is,
668 * and leaf logging indices.
669 */
670 void
671 xfs_dir2_leaf_compact_x1(
672 xfs_dabuf_t *bp, /* leaf buffer */
673 int *indexp, /* insertion index */
674 int *lowstalep, /* out: stale entry before us */
675 int *highstalep, /* out: stale entry after us */
676 int *lowlogp, /* out: low log index */
677 int *highlogp) /* out: high log index */
678 {
679 int from; /* source copy index */
680 int highstale; /* stale entry at/after index */
681 int index; /* insertion index */
682 int keepstale; /* source index of kept stale */
683 xfs_dir2_leaf_t *leaf; /* leaf structure */
684 int lowstale; /* stale entry before index */
685 int newindex=0; /* new insertion index */
686 int to; /* destination copy index */
687
688 leaf = bp->data;
689 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) > 1);
690 index = *indexp;
691 /*
692 * Find the first stale entry before our index, if any.
693 */
694 for (lowstale = index - 1;
695 lowstale >= 0 &&
696 INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) != XFS_DIR2_NULL_DATAPTR;
697 lowstale--)
698 continue;
699 /*
700 * Find the first stale entry at or after our index, if any.
701 * Stop if the answer would be worse than lowstale.
702 */
703 for (highstale = index;
704 highstale < INT_GET(leaf->hdr.count, ARCH_CONVERT) &&
705 INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) != XFS_DIR2_NULL_DATAPTR &&
706 (lowstale < 0 || index - lowstale > highstale - index);
707 highstale++)
708 continue;
709 /*
710 * Pick the better of lowstale and highstale.
711 */
712 if (lowstale >= 0 &&
713 (highstale == INT_GET(leaf->hdr.count, ARCH_CONVERT) ||
714 index - lowstale <= highstale - index))
715 keepstale = lowstale;
716 else
717 keepstale = highstale;
718 /*
719 * Copy the entries in place, removing all the stale entries
720 * except keepstale.
721 */
722 for (from = to = 0; from < INT_GET(leaf->hdr.count, ARCH_CONVERT); from++) {
723 /*
724 * Notice the new value of index.
725 */
726 if (index == from)
727 newindex = to;
728 if (from != keepstale &&
729 INT_GET(leaf->ents[from].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR) {
730 if (from == to)
731 *lowlogp = to;
732 continue;
733 }
734 /*
735 * Record the new keepstale value for the insertion.
736 */
737 if (from == keepstale)
738 lowstale = highstale = to;
739 /*
740 * Copy only the entries that have moved.
741 */
742 if (from > to)
743 leaf->ents[to] = leaf->ents[from];
744 to++;
745 }
746 ASSERT(from > to);
747 /*
748 * If the insertion point was past the last entry,
749 * set the new insertion point accordingly.
750 */
751 if (index == from)
752 newindex = to;
753 *indexp = newindex;
754 /*
755 * Adjust the leaf header values.
756 */
757 INT_MOD(leaf->hdr.count, ARCH_CONVERT, -(from - to));
758 INT_SET(leaf->hdr.stale, ARCH_CONVERT, 1);
759 /*
760 * Remember the low/high stale value only in the "right"
761 * direction.
762 */
763 if (lowstale >= newindex)
764 lowstale = -1;
765 else
766 highstale = INT_GET(leaf->hdr.count, ARCH_CONVERT);
767 *highlogp = INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1;
768 *lowstalep = lowstale;
769 *highstalep = highstale;
770 }
771
772 /*
773 * Getdents (readdir) for leaf and node directories.
774 * This reads the data blocks only, so is the same for both forms.
775 */
776 int /* error */
777 xfs_dir2_leaf_getdents(
778 xfs_trans_t *tp, /* transaction pointer */
779 xfs_inode_t *dp, /* incore directory inode */
780 uio_t *uio, /* I/O control & vectors */
781 int *eofp, /* out: reached end of dir */
782 xfs_dirent_t *dbp, /* caller's buffer */
783 xfs_dir2_put_t put) /* ABI formatting routine */
784 {
785 xfs_dabuf_t *bp; /* data block buffer */
786 int byteoff; /* offset in current block */
787 xfs_dir2_db_t curdb; /* db for current block */
788 xfs_dir2_off_t curoff; /* current overall offset */
789 xfs_dir2_data_t *data; /* data block structure */
790 xfs_dir2_data_entry_t *dep; /* data entry */
791 xfs_dir2_data_unused_t *dup; /* unused entry */
792 int eof; /* reached end of directory */
793 int error=0; /* error return value */
794 int i; /* temporary loop index */
795 int j; /* temporary loop index */
796 int length; /* temporary length value */
797 xfs_bmbt_irec_t *map; /* map vector for blocks */
798 xfs_extlen_t map_blocks; /* number of fsbs in map */
799 xfs_dablk_t map_off; /* last mapped file offset */
800 int map_size; /* total entries in *map */
801 int map_valid; /* valid entries in *map */
802 xfs_mount_t *mp; /* filesystem mount point */
803 xfs_dir2_off_t newoff; /* new curoff after new blk */
804 int nmap; /* mappings to ask xfs_bmapi */
805 xfs_dir2_put_args_t p; /* formatting arg bundle */
806 char *ptr=NULL; /* pointer to current data */
807 int ra_current; /* number of read-ahead blks */
808 int ra_index; /* *map index for read-ahead */
809 int ra_offset; /* map entry offset for ra */
810 int ra_want; /* readahead count wanted */
811
812 /*
813 * If the offset is at or past the largest allowed value,
814 * give up right away, return eof.
815 */
816 if (uio->uio_offset >= XFS_DIR2_MAX_DATAPTR) {
817 *eofp = 1;
818 return 0;
819 }
820 mp = dp->i_mount;
821 /*
822 * Setup formatting arguments.
823 */
824 p.dbp = dbp;
825 p.put = put;
826 p.uio = uio;
827 /*
828 * Set up to bmap a number of blocks based on the caller's
829 * buffer size, the directory block size, and the filesystem
830 * block size.
831 */
832 map_size =
833 howmany(uio->uio_resid + mp->m_dirblksize,
834 mp->m_sb.sb_blocksize);
835 map = kmem_alloc(map_size * sizeof(*map), KM_SLEEP);
836 map_valid = ra_index = ra_offset = ra_current = map_blocks = 0;
837 bp = NULL;
838 eof = 1;
839 /*
840 * Inside the loop we keep the main offset value as a byte offset
841 * in the directory file.
842 */
843 curoff = XFS_DIR2_DATAPTR_TO_BYTE(mp, uio->uio_offset);
844 /*
845 * Force this conversion through db so we truncate the offset
846 * down to get the start of the data block.
847 */
848 map_off = XFS_DIR2_DB_TO_DA(mp, XFS_DIR2_BYTE_TO_DB(mp, curoff));
849 /*
850 * Loop over directory entries until we reach the end offset.
851 * Get more blocks and readahead as necessary.
852 */
853 while (curoff < XFS_DIR2_LEAF_OFFSET) {
854 /*
855 * If we have no buffer, or we're off the end of the
856 * current buffer, need to get another one.
857 */
858 if (!bp || ptr >= (char *)bp->data + mp->m_dirblksize) {
859 /*
860 * If we have a buffer, we need to release it and
861 * take it out of the mapping.
862 */
863 if (bp) {
864 xfs_da_brelse(tp, bp);
865 bp = NULL;
866 map_blocks -= mp->m_dirblkfsbs;
867 /*
868 * Loop to get rid of the extents for the
869 * directory block.
870 */
871 for (i = mp->m_dirblkfsbs; i > 0; ) {
872 j = MIN((int)map->br_blockcount, i);
873 map->br_blockcount -= j;
874 map->br_startblock += j;
875 map->br_startoff += j;
876 /*
877 * If mapping is done, pitch it from
878 * the table.
879 */
880 if (!map->br_blockcount && --map_valid)
881 memmove(&map[0], &map[1],
882 sizeof(map[0]) *
883 map_valid);
884 i -= j;
885 }
886 }
887 /*
888 * Recalculate the readahead blocks wanted.
889 */
890 ra_want = howmany(uio->uio_resid + mp->m_dirblksize,
891 mp->m_sb.sb_blocksize) - 1;
892 /*
893 * If we don't have as many as we want, and we haven't
894 * run out of data blocks, get some more mappings.
895 */
896 if (1 + ra_want > map_blocks &&
897 map_off <
898 XFS_DIR2_BYTE_TO_DA(mp, XFS_DIR2_LEAF_OFFSET)) {
899 /*
900 * Get more bmaps, fill in after the ones
901 * we already have in the table.
902 */
903 nmap = map_size - map_valid;
904 error = xfs_bmapi(tp, dp,
905 map_off,
906 XFS_DIR2_BYTE_TO_DA(mp,
907 XFS_DIR2_LEAF_OFFSET) - map_off,
908 XFS_BMAPI_METADATA, NULL, 0,
909 &map[map_valid], &nmap, NULL);
910 /*
911 * Don't know if we should ignore this or
912 * try to return an error.
913 * The trouble with returning errors
914 * is that readdir will just stop without
915 * actually passing the error through.
916 */
917 if (error)
918 break; /* XXX */
919 /*
920 * If we got all the mappings we asked for,
921 * set the final map offset based on the
922 * last bmap value received.
923 * Otherwise, we've reached the end.
924 */
925 if (nmap == map_size - map_valid)
926 map_off =
927 map[map_valid + nmap - 1].br_startoff +
928 map[map_valid + nmap - 1].br_blockcount;
929 else
930 map_off =
931 XFS_DIR2_BYTE_TO_DA(mp,
932 XFS_DIR2_LEAF_OFFSET);
933 /*
934 * Look for holes in the mapping, and
935 * eliminate them. Count up the valid blocks.
936 */
937 for (i = map_valid; i < map_valid + nmap; ) {
938 if (map[i].br_startblock ==
939 HOLESTARTBLOCK) {
940 nmap--;
941 length = map_valid + nmap - i;
942 if (length)
943 memmove(&map[i],
944 &map[i + 1],
945 sizeof(map[i]) *
946 length);
947 } else {
948 map_blocks +=
949 map[i].br_blockcount;
950 i++;
951 }
952 }
953 map_valid += nmap;
954 }
955 /*
956 * No valid mappings, so no more data blocks.
957 */
958 if (!map_valid) {
959 curoff = XFS_DIR2_DA_TO_BYTE(mp, map_off);
960 break;
961 }
962 /*
963 * Read the directory block starting at the first
964 * mapping.
965 */
966 curdb = XFS_DIR2_DA_TO_DB(mp, map->br_startoff);
967 error = xfs_da_read_buf(tp, dp, map->br_startoff,
968 map->br_blockcount >= mp->m_dirblkfsbs ?
969 XFS_FSB_TO_DADDR(mp, map->br_startblock) :
970 -1,
971 &bp, XFS_DATA_FORK);
972 /*
973 * Should just skip over the data block instead
974 * of giving up.
975 */
976 if (error)
977 break; /* XXX */
978 /*
979 * Adjust the current amount of read-ahead: we just
980 * read a block that was previously ra.
981 */
982 if (ra_current)
983 ra_current -= mp->m_dirblkfsbs;
984 /*
985 * Do we need more readahead?
986 */
987 for (ra_index = ra_offset = i = 0;
988 ra_want > ra_current && i < map_blocks;
989 i += mp->m_dirblkfsbs) {
990 ASSERT(ra_index < map_valid);
991 /*
992 * Read-ahead a contiguous directory block.
993 */
994 if (i > ra_current &&
995 map[ra_index].br_blockcount >=
996 mp->m_dirblkfsbs) {
997 xfs_baread(mp->m_ddev_targp,
998 XFS_FSB_TO_DADDR(mp,
999 map[ra_index].br_startblock +
1000 ra_offset),
1001 (int)BTOBB(mp->m_dirblksize));
1002 ra_current = i;
1003 }
1004 /*
1005 * Read-ahead a non-contiguous directory block.
1006 * This doesn't use our mapping, but this
1007 * is a very rare case.
1008 */
1009 else if (i > ra_current) {
1010 (void)xfs_da_reada_buf(tp, dp,
1011 map[ra_index].br_startoff +
1012 ra_offset, XFS_DATA_FORK);
1013 ra_current = i;
1014 }
1015 /*
1016 * Advance offset through the mapping table.
1017 */
1018 for (j = 0; j < mp->m_dirblkfsbs; j++) {
1019 /*
1020 * The rest of this extent but not
1021 * more than a dir block.
1022 */
1023 length = MIN(mp->m_dirblkfsbs,
1024 (int)(map[ra_index].br_blockcount -
1025 ra_offset));
1026 j += length;
1027 ra_offset += length;
1028 /*
1029 * Advance to the next mapping if
1030 * this one is used up.
1031 */
1032 if (ra_offset ==
1033 map[ra_index].br_blockcount) {
1034 ra_offset = 0;
1035 ra_index++;
1036 }
1037 }
1038 }
1039 /*
1040 * Having done a read, we need to set a new offset.
1041 */
1042 newoff = XFS_DIR2_DB_OFF_TO_BYTE(mp, curdb, 0);
1043 /*
1044 * Start of the current block.
1045 */
1046 if (curoff < newoff)
1047 curoff = newoff;
1048 /*
1049 * Make sure we're in the right block.
1050 */
1051 else if (curoff > newoff)
1052 ASSERT(XFS_DIR2_BYTE_TO_DB(mp, curoff) ==
1053 curdb);
1054 data = bp->data;
1055 xfs_dir2_data_check(dp, bp);
1056 /*
1057 * Find our position in the block.
1058 */
1059 ptr = (char *)&data->u;
1060 byteoff = XFS_DIR2_BYTE_TO_OFF(mp, curoff);
1061 /*
1062 * Skip past the header.
1063 */
1064 if (byteoff == 0)
1065 curoff += (uint)sizeof(data->hdr);
1066 /*
1067 * Skip past entries until we reach our offset.
1068 */
1069 else {
1070 while ((char *)ptr - (char *)data < byteoff) {
1071 dup = (xfs_dir2_data_unused_t *)ptr;
1072
1073 if (INT_GET(dup->freetag, ARCH_CONVERT)
1074 == XFS_DIR2_DATA_FREE_TAG) {
1075
1076 length = INT_GET(dup->length,
1077 ARCH_CONVERT);
1078 ptr += length;
1079 continue;
1080 }
1081 dep = (xfs_dir2_data_entry_t *)ptr;
1082 length =
1083 XFS_DIR2_DATA_ENTSIZE(dep->namelen);
1084 ptr += length;
1085 }
1086 /*
1087 * Now set our real offset.
1088 */
1089 curoff =
1090 XFS_DIR2_DB_OFF_TO_BYTE(mp,
1091 XFS_DIR2_BYTE_TO_DB(mp, curoff),
1092 (char *)ptr - (char *)data);
1093 if (ptr >= (char *)data + mp->m_dirblksize) {
1094 continue;
1095 }
1096 }
1097 }
1098 /*
1099 * We have a pointer to an entry.
1100 * Is it a live one?
1101 */
1102 dup = (xfs_dir2_data_unused_t *)ptr;
1103 /*
1104 * No, it's unused, skip over it.
1105 */
1106 if (INT_GET(dup->freetag, ARCH_CONVERT)
1107 == XFS_DIR2_DATA_FREE_TAG) {
1108 length = INT_GET(dup->length, ARCH_CONVERT);
1109 ptr += length;
1110 curoff += length;
1111 continue;
1112 }
1113
1114 /*
1115 * Copy the entry into the putargs, and try formatting it.
1116 */
1117 dep = (xfs_dir2_data_entry_t *)ptr;
1118
1119 p.namelen = dep->namelen;
1120
1121 length = XFS_DIR2_DATA_ENTSIZE(p.namelen);
1122
1123 p.cook = XFS_DIR2_BYTE_TO_DATAPTR(mp, curoff + length);
1124
1125 p.ino = INT_GET(dep->inumber, ARCH_CONVERT);
1126 #if XFS_BIG_INUMS
1127 p.ino += mp->m_inoadd;
1128 #endif
1129 p.name = (char *)dep->name;
1130
1131 error = p.put(&p);
1132
1133 /*
1134 * Won't fit. Return to caller.
1135 */
1136 if (!p.done) {
1137 eof = 0;
1138 break;
1139 }
1140 /*
1141 * Advance to next entry in the block.
1142 */
1143 ptr += length;
1144 curoff += length;
1145 }
1146
1147 /*
1148 * All done. Set output offset value to current offset.
1149 */
1150 *eofp = eof;
1151 if (curoff > XFS_DIR2_DATAPTR_TO_BYTE(mp, XFS_DIR2_MAX_DATAPTR))
1152 uio->uio_offset = XFS_DIR2_MAX_DATAPTR;
1153 else
1154 uio->uio_offset = XFS_DIR2_BYTE_TO_DATAPTR(mp, curoff);
1155 kmem_free(map, map_size * sizeof(*map));
1156 if (bp)
1157 xfs_da_brelse(tp, bp);
1158 return error;
1159 }
1160
1161 /*
1162 * Initialize a new leaf block, leaf1 or leafn magic accepted.
1163 */
1164 int
1165 xfs_dir2_leaf_init(
1166 xfs_da_args_t *args, /* operation arguments */
1167 xfs_dir2_db_t bno, /* directory block number */
1168 xfs_dabuf_t **bpp, /* out: leaf buffer */
1169 int magic) /* magic number for block */
1170 {
1171 xfs_dabuf_t *bp; /* leaf buffer */
1172 xfs_inode_t *dp; /* incore directory inode */
1173 int error; /* error return code */
1174 xfs_dir2_leaf_t *leaf; /* leaf structure */
1175 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1176 xfs_mount_t *mp; /* filesystem mount point */
1177 xfs_trans_t *tp; /* transaction pointer */
1178
1179 dp = args->dp;
1180 ASSERT(dp != NULL);
1181 tp = args->trans;
1182 mp = dp->i_mount;
1183 ASSERT(bno >= XFS_DIR2_LEAF_FIRSTDB(mp) &&
1184 bno < XFS_DIR2_FREE_FIRSTDB(mp));
1185 /*
1186 * Get the buffer for the block.
1187 */
1188 error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, bno), -1, &bp,
1189 XFS_DATA_FORK);
1190 if (error) {
1191 return error;
1192 }
1193 ASSERT(bp != NULL);
1194 leaf = bp->data;
1195 /*
1196 * Initialize the header.
1197 */
1198 INT_SET(leaf->hdr.info.magic, ARCH_CONVERT, magic);
1199 leaf->hdr.info.forw = 0;
1200 leaf->hdr.info.back = 0;
1201 leaf->hdr.count = 0;
1202 leaf->hdr.stale = 0;
1203 xfs_dir2_leaf_log_header(tp, bp);
1204 /*
1205 * If it's a leaf-format directory initialize the tail.
1206 * In this case our caller has the real bests table to copy into
1207 * the block.
1208 */
1209 if (magic == XFS_DIR2_LEAF1_MAGIC) {
1210 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1211 ltp->bestcount = 0;
1212 xfs_dir2_leaf_log_tail(tp, bp);
1213 }
1214 *bpp = bp;
1215 return 0;
1216 }
1217
1218 /*
1219 * Log the bests entries indicated from a leaf1 block.
1220 */
1221 static void
1222 xfs_dir2_leaf_log_bests(
1223 xfs_trans_t *tp, /* transaction pointer */
1224 xfs_dabuf_t *bp, /* leaf buffer */
1225 int first, /* first entry to log */
1226 int last) /* last entry to log */
1227 {
1228 xfs_dir2_data_off_t *firstb; /* pointer to first entry */
1229 xfs_dir2_data_off_t *lastb; /* pointer to last entry */
1230 xfs_dir2_leaf_t *leaf; /* leaf structure */
1231 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1232
1233 leaf = bp->data;
1234 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC);
1235 ltp = XFS_DIR2_LEAF_TAIL_P(tp->t_mountp, leaf);
1236 firstb = XFS_DIR2_LEAF_BESTS_P(ltp) + first;
1237 lastb = XFS_DIR2_LEAF_BESTS_P(ltp) + last;
1238 xfs_da_log_buf(tp, bp, (uint)((char *)firstb - (char *)leaf),
1239 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1240 }
1241
1242 /*
1243 * Log the leaf entries indicated from a leaf1 or leafn block.
1244 */
1245 void
1246 xfs_dir2_leaf_log_ents(
1247 xfs_trans_t *tp, /* transaction pointer */
1248 xfs_dabuf_t *bp, /* leaf buffer */
1249 int first, /* first entry to log */
1250 int last) /* last entry to log */
1251 {
1252 xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
1253 xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
1254 xfs_dir2_leaf_t *leaf; /* leaf structure */
1255
1256 leaf = bp->data;
1257 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC ||
1258 INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1259 firstlep = &leaf->ents[first];
1260 lastlep = &leaf->ents[last];
1261 xfs_da_log_buf(tp, bp, (uint)((char *)firstlep - (char *)leaf),
1262 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1263 }
1264
1265 /*
1266 * Log the header of the leaf1 or leafn block.
1267 */
1268 void
1269 xfs_dir2_leaf_log_header(
1270 xfs_trans_t *tp, /* transaction pointer */
1271 xfs_dabuf_t *bp) /* leaf buffer */
1272 {
1273 xfs_dir2_leaf_t *leaf; /* leaf structure */
1274
1275 leaf = bp->data;
1276 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC ||
1277 INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1278 xfs_da_log_buf(tp, bp, (uint)((char *)&leaf->hdr - (char *)leaf),
1279 (uint)(sizeof(leaf->hdr) - 1));
1280 }
1281
1282 /*
1283 * Log the tail of the leaf1 block.
1284 */
1285 STATIC void
1286 xfs_dir2_leaf_log_tail(
1287 xfs_trans_t *tp, /* transaction pointer */
1288 xfs_dabuf_t *bp) /* leaf buffer */
1289 {
1290 xfs_dir2_leaf_t *leaf; /* leaf structure */
1291 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1292 xfs_mount_t *mp; /* filesystem mount point */
1293
1294 mp = tp->t_mountp;
1295 leaf = bp->data;
1296 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAF1_MAGIC);
1297 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1298 xfs_da_log_buf(tp, bp, (uint)((char *)ltp - (char *)leaf),
1299 (uint)(mp->m_dirblksize - 1));
1300 }
1301
1302 /*
1303 * Look up the entry referred to by args in the leaf format directory.
1304 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1305 * is also used by the node-format code.
1306 */
1307 int
1308 xfs_dir2_leaf_lookup(
1309 xfs_da_args_t *args) /* operation arguments */
1310 {
1311 xfs_dabuf_t *dbp; /* data block buffer */
1312 xfs_dir2_data_entry_t *dep; /* data block entry */
1313 xfs_inode_t *dp; /* incore directory inode */
1314 int error; /* error return code */
1315 int index; /* found entry index */
1316 xfs_dabuf_t *lbp; /* leaf buffer */
1317 xfs_dir2_leaf_t *leaf; /* leaf structure */
1318 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1319 xfs_trans_t *tp; /* transaction pointer */
1320
1321 xfs_dir2_trace_args("leaf_lookup", args);
1322 /*
1323 * Look up name in the leaf block, returning both buffers and index.
1324 */
1325 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1326 return error;
1327 }
1328 tp = args->trans;
1329 dp = args->dp;
1330 xfs_dir2_leaf_check(dp, lbp);
1331 leaf = lbp->data;
1332 /*
1333 * Get to the leaf entry and contained data entry address.
1334 */
1335 lep = &leaf->ents[index];
1336 /*
1337 * Point to the data entry.
1338 */
1339 dep = (xfs_dir2_data_entry_t *)
1340 ((char *)dbp->data +
1341 XFS_DIR2_DATAPTR_TO_OFF(dp->i_mount, INT_GET(lep->address, ARCH_CONVERT)));
1342 /*
1343 * Return the found inode number.
1344 */
1345 args->inumber = INT_GET(dep->inumber, ARCH_CONVERT);
1346 xfs_da_brelse(tp, dbp);
1347 xfs_da_brelse(tp, lbp);
1348 return XFS_ERROR(EEXIST);
1349 }
1350
1351 /*
1352 * Look up name/hash in the leaf block.
1353 * Fill in indexp with the found index, and dbpp with the data buffer.
1354 * If not found dbpp will be NULL, and ENOENT comes back.
1355 * lbpp will always be filled in with the leaf buffer unless there's an error.
1356 */
1357 static int /* error */
1358 xfs_dir2_leaf_lookup_int(
1359 xfs_da_args_t *args, /* operation arguments */
1360 xfs_dabuf_t **lbpp, /* out: leaf buffer */
1361 int *indexp, /* out: index in leaf block */
1362 xfs_dabuf_t **dbpp) /* out: data buffer */
1363 {
1364 xfs_dir2_db_t curdb; /* current data block number */
1365 xfs_dabuf_t *dbp; /* data buffer */
1366 xfs_dir2_data_entry_t *dep; /* data entry */
1367 xfs_inode_t *dp; /* incore directory inode */
1368 int error; /* error return code */
1369 int index; /* index in leaf block */
1370 xfs_dabuf_t *lbp; /* leaf buffer */
1371 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1372 xfs_dir2_leaf_t *leaf; /* leaf structure */
1373 xfs_mount_t *mp; /* filesystem mount point */
1374 xfs_dir2_db_t newdb; /* new data block number */
1375 xfs_trans_t *tp; /* transaction pointer */
1376
1377 dp = args->dp;
1378 tp = args->trans;
1379 mp = dp->i_mount;
1380 /*
1381 * Read the leaf block into the buffer.
1382 */
1383 if ((error =
1384 xfs_da_read_buf(tp, dp, mp->m_dirleafblk, -1, &lbp,
1385 XFS_DATA_FORK))) {
1386 return error;
1387 }
1388 *lbpp = lbp;
1389 leaf = lbp->data;
1390 xfs_dir2_leaf_check(dp, lbp);
1391 /*
1392 * Look for the first leaf entry with our hash value.
1393 */
1394 index = xfs_dir2_leaf_search_hash(args, lbp);
1395 /*
1396 * Loop over all the entries with the right hash value
1397 * looking to match the name.
1398 */
1399 for (lep = &leaf->ents[index], dbp = NULL, curdb = -1;
1400 index < INT_GET(leaf->hdr.count, ARCH_CONVERT) && INT_GET(lep->hashval, ARCH_CONVERT) == args->hashval;
1401 lep++, index++) {
1402 /*
1403 * Skip over stale leaf entries.
1404 */
1405 if (INT_GET(lep->address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
1406 continue;
1407 /*
1408 * Get the new data block number.
1409 */
1410 newdb = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
1411 /*
1412 * If it's not the same as the old data block number,
1413 * need to pitch the old one and read the new one.
1414 */
1415 if (newdb != curdb) {
1416 if (dbp)
1417 xfs_da_brelse(tp, dbp);
1418 if ((error =
1419 xfs_da_read_buf(tp, dp,
1420 XFS_DIR2_DB_TO_DA(mp, newdb), -1, &dbp,
1421 XFS_DATA_FORK))) {
1422 xfs_da_brelse(tp, lbp);
1423 return error;
1424 }
1425 xfs_dir2_data_check(dp, dbp);
1426 curdb = newdb;
1427 }
1428 /*
1429 * Point to the data entry.
1430 */
1431 dep = (xfs_dir2_data_entry_t *)
1432 ((char *)dbp->data +
1433 XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT)));
1434 /*
1435 * If it matches then return it.
1436 */
1437 if (dep->namelen == args->namelen &&
1438 dep->name[0] == args->name[0] &&
1439 memcmp(dep->name, args->name, args->namelen) == 0) {
1440 *dbpp = dbp;
1441 *indexp = index;
1442 return 0;
1443 }
1444 }
1445 /*
1446 * No match found, return ENOENT.
1447 */
1448 ASSERT(args->oknoent);
1449 if (dbp)
1450 xfs_da_brelse(tp, dbp);
1451 xfs_da_brelse(tp, lbp);
1452 return XFS_ERROR(ENOENT);
1453 }
1454
1455 /*
1456 * Remove an entry from a leaf format directory.
1457 */
1458 int /* error */
1459 xfs_dir2_leaf_removename(
1460 xfs_da_args_t *args) /* operation arguments */
1461 {
1462 xfs_dir2_data_off_t *bestsp; /* leaf block best freespace */
1463 xfs_dir2_data_t *data; /* data block structure */
1464 xfs_dir2_db_t db; /* data block number */
1465 xfs_dabuf_t *dbp; /* data block buffer */
1466 xfs_dir2_data_entry_t *dep; /* data entry structure */
1467 xfs_inode_t *dp; /* incore directory inode */
1468 int error; /* error return code */
1469 xfs_dir2_db_t i; /* temporary data block # */
1470 int index; /* index into leaf entries */
1471 xfs_dabuf_t *lbp; /* leaf buffer */
1472 xfs_dir2_leaf_t *leaf; /* leaf structure */
1473 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1474 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1475 xfs_mount_t *mp; /* filesystem mount point */
1476 int needlog; /* need to log data header */
1477 int needscan; /* need to rescan data frees */
1478 xfs_dir2_data_off_t oldbest; /* old value of best free */
1479 xfs_trans_t *tp; /* transaction pointer */
1480
1481 xfs_dir2_trace_args("leaf_removename", args);
1482 /*
1483 * Lookup the leaf entry, get the leaf and data blocks read in.
1484 */
1485 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1486 return error;
1487 }
1488 dp = args->dp;
1489 tp = args->trans;
1490 mp = dp->i_mount;
1491 leaf = lbp->data;
1492 data = dbp->data;
1493 xfs_dir2_data_check(dp, dbp);
1494 /*
1495 * Point to the leaf entry, use that to point to the data entry.
1496 */
1497 lep = &leaf->ents[index];
1498 db = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
1499 dep = (xfs_dir2_data_entry_t *)
1500 ((char *)data + XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT)));
1501 needscan = needlog = 0;
1502 oldbest = INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT);
1503 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1504 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
1505 ASSERT(INT_GET(bestsp[db], ARCH_CONVERT) == oldbest);
1506 /*
1507 * Mark the former data entry unused.
1508 */
1509 xfs_dir2_data_make_free(tp, dbp,
1510 (xfs_dir2_data_aoff_t)((char *)dep - (char *)data),
1511 XFS_DIR2_DATA_ENTSIZE(dep->namelen), &needlog, &needscan);
1512 /*
1513 * We just mark the leaf entry stale by putting a null in it.
1514 */
1515 INT_MOD(leaf->hdr.stale, ARCH_CONVERT, +1);
1516 xfs_dir2_leaf_log_header(tp, lbp);
1517 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_NULL_DATAPTR);
1518 xfs_dir2_leaf_log_ents(tp, lbp, index, index);
1519 /*
1520 * Scan the freespace in the data block again if necessary,
1521 * log the data block header if necessary.
1522 */
1523 if (needscan)
1524 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
1525 if (needlog)
1526 xfs_dir2_data_log_header(tp, dbp);
1527 /*
1528 * If the longest freespace in the data block has changed,
1529 * put the new value in the bests table and log that.
1530 */
1531 if (INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) != oldbest) {
1532 INT_COPY(bestsp[db], data->hdr.bestfree[0].length, ARCH_CONVERT);
1533 xfs_dir2_leaf_log_bests(tp, lbp, db, db);
1534 }
1535 xfs_dir2_data_check(dp, dbp);
1536 /*
1537 * If the data block is now empty then get rid of the data block.
1538 */
1539 if (INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) ==
1540 mp->m_dirblksize - (uint)sizeof(data->hdr)) {
1541 ASSERT(db != mp->m_dirdatablk);
1542 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1543 /*
1544 * Nope, can't get rid of it because it caused
1545 * allocation of a bmap btree block to do so.
1546 * Just go on, returning success, leaving the
1547 * empty block in place.
1548 */
1549 if (error == ENOSPC && args->total == 0) {
1550 xfs_da_buf_done(dbp);
1551 error = 0;
1552 }
1553 xfs_dir2_leaf_check(dp, lbp);
1554 xfs_da_buf_done(lbp);
1555 return error;
1556 }
1557 dbp = NULL;
1558 /*
1559 * If this is the last data block then compact the
1560 * bests table by getting rid of entries.
1561 */
1562 if (db == INT_GET(ltp->bestcount, ARCH_CONVERT) - 1) {
1563 /*
1564 * Look for the last active entry (i).
1565 */
1566 for (i = db - 1; i > 0; i--) {
1567 if (INT_GET(bestsp[i], ARCH_CONVERT) != NULLDATAOFF)
1568 break;
1569 }
1570 /*
1571 * Copy the table down so inactive entries at the
1572 * end are removed.
1573 */
1574 memmove(&bestsp[db - i], bestsp,
1575 (INT_GET(ltp->bestcount, ARCH_CONVERT) - (db - i)) * sizeof(*bestsp));
1576 INT_MOD(ltp->bestcount, ARCH_CONVERT, -(db - i));
1577 xfs_dir2_leaf_log_tail(tp, lbp);
1578 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1579 } else
1580 INT_SET(bestsp[db], ARCH_CONVERT, NULLDATAOFF);
1581 }
1582 /*
1583 * If the data block was not the first one, drop it.
1584 */
1585 else if (db != mp->m_dirdatablk && dbp != NULL) {
1586 xfs_da_buf_done(dbp);
1587 dbp = NULL;
1588 }
1589 xfs_dir2_leaf_check(dp, lbp);
1590 /*
1591 * See if we can convert to block form.
1592 */
1593 return xfs_dir2_leaf_to_block(args, lbp, dbp);
1594 }
1595
1596 /*
1597 * Replace the inode number in a leaf format directory entry.
1598 */
1599 int /* error */
1600 xfs_dir2_leaf_replace(
1601 xfs_da_args_t *args) /* operation arguments */
1602 {
1603 xfs_dabuf_t *dbp; /* data block buffer */
1604 xfs_dir2_data_entry_t *dep; /* data block entry */
1605 xfs_inode_t *dp; /* incore directory inode */
1606 int error; /* error return code */
1607 int index; /* index of leaf entry */
1608 xfs_dabuf_t *lbp; /* leaf buffer */
1609 xfs_dir2_leaf_t *leaf; /* leaf structure */
1610 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1611 xfs_trans_t *tp; /* transaction pointer */
1612
1613 xfs_dir2_trace_args("leaf_replace", args);
1614 /*
1615 * Look up the entry.
1616 */
1617 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1618 return error;
1619 }
1620 dp = args->dp;
1621 leaf = lbp->data;
1622 /*
1623 * Point to the leaf entry, get data address from it.
1624 */
1625 lep = &leaf->ents[index];
1626 /*
1627 * Point to the data entry.
1628 */
1629 dep = (xfs_dir2_data_entry_t *)
1630 ((char *)dbp->data +
1631 XFS_DIR2_DATAPTR_TO_OFF(dp->i_mount, INT_GET(lep->address, ARCH_CONVERT)));
1632 ASSERT(args->inumber != INT_GET(dep->inumber, ARCH_CONVERT));
1633 /*
1634 * Put the new inode number in, log it.
1635 */
1636 INT_SET(dep->inumber, ARCH_CONVERT, args->inumber);
1637 tp = args->trans;
1638 xfs_dir2_data_log_entry(tp, dbp, dep);
1639 xfs_da_buf_done(dbp);
1640 xfs_dir2_leaf_check(dp, lbp);
1641 xfs_da_brelse(tp, lbp);
1642 return 0;
1643 }
1644
1645 /*
1646 * Return index in the leaf block (lbp) which is either the first
1647 * one with this hash value, or if there are none, the insert point
1648 * for that hash value.
1649 */
1650 int /* index value */
1651 xfs_dir2_leaf_search_hash(
1652 xfs_da_args_t *args, /* operation arguments */
1653 xfs_dabuf_t *lbp) /* leaf buffer */
1654 {
1655 xfs_dahash_t hash=0; /* hash from this entry */
1656 xfs_dahash_t hashwant; /* hash value looking for */
1657 int high; /* high leaf index */
1658 int low; /* low leaf index */
1659 xfs_dir2_leaf_t *leaf; /* leaf structure */
1660 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1661 int mid=0; /* current leaf index */
1662
1663 leaf = lbp->data;
1664 #ifndef __KERNEL__
1665 if (!leaf->hdr.count)
1666 return 0;
1667 #endif
1668 /*
1669 * Note, the table cannot be empty, so we have to go through the loop.
1670 * Binary search the leaf entries looking for our hash value.
1671 */
1672 for (lep = leaf->ents, low = 0, high = INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1,
1673 hashwant = args->hashval;
1674 low <= high; ) {
1675 mid = (low + high) >> 1;
1676 if ((hash = INT_GET(lep[mid].hashval, ARCH_CONVERT)) == hashwant)
1677 break;
1678 if (hash < hashwant)
1679 low = mid + 1;
1680 else
1681 high = mid - 1;
1682 }
1683 /*
1684 * Found one, back up through all the equal hash values.
1685 */
1686 if (hash == hashwant) {
1687 while (mid > 0 && INT_GET(lep[mid - 1].hashval, ARCH_CONVERT) == hashwant) {
1688 mid--;
1689 }
1690 }
1691 /*
1692 * Need to point to an entry higher than ours.
1693 */
1694 else if (hash < hashwant)
1695 mid++;
1696 return mid;
1697 }
1698
1699 /*
1700 * Trim off a trailing data block. We know it's empty since the leaf
1701 * freespace table says so.
1702 */
1703 int /* error */
1704 xfs_dir2_leaf_trim_data(
1705 xfs_da_args_t *args, /* operation arguments */
1706 xfs_dabuf_t *lbp, /* leaf buffer */
1707 xfs_dir2_db_t db) /* data block number */
1708 {
1709 xfs_dir2_data_off_t *bestsp; /* leaf bests table */
1710 #ifdef DEBUG
1711 xfs_dir2_data_t *data; /* data block structure */
1712 #endif
1713 xfs_dabuf_t *dbp; /* data block buffer */
1714 xfs_inode_t *dp; /* incore directory inode */
1715 int error; /* error return value */
1716 xfs_dir2_leaf_t *leaf; /* leaf structure */
1717 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1718 xfs_mount_t *mp; /* filesystem mount point */
1719 xfs_trans_t *tp; /* transaction pointer */
1720
1721 dp = args->dp;
1722 mp = dp->i_mount;
1723 tp = args->trans;
1724 /*
1725 * Read the offending data block. We need its buffer.
1726 */
1727 if ((error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, db), -1, &dbp,
1728 XFS_DATA_FORK))) {
1729 return error;
1730 }
1731 #ifdef DEBUG
1732 data = dbp->data;
1733 ASSERT(INT_GET(data->hdr.magic, ARCH_CONVERT) == XFS_DIR2_DATA_MAGIC);
1734 #endif
1735 /* this seems to be an error
1736 * data is only valid if DEBUG is defined?
1737 * RMC 09/08/1999
1738 */
1739
1740 leaf = lbp->data;
1741 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1742 ASSERT(INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) ==
1743 mp->m_dirblksize - (uint)sizeof(data->hdr));
1744 ASSERT(db == INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1745 /*
1746 * Get rid of the data block.
1747 */
1748 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1749 ASSERT(error != ENOSPC);
1750 xfs_da_brelse(tp, dbp);
1751 return error;
1752 }
1753 /*
1754 * Eliminate the last bests entry from the table.
1755 */
1756 bestsp = XFS_DIR2_LEAF_BESTS_P(ltp);
1757 INT_MOD(ltp->bestcount, ARCH_CONVERT, -1);
1758 memmove(&bestsp[1], &bestsp[0], INT_GET(ltp->bestcount, ARCH_CONVERT) * sizeof(*bestsp));
1759 xfs_dir2_leaf_log_tail(tp, lbp);
1760 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1761 return 0;
1762 }
1763
1764 /*
1765 * Convert node form directory to leaf form directory.
1766 * The root of the node form dir needs to already be a LEAFN block.
1767 * Just return if we can't do anything.
1768 */
1769 int /* error */
1770 xfs_dir2_node_to_leaf(
1771 xfs_da_state_t *state) /* directory operation state */
1772 {
1773 xfs_da_args_t *args; /* operation arguments */
1774 xfs_inode_t *dp; /* incore directory inode */
1775 int error; /* error return code */
1776 xfs_dabuf_t *fbp; /* buffer for freespace block */
1777 xfs_fileoff_t fo; /* freespace file offset */
1778 xfs_dir2_free_t *free; /* freespace structure */
1779 xfs_dabuf_t *lbp; /* buffer for leaf block */
1780 xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
1781 xfs_dir2_leaf_t *leaf; /* leaf structure */
1782 xfs_mount_t *mp; /* filesystem mount point */
1783 int rval; /* successful free trim? */
1784 xfs_trans_t *tp; /* transaction pointer */
1785
1786 /*
1787 * There's more than a leaf level in the btree, so there must
1788 * be multiple leafn blocks. Give up.
1789 */
1790 if (state->path.active > 1)
1791 return 0;
1792 args = state->args;
1793 xfs_dir2_trace_args("node_to_leaf", args);
1794 mp = state->mp;
1795 dp = args->dp;
1796 tp = args->trans;
1797 /*
1798 * Get the last offset in the file.
1799 */
1800 if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK))) {
1801 return error;
1802 }
1803 fo -= mp->m_dirblkfsbs;
1804 /*
1805 * If there are freespace blocks other than the first one,
1806 * take this opportunity to remove trailing empty freespace blocks
1807 * that may have been left behind during no-space-reservation
1808 * operations.
1809 */
1810 while (fo > mp->m_dirfreeblk) {
1811 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1812 return error;
1813 }
1814 if (rval)
1815 fo -= mp->m_dirblkfsbs;
1816 else
1817 return 0;
1818 }
1819 /*
1820 * Now find the block just before the freespace block.
1821 */
1822 if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1823 return error;
1824 }
1825 /*
1826 * If it's not the single leaf block, give up.
1827 */
1828 if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + mp->m_dirblksize)
1829 return 0;
1830 lbp = state->path.blk[0].bp;
1831 leaf = lbp->data;
1832 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1833 /*
1834 * Read the freespace block.
1835 */
1836 if ((error = xfs_da_read_buf(tp, dp, mp->m_dirfreeblk, -1, &fbp,
1837 XFS_DATA_FORK))) {
1838 return error;
1839 }
1840 free = fbp->data;
1841 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
1842 ASSERT(!free->hdr.firstdb);
1843 /*
1844 * Now see if the leafn and free data will fit in a leaf1.
1845 * If not, release the buffer and give up.
1846 */
1847 if ((uint)sizeof(leaf->hdr) +
1848 (INT_GET(leaf->hdr.count, ARCH_CONVERT) - INT_GET(leaf->hdr.stale, ARCH_CONVERT)) * (uint)sizeof(leaf->ents[0]) +
1849 INT_GET(free->hdr.nvalid, ARCH_CONVERT) * (uint)sizeof(leaf->bests[0]) +
1850 (uint)sizeof(leaf->tail) >
1851 mp->m_dirblksize) {
1852 xfs_da_brelse(tp, fbp);
1853 return 0;
1854 }
1855 /*
1856 * If the leaf has any stale entries in it, compress them out.
1857 * The compact routine will log the header.
1858 */
1859 if (INT_GET(leaf->hdr.stale, ARCH_CONVERT))
1860 xfs_dir2_leaf_compact(args, lbp);
1861 else
1862 xfs_dir2_leaf_log_header(tp, lbp);
1863 INT_SET(leaf->hdr.info.magic, ARCH_CONVERT, XFS_DIR2_LEAF1_MAGIC);
1864 /*
1865 * Set up the leaf tail from the freespace block.
1866 */
1867 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
1868 INT_COPY(ltp->bestcount, free->hdr.nvalid, ARCH_CONVERT);
1869 /*
1870 * Set up the leaf bests table.
1871 */
1872 memcpy(XFS_DIR2_LEAF_BESTS_P(ltp), free->bests,
1873 INT_GET(ltp->bestcount, ARCH_CONVERT) * sizeof(leaf->bests[0]));
1874 xfs_dir2_leaf_log_bests(tp, lbp, 0, INT_GET(ltp->bestcount, ARCH_CONVERT) - 1);
1875 xfs_dir2_leaf_log_tail(tp, lbp);
1876 xfs_dir2_leaf_check(dp, lbp);
1877 /*
1878 * Get rid of the freespace block.
1879 */
1880 error = xfs_dir2_shrink_inode(args, XFS_DIR2_FREE_FIRSTDB(mp), fbp);
1881 if (error) {
1882 /*
1883 * This can't fail here because it can only happen when
1884 * punching out the middle of an extent, and this is an
1885 * isolated block.
1886 */
1887 ASSERT(error != ENOSPC);
1888 return error;
1889 }
1890 fbp = NULL;
1891 /*
1892 * Now see if we can convert the single-leaf directory
1893 * down to a block form directory.
1894 * This routine always kills the dabuf for the leaf, so
1895 * eliminate it from the path.
1896 */
1897 error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1898 state->path.blk[0].bp = NULL;
1899 return error;
1900 }
Linux with added FPC-III support