source: mainline/uspace/lib/ext4/libext4_balloc.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: 16.1 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);
164
165 EXT4FS_DBG("first =\%u (bg \%u), last = \%u (bg \%u)", first, block_group_first, first + count, block_group_last);
166
167 ext4_block_group_ref_t *bg_ref;
168 rc = ext4_filesystem_get_block_group_ref(fs, block_group_first, &bg_ref);
169 if (rc != EOK) {
170 EXT4FS_DBG("error in loading bg_ref \%d", rc);
171 return rc;
172 }
173
174 uint32_t index_in_group_first =
175 ext4_balloc_blockaddr2_index_in_group(sb, first);
176
177 uint32_t bitmap_block_addr = ext4_block_group_get_block_bitmap(
178 bg_ref->block_group, sb);
179
180 block_t *bitmap_block;
181 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr, 0);
182 if (rc != EOK) {
183 EXT4FS_DBG("error in loading bitmap \%d", rc);
184 return rc;
185 }
186
187 ext4_bitmap_free_bits(bitmap_block->data, index_in_group_first, count);
188
189 bitmap_block->dirty = true;
190
191 rc = block_put(bitmap_block);
192 if (rc != EOK) {
193 // Error in saving bitmap
194 ext4_filesystem_put_block_group_ref(bg_ref);
195 EXT4FS_DBG("error in saving bitmap \%d", rc);
196 return rc;
197 }
198
199 uint32_t block_size = ext4_superblock_get_block_size(sb);
200
201 // Update superblock free blocks count
202 uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
203 sb_free_blocks += count;
204 ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
205
206 // Update inode blocks count
207 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
208 ino_blocks -= count * (block_size / EXT4_INODE_BLOCK_SIZE);
209 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
210 inode_ref->dirty = true;
211
212 // Update block group free blocks count
213 uint32_t free_blocks = ext4_block_group_get_free_blocks_count(
214 bg_ref->block_group, sb);
215 free_blocks += count;
216 ext4_block_group_set_free_blocks_count(bg_ref->block_group,
217 sb, free_blocks);
218 bg_ref->dirty = true;
219
220 rc = ext4_filesystem_put_block_group_ref(bg_ref);
221 if (rc != EOK) {
222 EXT4FS_DBG("error in saving bg_ref \%d", rc);
223 // TODO error
224 return rc;
225 }
226
227 return EOK;
228}
229
230static uint32_t ext4_balloc_get_first_data_block_in_group(
231 ext4_superblock_t *sb, ext4_block_group_t *bg, uint32_t bgid)
232{
233 uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
234 uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(
235 bg, sb);
236 uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
237 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
238 uint32_t block_size = ext4_superblock_get_block_size(sb);
239 uint32_t inode_table_bytes;
240
241 if (bgid < block_group_count - 1) {
242 inode_table_bytes = inodes_per_group * inode_table_item_size;
243 } else {
244 // last block group could be smaller
245 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
246 inode_table_bytes =
247 (inodes_count_total - ((block_group_count - 1) * inodes_per_group))
248 * inode_table_item_size;
249 }
250
251 uint32_t inode_table_blocks = inode_table_bytes / block_size;
252
253 if (inode_table_bytes % block_size) {
254 inode_table_blocks++;
255 }
256
257 return inode_table_first_block + inode_table_blocks;
258}
259
260
261static uint32_t ext4_balloc_find_goal(ext4_inode_ref_t *inode_ref)
262{
263 int rc;
264 uint32_t goal = 0;
265
266 ext4_superblock_t *sb = inode_ref->fs->superblock;
267
268 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
269 uint32_t block_size = ext4_superblock_get_block_size(sb);
270 uint32_t inode_block_count = inode_size / block_size;
271
272 if (inode_size % block_size != 0) {
273 inode_block_count++;
274 }
275
276 if (inode_block_count > 0) {
277 // TODO check retval
278 ext4_filesystem_get_inode_data_block_index(inode_ref, inode_block_count - 1, &goal);
279
280 // TODO
281 // If goal == 0 -> SPARSE file !!!
282
283 goal++;
284 return goal;
285 }
286
287 // Identify block group of inode
288 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
289 uint32_t block_group = (inode_ref->index - 1) / inodes_per_group;
290 block_size = ext4_superblock_get_block_size(sb);
291
292 ext4_block_group_ref_t *bg_ref;
293 rc = ext4_filesystem_get_block_group_ref(inode_ref->fs, block_group, &bg_ref);
294 if (rc != EOK) {
295 return 0;
296 }
297
298 uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
299 uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(
300 bg_ref->block_group, sb);
301 uint16_t inode_table_item_size = ext4_superblock_get_inode_size(sb);
302 uint32_t inode_table_bytes;
303
304 if (block_group < block_group_count - 1) {
305 inode_table_bytes = inodes_per_group * inode_table_item_size;
306 } else {
307 // last block group could be smaller
308 uint32_t inodes_count_total = ext4_superblock_get_inodes_count(sb);
309 inode_table_bytes =
310 (inodes_count_total - ((block_group_count - 1) * inodes_per_group))
311 * inode_table_item_size;
312 }
313
314 uint32_t inode_table_blocks = inode_table_bytes / block_size;
315
316 if (inode_table_bytes % block_size) {
317 inode_table_blocks++;
318 }
319
320 goal = inode_table_first_block + inode_table_blocks;
321
322 ext4_filesystem_put_block_group_ref(bg_ref);
323
324 return goal;
325}
326
327int ext4_balloc_alloc_block(
328 ext4_inode_ref_t *inode_ref, uint32_t *fblock)
329{
330 int rc;
331 uint32_t allocated_block = 0;
332
333 uint32_t bitmap_block_addr;
334 block_t *bitmap_block;
335 uint32_t rel_block_idx = 0;
336
337 // Find GOAL
338 uint32_t goal = ext4_balloc_find_goal(inode_ref);
339 if (goal == 0) {
340 // TODO
341 EXT4FS_DBG("ERRORR (goal == 0)");
342 return ENOSPC;
343 }
344
345 ext4_superblock_t *sb = inode_ref->fs->superblock;
346
347 // Load block group number for goal and relative index
348 uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, goal);
349 uint32_t index_in_group = ext4_balloc_blockaddr2_index_in_group(sb, goal);
350
351
352 ext4_block_group_ref_t *bg_ref;
353 rc = ext4_filesystem_get_block_group_ref(inode_ref->fs, block_group, &bg_ref);
354 if (rc != EOK) {
355 EXT4FS_DBG("initial BG ref not loaded");
356 return rc;
357 }
358
359 uint32_t first_in_group =
360 ext4_balloc_get_first_data_block_in_group(sb,
361 bg_ref->block_group, block_group);
362
363 uint32_t first_in_group_index = ext4_balloc_blockaddr2_index_in_group(
364 sb, first_in_group);
365
366 if (index_in_group < first_in_group_index) {
367 index_in_group = first_in_group_index;
368 }
369
370 // Load bitmap
371 bitmap_block_addr = ext4_block_group_get_block_bitmap(bg_ref->block_group,
372 sb);
373
374 rc = block_get(&bitmap_block, inode_ref->fs->device, bitmap_block_addr, 0);
375 if (rc != EOK) {
376 ext4_filesystem_put_block_group_ref(bg_ref);
377 EXT4FS_DBG("initial bitmap not loaded");
378 return rc;
379 }
380
381 // Check if goal is free
382 if (ext4_bitmap_is_free_bit(bitmap_block->data, index_in_group)) {
383 ext4_bitmap_set_bit(bitmap_block->data, index_in_group);
384 bitmap_block->dirty = true;
385 rc = block_put(bitmap_block);
386 if (rc != EOK) {
387 // TODO error
388 EXT4FS_DBG("goal check: error in saving initial bitmap \%d", rc);
389 ext4_filesystem_put_block_group_ref(bg_ref);
390 return rc;
391 }
392
393 allocated_block = goal;
394 goto success;
395
396 }
397
398 uint32_t blocks_in_group = ext4_superblock_get_blocks_in_group(sb, block_group);
399
400 uint32_t end_idx = (index_in_group + 63) & ~63;
401 if (end_idx > blocks_in_group) {
402 end_idx = blocks_in_group;
403 }
404
405 // Try to find free block near to goal
406 for (uint32_t tmp_idx = index_in_group + 1; tmp_idx < end_idx; ++tmp_idx) {
407 if (ext4_bitmap_is_free_bit(bitmap_block->data, tmp_idx)) {
408
409 ext4_bitmap_set_bit(bitmap_block->data, tmp_idx);
410 bitmap_block->dirty = true;
411 rc = block_put(bitmap_block);
412 if (rc != EOK) {
413 // TODO error
414 EXT4FS_DBG("near blocks: error in saving initial bitmap \%d", rc);
415 }
416
417 allocated_block = ext4_balloc_index_in_group2blockaddr(
418 sb, tmp_idx, block_group);
419
420 goto success;
421 }
422
423 }
424
425 // Find free BYTE in bitmap
426 rc = ext4_bitmap_find_free_byte_and_set_bit(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
427 if (rc == EOK) {
428 bitmap_block->dirty = true;
429 rc = block_put(bitmap_block);
430 if (rc != EOK) {
431 // TODO error
432 EXT4FS_DBG("free byte: error in saving initial bitmap \%d", rc);
433 }
434
435 allocated_block = ext4_balloc_index_in_group2blockaddr(
436 sb, rel_block_idx, block_group);
437
438 goto success;
439 }
440
441 // Find free bit in bitmap
442 rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
443 if (rc == EOK) {
444 bitmap_block->dirty = true;
445 rc = block_put(bitmap_block);
446 if (rc != EOK) {
447 // TODO error
448 EXT4FS_DBG("free bit: error in saving initial bitmap \%d", rc);
449 }
450
451 allocated_block = ext4_balloc_index_in_group2blockaddr(
452 sb, rel_block_idx, block_group);
453
454 goto success;
455 }
456
457 // No free block found yet
458 block_put(bitmap_block);
459 ext4_filesystem_put_block_group_ref(bg_ref);
460
461 // Try other block groups
462 uint32_t block_group_count = ext4_superblock_get_block_group_count(sb);
463
464 uint32_t bgid = (block_group + 1) % block_group_count;
465 uint32_t count = block_group_count;
466
467 while (count > 0) {
468 rc = ext4_filesystem_get_block_group_ref(inode_ref->fs, bgid, &bg_ref);
469 if (rc != EOK) {
470 EXT4FS_DBG("errrrrrrrrrrr");
471 return rc;
472 }
473
474 // Load bitmap
475 bitmap_block_addr = ext4_block_group_get_block_bitmap(
476 bg_ref->block_group, sb);
477
478 rc = block_get(&bitmap_block, inode_ref->fs->device, bitmap_block_addr, 0);
479 if (rc != EOK) {
480 ext4_filesystem_put_block_group_ref(bg_ref);
481 EXT4FS_DBG("errrrrrrrrrr");
482 return rc;
483 }
484
485 first_in_group = ext4_balloc_get_first_data_block_in_group(
486 sb, bg_ref->block_group, bgid);
487 index_in_group = ext4_balloc_blockaddr2_index_in_group(sb,
488 first_in_group);
489 blocks_in_group = ext4_superblock_get_blocks_in_group(sb, bgid);
490
491 first_in_group_index = ext4_balloc_blockaddr2_index_in_group(
492 sb, first_in_group);
493
494 if (index_in_group < first_in_group_index) {
495 index_in_group = first_in_group_index;
496 }
497
498
499 rc = ext4_bitmap_find_free_byte_and_set_bit(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
500 if (rc == EOK) {
501 bitmap_block->dirty = true;
502 rc = block_put(bitmap_block);
503 if (rc != EOK) {
504 // TODO error
505 EXT4FS_DBG("error in saving bitmap \%d", rc);
506 }
507
508 allocated_block = ext4_balloc_index_in_group2blockaddr(
509 sb, rel_block_idx, bgid);
510
511 goto success;
512 }
513
514 // Find free bit in bitmap
515 rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data, index_in_group, &rel_block_idx, blocks_in_group);
516 if (rc == EOK) {
517 bitmap_block->dirty = true;
518 rc = block_put(bitmap_block);
519 if (rc != EOK) {
520 // TODO error
521 EXT4FS_DBG("error in saving bitmap \%d", rc);
522 }
523
524 allocated_block = ext4_balloc_index_in_group2blockaddr(
525 sb, rel_block_idx, bgid);
526
527 goto success;
528 }
529
530
531 // Next group
532 block_put(bitmap_block);
533 ext4_filesystem_put_block_group_ref(bg_ref);
534 bgid = (bgid + 1) % block_group_count;
535 count--;
536 }
537
538 return ENOSPC;
539
540success:
541 ; // Empty command - because of syntax
542
543 uint32_t block_size = ext4_superblock_get_block_size(sb);
544
545 // Update superblock free blocks count
546 uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
547 sb_free_blocks--;
548 ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
549
550 // Update inode blocks (different block size!) count
551
552 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
553 ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
554 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
555 inode_ref->dirty = true;
556
557 // Update block group free blocks count
558 uint32_t bg_free_blocks = ext4_block_group_get_free_blocks_count(
559 bg_ref->block_group, sb);
560 bg_free_blocks--;
561 ext4_block_group_set_free_blocks_count(bg_ref->block_group, sb, bg_free_blocks);
562 bg_ref->dirty = true;
563
564 ext4_filesystem_put_block_group_ref(bg_ref);
565
566 *fblock = allocated_block;
567 return EOK;
568}
569
570
571/**
572 * @}
573 */
Note: See TracBrowser for help on using the repository browser.