Root/
1 | /* |
2 | * linux/fs/adfs/map.c |
3 | * |
4 | * Copyright (C) 1997-2002 Russell King |
5 | * |
6 | * This program is free software; you can redistribute it and/or modify |
7 | * it under the terms of the GNU General Public License version 2 as |
8 | * published by the Free Software Foundation. |
9 | */ |
10 | #include <linux/buffer_head.h> |
11 | #include <asm/unaligned.h> |
12 | #include "adfs.h" |
13 | |
14 | /* |
15 | * The ADFS map is basically a set of sectors. Each sector is called a |
16 | * zone which contains a bitstream made up of variable sized fragments. |
17 | * Each bit refers to a set of bytes in the filesystem, defined by |
18 | * log2bpmb. This may be larger or smaller than the sector size, but |
19 | * the overall size it describes will always be a round number of |
20 | * sectors. A fragment id is always idlen bits long. |
21 | * |
22 | * < idlen > < n > <1> |
23 | * +---------+-------//---------+---+ |
24 | * | frag id | 0000....000000 | 1 | |
25 | * +---------+-------//---------+---+ |
26 | * |
27 | * The physical disk space used by a fragment is taken from the start of |
28 | * the fragment id up to and including the '1' bit - ie, idlen + n + 1 |
29 | * bits. |
30 | * |
31 | * A fragment id can be repeated multiple times in the whole map for |
32 | * large or fragmented files. The first map zone a fragment starts in |
33 | * is given by fragment id / ids_per_zone - this allows objects to start |
34 | * from any zone on the disk. |
35 | * |
36 | * Free space is described by a linked list of fragments. Each free |
37 | * fragment describes free space in the same way as the other fragments, |
38 | * however, the frag id specifies an offset (in map bits) from the end |
39 | * of this fragment to the start of the next free fragment. |
40 | * |
41 | * Objects stored on the disk are allocated object ids (we use these as |
42 | * our inode numbers.) Object ids contain a fragment id and an optional |
43 | * offset. This allows a directory fragment to contain small files |
44 | * associated with that directory. |
45 | */ |
46 | |
47 | /* |
48 | * For the future... |
49 | */ |
50 | static DEFINE_RWLOCK(adfs_map_lock); |
51 | |
52 | /* |
53 | * This is fun. We need to load up to 19 bits from the map at an |
54 | * arbitary bit alignment. (We're limited to 19 bits by F+ version 2). |
55 | */ |
56 | #define GET_FRAG_ID(_map,_start,_idmask) \ |
57 | ({ \ |
58 | unsigned char *_m = _map + (_start >> 3); \ |
59 | u32 _frag = get_unaligned_le32(_m); \ |
60 | _frag >>= (_start & 7); \ |
61 | _frag & _idmask; \ |
62 | }) |
63 | |
64 | /* |
65 | * return the map bit offset of the fragment frag_id in the zone dm. |
66 | * Note that the loop is optimised for best asm code - look at the |
67 | * output of: |
68 | * gcc -D__KERNEL__ -O2 -I../../include -o - -S map.c |
69 | */ |
70 | static int |
71 | lookup_zone(const struct adfs_discmap *dm, const unsigned int idlen, |
72 | const unsigned int frag_id, unsigned int *offset) |
73 | { |
74 | const unsigned int mapsize = dm->dm_endbit; |
75 | const u32 idmask = (1 << idlen) - 1; |
76 | unsigned char *map = dm->dm_bh->b_data + 4; |
77 | unsigned int start = dm->dm_startbit; |
78 | unsigned int mapptr; |
79 | u32 frag; |
80 | |
81 | do { |
82 | frag = GET_FRAG_ID(map, start, idmask); |
83 | mapptr = start + idlen; |
84 | |
85 | /* |
86 | * find end of fragment |
87 | */ |
88 | { |
89 | __le32 *_map = (__le32 *)map; |
90 | u32 v = le32_to_cpu(_map[mapptr >> 5]) >> (mapptr & 31); |
91 | while (v == 0) { |
92 | mapptr = (mapptr & ~31) + 32; |
93 | if (mapptr >= mapsize) |
94 | goto error; |
95 | v = le32_to_cpu(_map[mapptr >> 5]); |
96 | } |
97 | |
98 | mapptr += 1 + ffz(~v); |
99 | } |
100 | |
101 | if (frag == frag_id) |
102 | goto found; |
103 | again: |
104 | start = mapptr; |
105 | } while (mapptr < mapsize); |
106 | return -1; |
107 | |
108 | error: |
109 | printk(KERN_ERR "adfs: oversized fragment 0x%x at 0x%x-0x%x\n", |
110 | frag, start, mapptr); |
111 | return -1; |
112 | |
113 | found: |
114 | { |
115 | int length = mapptr - start; |
116 | if (*offset >= length) { |
117 | *offset -= length; |
118 | goto again; |
119 | } |
120 | } |
121 | return start + *offset; |
122 | } |
123 | |
124 | /* |
125 | * Scan the free space map, for this zone, calculating the total |
126 | * number of map bits in each free space fragment. |
127 | * |
128 | * Note: idmask is limited to 15 bits [3.2] |
129 | */ |
130 | static unsigned int |
131 | scan_free_map(struct adfs_sb_info *asb, struct adfs_discmap *dm) |
132 | { |
133 | const unsigned int mapsize = dm->dm_endbit + 32; |
134 | const unsigned int idlen = asb->s_idlen; |
135 | const unsigned int frag_idlen = idlen <= 15 ? idlen : 15; |
136 | const u32 idmask = (1 << frag_idlen) - 1; |
137 | unsigned char *map = dm->dm_bh->b_data; |
138 | unsigned int start = 8, mapptr; |
139 | u32 frag; |
140 | unsigned long total = 0; |
141 | |
142 | /* |
143 | * get fragment id |
144 | */ |
145 | frag = GET_FRAG_ID(map, start, idmask); |
146 | |
147 | /* |
148 | * If the freelink is null, then no free fragments |
149 | * exist in this zone. |
150 | */ |
151 | if (frag == 0) |
152 | return 0; |
153 | |
154 | do { |
155 | start += frag; |
156 | |
157 | /* |
158 | * get fragment id |
159 | */ |
160 | frag = GET_FRAG_ID(map, start, idmask); |
161 | mapptr = start + idlen; |
162 | |
163 | /* |
164 | * find end of fragment |
165 | */ |
166 | { |
167 | __le32 *_map = (__le32 *)map; |
168 | u32 v = le32_to_cpu(_map[mapptr >> 5]) >> (mapptr & 31); |
169 | while (v == 0) { |
170 | mapptr = (mapptr & ~31) + 32; |
171 | if (mapptr >= mapsize) |
172 | goto error; |
173 | v = le32_to_cpu(_map[mapptr >> 5]); |
174 | } |
175 | |
176 | mapptr += 1 + ffz(~v); |
177 | } |
178 | |
179 | total += mapptr - start; |
180 | } while (frag >= idlen + 1); |
181 | |
182 | if (frag != 0) |
183 | printk(KERN_ERR "adfs: undersized free fragment\n"); |
184 | |
185 | return total; |
186 | error: |
187 | printk(KERN_ERR "adfs: oversized free fragment\n"); |
188 | return 0; |
189 | } |
190 | |
191 | static int |
192 | scan_map(struct adfs_sb_info *asb, unsigned int zone, |
193 | const unsigned int frag_id, unsigned int mapoff) |
194 | { |
195 | const unsigned int idlen = asb->s_idlen; |
196 | struct adfs_discmap *dm, *dm_end; |
197 | int result; |
198 | |
199 | dm = asb->s_map + zone; |
200 | zone = asb->s_map_size; |
201 | dm_end = asb->s_map + zone; |
202 | |
203 | do { |
204 | result = lookup_zone(dm, idlen, frag_id, &mapoff); |
205 | |
206 | if (result != -1) |
207 | goto found; |
208 | |
209 | dm ++; |
210 | if (dm == dm_end) |
211 | dm = asb->s_map; |
212 | } while (--zone > 0); |
213 | |
214 | return -1; |
215 | found: |
216 | result -= dm->dm_startbit; |
217 | result += dm->dm_startblk; |
218 | |
219 | return result; |
220 | } |
221 | |
222 | /* |
223 | * calculate the amount of free blocks in the map. |
224 | * |
225 | * n=1 |
226 | * total_free = E(free_in_zone_n) |
227 | * nzones |
228 | */ |
229 | unsigned int |
230 | adfs_map_free(struct super_block *sb) |
231 | { |
232 | struct adfs_sb_info *asb = ADFS_SB(sb); |
233 | struct adfs_discmap *dm; |
234 | unsigned int total = 0; |
235 | unsigned int zone; |
236 | |
237 | dm = asb->s_map; |
238 | zone = asb->s_map_size; |
239 | |
240 | do { |
241 | total += scan_free_map(asb, dm++); |
242 | } while (--zone > 0); |
243 | |
244 | return signed_asl(total, asb->s_map2blk); |
245 | } |
246 | |
247 | int |
248 | adfs_map_lookup(struct super_block *sb, unsigned int frag_id, |
249 | unsigned int offset) |
250 | { |
251 | struct adfs_sb_info *asb = ADFS_SB(sb); |
252 | unsigned int zone, mapoff; |
253 | int result; |
254 | |
255 | /* |
256 | * map & root fragment is special - it starts in the center of the |
257 | * disk. The other fragments start at zone (frag / ids_per_zone) |
258 | */ |
259 | if (frag_id == ADFS_ROOT_FRAG) |
260 | zone = asb->s_map_size >> 1; |
261 | else |
262 | zone = frag_id / asb->s_ids_per_zone; |
263 | |
264 | if (zone >= asb->s_map_size) |
265 | goto bad_fragment; |
266 | |
267 | /* Convert sector offset to map offset */ |
268 | mapoff = signed_asl(offset, -asb->s_map2blk); |
269 | |
270 | read_lock(&adfs_map_lock); |
271 | result = scan_map(asb, zone, frag_id, mapoff); |
272 | read_unlock(&adfs_map_lock); |
273 | |
274 | if (result > 0) { |
275 | unsigned int secoff; |
276 | |
277 | /* Calculate sector offset into map block */ |
278 | secoff = offset - signed_asl(mapoff, asb->s_map2blk); |
279 | return secoff + signed_asl(result, asb->s_map2blk); |
280 | } |
281 | |
282 | adfs_error(sb, "fragment 0x%04x at offset %d not found in map", |
283 | frag_id, offset); |
284 | return 0; |
285 | |
286 | bad_fragment: |
287 | adfs_error(sb, "invalid fragment 0x%04x (zone = %d, max = %d)", |
288 | frag_id, zone, asb->s_map_size); |
289 | return 0; |
290 | } |
291 |
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