fs/udf/balloc.c

   1 /*
   2  * balloc.c
   3  *
   4  * PURPOSE
   5  *      Block allocation handling routines for the OSTA-UDF(tm) filesystem.
   6  *
   7  * COPYRIGHT
   8  *      This file is distributed under the terms of the GNU General Public
   9  *      License (GPL). Copies of the GPL can be obtained from:
  10  *              ftp://prep.ai.mit.edu/pub/gnu/GPL
  11  *      Each contributing author retains all rights to their own work.
  12  *
  13  *  (C) 1999-2001 Ben Fennema
  14  *  (C) 1999 Stelias Computing Inc
  15  *
  16  * HISTORY
  17  *
  18  *  02/24/99 blf  Created.
  19  *
  20  */
  21
  22 #include "udfdecl.h"
  23
  24 #include <linux/quotaops.h>
  25 #include <linux/buffer_head.h>
  26 #include <linux/bitops.h>
  27
  28 #include "udf_i.h"
  29 #include "udf_sb.h"
  30
  31 #define udf_clear_bit(nr, addr) ext2_clear_bit(nr, addr)
  32 #define udf_set_bit(nr, addr) ext2_set_bit(nr, addr)
  33 #define udf_test_bit(nr, addr) ext2_test_bit(nr, addr)
  34 #define udf_find_next_one_bit(addr, size, offset) \
  35                 ext2_find_next_bit(addr, size, offset)
  36
  37 static int read_block_bitmap(struct super_block *sb,
  38                              struct udf_bitmap *bitmap, unsigned int block,
  39                              unsigned long bitmap_nr)
  40 {
  41         struct buffer_head *bh = NULL;
  42         int retval = 0;
  43         struct kernel_lb_addr loc;
  44
  45         loc.logicalBlockNum = bitmap->s_extPosition;
  46         loc.partitionReferenceNum = UDF_SB(sb)->s_partition;
  47
  48         bh = udf_tread(sb, udf_get_lb_pblock(sb, &loc, block));
  49         if (!bh)
  50                 retval = -EIO;
  51
  52         bitmap->s_block_bitmap[bitmap_nr] = bh;
  53         return retval;
  54 }
  55
  56 static int __load_block_bitmap(struct super_block *sb,
  57                                struct udf_bitmap *bitmap,
  58                                unsigned int block_group)
  59 {
  60         int retval = 0;
  61         int nr_groups = bitmap->s_nr_groups;
  62
  63         if (block_group >= nr_groups) {
  64                 udf_debug("block_group (%d) > nr_groups (%d)\n", block_group,
  65                           nr_groups);
  66         }
  67
  68         if (bitmap->s_block_bitmap[block_group]) {
  69                 return block_group;
  70         } else {
  71                 retval = read_block_bitmap(sb, bitmap, block_group,
  72                                            block_group);
  73                 if (retval < 0)
  74                         return retval;
  75                 return block_group;
  76         }
  77 }
  78
  79 static inline int load_block_bitmap(struct super_block *sb,
  80                                     struct udf_bitmap *bitmap,
  81                                     unsigned int block_group)
  82 {
  83         int slot;
  84
  85         slot = __load_block_bitmap(sb, bitmap, block_group);
  86
  87         if (slot < 0)
  88                 return slot;
  89
  90         if (!bitmap->s_block_bitmap[slot])
  91                 return -EIO;
  92
  93         return slot;
  94 }
  95
  96 static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt)
  97 {
  98         struct udf_sb_info *sbi = UDF_SB(sb);
  99         struct logicalVolIntegrityDesc *lvid;
 100
 101         if (!sbi->s_lvid_bh)
 102                 return;
 103
 104         lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data;
 105         le32_add_cpu(&lvid->freeSpaceTable[partition], cnt);
 106         udf_updated_lvid(sb);
 107 }
 108
 109 static void udf_bitmap_free_blocks(struct super_block *sb,
 110                                    struct inode *inode,
 111                                    struct udf_bitmap *bitmap,
 112                                    struct kernel_lb_addr *bloc,
 113                                    uint32_t offset,
 114                                    uint32_t count)
 115 {
 116         struct udf_sb_info *sbi = UDF_SB(sb);
 117         struct buffer_head *bh = NULL;
 118         struct udf_part_map *partmap;
 119         unsigned long block;
 120         unsigned long block_group;
 121         unsigned long bit;
 122         unsigned long i;
 123         int bitmap_nr;
 124         unsigned long overflow;
 125
 126         mutex_lock(&sbi->s_alloc_mutex);
 127         partmap = &sbi->s_partmaps[bloc->partitionReferenceNum];
 128         if (bloc->logicalBlockNum + count < count ||
 129             (bloc->logicalBlockNum + count) > partmap->s_partition_len) {
 130                 udf_debug("%d < %d || %d + %d > %d\n",
 131                           bloc->logicalBlockNum, 0, bloc->logicalBlockNum,
 132                           count, partmap->s_partition_len);
 133                 goto error_return;
 134         }
 135
 136         block = bloc->logicalBlockNum + offset +
 137                 (sizeof(struct spaceBitmapDesc) << 3);
 138
 139         do {
 140                 overflow = 0;
 141                 block_group = block >> (sb->s_blocksize_bits + 3);
 142                 bit = block % (sb->s_blocksize << 3);
 143
 144                 /*
 145                 * Check to see if we are freeing blocks across a group boundary.
 146                 */
 147                 if (bit + count > (sb->s_blocksize << 3)) {
 148                         overflow = bit + count - (sb->s_blocksize << 3);
 149                         count -= overflow;
 150                 }
 151                 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 152                 if (bitmap_nr < 0)
 153                         goto error_return;
 154
 155                 bh = bitmap->s_block_bitmap[bitmap_nr];
 156                 for (i = 0; i < count; i++) {
 157                         if (udf_set_bit(bit + i, bh->b_data)) {
 158                                 udf_debug("bit %ld already set\n", bit + i);
 159                                 udf_debug("byte=%2x\n",
 160                                         ((char *)bh->b_data)[(bit + i) >> 3]);
 161                         } else {
 162                                 if (inode)
 163                                         dquot_free_block(inode, 1);
 164                                 udf_add_free_space(sb, sbi->s_partition, 1);
 165                         }
 166                 }
 167                 mark_buffer_dirty(bh);
 168                 if (overflow) {
 169                         block += count;
 170                         count = overflow;
 171                 }
 172         } while (overflow);
 173
 174 error_return:
 175         mutex_unlock(&sbi->s_alloc_mutex);
 176 }
 177
 178 static int udf_bitmap_prealloc_blocks(struct super_block *sb,
 179                                       struct inode *inode,
 180                                       struct udf_bitmap *bitmap,
 181                                       uint16_t partition, uint32_t first_block,
 182                                       uint32_t block_count)
 183 {
 184         struct udf_sb_info *sbi = UDF_SB(sb);
 185         int alloc_count = 0;
 186         int bit, block, block_group, group_start;
 187         int nr_groups, bitmap_nr;
 188         struct buffer_head *bh;
 189         __u32 part_len;
 190
 191         mutex_lock(&sbi->s_alloc_mutex);
 192         part_len = sbi->s_partmaps[partition].s_partition_len;
 193         if (first_block >= part_len)
 194                 goto out;
 195
 196         if (first_block + block_count > part_len)
 197                 block_count = part_len - first_block;
 198
 199         do {
 200                 nr_groups = udf_compute_nr_groups(sb, partition);
 201                 block = first_block + (sizeof(struct spaceBitmapDesc) << 3);
 202                 block_group = block >> (sb->s_blocksize_bits + 3);
 203                 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
 204
 205                 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 206                 if (bitmap_nr < 0)
 207                         goto out;
 208                 bh = bitmap->s_block_bitmap[bitmap_nr];
 209
 210                 bit = block % (sb->s_blocksize << 3);
 211
 212                 while (bit < (sb->s_blocksize << 3) && block_count > 0) {
 213                         if (!udf_test_bit(bit, bh->b_data))
 214                                 goto out;
 215                         else if (dquot_prealloc_block(inode, 1))
 216                                 goto out;
 217                         else if (!udf_clear_bit(bit, bh->b_data)) {
 218                                 udf_debug("bit already cleared for block %d\n", bit);
 219                                 dquot_free_block(inode, 1);
 220                                 goto out;
 221                         }
 222                         block_count--;
 223                         alloc_count++;
 224                         bit++;
 225                         block++;
 226                 }
 227                 mark_buffer_dirty(bh);
 228         } while (block_count > 0);
 229
 230 out:
 231         udf_add_free_space(sb, partition, -alloc_count);
 232         mutex_unlock(&sbi->s_alloc_mutex);
 233         return alloc_count;
 234 }
 235
 236 static int udf_bitmap_new_block(struct super_block *sb,
 237                                 struct inode *inode,
 238                                 struct udf_bitmap *bitmap, uint16_t partition,
 239                                 uint32_t goal, int *err)
 240 {
 241         struct udf_sb_info *sbi = UDF_SB(sb);
 242         int newbit, bit = 0, block, block_group, group_start;
 243         int end_goal, nr_groups, bitmap_nr, i;
 244         struct buffer_head *bh = NULL;
 245         char *ptr;
 246         int newblock = 0;
 247
 248         *err = -ENOSPC;
 249         mutex_lock(&sbi->s_alloc_mutex);
 250
 251 repeat:
 252         if (goal >= sbi->s_partmaps[partition].s_partition_len)
 253                 goal = 0;
 254
 255         nr_groups = bitmap->s_nr_groups;
 256         block = goal + (sizeof(struct spaceBitmapDesc) << 3);
 257         block_group = block >> (sb->s_blocksize_bits + 3);
 258         group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
 259
 260         bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 261         if (bitmap_nr < 0)
 262                 goto error_return;
 263         bh = bitmap->s_block_bitmap[bitmap_nr];
 264         ptr = memscan((char *)bh->b_data + group_start, 0xFF,
 265                       sb->s_blocksize - group_start);
 266
 267         if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
 268                 bit = block % (sb->s_blocksize << 3);
 269                 if (udf_test_bit(bit, bh->b_data))
 270                         goto got_block;
 271
 272                 end_goal = (bit + 63) & ~63;
 273                 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);
 274                 if (bit < end_goal)
 275                         goto got_block;
 276
 277                 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF,
 278                               sb->s_blocksize - ((bit + 7) >> 3));
 279                 newbit = (ptr - ((char *)bh->b_data)) << 3;
 280                 if (newbit < sb->s_blocksize << 3) {
 281                         bit = newbit;
 282                         goto search_back;
 283                 }
 284
 285                 newbit = udf_find_next_one_bit(bh->b_data,
 286                                                sb->s_blocksize << 3, bit);
 287                 if (newbit < sb->s_blocksize << 3) {
 288                         bit = newbit;
 289                         goto got_block;
 290                 }
 291         }
 292
 293         for (i = 0; i < (nr_groups * 2); i++) {
 294                 block_group++;
 295                 if (block_group >= nr_groups)
 296                         block_group = 0;
 297                 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
 298
 299                 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 300                 if (bitmap_nr < 0)
 301                         goto error_return;
 302                 bh = bitmap->s_block_bitmap[bitmap_nr];
 303                 if (i < nr_groups) {
 304                         ptr = memscan((char *)bh->b_data + group_start, 0xFF,
 305                                       sb->s_blocksize - group_start);
 306                         if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
 307                                 bit = (ptr - ((char *)bh->b_data)) << 3;
 308                                 break;
 309                         }
 310                 } else {
 311                         bit = udf_find_next_one_bit((char *)bh->b_data,
 312                                                     sb->s_blocksize << 3,
 313                                                     group_start << 3);
 314                         if (bit < sb->s_blocksize << 3)
 315                                 break;
 316                 }
 317         }
 318         if (i >= (nr_groups * 2)) {
 319                 mutex_unlock(&sbi->s_alloc_mutex);
 320                 return newblock;
 321         }
 322         if (bit < sb->s_blocksize << 3)
 323                 goto search_back;
 324         else
 325                 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3,
 326                                             group_start << 3);
 327         if (bit >= sb->s_blocksize << 3) {
 328                 mutex_unlock(&sbi->s_alloc_mutex);
 329                 return 0;
 330         }
 331
 332 search_back:
 333         i = 0;
 334         while (i < 7 && bit > (group_start << 3) &&
 335                udf_test_bit(bit - 1, bh->b_data)) {
 336                 ++i;
 337                 --bit;
 338         }
 339
 340 got_block:
 341
 342         /*
 343          * Check quota for allocation of this block.
 344          */
 345         if (inode) {
 346                 int ret = dquot_alloc_block(inode, 1);
 347
 348                 if (ret) {
 349                         mutex_unlock(&sbi->s_alloc_mutex);
 350                         *err = ret;
 351                         return 0;
 352                 }
 353         }
 354
 355         newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
 356                 (sizeof(struct spaceBitmapDesc) << 3);
 357
 358         if (!udf_clear_bit(bit, bh->b_data)) {
 359                 udf_debug("bit already cleared for block %d\n", bit);
 360                 goto repeat;
 361         }
 362
 363         mark_buffer_dirty(bh);
 364
 365         udf_add_free_space(sb, partition, -1);
 366         mutex_unlock(&sbi->s_alloc_mutex);
 367         *err = 0;
 368         return newblock;
 369
 370 error_return:
 371         *err = -EIO;
 372         mutex_unlock(&sbi->s_alloc_mutex);
 373         return 0;
 374 }
 375
 376 static void udf_table_free_blocks(struct super_block *sb,
 377                                   struct inode *inode,
 378                                   struct inode *table,
 379                                   struct kernel_lb_addr *bloc,
 380                                   uint32_t offset,
 381                                   uint32_t count)
 382 {
 383         struct udf_sb_info *sbi = UDF_SB(sb);
 384         struct udf_part_map *partmap;
 385         uint32_t start, end;
 386         uint32_t elen;
 387         struct kernel_lb_addr eloc;
 388         struct extent_position oepos, epos;
 389         int8_t etype;
 390         int i;
 391         struct udf_inode_info *iinfo;
 392
 393         mutex_lock(&sbi->s_alloc_mutex);
 394         partmap = &sbi->s_partmaps[bloc->partitionReferenceNum];
 395         if (bloc->logicalBlockNum + count < count ||
 396             (bloc->logicalBlockNum + count) > partmap->s_partition_len) {
 397                 udf_debug("%d < %d || %d + %d > %d\n",
 398                           bloc->logicalBlockNum, 0, bloc->logicalBlockNum, count,
 399                           partmap->s_partition_len);
 400                 goto error_return;
 401         }
 402
 403         iinfo = UDF_I(table);
 404         /* We do this up front - There are some error conditions that
 405            could occure, but.. oh well */
 406         if (inode)
 407                 dquot_free_block(inode, count);
 408         udf_add_free_space(sb, sbi->s_partition, count);
 409
 410         start = bloc->logicalBlockNum + offset;
 411         end = bloc->logicalBlockNum + offset + count - 1;
 412
 413         epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry);
 414         elen = 0;
 415         epos.block = oepos.block = iinfo->i_location;
 416         epos.bh = oepos.bh = NULL;
 417
 418         while (count &&
 419                (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
 420                 if (((eloc.logicalBlockNum +
 421                         (elen >> sb->s_blocksize_bits)) == start)) {
 422                         if ((0x3FFFFFFF - elen) <
 423                                         (count << sb->s_blocksize_bits)) {
 424                                 uint32_t tmp = ((0x3FFFFFFF - elen) >>
 425                                                         sb->s_blocksize_bits);
 426                                 count -= tmp;
 427                                 start += tmp;
 428                                 elen = (etype << 30) |
 429                                         (0x40000000 - sb->s_blocksize);
 430                         } else {
 431                                 elen = (etype << 30) |
 432                                         (elen +
 433                                         (count << sb->s_blocksize_bits));
 434                                 start += count;
 435                                 count = 0;
 436                         }
 437                         udf_write_aext(table, &oepos, &eloc, elen, 1);
 438                 } else if (eloc.logicalBlockNum == (end + 1)) {
 439                         if ((0x3FFFFFFF - elen) <
 440                                         (count << sb->s_blocksize_bits)) {
 441                                 uint32_t tmp = ((0x3FFFFFFF - elen) >>
 442                                                 sb->s_blocksize_bits);
 443                                 count -= tmp;
 444                                 end -= tmp;
 445                                 eloc.logicalBlockNum -= tmp;
 446                                 elen = (etype << 30) |
 447                                         (0x40000000 - sb->s_blocksize);
 448                         } else {
 449                                 eloc.logicalBlockNum = start;
 450                                 elen = (etype << 30) |
 451                                         (elen +
 452                                         (count << sb->s_blocksize_bits));
 453                                 end -= count;
 454                                 count = 0;
 455                         }
 456                         udf_write_aext(table, &oepos, &eloc, elen, 1);
 457                 }
 458
 459                 if (epos.bh != oepos.bh) {
 460                         i = -1;
 461                         oepos.block = epos.block;
 462                         brelse(oepos.bh);
 463                         get_bh(epos.bh);
 464                         oepos.bh = epos.bh;
 465                         oepos.offset = 0;
 466                 } else {
 467                         oepos.offset = epos.offset;
 468                 }
 469         }
 470
 471         if (count) {
 472                 /*
 473                  * NOTE: we CANNOT use udf_add_aext here, as it can try to
 474                  * allocate a new block, and since we hold the super block
 475                  * lock already very bad things would happen :)
 476                  *
 477                  * We copy the behavior of udf_add_aext, but instead of
 478                  * trying to allocate a new block close to the existing one,
 479                  * we just steal a block from the extent we are trying to add.
 480                  *
 481                  * It would be nice if the blocks were close together, but it
 482                  * isn't required.
 483                  */
 484
 485                 int adsize;
 486                 struct short_ad *sad = NULL;
 487                 struct long_ad *lad = NULL;
 488                 struct allocExtDesc *aed;
 489
 490                 eloc.logicalBlockNum = start;
 491                 elen = EXT_RECORDED_ALLOCATED |
 492                         (count << sb->s_blocksize_bits);
 493
 494                 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
 495                         adsize = sizeof(struct short_ad);
 496                 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
 497                         adsize = sizeof(struct long_ad);
 498                 else {
 499                         brelse(oepos.bh);
 500                         brelse(epos.bh);
 501                         goto error_return;
 502                 }
 503
 504                 if (epos.offset + (2 * adsize) > sb->s_blocksize) {
 505                         unsigned char *sptr, *dptr;
 506                         int loffset;
 507
 508                         brelse(oepos.bh);
 509                         oepos = epos;
 510
 511                         /* Steal a block from the extent being free'd */
 512                         epos.block.logicalBlockNum = eloc.logicalBlockNum;
 513                         eloc.logicalBlockNum++;
 514                         elen -= sb->s_blocksize;
 515
 516                         epos.bh = udf_tread(sb,
 517                                         udf_get_lb_pblock(sb, &epos.block, 0));
 518                         if (!epos.bh) {
 519                                 brelse(oepos.bh);
 520                                 goto error_return;
 521                         }
 522                         aed = (struct allocExtDesc *)(epos.bh->b_data);
 523                         aed->previousAllocExtLocation =
 524                                 cpu_to_le32(oepos.block.logicalBlockNum);
 525                         if (epos.offset + adsize > sb->s_blocksize) {
 526                                 loffset = epos.offset;
 527                                 aed->lengthAllocDescs = cpu_to_le32(adsize);
 528                                 sptr = iinfo->i_ext.i_data + epos.offset
 529                                                                 - adsize;
 530                                 dptr = epos.bh->b_data +
 531                                         sizeof(struct allocExtDesc);
 532                                 memcpy(dptr, sptr, adsize);
 533                                 epos.offset = sizeof(struct allocExtDesc) +
 534                                                 adsize;
 535                         } else {
 536                                 loffset = epos.offset + adsize;
 537                                 aed->lengthAllocDescs = cpu_to_le32(0);
 538                                 if (oepos.bh) {
 539                                         sptr = oepos.bh->b_data + epos.offset;
 540                                         aed = (struct allocExtDesc *)
 541                                                 oepos.bh->b_data;
 542                                         le32_add_cpu(&aed->lengthAllocDescs,
 543                                                         adsize);
 544                                 } else {
 545                                         sptr = iinfo->i_ext.i_data +
 546                                                                 epos.offset;
 547                                         iinfo->i_lenAlloc += adsize;
 548                                         mark_inode_dirty(table);
 549                                 }
 550                                 epos.offset = sizeof(struct allocExtDesc);
 551                         }
 552                         if (sbi->s_udfrev >= 0x0200)
 553                                 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED,
 554                                             3, 1, epos.block.logicalBlockNum,
 555                                             sizeof(struct tag));
 556                         else
 557                                 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED,
 558                                             2, 1, epos.block.logicalBlockNum,
 559                                             sizeof(struct tag));
 560
 561                         switch (iinfo->i_alloc_type) {
 562                         case ICBTAG_FLAG_AD_SHORT:
 563                                 sad = (struct short_ad *)sptr;
 564                                 sad->extLength = cpu_to_le32(
 565                                         EXT_NEXT_EXTENT_ALLOCDECS |
 566                                         sb->s_blocksize);
 567                                 sad->extPosition =
 568                                         cpu_to_le32(epos.block.logicalBlockNum);
 569                                 break;
 570                         case ICBTAG_FLAG_AD_LONG:
 571                                 lad = (struct long_ad *)sptr;
 572                                 lad->extLength = cpu_to_le32(
 573                                         EXT_NEXT_EXTENT_ALLOCDECS |
 574                                         sb->s_blocksize);
 575                                 lad->extLocation =
 576                                         cpu_to_lelb(epos.block);
 577                                 break;
 578                         }
 579                         if (oepos.bh) {
 580                                 udf_update_tag(oepos.bh->b_data, loffset);
 581                                 mark_buffer_dirty(oepos.bh);
 582                         } else {
 583                                 mark_inode_dirty(table);
 584                         }
 585                 }
 586
 587                 /* It's possible that stealing the block emptied the extent */
 588                 if (elen) {
 589                         udf_write_aext(table, &epos, &eloc, elen, 1);
 590
 591                         if (!epos.bh) {
 592                                 iinfo->i_lenAlloc += adsize;
 593                                 mark_inode_dirty(table);
 594                         } else {
 595                                 aed = (struct allocExtDesc *)epos.bh->b_data;
 596                                 le32_add_cpu(&aed->lengthAllocDescs, adsize);
 597                                 udf_update_tag(epos.bh->b_data, epos.offset);
 598                                 mark_buffer_dirty(epos.bh);
 599                         }
 600                 }
 601         }
 602
 603         brelse(epos.bh);
 604         brelse(oepos.bh);
 605
 606 error_return:
 607         mutex_unlock(&sbi->s_alloc_mutex);
 608         return;
 609 }
 610
 611 static int udf_table_prealloc_blocks(struct super_block *sb,
 612                                      struct inode *inode,
 613                                      struct inode *table, uint16_t partition,
 614                                      uint32_t first_block, uint32_t block_count)
 615 {
 616         struct udf_sb_info *sbi = UDF_SB(sb);
 617         int alloc_count = 0;
 618         uint32_t elen, adsize;
 619         struct kernel_lb_addr eloc;
 620         struct extent_position epos;
 621         int8_t etype = -1;
 622         struct udf_inode_info *iinfo;
 623
 624         if (first_block >= sbi->s_partmaps[partition].s_partition_len)
 625                 return 0;
 626
 627         iinfo = UDF_I(table);
 628         if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
 629                 adsize = sizeof(struct short_ad);
 630         else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
 631                 adsize = sizeof(struct long_ad);
 632         else
 633                 return 0;
 634
 635         mutex_lock(&sbi->s_alloc_mutex);
 636         epos.offset = sizeof(struct unallocSpaceEntry);
 637         epos.block = iinfo->i_location;
 638         epos.bh = NULL;
 639         eloc.logicalBlockNum = 0xFFFFFFFF;
 640
 641         while (first_block != eloc.logicalBlockNum &&
 642                (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
 643                 udf_debug("eloc=%d, elen=%d, first_block=%d\n",
 644                           eloc.logicalBlockNum, elen, first_block);
 645                 ; /* empty loop body */
 646         }
 647
 648         if (first_block == eloc.logicalBlockNum) {
 649                 epos.offset -= adsize;
 650
 651                 alloc_count = (elen >> sb->s_blocksize_bits);
 652                 if (inode && dquot_prealloc_block(inode,
 653                         alloc_count > block_count ? block_count : alloc_count))
 654                         alloc_count = 0;
 655                 else if (alloc_count > block_count) {
 656                         alloc_count = block_count;
 657                         eloc.logicalBlockNum += alloc_count;
 658                         elen -= (alloc_count << sb->s_blocksize_bits);
 659                         udf_write_aext(table, &epos, &eloc,
 660                                         (etype << 30) | elen, 1);
 661                 } else
 662                         udf_delete_aext(table, epos, eloc,
 663                                         (etype << 30) | elen);
 664         } else {
 665                 alloc_count = 0;
 666         }
 667
 668         brelse(epos.bh);
 669
 670         if (alloc_count)
 671                 udf_add_free_space(sb, partition, -alloc_count);
 672         mutex_unlock(&sbi->s_alloc_mutex);
 673         return alloc_count;
 674 }
 675
 676 static int udf_table_new_block(struct super_block *sb,
 677                                struct inode *inode,
 678                                struct inode *table, uint16_t partition,
 679                                uint32_t goal, int *err)
 680 {
 681         struct udf_sb_info *sbi = UDF_SB(sb);
 682         uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF;
 683         uint32_t newblock = 0, adsize;
 684         uint32_t elen, goal_elen = 0;
 685         struct kernel_lb_addr eloc, uninitialized_var(goal_eloc);
 686         struct extent_position epos, goal_epos;
 687         int8_t etype;
 688         struct udf_inode_info *iinfo = UDF_I(table);
 689
 690         *err = -ENOSPC;
 691
 692         if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
 693                 adsize = sizeof(struct short_ad);
 694         else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
 695                 adsize = sizeof(struct long_ad);
 696         else
 697                 return newblock;
 698
 699         mutex_lock(&sbi->s_alloc_mutex);
 700         if (goal >= sbi->s_partmaps[partition].s_partition_len)
 701                 goal = 0;
 702
 703         /* We search for the closest matching block to goal. If we find
 704            a exact hit, we stop. Otherwise we keep going till we run out
 705            of extents. We store the buffer_head, bloc, and extoffset
 706            of the current closest match and use that when we are done.
 707          */
 708         epos.offset = sizeof(struct unallocSpaceEntry);
 709         epos.block = iinfo->i_location;
 710         epos.bh = goal_epos.bh = NULL;
 711
 712         while (spread &&
 713                (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
 714                 if (goal >= eloc.logicalBlockNum) {
 715                         if (goal < eloc.logicalBlockNum +
 716                                         (elen >> sb->s_blocksize_bits))
 717                                 nspread = 0;
 718                         else
 719                                 nspread = goal - eloc.logicalBlockNum -
 720                                         (elen >> sb->s_blocksize_bits);
 721                 } else {
 722                         nspread = eloc.logicalBlockNum - goal;
 723                 }
 724
 725                 if (nspread < spread) {
 726                         spread = nspread;
 727                         if (goal_epos.bh != epos.bh) {
 728                                 brelse(goal_epos.bh);
 729                                 goal_epos.bh = epos.bh;
 730                                 get_bh(goal_epos.bh);
 731                         }
 732                         goal_epos.block = epos.block;
 733                         goal_epos.offset = epos.offset - adsize;
 734                         goal_eloc = eloc;
 735                         goal_elen = (etype << 30) | elen;
 736                 }
 737         }
 738
 739         brelse(epos.bh);
 740
 741         if (spread == 0xFFFFFFFF) {
 742                 brelse(goal_epos.bh);
 743                 mutex_unlock(&sbi->s_alloc_mutex);
 744                 return 0;
 745         }
 746
 747         /* Only allocate blocks from the beginning of the extent.
 748            That way, we only delete (empty) extents, never have to insert an
 749            extent because of splitting */
 750         /* This works, but very poorly.... */
 751
 752         newblock = goal_eloc.logicalBlockNum;
 753         goal_eloc.logicalBlockNum++;
 754         goal_elen -= sb->s_blocksize;
 755         if (inode) {
 756                 *err = dquot_alloc_block(inode, 1);
 757                 if (*err) {
 758                         brelse(goal_epos.bh);
 759                         mutex_unlock(&sbi->s_alloc_mutex);
 760                         return 0;
 761                 }
 762         }
 763
 764         if (goal_elen)
 765                 udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1);
 766         else
 767                 udf_delete_aext(table, goal_epos, goal_eloc, goal_elen);
 768         brelse(goal_epos.bh);
 769
 770         udf_add_free_space(sb, partition, -1);
 771
 772         mutex_unlock(&sbi->s_alloc_mutex);
 773         *err = 0;
 774         return newblock;
 775 }
 776
 777 void udf_free_blocks(struct super_block *sb, struct inode *inode,
 778                      struct kernel_lb_addr *bloc, uint32_t offset,
 779                      uint32_t count)
 780 {
 781         uint16_t partition = bloc->partitionReferenceNum;
 782         struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
 783
 784         if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) {
 785                 udf_bitmap_free_blocks(sb, inode, map->s_uspace.s_bitmap,
 786                                        bloc, offset, count);
 787         } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) {
 788                 udf_table_free_blocks(sb, inode, map->s_uspace.s_table,
 789                                       bloc, offset, count);
 790         } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) {
 791                 udf_bitmap_free_blocks(sb, inode, map->s_fspace.s_bitmap,
 792                                        bloc, offset, count);
 793         } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) {
 794                 udf_table_free_blocks(sb, inode, map->s_fspace.s_table,
 795                                       bloc, offset, count);
 796         }
 797 }
 798
 799 inline int udf_prealloc_blocks(struct super_block *sb,
 800                                struct inode *inode,
 801                                uint16_t partition, uint32_t first_block,
 802                                uint32_t block_count)
 803 {
 804         struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
 805
 806         if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
 807                 return udf_bitmap_prealloc_blocks(sb, inode,
 808                                                   map->s_uspace.s_bitmap,
 809                                                   partition, first_block,
 810                                                   block_count);
 811         else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
 812                 return udf_table_prealloc_blocks(sb, inode,
 813                                                  map->s_uspace.s_table,
 814                                                  partition, first_block,
 815                                                  block_count);
 816         else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP)
 817                 return udf_bitmap_prealloc_blocks(sb, inode,
 818                                                   map->s_fspace.s_bitmap,
 819                                                   partition, first_block,
 820                                                   block_count);
 821         else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE)
 822                 return udf_table_prealloc_blocks(sb, inode,
 823                                                  map->s_fspace.s_table,
 824                                                  partition, first_block,
 825                                                  block_count);
 826         else
 827                 return 0;
 828 }
 829
 830 inline int udf_new_block(struct super_block *sb,
 831                          struct inode *inode,
 832                          uint16_t partition, uint32_t goal, int *err)
 833 {
 834         struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
 835
 836         if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
 837                 return udf_bitmap_new_block(sb, inode,
 838                                            map->s_uspace.s_bitmap,
 839                                            partition, goal, err);
 840         else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
 841                 return udf_table_new_block(sb, inode,
 842                                            map->s_uspace.s_table,
 843                                            partition, goal, err);
 844         else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP)
 845                 return udf_bitmap_new_block(sb, inode,
 846                                             map->s_fspace.s_bitmap,
 847                                             partition, goal, err);
 848         else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE)
 849                 return udf_table_new_block(sb, inode,
 850                                            map->s_fspace.s_table,
 851                                            partition, goal, err);
 852         else {
 853                 *err = -EIO;
 854                 return 0;
 855         }
 856 }