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

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

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