mksquashfs: Create new lookup_inode2()

Move setting of pseudo and pseudo_id into lookup_inode() rather than
requiring callers to set them if necessary.  Add these as
parameters to lookup_inode() and rename to lookup_inode2().

This cleans up the code in the callers of lookup_inode2().

Also add lookup_inode() as an inline wrapper to lookup_inode2()
to avoid obfusticating existing callers of lookup_inode().

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: create inode_number() and parent_inode()

Move code to get the inode_number and the parent inode_number into
separate functions.  This removes duplicate code and removes knowledge
of the implementation out of the caller functions.

It is also the first stage in changing how and when the inode
numbers are computed.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: rearrange dir_scan* routines

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: move inode_number allocation and sorting into a new scan routine

Move inode_number allocation out of the first scan (dir_scan1), and
directory sorting out of the second scan (dir_scan2).

Move them into a new dir_scan3, and bump the existing dir_scan3 to
dir_scan4.

There are a couple of reasons for doing this:

1. It fixes the problem that inode_numbers were allocated in
   the order files were read from the source directories, which is often
   different to the order files appear in the final file system image
   after sorting (*)

2. Previously if a file was added in the first scan (i.e. not excluded),
   it was guaranteed to be present in the final file system image and
   to be at that place in the directory hierarchy, and so it made sense
   to allocate the inode number then (ignoring issue 1 above), but now with
   the empty action and the soon to be implemented move action,
   this no longer makes sense.

   2.1. a directories can be deleted by the empty action after the
       first scan (**)

   2.2. directories and files can be moved into different directories
        by the move action after the first scan, and inode numbers
        should be allocated based on where the files will be in the
        final file system image and not where they appeared in the
        source directories (another case of issue 1 above).

(*) this is an aesthetic issue rather than one of correctness (the
    previous allocation was correct, but perhaps not as nice aesthetically).

(**) putting the empty action in the first scan avoided the issue that
     inode_numbers were allocated in the first scan, but, it is broken.
     An empty directory in the first scan can be populated by pseudo files
     in the second scan, or by the move action.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: Use a linked list to store directory entries rather than an array

When scanning and storing the source directories use a
linked list to store the directory entries rather than an array.

This change is to more efficiently handle the empty action and the
soon to be implemented move action.  The empty action removes
directory entries and the move action may move directory entries
from one directory to another.  These actions are rather messy to
implement with arrays requiring any holes resulting from deleting/moving
to be filled by shuffling array entries down to fill the hole.
Linked lists allow entries to be deleted/moved much easier, which
is not only a performance improvement but results in more
aesthetically pleasing code.

Arrays were previously used only because the qsort function requires
arrays.  The move to linked lists has improved the code and this is
an additional unexpected bonus, which is in addition to the previously
mentioned reasons to move to linked lists.

Qsort is stil used in this commit, and so code has been added to
convert the linked-list into an array before calling qsort, and code
has also been added to convert the sorted array into a linked-list.
This is messy, but only temporary, to ensure this commit doesn't
break mksquashfs.  The next commit will remove qsort and will instead
add a merge sort which can efficiently sort linked lists
( O(n log n) which is the same complexity as qsort).

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: Remove qsort and add a bottom up linked list merge sort

Now that directory entries are stored in a linked list, rather
than an array, move to using a bottom up linked list merge sort.

Qsort and other O(n log n) algorithms work well with arrays but not
linked lists.  Merge sort another O(n log n) sort algorithm on the other
hand is not ideal for arrays (as it needs an additional n storage
locations as sorting is not done in place), but it is ideal for linked
lists because it doesn't require any extra storage.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
actions: Apply actions to the root directory

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
actions: fix root parent inode computation and action depth() test

The previous commit added the ability to execute actions on the root
inode ("/"), however, it introduces a couple of subtle bugs.

These bugs are caused by the change to create_dir_entry() where
the root dir_ent's parent directory is changed from NULL to the root
directory, creating the situation where the parent of the root directory
is itself.  This change was ultimately because the action code relies
on the parent directory not being NULL (previously the action code was
not executed on the root dir_ent and so the parent was never NULL).

