On Thu, 24 Feb 2022 16:47:30 +0800 Hillf Danton wrote:
> On Sat, 8 Jan 2022 08:46:17 -0800
> > From: Tim Murray <timmur...@google.com>
> >
> > f2fs rw_semaphores work better if writers can starve readers,
> > especially for the checkpoint thread, because writers are strictly
> > more important than reader threads. This prevents significant priority
> > inversion between low-priority readers that blocked while trying to
> > acquire the read lock and a second acquisition of the write lock that
> > might be blocking high priority work.
> >
> > Signed-off-by: Tim Murray <timmur...@google.com>
> > Signed-off-by: Jaegeuk Kim <jaeg...@kernel.org>
> > ---
>
> ...
>
> > +/*
> > + * An implementation of an rwsem that is explicitly unfair to readers. This
> > + * prevents priority inversion when a low-priority reader acquires the
> > read lock
> > + * while sleeping on the write lock but the write lock is needed by
> > + * higher-priority clients.
> > + */
> > +
> > +struct f2fs_rwsem {
> > + struct rw_semaphore internal_rwsem;
> > + wait_queue_head_t read_waiters;
> > +};
>
> ...
>
> > +static inline void f2fs_down_read(struct f2fs_rwsem *sem)
> > +{
> > + wait_event(sem->read_waiters, down_read_trylock(&sem->internal_rwsem));
> > +}
> > +
> > +static inline int f2fs_down_read_trylock(struct f2fs_rwsem *sem)
> > +{
> > + return down_read_trylock(&sem->internal_rwsem);
> > +}
> > +
> > +static inline void f2fs_up_read(struct f2fs_rwsem *sem)
> > +{
> > + up_read(&sem->internal_rwsem);
> > +}
> > +
> > +static inline void f2fs_down_write(struct f2fs_rwsem *sem)
> > +{
> > + down_write(&sem->internal_rwsem);
> > +}
> > +
> > +static inline int f2fs_down_write_trylock(struct f2fs_rwsem *sem)
> > +{
> > + return down_write_trylock(&sem->internal_rwsem);
> > +}
> > +
> > +static inline void f2fs_up_write(struct f2fs_rwsem *sem)
> > +{
> > + up_write(&sem->internal_rwsem);
> > + wake_up_all(&sem->read_waiters);
> > +}
> > +
>
> Here is my two cents, the unfair rwsem derived from lock_sock(), which has
> no link to rwsem.
>
> Only for thoughts now.
>
> Hillf
>
> struct unfair_rwsem {
> spinlock_t lock;
> int owner; /* < 0 writer, > 0 readers */
>
> struct list_head reader, writer; /* read/write waiters */
>
> #ifdef CONFIG_DEBUG_LOCK_ALLOC
> struct lockdep_map dep_map;
> #endif
> };
>
> struct unfair_rwsem_wait {
> struct list_head node;
> struct task_struct *task;
> };
>
> static void lock_unfair_rwsem(struct unfair_rwsem *us, int read)
> {
> struct unfair_rwsem_wait wait;
>
> mutex_acquire(&us->dep_map, 0, 0, _RET_IP_);
> might_sleep();
> wait.task = current;
> for (;;) {
> spin_lock(&us->lock);
> if (read) {
> if (us->owner >= 0) {
> us->owner++;
> spin_unlock(&us->lock);
> return;
> }
> list_add_tail(&wait.node, &us->reader);
> } else {
> if (us->owner == 0) {
> us->owner--;
> spin_unlock(&us->lock);
> return;
> }
> list_add_tail(&wait.node, &us->writer);
> }
> set_current_state(TASK_UNINTERRUPTIBLE);
> spin_unlock(&us->lock);
> schedule();
> }
> }
>
> void down_read_unfair_rwsem(struct unfair_rwsem *us)
> {
> lock_unfair_rwsem(us, 1);
> }
>
> void down_write_unfair_rwsem(struct unfair_rwsem *us)
> {
> lock_unfair_rwsem(us, 0);
> }
>
> static void unlock_unfair_rwsem(struct unfair_rwsem *us, int read)
> {
> struct list_head *head = NULL;
> int all = 0;
>
> spin_lock(&us->lock);
> if (us->owner < 0) {
> BUG_ON(read);
> us->owner++;
> BUG_ON(0 != us->owner);
>
> if (!list_empty(&us->writer))
> head = &us->writer;
> else if (!list_empty(&us->reader)) {
> head = &us->reader;
> all = 1;
> }
> } else if (us->owner > 0) {
> BUG_ON(!read);
> BUG_ON(!list_empty(&us->reader));
> us->owner--;
> if (us->owner == 0)
> if (!list_empty(&us->writer))
> head = &us->writer;
> } else
> BUG_ON(1);
>
> mutex_release(&us->dep_map, _RET_IP_);
> if (head) {
> struct unfair_rwsem_wait *wait;
> do {
> wait = list_first_entry(head, struct unfair_rwsem_wait,
> node);
> list_del(&wait->node);
> wake_up_process(wait->task);
> } while (all && !list_empty(head));
> }
> spin_unlock(&us->lock);
> }
>
> void up_write_unfair_rwsem(struct unfair_rwsem *us)
> {
> unlock_unfair_rwsem(us, 0);
> }
>
> void up_read_unfair_rwsem(struct unfair_rwsem *us)
> {
> unlock_unfair_rwsem(us, 1);
> }
>
And make unfair rwsem more unfair by setting lock owner for write waiter,
in addition to prefering to wake up write waiter over read waiter.
Hillf
--- x/unfair_rwsem.c
+++ y/unfair_rwsem.c
@@ -42,6 +42,8 @@ static void lock_unfair_rwsem(struct unf
set_current_state(TASK_UNINTERRUPTIBLE);
spin_unlock(&us->lock);
schedule();
+ if (!read)
+ return; /* because this is unfair rwsem */
}
}
@@ -88,8 +90,15 @@ static void unlock_unfair_rwsem(struct u
do {
wait = list_first_entry(head, struct unfair_rwsem_wait,
node);
list_del(&wait->node);
- wake_up_process(wait->task);
- } while (all && !list_empty(head));
+ if (all)
+ wake_up_process(wait->task);
+ else {
+ /* for the sake of unfairness */
+ us->owner = -1;
+ wake_up_process(wait->task);
+ break;
+ }
+ } while (!list_empty(head));
}
spin_unlock(&us->lock);
}
_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
