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