source: mainline/uspace/lib/ext4/libext4_balloc.c@ 3e2952b

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

more debugged version of releasing file/dir using extent
  • Property mode set to 100644
File size: 16.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_balloc.c
35 * @brief Physical block allocator.
36 */
37
38#include <errno.h>
39#include <sys/types.h>
40#include "libext4.h"
41
42static uint32_t ext4_balloc_blockaddr2_index_in_group(ext4_superblock_t *sb,
43 uint32_t block_addr)
44{
45 uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
46 uint32_t first_block = ext4_superblock_get_first_data_block(sb);
47
48 // First block == 0 or 1
49 if (first_block == 0) {
50 return block_addr % blocks_per_group;
51 } else {
52 return (block_addr - 1) % blocks_per_group;
53 }
54}
55
56static uint32_t ext4_balloc_index_in_group2blockaddr(ext4_superblock_t *sb,
57 uint32_t index, uint32_t bgid)
58{
59 uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
60
61 if (ext4_superblock_get_first_data_block(sb) == 0) {
62 return bgid * blocks_per_group + index;
63 } else {
64 return bgid * blocks_per_group + index + 1;
65 }
66
67}
68
69static uint32_t ext4_balloc_get_bgid_of_block(ext4_superblock_t *sb,
70 uint32_t block_addr)
71{
72 uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(sb);
73 uint32_t first_block = ext4_superblock_get_first_data_block(sb);
74
75 // First block == 0 or 1
76 if (first_block == 0) {
77 return block_addr / blocks_per_group;
78 } else {
79 return (block_addr - 1) / blocks_per_group;
80 }
81}
82
83
84int ext4_balloc_free_block(ext4_inode_ref_t *inode_ref, uint32_t block_addr)
85{
86 int rc;
87
88 ext4_filesystem_t *fs = inode_ref->fs;
89 ext4_superblock_t *sb = fs->superblock;
90
91 uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, block_addr);
92 uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(sb, block_addr);
93
94 ext4_block_group_ref_t *bg_ref;
95 rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
96 if (rc != EOK) {
97 EXT4FS_DBG("error in loading bg_ref \%d", rc);
98 return rc;
99 }
100
101 uint32_t bitmap_block_addr = ext4_block_group_get_block_bitmap(
102 bg_ref->block_group, sb);
103 block_t *bitmap_block;
104 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
105 if (rc != EOK) {
106 EXT4FS_DBG("error in loading bitmap \%d", rc);
107 return rc;
108 }
109
110 ext4_bitmap_free_bit(bitmap_block->data, index_in_group);
111 bitmap_block->dirty = true;
112
113 rc = block_put(bitmap_block);
114 if (rc != EOK) {
115 // Error in saving bitmap
116 ext4_filesystem_put_block_group_ref(bg_ref);
117 EXT4FS_DBG("error in saving bitmap \%d", rc);
118 return rc;
119 }
120
121 uint32_t block_size = ext4_superblock_get_block_size(sb);
122
123 // Update superblock free blocks count
124 uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
125 sb_free_blocks++;
126 ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
127
128 // Update inode blocks count
129 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
130 ino_blocks -= block_size / EXT4_INODE_BLOCK_SIZE;
131 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
132 inode_ref->dirty = true;
133
134 // Update block group free blocks count
135 uint32_t free_blocks = ext4_block_group_get_free_blocks_count(
136 bg_ref->block_group, sb);
137 free_blocks++;
138 ext4_block_group_set_free_blocks_count(bg_ref->block_group,
139 sb, free_blocks);
140 bg_ref->dirty = true;
141
142 rc = ext4_filesystem_put_block_group_ref(bg_ref);
143 if (rc != EOK) {
144 EXT4FS_DBG("error in saving bg_ref \%d", rc);
145 // TODO error
146 return rc;
147 }
148
149 return EOK;
150}
151
152int ext4_balloc_free_blocks(ext4_inode_ref_t *inode_ref,
153 uint32_t first, uint32_t count)
154{
155 int rc;
156
157 ext4_filesystem_t *fs = inode_ref->fs;
158 ext4_superblock_t *sb = fs->superblock;
159
160 uint32_t block_group_first =
161 ext4_balloc_get_bgid_of_block(sb, first);
162 uint32_t block_group_last =
163 ext4_balloc_get_bgid_of_block(sb, first + count - 1);
164
165 assert(block_group_first == block_group_last);
166
167 rc = ext4_filesystem_get_block_group_ref(fs, block_group_first, &bg_ref);
168 if (rc != EOK) {
169 EXT4FS_DBG("error in loading bg_ref \%d", rc);
170 return rc;
171 }
172
173 uint32_t index_in_group_first =
174 ext4_balloc_blockaddr2_index_in_group(sb, first);
175
176 uint32_t bitmap_block_addr = ext4_block_group_get_block_bitmap(
177 bg_ref->block_group, sb);
178
179 block_t *bitmap_block;
180 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
181 if (rc != EOK) {
182 EXT4FS_DBG("error in loading bitmap \%d", rc);
183 return rc;
184 }
185
186 ext4_bitmap_free_bits(bitmap_block->data, index_in_group_first, count);
187
188 bitmap_block->dirty = true;
189
190 rc = block_put(bitmap_block);
191 if (rc != EOK) {
192 // Error in saving bitmap
193 ext4_filesystem_put_block_group_ref(bg_ref);
194 EXT4FS_DBG("error in saving bitmap \%d", rc);
195 return rc;
196 }
197
198 uint32_t block_size = ext4_superblock_get_block_size(sb);
199
200 // Update superblock free blocks count
201 uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
202 sb_free_blocks += count;
203 ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
204
205 // Update inode blocks count
206 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
207 ino_blocks -= count * (block_size / EXT4_INODE_BLOCK_SIZE);
208 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
209 inode_ref->dirty = true;
210
211 // Update block group free blocks count
212 uint32_t free_blocks = ext4_block_group_get_free_blocks_count(
213 bg_ref->block_group, sb);
214 free_blocks += count;
215 ext4_block_group_set_free_blocks_count(bg_ref->block_group,
216 sb, free_blocks);
217 bg_ref->dirty = true;
218
219 rc = ext4_filesystem_put_block_group_ref(bg_ref);
220 if (rc != EOK) {
221 EXT4FS_DBG("error in saving bg_ref \%d", rc);
222 // TODO error
223 return rc;
224 }
225
226 return EOK;
227}
228
229static uint32_t ext4_balloc_get_first_data_block_in_group(
230 ext4_superblock_t *sb, ext4_block_group_t *bg, uint32_t bgid)
231{
232 uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
233 uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(
234 bg, sb);
235 uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
236 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
237 uint32_t block_size = ext4_superblock_get_block_size(sb);
238 uint32_t inode_table_bytes;
239
240 if (bgid < block_group_count - 1) {
241 inode_table_bytes = inodes_per_group * inode_table_item_size;
242 } else {
243 // last block group could be smaller
244 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
245 inode_table_bytes =
246 (inodes_count_total - ((block_group_count - 1) * inodes_per_group))
247 * inode_table_item_size;
248 }
249
250 uint32_t inode_table_blocks = inode_table_bytes / block_size;
251
252 if (inode_table_bytes % block_size) {
253 inode_table_blocks++;
254 }
255
256 return inode_table_first_block + inode_table_blocks;
257}
258
259
260static uint32_t ext4_balloc_find_goal(ext4_inode_ref_t *inode_ref)
261{
262 int rc;
263 uint32_t goal = 0;
264
265 ext4_superblock_t *sb = inode_ref->fs->superblock;
266
267 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
268 uint32_t block_size = ext4_superblock_get_block_size(sb);
269 uint32_t inode_block_count = inode_size / block_size;
270
271 if (inode_size % block_size != 0) {
272 inode_block_count++;
273 }
274
275 if (inode_block_count > 0) {
276 // TODO check retval
277 ext4_filesystem_get_inode_data_block_index(inode_ref, inode_block_count - 1, &goal);
278
279 // TODO
280 // If goal == 0 -> SPARSE file !!!
281
282 goal++;
283 return goal;
284 }
285
286 // Identify block group of inode
287 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
288 uint32_t block_group = (inode_ref->index - 1) / inodes_per_group;
289 block_size = ext4_superblock_get_block_size(sb);
290
291 ext4_block_group_ref_t *bg_ref;
292 rc = ext4_filesystem_get_block_group_ref(inode_ref->fs, block_group, &bg_ref);
293 if (rc != EOK) {
294 return 0;
295 }
296
297 uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
298 uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(
299 bg_ref->block_group, sb);
300 uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
301 uint32_t inode_table_bytes;
302
303 if (block_group < block_group_count - 1) {
304 inode_table_bytes = inodes_per_group * inode_table_item_size;
305 } else {
306 // last block group could be smaller
307 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
308 inode_table_bytes =
309 (inodes_count_total - ((block_group_count - 1) * inodes_per_group))
310 * inode_table_item_size;
311 }
312
313 uint32_t inode_table_blocks = inode_table_bytes / block_size;
314
315 if (inode_table_bytes % block_size) {
316 inode_table_blocks++;
317 }
318
319 goal = inode_table_first_block + inode_table_blocks;
320
321 ext4_filesystem_put_block_group_ref(bg_ref);
322
323 return goal;
324}
325
326int ext4_balloc_alloc_block(
327 ext4_inode_ref_t *inode_ref, uint32_t *fblock)
328{
329 int rc;
330 uint32_t allocated_block = 0;
331
332 uint32_t bitmap_block_addr;
333 block_t *bitmap_block;
334 uint32_t rel_block_idx = 0;
335
336 // Find GOAL
337 uint32_t goal = ext4_balloc_find_goal(inode_ref);
338 if (goal == 0) {
339 // TODO
340 EXT4FS_DBG("ERRORR (goal == 0)");
341 return ENOSPC;
342 }
343
344 ext4_superblock_t *sb = inode_ref->fs->superblock;
345
346 // Load block group number for goal and relative index
347 uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, goal);
348 uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(sb, goal);
349
350
351 ext4_block_group_ref_t *bg_ref;
352 rc = ext4_filesystem_get_block_group_ref(inode_ref->fs, block_group, &bg_ref);
353 if (rc != EOK) {
354 EXT4FS_DBG("initial BG ref not loaded");
355 return rc;
356 }
357
358 uint32_t first_in_group =
359 ext4_balloc_get_first_data_block_in_group(sb,
360 bg_ref->block_group, block_group);
361
362 uint32_t first_in_group_index = ext4_balloc_blockaddr2_index_in_group(
363 sb, first_in_group);
364
365 if (index_in_group < first_in_group_index) {
366 index_in_group = first_in_group_index;
367 }
368
369 // Load bitmap
370 bitmap_block_addr = ext4_block_group_get_block_bitmap(bg_ref->block_group,
371 sb);
372
373 rc = block_get(&bitmap_block, inode_ref->fs->device, bitmap_block_addr, 0);
374 if (rc != EOK) {
375 ext4_filesystem_put_block_group_ref(bg_ref);
376 EXT4FS_DBG("initial bitmap not loaded");
377 return rc;
378 }
379
380 // Check if goal is free
381 if (ext4_bitmap_is_free_bit(bitmap_block->data, index_in_group)) {
382 ext4_bitmap_set_bit(bitmap_block->data, index_in_group);
383 bitmap_block->dirty = true;
384 rc = block_put(bitmap_block);
385 if (rc != EOK) {
386 // TODO error
387 EXT4FS_DBG("goal check: error in saving initial bitmap \%d", rc);
388 ext4_filesystem_put_block_group_ref(bg_ref);
389 return rc;
390 }
391
392 allocated_block = goal;
393 goto success;
394
395 }
396
397 uint32_t blocks_in_group = ext4_superblock_get_blocks_in_group(sb, block_group);
398
399 uint32_t end_idx = (index_in_group + 63) & ~63;
400 if (end_idx > blocks_in_group) {
401 end_idx = blocks_in_group;
402 }
403
404 // Try to find free block near to goal
405 for (uint32_t tmp_idx = index_in_group + 1; tmp_idx < end_idx; ++tmp_idx) {
406 if (ext4_bitmap_is_free_bit(bitmap_block->data, tmp_idx)) {
407
408 ext4_bitmap_set_bit(bitmap_block->data, tmp_idx);
409 bitmap_block->dirty = true;
410 rc = block_put(bitmap_block);
411 if (rc != EOK) {
412 // TODO error
413 EXT4FS_DBG("near blocks: error in saving initial bitmap \%d", rc);
414 }
415
416 allocated_block = ext4_balloc_index_in_group2blockaddr(
417 sb, tmp_idx, block_group);
418
419 goto success;
420 }
421
422 }
423
424 // Find free BYTE in bitmap
425 rc = ext4_bitmap_find_free_byte_and_set_bit(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
426 if (rc == EOK) {
427 bitmap_block->dirty = true;
428 rc = block_put(bitmap_block);
429 if (rc != EOK) {
430 // TODO error
431 EXT4FS_DBG("free byte: error in saving initial bitmap \%d", rc);
432 }
433
434 allocated_block = ext4_balloc_index_in_group2blockaddr(
435 sb, rel_block_idx, block_group);
436
437 goto success;
438 }
439
440 // Find free bit in bitmap
441 rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
442 if (rc == EOK) {
443 bitmap_block->dirty = true;
444 rc = block_put(bitmap_block);
445 if (rc != EOK) {
446 // TODO error
447 EXT4FS_DBG("free bit: error in saving initial bitmap \%d", rc);
448 }
449
450 allocated_block = ext4_balloc_index_in_group2blockaddr(
451 sb, rel_block_idx, block_group);
452
453 goto success;
454 }
455
456 // No free block found yet
457 block_put(bitmap_block);
458 ext4_filesystem_put_block_group_ref(bg_ref);
459
460 // Try other block groups
461 uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
462
463 uint32_t bgid = (block_group + 1) % block_group_count;
464 uint32_t count = block_group_count;
465
466 while (count > 0) {
467 rc = ext4_filesystem_get_block_group_ref(inode_ref->fs, bgid, &bg_ref);
468 if (rc != EOK) {
469 EXT4FS_DBG("errrrrrrrrrrr");
470 return rc;
471 }
472
473 // Load bitmap
474 bitmap_block_addr = ext4_block_group_get_block_bitmap(
475 bg_ref->block_group, sb);
476
477 rc = block_get(&bitmap_block, inode_ref->fs->device, bitmap_block_addr, 0);
478 if (rc != EOK) {
479 ext4_filesystem_put_block_group_ref(bg_ref);
480 EXT4FS_DBG("errrrrrrrrrr");
481 return rc;
482 }
483
484 first_in_group = ext4_balloc_get_first_data_block_in_group(
485 sb, bg_ref->block_group, bgid);
486 index_in_group = ext4_balloc_blockaddr2_index_in_group(sb,
487 first_in_group);
488 blocks_in_group = ext4_superblock_get_blocks_in_group(sb, bgid);
489
490 first_in_group_index = ext4_balloc_blockaddr2_index_in_group(
491 sb, first_in_group);
492
493 if (index_in_group < first_in_group_index) {
494 index_in_group = first_in_group_index;
495 }
496
497
498 rc = ext4_bitmap_find_free_byte_and_set_bit(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
499 if (rc == EOK) {
500 bitmap_block->dirty = true;
501 rc = block_put(bitmap_block);
502 if (rc != EOK) {
503 // TODO error
504 EXT4FS_DBG("error in saving bitmap \%d", rc);
505 }
506
507 allocated_block = ext4_balloc_index_in_group2blockaddr(
508 sb, rel_block_idx, bgid);
509
510 goto success;
511 }
512
513 // Find free bit in bitmap
514 rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
515 if (rc == EOK) {
516 bitmap_block->dirty = true;
517 rc = block_put(bitmap_block);
518 if (rc != EOK) {
519 // TODO error
520 EXT4FS_DBG("error in saving bitmap \%d", rc);
521 }
522
523 allocated_block = ext4_balloc_index_in_group2blockaddr(
524 sb, rel_block_idx, bgid);
525
526 goto success;
527 }
528
529
530 // Next group
531 block_put(bitmap_block);
532 ext4_filesystem_put_block_group_ref(bg_ref);
533 bgid = (bgid + 1) % block_group_count;
534 count--;
535 }
536
537 return ENOSPC;
538
539success:
540 ; // Empty command - because of syntax
541
542 uint32_t block_size = ext4_superblock_get_block_size(sb);
543
544 // Update superblock free blocks count
545 uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
546 sb_free_blocks--;
547 ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
548
549 // Update inode blocks (different block size!) count
550
551 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
552 ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
553 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
554 inode_ref->dirty = true;
555
556 // Update block group free blocks count
557 uint32_t bg_free_blocks = ext4_block_group_get_free_blocks_count(
558 bg_ref->block_group, sb);
559 bg_free_blocks--;
560 ext4_block_group_set_free_blocks_count(bg_ref->block_group, sb, bg_free_blocks);
561 bg_ref->dirty = true;
562
563 ext4_filesystem_put_block_group_ref(bg_ref);
564
565 *fblock = allocated_block;
566 return EOK;
567}
568
569
570/**
571 * @}
572 */
Note: See TracBrowser for help on using the repository browser.