[unix-history] / usr / src / sys / ufs / ffs / ufs_lockf.c

/*
 * Copyright (c) 1982, 1986, 1989 Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Scooter Morris at Genentech Inc.
 *
 * %sccs.include.redist.c%
 *
 *	@(#)ufs_lockf.c	7.1 (Berkeley) %G%
 */

#include "param.h"
#include "systm.h"
#include "user.h"
#include "kernel.h"
#include "file.h"
#include "proc.h"
#include "socketvar.h"
#include "socket.h"
#include "vnode.h"
#include "ioctl.h"
#include "tty.h"
#include "malloc.h"
#include "fcntl.h"
#include "../ufs/lockf.h"
#include "../ufs/quota.h"
#include "../ufs/inode.h"

#ifdef	LOCKF_DEBUG
int	lockf_debug = 0;
#endif /* LOCKF_DEBUG */

/*
 * Common code for ufs byte range locking
 */

/*
 * Add a lock to the list.  Upgrade or downgrade our locks, if
 * they conflict.
 */
struct lockf *
lf_addlock(lock)
	register struct lockf *lock;
{
	register struct lockf *lf = lock->lf_inode->i_lockf;
	struct lockf *lastlock = (struct lockf *)0;
	struct lockf *prev, *overlap, *ltmp;
	int ovcase;

	/*
	 * First, see if we overlap with anything.
	 */
	ovcase = lf_findoverlap(lf, lock, &prev, &overlap);
	/*
	 * Add the new lock
	 */
	if (prev != (struct lockf *)0)
		prev->lf_next = lock;
	else
		lock->lf_inode->i_lockf = lock;
	lock->lf_next = overlap;
	/*
	 * Skip over locks owned by other processes.
	 * Merge any locks that are owned by ourselves.
	 */
	for (;;) {
		for (;;) {
			/*
			 * If no overlap, we are done.
			 */
			if (ovcase == 0)
				return;
			lf = overlap->lf_next;
			if (overlap->lf_id == lock->lf_id)
				break;
			/*
			 * We overlap with another process.
			 * If it is a block, panic.
			 */
			if (lock->lf_type == F_WRLCK ||
			    overlap->lf_type == F_WRLCK)
				panic("blocked in addlock");
			ovcase = lf_findoverlap(lf, lock, &prev, &overlap);
		}
		/*
		 * Five cases:
		 *	1) overlap == lock
		 *	2) overlap contains lock
		 *	3) lock contains overlap
		 *	4) overlap starts before lock
		 *	5) overlap ends after lock
		 */
		switch (ovcase) {

		case 1: /* overlap == lock */
			/*
			 * Undo spurious addition of lock to list.
			 */
			if (prev != (struct lockf *)0)
				prev->lf_next = overlap;
			else
				lock->lf_inode->i_lockf = overlap;
			/*
			 * If downgrading lock, others may be
			 * able to acquire it.
			 */
			if (lock->lf_type == F_RDLCK &&
			    overlap->lf_type == F_WRLCK)
				lf_wakelock(overlap);
			overlap->lf_type = lock->lf_type;
			free(lock, M_LOCKF);
			return;

		case 2: /* overlap contains lock */
			/*
			 * Undo spurious addition of lock to list.
			 */
			if (prev != (struct lockf *)0)
				prev->lf_next = overlap;
			else
				lock->lf_inode->i_lockf = overlap;
			if (overlap->lf_type == lock->lf_type) {
				free(lock, M_LOCKF);
				return;
			}
			lf_split(overlap, lock);
			lf_wakelock(overlap);
			return;

		case 3: /* lock contains overlap */
			/*
			 * If downgrading lock, others may be able to
			 * acquire it, otherwise take the list.
			 */
			if (lock->lf_type == F_RDLCK &&
			    overlap->lf_type == F_WRLCK) {
				lf_wakelock(overlap);
			} else {
				ltmp = lock->lf_block;
				lock->lf_block = overlap->lf_block;
				lf_addblock(lock, ltmp);
			}
			/*
			 * Delete the overlap.
			 */
			lock->lf_next = overlap->lf_next;
			free(overlap, M_LOCKF);
			break;

		case 4: /* overlap starts before lock */
			/*
			 * Reverse lock and overlap on the list
			 */
			if (prev != (struct lockf *)0)
				prev->lf_next = overlap;
			else
				lock->lf_inode->i_lockf = overlap;
			lock->lf_next = overlap->lf_next;
			overlap->lf_next = lock;
			overlap->lf_end = lock->lf_start - 1;
			lf_wakelock(overlap);
			break;

		case 5: /* overlap ends after lock */
			overlap->lf_start = lock->lf_end + 1;
			lf_wakelock(overlap);
			return;
		}
		ovcase = lf_findoverlap(lf, lock, &prev, &overlap);
	}
	/* NOTREACHED */
}

