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