1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * linux/fs/adfs/map.c |
4 | * |
5 | * Copyright (C) 1997-2002 Russell King |
6 | */ |
7 | #include <linux/slab.h> |
8 | #include <linux/statfs.h> |
9 | #include <asm/unaligned.h> |
10 | #include "adfs.h" |
11 | |
12 | /* |
13 | * The ADFS map is basically a set of sectors. Each sector is called a |
14 | * zone which contains a bitstream made up of variable sized fragments. |
15 | * Each bit refers to a set of bytes in the filesystem, defined by |
16 | * log2bpmb. This may be larger or smaller than the sector size, but |
17 | * the overall size it describes will always be a round number of |
18 | * sectors. A fragment id is always idlen bits long. |
19 | * |
20 | * < idlen > < n > <1> |
21 | * +---------+-------//---------+---+ |
22 | * | frag id | 0000....000000 | 1 | |
23 | * +---------+-------//---------+---+ |
24 | * |
25 | * The physical disk space used by a fragment is taken from the start of |
26 | * the fragment id up to and including the '1' bit - ie, idlen + n + 1 |
27 | * bits. |
28 | * |
29 | * A fragment id can be repeated multiple times in the whole map for |
30 | * large or fragmented files. The first map zone a fragment starts in |
31 | * is given by fragment id / ids_per_zone - this allows objects to start |
32 | * from any zone on the disk. |
33 | * |
34 | * Free space is described by a linked list of fragments. Each free |
35 | * fragment describes free space in the same way as the other fragments, |
36 | * however, the frag id specifies an offset (in map bits) from the end |
37 | * of this fragment to the start of the next free fragment. |
38 | * |
39 | * Objects stored on the disk are allocated object ids (we use these as |
40 | * our inode numbers.) Object ids contain a fragment id and an optional |
41 | * offset. This allows a directory fragment to contain small files |
42 | * associated with that directory. |
43 | */ |
44 | |
45 | /* |
46 | * For the future... |
47 | */ |
48 | static DEFINE_RWLOCK(adfs_map_lock); |
49 | |
50 | /* |
51 | * This is fun. We need to load up to 19 bits from the map at an |
52 | * arbitrary bit alignment. (We're limited to 19 bits by F+ version 2). |
53 | */ |
54 | #define GET_FRAG_ID(_map,_start,_idmask) \ |
55 | ({ \ |
56 | unsigned char *_m = _map + (_start >> 3); \ |
57 | u32 _frag = get_unaligned_le32(_m); \ |
58 | _frag >>= (_start & 7); \ |
59 | _frag & _idmask; \ |
60 | }) |
61 | |
62 | /* |
63 | * return the map bit offset of the fragment frag_id in the zone dm. |
64 | * Note that the loop is optimised for best asm code - look at the |
65 | * output of: |
66 | * gcc -D__KERNEL__ -O2 -I../../include -o - -S map.c |
67 | */ |
68 | static int lookup_zone(const struct adfs_discmap *dm, const unsigned int idlen, |
69 | const u32 frag_id, unsigned int *offset) |
70 | { |
71 | const unsigned int endbit = dm->dm_endbit; |
72 | const u32 idmask = (1 << idlen) - 1; |
73 | unsigned char *map = dm->dm_bh->b_data; |
74 | unsigned int start = dm->dm_startbit; |
75 | unsigned int freelink, fragend; |
76 | u32 frag; |
77 | |
78 | frag = GET_FRAG_ID(map, 8, idmask & 0x7fff); |
79 | freelink = frag ? 8 + frag : 0; |
80 | |
81 | do { |
82 | frag = GET_FRAG_ID(map, start, idmask); |
83 | |
84 | fragend = find_next_bit_le(addr: map, size: endbit, offset: start + idlen); |
85 | if (fragend >= endbit) |
86 | goto error; |
87 | |
88 | if (start == freelink) { |
89 | freelink += frag & 0x7fff; |
90 | } else if (frag == frag_id) { |
91 | unsigned int length = fragend + 1 - start; |
92 | |
93 | if (*offset < length) |
94 | return start + *offset; |
95 | *offset -= length; |
96 | } |
97 | |
98 | start = fragend + 1; |
99 | } while (start < endbit); |
100 | return -1; |
101 | |
102 | error: |
103 | printk(KERN_ERR "adfs: oversized fragment 0x%x at 0x%x-0x%x\n" , |
104 | frag, start, fragend); |
105 | return -1; |
106 | } |
107 | |
108 | /* |
109 | * Scan the free space map, for this zone, calculating the total |
110 | * number of map bits in each free space fragment. |
111 | * |
112 | * Note: idmask is limited to 15 bits [3.2] |
113 | */ |
114 | static unsigned int |
115 | scan_free_map(struct adfs_sb_info *asb, struct adfs_discmap *dm) |
116 | { |
117 | const unsigned int endbit = dm->dm_endbit; |
118 | const unsigned int idlen = asb->s_idlen; |
119 | const unsigned int frag_idlen = idlen <= 15 ? idlen : 15; |
120 | const u32 idmask = (1 << frag_idlen) - 1; |
121 | unsigned char *map = dm->dm_bh->b_data; |
122 | unsigned int start = 8, fragend; |
123 | u32 frag; |
124 | unsigned long total = 0; |
125 | |
126 | /* |
127 | * get fragment id |
128 | */ |
129 | frag = GET_FRAG_ID(map, start, idmask); |
130 | |
131 | /* |
132 | * If the freelink is null, then no free fragments |
133 | * exist in this zone. |
134 | */ |
135 | if (frag == 0) |
136 | return 0; |
137 | |
138 | do { |
139 | start += frag; |
140 | |
141 | frag = GET_FRAG_ID(map, start, idmask); |
142 | |
143 | fragend = find_next_bit_le(addr: map, size: endbit, offset: start + idlen); |
144 | if (fragend >= endbit) |
145 | goto error; |
146 | |
147 | total += fragend + 1 - start; |
148 | } while (frag >= idlen + 1); |
149 | |
150 | if (frag != 0) |
151 | printk(KERN_ERR "adfs: undersized free fragment\n" ); |
152 | |
153 | return total; |
154 | error: |
155 | printk(KERN_ERR "adfs: oversized free fragment\n" ); |
156 | return 0; |
157 | } |
158 | |
159 | static int scan_map(struct adfs_sb_info *asb, unsigned int zone, |
160 | const u32 frag_id, unsigned int mapoff) |
161 | { |
162 | const unsigned int idlen = asb->s_idlen; |
163 | struct adfs_discmap *dm, *dm_end; |
164 | int result; |
165 | |
166 | dm = asb->s_map + zone; |
167 | zone = asb->s_map_size; |
168 | dm_end = asb->s_map + zone; |
169 | |
170 | do { |
171 | result = lookup_zone(dm, idlen, frag_id, offset: &mapoff); |
172 | |
173 | if (result != -1) |
174 | goto found; |
175 | |
176 | dm ++; |
177 | if (dm == dm_end) |
178 | dm = asb->s_map; |
179 | } while (--zone > 0); |
180 | |
181 | return -1; |
182 | found: |
183 | result -= dm->dm_startbit; |
184 | result += dm->dm_startblk; |
185 | |
186 | return result; |
187 | } |
188 | |
189 | /* |
190 | * calculate the amount of free blocks in the map. |
191 | * |
192 | * n=1 |
193 | * total_free = E(free_in_zone_n) |
194 | * nzones |
195 | */ |
196 | void adfs_map_statfs(struct super_block *sb, struct kstatfs *buf) |
197 | { |
198 | struct adfs_sb_info *asb = ADFS_SB(sb); |
199 | struct adfs_discrecord *dr = adfs_map_discrecord(dm: asb->s_map); |
200 | struct adfs_discmap *dm; |
201 | unsigned int total = 0; |
202 | unsigned int zone; |
203 | |
204 | dm = asb->s_map; |
205 | zone = asb->s_map_size; |
206 | |
207 | do { |
208 | total += scan_free_map(asb, dm: dm++); |
209 | } while (--zone > 0); |
210 | |
211 | buf->f_blocks = adfs_disc_size(dr) >> sb->s_blocksize_bits; |
212 | buf->f_files = asb->s_ids_per_zone * asb->s_map_size; |
213 | buf->f_bavail = |
214 | buf->f_bfree = signed_asl(val: total, shift: asb->s_map2blk); |
215 | } |
216 | |
217 | int adfs_map_lookup(struct super_block *sb, u32 frag_id, unsigned int offset) |
218 | { |
219 | struct adfs_sb_info *asb = ADFS_SB(sb); |
220 | unsigned int zone, mapoff; |
221 | int result; |
222 | |
223 | /* |
224 | * map & root fragment is special - it starts in the center of the |
225 | * disk. The other fragments start at zone (frag / ids_per_zone) |
226 | */ |
227 | if (frag_id == ADFS_ROOT_FRAG) |
228 | zone = asb->s_map_size >> 1; |
229 | else |
230 | zone = frag_id / asb->s_ids_per_zone; |
231 | |
232 | if (zone >= asb->s_map_size) |
233 | goto bad_fragment; |
234 | |
235 | /* Convert sector offset to map offset */ |
236 | mapoff = signed_asl(val: offset, shift: -asb->s_map2blk); |
237 | |
238 | read_lock(&adfs_map_lock); |
239 | result = scan_map(asb, zone, frag_id, mapoff); |
240 | read_unlock(&adfs_map_lock); |
241 | |
242 | if (result > 0) { |
243 | unsigned int secoff; |
244 | |
245 | /* Calculate sector offset into map block */ |
246 | secoff = offset - signed_asl(val: mapoff, shift: asb->s_map2blk); |
247 | return secoff + signed_asl(val: result, shift: asb->s_map2blk); |
248 | } |
249 | |
250 | adfs_error(sb, "fragment 0x%04x at offset %d not found in map" , |
251 | frag_id, offset); |
252 | return 0; |
253 | |
254 | bad_fragment: |
255 | adfs_error(sb, "invalid fragment 0x%04x (zone = %d, max = %d)" , |
256 | frag_id, zone, asb->s_map_size); |
257 | return 0; |
258 | } |
259 | |
260 | static unsigned char adfs_calczonecheck(struct super_block *sb, unsigned char *map) |
261 | { |
262 | unsigned int v0, v1, v2, v3; |
263 | int i; |
264 | |
265 | v0 = v1 = v2 = v3 = 0; |
266 | for (i = sb->s_blocksize - 4; i; i -= 4) { |
267 | v0 += map[i] + (v3 >> 8); |
268 | v3 &= 0xff; |
269 | v1 += map[i + 1] + (v0 >> 8); |
270 | v0 &= 0xff; |
271 | v2 += map[i + 2] + (v1 >> 8); |
272 | v1 &= 0xff; |
273 | v3 += map[i + 3] + (v2 >> 8); |
274 | v2 &= 0xff; |
275 | } |
276 | v0 += v3 >> 8; |
277 | v1 += map[1] + (v0 >> 8); |
278 | v2 += map[2] + (v1 >> 8); |
279 | v3 += map[3] + (v2 >> 8); |
280 | |
281 | return v0 ^ v1 ^ v2 ^ v3; |
282 | } |
283 | |
284 | static int adfs_checkmap(struct super_block *sb, struct adfs_discmap *dm) |
285 | { |
286 | unsigned char crosscheck = 0, zonecheck = 1; |
287 | int i; |
288 | |
289 | for (i = 0; i < ADFS_SB(sb)->s_map_size; i++) { |
290 | unsigned char *map; |
291 | |
292 | map = dm[i].dm_bh->b_data; |
293 | |
294 | if (adfs_calczonecheck(sb, map) != map[0]) { |
295 | adfs_error(sb, "zone %d fails zonecheck" , i); |
296 | zonecheck = 0; |
297 | } |
298 | crosscheck ^= map[3]; |
299 | } |
300 | if (crosscheck != 0xff) |
301 | adfs_error(sb, "crosscheck != 0xff" ); |
302 | return crosscheck == 0xff && zonecheck; |
303 | } |
304 | |
305 | /* |
306 | * Layout the map - the first zone contains a copy of the disc record, |
307 | * and the last zone must be limited to the size of the filesystem. |
308 | */ |
309 | static void adfs_map_layout(struct adfs_discmap *dm, unsigned int nzones, |
310 | struct adfs_discrecord *dr) |
311 | { |
312 | unsigned int zone, zone_size; |
313 | u64 size; |
314 | |
315 | zone_size = (8 << dr->log2secsize) - le16_to_cpu(dr->zone_spare); |
316 | |
317 | dm[0].dm_bh = NULL; |
318 | dm[0].dm_startblk = 0; |
319 | dm[0].dm_startbit = 32 + ADFS_DR_SIZE_BITS; |
320 | dm[0].dm_endbit = 32 + zone_size; |
321 | |
322 | for (zone = 1; zone < nzones; zone++) { |
323 | dm[zone].dm_bh = NULL; |
324 | dm[zone].dm_startblk = zone * zone_size - ADFS_DR_SIZE_BITS; |
325 | dm[zone].dm_startbit = 32; |
326 | dm[zone].dm_endbit = 32 + zone_size; |
327 | } |
328 | |
329 | size = adfs_disc_size(dr) >> dr->log2bpmb; |
330 | size -= (nzones - 1) * zone_size - ADFS_DR_SIZE_BITS; |
331 | dm[nzones - 1].dm_endbit = 32 + size; |
332 | } |
333 | |
334 | static int adfs_map_read(struct adfs_discmap *dm, struct super_block *sb, |
335 | unsigned int map_addr, unsigned int nzones) |
336 | { |
337 | unsigned int zone; |
338 | |
339 | for (zone = 0; zone < nzones; zone++) { |
340 | dm[zone].dm_bh = sb_bread(sb, block: map_addr + zone); |
341 | if (!dm[zone].dm_bh) |
342 | return -EIO; |
343 | } |
344 | |
345 | return 0; |
346 | } |
347 | |
348 | static void adfs_map_relse(struct adfs_discmap *dm, unsigned int nzones) |
349 | { |
350 | unsigned int zone; |
351 | |
352 | for (zone = 0; zone < nzones; zone++) |
353 | brelse(bh: dm[zone].dm_bh); |
354 | } |
355 | |
356 | struct adfs_discmap *adfs_read_map(struct super_block *sb, struct adfs_discrecord *dr) |
357 | { |
358 | struct adfs_sb_info *asb = ADFS_SB(sb); |
359 | struct adfs_discmap *dm; |
360 | unsigned int map_addr, zone_size, nzones; |
361 | int ret; |
362 | |
363 | nzones = dr->nzones | dr->nzones_high << 8; |
364 | zone_size = (8 << dr->log2secsize) - le16_to_cpu(dr->zone_spare); |
365 | |
366 | asb->s_idlen = dr->idlen; |
367 | asb->s_map_size = nzones; |
368 | asb->s_map2blk = dr->log2bpmb - dr->log2secsize; |
369 | asb->s_log2sharesize = dr->log2sharesize; |
370 | asb->s_ids_per_zone = zone_size / (asb->s_idlen + 1); |
371 | |
372 | map_addr = (nzones >> 1) * zone_size - |
373 | ((nzones > 1) ? ADFS_DR_SIZE_BITS : 0); |
374 | map_addr = signed_asl(val: map_addr, shift: asb->s_map2blk); |
375 | |
376 | dm = kmalloc_array(n: nzones, size: sizeof(*dm), GFP_KERNEL); |
377 | if (dm == NULL) { |
378 | adfs_error(sb, "not enough memory" ); |
379 | return ERR_PTR(error: -ENOMEM); |
380 | } |
381 | |
382 | adfs_map_layout(dm, nzones, dr); |
383 | |
384 | ret = adfs_map_read(dm, sb, map_addr, nzones); |
385 | if (ret) { |
386 | adfs_error(sb, "unable to read map" ); |
387 | goto error_free; |
388 | } |
389 | |
390 | if (adfs_checkmap(sb, dm)) |
391 | return dm; |
392 | |
393 | adfs_error(sb, "map corrupted" ); |
394 | |
395 | error_free: |
396 | adfs_map_relse(dm, nzones); |
397 | kfree(objp: dm); |
398 | return ERR_PTR(error: -EIO); |
399 | } |
400 | |
401 | void adfs_free_map(struct super_block *sb) |
402 | { |
403 | struct adfs_sb_info *asb = ADFS_SB(sb); |
404 | |
405 | adfs_map_relse(dm: asb->s_map, nzones: asb->s_map_size); |
406 | kfree(objp: asb->s_map); |
407 | } |
408 | |