/*
 * Walk the list of locks for an inode and
 * return the first blocking lock.
 */
struct lockf *
lf_getblock(lock)
	register struct lockf *lock;
{
	struct lockf *prev, *overlap, *lf = lock->lf_inode->i_lockf;
	int ovcase;

	while (ovcase = lf_findoverlap(lf, lock, &prev, &overlap)) {
		/*
		 * We've found an overlap, see if it blocks us
		 */
		if ((lock->lf_type == F_WRLCK || overlap->lf_type == F_WRLCK) &&
		    overlap->lf_id != lock->lf_id)
			return (overlap);
		/*
		 * Nope, point to the next one on the list and
		 * see if it blocks us
		 */
		lf = overlap->lf_next;
	}
	return ((struct lockf *)0);
}

/*
 * Walk the list of locks for an inode to
 * find an overlapping lock (if any).
 *
 * NOTE: this returns only the FIRST overlapping lock.  There
 *	 may be more than one.
 */
lf_findoverlap(list, lock, prev, overlap)
	struct lockf *list;
	struct lockf *lock;
	struct lockf **prev;
	struct lockf **overlap;
{
	register struct lockf *lf = list;
	off_t start, end;

	*prev = (struct lockf *) 0;
	*overlap = lf;
	if ((lock == (struct lockf *)0) || (lf == (struct lockf *)0))
		return (0);
#ifdef LOCKF_DEBUG
	if (lockf_debug & 1)
		lf_print("lf_findoverlap: looking for overlap in", lock);
#endif /* LOCKF_DEBUG */
	start = lock->lf_start;
	end = lock->lf_end;
	while (lf != (struct lockf *)0) {
#ifdef	LOCKF_DEBUG
		if (lockf_debug & 1)
			lf_print("\tchecking", lf);
#endif /* LOCKF_DEBUG */
		/*
		 * Have we gone far enough?
		 */
		if (end != -1 && lf->lf_start > end)
#ifdef	LOCKF_DEBUG
			if (lockf_debug & 1)
				print("no overlap\n");
#endif /* LOCKF_DEBUG */
			return (0);
		/*
		 * OK, find the overlap
		 *
		 * Five cases:
		 *	1) overlap == lock
		 *	2) overlap contains lock
		 *	3) lock contains overlap
		 *	4) overlap starts before lock
		 *	5) overlap ends after lock
		 */
		if ((lf->lf_start == start) && (lf->lf_end == end)) {
			/* Case 1 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				printf("overlap == lock\n"); break;
#endif /* LOCKF_DEBUG */
			return (1);
		} else if ((lf->lf_start <= start) &&
		    (end != -1) &&
		    ((lf->lf_end >= end) || (lf->lf_end == -1))) {
			/* Case 2 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				printf("overlap contains lock\n"); break;
#endif /* LOCKF_DEBUG */
			return (2);
		} else if ((start <= lf->lf_start) &&
		    (lf->lf_end != -1) &&
		    ((end == -1) || (end >= lf->lf_end))) {
			/* Case 3 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				printf("lock contains overlap\n"); break;
#endif /* LOCKF_DEBUG */
			return (3);
		} else if ((lf->lf_start < start) &&
			((lf->lf_end >= start) || (lf->lf_end == -1))) {
			/* Case 4 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				printf("overlap starts before lock\n"); break;
#endif /* LOCKF_DEBUG */
			return (4);
		} else if ((lf->lf_start > start) &&
			(end != -1) &&
			((lf->lf_end > end) || (lf->lf_end == -1))) {
			/* Case 5 */
#ifdef LOCKF_DEBUG
			if (lockf_debug & 1)
				printf("overlap ends after lock\n"); break;
#endif /* LOCKF_DEBUG */
			return (5);
		}
		*prev = lf;
		*overlap = lf = lf->lf_next;
	}
	/* No overlap */
#ifdef	LOCKF_DEBUG
	if (lockf_debug & 1)
		print("no overlap\n");
#endif /* LOCKF_DEBUG */
	return (0);
}

