minix/fs/ext2/path.c

   1 /* This file contains the procedures that look up path names in the directory
   2  * system and determine the inode number that goes with a given path name.
   3  *
   4  * Created (MFS based):
   5  *   February 2010 (Evgeniy Ivanov)
   6  */
   7
   8 #include "fs.h"
   9 #include <assert.h>
  10 #include <string.h>
  11 #include <sys/param.h>
  12 #include "buf.h"
  13 #include "inode.h"
  14 #include "super.h"
  15
  16
  17 /*===========================================================================*
  18  *                             fs_lookup                                     *
  19  *===========================================================================*/
  20 int fs_lookup(ino_t dir_nr, char *name, struct fsdriver_node *node,
  21         int *is_mountpt)
  22 {
  23   struct inode *dirp, *rip;
  24
  25   /* Find the starting inode. */
  26   if ((dirp = find_inode(fs_dev, dir_nr)) == NULL)
  27         return EINVAL;
  28
  29   /* Look up the directory entry. */
  30   if ((rip = advance(dirp, name)) == NULL)
  31         return err_code;
  32
  33   /* On success, leave the resulting inode open and return its details. */
  34   node->fn_ino_nr = rip->i_num;
  35   node->fn_mode = rip->i_mode;
  36   node->fn_size = rip->i_size;
  37   node->fn_uid = rip->i_uid;
  38   node->fn_gid = rip->i_gid;
  39   /* This is only valid for block and character specials. But it doesn't
  40    * cause any harm to always set the device field. */
  41   node->fn_dev = (dev_t) rip->i_block[0];
  42
  43   *is_mountpt = rip->i_mountpoint;
  44
  45   return OK;
  46 }
  47
  48
  49 /*===========================================================================*
  50  *                              advance                                      *
  51  *===========================================================================*/
  52 struct inode *advance(dirp, string)
  53 struct inode *dirp;             /* inode for directory to be searched */
  54 const char *string;             /* component name to look for */
  55 {
  56 /* Given a directory and a component of a path, look up the component in
  57  * the directory, find the inode, open it, and return a pointer to its inode
  58  * slot.
  59  */
  60   ino_t numb;
  61   struct inode *rip;
  62
  63   assert(dirp != NULL);
  64
  65   /* If 'string' is empty, return an error. */
  66   if (string[0] == '\0') {
  67         err_code = ENOENT;
  68         return(NULL);
  69   }
  70
  71   /* If dir has been removed return ENOENT. */
  72   if (dirp->i_links_count == NO_LINK) {
  73         err_code = ENOENT;
  74         return(NULL);
  75   }
  76
  77   /* If 'string' is not present in the directory, signal error. */
  78   if ( (err_code = search_dir(dirp, string, &numb, LOOK_UP, 0)) != OK) {
  79         return(NULL);
  80   }
  81
  82   /* The component has been found in the directory.  Get inode. */
  83   if ( (rip = get_inode(dirp->i_dev, (int) numb)) == NULL)  {
  84         assert(err_code != OK);
  85         return(NULL);
  86   }
  87
  88   return(rip);
  89 }
  90
  91
  92 /*===========================================================================*
  93  *                              search_dir                                   *
  94  *===========================================================================*/
  95 int search_dir(ldir_ptr, string, numb, flag, ftype)
  96 register struct inode *ldir_ptr; /* ptr to inode for dir to search */
  97 const char *string;              /* component to search for */
  98 ino_t *numb;                     /* pointer to inode number */
  99 int flag;                        /* LOOK_UP, ENTER, DELETE or IS_EMPTY */
 100 int ftype;                       /* used when ENTER and INCOMPAT_FILETYPE */
 101 {
 102 /* This function searches the directory whose inode is pointed to by 'ldip':
 103  * if (flag == ENTER)  enter 'string' in the directory with inode # '*numb';
 104  * if (flag == DELETE) delete 'string' from the directory;
 105  * if (flag == LOOK_UP) search for 'string' and return inode # in 'numb';
 106  * if (flag == IS_EMPTY) return OK if only . and .. in dir else ENOTEMPTY;
 107  */
 108   register struct ext2_disk_dir_desc  *dp = NULL;
 109   register struct ext2_disk_dir_desc  *prev_dp = NULL;
 110   register struct buf *bp = NULL;
 111   int i, r, e_hit, t, match;
 112   off_t pos;
 113   unsigned new_slots;
 114   int extended = 0;
 115   int required_space = 0;
 116   int string_len = 0;
 117
 118   /* If 'ldir_ptr' is not a pointer to a dir inode, error. */
 119   if ( (ldir_ptr->i_mode & I_TYPE) != I_DIRECTORY)  {
 120         return(ENOTDIR);
 121   }
 122
 123   new_slots = 0;
 124   e_hit = FALSE;
 125   match = 0;            /* set when a string match occurs */
 126   pos = 0;
 127
 128   if ((string_len = strlen(string)) > EXT2_NAME_MAX)
 129         return(ENAMETOOLONG);
 130
 131   if (flag == ENTER) {
 132         required_space = MIN_DIR_ENTRY_SIZE + string_len;
 133         required_space += (required_space & 0x03) == 0 ? 0 :
 134                              (DIR_ENTRY_ALIGN - (required_space & 0x03) );
 135
 136         if (ldir_ptr->i_last_dpos < ldir_ptr->i_size &&
 137             ldir_ptr->i_last_dentry_size <= required_space)
 138                 pos = ldir_ptr->i_last_dpos;
 139   }
 140
 141   for (; pos < ldir_ptr->i_size; pos += ldir_ptr->i_sp->s_block_size) {
 142         /* Since directories don't have holes, 'b' cannot be NO_BLOCK. */
 143         if(!(bp = get_block_map(ldir_ptr,
 144            rounddown(pos, ldir_ptr->i_sp->s_block_size))))
 145                 panic("get_block returned NO_BLOCK");
 146
 147         prev_dp = NULL; /* New block - new first dentry, so no prev. */
 148
 149         /* Search a directory block.
 150          * Note, we set prev_dp at the end of the loop.
 151          */
 152         for (dp = (struct ext2_disk_dir_desc*) &b_data(bp);
 153              CUR_DISC_DIR_POS(dp, &b_data(bp)) < ldir_ptr->i_sp->s_block_size;
 154              dp = NEXT_DISC_DIR_DESC(dp) ) {
 155                 /* Match occurs if string found. */
 156                 if (flag != ENTER && dp->d_ino != NO_ENTRY) {
 157                         if (flag == IS_EMPTY) {
 158                                 /* If this test succeeds, dir is not empty. */
 159                                 if (ansi_strcmp(dp->d_name, ".", dp->d_name_len) != 0 &&
 160                                     ansi_strcmp(dp->d_name, "..", dp->d_name_len) != 0) match = 1;
 161                         } else {
 162                                 if (ansi_strcmp(dp->d_name, string, dp->d_name_len) == 0){
 163                                         match = 1;
 164                                 }
 165                         }
 166                 }
 167
 168                 if (match) {
 169                         /* LOOK_UP or DELETE found what it wanted. */
 170                         r = OK;
 171                         if (flag == IS_EMPTY) r = ENOTEMPTY;
 172                         else if (flag == DELETE) {
 173                                 if (dp->d_name_len >= sizeof(ino_t)) {
 174                                         /* Save d_ino for recovery. */
 175                                         t = dp->d_name_len - sizeof(ino_t);
 176                                         memcpy(&dp->d_name[t], &dp->d_ino, sizeof(dp->d_ino));
 177                                 }
 178                                 dp->d_ino = NO_ENTRY;   /* erase entry */
 179                                 lmfs_markdirty(bp);
 180
 181                                 /* If we don't support HTree (directory index),
 182                                  * which is fully compatible ext2 feature,
 183                                  * we should reset EXT2_INDEX_FL, when modify
 184                                  * linked directory structure.
 185                                  *
 186                                  * @TODO: actually we could just reset it for
 187                                  * each directory, but I added if() to not
 188                                  * forget about it later, when add HTree
 189                                  * support.
 190                                  */
 191                                 if (!HAS_COMPAT_FEATURE(ldir_ptr->i_sp,
 192                                                         COMPAT_DIR_INDEX))
 193                                         ldir_ptr->i_flags &= ~EXT2_INDEX_FL;
 194                                 if (pos < ldir_ptr->i_last_dpos) {
 195                                         ldir_ptr->i_last_dpos = pos;
 196                                         ldir_ptr->i_last_dentry_size =
 197                                                 conv2(le_CPU, dp->d_rec_len);
 198                                 }
 199                                 ldir_ptr->i_update |= CTIME | MTIME;
 200                                 ldir_ptr->i_dirt = IN_DIRTY;
 201                                 /* Now we have cleared dentry, if it's not
 202                                  * the first one, merge it with previous one.
 203                                  * Since we assume, that existing dentry must be
 204                                  * correct, there is no way to spann a data block.
 205                                  */
 206                                 if (prev_dp) {
 207                                         u16_t temp = conv2(le_CPU,
 208                                                         prev_dp->d_rec_len);
 209                                         temp += conv2(le_CPU,
 210                                                         dp->d_rec_len);
 211                                         prev_dp->d_rec_len = conv2(le_CPU,
 212                                                         temp);
 213                                 }
 214                         } else {
 215                                 /* 'flag' is LOOK_UP */
 216                                 *numb = (ino_t) conv4(le_CPU, dp->d_ino);
 217                         }
 218                         put_block(bp);
 219                         return(r);
 220                 }
 221
 222                 /* Check for free slot for the benefit of ENTER. */
 223                 if (flag == ENTER && dp->d_ino == NO_ENTRY) {
 224                         /* we found a free slot, check if it has enough space */
 225                         if (required_space <= conv2(le_CPU, dp->d_rec_len)) {
 226                                 e_hit = TRUE;   /* we found a free slot */
 227                                 break;
 228                         }
 229                 }
 230                 /* Can we shrink dentry? */
 231                 if (flag == ENTER && required_space <= DIR_ENTRY_SHRINK(dp)) {
 232                         /* Shrink directory and create empty slot, now
 233                          * dp->d_rec_len = DIR_ENTRY_ACTUAL_SIZE + DIR_ENTRY_SHRINK.
 234                          */
 235                         int new_slot_size = conv2(le_CPU, dp->d_rec_len);
 236                         int actual_size = DIR_ENTRY_ACTUAL_SIZE(dp);
 237                         new_slot_size -= actual_size;
 238                         dp->d_rec_len = conv2(le_CPU, actual_size);
 239                         dp = NEXT_DISC_DIR_DESC(dp);
 240                         dp->d_rec_len = conv2(le_CPU, new_slot_size);
 241                         /* if we fail before writing real ino */
 242                         dp->d_ino = NO_ENTRY;
 243                         lmfs_markdirty(bp);
 244                         e_hit = TRUE;   /* we found a free slot */
 245                         break;
 246                 }
 247
 248                 prev_dp = dp;
 249         }
 250
 251         /* The whole block has been searched or ENTER has a free slot. */
 252         if (e_hit) break;       /* e_hit set if ENTER can be performed now */
 253         put_block(bp);           /* otherwise, continue searching dir */
 254   }
 255
 256   /* The whole directory has now been searched. */
 257   if (flag != ENTER) {
 258         return(flag == IS_EMPTY ? OK : ENOENT);
 259   }
 260
 261   /* When ENTER next time, start searching for free slot from
 262    * i_last_dpos. It gives solid performance improvement.
 263    */
 264   ldir_ptr->i_last_dpos = pos;
 265   ldir_ptr->i_last_dentry_size = required_space;
 266
 267   /* This call is for ENTER.  If no free slot has been found so far, try to
 268    * extend directory.
 269    */
 270   if (e_hit == FALSE) { /* directory is full and no room left in last block */
 271         new_slots++;            /* increase directory size by 1 entry */
 272         if ( (bp = new_block(ldir_ptr, ldir_ptr->i_size)) == NULL)
 273                 return(err_code);
 274         dp = (struct ext2_disk_dir_desc*) &b_data(bp);
 275         dp->d_rec_len = conv2(le_CPU, ldir_ptr->i_sp->s_block_size);
 276         dp->d_name_len = DIR_ENTRY_MAX_NAME_LEN(dp); /* for failure */
 277         extended = 1;
 278   }
 279
 280   /* 'bp' now points to a directory block with space. 'dp' points to slot. */
 281   dp->d_name_len = string_len;
 282   for (i = 0; i < NAME_MAX && i < dp->d_name_len && string[i]; i++)
 283         dp->d_name[i] = string[i];
 284   dp->d_ino = (int) conv4(le_CPU, *numb);
 285   if (HAS_INCOMPAT_FEATURE(ldir_ptr->i_sp, INCOMPAT_FILETYPE)) {
 286         /* Convert ftype (from inode.i_mode) to dp->d_file_type */
 287         if (ftype == I_REGULAR)
 288                 dp->d_file_type = EXT2_FT_REG_FILE;
 289         else if (ftype == I_DIRECTORY)
 290                 dp->d_file_type = EXT2_FT_DIR;
 291         else if (ftype == I_SYMBOLIC_LINK)
 292                 dp->d_file_type = EXT2_FT_SYMLINK;
 293         else if (ftype == I_BLOCK_SPECIAL)
 294                 dp->d_file_type = EXT2_FT_BLKDEV;
 295         else if (ftype == I_CHAR_SPECIAL)
 296                 dp->d_file_type = EXT2_FT_CHRDEV;
 297         else if (ftype == I_NAMED_PIPE)
 298                 dp->d_file_type = EXT2_FT_FIFO;
 299         else
 300                 dp->d_file_type = EXT2_FT_UNKNOWN;
 301   }
 302   lmfs_markdirty(bp);
 303   put_block(bp);
 304   ldir_ptr->i_update |= CTIME | MTIME;  /* mark mtime for update later */
 305   ldir_ptr->i_dirt = IN_DIRTY;
 306
 307   if (new_slots == 1) {
 308         ldir_ptr->i_size += (off_t) conv2(le_CPU, dp->d_rec_len);
 309         /* Send the change to disk if the directory is extended. */
 310         if (extended) rw_inode(ldir_ptr, WRITING);
 311   }
 312   return(OK);
 313
 314 }