1/* 2 * linux/fs/hpfs/anode.c 3 * 4 * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999 5 * 6 * handling HPFS anode tree that contains file allocation info 7 */ 8 9#include "hpfs_fn.h" 10 11/* Find a sector in allocation tree */ 12 13secno hpfs_bplus_lookup(struct super_block *s, struct inode *inode, 14 struct bplus_header *btree, unsigned sec, 15 struct buffer_head *bh) 16{ 17 anode_secno a = -1; 18 struct anode *anode; 19 int i; 20 int c1, c2 = 0; 21 go_down: 22 if (hpfs_sb(s)->sb_chk) if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_bplus_lookup")) return -1; 23 if (btree->internal) { 24 for (i = 0; i < btree->n_used_nodes; i++) 25 if (btree->u.internal[i].file_secno > sec) { 26 a = btree->u.internal[i].down; 27 brelse(bh); 28 if (!(anode = hpfs_map_anode(s, a, &bh))) return -1; 29 btree = &anode->btree; 30 goto go_down; 31 } 32 hpfs_error(s, "sector %08x not found in internal anode %08x", sec, a); 33 brelse(bh); 34 return -1; 35 } 36 for (i = 0; i < btree->n_used_nodes; i++) 37 if (btree->u.external[i].file_secno <= sec && 38 btree->u.external[i].file_secno + btree->u.external[i].length > sec) { 39 a = btree->u.external[i].disk_secno + sec - btree->u.external[i].file_secno; 40 if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, a, 1, "data")) { 41 brelse(bh); 42 return -1; 43 } 44 if (inode) { 45 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode); 46 hpfs_inode->i_file_sec = btree->u.external[i].file_secno; 47 hpfs_inode->i_disk_sec = btree->u.external[i].disk_secno; 48 hpfs_inode->i_n_secs = btree->u.external[i].length; 49 } 50 brelse(bh); 51 return a; 52 } 53 hpfs_error(s, "sector %08x not found in external anode %08x", sec, a); 54 brelse(bh); 55 return -1; 56} 57 58/* Add a sector to tree */ 59 60secno hpfs_add_sector_to_btree(struct super_block *s, secno node, int fnod, unsigned fsecno) 61{ 62 struct bplus_header *btree; 63 struct anode *anode = NULL, *ranode = NULL; 64 struct fnode *fnode; 65 anode_secno a, na = -1, ra, up = -1; 66 secno se; 67 struct buffer_head *bh, *bh1, *bh2; 68 int n; 69 unsigned fs; 70 int c1, c2 = 0; 71 if (fnod) { 72 if (!(fnode = hpfs_map_fnode(s, node, &bh))) return -1; 73 btree = &fnode->btree; 74 } else { 75 if (!(anode = hpfs_map_anode(s, node, &bh))) return -1; 76 btree = &anode->btree; 77 } 78 a = node; 79 go_down: 80 if ((n = btree->n_used_nodes - 1) < -!!fnod) { 81 hpfs_error(s, "anode %08x has no entries", a); 82 brelse(bh); 83 return -1; 84 } 85 if (btree->internal) { 86 a = btree->u.internal[n].down; 87 btree->u.internal[n].file_secno = -1; 88 mark_buffer_dirty(bh); 89 brelse(bh); 90 if (hpfs_sb(s)->sb_chk) 91 if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_add_sector_to_btree #1")) return -1; 92 if (!(anode = hpfs_map_anode(s, a, &bh))) return -1; 93 btree = &anode->btree; 94 goto go_down; 95 } 96 if (n >= 0) { 97 if (btree->u.external[n].file_secno + btree->u.external[n].length != fsecno) { 98 hpfs_error(s, "allocated size %08x, trying to add sector %08x, %cnode %08x", 99 btree->u.external[n].file_secno + btree->u.external[n].length, fsecno, 100 fnod?'f':'a', node); 101 brelse(bh); 102 return -1; 103 } 104 if (hpfs_alloc_if_possible(s, se = btree->u.external[n].disk_secno + btree->u.external[n].length)) { 105 btree->u.external[n].length++; 106 mark_buffer_dirty(bh); 107 brelse(bh); 108 return se; 109 } 110 } else { 111 if (fsecno) { 112 hpfs_error(s, "empty file %08x, trying to add sector %08x", node, fsecno); 113 brelse(bh); 114 return -1; 115 } 116 se = !fnod ? node : (node + 16384) & ~16383; 117 } 118 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, 1))) { 119 brelse(bh); 120 return -1; 121 } 122 fs = n < 0 ? 0 : btree->u.external[n].file_secno + btree->u.external[n].length; 123 if (!btree->n_free_nodes) { 124 up = a != node ? anode->up : -1; 125 if (!(anode = hpfs_alloc_anode(s, a, &na, &bh1))) { 126 brelse(bh); 127 hpfs_free_sectors(s, se, 1); 128 return -1; 129 } 130 if (a == node && fnod) { 131 anode->up = node; 132 anode->btree.fnode_parent = 1; 133 anode->btree.n_used_nodes = btree->n_used_nodes; 134 anode->btree.first_free = btree->first_free; 135 anode->btree.n_free_nodes = 40 - anode->btree.n_used_nodes; 136 memcpy(&anode->u, &btree->u, btree->n_used_nodes * 12); 137 btree->internal = 1; 138 btree->n_free_nodes = 11; 139 btree->n_used_nodes = 1; 140 btree->first_free = (char *)&(btree->u.internal[1]) - (char *)btree; 141 btree->u.internal[0].file_secno = -1; 142 btree->u.internal[0].down = na; 143 mark_buffer_dirty(bh); 144 } else if (!(ranode = hpfs_alloc_anode(s, /*a*/0, &ra, &bh2))) { 145 brelse(bh); 146 brelse(bh1); 147 hpfs_free_sectors(s, se, 1); 148 hpfs_free_sectors(s, na, 1); 149 return -1; 150 } 151 brelse(bh); 152 bh = bh1; 153 btree = &anode->btree; 154 } 155 btree->n_free_nodes--; n = btree->n_used_nodes++; 156 btree->first_free += 12; 157 btree->u.external[n].disk_secno = se; 158 btree->u.external[n].file_secno = fs; 159 btree->u.external[n].length = 1; 160 mark_buffer_dirty(bh); 161 brelse(bh); 162 if ((a == node && fnod) || na == -1) return se; 163 c2 = 0; 164 while (up != -1) { 165 struct anode *new_anode; 166 if (hpfs_sb(s)->sb_chk) 167 if (hpfs_stop_cycles(s, up, &c1, &c2, "hpfs_add_sector_to_btree #2")) return -1; 168 if (up != node || !fnod) { 169 if (!(anode = hpfs_map_anode(s, up, &bh))) return -1; 170 btree = &anode->btree; 171 } else { 172 if (!(fnode = hpfs_map_fnode(s, up, &bh))) return -1; 173 btree = &fnode->btree; 174 } 175 if (btree->n_free_nodes) { 176 btree->n_free_nodes--; n = btree->n_used_nodes++; 177 btree->first_free += 8; 178 btree->u.internal[n].file_secno = -1; 179 btree->u.internal[n].down = na; 180 btree->u.internal[n-1].file_secno = fs; 181 mark_buffer_dirty(bh); 182 brelse(bh); 183 brelse(bh2); 184 hpfs_free_sectors(s, ra, 1); 185 if ((anode = hpfs_map_anode(s, na, &bh))) { 186 anode->up = up; 187 anode->btree.fnode_parent = up == node && fnod; 188 mark_buffer_dirty(bh); 189 brelse(bh); 190 } 191 return se; 192 } 193 up = up != node ? anode->up : -1; 194 btree->u.internal[btree->n_used_nodes - 1].file_secno = /*fs*/-1; 195 mark_buffer_dirty(bh); 196 brelse(bh); 197 a = na; 198 if ((new_anode = hpfs_alloc_anode(s, a, &na, &bh))) { 199 anode = new_anode; 200 /*anode->up = up != -1 ? up : ra;*/ 201 anode->btree.internal = 1; 202 anode->btree.n_used_nodes = 1; 203 anode->btree.n_free_nodes = 59; 204 anode->btree.first_free = 16; 205 anode->btree.u.internal[0].down = a; 206 anode->btree.u.internal[0].file_secno = -1; 207 mark_buffer_dirty(bh); 208 brelse(bh); 209 if ((anode = hpfs_map_anode(s, a, &bh))) { 210 anode->up = na; 211 mark_buffer_dirty(bh); 212 brelse(bh); 213 } 214 } else na = a; 215 } 216 if ((anode = hpfs_map_anode(s, na, &bh))) { 217 anode->up = node; 218 if (fnod) anode->btree.fnode_parent = 1; 219 mark_buffer_dirty(bh); 220 brelse(bh); 221 } 222 if (!fnod) { 223 if (!(anode = hpfs_map_anode(s, node, &bh))) { 224 brelse(bh2); 225 return -1; 226 } 227 btree = &anode->btree; 228 } else { 229 if (!(fnode = hpfs_map_fnode(s, node, &bh))) { 230 brelse(bh2); 231 return -1; 232 } 233 btree = &fnode->btree; 234 } 235 ranode->up = node; 236 memcpy(&ranode->btree, btree, btree->first_free); 237 if (fnod) ranode->btree.fnode_parent = 1; 238 ranode->btree.n_free_nodes = (ranode->btree.internal ? 60 : 40) - ranode->btree.n_used_nodes; 239 if (ranode->btree.internal) for (n = 0; n < ranode->btree.n_used_nodes; n++) { 240 struct anode *unode; 241 if ((unode = hpfs_map_anode(s, ranode->u.internal[n].down, &bh1))) { 242 unode->up = ra; 243 unode->btree.fnode_parent = 0; 244 mark_buffer_dirty(bh1); 245 brelse(bh1); 246 } 247 } 248 btree->internal = 1; 249 btree->n_free_nodes = fnod ? 10 : 58; 250 btree->n_used_nodes = 2; 251 btree->first_free = (char *)&btree->u.internal[2] - (char *)btree; 252 btree->u.internal[0].file_secno = fs; 253 btree->u.internal[0].down = ra; 254 btree->u.internal[1].file_secno = -1; 255 btree->u.internal[1].down = na; 256 mark_buffer_dirty(bh); 257 brelse(bh); 258 mark_buffer_dirty(bh2); 259 brelse(bh2); 260 return se; 261} 262 263/* 264 * Remove allocation tree. Recursion would look much nicer but 265 * I want to avoid it because it can cause stack overflow. 266 */ 267 268void hpfs_remove_btree(struct super_block *s, struct bplus_header *btree) 269{ 270 struct bplus_header *btree1 = btree; 271 struct anode *anode = NULL; 272 anode_secno ano = 0, oano; 273 struct buffer_head *bh; 274 int level = 0; 275 int pos = 0; 276 int i; 277 int c1, c2 = 0; 278 int d1, d2; 279 go_down: 280 d2 = 0; 281 while (btree1->internal) { 282 ano = btree1->u.internal[pos].down; 283 if (level) brelse(bh); 284 if (hpfs_sb(s)->sb_chk) 285 if (hpfs_stop_cycles(s, ano, &d1, &d2, "hpfs_remove_btree #1")) 286 return; 287 if (!(anode = hpfs_map_anode(s, ano, &bh))) return; 288 btree1 = &anode->btree; 289 level++; 290 pos = 0; 291 } 292 for (i = 0; i < btree1->n_used_nodes; i++) 293 hpfs_free_sectors(s, btree1->u.external[i].disk_secno, btree1->u.external[i].length); 294 go_up: 295 if (!level) return; 296 brelse(bh); 297 if (hpfs_sb(s)->sb_chk) 298 if (hpfs_stop_cycles(s, ano, &c1, &c2, "hpfs_remove_btree #2")) return; 299 hpfs_free_sectors(s, ano, 1); 300 oano = ano; 301 ano = anode->up; 302 if (--level) { 303 if (!(anode = hpfs_map_anode(s, ano, &bh))) return; 304 btree1 = &anode->btree; 305 } else btree1 = btree; 306 for (i = 0; i < btree1->n_used_nodes; i++) { 307 if (btree1->u.internal[i].down == oano) { 308 if ((pos = i + 1) < btree1->n_used_nodes) 309 goto go_down; 310 else 311 goto go_up; 312 } 313 } 314 hpfs_error(s, 315 "reference to anode %08x not found in anode %08x " 316 "(probably bad up pointer)", 317 oano, level ? ano : -1); 318 if (level) 319 brelse(bh); 320} 321 322/* Just a wrapper around hpfs_bplus_lookup .. used for reading eas */ 323 324static secno anode_lookup(struct super_block *s, anode_secno a, unsigned sec) 325{ 326 struct anode *anode; 327 struct buffer_head *bh; 328 if (!(anode = hpfs_map_anode(s, a, &bh))) return -1; 329 return hpfs_bplus_lookup(s, NULL, &anode->btree, sec, bh); 330} 331 332int hpfs_ea_read(struct super_block *s, secno a, int ano, unsigned pos, 333 unsigned len, char *buf) 334{ 335 struct buffer_head *bh; 336 char *data; 337 secno sec; 338 unsigned l; 339 while (len) { 340 if (ano) { 341 if ((sec = anode_lookup(s, a, pos >> 9)) == -1) 342 return -1; 343 } else sec = a + (pos >> 9); 344 if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #1")) return -1; 345 if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9))) 346 return -1; 347 l = 0x200 - (pos & 0x1ff); if (l > len) l = len; 348 memcpy(buf, data + (pos & 0x1ff), l); 349 brelse(bh); 350 buf += l; pos += l; len -= l; 351 } 352 return 0; 353} 354 355int hpfs_ea_write(struct super_block *s, secno a, int ano, unsigned pos, 356 unsigned len, const char *buf) 357{ 358 struct buffer_head *bh; 359 char *data; 360 secno sec; 361 unsigned l; 362 while (len) { 363 if (ano) { 364 if ((sec = anode_lookup(s, a, pos >> 9)) == -1) 365 return -1; 366 } else sec = a + (pos >> 9); 367 if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #2")) return -1; 368 if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9))) 369 return -1; 370 l = 0x200 - (pos & 0x1ff); if (l > len) l = len; 371 memcpy(data + (pos & 0x1ff), buf, l); 372 mark_buffer_dirty(bh); 373 brelse(bh); 374 buf += l; pos += l; len -= l; 375 } 376 return 0; 377} 378 379void hpfs_ea_remove(struct super_block *s, secno a, int ano, unsigned len) 380{ 381 struct anode *anode; 382 struct buffer_head *bh; 383 if (ano) { 384 if (!(anode = hpfs_map_anode(s, a, &bh))) return; 385 hpfs_remove_btree(s, &anode->btree); 386 brelse(bh); 387 hpfs_free_sectors(s, a, 1); 388 } else hpfs_free_sectors(s, a, (len + 511) >> 9); 389} 390 391/* Truncate allocation tree. Doesn't join anodes - I hope it doesn't matter */ 392 393void hpfs_truncate_btree(struct super_block *s, secno f, int fno, unsigned secs) 394{ 395 struct fnode *fnode; 396 struct anode *anode; 397 struct buffer_head *bh; 398 struct bplus_header *btree; 399 anode_secno node = f; 400 int i, j, nodes; 401 int c1, c2 = 0; 402 if (fno) { 403 if (!(fnode = hpfs_map_fnode(s, f, &bh))) return; 404 btree = &fnode->btree; 405 } else { 406 if (!(anode = hpfs_map_anode(s, f, &bh))) return; 407 btree = &anode->btree; 408 } 409 if (!secs) { 410 hpfs_remove_btree(s, btree); 411 if (fno) { 412 btree->n_free_nodes = 8; 413 btree->n_used_nodes = 0; 414 btree->first_free = 8; 415 btree->internal = 0; 416 mark_buffer_dirty(bh); 417 } else hpfs_free_sectors(s, f, 1); 418 brelse(bh); 419 return; 420 } 421 while (btree->internal) { 422 nodes = btree->n_used_nodes + btree->n_free_nodes; 423 for (i = 0; i < btree->n_used_nodes; i++) 424 if (btree->u.internal[i].file_secno >= secs) goto f; 425 brelse(bh); 426 hpfs_error(s, "internal btree %08x doesn't end with -1", node); 427 return; 428 f: 429 for (j = i + 1; j < btree->n_used_nodes; j++) 430 hpfs_ea_remove(s, btree->u.internal[j].down, 1, 0); 431 btree->n_used_nodes = i + 1; 432 btree->n_free_nodes = nodes - btree->n_used_nodes; 433 btree->first_free = 8 + 8 * btree->n_used_nodes; 434 mark_buffer_dirty(bh); 435 if (btree->u.internal[i].file_secno == secs) { 436 brelse(bh); 437 return; 438 } 439 node = btree->u.internal[i].down; 440 brelse(bh); 441 if (hpfs_sb(s)->sb_chk) 442 if (hpfs_stop_cycles(s, node, &c1, &c2, "hpfs_truncate_btree")) 443 return; 444 if (!(anode = hpfs_map_anode(s, node, &bh))) return; 445 btree = &anode->btree; 446 } 447 nodes = btree->n_used_nodes + btree->n_free_nodes; 448 for (i = 0; i < btree->n_used_nodes; i++) 449 if (btree->u.external[i].file_secno + btree->u.external[i].length >= secs) goto ff; 450 brelse(bh); 451 return; 452 ff: 453 if (secs <= btree->u.external[i].file_secno) { 454 hpfs_error(s, "there is an allocation error in file %08x, sector %08x", f, secs); 455 if (i) i--; 456 } 457 else if (btree->u.external[i].file_secno + btree->u.external[i].length > secs) { 458 hpfs_free_sectors(s, btree->u.external[i].disk_secno + secs - 459 btree->u.external[i].file_secno, btree->u.external[i].length 460 - secs + btree->u.external[i].file_secno); /* I hope gcc optimizes this :-) */ 461 btree->u.external[i].length = secs - btree->u.external[i].file_secno; 462 } 463 for (j = i + 1; j < btree->n_used_nodes; j++) 464 hpfs_free_sectors(s, btree->u.external[j].disk_secno, btree->u.external[j].length); 465 btree->n_used_nodes = i + 1; 466 btree->n_free_nodes = nodes - btree->n_used_nodes; 467 btree->first_free = 8 + 12 * btree->n_used_nodes; 468 mark_buffer_dirty(bh); 469 brelse(bh); 470} 471 472/* Remove file or directory and it's eas - note that directory must 473 be empty when this is called. */ 474 475void hpfs_remove_fnode(struct super_block *s, fnode_secno fno) 476{ 477 struct buffer_head *bh; 478 struct fnode *fnode; 479 struct extended_attribute *ea; 480 struct extended_attribute *ea_end; 481 if (!(fnode = hpfs_map_fnode(s, fno, &bh))) return; 482 if (!fnode->dirflag) hpfs_remove_btree(s, &fnode->btree); 483 else hpfs_remove_dtree(s, fnode->u.external[0].disk_secno); 484 ea_end = fnode_end_ea(fnode); 485 for (ea = fnode_ea(fnode); ea < ea_end; ea = next_ea(ea)) 486 if (ea->indirect) 487 hpfs_ea_remove(s, ea_sec(ea), ea->anode, ea_len(ea)); 488 hpfs_ea_ext_remove(s, fnode->ea_secno, fnode->ea_anode, fnode->ea_size_l); 489 brelse(bh); 490 hpfs_free_sectors(s, fno, 1); 491} 492