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