hpfs: don't bother with the i_version counter or f_version
[muen/linux.git] / fs / hpfs / dnode.c
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  *  linux/fs/hpfs/dnode.c
4  *
5  *  Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
6  *
7  *  handling directory dnode tree - adding, deleteing & searching for dirents
8  */
9
10 #include "hpfs_fn.h"
11
12 static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
13 {
14         struct hpfs_dirent *de;
15         struct hpfs_dirent *de_end = dnode_end_de(d);
16         int i = 1;
17         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
18                 if (de == fde) return ((loff_t) le32_to_cpu(d->self) << 4) | (loff_t)i;
19                 i++;
20         }
21         pr_info("%s(): not_found\n", __func__);
22         return ((loff_t)le32_to_cpu(d->self) << 4) | (loff_t)1;
23 }
24
25 int hpfs_add_pos(struct inode *inode, loff_t *pos)
26 {
27         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
28         int i = 0;
29         loff_t **ppos;
30
31         if (hpfs_inode->i_rddir_off)
32                 for (; hpfs_inode->i_rddir_off[i]; i++)
33                         if (hpfs_inode->i_rddir_off[i] == pos)
34                                 return 0;
35         if (!(i&0x0f)) {
36                 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
37                         pr_err("out of memory for position list\n");
38                         return -ENOMEM;
39                 }
40                 if (hpfs_inode->i_rddir_off) {
41                         memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
42                         kfree(hpfs_inode->i_rddir_off);
43                 }
44                 hpfs_inode->i_rddir_off = ppos;
45         }
46         hpfs_inode->i_rddir_off[i] = pos;
47         hpfs_inode->i_rddir_off[i + 1] = NULL;
48         return 0;
49 }
50
51 void hpfs_del_pos(struct inode *inode, loff_t *pos)
52 {
53         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
54         loff_t **i, **j;
55
56         if (!hpfs_inode->i_rddir_off) goto not_f;
57         for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
58         goto not_f;
59         fnd:
60         for (j = i + 1; *j; j++) ;
61         *i = *(j - 1);
62         *(j - 1) = NULL;
63         if (j - 1 == hpfs_inode->i_rddir_off) {
64                 kfree(hpfs_inode->i_rddir_off);
65                 hpfs_inode->i_rddir_off = NULL;
66         }
67         return;
68         not_f:
69         /*pr_warn("position pointer %p->%08x not found\n",
70                   pos, (int)*pos);*/
71         return;
72 }
73
74 static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
75                          loff_t p1, loff_t p2)
76 {
77         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
78         loff_t **i;
79
80         if (!hpfs_inode->i_rddir_off) return;
81         for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
82         return;
83 }
84
85 static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
86 {
87         if (*p == f) *p = t;
88 }
89
90 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
91 {
92         if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
93 }*/
94
95 static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
96 {
97         if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
98                 int n = (*p & 0x3f) + c;
99                 if (n > 0x3f)
100                         pr_err("%s(): %08x + %d\n",
101                                 __func__, (int)*p, (int)c >> 8);
102                 else
103                         *p = (*p & ~0x3f) | n;
104         }
105 }
106
107 static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
108 {
109         if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
110                 int n = (*p & 0x3f) - c;
111                 if (n < 1)
112                         pr_err("%s(): %08x - %d\n",
113                                 __func__, (int)*p, (int)c >> 8);
114                 else
115                         *p = (*p & ~0x3f) | n;
116         }
117 }
118
119 static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
120 {
121         struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
122         de_end = dnode_end_de(d);
123         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
124                 deee = dee; dee = de;
125         }       
126         return deee;
127 }
128
129 static struct hpfs_dirent *dnode_last_de(struct dnode *d)
130 {
131         struct hpfs_dirent *de, *de_end, *dee = NULL;
132         de_end = dnode_end_de(d);
133         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
134                 dee = de;
135         }       
136         return dee;
137 }
138
139 static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
140 {
141         struct hpfs_dirent *de;
142         if (!(de = dnode_last_de(d))) {
143                 hpfs_error(s, "set_last_pointer: empty dnode %08x", le32_to_cpu(d->self));
144                 return;
145         }
146         if (hpfs_sb(s)->sb_chk) {
147                 if (de->down) {
148                         hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
149                                 le32_to_cpu(d->self), de_down_pointer(de));
150                         return;
151                 }
152                 if (le16_to_cpu(de->length) != 32) {
153                         hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", le32_to_cpu(d->self));
154                         return;
155                 }
156         }
157         if (ptr) {
158                 le32_add_cpu(&d->first_free, 4);
159                 if (le32_to_cpu(d->first_free) > 2048) {
160                         hpfs_error(s, "set_last_pointer: too long dnode %08x", le32_to_cpu(d->self));
161                         le32_add_cpu(&d->first_free, -4);
162                         return;
163                 }
164                 de->length = cpu_to_le16(36);
165                 de->down = 1;
166                 *(__le32 *)((char *)de + 32) = cpu_to_le32(ptr);
167         }
168 }
169
170 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
171
172 struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d,
173                                 const unsigned char *name,
174                                 unsigned namelen, secno down_ptr)
175 {
176         struct hpfs_dirent *de;
177         struct hpfs_dirent *de_end = dnode_end_de(d);
178         unsigned d_size = de_size(namelen, down_ptr);
179         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
180                 int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
181                 if (!c) {
182                         hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, le32_to_cpu(d->self));
183                         return NULL;
184                 }
185                 if (c < 0) break;
186         }
187         memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
188         memset(de, 0, d_size);
189         if (down_ptr) {
190                 *(__le32 *)((char *)de + d_size - 4) = cpu_to_le32(down_ptr);
191                 de->down = 1;
192         }
193         de->length = cpu_to_le16(d_size);
194         de->not_8x3 = hpfs_is_name_long(name, namelen);
195         de->namelen = namelen;
196         memcpy(de->name, name, namelen);
197         le32_add_cpu(&d->first_free, d_size);
198         return de;
199 }
200
201 /* Delete dirent and don't care about its subtree */
202
203 static void hpfs_delete_de(struct super_block *s, struct dnode *d,
204                            struct hpfs_dirent *de)
205 {
206         if (de->last) {
207                 hpfs_error(s, "attempt to delete last dirent in dnode %08x", le32_to_cpu(d->self));
208                 return;
209         }
210         d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) - le16_to_cpu(de->length));
211         memmove(de, de_next_de(de), le32_to_cpu(d->first_free) + (char *)d - (char *)de);
212 }
213
214 static void fix_up_ptrs(struct super_block *s, struct dnode *d)
215 {
216         struct hpfs_dirent *de;
217         struct hpfs_dirent *de_end = dnode_end_de(d);
218         dnode_secno dno = le32_to_cpu(d->self);
219         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
220                 if (de->down) {
221                         struct quad_buffer_head qbh;
222                         struct dnode *dd;
223                         if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
224                                 if (le32_to_cpu(dd->up) != dno || dd->root_dnode) {
225                                         dd->up = cpu_to_le32(dno);
226                                         dd->root_dnode = 0;
227                                         hpfs_mark_4buffers_dirty(&qbh);
228                                 }
229                                 hpfs_brelse4(&qbh);
230                         }
231                 }
232 }
233
234 /* Add an entry to dnode and do dnode splitting if required */
235
236 static int hpfs_add_to_dnode(struct inode *i, dnode_secno dno,
237                              const unsigned char *name, unsigned namelen,
238                              struct hpfs_dirent *new_de, dnode_secno down_ptr)
239 {
240         struct quad_buffer_head qbh, qbh1, qbh2;
241         struct dnode *d, *ad, *rd, *nd = NULL;
242         dnode_secno adno, rdno;
243         struct hpfs_dirent *de;
244         struct hpfs_dirent nde;
245         unsigned char *nname;
246         int h;
247         int pos;
248         struct buffer_head *bh;
249         struct fnode *fnode;
250         int c1, c2 = 0;
251         if (!(nname = kmalloc(256, GFP_NOFS))) {
252                 pr_err("out of memory, can't add to dnode\n");
253                 return 1;
254         }
255         go_up:
256         if (namelen >= 256) {
257                 hpfs_error(i->i_sb, "%s(): namelen == %d", __func__, namelen);
258                 kfree(nd);
259                 kfree(nname);
260                 return 1;
261         }
262         if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
263                 kfree(nd);
264                 kfree(nname);
265                 return 1;
266         }
267         go_up_a:
268         if (hpfs_sb(i->i_sb)->sb_chk)
269                 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
270                         hpfs_brelse4(&qbh);
271                         kfree(nd);
272                         kfree(nname);
273                         return 1;
274                 }
275         if (le32_to_cpu(d->first_free) + de_size(namelen, down_ptr) <= 2048) {
276                 loff_t t;
277                 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
278                 t = get_pos(d, de);
279                 for_all_poss(i, hpfs_pos_ins, t, 1);
280                 for_all_poss(i, hpfs_pos_subst, 4, t);
281                 for_all_poss(i, hpfs_pos_subst, 5, t + 1);
282                 hpfs_mark_4buffers_dirty(&qbh);
283                 hpfs_brelse4(&qbh);
284                 kfree(nd);
285                 kfree(nname);
286                 return 0;
287         }
288         if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
289                 /* 0x924 is a max size of dnode after adding a dirent with
290                    max name length. We alloc this only once. There must
291                    not be any error while splitting dnodes, otherwise the
292                    whole directory, not only file we're adding, would
293                    be lost. */
294                 pr_err("out of memory for dnode splitting\n");
295                 hpfs_brelse4(&qbh);
296                 kfree(nname);
297                 return 1;
298         }       
299         memcpy(nd, d, le32_to_cpu(d->first_free));
300         copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
301         for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
302         h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
303         if (!(ad = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &adno, &qbh1))) {
304                 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
305                 hpfs_brelse4(&qbh);
306                 kfree(nd);
307                 kfree(nname);
308                 return 1;
309         }
310         i->i_size += 2048;
311         i->i_blocks += 4;
312         pos = 1;
313         for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
314                 copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
315                 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
316                 pos++;
317         }
318         copy_de(new_de = &nde, de);
319         memcpy(nname, de->name, de->namelen);
320         name = nname;
321         namelen = de->namelen;
322         for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
323         down_ptr = adno;
324         set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
325         de = de_next_de(de);
326         memmove((char *)nd + 20, de, le32_to_cpu(nd->first_free) + (char *)nd - (char *)de);
327         le32_add_cpu(&nd->first_free, -((char *)de - (char *)nd - 20));
328         memcpy(d, nd, le32_to_cpu(nd->first_free));
329         for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
330         fix_up_ptrs(i->i_sb, ad);
331         if (!d->root_dnode) {
332                 ad->up = d->up;
333                 dno = le32_to_cpu(ad->up);
334                 hpfs_mark_4buffers_dirty(&qbh);
335                 hpfs_brelse4(&qbh);
336                 hpfs_mark_4buffers_dirty(&qbh1);
337                 hpfs_brelse4(&qbh1);
338                 goto go_up;
339         }
340         if (!(rd = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &rdno, &qbh2))) {
341                 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
342                 hpfs_brelse4(&qbh);
343                 hpfs_brelse4(&qbh1);
344                 kfree(nd);
345                 kfree(nname);
346                 return 1;
347         }
348         i->i_size += 2048;
349         i->i_blocks += 4;
350         rd->root_dnode = 1;
351         rd->up = d->up;
352         if (!(fnode = hpfs_map_fnode(i->i_sb, le32_to_cpu(d->up), &bh))) {
353                 hpfs_free_dnode(i->i_sb, rdno);
354                 hpfs_brelse4(&qbh);
355                 hpfs_brelse4(&qbh1);
356                 hpfs_brelse4(&qbh2);
357                 kfree(nd);
358                 kfree(nname);
359                 return 1;
360         }
361         fnode->u.external[0].disk_secno = cpu_to_le32(rdno);
362         mark_buffer_dirty(bh);
363         brelse(bh);
364         hpfs_i(i)->i_dno = rdno;
365         d->up = ad->up = cpu_to_le32(rdno);
366         d->root_dnode = ad->root_dnode = 0;
367         hpfs_mark_4buffers_dirty(&qbh);
368         hpfs_brelse4(&qbh);
369         hpfs_mark_4buffers_dirty(&qbh1);
370         hpfs_brelse4(&qbh1);
371         qbh = qbh2;
372         set_last_pointer(i->i_sb, rd, dno);
373         dno = rdno;
374         d = rd;
375         goto go_up_a;
376 }
377
378 /*
379  * Add an entry to directory btree.
380  * I hate such crazy directory structure.
381  * It's easy to read but terrible to write.
382  * I wrote this directory code 4 times.
383  * I hope, now it's finally bug-free.
384  */
385
386 int hpfs_add_dirent(struct inode *i,
387                     const unsigned char *name, unsigned namelen,
388                     struct hpfs_dirent *new_de)
389 {
390         struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
391         struct dnode *d;
392         struct hpfs_dirent *de, *de_end;
393         struct quad_buffer_head qbh;
394         dnode_secno dno;
395         int c;
396         int c1, c2 = 0;
397         dno = hpfs_inode->i_dno;
398         down:
399         if (hpfs_sb(i->i_sb)->sb_chk)
400                 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
401         if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
402         de_end = dnode_end_de(d);
403         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
404                 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
405                         hpfs_brelse4(&qbh);
406                         return -1;
407                 }       
408                 if (c < 0) {
409                         if (de->down) {
410                                 dno = de_down_pointer(de);
411                                 hpfs_brelse4(&qbh);
412                                 goto down;
413                         }
414                         break;
415                 }
416         }
417         hpfs_brelse4(&qbh);
418         if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
419                 c = 1;
420                 goto ret;
421         }       
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
432 static 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
517 static 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
710 int 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         for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
729         hpfs_delete_de(i->i_sb, dnode, de);
730         hpfs_mark_4buffers_dirty(qbh);
731         hpfs_brelse4(qbh);
732         if (down) {
733                 dnode_secno a = move_to_top(i, down, dno);
734                 for_all_poss(i, hpfs_pos_subst, 5, t);
735                 if (a) delete_empty_dnode(i, a);
736                 return !a;
737         }
738         delete_empty_dnode(i, dno);
739         return 0;
740 }
741
742 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
743                        int *n_subdirs, int *n_items)
744 {
745         struct dnode *dnode;
746         struct quad_buffer_head qbh;
747         struct hpfs_dirent *de;
748         dnode_secno ptr, odno = 0;
749         int c1, c2 = 0;
750         int d1, d2 = 0;
751         go_down:
752         if (n_dnodes) (*n_dnodes)++;
753         if (hpfs_sb(s)->sb_chk)
754                 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
755         ptr = 0;
756         go_up:
757         if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
758         if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && le32_to_cpu(dnode->up) != odno)
759                 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, le32_to_cpu(dnode->up));
760         de = dnode_first_de(dnode);
761         if (ptr) while(1) {
762                 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
763                 if (de->last) {
764                         hpfs_brelse4(&qbh);
765                         hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
766                                 ptr, dno, odno);
767                         return;
768                 }
769                 de = de_next_de(de);
770         }
771         next_de:
772         if (de->down) {
773                 odno = dno;
774                 dno = de_down_pointer(de);
775                 hpfs_brelse4(&qbh);
776                 goto go_down;
777         }
778         process_de:
779         if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
780         if (!de->first && !de->last && n_items) (*n_items)++;
781         if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
782         ptr = dno;
783         dno = le32_to_cpu(dnode->up);
784         if (dnode->root_dnode) {
785                 hpfs_brelse4(&qbh);
786                 return;
787         }
788         hpfs_brelse4(&qbh);
789         if (hpfs_sb(s)->sb_chk)
790                 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
791         odno = -1;
792         goto go_up;
793 }
794
795 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
796                                           struct quad_buffer_head *qbh, struct dnode **dn)
797 {
798         int i;
799         struct hpfs_dirent *de, *de_end;
800         struct dnode *dnode;
801         dnode = hpfs_map_dnode(s, dno, qbh);
802         if (!dnode) return NULL;
803         if (dn) *dn=dnode;
804         de = dnode_first_de(dnode);
805         de_end = dnode_end_de(dnode);
806         for (i = 1; de < de_end; i++, de = de_next_de(de)) {
807                 if (i == n) {
808                         return de;
809                 }       
810                 if (de->last) break;
811         }
812         hpfs_brelse4(qbh);
813         hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
814         return NULL;
815 }
816
817 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
818 {
819         struct quad_buffer_head qbh;
820         dnode_secno d = dno;
821         dnode_secno up = 0;
822         struct hpfs_dirent *de;
823         int c1, c2 = 0;
824
825         again:
826         if (hpfs_sb(s)->sb_chk)
827                 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
828                         return d;
829         if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
830         if (hpfs_sb(s)->sb_chk)
831                 if (up && le32_to_cpu(((struct dnode *)qbh.data)->up) != up)
832                         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));
833         if (!de->down) {
834                 hpfs_brelse4(&qbh);
835                 return d;
836         }
837         up = d;
838         d = de_down_pointer(de);
839         hpfs_brelse4(&qbh);
840         goto again;
841 }
842
843 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
844                                    struct quad_buffer_head *qbh)
845 {
846         loff_t pos;
847         unsigned c;
848         dnode_secno dno;
849         struct hpfs_dirent *de, *d;
850         struct hpfs_dirent *up_de;
851         struct hpfs_dirent *end_up_de;
852         struct dnode *dnode;
853         struct dnode *up_dnode;
854         struct quad_buffer_head qbh0;
855
856         pos = *posp;
857         dno = pos >> 6 << 2;
858         pos &= 077;
859         if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
860                 goto bail;
861
862         /* Going to the next dirent */
863         if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
864                 if (!(++*posp & 077)) {
865                         hpfs_error(inode->i_sb,
866                                 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
867                                 (unsigned long long)*posp);
868                         goto bail;
869                 }
870                 /* We're going down the tree */
871                 if (d->down) {
872                         *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
873                 }
874         
875                 return de;
876         }
877
878         /* Going up */
879         if (dnode->root_dnode) goto bail;
880
881         if (!(up_dnode = hpfs_map_dnode(inode->i_sb, le32_to_cpu(dnode->up), &qbh0)))
882                 goto bail;
883
884         end_up_de = dnode_end_de(up_dnode);
885         c = 0;
886         for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
887              up_de = de_next_de(up_de)) {
888                 if (!(++c & 077)) hpfs_error(inode->i_sb,
889                         "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode->up));
890                 if (up_de->down && de_down_pointer(up_de) == dno) {
891                         *posp = ((loff_t) le32_to_cpu(dnode->up) << 4) + c;
892                         hpfs_brelse4(&qbh0);
893                         return de;
894                 }
895         }
896         
897         hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
898                 dno, le32_to_cpu(dnode->up));
899         hpfs_brelse4(&qbh0);
900         
901         bail:
902         *posp = 12;
903         return de;
904 }
905
906 /* Find a dirent in tree */
907
908 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
909                                const unsigned char *name, unsigned len,
910                                dnode_secno *dd, struct quad_buffer_head *qbh)
911 {
912         struct dnode *dnode;
913         struct hpfs_dirent *de;
914         struct hpfs_dirent *de_end;
915         int c1, c2 = 0;
916
917         if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
918         again:
919         if (hpfs_sb(inode->i_sb)->sb_chk)
920                 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
921         if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
922         
923         de_end = dnode_end_de(dnode);
924         for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
925                 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
926                 if (!t) {
927                         if (dd) *dd = dno;
928                         return de;
929                 }
930                 if (t < 0) {
931                         if (de->down) {
932                                 dno = de_down_pointer(de);
933                                 hpfs_brelse4(qbh);
934                                 goto again;
935                         }
936                 break;
937                 }
938         }
939         hpfs_brelse4(qbh);
940         return NULL;
941 }
942
943 /*
944  * Remove empty directory. In normal cases it is only one dnode with two
945  * entries, but we must handle also such obscure cases when it's a tree
946  * of empty dnodes.
947  */
948
949 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
950 {
951         struct quad_buffer_head qbh;
952         struct dnode *dnode;
953         struct hpfs_dirent *de;
954         dnode_secno d1, d2, rdno = dno;
955         while (1) {
956                 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
957                 de = dnode_first_de(dnode);
958                 if (de->last) {
959                         if (de->down) d1 = de_down_pointer(de);
960                         else goto error;
961                         hpfs_brelse4(&qbh);
962                         hpfs_free_dnode(s, dno);
963                         dno = d1;
964                 } else break;
965         }
966         if (!de->first) goto error;
967         d1 = de->down ? de_down_pointer(de) : 0;
968         de = de_next_de(de);
969         if (!de->last) goto error;
970         d2 = de->down ? de_down_pointer(de) : 0;
971         hpfs_brelse4(&qbh);
972         hpfs_free_dnode(s, dno);
973         do {
974                 while (d1) {
975                         if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
976                         de = dnode_first_de(dnode);
977                         if (!de->last) goto error;
978                         d1 = de->down ? de_down_pointer(de) : 0;
979                         hpfs_brelse4(&qbh);
980                         hpfs_free_dnode(s, dno);
981                 }
982                 d1 = d2;
983                 d2 = 0;
984         } while (d1);
985         return;
986         error:
987         hpfs_brelse4(&qbh);
988         hpfs_free_dnode(s, dno);
989         hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
990 }
991
992 /* 
993  * Find dirent for specified fnode. Use truncated 15-char name in fnode as
994  * a help for searching.
995  */
996
997 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
998                                      struct fnode *f, struct quad_buffer_head *qbh)
999 {
1000         unsigned char *name1;
1001         unsigned char *name2;
1002         int name1len, name2len;
1003         struct dnode *d;
1004         dnode_secno dno, downd;
1005         struct fnode *upf;
1006         struct buffer_head *bh;
1007         struct hpfs_dirent *de, *de_end;
1008         int c;
1009         int c1, c2 = 0;
1010         int d1, d2 = 0;
1011         name1 = f->name;
1012         if (!(name2 = kmalloc(256, GFP_NOFS))) {
1013                 pr_err("out of memory, can't map dirent\n");
1014                 return NULL;
1015         }
1016         if (f->len <= 15)
1017                 memcpy(name2, name1, name1len = name2len = f->len);
1018         else {
1019                 memcpy(name2, name1, 15);
1020                 memset(name2 + 15, 0xff, 256 - 15);
1021                 /*name2[15] = 0xff;*/
1022                 name1len = 15; name2len = 256;
1023         }
1024         if (!(upf = hpfs_map_fnode(s, le32_to_cpu(f->up), &bh))) {
1025                 kfree(name2);
1026                 return NULL;
1027         }       
1028         if (!fnode_is_dir(upf)) {
1029                 brelse(bh);
1030                 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, le32_to_cpu(f->up));
1031                 kfree(name2);
1032                 return NULL;
1033         }
1034         dno = le32_to_cpu(upf->u.external[0].disk_secno);
1035         brelse(bh);
1036         go_down:
1037         downd = 0;
1038         go_up:
1039         if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1040                 kfree(name2);
1041                 return NULL;
1042         }
1043         de_end = dnode_end_de(d);
1044         de = dnode_first_de(d);
1045         if (downd) {
1046                 while (de < de_end) {
1047                         if (de->down) if (de_down_pointer(de) == downd) goto f;
1048                         de = de_next_de(de);
1049                 }
1050                 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1051                 hpfs_brelse4(qbh);
1052                 kfree(name2);
1053                 return NULL;
1054         }
1055         next_de:
1056         if (le32_to_cpu(de->fnode) == fno) {
1057                 kfree(name2);
1058                 return de;
1059         }
1060         c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1061         if (c < 0 && de->down) {
1062                 dno = de_down_pointer(de);
1063                 hpfs_brelse4(qbh);
1064                 if (hpfs_sb(s)->sb_chk)
1065                         if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1066                                 kfree(name2);
1067                                 return NULL;
1068                 }
1069                 goto go_down;
1070         }
1071         f:
1072         if (le32_to_cpu(de->fnode) == fno) {
1073                 kfree(name2);
1074                 return de;
1075         }
1076         c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1077         if (c < 0 && !de->last) goto not_found;
1078         if ((de = de_next_de(de)) < de_end) goto next_de;
1079         if (d->root_dnode) goto not_found;
1080         downd = dno;
1081         dno = le32_to_cpu(d->up);
1082         hpfs_brelse4(qbh);
1083         if (hpfs_sb(s)->sb_chk)
1084                 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1085                         kfree(name2);
1086                         return NULL;
1087                 }
1088         goto go_up;
1089         not_found:
1090         hpfs_brelse4(qbh);
1091         hpfs_error(s, "dirent for fnode %08x not found", fno);
1092         kfree(name2);
1093         return NULL;
1094 }