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