/* UFS directory lookup and modification
   Copyright (C) 1992 Free Software Foundation

This file is part of the GNU Hurd.

The GNU Hurd is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

The GNU Hurd is distributed in the hope that it will be useful, 
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with the GNU Hurd; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */

/* Written by Michael I. Bushnell.  */

#include "ufs.h"
#include "fs.h"
#include "dir.h"
#include "inode.h"
#include "dinode.h"

#include <string.h>
#include <errno.h>

static error_t
dirscanblock (struct inode *, off_t, char *, int, enum lookup_type,
	      struct dirstat *, ino_t *);

static int
bad_dir_entry (struct direct *, char *);

/* Lookup a name in a directory.

   DP is a pointer to the locked inode of the directory.

   TYPE is one of LOOKUP, CREATE, RENAME, or REMOVE.  Each returns
   error codes appropriate to that type.  LOOKUP finds and existing
   node.  CREATE looks up, with the intention that a new entry will be
   made if one doesn't already exist.  RENAME is used to change the
   inode identification of a name.  (It would be better called
   "renumber".)  REMOVE finds an existing node which will be deleted.
   The special type CHK_LOOKUP is just like LOOKUP, except for "..".
   It is only used by checkpath, and should be used by nothing else.
   The special type REN_RENAME is just like RENAME, except for "..".
   It is only used by set_dot_dot, and should be used by nothing else.

   NEWNODE is the address of an inode pointer, into which the requested
   node will be stored, unless it is null.

   DS is a buffer of cached information which must be provided for all
   but LOOKUP calls.  It is expected that CREATE calls will be
   followed with direnter calls, RENAME calls with dirrewrite calls or
   direnter calls, depending on the success of the lookup, and REMOVE
   calls with dirremove calls.  If the directory modification call is
   not made, then the DS buffer must be freed with dsrelease.

   CRED describes the user making the call.  */
error_t
lookup(struct inode *dp,
       char *name,
       enum lookup_type type,
       struct inode **newnode,
       struct dirstat *ds,
       struct protid *cred)
{
  error_t err;
  off_t blockoff;
  off_t dirsize;
  mode_t dirmode;
  ino_t inum;
  int namelen;
  int special_dotdot;
  
  if (ds)
    ds->type = LOOKING;		/* indicates it's invalid */

  if (type & SPEC_DOTDOT)
    {
      special_dotdot = 1;
      type &= ~SPEC_DOTDOT;
    }
  else
    special_dotdot = 0;
 
  if (!(err = catch_exception ()))
    {
      dirmode = DI_MODE (dp->di);
      dirsize = dp->di->di_size;
      end_catch_exception ();
    }
  else
    return err;
  
  /* Check the ability of the user to access the directory. */
  if ((dirmode & IFMT) != IFDIR)
    return ENOTDIR;

  namelen = strlen (name);

  /* Empty name */
  /* This must come here, because the user need not have search permission,
     because the directory is not actually read.  */
  if (namelen == 0)
    switch (type)
      {
      case LOOKUP:
      case CREATE:
	dp->i_refcnt++;
	*newnode = dp;
	return 0;
	
      case REMOVE:
      case RENAME:
	return EISDIR;
      }
    
  err = ufs_access (dp, IEXEC, cred);
  if (err)
    return err;
  
  if (type == CREATE || type == RENAME)
    ds->stat = LOOKING;
  
