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) 354b11111aSMarcin Slusarz #define udf_find_next_one_bit(addr, size, offset) \ 364b11111aSMarcin Slusarz find_next_one_bit(addr, size, offset) 371da177e4SLinus Torvalds 381da177e4SLinus Torvalds #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x) 391da177e4SLinus Torvalds #define leNUM_to_cpup(x, y) xleNUM_to_cpup(x, y) 401da177e4SLinus Torvalds #define xleNUM_to_cpup(x, y) (le ## x ## _to_cpup(y)) 411da177e4SLinus Torvalds #define uintBPL_t uint(BITS_PER_LONG) 421da177e4SLinus Torvalds #define uint(x) xuint(x) 431da177e4SLinus Torvalds #define xuint(x) __le ## x 441da177e4SLinus Torvalds 45ddc0f846SAdrian Bunk static inline int find_next_one_bit(void *addr, int size, int offset) 461da177e4SLinus Torvalds { 471da177e4SLinus Torvalds uintBPL_t *p = ((uintBPL_t *) addr) + (offset / BITS_PER_LONG); 481da177e4SLinus Torvalds int result = offset & ~(BITS_PER_LONG - 1); 491da177e4SLinus Torvalds unsigned long tmp; 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds if (offset >= size) 521da177e4SLinus Torvalds return size; 531da177e4SLinus Torvalds size -= result; 541da177e4SLinus Torvalds offset &= (BITS_PER_LONG - 1); 55cb00ea35SCyrill Gorcunov if (offset) { 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 } 65cb00ea35SCyrill Gorcunov while (size & ~(BITS_PER_LONG - 1)) { 664b11111aSMarcin Slusarz tmp = leBPL_to_cpup(p++); 674b11111aSMarcin Slusarz if (tmp) 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, 85cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, unsigned int block, 86cb00ea35SCyrill Gorcunov unsigned long bitmap_nr) 871da177e4SLinus Torvalds { 881da177e4SLinus Torvalds struct buffer_head *bh = NULL; 891da177e4SLinus Torvalds int retval = 0; 901da177e4SLinus Torvalds kernel_lb_addr loc; 911da177e4SLinus Torvalds 921da177e4SLinus Torvalds loc.logicalBlockNum = bitmap->s_extPosition; 936c79e987SMarcin Slusarz loc.partitionReferenceNum = UDF_SB(sb)->s_partition; 941da177e4SLinus Torvalds 951da177e4SLinus Torvalds bh = udf_tread(sb, udf_get_lb_pblock(sb, loc, block)); 964b11111aSMarcin Slusarz if (!bh) 971da177e4SLinus Torvalds retval = -EIO; 984b11111aSMarcin Slusarz 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, 104cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, 105cb00ea35SCyrill Gorcunov unsigned int block_group) 1061da177e4SLinus Torvalds { 1071da177e4SLinus Torvalds int retval = 0; 1081da177e4SLinus Torvalds int nr_groups = bitmap->s_nr_groups; 1091da177e4SLinus Torvalds 110cb00ea35SCyrill Gorcunov if (block_group >= nr_groups) { 111cb00ea35SCyrill Gorcunov udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, 112cb00ea35SCyrill Gorcunov nr_groups); 1131da177e4SLinus Torvalds } 1141da177e4SLinus Torvalds 11528de7948SCyrill Gorcunov if (bitmap->s_block_bitmap[block_group]) { 1161da177e4SLinus Torvalds return block_group; 11728de7948SCyrill Gorcunov } else { 11828de7948SCyrill Gorcunov retval = read_block_bitmap(sb, bitmap, block_group, 11928de7948SCyrill Gorcunov block_group); 1201da177e4SLinus Torvalds if (retval < 0) 1211da177e4SLinus Torvalds return retval; 1221da177e4SLinus Torvalds return block_group; 1231da177e4SLinus Torvalds } 1241da177e4SLinus Torvalds } 1251da177e4SLinus Torvalds 1261da177e4SLinus Torvalds static inline int load_block_bitmap(struct super_block *sb, 127cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, 128cb00ea35SCyrill Gorcunov unsigned int block_group) 1291da177e4SLinus Torvalds { 1301da177e4SLinus Torvalds int slot; 1311da177e4SLinus Torvalds 1321da177e4SLinus Torvalds slot = __load_block_bitmap(sb, bitmap, block_group); 1331da177e4SLinus Torvalds 1341da177e4SLinus Torvalds if (slot < 0) 1351da177e4SLinus Torvalds return slot; 1361da177e4SLinus Torvalds 1371da177e4SLinus Torvalds if (!bitmap->s_block_bitmap[slot]) 1381da177e4SLinus Torvalds return -EIO; 1391da177e4SLinus Torvalds 1401da177e4SLinus Torvalds return slot; 1411da177e4SLinus Torvalds } 1421da177e4SLinus Torvalds 143742ba02aSMarcin Slusarz static bool udf_add_free_space(struct udf_sb_info *sbi, 144742ba02aSMarcin Slusarz u16 partition, u32 cnt) 145742ba02aSMarcin Slusarz { 146742ba02aSMarcin Slusarz struct logicalVolIntegrityDesc *lvid; 147742ba02aSMarcin Slusarz 148742ba02aSMarcin Slusarz if (sbi->s_lvid_bh) 149742ba02aSMarcin Slusarz return false; 150742ba02aSMarcin Slusarz 151742ba02aSMarcin Slusarz lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data; 152742ba02aSMarcin Slusarz lvid->freeSpaceTable[partition] = cpu_to_le32(le32_to_cpu( 153742ba02aSMarcin Slusarz lvid->freeSpaceTable[partition]) + cnt); 154742ba02aSMarcin Slusarz return true; 155742ba02aSMarcin Slusarz } 156742ba02aSMarcin Slusarz 1571da177e4SLinus Torvalds static void udf_bitmap_free_blocks(struct super_block *sb, 1581da177e4SLinus Torvalds struct inode *inode, 1591da177e4SLinus Torvalds struct udf_bitmap *bitmap, 160cb00ea35SCyrill Gorcunov kernel_lb_addr bloc, uint32_t offset, 161cb00ea35SCyrill Gorcunov uint32_t count) 1621da177e4SLinus Torvalds { 1631da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 1641da177e4SLinus Torvalds struct buffer_head *bh = NULL; 1651da177e4SLinus Torvalds unsigned long block; 1661da177e4SLinus Torvalds unsigned long block_group; 1671da177e4SLinus Torvalds unsigned long bit; 1681da177e4SLinus Torvalds unsigned long i; 1691da177e4SLinus Torvalds int bitmap_nr; 1701da177e4SLinus Torvalds unsigned long overflow; 1711da177e4SLinus Torvalds 1721e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 1731da177e4SLinus Torvalds if (bloc.logicalBlockNum < 0 || 1744b11111aSMarcin Slusarz (bloc.logicalBlockNum + count) > 1754b11111aSMarcin Slusarz sbi->s_partmaps[bloc.partitionReferenceNum].s_partition_len) { 17628de7948SCyrill Gorcunov udf_debug("%d < %d || %d + %d > %d\n", 17728de7948SCyrill Gorcunov bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 1784b11111aSMarcin Slusarz sbi->s_partmaps[bloc.partitionReferenceNum]. 1794b11111aSMarcin Slusarz s_partition_len); 1801da177e4SLinus Torvalds goto error_return; 1811da177e4SLinus Torvalds } 1821da177e4SLinus Torvalds 1834b11111aSMarcin Slusarz block = bloc.logicalBlockNum + offset + 1844b11111aSMarcin Slusarz (sizeof(struct spaceBitmapDesc) << 3); 1851da177e4SLinus Torvalds 1864daa1b87SMarcin Slusarz do { 1871da177e4SLinus Torvalds overflow = 0; 1881da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 1891da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 1901da177e4SLinus Torvalds 1911da177e4SLinus Torvalds /* 1921da177e4SLinus Torvalds * Check to see if we are freeing blocks across a group boundary. 1931da177e4SLinus Torvalds */ 194cb00ea35SCyrill Gorcunov if (bit + count > (sb->s_blocksize << 3)) { 1951da177e4SLinus Torvalds overflow = bit + count - (sb->s_blocksize << 3); 1961da177e4SLinus Torvalds count -= overflow; 1971da177e4SLinus Torvalds } 1981da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 1991da177e4SLinus Torvalds if (bitmap_nr < 0) 2001da177e4SLinus Torvalds goto error_return; 2011da177e4SLinus Torvalds 2021da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 203cb00ea35SCyrill Gorcunov for (i = 0; i < count; i++) { 204cb00ea35SCyrill Gorcunov if (udf_set_bit(bit + i, bh->b_data)) { 2051da177e4SLinus Torvalds udf_debug("bit %ld already set\n", bit + i); 2064b11111aSMarcin Slusarz udf_debug("byte=%2x\n", 2074b11111aSMarcin Slusarz ((char *)bh->b_data)[(bit + i) >> 3]); 208cb00ea35SCyrill Gorcunov } else { 2091da177e4SLinus Torvalds if (inode) 2101da177e4SLinus Torvalds DQUOT_FREE_BLOCK(inode, 1); 211742ba02aSMarcin Slusarz udf_add_free_space(sbi, sbi->s_partition, 1); 2121da177e4SLinus Torvalds } 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds mark_buffer_dirty(bh); 215cb00ea35SCyrill Gorcunov if (overflow) { 2161da177e4SLinus Torvalds block += count; 2171da177e4SLinus Torvalds count = overflow; 2181da177e4SLinus Torvalds } 2194daa1b87SMarcin Slusarz } while (overflow); 2204daa1b87SMarcin Slusarz 2211da177e4SLinus Torvalds error_return: 2221da177e4SLinus Torvalds sb->s_dirt = 1; 2236c79e987SMarcin Slusarz if (sbi->s_lvid_bh) 2246c79e987SMarcin Slusarz mark_buffer_dirty(sbi->s_lvid_bh); 2251e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 2261da177e4SLinus Torvalds } 2271da177e4SLinus Torvalds 2281da177e4SLinus Torvalds static int udf_bitmap_prealloc_blocks(struct super_block *sb, 2291da177e4SLinus Torvalds struct inode *inode, 230cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, 231cb00ea35SCyrill Gorcunov uint16_t partition, uint32_t first_block, 2321da177e4SLinus Torvalds uint32_t block_count) 2331da177e4SLinus Torvalds { 2341da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 2351da177e4SLinus Torvalds int alloc_count = 0; 2361da177e4SLinus Torvalds int bit, block, block_group, group_start; 2371da177e4SLinus Torvalds int nr_groups, bitmap_nr; 2381da177e4SLinus Torvalds struct buffer_head *bh; 2396c79e987SMarcin Slusarz __u32 part_len; 2401da177e4SLinus Torvalds 2411e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 2426c79e987SMarcin Slusarz part_len = sbi->s_partmaps[partition].s_partition_len; 2436c79e987SMarcin Slusarz if (first_block < 0 || first_block >= part_len) 2441da177e4SLinus Torvalds goto out; 2451da177e4SLinus Torvalds 2466c79e987SMarcin Slusarz if (first_block + block_count > part_len) 2476c79e987SMarcin Slusarz block_count = part_len - first_block; 2481da177e4SLinus Torvalds 2494daa1b87SMarcin Slusarz do { 250883cb9d1SMarcin Slusarz nr_groups = udf_compute_nr_groups(sb, partition); 2511da177e4SLinus Torvalds block = first_block + (sizeof(struct spaceBitmapDesc) << 3); 2521da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 2531da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 2541da177e4SLinus Torvalds 2551da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 2561da177e4SLinus Torvalds if (bitmap_nr < 0) 2571da177e4SLinus Torvalds goto out; 2581da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 2591da177e4SLinus Torvalds 2601da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 2611da177e4SLinus Torvalds 262cb00ea35SCyrill Gorcunov while (bit < (sb->s_blocksize << 3) && block_count > 0) { 2634daa1b87SMarcin Slusarz if (!udf_test_bit(bit, bh->b_data)) 2641da177e4SLinus Torvalds goto out; 2654daa1b87SMarcin Slusarz else if (DQUOT_PREALLOC_BLOCK(inode, 1)) 2661da177e4SLinus Torvalds goto out; 2674daa1b87SMarcin Slusarz else if (!udf_clear_bit(bit, bh->b_data)) { 2681da177e4SLinus Torvalds udf_debug("bit already cleared for block %d\n", bit); 2691da177e4SLinus Torvalds DQUOT_FREE_BLOCK(inode, 1); 2701da177e4SLinus Torvalds goto out; 2711da177e4SLinus Torvalds } 2721da177e4SLinus Torvalds block_count--; 2731da177e4SLinus Torvalds alloc_count++; 2741da177e4SLinus Torvalds bit++; 2751da177e4SLinus Torvalds block++; 2761da177e4SLinus Torvalds } 2771da177e4SLinus Torvalds mark_buffer_dirty(bh); 2784daa1b87SMarcin Slusarz } while (block_count > 0); 2794daa1b87SMarcin Slusarz 2801da177e4SLinus Torvalds out: 281742ba02aSMarcin Slusarz if (udf_add_free_space(sbi, partition, -alloc_count)) 2826c79e987SMarcin Slusarz mark_buffer_dirty(sbi->s_lvid_bh); 2831da177e4SLinus Torvalds sb->s_dirt = 1; 2841e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 2851da177e4SLinus Torvalds return alloc_count; 2861da177e4SLinus Torvalds } 2871da177e4SLinus Torvalds 2881da177e4SLinus Torvalds static int udf_bitmap_new_block(struct super_block *sb, 2891da177e4SLinus Torvalds struct inode *inode, 290cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, uint16_t partition, 291cb00ea35SCyrill Gorcunov uint32_t goal, int *err) 2921da177e4SLinus Torvalds { 2931da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 2941da177e4SLinus Torvalds int newbit, bit = 0, block, block_group, group_start; 2951da177e4SLinus Torvalds int end_goal, nr_groups, bitmap_nr, i; 2961da177e4SLinus Torvalds struct buffer_head *bh = NULL; 2971da177e4SLinus Torvalds char *ptr; 2981da177e4SLinus Torvalds int newblock = 0; 2991da177e4SLinus Torvalds 3001da177e4SLinus Torvalds *err = -ENOSPC; 3011e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 3021da177e4SLinus Torvalds 3031da177e4SLinus Torvalds repeat: 3046c79e987SMarcin Slusarz if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) 3051da177e4SLinus Torvalds goal = 0; 3061da177e4SLinus Torvalds 3071da177e4SLinus Torvalds nr_groups = bitmap->s_nr_groups; 3081da177e4SLinus Torvalds block = goal + (sizeof(struct spaceBitmapDesc) << 3); 3091da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 3101da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 3111da177e4SLinus Torvalds 3121da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 3131da177e4SLinus Torvalds if (bitmap_nr < 0) 3141da177e4SLinus Torvalds goto error_return; 3151da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 31628de7948SCyrill Gorcunov ptr = memscan((char *)bh->b_data + group_start, 0xFF, 317cb00ea35SCyrill Gorcunov sb->s_blocksize - group_start); 3181da177e4SLinus Torvalds 319cb00ea35SCyrill Gorcunov if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 3201da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 32128de7948SCyrill Gorcunov if (udf_test_bit(bit, bh->b_data)) 3221da177e4SLinus Torvalds goto got_block; 32328de7948SCyrill Gorcunov 3241da177e4SLinus Torvalds end_goal = (bit + 63) & ~63; 3251da177e4SLinus Torvalds bit = udf_find_next_one_bit(bh->b_data, end_goal, bit); 3261da177e4SLinus Torvalds if (bit < end_goal) 3271da177e4SLinus Torvalds goto got_block; 32828de7948SCyrill Gorcunov 3294b11111aSMarcin Slusarz ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, 3304b11111aSMarcin Slusarz sb->s_blocksize - ((bit + 7) >> 3)); 3311da177e4SLinus Torvalds newbit = (ptr - ((char *)bh->b_data)) << 3; 332cb00ea35SCyrill Gorcunov if (newbit < sb->s_blocksize << 3) { 3331da177e4SLinus Torvalds bit = newbit; 3341da177e4SLinus Torvalds goto search_back; 3351da177e4SLinus Torvalds } 33628de7948SCyrill Gorcunov 3374b11111aSMarcin Slusarz newbit = udf_find_next_one_bit(bh->b_data, 3384b11111aSMarcin Slusarz sb->s_blocksize << 3, bit); 339cb00ea35SCyrill Gorcunov if (newbit < sb->s_blocksize << 3) { 3401da177e4SLinus Torvalds bit = newbit; 3411da177e4SLinus Torvalds goto got_block; 3421da177e4SLinus Torvalds } 3431da177e4SLinus Torvalds } 3441da177e4SLinus Torvalds 345cb00ea35SCyrill Gorcunov for (i = 0; i < (nr_groups * 2); i++) { 3461da177e4SLinus Torvalds block_group++; 3471da177e4SLinus Torvalds if (block_group >= nr_groups) 3481da177e4SLinus Torvalds block_group = 0; 3491da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 3501da177e4SLinus Torvalds 3511da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 3521da177e4SLinus Torvalds if (bitmap_nr < 0) 3531da177e4SLinus Torvalds goto error_return; 3541da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 355cb00ea35SCyrill Gorcunov if (i < nr_groups) { 35628de7948SCyrill Gorcunov ptr = memscan((char *)bh->b_data + group_start, 0xFF, 357cb00ea35SCyrill Gorcunov sb->s_blocksize - group_start); 358cb00ea35SCyrill Gorcunov if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 3591da177e4SLinus Torvalds bit = (ptr - ((char *)bh->b_data)) << 3; 3601da177e4SLinus Torvalds break; 3611da177e4SLinus Torvalds } 362cb00ea35SCyrill Gorcunov } else { 36328de7948SCyrill Gorcunov bit = udf_find_next_one_bit((char *)bh->b_data, 364cb00ea35SCyrill Gorcunov sb->s_blocksize << 3, 365cb00ea35SCyrill Gorcunov group_start << 3); 3661da177e4SLinus Torvalds if (bit < sb->s_blocksize << 3) 3671da177e4SLinus Torvalds break; 3681da177e4SLinus Torvalds } 3691da177e4SLinus Torvalds } 370cb00ea35SCyrill Gorcunov if (i >= (nr_groups * 2)) { 3711e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3721da177e4SLinus Torvalds return newblock; 3731da177e4SLinus Torvalds } 3741da177e4SLinus Torvalds if (bit < sb->s_blocksize << 3) 3751da177e4SLinus Torvalds goto search_back; 3761da177e4SLinus Torvalds else 3774b11111aSMarcin Slusarz bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, 3784b11111aSMarcin Slusarz group_start << 3); 379cb00ea35SCyrill Gorcunov if (bit >= sb->s_blocksize << 3) { 3801e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3811da177e4SLinus Torvalds return 0; 3821da177e4SLinus Torvalds } 3831da177e4SLinus Torvalds 3841da177e4SLinus Torvalds search_back: 3854b11111aSMarcin Slusarz i = 0; 3864b11111aSMarcin Slusarz while (i < 7 && bit > (group_start << 3) && 3874b11111aSMarcin Slusarz udf_test_bit(bit - 1, bh->b_data)) { 3884b11111aSMarcin Slusarz ++i; 3894b11111aSMarcin Slusarz --bit; 3904b11111aSMarcin Slusarz } 3911da177e4SLinus Torvalds 3921da177e4SLinus Torvalds got_block: 3931da177e4SLinus Torvalds 3941da177e4SLinus Torvalds /* 3951da177e4SLinus Torvalds * Check quota for allocation of this block. 3961da177e4SLinus Torvalds */ 397cb00ea35SCyrill Gorcunov if (inode && DQUOT_ALLOC_BLOCK(inode, 1)) { 3981e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3991da177e4SLinus Torvalds *err = -EDQUOT; 4001da177e4SLinus Torvalds return 0; 4011da177e4SLinus Torvalds } 4021da177e4SLinus Torvalds 4031da177e4SLinus Torvalds newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - 4041da177e4SLinus Torvalds (sizeof(struct spaceBitmapDesc) << 3); 4051da177e4SLinus Torvalds 406cb00ea35SCyrill Gorcunov if (!udf_clear_bit(bit, bh->b_data)) { 4071da177e4SLinus Torvalds udf_debug("bit already cleared for block %d\n", bit); 4081da177e4SLinus Torvalds goto repeat; 4091da177e4SLinus Torvalds } 4101da177e4SLinus Torvalds 4111da177e4SLinus Torvalds mark_buffer_dirty(bh); 4121da177e4SLinus Torvalds 413742ba02aSMarcin Slusarz if (udf_add_free_space(sbi, partition, -1)) 4146c79e987SMarcin Slusarz mark_buffer_dirty(sbi->s_lvid_bh); 4151da177e4SLinus Torvalds sb->s_dirt = 1; 4161e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 4171da177e4SLinus Torvalds *err = 0; 4181da177e4SLinus Torvalds return newblock; 4191da177e4SLinus Torvalds 4201da177e4SLinus Torvalds error_return: 4211da177e4SLinus Torvalds *err = -EIO; 4221e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 4231da177e4SLinus Torvalds return 0; 4241da177e4SLinus Torvalds } 4251da177e4SLinus Torvalds 4261da177e4SLinus Torvalds static void udf_table_free_blocks(struct super_block *sb, 4271da177e4SLinus Torvalds struct inode *inode, 4281da177e4SLinus Torvalds struct inode *table, 429cb00ea35SCyrill Gorcunov kernel_lb_addr bloc, uint32_t offset, 430cb00ea35SCyrill Gorcunov uint32_t count) 4311da177e4SLinus Torvalds { 4321da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 4331da177e4SLinus Torvalds uint32_t start, end; 434ff116fc8SJan Kara uint32_t elen; 435ff116fc8SJan Kara kernel_lb_addr eloc; 436ff116fc8SJan Kara struct extent_position oepos, epos; 4371da177e4SLinus Torvalds int8_t etype; 4381da177e4SLinus Torvalds int i; 43948d6d8ffSMarcin Slusarz struct udf_inode_info *iinfo; 4401da177e4SLinus Torvalds 4411e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 4421da177e4SLinus Torvalds if (bloc.logicalBlockNum < 0 || 4434b11111aSMarcin Slusarz (bloc.logicalBlockNum + count) > 4444b11111aSMarcin Slusarz sbi->s_partmaps[bloc.partitionReferenceNum].s_partition_len) { 44528de7948SCyrill Gorcunov udf_debug("%d < %d || %d + %d > %d\n", 44628de7948SCyrill Gorcunov bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 4474b11111aSMarcin Slusarz sbi->s_partmaps[bloc.partitionReferenceNum]. 4484b11111aSMarcin Slusarz s_partition_len); 4491da177e4SLinus Torvalds goto error_return; 4501da177e4SLinus Torvalds } 4511da177e4SLinus Torvalds 45248d6d8ffSMarcin Slusarz iinfo = UDF_I(table); 4534b11111aSMarcin Slusarz /* We do this up front - There are some error conditions that 4544b11111aSMarcin Slusarz could occure, but.. oh well */ 4551da177e4SLinus Torvalds if (inode) 4561da177e4SLinus Torvalds DQUOT_FREE_BLOCK(inode, count); 457742ba02aSMarcin Slusarz if (udf_add_free_space(sbi, sbi->s_partition, count)) 4586c79e987SMarcin Slusarz mark_buffer_dirty(sbi->s_lvid_bh); 4591da177e4SLinus Torvalds 4601da177e4SLinus Torvalds start = bloc.logicalBlockNum + offset; 4611da177e4SLinus Torvalds end = bloc.logicalBlockNum + offset + count - 1; 4621da177e4SLinus Torvalds 463ff116fc8SJan Kara epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry); 4641da177e4SLinus Torvalds elen = 0; 46548d6d8ffSMarcin Slusarz epos.block = oepos.block = iinfo->i_location; 466ff116fc8SJan Kara epos.bh = oepos.bh = NULL; 4671da177e4SLinus Torvalds 46828de7948SCyrill Gorcunov while (count && 46928de7948SCyrill Gorcunov (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 4704b11111aSMarcin Slusarz if (((eloc.logicalBlockNum + 4714b11111aSMarcin Slusarz (elen >> sb->s_blocksize_bits)) == start)) { 4724b11111aSMarcin Slusarz if ((0x3FFFFFFF - elen) < 4734b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)) { 4744b11111aSMarcin Slusarz uint32_t tmp = ((0x3FFFFFFF - elen) >> 4754b11111aSMarcin Slusarz sb->s_blocksize_bits); 4764b11111aSMarcin Slusarz count -= tmp; 4774b11111aSMarcin Slusarz start += tmp; 4784b11111aSMarcin Slusarz elen = (etype << 30) | 4794b11111aSMarcin Slusarz (0x40000000 - sb->s_blocksize); 480cb00ea35SCyrill Gorcunov } else { 4814b11111aSMarcin Slusarz elen = (etype << 30) | 4824b11111aSMarcin Slusarz (elen + 4834b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)); 4841da177e4SLinus Torvalds start += count; 4851da177e4SLinus Torvalds count = 0; 4861da177e4SLinus Torvalds } 487ff116fc8SJan Kara udf_write_aext(table, &oepos, eloc, elen, 1); 488cb00ea35SCyrill Gorcunov } else if (eloc.logicalBlockNum == (end + 1)) { 4894b11111aSMarcin Slusarz if ((0x3FFFFFFF - elen) < 4904b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)) { 4914b11111aSMarcin Slusarz uint32_t tmp = ((0x3FFFFFFF - elen) >> 4924b11111aSMarcin Slusarz sb->s_blocksize_bits); 4934b11111aSMarcin Slusarz count -= tmp; 4944b11111aSMarcin Slusarz end -= tmp; 4954b11111aSMarcin Slusarz eloc.logicalBlockNum -= tmp; 4964b11111aSMarcin Slusarz elen = (etype << 30) | 4974b11111aSMarcin Slusarz (0x40000000 - sb->s_blocksize); 498cb00ea35SCyrill Gorcunov } else { 4991da177e4SLinus Torvalds eloc.logicalBlockNum = start; 5004b11111aSMarcin Slusarz elen = (etype << 30) | 5014b11111aSMarcin Slusarz (elen + 5024b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)); 5031da177e4SLinus Torvalds end -= count; 5041da177e4SLinus Torvalds count = 0; 5051da177e4SLinus Torvalds } 506ff116fc8SJan Kara udf_write_aext(table, &oepos, eloc, elen, 1); 5071da177e4SLinus Torvalds } 5081da177e4SLinus Torvalds 509cb00ea35SCyrill Gorcunov if (epos.bh != oepos.bh) { 5101da177e4SLinus Torvalds i = -1; 511ff116fc8SJan Kara oepos.block = epos.block; 5123bf25cb4SJan Kara brelse(oepos.bh); 5133bf25cb4SJan Kara get_bh(epos.bh); 514ff116fc8SJan Kara oepos.bh = epos.bh; 515ff116fc8SJan Kara oepos.offset = 0; 51628de7948SCyrill Gorcunov } else { 517ff116fc8SJan Kara oepos.offset = epos.offset; 5181da177e4SLinus Torvalds } 51928de7948SCyrill Gorcunov } 5201da177e4SLinus Torvalds 521cb00ea35SCyrill Gorcunov if (count) { 52228de7948SCyrill Gorcunov /* 5234b11111aSMarcin Slusarz * NOTE: we CANNOT use udf_add_aext here, as it can try to 5244b11111aSMarcin Slusarz * allocate a new block, and since we hold the super block 5254b11111aSMarcin Slusarz * lock already very bad things would happen :) 52628de7948SCyrill Gorcunov * 52728de7948SCyrill Gorcunov * We copy the behavior of udf_add_aext, but instead of 52828de7948SCyrill Gorcunov * trying to allocate a new block close to the existing one, 52928de7948SCyrill Gorcunov * we just steal a block from the extent we are trying to add. 53028de7948SCyrill Gorcunov * 53128de7948SCyrill Gorcunov * It would be nice if the blocks were close together, but it 53228de7948SCyrill Gorcunov * isn't required. 5331da177e4SLinus Torvalds */ 5341da177e4SLinus Torvalds 5351da177e4SLinus Torvalds int adsize; 5361da177e4SLinus Torvalds short_ad *sad = NULL; 5371da177e4SLinus Torvalds long_ad *lad = NULL; 5381da177e4SLinus Torvalds struct allocExtDesc *aed; 5391da177e4SLinus Torvalds 5401da177e4SLinus Torvalds eloc.logicalBlockNum = start; 54128de7948SCyrill Gorcunov elen = EXT_RECORDED_ALLOCATED | 54228de7948SCyrill Gorcunov (count << sb->s_blocksize_bits); 5431da177e4SLinus Torvalds 54448d6d8ffSMarcin Slusarz if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 5451da177e4SLinus Torvalds adsize = sizeof(short_ad); 54648d6d8ffSMarcin Slusarz else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 5471da177e4SLinus Torvalds adsize = sizeof(long_ad); 54848d6d8ffSMarcin Slusarz else { 5493bf25cb4SJan Kara brelse(oepos.bh); 5503bf25cb4SJan Kara brelse(epos.bh); 5511da177e4SLinus Torvalds goto error_return; 5521da177e4SLinus Torvalds } 5531da177e4SLinus Torvalds 554cb00ea35SCyrill Gorcunov if (epos.offset + (2 * adsize) > sb->s_blocksize) { 5551da177e4SLinus Torvalds char *sptr, *dptr; 5561da177e4SLinus Torvalds int loffset; 5571da177e4SLinus Torvalds 5583bf25cb4SJan Kara brelse(oepos.bh); 559ff116fc8SJan Kara oepos = epos; 5601da177e4SLinus Torvalds 5611da177e4SLinus Torvalds /* Steal a block from the extent being free'd */ 562ff116fc8SJan Kara epos.block.logicalBlockNum = eloc.logicalBlockNum; 5631da177e4SLinus Torvalds eloc.logicalBlockNum++; 5641da177e4SLinus Torvalds elen -= sb->s_blocksize; 5651da177e4SLinus Torvalds 5664b11111aSMarcin Slusarz epos.bh = udf_tread(sb, 5674b11111aSMarcin Slusarz udf_get_lb_pblock(sb, epos.block, 0)); 5684b11111aSMarcin Slusarz if (!epos.bh) { 5693bf25cb4SJan Kara brelse(oepos.bh); 5701da177e4SLinus Torvalds goto error_return; 5711da177e4SLinus Torvalds } 572ff116fc8SJan Kara aed = (struct allocExtDesc *)(epos.bh->b_data); 5734b11111aSMarcin Slusarz aed->previousAllocExtLocation = 5744b11111aSMarcin Slusarz cpu_to_le32(oepos.block.logicalBlockNum); 575cb00ea35SCyrill Gorcunov if (epos.offset + adsize > sb->s_blocksize) { 576ff116fc8SJan Kara loffset = epos.offset; 5771da177e4SLinus Torvalds aed->lengthAllocDescs = cpu_to_le32(adsize); 57848d6d8ffSMarcin Slusarz sptr = iinfo->i_ext.i_data + epos.offset 579c0b34438SMarcin Slusarz - adsize; 5804b11111aSMarcin Slusarz dptr = epos.bh->b_data + 5814b11111aSMarcin Slusarz sizeof(struct allocExtDesc); 5821da177e4SLinus Torvalds memcpy(dptr, sptr, adsize); 5834b11111aSMarcin Slusarz epos.offset = sizeof(struct allocExtDesc) + 5844b11111aSMarcin Slusarz adsize; 585cb00ea35SCyrill Gorcunov } else { 586ff116fc8SJan Kara loffset = epos.offset + adsize; 5871da177e4SLinus Torvalds aed->lengthAllocDescs = cpu_to_le32(0); 588cb00ea35SCyrill Gorcunov if (oepos.bh) { 589f5cc15daSJan Kara sptr = oepos.bh->b_data + epos.offset; 5904b11111aSMarcin Slusarz aed = (struct allocExtDesc *) 5914b11111aSMarcin Slusarz oepos.bh->b_data; 5921da177e4SLinus Torvalds aed->lengthAllocDescs = 5934b11111aSMarcin Slusarz cpu_to_le32(le32_to_cpu( 5944b11111aSMarcin Slusarz aed->lengthAllocDescs) + 5954b11111aSMarcin Slusarz adsize); 596cb00ea35SCyrill Gorcunov } else { 59748d6d8ffSMarcin Slusarz sptr = iinfo->i_ext.i_data + 598c0b34438SMarcin Slusarz epos.offset; 59948d6d8ffSMarcin Slusarz iinfo->i_lenAlloc += adsize; 6001da177e4SLinus Torvalds mark_inode_dirty(table); 6011da177e4SLinus Torvalds } 602f5cc15daSJan Kara epos.offset = sizeof(struct allocExtDesc); 6031da177e4SLinus Torvalds } 6046c79e987SMarcin Slusarz if (sbi->s_udfrev >= 0x0200) 6054b11111aSMarcin Slusarz udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 6064b11111aSMarcin Slusarz 3, 1, epos.block.logicalBlockNum, 6074b11111aSMarcin Slusarz sizeof(tag)); 6081da177e4SLinus Torvalds else 6094b11111aSMarcin Slusarz udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 6104b11111aSMarcin Slusarz 2, 1, epos.block.logicalBlockNum, 6114b11111aSMarcin Slusarz sizeof(tag)); 61228de7948SCyrill Gorcunov 61348d6d8ffSMarcin Slusarz switch (iinfo->i_alloc_type) { 6141da177e4SLinus Torvalds case ICBTAG_FLAG_AD_SHORT: 6151da177e4SLinus Torvalds sad = (short_ad *)sptr; 61628de7948SCyrill Gorcunov sad->extLength = cpu_to_le32( 61728de7948SCyrill Gorcunov EXT_NEXT_EXTENT_ALLOCDECS | 61828de7948SCyrill Gorcunov sb->s_blocksize); 6194b11111aSMarcin Slusarz sad->extPosition = 6204b11111aSMarcin Slusarz cpu_to_le32(epos.block.logicalBlockNum); 6211da177e4SLinus Torvalds break; 6221da177e4SLinus Torvalds case ICBTAG_FLAG_AD_LONG: 6231da177e4SLinus Torvalds lad = (long_ad *)sptr; 62428de7948SCyrill Gorcunov lad->extLength = cpu_to_le32( 62528de7948SCyrill Gorcunov EXT_NEXT_EXTENT_ALLOCDECS | 62628de7948SCyrill Gorcunov sb->s_blocksize); 6274b11111aSMarcin Slusarz lad->extLocation = 6284b11111aSMarcin Slusarz cpu_to_lelb(epos.block); 6291da177e4SLinus Torvalds break; 6301da177e4SLinus Torvalds } 631cb00ea35SCyrill Gorcunov if (oepos.bh) { 632ff116fc8SJan Kara udf_update_tag(oepos.bh->b_data, loffset); 633ff116fc8SJan Kara mark_buffer_dirty(oepos.bh); 63428de7948SCyrill Gorcunov } else { 6351da177e4SLinus Torvalds mark_inode_dirty(table); 6361da177e4SLinus Torvalds } 63728de7948SCyrill Gorcunov } 6381da177e4SLinus Torvalds 6394b11111aSMarcin Slusarz /* It's possible that stealing the block emptied the extent */ 6404b11111aSMarcin Slusarz if (elen) { 641ff116fc8SJan Kara udf_write_aext(table, &epos, eloc, elen, 1); 6421da177e4SLinus Torvalds 643cb00ea35SCyrill Gorcunov if (!epos.bh) { 64448d6d8ffSMarcin Slusarz iinfo->i_lenAlloc += adsize; 6451da177e4SLinus Torvalds mark_inode_dirty(table); 646cb00ea35SCyrill Gorcunov } else { 647ff116fc8SJan Kara aed = (struct allocExtDesc *)epos.bh->b_data; 6481da177e4SLinus Torvalds aed->lengthAllocDescs = 6494b11111aSMarcin Slusarz cpu_to_le32(le32_to_cpu( 6504b11111aSMarcin Slusarz aed->lengthAllocDescs) + adsize); 651ff116fc8SJan Kara udf_update_tag(epos.bh->b_data, epos.offset); 652ff116fc8SJan Kara mark_buffer_dirty(epos.bh); 6531da177e4SLinus Torvalds } 6541da177e4SLinus Torvalds } 6551da177e4SLinus Torvalds } 6561da177e4SLinus Torvalds 6573bf25cb4SJan Kara brelse(epos.bh); 6583bf25cb4SJan Kara brelse(oepos.bh); 6591da177e4SLinus Torvalds 6601da177e4SLinus Torvalds error_return: 6611da177e4SLinus Torvalds sb->s_dirt = 1; 6621e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 6631da177e4SLinus Torvalds return; 6641da177e4SLinus Torvalds } 6651da177e4SLinus Torvalds 6661da177e4SLinus Torvalds static int udf_table_prealloc_blocks(struct super_block *sb, 6671da177e4SLinus Torvalds struct inode *inode, 668cb00ea35SCyrill Gorcunov struct inode *table, uint16_t partition, 669cb00ea35SCyrill Gorcunov uint32_t first_block, uint32_t block_count) 6701da177e4SLinus Torvalds { 6711da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 6721da177e4SLinus Torvalds int alloc_count = 0; 673ff116fc8SJan Kara uint32_t elen, adsize; 674ff116fc8SJan Kara kernel_lb_addr eloc; 675ff116fc8SJan Kara struct extent_position epos; 6761da177e4SLinus Torvalds int8_t etype = -1; 67748d6d8ffSMarcin Slusarz struct udf_inode_info *iinfo; 6781da177e4SLinus Torvalds 6794b11111aSMarcin Slusarz if (first_block < 0 || 6804b11111aSMarcin Slusarz first_block >= sbi->s_partmaps[partition].s_partition_len) 6811da177e4SLinus Torvalds return 0; 6821da177e4SLinus Torvalds 68348d6d8ffSMarcin Slusarz iinfo = UDF_I(table); 68448d6d8ffSMarcin Slusarz if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 6851da177e4SLinus Torvalds adsize = sizeof(short_ad); 68648d6d8ffSMarcin Slusarz else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 6871da177e4SLinus Torvalds adsize = sizeof(long_ad); 6881da177e4SLinus Torvalds else 6891da177e4SLinus Torvalds return 0; 6901da177e4SLinus Torvalds 6911e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 692ff116fc8SJan Kara epos.offset = sizeof(struct unallocSpaceEntry); 69348d6d8ffSMarcin Slusarz epos.block = iinfo->i_location; 694ff116fc8SJan Kara epos.bh = NULL; 6951da177e4SLinus Torvalds eloc.logicalBlockNum = 0xFFFFFFFF; 6961da177e4SLinus Torvalds 69728de7948SCyrill Gorcunov while (first_block != eloc.logicalBlockNum && 69828de7948SCyrill Gorcunov (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 6991da177e4SLinus Torvalds udf_debug("eloc=%d, elen=%d, first_block=%d\n", 7001da177e4SLinus Torvalds eloc.logicalBlockNum, elen, first_block); 7011da177e4SLinus Torvalds ; /* empty loop body */ 7021da177e4SLinus Torvalds } 7031da177e4SLinus Torvalds 704cb00ea35SCyrill Gorcunov if (first_block == eloc.logicalBlockNum) { 705ff116fc8SJan Kara epos.offset -= adsize; 7061da177e4SLinus Torvalds 7071da177e4SLinus Torvalds alloc_count = (elen >> sb->s_blocksize_bits); 7084b11111aSMarcin Slusarz if (inode && DQUOT_PREALLOC_BLOCK(inode, 7094b11111aSMarcin Slusarz alloc_count > block_count ? block_count : alloc_count)) 7101da177e4SLinus Torvalds alloc_count = 0; 7114b11111aSMarcin Slusarz else if (alloc_count > block_count) { 7121da177e4SLinus Torvalds alloc_count = block_count; 7131da177e4SLinus Torvalds eloc.logicalBlockNum += alloc_count; 7141da177e4SLinus Torvalds elen -= (alloc_count << sb->s_blocksize_bits); 7154b11111aSMarcin Slusarz udf_write_aext(table, &epos, eloc, 7164b11111aSMarcin Slusarz (etype << 30) | elen, 1); 7174b11111aSMarcin Slusarz } else 7184b11111aSMarcin Slusarz udf_delete_aext(table, epos, eloc, 7194b11111aSMarcin Slusarz (etype << 30) | elen); 72028de7948SCyrill Gorcunov } else { 7211da177e4SLinus Torvalds alloc_count = 0; 72228de7948SCyrill Gorcunov } 7231da177e4SLinus Torvalds 7243bf25cb4SJan Kara brelse(epos.bh); 7251da177e4SLinus Torvalds 726742ba02aSMarcin Slusarz if (alloc_count && udf_add_free_space(sbi, partition, -alloc_count)) { 7276c79e987SMarcin Slusarz mark_buffer_dirty(sbi->s_lvid_bh); 7281da177e4SLinus Torvalds sb->s_dirt = 1; 7291da177e4SLinus Torvalds } 7301e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 7311da177e4SLinus Torvalds return alloc_count; 7321da177e4SLinus Torvalds } 7331da177e4SLinus Torvalds 7341da177e4SLinus Torvalds static int udf_table_new_block(struct super_block *sb, 7351da177e4SLinus Torvalds struct inode *inode, 736cb00ea35SCyrill Gorcunov struct inode *table, uint16_t partition, 737cb00ea35SCyrill Gorcunov uint32_t goal, int *err) 7381da177e4SLinus Torvalds { 7391da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 7401da177e4SLinus Torvalds uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; 7411da177e4SLinus Torvalds uint32_t newblock = 0, adsize; 742ff116fc8SJan Kara uint32_t elen, goal_elen = 0; 7433ad90ec0SWANG Cong kernel_lb_addr eloc, uninitialized_var(goal_eloc); 744ff116fc8SJan Kara struct extent_position epos, goal_epos; 7451da177e4SLinus Torvalds int8_t etype; 74648d6d8ffSMarcin Slusarz struct udf_inode_info *iinfo = UDF_I(table); 7471da177e4SLinus Torvalds 7481da177e4SLinus Torvalds *err = -ENOSPC; 7491da177e4SLinus Torvalds 75048d6d8ffSMarcin Slusarz if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 7511da177e4SLinus Torvalds adsize = sizeof(short_ad); 75248d6d8ffSMarcin Slusarz else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 7531da177e4SLinus Torvalds adsize = sizeof(long_ad); 7541da177e4SLinus Torvalds else 7551da177e4SLinus Torvalds return newblock; 7561da177e4SLinus Torvalds 7571e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 7586c79e987SMarcin Slusarz if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) 7591da177e4SLinus Torvalds goal = 0; 7601da177e4SLinus Torvalds 7614b11111aSMarcin Slusarz /* We search for the closest matching block to goal. If we find 7624b11111aSMarcin Slusarz a exact hit, we stop. Otherwise we keep going till we run out 7634b11111aSMarcin Slusarz of extents. We store the buffer_head, bloc, and extoffset 7644b11111aSMarcin Slusarz of the current closest match and use that when we are done. 7651da177e4SLinus Torvalds */ 766ff116fc8SJan Kara epos.offset = sizeof(struct unallocSpaceEntry); 76748d6d8ffSMarcin Slusarz epos.block = iinfo->i_location; 768ff116fc8SJan Kara epos.bh = goal_epos.bh = NULL; 7691da177e4SLinus Torvalds 77028de7948SCyrill Gorcunov while (spread && 77128de7948SCyrill Gorcunov (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 772cb00ea35SCyrill Gorcunov if (goal >= eloc.logicalBlockNum) { 7734b11111aSMarcin Slusarz if (goal < eloc.logicalBlockNum + 7744b11111aSMarcin Slusarz (elen >> sb->s_blocksize_bits)) 7751da177e4SLinus Torvalds nspread = 0; 7761da177e4SLinus Torvalds else 7771da177e4SLinus Torvalds nspread = goal - eloc.logicalBlockNum - 7781da177e4SLinus Torvalds (elen >> sb->s_blocksize_bits); 77928de7948SCyrill Gorcunov } else { 7801da177e4SLinus Torvalds nspread = eloc.logicalBlockNum - goal; 78128de7948SCyrill Gorcunov } 7821da177e4SLinus Torvalds 783cb00ea35SCyrill Gorcunov if (nspread < spread) { 7841da177e4SLinus Torvalds spread = nspread; 785cb00ea35SCyrill Gorcunov if (goal_epos.bh != epos.bh) { 7863bf25cb4SJan Kara brelse(goal_epos.bh); 787ff116fc8SJan Kara goal_epos.bh = epos.bh; 7883bf25cb4SJan Kara get_bh(goal_epos.bh); 7891da177e4SLinus Torvalds } 790ff116fc8SJan Kara goal_epos.block = epos.block; 791ff116fc8SJan Kara goal_epos.offset = epos.offset - adsize; 7921da177e4SLinus Torvalds goal_eloc = eloc; 7931da177e4SLinus Torvalds goal_elen = (etype << 30) | elen; 7941da177e4SLinus Torvalds } 7951da177e4SLinus Torvalds } 7961da177e4SLinus Torvalds 7973bf25cb4SJan Kara brelse(epos.bh); 7981da177e4SLinus Torvalds 799cb00ea35SCyrill Gorcunov if (spread == 0xFFFFFFFF) { 8003bf25cb4SJan Kara brelse(goal_epos.bh); 8011e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8021da177e4SLinus Torvalds return 0; 8031da177e4SLinus Torvalds } 8041da177e4SLinus Torvalds 8051da177e4SLinus Torvalds /* Only allocate blocks from the beginning of the extent. 8061da177e4SLinus Torvalds That way, we only delete (empty) extents, never have to insert an 8071da177e4SLinus Torvalds extent because of splitting */ 8081da177e4SLinus Torvalds /* This works, but very poorly.... */ 8091da177e4SLinus Torvalds 8101da177e4SLinus Torvalds newblock = goal_eloc.logicalBlockNum; 8111da177e4SLinus Torvalds goal_eloc.logicalBlockNum++; 8121da177e4SLinus Torvalds goal_elen -= sb->s_blocksize; 8131da177e4SLinus Torvalds 814cb00ea35SCyrill Gorcunov if (inode && DQUOT_ALLOC_BLOCK(inode, 1)) { 8153bf25cb4SJan Kara brelse(goal_epos.bh); 8161e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8171da177e4SLinus Torvalds *err = -EDQUOT; 8181da177e4SLinus Torvalds return 0; 8191da177e4SLinus Torvalds } 8201da177e4SLinus Torvalds 8211da177e4SLinus Torvalds if (goal_elen) 822ff116fc8SJan Kara udf_write_aext(table, &goal_epos, goal_eloc, goal_elen, 1); 8231da177e4SLinus Torvalds else 824ff116fc8SJan Kara udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); 8253bf25cb4SJan Kara brelse(goal_epos.bh); 8261da177e4SLinus Torvalds 827742ba02aSMarcin Slusarz if (udf_add_free_space(sbi, partition, -1)) 8286c79e987SMarcin Slusarz mark_buffer_dirty(sbi->s_lvid_bh); 8291da177e4SLinus Torvalds 8301da177e4SLinus Torvalds sb->s_dirt = 1; 8311e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8321da177e4SLinus Torvalds *err = 0; 8331da177e4SLinus Torvalds return newblock; 8341da177e4SLinus Torvalds } 8351da177e4SLinus Torvalds 8361da177e4SLinus Torvalds inline void udf_free_blocks(struct super_block *sb, 8371da177e4SLinus Torvalds struct inode *inode, 838cb00ea35SCyrill Gorcunov kernel_lb_addr bloc, uint32_t offset, 839cb00ea35SCyrill Gorcunov uint32_t count) 8401da177e4SLinus Torvalds { 8411da177e4SLinus Torvalds uint16_t partition = bloc.partitionReferenceNum; 8426c79e987SMarcin Slusarz struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 8431da177e4SLinus Torvalds 8446c79e987SMarcin Slusarz if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) { 8451da177e4SLinus Torvalds return udf_bitmap_free_blocks(sb, inode, 8466c79e987SMarcin Slusarz map->s_uspace.s_bitmap, 84728de7948SCyrill Gorcunov bloc, offset, count); 8486c79e987SMarcin Slusarz } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) { 8491da177e4SLinus Torvalds return udf_table_free_blocks(sb, inode, 8506c79e987SMarcin Slusarz map->s_uspace.s_table, 85128de7948SCyrill Gorcunov bloc, offset, count); 8526c79e987SMarcin Slusarz } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) { 8531da177e4SLinus Torvalds return udf_bitmap_free_blocks(sb, inode, 8546c79e987SMarcin Slusarz map->s_fspace.s_bitmap, 85528de7948SCyrill Gorcunov bloc, offset, count); 8566c79e987SMarcin Slusarz } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) { 8571da177e4SLinus Torvalds return udf_table_free_blocks(sb, inode, 8586c79e987SMarcin Slusarz map->s_fspace.s_table, 85928de7948SCyrill Gorcunov bloc, offset, count); 86028de7948SCyrill Gorcunov } else { 8611da177e4SLinus Torvalds return; 8621da177e4SLinus Torvalds } 86328de7948SCyrill Gorcunov } 8641da177e4SLinus Torvalds 8651da177e4SLinus Torvalds inline int udf_prealloc_blocks(struct super_block *sb, 8661da177e4SLinus Torvalds struct inode *inode, 867cb00ea35SCyrill Gorcunov uint16_t partition, uint32_t first_block, 868cb00ea35SCyrill Gorcunov uint32_t block_count) 8691da177e4SLinus Torvalds { 8706c79e987SMarcin Slusarz struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 8716c79e987SMarcin Slusarz 8724b11111aSMarcin Slusarz if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 8731da177e4SLinus Torvalds return udf_bitmap_prealloc_blocks(sb, inode, 8746c79e987SMarcin Slusarz map->s_uspace.s_bitmap, 8754b11111aSMarcin Slusarz partition, first_block, 8764b11111aSMarcin Slusarz block_count); 8774b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 8781da177e4SLinus Torvalds return udf_table_prealloc_blocks(sb, inode, 8796c79e987SMarcin Slusarz map->s_uspace.s_table, 8804b11111aSMarcin Slusarz partition, first_block, 8814b11111aSMarcin Slusarz block_count); 8824b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 8831da177e4SLinus Torvalds return udf_bitmap_prealloc_blocks(sb, inode, 8846c79e987SMarcin Slusarz map->s_fspace.s_bitmap, 8854b11111aSMarcin Slusarz partition, first_block, 8864b11111aSMarcin Slusarz block_count); 8874b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 8881da177e4SLinus Torvalds return udf_table_prealloc_blocks(sb, inode, 8896c79e987SMarcin Slusarz map->s_fspace.s_table, 8904b11111aSMarcin Slusarz partition, first_block, 8914b11111aSMarcin Slusarz block_count); 8924b11111aSMarcin Slusarz else 8931da177e4SLinus Torvalds return 0; 8941da177e4SLinus Torvalds } 8951da177e4SLinus Torvalds 8961da177e4SLinus Torvalds inline int udf_new_block(struct super_block *sb, 8971da177e4SLinus Torvalds struct inode *inode, 8981da177e4SLinus Torvalds uint16_t partition, uint32_t goal, int *err) 8991da177e4SLinus Torvalds { 9006c79e987SMarcin Slusarz struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 9013bf25cb4SJan Kara 9024b11111aSMarcin Slusarz if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 9034b11111aSMarcin Slusarz return udf_bitmap_new_block(sb, inode, 9046c79e987SMarcin Slusarz map->s_uspace.s_bitmap, 90528de7948SCyrill Gorcunov partition, goal, err); 9064b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 9071da177e4SLinus Torvalds return udf_table_new_block(sb, inode, 9086c79e987SMarcin Slusarz map->s_uspace.s_table, 90928de7948SCyrill Gorcunov partition, goal, err); 9104b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 9111da177e4SLinus Torvalds return udf_bitmap_new_block(sb, inode, 9126c79e987SMarcin Slusarz map->s_fspace.s_bitmap, 91328de7948SCyrill Gorcunov partition, goal, err); 9144b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 9151da177e4SLinus Torvalds return udf_table_new_block(sb, inode, 9166c79e987SMarcin Slusarz map->s_fspace.s_table, 91728de7948SCyrill Gorcunov partition, goal, err); 9184b11111aSMarcin Slusarz else { 9191da177e4SLinus Torvalds *err = -EIO; 9201da177e4SLinus Torvalds return 0; 9211da177e4SLinus Torvalds } 9221da177e4SLinus Torvalds } 923