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