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 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0); 423 ret: 424 return c; 425 } 426 427 /* 428 * Find dirent with higher name in 'from' subtree and move it to 'to' dnode. 429 * Return the dnode we moved from (to be checked later if it's empty) 430 */ 431 432 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to) 433 { 434 dnode_secno dno, ddno; 435 dnode_secno chk_up = to; 436 struct dnode *dnode; 437 struct quad_buffer_head qbh; 438 struct hpfs_dirent *de, *nde; 439 int a; 440 loff_t t; 441 int c1, c2 = 0; 442 dno = from; 443 while (1) { 444 if (hpfs_sb(i->i_sb)->sb_chk) 445 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top")) 446 return 0; 447 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0; 448 if (hpfs_sb(i->i_sb)->sb_chk) { 449 if (le32_to_cpu(dnode->up) != chk_up) { 450 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x", 451 dno, chk_up, le32_to_cpu(dnode->up)); 452 hpfs_brelse4(&qbh); 453 return 0; 454 } 455 chk_up = dno; 456 } 457 if (!(de = dnode_last_de(dnode))) { 458 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno); 459 hpfs_brelse4(&qbh); 460 return 0; 461 } 462 if (!de->down) break; 463 dno = de_down_pointer(de); 464 hpfs_brelse4(&qbh); 465 } 466 while (!(de = dnode_pre_last_de(dnode))) { 467 dnode_secno up = le32_to_cpu(dnode->up); 468 hpfs_brelse4(&qbh); 469 hpfs_free_dnode(i->i_sb, dno); 470 i->i_size -= 2048; 471 i->i_blocks -= 4; 472 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5); 473 if (up == to) return to; 474 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0; 475 if (dnode->root_dnode) { 476 hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to); 477 hpfs_brelse4(&qbh); 478 return 0; 479 } 480 de = dnode_last_de(dnode); 481 if (!de || !de->down) { 482 hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno); 483 hpfs_brelse4(&qbh); 484 return 0; 485 } 486 le32_add_cpu(&dnode->first_free, -4); 487 le16_add_cpu(&de->length, -4); 488 de->down = 0; 489 hpfs_mark_4buffers_dirty(&qbh); 490 dno = up; 491 } 492 t = get_pos(dnode, de); 493 for_all_poss(i, hpfs_pos_subst, t, 4); 494 for_all_poss(i, hpfs_pos_subst, t + 1, 5); 495 if (!(nde = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) { 496 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted"); 497 hpfs_brelse4(&qbh); 498 return 0; 499 } 500 memcpy(nde, de, le16_to_cpu(de->length)); 501 ddno = de->down ? de_down_pointer(de) : 0; 502 hpfs_delete_de(i->i_sb, dnode, de); 503 set_last_pointer(i->i_sb, dnode, ddno); 504 hpfs_mark_4buffers_dirty(&qbh); 505 hpfs_brelse4(&qbh); 506 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from); 507 kfree(nde); 508 if (a) return 0; 509 return dno; 510 } 511 512 /* 513 * Check if a dnode is empty and delete it from the tree 514 * (chkdsk doesn't like empty dnodes) 515 */ 516 517 static void delete_empty_dnode(struct inode *i, dnode_secno dno) 518 { 519 struct hpfs_inode_info *hpfs_inode = hpfs_i(i); 520 struct quad_buffer_head qbh; 521 struct dnode *dnode; 522 dnode_secno down, up, ndown; 523 int p; 524 struct hpfs_dirent *de; 525 int c1, c2 = 0; 526 try_it_again: 527 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return; 528 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return; 529 if (le32_to_cpu(dnode->first_free) > 56) goto end; 530 if (le32_to_cpu(dnode->first_free) == 52 || le32_to_cpu(dnode->first_free) == 56) { 531 struct hpfs_dirent *de_end; 532 int root = dnode->root_dnode; 533 up = le32_to_cpu(dnode->up); 534 de = dnode_first_de(dnode); 535 down = de->down ? de_down_pointer(de) : 0; 536 if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) { 537 hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno); 538 goto end; 539 } 540 hpfs_brelse4(&qbh); 541 hpfs_free_dnode(i->i_sb, dno); 542 i->i_size -= 2048; 543 i->i_blocks -= 4; 544 if (root) { 545 struct fnode *fnode; 546 struct buffer_head *bh; 547 struct dnode *d1; 548 struct quad_buffer_head qbh1; 549 if (hpfs_sb(i->i_sb)->sb_chk) 550 if (up != i->i_ino) { 551 hpfs_error(i->i_sb, 552 "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx", 553 dno, up, 554 (unsigned long)i->i_ino); 555 return; 556 } 557 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) { 558 d1->up = cpu_to_le32(up); 559 d1->root_dnode = 1; 560 hpfs_mark_4buffers_dirty(&qbh1); 561 hpfs_brelse4(&qbh1); 562 } 563 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) { 564 fnode->u.external[0].disk_secno = cpu_to_le32(down); 565 mark_buffer_dirty(bh); 566 brelse(bh); 567 } 568 hpfs_inode->i_dno = down; 569 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12); 570 return; 571 } 572 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return; 573 p = 1; 574 de_end = dnode_end_de(dnode); 575 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++) 576 if (de->down) if (de_down_pointer(de) == dno) goto fnd; 577 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up); 578 goto end; 579 fnd: 580 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p); 581 if (!down) { 582 de->down = 0; 583 le16_add_cpu(&de->length, -4); 584 le32_add_cpu(&dnode->first_free, -4); 585 memmove(de_next_de(de), (char *)de_next_de(de) + 4, 586 (char *)dnode + le32_to_cpu(dnode->first_free) - (char *)de_next_de(de)); 587 } else { 588 struct dnode *d1; 589 struct quad_buffer_head qbh1; 590 *(dnode_secno *) ((void *) de + le16_to_cpu(de->length) - 4) = down; 591 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) { 592 d1->up = cpu_to_le32(up); 593 hpfs_mark_4buffers_dirty(&qbh1); 594 hpfs_brelse4(&qbh1); 595 } 596 } 597 } else { 598 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, le32_to_cpu(dnode->first_free)); 599 goto end; 600 } 601 602 if (!de->last) { 603 struct hpfs_dirent *de_next = de_next_de(de); 604 struct hpfs_dirent *de_cp; 605 struct dnode *d1; 606 struct quad_buffer_head qbh1; 607 if (!de_next->down) goto endm; 608 ndown = de_down_pointer(de_next); 609 if (!(de_cp = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) { 610 pr_err("out of memory for dtree balancing\n"); 611 goto endm; 612 } 613 memcpy(de_cp, de, le16_to_cpu(de->length)); 614 hpfs_delete_de(i->i_sb, dnode, de); 615 hpfs_mark_4buffers_dirty(&qbh); 616 hpfs_brelse4(&qbh); 617 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4); 618 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1); 619 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) { 620 d1->up = cpu_to_le32(ndown); 621 hpfs_mark_4buffers_dirty(&qbh1); 622 hpfs_brelse4(&qbh1); 623 } 624 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0); 625 /*pr_info("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", 626 up, ndown, down, dno);*/ 627 dno = up; 628 kfree(de_cp); 629 goto try_it_again; 630 } else { 631 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode); 632 struct hpfs_dirent *de_cp; 633 struct dnode *d1; 634 struct quad_buffer_head qbh1; 635 dnode_secno dlp; 636 if (!de_prev) { 637 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up); 638 hpfs_mark_4buffers_dirty(&qbh); 639 hpfs_brelse4(&qbh); 640 dno = up; 641 goto try_it_again; 642 } 643 if (!de_prev->down) goto endm; 644 ndown = de_down_pointer(de_prev); 645 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) { 646 struct hpfs_dirent *del = dnode_last_de(d1); 647 dlp = del->down ? de_down_pointer(del) : 0; 648 if (!dlp && down) { 649 if (le32_to_cpu(d1->first_free) > 2044) { 650 if (hpfs_sb(i->i_sb)->sb_chk >= 2) { 651 pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n"); 652 pr_err("terminating balancing operation\n"); 653 } 654 hpfs_brelse4(&qbh1); 655 goto endm; 656 } 657 if (hpfs_sb(i->i_sb)->sb_chk >= 2) { 658 pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n"); 659 pr_err("goin'on\n"); 660 } 661 le16_add_cpu(&del->length, 4); 662 del->down = 1; 663 le32_add_cpu(&d1->first_free, 4); 664 } 665 if (dlp && !down) { 666 le16_add_cpu(&del->length, -4); 667 del->down = 0; 668 le32_add_cpu(&d1->first_free, -4); 669 } else if (down) 670 *(__le32 *) ((void *) del + le16_to_cpu(del->length) - 4) = cpu_to_le32(down); 671 } else goto endm; 672 if (!(de_cp = kmalloc(le16_to_cpu(de_prev->length), GFP_NOFS))) { 673 pr_err("out of memory for dtree balancing\n"); 674 hpfs_brelse4(&qbh1); 675 goto endm; 676 } 677 hpfs_mark_4buffers_dirty(&qbh1); 678 hpfs_brelse4(&qbh1); 679 memcpy(de_cp, de_prev, le16_to_cpu(de_prev->length)); 680 hpfs_delete_de(i->i_sb, dnode, de_prev); 681 if (!de_prev->down) { 682 le16_add_cpu(&de_prev->length, 4); 683 de_prev->down = 1; 684 le32_add_cpu(&dnode->first_free, 4); 685 } 686 *(__le32 *) ((void *) de_prev + le16_to_cpu(de_prev->length) - 4) = cpu_to_le32(ndown); 687 hpfs_mark_4buffers_dirty(&qbh); 688 hpfs_brelse4(&qbh); 689 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4); 690 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1)); 691 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) { 692 d1->up = cpu_to_le32(ndown); 693 hpfs_mark_4buffers_dirty(&qbh1); 694 hpfs_brelse4(&qbh1); 695 } 696 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp); 697 dno = up; 698 kfree(de_cp); 699 goto try_it_again; 700 } 701 endm: 702 hpfs_mark_4buffers_dirty(&qbh); 703 end: 704 hpfs_brelse4(&qbh); 705 } 706 707 708 /* Delete dirent from directory */ 709 710 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de, 711 struct quad_buffer_head *qbh, int depth) 712 { 713 struct dnode *dnode = qbh->data; 714 dnode_secno down = 0; 715 loff_t t; 716 if (de->first || de->last) { 717 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno); 718 hpfs_brelse4(qbh); 719 return 1; 720 } 721 if (de->down) down = de_down_pointer(de); 722 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) { 723 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) { 724 hpfs_brelse4(qbh); 725 return 2; 726 } 727 } 728 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1); 729 hpfs_delete_de(i->i_sb, dnode, de); 730 hpfs_mark_4buffers_dirty(qbh); 731 hpfs_brelse4(qbh); 732 if (down) { 733 dnode_secno a = move_to_top(i, down, dno); 734 for_all_poss(i, hpfs_pos_subst, 5, t); 735 if (a) delete_empty_dnode(i, a); 736 return !a; 737 } 738 delete_empty_dnode(i, dno); 739 return 0; 740 } 741 742 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes, 743 int *n_subdirs, int *n_items) 744 { 745 struct dnode *dnode; 746 struct quad_buffer_head qbh; 747 struct hpfs_dirent *de; 748 dnode_secno ptr, odno = 0; 749 int c1, c2 = 0; 750 int d1, d2 = 0; 751 go_down: 752 if (n_dnodes) (*n_dnodes)++; 753 if (hpfs_sb(s)->sb_chk) 754 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return; 755 ptr = 0; 756 go_up: 757 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return; 758 if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && le32_to_cpu(dnode->up) != odno) 759 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, le32_to_cpu(dnode->up)); 760 de = dnode_first_de(dnode); 761 if (ptr) while(1) { 762 if (de->down) if (de_down_pointer(de) == ptr) goto process_de; 763 if (de->last) { 764 hpfs_brelse4(&qbh); 765 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x", 766 ptr, dno, odno); 767 return; 768 } 769 de = de_next_de(de); 770 } 771 next_de: 772 if (de->down) { 773 odno = dno; 774 dno = de_down_pointer(de); 775 hpfs_brelse4(&qbh); 776 goto go_down; 777 } 778 process_de: 779 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++; 780 if (!de->first && !de->last && n_items) (*n_items)++; 781 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de; 782 ptr = dno; 783 dno = le32_to_cpu(dnode->up); 784 if (dnode->root_dnode) { 785 hpfs_brelse4(&qbh); 786 return; 787 } 788 hpfs_brelse4(&qbh); 789 if (hpfs_sb(s)->sb_chk) 790 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return; 791 odno = -1; 792 goto go_up; 793 } 794 795 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n, 796 struct quad_buffer_head *qbh, struct dnode **dn) 797 { 798 int i; 799 struct hpfs_dirent *de, *de_end; 800 struct dnode *dnode; 801 dnode = hpfs_map_dnode(s, dno, qbh); 802 if (!dnode) return NULL; 803 if (dn) *dn=dnode; 804 de = dnode_first_de(dnode); 805 de_end = dnode_end_de(dnode); 806 for (i = 1; de < de_end; i++, de = de_next_de(de)) { 807 if (i == n) { 808 return de; 809 } 810 if (de->last) break; 811 } 812 hpfs_brelse4(qbh); 813 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n); 814 return NULL; 815 } 816 817 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno) 818 { 819 struct quad_buffer_head qbh; 820 dnode_secno d = dno; 821 dnode_secno up = 0; 822 struct hpfs_dirent *de; 823 int c1, c2 = 0; 824 825 again: 826 if (hpfs_sb(s)->sb_chk) 827 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible")) 828 return d; 829 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno; 830 if (hpfs_sb(s)->sb_chk) 831 if (up && le32_to_cpu(((struct dnode *)qbh.data)->up) != up) 832 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)); 833 if (!de->down) { 834 hpfs_brelse4(&qbh); 835 return d; 836 } 837 up = d; 838 d = de_down_pointer(de); 839 hpfs_brelse4(&qbh); 840 goto again; 841 } 842 843 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp, 844 struct quad_buffer_head *qbh) 845 { 846 loff_t pos; 847 unsigned c; 848 dnode_secno dno; 849 struct hpfs_dirent *de, *d; 850 struct hpfs_dirent *up_de; 851 struct hpfs_dirent *end_up_de; 852 struct dnode *dnode; 853 struct dnode *up_dnode; 854 struct quad_buffer_head qbh0; 855 856 pos = *posp; 857 dno = pos >> 6 << 2; 858 pos &= 077; 859 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode))) 860 goto bail; 861 862 /* Going to the next dirent */ 863 if ((d = de_next_de(de)) < dnode_end_de(dnode)) { 864 if (!(++*posp & 077)) { 865 hpfs_error(inode->i_sb, 866 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx", 867 (unsigned long long)*posp); 868 goto bail; 869 } 870 /* We're going down the tree */ 871 if (d->down) { 872 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1; 873 } 874 875 return de; 876 } 877 878 /* Going up */ 879 if (dnode->root_dnode) goto bail; 880 881 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, le32_to_cpu(dnode->up), &qbh0))) 882 goto bail; 883 884 end_up_de = dnode_end_de(up_dnode); 885 c = 0; 886 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de; 887 up_de = de_next_de(up_de)) { 888 if (!(++c & 077)) hpfs_error(inode->i_sb, 889 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode->up)); 890 if (up_de->down && de_down_pointer(up_de) == dno) { 891 *posp = ((loff_t) le32_to_cpu(dnode->up) << 4) + c; 892 hpfs_brelse4(&qbh0); 893 return de; 894 } 895 } 896 897 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x", 898 dno, le32_to_cpu(dnode->up)); 899 hpfs_brelse4(&qbh0); 900 901 bail: 902 *posp = 12; 903 return de; 904 } 905 906 /* Find a dirent in tree */ 907 908 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, 909 const unsigned char *name, unsigned len, 910 dnode_secno *dd, struct quad_buffer_head *qbh) 911 { 912 struct dnode *dnode; 913 struct hpfs_dirent *de; 914 struct hpfs_dirent *de_end; 915 int c1, c2 = 0; 916 917 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n"); 918 again: 919 if (hpfs_sb(inode->i_sb)->sb_chk) 920 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL; 921 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL; 922 923 de_end = dnode_end_de(dnode); 924 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) { 925 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last); 926 if (!t) { 927 if (dd) *dd = dno; 928 return de; 929 } 930 if (t < 0) { 931 if (de->down) { 932 dno = de_down_pointer(de); 933 hpfs_brelse4(qbh); 934 goto again; 935 } 936 break; 937 } 938 } 939 hpfs_brelse4(qbh); 940 return NULL; 941 } 942 943 /* 944 * Remove empty directory. In normal cases it is only one dnode with two 945 * entries, but we must handle also such obscure cases when it's a tree 946 * of empty dnodes. 947 */ 948 949 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno) 950 { 951 struct quad_buffer_head qbh; 952 struct dnode *dnode; 953 struct hpfs_dirent *de; 954 dnode_secno d1, d2, rdno = dno; 955 while (1) { 956 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return; 957 de = dnode_first_de(dnode); 958 if (de->last) { 959 if (de->down) d1 = de_down_pointer(de); 960 else goto error; 961 hpfs_brelse4(&qbh); 962 hpfs_free_dnode(s, dno); 963 dno = d1; 964 } else break; 965 } 966 if (!de->first) goto error; 967 d1 = de->down ? de_down_pointer(de) : 0; 968 de = de_next_de(de); 969 if (!de->last) goto error; 970 d2 = de->down ? de_down_pointer(de) : 0; 971 hpfs_brelse4(&qbh); 972 hpfs_free_dnode(s, dno); 973 do { 974 while (d1) { 975 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return; 976 de = dnode_first_de(dnode); 977 if (!de->last) goto error; 978 d1 = de->down ? de_down_pointer(de) : 0; 979 hpfs_brelse4(&qbh); 980 hpfs_free_dnode(s, dno); 981 } 982 d1 = d2; 983 d2 = 0; 984 } while (d1); 985 return; 986 error: 987 hpfs_brelse4(&qbh); 988 hpfs_free_dnode(s, dno); 989 hpfs_error(s, "directory %08x is corrupted or not empty", rdno); 990 } 991 992 /* 993 * Find dirent for specified fnode. Use truncated 15-char name in fnode as 994 * a help for searching. 995 */ 996 997 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno, 998 struct fnode *f, struct quad_buffer_head *qbh) 999 { 1000 unsigned char *name1; 1001 unsigned char *name2; 1002 int name1len, name2len; 1003 struct dnode *d; 1004 dnode_secno dno, downd; 1005 struct fnode *upf; 1006 struct buffer_head *bh; 1007 struct hpfs_dirent *de, *de_end; 1008 int c; 1009 int c1, c2 = 0; 1010 int d1, d2 = 0; 1011 name1 = f->name; 1012 if (!(name2 = kmalloc(256, GFP_NOFS))) { 1013 pr_err("out of memory, can't map dirent\n"); 1014 return NULL; 1015 } 1016 if (f->len <= 15) 1017 memcpy(name2, name1, name1len = name2len = f->len); 1018 else { 1019 memcpy(name2, name1, 15); 1020 memset(name2 + 15, 0xff, 256 - 15); 1021 /*name2[15] = 0xff;*/ 1022 name1len = 15; name2len = 256; 1023 } 1024 if (!(upf = hpfs_map_fnode(s, le32_to_cpu(f->up), &bh))) { 1025 kfree(name2); 1026 return NULL; 1027 } 1028 if (!fnode_is_dir(upf)) { 1029 brelse(bh); 1030 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, le32_to_cpu(f->up)); 1031 kfree(name2); 1032 return NULL; 1033 } 1034 dno = le32_to_cpu(upf->u.external[0].disk_secno); 1035 brelse(bh); 1036 go_down: 1037 downd = 0; 1038 go_up: 1039 if (!(d = hpfs_map_dnode(s, dno, qbh))) { 1040 kfree(name2); 1041 return NULL; 1042 } 1043 de_end = dnode_end_de(d); 1044 de = dnode_first_de(d); 1045 if (downd) { 1046 while (de < de_end) { 1047 if (de->down) if (de_down_pointer(de) == downd) goto f; 1048 de = de_next_de(de); 1049 } 1050 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno); 1051 hpfs_brelse4(qbh); 1052 kfree(name2); 1053 return NULL; 1054 } 1055 next_de: 1056 if (le32_to_cpu(de->fnode) == fno) { 1057 kfree(name2); 1058 return de; 1059 } 1060 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last); 1061 if (c < 0 && de->down) { 1062 dno = de_down_pointer(de); 1063 hpfs_brelse4(qbh); 1064 if (hpfs_sb(s)->sb_chk) 1065 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) { 1066 kfree(name2); 1067 return NULL; 1068 } 1069 goto go_down; 1070 } 1071 f: 1072 if (le32_to_cpu(de->fnode) == fno) { 1073 kfree(name2); 1074 return de; 1075 } 1076 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last); 1077 if (c < 0 && !de->last) goto not_found; 1078 if ((de = de_next_de(de)) < de_end) goto next_de; 1079 if (d->root_dnode) goto not_found; 1080 downd = dno; 1081 dno = le32_to_cpu(d->up); 1082 hpfs_brelse4(qbh); 1083 if (hpfs_sb(s)->sb_chk) 1084 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) { 1085 kfree(name2); 1086 return NULL; 1087 } 1088 goto go_up; 1089 not_found: 1090 hpfs_brelse4(qbh); 1091 hpfs_error(s, "dirent for fnode %08x not found", fno); 1092 kfree(name2); 1093 return NULL; 1094 } 1095