d0d42ad18e83dcb82830176c0ed78525d391b5c2
[lwext4.git] / lwext4 / ext4_balloc.c
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_balloc.c
39  * @brief Physical block allocator.
40  */
41
42 #include <ext4_config.h>
43 #include <ext4_balloc.h>
44 #include <ext4_super.h>
45 #include <ext4_block_group.h>
46 #include <ext4_fs.h>
47 #include <ext4_bitmap.h>
48 #include <ext4_inode.h>
49
50
51 /**@brief Compute number of block group from block address.
52  * @param sb         Superblock pointer.
53  * @param baddr Absolute address of block.
54  * @return Block group index
55  */
56 static uint32_t ext4_balloc_get_bgid_of_block(struct ext4_sblock *s,
57     uint32_t baddr)
58 {
59     if(ext4_get32(s, first_data_block))
60         baddr--;
61
62     return baddr / ext4_get32(s, blocks_per_group);
63 }
64
65
66 uint32_t ext4_balloc_get_first_data_block_in_group(struct ext4_sblock *s,
67     struct ext4_block_group_ref * bg_ref)
68 {
69     uint32_t block_group_count = ext4_block_group_cnt(s);
70     uint32_t inode_table_first_block =
71             ext4_bg_get_inode_table_first_block(bg_ref->block_group, s);
72     uint32_t block_size  = ext4_sb_get_block_size(s);
73
74     uint16_t inode_size = ext4_get16(s, inode_size);
75     uint32_t inodes_per_group = ext4_get32(s, inodes_per_group);
76
77     uint32_t inode_table_bytes;
78
79
80     if (bg_ref->index < block_group_count - 1) {
81         inode_table_bytes = inodes_per_group * inode_size;
82     } else {
83         /* Last block group could be smaller */
84         uint32_t inodes_count_total = ext4_get32(s, inodes_count);
85         inode_table_bytes =
86                 (inodes_count_total - ((block_group_count - 1) *
87                         inodes_per_group)) * inode_size;
88     }
89
90     uint32_t inode_table_blocks = inode_table_bytes / block_size;
91
92     if (inode_table_bytes % block_size)
93         inode_table_blocks++;
94
95     return inode_table_first_block + inode_table_blocks;
96 }
97
98 int ext4_balloc_free_block(struct ext4_inode_ref *inode_ref, uint32_t baddr)
99 {
100     struct ext4_fs *fs = inode_ref->fs;
101     struct ext4_sblock *sb = &fs->sb;
102
103
104     uint32_t block_group    = ext4_balloc_get_bgid_of_block(sb, baddr);
105     uint32_t index_in_group = ext4_fs_baddr2_index_in_group(sb, baddr);
106
107     /* Load block group reference */
108     struct ext4_block_group_ref bg_ref;
109     int rc = ext4_fs_get_block_group_ref(fs, block_group, &bg_ref);
110     if (rc != EOK)
111         return rc;
112
113     /* Load block with bitmap */
114     uint32_t bitmap_block_addr =
115             ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
116
117     struct ext4_block bitmap_block;
118
119     rc = ext4_block_get(fs->bdev, &bitmap_block, bitmap_block_addr);
120     if (rc != EOK){
121         ext4_fs_put_block_group_ref(&bg_ref);
122         return rc;
123     }
124
125     /* Modify bitmap */
126     ext4_bmap_bit_clr(bitmap_block.data, index_in_group);
127     bitmap_block.dirty = true;
128
129     /* Release block with bitmap */
130     rc = ext4_block_set(fs->bdev, &bitmap_block);
131     if (rc != EOK) {
132         /* Error in saving bitmap */
133         ext4_fs_put_block_group_ref(&bg_ref);
134         return rc;
135     }
136
137     uint32_t block_size = ext4_sb_get_block_size(sb);
138
139     /* Update superblock free blocks count */
140     uint64_t sb_free_blocks =
141             ext4_sb_get_free_blocks_cnt(sb);
142     sb_free_blocks++;
143     ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
144
145     /* Update inode blocks count */
146     uint64_t ino_blocks =
147             ext4_inode_get_blocks_count(sb, inode_ref->inode);
148     ino_blocks -= block_size / EXT4_INODE_BLOCK_SIZE;
149     ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
150     inode_ref->dirty = true;
151
152     /* Update block group free blocks count */
153     uint32_t free_blocks =
154             ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
155     free_blocks++;
156     ext4_bg_set_free_blocks_count(bg_ref.block_group,
157         sb, free_blocks);
158
159     bg_ref.dirty = true;
160
161     /* Release block group reference */
162     return ext4_fs_put_block_group_ref(&bg_ref);
163 }
164
165 int ext4_balloc_free_blocks(struct ext4_inode_ref *inode_ref, uint32_t first,
166     uint32_t count)
167 {
168     struct ext4_fs *fs = inode_ref->fs;
169     struct ext4_sblock *sb = &fs->sb;
170
171     /* Compute indexes */
172     uint32_t block_group_first =
173             ext4_balloc_get_bgid_of_block(sb, first);
174     uint32_t block_group_last =
175             ext4_balloc_get_bgid_of_block(sb, first + count - 1);
176
177     ext4_assert(block_group_first == block_group_last);
178
179     /* Load block group reference */
180     struct ext4_block_group_ref bg_ref;
181     int rc = ext4_fs_get_block_group_ref(fs, block_group_first, &bg_ref);
182     if (rc != EOK)
183         return rc;
184
185     uint32_t index_in_group_first =
186             ext4_fs_baddr2_index_in_group(sb, first);
187
188     /* Load block with bitmap */
189     uint32_t bitmap_block_addr =
190             ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
191
192     struct ext4_block bitmap_block;
193
194     rc = ext4_block_get(fs->bdev, &bitmap_block, bitmap_block_addr);
195     if (rc != EOK){
196         ext4_fs_put_block_group_ref(&bg_ref);
197         return rc;
198     }
199
200     /* Modify bitmap */
201     ext4_bmap_bits_free(bitmap_block.data, index_in_group_first, count);
202     bitmap_block.dirty = true;
203
204     /* Release block with bitmap */
205     rc = ext4_block_set(fs->bdev, &bitmap_block);
206     if (rc != EOK) {
207         ext4_fs_put_block_group_ref(&bg_ref);
208         return rc;
209     }
210
211     uint32_t block_size = ext4_sb_get_block_size(sb);
212
213     /* Update superblock free blocks count */
214     uint64_t sb_free_blocks =
215             ext4_sb_get_free_blocks_cnt(sb);
216     sb_free_blocks += count;
217     ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
218
219     /* Update inode blocks count */
220     uint64_t ino_blocks =
221             ext4_inode_get_blocks_count(sb, inode_ref->inode);
222     ino_blocks -= count * (block_size / EXT4_INODE_BLOCK_SIZE);
223     ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
224     inode_ref->dirty = true;
225
226     /* Update block group free blocks count */
227     uint32_t free_blocks =
228             ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
229     free_blocks += count;
230     ext4_bg_set_free_blocks_count(bg_ref.block_group,
231         sb, free_blocks);
232     bg_ref.dirty = true;
233
234     /* Release block group reference */
235     return ext4_fs_put_block_group_ref(&bg_ref);
236 }
237
238
239 /**@brief Compute 'goal' for allocation algorithm.
240  * @param inode_ref Reference to inode, to allocate block for
241  * @param goal
242  * @return error code
243  */
244 static int ext4_balloc_find_goal(struct ext4_inode_ref *inode_ref, uint32_t *goal)
245 {
246     struct ext4_sblock *sb = &inode_ref->fs->sb;
247     *goal = 0;
248
249     uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
250     uint32_t block_size = ext4_sb_get_block_size(sb);
251     uint32_t inode_block_count = inode_size / block_size;
252
253     if (inode_size % block_size != 0)
254         inode_block_count++;
255
256     /* If inode has some blocks, get last block address + 1 */
257     if (inode_block_count > 0) {
258         int rc = ext4_fs_get_inode_data_block_index(inode_ref,
259                 inode_block_count - 1, goal);
260         if (rc != EOK)
261             return rc;
262
263         if (*goal != 0) {
264             (*goal)++;
265             return rc;
266         }
267
268         /* If goal == 0, sparse file -> continue */
269     }
270
271     /* Identify block group of inode */
272
273     uint32_t inodes_per_group = ext4_get32(sb, inodes_per_group);
274     uint32_t block_group = (inode_ref->index - 1) / inodes_per_group;
275     block_size = ext4_sb_get_block_size(sb);
276
277     /* Load block group reference */
278     struct ext4_block_group_ref bg_ref;
279     int rc = ext4_fs_get_block_group_ref(inode_ref->fs,
280             block_group, &bg_ref);
281     if (rc != EOK)
282         return rc;
283
284     /* Compute indexes */
285     uint32_t block_group_count = ext4_block_group_cnt(sb);
286     uint32_t inode_table_first_block =
287             ext4_bg_get_inode_table_first_block(bg_ref.block_group, sb);
288     uint16_t inode_table_item_size = ext4_get16(sb, inode_size);
289     uint32_t inode_table_bytes;
290
291     /* Check for last block group */
292     if (block_group < block_group_count - 1) {
293         inode_table_bytes = inodes_per_group * inode_table_item_size;
294     } else {
295         /* Last block group could be smaller */
296         uint32_t inodes_count_total = ext4_get32(sb, inodes_count);
297
298         inode_table_bytes =
299                 (inodes_count_total - ((block_group_count - 1) *
300                         inodes_per_group)) * inode_table_item_size;
301     }
302
303     uint32_t inode_table_blocks = inode_table_bytes / block_size;
304
305     if (inode_table_bytes % block_size)
306         inode_table_blocks++;
307
308     *goal = inode_table_first_block + inode_table_blocks;
309
310     return  ext4_fs_put_block_group_ref(&bg_ref);
311 }
312
313
314 int ext4_balloc_alloc_block(struct ext4_inode_ref *inode_ref,
315     uint32_t *fblock)
316 {
317     uint32_t allocated_block = 0;
318     uint32_t bitmap_block_addr;
319     uint32_t rel_block_idx = 0;
320     uint32_t free_blocks;
321     uint32_t goal;
322     struct ext4_block bitmap_block;
323
324     int rc = ext4_balloc_find_goal(inode_ref, &goal);
325     if (rc != EOK) {
326         /* no goal found => partition is full */
327         return rc;
328     }
329
330     struct ext4_sblock *sb = &inode_ref->fs->sb;
331
332     /* Load block group number for goal and relative index */
333     uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, goal);
334     uint32_t index_in_group =
335             ext4_fs_baddr2_index_in_group(sb, goal);
336
337     /* Load block group reference */
338     struct ext4_block_group_ref bg_ref;
339     rc = ext4_fs_get_block_group_ref(inode_ref->fs,
340             block_group, &bg_ref);
341     if (rc != EOK)
342         return rc;
343
344     free_blocks =
345             ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
346     if (free_blocks == 0) {
347         /* This group has no free blocks */
348         goto goal_failed;
349     }
350
351     /* Compute indexes */
352     uint32_t first_in_group =
353             ext4_balloc_get_first_data_block_in_group(sb, &bg_ref);
354
355     uint32_t first_in_group_index =
356             ext4_fs_baddr2_index_in_group(sb, first_in_group);
357
358     if (index_in_group < first_in_group_index)
359         index_in_group = first_in_group_index;
360
361     /* Load block with bitmap */
362     bitmap_block_addr =
363             ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
364
365     rc = ext4_block_get(inode_ref->fs->bdev, &bitmap_block,
366             bitmap_block_addr);
367     if (rc != EOK) {
368         ext4_fs_put_block_group_ref(&bg_ref);
369         return rc;
370     }
371
372     /* Check if goal is free */
373     if (ext4_bmap_is_bit_clr(bitmap_block.data, index_in_group)) {
374         ext4_bmap_bit_set(bitmap_block.data, index_in_group);
375         bitmap_block.dirty = true;
376         rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
377         if (rc != EOK) {
378             ext4_fs_put_block_group_ref(&bg_ref);
379             return rc;
380         }
381
382         allocated_block =
383                 ext4_fs_index_in_group2_baddr(sb, index_in_group,
384                         block_group);
385
386         goto success;
387     }
388
389     uint32_t blocks_in_group =
390             ext4_blocks_in_group_cnt(sb, block_group);
391
392     uint32_t end_idx = (index_in_group + 63) & ~63;
393     if (end_idx > blocks_in_group)
394         end_idx = blocks_in_group;
395
396     /* Try to find free block near to goal */
397     uint32_t tmp_idx;
398     for (tmp_idx = index_in_group + 1; tmp_idx < end_idx;
399             ++tmp_idx) {
400         if (ext4_bmap_is_bit_clr(bitmap_block.data, tmp_idx)) {
401             ext4_bmap_bit_set(bitmap_block.data, tmp_idx);
402
403             bitmap_block.dirty = true;
404             rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
405             if (rc != EOK)
406                 return rc;
407
408             allocated_block =
409                     ext4_fs_index_in_group2_baddr(sb, tmp_idx,
410                             block_group);
411
412             goto success;
413         }
414     }
415
416
417
418     /* Find free bit in bitmap */
419     rc = ext4_bmap_bit_find_clr(bitmap_block.data,
420             index_in_group, blocks_in_group, &rel_block_idx);
421     if (rc == EOK) {
422         ext4_bmap_bit_set(bitmap_block.data, rel_block_idx);
423         bitmap_block.dirty = true;
424         rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
425         if (rc != EOK)
426             return rc;
427
428         allocated_block =
429                 ext4_fs_index_in_group2_baddr(sb, rel_block_idx,
430                         block_group);
431
432         goto success;
433     }
434
435     /* No free block found yet */
436     rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
437     if(rc != EOK){
438         ext4_fs_put_block_group_ref(&bg_ref);
439         return rc;
440     }
441
442 goal_failed:
443
444     rc = ext4_fs_put_block_group_ref(&bg_ref);
445     if(rc != EOK)
446         return rc;
447
448
449     /* Try other block groups */
450     uint32_t block_group_count = ext4_block_group_cnt(sb);
451
452     uint32_t bgid = (block_group + 1) % block_group_count;
453     uint32_t count = block_group_count;
454
455     while (count > 0) {
456         rc = ext4_fs_get_block_group_ref(inode_ref->fs, bgid,
457                 &bg_ref);
458         if (rc != EOK)
459             return rc;
460
461         free_blocks =
462                 ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
463         if (free_blocks == 0) {
464             /* This group has no free blocks */
465             goto next_group;
466         }
467
468         /* Load block with bitmap */
469         bitmap_block_addr =
470                 ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
471
472         rc = ext4_block_get(inode_ref->fs->bdev, &bitmap_block,
473                 bitmap_block_addr);
474
475         if (rc != EOK) {
476             ext4_fs_put_block_group_ref(&bg_ref);
477             return rc;
478         }
479
480         /* Compute indexes */
481         first_in_group =
482                 ext4_balloc_get_first_data_block_in_group(sb, &bg_ref);
483         index_in_group =
484                 ext4_fs_baddr2_index_in_group(sb, first_in_group);
485         blocks_in_group = ext4_blocks_in_group_cnt(sb, bgid);
486
487         first_in_group_index =
488                 ext4_fs_baddr2_index_in_group(sb, first_in_group);
489
490         if (index_in_group < first_in_group_index)
491             index_in_group = first_in_group_index;
492
493
494         rc = ext4_bmap_bit_find_clr(bitmap_block.data,
495                 index_in_group, blocks_in_group, &rel_block_idx);
496
497         if (rc == EOK) {
498
499             ext4_bmap_bit_set(bitmap_block.data, rel_block_idx);
500
501             bitmap_block.dirty = true;
502             rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
503             if (rc != EOK){
504                 ext4_fs_put_block_group_ref(&bg_ref);
505                 return rc;
506             }
507
508             allocated_block =
509                     ext4_fs_index_in_group2_baddr(sb, rel_block_idx,
510                             bgid);
511
512             goto success;
513         }
514
515         rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
516         if(rc != EOK){
517             ext4_fs_put_block_group_ref(&bg_ref);
518             return rc;
519         }
520
521 next_group:
522         rc = ext4_fs_put_block_group_ref(&bg_ref);
523         if(rc != EOK){
524             return rc;
525         }
526
527         /* Goto next group */
528         bgid = (bgid + 1) % block_group_count;
529         count--;
530     }
531
532     return ENOSPC;
533
534     success:
535     /* Empty command - because of syntax */
536     ;
537
538     uint32_t block_size = ext4_sb_get_block_size(sb);
539
540     /* Update superblock free blocks count */
541     uint64_t sb_free_blocks = ext4_sb_get_free_blocks_cnt(sb);
542     sb_free_blocks--;
543     ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
544
545     /* Update inode blocks (different block size!) count */
546     uint64_t ino_blocks =
547             ext4_inode_get_blocks_count(sb, inode_ref->inode);
548     ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
549     ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
550     inode_ref->dirty = true;
551
552     /* Update block group free blocks count */
553     uint32_t bg_free_blocks =
554             ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
555     bg_free_blocks--;
556     ext4_bg_set_free_blocks_count(bg_ref.block_group, sb,
557         bg_free_blocks);
558
559     bg_ref.dirty = true;
560
561     rc = ext4_fs_put_block_group_ref(&bg_ref);
562
563     *fblock = allocated_block;
564     return rc;
565 }
566
567 int ext4_balloc_try_alloc_block(struct ext4_inode_ref *inode_ref,
568     uint32_t baddr, bool *free)
569 {
570     int rc;
571
572     struct ext4_fs *fs = inode_ref->fs;
573     struct ext4_sblock *sb = &fs->sb;
574
575     /* Compute indexes */
576     uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, baddr);
577     uint32_t index_in_group =
578             ext4_fs_baddr2_index_in_group(sb, baddr);
579
580     /* Load block group reference */
581     struct ext4_block_group_ref bg_ref;
582     rc = ext4_fs_get_block_group_ref(fs, block_group, &bg_ref);
583     if (rc != EOK)
584         return rc;
585
586     /* Load block with bitmap */
587     uint32_t bitmap_block_addr =
588             ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
589
590
591     struct ext4_block bitmap_block;
592
593     rc = ext4_block_get(fs->bdev, &bitmap_block, bitmap_block_addr);
594     if (rc != EOK){
595         ext4_fs_put_block_group_ref(&bg_ref);
596         return rc;
597     }
598
599     /* Check if block is free */
600     *free = ext4_bmap_is_bit_clr(bitmap_block.data, index_in_group);
601
602     /* Allocate block if possible */
603     if (*free) {
604         ext4_bmap_bit_set(bitmap_block.data, index_in_group);
605         bitmap_block.dirty = true;
606     }
607
608     /* Release block with bitmap */
609     rc = ext4_block_set(fs->bdev, &bitmap_block);
610     if (rc != EOK) {
611         /* Error in saving bitmap */
612         ext4_fs_put_block_group_ref(&bg_ref);
613         return rc;
614     }
615
616     /* If block is not free, return */
617     if (!(*free))
618         goto terminate;
619
620     uint32_t block_size = ext4_sb_get_block_size(sb);
621
622     /* Update superblock free blocks count */
623     uint64_t sb_free_blocks = ext4_sb_get_free_blocks_cnt(sb);
624     sb_free_blocks--;
625     ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
626
627     /* Update inode blocks count */
628     uint64_t ino_blocks =
629             ext4_inode_get_blocks_count(sb, inode_ref->inode);
630     ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
631     ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
632     inode_ref->dirty = true;
633
634     /* Update block group free blocks count */
635     uint32_t free_blocks =
636             ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
637     free_blocks--;
638     ext4_bg_set_free_blocks_count(bg_ref.block_group,
639         sb, free_blocks);
640
641     bg_ref.dirty = true;
642
643     terminate:
644     return ext4_fs_put_block_group_ref(&bg_ref);
645 }
646
647 /**
648  * @}
649  */