This, however, introduces the following two subtle bugs:

1. Root parent inode number computation is broken

get_parent_no() returns the parent inode number for a directory when
this directory inode is being added to the inode table.  get_parent_no()
relies on the special case that the parent is NULL to detect when it is
dealing with the root directory inode.  As the root parent is now
itself, we effectively end up with ".." and "." in the root directory
having the same inode number, which is obviously wrong.

Due to the way mount works, the parent directory ("..") of a mounted
filesystem is the parent of the mount point (as you would expect),
and so this bug is largely hidden, however, the readir() system
call directly queries the filesystem, and this does return ".." and
"." as having the same inode number

% myls .

. 961
.. 961
.git 1
0001-Apply-actions-to-the-root-directory.patch 826

2. The depth() operation tests the depth of a particular file or
directory, files in the root directory have depth 1, files in immediate
subdirectories have depth 2 and so on.  Making the parent of the root
dir_ent be the root introduces the suble bug that the root inode
will be incorrectly considered to be at depth 1, when it should be at
depth 0.

The correct solution is to add a dummy parent dir_info at depth 0,
and to check for that in get_parent_no().

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: fix subpathname() so it doesn't use source_name

Source_name stores the original name of the file if it has been
renamed and it is needed by pathname() when accessing the file.

Subpathname() on the other hand should return the pathname() of
the file in the Squashfs filesystem after renaming and moving.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: fix assignment of source_name

Normally create_dir_entry will be called with source_name == NULL
if the file has not been renamed.

If the file has been renamed, create_dir_entry will be called
with name holding the new name, and source_name holding the
original_name.

This commit fixes the callers which in the case where the file
has not been renamed, call create_dir_entry with source_name ==
name, leading to source_name being != NULL when the file has not
been renamed.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquasfs: fix free_dir_entry

Now that create_dir_entry isn't being called with source_name ==
name, remove the check for that in free_dir_entry.

Also tidy code by removing the unnecessary != NULL check for name.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: optimise lookup_inode2() for dirs

Don't do the look-up for directories because we don't hard-link
directories.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: fix -info to use subpathname()

Now we have subpathname() that represents the pathname of the file
from the point of view of the output Squashfs filesystem (rather
than pathname(), which represents the pathname in the source
filesystem), use that in preference to pathname().

In the future with the move action, which can rename and move files
around, this is necessary because the output should reflect the
results of any move actions.

Additionally, irrespective of the new move action, subpathname()
was always a better choice than pathname(), but until recently it
didn't exist, and so couldn't be used.

Also fix the numerous -info outputs which incorrectly just output
the name of the file rather than the full pathname.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: get rid of redundant dir_name in dir_scan4()

With the fix of the -info output lines to use subpathname(), there
is now only one use of dir_name.  Get rid of it and use dir_ent->name
directly.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: get rid of redundant inode_info in dir_scan4()

Only used in next line, get rid of it and use dir_ent->inode directly

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: make subpathname() return a leading "/"

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
actions: make sure user supplied (sub)pathname has a leading "/"

If the user supplied subpathname or pathname does not have a
leading "/" then add one, otherwise matches against the pathname
supplied by subpathname() will always fail.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
mksquashfs: fix root dir_ent naming

root dir_ent should be unamed ("") and not pathname.

This enables pathname("/") and subpathname("/") to
match on the root directory.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
pseudo: fix handling of modify pseudo files

Matthieu CASTET reported a bug with modify pseudo files where if
a directory was modified, it would be subsequently treated as
a non-directory for further pseudo modify files.

His provided patch was unfortunately only a partial fix.

This is a full fix for the bug.

Thanks to Matthieu CASTET for reporting the bug.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
pseudo: fix handling of directory pseudo files

Fix bug where directories created by pseudo directory files
did not have subpath correctly set.

This meant subpathname() would not return the correct pathname,
with the effect that -info and the action tests pathname() and
subpathname() were broken.

Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>