xref: /linux/fs/hpfs/dnode.c (revision e5c86679d5e864947a52fb31e45a425dea3e7fa9)
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 
11 static 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 
24 int 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)
33 				return 0;
34 	if (!(i&0x0f)) {
35 		if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
36 			pr_err("out of memory for position list\n");
37 			return -ENOMEM;
38 		}
39 		if (hpfs_inode->i_rddir_off) {
40 			memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
41 			kfree(hpfs_inode->i_rddir_off);
42 		}
43 		hpfs_inode->i_rddir_off = ppos;
44 	}
45 	hpfs_inode->i_rddir_off[i] = pos;
46 	hpfs_inode->i_rddir_off[i + 1] = NULL;
47 	return 0;
48 }
49 
50 void hpfs_del_pos(struct inode *inode, loff_t *pos)
51 {
52 	struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
53 	loff_t **i, **j;
54 
55 	if (!hpfs_inode->i_rddir_off) goto not_f;
56 	for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
57 	goto not_f;
58 	fnd:
59 	for (j = i + 1; *j; j++) ;
60 	*i = *(j - 1);
61 	*(j - 1) = NULL;
62 	if (j - 1 == hpfs_inode->i_rddir_off) {
63 		kfree(hpfs_inode->i_rddir_off);
64 		hpfs_inode->i_rddir_off = NULL;
65 	}
66 	return;
67 	not_f:
68 	/*pr_warn("position pointer %p->%08x not found\n",
69 		  pos, (int)*pos);*/
70 	return;
71 }
72 
73 static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
74 			 loff_t p1, loff_t p2)
75 {
76 	struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
77 	loff_t **i;
78 
79 	if (!hpfs_inode->i_rddir_off) return;
80 	for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
81 	return;
82 }
83 
84 static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
85 {
86 	if (*p == f) *p = t;
87 }
88 
89 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
90 {
91 	if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
92 }*/
93 
94 static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
95 {
96 	if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
97 		int n = (*p & 0x3f) + c;
98 		if (n > 0x3f)
99 			pr_err("%s(): %08x + %d\n",
100 				__func__, (int)*p, (int)c >> 8);
101 		else
102 			*p = (*p & ~0x3f) | n;
103 	}
104 }
105 
106 static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
107 {
108 	if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
109 		int n = (*p & 0x3f) - c;
110 		if (n < 1)
111 			pr_err("%s(): %08x - %d\n",
112 				__func__, (int)*p, (int)c >> 8);
113 		else
114 			*p = (*p & ~0x3f) | n;
115 	}
116 }
117 
118 static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
119 {
120 	struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
121 	de_end = dnode_end_de(d);
122 	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
123 		deee = dee; dee = de;
124 	}
125 	return deee;
126 }
127 
128 static struct hpfs_dirent *dnode_last_de(struct dnode *d)
129 {
130 	struct hpfs_dirent *de, *de_end, *dee = NULL;
131 	de_end = dnode_end_de(d);
132 	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
133 		dee = de;
134 	}
135 	return dee;
136 }
137 
138 static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
139 {
140 	struct hpfs_dirent *de;
141 	if (!(de = dnode_last_de(d))) {
142 		hpfs_error(s, "set_last_pointer: empty dnode %08x", le32_to_cpu(d->self));
143 		return;
144 	}
145 	if (hpfs_sb(s)->sb_chk) {
146 		if (de->down) {
147 			hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
148 				le32_to_cpu(d->self), de_down_pointer(de));
149 			return;
150 		}
151 		if (le16_to_cpu(de->length) != 32) {
152 			hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", le32_to_cpu(d->self));
153 			return;
154 		}
155 	}
156 	if (ptr) {
157 		le32_add_cpu(&d->first_free, 4);
158 		if (le32_to_cpu(d->first_free) > 2048) {
159 			hpfs_error(s, "set_last_pointer: too long dnode %08x", le32_to_cpu(d->self));
160 			le32_add_cpu(&d->first_free, -4);
161 			return;
162 		}
163 		de->length = cpu_to_le16(36);
164 		de->down = 1;
165 		*(__le32 *)((char *)de + 32) = cpu_to_le32(ptr);
166 	}
167 }
168 
169 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
170 
171 struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d,
172 				const unsigned char *name,
173 				unsigned namelen, secno down_ptr)
174 {
175 	struct hpfs_dirent *de;
176 	struct hpfs_dirent *de_end = dnode_end_de(d);
177 	unsigned d_size = de_size(namelen, down_ptr);
178 	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
179 		int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
180 		if (!c) {
181 			hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, le32_to_cpu(d->self));
182 			return NULL;
183 		}
184 		if (c < 0) break;
185 	}
186 	memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
187 	memset(de, 0, d_size);
188 	if (down_ptr) {
189 		*(__le32 *)((char *)de + d_size - 4) = cpu_to_le32(down_ptr);
190 		de->down = 1;
191 	}
192 	de->length = cpu_to_le16(d_size);
193 	de->not_8x3 = hpfs_is_name_long(name, namelen);
194 	de->namelen = namelen;
195 	memcpy(de->name, name, namelen);
196 	le32_add_cpu(&d->first_free, d_size);
197 	return de;
198 }
199 
200 /* Delete dirent and don't care about its subtree */
201 
202 static void hpfs_delete_de(struct super_block *s, struct dnode *d,
203 			   struct hpfs_dirent *de)
204 {
205 	if (de->last) {
206 		hpfs_error(s, "attempt to delete last dirent in dnode %08x", le32_to_cpu(d->self));
207 		return;
208 	}
209 	d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) - le16_to_cpu(de->length));
210 	memmove(de, de_next_de(de), le32_to_cpu(d->first_free) + (char *)d - (char *)de);
211 }
212 
213 static void fix_up_ptrs(struct super_block *s, struct dnode *d)
214 {
215 	struct hpfs_dirent *de;
216 	struct hpfs_dirent *de_end = dnode_end_de(d);
217 	dnode_secno dno = le32_to_cpu(d->self);
218 	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
219 		if (de->down) {
220 			struct quad_buffer_head qbh;
221 			struct dnode *dd;
222 			if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
223 				if (le32_to_cpu(dd->up) != dno || dd->root_dnode) {
224 					dd->up = cpu_to_le32(dno);
225 					dd->root_dnode = 0;
226 					hpfs_mark_4buffers_dirty(&qbh);
227 				}
228 				hpfs_brelse4(&qbh);
229 			}
230 		}
231 }
232 
233 /* Add an entry to dnode and do dnode splitting if required */
234 
235 static int hpfs_add_to_dnode(struct inode *i, dnode_secno dno,
236 			     const unsigned char *name, unsigned namelen,
237 			     struct hpfs_dirent *new_de, dnode_secno down_ptr)
238 {
239 	struct quad_buffer_head qbh, qbh1, qbh2;
240 	struct dnode *d, *ad, *rd, *nd = NULL;
241 	dnode_secno adno, rdno;
242 	struct hpfs_dirent *de;
243 	struct hpfs_dirent nde;
244 	unsigned char *nname;
245 	int h;
246 	int pos;
247 	struct buffer_head *bh;
248 	struct fnode *fnode;
249 	int c1, c2 = 0;
250 	if (!(nname = kmalloc(256, GFP_NOFS))) {
251 		pr_err("out of memory, can't add to dnode\n");
252 		return 1;
253 	}
254 	go_up:
255 	if (namelen >= 256) {
256 		hpfs_error(i->i_sb, "%s(): namelen == %d", __func__, namelen);
257 		kfree(nd);
258 		kfree(nname);
259 		return 1;
260 	}
261 	if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
262 		kfree(nd);
263 		kfree(nname);
264 		return 1;
265 	}
266 	go_up_a:
267 	if (hpfs_sb(i->i_sb)->sb_chk)
268 		if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
269 			hpfs_brelse4(&qbh);
270 			kfree(nd);
271 			kfree(nname);
272 			return 1;
273 		}
274 	if (le32_to_cpu(d->first_free) + de_size(namelen, down_ptr) <= 2048) {
275 		loff_t t;
276 		copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
277 		t = get_pos(d, de);
278 		for_all_poss(i, hpfs_pos_ins, t, 1);
279 		for_all_poss(i, hpfs_pos_subst, 4, t);
280 		for_all_poss(i, hpfs_pos_subst, 5, t + 1);
281 		hpfs_mark_4buffers_dirty(&qbh);
282 		hpfs_brelse4(&qbh);
283 		kfree(nd);
284 		kfree(nname);
285 		return 0;
286 	}
287 	if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
288 		/* 0x924 is a max size of dnode after adding a dirent with
289 		   max name length. We alloc this only once. There must
290 		   not be any error while splitting dnodes, otherwise the
291 		   whole directory, not only file we're adding, would
292 		   be lost. */
293 		pr_err("out of memory for dnode splitting\n");
294 		hpfs_brelse4(&qbh);
295 		kfree(nname);
296 		return 1;
297 	}
298 	memcpy(nd, d, le32_to_cpu(d->first_free));
299 	copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
300 	for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
301 	h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
302 	if (!(ad = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &adno, &qbh1))) {
303 		hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
304 		hpfs_brelse4(&qbh);
305 		kfree(nd);
306 		kfree(nname);
307 		return 1;
308 	}
309 	i->i_size += 2048;
310 	i->i_blocks += 4;
311 	pos = 1;
312 	for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
313 		copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
314 		for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
315 		pos++;
316 	}
317 	copy_de(new_de = &nde, de);
318 	memcpy(nname, de->name, de->namelen);
319 	name = nname;
320 	namelen = de->namelen;
321 	for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
322 	down_ptr = adno;
323 	set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
324 	de = de_next_de(de);
325 	memmove((char *)nd + 20, de, le32_to_cpu(nd->first_free) + (char *)nd - (char *)de);
326 	le32_add_cpu(&nd->first_free, -((char *)de - (char *)nd - 20));
327 	memcpy(d, nd, le32_to_cpu(nd->first_free));
328 	for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
329 	fix_up_ptrs(i->i_sb, ad);
330 	if (!d->root_dnode) {
331 		ad->up = d->up;
332 		dno = le32_to_cpu(ad->up);
333 		hpfs_mark_4buffers_dirty(&qbh);
334 		hpfs_brelse4(&qbh);
335 		hpfs_mark_4buffers_dirty(&qbh1);
336 		hpfs_brelse4(&qbh1);
337 		goto go_up;
338 	}
339 	if (!(rd = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &rdno, &qbh2))) {
340 		hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
341 		hpfs_brelse4(&qbh);
342 		hpfs_brelse4(&qbh1);
343 		kfree(nd);
344 		kfree(nname);
345 		return 1;
346 	}
347 	i->i_size += 2048;
348 	i->i_blocks += 4;
349 	rd->root_dnode = 1;
350 	rd->up = d->up;
351 	if (!(fnode = hpfs_map_fnode(i->i_sb, le32_to_cpu(d->up), &bh))) {
352 		hpfs_free_dnode(i->i_sb, rdno);
353 		hpfs_brelse4(&qbh);
354 		hpfs_brelse4(&qbh1);
355 		hpfs_brelse4(&qbh2);
356 		kfree(nd);
357 		kfree(nname);
358 		return 1;
359 	}
360 	fnode->u.external[0].disk_secno = cpu_to_le32(rdno);
361 	mark_buffer_dirty(bh);
362 	brelse(bh);
363 	hpfs_i(i)->i_dno = rdno;
364 	d->up = ad->up = cpu_to_le32(rdno);
365 	d->root_dnode = ad->root_dnode = 0;
366 	hpfs_mark_4buffers_dirty(&qbh);
367 	hpfs_brelse4(&qbh);
368 	hpfs_mark_4buffers_dirty(&qbh1);
369 	hpfs_brelse4(&qbh1);
370 	qbh = qbh2;
371 	set_last_pointer(i->i_sb, rd, dno);
372 	dno = rdno;
373 	d = rd;
374 	goto go_up_a;
375 }
376 
377 /*
378  * Add an entry to directory btree.
379  * I hate such crazy directory structure.
380  * It's easy to read but terrible to write.
381  * I wrote this directory code 4 times.
382  * I hope, now it's finally bug-free.
383  */
384 
385 int hpfs_add_dirent(struct inode *i,
386 		    const unsigned char *name, unsigned namelen,
387 		    struct hpfs_dirent *new_de)
388 {
389 	struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
390 	struct dnode *d;
391 	struct hpfs_dirent *de, *de_end;
392 	struct quad_buffer_head qbh;
393 	dnode_secno dno;
394 	int c;
395 	int c1, c2 = 0;
396 	dno = hpfs_inode->i_dno;
397 	down:
398 	if (hpfs_sb(i->i_sb)->sb_chk)
399 		if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
400 	if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
401 	de_end = dnode_end_de(d);
402 	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
403 		if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
404 			hpfs_brelse4(&qbh);
405 			return -1;
406 		}
407 		if (c < 0) {
408 			if (de->down) {
409 				dno = de_down_pointer(de);
410 				hpfs_brelse4(&qbh);
411 				goto down;
412 			}
413 			break;
414 		}
415 	}
416 	hpfs_brelse4(&qbh);
417 	if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
418 		c = 1;
419 		goto ret;
420 	}
421 	i->i_version++;
422 	c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
423 	ret:
424 	return c;
425 }
426 
427 /*
428  * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
429  * Return the dnode we moved from (to be checked later if it's empty)
430  */
431 
432 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
433 {
434 	dnode_secno dno, ddno;
435 	dnode_secno chk_up = to;
436 	struct dnode *dnode;
437 	struct quad_buffer_head qbh;
438 	struct hpfs_dirent *de, *nde;
439 	int a;
440 	loff_t t;
441 	int c1, c2 = 0;
442 	dno = from;
443 	while (1) {
444 		if (hpfs_sb(i->i_sb)->sb_chk)
445 			if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
446 				return 0;
447 		if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
448 		if (hpfs_sb(i->i_sb)->sb_chk) {
449 			if (le32_to_cpu(dnode->up) != chk_up) {
450 				hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
451 					dno, chk_up, le32_to_cpu(dnode->up));
452 				hpfs_brelse4(&qbh);
453 				return 0;
454 			}
455 			chk_up = dno;
456 		}
457 		if (!(de = dnode_last_de(dnode))) {
458 			hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
459 			hpfs_brelse4(&qbh);
460 			return 0;
461 		}
462 		if (!de->down) break;
463 		dno = de_down_pointer(de);
464 		hpfs_brelse4(&qbh);
465 	}
466 	while (!(de = dnode_pre_last_de(dnode))) {
467 		dnode_secno up = le32_to_cpu(dnode->up);
468 		hpfs_brelse4(&qbh);
469 		hpfs_free_dnode(i->i_sb, dno);
470 		i->i_size -= 2048;
471 		i->i_blocks -= 4;
472 		for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
473 		if (up == to) return to;
474 		if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
475 		if (dnode->root_dnode) {
476 			hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
477 			hpfs_brelse4(&qbh);
478 			return 0;
479 		}
480 		de = dnode_last_de(dnode);
481 		if (!de || !de->down) {
482 			hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
483 			hpfs_brelse4(&qbh);
484 			return 0;
485 		}
486 		le32_add_cpu(&dnode->first_free, -4);
487 		le16_add_cpu(&de->length, -4);
488 		de->down = 0;
489 		hpfs_mark_4buffers_dirty(&qbh);
490 		dno = up;
491 	}
492 	t = get_pos(dnode, de);
493 	for_all_poss(i, hpfs_pos_subst, t, 4);
494 	for_all_poss(i, hpfs_pos_subst, t + 1, 5);
495 	if (!(nde = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
496 		hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
497 		hpfs_brelse4(&qbh);
498 		return 0;
499 	}
500 	memcpy(nde, de, le16_to_cpu(de->length));
501 	ddno = de->down ? de_down_pointer(de) : 0;
502 	hpfs_delete_de(i->i_sb, dnode, de);
503 	set_last_pointer(i->i_sb, dnode, ddno);
504 	hpfs_mark_4buffers_dirty(&qbh);
505 	hpfs_brelse4(&qbh);
506 	a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
507 	kfree(nde);
508 	if (a) return 0;
509 	return dno;
510 }
511 
512 /*
513  * Check if a dnode is empty and delete it from the tree
514  * (chkdsk doesn't like empty dnodes)
515  */
516 
517 static void delete_empty_dnode(struct inode *i, dnode_secno dno)
518 {
519 	struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
520 	struct quad_buffer_head qbh;
521 	struct dnode *dnode;
522 	dnode_secno down, up, ndown;
523 	int p;
524 	struct hpfs_dirent *de;
525 	int c1, c2 = 0;
526 	try_it_again:
527 	if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
528 	if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
529 	if (le32_to_cpu(dnode->first_free) > 56) goto end;
530 	if (le32_to_cpu(dnode->first_free) == 52 || le32_to_cpu(dnode->first_free) == 56) {
531 		struct hpfs_dirent *de_end;
532 		int root = dnode->root_dnode;
533 		up = le32_to_cpu(dnode->up);
534 		de = dnode_first_de(dnode);
535 		down = de->down ? de_down_pointer(de) : 0;
536 		if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
537 			hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
538 			goto end;
539 		}
540 		hpfs_brelse4(&qbh);
541 		hpfs_free_dnode(i->i_sb, dno);
542 		i->i_size -= 2048;
543 		i->i_blocks -= 4;
544 		if (root) {
545 			struct fnode *fnode;
546 			struct buffer_head *bh;
547 			struct dnode *d1;
548 			struct quad_buffer_head qbh1;
549 			if (hpfs_sb(i->i_sb)->sb_chk)
550 				if (up != i->i_ino) {
551 					hpfs_error(i->i_sb,
552 						   "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
553 						   dno, up,
554 						   (unsigned long)i->i_ino);
555 					return;
556 				}
557 			if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
558 				d1->up = cpu_to_le32(up);
559 				d1->root_dnode = 1;
560 				hpfs_mark_4buffers_dirty(&qbh1);
561 				hpfs_brelse4(&qbh1);
562 			}
563 			if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
564 				fnode->u.external[0].disk_secno = cpu_to_le32(down);
565 				mark_buffer_dirty(bh);
566 				brelse(bh);
567 			}
568 			hpfs_inode->i_dno = down;
569 			for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
570 			return;
571 		}
572 		if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
573 		p = 1;
574 		de_end = dnode_end_de(dnode);
575 		for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
576 			if (de->down) if (de_down_pointer(de) == dno) goto fnd;
577 		hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
578 		goto end;
579 		fnd:
580 		for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
581 		if (!down) {
582 			de->down = 0;
583 			le16_add_cpu(&de->length, -4);
584 			le32_add_cpu(&dnode->first_free, -4);
585 			memmove(de_next_de(de), (char *)de_next_de(de) + 4,
586 				(char *)dnode + le32_to_cpu(dnode->first_free) - (char *)de_next_de(de));
587 		} else {
588 			struct dnode *d1;
589 			struct quad_buffer_head qbh1;
590 			*(dnode_secno *) ((void *) de + le16_to_cpu(de->length) - 4) = down;
591 			if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
592 				d1->up = cpu_to_le32(up);
593 				hpfs_mark_4buffers_dirty(&qbh1);
594 				hpfs_brelse4(&qbh1);
595 			}
596 		}
597 	} else {
598 		hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, le32_to_cpu(dnode->first_free));
599 		goto end;
600 	}
601 
602 	if (!de->last) {
603 		struct hpfs_dirent *de_next = de_next_de(de);
604 		struct hpfs_dirent *de_cp;
605 		struct dnode *d1;
606 		struct quad_buffer_head qbh1;
607 		if (!de_next->down) goto endm;
608 		ndown = de_down_pointer(de_next);
609 		if (!(de_cp = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
610 			pr_err("out of memory for dtree balancing\n");
611 			goto endm;
612 		}
613 		memcpy(de_cp, de, le16_to_cpu(de->length));
614 		hpfs_delete_de(i->i_sb, dnode, de);
615 		hpfs_mark_4buffers_dirty(&qbh);
616 		hpfs_brelse4(&qbh);
617 		for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
618 		for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
619 		if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
620 			d1->up = cpu_to_le32(ndown);
621 			hpfs_mark_4buffers_dirty(&qbh1);
622 			hpfs_brelse4(&qbh1);
623 		}
624 		hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
625 		/*pr_info("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n",
626 		  up, ndown, down, dno);*/
627 		dno = up;
628 		kfree(de_cp);
629 		goto try_it_again;
630 	} else {
631 		struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
632 		struct hpfs_dirent *de_cp;
633 		struct dnode *d1;
634 		struct quad_buffer_head qbh1;
635 		dnode_secno dlp;
636 		if (!de_prev) {
637 			hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
638 			hpfs_mark_4buffers_dirty(&qbh);
639 			hpfs_brelse4(&qbh);
640 			dno = up;
641 			goto try_it_again;
642 		}
643 		if (!de_prev->down) goto endm;
644 		ndown = de_down_pointer(de_prev);
645 		if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
646 			struct hpfs_dirent *del = dnode_last_de(d1);
647 			dlp = del->down ? de_down_pointer(del) : 0;
648 			if (!dlp && down) {
649 				if (le32_to_cpu(d1->first_free) > 2044) {
650 					if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
651 						pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
652 						pr_err("terminating balancing operation\n");
653 					}
654 					hpfs_brelse4(&qbh1);
655 					goto endm;
656 				}
657 				if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
658 					pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
659 					pr_err("goin'on\n");
660 				}
661 				le16_add_cpu(&del->length, 4);
662 				del->down = 1;
663 				le32_add_cpu(&d1->first_free, 4);
664 			}
665 			if (dlp && !down) {
666 				le16_add_cpu(&del->length, -4);
667 				del->down = 0;
668 				le32_add_cpu(&d1->first_free, -4);
669 			} else if (down)
670 				*(__le32 *) ((void *) del + le16_to_cpu(del->length) - 4) = cpu_to_le32(down);
671 		} else goto endm;
672 		if (!(de_cp = kmalloc(le16_to_cpu(de_prev->length), GFP_NOFS))) {
673 			pr_err("out of memory for dtree balancing\n");
674 			hpfs_brelse4(&qbh1);
675 			goto endm;
676 		}
677 		hpfs_mark_4buffers_dirty(&qbh1);
678 		hpfs_brelse4(&qbh1);
679 		memcpy(de_cp, de_prev, le16_to_cpu(de_prev->length));
680 		hpfs_delete_de(i->i_sb, dnode, de_prev);
681 		if (!de_prev->down) {
682 			le16_add_cpu(&de_prev->length, 4);
683 			de_prev->down = 1;
684 			le32_add_cpu(&dnode->first_free, 4);
685 		}
686 		*(__le32 *) ((void *) de_prev + le16_to_cpu(de_prev->length) - 4) = cpu_to_le32(ndown);
687 		hpfs_mark_4buffers_dirty(&qbh);
688 		hpfs_brelse4(&qbh);
689 		for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
690 		for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
691 		if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
692 			d1->up = cpu_to_le32(ndown);
693 			hpfs_mark_4buffers_dirty(&qbh1);
694 			hpfs_brelse4(&qbh1);
695 		}
696 		hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
697 		dno = up;
698 		kfree(de_cp);
699 		goto try_it_again;
700 	}
701 	endm:
702 	hpfs_mark_4buffers_dirty(&qbh);
703 	end:
704 	hpfs_brelse4(&qbh);
705 }
706 
707 
708 /* Delete dirent from directory */
709 
710 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
711 		       struct quad_buffer_head *qbh, int depth)
712 {
713 	struct dnode *dnode = qbh->data;
714 	dnode_secno down = 0;
715 	loff_t t;
716 	if (de->first || de->last) {
717 		hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
718 		hpfs_brelse4(qbh);
719 		return 1;
720 	}
721 	if (de->down) down = de_down_pointer(de);
722 	if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
723 		if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
724 			hpfs_brelse4(qbh);
725 			return 2;
726 		}
727 	}
728 	i->i_version++;
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 
743 void 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 
796 static 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 
818 dnode_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 
844 struct 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 
909 struct 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 
950 void 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 
998 struct 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 }
1096