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
)
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;
32 if (!(ppos
= kmalloc((i
+0x11) * sizeof(loff_t
*), GFP_KERNEL
))) {
33 printk("HPFS: out of memory for position list\n");
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
);
40 inode
->i_hpfs_rddir_off
= ppos
;
42 inode
->i_hpfs_rddir_off
[i
] = pos
;
43 inode
->i_hpfs_rddir_off
[i
+ 1] = NULL
;
46 void hpfs_del_pos(struct inode
*inode
, loff_t
*pos
)
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
;
53 for (j
= i
+ 1; *j
; j
++) ;
56 if (j
- 1 == inode
->i_hpfs_rddir_off
) {
57 kfree(inode
->i_hpfs_rddir_off
);
58 inode
->i_hpfs_rddir_off
= NULL
;
62 /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
66 static void for_all_poss(struct inode
*inode
, void (*f
)(loff_t
*, loff_t
, loff_t
),
70 if (!inode
->i_hpfs_rddir_off
) return;
71 for (i
= inode
->i_hpfs_rddir_off
; *i
; i
++) (*f
)(*i
, p1
, p2
);
75 void hpfs_pos_subst(loff_t
*p
, loff_t f
, loff_t t
)
80 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
82 if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
85 void hpfs_pos_ins(loff_t
*p
, loff_t d
, loff_t c
)
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
;
94 void hpfs_pos_del(loff_t
*p
, loff_t d
, loff_t c
)
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
;
103 static struct hpfs_dirent
*dnode_pre_last_de(struct dnode
*d
)
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
;
113 static struct hpfs_dirent
*dnode_last_de(struct dnode
*d
)
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
)) {
123 static void set_last_pointer(struct super_block
*s
, struct dnode
*d
, dnode_secno ptr
)
125 struct hpfs_dirent
*de
;
126 if (!(de
= dnode_last_de(d
))) {
127 hpfs_error(s
, "set_last_pointer: empty dnode %08x", d
->self
);
132 hpfs_error(s
, "set_last_pointer: dnode %08x has already last pointer %08x",
133 d
->self
, de_down_pointer(de
));
136 if (de
->length
!= 32) {
137 hpfs_error(s
, "set_last_pointer: bad last dirent in dnode %08x", d
->self
);
142 if ((d
->first_free
+= 4) > 2048) {
143 hpfs_error(s
,"set_last_pointer: too long dnode %08x", d
->self
);
149 *(dnode_secno
*)((char *)de
+ 32) = ptr
;
153 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
155 struct hpfs_dirent
*hpfs_add_de(struct super_block
*s
, struct dnode
*d
, unsigned char *name
,
156 unsigned namelen
, secno down_ptr
)
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
);
164 hpfs_error(s
, "name (%c,%d) already exists in dnode %08x", *name
, namelen
, d
->self
);
169 memmove((char *)de
+ d_size
, de
, (char *)de_end
- (char *)de
);
170 memset(de
, 0, d_size
);
172 *(int *)((char *)de
+ d_size
- 4) = down_ptr
;
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
;
184 /* Delete dirent and don't care about it's subtree */
186 void hpfs_delete_de(struct super_block
*s
, struct dnode
*d
, struct hpfs_dirent
*de
)
189 hpfs_error(s
, "attempt to delete last dirent in dnode %08x", d
->self
);
192 d
->first_free
-= de
->length
;
193 memmove(de
, de_next_de(de
), d
->first_free
+ (char *)d
- (char *)de
);
196 static void fix_up_ptrs(struct super_block
*s
, struct dnode
*d
)
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
))
203 struct quad_buffer_head qbh
;
205 if ((dd
= hpfs_map_dnode(s
, de_down_pointer(de
), &qbh
))) {
206 if (dd
->up
!= dno
|| dd
->root_dnode
) {
209 hpfs_mark_4buffers_dirty(&qbh
);
216 /* Add an entry to dnode and do dnode splitting if required */
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
)
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
;
229 struct buffer_head
*bh
;
232 if (!(nname
= kmalloc(256, GFP_KERNEL
))) {
233 printk("HPFS: out of memory, can't add to dnode\n");
237 if (namelen
>= 256) {
238 hpfs_error(i
->i_sb
, "hpfs_add_to_dnode: namelen == %d", namelen
);
243 if (!(d
= hpfs_map_dnode(i
->i_sb
, dno
, &qbh
))) {
249 if (i
->i_sb
->s_hpfs_chk
)
250 if (hpfs_stop_cycles(i
->i_sb
, dno
, &c1
, &c2
, "hpfs_add_to_dnode")) {
256 if (d
->first_free
+ de_size(namelen
, down_ptr
) <= 2048) {
258 copy_de(de
=hpfs_add_de(i
->i_sb
, d
, name
, namelen
, down_ptr
), new_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
);
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
275 printk("HPFS: out of memory for dnode splitting\n");
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");
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
);
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);
303 set_last_pointer(i
->i_sb
, ad
, de
->down
? de_down_pointer(de
) : 0);
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
);
314 hpfs_mark_4buffers_dirty(&qbh1
);
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");
330 if (!(fnode
= hpfs_map_fnode(i
->i_sb
, d
->up
, &bh
))) {
331 hpfs_free_dnode(i
->i_sb
, rdno
);
339 fnode
->u
.external
[0].disk_secno
= rdno
;
340 mark_buffer_dirty(bh
, 1);
342 d
->up
= ad
->up
= i
->i_hpfs_dno
= rdno
;
343 d
->root_dnode
= ad
->root_dnode
= 0;
344 hpfs_mark_4buffers_dirty(&qbh
);
346 hpfs_mark_4buffers_dirty(&qbh1
);
349 set_last_pointer(i
->i_sb
, rd
, dno
);
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.
363 int hpfs_add_dirent(struct inode
*i
, unsigned char *name
, unsigned namelen
,
364 struct hpfs_dirent
*new_de
, int cdepth
)
367 struct hpfs_dirent
*de
, *de_end
;
368 struct quad_buffer_head qbh
;
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
))) {
385 dno
= de_down_pointer(de
);
393 if (!cdepth
) hpfs_lock_creation(i
->i_sb
);
394 if (hpfs_check_free_dnodes(i
->i_sb
, FREE_DNODES_ADD
)) {
398 i
->i_version
= ++event
;
399 c
= hpfs_add_to_dnode(i
, dno
, name
, namelen
, new_de
, 0);
401 if (!cdepth
) hpfs_unlock_creation(i
->i_sb
);
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)
410 static secno
move_to_top(struct inode
*i
, dnode_secno from
, dnode_secno to
)
412 dnode_secno dno
, ddno
;
413 dnode_secno chk_up
= to
;
415 struct quad_buffer_head qbh
;
416 struct hpfs_dirent
*de
, *nde
;
422 if (i
->i_sb
->s_hpfs_chk
)
423 if (hpfs_stop_cycles(i
->i_sb
, dno
, &c1
, &c2
, "move_to_top"))
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
);
435 if (!(de
= dnode_last_de(dnode
))) {
436 hpfs_error(i
->i_sb
, "move_to_top: dnode %08x has no last de", dno
);
440 if (!de
->down
) break;
441 dno
= de_down_pointer(de
);
444 while (!(de
= dnode_pre_last_de(dnode
))) {
445 dnode_secno up
= dnode
->up
;
447 hpfs_free_dnode(i
->i_sb
, dno
);
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
);
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
);
464 dnode
->first_free
-= 4;
467 hpfs_mark_4buffers_dirty(&qbh
);
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");
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
);
484 a
= hpfs_add_to_dnode(i
, to
, nde
->name
, nde
->namelen
, nde
, from
);
491 * Check if a dnode is empty and delete it from the tree
492 * (chkdsk doesn't like empty dnodes)
495 static void delete_empty_dnode(struct inode
*i
, dnode_secno dno
)
497 struct quad_buffer_head qbh
;
499 dnode_secno down
, up
, ndown
;
501 struct hpfs_dirent
*de
;
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
;
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
);
518 hpfs_free_dnode(i
->i_sb
, dno
);
523 struct buffer_head
*bh
;
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
);
530 if ((d1
= hpfs_map_dnode(i
->i_sb
, down
, &qbh1
))) {
533 hpfs_mark_4buffers_dirty(&qbh1
);
536 if ((fnode
= hpfs_map_fnode(i
->i_sb
, up
, &bh
))) {
537 fnode
->u
.external
[0].disk_secno
= down
;
538 mark_buffer_dirty(bh
, 1);
541 i
->i_hpfs_dno
= down
;
542 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | 1, (loff_t
) 12);
545 if (!(dnode
= hpfs_map_dnode(i
->i_sb
, up
, &qbh
))) return;
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
);
553 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | 1, ((loff_t
)up
<< 4) | p
);
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
));
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
))) {
566 hpfs_mark_4buffers_dirty(&qbh1
);
571 hpfs_error(i
->i_sb
, "delete_empty_dnode: dnode %08x, first_free == %03x", dno
, dnode
->first_free
);
576 struct hpfs_dirent
*de_next
= de_next_de(de
);
577 struct hpfs_dirent
*de_cp
;
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");
586 memcpy(de_cp
, de
, de
->length
);
587 hpfs_delete_de(i
->i_sb
, dnode
, de
);
588 hpfs_mark_4buffers_dirty(&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
))) {
594 hpfs_mark_4buffers_dirty(&qbh1
);
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);*/
603 struct hpfs_dirent
*de_prev
= dnode_pre_last_de(dnode
);
604 struct hpfs_dirent
*de_cp
;
606 struct quad_buffer_head qbh1
;
609 hpfs_error(i
->i_sb
, "delete_empty_dnode: empty dnode %08x", up
);
610 hpfs_mark_4buffers_dirty(&qbh
);
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;
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");
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");
642 *(dnode_secno
*) ((void *) del
+ del
->length
- 4) = down
;
644 if (!(de_cp
= kmalloc(de_prev
->length
, GFP_KERNEL
))) {
645 printk("HPFS: out of memory for dtree balancing\n");
649 hpfs_mark_4buffers_dirty(&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;
656 dnode
->first_free
+= 4;
658 *(dnode_secno
*) ((void *) de_prev
+ de_prev
->length
- 4) = ndown
;
659 hpfs_mark_4buffers_dirty(&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
))) {
665 hpfs_mark_4buffers_dirty(&qbh1
);
668 hpfs_add_to_dnode(i
, ndown
, de_cp
->name
, de_cp
->namelen
, de_cp
, dlp
);
674 hpfs_mark_4buffers_dirty(&qbh
);
680 /* Delete dirent from directory */
682 int hpfs_remove_dirent(struct inode
*i
, dnode_secno dno
, struct hpfs_dirent
*de
,
683 struct quad_buffer_head
*qbh
, int depth
)
685 struct dnode
*dnode
= qbh
->data
;
686 dnode_secno down
= 0;
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
);
694 if (de
->down
) down
= de_down_pointer(de
);
695 if (depth
&& (de
->down
|| (de
== dnode_first_de(dnode
) && de_next_de(de
)->last
))) {
697 hpfs_lock_creation(i
->i_sb
);
698 if (hpfs_check_free_dnodes(i
->i_sb
, FREE_DNODES_DEL
)) {
700 hpfs_unlock_creation(i
->i_sb
);
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
);
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
);
716 delete_empty_dnode(i
, dno
);
717 if (lock
) hpfs_unlock_creation(i
->i_sb
);
721 void hpfs_count_dnodes(struct super_block
*s
, dnode_secno dno
, int *n_dnodes
,
722 int *n_subdirs
, int *n_items
)
725 struct quad_buffer_head qbh
;
726 struct hpfs_dirent
*de
;
727 dnode_secno ptr
, odno
= 0;
731 if (n_dnodes
) (*n_dnodes
)++;
733 if (hpfs_stop_cycles(s
, dno
, &c1
, &c2
, "hpfs_count_dnodes #1")) return;
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
);
741 if (de
->down
) if (de_down_pointer(de
) == ptr
) goto process_de
;
744 hpfs_error(s
, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
753 dno
= de_down_pointer(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
;
763 if (dnode
->root_dnode
) {
769 if (hpfs_stop_cycles(s
, ptr
, &d1
, &d2
, "hpfs_count_dnodes #2")) return;
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
)
778 struct hpfs_dirent
*de
, *de_end
;
780 dnode
= hpfs_map_dnode(s
, dno
, qbh
);
781 if (!dnode
) return NULL
;
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
)) {
792 hpfs_error(s
, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno
, n
);
796 dnode_secno
hpfs_de_as_down_as_possible(struct super_block
*s
, dnode_secno dno
)
798 struct quad_buffer_head qbh
;
801 struct hpfs_dirent
*de
;
806 if (hpfs_stop_cycles(s
, d
, &c1
, &c2
, "hpfs_de_as_down_as_possible"))
808 if (!(de
= map_nth_dirent(s
, d
, 1, &qbh
, NULL
))) return dno
;
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
);
817 d
= de_down_pointer(de
);
822 struct hpfs_dirent
*map_pos_dirent(struct inode
*inode
, loff_t
*posp
,
823 struct quad_buffer_head
*qbh
)
828 struct hpfs_dirent
*de
, *d
;
829 struct hpfs_dirent
*up_de
;
830 struct hpfs_dirent
*end_up_de
;
832 struct dnode
*up_dnode
;
833 struct quad_buffer_head qbh0
;
838 if (!(de
= map_nth_dirent(inode
->i_sb
, dno
, pos
, qbh
, &dnode
)))
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
);
847 /* We're going down the tree */
849 *posp
= ((loff_t
) hpfs_de_as_down_as_possible(inode
->i_sb
, de_down_pointer(d
)) << 4) + 1;
856 if (dnode
->root_dnode
) goto bail
;
858 if (!(up_dnode
= hpfs_map_dnode(inode
->i_sb
, dnode
->up
, &qbh0
)))
861 end_up_de
= dnode_end_de(up_dnode
);
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
;
874 hpfs_error(inode
->i_sb
, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
883 /* Find a dirent in tree */
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
)
889 struct hpfs_dirent
*de
;
890 struct hpfs_dirent
*de_end
;
893 if (!S_ISDIR(inode
->i_mode
)) hpfs_error(inode
->i_sb
, "map_dirent: not a directory\n");
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
;
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
);
908 dno
= de_down_pointer(de
);
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
925 void hpfs_remove_dtree(struct super_block
*s
, dnode_secno dno
)
927 struct quad_buffer_head qbh
;
929 struct hpfs_dirent
*de
;
930 dnode_secno d1
, d2
, rdno
= dno
;
932 if (!(dnode
= hpfs_map_dnode(s
, dno
, &qbh
))) return;
933 de
= dnode_first_de(dnode
);
935 if (de
->down
) d1
= de_down_pointer(de
);
938 hpfs_free_dnode(s
, dno
);
942 if (!de
->first
) goto error
;
943 d1
= de
->down
? de_down_pointer(de
) : 0;
945 if (!de
->last
) goto error
;
946 d2
= de
->down
? de_down_pointer(de
) : 0;
948 hpfs_free_dnode(s
, dno
);
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;
956 hpfs_free_dnode(s
, dno
);
964 hpfs_free_dnode(s
, dno
);
965 hpfs_error(s
, "directory %08x is corrupted or not empty", rdno
);
969 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
970 * a help for searching.
973 struct hpfs_dirent
*map_fnode_dirent(struct super_block
*s
, fnode_secno fno
,
974 struct fnode
*f
, struct quad_buffer_head
*qbh
)
978 int name1len
, name2len
;
980 dnode_secno dno
, downd
;
982 struct buffer_head
*bh
;
983 struct hpfs_dirent
*de
, *de_end
;
988 if (!(name2
= kmalloc(256, GFP_KERNEL
))) {
989 printk("HPFS: out of memory, can't map dirent\n");
993 memcpy(name2
, name1
, name1len
= name2len
= f
->len
);
995 memcpy(name2
, name1
, 15);
996 memset(name2
+ 15, 0xff, 256 - 15);
997 /*name2[15] = 0xff;*/
998 name1len
= 15; name2len
= 256;
1000 if (!(upf
= hpfs_map_fnode(s
, f
->up
, &bh
))) {
1004 if (!upf
->dirflag
) {
1006 hpfs_error(s
, "fnode %08x has non-directory parent %08x", fno
, f
->up
);
1010 dno
= upf
->u
.external
[0].disk_secno
;
1015 if (!(d
= hpfs_map_dnode(s
, dno
, qbh
))) {
1019 de_end
= dnode_end_de(d
);
1020 de
= dnode_first_de(d
);
1022 while (de
< de_end
) {
1023 if (de
->down
) if (de_down_pointer(de
) == downd
) goto f
;
1024 de
= de_next_de(de
);
1026 hpfs_error(s
, "pointer to dnode %08x not found in dnode %08x", downd
, dno
);
1032 if (de
->fnode
== fno
) {
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
);
1041 if (hpfs_stop_cycles(s
, dno
, &c1
, &c2
, "map_fnode_dirent #1")) {
1048 if (de
->fnode
== fno
) {
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
;
1060 if (hpfs_stop_cycles(s
, downd
, &d1
, &d2
, "map_fnode_dirent #2")) {
1067 hpfs_error(s
, "dirent for fnode %08x not found", fno
);