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