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