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_format.h"
21#include "xfs_log_format.h"
22#include "xfs_shared.h"
23#include "xfs_trans_resv.h"
24#include "xfs_bit.h"
25#include "xfs_sb.h"
26#include "xfs_mount.h"
27#include "xfs_inode.h"
28#include "xfs_btree.h"
29#include "xfs_alloc_btree.h"
30#include "xfs_alloc.h"
31#include "xfs_extent_busy.h"
32#include "xfs_error.h"
33#include "xfs_cksum.h"
34#include "xfs_trace.h"
35#include "xfs_trans.h"
36#include "xfs_buf_item.h"
37#include "xfs_log.h"
38
39struct workqueue_struct *xfs_alloc_wq;
40
41#define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
42
43#define XFSA_FIXUP_BNO_OK 1
44#define XFSA_FIXUP_CNT_OK 2
45
46STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
47STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
48STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
49STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
50 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
51
52
53
54
55STATIC int
56xfs_alloc_lookup_eq(
57 struct xfs_btree_cur *cur,
58 xfs_agblock_t bno,
59 xfs_extlen_t len,
60 int *stat)
61{
62 cur->bc_rec.a.ar_startblock = bno;
63 cur->bc_rec.a.ar_blockcount = len;
64 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
65}
66
67
68
69
70
71int
72xfs_alloc_lookup_ge(
73 struct xfs_btree_cur *cur,
74 xfs_agblock_t bno,
75 xfs_extlen_t len,
76 int *stat)
77{
78 cur->bc_rec.a.ar_startblock = bno;
79 cur->bc_rec.a.ar_blockcount = len;
80 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
81}
82
83
84
85
86
87int
88xfs_alloc_lookup_le(
89 struct xfs_btree_cur *cur,
90 xfs_agblock_t bno,
91 xfs_extlen_t len,
92 int *stat)
93{
94 cur->bc_rec.a.ar_startblock = bno;
95 cur->bc_rec.a.ar_blockcount = len;
96 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
97}
98
99
100
101
102
103
104STATIC int
105xfs_alloc_update(
106 struct xfs_btree_cur *cur,
107 xfs_agblock_t bno,
108 xfs_extlen_t len)
109{
110 union xfs_btree_rec rec;
111
112 rec.alloc.ar_startblock = cpu_to_be32(bno);
113 rec.alloc.ar_blockcount = cpu_to_be32(len);
114 return xfs_btree_update(cur, &rec);
115}
116
117
118
119
120int
121xfs_alloc_get_rec(
122 struct xfs_btree_cur *cur,
123 xfs_agblock_t *bno,
124 xfs_extlen_t *len,
125 int *stat)
126{
127 union xfs_btree_rec *rec;
128 int error;
129
130 error = xfs_btree_get_rec(cur, &rec, stat);
131 if (!error && *stat == 1) {
132 *bno = be32_to_cpu(rec->alloc.ar_startblock);
133 *len = be32_to_cpu(rec->alloc.ar_blockcount);
134 }
135 return error;
136}
137
138
139
140
141
142STATIC void
143xfs_alloc_compute_aligned(
144 xfs_alloc_arg_t *args,
145 xfs_agblock_t foundbno,
146 xfs_extlen_t foundlen,
147 xfs_agblock_t *resbno,
148 xfs_extlen_t *reslen)
149{
150 xfs_agblock_t bno;
151 xfs_extlen_t len;
152 xfs_extlen_t diff;
153
154
155 xfs_extent_busy_trim(args, foundbno, foundlen, &bno, &len);
156
157
158
159
160
161 if (bno < args->min_agbno && bno + len > args->min_agbno) {
162 diff = args->min_agbno - bno;
163 if (len > diff) {
164 bno += diff;
165 len -= diff;
166 }
167 }
168
169 if (args->alignment > 1 && len >= args->minlen) {
170 xfs_agblock_t aligned_bno = roundup(bno, args->alignment);
171
172 diff = aligned_bno - bno;
173
174 *resbno = aligned_bno;
175 *reslen = diff >= len ? 0 : len - diff;
176 } else {
177 *resbno = bno;
178 *reslen = len;
179 }
180}
181
182
183
184
185
186STATIC xfs_extlen_t
187xfs_alloc_compute_diff(
188 xfs_agblock_t wantbno,
189 xfs_extlen_t wantlen,
190 xfs_extlen_t alignment,
191 char userdata,
192 xfs_agblock_t freebno,
193 xfs_extlen_t freelen,
194 xfs_agblock_t *newbnop)
195{
196 xfs_agblock_t freeend;
197 xfs_agblock_t newbno1;
198 xfs_agblock_t newbno2;
199 xfs_extlen_t newlen1=0;
200 xfs_extlen_t newlen2=0;
201 xfs_agblock_t wantend;
202
203 ASSERT(freelen >= wantlen);
204 freeend = freebno + freelen;
205 wantend = wantbno + wantlen;
206
207
208
209
210
211
212
213 if (freebno >= wantbno || (userdata && freeend < wantend)) {
214 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
215 newbno1 = NULLAGBLOCK;
216 } else if (freeend >= wantend && alignment > 1) {
217 newbno1 = roundup(wantbno, alignment);
218 newbno2 = newbno1 - alignment;
219 if (newbno1 >= freeend)
220 newbno1 = NULLAGBLOCK;
221 else
222 newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
223 if (newbno2 < freebno)
224 newbno2 = NULLAGBLOCK;
225 else
226 newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
227 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
228 if (newlen1 < newlen2 ||
229 (newlen1 == newlen2 &&
230 XFS_ABSDIFF(newbno1, wantbno) >
231 XFS_ABSDIFF(newbno2, wantbno)))
232 newbno1 = newbno2;
233 } else if (newbno2 != NULLAGBLOCK)
234 newbno1 = newbno2;
235 } else if (freeend >= wantend) {
236 newbno1 = wantbno;
237 } else if (alignment > 1) {
238 newbno1 = roundup(freeend - wantlen, alignment);
239 if (newbno1 > freeend - wantlen &&
240 newbno1 - alignment >= freebno)
241 newbno1 -= alignment;
242 else if (newbno1 >= freeend)
243 newbno1 = NULLAGBLOCK;
244 } else
245 newbno1 = freeend - wantlen;
246 *newbnop = newbno1;
247 return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
248}
249
250
251
252
253
254
255
256STATIC void
257xfs_alloc_fix_len(
258 xfs_alloc_arg_t *args)
259{
260 xfs_extlen_t k;
261 xfs_extlen_t rlen;
262
263 ASSERT(args->mod < args->prod);
264 rlen = args->len;
265 ASSERT(rlen >= args->minlen);
266 ASSERT(rlen <= args->maxlen);
267 if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
268 (args->mod == 0 && rlen < args->prod))
269 return;
270 k = rlen % args->prod;
271 if (k == args->mod)
272 return;
273 if (k > args->mod)
274 rlen = rlen - (k - args->mod);
275 else
276 rlen = rlen - args->prod + (args->mod - k);
277
278 if ((int)rlen < (int)args->minlen)
279 return;
280 ASSERT(rlen >= args->minlen && rlen <= args->maxlen);
281 ASSERT(rlen % args->prod == args->mod);
282 args->len = rlen;
283}
284
285
286
287
288
289STATIC int
290xfs_alloc_fix_minleft(
291 xfs_alloc_arg_t *args)
292{
293 xfs_agf_t *agf;
294 int diff;
295
296 if (args->minleft == 0)
297 return 1;
298 agf = XFS_BUF_TO_AGF(args->agbp);
299 diff = be32_to_cpu(agf->agf_freeblks)
300 - args->len - args->minleft;
301 if (diff >= 0)
302 return 1;
303 args->len += diff;
304
305 if ((int)args->len >= (int)args->minlen)
306 return 1;
307 args->agbno = NULLAGBLOCK;
308 return 0;
309}
310
311
312
313
314
315
316
317
318STATIC int
319xfs_alloc_fixup_trees(
320 xfs_btree_cur_t *cnt_cur,
321 xfs_btree_cur_t *bno_cur,
322 xfs_agblock_t fbno,
323 xfs_extlen_t flen,
324 xfs_agblock_t rbno,
325 xfs_extlen_t rlen,
326 int flags)
327{
328 int error;
329 int i;
330 xfs_agblock_t nfbno1;
331 xfs_agblock_t nfbno2;
332 xfs_extlen_t nflen1=0;
333 xfs_extlen_t nflen2=0;
334 struct xfs_mount *mp;
335
336 mp = cnt_cur->bc_mp;
337
338
339
340
341 if (flags & XFSA_FIXUP_CNT_OK) {
342#ifdef DEBUG
343 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
344 return error;
345 XFS_WANT_CORRUPTED_RETURN(mp,
346 i == 1 && nfbno1 == fbno && nflen1 == flen);
347#endif
348 } else {
349 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
350 return error;
351 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
352 }
353
354
355
356 if (flags & XFSA_FIXUP_BNO_OK) {
357#ifdef DEBUG
358 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
359 return error;
360 XFS_WANT_CORRUPTED_RETURN(mp,
361 i == 1 && nfbno1 == fbno && nflen1 == flen);
362#endif
363 } else {
364 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
365 return error;
366 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
367 }
368
369#ifdef DEBUG
370 if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
371 struct xfs_btree_block *bnoblock;
372 struct xfs_btree_block *cntblock;
373
374 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
375 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
376
377 XFS_WANT_CORRUPTED_RETURN(mp,
378 bnoblock->bb_numrecs == cntblock->bb_numrecs);
379 }
380#endif
381
382
383
384
385
386
387 if (rbno == fbno && rlen == flen)
388 nfbno1 = nfbno2 = NULLAGBLOCK;
389 else if (rbno == fbno) {
390 nfbno1 = rbno + rlen;
391 nflen1 = flen - rlen;
392 nfbno2 = NULLAGBLOCK;
393 } else if (rbno + rlen == fbno + flen) {
394 nfbno1 = fbno;
395 nflen1 = flen - rlen;
396 nfbno2 = NULLAGBLOCK;
397 } else {
398 nfbno1 = fbno;
399 nflen1 = rbno - fbno;
400 nfbno2 = rbno + rlen;
401 nflen2 = (fbno + flen) - nfbno2;
402 }
403
404
405
406 if ((error = xfs_btree_delete(cnt_cur, &i)))
407 return error;
408 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
409
410
411
412 if (nfbno1 != NULLAGBLOCK) {
413 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
414 return error;
415 XFS_WANT_CORRUPTED_RETURN(mp, i == 0);
416 if ((error = xfs_btree_insert(cnt_cur, &i)))
417 return error;
418 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
419 }
420 if (nfbno2 != NULLAGBLOCK) {
421 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
422 return error;
423 XFS_WANT_CORRUPTED_RETURN(mp, i == 0);
424 if ((error = xfs_btree_insert(cnt_cur, &i)))
425 return error;
426 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
427 }
428
429
430
431 if (nfbno1 == NULLAGBLOCK) {
432
433
434
435 if ((error = xfs_btree_delete(bno_cur, &i)))
436 return error;
437 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
438 } else {
439
440
441
442 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
443 return error;
444 }
445 if (nfbno2 != NULLAGBLOCK) {
446
447
448
449 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
450 return error;
451 XFS_WANT_CORRUPTED_RETURN(mp, i == 0);
452 if ((error = xfs_btree_insert(bno_cur, &i)))
453 return error;
454 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
455 }
456 return 0;
457}
458
459static bool
460xfs_agfl_verify(
461 struct xfs_buf *bp)
462{
463 struct xfs_mount *mp = bp->b_target->bt_mount;
464 struct xfs_agfl *agfl = XFS_BUF_TO_AGFL(bp);
465 int i;
466
467 if (!uuid_equal(&agfl->agfl_uuid, &mp->m_sb.sb_uuid))
468 return false;
469 if (be32_to_cpu(agfl->agfl_magicnum) != XFS_AGFL_MAGIC)
470 return false;
471
472
473
474
475
476
477 if (bp->b_pag && be32_to_cpu(agfl->agfl_seqno) != bp->b_pag->pag_agno)
478 return false;
479
480 for (i = 0; i < XFS_AGFL_SIZE(mp); i++) {
481 if (be32_to_cpu(agfl->agfl_bno[i]) != NULLAGBLOCK &&
482 be32_to_cpu(agfl->agfl_bno[i]) >= mp->m_sb.sb_agblocks)
483 return false;
484 }
485 return true;
486}
487
488static void
489xfs_agfl_read_verify(
490 struct xfs_buf *bp)
491{
492 struct xfs_mount *mp = bp->b_target->bt_mount;
493
494
495
496
497
498
499
500 if (!xfs_sb_version_hascrc(&mp->m_sb))
501 return;
502
503 if (!xfs_buf_verify_cksum(bp, XFS_AGFL_CRC_OFF))
504 xfs_buf_ioerror(bp, -EFSBADCRC);
505 else if (!xfs_agfl_verify(bp))
506 xfs_buf_ioerror(bp, -EFSCORRUPTED);
507
508 if (bp->b_error)
509 xfs_verifier_error(bp);
510}
511
512static void
513xfs_agfl_write_verify(
514 struct xfs_buf *bp)
515{
516 struct xfs_mount *mp = bp->b_target->bt_mount;
517 struct xfs_buf_log_item *bip = bp->b_fspriv;
518
519
520 if (!xfs_sb_version_hascrc(&mp->m_sb))
521 return;
522
523 if (!xfs_agfl_verify(bp)) {
524 xfs_buf_ioerror(bp, -EFSCORRUPTED);
525 xfs_verifier_error(bp);
526 return;
527 }
528
529 if (bip)
530 XFS_BUF_TO_AGFL(bp)->agfl_lsn = cpu_to_be64(bip->bli_item.li_lsn);
531
532 xfs_buf_update_cksum(bp, XFS_AGFL_CRC_OFF);
533}
534
535const struct xfs_buf_ops xfs_agfl_buf_ops = {
536 .verify_read = xfs_agfl_read_verify,
537 .verify_write = xfs_agfl_write_verify,
538};
539
540
541
542
543STATIC int
544xfs_alloc_read_agfl(
545 xfs_mount_t *mp,
546 xfs_trans_t *tp,
547 xfs_agnumber_t agno,
548 xfs_buf_t **bpp)
549{
550 xfs_buf_t *bp;
551 int error;
552
553 ASSERT(agno != NULLAGNUMBER);
554 error = xfs_trans_read_buf(
555 mp, tp, mp->m_ddev_targp,
556 XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
557 XFS_FSS_TO_BB(mp, 1), 0, &bp, &xfs_agfl_buf_ops);
558 if (error)
559 return error;
560 xfs_buf_set_ref(bp, XFS_AGFL_REF);
561 *bpp = bp;
562 return 0;
563}
564
565STATIC int
566xfs_alloc_update_counters(
567 struct xfs_trans *tp,
568 struct xfs_perag *pag,
569 struct xfs_buf *agbp,
570 long len)
571{
572 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
573
574 pag->pagf_freeblks += len;
575 be32_add_cpu(&agf->agf_freeblks, len);
576
577 xfs_trans_agblocks_delta(tp, len);
578 if (unlikely(be32_to_cpu(agf->agf_freeblks) >
579 be32_to_cpu(agf->agf_length)))
580 return -EFSCORRUPTED;
581
582 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
583 return 0;
584}
585
586
587
588
589
590
591
592
593
594
595
596
597
598STATIC int
599xfs_alloc_ag_vextent(
600 xfs_alloc_arg_t *args)
601{
602 int error=0;
603
604 ASSERT(args->minlen > 0);
605 ASSERT(args->maxlen > 0);
606 ASSERT(args->minlen <= args->maxlen);
607 ASSERT(args->mod < args->prod);
608 ASSERT(args->alignment > 0);
609
610
611
612 args->wasfromfl = 0;
613 switch (args->type) {
614 case XFS_ALLOCTYPE_THIS_AG:
615 error = xfs_alloc_ag_vextent_size(args);
616 break;
617 case XFS_ALLOCTYPE_NEAR_BNO:
618 error = xfs_alloc_ag_vextent_near(args);
619 break;
620 case XFS_ALLOCTYPE_THIS_BNO:
621 error = xfs_alloc_ag_vextent_exact(args);
622 break;
623 default:
624 ASSERT(0);
625
626 }
627
628 if (error || args->agbno == NULLAGBLOCK)
629 return error;
630
631 ASSERT(args->len >= args->minlen);
632 ASSERT(args->len <= args->maxlen);
633 ASSERT(!args->wasfromfl || !args->isfl);
634 ASSERT(args->agbno % args->alignment == 0);
635
636 if (!args->wasfromfl) {
637 error = xfs_alloc_update_counters(args->tp, args->pag,
638 args->agbp,
639 -((long)(args->len)));
640 if (error)
641 return error;
642
643 ASSERT(!xfs_extent_busy_search(args->mp, args->agno,
644 args->agbno, args->len));
645 }
646
647 if (!args->isfl) {
648 xfs_trans_mod_sb(args->tp, args->wasdel ?
649 XFS_TRANS_SB_RES_FDBLOCKS :
650 XFS_TRANS_SB_FDBLOCKS,
651 -((long)(args->len)));
652 }
653
654 XFS_STATS_INC(xs_allocx);
655 XFS_STATS_ADD(xs_allocb, args->len);
656 return error;
657}
658
659
660
661
662
663
664
665STATIC int
666xfs_alloc_ag_vextent_exact(
667 xfs_alloc_arg_t *args)
668{
669 xfs_btree_cur_t *bno_cur;
670 xfs_btree_cur_t *cnt_cur;
671 int error;
672 xfs_agblock_t fbno;
673 xfs_extlen_t flen;
674 xfs_agblock_t tbno;
675 xfs_extlen_t tlen;
676 xfs_agblock_t tend;
677 int i;
678
679 ASSERT(args->alignment == 1);
680
681
682
683
684 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
685 args->agno, XFS_BTNUM_BNO);
686
687
688
689
690
691
692 error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
693 if (error)
694 goto error0;
695 if (!i)
696 goto not_found;
697
698
699
700
701 error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
702 if (error)
703 goto error0;
704 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
705 ASSERT(fbno <= args->agbno);
706
707
708
709
710 xfs_extent_busy_trim(args, fbno, flen, &tbno, &tlen);
711
712
713
714
715
716 if (tbno > args->agbno)
717 goto not_found;
718 if (tlen < args->minlen)
719 goto not_found;
720 tend = tbno + tlen;
721 if (tend < args->agbno + args->minlen)
722 goto not_found;
723
724
725
726
727
728
729
730 args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
731 - args->agbno;
732 xfs_alloc_fix_len(args);
733 if (!xfs_alloc_fix_minleft(args))
734 goto not_found;
735
736 ASSERT(args->agbno + args->len <= tend);
737
738
739
740
741
742 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
743 args->agno, XFS_BTNUM_CNT);
744 ASSERT(args->agbno + args->len <=
745 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
746 error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
747 args->len, XFSA_FIXUP_BNO_OK);
748 if (error) {
749 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
750 goto error0;
751 }
752
753 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
754 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
755
756 args->wasfromfl = 0;
757 trace_xfs_alloc_exact_done(args);
758 return 0;
759
760not_found:
761
762 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
763 args->agbno = NULLAGBLOCK;
764 trace_xfs_alloc_exact_notfound(args);
765 return 0;
766
767error0:
768 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
769 trace_xfs_alloc_exact_error(args);
770 return error;
771}
772
773
774
775
776
777STATIC int
778xfs_alloc_find_best_extent(
779 struct xfs_alloc_arg *args,
780 struct xfs_btree_cur **gcur,
781 struct xfs_btree_cur **scur,
782 xfs_agblock_t gdiff,
783 xfs_agblock_t *sbno,
784 xfs_extlen_t *slen,
785 xfs_agblock_t *sbnoa,
786 xfs_extlen_t *slena,
787 int dir)
788{
789 xfs_agblock_t new;
790 xfs_agblock_t sdiff;
791 int error;
792 int i;
793
794
795 if (!gdiff)
796 goto out_use_good;
797
798
799
800
801 do {
802 error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
803 if (error)
804 goto error0;
805 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
806 xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
807
808
809
810
811 if (!dir) {
812 if (*sbnoa > args->max_agbno)
813 goto out_use_good;
814 if (*sbnoa >= args->agbno + gdiff)
815 goto out_use_good;
816 } else {
817 if (*sbnoa < args->min_agbno)
818 goto out_use_good;
819 if (*sbnoa <= args->agbno - gdiff)
820 goto out_use_good;
821 }
822
823
824
825
826 if (*slena >= args->minlen) {
827 args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
828 xfs_alloc_fix_len(args);
829
830 sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
831 args->alignment,
832 args->userdata, *sbnoa,
833 *slena, &new);
834
835
836
837
838 if (sdiff < gdiff)
839 goto out_use_search;
840 goto out_use_good;
841 }
842
843 if (!dir)
844 error = xfs_btree_increment(*scur, 0, &i);
845 else
846 error = xfs_btree_decrement(*scur, 0, &i);
847 if (error)
848 goto error0;
849 } while (i);
850
851out_use_good:
852 xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
853 *scur = NULL;
854 return 0;
855
856out_use_search:
857 xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
858 *gcur = NULL;
859 return 0;
860
861error0:
862
863 return error;
864}
865
866
867
868
869
870
871
872STATIC int
873xfs_alloc_ag_vextent_near(
874 xfs_alloc_arg_t *args)
875{
876 xfs_btree_cur_t *bno_cur_gt;
877 xfs_btree_cur_t *bno_cur_lt;
878 xfs_btree_cur_t *cnt_cur;
879 xfs_agblock_t gtbno;
880 xfs_agblock_t gtbnoa;
881 xfs_extlen_t gtdiff;
882 xfs_extlen_t gtlen;
883 xfs_extlen_t gtlena;
884 xfs_agblock_t gtnew;
885 int error;
886 int i;
887 int j;
888 xfs_agblock_t ltbno;
889 xfs_agblock_t ltbnoa;
890 xfs_extlen_t ltdiff;
891 xfs_extlen_t ltlen;
892 xfs_extlen_t ltlena;
893 xfs_agblock_t ltnew;
894 xfs_extlen_t rlen;
895 int forced = 0;
896#ifdef DEBUG
897
898
899
900 int dofirst;
901
902 dofirst = prandom_u32() & 1;
903#endif
904
905
906 if (!args->min_agbno && !args->max_agbno)
907 args->max_agbno = args->mp->m_sb.sb_agblocks - 1;
908 ASSERT(args->min_agbno <= args->max_agbno);
909
910
911 if (args->agbno < args->min_agbno)
912 args->agbno = args->min_agbno;
913 if (args->agbno > args->max_agbno)
914 args->agbno = args->max_agbno;
915
916restart:
917 bno_cur_lt = NULL;
918 bno_cur_gt = NULL;
919 ltlen = 0;
920 gtlena = 0;
921 ltlena = 0;
922
923
924
925
926 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
927 args->agno, XFS_BTNUM_CNT);
928
929
930
931
932 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
933 goto error0;
934
935
936
937
938 if (!i) {
939 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, <bno,
940 <len, &i)))
941 goto error0;
942 if (i == 0 || ltlen == 0) {
943 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
944 trace_xfs_alloc_near_noentry(args);
945 return 0;
946 }
947 ASSERT(i == 1);
948 }
949 args->wasfromfl = 0;
950
951
952
953
954
955
956
957
958
959
960
961 while (xfs_btree_islastblock(cnt_cur, 0)) {
962 xfs_extlen_t bdiff;
963 int besti=0;
964 xfs_extlen_t blen=0;
965 xfs_agblock_t bnew=0;
966
967#ifdef DEBUG
968 if (dofirst)
969 break;
970#endif
971
972
973
974
975
976
977 if (ltlen || args->alignment > 1) {
978 cnt_cur->bc_ptrs[0] = 1;
979 do {
980 if ((error = xfs_alloc_get_rec(cnt_cur, <bno,
981 <len, &i)))
982 goto error0;
983 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
984 if (ltlen >= args->minlen)
985 break;
986 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
987 goto error0;
988 } while (i);
989 ASSERT(ltlen >= args->minlen);
990 if (!i)
991 break;
992 }
993 i = cnt_cur->bc_ptrs[0];
994 for (j = 1, blen = 0, bdiff = 0;
995 !error && j && (blen < args->maxlen || bdiff > 0);
996 error = xfs_btree_increment(cnt_cur, 0, &j)) {
997
998
999
1000
1001 if ((error = xfs_alloc_get_rec(cnt_cur, <bno, <len, &i)))
1002 goto error0;
1003 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1004 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1005 <bnoa, <lena);
1006 if (ltlena < args->minlen)
1007 continue;
1008 if (ltbnoa < args->min_agbno || ltbnoa > args->max_agbno)
1009 continue;
1010 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1011 xfs_alloc_fix_len(args);
1012 ASSERT(args->len >= args->minlen);
1013 if (args->len < blen)
1014 continue;
1015 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1016 args->alignment, args->userdata, ltbnoa,
1017 ltlena, <new);
1018 if (ltnew != NULLAGBLOCK &&
1019 (args->len > blen || ltdiff < bdiff)) {
1020 bdiff = ltdiff;
1021 bnew = ltnew;
1022 blen = args->len;
1023 besti = cnt_cur->bc_ptrs[0];
1024 }
1025 }
1026
1027
1028
1029
1030 if (blen == 0)
1031 break;
1032
1033
1034
1035 cnt_cur->bc_ptrs[0] = besti;
1036 if ((error = xfs_alloc_get_rec(cnt_cur, <bno, <len, &i)))
1037 goto error0;
1038 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1039 ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
1040 args->len = blen;
1041 if (!xfs_alloc_fix_minleft(args)) {
1042 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1043 trace_xfs_alloc_near_nominleft(args);
1044 return 0;
1045 }
1046 blen = args->len;
1047
1048
1049
1050 args->agbno = bnew;
1051 ASSERT(bnew >= ltbno);
1052 ASSERT(bnew + blen <= ltbno + ltlen);
1053
1054
1055
1056 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
1057 args->agbp, args->agno, XFS_BTNUM_BNO);
1058
1059
1060
1061 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
1062 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
1063 goto error0;
1064 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1065 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1066
1067 trace_xfs_alloc_near_first(args);
1068 return 0;
1069 }
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1086 args->agno, XFS_BTNUM_BNO);
1087
1088
1089
1090 if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
1091 goto error0;
1092 if (!i) {
1093
1094
1095
1096
1097 bno_cur_gt = bno_cur_lt;
1098 bno_cur_lt = NULL;
1099 }
1100
1101
1102
1103 else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
1104 goto error0;
1105
1106
1107
1108
1109 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
1110 goto error0;
1111 if (!i) {
1112
1113
1114
1115 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
1116 bno_cur_gt = NULL;
1117 }
1118
1119
1120
1121
1122
1123 do {
1124 if (bno_cur_lt) {
1125 if ((error = xfs_alloc_get_rec(bno_cur_lt, <bno, <len, &i)))
1126 goto error0;
1127 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1128 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1129 <bnoa, <lena);
1130 if (ltlena >= args->minlen && ltbnoa >= args->min_agbno)
1131 break;
1132 if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
1133 goto error0;
1134 if (!i || ltbnoa < args->min_agbno) {
1135 xfs_btree_del_cursor(bno_cur_lt,
1136 XFS_BTREE_NOERROR);
1137 bno_cur_lt = NULL;
1138 }
1139 }
1140 if (bno_cur_gt) {
1141 if ((error = xfs_alloc_get_rec(bno_cur_gt, >bno, >len, &i)))
1142 goto error0;
1143 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1144 xfs_alloc_compute_aligned(args, gtbno, gtlen,
1145 >bnoa, >lena);
1146 if (gtlena >= args->minlen && gtbnoa <= args->max_agbno)
1147 break;
1148 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
1149 goto error0;
1150 if (!i || gtbnoa > args->max_agbno) {
1151 xfs_btree_del_cursor(bno_cur_gt,
1152 XFS_BTREE_NOERROR);
1153 bno_cur_gt = NULL;
1154 }
1155 }
1156 } while (bno_cur_lt || bno_cur_gt);
1157
1158
1159
1160
1161 if (bno_cur_lt && bno_cur_gt) {
1162 if (ltlena >= args->minlen) {
1163
1164
1165
1166 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1167 xfs_alloc_fix_len(args);
1168 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1169 args->alignment, args->userdata, ltbnoa,
1170 ltlena, <new);
1171
1172 error = xfs_alloc_find_best_extent(args,
1173 &bno_cur_lt, &bno_cur_gt,
1174 ltdiff, >bno, >len,
1175 >bnoa, >lena,
1176 0 );
1177 } else {
1178 ASSERT(gtlena >= args->minlen);
1179
1180
1181
1182
1183 args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1184 xfs_alloc_fix_len(args);
1185 gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1186 args->alignment, args->userdata, gtbnoa,
1187 gtlena, >new);
1188
1189 error = xfs_alloc_find_best_extent(args,
1190 &bno_cur_gt, &bno_cur_lt,
1191 gtdiff, <bno, <len,
1192 <bnoa, <lena,
1193 1 );
1194 }
1195
1196 if (error)
1197 goto error0;
1198 }
1199
1200
1201
1202
1203 if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
1204 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1205
1206 if (!forced++) {
1207 trace_xfs_alloc_near_busy(args);
1208 xfs_log_force(args->mp, XFS_LOG_SYNC);
1209 goto restart;
1210 }
1211 trace_xfs_alloc_size_neither(args);
1212 args->agbno = NULLAGBLOCK;
1213 return 0;
1214 }
1215
1216
1217
1218
1219
1220
1221
1222 if (bno_cur_gt) {
1223 bno_cur_lt = bno_cur_gt;
1224 bno_cur_gt = NULL;
1225 ltbno = gtbno;
1226 ltbnoa = gtbnoa;
1227 ltlen = gtlen;
1228 ltlena = gtlena;
1229 j = 1;
1230 } else
1231 j = 0;
1232
1233
1234
1235
1236 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1237 xfs_alloc_fix_len(args);
1238 if (!xfs_alloc_fix_minleft(args)) {
1239 trace_xfs_alloc_near_nominleft(args);
1240 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1241 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1242 return 0;
1243 }
1244 rlen = args->len;
1245 (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
1246 args->userdata, ltbnoa, ltlena, <new);
1247 ASSERT(ltnew >= ltbno);
1248 ASSERT(ltnew + rlen <= ltbnoa + ltlena);
1249 ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
1250 ASSERT(ltnew >= args->min_agbno && ltnew <= args->max_agbno);
1251 args->agbno = ltnew;
1252
1253 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1254 ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1255 goto error0;
1256
1257 if (j)
1258 trace_xfs_alloc_near_greater(args);
1259 else
1260 trace_xfs_alloc_near_lesser(args);
1261
1262 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1263 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1264 return 0;
1265
1266 error0:
1267 trace_xfs_alloc_near_error(args);
1268 if (cnt_cur != NULL)
1269 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1270 if (bno_cur_lt != NULL)
1271 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1272 if (bno_cur_gt != NULL)
1273 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1274 return error;
1275}
1276
1277
1278
1279
1280
1281
1282
1283STATIC int
1284xfs_alloc_ag_vextent_size(
1285 xfs_alloc_arg_t *args)
1286{
1287 xfs_btree_cur_t *bno_cur;
1288 xfs_btree_cur_t *cnt_cur;
1289 int error;
1290 xfs_agblock_t fbno;
1291 xfs_extlen_t flen;
1292 int i;
1293 xfs_agblock_t rbno;
1294 xfs_extlen_t rlen;
1295 int forced = 0;
1296
1297restart:
1298
1299
1300
1301 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1302 args->agno, XFS_BTNUM_CNT);
1303 bno_cur = NULL;
1304
1305
1306
1307
1308 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1309 args->maxlen + args->alignment - 1, &i)))
1310 goto error0;
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320 if (!i || forced > 1) {
1321 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1322 &fbno, &flen, &i);
1323 if (error)
1324 goto error0;
1325 if (i == 0 || flen == 0) {
1326 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1327 trace_xfs_alloc_size_noentry(args);
1328 return 0;
1329 }
1330 ASSERT(i == 1);
1331 xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
1332 } else {
1333
1334
1335
1336
1337
1338
1339 for (;;) {
1340 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1341 if (error)
1342 goto error0;
1343 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1344
1345 xfs_alloc_compute_aligned(args, fbno, flen,
1346 &rbno, &rlen);
1347
1348 if (rlen >= args->maxlen)
1349 break;
1350
1351 error = xfs_btree_increment(cnt_cur, 0, &i);
1352 if (error)
1353 goto error0;
1354 if (i == 0) {
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365 xfs_btree_del_cursor(cnt_cur,
1366 XFS_BTREE_NOERROR);
1367 trace_xfs_alloc_size_busy(args);
1368 if (!forced++)
1369 xfs_log_force(args->mp, XFS_LOG_SYNC);
1370 goto restart;
1371 }
1372 }
1373 }
1374
1375
1376
1377
1378
1379
1380
1381 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1382 XFS_WANT_CORRUPTED_GOTO(args->mp, rlen == 0 ||
1383 (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1384 if (rlen < args->maxlen) {
1385 xfs_agblock_t bestfbno;
1386 xfs_extlen_t bestflen;
1387 xfs_agblock_t bestrbno;
1388 xfs_extlen_t bestrlen;
1389
1390 bestrlen = rlen;
1391 bestrbno = rbno;
1392 bestflen = flen;
1393 bestfbno = fbno;
1394 for (;;) {
1395 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1396 goto error0;
1397 if (i == 0)
1398 break;
1399 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1400 &i)))
1401 goto error0;
1402 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1403 if (flen < bestrlen)
1404 break;
1405 xfs_alloc_compute_aligned(args, fbno, flen,
1406 &rbno, &rlen);
1407 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1408 XFS_WANT_CORRUPTED_GOTO(args->mp, rlen == 0 ||
1409 (rlen <= flen && rbno + rlen <= fbno + flen),
1410 error0);
1411 if (rlen > bestrlen) {
1412 bestrlen = rlen;
1413 bestrbno = rbno;
1414 bestflen = flen;
1415 bestfbno = fbno;
1416 if (rlen == args->maxlen)
1417 break;
1418 }
1419 }
1420 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1421 &i)))
1422 goto error0;
1423 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1424 rlen = bestrlen;
1425 rbno = bestrbno;
1426 flen = bestflen;
1427 fbno = bestfbno;
1428 }
1429 args->wasfromfl = 0;
1430
1431
1432
1433 args->len = rlen;
1434 if (rlen < args->minlen) {
1435 if (!forced++) {
1436 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1437 trace_xfs_alloc_size_busy(args);
1438 xfs_log_force(args->mp, XFS_LOG_SYNC);
1439 goto restart;
1440 }
1441 goto out_nominleft;
1442 }
1443 xfs_alloc_fix_len(args);
1444
1445 if (!xfs_alloc_fix_minleft(args))
1446 goto out_nominleft;
1447 rlen = args->len;
1448 XFS_WANT_CORRUPTED_GOTO(args->mp, rlen <= flen, error0);
1449
1450
1451
1452 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1453 args->agno, XFS_BTNUM_BNO);
1454 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1455 rbno, rlen, XFSA_FIXUP_CNT_OK)))
1456 goto error0;
1457 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1458 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1459 cnt_cur = bno_cur = NULL;
1460 args->len = rlen;
1461 args->agbno = rbno;
1462 XFS_WANT_CORRUPTED_GOTO(args->mp,
1463 args->agbno + args->len <=
1464 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1465 error0);
1466 trace_xfs_alloc_size_done(args);
1467 return 0;
1468
1469error0:
1470 trace_xfs_alloc_size_error(args);
1471 if (cnt_cur)
1472 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1473 if (bno_cur)
1474 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1475 return error;
1476
1477out_nominleft:
1478 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1479 trace_xfs_alloc_size_nominleft(args);
1480 args->agbno = NULLAGBLOCK;
1481 return 0;
1482}
1483
1484
1485
1486
1487
1488
1489STATIC int
1490xfs_alloc_ag_vextent_small(
1491 xfs_alloc_arg_t *args,
1492 xfs_btree_cur_t *ccur,
1493 xfs_agblock_t *fbnop,
1494 xfs_extlen_t *flenp,
1495 int *stat)
1496{
1497 int error;
1498 xfs_agblock_t fbno;
1499 xfs_extlen_t flen;
1500 int i;
1501
1502 if ((error = xfs_btree_decrement(ccur, 0, &i)))
1503 goto error0;
1504 if (i) {
1505 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1506 goto error0;
1507 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1508 }
1509
1510
1511
1512
1513
1514 else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
1515 (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1516 > args->minleft)) {
1517 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1518 if (error)
1519 goto error0;
1520 if (fbno != NULLAGBLOCK) {
1521 xfs_extent_busy_reuse(args->mp, args->agno, fbno, 1,
1522 args->userdata);
1523
1524 if (args->userdata) {
1525 xfs_buf_t *bp;
1526
1527 bp = xfs_btree_get_bufs(args->mp, args->tp,
1528 args->agno, fbno, 0);
1529 xfs_trans_binval(args->tp, bp);
1530 }
1531 args->len = 1;
1532 args->agbno = fbno;
1533 XFS_WANT_CORRUPTED_GOTO(args->mp,
1534 args->agbno + args->len <=
1535 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1536 error0);
1537 args->wasfromfl = 1;
1538 trace_xfs_alloc_small_freelist(args);
1539 *stat = 0;
1540 return 0;
1541 }
1542
1543
1544
1545 else
1546 flen = 0;
1547 }
1548
1549
1550
1551 else {
1552 fbno = NULLAGBLOCK;
1553 flen = 0;
1554 }
1555
1556
1557
1558 if (flen < args->minlen) {
1559 args->agbno = NULLAGBLOCK;
1560 trace_xfs_alloc_small_notenough(args);
1561 flen = 0;
1562 }
1563 *fbnop = fbno;
1564 *flenp = flen;
1565 *stat = 1;
1566 trace_xfs_alloc_small_done(args);
1567 return 0;
1568
1569error0:
1570 trace_xfs_alloc_small_error(args);
1571 return error;
1572}
1573
1574
1575
1576
1577STATIC int
1578xfs_free_ag_extent(
1579 xfs_trans_t *tp,
1580 xfs_buf_t *agbp,
1581 xfs_agnumber_t agno,
1582 xfs_agblock_t bno,
1583 xfs_extlen_t len,
1584 int isfl)
1585{
1586 xfs_btree_cur_t *bno_cur;
1587 xfs_btree_cur_t *cnt_cur;
1588 int error;
1589 xfs_agblock_t gtbno;
1590 xfs_extlen_t gtlen;
1591 int haveleft;
1592 int haveright;
1593 int i;
1594 xfs_agblock_t ltbno;
1595 xfs_extlen_t ltlen;
1596 xfs_mount_t *mp;
1597 xfs_agblock_t nbno;
1598 xfs_extlen_t nlen;
1599 xfs_perag_t *pag;
1600
1601 mp = tp->t_mountp;
1602
1603
1604
1605 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
1606 cnt_cur = NULL;
1607
1608
1609
1610
1611 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1612 goto error0;
1613 if (haveleft) {
1614
1615
1616
1617 if ((error = xfs_alloc_get_rec(bno_cur, <bno, <len, &i)))
1618 goto error0;
1619 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1620
1621
1622
1623 if (ltbno + ltlen < bno)
1624 haveleft = 0;
1625 else {
1626
1627
1628
1629
1630
1631 XFS_WANT_CORRUPTED_GOTO(mp,
1632 ltbno + ltlen <= bno, error0);
1633 }
1634 }
1635
1636
1637
1638
1639 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1640 goto error0;
1641 if (haveright) {
1642
1643
1644
1645 if ((error = xfs_alloc_get_rec(bno_cur, >bno, >len, &i)))
1646 goto error0;
1647 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1648
1649
1650
1651 if (bno + len < gtbno)
1652 haveright = 0;
1653 else {
1654
1655
1656
1657
1658
1659 XFS_WANT_CORRUPTED_GOTO(mp, gtbno >= bno + len, error0);
1660 }
1661 }
1662
1663
1664
1665 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
1666
1667
1668
1669
1670 if (haveleft && haveright) {
1671
1672
1673
1674 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1675 goto error0;
1676 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1677 if ((error = xfs_btree_delete(cnt_cur, &i)))
1678 goto error0;
1679 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1680
1681
1682
1683 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1684 goto error0;
1685 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1686 if ((error = xfs_btree_delete(cnt_cur, &i)))
1687 goto error0;
1688 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1689
1690
1691
1692 if ((error = xfs_btree_delete(bno_cur, &i)))
1693 goto error0;
1694 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1695
1696
1697
1698 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1699 goto error0;
1700 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1701#ifdef DEBUG
1702
1703
1704
1705
1706 {
1707 xfs_agblock_t xxbno;
1708 xfs_extlen_t xxlen;
1709
1710 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1711 &i)))
1712 goto error0;
1713 XFS_WANT_CORRUPTED_GOTO(mp,
1714 i == 1 && xxbno == ltbno && xxlen == ltlen,
1715 error0);
1716 }
1717#endif
1718
1719
1720
1721 nbno = ltbno;
1722 nlen = len + ltlen + gtlen;
1723 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1724 goto error0;
1725 }
1726
1727
1728
1729
1730 else if (haveleft) {
1731
1732
1733
1734 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1735 goto error0;
1736 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1737 if ((error = xfs_btree_delete(cnt_cur, &i)))
1738 goto error0;
1739 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1740
1741
1742
1743
1744 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1745 goto error0;
1746 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1747 nbno = ltbno;
1748 nlen = len + ltlen;
1749 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1750 goto error0;
1751 }
1752
1753
1754
1755
1756 else if (haveright) {
1757
1758
1759
1760 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1761 goto error0;
1762 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1763 if ((error = xfs_btree_delete(cnt_cur, &i)))
1764 goto error0;
1765 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1766
1767
1768
1769
1770 nbno = bno;
1771 nlen = len + gtlen;
1772 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1773 goto error0;
1774 }
1775
1776
1777
1778
1779 else {
1780 nbno = bno;
1781 nlen = len;
1782 if ((error = xfs_btree_insert(bno_cur, &i)))
1783 goto error0;
1784 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1785 }
1786 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1787 bno_cur = NULL;
1788
1789
1790
1791 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1792 goto error0;
1793 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, error0);
1794 if ((error = xfs_btree_insert(cnt_cur, &i)))
1795 goto error0;
1796 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1797 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1798 cnt_cur = NULL;
1799
1800
1801
1802
1803 pag = xfs_perag_get(mp, agno);
1804 error = xfs_alloc_update_counters(tp, pag, agbp, len);
1805 xfs_perag_put(pag);
1806 if (error)
1807 goto error0;
1808
1809 if (!isfl)
1810 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1811 XFS_STATS_INC(xs_freex);
1812 XFS_STATS_ADD(xs_freeb, len);
1813
1814 trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
1815
1816 return 0;
1817
1818 error0:
1819 trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
1820 if (bno_cur)
1821 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1822 if (cnt_cur)
1823 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1824 return error;
1825}
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835void
1836xfs_alloc_compute_maxlevels(
1837 xfs_mount_t *mp)
1838{
1839 int level;
1840 uint maxblocks;
1841 uint maxleafents;
1842 int minleafrecs;
1843 int minnoderecs;
1844
1845 maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1846 minleafrecs = mp->m_alloc_mnr[0];
1847 minnoderecs = mp->m_alloc_mnr[1];
1848 maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1849 for (level = 1; maxblocks > 1; level++)
1850 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1851 mp->m_ag_maxlevels = level;
1852}
1853
1854
1855
1856
1857xfs_extlen_t
1858xfs_alloc_longest_free_extent(
1859 struct xfs_mount *mp,
1860 struct xfs_perag *pag,
1861 xfs_extlen_t need)
1862{
1863 xfs_extlen_t delta = 0;
1864
1865 if (need > pag->pagf_flcount)
1866 delta = need - pag->pagf_flcount;
1867
1868 if (pag->pagf_longest > delta)
1869 return pag->pagf_longest - delta;
1870 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1871}
1872
1873unsigned int
1874xfs_alloc_min_freelist(
1875 struct xfs_mount *mp,
1876 struct xfs_perag *pag)
1877{
1878 unsigned int min_free;
1879
1880
1881 min_free = min_t(unsigned int, pag->pagf_levels[XFS_BTNUM_BNOi] + 1,
1882 mp->m_ag_maxlevels);
1883
1884 min_free += min_t(unsigned int, pag->pagf_levels[XFS_BTNUM_CNTi] + 1,
1885 mp->m_ag_maxlevels);
1886
1887 return min_free;
1888}
1889
1890
1891
1892
1893
1894
1895
1896static bool
1897xfs_alloc_space_available(
1898 struct xfs_alloc_arg *args,
1899 xfs_extlen_t min_free,
1900 int flags)
1901{
1902 struct xfs_perag *pag = args->pag;
1903 xfs_extlen_t longest;
1904 int available;
1905
1906 if (flags & XFS_ALLOC_FLAG_FREEING)
1907 return true;
1908
1909
1910 longest = xfs_alloc_longest_free_extent(args->mp, pag, min_free);
1911 if ((args->minlen + args->alignment + args->minalignslop - 1) > longest)
1912 return false;
1913
1914
1915 available = (int)(pag->pagf_freeblks + pag->pagf_flcount -
1916 min_free - args->total);
1917 if (available < (int)args->minleft)
1918 return false;
1919
1920 return true;
1921}
1922
1923
1924
1925
1926
1927STATIC int
1928xfs_alloc_fix_freelist(
1929 struct xfs_alloc_arg *args,
1930 int flags)
1931{
1932 struct xfs_mount *mp = args->mp;
1933 struct xfs_perag *pag = args->pag;
1934 struct xfs_trans *tp = args->tp;
1935 struct xfs_buf *agbp = NULL;
1936 struct xfs_buf *agflbp = NULL;
1937 struct xfs_alloc_arg targs;
1938 xfs_agblock_t bno;
1939 xfs_extlen_t need;
1940 int error;
1941
1942 if (!pag->pagf_init) {
1943 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
1944 if (error)
1945 goto out_no_agbp;
1946 if (!pag->pagf_init) {
1947 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1948 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1949 goto out_agbp_relse;
1950 }
1951 }
1952
1953
1954
1955
1956
1957
1958 if (pag->pagf_metadata && args->userdata &&
1959 (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1960 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1961 goto out_agbp_relse;
1962 }
1963
1964 need = xfs_alloc_min_freelist(mp, pag);
1965 if (!xfs_alloc_space_available(args, need, flags))
1966 goto out_agbp_relse;
1967
1968
1969
1970
1971
1972 if (!agbp) {
1973 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
1974 if (error)
1975 goto out_no_agbp;
1976 if (!agbp) {
1977 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1978 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1979 goto out_no_agbp;
1980 }
1981 }
1982
1983
1984 need = xfs_alloc_min_freelist(mp, pag);
1985 if (!xfs_alloc_space_available(args, need, flags))
1986 goto out_agbp_relse;
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004 while (pag->pagf_flcount > need) {
2005 struct xfs_buf *bp;
2006
2007 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
2008 if (error)
2009 goto out_agbp_relse;
2010 error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1);
2011 if (error)
2012 goto out_agbp_relse;
2013 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
2014 xfs_trans_binval(tp, bp);
2015 }
2016
2017 memset(&targs, 0, sizeof(targs));
2018 targs.tp = tp;
2019 targs.mp = mp;
2020 targs.agbp = agbp;
2021 targs.agno = args->agno;
2022 targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
2023 targs.type = XFS_ALLOCTYPE_THIS_AG;
2024 targs.pag = pag;
2025 error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp);
2026 if (error)
2027 goto out_agbp_relse;
2028
2029
2030 while (pag->pagf_flcount < need) {
2031 targs.agbno = 0;
2032 targs.maxlen = need - pag->pagf_flcount;
2033
2034
2035 error = xfs_alloc_ag_vextent(&targs);
2036 if (error)
2037 goto out_agflbp_relse;
2038
2039
2040
2041
2042
2043
2044 if (targs.agbno == NULLAGBLOCK) {
2045 if (flags & XFS_ALLOC_FLAG_FREEING)
2046 break;
2047 goto out_agflbp_relse;
2048 }
2049
2050
2051
2052 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2053 error = xfs_alloc_put_freelist(tp, agbp,
2054 agflbp, bno, 0);
2055 if (error)
2056 goto out_agflbp_relse;
2057 }
2058 }
2059 xfs_trans_brelse(tp, agflbp);
2060 args->agbp = agbp;
2061 return 0;
2062
2063out_agflbp_relse:
2064 xfs_trans_brelse(tp, agflbp);
2065out_agbp_relse:
2066 if (agbp)
2067 xfs_trans_brelse(tp, agbp);
2068out_no_agbp:
2069 args->agbp = NULL;
2070 return error;
2071}
2072
2073
2074
2075
2076
2077int
2078xfs_alloc_get_freelist(
2079 xfs_trans_t *tp,
2080 xfs_buf_t *agbp,
2081 xfs_agblock_t *bnop,
2082 int btreeblk)
2083{
2084 xfs_agf_t *agf;
2085 xfs_buf_t *agflbp;
2086 xfs_agblock_t bno;
2087 __be32 *agfl_bno;
2088 int error;
2089 int logflags;
2090 xfs_mount_t *mp = tp->t_mountp;
2091 xfs_perag_t *pag;
2092
2093
2094
2095
2096 agf = XFS_BUF_TO_AGF(agbp);
2097 if (!agf->agf_flcount) {
2098 *bnop = NULLAGBLOCK;
2099 return 0;
2100 }
2101
2102
2103
2104 error = xfs_alloc_read_agfl(mp, tp, be32_to_cpu(agf->agf_seqno),
2105 &agflbp);
2106 if (error)
2107 return error;
2108
2109
2110
2111
2112
2113 agfl_bno = XFS_BUF_TO_AGFL_BNO(mp, agflbp);
2114 bno = be32_to_cpu(agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
2115 be32_add_cpu(&agf->agf_flfirst, 1);
2116 xfs_trans_brelse(tp, agflbp);
2117 if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
2118 agf->agf_flfirst = 0;
2119
2120 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2121 be32_add_cpu(&agf->agf_flcount, -1);
2122 xfs_trans_agflist_delta(tp, -1);
2123 pag->pagf_flcount--;
2124 xfs_perag_put(pag);
2125
2126 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2127 if (btreeblk) {
2128 be32_add_cpu(&agf->agf_btreeblks, 1);
2129 pag->pagf_btreeblks++;
2130 logflags |= XFS_AGF_BTREEBLKS;
2131 }
2132
2133 xfs_alloc_log_agf(tp, agbp, logflags);
2134 *bnop = bno;
2135
2136 return 0;
2137}
2138
2139
2140
2141
2142void
2143xfs_alloc_log_agf(
2144 xfs_trans_t *tp,
2145 xfs_buf_t *bp,
2146 int fields)
2147{
2148 int first;
2149 int last;
2150 static const short offsets[] = {
2151 offsetof(xfs_agf_t, agf_magicnum),
2152 offsetof(xfs_agf_t, agf_versionnum),
2153 offsetof(xfs_agf_t, agf_seqno),
2154 offsetof(xfs_agf_t, agf_length),
2155 offsetof(xfs_agf_t, agf_roots[0]),
2156 offsetof(xfs_agf_t, agf_levels[0]),
2157 offsetof(xfs_agf_t, agf_flfirst),
2158 offsetof(xfs_agf_t, agf_fllast),
2159 offsetof(xfs_agf_t, agf_flcount),
2160 offsetof(xfs_agf_t, agf_freeblks),
2161 offsetof(xfs_agf_t, agf_longest),
2162 offsetof(xfs_agf_t, agf_btreeblks),
2163 offsetof(xfs_agf_t, agf_uuid),
2164 sizeof(xfs_agf_t)
2165 };
2166
2167 trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2168
2169 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
2170
2171 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2172 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2173}
2174
2175
2176
2177
2178int
2179xfs_alloc_pagf_init(
2180 xfs_mount_t *mp,
2181 xfs_trans_t *tp,
2182 xfs_agnumber_t agno,
2183 int flags)
2184{
2185 xfs_buf_t *bp;
2186 int error;
2187
2188 if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2189 return error;
2190 if (bp)
2191 xfs_trans_brelse(tp, bp);
2192 return 0;
2193}
2194
2195
2196
2197
2198int
2199xfs_alloc_put_freelist(
2200 xfs_trans_t *tp,
2201 xfs_buf_t *agbp,
2202 xfs_buf_t *agflbp,
2203 xfs_agblock_t bno,
2204 int btreeblk)
2205{
2206 xfs_agf_t *agf;
2207 __be32 *blockp;
2208 int error;
2209 int logflags;
2210 xfs_mount_t *mp;
2211 xfs_perag_t *pag;
2212 __be32 *agfl_bno;
2213 int startoff;
2214
2215 agf = XFS_BUF_TO_AGF(agbp);
2216 mp = tp->t_mountp;
2217
2218 if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2219 be32_to_cpu(agf->agf_seqno), &agflbp)))
2220 return error;
2221 be32_add_cpu(&agf->agf_fllast, 1);
2222 if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
2223 agf->agf_fllast = 0;
2224
2225 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2226 be32_add_cpu(&agf->agf_flcount, 1);
2227 xfs_trans_agflist_delta(tp, 1);
2228 pag->pagf_flcount++;
2229
2230 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2231 if (btreeblk) {
2232 be32_add_cpu(&agf->agf_btreeblks, -1);
2233 pag->pagf_btreeblks--;
2234 logflags |= XFS_AGF_BTREEBLKS;
2235 }
2236 xfs_perag_put(pag);
2237
2238 xfs_alloc_log_agf(tp, agbp, logflags);
2239
2240 ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2241
2242 agfl_bno = XFS_BUF_TO_AGFL_BNO(mp, agflbp);
2243 blockp = &agfl_bno[be32_to_cpu(agf->agf_fllast)];
2244 *blockp = cpu_to_be32(bno);
2245 startoff = (char *)blockp - (char *)agflbp->b_addr;
2246
2247 xfs_alloc_log_agf(tp, agbp, logflags);
2248
2249 xfs_trans_buf_set_type(tp, agflbp, XFS_BLFT_AGFL_BUF);
2250 xfs_trans_log_buf(tp, agflbp, startoff,
2251 startoff + sizeof(xfs_agblock_t) - 1);
2252 return 0;
2253}
2254
2255static bool
2256xfs_agf_verify(
2257 struct xfs_mount *mp,
2258 struct xfs_buf *bp)
2259 {
2260 struct xfs_agf *agf = XFS_BUF_TO_AGF(bp);
2261
2262 if (xfs_sb_version_hascrc(&mp->m_sb) &&
2263 !uuid_equal(&agf->agf_uuid, &mp->m_sb.sb_uuid))
2264 return false;
2265
2266 if (!(agf->agf_magicnum == cpu_to_be32(XFS_AGF_MAGIC) &&
2267 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2268 be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2269 be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2270 be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
2271 be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp)))
2272 return false;
2273
2274 if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) > XFS_BTREE_MAXLEVELS ||
2275 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) > XFS_BTREE_MAXLEVELS)
2276 return false;
2277
2278
2279
2280
2281
2282
2283
2284 if (bp->b_pag && be32_to_cpu(agf->agf_seqno) != bp->b_pag->pag_agno)
2285 return false;
2286
2287 if (xfs_sb_version_haslazysbcount(&mp->m_sb) &&
2288 be32_to_cpu(agf->agf_btreeblks) > be32_to_cpu(agf->agf_length))
2289 return false;
2290
2291 return true;;
2292
2293}
2294
2295static void
2296xfs_agf_read_verify(
2297 struct xfs_buf *bp)
2298{
2299 struct xfs_mount *mp = bp->b_target->bt_mount;
2300
2301 if (xfs_sb_version_hascrc(&mp->m_sb) &&
2302 !xfs_buf_verify_cksum(bp, XFS_AGF_CRC_OFF))
2303 xfs_buf_ioerror(bp, -EFSBADCRC);
2304 else if (XFS_TEST_ERROR(!xfs_agf_verify(mp, bp), mp,
2305 XFS_ERRTAG_ALLOC_READ_AGF,
2306 XFS_RANDOM_ALLOC_READ_AGF))
2307 xfs_buf_ioerror(bp, -EFSCORRUPTED);
2308
2309 if (bp->b_error)
2310 xfs_verifier_error(bp);
2311}
2312
2313static void
2314xfs_agf_write_verify(
2315 struct xfs_buf *bp)
2316{
2317 struct xfs_mount *mp = bp->b_target->bt_mount;
2318 struct xfs_buf_log_item *bip = bp->b_fspriv;
2319
2320 if (!xfs_agf_verify(mp, bp)) {
2321 xfs_buf_ioerror(bp, -EFSCORRUPTED);
2322 xfs_verifier_error(bp);
2323 return;
2324 }
2325
2326 if (!xfs_sb_version_hascrc(&mp->m_sb))
2327 return;
2328
2329 if (bip)
2330 XFS_BUF_TO_AGF(bp)->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2331
2332 xfs_buf_update_cksum(bp, XFS_AGF_CRC_OFF);
2333}
2334
2335const struct xfs_buf_ops xfs_agf_buf_ops = {
2336 .verify_read = xfs_agf_read_verify,
2337 .verify_write = xfs_agf_write_verify,
2338};
2339
2340
2341
2342
2343int
2344xfs_read_agf(
2345 struct xfs_mount *mp,
2346 struct xfs_trans *tp,
2347 xfs_agnumber_t agno,
2348 int flags,
2349 struct xfs_buf **bpp)
2350{
2351 int error;
2352
2353 trace_xfs_read_agf(mp, agno);
2354
2355 ASSERT(agno != NULLAGNUMBER);
2356 error = xfs_trans_read_buf(
2357 mp, tp, mp->m_ddev_targp,
2358 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
2359 XFS_FSS_TO_BB(mp, 1), flags, bpp, &xfs_agf_buf_ops);
2360 if (error)
2361 return error;
2362 if (!*bpp)
2363 return 0;
2364
2365 ASSERT(!(*bpp)->b_error);
2366 xfs_buf_set_ref(*bpp, XFS_AGF_REF);
2367 return 0;
2368}
2369
2370
2371
2372
2373int
2374xfs_alloc_read_agf(
2375 struct xfs_mount *mp,
2376 struct xfs_trans *tp,
2377 xfs_agnumber_t agno,
2378 int flags,
2379 struct xfs_buf **bpp)
2380{
2381 struct xfs_agf *agf;
2382 struct xfs_perag *pag;
2383 int error;
2384
2385 trace_xfs_alloc_read_agf(mp, agno);
2386
2387 ASSERT(agno != NULLAGNUMBER);
2388 error = xfs_read_agf(mp, tp, agno,
2389 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
2390 bpp);
2391 if (error)
2392 return error;
2393 if (!*bpp)
2394 return 0;
2395 ASSERT(!(*bpp)->b_error);
2396
2397 agf = XFS_BUF_TO_AGF(*bpp);
2398 pag = xfs_perag_get(mp, agno);
2399 if (!pag->pagf_init) {
2400 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
2401 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
2402 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2403 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
2404 pag->pagf_levels[XFS_BTNUM_BNOi] =
2405 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
2406 pag->pagf_levels[XFS_BTNUM_CNTi] =
2407 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
2408 spin_lock_init(&pag->pagb_lock);
2409 pag->pagb_count = 0;
2410 pag->pagb_tree = RB_ROOT;
2411 pag->pagf_init = 1;
2412 }
2413#ifdef DEBUG
2414 else if (!XFS_FORCED_SHUTDOWN(mp)) {
2415 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
2416 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
2417 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2418 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
2419 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
2420 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
2421 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
2422 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
2423 }
2424#endif
2425 xfs_perag_put(pag);
2426 return 0;
2427}
2428
2429
2430
2431
2432
2433
2434int
2435xfs_alloc_vextent(
2436 xfs_alloc_arg_t *args)
2437{
2438 xfs_agblock_t agsize;
2439 int error;
2440 int flags;
2441 xfs_extlen_t minleft;
2442 xfs_mount_t *mp;
2443 xfs_agnumber_t sagno;
2444 xfs_alloctype_t type;
2445 int bump_rotor = 0;
2446 int no_min = 0;
2447 xfs_agnumber_t rotorstep = xfs_rotorstep;
2448
2449 mp = args->mp;
2450 type = args->otype = args->type;
2451 args->agbno = NULLAGBLOCK;
2452
2453
2454
2455
2456
2457 agsize = mp->m_sb.sb_agblocks;
2458 if (args->maxlen > agsize)
2459 args->maxlen = agsize;
2460 if (args->alignment == 0)
2461 args->alignment = 1;
2462 ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2463 ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2464 ASSERT(args->minlen <= args->maxlen);
2465 ASSERT(args->minlen <= agsize);
2466 ASSERT(args->mod < args->prod);
2467 if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2468 XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2469 args->minlen > args->maxlen || args->minlen > agsize ||
2470 args->mod >= args->prod) {
2471 args->fsbno = NULLFSBLOCK;
2472 trace_xfs_alloc_vextent_badargs(args);
2473 return 0;
2474 }
2475 minleft = args->minleft;
2476
2477 switch (type) {
2478 case XFS_ALLOCTYPE_THIS_AG:
2479 case XFS_ALLOCTYPE_NEAR_BNO:
2480 case XFS_ALLOCTYPE_THIS_BNO:
2481
2482
2483
2484 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2485 args->pag = xfs_perag_get(mp, args->agno);
2486 args->minleft = 0;
2487 error = xfs_alloc_fix_freelist(args, 0);
2488 args->minleft = minleft;
2489 if (error) {
2490 trace_xfs_alloc_vextent_nofix(args);
2491 goto error0;
2492 }
2493 if (!args->agbp) {
2494 trace_xfs_alloc_vextent_noagbp(args);
2495 break;
2496 }
2497 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2498 if ((error = xfs_alloc_ag_vextent(args)))
2499 goto error0;
2500 break;
2501 case XFS_ALLOCTYPE_START_BNO:
2502
2503
2504
2505
2506 if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
2507 (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2508 args->fsbno = XFS_AGB_TO_FSB(mp,
2509 ((mp->m_agfrotor / rotorstep) %
2510 mp->m_sb.sb_agcount), 0);
2511 bump_rotor = 1;
2512 }
2513 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2514 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2515
2516 case XFS_ALLOCTYPE_ANY_AG:
2517 case XFS_ALLOCTYPE_START_AG:
2518 case XFS_ALLOCTYPE_FIRST_AG:
2519
2520
2521
2522 if (type == XFS_ALLOCTYPE_ANY_AG) {
2523
2524
2525
2526 args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2527 mp->m_sb.sb_agcount;
2528 args->type = XFS_ALLOCTYPE_THIS_AG;
2529 flags = XFS_ALLOC_FLAG_TRYLOCK;
2530 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2531
2532
2533
2534 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2535 args->type = XFS_ALLOCTYPE_THIS_AG;
2536 sagno = 0;
2537 flags = 0;
2538 } else {
2539 if (type == XFS_ALLOCTYPE_START_AG)
2540 args->type = XFS_ALLOCTYPE_THIS_AG;
2541
2542
2543
2544 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2545 flags = XFS_ALLOC_FLAG_TRYLOCK;
2546 }
2547
2548
2549
2550
2551 for (;;) {
2552 args->pag = xfs_perag_get(mp, args->agno);
2553 if (no_min) args->minleft = 0;
2554 error = xfs_alloc_fix_freelist(args, flags);
2555 args->minleft = minleft;
2556 if (error) {
2557 trace_xfs_alloc_vextent_nofix(args);
2558 goto error0;
2559 }
2560
2561
2562
2563 if (args->agbp) {
2564 if ((error = xfs_alloc_ag_vextent(args)))
2565 goto error0;
2566 break;
2567 }
2568
2569 trace_xfs_alloc_vextent_loopfailed(args);
2570
2571
2572
2573
2574 if (args->agno == sagno &&
2575 type == XFS_ALLOCTYPE_START_BNO)
2576 args->type = XFS_ALLOCTYPE_THIS_AG;
2577
2578
2579
2580
2581
2582
2583
2584 if (++(args->agno) == mp->m_sb.sb_agcount) {
2585 if (args->firstblock != NULLFSBLOCK)
2586 args->agno = sagno;
2587 else
2588 args->agno = 0;
2589 }
2590
2591
2592
2593
2594 if (args->agno == sagno) {
2595 if (no_min == 1) {
2596 args->agbno = NULLAGBLOCK;
2597 trace_xfs_alloc_vextent_allfailed(args);
2598 break;
2599 }
2600 if (flags == 0) {
2601 no_min = 1;
2602 } else {
2603 flags = 0;
2604 if (type == XFS_ALLOCTYPE_START_BNO) {
2605 args->agbno = XFS_FSB_TO_AGBNO(mp,
2606 args->fsbno);
2607 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2608 }
2609 }
2610 }
2611 xfs_perag_put(args->pag);
2612 }
2613 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2614 if (args->agno == sagno)
2615 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2616 (mp->m_sb.sb_agcount * rotorstep);
2617 else
2618 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2619 (mp->m_sb.sb_agcount * rotorstep);
2620 }
2621 break;
2622 default:
2623 ASSERT(0);
2624
2625 }
2626 if (args->agbno == NULLAGBLOCK)
2627 args->fsbno = NULLFSBLOCK;
2628 else {
2629 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2630#ifdef DEBUG
2631 ASSERT(args->len >= args->minlen);
2632 ASSERT(args->len <= args->maxlen);
2633 ASSERT(args->agbno % args->alignment == 0);
2634 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2635 args->len);
2636#endif
2637 }
2638 xfs_perag_put(args->pag);
2639 return 0;
2640error0:
2641 xfs_perag_put(args->pag);
2642 return error;
2643}
2644
2645
2646
2647
2648
2649
2650int
2651xfs_free_extent(
2652 xfs_trans_t *tp,
2653 xfs_fsblock_t bno,
2654 xfs_extlen_t len)
2655{
2656 xfs_alloc_arg_t args;
2657 int error;
2658
2659 ASSERT(len != 0);
2660 memset(&args, 0, sizeof(xfs_alloc_arg_t));
2661 args.tp = tp;
2662 args.mp = tp->t_mountp;
2663
2664
2665
2666
2667
2668 args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
2669 if (args.agno >= args.mp->m_sb.sb_agcount)
2670 return -EFSCORRUPTED;
2671
2672 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
2673 if (args.agbno >= args.mp->m_sb.sb_agblocks)
2674 return -EFSCORRUPTED;
2675
2676 args.pag = xfs_perag_get(args.mp, args.agno);
2677 ASSERT(args.pag);
2678
2679 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2680 if (error)
2681 goto error0;
2682
2683
2684 if (args.agbno + len >
2685 be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
2686 error = -EFSCORRUPTED;
2687 goto error0;
2688 }
2689
2690 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
2691 if (!error)
2692 xfs_extent_busy_insert(tp, args.agno, args.agbno, len, 0);
2693error0:
2694 xfs_perag_put(args.pag);
2695 return error;
2696}
2697