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) d->self << 4) | (loff_t)i;
  18                 i++;
  19         }
  20         printk("HPFS: get_pos: not_found\n");
  21         return ((loff_t)d->self << 4) | (loff_t)1;
  22 }
  23
  24 void hpfs_add_pos(struct inode *inode, loff_t *pos)
  25 {
  26         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
  27         int i = 0;
  28         loff_t **ppos;
  29
  30         if (hpfs_inode->i_rddir_off)
  31                 for (; hpfs_inode->i_rddir_off[i]; i++)
  32                         if (hpfs_inode->i_rddir_off[i] == pos) return;
  33         if (!(i&0x0f)) {
  34                 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
  35                         printk("HPFS: out of memory for position list\n");
  36                         return;
  37                 }
  38                 if (hpfs_inode->i_rddir_off) {
  39                         memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
  40                         kfree(hpfs_inode->i_rddir_off);
  41                 }
  42                 hpfs_inode->i_rddir_off = ppos;
  43         }
  44         hpfs_inode->i_rddir_off[i] = pos;
  45         hpfs_inode->i_rddir_off[i + 1] = NULL;
  46 }
  47
  48 void hpfs_del_pos(struct inode *inode, loff_t *pos)
  49 {
  50         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
  51         loff_t **i, **j;
  52
  53         if (!hpfs_inode->i_rddir_off) goto not_f;
  54         for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
  55         goto not_f;
  56         fnd:
  57         for (j = i + 1; *j; j++) ;
  58         *i = *(j - 1);
  59         *(j - 1) = NULL;
  60         if (j - 1 == hpfs_inode->i_rddir_off) {
  61                 kfree(hpfs_inode->i_rddir_off);
  62                 hpfs_inode->i_rddir_off = NULL;
  63         }
  64         return;
  65         not_f:
  66         /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
  67         return;
  68 }
  69
  70 static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
  71                          loff_t p1, loff_t p2)
  72 {
  73         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
  74         loff_t **i;
  75
  76         if (!hpfs_inode->i_rddir_off) return;
  77         for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
  78         return;
  79 }
  80
  81 static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
  82 {
  83         if (*p == f) *p = t;
  84 }
  85
  86 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
  87 {
  88         if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
  89 }*/
  90
  91 static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
  92 {
  93         if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
  94                 int n = (*p & 0x3f) + c;
  95                 if (n > 0x3f) printk("HPFS: hpfs_pos_ins: %08x + %d\n", (int)*p, (int)c >> 8);
  96                 else *p = (*p & ~0x3f) | n;
  97         }
  98 }
  99
 100 static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
 101 {
 102         if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
 103                 int n = (*p & 0x3f) - c;
 104                 if (n < 1) printk("HPFS: hpfs_pos_ins: %08x - %d\n", (int)*p, (int)c >> 8);
 105                 else *p = (*p & ~0x3f) | n;
 106         }
 107 }
 108
 109 static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
 110 {
 111         struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
 112         de_end = dnode_end_de(d);
 113         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
 114                 deee = dee; dee = de;
 115         }
 116         return deee;
 117 }
 118
 119 static struct hpfs_dirent *dnode_last_de(struct dnode *d)
 120 {
 121         struct hpfs_dirent *de, *de_end, *dee = NULL;
 122         de_end = dnode_end_de(d);
 123         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
 124                 dee = de;
 125         }
 126         return dee;
 127 }
 128
 129 static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
 130 {
 131         struct hpfs_dirent *de;
 132         if (!(de = dnode_last_de(d))) {
 133                 hpfs_error(s, "set_last_pointer: empty dnode %08x", d->self);
 134                 return;
 135         }
 136         if (hpfs_sb(s)->sb_chk) {
 137                 if (de->down) {
 138                         hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
 139                                 d->self, de_down_pointer(de));
 140                         return;
 141                 }
 142                 if (de->length != 32) {
 143                         hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", d->self);
 144                         return;
 145                 }
 146         }
 147         if (ptr) {
 148                 if ((d->first_free += 4) > 2048) {
 149                         hpfs_error(s,"set_last_pointer: too long dnode %08x", d->self);
 150                         d->first_free -= 4;
 151                         return;
 152                 }
 153                 de->length = 36;
 154                 de->down = 1;
 155                 *(dnode_secno *)((char *)de + 32) = ptr;
 156         }
 157 }
 158
 159 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
 160
 161 struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d,
 162                                 const unsigned char *name,
 163                                 unsigned namelen, secno down_ptr)
 164 {
 165         struct hpfs_dirent *de;
 166         struct hpfs_dirent *de_end = dnode_end_de(d);
 167         unsigned d_size = de_size(namelen, down_ptr);
 168         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
 169                 int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
 170                 if (!c) {
 171                         hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, d->self);
 172                         return NULL;
 173                 }
 174                 if (c < 0) break;
 175         }
 176         memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
 177         memset(de, 0, d_size);
 178         if (down_ptr) {
 179                 *(int *)((char *)de + d_size - 4) = down_ptr;
 180                 de->down = 1;
 181         }
 182         de->length = d_size;
 183         if (down_ptr) de->down = 1;
 184         de->not_8x3 = hpfs_is_name_long(name, namelen);
 185         de->namelen = namelen;
 186         memcpy(de->name, name, namelen);
 187         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", d->self);
 198                 return;
 199         }
 200         d->first_free -= de->length;
 201         memmove(de, de_next_de(de), 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 = 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 (dd->up != dno || dd->root_dnode) {
 215                                         dd->up = 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 (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, 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, d->up, &adno, &qbh1, 0))) {
 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, nd->first_free + (char *)nd - (char *)de);
 317         nd->first_free -= (char *)de - (char *)nd - 20;
 318         memcpy(d, nd, 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                 dno = ad->up = d->up;
 323                 hpfs_mark_4buffers_dirty(&qbh);
 324                 hpfs_brelse4(&qbh);
 325                 hpfs_mark_4buffers_dirty(&qbh1);
 326                 hpfs_brelse4(&qbh1);
 327                 goto go_up;
 328         }
 329         if (!(rd = hpfs_alloc_dnode(i->i_sb, d->up, &rdno, &qbh2, 0))) {
 330                 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
 331                 hpfs_brelse4(&qbh);
 332                 hpfs_brelse4(&qbh1);
 333                 kfree(nd);
 334                 kfree(nname);
 335                 return 1;
 336         }
 337         i->i_size += 2048;
 338         i->i_blocks += 4;
 339         rd->root_dnode = 1;
 340         rd->up = d->up;
 341         if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) {
 342                 hpfs_free_dnode(i->i_sb, rdno);
 343                 hpfs_brelse4(&qbh);
 344                 hpfs_brelse4(&qbh1);
 345                 hpfs_brelse4(&qbh2);
 346                 kfree(nd);
 347                 kfree(nname);
 348                 return 1;
 349         }
 350         fnode->u.external[0].disk_secno = rdno;
 351         mark_buffer_dirty(bh);
 352         brelse(bh);
 353         d->up = ad->up = hpfs_i(i)->i_dno = rdno;
 354         d->root_dnode = ad->root_dnode = 0;
 355         hpfs_mark_4buffers_dirty(&qbh);
 356         hpfs_brelse4(&qbh);
 357         hpfs_mark_4buffers_dirty(&qbh1);
 358         hpfs_brelse4(&qbh1);
 359         qbh = qbh2;
 360         set_last_pointer(i->i_sb, rd, dno);
 361         dno = rdno;
 362         d = rd;
 363         goto go_up_a;
 364 }
 365
 366 /*
 367  * Add an entry to directory btree.
 368  * I hate such crazy directory structure.
 369  * It's easy to read but terrible to write.
 370  * I wrote this directory code 4 times.
 371  * I hope, now it's finally bug-free.
 372  */
 373
 374 int hpfs_add_dirent(struct inode *i,
 375                     const unsigned char *name, unsigned namelen,
 376                     struct hpfs_dirent *new_de, int cdepth)
 377 {
 378         struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
 379         struct dnode *d;
 380         struct hpfs_dirent *de, *de_end;
 381         struct quad_buffer_head qbh;
 382         dnode_secno dno;
 383         int c;
 384         int c1, c2 = 0;
 385         dno = hpfs_inode->i_dno;
 386         down:
 387         if (hpfs_sb(i->i_sb)->sb_chk)
 388                 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
 389         if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
 390         de_end = dnode_end_de(d);
 391         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
 392                 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
 393                         hpfs_brelse4(&qbh);
 394                         return -1;
 395                 }
 396                 if (c < 0) {
 397                         if (de->down) {
 398                                 dno = de_down_pointer(de);
 399                                 hpfs_brelse4(&qbh);
 400                                 goto down;
 401                         }
 402                         break;
 403                 }
 404         }
 405         hpfs_brelse4(&qbh);
 406         if (!cdepth) hpfs_lock_creation(i->i_sb);
 407         if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
 408                 c = 1;
 409                 goto ret;
 410         }
 411         i->i_version++;
 412         c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
 413         ret:
 414         if (!cdepth) hpfs_unlock_creation(i->i_sb);
 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 (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, 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 = 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 -= 4;
 478                 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(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, 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 (dnode->first_free > 56) goto end;
 521         if (dnode->first_free == 52 || dnode->first_free == 56) {
 522                 struct hpfs_dirent *de_end;
 523                 int root = dnode->root_dnode;
 524                 up = 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 = 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 = 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 -= 4;
 574                         dnode->first_free -= 4;
 575                         memmove(de_next_de(de), (char *)de_next_de(de) + 4,
 576                                 (char *)dnode + 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 + de->length - 4) = down;
 581                         if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
 582                                 d1->up = 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, 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(de->length, GFP_NOFS))) {
 600                         printk("HPFS: out of memory for dtree balancing\n");
 601                         goto endm;
 602                 }
 603                 memcpy(de_cp, de, 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 = 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 (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 += 4;
 651                                 del->down = 1;
 652                                 d1->first_free += 4;
 653                         }
 654                         if (dlp && !down) {
 655                                 del->length -= 4;
 656                                 del->down = 0;
 657                                 d1->first_free -= 4;
 658                         } else if (down)
 659                                 *(dnode_secno *) ((void *) del + del->length - 4) = down;
 660                 } else goto endm;
 661                 if (!(de_cp = kmalloc(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, de_prev->length);
 669                 hpfs_delete_de(i->i_sb, dnode, de_prev);
 670                 if (!de_prev->down) {
 671                         de_prev->length += 4;
 672                         de_prev->down = 1;
 673                         dnode->first_free += 4;
 674                 }
 675                 *(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = 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 = 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         int lock = 0;
 705         loff_t t;
 706         if (de->first || de->last) {
 707                 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
 708                 hpfs_brelse4(qbh);
 709                 return 1;
 710         }
 711         if (de->down) down = de_down_pointer(de);
 712         if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
 713                 lock = 1;
 714                 hpfs_lock_creation(i->i_sb);
 715                 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
 716                         hpfs_brelse4(qbh);
 717                         hpfs_unlock_creation(i->i_sb);
 718                         return 2;
 719                 }
 720         }
 721         i->i_version++;
 722         for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
 723         hpfs_delete_de(i->i_sb, dnode, de);
 724         hpfs_mark_4buffers_dirty(qbh);
 725         hpfs_brelse4(qbh);
 726         if (down) {
 727                 dnode_secno a = move_to_top(i, down, dno);
 728                 for_all_poss(i, hpfs_pos_subst, 5, t);
 729                 if (a) delete_empty_dnode(i, a);
 730                 if (lock) hpfs_unlock_creation(i->i_sb);
 731                 return !a;
 732         }
 733         delete_empty_dnode(i, dno);
 734         if (lock) hpfs_unlock_creation(i->i_sb);
 735         return 0;
 736 }
 737
 738 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
 739                        int *n_subdirs, int *n_items)
 740 {
 741         struct dnode *dnode;
 742         struct quad_buffer_head qbh;
 743         struct hpfs_dirent *de;
 744         dnode_secno ptr, odno = 0;
 745         int c1, c2 = 0;
 746         int d1, d2 = 0;
 747         go_down:
 748         if (n_dnodes) (*n_dnodes)++;
 749         if (hpfs_sb(s)->sb_chk)
 750                 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
 751         ptr = 0;
 752         go_up:
 753         if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
 754         if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && dnode->up != odno)
 755                 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up);
 756         de = dnode_first_de(dnode);
 757         if (ptr) while(1) {
 758                 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
 759                 if (de->last) {
 760                         hpfs_brelse4(&qbh);
 761                         hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
 762                                 ptr, dno, odno);
 763                         return;
 764                 }
 765                 de = de_next_de(de);
 766         }
 767         next_de:
 768         if (de->down) {
 769                 odno = dno;
 770                 dno = de_down_pointer(de);
 771                 hpfs_brelse4(&qbh);
 772                 goto go_down;
 773         }
 774         process_de:
 775         if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
 776         if (!de->first && !de->last && n_items) (*n_items)++;
 777         if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
 778         ptr = dno;
 779         dno = dnode->up;
 780         if (dnode->root_dnode) {
 781                 hpfs_brelse4(&qbh);
 782                 return;
 783         }
 784         hpfs_brelse4(&qbh);
 785         if (hpfs_sb(s)->sb_chk)
 786                 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
 787         odno = -1;
 788         goto go_up;
 789 }
 790
 791 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
 792                                           struct quad_buffer_head *qbh, struct dnode **dn)
 793 {
 794         int i;
 795         struct hpfs_dirent *de, *de_end;
 796         struct dnode *dnode;
 797         dnode = hpfs_map_dnode(s, dno, qbh);
 798         if (!dnode) return NULL;
 799         if (dn) *dn=dnode;
 800         de = dnode_first_de(dnode);
 801         de_end = dnode_end_de(dnode);
 802         for (i = 1; de < de_end; i++, de = de_next_de(de)) {
 803                 if (i == n) {
 804                         return de;
 805                 }
 806                 if (de->last) break;
 807         }
 808         hpfs_brelse4(qbh);
 809         hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
 810         return NULL;
 811 }
 812
 813 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
 814 {
 815         struct quad_buffer_head qbh;
 816         dnode_secno d = dno;
 817         dnode_secno up = 0;
 818         struct hpfs_dirent *de;
 819         int c1, c2 = 0;
 820
 821         again:
 822         if (hpfs_sb(s)->sb_chk)
 823                 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
 824                         return d;
 825         if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
 826         if (hpfs_sb(s)->sb_chk)
 827                 if (up && ((struct dnode *)qbh.data)->up != up)
 828                         hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, ((struct dnode *)qbh.data)->up);
 829         if (!de->down) {
 830                 hpfs_brelse4(&qbh);
 831                 return d;
 832         }
 833         up = d;
 834         d = de_down_pointer(de);
 835         hpfs_brelse4(&qbh);
 836         goto again;
 837 }
 838
 839 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
 840                                    struct quad_buffer_head *qbh)
 841 {
 842         loff_t pos;
 843         unsigned c;
 844         dnode_secno dno;
 845         struct hpfs_dirent *de, *d;
 846         struct hpfs_dirent *up_de;
 847         struct hpfs_dirent *end_up_de;
 848         struct dnode *dnode;
 849         struct dnode *up_dnode;
 850         struct quad_buffer_head qbh0;
 851
 852         pos = *posp;
 853         dno = pos >> 6 << 2;
 854         pos &= 077;
 855         if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
 856                 goto bail;
 857
 858         /* Going to the next dirent */
 859         if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
 860                 if (!(++*posp & 077)) {
 861                         hpfs_error(inode->i_sb,
 862                                 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
 863                                 (unsigned long long)*posp);
 864                         goto bail;
 865                 }
 866                 /* We're going down the tree */
 867                 if (d->down) {
 868                         *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
 869                 }
 870
 871                 return de;
 872         }
 873
 874         /* Going up */
 875         if (dnode->root_dnode) goto bail;
 876
 877         if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0)))
 878                 goto bail;
 879
 880         end_up_de = dnode_end_de(up_dnode);
 881         c = 0;
 882         for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
 883              up_de = de_next_de(up_de)) {
 884                 if (!(++c & 077)) hpfs_error(inode->i_sb,
 885                         "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up);
 886                 if (up_de->down && de_down_pointer(up_de) == dno) {
 887                         *posp = ((loff_t) dnode->up << 4) + c;
 888                         hpfs_brelse4(&qbh0);
 889                         return de;
 890                 }
 891         }
 892
 893         hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
 894                 dno, dnode->up);
 895         hpfs_brelse4(&qbh0);
 896
 897         bail:
 898         *posp = 12;
 899         return de;
 900 }
 901
 902 /* Find a dirent in tree */
 903
 904 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
 905                                const unsigned char *name, unsigned len,
 906                                dnode_secno *dd, struct quad_buffer_head *qbh)
 907 {
 908         struct dnode *dnode;
 909         struct hpfs_dirent *de;
 910         struct hpfs_dirent *de_end;
 911         int c1, c2 = 0;
 912
 913         if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
 914         again:
 915         if (hpfs_sb(inode->i_sb)->sb_chk)
 916                 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
 917         if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
 918
 919         de_end = dnode_end_de(dnode);
 920         for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
 921                 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
 922                 if (!t) {
 923                         if (dd) *dd = dno;
 924                         return de;
 925                 }
 926                 if (t < 0) {
 927                         if (de->down) {
 928                                 dno = de_down_pointer(de);
 929                                 hpfs_brelse4(qbh);
 930                                 goto again;
 931                         }
 932                 break;
 933                 }
 934         }
 935         hpfs_brelse4(qbh);
 936         return NULL;
 937 }
 938
 939 /*
 940  * Remove empty directory. In normal cases it is only one dnode with two
 941  * entries, but we must handle also such obscure cases when it's a tree
 942  * of empty dnodes.
 943  */
 944
 945 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
 946 {
 947         struct quad_buffer_head qbh;
 948         struct dnode *dnode;
 949         struct hpfs_dirent *de;
 950         dnode_secno d1, d2, rdno = dno;
 951         while (1) {
 952                 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
 953                 de = dnode_first_de(dnode);
 954                 if (de->last) {
 955                         if (de->down) d1 = de_down_pointer(de);
 956                         else goto error;
 957                         hpfs_brelse4(&qbh);
 958                         hpfs_free_dnode(s, dno);
 959                         dno = d1;
 960                 } else break;
 961         }
 962         if (!de->first) goto error;
 963         d1 = de->down ? de_down_pointer(de) : 0;
 964         de = de_next_de(de);
 965         if (!de->last) goto error;
 966         d2 = de->down ? de_down_pointer(de) : 0;
 967         hpfs_brelse4(&qbh);
 968         hpfs_free_dnode(s, dno);
 969         do {
 970                 while (d1) {
 971                         if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
 972                         de = dnode_first_de(dnode);
 973                         if (!de->last) goto error;
 974                         d1 = de->down ? de_down_pointer(de) : 0;
 975                         hpfs_brelse4(&qbh);
 976                         hpfs_free_dnode(s, dno);
 977                 }
 978                 d1 = d2;
 979                 d2 = 0;
 980         } while (d1);
 981         return;
 982         error:
 983         hpfs_brelse4(&qbh);
 984         hpfs_free_dnode(s, dno);
 985         hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
 986 }
 987
 988 /*
 989  * Find dirent for specified fnode. Use truncated 15-char name in fnode as
 990  * a help for searching.
 991  */
 992
 993 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
 994                                      struct fnode *f, struct quad_buffer_head *qbh)
 995 {
 996         unsigned char *name1;
 997         unsigned char *name2;
 998         int name1len, name2len;
 999         struct dnode *d;
1000         dnode_secno dno, downd;
1001         struct fnode *upf;
1002         struct buffer_head *bh;
1003         struct hpfs_dirent *de, *de_end;
1004         int c;
1005         int c1, c2 = 0;
1006         int d1, d2 = 0;
1007         name1 = f->name;
1008         if (!(name2 = kmalloc(256, GFP_NOFS))) {
1009                 printk("HPFS: out of memory, can't map dirent\n");
1010                 return NULL;
1011         }
1012         if (f->len <= 15)
1013                 memcpy(name2, name1, name1len = name2len = f->len);
1014         else {
1015                 memcpy(name2, name1, 15);
1016                 memset(name2 + 15, 0xff, 256 - 15);
1017                 /*name2[15] = 0xff;*/
1018                 name1len = 15; name2len = 256;
1019         }
1020         if (!(upf = hpfs_map_fnode(s, f->up, &bh))) {
1021                 kfree(name2);
1022                 return NULL;
1023         }
1024         if (!upf->dirflag) {
1025                 brelse(bh);
1026                 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up);
1027                 kfree(name2);
1028                 return NULL;
1029         }
1030         dno = upf->u.external[0].disk_secno;
1031         brelse(bh);
1032         go_down:
1033         downd = 0;
1034         go_up:
1035         if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1036                 kfree(name2);
1037                 return NULL;
1038         }
1039         de_end = dnode_end_de(d);
1040         de = dnode_first_de(d);
1041         if (downd) {
1042                 while (de < de_end) {
1043                         if (de->down) if (de_down_pointer(de) == downd) goto f;
1044                         de = de_next_de(de);
1045                 }
1046                 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1047                 hpfs_brelse4(qbh);
1048                 kfree(name2);
1049                 return NULL;
1050         }
1051         next_de:
1052         if (de->fnode == fno) {
1053                 kfree(name2);
1054                 return de;
1055         }
1056         c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1057         if (c < 0 && de->down) {
1058                 dno = de_down_pointer(de);
1059                 hpfs_brelse4(qbh);
1060                 if (hpfs_sb(s)->sb_chk)
1061                         if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1062                         kfree(name2);
1063                         return NULL;
1064                 }
1065                 goto go_down;
1066         }
1067         f:
1068         if (de->fnode == fno) {
1069                 kfree(name2);
1070                 return de;
1071         }
1072         c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1073         if (c < 0 && !de->last) goto not_found;
1074         if ((de = de_next_de(de)) < de_end) goto next_de;
1075         if (d->root_dnode) goto not_found;
1076         downd = dno;
1077         dno = d->up;
1078         hpfs_brelse4(qbh);
1079         if (hpfs_sb(s)->sb_chk)
1080                 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1081                         kfree(name2);
1082                         return NULL;
1083                 }
1084         goto go_up;
1085         not_found:
1086         hpfs_brelse4(qbh);
1087         hpfs_error(s, "dirent for fnode %08x not found", fno);
1088         kfree(name2);
1089         return NULL;
1090 }