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