  for (blockoff = 0; blockoff < dirsize; blockoff += DIRBLKSIZ)
    {
      err = dirscanblock (dp, blockoff, name, namelen, type, ds, &inum);
      switch (err)
	{
	case 0:
	  /* Found it. */

	  if (inum == dp->i_number)
	    {
	      *newnode = dp;
	      dp->i_refcnt++;
	    }
	  else if (namelen == 2 && name[0] == '.' && name[1] == '.')
	    {
	      /* This case is special, because if we just did iget,
		 then we could deadlock.  As a result, we release our
		 lock and then lock things in the proper order.  */
	      if (type == LOOKUP && special_dotdot)
		{
		  /* This special case is for checkpath, where we don't
		     need dp locked any more, so it isn't worth the 
		     trouble. */
		  iput (dp);
		  if (err = iget (inum, newnode))
		    return err;
		}
	      else if ((type == RENAME || type == REMOVE)
		       && special_dotdot)
		{
		  /* This is for lookups which only want to change
		     the ".." entry, but already have the parent locked.
		     The caller must do a ufs_checkdirmod themselves.  */
		  return 0;
		}
	      else
		{
		  mutex_unlock (&dp->i_toplock);
		  if (err = iget (inum, newnode))
		    return err;
		  mutex_lock (&dp->i_toplock);
		}
	    }
	  else
	    err = iget (inum, newnode);
	  if (err)
	    return err;
	  
	  /* If we are deleting or renaming this, then 
	     we have to check more permissions now. */
	  if (type == REMOVE || type == RENAME)
	    {
	      err = ufs_checkdirmod (dp, dirmode, *newnode, cred);
	      
	      if (err)
		{
		  if (inum == dp->i_number)
		    irele (*newnode);
		  else
		    iput (*newnode);
		}
	    }
	  return err;

	default:
	  /* Some miscellaneous error. */
	  return err;
	  
	case ENOENT:
	  /* Not in this block. */
	  break;
	}
    }
  
  /* It wasn't there. */
  if (type == CREATE || type == RENAME)
    {
      /* If we didn't find any room, then we will have to
	 extend the dir to add this entry.  */
      if (ds->type == LOOKING)
	{
	  ds->type = CREATE;
	  ds->stat = EXTEND;
	  ds->blkoff = dirsize;
	}

      err = ufs_checkdirmod (dp, dirmode, 0, cred);
    }
  
  return err ? err : ENOENT;
}

/* Scan a block of a directory for a name.  Arguments are similar as
   for lookup.  */
static error_t
dirscanblock (struct inode *dp,
	      off_t blockoff,
	      char *name,
	      int namelen,
	      enum lookup_type type,
	      struct dirstat *ds,
	      ino_t *inum)
{
  int nfree = 0;
  int needed = 0;
  int countup = 0;
  char *currentoff, *prevoff;
  char buf[DIRBLKSIZ];
  int err;
  struct direct *entry;

  if (ds && ds->stat == LOOKING)
    {
      countup = 1;
      needed = DIRSIZ (namelen);
    }

  err = fs_rdwr (dp, buf, blockoff, DIRBLKSIZ, 0, 0);
  if (err)
    return err;
  
  for (currentoff = buf, prevoff = buf; 
       currentoff < buf + DIRBLKSIZ; 
       prevoff = currentoff, currentoff += entry->d_reclen)
    {
      entry = (struct direct *) currentoff;
      
      if (bad_dir_entry (entry, buf))
	return ENOENT;		/* Causes skip to next block */
	  
      if (countup)
	{
	  int thisfree;

	  if (entry->d_ino == 0)
	    thisfree = entry->d_reclen;
	  else
	    thisfree = entry->d_reclen - DIRSIZ (entry->d_namlen);

	  if (thisfree >= needed)
	    {
	      ds->type = CREATE;
	      ds->stat = entry->d_ino == 0 ? TAKE : SHRINK;
	      ds->blkoff = blockoff;
	      ds->offinblk = currentoff - buf;
	      countup = 0;
	    }
	  
	  nfree += thisfree;
	  if (nfree >= needed)
	    {
	      ds->type = CREATE;
	      ds->stat = COMPRESS;
	      ds->blkoff = blockoff;
	      ds->offinblk = 0;
	      countup = 0;
	    }
	}

      if (entry->d_namlen != namelen
	  || entry->d_name[0] != name[0]
	  || bcmp (entry->d_name, name, namelen))
	continue;

      /* We have found the required name. */

      switch (type)
	{
	case REMOVE:
	case RENAME:
	  ds->type = type;
	  ds->stat = HERE_TIS;
	  ds->blkoff = blockoff;
	  ds->prevoffinblk = prevoff - buf;
	  ds->offinblk = currentoff - buf;
	  break;
	  
	case CREATE:
	  ds->type = LOOKING;	/* reset to invalid */
	  break;
	  
	case LOOKUP:
	  break;
	  
	default:
	  panic ("dirscanblock");
	}

      *inum = entry->d_ino;
      return 0;
    }

  return ENOENT;
}

