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