API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 29th, 2016
63
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 19.83 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #include "LLFS.h"
  3.  
  4. #include <iostream>
  5.  
  6. #define BLOCK_SIZE 512
  7. #define BLOCK_COUNT 4096
  8.  
  9. namespace Filesystem {
  10.  
  11.  
  12. void format(char *disk) {
  13. std::cout << "Formatting llfs disk '" << disk << "'\n";
  14. char *data = (char *) malloc(BLOCK_SIZE * BLOCK_COUNT);
  15. memset(data, 0, BLOCK_SIZE * BLOCK_COUNT);
  16.  
  17. superblock_t *superblock = (superblock_t *) data;
  18. superblock->type = 0x53464C4C;
  19. superblock->file_count = 1;
  20. superblock->inode_count = 1;
  21. printf(" Marking all blocks as available except superblock and inode blocks\n");
  22. // mark all blocks as available, except the first 10, and the inode blocks
  23. char *free_blocks = (char *) data + 512;
  24. memset(free_blocks, 0xFF, 512);
  25. for (int i = 0; i < 4096; i++) {
  26. if (i < 10 || (i % 256) == 255) {
  27. free_blocks[i / 8] &= ~(1 << (i % 8));
  28. }
  29. }
  30.  
  31. printf(" Marking all inodes as available\n");
  32. char *free_inodes = (char *) data + 1024;
  33. memset(free_inodes, 0xFF, 32);
  34.  
  35. printf(" Allocating first inode for root directory\n");
  36. free_inodes[0] &= ~(1);
  37. inode_t *rootInode = (inode_t *) data + (255 * 16);
  38. rootInode->file_size = 512;
  39. rootInode->file_type = FileType::DIR;
  40. rootInode->blocks[0] = 10;
  41. printf(" Allocating first block for root directory\n");
  42. free_blocks[1] &= ~(1 << (2));
  43. char *dir = data + 10 * 512;
  44. strncpy(dir + 1, ".", 30);
  45. strncpy(dir + 33, "..", 30);
  46. for (int i = 2; i < 16; i++) {
  47. dir[i*32] = (unsigned char) 0xFF;
  48. }
  49.  
  50. std::FILE *fdisk = fopen(disk, "w+");
  51. fwrite(data, 1, 512 * 4096, fdisk);
  52. fclose(fdisk);
  53. free(data);
  54. }
  55.  
  56. LLFS *mount(char *disk) {
  57.  
  58. std::FILE *fdisk = fopen(disk, "r+");
  59.  
  60. LLFS *fs = new LLFS(fdisk);
  61.  
  62. return fs;
  63. }
  64.  
  65. void unmount(LLFS *fs) {
  66. fs->sync();
  67. }
  68.  
  69. LLFS::LLFS(std::FILE *fdisk) : disk(fdisk) {
  70. superblock = (superblock_t *) malloc(512);
  71. free_blocks = (char *) malloc(512);
  72. free_inodes = (char *) malloc(32);
  73.  
  74. fseek(disk, 0, SEEK_SET);
  75. fread(superblock, 1, 512, disk);
  76. fread(free_blocks, 1, 512, disk);
  77. fread(free_inodes, 1, 32, disk);
  78.  
  79. for (int i = 0; i < 32; i++) {
  80. inode_block_cache[i] = nullptr;
  81. }
  82.  
  83. open_files_size = 32;
  84. open_files_index = 0;
  85. open_files = (File**) malloc(sizeof(File *) * open_files_size);
  86.  
  87. static_cache_size = 0;
  88. static_cache_index = 0;
  89. static_cache = nullptr;
  90.  
  91. dynamic_cache_size = 32;
  92. dynamic_cache_index = 0;
  93. dynamic_cache = (BlockCacheEntry **) malloc(sizeof(BlockCacheEntry*) * dynamic_cache_size);
  94.  
  95. root = new File(this, nullptr, "/", "/", 0, getInode(0), true);
  96. }
  97.  
  98. /*LLFS::~LLFS() {
  99. sync();
  100. fclose(disk);
  101.  
  102. delete superblock;
  103. delete free_blocks;
  104. delete free_inodes;
  105.  
  106. for (int i = 0; i < 32; i++) {
  107. if (inode_block_cache[i] != nullptr) {
  108. delete inode_block_cache[i];
  109. }
  110. }
  111.  
  112. for (int i = 0; i < open_files_index; i++) {
  113. delete open_files[i];
  114. }
  115. delete root;
  116.  
  117. delete open_files;
  118. delete[] inode_block_cache;
  119. }*/
  120.  
  121. File *LLFS::open(char *path) {
  122. if (strcmp("/", path) == 0) {
  123. return root;
  124. }
  125. for (int i = 0; i < open_files_index; i++) {
  126. if (strcmp(open_files[i]->getName(), path) == 0) {
  127. std::cout << "File already open\n";
  128. return nullptr;
  129. }
  130. }
  131. int len = strlen(path);
  132. char part[50];
  133. File *parent = root;
  134. int o = 0;
  135. for (int i = 1; i < len; i++) {
  136. char next = path[i];
  137. if (next == '/') {
  138. part[o] = '\0';
  139. parent = parent->getChildDir(part);
  140. o = 0;
  141. } else {
  142. part[o++] = next;
  143. }
  144. }
  145. part[o] = '\0';
  146. if (o == 0) {
  147. return parent;
  148. }
  149.  
  150. File *file = parent->getChild(part);
  151. open_files[open_files_index++] = file;
  152.  
  153. return file;
  154. }
  155.  
  156. void LLFS::close(File *file) {
  157. bool found = false;
  158. for (int i = 0; i < open_files_index; i++) {
  159. if (found) {
  160. open_files[i - 1] = open_files[i];
  161. } else {
  162. if (open_files[i] == file) {
  163. found = true;
  164. }
  165. }
  166. }
  167. if (found) {
  168. open_files_index--;
  169. }
  170. delete file;
  171. }
  172.  
  173. inode_t *LLFS::getInode(int number) {
  174. int inode_block = number / 16;
  175. if (inode_block_cache[inode_block] == nullptr) {
  176. std::cout << "Loading inode block " << inode_block << "\n";
  177. char *inode_block_data = (char *) malloc(512);
  178. fseek(disk, (inode_block * 256 + 255) * 512, SEEK_SET);
  179. fread(inode_block_data, 1, 512, disk);
  180. inode_block_cache[inode_block] = inode_block_data;
  181. }
  182. std::cout << "getting inode " << number << "\n";
  183. inode_t *inode = (inode_t *) (inode_block_cache[inode_block] + (number % 16) * 32);
  184. return inode;
  185. }
  186.  
  187. unsigned int LLFS::createInode() {
  188. int number = -1;
  189. // TODO continue from same point each time
  190. for (int i = 0; i < 32; i++) {
  191. unsigned char next = free_inodes[i];
  192. if (next != 0) {
  193. int o;
  194. for (o = 0; o < 8; o++) {
  195. if (((next >> o) & 1) == 1) {
  196. number = i * 8 + o;
  197. break;
  198. }
  199. }
  200. break;
  201. }
  202. }
  203. if (number == -1) {
  204. printf("Error: no free inodes for allocation");
  205. return NULL;
  206. }
  207. free_inodes[number / 8] &= ~(1 << (number % 8));
  208. printf("Allocating inode %d\n", number);
  209. superblock->inode_count++;
  210. return number;
  211. }
  212.  
  213. BlockCacheEntry *LLFS::allocateBlock() {
  214. int number = -1;
  215. // TODO continue from same point each time
  216. for (int i = 0; i < 512; i++) {
  217. unsigned char next = free_blocks[i];
  218. if (next != 0) {
  219. int o;
  220. for (o = 0; o < 8; o++) {
  221. if (((next >> o) & 1) == 1) {
  222. number = i * 8 + o;
  223. break;
  224. }
  225. }
  226. break;
  227. }
  228. }
  229. if (number == -1) {
  230. printf("Error: no free blocks for allocation");
  231. return nullptr;
  232. }
  233. free_blocks[number / 8] &= ~(1 << (number % 8));
  234. printf("Allocating block %d\n", number);
  235. return getBlock(number);
  236. }
  237.  
  238. void LLFS::sync() {
  239. fseek(disk, 0, SEEK_SET);
  240. fwrite(superblock, 1, 512, disk);
  241. fwrite(free_blocks, 1, 512, disk);
  242. fwrite(free_inodes, 1, 32, disk);
  243.  
  244. // if we crash here then we just have to notice that an inode/block is ununsed when we walk the tree
  245.  
  246. for (int i = 0; i < 32; i++) {
  247. if (inode_block_cache[i] != nullptr) {
  248. std::cout << "Saving inode block " << i << "\n";
  249. fseek(disk, (i * 256 + 255) * 512, SEEK_SET);
  250. fwrite(inode_block_cache[i], 1, 512, disk);
  251. }
  252. }
  253. // if we crash below here then we lost data but not consistency
  254.  
  255. for (int i = 0; i < dynamic_cache_index; i++) {
  256. BlockCacheEntry *entry = dynamic_cache[i];
  257. if (entry->modified) {
  258. fseek(disk, entry->number * 512, SEEK_SET);
  259. fwrite(entry->block, 1, 512, disk);
  260. }
  261. delete entry;
  262. dynamic_cache[i] = nullptr;
  263. }
  264. dynamic_cache_index = 0;
  265. }
  266.  
  267. BlockCacheEntry *LLFS::getBlock(int number) {
  268. if (static_cache_index > 0) {
  269.  
  270. }
  271. if (dynamic_cache_index > 0) {
  272. for (int i = 0; i < dynamic_cache_index; i++) {
  273. BlockCacheEntry *entry = dynamic_cache[i];
  274. if (entry->number == number) {
  275. std::cout << "Fetched block " << number << " from dynamic cache\n";
  276. return entry;
  277. }
  278. }
  279. }
  280. if (dynamic_cache_index == dynamic_cache_size) {
  281. std::cout << "Dynamic cache full, syncing to disk\n";
  282. sync();
  283. }
  284. std::cout << "Loading block " << number << " from disk\n";
  285. char *block = (char*) malloc(512);
  286. fseek(disk, number*512, SEEK_SET);
  287. fread(block, 1, 512, disk);
  288. BlockCacheEntry *entry = new BlockCacheEntry(number, block);
  289. dynamic_cache[dynamic_cache_index++] = entry;
  290. return entry;
  291. }
  292.  
  293. std::FILE *LLFS::getDisk() {
  294. return disk;
  295. }
  296.  
  297. void LLFS::releaseBlock(int num) {
  298. free_blocks[num/8] |= (1 << (num % 8));
  299. std::cout << "Releasing block " << num << "\n";
  300. }
  301.  
  302. void LLFS::releaseInode(int num) {
  303. free_inodes[num / 8] |= (1 << (num % 8));
  304. int inode_block = num / 16;
  305. if (inode_block_cache[inode_block] == nullptr) {
  306. std::cout << "Loading inode block " << inode_block << "\n";
  307. char *inode_block_data = (char *) malloc(512);
  308. fseek(disk, (inode_block * 256 + 255) * 512, SEEK_SET);
  309. fread(inode_block_data, 1, 512, disk);
  310. inode_block_cache[inode_block] = inode_block_data;
  311. }
  312. memset(inode_block_cache[inode_block] + (num % 16) * 32, 0, 32);
  313. std::cout << "Releasing inode " << num << "\n";
  314. }
  315.  
  316. File::File(LLFS *fs, File *parent, char *name, char *path, int inode_number, inode_t *in, bool isDir) :
  317. fs(fs), parent(parent), file_name(name), file_path(path), inode(in), isDir(isDir), inode_number(inode_number) {
  318. std::cout << "Creating file '" << path << " \n";
  319. created = inode != nullptr;
  320. seek_pos = 0;
  321.  
  322. if (isDir) {
  323. entries = (DirectoryEntry**) malloc(sizeof(DirectoryEntry*) * 32);
  324. entries_size = 32;
  325. entries_index = 0;
  326.  
  327. if (created) {
  328. BlockCacheEntry *data = fs->getBlock(inode->blocks[0]);
  329.  
  330. char *block = data->block;
  331. for (int i = 0; i < 16; i++) {
  332. unsigned char inode = block[i * 32];
  333. if (inode != 0xFF) {
  334. char *fname = (char*) malloc(31);
  335. memset(fname, 0, 31);
  336. strncpy(fname, (char *) (block + i * 32 + 1), 30);
  337. DirectoryEntry *entry = new DirectoryEntry(inode, fname);
  338. std::cout << "Loaded dir entry " << fname << " for directory " << file_path << "\n";
  339. entries[entries_index++] = entry;
  340. }
  341. }
  342. }
  343. } else {
  344. entries = nullptr;
  345. entries_size = 0;
  346. entries_index = 0;
  347. }
  348.  
  349. }
  350.  
  351. char *File::getPath() {
  352. return file_path;
  353. }
  354.  
  355. char *File::getName() {
  356. return file_name;
  357. }
  358.  
  359. File *File::getParent() {
  360. return parent;
  361. }
  362.  
  363. bool File::exists() {
  364. return created;
  365. }
  366.  
  367. bool File::isFile() {
  368. return !isDir;
  369. }
  370.  
  371. bool File::isDirectory() {
  372. return isDir;
  373. }
  374.  
  375. File *File::getChild(char *name) {
  376. if (!isDir) {
  377. std::cout << "[Error: cannot get child of non-directory" << file_path << "]\n";
  378. return nullptr;
  379. }
  380. std::cout << "Getting child " << name << " from " << file_path << "\n";
  381. char *fpath = (char*) malloc(250);
  382. strcpy(fpath, file_path);
  383. strcat(fpath, name);
  384. char *fname = (char*)malloc(strlen(name+1));
  385. strcpy(fname, name);
  386. for (int i = 0; i < entries_index; i++) {
  387. if (strcmp(entries[i]->name, name) == 0) {
  388. return new File(fs, this, fname, fpath, entries[i]->inode, fs->getInode(entries[i]->inode), false);
  389. }
  390. }
  391. return new File(fs, this, fname, fpath, -1, nullptr, false);
  392. }
  393.  
  394. File *File::getChildDir(char *name) {
  395. if (!isDir) {
  396. std::cout << "[Error: cannot get child of non-directory" << file_path << "]\n";
  397. return nullptr;
  398. }
  399. // TODO needs to call open
  400. std::cout << "Getting child directory " << name << " from " << file_path << "\n";
  401. char *fpath = (char*) malloc(250);
  402. strcpy(fpath, file_path);
  403. strcat(fpath, name);
  404. strcat(fpath, "/");
  405. char *fname = (char*) malloc(strlen(name + 1));
  406. strcpy(fname, name);
  407. for (int i = 0; i < entries_index; i++) {
  408. if (strcmp(entries[i]->name, name) == 0) {
  409. return new File(fs, this, fname, fpath, entries[i]->inode, fs->getInode(entries[i]->inode), true);
  410. }
  411. }
  412. return new File(fs, this, fname, fpath, -1, nullptr, true);
  413. }
  414.  
  415. DirectoryEntry **File::getDirectoryContents() {
  416. return entries;
  417. }
  418.  
  419. void File::create() {
  420. if (isDir) {
  421. std::cout << "Use mkdir instead\n";
  422. return;
  423. }
  424. if (created) {
  425. std::cout << "File already created\n";
  426. return;
  427. }
  428. created = true;
  429. inode_number = fs->createInode();
  430. std::cout << "Creating new file '" << file_path << "' " << inode_number << " \n";
  431. inode = fs->getInode(inode_number);
  432. inode->file_size = 0;
  433. inode->file_type = FileType::FILE;
  434. parent->addFile(this);
  435. }
  436.  
  437. void File::addFile(File *child) {
  438. if (!isDir) {
  439. std::cout << "Can only add files to directories\n";
  440. return;
  441. }
  442. std::cout << "Adding file " << child->file_path << " to directory " << file_path << "\n";
  443. DirectoryEntry *entry = new DirectoryEntry(child->inode_number, child->file_name);
  444. entries[entries_index++] = entry;
  445. BlockCacheEntry *block = fs->getBlock(inode->blocks[0]);
  446. std::cout << "Saving directory contents of " << file_path << " to block " << inode->blocks[0] << "\n";
  447. block->modified = true;
  448. for (int i = 0; i < 16; i++) {
  449. if (i >= entries_index) {
  450. block->block[i * 32] = (unsigned char) 0xFF;
  451. } else {
  452. block->block[i * 32] = entries[i]->inode;
  453. strncpy((char*)(block->block + i * 32 + 1), entries[i]->name, 31);
  454. }
  455. }
  456. }
  457.  
  458. void File::seek(int pos) {
  459. seek_pos = pos;
  460. std::cout << "Seeking file " << file_path << " to position " << pos << "\n";
  461. }
  462.  
  463. void File::write(char *src, int len) {
  464. std::cout << "Writing " << len << " bytes to " << file_path << " at position " << seek_pos << "\n";
  465. int remaining = len;
  466. int offset = 0;
  467. while (remaining > 0) {
  468. int block_pos = seek_pos / 512;
  469. BlockCacheEntry *block = nullptr;
  470. if (inode->blocks[block_pos] == 0) {
  471. block = fs->allocateBlock();
  472. inode->blocks[block_pos] = block->number;
  473. } else {
  474. block = fs->getBlock(inode->blocks[block_pos]);
  475. }
  476. int subpos = seek_pos % 512;
  477. int sublen = 512 - subpos;
  478. if (remaining < sublen) {
  479. sublen = remaining;
  480. }
  481. memcpy(block->block + subpos, src + offset, sublen);
  482. block->modified = true;
  483. seek_pos += sublen;
  484. remaining -= sublen;
  485. offset += sublen;
  486. }
  487. if (seek_pos > inode->file_size) {
  488. inode->file_size = seek_pos;
  489. std::cout << "new file size is " << inode->file_size << "\n";
  490. }
  491. }
  492.  
  493. int File::read(char *dest, int len) {
  494. if (seek_pos + len >= inode->file_size) {
  495. len = inode->file_size - seek_pos;
  496. }
  497. std::cout << "Reading " << len << " bytes from file " << file_path << " at position " << seek_pos << "\n";
  498. int remaining = len;
  499. int offset = 0;
  500. while (remaining > 0) {
  501. int block_pos = seek_pos / 512;
  502. BlockCacheEntry *block = nullptr;
  503. if (inode->blocks[block_pos] == 0) {
  504. block = fs->allocateBlock();
  505. inode->blocks[block_pos] = block->number;
  506. } else {
  507. block = fs->getBlock(inode->blocks[block_pos]);
  508. }
  509. int subpos = seek_pos % 512;
  510. int sublen = 512 - subpos;
  511. if (remaining < sublen) {
  512. sublen = remaining;
  513. }
  514. memcpy(dest + offset, block->block + subpos, sublen);
  515. seek_pos += sublen;
  516. offset += sublen;
  517. remaining -= sublen;
  518. }
  519.  
  520. return len;
  521. }
  522.  
  523. void File::mkdir() {
  524. if (!isDir) {
  525. std::cout << "Cannot make a directory in a file\n";
  526. return;
  527. }
  528. if (created) {
  529. std::cout << "Directory already created\n";
  530. return;
  531. }
  532. created = true;
  533. inode_number = fs->createInode();
  534. std::cout << "Creating new dir '" << file_path << "' " << inode_number << " \n";
  535. inode = fs->getInode(inode_number);
  536. inode->file_size = 512;
  537. inode->file_type = FileType::DIR;
  538. parent->addFile(this);
  539.  
  540. entries = (DirectoryEntry**) malloc(sizeof(DirectoryEntry*) * 32);
  541. entries_size = 32;
  542. entries_index = 0;
  543.  
  544. DirectoryEntry *self_dir = new DirectoryEntry(inode_number, ".");
  545. DirectoryEntry *parent_dir = new DirectoryEntry(parent->inode_number, "..");
  546. entries[entries_index++] = self_dir;
  547. entries[entries_index++] = parent_dir;
  548.  
  549. BlockCacheEntry *data = fs->allocateBlock();
  550. inode->blocks[0] = data->number;
  551. std::cout << "Saving directory contents of " << file_path << " to block " << inode->blocks[0] << "\n";
  552. data->modified = true;
  553. for (int i = 0; i < 16; i++) {
  554. if (i >= entries_index) {
  555. data->block[i * 32] = (unsigned char) 0xFF;
  556. } else {
  557. data->block[i * 32] = entries[i]->inode;
  558. strncpy((char*) (data->block + i * 32 + 1), entries[i]->name, 31);
  559. }
  560. }
  561.  
  562. }
  563.  
  564. void File::remove() {
  565. if (parent == nullptr) {
  566. std::cout << "Cannot delete the root directory\n";
  567. }
  568. if (isDir) {
  569. std::cout << "Deleting directory " << file_path << "\n";
  570. for (int i = 0; i < entries_index; i++) {
  571. DirectoryEntry *entry = entries[i];
  572. inode_t *child_inode = fs->getInode(entry->inode);
  573. if (child_inode->file_type == FileType::DIR) {
  574. File *child_dir = getChildDir(entry->name);
  575. child_dir->remove();
  576. } else {
  577. File *child = getChild(entry->name);
  578. child->remove();
  579. }
  580. }
  581. } else {
  582. std::cout << "Deleting file " << file_path << "\n";
  583. }
  584.  
  585. parent->removeFile(inode_number);
  586.  
  587. for (int i = 0; i < 10; i++) {
  588. if (inode->blocks[i] != 0) {
  589. fs->releaseBlock(inode->blocks[i]);
  590. }
  591. }
  592. fs->releaseInode(inode_number);
  593. }
  594.  
  595. void File::removeFile(int inode_num) {
  596. if (!isDir) {
  597. std::cout << "Can only remove files from directories\n";
  598. return;
  599. }
  600. bool found = false;
  601. DirectoryEntry *found_entry = nullptr;
  602. for (int i = 0; i < entries_index; i++) {
  603. if (found) {
  604. entries[i - 1] = entries[i];
  605. } else {
  606. if (entries[i]->inode == inode_num) {
  607. found = true;
  608. found_entry = entries[i];
  609. }
  610. }
  611. }
  612. if (found_entry == nullptr) {
  613. std::cout << "File with inode " << inode_num << " not found in directory " << file_path << "\n";
  614. return;
  615. }
  616. entries_index--;
  617. delete found_entry;
  618. BlockCacheEntry *block = fs->getBlock(inode->blocks[0]);
  619. std::cout << "Saving directory contents of " << file_path << " to block " << inode->blocks[0] << "\n";
  620. block->modified = true;
  621. for (int i = 0; i < 16; i++) {
  622. if (i >= entries_index) {
  623. block->block[i * 32] = (unsigned char) 0xFF;
  624. memset(block->block + i * 32 + 1, 0, 31);
  625. } else {
  626. block->block[i * 32] = entries[i]->inode;
  627. strncpy((char*) (block->block + i * 32 + 1), entries[i]->name, 31);
  628. }
  629. }
  630. }
  631.  
  632.  
  633. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!