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