| /* |
| * Copyright (C) 2015-2016 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include <assert.h> |
| #include <inttypes.h> |
| #include <lk/compiler.h> |
| #include <stdbool.h> |
| #include <stdint.h> |
| #include <stdio.h> |
| #include <string.h> |
| |
| #include "array.h" |
| #include "block_allocator.h" |
| #include "block_set.h" |
| #include "checkpoint.h" |
| #include "debug.h" |
| #include "file.h" |
| #include "transaction.h" |
| |
| bool print_merge_free; |
| |
| /** |
| * transaction_check_free |
| * @tr: Transaction object. |
| * @set: Free set to check. |
| * @min_free Number of block that must be in @set |
| * |
| * Return: %true is @set contains @min_free or more blocks, %false otherwise. |
| */ |
| static bool transaction_check_free(struct transaction* tr, |
| struct block_set* set, |
| data_block_t min_free) { |
| data_block_t next_block; |
| struct block_range free_range; |
| data_block_t count; |
| |
| next_block = 0; |
| while (true) { |
| free_range = block_set_find_next_range(tr, set, next_block); |
| if (block_range_empty(free_range)) { |
| return false; |
| } |
| count = free_range.end - free_range.start; |
| if (count >= min_free) { |
| return true; |
| } |
| min_free -= count; |
| next_block = free_range.end; |
| } |
| } |
| |
| /** |
| * transaction_merge_free_sets |
| * @tr: Transaction object. |
| * @new_set: Output set. |
| * @set_i: Initial set. |
| * @set_d: Set of blocks to delete. |
| * @set_a: Set of blocks to add. |
| * |
| * Helper function to update the free_set when committing a transaction. |
| * @new_set = @set_i - @set_d - @new_set-blocks + @set_a + set_[ida]-blocks |
| * @new_set must start empty and will be initialized and filled in this |
| * function. |
| */ |
| static void transaction_merge_free_sets(struct transaction* tr, |
| struct block_set* new_set, |
| struct block_set* set_i, |
| struct block_set* set_d, |
| struct block_set* set_a) { |
| data_block_t next_block; |
| struct block_range delete_range = BLOCK_RANGE_INITIAL_VALUE(delete_range); |
| struct block_range add_range = BLOCK_RANGE_INITIAL_VALUE(add_range); |
| |
| /* new_set should start empty. */ |
| assert(block_set_find_next_block(tr, new_set, 1, true) == 0); |
| block_set_copy(tr, new_set, set_i); |
| |
| full_assert(block_set_check(tr, set_i)); |
| full_assert(block_set_check(tr, set_d)); |
| full_assert(block_set_check(tr, set_a)); |
| |
| assert(!block_mac_valid(tr, &set_i->block_tree.root) || |
| transaction_block_need_copy( |
| tr, block_mac_to_block(tr, &set_i->block_tree.root))); |
| if (print_merge_free) { |
| printf("%s\n", __func__); |
| } |
| |
| /* TODO: don't walk the whole tree each time */ |
| next_block = 1; |
| while (next_block != 0) { |
| tr->min_free_block = next_block; |
| delete_range = block_set_find_next_range(tr, set_d, next_block); |
| add_range = block_set_find_next_range(tr, set_a, next_block); |
| if (print_merge_free) { |
| printf("%s: add %" PRIu64 "-%" PRIu64 " or delete %" PRIu64 |
| "-%" PRIu64 "\n", |
| __func__, add_range.start, add_range.end - 1, |
| delete_range.start, delete_range.end - 1); |
| } |
| assert(!block_range_overlap(delete_range, add_range)); |
| if (block_range_before(delete_range, add_range)) { |
| assert(delete_range.start >= next_block); |
| tr->min_free_block = delete_range.end; |
| block_allocator_suspend_set_updates(tr); |
| block_set_remove_range(tr, new_set, delete_range); |
| block_allocator_process_queue(tr); |
| next_block = delete_range.end; |
| } else if (!block_range_empty(add_range)) { |
| assert(add_range.start >= next_block); |
| tr->min_free_block = add_range.end; |
| block_allocator_suspend_set_updates(tr); |
| block_set_add_range(tr, new_set, add_range); |
| block_allocator_process_queue(tr); |
| next_block = add_range.end; |
| } else { |
| assert(block_range_empty(delete_range)); |
| assert(block_range_empty(add_range)); |
| next_block = 0; |
| } |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| return; |
| } |
| } |
| full_assert(block_set_check(tr, new_set)); |
| } |
| |
| /** transaction_rebuild_free_set - Rebuild free set from referenced file blocks |
| * @tr: Transaction object. |
| * @new_free_set: Output free set. |
| * @files: Root block and mac of the files tree. |
| * @checkpoint: Checkpoint metadata block and mac |
| * |
| * Rebuilds the file system free set by walking the current files tree and |
| * ensuring that all referenced blocks are marked as not free. @new_free_set |
| * will be initialized to contain all blocks not referenced from the files root. |
| * The @checkpoint metadata block will also be removed from the free set, but |
| * its children (checkpoint files tree and free set) will not be checked. The |
| * blocks in the checkpoint (beside the metadata block) are tracked as |
| * free/allocated by the checkpoint free set rather than the active file system |
| * free set. |
| * |
| * We ignore tr->freed and tr->fs->free here because we are reconstructing the |
| * entire free set. All blocks that were freed in this transaction will not be |
| * referenced by @new_files. |
| */ |
| static void transaction_rebuild_free_set(struct transaction* tr, |
| struct block_set* new_free_set, |
| struct block_mac* new_files, |
| struct block_mac* new_checkpoint) { |
| struct block_range init_range = { |
| .start = tr->fs->min_block_num, |
| .end = tr->fs->dev->block_count, |
| }; |
| struct block_range range; |
| struct block_set previously_allocated = |
| BLOCK_SET_INITIAL_VALUE(previously_allocated); |
| |
| /* |
| * Copy and save tr->allocated so that we can keep track of the blocks |
| * already allocated for the current transaction when performing allocations |
| * for the new free set tree nodes. We then reset tr->allocated so that it |
| * will only hold new blocks allocated for new_free_set. All blocks |
| * allocated for files will already be referenced in new_files, so we'll |
| * already be removing them from new_free_set. |
| */ |
| assert(list_in_list(&tr->allocated.node)); |
| list_delete(&tr->allocated.node); |
| block_set_copy_ro(tr, &previously_allocated, &tr->allocated); |
| list_add_tail(&tr->fs->allocated, &previously_allocated.node); |
| |
| block_set_init(tr->fs, &tr->allocated); |
| list_add_tail(&tr->fs->allocated, &tr->allocated.node); |
| |
| block_set_init(tr->fs, new_free_set); |
| new_free_set->block_tree.copy_on_write = true; |
| new_free_set->block_tree.allow_copy_on_write = true; |
| |
| block_set_add_range(tr, new_free_set, init_range); |
| |
| if (block_mac_valid(tr, new_checkpoint)) { |
| block_set_remove_block(tr, new_free_set, |
| block_mac_to_block(tr, new_checkpoint)); |
| } |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| return; |
| } |
| |
| if (block_mac_valid(tr, new_files)) { |
| files_rebuild_free_set(tr, new_free_set, new_files); |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| return; |
| } |
| } |
| |
| for (range = block_set_find_next_range(tr, &tr->allocated, 1); |
| !block_range_empty(range); |
| range = block_set_find_next_range(tr, &tr->allocated, range.end)) { |
| tr->min_free_block = range.end; |
| block_allocator_suspend_set_updates(tr); |
| block_set_remove_range(tr, new_free_set, range); |
| block_allocator_process_queue(tr); |
| } |
| |
| /* |
| * Copy the rest of the allocated blocks back to tr->allocated to maintain a |
| * consistent state. We don't actually need to do this with the current code |
| * calling this function, but this restores the transaction state to what |
| * would be expected if it were to be used in the future. |
| */ |
| for (range = block_set_find_next_range(tr, &previously_allocated, 1); |
| !block_range_empty(range); |
| range = block_set_find_next_range(tr, &previously_allocated, |
| range.end)) { |
| block_set_add_range(tr, &tr->allocated, range); |
| } |
| list_delete(&previously_allocated.node); |
| |
| full_assert(block_set_check(tr, new_free_set)); |
| } |
| |
| /** |
| * transaction_block_need_copy - Check if block needs copy |
| * @tr: Transaction object. |
| * @block: Block number to check. |
| * |
| * Return: %true if block has not been allocated as a non-tmp block for @tr, |
| * %false otherwise. |
| */ |
| bool transaction_block_need_copy(struct transaction* tr, data_block_t block) { |
| assert(block); |
| assert(!block_set_block_in_set(tr, &tr->tmp_allocated, block)); |
| assert(!block_allocator_allocation_queued(tr, block, true)); |
| |
| return !block_set_block_in_set(tr, &tr->allocated, block) && |
| !block_allocator_allocation_queued(tr, block, false); |
| } |
| |
| /** |
| * transaction_delete_active - Remove transaction from active lists (internal) |
| * @tr: Transaction object. |
| */ |
| static void transaction_delete_active(struct transaction* tr) { |
| assert(list_in_list(&tr->allocated.node)); |
| assert(list_in_list(&tr->tmp_allocated.node)); |
| list_delete(&tr->allocated.node); |
| list_delete(&tr->tmp_allocated.node); |
| } |
| |
| /** |
| * transaction_fail - Fail transaction |
| * @tr: Transaction object. |
| * |
| * Marks transaction as failed, removes it from active list, discards dirty |
| * cache entries and restore open files to last committed state. |
| */ |
| void transaction_fail(struct transaction* tr) { |
| assert(!tr->failed); |
| |
| tr->failed = true; |
| |
| if (tr->complete) { |
| return; |
| } |
| |
| block_cache_discard_transaction(tr, true); |
| transaction_delete_active(tr); |
| file_transaction_failed(tr); |
| } |
| |
| /** |
| * transaction_free - Free transaction |
| * @tr: Transaction object. |
| * |
| * Prepare @tr for free. @tr must not be active and all open files must already |
| * be closed. |
| */ |
| void transaction_free(struct transaction* tr) { |
| assert(!transaction_is_active(tr)); |
| assert(list_is_empty(&tr->open_files)); |
| assert(list_in_list(&tr->node)); |
| list_delete(&tr->node); |
| } |
| |
| /** |
| * check_free_tree - Check tree of free set (internal) |
| * @tr: Transaction object. |
| * @free: Set object. |
| * |
| * Check that the blocks used by the tree for a free set are not in the same |
| * set. |
| */ |
| static void check_free_tree(struct transaction* tr, struct block_set* free) { |
| unsigned int i; |
| struct block_tree_path path; |
| |
| block_tree_walk(tr, &free->block_tree, 0, true, &path); |
| while (block_tree_path_get_key(&path)) { |
| for (i = 0; i < path.count; i++) { |
| assert(!block_set_block_in_set( |
| tr, free, |
| block_mac_to_block(tr, &path.entry[i].block_mac))); |
| } |
| block_tree_path_next(&path); |
| } |
| } |
| |
| /** |
| * transaction_complete - Complete transaction, optionally updating checkpoint |
| * @tr: Transaction object. |
| * @update_checkpoint: If true, update checkpoint with the new file-system |
| * state. |
| */ |
| void transaction_complete_etc(struct transaction* tr, bool update_checkpoint) { |
| struct block_mac new_files; |
| struct transaction* tmp_tr; |
| struct transaction* other_tr; |
| struct block_set new_free_set = BLOCK_SET_INITIAL_VALUE(new_free_set); |
| struct checkpoint* new_checkpoint = NULL; |
| struct block_mac new_checkpoint_mac; |
| struct obj_ref new_checkpoint_ref = |
| OBJ_REF_INITIAL_VALUE(new_checkpoint_ref); |
| bool super_block_updated; |
| |
| assert(tr->fs); |
| assert(!tr->complete); |
| |
| if (tr->fs->checkpoint_required) { |
| tr->fs->checkpoint_required = false; |
| if (!checkpoint_commit(tr->fs)) { |
| /* |
| * checkpoint creation failed, so we need to try again before we |
| * commit the next transaction |
| */ |
| tr->fs->checkpoint_required = true; |
| transaction_fail(tr); |
| pr_warn("auto-checkpoint failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| } |
| |
| // printf("%s: %" PRIu64 "\n", __func__, tr->version); |
| |
| block_mac_copy(tr, &new_checkpoint_mac, &tr->fs->checkpoint); |
| |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| assert(transaction_is_active(tr)); |
| |
| file_transaction_complete(tr, &new_files); |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| if (update_checkpoint) { |
| new_checkpoint = checkpoint_get_new_block(tr, &new_checkpoint_ref, |
| &new_checkpoint_mac); |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| assert(new_checkpoint); |
| } |
| |
| tr->new_free_set = &new_free_set; |
| if (tr->rebuild_free_set) { |
| transaction_rebuild_free_set(tr, &new_free_set, &new_files, |
| &new_checkpoint_mac); |
| } else { |
| transaction_merge_free_sets(tr, &new_free_set, &tr->fs->free, |
| &tr->allocated, &tr->freed); |
| } |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| if (!transaction_check_free(tr, &new_free_set, tr->fs->reserved_count)) { |
| if (!tr->failed) { |
| transaction_fail(tr); |
| } |
| pr_warn("transaction would leave fs too full, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| if (tr->fs->alternate_data && tr->repaired) { |
| if (!tr->failed) { |
| transaction_fail(tr); |
| } |
| pr_warn("transaction cannot repair alternate fs, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| if (0) { |
| printf("%s: old free:\n", __func__); |
| block_set_print(tr, &tr->fs->free); |
| printf("%s: tmp_allocated:\n", __func__); |
| block_set_print(tr, &tr->tmp_allocated); |
| printf("%s: allocated:\n", __func__); |
| block_set_print(tr, &tr->allocated); |
| printf("%s: freed:\n", __func__); |
| block_set_print(tr, &tr->freed); |
| printf("%s: new free:\n", __func__); |
| block_set_print(tr, &new_free_set); |
| } |
| |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| if (update_checkpoint) { |
| checkpoint_update_roots(tr, new_checkpoint, &new_files, |
| &new_free_set.block_tree.root); |
| block_put_dirty(tr, new_checkpoint, &new_checkpoint_ref, |
| &new_checkpoint_mac, NULL); |
| /* |
| * We have now released the block reference new_checkpoint_ref, so make |
| * sure we don't release it again in err_transaction_failed |
| */ |
| new_checkpoint = NULL; |
| } |
| |
| block_cache_clean_transaction(tr); |
| |
| if (tr->failed) { |
| pr_warn("transaction failed, abort\n"); |
| goto err_transaction_failed; |
| } |
| |
| assert(block_range_empty(new_free_set.initial_range)); |
| check_free_tree(tr, &new_free_set); |
| |
| if (block_mac_same_block(tr, &tr->fs->free.block_tree.root, |
| &new_free_set.block_tree.root)) { |
| /* |
| * If the root block of the free tree did not move, there can be no |
| * other changes to the filesystem. |
| */ |
| assert(block_mac_eq(tr, &tr->fs->free.block_tree.root, |
| &new_free_set.block_tree.root)); |
| assert(block_mac_eq(tr, &tr->fs->files.root, &new_files)); |
| |
| /* |
| * Skip super block write if there are no changes to the filesystem. |
| * This is needed in case a previous write error has triggered a request |
| * to write another copy of the old super block. There can only be one |
| * copy of each block in the cache. If we try to write a new super block |
| * here before cleaning the pending one, we get a conflict. If there |
| * were changes to the filesystem, the pending super block has already |
| * been cleaned at this point. |
| */ |
| goto complete_nop_transaction; |
| } |
| |
| super_block_updated = update_super_block(tr, &new_free_set.block_tree.root, |
| &new_files, &new_checkpoint_mac); |
| if (!super_block_updated) { |
| assert(tr->failed); |
| pr_warn("failed to update super block, abort\n"); |
| goto err_transaction_failed; |
| } |
| block_cache_clean_transaction(tr); |
| |
| /* |
| * If an error was detected writing the super block, it is not safe to |
| * continue as we do not know if the write completed. We need to rewrite a |
| * known state over the unknown super block to avoid an inconsistent view of |
| * the filesystem. |
| * |
| * At this point block_cache_complete_write has been called by the block |
| * device, so the current superblock slot in the block cache is free and not |
| * associated with the pending transaction. |
| */ |
| if (tr->failed) { |
| pr_warn("failed to write super block, notify fs and abort the transaction\n"); |
| /* |
| * Superblock could have been written or not. Make sure no other blocks |
| * are written to the filesystem before writing another copy of the |
| * superblock with the existing file and free trees. |
| * |
| * TODO: Don't trigger a superblock write on unaffected filesystems. |
| * We update all for now to simplify testing. |
| */ |
| fs_unknown_super_block_state_all(); |
| goto err_transaction_failed; |
| } |
| |
| tr->fs->free.block_tree.root = new_free_set.block_tree.root; |
| block_range_clear( |
| &tr->fs->free |
| .initial_range); /* clear for initial file-system state */ |
| tr->fs->files.root = new_files; |
| tr->fs->super_block_version = tr->fs->written_super_block_version; |
| tr->fs->checkpoint = new_checkpoint_mac; |
| if (tr->repaired) { |
| assert(!tr->fs->alternate_data); |
| tr->fs->main_repaired = true; |
| } |
| if (update_checkpoint) { |
| tr->fs->checkpoint_free.block_tree.root = new_free_set.block_tree.root; |
| block_range_clear(&tr->fs->checkpoint_free.initial_range); |
| } |
| |
| complete_nop_transaction: |
| transaction_delete_active(tr); |
| tr->complete = true; |
| |
| file_transaction_success(tr); |
| assert(!tr->failed); |
| |
| check_free_tree(tr, &tr->fs->free); |
| |
| list_for_every_entry_safe(&tr->fs->transactions, other_tr, tmp_tr, |
| struct transaction, node) { |
| if (tr->failed) { |
| break; |
| } |
| if (!transaction_is_active(other_tr)) { |
| continue; |
| } |
| if (tr->rebuild_free_set) { |
| /* |
| * TODO: only fail actually conflicting transactions when rebuilding |
| * the free set. When rebuilding, tr->freed does not contain all |
| * freed blocks if tree nodes were dropped. We could rebuild a free |
| * set delta by subtracting the new free set from the old one and |
| * then compare this delta against other transactions. |
| */ |
| pr_warn("Rebuilding free set requires failing all pending transactions\n"); |
| transaction_fail(other_tr); |
| } else if (block_set_overlap(tr, &tr->freed, &other_tr->freed)) { |
| pr_warn("fail conflicting transaction\n"); |
| transaction_fail(other_tr); |
| } |
| } |
| if (tr->failed) { |
| pr_warn("transaction failed while failing conflicting transactions\n"); |
| tr->failed = false; |
| list_for_every_entry_safe(&tr->fs->transactions, other_tr, tmp_tr, |
| struct transaction, node) { |
| if (!transaction_is_active(other_tr)) { |
| continue; |
| } |
| pr_warn("fail possibly conflicting transaction\n"); |
| transaction_fail(other_tr); |
| } |
| } |
| assert(!tr->failed); |
| block_cache_discard_transaction(tr, false); |
| |
| err_transaction_failed: |
| if (new_checkpoint) { |
| block_put_dirty_discard(new_checkpoint, &new_checkpoint_ref); |
| } |
| if (tr->failed) { |
| file_transaction_complete_failed(tr); |
| } |
| assert(!block_cache_debug_get_ref_block_count()); |
| } |
| |
| /** |
| * transaction_initial_super_block_complete - Complete special transaction |
| * @tr: Transaction object. Must match initial_super_block_tr in fs. |
| * |
| * Flush the initial superblock in @tr to disk. If the block could not be |
| * written re-initialize @tr and leave it in place for another attempt. |
| * Otherwise clear @tr->fs->initial_super_block_tr and free @tr. |
| * |
| * The initial superblock can only be flushed from the block cache by the |
| * block_cache_clean_transaction() call here, as we do not allow initial |
| * superblocks to be flushed to make room for other data. This ensures that we |
| * don't run out of room to recreate the superblock write in case it fails. |
| */ |
| void transaction_initial_super_block_complete(struct transaction* tr) { |
| assert(tr == tr->fs->initial_super_block_tr); |
| block_cache_clean_transaction(tr); |
| if (tr->failed) { |
| /* |
| * If we failed to write the superblock we re-initialize a new attempt |
| * to write that superblock before the next time we write to this |
| * filesystem. |
| */ |
| pr_err("%s: failed to write initial superblock, version %d.\n", |
| __func__, tr->fs->written_super_block_version); |
| write_current_super_block(tr->fs, true /* reinitialize */); |
| return; |
| } |
| printf("%s: write initial superblock, version %d -> %d\n", __func__, |
| tr->fs->super_block_version, tr->fs->written_super_block_version); |
| |
| assert(tr == tr->fs->initial_super_block_tr); |
| tr->fs->super_block_version = tr->fs->written_super_block_version; |
| tr->fs->initial_super_block_tr = NULL; |
| |
| /* not a real transaction, discard the state so it can be freed */ |
| transaction_fail(tr); |
| transaction_free(tr); |
| free(tr); |
| } |
| |
| /** |
| * transaction_activate - Activate transaction |
| * @tr: Transaction object. |
| */ |
| void transaction_activate(struct transaction* tr) { |
| assert(tr->fs); |
| assert(!transaction_is_active(tr)); |
| |
| tr->failed = false; |
| tr->invalid_block_found = false; |
| tr->complete = false; |
| tr->rebuild_free_set = false; |
| tr->repaired = false; |
| tr->min_free_block = 0; |
| tr->last_free_block = 0; |
| tr->last_tmp_free_block = 0; |
| tr->new_free_set = NULL; |
| |
| block_set_init(tr->fs, &tr->tmp_allocated); |
| block_set_init(tr->fs, &tr->allocated); |
| block_set_init(tr->fs, &tr->freed); |
| |
| fs_file_tree_init(tr->fs, &tr->files_added); |
| fs_file_tree_init(tr->fs, &tr->files_updated); |
| fs_file_tree_init(tr->fs, &tr->files_removed); |
| |
| list_add_tail(&tr->fs->allocated, &tr->allocated.node); |
| list_add_tail(&tr->fs->allocated, &tr->tmp_allocated.node); |
| } |
| |
| /** |
| * transaction_init - Initialize new transaction object |
| * @tr: Transaction object. |
| * @fs: File system state object. |
| * @activate: Activate transaction |
| */ |
| void transaction_init(struct transaction* tr, struct fs* fs, bool activate) { |
| assert(fs); |
| assert(fs->dev); |
| |
| memset(tr, 0, sizeof(*tr)); |
| tr->fs = fs; |
| |
| list_initialize(&tr->open_files); |
| list_add_tail(&fs->transactions, &tr->node); |
| |
| if (activate) { |
| transaction_activate(tr); |
| } |
| } |
