source: mainline/uspace/lib/ext4/libext4_balloc.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: 9.4 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#include <errno.h>
34#include <sys/types.h>
35#include "libext4.h"
36
37int ext4_bitmap_free_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t block_index)
38{
39 int rc;
40 uint32_t blocks_per_group;
41 uint32_t block_group;
42 uint32_t index_in_group;
43 uint32_t bitmap_block;
44 uint32_t block_size;
45 ext4_block_group_ref_t *bg_ref;
46 block_t *block;
47 uint32_t first_block;
48
49 block_size = ext4_superblock_get_block_size(fs->superblock);
50 blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
51 first_block = ext4_superblock_get_first_data_block(fs->superblock);
52
53 // First block == 0 or 1
54 if (first_block == 0) {
55 block_group = block_index / blocks_per_group;
56 index_in_group = block_index % blocks_per_group;
57 } else {
58 block_group = (block_index - 1) / blocks_per_group;
59 index_in_group = (block_index - 1) % blocks_per_group;
60 }
61
62 rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
63 if (rc != EOK) {
64 return rc;
65 }
66
67 bitmap_block = ext4_block_group_get_block_bitmap(bg_ref->block_group);
68
69 rc = block_get(&block, fs->device, bitmap_block, 0);
70 if (rc != EOK) {
71 return rc;
72 }
73
74 ext4_bitmap_free_bit(block->data, index_in_group);
75
76 block->dirty = true;
77 rc = block_put(block);
78 if (rc != EOK) {
79 return rc;
80 }
81
82 uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode);
83 ino_blocks -= block_size / EXT4_INODE_BLOCK_SIZE;
84 ext4_inode_set_blocks_count(fs->superblock, inode_ref->inode, ino_blocks);
85 inode_ref->dirty = true;
86
87 uint32_t free_blocks = ext4_block_group_get_free_blocks_count(bg_ref->block_group);
88 free_blocks++;
89 ext4_block_group_set_free_blocks_count(bg_ref->block_group, free_blocks);
90 bg_ref->dirty = true;
91
92 // TODO change free blocks count in superblock
93
94 rc = ext4_filesystem_put_block_group_ref(bg_ref);
95 if (rc != EOK) {
96 EXT4FS_DBG("error in saving bg_ref \%d", rc);
97 // TODO error
98 return rc;
99 }
100
101 return EOK;
102}
103
104
105static uint32_t ext4_bitmap_find_goal(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref)
106{
107 uint32_t goal = 0;
108
109 int rc;
110 uint64_t inode_size = ext4_inode_get_size(fs->superblock, inode_ref->inode);
111 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
112 uint32_t inode_block_count = inode_size / block_size;
113
114
115 if (inode_size % block_size != 0) {
116 inode_block_count++;
117 }
118
119 if (inode_block_count > 0) {
120 // TODO check retval
121// EXT4FS_DBG("has blocks");
122 ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, inode_block_count - 1, &goal);
123
124 // TODO
125 // If goal == 0 -> SPARSE file !!!
126 goal++;
127 return goal;
128 }
129
130// uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
131
132 // Identify block group of inode
133 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(fs->superblock);
134 uint32_t block_group = (inode_ref->index - 1) / inodes_per_group;
135 block_size = ext4_superblock_get_block_size(fs->superblock);
136
137 ext4_block_group_ref_t *bg_ref;
138 rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
139 if (rc != EOK) {
140 return 0;
141 }
142
143 uint32_t inode_table_first_block = ext4_block_group_get_inode_table_first_block(bg_ref->block_group);
144 uint16_t inode_table_item_size = ext4_superblock_get_inode_size(fs->superblock);
145 uint32_t inode_table_bytes = inodes_per_group * inode_table_item_size;
146 uint32_t inode_table_blocks = inode_table_bytes / block_size;
147
148 if (inode_table_bytes % block_size) {
149 inode_table_blocks++;
150 }
151
152 goal = inode_table_first_block + inode_table_blocks;
153
154 ext4_filesystem_put_block_group_ref(bg_ref);
155
156 return goal;
157}
158
159int ext4_bitmap_alloc_block(ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, uint32_t *fblock)
160{
161 int rc;
162 ext4_block_group_ref_t *bg_ref;
163 uint32_t bitmap_block;
164 block_t *block;
165 uint32_t rel_block_idx = 0;
166 uint32_t index_in_group;
167 uint32_t tmp;
168
169 uint32_t allocated_block = 0;
170
171 // Determine GOAL
172 uint32_t goal = ext4_bitmap_find_goal(fs, inode_ref);
173
174 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
175
176 //if (goal == 0) - unable to determine goal
177 if (goal == 0) {
178 // TODO
179 EXT4FS_DBG("ERRORR (goal == 0)");
180 }
181
182// EXT4FS_DBG("goal = \%u", goal);
183
184 uint32_t blocks_per_group = ext4_superblock_get_blocks_per_group(fs->superblock);
185 uint32_t first_block = ext4_superblock_get_first_data_block(fs->superblock);
186
187 uint32_t block_group;
188
189 // First block == 0 or 1
190 if (first_block == 0) {
191 block_group = goal / blocks_per_group;
192 index_in_group = goal % blocks_per_group;
193 } else {
194 block_group = (goal - 1) / blocks_per_group;
195 index_in_group = (goal - 1) % blocks_per_group;
196 }
197
198
199// EXT4FS_DBG("block_group = \%u, index_in_group = \%u", block_group, index_in_group);
200
201 rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
202 if (rc != EOK) {
203 return rc;
204 }
205
206 // Load bitmap
207 bitmap_block = ext4_block_group_get_block_bitmap(bg_ref->block_group);
208
209 rc = block_get(&block, fs->device, bitmap_block, 0);
210 if (rc != EOK) {
211 ext4_filesystem_put_block_group_ref(bg_ref);
212 return rc;
213 }
214
215// EXT4FS_DBG("bitmap loaded");
216
217 if (ext4_bitmap_is_free_bit(block->data, index_in_group)) {
218
219// EXT4FS_DBG("goal is free");
220
221 ext4_bitmap_set_bit(block->data, index_in_group);
222 block->dirty = true;
223 rc = block_put(block);
224 if (rc != EOK) {
225 // TODO error
226 EXT4FS_DBG("error in saving bitmap \%d", rc);
227 }
228
229 allocated_block = goal;
230 goto end;
231
232 }
233
234// EXT4FS_DBG("try 63 blocks after goal");
235 // Try to find free block near to goal
236 for (tmp = index_in_group + 1; (tmp < blocks_per_group) && (tmp < ((index_in_group + 63) & ~63)); ++tmp) {
237
238// EXT4FS_DBG("trying \%u", tmp);
239
240 if (ext4_bitmap_is_free_bit(block->data, tmp)) {
241
242// EXT4FS_DBG("block \%u is free -> allocate it", tmp);
243
244 ext4_bitmap_set_bit(block->data, tmp);
245 block->dirty = true;
246 rc = block_put(block);
247 if (rc != EOK) {
248 // TODO error
249 EXT4FS_DBG("error in saving bitmap \%d", rc);
250 }
251
252 if (first_block == 0) {
253 allocated_block = blocks_per_group * block_group + tmp;
254 } else {
255 allocated_block = blocks_per_group * block_group + tmp + 1;
256 }
257
258 goto end;
259 }
260 }
261
262// EXT4FS_DBG("try find free byte");
263
264 // Find free BYTE in bitmap
265 rc = ext4_bitmap_find_free_byte_and_set_bit(block->data, index_in_group, &rel_block_idx, block_size);
266 if (rc == EOK) {
267 block->dirty = true;
268 rc = block_put(block);
269 if (rc != EOK) {
270 // TODO error
271 EXT4FS_DBG("error in saving bitmap \%d", rc);
272 }
273
274 if (first_block == 0) {
275 allocated_block = blocks_per_group * block_group + rel_block_idx;
276 } else {
277 allocated_block = blocks_per_group * block_group + rel_block_idx + 1;
278 }
279
280 goto end;
281 }
282
283// EXT4FS_DBG("try find free bit");
284
285 // Find free bit in bitmap
286 rc = ext4_bitmap_find_free_bit_and_set(block->data, index_in_group, &rel_block_idx, block_size);
287 if (rc == EOK) {
288 block->dirty = true;
289 rc = block_put(block);
290 if (rc != EOK) {
291 // TODO error
292 EXT4FS_DBG("error in saving bitmap \%d", rc);
293 }
294
295 if (first_block == 0) {
296 allocated_block = blocks_per_group * block_group + rel_block_idx;
297 } else {
298 allocated_block = blocks_per_group * block_group + rel_block_idx + 1;
299 }
300
301 goto end;
302 }
303
304
305 // TODO Try other block groups
306 EXT4FS_DBG("try other block group");
307 return ENOSPC;
308
309end:
310
311 ;
312// EXT4FS_DBG("returning block \%u", allocated_block);
313
314 // TODO decrement superblock free blocks count
315 //uint32_t sb_free_blocks = ext4_superblock_get_free_blocks_count(sb);
316 //sb_free_blocks--;
317 //ext4_superblock_set_free_blocks_count(sb, sb_free_blocks);
318
319 uint64_t ino_blocks = ext4_inode_get_blocks_count(fs->superblock, inode_ref->inode);
320 ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
321 ext4_inode_set_blocks_count(fs->superblock, inode_ref->inode, ino_blocks);
322 inode_ref->dirty = true;
323
324 uint32_t bg_free_blocks = ext4_block_group_get_free_blocks_count(bg_ref->block_group);
325 bg_free_blocks--;
326 ext4_block_group_set_free_blocks_count(bg_ref->block_group, bg_free_blocks);
327 bg_ref->dirty = true;
328
329 ext4_filesystem_put_block_group_ref(bg_ref);
330
331// EXT4FS_DBG("block \%u allocated", blocks_per_group * block_group + rel_block_idx + 1);
332
333
334
335 *fblock = allocated_block;
336 return EOK;
337}
338
339
340/**
341 * @file libext4_balloc.c
342 * @brief TODO
343 */
344
345
346
347/**
348 * @}
349 */
Note: See TracBrowser for help on using the repository browser.