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 #include <assert.h>
18 #include <inttypes.h>
19 
20 #include "block_allocator.h"
21 #include "block_map.h"
22 #include "block_tree.h"
23 #include "debug.h"
24 #include "transaction.h"
25 
26 static bool print_block_map;
27 
28 /**
29  * block_map_init - Initialize in-memory block map structute
30  * @tr:         Transaction object.
31  * @block_map:  Block map object.
32  * @root:       Block mac of root tree.
33  * @block_size: Block size of device.
34  */
35 
block_map_init(const struct transaction * tr,struct block_map * block_map,const struct block_mac * root,size_t block_size)36 void block_map_init(const struct transaction* tr,
37                     struct block_map* block_map,
38                     const struct block_mac* root,
39                     size_t block_size) {
40     size_t block_num_size = tr->fs->block_num_size;
41     size_t block_mac_size = block_num_size + tr->fs->mac_size;
42     memset(block_map, 0, sizeof(*block_map));
43     block_tree_init(&block_map->tree, block_size, block_num_size,
44                     block_mac_size, block_mac_size);
45     block_map->tree.copy_on_write = 1;
46     block_map->tree.allow_copy_on_write = 1;
47     block_map->tree.root = *root;
48 }
49 
50 /**
51  * block_map_get - Lookup a block
52  * @tr:         Transaction object.
53  * @block_map:  Block map object.
54  * @index:      Index of block to get.
55  * @block_mac:  Pointer to return block_mac in.
56  *
57  * Return: %true if a block_mac exists at @index, %false if not. When returning
58  * %true, @block_mac will be filled in. Otherwise, @block_mac is not touched.
59  */
block_map_get(struct transaction * tr,struct block_map * block_map,data_block_t index,struct block_mac * block_mac)60 bool block_map_get(struct transaction* tr,
61                    struct block_map* block_map,
62                    data_block_t index,
63                    struct block_mac* block_mac) {
64     struct block_tree_path path;
65 
66     index++; /* 0 is not a valid block tree key */
67 
68     block_tree_walk(tr, &block_map->tree, index, false, &path);
69     if (block_tree_path_get_key(&path) != index) {
70         if (print_block_map) {
71             printf("%s: %" PRIu64 " not found (next key %" PRIu64 ")\n",
72                    __func__, index, block_tree_path_get_key(&path));
73         }
74         return false;
75     }
76     *block_mac = block_tree_path_get_data_block_mac(&path);
77 
78     return true;
79 }
80 
81 /**
82  * block_map_set - Store a block_mac
83  * @tr:         Transaction object.
84  * @block_map:  Block map object.
85  * @index:      Index of block to set.
86  * @block_mac:  block_mac to store, or %NULL to remove the block_mac at @index.
87  */
block_map_set(struct transaction * tr,struct block_map * block_map,data_block_t index,const struct block_mac * block_mac)88 void block_map_set(struct transaction* tr,
89                    struct block_map* block_map,
90                    data_block_t index,
91                    const struct block_mac* block_mac) {
92     struct block_tree_path path;
93 
94     index++; /* 0 is not a valid block tree key */
95 
96     if (tr->failed) {
97         pr_warn("transaction failed, ignore\n");
98         return;
99     }
100 
101     block_tree_walk(tr, &block_map->tree, index, false, &path);
102     if (tr->failed) {
103         pr_warn("transaction failed, abort\n");
104         return;
105     }
106     if (block_tree_path_get_key(&path) == index) {
107         if (print_block_map) {
108             printf("%s: block_map at %" PRIu64
109                    ": remove existing entry at %" PRIu64 "\n",
110                    __func__, block_mac_to_block(tr, &block_map->tree.root),
111                    index);
112         }
113         block_tree_remove(tr, &block_map->tree, index,
114                           block_tree_path_get_data(&path));
115         if (tr->failed) {
116             pr_warn("transaction failed, abort\n");
117             return;
118         }
119     }
120     if (block_mac && block_mac_valid(tr, block_mac)) {
121         if (print_block_map) {
122             printf("%s: block_map at %" PRIu64 ": [%" PRIu64 "] = %" PRIu64
123                    "\n",
124                    __func__, block_mac_to_block(tr, &block_map->tree.root),
125                    index, block_mac_to_block(tr, block_mac));
126         }
127         block_tree_insert(tr, &block_map->tree, index,
128                           block_mac_to_block(tr, block_mac));
129         /* TODO: insert mac */
130     }
131 }
132 
133 /**
134  * block_map_put_dirty - Release a block stored in a block_map, and update mac
135  * @tr:         Transaction object.
136  * @block_map:  Block map object.
137  * @index:      Index of block to update.
138  * @data:       block cache entry.
139  * @data_ref:   reference to @data.
140  */
block_map_put_dirty(struct transaction * tr,struct block_map * block_map,data_block_t index,void * data,struct obj_ref * data_ref)141 void block_map_put_dirty(struct transaction* tr,
142                          struct block_map* block_map,
143                          data_block_t index,
144                          void* data,
145                          struct obj_ref* data_ref) {
146     struct block_tree_path path;
147 
148     index++; /* 0 is not a valid block tree key */
149 
150     block_tree_walk(tr, &block_map->tree, index, false, &path);
151     if (tr->failed) {
152         pr_warn("transaction failed\n");
153         block_put_dirty_discard(data, data_ref);
154         return;
155     }
156 
157     if (print_block_map) {
158         printf("%s: %" PRIu64 " (found key %" PRIu64 ")\n", __func__, index,
159                block_tree_path_get_key(&path));
160     }
161 
162     assert(block_tree_path_get_key(&path) == index);
163     block_tree_path_put_dirty(tr, &path, path.count, data, data_ref);
164 }
165 
166 /**
167  * block_map_truncate - Free blocks
168  * @tr:         Transaction object.
169  * @block_map:  Block map object.
170  * @index:      Index to start freeing at.
171  *
172  * Remove and free all blocks starting at @index.
173  */
block_map_truncate(struct transaction * tr,struct block_map * block_map,data_block_t index)174 void block_map_truncate(struct transaction* tr,
175                         struct block_map* block_map,
176                         data_block_t index) {
177     struct block_tree_path path;
178     data_block_t key;
179     data_block_t data;
180     data_block_t curr_index;
181 
182     curr_index = index + 1; /* 0 is not a valid block tree key */
183 
184     while (true) {
185         block_tree_walk(tr, &block_map->tree, curr_index, false, &path);
186         if (tr->failed) {
187             pr_warn("transaction failed, abort\n");
188             return;
189         }
190         key = block_tree_path_get_key(&path);
191         if (!key) {
192             break;
193         }
194         assert(key >= curr_index);
195         data = block_tree_path_get_data(&path);
196         if (!data) {
197             /* block_tree_walk returned an empty insert spot for curr_index */
198             assert(key != curr_index);
199             curr_index = key;
200             continue;
201         }
202         assert(data);
203         block_tree_remove(tr, &block_map->tree, key, data);
204         if (tr->failed) {
205             pr_warn("transaction failed, abort\n");
206             return;
207         }
208         block_discard_dirty_by_block(tr->fs->dev, data);
209         block_free(tr, data);
210         if (tr->failed) {
211             pr_warn("transaction failed, abort\n");
212             return;
213         }
214     }
215 
216     /* Only a root leaf node should remain if truncating to 0 */
217     assert(index || path.count == 1);
218 }
219 
220 /**
221  * block_map_check - Check block map for errors
222  * @tr:             Transaction object.
223  * @block_map:      Block map object.
224  * @max_index:      Block map index at and after which no data is expected (i.e.
225  *                  maximum exclusive)
226  *
227  * Return: %false if an error was detected, %true otherwise.
228  */
block_map_check(struct transaction * tr,struct block_map * block_map,data_block_t max_index)229 bool block_map_check(struct transaction* tr,
230                      struct block_map* block_map,
231                      data_block_t max_index) {
232     struct block_tree_path path;
233     data_block_t prev_index = 0;
234     data_block_t index = 1;
235     data_block_t min = tr->fs->min_block_num;
236     data_block_t max = tr->fs->dev->block_count;
237     data_block_t data;
238 
239     if (!block_tree_check(tr, &block_map->tree)) {
240         return false;
241     }
242 
243     max_index++; /* 0 is not a valid block tree key */
244 
245     block_tree_walk(tr, &block_map->tree, index, false, &path);
246     index = block_tree_path_get_key(&path);
247     while (index) {
248         if (index <= prev_index) {
249             pr_err("block map indices are not sequential, %" PRIu64
250                    " is after %" PRIu64 "\n",
251                    index, prev_index);
252             return false;
253         }
254         if (index >= max_index) {
255             pr_err("block map index %" PRIu64
256                    " is past (exclusive) block map max index %" PRIu64 "\n",
257                    index, max_index);
258             return false;
259         }
260         data = block_tree_path_get_data(&path);
261         if (data < min) {
262             pr_err("block map data %" PRIu64 " < minimum block %" PRIu64 "\n",
263                    index, min);
264             return false;
265         }
266         if (data >= max) {
267             pr_err("block map data %" PRIu64 " >= block count %" PRIu64 "\n",
268                    index, max);
269             return false;
270         }
271         prev_index = index;
272         block_tree_path_next(&path);
273         index = block_tree_path_get_key(&path);
274     }
275 
276     return true;
277 }
278 
279 /**
280  * block_map_free - Free blocks
281  * @tr:         Transaction object.
282  * @block_map:  Block map object.
283  *
284  * Free block_map and all blocks stored in it.
285  */
block_map_free(struct transaction * tr,struct block_map * block_map)286 void block_map_free(struct transaction* tr, struct block_map* block_map) {
287     data_block_t root_block;
288 
289     if (!block_mac_valid(tr, &block_map->tree.root)) {
290         return;
291     }
292     if (print_block_map) {
293         printf("%s: root %" PRIu64 "\n", __func__,
294                block_mac_to_block(tr, &block_map->tree.root));
295         block_tree_print(tr, &block_map->tree);
296     }
297 
298     block_map_truncate(tr, block_map, 0);
299     if (tr->failed) {
300         pr_warn("transaction failed\n");
301         return;
302     }
303 
304     root_block = block_mac_to_block(tr, &block_map->tree.root);
305 
306     block_discard_dirty_by_block(tr->fs->dev, root_block);
307     block_free(tr, root_block);
308 }
309