fs/adfs/map.c

   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 rwlock_t adfs_map_lock = RW_LOCK_UNLOCKED;
  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                         u32 v, *_map = (u32 *)map;
  96
  97                         v = le32_to_cpu(_map[mapptr >> 5]) >> (mapptr & 31);
  98                         while (v == 0) {
  99                                 mapptr = (mapptr & ~31) + 32;
 100                                 if (mapptr >= mapsize)
 101                                         goto error;
 102                                 v = le32_to_cpu(_map[mapptr >> 5]);
 103                         }
 104
 105                         mapptr += 1 + ffz(~v);
 106                 }
 107
 108                 if (frag == frag_id)
 109                         goto found;
 110 again:
 111                 start = mapptr;
 112         } while (mapptr < mapsize);
 113         return -1;
 114
 115 error:
 116         printk(KERN_ERR "adfs: oversized fragment 0x%x at 0x%x-0x%x\n",
 117                 frag, start, mapptr);
 118         return -1;
 119
 120 found:
 121         {
 122                 int length = mapptr - start;
 123                 if (*offset >= length) {
 124                         *offset -= length;
 125                         goto again;
 126                 }
 127         }
 128         return start + *offset;
 129 }
 130
 131 /*
 132  * Scan the free space map, for this zone, calculating the total
 133  * number of map bits in each free space fragment.
 134  *
 135  * Note: idmask is limited to 15 bits [3.2]
 136  */
 137 static unsigned int
 138 scan_free_map(struct adfs_sb_info *asb, struct adfs_discmap *dm)
 139 {
 140         const unsigned int mapsize = dm->dm_endbit + 32;
 141         const unsigned int idlen  = asb->s_idlen;
 142         const unsigned int frag_idlen = idlen <= 15 ? idlen : 15;
 143         const u32 idmask = (1 << frag_idlen) - 1;
 144         unsigned char *map = dm->dm_bh->b_data;
 145         unsigned int start = 8, mapptr;
 146         u32 frag;
 147         unsigned long total = 0;
 148
 149         /*
 150          * get fragment id
 151          */
 152         frag = GET_FRAG_ID(map, start, idmask);
 153
 154         /*
 155          * If the freelink is null, then no free fragments
 156          * exist in this zone.
 157          */
 158         if (frag == 0)
 159                 return 0;
 160
 161         do {
 162                 start += frag;
 163
 164                 /*
 165                  * get fragment id
 166                  */
 167                 frag = GET_FRAG_ID(map, start, idmask);
 168                 mapptr = start + idlen;
 169
 170                 /*
 171                  * find end of fragment
 172                  */
 173                 {
 174                         u32 v, *_map = (u32 *)map;
 175
 176                         v = le32_to_cpu(_map[mapptr >> 5]) >> (mapptr & 31);
 177                         while (v == 0) {
 178                                 mapptr = (mapptr & ~31) + 32;
 179                                 if (mapptr >= mapsize)
 180                                         goto error;
 181                                 v = le32_to_cpu(_map[mapptr >> 5]);
 182                         }
 183
 184                         mapptr += 1 + ffz(~v);
 185                 }
 186
 187                 total += mapptr - start;
 188         } while (frag >= idlen + 1);
 189
 190         if (frag != 0)
 191                 printk(KERN_ERR "adfs: undersized free fragment\n");
 192
 193         return total;
 194 error:
 195         printk(KERN_ERR "adfs: oversized free fragment\n");
 196         return 0;
 197 }
 198
 199 static int
 200 scan_map(struct adfs_sb_info *asb, unsigned int zone,
 201          const unsigned int frag_id, unsigned int mapoff)
 202 {
 203         const unsigned int idlen = asb->s_idlen;
 204         struct adfs_discmap *dm, *dm_end;
 205         int result;
 206
 207         dm      = asb->s_map + zone;
 208         zone    = asb->s_map_size;
 209         dm_end  = asb->s_map + zone;
 210
 211         do {
 212                 result = lookup_zone(dm, idlen, frag_id, &mapoff);
 213
 214                 if (result != -1)
 215                         goto found;
 216
 217                 dm ++;
 218                 if (dm == dm_end)
 219                         dm = asb->s_map;
 220         } while (--zone > 0);
 221
 222         return -1;
 223 found:
 224         result -= dm->dm_startbit;
 225         result += dm->dm_startblk;
 226
 227         return result;
 228 }
 229
 230 /*
 231  * calculate the amount of free blocks in the map.
 232  *
 233  *              n=1
 234  *  total_free = E(free_in_zone_n)
 235  *              nzones
 236  */
 237 unsigned int
 238 adfs_map_free(struct super_block *sb)
 239 {
 240         struct adfs_sb_info *asb = ADFS_SB(sb);
 241         struct adfs_discmap *dm;
 242         unsigned int total = 0;
 243         unsigned int zone;
 244
 245         dm   = asb->s_map;
 246         zone = asb->s_map_size;
 247
 248         do {
 249                 total += scan_free_map(asb, dm++);
 250         } while (--zone > 0);
 251
 252         return signed_asl(total, asb->s_map2blk);
 253 }
 254
 255 int
 256 adfs_map_lookup(struct super_block *sb, unsigned int frag_id,
 257                 unsigned int offset)
 258 {
 259         struct adfs_sb_info *asb = ADFS_SB(sb);
 260         unsigned int zone, mapoff;
 261         int result;
 262
 263         /*
 264          * map & root fragment is special - it starts in the center of the
 265          * disk.  The other fragments start at zone (frag / ids_per_zone)
 266          */
 267         if (frag_id == ADFS_ROOT_FRAG)
 268                 zone = asb->s_map_size >> 1;
 269         else
 270                 zone = frag_id / asb->s_ids_per_zone;
 271
 272         if (zone >= asb->s_map_size)
 273                 goto bad_fragment;
 274
 275         /* Convert sector offset to map offset */
 276         mapoff = signed_asl(offset, -asb->s_map2blk);
 277
 278         read_lock(&adfs_map_lock);
 279         result = scan_map(asb, zone, frag_id, mapoff);
 280         read_unlock(&adfs_map_lock);
 281
 282         if (result > 0) {
 283                 unsigned int secoff;
 284
 285                 /* Calculate sector offset into map block */
 286                 secoff = offset - signed_asl(mapoff, asb->s_map2blk);
 287                 return secoff + signed_asl(result, asb->s_map2blk);
 288         }
 289
 290         adfs_error(sb, "fragment 0x%04x at offset %d not found in map",
 291                    frag_id, offset);
 292         return 0;
 293
 294 bad_fragment:
 295         adfs_error(sb, "invalid fragment 0x%04x (zone = %d, max = %d)",
 296                    frag_id, zone, asb->s_map_size);
 297         return 0;
 298 }