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