Is this EXT2 parsing implementation correct?


Recommended Posts

I need to write a small application that checks whether a file exists on an EXT2/3 partition. I looked for some simple directory parsing implementation and came across this one from from https://github.com/TheCodeArtist/ext2-parser/blob/master/ext-shell.c:

void ls(int fd, int base_inode_num)
{
char* name;
int curr_inode_num;
int curr_inode_type;
 
debug("data block addr\t= 0x%x\n", inodes[base_inode_num-1].i_block[0]);
 
struct os_direntry_t* dirEntry = malloc(sizeof(struct os_direntry_t));
assert (dirEntry != NULL);
assert(lseek(fd, (off_t)(inodes[base_inode_num-1].i_block[0]*1024), SEEK_SET) == (off_t)(inodes[base_inode_num-1].i_block[0]*1024));
assert(read(fd, (void *)dirEntry, sizeof(struct os_direntry_t)) == sizeof(struct os_direntry_t));
 
while (dirEntry->inode) {
 
name = (char*)malloc(dirEntry->name_len+1);
memcpy(name, dirEntry->file_name, dirEntry->name_len);
name[dirEntry->name_len+1] = '\0';
 
curr_inode_num = dirEntry->inode;
curr_inode_type = dirEntry->file_type;
 
lseek(fd, (dirEntry->rec_len - sizeof(struct os_direntry_t)), SEEK_CUR);
assert(read(fd, (void *)dirEntry, sizeof(struct os_direntry_t)) == sizeof(struct os_direntry_t));
 
if (name[0] == '.') {
if ( name[1]=='.' || name[1]=='\0')
continue;
} else {
debug("rec_len\t\t= %d\n", dirEntry->rec_len);
debug("dirEntry->inode\t= %d\n",dirEntry->inode);
printInodeType(curr_inode_type);
printInodePerm(fd, curr_inode_num);
printf("%d\t", curr_inode_num);
printf("%s\t", name);
printf("\n");
}
}
 
return;
}

It seems to start reading the first directory inode data block and keeps reading all the directory entry structures however I don't understand how is this supposed to work if the directory contains more entries that can be stored in a single inode data block. Is this implementation incomplete/wrong, am I reading it incorrectly or is there some EXT2/3 behavior I'm not aware of? Shouldn't the function read the directory inode data blocks before starting to read the entries?

Why are you trying to read the filesystem metadata directly? It seems potentially problematic and unnecessarily complicated. You can check whether a file exists on any filesystem Linux understands - whether that be EXT2, EXT3, EXT4, XFS, BTRFS, UDF, HFS, HFS+, UFS, FAT32, or NTFS - with a few simple commands. For example:

$ sudo mount -o ro /dev/sdb1 /mnt
$ find /mnt -name '*somefile.txt'
$ sudo umount /mnt
 

If your goal is to search the contents of a read-only image file like the project you linked to seems to suggest, you can also do that fairly simply using existing utilities. For example:

$ sudo kpartx -av some_hard_disk_image.img
$ sudo mount -o ro /dev/mapper/loop0p1 /mnt
$ find /mnt -name '*somefile.txt'
$ sudo umount /mnt
$ sudo kpartx -d some_hard_disk_image.img
  On 23/09/2013 at 20:00, xorangekiller said:

Why are you trying to read the filesystem metadata directly? It seems potentially problematic and unnecessarily complicated. You can check whether a file exists on any filesystem Linux understands - whether that be EXT2, EXT3, EXT4, XFS, BTRFS, UDF, HFS, HFS+, UFS, FAT32, or NTFS - with a few simple commands. For example:

I don't see what is complicated. I did the same for NTFS and FAT32 without any problem, it was actually pretty easier since they aren't splitted up in all those annoying regions. While EXT2/3 are documented as well the documentation is quite bad since it doesn't cover the common implementations behaviors. In the end I just followed how it was implemented in the kernel sources, certainly having being able to read directories in sequence without having to read the data as a file first would have helped a lot. Having to ask users to install cygwin or other pieces of garbage for a minor function, now that would have been complicated. With ~200 lines of code (ignoring the structures) I solved the problem without any other annoying library or additional software.

