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 static 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 static 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 static 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 static void hpfs_delete_de(struct super_block *s, struct dnode *d,
193 struct hpfs_dirent *de)
196 hpfs_error(s, "attempt to delete last dirent in dnode %08x", d->self);
199 d->first_free -= de->length;
200 memmove(de, de_next_de(de), d->first_free + (char *)d - (char *)de);
203 static void fix_up_ptrs(struct super_block *s, struct dnode *d)
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))
210 struct quad_buffer_head qbh;
212 if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
213 if (dd->up != dno || dd->root_dnode) {
216 hpfs_mark_4buffers_dirty(&qbh);
223 /* Add an entry to dnode and do dnode splitting if required */
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)
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;
237 struct buffer_head *bh;
240 if (!(nname = kmalloc(256, GFP_NOFS))) {
241 printk("HPFS: out of memory, can't add to dnode\n");
245 if (namelen >= 256) {
246 hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen);
251 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
257 if (hpfs_sb(i->i_sb)->sb_chk)
258 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
264 if (d->first_free + de_size(namelen, down_ptr) <= 2048) {
266 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_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);
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
283 printk("HPFS: out of memory for dnode splitting\n");
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");
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);
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);
311 set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
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);
322 hpfs_mark_4buffers_dirty(&qbh1);
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");
338 if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) {
339 hpfs_free_dnode(i->i_sb, rdno);
347 fnode->u.external[0].disk_secno = rdno;
348 mark_buffer_dirty(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);
354 hpfs_mark_4buffers_dirty(&qbh1);
357 set_last_pointer(i->i_sb, rd, dno);
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.
371 int hpfs_add_dirent(struct inode *i, unsigned char *name, unsigned namelen,
372 struct hpfs_dirent *new_de, int cdepth)
374 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
376 struct hpfs_dirent *de, *de_end;
377 struct quad_buffer_head qbh;
381 dno = hpfs_inode->i_dno;
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))) {
394 dno = de_down_pointer(de);
402 if (!cdepth) hpfs_lock_creation(i->i_sb);
403 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
408 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
410 if (!cdepth) hpfs_unlock_creation(i->i_sb);
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)
419 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
421 dnode_secno dno, ddno;
422 dnode_secno chk_up = to;
424 struct quad_buffer_head qbh;
425 struct hpfs_dirent *de, *nde;
431 if (hpfs_sb(i->i_sb)->sb_chk)
432 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
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);
444 if (!(de = dnode_last_de(dnode))) {
445 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
449 if (!de->down) break;
450 dno = de_down_pointer(de);
453 while (!(de = dnode_pre_last_de(dnode))) {
454 dnode_secno up = dnode->up;
456 hpfs_free_dnode(i->i_sb, dno);
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);
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);
473 dnode->first_free -= 4;
476 hpfs_mark_4buffers_dirty(&qbh);
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");
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);
493 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
500 * Check if a dnode is empty and delete it from the tree
501 * (chkdsk doesn't like empty dnodes)
504 static void delete_empty_dnode(struct inode *i, dnode_secno dno)
506 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
507 struct quad_buffer_head qbh;
509 dnode_secno down, up, ndown;
511 struct hpfs_dirent *de;
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;
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);
528 hpfs_free_dnode(i->i_sb, dno);
533 struct buffer_head *bh;
535 struct quad_buffer_head qbh1;
536 if (hpfs_sb(i->i_sb)->sb_chk)
537 if (up != i->i_ino) {
539 "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
540 dno, up, (unsigned long)i->i_ino);
543 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
546 hpfs_mark_4buffers_dirty(&qbh1);
549 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
550 fnode->u.external[0].disk_secno = down;
551 mark_buffer_dirty(bh);
554 hpfs_inode->i_dno = down;
555 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
558 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
560 de_end = dnode_end_de(dnode);
561 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
562 if (de->down) if (de_down_pointer(de) == dno) goto fnd;
563 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
566 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
570 dnode->first_free -= 4;
571 memmove(de_next_de(de), (char *)de_next_de(de) + 4,
572 (char *)dnode + dnode->first_free - (char *)de_next_de(de));
575 struct quad_buffer_head qbh1;
576 *(dnode_secno *) ((void *) de + de->length - 4) = down;
577 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
579 hpfs_mark_4buffers_dirty(&qbh1);
584 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, dnode->first_free);
589 struct hpfs_dirent *de_next = de_next_de(de);
590 struct hpfs_dirent *de_cp;
592 struct quad_buffer_head qbh1;
593 if (!de_next->down) goto endm;
594 ndown = de_down_pointer(de_next);
595 if (!(de_cp = kmalloc(de->length, GFP_NOFS))) {
596 printk("HPFS: out of memory for dtree balancing\n");
599 memcpy(de_cp, de, de->length);
600 hpfs_delete_de(i->i_sb, dnode, de);
601 hpfs_mark_4buffers_dirty(&qbh);
603 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
604 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
605 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
607 hpfs_mark_4buffers_dirty(&qbh1);
610 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
611 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
616 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
617 struct hpfs_dirent *de_cp;
619 struct quad_buffer_head qbh1;
622 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
623 hpfs_mark_4buffers_dirty(&qbh);
628 if (!de_prev->down) goto endm;
629 ndown = de_down_pointer(de_prev);
630 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
631 struct hpfs_dirent *del = dnode_last_de(d1);
632 dlp = del->down ? de_down_pointer(del) : 0;
634 if (d1->first_free > 2044) {
635 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
636 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
637 printk("HPFS: warning: terminating balancing operation\n");
642 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
643 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
644 printk("HPFS: warning: goin'on\n");
655 *(dnode_secno *) ((void *) del + del->length - 4) = down;
657 if (!(de_cp = kmalloc(de_prev->length, GFP_NOFS))) {
658 printk("HPFS: out of memory for dtree balancing\n");
662 hpfs_mark_4buffers_dirty(&qbh1);
664 memcpy(de_cp, de_prev, de_prev->length);
665 hpfs_delete_de(i->i_sb, dnode, de_prev);
666 if (!de_prev->down) {
667 de_prev->length += 4;
669 dnode->first_free += 4;
671 *(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = ndown;
672 hpfs_mark_4buffers_dirty(&qbh);
674 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
675 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
676 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
678 hpfs_mark_4buffers_dirty(&qbh1);
681 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
687 hpfs_mark_4buffers_dirty(&qbh);
693 /* Delete dirent from directory */
695 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
696 struct quad_buffer_head *qbh, int depth)
698 struct dnode *dnode = qbh->data;
699 dnode_secno down = 0;
702 if (de->first || de->last) {
703 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
707 if (de->down) down = de_down_pointer(de);
708 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
710 hpfs_lock_creation(i->i_sb);
711 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
713 hpfs_unlock_creation(i->i_sb);
718 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
719 hpfs_delete_de(i->i_sb, dnode, de);
720 hpfs_mark_4buffers_dirty(qbh);
723 dnode_secno a = move_to_top(i, down, dno);
724 for_all_poss(i, hpfs_pos_subst, 5, t);
725 if (a) delete_empty_dnode(i, a);
726 if (lock) hpfs_unlock_creation(i->i_sb);
729 delete_empty_dnode(i, dno);
730 if (lock) hpfs_unlock_creation(i->i_sb);
734 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
735 int *n_subdirs, int *n_items)
738 struct quad_buffer_head qbh;
739 struct hpfs_dirent *de;
740 dnode_secno ptr, odno = 0;
744 if (n_dnodes) (*n_dnodes)++;
745 if (hpfs_sb(s)->sb_chk)
746 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
749 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
750 if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && dnode->up != odno)
751 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up);
752 de = dnode_first_de(dnode);
754 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
757 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
766 dno = de_down_pointer(de);
771 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
772 if (!de->first && !de->last && n_items) (*n_items)++;
773 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
776 if (dnode->root_dnode) {
781 if (hpfs_sb(s)->sb_chk)
782 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
787 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
788 struct quad_buffer_head *qbh, struct dnode **dn)
791 struct hpfs_dirent *de, *de_end;
793 dnode = hpfs_map_dnode(s, dno, qbh);
794 if (!dnode) return NULL;
796 de = dnode_first_de(dnode);
797 de_end = dnode_end_de(dnode);
798 for (i = 1; de < de_end; i++, de = de_next_de(de)) {
805 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
809 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
811 struct quad_buffer_head qbh;
814 struct hpfs_dirent *de;
818 if (hpfs_sb(s)->sb_chk)
819 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
821 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
822 if (hpfs_sb(s)->sb_chk)
823 if (up && ((struct dnode *)qbh.data)->up != up)
824 hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, ((struct dnode *)qbh.data)->up);
830 d = de_down_pointer(de);
835 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
836 struct quad_buffer_head *qbh)
841 struct hpfs_dirent *de, *d;
842 struct hpfs_dirent *up_de;
843 struct hpfs_dirent *end_up_de;
845 struct dnode *up_dnode;
846 struct quad_buffer_head qbh0;
851 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
854 /* Going to the next dirent */
855 if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
856 if (!(++*posp & 077)) {
857 hpfs_error(inode->i_sb,
858 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
859 (unsigned long long)*posp);
862 /* We're going down the tree */
864 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
871 if (dnode->root_dnode) goto bail;
873 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0)))
876 end_up_de = dnode_end_de(up_dnode);
878 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
879 up_de = de_next_de(up_de)) {
880 if (!(++c & 077)) hpfs_error(inode->i_sb,
881 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up);
882 if (up_de->down && de_down_pointer(up_de) == dno) {
883 *posp = ((loff_t) dnode->up << 4) + c;
889 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
898 /* Find a dirent in tree */
900 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, char *name, unsigned len,
901 dnode_secno *dd, struct quad_buffer_head *qbh)
904 struct hpfs_dirent *de;
905 struct hpfs_dirent *de_end;
908 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
910 if (hpfs_sb(inode->i_sb)->sb_chk)
911 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
912 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
914 de_end = dnode_end_de(dnode);
915 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
916 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
923 dno = de_down_pointer(de);
935 * Remove empty directory. In normal cases it is only one dnode with two
936 * entries, but we must handle also such obscure cases when it's a tree
940 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
942 struct quad_buffer_head qbh;
944 struct hpfs_dirent *de;
945 dnode_secno d1, d2, rdno = dno;
947 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
948 de = dnode_first_de(dnode);
950 if (de->down) d1 = de_down_pointer(de);
953 hpfs_free_dnode(s, dno);
957 if (!de->first) goto error;
958 d1 = de->down ? de_down_pointer(de) : 0;
960 if (!de->last) goto error;
961 d2 = de->down ? de_down_pointer(de) : 0;
963 hpfs_free_dnode(s, dno);
966 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
967 de = dnode_first_de(dnode);
968 if (!de->last) goto error;
969 d1 = de->down ? de_down_pointer(de) : 0;
971 hpfs_free_dnode(s, dno);
979 hpfs_free_dnode(s, dno);
980 hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
984 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
985 * a help for searching.
988 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
989 struct fnode *f, struct quad_buffer_head *qbh)
993 int name1len, name2len;
995 dnode_secno dno, downd;
997 struct buffer_head *bh;
998 struct hpfs_dirent *de, *de_end;
1003 if (!(name2 = kmalloc(256, GFP_NOFS))) {
1004 printk("HPFS: out of memory, can't map dirent\n");
1008 memcpy(name2, name1, name1len = name2len = f->len);
1010 memcpy(name2, name1, 15);
1011 memset(name2 + 15, 0xff, 256 - 15);
1012 /*name2[15] = 0xff;*/
1013 name1len = 15; name2len = 256;
1015 if (!(upf = hpfs_map_fnode(s, f->up, &bh))) {
1019 if (!upf->dirflag) {
1021 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up);
1025 dno = upf->u.external[0].disk_secno;
1030 if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1034 de_end = dnode_end_de(d);
1035 de = dnode_first_de(d);
1037 while (de < de_end) {
1038 if (de->down) if (de_down_pointer(de) == downd) goto f;
1039 de = de_next_de(de);
1041 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1047 if (de->fnode == fno) {
1051 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1052 if (c < 0 && de->down) {
1053 dno = de_down_pointer(de);
1055 if (hpfs_sb(s)->sb_chk)
1056 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1063 if (de->fnode == fno) {
1067 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1068 if (c < 0 && !de->last) goto not_found;
1069 if ((de = de_next_de(de)) < de_end) goto next_de;
1070 if (d->root_dnode) goto not_found;
1074 if (hpfs_sb(s)->sb_chk)
1075 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1082 hpfs_error(s, "dirent for fnode %08x not found", fno);