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@hootie.lvld.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-2000 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 #include <linux/fs.h>
  29 #include <linux/locks.h>
  30 #include <linux/quotaops.h>
  31 #include <linux/udf_fs.h>
  32
  33 #include <asm/bitops.h>
  34
  35 #include "udf_i.h"
  36 #include "udf_sb.h"
  37
  38 #define udf_clear_bit(nr,addr) ext2_clear_bit(nr,addr)
  39 #define udf_set_bit(nr,addr) ext2_set_bit(nr,addr)
  40 #define udf_test_bit(nr, addr) ext2_test_bit(nr, addr)
  41 #define udf_find_first_one_bit(addr, size) find_first_one_bit(addr, size)
  42 #define udf_find_next_one_bit(addr, size, offset) find_next_one_bit(addr, size, offset)
  43
  44 #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x)
  45 #define leNUM_to_cpup(x,y) xleNUM_to_cpup(x,y)
  46 #define xleNUM_to_cpup(x,y) (le ## x ## _to_cpup(y))
  47
  48 extern inline int find_next_one_bit (void * addr, int size, int offset)
  49 {
  50         unsigned long * p = ((unsigned long *) addr) + (offset / BITS_PER_LONG);
  51         unsigned long result = offset & ~(BITS_PER_LONG-1);
  52         unsigned long tmp;
  53
  54         if (offset >= size)
  55                 return size;
  56         size -= result;
  57         offset &= (BITS_PER_LONG-1);
  58         if (offset)
  59         {
  60                 tmp = leBPL_to_cpup(p++);
  61                 tmp &= ~0UL << offset;
  62                 if (size < BITS_PER_LONG)
  63                         goto found_first;
  64                 if (tmp)
  65                         goto found_middle;
  66                 size -= BITS_PER_LONG;
  67                 result += BITS_PER_LONG;
  68         }
  69         while (size & ~(BITS_PER_LONG-1))
  70         {
  71                 if ((tmp = leBPL_to_cpup(p++)))
  72                         goto found_middle;
  73                 result += BITS_PER_LONG;
  74                 size -= BITS_PER_LONG;
  75         }
  76         if (!size)
  77                 return result;
  78         tmp = leBPL_to_cpup(p);
  79 found_first:
  80         tmp &= ~0UL >> (BITS_PER_LONG-size);
  81 found_middle:
  82         return result + ffz(~tmp);
  83 }
  84
  85 #define find_first_one_bit(addr, size)\
  86         find_next_one_bit((addr), (size), 0)
  87
  88 static int read_block_bitmap(struct super_block * sb, Uint32 bitmap,
  89         unsigned int block, unsigned long bitmap_nr)
  90 {
  91         struct buffer_head *bh = NULL;
  92         int retval = 0;
  93         lb_addr loc;
  94
  95         loc.logicalBlockNum = bitmap;
  96         loc.partitionReferenceNum = UDF_SB_PARTITION(sb);
  97
  98         bh = udf_tread(sb, udf_get_lb_pblock(sb, loc, block), sb->s_blocksize);
  99         if (!bh)
 100         {
 101                 retval = -EIO;
 102         }
 103         UDF_SB_BLOCK_BITMAP_NUMBER(sb, bitmap_nr) = block;
 104         UDF_SB_BLOCK_BITMAP(sb, bitmap_nr) = bh;
 105         return retval;
 106 }
 107
 108 static int __load_block_bitmap(struct super_block * sb, Uint32 bitmap,
 109         unsigned int block_group)
 110 {
 111         int i, j, retval = 0;
 112         unsigned long block_bitmap_number;
 113         struct buffer_head * block_bitmap = NULL;
 114         int nr_groups = (UDF_SB_PARTLEN(sb, UDF_SB_PARTITION(sb)) +
 115                 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
 116
 117         if (block_group >= nr_groups)
 118         {
 119                 udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, nr_groups);
 120         }
 121
 122         if (nr_groups <= UDF_MAX_BLOCK_LOADED)
 123         {
 124                 if (UDF_SB_BLOCK_BITMAP(sb, block_group))
 125                 {
 126                         if (UDF_SB_BLOCK_BITMAP_NUMBER(sb, block_group) == block_group)
 127                                 return block_group;
 128                 }
 129                 retval = read_block_bitmap(sb, bitmap, block_group, block_group);
 130                 if (retval < 0)
 131                         return retval;
 132                 return block_group;
 133         }
 134
 135         for (i=0; i<UDF_SB_LOADED_BLOCK_BITMAPS(sb) &&
 136                 UDF_SB_BLOCK_BITMAP_NUMBER(sb, i) != block_group; i++)
 137         {
 138                 ;
 139         }
 140         if (i < UDF_SB_LOADED_BLOCK_BITMAPS(sb) &&
 141                 UDF_SB_BLOCK_BITMAP_NUMBER(sb, i) == block_group)
 142         {
 143                 block_bitmap_number = UDF_SB_BLOCK_BITMAP_NUMBER(sb, i);
 144                 block_bitmap = UDF_SB_BLOCK_BITMAP(sb, i);
 145                 for (j=i; j>0; j--)
 146                 {
 147                         UDF_SB_BLOCK_BITMAP_NUMBER(sb, j) = UDF_SB_BLOCK_BITMAP_NUMBER(sb, j-1);
 148                         UDF_SB_BLOCK_BITMAP(sb, j) = UDF_SB_BLOCK_BITMAP(sb, j-1);
 149                 }
 150                 UDF_SB_BLOCK_BITMAP_NUMBER(sb, 0) = block_bitmap_number;
 151                 UDF_SB_BLOCK_BITMAP(sb, 0) = block_bitmap;
 152
 153                 if (!block_bitmap)
 154                         retval = read_block_bitmap(sb, bitmap, block_group, 0);
 155         }
 156         else
 157         {
 158                 if (UDF_SB_LOADED_BLOCK_BITMAPS(sb) < UDF_MAX_BLOCK_LOADED)
 159                         UDF_SB_LOADED_BLOCK_BITMAPS(sb) ++;
 160                 else
 161                         brelse(UDF_SB_BLOCK_BITMAP(sb, UDF_MAX_BLOCK_LOADED-1));
 162                 for (j=UDF_SB_LOADED_BLOCK_BITMAPS(sb)-1; j>0; j--)
 163                 {
 164                         UDF_SB_BLOCK_BITMAP_NUMBER(sb, j) = UDF_SB_BLOCK_BITMAP_NUMBER(sb, j-1);
 165                         UDF_SB_BLOCK_BITMAP(sb, j) = UDF_SB_BLOCK_BITMAP(sb, j-1);
 166                 }
 167                 retval = read_block_bitmap(sb, bitmap, block_group, 0);
 168         }
 169         return retval;
 170 }
 171
 172 static inline int load_block_bitmap(struct super_block *sb, Uint32 bitmap,
 173         unsigned int block_group)
 174 {
 175         int slot;
 176         int nr_groups = (UDF_SB_PARTLEN(sb, UDF_SB_PARTITION(sb)) +
 177                 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
 178
 179         if (UDF_SB_LOADED_BLOCK_BITMAPS(sb) > 0 &&
 180                 UDF_SB_BLOCK_BITMAP_NUMBER(sb, 0) == block_group &&
 181                 UDF_SB_BLOCK_BITMAP(sb, block_group))
 182         {
 183                 return 0;
 184         }
 185         else if (nr_groups <= UDF_MAX_BLOCK_LOADED &&
 186                 UDF_SB_BLOCK_BITMAP_NUMBER(sb, block_group) == block_group &&
 187                 UDF_SB_BLOCK_BITMAP(sb, block_group))
 188         {
 189                 slot = block_group;
 190         }
 191         else
 192         {
 193                 slot = __load_block_bitmap(sb, bitmap, block_group);
 194         }
 195
 196         if (slot < 0)
 197                 return slot;
 198
 199         if (!UDF_SB_BLOCK_BITMAP(sb, slot))
 200                 return -EIO;
 201
 202         return slot;
 203 }
 204
 205 static void udf_bitmap_free_blocks(const struct inode * inode, Uint32 bitmap,
 206         lb_addr bloc, Uint32 offset, Uint32 count)
 207 {
 208         struct buffer_head * bh = NULL;
 209         unsigned long block;
 210         unsigned long block_group;
 211         unsigned long bit;
 212         unsigned long i;
 213         int bitmap_nr;
 214         unsigned long overflow;
 215         struct super_block * sb;
 216
 217         sb = inode->i_sb;
 218         if (!sb)
 219         {
 220                 udf_debug("nonexistent device");
 221                 return;
 222         }
 223
 224         lock_super(sb);
 225         if (bloc.logicalBlockNum < 0 ||
 226                 (bloc.logicalBlockNum + count) > UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum))
 227         {
 228                 udf_debug("%d < %d || %d + %d > %d\n",
 229                         bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count,
 230                         UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum));
 231                 goto error_return;
 232         }
 233
 234         block = bloc.logicalBlockNum + offset + (sizeof(struct SpaceBitmapDesc) << 3);
 235
 236 do_more:
 237         overflow = 0;
 238         block_group = block >> (sb->s_blocksize_bits + 3);
 239         bit = block % (sb->s_blocksize << 3);
 240
 241         /*
 242          * Check to see if we are freeing blocks across a group boundary.
 243          */
 244         if (bit + count > (sb->s_blocksize << 3))
 245         {
 246                 overflow = bit + count - (sb->s_blocksize << 3);
 247                 count -= overflow;
 248         }
 249         bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 250         if (bitmap_nr < 0)
 251                 goto error_return;
 252
 253         bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
 254         for (i=0; i < count; i++)
 255         {
 256                 if (udf_set_bit(bit + i, bh->b_data))
 257                 {
 258                         udf_debug("bit %ld already set\n", bit + i);
 259                         udf_debug("byte=%2x\n", ((char *)bh->b_data)[(bit + i) >> 3]);
 260                 }
 261                 else
 262                 {
 263                         DQUOT_FREE_BLOCK(sb, inode, 1);
 264                         if (UDF_SB_LVIDBH(sb))
 265                         {
 266                                 UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)] =
 267                                         cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)])+1);
 268                         }
 269                 }
 270         }
 271         mark_buffer_dirty(bh);
 272         if (overflow)
 273         {
 274                 block += count;
 275                 count = overflow;
 276                 goto do_more;
 277         }
 278 error_return:
 279         sb->s_dirt = 1;
 280         if (UDF_SB_LVIDBH(sb))
 281                 mark_buffer_dirty(UDF_SB_LVIDBH(sb));
 282         unlock_super(sb);
 283         return;
 284 }
 285
 286 static int udf_bitmap_prealloc_blocks(const struct inode * inode, Uint32 bitmap,
 287         Uint16 partition, Uint32 first_block, Uint32 block_count)
 288 {
 289         int alloc_count = 0;
 290         int bit, block, block_group, group_start;
 291         int nr_groups, bitmap_nr;
 292         struct buffer_head *bh;
 293         struct super_block *sb;
 294
 295         sb = inode->i_sb;
 296         if (!sb)
 297         {
 298                 udf_debug("nonexistent device\n");
 299                 return 0;
 300         }
 301         lock_super(sb);
 302
 303         if (first_block < 0 || first_block >= UDF_SB_PARTLEN(sb, partition))
 304                 goto out;
 305
 306 repeat:
 307         nr_groups = (UDF_SB_PARTLEN(sb, partition) +
 308                 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
 309         block = first_block + (sizeof(struct SpaceBitmapDesc) << 3);
 310         block_group = block >> (sb->s_blocksize_bits + 3);
 311         group_start = block_group ? 0 : sizeof(struct SpaceBitmapDesc);
 312
 313         bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 314         if (bitmap_nr < 0)
 315                 goto out;
 316         bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
 317
 318         bit = block % (sb->s_blocksize << 3);
 319
 320         while (bit < (sb->s_blocksize << 3) && block_count > 0)
 321         {
 322                 if (!udf_test_bit(bit, bh->b_data))
 323                         goto out;
 324                 else if (DQUOT_PREALLOC_BLOCK(sb, inode, 1))
 325                         goto out;
 326                 else if (!udf_clear_bit(bit, bh->b_data))
 327                 {
 328                         udf_debug("bit already cleared for block %d\n", bit);
 329                         DQUOT_FREE_BLOCK(sb, inode, 1);
 330                         goto out;
 331                 }
 332                 block_count --;
 333                 alloc_count ++;
 334                 bit ++;
 335                 block ++;
 336         }
 337         mark_buffer_dirty(bh);
 338         if (block_count > 0)
 339                 goto repeat;
 340 out:
 341         if (UDF_SB_LVIDBH(sb))
 342         {
 343                 UDF_SB_LVID(sb)->freeSpaceTable[partition] =
 344                         cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-alloc_count);
 345                 mark_buffer_dirty(UDF_SB_LVIDBH(sb));
 346         }
 347         sb->s_dirt = 1;
 348         unlock_super(sb);
 349         return alloc_count;
 350 }
 351
 352 static int udf_bitmap_new_block(const struct inode * inode, Uint32 bitmap,
 353         Uint16 partition, Uint32 goal, int *err)
 354 {
 355         int tmp, newbit, bit=0, block, block_group, group_start;
 356         int end_goal, nr_groups, bitmap_nr, i;
 357         struct buffer_head *bh = NULL;
 358         struct super_block *sb;
 359         char *ptr;
 360         int newblock = 0;
 361
 362         *err = -ENOSPC;
 363         sb = inode->i_sb;
 364         if (!sb)
 365         {
 366                 udf_debug("nonexistent device\n");
 367                 return newblock;
 368         }
 369         lock_super(sb);
 370
 371 repeat:
 372         if (goal < 0 || goal >= UDF_SB_PARTLEN(sb, partition))
 373                 goal = 0;
 374
 375         nr_groups = (UDF_SB_PARTLEN(sb, partition) +
 376                 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
 377         block = goal + (sizeof(struct SpaceBitmapDesc) << 3);
 378         block_group = block >> (sb->s_blocksize_bits + 3);
 379         group_start = block_group ? 0 : sizeof(struct SpaceBitmapDesc);
 380
 381         bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 382         if (bitmap_nr < 0)
 383                 goto error_return;
 384         bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
 385         ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start);
 386
 387         if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize)
 388         {
 389                 bit = block % (sb->s_blocksize << 3);
 390
 391                 if (udf_test_bit(bit, bh->b_data))
 392                 {
 393                         goto got_block;
 394                 }
 395                 end_goal = (bit + 63) & ~63;
 396                 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);
 397                 if (bit < end_goal)
 398                         goto got_block;
 399                 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, sb->s_blocksize - ((bit + 7) >> 3));
 400                 newbit = (ptr - ((char *)bh->b_data)) << 3;
 401                 if (newbit < sb->s_blocksize << 3)
 402                 {
 403                         bit = newbit;
 404                         goto search_back;
 405                 }
 406                 newbit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, bit);
 407                 if (newbit < sb->s_blocksize << 3)
 408                 {
 409                         bit = newbit;
 410                         goto got_block;
 411                 }
 412         }
 413
 414         for (i=0; i<(nr_groups*2); i++)
 415         {
 416                 block_group ++;
 417                 if (block_group >= nr_groups)
 418                         block_group = 0;
 419                 group_start = block_group ? 0 : sizeof(struct SpaceBitmapDesc);
 420
 421                 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
 422                 if (bitmap_nr < 0)
 423                         goto error_return;
 424                 bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
 425                 if (i < nr_groups)
 426                 {
 427                         ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start);
 428                         if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize)
 429                         {
 430                                 bit = (ptr - ((char *)bh->b_data)) << 3;
 431                                 break;
 432                         }
 433                 }
 434                 else
 435                 {
 436                         bit = udf_find_next_one_bit((char *)bh->b_data, sb->s_blocksize << 3, group_start << 3);
 437                         if (bit < sb->s_blocksize << 3)
 438                                 break;
 439                 }
 440         }
 441         if (i >= (nr_groups*2))
 442         {
 443                 unlock_super(sb);
 444                 return newblock;
 445         }
 446         if (bit < sb->s_blocksize << 3)
 447                 goto search_back;
 448         else
 449                 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, group_start << 3);
 450         if (bit >= sb->s_blocksize << 3)
 451         {
 452                 unlock_super(sb);
 453                 return 0;
 454         }
 455
 456 search_back:
 457         for (i=0; i<7 && bit > (group_start << 3) && udf_test_bit(bit - 1, bh->b_data); i++, bit--);
 458
 459 got_block:
 460
 461         /*
 462          * Check quota for allocation of this block.
 463          */
 464         if (DQUOT_ALLOC_BLOCK(sb, inode, 1))
 465         {
 466                 unlock_super(sb);
 467                 *err = -EDQUOT;
 468                 return 0;
 469         }
 470
 471         newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
 472                 (sizeof(struct SpaceBitmapDesc) << 3);
 473
 474         tmp = udf_get_pblock(sb, newblock, partition, 0);
 475         if (!udf_clear_bit(bit, bh->b_data))
 476         {
 477                 udf_debug("bit already cleared for block %d\n", bit);
 478                 goto repeat;
 479         }
 480
 481         mark_buffer_dirty(bh);
 482
 483         if (UDF_SB_LVIDBH(sb))
 484         {
 485                 UDF_SB_LVID(sb)->freeSpaceTable[partition] =
 486                         cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-1);
 487                 mark_buffer_dirty(UDF_SB_LVIDBH(sb));
 488         }
 489         sb->s_dirt = 1;
 490         unlock_super(sb);
 491         *err = 0;
 492         return newblock;
 493
 494 error_return:
 495         *err = -EIO;
 496         unlock_super(sb);
 497         return 0;
 498 }
 499
 500 inline void udf_free_blocks(const struct inode * inode, lb_addr bloc,
 501     Uint32 offset, Uint32 count)
 502 {
 503         if (UDF_SB_PARTFLAGS(inode->i_sb, bloc.partitionReferenceNum) & UDF_PART_FLAG_UNALLOC_BITMAP)
 504         {
 505                 return udf_bitmap_free_blocks(inode,
 506                         UDF_SB_PARTMAPS(inode->i_sb)[bloc.partitionReferenceNum].s_uspace.bitmap,
 507                         bloc, offset, count);
 508         }
 509         else if (UDF_SB_PARTFLAGS(inode->i_sb, bloc.partitionReferenceNum) & UDF_PART_FLAG_FREED_BITMAP)
 510         {
 511                 return udf_bitmap_free_blocks(inode,
 512                         UDF_SB_PARTMAPS(inode->i_sb)[bloc.partitionReferenceNum].s_fspace.bitmap,
 513                         bloc, offset, count);
 514         }
 515         else
 516                 return;
 517 }
 518
 519 inline int udf_prealloc_blocks(const struct inode * inode, Uint16 partition,
 520         Uint32 first_block, Uint32 block_count)
 521 {
 522         if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
 523         {
 524                 return udf_bitmap_prealloc_blocks(inode,
 525                         UDF_SB_PARTMAPS(inode->i_sb)[partition].s_uspace.bitmap,
 526                         partition, first_block, block_count);
 527         }
 528         else if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
 529         {
 530                 return udf_bitmap_prealloc_blocks(inode,
 531                         UDF_SB_PARTMAPS(inode->i_sb)[partition].s_fspace.bitmap,
 532                         partition, first_block, block_count);
 533         }
 534         else
 535                 return 0;
 536 }
 537
 538 inline int udf_new_block(const struct inode * inode, Uint16 partition,
 539         Uint32 goal, int *err)
 540 {
 541         if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
 542         {
 543                 return udf_bitmap_new_block(inode,
 544                         UDF_SB_PARTMAPS(inode->i_sb)[partition].s_uspace.bitmap,
 545                         partition, goal, err);
 546         }
 547         else if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
 548         {
 549                 return udf_bitmap_new_block(inode,
 550                         UDF_SB_PARTMAPS(inode->i_sb)[partition].s_fspace.bitmap,
 551                         partition, goal, err);
 552         }
 553         else
 554         {
 555                 *err = -EIO;
 556                 return 0;
 557         }
 558 }
 559