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