1
2
3
4
5
6
7
8
9
10#include <linux/buffer_head.h>
11#include <asm/unaligned.h>
12#include "adfs.h"
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50static DEFINE_RWLOCK(adfs_map_lock);
51
52
53
54
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
66
67
68
69
70static int
71lookup_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
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;
103again:
104 start = mapptr;
105 } while (mapptr < mapsize);
106 return -1;
107
108error:
109 printk(KERN_ERR "adfs: oversized fragment 0x%x at 0x%x-0x%x\n",
110 frag, start, mapptr);
111 return -1;
112
113found:
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
126
127
128
129
130static unsigned int
131scan_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
144
145 frag = GET_FRAG_ID(map, start, idmask);
146
147
148
149
150
151 if (frag == 0)
152 return 0;
153
154 do {
155 start += frag;
156
157
158
159
160 frag = GET_FRAG_ID(map, start, idmask);
161 mapptr = start + idlen;
162
163
164
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;
186error:
187 printk(KERN_ERR "adfs: oversized free fragment\n");
188 return 0;
189}
190
191static int
192scan_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;
215found:
216 result -= dm->dm_startbit;
217 result += dm->dm_startblk;
218
219 return result;
220}
221
222
223
224
225
226
227
228
229unsigned int
230adfs_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
247int
248adfs_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
257
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
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
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
286bad_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