3b834563b1f161352806249f0ef62b3e552ecee6
[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         i->i_version++;
423         c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
424         ret:
425         return c;
426 }
427
428 /* 
429  * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
430  * Return the dnode we moved from (to be checked later if it's empty)
431  */
432
433 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
434 {
435         dnode_secno dno, ddno;
436         dnode_secno chk_up = to;
437         struct dnode *dnode;
438         struct quad_buffer_head qbh;
439         struct hpfs_dirent *de, *nde;
440         int a;
441         loff_t t;
442         int c1, c2 = 0;
443         dno = from;
444         while (1) {
445                 if (hpfs_sb(i->i_sb)->sb_chk)
446                         if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
447                                 return 0;
448                 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
449                 if (hpfs_sb(i->i_sb)->sb_chk) {
450                         if (le32_to_cpu(dnode->up) != chk_up) {
451                                 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
452                                         dno, chk_up, le32_to_cpu(dnode->up));
453                                 hpfs_brelse4(&qbh);
454                                 return 0;
455                         }
456                         chk_up = dno;
457                 }
458                 if (!(de = dnode_last_de(dnode))) {
459                         hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
460                         hpfs_brelse4(&qbh);
461                         return 0;
462                 }
463                 if (!de->down) break;
464                 dno = de_down_pointer(de);
465                 hpfs_brelse4(&qbh);
466         }
467         while (!(de = dnode_pre_last_de(dnode))) {
468                 dnode_secno up = le32_to_cpu(dnode->up);
469                 hpfs_brelse4(&qbh);
470                 hpfs_free_dnode(i->i_sb, dno);
471                 i->i_size -= 2048;
472                 i->i_blocks -= 4;
473                 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
474                 if (up == to) return to;
475                 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
476                 if (dnode->root_dnode) {
477                         hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
478                         hpfs_brelse4(&qbh);
479                         return 0;
480                 }
481                 de = dnode_last_de(dnode);
482                 if (!de || !de->down) {
483                         hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
484                         hpfs_brelse4(&qbh);
485                         return 0;
486                 }
487                 le32_add_cpu(&dnode->first_free, -4);
488                 le16_add_cpu(&de->length, -4);
489                 de->down = 0;
490                 hpfs_mark_4buffers_dirty(&qbh);
491                 dno = up;
492         }
493         t = get_pos(dnode, de);
494         for_all_poss(i, hpfs_pos_subst, t, 4);
495         for_all_poss(i, hpfs_pos_subst, t + 1, 5);
496         if (!(nde = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
497                 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
498                 hpfs_brelse4(&qbh);
499                 return 0;
500         }
501         memcpy(nde, de, le16_to_cpu(de->length));
502         ddno = de->down ? de_down_pointer(de) : 0;
503         hpfs_delete_de(i->i_sb, dnode, de);
504         set_last_pointer(i->i_sb, dnode, ddno);
505         hpfs_mark_4buffers_dirty(&qbh);
506         hpfs_brelse4(&qbh);
507         a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
508         kfree(nde);
509         if (a) return 0;
510         return dno;
511 }
512
513 /* 
514  * Check if a dnode is empty and delete it from the tree
515  * (chkdsk doesn't like empty dnodes)
516  */
517
518 static void delete_empty_dnode(struct inode *i, dnode_secno dno)
519 {
520         struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
521         struct quad_buffer_head qbh;
522         struct dnode *dnode;
523         dnode_secno down, up, ndown;
524         int p;
525         struct hpfs_dirent *de;
526         int c1, c2 = 0;
527         try_it_again:
528         if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
529         if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
530         if (le32_to_cpu(dnode->first_free) > 56) goto end;
531         if (le32_to_cpu(dnode->first_free) == 52 || le32_to_cpu(dnode->first_free) == 56) {
532                 struct hpfs_dirent *de_end;
533                 int root = dnode->root_dnode;
534                 up = le32_to_cpu(dnode->up);
535                 de = dnode_first_de(dnode);
536                 down = de->down ? de_down_pointer(de) : 0;
537                 if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
538                         hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
539                         goto end;
540                 }
541                 hpfs_brelse4(&qbh);
542                 hpfs_free_dnode(i->i_sb, dno);
543                 i->i_size -= 2048;
544                 i->i_blocks -= 4;
545                 if (root) {
546                         struct fnode *fnode;
547                         struct buffer_head *bh;
548                         struct dnode *d1;
549                         struct quad_buffer_head qbh1;
550                         if (hpfs_sb(i->i_sb)->sb_chk)
551                                 if (up != i->i_ino) {
552                                         hpfs_error(i->i_sb,
553                                                    "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
554                                                    dno, up,
555                                                    (unsigned long)i->i_ino);
556                                         return;
557                                 }
558                         if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
559                                 d1->up = cpu_to_le32(up);
560                                 d1->root_dnode = 1;
561                                 hpfs_mark_4buffers_dirty(&qbh1);
562                                 hpfs_brelse4(&qbh1);
563                         }
564                         if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
565                                 fnode->u.external[0].disk_secno = cpu_to_le32(down);
566                                 mark_buffer_dirty(bh);
567                                 brelse(bh);
568                         }
569                         hpfs_inode->i_dno = down;
570                         for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
571                         return;
572                 }
573                 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
574                 p = 1;
575                 de_end = dnode_end_de(dnode);
576                 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
577                         if (de->down) if (de_down_pointer(de) == dno) goto fnd;
578                 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
579                 goto end;
580                 fnd:
581                 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
582                 if (!down) {
583                         de->down = 0;
584                         le16_add_cpu(&de->length, -4);
585                         le32_add_cpu(&dnode->first_free, -4);
586                         memmove(de_next_de(de), (char *)de_next_de(de) + 4,
587                                 (char *)dnode + le32_to_cpu(dnode->first_free) - (char *)de_next_de(de));
588                 } else {
589                         struct dnode *d1;
590                         struct quad_buffer_head qbh1;
591                         *(dnode_secno *) ((void *) de + le16_to_cpu(de->length) - 4) = down;
592                         if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
593                                 d1->up = cpu_to_le32(up);
594                                 hpfs_mark_4buffers_dirty(&qbh1);
595                                 hpfs_brelse4(&qbh1);
596                         }
597                 }
598         } else {
599                 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, le32_to_cpu(dnode->first_free));
600                 goto end;
601         }
602
603         if (!de->last) {
604                 struct hpfs_dirent *de_next = de_next_de(de);
605                 struct hpfs_dirent *de_cp;
606                 struct dnode *d1;
607                 struct quad_buffer_head qbh1;
608                 if (!de_next->down) goto endm;
609                 ndown = de_down_pointer(de_next);
610                 if (!(de_cp = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
611                         pr_err("out of memory for dtree balancing\n");
612                         goto endm;
613                 }
614                 memcpy(de_cp, de, le16_to_cpu(de->length));
615                 hpfs_delete_de(i->i_sb, dnode, de);
616                 hpfs_mark_4buffers_dirty(&qbh);
617                 hpfs_brelse4(&qbh);
618                 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
619                 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
620                 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
621                         d1->up = cpu_to_le32(ndown);
622                         hpfs_mark_4buffers_dirty(&qbh1);
623                         hpfs_brelse4(&qbh1);
624                 }
625                 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
626                 /*pr_info("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n",
627                   up, ndown, down, dno);*/
628                 dno = up;
629                 kfree(de_cp);
630                 goto try_it_again;
631         } else {
632                 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
633                 struct hpfs_dirent *de_cp;
634                 struct dnode *d1;
635                 struct quad_buffer_head qbh1;
636                 dnode_secno dlp;
637                 if (!de_prev) {
638                         hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
639                         hpfs_mark_4buffers_dirty(&qbh);
640                         hpfs_brelse4(&qbh);
641                         dno = up;
642                         goto try_it_again;
643                 }
644                 if (!de_prev->down) goto endm;
645                 ndown = de_down_pointer(de_prev);
646                 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
647                         struct hpfs_dirent *del = dnode_last_de(d1);
648                         dlp = del->down ? de_down_pointer(del) : 0;
649                         if (!dlp && down) {
650                                 if (le32_to_cpu(d1->first_free) > 2044) {
651                                         if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
652                                                 pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
653                                                 pr_err("terminating balancing operation\n");
654                                         }
655                                         hpfs_brelse4(&qbh1);
656                                         goto endm;
657                                 }
658                                 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
659                                         pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
660                                         pr_err("goin'on\n");
661                                 }
662                                 le16_add_cpu(&del->length, 4);
663                                 del->down = 1;
664                                 le32_add_cpu(&d1->first_free, 4);
665                         }
666                         if (dlp && !down) {
667                                 le16_add_cpu(&del->length, -4);
668                                 del->down = 0;
669                                 le32_add_cpu(&d1->first_free, -4);
670                         } else if (down)
671                                 *(__le32 *) ((void *) del + le16_to_cpu(del->length) - 4) = cpu_to_le32(down);
672                 } else goto endm;
673                 if (!(de_cp = kmalloc(le16_to_cpu(de_prev->length), GFP_NOFS))) {
674                         pr_err("out of memory for dtree balancing\n");
675                         hpfs_brelse4(&qbh1);
676                         goto endm;
677                 }
678                 hpfs_mark_4buffers_dirty(&qbh1);
679                 hpfs_brelse4(&qbh1);
680                 memcpy(de_cp, de_prev, le16_to_cpu(de_prev->length));
681                 hpfs_delete_de(i->i_sb, dnode, de_prev);
682                 if (!de_prev->down) {
683                         le16_add_cpu(&de_prev->length, 4);
684                         de_prev->down = 1;
685                         le32_add_cpu(&dnode->first_free, 4);
686                 }
687                 *(__le32 *) ((void *) de_prev + le16_to_cpu(de_prev->length) - 4) = cpu_to_le32(ndown);
688                 hpfs_mark_4buffers_dirty(&qbh);
689                 hpfs_brelse4(&qbh);
690                 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
691                 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
692                 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
693                         d1->up = cpu_to_le32(ndown);
694                         hpfs_mark_4buffers_dirty(&qbh1);
695                         hpfs_brelse4(&qbh1);
696                 }
697                 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
698                 dno = up;
699                 kfree(de_cp);
700                 goto try_it_again;
701         }
702         endm:
703         hpfs_mark_4buffers_dirty(&qbh);
704         end:
705         hpfs_brelse4(&qbh);
706 }
707
708
709 /* Delete dirent from directory */
710
711 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
712                        struct quad_buffer_head *qbh, int depth)
713 {
714         struct dnode *dnode = qbh->data;
715         dnode_secno down = 0;
716         loff_t t;
717         if (de->first || de->last) {
718                 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
719                 hpfs_brelse4(qbh);
720                 return 1;
721         }
722         if (de->down) down = de_down_pointer(de);
723         if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
724                 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
725                         hpfs_brelse4(qbh);
726                         return 2;
727                 }
728         }
729         i->i_version++;
730         for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
731         hpfs_delete_de(i->i_sb, dnode, de);
732         hpfs_mark_4buffers_dirty(qbh);
733         hpfs_brelse4(qbh);
734         if (down) {
735                 dnode_secno a = move_to_top(i, down, dno);
736                 for_all_poss(i, hpfs_pos_subst, 5, t);
737                 if (a) delete_empty_dnode(i, a);
738                 return !a;
739         }
740         delete_empty_dnode(i, dno);
741         return 0;
742 }
743
744 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
745                        int *n_subdirs, int *n_items)
746 {
747         struct dnode *dnode;
748         struct quad_buffer_head qbh;
749         struct hpfs_dirent *de;
750         dnode_secno ptr, odno = 0;
751         int c1, c2 = 0;
752         int d1, d2 = 0;
753         go_down:
754         if (n_dnodes) (*n_dnodes)++;
755         if (hpfs_sb(s)->sb_chk)
756                 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
757         ptr = 0;
758         go_up:
759         if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
760         if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && le32_to_cpu(dnode->up) != odno)
761                 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, le32_to_cpu(dnode->up));
762         de = dnode_first_de(dnode);
763         if (ptr) while(1) {
764                 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
765                 if (de->last) {
766                         hpfs_brelse4(&qbh);
767                         hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
768                                 ptr, dno, odno);
769                         return;
770                 }
771                 de = de_next_de(de);
772         }
773         next_de:
774         if (de->down) {
775                 odno = dno;
776                 dno = de_down_pointer(de);
777                 hpfs_brelse4(&qbh);
778                 goto go_down;
779         }
780         process_de:
781         if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
782         if (!de->first && !de->last && n_items) (*n_items)++;
783         if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
784         ptr = dno;
785         dno = le32_to_cpu(dnode->up);
786         if (dnode->root_dnode) {
787                 hpfs_brelse4(&qbh);
788                 return;
789         }
790         hpfs_brelse4(&qbh);
791         if (hpfs_sb(s)->sb_chk)
792                 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
793         odno = -1;
794         goto go_up;
795 }
796
797 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
798                                           struct quad_buffer_head *qbh, struct dnode **dn)
799 {
800         int i;
801         struct hpfs_dirent *de, *de_end;
802         struct dnode *dnode;
803         dnode = hpfs_map_dnode(s, dno, qbh);
804         if (!dnode) return NULL;
805         if (dn) *dn=dnode;
806         de = dnode_first_de(dnode);
807         de_end = dnode_end_de(dnode);
808         for (i = 1; de < de_end; i++, de = de_next_de(de)) {
809                 if (i == n) {
810                         return de;
811                 }       
812                 if (de->last) break;
813         }
814         hpfs_brelse4(qbh);
815         hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
816         return NULL;
817 }
818
819 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
820 {
821         struct quad_buffer_head qbh;
822         dnode_secno d = dno;
823         dnode_secno up = 0;
824         struct hpfs_dirent *de;
825         int c1, c2 = 0;
826
827         again:
828         if (hpfs_sb(s)->sb_chk)
829                 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
830                         return d;
831         if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
832         if (hpfs_sb(s)->sb_chk)
833                 if (up && le32_to_cpu(((struct dnode *)qbh.data)->up) != up)
834                         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));
835         if (!de->down) {
836                 hpfs_brelse4(&qbh);
837                 return d;
838         }
839         up = d;
840         d = de_down_pointer(de);
841         hpfs_brelse4(&qbh);
842         goto again;
843 }
844
845 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
846                                    struct quad_buffer_head *qbh)
847 {
848         loff_t pos;
849         unsigned c;
850         dnode_secno dno;
851         struct hpfs_dirent *de, *d;
852         struct hpfs_dirent *up_de;
853         struct hpfs_dirent *end_up_de;
854         struct dnode *dnode;
855         struct dnode *up_dnode;
856         struct quad_buffer_head qbh0;
857
858         pos = *posp;
859         dno = pos >> 6 << 2;
860         pos &= 077;
861         if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
862                 goto bail;
863
864         /* Going to the next dirent */
865         if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
866                 if (!(++*posp & 077)) {
867                         hpfs_error(inode->i_sb,
868                                 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
869                                 (unsigned long long)*posp);
870                         goto bail;
871                 }
872                 /* We're going down the tree */
873                 if (d->down) {
874                         *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
875                 }
876         
877                 return de;
878         }
879
880         /* Going up */
881         if (dnode->root_dnode) goto bail;
882
883         if (!(up_dnode = hpfs_map_dnode(inode->i_sb, le32_to_cpu(dnode->up), &qbh0)))
884                 goto bail;
885
886         end_up_de = dnode_end_de(up_dnode);
887         c = 0;
888         for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
889              up_de = de_next_de(up_de)) {
890                 if (!(++c & 077)) hpfs_error(inode->i_sb,
891                         "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode->up));
892                 if (up_de->down && de_down_pointer(up_de) == dno) {
893                         *posp = ((loff_t) le32_to_cpu(dnode->up) << 4) + c;
894                         hpfs_brelse4(&qbh0);
895                         return de;
896                 }
897         }
898         
899         hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
900                 dno, le32_to_cpu(dnode->up));
901         hpfs_brelse4(&qbh0);
902         
903         bail:
904         *posp = 12;
905         return de;
906 }
907
908 /* Find a dirent in tree */
909
910 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
911                                const unsigned char *name, unsigned len,
912                                dnode_secno *dd, struct quad_buffer_head *qbh)
913 {
914         struct dnode *dnode;
915         struct hpfs_dirent *de;
916         struct hpfs_dirent *de_end;
917         int c1, c2 = 0;
918
919         if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
920         again:
921         if (hpfs_sb(inode->i_sb)->sb_chk)
922                 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
923         if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
924         
925         de_end = dnode_end_de(dnode);
926         for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
927                 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
928                 if (!t) {
929                         if (dd) *dd = dno;
930                         return de;
931                 }
932                 if (t < 0) {
933                         if (de->down) {
934                                 dno = de_down_pointer(de);
935                                 hpfs_brelse4(qbh);
936                                 goto again;
937                         }
938                 break;
939                 }
940         }
941         hpfs_brelse4(qbh);
942         return NULL;
943 }
944
945 /*
946  * Remove empty directory. In normal cases it is only one dnode with two
947  * entries, but we must handle also such obscure cases when it's a tree
948  * of empty dnodes.
949  */
950
951 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
952 {
953         struct quad_buffer_head qbh;
954         struct dnode *dnode;
955         struct hpfs_dirent *de;
956         dnode_secno d1, d2, rdno = dno;
957         while (1) {
958                 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
959                 de = dnode_first_de(dnode);
960                 if (de->last) {
961                         if (de->down) d1 = de_down_pointer(de);
962                         else goto error;
963                         hpfs_brelse4(&qbh);
964                         hpfs_free_dnode(s, dno);
965                         dno = d1;
966                 } else break;
967         }
968         if (!de->first) goto error;
969         d1 = de->down ? de_down_pointer(de) : 0;
970         de = de_next_de(de);
971         if (!de->last) goto error;
972         d2 = de->down ? de_down_pointer(de) : 0;
973         hpfs_brelse4(&qbh);
974         hpfs_free_dnode(s, dno);
975         do {
976                 while (d1) {
977                         if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
978                         de = dnode_first_de(dnode);
979                         if (!de->last) goto error;
980                         d1 = de->down ? de_down_pointer(de) : 0;
981                         hpfs_brelse4(&qbh);
982                         hpfs_free_dnode(s, dno);
983                 }
984                 d1 = d2;
985                 d2 = 0;
986         } while (d1);
987         return;
988         error:
989         hpfs_brelse4(&qbh);
990         hpfs_free_dnode(s, dno);
991         hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
992 }
993
994 /* 
995  * Find dirent for specified fnode. Use truncated 15-char name in fnode as
996  * a help for searching.
997  */
998
999 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
1000                                      struct fnode *f, struct quad_buffer_head *qbh)
1001 {
1002         unsigned char *name1;
1003         unsigned char *name2;
1004         int name1len, name2len;
1005         struct dnode *d;
1006         dnode_secno dno, downd;
1007         struct fnode *upf;
1008         struct buffer_head *bh;
1009         struct hpfs_dirent *de, *de_end;
1010         int c;
1011         int c1, c2 = 0;
1012         int d1, d2 = 0;
1013         name1 = f->name;
1014         if (!(name2 = kmalloc(256, GFP_NOFS))) {
1015                 pr_err("out of memory, can't map dirent\n");
1016                 return NULL;
1017         }
1018         if (f->len <= 15)
1019                 memcpy(name2, name1, name1len = name2len = f->len);
1020         else {
1021                 memcpy(name2, name1, 15);
1022                 memset(name2 + 15, 0xff, 256 - 15);
1023                 /*name2[15] = 0xff;*/
1024                 name1len = 15; name2len = 256;
1025         }
1026         if (!(upf = hpfs_map_fnode(s, le32_to_cpu(f->up), &bh))) {
1027                 kfree(name2);
1028                 return NULL;
1029         }       
1030         if (!fnode_is_dir(upf)) {
1031                 brelse(bh);
1032                 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, le32_to_cpu(f->up));
1033                 kfree(name2);
1034                 return NULL;
1035         }
1036         dno = le32_to_cpu(upf->u.external[0].disk_secno);
1037         brelse(bh);
1038         go_down:
1039         downd = 0;
1040         go_up:
1041         if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1042                 kfree(name2);
1043                 return NULL;
1044         }
1045         de_end = dnode_end_de(d);
1046         de = dnode_first_de(d);
1047         if (downd) {
1048                 while (de < de_end) {
1049                         if (de->down) if (de_down_pointer(de) == downd) goto f;
1050                         de = de_next_de(de);
1051                 }
1052                 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1053                 hpfs_brelse4(qbh);
1054                 kfree(name2);
1055                 return NULL;
1056         }
1057         next_de:
1058         if (le32_to_cpu(de->fnode) == fno) {
1059                 kfree(name2);
1060                 return de;
1061         }
1062         c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1063         if (c < 0 && de->down) {
1064                 dno = de_down_pointer(de);
1065                 hpfs_brelse4(qbh);
1066                 if (hpfs_sb(s)->sb_chk)
1067                         if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1068                                 kfree(name2);
1069                                 return NULL;
1070                 }
1071                 goto go_down;
1072         }
1073         f:
1074         if (le32_to_cpu(de->fnode) == fno) {
1075                 kfree(name2);
1076                 return de;
1077         }
1078         c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1079         if (c < 0 && !de->last) goto not_found;
1080         if ((de = de_next_de(de)) < de_end) goto next_de;
1081         if (d->root_dnode) goto not_found;
1082         downd = dno;
1083         dno = le32_to_cpu(d->up);
1084         hpfs_brelse4(qbh);
1085         if (hpfs_sb(s)->sb_chk)
1086                 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1087                         kfree(name2);
1088                         return NULL;
1089                 }
1090         goto go_up;
1091         not_found:
1092         hpfs_brelse4(qbh);
1093         hpfs_error(s, "dirent for fnode %08x not found", fno);
1094         kfree(name2);
1095         return NULL;
1096 }