?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
KVM: PPC: Book3S: Fix compile error that occurs with some gcc versions
[linux/fpc-iii.git] / fs / xfs / libxfs / xfs_ialloc_btree.c
blobaf197a5f3a82e622c2dea38a9a2b33aaaf676b66
1 /*
2 * Copyright (c) 2000-2001,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_shared.h"
21 #include "xfs_format.h"
22 #include "xfs_log_format.h"
23 #include "xfs_trans_resv.h"
24 #include "xfs_bit.h"
25 #include "xfs_mount.h"
26 #include "xfs_inode.h"
27 #include "xfs_btree.h"
28 #include "xfs_ialloc.h"
29 #include "xfs_ialloc_btree.h"
30 #include "xfs_alloc.h"
31 #include "xfs_error.h"
32 #include "xfs_trace.h"
33 #include "xfs_cksum.h"
34 #include "xfs_trans.h"
35 #include "xfs_rmap.h"
36
37
38 STATIC int
39 xfs_inobt_get_minrecs(
40 struct xfs_btree_cur *cur,
41 int level)
42 {
43 return cur->bc_mp->m_inobt_mnr[level != 0];
44 }
45
46 STATIC struct xfs_btree_cur *
47 xfs_inobt_dup_cursor(
48 struct xfs_btree_cur *cur)
49 {
50 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
51 cur->bc_private.a.agbp, cur->bc_private.a.agno,
52 cur->bc_btnum);
53 }
54
55 STATIC void
56 xfs_inobt_set_root(
57 struct xfs_btree_cur *cur,
58 union xfs_btree_ptr *nptr,
59 int inc) /* level change */
60 {
61 struct xfs_buf *agbp = cur->bc_private.a.agbp;
62 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
63
64 agi->agi_root = nptr->s;
65 be32_add_cpu(&agi->agi_level, inc);
66 xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
67 }
68
69 STATIC void
70 xfs_finobt_set_root(
71 struct xfs_btree_cur *cur,
72 union xfs_btree_ptr *nptr,
73 int inc) /* level change */
74 {
75 struct xfs_buf *agbp = cur->bc_private.a.agbp;
76 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
77
78 agi->agi_free_root = nptr->s;
79 be32_add_cpu(&agi->agi_free_level, inc);
80 xfs_ialloc_log_agi(cur->bc_tp, agbp,
81 XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL);
82 }
83
84 STATIC int
85 __xfs_inobt_alloc_block(
86 struct xfs_btree_cur *cur,
87 union xfs_btree_ptr *start,
88 union xfs_btree_ptr *new,
89 int *stat,
90 enum xfs_ag_resv_type resv)
91 {
92 xfs_alloc_arg_t args; /* block allocation args */
93 int error; /* error return value */
94 xfs_agblock_t sbno = be32_to_cpu(start->s);
95
96 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
97
98 memset(&args, 0, sizeof(args));
99 args.tp = cur->bc_tp;
100 args.mp = cur->bc_mp;
101 xfs_rmap_ag_owner(&args.oinfo, XFS_RMAP_OWN_INOBT);
102 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
103 args.minlen = 1;
104 args.maxlen = 1;
105 args.prod = 1;
106 args.type = XFS_ALLOCTYPE_NEAR_BNO;
107 args.resv = resv;
108
109 error = xfs_alloc_vextent(&args);
110 if (error) {
111 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
112 return error;
113 }
114 if (args.fsbno == NULLFSBLOCK) {
115 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
116 *stat = 0;
117 return 0;
118 }
119 ASSERT(args.len == 1);
120 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
121
122 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
123 *stat = 1;
124 return 0;
125 }
126
127 STATIC int
128 xfs_inobt_alloc_block(
129 struct xfs_btree_cur *cur,
130 union xfs_btree_ptr *start,
131 union xfs_btree_ptr *new,
132 int *stat)
133 {
134 return __xfs_inobt_alloc_block(cur, start, new, stat, XFS_AG_RESV_NONE);
135 }
136
137 STATIC int
138 xfs_finobt_alloc_block(
139 struct xfs_btree_cur *cur,
140 union xfs_btree_ptr *start,
141 union xfs_btree_ptr *new,
142 int *stat)
143 {
144 if (cur->bc_mp->m_inotbt_nores)
145 return xfs_inobt_alloc_block(cur, start, new, stat);
146 return __xfs_inobt_alloc_block(cur, start, new, stat,
147 XFS_AG_RESV_METADATA);
148 }
149
150 STATIC int
151 __xfs_inobt_free_block(
152 struct xfs_btree_cur *cur,
153 struct xfs_buf *bp,
154 enum xfs_ag_resv_type resv)
155 {
156 struct xfs_owner_info oinfo;
157
158 xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_INOBT);
159 return xfs_free_extent(cur->bc_tp,
160 XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)), 1,
161 &oinfo, resv);
162 }
163
164 STATIC int
165 xfs_inobt_free_block(
166 struct xfs_btree_cur *cur,
167 struct xfs_buf *bp)
168 {
169 return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_NONE);
170 }
171
172 STATIC int
173 xfs_finobt_free_block(
174 struct xfs_btree_cur *cur,
175 struct xfs_buf *bp)
176 {
177 if (cur->bc_mp->m_inotbt_nores)
178 return xfs_inobt_free_block(cur, bp);
179 return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_METADATA);
180 }
181
182 STATIC int
183 xfs_inobt_get_maxrecs(
184 struct xfs_btree_cur *cur,
185 int level)
186 {
187 return cur->bc_mp->m_inobt_mxr[level != 0];
188 }
189
190 STATIC void
191 xfs_inobt_init_key_from_rec(
192 union xfs_btree_key *key,
193 union xfs_btree_rec *rec)
194 {
195 key->inobt.ir_startino = rec->inobt.ir_startino;
196 }
197
198 STATIC void
199 xfs_inobt_init_high_key_from_rec(
200 union xfs_btree_key *key,
201 union xfs_btree_rec *rec)
202 {
203 __u32 x;
204
205 x = be32_to_cpu(rec->inobt.ir_startino);
206 x += XFS_INODES_PER_CHUNK - 1;
207 key->inobt.ir_startino = cpu_to_be32(x);
208 }
209
210 STATIC void
211 xfs_inobt_init_rec_from_cur(
212 struct xfs_btree_cur *cur,
213 union xfs_btree_rec *rec)
214 {
215 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
216 if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
217 rec->inobt.ir_u.sp.ir_holemask =
218 cpu_to_be16(cur->bc_rec.i.ir_holemask);
219 rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count;
220 rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount;
221 } else {
222 /* ir_holemask/ir_count not supported on-disk */
223 rec->inobt.ir_u.f.ir_freecount =
224 cpu_to_be32(cur->bc_rec.i.ir_freecount);
225 }
226 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
227 }
228
229 /*
230 * initial value of ptr for lookup
231 */
232 STATIC void
233 xfs_inobt_init_ptr_from_cur(
234 struct xfs_btree_cur *cur,
235 union xfs_btree_ptr *ptr)
236 {
237 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
238
239 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
240
241 ptr->s = agi->agi_root;
242 }
243
244 STATIC void
245 xfs_finobt_init_ptr_from_cur(
246 struct xfs_btree_cur *cur,
247 union xfs_btree_ptr *ptr)
248 {
249 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
250
251 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
252 ptr->s = agi->agi_free_root;
253 }
254
255 STATIC int64_t
256 xfs_inobt_key_diff(
257 struct xfs_btree_cur *cur,
258 union xfs_btree_key *key)
259 {
260 return (int64_t)be32_to_cpu(key->inobt.ir_startino) -
261 cur->bc_rec.i.ir_startino;
262 }
263
264 STATIC int64_t
265 xfs_inobt_diff_two_keys(
266 struct xfs_btree_cur *cur,
267 union xfs_btree_key *k1,
268 union xfs_btree_key *k2)
269 {
270 return (int64_t)be32_to_cpu(k1->inobt.ir_startino) -
271 be32_to_cpu(k2->inobt.ir_startino);
272 }
273
274 static xfs_failaddr_t
275 xfs_inobt_verify(
276 struct xfs_buf *bp)
277 {
278 struct xfs_mount *mp = bp->b_target->bt_mount;
279 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
280 xfs_failaddr_t fa;
281 unsigned int level;
282
283 /*
284 * During growfs operations, we can't verify the exact owner as the
285 * perag is not fully initialised and hence not attached to the buffer.
286 *
287 * Similarly, during log recovery we will have a perag structure
288 * attached, but the agi information will not yet have been initialised
289 * from the on disk AGI. We don't currently use any of this information,
290 * but beware of the landmine (i.e. need to check pag->pagi_init) if we
291 * ever do.
292 */
293 switch (block->bb_magic) {
294 case cpu_to_be32(XFS_IBT_CRC_MAGIC):
295 case cpu_to_be32(XFS_FIBT_CRC_MAGIC):
296 fa = xfs_btree_sblock_v5hdr_verify(bp);
297 if (fa)
298 return fa;
299 /* fall through */
300 case cpu_to_be32(XFS_IBT_MAGIC):
301 case cpu_to_be32(XFS_FIBT_MAGIC):
302 break;
303 default:
304 return NULL;
305 }
306
307 /* level verification */
308 level = be16_to_cpu(block->bb_level);
309 if (level >= mp->m_in_maxlevels)
310 return __this_address;
311
312 return xfs_btree_sblock_verify(bp, mp->m_inobt_mxr[level != 0]);
313 }
314
315 static void
316 xfs_inobt_read_verify(
317 struct xfs_buf *bp)
318 {
319 xfs_failaddr_t fa;
320
321 if (!xfs_btree_sblock_verify_crc(bp))
322 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
323 else {
324 fa = xfs_inobt_verify(bp);
325 if (fa)
326 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
327 }
328
329 if (bp->b_error)
330 trace_xfs_btree_corrupt(bp, _RET_IP_);
331 }
332
333 static void
334 xfs_inobt_write_verify(
335 struct xfs_buf *bp)
336 {
337 xfs_failaddr_t fa;
338
339 fa = xfs_inobt_verify(bp);
340 if (fa) {
341 trace_xfs_btree_corrupt(bp, _RET_IP_);
342 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
343 return;
344 }
345 xfs_btree_sblock_calc_crc(bp);
346
347 }
348
349 const struct xfs_buf_ops xfs_inobt_buf_ops = {
350 .name = "xfs_inobt",
351 .verify_read = xfs_inobt_read_verify,
352 .verify_write = xfs_inobt_write_verify,
353 .verify_struct = xfs_inobt_verify,
354 };
355
356 STATIC int
357 xfs_inobt_keys_inorder(
358 struct xfs_btree_cur *cur,
359 union xfs_btree_key *k1,
360 union xfs_btree_key *k2)
361 {
362 return be32_to_cpu(k1->inobt.ir_startino) <
363 be32_to_cpu(k2->inobt.ir_startino);
364 }
365
366 STATIC int
367 xfs_inobt_recs_inorder(
368 struct xfs_btree_cur *cur,
369 union xfs_btree_rec *r1,
370 union xfs_btree_rec *r2)
371 {
372 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
373 be32_to_cpu(r2->inobt.ir_startino);
374 }
375
376 static const struct xfs_btree_ops xfs_inobt_ops = {
377 .rec_len = sizeof(xfs_inobt_rec_t),
378 .key_len = sizeof(xfs_inobt_key_t),
379
380 .dup_cursor = xfs_inobt_dup_cursor,
381 .set_root = xfs_inobt_set_root,
382 .alloc_block = xfs_inobt_alloc_block,
383 .free_block = xfs_inobt_free_block,
384 .get_minrecs = xfs_inobt_get_minrecs,
385 .get_maxrecs = xfs_inobt_get_maxrecs,
386 .init_key_from_rec = xfs_inobt_init_key_from_rec,
387 .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec,
388 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
389 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
390 .key_diff = xfs_inobt_key_diff,
391 .buf_ops = &xfs_inobt_buf_ops,
392 .diff_two_keys = xfs_inobt_diff_two_keys,
393 .keys_inorder = xfs_inobt_keys_inorder,
394 .recs_inorder = xfs_inobt_recs_inorder,
395 };
396
397 static const struct xfs_btree_ops xfs_finobt_ops = {
398 .rec_len = sizeof(xfs_inobt_rec_t),
399 .key_len = sizeof(xfs_inobt_key_t),
400
401 .dup_cursor = xfs_inobt_dup_cursor,
402 .set_root = xfs_finobt_set_root,
403 .alloc_block = xfs_finobt_alloc_block,
404 .free_block = xfs_finobt_free_block,
405 .get_minrecs = xfs_inobt_get_minrecs,
406 .get_maxrecs = xfs_inobt_get_maxrecs,
407 .init_key_from_rec = xfs_inobt_init_key_from_rec,
408 .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec,
409 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
410 .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur,
411 .key_diff = xfs_inobt_key_diff,
412 .buf_ops = &xfs_inobt_buf_ops,
413 .diff_two_keys = xfs_inobt_diff_two_keys,
414 .keys_inorder = xfs_inobt_keys_inorder,
415 .recs_inorder = xfs_inobt_recs_inorder,
416 };
417
418 /*
419 * Allocate a new inode btree cursor.
420 */
421 struct xfs_btree_cur * /* new inode btree cursor */
422 xfs_inobt_init_cursor(
423 struct xfs_mount *mp, /* file system mount point */
424 struct xfs_trans *tp, /* transaction pointer */
425 struct xfs_buf *agbp, /* buffer for agi structure */
426 xfs_agnumber_t agno, /* allocation group number */
427 xfs_btnum_t btnum) /* ialloc or free ino btree */
428 {
429 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
430 struct xfs_btree_cur *cur;
431
432 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
433
434 cur->bc_tp = tp;
435 cur->bc_mp = mp;
436 cur->bc_btnum = btnum;
437 if (btnum == XFS_BTNUM_INO) {
438 cur->bc_nlevels = be32_to_cpu(agi->agi_level);
439 cur->bc_ops = &xfs_inobt_ops;
440 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_ibt_2);
441 } else {
442 cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
443 cur->bc_ops = &xfs_finobt_ops;
444 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_fibt_2);
445 }
446
447 cur->bc_blocklog = mp->m_sb.sb_blocklog;
448
449 if (xfs_sb_version_hascrc(&mp->m_sb))
450 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
451
452 cur->bc_private.a.agbp = agbp;
453 cur->bc_private.a.agno = agno;
454
455 return cur;
456 }
457
458 /*
459 * Calculate number of records in an inobt btree block.
460 */
461 int
462 xfs_inobt_maxrecs(
463 struct xfs_mount *mp,
464 int blocklen,
465 int leaf)
466 {
467 blocklen -= XFS_INOBT_BLOCK_LEN(mp);
468
469 if (leaf)
470 return blocklen / sizeof(xfs_inobt_rec_t);
471 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
472 }
473
474 /*
475 * Convert the inode record holemask to an inode allocation bitmap. The inode
476 * allocation bitmap is inode granularity and specifies whether an inode is
477 * physically allocated on disk (not whether the inode is considered allocated
478 * or free by the fs).
479 *
480 * A bit value of 1 means the inode is allocated, a value of 0 means it is free.
481 */
482 uint64_t
483 xfs_inobt_irec_to_allocmask(
484 struct xfs_inobt_rec_incore *rec)
485 {
486 uint64_t bitmap = 0;
487 uint64_t inodespbit;
488 int nextbit;
489 uint allocbitmap;
490
491 /*
492 * The holemask has 16-bits for a 64 inode record. Therefore each
493 * holemask bit represents multiple inodes. Create a mask of bits to set
494 * in the allocmask for each holemask bit.
495 */
496 inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1;
497
498 /*
499 * Allocated inodes are represented by 0 bits in holemask. Invert the 0
500 * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask
501 * anything beyond the 16 holemask bits since this casts to a larger
502 * type.
503 */
504 allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1);
505
506 /*
507 * allocbitmap is the inverted holemask so every set bit represents
508 * allocated inodes. To expand from 16-bit holemask granularity to
509 * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target
510 * bitmap for every holemask bit.
511 */
512 nextbit = xfs_next_bit(&allocbitmap, 1, 0);
513 while (nextbit != -1) {
514 ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY));
515
516 bitmap |= (inodespbit <<
517 (nextbit * XFS_INODES_PER_HOLEMASK_BIT));
518
519 nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1);
520 }
521
522 return bitmap;
523 }
524
525 #if defined(DEBUG) || defined(XFS_WARN)
526 /*
527 * Verify that an in-core inode record has a valid inode count.
528 */
529 int
530 xfs_inobt_rec_check_count(
531 struct xfs_mount *mp,
532 struct xfs_inobt_rec_incore *rec)
533 {
534 int inocount = 0;
535 int nextbit = 0;
536 uint64_t allocbmap;
537 int wordsz;
538
539 wordsz = sizeof(allocbmap) / sizeof(unsigned int);
540 allocbmap = xfs_inobt_irec_to_allocmask(rec);
541
542 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit);
543 while (nextbit != -1) {
544 inocount++;
545 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz,
546 nextbit + 1);
547 }
548
549 if (inocount != rec->ir_count)
550 return -EFSCORRUPTED;
551
552 return 0;
553 }
554 #endif /* DEBUG */
555
556 static xfs_extlen_t
557 xfs_inobt_max_size(
558 struct xfs_mount *mp)
559 {
560 /* Bail out if we're uninitialized, which can happen in mkfs. */
561 if (mp->m_inobt_mxr[0] == 0)
562 return 0;
563
564 return xfs_btree_calc_size(mp, mp->m_inobt_mnr,
565 (uint64_t)mp->m_sb.sb_agblocks * mp->m_sb.sb_inopblock /
566 XFS_INODES_PER_CHUNK);
567 }
568
569 static int
570 xfs_inobt_count_blocks(
571 struct xfs_mount *mp,
572 xfs_agnumber_t agno,
573 xfs_btnum_t btnum,
574 xfs_extlen_t *tree_blocks)
575 {
576 struct xfs_buf *agbp;
577 struct xfs_btree_cur *cur;
578 int error;
579
580 error = xfs_ialloc_read_agi(mp, NULL, agno, &agbp);
581 if (error)
582 return error;
583
584 cur = xfs_inobt_init_cursor(mp, NULL, agbp, agno, btnum);
585 error = xfs_btree_count_blocks(cur, tree_blocks);
586 xfs_btree_del_cursor(cur, error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR);
587 xfs_buf_relse(agbp);
588
589 return error;
590 }
591
592 /*
593 * Figure out how many blocks to reserve and how many are used by this btree.
594 */
595 int
596 xfs_finobt_calc_reserves(
597 struct xfs_mount *mp,
598 xfs_agnumber_t agno,
599 xfs_extlen_t *ask,
600 xfs_extlen_t *used)
601 {
602 xfs_extlen_t tree_len = 0;
603 int error;
604
605 if (!xfs_sb_version_hasfinobt(&mp->m_sb))
606 return 0;
607
608 error = xfs_inobt_count_blocks(mp, agno, XFS_BTNUM_FINO, &tree_len);
609 if (error)
610 return error;
611
612 *ask += xfs_inobt_max_size(mp);
613 *used += tree_len;
614 return 0;
615 }
Linux with added FPC-III support