source: mainline/uspace/lib/ext4/libext4_ialloc.c@ d776329b

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since d776329b was 8a45707d, checked in by Martin Decky <martin@…>, 10 years ago

avoid the corner case where the last block group is the only block group with free blocks, but it has lower than average number of free inodes
(this bug rendered the rest of the free blocks on the file system unusable for new inodes)
  • Property mode set to 100644
File size: 9.1 KB
Line 
1/*
2 * Copyright (c) 2012 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 * @file libext4_ialloc.c
34 * @brief I-node (de)allocation operations.
35 */
36
37#include <errno.h>
38#include <time.h>
39#include "libext4.h"
40
41
42/** Convert i-node number to relative index in block group.
43 *
44 * @param sb Superblock
45 * @param inode I-node number to be converted
46 *
47 * @return Index of the i-node in the block group
48 *
49 */
50static uint32_t ext4_ialloc_inode2index_in_group(ext4_superblock_t *sb,
51 uint32_t inode)
52{
53 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
54 return (inode - 1) % inodes_per_group;
55}
56
57/** Convert relative index of i-node to absolute i-node number.
58 *
59 * @param sb Superblock
60 * @param inode Index to be converted
61 *
62 * @return Absolute number of the i-node
63 *
64 */
65static uint32_t ext4_ialloc_index_in_group2inode(ext4_superblock_t *sb,
66 uint32_t index, uint32_t bgid)
67{
68 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
69 return bgid * inodes_per_group + (index + 1);
70}
71
72/** Compute block group number from the i-node number.
73 *
74 * @param sb Superblock
75 * @param inode I-node number to be found the block group for
76 *
77 * @return Block group number computed from i-node number
78 *
79 */
80static uint32_t ext4_ialloc_get_bgid_of_inode(ext4_superblock_t *sb,
81 uint32_t inode)
82{
83 uint32_t inodes_per_group = ext4_superblock_get_inodes_per_group(sb);
84 return (inode - 1) / inodes_per_group;
85}
86
87
88/** Free i-node number and modify filesystem data structers.
89 *
90 * @param fs Filesystem, where the i-node is located
91 * @param index Index of i-node to be release
92 * @param is_dir Flag us for information whether i-node is directory or not
93 *
94 */
95int ext4_ialloc_free_inode(ext4_filesystem_t *fs, uint32_t index, bool is_dir)
96{
97 ext4_superblock_t *sb = fs->superblock;
98
99 /* Compute index of block group and load it */
100 uint32_t block_group = ext4_ialloc_get_bgid_of_inode(sb, index);
101
102 ext4_block_group_ref_t *bg_ref;
103 int rc = ext4_filesystem_get_block_group_ref(fs, block_group, &bg_ref);
104 if (rc != EOK)
105 return rc;
106
107 /* Load i-node bitmap */
108 uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap(
109 bg_ref->block_group, sb);
110 block_t *bitmap_block;
111 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr,
112 BLOCK_FLAGS_NONE);
113 if (rc != EOK)
114 return rc;
115
116 /* Free i-node in the bitmap */
117 uint32_t index_in_group = ext4_ialloc_inode2index_in_group(sb, index);
118 ext4_bitmap_free_bit(bitmap_block->data, index_in_group);
119 bitmap_block->dirty = true;
120
121 /* Put back the block with bitmap */
122 rc = block_put(bitmap_block);
123 if (rc != EOK) {
124 /* Error in saving bitmap */
125 ext4_filesystem_put_block_group_ref(bg_ref);
126 return rc;
127 }
128
129 /* If released i-node is a directory, decrement used directories count */
130 if (is_dir) {
131 uint32_t bg_used_dirs = ext4_block_group_get_used_dirs_count(
132 bg_ref->block_group, sb);
133 bg_used_dirs--;
134 ext4_block_group_set_used_dirs_count(bg_ref->block_group, sb,
135 bg_used_dirs);
136 }
137
138 /* Update block group free inodes count */
139 uint32_t free_inodes = ext4_block_group_get_free_inodes_count(
140 bg_ref->block_group, sb);
141 free_inodes++;
142 ext4_block_group_set_free_inodes_count(bg_ref->block_group, sb,
143 free_inodes);
144
145 bg_ref->dirty = true;
146
147 /* Put back the modified block group */
148 rc = ext4_filesystem_put_block_group_ref(bg_ref);
149 if (rc != EOK)
150 return rc;
151
152 /* Update superblock free inodes count */
153 uint32_t sb_free_inodes =
154 ext4_superblock_get_free_inodes_count(sb);
155 sb_free_inodes++;
156 ext4_superblock_set_free_inodes_count(sb, sb_free_inodes);
157
158 return EOK;
159}
160
161/** I-node allocation algorithm.
162 *
163 * This is more simple algorithm, than Orlov allocator used
164 * in the Linux kernel.
165 *
166 * @param fs Filesystem to allocate i-node on
167 * @param index Output value - allocated i-node number
168 * @param is_dir Flag if allocated i-node will be file or directory
169 *
170 * @return Error code
171 *
172 */
173int ext4_ialloc_alloc_inode(ext4_filesystem_t *fs, uint32_t *index, bool is_dir)
174{
175 ext4_superblock_t *sb = fs->superblock;
176
177 uint32_t bgid = 0;
178 uint32_t bg_count = ext4_superblock_get_block_group_count(sb);
179 uint32_t sb_free_inodes = ext4_superblock_get_free_inodes_count(sb);
180 uint32_t avg_free_inodes = sb_free_inodes / bg_count;
181
182 /* Try to find free i-node in all block groups */
183 while (bgid < bg_count) {
184 /* Load block group to check */
185 ext4_block_group_ref_t *bg_ref;
186 int rc = ext4_filesystem_get_block_group_ref(fs, bgid, &bg_ref);
187 if (rc != EOK)
188 return rc;
189
190 ext4_block_group_t *bg = bg_ref->block_group;
191
192 /* Read necessary values for algorithm */
193 uint32_t free_blocks = ext4_block_group_get_free_blocks_count(bg, sb);
194 uint32_t free_inodes = ext4_block_group_get_free_inodes_count(bg, sb);
195 uint32_t used_dirs = ext4_block_group_get_used_dirs_count(bg, sb);
196
197 /*
198 * Check if this block group is a good candidate
199 * for allocation.
200 *
201 * The criterion is based on the average number
202 * of free inodes, unless we examine the last block
203 * group. In that case the last block group might
204 * have less than the average number of free inodes,
205 * but it still needs to be taken as a candidate
206 * because the previous block groups have zero free
207 * blocks.
208 */
209 if (((free_inodes >= avg_free_inodes) || (bgid == bg_count - 1)) &&
210 (free_blocks > 0)) {
211 /* Load block with bitmap */
212 uint32_t bitmap_block_addr = ext4_block_group_get_inode_bitmap(
213 bg_ref->block_group, sb);
214
215 block_t *bitmap_block;
216 rc = block_get(&bitmap_block, fs->device, bitmap_block_addr,
217 BLOCK_FLAGS_NONE);
218 if (rc != EOK) {
219 ext4_filesystem_put_block_group_ref(bg_ref);
220 return rc;
221 }
222
223 /* Try to allocate i-node in the bitmap */
224 uint32_t inodes_in_group = ext4_superblock_get_inodes_in_group(sb, bgid);
225 uint32_t index_in_group;
226 rc = ext4_bitmap_find_free_bit_and_set(bitmap_block->data,
227 0, &index_in_group, inodes_in_group);
228
229 /* Block group has not any free i-node */
230 if (rc == ENOSPC) {
231 rc = block_put(bitmap_block);
232 if (rc != EOK) {
233 ext4_filesystem_put_block_group_ref(bg_ref);
234 return rc;
235 }
236
237 rc = ext4_filesystem_put_block_group_ref(bg_ref);
238 if (rc != EOK)
239 return rc;
240
241 bgid++;
242 continue;
243 }
244
245 /* Free i-node found, save the bitmap */
246 bitmap_block->dirty = true;
247
248 rc = block_put(bitmap_block);
249 if (rc != EOK) {
250 ext4_filesystem_put_block_group_ref(bg_ref);
251 return rc;
252 }
253
254 /* Modify filesystem counters */
255 free_inodes--;
256 ext4_block_group_set_free_inodes_count(bg, sb, free_inodes);
257
258 /* Increment used directories counter */
259 if (is_dir) {
260 used_dirs++;
261 ext4_block_group_set_used_dirs_count(bg, sb, used_dirs);
262 }
263
264 /* Decrease unused inodes count */
265 if (ext4_block_group_has_flag(bg,
266 EXT4_BLOCK_GROUP_ITABLE_ZEROED)) {
267 uint32_t unused =
268 ext4_block_group_get_itable_unused(bg, sb);
269
270 uint32_t inodes_in_group =
271 ext4_superblock_get_inodes_in_group(sb, bgid);
272
273 uint32_t free = inodes_in_group - unused;
274
275 if (index_in_group >= free) {
276 unused = inodes_in_group - (index_in_group + 1);
277 ext4_block_group_set_itable_unused(bg, sb, unused);
278 }
279 }
280
281 /* Save modified block group */
282 bg_ref->dirty = true;
283
284 rc = ext4_filesystem_put_block_group_ref(bg_ref);
285 if (rc != EOK)
286 return rc;
287
288 /* Update superblock */
289 sb_free_inodes--;
290 ext4_superblock_set_free_inodes_count(sb, sb_free_inodes);
291
292 /* Compute the absolute i-nodex number */
293 *index = ext4_ialloc_index_in_group2inode(sb, index_in_group, bgid);
294
295 return EOK;
296 }
297
298 /* Block group not modified, put it and jump to the next block group */
299 rc = ext4_filesystem_put_block_group_ref(bg_ref);
300 if (rc != EOK)
301 return rc;
302
303 ++bgid;
304 }
305
306 return ENOSPC;
307}
308
309/**
310 * @}
311 */
Note: See TracBrowser for help on using the repository browser.