blob: 3228c524ebe56f948d8896cec23ca6b1284f6303 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * linux/fs/hpfs/dnode.c
3 *
4 * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
5 *
6 * handling directory dnode tree - adding, deleteing & searching for dirents
7 */
8
9#include "hpfs_fn.h"
10
11static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
12{
13 struct hpfs_dirent *de;
14 struct hpfs_dirent *de_end = dnode_end_de(d);
15 int i = 1;
16 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
Mikulas Patocka0b697602011-05-08 20:44:26 +020017 if (de == fde) return ((loff_t) le32_to_cpu(d->self) << 4) | (loff_t)i;
Linus Torvalds1da177e2005-04-16 15:20:36 -070018 i++;
19 }
20 printk("HPFS: get_pos: not_found\n");
Mikulas Patocka0b697602011-05-08 20:44:26 +020021 return ((loff_t)le32_to_cpu(d->self) << 4) | (loff_t)1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070022}
23
24void hpfs_add_pos(struct inode *inode, loff_t *pos)
25{
26 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
27 int i = 0;
28 loff_t **ppos;
29
30 if (hpfs_inode->i_rddir_off)
31 for (; hpfs_inode->i_rddir_off[i]; i++)
32 if (hpfs_inode->i_rddir_off[i] == pos) return;
33 if (!(i&0x0f)) {
34 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
35 printk("HPFS: out of memory for position list\n");
36 return;
37 }
38 if (hpfs_inode->i_rddir_off) {
39 memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
40 kfree(hpfs_inode->i_rddir_off);
41 }
42 hpfs_inode->i_rddir_off = ppos;
43 }
44 hpfs_inode->i_rddir_off[i] = pos;
45 hpfs_inode->i_rddir_off[i + 1] = NULL;
46}
47
48void hpfs_del_pos(struct inode *inode, loff_t *pos)
49{
50 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
51 loff_t **i, **j;
52
53 if (!hpfs_inode->i_rddir_off) goto not_f;
54 for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
55 goto not_f;
56 fnd:
57 for (j = i + 1; *j; j++) ;
58 *i = *(j - 1);
59 *(j - 1) = NULL;
60 if (j - 1 == hpfs_inode->i_rddir_off) {
61 kfree(hpfs_inode->i_rddir_off);
62 hpfs_inode->i_rddir_off = NULL;
63 }
64 return;
65 not_f:
66 /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
67 return;
68}
69
70static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
71 loff_t p1, loff_t p2)
72{
73 struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
74 loff_t **i;
75
76 if (!hpfs_inode->i_rddir_off) return;
77 for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
78 return;
79}
80
81static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
82{
83 if (*p == f) *p = t;
84}
85
86/*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
87{
88 if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
89}*/
90
91static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
92{
93 if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
94 int n = (*p & 0x3f) + c;
95 if (n > 0x3f) printk("HPFS: hpfs_pos_ins: %08x + %d\n", (int)*p, (int)c >> 8);
96 else *p = (*p & ~0x3f) | n;
97 }
98}
99
100static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
101{
102 if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
103 int n = (*p & 0x3f) - c;
104 if (n < 1) printk("HPFS: hpfs_pos_ins: %08x - %d\n", (int)*p, (int)c >> 8);
105 else *p = (*p & ~0x3f) | n;
106 }
107}
108
109static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
110{
111 struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
112 de_end = dnode_end_de(d);
113 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
114 deee = dee; dee = de;
115 }
116 return deee;
117}
118
119static struct hpfs_dirent *dnode_last_de(struct dnode *d)
120{
121 struct hpfs_dirent *de, *de_end, *dee = NULL;
122 de_end = dnode_end_de(d);
123 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
124 dee = de;
125 }
126 return dee;
127}
128
129static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
130{
131 struct hpfs_dirent *de;
132 if (!(de = dnode_last_de(d))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200133 hpfs_error(s, "set_last_pointer: empty dnode %08x", le32_to_cpu(d->self));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134 return;
135 }
136 if (hpfs_sb(s)->sb_chk) {
137 if (de->down) {
138 hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
Mikulas Patocka0b697602011-05-08 20:44:26 +0200139 le32_to_cpu(d->self), de_down_pointer(de));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140 return;
141 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200142 if (le16_to_cpu(de->length) != 32) {
143 hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", le32_to_cpu(d->self));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144 return;
145 }
146 }
147 if (ptr) {
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200148 d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) + 4);
149 if (le32_to_cpu(d->first_free) > 2048) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200150 hpfs_error(s, "set_last_pointer: too long dnode %08x", le32_to_cpu(d->self));
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200151 d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152 return;
153 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200154 de->length = cpu_to_le16(36);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155 de->down = 1;
Al Viro46287aa2012-04-17 16:20:49 -0400156 *(__le32 *)((char *)de + 32) = cpu_to_le32(ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157 }
158}
159
160/* Add an entry to dnode and don't care if it grows over 2048 bytes */
161
Al Viro7e7742e2010-01-31 17:09:29 -0500162struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d,
163 const unsigned char *name,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 unsigned namelen, secno down_ptr)
165{
166 struct hpfs_dirent *de;
167 struct hpfs_dirent *de_end = dnode_end_de(d);
168 unsigned d_size = de_size(namelen, down_ptr);
169 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
170 int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
171 if (!c) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200172 hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, le32_to_cpu(d->self));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173 return NULL;
174 }
175 if (c < 0) break;
176 }
177 memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
178 memset(de, 0, d_size);
179 if (down_ptr) {
Al Viro46287aa2012-04-17 16:20:49 -0400180 *(__le32 *)((char *)de + d_size - 4) = cpu_to_le32(down_ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181 de->down = 1;
182 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200183 de->length = cpu_to_le16(d_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700184 de->not_8x3 = hpfs_is_name_long(name, namelen);
185 de->namelen = namelen;
186 memcpy(de->name, name, namelen);
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200187 d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) + d_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188 return de;
189}
190
191/* Delete dirent and don't care about its subtree */
192
193static void hpfs_delete_de(struct super_block *s, struct dnode *d,
194 struct hpfs_dirent *de)
195{
196 if (de->last) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200197 hpfs_error(s, "attempt to delete last dirent in dnode %08x", le32_to_cpu(d->self));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700198 return;
199 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200200 d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) - le16_to_cpu(de->length));
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200201 memmove(de, de_next_de(de), le32_to_cpu(d->first_free) + (char *)d - (char *)de);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202}
203
204static void fix_up_ptrs(struct super_block *s, struct dnode *d)
205{
206 struct hpfs_dirent *de;
207 struct hpfs_dirent *de_end = dnode_end_de(d);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200208 dnode_secno dno = le32_to_cpu(d->self);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
210 if (de->down) {
211 struct quad_buffer_head qbh;
212 struct dnode *dd;
213 if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200214 if (le32_to_cpu(dd->up) != dno || dd->root_dnode) {
215 dd->up = cpu_to_le32(dno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216 dd->root_dnode = 0;
217 hpfs_mark_4buffers_dirty(&qbh);
218 }
219 hpfs_brelse4(&qbh);
220 }
221 }
222}
223
224/* Add an entry to dnode and do dnode splitting if required */
225
226static int hpfs_add_to_dnode(struct inode *i, dnode_secno dno,
Al Viro7e7742e2010-01-31 17:09:29 -0500227 const unsigned char *name, unsigned namelen,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700228 struct hpfs_dirent *new_de, dnode_secno down_ptr)
229{
230 struct quad_buffer_head qbh, qbh1, qbh2;
231 struct dnode *d, *ad, *rd, *nd = NULL;
232 dnode_secno adno, rdno;
233 struct hpfs_dirent *de;
234 struct hpfs_dirent nde;
Al Viro7e7742e2010-01-31 17:09:29 -0500235 unsigned char *nname;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236 int h;
237 int pos;
238 struct buffer_head *bh;
239 struct fnode *fnode;
240 int c1, c2 = 0;
241 if (!(nname = kmalloc(256, GFP_NOFS))) {
242 printk("HPFS: out of memory, can't add to dnode\n");
243 return 1;
244 }
245 go_up:
246 if (namelen >= 256) {
247 hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen);
Jesper Juhlf99d49a2005-11-07 01:01:34 -0800248 kfree(nd);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249 kfree(nname);
250 return 1;
251 }
252 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
Jesper Juhlf99d49a2005-11-07 01:01:34 -0800253 kfree(nd);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700254 kfree(nname);
255 return 1;
256 }
257 go_up_a:
258 if (hpfs_sb(i->i_sb)->sb_chk)
259 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
260 hpfs_brelse4(&qbh);
Jesper Juhlf99d49a2005-11-07 01:01:34 -0800261 kfree(nd);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700262 kfree(nname);
263 return 1;
264 }
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200265 if (le32_to_cpu(d->first_free) + de_size(namelen, down_ptr) <= 2048) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266 loff_t t;
267 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
268 t = get_pos(d, de);
269 for_all_poss(i, hpfs_pos_ins, t, 1);
270 for_all_poss(i, hpfs_pos_subst, 4, t);
271 for_all_poss(i, hpfs_pos_subst, 5, t + 1);
272 hpfs_mark_4buffers_dirty(&qbh);
273 hpfs_brelse4(&qbh);
Jesper Juhlf99d49a2005-11-07 01:01:34 -0800274 kfree(nd);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700275 kfree(nname);
276 return 0;
277 }
278 if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
279 /* 0x924 is a max size of dnode after adding a dirent with
280 max name length. We alloc this only once. There must
281 not be any error while splitting dnodes, otherwise the
282 whole directory, not only file we're adding, would
283 be lost. */
284 printk("HPFS: out of memory for dnode splitting\n");
285 hpfs_brelse4(&qbh);
286 kfree(nname);
287 return 1;
288 }
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200289 memcpy(nd, d, le32_to_cpu(d->first_free));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700290 copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
291 for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
292 h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200293 if (!(ad = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &adno, &qbh1))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
295 hpfs_brelse4(&qbh);
296 kfree(nd);
297 kfree(nname);
298 return 1;
299 }
300 i->i_size += 2048;
301 i->i_blocks += 4;
302 pos = 1;
303 for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
304 copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
305 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
306 pos++;
307 }
308 copy_de(new_de = &nde, de);
Al Viro7e7742e2010-01-31 17:09:29 -0500309 memcpy(nname, de->name, de->namelen);
310 name = nname;
311 namelen = de->namelen;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700312 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
313 down_ptr = adno;
314 set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
315 de = de_next_de(de);
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200316 memmove((char *)nd + 20, de, le32_to_cpu(nd->first_free) + (char *)nd - (char *)de);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200317 nd->first_free = cpu_to_le32(le32_to_cpu(nd->first_free) - ((char *)de - (char *)nd - 20));
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200318 memcpy(d, nd, le32_to_cpu(nd->first_free));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319 for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
320 fix_up_ptrs(i->i_sb, ad);
321 if (!d->root_dnode) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200322 ad->up = d->up;
323 dno = le32_to_cpu(ad->up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700324 hpfs_mark_4buffers_dirty(&qbh);
325 hpfs_brelse4(&qbh);
326 hpfs_mark_4buffers_dirty(&qbh1);
327 hpfs_brelse4(&qbh1);
328 goto go_up;
329 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200330 if (!(rd = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &rdno, &qbh2))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700331 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
332 hpfs_brelse4(&qbh);
333 hpfs_brelse4(&qbh1);
334 kfree(nd);
335 kfree(nname);
336 return 1;
337 }
338 i->i_size += 2048;
339 i->i_blocks += 4;
340 rd->root_dnode = 1;
341 rd->up = d->up;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200342 if (!(fnode = hpfs_map_fnode(i->i_sb, le32_to_cpu(d->up), &bh))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700343 hpfs_free_dnode(i->i_sb, rdno);
344 hpfs_brelse4(&qbh);
345 hpfs_brelse4(&qbh1);
346 hpfs_brelse4(&qbh2);
347 kfree(nd);
348 kfree(nname);
349 return 1;
350 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200351 fnode->u.external[0].disk_secno = cpu_to_le32(rdno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352 mark_buffer_dirty(bh);
353 brelse(bh);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200354 hpfs_i(i)->i_dno = rdno;
355 d->up = ad->up = cpu_to_le32(rdno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356 d->root_dnode = ad->root_dnode = 0;
357 hpfs_mark_4buffers_dirty(&qbh);
358 hpfs_brelse4(&qbh);
359 hpfs_mark_4buffers_dirty(&qbh1);
360 hpfs_brelse4(&qbh1);
361 qbh = qbh2;
362 set_last_pointer(i->i_sb, rd, dno);
363 dno = rdno;
364 d = rd;
365 goto go_up_a;
366}
367
368/*
369 * Add an entry to directory btree.
370 * I hate such crazy directory structure.
371 * It's easy to read but terrible to write.
372 * I wrote this directory code 4 times.
373 * I hope, now it's finally bug-free.
374 */
375
Al Viro7e7742e2010-01-31 17:09:29 -0500376int hpfs_add_dirent(struct inode *i,
377 const unsigned char *name, unsigned namelen,
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200378 struct hpfs_dirent *new_de)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379{
380 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
381 struct dnode *d;
382 struct hpfs_dirent *de, *de_end;
383 struct quad_buffer_head qbh;
384 dnode_secno dno;
385 int c;
386 int c1, c2 = 0;
387 dno = hpfs_inode->i_dno;
388 down:
389 if (hpfs_sb(i->i_sb)->sb_chk)
390 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
391 if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
392 de_end = dnode_end_de(d);
393 for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
394 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
395 hpfs_brelse4(&qbh);
396 return -1;
397 }
398 if (c < 0) {
399 if (de->down) {
400 dno = de_down_pointer(de);
401 hpfs_brelse4(&qbh);
402 goto down;
403 }
404 break;
405 }
406 }
407 hpfs_brelse4(&qbh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
409 c = 1;
410 goto ret;
411 }
412 i->i_version++;
413 c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
414 ret:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 return c;
416}
417
418/*
419 * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
420 * Return the dnode we moved from (to be checked later if it's empty)
421 */
422
423static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
424{
425 dnode_secno dno, ddno;
426 dnode_secno chk_up = to;
427 struct dnode *dnode;
428 struct quad_buffer_head qbh;
429 struct hpfs_dirent *de, *nde;
430 int a;
431 loff_t t;
432 int c1, c2 = 0;
433 dno = from;
434 while (1) {
435 if (hpfs_sb(i->i_sb)->sb_chk)
436 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
437 return 0;
438 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
439 if (hpfs_sb(i->i_sb)->sb_chk) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200440 if (le32_to_cpu(dnode->up) != chk_up) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700441 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
Mikulas Patocka0b697602011-05-08 20:44:26 +0200442 dno, chk_up, le32_to_cpu(dnode->up));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 hpfs_brelse4(&qbh);
444 return 0;
445 }
446 chk_up = dno;
447 }
448 if (!(de = dnode_last_de(dnode))) {
449 hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
450 hpfs_brelse4(&qbh);
451 return 0;
452 }
453 if (!de->down) break;
454 dno = de_down_pointer(de);
455 hpfs_brelse4(&qbh);
456 }
457 while (!(de = dnode_pre_last_de(dnode))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200458 dnode_secno up = le32_to_cpu(dnode->up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700459 hpfs_brelse4(&qbh);
460 hpfs_free_dnode(i->i_sb, dno);
461 i->i_size -= 2048;
462 i->i_blocks -= 4;
463 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
464 if (up == to) return to;
465 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
466 if (dnode->root_dnode) {
467 hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
468 hpfs_brelse4(&qbh);
469 return 0;
470 }
471 de = dnode_last_de(dnode);
472 if (!de || !de->down) {
473 hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
474 hpfs_brelse4(&qbh);
475 return 0;
476 }
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200477 dnode->first_free = cpu_to_le32(le32_to_cpu(dnode->first_free) - 4);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200478 de->length = cpu_to_le16(le16_to_cpu(de->length) - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479 de->down = 0;
480 hpfs_mark_4buffers_dirty(&qbh);
481 dno = up;
482 }
483 t = get_pos(dnode, de);
484 for_all_poss(i, hpfs_pos_subst, t, 4);
485 for_all_poss(i, hpfs_pos_subst, t + 1, 5);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200486 if (!(nde = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700487 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
488 hpfs_brelse4(&qbh);
489 return 0;
490 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200491 memcpy(nde, de, le16_to_cpu(de->length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 ddno = de->down ? de_down_pointer(de) : 0;
493 hpfs_delete_de(i->i_sb, dnode, de);
494 set_last_pointer(i->i_sb, dnode, ddno);
495 hpfs_mark_4buffers_dirty(&qbh);
496 hpfs_brelse4(&qbh);
497 a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
498 kfree(nde);
499 if (a) return 0;
500 return dno;
501}
502
503/*
504 * Check if a dnode is empty and delete it from the tree
505 * (chkdsk doesn't like empty dnodes)
506 */
507
508static void delete_empty_dnode(struct inode *i, dnode_secno dno)
509{
510 struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
511 struct quad_buffer_head qbh;
512 struct dnode *dnode;
513 dnode_secno down, up, ndown;
514 int p;
515 struct hpfs_dirent *de;
516 int c1, c2 = 0;
517 try_it_again:
518 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
519 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200520 if (le32_to_cpu(dnode->first_free) > 56) goto end;
521 if (le32_to_cpu(dnode->first_free) == 52 || le32_to_cpu(dnode->first_free) == 56) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700522 struct hpfs_dirent *de_end;
523 int root = dnode->root_dnode;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200524 up = le32_to_cpu(dnode->up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525 de = dnode_first_de(dnode);
526 down = de->down ? de_down_pointer(de) : 0;
527 if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
528 hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
529 goto end;
530 }
531 hpfs_brelse4(&qbh);
532 hpfs_free_dnode(i->i_sb, dno);
533 i->i_size -= 2048;
534 i->i_blocks -= 4;
535 if (root) {
536 struct fnode *fnode;
537 struct buffer_head *bh;
538 struct dnode *d1;
539 struct quad_buffer_head qbh1;
Randy Dunlap18debbb2006-12-06 20:37:05 -0800540 if (hpfs_sb(i->i_sb)->sb_chk)
541 if (up != i->i_ino) {
542 hpfs_error(i->i_sb,
543 "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
544 dno, up, (unsigned long)i->i_ino);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700545 return;
Randy Dunlap18debbb2006-12-06 20:37:05 -0800546 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700547 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200548 d1->up = cpu_to_le32(up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 d1->root_dnode = 1;
550 hpfs_mark_4buffers_dirty(&qbh1);
551 hpfs_brelse4(&qbh1);
552 }
553 if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200554 fnode->u.external[0].disk_secno = cpu_to_le32(down);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555 mark_buffer_dirty(bh);
556 brelse(bh);
557 }
558 hpfs_inode->i_dno = down;
559 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
560 return;
561 }
562 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
563 p = 1;
564 de_end = dnode_end_de(dnode);
565 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
566 if (de->down) if (de_down_pointer(de) == dno) goto fnd;
567 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
568 goto end;
569 fnd:
570 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
571 if (!down) {
572 de->down = 0;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200573 de->length = cpu_to_le16(le16_to_cpu(de->length) - 4);
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200574 dnode->first_free = cpu_to_le32(le32_to_cpu(dnode->first_free) - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575 memmove(de_next_de(de), (char *)de_next_de(de) + 4,
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200576 (char *)dnode + le32_to_cpu(dnode->first_free) - (char *)de_next_de(de));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577 } else {
578 struct dnode *d1;
579 struct quad_buffer_head qbh1;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200580 *(dnode_secno *) ((void *) de + le16_to_cpu(de->length) - 4) = down;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581 if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200582 d1->up = cpu_to_le32(up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700583 hpfs_mark_4buffers_dirty(&qbh1);
584 hpfs_brelse4(&qbh1);
585 }
586 }
587 } else {
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200588 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, le32_to_cpu(dnode->first_free));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589 goto end;
590 }
591
592 if (!de->last) {
593 struct hpfs_dirent *de_next = de_next_de(de);
594 struct hpfs_dirent *de_cp;
595 struct dnode *d1;
596 struct quad_buffer_head qbh1;
597 if (!de_next->down) goto endm;
598 ndown = de_down_pointer(de_next);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200599 if (!(de_cp = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700600 printk("HPFS: out of memory for dtree balancing\n");
601 goto endm;
602 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200603 memcpy(de_cp, de, le16_to_cpu(de->length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700604 hpfs_delete_de(i->i_sb, dnode, de);
605 hpfs_mark_4buffers_dirty(&qbh);
606 hpfs_brelse4(&qbh);
607 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
608 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
609 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200610 d1->up = cpu_to_le32(ndown);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700611 hpfs_mark_4buffers_dirty(&qbh1);
612 hpfs_brelse4(&qbh1);
613 }
614 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
615 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
616 dno = up;
617 kfree(de_cp);
618 goto try_it_again;
619 } else {
620 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
621 struct hpfs_dirent *de_cp;
622 struct dnode *d1;
623 struct quad_buffer_head qbh1;
624 dnode_secno dlp;
625 if (!de_prev) {
626 hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
627 hpfs_mark_4buffers_dirty(&qbh);
628 hpfs_brelse4(&qbh);
629 dno = up;
630 goto try_it_again;
631 }
632 if (!de_prev->down) goto endm;
633 ndown = de_down_pointer(de_prev);
634 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
635 struct hpfs_dirent *del = dnode_last_de(d1);
636 dlp = del->down ? de_down_pointer(del) : 0;
637 if (!dlp && down) {
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200638 if (le32_to_cpu(d1->first_free) > 2044) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
640 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
641 printk("HPFS: warning: terminating balancing operation\n");
642 }
643 hpfs_brelse4(&qbh1);
644 goto endm;
645 }
646 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
647 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
648 printk("HPFS: warning: goin'on\n");
649 }
Mikulas Patocka0b697602011-05-08 20:44:26 +0200650 del->length = cpu_to_le16(le16_to_cpu(del->length) + 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651 del->down = 1;
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200652 d1->first_free = cpu_to_le32(le32_to_cpu(d1->first_free) + 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 }
654 if (dlp && !down) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200655 del->length = cpu_to_le16(le16_to_cpu(del->length) - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 del->down = 0;
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200657 d1->first_free = cpu_to_le32(le32_to_cpu(d1->first_free) - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700658 } else if (down)
Al Viro46287aa2012-04-17 16:20:49 -0400659 *(__le32 *) ((void *) del + le16_to_cpu(del->length) - 4) = cpu_to_le32(down);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700660 } else goto endm;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200661 if (!(de_cp = kmalloc(le16_to_cpu(de_prev->length), GFP_NOFS))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 printk("HPFS: out of memory for dtree balancing\n");
663 hpfs_brelse4(&qbh1);
664 goto endm;
665 }
666 hpfs_mark_4buffers_dirty(&qbh1);
667 hpfs_brelse4(&qbh1);
Mikulas Patocka0b697602011-05-08 20:44:26 +0200668 memcpy(de_cp, de_prev, le16_to_cpu(de_prev->length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700669 hpfs_delete_de(i->i_sb, dnode, de_prev);
670 if (!de_prev->down) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200671 de_prev->length = cpu_to_le16(le16_to_cpu(de_prev->length) + 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672 de_prev->down = 1;
Mikulas Patocka7d23ce32011-05-08 20:43:06 +0200673 dnode->first_free = cpu_to_le32(le32_to_cpu(dnode->first_free) + 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700674 }
Al Viro46287aa2012-04-17 16:20:49 -0400675 *(__le32 *) ((void *) de_prev + le16_to_cpu(de_prev->length) - 4) = cpu_to_le32(ndown);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676 hpfs_mark_4buffers_dirty(&qbh);
677 hpfs_brelse4(&qbh);
678 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
679 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
680 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200681 d1->up = cpu_to_le32(ndown);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682 hpfs_mark_4buffers_dirty(&qbh1);
683 hpfs_brelse4(&qbh1);
684 }
685 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
686 dno = up;
687 kfree(de_cp);
688 goto try_it_again;
689 }
690 endm:
691 hpfs_mark_4buffers_dirty(&qbh);
692 end:
693 hpfs_brelse4(&qbh);
694}
695
696
697/* Delete dirent from directory */
698
699int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
700 struct quad_buffer_head *qbh, int depth)
701{
702 struct dnode *dnode = qbh->data;
703 dnode_secno down = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700704 loff_t t;
705 if (de->first || de->last) {
706 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
707 hpfs_brelse4(qbh);
708 return 1;
709 }
710 if (de->down) down = de_down_pointer(de);
711 if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
713 hpfs_brelse4(qbh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700714 return 2;
715 }
716 }
717 i->i_version++;
718 for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
719 hpfs_delete_de(i->i_sb, dnode, de);
720 hpfs_mark_4buffers_dirty(qbh);
721 hpfs_brelse4(qbh);
722 if (down) {
723 dnode_secno a = move_to_top(i, down, dno);
724 for_all_poss(i, hpfs_pos_subst, 5, t);
725 if (a) delete_empty_dnode(i, a);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700726 return !a;
727 }
728 delete_empty_dnode(i, dno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700729 return 0;
730}
731
732void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
733 int *n_subdirs, int *n_items)
734{
735 struct dnode *dnode;
736 struct quad_buffer_head qbh;
737 struct hpfs_dirent *de;
738 dnode_secno ptr, odno = 0;
739 int c1, c2 = 0;
740 int d1, d2 = 0;
741 go_down:
742 if (n_dnodes) (*n_dnodes)++;
743 if (hpfs_sb(s)->sb_chk)
744 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
745 ptr = 0;
746 go_up:
747 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200748 if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && le32_to_cpu(dnode->up) != odno)
749 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, le32_to_cpu(dnode->up));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700750 de = dnode_first_de(dnode);
751 if (ptr) while(1) {
752 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
753 if (de->last) {
754 hpfs_brelse4(&qbh);
755 hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
756 ptr, dno, odno);
757 return;
758 }
759 de = de_next_de(de);
760 }
761 next_de:
762 if (de->down) {
763 odno = dno;
764 dno = de_down_pointer(de);
765 hpfs_brelse4(&qbh);
766 goto go_down;
767 }
768 process_de:
769 if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
770 if (!de->first && !de->last && n_items) (*n_items)++;
771 if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
772 ptr = dno;
Mikulas Patocka0b697602011-05-08 20:44:26 +0200773 dno = le32_to_cpu(dnode->up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774 if (dnode->root_dnode) {
775 hpfs_brelse4(&qbh);
776 return;
777 }
778 hpfs_brelse4(&qbh);
779 if (hpfs_sb(s)->sb_chk)
780 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
781 odno = -1;
782 goto go_up;
783}
784
785static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
786 struct quad_buffer_head *qbh, struct dnode **dn)
787{
788 int i;
789 struct hpfs_dirent *de, *de_end;
790 struct dnode *dnode;
791 dnode = hpfs_map_dnode(s, dno, qbh);
792 if (!dnode) return NULL;
793 if (dn) *dn=dnode;
794 de = dnode_first_de(dnode);
795 de_end = dnode_end_de(dnode);
796 for (i = 1; de < de_end; i++, de = de_next_de(de)) {
797 if (i == n) {
798 return de;
799 }
800 if (de->last) break;
801 }
802 hpfs_brelse4(qbh);
803 hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
804 return NULL;
805}
806
807dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
808{
809 struct quad_buffer_head qbh;
810 dnode_secno d = dno;
811 dnode_secno up = 0;
812 struct hpfs_dirent *de;
813 int c1, c2 = 0;
814
815 again:
816 if (hpfs_sb(s)->sb_chk)
817 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
818 return d;
819 if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
820 if (hpfs_sb(s)->sb_chk)
Mikulas Patocka0b697602011-05-08 20:44:26 +0200821 if (up && le32_to_cpu(((struct dnode *)qbh.data)->up) != up)
822 hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, le32_to_cpu(((struct dnode *)qbh.data)->up));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700823 if (!de->down) {
824 hpfs_brelse4(&qbh);
825 return d;
826 }
827 up = d;
828 d = de_down_pointer(de);
829 hpfs_brelse4(&qbh);
830 goto again;
831}
832
833struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
834 struct quad_buffer_head *qbh)
835{
836 loff_t pos;
837 unsigned c;
838 dnode_secno dno;
839 struct hpfs_dirent *de, *d;
840 struct hpfs_dirent *up_de;
841 struct hpfs_dirent *end_up_de;
842 struct dnode *dnode;
843 struct dnode *up_dnode;
844 struct quad_buffer_head qbh0;
845
846 pos = *posp;
847 dno = pos >> 6 << 2;
848 pos &= 077;
849 if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
850 goto bail;
851
852 /* Going to the next dirent */
853 if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
854 if (!(++*posp & 077)) {
Randy Dunlap18debbb2006-12-06 20:37:05 -0800855 hpfs_error(inode->i_sb,
856 "map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
857 (unsigned long long)*posp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700858 goto bail;
859 }
860 /* We're going down the tree */
861 if (d->down) {
862 *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
863 }
864
865 return de;
866 }
867
868 /* Going up */
869 if (dnode->root_dnode) goto bail;
870
Mikulas Patocka0b697602011-05-08 20:44:26 +0200871 if (!(up_dnode = hpfs_map_dnode(inode->i_sb, le32_to_cpu(dnode->up), &qbh0)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700872 goto bail;
873
874 end_up_de = dnode_end_de(up_dnode);
875 c = 0;
876 for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
877 up_de = de_next_de(up_de)) {
878 if (!(++c & 077)) hpfs_error(inode->i_sb,
Mikulas Patocka0b697602011-05-08 20:44:26 +0200879 "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode->up));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880 if (up_de->down && de_down_pointer(up_de) == dno) {
Mikulas Patocka0b697602011-05-08 20:44:26 +0200881 *posp = ((loff_t) le32_to_cpu(dnode->up) << 4) + c;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700882 hpfs_brelse4(&qbh0);
883 return de;
884 }
885 }
886
887 hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
Mikulas Patocka0b697602011-05-08 20:44:26 +0200888 dno, le32_to_cpu(dnode->up));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700889 hpfs_brelse4(&qbh0);
890
891 bail:
892 *posp = 12;
893 return de;
894}
895
896/* Find a dirent in tree */
897
Al Viro7e7742e2010-01-31 17:09:29 -0500898struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
899 const unsigned char *name, unsigned len,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900 dnode_secno *dd, struct quad_buffer_head *qbh)
901{
902 struct dnode *dnode;
903 struct hpfs_dirent *de;
904 struct hpfs_dirent *de_end;
905 int c1, c2 = 0;
906
907 if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
908 again:
909 if (hpfs_sb(inode->i_sb)->sb_chk)
910 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
911 if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
912
913 de_end = dnode_end_de(dnode);
914 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
915 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
916 if (!t) {
917 if (dd) *dd = dno;
918 return de;
919 }
920 if (t < 0) {
921 if (de->down) {
922 dno = de_down_pointer(de);
923 hpfs_brelse4(qbh);
924 goto again;
925 }
926 break;
927 }
928 }
929 hpfs_brelse4(qbh);
930 return NULL;
931}
932
933/*
934 * Remove empty directory. In normal cases it is only one dnode with two
935 * entries, but we must handle also such obscure cases when it's a tree
936 * of empty dnodes.
937 */
938
939void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
940{
941 struct quad_buffer_head qbh;
942 struct dnode *dnode;
943 struct hpfs_dirent *de;
944 dnode_secno d1, d2, rdno = dno;
945 while (1) {
946 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
947 de = dnode_first_de(dnode);
948 if (de->last) {
949 if (de->down) d1 = de_down_pointer(de);
950 else goto error;
951 hpfs_brelse4(&qbh);
952 hpfs_free_dnode(s, dno);
953 dno = d1;
954 } else break;
955 }
956 if (!de->first) goto error;
957 d1 = de->down ? de_down_pointer(de) : 0;
958 de = de_next_de(de);
959 if (!de->last) goto error;
960 d2 = de->down ? de_down_pointer(de) : 0;
961 hpfs_brelse4(&qbh);
962 hpfs_free_dnode(s, dno);
963 do {
964 while (d1) {
965 if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
966 de = dnode_first_de(dnode);
967 if (!de->last) goto error;
968 d1 = de->down ? de_down_pointer(de) : 0;
969 hpfs_brelse4(&qbh);
970 hpfs_free_dnode(s, dno);
971 }
972 d1 = d2;
973 d2 = 0;
974 } while (d1);
975 return;
976 error:
977 hpfs_brelse4(&qbh);
978 hpfs_free_dnode(s, dno);
979 hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
980}
981
982/*
983 * Find dirent for specified fnode. Use truncated 15-char name in fnode as
984 * a help for searching.
985 */
986
987struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
988 struct fnode *f, struct quad_buffer_head *qbh)
989{
Al Viro7e7742e2010-01-31 17:09:29 -0500990 unsigned char *name1;
991 unsigned char *name2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700992 int name1len, name2len;
993 struct dnode *d;
994 dnode_secno dno, downd;
995 struct fnode *upf;
996 struct buffer_head *bh;
997 struct hpfs_dirent *de, *de_end;
998 int c;
999 int c1, c2 = 0;
1000 int d1, d2 = 0;
1001 name1 = f->name;
1002 if (!(name2 = kmalloc(256, GFP_NOFS))) {
1003 printk("HPFS: out of memory, can't map dirent\n");
1004 return NULL;
1005 }
1006 if (f->len <= 15)
1007 memcpy(name2, name1, name1len = name2len = f->len);
1008 else {
1009 memcpy(name2, name1, 15);
1010 memset(name2 + 15, 0xff, 256 - 15);
1011 /*name2[15] = 0xff;*/
1012 name1len = 15; name2len = 256;
1013 }
Mikulas Patocka0b697602011-05-08 20:44:26 +02001014 if (!(upf = hpfs_map_fnode(s, le32_to_cpu(f->up), &bh))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001015 kfree(name2);
1016 return NULL;
1017 }
Al Viroc4c99542012-04-06 14:30:07 -04001018 if (!fnode_is_dir(upf)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001019 brelse(bh);
Mikulas Patocka0b697602011-05-08 20:44:26 +02001020 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, le32_to_cpu(f->up));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021 kfree(name2);
1022 return NULL;
1023 }
Mikulas Patocka0b697602011-05-08 20:44:26 +02001024 dno = le32_to_cpu(upf->u.external[0].disk_secno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001025 brelse(bh);
1026 go_down:
1027 downd = 0;
1028 go_up:
1029 if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1030 kfree(name2);
1031 return NULL;
1032 }
1033 de_end = dnode_end_de(d);
1034 de = dnode_first_de(d);
1035 if (downd) {
1036 while (de < de_end) {
1037 if (de->down) if (de_down_pointer(de) == downd) goto f;
1038 de = de_next_de(de);
1039 }
1040 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1041 hpfs_brelse4(qbh);
1042 kfree(name2);
1043 return NULL;
1044 }
1045 next_de:
Mikulas Patocka0b697602011-05-08 20:44:26 +02001046 if (le32_to_cpu(de->fnode) == fno) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001047 kfree(name2);
1048 return de;
1049 }
1050 c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1051 if (c < 0 && de->down) {
1052 dno = de_down_pointer(de);
1053 hpfs_brelse4(qbh);
1054 if (hpfs_sb(s)->sb_chk)
1055 if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1056 kfree(name2);
1057 return NULL;
1058 }
1059 goto go_down;
1060 }
1061 f:
Mikulas Patocka0b697602011-05-08 20:44:26 +02001062 if (le32_to_cpu(de->fnode) == fno) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001063 kfree(name2);
1064 return de;
1065 }
1066 c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1067 if (c < 0 && !de->last) goto not_found;
1068 if ((de = de_next_de(de)) < de_end) goto next_de;
1069 if (d->root_dnode) goto not_found;
1070 downd = dno;
Mikulas Patocka0b697602011-05-08 20:44:26 +02001071 dno = le32_to_cpu(d->up);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001072 hpfs_brelse4(qbh);
1073 if (hpfs_sb(s)->sb_chk)
1074 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1075 kfree(name2);
1076 return NULL;
1077 }
1078 goto go_up;
1079 not_found:
1080 hpfs_brelse4(qbh);
1081 hpfs_error(s, "dirent for fnode %08x not found", fno);
1082 kfree(name2);
1083 return NULL;
1084}