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