1/*
2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
3 *
4 *
5 * HelenOS:
6 * Copyright (c) 2012 Martin Sucha
7 * Copyright (c) 2012 Frantisek Princ
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * - Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * - Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * - The name of the author may not be used to endorse or promote products
20 * derived from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34/** @addtogroup lwext4
35 * @{
36 */
37/**
38 * @file ext4_ialloc.c
39 * @brief Inode allocation procedures.
40 */
41
42#include <ext4_config.h>
43#include <ext4_types.h>
44#include <ext4_misc.h>
45#include <ext4_errno.h>
46#include <ext4_debug.h>
47
48#include <ext4_trans.h>
49#include <ext4_ialloc.h>
50#include <ext4_super.h>
51#include <ext4_crc32.h>
52#include <ext4_fs.h>
53#include <ext4_blockdev.h>
54#include <ext4_block_group.h>
55#include <ext4_bitmap.h>
56
57/**@brief Convert i-node number to relative index in block group.
58 * @param sb Superblock
59 * @param inode I-node number to be converted
60 * @return Index of the i-node in the block group
61 */
62static uint32_t ext4_ialloc_inode_to_bgidx(struct ext4_sblock *sb,
63 uint32_t inode)
64{
65 uint32_t inodes_per_group = ext4_get32(sb, inodes_per_group);
66 return (inode - 1) % inodes_per_group;
67}
68
69/**@brief Convert relative index of i-node to absolute i-node number.
70 * @param sb Superblock
71 * @param index Index to be converted
72 * @return Absolute number of the i-node
73 *
74 */
75static uint32_t ext4_ialloc_bgidx_to_inode(struct ext4_sblock *sb,
76 uint32_t index, uint32_t bgid)
77{
78 uint32_t inodes_per_group = ext4_get32(sb, inodes_per_group);
79 return bgid * inodes_per_group + (index + 1);
80}
81
82/**@brief Compute block group number from the i-node number.
83 * @param sb Superblock
84 * @param inode I-node number to be found the block group for
85 * @return Block group number computed from i-node number
86 */
87static uint32_t ext4_ialloc_get_bgid_of_inode(struct ext4_sblock *sb,
88 uint32_t inode)
89{
90 uint32_t inodes_per_group = ext4_get32(sb, inodes_per_group);
91 return (inode - 1) / inodes_per_group;
92}
93
94#if CONFIG_META_CSUM_ENABLE
95static uint32_t ext4_ialloc_bitmap_csum(struct ext4_sblock *sb, void *bitmap)
96{
97 uint32_t csum = 0;
98 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) {
99 uint32_t inodes_per_group =
100 ext4_get32(sb, inodes_per_group);
101
102 /* First calculate crc32 checksum against fs uuid */
103 csum = ext4_crc32c(EXT4_CRC32_INIT, buf: sb->uuid, size: sizeof(sb->uuid));
104 /* Then calculate crc32 checksum against inode bitmap */
105 csum = ext4_crc32c(crc: csum, buf: bitmap, size: (inodes_per_group + 7) / 8);
106 }
107 return csum;
108}
109#else
110#define ext4_ialloc_bitmap_csum(...) 0
111#endif
112
113void ext4_ialloc_set_bitmap_csum(struct ext4_sblock *sb, struct ext4_bgroup *bg,
114 void *bitmap __unused)
115{
116 int desc_size = ext4_sb_get_desc_size(s: sb);
117 uint32_t csum = ext4_ialloc_bitmap_csum(sb, bitmap);
118 uint16_t lo_csum = to_le16(csum & 0xFFFF),
119 hi_csum = to_le16(csum >> 16);
120
121 if (!ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM))
122 return;
123
124 /* See if we need to assign a 32bit checksum */
125 bg->inode_bitmap_csum_lo = lo_csum;
126 if (desc_size == EXT4_MAX_BLOCK_GROUP_DESCRIPTOR_SIZE)
127 bg->inode_bitmap_csum_hi = hi_csum;
128
129}
130
131#if CONFIG_META_CSUM_ENABLE
132static bool
133ext4_ialloc_verify_bitmap_csum(struct ext4_sblock *sb, struct ext4_bgroup *bg,
134 void *bitmap __unused)
135{
136
137 int desc_size = ext4_sb_get_desc_size(s: sb);
138 uint32_t csum = ext4_ialloc_bitmap_csum(sb, bitmap);
139 uint16_t lo_csum = to_le16(csum & 0xFFFF),
140 hi_csum = to_le16(csum >> 16);
141
142 if (!ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM))
143 return true;
144
145 if (bg->inode_bitmap_csum_lo != lo_csum)
146 return false;
147
148 if (desc_size == EXT4_MAX_BLOCK_GROUP_DESCRIPTOR_SIZE)
149 if (bg->inode_bitmap_csum_hi != hi_csum)
150 return false;
151
152 return true;
153}
154#else
155#define ext4_ialloc_verify_bitmap_csum(...) true
156#endif
157
158int ext4_ialloc_free_inode(struct ext4_fs *fs, uint32_t index, bool is_dir)
159{
160 struct ext4_sblock *sb = &fs->sb;
161
162 /* Compute index of block group and load it */
163 uint32_t block_group = ext4_ialloc_get_bgid_of_inode(sb, inode: index);
164
165 struct ext4_block_group_ref bg_ref;
166 int rc = ext4_fs_get_block_group_ref(fs, bgid: block_group, ref: &bg_ref);
167 if (rc != EOK)
168 return rc;
169
170 struct ext4_bgroup *bg = bg_ref.block_group;
171
172 /* Load i-node bitmap */
173 ext4_fsblk_t bitmap_block_addr =
174 ext4_bg_get_inode_bitmap(bg, s: sb);
175
176 struct ext4_block b;
177 rc = ext4_trans_block_get(bdev: fs->bdev, b: &b, lba: bitmap_block_addr);
178 if (rc != EOK)
179 return rc;
180
181 if (!ext4_ialloc_verify_bitmap_csum(sb, bg, bitmap: b.data)) {
182 ext4_dbg(DEBUG_IALLOC,
183 DBG_WARN "Bitmap checksum failed."
184 "Group: %" PRIu32"\n",
185 bg_ref.index);
186 }
187
188 /* Free i-node in the bitmap */
189 uint32_t index_in_group = ext4_ialloc_inode_to_bgidx(sb, inode: index);
190 ext4_bmap_bit_clr(bmap: b.data, bit: index_in_group);
191 ext4_ialloc_set_bitmap_csum(sb, bg, bitmap: b.data);
192 ext4_trans_set_block_dirty(buf: b.buf);
193
194 /* Put back the block with bitmap */
195 rc = ext4_block_set(bdev: fs->bdev, b: &b);
196 if (rc != EOK) {
197 /* Error in saving bitmap */
198 ext4_fs_put_block_group_ref(ref: &bg_ref);
199 return rc;
200 }
201
202 /* If released i-node is a directory, decrement used directories count
203 */
204 if (is_dir) {
205 uint32_t bg_used_dirs = ext4_bg_get_used_dirs_count(bg, s: sb);
206 bg_used_dirs--;
207 ext4_bg_set_used_dirs_count(bg, s: sb, cnt: bg_used_dirs);
208 }
209
210 /* Update block group free inodes count */
211 uint32_t free_inodes = ext4_bg_get_free_inodes_count(bg, s: sb);
212 free_inodes++;
213 ext4_bg_set_free_inodes_count(bg, s: sb, cnt: free_inodes);
214
215 bg_ref.dirty = true;
216
217 /* Put back the modified block group */
218 rc = ext4_fs_put_block_group_ref(ref: &bg_ref);
219 if (rc != EOK)
220 return rc;
221
222 /* Update superblock free inodes count */
223 ext4_set32(sb, free_inodes_count,
224 ext4_get32(sb, free_inodes_count) + 1);
225
226 return EOK;
227}
228
229int ext4_ialloc_alloc_inode(struct ext4_fs *fs, uint32_t *idx, bool is_dir)
230{
231 struct ext4_sblock *sb = &fs->sb;
232
233 uint32_t bgid = fs->last_inode_bg_id;
234 uint32_t bg_count = ext4_block_group_cnt(s: sb);
235 uint32_t sb_free_inodes = ext4_get32(sb, free_inodes_count);
236 bool rewind = false;
237
238 /* Try to find free i-node in all block groups */
239 while (bgid <= bg_count) {
240
241 if (bgid == bg_count) {
242 if (rewind)
243 break;
244 bg_count = fs->last_inode_bg_id;
245 bgid = 0;
246 rewind = true;
247 continue;
248 }
249
250 /* Load block group to check */
251 struct ext4_block_group_ref bg_ref;
252 int rc = ext4_fs_get_block_group_ref(fs, bgid, ref: &bg_ref);
253 if (rc != EOK)
254 return rc;
255
256 struct ext4_bgroup *bg = bg_ref.block_group;
257
258 /* Read necessary values for algorithm */
259 uint32_t free_inodes = ext4_bg_get_free_inodes_count(bg, s: sb);
260 uint32_t used_dirs = ext4_bg_get_used_dirs_count(bg, s: sb);
261
262 /* Check if this block group is good candidate for allocation */
263 if (free_inodes > 0) {
264 /* Load block with bitmap */
265 ext4_fsblk_t bmp_blk_add = ext4_bg_get_inode_bitmap(bg, s: sb);
266
267 struct ext4_block b;
268 rc = ext4_trans_block_get(bdev: fs->bdev, b: &b, lba: bmp_blk_add);
269 if (rc != EOK) {
270 ext4_fs_put_block_group_ref(ref: &bg_ref);
271 return rc;
272 }
273
274 if (!ext4_ialloc_verify_bitmap_csum(sb, bg, bitmap: b.data)) {
275 ext4_dbg(DEBUG_IALLOC,
276 DBG_WARN "Bitmap checksum failed."
277 "Group: %" PRIu32"\n",
278 bg_ref.index);
279 }
280
281 /* Try to allocate i-node in the bitmap */
282 uint32_t inodes_in_bg;
283 uint32_t idx_in_bg;
284
285 inodes_in_bg = ext4_inodes_in_group_cnt(s: sb, bgid);
286 rc = ext4_bmap_bit_find_clr(bmap: b.data, sbit: 0, ebit: inodes_in_bg,
287 bit_id: &idx_in_bg);
288 /* Block group has not any free i-node */
289 if (rc == ENOSPC) {
290 rc = ext4_block_set(bdev: fs->bdev, b: &b);
291 if (rc != EOK) {
292 ext4_fs_put_block_group_ref(ref: &bg_ref);
293 return rc;
294 }
295
296 rc = ext4_fs_put_block_group_ref(ref: &bg_ref);
297 if (rc != EOK)
298 return rc;
299
300 continue;
301 }
302
303 ext4_bmap_bit_set(bmap: b.data, bit: idx_in_bg);
304
305 /* Free i-node found, save the bitmap */
306 ext4_ialloc_set_bitmap_csum(sb,bg,
307 bitmap: b.data);
308 ext4_trans_set_block_dirty(buf: b.buf);
309
310 ext4_block_set(bdev: fs->bdev, b: &b);
311 if (rc != EOK) {
312 ext4_fs_put_block_group_ref(ref: &bg_ref);
313 return rc;
314 }
315
316 /* Modify filesystem counters */
317 free_inodes--;
318 ext4_bg_set_free_inodes_count(bg, s: sb, cnt: free_inodes);
319
320 /* Increment used directories counter */
321 if (is_dir) {
322 used_dirs++;
323 ext4_bg_set_used_dirs_count(bg, s: sb, cnt: used_dirs);
324 }
325
326 /* Decrease unused inodes count */
327 uint32_t unused =
328 ext4_bg_get_itable_unused(bg, s: sb);
329
330 uint32_t free = inodes_in_bg - unused;
331
332 if (idx_in_bg >= free) {
333 unused = inodes_in_bg - (idx_in_bg + 1);
334 ext4_bg_set_itable_unused(bg, s: sb, cnt: unused);
335 }
336
337 /* Save modified block group */
338 bg_ref.dirty = true;
339
340 rc = ext4_fs_put_block_group_ref(ref: &bg_ref);
341 if (rc != EOK)
342 return rc;
343
344 /* Update superblock */
345 sb_free_inodes--;
346 ext4_set32(sb, free_inodes_count, sb_free_inodes);
347
348 /* Compute the absolute i-nodex number */
349 *idx = ext4_ialloc_bgidx_to_inode(sb, index: idx_in_bg, bgid);
350
351 fs->last_inode_bg_id = bgid;
352
353 return EOK;
354 }
355
356 /* Block group not modified, put it and jump to the next block
357 * group */
358 ext4_fs_put_block_group_ref(ref: &bg_ref);
359 if (rc != EOK)
360 return rc;
361
362 ++bgid;
363 }
364
365 return ENOSPC;
366}
367
368/**
369 * @}
370 */
371