408 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * linux/fs/adfs/map.c4 *5 * Copyright (C) 1997-2002 Russell King6 */7#include <linux/slab.h>8#include <linux/statfs.h>9#include <linux/unaligned.h>10#include "adfs.h"11 12/*13 * The ADFS map is basically a set of sectors. Each sector is called a14 * zone which contains a bitstream made up of variable sized fragments.15 * Each bit refers to a set of bytes in the filesystem, defined by16 * log2bpmb. This may be larger or smaller than the sector size, but17 * the overall size it describes will always be a round number of18 * 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 of26 * the fragment id up to and including the '1' bit - ie, idlen + n + 127 * bits.28 *29 * A fragment id can be repeated multiple times in the whole map for30 * large or fragmented files. The first map zone a fragment starts in31 * is given by fragment id / ids_per_zone - this allows objects to start32 * from any zone on the disk.33 *34 * Free space is described by a linked list of fragments. Each free35 * 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 end37 * 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 as40 * our inode numbers.) Object ids contain a fragment id and an optional41 * offset. This allows a directory fragment to contain small files42 * associated with that directory.43 */44 45/*46 * For the future...47 */48static DEFINE_RWLOCK(adfs_map_lock);49 50/*51 * This is fun. We need to load up to 19 bits from the map at an52 * 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 the65 * output of:66 * gcc -D__KERNEL__ -O2 -I../../include -o - -S map.c67 */68static 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(map, endbit, 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 102error: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 total110 * number of map bits in each free space fragment.111 *112 * Note: idmask is limited to 15 bits [3.2]113 */114static unsigned int115scan_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 id128 */129 frag = GET_FRAG_ID(map, start, idmask);130 131 /*132 * If the freelink is null, then no free fragments133 * 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(map, endbit, 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;154error:155 printk(KERN_ERR "adfs: oversized free fragment\n");156 return 0;157}158 159static 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, &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;182found: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=1193 * total_free = E(free_in_zone_n)194 * nzones195 */196void 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(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++);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(total, asb->s_map2blk);215}216 217int 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 the225 * 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 else230 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(offset, -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(mapoff, asb->s_map2blk);247 return secoff + signed_asl(result, 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 254bad_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 260static 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 284static 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 */309static 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 334static 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, map_addr + zone);341 if (!dm[zone].dm_bh)342 return -EIO;343 }344 345 return 0;346}347 348static 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(dm[zone].dm_bh);354}355 356struct 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(map_addr, asb->s_map2blk);375 376 dm = kmalloc_array(nzones, sizeof(*dm), GFP_KERNEL);377 if (dm == NULL) {378 adfs_error(sb, "not enough memory");379 return ERR_PTR(-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 395error_free:396 adfs_map_relse(dm, nzones);397 kfree(dm);398 return ERR_PTR(-EIO);399}400 401void adfs_free_map(struct super_block *sb)402{403 struct adfs_sb_info *asb = ADFS_SB(sb);404 405 adfs_map_relse(asb->s_map, asb->s_map_size);406 kfree(asb->s_map);407}408