Ultrix-3.1/sys/sys/flock.c

/**********************************************************************
 *   Copyright (c) Digital Equipment Corporation 1984, 1985, 1986.    *
 *   All Rights Reserved. 					      *
 *   Reference "/usr/src/COPYRIGHT" for applicable restrictions.      *
 **********************************************************************/

/*
 * SCCSID: @(#)flock.c	3.1	7/21/87
 */

#include <sys/types.h>
#include <sys/param.h>
#include <errno.h>
#include <sys/file.h>
#include <sys/inode.h>
#include <sys/dir.h>
#include <signal.h>
#include <sys/proc.h>
#include <sys/user.h>
#include <sys/flock.h>

/* region types */
#define	S_BEFORE	010
#define	S_START		020
#define	S_MIDDLE	030
#define	S_END		040
#define	S_AFTER		050
#define	E_BEFORE	001
#define	E_START		002
#define	E_MIDDLE	003
#define	E_END		004
#define	E_AFTER		005

#define	SLEEP(ptr, pri)		sleep(ptr, pri)
#define	WAKEUP(ptr)		if (ptr->stat.wakeflg) { \
					wakeup(ptr); \
					ptr->stat.wakeflg = 0 ; \
				}
#define l_end 		l_len
#define MAXEND  	017777777777

extern	struct	flckinfo flckinfo;	/* configuration and acct info		*/
struct	filock	*frlock;		/* pointer to record lock free list	*/
struct	flino	*frfid;			/* file id free list			*/
struct	flino	*fids;			/* file id head list			*/
struct	flino	sleeplcks;		/* head of chain of sleeping locks	*/

/* find file id */
static struct flino *
findfid(fp)
struct file *fp;
{
	register struct flino *flip;
	register i;
	register dev_t d;
	register ino_t n;

	d = fp->f_inode->i_dev;
	n = fp->f_inode->i_number;
	flip = fids;
	while (flip != NULL) {
		if (flip->fl_dev == d && flip->fl_number == n) {
			flip->fl_refcnt++;
			break;
		}
		flip = flip->flinext;
	}
	return (flip);
}

static struct flino *
allocfid(fp)
struct file *fp;
{
	struct flino *flip;

	flip = frfid;
	if (flip != NULL) {
		++flckinfo.filcnt;
		++flckinfo.filtot;
		/* remove from free list */
		frfid = flip->flinext;
		if (frfid != NULL)
			frfid->fliprev = NULL;

		/* insert into allocated file identifier list */
		if (fids != NULL)
			fids->fliprev = flip;
		flip->flinext = fids;
		fids = flip;

		/* set up file identifier info */
		++flip->fl_refcnt;
		flip->fl_dev = fp->f_inode->i_dev;
		flip->fl_number = fp->f_inode->i_number;
	}
	return (flip);
}

static freefid(flip)
struct flino *flip;
{
	if (--flip->fl_refcnt <= 0 && flip->fl_flck == NULL) {
		--flckinfo.filcnt;
		if (flip->fliprev != NULL)
			flip->fliprev->flinext = flip->flinext;
		else
			fids = flip->flinext;
		if (flip->flinext != NULL)
			flip->flinext->fliprev = flip->fliprev;
		flip->fl_dev = 0;
		flip->fl_number = 0;
		flip->fl_refcnt = 0;
		if (frfid != NULL)
			frfid->fliprev = flip;
		flip->flinext = frfid;
		flip->fliprev = NULL;
		frfid = flip;
	}
}
	

/* build file lock free list
 */
flckinit()
{
	register i;

	for (i=0; i<flckinfo.fils; i++) {
		freefid(&flinotab[i]);
	}
	flckinfo.filcnt = 0;

	for (i=0; i<flckinfo.recs; i++) {
		if (frlock == NULL) {
			flox[i].flknext = flox[i].flkprev = NULL;
			frlock = &flox[i];
		} else {
			flox[i].flknext = frlock;
			flox[i].flkprev = NULL;
			frlock = (frlock->flkprev = &flox[i]);
		}
	}
	flckinfo.reccnt = 0;
}

/* insert lock after given lock using locking data */

static struct filock *
insflck(flip, lckdat, fl)
struct	flino	*flip;
struct	filock	*fl;
struct	flock	*lckdat;
{
	register struct filock *new;
	struct	filock	*f;

