1 /*
2 * Copyright (c) 2012 Dave Vasilevsky <dave@vasilevsky.ca>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25 #include "file.h"
26
27 #include "fs.h"
28 #include "swap.h"
29 #include "table.h"
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <sys/stat.h>
34
sqfs_frag_entry(sqfs * fs,struct squashfs_fragment_entry * frag,uint32_t idx)35 sqfs_err sqfs_frag_entry(sqfs *fs, struct squashfs_fragment_entry *frag,
36 uint32_t idx) {
37 sqfs_err err = SQFS_OK;
38
39 if (idx == SQUASHFS_INVALID_FRAG)
40 return SQFS_ERR;
41
42 err = sqfs_table_get(&fs->frag_table, fs, idx, frag);
43 sqfs_swapin_fragment_entry(frag);
44 return err;
45 }
46
sqfs_frag_block(sqfs * fs,sqfs_inode * inode,size_t * offset,size_t * size,sqfs_block ** block)47 sqfs_err sqfs_frag_block(sqfs *fs, sqfs_inode *inode,
48 size_t *offset, size_t *size, sqfs_block **block) {
49 struct squashfs_fragment_entry frag;
50 sqfs_err err = SQFS_OK;
51
52 if (!S_ISREG(inode->base.mode))
53 return SQFS_ERR;
54
55 err = sqfs_frag_entry(fs, &frag, inode->xtra.reg.frag_idx);
56 if (err)
57 return err;
58
59 err = sqfs_data_cache(fs, &fs->frag_cache, frag.start_block,
60 frag.size, block);
61 if (err)
62 return SQFS_ERR;
63
64 *offset = inode->xtra.reg.frag_off;
65 *size = inode->xtra.reg.file_size % fs->sb.block_size;
66 return SQFS_OK;
67 }
68
sqfs_blocklist_count(sqfs * fs,sqfs_inode * inode)69 size_t sqfs_blocklist_count(sqfs *fs, sqfs_inode *inode) {
70 uint64_t size = inode->xtra.reg.file_size;
71 size_t block = fs->sb.block_size;
72 if (inode->xtra.reg.frag_idx == SQUASHFS_INVALID_FRAG) {
73 return sqfs_divceil(size, block);
74 } else {
75 return (size_t)(size / block);
76 }
77 }
78
sqfs_blocklist_init(sqfs * fs,sqfs_inode * inode,sqfs_blocklist * bl)79 void sqfs_blocklist_init(sqfs *fs, sqfs_inode *inode, sqfs_blocklist *bl) {
80 bl->fs = fs;
81 bl->remain = sqfs_blocklist_count(fs, inode);
82 bl->cur = inode->next;
83 bl->started = false;
84 bl->pos = 0;
85 bl->block = inode->xtra.reg.start_block;
86 bl->input_size = 0;
87 }
88
sqfs_blocklist_next(sqfs_blocklist * bl)89 sqfs_err sqfs_blocklist_next(sqfs_blocklist *bl) {
90 sqfs_err err = SQFS_OK;
91 bool compressed;
92
93 if (bl->remain == 0)
94 return SQFS_ERR;
95 --(bl->remain);
96
97 err = sqfs_md_read(bl->fs, &bl->cur, &bl->header,
98 sizeof(bl->header));
99 if (err)
100 return err;
101 sqfs_swapin32(&bl->header);
102
103 bl->block += bl->input_size;
104 sqfs_data_header(bl->header, &compressed, &bl->input_size);
105
106 if (bl->started)
107 bl->pos += bl->fs->sb.block_size;
108 bl->started = true;
109
110 return SQFS_OK;
111 }
112
sqfs_read_range(sqfs * fs,sqfs_inode * inode,sqfs_off_t start,sqfs_off_t * size,void * buf)113 sqfs_err sqfs_read_range(sqfs *fs, sqfs_inode *inode, sqfs_off_t start,
114 sqfs_off_t *size, void *buf) {
115 sqfs_err err = SQFS_OK;
116
117 sqfs_off_t file_size;
118 size_t block_size;
119 sqfs_blocklist bl;
120
121 size_t read_off;
122 char *buf_orig;
123
124 if (!S_ISREG(inode->base.mode))
125 return SQFS_ERR;
126
127 file_size = inode->xtra.reg.file_size;
128 block_size = fs->sb.block_size;
129
130 if (*size < 0 || start > file_size)
131 return SQFS_ERR;
132 if (start == file_size) {
133 *size = 0;
134 return SQFS_OK;
135 }
136
137 err = sqfs_blockidx_blocklist(fs, inode, &bl, start);
138 if (err)
139 return err;
140
141 read_off = start % block_size;
142 buf_orig = buf;
143 while (*size > 0) {
144 sqfs_block *block = NULL;
145 size_t data_off, data_size;
146 size_t take;
147
148 bool fragment = (bl.remain == 0);
149 if (fragment) { /* fragment */
150 if (inode->xtra.reg.frag_idx == SQUASHFS_INVALID_FRAG)
151 break;
152 err = sqfs_frag_block(fs, inode, &data_off, &data_size, &block);
153 if (err)
154 return err;
155 } else {
156 if ((err = sqfs_blocklist_next(&bl)))
157 return err;
158 if (bl.pos + block_size <= start)
159 continue;
160
161 data_off = 0;
162 if (bl.input_size == 0) { /* Hole! */
163 data_size = (size_t)(file_size - bl.pos);
164 if (data_size > block_size)
165 data_size = block_size;
166 } else {
167 err = sqfs_data_cache(fs, &fs->data_cache, bl.block,
168 bl.header, &block);
169 if (err)
170 return err;
171 data_size = block->size;
172 }
173 }
174
175 take = data_size - read_off;
176 if (take > *size)
177 take = (size_t)(*size);
178 if (block) {
179 memcpy(buf, (char*)block->data + data_off + read_off, take);
180 /* BLOCK CACHED, DON'T DISPOSE */
181 } else {
182 memset(buf, 0, take);
183 }
184 read_off = 0;
185 *size -= take;
186 buf = (char*)buf + take;
187
188 if (fragment)
189 break;
190 }
191
192 *size = (char*)buf - buf_orig;
193 return *size ? SQFS_OK : SQFS_ERR;
194 }
195
196
197 /*
198 To read block N of a M-block file, we have to read N blocksizes from the,
199 metadata. This is a lot of work for large files! So for those files, we use
200 an index to speed it up.
201
202 The M blocksizes are split between M / SQUASHFS_METADATA_SIZE MD-blocks.
203 For each of these blocks, we maintain in the index the location of the
204 MD-block, and the location of the data block corresponding to the start
205 of that MD-block.
206
207 Then to read block N, we just calculate which metadata block index
208 ("metablock") we want, and get that block-index entry. Then we
209 only need to read that one MD-block to seek within the file.
210 */
211
212 /* Is a file worth indexing? */
sqfs_blockidx_indexable(sqfs * fs,sqfs_inode * inode)213 static bool sqfs_blockidx_indexable(sqfs *fs, sqfs_inode *inode) {
214 size_t blocks = sqfs_blocklist_count(fs, inode);
215 size_t md_size = blocks * sizeof(sqfs_blocklist_entry);
216 return md_size >= SQUASHFS_METADATA_SIZE;
217 }
218
sqfs_blockidx_dispose(void * data)219 static void sqfs_blockidx_dispose(void *data) {
220 free(*(sqfs_blockidx_entry**)data);
221 }
222
sqfs_blockidx_init(sqfs_cache * cache)223 sqfs_err sqfs_blockidx_init(sqfs_cache *cache) {
224 return sqfs_cache_init(cache, sizeof(sqfs_blockidx_entry**),
225 SQUASHFS_META_SLOTS, &sqfs_blockidx_dispose);
226 }
227
sqfs_blockidx_add(sqfs * fs,sqfs_inode * inode,sqfs_blockidx_entry ** out)228 sqfs_err sqfs_blockidx_add(sqfs *fs, sqfs_inode *inode,
229 sqfs_blockidx_entry **out) {
230 size_t blocks; /* Number of blocks in the file */
231 size_t md_size; /* Amount of metadata necessary to hold the blocksizes */
232 size_t count; /* Number of block-index entries necessary */
233
234 sqfs_blockidx_entry *blockidx;
235 sqfs_blocklist bl;
236
237 /* For the cache */
238 sqfs_cache_idx idx;
239 sqfs_blockidx_entry **cachep;
240
241 size_t i = 0;
242 bool first = true;
243
244 *out = NULL;
245
246 blocks = sqfs_blocklist_count(fs, inode);
247 md_size = blocks * sizeof(sqfs_blocklist_entry);
248 count = (inode->next.offset + md_size - 1)
249 / SQUASHFS_METADATA_SIZE;
250 blockidx = malloc(count * sizeof(sqfs_blockidx_entry));
251 if (!blockidx)
252 return SQFS_ERR;
253
254 sqfs_blocklist_init(fs, inode, &bl);
255 while (bl.remain && i < count) {
256 sqfs_err err = SQFS_OK;
257 /* If the MD cursor offset is small, we found a new MD-block.
258 * Skip the first MD-block, because we already know where it is:
259 * inode->next.offset */
260 if (bl.cur.offset < sizeof(sqfs_blocklist_entry) && !first) {
261 blockidx[i].data_block = bl.block + bl.input_size;
262 blockidx[i++].md_block = (uint32_t)(bl.cur.block - fs->sb.inode_table_start);
263 }
264 first = false;
265
266 err = sqfs_blocklist_next(&bl);
267 if (err) {
268 free(blockidx);
269 return SQFS_ERR;
270 }
271 }
272
273 idx = inode->base.inode_number + 1; /* zero means invalid */
274 cachep = sqfs_cache_add(&fs->blockidx, idx);
275 *out = *cachep = blockidx;
276 return SQFS_OK;
277 }
278
sqfs_blockidx_blocklist(sqfs * fs,sqfs_inode * inode,sqfs_blocklist * bl,sqfs_off_t start)279 sqfs_err sqfs_blockidx_blocklist(sqfs *fs, sqfs_inode *inode,
280 sqfs_blocklist *bl, sqfs_off_t start) {
281 size_t block, metablock, skipped;
282 sqfs_blockidx_entry *blockidx, **bp;
283 sqfs_cache_idx idx;
284
285 sqfs_blocklist_init(fs, inode, bl);
286 block = (size_t)(start / fs->sb.block_size);
287 if (block > bl->remain) { /* fragment */
288 bl->remain = 0;
289 return SQFS_OK;
290 }
291
292 /* How many MD-blocks do we want to skip? */
293 metablock = (bl->cur.offset + block * sizeof(sqfs_blocklist_entry))
294 / SQUASHFS_METADATA_SIZE;
295 if (metablock == 0)
296 return SQFS_OK; /* no skip needed, don't want an index */
297 if (!sqfs_blockidx_indexable(fs, inode))
298 return SQFS_OK; /* too small to index */
299
300 /* Get the index, creating it if necessary */
301 idx = inode->base.inode_number + 1; /* zero means invalid index */
302 if ((bp = sqfs_cache_get(&fs->blockidx, idx))) {
303 blockidx = *bp;
304 } else {
305 sqfs_err err = sqfs_blockidx_add(fs, inode, &blockidx);
306 if (err)
307 return err;
308 }
309
310 skipped = (metablock * SQUASHFS_METADATA_SIZE / sizeof(sqfs_blocklist_entry))
311 - (bl->cur.offset / sizeof(sqfs_blocklist_entry));
312
313 blockidx += metablock - 1;
314 bl->cur.block = blockidx->md_block + fs->sb.inode_table_start;
315 bl->cur.offset %= sizeof(sqfs_blocklist_entry);
316 bl->remain -= skipped;
317 bl->pos = (uint64_t)skipped * fs->sb.block_size;
318 bl->block = blockidx->data_block;
319 return SQFS_OK;
320 }
321
322