#ifdef  SCCS_ID
static char SCCS_ID [] = "@(#)lockf.c    	3.3	 19:29:07 - 83/04/07 ";
#endif  SCCS_ID
/*
 * file lock routines
 * John Bass, PO Box 1223, San Luis Obispo, CA 93401
 * original design spring 1976, CalPoly, San Luis Obispo
 * Deadlock idea from Ed Grudzien at Basys April 1980
 * extensions fall 1980, Onyx Systems Inc., San Jose
 */
#include <sys/param.h>
#include <sys/inode.h>
#include <sys/file.h>
#include <sys/proc.h>
#include <sys/dir.h>
#include <sys/user.h>

#define MAXSIZE (long)(1L<<30)  /* number larger than any request */
/*
 * locking -- handles syscall requests
 */

locking() {
        struct file *fp;
        struct inode *ip;
        int foo;
        /*
         * define order and type of syscall args
         */
        register struct a {
                int     fdes;
                int     flag;
                off_t   size;
                } *uap;
        register struct locklist *cl, *nl;
        off_t   LB, UB;

	uap = (struct a *)u.u_ap;
        /*
         * check for valid open file
         */
        fp = getf(uap->fdes);
        if(fp == NULL) return;
        ip = fp->f_inode;
        if ((ip->i_flag&IFMT) == IFDIR) {
                u.u_error = EACCES;
                return;
        }

        /*
         * validate ranges
         * kludge for zero length
         */
        LB = fp->f_un.f_offset;
        if( uap->size ) {
                UB = LB + uap->size;
                if(UB <= 0) UB = MAXSIZE;
        }
        else UB = MAXSIZE;

        /*
         * test for unlock request
         */
        if(uap->flag == 0) {
                /*
                 * starting at list head scan
                 * for locks in the range by
                 * this process
                 */
                cl = &ip->i_locklist;   /* note addr is pointer in inode */
                while(nl = cl->ll_link) {
                        /*
                         * if not by this process skip to next lock
                         */
                        if(nl->ll_proc != u.u_procp) {
                                cl = nl;
                                continue;
                        }
                        /*
                         * check for locks in proper range
                         */
                        if( UB <= nl->ll_start )
                                break;
                        if( nl->ll_end <= LB ) {
                                cl = nl;
                                continue;
                        }
                        /*
                         * for locks fully contained within
                         * requested range, just delete the item
                         */
                        if( LB <= nl->ll_start && nl->ll_end <= UB) {
                                cl->ll_link = nl->ll_link;
                                lockfree(nl);
                                continue;
                        }
                        /*
                         * if some one is sleeping on this lock
                         * do a wakeup, we may free the region
                         * being slept on
                         */
                        if(nl->ll_flags & IWANT) {
                                nl->ll_flags &= ~IWANT;
                                wakeup(nl);
                        }
                        /*
                         * middle section is being removed
                         * add new lock for last section
                         * modify existing lock for first section.
                         * if no locks, return in error
                         */
                        if( nl->ll_start < LB && UB < nl->ll_end) {
                                if( lockadd(nl,UB,nl->ll_end) ) return;
                                nl->ll_end = LB;
                                break;
                        }
                        /*
                         * first section is being deleted
                         * just move starting point up
                         */
                        if( LB <= nl->ll_start && UB < nl->ll_end) {
                                nl->ll_start = UB;
                                break;
                        }
                        /*
                         * must be deleting last part of this section
                         * move ending point down
                         * continue looking for locks covered by upper
                         * limit of unlock range
                         */
                        nl->ll_end = LB;
                        cl = nl;
                }
                /*
                 * end of scan for unlock request
                 */
                return;
        }
        /*
         * request must be a lock of some kind
         * check to see if the region is lockable by this
         * process
         */
        if(locked(uap->flag, ip, LB, UB))return;
        cl = &ip->i_locklist;   /* note addr is pointer in inode */
        /*
         * simple case, no existing locks, simply add new lock
         */
        if( (nl=cl->ll_link) == NULL ) {
                lockadd(cl, LB, UB);
                return;
        }
        /*
         * simple case, lock is before existing locks,
         * simply insert at head of list
         */
        if( UB < nl->ll_start ) {
                lockadd(cl,LB,UB);
                return;
        }
        /*
         * ending range of lock is same as start of lock by
         * another process, simply insert at head of list
         */
        if( UB <= nl->ll_start && u.u_procp != nl->ll_proc ) {
                lockadd(cl, LB, UB);
                return;
        }
        /*
         * request range overlaps with begining of first request
         * modify starting point in lock to include requested region
         */
        if( UB >= nl->ll_start && LB < nl->ll_start ) {
                nl->ll_start = LB;
        }
        /*
         * scan thru remaining locklist
         */
        cl = nl;
        do {
                /*
                 * actions for requests at end of list
                 */
                if( ( nl = cl->ll_link ) == NULL ) {
                        /*
                         * request overlaps tail of last entry
                         * extend end point
                         */
                        if( LB <= cl->ll_end && u.u_procp == cl->ll_proc ) {
                                if( UB > cl->ll_end ) cl->ll_end = UB;
                                return;
                        }
                        /*
                         * otherwise add new entry
                         */
                        lockadd(cl, LB, UB);
                        return;
                }
                /*
                 * if more locks in range skip to next
                 * otherwise stop scan
                 */
                if( nl->ll_start < LB ) {
                        cl = nl;
                }
                else {
                        break;
                }
        } while(foo=1); /* compiler bug for do{}while(constant) */
        /*
         * if upper bound is fully resolved were done
         * otherwise fix end of last entry or add new entry
         */
        if(UB <= cl->ll_end) return;
        if(LB <= cl->ll_end && u.u_procp == cl->ll_proc) cl->ll_end = UB;
        else {
                if( lockadd(cl, LB, UB) ) return;
                cl = cl->ll_link;
        }
        /*
         * end point set above may overlap later entries
         * if so delete or modify them to perform the compaction
         */
        while( (nl=cl->ll_link) != NULL)  {
                /*
                 * if we found lock by another process we must
                 * be done since we validated the range above
                 */
                if(u.u_procp != nl->ll_proc) return;
                /*
                 * if the new endpoint no longer overlaps were done
                 */
                if(cl->ll_end < nl->ll_start) return;
                /*
                 * if the new range overlaps the first part of the
                 * next lock, take its end point
                 * and delete the next lock
                 * we should be done
                 */
                if(cl->ll_end <= nl->ll_end) {
                        cl->ll_end = nl->ll_end;
                        cl->ll_link = nl->ll_link;
                        lockfree(nl);
                        return;
                }
                /*
                 * the next lock is fully included in the new range
                 * so it may be deleted
                 */
                cl->ll_link = nl->ll_link;
                lockfree(nl);
        }
}
/*
 * locked -- routine to scan locks and check for a locked condition
 */
