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