path: root/extent-tree.c
Commit message (Collapse)AuthorAge
* Merge branch 'for-chris' of git:// into ↵Chris Mason2013-02-06
|\ | | | | | | | | | | | | | | | | raid56 Conflicts: ctree.h Signed-off-by: Chris Mason <>
| * Btrfs-progs: use btrfs_lookup_first_block_group when fixing accountingJosef Bacik2013-02-01
| | | | | | | | | | | | | | | | | | | | | | This was a bug from long time ago that never actually got fixed. We start with bytenr 0 when looping through all of the block groups, but btrfs_lookup_block_group will bail out since it couldn't find a block group with 0 as the bytenr. Btrfs_lookup_first_block_group will be nice and adjust the start up to the right value, so this way we reset all the block groups properly and not screw up the users block group accounting. Thanks, Signed-off-by: Josef Bacik <>
* | Add basic RAID[56] supportDavid Woodhouse2013-02-01
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | David Woodhouse originally contributed this code, and Chris Mason changed it around to reflect the current design goals for raid56. The original code expected all metadata and data writes to be full stripes. This meant metadata block size == stripe size, and had a few other restrictions. This version allows metadata blocks smaller than the stripe size. It implements both raid5 and raid6, although it does not have code to rebuild from parity if one of the drives is missing or incorrect. Signed-off-by: David Woodhouse <> Signed-off-by: Chris Mason <>
* | Fix alignment during allocationsChris Mason2013-02-01
|/ | | | | | | We need to align earlier to make sure we're getting things properly setup against the raid56 stripes. Signed-off-by: Chris Mason <>
* btrfsck: add early code to handle corrupted block groupsChris Mason2012-02-22
| | | | | | | This is mostly disabled, but it is step one in handling corrupted block groups in the extent allocation tree. Signed-off-by: Chris Mason <>
* btrfsck: remove extents from the fsck reference tracker as they are freedChris Mason2012-02-10
| | | | | | | | | | | | | | | | | | | During btrfsck --repair, we make an index of extents that have incorrect reference counts. Once we've collect the whole index, we go through and modify the extent allocation tree to reflect the correct results. Changing the extent allocation tree may free blocks, and so it may end up removing a block that had a missing reference structure. The fsck code may then circle back around and add the reference back. The result is an extent that isn't actually used, but is recorded in the extent allocation tree. This commit adds a hook called as extents are freed. The hook searches the index of incorrect references and updates it to reflect the freeing of the extent. Signed-off-by: Chris Mason <>
* btrfsck: make sure we fix the block group accounting during repairChris Mason2012-02-09
| | | | | | | | The block group accounting is fixed after we check the extent back references. This makes sure the accounting is fixed unless we were not able to repair the backrefs. Signed-off-by: Chris Mason <>
* btrfsck: make sure to dirty all block groups as we fix accountingChris Mason2012-02-09
| | | | | | | | | The code that corrects the count of bytes used in each block group was only marking block groups dirty when they contained extents. This fixes things to dirty all the block groups, so any empty block groups are written with their correct (zero) count. Signed-off-by: Chris Mason <>
* btrfsck: fix block group accounting during repairChris Mason2012-02-08
| | | | Signed-off-by: Chris Mason <>
* btrfs-corrupt-block: add -E option to randomly corrupt the extent_rootChris Mason2012-02-07
| | | | Signed-off-by: Chris Mason <>
* btrfsck: add code to rebuild extent recordsChris Mason2012-02-07
| | | | | | | This also includes a new --repair btrfsck option. For now it can only fix errors in the extent allocation tree. Signed-off-by: Chris Mason <>
* btrfs-progs: add a recovery utility to pull files from damanged filesystemsJosef Bacik2011-10-27
| | | | | Signed-off-by: Josef Bacik <> Signed-off-by: Chris Mason <>
* btrfs progs: fix extra metadata chunk allocation in --mixed caseArne Jansen2011-10-25
| | | | | | | | | | | | | | | | | | | | When creating a mixed fs with mkfs, an extra metadata chunk got allocated. This is because btrfs_reserve_extent calls do_chunk_alloc for METADATA, which in turn wasn't able to find the proper space_info, as __find_space_info did a hard compare of the flags. It is now sufficient for the space_info to include the proper flag. This reflects the change done to the kernel code to support mixed chunks. Also for a subsequent chunk allocation (which should not be hit in the mkfs case), the chunk is now created with the flags from the space_info instead of the requested flags. A better solution would be to pull the full changeset for the mixed case from the kernel into the user mode (or, even better, share the code) The additional chunk probably confused block_rsv calculation, which in turn led to severeal ENOSPC Oopses. Signed-off-by: Arne Jansen <> Signed-off-by: Hugo Mills <>
* btrfs-progs: cast u64 to long long to avoid printf warningsAnton Blanchard2011-10-25
| | | | | | | | | | | | When building on ppc64 I hit a number of warnings in printf: btrfs-map-logical.c:69: error: format ‘%Lu’ expects type ‘long long unsigned int’, but argument 4 has type ‘u64’ Fix them. Signed-off-by: Anton Blanchard <> Signed-off-by: Hugo Mills <>
* Fix unused-but-set errors in gcc-4.6Chris Ball2011-10-25
| | | | | | | | | | | | | | | | gcc-4.6 (as shipped in Fedora) turns on -Wunused-but-set-variable by default, which breaks the build when combined with -Wall, e.g.: debug-tree.c: In function ‘print_extent_leaf’: debug-tree.c:45:13: error: variable ‘last_len’ set but not used [-Werror=unused-but-set-variable] debug-tree.c:44:13: error: variable ‘last’ set but not used [-Werror=unused-but-set-variable] debug-tree.c:41:21: error: variable ‘item’ set but not used [-Werror=unused-but-set-variable] cc1: all warnings being treated as errors This patch fixes the errors by removing the unused variables. Signed-off-by: Chris Ball <> Signed-off-by: Hugo Mills <>
* Check for RAID10 in set_avail_alloc_bitsChris Mason2011-04-22
| | | | | | | | | | | | | When raid is setup with mkfs, it is supposed to cow the initial filesystem it creates up to the desired raid level. RAID10 was not in the list of RAID levels it checked for, so the initial FS created for RAID10 actually only lived on the first disk. This works well enough because all the roots get quickly cowed during the first mount. The exception is the data relocation tree, which only gets cowed when we do a balance. Signed-off-by: Chris Mason <>
* Check duplicate backrefs for both data and metadataYan Zheng2009-06-11
| | | | | | | | | | lookup_inline_extent_backref only checks for duplicate backref for data extent. It assumes backrefs for tree block never conflict. This patch makes lookup_inline_extent_backref check duplicate backrefs for both data and tree block, so that we can detect potential bug earlier. Signed-off-by: Yan Zheng <> Signed-off-by: Chris Mason <>
* Make sure all dirty blocks are written at commit timeYan Zheng2009-06-08
| | | | | | | | | Write dirty block groups may make some block groups dirty. This patch make btrfs_write_dirty_block_groups properly handle the recursion. Signed-off-by: Yan Zheng <> Signed-off-by: Chris Mason <>
* Update converter for the new formatYan Zheng2009-06-08
| | | | | Signed-off-by: Yan Zheng <> Signed-off-by: Chris Mason <>
* Mixed back reference (FORWARD ROLLING FORMAT CHANGE)Chris Mason2009-06-08
| | | | | | | | | | | | | | | | | This commit introduces a new kind of back reference for btrfs metadata. Once a filesystem has been mounted with this commit, IT WILL NO LONGER BE MOUNTABLE BY OLDER KERNELS. The new back ref provides information about pointer's key, level and in which tree the pointer lives. This information allow us to find the pointer by searching the tree. The shortcoming of the new back ref is that it only works for pointers in tree blocks referenced by their owner trees. This is mostly a problem for snapshots, where resolving one of these fuzzy back references would be O(number_of_snapshots) and quite slow. The solution used here is to use the fuzzy back references in the common case where a given tree block is only referenced by one root, and use the full back references when multiple roots have a reference
* Fix printf format casting errorsLuca Bruno2009-06-03
| | | | | | | | | | | | There are still some warnings of the form: format '%llu' expects type 'long long unsigned int' but argument has type 'u64' In conjunction with -Werror, this is causing some build failures. Now they're properly casted, avoiding compiler warnings. Signed-off-by: Luca Bruno <> Signed-off-by: Chris Mason <>
* Add semantic checks to btrfsck for files and directoriesYan Zheng2009-01-07
| | | | | | | | | | | | | | | | This patch makes btrfsck check more things, including directory items, file extents, checksumming, inode link counts etc. The code for these checks is similar to the code verifies extent back references. The main difference is that shared tree blocks are treated specially. The partial checking results(unresolved references and/or errors) of shared sub-trees are cached. This avoids scanning the shared blocks several times. Thank you, Signed-off-by: Yan Zheng <>
* Btrfs: update converter for the new disk formatYan Zheng2008-12-17
| | | | | | | | | | | This patch updates the ext3 to btrfs converter for the new disk format. This mainly involves changing the convert's data relocation and free space management code. This patch also ports some functions from kernel module to btrfs-progs. Thank you, Signed-off-by: Yan Zheng <>
* superblock duplicationYan Zheng2008-12-05
| | | | | | | | | | This patch updates btrfs-progs for superblock duplication. Note: I didn't make this patch as complete as the one for kernel since updating the converter requires changing the code again. Thank you, Signed-off-by: Yan Zheng <>
* update btrfs-progs for seed device supportYan Zheng2008-11-18
| | | | | | | | | | | | This patch does the following: 1) Update device management code to match the kernel code. 2) Allocator fixes. 3) Add a program called btrfstune to set/clear the SEEDING super block flags.
* Remove offset field from struct btrfs_extent_refYan Zheng2008-10-09
| | | | | | | | | | | | | | The offset field in struct btrfs_extent_ref records the position inside file that file extent is referenced by. In the new back reference system, tree leaves holding reference to file extent are recorded explicitly. We can quickly scan these tree leaves, so the offset field is not required. This patch also makes the back reference system check the objectid when extents are being deleted Signed-off-by: Yan Zheng <>
* Full back reference supportZheng Yan2008-09-23
| | | | | | | | This patch makes the back reference system to explicit record the location of parent node for all types of extents. The location of parent node is placed into the offset field of backref key. Every time a tree block is balanced, the back references for the affected lower level extents are updated.
* Verify parent generation number on btree readsChris Mason2008-05-13
* Pass down the expected generation number when reading tree blocksChris Mason2008-05-12
* Speed improvement and bug fixes for ext3 converterYan Zheng2008-04-24
| | | | | | | | This patch improves converter's allocator and fixes a bug in data relocation function. The new allocator caches free blocks as Btrfs's default allocator. In testing here, the user CPU time reduced to half of the original when checksum and small file packing was disabled. This patch also enlarges the size of block groups created by the converter.
* Fix balance_level to free the middle block if there is room in the left oneChris Mason2008-04-24
| | | | | | balance level starts by trying to empty the middle block, and then pushes from the right to the middle. This might empty the right block and leave a small number of pointers in the middle.
* Update the Ext3 converterChris Mason2008-04-22
| | | | | | | | | | | The main changes in this patch are adding chunk handing and data relocation ability. In the last step of conversion, the converter relocates data in system chunk and move chunk tree into system chunk. In the rollback process, the converter remove chunk tree from system chunk and copy data back. Regards YZ ---
* Add chunk uuids and update multi-device back referencesChris Mason2008-04-15
| | | | | | | | | | | | | | | | | | Block headers now store the chunk tree uuid Chunk items records the device uuid for each stripes Device extent items record better back refs to the chunk tree Block groups record better back refs to the chunk tree The chunk tree format has also changed. The objectid of BTRFS_CHUNK_ITEM_KEY used to be the logical offset of the chunk. Now it is a chunk tree id, with the logical offset being stored in the offset field of the key. This allows a single chunk tree to record multiple logical address spaces, upping the number of bytes indexed by a chunk tree from 2^64 to 2^128.
* Don't allow written blocks from this transaction to be reallocatedChris Mason2008-04-04
| | | | | | | | | | | | When a block is freed, it can be immediately reused if it is from the current transaction. But, an extra check is required to make sure the block had not been written yet. If it were reused after being written, the transid in the block header might match the transid of the next time the block was allocated. The parent node records the transaction ID of the block it is pointing to, and this is used as part of validating the block on reads. So, there can only be one version of a block per transaction.
* Recow all roots at the end of mkfsChris Mason2008-04-04
| | | | | | The mkfs code bootstraps the filesystem on a single device. Once the raid block groups are setup, it needs to recow all of the blocks so that each tree is properly allocated.
* Add support for single single duplication of metadataChris Mason2008-04-03
* Add mirroring support across multiple drivesChris Mason2008-04-03
* btrfs-progs: Fix printf format casting errorsAlex Chiang2008-04-01
| | | | | | | | | | | We get lots of warnings of the flavor: utils.c:441: warning: format '%Lu' expects type 'long long unsigned int' but argument 2 has type 'u64' And thanks to -Werror, the build fails. Clean up these printfs by properly casting the arg to the format specified. Signed-off-by: Alex Chiang <>
* Implement raid0 when multiple devices are presentChris Mason2008-03-25
| | | | This defaults to striping across all devices
* Walk all block devices looking for btrfsChris Mason2008-03-24
* Dynamic chunk allocationChris Mason2008-03-24
* Add support for multiple devices per filesystemChris Mason2008-03-24
* Remove extent back refs in batches, and avoid duplicate searchesChris Mason2008-03-04
* Add debugging for block group update failureChris Mason2008-02-04
* Insert extent record and the first backref in a single balanceChris Mason2008-03-04
* Tune readahead during defrag to avoid reading too much at onceChris Mason2008-01-24
* Rename the extent_map code to extent_ioChris Mason2008-03-04
| | | | This mirrors the changes in the kernel code.
* Hash in the owner and offset for file extent backref keysChris Mason2008-02-01
* A few update for btrfs-progsYan2008-01-08
| | | | | | | Hello, This patch adds inode flags definition to btrfs-progs and updates extent-tree.c to match the kernel.
* Update find_free_extent for the ext3 conversion toolYan2008-01-04
| | | | | This patch adds customized find_free_extent support to btrfs-progs, the conversion program requires this.