2 * linux/fs/hpfs/dnode.c
4 * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
6 * handling directory dnode tree - adding, deleteing & searching for dirents
11 static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
13 struct hpfs_dirent *de;
14 struct hpfs_dirent *de_end = dnode_end_de(d);
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;
20 printk("HPFS: get_pos: not_found\n");
21 return ((loff_t)d->self << 4) | (loff_t)1;
24 void hpfs_add_pos(struct inode *inode, loff_t *pos)
26 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
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;
34 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
35 printk("HPFS: out of memory for position list\n");
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);
42 hpfs_inode->i_rddir_off = ppos;
44 hpfs_inode->i_rddir_off[i] = pos;
45 hpfs_inode->i_rddir_off[i + 1] = NULL;
48 void hpfs_del_pos(struct inode *inode, loff_t *pos)
50 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
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;
57 for (j = i + 1; *j; j++) ;
60 if (j - 1 == hpfs_inode->i_rddir_off) {
61 kfree(hpfs_inode->i_rddir_off);
62 hpfs_inode->i_rddir_off = NULL;
66 /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
70 static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
73 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
76 if (!hpfs_inode->i_rddir_off) return;
77 for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
81 void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
86 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
88 if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
91 void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
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;
100 void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
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;
109 static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
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;
119 static struct hpfs_dirent *dnode_last_de(struct dnode *d)
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)) {
129 static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
131 struct hpfs_dirent *de;
132 if (!(de = dnode_last_de(d))) {
133 hpfs_error(s, "set_last_pointer: empty dnode %08x", d->self);
136 if (hpfs_sb(s)->sb_chk) {
138 hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
139 d->self, de_down_pointer(de));
142 if (de->length != 32) {
143 hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", d->self);
148 if ((d->first_free += 4) > 2048) {
149 hpfs_error(s,"set_last_pointer: too long dnode %08x", d->self);
155 *(dnode_secno *)((char *)de + 32) = ptr;
159 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
161 struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d, unsigned char *name,
162 unsigned namelen, secno down_ptr)
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);
170 hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, d->self);
175 memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
176 memset(de, 0, d_size);
178 *(int *)((char *)de + d_size - 4) = down_ptr;
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;
190 /* Delete dirent and don't care about its subtree */
192 void hpfs_delete_de(struct super_block *s, struct dnode *d, struct hpfs_dirent *de)
195 hpfs_error(s, "attempt to delete last dirent in dnode %08x", d->self);
198 d->first_free -= de->length;
199 memmove(de, de_next_de(de), d->first_free + (char *)d - (char *)de);
202 static void fix_up_ptrs(struct super_block *s, struct dnode *d)
204 struct hpfs_dirent *de;
205 struct hpfs_dirent *de_end = dnode_end_de(d);
206 dnode_secno dno = d->self;
207 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
209 struct quad_buffer_head qbh;
211 if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
212 if (dd->up != dno || dd->root_dnode) {
215 hpfs_mark_4buffers_dirty(&qbh);
222 /* Add an entry to dnode and do dnode splitting if required */
224 int hpfs_add_to_dnode(struct inode *i, dnode_secno dno, unsigned char *name, unsigned namelen,
225 struct hpfs_dirent *new_de, dnode_secno down_ptr)
227 struct quad_buffer_head qbh, qbh1, qbh2;
228 struct dnode *d, *ad, *rd, *nd = NULL;
229 dnode_secno adno, rdno;
230 struct hpfs_dirent *de;
231 struct hpfs_dirent nde;
235 struct buffer_head *bh;
238 if (!(nname = kmalloc(256, GFP_NOFS))) {
239 printk("HPFS: out of memory, can't add to dnode\n");
243 if (namelen >= 256) {
244 hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen);
249 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
255 if (hpfs_sb(i->i_sb)->sb_chk)
256 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
262 if (d->first_free + de_size(namelen, down_ptr) <= 2048) {
264 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
266 for_all_poss(i, hpfs_pos_ins, t, 1);
267 for_all_poss(i, hpfs_pos_subst, 4, t);
268 for_all_poss(i, hpfs_pos_subst, 5, t + 1);
269 hpfs_mark_4buffers_dirty(&qbh);
275 if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
276 /* 0x924 is a max size of dnode after adding a dirent with
277 max name length. We alloc this only once. There must
278 not be any error while splitting dnodes, otherwise the
279 whole directory, not only file we're adding, would
281 printk("HPFS: out of memory for dnode splitting\n");
286 memcpy(nd, d, d->first_free);
287 copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
288 for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
289 h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
290 if (!(ad = hpfs_alloc_dnode(i->i_sb, d->up, &adno, &qbh1, 0))) {
291 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
300 for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
301 copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
302 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
305 copy_de(new_de = &nde, de);
306 memcpy(name = nname, de->name, namelen = de->namelen);
307 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
309 set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
311 memmove((char *)nd + 20, de, nd->first_free + (char *)nd - (char *)de);
312 nd->first_free -= (char *)de - (char *)nd - 20;
313 memcpy(d, nd, nd->first_free);
314 for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
315 fix_up_ptrs(i->i_sb, ad);
316 if (!d->root_dnode) {
317 dno = ad->up = d->up;
318 hpfs_mark_4buffers_dirty(&qbh);
320 hpfs_mark_4buffers_dirty(&qbh1);
324 if (!(rd = hpfs_alloc_dnode(i->i_sb, d->up, &rdno, &qbh2, 0))) {
325 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
336 if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) {
337 hpfs_free_dnode(i->i_sb, rdno);
345 fnode->u.external[0].disk_secno = rdno;
346 mark_buffer_dirty(bh);
348 d->up = ad->up = hpfs_i(i)->i_dno = rdno;
349 d->root_dnode = ad->root_dnode = 0;
350 hpfs_mark_4buffers_dirty(&qbh);
352 hpfs_mark_4buffers_dirty(&qbh1);
355 set_last_pointer(i->i_sb, rd, dno);
362 * Add an entry to directory btree.
363 * I hate such crazy directory structure.
364 * It's easy to read but terrible to write.
365 * I wrote this directory code 4 times.
366 * I hope, now it's finally bug-free.
369 int hpfs_add_dirent(struct inode *i, unsigned char *name, unsigned namelen,
370 struct hpfs_dirent *new_de, int cdepth)
372 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
374 struct hpfs_dirent *de, *de_end;
375 struct quad_buffer_head qbh;
379 dno = hpfs_inode->i_dno;
381 if (hpfs_sb(i->i_sb)->sb_chk)
382 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
383 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
384 de_end = dnode_end_de(d);
385 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
386 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
392 dno = de_down_pointer(de);
400 if (!cdepth) hpfs_lock_creation(i->i_sb);
401 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
406 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
408 if (!cdepth) hpfs_unlock_creation(i->i_sb);
413 * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
414 * Return the dnode we moved from (to be checked later if it's empty)
417 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
419 dnode_secno dno, ddno;
420 dnode_secno chk_up = to;
422 struct quad_buffer_head qbh;
423 struct hpfs_dirent *de, *nde;
429 if (hpfs_sb(i->i_sb)->sb_chk)
430 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
432 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
433 if (hpfs_sb(i->i_sb)->sb_chk) {
434 if (dnode->up != chk_up) {
435 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
436 dno, chk_up, dnode->up);
442 if (!(de = dnode_last_de(dnode))) {
443 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
447 if (!de->down) break;
448 dno = de_down_pointer(de);
451 while (!(de = dnode_pre_last_de(dnode))) {
452 dnode_secno up = dnode->up;
454 hpfs_free_dnode(i->i_sb, dno);
457 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
458 if (up == to) return to;
459 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
460 if (dnode->root_dnode) {
461 hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
465 de = dnode_last_de(dnode);
466 if (!de || !de->down) {
467 hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
471 dnode->first_free -= 4;
474 hpfs_mark_4buffers_dirty(&qbh);
477 t = get_pos(dnode, de);
478 for_all_poss(i, hpfs_pos_subst, t, 4);
479 for_all_poss(i, hpfs_pos_subst, t + 1, 5);
480 if (!(nde = kmalloc(de->length, GFP_NOFS))) {
481 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
485 memcpy(nde, de, de->length);
486 ddno = de->down ? de_down_pointer(de) : 0;
487 hpfs_delete_de(i->i_sb, dnode, de);
488 set_last_pointer(i->i_sb, dnode, ddno);
489 hpfs_mark_4buffers_dirty(&qbh);
491 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
498 * Check if a dnode is empty and delete it from the tree
499 * (chkdsk doesn't like empty dnodes)
502 static void delete_empty_dnode(struct inode *i, dnode_secno dno)
504 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
505 struct quad_buffer_head qbh;
507 dnode_secno down, up, ndown;
509 struct hpfs_dirent *de;
512 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
513 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
514 if (dnode->first_free > 56) goto end;
515 if (dnode->first_free == 52 || dnode->first_free == 56) {
516 struct hpfs_dirent *de_end;
517 int root = dnode->root_dnode;
519 de = dnode_first_de(dnode);
520 down = de->down ? de_down_pointer(de) : 0;
521 if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
522 hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
526 hpfs_free_dnode(i->i_sb, dno);
531 struct buffer_head *bh;
533 struct quad_buffer_head qbh1;
534 if (hpfs_sb(i->i_sb)->sb_chk) if (up != i->i_ino) {
535 hpfs_error(i->i_sb, "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08x", dno, up, i->i_ino);
538 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
541 hpfs_mark_4buffers_dirty(&qbh1);
544 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
545 fnode->u.external[0].disk_secno = down;
546 mark_buffer_dirty(bh);
549 hpfs_inode->i_dno = down;
550 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
553 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
555 de_end = dnode_end_de(dnode);
556 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
557 if (de->down) if (de_down_pointer(de) == dno) goto fnd;
558 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
561 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
565 dnode->first_free -= 4;
566 memmove(de_next_de(de), (char *)de_next_de(de) + 4,
567 (char *)dnode + dnode->first_free - (char *)de_next_de(de));
570 struct quad_buffer_head qbh1;
571 *(dnode_secno *) ((void *) de + de->length - 4) = down;
572 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
574 hpfs_mark_4buffers_dirty(&qbh1);
579 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, dnode->first_free);
584 struct hpfs_dirent *de_next = de_next_de(de);
585 struct hpfs_dirent *de_cp;
587 struct quad_buffer_head qbh1;
588 if (!de_next->down) goto endm;
589 ndown = de_down_pointer(de_next);
590 if (!(de_cp = kmalloc(de->length, GFP_NOFS))) {
591 printk("HPFS: out of memory for dtree balancing\n");
594 memcpy(de_cp, de, de->length);
595 hpfs_delete_de(i->i_sb, dnode, de);
596 hpfs_mark_4buffers_dirty(&qbh);
598 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
599 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
600 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
602 hpfs_mark_4buffers_dirty(&qbh1);
605 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
606 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
611 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
612 struct hpfs_dirent *de_cp;
614 struct quad_buffer_head qbh1;
617 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
618 hpfs_mark_4buffers_dirty(&qbh);
623 if (!de_prev->down) goto endm;
624 ndown = de_down_pointer(de_prev);
625 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
626 struct hpfs_dirent *del = dnode_last_de(d1);
627 dlp = del->down ? de_down_pointer(del) : 0;
629 if (d1->first_free > 2044) {
630 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
631 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
632 printk("HPFS: warning: terminating balancing operation\n");
637 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
638 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
639 printk("HPFS: warning: goin'on\n");
650 *(dnode_secno *) ((void *) del + del->length - 4) = down;
652 if (!(de_cp = kmalloc(de_prev->length, GFP_NOFS))) {
653 printk("HPFS: out of memory for dtree balancing\n");
657 hpfs_mark_4buffers_dirty(&qbh1);
659 memcpy(de_cp, de_prev, de_prev->length);
660 hpfs_delete_de(i->i_sb, dnode, de_prev);
661 if (!de_prev->down) {
662 de_prev->length += 4;
664 dnode->first_free += 4;
666 *(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = ndown;
667 hpfs_mark_4buffers_dirty(&qbh);
669 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
670 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
671 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
673 hpfs_mark_4buffers_dirty(&qbh1);
676 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
682 hpfs_mark_4buffers_dirty(&qbh);
688 /* Delete dirent from directory */
690 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
691 struct quad_buffer_head *qbh, int depth)
693 struct dnode *dnode = qbh->data;
694 dnode_secno down = 0;
697 if (de->first || de->last) {
698 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
702 if (de->down) down = de_down_pointer(de);
703 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
705 hpfs_lock_creation(i->i_sb);
706 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
708 hpfs_unlock_creation(i->i_sb);
713 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
714 hpfs_delete_de(i->i_sb, dnode, de);
715 hpfs_mark_4buffers_dirty(qbh);
718 dnode_secno a = move_to_top(i, down, dno);
719 for_all_poss(i, hpfs_pos_subst, 5, t);
720 if (a) delete_empty_dnode(i, a);
721 if (lock) hpfs_unlock_creation(i->i_sb);
724 delete_empty_dnode(i, dno);
725 if (lock) hpfs_unlock_creation(i->i_sb);
729 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
730 int *n_subdirs, int *n_items)
733 struct quad_buffer_head qbh;
734 struct hpfs_dirent *de;
735 dnode_secno ptr, odno = 0;
739 if (n_dnodes) (*n_dnodes)++;
740 if (hpfs_sb(s)->sb_chk)
741 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
744 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
745 if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && dnode->up != odno)
746 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up);
747 de = dnode_first_de(dnode);
749 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
752 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
761 dno = de_down_pointer(de);
766 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
767 if (!de->first && !de->last && n_items) (*n_items)++;
768 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
771 if (dnode->root_dnode) {
776 if (hpfs_sb(s)->sb_chk)
777 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
782 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
783 struct quad_buffer_head *qbh, struct dnode **dn)
786 struct hpfs_dirent *de, *de_end;
788 dnode = hpfs_map_dnode(s, dno, qbh);
789 if (!dnode) return NULL;
791 de = dnode_first_de(dnode);
792 de_end = dnode_end_de(dnode);
793 for (i = 1; de < de_end; i++, de = de_next_de(de)) {
800 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
804 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
806 struct quad_buffer_head qbh;
809 struct hpfs_dirent *de;
813 if (hpfs_sb(s)->sb_chk)
814 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
816 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
817 if (hpfs_sb(s)->sb_chk)
818 if (up && ((struct dnode *)qbh.data)->up != up)
819 hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, ((struct dnode *)qbh.data)->up);
825 d = de_down_pointer(de);
830 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
831 struct quad_buffer_head *qbh)
836 struct hpfs_dirent *de, *d;
837 struct hpfs_dirent *up_de;
838 struct hpfs_dirent *end_up_de;
840 struct dnode *up_dnode;
841 struct quad_buffer_head qbh0;
846 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
849 /* Going to the next dirent */
850 if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
851 if (!(++*posp & 077)) {
852 hpfs_error(inode->i_sb, "map_pos_dirent: pos crossed dnode boundary; pos = %08x", *posp);
855 /* We're going down the tree */
857 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
864 if (dnode->root_dnode) goto bail;
866 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0)))
869 end_up_de = dnode_end_de(up_dnode);
871 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
872 up_de = de_next_de(up_de)) {
873 if (!(++c & 077)) hpfs_error(inode->i_sb,
874 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up);
875 if (up_de->down && de_down_pointer(up_de) == dno) {
876 *posp = ((loff_t) dnode->up << 4) + c;
882 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
891 /* Find a dirent in tree */
893 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, char *name, unsigned len,
894 dnode_secno *dd, struct quad_buffer_head *qbh)
897 struct hpfs_dirent *de;
898 struct hpfs_dirent *de_end;
901 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
903 if (hpfs_sb(inode->i_sb)->sb_chk)
904 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
905 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
907 de_end = dnode_end_de(dnode);
908 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
909 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
916 dno = de_down_pointer(de);
928 * Remove empty directory. In normal cases it is only one dnode with two
929 * entries, but we must handle also such obscure cases when it's a tree
933 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
935 struct quad_buffer_head qbh;
937 struct hpfs_dirent *de;
938 dnode_secno d1, d2, rdno = dno;
940 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
941 de = dnode_first_de(dnode);
943 if (de->down) d1 = de_down_pointer(de);
946 hpfs_free_dnode(s, dno);
950 if (!de->first) goto error;
951 d1 = de->down ? de_down_pointer(de) : 0;
953 if (!de->last) goto error;
954 d2 = de->down ? de_down_pointer(de) : 0;
956 hpfs_free_dnode(s, dno);
959 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
960 de = dnode_first_de(dnode);
961 if (!de->last) goto error;
962 d1 = de->down ? de_down_pointer(de) : 0;
964 hpfs_free_dnode(s, dno);
972 hpfs_free_dnode(s, dno);
973 hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
977 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
978 * a help for searching.
981 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
982 struct fnode *f, struct quad_buffer_head *qbh)
986 int name1len, name2len;
988 dnode_secno dno, downd;
990 struct buffer_head *bh;
991 struct hpfs_dirent *de, *de_end;
996 if (!(name2 = kmalloc(256, GFP_NOFS))) {
997 printk("HPFS: out of memory, can't map dirent\n");
1001 memcpy(name2, name1, name1len = name2len = f->len);
1003 memcpy(name2, name1, 15);
1004 memset(name2 + 15, 0xff, 256 - 15);
1005 /*name2[15] = 0xff;*/
1006 name1len = 15; name2len = 256;
1008 if (!(upf = hpfs_map_fnode(s, f->up, &bh))) {
1012 if (!upf->dirflag) {
1014 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up);
1018 dno = upf->u.external[0].disk_secno;
1023 if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1027 de_end = dnode_end_de(d);
1028 de = dnode_first_de(d);
1030 while (de < de_end) {
1031 if (de->down) if (de_down_pointer(de) == downd) goto f;
1032 de = de_next_de(de);
1034 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1040 if (de->fnode == fno) {
1044 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1045 if (c < 0 && de->down) {
1046 dno = de_down_pointer(de);
1048 if (hpfs_sb(s)->sb_chk)
1049 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1056 if (de->fnode == fno) {
1060 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1061 if (c < 0 && !de->last) goto not_found;
1062 if ((de = de_next_de(de)) < de_end) goto next_de;
1063 if (d->root_dnode) goto not_found;
1067 if (hpfs_sb(s)->sb_chk)
1068 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1075 hpfs_error(s, "dirent for fnode %08x not found", fno);