/*
 * Add a lock to the end of the blocked list.
 */
lf_addblock(lock, blocked)
	struct lockf *lock;
	struct lockf *blocked;
{
	register struct lockf *lf;

	if (lock == (struct lockf *)0)
		return;
	if ((lf = lock->lf_block) == (struct lockf *)0) {
		lock->lf_block = blocked;
		return;
	}
	while (lf->lf_block != (struct lockf *)0)
		lf = lf->lf_block;
	lf->lf_block = blocked;
	return;
}

/*
 * Combine two locks into a single lock
 */
lf_combine(lock1, lock2)
	struct lockf *lock1;
	struct lockf *lock2;
{
#ifdef LOCKF_DEBUG
	if (lockf_debug & 1) {
		lf_print("lf_combine", lock1);
		lf_print("combining with", lock2);
	}
#endif /* LOCKF_DEBUG */
	/*
	 * Sanity check
	 */
	if ( (lock1->lf_id != lock2->lf_id) ||
	     (lock1->lf_type != lock2->lf_type) )
		panic("lf_combine");
	if (lock1->lf_start > lock2->lf_start)
		lock1->lf_start = lock2->lf_start;
	if ((lock1->lf_end == -1) || (lock2->lf_end == -1))
		lock1->lf_end == -1;
	else if (lock1->lf_end < lock2->lf_end)
		lock1->lf_end = lock2->lf_end;
	/* Add the block lists together */
	lf_addblock(lock1, lock2->lf_block);
	free(lock2, M_LOCKF);
}

/*
 * Split a lock and a contained region into
 * three locks
 */
lf_split(lock1, lock2)
	register struct lockf *lock1;
	register struct lockf *lock2;
{
	register struct lockf *splitlock;

#ifdef LOCKF_DEBUG
	if (lockf_debug & 1) {
		lf_print("lf_split", lock1);
		lf_print("splitting from", lock2);
	}
#endif /* LOCKF_DEBUG */
	/*
	 * Make a new lock consisting of the last part of
	 * the encompassing lock
	 */
	MALLOC(splitlock, struct lockf *, sizeof *splitlock, M_LOCKF, M_WAITOK);
	bcopy((caddr_t)lock1, (caddr_t)splitlock, sizeof *splitlock);
	splitlock->lf_end = lock2->lf_end + 1;
	lock1->lf_end = lock2->lf_start - 1;
	/*
	 * OK, now link it in
	 */
	splitlock->lf_next = lock1->lf_next;
	lock2->lf_next = splitlock;
	lock1->lf_next = lock2;
}

/*
 * lf_remove: remove a lock (or a portion of a lock) from the lock list
 */
