projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
s390/pfault: add sanity check
[deliverable/linux.git] / fs / xfs / xfs_dir2_block.c
1 /*
2 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_log.h"
22 #include "xfs_inum.h"
23 #include "xfs_trans.h"
24 #include "xfs_sb.h"
25 #include "xfs_ag.h"
26 #include "xfs_mount.h"
27 #include "xfs_da_btree.h"
28 #include "xfs_bmap_btree.h"
29 #include "xfs_dinode.h"
30 #include "xfs_inode.h"
31 #include "xfs_inode_item.h"
32 #include "xfs_dir2.h"
33 #include "xfs_dir2_format.h"
34 #include "xfs_dir2_priv.h"
35 #include "xfs_error.h"
36 #include "xfs_trace.h"
37
38 /*
39 * Local function prototypes.
40 */
41 static void xfs_dir2_block_log_leaf(xfs_trans_t *tp, xfs_dabuf_t *bp, int first,
42 int last);
43 static void xfs_dir2_block_log_tail(xfs_trans_t *tp, xfs_dabuf_t *bp);
44 static int xfs_dir2_block_lookup_int(xfs_da_args_t *args, xfs_dabuf_t **bpp,
45 int *entno);
46 static int xfs_dir2_block_sort(const void *a, const void *b);
47
48 static xfs_dahash_t xfs_dir_hash_dot, xfs_dir_hash_dotdot;
49
50 /*
51 * One-time startup routine called from xfs_init().
52 */
53 void
54 xfs_dir_startup(void)
55 {
56 xfs_dir_hash_dot = xfs_da_hashname((unsigned char *)".", 1);
57 xfs_dir_hash_dotdot = xfs_da_hashname((unsigned char *)"..", 2);
58 }
59
60 /*
61 * Add an entry to a block directory.
62 */
63 int /* error */
64 xfs_dir2_block_addname(
65 xfs_da_args_t *args) /* directory op arguments */
66 {
67 xfs_dir2_data_free_t *bf; /* bestfree table in block */
68 xfs_dir2_data_hdr_t *hdr; /* block header */
69 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */
70 xfs_dabuf_t *bp; /* buffer for block */
71 xfs_dir2_block_tail_t *btp; /* block tail */
72 int compact; /* need to compact leaf ents */
73 xfs_dir2_data_entry_t *dep; /* block data entry */
74 xfs_inode_t *dp; /* directory inode */
75 xfs_dir2_data_unused_t *dup; /* block unused entry */
76 int error; /* error return value */
77 xfs_dir2_data_unused_t *enddup=NULL; /* unused at end of data */
78 xfs_dahash_t hash; /* hash value of found entry */
79 int high; /* high index for binary srch */
80 int highstale; /* high stale index */
81 int lfloghigh=0; /* last final leaf to log */
82 int lfloglow=0; /* first final leaf to log */
83 int len; /* length of the new entry */
84 int low; /* low index for binary srch */
85 int lowstale; /* low stale index */
86 int mid=0; /* midpoint for binary srch */
87 xfs_mount_t *mp; /* filesystem mount point */
88 int needlog; /* need to log header */
89 int needscan; /* need to rescan freespace */
90 __be16 *tagp; /* pointer to tag value */
91 xfs_trans_t *tp; /* transaction structure */
92
93 trace_xfs_dir2_block_addname(args);
94
95 dp = args->dp;
96 tp = args->trans;
97 mp = dp->i_mount;
98 /*
99 * Read the (one and only) directory block into dabuf bp.
100 */
101 if ((error =
102 xfs_da_read_buf(tp, dp, mp->m_dirdatablk, -1, &bp, XFS_DATA_FORK))) {
103 return error;
104 }
105 ASSERT(bp != NULL);
106 hdr = bp->data;
107 /*
108 * Check the magic number, corrupted if wrong.
109 */
110 if (unlikely(hdr->magic != cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))) {
111 XFS_CORRUPTION_ERROR("xfs_dir2_block_addname",
112 XFS_ERRLEVEL_LOW, mp, hdr);
113 xfs_da_brelse(tp, bp);
114 return XFS_ERROR(EFSCORRUPTED);
115 }
116 len = xfs_dir2_data_entsize(args->namelen);
117 /*
118 * Set up pointers to parts of the block.
119 */
120 bf = hdr->bestfree;
121 btp = xfs_dir2_block_tail_p(mp, hdr);
122 blp = xfs_dir2_block_leaf_p(btp);
123 /*
124 * No stale entries? Need space for entry and new leaf.
125 */
126 if (!btp->stale) {
127 /*
128 * Tag just before the first leaf entry.
129 */
130 tagp = (__be16 *)blp - 1;
131 /*
132 * Data object just before the first leaf entry.
133 */
134 enddup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
135 /*
136 * If it's not free then can't do this add without cleaning up:
137 * the space before the first leaf entry needs to be free so it
138 * can be expanded to hold the pointer to the new entry.
139 */
140 if (be16_to_cpu(enddup->freetag) != XFS_DIR2_DATA_FREE_TAG)
141 dup = enddup = NULL;
142 /*
143 * Check out the biggest freespace and see if it's the same one.
144 */
145 else {
146 dup = (xfs_dir2_data_unused_t *)
147 ((char *)hdr + be16_to_cpu(bf[0].offset));
148 if (dup == enddup) {
149 /*
150 * It is the biggest freespace, is it too small
151 * to hold the new leaf too?
152 */
153 if (be16_to_cpu(dup->length) < len + (uint)sizeof(*blp)) {
154 /*
155 * Yes, we use the second-largest
156 * entry instead if it works.
157 */
158 if (be16_to_cpu(bf[1].length) >= len)
159 dup = (xfs_dir2_data_unused_t *)
160 ((char *)hdr +
161 be16_to_cpu(bf[1].offset));
162 else
163 dup = NULL;
164 }
165 } else {
166 /*
167 * Not the same free entry,
168 * just check its length.
169 */
170 if (be16_to_cpu(dup->length) < len) {
171 dup = NULL;
172 }
173 }
174 }
175 compact = 0;
176 }
177 /*
178 * If there are stale entries we'll use one for the leaf.
179 * Is the biggest entry enough to avoid compaction?
180 */
181 else if (be16_to_cpu(bf[0].length) >= len) {
182 dup = (xfs_dir2_data_unused_t *)
183 ((char *)hdr + be16_to_cpu(bf[0].offset));
184 compact = 0;
185 }
186 /*
187 * Will need to compact to make this work.
188 */
189 else {
190 /*
191 * Tag just before the first leaf entry.
192 */
193 tagp = (__be16 *)blp - 1;
194 /*
195 * Data object just before the first leaf entry.
196 */
197 dup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
198 /*
199 * If it's not free then the data will go where the
200 * leaf data starts now, if it works at all.
201 */
202 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
203 if (be16_to_cpu(dup->length) + (be32_to_cpu(btp->stale) - 1) *
204 (uint)sizeof(*blp) < len)
205 dup = NULL;
206 } else if ((be32_to_cpu(btp->stale) - 1) * (uint)sizeof(*blp) < len)
207 dup = NULL;
208 else
209 dup = (xfs_dir2_data_unused_t *)blp;
210 compact = 1;
211 }
212 /*
213 * If this isn't a real add, we're done with the buffer.
214 */
215 if (args->op_flags & XFS_DA_OP_JUSTCHECK)
216 xfs_da_brelse(tp, bp);
217 /*
218 * If we don't have space for the new entry & leaf ...
219 */
220 if (!dup) {
221 /*
222 * Not trying to actually do anything, or don't have
223 * a space reservation: return no-space.
224 */
225 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) || args->total == 0)
226 return XFS_ERROR(ENOSPC);
227 /*
228 * Convert to the next larger format.
229 * Then add the new entry in that format.
230 */
231 error = xfs_dir2_block_to_leaf(args, bp);
232 xfs_da_buf_done(bp);
233 if (error)
234 return error;
235 return xfs_dir2_leaf_addname(args);
236 }
237 /*
238 * Just checking, and it would work, so say so.
239 */
240 if (args->op_flags & XFS_DA_OP_JUSTCHECK)
241 return 0;
242 needlog = needscan = 0;
243 /*
244 * If need to compact the leaf entries, do it now.
245 * Leave the highest-numbered stale entry stale.
246 * XXX should be the one closest to mid but mid is not yet computed.
247 */
248 if (compact) {
249 int fromidx; /* source leaf index */
250 int toidx; /* target leaf index */
251
252 for (fromidx = toidx = be32_to_cpu(btp->count) - 1,
253 highstale = lfloghigh = -1;
254 fromidx >= 0;
255 fromidx--) {
256 if (blp[fromidx].address ==
257 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
258 if (highstale == -1)
259 highstale = toidx;
260 else {
261 if (lfloghigh == -1)
262 lfloghigh = toidx;
263 continue;
264 }
265 }
266 if (fromidx < toidx)
267 blp[toidx] = blp[fromidx];
268 toidx--;
269 }
270 lfloglow = toidx + 1 - (be32_to_cpu(btp->stale) - 1);
271 lfloghigh -= be32_to_cpu(btp->stale) - 1;
272 be32_add_cpu(&btp->count, -(be32_to_cpu(btp->stale) - 1));
273 xfs_dir2_data_make_free(tp, bp,
274 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
275 (xfs_dir2_data_aoff_t)((be32_to_cpu(btp->stale) - 1) * sizeof(*blp)),
276 &needlog, &needscan);
277 blp += be32_to_cpu(btp->stale) - 1;
278 btp->stale = cpu_to_be32(1);
279 /*
280 * If we now need to rebuild the bestfree map, do so.
281 * This needs to happen before the next call to use_free.
282 */
283 if (needscan) {
284 xfs_dir2_data_freescan(mp, hdr, &needlog);
285 needscan = 0;
286 }
287 }
288 /*
289 * Set leaf logging boundaries to impossible state.
290 * For the no-stale case they're set explicitly.
291 */
292 else if (btp->stale) {
293 lfloglow = be32_to_cpu(btp->count);
294 lfloghigh = -1;
295 }
296 /*
297 * Find the slot that's first lower than our hash value, -1 if none.
298 */
299 for (low = 0, high = be32_to_cpu(btp->count) - 1; low <= high; ) {
300 mid = (low + high) >> 1;
301 if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)
302 break;
303 if (hash < args->hashval)
304 low = mid + 1;
305 else
306 high = mid - 1;
307 }
308 while (mid >= 0 && be32_to_cpu(blp[mid].hashval) >= args->hashval) {
309 mid--;
310 }
311 /*
312 * No stale entries, will use enddup space to hold new leaf.
313 */
314 if (!btp->stale) {
315 /*
316 * Mark the space needed for the new leaf entry, now in use.
317 */
318 xfs_dir2_data_use_free(tp, bp, enddup,
319 (xfs_dir2_data_aoff_t)
320 ((char *)enddup - (char *)hdr + be16_to_cpu(enddup->length) -
321 sizeof(*blp)),
322 (xfs_dir2_data_aoff_t)sizeof(*blp),
323 &needlog, &needscan);
324 /*
325 * Update the tail (entry count).
326 */
327 be32_add_cpu(&btp->count, 1);
328 /*
329 * If we now need to rebuild the bestfree map, do so.
330 * This needs to happen before the next call to use_free.
331 */
332 if (needscan) {
333 xfs_dir2_data_freescan(mp, hdr, &needlog);
334 needscan = 0;
335 }
336 /*
337 * Adjust pointer to the first leaf entry, we're about to move
338 * the table up one to open up space for the new leaf entry.
339 * Then adjust our index to match.
340 */
341 blp--;
342 mid++;
343 if (mid)
344 memmove(blp, &blp[1], mid * sizeof(*blp));
345 lfloglow = 0;
346 lfloghigh = mid;
347 }
348 /*
349 * Use a stale leaf for our new entry.
350 */
351 else {
352 for (lowstale = mid;
353 lowstale >= 0 &&
354 blp[lowstale].address !=
355 cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
356 lowstale--)
357 continue;
358 for (highstale = mid + 1;
359 highstale < be32_to_cpu(btp->count) &&
360 blp[highstale].address !=
361 cpu_to_be32(XFS_DIR2_NULL_DATAPTR) &&
362 (lowstale < 0 || mid - lowstale > highstale - mid);
363 highstale++)
364 continue;
365 /*
366 * Move entries toward the low-numbered stale entry.
367 */
368 if (lowstale >= 0 &&
369 (highstale == be32_to_cpu(btp->count) ||
370 mid - lowstale <= highstale - mid)) {
371 if (mid - lowstale)
372 memmove(&blp[lowstale], &blp[lowstale + 1],
373 (mid - lowstale) * sizeof(*blp));
374 lfloglow = MIN(lowstale, lfloglow);
375 lfloghigh = MAX(mid, lfloghigh);
376 }
377 /*
378 * Move entries toward the high-numbered stale entry.
379 */
380 else {
381 ASSERT(highstale < be32_to_cpu(btp->count));
382 mid++;
383 if (highstale - mid)
384 memmove(&blp[mid + 1], &blp[mid],
385 (highstale - mid) * sizeof(*blp));
386 lfloglow = MIN(mid, lfloglow);
387 lfloghigh = MAX(highstale, lfloghigh);
388 }
389 be32_add_cpu(&btp->stale, -1);
390 }
391 /*
392 * Point to the new data entry.
393 */
394 dep = (xfs_dir2_data_entry_t *)dup;
395 /*
396 * Fill in the leaf entry.
397 */
398 blp[mid].hashval = cpu_to_be32(args->hashval);
399 blp[mid].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(mp,
400 (char *)dep - (char *)hdr));
401 xfs_dir2_block_log_leaf(tp, bp, lfloglow, lfloghigh);
402 /*
403 * Mark space for the data entry used.
404 */
405 xfs_dir2_data_use_free(tp, bp, dup,
406 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
407 (xfs_dir2_data_aoff_t)len, &needlog, &needscan);
408 /*
409 * Create the new data entry.
410 */
411 dep->inumber = cpu_to_be64(args->inumber);
412 dep->namelen = args->namelen;
413 memcpy(dep->name, args->name, args->namelen);
414 tagp = xfs_dir2_data_entry_tag_p(dep);
415 *tagp = cpu_to_be16((char *)dep - (char *)hdr);
416 /*
417 * Clean up the bestfree array and log the header, tail, and entry.
418 */
419 if (needscan)
420 xfs_dir2_data_freescan(mp, hdr, &needlog);
421 if (needlog)
422 xfs_dir2_data_log_header(tp, bp);
423 xfs_dir2_block_log_tail(tp, bp);
424 xfs_dir2_data_log_entry(tp, bp, dep);
425 xfs_dir2_data_check(dp, bp);
426 xfs_da_buf_done(bp);
427 return 0;
428 }
429
430 /*
431 * Readdir for block directories.
432 */
433 int /* error */
434 xfs_dir2_block_getdents(
435 xfs_inode_t *dp, /* incore inode */
436 void *dirent,
437 xfs_off_t *offset,
438 filldir_t filldir)
439 {
440 xfs_dir2_data_hdr_t *hdr; /* block header */
441 xfs_dabuf_t *bp; /* buffer for block */
442 xfs_dir2_block_tail_t *btp; /* block tail */
443 xfs_dir2_data_entry_t *dep; /* block data entry */
444 xfs_dir2_data_unused_t *dup; /* block unused entry */
445 char *endptr; /* end of the data entries */
446 int error; /* error return value */
447 xfs_mount_t *mp; /* filesystem mount point */
448 char *ptr; /* current data entry */
449 int wantoff; /* starting block offset */
450 xfs_off_t cook;
451
452 mp = dp->i_mount;
453 /*
454 * If the block number in the offset is out of range, we're done.
455 */
456 if (xfs_dir2_dataptr_to_db(mp, *offset) > mp->m_dirdatablk) {
457 return 0;
458 }
459 /*
460 * Can't read the block, give up, else get dabuf in bp.
461 */
462 error = xfs_da_read_buf(NULL, dp, mp->m_dirdatablk, -1,
463 &bp, XFS_DATA_FORK);
464 if (error)
465 return error;
466
467 ASSERT(bp != NULL);
468 /*
469 * Extract the byte offset we start at from the seek pointer.
470 * We'll skip entries before this.
471 */
472 wantoff = xfs_dir2_dataptr_to_off(mp, *offset);
473 hdr = bp->data;
474 xfs_dir2_data_check(dp, bp);
475 /*
476 * Set up values for the loop.
477 */
478 btp = xfs_dir2_block_tail_p(mp, hdr);
479 ptr = (char *)(hdr + 1);
480 endptr = (char *)xfs_dir2_block_leaf_p(btp);
481
482 /*
483 * Loop over the data portion of the block.
484 * Each object is a real entry (dep) or an unused one (dup).
485 */
486 while (ptr < endptr) {
487 dup = (xfs_dir2_data_unused_t *)ptr;
488 /*
489 * Unused, skip it.
490 */
491 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
492 ptr += be16_to_cpu(dup->length);
493 continue;
494 }
495
496 dep = (xfs_dir2_data_entry_t *)ptr;
497
498 /*
499 * Bump pointer for the next iteration.
500 */
501 ptr += xfs_dir2_data_entsize(dep->namelen);
502 /*
503 * The entry is before the desired starting point, skip it.
504 */
505 if ((char *)dep - (char *)hdr < wantoff)
506 continue;
507
508 cook = xfs_dir2_db_off_to_dataptr(mp, mp->m_dirdatablk,
509 (char *)dep - (char *)hdr);
510
511 /*
512 * If it didn't fit, set the final offset to here & return.
513 */
514 if (filldir(dirent, (char *)dep->name, dep->namelen,
515 cook & 0x7fffffff, be64_to_cpu(dep->inumber),
516 DT_UNKNOWN)) {
517 *offset = cook & 0x7fffffff;
518 xfs_da_brelse(NULL, bp);
519 return 0;
520 }
521 }
522
523 /*
524 * Reached the end of the block.
525 * Set the offset to a non-existent block 1 and return.
526 */
527 *offset = xfs_dir2_db_off_to_dataptr(mp, mp->m_dirdatablk + 1, 0) &
528 0x7fffffff;
529 xfs_da_brelse(NULL, bp);
530 return 0;
531 }
532
533 /*
534 * Log leaf entries from the block.
535 */
536 static void
537 xfs_dir2_block_log_leaf(
538 xfs_trans_t *tp, /* transaction structure */
539 xfs_dabuf_t *bp, /* block buffer */
540 int first, /* index of first logged leaf */
541 int last) /* index of last logged leaf */
542 {
543 xfs_dir2_data_hdr_t *hdr = bp->data;
544 xfs_dir2_leaf_entry_t *blp;
545 xfs_dir2_block_tail_t *btp;
546
547 btp = xfs_dir2_block_tail_p(tp->t_mountp, hdr);
548 blp = xfs_dir2_block_leaf_p(btp);
549 xfs_da_log_buf(tp, bp, (uint)((char *)&blp[first] - (char *)hdr),
550 (uint)((char *)&blp[last + 1] - (char *)hdr - 1));
551 }
552
553 /*
554 * Log the block tail.
555 */
556 static void
557 xfs_dir2_block_log_tail(
558 xfs_trans_t *tp, /* transaction structure */
559 xfs_dabuf_t *bp) /* block buffer */
560 {
561 xfs_dir2_data_hdr_t *hdr = bp->data;
562 xfs_dir2_block_tail_t *btp;
563
564 btp = xfs_dir2_block_tail_p(tp->t_mountp, hdr);
565 xfs_da_log_buf(tp, bp, (uint)((char *)btp - (char *)hdr),
566 (uint)((char *)(btp + 1) - (char *)hdr - 1));
567 }
568
569 /*
570 * Look up an entry in the block. This is the external routine,
571 * xfs_dir2_block_lookup_int does the real work.
572 */
573 int /* error */
574 xfs_dir2_block_lookup(
575 xfs_da_args_t *args) /* dir lookup arguments */
576 {
577 xfs_dir2_data_hdr_t *hdr; /* block header */
578 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */
579 xfs_dabuf_t *bp; /* block buffer */
580 xfs_dir2_block_tail_t *btp; /* block tail */
581 xfs_dir2_data_entry_t *dep; /* block data entry */
582 xfs_inode_t *dp; /* incore inode */
583 int ent; /* entry index */
584 int error; /* error return value */
585 xfs_mount_t *mp; /* filesystem mount point */
586
587 trace_xfs_dir2_block_lookup(args);
588
589 /*
590 * Get the buffer, look up the entry.
591 * If not found (ENOENT) then return, have no buffer.
592 */
593 if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent)))
594 return error;
595 dp = args->dp;
596 mp = dp->i_mount;
597 hdr = bp->data;
598 xfs_dir2_data_check(dp, bp);
599 btp = xfs_dir2_block_tail_p(mp, hdr);
600 blp = xfs_dir2_block_leaf_p(btp);
601 /*
602 * Get the offset from the leaf entry, to point to the data.
603 */
604 dep = (xfs_dir2_data_entry_t *)((char *)hdr +
605 xfs_dir2_dataptr_to_off(mp, be32_to_cpu(blp[ent].address)));
606 /*
607 * Fill in inode number, CI name if appropriate, release the block.
608 */
609 args->inumber = be64_to_cpu(dep->inumber);
610 error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
611 xfs_da_brelse(args->trans, bp);
612 return XFS_ERROR(error);
613 }
614
615 /*
616 * Internal block lookup routine.
617 */
618 static int /* error */
619 xfs_dir2_block_lookup_int(
620 xfs_da_args_t *args, /* dir lookup arguments */
621 xfs_dabuf_t **bpp, /* returned block buffer */
622 int *entno) /* returned entry number */
623 {
624 xfs_dir2_dataptr_t addr; /* data entry address */
625 xfs_dir2_data_hdr_t *hdr; /* block header */
626 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */
627 xfs_dabuf_t *bp; /* block buffer */
628 xfs_dir2_block_tail_t *btp; /* block tail */
629 xfs_dir2_data_entry_t *dep; /* block data entry */
630 xfs_inode_t *dp; /* incore inode */
631 int error; /* error return value */
632 xfs_dahash_t hash; /* found hash value */
633 int high; /* binary search high index */
634 int low; /* binary search low index */
635 int mid; /* binary search current idx */
636 xfs_mount_t *mp; /* filesystem mount point */
637 xfs_trans_t *tp; /* transaction pointer */
638 enum xfs_dacmp cmp; /* comparison result */
639
640 dp = args->dp;
641 tp = args->trans;
642 mp = dp->i_mount;
643 /*
644 * Read the buffer, return error if we can't get it.
645 */
646 if ((error =
647 xfs_da_read_buf(tp, dp, mp->m_dirdatablk, -1, &bp, XFS_DATA_FORK))) {
648 return error;
649 }
650 ASSERT(bp != NULL);
651 hdr = bp->data;
652 xfs_dir2_data_check(dp, bp);
653 btp = xfs_dir2_block_tail_p(mp, hdr);
654 blp = xfs_dir2_block_leaf_p(btp);
655 /*
656 * Loop doing a binary search for our hash value.
657 * Find our entry, ENOENT if it's not there.
658 */
659 for (low = 0, high = be32_to_cpu(btp->count) - 1; ; ) {
660 ASSERT(low <= high);
661 mid = (low + high) >> 1;
662 if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)
663 break;
664 if (hash < args->hashval)
665 low = mid + 1;
666 else
667 high = mid - 1;
668 if (low > high) {
669 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
670 xfs_da_brelse(tp, bp);
671 return XFS_ERROR(ENOENT);
672 }
673 }
674 /*
675 * Back up to the first one with the right hash value.
676 */
677 while (mid > 0 && be32_to_cpu(blp[mid - 1].hashval) == args->hashval) {
678 mid--;
679 }
680 /*
681 * Now loop forward through all the entries with the
682 * right hash value looking for our name.
683 */
684 do {
685 if ((addr = be32_to_cpu(blp[mid].address)) == XFS_DIR2_NULL_DATAPTR)
686 continue;
687 /*
688 * Get pointer to the entry from the leaf.
689 */
690 dep = (xfs_dir2_data_entry_t *)
691 ((char *)hdr + xfs_dir2_dataptr_to_off(mp, addr));
692 /*
693 * Compare name and if it's an exact match, return the index
694 * and buffer. If it's the first case-insensitive match, store
695 * the index and buffer and continue looking for an exact match.
696 */
697 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
698 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
699 args->cmpresult = cmp;
700 *bpp = bp;
701 *entno = mid;
702 if (cmp == XFS_CMP_EXACT)
703 return 0;
704 }
705 } while (++mid < be32_to_cpu(btp->count) &&
706 be32_to_cpu(blp[mid].hashval) == hash);
707
708 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
709 /*
710 * Here, we can only be doing a lookup (not a rename or replace).
711 * If a case-insensitive match was found earlier, return success.
712 */
713 if (args->cmpresult == XFS_CMP_CASE)
714 return 0;
715 /*
716 * No match, release the buffer and return ENOENT.
717 */
718 xfs_da_brelse(tp, bp);
719 return XFS_ERROR(ENOENT);
720 }
721
722 /*
723 * Remove an entry from a block format directory.
724 * If that makes the block small enough to fit in shortform, transform it.
725 */
726 int /* error */
727 xfs_dir2_block_removename(
728 xfs_da_args_t *args) /* directory operation args */
729 {
730 xfs_dir2_data_hdr_t *hdr; /* block header */
731 xfs_dir2_leaf_entry_t *blp; /* block leaf pointer */
732 xfs_dabuf_t *bp; /* block buffer */
733 xfs_dir2_block_tail_t *btp; /* block tail */
734 xfs_dir2_data_entry_t *dep; /* block data entry */
735 xfs_inode_t *dp; /* incore inode */
736 int ent; /* block leaf entry index */
737 int error; /* error return value */
738 xfs_mount_t *mp; /* filesystem mount point */
739 int needlog; /* need to log block header */
740 int needscan; /* need to fixup bestfree */
741 xfs_dir2_sf_hdr_t sfh; /* shortform header */
742 int size; /* shortform size */
743 xfs_trans_t *tp; /* transaction pointer */
744
745 trace_xfs_dir2_block_removename(args);
746
747 /*
748 * Look up the entry in the block. Gets the buffer and entry index.
749 * It will always be there, the vnodeops level does a lookup first.
750 */
751 if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent))) {
752 return error;
753 }
754 dp = args->dp;
755 tp = args->trans;
756 mp = dp->i_mount;
757 hdr = bp->data;
758 btp = xfs_dir2_block_tail_p(mp, hdr);
759 blp = xfs_dir2_block_leaf_p(btp);
760 /*
761 * Point to the data entry using the leaf entry.
762 */
763 dep = (xfs_dir2_data_entry_t *)
764 ((char *)hdr + xfs_dir2_dataptr_to_off(mp, be32_to_cpu(blp[ent].address)));
765 /*
766 * Mark the data entry's space free.
767 */
768 needlog = needscan = 0;
769 xfs_dir2_data_make_free(tp, bp,
770 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
771 xfs_dir2_data_entsize(dep->namelen), &needlog, &needscan);
772 /*
773 * Fix up the block tail.
774 */
775 be32_add_cpu(&btp->stale, 1);
776 xfs_dir2_block_log_tail(tp, bp);
777 /*
778 * Remove the leaf entry by marking it stale.
779 */
780 blp[ent].address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
781 xfs_dir2_block_log_leaf(tp, bp, ent, ent);
782 /*
783 * Fix up bestfree, log the header if necessary.
784 */
785 if (needscan)
786 xfs_dir2_data_freescan(mp, hdr, &needlog);
787 if (needlog)
788 xfs_dir2_data_log_header(tp, bp);
789 xfs_dir2_data_check(dp, bp);
790 /*
791 * See if the size as a shortform is good enough.
792 */
793 size = xfs_dir2_block_sfsize(dp, hdr, &sfh);
794 if (size > XFS_IFORK_DSIZE(dp)) {
795 xfs_da_buf_done(bp);
796 return 0;
797 }
798 /*
799 * If it works, do the conversion.
800 */
801 return xfs_dir2_block_to_sf(args, bp, size, &sfh);
802 }
803
804 /*
805 * Replace an entry in a V2 block directory.
806 * Change the inode number to the new value.
807 */
808 int /* error */
809 xfs_dir2_block_replace(
810 xfs_da_args_t *args) /* directory operation args */
811 {
812 xfs_dir2_data_hdr_t *hdr; /* block header */
813 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */
814 xfs_dabuf_t *bp; /* block buffer */
815 xfs_dir2_block_tail_t *btp; /* block tail */
816 xfs_dir2_data_entry_t *dep; /* block data entry */
817 xfs_inode_t *dp; /* incore inode */
818 int ent; /* leaf entry index */
819 int error; /* error return value */
820 xfs_mount_t *mp; /* filesystem mount point */
821
822 trace_xfs_dir2_block_replace(args);
823
824 /*
825 * Lookup the entry in the directory. Get buffer and entry index.
826 * This will always succeed since the caller has already done a lookup.
827 */
828 if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent))) {
829 return error;
830 }
831 dp = args->dp;
832 mp = dp->i_mount;
833 hdr = bp->data;
834 btp = xfs_dir2_block_tail_p(mp, hdr);
835 blp = xfs_dir2_block_leaf_p(btp);
836 /*
837 * Point to the data entry we need to change.
838 */
839 dep = (xfs_dir2_data_entry_t *)
840 ((char *)hdr + xfs_dir2_dataptr_to_off(mp, be32_to_cpu(blp[ent].address)));
841 ASSERT(be64_to_cpu(dep->inumber) != args->inumber);
842 /*
843 * Change the inode number to the new value.
844 */
845 dep->inumber = cpu_to_be64(args->inumber);
846 xfs_dir2_data_log_entry(args->trans, bp, dep);
847 xfs_dir2_data_check(dp, bp);
848 xfs_da_buf_done(bp);
849 return 0;
850 }
851
852 /*
853 * Qsort comparison routine for the block leaf entries.
854 */
855 static int /* sort order */
856 xfs_dir2_block_sort(
857 const void *a, /* first leaf entry */
858 const void *b) /* second leaf entry */
859 {
860 const xfs_dir2_leaf_entry_t *la; /* first leaf entry */
861 const xfs_dir2_leaf_entry_t *lb; /* second leaf entry */
862
863 la = a;
864 lb = b;
865 return be32_to_cpu(la->hashval) < be32_to_cpu(lb->hashval) ? -1 :
866 (be32_to_cpu(la->hashval) > be32_to_cpu(lb->hashval) ? 1 : 0);
867 }
868
869 /*
870 * Convert a V2 leaf directory to a V2 block directory if possible.
871 */
872 int /* error */
873 xfs_dir2_leaf_to_block(
874 xfs_da_args_t *args, /* operation arguments */
875 xfs_dabuf_t *lbp, /* leaf buffer */
876 xfs_dabuf_t *dbp) /* data buffer */
877 {
878 __be16 *bestsp; /* leaf bests table */
879 xfs_dir2_data_hdr_t *hdr; /* block header */
880 xfs_dir2_block_tail_t *btp; /* block tail */
881 xfs_inode_t *dp; /* incore directory inode */
882 xfs_dir2_data_unused_t *dup; /* unused data entry */
883 int error; /* error return value */
884 int from; /* leaf from index */
885 xfs_dir2_leaf_t *leaf; /* leaf structure */
886 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
887 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
888 xfs_mount_t *mp; /* file system mount point */
889 int needlog; /* need to log data header */
890 int needscan; /* need to scan for bestfree */
891 xfs_dir2_sf_hdr_t sfh; /* shortform header */
892 int size; /* bytes used */
893 __be16 *tagp; /* end of entry (tag) */
894 int to; /* block/leaf to index */
895 xfs_trans_t *tp; /* transaction pointer */
896
897 trace_xfs_dir2_leaf_to_block(args);
898
899 dp = args->dp;
900 tp = args->trans;
901 mp = dp->i_mount;
902 leaf = lbp->data;
903 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC));
904 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
905 /*
906 * If there are data blocks other than the first one, take this
907 * opportunity to remove trailing empty data blocks that may have
908 * been left behind during no-space-reservation operations.
909 * These will show up in the leaf bests table.
910 */
911 while (dp->i_d.di_size > mp->m_dirblksize) {
912 bestsp = xfs_dir2_leaf_bests_p(ltp);
913 if (be16_to_cpu(bestsp[be32_to_cpu(ltp->bestcount) - 1]) ==
914 mp->m_dirblksize - (uint)sizeof(*hdr)) {
915 if ((error =
916 xfs_dir2_leaf_trim_data(args, lbp,
917 (xfs_dir2_db_t)(be32_to_cpu(ltp->bestcount) - 1))))
918 goto out;
919 } else {
920 error = 0;
921 goto out;
922 }
923 }
924 /*
925 * Read the data block if we don't already have it, give up if it fails.
926 */
927 if (dbp == NULL &&
928 (error = xfs_da_read_buf(tp, dp, mp->m_dirdatablk, -1, &dbp,
929 XFS_DATA_FORK))) {
930 goto out;
931 }
932 hdr = dbp->data;
933 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC));
934 /*
935 * Size of the "leaf" area in the block.
936 */
937 size = (uint)sizeof(xfs_dir2_block_tail_t) +
938 (uint)sizeof(*lep) * (be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale));
939 /*
940 * Look at the last data entry.
941 */
942 tagp = (__be16 *)((char *)hdr + mp->m_dirblksize) - 1;
943 dup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
944 /*
945 * If it's not free or is too short we can't do it.
946 */
947 if (be16_to_cpu(dup->freetag) != XFS_DIR2_DATA_FREE_TAG ||
948 be16_to_cpu(dup->length) < size) {
949 error = 0;
950 goto out;
951 }
952 /*
953 * Start converting it to block form.
954 */
955 hdr->magic = cpu_to_be32(XFS_DIR2_BLOCK_MAGIC);
956 needlog = 1;
957 needscan = 0;
958 /*
959 * Use up the space at the end of the block (blp/btp).
960 */
961 xfs_dir2_data_use_free(tp, dbp, dup, mp->m_dirblksize - size, size,
962 &needlog, &needscan);
963 /*
964 * Initialize the block tail.
965 */
966 btp = xfs_dir2_block_tail_p(mp, hdr);
967 btp->count = cpu_to_be32(be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale));
968 btp->stale = 0;
969 xfs_dir2_block_log_tail(tp, dbp);
970 /*
971 * Initialize the block leaf area. We compact out stale entries.
972 */
973 lep = xfs_dir2_block_leaf_p(btp);
974 for (from = to = 0; from < be16_to_cpu(leaf->hdr.count); from++) {
975 if (leaf->ents[from].address ==
976 cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
977 continue;
978 lep[to++] = leaf->ents[from];
979 }
980 ASSERT(to == be32_to_cpu(btp->count));
981 xfs_dir2_block_log_leaf(tp, dbp, 0, be32_to_cpu(btp->count) - 1);
982 /*
983 * Scan the bestfree if we need it and log the data block header.
984 */
985 if (needscan)
986 xfs_dir2_data_freescan(mp, hdr, &needlog);
987 if (needlog)
988 xfs_dir2_data_log_header(tp, dbp);
989 /*
990 * Pitch the old leaf block.
991 */
992 error = xfs_da_shrink_inode(args, mp->m_dirleafblk, lbp);
993 lbp = NULL;
994 if (error) {
995 goto out;
996 }
997 /*
998 * Now see if the resulting block can be shrunken to shortform.
999 */
1000 size = xfs_dir2_block_sfsize(dp, hdr, &sfh);
1001 if (size > XFS_IFORK_DSIZE(dp)) {
1002 error = 0;
1003 goto out;
1004 }
1005 return xfs_dir2_block_to_sf(args, dbp, size, &sfh);
1006 out:
1007 if (lbp)
1008 xfs_da_buf_done(lbp);
1009 if (dbp)
1010 xfs_da_buf_done(dbp);
1011 return error;
1012 }
1013
1014 /*
1015 * Convert the shortform directory to block form.
1016 */
1017 int /* error */
1018 xfs_dir2_sf_to_block(
1019 xfs_da_args_t *args) /* operation arguments */
1020 {
1021 xfs_dir2_db_t blkno; /* dir-relative block # (0) */
1022 xfs_dir2_data_hdr_t *hdr; /* block header */
1023 xfs_dir2_leaf_entry_t *blp; /* block leaf entries */
1024 xfs_dabuf_t *bp; /* block buffer */
1025 xfs_dir2_block_tail_t *btp; /* block tail pointer */
1026 xfs_dir2_data_entry_t *dep; /* data entry pointer */
1027 xfs_inode_t *dp; /* incore directory inode */
1028 int dummy; /* trash */
1029 xfs_dir2_data_unused_t *dup; /* unused entry pointer */
1030 int endoffset; /* end of data objects */
1031 int error; /* error return value */
1032 int i; /* index */
1033 xfs_mount_t *mp; /* filesystem mount point */
1034 int needlog; /* need to log block header */
1035 int needscan; /* need to scan block freespc */
1036 int newoffset; /* offset from current entry */
1037 int offset; /* target block offset */
1038 xfs_dir2_sf_entry_t *sfep; /* sf entry pointer */
1039 xfs_dir2_sf_hdr_t *oldsfp; /* old shortform header */
1040 xfs_dir2_sf_hdr_t *sfp; /* shortform header */
1041 __be16 *tagp; /* end of data entry */
1042 xfs_trans_t *tp; /* transaction pointer */
1043 struct xfs_name name;
1044
1045 trace_xfs_dir2_sf_to_block(args);
1046
1047 dp = args->dp;
1048 tp = args->trans;
1049 mp = dp->i_mount;
1050 ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
1051 /*
1052 * Bomb out if the shortform directory is way too short.
1053 */
1054 if (dp->i_d.di_size < offsetof(xfs_dir2_sf_hdr_t, parent)) {
1055 ASSERT(XFS_FORCED_SHUTDOWN(mp));
1056 return XFS_ERROR(EIO);
1057 }
1058
1059 oldsfp = (xfs_dir2_sf_hdr_t *)dp->i_df.if_u1.if_data;
1060
1061 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
1062 ASSERT(dp->i_df.if_u1.if_data != NULL);
1063 ASSERT(dp->i_d.di_size >= xfs_dir2_sf_hdr_size(oldsfp->i8count));
1064
1065 /*
1066 * Copy the directory into a temporary buffer.
1067 * Then pitch the incore inode data so we can make extents.
1068 */
1069 sfp = kmem_alloc(dp->i_df.if_bytes, KM_SLEEP);
1070 memcpy(sfp, oldsfp, dp->i_df.if_bytes);
1071
1072 xfs_idata_realloc(dp, -dp->i_df.if_bytes, XFS_DATA_FORK);
1073 dp->i_d.di_size = 0;
1074 xfs_trans_log_inode(tp, dp, XFS_ILOG_CORE);
1075
1076 /*
1077 * Add block 0 to the inode.
1078 */
1079 error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE, &blkno);
1080 if (error) {
1081 kmem_free(sfp);
1082 return error;
1083 }
1084 /*
1085 * Initialize the data block.
1086 */
1087 error = xfs_dir2_data_init(args, blkno, &bp);
1088 if (error) {
1089 kmem_free(sfp);
1090 return error;
1091 }
1092 hdr = bp->data;
1093 hdr->magic = cpu_to_be32(XFS_DIR2_BLOCK_MAGIC);
1094 /*
1095 * Compute size of block "tail" area.
1096 */
1097 i = (uint)sizeof(*btp) +
1098 (sfp->count + 2) * (uint)sizeof(xfs_dir2_leaf_entry_t);
1099 /*
1100 * The whole thing is initialized to free by the init routine.
1101 * Say we're using the leaf and tail area.
1102 */
1103 dup = (xfs_dir2_data_unused_t *)(hdr + 1);
1104 needlog = needscan = 0;
1105 xfs_dir2_data_use_free(tp, bp, dup, mp->m_dirblksize - i, i, &needlog,
1106 &needscan);
1107 ASSERT(needscan == 0);
1108 /*
1109 * Fill in the tail.
1110 */
1111 btp = xfs_dir2_block_tail_p(mp, hdr);
1112 btp->count = cpu_to_be32(sfp->count + 2); /* ., .. */
1113 btp->stale = 0;
1114 blp = xfs_dir2_block_leaf_p(btp);
1115 endoffset = (uint)((char *)blp - (char *)hdr);
1116 /*
1117 * Remove the freespace, we'll manage it.
1118 */
1119 xfs_dir2_data_use_free(tp, bp, dup,
1120 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
1121 be16_to_cpu(dup->length), &needlog, &needscan);
1122 /*
1123 * Create entry for .
1124 */
1125 dep = (xfs_dir2_data_entry_t *)
1126 ((char *)hdr + XFS_DIR2_DATA_DOT_OFFSET);
1127 dep->inumber = cpu_to_be64(dp->i_ino);
1128 dep->namelen = 1;
1129 dep->name[0] = '.';
1130 tagp = xfs_dir2_data_entry_tag_p(dep);
1131 *tagp = cpu_to_be16((char *)dep - (char *)hdr);
1132 xfs_dir2_data_log_entry(tp, bp, dep);
1133 blp[0].hashval = cpu_to_be32(xfs_dir_hash_dot);
1134 blp[0].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(mp,
1135 (char *)dep - (char *)hdr));
1136 /*
1137 * Create entry for ..
1138 */
1139 dep = (xfs_dir2_data_entry_t *)
1140 ((char *)hdr + XFS_DIR2_DATA_DOTDOT_OFFSET);
1141 dep->inumber = cpu_to_be64(xfs_dir2_sf_get_parent_ino(sfp));
1142 dep->namelen = 2;
1143 dep->name[0] = dep->name[1] = '.';
1144 tagp = xfs_dir2_data_entry_tag_p(dep);
1145 *tagp = cpu_to_be16((char *)dep - (char *)hdr);
1146 xfs_dir2_data_log_entry(tp, bp, dep);
1147 blp[1].hashval = cpu_to_be32(xfs_dir_hash_dotdot);
1148 blp[1].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(mp,
1149 (char *)dep - (char *)hdr));
1150 offset = XFS_DIR2_DATA_FIRST_OFFSET;
1151 /*
1152 * Loop over existing entries, stuff them in.
1153 */
1154 i = 0;
1155 if (!sfp->count)
1156 sfep = NULL;
1157 else
1158 sfep = xfs_dir2_sf_firstentry(sfp);
1159 /*
1160 * Need to preserve the existing offset values in the sf directory.
1161 * Insert holes (unused entries) where necessary.
1162 */
1163 while (offset < endoffset) {
1164 /*
1165 * sfep is null when we reach the end of the list.
1166 */
1167 if (sfep == NULL)
1168 newoffset = endoffset;
1169 else
1170 newoffset = xfs_dir2_sf_get_offset(sfep);
1171 /*
1172 * There should be a hole here, make one.
1173 */
1174 if (offset < newoffset) {
1175 dup = (xfs_dir2_data_unused_t *)((char *)hdr + offset);
1176 dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
1177 dup->length = cpu_to_be16(newoffset - offset);
1178 *xfs_dir2_data_unused_tag_p(dup) = cpu_to_be16(
1179 ((char *)dup - (char *)hdr));
1180 xfs_dir2_data_log_unused(tp, bp, dup);
1181 xfs_dir2_data_freeinsert(hdr, dup, &dummy);
1182 offset += be16_to_cpu(dup->length);
1183 continue;
1184 }
1185 /*
1186 * Copy a real entry.
1187 */
1188 dep = (xfs_dir2_data_entry_t *)((char *)hdr + newoffset);
1189 dep->inumber = cpu_to_be64(xfs_dir2_sfe_get_ino(sfp, sfep));
1190 dep->namelen = sfep->namelen;
1191 memcpy(dep->name, sfep->name, dep->namelen);
1192 tagp = xfs_dir2_data_entry_tag_p(dep);
1193 *tagp = cpu_to_be16((char *)dep - (char *)hdr);
1194 xfs_dir2_data_log_entry(tp, bp, dep);
1195 name.name = sfep->name;
1196 name.len = sfep->namelen;
1197 blp[2 + i].hashval = cpu_to_be32(mp->m_dirnameops->
1198 hashname(&name));
1199 blp[2 + i].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(mp,
1200 (char *)dep - (char *)hdr));
1201 offset = (int)((char *)(tagp + 1) - (char *)hdr);
1202 if (++i == sfp->count)
1203 sfep = NULL;
1204 else
1205 sfep = xfs_dir2_sf_nextentry(sfp, sfep);
1206 }
1207 /* Done with the temporary buffer */
1208 kmem_free(sfp);
1209 /*
1210 * Sort the leaf entries by hash value.
1211 */
1212 xfs_sort(blp, be32_to_cpu(btp->count), sizeof(*blp), xfs_dir2_block_sort);
1213 /*
1214 * Log the leaf entry area and tail.
1215 * Already logged the header in data_init, ignore needlog.
1216 */
1217 ASSERT(needscan == 0);
1218 xfs_dir2_block_log_leaf(tp, bp, 0, be32_to_cpu(btp->count) - 1);
1219 xfs_dir2_block_log_tail(tp, bp);
1220 xfs_dir2_data_check(dp, bp);
1221 xfs_da_buf_done(bp);
1222 return 0;
1223 }
Linux kernel - Deliverables
This page took 0.056056 seconds and 5 git commands to generate.