11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * linux/fs/hpfs/alloc.c 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999 51da177e4SLinus Torvalds * 61da177e4SLinus Torvalds * HPFS bitmap operations 71da177e4SLinus Torvalds */ 81da177e4SLinus Torvalds 91da177e4SLinus Torvalds #include "hpfs_fn.h" 101da177e4SLinus Torvalds 112cbe5c76SMikulas Patocka static void hpfs_claim_alloc(struct super_block *s, secno sec) 122cbe5c76SMikulas Patocka { 132cbe5c76SMikulas Patocka struct hpfs_sb_info *sbi = hpfs_sb(s); 142cbe5c76SMikulas Patocka if (sbi->sb_n_free != (unsigned)-1) { 152cbe5c76SMikulas Patocka if (unlikely(!sbi->sb_n_free)) { 162cbe5c76SMikulas Patocka hpfs_error(s, "free count underflow, allocating sector %08x", sec); 172cbe5c76SMikulas Patocka sbi->sb_n_free = -1; 182cbe5c76SMikulas Patocka return; 192cbe5c76SMikulas Patocka } 202cbe5c76SMikulas Patocka sbi->sb_n_free--; 212cbe5c76SMikulas Patocka } 222cbe5c76SMikulas Patocka } 232cbe5c76SMikulas Patocka 242cbe5c76SMikulas Patocka static void hpfs_claim_free(struct super_block *s, secno sec) 252cbe5c76SMikulas Patocka { 262cbe5c76SMikulas Patocka struct hpfs_sb_info *sbi = hpfs_sb(s); 272cbe5c76SMikulas Patocka if (sbi->sb_n_free != (unsigned)-1) { 282cbe5c76SMikulas Patocka if (unlikely(sbi->sb_n_free >= sbi->sb_fs_size)) { 292cbe5c76SMikulas Patocka hpfs_error(s, "free count overflow, freeing sector %08x", sec); 302cbe5c76SMikulas Patocka sbi->sb_n_free = -1; 312cbe5c76SMikulas Patocka return; 322cbe5c76SMikulas Patocka } 332cbe5c76SMikulas Patocka sbi->sb_n_free++; 342cbe5c76SMikulas Patocka } 352cbe5c76SMikulas Patocka } 362cbe5c76SMikulas Patocka 372cbe5c76SMikulas Patocka static void hpfs_claim_dirband_alloc(struct super_block *s, secno sec) 382cbe5c76SMikulas Patocka { 392cbe5c76SMikulas Patocka struct hpfs_sb_info *sbi = hpfs_sb(s); 402cbe5c76SMikulas Patocka if (sbi->sb_n_free_dnodes != (unsigned)-1) { 412cbe5c76SMikulas Patocka if (unlikely(!sbi->sb_n_free_dnodes)) { 422cbe5c76SMikulas Patocka hpfs_error(s, "dirband free count underflow, allocating sector %08x", sec); 432cbe5c76SMikulas Patocka sbi->sb_n_free_dnodes = -1; 442cbe5c76SMikulas Patocka return; 452cbe5c76SMikulas Patocka } 462cbe5c76SMikulas Patocka sbi->sb_n_free_dnodes--; 472cbe5c76SMikulas Patocka } 482cbe5c76SMikulas Patocka } 492cbe5c76SMikulas Patocka 502cbe5c76SMikulas Patocka static void hpfs_claim_dirband_free(struct super_block *s, secno sec) 512cbe5c76SMikulas Patocka { 522cbe5c76SMikulas Patocka struct hpfs_sb_info *sbi = hpfs_sb(s); 532cbe5c76SMikulas Patocka if (sbi->sb_n_free_dnodes != (unsigned)-1) { 542cbe5c76SMikulas Patocka if (unlikely(sbi->sb_n_free_dnodes >= sbi->sb_dirband_size / 4)) { 552cbe5c76SMikulas Patocka hpfs_error(s, "dirband free count overflow, freeing sector %08x", sec); 562cbe5c76SMikulas Patocka sbi->sb_n_free_dnodes = -1; 572cbe5c76SMikulas Patocka return; 582cbe5c76SMikulas Patocka } 592cbe5c76SMikulas Patocka sbi->sb_n_free_dnodes++; 602cbe5c76SMikulas Patocka } 612cbe5c76SMikulas Patocka } 622cbe5c76SMikulas Patocka 631da177e4SLinus Torvalds /* 641da177e4SLinus Torvalds * Check if a sector is allocated in bitmap 651da177e4SLinus Torvalds * This is really slow. Turned on only if chk==2 661da177e4SLinus Torvalds */ 671da177e4SLinus Torvalds 681da177e4SLinus Torvalds static int chk_if_allocated(struct super_block *s, secno sec, char *msg) 691da177e4SLinus Torvalds { 701da177e4SLinus Torvalds struct quad_buffer_head qbh; 7152576da3SAl Viro __le32 *bmp; 721da177e4SLinus Torvalds if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "chk"))) goto fail; 7352576da3SAl Viro if ((le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f)) & 1) { 741da177e4SLinus Torvalds hpfs_error(s, "sector '%s' - %08x not allocated in bitmap", msg, sec); 751da177e4SLinus Torvalds goto fail1; 761da177e4SLinus Torvalds } 771da177e4SLinus Torvalds hpfs_brelse4(&qbh); 781da177e4SLinus Torvalds if (sec >= hpfs_sb(s)->sb_dirband_start && sec < hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) { 791da177e4SLinus Torvalds unsigned ssec = (sec - hpfs_sb(s)->sb_dirband_start) / 4; 801da177e4SLinus Torvalds if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto fail; 810b69760bSMikulas Patocka if ((le32_to_cpu(bmp[ssec >> 5]) >> (ssec & 0x1f)) & 1) { 821da177e4SLinus Torvalds hpfs_error(s, "sector '%s' - %08x not allocated in directory bitmap", msg, sec); 831da177e4SLinus Torvalds goto fail1; 841da177e4SLinus Torvalds } 851da177e4SLinus Torvalds hpfs_brelse4(&qbh); 861da177e4SLinus Torvalds } 871da177e4SLinus Torvalds return 0; 881da177e4SLinus Torvalds fail1: 891da177e4SLinus Torvalds hpfs_brelse4(&qbh); 901da177e4SLinus Torvalds fail: 911da177e4SLinus Torvalds return 1; 921da177e4SLinus Torvalds } 931da177e4SLinus Torvalds 941da177e4SLinus Torvalds /* 951da177e4SLinus Torvalds * Check if sector(s) have proper number and additionally check if they're 961da177e4SLinus Torvalds * allocated in bitmap. 971da177e4SLinus Torvalds */ 981da177e4SLinus Torvalds 991da177e4SLinus Torvalds int hpfs_chk_sectors(struct super_block *s, secno start, int len, char *msg) 1001da177e4SLinus Torvalds { 1011da177e4SLinus Torvalds if (start + len < start || start < 0x12 || 1021da177e4SLinus Torvalds start + len > hpfs_sb(s)->sb_fs_size) { 1031da177e4SLinus Torvalds hpfs_error(s, "sector(s) '%s' badly placed at %08x", msg, start); 1041da177e4SLinus Torvalds return 1; 1051da177e4SLinus Torvalds } 1061da177e4SLinus Torvalds if (hpfs_sb(s)->sb_chk>=2) { 1071da177e4SLinus Torvalds int i; 1081da177e4SLinus Torvalds for (i = 0; i < len; i++) 1091da177e4SLinus Torvalds if (chk_if_allocated(s, start + i, msg)) return 1; 1101da177e4SLinus Torvalds } 1111da177e4SLinus Torvalds return 0; 1121da177e4SLinus Torvalds } 1131da177e4SLinus Torvalds 1141da177e4SLinus Torvalds static secno alloc_in_bmp(struct super_block *s, secno near, unsigned n, unsigned forward) 1151da177e4SLinus Torvalds { 1161da177e4SLinus Torvalds struct quad_buffer_head qbh; 11752576da3SAl Viro __le32 *bmp; 1181da177e4SLinus Torvalds unsigned bs = near & ~0x3fff; 1191da177e4SLinus Torvalds unsigned nr = (near & 0x3fff) & ~(n - 1); 1201da177e4SLinus Torvalds /*unsigned mnr;*/ 1211da177e4SLinus Torvalds unsigned i, q; 1221da177e4SLinus Torvalds int a, b; 1231da177e4SLinus Torvalds secno ret = 0; 1241da177e4SLinus Torvalds if (n != 1 && n != 4) { 1251da177e4SLinus Torvalds hpfs_error(s, "Bad allocation size: %d", n); 1261da177e4SLinus Torvalds return 0; 1271da177e4SLinus Torvalds } 1281da177e4SLinus Torvalds if (bs != ~0x3fff) { 1291da177e4SLinus Torvalds if (!(bmp = hpfs_map_bitmap(s, near >> 14, &qbh, "aib"))) goto uls; 1301da177e4SLinus Torvalds } else { 1311da177e4SLinus Torvalds if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto uls; 1321da177e4SLinus Torvalds } 1331da177e4SLinus Torvalds if (!tstbits(bmp, nr, n + forward)) { 1341da177e4SLinus Torvalds ret = bs + nr; 1351da177e4SLinus Torvalds goto rt; 1361da177e4SLinus Torvalds } 1371da177e4SLinus Torvalds q = nr + n; b = 0; 1381da177e4SLinus Torvalds while ((a = tstbits(bmp, q, n + forward)) != 0) { 1391da177e4SLinus Torvalds q += a; 1401da177e4SLinus Torvalds if (n != 1) q = ((q-1)&~(n-1))+n; 1411da177e4SLinus Torvalds if (!b) { 1421da177e4SLinus Torvalds if (q>>5 != nr>>5) { 1431da177e4SLinus Torvalds b = 1; 1441da177e4SLinus Torvalds q = nr & 0x1f; 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds } else if (q > nr) break; 1471da177e4SLinus Torvalds } 1481da177e4SLinus Torvalds if (!a) { 1491da177e4SLinus Torvalds ret = bs + q; 1501da177e4SLinus Torvalds goto rt; 1511da177e4SLinus Torvalds } 1521da177e4SLinus Torvalds nr >>= 5; 1530b69760bSMikulas Patocka /*for (i = nr + 1; i != nr; i++, i &= 0x1ff) */ 1541da177e4SLinus Torvalds i = nr; 1551da177e4SLinus Torvalds do { 1560b69760bSMikulas Patocka if (!le32_to_cpu(bmp[i])) goto cont; 1570b69760bSMikulas Patocka if (n + forward >= 0x3f && le32_to_cpu(bmp[i]) != 0xffffffff) goto cont; 1581da177e4SLinus Torvalds q = i<<5; 1591da177e4SLinus Torvalds if (i > 0) { 1600b69760bSMikulas Patocka unsigned k = le32_to_cpu(bmp[i-1]); 1611da177e4SLinus Torvalds while (k & 0x80000000) { 1621da177e4SLinus Torvalds q--; k <<= 1; 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds } 1651da177e4SLinus Torvalds if (n != 1) q = ((q-1)&~(n-1))+n; 1661da177e4SLinus Torvalds while ((a = tstbits(bmp, q, n + forward)) != 0) { 1671da177e4SLinus Torvalds q += a; 1681da177e4SLinus Torvalds if (n != 1) q = ((q-1)&~(n-1))+n; 1691da177e4SLinus Torvalds if (q>>5 > i) break; 1701da177e4SLinus Torvalds } 1711da177e4SLinus Torvalds if (!a) { 1721da177e4SLinus Torvalds ret = bs + q; 1731da177e4SLinus Torvalds goto rt; 1741da177e4SLinus Torvalds } 1751da177e4SLinus Torvalds cont: 1761da177e4SLinus Torvalds i++, i &= 0x1ff; 1771da177e4SLinus Torvalds } while (i != nr); 1781da177e4SLinus Torvalds rt: 1791da177e4SLinus Torvalds if (ret) { 1800b69760bSMikulas Patocka if (hpfs_sb(s)->sb_chk && ((ret >> 14) != (bs >> 14) || (le32_to_cpu(bmp[(ret & 0x3fff) >> 5]) | ~(((1 << n) - 1) << (ret & 0x1f))) != 0xffffffff)) { 1811da177e4SLinus Torvalds hpfs_error(s, "Allocation doesn't work! Wanted %d, allocated at %08x", n, ret); 1821da177e4SLinus Torvalds ret = 0; 1831da177e4SLinus Torvalds goto b; 1841da177e4SLinus Torvalds } 1850b69760bSMikulas Patocka bmp[(ret & 0x3fff) >> 5] &= cpu_to_le32(~(((1 << n) - 1) << (ret & 0x1f))); 1861da177e4SLinus Torvalds hpfs_mark_4buffers_dirty(&qbh); 1871da177e4SLinus Torvalds } 1881da177e4SLinus Torvalds b: 1891da177e4SLinus Torvalds hpfs_brelse4(&qbh); 1901da177e4SLinus Torvalds uls: 1911da177e4SLinus Torvalds return ret; 1921da177e4SLinus Torvalds } 1931da177e4SLinus Torvalds 1941da177e4SLinus Torvalds /* 1951da177e4SLinus Torvalds * Allocation strategy: 1) search place near the sector specified 1961da177e4SLinus Torvalds * 2) search bitmap where free sectors last found 1971da177e4SLinus Torvalds * 3) search all bitmaps 1981da177e4SLinus Torvalds * 4) search all bitmaps ignoring number of pre-allocated 1991da177e4SLinus Torvalds * sectors 2001da177e4SLinus Torvalds */ 2011da177e4SLinus Torvalds 2027d23ce36SMikulas Patocka secno hpfs_alloc_sector(struct super_block *s, secno near, unsigned n, int forward) 2031da177e4SLinus Torvalds { 2041da177e4SLinus Torvalds secno sec; 2051da177e4SLinus Torvalds int i; 2061da177e4SLinus Torvalds unsigned n_bmps; 2071da177e4SLinus Torvalds struct hpfs_sb_info *sbi = hpfs_sb(s); 2081da177e4SLinus Torvalds int f_p = 0; 2091da177e4SLinus Torvalds int near_bmp; 2101da177e4SLinus Torvalds if (forward < 0) { 2111da177e4SLinus Torvalds forward = -forward; 2121da177e4SLinus Torvalds f_p = 1; 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds n_bmps = (sbi->sb_fs_size + 0x4000 - 1) >> 14; 2151da177e4SLinus Torvalds if (near && near < sbi->sb_fs_size) { 2161da177e4SLinus Torvalds if ((sec = alloc_in_bmp(s, near, n, f_p ? forward : forward/4))) goto ret; 2171da177e4SLinus Torvalds near_bmp = near >> 14; 2181da177e4SLinus Torvalds } else near_bmp = n_bmps / 2; 2191da177e4SLinus Torvalds /* 2201da177e4SLinus Torvalds if (b != -1) { 2211da177e4SLinus Torvalds if ((sec = alloc_in_bmp(s, b<<14, n, f_p ? forward : forward/2))) { 2221da177e4SLinus Torvalds b &= 0x0fffffff; 2231da177e4SLinus Torvalds goto ret; 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds if (b > 0x10000000) if ((sec = alloc_in_bmp(s, (b&0xfffffff)<<14, n, f_p ? forward : 0))) goto ret; 2261da177e4SLinus Torvalds */ 2271da177e4SLinus Torvalds if (!f_p) if (forward > sbi->sb_max_fwd_alloc) forward = sbi->sb_max_fwd_alloc; 2281da177e4SLinus Torvalds less_fwd: 2291da177e4SLinus Torvalds for (i = 0; i < n_bmps; i++) { 2301da177e4SLinus Torvalds if (near_bmp+i < n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i) << 14, n, forward)))) { 2311da177e4SLinus Torvalds sbi->sb_c_bitmap = near_bmp+i; 2321da177e4SLinus Torvalds goto ret; 2331da177e4SLinus Torvalds } 2341da177e4SLinus Torvalds if (!forward) { 2351da177e4SLinus Torvalds if (near_bmp-i-1 >= 0 && ((sec = alloc_in_bmp(s, (near_bmp-i-1) << 14, n, forward)))) { 2361da177e4SLinus Torvalds sbi->sb_c_bitmap = near_bmp-i-1; 2371da177e4SLinus Torvalds goto ret; 2381da177e4SLinus Torvalds } 2391da177e4SLinus Torvalds } else { 2401da177e4SLinus Torvalds if (near_bmp+i >= n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i-n_bmps) << 14, n, forward)))) { 2411da177e4SLinus Torvalds sbi->sb_c_bitmap = near_bmp+i-n_bmps; 2421da177e4SLinus Torvalds goto ret; 2431da177e4SLinus Torvalds } 2441da177e4SLinus Torvalds } 2451da177e4SLinus Torvalds if (i == 1 && sbi->sb_c_bitmap != -1 && ((sec = alloc_in_bmp(s, (sbi->sb_c_bitmap) << 14, n, forward)))) { 2461da177e4SLinus Torvalds goto ret; 2471da177e4SLinus Torvalds } 2481da177e4SLinus Torvalds } 2491da177e4SLinus Torvalds if (!f_p) { 2501da177e4SLinus Torvalds if (forward) { 2511da177e4SLinus Torvalds sbi->sb_max_fwd_alloc = forward * 3 / 4; 2521da177e4SLinus Torvalds forward /= 2; 2531da177e4SLinus Torvalds goto less_fwd; 2541da177e4SLinus Torvalds } 2551da177e4SLinus Torvalds } 2561da177e4SLinus Torvalds sec = 0; 2571da177e4SLinus Torvalds ret: 2582cbe5c76SMikulas Patocka if (sec) { 2592cbe5c76SMikulas Patocka i = 0; 2602cbe5c76SMikulas Patocka do 2612cbe5c76SMikulas Patocka hpfs_claim_alloc(s, sec + i); 2622cbe5c76SMikulas Patocka while (unlikely(++i < n)); 2632cbe5c76SMikulas Patocka } 2641da177e4SLinus Torvalds if (sec && f_p) { 2651da177e4SLinus Torvalds for (i = 0; i < forward; i++) { 2662cbe5c76SMikulas Patocka if (!hpfs_alloc_if_possible(s, sec + n + i)) { 2671da177e4SLinus Torvalds hpfs_error(s, "Prealloc doesn't work! Wanted %d, allocated at %08x, can't allocate %d", forward, sec, i); 2681da177e4SLinus Torvalds sec = 0; 2691da177e4SLinus Torvalds break; 2701da177e4SLinus Torvalds } 2711da177e4SLinus Torvalds } 2721da177e4SLinus Torvalds } 2731da177e4SLinus Torvalds return sec; 2741da177e4SLinus Torvalds } 2751da177e4SLinus Torvalds 2767d23ce36SMikulas Patocka static secno alloc_in_dirband(struct super_block *s, secno near) 2771da177e4SLinus Torvalds { 2781da177e4SLinus Torvalds unsigned nr = near; 2791da177e4SLinus Torvalds secno sec; 2801da177e4SLinus Torvalds struct hpfs_sb_info *sbi = hpfs_sb(s); 2811da177e4SLinus Torvalds if (nr < sbi->sb_dirband_start) 2821da177e4SLinus Torvalds nr = sbi->sb_dirband_start; 2831da177e4SLinus Torvalds if (nr >= sbi->sb_dirband_start + sbi->sb_dirband_size) 2841da177e4SLinus Torvalds nr = sbi->sb_dirband_start + sbi->sb_dirband_size - 4; 2851da177e4SLinus Torvalds nr -= sbi->sb_dirband_start; 2861da177e4SLinus Torvalds nr >>= 2; 2871da177e4SLinus Torvalds sec = alloc_in_bmp(s, (~0x3fff) | nr, 1, 0); 2881da177e4SLinus Torvalds if (!sec) return 0; 2892cbe5c76SMikulas Patocka hpfs_claim_dirband_alloc(s, sec); 2901da177e4SLinus Torvalds return ((sec & 0x3fff) << 2) + sbi->sb_dirband_start; 2911da177e4SLinus Torvalds } 2921da177e4SLinus Torvalds 2931da177e4SLinus Torvalds /* Alloc sector if it's free */ 2941da177e4SLinus Torvalds 2957d23ce36SMikulas Patocka int hpfs_alloc_if_possible(struct super_block *s, secno sec) 2961da177e4SLinus Torvalds { 2971da177e4SLinus Torvalds struct quad_buffer_head qbh; 29852576da3SAl Viro __le32 *bmp; 2991da177e4SLinus Torvalds if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "aip"))) goto end; 3000b69760bSMikulas Patocka if (le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) & (1 << (sec & 0x1f))) { 3010b69760bSMikulas Patocka bmp[(sec & 0x3fff) >> 5] &= cpu_to_le32(~(1 << (sec & 0x1f))); 3021da177e4SLinus Torvalds hpfs_mark_4buffers_dirty(&qbh); 3031da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3042cbe5c76SMikulas Patocka hpfs_claim_alloc(s, sec); 3051da177e4SLinus Torvalds return 1; 3061da177e4SLinus Torvalds } 3071da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3081da177e4SLinus Torvalds end: 3091da177e4SLinus Torvalds return 0; 3101da177e4SLinus Torvalds } 3111da177e4SLinus Torvalds 3121da177e4SLinus Torvalds /* Free sectors in bitmaps */ 3131da177e4SLinus Torvalds 3141da177e4SLinus Torvalds void hpfs_free_sectors(struct super_block *s, secno sec, unsigned n) 3151da177e4SLinus Torvalds { 3161da177e4SLinus Torvalds struct quad_buffer_head qbh; 31752576da3SAl Viro __le32 *bmp; 3181da177e4SLinus Torvalds struct hpfs_sb_info *sbi = hpfs_sb(s); 319b7cb1ce2SFabian Frederick /*pr_info("2 - ");*/ 3201da177e4SLinus Torvalds if (!n) return; 3211da177e4SLinus Torvalds if (sec < 0x12) { 3221da177e4SLinus Torvalds hpfs_error(s, "Trying to free reserved sector %08x", sec); 3231da177e4SLinus Torvalds return; 3241da177e4SLinus Torvalds } 3251da177e4SLinus Torvalds sbi->sb_max_fwd_alloc += n > 0xffff ? 0xffff : n; 3261da177e4SLinus Torvalds if (sbi->sb_max_fwd_alloc > 0xffffff) sbi->sb_max_fwd_alloc = 0xffffff; 3271da177e4SLinus Torvalds new_map: 3281da177e4SLinus Torvalds if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "free"))) { 3291da177e4SLinus Torvalds return; 3301da177e4SLinus Torvalds } 3311da177e4SLinus Torvalds new_tst: 3320b69760bSMikulas Patocka if ((le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f) & 1)) { 3331da177e4SLinus Torvalds hpfs_error(s, "sector %08x not allocated", sec); 3341da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3351da177e4SLinus Torvalds return; 3361da177e4SLinus Torvalds } 3370b69760bSMikulas Patocka bmp[(sec & 0x3fff) >> 5] |= cpu_to_le32(1 << (sec & 0x1f)); 3382cbe5c76SMikulas Patocka hpfs_claim_free(s, sec); 3391da177e4SLinus Torvalds if (!--n) { 3401da177e4SLinus Torvalds hpfs_mark_4buffers_dirty(&qbh); 3411da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3421da177e4SLinus Torvalds return; 3431da177e4SLinus Torvalds } 3441da177e4SLinus Torvalds if (!(++sec & 0x3fff)) { 3451da177e4SLinus Torvalds hpfs_mark_4buffers_dirty(&qbh); 3461da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3471da177e4SLinus Torvalds goto new_map; 3481da177e4SLinus Torvalds } 3491da177e4SLinus Torvalds goto new_tst; 3501da177e4SLinus Torvalds } 3511da177e4SLinus Torvalds 3521da177e4SLinus Torvalds /* 3531da177e4SLinus Torvalds * Check if there are at least n free dnodes on the filesystem. 3541da177e4SLinus Torvalds * Called before adding to dnode. If we run out of space while 3551da177e4SLinus Torvalds * splitting dnodes, it would corrupt dnode tree. 3561da177e4SLinus Torvalds */ 3571da177e4SLinus Torvalds 3581da177e4SLinus Torvalds int hpfs_check_free_dnodes(struct super_block *s, int n) 3591da177e4SLinus Torvalds { 3601da177e4SLinus Torvalds int n_bmps = (hpfs_sb(s)->sb_fs_size + 0x4000 - 1) >> 14; 3611da177e4SLinus Torvalds int b = hpfs_sb(s)->sb_c_bitmap & 0x0fffffff; 3621da177e4SLinus Torvalds int i, j; 36352576da3SAl Viro __le32 *bmp; 3641da177e4SLinus Torvalds struct quad_buffer_head qbh; 3651da177e4SLinus Torvalds if ((bmp = hpfs_map_dnode_bitmap(s, &qbh))) { 3661da177e4SLinus Torvalds for (j = 0; j < 512; j++) { 3671da177e4SLinus Torvalds unsigned k; 3680b69760bSMikulas Patocka if (!le32_to_cpu(bmp[j])) continue; 3690b69760bSMikulas Patocka for (k = le32_to_cpu(bmp[j]); k; k >>= 1) if (k & 1) if (!--n) { 3701da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3711da177e4SLinus Torvalds return 0; 3721da177e4SLinus Torvalds } 3731da177e4SLinus Torvalds } 3741da177e4SLinus Torvalds } 3751da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3761da177e4SLinus Torvalds i = 0; 3771da177e4SLinus Torvalds if (hpfs_sb(s)->sb_c_bitmap != -1) { 3781da177e4SLinus Torvalds bmp = hpfs_map_bitmap(s, b, &qbh, "chkdn1"); 3791da177e4SLinus Torvalds goto chk_bmp; 3801da177e4SLinus Torvalds } 3811da177e4SLinus Torvalds chk_next: 3821da177e4SLinus Torvalds if (i == b) i++; 3831da177e4SLinus Torvalds if (i >= n_bmps) return 1; 3841da177e4SLinus Torvalds bmp = hpfs_map_bitmap(s, i, &qbh, "chkdn2"); 3851da177e4SLinus Torvalds chk_bmp: 3861da177e4SLinus Torvalds if (bmp) { 3871da177e4SLinus Torvalds for (j = 0; j < 512; j++) { 3880b69760bSMikulas Patocka u32 k; 3890b69760bSMikulas Patocka if (!le32_to_cpu(bmp[j])) continue; 3901da177e4SLinus Torvalds for (k = 0xf; k; k <<= 4) 3910b69760bSMikulas Patocka if ((le32_to_cpu(bmp[j]) & k) == k) { 3921da177e4SLinus Torvalds if (!--n) { 3931da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3941da177e4SLinus Torvalds return 0; 3951da177e4SLinus Torvalds } 3961da177e4SLinus Torvalds } 3971da177e4SLinus Torvalds } 3981da177e4SLinus Torvalds hpfs_brelse4(&qbh); 3991da177e4SLinus Torvalds } 4001da177e4SLinus Torvalds i++; 4011da177e4SLinus Torvalds goto chk_next; 4021da177e4SLinus Torvalds } 4031da177e4SLinus Torvalds 4041da177e4SLinus Torvalds void hpfs_free_dnode(struct super_block *s, dnode_secno dno) 4051da177e4SLinus Torvalds { 4061da177e4SLinus Torvalds if (hpfs_sb(s)->sb_chk) if (dno & 3) { 4071da177e4SLinus Torvalds hpfs_error(s, "hpfs_free_dnode: dnode %08x not aligned", dno); 4081da177e4SLinus Torvalds return; 4091da177e4SLinus Torvalds } 4101da177e4SLinus Torvalds if (dno < hpfs_sb(s)->sb_dirband_start || 4111da177e4SLinus Torvalds dno >= hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) { 4121da177e4SLinus Torvalds hpfs_free_sectors(s, dno, 4); 4131da177e4SLinus Torvalds } else { 4141da177e4SLinus Torvalds struct quad_buffer_head qbh; 41552576da3SAl Viro __le32 *bmp; 4161da177e4SLinus Torvalds unsigned ssec = (dno - hpfs_sb(s)->sb_dirband_start) / 4; 4171da177e4SLinus Torvalds if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) { 4181da177e4SLinus Torvalds return; 4191da177e4SLinus Torvalds } 4200b69760bSMikulas Patocka bmp[ssec >> 5] |= cpu_to_le32(1 << (ssec & 0x1f)); 4211da177e4SLinus Torvalds hpfs_mark_4buffers_dirty(&qbh); 4221da177e4SLinus Torvalds hpfs_brelse4(&qbh); 4232cbe5c76SMikulas Patocka hpfs_claim_dirband_free(s, dno); 4241da177e4SLinus Torvalds } 4251da177e4SLinus Torvalds } 4261da177e4SLinus Torvalds 4271da177e4SLinus Torvalds struct dnode *hpfs_alloc_dnode(struct super_block *s, secno near, 4287d23ce36SMikulas Patocka dnode_secno *dno, struct quad_buffer_head *qbh) 4291da177e4SLinus Torvalds { 4301da177e4SLinus Torvalds struct dnode *d; 4312cbe5c76SMikulas Patocka if (hpfs_get_free_dnodes(s) > FREE_DNODES_ADD) { 4327d23ce36SMikulas Patocka if (!(*dno = alloc_in_dirband(s, near))) 4337d23ce36SMikulas Patocka if (!(*dno = hpfs_alloc_sector(s, near, 4, 0))) return NULL; 4341da177e4SLinus Torvalds } else { 4357d23ce36SMikulas Patocka if (!(*dno = hpfs_alloc_sector(s, near, 4, 0))) 4367d23ce36SMikulas Patocka if (!(*dno = alloc_in_dirband(s, near))) return NULL; 4371da177e4SLinus Torvalds } 4381da177e4SLinus Torvalds if (!(d = hpfs_get_4sectors(s, *dno, qbh))) { 4391da177e4SLinus Torvalds hpfs_free_dnode(s, *dno); 4401da177e4SLinus Torvalds return NULL; 4411da177e4SLinus Torvalds } 4421da177e4SLinus Torvalds memset(d, 0, 2048); 4430b69760bSMikulas Patocka d->magic = cpu_to_le32(DNODE_MAGIC); 4440b69760bSMikulas Patocka d->first_free = cpu_to_le32(52); 4451da177e4SLinus Torvalds d->dirent[0] = 32; 4461da177e4SLinus Torvalds d->dirent[2] = 8; 4471da177e4SLinus Torvalds d->dirent[30] = 1; 4481da177e4SLinus Torvalds d->dirent[31] = 255; 4490b69760bSMikulas Patocka d->self = cpu_to_le32(*dno); 4501da177e4SLinus Torvalds return d; 4511da177e4SLinus Torvalds } 4521da177e4SLinus Torvalds 4531da177e4SLinus Torvalds struct fnode *hpfs_alloc_fnode(struct super_block *s, secno near, fnode_secno *fno, 4541da177e4SLinus Torvalds struct buffer_head **bh) 4551da177e4SLinus Torvalds { 4561da177e4SLinus Torvalds struct fnode *f; 4577d23ce36SMikulas Patocka if (!(*fno = hpfs_alloc_sector(s, near, 1, FNODE_ALLOC_FWD))) return NULL; 4581da177e4SLinus Torvalds if (!(f = hpfs_get_sector(s, *fno, bh))) { 4591da177e4SLinus Torvalds hpfs_free_sectors(s, *fno, 1); 4601da177e4SLinus Torvalds return NULL; 4611da177e4SLinus Torvalds } 4621da177e4SLinus Torvalds memset(f, 0, 512); 4630b69760bSMikulas Patocka f->magic = cpu_to_le32(FNODE_MAGIC); 4640b69760bSMikulas Patocka f->ea_offs = cpu_to_le16(0xc4); 4651da177e4SLinus Torvalds f->btree.n_free_nodes = 8; 4660b69760bSMikulas Patocka f->btree.first_free = cpu_to_le16(8); 4671da177e4SLinus Torvalds return f; 4681da177e4SLinus Torvalds } 4691da177e4SLinus Torvalds 4701da177e4SLinus Torvalds struct anode *hpfs_alloc_anode(struct super_block *s, secno near, anode_secno *ano, 4711da177e4SLinus Torvalds struct buffer_head **bh) 4721da177e4SLinus Torvalds { 4731da177e4SLinus Torvalds struct anode *a; 4747d23ce36SMikulas Patocka if (!(*ano = hpfs_alloc_sector(s, near, 1, ANODE_ALLOC_FWD))) return NULL; 4751da177e4SLinus Torvalds if (!(a = hpfs_get_sector(s, *ano, bh))) { 4761da177e4SLinus Torvalds hpfs_free_sectors(s, *ano, 1); 4771da177e4SLinus Torvalds return NULL; 4781da177e4SLinus Torvalds } 4791da177e4SLinus Torvalds memset(a, 0, 512); 4800b69760bSMikulas Patocka a->magic = cpu_to_le32(ANODE_MAGIC); 4810b69760bSMikulas Patocka a->self = cpu_to_le32(*ano); 4821da177e4SLinus Torvalds a->btree.n_free_nodes = 40; 4831da177e4SLinus Torvalds a->btree.n_used_nodes = 0; 4840b69760bSMikulas Patocka a->btree.first_free = cpu_to_le16(8); 4851da177e4SLinus Torvalds return a; 4861da177e4SLinus Torvalds } 487a27b5b97SMikulas Patocka 488a27b5b97SMikulas Patocka static unsigned find_run(__le32 *bmp, unsigned *idx) 489a27b5b97SMikulas Patocka { 490a27b5b97SMikulas Patocka unsigned len; 491a27b5b97SMikulas Patocka while (tstbits(bmp, *idx, 1)) { 492a27b5b97SMikulas Patocka (*idx)++; 493a27b5b97SMikulas Patocka if (unlikely(*idx >= 0x4000)) 494a27b5b97SMikulas Patocka return 0; 495a27b5b97SMikulas Patocka } 496a27b5b97SMikulas Patocka len = 1; 497a27b5b97SMikulas Patocka while (!tstbits(bmp, *idx + len, 1)) 498a27b5b97SMikulas Patocka len++; 499a27b5b97SMikulas Patocka return len; 500a27b5b97SMikulas Patocka } 501a27b5b97SMikulas Patocka 502a27b5b97SMikulas Patocka static int do_trim(struct super_block *s, secno start, unsigned len, secno limit_start, secno limit_end, unsigned minlen, unsigned *result) 503a27b5b97SMikulas Patocka { 504a27b5b97SMikulas Patocka int err; 505a27b5b97SMikulas Patocka secno end; 506a27b5b97SMikulas Patocka if (fatal_signal_pending(current)) 507a27b5b97SMikulas Patocka return -EINTR; 508a27b5b97SMikulas Patocka end = start + len; 509a27b5b97SMikulas Patocka if (start < limit_start) 510a27b5b97SMikulas Patocka start = limit_start; 511a27b5b97SMikulas Patocka if (end > limit_end) 512a27b5b97SMikulas Patocka end = limit_end; 513a27b5b97SMikulas Patocka if (start >= end) 514a27b5b97SMikulas Patocka return 0; 515a27b5b97SMikulas Patocka if (end - start < minlen) 516a27b5b97SMikulas Patocka return 0; 517a27b5b97SMikulas Patocka err = sb_issue_discard(s, start, end - start, GFP_NOFS, 0); 518a27b5b97SMikulas Patocka if (err) 519a27b5b97SMikulas Patocka return err; 520a27b5b97SMikulas Patocka *result += end - start; 521a27b5b97SMikulas Patocka return 0; 522a27b5b97SMikulas Patocka } 523a27b5b97SMikulas Patocka 524a27b5b97SMikulas Patocka int hpfs_trim_fs(struct super_block *s, u64 start, u64 end, u64 minlen, unsigned *result) 525a27b5b97SMikulas Patocka { 526a27b5b97SMikulas Patocka int err = 0; 527a27b5b97SMikulas Patocka struct hpfs_sb_info *sbi = hpfs_sb(s); 528a27b5b97SMikulas Patocka unsigned idx, len, start_bmp, end_bmp; 529a27b5b97SMikulas Patocka __le32 *bmp; 530a27b5b97SMikulas Patocka struct quad_buffer_head qbh; 531a27b5b97SMikulas Patocka 532a27b5b97SMikulas Patocka *result = 0; 533a27b5b97SMikulas Patocka if (!end || end > sbi->sb_fs_size) 534a27b5b97SMikulas Patocka end = sbi->sb_fs_size; 535a27b5b97SMikulas Patocka if (start >= sbi->sb_fs_size) 536a27b5b97SMikulas Patocka return 0; 537a27b5b97SMikulas Patocka if (minlen > 0x4000) 538a27b5b97SMikulas Patocka return 0; 539a27b5b97SMikulas Patocka if (start < sbi->sb_dirband_start + sbi->sb_dirband_size && end > sbi->sb_dirband_start) { 540a27b5b97SMikulas Patocka hpfs_lock(s); 541bc98a42cSDavid Howells if (sb_rdonly(s)) { 542a27b5b97SMikulas Patocka err = -EROFS; 543a27b5b97SMikulas Patocka goto unlock_1; 544a27b5b97SMikulas Patocka } 545a27b5b97SMikulas Patocka if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) { 546a27b5b97SMikulas Patocka err = -EIO; 547a27b5b97SMikulas Patocka goto unlock_1; 548a27b5b97SMikulas Patocka } 549a27b5b97SMikulas Patocka idx = 0; 550a27b5b97SMikulas Patocka while ((len = find_run(bmp, &idx)) && !err) { 551a27b5b97SMikulas Patocka err = do_trim(s, sbi->sb_dirband_start + idx * 4, len * 4, start, end, minlen, result); 552a27b5b97SMikulas Patocka idx += len; 553a27b5b97SMikulas Patocka } 554a27b5b97SMikulas Patocka hpfs_brelse4(&qbh); 555a27b5b97SMikulas Patocka unlock_1: 556a27b5b97SMikulas Patocka hpfs_unlock(s); 557a27b5b97SMikulas Patocka } 558a27b5b97SMikulas Patocka start_bmp = start >> 14; 559a27b5b97SMikulas Patocka end_bmp = (end + 0x3fff) >> 14; 560a27b5b97SMikulas Patocka while (start_bmp < end_bmp && !err) { 561a27b5b97SMikulas Patocka hpfs_lock(s); 562bc98a42cSDavid Howells if (sb_rdonly(s)) { 563a27b5b97SMikulas Patocka err = -EROFS; 564a27b5b97SMikulas Patocka goto unlock_2; 565a27b5b97SMikulas Patocka } 566a27b5b97SMikulas Patocka if (!(bmp = hpfs_map_bitmap(s, start_bmp, &qbh, "trim"))) { 567a27b5b97SMikulas Patocka err = -EIO; 568a27b5b97SMikulas Patocka goto unlock_2; 569a27b5b97SMikulas Patocka } 570a27b5b97SMikulas Patocka idx = 0; 571a27b5b97SMikulas Patocka while ((len = find_run(bmp, &idx)) && !err) { 572a27b5b97SMikulas Patocka err = do_trim(s, (start_bmp << 14) + idx, len, start, end, minlen, result); 573a27b5b97SMikulas Patocka idx += len; 574a27b5b97SMikulas Patocka } 575a27b5b97SMikulas Patocka hpfs_brelse4(&qbh); 576a27b5b97SMikulas Patocka unlock_2: 577a27b5b97SMikulas Patocka hpfs_unlock(s); 578a27b5b97SMikulas Patocka start_bmp++; 579a27b5b97SMikulas Patocka } 580a27b5b97SMikulas Patocka return err; 581a27b5b97SMikulas Patocka } 582