locked(flag, ip, LB, UB)
register struct inode *ip;
off_t   LB, UB;
{
        register struct locklist *nl = ip->i_locklist;

        /*
         * scan list while locks are in requested range
         */
        while(nl != NULL && nl->ll_start < UB) {
                /*
                 * skip locks for this process
                 * and those out of range
                 */
                if( nl->ll_proc == u.u_procp || nl->ll_end <= LB) {
                        nl = nl->ll_link;
                        if(nl == NULL) return(NULL);
                        continue;
                }
                /*
                 * must have found lock by another process
                 * if request is to test only, then exit with
                 * error code
                 */
                if(flag>1) {
                        u.u_error = EACCES;
                        return(1);
                }
                /*
                 * will need to sleep on lock, check for deadlock first
                 * abort on error
                 */
                if(deadlock(nl) != NULL) return(1);
                /*
                 * post want flag to get awoken
                 * then sleep till lock is released
                 */
                nl->ll_flags |= IWANT;
                sleep( (caddr_t)nl, PSLEP);
                /*
                 * set scan back to begining to catch
                 * any new areas locked
                 * or a partial delete
                 */
                nl = ip->i_locklist;
                /*
                 * abort if any errors
                 */
                if(u.u_error) return(1);
        }
        return(NULL);
}

/*
 * deadlock -- routine to follow chain of locks and proc table entries
 *              to find deadlocks on file locks.
 */

deadlock(lp)
register struct locklist *lp;
{
        register struct locklist *nl;

        /*
         * scan while the process owning the lock is sleeping
         */
        while(lp->ll_proc->p_stat == SSLEEP) {
                /*
                 * if the object the process is sleeping on is
                 * NOT in the locktable every thing is ok
                 * fall out of loop and return NULL
                 */
                nl = lp->ll_proc->p_wchan;
                if( nl < &locklist[0] || nl >= &locklist[NFLOCKS] )
                        break;
                /*
                 * the object was a locklist entry
                 * if the owner of that entry is this
                 * process then a deadlock would occur
                 * set error exit and return
                 */
                if(nl->ll_proc == u.u_procp) {
                        u.u_error = EDEADLOCK;
                        return(nl);
                }
                /*
                 * the object was a locklist entry
                 * owned by some other process
                 * continue the scan with that process
                 */
                lp = nl;
        }
        return(NULL);
}

/*
 * unlock -- called by close to release all locks for this process
 */

