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