fs/adfs/map.c

   1 /*
   2  *  linux/fs/adfs/map.c
   3  *
   4  *  Copyright (C) 1997-1999 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/version.h>
  11 #include <linux/errno.h>
  12 #include <linux/fs.h>
  13 #include <linux/adfs_fs.h>
  14 #include <linux/spinlock.h>
  15
  16 #include "adfs.h"
  17
  18 /*
  19  * For the future...
  20  */
  21 static rwlock_t adfs_map_lock;
  22
  23 #define GET_FRAG_ID(_map,_start,_idmask)                                \
  24         ({                                                              \
  25                 unsigned long _v2, _frag;                               \
  26                 unsigned int _tmp;                                      \
  27                 _tmp = _start >> 5;                                     \
  28                 _frag = le32_to_cpu(_map[_tmp]);                        \
  29                 _v2   = le32_to_cpu(_map[_tmp + 1]);                    \
  30                 _tmp = start & 31;                                      \
  31                 _frag = (_frag >> _tmp) | (_v2 << (32 - _tmp));         \
  32                 _frag & _idmask;                                        \
  33         })
  34
  35 /*
  36  * return the map bit offset of the fragment frag_id in
  37  * the zone dm.
  38  * Note that the loop is optimised for best asm code -
  39  * look at the output of:
  40  *  gcc -D__KERNEL__ -O2 -I../../include -o - -S map.c
  41  */
  42 static int
  43 lookup_zone(const struct adfs_discmap *dm, const unsigned int idlen,
  44             const unsigned int frag_id, unsigned int *offset)
  45 {
  46         const unsigned int mapsize = dm->dm_endbit;
  47         const unsigned int idmask = (1 << idlen) - 1;
  48         unsigned long *map = ((unsigned long *)dm->dm_bh->b_data) + 1;
  49         unsigned int start = dm->dm_startbit;
  50         unsigned int mapptr;
  51
  52         do {
  53                 unsigned long frag;
  54
  55                 frag = GET_FRAG_ID(map, start, idmask);
  56                 mapptr = start + idlen;
  57
  58                 /*
  59                  * find end of fragment
  60                  */
  61                 {
  62                         unsigned long v2;
  63
  64                         while ((v2 = map[mapptr >> 5] >> (mapptr & 31)) == 0) {
  65                                 mapptr = (mapptr & ~31) + 32;
  66                                 if (mapptr >= mapsize)
  67                                         goto error;
  68                         }
  69
  70                         mapptr += 1 + ffz(~v2);
  71                 }
  72
  73                 if (frag == frag_id)
  74                         goto found;
  75 again:
  76                 start = mapptr;
  77         } while (mapptr < mapsize);
  78
  79 error:
  80         return -1;
  81
  82 found:
  83         {
  84                 int length = mapptr - start;
  85                 if (*offset >= length) {
  86                         *offset -= length;
  87                         goto again;
  88                 }
  89         }
  90         return start + *offset;
  91 }
  92
  93 /*
  94  * Scan the free space map, for this zone, calculating the total
  95  * number of map bits in each free space fragment.
  96  *
  97  * Note: idmask is limited to 15 bits [3.2]
  98  */
  99 static unsigned int
 100 scan_free_map(struct adfs_sb_info *asb, struct adfs_discmap *dm)
 101 {
 102         const unsigned int mapsize = dm->dm_endbit + 32;
 103         const unsigned int idlen  = asb->s_idlen;
 104         const unsigned int frag_idlen = idlen <= 15 ? idlen : 15;
 105         const unsigned int idmask = (1 << frag_idlen) - 1;
 106         unsigned long *map = (unsigned long *)dm->dm_bh->b_data;
 107         unsigned int start = 8, mapptr;
 108         unsigned long frag;
 109         unsigned long total = 0;
 110
 111         /*
 112          * get fragment id
 113          */
 114         frag = GET_FRAG_ID(map, start, idmask);
 115
 116         /*
 117          * If the freelink is null, then no free fragments
 118          * exist in this zone.
 119          */
 120         if (frag == 0)
 121                 return 0;
 122
 123         do {
 124                 start += frag;
 125
 126                 /*
 127                  * get fragment id
 128                  */
 129                 frag = GET_FRAG_ID(map, start, idmask);
 130                 mapptr = start + idlen;
 131
 132                 /*
 133                  * find end of fragment
 134                  */
 135                 {
 136                         unsigned long v2;
 137
 138                         while ((v2 = map[mapptr >> 5] >> (mapptr & 31)) == 0) {
 139                                 mapptr = (mapptr & ~31) + 32;
 140                                 if (mapptr >= mapsize)
 141                                         goto error;
 142                         }
 143
 144                         mapptr += 1 + ffz(~v2);
 145                 }
 146
 147                 total += mapptr - start;
 148         } while (frag >= idlen + 1);
 149
 150         if (frag != 0)
 151                 printk(KERN_ERR "adfs: undersized free fragment\n");
 152
 153         return total;
 154 error:
 155         printk(KERN_ERR "adfs: oversized free fragment\n");
 156         return 0;
 157 }
 158
 159 static int
 160 scan_map(struct adfs_sb_info *asb, unsigned int zone,
 161          const unsigned int frag_id, unsigned int mapoff)
 162 {
 163         const unsigned int idlen = asb->s_idlen;
 164         struct adfs_discmap *dm, *dm_end;
 165         int result;
 166
 167         dm      = asb->s_map + zone;
 168         zone    = asb->s_map_size;
 169         dm_end  = asb->s_map + zone;
 170
 171         do {
 172                 result = lookup_zone(dm, idlen, frag_id, &mapoff);
 173
 174                 if (result != -1)
 175                         goto found;
 176
 177                 dm ++;
 178                 if (dm == dm_end)
 179                         dm = asb->s_map;
 180         } while (--zone > 0);
 181
 182         return -1;
 183 found:
 184         result -= dm->dm_startbit;
 185         result += dm->dm_startblk;
 186
 187         return result;
 188 }
 189
 190 /*
 191  * calculate the amount of free blocks in the map.
 192  *
 193  *              n=1
 194  *  total_free = E(free_in_zone_n)
 195  *              nzones
 196  */
 197 unsigned int
 198 adfs_map_free(struct super_block *sb)
 199 {
 200         struct adfs_sb_info *asb = &sb->u.adfs_sb;
 201         struct adfs_discmap *dm;
 202         unsigned int total = 0;
 203         unsigned int zone;
 204
 205         dm   = asb->s_map;
 206         zone = asb->s_map_size;
 207
 208         do {
 209                 total += scan_free_map(asb, dm++);
 210         } while (--zone > 0);
 211
 212         return signed_asl(total, asb->s_map2blk);
 213 }
 214
 215 int adfs_map_lookup (struct super_block *sb, int frag_id, int offset)
 216 {
 217         struct adfs_sb_info *asb = &sb->u.adfs_sb;
 218         unsigned int zone, mapoff;
 219         int result;
 220
 221         /*
 222          * map & root fragment is special - it starts in the center of the
 223          * disk.  The other fragments start at zone (frag / ids_per_zone)
 224          */
 225         if (frag_id == ADFS_ROOT_FRAG)
 226                 zone = asb->s_map_size >> 1;
 227         else
 228                 zone = frag_id / asb->s_ids_per_zone;
 229
 230         if (zone >= asb->s_map_size)
 231                 goto bad_fragment;
 232
 233         /* Convert sector offset to map offset */
 234         mapoff = signed_asl(offset, -asb->s_map2blk);
 235
 236         read_lock(&adfs_map_lock);
 237         result = scan_map(asb, zone, frag_id, mapoff);
 238         read_unlock(&adfs_map_lock);
 239
 240         if (result > 0) {
 241                 unsigned int secoff;
 242
 243                 /* Calculate sector offset into map block */
 244                 secoff = offset - signed_asl(mapoff, asb->s_map2blk);
 245                 return secoff + signed_asl(result, asb->s_map2blk);
 246         }
 247
 248         adfs_error(sb, "fragment %04X at offset %d not found in map",
 249                    frag_id, offset);
 250         return 0;
 251
 252 bad_fragment:
 253         adfs_error(sb, "fragment %X is invalid (zone = %d, max = %d)",
 254                    frag_id, zone, asb->s_map_size);
 255         return 0;
 256 }