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; 905ca4e4beSPekka Enberg struct kernel_lb_addr loc; 911da177e4SLinus Torvalds 921da177e4SLinus Torvalds loc.logicalBlockNum = bitmap->s_extPosition; 936c79e987SMarcin Slusarz loc.partitionReferenceNum = UDF_SB(sb)->s_partition; 941da177e4SLinus Torvalds 9597e961fdSPekka Enberg 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 143146bca72SJan Kara static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt) 144742ba02aSMarcin Slusarz { 145146bca72SJan Kara struct udf_sb_info *sbi = UDF_SB(sb); 146742ba02aSMarcin Slusarz struct logicalVolIntegrityDesc *lvid; 147742ba02aSMarcin Slusarz 148146bca72SJan Kara if (!sbi->s_lvid_bh) 149146bca72SJan Kara return; 150742ba02aSMarcin Slusarz 151742ba02aSMarcin Slusarz lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data; 152c2104fdaSmarcin.slusarz@gmail.com le32_add_cpu(&lvid->freeSpaceTable[partition], cnt); 153146bca72SJan Kara udf_updated_lvid(sb); 154742ba02aSMarcin Slusarz } 155742ba02aSMarcin Slusarz 1561da177e4SLinus Torvalds static void udf_bitmap_free_blocks(struct super_block *sb, 1571da177e4SLinus Torvalds struct inode *inode, 1581da177e4SLinus Torvalds struct udf_bitmap *bitmap, 15997e961fdSPekka Enberg struct kernel_lb_addr *bloc, 16097e961fdSPekka Enberg 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; 16597e961fdSPekka Enberg struct udf_part_map *partmap; 1661da177e4SLinus Torvalds unsigned long block; 1671da177e4SLinus Torvalds unsigned long block_group; 1681da177e4SLinus Torvalds unsigned long bit; 1691da177e4SLinus Torvalds unsigned long i; 1701da177e4SLinus Torvalds int bitmap_nr; 1711da177e4SLinus Torvalds unsigned long overflow; 1721da177e4SLinus Torvalds 1731e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 17497e961fdSPekka Enberg partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; 17597e961fdSPekka Enberg if (bloc->logicalBlockNum < 0 || 17697e961fdSPekka Enberg (bloc->logicalBlockNum + count) > 17797e961fdSPekka Enberg partmap->s_partition_len) { 17828de7948SCyrill Gorcunov udf_debug("%d < %d || %d + %d > %d\n", 17997e961fdSPekka Enberg bloc->logicalBlockNum, 0, bloc->logicalBlockNum, 18097e961fdSPekka Enberg count, partmap->s_partition_len); 1811da177e4SLinus Torvalds goto error_return; 1821da177e4SLinus Torvalds } 1831da177e4SLinus Torvalds 18497e961fdSPekka Enberg block = bloc->logicalBlockNum + offset + 1854b11111aSMarcin Slusarz (sizeof(struct spaceBitmapDesc) << 3); 1861da177e4SLinus Torvalds 1874daa1b87SMarcin Slusarz do { 1881da177e4SLinus Torvalds overflow = 0; 1891da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 1901da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 1911da177e4SLinus Torvalds 1921da177e4SLinus Torvalds /* 1931da177e4SLinus Torvalds * Check to see if we are freeing blocks across a group boundary. 1941da177e4SLinus Torvalds */ 195cb00ea35SCyrill Gorcunov if (bit + count > (sb->s_blocksize << 3)) { 1961da177e4SLinus Torvalds overflow = bit + count - (sb->s_blocksize << 3); 1971da177e4SLinus Torvalds count -= overflow; 1981da177e4SLinus Torvalds } 1991da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 2001da177e4SLinus Torvalds if (bitmap_nr < 0) 2011da177e4SLinus Torvalds goto error_return; 2021da177e4SLinus Torvalds 2031da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 204cb00ea35SCyrill Gorcunov for (i = 0; i < count; i++) { 205cb00ea35SCyrill Gorcunov if (udf_set_bit(bit + i, bh->b_data)) { 2061da177e4SLinus Torvalds udf_debug("bit %ld already set\n", bit + i); 2074b11111aSMarcin Slusarz udf_debug("byte=%2x\n", 2084b11111aSMarcin Slusarz ((char *)bh->b_data)[(bit + i) >> 3]); 209cb00ea35SCyrill Gorcunov } else { 2101da177e4SLinus Torvalds if (inode) 211bacfb7c2SJan Kara vfs_dq_free_block(inode, 1); 212146bca72SJan Kara udf_add_free_space(sb, sbi->s_partition, 1); 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds } 2151da177e4SLinus Torvalds mark_buffer_dirty(bh); 216cb00ea35SCyrill Gorcunov if (overflow) { 2171da177e4SLinus Torvalds block += count; 2181da177e4SLinus Torvalds count = overflow; 2191da177e4SLinus Torvalds } 2204daa1b87SMarcin Slusarz } while (overflow); 2214daa1b87SMarcin Slusarz 2221da177e4SLinus Torvalds error_return: 2231e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds 2261da177e4SLinus Torvalds static int udf_bitmap_prealloc_blocks(struct super_block *sb, 2271da177e4SLinus Torvalds struct inode *inode, 228cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, 229cb00ea35SCyrill Gorcunov uint16_t partition, uint32_t first_block, 2301da177e4SLinus Torvalds uint32_t block_count) 2311da177e4SLinus Torvalds { 2321da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 2331da177e4SLinus Torvalds int alloc_count = 0; 2341da177e4SLinus Torvalds int bit, block, block_group, group_start; 2351da177e4SLinus Torvalds int nr_groups, bitmap_nr; 2361da177e4SLinus Torvalds struct buffer_head *bh; 2376c79e987SMarcin Slusarz __u32 part_len; 2381da177e4SLinus Torvalds 2391e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 2406c79e987SMarcin Slusarz part_len = sbi->s_partmaps[partition].s_partition_len; 2416c79e987SMarcin Slusarz if (first_block < 0 || first_block >= part_len) 2421da177e4SLinus Torvalds goto out; 2431da177e4SLinus Torvalds 2446c79e987SMarcin Slusarz if (first_block + block_count > part_len) 2456c79e987SMarcin Slusarz block_count = part_len - first_block; 2461da177e4SLinus Torvalds 2474daa1b87SMarcin Slusarz do { 248883cb9d1SMarcin Slusarz nr_groups = udf_compute_nr_groups(sb, partition); 2491da177e4SLinus Torvalds block = first_block + (sizeof(struct spaceBitmapDesc) << 3); 2501da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 2511da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 2521da177e4SLinus Torvalds 2531da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 2541da177e4SLinus Torvalds if (bitmap_nr < 0) 2551da177e4SLinus Torvalds goto out; 2561da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 2571da177e4SLinus Torvalds 2581da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 2591da177e4SLinus Torvalds 260cb00ea35SCyrill Gorcunov while (bit < (sb->s_blocksize << 3) && block_count > 0) { 2614daa1b87SMarcin Slusarz if (!udf_test_bit(bit, bh->b_data)) 2621da177e4SLinus Torvalds goto out; 263bacfb7c2SJan Kara else if (vfs_dq_prealloc_block(inode, 1)) 2641da177e4SLinus Torvalds goto out; 2654daa1b87SMarcin Slusarz else if (!udf_clear_bit(bit, bh->b_data)) { 2661da177e4SLinus Torvalds udf_debug("bit already cleared for block %d\n", bit); 267bacfb7c2SJan Kara vfs_dq_free_block(inode, 1); 2681da177e4SLinus Torvalds goto out; 2691da177e4SLinus Torvalds } 2701da177e4SLinus Torvalds block_count--; 2711da177e4SLinus Torvalds alloc_count++; 2721da177e4SLinus Torvalds bit++; 2731da177e4SLinus Torvalds block++; 2741da177e4SLinus Torvalds } 2751da177e4SLinus Torvalds mark_buffer_dirty(bh); 2764daa1b87SMarcin Slusarz } while (block_count > 0); 2774daa1b87SMarcin Slusarz 2781da177e4SLinus Torvalds out: 279146bca72SJan Kara udf_add_free_space(sb, partition, -alloc_count); 2801e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 2811da177e4SLinus Torvalds return alloc_count; 2821da177e4SLinus Torvalds } 2831da177e4SLinus Torvalds 2841da177e4SLinus Torvalds static int udf_bitmap_new_block(struct super_block *sb, 2851da177e4SLinus Torvalds struct inode *inode, 286cb00ea35SCyrill Gorcunov struct udf_bitmap *bitmap, uint16_t partition, 287cb00ea35SCyrill Gorcunov uint32_t goal, int *err) 2881da177e4SLinus Torvalds { 2891da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 2901da177e4SLinus Torvalds int newbit, bit = 0, block, block_group, group_start; 2911da177e4SLinus Torvalds int end_goal, nr_groups, bitmap_nr, i; 2921da177e4SLinus Torvalds struct buffer_head *bh = NULL; 2931da177e4SLinus Torvalds char *ptr; 2941da177e4SLinus Torvalds int newblock = 0; 2951da177e4SLinus Torvalds 2961da177e4SLinus Torvalds *err = -ENOSPC; 2971e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 2981da177e4SLinus Torvalds 2991da177e4SLinus Torvalds repeat: 3006c79e987SMarcin Slusarz if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) 3011da177e4SLinus Torvalds goal = 0; 3021da177e4SLinus Torvalds 3031da177e4SLinus Torvalds nr_groups = bitmap->s_nr_groups; 3041da177e4SLinus Torvalds block = goal + (sizeof(struct spaceBitmapDesc) << 3); 3051da177e4SLinus Torvalds block_group = block >> (sb->s_blocksize_bits + 3); 3061da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 3071da177e4SLinus Torvalds 3081da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 3091da177e4SLinus Torvalds if (bitmap_nr < 0) 3101da177e4SLinus Torvalds goto error_return; 3111da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 31228de7948SCyrill Gorcunov ptr = memscan((char *)bh->b_data + group_start, 0xFF, 313cb00ea35SCyrill Gorcunov sb->s_blocksize - group_start); 3141da177e4SLinus Torvalds 315cb00ea35SCyrill Gorcunov if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 3161da177e4SLinus Torvalds bit = block % (sb->s_blocksize << 3); 31728de7948SCyrill Gorcunov if (udf_test_bit(bit, bh->b_data)) 3181da177e4SLinus Torvalds goto got_block; 31928de7948SCyrill Gorcunov 3201da177e4SLinus Torvalds end_goal = (bit + 63) & ~63; 3211da177e4SLinus Torvalds bit = udf_find_next_one_bit(bh->b_data, end_goal, bit); 3221da177e4SLinus Torvalds if (bit < end_goal) 3231da177e4SLinus Torvalds goto got_block; 32428de7948SCyrill Gorcunov 3254b11111aSMarcin Slusarz ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, 3264b11111aSMarcin Slusarz sb->s_blocksize - ((bit + 7) >> 3)); 3271da177e4SLinus Torvalds newbit = (ptr - ((char *)bh->b_data)) << 3; 328cb00ea35SCyrill Gorcunov if (newbit < sb->s_blocksize << 3) { 3291da177e4SLinus Torvalds bit = newbit; 3301da177e4SLinus Torvalds goto search_back; 3311da177e4SLinus Torvalds } 33228de7948SCyrill Gorcunov 3334b11111aSMarcin Slusarz newbit = udf_find_next_one_bit(bh->b_data, 3344b11111aSMarcin Slusarz sb->s_blocksize << 3, bit); 335cb00ea35SCyrill Gorcunov if (newbit < sb->s_blocksize << 3) { 3361da177e4SLinus Torvalds bit = newbit; 3371da177e4SLinus Torvalds goto got_block; 3381da177e4SLinus Torvalds } 3391da177e4SLinus Torvalds } 3401da177e4SLinus Torvalds 341cb00ea35SCyrill Gorcunov for (i = 0; i < (nr_groups * 2); i++) { 3421da177e4SLinus Torvalds block_group++; 3431da177e4SLinus Torvalds if (block_group >= nr_groups) 3441da177e4SLinus Torvalds block_group = 0; 3451da177e4SLinus Torvalds group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 3461da177e4SLinus Torvalds 3471da177e4SLinus Torvalds bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 3481da177e4SLinus Torvalds if (bitmap_nr < 0) 3491da177e4SLinus Torvalds goto error_return; 3501da177e4SLinus Torvalds bh = bitmap->s_block_bitmap[bitmap_nr]; 351cb00ea35SCyrill Gorcunov if (i < nr_groups) { 35228de7948SCyrill Gorcunov ptr = memscan((char *)bh->b_data + group_start, 0xFF, 353cb00ea35SCyrill Gorcunov sb->s_blocksize - group_start); 354cb00ea35SCyrill Gorcunov if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 3551da177e4SLinus Torvalds bit = (ptr - ((char *)bh->b_data)) << 3; 3561da177e4SLinus Torvalds break; 3571da177e4SLinus Torvalds } 358cb00ea35SCyrill Gorcunov } else { 35928de7948SCyrill Gorcunov bit = udf_find_next_one_bit((char *)bh->b_data, 360cb00ea35SCyrill Gorcunov sb->s_blocksize << 3, 361cb00ea35SCyrill Gorcunov group_start << 3); 3621da177e4SLinus Torvalds if (bit < sb->s_blocksize << 3) 3631da177e4SLinus Torvalds break; 3641da177e4SLinus Torvalds } 3651da177e4SLinus Torvalds } 366cb00ea35SCyrill Gorcunov if (i >= (nr_groups * 2)) { 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 3734b11111aSMarcin Slusarz bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, 3744b11111aSMarcin Slusarz group_start << 3); 375cb00ea35SCyrill Gorcunov if (bit >= sb->s_blocksize << 3) { 3761e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3771da177e4SLinus Torvalds return 0; 3781da177e4SLinus Torvalds } 3791da177e4SLinus Torvalds 3801da177e4SLinus Torvalds search_back: 3814b11111aSMarcin Slusarz i = 0; 3824b11111aSMarcin Slusarz while (i < 7 && bit > (group_start << 3) && 3834b11111aSMarcin Slusarz udf_test_bit(bit - 1, bh->b_data)) { 3844b11111aSMarcin Slusarz ++i; 3854b11111aSMarcin Slusarz --bit; 3864b11111aSMarcin Slusarz } 3871da177e4SLinus Torvalds 3881da177e4SLinus Torvalds got_block: 3891da177e4SLinus Torvalds 3901da177e4SLinus Torvalds /* 3911da177e4SLinus Torvalds * Check quota for allocation of this block. 3921da177e4SLinus Torvalds */ 393bacfb7c2SJan Kara if (inode && vfs_dq_alloc_block(inode, 1)) { 3941e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 3951da177e4SLinus Torvalds *err = -EDQUOT; 3961da177e4SLinus Torvalds return 0; 3971da177e4SLinus Torvalds } 3981da177e4SLinus Torvalds 3991da177e4SLinus Torvalds newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - 4001da177e4SLinus Torvalds (sizeof(struct spaceBitmapDesc) << 3); 4011da177e4SLinus Torvalds 402cb00ea35SCyrill Gorcunov if (!udf_clear_bit(bit, bh->b_data)) { 4031da177e4SLinus Torvalds udf_debug("bit already cleared for block %d\n", bit); 4041da177e4SLinus Torvalds goto repeat; 4051da177e4SLinus Torvalds } 4061da177e4SLinus Torvalds 4071da177e4SLinus Torvalds mark_buffer_dirty(bh); 4081da177e4SLinus Torvalds 409146bca72SJan Kara udf_add_free_space(sb, partition, -1); 4101e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 4111da177e4SLinus Torvalds *err = 0; 4121da177e4SLinus Torvalds return newblock; 4131da177e4SLinus Torvalds 4141da177e4SLinus Torvalds error_return: 4151da177e4SLinus Torvalds *err = -EIO; 4161e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 4171da177e4SLinus Torvalds return 0; 4181da177e4SLinus Torvalds } 4191da177e4SLinus Torvalds 4201da177e4SLinus Torvalds static void udf_table_free_blocks(struct super_block *sb, 4211da177e4SLinus Torvalds struct inode *inode, 4221da177e4SLinus Torvalds struct inode *table, 42397e961fdSPekka Enberg struct kernel_lb_addr *bloc, 42497e961fdSPekka Enberg uint32_t offset, 425cb00ea35SCyrill Gorcunov uint32_t count) 4261da177e4SLinus Torvalds { 4271da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 42897e961fdSPekka Enberg struct udf_part_map *partmap; 4291da177e4SLinus Torvalds uint32_t start, end; 430ff116fc8SJan Kara uint32_t elen; 4315ca4e4beSPekka Enberg struct kernel_lb_addr eloc; 432ff116fc8SJan Kara struct extent_position oepos, epos; 4331da177e4SLinus Torvalds int8_t etype; 4341da177e4SLinus Torvalds int i; 43548d6d8ffSMarcin Slusarz struct udf_inode_info *iinfo; 4361da177e4SLinus Torvalds 4371e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 43897e961fdSPekka Enberg partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; 43997e961fdSPekka Enberg if (bloc->logicalBlockNum < 0 || 44097e961fdSPekka Enberg (bloc->logicalBlockNum + count) > 44197e961fdSPekka Enberg partmap->s_partition_len) { 44228de7948SCyrill Gorcunov udf_debug("%d < %d || %d + %d > %d\n", 44328de7948SCyrill Gorcunov bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 44497e961fdSPekka Enberg partmap->s_partition_len); 4451da177e4SLinus Torvalds goto error_return; 4461da177e4SLinus Torvalds } 4471da177e4SLinus Torvalds 44848d6d8ffSMarcin Slusarz iinfo = UDF_I(table); 4494b11111aSMarcin Slusarz /* We do this up front - There are some error conditions that 4504b11111aSMarcin Slusarz could occure, but.. oh well */ 4511da177e4SLinus Torvalds if (inode) 452bacfb7c2SJan Kara vfs_dq_free_block(inode, count); 453146bca72SJan Kara udf_add_free_space(sb, sbi->s_partition, count); 4541da177e4SLinus Torvalds 45597e961fdSPekka Enberg start = bloc->logicalBlockNum + offset; 45697e961fdSPekka Enberg end = bloc->logicalBlockNum + offset + count - 1; 4571da177e4SLinus Torvalds 458ff116fc8SJan Kara epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry); 4591da177e4SLinus Torvalds elen = 0; 46048d6d8ffSMarcin Slusarz epos.block = oepos.block = iinfo->i_location; 461ff116fc8SJan Kara epos.bh = oepos.bh = NULL; 4621da177e4SLinus Torvalds 46328de7948SCyrill Gorcunov while (count && 46428de7948SCyrill Gorcunov (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 4654b11111aSMarcin Slusarz if (((eloc.logicalBlockNum + 4664b11111aSMarcin Slusarz (elen >> sb->s_blocksize_bits)) == start)) { 4674b11111aSMarcin Slusarz if ((0x3FFFFFFF - elen) < 4684b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)) { 4694b11111aSMarcin Slusarz uint32_t tmp = ((0x3FFFFFFF - elen) >> 4704b11111aSMarcin Slusarz sb->s_blocksize_bits); 4714b11111aSMarcin Slusarz count -= tmp; 4724b11111aSMarcin Slusarz start += tmp; 4734b11111aSMarcin Slusarz elen = (etype << 30) | 4744b11111aSMarcin Slusarz (0x40000000 - sb->s_blocksize); 475cb00ea35SCyrill Gorcunov } else { 4764b11111aSMarcin Slusarz elen = (etype << 30) | 4774b11111aSMarcin Slusarz (elen + 4784b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)); 4791da177e4SLinus Torvalds start += count; 4801da177e4SLinus Torvalds count = 0; 4811da177e4SLinus Torvalds } 48297e961fdSPekka Enberg udf_write_aext(table, &oepos, &eloc, elen, 1); 483cb00ea35SCyrill Gorcunov } else if (eloc.logicalBlockNum == (end + 1)) { 4844b11111aSMarcin Slusarz if ((0x3FFFFFFF - elen) < 4854b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)) { 4864b11111aSMarcin Slusarz uint32_t tmp = ((0x3FFFFFFF - elen) >> 4874b11111aSMarcin Slusarz sb->s_blocksize_bits); 4884b11111aSMarcin Slusarz count -= tmp; 4894b11111aSMarcin Slusarz end -= tmp; 4904b11111aSMarcin Slusarz eloc.logicalBlockNum -= tmp; 4914b11111aSMarcin Slusarz elen = (etype << 30) | 4924b11111aSMarcin Slusarz (0x40000000 - sb->s_blocksize); 493cb00ea35SCyrill Gorcunov } else { 4941da177e4SLinus Torvalds eloc.logicalBlockNum = start; 4954b11111aSMarcin Slusarz elen = (etype << 30) | 4964b11111aSMarcin Slusarz (elen + 4974b11111aSMarcin Slusarz (count << sb->s_blocksize_bits)); 4981da177e4SLinus Torvalds end -= count; 4991da177e4SLinus Torvalds count = 0; 5001da177e4SLinus Torvalds } 50197e961fdSPekka Enberg udf_write_aext(table, &oepos, &eloc, elen, 1); 5021da177e4SLinus Torvalds } 5031da177e4SLinus Torvalds 504cb00ea35SCyrill Gorcunov if (epos.bh != oepos.bh) { 5051da177e4SLinus Torvalds i = -1; 506ff116fc8SJan Kara oepos.block = epos.block; 5073bf25cb4SJan Kara brelse(oepos.bh); 5083bf25cb4SJan Kara get_bh(epos.bh); 509ff116fc8SJan Kara oepos.bh = epos.bh; 510ff116fc8SJan Kara oepos.offset = 0; 51128de7948SCyrill Gorcunov } else { 512ff116fc8SJan Kara oepos.offset = epos.offset; 5131da177e4SLinus Torvalds } 51428de7948SCyrill Gorcunov } 5151da177e4SLinus Torvalds 516cb00ea35SCyrill Gorcunov if (count) { 51728de7948SCyrill Gorcunov /* 5184b11111aSMarcin Slusarz * NOTE: we CANNOT use udf_add_aext here, as it can try to 5194b11111aSMarcin Slusarz * allocate a new block, and since we hold the super block 5204b11111aSMarcin Slusarz * lock already very bad things would happen :) 52128de7948SCyrill Gorcunov * 52228de7948SCyrill Gorcunov * We copy the behavior of udf_add_aext, but instead of 52328de7948SCyrill Gorcunov * trying to allocate a new block close to the existing one, 52428de7948SCyrill Gorcunov * we just steal a block from the extent we are trying to add. 52528de7948SCyrill Gorcunov * 52628de7948SCyrill Gorcunov * It would be nice if the blocks were close together, but it 52728de7948SCyrill Gorcunov * isn't required. 5281da177e4SLinus Torvalds */ 5291da177e4SLinus Torvalds 5301da177e4SLinus Torvalds int adsize; 5315ca4e4beSPekka Enberg struct short_ad *sad = NULL; 5325ca4e4beSPekka Enberg struct long_ad *lad = NULL; 5331da177e4SLinus Torvalds struct allocExtDesc *aed; 5341da177e4SLinus Torvalds 5351da177e4SLinus Torvalds eloc.logicalBlockNum = start; 53628de7948SCyrill Gorcunov elen = EXT_RECORDED_ALLOCATED | 53728de7948SCyrill Gorcunov (count << sb->s_blocksize_bits); 5381da177e4SLinus Torvalds 53948d6d8ffSMarcin Slusarz if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 5405ca4e4beSPekka Enberg adsize = sizeof(struct short_ad); 54148d6d8ffSMarcin Slusarz else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 5425ca4e4beSPekka Enberg adsize = sizeof(struct long_ad); 54348d6d8ffSMarcin Slusarz else { 5443bf25cb4SJan Kara brelse(oepos.bh); 5453bf25cb4SJan Kara brelse(epos.bh); 5461da177e4SLinus Torvalds goto error_return; 5471da177e4SLinus Torvalds } 5481da177e4SLinus Torvalds 549cb00ea35SCyrill Gorcunov if (epos.offset + (2 * adsize) > sb->s_blocksize) { 5501da177e4SLinus Torvalds char *sptr, *dptr; 5511da177e4SLinus Torvalds int loffset; 5521da177e4SLinus Torvalds 5533bf25cb4SJan Kara brelse(oepos.bh); 554ff116fc8SJan Kara oepos = epos; 5551da177e4SLinus Torvalds 5561da177e4SLinus Torvalds /* Steal a block from the extent being free'd */ 557ff116fc8SJan Kara epos.block.logicalBlockNum = eloc.logicalBlockNum; 5581da177e4SLinus Torvalds eloc.logicalBlockNum++; 5591da177e4SLinus Torvalds elen -= sb->s_blocksize; 5601da177e4SLinus Torvalds 5614b11111aSMarcin Slusarz epos.bh = udf_tread(sb, 56297e961fdSPekka Enberg udf_get_lb_pblock(sb, &epos.block, 0)); 5634b11111aSMarcin Slusarz if (!epos.bh) { 5643bf25cb4SJan Kara brelse(oepos.bh); 5651da177e4SLinus Torvalds goto error_return; 5661da177e4SLinus Torvalds } 567ff116fc8SJan Kara aed = (struct allocExtDesc *)(epos.bh->b_data); 5684b11111aSMarcin Slusarz aed->previousAllocExtLocation = 5694b11111aSMarcin Slusarz cpu_to_le32(oepos.block.logicalBlockNum); 570cb00ea35SCyrill Gorcunov if (epos.offset + adsize > sb->s_blocksize) { 571ff116fc8SJan Kara loffset = epos.offset; 5721da177e4SLinus Torvalds aed->lengthAllocDescs = cpu_to_le32(adsize); 57348d6d8ffSMarcin Slusarz sptr = iinfo->i_ext.i_data + epos.offset 574c0b34438SMarcin Slusarz - adsize; 5754b11111aSMarcin Slusarz dptr = epos.bh->b_data + 5764b11111aSMarcin Slusarz sizeof(struct allocExtDesc); 5771da177e4SLinus Torvalds memcpy(dptr, sptr, adsize); 5784b11111aSMarcin Slusarz epos.offset = sizeof(struct allocExtDesc) + 5794b11111aSMarcin Slusarz adsize; 580cb00ea35SCyrill Gorcunov } else { 581ff116fc8SJan Kara loffset = epos.offset + adsize; 5821da177e4SLinus Torvalds aed->lengthAllocDescs = cpu_to_le32(0); 583cb00ea35SCyrill Gorcunov if (oepos.bh) { 584f5cc15daSJan Kara sptr = oepos.bh->b_data + epos.offset; 5854b11111aSMarcin Slusarz aed = (struct allocExtDesc *) 5864b11111aSMarcin Slusarz oepos.bh->b_data; 587c2104fdaSmarcin.slusarz@gmail.com le32_add_cpu(&aed->lengthAllocDescs, 5884b11111aSMarcin Slusarz adsize); 589cb00ea35SCyrill Gorcunov } else { 59048d6d8ffSMarcin Slusarz sptr = iinfo->i_ext.i_data + 591c0b34438SMarcin Slusarz epos.offset; 59248d6d8ffSMarcin Slusarz iinfo->i_lenAlloc += adsize; 5931da177e4SLinus Torvalds mark_inode_dirty(table); 5941da177e4SLinus Torvalds } 595f5cc15daSJan Kara epos.offset = sizeof(struct allocExtDesc); 5961da177e4SLinus Torvalds } 5976c79e987SMarcin Slusarz if (sbi->s_udfrev >= 0x0200) 5984b11111aSMarcin Slusarz udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 5994b11111aSMarcin Slusarz 3, 1, epos.block.logicalBlockNum, 6005ca4e4beSPekka Enberg sizeof(struct tag)); 6011da177e4SLinus Torvalds else 6024b11111aSMarcin Slusarz udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 6034b11111aSMarcin Slusarz 2, 1, epos.block.logicalBlockNum, 6045ca4e4beSPekka Enberg sizeof(struct tag)); 60528de7948SCyrill Gorcunov 60648d6d8ffSMarcin Slusarz switch (iinfo->i_alloc_type) { 6071da177e4SLinus Torvalds case ICBTAG_FLAG_AD_SHORT: 6085ca4e4beSPekka Enberg sad = (struct short_ad *)sptr; 60928de7948SCyrill Gorcunov sad->extLength = cpu_to_le32( 61028de7948SCyrill Gorcunov EXT_NEXT_EXTENT_ALLOCDECS | 61128de7948SCyrill Gorcunov sb->s_blocksize); 6124b11111aSMarcin Slusarz sad->extPosition = 6134b11111aSMarcin Slusarz cpu_to_le32(epos.block.logicalBlockNum); 6141da177e4SLinus Torvalds break; 6151da177e4SLinus Torvalds case ICBTAG_FLAG_AD_LONG: 6165ca4e4beSPekka Enberg lad = (struct long_ad *)sptr; 61728de7948SCyrill Gorcunov lad->extLength = cpu_to_le32( 61828de7948SCyrill Gorcunov EXT_NEXT_EXTENT_ALLOCDECS | 61928de7948SCyrill Gorcunov sb->s_blocksize); 6204b11111aSMarcin Slusarz lad->extLocation = 6214b11111aSMarcin Slusarz cpu_to_lelb(epos.block); 6221da177e4SLinus Torvalds break; 6231da177e4SLinus Torvalds } 624cb00ea35SCyrill Gorcunov if (oepos.bh) { 625ff116fc8SJan Kara udf_update_tag(oepos.bh->b_data, loffset); 626ff116fc8SJan Kara mark_buffer_dirty(oepos.bh); 62728de7948SCyrill Gorcunov } else { 6281da177e4SLinus Torvalds mark_inode_dirty(table); 6291da177e4SLinus Torvalds } 63028de7948SCyrill Gorcunov } 6311da177e4SLinus Torvalds 6324b11111aSMarcin Slusarz /* It's possible that stealing the block emptied the extent */ 6334b11111aSMarcin Slusarz if (elen) { 63497e961fdSPekka Enberg udf_write_aext(table, &epos, &eloc, elen, 1); 6351da177e4SLinus Torvalds 636cb00ea35SCyrill Gorcunov if (!epos.bh) { 63748d6d8ffSMarcin Slusarz iinfo->i_lenAlloc += adsize; 6381da177e4SLinus Torvalds mark_inode_dirty(table); 639cb00ea35SCyrill Gorcunov } else { 640ff116fc8SJan Kara aed = (struct allocExtDesc *)epos.bh->b_data; 641c2104fdaSmarcin.slusarz@gmail.com le32_add_cpu(&aed->lengthAllocDescs, adsize); 642ff116fc8SJan Kara udf_update_tag(epos.bh->b_data, epos.offset); 643ff116fc8SJan Kara mark_buffer_dirty(epos.bh); 6441da177e4SLinus Torvalds } 6451da177e4SLinus Torvalds } 6461da177e4SLinus Torvalds } 6471da177e4SLinus Torvalds 6483bf25cb4SJan Kara brelse(epos.bh); 6493bf25cb4SJan Kara brelse(oepos.bh); 6501da177e4SLinus Torvalds 6511da177e4SLinus Torvalds error_return: 6521e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 6531da177e4SLinus Torvalds return; 6541da177e4SLinus Torvalds } 6551da177e4SLinus Torvalds 6561da177e4SLinus Torvalds static int udf_table_prealloc_blocks(struct super_block *sb, 6571da177e4SLinus Torvalds struct inode *inode, 658cb00ea35SCyrill Gorcunov struct inode *table, uint16_t partition, 659cb00ea35SCyrill Gorcunov uint32_t first_block, uint32_t block_count) 6601da177e4SLinus Torvalds { 6611da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 6621da177e4SLinus Torvalds int alloc_count = 0; 663ff116fc8SJan Kara uint32_t elen, adsize; 6645ca4e4beSPekka Enberg struct kernel_lb_addr eloc; 665ff116fc8SJan Kara struct extent_position epos; 6661da177e4SLinus Torvalds int8_t etype = -1; 66748d6d8ffSMarcin Slusarz struct udf_inode_info *iinfo; 6681da177e4SLinus Torvalds 6694b11111aSMarcin Slusarz if (first_block < 0 || 6704b11111aSMarcin Slusarz first_block >= sbi->s_partmaps[partition].s_partition_len) 6711da177e4SLinus Torvalds return 0; 6721da177e4SLinus Torvalds 67348d6d8ffSMarcin Slusarz iinfo = UDF_I(table); 67448d6d8ffSMarcin Slusarz if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 6755ca4e4beSPekka Enberg adsize = sizeof(struct short_ad); 67648d6d8ffSMarcin Slusarz else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 6775ca4e4beSPekka Enberg adsize = sizeof(struct long_ad); 6781da177e4SLinus Torvalds else 6791da177e4SLinus Torvalds return 0; 6801da177e4SLinus Torvalds 6811e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 682ff116fc8SJan Kara epos.offset = sizeof(struct unallocSpaceEntry); 68348d6d8ffSMarcin Slusarz epos.block = iinfo->i_location; 684ff116fc8SJan Kara epos.bh = NULL; 6851da177e4SLinus Torvalds eloc.logicalBlockNum = 0xFFFFFFFF; 6861da177e4SLinus Torvalds 68728de7948SCyrill Gorcunov while (first_block != eloc.logicalBlockNum && 68828de7948SCyrill Gorcunov (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 6891da177e4SLinus Torvalds udf_debug("eloc=%d, elen=%d, first_block=%d\n", 6901da177e4SLinus Torvalds eloc.logicalBlockNum, elen, first_block); 6911da177e4SLinus Torvalds ; /* empty loop body */ 6921da177e4SLinus Torvalds } 6931da177e4SLinus Torvalds 694cb00ea35SCyrill Gorcunov if (first_block == eloc.logicalBlockNum) { 695ff116fc8SJan Kara epos.offset -= adsize; 6961da177e4SLinus Torvalds 6971da177e4SLinus Torvalds alloc_count = (elen >> sb->s_blocksize_bits); 698bacfb7c2SJan Kara if (inode && vfs_dq_prealloc_block(inode, 6994b11111aSMarcin Slusarz alloc_count > block_count ? block_count : alloc_count)) 7001da177e4SLinus Torvalds alloc_count = 0; 7014b11111aSMarcin Slusarz else if (alloc_count > block_count) { 7021da177e4SLinus Torvalds alloc_count = block_count; 7031da177e4SLinus Torvalds eloc.logicalBlockNum += alloc_count; 7041da177e4SLinus Torvalds elen -= (alloc_count << sb->s_blocksize_bits); 70597e961fdSPekka Enberg udf_write_aext(table, &epos, &eloc, 7064b11111aSMarcin Slusarz (etype << 30) | elen, 1); 7074b11111aSMarcin Slusarz } else 7084b11111aSMarcin Slusarz udf_delete_aext(table, epos, eloc, 7094b11111aSMarcin Slusarz (etype << 30) | elen); 71028de7948SCyrill Gorcunov } else { 7111da177e4SLinus Torvalds alloc_count = 0; 71228de7948SCyrill Gorcunov } 7131da177e4SLinus Torvalds 7143bf25cb4SJan Kara brelse(epos.bh); 7151da177e4SLinus Torvalds 716146bca72SJan Kara if (alloc_count) 717146bca72SJan Kara udf_add_free_space(sb, partition, -alloc_count); 7181e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 7191da177e4SLinus Torvalds return alloc_count; 7201da177e4SLinus Torvalds } 7211da177e4SLinus Torvalds 7221da177e4SLinus Torvalds static int udf_table_new_block(struct super_block *sb, 7231da177e4SLinus Torvalds struct inode *inode, 724cb00ea35SCyrill Gorcunov struct inode *table, uint16_t partition, 725cb00ea35SCyrill Gorcunov uint32_t goal, int *err) 7261da177e4SLinus Torvalds { 7271da177e4SLinus Torvalds struct udf_sb_info *sbi = UDF_SB(sb); 7281da177e4SLinus Torvalds uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; 7291da177e4SLinus Torvalds uint32_t newblock = 0, adsize; 730ff116fc8SJan Kara uint32_t elen, goal_elen = 0; 7315ca4e4beSPekka Enberg struct kernel_lb_addr eloc, uninitialized_var(goal_eloc); 732ff116fc8SJan Kara struct extent_position epos, goal_epos; 7331da177e4SLinus Torvalds int8_t etype; 73448d6d8ffSMarcin Slusarz struct udf_inode_info *iinfo = UDF_I(table); 7351da177e4SLinus Torvalds 7361da177e4SLinus Torvalds *err = -ENOSPC; 7371da177e4SLinus Torvalds 73848d6d8ffSMarcin Slusarz if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 7395ca4e4beSPekka Enberg adsize = sizeof(struct short_ad); 74048d6d8ffSMarcin Slusarz else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 7415ca4e4beSPekka Enberg adsize = sizeof(struct long_ad); 7421da177e4SLinus Torvalds else 7431da177e4SLinus Torvalds return newblock; 7441da177e4SLinus Torvalds 7451e7933deSIngo Molnar mutex_lock(&sbi->s_alloc_mutex); 7466c79e987SMarcin Slusarz if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) 7471da177e4SLinus Torvalds goal = 0; 7481da177e4SLinus Torvalds 7494b11111aSMarcin Slusarz /* We search for the closest matching block to goal. If we find 7504b11111aSMarcin Slusarz a exact hit, we stop. Otherwise we keep going till we run out 7514b11111aSMarcin Slusarz of extents. We store the buffer_head, bloc, and extoffset 7524b11111aSMarcin Slusarz of the current closest match and use that when we are done. 7531da177e4SLinus Torvalds */ 754ff116fc8SJan Kara epos.offset = sizeof(struct unallocSpaceEntry); 75548d6d8ffSMarcin Slusarz epos.block = iinfo->i_location; 756ff116fc8SJan Kara epos.bh = goal_epos.bh = NULL; 7571da177e4SLinus Torvalds 75828de7948SCyrill Gorcunov while (spread && 75928de7948SCyrill Gorcunov (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 760cb00ea35SCyrill Gorcunov if (goal >= eloc.logicalBlockNum) { 7614b11111aSMarcin Slusarz if (goal < eloc.logicalBlockNum + 7624b11111aSMarcin Slusarz (elen >> sb->s_blocksize_bits)) 7631da177e4SLinus Torvalds nspread = 0; 7641da177e4SLinus Torvalds else 7651da177e4SLinus Torvalds nspread = goal - eloc.logicalBlockNum - 7661da177e4SLinus Torvalds (elen >> sb->s_blocksize_bits); 76728de7948SCyrill Gorcunov } else { 7681da177e4SLinus Torvalds nspread = eloc.logicalBlockNum - goal; 76928de7948SCyrill Gorcunov } 7701da177e4SLinus Torvalds 771cb00ea35SCyrill Gorcunov if (nspread < spread) { 7721da177e4SLinus Torvalds spread = nspread; 773cb00ea35SCyrill Gorcunov if (goal_epos.bh != epos.bh) { 7743bf25cb4SJan Kara brelse(goal_epos.bh); 775ff116fc8SJan Kara goal_epos.bh = epos.bh; 7763bf25cb4SJan Kara get_bh(goal_epos.bh); 7771da177e4SLinus Torvalds } 778ff116fc8SJan Kara goal_epos.block = epos.block; 779ff116fc8SJan Kara goal_epos.offset = epos.offset - adsize; 7801da177e4SLinus Torvalds goal_eloc = eloc; 7811da177e4SLinus Torvalds goal_elen = (etype << 30) | elen; 7821da177e4SLinus Torvalds } 7831da177e4SLinus Torvalds } 7841da177e4SLinus Torvalds 7853bf25cb4SJan Kara brelse(epos.bh); 7861da177e4SLinus Torvalds 787cb00ea35SCyrill Gorcunov if (spread == 0xFFFFFFFF) { 7883bf25cb4SJan Kara brelse(goal_epos.bh); 7891e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 7901da177e4SLinus Torvalds return 0; 7911da177e4SLinus Torvalds } 7921da177e4SLinus Torvalds 7931da177e4SLinus Torvalds /* Only allocate blocks from the beginning of the extent. 7941da177e4SLinus Torvalds That way, we only delete (empty) extents, never have to insert an 7951da177e4SLinus Torvalds extent because of splitting */ 7961da177e4SLinus Torvalds /* This works, but very poorly.... */ 7971da177e4SLinus Torvalds 7981da177e4SLinus Torvalds newblock = goal_eloc.logicalBlockNum; 7991da177e4SLinus Torvalds goal_eloc.logicalBlockNum++; 8001da177e4SLinus Torvalds goal_elen -= sb->s_blocksize; 8011da177e4SLinus Torvalds 802bacfb7c2SJan Kara if (inode && vfs_dq_alloc_block(inode, 1)) { 8033bf25cb4SJan Kara brelse(goal_epos.bh); 8041e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8051da177e4SLinus Torvalds *err = -EDQUOT; 8061da177e4SLinus Torvalds return 0; 8071da177e4SLinus Torvalds } 8081da177e4SLinus Torvalds 8091da177e4SLinus Torvalds if (goal_elen) 81097e961fdSPekka Enberg udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1); 8111da177e4SLinus Torvalds else 812ff116fc8SJan Kara udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); 8133bf25cb4SJan Kara brelse(goal_epos.bh); 8141da177e4SLinus Torvalds 815146bca72SJan Kara udf_add_free_space(sb, partition, -1); 8161da177e4SLinus Torvalds 8171e7933deSIngo Molnar mutex_unlock(&sbi->s_alloc_mutex); 8181da177e4SLinus Torvalds *err = 0; 8191da177e4SLinus Torvalds return newblock; 8201da177e4SLinus Torvalds } 8211da177e4SLinus Torvalds 82297e961fdSPekka Enberg void udf_free_blocks(struct super_block *sb, struct inode *inode, 82397e961fdSPekka Enberg struct kernel_lb_addr *bloc, uint32_t offset, 824cb00ea35SCyrill Gorcunov uint32_t count) 8251da177e4SLinus Torvalds { 82697e961fdSPekka Enberg uint16_t partition = bloc->partitionReferenceNum; 8276c79e987SMarcin Slusarz struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 8281da177e4SLinus Torvalds 8296c79e987SMarcin Slusarz if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) { 830e650b94aSJan Kara udf_bitmap_free_blocks(sb, inode, map->s_uspace.s_bitmap, 83128de7948SCyrill Gorcunov bloc, offset, count); 8326c79e987SMarcin Slusarz } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) { 833e650b94aSJan Kara udf_table_free_blocks(sb, inode, map->s_uspace.s_table, 83428de7948SCyrill Gorcunov bloc, offset, count); 8356c79e987SMarcin Slusarz } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) { 836e650b94aSJan Kara udf_bitmap_free_blocks(sb, inode, map->s_fspace.s_bitmap, 83728de7948SCyrill Gorcunov bloc, offset, count); 8386c79e987SMarcin Slusarz } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) { 839e650b94aSJan Kara udf_table_free_blocks(sb, inode, map->s_fspace.s_table, 84028de7948SCyrill Gorcunov bloc, offset, count); 8411da177e4SLinus Torvalds } 84228de7948SCyrill Gorcunov } 8431da177e4SLinus Torvalds 8441da177e4SLinus Torvalds inline int udf_prealloc_blocks(struct super_block *sb, 8451da177e4SLinus Torvalds struct inode *inode, 846cb00ea35SCyrill Gorcunov uint16_t partition, uint32_t first_block, 847cb00ea35SCyrill Gorcunov uint32_t block_count) 8481da177e4SLinus Torvalds { 8496c79e987SMarcin Slusarz struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 8506c79e987SMarcin Slusarz 8514b11111aSMarcin Slusarz if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 8521da177e4SLinus Torvalds return udf_bitmap_prealloc_blocks(sb, inode, 8536c79e987SMarcin Slusarz map->s_uspace.s_bitmap, 8544b11111aSMarcin Slusarz partition, first_block, 8554b11111aSMarcin Slusarz block_count); 8564b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 8571da177e4SLinus Torvalds return udf_table_prealloc_blocks(sb, inode, 8586c79e987SMarcin Slusarz map->s_uspace.s_table, 8594b11111aSMarcin Slusarz partition, first_block, 8604b11111aSMarcin Slusarz block_count); 8614b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 8621da177e4SLinus Torvalds return udf_bitmap_prealloc_blocks(sb, inode, 8636c79e987SMarcin Slusarz map->s_fspace.s_bitmap, 8644b11111aSMarcin Slusarz partition, first_block, 8654b11111aSMarcin Slusarz block_count); 8664b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 8671da177e4SLinus Torvalds return udf_table_prealloc_blocks(sb, inode, 8686c79e987SMarcin Slusarz map->s_fspace.s_table, 8694b11111aSMarcin Slusarz partition, first_block, 8704b11111aSMarcin Slusarz block_count); 8714b11111aSMarcin Slusarz else 8721da177e4SLinus Torvalds return 0; 8731da177e4SLinus Torvalds } 8741da177e4SLinus Torvalds 8751da177e4SLinus Torvalds inline int udf_new_block(struct super_block *sb, 8761da177e4SLinus Torvalds struct inode *inode, 8771da177e4SLinus Torvalds uint16_t partition, uint32_t goal, int *err) 8781da177e4SLinus Torvalds { 8796c79e987SMarcin Slusarz struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 8803bf25cb4SJan Kara 8814b11111aSMarcin Slusarz if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 8824b11111aSMarcin Slusarz return udf_bitmap_new_block(sb, inode, 8836c79e987SMarcin Slusarz map->s_uspace.s_bitmap, 88428de7948SCyrill Gorcunov partition, goal, err); 8854b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 8861da177e4SLinus Torvalds return udf_table_new_block(sb, inode, 8876c79e987SMarcin Slusarz map->s_uspace.s_table, 88828de7948SCyrill Gorcunov partition, goal, err); 8894b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 8901da177e4SLinus Torvalds return udf_bitmap_new_block(sb, inode, 8916c79e987SMarcin Slusarz map->s_fspace.s_bitmap, 89228de7948SCyrill Gorcunov partition, goal, err); 8934b11111aSMarcin Slusarz else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 8941da177e4SLinus Torvalds return udf_table_new_block(sb, inode, 8956c79e987SMarcin Slusarz map->s_fspace.s_table, 89628de7948SCyrill Gorcunov partition, goal, err); 8974b11111aSMarcin Slusarz else { 8981da177e4SLinus Torvalds *err = -EIO; 8991da177e4SLinus Torvalds return 0; 9001da177e4SLinus Torvalds } 9011da177e4SLinus Torvalds } 902