	new = frlock;
	if (new != NULL) {
		++flckinfo.reccnt;
		++flckinfo.rectot;
		frlock = new->flknext;
		if (frlock != NULL)
			frlock->flkprev = NULL;
		new->set = *lckdat;
		new->set.l_pid = u.u_procp->p_pid;
		new->stat.wakeflg = 0;
		if (fl == NULL) {
			new->flknext = flip->fl_flck;
			if (flip->fl_flck != NULL)
				flip->fl_flck->flkprev = new;
			flip->fl_flck = new;
		} else {
			new->flknext = fl->flknext;
			if (fl->flknext != NULL)
				fl->flknext->flkprev = new;
			fl->flknext = new;
		}
		new->flkprev = fl;
	}
	return (new);
}

/* delete lock
 */
static delflck(flip, fl)
struct flino *flip;
struct filock *fl;
{
	if (fl->flkprev != NULL)
		fl->flkprev->flknext = fl->flknext;
	else
		flip->fl_flck = fl->flknext;
	if (fl->flknext != NULL)
		fl->flknext->flkprev = fl->flkprev;
	WAKEUP(fl);

	--flckinfo.reccnt;
	if (frlock == NULL) {
		fl->flknext = fl->flkprev = NULL;
		frlock = fl;
	} else {
		fl->flknext = frlock;
		fl->flkprev = NULL;
		frlock = (frlock->flkprev = fl);
	}
}

/* regflck sets the type of span of this (un)lock relative to the specified
 * already existing locked section.
 * There are five regions:
 *
 *  S_BEFORE        S_START         S_MIDDLE         S_END          S_AFTER
 *     010            020             030             040             050
 *  E_BEFORE        E_START         E_MIDDLE         E_END          E_AFTER
 *      01             02              03              04              05
 * 			|-------------------------------|
 *
 * relative to the already locked section.  The type is two octal digits,
 * the 8's digit is the start type and the 1's digit is the end type.
 */
static int
regflck(ld, flp)
struct flock *ld;
struct filock *flp;
{
	register int regntype;

	if (ld->l_start > flp->set.l_start) {
		if (ld->l_start > flp->set.l_end)
			return(S_AFTER|E_AFTER);
		else if (ld->l_start == flp->set.l_end)
			return(S_END|E_AFTER);
		else
			regntype = S_MIDDLE;
	} else if (ld->l_start == flp->set.l_start)
		regntype = S_START;
	else
		regntype = S_BEFORE;

	if (ld->l_end > flp->set.l_start) {
		if (ld->l_end > flp->set.l_end)
			regntype |= E_AFTER;
		else if (ld->l_end == flp->set.l_end)
			regntype |= E_END;
		else
			regntype |= E_MIDDLE;
	} else if (ld->l_end == flp->set.l_start)
		regntype |= E_START;
	else
		regntype |= E_BEFORE;

	return (regntype);
}

/* Adjust file lock from region specified by 'ld' starting at lock 'insrtp'
 */
static flckadj(flip, insrtp, ld)
struct flino	*flip;
struct filock	*insrtp;
struct flock	*ld;
{
	struct	flock	td;			/* lock data for severed lock */
	struct	filock	*flp, *nflp, *tdi, *tdp;
	int	insrtflg, rv = 0;
	int	regtyp;

	insrtflg = (ld->l_type != F_UNLCK) ? 1 : 0;

