aboutsummaryrefslogtreecommitdiffstats
path: root/fs/hpfs/dnode.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/hpfs/dnode.c')
-rw-r--r--fs/hpfs/dnode.c1080
1 files changed, 1080 insertions, 0 deletions
diff --git a/fs/hpfs/dnode.c b/fs/hpfs/dnode.c
new file mode 100644
index 000000000000..1d21307730a8
--- /dev/null
+++ b/fs/hpfs/dnode.c
@@ -0,0 +1,1080 @@
1/*
2 * linux/fs/hpfs/dnode.c
3 *
4 * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
5 *
6 * handling directory dnode tree - adding, deleteing & searching for dirents
7 */
8
9#include "hpfs_fn.h"
10
11static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
12{
13 struct hpfs_dirent *de;
14 struct hpfs_dirent *de_end = dnode_end_de(d);
15 int i = 1;
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;
18 i++;
19 }
20 printk("HPFS: get_pos: not_found\n");
21 return ((loff_t)d->self << 4) | (loff_t)1;
22}
23
24void hpfs_add_pos(struct inode *inode, loff_t *pos)
25{
26 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
27 int i = 0;
28 loff_t **ppos;
29
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;
33 if (!(i&0x0f)) {
34 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
35 printk("HPFS: out of memory for position list\n");
36 return;
37 }
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);
41 }
42 hpfs_inode->i_rddir_off = ppos;
43 }
44 hpfs_inode->i_rddir_off[i] = pos;
45 hpfs_inode->i_rddir_off[i + 1] = NULL;
46}
47
48void hpfs_del_pos(struct inode *inode, loff_t *pos)
49{
50 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
51 loff_t **i, **j;
52
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;
55 goto not_f;
56 fnd:
57 for (j = i + 1; *j; j++) ;
58 *i = *(j - 1);
59 *(j - 1) = NULL;
60 if (j - 1 == hpfs_inode->i_rddir_off) {
61 kfree(hpfs_inode->i_rddir_off);
62 hpfs_inode->i_rddir_off = NULL;
63 }
64 return;
65 not_f:
66 /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
67 return;
68}
69
70static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
71 loff_t p1, loff_t p2)
72{
73 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
74 loff_t **i;
75
76 if (!hpfs_inode->i_rddir_off) return;
77 for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
78 return;
79}
80
81static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
82{
83 if (*p == f) *p = t;
84}
85
86/*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
87{
88 if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
89}*/
90
91static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
92{
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;
97 }
98}
99
100static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
101{
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;
106 }
107}
108
109static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
110{
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;
115 }
116 return deee;
117}
118
119static struct hpfs_dirent *dnode_last_de(struct dnode *d)
120{
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)) {
124 dee = de;
125 }
126 return dee;
127}
128
129static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
130{
131 struct hpfs_dirent *de;
132 if (!(de = dnode_last_de(d))) {
133 hpfs_error(s, "set_last_pointer: empty dnode %08x", d->self);
134 return;
135 }
136 if (hpfs_sb(s)->sb_chk) {
137 if (de->down) {
138 hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
139 d->self, de_down_pointer(de));
140 return;
141 }
142 if (de->length != 32) {
143 hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", d->self);
144 return;
145 }
146 }
147 if (ptr) {
148 if ((d->first_free += 4) > 2048) {
149 hpfs_error(s,"set_last_pointer: too long dnode %08x", d->self);
150 d->first_free -= 4;
151 return;
152 }
153 de->length = 36;
154 de->down = 1;
155 *(dnode_secno *)((char *)de + 32) = ptr;
156 }
157}
158
159/* Add an entry to dnode and don't care if it grows over 2048 bytes */
160
161struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d, unsigned char *name,
162 unsigned namelen, secno down_ptr)
163{
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);
169 if (!c) {
170 hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, d->self);
171 return NULL;
172 }
173 if (c < 0) break;
174 }
175 memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
176 memset(de, 0, d_size);
177 if (down_ptr) {
178 *(int *)((char *)de + d_size - 4) = down_ptr;
179 de->down = 1;
180 }
181 de->length = d_size;
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;
187 return de;
188}
189
190/* Delete dirent and don't care about its subtree */
191
192static void hpfs_delete_de(struct super_block *s, struct dnode *d,
193 struct hpfs_dirent *de)
194{
195 if (de->last) {
196 hpfs_error(s, "attempt to delete last dirent in dnode %08x", d->self);
197 return;
198 }
199 d->first_free -= de->length;
200 memmove(de, de_next_de(de), d->first_free + (char *)d - (char *)de);
201}
202
203static void fix_up_ptrs(struct super_block *s, struct dnode *d)
204{
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))
209 if (de->down) {
210 struct quad_buffer_head qbh;
211 struct dnode *dd;
212 if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
213 if (dd->up != dno || dd->root_dnode) {
214 dd->up = dno;
215 dd->root_dnode = 0;
216 hpfs_mark_4buffers_dirty(&qbh);
217 }
218 hpfs_brelse4(&qbh);
219 }
220 }
221}
222
223/* Add an entry to dnode and do dnode splitting if required */
224
225static 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)
228{
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;
234 char *nname;
235 int h;
236 int pos;
237 struct buffer_head *bh;
238 struct fnode *fnode;
239 int c1, c2 = 0;
240 if (!(nname = kmalloc(256, GFP_NOFS))) {
241 printk("HPFS: out of memory, can't add to dnode\n");
242 return 1;
243 }
244 go_up:
245 if (namelen >= 256) {
246 hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen);
247 if (nd) kfree(nd);
248 kfree(nname);
249 return 1;
250 }
251 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
252 if (nd) kfree(nd);
253 kfree(nname);
254 return 1;
255 }
256 go_up_a:
257 if (hpfs_sb(i->i_sb)->sb_chk)
258 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
259 hpfs_brelse4(&qbh);
260 if (nd) kfree(nd);
261 kfree(nname);
262 return 1;
263 }
264 if (d->first_free + de_size(namelen, down_ptr) <= 2048) {
265 loff_t t;
266 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
267 t = get_pos(d, 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);
272 hpfs_brelse4(&qbh);
273 if (nd) kfree(nd);
274 kfree(nname);
275 return 0;
276 }
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
282 be lost. */
283 printk("HPFS: out of memory for dnode splitting\n");
284 hpfs_brelse4(&qbh);
285 kfree(nname);
286 return 1;
287 }
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");
294 hpfs_brelse4(&qbh);
295 kfree(nd);
296 kfree(nname);
297 return 1;
298 }
299 i->i_size += 2048;
300 i->i_blocks += 4;
301 pos = 1;
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);
305 pos++;
306 }
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);
310 down_ptr = adno;
311 set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
312 de = de_next_de(de);
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);
321 hpfs_brelse4(&qbh);
322 hpfs_mark_4buffers_dirty(&qbh1);
323 hpfs_brelse4(&qbh1);
324 goto go_up;
325 }
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");
328 hpfs_brelse4(&qbh);
329 hpfs_brelse4(&qbh1);
330 kfree(nd);
331 kfree(nname);
332 return 1;
333 }
334 i->i_size += 2048;
335 i->i_blocks += 4;
336 rd->root_dnode = 1;
337 rd->up = d->up;
338 if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) {
339 hpfs_free_dnode(i->i_sb, rdno);
340 hpfs_brelse4(&qbh);
341 hpfs_brelse4(&qbh1);
342 hpfs_brelse4(&qbh2);
343 kfree(nd);
344 kfree(nname);
345 return 1;
346 }
347 fnode->u.external[0].disk_secno = rdno;
348 mark_buffer_dirty(bh);
349 brelse(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);
353 hpfs_brelse4(&qbh);
354 hpfs_mark_4buffers_dirty(&qbh1);
355 hpfs_brelse4(&qbh1);
356 qbh = qbh2;
357 set_last_pointer(i->i_sb, rd, dno);
358 dno = rdno;
359 d = rd;
360 goto go_up_a;
361}
362
363/*
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.
369 */
370
371int hpfs_add_dirent(struct inode *i, unsigned char *name, unsigned namelen,
372 struct hpfs_dirent *new_de, int cdepth)
373{
374 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
375 struct dnode *d;
376 struct hpfs_dirent *de, *de_end;
377 struct quad_buffer_head qbh;
378 dnode_secno dno;
379 int c;
380 int c1, c2 = 0;
381 dno = hpfs_inode->i_dno;
382 down:
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))) {
389 hpfs_brelse4(&qbh);
390 return -1;
391 }
392 if (c < 0) {
393 if (de->down) {
394 dno = de_down_pointer(de);
395 hpfs_brelse4(&qbh);
396 goto down;
397 }
398 break;
399 }
400 }
401 hpfs_brelse4(&qbh);
402 if (!cdepth) hpfs_lock_creation(i->i_sb);
403 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
404 c = 1;
405 goto ret;
406 }
407 i->i_version++;
408 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
409 ret:
410 if (!cdepth) hpfs_unlock_creation(i->i_sb);
411 return c;
412}
413
414/*
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)
417 */
418
419static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
420{
421 dnode_secno dno, ddno;
422 dnode_secno chk_up = to;
423 struct dnode *dnode;
424 struct quad_buffer_head qbh;
425 struct hpfs_dirent *de, *nde;
426 int a;
427 loff_t t;
428 int c1, c2 = 0;
429 dno = from;
430 while (1) {
431 if (hpfs_sb(i->i_sb)->sb_chk)
432 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
433 return 0;
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);
439 hpfs_brelse4(&qbh);
440 return 0;
441 }
442 chk_up = dno;
443 }
444 if (!(de = dnode_last_de(dnode))) {
445 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
446 hpfs_brelse4(&qbh);
447 return 0;
448 }
449 if (!de->down) break;
450 dno = de_down_pointer(de);
451 hpfs_brelse4(&qbh);
452 }
453 while (!(de = dnode_pre_last_de(dnode))) {
454 dnode_secno up = dnode->up;
455 hpfs_brelse4(&qbh);
456 hpfs_free_dnode(i->i_sb, dno);
457 i->i_size -= 2048;
458 i->i_blocks -= 4;
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);
464 hpfs_brelse4(&qbh);
465 return 0;
466 }
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);
470 hpfs_brelse4(&qbh);
471 return 0;
472 }
473 dnode->first_free -= 4;
474 de->length -= 4;
475 de->down = 0;
476 hpfs_mark_4buffers_dirty(&qbh);
477 dno = up;
478 }
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");
484 hpfs_brelse4(&qbh);
485 return 0;
486 }
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);
492 hpfs_brelse4(&qbh);
493 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
494 kfree(nde);
495 if (a) return 0;
496 return dno;
497}
498
499/*
500 * Check if a dnode is empty and delete it from the tree
501 * (chkdsk doesn't like empty dnodes)
502 */
503
504static void delete_empty_dnode(struct inode *i, dnode_secno dno)
505{
506 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
507 struct quad_buffer_head qbh;
508 struct dnode *dnode;
509 dnode_secno down, up, ndown;
510 int p;
511 struct hpfs_dirent *de;
512 int c1, c2 = 0;
513 try_it_again:
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;
520 up = dnode->up;
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);
525 goto end;
526 }
527 hpfs_brelse4(&qbh);
528 hpfs_free_dnode(i->i_sb, dno);
529 i->i_size -= 2048;
530 i->i_blocks -= 4;
531 if (root) {
532 struct fnode *fnode;
533 struct buffer_head *bh;
534 struct dnode *d1;
535 struct quad_buffer_head qbh1;
536 if (hpfs_sb(i->i_sb)->sb_chk) if (up != i->i_ino) {
537 hpfs_error(i->i_sb, "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08x", dno, up, i->i_ino);
538 return;
539 }
540 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
541 d1->up = up;
542 d1->root_dnode = 1;
543 hpfs_mark_4buffers_dirty(&qbh1);
544 hpfs_brelse4(&qbh1);
545 }
546 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
547 fnode->u.external[0].disk_secno = down;
548 mark_buffer_dirty(bh);
549 brelse(bh);
550 }
551 hpfs_inode->i_dno = down;
552 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
553 return;
554 }
555 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
556 p = 1;
557 de_end = dnode_end_de(dnode);
558 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
559 if (de->down) if (de_down_pointer(de) == dno) goto fnd;
560 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
561 goto end;
562 fnd:
563 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
564 if (!down) {
565 de->down = 0;
566 de->length -= 4;
567 dnode->first_free -= 4;
568 memmove(de_next_de(de), (char *)de_next_de(de) + 4,
569 (char *)dnode + dnode->first_free - (char *)de_next_de(de));
570 } else {
571 struct dnode *d1;
572 struct quad_buffer_head qbh1;
573 *(dnode_secno *) ((void *) de + de->length - 4) = down;
574 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
575 d1->up = up;
576 hpfs_mark_4buffers_dirty(&qbh1);
577 hpfs_brelse4(&qbh1);
578 }
579 }
580 } else {
581 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, dnode->first_free);
582 goto end;
583 }
584
585 if (!de->last) {
586 struct hpfs_dirent *de_next = de_next_de(de);
587 struct hpfs_dirent *de_cp;
588 struct dnode *d1;
589 struct quad_buffer_head qbh1;
590 if (!de_next->down) goto endm;
591 ndown = de_down_pointer(de_next);
592 if (!(de_cp = kmalloc(de->length, GFP_NOFS))) {
593 printk("HPFS: out of memory for dtree balancing\n");
594 goto endm;
595 }
596 memcpy(de_cp, de, de->length);
597 hpfs_delete_de(i->i_sb, dnode, de);
598 hpfs_mark_4buffers_dirty(&qbh);
599 hpfs_brelse4(&qbh);
600 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
601 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
602 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
603 d1->up = ndown;
604 hpfs_mark_4buffers_dirty(&qbh1);
605 hpfs_brelse4(&qbh1);
606 }
607 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
608 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
609 dno = up;
610 kfree(de_cp);
611 goto try_it_again;
612 } else {
613 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
614 struct hpfs_dirent *de_cp;
615 struct dnode *d1;
616 struct quad_buffer_head qbh1;
617 dnode_secno dlp;
618 if (!de_prev) {
619 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
620 hpfs_mark_4buffers_dirty(&qbh);
621 hpfs_brelse4(&qbh);
622 dno = up;
623 goto try_it_again;
624 }
625 if (!de_prev->down) goto endm;
626 ndown = de_down_pointer(de_prev);
627 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
628 struct hpfs_dirent *del = dnode_last_de(d1);
629 dlp = del->down ? de_down_pointer(del) : 0;
630 if (!dlp && down) {
631 if (d1->first_free > 2044) {
632 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
633 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
634 printk("HPFS: warning: terminating balancing operation\n");
635 }
636 hpfs_brelse4(&qbh1);
637 goto endm;
638 }
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: goin'on\n");
642 }
643 del->length += 4;
644 del->down = 1;
645 d1->first_free += 4;
646 }
647 if (dlp && !down) {
648 del->length -= 4;
649 del->down = 0;
650 d1->first_free -= 4;
651 } else if (down)
652 *(dnode_secno *) ((void *) del + del->length - 4) = down;
653 } else goto endm;
654 if (!(de_cp = kmalloc(de_prev->length, GFP_NOFS))) {
655 printk("HPFS: out of memory for dtree balancing\n");
656 hpfs_brelse4(&qbh1);
657 goto endm;
658 }
659 hpfs_mark_4buffers_dirty(&qbh1);
660 hpfs_brelse4(&qbh1);
661 memcpy(de_cp, de_prev, de_prev->length);
662 hpfs_delete_de(i->i_sb, dnode, de_prev);
663 if (!de_prev->down) {
664 de_prev->length += 4;
665 de_prev->down = 1;
666 dnode->first_free += 4;
667 }
668 *(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = ndown;
669 hpfs_mark_4buffers_dirty(&qbh);
670 hpfs_brelse4(&qbh);
671 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
672 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
673 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
674 d1->up = ndown;
675 hpfs_mark_4buffers_dirty(&qbh1);
676 hpfs_brelse4(&qbh1);
677 }
678 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
679 dno = up;
680 kfree(de_cp);
681 goto try_it_again;
682 }
683 endm:
684 hpfs_mark_4buffers_dirty(&qbh);
685 end:
686 hpfs_brelse4(&qbh);
687}
688
689
690/* Delete dirent from directory */
691
692int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
693 struct quad_buffer_head *qbh, int depth)
694{
695 struct dnode *dnode = qbh->data;
696 dnode_secno down = 0;
697 int lock = 0;
698 loff_t t;
699 if (de->first || de->last) {
700 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
701 hpfs_brelse4(qbh);
702 return 1;
703 }
704 if (de->down) down = de_down_pointer(de);
705 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
706 lock = 1;
707 hpfs_lock_creation(i->i_sb);
708 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
709 hpfs_brelse4(qbh);
710 hpfs_unlock_creation(i->i_sb);
711 return 2;
712 }
713 }
714 i->i_version++;
715 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
716 hpfs_delete_de(i->i_sb, dnode, de);
717 hpfs_mark_4buffers_dirty(qbh);
718 hpfs_brelse4(qbh);
719 if (down) {
720 dnode_secno a = move_to_top(i, down, dno);
721 for_all_poss(i, hpfs_pos_subst, 5, t);
722 if (a) delete_empty_dnode(i, a);
723 if (lock) hpfs_unlock_creation(i->i_sb);
724 return !a;
725 }
726 delete_empty_dnode(i, dno);
727 if (lock) hpfs_unlock_creation(i->i_sb);
728 return 0;
729}
730
731void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
732 int *n_subdirs, int *n_items)
733{
734 struct dnode *dnode;
735 struct quad_buffer_head qbh;
736 struct hpfs_dirent *de;
737 dnode_secno ptr, odno = 0;
738 int c1, c2 = 0;
739 int d1, d2 = 0;
740 go_down:
741 if (n_dnodes) (*n_dnodes)++;
742 if (hpfs_sb(s)->sb_chk)
743 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
744 ptr = 0;
745 go_up:
746 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
747 if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && dnode->up != odno)
748 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up);
749 de = dnode_first_de(dnode);
750 if (ptr) while(1) {
751 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
752 if (de->last) {
753 hpfs_brelse4(&qbh);
754 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
755 ptr, dno, odno);
756 return;
757 }
758 de = de_next_de(de);
759 }
760 next_de:
761 if (de->down) {
762 odno = dno;
763 dno = de_down_pointer(de);
764 hpfs_brelse4(&qbh);
765 goto go_down;
766 }
767 process_de:
768 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
769 if (!de->first && !de->last && n_items) (*n_items)++;
770 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
771 ptr = dno;
772 dno = dnode->up;
773 if (dnode->root_dnode) {
774 hpfs_brelse4(&qbh);
775 return;
776 }
777 hpfs_brelse4(&qbh);
778 if (hpfs_sb(s)->sb_chk)
779 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
780 odno = -1;
781 goto go_up;
782}
783
784static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
785 struct quad_buffer_head *qbh, struct dnode **dn)
786{
787 int i;
788 struct hpfs_dirent *de, *de_end;
789 struct dnode *dnode;
790 dnode = hpfs_map_dnode(s, dno, qbh);
791 if (!dnode) return NULL;
792 if (dn) *dn=dnode;
793 de = dnode_first_de(dnode);
794 de_end = dnode_end_de(dnode);
795 for (i = 1; de < de_end; i++, de = de_next_de(de)) {
796 if (i == n) {
797 return de;
798 }
799 if (de->last) break;
800 }
801 hpfs_brelse4(qbh);
802 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
803 return NULL;
804}
805
806dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
807{
808 struct quad_buffer_head qbh;
809 dnode_secno d = dno;
810 dnode_secno up = 0;
811 struct hpfs_dirent *de;
812 int c1, c2 = 0;
813
814 again:
815 if (hpfs_sb(s)->sb_chk)
816 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
817 return d;
818 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
819 if (hpfs_sb(s)->sb_chk)
820 if (up && ((struct dnode *)qbh.data)->up != up)
821 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);
822 if (!de->down) {
823 hpfs_brelse4(&qbh);
824 return d;
825 }
826 up = d;
827 d = de_down_pointer(de);
828 hpfs_brelse4(&qbh);
829 goto again;
830}
831
832struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
833 struct quad_buffer_head *qbh)
834{
835 loff_t pos;
836 unsigned c;
837 dnode_secno dno;
838 struct hpfs_dirent *de, *d;
839 struct hpfs_dirent *up_de;
840 struct hpfs_dirent *end_up_de;
841 struct dnode *dnode;
842 struct dnode *up_dnode;
843 struct quad_buffer_head qbh0;
844
845 pos = *posp;
846 dno = pos >> 6 << 2;
847 pos &= 077;
848 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
849 goto bail;
850
851 /* Going to the next dirent */
852 if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
853 if (!(++*posp & 077)) {
854 hpfs_error(inode->i_sb, "map_pos_dirent: pos crossed dnode boundary; pos = %08x", *posp);
855 goto bail;
856 }
857 /* We're going down the tree */
858 if (d->down) {
859 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
860 }
861
862 return de;
863 }
864
865 /* Going up */
866 if (dnode->root_dnode) goto bail;
867
868 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0)))
869 goto bail;
870
871 end_up_de = dnode_end_de(up_dnode);
872 c = 0;
873 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
874 up_de = de_next_de(up_de)) {
875 if (!(++c & 077)) hpfs_error(inode->i_sb,
876 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up);
877 if (up_de->down && de_down_pointer(up_de) == dno) {
878 *posp = ((loff_t) dnode->up << 4) + c;
879 hpfs_brelse4(&qbh0);
880 return de;
881 }
882 }
883
884 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
885 dno, dnode->up);
886 hpfs_brelse4(&qbh0);
887
888 bail:
889 *posp = 12;
890 return de;
891}
892
893/* Find a dirent in tree */
894
895struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, char *name, unsigned len,
896 dnode_secno *dd, struct quad_buffer_head *qbh)
897{
898 struct dnode *dnode;
899 struct hpfs_dirent *de;
900 struct hpfs_dirent *de_end;
901 int c1, c2 = 0;
902
903 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
904 again:
905 if (hpfs_sb(inode->i_sb)->sb_chk)
906 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
907 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
908
909 de_end = dnode_end_de(dnode);
910 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
911 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
912 if (!t) {
913 if (dd) *dd = dno;
914 return de;
915 }
916 if (t < 0) {
917 if (de->down) {
918 dno = de_down_pointer(de);
919 hpfs_brelse4(qbh);
920 goto again;
921 }
922 break;
923 }
924 }
925 hpfs_brelse4(qbh);
926 return NULL;
927}
928
929/*
930 * Remove empty directory. In normal cases it is only one dnode with two
931 * entries, but we must handle also such obscure cases when it's a tree
932 * of empty dnodes.
933 */
934
935void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
936{
937 struct quad_buffer_head qbh;
938 struct dnode *dnode;
939 struct hpfs_dirent *de;
940 dnode_secno d1, d2, rdno = dno;
941 while (1) {
942 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
943 de = dnode_first_de(dnode);
944 if (de->last) {
945 if (de->down) d1 = de_down_pointer(de);
946 else goto error;
947 hpfs_brelse4(&qbh);
948 hpfs_free_dnode(s, dno);
949 dno = d1;
950 } else break;
951 }
952 if (!de->first) goto error;
953 d1 = de->down ? de_down_pointer(de) : 0;
954 de = de_next_de(de);
955 if (!de->last) goto error;
956 d2 = de->down ? de_down_pointer(de) : 0;
957 hpfs_brelse4(&qbh);
958 hpfs_free_dnode(s, dno);
959 do {
960 while (d1) {
961 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
962 de = dnode_first_de(dnode);
963 if (!de->last) goto error;
964 d1 = de->down ? de_down_pointer(de) : 0;
965 hpfs_brelse4(&qbh);
966 hpfs_free_dnode(s, dno);
967 }
968 d1 = d2;
969 d2 = 0;
970 } while (d1);
971 return;
972 error:
973 hpfs_brelse4(&qbh);
974 hpfs_free_dnode(s, dno);
975 hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
976}
977
978/*
979 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
980 * a help for searching.
981 */
982
983struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
984 struct fnode *f, struct quad_buffer_head *qbh)
985{
986 char *name1;
987 char *name2;
988 int name1len, name2len;
989 struct dnode *d;
990 dnode_secno dno, downd;
991 struct fnode *upf;
992 struct buffer_head *bh;
993 struct hpfs_dirent *de, *de_end;
994 int c;
995 int c1, c2 = 0;
996 int d1, d2 = 0;
997 name1 = f->name;
998 if (!(name2 = kmalloc(256, GFP_NOFS))) {
999 printk("HPFS: out of memory, can't map dirent\n");
1000 return NULL;
1001 }
1002 if (f->len <= 15)
1003 memcpy(name2, name1, name1len = name2len = f->len);
1004 else {
1005 memcpy(name2, name1, 15);
1006 memset(name2 + 15, 0xff, 256 - 15);
1007 /*name2[15] = 0xff;*/
1008 name1len = 15; name2len = 256;
1009 }
1010 if (!(upf = hpfs_map_fnode(s, f->up, &bh))) {
1011 kfree(name2);
1012 return NULL;
1013 }
1014 if (!upf->dirflag) {
1015 brelse(bh);
1016 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up);
1017 kfree(name2);
1018 return NULL;
1019 }
1020 dno = upf->u.external[0].disk_secno;
1021 brelse(bh);
1022 go_down:
1023 downd = 0;
1024 go_up:
1025 if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1026 kfree(name2);
1027 return NULL;
1028 }
1029 de_end = dnode_end_de(d);
1030 de = dnode_first_de(d);
1031 if (downd) {
1032 while (de < de_end) {
1033 if (de->down) if (de_down_pointer(de) == downd) goto f;
1034 de = de_next_de(de);
1035 }
1036 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1037 hpfs_brelse4(qbh);
1038 kfree(name2);
1039 return NULL;
1040 }
1041 next_de:
1042 if (de->fnode == fno) {
1043 kfree(name2);
1044 return de;
1045 }
1046 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1047 if (c < 0 && de->down) {
1048 dno = de_down_pointer(de);
1049 hpfs_brelse4(qbh);
1050 if (hpfs_sb(s)->sb_chk)
1051 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1052 kfree(name2);
1053 return NULL;
1054 }
1055 goto go_down;
1056 }
1057 f:
1058 if (de->fnode == fno) {
1059 kfree(name2);
1060 return de;
1061 }
1062 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1063 if (c < 0 && !de->last) goto not_found;
1064 if ((de = de_next_de(de)) < de_end) goto next_de;
1065 if (d->root_dnode) goto not_found;
1066 downd = dno;
1067 dno = d->up;
1068 hpfs_brelse4(qbh);
1069 if (hpfs_sb(s)->sb_chk)
1070 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1071 kfree(name2);
1072 return NULL;
1073 }
1074 goto go_up;
1075 not_found:
1076 hpfs_brelse4(qbh);
1077 hpfs_error(s, "dirent for fnode %08x not found", fno);
1078 kfree(name2);
1079 return NULL;
1080}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-02 06:24:20 -0400