1 /*
2  * Copyright (C) 2015-2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <stdbool.h>
20 #include <stdint.h>
21 #include <stdio.h>
22 #include <string.h>
23 
24 #include <lk/list.h>
25 
26 #include "block_cache.h"
27 #include "block_range.h"
28 #include "block_tree.h"
29 
30 extern bool print_lookup; /* TODO: remove */
31 
32 #define BLOCK_SET_MAX_DEPTH (BLOCK_TREE_MAX_DEPTH)
33 
34 /**
35  * struct block_set - In-memory state of B+ tree backed block set
36  * @node:               List node used to link transaction allocated sets in fs.
37  * @block_tree:         Block tree state.
38  * @inserting_range:    Block range added to set but not yet in @block_tree.
39  * @updating:           %true while updating the set, %false otherwise. If a
40  *                      set insert or remove operation is re-entered while
41  *                      @updating is %true, the update is only applied to
42  *                      @inserting_range/@removing_range.
43  *
44  * In-memory state of B+ tree backed block set. Blocks that are part of the
45  * block-set are tracked as ranges. A range is stored in @block_tree with the
46  * start values as the key and the end value as the data. Unless an update is
47  * in progress, all ranges in @block_tree are non-overlapping, and non-adjacent.
48  * For instance, a block set containing only block 1 and 3 will be stored as two
49  * ranges in @block_tree. Adding block 2 to this block-set will cause those two
50  * ranges to be merged into a single range covering block 1 through 3.
51  */
52 struct block_set {
53     struct list_node node;
54     struct block_tree block_tree;
55     struct block_range initial_range;
56     bool updating;
57 };
58 
59 #define BLOCK_SET_INITIAL_VALUE(block_set)                                   \
60     {                                                                        \
61         .node = LIST_INITIAL_CLEARED_VALUE,                                  \
62         .block_tree = BLOCK_TREE_INITIAL_VALUE(block_set.block_tree),        \
63         .initial_range = BLOCK_RANGE_INITIAL_VALUE(block_set.initial_range), \
64         .updating = 0,                                                       \
65     }
66 
67 struct transaction;
68 struct fs;
69 
70 void block_set_print(struct transaction* tr, struct block_set* set);
71 bool block_set_check(struct transaction* tr, struct block_set* set);
72 
73 bool block_set_block_in_set(struct transaction* tr,
74                             struct block_set* set,
75                             data_block_t block);
76 bool block_set_range_in_set(struct transaction* tr,
77                             struct block_set* set,
78                             struct block_range range);
79 bool block_set_range_not_in_set(struct transaction* tr,
80                                 struct block_set* set,
81                                 struct block_range range);
82 
83 data_block_t block_set_find_next_block(struct transaction* tr,
84                                        struct block_set* set,
85                                        data_block_t min_block,
86                                        bool in_set);
87 
88 struct block_range block_set_find_next_range(struct transaction* tr,
89                                              struct block_set* set,
90                                              data_block_t min_block);
91 
92 bool block_set_overlap(struct transaction* tr,
93                        struct block_set* set_a,
94                        struct block_set* set_b);
95 
96 void block_set_add_range(struct transaction* tr,
97                          struct block_set* set,
98                          struct block_range range);
99 
100 void block_set_add_block(struct transaction* tr,
101                          struct block_set* set,
102                          data_block_t block);
103 
104 void block_set_remove_range(struct transaction* tr,
105                             struct block_set* set,
106                             struct block_range range);
107 
108 void block_set_remove_block(struct transaction* tr,
109                             struct block_set* set,
110                             data_block_t block);
111 
112 void block_set_init(struct fs* fs, struct block_set* set);
113 
114 void block_set_add_initial_range(struct block_set* set,
115                                  struct block_range range);
116 
117 void block_set_copy(struct transaction* tr,
118                     struct block_set* dest,
119                     const struct block_set* src);
120 
121 void block_set_copy_ro_fs(struct fs* fs,
122                           struct block_set* dest,
123                           const struct block_set* src);
124 
125 void block_set_copy_ro(struct transaction* tr,
126                        struct block_set* dest,
127                        const struct block_set* src);
128