Linux-2.6.12-rc2
[linux-2.6.git] / 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 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 }