3

As far as I know, once an inode of a file is found, finding the data is trivial - done by accessing a specific location on the disk, which is stored in the inode.

The question however is how exactly are the inodes found, when the system is given a filepath?

The purpose of my question is mainly the desire to grasp the way the b-trees are implemented in real life. I understand the general idea of it, I would like to know how exactly it is implemented in Unix filesystem (if at all), though.

Does each node of the tree store the inode number, with the leaves additionally storing the address on the disk of the inode itself? Or maybe the consecutive parts of the filepath?

Does the implementation vary depending on whether the disk is a hard drive or an SSD?

closed as too broad by Wildcard, GAD3R, Michael Homer, countermode, Anthon Jan 23 '17 at 7:51

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    What file system? – phk Jan 22 '17 at 11:12
  • @phk Answers relating any file systems are welcome. I'm generally interested in how are the searches optimised. – Dart Dega Jan 22 '17 at 11:14
  • 1
    Maybe this would fit better at Computer Science then. – phk Jan 22 '17 at 13:01
1

IMHO: You have two questions:

how exactly are the inodes found, when the system is given a filepath

and

desire to grasp the way the b-trees are implemented in real life.

Maybe your question is: how are inodes stored (in a b-tree), or the data an inode references. If so, I cannot answer that.

As far as your first - literal question goes, the answer, depening on OS ranges from not difficult to opaque. The classic system calls (open, unlink) will read the directory looking for the filename entry - and will start (in modern times - with a call to opendir()).

In classic UNIX - the maximum filename was 14 characters - that left 2 bytes for the inode (a directory entry was 16-bytes). There was not (and still not afaik) a b-tree organization of filenames and inodes - the search was (and is?) serial read of the directory. This falls in the category simple to examine.

Even on systems of today - where longer filenames are permitted - the basic look of the directory entries may be unchanged - 2bytes (inode), 14 bytes (initial filename/complete filename). (At least on AIX - where everything - even directories follows the UNIX adiom: everything is a file, some are special.)

michael@x071:[/home/michael]ls -lia /tmp | head
total 287464
    2 drwxrwxrwt 54 bin      bin       36864 Jan 22 13:35 .
    2 drwxr-xr-x 39 root     system     4096 Jan  5 12:27 ..
    5 drwxrwxrwt  2 root     system      256 May  8  2013 .X11-unix
    6 -rw-r-----  1 root     system        0 May 23  2014 .ahafs.out.michael.10223652
    7 -rw-r-----  1 root     system        0 May 23  2014 .ahafs.out.michael.9502870
    8 -r--r--r--  1 root     system       25 Jun  9  2013 .aix_ISMP_lock____.save
    9 drwxrwxrwt  3 root     system     4096 Dec 27 12:15 .com_ibm_tools_attach
   62 -rw-r--r--  1 root     system     3124 Dec 27 11:21 .ctinst.log
   63 -rw-r-----  1 michael  felt       2578 Aug 16  2013 .htaccess

michael@x071:[/home/michael]od -dc /tmp | head -20
0000000       2   11776       0       0       0       0       0       0
         \0 002   .  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
0000020       2   11822       0       0       0       0       0       0
         \0 002   .   .  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0  \0
0000040   32848   11895   28530   27492   26994   11825   13109   13878
        200   P   .   w   o   r   k   d   i   r   .   1   3   5   6   6
0000060       5   11864   12593   11637   28265   30720       0       0
         \0 005   .   X   1   1   -   u   n   i   x  \0  \0  \0  \0  \0
0000100       6   11873   26721   26227   11887   30068   11885   26979
         \0 006   .   a   h   a   f   s   .   o   u   t   .   m   i   c
0000120       7   11873   26721   26227   11887   30068   11885   26979
         \0  \a   .   a   h   a   f   s   .   o   u   t   .   m   i   c
0000140       8   11873   27000   24393   21325   20575   27759   25451
         \0  \b   .   a   i   x   _   I   S   M   P   _   l   o   c   k
0000160       9   11875   28525   24425   25197   24436   28527   27763
         \0  \t   .   c   o   m   _   i   b   m   _   t   o   o   l   s
0000200      62   11875   29801   28275   29742   27759   26368       0
         \0   >   .   c   t   i   n   s   t   .   l   o   g  \0  \0  \0
