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_sb.h"
26#include "xfs_ag.h"
27#include "xfs_mount.h"
28#include "xfs_inode.h"
29#include "xfs_btree.h"
30#include "xfs_ialloc.h"
31#include "xfs_ialloc_btree.h"
32#include "xfs_alloc.h"
33#include "xfs_error.h"
34#include "xfs_trace.h"
35#include "xfs_cksum.h"
36#include "xfs_trans.h"
37
38
39STATIC int
40xfs_inobt_get_minrecs(
41 struct xfs_btree_cur *cur,
42 int level)
43{
44 return cur->bc_mp->m_inobt_mnr[level != 0];
45}
46
47STATIC struct xfs_btree_cur *
48xfs_inobt_dup_cursor(
49 struct xfs_btree_cur *cur)
50{
51 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
52 cur->bc_private.a.agbp, cur->bc_private.a.agno,
53 cur->bc_btnum);
54}
55
56STATIC void
57xfs_inobt_set_root(
58 struct xfs_btree_cur *cur,
59 union xfs_btree_ptr *nptr,
60 int inc)
61{
62 struct xfs_buf *agbp = cur->bc_private.a.agbp;
63 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
64
65 agi->agi_root = nptr->s;
66 be32_add_cpu(&agi->agi_level, inc);
67 xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
68}
69
70STATIC void
71xfs_finobt_set_root(
72 struct xfs_btree_cur *cur,
73 union xfs_btree_ptr *nptr,
74 int inc)
75{
76 struct xfs_buf *agbp = cur->bc_private.a.agbp;
77 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
78
79 agi->agi_free_root = nptr->s;
80 be32_add_cpu(&agi->agi_free_level, inc);
81 xfs_ialloc_log_agi(cur->bc_tp, agbp,
82 XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL);
83}
84
85STATIC int
86xfs_inobt_alloc_block(
87 struct xfs_btree_cur *cur,
88 union xfs_btree_ptr *start,
89 union xfs_btree_ptr *new,
90 int *stat)
91{
92 xfs_alloc_arg_t args;
93 int error;
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 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
102 args.minlen = 1;
103 args.maxlen = 1;
104 args.prod = 1;
105 args.type = XFS_ALLOCTYPE_NEAR_BNO;
106
107 error = xfs_alloc_vextent(&args);
108 if (error) {
109 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
110 return error;
111 }
112 if (args.fsbno == NULLFSBLOCK) {
113 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
114 *stat = 0;
115 return 0;
116 }
117 ASSERT(args.len == 1);
118 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
119
120 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
121 *stat = 1;
122 return 0;
123}
124
125STATIC int
126xfs_inobt_free_block(
127 struct xfs_btree_cur *cur,
128 struct xfs_buf *bp)
129{
130 xfs_fsblock_t fsbno;
131 int error;
132
133 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp));
134 error = xfs_free_extent(cur->bc_tp, fsbno, 1);
135 if (error)
136 return error;
137
138 xfs_trans_binval(cur->bc_tp, bp);
139 return error;
140}
141
142STATIC int
143xfs_inobt_get_maxrecs(
144 struct xfs_btree_cur *cur,
145 int level)
146{
147 return cur->bc_mp->m_inobt_mxr[level != 0];
148}
149
150STATIC void
151xfs_inobt_init_key_from_rec(
152 union xfs_btree_key *key,
153 union xfs_btree_rec *rec)
154{
155 key->inobt.ir_startino = rec->inobt.ir_startino;
156}
157
158STATIC void
159xfs_inobt_init_rec_from_key(
160 union xfs_btree_key *key,
161 union xfs_btree_rec *rec)
162{
163 rec->inobt.ir_startino = key->inobt.ir_startino;
164}
165
166STATIC void
167xfs_inobt_init_rec_from_cur(
168 struct xfs_btree_cur *cur,
169 union xfs_btree_rec *rec)
170{
171 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
172 rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
173 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
174}
175
176
177
178
179STATIC void
180xfs_inobt_init_ptr_from_cur(
181 struct xfs_btree_cur *cur,
182 union xfs_btree_ptr *ptr)
183{
184 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
185
186 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
187
188 ptr->s = agi->agi_root;
189}
190
191STATIC void
192xfs_finobt_init_ptr_from_cur(
193 struct xfs_btree_cur *cur,
194 union xfs_btree_ptr *ptr)
195{
196 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
197
198 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
199 ptr->s = agi->agi_free_root;
200}
201
202STATIC __int64_t
203xfs_inobt_key_diff(
204 struct xfs_btree_cur *cur,
205 union xfs_btree_key *key)
206{
207 return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
208 cur->bc_rec.i.ir_startino;
209}
210
211static int
212xfs_inobt_verify(
213 struct xfs_buf *bp)
214{
215 struct xfs_mount *mp = bp->b_target->bt_mount;
216 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
217 struct xfs_perag *pag = bp->b_pag;
218 unsigned int level;
219
220
221
222
223
224
225
226
227
228
229
230 switch (block->bb_magic) {
231 case cpu_to_be32(XFS_IBT_CRC_MAGIC):
232 case cpu_to_be32(XFS_FIBT_CRC_MAGIC):
233 if (!xfs_sb_version_hascrc(&mp->m_sb))
234 return false;
235 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid))
236 return false;
237 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
238 return false;
239 if (pag &&
240 be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
241 return false;
242
243 case cpu_to_be32(XFS_IBT_MAGIC):
244 case cpu_to_be32(XFS_FIBT_MAGIC):
245 break;
246 default:
247 return 0;
248 }
249
250
251 level = be16_to_cpu(block->bb_level);
252 if (level >= mp->m_in_maxlevels)
253 return false;
254 if (be16_to_cpu(block->bb_numrecs) > mp->m_inobt_mxr[level != 0])
255 return false;
256
257
258 if (!block->bb_u.s.bb_leftsib ||
259 (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks &&
260 block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK)))
261 return false;
262 if (!block->bb_u.s.bb_rightsib ||
263 (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks &&
264 block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK)))
265 return false;
266
267 return true;
268}
269
270static void
271xfs_inobt_read_verify(
272 struct xfs_buf *bp)
273{
274 if (!xfs_btree_sblock_verify_crc(bp))
275 xfs_buf_ioerror(bp, -EFSBADCRC);
276 else if (!xfs_inobt_verify(bp))
277 xfs_buf_ioerror(bp, -EFSCORRUPTED);
278
279 if (bp->b_error) {
280 trace_xfs_btree_corrupt(bp, _RET_IP_);
281 xfs_verifier_error(bp);
282 }
283}
284
285static void
286xfs_inobt_write_verify(
287 struct xfs_buf *bp)
288{
289 if (!xfs_inobt_verify(bp)) {
290 trace_xfs_btree_corrupt(bp, _RET_IP_);
291 xfs_buf_ioerror(bp, -EFSCORRUPTED);
292 xfs_verifier_error(bp);
293 return;
294 }
295 xfs_btree_sblock_calc_crc(bp);
296
297}
298
299const struct xfs_buf_ops xfs_inobt_buf_ops = {
300 .verify_read = xfs_inobt_read_verify,
301 .verify_write = xfs_inobt_write_verify,
302};
303
304#if defined(DEBUG) || defined(XFS_WARN)
305STATIC int
306xfs_inobt_keys_inorder(
307 struct xfs_btree_cur *cur,
308 union xfs_btree_key *k1,
309 union xfs_btree_key *k2)
310{
311 return be32_to_cpu(k1->inobt.ir_startino) <
312 be32_to_cpu(k2->inobt.ir_startino);
313}
314
315STATIC int
316xfs_inobt_recs_inorder(
317 struct xfs_btree_cur *cur,
318 union xfs_btree_rec *r1,
319 union xfs_btree_rec *r2)
320{
321 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
322 be32_to_cpu(r2->inobt.ir_startino);
323}
324#endif
325
326static const struct xfs_btree_ops xfs_inobt_ops = {
327 .rec_len = sizeof(xfs_inobt_rec_t),
328 .key_len = sizeof(xfs_inobt_key_t),
329
330 .dup_cursor = xfs_inobt_dup_cursor,
331 .set_root = xfs_inobt_set_root,
332 .alloc_block = xfs_inobt_alloc_block,
333 .free_block = xfs_inobt_free_block,
334 .get_minrecs = xfs_inobt_get_minrecs,
335 .get_maxrecs = xfs_inobt_get_maxrecs,
336 .init_key_from_rec = xfs_inobt_init_key_from_rec,
337 .init_rec_from_key = xfs_inobt_init_rec_from_key,
338 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
339 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur,
340 .key_diff = xfs_inobt_key_diff,
341 .buf_ops = &xfs_inobt_buf_ops,
342#if defined(DEBUG) || defined(XFS_WARN)
343 .keys_inorder = xfs_inobt_keys_inorder,
344 .recs_inorder = xfs_inobt_recs_inorder,
345#endif
346};
347
348static const struct xfs_btree_ops xfs_finobt_ops = {
349 .rec_len = sizeof(xfs_inobt_rec_t),
350 .key_len = sizeof(xfs_inobt_key_t),
351
352 .dup_cursor = xfs_inobt_dup_cursor,
353 .set_root = xfs_finobt_set_root,
354 .alloc_block = xfs_inobt_alloc_block,
355 .free_block = xfs_inobt_free_block,
356 .get_minrecs = xfs_inobt_get_minrecs,
357 .get_maxrecs = xfs_inobt_get_maxrecs,
358 .init_key_from_rec = xfs_inobt_init_key_from_rec,
359 .init_rec_from_key = xfs_inobt_init_rec_from_key,
360 .init_rec_from_cur = xfs_inobt_init_rec_from_cur,
361 .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur,
362 .key_diff = xfs_inobt_key_diff,
363 .buf_ops = &xfs_inobt_buf_ops,
364#if defined(DEBUG) || defined(XFS_WARN)
365 .keys_inorder = xfs_inobt_keys_inorder,
366 .recs_inorder = xfs_inobt_recs_inorder,
367#endif
368};
369
370
371
372
373struct xfs_btree_cur *
374xfs_inobt_init_cursor(
375 struct xfs_mount *mp,
376 struct xfs_trans *tp,
377 struct xfs_buf *agbp,
378 xfs_agnumber_t agno,
379 xfs_btnum_t btnum)
380{
381 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp);
382 struct xfs_btree_cur *cur;
383
384 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
385
386 cur->bc_tp = tp;
387 cur->bc_mp = mp;
388 cur->bc_btnum = btnum;
389 if (btnum == XFS_BTNUM_INO) {
390 cur->bc_nlevels = be32_to_cpu(agi->agi_level);
391 cur->bc_ops = &xfs_inobt_ops;
392 } else {
393 cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
394 cur->bc_ops = &xfs_finobt_ops;
395 }
396
397 cur->bc_blocklog = mp->m_sb.sb_blocklog;
398
399 if (xfs_sb_version_hascrc(&mp->m_sb))
400 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
401
402 cur->bc_private.a.agbp = agbp;
403 cur->bc_private.a.agno = agno;
404
405 return cur;
406}
407
408
409
410
411int
412xfs_inobt_maxrecs(
413 struct xfs_mount *mp,
414 int blocklen,
415 int leaf)
416{
417 blocklen -= XFS_INOBT_BLOCK_LEN(mp);
418
419 if (leaf)
420 return blocklen / sizeof(xfs_inobt_rec_t);
421 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
422}
423
