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