Back to home page

OSCL-LXR

 
 

    


0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hpfs/anode.c
0004  *
0005  *  Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
0006  *
0007  *  handling HPFS anode tree that contains file allocation info
0008  */
0009 
0010 #include "hpfs_fn.h"
0011 
0012 /* Find a sector in allocation tree */
0013 
0014 secno hpfs_bplus_lookup(struct super_block *s, struct inode *inode,
0015            struct bplus_header *btree, unsigned sec,
0016            struct buffer_head *bh)
0017 {
0018     anode_secno a = -1;
0019     struct anode *anode;
0020     int i;
0021     int c1, c2 = 0;
0022     go_down:
0023     if (hpfs_sb(s)->sb_chk) if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_bplus_lookup")) return -1;
0024     if (bp_internal(btree)) {
0025         for (i = 0; i < btree->n_used_nodes; i++)
0026             if (le32_to_cpu(btree->u.internal[i].file_secno) > sec) {
0027                 a = le32_to_cpu(btree->u.internal[i].down);
0028                 brelse(bh);
0029                 if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
0030                 btree = &anode->btree;
0031                 goto go_down;
0032             }
0033         hpfs_error(s, "sector %08x not found in internal anode %08x", sec, a);
0034         brelse(bh);
0035         return -1;
0036     }
0037     for (i = 0; i < btree->n_used_nodes; i++)
0038         if (le32_to_cpu(btree->u.external[i].file_secno) <= sec &&
0039             le32_to_cpu(btree->u.external[i].file_secno) + le32_to_cpu(btree->u.external[i].length) > sec) {
0040             a = le32_to_cpu(btree->u.external[i].disk_secno) + sec - le32_to_cpu(btree->u.external[i].file_secno);
0041             if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, a, 1, "data")) {
0042                 brelse(bh);
0043                 return -1;
0044             }
0045             if (inode) {
0046                 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
0047                 hpfs_inode->i_file_sec = le32_to_cpu(btree->u.external[i].file_secno);
0048                 hpfs_inode->i_disk_sec = le32_to_cpu(btree->u.external[i].disk_secno);
0049                 hpfs_inode->i_n_secs = le32_to_cpu(btree->u.external[i].length);
0050             }
0051             brelse(bh);
0052             return a;
0053         }
0054     hpfs_error(s, "sector %08x not found in external anode %08x", sec, a);
0055     brelse(bh);
0056     return -1;
0057 }
0058 
0059 /* Add a sector to tree */
0060 
0061 secno hpfs_add_sector_to_btree(struct super_block *s, secno node, int fnod, unsigned fsecno)
0062 {
0063     struct bplus_header *btree;
0064     struct anode *anode = NULL, *ranode = NULL;
0065     struct fnode *fnode;
0066     anode_secno a, na = -1, ra, up = -1;
0067     secno se;
0068     struct buffer_head *bh, *bh1, *bh2;
0069     int n;
0070     unsigned fs;
0071     int c1, c2 = 0;
0072     if (fnod) {
0073         if (!(fnode = hpfs_map_fnode(s, node, &bh))) return -1;
0074         btree = &fnode->btree;
0075     } else {
0076         if (!(anode = hpfs_map_anode(s, node, &bh))) return -1;
0077         btree = &anode->btree;
0078     }
0079     a = node;
0080     go_down:
0081     if ((n = btree->n_used_nodes - 1) < -!!fnod) {
0082         hpfs_error(s, "anode %08x has no entries", a);
0083         brelse(bh);
0084         return -1;
0085     }
0086     if (bp_internal(btree)) {
0087         a = le32_to_cpu(btree->u.internal[n].down);
0088         btree->u.internal[n].file_secno = cpu_to_le32(-1);
0089         mark_buffer_dirty(bh);
0090         brelse(bh);
0091         if (hpfs_sb(s)->sb_chk)
0092             if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_add_sector_to_btree #1")) return -1;
0093         if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
0094         btree = &anode->btree;
0095         goto go_down;
0096     }
0097     if (n >= 0) {
0098         if (le32_to_cpu(btree->u.external[n].file_secno) + le32_to_cpu(btree->u.external[n].length) != fsecno) {
0099             hpfs_error(s, "allocated size %08x, trying to add sector %08x, %cnode %08x",
0100                 le32_to_cpu(btree->u.external[n].file_secno) + le32_to_cpu(btree->u.external[n].length), fsecno,
0101                 fnod?'f':'a', node);
0102             brelse(bh);
0103             return -1;
0104         }
0105         if (hpfs_alloc_if_possible(s, se = le32_to_cpu(btree->u.external[n].disk_secno) + le32_to_cpu(btree->u.external[n].length))) {
0106             le32_add_cpu(&btree->u.external[n].length, 1);
0107             mark_buffer_dirty(bh);
0108             brelse(bh);
0109             return se;
0110         }
0111     } else {
0112         if (fsecno) {
0113             hpfs_error(s, "empty file %08x, trying to add sector %08x", node, fsecno);
0114             brelse(bh);
0115             return -1;
0116         }
0117         se = !fnod ? node : (node + 16384) & ~16383;
0118     }   
0119     if (!(se = hpfs_alloc_sector(s, se, 1, fsecno*ALLOC_M>ALLOC_FWD_MAX ? ALLOC_FWD_MAX : fsecno*ALLOC_M<ALLOC_FWD_MIN ? ALLOC_FWD_MIN : fsecno*ALLOC_M))) {
0120         brelse(bh);
0121         return -1;
0122     }
0123     fs = n < 0 ? 0 : le32_to_cpu(btree->u.external[n].file_secno) + le32_to_cpu(btree->u.external[n].length);
0124     if (!btree->n_free_nodes) {
0125         up = a != node ? le32_to_cpu(anode->up) : -1;
0126         if (!(anode = hpfs_alloc_anode(s, a, &na, &bh1))) {
0127             brelse(bh);
0128             hpfs_free_sectors(s, se, 1);
0129             return -1;
0130         }
0131         if (a == node && fnod) {
0132             anode->up = cpu_to_le32(node);
0133             anode->btree.flags |= BP_fnode_parent;
0134             anode->btree.n_used_nodes = btree->n_used_nodes;
0135             anode->btree.first_free = btree->first_free;
0136             anode->btree.n_free_nodes = 40 - anode->btree.n_used_nodes;
0137             memcpy(&anode->u, &btree->u, btree->n_used_nodes * 12);
0138             btree->flags |= BP_internal;
0139             btree->n_free_nodes = 11;
0140             btree->n_used_nodes = 1;
0141             btree->first_free = cpu_to_le16((char *)&(btree->u.internal[1]) - (char *)btree);
0142             btree->u.internal[0].file_secno = cpu_to_le32(-1);
0143             btree->u.internal[0].down = cpu_to_le32(na);
0144             mark_buffer_dirty(bh);
0145         } else if (!(ranode = hpfs_alloc_anode(s, /*a*/0, &ra, &bh2))) {
0146             brelse(bh);
0147             brelse(bh1);
0148             hpfs_free_sectors(s, se, 1);
0149             hpfs_free_sectors(s, na, 1);
0150             return -1;
0151         }
0152         brelse(bh);
0153         bh = bh1;
0154         btree = &anode->btree;
0155     }
0156     btree->n_free_nodes--; n = btree->n_used_nodes++;
0157     le16_add_cpu(&btree->first_free, 12);
0158     btree->u.external[n].disk_secno = cpu_to_le32(se);
0159     btree->u.external[n].file_secno = cpu_to_le32(fs);
0160     btree->u.external[n].length = cpu_to_le32(1);
0161     mark_buffer_dirty(bh);
0162     brelse(bh);
0163     if ((a == node && fnod) || na == -1) return se;
0164     c2 = 0;
0165     while (up != (anode_secno)-1) {
0166         struct anode *new_anode;
0167         if (hpfs_sb(s)->sb_chk)
0168             if (hpfs_stop_cycles(s, up, &c1, &c2, "hpfs_add_sector_to_btree #2")) return -1;
0169         if (up != node || !fnod) {
0170             if (!(anode = hpfs_map_anode(s, up, &bh))) return -1;
0171             btree = &anode->btree;
0172         } else {
0173             if (!(fnode = hpfs_map_fnode(s, up, &bh))) return -1;
0174             btree = &fnode->btree;
0175         }
0176         if (btree->n_free_nodes) {
0177             btree->n_free_nodes--; n = btree->n_used_nodes++;
0178             le16_add_cpu(&btree->first_free, 8);
0179             btree->u.internal[n].file_secno = cpu_to_le32(-1);
0180             btree->u.internal[n].down = cpu_to_le32(na);
0181             btree->u.internal[n-1].file_secno = cpu_to_le32(fs);
0182             mark_buffer_dirty(bh);
0183             brelse(bh);
0184             brelse(bh2);
0185             hpfs_free_sectors(s, ra, 1);
0186             if ((anode = hpfs_map_anode(s, na, &bh))) {
0187                 anode->up = cpu_to_le32(up);
0188                 if (up == node && fnod)
0189                     anode->btree.flags |= BP_fnode_parent;
0190                 else
0191                     anode->btree.flags &= ~BP_fnode_parent;
0192                 mark_buffer_dirty(bh);
0193                 brelse(bh);
0194             }
0195             return se;
0196         }
0197         up = up != node ? le32_to_cpu(anode->up) : -1;
0198         btree->u.internal[btree->n_used_nodes - 1].file_secno = cpu_to_le32(/*fs*/-1);
0199         mark_buffer_dirty(bh);
0200         brelse(bh);
0201         a = na;
0202         if ((new_anode = hpfs_alloc_anode(s, a, &na, &bh))) {
0203             anode = new_anode;
0204             /*anode->up = cpu_to_le32(up != -1 ? up : ra);*/
0205             anode->btree.flags |= BP_internal;
0206             anode->btree.n_used_nodes = 1;
0207             anode->btree.n_free_nodes = 59;
0208             anode->btree.first_free = cpu_to_le16(16);
0209             anode->btree.u.internal[0].down = cpu_to_le32(a);
0210             anode->btree.u.internal[0].file_secno = cpu_to_le32(-1);
0211             mark_buffer_dirty(bh);
0212             brelse(bh);
0213             if ((anode = hpfs_map_anode(s, a, &bh))) {
0214                 anode->up = cpu_to_le32(na);
0215                 mark_buffer_dirty(bh);
0216                 brelse(bh);
0217             }
0218         } else na = a;
0219     }
0220     if ((anode = hpfs_map_anode(s, na, &bh))) {
0221         anode->up = cpu_to_le32(node);
0222         if (fnod)
0223             anode->btree.flags |= BP_fnode_parent;
0224         mark_buffer_dirty(bh);
0225         brelse(bh);
0226     }
0227     if (!fnod) {
0228         if (!(anode = hpfs_map_anode(s, node, &bh))) {
0229             brelse(bh2);
0230             return -1;
0231         }
0232         btree = &anode->btree;
0233     } else {
0234         if (!(fnode = hpfs_map_fnode(s, node, &bh))) {
0235             brelse(bh2);
0236             return -1;
0237         }
0238         btree = &fnode->btree;
0239     }
0240     ranode->up = cpu_to_le32(node);
0241     memcpy(&ranode->btree, btree, le16_to_cpu(btree->first_free));
0242     if (fnod)
0243         ranode->btree.flags |= BP_fnode_parent;
0244     ranode->btree.n_free_nodes = (bp_internal(&ranode->btree) ? 60 : 40) - ranode->btree.n_used_nodes;
0245     if (bp_internal(&ranode->btree)) for (n = 0; n < ranode->btree.n_used_nodes; n++) {
0246         struct anode *unode;
0247         if ((unode = hpfs_map_anode(s, le32_to_cpu(ranode->u.internal[n].down), &bh1))) {
0248             unode->up = cpu_to_le32(ra);
0249             unode->btree.flags &= ~BP_fnode_parent;
0250             mark_buffer_dirty(bh1);
0251             brelse(bh1);
0252         }
0253     }
0254     btree->flags |= BP_internal;
0255     btree->n_free_nodes = fnod ? 10 : 58;
0256     btree->n_used_nodes = 2;
0257     btree->first_free = cpu_to_le16((char *)&btree->u.internal[2] - (char *)btree);
0258     btree->u.internal[0].file_secno = cpu_to_le32(fs);
0259     btree->u.internal[0].down = cpu_to_le32(ra);
0260     btree->u.internal[1].file_secno = cpu_to_le32(-1);
0261     btree->u.internal[1].down = cpu_to_le32(na);
0262     mark_buffer_dirty(bh);
0263     brelse(bh);
0264     mark_buffer_dirty(bh2);
0265     brelse(bh2);
0266     return se;
0267 }
0268 
0269 /*
0270  * Remove allocation tree. Recursion would look much nicer but
0271  * I want to avoid it because it can cause stack overflow.
0272  */
0273 
0274 void hpfs_remove_btree(struct super_block *s, struct bplus_header *btree)
0275 {
0276     struct bplus_header *btree1 = btree;
0277     struct anode *anode = NULL;
0278     anode_secno ano = 0, oano;
0279     struct buffer_head *bh;
0280     int level = 0;
0281     int pos = 0;
0282     int i;
0283     int c1, c2 = 0;
0284     int d1, d2;
0285     go_down:
0286     d2 = 0;
0287     while (bp_internal(btree1)) {
0288         ano = le32_to_cpu(btree1->u.internal[pos].down);
0289         if (level) brelse(bh);
0290         if (hpfs_sb(s)->sb_chk)
0291             if (hpfs_stop_cycles(s, ano, &d1, &d2, "hpfs_remove_btree #1"))
0292                 return;
0293         if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
0294         btree1 = &anode->btree;
0295         level++;
0296         pos = 0;
0297     }
0298     for (i = 0; i < btree1->n_used_nodes; i++)
0299         hpfs_free_sectors(s, le32_to_cpu(btree1->u.external[i].disk_secno), le32_to_cpu(btree1->u.external[i].length));
0300     go_up:
0301     if (!level) return;
0302     brelse(bh);
0303     if (hpfs_sb(s)->sb_chk)
0304         if (hpfs_stop_cycles(s, ano, &c1, &c2, "hpfs_remove_btree #2")) return;
0305     hpfs_free_sectors(s, ano, 1);
0306     oano = ano;
0307     ano = le32_to_cpu(anode->up);
0308     if (--level) {
0309         if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
0310         btree1 = &anode->btree;
0311     } else btree1 = btree;
0312     for (i = 0; i < btree1->n_used_nodes; i++) {
0313         if (le32_to_cpu(btree1->u.internal[i].down) == oano) {
0314             if ((pos = i + 1) < btree1->n_used_nodes)
0315                 goto go_down;
0316             else
0317                 goto go_up;
0318         }
0319     }
0320     hpfs_error(s,
0321            "reference to anode %08x not found in anode %08x "
0322            "(probably bad up pointer)",
0323            oano, level ? ano : -1);
0324     if (level)
0325         brelse(bh);
0326 }
0327 
0328 /* Just a wrapper around hpfs_bplus_lookup .. used for reading eas */
0329 
0330 static secno anode_lookup(struct super_block *s, anode_secno a, unsigned sec)
0331 {
0332     struct anode *anode;
0333     struct buffer_head *bh;
0334     if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
0335     return hpfs_bplus_lookup(s, NULL, &anode->btree, sec, bh);
0336 }
0337 
0338 int hpfs_ea_read(struct super_block *s, secno a, int ano, unsigned pos,
0339         unsigned len, char *buf)
0340 {
0341     struct buffer_head *bh;
0342     char *data;
0343     secno sec;
0344     unsigned l;
0345     while (len) {
0346         if (ano) {
0347             if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
0348                 return -1;
0349         } else sec = a + (pos >> 9);
0350         if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #1")) return -1;
0351         if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
0352             return -1;
0353         l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
0354         memcpy(buf, data + (pos & 0x1ff), l);
0355         brelse(bh);
0356         buf += l; pos += l; len -= l;
0357     }
0358     return 0;
0359 }
0360 
0361 int hpfs_ea_write(struct super_block *s, secno a, int ano, unsigned pos,
0362          unsigned len, const char *buf)
0363 {
0364     struct buffer_head *bh;
0365     char *data;
0366     secno sec;
0367     unsigned l;
0368     while (len) {
0369         if (ano) {
0370             if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
0371                 return -1;
0372         } else sec = a + (pos >> 9);
0373         if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #2")) return -1;
0374         if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
0375             return -1;
0376         l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
0377         memcpy(data + (pos & 0x1ff), buf, l);
0378         mark_buffer_dirty(bh);
0379         brelse(bh);
0380         buf += l; pos += l; len -= l;
0381     }
0382     return 0;
0383 }
0384 
0385 void hpfs_ea_remove(struct super_block *s, secno a, int ano, unsigned len)
0386 {
0387     struct anode *anode;
0388     struct buffer_head *bh;
0389     if (ano) {
0390         if (!(anode = hpfs_map_anode(s, a, &bh))) return;
0391         hpfs_remove_btree(s, &anode->btree);
0392         brelse(bh);
0393         hpfs_free_sectors(s, a, 1);
0394     } else hpfs_free_sectors(s, a, (len + 511) >> 9);
0395 }
0396 
0397 /* Truncate allocation tree. Doesn't join anodes - I hope it doesn't matter */
0398 
0399 void hpfs_truncate_btree(struct super_block *s, secno f, int fno, unsigned secs)
0400 {
0401     struct fnode *fnode;
0402     struct anode *anode;
0403     struct buffer_head *bh;
0404     struct bplus_header *btree;
0405     anode_secno node = f;
0406     int i, j, nodes;
0407     int c1, c2 = 0;
0408     if (fno) {
0409         if (!(fnode = hpfs_map_fnode(s, f, &bh))) return;
0410         btree = &fnode->btree;
0411     } else {
0412         if (!(anode = hpfs_map_anode(s, f, &bh))) return;
0413         btree = &anode->btree;
0414     }
0415     if (!secs) {
0416         hpfs_remove_btree(s, btree);
0417         if (fno) {
0418             btree->n_free_nodes = 8;
0419             btree->n_used_nodes = 0;
0420             btree->first_free = cpu_to_le16(8);
0421             btree->flags &= ~BP_internal;
0422             mark_buffer_dirty(bh);
0423         } else hpfs_free_sectors(s, f, 1);
0424         brelse(bh);
0425         return;
0426     }
0427     while (bp_internal(btree)) {
0428         nodes = btree->n_used_nodes + btree->n_free_nodes;
0429         for (i = 0; i < btree->n_used_nodes; i++)
0430             if (le32_to_cpu(btree->u.internal[i].file_secno) >= secs) goto f;
0431         brelse(bh);
0432         hpfs_error(s, "internal btree %08x doesn't end with -1", node);
0433         return;
0434         f:
0435         for (j = i + 1; j < btree->n_used_nodes; j++)
0436             hpfs_ea_remove(s, le32_to_cpu(btree->u.internal[j].down), 1, 0);
0437         btree->n_used_nodes = i + 1;
0438         btree->n_free_nodes = nodes - btree->n_used_nodes;
0439         btree->first_free = cpu_to_le16(8 + 8 * btree->n_used_nodes);
0440         mark_buffer_dirty(bh);
0441         if (btree->u.internal[i].file_secno == cpu_to_le32(secs)) {
0442             brelse(bh);
0443             return;
0444         }
0445         node = le32_to_cpu(btree->u.internal[i].down);
0446         brelse(bh);
0447         if (hpfs_sb(s)->sb_chk)
0448             if (hpfs_stop_cycles(s, node, &c1, &c2, "hpfs_truncate_btree"))
0449                 return;
0450         if (!(anode = hpfs_map_anode(s, node, &bh))) return;
0451         btree = &anode->btree;
0452     }   
0453     nodes = btree->n_used_nodes + btree->n_free_nodes;
0454     for (i = 0; i < btree->n_used_nodes; i++)
0455         if (le32_to_cpu(btree->u.external[i].file_secno) + le32_to_cpu(btree->u.external[i].length) >= secs) goto ff;
0456     brelse(bh);
0457     return;
0458     ff:
0459     if (secs <= le32_to_cpu(btree->u.external[i].file_secno)) {
0460         hpfs_error(s, "there is an allocation error in file %08x, sector %08x", f, secs);
0461         if (i) i--;
0462     }
0463     else if (le32_to_cpu(btree->u.external[i].file_secno) + le32_to_cpu(btree->u.external[i].length) > secs) {
0464         hpfs_free_sectors(s, le32_to_cpu(btree->u.external[i].disk_secno) + secs -
0465             le32_to_cpu(btree->u.external[i].file_secno), le32_to_cpu(btree->u.external[i].length)
0466             - secs + le32_to_cpu(btree->u.external[i].file_secno)); /* I hope gcc optimizes this :-) */
0467         btree->u.external[i].length = cpu_to_le32(secs - le32_to_cpu(btree->u.external[i].file_secno));
0468     }
0469     for (j = i + 1; j < btree->n_used_nodes; j++)
0470         hpfs_free_sectors(s, le32_to_cpu(btree->u.external[j].disk_secno), le32_to_cpu(btree->u.external[j].length));
0471     btree->n_used_nodes = i + 1;
0472     btree->n_free_nodes = nodes - btree->n_used_nodes;
0473     btree->first_free = cpu_to_le16(8 + 12 * btree->n_used_nodes);
0474     mark_buffer_dirty(bh);
0475     brelse(bh);
0476 }
0477 
0478 /* Remove file or directory and it's eas - note that directory must
0479    be empty when this is called. */
0480 
0481 void hpfs_remove_fnode(struct super_block *s, fnode_secno fno)
0482 {
0483     struct buffer_head *bh;
0484     struct fnode *fnode;
0485     struct extended_attribute *ea;
0486     struct extended_attribute *ea_end;
0487     if (!(fnode = hpfs_map_fnode(s, fno, &bh))) return;
0488     if (!fnode_is_dir(fnode)) hpfs_remove_btree(s, &fnode->btree);
0489     else hpfs_remove_dtree(s, le32_to_cpu(fnode->u.external[0].disk_secno));
0490     ea_end = fnode_end_ea(fnode);
0491     for (ea = fnode_ea(fnode); ea < ea_end; ea = next_ea(ea))
0492         if (ea_indirect(ea))
0493             hpfs_ea_remove(s, ea_sec(ea), ea_in_anode(ea), ea_len(ea));
0494     hpfs_ea_ext_remove(s, le32_to_cpu(fnode->ea_secno), fnode_in_anode(fnode), le32_to_cpu(fnode->ea_size_l));
0495     brelse(bh);
0496     hpfs_free_sectors(s, fno, 1);
0497 }