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