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