2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
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.
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.
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
20 #include "xfs_types.h"
24 #include "xfs_trans.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_btree_trace.h"
39 #include "xfs_ialloc.h"
40 #include "xfs_alloc.h"
41 #include "xfs_error.h"
45 * Get the data from the pointed-to record.
49 xfs_btree_cur_t *cur, /* btree cursor */
50 xfs_agblock_t *bno, /* output: starting block of extent */
51 xfs_extlen_t *len, /* output: length of extent */
52 int *stat) /* output: success/failure */
54 xfs_alloc_block_t *block; /* btree block */
56 int error; /* error return value */
58 int ptr; /* record number */
60 ptr = cur->bc_ptrs[0];
61 block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
63 if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
67 * Off the right end or left end, return failure.
69 if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
74 * Point to the record and extract its data.
77 xfs_alloc_rec_t *rec; /* record data */
79 rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
80 *bno = be32_to_cpu(rec->ar_startblock);
81 *len = be32_to_cpu(rec->ar_blockcount);
88 STATIC struct xfs_btree_cur *
89 xfs_allocbt_dup_cursor(
90 struct xfs_btree_cur *cur)
92 return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp,
93 cur->bc_private.a.agbp, cur->bc_private.a.agno,
99 struct xfs_btree_cur *cur,
100 union xfs_btree_ptr *ptr,
103 struct xfs_buf *agbp = cur->bc_private.a.agbp;
104 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
105 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno);
106 int btnum = cur->bc_btnum;
110 agf->agf_roots[btnum] = ptr->s;
111 be32_add_cpu(&agf->agf_levels[btnum], inc);
112 cur->bc_mp->m_perag[seqno].pagf_levels[btnum] += inc;
114 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
118 xfs_allocbt_alloc_block(
119 struct xfs_btree_cur *cur,
120 union xfs_btree_ptr *start,
121 union xfs_btree_ptr *new,
128 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
130 /* Allocate the new block from the freelist. If we can't, give up. */
131 error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
134 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
138 if (bno == NULLAGBLOCK) {
139 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
144 xfs_trans_agbtree_delta(cur->bc_tp, 1);
145 new->s = cpu_to_be32(bno);
147 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
153 xfs_allocbt_free_block(
154 struct xfs_btree_cur *cur,
157 struct xfs_buf *agbp = cur->bc_private.a.agbp;
158 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
162 bno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(bp));
163 error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1);
168 * Since blocks move to the free list without the coordination used in
169 * xfs_bmap_finish, we can't allow block to be available for
170 * reallocation and non-transaction writing (user data) until we know
171 * that the transaction that moved it to the free list is permanently
172 * on disk. We track the blocks by declaring these blocks as "busy";
173 * the busy list is maintained on a per-ag basis and each transaction
174 * records which entries should be removed when the iclog commits to
175 * disk. If a busy block is allocated, the iclog is pushed up to the
176 * LSN that freed the block.
178 xfs_alloc_mark_busy(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
179 xfs_trans_agbtree_delta(cur->bc_tp, -1);
184 * Update the longest extent in the AGF
187 xfs_allocbt_update_lastrec(
188 struct xfs_btree_cur *cur,
189 struct xfs_btree_block *block,
190 union xfs_btree_rec *rec,
194 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
195 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno);
199 ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
204 * If this is the last leaf block and it's the last record,
205 * then update the size of the longest extent in the AG.
207 if (ptr != xfs_btree_get_numrecs(block))
209 len = rec->alloc.ar_blockcount;
212 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
213 be32_to_cpu(agf->agf_longest))
215 len = rec->alloc.ar_blockcount;
218 numrecs = xfs_btree_get_numrecs(block);
221 ASSERT(ptr == numrecs + 1);
224 xfs_alloc_rec_t *rrp;
226 rrp = XFS_ALLOC_REC_ADDR(block, numrecs, cur);
227 len = rrp->ar_blockcount;
238 agf->agf_longest = len;
239 cur->bc_mp->m_perag[seqno].pagf_longest = be32_to_cpu(len);
240 xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST);
244 xfs_allocbt_get_minrecs(
245 struct xfs_btree_cur *cur,
248 return cur->bc_mp->m_alloc_mnr[level != 0];
252 xfs_allocbt_get_maxrecs(
253 struct xfs_btree_cur *cur,
256 return cur->bc_mp->m_alloc_mxr[level != 0];
260 xfs_allocbt_init_key_from_rec(
261 union xfs_btree_key *key,
262 union xfs_btree_rec *rec)
264 ASSERT(rec->alloc.ar_startblock != 0);
266 key->alloc.ar_startblock = rec->alloc.ar_startblock;
267 key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
271 xfs_allocbt_init_rec_from_key(
272 union xfs_btree_key *key,
273 union xfs_btree_rec *rec)
275 ASSERT(key->alloc.ar_startblock != 0);
277 rec->alloc.ar_startblock = key->alloc.ar_startblock;
278 rec->alloc.ar_blockcount = key->alloc.ar_blockcount;
282 xfs_allocbt_init_rec_from_cur(
283 struct xfs_btree_cur *cur,
284 union xfs_btree_rec *rec)
286 ASSERT(cur->bc_rec.a.ar_startblock != 0);
288 rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
289 rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
293 xfs_allocbt_init_ptr_from_cur(
294 struct xfs_btree_cur *cur,
295 union xfs_btree_ptr *ptr)
297 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
299 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
300 ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
302 ptr->s = agf->agf_roots[cur->bc_btnum];
306 xfs_allocbt_key_diff(
307 struct xfs_btree_cur *cur,
308 union xfs_btree_key *key)
310 xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a;
311 xfs_alloc_key_t *kp = &key->alloc;
314 if (cur->bc_btnum == XFS_BTNUM_BNO) {
315 return (__int64_t)be32_to_cpu(kp->ar_startblock) -
319 diff = (__int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
323 return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
327 xfs_allocbt_kill_root(
328 struct xfs_btree_cur *cur,
331 union xfs_btree_ptr *newroot)
335 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
336 XFS_BTREE_STATS_INC(cur, killroot);
339 * Update the root pointer, decreasing the level by 1 and then
342 xfs_allocbt_set_root(cur, newroot, -1);
343 error = xfs_allocbt_free_block(cur, bp);
345 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
349 XFS_BTREE_STATS_INC(cur, free);
351 xfs_btree_setbuf(cur, level, NULL);
354 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
358 #ifdef XFS_BTREE_TRACE
359 ktrace_t *xfs_allocbt_trace_buf;
362 xfs_allocbt_trace_enter(
363 struct xfs_btree_cur *cur,
380 ktrace_enter(xfs_allocbt_trace_buf, (void *)(__psint_t)type,
381 (void *)func, (void *)s, NULL, (void *)cur,
382 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
383 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
384 (void *)a8, (void *)a9, (void *)a10);
388 xfs_allocbt_trace_cursor(
389 struct xfs_btree_cur *cur,
394 *s0 = cur->bc_private.a.agno;
395 *l0 = cur->bc_rec.a.ar_startblock;
396 *l1 = cur->bc_rec.a.ar_blockcount;
400 xfs_allocbt_trace_key(
401 struct xfs_btree_cur *cur,
402 union xfs_btree_key *key,
406 *l0 = be32_to_cpu(key->alloc.ar_startblock);
407 *l1 = be32_to_cpu(key->alloc.ar_blockcount);
411 xfs_allocbt_trace_record(
412 struct xfs_btree_cur *cur,
413 union xfs_btree_rec *rec,
418 *l0 = be32_to_cpu(rec->alloc.ar_startblock);
419 *l1 = be32_to_cpu(rec->alloc.ar_blockcount);
422 #endif /* XFS_BTREE_TRACE */
424 static const struct xfs_btree_ops xfs_allocbt_ops = {
425 .rec_len = sizeof(xfs_alloc_rec_t),
426 .key_len = sizeof(xfs_alloc_key_t),
428 .dup_cursor = xfs_allocbt_dup_cursor,
429 .set_root = xfs_allocbt_set_root,
430 .kill_root = xfs_allocbt_kill_root,
431 .alloc_block = xfs_allocbt_alloc_block,
432 .free_block = xfs_allocbt_free_block,
433 .update_lastrec = xfs_allocbt_update_lastrec,
434 .get_minrecs = xfs_allocbt_get_minrecs,
435 .get_maxrecs = xfs_allocbt_get_maxrecs,
436 .init_key_from_rec = xfs_allocbt_init_key_from_rec,
437 .init_rec_from_key = xfs_allocbt_init_rec_from_key,
438 .init_rec_from_cur = xfs_allocbt_init_rec_from_cur,
439 .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur,
440 .key_diff = xfs_allocbt_key_diff,
442 #ifdef XFS_BTREE_TRACE
443 .trace_enter = xfs_allocbt_trace_enter,
444 .trace_cursor = xfs_allocbt_trace_cursor,
445 .trace_key = xfs_allocbt_trace_key,
446 .trace_record = xfs_allocbt_trace_record,
451 * Allocate a new allocation btree cursor.
453 struct xfs_btree_cur * /* new alloc btree cursor */
454 xfs_allocbt_init_cursor(
455 struct xfs_mount *mp, /* file system mount point */
456 struct xfs_trans *tp, /* transaction pointer */
457 struct xfs_buf *agbp, /* buffer for agf structure */
458 xfs_agnumber_t agno, /* allocation group number */
459 xfs_btnum_t btnum) /* btree identifier */
461 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
462 struct xfs_btree_cur *cur;
464 ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
466 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
470 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[btnum]);
471 cur->bc_btnum = btnum;
472 cur->bc_blocklog = mp->m_sb.sb_blocklog;
474 cur->bc_ops = &xfs_allocbt_ops;
475 if (btnum == XFS_BTNUM_CNT)
476 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
478 cur->bc_private.a.agbp = agbp;
479 cur->bc_private.a.agno = agno;