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