1/* 2 * linux/fs/hpfs/dnode.c 3 * 4 * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999 5 * 6 * handling directory dnode tree - adding, deleteing & searching for dirents 7 */ 8 9#include "hpfs_fn.h" 10 11static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde) 12{ 13 struct hpfs_dirent *de; 14 struct hpfs_dirent *de_end = dnode_end_de(d); 15 int i = 1; 16 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) { 17 if (de == fde) return ((loff_t) d->self << 4) | (loff_t)i; 18 i++; 19 } 20 printk("HPFS: get_pos: not_found\n"); 21 return ((loff_t)d->self << 4) | (loff_t)1; 22} 23 24void hpfs_add_pos(struct inode *inode, loff_t *pos) 25{ 26 int i = 0; 27 loff_t **ppos; 28 if (inode->i_hpfs_rddir_off) 29 for (; inode->i_hpfs_rddir_off[i]; i++) 30 if (inode->i_hpfs_rddir_off[i] == pos) return; 31 if (!(i&0x0f)) { 32 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_KERNEL))) { 33 printk("HPFS: out of memory for position list\n"); 34 return; 35 } 36 if (inode->i_hpfs_rddir_off) { 37 memcpy(ppos, inode->i_hpfs_rddir_off, i * sizeof(loff_t)); 38 kfree(inode->i_hpfs_rddir_off); 39 } 40 inode->i_hpfs_rddir_off = ppos; 41 } 42 inode->i_hpfs_rddir_off[i] = pos; 43 inode->i_hpfs_rddir_off[i + 1] = NULL; 44} 45 46void hpfs_del_pos(struct inode *inode, loff_t *pos) 47{ 48 loff_t **i, **j; 49 if (!inode->i_hpfs_rddir_off) goto not_f; 50 for (i = inode->i_hpfs_rddir_off; *i; i++) if (*i == pos) goto fnd; 51 goto not_f; 52 fnd: 53 for (j = i + 1; *j; j++) ; 54 *i = *(j - 1); 55 *(j - 1) = NULL; 56 if (j - 1 == inode->i_hpfs_rddir_off) { 57 kfree(inode->i_hpfs_rddir_off); 58 inode->i_hpfs_rddir_off = NULL; 59 } 60 return; 61 not_f: 62 /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/ 63 return; 64} 65 66static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t), 67 loff_t p1, loff_t p2) 68{ 69 loff_t **i; 70 if (!inode->i_hpfs_rddir_off) return; 71 for (i = inode->i_hpfs_rddir_off; *i; i++) (*f)(*i, p1, p2); 72 return; 73} 74 75void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t) 76{ 77 if (*p == f) *p = t; 78} 79 80/*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t) 81{ 82 if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f); 83}*/ 84 85void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c) 86{ 87 if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) { 88 int n = (*p & 0x3f) + c; 89 if (n > 0x3f) printk("HPFS: hpfs_pos_ins: %08x + %d\n", (int)*p, (int)c >> 8); 90 else *p = (*p & ~0x3f) | n; 91 } 92} 93 94void hpfs_pos_del(loff_t *p, loff_t d, loff_t c) 95{ 96 if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) { 97 int n = (*p & 0x3f) - c; 98 if (n < 1) printk("HPFS: hpfs_pos_ins: %08x - %d\n", (int)*p, (int)c >> 8); 99 else *p = (*p & ~0x3f) | n; 100 } 101} 102 103static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d) 104{ 105 struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL; 106 de_end = dnode_end_de(d); 107 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) { 108 deee = dee; dee = de; 109 } 110 return deee; 111} 112 113static struct hpfs_dirent *dnode_last_de(struct dnode *d) 114{ 115 struct hpfs_dirent *de, *de_end, *dee = NULL; 116 de_end = dnode_end_de(d); 117 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) { 118 dee = de; 119 } 120 return dee; 121} 122 123static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr) 124{ 125 struct hpfs_dirent *de; 126 if (!(de = dnode_last_de(d))) { 127 hpfs_error(s, "set_last_pointer: empty dnode %08x", d->self); 128 return; 129 } 130 if (s->s_hpfs_chk) { 131 if (de->down) { 132 hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x", 133 d->self, de_down_pointer(de)); 134 return; 135 } 136 if (de->length != 32) { 137 hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", d->self); 138 return; 139 } 140 } 141 if (ptr) { 142 if ((d->first_free += 4) > 2048) { 143 hpfs_error(s,"set_last_pointer: too long dnode %08x", d->self); 144 d->first_free -= 4; 145 return; 146 } 147 de->length = 36; 148 de->down = 1; 149 *(dnode_secno *)((char *)de + 32) = ptr; 150 } 151} 152 153/* Add an entry to dnode and don't care if it grows over 2048 bytes */ 154 155struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d, unsigned char *name, 156 unsigned namelen, secno down_ptr) 157{ 158 struct hpfs_dirent *de; 159 struct hpfs_dirent *de_end = dnode_end_de(d); 160 unsigned d_size = de_size(namelen, down_ptr); 161 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) { 162 int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last); 163 if (!c) { 164 hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, d->self); 165 return NULL; 166 } 167 if (c < 0) break; 168 } 169 memmove((char *)de + d_size, de, (char *)de_end - (char *)de); 170 memset(de, 0, d_size); 171 if (down_ptr) { 172 *(int *)((char *)de + d_size - 4) = down_ptr; 173 de->down = 1; 174 } 175 de->length = d_size; 176 if (down_ptr) de->down = 1; 177 de->not_8x3 = hpfs_is_name_long(name, namelen); 178 de->namelen = namelen; 179 memcpy(de->name, name, namelen); 180 d->first_free += d_size; 181 return de; 182} 183 184/* Delete dirent and don't care about it's subtree */ 185 186void hpfs_delete_de(struct super_block *s, struct dnode *d, struct hpfs_dirent *de) 187{ 188 if (de->last) { 189 hpfs_error(s, "attempt to delete last dirent in dnode %08x", d->self); 190 return; 191 } 192 d->first_free -= de->length; 193 memmove(de, de_next_de(de), d->first_free + (char *)d - (char *)de); 194} 195 196static void fix_up_ptrs(struct super_block *s, struct dnode *d) 197{ 198 struct hpfs_dirent *de; 199 struct hpfs_dirent *de_end = dnode_end_de(d); 200 dnode_secno dno = d->self; 201 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) 202 if (de->down) { 203 struct quad_buffer_head qbh; 204 struct dnode *dd; 205 if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) { 206 if (dd->up != dno || dd->root_dnode) { 207 dd->up = dno; 208 dd->root_dnode = 0; 209 hpfs_mark_4buffers_dirty(&qbh); 210 } 211 hpfs_brelse4(&qbh); 212 } 213 } 214} 215 216/* Add an entry to dnode and do dnode splitting if required */ 217 218int hpfs_add_to_dnode(struct inode *i, dnode_secno dno, unsigned char *name, unsigned namelen, 219 struct hpfs_dirent *new_de, dnode_secno down_ptr) 220{ 221 struct quad_buffer_head qbh, qbh1, qbh2; 222 struct dnode *d, *ad, *rd, *nd = NULL; 223 dnode_secno adno, rdno; 224 struct hpfs_dirent *de; 225 struct hpfs_dirent nde; 226 char *nname; 227 int h; 228 int pos; 229 struct buffer_head *bh; 230 struct fnode *fnode; 231 int c1, c2 = 0; 232 if (!(nname = kmalloc(256, GFP_KERNEL))) { 233 printk("HPFS: out of memory, can't add to dnode\n"); 234 return 1; 235 } 236 go_up: 237 if (namelen >= 256) { 238 hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen); 239 if (nd) kfree(nd); 240 kfree(nname); 241 return 1; 242 } 243 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) { 244 if (nd) kfree(nd); 245 kfree(nname); 246 return 1; 247 } 248 go_up_a: 249 if (i->i_sb->s_hpfs_chk) 250 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) { 251 hpfs_brelse4(&qbh); 252 if (nd) kfree(nd); 253 kfree(nname); 254 return 1; 255 } 256 if (d->first_free + de_size(namelen, down_ptr) <= 2048) { 257 loff_t t; 258 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de); 259 t = get_pos(d, de); 260 for_all_poss(i, hpfs_pos_ins, t, 1); 261 for_all_poss(i, hpfs_pos_subst, 4, t); 262 for_all_poss(i, hpfs_pos_subst, 5, t + 1); 263 hpfs_mark_4buffers_dirty(&qbh); 264 hpfs_brelse4(&qbh); 265 if (nd) kfree(nd); 266 kfree(nname); 267 return 0; 268 } 269 if (!nd) if (!(nd = kmalloc(0x924, GFP_KERNEL))) { 270 /* 0x924 is a max size of dnode after adding a dirent with 271 max name length. We alloc this only once. There must 272 not be any error while splitting dnodes, otherwise the 273 whole directory, not only file we're adding, would 274 be lost. */ 275 printk("HPFS: out of memory for dnode splitting\n"); 276 hpfs_brelse4(&qbh); 277 kfree(nname); 278 return 1; 279 } 280 memcpy(nd, d, d->first_free); 281 copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de); 282 for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1); 283 h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10; 284 if (!(ad = hpfs_alloc_dnode(i->i_sb, d->up, &adno, &qbh1, 0))) { 285 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted"); 286 hpfs_brelse4(&qbh); 287 kfree(nd); 288 kfree(nname); 289 return 1; 290 } 291 i->i_size += 2048; 292 i->i_blocks += 4; 293 pos = 1; 294 for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) { 295 copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de); 296 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos); 297 pos++; 298 } 299 copy_de(new_de = &nde, de); 300 memcpy(name = nname, de->name, namelen = de->namelen); 301 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4); 302 down_ptr = adno; 303 set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0); 304 de = de_next_de(de); 305 memmove((char *)nd + 20, de, nd->first_free + (char *)nd - (char *)de); 306 nd->first_free -= (char *)de - (char *)nd - 20; 307 memcpy(d, nd, nd->first_free); 308 for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos); 309 fix_up_ptrs(i->i_sb, ad); 310 if (!d->root_dnode) { 311 dno = ad->up = d->up; 312 hpfs_mark_4buffers_dirty(&qbh); 313 hpfs_brelse4(&qbh); 314 hpfs_mark_4buffers_dirty(&qbh1); 315 hpfs_brelse4(&qbh1); 316 goto go_up; 317 } 318 if (!(rd = hpfs_alloc_dnode(i->i_sb, d->up, &rdno, &qbh2, 0))) { 319 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted"); 320 hpfs_brelse4(&qbh); 321 hpfs_brelse4(&qbh1); 322 kfree(nd); 323 kfree(nname); 324 return 1; 325 } 326 i->i_size += 2048; 327 i->i_blocks += 4; 328 rd->root_dnode = 1; 329 rd->up = d->up; 330 if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) { 331 hpfs_free_dnode(i->i_sb, rdno); 332 hpfs_brelse4(&qbh); 333 hpfs_brelse4(&qbh1); 334 hpfs_brelse4(&qbh2); 335 kfree(nd); 336 kfree(nname); 337 return 1; 338 } 339 fnode->u.external[0].disk_secno = rdno; 340 mark_buffer_dirty(bh); 341 brelse(bh); 342 d->up = ad->up = i->i_hpfs_dno = rdno; 343 d->root_dnode = ad->root_dnode = 0; 344 hpfs_mark_4buffers_dirty(&qbh); 345 hpfs_brelse4(&qbh); 346 hpfs_mark_4buffers_dirty(&qbh1); 347 hpfs_brelse4(&qbh1); 348 qbh = qbh2; 349 set_last_pointer(i->i_sb, rd, dno); 350 dno = rdno; 351 d = rd; 352 goto go_up_a; 353} 354 355/* 356 * Add an entry to directory btree. 357 * I hate such crazy directory structure. 358 * It's easy to read but terrible to write. 359 * I wrote this directory code 4 times. 360 * I hope, now it's finally bug-free. 361 */ 362 363int hpfs_add_dirent(struct inode *i, unsigned char *name, unsigned namelen, 364 struct hpfs_dirent *new_de, int cdepth) 365{ 366 struct dnode *d; 367 struct hpfs_dirent *de, *de_end; 368 struct quad_buffer_head qbh; 369 dnode_secno dno; 370 int c; 371 int c1, c2 = 0; 372 dno = i->i_hpfs_dno; 373 down: 374 if (i->i_sb->s_hpfs_chk) 375 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1; 376 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1; 377 de_end = dnode_end_de(d); 378 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) { 379 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) { 380 hpfs_brelse4(&qbh); 381 return -1; 382 } 383 if (c < 0) { 384 if (de->down) { 385 dno = de_down_pointer(de); 386 hpfs_brelse4(&qbh); 387 goto down; 388 } 389 break; 390 } 391 } 392 hpfs_brelse4(&qbh); 393 if (!cdepth) hpfs_lock_creation(i->i_sb); 394 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) { 395 c = 1; 396 goto ret; 397 } 398 i->i_version = ++event; 399 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0); 400 ret: 401 if (!cdepth) hpfs_unlock_creation(i->i_sb); 402 return c; 403} 404 405/* 406 * Find dirent with higher name in 'from' subtree and move it to 'to' dnode. 407 * Return the dnode we moved from (to be checked later if it's empty) 408 */ 409 410static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to) 411{ 412 dnode_secno dno, ddno; 413 dnode_secno chk_up = to; 414 struct dnode *dnode; 415 struct quad_buffer_head qbh; 416 struct hpfs_dirent *de, *nde; 417 int a; 418 loff_t t; 419 int c1, c2 = 0; 420 dno = from; 421 while (1) { 422 if (i->i_sb->s_hpfs_chk) 423 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top")) 424 return 0; 425 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0; 426 if (i->i_sb->s_hpfs_chk) { 427 if (dnode->up != chk_up) { 428 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x", 429 dno, chk_up, dnode->up); 430 hpfs_brelse4(&qbh); 431 return 0; 432 } 433 chk_up = dno; 434 } 435 if (!(de = dnode_last_de(dnode))) { 436 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno); 437 hpfs_brelse4(&qbh); 438 return 0; 439 } 440 if (!de->down) break; 441 dno = de_down_pointer(de); 442 hpfs_brelse4(&qbh); 443 } 444 while (!(de = dnode_pre_last_de(dnode))) { 445 dnode_secno up = dnode->up; 446 hpfs_brelse4(&qbh); 447 hpfs_free_dnode(i->i_sb, dno); 448 i->i_size -= 2048; 449 i->i_blocks -= 4; 450 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5); 451 if (up == to) return to; 452 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0; 453 if (dnode->root_dnode) { 454 hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to); 455 hpfs_brelse4(&qbh); 456 return 0; 457 } 458 de = dnode_last_de(dnode); 459 if (!de || !de->down) { 460 hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno); 461 hpfs_brelse4(&qbh); 462 return 0; 463 } 464 dnode->first_free -= 4; 465 de->length -= 4; 466 de->down = 0; 467 hpfs_mark_4buffers_dirty(&qbh); 468 dno = up; 469 } 470 t = get_pos(dnode, de); 471 for_all_poss(i, hpfs_pos_subst, t, 4); 472 for_all_poss(i, hpfs_pos_subst, t + 1, 5); 473 if (!(nde = kmalloc(de->length, GFP_KERNEL))) { 474 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted"); 475 hpfs_brelse4(&qbh); 476 return 0; 477 } 478 memcpy(nde, de, de->length); 479 ddno = de->down ? de_down_pointer(de) : 0; 480 hpfs_delete_de(i->i_sb, dnode, de); 481 set_last_pointer(i->i_sb, dnode, ddno); 482 hpfs_mark_4buffers_dirty(&qbh); 483 hpfs_brelse4(&qbh); 484 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from); 485 kfree(nde); 486 if (a) return 0; 487 return dno; 488} 489 490/* 491 * Check if a dnode is empty and delete it from the tree 492 * (chkdsk doesn't like empty dnodes) 493 */ 494 495static void delete_empty_dnode(struct inode *i, dnode_secno dno) 496{ 497 struct quad_buffer_head qbh; 498 struct dnode *dnode; 499 dnode_secno down, up, ndown; 500 int p; 501 struct hpfs_dirent *de; 502 int c1, c2 = 0; 503 try_it_again: 504 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return; 505 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return; 506 if (dnode->first_free > 56) goto end; 507 if (dnode->first_free == 52 || dnode->first_free == 56) { 508 struct hpfs_dirent *de_end; 509 int root = dnode->root_dnode; 510 up = dnode->up; 511 de = dnode_first_de(dnode); 512 down = de->down ? de_down_pointer(de) : 0; 513 if (i->i_sb->s_hpfs_chk) if (root && !down) { 514 hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno); 515 goto end; 516 } 517 hpfs_brelse4(&qbh); 518 hpfs_free_dnode(i->i_sb, dno); 519 i->i_size -= 2048; 520 i->i_blocks -= 4; 521 if (root) { 522 struct fnode *fnode; 523 struct buffer_head *bh; 524 struct dnode *d1; 525 struct quad_buffer_head qbh1; 526 if (i->i_sb->s_hpfs_chk) if (up != i->i_ino) { 527 hpfs_error(i->i_sb, "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08x", dno, up, i->i_ino); 528 return; 529 } 530 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) { 531 d1->up = up; 532 d1->root_dnode = 1; 533 hpfs_mark_4buffers_dirty(&qbh1); 534 hpfs_brelse4(&qbh1); 535 } 536 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) { 537 fnode->u.external[0].disk_secno = down; 538 mark_buffer_dirty(bh); 539 brelse(bh); 540 } 541 i->i_hpfs_dno = down; 542 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12); 543 return; 544 } 545 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return; 546 p = 1; 547 de_end = dnode_end_de(dnode); 548 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++) 549 if (de->down) if (de_down_pointer(de) == dno) goto fnd; 550 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up); 551 goto end; 552 fnd: 553 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p); 554 if (!down) { 555 de->down = 0; 556 de->length -= 4; 557 dnode->first_free -= 4; 558 memmove(de_next_de(de), (char *)de_next_de(de) + 4, 559 (char *)dnode + dnode->first_free - (char *)de_next_de(de)); 560 } else { 561 struct dnode *d1; 562 struct quad_buffer_head qbh1; 563 *(dnode_secno *) ((void *) de + de->length - 4) = down; 564 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) { 565 d1->up = up; 566 hpfs_mark_4buffers_dirty(&qbh1); 567 hpfs_brelse4(&qbh1); 568 } 569 } 570 } else { 571 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, dnode->first_free); 572 goto end; 573 } 574 575 if (!de->last) { 576 struct hpfs_dirent *de_next = de_next_de(de); 577 struct hpfs_dirent *de_cp; 578 struct dnode *d1; 579 struct quad_buffer_head qbh1; 580 if (!de_next->down) goto endm; 581 ndown = de_down_pointer(de_next); 582 if (!(de_cp = kmalloc(de->length, GFP_KERNEL))) { 583 printk("HPFS: out of memory for dtree balancing\n"); 584 goto endm; 585 } 586 memcpy(de_cp, de, de->length); 587 hpfs_delete_de(i->i_sb, dnode, de); 588 hpfs_mark_4buffers_dirty(&qbh); 589 hpfs_brelse4(&qbh); 590 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4); 591 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1); 592 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) { 593 d1->up = ndown; 594 hpfs_mark_4buffers_dirty(&qbh1); 595 hpfs_brelse4(&qbh1); 596 } 597 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0); 598 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/ 599 dno = up; 600 kfree(de_cp); 601 goto try_it_again; 602 } else { 603 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode); 604 struct hpfs_dirent *de_cp; 605 struct dnode *d1; 606 struct quad_buffer_head qbh1; 607 dnode_secno dlp; 608 if (!de_prev) { 609 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up); 610 hpfs_mark_4buffers_dirty(&qbh); 611 hpfs_brelse4(&qbh); 612 dno = up; 613 goto try_it_again; 614 } 615 if (!de_prev->down) goto endm; 616 ndown = de_down_pointer(de_prev); 617 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) { 618 struct hpfs_dirent *del = dnode_last_de(d1); 619 dlp = del->down ? de_down_pointer(del) : 0; 620 if (!dlp && down) { 621 if (d1->first_free > 2044) { 622 if (i->i_sb->s_hpfs_chk >= 2) { 623 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n"); 624 printk("HPFS: warning: terminating balancing operation\n"); 625 } 626 hpfs_brelse4(&qbh1); 627 goto endm; 628 } 629 if (i->i_sb->s_hpfs_chk >= 2) { 630 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n"); 631 printk("HPFS: warning: goin'on\n"); 632 } 633 del->length += 4; 634 del->down = 1; 635 d1->first_free += 4; 636 } 637 if (dlp && !down) { 638 del->length -= 4; 639 del->down = 0; 640 d1->first_free -= 4; 641 } else if (down) 642 *(dnode_secno *) ((void *) del + del->length - 4) = down; 643 } else goto endm; 644 if (!(de_cp = kmalloc(de_prev->length, GFP_KERNEL))) { 645 printk("HPFS: out of memory for dtree balancing\n"); 646 hpfs_brelse4(&qbh1); 647 goto endm; 648 } 649 hpfs_mark_4buffers_dirty(&qbh1); 650 hpfs_brelse4(&qbh1); 651 memcpy(de_cp, de_prev, de_prev->length); 652 hpfs_delete_de(i->i_sb, dnode, de_prev); 653 if (!de_prev->down) { 654 de_prev->length += 4; 655 de_prev->down = 1; 656 dnode->first_free += 4; 657 } 658 *(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = ndown; 659 hpfs_mark_4buffers_dirty(&qbh); 660 hpfs_brelse4(&qbh); 661 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4); 662 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1)); 663 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) { 664 d1->up = ndown; 665 hpfs_mark_4buffers_dirty(&qbh1); 666 hpfs_brelse4(&qbh1); 667 } 668 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp); 669 dno = up; 670 kfree(de_cp); 671 goto try_it_again; 672 } 673 endm: 674 hpfs_mark_4buffers_dirty(&qbh); 675 end: 676 hpfs_brelse4(&qbh); 677} 678 679 680/* Delete dirent from directory */ 681 682int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de, 683 struct quad_buffer_head *qbh, int depth) 684{ 685 struct dnode *dnode = qbh->data; 686 dnode_secno down = 0; 687 int lock = 0; 688 loff_t t; 689 if (de->first || de->last) { 690 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno); 691 hpfs_brelse4(qbh); 692 return 1; 693 } 694 if (de->down) down = de_down_pointer(de); 695 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) { 696 lock = 1; 697 hpfs_lock_creation(i->i_sb); 698 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) { 699 hpfs_brelse4(qbh); 700 hpfs_unlock_creation(i->i_sb); 701 return 2; 702 } 703 } 704 i->i_version = ++event; 705 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1); 706 hpfs_delete_de(i->i_sb, dnode, de); 707 hpfs_mark_4buffers_dirty(qbh); 708 hpfs_brelse4(qbh); 709 if (down) { 710 dnode_secno a = move_to_top(i, down, dno); 711 for_all_poss(i, hpfs_pos_subst, 5, t); 712 if (a) delete_empty_dnode(i, a); 713 if (lock) hpfs_unlock_creation(i->i_sb); 714 return !a; 715 } 716 delete_empty_dnode(i, dno); 717 if (lock) hpfs_unlock_creation(i->i_sb); 718 return 0; 719} 720 721void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes, 722 int *n_subdirs, int *n_items) 723{ 724 struct dnode *dnode; 725 struct quad_buffer_head qbh; 726 struct hpfs_dirent *de; 727 dnode_secno ptr, odno = 0; 728 int c1, c2 = 0; 729 int d1, d2 = 0; 730 go_down: 731 if (n_dnodes) (*n_dnodes)++; 732 if (s->s_hpfs_chk) 733 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return; 734 ptr = 0; 735 go_up: 736 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return; 737 if (s->s_hpfs_chk) if (odno && odno != -1 && dnode->up != odno) 738 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up); 739 de = dnode_first_de(dnode); 740 if (ptr) while(1) { 741 if (de->down) if (de_down_pointer(de) == ptr) goto process_de; 742 if (de->last) { 743 hpfs_brelse4(&qbh); 744 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x", 745 ptr, dno, odno); 746 return; 747 } 748 de = de_next_de(de); 749 } 750 next_de: 751 if (de->down) { 752 odno = dno; 753 dno = de_down_pointer(de); 754 hpfs_brelse4(&qbh); 755 goto go_down; 756 } 757 process_de: 758 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++; 759 if (!de->first && !de->last && n_items) (*n_items)++; 760 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de; 761 ptr = dno; 762 dno = dnode->up; 763 if (dnode->root_dnode) { 764 hpfs_brelse4(&qbh); 765 return; 766 } 767 hpfs_brelse4(&qbh); 768 if (s->s_hpfs_chk) 769 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return; 770 odno = -1; 771 goto go_up; 772} 773 774static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n, 775 struct quad_buffer_head *qbh, struct dnode **dn) 776{ 777 int i; 778 struct hpfs_dirent *de, *de_end; 779 struct dnode *dnode; 780 dnode = hpfs_map_dnode(s, dno, qbh); 781 if (!dnode) return NULL; 782 if (dn) *dn=dnode; 783 de = dnode_first_de(dnode); 784 de_end = dnode_end_de(dnode); 785 for (i = 1; de < de_end; i++, de = de_next_de(de)) { 786 if (i == n) { 787 return de; 788 } 789 if (de->last) break; 790 } 791 hpfs_brelse4(qbh); 792 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n); 793 return NULL; 794} 795 796dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno) 797{ 798 struct quad_buffer_head qbh; 799 dnode_secno d = dno; 800 dnode_secno up = 0; 801 struct hpfs_dirent *de; 802 int c1, c2 = 0; 803 804 again: 805 if (s->s_hpfs_chk) 806 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible")) 807 return d; 808 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno; 809 if (s->s_hpfs_chk) 810 if (up && ((struct dnode *)qbh.data)->up != up) 811 hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, ((struct dnode *)qbh.data)->up); 812 if (!de->down) { 813 hpfs_brelse4(&qbh); 814 return d; 815 } 816 up = d; 817 d = de_down_pointer(de); 818 hpfs_brelse4(&qbh); 819 goto again; 820} 821 822struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp, 823 struct quad_buffer_head *qbh) 824{ 825 loff_t pos; 826 unsigned c; 827 dnode_secno dno; 828 struct hpfs_dirent *de, *d; 829 struct hpfs_dirent *up_de; 830 struct hpfs_dirent *end_up_de; 831 struct dnode *dnode; 832 struct dnode *up_dnode; 833 struct quad_buffer_head qbh0; 834 835 pos = *posp; 836 dno = pos >> 6 << 2; 837 pos &= 077; 838 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode))) 839 goto bail; 840 841 /* Going to the next dirent */ 842 if ((d = de_next_de(de)) < dnode_end_de(dnode)) { 843 if (!(++*posp & 077)) { 844 hpfs_error(inode->i_sb, "map_pos_dirent: pos crossed dnode boundary; pos = %08x", *posp); 845 goto bail; 846 } 847 /* We're going down the tree */ 848 if (d->down) { 849 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1; 850 } 851 852 return de; 853 } 854 855 /* Going up */ 856 if (dnode->root_dnode) goto bail; 857 858 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0))) 859 goto bail; 860 861 end_up_de = dnode_end_de(up_dnode); 862 c = 0; 863 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de; 864 up_de = de_next_de(up_de)) { 865 if (!(++c & 077)) hpfs_error(inode->i_sb, 866 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up); 867 if (up_de->down && de_down_pointer(up_de) == dno) { 868 *posp = ((loff_t) dnode->up << 4) + c; 869 hpfs_brelse4(&qbh0); 870 return de; 871 } 872 } 873 874 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x", 875 dno, dnode->up); 876 hpfs_brelse4(&qbh0); 877 878 bail: 879 *posp = 12; 880 return de; 881} 882 883/* Find a dirent in tree */ 884 885struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, char *name, unsigned len, 886 dnode_secno *dd, struct quad_buffer_head *qbh) 887{ 888 struct dnode *dnode; 889 struct hpfs_dirent *de; 890 struct hpfs_dirent *de_end; 891 int c1, c2 = 0; 892 893 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n"); 894 again: 895 if (inode->i_sb->s_hpfs_chk) 896 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL; 897 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL; 898 899 de_end = dnode_end_de(dnode); 900 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) { 901 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last); 902 if (!t) { 903 if (dd) *dd = dno; 904 return de; 905 } 906 if (t < 0) { 907 if (de->down) { 908 dno = de_down_pointer(de); 909 hpfs_brelse4(qbh); 910 goto again; 911 } 912 break; 913 } 914 } 915 hpfs_brelse4(qbh); 916 return NULL; 917} 918 919/* 920 * Remove empty directory. In normal cases it is only one dnode with two 921 * entries, but we must handle also such obscure cases when it's a tree 922 * of empty dnodes. 923 */ 924 925void hpfs_remove_dtree(struct super_block *s, dnode_secno dno) 926{ 927 struct quad_buffer_head qbh; 928 struct dnode *dnode; 929 struct hpfs_dirent *de; 930 dnode_secno d1, d2, rdno = dno; 931 while (1) { 932 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return; 933 de = dnode_first_de(dnode); 934 if (de->last) { 935 if (de->down) d1 = de_down_pointer(de); 936 else goto error; 937 hpfs_brelse4(&qbh); 938 hpfs_free_dnode(s, dno); 939 dno = d1; 940 } else break; 941 } 942 if (!de->first) goto error; 943 d1 = de->down ? de_down_pointer(de) : 0; 944 de = de_next_de(de); 945 if (!de->last) goto error; 946 d2 = de->down ? de_down_pointer(de) : 0; 947 hpfs_brelse4(&qbh); 948 hpfs_free_dnode(s, dno); 949 do { 950 while (d1) { 951 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return; 952 de = dnode_first_de(dnode); 953 if (!de->last) goto error; 954 d1 = de->down ? de_down_pointer(de) : 0; 955 hpfs_brelse4(&qbh); 956 hpfs_free_dnode(s, dno); 957 } 958 d1 = d2; 959 d2 = 0; 960 } while (d1); 961 return; 962 error: 963 hpfs_brelse4(&qbh); 964 hpfs_free_dnode(s, dno); 965 hpfs_error(s, "directory %08x is corrupted or not empty", rdno); 966} 967 968/* 969 * Find dirent for specified fnode. Use truncated 15-char name in fnode as 970 * a help for searching. 971 */ 972 973struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno, 974 struct fnode *f, struct quad_buffer_head *qbh) 975{ 976 char *name1; 977 char *name2; 978 int name1len, name2len; 979 struct dnode *d; 980 dnode_secno dno, downd; 981 struct fnode *upf; 982 struct buffer_head *bh; 983 struct hpfs_dirent *de, *de_end; 984 int c; 985 int c1, c2 = 0; 986 int d1, d2 = 0; 987 name1 = f->name; 988 if (!(name2 = kmalloc(256, GFP_KERNEL))) { 989 printk("HPFS: out of memory, can't map dirent\n"); 990 return NULL; 991 } 992 if (f->len <= 15) 993 memcpy(name2, name1, name1len = name2len = f->len); 994 else { 995 memcpy(name2, name1, 15); 996 memset(name2 + 15, 0xff, 256 - 15); 997 /*name2[15] = 0xff;*/ 998 name1len = 15; name2len = 256; 999 } 1000 if (!(upf = hpfs_map_fnode(s, f->up, &bh))) { 1001 kfree(name2); 1002 return NULL; 1003 } 1004 if (!upf->dirflag) { 1005 brelse(bh); 1006 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up); 1007 kfree(name2); 1008 return NULL; 1009 } 1010 dno = upf->u.external[0].disk_secno; 1011 brelse(bh); 1012 go_down: 1013 downd = 0; 1014 go_up: 1015 if (!(d = hpfs_map_dnode(s, dno, qbh))) { 1016 kfree(name2); 1017 return NULL; 1018 } 1019 de_end = dnode_end_de(d); 1020 de = dnode_first_de(d); 1021 if (downd) { 1022 while (de < de_end) { 1023 if (de->down) if (de_down_pointer(de) == downd) goto f; 1024 de = de_next_de(de); 1025 } 1026 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno); 1027 hpfs_brelse4(qbh); 1028 kfree(name2); 1029 return NULL; 1030 } 1031 next_de: 1032 if (de->fnode == fno) { 1033 kfree(name2); 1034 return de; 1035 } 1036 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last); 1037 if (c < 0 && de->down) { 1038 dno = de_down_pointer(de); 1039 hpfs_brelse4(qbh); 1040 if (s->s_hpfs_chk) 1041 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) { 1042 kfree(name2); 1043 return NULL; 1044 } 1045 goto go_down; 1046 } 1047 f: 1048 if (de->fnode == fno) { 1049 kfree(name2); 1050 return de; 1051 } 1052 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last); 1053 if (c < 0 && !de->last) goto not_found; 1054 if ((de = de_next_de(de)) < de_end) goto next_de; 1055 if (d->root_dnode) goto not_found; 1056 downd = dno; 1057 dno = d->up; 1058 hpfs_brelse4(qbh); 1059 if (s->s_hpfs_chk) 1060 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) { 1061 kfree(name2); 1062 return NULL; 1063 } 1064 goto go_up; 1065 not_found: 1066 hpfs_brelse4(qbh); 1067 hpfs_error(s, "dirent for fnode %08x not found", fno); 1068 kfree(name2); 1069 return NULL; 1070} 1071