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