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