static int
bad_dir_entry (struct direct *entry,
	       char *blockstart)
{
  if (!entry->d_reclen
      || entry->d_reclen % 4
      || entry->d_namlen > MAXNAMLEN
      || (char *)entry + entry->d_reclen > blockstart + DIRBLKSIZ
      || entry->d_name[entry->d_namlen])
    return 1;

  /* These checks are more expensive, so we only do them if this
     option has been set. */
  if (long_dir_consistency_checking
      && (DIRSIZ(entry->d_namlen) > entry->d_reclen
	  || memchr (entry->d_name, '\0', entry->d_namlen)))
    return 1;
  
  return 0;
}

/* Following a lookup call for CREATE, this adds a node to a directory.
   DP is the directory to be modified; NAME is the name to be entered;
   IP is the inode being linked in; DS is the cached information returned
   by lookup; CRED describes the user making the call.  This call may
   only be made if the directory has been held locked continuously since
   the preceding lookup call, and only if that call returned ENOENT. */
error_t
direnter(struct inode *dp,
	 char *name,
	 struct inode *ip,
	 struct dirstat *ds,
	 struct protid *cred)
{
  char buf[DIRBLKSIZ];
  struct direct *old, *new, *from, *to;
  int namelen = strlen (name);
  int needed = DIRSIZ (namelen);
  int oldneeded;
  char *fromoff, *tooff;
  int totfreed;  
  error_t err;

  if (ds->type != CREATE)
    panic ("direnter bad type");
  
  if (ds->stat == TAKE
      || ds->stat == SHRINK
      || ds->stat == COMPRESS)
    {
      err = fs_rdwr (dp, buf, ds->blkoff, DIRBLKSIZ, 0, 0);
      if (err)
	return err;
    }

  switch (ds->stat)
    {
    case TAKE:
      /* We are supposed to consume this slot. */
      old = (struct direct *) (buf + ds->offinblk);
      if (old->d_ino != 0
	  || old->d_namlen <= needed)
	panic ("direnter (TAKE) slot too small");
      
      old->d_ino = ip->i_number;
      old->d_namlen = namelen;
      bcopy (name, old->d_name, namelen + 1);

      break;
      
    case SHRINK:
      /* We are supposed to take the extra space at the end
	 of this slot. */
      old = (struct direct *) (buf + ds->offinblk);
      oldneeded = DIRSIZ (old->d_namlen);
      if (old->d_reclen - oldneeded < needed)
	panic ("direnter (SHRINK) slot too small");
      
      new = (struct direct *) (buf + ds->offinblk + oldneeded);

      new->d_ino = ip->i_number;
      new->d_reclen = old->d_reclen - oldneeded;
      new->d_namlen = namelen;
      bcopy (name, new->d_name, namelen + 1);
      
      old->d_reclen = oldneeded;
      
      break;
      
    case COMPRESS:
      /* We are supposed to move all the entries to the
	 front of the block, giving each the minimum
	 necessary room.  This should free up enough space
	 for the new entry. */
      for (fromoff = tooff = buf, totfreed = 0;
	   fromoff < buf + DIRBLKSIZ;
	   fromoff += from->d_reclen)
	{
	  from = (struct direct *) fromoff;
	  to = (struct direct *) tooff;
	  
	  if (from->d_ino == 0)
	    continue;

	  to->d_ino = from->d_ino;
	  to->d_reclen = DIRSIZ (from->d_namlen);
	  to->d_namlen = from->d_namlen;
	  bcopy (from->d_name, to->d_name, from->d_namlen + 1);
	  
	  tooff += to->d_reclen;
	}

      totfreed = buf + DIRBLKSIZ - tooff;
      if (totfreed < needed)
	panic ("direnter (COMPRESS) not enough space");
      
      new = (struct direct *) tooff;
      new->d_ino = ip->i_number;
      new->d_reclen = totfreed;
      new->d_namlen = namelen;
      bcopy (name, new->d_name, namelen + 1);
      break;

    case EXTEND:
      /* We are supposed to add a new block to the directory. */
      new = (struct direct *) buf;
      new->d_ino = ip->i_number;
      new->d_reclen = DIRBLKSIZ;
      new->d_namlen = namelen;
      bcopy (name, new->d_name, namelen + 1);
      break;
      
    default:
      panic ("direnter bad status");
    }
        
