fs/hpfs/dnode.c

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