source: mainline/uspace/lib/ext4/libext4_filesystem.c@ 2674db6

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

New block allocation algorithm (from ext2)
  • Property mode set to 100644
File size: 14.7 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_filesystem.c
35 * @brief TODO
36 */
37
38#include <byteorder.h>
39#include <errno.h>
40#include <malloc.h>
41#include "libext4.h"
42
43int ext4_filesystem_init(ext4_filesystem_t *fs, service_id_t service_id)
44{
45 int rc;
46 ext4_superblock_t *temp_superblock;
47 size_t block_size;
48 uint32_t block_ids_per_block;
49 int i;
50
51 fs->device = service_id;
52
53 // TODO what does constant 2048 mean?
54 rc = block_init(EXCHANGE_SERIALIZE, fs->device, 2048);
55 if (rc != EOK) {
56 return rc;
57 }
58
59 /* Read superblock from device */
60 rc = ext4_superblock_read_direct(fs->device, &temp_superblock);
61 if (rc != EOK) {
62 block_fini(fs->device);
63 return rc;
64 }
65
66 /* Read block size from superblock and check */
67 block_size = ext4_superblock_get_block_size(temp_superblock);
68 if (block_size > EXT4_MAX_BLOCK_SIZE) {
69 block_fini(fs->device);
70 return ENOTSUP;
71 }
72
73 /* Initialize block caching */
74 // TODO set cache MODE to write through (now writeback for faster testing)
75 rc = block_cache_init(service_id, block_size, 0, CACHE_MODE_WB);
76 if (rc != EOK) {
77 block_fini(fs->device);
78 return rc;
79 }
80
81 block_ids_per_block = block_size / sizeof(uint32_t);
82 fs->inode_block_limits[0] = EXT4_INODE_DIRECT_BLOCK_COUNT;
83 fs->inode_blocks_per_level[0] = 1;
84 for (i = 1; i < 4; i++) {
85 fs->inode_blocks_per_level[i] = fs->inode_blocks_per_level[i-1] *
86 block_ids_per_block;
87 fs->inode_block_limits[i] = fs->inode_block_limits[i-1] +
88 fs->inode_blocks_per_level[i];
89 }
90
91 /* Return loaded superblock */
92 fs->superblock = temp_superblock;
93
94 return EOK;
95}
96
97void ext4_filesystem_fini(ext4_filesystem_t *fs)
98{
99 free(fs->superblock);
100 block_fini(fs->device);
101}
102
103int ext4_filesystem_check_sanity(ext4_filesystem_t *fs)
104{
105 int rc;
106
107 rc = ext4_superblock_check_sanity(fs->superblock);
108 if (rc != EOK) {
109 return rc;
110 }
111
112 return EOK;
113}
114
115int ext4_filesystem_check_features(ext4_filesystem_t *fs, bool *o_read_only)
116{
117 /* Feature flags are present in rev 1 and later */
118 if (ext4_superblock_get_rev_level(fs->superblock) == 0) {
119 *o_read_only = false;
120 return EOK;
121 }
122
123 uint32_t incompatible_features;
124 incompatible_features = ext4_superblock_get_features_incompatible(fs->superblock);
125 incompatible_features &= ~EXT4_FEATURE_INCOMPAT_SUPP;
126 if (incompatible_features > 0) {
127 *o_read_only = true;
128 return ENOTSUP;
129 }
130
131 uint32_t compatible_read_only;
132 compatible_read_only = ext4_superblock_get_features_read_only(fs->superblock);
133 compatible_read_only &= ~EXT4_FEATURE_RO_COMPAT_SUPP;
134 if (compatible_read_only > 0) {
135 *o_read_only = true;
136 }
137
138 return EOK;
139}
140
141int ext4_filesystem_get_block_group_ref(ext4_filesystem_t *fs, uint32_t bgid,
142 ext4_block_group_ref_t **ref)
143{
144 int rc;
145 aoff64_t block_id;
146 uint32_t descriptors_per_block;
147 size_t offset;
148 ext4_block_group_ref_t *newref;
149
150 newref = malloc(sizeof(ext4_block_group_ref_t));
151 if (newref == NULL) {
152 return ENOMEM;
153 }
154
155 descriptors_per_block = ext4_superblock_get_block_size(fs->superblock)
156 / ext4_superblock_get_desc_size(fs->superblock);
157
158 /* Block group descriptor table starts at the next block after superblock */
159 block_id = ext4_superblock_get_first_data_block(fs->superblock) + 1;
160
161 /* Find the block containing the descriptor we are looking for */
162 block_id += bgid / descriptors_per_block;
163 offset = (bgid % descriptors_per_block) * ext4_superblock_get_desc_size(fs->superblock);
164
165 rc = block_get(&newref->block, fs->device, block_id, 0);
166 if (rc != EOK) {
167 free(newref);
168 return rc;
169 }
170
171 newref->block_group = newref->block->data + offset;
172 newref->dirty = false;
173
174 *ref = newref;
175
176 return EOK;
177}
178
179int ext4_filesystem_put_block_group_ref(ext4_block_group_ref_t *ref)
180{
181 int rc;
182
183 if (ref->dirty) {
184 ref->block->dirty = true;
185 }
186
187 rc = block_put(ref->block);
188 free(ref);
189
190 return rc;
191}
192
193int ext4_filesystem_get_inode_ref(ext4_filesystem_t *fs, uint32_t index,
194 ext4_inode_ref_t **ref)
195{
196 int rc;
197 aoff64_t block_id;
198 uint32_t block_group;
199 uint32_t offset_in_group;
200 uint32_t byte_offset_in_group;
201 size_t offset_in_block;
202 uint32_t inodes_per_group;
203 uint32_t inode_table_start;
204 uint16_t inode_size;
205 uint32_t block_size;
206 ext4_block_group_ref_t *bg_ref;
207 ext4_inode_ref_t *newref;
208
209 newref = malloc(sizeof(ext4_inode_ref_t));
210 if (newref == NULL) {
211 return ENOMEM;
212 }
213
214 inodes_per_group = ext4_superblock_get_inodes_per_group(fs->superblock);
215
216 /* inode numbers are 1-based, but it is simpler to work with 0-based
217 * when computing indices
218 */
219 index -= 1;
220 block_group = index / inodes_per_group;
221 offset_in_group = index % inodes_per_group;
222
223 rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
224 if (rc != EOK) {
225 free(newref);
226 return rc;
227 }
228
229 inode_table_start = ext4_block_group_get_inode_table_first_block(
230 bg_ref->block_group);
231
232 rc = ext4_filesystem_put_block_group_ref(bg_ref);
233 if (rc != EOK) {
234 free(newref);
235 return rc;
236 }
237
238 inode_size = ext4_superblock_get_inode_size(fs->superblock);
239 block_size = ext4_superblock_get_block_size(fs->superblock);
240
241 byte_offset_in_group = offset_in_group * inode_size;
242
243 block_id = inode_table_start + (byte_offset_in_group / block_size);
244 offset_in_block = byte_offset_in_group % block_size;
245
246 rc = block_get(&newref->block, fs->device, block_id, 0);
247 if (rc != EOK) {
248 free(newref);
249 return rc;
250 }
251
252 newref->inode = newref->block->data + offset_in_block;
253 /* we decremented index above, but need to store the original value
254 * in the reference
255 */
256 newref->index = index+1;
257 newref->dirty = false;
258
259 *ref = newref;
260
261 return EOK;
262}
263
264
265int ext4_filesystem_put_inode_ref(ext4_inode_ref_t *ref)
266{
267 int rc;
268
269 if (ref->dirty) {
270 ref->block->dirty = true;
271 }
272
273 rc = block_put(ref->block);
274 free(ref);
275
276 return rc;
277}
278
279int ext4_filesystem_get_inode_data_block_index(ext4_filesystem_t *fs, ext4_inode_t* inode,
280 aoff64_t iblock, uint32_t* fblock)
281{
282 int rc;
283 uint32_t offset_in_block;
284 uint32_t current_block;
285 aoff64_t block_offset_in_level;
286 int i;
287 int level;
288 block_t *block;
289
290 /* Handle inode using extents */
291 if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_INCOMPAT_EXTENTS) &&
292 ext4_inode_has_flag(inode, EXT4_INODE_FLAG_EXTENTS)) {
293 current_block = ext4_inode_get_extent_block(inode, iblock, fs->device);
294 *fblock = current_block;
295 return EOK;
296
297 }
298
299 /* Handle simple case when we are dealing with direct reference */
300 if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
301 current_block = ext4_inode_get_direct_block(inode, (uint32_t)iblock);
302 *fblock = current_block;
303 return EOK;
304 }
305
306 /* Determine the indirection level needed to get the desired block */
307 level = -1;
308 for (i = 1; i < 4; i++) {
309 if (iblock < fs->inode_block_limits[i]) {
310 level = i;
311 break;
312 }
313 }
314
315 if (level == -1) {
316 return EIO;
317 }
318
319 /* Compute offsets for the topmost level */
320 block_offset_in_level = iblock - fs->inode_block_limits[level-1];
321 current_block = ext4_inode_get_indirect_block(inode, level-1);
322 offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1];
323
324 if (current_block == 0) {
325 *fblock = 0;
326 return EOK;
327 }
328
329 /* Navigate through other levels, until we find the block number
330 * or find null reference meaning we are dealing with sparse file
331 */
332 while (level > 0) {
333 rc = block_get(&block, fs->device, current_block, 0);
334 if (rc != EOK) {
335 return rc;
336 }
337
338 current_block = uint32_t_le2host(((uint32_t*)block->data)[offset_in_block]);
339
340 rc = block_put(block);
341 if (rc != EOK) {
342 return rc;
343 }
344
345 if (current_block == 0) {
346 /* This is a sparse file */
347 *fblock = 0;
348 return EOK;
349 }
350
351 level -= 1;
352
353 /* If we are on the last level, break here as
354 * there is no next level to visit
355 */
356 if (level == 0) {
357 break;
358 }
359
360 /* Visit the next level */
361 block_offset_in_level %= fs->inode_blocks_per_level[level];
362 offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1];
363 }
364
365 *fblock = current_block;
366
367 return EOK;
368}
369
370
371int ext4_filesystem_set_inode_data_block_index(ext4_filesystem_t *fs,
372 ext4_inode_ref_t *inode_ref, aoff64_t iblock, uint32_t fblock)
373{
374
375 int rc;
376 uint32_t offset_in_block;
377 uint32_t current_block, new_block_addr;
378 uint32_t block_size;
379 aoff64_t block_offset_in_level;
380 int i;
381 int level;
382 block_t *block, *new_block;
383
384 /* Handle inode using extents */
385 if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_INCOMPAT_EXTENTS) &&
386 ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS)) {
387 // TODO
388 return ENOTSUP;
389
390 }
391
392 /* Handle simple case when we are dealing with direct reference */
393 if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
394 ext4_inode_set_direct_block(inode_ref->inode, (uint32_t)iblock, fblock);
395 inode_ref->dirty = true;
396 return EOK;
397 }
398
399 /* Determine the indirection level needed to get the desired block */
400 level = -1;
401 for (i = 1; i < 4; i++) {
402 if (iblock < fs->inode_block_limits[i]) {
403 level = i;
404 break;
405 }
406 }
407
408 if (level == -1) {
409 return EIO;
410 }
411
412 block_size = ext4_superblock_get_block_size(fs->superblock);
413
414 /* Compute offsets for the topmost level */
415 block_offset_in_level = iblock - fs->inode_block_limits[level-1];
416 current_block = ext4_inode_get_indirect_block(inode_ref->inode, level-1);
417 offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1];
418
419 if (current_block == 0) {
420 rc = ext4_bitmap_alloc_block(fs, inode_ref, &new_block_addr);
421 if (rc != EOK) {
422 // TODO error
423 EXT4FS_DBG("error in allocation");
424 }
425// EXT4FS_DBG("AAA: new addr \%u, level = \%u", new_block_addr, level);
426
427 ext4_inode_set_indirect_block(inode_ref->inode, level - 1, new_block_addr);
428
429 inode_ref->dirty = true;
430
431 rc = block_get(&new_block, fs->device, new_block_addr, BLOCK_FLAGS_NOREAD);
432 if (rc != EOK) {
433 EXT4FS_DBG("block load error");
434 // TODO error
435 }
436
437 memset(new_block->data, 0, block_size);
438 new_block->dirty = true;
439
440 rc = block_put(new_block);
441 if (rc != EOK) {
442 EXT4FS_DBG("block put error");
443 }
444
445// EXT4FS_DBG("allocated indirect block for level \%u, during setting iblock \%u", level, (uint32_t)iblock);
446
447 current_block = new_block_addr;
448 }
449
450 /* Navigate through other levels, until we find the block number
451 * or find null reference meaning we are dealing with sparse file
452 */
453 while (level > 0) {
454
455 rc = block_get(&block, fs->device, current_block, 0);
456 if (rc != EOK) {
457 return rc;
458 }
459
460 current_block = uint32_t_le2host(((uint32_t*)block->data)[offset_in_block]);
461
462 if (current_block == 0) {
463 if (level > 1) {
464
465 rc = ext4_bitmap_alloc_block(fs, inode_ref, &new_block_addr);
466 if (rc != EOK) {
467 // TODO error
468 EXT4FS_DBG("allocation error");
469 }
470
471 rc = block_get(&new_block, fs->device, new_block_addr, BLOCK_FLAGS_NOREAD);
472 if (rc != EOK) {
473 // TODO error
474
475 EXT4FS_DBG("BBB: error block loading");
476
477 }
478 memset(new_block->data, 0, block_size);
479 new_block->dirty = true;
480
481 block_put(new_block);
482
483 ((uint32_t*)block->data)[offset_in_block] = host2uint32_t_le(new_block_addr);
484 block->dirty = true;
485 current_block = new_block_addr;
486 } else {
487 ((uint32_t*)block->data)[offset_in_block] = host2uint32_t_le(fblock);
488 block->dirty = true;
489 }
490 }
491
492 rc = block_put(block);
493 if (rc != EOK) {
494 return rc;
495 }
496
497 level -= 1;
498
499 /* If we are on the last level, break here as
500 * there is no next level to visit
501 */
502 if (level == 0) {
503 break;
504 }
505
506 /* Visit the next level */
507 block_offset_in_level %= fs->inode_blocks_per_level[level];
508 offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1];
509 }
510
511 return EOK;
512}
513
514int ext4_filesystem_release_inode_block(ext4_filesystem_t *fs,
515 ext4_inode_ref_t *inode_ref, uint32_t iblock)
516{
517 int rc;
518 uint32_t fblock;
519 int i;
520 int level;
521 aoff64_t block_offset_in_level;
522 uint32_t current_block;
523 uint32_t offset_in_block;
524 block_t *block;
525 ext4_inode_t *inode = inode_ref->inode;
526
527 /* TODO handle extents */
528
529
530 /* Handle simple case when we are dealing with direct reference */
531 if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
532 fblock = ext4_inode_get_direct_block(inode, iblock);
533 // Sparse file
534 if (fblock == 0) {
535 return EOK;
536 }
537
538 ext4_inode_set_direct_block(inode, iblock, 0);
539 return ext4_bitmap_free_block(fs, inode_ref, fblock);
540 }
541
542
543 /* Determine the indirection level needed to get the desired block */
544 level = -1;
545 for (i = 1; i < 4; i++) {
546 if (iblock < fs->inode_block_limits[i]) {
547 level = i;
548 break;
549 }
550 }
551
552 if (level == -1) {
553 return EIO;
554 }
555
556 /* Compute offsets for the topmost level */
557 block_offset_in_level = iblock - fs->inode_block_limits[level-1];
558 current_block = ext4_inode_get_indirect_block(inode, level-1);
559 offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1];
560
561 /* Navigate through other levels, until we find the block number
562 * or find null reference meaning we are dealing with sparse file
563 */
564 while (level > 0) {
565 rc = block_get(&block, fs->device, current_block, 0);
566 if (rc != EOK) {
567 return rc;
568 }
569
570 current_block = uint32_t_le2host(((uint32_t*)block->data)[offset_in_block]);
571
572 // Set zero
573 if (level == 1) {
574 ((uint32_t*)block->data)[offset_in_block] = host2uint32_t_le(0);
575 block->dirty = true;
576 }
577
578 rc = block_put(block);
579 if (rc != EOK) {
580 return rc;
581 }
582
583 level -= 1;
584
585 /* If we are on the last level, break here as
586 * there is no next level to visit
587 */
588 if (level == 0) {
589 break;
590 }
591
592 /* Visit the next level */
593 block_offset_in_level %= fs->inode_blocks_per_level[level];
594 offset_in_block = block_offset_in_level / fs->inode_blocks_per_level[level-1];
595 }
596
597 fblock = current_block;
598
599 if (fblock == 0) {
600 return EOK;
601 }
602
603 return ext4_bitmap_free_block(fs, inode_ref, fblock);
604
605}
606
607
608/**
609 * @}
610 */
Note: See TracBrowser for help on using the repository browser.