So if I understand you proprerly, you were trying to read data from an EXT2 partition on Windows? In that case even installing Cygwin like you suggest would not have helped. Although I now understand why you couldn't use the sequence of basic commands I posted above, I stand by my assertion that you are going about this the wrong way. It sounds like Windows is not the right tool for the job.

 

That said, I would love to see your source code if you have it working. I'm assuming it is GPLv2 licensed since you took code from the kernel, of course.

  On 27/09/2013 at 00:24, xorangekiller said:

So if I understand you proprerly, you were trying to read data from an EXT2 partition on Windows?

On Linux there are several libraries available for that making the whole ordeal quite pointless.

 

  On 27/09/2013 at 00:24, xorangekiller said:

In that case even installing Cygwin like you suggest would not have helped.

Yes it would because those same libraries can be compiled and used there. But requiring something as horrible as Cygwin to be installed on user machines just to save a few hundred lines of code didn't really seem a good idea.

 

  On 27/09/2013 at 00:24, xorangekiller said:

Although I now understand why you couldn't use the sequence of basic commands I posted above, I stand by my assertion that you are going about this the wrong way. It sounds like Windows is not the right tool for the job.

I don't think that requiring users to reboot back to linux every time they want to find a file is a solution either.

 

  On 27/09/2013 at 00:24, xorangekiller said:

Although I now understand why you couldn't use the sequence of basic commands I posted above, I stand by my assertion that you are going about this the wrong way. It sounds like Windows is not the right tool for the job.

Following an implementation doesn't mean copying any line of code, code that would have been entirely useless anyway since that's a driver code, and drivers are made for asynchronous access therefore full of additional abstractions, thread synchronization and memory paging. Following the implementation meant simply looking which fields of the filesystem structures the EXT2 driver was looking for doing those basic calculations for finding out which data to read next. I found some noticeable differences between how the ext2 driver handles reading the directories compared to that code example I linked above and also to the many confused and incomplete specifications available.

 