	nflp = (insrtp == NULL) ? flip->fl_flck : insrtp;
	while (flp = nflp) {
		nflp = flp->flknext;
		if (flp->set.l_pid == u.u_procp->p_pid) {

			regtyp = regflck(ld, flp);

			/* release already locked region if necessary */

			switch (regtyp) {
			case S_BEFORE|E_BEFORE:
				nflp = NULL;
				break;
			case S_BEFORE|E_START:
				if (ld->l_type == flp->set.l_type) {
					ld->l_end = flp->set.l_end;
					if (insrtp == flp)
						insrtp = flp->flkprev;
					delflck(flip, flp);
				}
				nflp = NULL;
				break;
			case S_START|E_END:
				/* don't bother if this is in the middle of
				 * an already similarly set section.
				 */
				if (ld->l_type == flp->set.l_type)
					return(rv);
			case S_START|E_AFTER:
				insrtp = flp->flkprev;
				delflck(flip, flp);
				break;
			case S_BEFORE|E_END:
				if (ld->l_type == flp->set.l_type)
					nflp = NULL;
			case S_BEFORE|E_AFTER:
				if (insrtp == flp)
					insrtp = flp->flkprev;
				delflck(flip, flp);
				break;
			case S_BEFORE|E_MIDDLE:
				if (ld->l_type == flp->set.l_type)
					ld->l_end = flp->set.l_end;
				else {
					/* setup piece after end of (un)lock */
					td = flp->set;
					td.l_start = ld->l_end;
					tdp = tdi = flp;
					do {
						if (tdp->set.l_start < ld->l_start)
							tdi = tdp;
						else
							break;
					} while (tdp = tdp->flknext);
					if (insflck(flip, &td, tdi) == NULL)
						return(ENOSPC);
				}
				if (insrtp == flp)
					insrtp = flp->flkprev;
				delflck(flip, flp);
				nflp = NULL;
				break;
			case S_START|E_MIDDLE:
			case S_MIDDLE|E_MIDDLE:
				/* don't bother if this is in the middle of
				 * an already similarly set section.
				 */
				if (ld->l_type == flp->set.l_type)
					return(rv);
				/* setup piece after end of (un)lock */
				td = flp->set;
				td.l_start = ld->l_end;
				tdp = tdi = flp;
				do {
					if (tdp->set.l_start < ld->l_start)
						tdi = tdp;
					else
						break;
				} while (tdp = tdp->flknext);
				if (insflck(flip, &td, tdi) == NULL)
					return(ENOSPC);
				if (regtyp == (S_MIDDLE|E_MIDDLE)) {
					/* setup piece before (un)lock */
					flp->set.l_end = ld->l_start;
					WAKEUP(flp);
					insrtp = flp;
				} else {
					insrtp = flp->flkprev;
					delflck(flip, flp);
				}
				nflp = NULL;
				break;
			case S_MIDDLE|E_END:
				/* don't bother if this is in the middle of
				 * an already similarly set section.
				 */
				if (ld->l_type == flp->set.l_type)
					return(rv);
				flp->set.l_end = ld->l_start;
				WAKEUP(flp);
				insrtp = flp;
				break;
			case S_MIDDLE|E_AFTER:
			case S_END|E_AFTER:
				if (ld->l_type == flp->set.l_type) {
					ld->l_start = flp->set.l_start;
					insrtp = flp->flkprev;
					delflck(flip, flp);
				} else {
					flp->set.l_end = ld->l_start;
					WAKEUP(flp);
					insrtp = flp;
				}
				break;
			case S_AFTER|E_AFTER:
				insrtp = flp;
				break;
			}
		} else {
			if (flp->set.l_start > ld->l_end)
				nflp = NULL;
		}
	}

	if (insrtflg) {
		if (flp = insrtp) {
			do {
				if (flp->set.l_start < ld->l_start)
					insrtp = flp;
				else
					break;
			} while (flp = flp->flknext);
		}
		if (insflck(flip, ld, insrtp) == NULL)
			rv = ENOSPC;
	}

	return (rv);
}

/* blocked checks whether a new lock (lckdat) would be
 * blocked by a previously set lock owned by another process.
 * When blocked is called, 'flp' should point
 * to the record from which the search should begin.
 * Insrt is set to point to the lock before which the new lock
 * is to be placed.
 */
static struct filock *
blocked(flp, lckdat, insrt)
struct filock *flp;
struct flock *lckdat;
struct filock **insrt;
{
	struct filock *f;

	*insrt = NULL;
	for (f = flp; f != NULL; f = f->flknext) {
		if (f->set.l_start < lckdat->l_start)
			*insrt = f;
		else
			break;
		if (f->set.l_pid == u.u_procp->p_pid) {
			if (lckdat->l_start <= f->set.l_end
			    && lckdat->l_end >= f->set.l_start) {
				*insrt = f;
				break;
			}
		} else	if (lckdat->l_start < f->set.l_end
			    && lckdat->l_end > f->set.l_start
			    && (f->set.l_type == F_WRLCK
				|| (f->set.l_type == F_RDLCK
				    && lckdat->l_type == F_WRLCK)))
				return(f);
	}

	for ( ; f != NULL; f = f->flknext) {
		if (lckdat->l_start < f->set.l_end
		    && lckdat->l_end > f->set.l_start
		    && f->set.l_pid != u.u_procp->p_pid
		    && (f->set.l_type == F_WRLCK
			|| (f->set.l_type == F_RDLCK && lckdat->l_type == F_WRLCK)))
			return(f);
		if (f->set.l_start > lckdat->l_end)
			break;
	}

	return(NULL);
}

/* locate overlapping file locks
 */
getflck(fp, lckdat)
struct file *fp;
struct flock *lckdat;
{
	register struct flino *flip;
	struct filock *found, *insrt = NULL;
	register int retval = 0;
	int inwhence;		/* whence of request */

	/* get file identifier and file lock list pointer if there is one */
	flip = findfid(fp);
	if (flip == NULL) {
		lckdat->l_type = F_UNLCK;
		return (0);
	}

	/* convert start to be relative to beginning of file */
	inwhence = lckdat->l_whence;
	if (retval=convoff(fp, lckdat, 0))
		return (retval);
	if (lckdat->l_len == 0)
		lckdat->l_end = MAXEND;
	else
		lckdat->l_end += lckdat->l_start;

