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