map.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    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 }

Cache object: 51007772cc50b46382adf3ced2ade482

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/fs/adfs/map.c

FreeBSD/Linux Kernel Cross Reference
sys/fs/adfs/map.c