struct lockf *
lf_remove(lfun)
	register struct lockf *lfun;
{
	struct inode *ip = lfun->lf_inode;
	register struct lockf *lf = ip->i_lockf;
	struct lockf *blocklist = (struct lockf *)0;
	struct lockf *overlap, *prev;
	int ovcase;

	if (lf == (struct lockf *)0)
		return((struct lockf *)0);
#ifdef	LOCKF_DEBUG
	if (lockf_debug & 1)
		printf("lf_remove", lfun);
#endif	LOCKF_DEBUG
	while (ovcase = lf_findoverlap(lf, lfun, &prev, &overlap)) {
		/*
		 * Point to the next element for the loop
		 */
		lf = overlap->lf_next;
		/*
		 * Check to see if it is our lock.
		 */
		if (lfun->lf_id == overlap->lf_id) {
			/*
			 * Save the list of locks to be retried.
			 */
			if (blocklist == (struct lockf *)0)
				blocklist = overlap->lf_block;
			else
				lf_addblock(blocklist, overlap->lf_block);

			switch (ovcase) {

			case 1: /* overlap == lock */
				if (prev != (struct lockf *)0)
					prev->lf_next = overlap->lf_next;
				else
					ip->i_lockf = overlap->lf_next;
				free(overlap, M_LOCKF);
				return (blocklist);

			case 2: /* overlap contains lock: split it */
				lf_split(overlap, lfun);
				overlap->lf_next = lfun->lf_next;
				return (blocklist);

			case 3: /* lock contains overlap */
				if (prev != (struct lockf *)0)
					prev->lf_next = overlap->lf_next;
				else
					ip->i_lockf = overlap->lf_next;
				free(overlap, M_LOCKF);
				break;

			case 4: /* overlap starts before lock */
				overlap->lf_end = lfun->lf_start - 1;
				break;

			case 5: /* overlap ends after lock */
				overlap->lf_start = lfun->lf_end + 1;
				return (blocklist);
			}
		}
	}
	return (blocklist);
}

/*
 * Wakeup a blocklist
 */
lf_wakelock(blocklist)
	register struct lockf *blocklist;
{
        register struct lockf *wakelock;

        while (blocklist != (struct lockf *)0) {
                wakelock = blocklist;
                blocklist = blocklist->lf_block;
		wakelock->lf_block = (struct lockf *)0;
		wakelock->lf_next = (struct lockf *)0;
#ifdef LOCKF_DEBUG
		if (lockf_debug & 4)
			lf_print("ufs_wakelock: awakening", wakelock);
#endif /* LOCKF_DEBUG */
                wakeup((caddr_t)wakelock);
        }
}

#ifdef LOCKF_DEBUG
/*
 * Print out a lock.
 */
