2 * Copyright (c) 2009 Konstantin Belousov <kib@FreeBSD.org>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice unmodified, this list of conditions, and the following
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 #include <sys/cdefs.h>
28 __FBSDID("$FreeBSD$");
30 #include <sys/param.h>
31 #include <sys/kernel.h>
33 #include <sys/mutex.h>
35 #include <sys/rangelock.h>
36 #include <sys/systm.h>
41 TAILQ_ENTRY(rl_q_entry
) rl_q_link
;
42 off_t rl_q_start
, rl_q_end
;
46 static uma_zone_t rl_entry_zone
;
49 rangelock_sys_init(void)
52 rl_entry_zone
= uma_zcreate("rl_entry", sizeof(struct rl_q_entry
),
53 NULL
, NULL
, NULL
, NULL
, UMA_ALIGN_PTR
, 0);
55 SYSINIT(vfs
, SI_SUB_LOCK
, SI_ORDER_ANY
, rangelock_sys_init
, NULL
);
57 static struct rl_q_entry
*
61 return (uma_zalloc(rl_entry_zone
, M_WAITOK
));
65 rlqentry_free(struct rl_q_entry
*rleq
)
68 uma_zfree(rl_entry_zone
, rleq
);
72 rangelock_init(struct rangelock
*lock
)
75 TAILQ_INIT(&lock
->rl_waiters
);
76 lock
->rl_currdep
= NULL
;
80 rangelock_destroy(struct rangelock
*lock
)
83 KASSERT(TAILQ_EMPTY(&lock
->rl_waiters
), ("Dangling waiters"));
87 * Two entries are compatible if their ranges do not overlap, or both
88 * entries are for read.
91 ranges_overlap(const struct rl_q_entry
*e1
,
92 const struct rl_q_entry
*e2
)
95 if (e1
->rl_q_start
< e2
->rl_q_end
&& e1
->rl_q_end
> e2
->rl_q_start
)
101 * Recalculate the lock->rl_currdep after an unlock.
104 rangelock_calc_block(struct rangelock
*lock
)
106 struct rl_q_entry
*entry
, *nextentry
, *entry1
;
108 for (entry
= lock
->rl_currdep
; entry
!= NULL
; entry
= nextentry
) {
109 nextentry
= TAILQ_NEXT(entry
, rl_q_link
);
110 if (entry
->rl_q_flags
& RL_LOCK_READ
) {
111 /* Reads must not overlap with granted writes. */
112 for (entry1
= TAILQ_FIRST(&lock
->rl_waiters
);
113 !(entry1
->rl_q_flags
& RL_LOCK_READ
);
114 entry1
= TAILQ_NEXT(entry1
, rl_q_link
)) {
115 if (ranges_overlap(entry
, entry1
))
119 /* Write must not overlap with any granted locks. */
120 for (entry1
= TAILQ_FIRST(&lock
->rl_waiters
);
122 entry1
= TAILQ_NEXT(entry1
, rl_q_link
)) {
123 if (ranges_overlap(entry
, entry1
))
127 /* Move grantable write locks to the front. */
128 TAILQ_REMOVE(&lock
->rl_waiters
, entry
, rl_q_link
);
129 TAILQ_INSERT_HEAD(&lock
->rl_waiters
, entry
, rl_q_link
);
132 /* Grant this lock. */
133 entry
->rl_q_flags
|= RL_LOCK_GRANTED
;
137 lock
->rl_currdep
= entry
;
141 rangelock_unlock_locked(struct rangelock
*lock
, struct rl_q_entry
*entry
,
145 MPASS(lock
!= NULL
&& entry
!= NULL
&& ilk
!= NULL
);
146 mtx_assert(ilk
, MA_OWNED
);
147 KASSERT(entry
!= lock
->rl_currdep
, ("stuck currdep"));
149 TAILQ_REMOVE(&lock
->rl_waiters
, entry
, rl_q_link
);
150 rangelock_calc_block(lock
);
152 if (curthread
->td_rlqe
== NULL
)
153 curthread
->td_rlqe
= entry
;
155 rlqentry_free(entry
);
159 rangelock_unlock(struct rangelock
*lock
, void *cookie
, struct mtx
*ilk
)
162 MPASS(lock
!= NULL
&& cookie
!= NULL
&& ilk
!= NULL
);
165 rangelock_unlock_locked(lock
, cookie
, ilk
);
169 * Unlock the sub-range of granted lock.
172 rangelock_unlock_range(struct rangelock
*lock
, void *cookie
, off_t start
,
173 off_t end
, struct mtx
*ilk
)
175 struct rl_q_entry
*entry
;
177 MPASS(lock
!= NULL
&& cookie
!= NULL
&& ilk
!= NULL
);
179 KASSERT(entry
->rl_q_flags
& RL_LOCK_GRANTED
,
180 ("Unlocking non-granted lock"));
181 KASSERT(entry
->rl_q_start
== start
, ("wrong start"));
182 KASSERT(entry
->rl_q_end
>= end
, ("wrong end"));
185 if (entry
->rl_q_end
== end
) {
186 rangelock_unlock_locked(lock
, cookie
, ilk
);
189 entry
->rl_q_end
= end
;
190 rangelock_calc_block(lock
);
196 * Add the lock request to the queue of the pending requests for
197 * rangelock. Sleep until the request can be granted.
200 rangelock_enqueue(struct rangelock
*lock
, off_t start
, off_t end
, int mode
,
203 struct rl_q_entry
*entry
;
206 MPASS(lock
!= NULL
&& ilk
!= NULL
);
209 if (td
->td_rlqe
!= NULL
) {
213 entry
= rlqentry_alloc();
214 MPASS(entry
!= NULL
);
215 entry
->rl_q_flags
= mode
;
216 entry
->rl_q_start
= start
;
217 entry
->rl_q_end
= end
;
221 * XXXKIB TODO. Check that a thread does not try to enqueue a
222 * lock that is incompatible with another request from the same
226 TAILQ_INSERT_TAIL(&lock
->rl_waiters
, entry
, rl_q_link
);
227 if (lock
->rl_currdep
== NULL
)
228 lock
->rl_currdep
= entry
;
229 rangelock_calc_block(lock
);
230 while (!(entry
->rl_q_flags
& RL_LOCK_GRANTED
))
231 msleep(entry
, ilk
, 0, "range", 0);
237 rangelock_rlock(struct rangelock
*lock
, off_t start
, off_t end
, struct mtx
*ilk
)
240 return (rangelock_enqueue(lock
, start
, end
, RL_LOCK_READ
, ilk
));
244 rangelock_wlock(struct rangelock
*lock
, off_t start
, off_t end
, struct mtx
*ilk
)
247 return (rangelock_enqueue(lock
, start
, end
, RL_LOCK_WRITE
, ilk
));