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