1 /*
2  *  linux/fs/hpfs/anode.c
3  *
4  *  Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
5  *
6  *  handling HPFS anode tree that contains file allocation info
7  */
8 
9 #include "hpfs_fn.h"
10 
11 /* Find a sector in allocation tree */
12 
hpfs_bplus_lookup(struct super_block * s,struct inode * inode,struct bplus_header * btree,unsigned sec,struct buffer_head * bh)13 secno hpfs_bplus_lookup(struct super_block *s, struct inode *inode,
14 		   struct bplus_header *btree, unsigned sec,
15 		   struct buffer_head *bh)
16 {
17 	anode_secno a = -1;
18 	struct anode *anode;
19 	int i;
20 	int c1, c2 = 0;
21 	go_down:
22 	if (s->s_hpfs_chk) if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_bplus_lookup")) return -1;
23 	if (btree->internal) {
24 		for (i = 0; i < btree->n_used_nodes; i++)
25 			if (btree->u.internal[i].file_secno > sec) {
26 				a = btree->u.internal[i].down;
27 				brelse(bh);
28 				if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
29 				btree = &anode->btree;
30 				goto go_down;
31 			}
32 		hpfs_error(s, "sector %08x not found in internal anode %08x", sec, a);
33 		brelse(bh);
34 		return -1;
35 	}
36 	for (i = 0; i < btree->n_used_nodes; i++)
37 		if (btree->u.external[i].file_secno <= sec &&
38 		    btree->u.external[i].file_secno + btree->u.external[i].length > sec) {
39 			a = btree->u.external[i].disk_secno + sec - btree->u.external[i].file_secno;
40 			if (s->s_hpfs_chk) if (hpfs_chk_sectors(s, a, 1, "data")) {
41 				brelse(bh);
42 				return -1;
43 			}
44 			if (inode) {
45 				inode->i_hpfs_file_sec = btree->u.external[i].file_secno;
46 				inode->i_hpfs_disk_sec = btree->u.external[i].disk_secno;
47 				inode->i_hpfs_n_secs = btree->u.external[i].length;
48 			}
49 			brelse(bh);
50 			return a;
51 		}
52 	hpfs_error(s, "sector %08x not found in external anode %08x", sec, a);
53 	brelse(bh);
54 	return -1;
55 }
56 
57 /* Add a sector to tree */
58 
hpfs_add_sector_to_btree(struct super_block * s,secno node,int fnod,unsigned fsecno)59 secno hpfs_add_sector_to_btree(struct super_block *s, secno node, int fnod, unsigned fsecno)
60 {
61 	struct bplus_header *btree;
62 	struct anode *anode = NULL, *ranode = NULL;
63 	struct fnode *fnode;
64 	anode_secno a, na = -1, ra, up = -1;
65 	secno se;
66 	struct buffer_head *bh, *bh1, *bh2;
67 	int n;
68 	unsigned fs;
69 	int c1, c2 = 0;
70 	if (fnod) {
71 		if (!(fnode = hpfs_map_fnode(s, node, &bh))) return -1;
72 		btree = &fnode->btree;
73 	} else {
74 		if (!(anode = hpfs_map_anode(s, node, &bh))) return -1;
75 		btree = &anode->btree;
76 	}
77 	a = node;
78 	go_down:
79 	if ((n = btree->n_used_nodes - 1) < -!!fnod) {
80 		hpfs_error(s, "anode %08x has no entries", a);
81 		brelse(bh);
82 		return -1;
83 	}
84 	if (btree->internal) {
85 		a = btree->u.internal[n].down;
86 		btree->u.internal[n].file_secno = -1;
87 		mark_buffer_dirty(bh);
88 		brelse(bh);
89 		if (s->s_hpfs_chk)
90 			if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_add_sector_to_btree #1")) return -1;
91 		if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
92 		btree = &anode->btree;
93 		goto go_down;
94 	}
95 	if (n >= 0) {
96 		if (btree->u.external[n].file_secno + btree->u.external[n].length != fsecno) {
97 			hpfs_error(s, "allocated size %08x, trying to add sector %08x, %cnode %08x",
98 				btree->u.external[n].file_secno + btree->u.external[n].length, fsecno,
99 				fnod?'f':'a', node);
100 			brelse(bh);
101 			return -1;
102 		}
103 		if (hpfs_alloc_if_possible(s, se = btree->u.external[n].disk_secno + btree->u.external[n].length)) {
104 			btree->u.external[n].length++;
105 			mark_buffer_dirty(bh);
106 			brelse(bh);
107 			return se;
108 		}
109 	} else {
110 		if (fsecno) {
111 			hpfs_error(s, "empty file %08x, trying to add sector %08x", node, fsecno);
112 			brelse(bh);
113 			return -1;
114 		}
115 		se = !fnod ? node : (node + 16384) & ~16383;
116 	}
117 	if (!(se = hpfs_alloc_sector(s, se, 1, fsecno*ALLOC_M>ALLOC_FWD_MAX ? ALLOC_FWD_MAX : fsecno*ALLOC_M<ALLOC_FWD_MIN ? ALLOC_FWD_MIN : fsecno*ALLOC_M, 1))) {
118 		brelse(bh);
119 		return -1;
120 	}
121 	fs = n < 0 ? 0 : btree->u.external[n].file_secno + btree->u.external[n].length;
122 	if (!btree->n_free_nodes) {
123 		up = a != node ? anode->up : -1;
124 		if (!(anode = hpfs_alloc_anode(s, a, &na, &bh1))) {
125 			brelse(bh);
126 			hpfs_free_sectors(s, se, 1);
127 			return -1;
128 		}
129 		if (a == node && fnod) {
130 			anode->up = node;
131 			anode->btree.fnode_parent = 1;
132 			anode->btree.n_used_nodes = btree->n_used_nodes;
133 			anode->btree.first_free = btree->first_free;
134 			anode->btree.n_free_nodes = 40 - anode->btree.n_used_nodes;
135 			memcpy(&anode->u, &btree->u, btree->n_used_nodes * 12);
136 			btree->internal = 1;
137 			btree->n_free_nodes = 11;
138 			btree->n_used_nodes = 1;
139 			btree->first_free = (char *)&(btree->u.internal[1]) - (char *)btree;
140 			btree->u.internal[0].file_secno = -1;
141 			btree->u.internal[0].down = na;
142 			mark_buffer_dirty(bh);
143 		} else if (!(ranode = hpfs_alloc_anode(s, /*a*/0, &ra, &bh2))) {
144 			brelse(bh);
145 			brelse(bh1);
146 			hpfs_free_sectors(s, se, 1);
147 			hpfs_free_sectors(s, na, 1);
148 			return -1;
149 		}
150 		brelse(bh);
151 		bh = bh1;
152 		btree = &anode->btree;
153 	}
154 	btree->n_free_nodes--; n = btree->n_used_nodes++;
155 	btree->first_free += 12;
156 	btree->u.external[n].disk_secno = se;
157 	btree->u.external[n].file_secno = fs;
158 	btree->u.external[n].length = 1;
159 	mark_buffer_dirty(bh);
160 	brelse(bh);
161 	if ((a == node && fnod) || na == -1) return se;
162 	c2 = 0;
163 	while (up != -1) {
164 		struct anode *new_anode;
165 		if (s->s_hpfs_chk)
166 			if (hpfs_stop_cycles(s, up, &c1, &c2, "hpfs_add_sector_to_btree #2")) return -1;
167 		if (up != node || !fnod) {
168 			if (!(anode = hpfs_map_anode(s, up, &bh))) return -1;
169 			btree = &anode->btree;
170 		} else {
171 			if (!(fnode = hpfs_map_fnode(s, up, &bh))) return -1;
172 			btree = &fnode->btree;
173 		}
174 		if (btree->n_free_nodes) {
175 			btree->n_free_nodes--; n = btree->n_used_nodes++;
176 			btree->first_free += 8;
177 			btree->u.internal[n].file_secno = -1;
178 			btree->u.internal[n].down = na;
179 			btree->u.internal[n-1].file_secno = fs;
180 			mark_buffer_dirty(bh);
181 			brelse(bh);
182 			brelse(bh2);
183 			hpfs_free_sectors(s, ra, 1);
184 			if ((anode = hpfs_map_anode(s, na, &bh))) {
185 				anode->up = up;
186 				anode->btree.fnode_parent = up == node && fnod;
187 				mark_buffer_dirty(bh);
188 				brelse(bh);
189 			}
190 			return se;
191 		}
192 		up = up != node ? anode->up : -1;
193 		btree->u.internal[btree->n_used_nodes - 1].file_secno = /*fs*/-1;
194 		mark_buffer_dirty(bh);
195 		brelse(bh);
196 		a = na;
197 		if ((new_anode = hpfs_alloc_anode(s, a, &na, &bh))) {
198 			anode = new_anode;
199 			/*anode->up = up != -1 ? up : ra;*/
200 			anode->btree.internal = 1;
201 			anode->btree.n_used_nodes = 1;
202 			anode->btree.n_free_nodes = 59;
203 			anode->btree.first_free = 16;
204 			anode->btree.u.internal[0].down = a;
205 			anode->btree.u.internal[0].file_secno = -1;
206 			mark_buffer_dirty(bh);
207 			brelse(bh);
208 			if ((anode = hpfs_map_anode(s, a, &bh))) {
209 				anode->up = na;
210 				mark_buffer_dirty(bh);
211 				brelse(bh);
212 			}
213 		} else na = a;
214 	}
215 	if ((anode = hpfs_map_anode(s, na, &bh))) {
216 		anode->up = node;
217 		if (fnod) anode->btree.fnode_parent = 1;
218 		mark_buffer_dirty(bh);
219 		brelse(bh);
220 	}
221 	if (!fnod) {
222 		if (!(anode = hpfs_map_anode(s, node, &bh))) {
223 			brelse(bh2);
224 			return -1;
225 		}
226 		btree = &anode->btree;
227 	} else {
228 		if (!(fnode = hpfs_map_fnode(s, node, &bh))) {
229 			brelse(bh2);
230 			return -1;
231 		}
232 		btree = &fnode->btree;
233 	}
234 	ranode->up = node;
235 	memcpy(&ranode->btree, btree, btree->first_free);
236 	if (fnod) ranode->btree.fnode_parent = 1;
237 	ranode->btree.n_free_nodes = (ranode->btree.internal ? 60 : 40) - ranode->btree.n_used_nodes;
238 	if (ranode->btree.internal) for (n = 0; n < ranode->btree.n_used_nodes; n++) {
239 		struct anode *unode;
240 		if ((unode = hpfs_map_anode(s, ranode->u.internal[n].down, &bh1))) {
241 			unode->up = ra;
242 			unode->btree.fnode_parent = 0;
243 			mark_buffer_dirty(bh1);
244 			brelse(bh1);
245 		}
246 	}
247 	btree->internal = 1;
248 	btree->n_free_nodes = fnod ? 10 : 58;
249 	btree->n_used_nodes = 2;
250 	btree->first_free = (char *)&btree->u.internal[2] - (char *)btree;
251 	btree->u.internal[0].file_secno = fs;
252 	btree->u.internal[0].down = ra;
253 	btree->u.internal[1].file_secno = -1;
254 	btree->u.internal[1].down = na;
255 	mark_buffer_dirty(bh);
256 	brelse(bh);
257 	mark_buffer_dirty(bh2);
258 	brelse(bh2);
259 	return se;
260 }
261 
262 /*
263  * Remove allocation tree. Recursion would look much nicer but
264  * I want to avoid it because it can cause stack overflow.
265  */
266 
hpfs_remove_btree(struct super_block * s,struct bplus_header * btree)267 void hpfs_remove_btree(struct super_block *s, struct bplus_header *btree)
268 {
269 	struct bplus_header *btree1 = btree;
270 	struct anode *anode = NULL;
271 	anode_secno ano = 0, oano;
272 	struct buffer_head *bh;
273 	int level = 0;
274 	int pos = 0;
275 	int i;
276 	int c1, c2 = 0;
277 	int d1, d2;
278 	go_down:
279 	d2 = 0;
280 	while (btree1->internal) {
281 		ano = btree1->u.internal[pos].down;
282 		if (level) brelse(bh);
283 		if (s->s_hpfs_chk)
284 			if (hpfs_stop_cycles(s, ano, &d1, &d2, "hpfs_remove_btree #1"))
285 				return;
286 		if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
287 		btree1 = &anode->btree;
288 		level++;
289 		pos = 0;
290 	}
291 	for (i = 0; i < btree1->n_used_nodes; i++)
292 		hpfs_free_sectors(s, btree1->u.external[i].disk_secno, btree1->u.external[i].length);
293 	go_up:
294 	if (!level) return;
295 	brelse(bh);
296 	if (s->s_hpfs_chk)
297 		if (hpfs_stop_cycles(s, ano, &c1, &c2, "hpfs_remove_btree #2")) return;
298 	hpfs_free_sectors(s, ano, 1);
299 	oano = ano;
300 	ano = anode->up;
301 	if (--level) {
302 		if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
303 		btree1 = &anode->btree;
304 	} else btree1 = btree;
305 	for (i = 0; i < btree1->n_used_nodes; i++) {
306 		if (btree1->u.internal[i].down == oano) {
307 			if ((pos = i + 1) < btree1->n_used_nodes)
308 				goto go_down;
309 			else
310 				goto go_up;
311 		}
312 	}
313 	hpfs_error(s,
314 		   "reference to anode %08x not found in anode %08x "
315 		   "(probably bad up pointer)",
316 		   oano, level ? ano : -1);
317 	if (level)
318 		brelse(bh);
319 }
320 
321 /* Just a wrapper around hpfs_bplus_lookup .. used for reading eas */
322 
anode_lookup(struct super_block * s,anode_secno a,unsigned sec)323 static secno anode_lookup(struct super_block *s, anode_secno a, unsigned sec)
324 {
325 	struct anode *anode;
326 	struct buffer_head *bh;
327 	if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
328 	return hpfs_bplus_lookup(s, NULL, &anode->btree, sec, bh);
329 }
330 
hpfs_ea_read(struct super_block * s,secno a,int ano,unsigned pos,unsigned len,char * buf)331 int hpfs_ea_read(struct super_block *s, secno a, int ano, unsigned pos,
332 	    unsigned len, char *buf)
333 {
334 	struct buffer_head *bh;
335 	char *data;
336 	secno sec;
337 	unsigned l;
338 	while (len) {
339 		if (ano) {
340 			if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
341 				return -1;
342 		} else sec = a + (pos >> 9);
343 		if (s->s_hpfs_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #1")) return -1;
344 		if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
345 			return -1;
346 		l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
347 		memcpy(buf, data + (pos & 0x1ff), l);
348 		brelse(bh);
349 		buf += l; pos += l; len -= l;
350 	}
351 	return 0;
352 }
353 
hpfs_ea_write(struct super_block * s,secno a,int ano,unsigned pos,unsigned len,char * buf)354 int hpfs_ea_write(struct super_block *s, secno a, int ano, unsigned pos,
355 	     unsigned len, char *buf)
356 {
357 	struct buffer_head *bh;
358 	char *data;
359 	secno sec;
360 	unsigned l;
361 	while (len) {
362 		if (ano) {
363 			if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
364 				return -1;
365 		} else sec = a + (pos >> 9);
366 		if (s->s_hpfs_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #2")) return -1;
367 		if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
368 			return -1;
369 		l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
370 		memcpy(data + (pos & 0x1ff), buf, l);
371 		mark_buffer_dirty(bh);
372 		brelse(bh);
373 		buf += l; pos += l; len -= l;
374 	}
375 	return 0;
376 }
377 
hpfs_ea_remove(struct super_block * s,secno a,int ano,unsigned len)378 void hpfs_ea_remove(struct super_block *s, secno a, int ano, unsigned len)
379 {
380 	struct anode *anode;
381 	struct buffer_head *bh;
382 	if (ano) {
383 		if (!(anode = hpfs_map_anode(s, a, &bh))) return;
384 		hpfs_remove_btree(s, &anode->btree);
385 		brelse(bh);
386 		hpfs_free_sectors(s, a, 1);
387 	} else hpfs_free_sectors(s, a, (len + 511) >> 9);
388 }
389 
390 /* Truncate allocation tree. Doesn't join anodes - I hope it doesn't matter */
391 
hpfs_truncate_btree(struct super_block * s,secno f,int fno,unsigned secs)392 void hpfs_truncate_btree(struct super_block *s, secno f, int fno, unsigned secs)
393 {
394 	struct fnode *fnode;
395 	struct anode *anode;
396 	struct buffer_head *bh;
397 	struct bplus_header *btree;
398 	anode_secno node = f;
399 	int i, j, nodes;
400 	int c1, c2 = 0;
401 	if (fno) {
402 		if (!(fnode = hpfs_map_fnode(s, f, &bh))) return;
403 		btree = &fnode->btree;
404 	} else {
405 		if (!(anode = hpfs_map_anode(s, f, &bh))) return;
406 		btree = &anode->btree;
407 	}
408 	if (!secs) {
409 		hpfs_remove_btree(s, btree);
410 		if (fno) {
411 			btree->n_free_nodes = 8;
412 			btree->n_used_nodes = 0;
413 			btree->first_free = 8;
414 			btree->internal = 0;
415 			mark_buffer_dirty(bh);
416 		} else hpfs_free_sectors(s, f, 1);
417 		brelse(bh);
418 		return;
419 	}
420 	while (btree->internal) {
421 		nodes = btree->n_used_nodes + btree->n_free_nodes;
422 		for (i = 0; i < btree->n_used_nodes; i++)
423 			if (btree->u.internal[i].file_secno >= secs) goto f;
424 		brelse(bh);
425 		hpfs_error(s, "internal btree %08x doesn't end with -1", node);
426 		return;
427 		f:
428 		for (j = i + 1; j < btree->n_used_nodes; j++)
429 			hpfs_ea_remove(s, btree->u.internal[j].down, 1, 0);
430 		btree->n_used_nodes = i + 1;
431 		btree->n_free_nodes = nodes - btree->n_used_nodes;
432 		btree->first_free = 8 + 8 * btree->n_used_nodes;
433 		mark_buffer_dirty(bh);
434 		if (btree->u.internal[i].file_secno == secs) {
435 			brelse(bh);
436 			return;
437 		}
438 		node = btree->u.internal[i].down;
439 		brelse(bh);
440 		if (s->s_hpfs_chk)
441 			if (hpfs_stop_cycles(s, node, &c1, &c2, "hpfs_truncate_btree"))
442 				return;
443 		if (!(anode = hpfs_map_anode(s, node, &bh))) return;
444 		btree = &anode->btree;
445 	}
446 	nodes = btree->n_used_nodes + btree->n_free_nodes;
447 	for (i = 0; i < btree->n_used_nodes; i++)
448 		if (btree->u.external[i].file_secno + btree->u.external[i].length >= secs) goto ff;
449 	brelse(bh);
450 	return;
451 	ff:
452 	if (secs <= btree->u.external[i].file_secno) {
453 		hpfs_error(s, "there is an allocation error in file %08x, sector %08x", f, secs);
454 		if (i) i--;
455 	}
456 	else if (btree->u.external[i].file_secno + btree->u.external[i].length > secs) {
457 		hpfs_free_sectors(s, btree->u.external[i].disk_secno + secs -
458 			btree->u.external[i].file_secno, btree->u.external[i].length
459 			- secs + btree->u.external[i].file_secno); /* I hope gcc optimizes this :-) */
460 		btree->u.external[i].length = secs - btree->u.external[i].file_secno;
461 	}
462 	for (j = i + 1; j < btree->n_used_nodes; j++)
463 		hpfs_free_sectors(s, btree->u.external[j].disk_secno, btree->u.external[j].length);
464 	btree->n_used_nodes = i + 1;
465 	btree->n_free_nodes = nodes - btree->n_used_nodes;
466 	btree->first_free = 8 + 12 * btree->n_used_nodes;
467 	mark_buffer_dirty(bh);
468 	brelse(bh);
469 }
470 
471 /* Remove file or directory and it's eas - note that directory must
472    be empty when this is called. */
473 
hpfs_remove_fnode(struct super_block * s,fnode_secno fno)474 void hpfs_remove_fnode(struct super_block *s, fnode_secno fno)
475 {
476 	struct buffer_head *bh;
477 	struct fnode *fnode;
478 	struct extended_attribute *ea;
479 	struct extended_attribute *ea_end;
480 	if (!(fnode = hpfs_map_fnode(s, fno, &bh))) return;
481 	if (!fnode->dirflag) hpfs_remove_btree(s, &fnode->btree);
482 	else hpfs_remove_dtree(s, fnode->u.external[0].disk_secno);
483 	ea_end = fnode_end_ea(fnode);
484 	for (ea = fnode_ea(fnode); ea < ea_end; ea = next_ea(ea))
485 		if (ea->indirect)
486 			hpfs_ea_remove(s, ea_sec(ea), ea->anode, ea_len(ea));
487 	hpfs_ea_ext_remove(s, fnode->ea_secno, fnode->ea_anode, fnode->ea_size_l);
488 	brelse(bh);
489 	hpfs_free_sectors(s, fno, 1);
490 }
491