Skip to content
Navigation Menu
Toggle navigation
Sign in
In this repository
All GitHub Enterprise
↵
Jump to
↵
No suggested jump to results
In this repository
All GitHub Enterprise
↵
Jump to
↵
In this organization
All GitHub Enterprise
↵
Jump to
↵
In this repository
All GitHub Enterprise
↵
Jump to
↵
Sign in
Reseting focus
You signed in with another tab or window.
Reload
to refresh your session.
You signed out in another tab or window.
Reload
to refresh your session.
You switched accounts on another tab or window.
Reload
to refresh your session.
Dismiss alert
{{ message }}
mariux64
/
linux
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
2
Pull requests
0
Actions
Projects
0
Wiki
Security
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security
Insights
Files
53d2e69
Documentation
arch
block
certs
crypto
drivers
firmware
fs
9p
adfs
affs
afs
autofs4
befs
bfs
btrfs
cachefiles
ceph
cifs
coda
configfs
cramfs
crypto
debugfs
devpts
dlm
ecryptfs
efivarfs
efs
exofs
exportfs
ext2
ext4
f2fs
fat
freevxfs
fscache
fuse
gfs2
hfs
hfsplus
hostfs
hpfs
hugetlbfs
isofs
jbd2
jffs2
jfs
kernfs
lockd
logfs
minix
ncpfs
nfs
nfs_common
nfsd
nilfs2
nls
notify
ntfs
ocfs2
omfs
openpromfs
overlayfs
proc
pstore
qnx4
qnx6
quota
ramfs
reiserfs
romfs
squashfs
sysfs
sysv
tracefs
ubifs
udf
ufs
xfs
libxfs
xfs_alloc.c
xfs_alloc.h
xfs_alloc_btree.c
xfs_alloc_btree.h
xfs_attr.c
xfs_attr_leaf.c
xfs_attr_leaf.h
xfs_attr_remote.c
xfs_attr_remote.h
xfs_attr_sf.h
xfs_bit.c
xfs_bit.h
xfs_bmap.c
xfs_bmap.h
xfs_bmap_btree.c
xfs_bmap_btree.h
xfs_btree.c
xfs_btree.h
xfs_cksum.h
xfs_da_btree.c
xfs_da_btree.h
xfs_da_format.c
xfs_da_format.h
xfs_dir2.c
xfs_dir2.h
xfs_dir2_block.c
xfs_dir2_data.c
xfs_dir2_leaf.c
xfs_dir2_node.c
xfs_dir2_priv.h
xfs_dir2_sf.c
xfs_dquot_buf.c
xfs_format.h
xfs_fs.h
xfs_ialloc.c
xfs_ialloc.h
xfs_ialloc_btree.c
xfs_ialloc_btree.h
xfs_inode_buf.c
xfs_inode_buf.h
xfs_inode_fork.c
xfs_inode_fork.h
xfs_log_format.h
xfs_log_recover.h
xfs_log_rlimit.c
xfs_quota_defs.h
xfs_rtbitmap.c
xfs_sb.c
xfs_sb.h
xfs_shared.h
xfs_symlink_remote.c
xfs_trans_resv.c
xfs_trans_resv.h
xfs_trans_space.h
xfs_types.h
Kconfig
Makefile
kmem.c
kmem.h
mrlock.h
uuid.c
uuid.h
xfs.h
xfs_acl.c
xfs_acl.h
xfs_aops.c
xfs_aops.h
xfs_attr.h
xfs_attr_inactive.c
xfs_attr_list.c
xfs_bmap_util.c
xfs_bmap_util.h
xfs_buf.c
xfs_buf.h
xfs_buf_item.c
xfs_buf_item.h
xfs_dir2_readdir.c
xfs_discard.c
xfs_discard.h
xfs_dquot.c
xfs_dquot.h
xfs_dquot_item.c
xfs_dquot_item.h
xfs_error.c
xfs_error.h
xfs_export.c
xfs_export.h
xfs_extent_busy.c
xfs_extent_busy.h
xfs_extfree_item.c
xfs_extfree_item.h
xfs_file.c
xfs_filestream.c
xfs_filestream.h
xfs_fsops.c
xfs_fsops.h
xfs_globals.c
xfs_icache.c
xfs_icache.h
xfs_icreate_item.c
xfs_icreate_item.h
xfs_inode.c
xfs_inode.h
xfs_inode_item.c
xfs_inode_item.h
xfs_ioctl.c
xfs_ioctl.h
xfs_ioctl32.c
xfs_ioctl32.h
xfs_iomap.c
xfs_iomap.h
xfs_iops.c
xfs_iops.h
xfs_itable.c
xfs_itable.h
xfs_linux.h
xfs_log.c
xfs_log.h
xfs_log_cil.c
xfs_log_priv.h
xfs_log_recover.c
xfs_message.c
xfs_message.h
xfs_mount.c
xfs_mount.h
xfs_mru_cache.c
xfs_mru_cache.h
xfs_ondisk.h
xfs_pnfs.c
xfs_pnfs.h
xfs_qm.c
xfs_qm.h
xfs_qm_bhv.c
xfs_qm_syscalls.c
xfs_quota.h
xfs_quotaops.c
xfs_rtalloc.c
xfs_rtalloc.h
xfs_stats.c
xfs_stats.h
xfs_super.c
xfs_super.h
xfs_symlink.c
xfs_symlink.h
xfs_sysctl.c
xfs_sysctl.h
xfs_sysfs.c
xfs_sysfs.h
xfs_trace.c
xfs_trace.h
xfs_trans.c
xfs_trans.h
xfs_trans_ail.c
xfs_trans_buf.c
xfs_trans_dquot.c
xfs_trans_extfree.c
xfs_trans_inode.c
xfs_trans_priv.h
xfs_xattr.c
Kconfig
Kconfig.binfmt
Makefile
aio.c
anon_inodes.c
attr.c
bad_inode.c
binfmt_aout.c
binfmt_elf.c
binfmt_elf_fdpic.c
binfmt_em86.c
binfmt_flat.c
binfmt_misc.c
binfmt_script.c
block_dev.c
buffer.c
char_dev.c
compat.c
compat_binfmt_elf.c
compat_ioctl.c
coredump.c
dax.c
dcache.c
dcookies.c
direct-io.c
drop_caches.c
eventfd.c
eventpoll.c
exec.c
fcntl.c
fhandle.c
file.c
file_table.c
filesystems.c
fs-writeback.c
fs_pin.c
fs_struct.c
inode.c
internal.h
ioctl.c
libfs.c
locks.c
mbcache.c
mount.h
mpage.c
namei.c
namespace.c
no-block.c
nsfs.c
open.c
pipe.c
pnode.c
pnode.h
posix_acl.c
proc_namespace.c
read_write.c
readdir.c
select.c
seq_file.c
signalfd.c
splice.c
stack.c
stat.c
statfs.c
super.c
sync.c
timerfd.c
userfaultfd.c
utimes.c
xattr.c
include
init
ipc
kernel
lib
mm
net
samples
scripts
security
sound
tools
usr
virt
.get_maintainer.ignore
.gitignore
.mailmap
COPYING
CREDITS
Kbuild
Kconfig
MAINTAINERS
Makefile
README
REPORTING-BUGS
Breadcrumbs
linux
/
fs
/
xfs
/
libxfs
/
xfs_alloc_btree.c
Blame
Blame
Latest commit
History
History
474 lines (413 loc) · 11.7 KB
Breadcrumbs
linux
/
fs
/
xfs
/
libxfs
/
xfs_alloc_btree.c
Top
File metadata and controls
Code
Blame
474 lines (413 loc) · 11.7 KB
Raw
/* * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. * All Rights Reserved. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation. * * This program is distributed in the hope that it would be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #include "xfs.h" #include "xfs_fs.h" #include "xfs_shared.h" #include "xfs_format.h" #include "xfs_log_format.h" #include "xfs_trans_resv.h" #include "xfs_sb.h" #include "xfs_mount.h" #include "xfs_btree.h" #include "xfs_alloc_btree.h" #include "xfs_alloc.h" #include "xfs_extent_busy.h" #include "xfs_error.h" #include "xfs_trace.h" #include "xfs_cksum.h" #include "xfs_trans.h" STATIC struct xfs_btree_cur * xfs_allocbt_dup_cursor( struct xfs_btree_cur *cur) { return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agbp, cur->bc_private.a.agno, cur->bc_btnum); } STATIC void xfs_allocbt_set_root( struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr, int inc) { struct xfs_buf *agbp = cur->bc_private.a.agbp; struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); int btnum = cur->bc_btnum; struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno); ASSERT(ptr->s != 0); agf->agf_roots[btnum] = ptr->s; be32_add_cpu(&agf->agf_levels[btnum], inc); pag->pagf_levels[btnum] += inc; xfs_perag_put(pag); xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); } STATIC int xfs_allocbt_alloc_block( struct xfs_btree_cur *cur, union xfs_btree_ptr *start, union xfs_btree_ptr *new, int *stat) { int error; xfs_agblock_t bno; XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); /* Allocate the new block from the freelist. If we can't, give up. */ error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp, &bno, 1); if (error) { XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); return error; } if (bno == NULLAGBLOCK) { XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); *stat = 0; return 0; } xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, false); xfs_trans_agbtree_delta(cur->bc_tp, 1); new->s = cpu_to_be32(bno); XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); *stat = 1; return 0; } STATIC int xfs_allocbt_free_block( struct xfs_btree_cur *cur, struct xfs_buf *bp) { struct xfs_buf *agbp = cur->bc_private.a.agbp; struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); xfs_agblock_t bno; int error; bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp)); error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); if (error) return error; xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1, XFS_EXTENT_BUSY_SKIP_DISCARD); xfs_trans_agbtree_delta(cur->bc_tp, -1); return 0; } /* * Update the longest extent in the AGF */ STATIC void xfs_allocbt_update_lastrec( struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_rec *rec, int ptr, int reason) { struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); struct xfs_perag *pag; __be32 len; int numrecs; ASSERT(cur->bc_btnum == XFS_BTNUM_CNT); switch (reason) { case LASTREC_UPDATE: /* * If this is the last leaf block and it's the last record, * then update the size of the longest extent in the AG. */ if (ptr != xfs_btree_get_numrecs(block)) return; len = rec->alloc.ar_blockcount; break; case LASTREC_INSREC: if (be32_to_cpu(rec->alloc.ar_blockcount) <= be32_to_cpu(agf->agf_longest)) return; len = rec->alloc.ar_blockcount; break; case LASTREC_DELREC: numrecs = xfs_btree_get_numrecs(block); if (ptr <= numrecs) return; ASSERT(ptr == numrecs + 1); if (numrecs) { xfs_alloc_rec_t *rrp; rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs); len = rrp->ar_blockcount; } else { len = 0; } break; default: ASSERT(0); return; } agf->agf_longest = len; pag = xfs_perag_get(cur->bc_mp, seqno); pag->pagf_longest = be32_to_cpu(len); xfs_perag_put(pag); xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST); } STATIC int xfs_allocbt_get_minrecs( struct xfs_btree_cur *cur, int level) { return cur->bc_mp->m_alloc_mnr[level != 0]; } STATIC int xfs_allocbt_get_maxrecs( struct xfs_btree_cur *cur, int level) { return cur->bc_mp->m_alloc_mxr[level != 0]; } STATIC void xfs_allocbt_init_key_from_rec( union xfs_btree_key *key, union xfs_btree_rec *rec) { ASSERT(rec->alloc.ar_startblock != 0); key->alloc.ar_startblock = rec->alloc.ar_startblock; key->alloc.ar_blockcount = rec->alloc.ar_blockcount; } STATIC void xfs_allocbt_init_rec_from_key( union xfs_btree_key *key, union xfs_btree_rec *rec) { ASSERT(key->alloc.ar_startblock != 0); rec->alloc.ar_startblock = key->alloc.ar_startblock; rec->alloc.ar_blockcount = key->alloc.ar_blockcount; } STATIC void xfs_allocbt_init_rec_from_cur( struct xfs_btree_cur *cur, union xfs_btree_rec *rec) { ASSERT(cur->bc_rec.a.ar_startblock != 0); rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock); rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount); } STATIC void xfs_allocbt_init_ptr_from_cur( struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr) { struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno)); ASSERT(agf->agf_roots[cur->bc_btnum] != 0); ptr->s = agf->agf_roots[cur->bc_btnum]; } STATIC __int64_t xfs_allocbt_key_diff( struct xfs_btree_cur *cur, union xfs_btree_key *key) { xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a; xfs_alloc_key_t *kp = &key->alloc; __int64_t diff; if (cur->bc_btnum == XFS_BTNUM_BNO) { return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; } diff = (__int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount; if (diff) return diff; return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock; } static bool xfs_allocbt_verify( struct xfs_buf *bp) { struct xfs_mount *mp = bp->b_target->bt_mount; struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); struct xfs_perag *pag = bp->b_pag; unsigned int level; /* * magic number and level verification * * During growfs operations, we can't verify the exact level or owner as * the perag is not fully initialised and hence not attached to the * buffer. In this case, check against the maximum tree depth. * * Similarly, during log recovery we will have a perag structure * attached, but the agf information will not yet have been initialised * from the on disk AGF. Again, we can only check against maximum limits * in this case. */ level = be16_to_cpu(block->bb_level); switch (block->bb_magic) { case cpu_to_be32(XFS_ABTB_CRC_MAGIC): if (!xfs_btree_sblock_v5hdr_verify(bp)) return false; /* fall through */ case cpu_to_be32(XFS_ABTB_MAGIC): if (pag && pag->pagf_init) { if (level >= pag->pagf_levels[XFS_BTNUM_BNOi]) return false; } else if (level >= mp->m_ag_maxlevels) return false; break; case cpu_to_be32(XFS_ABTC_CRC_MAGIC): if (!xfs_btree_sblock_v5hdr_verify(bp)) return false; /* fall through */ case cpu_to_be32(XFS_ABTC_MAGIC): if (pag && pag->pagf_init) { if (level >= pag->pagf_levels[XFS_BTNUM_CNTi]) return false; } else if (level >= mp->m_ag_maxlevels) return false; break; default: return false; } return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]); } static void xfs_allocbt_read_verify( struct xfs_buf *bp) { if (!xfs_btree_sblock_verify_crc(bp)) xfs_buf_ioerror(bp, -EFSBADCRC); else if (!xfs_allocbt_verify(bp)) xfs_buf_ioerror(bp, -EFSCORRUPTED); if (bp->b_error) { trace_xfs_btree_corrupt(bp, _RET_IP_); xfs_verifier_error(bp); } } static void xfs_allocbt_write_verify( struct xfs_buf *bp) { if (!xfs_allocbt_verify(bp)) { trace_xfs_btree_corrupt(bp, _RET_IP_); xfs_buf_ioerror(bp, -EFSCORRUPTED); xfs_verifier_error(bp); return; } xfs_btree_sblock_calc_crc(bp); } const struct xfs_buf_ops xfs_allocbt_buf_ops = { .name = "xfs_allocbt", .verify_read = xfs_allocbt_read_verify, .verify_write = xfs_allocbt_write_verify, }; #if defined(DEBUG) || defined(XFS_WARN) STATIC int xfs_allocbt_keys_inorder( struct xfs_btree_cur *cur, union xfs_btree_key *k1, union xfs_btree_key *k2) { if (cur->bc_btnum == XFS_BTNUM_BNO) { return be32_to_cpu(k1->alloc.ar_startblock) < be32_to_cpu(k2->alloc.ar_startblock); } else { return be32_to_cpu(k1->alloc.ar_blockcount) < be32_to_cpu(k2->alloc.ar_blockcount) || (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount && be32_to_cpu(k1->alloc.ar_startblock) < be32_to_cpu(k2->alloc.ar_startblock)); } } STATIC int xfs_allocbt_recs_inorder( struct xfs_btree_cur *cur, union xfs_btree_rec *r1, union xfs_btree_rec *r2) { if (cur->bc_btnum == XFS_BTNUM_BNO) { return be32_to_cpu(r1->alloc.ar_startblock) + be32_to_cpu(r1->alloc.ar_blockcount) <= be32_to_cpu(r2->alloc.ar_startblock); } else { return be32_to_cpu(r1->alloc.ar_blockcount) < be32_to_cpu(r2->alloc.ar_blockcount) || (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount && be32_to_cpu(r1->alloc.ar_startblock) < be32_to_cpu(r2->alloc.ar_startblock)); } } #endif /* DEBUG */ static const struct xfs_btree_ops xfs_allocbt_ops = { .rec_len = sizeof(xfs_alloc_rec_t), .key_len = sizeof(xfs_alloc_key_t), .dup_cursor = xfs_allocbt_dup_cursor, .set_root = xfs_allocbt_set_root, .alloc_block = xfs_allocbt_alloc_block, .free_block = xfs_allocbt_free_block, .update_lastrec = xfs_allocbt_update_lastrec, .get_minrecs = xfs_allocbt_get_minrecs, .get_maxrecs = xfs_allocbt_get_maxrecs, .init_key_from_rec = xfs_allocbt_init_key_from_rec, .init_rec_from_key = xfs_allocbt_init_rec_from_key, .init_rec_from_cur = xfs_allocbt_init_rec_from_cur, .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur, .key_diff = xfs_allocbt_key_diff, .buf_ops = &xfs_allocbt_buf_ops, #if defined(DEBUG) || defined(XFS_WARN) .keys_inorder = xfs_allocbt_keys_inorder, .recs_inorder = xfs_allocbt_recs_inorder, #endif }; /* * Allocate a new allocation btree cursor. */ struct xfs_btree_cur * /* new alloc btree cursor */ xfs_allocbt_init_cursor( struct xfs_mount *mp, /* file system mount point */ struct xfs_trans *tp, /* transaction pointer */ struct xfs_buf *agbp, /* buffer for agf structure */ xfs_agnumber_t agno, /* allocation group number */ xfs_btnum_t btnum) /* btree identifier */ { struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); struct xfs_btree_cur *cur; ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT); cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP); cur->bc_tp = tp; cur->bc_mp = mp; cur->bc_btnum = btnum; cur->bc_blocklog = mp->m_sb.sb_blocklog; cur->bc_ops = &xfs_allocbt_ops; if (btnum == XFS_BTNUM_CNT) { cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]); cur->bc_flags = XFS_BTREE_LASTREC_UPDATE; } else { cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]); } cur->bc_private.a.agbp = agbp; cur->bc_private.a.agno = agno; if (xfs_sb_version_hascrc(&mp->m_sb)) cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; return cur; } /* * Calculate number of records in an alloc btree block. */ int xfs_allocbt_maxrecs( struct xfs_mount *mp, int blocklen, int leaf) { blocklen -= XFS_ALLOC_BLOCK_LEN(mp); if (leaf) return blocklen / sizeof(xfs_alloc_rec_t); return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
You can’t perform that action at this time.