1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
36
37STATIC int
38xfs_inobt_get_minrecs(
39 struct xfs_btree_cur *cur,
40 int level)
41{
42 return cur->bc_mp->m_inobt_mnr[level != 0];
43}
44
45STATIC struct xfs_btree_cur *
46xfs_inobt_dup_cursor(
47 struct xfs_btree_cur *cur)
48{
49 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
50 cur->bc_private.a.agbp, cur->bc_private.a.agno,
51 cur->bc_btnum);
52}
53
54STATIC void
55xfs_inobt_set_root(
56 struct xfs_btree_cur *cur,
57 union xfs_btree_ptr *nptr,
58 int inc)
59{
60 struct xfs_buf *agbp = cur->bc_private.a.agbp;
61 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
62
63 agi->agi_root = nptr->s;
64 be32_add_cpu(&agi->agi_level, inc);
65 xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
66}
67
68STATIC void
69xfs_finobt_set_root(
70 struct xfs_btree_cur *cur,
71 union xfs_btree_ptr *nptr,
72 int inc)
73{
74 struct xfs_buf *agbp = cur->bc_private.a.agbp;
75 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
76
77 agi->agi_free_root = nptr->s;
78 be32_add_cpu(&agi->agi_free_level, inc);
79 xfs_ialloc_log_agi(cur->bc_tp, agbp,
80 XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL);
81}
82
83STATIC int
84xfs_inobt_alloc_block(
85 struct xfs_btree_cur *cur,
86 union xfs_btree_ptr *start,
87 union xfs_btree_ptr *new,
88 int *stat)
89{
90 xfs_alloc_arg_t args;
91 int error;
92 xfs_agblock_t sbno = be32_to_cpu(start->s);
93
94 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
95
96 memset(&args, 0, sizeof(args));
97 args.tp = cur->bc_tp;
98 args.mp = cur->bc_mp;
99 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
100 args.minlen = 1;
101 args.maxlen = 1;
102 args.prod = 1;
103 args.type = XFS_ALLOCTYPE_NEAR_BNO;
104
105 error = xfs_alloc_vextent(&args);
106 if (error) {
107 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
108 return error;
109 }
110 if (args.fsbno == NULLFSBLOCK) {
111 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
112 *stat = 0;
113 return 0;
114 }
115 ASSERT(args.len == 1);
116 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
117
118 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
119 *stat = 1;
120 return 0;
121}
122
123STATIC int
124xfs_inobt_free_block(
125 struct xfs_btree_cur *cur,
126 struct xfs_buf *bp)
127{
128 return xfs_free_extent(cur->bc_tp,
129 XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)), 1);
130}
131
132STATIC int
133xfs_inobt_get_maxrecs(
134 struct xfs_btree_cur *cur,
135 int level)
136{
137 return cur->bc_mp->m_inobt_mxr[level != 0];
138}
139
140STATIC void
141xfs_inobt_init_key_from_rec(
142 union xfs_btree_key *key,
143 union xfs_btree_rec *rec)
144{
145 key->inobt.ir_startino = rec->inobt.ir_startino;
146}
147
148STATIC void
149xfs_inobt_init_rec_from_key(
150 union xfs_btree_key *key,
151 union xfs_btree_rec *rec)
152{
153 rec->inobt.ir_startino = key->inobt.ir_startino;
154}
155
156STATIC void
157xfs_inobt_init_rec_from_cur(
158 struct xfs_btree_cur *cur,
159 union xfs_btree_rec *rec)
160{
161 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
162 if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
163 rec->inobt.ir_u.sp.ir_holemask =
164 cpu_to_be16(cur->bc_rec.i.ir_holemask);
165 rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count;
166 rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount;
167 } else {
168
169 rec->inobt.ir_u.f.ir_freecount =
170 cpu_to_be32(cur->bc_rec.i.ir_freecount);
171 }
172 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
173}
174
175
176
177
178STATIC void
179xfs_inobt_init_ptr_from_cur(
180 struct xfs_btree_cur *cur,
181 union xfs_btree_ptr *ptr)
182{
183 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
184
185 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
186
187 ptr->s = agi->agi_root;
188}
189
190STATIC void
191xfs_finobt_init_ptr_from_cur(
192 struct xfs_btree_cur *cur,
193 union xfs_btree_ptr *ptr)
194{
195 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
196
197 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
198 ptr->s = agi->agi_free_root;
199}
200
201STATIC __int64_t
202xfs_inobt_key_diff(
203 struct xfs_btree_cur *cur,
204 union xfs_btree_key *key)
205{
206 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
207 cur->bc_rec.i.ir_startino;
208}
209
210static int
211xfs_inobt_verify(
212 struct xfs_buf *bp)
213{
214 struct xfs_mount *mp = bp->b_target->bt_mount;
215 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
216 unsigned int level;
217
218
219
220
221
222
223
224
225
226
227
228 switch (block->bb_magic) {
229 case cpu_to_be32(XFS_IBT_CRC_MAGIC):
230 case cpu_to_be32(XFS_FIBT_CRC_MAGIC):
231 if (!xfs_btree_sblock_v5hdr_verify(bp))
232 return false;
233
234 case cpu_to_be32(XFS_IBT_MAGIC):
235 case cpu_to_be32(XFS_FIBT_MAGIC):
236 break;
237 default:
238 return 0;
239 }
240
241
242 level = be16_to_cpu(block->bb_level);
243 if (level >= mp->m_in_maxlevels)
244 return false;
245
246 return xfs_btree_sblock_verify(bp, mp->m_inobt_mxr[level != 0]);
247}
248
249static void
250xfs_inobt_read_verify(
251 struct xfs_buf *bp)
252{
253 if (!xfs_btree_sblock_verify_crc(bp))
254 xfs_buf_ioerror(bp, -EFSBADCRC);
255 else if (!xfs_inobt_verify(bp))
256 xfs_buf_ioerror(bp, -EFSCORRUPTED);
257
258 if (bp->b_error) {
259 trace_xfs_btree_corrupt(bp, _RET_IP_);
260 xfs_verifier_error(bp);
261 }
262}
263
264static void
265xfs_inobt_write_verify(
266 struct xfs_buf *bp)
267{
268 if (!xfs_inobt_verify(bp)) {
269 trace_xfs_btree_corrupt(bp, _RET_IP_);
270 xfs_buf_ioerror(bp, -EFSCORRUPTED);
271 xfs_verifier_error(bp);
272 return;
273 }
274 xfs_btree_sblock_calc_crc(bp);
275
276}
277
278const struct xfs_buf_ops xfs_inobt_buf_ops = {
279 .name = "xfs_inobt",
280 .verify_read = xfs_inobt_read_verify,
281 .verify_write = xfs_inobt_write_verify,
282};
283
284#if defined(DEBUG) || defined(XFS_WARN)
285STATIC int
286xfs_inobt_keys_inorder(
287 struct xfs_btree_cur *cur,
288 union xfs_btree_key *k1,
289 union xfs_btree_key *k2)
290{
291 return be32_to_cpu(k1->inobt.ir_startino) <
292 be32_to_cpu(k2->inobt.ir_startino);
293}
294
295STATIC int
296xfs_inobt_recs_inorder(
297 struct xfs_btree_cur *cur,
298 union xfs_btree_rec *r1,
299 union xfs_btree_rec *r2)
300{
301 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
302 be32_to_cpu(r2->inobt.ir_startino);
303}
304#endif
305
306static const struct xfs_btree_ops xfs_inobt_ops = {
307 .rec_len = sizeof(xfs_inobt_rec_t),
308 .key_len = sizeof(xfs_inobt_key_t),
309
310 .dup_cursor = xfs_inobt_dup_cursor,
311 .set_root = xfs_inobt_set_root,
312 .alloc_block = xfs_inobt_alloc_block,
313 .free_block = xfs_inobt_free_block,
314 .get_minrecs = xfs_inobt_get_minrecs,
315 .get_maxrecs = xfs_inobt_get_maxrecs,
316 .init_key_from_rec = xfs_inobt_init_key_from_rec,
317 .init_rec_from_key = xfs_inobt_init_rec_from_key,
318 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
319 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
320 .key_diff = xfs_inobt_key_diff,
321 .buf_ops = &xfs_inobt_buf_ops,
322#if defined(DEBUG) || defined(XFS_WARN)
323 .keys_inorder = xfs_inobt_keys_inorder,
324 .recs_inorder = xfs_inobt_recs_inorder,
325#endif
326};
327
328static const struct xfs_btree_ops xfs_finobt_ops = {
329 .rec_len = sizeof(xfs_inobt_rec_t),
330 .key_len = sizeof(xfs_inobt_key_t),
331
332 .dup_cursor = xfs_inobt_dup_cursor,
333 .set_root = xfs_finobt_set_root,
334 .alloc_block = xfs_inobt_alloc_block,
335 .free_block = xfs_inobt_free_block,
336 .get_minrecs = xfs_inobt_get_minrecs,
337 .get_maxrecs = xfs_inobt_get_maxrecs,
338 .init_key_from_rec = xfs_inobt_init_key_from_rec,
339 .init_rec_from_key = xfs_inobt_init_rec_from_key,
340 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
341 .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur,
342 .key_diff = xfs_inobt_key_diff,
343 .buf_ops = &xfs_inobt_buf_ops,
344#if defined(DEBUG) || defined(XFS_WARN)
345 .keys_inorder = xfs_inobt_keys_inorder,
346 .recs_inorder = xfs_inobt_recs_inorder,
347#endif
348};
349
350
351
352
353struct xfs_btree_cur *
354xfs_inobt_init_cursor(
355 struct xfs_mount *mp,
356 struct xfs_trans *tp,
357 struct xfs_buf *agbp,
358 xfs_agnumber_t agno,
359 xfs_btnum_t btnum)
360{
361 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
362 struct xfs_btree_cur *cur;
363
364 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
365
366 cur->bc_tp = tp;
367 cur->bc_mp = mp;
368 cur->bc_btnum = btnum;
369 if (btnum == XFS_BTNUM_INO) {
370 cur->bc_nlevels = be32_to_cpu(agi->agi_level);
371 cur->bc_ops = &xfs_inobt_ops;
372 } else {
373 cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
374 cur->bc_ops = &xfs_finobt_ops;
375 }
376
377 cur->bc_blocklog = mp->m_sb.sb_blocklog;
378
379 if (xfs_sb_version_hascrc(&mp->m_sb))
380 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
381
382 cur->bc_private.a.agbp = agbp;
383 cur->bc_private.a.agno = agno;
384
385 return cur;
386}
387
388
389
390
391int
392xfs_inobt_maxrecs(
393 struct xfs_mount *mp,
394 int blocklen,
395 int leaf)
396{
397 blocklen -= XFS_INOBT_BLOCK_LEN(mp);
398
399 if (leaf)
400 return blocklen / sizeof(xfs_inobt_rec_t);
401 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
402}
403
404
405
406
407
408
409
410
411
412uint64_t
413xfs_inobt_irec_to_allocmask(
414 struct xfs_inobt_rec_incore *rec)
415{
416 uint64_t bitmap = 0;
417 uint64_t inodespbit;
418 int nextbit;
419 uint allocbitmap;
420
421
422
423
424
425
426 inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1;
427
428
429
430
431
432
433
434 allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1);
435
436
437
438
439
440
441
442 nextbit = xfs_next_bit(&allocbitmap, 1, 0);
443 while (nextbit != -1) {
444 ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY));
445
446 bitmap |= (inodespbit <<
447 (nextbit * XFS_INODES_PER_HOLEMASK_BIT));
448
449 nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1);
450 }
451
452 return bitmap;
453}
454
455#if defined(DEBUG) || defined(XFS_WARN)
456
457
458
459int
460xfs_inobt_rec_check_count(
461 struct xfs_mount *mp,
462 struct xfs_inobt_rec_incore *rec)
463{
464 int inocount = 0;
465 int nextbit = 0;
466 uint64_t allocbmap;
467 int wordsz;
468
469 wordsz = sizeof(allocbmap) / sizeof(unsigned int);
470 allocbmap = xfs_inobt_irec_to_allocmask(rec);
471
472 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit);
473 while (nextbit != -1) {
474 inocount++;
475 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz,
476 nextbit + 1);
477 }
478
479 if (inocount != rec->ir_count)
480 return -EFSCORRUPTED;
481
482 return 0;
483}
484#endif
485