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