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