?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 2.6.16.9
[wandboard.git] / fs / xfs / xfs_dir2_node.c
blob641f8633d25418309f6393c44de69d82c88c98fd
1 /*
2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_log.h"
22 #include "xfs_inum.h"
23 #include "xfs_trans.h"
24 #include "xfs_sb.h"
25 #include "xfs_dir.h"
26 #include "xfs_dir2.h"
27 #include "xfs_dmapi.h"
28 #include "xfs_mount.h"
29 #include "xfs_da_btree.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_dir_sf.h"
32 #include "xfs_dir2_sf.h"
33 #include "xfs_attr_sf.h"
34 #include "xfs_dinode.h"
35 #include "xfs_inode.h"
36 #include "xfs_bmap.h"
37 #include "xfs_dir2_data.h"
38 #include "xfs_dir2_leaf.h"
39 #include "xfs_dir2_block.h"
40 #include "xfs_dir2_node.h"
41 #include "xfs_dir2_trace.h"
42 #include "xfs_error.h"
43
44 /*
45 * Function declarations.
46 */
47 static void xfs_dir2_free_log_header(xfs_trans_t *tp, xfs_dabuf_t *bp);
48 static int xfs_dir2_leafn_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index);
49 #ifdef DEBUG
50 static void xfs_dir2_leafn_check(xfs_inode_t *dp, xfs_dabuf_t *bp);
51 #else
52 #define xfs_dir2_leafn_check(dp, bp)
53 #endif
54 static void xfs_dir2_leafn_moveents(xfs_da_args_t *args, xfs_dabuf_t *bp_s,
55 int start_s, xfs_dabuf_t *bp_d, int start_d,
56 int count);
57 static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state,
58 xfs_da_state_blk_t *blk1,
59 xfs_da_state_blk_t *blk2);
60 static int xfs_dir2_leafn_remove(xfs_da_args_t *args, xfs_dabuf_t *bp,
61 int index, xfs_da_state_blk_t *dblk,
62 int *rval);
63 static int xfs_dir2_node_addname_int(xfs_da_args_t *args,
64 xfs_da_state_blk_t *fblk);
65
66 /*
67 * Log entries from a freespace block.
68 */
69 void
70 xfs_dir2_free_log_bests(
71 xfs_trans_t *tp, /* transaction pointer */
72 xfs_dabuf_t *bp, /* freespace buffer */
73 int first, /* first entry to log */
74 int last) /* last entry to log */
75 {
76 xfs_dir2_free_t *free; /* freespace structure */
77
78 free = bp->data;
79 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
80 xfs_da_log_buf(tp, bp,
81 (uint)((char *)&free->bests[first] - (char *)free),
82 (uint)((char *)&free->bests[last] - (char *)free +
83 sizeof(free->bests[0]) - 1));
84 }
85
86 /*
87 * Log header from a freespace block.
88 */
89 static void
90 xfs_dir2_free_log_header(
91 xfs_trans_t *tp, /* transaction pointer */
92 xfs_dabuf_t *bp) /* freespace buffer */
93 {
94 xfs_dir2_free_t *free; /* freespace structure */
95
96 free = bp->data;
97 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
98 xfs_da_log_buf(tp, bp, (uint)((char *)&free->hdr - (char *)free),
99 (uint)(sizeof(xfs_dir2_free_hdr_t) - 1));
100 }
101
102 /*
103 * Convert a leaf-format directory to a node-format directory.
104 * We need to change the magic number of the leaf block, and copy
105 * the freespace table out of the leaf block into its own block.
106 */
107 int /* error */
108 xfs_dir2_leaf_to_node(
109 xfs_da_args_t *args, /* operation arguments */
110 xfs_dabuf_t *lbp) /* leaf buffer */
111 {
112 xfs_inode_t *dp; /* incore directory inode */
113 int error; /* error return value */
114 xfs_dabuf_t *fbp; /* freespace buffer */
115 xfs_dir2_db_t fdb; /* freespace block number */
116 xfs_dir2_free_t *free; /* freespace structure */
117 xfs_dir2_data_off_t *from; /* pointer to freespace entry */
118 int i; /* leaf freespace index */
119 xfs_dir2_leaf_t *leaf; /* leaf structure */
120 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
121 xfs_mount_t *mp; /* filesystem mount point */
122 int n; /* count of live freespc ents */
123 xfs_dir2_data_off_t off; /* freespace entry value */
124 xfs_dir2_data_off_t *to; /* pointer to freespace entry */
125 xfs_trans_t *tp; /* transaction pointer */
126
127 xfs_dir2_trace_args_b("leaf_to_node", args, lbp);
128 dp = args->dp;
129 mp = dp->i_mount;
130 tp = args->trans;
131 /*
132 * Add a freespace block to the directory.
133 */
134 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) {
135 return error;
136 }
137 ASSERT(fdb == XFS_DIR2_FREE_FIRSTDB(mp));
138 /*
139 * Get the buffer for the new freespace block.
140 */
141 if ((error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, fdb), -1, &fbp,
142 XFS_DATA_FORK))) {
143 return error;
144 }
145 ASSERT(fbp != NULL);
146 free = fbp->data;
147 leaf = lbp->data;
148 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
149 /*
150 * Initialize the freespace block header.
151 */
152 INT_SET(free->hdr.magic, ARCH_CONVERT, XFS_DIR2_FREE_MAGIC);
153 free->hdr.firstdb = 0;
154 ASSERT(INT_GET(ltp->bestcount, ARCH_CONVERT) <= (uint)dp->i_d.di_size / mp->m_dirblksize);
155 INT_COPY(free->hdr.nvalid, ltp->bestcount, ARCH_CONVERT);
156 /*
157 * Copy freespace entries from the leaf block to the new block.
158 * Count active entries.
159 */
160 for (i = n = 0, from = XFS_DIR2_LEAF_BESTS_P(ltp), to = free->bests;
161 i < INT_GET(ltp->bestcount, ARCH_CONVERT); i++, from++, to++) {
162 if ((off = INT_GET(*from, ARCH_CONVERT)) != NULLDATAOFF)
163 n++;
164 INT_SET(*to, ARCH_CONVERT, off);
165 }
166 INT_SET(free->hdr.nused, ARCH_CONVERT, n);
167 INT_SET(leaf->hdr.info.magic, ARCH_CONVERT, XFS_DIR2_LEAFN_MAGIC);
168 /*
169 * Log everything.
170 */
171 xfs_dir2_leaf_log_header(tp, lbp);
172 xfs_dir2_free_log_header(tp, fbp);
173 xfs_dir2_free_log_bests(tp, fbp, 0, INT_GET(free->hdr.nvalid, ARCH_CONVERT) - 1);
174 xfs_da_buf_done(fbp);
175 xfs_dir2_leafn_check(dp, lbp);
176 return 0;
177 }
178
179 /*
180 * Add a leaf entry to a leaf block in a node-form directory.
181 * The other work necessary is done from the caller.
182 */
183 static int /* error */
184 xfs_dir2_leafn_add(
185 xfs_dabuf_t *bp, /* leaf buffer */
186 xfs_da_args_t *args, /* operation arguments */
187 int index) /* insertion pt for new entry */
188 {
189 int compact; /* compacting stale leaves */
190 xfs_inode_t *dp; /* incore directory inode */
191 int highstale; /* next stale entry */
192 xfs_dir2_leaf_t *leaf; /* leaf structure */
193 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
194 int lfloghigh; /* high leaf entry logging */
195 int lfloglow; /* low leaf entry logging */
196 int lowstale; /* previous stale entry */
197 xfs_mount_t *mp; /* filesystem mount point */
198 xfs_trans_t *tp; /* transaction pointer */
199
200 xfs_dir2_trace_args_sb("leafn_add", args, index, bp);
201 dp = args->dp;
202 mp = dp->i_mount;
203 tp = args->trans;
204 leaf = bp->data;
205
206 /*
207 * Quick check just to make sure we are not going to index
208 * into other peoples memory
209 */
210 if (index < 0)
211 return XFS_ERROR(EFSCORRUPTED);
212
213 /*
214 * If there are already the maximum number of leaf entries in
215 * the block, if there are no stale entries it won't fit.
216 * Caller will do a split. If there are stale entries we'll do
217 * a compact.
218 */
219
220 if (INT_GET(leaf->hdr.count, ARCH_CONVERT) == XFS_DIR2_MAX_LEAF_ENTS(mp)) {
221 if (!leaf->hdr.stale)
222 return XFS_ERROR(ENOSPC);
223 compact = INT_GET(leaf->hdr.stale, ARCH_CONVERT) > 1;
224 } else
225 compact = 0;
226 ASSERT(index == 0 || INT_GET(leaf->ents[index - 1].hashval, ARCH_CONVERT) <= args->hashval);
227 ASSERT(index == INT_GET(leaf->hdr.count, ARCH_CONVERT) ||
228 INT_GET(leaf->ents[index].hashval, ARCH_CONVERT) >= args->hashval);
229
230 if (args->justcheck)
231 return 0;
232
233 /*
234 * Compact out all but one stale leaf entry. Leaves behind
235 * the entry closest to index.
236 */
237 if (compact) {
238 xfs_dir2_leaf_compact_x1(bp, &index, &lowstale, &highstale,
239 &lfloglow, &lfloghigh);
240 }
241 /*
242 * Set impossible logging indices for this case.
243 */
244 else if (leaf->hdr.stale) {
245 lfloglow = INT_GET(leaf->hdr.count, ARCH_CONVERT);
246 lfloghigh = -1;
247 }
248 /*
249 * No stale entries, just insert a space for the new entry.
250 */
251 if (!leaf->hdr.stale) {
252 lep = &leaf->ents[index];
253 if (index < INT_GET(leaf->hdr.count, ARCH_CONVERT))
254 memmove(lep + 1, lep,
255 (INT_GET(leaf->hdr.count, ARCH_CONVERT) - index) * sizeof(*lep));
256 lfloglow = index;
257 lfloghigh = INT_GET(leaf->hdr.count, ARCH_CONVERT);
258 INT_MOD(leaf->hdr.count, ARCH_CONVERT, +1);
259 }
260 /*
261 * There are stale entries. We'll use one for the new entry.
262 */
263 else {
264 /*
265 * If we didn't do a compact then we need to figure out
266 * which stale entry will be used.
267 */
268 if (compact == 0) {
269 /*
270 * Find first stale entry before our insertion point.
271 */
272 for (lowstale = index - 1;
273 lowstale >= 0 &&
274 INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) !=
275 XFS_DIR2_NULL_DATAPTR;
276 lowstale--)
277 continue;
278 /*
279 * Find next stale entry after insertion point.
280 * Stop looking if the answer would be worse than
281 * lowstale already found.
282 */
283 for (highstale = index;
284 highstale < INT_GET(leaf->hdr.count, ARCH_CONVERT) &&
285 INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) !=
286 XFS_DIR2_NULL_DATAPTR &&
287 (lowstale < 0 ||
288 index - lowstale - 1 >= highstale - index);
289 highstale++)
290 continue;
291 }
292 /*
293 * Using the low stale entry.
294 * Shift entries up toward the stale slot.
295 */
296 if (lowstale >= 0 &&
297 (highstale == INT_GET(leaf->hdr.count, ARCH_CONVERT) ||
298 index - lowstale - 1 < highstale - index)) {
299 ASSERT(INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) ==
300 XFS_DIR2_NULL_DATAPTR);
301 ASSERT(index - lowstale - 1 >= 0);
302 if (index - lowstale - 1 > 0)
303 memmove(&leaf->ents[lowstale],
304 &leaf->ents[lowstale + 1],
305 (index - lowstale - 1) * sizeof(*lep));
306 lep = &leaf->ents[index - 1];
307 lfloglow = MIN(lowstale, lfloglow);
308 lfloghigh = MAX(index - 1, lfloghigh);
309 }
310 /*
311 * Using the high stale entry.
312 * Shift entries down toward the stale slot.
313 */
314 else {
315 ASSERT(INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) ==
316 XFS_DIR2_NULL_DATAPTR);
317 ASSERT(highstale - index >= 0);
318 if (highstale - index > 0)
319 memmove(&leaf->ents[index + 1],
320 &leaf->ents[index],
321 (highstale - index) * sizeof(*lep));
322 lep = &leaf->ents[index];
323 lfloglow = MIN(index, lfloglow);
324 lfloghigh = MAX(highstale, lfloghigh);
325 }
326 INT_MOD(leaf->hdr.stale, ARCH_CONVERT, -1);
327 }
328 /*
329 * Insert the new entry, log everything.
330 */
331 INT_SET(lep->hashval, ARCH_CONVERT, args->hashval);
332 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_DB_OFF_TO_DATAPTR(mp, args->blkno, args->index));
333 xfs_dir2_leaf_log_header(tp, bp);
334 xfs_dir2_leaf_log_ents(tp, bp, lfloglow, lfloghigh);
335 xfs_dir2_leafn_check(dp, bp);
336 return 0;
337 }
338
339 #ifdef DEBUG
340 /*
341 * Check internal consistency of a leafn block.
342 */
343 void
344 xfs_dir2_leafn_check(
345 xfs_inode_t *dp, /* incore directory inode */
346 xfs_dabuf_t *bp) /* leaf buffer */
347 {
348 int i; /* leaf index */
349 xfs_dir2_leaf_t *leaf; /* leaf structure */
350 xfs_mount_t *mp; /* filesystem mount point */
351 int stale; /* count of stale leaves */
352
353 leaf = bp->data;
354 mp = dp->i_mount;
355 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
356 ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) <= XFS_DIR2_MAX_LEAF_ENTS(mp));
357 for (i = stale = 0; i < INT_GET(leaf->hdr.count, ARCH_CONVERT); i++) {
358 if (i + 1 < INT_GET(leaf->hdr.count, ARCH_CONVERT)) {
359 ASSERT(INT_GET(leaf->ents[i].hashval, ARCH_CONVERT) <=
360 INT_GET(leaf->ents[i + 1].hashval, ARCH_CONVERT));
361 }
362 if (INT_GET(leaf->ents[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
363 stale++;
364 }
365 ASSERT(INT_GET(leaf->hdr.stale, ARCH_CONVERT) == stale);
366 }
367 #endif /* DEBUG */
368
369 /*
370 * Return the last hash value in the leaf.
371 * Stale entries are ok.
372 */
373 xfs_dahash_t /* hash value */
374 xfs_dir2_leafn_lasthash(
375 xfs_dabuf_t *bp, /* leaf buffer */
376 int *count) /* count of entries in leaf */
377 {
378 xfs_dir2_leaf_t *leaf; /* leaf structure */
379
380 leaf = bp->data;
381 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
382 if (count)
383 *count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
384 if (!leaf->hdr.count)
385 return 0;
386 return INT_GET(leaf->ents[INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1].hashval, ARCH_CONVERT);
387 }
388
389 /*
390 * Look up a leaf entry in a node-format leaf block.
391 * If this is an addname then the extrablk in state is a freespace block,
392 * otherwise it's a data block.
393 */
394 int
395 xfs_dir2_leafn_lookup_int(
396 xfs_dabuf_t *bp, /* leaf buffer */
397 xfs_da_args_t *args, /* operation arguments */
398 int *indexp, /* out: leaf entry index */
399 xfs_da_state_t *state) /* state to fill in */
400 {
401 xfs_dabuf_t *curbp; /* current data/free buffer */
402 xfs_dir2_db_t curdb; /* current data block number */
403 xfs_dir2_db_t curfdb; /* current free block number */
404 xfs_dir2_data_entry_t *dep; /* data block entry */
405 xfs_inode_t *dp; /* incore directory inode */
406 int error; /* error return value */
407 int fi; /* free entry index */
408 xfs_dir2_free_t *free=NULL; /* free block structure */
409 int index; /* leaf entry index */
410 xfs_dir2_leaf_t *leaf; /* leaf structure */
411 int length=0; /* length of new data entry */
412 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
413 xfs_mount_t *mp; /* filesystem mount point */
414 xfs_dir2_db_t newdb; /* new data block number */
415 xfs_dir2_db_t newfdb; /* new free block number */
416 xfs_trans_t *tp; /* transaction pointer */
417
418 dp = args->dp;
419 tp = args->trans;
420 mp = dp->i_mount;
421 leaf = bp->data;
422 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
423 #ifdef __KERNEL__
424 ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) > 0);
425 #endif
426 xfs_dir2_leafn_check(dp, bp);
427 /*
428 * Look up the hash value in the leaf entries.
429 */
430 index = xfs_dir2_leaf_search_hash(args, bp);
431 /*
432 * Do we have a buffer coming in?
433 */
434 if (state->extravalid)
435 curbp = state->extrablk.bp;
436 else
437 curbp = NULL;
438 /*
439 * For addname, it's a free block buffer, get the block number.
440 */
441 if (args->addname) {
442 curfdb = curbp ? state->extrablk.blkno : -1;
443 curdb = -1;
444 length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
445 if ((free = (curbp ? curbp->data : NULL)))
446 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
447 }
448 /*
449 * For others, it's a data block buffer, get the block number.
450 */
451 else {
452 curfdb = -1;
453 curdb = curbp ? state->extrablk.blkno : -1;
454 }
455 /*
456 * Loop over leaf entries with the right hash value.
457 */
458 for (lep = &leaf->ents[index];
459 index < INT_GET(leaf->hdr.count, ARCH_CONVERT) && INT_GET(lep->hashval, ARCH_CONVERT) == args->hashval;
460 lep++, index++) {
461 /*
462 * Skip stale leaf entries.
463 */
464 if (INT_GET(lep->address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
465 continue;
466 /*
467 * Pull the data block number from the entry.
468 */
469 newdb = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
470 /*
471 * For addname, we're looking for a place to put the new entry.
472 * We want to use a data block with an entry of equal
473 * hash value to ours if there is one with room.
474 */
475 if (args->addname) {
476 /*
477 * If this block isn't the data block we already have
478 * in hand, take a look at it.
479 */
480 if (newdb != curdb) {
481 curdb = newdb;
482 /*
483 * Convert the data block to the free block
484 * holding its freespace information.
485 */
486 newfdb = XFS_DIR2_DB_TO_FDB(mp, newdb);
487 /*
488 * If it's not the one we have in hand,
489 * read it in.
490 */
491 if (newfdb != curfdb) {
492 /*
493 * If we had one before, drop it.
494 */
495 if (curbp)
496 xfs_da_brelse(tp, curbp);
497 /*
498 * Read the free block.
499 */
500 if ((error = xfs_da_read_buf(tp, dp,
501 XFS_DIR2_DB_TO_DA(mp,
502 newfdb),
503 -1, &curbp,
504 XFS_DATA_FORK))) {
505 return error;
506 }
507 curfdb = newfdb;
508 free = curbp->data;
509 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) ==
510 XFS_DIR2_FREE_MAGIC);
511 ASSERT((INT_GET(free->hdr.firstdb, ARCH_CONVERT) %
512 XFS_DIR2_MAX_FREE_BESTS(mp)) ==
513 0);
514 ASSERT(INT_GET(free->hdr.firstdb, ARCH_CONVERT) <= curdb);
515 ASSERT(curdb <
516 INT_GET(free->hdr.firstdb, ARCH_CONVERT) +
517 INT_GET(free->hdr.nvalid, ARCH_CONVERT));
518 }
519 /*
520 * Get the index for our entry.
521 */
522 fi = XFS_DIR2_DB_TO_FDINDEX(mp, curdb);
523 /*
524 * If it has room, return it.
525 */
526 if (unlikely(INT_GET(free->bests[fi], ARCH_CONVERT) == NULLDATAOFF)) {
527 XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
528 XFS_ERRLEVEL_LOW, mp);
529 return XFS_ERROR(EFSCORRUPTED);
530 }
531 if (INT_GET(free->bests[fi], ARCH_CONVERT) >= length) {
532 *indexp = index;
533 state->extravalid = 1;
534 state->extrablk.bp = curbp;
535 state->extrablk.blkno = curfdb;
536 state->extrablk.index = fi;
537 state->extrablk.magic =
538 XFS_DIR2_FREE_MAGIC;
539 ASSERT(args->oknoent);
540 return XFS_ERROR(ENOENT);
541 }
542 }
543 }
544 /*
545 * Not adding a new entry, so we really want to find
546 * the name given to us.
547 */
548 else {
549 /*
550 * If it's a different data block, go get it.
551 */
552 if (newdb != curdb) {
553 /*
554 * If we had a block before, drop it.
555 */
556 if (curbp)
557 xfs_da_brelse(tp, curbp);
558 /*
559 * Read the data block.
560 */
561 if ((error =
562 xfs_da_read_buf(tp, dp,
563 XFS_DIR2_DB_TO_DA(mp, newdb), -1,
564 &curbp, XFS_DATA_FORK))) {
565 return error;
566 }
567 xfs_dir2_data_check(dp, curbp);
568 curdb = newdb;
569 }
570 /*
571 * Point to the data entry.
572 */
573 dep = (xfs_dir2_data_entry_t *)
574 ((char *)curbp->data +
575 XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT)));
576 /*
577 * Compare the entry, return it if it matches.
578 */
579 if (dep->namelen == args->namelen &&
580 dep->name[0] == args->name[0] &&
581 memcmp(dep->name, args->name, args->namelen) == 0) {
582 args->inumber = INT_GET(dep->inumber, ARCH_CONVERT);
583 *indexp = index;
584 state->extravalid = 1;
585 state->extrablk.bp = curbp;
586 state->extrablk.blkno = curdb;
587 state->extrablk.index =
588 (int)((char *)dep -
589 (char *)curbp->data);
590 state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
591 return XFS_ERROR(EEXIST);
592 }
593 }
594 }
595 /*
596 * Didn't find a match.
597 * If we are holding a buffer, give it back in case our caller
598 * finds it useful.
599 */
600 if ((state->extravalid = (curbp != NULL))) {
601 state->extrablk.bp = curbp;
602 state->extrablk.index = -1;
603 /*
604 * For addname, giving back a free block.
605 */
606 if (args->addname) {
607 state->extrablk.blkno = curfdb;
608 state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
609 }
610 /*
611 * For other callers, giving back a data block.
612 */
613 else {
614 state->extrablk.blkno = curdb;
615 state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
616 }
617 }
618 /*
619 * Return the final index, that will be the insertion point.
620 */
621 *indexp = index;
622 ASSERT(index == INT_GET(leaf->hdr.count, ARCH_CONVERT) || args->oknoent);
623 return XFS_ERROR(ENOENT);
624 }
625
626 /*
627 * Move count leaf entries from source to destination leaf.
628 * Log entries and headers. Stale entries are preserved.
629 */
630 static void
631 xfs_dir2_leafn_moveents(
632 xfs_da_args_t *args, /* operation arguments */
633 xfs_dabuf_t *bp_s, /* source leaf buffer */
634 int start_s, /* source leaf index */
635 xfs_dabuf_t *bp_d, /* destination leaf buffer */
636 int start_d, /* destination leaf index */
637 int count) /* count of leaves to copy */
638 {
639 xfs_dir2_leaf_t *leaf_d; /* destination leaf structure */
640 xfs_dir2_leaf_t *leaf_s; /* source leaf structure */
641 int stale; /* count stale leaves copied */
642 xfs_trans_t *tp; /* transaction pointer */
643
644 xfs_dir2_trace_args_bibii("leafn_moveents", args, bp_s, start_s, bp_d,
645 start_d, count);
646 /*
647 * Silently return if nothing to do.
648 */
649 if (count == 0) {
650 return;
651 }
652 tp = args->trans;
653 leaf_s = bp_s->data;
654 leaf_d = bp_d->data;
655 /*
656 * If the destination index is not the end of the current
657 * destination leaf entries, open up a hole in the destination
658 * to hold the new entries.
659 */
660 if (start_d < INT_GET(leaf_d->hdr.count, ARCH_CONVERT)) {
661 memmove(&leaf_d->ents[start_d + count], &leaf_d->ents[start_d],
662 (INT_GET(leaf_d->hdr.count, ARCH_CONVERT) - start_d) *
663 sizeof(xfs_dir2_leaf_entry_t));
664 xfs_dir2_leaf_log_ents(tp, bp_d, start_d + count,
665 count + INT_GET(leaf_d->hdr.count, ARCH_CONVERT) - 1);
666 }
667 /*
668 * If the source has stale leaves, count the ones in the copy range
669 * so we can update the header correctly.
670 */
671 if (leaf_s->hdr.stale) {
672 int i; /* temp leaf index */
673
674 for (i = start_s, stale = 0; i < start_s + count; i++) {
675 if (INT_GET(leaf_s->ents[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
676 stale++;
677 }
678 } else
679 stale = 0;
680 /*
681 * Copy the leaf entries from source to destination.
682 */
683 memcpy(&leaf_d->ents[start_d], &leaf_s->ents[start_s],
684 count * sizeof(xfs_dir2_leaf_entry_t));
685 xfs_dir2_leaf_log_ents(tp, bp_d, start_d, start_d + count - 1);
686 /*
687 * If there are source entries after the ones we copied,
688 * delete the ones we copied by sliding the next ones down.
689 */
690 if (start_s + count < INT_GET(leaf_s->hdr.count, ARCH_CONVERT)) {
691 memmove(&leaf_s->ents[start_s], &leaf_s->ents[start_s + count],
692 count * sizeof(xfs_dir2_leaf_entry_t));
693 xfs_dir2_leaf_log_ents(tp, bp_s, start_s, start_s + count - 1);
694 }
695 /*
696 * Update the headers and log them.
697 */
698 INT_MOD(leaf_s->hdr.count, ARCH_CONVERT, -(count));
699 INT_MOD(leaf_s->hdr.stale, ARCH_CONVERT, -(stale));
700 INT_MOD(leaf_d->hdr.count, ARCH_CONVERT, count);
701 INT_MOD(leaf_d->hdr.stale, ARCH_CONVERT, stale);
702 xfs_dir2_leaf_log_header(tp, bp_s);
703 xfs_dir2_leaf_log_header(tp, bp_d);
704 xfs_dir2_leafn_check(args->dp, bp_s);
705 xfs_dir2_leafn_check(args->dp, bp_d);
706 }
707
708 /*
709 * Determine the sort order of two leaf blocks.
710 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
711 */
712 int /* sort order */
713 xfs_dir2_leafn_order(
714 xfs_dabuf_t *leaf1_bp, /* leaf1 buffer */
715 xfs_dabuf_t *leaf2_bp) /* leaf2 buffer */
716 {
717 xfs_dir2_leaf_t *leaf1; /* leaf1 structure */
718 xfs_dir2_leaf_t *leaf2; /* leaf2 structure */
719
720 leaf1 = leaf1_bp->data;
721 leaf2 = leaf2_bp->data;
722 ASSERT(INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
723 ASSERT(INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
724 if (INT_GET(leaf1->hdr.count, ARCH_CONVERT) > 0 &&
725 INT_GET(leaf2->hdr.count, ARCH_CONVERT) > 0 &&
726 (INT_GET(leaf2->ents[0].hashval, ARCH_CONVERT) < INT_GET(leaf1->ents[0].hashval, ARCH_CONVERT) ||
727 INT_GET(leaf2->ents[INT_GET(leaf2->hdr.count, ARCH_CONVERT) - 1].hashval, ARCH_CONVERT) <
728 INT_GET(leaf1->ents[INT_GET(leaf1->hdr.count, ARCH_CONVERT) - 1].hashval, ARCH_CONVERT)))
729 return 1;
730 return 0;
731 }
732
733 /*
734 * Rebalance leaf entries between two leaf blocks.
735 * This is actually only called when the second block is new,
736 * though the code deals with the general case.
737 * A new entry will be inserted in one of the blocks, and that
738 * entry is taken into account when balancing.
739 */
740 static void
741 xfs_dir2_leafn_rebalance(
742 xfs_da_state_t *state, /* btree cursor */
743 xfs_da_state_blk_t *blk1, /* first btree block */
744 xfs_da_state_blk_t *blk2) /* second btree block */
745 {
746 xfs_da_args_t *args; /* operation arguments */
747 int count; /* count (& direction) leaves */
748 int isleft; /* new goes in left leaf */
749 xfs_dir2_leaf_t *leaf1; /* first leaf structure */
750 xfs_dir2_leaf_t *leaf2; /* second leaf structure */
751 int mid; /* midpoint leaf index */
752 #ifdef DEBUG
753 int oldstale; /* old count of stale leaves */
754 #endif
755 int oldsum; /* old total leaf count */
756 int swap; /* swapped leaf blocks */
757
758 args = state->args;
759 /*
760 * If the block order is wrong, swap the arguments.
761 */
762 if ((swap = xfs_dir2_leafn_order(blk1->bp, blk2->bp))) {
763 xfs_da_state_blk_t *tmp; /* temp for block swap */
764
765 tmp = blk1;
766 blk1 = blk2;
767 blk2 = tmp;
768 }
769 leaf1 = blk1->bp->data;
770 leaf2 = blk2->bp->data;
771 oldsum = INT_GET(leaf1->hdr.count, ARCH_CONVERT) + INT_GET(leaf2->hdr.count, ARCH_CONVERT);
772 #ifdef DEBUG
773 oldstale = INT_GET(leaf1->hdr.stale, ARCH_CONVERT) + INT_GET(leaf2->hdr.stale, ARCH_CONVERT);
774 #endif
775 mid = oldsum >> 1;
776 /*
777 * If the old leaf count was odd then the new one will be even,
778 * so we need to divide the new count evenly.
779 */
780 if (oldsum & 1) {
781 xfs_dahash_t midhash; /* middle entry hash value */
782
783 if (mid >= INT_GET(leaf1->hdr.count, ARCH_CONVERT))
784 midhash = INT_GET(leaf2->ents[mid - INT_GET(leaf1->hdr.count, ARCH_CONVERT)].hashval, ARCH_CONVERT);
785 else
786 midhash = INT_GET(leaf1->ents[mid].hashval, ARCH_CONVERT);
787 isleft = args->hashval <= midhash;
788 }
789 /*
790 * If the old count is even then the new count is odd, so there's
791 * no preferred side for the new entry.
792 * Pick the left one.
793 */
794 else
795 isleft = 1;
796 /*
797 * Calculate moved entry count. Positive means left-to-right,
798 * negative means right-to-left. Then move the entries.
799 */
800 count = INT_GET(leaf1->hdr.count, ARCH_CONVERT) - mid + (isleft == 0);
801 if (count > 0)
802 xfs_dir2_leafn_moveents(args, blk1->bp,
803 INT_GET(leaf1->hdr.count, ARCH_CONVERT) - count, blk2->bp, 0, count);
804 else if (count < 0)
805 xfs_dir2_leafn_moveents(args, blk2->bp, 0, blk1->bp,
806 INT_GET(leaf1->hdr.count, ARCH_CONVERT), count);
807 ASSERT(INT_GET(leaf1->hdr.count, ARCH_CONVERT) + INT_GET(leaf2->hdr.count, ARCH_CONVERT) == oldsum);
808 ASSERT(INT_GET(leaf1->hdr.stale, ARCH_CONVERT) + INT_GET(leaf2->hdr.stale, ARCH_CONVERT) == oldstale);
809 /*
810 * Mark whether we're inserting into the old or new leaf.
811 */
812 if (INT_GET(leaf1->hdr.count, ARCH_CONVERT) < INT_GET(leaf2->hdr.count, ARCH_CONVERT))
813 state->inleaf = swap;
814 else if (INT_GET(leaf1->hdr.count, ARCH_CONVERT) > INT_GET(leaf2->hdr.count, ARCH_CONVERT))
815 state->inleaf = !swap;
816 else
817 state->inleaf =
818 swap ^ (blk1->index <= INT_GET(leaf1->hdr.count, ARCH_CONVERT));
819 /*
820 * Adjust the expected index for insertion.
821 */
822 if (!state->inleaf)
823 blk2->index = blk1->index - INT_GET(leaf1->hdr.count, ARCH_CONVERT);
824
825 /*
826 * Finally sanity check just to make sure we are not returning a negative index
827 */
828 if(blk2->index < 0) {
829 state->inleaf = 1;
830 blk2->index = 0;
831 cmn_err(CE_ALERT,
832 "xfs_dir2_leafn_rebalance: picked the wrong leaf? reverting orignal leaf: "
833 "blk1->index %d\n",
834 blk1->index);
835 }
836 }
837
838 /*
839 * Remove an entry from a node directory.
840 * This removes the leaf entry and the data entry,
841 * and updates the free block if necessary.
842 */
843 static int /* error */
844 xfs_dir2_leafn_remove(
845 xfs_da_args_t *args, /* operation arguments */
846 xfs_dabuf_t *bp, /* leaf buffer */
847 int index, /* leaf entry index */
848 xfs_da_state_blk_t *dblk, /* data block */
849 int *rval) /* resulting block needs join */
850 {
851 xfs_dir2_data_t *data; /* data block structure */
852 xfs_dir2_db_t db; /* data block number */
853 xfs_dabuf_t *dbp; /* data block buffer */
854 xfs_dir2_data_entry_t *dep; /* data block entry */
855 xfs_inode_t *dp; /* incore directory inode */
856 xfs_dir2_leaf_t *leaf; /* leaf structure */
857 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
858 int longest; /* longest data free entry */
859 int off; /* data block entry offset */
860 xfs_mount_t *mp; /* filesystem mount point */
861 int needlog; /* need to log data header */
862 int needscan; /* need to rescan data frees */
863 xfs_trans_t *tp; /* transaction pointer */
864
865 xfs_dir2_trace_args_sb("leafn_remove", args, index, bp);
866 dp = args->dp;
867 tp = args->trans;
868 mp = dp->i_mount;
869 leaf = bp->data;
870 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
871 /*
872 * Point to the entry we're removing.
873 */
874 lep = &leaf->ents[index];
875 /*
876 * Extract the data block and offset from the entry.
877 */
878 db = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
879 ASSERT(dblk->blkno == db);
880 off = XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT));
881 ASSERT(dblk->index == off);
882 /*
883 * Kill the leaf entry by marking it stale.
884 * Log the leaf block changes.
885 */
886 INT_MOD(leaf->hdr.stale, ARCH_CONVERT, +1);
887 xfs_dir2_leaf_log_header(tp, bp);
888 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_NULL_DATAPTR);
889 xfs_dir2_leaf_log_ents(tp, bp, index, index);
890 /*
891 * Make the data entry free. Keep track of the longest freespace
892 * in the data block in case it changes.
893 */
894 dbp = dblk->bp;
895 data = dbp->data;
896 dep = (xfs_dir2_data_entry_t *)((char *)data + off);
897 longest = INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT);
898 needlog = needscan = 0;
899 xfs_dir2_data_make_free(tp, dbp, off,
900 XFS_DIR2_DATA_ENTSIZE(dep->namelen), &needlog, &needscan);
901 /*
902 * Rescan the data block freespaces for bestfree.
903 * Log the data block header if needed.
904 */
905 if (needscan)
906 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
907 if (needlog)
908 xfs_dir2_data_log_header(tp, dbp);
909 xfs_dir2_data_check(dp, dbp);
910 /*
911 * If the longest data block freespace changes, need to update
912 * the corresponding freeblock entry.
913 */
914 if (longest < INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT)) {
915 int error; /* error return value */
916 xfs_dabuf_t *fbp; /* freeblock buffer */
917 xfs_dir2_db_t fdb; /* freeblock block number */
918 int findex; /* index in freeblock entries */
919 xfs_dir2_free_t *free; /* freeblock structure */
920 int logfree; /* need to log free entry */
921
922 /*
923 * Convert the data block number to a free block,
924 * read in the free block.
925 */
926 fdb = XFS_DIR2_DB_TO_FDB(mp, db);
927 if ((error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, fdb),
928 -1, &fbp, XFS_DATA_FORK))) {
929 return error;
930 }
931 free = fbp->data;
932 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
933 ASSERT(INT_GET(free->hdr.firstdb, ARCH_CONVERT) ==
934 XFS_DIR2_MAX_FREE_BESTS(mp) *
935 (fdb - XFS_DIR2_FREE_FIRSTDB(mp)));
936 /*
937 * Calculate which entry we need to fix.
938 */
939 findex = XFS_DIR2_DB_TO_FDINDEX(mp, db);
940 longest = INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT);
941 /*
942 * If the data block is now empty we can get rid of it
943 * (usually).
944 */
945 if (longest == mp->m_dirblksize - (uint)sizeof(data->hdr)) {
946 /*
947 * Try to punch out the data block.
948 */
949 error = xfs_dir2_shrink_inode(args, db, dbp);
950 if (error == 0) {
951 dblk->bp = NULL;
952 data = NULL;
953 }
954 /*
955 * We can get ENOSPC if there's no space reservation.
956 * In this case just drop the buffer and some one else
957 * will eventually get rid of the empty block.
958 */
959 else if (error == ENOSPC && args->total == 0)
960 xfs_da_buf_done(dbp);
961 else
962 return error;
963 }
964 /*
965 * If we got rid of the data block, we can eliminate that entry
966 * in the free block.
967 */
968 if (data == NULL) {
969 /*
970 * One less used entry in the free table.
971 */
972 INT_MOD(free->hdr.nused, ARCH_CONVERT, -1);
973 xfs_dir2_free_log_header(tp, fbp);
974 /*
975 * If this was the last entry in the table, we can
976 * trim the table size back. There might be other
977 * entries at the end referring to non-existent
978 * data blocks, get those too.
979 */
980 if (findex == INT_GET(free->hdr.nvalid, ARCH_CONVERT) - 1) {
981 int i; /* free entry index */
982
983 for (i = findex - 1;
984 i >= 0 && INT_GET(free->bests[i], ARCH_CONVERT) == NULLDATAOFF;
985 i--)
986 continue;
987 INT_SET(free->hdr.nvalid, ARCH_CONVERT, i + 1);
988 logfree = 0;
989 }
990 /*
991 * Not the last entry, just punch it out.
992 */
993 else {
994 INT_SET(free->bests[findex], ARCH_CONVERT, NULLDATAOFF);
995 logfree = 1;
996 }
997 /*
998 * If there are no useful entries left in the block,
999 * get rid of the block if we can.
1000 */
1001 if (!free->hdr.nused) {
1002 error = xfs_dir2_shrink_inode(args, fdb, fbp);
1003 if (error == 0) {
1004 fbp = NULL;
1005 logfree = 0;
1006 } else if (error != ENOSPC || args->total != 0)
1007 return error;
1008 /*
1009 * It's possible to get ENOSPC if there is no
1010 * space reservation. In this case some one
1011 * else will eventually get rid of this block.
1012 */
1013 }
1014 }
1015 /*
1016 * Data block is not empty, just set the free entry to
1017 * the new value.
1018 */
1019 else {
1020 INT_SET(free->bests[findex], ARCH_CONVERT, longest);
1021 logfree = 1;
1022 }
1023 /*
1024 * Log the free entry that changed, unless we got rid of it.
1025 */
1026 if (logfree)
1027 xfs_dir2_free_log_bests(tp, fbp, findex, findex);
1028 /*
1029 * Drop the buffer if we still have it.
1030 */
1031 if (fbp)
1032 xfs_da_buf_done(fbp);
1033 }
1034 xfs_dir2_leafn_check(dp, bp);
1035 /*
1036 * Return indication of whether this leaf block is emtpy enough
1037 * to justify trying to join it with a neighbor.
1038 */
1039 *rval =
1040 ((uint)sizeof(leaf->hdr) +
1041 (uint)sizeof(leaf->ents[0]) *
1042 (INT_GET(leaf->hdr.count, ARCH_CONVERT) - INT_GET(leaf->hdr.stale, ARCH_CONVERT))) <
1043 mp->m_dir_magicpct;
1044 return 0;
1045 }
1046
1047 /*
1048 * Split the leaf entries in the old block into old and new blocks.
1049 */
1050 int /* error */
1051 xfs_dir2_leafn_split(
1052 xfs_da_state_t *state, /* btree cursor */
1053 xfs_da_state_blk_t *oldblk, /* original block */
1054 xfs_da_state_blk_t *newblk) /* newly created block */
1055 {
1056 xfs_da_args_t *args; /* operation arguments */
1057 xfs_dablk_t blkno; /* new leaf block number */
1058 int error; /* error return value */
1059 xfs_mount_t *mp; /* filesystem mount point */
1060
1061 /*
1062 * Allocate space for a new leaf node.
1063 */
1064 args = state->args;
1065 mp = args->dp->i_mount;
1066 ASSERT(args != NULL);
1067 ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC);
1068 error = xfs_da_grow_inode(args, &blkno);
1069 if (error) {
1070 return error;
1071 }
1072 /*
1073 * Initialize the new leaf block.
1074 */
1075 error = xfs_dir2_leaf_init(args, XFS_DIR2_DA_TO_DB(mp, blkno),
1076 &newblk->bp, XFS_DIR2_LEAFN_MAGIC);
1077 if (error) {
1078 return error;
1079 }
1080 newblk->blkno = blkno;
1081 newblk->magic = XFS_DIR2_LEAFN_MAGIC;
1082 /*
1083 * Rebalance the entries across the two leaves, link the new
1084 * block into the leaves.
1085 */
1086 xfs_dir2_leafn_rebalance(state, oldblk, newblk);
1087 error = xfs_da_blk_link(state, oldblk, newblk);
1088 if (error) {
1089 return error;
1090 }
1091 /*
1092 * Insert the new entry in the correct block.
1093 */
1094 if (state->inleaf)
1095 error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index);
1096 else
1097 error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index);
1098 /*
1099 * Update last hashval in each block since we added the name.
1100 */
1101 oldblk->hashval = xfs_dir2_leafn_lasthash(oldblk->bp, NULL);
1102 newblk->hashval = xfs_dir2_leafn_lasthash(newblk->bp, NULL);
1103 xfs_dir2_leafn_check(args->dp, oldblk->bp);
1104 xfs_dir2_leafn_check(args->dp, newblk->bp);
1105 return error;
1106 }
1107
1108 /*
1109 * Check a leaf block and its neighbors to see if the block should be
1110 * collapsed into one or the other neighbor. Always keep the block
1111 * with the smaller block number.
1112 * If the current block is over 50% full, don't try to join it, return 0.
1113 * If the block is empty, fill in the state structure and return 2.
1114 * If it can be collapsed, fill in the state structure and return 1.
1115 * If nothing can be done, return 0.
1116 */
1117 int /* error */
1118 xfs_dir2_leafn_toosmall(
1119 xfs_da_state_t *state, /* btree cursor */
1120 int *action) /* resulting action to take */
1121 {
1122 xfs_da_state_blk_t *blk; /* leaf block */
1123 xfs_dablk_t blkno; /* leaf block number */
1124 xfs_dabuf_t *bp; /* leaf buffer */
1125 int bytes; /* bytes in use */
1126 int count; /* leaf live entry count */
1127 int error; /* error return value */
1128 int forward; /* sibling block direction */
1129 int i; /* sibling counter */
1130 xfs_da_blkinfo_t *info; /* leaf block header */
1131 xfs_dir2_leaf_t *leaf; /* leaf structure */
1132 int rval; /* result from path_shift */
1133
1134 /*
1135 * Check for the degenerate case of the block being over 50% full.
1136 * If so, it's not worth even looking to see if we might be able
1137 * to coalesce with a sibling.
1138 */
1139 blk = &state->path.blk[state->path.active - 1];
1140 info = blk->bp->data;
1141 ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1142 leaf = (xfs_dir2_leaf_t *)info;
1143 count = INT_GET(leaf->hdr.count, ARCH_CONVERT) - INT_GET(leaf->hdr.stale, ARCH_CONVERT);
1144 bytes = (uint)sizeof(leaf->hdr) + count * (uint)sizeof(leaf->ents[0]);
1145 if (bytes > (state->blocksize >> 1)) {
1146 /*
1147 * Blk over 50%, don't try to join.
1148 */
1149 *action = 0;
1150 return 0;
1151 }
1152 /*
1153 * Check for the degenerate case of the block being empty.
1154 * If the block is empty, we'll simply delete it, no need to
1155 * coalesce it with a sibling block. We choose (arbitrarily)
1156 * to merge with the forward block unless it is NULL.
1157 */
1158 if (count == 0) {
1159 /*
1160 * Make altpath point to the block we want to keep and
1161 * path point to the block we want to drop (this one).
1162 */
1163 forward = info->forw;
1164 memcpy(&state->altpath, &state->path, sizeof(state->path));
1165 error = xfs_da_path_shift(state, &state->altpath, forward, 0,
1166 &rval);
1167 if (error)
1168 return error;
1169 *action = rval ? 2 : 0;
1170 return 0;
1171 }
1172 /*
1173 * Examine each sibling block to see if we can coalesce with
1174 * at least 25% free space to spare. We need to figure out
1175 * whether to merge with the forward or the backward block.
1176 * We prefer coalescing with the lower numbered sibling so as
1177 * to shrink a directory over time.
1178 */
1179 forward = INT_GET(info->forw, ARCH_CONVERT) < INT_GET(info->back, ARCH_CONVERT);
1180 for (i = 0, bp = NULL; i < 2; forward = !forward, i++) {
1181 blkno = forward ?INT_GET( info->forw, ARCH_CONVERT) : INT_GET(info->back, ARCH_CONVERT);
1182 if (blkno == 0)
1183 continue;
1184 /*
1185 * Read the sibling leaf block.
1186 */
1187 if ((error =
1188 xfs_da_read_buf(state->args->trans, state->args->dp, blkno,
1189 -1, &bp, XFS_DATA_FORK))) {
1190 return error;
1191 }
1192 ASSERT(bp != NULL);
1193 /*
1194 * Count bytes in the two blocks combined.
1195 */
1196 leaf = (xfs_dir2_leaf_t *)info;
1197 count = INT_GET(leaf->hdr.count, ARCH_CONVERT) - INT_GET(leaf->hdr.stale, ARCH_CONVERT);
1198 bytes = state->blocksize - (state->blocksize >> 2);
1199 leaf = bp->data;
1200 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1201 count += INT_GET(leaf->hdr.count, ARCH_CONVERT) - INT_GET(leaf->hdr.stale, ARCH_CONVERT);
1202 bytes -= count * (uint)sizeof(leaf->ents[0]);
1203 /*
1204 * Fits with at least 25% to spare.
1205 */
1206 if (bytes >= 0)
1207 break;
1208 xfs_da_brelse(state->args->trans, bp);
1209 }
1210 /*
1211 * Didn't like either block, give up.
1212 */
1213 if (i >= 2) {
1214 *action = 0;
1215 return 0;
1216 }
1217 /*
1218 * Done with the sibling leaf block here, drop the dabuf
1219 * so path_shift can get it.
1220 */
1221 xfs_da_buf_done(bp);
1222 /*
1223 * Make altpath point to the block we want to keep (the lower
1224 * numbered block) and path point to the block we want to drop.
1225 */
1226 memcpy(&state->altpath, &state->path, sizeof(state->path));
1227 if (blkno < blk->blkno)
1228 error = xfs_da_path_shift(state, &state->altpath, forward, 0,
1229 &rval);
1230 else
1231 error = xfs_da_path_shift(state, &state->path, forward, 0,
1232 &rval);
1233 if (error) {
1234 return error;
1235 }
1236 *action = rval ? 0 : 1;
1237 return 0;
1238 }
1239
1240 /*
1241 * Move all the leaf entries from drop_blk to save_blk.
1242 * This is done as part of a join operation.
1243 */
1244 void
1245 xfs_dir2_leafn_unbalance(
1246 xfs_da_state_t *state, /* cursor */
1247 xfs_da_state_blk_t *drop_blk, /* dead block */
1248 xfs_da_state_blk_t *save_blk) /* surviving block */
1249 {
1250 xfs_da_args_t *args; /* operation arguments */
1251 xfs_dir2_leaf_t *drop_leaf; /* dead leaf structure */
1252 xfs_dir2_leaf_t *save_leaf; /* surviving leaf structure */
1253
1254 args = state->args;
1255 ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1256 ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1257 drop_leaf = drop_blk->bp->data;
1258 save_leaf = save_blk->bp->data;
1259 ASSERT(INT_GET(drop_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1260 ASSERT(INT_GET(save_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1261 /*
1262 * If there are any stale leaf entries, take this opportunity
1263 * to purge them.
1264 */
1265 if (INT_GET(drop_leaf->hdr.stale, ARCH_CONVERT))
1266 xfs_dir2_leaf_compact(args, drop_blk->bp);
1267 if (INT_GET(save_leaf->hdr.stale, ARCH_CONVERT))
1268 xfs_dir2_leaf_compact(args, save_blk->bp);
1269 /*
1270 * Move the entries from drop to the appropriate end of save.
1271 */
1272 drop_blk->hashval = INT_GET(drop_leaf->ents[INT_GET(drop_leaf->hdr.count, ARCH_CONVERT) - 1].hashval, ARCH_CONVERT);
1273 if (xfs_dir2_leafn_order(save_blk->bp, drop_blk->bp))
1274 xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp, 0,
1275 INT_GET(drop_leaf->hdr.count, ARCH_CONVERT));
1276 else
1277 xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp,
1278 INT_GET(save_leaf->hdr.count, ARCH_CONVERT), INT_GET(drop_leaf->hdr.count, ARCH_CONVERT));
1279 save_blk->hashval = INT_GET(save_leaf->ents[INT_GET(save_leaf->hdr.count, ARCH_CONVERT) - 1].hashval, ARCH_CONVERT);
1280 xfs_dir2_leafn_check(args->dp, save_blk->bp);
1281 }
1282
1283 /*
1284 * Top-level node form directory addname routine.
1285 */
1286 int /* error */
1287 xfs_dir2_node_addname(
1288 xfs_da_args_t *args) /* operation arguments */
1289 {
1290 xfs_da_state_blk_t *blk; /* leaf block for insert */
1291 int error; /* error return value */
1292 int rval; /* sub-return value */
1293 xfs_da_state_t *state; /* btree cursor */
1294
1295 xfs_dir2_trace_args("node_addname", args);
1296 /*
1297 * Allocate and initialize the state (btree cursor).
1298 */
1299 state = xfs_da_state_alloc();
1300 state->args = args;
1301 state->mp = args->dp->i_mount;
1302 state->blocksize = state->mp->m_dirblksize;
1303 state->node_ents = state->mp->m_dir_node_ents;
1304 /*
1305 * Look up the name. We're not supposed to find it, but
1306 * this gives us the insertion point.
1307 */
1308 error = xfs_da_node_lookup_int(state, &rval);
1309 if (error)
1310 rval = error;
1311 if (rval != ENOENT) {
1312 goto done;
1313 }
1314 /*
1315 * Add the data entry to a data block.
1316 * Extravalid is set to a freeblock found by lookup.
1317 */
1318 rval = xfs_dir2_node_addname_int(args,
1319 state->extravalid ? &state->extrablk : NULL);
1320 if (rval) {
1321 goto done;
1322 }
1323 blk = &state->path.blk[state->path.active - 1];
1324 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1325 /*
1326 * Add the new leaf entry.
1327 */
1328 rval = xfs_dir2_leafn_add(blk->bp, args, blk->index);
1329 if (rval == 0) {
1330 /*
1331 * It worked, fix the hash values up the btree.
1332 */
1333 if (!args->justcheck)
1334 xfs_da_fixhashpath(state, &state->path);
1335 } else {
1336 /*
1337 * It didn't work, we need to split the leaf block.
1338 */
1339 if (args->total == 0) {
1340 ASSERT(rval == ENOSPC);
1341 goto done;
1342 }
1343 /*
1344 * Split the leaf block and insert the new entry.
1345 */
1346 rval = xfs_da_split(state);
1347 }
1348 done:
1349 xfs_da_state_free(state);
1350 return rval;
1351 }
1352
1353 /*
1354 * Add the data entry for a node-format directory name addition.
1355 * The leaf entry is added in xfs_dir2_leafn_add.
1356 * We may enter with a freespace block that the lookup found.
1357 */
1358 static int /* error */
1359 xfs_dir2_node_addname_int(
1360 xfs_da_args_t *args, /* operation arguments */
1361 xfs_da_state_blk_t *fblk) /* optional freespace block */
1362 {
1363 xfs_dir2_data_t *data; /* data block structure */
1364 xfs_dir2_db_t dbno; /* data block number */
1365 xfs_dabuf_t *dbp; /* data block buffer */
1366 xfs_dir2_data_entry_t *dep; /* data entry pointer */
1367 xfs_inode_t *dp; /* incore directory inode */
1368 xfs_dir2_data_unused_t *dup; /* data unused entry pointer */
1369 int error; /* error return value */
1370 xfs_dir2_db_t fbno; /* freespace block number */
1371 xfs_dabuf_t *fbp; /* freespace buffer */
1372 int findex; /* freespace entry index */
1373 xfs_dir2_free_t *free=NULL; /* freespace block structure */
1374 xfs_dir2_db_t ifbno; /* initial freespace block no */
1375 xfs_dir2_db_t lastfbno=0; /* highest freespace block no */
1376 int length; /* length of the new entry */
1377 int logfree; /* need to log free entry */
1378 xfs_mount_t *mp; /* filesystem mount point */
1379 int needlog; /* need to log data header */
1380 int needscan; /* need to rescan data frees */
1381 xfs_dir2_data_off_t *tagp; /* data entry tag pointer */
1382 xfs_trans_t *tp; /* transaction pointer */
1383
1384 dp = args->dp;
1385 mp = dp->i_mount;
1386 tp = args->trans;
1387 length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
1388 /*
1389 * If we came in with a freespace block that means that lookup
1390 * found an entry with our hash value. This is the freespace
1391 * block for that data entry.
1392 */
1393 if (fblk) {
1394 fbp = fblk->bp;
1395 /*
1396 * Remember initial freespace block number.
1397 */
1398 ifbno = fblk->blkno;
1399 free = fbp->data;
1400 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
1401 findex = fblk->index;
1402 /*
1403 * This means the free entry showed that the data block had
1404 * space for our entry, so we remembered it.
1405 * Use that data block.
1406 */
1407 if (findex >= 0) {
1408 ASSERT(findex < INT_GET(free->hdr.nvalid, ARCH_CONVERT));
1409 ASSERT(INT_GET(free->bests[findex], ARCH_CONVERT) != NULLDATAOFF);
1410 ASSERT(INT_GET(free->bests[findex], ARCH_CONVERT) >= length);
1411 dbno = INT_GET(free->hdr.firstdb, ARCH_CONVERT) + findex;
1412 }
1413 /*
1414 * The data block looked at didn't have enough room.
1415 * We'll start at the beginning of the freespace entries.
1416 */
1417 else {
1418 dbno = -1;
1419 findex = 0;
1420 }
1421 }
1422 /*
1423 * Didn't come in with a freespace block, so don't have a data block.
1424 */
1425 else {
1426 ifbno = dbno = -1;
1427 fbp = NULL;
1428 findex = 0;
1429 }
1430 /*
1431 * If we don't have a data block yet, we're going to scan the
1432 * freespace blocks looking for one. Figure out what the
1433 * highest freespace block number is.
1434 */
1435 if (dbno == -1) {
1436 xfs_fileoff_t fo; /* freespace block number */
1437
1438 if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK)))
1439 return error;
1440 lastfbno = XFS_DIR2_DA_TO_DB(mp, (xfs_dablk_t)fo);
1441 fbno = ifbno;
1442 }
1443 /*
1444 * While we haven't identified a data block, search the freeblock
1445 * data for a good data block. If we find a null freeblock entry,
1446 * indicating a hole in the data blocks, remember that.
1447 */
1448 while (dbno == -1) {
1449 /*
1450 * If we don't have a freeblock in hand, get the next one.
1451 */
1452 if (fbp == NULL) {
1453 /*
1454 * Happens the first time through unless lookup gave
1455 * us a freespace block to start with.
1456 */
1457 if (++fbno == 0)
1458 fbno = XFS_DIR2_FREE_FIRSTDB(mp);
1459 /*
1460 * If it's ifbno we already looked at it.
1461 */
1462 if (fbno == ifbno)
1463 fbno++;
1464 /*
1465 * If it's off the end we're done.
1466 */
1467 if (fbno >= lastfbno)
1468 break;
1469 /*
1470 * Read the block. There can be holes in the
1471 * freespace blocks, so this might not succeed.
1472 * This should be really rare, so there's no reason
1473 * to avoid it.
1474 */
1475 if ((error = xfs_da_read_buf(tp, dp,
1476 XFS_DIR2_DB_TO_DA(mp, fbno), -2, &fbp,
1477 XFS_DATA_FORK))) {
1478 return error;
1479 }
1480 if (unlikely(fbp == NULL)) {
1481 continue;
1482 }
1483 free = fbp->data;
1484 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
1485 findex = 0;
1486 }
1487 /*
1488 * Look at the current free entry. Is it good enough?
1489 */
1490 if (INT_GET(free->bests[findex], ARCH_CONVERT) != NULLDATAOFF &&
1491 INT_GET(free->bests[findex], ARCH_CONVERT) >= length)
1492 dbno = INT_GET(free->hdr.firstdb, ARCH_CONVERT) + findex;
1493 else {
1494 /*
1495 * Are we done with the freeblock?
1496 */
1497 if (++findex == INT_GET(free->hdr.nvalid, ARCH_CONVERT)) {
1498 /*
1499 * Drop the block.
1500 */
1501 xfs_da_brelse(tp, fbp);
1502 fbp = NULL;
1503 if (fblk && fblk->bp)
1504 fblk->bp = NULL;
1505 }
1506 }
1507 }
1508 /*
1509 * If we don't have a data block, we need to allocate one and make
1510 * the freespace entries refer to it.
1511 */
1512 if (unlikely(dbno == -1)) {
1513 /*
1514 * Not allowed to allocate, return failure.
1515 */
1516 if (args->justcheck || args->total == 0) {
1517 /*
1518 * Drop the freespace buffer unless it came from our
1519 * caller.
1520 */
1521 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1522 xfs_da_buf_done(fbp);
1523 return XFS_ERROR(ENOSPC);
1524 }
1525 /*
1526 * Allocate and initialize the new data block.
1527 */
1528 if (unlikely((error = xfs_dir2_grow_inode(args,
1529 XFS_DIR2_DATA_SPACE,
1530 &dbno)) ||
1531 (error = xfs_dir2_data_init(args, dbno, &dbp)))) {
1532 /*
1533 * Drop the freespace buffer unless it came from our
1534 * caller.
1535 */
1536 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1537 xfs_da_buf_done(fbp);
1538 return error;
1539 }
1540 /*
1541 * If (somehow) we have a freespace block, get rid of it.
1542 */
1543 if (fbp)
1544 xfs_da_brelse(tp, fbp);
1545 if (fblk && fblk->bp)
1546 fblk->bp = NULL;
1547
1548 /*
1549 * Get the freespace block corresponding to the data block
1550 * that was just allocated.
1551 */
1552 fbno = XFS_DIR2_DB_TO_FDB(mp, dbno);
1553 if (unlikely(error = xfs_da_read_buf(tp, dp,
1554 XFS_DIR2_DB_TO_DA(mp, fbno), -2, &fbp,
1555 XFS_DATA_FORK))) {
1556 xfs_da_buf_done(dbp);
1557 return error;
1558 }
1559 /*
1560 * If there wasn't a freespace block, the read will
1561 * return a NULL fbp. Allocate and initialize a new one.
1562 */
1563 if( fbp == NULL ) {
1564 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE,
1565 &fbno))) {
1566 return error;
1567 }
1568
1569 if (unlikely(XFS_DIR2_DB_TO_FDB(mp, dbno) != fbno)) {
1570 cmn_err(CE_ALERT,
1571 "xfs_dir2_node_addname_int: dir ino "
1572 "%llu needed freesp block %lld for\n"
1573 " data block %lld, got %lld\n"
1574 " ifbno %llu lastfbno %d\n",
1575 (unsigned long long)dp->i_ino,
1576 (long long)XFS_DIR2_DB_TO_FDB(mp, dbno),
1577 (long long)dbno, (long long)fbno,
1578 (unsigned long long)ifbno, lastfbno);
1579 if (fblk) {
1580 cmn_err(CE_ALERT,
1581 " fblk 0x%p blkno %llu "
1582 "index %d magic 0x%x\n",
1583 fblk,
1584 (unsigned long long)fblk->blkno,
1585 fblk->index,
1586 fblk->magic);
1587 } else {
1588 cmn_err(CE_ALERT,
1589 " ... fblk is NULL\n");
1590 }
1591 XFS_ERROR_REPORT("xfs_dir2_node_addname_int",
1592 XFS_ERRLEVEL_LOW, mp);
1593 return XFS_ERROR(EFSCORRUPTED);
1594 }
1595
1596 /*
1597 * Get a buffer for the new block.
1598 */
1599 if ((error = xfs_da_get_buf(tp, dp,
1600 XFS_DIR2_DB_TO_DA(mp, fbno),
1601 -1, &fbp, XFS_DATA_FORK))) {
1602 return error;
1603 }
1604 ASSERT(fbp != NULL);
1605
1606 /*
1607 * Initialize the new block to be empty, and remember
1608 * its first slot as our empty slot.
1609 */
1610 free = fbp->data;
1611 INT_SET(free->hdr.magic, ARCH_CONVERT, XFS_DIR2_FREE_MAGIC);
1612 INT_SET(free->hdr.firstdb, ARCH_CONVERT,
1613 (fbno - XFS_DIR2_FREE_FIRSTDB(mp)) *
1614 XFS_DIR2_MAX_FREE_BESTS(mp));
1615 free->hdr.nvalid = 0;
1616 free->hdr.nused = 0;
1617 } else {
1618 free = fbp->data;
1619 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
1620 }
1621
1622 /*
1623 * Set the freespace block index from the data block number.
1624 */
1625 findex = XFS_DIR2_DB_TO_FDINDEX(mp, dbno);
1626 /*
1627 * If it's after the end of the current entries in the
1628 * freespace block, extend that table.
1629 */
1630 if (findex >= INT_GET(free->hdr.nvalid, ARCH_CONVERT)) {
1631 ASSERT(findex < XFS_DIR2_MAX_FREE_BESTS(mp));
1632 INT_SET(free->hdr.nvalid, ARCH_CONVERT, findex + 1);
1633 /*
1634 * Tag new entry so nused will go up.
1635 */
1636 INT_SET(free->bests[findex], ARCH_CONVERT, NULLDATAOFF);
1637 }
1638 /*
1639 * If this entry was for an empty data block
1640 * (this should always be true) then update the header.
1641 */
1642 if (INT_GET(free->bests[findex], ARCH_CONVERT) == NULLDATAOFF) {
1643 INT_MOD(free->hdr.nused, ARCH_CONVERT, +1);
1644 xfs_dir2_free_log_header(tp, fbp);
1645 }
1646 /*
1647 * Update the real value in the table.
1648 * We haven't allocated the data entry yet so this will
1649 * change again.
1650 */
1651 data = dbp->data;
1652 INT_COPY(free->bests[findex], data->hdr.bestfree[0].length, ARCH_CONVERT);
1653 logfree = 1;
1654 }
1655 /*
1656 * We had a data block so we don't have to make a new one.
1657 */
1658 else {
1659 /*
1660 * If just checking, we succeeded.
1661 */
1662 if (args->justcheck) {
1663 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1664 xfs_da_buf_done(fbp);
1665 return 0;
1666 }
1667 /*
1668 * Read the data block in.
1669 */
1670 if (unlikely(
1671 error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, dbno),
1672 -1, &dbp, XFS_DATA_FORK))) {
1673 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1674 xfs_da_buf_done(fbp);
1675 return error;
1676 }
1677 data = dbp->data;
1678 logfree = 0;
1679 }
1680 ASSERT(INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT) >= length);
1681 /*
1682 * Point to the existing unused space.
1683 */
1684 dup = (xfs_dir2_data_unused_t *)
1685 ((char *)data + INT_GET(data->hdr.bestfree[0].offset, ARCH_CONVERT));
1686 needscan = needlog = 0;
1687 /*
1688 * Mark the first part of the unused space, inuse for us.
1689 */
1690 xfs_dir2_data_use_free(tp, dbp, dup,
1691 (xfs_dir2_data_aoff_t)((char *)dup - (char *)data), length,
1692 &needlog, &needscan);
1693 /*
1694 * Fill in the new entry and log it.
1695 */
1696 dep = (xfs_dir2_data_entry_t *)dup;
1697 INT_SET(dep->inumber, ARCH_CONVERT, args->inumber);
1698 dep->namelen = args->namelen;
1699 memcpy(dep->name, args->name, dep->namelen);
1700 tagp = XFS_DIR2_DATA_ENTRY_TAG_P(dep);
1701 INT_SET(*tagp, ARCH_CONVERT, (xfs_dir2_data_off_t)((char *)dep - (char *)data));
1702 xfs_dir2_data_log_entry(tp, dbp, dep);
1703 /*
1704 * Rescan the block for bestfree if needed.
1705 */
1706 if (needscan)
1707 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
1708 /*
1709 * Log the data block header if needed.
1710 */
1711 if (needlog)
1712 xfs_dir2_data_log_header(tp, dbp);
1713 /*
1714 * If the freespace entry is now wrong, update it.
1715 */
1716 if (INT_GET(free->bests[findex], ARCH_CONVERT) != INT_GET(data->hdr.bestfree[0].length, ARCH_CONVERT)) {
1717 INT_COPY(free->bests[findex], data->hdr.bestfree[0].length, ARCH_CONVERT);
1718 logfree = 1;
1719 }
1720 /*
1721 * Log the freespace entry if needed.
1722 */
1723 if (logfree)
1724 xfs_dir2_free_log_bests(tp, fbp, findex, findex);
1725 /*
1726 * If the caller didn't hand us the freespace block, drop it.
1727 */
1728 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1729 xfs_da_buf_done(fbp);
1730 /*
1731 * Return the data block and offset in args, then drop the data block.
1732 */
1733 args->blkno = (xfs_dablk_t)dbno;
1734 args->index = INT_GET(*tagp, ARCH_CONVERT);
1735 xfs_da_buf_done(dbp);
1736 return 0;
1737 }
1738
1739 /*
1740 * Lookup an entry in a node-format directory.
1741 * All the real work happens in xfs_da_node_lookup_int.
1742 * The only real output is the inode number of the entry.
1743 */
1744 int /* error */
1745 xfs_dir2_node_lookup(
1746 xfs_da_args_t *args) /* operation arguments */
1747 {
1748 int error; /* error return value */
1749 int i; /* btree level */
1750 int rval; /* operation return value */
1751 xfs_da_state_t *state; /* btree cursor */
1752
1753 xfs_dir2_trace_args("node_lookup", args);
1754 /*
1755 * Allocate and initialize the btree cursor.
1756 */
1757 state = xfs_da_state_alloc();
1758 state->args = args;
1759 state->mp = args->dp->i_mount;
1760 state->blocksize = state->mp->m_dirblksize;
1761 state->node_ents = state->mp->m_dir_node_ents;
1762 /*
1763 * Fill in the path to the entry in the cursor.
1764 */
1765 error = xfs_da_node_lookup_int(state, &rval);
1766 if (error)
1767 rval = error;
1768 /*
1769 * Release the btree blocks and leaf block.
1770 */
1771 for (i = 0; i < state->path.active; i++) {
1772 xfs_da_brelse(args->trans, state->path.blk[i].bp);
1773 state->path.blk[i].bp = NULL;
1774 }
1775 /*
1776 * Release the data block if we have it.
1777 */
1778 if (state->extravalid && state->extrablk.bp) {
1779 xfs_da_brelse(args->trans, state->extrablk.bp);
1780 state->extrablk.bp = NULL;
1781 }
1782 xfs_da_state_free(state);
1783 return rval;
1784 }
1785
1786 /*
1787 * Remove an entry from a node-format directory.
1788 */
1789 int /* error */
1790 xfs_dir2_node_removename(
1791 xfs_da_args_t *args) /* operation arguments */
1792 {
1793 xfs_da_state_blk_t *blk; /* leaf block */
1794 int error; /* error return value */
1795 int rval; /* operation return value */
1796 xfs_da_state_t *state; /* btree cursor */
1797
1798 xfs_dir2_trace_args("node_removename", args);
1799 /*
1800 * Allocate and initialize the btree cursor.
1801 */
1802 state = xfs_da_state_alloc();
1803 state->args = args;
1804 state->mp = args->dp->i_mount;
1805 state->blocksize = state->mp->m_dirblksize;
1806 state->node_ents = state->mp->m_dir_node_ents;
1807 /*
1808 * Look up the entry we're deleting, set up the cursor.
1809 */
1810 error = xfs_da_node_lookup_int(state, &rval);
1811 if (error) {
1812 rval = error;
1813 }
1814 /*
1815 * Didn't find it, upper layer screwed up.
1816 */
1817 if (rval != EEXIST) {
1818 xfs_da_state_free(state);
1819 return rval;
1820 }
1821 blk = &state->path.blk[state->path.active - 1];
1822 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1823 ASSERT(state->extravalid);
1824 /*
1825 * Remove the leaf and data entries.
1826 * Extrablk refers to the data block.
1827 */
1828 error = xfs_dir2_leafn_remove(args, blk->bp, blk->index,
1829 &state->extrablk, &rval);
1830 if (error) {
1831 return error;
1832 }
1833 /*
1834 * Fix the hash values up the btree.
1835 */
1836 xfs_da_fixhashpath(state, &state->path);
1837 /*
1838 * If we need to join leaf blocks, do it.
1839 */
1840 if (rval && state->path.active > 1)
1841 error = xfs_da_join(state);
1842 /*
1843 * If no errors so far, try conversion to leaf format.
1844 */
1845 if (!error)
1846 error = xfs_dir2_node_to_leaf(state);
1847 xfs_da_state_free(state);
1848 return error;
1849 }
1850
1851 /*
1852 * Replace an entry's inode number in a node-format directory.
1853 */
1854 int /* error */
1855 xfs_dir2_node_replace(
1856 xfs_da_args_t *args) /* operation arguments */
1857 {
1858 xfs_da_state_blk_t *blk; /* leaf block */
1859 xfs_dir2_data_t *data; /* data block structure */
1860 xfs_dir2_data_entry_t *dep; /* data entry changed */
1861 int error; /* error return value */
1862 int i; /* btree level */
1863 xfs_ino_t inum; /* new inode number */
1864 xfs_dir2_leaf_t *leaf; /* leaf structure */
1865 xfs_dir2_leaf_entry_t *lep; /* leaf entry being changed */
1866 int rval; /* internal return value */
1867 xfs_da_state_t *state; /* btree cursor */
1868
1869 xfs_dir2_trace_args("node_replace", args);
1870 /*
1871 * Allocate and initialize the btree cursor.
1872 */
1873 state = xfs_da_state_alloc();
1874 state->args = args;
1875 state->mp = args->dp->i_mount;
1876 state->blocksize = state->mp->m_dirblksize;
1877 state->node_ents = state->mp->m_dir_node_ents;
1878 inum = args->inumber;
1879 /*
1880 * Lookup the entry to change in the btree.
1881 */
1882 error = xfs_da_node_lookup_int(state, &rval);
1883 if (error) {
1884 rval = error;
1885 }
1886 /*
1887 * It should be found, since the vnodeops layer has looked it up
1888 * and locked it. But paranoia is good.
1889 */
1890 if (rval == EEXIST) {
1891 /*
1892 * Find the leaf entry.
1893 */
1894 blk = &state->path.blk[state->path.active - 1];
1895 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1896 leaf = blk->bp->data;
1897 lep = &leaf->ents[blk->index];
1898 ASSERT(state->extravalid);
1899 /*
1900 * Point to the data entry.
1901 */
1902 data = state->extrablk.bp->data;
1903 ASSERT(INT_GET(data->hdr.magic, ARCH_CONVERT) == XFS_DIR2_DATA_MAGIC);
1904 dep = (xfs_dir2_data_entry_t *)
1905 ((char *)data +
1906 XFS_DIR2_DATAPTR_TO_OFF(state->mp, INT_GET(lep->address, ARCH_CONVERT)));
1907 ASSERT(inum != INT_GET(dep->inumber, ARCH_CONVERT));
1908 /*
1909 * Fill in the new inode number and log the entry.
1910 */
1911 INT_SET(dep->inumber, ARCH_CONVERT, inum);
1912 xfs_dir2_data_log_entry(args->trans, state->extrablk.bp, dep);
1913 rval = 0;
1914 }
1915 /*
1916 * Didn't find it, and we're holding a data block. Drop it.
1917 */
1918 else if (state->extravalid) {
1919 xfs_da_brelse(args->trans, state->extrablk.bp);
1920 state->extrablk.bp = NULL;
1921 }
1922 /*
1923 * Release all the buffers in the cursor.
1924 */
1925 for (i = 0; i < state->path.active; i++) {
1926 xfs_da_brelse(args->trans, state->path.blk[i].bp);
1927 state->path.blk[i].bp = NULL;
1928 }
1929 xfs_da_state_free(state);
1930 return rval;
1931 }
1932
1933 /*
1934 * Trim off a trailing empty freespace block.
1935 * Return (in rvalp) 1 if we did it, 0 if not.
1936 */
1937 int /* error */
1938 xfs_dir2_node_trim_free(
1939 xfs_da_args_t *args, /* operation arguments */
1940 xfs_fileoff_t fo, /* free block number */
1941 int *rvalp) /* out: did something */
1942 {
1943 xfs_dabuf_t *bp; /* freespace buffer */
1944 xfs_inode_t *dp; /* incore directory inode */
1945 int error; /* error return code */
1946 xfs_dir2_free_t *free; /* freespace structure */
1947 xfs_mount_t *mp; /* filesystem mount point */
1948 xfs_trans_t *tp; /* transaction pointer */
1949
1950 dp = args->dp;
1951 mp = dp->i_mount;
1952 tp = args->trans;
1953 /*
1954 * Read the freespace block.
1955 */
1956 if (unlikely(error = xfs_da_read_buf(tp, dp, (xfs_dablk_t)fo, -2, &bp,
1957 XFS_DATA_FORK))) {
1958 return error;
1959 }
1960
1961 /*
1962 * There can be holes in freespace. If fo is a hole, there's
1963 * nothing to do.
1964 */
1965 if (bp == NULL) {
1966 return 0;
1967 }
1968 free = bp->data;
1969 ASSERT(INT_GET(free->hdr.magic, ARCH_CONVERT) == XFS_DIR2_FREE_MAGIC);
1970 /*
1971 * If there are used entries, there's nothing to do.
1972 */
1973 if (INT_GET(free->hdr.nused, ARCH_CONVERT) > 0) {
1974 xfs_da_brelse(tp, bp);
1975 *rvalp = 0;
1976 return 0;
1977 }
1978 /*
1979 * Blow the block away.
1980 */
1981 if ((error =
1982 xfs_dir2_shrink_inode(args, XFS_DIR2_DA_TO_DB(mp, (xfs_dablk_t)fo),
1983 bp))) {
1984 /*
1985 * Can't fail with ENOSPC since that only happens with no
1986 * space reservation, when breaking up an extent into two
1987 * pieces. This is the last block of an extent.
1988 */
1989 ASSERT(error != ENOSPC);
1990 xfs_da_brelse(tp, bp);
1991 return error;
1992 }
1993 /*
1994 * Return that we succeeded.
1995 */
1996 *rvalp = 1;
1997 return 0;
1998 }
WandBoard kernel