Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/fs/hpfs/anode.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
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 13 secno 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 (s->s_hpfs_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 (s->s_hpfs_chk) if (hpfs_chk_sectors(s, a, 1, "data")) { 41 brelse(bh); 42 return -1; 43 } 44 if (inode) { 45 inode->i_hpfs_file_sec = btree->u.external[i].file_secno; 46 inode->i_hpfs_disk_sec = btree->u.external[i].disk_secno; 47 inode->i_hpfs_n_secs = btree->u.external[i].length; 48 } 49 brelse(bh); 50 return a; 51 } 52 hpfs_error(s, "sector %08x not found in external anode %08x", sec, a); 53 brelse(bh); 54 return -1; 55 } 56 57 /* Add a sector to tree */ 58 59 secno hpfs_add_sector_to_btree(struct super_block *s, secno node, int fnod, unsigned fsecno) 60 { 61 struct bplus_header *btree; 62 struct anode *anode = NULL, *ranode = NULL; 63 struct fnode *fnode; 64 anode_secno a, na = -1, ra, up = -1; 65 secno se; 66 struct buffer_head *bh, *bh1, *bh2; 67 int n; 68 unsigned fs; 69 int c1, c2 = 0; 70 if (fnod) { 71 if (!(fnode = hpfs_map_fnode(s, node, &bh))) return -1; 72 btree = &fnode->btree; 73 } else { 74 if (!(anode = hpfs_map_anode(s, node, &bh))) return -1; 75 btree = &anode->btree; 76 } 77 a = node; 78 go_down: 79 if ((n = btree->n_used_nodes - 1) < -!!fnod) { 80 hpfs_error(s, "anode %08x has no entries", a); 81 brelse(bh); 82 return -1; 83 } 84 if (btree->internal) { 85 a = btree->u.internal[n].down; 86 btree->u.internal[n].file_secno = -1; 87 mark_buffer_dirty(bh); 88 brelse(bh); 89 if (s->s_hpfs_chk) 90 if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_add_sector_to_btree #1")) return -1; 91 if (!(anode = hpfs_map_anode(s, a, &bh))) return -1; 92 btree = &anode->btree; 93 goto go_down; 94 } 95 if (n >= 0) { 96 if (btree->u.external[n].file_secno + btree->u.external[n].length != fsecno) { 97 hpfs_error(s, "allocated size %08x, trying to add sector %08x, %cnode %08x", 98 btree->u.external[n].file_secno + btree->u.external[n].length, fsecno, 99 fnod?'f':'a', node); 100 brelse(bh); 101 return -1; 102 } 103 if (hpfs_alloc_if_possible(s, se = btree->u.external[n].disk_secno + btree->u.external[n].length)) { 104 btree->u.external[n].length++; 105 mark_buffer_dirty(bh); 106 brelse(bh); 107 return se; 108 } 109 } else { 110 if (fsecno) { 111 hpfs_error(s, "empty file %08x, trying to add sector %08x", node, fsecno); 112 brelse(bh); 113 return -1; 114 } 115 se = node; 116 } 117 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))) { 118 brelse(bh); 119 return -1; 120 } 121 fs = n < 0 ? 0 : btree->u.external[n].file_secno + btree->u.external[n].length; 122 if (!btree->n_free_nodes) { 123 up = a != node ? anode->up : -1; 124 if (!(anode = hpfs_alloc_anode(s, a, &na, &bh1))) { 125 brelse(bh); 126 hpfs_free_sectors(s, se, 1); 127 return -1; 128 } 129 if (a == node && fnod) { 130 anode->up = node; 131 anode->btree.fnode_parent = 1; 132 anode->btree.n_used_nodes = btree->n_used_nodes; 133 anode->btree.first_free = btree->first_free; 134 anode->btree.n_free_nodes = 40 - anode->btree.n_used_nodes; 135 memcpy(&anode->u, &btree->u, btree->n_used_nodes * 12); 136 btree->internal = 1; 137 btree->n_free_nodes = 11; 138 btree->n_used_nodes = 1; 139 btree->first_free = (char *)&(btree->u.internal[1]) - (char *)btree; 140 btree->u.internal[0].file_secno = -1; 141 btree->u.internal[0].down = na; 142 mark_buffer_dirty(bh); 143 } else if (!(ranode = hpfs_alloc_anode(s, /*a*/0, &ra, &bh2))) { 144 brelse(bh); 145 brelse(bh1); 146 hpfs_free_sectors(s, se, 1); 147 hpfs_free_sectors(s, na, 1); 148 return -1; 149 } 150 brelse(bh); 151 bh = bh1; 152 btree = &anode->btree; 153 } 154 btree->n_free_nodes--; n = btree->n_used_nodes++; 155 btree->first_free += 12; 156 btree->u.external[n].disk_secno = se; 157 btree->u.external[n].file_secno = fs; 158 btree->u.external[n].length = 1; 159 mark_buffer_dirty(bh); 160 brelse(bh); 161 if ((a == node && fnod) || na == -1) return se; 162 c2 = 0; 163 while (up != -1) { 164 struct anode *new_anode; 165 if (s->s_hpfs_chk) 166 if (hpfs_stop_cycles(s, up, &c1, &c2, "hpfs_add_sector_to_btree #2")) return -1; 167 if (up != node || !fnod) { 168 if (!(anode = hpfs_map_anode(s, up, &bh))) return -1; 169 btree = &anode->btree; 170 } else { 171 if (!(fnode = hpfs_map_fnode(s, up, &bh))) return -1; 172 btree = &fnode->btree; 173 } 174 if (btree->n_free_nodes) { 175 btree->n_free_nodes--; n = btree->n_used_nodes++; 176 btree->first_free += 8; 177 btree->u.internal[n].file_secno = -1; 178 btree->u.internal[n].down = na; 179 btree->u.internal[n-1].file_secno = fs; 180 mark_buffer_dirty(bh); 181 brelse(bh); 182 brelse(bh2); 183 hpfs_free_sectors(s, ra, 1); 184 if ((anode = hpfs_map_anode(s, na, &bh))) { 185 anode->up = up; 186 anode->btree.fnode_parent = up == node && fnod; 187 mark_buffer_dirty(bh); 188 brelse(bh); 189 } 190 return se; 191 } 192 up = up != node ? anode->up : -1; 193 btree->u.internal[btree->n_used_nodes - 1].file_secno = /*fs*/-1; 194 if (up == -1) anode->up = ra; 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 268 void 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 (s->s_hpfs_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 (s->s_hpfs_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 324 static 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 332 int 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 (s->s_hpfs_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 355 int hpfs_ea_write(struct super_block *s, secno a, int ano, unsigned pos, 356 unsigned len, 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 (s->s_hpfs_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 379 void 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 393 void 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 (s->s_hpfs_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 475 void 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 }
Cache object: a48c1e926b1935837cce90613181be4a
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]