datastream.c 16 KB

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