0000220      63   11880   29793   25443   25971   29440       0       0
         \0   ?   .   h   t   a   c   c   e   s   s  \0  \0  \0  \0  \0

Note: just tried above on a Linux system - and maybe these are now organized as a b-tree. No idea - because I get the following output:

michael@x067:~$ od -dc /tmp|head
od: /tmp: read error: Is a directory
0000000

So, classically: inode "lookup/mapping" to a (special) file were just the first two-bytes of a directory entry. Inodes were either on-disk, or stored in memory in, e.g., a b-tree.

In AIX - the 'dirent' struct is "easy to find" in as:

#define _D_NAME_MAX 255

struct  dirent {
        __ulong64_t     d_offset;       /* real off after this entry */
        ino_t           d_ino;          /* inode number of entry */
        ushort_t        d_reclen;       /* length of this record */
        ushort_t        d_namlen;       /* length of string in d_name */
        char            d_name[_D_NAME_MAX+1];  /* name must be no longer than this */
                                        /* redefine w/#define when name decided */
};

And on a Linux (3.2.X.Y kernel) - the include file includes and the structure is:

struct dirent
  {
#ifndef __USE_FILE_OFFSET64
    __ino_t d_ino;
    __off_t d_off;
#else
    __ino64_t d_ino;
    __off64_t d_off;
#endif
    unsigned short int d_reclen;
    unsigned char d_type;
    char d_name[256];           /* We must not include limits.h! */
  };

Both - imho - are basically, the same - the differences be neutralized by how they are returned via the call readdir()

Linux/GNU approach:

/usr/include/dirent.h:
/* This is the data type of directory stream objects.
   The actual structure is opaque to users.  */
typedef struct __dirstream DIR;

Note: I was unable to find anything for __dirstream - so I added the 'comment' about it being opaque

extern DIR *opendir (__const char *__name) __nonnull ((1));
...
/* Read a directory entry from DIRP.  Return a pointer to a `struct
   dirent' describing the entry, or NULL for EOF or error.  The
   storage returned may be overwritten by a later readdir call on the
   same DIR stream.

   If the Large File Support API is selected we have to use the
   appropriate interface.

   This function is a possible cancellation point and therefore not
   marked with __THROW.  */
#ifndef __USE_FILE_OFFSET64
extern struct dirent *readdir (DIR *__dirp) __nonnull ((1));
#else
# ifdef __REDIRECT
extern struct dirent *__REDIRECT (readdir, (DIR *__dirp), readdir64)
     __nonnull ((1));
# else
#  define readdir readdir64
# endif
#endif

#ifdef __USE_LARGEFILE64
extern struct dirent64 *readdir64 (DIR *__dirp) __nonnull ((1));
#endif

On AIX:

/*
 * Definitions for library routines operating on directories.
 */
typedef struct _dirdesc {
#ifdef _ALL_SOURCE
        int     dd_fd;          /* file descriptor of directory */
        blksize_t dd_blksize;   /* this filesystem's block size */
        char    *dd_buf;        /* malloc'd buffer depending of fs bsize */
        long    dd_size;        /* size of buffer */
        long    dd_flag;        /* private flags for readdir, unused */
        off_t   dd_loc;         /* logical(dirent) offset in  directory */
        off_t   dd_curoff;      /* real offset in directory corresponding
                                 * to dd_loc */
#else
        int     __dd_fd;                /* file descriptor of directory */
        blksize_t __dd_blksize; /* this filesystem's block size */
        char    *__dd_buf;      /* malloc'd buffer depending of fs bsize */
        long    __dd_size;      /* size of buffer */
        long    __dd_flag;      /* private flags for readdir, unused */
        off_t   __dd_loc;       /* logical(dirent) offset in  directory */
        off_t   __dd_curoff;    /* real offset in directory corresponding
                                 * to dd_loc */
#endif
#if defined(_THREAD_SAFE) && defined(_ALL_SOURCE)
        void    *dd_lock;       /* for inter-thread locking */
#endif

} DIR;

...

extern  DIR *opendir(const char *);
extern  struct dirent *readdir(DIR *);

In short - imho - depending on OS, the structure on disk may be quite simple or opaque. In the kernel I am not surprised if the organization is opaque as then you can modify the organization without needing to change any application code.

Not the answer you're looking for? Browse other questions tagged or ask your own question.