~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/befs/datastream.c

Version: ~ [ linux-5.10-rc1 ] ~ [ linux-5.9.1 ] ~ [ linux-5.8.16 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.72 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.152 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.202 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.240 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.240 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp