blob: 2333537f357afa4879c733912eac36989fa616fb [file] [log] [blame]
/*
* 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.
*/
#pragma once
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <lk/list.h>
#include "block_cache.h"
#include "block_range.h"
#include "block_tree.h"
extern bool print_lookup; /* TODO: remove */
#define BLOCK_SET_MAX_DEPTH (BLOCK_TREE_MAX_DEPTH)
/**
* struct block_set - In-memory state of B+ tree backed block set
* @node: List node used to link transaction allocated sets in fs.
* @block_tree: Block tree state.
* @inserting_range: Block range added to set but not yet in @block_tree.
* @updating: %true while updating the set, %false otherwise. If a
* set insert or remove operation is re-entered while
* @updating is %true, the update is only applied to
* @inserting_range/@removing_range.
*
* In-memory state of B+ tree backed block set. Blocks that are part of the
* block-set are tracked as ranges. A range is stored in @block_tree with the
* start values as the key and the end value as the data. Unless an update is
* in progress, all ranges in @block_tree are non-overlapping, and non-adjacent.
* For instance, a block set containing only block 1 and 3 will be stored as two
* ranges in @block_tree. Adding block 2 to this block-set will cause those two
* ranges to be merged into a single range covering block 1 through 3.
*/
struct block_set {
struct list_node node;
struct block_tree block_tree;
struct block_range initial_range;
bool updating;
};
#define BLOCK_SET_INITIAL_VALUE(block_set) \
{ \
.node = LIST_INITIAL_CLEARED_VALUE, \
.block_tree = BLOCK_TREE_INITIAL_VALUE(block_set.block_tree), \
.initial_range = BLOCK_RANGE_INITIAL_VALUE(block_set.initial_range), \
.updating = 0, \
}
struct transaction;
struct fs;
void block_set_print(struct transaction* tr, struct block_set* set);
bool block_set_check(struct transaction* tr, struct block_set* set);
bool block_set_block_in_set(struct transaction* tr,
struct block_set* set,
data_block_t block);
bool block_set_range_in_set(struct transaction* tr,
struct block_set* set,
struct block_range range);
bool block_set_range_not_in_set(struct transaction* tr,
struct block_set* set,
struct block_range range);
data_block_t block_set_find_next_block(struct transaction* tr,
struct block_set* set,
data_block_t min_block,
bool in_set);
struct block_range block_set_find_next_range(struct transaction* tr,
struct block_set* set,
data_block_t min_block);
bool block_set_overlap(struct transaction* tr,
struct block_set* set_a,
struct block_set* set_b);
void block_set_add_range(struct transaction* tr,
struct block_set* set,
struct block_range range);
void block_set_add_block(struct transaction* tr,
struct block_set* set,
data_block_t block);
void block_set_remove_range(struct transaction* tr,
struct block_set* set,
struct block_range range);
void block_set_remove_block(struct transaction* tr,
struct block_set* set,
data_block_t block);
void block_set_init(struct fs* fs, struct block_set* set);
void block_set_add_initial_range(struct block_set* set,
struct block_range range);
void block_set_copy(struct transaction* tr,
struct block_set* dest,
const struct block_set* src);
void block_set_copy_ro_fs(struct fs* fs,
struct block_set* dest,
const struct block_set* src);
void block_set_copy_ro(struct transaction* tr,
struct block_set* dest,
const struct block_set* src);