unlock(ip)
register struct inode *ip;
{
        register struct locklist *nl;
        register struct locklist *cl;

        if(cl = &ip->i_locklist)
                while( (nl = cl->ll_link) != NULL) {
                        if(nl->ll_proc == u.u_procp) {
                                cl->ll_link = nl->ll_link;
                                lockfree(nl);
                        }
                        else cl = nl;
                }
}

/*
 * lockalloc -- allocates free list, returns free lock items
 */
struct locklist *
lockalloc(){
        register struct locklist *fl = &locklist[0];
        register struct locklist *nl;

        /*
         * if first entry has never been used
         * link the locklist table into the freelist
         */
        if(fl->ll_proc == NULL) {
                fl->ll_proc = &proc[0];
                for(nl= &locklist[1]; nl < &locklist[NFLOCKS]; nl++) {
                        lockfree(nl);
                }
        }
        /*
         * if all the locks are used error exit
         */
        if( (nl=fl->ll_link) == NULL) {
                u.u_error = EDEADLOCK;
                return(NULL);
        }
        /*
         * return the next lock on the list
         */
        fl->ll_link = nl->ll_link;
        nl->ll_link = NULL;
        return(nl);
}

/*
 * lockfree -- returns a lock item to the free list
 */

lockfree(lp)
register struct locklist *lp;
{
        register struct locklist *fl = &locklist[0];

        /*
         * if some process is sleeping on this lock
         * wake them up
         */
        if(lp->ll_flags & IWANT) {
                lp->ll_flags &= ~IWANT;
                wakeup(lp);
        }
        /*
         * add the lock into the free list
         */
        lp->ll_link = fl->ll_link;
        fl->ll_link = lp;
}

/*
 * lockadd -- routine to add item to list
 */
lockadd(cl,LB,UB)
register struct locklist *cl;
off_t LB,UB;
{
        register struct locklist *nl;

        /*
         * get a lock, return if none available
         */
        nl = lockalloc();
        if(nl == NULL) {
                return(1);
        }
        /*
         * link the new entry into list at current spot
         * fill in the data from the args
         */
        nl->ll_link = cl->ll_link;
        cl->ll_link = nl;
        nl->ll_proc = u.u_procp;
        nl->ll_start = LB;
        nl->ll_end = UB;
        return(0);
}
#if debugging
/*
******************************************************************************
** the following code is the user state test fixture for the locking code ****
******************************************************************************
*/

#define TESTMAX 10
struct proc proc[TESTMAX];
struct user u;
struct locklist locklist[NFLOCKS];
struct file file[TESTMAX];
struct inode inode[TESTMAX];

main(){
        int val;
        register struct a {
                int     fdes;
                char    flag;
                off_t   size;
                } *uap = (struct a *)u.u_ap;
        while(1) {
                printf("proc    fdes    flag    offset  size:\n");
                scanf("%d",&val); u.u_procp = val;
                scanf("%d",&val); uap->fdes = val;
                scanf("%d",&val); uap->flag = val;
                scanf("%d",&val); file[uap->fdes].f_un.f_offset = val;
                scanf("%d",&val); uap->size = val;

                if(uap->flag > 2) exit(0);

                u.u_procp = &proc[(int)u.u_procp];
                u.u_error = NULL;
                locking();
                if(u.u_error) printf("\n****error is %d0,u.u_error);
                prntlocks(file[uap->fdes].f_inode);
        }
}
sleep(a,b) {
        printf("sleeping on (%x)\n",a);
        u.u_procp->p_wchan = a;
        u.u_procp->p_stat = SSLEEP;
        u.u_error = 99;
}
wakeup(a)
{
        register struct proc *p;

        for(p=proc; p < &proc[TESTMAX]; p++)
                if(p->p_wchan == a) {
                        p->p_wchan = 0;
                        p->p_stat = 0;
                        printf("process(%d) awake\n",p-&proc[0]);
                }
}
getf(a){
        file[a].f_inode = &inode[a];
        return(&file[a]);
}
prntlocks(ip){
        register struct locklist *ll;
        register struct proc *p;

        for(ll=ip->i_locklist; ll; ll = ll->ll_link)
                printf("ll(%x) ll_link(%x) ll_procp(%d) ll_lb(%D) ll_UB(%D)\n",
                        ll,
                        ll->ll_link,
                        ll->ll_proc - &proc[0],
                        ll->ll_start,
                        ll->ll_end);
        for(p=proc; p < maxproc; p++)
                if(p->p_stat == SSLEEP && p->p_wchan >= locklist &&
                        p->p_wchan < &locklist[NFLOCKS])
                        printf("proc(%d) sleeping\n",p-&proc[0]);
}
#endif
