fs/udf/balloc.c

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