1 /*
2 * Copyright (C) 2013 Raphael S. Carvalho <raphael.scarv@gmail.com>
3 *
4 * Partially taken from fs/ext2/bmap.c
5 * This file was modified according UFS1/2 needs.
6 *
7 * Copyright (C) 2009 Liu Aleaxander -- All rights reserved. This file
8 * may be redistributed under the terms of the GNU Public License.
9 */
10
11 #include <stdio.h>
12 #include <dprintf.h>
13 #include <fs.h>
14 #include <disk.h>
15 #include <cache.h>
16 #include "ufs.h"
17
18 /*
19 * Copy blk address into buffer, this was needed since UFS1/2 addr size
20 * in blk maps differs from each other (32/64 bits respectivelly).
21 */
22 static inline uint64_t
get_blkaddr(const uint8_t * blk,uint32_t index,uint32_t shift)23 get_blkaddr (const uint8_t *blk, uint32_t index, uint32_t shift)
24 {
25 uint64_t addr = 0;
26
27 memcpy((uint8_t *) &addr,
28 (uint8_t *) blk + (index << shift),
29 1 << shift);
30
31 return addr;
32 }
33
34 /*
35 * Scan forward in a range of blocks to see if they are contiguous,
36 * then return the initial value.
37 */
38 static uint64_t
scan_set_nblocks(const uint8_t * map,uint32_t index,uint32_t addr_shift,unsigned int count,size_t * nblocks)39 scan_set_nblocks(const uint8_t *map, uint32_t index, uint32_t addr_shift,
40 unsigned int count, size_t *nblocks)
41 {
42 uint64_t addr;
43 uint64_t blk = get_blkaddr(map, index, addr_shift);
44
45 /*
46 * Block spans 8 fragments, then address is interleaved by 8.
47 * This code works for either 32/64 sized addresses.
48 */
49 if (nblocks) {
50 uint32_t skip = blk ? FRAGMENTS_PER_BLK : 0;
51 uint32_t next = blk + skip;
52 size_t cnt = 1;
53
54 /* Get address of starting blk pointer */
55 map += (index << addr_shift);
56
57 ufs_debug("[scan] start blk: %u\n", blk);
58 ufs_debug("[scan] count (nr of blks): %u\n", count);
59 /* Go up to the end of blk map */
60 while (--count) {
61 map += 1 << addr_shift;
62 addr = get_blkaddr(map, 0, addr_shift);
63 #if 0
64 /* Extra debugging info (Too much prints) */
65 ufs_debug("[scan] addr: %u next: %u\n", addr, next);
66 #endif
67 if (addr == next) {
68 cnt++;
69 next += skip;
70 } else {
71 break;
72 }
73 }
74 *nblocks = cnt;
75 ufs_debug("[scan] nblocks: %u\n", cnt);
76 ufs_debug("[scan] end blk: %u\n", next - FRAGMENTS_PER_BLK);
77 }
78
79 return blk;
80 }
81
82 /*
83 * The actual indirect block map handling - the block passed in should
84 * be relative to the beginning of the particular block hierarchy.
85 *
86 * @shft_per_blk: shift to get nr. of addresses in a block.
87 * @mask_per_blk: mask to limit the max nr. of addresses in a block.
88 * @addr_count: nr. of addresses in a block.
89 */
90 static uint64_t
bmap_indirect(struct fs_info * fs,uint64_t start,uint32_t block,int levels,size_t * nblocks)91 bmap_indirect(struct fs_info *fs, uint64_t start, uint32_t block,
92 int levels, size_t *nblocks)
93 {
94 uint32_t shft_per_blk = fs->block_shift - UFS_SB(fs)->addr_shift;
95 uint32_t addr_count = (1 << shft_per_blk);
96 uint32_t mask_per_blk = addr_count - 1;
97 const uint8_t *blk = NULL;
98 uint32_t index = 0;
99
100 while (levels--) {
101 if (!start) {
102 if (nblocks)
103 *nblocks = addr_count << (levels * shft_per_blk);
104 return 0;
105 }
106
107 blk = get_cache(fs->fs_dev, frag_to_blk(fs, start));
108 index = (block >> (levels * shft_per_blk)) & mask_per_blk;
109 start = get_blkaddr(blk, index, UFS_SB(fs)->addr_shift);
110 }
111
112 return scan_set_nblocks(blk, index, UFS_SB(fs)->addr_shift,
113 addr_count - index, nblocks);
114 }
115
116 /*
117 * Handle the traditional block map, like indirect, double indirect
118 * and triple indirect
119 */
ufs_bmap(struct inode * inode,block_t block,size_t * nblocks)120 uint64_t ufs_bmap (struct inode *inode, block_t block, size_t *nblocks)
121 {
122 uint32_t shft_per_blk, ptrs_per_blk;
123 static uint32_t indir_blks, double_blks, triple_blks;
124 struct fs_info *fs = inode->fs;
125
126 /* Initialize static values */
127 if (!indir_blks) {
128 shft_per_blk = fs->block_shift - UFS_SB(fs)->addr_shift;
129 ptrs_per_blk = fs->block_size >> UFS_SB(fs)->addr_shift;
130
131 indir_blks = ptrs_per_blk;
132 double_blks = ptrs_per_blk << shft_per_blk;
133 triple_blks = double_blks << shft_per_blk;
134 }
135
136 /*
137 * direct blocks
138 * (UFS2_ADDR_SHIFT) is also used for UFS1 because its direct ptr array
139 * was extended to 64 bits.
140 */
141 if (block < UFS_DIRECT_BLOCKS)
142 return scan_set_nblocks((uint8_t *) PVT(inode)->direct_blk_ptr,
143 block, UFS2_ADDR_SHIFT,
144 UFS_DIRECT_BLOCKS - block, nblocks);
145
146 /* indirect blocks */
147 block -= UFS_DIRECT_BLOCKS;
148 if (block < indir_blks)
149 return bmap_indirect(fs, PVT(inode)->indirect_blk_ptr,
150 block, 1, nblocks);
151
152 /* double indirect blocks */
153 block -= indir_blks;
154 if (block < double_blks)
155 return bmap_indirect(fs, PVT(inode)->double_indirect_blk_ptr,
156 block, 2, nblocks);
157
158 /* triple indirect blocks */
159 block -= double_blks;
160 if (block < triple_blks)
161 return bmap_indirect(fs, PVT(inode)->triple_indirect_blk_ptr,
162 block, 3, nblocks);
163
164 /* This can't happen... */
165 return 0;
166 }
167
168 /*
169 * Next extent for getfssec
170 * "Remaining sectors" means (lstart & blkmask).
171 */
ufs_next_extent(struct inode * inode,uint32_t lstart)172 int ufs_next_extent(struct inode *inode, uint32_t lstart)
173 {
174 struct fs_info *fs = inode->fs;
175 int blktosec = BLOCK_SHIFT(fs) - SECTOR_SHIFT(fs);
176 int frag_shift = BLOCK_SHIFT(fs) - UFS_SB(fs)->c_blk_frag_shift;
177 int blkmask = (1 << blktosec) - 1;
178 block_t block;
179 size_t nblocks = 0;
180
181 ufs_debug("ufs_next_extent:\n");
182 block = ufs_bmap(inode, lstart >> blktosec, &nblocks);
183 ufs_debug("blk: %u\n", block);
184
185 if (!block) // Sparse block
186 inode->next_extent.pstart = EXTENT_ZERO;
187 else
188 /*
189 * Convert blk into sect addr and add the remaining
190 * sectors into pstart (sector start address).
191 */
192 inode->next_extent.pstart =
193 ((sector_t) (block << (frag_shift - SECTOR_SHIFT(fs)))) |
194 (lstart & blkmask);
195
196 /*
197 * Subtract the remaining sectors from len since these sectors
198 * were added to pstart (sector start address).
199 */
200 inode->next_extent.len = (nblocks << blktosec) - (lstart & blkmask);
201 return 0;
202 }