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