  err = fs_rdwr (dp, buf, ds->blkoff, DIRBLKSIZ, 1, 0);
  file_update (dp, 1);

  return err;
}

/* Following a lookup call for REMOVE, this removes the link from the
   directory.  DP is the directory being changed and DS is the cached
   information returned from lookup.  This call is only valid if the
   directory has been locked continously since the call to lookup, and
   only if that call succeeded.  */
error_t
dirremove(struct inode *dp,
	  struct dirstat *ds)
{
  struct direct *prev, *cur;
  char buf[DIRBLKSIZ];
  error_t err;
  
  if (ds->type != REMOVE)
    panic ("dirremove bad type");
  if (ds->stat != HERE_TIS)
    panic ("dirremove bad status");
  
  err = fs_rdwr (dp, buf, ds->blkoff, DIRBLKSIZ, 0, 0);
  if (err)
    return err;

  cur = (struct direct *) (buf + ds->offinblk);
  prev = (struct direct *) (buf + ds->prevoffinblk);
  
  if (ds->blkoff == 0)
    cur->d_ino = 0;
  else
    {
      if (ds->offinblk - ds->prevoffinblk != prev->d_reclen)
	panic ("dirremove bad ds record");
      prev->d_reclen += cur->d_reclen;
    }
  
  err = fs_rdwr (dp, buf, ds->blkoff, DIRBLKSIZ, 1, 0);
  file_update (dp, 1);
  return err;
}
  

/* Following a lookup call for RENAME, this changes the inode number
   on a directory entry.  DP is the directory being changed; IP is 
   the new inode being linked in; DP is the cached information returned 
   by lookup.  This call is only valid if the directory has been locked
   continuously since the call to lookup, and only if that call
   succeeded.  */
error_t
dirrewrite(struct inode *dp, 
	   struct inode *ip,
	   struct dirstat *ds)
{
  struct direct *entry;
  char buf[DIRBLKSIZ];
  error_t err;
  
  if (ds->type != RENAME)
    panic ("dirrewrite bad type");
  if (ds->stat != HERE_TIS)
    panic ("dirrewrite bad stat");
  
  err = fs_rdwr (dp, buf, ds->blkoff, DIRBLKSIZ, 0, 0);
  if (err)
    return err;
  
  entry = (struct direct *) (buf + ds->offinblk);
  entry->d_ino = ip->i_number;
  
  err = fs_rdwr (dp, buf, ds->blkoff, DIRBLKSIZ, 1, 0);
  file_update (dp, 1);
  return err;
}

/* Tell if IP is an empty directory (has only "." and ".." entries). */
/* This routine must be called from inside a catch_exception ().  */
int
dirempty(struct inode *dp,
	 struct protid *cred)
{
  struct direct *entry;
  int curoff;
  char *offinblk;
  char buf[DIRBLKSIZ];
  
  for (curoff = 0; curoff < dp->di->di_size; curoff += DIRBLKSIZ)
    {
      fs_rdwr (dp, buf, curoff, DIRBLKSIZ, 0, 0);
      
      for (offinblk = buf;
	   offinblk < buf + DIRBLKSIZ; 
	   offinblk += entry->d_reclen)
	{
	  entry = (struct direct *) offinblk;

	  if (entry->d_ino != 0
	      && (entry->d_namlen > 2
		  || entry->d_name[0] != '.'
		  || (entry->d_name[1] != '.'
		      && entry->d_name[1] != '\0')))
	    return 0;
	}
    }
  return 1;
}