	/* find overlapping lock */

	found = blocked(flip->fl_flck, lckdat, &insrt);
	if (found != NULL)
		*lckdat = found->set;
	else
		lckdat->l_type = F_UNLCK;
	freefid(flip);

	/* restore length */
	if (lckdat->l_end == MAXEND)
		lckdat->l_len = 0;
	else
		lckdat->l_len -= lckdat->l_start;

	retval = convoff(fp, lckdat, inwhence);
	return (retval);
}

/* clear and set file locks
 */
setflck(fp, lckdat, slpflg)
struct file *fp;
struct flock *lckdat;
int slpflg;
{
	register struct flino *flip;
	register struct filock *found, *sf;
	struct filock *insrt = NULL;
	register int retval = 0;
	int contflg = 0;

	/* check access permissions */
	if ((lckdat->l_type == F_RDLCK && (fp->f_flag&FREAD) == 0)
	    || (lckdat->l_type == F_WRLCK && (fp->f_flag&FWRITE) == 0))
		return (EBADF);
	
	/* convert start to be relative to beginning of file */
	if (retval=convoff(fp, lckdat, 0))
		return (retval);
	if (lckdat->l_len == 0)
		lckdat->l_end = MAXEND;
	else
		lckdat->l_end += lckdat->l_start;

	/* get or create a file/inode record lock header */
	flip = findfid(fp);
	if (flip == NULL) {
		if (lckdat->l_type == F_UNLCK)
			return (0);
		if ((flip=allocfid(fp)) == NULL)
			return (ENOLCK);
	}

	do {
		contflg = 0;
		switch (lckdat->l_type) {
		case F_RDLCK:
		case F_WRLCK:
			if ((found=blocked(flip->fl_flck, lckdat, &insrt)) == NULL)
				retval = flckadj(flip, insrt, lckdat);
			else if (slpflg) {
				/* do deadlock detection here */
				if (deadflck(found))
					retval = EDEADLK;
				else
					if ((sf=insflck(&sleeplcks, lckdat, NULL)) == NULL)
						retval = ENOSPC;
					else {
						found->stat.wakeflg++;
						sf->stat.blkpid = found->set.l_pid;
						SLEEP(found, PCATCH|(PZERO+1));
						contflg = 1;
						sf->stat.blkpid = 0;
						delflck(&sleeplcks, sf);
					}
			} else
				retval = EAGAIN;
			break;
		case F_UNLCK:
			/* removing a file record lock */
			retval = flckadj(flip, flip->fl_flck, lckdat);
			break;
		default:
			retval = EINVAL;	/* invalid lock type */
			break;
		}
	} while (contflg);
	freefid(flip);
	return(retval);
}

/* convoff - converts the given data (start, whence) to the
 * given whence.
 */
static int
convoff(fp, lckdat, whence)
struct file *fp;
struct flock *lckdat;
int whence;
{
	if (lckdat->l_whence == 1)
		lckdat->l_start += fp->f_un.f_offset;
	else if (lckdat->l_whence == 2)
		lckdat->l_start += fp->f_inode->i_size;
	else if (lckdat->l_whence != 0)
		return (EINVAL);
	if (lckdat->l_start < 0)
		return (EINVAL);
	if (whence == 1)
		lckdat->l_start -= fp->f_un.f_offset;
	else if (whence == 2)
		lckdat->l_start -= fp->f_inode->i_size;
	else if (whence != 0)
		return (EINVAL);
	lckdat->l_whence = whence;
	return (0);
}

/* deadflck does the deadlock detection for the given record */
static int
deadflck(flp)
struct filock *flp;
{
	register struct filock *blck, *sf;
	int blckpid;

	blck = flp;	/* current blocking lock pointer */
	blckpid = blck->set.l_pid;
	do {
		if (blckpid == u.u_procp->p_pid)
			return(1);
		/* if the blocking process is sleeping on a locked region,
		 * change the blocked lock to this one.
		 */
		for (sf = sleeplcks.fl_flck; sf != NULL; sf = sf->flknext) {
			if (blckpid == sf->set.l_pid) {
				blckpid = sf->stat.blkpid;
				break;
			}
		}
		blck = sf;
	} while (blck != NULL);
	return(0);
}

/* Clean up record locks left around by process (called in closef) */
cleanlocks(fp)
struct file *fp;
{
	register struct filock *flp, *nflp;
	register struct flino *flip;

	flip = findfid(fp);
	if (flip == NULL)
		return;

	for (flp=flip->fl_flck; flp!=NULL; flp=nflp) {
		nflp = flp->flknext;
		if (flp->set.l_pid == u.u_procp->p_pid)
			delflck(flip, flp);
	}
	freefid(flip);

	return;
}