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 */
22static inline uint64_t
23get_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 */
38static uint64_t
39scan_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 */
90static uint64_t
91bmap_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 */
120uint64_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 */
172int 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}