I don't want to post the code since it relies on a lot additional code to perform the disk reads and other application tasks but I can describe the steps required to obtain the same, in case anybody with the same problem would ever stumble into this thread:

  1. Read the SuperBlock that is always 1024 bytes after the beginning of the partition
  2. Calculate the block size by shifting the base block size on the left by the logarithmic block size value in the superblock (a simple 1024 << LOGBLOCKVALUE)
  3. Calculate the logical superblock block number by dividing the SuperBlock offset by the block size
  4. Calculate the number of Block Groups by dividing the SuperBlock inodes count value by the SuperBlock inodes per group value
  5. Read all the blocks group descriptors into an array (they're stored sequentially). The position of the first descriptor is at BLOCKSIZE*(SUPERBLOCK_BLOCKNUMBER + 1).
  6. Read the root directory inode (always 2). In order to do that it's required to know which group of inodes the inode belongs to (inodes are compacted in several groups, one for each blocks group), the position of the inodes table, and the position of that inode within the inodes group. The group number is a simple (INODENUMBER-1) (inodes are non-positional and 0 is reserved so in the calculations you always have to subtract 1) divided by the INODES_PER_GROUP value of the Superblock. Then to find the inodes block table position you read the INODES_TABLE_BLOCK_NUMBER of the matching group from the blocks group descriptors array read before and multiply it by the block size. Then to find the byte offset of the inode within that inode table you first find the logical inode number in the table by doing a module division of the (INODENUMBER-1) by the superblock INODES_PER_GROUP value. Then you multiply that value by the INODE_STRUCTURE_SIZE value of the superblock finding out the byte offset inside the table you need to read at.
  7. Then you need a function to read directory or files, reading both is actually exactly the same. Every inode has a BLOCKS array containing 15 block numbers, the first 12 items are direct block values, the 13th item is a block number of a block that is entirely used for storing additional block values, the 14th and 15th block numbers are the same but with twice and thrice the indirection. There's a value in the inode (BLOCKSCOUNT) that tells exactly how many blocks there are to read. Blocks numbers equal to zero are non-allocated blocks (used in sparse files).
  8. Once obtained the directory data you start reading all the directory structures one by one, moving by the record length value. The file name is adjacent to the structure and the file type is stored in the directory itself. The list should end when the record length is 0. If a directory structure contains an inode with the value 0 it means the item has been deleted (explaining how recovering files on EXT2 was quite the nightmare, you no longer know where it is and there's no other name associated to it).

The longest part is reading the blocks values but I think the whole implementation can be done with 100 lines or less on an unmanaged language especially if you don't care about reading the whole structures.

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • BBC threatens Perplexity with legal action over content scraping by Paul Hill Image via Depositphotos.com The UK’s public broadcaster, BBC, has written a letter to Perplexity, the AI search startup, asking it to stop scraping articles from its websites, delete existing copies of content, and propose some sort of financial compensation if it would like to carry on scraping data. If the demands are not met, BBC may seek an injunction against the startup citing alleged misuse of its intellectual property. BBC is probably responding in this way because it has seen other news organizations cement deals with firms like OpenAI and Mistral. The income stream allows news organizations to raise more funds and also cover the costs of the extra load on their servers caused by AI scraping. For anybody not familiar with Perplexity, it’s a bit like ChatGPT but has a much stronger emphasis on searching the web to find information. You can ask it anything you want to know about and it very quickly searches online and constructs a specific response to your question based on what it has found. The company offers many of its features for free, but does have Perplexity Pro, which costs money. Essentially, Perplexity is making money from publishers by using their content to improve its own product, but not paying them all. Perplexity's defense and existing publisher programs In a statement to the Financial Times, Perplexity labeled the BBC’s claims as "manipulative and opportunistic". The startup accused the broadcaster of having “a fundamental misunderstanding of technology, the internet and intellectual property law.” This is not the first time Perplexity has had a run-in with the media. Forbes and Wired accused it of plagiarizing content from their websites and The New York Times sent the company a cease and desist notice to stop using its content for AI purposes. To assuage publishers, Perplexity has set up a revenue sharing program, which includes TIME, Fortune, Der Spiegel, and others. According to Digiday, the revenue share was up to 25%. It’s not clear if BBC has tried engaging through this avenue or if it wants to try to squeeze the startup for a bigger slice. The escalating battle over AI and intellectual property Even if you only keep up with AI developments in passing, you’ll likely have seen that AI models need to be trained on vast amounts of data, much of which is copyrighted. There is an ongoing debate about whether these companies should be allowed to train on this data, or first seek out permission from the copyright holders. The move from the BBC could spur other publishers on to try and get themselves a better deal from Perplexity. Alternatively, Perplexity could remove BBC content from its platform and stop pulling information from there. It could probably find most of the information elsewhere, but if Perplexity tried to pull this too much it would eventually end up pretty useless with not a lot of content. Overall, this is just one of many ongoing legal issues surrounding AI, but once a conclusion has been reached, it could set a precedent about how AI companies should go about getting content from publishers. Source: FT via Reuters
    • No, it's in fact not always there. You have to enable the FPS overlay first, either in Steam general settings or in the.... Steam Overlay... which is Shift+Tab. And what is that? A keyboard shortcut
    • Mangohud hasn't been built into anything but the Steam Deck until now, you had to set it up yourself.
    • M$ Start Menu and its Oddities: What Do They Know? Do They Know Things?? Let's Find Out! Short answer is "you actually want Open-Shell or any of its paid alternatives".
    • Windoze 11 delivering whatever drivers to me in a recent laptop (2024) made me disable the ability to receive drivers altoghether. I was repeatedly losing the ability to have a lighted keyboard, because I'd install the most recent driver from the manufacturer, and Windoze would immediately "replace it" or "complement it" with a whatever "Component download" of its own. Wasted me a couple of days troubleshooting that crap. Windoze 11 wasting my time since like forever.
  • Recent Achievements

    • One Month Later
      KynanSEIT earned a badge
      One Month Later
    • One Month Later
      gowtham07 earned a badge
      One Month Later
    • Collaborator
      lethalman went up a rank
      Collaborator
    • Week One Done
      Wayne Robinson earned a badge
      Week One Done
    • One Month Later
      Karan Khanna earned a badge
      One Month Later
  • Popular Contributors

    1. 1
      +primortal
      679
    2. 2
      ATLien_0
      274
    3. 3
      Michael Scrip
      220
    4. 4
      +FloatingFatMan
      171
    5. 5
      Steven P.
      160
  • Tell a friend

    Love Neowin? Tell a friend!