source: mainline/uspace/lib/ext4/libext4_balloc.c@ 001307cf

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

simplied headers of more functions, improved bg_ref and inode_ref structures, added block group checksumming and fixed bug in block_group values updating

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