source: mainline/uspace/lib/ext4/libext4_extent.c@ 5b0a3946

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 5b0a3946 was 5b0a3946, checked in by Frantisek Princ <frantisek.princ@…>, 14 years ago

developement version of releasing more complex extent tree with nontrivial depth (> 0)
  • Property mode set to 100644
File size: 13.0 KB
Line 
1/*
2 * Copyright (c) 2011 Frantisek Princ
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libext4
30 * @{
31 */
32
33/**
34 * @file libext4_extent.c
35 * @brief Ext4 extent structures operations.
36 */
37
38#include <byteorder.h>
39#include <errno.h>
40#include <malloc.h>
41#include "libext4.h"
42
43uint32_t ext4_extent_get_first_block(ext4_extent_t *extent)
44{
45 return uint32_t_le2host(extent->first_block);
46}
47
48void ext4_extent_set_first_block(ext4_extent_t *extent, uint32_t first_block)
49{
50 extent->first_block = host2uint32_t_le(first_block);
51}
52
53uint16_t ext4_extent_get_block_count(ext4_extent_t *extent)
54{
55 return uint16_t_le2host(extent->block_count);
56}
57
58void ext4_extent_set_block_count(ext4_extent_t *extent, uint16_t block_count)
59{
60 extent->block_count = host2uint16_t_le(block_count);
61}
62
63uint64_t ext4_extent_get_start(ext4_extent_t *extent)
64{
65 return ((uint64_t)uint16_t_le2host(extent->start_hi)) << 32 |
66 ((uint64_t)uint32_t_le2host(extent->start_lo));
67}
68
69void ext4_extent_set_start(ext4_extent_t *extent, uint64_t start)
70{
71 extent->start_lo = host2uint32_t_le((start << 32) >> 32);
72 extent->start_hi = host2uint16_t_le((uint16_t)(start >> 32));
73}
74
75uint32_t ext4_extent_index_get_first_block(ext4_extent_index_t *index)
76{
77 return uint32_t_le2host(index->first_block);
78}
79
80void ext4_extent_index_set_first_block(ext4_extent_index_t *index,
81 uint32_t first)
82{
83 index->first_block = host2uint32_t_le(first);
84}
85
86uint64_t ext4_extent_index_get_leaf(ext4_extent_index_t *index)
87{
88 return ((uint64_t)uint16_t_le2host(index->leaf_hi)) << 32 |
89 ((uint64_t)uint32_t_le2host(index->leaf_lo));
90}
91
92void ext4_extent_index_set_leaf(ext4_extent_index_t *index, uint64_t leaf)
93{
94 index->leaf_lo = host2uint32_t_le((leaf << 32) >> 32);
95 index->leaf_hi = host2uint16_t_le((uint16_t)(leaf >> 32));
96}
97
98uint16_t ext4_extent_header_get_magic(ext4_extent_header_t *header)
99{
100 return uint16_t_le2host(header->magic);
101}
102
103void ext4_extent_header_set_magic(ext4_extent_header_t *header, uint16_t magic)
104{
105 header->magic = host2uint16_t_le(magic);
106}
107
108uint16_t ext4_extent_header_get_entries_count(ext4_extent_header_t *header)
109{
110 return uint16_t_le2host(header->entries_count);
111}
112
113void ext4_extent_header_set_entries_count(ext4_extent_header_t *header,
114 uint16_t count)
115{
116 header->entries_count = host2uint16_t_le(count);
117}
118
119uint16_t ext4_extent_header_get_max_entries_count(ext4_extent_header_t *header)
120{
121 return uint16_t_le2host(header->max_entries_count);
122}
123
124void ext4_extent_header_set_max_entries_count(ext4_extent_header_t *header,
125 uint16_t max_count)
126{
127 header->max_entries_count = host2uint16_t_le(max_count);
128}
129
130uint16_t ext4_extent_header_get_depth(ext4_extent_header_t *header)
131{
132 return uint16_t_le2host(header->depth);
133}
134
135void ext4_extent_header_set_depth(ext4_extent_header_t *header, uint16_t depth)
136{
137 header->depth = host2uint16_t_le(depth);
138}
139
140uint32_t ext4_extent_header_get_generation(ext4_extent_header_t *header)
141{
142 return uint32_t_le2host(header->generation);
143}
144
145void ext4_extent_header_set_generation(ext4_extent_header_t *header,
146 uint32_t generation)
147{
148 header->generation = host2uint32_t_le(generation);
149}
150
151/**
152 * Binary search in extent index node
153 */
154static void ext4_extent_binsearch_idx(ext4_extent_header_t *header,
155 ext4_extent_index_t **index, uint32_t iblock)
156{
157 ext4_extent_index_t *r, *l, *m;
158
159 uint16_t entries_count = ext4_extent_header_get_entries_count(header);
160
161 if (entries_count == 1) {
162 *index = EXT4_EXTENT_FIRST_INDEX(header);
163 return;
164 }
165
166 l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
167 r = l + entries_count - 1;
168
169 while (l <= r) {
170 m = l + (r - l) / 2;
171 uint32_t first_block = ext4_extent_index_get_first_block(m);
172 if (iblock < first_block) {
173 r = m - 1;
174 } else {
175 l = m + 1;
176 }
177 }
178
179 *index = l - 1;
180}
181
182/**
183 * Binary search in extent leaf node
184 */
185static void ext4_extent_binsearch(ext4_extent_header_t *header,
186 ext4_extent_t **extent, uint32_t iblock)
187{
188 ext4_extent_t *r, *l, *m;
189
190 uint16_t entries_count = ext4_extent_header_get_entries_count(header);
191
192 if (entries_count == 0) {
193 // this leaf is empty
194 EXT4FS_DBG("EMPTY LEAF");
195 *extent = NULL;
196 return;
197 }
198
199 if (entries_count == 1) {
200 *extent = EXT4_EXTENT_FIRST(header);
201 return;
202 }
203
204 l = EXT4_EXTENT_FIRST(header) + 1;
205 r = l + entries_count - 1;
206
207 while (l < r) {
208 m = l + (r - l) / 2;
209 uint32_t first_block = ext4_extent_get_first_block(m);
210 if (iblock < first_block) {
211 r = m - 1;
212 } else {
213 l = m + 1;
214 }
215 }
216
217 *extent = l - 1;
218}
219
220// Reading routine without saving blocks to path - for saving memory during finding block
221int ext4_extent_find_block(ext4_inode_ref_t *inode_ref, uint32_t iblock, uint32_t *fblock)
222{
223 int rc;
224
225 block_t* block = NULL;
226
227 ext4_extent_header_t *header = ext4_inode_get_extent_header(inode_ref->inode);
228 while (ext4_extent_header_get_depth(header) != 0) {
229
230 ext4_extent_index_t *index;
231 ext4_extent_binsearch_idx(header, &index, iblock);
232
233 uint64_t child = ext4_extent_index_get_leaf(index);
234
235 if (block != NULL) {
236 block_put(block);
237 }
238
239 rc = block_get(&block, inode_ref->fs->device, child, BLOCK_FLAGS_NONE);
240 if (rc != EOK) {
241 return rc;
242 }
243
244 header = (ext4_extent_header_t *)block->data;
245 }
246
247
248 ext4_extent_t* extent = NULL;
249 ext4_extent_binsearch(header, &extent, iblock);
250
251 assert(extent != NULL);
252
253 uint32_t phys_block;
254 phys_block = ext4_extent_get_start(extent) + iblock;
255 phys_block -= ext4_extent_get_first_block(extent);
256
257 *fblock = phys_block;
258
259 if (block != NULL) {
260 block_put(block);
261 }
262
263
264 return EOK;
265}
266
267static int ext4_extent_find_extent(ext4_inode_ref_t *inode_ref,
268 uint32_t iblock, ext4_extent_path_t **ret_path)
269{
270 int rc;
271
272 ext4_extent_header_t *eh =
273 ext4_inode_get_extent_header(inode_ref->inode);
274
275 uint16_t depth = ext4_extent_header_get_depth(eh);
276
277 ext4_extent_path_t *tmp_path;
278
279 // Added 2 for possible tree growing
280 tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2));
281 if (tmp_path == NULL) {
282 return ENOMEM;
283 }
284
285 tmp_path[0].block = inode_ref->block;
286 tmp_path[0].header = eh;
287
288 uint16_t pos = 0;
289 while (ext4_extent_header_get_depth(eh) != 0) {
290
291 ext4_extent_binsearch_idx(tmp_path[pos].header, &tmp_path[pos].index, iblock);
292
293 tmp_path[pos].depth = depth;
294 tmp_path[pos].extent = NULL;
295
296 assert(tmp_path[pos].index != NULL);
297
298 uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);
299
300 block_t *block;
301 rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE);
302 if (rc != EOK) {
303 // TODO cleanup
304 EXT4FS_DBG("ERRRR");
305 return rc;
306 }
307
308 pos++;
309
310 eh = (ext4_extent_header_t *)block->data;
311 tmp_path[pos].block = block;
312 tmp_path[pos].header = eh;
313
314 }
315
316 tmp_path[pos].depth = 0;
317 tmp_path[pos].extent = NULL;
318 tmp_path[pos].index = NULL;
319
320 /* find extent */
321 ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent, iblock);
322
323 *ret_path = tmp_path;
324
325 return EOK;
326}
327
328static int ext4_extent_release(ext4_inode_ref_t *inode_ref, ext4_extent_t* extent)
329{
330 int rc;
331
332 uint64_t start = ext4_extent_get_start(extent);
333 uint16_t block_count = ext4_extent_get_block_count(extent);
334
335 rc = ext4_balloc_free_blocks(inode_ref, start, block_count);
336 if (rc != EOK) {
337 EXT4FS_DBG("ERROR");
338 return rc;
339 }
340
341 return EOK;
342}
343
344// Recursive release
345static int ext4_extent_release_branch(ext4_inode_ref_t *inode_ref,
346 ext4_extent_index_t *index)
347{
348 int rc;
349
350 block_t* block;
351
352 uint32_t fblock = ext4_extent_index_get_leaf(index);
353
354 EXT4FS_DBG("fblock = \%u", fblock);
355
356 rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NOREAD);
357 if (rc != EOK) {
358 EXT4FS_DBG("ERROR get_block");
359 return rc;
360 }
361
362 ext4_extent_header_t *header = block->data;
363
364 if (ext4_extent_header_get_depth(header)) {
365
366 ext4_extent_index_t *idx = EXT4_EXTENT_FIRST_INDEX(header);
367
368 for (uint32_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, ++idx) {
369 rc = ext4_extent_release_branch(inode_ref, idx);
370 if (rc != EOK) {
371 EXT4FS_DBG("error recursion");
372 return rc;
373 }
374 }
375 } else {
376 ext4_extent_t *ext = EXT4_EXTENT_FIRST(header);
377
378 for (uint32_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, ++ext) {
379 rc = ext4_extent_release(inode_ref, ext);
380 if (rc != EOK) {
381 EXT4FS_DBG("error recursion");
382 return rc;
383 }
384 }
385 }
386
387 rc = block_put(block);
388 if (rc != EOK) {
389 EXT4FS_DBG("ERROR put_block");
390 return rc;
391 }
392
393 ext4_balloc_free_block(inode_ref, fblock);
394
395 return EOK;
396}
397
398int ext4_extent_release_blocks_from(ext4_inode_ref_t *inode_ref, uint32_t iblock_from)
399{
400 int rc;
401
402 // 1) Delete iblock and successors in the same extent
403
404 ext4_extent_path_t *path;
405 rc = ext4_extent_find_extent(inode_ref, iblock_from, &path);
406 if (rc != EOK) {
407 return rc;
408 }
409
410 ext4_extent_path_t *path_ptr = path;
411 while (path_ptr->depth != 0) {
412 path_ptr++;
413 }
414
415 assert(path_ptr->extent != NULL);
416
417 uint32_t first_fblock;
418 first_fblock = ext4_extent_get_start(path_ptr->extent) + iblock_from;
419 first_fblock -= ext4_extent_get_first_block(path_ptr->extent);
420
421 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
422
423 uint16_t delete_count = block_count - first_fblock +
424 ext4_extent_get_start(path_ptr->extent);
425
426 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);
427
428 block_count -= delete_count;
429 ext4_extent_set_block_count(path_ptr->extent, block_count);
430
431 path_ptr->block->dirty = true;
432
433 bool check_tree = false;
434
435 uint16_t old_root_entries = ext4_extent_header_get_entries_count(path->header);
436
437 if (block_count == 0) {
438 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
439 entries--;
440 ext4_extent_header_set_entries_count(path_ptr->header, entries);
441
442 // If empty leaf, will be released and the whole tree must be checked
443 if (path_ptr != path) {
444 rc = ext4_balloc_free_block(inode_ref, path_ptr->block->pba);
445 if (rc != EOK) {
446 EXT4FS_DBG("ERROR");
447 // TODO
448 }
449 check_tree = true;
450 }
451 }
452
453 --path_ptr;
454
455 while ((path_ptr >= path) && check_tree) {
456
457 if (path_ptr > path) {
458
459 EXT4FS_DBG("not root");
460 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
461 entries--;
462 ext4_extent_header_set_entries_count(path_ptr->header, entries);
463
464 if (entries == 0) {
465 rc = ext4_balloc_free_block(inode_ref, path_ptr->block->pba);
466 if (rc != EOK) {
467 EXT4FS_DBG("ERROR");
468 // TODO
469 }
470 } else {
471 break;
472 }
473
474 } else {
475 EXT4FS_DBG("root");
476
477 // TODO tady je BUG asi
478
479 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
480 entries--;
481 ext4_extent_header_set_entries_count(path_ptr->header, entries);
482
483 break;
484 }
485
486 path_ptr--;
487 }
488
489 ext4_extent_header_t *header = path->header;
490
491 // 2) delete or successors first level extents/indexes
492 if (ext4_extent_header_get_depth(header)) {
493
494 ext4_extent_index_t *index = path->index + 1;
495 ext4_extent_index_t *stop = EXT4_EXTENT_FIRST_INDEX(header) +
496 old_root_entries;
497
498 if (index < stop) {
499 inode_ref->dirty = true;
500 }
501
502 while (index < stop) {
503 rc = ext4_extent_release_branch(inode_ref, index);
504 if (rc != EOK) {
505 EXT4FS_DBG("ERR");
506 // TODO error
507 }
508 ++index;
509
510 uint16_t entries = ext4_extent_header_get_entries_count(header);
511 entries--;
512 ext4_extent_header_set_entries_count(header, entries);
513
514 }
515
516 } else {
517
518 ext4_extent_t *extent = path->extent + 1;
519 ext4_extent_t *stop = EXT4_EXTENT_FIRST(header) +
520 old_root_entries;
521
522 if (extent != stop) {
523 inode_ref->dirty = true;
524 }
525
526 while (extent < stop) {
527 rc = ext4_extent_release(inode_ref, extent);
528 if (rc != EOK) {
529 EXT4FS_DBG("ERR");
530 // TODO error
531 }
532 ++extent;
533
534 uint16_t entries = ext4_extent_header_get_entries_count(header);
535 entries--;
536 ext4_extent_header_set_entries_count(header, entries);
537 }
538 }
539
540 uint16_t depth = path->depth;
541
542 // Put loaded blocks
543 // From 1 -> 0 is a block with inode data
544 for (uint16_t i = 1; i < depth; ++i) {
545 if (path[i].block) {
546 block_put(path[i].block);
547 }
548 }
549
550 // Destroy temporary data structure
551 free(path);
552
553 return EOK;
554}
555
556/**
557 * @}
558 */
Note: See TracBrowser for help on using the repository browser.