lf_print(tag, lock)
	char *tag;
	register lockf *lock;
{
	
	printf("%s: lock 0x%X for proc %d in ino %d on dev <%d, %d>, ",
		tag, lock, lock->lp_proc->p_pid, lock->lf_inode->i_number,
		major(lock->lf_inode->i_dev), minor(lock->lf_inode->i_dev));
	printf("type %s, start %d, end %d\n",
		lock->lf_type == F_RDLCK ? "shared" :
		lock->lf_type == F_WRLCK ? "exclusive" :
		"unknown", start, end);
}
#endif /* LOCKF_DEBUG */
Commit	Line	Data
f3e2d1ca KM	1	/*
	2	* Copyright (c) 1982, 1986, 1989 Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* This code is derived from software contributed to Berkeley by
	6	* Scooter Morris at Genentech Inc.
	7	*
	8	* %sccs.include.redist.c%
	9	*
	10	* @(#)ufs_lockf.c 7.1 (Berkeley) %G%
	11	*/
	12
	13	#include "param.h"
	14	#include "systm.h"
	15	#include "user.h"
	16	#include "kernel.h"
	17	#include "file.h"
	18	#include "proc.h"
	19	#include "socketvar.h"
	20	#include "socket.h"
	21	#include "vnode.h"
	22	#include "ioctl.h"
	23	#include "tty.h"
	24	#include "malloc.h"
	25	#include "fcntl.h"
	26	#include "../ufs/lockf.h"
	27	#include "../ufs/quota.h"
	28	#include "../ufs/inode.h"
	29
	30	#ifdef LOCKF_DEBUG
	31	int lockf_debug = 0;
	32	#endif /* LOCKF_DEBUG */
	33
	34	/*
	35	* Common code for ufs byte range locking
	36	*/
	37
	38	/*
	39	* Add a lock to the list. Upgrade or downgrade our locks, if
	40	* they conflict.
	41	*/
	42	struct lockf *
	43	lf_addlock(lock)
	44	register struct lockf *lock;
	45	{
	46	register struct lockf *lf = lock->lf_inode->i_lockf;
	47	struct lockf lastlock = (struct lockf )0;
	48	struct lockf prev, overlap, *ltmp;
	49	int ovcase;
	50
	51	/*
	52	* First, see if we overlap with anything.
	53	*/
	54	ovcase = lf_findoverlap(lf, lock, &prev, &overlap);
	55	/*
	56	* Add the new lock
	57	*/
	58	if (prev != (struct lockf *)0)
	59	prev->lf_next = lock;
	60	else
	61	lock->lf_inode->i_lockf = lock;
	62	lock->lf_next = overlap;
	63	/*
	64	* Skip over locks owned by other processes.
65	* Merge any locks that are owned by ourselves.
66	*/
67	for (;;) {
68	for (;;) {
69	/*
70	* If no overlap, we are done.
71	*/
72	if (ovcase == 0)
73	return;
74	lf = overlap->lf_next;
75	if (overlap->lf_id == lock->lf_id)
76	break;
77	/*
78	* We overlap with another process.
79	* If it is a block, panic.
80	*/
81	if (lock->lf_type == F_WRLCK \|\|
82	overlap->lf_type == F_WRLCK)
83	panic("blocked in addlock");
84	ovcase = lf_findoverlap(lf, lock, &prev, &overlap);
85	}
86	/*
87	* Five cases:
88	* 1) overlap == lock
89	* 2) overlap contains lock
90	* 3) lock contains overlap
91	* 4) overlap starts before lock
92	* 5) overlap ends after lock
93	*/
94	switch (ovcase) {
95
96	case 1: /* overlap == lock */
97	/*
98	* Undo spurious addition of lock to list.
99	*/
100	if (prev != (struct lockf *)0)
101	prev->lf_next = overlap;
102	else
103	lock->lf_inode->i_lockf = overlap;
104	/*
105	* If downgrading lock, others may be
106	* able to acquire it.
107	*/
108	if (lock->lf_type == F_RDLCK &&
109	overlap->lf_type == F_WRLCK)
110	lf_wakelock(overlap);
111	overlap->lf_type = lock->lf_type;
112	free(lock, M_LOCKF);
113	return;
114
115	case 2: /* overlap contains lock */
116	/*
117	* Undo spurious addition of lock to list.
118	*/
119	if (prev != (struct lockf *)0)
120	prev->lf_next = overlap;
121	else
122	lock->lf_inode->i_lockf = overlap;
123	if (overlap->lf_type == lock->lf_type) {
124	free(lock, M_LOCKF);
125	return;
126	}
127	lf_split(overlap, lock);
128	lf_wakelock(overlap);
129	return;
130
131	case 3: /* lock contains overlap */
132	/*
133	* If downgrading lock, others may be able to
134	* acquire it, otherwise take the list.
135	*/
136	if (lock->lf_type == F_RDLCK &&
137	overlap->lf_type == F_WRLCK) {
138	lf_wakelock(overlap);
139	} else {
140	ltmp = lock->lf_block;
141	lock->lf_block = overlap->lf_block;
142	lf_addblock(lock, ltmp);
143	}
144	/*
145	* Delete the overlap.
146	*/
147	lock->lf_next = overlap->lf_next;
148	free(overlap, M_LOCKF);
149	break;
150
151	case 4: /* overlap starts before lock */
152	/*
153	* Reverse lock and overlap on the list
154	*/
155	if (prev != (struct lockf *)0)
156	prev->lf_next = overlap;
157	else
158	lock->lf_inode->i_lockf = overlap;
159	lock->lf_next = overlap->lf_next;
160	overlap->lf_next = lock;
161	overlap->lf_end = lock->lf_start - 1;
162	lf_wakelock(overlap);
163	break;
164
165	case 5: /* overlap ends after lock */
166	overlap->lf_start = lock->lf_end + 1;
167	lf_wakelock(overlap);
168	return;
169	}
170	ovcase = lf_findoverlap(lf, lock, &prev, &overlap);
171	}
172	/* NOTREACHED */
173	}
174
175	/*
176	* Walk the list of locks for an inode and
177	* return the first blocking lock.
178	*/
179	struct lockf *
180	lf_getblock(lock)
181	register struct lockf *lock;
182	{
183	struct lockf prev, overlap, *lf = lock->lf_inode->i_lockf;
184	int ovcase;
185
186	while (ovcase = lf_findoverlap(lf, lock, &prev, &overlap)) {
187	/*
188	* We've found an overlap, see if it blocks us
189	*/
190	if ((lock->lf_type == F_WRLCK \|\| overlap->lf_type == F_WRLCK) &&
191	overlap->lf_id != lock->lf_id)
192	return (overlap);
193	/*
194	* Nope, point to the next one on the list and
195	* see if it blocks us
196	*/
197	lf = overlap->lf_next;
198	}
199	return ((struct lockf *)0);
200	}
201
202	/*
203	* Walk the list of locks for an inode to
204	* find an overlapping lock (if any).
205	*
206	* NOTE: this returns only the FIRST overlapping lock. There
207	* may be more than one.
208	*/
209	lf_findoverlap(list, lock, prev, overlap)
210	struct lockf *list;
211	struct lockf *lock;
212	struct lockf **prev;
213	struct lockf **overlap;
214	{
215	register struct lockf *lf = list;
216	off_t start, end;
217
218	prev = (struct lockf ) 0;
219	*overlap = lf;
220	if ((lock == (struct lockf )0) \|\| (lf == (struct lockf )0))
221	return (0);
222	#ifdef LOCKF_DEBUG
223	if (lockf_debug & 1)
224	lf_print("lf_findoverlap: looking for overlap in", lock);
225	#endif /* LOCKF_DEBUG */
226	start = lock->lf_start;
227	end = lock->lf_end;
228	while (lf != (struct lockf *)0) {
229	#ifdef LOCKF_DEBUG
230	if (lockf_debug & 1)
231	lf_print("\tchecking", lf);
232	#endif /* LOCKF_DEBUG */
233	/*
234	* Have we gone far enough?
235	*/
236	if (end != -1 && lf->lf_start > end)
237	#ifdef LOCKF_DEBUG
238	if (lockf_debug & 1)
239	print("no overlap\n");
240	#endif /* LOCKF_DEBUG */
241	return (0);
242	/*
243	* OK, find the overlap
244	*
245	* Five cases:
246	* 1) overlap == lock
247	* 2) overlap contains lock
248	* 3) lock contains overlap
249	* 4) overlap starts before lock
250	* 5) overlap ends after lock
251	*/
252	if ((lf->lf_start == start) && (lf->lf_end == end)) {
253	/* Case 1 */
254	#ifdef LOCKF_DEBUG
255	if (lockf_debug & 1)
256	printf("overlap == lock\n"); break;
257	#endif /* LOCKF_DEBUG */
258	return (1);
259	} else if ((lf->lf_start <= start) &&
260	(end != -1) &&
261	((lf->lf_end >= end) \|\| (lf->lf_end == -1))) {
262	/* Case 2 */
263	#ifdef LOCKF_DEBUG
264	if (lockf_debug & 1)
265	printf("overlap contains lock\n"); break;
266	#endif /* LOCKF_DEBUG */
267	return (2);
268	} else if ((start <= lf->lf_start) &&
269	(lf->lf_end != -1) &&
270	((end == -1) \|\| (end >= lf->lf_end))) {
271	/* Case 3 */
272	#ifdef LOCKF_DEBUG
273	if (lockf_debug & 1)
274	printf("lock contains overlap\n"); break;
275	#endif /* LOCKF_DEBUG */
276	return (3);
277	} else if ((lf->lf_start < start) &&
278	((lf->lf_end >= start) \|\| (lf->lf_end == -1))) {
279	/* Case 4 */
280	#ifdef LOCKF_DEBUG
281	if (lockf_debug & 1)
282	printf("overlap starts before lock\n"); break;
283	#endif /* LOCKF_DEBUG */
284	return (4);
285	} else if ((lf->lf_start > start) &&
286	(end != -1) &&
287	((lf->lf_end > end) \|\| (lf->lf_end == -1))) {
288	/* Case 5 */
289	#ifdef LOCKF_DEBUG
290	if (lockf_debug & 1)
291	printf("overlap ends after lock\n"); break;
292	#endif /* LOCKF_DEBUG */
293	return (5);
294	}
295	*prev = lf;
296	*overlap = lf = lf->lf_next;
297	}
298	/* No overlap */
299	#ifdef LOCKF_DEBUG
300	if (lockf_debug & 1)
301	print("no overlap\n");
302	#endif /* LOCKF_DEBUG */
303	return (0);
304	}
305
306	/*
307	* Add a lock to the end of the blocked list.
308	*/
309	lf_addblock(lock, blocked)
310	struct lockf *lock;
311	struct lockf *blocked;
312	{
313	register struct lockf *lf;
314
315	if (lock == (struct lockf *)0)
316	return;
317	if ((lf = lock->lf_block) == (struct lockf *)0) {
318	lock->lf_block = blocked;
319	return;
320	}
321	while (lf->lf_block != (struct lockf *)0)
322	lf = lf->lf_block;
323	lf->lf_block = blocked;
324	return;
325	}
326
327	/*
328	* Combine two locks into a single lock
329	*/
330	lf_combine(lock1, lock2)
331	struct lockf *lock1;
332	struct lockf *lock2;
333	{
334	#ifdef LOCKF_DEBUG
335	if (lockf_debug & 1) {
336	lf_print("lf_combine", lock1);
337	lf_print("combining with", lock2);
338	}
339	#endif /* LOCKF_DEBUG */
340	/*
341	* Sanity check
342	*/
343	if ( (lock1->lf_id != lock2->lf_id) \|\|
344	(lock1->lf_type != lock2->lf_type) )
345	panic("lf_combine");
346	if (lock1->lf_start > lock2->lf_start)
347	lock1->lf_start = lock2->lf_start;
348	if ((lock1->lf_end == -1) \|\| (lock2->lf_end == -1))
349	lock1->lf_end == -1;
350	else if (lock1->lf_end < lock2->lf_end)
351	lock1->lf_end = lock2->lf_end;
352	/* Add the block lists together */
353	lf_addblock(lock1, lock2->lf_block);
354	free(lock2, M_LOCKF);
355	}
356
357	/*
358	* Split a lock and a contained region into
359	* three locks
360	*/
361	lf_split(lock1, lock2)
362	register struct lockf *lock1;
363	register struct lockf *lock2;
364	{
365	register struct lockf *splitlock;
366
367	#ifdef LOCKF_DEBUG
368	if (lockf_debug & 1) {
369	lf_print("lf_split", lock1);
370	lf_print("splitting from", lock2);
371	}
372	#endif /* LOCKF_DEBUG */
373	/*
374	* Make a new lock consisting of the last part of
375	* the encompassing lock
376	*/
377	MALLOC(splitlock, struct lockf , sizeof splitlock, M_LOCKF, M_WAITOK);
378	bcopy((caddr_t)lock1, (caddr_t)splitlock, sizeof *splitlock);
379	splitlock->lf_end = lock2->lf_end + 1;
380	lock1->lf_end = lock2->lf_start - 1;
381	/*
382	* OK, now link it in
383	*/
384	splitlock->lf_next = lock1->lf_next;
385	lock2->lf_next = splitlock;
386	lock1->lf_next = lock2;
387	}
388
389	/*
390	* lf_remove: remove a lock (or a portion of a lock) from the lock list
391	*/
392	struct lockf *
393	lf_remove(lfun)
394	register struct lockf *lfun;
395	{
396	struct inode *ip = lfun->lf_inode;
397	register struct lockf *lf = ip->i_lockf;
398	struct lockf blocklist = (struct lockf )0;
399	struct lockf overlap, prev;
400	int ovcase;
401
402	if (lf == (struct lockf *)0)
403	return((struct lockf *)0);
404	#ifdef LOCKF_DEBUG
405	if (lockf_debug & 1)
406	printf("lf_remove", lfun);
407	#endif LOCKF_DEBUG
408	while (ovcase = lf_findoverlap(lf, lfun, &prev, &overlap)) {
409	/*
410	* Point to the next element for the loop
411	*/
412	lf = overlap->lf_next;
413	/*
414	* Check to see if it is our lock.
415	*/
416	if (lfun->lf_id == overlap->lf_id) {
417	/*
418	* Save the list of locks to be retried.
419	*/
420	if (blocklist == (struct lockf *)0)
421	blocklist = overlap->lf_block;
422	else
423	lf_addblock(blocklist, overlap->lf_block);
424
425	switch (ovcase) {
426
427	case 1: /* overlap == lock */
428	if (prev != (struct lockf *)0)
429	prev->lf_next = overlap->lf_next;
430	else
431	ip->i_lockf = overlap->lf_next;
432	free(overlap, M_LOCKF);
433	return (blocklist);
434
435	case 2: /* overlap contains lock: split it */
436	lf_split(overlap, lfun);
437	overlap->lf_next = lfun->lf_next;
438	return (blocklist);
439
440	case 3: /* lock contains overlap */
441	if (prev != (struct lockf *)0)
442	prev->lf_next = overlap->lf_next;
443	else
444	ip->i_lockf = overlap->lf_next;
445	free(overlap, M_LOCKF);
446	break;
447
448	case 4: /* overlap starts before lock */
449	overlap->lf_end = lfun->lf_start - 1;
450	break;
451
452	case 5: /* overlap ends after lock */
453	overlap->lf_start = lfun->lf_end + 1;
454	return (blocklist);
455	}
456	}
457	}
458	return (blocklist);
459	}
460
461	/*
462	* Wakeup a blocklist
463	*/
464	lf_wakelock(blocklist)
465	register struct lockf *blocklist;
466	{
467	register struct lockf *wakelock;
468
469	while (blocklist != (struct lockf *)0) {
470	wakelock = blocklist;
471	blocklist = blocklist->lf_block;
472	wakelock->lf_block = (struct lockf *)0;
473	wakelock->lf_next = (struct lockf *)0;
474	#ifdef LOCKF_DEBUG
475	if (lockf_debug & 4)
476	lf_print("ufs_wakelock: awakening", wakelock);
477	#endif /* LOCKF_DEBUG */
478	wakeup((caddr_t)wakelock);
479	}
480	}
481
482	#ifdef LOCKF_DEBUG
483	/*
484	* Print out a lock.
485	*/
486	lf_print(tag, lock)
487	char *tag;
488	register lockf *lock;
489	{
490
491	printf("%s: lock 0x%X for proc %d in ino %d on dev <%d, %d>, ",
492	tag, lock, lock->lp_proc->p_pid, lock->lf_inode->i_number,
493	major(lock->lf_inode->i_dev), minor(lock->lf_inode->i_dev));
494	printf("type %s, start %d, end %d\n",
495	lock->lf_type == F_RDLCK ? "shared" :
496	lock->lf_type == F_WRLCK ? "exclusive" :
497	"unknown", start, end);
498	}
499	#endif /* LOCKF_DEBUG */