Ext2FileSystem.cpp 38 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167
  1. #include "Ext2FileSystem.h"
  2. #include "ext2_fs.h"
  3. #include "UnixTypes.h"
  4. #include <AK/Bitmap.h>
  5. #include <AK/StdLib.h>
  6. #include <AK/kmalloc.h>
  7. #include <AK/ktime.h>
  8. #include <AK/kstdio.h>
  9. #include <AK/BufferStream.h>
  10. #include <LibC/errno_numbers.h>
  11. //#define EXT2_DEBUG
  12. RetainPtr<Ext2FS> Ext2FS::create(RetainPtr<DiskDevice>&& device)
  13. {
  14. return adopt(*new Ext2FS(move(device)));
  15. }
  16. Ext2FS::Ext2FS(RetainPtr<DiskDevice>&& device)
  17. : DiskBackedFS(move(device))
  18. {
  19. }
  20. Ext2FS::~Ext2FS()
  21. {
  22. }
  23. ByteBuffer Ext2FS::readSuperBlock() const
  24. {
  25. auto buffer = ByteBuffer::createUninitialized(1024);
  26. device().readBlock(2, buffer.pointer());
  27. device().readBlock(3, buffer.offsetPointer(512));
  28. return buffer;
  29. }
  30. bool Ext2FS::writeSuperBlock(const ext2_super_block& sb)
  31. {
  32. const byte* raw = (const byte*)&sb;
  33. bool success;
  34. success = device().writeBlock(2, raw);
  35. ASSERT(success);
  36. success = device().writeBlock(3, raw + 512);
  37. ASSERT(success);
  38. // FIXME: This is an ugly way to refresh the superblock cache. :-|
  39. superBlock();
  40. return true;
  41. }
  42. unsigned Ext2FS::firstBlockOfGroup(unsigned groupIndex) const
  43. {
  44. return superBlock().s_first_data_block + (groupIndex * superBlock().s_blocks_per_group);
  45. }
  46. const ext2_super_block& Ext2FS::superBlock() const
  47. {
  48. if (!m_cachedSuperBlock)
  49. m_cachedSuperBlock = readSuperBlock();
  50. return *reinterpret_cast<ext2_super_block*>(m_cachedSuperBlock.pointer());
  51. }
  52. const ext2_group_desc& Ext2FS::blockGroupDescriptor(unsigned groupIndex) const
  53. {
  54. // FIXME: Should this fail gracefully somehow?
  55. ASSERT(groupIndex <= m_blockGroupCount);
  56. if (!m_cachedBlockGroupDescriptorTable) {
  57. unsigned blocksToRead = ceilDiv(m_blockGroupCount * (unsigned)sizeof(ext2_group_desc), blockSize());
  58. unsigned firstBlockOfBGDT = blockSize() == 1024 ? 2 : 1;
  59. #ifdef EXT2_DEBUG
  60. kprintf("ext2fs: block group count: %u, blocks-to-read: %u\n", m_blockGroupCount, blocksToRead);
  61. kprintf("ext2fs: first block of BGDT: %u\n", firstBlockOfBGDT);
  62. #endif
  63. m_cachedBlockGroupDescriptorTable = readBlocks(firstBlockOfBGDT, blocksToRead);
  64. }
  65. return reinterpret_cast<ext2_group_desc*>(m_cachedBlockGroupDescriptorTable.pointer())[groupIndex - 1];
  66. }
  67. bool Ext2FS::initialize()
  68. {
  69. auto& superBlock = this->superBlock();
  70. #ifdef EXT2_DEBUG
  71. kprintf("ext2fs: super block magic: %x (super block size: %u)\n", superBlock.s_magic, sizeof(ext2_super_block));
  72. #endif
  73. if (superBlock.s_magic != EXT2_SUPER_MAGIC)
  74. return false;
  75. #ifdef EXT2_DEBUG
  76. kprintf("ext2fs: %u inodes, %u blocks\n", superBlock.s_inodes_count, superBlock.s_blocks_count);
  77. kprintf("ext2fs: block size = %u\n", EXT2_BLOCK_SIZE(&superBlock));
  78. kprintf("ext2fs: first data block = %u\n", superBlock.s_first_data_block);
  79. kprintf("ext2fs: inodes per block = %u\n", inodesPerBlock());
  80. kprintf("ext2fs: inodes per group = %u\n", inodesPerGroup());
  81. kprintf("ext2fs: free inodes = %u\n", superBlock.s_free_inodes_count);
  82. kprintf("ext2fs: desc per block = %u\n", EXT2_DESC_PER_BLOCK(&superBlock));
  83. kprintf("ext2fs: desc size = %u\n", EXT2_DESC_SIZE(&superBlock));
  84. #endif
  85. setBlockSize(EXT2_BLOCK_SIZE(&superBlock));
  86. m_blockGroupCount = ceilDiv(superBlock.s_blocks_count, superBlock.s_blocks_per_group);
  87. if (m_blockGroupCount == 0) {
  88. kprintf("ext2fs: no block groups :(\n");
  89. return false;
  90. }
  91. // Preheat the BGD cache.
  92. blockGroupDescriptor(0);
  93. #ifdef EXT2_DEBUG
  94. for (unsigned i = 1; i <= m_blockGroupCount; ++i) {
  95. auto& group = blockGroupDescriptor(i);
  96. kprintf("ext2fs: group[%u] { block_bitmap: %u, inode_bitmap: %u, inode_table: %u }\n",
  97. i,
  98. group.bg_block_bitmap,
  99. group.bg_inode_bitmap,
  100. group.bg_inode_table);
  101. }
  102. #endif
  103. return true;
  104. }
  105. const char* Ext2FS::class_name() const
  106. {
  107. return "ext2fs";
  108. }
  109. InodeIdentifier Ext2FS::rootInode() const
  110. {
  111. return { id(), EXT2_ROOT_INO };
  112. }
  113. #ifdef EXT2_DEBUG
  114. static void dumpExt2Inode(const ext2_inode& inode)
  115. {
  116. kprintf("Dump of ext2_inode:\n");
  117. kprintf(" i_size: %u\n", inode.i_size);
  118. kprintf(" i_mode: %u\n", inode.i_mode);
  119. kprintf(" i_blocks: %u\n", inode.i_blocks);
  120. kprintf(" i_uid: %u\n", inode.i_uid);
  121. kprintf(" i_gid: %u\n", inode.i_gid);
  122. }
  123. #endif
  124. ByteBuffer Ext2FS::readBlockContainingInode(unsigned inode, unsigned& blockIndex, unsigned& offset) const
  125. {
  126. auto& superBlock = this->superBlock();
  127. if (inode != EXT2_ROOT_INO && inode < EXT2_FIRST_INO(&superBlock))
  128. return { };
  129. if (inode > superBlock.s_inodes_count)
  130. return { };
  131. auto& bgd = blockGroupDescriptor(groupIndexFromInode(inode));
  132. offset = ((inode - 1) % inodesPerGroup()) * inodeSize();
  133. blockIndex = bgd.bg_inode_table + (offset >> EXT2_BLOCK_SIZE_BITS(&superBlock));
  134. offset &= blockSize() - 1;
  135. return readBlock(blockIndex);
  136. }
  137. OwnPtr<ext2_inode> Ext2FS::lookupExt2Inode(unsigned inode) const
  138. {
  139. unsigned blockIndex;
  140. unsigned offset;
  141. auto block = readBlockContainingInode(inode, blockIndex, offset);
  142. if (!block)
  143. return { };
  144. auto* e2inode = reinterpret_cast<ext2_inode*>(kmalloc(inodeSize()));
  145. memcpy(e2inode, reinterpret_cast<ext2_inode*>(block.offsetPointer(offset)), inodeSize());
  146. #ifdef EXT2_DEBUG
  147. dumpExt2Inode(*e2inode);
  148. #endif
  149. return OwnPtr<ext2_inode>(e2inode);
  150. }
  151. InodeMetadata Ext2FS::inodeMetadata(InodeIdentifier inode) const
  152. {
  153. ASSERT(inode.fsid() == id());
  154. auto e2inode = lookupExt2Inode(inode.index());
  155. if (!e2inode)
  156. return InodeMetadata();
  157. InodeMetadata metadata;
  158. metadata.inode = inode;
  159. metadata.size = e2inode->i_size;
  160. metadata.mode = e2inode->i_mode;
  161. metadata.uid = e2inode->i_uid;
  162. metadata.gid = e2inode->i_gid;
  163. metadata.linkCount = e2inode->i_links_count;
  164. metadata.atime = e2inode->i_atime;
  165. metadata.ctime = e2inode->i_ctime;
  166. metadata.mtime = e2inode->i_mtime;
  167. metadata.dtime = e2inode->i_dtime;
  168. metadata.blockSize = blockSize();
  169. metadata.blockCount = e2inode->i_blocks;
  170. if (isBlockDevice(e2inode->i_mode) || isCharacterDevice(e2inode->i_mode)) {
  171. unsigned dev = e2inode->i_block[0];
  172. metadata.majorDevice = (dev & 0xfff00) >> 8;
  173. metadata.minorDevice= (dev & 0xff) | ((dev >> 12) & 0xfff00);
  174. }
  175. return metadata;
  176. }
  177. Vector<unsigned> Ext2FS::blockListForInode(const ext2_inode& e2inode) const
  178. {
  179. unsigned entriesPerBlock = EXT2_ADDR_PER_BLOCK(&superBlock());
  180. // NOTE: i_blocks is number of 512-byte blocks, not number of fs-blocks.
  181. unsigned blockCount = e2inode.i_blocks / (blockSize() / 512);
  182. unsigned blocksRemaining = blockCount;
  183. Vector<unsigned> list;
  184. list.ensureCapacity(blocksRemaining);
  185. unsigned directCount = min(blockCount, (unsigned)EXT2_NDIR_BLOCKS);
  186. for (unsigned i = 0; i < directCount; ++i) {
  187. list.unchecked_append(e2inode.i_block[i]);
  188. --blocksRemaining;
  189. }
  190. if (!blocksRemaining)
  191. return list;
  192. auto processBlockArray = [&] (unsigned arrayBlockIndex, auto&& callback) {
  193. auto arrayBlock = readBlock(arrayBlockIndex);
  194. ASSERT(arrayBlock);
  195. auto* array = reinterpret_cast<const __u32*>(arrayBlock.pointer());
  196. unsigned count = min(blocksRemaining, entriesPerBlock);
  197. for (unsigned i = 0; i < count; ++i) {
  198. if (!array[i]) {
  199. blocksRemaining = 0;
  200. return;
  201. }
  202. callback(array[i]);
  203. --blocksRemaining;
  204. }
  205. };
  206. processBlockArray(e2inode.i_block[EXT2_IND_BLOCK], [&] (unsigned entry) {
  207. list.unchecked_append(entry);
  208. });
  209. if (!blocksRemaining)
  210. return list;
  211. processBlockArray(e2inode.i_block[EXT2_DIND_BLOCK], [&] (unsigned entry) {
  212. processBlockArray(entry, [&] (unsigned entry) {
  213. list.unchecked_append(entry);
  214. });
  215. });
  216. if (!blocksRemaining)
  217. return list;
  218. processBlockArray(e2inode.i_block[EXT2_TIND_BLOCK], [&] (unsigned entry) {
  219. processBlockArray(entry, [&] (unsigned entry) {
  220. processBlockArray(entry, [&] (unsigned entry) {
  221. list.unchecked_append(entry);
  222. });
  223. });
  224. });
  225. return list;
  226. }
  227. Ext2FSInode::Ext2FSInode(Ext2FS& fs, unsigned index, const ext2_inode& raw_inode)
  228. : CoreInode(fs, index)
  229. , m_raw_inode(raw_inode)
  230. {
  231. }
  232. Ext2FSInode::~Ext2FSInode()
  233. {
  234. }
  235. void Ext2FSInode::populate_metadata() const
  236. {
  237. m_metadata.inode = identifier();
  238. m_metadata.size = m_raw_inode.i_size;
  239. m_metadata.mode = m_raw_inode.i_mode;
  240. m_metadata.uid = m_raw_inode.i_uid;
  241. m_metadata.gid = m_raw_inode.i_gid;
  242. m_metadata.linkCount = m_raw_inode.i_links_count;
  243. m_metadata.atime = m_raw_inode.i_atime;
  244. m_metadata.ctime = m_raw_inode.i_ctime;
  245. m_metadata.mtime = m_raw_inode.i_mtime;
  246. m_metadata.dtime = m_raw_inode.i_dtime;
  247. m_metadata.blockSize = fs().blockSize();
  248. m_metadata.blockCount = m_raw_inode.i_blocks;
  249. if (isBlockDevice(m_raw_inode.i_mode) || isCharacterDevice(m_raw_inode.i_mode)) {
  250. unsigned dev = m_raw_inode.i_block[0];
  251. m_metadata.majorDevice = (dev & 0xfff00) >> 8;
  252. m_metadata.minorDevice= (dev & 0xff) | ((dev >> 12) & 0xfff00);
  253. }
  254. }
  255. RetainPtr<CoreInode> Ext2FS::get_inode(InodeIdentifier inode) const
  256. {
  257. ASSERT(inode.fsid() == id());
  258. {
  259. LOCKER(m_inode_cache_lock);
  260. auto it = m_inode_cache.find(inode.index());
  261. if (it != m_inode_cache.end())
  262. return (*it).value;
  263. }
  264. auto raw_inode = lookupExt2Inode(inode.index());
  265. if (!raw_inode)
  266. return nullptr;
  267. LOCKER(m_inode_cache_lock);
  268. auto it = m_inode_cache.find(inode.index());
  269. if (it != m_inode_cache.end())
  270. return (*it).value;
  271. auto new_inode = adopt(*new Ext2FSInode(const_cast<Ext2FS&>(*this), inode.index(), *raw_inode));
  272. m_inode_cache.set(inode.index(), new_inode.copyRef());
  273. return new_inode;
  274. }
  275. Unix::ssize_t Ext2FSInode::read_bytes(Unix::off_t offset, Unix::size_t count, byte* buffer, FileDescriptor*)
  276. {
  277. ASSERT(offset >= 0);
  278. if (m_raw_inode.i_size == 0)
  279. return 0;
  280. // Symbolic links shorter than 60 characters are store inline inside the i_block array.
  281. // This avoids wasting an entire block on short links. (Most links are short.)
  282. static const unsigned max_inline_symlink_length = 60;
  283. if (is_symlink() && size() < max_inline_symlink_length) {
  284. Unix::ssize_t nread = min((Unix::off_t)size() - offset, static_cast<Unix::off_t>(count));
  285. memcpy(buffer, m_raw_inode.i_block + offset, nread);
  286. return nread;
  287. }
  288. if (m_block_list.isEmpty()) {
  289. auto block_list = fs().blockListForInode(m_raw_inode);
  290. LOCKER(m_lock);
  291. if (m_block_list.size() != block_list.size())
  292. m_block_list = move(block_list);
  293. }
  294. if (m_block_list.isEmpty()) {
  295. kprintf("ext2fs: read_bytes: empty block list for inode %u\n", index());
  296. return -EIO;
  297. }
  298. const size_t block_size = fs().blockSize();
  299. dword first_block_logical_index = offset / block_size;
  300. dword last_block_logical_index = (offset + count) / block_size;
  301. if (last_block_logical_index >= m_block_list.size())
  302. last_block_logical_index = m_block_list.size() - 1;
  303. dword offset_into_first_block = offset % block_size;
  304. Unix::ssize_t nread = 0;
  305. Unix::size_t remaining_count = min((Unix::off_t)count, (Unix::off_t)size() - offset);
  306. byte* out = buffer;
  307. #ifdef EXT2_DEBUG
  308. kprintf("ok let's do it, read(%llu, %u) -> blocks %u thru %u, oifb: %u\n", offset, count, firstBlockLogicalIndex, lastBlockLogicalIndex, offsetIntoFirstBlock);
  309. #endif
  310. for (dword bi = first_block_logical_index; remaining_count && bi <= last_block_logical_index; ++bi) {
  311. auto block = fs().readBlock(m_block_list[bi]);
  312. if (!block) {
  313. kprintf("ext2fs: read_bytes: readBlock(%u) failed (lbi: %u)\n", m_block_list[bi], bi);
  314. return -EIO;
  315. }
  316. dword offset_into_block = (bi == first_block_logical_index) ? offset_into_first_block : 0;
  317. dword num_bytes_to_copy = min(block_size - offset_into_block, remaining_count);
  318. memcpy(out, block.pointer() + offset_into_block, num_bytes_to_copy);
  319. remaining_count -= num_bytes_to_copy;
  320. nread += num_bytes_to_copy;
  321. out += num_bytes_to_copy;
  322. }
  323. return nread;
  324. }
  325. Unix::ssize_t Ext2FS::read_inode_bytes(InodeIdentifier inode, Unix::off_t offset, Unix::size_t count, byte* buffer, FileDescriptor*) const
  326. {
  327. ASSERT(offset >= 0);
  328. ASSERT(inode.fsid() == id());
  329. auto e2inode = lookupExt2Inode(inode.index());
  330. if (!e2inode) {
  331. kprintf("ext2fs: readInodeBytes: metadata lookup for inode %u failed\n", inode.index());
  332. return -EIO;
  333. }
  334. #if 0
  335. // FIXME: We can't fail here while the directory traversal depends on this function. :]
  336. if (isDirectory(e2inode->i_mode))
  337. return -EISDIR;
  338. #endif
  339. if (e2inode->i_size == 0)
  340. return 0;
  341. // Symbolic links shorter than 60 characters are store inline inside the i_block array.
  342. // This avoids wasting an entire block on short links. (Most links are short.)
  343. static const unsigned maxInlineSymlinkLength = 60;
  344. if (isSymbolicLink(e2inode->i_mode) && e2inode->i_size < maxInlineSymlinkLength) {
  345. Unix::ssize_t nread = min((Unix::off_t)e2inode->i_size - offset, static_cast<Unix::off_t>(count));
  346. memcpy(buffer, e2inode->i_block + offset, nread);
  347. return nread;
  348. }
  349. // FIXME: It's grossly inefficient to fetch the blocklist on every call to readInodeBytes().
  350. // It needs to be cached!
  351. auto list = blockListForInode(*e2inode);
  352. if (list.isEmpty()) {
  353. kprintf("ext2fs: readInodeBytes: empty block list for inode %u\n", inode.index());
  354. return -EIO;
  355. }
  356. dword firstBlockLogicalIndex = offset / blockSize();
  357. dword lastBlockLogicalIndex = (offset + count) / blockSize();
  358. if (lastBlockLogicalIndex >= list.size())
  359. lastBlockLogicalIndex = list.size() - 1;
  360. dword offsetIntoFirstBlock = offset % blockSize();
  361. Unix::ssize_t nread = 0;
  362. Unix::size_t remainingCount = min((Unix::off_t)count, (Unix::off_t)e2inode->i_size - offset);
  363. byte* out = buffer;
  364. #ifdef EXT2_DEBUG
  365. kprintf("ok let's do it, read(%llu, %u) -> blocks %u thru %u, oifb: %u\n", offset, count, firstBlockLogicalIndex, lastBlockLogicalIndex, offsetIntoFirstBlock);
  366. #endif
  367. for (dword bi = firstBlockLogicalIndex; bi <= lastBlockLogicalIndex; ++bi) {
  368. auto block = readBlock(list[bi]);
  369. if (!block) {
  370. kprintf("ext2fs: readInodeBytes: readBlock(%u) failed (lbi: %u)\n", list[bi], bi);
  371. return -EIO;
  372. }
  373. dword offsetIntoBlock;
  374. if (bi == firstBlockLogicalIndex)
  375. offsetIntoBlock = offsetIntoFirstBlock;
  376. else
  377. offsetIntoBlock = 0;
  378. dword numBytesToCopy = min(blockSize() - offsetIntoBlock, remainingCount);
  379. memcpy(out, block.pointer() + offsetIntoBlock, numBytesToCopy);
  380. remainingCount -= numBytesToCopy;
  381. nread += numBytesToCopy;
  382. out += numBytesToCopy;
  383. }
  384. return nread;
  385. }
  386. bool Ext2FS::writeInode(InodeIdentifier inode, const ByteBuffer& data)
  387. {
  388. ASSERT(inode.fsid() == id());
  389. auto e2inode = lookupExt2Inode(inode.index());
  390. if (!e2inode) {
  391. kprintf("ext2fs: writeInode: metadata lookup for inode %u failed\n", inode.index());
  392. return false;
  393. }
  394. // FIXME: Support writing to symlink inodes.
  395. ASSERT(!isSymbolicLink(e2inode->i_mode));
  396. unsigned blocksNeededBefore = ceilDiv(e2inode->i_size, blockSize());
  397. unsigned blocksNeededAfter = ceilDiv((unsigned)data.size(), blockSize());
  398. // FIXME: Support growing or shrinking the block list.
  399. ASSERT(blocksNeededBefore == blocksNeededAfter);
  400. auto list = blockListForInode(*e2inode);
  401. if (list.isEmpty()) {
  402. kprintf("ext2fs: writeInode: empty block list for inode %u\n", inode.index());
  403. return false;
  404. }
  405. for (unsigned i = 0; i < list.size(); ++i) {
  406. auto section = data.slice(i * blockSize(), blockSize());
  407. //kprintf("section = %p (%u)\n", section.pointer(), section.size());
  408. bool success = writeBlock(list[i], section);
  409. ASSERT(success);
  410. }
  411. return true;
  412. }
  413. bool Ext2FSInode::traverse_as_directory(Function<bool(const FS::DirectoryEntry&)> callback)
  414. {
  415. ASSERT(metadata().isDirectory());
  416. #ifdef EXT2_DEBUG
  417. kprintf("Ext2Inode::traverse_as_directory: inode=%u:\n", index());
  418. #endif
  419. auto buffer = read_entire();
  420. ASSERT(buffer);
  421. auto* entry = reinterpret_cast<ext2_dir_entry_2*>(buffer.pointer());
  422. while (entry < buffer.endPointer()) {
  423. if (entry->inode != 0) {
  424. #ifdef EXT2_DEBUG
  425. kprintf("Ext2Inode::traverse_as_directory: %u, name_len: %u, rec_len: %u, file_type: %u, name: %s\n", entry->inode, entry->name_len, entry->rec_len, entry->file_type, namebuf);
  426. #endif
  427. if (!callback({ entry->name, entry->name_len, { fsid(), entry->inode }, entry->file_type }))
  428. break;
  429. }
  430. entry = (ext2_dir_entry_2*)((char*)entry + entry->rec_len);
  431. }
  432. return true;
  433. }
  434. bool Ext2FS::deprecated_enumerateDirectoryInode(InodeIdentifier inode, Function<bool(const DirectoryEntry&)> callback) const
  435. {
  436. ASSERT(inode.fsid() == id());
  437. ASSERT(isDirectoryInode(inode.index()));
  438. #ifdef EXT2_DEBUG
  439. kprintf("ext2fs: Enumerating directory contents of inode %u:\n", inode.index());
  440. #endif
  441. auto buffer = readEntireInode(inode);
  442. ASSERT(buffer);
  443. auto* entry = reinterpret_cast<ext2_dir_entry_2*>(buffer.pointer());
  444. while (entry < buffer.endPointer()) {
  445. if (entry->inode != 0) {
  446. #ifdef EXT2_DEBUG
  447. kprintf("inode: %u, name_len: %u, rec_len: %u, file_type: %u, name: %s\n", entry->inode, entry->name_len, entry->rec_len, entry->file_type, namebuf);
  448. #endif
  449. if (!callback({ entry->name, entry->name_len, { id(), entry->inode }, entry->file_type }))
  450. break;
  451. }
  452. entry = (ext2_dir_entry_2*)((char*)entry + entry->rec_len);
  453. }
  454. return true;
  455. }
  456. bool Ext2FS::addInodeToDirectory(unsigned directoryInode, unsigned inode, const String& name, byte fileType, int& error)
  457. {
  458. auto e2inodeForDirectory = lookupExt2Inode(directoryInode);
  459. ASSERT(e2inodeForDirectory);
  460. ASSERT(isDirectory(e2inodeForDirectory->i_mode));
  461. //#ifdef EXT2_DEBUG
  462. dbgprintf("Ext2FS: Adding inode %u with name '%s' to directory %u\n", inode, name.characters(), directoryInode);
  463. //#endif
  464. Vector<DirectoryEntry> entries;
  465. bool nameAlreadyExists = false;
  466. deprecated_enumerateDirectoryInode({ id(), directoryInode }, [&] (const DirectoryEntry& entry) {
  467. if (!strcmp(entry.name, name.characters())) {
  468. nameAlreadyExists = true;
  469. return false;
  470. }
  471. entries.append(entry);
  472. return true;
  473. });
  474. if (nameAlreadyExists) {
  475. kprintf("Ext2FS: Name '%s' already exists in directory inode %u\n", name.characters(), directoryInode);
  476. error = -EEXIST;
  477. return false;
  478. }
  479. entries.append({ name.characters(), name.length(), { id(), inode }, fileType });
  480. return writeDirectoryInode(directoryInode, move(entries));
  481. }
  482. bool Ext2FS::writeDirectoryInode(unsigned directoryInode, Vector<DirectoryEntry>&& entries)
  483. {
  484. dbgprintf("Ext2FS: New directory inode %u contents to write:\n", directoryInode);
  485. unsigned directorySize = 0;
  486. for (auto& entry : entries) {
  487. //kprintf(" - %08u %s\n", entry.inode.index(), entry.name);
  488. directorySize += EXT2_DIR_REC_LEN(entry.name_length);
  489. }
  490. unsigned blocksNeeded = ceilDiv(directorySize, blockSize());
  491. unsigned occupiedSize = blocksNeeded * blockSize();
  492. dbgprintf("Ext2FS: directory size: %u (occupied: %u)\n", directorySize, occupiedSize);
  493. auto directoryData = ByteBuffer::createUninitialized(occupiedSize);
  494. BufferStream stream(directoryData);
  495. for (unsigned i = 0; i < entries.size(); ++i) {
  496. auto& entry = entries[i];
  497. unsigned recordLength = EXT2_DIR_REC_LEN(entry.name_length);
  498. if (i == entries.size() - 1)
  499. recordLength += occupiedSize - directorySize;
  500. dbgprintf("* inode: %u", entry.inode.index());
  501. dbgprintf(", name_len: %u", word(entry.name_length));
  502. dbgprintf(", rec_len: %u", word(recordLength));
  503. dbgprintf(", file_type: %u", byte(entry.fileType));
  504. dbgprintf(", name: %s\n", entry.name);
  505. stream << dword(entry.inode.index());
  506. stream << word(recordLength);
  507. stream << byte(entry.name_length);
  508. stream << byte(entry.fileType);
  509. stream << entry.name;
  510. unsigned padding = recordLength - entry.name_length - 8;
  511. //dbgprintf(" *** pad %u bytes\n", padding);
  512. for (unsigned j = 0; j < padding; ++j) {
  513. stream << byte(0);
  514. }
  515. }
  516. stream.fillToEnd(0);
  517. #if 0
  518. kprintf("data to write (%u):\n", directoryData.size());
  519. for (unsigned i = 0; i < directoryData.size(); ++i) {
  520. kprintf("%02x ", directoryData[i]);
  521. if ((i + 1) % 8 == 0)
  522. kprintf(" ");
  523. if ((i + 1) % 16 == 0)
  524. kprintf("\n");
  525. }
  526. kprintf("\n");
  527. #endif
  528. writeInode({ id(), directoryInode }, directoryData);
  529. return true;
  530. }
  531. unsigned Ext2FS::inodesPerBlock() const
  532. {
  533. return EXT2_INODES_PER_BLOCK(&superBlock());
  534. }
  535. unsigned Ext2FS::inodesPerGroup() const
  536. {
  537. return EXT2_INODES_PER_GROUP(&superBlock());
  538. }
  539. unsigned Ext2FS::inodeSize() const
  540. {
  541. return EXT2_INODE_SIZE(&superBlock());
  542. }
  543. unsigned Ext2FS::blocksPerGroup() const
  544. {
  545. return EXT2_BLOCKS_PER_GROUP(&superBlock());
  546. }
  547. void Ext2FS::dumpBlockBitmap(unsigned groupIndex) const
  548. {
  549. ASSERT(groupIndex <= m_blockGroupCount);
  550. auto& bgd = blockGroupDescriptor(groupIndex);
  551. unsigned blocksInGroup = min(blocksPerGroup(), superBlock().s_blocks_count);
  552. unsigned blockCount = ceilDiv(blocksInGroup, 8u);
  553. auto bitmapBlocks = readBlocks(bgd.bg_block_bitmap, blockCount);
  554. ASSERT(bitmapBlocks);
  555. kprintf("ext2fs: group[%u] block bitmap (bitmap occupies %u blocks):\n", groupIndex, blockCount);
  556. auto bitmap = Bitmap::wrap(bitmapBlocks.pointer(), blocksInGroup);
  557. for (unsigned i = 0; i < blocksInGroup; ++i) {
  558. kprintf("%c", bitmap.get(i) ? '1' : '0');
  559. }
  560. kprintf("\n");
  561. }
  562. void Ext2FS::dumpInodeBitmap(unsigned groupIndex) const
  563. {
  564. traverseInodeBitmap(groupIndex, [] (unsigned, const Bitmap& bitmap) {
  565. for (unsigned i = 0; i < bitmap.size(); ++i)
  566. kprintf("%c", bitmap.get(i) ? '1' : '0');
  567. return true;
  568. });
  569. }
  570. template<typename F>
  571. void Ext2FS::traverseInodeBitmap(unsigned groupIndex, F callback) const
  572. {
  573. ASSERT(groupIndex <= m_blockGroupCount);
  574. auto& bgd = blockGroupDescriptor(groupIndex);
  575. unsigned inodesInGroup = min(inodesPerGroup(), superBlock().s_inodes_count);
  576. unsigned blockCount = ceilDiv(inodesInGroup, 8u);
  577. for (unsigned i = 0; i < blockCount; ++i) {
  578. auto block = readBlock(bgd.bg_inode_bitmap + i);
  579. ASSERT(block);
  580. bool shouldContinue = callback(i * (blockSize() / 8) + 1, Bitmap::wrap(block.pointer(), inodesInGroup));
  581. if (!shouldContinue)
  582. break;
  583. }
  584. }
  585. template<typename F>
  586. void Ext2FS::traverseBlockBitmap(unsigned groupIndex, F callback) const
  587. {
  588. ASSERT(groupIndex <= m_blockGroupCount);
  589. auto& bgd = blockGroupDescriptor(groupIndex);
  590. unsigned blocksInGroup = min(blocksPerGroup(), superBlock().s_blocks_count);
  591. unsigned blockCount = ceilDiv(blocksInGroup, 8u);
  592. for (unsigned i = 0; i < blockCount; ++i) {
  593. auto block = readBlock(bgd.bg_block_bitmap + i);
  594. ASSERT(block);
  595. bool shouldContinue = callback(i * (blockSize() / 8) + 1, Bitmap::wrap(block.pointer(), blocksInGroup));
  596. if (!shouldContinue)
  597. break;
  598. }
  599. }
  600. bool Ext2FS::modifyLinkCount(InodeIndex inode, int delta)
  601. {
  602. ASSERT(inode);
  603. auto e2inode = lookupExt2Inode(inode);
  604. if (!e2inode)
  605. return false;
  606. auto newLinkCount = e2inode->i_links_count + delta;
  607. dbgprintf("Ext2FS: changing inode %u link count from %u to %u\n", inode, e2inode->i_links_count, newLinkCount);
  608. e2inode->i_links_count = newLinkCount;
  609. return writeExt2Inode(inode, *e2inode);
  610. }
  611. bool Ext2FS::set_mtime(InodeIdentifier inode, dword timestamp)
  612. {
  613. ASSERT(inode.fsid() == id());
  614. auto e2inode = lookupExt2Inode(inode.index());
  615. if (!e2inode)
  616. return false;
  617. kprintf("changing inode %u mtime from %u to %u\n", inode.index(), e2inode->i_mtime, timestamp);
  618. e2inode->i_mtime = timestamp;
  619. return writeExt2Inode(inode.index(), *e2inode);
  620. }
  621. bool Ext2FS::writeExt2Inode(unsigned inode, const ext2_inode& e2inode)
  622. {
  623. unsigned blockIndex;
  624. unsigned offset;
  625. auto block = readBlockContainingInode(inode, blockIndex, offset);
  626. if (!block)
  627. return false;
  628. {
  629. LOCKER(m_inode_cache_lock);
  630. auto it = m_inode_cache.find(inode);
  631. if (it != m_inode_cache.end()) {
  632. auto& cached_inode = *(*it).value;
  633. LOCKER(cached_inode.m_lock);
  634. cached_inode.m_raw_inode = e2inode;
  635. cached_inode.populate_metadata();
  636. if (cached_inode.is_directory())
  637. cached_inode.m_lookup_cache.clear();
  638. }
  639. }
  640. memcpy(reinterpret_cast<ext2_inode*>(block.offsetPointer(offset)), &e2inode, inodeSize());
  641. writeBlock(blockIndex, block);
  642. return true;
  643. }
  644. bool Ext2FS::isDirectoryInode(unsigned inode) const
  645. {
  646. if (auto e2inode = lookupExt2Inode(inode))
  647. return isDirectory(e2inode->i_mode);
  648. return false;
  649. }
  650. Vector<Ext2FS::BlockIndex> Ext2FS::allocateBlocks(unsigned group, unsigned count)
  651. {
  652. dbgprintf("Ext2FS: allocateBlocks(group: %u, count: %u)\n", group, count);
  653. auto& bgd = blockGroupDescriptor(group);
  654. if (bgd.bg_free_blocks_count < count) {
  655. kprintf("ExtFS: allocateBlocks can't allocate out of group %u, wanted %u but only %u available\n", group, count, bgd.bg_free_blocks_count);
  656. return { };
  657. }
  658. // FIXME: Implement a scan that finds consecutive blocks if possible.
  659. Vector<BlockIndex> blocks;
  660. traverseBlockBitmap(group, [&blocks, count] (unsigned firstBlockInBitmap, const Bitmap& bitmap) {
  661. for (unsigned i = 0; i < bitmap.size(); ++i) {
  662. if (!bitmap.get(i)) {
  663. blocks.append(firstBlockInBitmap + i);
  664. if (blocks.size() == count)
  665. return false;
  666. }
  667. }
  668. return true;
  669. });
  670. dbgprintf("Ext2FS: allocateBlock found these blocks:\n");
  671. for (auto& bi : blocks) {
  672. dbgprintf(" > %u\n", bi);
  673. }
  674. return blocks;
  675. }
  676. unsigned Ext2FS::allocateInode(unsigned preferredGroup, unsigned expectedSize)
  677. {
  678. dbgprintf("Ext2FS: allocateInode(preferredGroup: %u, expectedSize: %u)\n", preferredGroup, expectedSize);
  679. unsigned neededBlocks = ceilDiv(expectedSize, blockSize());
  680. dbgprintf("Ext2FS: minimum needed blocks: %u\n", neededBlocks);
  681. unsigned groupIndex = 0;
  682. auto isSuitableGroup = [this, neededBlocks] (unsigned groupIndex) {
  683. auto& bgd = blockGroupDescriptor(groupIndex);
  684. return bgd.bg_free_inodes_count && bgd.bg_free_blocks_count >= neededBlocks;
  685. };
  686. if (preferredGroup && isSuitableGroup(preferredGroup)) {
  687. groupIndex = preferredGroup;
  688. } else {
  689. for (unsigned i = 1; i <= m_blockGroupCount; ++i) {
  690. if (isSuitableGroup(i))
  691. groupIndex = i;
  692. }
  693. }
  694. if (!groupIndex) {
  695. kprintf("Ext2FS: allocateInode: no suitable group found for new inode with %u blocks needed :(\n", neededBlocks);
  696. return 0;
  697. }
  698. dbgprintf("Ext2FS: allocateInode: found suitable group [%u] for new inode with %u blocks needed :^)\n", groupIndex, neededBlocks);
  699. unsigned firstFreeInodeInGroup = 0;
  700. traverseInodeBitmap(groupIndex, [&firstFreeInodeInGroup] (unsigned firstInodeInBitmap, const Bitmap& bitmap) {
  701. for (unsigned i = 0; i < bitmap.size(); ++i) {
  702. if (!bitmap.get(i)) {
  703. firstFreeInodeInGroup = firstInodeInBitmap + i;
  704. return false;
  705. }
  706. }
  707. return true;
  708. });
  709. if (!firstFreeInodeInGroup) {
  710. kprintf("Ext2FS: firstFreeInodeInGroup returned no inode, despite bgd claiming there are inodes :(\n");
  711. return 0;
  712. }
  713. unsigned inode = firstFreeInodeInGroup;
  714. dbgprintf("Ext2FS: found suitable inode %u\n", inode);
  715. // FIXME: allocate blocks if needed!
  716. return inode;
  717. }
  718. unsigned Ext2FS::groupIndexFromInode(unsigned inode) const
  719. {
  720. if (!inode)
  721. return 0;
  722. return (inode - 1) / inodesPerGroup() + 1;
  723. }
  724. bool Ext2FS::setInodeAllocationState(unsigned inode, bool newState)
  725. {
  726. auto& bgd = blockGroupDescriptor(groupIndexFromInode(inode));
  727. // Update inode bitmap
  728. unsigned inodesPerBitmapBlock = blockSize() * 8;
  729. unsigned bitmapBlockIndex = (inode - 1) / inodesPerBitmapBlock;
  730. unsigned bitIndex = (inode - 1) % inodesPerBitmapBlock;
  731. auto block = readBlock(bgd.bg_inode_bitmap + bitmapBlockIndex);
  732. ASSERT(block);
  733. auto bitmap = Bitmap::wrap(block.pointer(), block.size());
  734. bool currentState = bitmap.get(bitIndex);
  735. dbgprintf("ext2fs: setInodeAllocationState(%u) %u -> %u\n", inode, currentState, newState);
  736. if (currentState == newState)
  737. return true;
  738. bitmap.set(bitIndex, newState);
  739. writeBlock(bgd.bg_inode_bitmap + bitmapBlockIndex, block);
  740. // Update superblock
  741. auto& sb = *reinterpret_cast<ext2_super_block*>(m_cachedSuperBlock.pointer());
  742. dbgprintf("Ext2FS: superblock free inode count %u -> %u\n", sb.s_free_inodes_count, sb.s_free_inodes_count - 1);
  743. if (newState)
  744. --sb.s_free_inodes_count;
  745. else
  746. ++sb.s_free_inodes_count;
  747. writeSuperBlock(sb);
  748. // Update BGD
  749. auto& mutableBGD = const_cast<ext2_group_desc&>(bgd);
  750. if (newState)
  751. --mutableBGD.bg_free_inodes_count;
  752. else
  753. ++mutableBGD.bg_free_inodes_count;
  754. dbgprintf("Ext2FS: group free inode count %u -> %u\n", bgd.bg_free_inodes_count, bgd.bg_free_inodes_count - 1);
  755. unsigned blocksToWrite = ceilDiv(m_blockGroupCount * (unsigned)sizeof(ext2_group_desc), blockSize());
  756. unsigned firstBlockOfBGDT = blockSize() == 1024 ? 2 : 1;
  757. writeBlocks(firstBlockOfBGDT, blocksToWrite, m_cachedBlockGroupDescriptorTable);
  758. return true;
  759. }
  760. bool Ext2FS::setBlockAllocationState(GroupIndex group, BlockIndex bi, bool newState)
  761. {
  762. auto& bgd = blockGroupDescriptor(group);
  763. // Update block bitmap
  764. unsigned blocksPerBitmapBlock = blockSize() * 8;
  765. unsigned bitmapBlockIndex = (bi - 1) / blocksPerBitmapBlock;
  766. unsigned bitIndex = (bi - 1) % blocksPerBitmapBlock;
  767. auto block = readBlock(bgd.bg_block_bitmap + bitmapBlockIndex);
  768. ASSERT(block);
  769. auto bitmap = Bitmap::wrap(block.pointer(), block.size());
  770. bool currentState = bitmap.get(bitIndex);
  771. dbgprintf("Ext2FS: setBlockAllocationState(%u) %u -> %u\n", bi, currentState, newState);
  772. if (currentState == newState)
  773. return true;
  774. bitmap.set(bitIndex, newState);
  775. writeBlock(bgd.bg_block_bitmap + bitmapBlockIndex, block);
  776. // Update superblock
  777. auto& sb = *reinterpret_cast<ext2_super_block*>(m_cachedSuperBlock.pointer());
  778. dbgprintf("Ext2FS: superblock free block count %u -> %u\n", sb.s_free_blocks_count, sb.s_free_blocks_count - 1);
  779. if (newState)
  780. --sb.s_free_blocks_count;
  781. else
  782. ++sb.s_free_blocks_count;
  783. writeSuperBlock(sb);
  784. // Update BGD
  785. auto& mutableBGD = const_cast<ext2_group_desc&>(bgd);
  786. if (newState)
  787. --mutableBGD.bg_free_blocks_count;
  788. else
  789. ++mutableBGD.bg_free_blocks_count;
  790. dbgprintf("Ext2FS: group free block count %u -> %u\n", bgd.bg_free_blocks_count, bgd.bg_free_blocks_count - 1);
  791. unsigned blocksToWrite = ceilDiv(m_blockGroupCount * (unsigned)sizeof(ext2_group_desc), blockSize());
  792. unsigned firstBlockOfBGDT = blockSize() == 1024 ? 2 : 1;
  793. writeBlocks(firstBlockOfBGDT, blocksToWrite, m_cachedBlockGroupDescriptorTable);
  794. return true;
  795. }
  796. InodeIdentifier Ext2FS::create_directory(InodeIdentifier parentInode, const String& name, Unix::mode_t mode, int& error)
  797. {
  798. ASSERT(parentInode.fsid() == id());
  799. ASSERT(isDirectoryInode(parentInode.index()));
  800. // Fix up the mode to definitely be a directory.
  801. // FIXME: This is a bit on the hackish side.
  802. mode &= ~0170000;
  803. mode |= 0040000;
  804. // NOTE: When creating a new directory, make the size 1 block.
  805. // There's probably a better strategy here, but this works for now.
  806. auto inode = create_inode(parentInode, name, mode, blockSize(), error);
  807. if (!inode.isValid())
  808. return { };
  809. dbgprintf("Ext2FS: create_directory: created new directory named '%s' with inode %u\n", name.characters(), inode.index());
  810. Vector<DirectoryEntry> entries;
  811. entries.append({ ".", inode, EXT2_FT_DIR });
  812. entries.append({ "..", parentInode, EXT2_FT_DIR });
  813. bool success = writeDirectoryInode(inode.index(), move(entries));
  814. ASSERT(success);
  815. success = modifyLinkCount(parentInode.index(), 1);
  816. ASSERT(success);
  817. auto& bgd = const_cast<ext2_group_desc&>(blockGroupDescriptor(groupIndexFromInode(inode.index())));
  818. ++bgd.bg_used_dirs_count;
  819. dbgprintf("Ext2FS: incremented bg_used_dirs_count %u -> %u\n", bgd.bg_used_dirs_count - 1, bgd.bg_used_dirs_count);
  820. unsigned blocksToWrite = ceilDiv(m_blockGroupCount * (unsigned)sizeof(ext2_group_desc), blockSize());
  821. unsigned firstBlockOfBGDT = blockSize() == 1024 ? 2 : 1;
  822. writeBlocks(firstBlockOfBGDT, blocksToWrite, m_cachedBlockGroupDescriptorTable);
  823. error = 0;
  824. return inode;
  825. }
  826. InodeIdentifier Ext2FS::create_inode(InodeIdentifier parentInode, const String& name, Unix::mode_t mode, unsigned size, int& error)
  827. {
  828. ASSERT(parentInode.fsid() == id());
  829. ASSERT(isDirectoryInode(parentInode.index()));
  830. dbgprintf("Ext2FS: Adding inode '%s' (mode %u) to parent directory %u:\n", name.characters(), mode, parentInode.index());
  831. // NOTE: This doesn't commit the inode allocation just yet!
  832. auto inode = allocateInode(0, 0);
  833. if (!inode) {
  834. kprintf("Ext2FS: createInode: allocateInode failed\n");
  835. error = -ENOSPC;
  836. return { };
  837. }
  838. auto blocks = allocateBlocks(groupIndexFromInode(inode), ceilDiv(size, blockSize()));
  839. if (blocks.isEmpty()) {
  840. kprintf("Ext2FS: createInode: allocateBlocks failed\n");
  841. error = -ENOSPC;
  842. return { };
  843. }
  844. byte fileType = 0;
  845. if (isRegularFile(mode))
  846. fileType = EXT2_FT_REG_FILE;
  847. else if (isDirectory(mode))
  848. fileType = EXT2_FT_DIR;
  849. else if (isCharacterDevice(mode))
  850. fileType = EXT2_FT_CHRDEV;
  851. else if (isBlockDevice(mode))
  852. fileType = EXT2_FT_BLKDEV;
  853. else if (isFIFO(mode))
  854. fileType = EXT2_FT_FIFO;
  855. else if (isSocket(mode))
  856. fileType = EXT2_FT_SOCK;
  857. else if (isSymbolicLink(mode))
  858. fileType = EXT2_FT_SYMLINK;
  859. // Try adding it to the directory first, in case the name is already in use.
  860. bool success = addInodeToDirectory(parentInode.index(), inode, name, fileType, error);
  861. if (!success)
  862. return { };
  863. // Looks like we're good, time to update the inode bitmap and group+global inode counters.
  864. success = setInodeAllocationState(inode, true);
  865. ASSERT(success);
  866. for (auto bi : blocks) {
  867. success = setBlockAllocationState(groupIndexFromInode(inode), bi, true);
  868. ASSERT(success);
  869. }
  870. unsigned initialLinksCount;
  871. if (isDirectory(mode))
  872. initialLinksCount = 2; // (parent directory + "." entry in self)
  873. else
  874. initialLinksCount = 1;
  875. auto timestamp = ktime(nullptr);
  876. auto e2inode = make<ext2_inode>();
  877. memset(e2inode.ptr(), 0, sizeof(ext2_inode));
  878. e2inode->i_mode = mode;
  879. e2inode->i_uid = 0;
  880. e2inode->i_size = size;
  881. e2inode->i_atime = timestamp;
  882. e2inode->i_ctime = timestamp;
  883. e2inode->i_mtime = timestamp;
  884. e2inode->i_dtime = 0;
  885. e2inode->i_gid = 0;
  886. e2inode->i_links_count = initialLinksCount;
  887. e2inode->i_blocks = blocks.size() * (blockSize() / 512);
  888. // FIXME: Implement writing out indirect blocks!
  889. ASSERT(blocks.size() < EXT2_NDIR_BLOCKS);
  890. dbgprintf("Ext2FS: writing %zu blocks to i_block array\n", min((size_t)EXT2_NDIR_BLOCKS, blocks.size()));
  891. for (unsigned i = 0; i < min((size_t)EXT2_NDIR_BLOCKS, blocks.size()); ++i) {
  892. e2inode->i_block[i] = blocks[i];
  893. }
  894. e2inode->i_flags = 0;
  895. success = writeExt2Inode(inode, *e2inode);
  896. ASSERT(success);
  897. return { id(), inode };
  898. }
  899. InodeIdentifier Ext2FS::find_parent_of_inode(InodeIdentifier inode_id) const
  900. {
  901. auto inode = get_inode(inode_id);
  902. ASSERT(inode);
  903. unsigned groupIndex = groupIndexFromInode(inode->index());
  904. unsigned firstInodeInGroup = inodesPerGroup() * (groupIndex - 1);
  905. Vector<RetainPtr<Ext2FSInode>> directories_in_group;
  906. for (unsigned i = 0; i < inodesPerGroup(); ++i) {
  907. auto group_member = get_inode({ id(), firstInodeInGroup + i });
  908. if (!group_member)
  909. continue;
  910. if (group_member->is_directory())
  911. directories_in_group.append(move(group_member));
  912. }
  913. InodeIdentifier foundParent;
  914. for (auto& directory : directories_in_group) {
  915. if (!directory->reverse_lookup(inode->identifier()).isNull()) {
  916. foundParent = directory->identifier();
  917. break;
  918. }
  919. }
  920. return foundParent;
  921. }
  922. void Ext2FSInode::populate_lookup_cache()
  923. {
  924. {
  925. LOCKER(m_lock);
  926. if (!m_lookup_cache.isEmpty())
  927. return;
  928. }
  929. HashMap<String, unsigned> children;
  930. traverse_as_directory([&children] (auto& entry) {
  931. children.set(String(entry.name, entry.name_length), entry.inode.index());
  932. return true;
  933. });
  934. LOCKER(m_lock);
  935. if (!m_lookup_cache.isEmpty())
  936. return;
  937. m_lookup_cache = move(children);
  938. }
  939. InodeIdentifier Ext2FSInode::lookup(const String& name)
  940. {
  941. ASSERT(is_directory());
  942. populate_lookup_cache();
  943. LOCKER(m_lock);
  944. auto it = m_lookup_cache.find(name);
  945. if (it != m_lookup_cache.end())
  946. return { fsid(), (*it).value };
  947. return { };
  948. }
  949. String Ext2FSInode::reverse_lookup(InodeIdentifier child_id)
  950. {
  951. ASSERT(is_directory());
  952. ASSERT(child_id.fsid() == fsid());
  953. populate_lookup_cache();
  954. LOCKER(m_lock);
  955. for (auto it : m_lookup_cache) {
  956. if (it.value == child_id.index())
  957. return it.key;
  958. }
  959. return { };
  960. }