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