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 printk("HPFS: get_pos: not_found\n");
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 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", le32_to_cpu(d
->self
));
136 if (hpfs_sb(s
)->sb_chk
) {
138 hpfs_error(s
, "set_last_pointer: dnode %08x has already last pointer %08x",
139 le32_to_cpu(d
->self
), de_down_pointer(de
));
142 if (le16_to_cpu(de
->length
) != 32) {
143 hpfs_error(s
, "set_last_pointer: bad last dirent in dnode %08x", le32_to_cpu(d
->self
));
148 le32_add_cpu(&d
->first_free
, 4);
149 if (le32_to_cpu(d
->first_free
) > 2048) {
150 hpfs_error(s
, "set_last_pointer: too long dnode %08x", le32_to_cpu(d
->self
));
151 le32_add_cpu(&d
->first_free
, -4);
154 de
->length
= cpu_to_le16(36);
156 *(__le32
*)((char *)de
+ 32) = cpu_to_le32(ptr
);
160 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
162 struct hpfs_dirent
*hpfs_add_de(struct super_block
*s
, struct dnode
*d
,
163 const unsigned char *name
,
164 unsigned namelen
, secno down_ptr
)
166 struct hpfs_dirent
*de
;
167 struct hpfs_dirent
*de_end
= dnode_end_de(d
);
168 unsigned d_size
= de_size(namelen
, down_ptr
);
169 for (de
= dnode_first_de(d
); de
< de_end
; de
= de_next_de(de
)) {
170 int c
= hpfs_compare_names(s
, name
, namelen
, de
->name
, de
->namelen
, de
->last
);
172 hpfs_error(s
, "name (%c,%d) already exists in dnode %08x", *name
, namelen
, le32_to_cpu(d
->self
));
177 memmove((char *)de
+ d_size
, de
, (char *)de_end
- (char *)de
);
178 memset(de
, 0, d_size
);
180 *(__le32
*)((char *)de
+ d_size
- 4) = cpu_to_le32(down_ptr
);
183 de
->length
= cpu_to_le16(d_size
);
184 de
->not_8x3
= hpfs_is_name_long(name
, namelen
);
185 de
->namelen
= namelen
;
186 memcpy(de
->name
, name
, namelen
);
187 le32_add_cpu(&d
->first_free
, d_size
);
191 /* Delete dirent and don't care about its subtree */
193 static void hpfs_delete_de(struct super_block
*s
, struct dnode
*d
,
194 struct hpfs_dirent
*de
)
197 hpfs_error(s
, "attempt to delete last dirent in dnode %08x", le32_to_cpu(d
->self
));
200 d
->first_free
= cpu_to_le32(le32_to_cpu(d
->first_free
) - le16_to_cpu(de
->length
));
201 memmove(de
, de_next_de(de
), le32_to_cpu(d
->first_free
) + (char *)d
- (char *)de
);
204 static void fix_up_ptrs(struct super_block
*s
, struct dnode
*d
)
206 struct hpfs_dirent
*de
;
207 struct hpfs_dirent
*de_end
= dnode_end_de(d
);
208 dnode_secno dno
= le32_to_cpu(d
->self
);
209 for (de
= dnode_first_de(d
); de
< de_end
; de
= de_next_de(de
))
211 struct quad_buffer_head qbh
;
213 if ((dd
= hpfs_map_dnode(s
, de_down_pointer(de
), &qbh
))) {
214 if (le32_to_cpu(dd
->up
) != dno
|| dd
->root_dnode
) {
215 dd
->up
= cpu_to_le32(dno
);
217 hpfs_mark_4buffers_dirty(&qbh
);
224 /* Add an entry to dnode and do dnode splitting if required */
226 static int hpfs_add_to_dnode(struct inode
*i
, dnode_secno dno
,
227 const unsigned char *name
, unsigned namelen
,
228 struct hpfs_dirent
*new_de
, dnode_secno down_ptr
)
230 struct quad_buffer_head qbh
, qbh1
, qbh2
;
231 struct dnode
*d
, *ad
, *rd
, *nd
= NULL
;
232 dnode_secno adno
, rdno
;
233 struct hpfs_dirent
*de
;
234 struct hpfs_dirent nde
;
235 unsigned char *nname
;
238 struct buffer_head
*bh
;
241 if (!(nname
= kmalloc(256, GFP_NOFS
))) {
242 printk("HPFS: out of memory, can't add to dnode\n");
246 if (namelen
>= 256) {
247 hpfs_error(i
->i_sb
, "hpfs_add_to_dnode: namelen == %d", namelen
);
252 if (!(d
= hpfs_map_dnode(i
->i_sb
, dno
, &qbh
))) {
258 if (hpfs_sb(i
->i_sb
)->sb_chk
)
259 if (hpfs_stop_cycles(i
->i_sb
, dno
, &c1
, &c2
, "hpfs_add_to_dnode")) {
265 if (le32_to_cpu(d
->first_free
) + de_size(namelen
, down_ptr
) <= 2048) {
267 copy_de(de
=hpfs_add_de(i
->i_sb
, d
, name
, namelen
, down_ptr
), new_de
);
269 for_all_poss(i
, hpfs_pos_ins
, t
, 1);
270 for_all_poss(i
, hpfs_pos_subst
, 4, t
);
271 for_all_poss(i
, hpfs_pos_subst
, 5, t
+ 1);
272 hpfs_mark_4buffers_dirty(&qbh
);
278 if (!nd
) if (!(nd
= kmalloc(0x924, GFP_NOFS
))) {
279 /* 0x924 is a max size of dnode after adding a dirent with
280 max name length. We alloc this only once. There must
281 not be any error while splitting dnodes, otherwise the
282 whole directory, not only file we're adding, would
284 printk("HPFS: out of memory for dnode splitting\n");
289 memcpy(nd
, d
, le32_to_cpu(d
->first_free
));
290 copy_de(de
= hpfs_add_de(i
->i_sb
, nd
, name
, namelen
, down_ptr
), new_de
);
291 for_all_poss(i
, hpfs_pos_ins
, get_pos(nd
, de
), 1);
292 h
= ((char *)dnode_last_de(nd
) - (char *)nd
) / 2 + 10;
293 if (!(ad
= hpfs_alloc_dnode(i
->i_sb
, le32_to_cpu(d
->up
), &adno
, &qbh1
))) {
294 hpfs_error(i
->i_sb
, "unable to alloc dnode - dnode tree will be corrupted");
303 for (de
= dnode_first_de(nd
); (char *)de_next_de(de
) - (char *)nd
< h
; de
= de_next_de(de
)) {
304 copy_de(hpfs_add_de(i
->i_sb
, ad
, de
->name
, de
->namelen
, de
->down
? de_down_pointer(de
) : 0), de
);
305 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | pos
, ((loff_t
)adno
<< 4) | pos
);
308 copy_de(new_de
= &nde
, de
);
309 memcpy(nname
, de
->name
, de
->namelen
);
311 namelen
= de
->namelen
;
312 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | pos
, 4);
314 set_last_pointer(i
->i_sb
, ad
, de
->down
? de_down_pointer(de
) : 0);
316 memmove((char *)nd
+ 20, de
, le32_to_cpu(nd
->first_free
) + (char *)nd
- (char *)de
);
317 le32_add_cpu(&nd
->first_free
, -((char *)de
- (char *)nd
- 20));
318 memcpy(d
, nd
, le32_to_cpu(nd
->first_free
));
319 for_all_poss(i
, hpfs_pos_del
, (loff_t
)dno
<< 4, pos
);
320 fix_up_ptrs(i
->i_sb
, ad
);
321 if (!d
->root_dnode
) {
323 dno
= le32_to_cpu(ad
->up
);
324 hpfs_mark_4buffers_dirty(&qbh
);
326 hpfs_mark_4buffers_dirty(&qbh1
);
330 if (!(rd
= hpfs_alloc_dnode(i
->i_sb
, le32_to_cpu(d
->up
), &rdno
, &qbh2
))) {
331 hpfs_error(i
->i_sb
, "unable to alloc dnode - dnode tree will be corrupted");
342 if (!(fnode
= hpfs_map_fnode(i
->i_sb
, le32_to_cpu(d
->up
), &bh
))) {
343 hpfs_free_dnode(i
->i_sb
, rdno
);
351 fnode
->u
.external
[0].disk_secno
= cpu_to_le32(rdno
);
352 mark_buffer_dirty(bh
);
354 hpfs_i(i
)->i_dno
= rdno
;
355 d
->up
= ad
->up
= cpu_to_le32(rdno
);
356 d
->root_dnode
= ad
->root_dnode
= 0;
357 hpfs_mark_4buffers_dirty(&qbh
);
359 hpfs_mark_4buffers_dirty(&qbh1
);
362 set_last_pointer(i
->i_sb
, rd
, dno
);
369 * Add an entry to directory btree.
370 * I hate such crazy directory structure.
371 * It's easy to read but terrible to write.
372 * I wrote this directory code 4 times.
373 * I hope, now it's finally bug-free.
376 int hpfs_add_dirent(struct inode
*i
,
377 const unsigned char *name
, unsigned namelen
,
378 struct hpfs_dirent
*new_de
)
380 struct hpfs_inode_info
*hpfs_inode
= hpfs_i(i
);
382 struct hpfs_dirent
*de
, *de_end
;
383 struct quad_buffer_head qbh
;
387 dno
= hpfs_inode
->i_dno
;
389 if (hpfs_sb(i
->i_sb
)->sb_chk
)
390 if (hpfs_stop_cycles(i
->i_sb
, dno
, &c1
, &c2
, "hpfs_add_dirent")) return 1;
391 if (!(d
= hpfs_map_dnode(i
->i_sb
, dno
, &qbh
))) return 1;
392 de_end
= dnode_end_de(d
);
393 for (de
= dnode_first_de(d
); de
< de_end
; de
= de_next_de(de
)) {
394 if (!(c
= hpfs_compare_names(i
->i_sb
, name
, namelen
, de
->name
, de
->namelen
, de
->last
))) {
400 dno
= de_down_pointer(de
);
408 if (hpfs_check_free_dnodes(i
->i_sb
, FREE_DNODES_ADD
)) {
413 c
= hpfs_add_to_dnode(i
, dno
, name
, namelen
, new_de
, 0);
419 * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
420 * Return the dnode we moved from (to be checked later if it's empty)
423 static secno
move_to_top(struct inode
*i
, dnode_secno from
, dnode_secno to
)
425 dnode_secno dno
, ddno
;
426 dnode_secno chk_up
= to
;
428 struct quad_buffer_head qbh
;
429 struct hpfs_dirent
*de
, *nde
;
435 if (hpfs_sb(i
->i_sb
)->sb_chk
)
436 if (hpfs_stop_cycles(i
->i_sb
, dno
, &c1
, &c2
, "move_to_top"))
438 if (!(dnode
= hpfs_map_dnode(i
->i_sb
, dno
, &qbh
))) return 0;
439 if (hpfs_sb(i
->i_sb
)->sb_chk
) {
440 if (le32_to_cpu(dnode
->up
) != chk_up
) {
441 hpfs_error(i
->i_sb
, "move_to_top: up pointer from %08x should be %08x, is %08x",
442 dno
, chk_up
, le32_to_cpu(dnode
->up
));
448 if (!(de
= dnode_last_de(dnode
))) {
449 hpfs_error(i
->i_sb
, "move_to_top: dnode %08x has no last de", dno
);
453 if (!de
->down
) break;
454 dno
= de_down_pointer(de
);
457 while (!(de
= dnode_pre_last_de(dnode
))) {
458 dnode_secno up
= le32_to_cpu(dnode
->up
);
460 hpfs_free_dnode(i
->i_sb
, dno
);
463 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | 1, 5);
464 if (up
== to
) return to
;
465 if (!(dnode
= hpfs_map_dnode(i
->i_sb
, up
, &qbh
))) return 0;
466 if (dnode
->root_dnode
) {
467 hpfs_error(i
->i_sb
, "move_to_top: got to root_dnode while moving from %08x to %08x", from
, to
);
471 de
= dnode_last_de(dnode
);
472 if (!de
|| !de
->down
) {
473 hpfs_error(i
->i_sb
, "move_to_top: dnode %08x doesn't point down to %08x", up
, dno
);
477 le32_add_cpu(&dnode
->first_free
, -4);
478 le16_add_cpu(&de
->length
, -4);
480 hpfs_mark_4buffers_dirty(&qbh
);
483 t
= get_pos(dnode
, de
);
484 for_all_poss(i
, hpfs_pos_subst
, t
, 4);
485 for_all_poss(i
, hpfs_pos_subst
, t
+ 1, 5);
486 if (!(nde
= kmalloc(le16_to_cpu(de
->length
), GFP_NOFS
))) {
487 hpfs_error(i
->i_sb
, "out of memory for dirent - directory will be corrupted");
491 memcpy(nde
, de
, le16_to_cpu(de
->length
));
492 ddno
= de
->down
? de_down_pointer(de
) : 0;
493 hpfs_delete_de(i
->i_sb
, dnode
, de
);
494 set_last_pointer(i
->i_sb
, dnode
, ddno
);
495 hpfs_mark_4buffers_dirty(&qbh
);
497 a
= hpfs_add_to_dnode(i
, to
, nde
->name
, nde
->namelen
, nde
, from
);
504 * Check if a dnode is empty and delete it from the tree
505 * (chkdsk doesn't like empty dnodes)
508 static void delete_empty_dnode(struct inode
*i
, dnode_secno dno
)
510 struct hpfs_inode_info
*hpfs_inode
= hpfs_i(i
);
511 struct quad_buffer_head qbh
;
513 dnode_secno down
, up
, ndown
;
515 struct hpfs_dirent
*de
;
518 if (hpfs_stop_cycles(i
->i_sb
, dno
, &c1
, &c2
, "delete_empty_dnode")) return;
519 if (!(dnode
= hpfs_map_dnode(i
->i_sb
, dno
, &qbh
))) return;
520 if (le32_to_cpu(dnode
->first_free
) > 56) goto end
;
521 if (le32_to_cpu(dnode
->first_free
) == 52 || le32_to_cpu(dnode
->first_free
) == 56) {
522 struct hpfs_dirent
*de_end
;
523 int root
= dnode
->root_dnode
;
524 up
= le32_to_cpu(dnode
->up
);
525 de
= dnode_first_de(dnode
);
526 down
= de
->down
? de_down_pointer(de
) : 0;
527 if (hpfs_sb(i
->i_sb
)->sb_chk
) if (root
&& !down
) {
528 hpfs_error(i
->i_sb
, "delete_empty_dnode: root dnode %08x is empty", dno
);
532 hpfs_free_dnode(i
->i_sb
, dno
);
537 struct buffer_head
*bh
;
539 struct quad_buffer_head qbh1
;
540 if (hpfs_sb(i
->i_sb
)->sb_chk
)
541 if (up
!= i
->i_ino
) {
543 "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
544 dno
, up
, (unsigned long)i
->i_ino
);
547 if ((d1
= hpfs_map_dnode(i
->i_sb
, down
, &qbh1
))) {
548 d1
->up
= cpu_to_le32(up
);
550 hpfs_mark_4buffers_dirty(&qbh1
);
553 if ((fnode
= hpfs_map_fnode(i
->i_sb
, up
, &bh
))) {
554 fnode
->u
.external
[0].disk_secno
= cpu_to_le32(down
);
555 mark_buffer_dirty(bh
);
558 hpfs_inode
->i_dno
= down
;
559 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | 1, (loff_t
) 12);
562 if (!(dnode
= hpfs_map_dnode(i
->i_sb
, up
, &qbh
))) return;
564 de_end
= dnode_end_de(dnode
);
565 for (de
= dnode_first_de(dnode
); de
< de_end
; de
= de_next_de(de
), p
++)
566 if (de
->down
) if (de_down_pointer(de
) == dno
) goto fnd
;
567 hpfs_error(i
->i_sb
, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno
, up
);
570 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)dno
<< 4) | 1, ((loff_t
)up
<< 4) | p
);
573 le16_add_cpu(&de
->length
, -4);
574 le32_add_cpu(&dnode
->first_free
, -4);
575 memmove(de_next_de(de
), (char *)de_next_de(de
) + 4,
576 (char *)dnode
+ le32_to_cpu(dnode
->first_free
) - (char *)de_next_de(de
));
579 struct quad_buffer_head qbh1
;
580 *(dnode_secno
*) ((void *) de
+ le16_to_cpu(de
->length
) - 4) = down
;
581 if ((d1
= hpfs_map_dnode(i
->i_sb
, down
, &qbh1
))) {
582 d1
->up
= cpu_to_le32(up
);
583 hpfs_mark_4buffers_dirty(&qbh1
);
588 hpfs_error(i
->i_sb
, "delete_empty_dnode: dnode %08x, first_free == %03x", dno
, le32_to_cpu(dnode
->first_free
));
593 struct hpfs_dirent
*de_next
= de_next_de(de
);
594 struct hpfs_dirent
*de_cp
;
596 struct quad_buffer_head qbh1
;
597 if (!de_next
->down
) goto endm
;
598 ndown
= de_down_pointer(de_next
);
599 if (!(de_cp
= kmalloc(le16_to_cpu(de
->length
), GFP_NOFS
))) {
600 printk("HPFS: out of memory for dtree balancing\n");
603 memcpy(de_cp
, de
, le16_to_cpu(de
->length
));
604 hpfs_delete_de(i
->i_sb
, dnode
, de
);
605 hpfs_mark_4buffers_dirty(&qbh
);
607 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)up
<< 4) | p
, 4);
608 for_all_poss(i
, hpfs_pos_del
, ((loff_t
)up
<< 4) | p
, 1);
609 if (de_cp
->down
) if ((d1
= hpfs_map_dnode(i
->i_sb
, de_down_pointer(de_cp
), &qbh1
))) {
610 d1
->up
= cpu_to_le32(ndown
);
611 hpfs_mark_4buffers_dirty(&qbh1
);
614 hpfs_add_to_dnode(i
, ndown
, de_cp
->name
, de_cp
->namelen
, de_cp
, de_cp
->down
? de_down_pointer(de_cp
) : 0);
615 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
620 struct hpfs_dirent
*de_prev
= dnode_pre_last_de(dnode
);
621 struct hpfs_dirent
*de_cp
;
623 struct quad_buffer_head qbh1
;
626 hpfs_error(i
->i_sb
, "delete_empty_dnode: empty dnode %08x", up
);
627 hpfs_mark_4buffers_dirty(&qbh
);
632 if (!de_prev
->down
) goto endm
;
633 ndown
= de_down_pointer(de_prev
);
634 if ((d1
= hpfs_map_dnode(i
->i_sb
, ndown
, &qbh1
))) {
635 struct hpfs_dirent
*del
= dnode_last_de(d1
);
636 dlp
= del
->down
? de_down_pointer(del
) : 0;
638 if (le32_to_cpu(d1
->first_free
) > 2044) {
639 if (hpfs_sb(i
->i_sb
)->sb_chk
>= 2) {
640 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
641 printk("HPFS: warning: terminating balancing operation\n");
646 if (hpfs_sb(i
->i_sb
)->sb_chk
>= 2) {
647 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
648 printk("HPFS: warning: goin'on\n");
650 le16_add_cpu(&del
->length
, 4);
652 le32_add_cpu(&d1
->first_free
, 4);
655 le16_add_cpu(&del
->length
, -4);
657 le32_add_cpu(&d1
->first_free
, -4);
659 *(__le32
*) ((void *) del
+ le16_to_cpu(del
->length
) - 4) = cpu_to_le32(down
);
661 if (!(de_cp
= kmalloc(le16_to_cpu(de_prev
->length
), GFP_NOFS
))) {
662 printk("HPFS: out of memory for dtree balancing\n");
666 hpfs_mark_4buffers_dirty(&qbh1
);
668 memcpy(de_cp
, de_prev
, le16_to_cpu(de_prev
->length
));
669 hpfs_delete_de(i
->i_sb
, dnode
, de_prev
);
670 if (!de_prev
->down
) {
671 le16_add_cpu(&de_prev
->length
, 4);
673 le32_add_cpu(&dnode
->first_free
, 4);
675 *(__le32
*) ((void *) de_prev
+ le16_to_cpu(de_prev
->length
) - 4) = cpu_to_le32(ndown
);
676 hpfs_mark_4buffers_dirty(&qbh
);
678 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)up
<< 4) | (p
- 1), 4);
679 for_all_poss(i
, hpfs_pos_subst
, ((loff_t
)up
<< 4) | p
, ((loff_t
)up
<< 4) | (p
- 1));
680 if (down
) if ((d1
= hpfs_map_dnode(i
->i_sb
, de_down_pointer(de
), &qbh1
))) {
681 d1
->up
= cpu_to_le32(ndown
);
682 hpfs_mark_4buffers_dirty(&qbh1
);
685 hpfs_add_to_dnode(i
, ndown
, de_cp
->name
, de_cp
->namelen
, de_cp
, dlp
);
691 hpfs_mark_4buffers_dirty(&qbh
);
697 /* Delete dirent from directory */
699 int hpfs_remove_dirent(struct inode
*i
, dnode_secno dno
, struct hpfs_dirent
*de
,
700 struct quad_buffer_head
*qbh
, int depth
)
702 struct dnode
*dnode
= qbh
->data
;
703 dnode_secno down
= 0;
705 if (de
->first
|| de
->last
) {
706 hpfs_error(i
->i_sb
, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno
);
710 if (de
->down
) down
= de_down_pointer(de
);
711 if (depth
&& (de
->down
|| (de
== dnode_first_de(dnode
) && de_next_de(de
)->last
))) {
712 if (hpfs_check_free_dnodes(i
->i_sb
, FREE_DNODES_DEL
)) {
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
);
728 delete_empty_dnode(i
, dno
);
732 void hpfs_count_dnodes(struct super_block
*s
, dnode_secno dno
, int *n_dnodes
,
733 int *n_subdirs
, int *n_items
)
736 struct quad_buffer_head qbh
;
737 struct hpfs_dirent
*de
;
738 dnode_secno ptr
, odno
= 0;
742 if (n_dnodes
) (*n_dnodes
)++;
743 if (hpfs_sb(s
)->sb_chk
)
744 if (hpfs_stop_cycles(s
, dno
, &c1
, &c2
, "hpfs_count_dnodes #1")) return;
747 if (!(dnode
= hpfs_map_dnode(s
, dno
, &qbh
))) return;
748 if (hpfs_sb(s
)->sb_chk
) if (odno
&& odno
!= -1 && le32_to_cpu(dnode
->up
) != odno
)
749 hpfs_error(s
, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno
, dno
, le32_to_cpu(dnode
->up
));
750 de
= dnode_first_de(dnode
);
752 if (de
->down
) if (de_down_pointer(de
) == ptr
) goto process_de
;
755 hpfs_error(s
, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
764 dno
= de_down_pointer(de
);
769 if (!de
->first
&& !de
->last
&& de
->directory
&& n_subdirs
) (*n_subdirs
)++;
770 if (!de
->first
&& !de
->last
&& n_items
) (*n_items
)++;
771 if ((de
= de_next_de(de
)) < dnode_end_de(dnode
)) goto next_de
;
773 dno
= le32_to_cpu(dnode
->up
);
774 if (dnode
->root_dnode
) {
779 if (hpfs_sb(s
)->sb_chk
)
780 if (hpfs_stop_cycles(s
, ptr
, &d1
, &d2
, "hpfs_count_dnodes #2")) return;
785 static struct hpfs_dirent
*map_nth_dirent(struct super_block
*s
, dnode_secno dno
, int n
,
786 struct quad_buffer_head
*qbh
, struct dnode
**dn
)
789 struct hpfs_dirent
*de
, *de_end
;
791 dnode
= hpfs_map_dnode(s
, dno
, qbh
);
792 if (!dnode
) return NULL
;
794 de
= dnode_first_de(dnode
);
795 de_end
= dnode_end_de(dnode
);
796 for (i
= 1; de
< de_end
; i
++, de
= de_next_de(de
)) {
803 hpfs_error(s
, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno
, n
);
807 dnode_secno
hpfs_de_as_down_as_possible(struct super_block
*s
, dnode_secno dno
)
809 struct quad_buffer_head qbh
;
812 struct hpfs_dirent
*de
;
816 if (hpfs_sb(s
)->sb_chk
)
817 if (hpfs_stop_cycles(s
, d
, &c1
, &c2
, "hpfs_de_as_down_as_possible"))
819 if (!(de
= map_nth_dirent(s
, d
, 1, &qbh
, NULL
))) return dno
;
820 if (hpfs_sb(s
)->sb_chk
)
821 if (up
&& le32_to_cpu(((struct dnode
*)qbh
.data
)->up
) != up
)
822 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
));
828 d
= de_down_pointer(de
);
833 struct hpfs_dirent
*map_pos_dirent(struct inode
*inode
, loff_t
*posp
,
834 struct quad_buffer_head
*qbh
)
839 struct hpfs_dirent
*de
, *d
;
840 struct hpfs_dirent
*up_de
;
841 struct hpfs_dirent
*end_up_de
;
843 struct dnode
*up_dnode
;
844 struct quad_buffer_head qbh0
;
849 if (!(de
= map_nth_dirent(inode
->i_sb
, dno
, pos
, qbh
, &dnode
)))
852 /* Going to the next dirent */
853 if ((d
= de_next_de(de
)) < dnode_end_de(dnode
)) {
854 if (!(++*posp
& 077)) {
855 hpfs_error(inode
->i_sb
,
856 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
857 (unsigned long long)*posp
);
860 /* We're going down the tree */
862 *posp
= ((loff_t
) hpfs_de_as_down_as_possible(inode
->i_sb
, de_down_pointer(d
)) << 4) + 1;
869 if (dnode
->root_dnode
) goto bail
;
871 if (!(up_dnode
= hpfs_map_dnode(inode
->i_sb
, le32_to_cpu(dnode
->up
), &qbh0
)))
874 end_up_de
= dnode_end_de(up_dnode
);
876 for (up_de
= dnode_first_de(up_dnode
); up_de
< end_up_de
;
877 up_de
= de_next_de(up_de
)) {
878 if (!(++c
& 077)) hpfs_error(inode
->i_sb
,
879 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode
->up
));
880 if (up_de
->down
&& de_down_pointer(up_de
) == dno
) {
881 *posp
= ((loff_t
) le32_to_cpu(dnode
->up
) << 4) + c
;
887 hpfs_error(inode
->i_sb
, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
888 dno
, le32_to_cpu(dnode
->up
));
896 /* Find a dirent in tree */
898 struct hpfs_dirent
*map_dirent(struct inode
*inode
, dnode_secno dno
,
899 const unsigned char *name
, unsigned len
,
900 dnode_secno
*dd
, struct quad_buffer_head
*qbh
)
903 struct hpfs_dirent
*de
;
904 struct hpfs_dirent
*de_end
;
907 if (!S_ISDIR(inode
->i_mode
)) hpfs_error(inode
->i_sb
, "map_dirent: not a directory\n");
909 if (hpfs_sb(inode
->i_sb
)->sb_chk
)
910 if (hpfs_stop_cycles(inode
->i_sb
, dno
, &c1
, &c2
, "map_dirent")) return NULL
;
911 if (!(dnode
= hpfs_map_dnode(inode
->i_sb
, dno
, qbh
))) return NULL
;
913 de_end
= dnode_end_de(dnode
);
914 for (de
= dnode_first_de(dnode
); de
< de_end
; de
= de_next_de(de
)) {
915 int t
= hpfs_compare_names(inode
->i_sb
, name
, len
, de
->name
, de
->namelen
, de
->last
);
922 dno
= de_down_pointer(de
);
934 * Remove empty directory. In normal cases it is only one dnode with two
935 * entries, but we must handle also such obscure cases when it's a tree
939 void hpfs_remove_dtree(struct super_block
*s
, dnode_secno dno
)
941 struct quad_buffer_head qbh
;
943 struct hpfs_dirent
*de
;
944 dnode_secno d1
, d2
, rdno
= dno
;
946 if (!(dnode
= hpfs_map_dnode(s
, dno
, &qbh
))) return;
947 de
= dnode_first_de(dnode
);
949 if (de
->down
) d1
= de_down_pointer(de
);
952 hpfs_free_dnode(s
, dno
);
956 if (!de
->first
) goto error
;
957 d1
= de
->down
? de_down_pointer(de
) : 0;
959 if (!de
->last
) goto error
;
960 d2
= de
->down
? de_down_pointer(de
) : 0;
962 hpfs_free_dnode(s
, dno
);
965 if (!(dnode
= hpfs_map_dnode(s
, dno
= d1
, &qbh
))) return;
966 de
= dnode_first_de(dnode
);
967 if (!de
->last
) goto error
;
968 d1
= de
->down
? de_down_pointer(de
) : 0;
970 hpfs_free_dnode(s
, dno
);
978 hpfs_free_dnode(s
, dno
);
979 hpfs_error(s
, "directory %08x is corrupted or not empty", rdno
);
983 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
984 * a help for searching.
987 struct hpfs_dirent
*map_fnode_dirent(struct super_block
*s
, fnode_secno fno
,
988 struct fnode
*f
, struct quad_buffer_head
*qbh
)
990 unsigned char *name1
;
991 unsigned char *name2
;
992 int name1len
, name2len
;
994 dnode_secno dno
, downd
;
996 struct buffer_head
*bh
;
997 struct hpfs_dirent
*de
, *de_end
;
1002 if (!(name2
= kmalloc(256, GFP_NOFS
))) {
1003 printk("HPFS: out of memory, can't map dirent\n");
1007 memcpy(name2
, name1
, name1len
= name2len
= f
->len
);
1009 memcpy(name2
, name1
, 15);
1010 memset(name2
+ 15, 0xff, 256 - 15);
1011 /*name2[15] = 0xff;*/
1012 name1len
= 15; name2len
= 256;
1014 if (!(upf
= hpfs_map_fnode(s
, le32_to_cpu(f
->up
), &bh
))) {
1018 if (!fnode_is_dir(upf
)) {
1020 hpfs_error(s
, "fnode %08x has non-directory parent %08x", fno
, le32_to_cpu(f
->up
));
1024 dno
= le32_to_cpu(upf
->u
.external
[0].disk_secno
);
1029 if (!(d
= hpfs_map_dnode(s
, dno
, qbh
))) {
1033 de_end
= dnode_end_de(d
);
1034 de
= dnode_first_de(d
);
1036 while (de
< de_end
) {
1037 if (de
->down
) if (de_down_pointer(de
) == downd
) goto f
;
1038 de
= de_next_de(de
);
1040 hpfs_error(s
, "pointer to dnode %08x not found in dnode %08x", downd
, dno
);
1046 if (le32_to_cpu(de
->fnode
) == fno
) {
1050 c
= hpfs_compare_names(s
, name1
, name1len
, de
->name
, de
->namelen
, de
->last
);
1051 if (c
< 0 && de
->down
) {
1052 dno
= de_down_pointer(de
);
1054 if (hpfs_sb(s
)->sb_chk
)
1055 if (hpfs_stop_cycles(s
, dno
, &c1
, &c2
, "map_fnode_dirent #1")) {
1062 if (le32_to_cpu(de
->fnode
) == fno
) {
1066 c
= hpfs_compare_names(s
, name2
, name2len
, de
->name
, de
->namelen
, de
->last
);
1067 if (c
< 0 && !de
->last
) goto not_found
;
1068 if ((de
= de_next_de(de
)) < de_end
) goto next_de
;
1069 if (d
->root_dnode
) goto not_found
;
1071 dno
= le32_to_cpu(d
->up
);
1073 if (hpfs_sb(s
)->sb_chk
)
1074 if (hpfs_stop_cycles(s
, downd
, &d1
, &d2
, "map_fnode_dirent #2")) {
1081 hpfs_error(s
, "dirent for fnode %08x not found", fno
);
This page took 0.054312 seconds and 5 git commands to generate.