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