?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
sh: use declared coherent memory for dreamcast pci ethernet adapter
[linux-2.6/mini2440.git] / fs / xfs / xfs_alloc.c
blob012a649a19c35c2fc68e0b953557b92f42df83b7
1 /*
2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
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
48 STATIC int
49 xfs_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)
55 ktrace_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 /* XFS_ALLOC_TRACE */
77
78 /*
79 * Prototypes for per-ag allocation routines
80 */
81
82 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
83 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
84 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
85 STATIC 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 * Internal functions.
90 */
91
92 /*
93 * Compute aligned version of the found extent.
94 * Takes alignment and min length into account.
95 */
96 STATIC int /* success (>= minlen) */
97 xfs_alloc_compute_aligned(
98 xfs_agblock_t foundbno, /* starting block in found extent */
99 xfs_extlen_t foundlen, /* length in found extent */
100 xfs_extlen_t alignment, /* alignment for allocation */
101 xfs_extlen_t minlen, /* minimum length for allocation */
102 xfs_agblock_t *resbno, /* result block number */
103 xfs_extlen_t *reslen) /* result length */
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 * Compute best start block and diff for "near" allocations.
124 * freelen >= wantlen already checked by caller.
125 */
126 STATIC xfs_extlen_t /* difference value (absolute) */
127 xfs_alloc_compute_diff(
128 xfs_agblock_t wantbno, /* target starting block */
129 xfs_extlen_t wantlen, /* target length */
130 xfs_extlen_t alignment, /* target alignment */
131 xfs_agblock_t freebno, /* freespace's starting block */
132 xfs_extlen_t freelen, /* freespace's length */
133 xfs_agblock_t *newbnop) /* result: best start block from free */
134 {
135 xfs_agblock_t freeend; /* end of freespace extent */
136 xfs_agblock_t newbno1; /* return block number */
137 xfs_agblock_t newbno2; /* other new block number */
138 xfs_extlen_t newlen1=0; /* length with newbno1 */
139 xfs_extlen_t newlen2=0; /* length with newbno2 */
140 xfs_agblock_t wantend; /* end of target extent */
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 * Fix up the length, based on mod and prod.
184 * len should be k * prod + mod for some k.
185 * If len is too small it is returned unchanged.
186 * If len hits maxlen it is left alone.
187 */
188 STATIC void
189 xfs_alloc_fix_len(
190 xfs_alloc_arg_t *args) /* allocation argument structure */
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 * Fix up length if there is too little space left in the a.g.
220 * Return 1 if ok, 0 if too little, should give up.
221 */
222 STATIC int
223 xfs_alloc_fix_minleft(
224 xfs_alloc_arg_t *args) /* allocation argument structure */
225 {
226 xfs_agf_t *agf; /* a.g. freelist header */
227 int diff; /* free space difference */
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; /* shrink the allocated space */
238 if (args->len >= args->minlen)
239 return 1;
240 args->agbno = NULLAGBLOCK;
241 return 0;
242 }
243
244 /*
245 * Update the two btrees, logically removing from freespace the extent
246 * starting at rbno, rlen blocks. The extent is contained within the
247 * actual (current) free extent fbno for flen blocks.
248 * Flags are passed in indicating whether the cursors are set to the
249 * relevant records.
250 */
251 STATIC int /* error code */
252 xfs_alloc_fixup_trees(
253 xfs_btree_cur_t *cnt_cur, /* cursor for by-size btree */
254 xfs_btree_cur_t *bno_cur, /* cursor for by-block btree */
255 xfs_agblock_t fbno, /* starting block of free extent */
256 xfs_extlen_t flen, /* length of free extent */
257 xfs_agblock_t rbno, /* starting block of returned extent */
258 xfs_extlen_t rlen, /* length of returned extent */
259 int flags) /* flags, XFSA_FIXUP_... */
260 {
261 int error; /* error code */
262 int i; /* operation results */
263 xfs_agblock_t nfbno1; /* first new free startblock */
264 xfs_agblock_t nfbno2; /* second new free startblock */
265 xfs_extlen_t nflen1=0; /* first new free length */
266 xfs_extlen_t nflen2=0; /* second new free length */
267
268 /*
269 * Look up the record in the by-size tree if necessary.
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 * Look up the record in the by-block tree if necessary.
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 * Deal with all four cases: the allocated record is contained
315 * within the freespace record, so we can have new freespace
316 * at either (or both) end, or no freespace remaining.
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 * Delete the entry from the by-size btree.
336 */
337 if ((error = xfs_alloc_delete(cnt_cur, &i)))
338 return error;
339 XFS_WANT_CORRUPTED_RETURN(i == 1);
340 /*
341 * Add new by-size btree entry(s).
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 * Fix up the by-block btree entry(s).
361 */
362 if (nfbno1 == NULLAGBLOCK) {
363 /*
364 * No remaining freespace, just delete the by-block tree entry.
365 */
366 if ((error = xfs_alloc_delete(bno_cur, &i)))
367 return error;
368 XFS_WANT_CORRUPTED_RETURN(i == 1);
369 } else {
370 /*
371 * Update the by-block entry to start later|be shorter.
372 */
373 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
374 return error;
375 }
376 if (nfbno2 != NULLAGBLOCK) {
377 /*
378 * 2 resulting free entries, need to add one.
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 * Read in the allocation group free block array.
392 */
393 STATIC int /* error */
394 xfs_alloc_read_agfl(
395 xfs_mount_t *mp, /* mount point structure */
396 xfs_trans_t *tp, /* transaction pointer */
397 xfs_agnumber_t agno, /* allocation group number */
398 xfs_buf_t **bpp) /* buffer for the ag free block array */
399 {
400 xfs_buf_t *bp; /* return value */
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 * Add an allocation trace entry for an alloc call.
420 */
421 STATIC void
422 xfs_alloc_trace_alloc(
423 const char *name, /* function tag string */
424 char *str, /* additional string */
425 xfs_alloc_arg_t *args, /* allocation argument structure */
426 int line) /* source line number */
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 * Add an allocation trace entry for a free call.
453 */
454 STATIC void
455 xfs_alloc_trace_free(
456 const char *name, /* function tag string */
457 char *str, /* additional string */
458 xfs_mount_t *mp, /* file system mount point */
459 xfs_agnumber_t agno, /* allocation group number */
460 xfs_agblock_t agbno, /* a.g. relative block number */
461 xfs_extlen_t len, /* length of extent */
462 int isfl, /* set if is freelist allocation/free */
463 int line) /* source line number */
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 * Add an allocation trace entry for modifying an agf.
479 */
480 STATIC void
481 xfs_alloc_trace_modagf(
482 const char *name, /* function tag string */
483 char *str, /* additional string */
484 xfs_mount_t *mp, /* file system mount point */
485 xfs_agf_t *agf, /* new agf value */
486 int flags, /* logging flags for agf */
487 int line) /* source line number */
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
508 STATIC void
509 xfs_alloc_trace_busy(
510 const char *name, /* function tag string */
511 char *str, /* additional string */
512 xfs_mount_t *mp, /* file system mount point */
513 xfs_agnumber_t agno, /* allocation group number */
514 xfs_agblock_t agbno, /* a.g. relative block number */
515 xfs_extlen_t len, /* length of extent */
516 int slot, /* perag Busy slot */
517 xfs_trans_t *tp,
518 int trtype, /* type: add, delete, search */
519 int line) /* source line number */
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 /* XFS_ALLOC_TRACE */
534
535 /*
536 * Allocation group level functions.
537 */
538
539 /*
540 * Allocate a variable extent in the allocation group agno.
541 * Type and bno are used to determine where in the allocation group the
542 * extent will start.
543 * Extent's length (returned in *len) will be between minlen and maxlen,
544 * and of the form k * prod + mod unless there's nothing that large.
545 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
546 */
547 STATIC int /* error */
548 xfs_alloc_ag_vextent(
549 xfs_alloc_arg_t *args) /* argument structure for allocation */
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 * Branch to correct routine based on the type.
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 /* NOTREACHED */
575 }
576 if (error)
577 return error;
578 /*
579 * If the allocation worked, need to change the agf structure
580 * (and log it), and the superblock.
581 */
582 if (args->agbno != NULLAGBLOCK) {
583 xfs_agf_t *agf; /* allocation group freelist header */
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 /* search the busylist for these blocks */
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 * Allocate a variable extent at exactly agno/bno.
620 * Extent's length (returned in *len) will be between minlen and maxlen,
621 * and of the form k * prod + mod unless there's nothing that large.
622 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
623 */
624 STATIC int /* error */
625 xfs_alloc_ag_vextent_exact(
626 xfs_alloc_arg_t *args) /* allocation argument structure */
627 {
628 xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
629 xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
630 xfs_agblock_t end; /* end of allocated extent */
631 int error;
632 xfs_agblock_t fbno; /* start block of found extent */
633 xfs_agblock_t fend; /* end block of found extent */
634 xfs_extlen_t flen; /* length of found extent */
635 int i; /* success/failure of operation */
636 xfs_agblock_t maxend; /* end of maximal extent */
637 xfs_agblock_t minend; /* end of minimal extent */
638 xfs_extlen_t rlen; /* length of returned extent */
639
640 ASSERT(args->alignment == 1);
641 /*
642 * Allocate/initialize a cursor for the by-number freespace btree.
643 */
644 bno_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
645 args->agno, XFS_BTNUM_BNO, NULL, 0);
646 /*
647 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
648 * Look for the closest free block <= bno, it must contain bno
649 * if any free block does.
650 */
651 if ((error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i)))
652 goto error0;
653 if (!i) {
654 /*
655 * Didn't find it, return null.
656 */
657 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
658 args->agbno = NULLAGBLOCK;
659 return 0;
660 }
661 /*
662 * Grab the freespace record.
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 * Give up if the freespace isn't long enough for the minimum request.
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 * End of extent will be smaller of the freespace end and the
681 * maximal requested end.
682 */
683 end = XFS_AGBLOCK_MIN(fend, maxend);
684 /*
685 * Fix the length according to mod and prod if given.
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 * We are allocating agbno for rlen [agbno .. end]
698 * Allocate/initialize a cursor for the by-size btree.
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
715 error0:
716 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
717 TRACE_ALLOC("error", args);
718 return error;
719 }
720
721 /*
722 * Allocate a variable extent near bno in the allocation group agno.
723 * Extent's length (returned in len) will be between minlen and maxlen,
724 * and of the form k * prod + mod unless there's nothing that large.
725 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
726 */
727 STATIC int /* error */
728 xfs_alloc_ag_vextent_near(
729 xfs_alloc_arg_t *args) /* allocation argument structure */
730 {
731 xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
732 xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
733 xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
734 xfs_agblock_t gtbno; /* start bno of right side entry */
735 xfs_agblock_t gtbnoa; /* aligned ... */
736 xfs_extlen_t gtdiff; /* difference to right side entry */
737 xfs_extlen_t gtlen; /* length of right side entry */
738 xfs_extlen_t gtlena; /* aligned ... */
739 xfs_agblock_t gtnew; /* useful start bno of right side */
740 int error; /* error code */
741 int i; /* result code, temporary */
742 int j; /* result code, temporary */
743 xfs_agblock_t ltbno; /* start bno of left side entry */
744 xfs_agblock_t ltbnoa; /* aligned ... */
745 xfs_extlen_t ltdiff; /* difference to left side entry */
746 /*REFERENCED*/
747 xfs_agblock_t ltend; /* end bno of left side entry */
748 xfs_extlen_t ltlen; /* length of left side entry */
749 xfs_extlen_t ltlena; /* aligned ... */
750 xfs_agblock_t ltnew; /* useful start bno of left side */
751 xfs_extlen_t rlen; /* length of returned extent */
752 #if defined(DEBUG) && defined(__KERNEL__)
753 /*
754 * Randomly don't execute the first algorithm.
755 */
756 int dofirst; /* set to do first algorithm */
757
758 dofirst = random32() & 1;
759 #endif
760 /*
761 * Get a cursor for the by-size btree.
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 * See if there are any free extents as big as maxlen.
769 */
770 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
771 goto error0;
772 /*
773 * If none, then pick up the last entry in the tree unless the
774 * tree is empty.
775 */
776 if (!i) {
777 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
778 &ltlen, &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 * First algorithm.
789 * If the requested extent is large wrt the freespaces available
790 * in this a.g., then the cursor will be pointing to a btree entry
791 * near the right edge of the tree. If it's in the last btree leaf
792 * block, then we just examine all the entries in that block
793 * that are big enough, and pick the best one.
794 * This is written as a while loop so we can break out of it,
795 * but we never loop back to the top.
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 * Start from the entry that lookup found, sequence through
809 * all larger free blocks. If we're actually pointing at a
810 * record smaller than maxlen, go to the start of this block,
811 * and skip all those smaller than minlen.
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, &ltbno,
817 &ltlen, &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 * For each entry, decide if it's better than
835 * the previous best entry.
836 */
837 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &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 &ltbnoa, &ltlena))
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, &ltnew);
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 * It didn't work. We COULD be in a case where
861 * there's a good record somewhere, so try again.
862 */
863 if (blen == 0)
864 break;
865 /*
866 * Point at the best entry, and retrieve it again.
867 */
868 cnt_cur->bc_ptrs[0] = besti;
869 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &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 * We are allocating starting at bnew for blen blocks.
883 */
884 args->agbno = bnew;
885 ASSERT(bnew >= ltbno);
886 ASSERT(bnew + blen <= ltend);
887 /*
888 * Set up a cursor for the by-bno tree.
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 * Fix up the btree entries.
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 * Second algorithm.
905 * Search in the by-bno tree to the left and to the right
906 * simultaneously, until in each case we find a space big enough,
907 * or run into the edge of the tree. When we run into the edge,
908 * we deallocate that cursor.
909 * If both searches succeed, we compare the two spaces and pick
910 * the better one.
911 * With alignment, it's possible for both to fail; the upper
912 * level algorithm that picks allocation groups for allocations
913 * is not supposed to do this.
914 */
915 /*
916 * Allocate and initialize the cursor for the leftward search.
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 * Lookup <= bno to find the leftward search's starting point.
922 */
923 if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
924 goto error0;
925 if (!i) {
926 /*
927 * Didn't find anything; use this cursor for the rightward
928 * search.
929 */
930 bno_cur_gt = bno_cur_lt;
931 bno_cur_lt = NULL;
932 }
933 /*
934 * Found something. Duplicate the cursor for the rightward search.
935 */
936 else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
937 goto error0;
938 /*
939 * Increment the cursor, so we will point at the entry just right
940 * of the leftward entry if any, or to the leftmost entry.
941 */
942 if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
943 goto error0;
944 if (!i) {
945 /*
946 * It failed, there are no rightward entries.
947 */
948 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
949 bno_cur_gt = NULL;
950 }
951 /*
952 * Loop going left with the leftward cursor, right with the
953 * rightward cursor, until either both directions give up or
954 * we find an entry at least as big as minlen.
955 */
956 do {
957 if (bno_cur_lt) {
958 if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &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 &ltbnoa, &ltlena))
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, &gtbno, &gtlen, &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 &gtbnoa, &gtlena))
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 * Got both cursors still active, need to find better entry.
992 */
993 if (bno_cur_lt && bno_cur_gt) {
994 /*
995 * Left side is long enough, look for a right side entry.
996 */
997 if (ltlena >= args->minlen) {
998 /*
999 * Fix up the length.
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, &ltnew);
1006 /*
1007 * Not perfect.
1008 */
1009 if (ltdiff) {
1010 /*
1011 * Look until we find a better one, run out of
1012 * space, or run off the end.
1013 */
1014 while (bno_cur_lt && bno_cur_gt) {
1015 if ((error = xfs_alloc_get_rec(
1016 bno_cur_gt, &gtbno,
1017 &gtlen, &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 &gtbnoa, &gtlena);
1023 /*
1024 * The left one is clearly better.
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 * If we reach a big enough entry,
1035 * compare the two and pick the best.
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, &gtnew);
1047 /*
1048 * Right side is better.
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 * Left side is better.
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 * Fell off the right end.
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 * The left side is perfect, trash the right side.
1084 */
1085 else {
1086 xfs_btree_del_cursor(bno_cur_gt,
1087 XFS_BTREE_NOERROR);
1088 bno_cur_gt = NULL;
1089 }
1090 }
1091 /*
1092 * It's the right side that was found first, look left.
1093 */
1094 else {
1095 /*
1096 * Fix up the length.
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, &gtnew);
1103 /*
1104 * Right side entry isn't perfect.
1105 */
1106 if (gtdiff) {
1107 /*
1108 * Look until we find a better one, run out of
1109 * space, or run off the end.
1110 */
1111 while (bno_cur_lt && bno_cur_gt) {
1112 if ((error = xfs_alloc_get_rec(
1113 bno_cur_lt, &ltbno,
1114 &ltlen, &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 &ltbnoa, &ltlena);
1120 /*
1121 * The right one is clearly better.
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 * If we reach a big enough entry,
1132 * compare the two and pick the best.
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, &ltnew);
1143 /*
1144 * Left side is better.
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 * Right side is better.
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 * Fell off the left end.
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 * The right side is perfect, trash the left side.
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 * If we couldn't get anything, give up.
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 * At this point we have selected a freespace entry, either to the
1197 * left or to the right. If it's on the right, copy all the
1198 * useful variables to the "left" set so we only have one
1199 * copy of this code.
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 * Fix up the length and compute the useful address.
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, &ltnew);
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 * Allocate a variable extent anywhere in the allocation group agno.
1251 * Extent's length (returned in len) will be between minlen and maxlen,
1252 * and of the form k * prod + mod unless there's nothing that large.
1253 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1254 */
1255 STATIC int /* error */
1256 xfs_alloc_ag_vextent_size(
1257 xfs_alloc_arg_t *args) /* allocation argument structure */
1258 {
1259 xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
1260 xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
1261 int error; /* error result */
1262 xfs_agblock_t fbno; /* start of found freespace */
1263 xfs_extlen_t flen; /* length of found freespace */
1264 int i; /* temp status variable */
1265 xfs_agblock_t rbno; /* returned block number */
1266 xfs_extlen_t rlen; /* length of returned extent */
1267
1268 /*
1269 * Allocate and initialize a cursor for the by-size btree.
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 * Look for an entry >= maxlen+alignment-1 blocks.
1276 */
1277 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1278 args->maxlen + args->alignment - 1, &i)))
1279 goto error0;
1280 /*
1281 * If none, then pick up the last entry in the tree unless the
1282 * tree is empty.
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 * There's a freespace as big as maxlen+alignment-1, get it.
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 * In the first case above, we got the last entry in the
1305 * by-size btree. Now we check to see if the space hits maxlen
1306 * once aligned; if not, we search left for something better.
1307 * This can't happen in the second case above.
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 * Fix up the length.
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 * Allocate and initialize a cursor for the by-block tree.
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
1393 error0:
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 * Deal with the case where only small freespaces remain.
1404 * Either return the contents of the last freespace record,
1405 * or allocate space from the freelist if there is nothing in the tree.
1406 */
1407 STATIC int /* error */
1408 xfs_alloc_ag_vextent_small(
1409 xfs_alloc_arg_t *args, /* allocation argument structure */
1410 xfs_btree_cur_t *ccur, /* by-size cursor */
1411 xfs_agblock_t *fbnop, /* result block number */
1412 xfs_extlen_t *flenp, /* result length */
1413 int *stat) /* status: 0-freelist, 1-normal/none */
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 * Nothing in the btree, try the freelist. Make sure
1429 * to respect minleft even when pulling from the
1430 * freelist.
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 * Nothing in the freelist.
1459 */
1460 else
1461 flen = 0;
1462 }
1463 /*
1464 * Can't allocate from the freelist for some reason.
1465 */
1466 else {
1467 fbno = NULLAGBLOCK;
1468 flen = 0;
1469 }
1470 /*
1471 * Can't do the allocation, give up.
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
1484 error0:
1485 TRACE_ALLOC("error", args);
1486 return error;
1487 }
1488
1489 /*
1490 * Free the extent starting at agno/bno for length.
1491 */
1492 STATIC int /* error */
1493 xfs_free_ag_extent(
1494 xfs_trans_t *tp, /* transaction pointer */
1495 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
1496 xfs_agnumber_t agno, /* allocation group number */
1497 xfs_agblock_t bno, /* starting block number */
1498 xfs_extlen_t len, /* length of extent */
1499 int isfl) /* set if is freelist blocks - no sb acctg */
1500 {
1501 xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
1502 xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
1503 int error; /* error return value */
1504 xfs_agblock_t gtbno; /* start of right neighbor block */
1505 xfs_extlen_t gtlen; /* length of right neighbor block */
1506 int haveleft; /* have a left neighbor block */
1507 int haveright; /* have a right neighbor block */
1508 int i; /* temp, result code */
1509 xfs_agblock_t ltbno; /* start of left neighbor block */
1510 xfs_extlen_t ltlen; /* length of left neighbor block */
1511 xfs_mount_t *mp; /* mount point struct for filesystem */
1512 xfs_agblock_t nbno; /* new starting block of freespace */
1513 xfs_extlen_t nlen; /* new length of freespace */
1514
1515 mp = tp->t_mountp;
1516 /*
1517 * Allocate and initialize a cursor for the by-block btree.
1518 */
1519 bno_cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO, NULL,
1520 0);
1521 cnt_cur = NULL;
1522 /*
1523 * Look for a neighboring block on the left (lower block numbers)
1524 * that is contiguous with this space.
1525 */
1526 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1527 goto error0;
1528 if (haveleft) {
1529 /*
1530 * There is a block to our left.
1531 */
1532 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1533 goto error0;
1534 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1535 /*
1536 * It's not contiguous, though.
1537 */
1538 if (ltbno + ltlen < bno)
1539 haveleft = 0;
1540 else {
1541 /*
1542 * If this failure happens the request to free this
1543 * space was invalid, it's (partly) already free.
1544 * Very bad.
1545 */
1546 XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1547 }
1548 }
1549 /*
1550 * Look for a neighboring block on the right (higher block numbers)
1551 * that is contiguous with this space.
1552 */
1553 if ((error = xfs_alloc_increment(bno_cur, 0, &haveright)))
1554 goto error0;
1555 if (haveright) {
1556 /*
1557 * There is a block to our right.
1558 */
1559 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1560 goto error0;
1561 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1562 /*
1563 * It's not contiguous, though.
1564 */
1565 if (bno + len < gtbno)
1566 haveright = 0;
1567 else {
1568 /*
1569 * If this failure happens the request to free this
1570 * space was invalid, it's (partly) already free.
1571 * Very bad.
1572 */
1573 XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1574 }
1575 }
1576 /*
1577 * Now allocate and initialize a cursor for the by-size tree.
1578 */
1579 cnt_cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT, NULL,
1580 0);
1581 /*
1582 * Have both left and right contiguous neighbors.
1583 * Merge all three into a single free block.
1584 */
1585 if (haveleft && haveright) {
1586 /*
1587 * Delete the old by-size entry on the left.
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 * Delete the old by-size entry on the right.
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 * Delete the old by-block entry for the right block.
1606 */
1607 if ((error = xfs_alloc_delete(bno_cur, &i)))
1608 goto error0;
1609 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1610 /*
1611 * Move the by-block cursor back to the left neighbor.
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 * Check that this is the right record: delete didn't
1619 * mangle the cursor.
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 * Update remaining by-block entry to the new, joined block.
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 * Have only a left contiguous neighbor.
1643 * Merge it together with the new freespace.
1644 */
1645 else if (haveleft) {
1646 /*
1647 * Delete the old by-size entry on the left.
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 * Back up the by-block cursor to the left neighbor, and
1657 * update its length.
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 * Have only a right contiguous neighbor.
1669 * Merge it together with the new freespace.
1670 */
1671 else if (haveright) {
1672 /*
1673 * Delete the old by-size entry on the right.
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 * Update the starting block and length of the right
1683 * neighbor in the by-block tree.
1684 */
1685 nbno = bno;
1686 nlen = len + gtlen;
1687 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1688 goto error0;
1689 }
1690 /*
1691 * No contiguous neighbors.
1692 * Insert the new freespace into the by-block tree.
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 * In all cases we need to insert the new freespace in the by-size tree.
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 * Update the freespace totals in the ag and superblock.
1716 */
1717 {
1718 xfs_agf_t *agf;
1719 xfs_perag_t *pag; /* per allocation group data */
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 * Since blocks move to the free list without the coordination
1744 * used in xfs_bmap_finish, we can't allow block to be available
1745 * for reallocation and non-transaction writing (user data)
1746 * until we know that the transaction that moved it to the free
1747 * list is permanently on disk. We track the blocks by declaring
1748 * these blocks as "busy"; the busy list is maintained on a per-ag
1749 * basis and each transaction records which entries should be removed
1750 * when the iclog commits to disk. If a busy block is allocated,
1751 * the iclog is pushed up to the LSN that freed the block.
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 * Visible (exported) allocation/free functions.
1767 * Some of these are used just by xfs_alloc_btree.c and this file.
1768 */
1769
1770 /*
1771 * Compute and fill in value of m_ag_maxlevels.
1772 */
1773 void
1774 xfs_alloc_compute_maxlevels(
1775 xfs_mount_t *mp) /* file system mount structure */
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 * Decide whether to use this allocation group for this allocation.
1794 * If so, fix up the btree freelist's size.
1795 */
1796 STATIC int /* error */
1797 xfs_alloc_fix_freelist(
1798 xfs_alloc_arg_t *args, /* allocation argument structure */
1799 int flags) /* XFS_ALLOC_FLAG_... */
1800 {
1801 xfs_buf_t *agbp; /* agf buffer pointer */
1802 xfs_agf_t *agf; /* a.g. freespace structure pointer */
1803 xfs_buf_t *agflbp;/* agfl buffer pointer */
1804 xfs_agblock_t bno; /* freelist block */
1805 xfs_extlen_t delta; /* new blocks needed in freelist */
1806 int error; /* error result code */
1807 xfs_extlen_t longest;/* longest extent in allocation group */
1808 xfs_mount_t *mp; /* file system mount point structure */
1809 xfs_extlen_t need; /* total blocks needed in freelist */
1810 xfs_perag_t *pag; /* per-ag information structure */
1811 xfs_alloc_arg_t targs; /* local allocation arguments */
1812 xfs_trans_t *tp; /* transaction pointer */
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 * If this is a metadata preferred pag and we are user data
1833 * then try somewhere else if we are not being asked to
1834 * try harder at this point
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 * If it looks like there isn't a long enough extent, or enough
1848 * total blocks, reject it.
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 * Get the a.g. freespace buffer.
1866 * Can fail if we're not blocking on locks, and it's held.
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 * Figure out how many blocks we should have in the freelist.
1881 */
1882 agf = XFS_BUF_TO_AGF(agbp);
1883 need = XFS_MIN_FREELIST(agf, mp);
1884 /*
1885 * If there isn't enough total or single-extent, reject it.
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 * Make the freelist shorter if it's too long.
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 * Initialize the args structure.
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 * Make the freelist longer if it's too short.
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 * Allocate as many blocks as possible at once.
1939 */
1940 if ((error = xfs_alloc_ag_vextent(&targs))) {
1941 xfs_trans_brelse(tp, agflbp);
1942 return error;
1943 }
1944 /*
1945 * Stop if we run out. Won't happen if callers are obeying
1946 * the restrictions correctly. Can happen for free calls
1947 * on a completely full ag.
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 * Put each allocated block on the list.
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 * Get a block from the freelist.
1973 * Returns with the buffer for the block gotten.
1974 */
1975 int /* error */
1976 xfs_alloc_get_freelist(
1977 xfs_trans_t *tp, /* transaction pointer */
1978 xfs_buf_t *agbp, /* buffer containing the agf structure */
1979 xfs_agblock_t *bnop, /* block address retrieved from freelist */
1980 int btreeblk) /* destination is a AGF btree */
1981 {
1982 xfs_agf_t *agf; /* a.g. freespace structure */
1983 xfs_agfl_t *agfl; /* a.g. freelist structure */
1984 xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
1985 xfs_agblock_t bno; /* block number returned */
1986 int error;
1987 int logflags;
1988 xfs_mount_t *mp; /* mount structure */
1989 xfs_perag_t *pag; /* per allocation group data */
1990
1991 agf = XFS_BUF_TO_AGF(agbp);
1992 /*
1993 * Freelist is empty, give up.
1994 */
1995 if (!agf->agf_flcount) {
1996 *bnop = NULLAGBLOCK;
1997 return 0;
1998 }
1999 /*
2000 * Read the array of free blocks.
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 * Get the block number and update the data structures.
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 * As blocks are freed, they are added to the per-ag busy list
2033 * and remain there until the freeing transaction is committed to
2034 * disk. Now that we have allocated blocks, this list must be
2035 * searched to see if a block is being reused. If one is, then
2036 * the freeing transaction must be pushed to disk NOW by forcing
2037 * to disk all iclogs up that transaction's LSN.
2038 */
2039 xfs_alloc_search_busy(tp, be32_to_cpu(agf->agf_seqno), bno, 1);
2040 return 0;
2041 }
2042
2043 /*
2044 * Log the given fields from the agf structure.
2045 */
2046 void
2047 xfs_alloc_log_agf(
2048 xfs_trans_t *tp, /* transaction pointer */
2049 xfs_buf_t *bp, /* buffer for a.g. freelist header */
2050 int fields) /* mask of fields to be logged (XFS_AGF_...) */
2051 {
2052 int first; /* first byte offset */
2053 int last; /* last byte offset */
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 * Interface for inode allocation to force the pag data to be initialized.
2076 */
2077 int /* error */
2078 xfs_alloc_pagf_init(
2079 xfs_mount_t *mp, /* file system mount structure */
2080 xfs_trans_t *tp, /* transaction pointer */
2081 xfs_agnumber_t agno, /* allocation group number */
2082 int flags) /* XFS_ALLOC_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 * Put the block on the freelist for the allocation group.
2096 */
2097 int /* error */
2098 xfs_alloc_put_freelist(
2099 xfs_trans_t *tp, /* transaction pointer */
2100 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
2101 xfs_buf_t *agflbp,/* buffer for a.g. free block array */
2102 xfs_agblock_t bno, /* block being freed */
2103 int btreeblk) /* block came from a AGF btree */
2104 {
2105 xfs_agf_t *agf; /* a.g. freespace structure */
2106 xfs_agfl_t *agfl; /* a.g. free block array */
2107 __be32 *blockp;/* pointer to array entry */
2108 int error;
2109 int logflags;
2110 xfs_mount_t *mp; /* mount structure */
2111 xfs_perag_t *pag; /* per allocation group data */
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 * Read in the allocation group header (free/alloc section).
2152 */
2153 int /* error */
2154 xfs_alloc_read_agf(
2155 xfs_mount_t *mp, /* mount point structure */
2156 xfs_trans_t *tp, /* transaction pointer */
2157 xfs_agnumber_t agno, /* allocation group number */
2158 int flags, /* XFS_ALLOC_FLAG_... */
2159 xfs_buf_t **bpp) /* buffer for the ag freelist header */
2160 {
2161 xfs_agf_t *agf; /* ag freelist header */
2162 int agf_ok; /* set if agf is consistent */
2163 xfs_buf_t *bp; /* return value */
2164 xfs_perag_t *pag; /* per allocation group data */
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 * Validate the magic number of the agf block.
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 * Allocate an extent (variable-size).
2232 * Depending on the allocation type, we either look in a single allocation
2233 * group or loop over the allocation groups to find the result.
2234 */
2235 int /* error */
2236 xfs_alloc_vextent(
2237 xfs_alloc_arg_t *args) /* allocation argument structure */
2238 {
2239 xfs_agblock_t agsize; /* allocation group size */
2240 int error;
2241 int flags; /* XFS_ALLOC_FLAG_... locking flags */
2242 xfs_extlen_t minleft;/* minimum left value, temp copy */
2243 xfs_mount_t *mp; /* mount structure pointer */
2244 xfs_agnumber_t sagno; /* starting allocation group number */
2245 xfs_alloctype_t type; /* input allocation type */
2246 int bump_rotor = 0;
2247 int no_min = 0;
2248 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2249
2250 mp = args->mp;
2251 type = args->otype = args->type;
2252 args->agbno = NULLAGBLOCK;
2253 /*
2254 * Just fix this up, for the case where the last a.g. is shorter
2255 * (or there's only one a.g.) and the caller couldn't easily figure
2256 * that out (xfs_bmap_alloc).
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 * These three force us into a single a.g.
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 * Try near allocation first, then anywhere-in-ag after
2308 * the first a.g. fails.
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 /* FALLTHROUGH */
2320 case XFS_ALLOCTYPE_ANY_AG:
2321 case XFS_ALLOCTYPE_START_AG:
2322 case XFS_ALLOCTYPE_FIRST_AG:
2323 /*
2324 * Rotate through the allocation groups looking for a winner.
2325 */
2326 if (type == XFS_ALLOCTYPE_ANY_AG) {
2327 /*
2328 * Start with the last place we left off.
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 * Start with allocation group given by bno.
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 * Start with the given allocation group.
2347 */
2348 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2349 flags = XFS_ALLOC_FLAG_TRYLOCK;
2350 }
2351 /*
2352 * Loop over allocation groups twice; first time with
2353 * trylock set, second time without.
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 * If we get a buffer back then the allocation will fly.
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 * Didn't work, figure out the next iteration.
2376 */
2377 if (args->agno == sagno &&
2378 type == XFS_ALLOCTYPE_START_BNO)
2379 args->type = XFS_ALLOCTYPE_THIS_AG;
2380 /*
2381 * For the first allocation, we can try any AG to get
2382 * space. However, if we already have allocated a
2383 * block, we don't want to try AGs whose number is below
2384 * sagno. Otherwise, we may end up with out-of-order
2385 * locking of AGF, which might cause deadlock.
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 * Reached the starting a.g., must either be done
2395 * or switch to non-trylock mode.
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 /* NOTREACHED */
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;
2442 error0:
2443 up_read(&mp->m_peraglock);
2444 return error;
2445 }
2446
2447 /*
2448 * Free an extent.
2449 * Just break up the extent address and hand off to xfs_free_ag_extent
2450 * after fixing up the freelist.
2451 */
2452 int /* error */
2453 xfs_free_extent(
2454 xfs_trans_t *tp, /* transaction pointer */
2455 xfs_fsblock_t bno, /* starting block number of extent */
2456 xfs_extlen_t len) /* length of extent */
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);
2478 error0:
2479 up_read(&args.mp->m_peraglock);
2480 return error;
2481 }
2482
2483
2484 /*
2485 * AG Busy list management
2486 * The busy list contains block ranges that have been freed but whose
2487 * transactions have not yet hit disk. If any block listed in a busy
2488 * list is reused, the transaction that freed it must be forced to disk
2489 * before continuing to use the block.
2490 *
2491 * xfs_alloc_mark_busy - add to the per-ag busy list
2492 * xfs_alloc_clear_busy - remove an item from the per-ag busy list
2493 */
2494 void
2495 xfs_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 /* search pagb_list for an open slot */
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 * The busy list is full! Since it is now not possible to
2529 * track the free block, make this a synchronous transaction
2530 * to insure that the block is not reused before this
2531 * transaction commits.
2532 */
2533 xfs_trans_set_sync(tp);
2534 }
2535
2536 mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
2537 }
2538
2539 void
2540 xfs_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 * returns non-zero if any of (agno,bno):len is in a busy list
2568 */
2569 STATIC int
2570 xfs_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 /* search pagb_list for this slot, skipping open slots */
2591 for (bsy = mp->m_perag[agno].pagb_list, n = 0;
2592 cnt; bsy++, n++) {
2593
2594 /*
2595 * (start1,length1) within (start2, length2)
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 * If a block was found, force the log through the LSN of the
2613 * transaction that freed the block
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 }
Support for the Chinese Samsung S3C2440 based development boards