Skip to contentSkip to conversation

fcntl and flock wakeups not FIFO?

DISCUSSION Matthew Wilcox 2 participants 5 messages Feb 18, 2003 VFS

lore
Share & tools
lore
#0 lore raw

[cc'ing the person or list mentioned in MAINTAINERS would get you a better response :-P]

Quoted 6 lines

I've been doing some experimenting with locking on 2.4.18 and have noticed that if I have a number of writers waiting on a lock, they are not woken up in the order in which they requested the lock.

Is this expected? If so, what was the reasoning for this and are there any patches to give FIFO wakeups?

That certainly isn't what's supposed to happen. They should get woken up in-order. The code in 2.4.18 seems to be doing that. Are you doing anything clever with scheduling?

Signature · 3 lines
"It's not Hollywood.  War is real, war is primarily not about defeat or
victory, it is about death.  I've seen thousands and thousands of dead bodies.
Do you think I want to have an academic debate on this subject?" -- Robert Fisk
#1 lore raw
Quoted 2 lines · Matthew Wilcox

[cc'ing the person or list mentioned in MAINTAINERS would get you a better response :-P]

Hmm...that might be a good idea. :)

Quoted 11 lines
Quoted 6 lines

I've been doing some experimenting with locking on 2.4.18 and have noticed that if I have a number of writers waiting on a lock, they are not woken up in the order in which they requested the lock.

Is this expected? If so, what was the reasoning for this and are there any patches to give FIFO wakeups?

That certainly isn't what's supposed to happen. They should get woken up in-order. The code in 2.4.18 seems to be doing that. Are you doing anything clever with scheduling?

Well maybe a little bit on the production box, but I don't think its the cause since the same thing happens on my home machine with a stock Mandrake 9 kernel (2.4.19-16mdk).

Here's the test app:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/file.h>

int main(int argc, char **argv)

{
    int fd = open("/dev/null", O_RDWR);
    if (fd < 0)
    {
       perror("open");
       exit(-1);
    }

    printf("aquiring exclusive lock\n");
    int rc = flock(fd, LOCK_EX);
    if (rc < 0)
    {
       perror("flock");
       exit(-1);
    }

    printf("got lock\n");

    while(1)
       pause();

    return 0;
}

I start up four different instances of it in different windows, then kill them (ctrl-c) in the order that I started them.

It doesn't happen every time, but they don't always get the lock in the same order that I started them.

Chris

#2 lore raw
In reply to Matthew Wilcox
Quoted 10 lines · Matthew Wilcox
Quoted 6 lines

I've been doing some experimenting with locking on 2.4.18 and have noticed that if I have a number of writers waiting on a lock, they are not woken up in the order in which they requested the lock.

Is this expected? If so, what was the reasoning for this and are there any patches to give FIFO wakeups?

That certainly isn't what's supposed to happen. They should get woken up in-order. The code in 2.4.18 seems to be doing that. Are you doing anything clever with scheduling?

I have a potential cause here, but I'm not sure if it makes sense. The following code (slightly reformatted) is taken from locks.c in the Mandrake 2.4.19-16mdk kernel.

static void locks_wake_up_blocks(struct file_lock *blocker, unsigned int wait)

{
    while (!list_empty(&blocker->fl_block)) {
      struct file_lock *waiter = list_entry(blocker->fl_block.next,
                                           struct file_lock, fl_block);
      if (wait) {
        locks_notify_blocked(waiter);

        /* Let the blocked process remove waiter from the
         * block list when it gets scheduled.
         */
        current->policy |= SCHED_YIELD;
        schedule();
      } else {
        /* Remove waiter from the block list, because by the
         * time it wakes up blocker won't exist any more.
         */
        locks_delete_block(waiter);
        locks_notify_blocked(waiter);
      }
    }
}

It appears that if this function is called with a wait value of zero, all of the waiting processes will be woken up before the scheduler gets called. This means that the scheduler ends up picking which process runs rather than the locking code.

Looking through the file, there is no call chain on an unlock or on closing the last locked fd which can give a nonzero wait value, meaning that we will always end up with the scheduler making the decision in these cases.

Am I missing something?

Chris

#3 lore raw
Quoted 28 lines · Chris Friesen
Quoted 3 lines

That certainly isn't what's supposed to happen. They should get woken up in-order. The code in 2.4.18 seems to be doing that. Are you doing anything clever with scheduling?

static void locks_wake_up_blocks(struct file_lock *blocker, unsigned int wait)

{
     while (!list_empty(&blocker->fl_block)) {
       struct file_lock *waiter = list_entry(blocker->fl_block.next,
                                            struct file_lock, fl_block);
       if (wait) {
         locks_notify_blocked(waiter);

         /* Let the blocked process remove waiter from the
          * block list when it gets scheduled.
          */
         current->policy |= SCHED_YIELD;
         schedule();
       } else {
         /* Remove waiter from the block list, because by the
          * time it wakes up blocker won't exist any more.
          */
         locks_delete_block(waiter);
         locks_notify_blocked(waiter);
       }
     }
}
Quoted 4 lines

It appears that if this function is called with a wait value of zero, all of the waiting processes will be woken up before the scheduler gets called. This means that the scheduler ends up picking which process runs rather than the locking code.

Right. That's why I asked whether you were doing something clever with scheduling ;-)

Quoted 4 lines

Looking through the file, there is no call chain on an unlock or on closing the last locked fd which can give a nonzero wait value, meaning that we will always end up with the scheduler making the decision in these cases.

I'm impressed that you chased it through ;-) This logic is mostly gone from 2.5 because I found it too hard to keep in my mind while working on this file.

Quoted 1 line

Am I missing something?

Nope, it's true. But the tasks get marked as runnable in the right order, so the scheduler should be doing the right thing -- if any tasks really have a better reason to run first (whether it's through RT scheduling or through standard Unix priority scheduling) then they'll get the lock first. Otherwise, I'd've thought it should be first-runnable, first-run.

Signature · 3 lines
"It's not Hollywood.  War is real, war is primarily not about defeat or
victory, it is about death.  I've seen thousands and thousands of dead bodies.
Do you think I want to have an academic debate on this subject?" -- Robert Fisk
#4 lore raw
Quoted 10 lines · Matthew Wilcox
Quoted 4 lines · Chris Friesen

It appears that if this function is called with a wait value of zero, all of the waiting processes will be woken up before the scheduler gets called. This means that the scheduler ends up picking which process runs rather than the locking code.

Right. That's why I asked whether you were doing something clever with scheduling ;-)

Ah, okay.

Quoted 6 lines
Quoted 4 lines

Looking through the file, there is no call chain on an unlock or on closing the last locked fd which can give a nonzero wait value, meaning that we will always end up with the scheduler making the decision in these cases.

I'm impressed that you chased it through ;-)

I was bored and it was bothering me.... :)

Quoted 7 lines
Quoted 1 line

Am I missing something?

Nope, it's true. But the tasks get marked as runnable in the right order, so the scheduler should be doing the right thing -- if any tasks really have a better reason to run first (whether it's through RT scheduling or through standard Unix priority scheduling) then they'll get the lock first. Otherwise, I'd've thought it should be first-runnable, first-run.

Apparently not always. I guess it's probably good enough for my purposes the way it is, it just surprised me a bit.

Is 2.5 the same way? (Haven't looked at it yet.)

Chris

Signature · 4 lines
Chris Friesen                    | MailStop: 043/33/F10
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: [email protected]