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_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_bmap_btree.h"
27#include "xfs_alloc_btree.h"
28#include "xfs_ialloc_btree.h"
29#include "xfs_dinode.h"
30#include "xfs_inode.h"
31#include "xfs_btree.h"
32#include "xfs_alloc.h"
33#include "xfs_extent_busy.h"
34#include "xfs_error.h"
35#include "xfs_trace.h"
36#include "xfs_cksum.h"
37
38
39STATIC struct xfs_btree_cur *
40xfs_allocbt_dup_cursor(
41 struct xfs_btree_cur *cur)
42{
43 return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp,
44 cur->bc_private.a.agbp, cur->bc_private.a.agno,
45 cur->bc_btnum);
46}
47
48STATIC void
49xfs_allocbt_set_root(
50 struct xfs_btree_cur *cur,
51 union xfs_btree_ptr *ptr,
52 int inc)
53{
54 struct xfs_buf *agbp = cur->bc_private.a.agbp;
55 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
56 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno);
57 int btnum = cur->bc_btnum;
58 struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno);
59
60 ASSERT(ptr->s != 0);
61
62 agf->agf_roots[btnum] = ptr->s;
63 be32_add_cpu(&agf->agf_levels[btnum], inc);
64 pag->pagf_levels[btnum] += inc;
65 xfs_perag_put(pag);
66
67 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
68}
69
70STATIC int
71xfs_allocbt_alloc_block(
72 struct xfs_btree_cur *cur,
73 union xfs_btree_ptr *start,
74 union xfs_btree_ptr *new,
75 int length,
76 int *stat)
77{
78 int error;
79 xfs_agblock_t bno;
80
81 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
82
83
84 error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
85 &bno, 1);
86 if (error) {
87 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
88 return error;
89 }
90
91 if (bno == NULLAGBLOCK) {
92 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
93 *stat = 0;
94 return 0;
95 }
96
97 xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, false);
98
99 xfs_trans_agbtree_delta(cur->bc_tp, 1);
100 new->s = cpu_to_be32(bno);
101
102 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
103 *stat = 1;
104 return 0;
105}
106
107STATIC int
108xfs_allocbt_free_block(
109 struct xfs_btree_cur *cur,
110 struct xfs_buf *bp)
111{
112 struct xfs_buf *agbp = cur->bc_private.a.agbp;
113 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
114 xfs_agblock_t bno;
115 int error;
116
117 bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp));
118 error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1);
119 if (error)
120 return error;
121
122 xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1,
123 XFS_EXTENT_BUSY_SKIP_DISCARD);
124 xfs_trans_agbtree_delta(cur->bc_tp, -1);
125
126 xfs_trans_binval(cur->bc_tp, bp);
127 return 0;
128}
129
130
131
132
133STATIC void
134xfs_allocbt_update_lastrec(
135 struct xfs_btree_cur *cur,
136 struct xfs_btree_block *block,
137 union xfs_btree_rec *rec,
138 int ptr,
139 int reason)
140{
141 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
142 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno);
143 struct xfs_perag *pag;
144 __be32 len;
145 int numrecs;
146
147 ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
148
149 switch (reason) {
150 case LASTREC_UPDATE:
151
152
153
154
155 if (ptr != xfs_btree_get_numrecs(block))
156 return;
157 len = rec->alloc.ar_blockcount;
158 break;
159 case LASTREC_INSREC:
160 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
161 be32_to_cpu(agf->agf_longest))
162 return;
163 len = rec->alloc.ar_blockcount;
164 break;
165 case LASTREC_DELREC:
166 numrecs = xfs_btree_get_numrecs(block);
167 if (ptr <= numrecs)
168 return;
169 ASSERT(ptr == numrecs + 1);
170
171 if (numrecs) {
172 xfs_alloc_rec_t *rrp;
173
174 rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs);
175 len = rrp->ar_blockcount;
176 } else {
177 len = 0;
178 }
179
180 break;
181 default:
182 ASSERT(0);
183 return;
184 }
185
186 agf->agf_longest = len;
187 pag = xfs_perag_get(cur->bc_mp, seqno);
188 pag->pagf_longest = be32_to_cpu(len);
189 xfs_perag_put(pag);
190 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST);
191}
192
193STATIC int
194xfs_allocbt_get_minrecs(
195 struct xfs_btree_cur *cur,
196 int level)
197{
198 return cur->bc_mp->m_alloc_mnr[level != 0];
199}
200
201STATIC int
202xfs_allocbt_get_maxrecs(
203 struct xfs_btree_cur *cur,
204 int level)
205{
206 return cur->bc_mp->m_alloc_mxr[level != 0];
207}
208
209STATIC void
210xfs_allocbt_init_key_from_rec(
211 union xfs_btree_key *key,
212 union xfs_btree_rec *rec)
213{
214 ASSERT(rec->alloc.ar_startblock != 0);
215
216 key->alloc.ar_startblock = rec->alloc.ar_startblock;
217 key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
218}
219
220STATIC void
221xfs_allocbt_init_rec_from_key(
222 union xfs_btree_key *key,
223 union xfs_btree_rec *rec)
224{
225 ASSERT(key->alloc.ar_startblock != 0);
226
227 rec->alloc.ar_startblock = key->alloc.ar_startblock;
228 rec->alloc.ar_blockcount = key->alloc.ar_blockcount;
229}
230
231STATIC void
232xfs_allocbt_init_rec_from_cur(
233 struct xfs_btree_cur *cur,
234 union xfs_btree_rec *rec)
235{
236 ASSERT(cur->bc_rec.a.ar_startblock != 0);
237
238 rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
239 rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
240}
241
242STATIC void
243xfs_allocbt_init_ptr_from_cur(
244 struct xfs_btree_cur *cur,
245 union xfs_btree_ptr *ptr)
246{
247 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
248
249 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
250 ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
251
252 ptr->s = agf->agf_roots[cur->bc_btnum];
253}
254
255STATIC __int64_t
256xfs_allocbt_key_diff(
257 struct xfs_btree_cur *cur,
258 union xfs_btree_key *key)
259{
260 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a;
261 xfs_alloc_key_t *kp = &key->alloc;
262 __int64_t diff;
263
264 if (cur->bc_btnum == XFS_BTNUM_BNO) {
265 return (__int64_t)be32_to_cpu(kp->ar_startblock) -
266 rec->ar_startblock;
267 }
268
269 diff = (__int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
270 if (diff)
271 return diff;
272
273 return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
274}
275
276static bool
277xfs_allocbt_verify(
278 struct xfs_buf *bp)
279{
280 struct xfs_mount *mp = bp->b_target->bt_mount;
281 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
282 struct xfs_perag *pag = bp->b_pag;
283 unsigned int level;
284
285
286
287
288
289
290
291
292
293
294
295
296
297 level = be16_to_cpu(block->bb_level);
298 switch (block->bb_magic) {
299 case cpu_to_be32(XFS_ABTB_CRC_MAGIC):
300 if (!xfs_sb_version_hascrc(&mp->m_sb))
301 return false;
302 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid))
303 return false;
304 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
305 return false;
306 if (pag &&
307 be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
308 return false;
309
310 case cpu_to_be32(XFS_ABTB_MAGIC):
311 if (pag && pag->pagf_init) {
312 if (level >= pag->pagf_levels[XFS_BTNUM_BNOi])
313 return false;
314 } else if (level >= mp->m_ag_maxlevels)
315 return false;
316 break;
317 case cpu_to_be32(XFS_ABTC_CRC_MAGIC):
318 if (!xfs_sb_version_hascrc(&mp->m_sb))
319 return false;
320 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid))
321 return false;
322 if (block->bb_u.s.bb_blkno != cpu_to_be64(bp->b_bn))
323 return false;
324 if (pag &&
325 be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
326 return false;
327
328 case cpu_to_be32(XFS_ABTC_MAGIC):
329 if (pag && pag->pagf_init) {
330 if (level >= pag->pagf_levels[XFS_BTNUM_CNTi])
331 return false;
332 } else if (level >= mp->m_ag_maxlevels)
333 return false;
334 break;
335 default:
336 return false;
337 }
338
339
340 if (be16_to_cpu(block->bb_numrecs) > mp->m_alloc_mxr[level != 0])
341 return false;
342
343
344 if (!block->bb_u.s.bb_leftsib ||
345 (be32_to_cpu(block->bb_u.s.bb_leftsib) >= mp->m_sb.sb_agblocks &&
346 block->bb_u.s.bb_leftsib != cpu_to_be32(NULLAGBLOCK)))
347 return false;
348 if (!block->bb_u.s.bb_rightsib ||
349 (be32_to_cpu(block->bb_u.s.bb_rightsib) >= mp->m_sb.sb_agblocks &&
350 block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK)))
351 return false;
352
353 return true;
354}
355
356static void
357xfs_allocbt_read_verify(
358 struct xfs_buf *bp)
359{
360 if (!(xfs_btree_sblock_verify_crc(bp) &&
361 xfs_allocbt_verify(bp))) {
362 trace_xfs_btree_corrupt(bp, _RET_IP_);
363 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW,
364 bp->b_target->bt_mount, bp->b_addr);
365 xfs_buf_ioerror(bp, EFSCORRUPTED);
366 }
367}
368
369static void
370xfs_allocbt_write_verify(
371 struct xfs_buf *bp)
372{
373 if (!xfs_allocbt_verify(bp)) {
374 trace_xfs_btree_corrupt(bp, _RET_IP_);
375 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW,
376 bp->b_target->bt_mount, bp->b_addr);
377 xfs_buf_ioerror(bp, EFSCORRUPTED);
378 }
379 xfs_btree_sblock_calc_crc(bp);
380
381}
382
383const struct xfs_buf_ops xfs_allocbt_buf_ops = {
384 .verify_read = xfs_allocbt_read_verify,
385 .verify_write = xfs_allocbt_write_verify,
386};
387
388
389#if defined(DEBUG) || defined(XFS_WARN)
390STATIC int
391xfs_allocbt_keys_inorder(
392 struct xfs_btree_cur *cur,
393 union xfs_btree_key *k1,
394 union xfs_btree_key *k2)
395{
396 if (cur->bc_btnum == XFS_BTNUM_BNO) {
397 return be32_to_cpu(k1->alloc.ar_startblock) <
398 be32_to_cpu(k2->alloc.ar_startblock);
399 } else {
400 return be32_to_cpu(k1->alloc.ar_blockcount) <
401 be32_to_cpu(k2->alloc.ar_blockcount) ||
402 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount &&
403 be32_to_cpu(k1->alloc.ar_startblock) <
404 be32_to_cpu(k2->alloc.ar_startblock));
405 }
406}
407
408STATIC int
409xfs_allocbt_recs_inorder(
410 struct xfs_btree_cur *cur,
411 union xfs_btree_rec *r1,
412 union xfs_btree_rec *r2)
413{
414 if (cur->bc_btnum == XFS_BTNUM_BNO) {
415 return be32_to_cpu(r1->alloc.ar_startblock) +
416 be32_to_cpu(r1->alloc.ar_blockcount) <=
417 be32_to_cpu(r2->alloc.ar_startblock);
418 } else {
419 return be32_to_cpu(r1->alloc.ar_blockcount) <
420 be32_to_cpu(r2->alloc.ar_blockcount) ||
421 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount &&
422 be32_to_cpu(r1->alloc.ar_startblock) <
423 be32_to_cpu(r2->alloc.ar_startblock));
424 }
425}
426#endif
427
428static const struct xfs_btree_ops xfs_allocbt_ops = {
429 .rec_len = sizeof(xfs_alloc_rec_t),
430 .key_len = sizeof(xfs_alloc_key_t),
431
432 .dup_cursor = xfs_allocbt_dup_cursor,
433 .set_root = xfs_allocbt_set_root,
434 .alloc_block = xfs_allocbt_alloc_block,
435 .free_block = xfs_allocbt_free_block,
436 .update_lastrec = xfs_allocbt_update_lastrec,
437 .get_minrecs = xfs_allocbt_get_minrecs,
438 .get_maxrecs = xfs_allocbt_get_maxrecs,
439 .init_key_from_rec = xfs_allocbt_init_key_from_rec,
440 .init_rec_from_key = xfs_allocbt_init_rec_from_key,
441 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur,
442 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur,
443 .key_diff = xfs_allocbt_key_diff,
444 .buf_ops = &xfs_allocbt_buf_ops,
445#if defined(DEBUG) || defined(XFS_WARN)
446 .keys_inorder = xfs_allocbt_keys_inorder,
447 .recs_inorder = xfs_allocbt_recs_inorder,
448#endif
449};
450
451
452
453
454struct xfs_btree_cur *
455xfs_allocbt_init_cursor(
456 struct xfs_mount *mp,
457 struct xfs_trans *tp,
458 struct xfs_buf *agbp,
459 xfs_agnumber_t agno,
460 xfs_btnum_t btnum)
461{
462 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
463 struct xfs_btree_cur *cur;
464
465 ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
466
467 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
468
469 cur->bc_tp = tp;
470 cur->bc_mp = mp;
471 cur->bc_btnum = btnum;
472 cur->bc_blocklog = mp->m_sb.sb_blocklog;
473 cur->bc_ops = &xfs_allocbt_ops;
474
475 if (btnum == XFS_BTNUM_CNT) {
476 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]);
477 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
478 } else {
479 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]);
480 }
481
482 cur->bc_private.a.agbp = agbp;
483 cur->bc_private.a.agno = agno;
484
485 if (xfs_sb_version_hascrc(&mp->m_sb))
486 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
487
488 return cur;
489}
490
491
492
493
494int
495xfs_allocbt_maxrecs(
496 struct xfs_mount *mp,
497 int blocklen,
498 int leaf)
499{
500 blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
501
502 if (leaf)
503 return blocklen / sizeof(xfs_alloc_rec_t);
504 return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
505}
506