1 /* 2 * Copyright (C) 2013 Raphael S. Carvalho <raphael.scarv (at) 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 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 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 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 */ 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 */ 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 }
