1 /*
2  * linux/fs/befs/datastream.c
3  *
4  * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
5  *
6  * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
7  *
8  * Many thanks to Dominic Giampaolo, author of "Practical File System
9  * Design with the Be File System", for such a helpful book.
10  *
11  */
12 
13 #include <linux/kernel.h>
14 #include <linux/buffer_head.h>
15 #include <linux/string.h>
16 
17 #include "befs.h"
18 #include "datastream.h"
19 #include "io.h"
20 
21 const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
22 
23 static int befs_find_brun_direct(struct super_block *sb,
24 				 befs_data_stream * data,
25 				 befs_blocknr_t blockno, befs_block_run * run);
26 
27 static int befs_find_brun_indirect(struct super_block *sb,
28 				   befs_data_stream * data,
29 				   befs_blocknr_t blockno,
30 				   befs_block_run * run);
31 
32 static int befs_find_brun_dblindirect(struct super_block *sb,
33 				      befs_data_stream * data,
34 				      befs_blocknr_t blockno,
35 				      befs_block_run * run);
36 
37 /**
38  * befs_read_datastream - get buffer_head containing data, starting from pos.
39  * @sb: Filesystem superblock
40  * @ds: datastrem to find data with
41  * @pos: start of data
42  * @off: offset of data in buffer_head->b_data
43  *
44  * Returns pointer to buffer_head containing data starting with offset @off,
45  * if you don't need to know offset just set @off = NULL.
46  */
47 struct buffer_head *
befs_read_datastream(struct super_block * sb,befs_data_stream * ds,befs_off_t pos,uint * off)48 befs_read_datastream(struct super_block *sb, befs_data_stream * ds,
49 		     befs_off_t pos, uint * off)
50 {
51 	struct buffer_head *bh = NULL;
52 	befs_block_run run;
53 	befs_blocknr_t block;	/* block coresponding to pos */
54 
55 	befs_debug(sb, "---> befs_read_datastream() %Lu", pos);
56 	block = pos >> BEFS_SB(sb)->block_shift;
57 	if (off)
58 		*off = pos - (block << BEFS_SB(sb)->block_shift);
59 
60 	if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
61 		befs_error(sb, "BeFS: Error finding disk addr of block %lu",
62 			   block);
63 		befs_debug(sb, "<--- befs_read_datastream() ERROR");
64 		return NULL;
65 	}
66 	bh = befs_bread_iaddr(sb, run);
67 	if (!bh) {
68 		befs_error(sb, "BeFS: Error reading block %lu from datastream",
69 			   block);
70 		return NULL;
71 	}
72 
73 	befs_debug(sb, "<--- befs_read_datastream() read data, starting at %Lu",
74 		   pos);
75 
76 	return bh;
77 }
78 
79 /*
80  * Takes a file position and gives back a brun who's starting block
81  * is block number fblock of the file.
82  *
83  * Returns BEFS_OK or BEFS_ERR.
84  *
85  * Calls specialized functions for each of the three possible
86  * datastream regions.
87  *
88  * 2001-11-15 Will Dyson
89  */
90 int
befs_fblock2brun(struct super_block * sb,befs_data_stream * data,befs_blocknr_t fblock,befs_block_run * run)91 befs_fblock2brun(struct super_block *sb, befs_data_stream * data,
92 		 befs_blocknr_t fblock, befs_block_run * run)
93 {
94 	int err;
95 	befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
96 
97 	if (pos < data->max_direct_range) {
98 		err = befs_find_brun_direct(sb, data, fblock, run);
99 
100 	} else if (pos < data->max_indirect_range) {
101 		err = befs_find_brun_indirect(sb, data, fblock, run);
102 
103 	} else if (pos < data->max_double_indirect_range) {
104 		err = befs_find_brun_dblindirect(sb, data, fblock, run);
105 
106 	} else {
107 		befs_error(sb,
108 			   "befs_fblock2brun() was asked to find block %lu, "
109 			   "which is not mapped by the datastream\n", fblock);
110 		err = BEFS_ERR;
111 	}
112 	return err;
113 }
114 
115 /**
116  * befs_read_lsmylink - read long symlink from datastream.
117  * @sb: Filesystem superblock
118  * @ds: Datastrem to read from
119  * @buf: Buffer in which to place long symlink data
120  * @len: Length of the long symlink in bytes
121  *
122  * Returns the number of bytes read
123  */
124 size_t
befs_read_lsymlink(struct super_block * sb,befs_data_stream * ds,void * buff,befs_off_t len)125 befs_read_lsymlink(struct super_block * sb, befs_data_stream * ds, void *buff,
126 		   befs_off_t len)
127 {
128 	befs_off_t bytes_read = 0;	/* bytes readed */
129 	u16 plen;
130 	struct buffer_head *bh = NULL;
131 	befs_debug(sb, "---> befs_read_lsymlink() length: %Lu", len);
132 
133 	while (bytes_read < len) {
134 		bh = befs_read_datastream(sb, ds, bytes_read, NULL);
135 		if (!bh) {
136 			befs_error(sb, "BeFS: Error reading datastream block "
137 				   "starting from %Lu", bytes_read);
138 			befs_debug(sb, "<--- befs_read_lsymlink() ERROR");
139 			return bytes_read;
140 
141 		}
142 		plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
143 		    BEFS_SB(sb)->block_size : len - bytes_read;
144 		memcpy(buff + bytes_read, bh->b_data, plen);
145 		brelse(bh);
146 		bytes_read += plen;
147 	}
148 
149 	befs_debug(sb, "<--- befs_read_lsymlink() read %u bytes", bytes_read);
150 	return bytes_read;
151 }
152 
153 /**
154  * befs_count_blocks - blocks used by a file
155  * @sb: Filesystem superblock
156  * @ds: Datastream of the file
157  *
158  * Counts the number of fs blocks that the file represented by
159  * inode occupies on the filesystem, counting both regular file
160  * data and filesystem metadata (and eventually attribute data
161  * when we support attributes)
162 */
163 
164 befs_blocknr_t
befs_count_blocks(struct super_block * sb,befs_data_stream * ds)165 befs_count_blocks(struct super_block * sb, befs_data_stream * ds)
166 {
167 	befs_blocknr_t blocks;
168 	befs_blocknr_t datablocks;	/* File data blocks */
169 	befs_blocknr_t metablocks;	/* FS metadata blocks */
170 	befs_sb_info *befs_sb = BEFS_SB(sb);
171 
172 	befs_debug(sb, "---> befs_count_blocks()");
173 
174 	datablocks = ds->size >> befs_sb->block_shift;
175 	if (ds->size & (befs_sb->block_size - 1))
176 		datablocks += 1;
177 
178 	metablocks = 1;		/* Start with 1 block for inode */
179 
180 	/* Size of indirect block */
181 	if (ds->size > ds->max_direct_range)
182 		metablocks += ds->indirect.len;
183 
184 	/*
185 	   Double indir block, plus all the indirect blocks it mapps
186 	   In the double-indirect range, all block runs of data are
187 	   BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
188 	   how many data block runs are in the double-indirect region,
189 	   and from that we know how many indirect blocks it takes to
190 	   map them. We assume that the indirect blocks are also
191 	   BEFS_DBLINDIR_BRUN_LEN blocks long.
192 	 */
193 	if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
194 		uint dbl_bytes;
195 		uint dbl_bruns;
196 		uint indirblocks;
197 
198 		dbl_bytes =
199 		    ds->max_double_indirect_range - ds->max_indirect_range;
200 		dbl_bruns =
201 		    dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
202 		indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
203 
204 		metablocks += ds->double_indirect.len;
205 		metablocks += indirblocks;
206 	}
207 
208 	blocks = datablocks + metablocks;
209 	befs_debug(sb, "<--- befs_count_blocks() %u blocks", blocks);
210 
211 	return blocks;
212 }
213 
214 /*
215 	Finds the block run that starts at file block number blockno
216 	in the file represented by the datastream data, if that
217 	blockno is in the direct region of the datastream.
218 
219 	sb: the superblock
220 	data: the datastream
221 	blockno: the blocknumber to find
222 	run: The found run is passed back through this pointer
223 
224 	Return value is BEFS_OK if the blockrun is found, BEFS_ERR
225 	otherwise.
226 
227 	Algorithm:
228 	Linear search. Checks each element of array[] to see if it
229 	contains the blockno-th filesystem block. This is necessary
230 	because the block runs map variable amounts of data. Simply
231 	keeps a count of the number of blocks searched so far (sum),
232 	incrementing this by the length of each block run as we come
233 	across it. Adds sum to *count before returning (this is so
234 	you can search multiple arrays that are logicaly one array,
235 	as in the indirect region code).
236 
237 	When/if blockno is found, if blockno is inside of a block
238 	run as stored on disk, we offset the start and length members
239 	of the block run, so that blockno is the start and len is
240 	still valid (the run ends in the same place).
241 
242 	2001-11-15 Will Dyson
243 */
244 static int
befs_find_brun_direct(struct super_block * sb,befs_data_stream * data,befs_blocknr_t blockno,befs_block_run * run)245 befs_find_brun_direct(struct super_block *sb, befs_data_stream * data,
246 		      befs_blocknr_t blockno, befs_block_run * run)
247 {
248 	int i;
249 	befs_block_run *array = data->direct;
250 	befs_blocknr_t sum;
251 	befs_blocknr_t max_block =
252 	    data->max_direct_range >> BEFS_SB(sb)->block_shift;
253 
254 	befs_debug(sb, "---> befs_find_brun_direct(), find %lu", blockno);
255 
256 	if (blockno > max_block) {
257 		befs_error(sb, "befs_find_brun_direct() passed block outside of"
258 			   "direct region");
259 		return BEFS_ERR;
260 	}
261 
262 	for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
263 	     sum += array[i].len, i++) {
264 		if (blockno >= sum && blockno < sum + (array[i].len)) {
265 			int offset = blockno - sum;
266 			run->allocation_group = array[i].allocation_group;
267 			run->start = array[i].start + offset;
268 			run->len = array[i].len - offset;
269 
270 			befs_debug(sb, "---> befs_find_brun_direct(), "
271 				   "found %lu at direct[%d]", blockno, i);
272 			return BEFS_OK;
273 		}
274 	}
275 
276 	befs_debug(sb, "---> befs_find_brun_direct() ERROR");
277 	return BEFS_ERR;
278 }
279 
280 /*
281 	Finds the block run that starts at file block number blockno
282 	in the file represented by the datastream data, if that
283 	blockno is in the indirect region of the datastream.
284 
285 	sb: the superblock
286 	data: the datastream
287 	blockno: the blocknumber to find
288 	run: The found run is passed back through this pointer
289 
290 	Return value is BEFS_OK if the blockrun is found, BEFS_ERR
291 	otherwise.
292 
293 	Algorithm:
294 	For each block in the indirect run of the datastream, read
295 	it in and search through it for	search_blk.
296 
297 	XXX:
298 	Really should check to make sure blockno is inside indirect
299 	region.
300 
301 	2001-11-15 Will Dyson
302 */
303 static int
befs_find_brun_indirect(struct super_block * sb,befs_data_stream * data,befs_blocknr_t blockno,befs_block_run * run)304 befs_find_brun_indirect(struct super_block *sb,
305 			befs_data_stream * data, befs_blocknr_t blockno,
306 			befs_block_run * run)
307 {
308 	int i, j;
309 	befs_blocknr_t sum = 0;
310 	befs_blocknr_t indir_start_blk;
311 	befs_blocknr_t search_blk;
312 	struct buffer_head *indirblock;
313 	befs_disk_block_run *array;
314 
315 	befs_block_run indirect = data->indirect;
316 	befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
317 	int arraylen = befs_iaddrs_per_block(sb);
318 
319 	befs_debug(sb, "---> befs_find_brun_indirect(), find %lu", blockno);
320 
321 	indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
322 	search_blk = blockno - indir_start_blk;
323 
324 	/* Examine blocks of the indirect run one at a time */
325 	for (i = 0; i < indirect.len; i++) {
326 		indirblock = befs_bread(sb, indirblockno + i);
327 		if (indirblock == NULL) {
328 			befs_debug(sb,
329 				   "---> befs_find_brun_indirect() failed to "
330 				   "read disk block %lu from the indirect brun",
331 				   indirblockno + i);
332 			return BEFS_ERR;
333 		}
334 
335 		array = (befs_disk_block_run *) indirblock->b_data;
336 
337 		for (j = 0; j < arraylen; ++j) {
338 			int len = fs16_to_cpu(sb, array[j].len);
339 
340 			if (search_blk >= sum && search_blk < sum + len) {
341 				int offset = search_blk - sum;
342 				run->allocation_group =
343 				    fs32_to_cpu(sb, array[j].allocation_group);
344 				run->start =
345 				    fs16_to_cpu(sb, array[j].start) + offset;
346 				run->len =
347 				    fs16_to_cpu(sb, array[j].len) - offset;
348 
349 				brelse(indirblock);
350 				befs_debug(sb,
351 					   "<--- befs_find_brun_indirect() found "
352 					   "file block %lu at indirect[%d]",
353 					   blockno, j + (i * arraylen));
354 				return BEFS_OK;
355 			}
356 			sum += len;
357 		}
358 
359 		brelse(indirblock);
360 	}
361 
362 	/* Only fallthrough is an error */
363 	befs_error(sb, "BeFS: befs_find_brun_indirect() failed to find "
364 		   "file block %lu", blockno);
365 
366 	befs_debug(sb, "<--- befs_find_brun_indirect() ERROR");
367 	return BEFS_ERR;
368 }
369 
370 /*
371 	Finds the block run that starts at file block number blockno
372 	in the file represented by the datastream data, if that
373 	blockno is in the double-indirect region of the datastream.
374 
375 	sb: the superblock
376 	data: the datastream
377 	blockno: the blocknumber to find
378 	run: The found run is passed back through this pointer
379 
380 	Return value is BEFS_OK if the blockrun is found, BEFS_ERR
381 	otherwise.
382 
383 	Algorithm:
384 	The block runs in the double-indirect region are different.
385 	They are always allocated 4 fs blocks at a time, so each
386 	block run maps a constant amount of file data. This means
387 	that we can directly calculate how many block runs into the
388 	double-indirect region we need to go to get to the one that
389 	maps a particular filesystem block.
390 
391 	We do this in two stages. First we calculate which of the
392 	inode addresses in the double-indirect block will point us
393 	to the indirect block that contains the mapping for the data,
394 	then we calculate which of the inode addresses in that
395 	indirect block maps the data block we are after.
396 
397 	Oh, and once we've done that, we actually read in the blocks
398 	that contain the inode addresses we calculated above. Even
399 	though the double-indirect run may be several blocks long,
400 	we can calculate which of those blocks will contain the index
401 	we are after and only read that one. We then follow it to
402 	the indirect block and perform a  similar process to find
403 	the actual block run that maps the data block we are interested
404 	in.
405 
406 	Then we offset the run as in befs_find_brun_array() and we are
407 	done.
408 
409 	2001-11-15 Will Dyson
410 */
411 static int
befs_find_brun_dblindirect(struct super_block * sb,befs_data_stream * data,befs_blocknr_t blockno,befs_block_run * run)412 befs_find_brun_dblindirect(struct super_block *sb,
413 			   befs_data_stream * data, befs_blocknr_t blockno,
414 			   befs_block_run * run)
415 {
416 	int dblindir_indx;
417 	int indir_indx;
418 	int offset;
419 	int dbl_which_block;
420 	int which_block;
421 	int dbl_block_indx;
422 	int block_indx;
423 	off_t dblindir_leftover;
424 	befs_blocknr_t blockno_at_run_start;
425 	struct buffer_head *dbl_indir_block;
426 	struct buffer_head *indir_block;
427 	befs_block_run indir_run;
428 	befs_disk_inode_addr *iaddr_array = NULL;
429 	befs_sb_info *befs_sb = BEFS_SB(sb);
430 
431 	befs_blocknr_t indir_start_blk =
432 	    data->max_indirect_range >> befs_sb->block_shift;
433 
434 	off_t dbl_indir_off = blockno - indir_start_blk;
435 
436 	/* number of data blocks mapped by each of the iaddrs in
437 	 * the indirect block pointed to by the double indirect block
438 	 */
439 	size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
440 
441 	/* number of data blocks mapped by each of the iaddrs in
442 	 * the double indirect block
443 	 */
444 	size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
445 	    * BEFS_DBLINDIR_BRUN_LEN;
446 
447 	befs_debug(sb, "---> befs_find_brun_dblindirect() find %lu", blockno);
448 
449 	/* First, discover which of the double_indir->indir blocks
450 	 * contains pos. Then figure out how much of pos that
451 	 * accounted for. Then discover which of the iaddrs in
452 	 * the indirect block contains pos.
453 	 */
454 
455 	dblindir_indx = dbl_indir_off / diblklen;
456 	dblindir_leftover = dbl_indir_off % diblklen;
457 	indir_indx = dblindir_leftover / diblklen;
458 
459 	/* Read double indirect block */
460 	dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
461 	if (dbl_which_block > data->double_indirect.len) {
462 		befs_error(sb, "The double-indirect index calculated by "
463 			   "befs_read_brun_dblindirect(), %d, is outside the range "
464 			   "of the double-indirect block", dblindir_indx);
465 		return BEFS_ERR;
466 	}
467 
468 	dbl_indir_block =
469 	    befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
470 					dbl_which_block);
471 	if (dbl_indir_block == NULL) {
472 		befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
473 			   "double-indirect block at blockno %lu",
474 			   iaddr2blockno(sb,
475 					 &data->double_indirect) +
476 			   dbl_which_block);
477 		brelse(dbl_indir_block);
478 		return BEFS_ERR;
479 	}
480 
481 	dbl_block_indx =
482 	    dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
483 	iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
484 	indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
485 	brelse(dbl_indir_block);
486 	iaddr_array = NULL;
487 
488 	/* Read indirect block */
489 	which_block = indir_indx / befs_iaddrs_per_block(sb);
490 	if (which_block > indir_run.len) {
491 		befs_error(sb, "The indirect index calculated by "
492 			   "befs_read_brun_dblindirect(), %d, is outside the range "
493 			   "of the indirect block", indir_indx);
494 		return BEFS_ERR;
495 	}
496 
497 	indir_block =
498 	    befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
499 	if (indir_block == NULL) {
500 		befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
501 			   "indirect block at blockno %lu",
502 			   iaddr2blockno(sb, &indir_run) + which_block);
503 		brelse(indir_block);
504 		return BEFS_ERR;
505 	}
506 
507 	block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
508 	iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
509 	*run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
510 	brelse(indir_block);
511 	iaddr_array = NULL;
512 
513 	blockno_at_run_start = indir_start_blk;
514 	blockno_at_run_start += diblklen * dblindir_indx;
515 	blockno_at_run_start += iblklen * indir_indx;
516 	offset = blockno - blockno_at_run_start;
517 
518 	run->start += offset;
519 	run->len -= offset;
520 
521 	befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
522 		   " double_indirect_leftover = %lu",
523 		   blockno, dblindir_indx, indir_indx, dblindir_leftover);
524 
525 	return BEFS_OK;
526 }
527