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) le32_to_cpu(d->self) << 4) | (loff_t)i;
20 pr_info("%s(): not_found\n", __func__);
21 return ((loff_t)le32_to_cpu(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 pr_err("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 /*pr_warn("position pointer %p->%08x not found\n",
71 static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
74 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
77 if (!hpfs_inode->i_rddir_off) return;
78 for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
82 static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
87 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
89 if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
92 static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
94 if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
95 int n = (*p & 0x3f) + c;
97 pr_err("%s(): %08x + %d\n",
98 __func__, (int)*p, (int)c >> 8);
100 *p = (*p & ~0x3f) | n;
104 static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
106 if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
107 int n = (*p & 0x3f) - c;
109 pr_err("%s(): %08x - %d\n",
110 __func__, (int)*p, (int)c >> 8);
112 *p = (*p & ~0x3f) | n;
116 static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
118 struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
119 de_end = dnode_end_de(d);
120 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
121 deee = dee; dee = de;
126 static struct hpfs_dirent *dnode_last_de(struct dnode *d)
128 struct hpfs_dirent *de, *de_end, *dee = NULL;
129 de_end = dnode_end_de(d);
130 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
136 static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
138 struct hpfs_dirent *de;
139 if (!(de = dnode_last_de(d))) {
140 hpfs_error(s, "set_last_pointer: empty dnode %08x", le32_to_cpu(d->self));
143 if (hpfs_sb(s)->sb_chk) {
145 hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
146 le32_to_cpu(d->self), de_down_pointer(de));
149 if (le16_to_cpu(de->length) != 32) {
150 hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", le32_to_cpu(d->self));
155 le32_add_cpu(&d->first_free, 4);
156 if (le32_to_cpu(d->first_free) > 2048) {
157 hpfs_error(s, "set_last_pointer: too long dnode %08x", le32_to_cpu(d->self));
158 le32_add_cpu(&d->first_free, -4);
161 de->length = cpu_to_le16(36);
163 *(__le32 *)((char *)de + 32) = cpu_to_le32(ptr);
167 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
169 struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d,
170 const unsigned char *name,
171 unsigned namelen, secno down_ptr)
173 struct hpfs_dirent *de;
174 struct hpfs_dirent *de_end = dnode_end_de(d);
175 unsigned d_size = de_size(namelen, down_ptr);
176 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
177 int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
179 hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, le32_to_cpu(d->self));
184 memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
185 memset(de, 0, d_size);
187 *(__le32 *)((char *)de + d_size - 4) = cpu_to_le32(down_ptr);
190 de->length = cpu_to_le16(d_size);
191 de->not_8x3 = hpfs_is_name_long(name, namelen);
192 de->namelen = namelen;
193 memcpy(de->name, name, namelen);
194 le32_add_cpu(&d->first_free, d_size);
198 /* Delete dirent and don't care about its subtree */
200 static void hpfs_delete_de(struct super_block *s, struct dnode *d,
201 struct hpfs_dirent *de)
204 hpfs_error(s, "attempt to delete last dirent in dnode %08x", le32_to_cpu(d->self));
207 d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) - le16_to_cpu(de->length));
208 memmove(de, de_next_de(de), le32_to_cpu(d->first_free) + (char *)d - (char *)de);
211 static void fix_up_ptrs(struct super_block *s, struct dnode *d)
213 struct hpfs_dirent *de;
214 struct hpfs_dirent *de_end = dnode_end_de(d);
215 dnode_secno dno = le32_to_cpu(d->self);
216 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
218 struct quad_buffer_head qbh;
220 if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
221 if (le32_to_cpu(dd->up) != dno || dd->root_dnode) {
222 dd->up = cpu_to_le32(dno);
224 hpfs_mark_4buffers_dirty(&qbh);
231 /* Add an entry to dnode and do dnode splitting if required */
233 static int hpfs_add_to_dnode(struct inode *i, dnode_secno dno,
234 const unsigned char *name, unsigned namelen,
235 struct hpfs_dirent *new_de, dnode_secno down_ptr)
237 struct quad_buffer_head qbh, qbh1, qbh2;
238 struct dnode *d, *ad, *rd, *nd = NULL;
239 dnode_secno adno, rdno;
240 struct hpfs_dirent *de;
241 struct hpfs_dirent nde;
242 unsigned char *nname;
245 struct buffer_head *bh;
248 if (!(nname = kmalloc(256, GFP_NOFS))) {
249 pr_err("out of memory, can't add to dnode\n");
253 if (namelen >= 256) {
254 hpfs_error(i->i_sb, "%s(): namelen == %d", __func__, namelen);
259 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
265 if (hpfs_sb(i->i_sb)->sb_chk)
266 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
272 if (le32_to_cpu(d->first_free) + de_size(namelen, down_ptr) <= 2048) {
274 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
276 for_all_poss(i, hpfs_pos_ins, t, 1);
277 for_all_poss(i, hpfs_pos_subst, 4, t);
278 for_all_poss(i, hpfs_pos_subst, 5, t + 1);
279 hpfs_mark_4buffers_dirty(&qbh);
285 if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
286 /* 0x924 is a max size of dnode after adding a dirent with
287 max name length. We alloc this only once. There must
288 not be any error while splitting dnodes, otherwise the
289 whole directory, not only file we're adding, would
291 pr_err("out of memory for dnode splitting\n");
296 memcpy(nd, d, le32_to_cpu(d->first_free));
297 copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
298 for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
299 h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
300 if (!(ad = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &adno, &qbh1))) {
301 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
310 for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
311 copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
312 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
315 copy_de(new_de = &nde, de);
316 memcpy(nname, de->name, de->namelen);
318 namelen = de->namelen;
319 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
321 set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
323 memmove((char *)nd + 20, de, le32_to_cpu(nd->first_free) + (char *)nd - (char *)de);
324 le32_add_cpu(&nd->first_free, -((char *)de - (char *)nd - 20));
325 memcpy(d, nd, le32_to_cpu(nd->first_free));
326 for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
327 fix_up_ptrs(i->i_sb, ad);
328 if (!d->root_dnode) {
330 dno = le32_to_cpu(ad->up);
331 hpfs_mark_4buffers_dirty(&qbh);
333 hpfs_mark_4buffers_dirty(&qbh1);
337 if (!(rd = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &rdno, &qbh2))) {
338 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
349 if (!(fnode = hpfs_map_fnode(i->i_sb, le32_to_cpu(d->up), &bh))) {
350 hpfs_free_dnode(i->i_sb, rdno);
358 fnode->u.external[0].disk_secno = cpu_to_le32(rdno);
359 mark_buffer_dirty(bh);
361 hpfs_i(i)->i_dno = rdno;
362 d->up = ad->up = cpu_to_le32(rdno);
363 d->root_dnode = ad->root_dnode = 0;
364 hpfs_mark_4buffers_dirty(&qbh);
366 hpfs_mark_4buffers_dirty(&qbh1);
369 set_last_pointer(i->i_sb, rd, dno);
376 * Add an entry to directory btree.
377 * I hate such crazy directory structure.
378 * It's easy to read but terrible to write.
379 * I wrote this directory code 4 times.
380 * I hope, now it's finally bug-free.
383 int hpfs_add_dirent(struct inode *i,
384 const unsigned char *name, unsigned namelen,
385 struct hpfs_dirent *new_de)
387 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
389 struct hpfs_dirent *de, *de_end;
390 struct quad_buffer_head qbh;
394 dno = hpfs_inode->i_dno;
396 if (hpfs_sb(i->i_sb)->sb_chk)
397 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
398 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
399 de_end = dnode_end_de(d);
400 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
401 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
407 dno = de_down_pointer(de);
415 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
420 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
426 * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
427 * Return the dnode we moved from (to be checked later if it's empty)
430 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
432 dnode_secno dno, ddno;
433 dnode_secno chk_up = to;
435 struct quad_buffer_head qbh;
436 struct hpfs_dirent *de, *nde;
442 if (hpfs_sb(i->i_sb)->sb_chk)
443 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
445 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
446 if (hpfs_sb(i->i_sb)->sb_chk) {
447 if (le32_to_cpu(dnode->up) != chk_up) {
448 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
449 dno, chk_up, le32_to_cpu(dnode->up));
455 if (!(de = dnode_last_de(dnode))) {
456 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
460 if (!de->down) break;
461 dno = de_down_pointer(de);
464 while (!(de = dnode_pre_last_de(dnode))) {
465 dnode_secno up = le32_to_cpu(dnode->up);
467 hpfs_free_dnode(i->i_sb, dno);
470 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
471 if (up == to) return to;
472 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
473 if (dnode->root_dnode) {
474 hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
478 de = dnode_last_de(dnode);
479 if (!de || !de->down) {
480 hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
484 le32_add_cpu(&dnode->first_free, -4);
485 le16_add_cpu(&de->length, -4);
487 hpfs_mark_4buffers_dirty(&qbh);
490 t = get_pos(dnode, de);
491 for_all_poss(i, hpfs_pos_subst, t, 4);
492 for_all_poss(i, hpfs_pos_subst, t + 1, 5);
493 if (!(nde = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
494 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
498 memcpy(nde, de, le16_to_cpu(de->length));
499 ddno = de->down ? de_down_pointer(de) : 0;
500 hpfs_delete_de(i->i_sb, dnode, de);
501 set_last_pointer(i->i_sb, dnode, ddno);
502 hpfs_mark_4buffers_dirty(&qbh);
504 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
511 * Check if a dnode is empty and delete it from the tree
512 * (chkdsk doesn't like empty dnodes)
515 static void delete_empty_dnode(struct inode *i, dnode_secno dno)
517 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
518 struct quad_buffer_head qbh;
520 dnode_secno down, up, ndown;
522 struct hpfs_dirent *de;
525 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
526 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
527 if (le32_to_cpu(dnode->first_free) > 56) goto end;
528 if (le32_to_cpu(dnode->first_free) == 52 || le32_to_cpu(dnode->first_free) == 56) {
529 struct hpfs_dirent *de_end;
530 int root = dnode->root_dnode;
531 up = le32_to_cpu(dnode->up);
532 de = dnode_first_de(dnode);
533 down = de->down ? de_down_pointer(de) : 0;
534 if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
535 hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
539 hpfs_free_dnode(i->i_sb, dno);
544 struct buffer_head *bh;
546 struct quad_buffer_head qbh1;
547 if (hpfs_sb(i->i_sb)->sb_chk)
548 if (up != i->i_ino) {
550 "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
551 dno, up, (unsigned long)i->i_ino);
554 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
555 d1->up = cpu_to_le32(up);
557 hpfs_mark_4buffers_dirty(&qbh1);
560 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
561 fnode->u.external[0].disk_secno = cpu_to_le32(down);
562 mark_buffer_dirty(bh);
565 hpfs_inode->i_dno = down;
566 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
569 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
571 de_end = dnode_end_de(dnode);
572 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
573 if (de->down) if (de_down_pointer(de) == dno) goto fnd;
574 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
577 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
580 le16_add_cpu(&de->length, -4);
581 le32_add_cpu(&dnode->first_free, -4);
582 memmove(de_next_de(de), (char *)de_next_de(de) + 4,
583 (char *)dnode + le32_to_cpu(dnode->first_free) - (char *)de_next_de(de));
586 struct quad_buffer_head qbh1;
587 *(dnode_secno *) ((void *) de + le16_to_cpu(de->length) - 4) = down;
588 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
589 d1->up = cpu_to_le32(up);
590 hpfs_mark_4buffers_dirty(&qbh1);
595 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, le32_to_cpu(dnode->first_free));
600 struct hpfs_dirent *de_next = de_next_de(de);
601 struct hpfs_dirent *de_cp;
603 struct quad_buffer_head qbh1;
604 if (!de_next->down) goto endm;
605 ndown = de_down_pointer(de_next);
606 if (!(de_cp = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
607 pr_err("out of memory for dtree balancing\n");
610 memcpy(de_cp, de, le16_to_cpu(de->length));
611 hpfs_delete_de(i->i_sb, dnode, de);
612 hpfs_mark_4buffers_dirty(&qbh);
614 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
615 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
616 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
617 d1->up = cpu_to_le32(ndown);
618 hpfs_mark_4buffers_dirty(&qbh1);
621 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
622 /*pr_info("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n",
623 up, ndown, down, dno);*/
628 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
629 struct hpfs_dirent *de_cp;
631 struct quad_buffer_head qbh1;
634 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
635 hpfs_mark_4buffers_dirty(&qbh);
640 if (!de_prev->down) goto endm;
641 ndown = de_down_pointer(de_prev);
642 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
643 struct hpfs_dirent *del = dnode_last_de(d1);
644 dlp = del->down ? de_down_pointer(del) : 0;
646 if (le32_to_cpu(d1->first_free) > 2044) {
647 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
648 pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
649 pr_err("terminating balancing operation\n");
654 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
655 pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
658 le16_add_cpu(&del->length, 4);
660 le32_add_cpu(&d1->first_free, 4);
663 le16_add_cpu(&del->length, -4);
665 le32_add_cpu(&d1->first_free, -4);
667 *(__le32 *) ((void *) del + le16_to_cpu(del->length) - 4) = cpu_to_le32(down);
669 if (!(de_cp = kmalloc(le16_to_cpu(de_prev->length), GFP_NOFS))) {
670 pr_err("out of memory for dtree balancing\n");
674 hpfs_mark_4buffers_dirty(&qbh1);
676 memcpy(de_cp, de_prev, le16_to_cpu(de_prev->length));
677 hpfs_delete_de(i->i_sb, dnode, de_prev);
678 if (!de_prev->down) {
679 le16_add_cpu(&de_prev->length, 4);
681 le32_add_cpu(&dnode->first_free, 4);
683 *(__le32 *) ((void *) de_prev + le16_to_cpu(de_prev->length) - 4) = cpu_to_le32(ndown);
684 hpfs_mark_4buffers_dirty(&qbh);
686 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
687 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
688 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
689 d1->up = cpu_to_le32(ndown);
690 hpfs_mark_4buffers_dirty(&qbh1);
693 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
699 hpfs_mark_4buffers_dirty(&qbh);
705 /* Delete dirent from directory */
707 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
708 struct quad_buffer_head *qbh, int depth)
710 struct dnode *dnode = qbh->data;
711 dnode_secno down = 0;
713 if (de->first || de->last) {
714 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
718 if (de->down) down = de_down_pointer(de);
719 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
720 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
726 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
727 hpfs_delete_de(i->i_sb, dnode, de);
728 hpfs_mark_4buffers_dirty(qbh);
731 dnode_secno a = move_to_top(i, down, dno);
732 for_all_poss(i, hpfs_pos_subst, 5, t);
733 if (a) delete_empty_dnode(i, a);
736 delete_empty_dnode(i, dno);
740 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
741 int *n_subdirs, int *n_items)
744 struct quad_buffer_head qbh;
745 struct hpfs_dirent *de;
746 dnode_secno ptr, odno = 0;
750 if (n_dnodes) (*n_dnodes)++;
751 if (hpfs_sb(s)->sb_chk)
752 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
755 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
756 if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && le32_to_cpu(dnode->up) != odno)
757 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, le32_to_cpu(dnode->up));
758 de = dnode_first_de(dnode);
760 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
763 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
772 dno = de_down_pointer(de);
777 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
778 if (!de->first && !de->last && n_items) (*n_items)++;
779 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
781 dno = le32_to_cpu(dnode->up);
782 if (dnode->root_dnode) {
787 if (hpfs_sb(s)->sb_chk)
788 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
793 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
794 struct quad_buffer_head *qbh, struct dnode **dn)
797 struct hpfs_dirent *de, *de_end;
799 dnode = hpfs_map_dnode(s, dno, qbh);
800 if (!dnode) return NULL;
802 de = dnode_first_de(dnode);
803 de_end = dnode_end_de(dnode);
804 for (i = 1; de < de_end; i++, de = de_next_de(de)) {
811 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
815 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
817 struct quad_buffer_head qbh;
820 struct hpfs_dirent *de;
824 if (hpfs_sb(s)->sb_chk)
825 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
827 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
828 if (hpfs_sb(s)->sb_chk)
829 if (up && le32_to_cpu(((struct dnode *)qbh.data)->up) != up)
830 hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, le32_to_cpu(((struct dnode *)qbh.data)->up));
836 d = de_down_pointer(de);
841 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
842 struct quad_buffer_head *qbh)
847 struct hpfs_dirent *de, *d;
848 struct hpfs_dirent *up_de;
849 struct hpfs_dirent *end_up_de;
851 struct dnode *up_dnode;
852 struct quad_buffer_head qbh0;
857 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
860 /* Going to the next dirent */
861 if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
862 if (!(++*posp & 077)) {
863 hpfs_error(inode->i_sb,
864 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
865 (unsigned long long)*posp);
868 /* We're going down the tree */
870 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
877 if (dnode->root_dnode) goto bail;
879 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, le32_to_cpu(dnode->up), &qbh0)))
882 end_up_de = dnode_end_de(up_dnode);
884 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
885 up_de = de_next_de(up_de)) {
886 if (!(++c & 077)) hpfs_error(inode->i_sb,
887 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode->up));
888 if (up_de->down && de_down_pointer(up_de) == dno) {
889 *posp = ((loff_t) le32_to_cpu(dnode->up) << 4) + c;
895 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
896 dno, le32_to_cpu(dnode->up));
904 /* Find a dirent in tree */
906 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
907 const unsigned char *name, unsigned len,
908 dnode_secno *dd, struct quad_buffer_head *qbh)
911 struct hpfs_dirent *de;
912 struct hpfs_dirent *de_end;
915 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
917 if (hpfs_sb(inode->i_sb)->sb_chk)
918 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
919 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
921 de_end = dnode_end_de(dnode);
922 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
923 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
930 dno = de_down_pointer(de);
942 * Remove empty directory. In normal cases it is only one dnode with two
943 * entries, but we must handle also such obscure cases when it's a tree
947 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
949 struct quad_buffer_head qbh;
951 struct hpfs_dirent *de;
952 dnode_secno d1, d2, rdno = dno;
954 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
955 de = dnode_first_de(dnode);
957 if (de->down) d1 = de_down_pointer(de);
960 hpfs_free_dnode(s, dno);
964 if (!de->first) goto error;
965 d1 = de->down ? de_down_pointer(de) : 0;
967 if (!de->last) goto error;
968 d2 = de->down ? de_down_pointer(de) : 0;
970 hpfs_free_dnode(s, dno);
973 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
974 de = dnode_first_de(dnode);
975 if (!de->last) goto error;
976 d1 = de->down ? de_down_pointer(de) : 0;
978 hpfs_free_dnode(s, dno);
986 hpfs_free_dnode(s, dno);
987 hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
991 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
992 * a help for searching.
995 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
996 struct fnode *f, struct quad_buffer_head *qbh)
998 unsigned char *name1;
999 unsigned char *name2;
1000 int name1len, name2len;
1002 dnode_secno dno, downd;
1004 struct buffer_head *bh;
1005 struct hpfs_dirent *de, *de_end;
1010 if (!(name2 = kmalloc(256, GFP_NOFS))) {
1011 pr_err("out of memory, can't map dirent\n");
1015 memcpy(name2, name1, name1len = name2len = f->len);
1017 memcpy(name2, name1, 15);
1018 memset(name2 + 15, 0xff, 256 - 15);
1019 /*name2[15] = 0xff;*/
1020 name1len = 15; name2len = 256;
1022 if (!(upf = hpfs_map_fnode(s, le32_to_cpu(f->up), &bh))) {
1026 if (!fnode_is_dir(upf)) {
1028 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, le32_to_cpu(f->up));
1032 dno = le32_to_cpu(upf->u.external[0].disk_secno);
1037 if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1041 de_end = dnode_end_de(d);
1042 de = dnode_first_de(d);
1044 while (de < de_end) {
1045 if (de->down) if (de_down_pointer(de) == downd) goto f;
1046 de = de_next_de(de);
1048 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1054 if (le32_to_cpu(de->fnode) == fno) {
1058 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1059 if (c < 0 && de->down) {
1060 dno = de_down_pointer(de);
1062 if (hpfs_sb(s)->sb_chk)
1063 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1070 if (le32_to_cpu(de->fnode) == fno) {
1074 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1075 if (c < 0 && !de->last) goto not_found;
1076 if ((de = de_next_de(de)) < de_end) goto next_de;
1077 if (d->root_dnode) goto not_found;
1079 dno = le32_to_cpu(d->up);
1081 if (hpfs_sb(s)->sb_chk)
1082 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1089 hpfs_error(s, "dirent for fnode %08x not found", fno);