11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * balloc.c 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * PURPOSE 51da177e4SLinus Torvalds * Block allocation handling routines for the OSTA-UDF(tm) filesystem. 61da177e4SLinus Torvalds * 71da177e4SLinus Torvalds * COPYRIGHT 81da177e4SLinus Torvalds * This file is distributed under the terms of the GNU General Public 91da177e4SLinus Torvalds * License (GPL). Copies of the GPL can be obtained from: 101da177e4SLinus Torvalds * ftp://prep.ai.mit.edu/pub/gnu/GPL 111da177e4SLinus Torvalds * Each contributing author retains all rights to their own work. 121da177e4SLinus Torvalds * 131da177e4SLinus Torvalds * (C) 1999-2001 Ben Fennema 141da177e4SLinus Torvalds * (C) 1999 Stelias Computing Inc 151da177e4SLinus Torvalds * 161da177e4SLinus Torvalds * HISTORY 171da177e4SLinus Torvalds * 181da177e4SLinus Torvalds * 02/24/99 blf Created. 191da177e4SLinus Torvalds * 201da177e4SLinus Torvalds */ 211da177e4SLinus Torvalds 221da177e4SLinus Torvalds #include "udfdecl.h" 231da177e4SLinus Torvalds 241da177e4SLinus Torvalds #include <linux/quotaops.h> 251da177e4SLinus Torvalds #include <linux/buffer_head.h> 261da177e4SLinus Torvalds #include <linux/bitops.h> 271da177e4SLinus Torvalds 281da177e4SLinus Torvalds #include "udf_i.h" 291da177e4SLinus Torvalds #include "udf_sb.h" 301da177e4SLinus Torvalds 311da177e4SLinus Torvalds #define udf_clear_bit(nr,addr) ext2_clear_bit(nr,addr) 321da177e4SLinus Torvalds #define udf_set_bit(nr,addr) ext2_set_bit(nr,addr) 331da177e4SLinus Torvalds #define udf_test_bit(nr, addr) ext2_test_bit(nr, addr) 341da177e4SLinus Torvalds #define udf_find_first_one_bit(addr, size) find_first_one_bit(addr, size) 351da177e4SLinus Torvalds #define udf_find_next_one_bit(addr, size, offset) find_next_one_bit(addr, size, offset) 361da177e4SLinus Torvalds 371da177e4SLinus Torvalds #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x) 381da177e4SLinus Torvalds #define leNUM_to_cpup(x,y) xleNUM_to_cpup(x,y) 391da177e4SLinus Torvalds #define xleNUM_to_cpup(x,y) (le ## x ## _to_cpup(y)) 401da177e4SLinus Torvalds #define uintBPL_t uint(BITS_PER_LONG) 411da177e4SLinus Torvalds #define uint(x) xuint(x) 421da177e4SLinus Torvalds #define xuint(x) __le ## x 431da177e4SLinus Torvalds 44ddc0f846SAdrian Bunk static inline int find_next_one_bit (void * addr, int size, int offset) 451da177e4SLinus Torvalds { 461da177e4SLinus Torvalds uintBPL_t * p = ((uintBPL_t *) addr) + (offset / BITS_PER_LONG); 471da177e4SLinus Torvalds int result = offset & ~(BITS_PER_LONG-1); 481da177e4SLinus Torvalds unsigned long tmp; 491da177e4SLinus Torvalds 501da177e4SLinus Torvalds if (offset >= size) 511da177e4SLinus Torvalds return size; 521da177e4SLinus Torvalds size -= result; 531da177e4SLinus Torvalds offset &= (BITS_PER_LONG-1); 541da177e4SLinus Torvalds if (offset) 551da177e4SLinus Torvalds { 561da177e4SLinus Torvalds tmp = leBPL_to_cpup(p++); 571da177e4SLinus Torvalds tmp &= ~0UL << offset; 581da177e4SLinus Torvalds if (size < BITS_PER_LONG) 591da177e4SLinus Torvalds goto found_first; 601da177e4SLinus Torvalds if (tmp) 611da177e4SLinus Torvalds goto found_middle; 621da177e4SLinus Torvalds size -= BITS_PER_LONG; 631da177e4SLinus Torvalds result += BITS_PER_LONG; 641da177e4SLinus Torvalds } 651da177e4SLinus Torvalds while (size & ~(BITS_PER_LONG-1)) 661da177e4SLinus Torvalds { 671da177e4SLinus Torvalds if ((tmp = leBPL_to_cpup(p++))) 681da177e4SLinus Torvalds goto found_middle; 691da177e4SLinus Torvalds result += BITS_PER_LONG; 701da177e4SLinus Torvalds size -= BITS_PER_LONG; 711da177e4SLinus Torvalds } 721da177e4SLinus Torvalds if (!size) 731da177e4SLinus Torvalds return result; 741da177e4SLinus Torvalds tmp = leBPL_to_cpup(p); 751da177e4SLinus Torvalds found_first: 761da177e4SLinus Torvalds tmp &= ~0UL >> (BITS_PER_LONG-size); 771da177e4SLinus Torvalds found_middle: 781da177e4SLinus Torvalds return result + ffz(~tmp); 791da177e4SLinus Torvalds } 801da177e4SLinus Torvalds 811da177e4SLinus Torvalds #define find_first_one_bit(addr, size)\ 821da177e4SLinus Torvalds find_next_one_bit((addr), (size), 0) 831da177e4SLinus Torvalds 841da177e4SLinus Torvalds static int read_block_bitmap(struct super_block * sb, 851da177e4SLinus Torvalds struct udf_bitmap *bitmap, unsigned int block, unsigned long bitmap_nr) 861da177e4SLinus Torvalds { 871da177e4SLinus Torvalds struct buffer_head *bh = NULL; 881da177e4SLinus Torvalds int retval = 0; 891da177e4SLinus Torvalds kernel_lb_addr loc; 901da177e4SLinus Torvalds 911da177e4SLinus Torvalds loc.logicalBlockNum = bitmap->s_extPosition; 921da177e4SLinus Torvalds loc.partitionReferenceNum = UDF_SB_PARTITION(sb); 931da177e4SLinus Torvalds 941da177e4SLinus Torvalds bh = udf_tread(sb, udf_get_lb_pblock(sb, loc, block)); 951da177e4SLinus Torvalds if (!bh) 961da177e4SLinus Torvalds { 971da177e4SLinus Torvalds retval = -EIO; 981da177e4SLinus Torvalds } 991da177e4SLinus Torvalds bitmap->s_block_bitmap[bitmap_nr] = bh; 1001da177e4SLinus Torvalds return retval; 1011da177e4SLinus Torvalds } 1021da177e4SLinus Torvalds 1031da177e4SLinus Torvalds static int __load_block_bitmap(struct super_block * sb, 1041da177e4SLinus Torvalds struct udf_bitmap *bitmap, unsigned int block_group) 1051da177e4SLinus Torvalds { 1061da177e4SLinus Torvalds int retval = 0; 1071da177e4SLinus Torvalds int nr_groups = bitmap->s_nr_groups; 1081da177e4SLinus Torvalds 1091da177e4SLinus Torvalds if (block_group >= nr_groups) 1101da177e4SLinus Torvalds { 1111da177e4SLinus Torvalds udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, nr_groups); 1121da177e4SLinus Torvalds } 1131da177e4SLinus Torvalds 1141da177e4SLinus Torvalds if (bitmap->s_block_bitmap[block_group]) 1151da177e4SLinus Torvalds return block_group; 1161da177e4SLinus Torvalds else 1171da177e4SLinus Torvalds { 1181da177e4SLinus Torvalds retval = read_block_bitmap(sb, bitmap, block_group, block_group); 1191da177e4SLinus Torvalds if (retval < 0) 1201da177e4SLinus Torvalds return retval; 1211da177e4SLinus Torvalds return block_group; 1221da177e4SLinus Torvalds } 1231da177e4SLinus Torvalds } 1241da177e4SLinus Torvalds 1251da177e4SLinus Torvalds static inline int load_block_bitmap(struct super_block * sb, 1261da177e4SLinus Torvalds struct udf_bitmap *bitmap, unsigned int block_group) 1271da177e4SLinus Torvalds { 1281da177e4SLinus Torvalds int slot; 1291da177e4SLinus Torvalds 1301da177e4SLinus Torvalds slot = __load_block_bitmap(sb, bitmap, block_group); 1311da177e4SLinus Torvalds 1321da177e4SLinus Torvalds if (slot < 0) 1331da177e4SLinus Torvalds return slot; 1341da177e4SLinus Torvalds 1351da177e4SLinus Torvalds if (!bitmap->s_block_bitmap[slot]) 1361da177e4SLinus Torvalds return -EIO; 1371da177e4SLinus Torvalds 1381da177e4SLinus Torvalds return slot; 1391da177e4SLinus Torvalds } 1401da177e4SLinus Torvalds 1411da177e4SLinus Torvalds static void udf_bitmap_free_blocks(struct super_block * sb, 1421da177e4SLinus Torvalds struct inode * inode, 1431da177e4SLinus Torvalds struct udf_bitmap *bitmap, 1441da177e4SLinus Torvalds kernel_lb_addr bloc, uint32_t offset, uint32_t count) 1451da177e4SLinus Torvalds { 1461da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 1471da177e4SLinus Torvalds struct buffer_head * bh = NULL; 1481da177e4SLinus Torvalds unsigned long block; 1491da177e4SLinus Torvalds unsigned long block_group; 1501da177e4SLinus Torvalds unsigned long bit; 1511da177e4SLinus Torvalds unsigned long i; 1521da177e4SLinus Torvalds int bitmap_nr; 1531da177e4SLinus Torvalds unsigned long overflow; 1541da177e4SLinus Torvalds 1551e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 1561da177e4SLinus Torvalds if (bloc.logicalBlockNum < 0 || 1571da177e4SLinus Torvalds (bloc.logicalBlockNum + count) > UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum)) 1581da177e4SLinus Torvalds { 1591da177e4SLinus Torvalds udf_debug("%d < %d || %d + %d > %d\n", 1601da177e4SLinus Torvalds bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 1611da177e4SLinus Torvalds UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum)); 1621da177e4SLinus Torvalds goto error_return; 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds block = bloc.logicalBlockNum + offset + (sizeof(struct spaceBitmapDesc) << 3); 1661da177e4SLinus Torvalds 1671da177e4SLinus Torvalds do_more: 1681da177e4SLinus Torvalds overflow = 0; 1691da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 1701da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 1711da177e4SLinus Torvalds 1721da177e4SLinus Torvalds /* 1731da177e4SLinus Torvalds * Check to see if we are freeing blocks across a group boundary. 1741da177e4SLinus Torvalds */ 1751da177e4SLinus Torvalds if (bit + count > (sb->s_blocksize << 3)) 1761da177e4SLinus Torvalds { 1771da177e4SLinus Torvalds overflow = bit + count - (sb->s_blocksize << 3); 1781da177e4SLinus Torvalds count -= overflow; 1791da177e4SLinus Torvalds } 1801da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 1811da177e4SLinus Torvalds if (bitmap_nr < 0) 1821da177e4SLinus Torvalds goto error_return; 1831da177e4SLinus Torvalds 1841da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 1851da177e4SLinus Torvalds for (i=0; i < count; i++) 1861da177e4SLinus Torvalds { 1871da177e4SLinus Torvalds if (udf_set_bit(bit + i, bh->b_data)) 1881da177e4SLinus Torvalds { 1891da177e4SLinus Torvalds udf_debug("bit %ld already set\n", bit + i); 1901da177e4SLinus Torvalds udf_debug("byte=%2x\n", ((char *)bh->b_data)[(bit + i) >> 3]); 1911da177e4SLinus Torvalds } 1921da177e4SLinus Torvalds else 1931da177e4SLinus Torvalds { 1941da177e4SLinus Torvalds if (inode) 1951da177e4SLinus Torvalds DQUOT_FREE_BLOCK(inode, 1); 1961da177e4SLinus Torvalds if (UDF_SB_LVIDBH(sb)) 1971da177e4SLinus Torvalds { 1981da177e4SLinus Torvalds UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)] = 1991da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)])+1); 2001da177e4SLinus Torvalds } 2011da177e4SLinus Torvalds } 2021da177e4SLinus Torvalds } 2031da177e4SLinus Torvalds mark_buffer_dirty(bh); 2041da177e4SLinus Torvalds if (overflow) 2051da177e4SLinus Torvalds { 2061da177e4SLinus Torvalds block += count; 2071da177e4SLinus Torvalds count = overflow; 2081da177e4SLinus Torvalds goto do_more; 2091da177e4SLinus Torvalds } 2101da177e4SLinus Torvalds error_return: 2111da177e4SLinus Torvalds sb->s_dirt = 1; 2121da177e4SLinus Torvalds if (UDF_SB_LVIDBH(sb)) 2131da177e4SLinus Torvalds mark_buffer_dirty(UDF_SB_LVIDBH(sb)); 2141e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 2151da177e4SLinus Torvalds return; 2161da177e4SLinus Torvalds } 2171da177e4SLinus Torvalds 2181da177e4SLinus Torvalds static int udf_bitmap_prealloc_blocks(struct super_block * sb, 2191da177e4SLinus Torvalds struct inode * inode, 2201da177e4SLinus Torvalds struct udf_bitmap *bitmap, uint16_t partition, uint32_t first_block, 2211da177e4SLinus Torvalds uint32_t block_count) 2221da177e4SLinus Torvalds { 2231da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 2241da177e4SLinus Torvalds int alloc_count = 0; 2251da177e4SLinus Torvalds int bit, block, block_group, group_start; 2261da177e4SLinus Torvalds int nr_groups, bitmap_nr; 2271da177e4SLinus Torvalds struct buffer_head *bh; 2281da177e4SLinus Torvalds 2291e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 2301da177e4SLinus Torvalds if (first_block < 0 || first_block >= UDF_SB_PARTLEN(sb, partition)) 2311da177e4SLinus Torvalds goto out; 2321da177e4SLinus Torvalds 2331da177e4SLinus Torvalds if (first_block + block_count > UDF_SB_PARTLEN(sb, partition)) 2341da177e4SLinus Torvalds block_count = UDF_SB_PARTLEN(sb, partition) - first_block; 2351da177e4SLinus Torvalds 2361da177e4SLinus Torvalds repeat: 2371da177e4SLinus Torvalds nr_groups = (UDF_SB_PARTLEN(sb, partition) + 2381da177e4SLinus Torvalds (sizeof(struct spaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8); 2391da177e4SLinus Torvalds block = first_block + (sizeof(struct spaceBitmapDesc) << 3); 2401da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 2411da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 2421da177e4SLinus Torvalds 2431da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 2441da177e4SLinus Torvalds if (bitmap_nr < 0) 2451da177e4SLinus Torvalds goto out; 2461da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 2471da177e4SLinus Torvalds 2481da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 2491da177e4SLinus Torvalds 2501da177e4SLinus Torvalds while (bit < (sb->s_blocksize << 3) && block_count > 0) 2511da177e4SLinus Torvalds { 2521da177e4SLinus Torvalds if (!udf_test_bit(bit, bh->b_data)) 2531da177e4SLinus Torvalds goto out; 2541da177e4SLinus Torvalds else if (DQUOT_PREALLOC_BLOCK(inode, 1)) 2551da177e4SLinus Torvalds goto out; 2561da177e4SLinus Torvalds else if (!udf_clear_bit(bit, bh->b_data)) 2571da177e4SLinus Torvalds { 2581da177e4SLinus Torvalds udf_debug("bit already cleared for block %d\n", bit); 2591da177e4SLinus Torvalds DQUOT_FREE_BLOCK(inode, 1); 2601da177e4SLinus Torvalds goto out; 2611da177e4SLinus Torvalds } 2621da177e4SLinus Torvalds block_count --; 2631da177e4SLinus Torvalds alloc_count ++; 2641da177e4SLinus Torvalds bit ++; 2651da177e4SLinus Torvalds block ++; 2661da177e4SLinus Torvalds } 2671da177e4SLinus Torvalds mark_buffer_dirty(bh); 2681da177e4SLinus Torvalds if (block_count > 0) 2691da177e4SLinus Torvalds goto repeat; 2701da177e4SLinus Torvalds out: 2711da177e4SLinus Torvalds if (UDF_SB_LVIDBH(sb)) 2721da177e4SLinus Torvalds { 2731da177e4SLinus Torvalds UDF_SB_LVID(sb)->freeSpaceTable[partition] = 2741da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-alloc_count); 2751da177e4SLinus Torvalds mark_buffer_dirty(UDF_SB_LVIDBH(sb)); 2761da177e4SLinus Torvalds } 2771da177e4SLinus Torvalds sb->s_dirt = 1; 2781e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 2791da177e4SLinus Torvalds return alloc_count; 2801da177e4SLinus Torvalds } 2811da177e4SLinus Torvalds 2821da177e4SLinus Torvalds static int udf_bitmap_new_block(struct super_block * sb, 2831da177e4SLinus Torvalds struct inode * inode, 2841da177e4SLinus Torvalds struct udf_bitmap *bitmap, uint16_t partition, uint32_t goal, int *err) 2851da177e4SLinus Torvalds { 2861da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 2871da177e4SLinus Torvalds int newbit, bit=0, block, block_group, group_start; 2881da177e4SLinus Torvalds int end_goal, nr_groups, bitmap_nr, i; 2891da177e4SLinus Torvalds struct buffer_head *bh = NULL; 2901da177e4SLinus Torvalds char *ptr; 2911da177e4SLinus Torvalds int newblock = 0; 2921da177e4SLinus Torvalds 2931da177e4SLinus Torvalds *err = -ENOSPC; 2941e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 2951da177e4SLinus Torvalds 2961da177e4SLinus Torvalds repeat: 2971da177e4SLinus Torvalds if (goal < 0 || goal >= UDF_SB_PARTLEN(sb, partition)) 2981da177e4SLinus Torvalds goal = 0; 2991da177e4SLinus Torvalds 3001da177e4SLinus Torvalds nr_groups = bitmap->s_nr_groups; 3011da177e4SLinus Torvalds block = goal + (sizeof(struct spaceBitmapDesc) << 3); 3021da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 3031da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 3041da177e4SLinus Torvalds 3051da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 3061da177e4SLinus Torvalds if (bitmap_nr < 0) 3071da177e4SLinus Torvalds goto error_return; 3081da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 3091da177e4SLinus Torvalds ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start); 3101da177e4SLinus Torvalds 3111da177e4SLinus Torvalds if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) 3121da177e4SLinus Torvalds { 3131da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 3141da177e4SLinus Torvalds 3151da177e4SLinus Torvalds if (udf_test_bit(bit, bh->b_data)) 3161da177e4SLinus Torvalds { 3171da177e4SLinus Torvalds goto got_block; 3181da177e4SLinus Torvalds } 3191da177e4SLinus Torvalds end_goal = (bit + 63) & ~63; 3201da177e4SLinus Torvalds bit = udf_find_next_one_bit(bh->b_data, end_goal, bit); 3211da177e4SLinus Torvalds if (bit < end_goal) 3221da177e4SLinus Torvalds goto got_block; 3231da177e4SLinus Torvalds ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, sb->s_blocksize - ((bit + 7) >> 3)); 3241da177e4SLinus Torvalds newbit = (ptr - ((char *)bh->b_data)) << 3; 3251da177e4SLinus Torvalds if (newbit < sb->s_blocksize << 3) 3261da177e4SLinus Torvalds { 3271da177e4SLinus Torvalds bit = newbit; 3281da177e4SLinus Torvalds goto search_back; 3291da177e4SLinus Torvalds } 3301da177e4SLinus Torvalds newbit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, bit); 3311da177e4SLinus Torvalds if (newbit < sb->s_blocksize << 3) 3321da177e4SLinus Torvalds { 3331da177e4SLinus Torvalds bit = newbit; 3341da177e4SLinus Torvalds goto got_block; 3351da177e4SLinus Torvalds } 3361da177e4SLinus Torvalds } 3371da177e4SLinus Torvalds 3381da177e4SLinus Torvalds for (i=0; i<(nr_groups*2); i++) 3391da177e4SLinus Torvalds { 3401da177e4SLinus Torvalds block_group ++; 3411da177e4SLinus Torvalds if (block_group >= nr_groups) 3421da177e4SLinus Torvalds block_group = 0; 3431da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 3441da177e4SLinus Torvalds 3451da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 3461da177e4SLinus Torvalds if (bitmap_nr < 0) 3471da177e4SLinus Torvalds goto error_return; 3481da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 3491da177e4SLinus Torvalds if (i < nr_groups) 3501da177e4SLinus Torvalds { 3511da177e4SLinus Torvalds ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start); 3521da177e4SLinus Torvalds if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) 3531da177e4SLinus Torvalds { 3541da177e4SLinus Torvalds bit = (ptr - ((char *)bh->b_data)) << 3; 3551da177e4SLinus Torvalds break; 3561da177e4SLinus Torvalds } 3571da177e4SLinus Torvalds } 3581da177e4SLinus Torvalds else 3591da177e4SLinus Torvalds { 3601da177e4SLinus Torvalds bit = udf_find_next_one_bit((char *)bh->b_data, sb->s_blocksize << 3, group_start << 3); 3611da177e4SLinus Torvalds if (bit < sb->s_blocksize << 3) 3621da177e4SLinus Torvalds break; 3631da177e4SLinus Torvalds } 3641da177e4SLinus Torvalds } 3651da177e4SLinus Torvalds if (i >= (nr_groups*2)) 3661da177e4SLinus Torvalds { 3671e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3681da177e4SLinus Torvalds return newblock; 3691da177e4SLinus Torvalds } 3701da177e4SLinus Torvalds if (bit < sb->s_blocksize << 3) 3711da177e4SLinus Torvalds goto search_back; 3721da177e4SLinus Torvalds else 3731da177e4SLinus Torvalds bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, group_start << 3); 3741da177e4SLinus Torvalds if (bit >= sb->s_blocksize << 3) 3751da177e4SLinus Torvalds { 3761e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3771da177e4SLinus Torvalds return 0; 3781da177e4SLinus Torvalds } 3791da177e4SLinus Torvalds 3801da177e4SLinus Torvalds search_back: 3811da177e4SLinus Torvalds for (i=0; i<7 && bit > (group_start << 3) && udf_test_bit(bit - 1, bh->b_data); i++, bit--); 3821da177e4SLinus Torvalds 3831da177e4SLinus Torvalds got_block: 3841da177e4SLinus Torvalds 3851da177e4SLinus Torvalds /* 3861da177e4SLinus Torvalds * Check quota for allocation of this block. 3871da177e4SLinus Torvalds */ 3881da177e4SLinus Torvalds if (inode && DQUOT_ALLOC_BLOCK(inode, 1)) 3891da177e4SLinus Torvalds { 3901e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3911da177e4SLinus Torvalds *err = -EDQUOT; 3921da177e4SLinus Torvalds return 0; 3931da177e4SLinus Torvalds } 3941da177e4SLinus Torvalds 3951da177e4SLinus Torvalds newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - 3961da177e4SLinus Torvalds (sizeof(struct spaceBitmapDesc) << 3); 3971da177e4SLinus Torvalds 3981da177e4SLinus Torvalds if (!udf_clear_bit(bit, bh->b_data)) 3991da177e4SLinus Torvalds { 4001da177e4SLinus Torvalds udf_debug("bit already cleared for block %d\n", bit); 4011da177e4SLinus Torvalds goto repeat; 4021da177e4SLinus Torvalds } 4031da177e4SLinus Torvalds 4041da177e4SLinus Torvalds mark_buffer_dirty(bh); 4051da177e4SLinus Torvalds 4061da177e4SLinus Torvalds if (UDF_SB_LVIDBH(sb)) 4071da177e4SLinus Torvalds { 4081da177e4SLinus Torvalds UDF_SB_LVID(sb)->freeSpaceTable[partition] = 4091da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-1); 4101da177e4SLinus Torvalds mark_buffer_dirty(UDF_SB_LVIDBH(sb)); 4111da177e4SLinus Torvalds } 4121da177e4SLinus Torvalds sb->s_dirt = 1; 4131e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 4141da177e4SLinus Torvalds *err = 0; 4151da177e4SLinus Torvalds return newblock; 4161da177e4SLinus Torvalds 4171da177e4SLinus Torvalds error_return: 4181da177e4SLinus Torvalds *err = -EIO; 4191e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 4201da177e4SLinus Torvalds return 0; 4211da177e4SLinus Torvalds } 4221da177e4SLinus Torvalds 4231da177e4SLinus Torvalds static void udf_table_free_blocks(struct super_block * sb, 4241da177e4SLinus Torvalds struct inode * inode, 4251da177e4SLinus Torvalds struct inode * table, 4261da177e4SLinus Torvalds kernel_lb_addr bloc, uint32_t offset, uint32_t count) 4271da177e4SLinus Torvalds { 4281da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 4291da177e4SLinus Torvalds uint32_t start, end; 430ff116fc8SJan Kara uint32_t elen; 431ff116fc8SJan Kara kernel_lb_addr eloc; 432ff116fc8SJan Kara struct extent_position oepos, epos; 4331da177e4SLinus Torvalds int8_t etype; 4341da177e4SLinus Torvalds int i; 4351da177e4SLinus Torvalds 4361e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 4371da177e4SLinus Torvalds if (bloc.logicalBlockNum < 0 || 4381da177e4SLinus Torvalds (bloc.logicalBlockNum + count) > UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum)) 4391da177e4SLinus Torvalds { 4401da177e4SLinus Torvalds udf_debug("%d < %d || %d + %d > %d\n", 4411da177e4SLinus Torvalds bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 4421da177e4SLinus Torvalds UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum)); 4431da177e4SLinus Torvalds goto error_return; 4441da177e4SLinus Torvalds } 4451da177e4SLinus Torvalds 4461da177e4SLinus Torvalds /* We do this up front - There are some error conditions that could occure, 4471da177e4SLinus Torvalds but.. oh well */ 4481da177e4SLinus Torvalds if (inode) 4491da177e4SLinus Torvalds DQUOT_FREE_BLOCK(inode, count); 4501da177e4SLinus Torvalds if (UDF_SB_LVIDBH(sb)) 4511da177e4SLinus Torvalds { 4521da177e4SLinus Torvalds UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)] = 4531da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)])+count); 4541da177e4SLinus Torvalds mark_buffer_dirty(UDF_SB_LVIDBH(sb)); 4551da177e4SLinus Torvalds } 4561da177e4SLinus Torvalds 4571da177e4SLinus Torvalds start = bloc.logicalBlockNum + offset; 4581da177e4SLinus Torvalds end = bloc.logicalBlockNum + offset + count - 1; 4591da177e4SLinus Torvalds 460ff116fc8SJan Kara epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry); 4611da177e4SLinus Torvalds elen = 0; 462ff116fc8SJan Kara epos.block = oepos.block = UDF_I_LOCATION(table); 463ff116fc8SJan Kara epos.bh = oepos.bh = NULL; 4641da177e4SLinus Torvalds 4651da177e4SLinus Torvalds while (count && (etype = 466ff116fc8SJan Kara udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) 4671da177e4SLinus Torvalds { 4681da177e4SLinus Torvalds if (((eloc.logicalBlockNum + (elen >> sb->s_blocksize_bits)) == 4691da177e4SLinus Torvalds start)) 4701da177e4SLinus Torvalds { 4711da177e4SLinus Torvalds if ((0x3FFFFFFF - elen) < (count << sb->s_blocksize_bits)) 4721da177e4SLinus Torvalds { 4731da177e4SLinus Torvalds count -= ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits); 4741da177e4SLinus Torvalds start += ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits); 4751da177e4SLinus Torvalds elen = (etype << 30) | (0x40000000 - sb->s_blocksize); 4761da177e4SLinus Torvalds } 4771da177e4SLinus Torvalds else 4781da177e4SLinus Torvalds { 4791da177e4SLinus Torvalds elen = (etype << 30) | 4801da177e4SLinus Torvalds (elen + (count << sb->s_blocksize_bits)); 4811da177e4SLinus Torvalds start += count; 4821da177e4SLinus Torvalds count = 0; 4831da177e4SLinus Torvalds } 484ff116fc8SJan Kara udf_write_aext(table, &oepos, eloc, elen, 1); 4851da177e4SLinus Torvalds } 4861da177e4SLinus Torvalds else if (eloc.logicalBlockNum == (end + 1)) 4871da177e4SLinus Torvalds { 4881da177e4SLinus Torvalds if ((0x3FFFFFFF - elen) < (count << sb->s_blocksize_bits)) 4891da177e4SLinus Torvalds { 4901da177e4SLinus Torvalds count -= ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits); 4911da177e4SLinus Torvalds end -= ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits); 4921da177e4SLinus Torvalds eloc.logicalBlockNum -= 4931da177e4SLinus Torvalds ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits); 4941da177e4SLinus Torvalds elen = (etype << 30) | (0x40000000 - sb->s_blocksize); 4951da177e4SLinus Torvalds } 4961da177e4SLinus Torvalds else 4971da177e4SLinus Torvalds { 4981da177e4SLinus Torvalds eloc.logicalBlockNum = start; 4991da177e4SLinus Torvalds elen = (etype << 30) | 5001da177e4SLinus Torvalds (elen + (count << sb->s_blocksize_bits)); 5011da177e4SLinus Torvalds end -= count; 5021da177e4SLinus Torvalds count = 0; 5031da177e4SLinus Torvalds } 504ff116fc8SJan Kara udf_write_aext(table, &oepos, eloc, elen, 1); 5051da177e4SLinus Torvalds } 5061da177e4SLinus Torvalds 507ff116fc8SJan Kara if (epos.bh != oepos.bh) 5081da177e4SLinus Torvalds { 5091da177e4SLinus Torvalds i = -1; 510ff116fc8SJan Kara oepos.block = epos.block; 511*3bf25cb4SJan Kara brelse(oepos.bh); 512*3bf25cb4SJan Kara get_bh(epos.bh); 513ff116fc8SJan Kara oepos.bh = epos.bh; 514ff116fc8SJan Kara oepos.offset = 0; 5151da177e4SLinus Torvalds } 5161da177e4SLinus Torvalds else 517ff116fc8SJan Kara oepos.offset = epos.offset; 5181da177e4SLinus Torvalds } 5191da177e4SLinus Torvalds 5201da177e4SLinus Torvalds if (count) 5211da177e4SLinus Torvalds { 5221da177e4SLinus Torvalds /* NOTE: we CANNOT use udf_add_aext here, as it can try to allocate 5231da177e4SLinus Torvalds a new block, and since we hold the super block lock already 5241da177e4SLinus Torvalds very bad things would happen :) 5251da177e4SLinus Torvalds 5261da177e4SLinus Torvalds We copy the behavior of udf_add_aext, but instead of 5271da177e4SLinus Torvalds trying to allocate a new block close to the existing one, 5281da177e4SLinus Torvalds we just steal a block from the extent we are trying to add. 5291da177e4SLinus Torvalds 5301da177e4SLinus Torvalds It would be nice if the blocks were close together, but it 5311da177e4SLinus Torvalds isn't required. 5321da177e4SLinus Torvalds */ 5331da177e4SLinus Torvalds 5341da177e4SLinus Torvalds int adsize; 5351da177e4SLinus Torvalds short_ad *sad = NULL; 5361da177e4SLinus Torvalds long_ad *lad = NULL; 5371da177e4SLinus Torvalds struct allocExtDesc *aed; 5381da177e4SLinus Torvalds 5391da177e4SLinus Torvalds eloc.logicalBlockNum = start; 5401da177e4SLinus Torvalds elen = EXT_RECORDED_ALLOCATED | 5411da177e4SLinus Torvalds (count << sb->s_blocksize_bits); 5421da177e4SLinus Torvalds 5431da177e4SLinus Torvalds if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_SHORT) 5441da177e4SLinus Torvalds adsize = sizeof(short_ad); 5451da177e4SLinus Torvalds else if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_LONG) 5461da177e4SLinus Torvalds adsize = sizeof(long_ad); 5471da177e4SLinus Torvalds else 5481da177e4SLinus Torvalds { 549*3bf25cb4SJan Kara brelse(oepos.bh); 550*3bf25cb4SJan Kara brelse(epos.bh); 5511da177e4SLinus Torvalds goto error_return; 5521da177e4SLinus Torvalds } 5531da177e4SLinus Torvalds 554ff116fc8SJan Kara if (epos.offset + (2 * adsize) > sb->s_blocksize) 5551da177e4SLinus Torvalds { 5561da177e4SLinus Torvalds char *sptr, *dptr; 5571da177e4SLinus Torvalds int loffset; 5581da177e4SLinus Torvalds 559*3bf25cb4SJan Kara brelse(oepos.bh); 560ff116fc8SJan Kara oepos = epos; 5611da177e4SLinus Torvalds 5621da177e4SLinus Torvalds /* Steal a block from the extent being free'd */ 563ff116fc8SJan Kara epos.block.logicalBlockNum = eloc.logicalBlockNum; 5641da177e4SLinus Torvalds eloc.logicalBlockNum ++; 5651da177e4SLinus Torvalds elen -= sb->s_blocksize; 5661da177e4SLinus Torvalds 567ff116fc8SJan Kara if (!(epos.bh = udf_tread(sb, 568ff116fc8SJan Kara udf_get_lb_pblock(sb, epos.block, 0)))) 5691da177e4SLinus Torvalds { 570*3bf25cb4SJan Kara brelse(oepos.bh); 5711da177e4SLinus Torvalds goto error_return; 5721da177e4SLinus Torvalds } 573ff116fc8SJan Kara aed = (struct allocExtDesc *)(epos.bh->b_data); 574ff116fc8SJan Kara aed->previousAllocExtLocation = cpu_to_le32(oepos.block.logicalBlockNum); 575ff116fc8SJan Kara if (epos.offset + adsize > sb->s_blocksize) 5761da177e4SLinus Torvalds { 577ff116fc8SJan Kara loffset = epos.offset; 5781da177e4SLinus Torvalds aed->lengthAllocDescs = cpu_to_le32(adsize); 579ff116fc8SJan Kara sptr = UDF_I_DATA(inode) + epos.offset - 58099603966SKAMBAROV, ZAUR udf_file_entry_alloc_offset(inode) + 58199603966SKAMBAROV, ZAUR UDF_I_LENEATTR(inode) - adsize; 582ff116fc8SJan Kara dptr = epos.bh->b_data + sizeof(struct allocExtDesc); 5831da177e4SLinus Torvalds memcpy(dptr, sptr, adsize); 584ff116fc8SJan Kara epos.offset = sizeof(struct allocExtDesc) + adsize; 5851da177e4SLinus Torvalds } 5861da177e4SLinus Torvalds else 5871da177e4SLinus Torvalds { 588ff116fc8SJan Kara loffset = epos.offset + adsize; 5891da177e4SLinus Torvalds aed->lengthAllocDescs = cpu_to_le32(0); 590ff116fc8SJan Kara sptr = oepos.bh->b_data + epos.offset; 591ff116fc8SJan Kara epos.offset = sizeof(struct allocExtDesc); 5921da177e4SLinus Torvalds 593ff116fc8SJan Kara if (oepos.bh) 5941da177e4SLinus Torvalds { 595ff116fc8SJan Kara aed = (struct allocExtDesc *)oepos.bh->b_data; 5961da177e4SLinus Torvalds aed->lengthAllocDescs = 5971da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(aed->lengthAllocDescs) + adsize); 5981da177e4SLinus Torvalds } 5991da177e4SLinus Torvalds else 6001da177e4SLinus Torvalds { 6011da177e4SLinus Torvalds UDF_I_LENALLOC(table) += adsize; 6021da177e4SLinus Torvalds mark_inode_dirty(table); 6031da177e4SLinus Torvalds } 6041da177e4SLinus Torvalds } 6051da177e4SLinus Torvalds if (UDF_SB_UDFREV(sb) >= 0x0200) 606ff116fc8SJan Kara udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 3, 1, 607ff116fc8SJan Kara epos.block.logicalBlockNum, sizeof(tag)); 6081da177e4SLinus Torvalds else 609ff116fc8SJan Kara udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 2, 1, 610ff116fc8SJan Kara epos.block.logicalBlockNum, sizeof(tag)); 6111da177e4SLinus Torvalds switch (UDF_I_ALLOCTYPE(table)) 6121da177e4SLinus Torvalds { 6131da177e4SLinus Torvalds case ICBTAG_FLAG_AD_SHORT: 6141da177e4SLinus Torvalds { 6151da177e4SLinus Torvalds sad = (short_ad *)sptr; 6161da177e4SLinus Torvalds sad->extLength = cpu_to_le32( 6171da177e4SLinus Torvalds EXT_NEXT_EXTENT_ALLOCDECS | 6181da177e4SLinus Torvalds sb->s_blocksize); 619ff116fc8SJan Kara sad->extPosition = cpu_to_le32(epos.block.logicalBlockNum); 6201da177e4SLinus Torvalds break; 6211da177e4SLinus Torvalds } 6221da177e4SLinus Torvalds case ICBTAG_FLAG_AD_LONG: 6231da177e4SLinus Torvalds { 6241da177e4SLinus Torvalds lad = (long_ad *)sptr; 6251da177e4SLinus Torvalds lad->extLength = cpu_to_le32( 6261da177e4SLinus Torvalds EXT_NEXT_EXTENT_ALLOCDECS | 6271da177e4SLinus Torvalds sb->s_blocksize); 628ff116fc8SJan Kara lad->extLocation = cpu_to_lelb(epos.block); 6291da177e4SLinus Torvalds break; 6301da177e4SLinus Torvalds } 6311da177e4SLinus Torvalds } 632ff116fc8SJan Kara if (oepos.bh) 6331da177e4SLinus Torvalds { 634ff116fc8SJan Kara udf_update_tag(oepos.bh->b_data, loffset); 635ff116fc8SJan Kara mark_buffer_dirty(oepos.bh); 6361da177e4SLinus Torvalds } 6371da177e4SLinus Torvalds else 6381da177e4SLinus Torvalds mark_inode_dirty(table); 6391da177e4SLinus Torvalds } 6401da177e4SLinus Torvalds 6411da177e4SLinus Torvalds if (elen) /* It's possible that stealing the block emptied the extent */ 6421da177e4SLinus Torvalds { 643ff116fc8SJan Kara udf_write_aext(table, &epos, eloc, elen, 1); 6441da177e4SLinus Torvalds 645ff116fc8SJan Kara if (!epos.bh) 6461da177e4SLinus Torvalds { 6471da177e4SLinus Torvalds UDF_I_LENALLOC(table) += adsize; 6481da177e4SLinus Torvalds mark_inode_dirty(table); 6491da177e4SLinus Torvalds } 6501da177e4SLinus Torvalds else 6511da177e4SLinus Torvalds { 652ff116fc8SJan Kara aed = (struct allocExtDesc *)epos.bh->b_data; 6531da177e4SLinus Torvalds aed->lengthAllocDescs = 6541da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(aed->lengthAllocDescs) + adsize); 655ff116fc8SJan Kara udf_update_tag(epos.bh->b_data, epos.offset); 656ff116fc8SJan Kara mark_buffer_dirty(epos.bh); 6571da177e4SLinus Torvalds } 6581da177e4SLinus Torvalds } 6591da177e4SLinus Torvalds } 6601da177e4SLinus Torvalds 661*3bf25cb4SJan Kara brelse(epos.bh); 662*3bf25cb4SJan Kara brelse(oepos.bh); 6631da177e4SLinus Torvalds 6641da177e4SLinus Torvalds error_return: 6651da177e4SLinus Torvalds sb->s_dirt = 1; 6661e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 6671da177e4SLinus Torvalds return; 6681da177e4SLinus Torvalds } 6691da177e4SLinus Torvalds 6701da177e4SLinus Torvalds static int udf_table_prealloc_blocks(struct super_block * sb, 6711da177e4SLinus Torvalds struct inode * inode, 6721da177e4SLinus Torvalds struct inode *table, uint16_t partition, uint32_t first_block, 6731da177e4SLinus Torvalds uint32_t block_count) 6741da177e4SLinus Torvalds { 6751da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 6761da177e4SLinus Torvalds int alloc_count = 0; 677ff116fc8SJan Kara uint32_t elen, adsize; 678ff116fc8SJan Kara kernel_lb_addr eloc; 679ff116fc8SJan Kara struct extent_position epos; 6801da177e4SLinus Torvalds int8_t etype = -1; 6811da177e4SLinus Torvalds 6821da177e4SLinus Torvalds if (first_block < 0 || first_block >= UDF_SB_PARTLEN(sb, partition)) 6831da177e4SLinus Torvalds return 0; 6841da177e4SLinus Torvalds 6851da177e4SLinus Torvalds if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_SHORT) 6861da177e4SLinus Torvalds adsize = sizeof(short_ad); 6871da177e4SLinus Torvalds else if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_LONG) 6881da177e4SLinus Torvalds adsize = sizeof(long_ad); 6891da177e4SLinus Torvalds else 6901da177e4SLinus Torvalds return 0; 6911da177e4SLinus Torvalds 6921e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 693ff116fc8SJan Kara epos.offset = sizeof(struct unallocSpaceEntry); 694ff116fc8SJan Kara epos.block = UDF_I_LOCATION(table); 695ff116fc8SJan Kara epos.bh = NULL; 6961da177e4SLinus Torvalds eloc.logicalBlockNum = 0xFFFFFFFF; 6971da177e4SLinus Torvalds 6981da177e4SLinus Torvalds while (first_block != eloc.logicalBlockNum && (etype = 699ff116fc8SJan Kara udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) 7001da177e4SLinus Torvalds { 7011da177e4SLinus Torvalds udf_debug("eloc=%d, elen=%d, first_block=%d\n", 7021da177e4SLinus Torvalds eloc.logicalBlockNum, elen, first_block); 7031da177e4SLinus Torvalds ; /* empty loop body */ 7041da177e4SLinus Torvalds } 7051da177e4SLinus Torvalds 7061da177e4SLinus Torvalds if (first_block == eloc.logicalBlockNum) 7071da177e4SLinus Torvalds { 708ff116fc8SJan Kara epos.offset -= adsize; 7091da177e4SLinus Torvalds 7101da177e4SLinus Torvalds alloc_count = (elen >> sb->s_blocksize_bits); 7111da177e4SLinus Torvalds if (inode && DQUOT_PREALLOC_BLOCK(inode, alloc_count > block_count ? block_count : alloc_count)) 7121da177e4SLinus Torvalds alloc_count = 0; 7131da177e4SLinus Torvalds else if (alloc_count > block_count) 7141da177e4SLinus Torvalds { 7151da177e4SLinus Torvalds alloc_count = block_count; 7161da177e4SLinus Torvalds eloc.logicalBlockNum += alloc_count; 7171da177e4SLinus Torvalds elen -= (alloc_count << sb->s_blocksize_bits); 718ff116fc8SJan Kara udf_write_aext(table, &epos, eloc, (etype << 30) | elen, 1); 7191da177e4SLinus Torvalds } 7201da177e4SLinus Torvalds else 721ff116fc8SJan Kara udf_delete_aext(table, epos, eloc, (etype << 30) | elen); 7221da177e4SLinus Torvalds } 7231da177e4SLinus Torvalds else 7241da177e4SLinus Torvalds alloc_count = 0; 7251da177e4SLinus Torvalds 726*3bf25cb4SJan Kara brelse(epos.bh); 7271da177e4SLinus Torvalds 7281da177e4SLinus Torvalds if (alloc_count && UDF_SB_LVIDBH(sb)) 7291da177e4SLinus Torvalds { 7301da177e4SLinus Torvalds UDF_SB_LVID(sb)->freeSpaceTable[partition] = 7311da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-alloc_count); 7321da177e4SLinus Torvalds mark_buffer_dirty(UDF_SB_LVIDBH(sb)); 7331da177e4SLinus Torvalds sb->s_dirt = 1; 7341da177e4SLinus Torvalds } 7351e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 7361da177e4SLinus Torvalds return alloc_count; 7371da177e4SLinus Torvalds } 7381da177e4SLinus Torvalds 7391da177e4SLinus Torvalds static int udf_table_new_block(struct super_block * sb, 7401da177e4SLinus Torvalds struct inode * inode, 7411da177e4SLinus Torvalds struct inode *table, uint16_t partition, uint32_t goal, int *err) 7421da177e4SLinus Torvalds { 7431da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 7441da177e4SLinus Torvalds uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; 7451da177e4SLinus Torvalds uint32_t newblock = 0, adsize; 746ff116fc8SJan Kara uint32_t elen, goal_elen = 0; 747ff116fc8SJan Kara kernel_lb_addr eloc, goal_eloc; 748ff116fc8SJan Kara struct extent_position epos, goal_epos; 7491da177e4SLinus Torvalds int8_t etype; 7501da177e4SLinus Torvalds 7511da177e4SLinus Torvalds *err = -ENOSPC; 7521da177e4SLinus Torvalds 7531da177e4SLinus Torvalds if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_SHORT) 7541da177e4SLinus Torvalds adsize = sizeof(short_ad); 7551da177e4SLinus Torvalds else if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_LONG) 7561da177e4SLinus Torvalds adsize = sizeof(long_ad); 7571da177e4SLinus Torvalds else 7581da177e4SLinus Torvalds return newblock; 7591da177e4SLinus Torvalds 7601e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 7611da177e4SLinus Torvalds if (goal < 0 || goal >= UDF_SB_PARTLEN(sb, partition)) 7621da177e4SLinus Torvalds goal = 0; 7631da177e4SLinus Torvalds 7641da177e4SLinus Torvalds /* We search for the closest matching block to goal. If we find a exact hit, 7651da177e4SLinus Torvalds we stop. Otherwise we keep going till we run out of extents. 7661da177e4SLinus Torvalds We store the buffer_head, bloc, and extoffset of the current closest 7671da177e4SLinus Torvalds match and use that when we are done. 7681da177e4SLinus Torvalds */ 769ff116fc8SJan Kara epos.offset = sizeof(struct unallocSpaceEntry); 770ff116fc8SJan Kara epos.block = UDF_I_LOCATION(table); 771ff116fc8SJan Kara epos.bh = goal_epos.bh = NULL; 7721da177e4SLinus Torvalds 7731da177e4SLinus Torvalds while (spread && (etype = 774ff116fc8SJan Kara udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) 7751da177e4SLinus Torvalds { 7761da177e4SLinus Torvalds if (goal >= eloc.logicalBlockNum) 7771da177e4SLinus Torvalds { 7781da177e4SLinus Torvalds if (goal < eloc.logicalBlockNum + (elen >> sb->s_blocksize_bits)) 7791da177e4SLinus Torvalds nspread = 0; 7801da177e4SLinus Torvalds else 7811da177e4SLinus Torvalds nspread = goal - eloc.logicalBlockNum - 7821da177e4SLinus Torvalds (elen >> sb->s_blocksize_bits); 7831da177e4SLinus Torvalds } 7841da177e4SLinus Torvalds else 7851da177e4SLinus Torvalds nspread = eloc.logicalBlockNum - goal; 7861da177e4SLinus Torvalds 7871da177e4SLinus Torvalds if (nspread < spread) 7881da177e4SLinus Torvalds { 7891da177e4SLinus Torvalds spread = nspread; 790ff116fc8SJan Kara if (goal_epos.bh != epos.bh) 7911da177e4SLinus Torvalds { 792*3bf25cb4SJan Kara brelse(goal_epos.bh); 793ff116fc8SJan Kara goal_epos.bh = epos.bh; 794*3bf25cb4SJan Kara get_bh(goal_epos.bh); 7951da177e4SLinus Torvalds } 796ff116fc8SJan Kara goal_epos.block = epos.block; 797ff116fc8SJan Kara goal_epos.offset = epos.offset - adsize; 7981da177e4SLinus Torvalds goal_eloc = eloc; 7991da177e4SLinus Torvalds goal_elen = (etype << 30) | elen; 8001da177e4SLinus Torvalds } 8011da177e4SLinus Torvalds } 8021da177e4SLinus Torvalds 803*3bf25cb4SJan Kara brelse(epos.bh); 8041da177e4SLinus Torvalds 8051da177e4SLinus Torvalds if (spread == 0xFFFFFFFF) 8061da177e4SLinus Torvalds { 807*3bf25cb4SJan Kara brelse(goal_epos.bh); 8081e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8091da177e4SLinus Torvalds return 0; 8101da177e4SLinus Torvalds } 8111da177e4SLinus Torvalds 8121da177e4SLinus Torvalds /* Only allocate blocks from the beginning of the extent. 8131da177e4SLinus Torvalds That way, we only delete (empty) extents, never have to insert an 8141da177e4SLinus Torvalds extent because of splitting */ 8151da177e4SLinus Torvalds /* This works, but very poorly.... */ 8161da177e4SLinus Torvalds 8171da177e4SLinus Torvalds newblock = goal_eloc.logicalBlockNum; 8181da177e4SLinus Torvalds goal_eloc.logicalBlockNum ++; 8191da177e4SLinus Torvalds goal_elen -= sb->s_blocksize; 8201da177e4SLinus Torvalds 8211da177e4SLinus Torvalds if (inode && DQUOT_ALLOC_BLOCK(inode, 1)) 8221da177e4SLinus Torvalds { 823*3bf25cb4SJan Kara brelse(goal_epos.bh); 8241e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8251da177e4SLinus Torvalds *err = -EDQUOT; 8261da177e4SLinus Torvalds return 0; 8271da177e4SLinus Torvalds } 8281da177e4SLinus Torvalds 8291da177e4SLinus Torvalds if (goal_elen) 830ff116fc8SJan Kara udf_write_aext(table, &goal_epos, goal_eloc, goal_elen, 1); 8311da177e4SLinus Torvalds else 832ff116fc8SJan Kara udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); 833*3bf25cb4SJan Kara brelse(goal_epos.bh); 8341da177e4SLinus Torvalds 8351da177e4SLinus Torvalds if (UDF_SB_LVIDBH(sb)) 8361da177e4SLinus Torvalds { 8371da177e4SLinus Torvalds UDF_SB_LVID(sb)->freeSpaceTable[partition] = 8381da177e4SLinus Torvalds cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-1); 8391da177e4SLinus Torvalds mark_buffer_dirty(UDF_SB_LVIDBH(sb)); 8401da177e4SLinus Torvalds } 8411da177e4SLinus Torvalds 8421da177e4SLinus Torvalds sb->s_dirt = 1; 8431e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8441da177e4SLinus Torvalds *err = 0; 8451da177e4SLinus Torvalds return newblock; 8461da177e4SLinus Torvalds } 8471da177e4SLinus Torvalds 8481da177e4SLinus Torvalds inline void udf_free_blocks(struct super_block * sb, 8491da177e4SLinus Torvalds struct inode * inode, 8501da177e4SLinus Torvalds kernel_lb_addr bloc, uint32_t offset, uint32_t count) 8511da177e4SLinus Torvalds { 8521da177e4SLinus Torvalds uint16_t partition = bloc.partitionReferenceNum; 8531da177e4SLinus Torvalds 8541da177e4SLinus Torvalds if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP) 8551da177e4SLinus Torvalds { 8561da177e4SLinus Torvalds return udf_bitmap_free_blocks(sb, inode, 8571da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_bitmap, 8581da177e4SLinus Torvalds bloc, offset, count); 8591da177e4SLinus Torvalds } 8601da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_TABLE) 8611da177e4SLinus Torvalds { 8621da177e4SLinus Torvalds return udf_table_free_blocks(sb, inode, 8631da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_table, 8641da177e4SLinus Torvalds bloc, offset, count); 8651da177e4SLinus Torvalds } 8661da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_BITMAP) 8671da177e4SLinus Torvalds { 8681da177e4SLinus Torvalds return udf_bitmap_free_blocks(sb, inode, 8691da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_bitmap, 8701da177e4SLinus Torvalds bloc, offset, count); 8711da177e4SLinus Torvalds } 8721da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_TABLE) 8731da177e4SLinus Torvalds { 8741da177e4SLinus Torvalds return udf_table_free_blocks(sb, inode, 8751da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_table, 8761da177e4SLinus Torvalds bloc, offset, count); 8771da177e4SLinus Torvalds } 8781da177e4SLinus Torvalds else 8791da177e4SLinus Torvalds return; 8801da177e4SLinus Torvalds } 8811da177e4SLinus Torvalds 8821da177e4SLinus Torvalds inline int udf_prealloc_blocks(struct super_block * sb, 8831da177e4SLinus Torvalds struct inode * inode, 8841da177e4SLinus Torvalds uint16_t partition, uint32_t first_block, uint32_t block_count) 8851da177e4SLinus Torvalds { 8861da177e4SLinus Torvalds if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP) 8871da177e4SLinus Torvalds { 8881da177e4SLinus Torvalds return udf_bitmap_prealloc_blocks(sb, inode, 8891da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_bitmap, 8901da177e4SLinus Torvalds partition, first_block, block_count); 8911da177e4SLinus Torvalds } 8921da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_TABLE) 8931da177e4SLinus Torvalds { 8941da177e4SLinus Torvalds return udf_table_prealloc_blocks(sb, inode, 8951da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_table, 8961da177e4SLinus Torvalds partition, first_block, block_count); 8971da177e4SLinus Torvalds } 8981da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_BITMAP) 8991da177e4SLinus Torvalds { 9001da177e4SLinus Torvalds return udf_bitmap_prealloc_blocks(sb, inode, 9011da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_bitmap, 9021da177e4SLinus Torvalds partition, first_block, block_count); 9031da177e4SLinus Torvalds } 9041da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_TABLE) 9051da177e4SLinus Torvalds { 9061da177e4SLinus Torvalds return udf_table_prealloc_blocks(sb, inode, 9071da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_table, 9081da177e4SLinus Torvalds partition, first_block, block_count); 9091da177e4SLinus Torvalds } 9101da177e4SLinus Torvalds else 9111da177e4SLinus Torvalds return 0; 9121da177e4SLinus Torvalds } 9131da177e4SLinus Torvalds 9141da177e4SLinus Torvalds inline int udf_new_block(struct super_block * sb, 9151da177e4SLinus Torvalds struct inode * inode, 9161da177e4SLinus Torvalds uint16_t partition, uint32_t goal, int *err) 9171da177e4SLinus Torvalds { 918*3bf25cb4SJan Kara int ret; 919*3bf25cb4SJan Kara 9201da177e4SLinus Torvalds if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP) 9211da177e4SLinus Torvalds { 922*3bf25cb4SJan Kara ret = udf_bitmap_new_block(sb, inode, 9231da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_bitmap, 9241da177e4SLinus Torvalds partition, goal, err); 925*3bf25cb4SJan Kara return ret; 9261da177e4SLinus Torvalds } 9271da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_TABLE) 9281da177e4SLinus Torvalds { 9291da177e4SLinus Torvalds return udf_table_new_block(sb, inode, 9301da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_table, 9311da177e4SLinus Torvalds partition, goal, err); 9321da177e4SLinus Torvalds } 9331da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_BITMAP) 9341da177e4SLinus Torvalds { 9351da177e4SLinus Torvalds return udf_bitmap_new_block(sb, inode, 9361da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_bitmap, 9371da177e4SLinus Torvalds partition, goal, err); 9381da177e4SLinus Torvalds } 9391da177e4SLinus Torvalds else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_TABLE) 9401da177e4SLinus Torvalds { 9411da177e4SLinus Torvalds return udf_table_new_block(sb, inode, 9421da177e4SLinus Torvalds UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_table, 9431da177e4SLinus Torvalds partition, goal, err); 9441da177e4SLinus Torvalds } 9451da177e4SLinus Torvalds else 9461da177e4SLinus Torvalds { 9471da177e4SLinus Torvalds *err = -EIO; 9481da177e4SLinus Torvalds return 0; 9491da177e4SLinus Torvalds } 9501da177e4SLinus Torvalds } 951