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