/* Check if source directory is in the path of the target directory.
   We get target locked, source unlocked but with a reference.  When
   we return, nothing is locked, and target has lost its reference.
   This routine assumes that no renames of directories will happen
   while it is running; as a result, ufs_rename serializes all renames
   of directories.  */
error_t
checkpath(struct inode *source,
	  struct inode *target,
	  struct protid *cred)
{
  error_t err;
  struct inode *ip;
  ino_t sourceinum = source->i_number;
  
  ip = target;
  for (ip = target, err = 0;
       /* nothing */;
       /* This special lookup does an iput on its first argument
	  when it succeeds. */
       err = lookup (ip, "..", LOOKUP | SPEC_DOTDOT, &ip, 0, cred))
    {
      if (err)
	{
	  iput (ip);
	  return err;
	}
      
      if (ip->i_number == sourceinum)
	{
	  iput (ip);
	  return EINVAL;
	}
      
      if (ip->i_number == ROOTINO)
	{
	  iput (ip);
	  return 0;
	}
    }
}  


void
dsrelease (struct dirstat *ds)
{
  ds->type = LOOKUP;
  return;
}


error_t
ufs_access (struct inode *ip,
	    mode_t type,
	    struct protid *cred)
{
  volatile mode_t mode = DI_MODE (ip->di);
  int test;
  error_t error;
  
  if (isuid (0, cred))
    return 0;
  
  if (error = catch_exception ())
    return error;
  
  if (isuid (DI_UID (ip->di), cred))
    test = (mode & IOWNER) >> 6;
  else if (groupmember (DI_GID (ip->di), cred))
    test = (mode & IGROUP) >> 3;
  else if (cred->nuids || !(mode & IUSEUNK))
    test = mode & IKNOWN;
  else
    test = (mode & IUNKNOWN) >> 18;
  end_catch_exception ();
  return ((test & (type >> 6)) ? 0 : EACCES);
}

error_t
ufs_checkdirmod (struct inode *dp,
		 mode_t dirmode,
		 struct inode *ip,
		 struct protid *cred)
{
  error_t err;
  
  err = ufs_access (dp, IWRITE, cred);
  if (err)
    return err;

  /* Sticky bit means you must be the owner of the 
     file, or the directory, or root, in order to
     manipulate it.  */
  if (ip
      && (dirmode & ISVTX)
      && ! isowner (dp, cred)
      && ! isowner (ip, cred)
      && ! isuid (0, cred))
    err = EPERM;
  return err;
}

int
groupmember (gid_t grp,
	     struct protid *cred)
{
  int i;
  gid_t *idp;
  
  for (i = 0, idp = cred->gids->ids; i < cred->ngids;
       i++, idp++)
    if (grp == *idp)
      return 1;
  return 0;
}

/* This means "is U.I.D.", not "inode set U.I.D." */
int
isuid (uid_t uid,
       struct protid *cred)
{
  int i;
  uid_t *idp;
  
  for (i = 0, idp = cred->uids->ids; i < cred->nuids;
       i++, idp++)
    if (uid == *idp)
      return 1;
  return 0;
}

/* Test if the user can do owner-only modifications */
int 
isowner (struct inode *ip,
	 struct protid *cred)
{
  int i;
  uid_t *idp;
  uid_t owner;
  gid_t group;
  error_t error;

  if (error = catch_exception ())
    return error;
  owner = DI_UID (ip->di);
  group = DI_GID (ip->di);
  end_catch_exception ();

  for (i = 0, idp = cred->uids->ids; i < cred->nuids; i++, idp++)
    {
      if (*idp == 0 || *idp == owner)
	return 0;
      if (*idp == group && groupmember (group, cred))
	return 0;
    }
  return EPERM;
}

  
 
