fs/hpfs/alloc.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hpfs/alloc.c
0004  *
0005  *  Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
0006  *
0007  *  HPFS bitmap operations
0008  */
0009
0010 #include "hpfs_fn.h"
0011
0012 static void hpfs_claim_alloc(struct super_block *s, secno sec)
0013 {
0014     struct hpfs_sb_info *sbi = hpfs_sb(s);
0015     if (sbi->sb_n_free != (unsigned)-1) {
0016         if (unlikely(!sbi->sb_n_free)) {
0017             hpfs_error(s, "free count underflow, allocating sector %08x", sec);
0018             sbi->sb_n_free = -1;
0019             return;
0020         }
0021         sbi->sb_n_free--;
0022     }
0023 }
0024
0025 static void hpfs_claim_free(struct super_block *s, secno sec)
0026 {
0027     struct hpfs_sb_info *sbi = hpfs_sb(s);
0028     if (sbi->sb_n_free != (unsigned)-1) {
0029         if (unlikely(sbi->sb_n_free >= sbi->sb_fs_size)) {
0030             hpfs_error(s, "free count overflow, freeing sector %08x", sec);
0031             sbi->sb_n_free = -1;
0032             return;
0033         }
0034         sbi->sb_n_free++;
0035     }
0036 }
0037
0038 static void hpfs_claim_dirband_alloc(struct super_block *s, secno sec)
0039 {
0040     struct hpfs_sb_info *sbi = hpfs_sb(s);
0041     if (sbi->sb_n_free_dnodes != (unsigned)-1) {
0042         if (unlikely(!sbi->sb_n_free_dnodes)) {
0043             hpfs_error(s, "dirband free count underflow, allocating sector %08x", sec);
0044             sbi->sb_n_free_dnodes = -1;
0045             return;
0046         }
0047         sbi->sb_n_free_dnodes--;
0048     }
0049 }
0050
0051 static void hpfs_claim_dirband_free(struct super_block *s, secno sec)
0052 {
0053     struct hpfs_sb_info *sbi = hpfs_sb(s);
0054     if (sbi->sb_n_free_dnodes != (unsigned)-1) {
0055         if (unlikely(sbi->sb_n_free_dnodes >= sbi->sb_dirband_size / 4)) {
0056             hpfs_error(s, "dirband free count overflow, freeing sector %08x", sec);
0057             sbi->sb_n_free_dnodes = -1;
0058             return;
0059         }
0060         sbi->sb_n_free_dnodes++;
0061     }
0062 }
0063
0064 /*
0065  * Check if a sector is allocated in bitmap
0066  * This is really slow. Turned on only if chk==2
0067  */
0068
0069 static int chk_if_allocated(struct super_block *s, secno sec, char *msg)
0070 {
0071     struct quad_buffer_head qbh;
0072     __le32 *bmp;
0073     if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "chk"))) goto fail;
0074     if ((le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f)) & 1) {
0075         hpfs_error(s, "sector '%s' - %08x not allocated in bitmap", msg, sec);
0076         goto fail1;
0077     }
0078     hpfs_brelse4(&qbh);
0079     if (sec >= hpfs_sb(s)->sb_dirband_start && sec < hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
0080         unsigned ssec = (sec - hpfs_sb(s)->sb_dirband_start) / 4;
0081         if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto fail;
0082         if ((le32_to_cpu(bmp[ssec >> 5]) >> (ssec & 0x1f)) & 1) {
0083             hpfs_error(s, "sector '%s' - %08x not allocated in directory bitmap", msg, sec);
0084             goto fail1;
0085         }
0086         hpfs_brelse4(&qbh);
0087     }
0088     return 0;
0089     fail1:
0090     hpfs_brelse4(&qbh);
0091     fail:
0092     return 1;
0093 }
0094
0095 /*
0096  * Check if sector(s) have proper number and additionally check if they're
0097  * allocated in bitmap.
0098  */
0099
0100 int hpfs_chk_sectors(struct super_block *s, secno start, int len, char *msg)
0101 {
0102     if (start + len < start || start < 0x12 ||
0103         start + len > hpfs_sb(s)->sb_fs_size) {
0104             hpfs_error(s, "sector(s) '%s' badly placed at %08x", msg, start);
0105         return 1;
0106     }
0107     if (hpfs_sb(s)->sb_chk>=2) {
0108         int i;
0109         for (i = 0; i < len; i++)
0110             if (chk_if_allocated(s, start + i, msg)) return 1;
0111     }
0112     return 0;
0113 }
0114
0115 static secno alloc_in_bmp(struct super_block *s, secno near, unsigned n, unsigned forward)
0116 {
0117     struct quad_buffer_head qbh;
0118     __le32 *bmp;
0119     unsigned bs = near & ~0x3fff;
0120     unsigned nr = (near & 0x3fff) & ~(n - 1);
0121     /*unsigned mnr;*/
0122     unsigned i, q;
0123     int a, b;
0124     secno ret = 0;
0125     if (n != 1 && n != 4) {
0126         hpfs_error(s, "Bad allocation size: %d", n);
0127         return 0;
0128     }
0129     if (bs != ~0x3fff) {
0130         if (!(bmp = hpfs_map_bitmap(s, near >> 14, &qbh, "aib"))) goto uls;
0131     } else {
0132         if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto uls;
0133     }
0134     if (!tstbits(bmp, nr, n + forward)) {
0135         ret = bs + nr;
0136         goto rt;
0137     }
0138     q = nr + n; b = 0;
0139     while ((a = tstbits(bmp, q, n + forward)) != 0) {
0140         q += a;
0141         if (n != 1) q = ((q-1)&~(n-1))+n;
0142         if (!b) {
0143             if (q>>5 != nr>>5) {
0144                 b = 1;
0145                 q = nr & 0x1f;
0146             }
0147         } else if (q > nr) break;
0148     }
0149     if (!a) {
0150         ret = bs + q;
0151         goto rt;
0152     }
0153     nr >>= 5;
0154     /*for (i = nr + 1; i != nr; i++, i &= 0x1ff) */
0155     i = nr;
0156     do {
0157         if (!le32_to_cpu(bmp[i])) goto cont;
0158         if (n + forward >= 0x3f && le32_to_cpu(bmp[i]) != 0xffffffff) goto cont;
0159         q = i<<5;
0160         if (i > 0) {
0161             unsigned k = le32_to_cpu(bmp[i-1]);
0162             while (k & 0x80000000) {
0163                 q--; k <<= 1;
0164             }
0165         }
0166         if (n != 1) q = ((q-1)&~(n-1))+n;
0167         while ((a = tstbits(bmp, q, n + forward)) != 0) {
0168             q += a;
0169             if (n != 1) q = ((q-1)&~(n-1))+n;
0170             if (q>>5 > i) break;
0171         }
0172         if (!a) {
0173             ret = bs + q;
0174             goto rt;
0175         }
0176         cont:
0177         i++, i &= 0x1ff;
0178     } while (i != nr);
0179     rt:
0180     if (ret) {
0181         if (hpfs_sb(s)->sb_chk && ((ret >> 14) != (bs >> 14) || (le32_to_cpu(bmp[(ret & 0x3fff) >> 5]) | ~(((1 << n) - 1) << (ret & 0x1f))) != 0xffffffff)) {
0182             hpfs_error(s, "Allocation doesn't work! Wanted %d, allocated at %08x", n, ret);
0183             ret = 0;
0184             goto b;
0185         }
0186         bmp[(ret & 0x3fff) >> 5] &= cpu_to_le32(~(((1 << n) - 1) << (ret & 0x1f)));
0187         hpfs_mark_4buffers_dirty(&qbh);
0188     }
0189     b:
0190     hpfs_brelse4(&qbh);
0191     uls:
0192     return ret;
0193 }
0194
0195 /*
0196  * Allocation strategy: 1) search place near the sector specified
0197  *          2) search bitmap where free sectors last found
0198  *          3) search all bitmaps
0199  *          4) search all bitmaps ignoring number of pre-allocated
0200  *              sectors
0201  */
0202
0203 secno hpfs_alloc_sector(struct super_block *s, secno near, unsigned n, int forward)
0204 {
0205     secno sec;
0206     int i;
0207     unsigned n_bmps;
0208     struct hpfs_sb_info *sbi = hpfs_sb(s);
0209     int f_p = 0;
0210     int near_bmp;
0211     if (forward < 0) {
0212         forward = -forward;
0213         f_p = 1;
0214     }
0215     n_bmps = (sbi->sb_fs_size + 0x4000 - 1) >> 14;
0216     if (near && near < sbi->sb_fs_size) {
0217         if ((sec = alloc_in_bmp(s, near, n, f_p ? forward : forward/4))) goto ret;
0218         near_bmp = near >> 14;
0219     } else near_bmp = n_bmps / 2;
0220     /*
0221     if (b != -1) {
0222         if ((sec = alloc_in_bmp(s, b<<14, n, f_p ? forward : forward/2))) {
0223             b &= 0x0fffffff;
0224             goto ret;
0225         }
0226         if (b > 0x10000000) if ((sec = alloc_in_bmp(s, (b&0xfffffff)<<14, n, f_p ? forward : 0))) goto ret;
0227     */
0228     if (!f_p) if (forward > sbi->sb_max_fwd_alloc) forward = sbi->sb_max_fwd_alloc;
0229     less_fwd:
0230     for (i = 0; i < n_bmps; i++) {
0231         if (near_bmp+i < n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i) << 14, n, forward)))) {
0232             sbi->sb_c_bitmap = near_bmp+i;
0233             goto ret;
0234         }
0235         if (!forward) {
0236             if (near_bmp-i-1 >= 0 && ((sec = alloc_in_bmp(s, (near_bmp-i-1) << 14, n, forward)))) {
0237                 sbi->sb_c_bitmap = near_bmp-i-1;
0238                 goto ret;
0239             }
0240         } else {
0241             if (near_bmp+i >= n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i-n_bmps) << 14, n, forward)))) {
0242                 sbi->sb_c_bitmap = near_bmp+i-n_bmps;
0243                 goto ret;
0244             }
0245         }
0246         if (i == 1 && sbi->sb_c_bitmap != -1 && ((sec = alloc_in_bmp(s, (sbi->sb_c_bitmap) << 14, n, forward)))) {
0247             goto ret;
0248         }
0249     }
0250     if (!f_p) {
0251         if (forward) {
0252             sbi->sb_max_fwd_alloc = forward * 3 / 4;
0253             forward /= 2;
0254             goto less_fwd;
0255         }
0256     }
0257     sec = 0;
0258     ret:
0259     if (sec) {
0260         i = 0;
0261         do
0262             hpfs_claim_alloc(s, sec + i);
0263         while (unlikely(++i < n));
0264     }
0265     if (sec && f_p) {
0266         for (i = 0; i < forward; i++) {
0267             if (!hpfs_alloc_if_possible(s, sec + n + i)) {
0268                 hpfs_error(s, "Prealloc doesn't work! Wanted %d, allocated at %08x, can't allocate %d", forward, sec, i);
0269                 sec = 0;
0270                 break;
0271             }
0272         }
0273     }
0274     return sec;
0275 }
0276
0277 static secno alloc_in_dirband(struct super_block *s, secno near)
0278 {
0279     unsigned nr = near;
0280     secno sec;
0281     struct hpfs_sb_info *sbi = hpfs_sb(s);
0282     if (nr < sbi->sb_dirband_start)
0283         nr = sbi->sb_dirband_start;
0284     if (nr >= sbi->sb_dirband_start + sbi->sb_dirband_size)
0285         nr = sbi->sb_dirband_start + sbi->sb_dirband_size - 4;
0286     nr -= sbi->sb_dirband_start;
0287     nr >>= 2;
0288     sec = alloc_in_bmp(s, (~0x3fff) | nr, 1, 0);
0289     if (!sec) return 0;
0290     hpfs_claim_dirband_alloc(s, sec);
0291     return ((sec & 0x3fff) << 2) + sbi->sb_dirband_start;
0292 }
0293
0294 /* Alloc sector if it's free */
0295
0296 int hpfs_alloc_if_possible(struct super_block *s, secno sec)
0297 {
0298     struct quad_buffer_head qbh;
0299     __le32 *bmp;
0300     if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "aip"))) goto end;
0301     if (le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) & (1 << (sec & 0x1f))) {
0302         bmp[(sec & 0x3fff) >> 5] &= cpu_to_le32(~(1 << (sec & 0x1f)));
0303         hpfs_mark_4buffers_dirty(&qbh);
0304         hpfs_brelse4(&qbh);
0305         hpfs_claim_alloc(s, sec);
0306         return 1;
0307     }
0308     hpfs_brelse4(&qbh);
0309     end:
0310     return 0;
0311 }
0312
0313 /* Free sectors in bitmaps */
0314
0315 void hpfs_free_sectors(struct super_block *s, secno sec, unsigned n)
0316 {
0317     struct quad_buffer_head qbh;
0318     __le32 *bmp;
0319     struct hpfs_sb_info *sbi = hpfs_sb(s);
0320     /*pr_info("2 - ");*/
0321     if (!n) return;
0322     if (sec < 0x12) {
0323         hpfs_error(s, "Trying to free reserved sector %08x", sec);
0324         return;
0325     }
0326     sbi->sb_max_fwd_alloc += n > 0xffff ? 0xffff : n;
0327     if (sbi->sb_max_fwd_alloc > 0xffffff) sbi->sb_max_fwd_alloc = 0xffffff;
0328     new_map:
0329     if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "free"))) {
0330         return;
0331     }
0332     new_tst:
0333     if ((le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f) & 1)) {
0334         hpfs_error(s, "sector %08x not allocated", sec);
0335         hpfs_brelse4(&qbh);
0336         return;
0337     }
0338     bmp[(sec & 0x3fff) >> 5] |= cpu_to_le32(1 << (sec & 0x1f));
0339     hpfs_claim_free(s, sec);
0340     if (!--n) {
0341         hpfs_mark_4buffers_dirty(&qbh);
0342         hpfs_brelse4(&qbh);
0343         return;
0344     }
0345     if (!(++sec & 0x3fff)) {
0346         hpfs_mark_4buffers_dirty(&qbh);
0347         hpfs_brelse4(&qbh);
0348         goto new_map;
0349     }
0350     goto new_tst;
0351 }
0352
0353 /*
0354  * Check if there are at least n free dnodes on the filesystem.
0355  * Called before adding to dnode. If we run out of space while
0356  * splitting dnodes, it would corrupt dnode tree.
0357  */
0358
0359 int hpfs_check_free_dnodes(struct super_block *s, int n)
0360 {
0361     int n_bmps = (hpfs_sb(s)->sb_fs_size + 0x4000 - 1) >> 14;
0362     int b = hpfs_sb(s)->sb_c_bitmap & 0x0fffffff;
0363     int i, j;
0364     __le32 *bmp;
0365     struct quad_buffer_head qbh;
0366     if ((bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
0367         for (j = 0; j < 512; j++) {
0368             unsigned k;
0369             if (!le32_to_cpu(bmp[j])) continue;
0370             for (k = le32_to_cpu(bmp[j]); k; k >>= 1) if (k & 1) if (!--n) {
0371                 hpfs_brelse4(&qbh);
0372                 return 0;
0373             }
0374         }
0375     }
0376     hpfs_brelse4(&qbh);
0377     i = 0;
0378     if (hpfs_sb(s)->sb_c_bitmap != -1) {
0379         bmp = hpfs_map_bitmap(s, b, &qbh, "chkdn1");
0380         goto chk_bmp;
0381     }
0382     chk_next:
0383     if (i == b) i++;
0384     if (i >= n_bmps) return 1;
0385     bmp = hpfs_map_bitmap(s, i, &qbh, "chkdn2");
0386     chk_bmp:
0387     if (bmp) {
0388         for (j = 0; j < 512; j++) {
0389             u32 k;
0390             if (!le32_to_cpu(bmp[j])) continue;
0391             for (k = 0xf; k; k <<= 4)
0392                 if ((le32_to_cpu(bmp[j]) & k) == k) {
0393                     if (!--n) {
0394                         hpfs_brelse4(&qbh);
0395                         return 0;
0396                     }
0397                 }
0398         }
0399         hpfs_brelse4(&qbh);
0400     }
0401     i++;
0402     goto chk_next;
0403 }
0404
0405 void hpfs_free_dnode(struct super_block *s, dnode_secno dno)
0406 {
0407     if (hpfs_sb(s)->sb_chk) if (dno & 3) {
0408         hpfs_error(s, "hpfs_free_dnode: dnode %08x not aligned", dno);
0409         return;
0410     }
0411     if (dno < hpfs_sb(s)->sb_dirband_start ||
0412         dno >= hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
0413         hpfs_free_sectors(s, dno, 4);
0414     } else {
0415         struct quad_buffer_head qbh;
0416         __le32 *bmp;
0417         unsigned ssec = (dno - hpfs_sb(s)->sb_dirband_start) / 4;
0418         if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
0419             return;
0420         }
0421         bmp[ssec >> 5] |= cpu_to_le32(1 << (ssec & 0x1f));
0422         hpfs_mark_4buffers_dirty(&qbh);
0423         hpfs_brelse4(&qbh);
0424         hpfs_claim_dirband_free(s, dno);
0425     }
0426 }
0427
0428 struct dnode *hpfs_alloc_dnode(struct super_block *s, secno near,
0429              dnode_secno *dno, struct quad_buffer_head *qbh)
0430 {
0431     struct dnode *d;
0432     if (hpfs_get_free_dnodes(s) > FREE_DNODES_ADD) {
0433         if (!(*dno = alloc_in_dirband(s, near)))
0434             if (!(*dno = hpfs_alloc_sector(s, near, 4, 0))) return NULL;
0435     } else {
0436         if (!(*dno = hpfs_alloc_sector(s, near, 4, 0)))
0437             if (!(*dno = alloc_in_dirband(s, near))) return NULL;
0438     }
0439     if (!(d = hpfs_get_4sectors(s, *dno, qbh))) {
0440         hpfs_free_dnode(s, *dno);
0441         return NULL;
0442     }
0443     memset(d, 0, 2048);
0444     d->magic = cpu_to_le32(DNODE_MAGIC);
0445     d->first_free = cpu_to_le32(52);
0446     d->dirent[0] = 32;
0447     d->dirent[2] = 8;
0448     d->dirent[30] = 1;
0449     d->dirent[31] = 255;
0450     d->self = cpu_to_le32(*dno);
0451     return d;
0452 }
0453
0454 struct fnode *hpfs_alloc_fnode(struct super_block *s, secno near, fnode_secno *fno,
0455               struct buffer_head **bh)
0456 {
0457     struct fnode *f;
0458     if (!(*fno = hpfs_alloc_sector(s, near, 1, FNODE_ALLOC_FWD))) return NULL;
0459     if (!(f = hpfs_get_sector(s, *fno, bh))) {
0460         hpfs_free_sectors(s, *fno, 1);
0461         return NULL;
0462     }
0463     memset(f, 0, 512);
0464     f->magic = cpu_to_le32(FNODE_MAGIC);
0465     f->ea_offs = cpu_to_le16(0xc4);
0466     f->btree.n_free_nodes = 8;
0467     f->btree.first_free = cpu_to_le16(8);
0468     return f;
0469 }
0470
0471 struct anode *hpfs_alloc_anode(struct super_block *s, secno near, anode_secno *ano,
0472               struct buffer_head **bh)
0473 {
0474     struct anode *a;
0475     if (!(*ano = hpfs_alloc_sector(s, near, 1, ANODE_ALLOC_FWD))) return NULL;
0476     if (!(a = hpfs_get_sector(s, *ano, bh))) {
0477         hpfs_free_sectors(s, *ano, 1);
0478         return NULL;
0479     }
0480     memset(a, 0, 512);
0481     a->magic = cpu_to_le32(ANODE_MAGIC);
0482     a->self = cpu_to_le32(*ano);
0483     a->btree.n_free_nodes = 40;
0484     a->btree.n_used_nodes = 0;
0485     a->btree.first_free = cpu_to_le16(8);
0486     return a;
0487 }
0488
0489 static unsigned find_run(__le32 *bmp, unsigned *idx)
0490 {
0491     unsigned len;
0492     while (tstbits(bmp, *idx, 1)) {
0493         (*idx)++;
0494         if (unlikely(*idx >= 0x4000))
0495             return 0;
0496     }
0497     len = 1;
0498     while (!tstbits(bmp, *idx + len, 1))
0499         len++;
0500     return len;
0501 }
0502
0503 static int do_trim(struct super_block *s, secno start, unsigned len, secno limit_start, secno limit_end, unsigned minlen, unsigned *result)
0504 {
0505     int err;
0506     secno end;
0507     if (fatal_signal_pending(current))
0508         return -EINTR;
0509     end = start + len;
0510     if (start < limit_start)
0511         start = limit_start;
0512     if (end > limit_end)
0513         end = limit_end;
0514     if (start >= end)
0515         return 0;
0516     if (end - start < minlen)
0517         return 0;
0518     err = sb_issue_discard(s, start, end - start, GFP_NOFS, 0);
0519     if (err)
0520         return err;
0521     *result += end - start;
0522     return 0;
0523 }
0524
0525 int hpfs_trim_fs(struct super_block *s, u64 start, u64 end, u64 minlen, unsigned *result)
0526 {
0527     int err = 0;
0528     struct hpfs_sb_info *sbi = hpfs_sb(s);
0529     unsigned idx, len, start_bmp, end_bmp;
0530     __le32 *bmp;
0531     struct quad_buffer_head qbh;
0532
0533     *result = 0;
0534     if (!end || end > sbi->sb_fs_size)
0535         end = sbi->sb_fs_size;
0536     if (start >= sbi->sb_fs_size)
0537         return 0;
0538     if (minlen > 0x4000)
0539         return 0;
0540     if (start < sbi->sb_dirband_start + sbi->sb_dirband_size && end > sbi->sb_dirband_start) {
0541         hpfs_lock(s);
0542         if (sb_rdonly(s)) {
0543             err = -EROFS;
0544             goto unlock_1;
0545         }
0546         if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
0547             err = -EIO;
0548             goto unlock_1;
0549         }
0550         idx = 0;
0551         while ((len = find_run(bmp, &idx)) && !err) {
0552             err = do_trim(s, sbi->sb_dirband_start + idx * 4, len * 4, start, end, minlen, result);
0553             idx += len;
0554         }
0555         hpfs_brelse4(&qbh);
0556 unlock_1:
0557         hpfs_unlock(s);
0558     }
0559     start_bmp = start >> 14;
0560     end_bmp = (end + 0x3fff) >> 14;
0561     while (start_bmp < end_bmp && !err) {
0562         hpfs_lock(s);
0563         if (sb_rdonly(s)) {
0564             err = -EROFS;
0565             goto unlock_2;
0566         }
0567         if (!(bmp = hpfs_map_bitmap(s, start_bmp, &qbh, "trim"))) {
0568             err = -EIO;
0569             goto unlock_2;
0570         }
0571         idx = 0;
0572         while ((len = find_run(bmp, &idx)) && !err) {
0573             err = do_trim(s, (start_bmp << 14) + idx, len, start, end, minlen, result);
0574             idx += len;
0575         }
0576         hpfs_brelse4(&qbh);
0577 unlock_2:
0578         hpfs_unlock(s);
0579         start_bmp++;
0580     }
0581     return err;
0582 }