Suspend2 merge preparation: Rationale behind the freezer changes.
Hi all.
In merging suspend2, one of the biggest changes is in the area of freezing activity. I'm writing this email in an effort to improve understanding of why I've implemented the freezer differently, and perhaps get some ideas as to how I could better achieve the desired results.
First of all, let me explain that although swsusp and suspend2 work at a very fundamental level in the same way, there are also some important differences. Of particular relevance to this conversation is the fact that swsusp makes what is as close to an atomic copy of the entire image to be saved as we can get and then saves it. In contrast, suspend2 saves one portion of the memory (lru pages), makes an atomic copy of the rest and then saves the atomic copy of the second part.
In order, then, for suspend2 to get the equivalent of an atomic copy of memory, pages must not be added to or removed from the LRU list once we start saving the image. (There are other issues and measures taken, but they're not relevant here).
One of the problems we face in achieving this goal is the fact that timers & timeouts can still fire during this period. These can of course be used to start new processes and to cause others (eg sleep) to exit, with the result that we can end up with changes to the LRU lists and therefore an inconsistent image.
Secondly, we have a more basic problem with the existing freezer implementation. A fundamental assumption made by it is that the order in which processes are signalled does not matter; that there will be no deadlocks caused by freezing one process before another. This simply isn't true.
Thirdly, the existing implementation does not allow us to quickly stop activity. Under heavy load, particularly heavy I/O (assuming the freezer does work), it make take quite a while for processes to respond to the pseudo-signal and enter the refrigerator. New processes may also be spawned, further complicating matters. The busier the system is, the more hit-and-miss freezing becomes.
The implementation of the freezer that I have developed addresses these concerns by adding an atomic count of the number of procesess in critical paths. The first part of the freezer simply waits for the number of processes in critical paths to reach zero.
A critical path is defined as one in which a process takes locks or carries out other activities which could deadlock with another process or make the process not respond to a freezer signal. When a process enters a critical path, the ACTIVITY_START macro causes it to be marked PF_FRIDGE_WAIT and the count of processes in critical paths is atomically imcremented. When it returns, a matching ACTIVITY_END macro reverses these effects. Use of a local variable makes it safe for processes to pass through multiple ACTIVITY_START calls; only the matching ACTIVITY_END will reverse the initial ACTIVITY_START. It may be that in the middle of a critical patch, there is sleeping in which we could safely suspend. This can be indicated by surrounding the sleep with ACTIVITY_PAUSING and ACTIVITY_RESTARTING calls. The thread is thus temporarily marked as safely suspendable.
These four macros play a further role. When we begin to wait for the activity counter to reach zero, a flag is set to record this fact. Macro calls check this flag, and a process reaching a START or RESTARTING activity macro while the flag is set will be refrigerated at that point until after the suspend cycle is completed. This helps us quiesce the system more quickly.
Some processes receive special treatment during this period.
A process marked PF_NOFREEZE is never refrigerated or counted in measuring activity.
A process may instead be marked PF_SYNCTHREAD. It is good for us to sync all dirty data to disc prior to suspending, just-in-case something goes wrong or the user uses noresume. By doing this, we maximise the filesystem integrity as far as is possible. PF_SYNCTHREAD is used for processes such as journalling threads that are used in doing this, and for processes which begin a filesystem sync. These processes are allowed to continue operation during the initial phase, and are frozen later.
The freezing process is thus:
1) Set FREEZE_NEW_ACTIVITY flag and wait for activity count to reach zero. New activity is held, existing activity completes critical paths or pauses at a safe place and syncing runs to completion.
2) Do our own sys_sync, just in case none were already running.
3) Set FREEZE_UNREFRIGERATED flag. Syncthreads will now enter the refrigerator of their own accord or by being signalled.
4) Signal remaining processes to be frozen. Deadlocking is avoided because those that would start critical paths are held at the ACTIVITY_START/RESTARTING calls, prior to taking the locks that would cause the deadlocks.
Regards,
Nigel
Signature · 7 lines
Nigel & Michelle Cunningham C/- Westminster Presbyterian Church Belconnen 61 Templeton Street, Cook, ACT 2614. +61 (2) 6251 7727(wk); +61 (2) 6254 0216 (home) Evolution (n): A hypothetical process whereby infinitely improbable events occur with alarming frequency, order arises from chaos, and no one is given credit.
Hi!
Quoted 5 lines
In merging suspend2, one of the biggest changes is in the area of freezing activity. I'm writing this email in an effort to improve understanding of why I've implemented the freezer differently, and perhaps get some ideas as to how I could better achieve the desired results.
Thanks for this. (Btw you might want to Cc me on such mails, I read both list and personal mails, but you'll get way better response time.)
Quoted 7 lines
First of all, let me explain that although swsusp and suspend2 work at a very fundamental level in the same way, there are also some important differences. Of particular relevance to this conversation is the fact that swsusp makes what is as close to an atomic copy of the entire image to be saved as we can get and then saves it. In contrast, suspend2 saves one portion of the memory (lru pages), makes an atomic copy of the rest and then saves the atomic copy of the second part.
Hmm, I did not realize this difference. Doing these hacks with LRU seems pretty crazy to me...
Would it be possible to stop processes when they try to manipulate LRU, instead?
Quoted 5 lines
Secondly, we have a more basic problem with the existing freezer implementation. A fundamental assumption made by it is that the order in which processes are signalled does not matter; that there will be no deadlocks caused by freezing one process before another. This simply isn't true.
It better should be. If it is not true, then kill -STOP -1 does not work, and that would be a kernel bug, right?
When user thread is stopped, it should better not hold any lock, because otherwise we have problem anyway.
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Quoted 6 lines
Thirdly, the existing implementation does not allow us to quickly stop activity. Under heavy load, particularly heavy I/O (assuming the freezer does work), it make take quite a while for processes to respond to the pseudo-signal and enter the refrigerator. New processes may also be spawned, further complicating matters. The busier the system is, the more hit-and-miss freezing becomes.
I agree it can take longer, but modulo bugs, it should be always possible.
Quoted 4 lines
The implementation of the freezer that I have developed addresses these concerns by adding an atomic count of the number of procesess in critical paths. The first part of the freezer simply waits for the number of processes in critical paths to reach zero.
Exactly, you slowed down critical paths of kernel... This makes patch big, ugly, and is bad idea.
Quoted 6 lines
These four macros play a further role. When we begin to wait for the activity counter to reach zero, a flag is set to record this fact. Macro calls check this flag, and a process reaching a START or RESTARTING activity macro while the flag is set will be refrigerated at that point until after the suspend cycle is completed. This helps us quiesce the system more quickly.
Adding hooks to "fast" stuff like read()/write()/open is no-no. Adding small number of hooks to slower stuff like exec()/exit() might be acceptable. Could you get away with that?
Pavel
Signature · 1 line
934a471f20d6580d5aad759bf0d97ddc
Hi.
Quoted 2 lines · Pavel Machek
Thanks for this. (Btw you might want to Cc me on such mails, I read both list and personal mails, but you'll get way better response time.)
Humble apologies! :>
Quoted 5 lines
Quoted 1 line
First of all, let me explain that although swsusp and suspend2 work at a very fundamental level in the same way, there are also some important differences. Of particular relevance to this conversation is the fact that swsusp makes what is as close to an atomic copy of the entire image to be saved as we can get and then saves it. In contrast, suspend2 saves one portion of the memory (lru pages), makes an atomic copy of the rest and then saves the atomic copy of the second part.
Hmm, I did not realize this difference. Doing these hacks with LRU seems pretty crazy to me...
No... this is what you already know, just described differently. You mentioned in your documentation that suspend2 overcomes the half of memory limitation by saving the image in two parts: the second part is LRU (unless I have my terminology confused: I'm talking about pages on the inactive and active lists). By the time this is done, all other processes are stopped, so there's no danger of corruption anyway. Suspend2 itself doesn't affect LRU because I switched from using the 'normal' swap read/write calls ages ago, as part of adding swapfile support. For 2.6 we're directly using BIOs.
Quoted 2 lines
Would it be possible to stop processes when they try to manipulate LRU, instead?
They're already stopped.
Quoted 5 lines
Quoted 1 line
Secondly, we have a more basic problem with the existing freezer implementation. A fundamental assumption made by it is that the order in which processes are signalled does not matter; that there will be no deadlocks caused by freezing one process before another. This simply isn't true.
It better should be. If it is not true, then kill -STOP -1 does not work, and that would be a kernel bug, right?
We already discussed the example of trying to do an ls on an NFS share and the NFS threads being frozen first. I can come up with more examples if you'd like. I guess the simplest one (off the top of my head) would be freezing kjournald while processes are submitting and waiting on I/O.
Quoted 2 lines
When user thread is stopped, it should better not hold any lock, because otherwise we have problem anyway.
Yes, but we're not just talking about user threads. We could differentiate kernel threads and user threads (presumably using another PF_ flag?) and attempt to freeze the user threads first.
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Yes, but what order? I played with that problem for ages. Perhaps I just
didn't find the right combination.
Quoted 3 lines
Quoted 1 line
Thirdly, the existing implementation does not allow us to quickly stop activity. Under heavy load, particularly heavy I/O (assuming the freezer does work), it make take quite a while for processes to respond to the pseudo-signal and enter the refrigerator. New processes may also be spawned, further complicating matters. The busier the system is, the more hit-and-miss freezing becomes.
I agree it can take longer, but modulo bugs, it should be always possible.
Should... I'll find some time to roll a freezer implementation that does what you're suggesting (try user space threads first, seek an order for kernel space threads). If we can do it that way, it will be less invasive. I'll see...
Quoted 4 lines
Quoted 1 line
The implementation of the freezer that I have developed addresses these concerns by adding an atomic count of the number of procesess in critical paths. The first part of the freezer simply waits for the number of processes in critical paths to reach zero.
Exactly, you slowed down critical paths of kernel... This makes patch big, ugly, and is bad idea.
Maybe I wasn't clear enough. When we're not suspending, all that is added to the paths that are modified is:
- 9 tests, possibly resulting in refrigerator entry or immediately dropping through, setting the PF_FRIDGE_WAIT flag and incrementing the atomic_t at the start of a busy path.
- 2 tests, possibly resetting the flag & decrementing the counter at the end.
- 3 tests, setting a local variable, restting the FRIDGE_WAIT flag and decrementing the atomic_t when dropping locks and sleeping in kernel.
- 10 tests, possibly resulting in refrigerator entry or immediately dropping through, restoring the PF_FRIDGE_WAIT flag and reincrementing the atomic_t after such sleeps.
I've been using this approach for months, and my Celeron 933 doesn't feel slow at all. I've had no complains from users either.
We really need to ask how critical these paths really are: some of them are certainly more commonly used, such as sys_read & sys_write. The vast majority, however, are less commonly used. I wonder if it's worth getting a benchmarking program. I'll try your suggestion above first.
Quoted 6 lines
Quoted 1 line
These four macros play a further role. When we begin to wait for the activity counter to reach zero, a flag is set to record this fact. Macro calls check this flag, and a process reaching a START or RESTARTING activity macro while the flag is set will be refrigerated at that point until after the suspend cycle is completed. This helps us quiesce the system more quickly.
Adding hooks to "fast" stuff like read()/write()/open is no-no. Adding small number of hooks to slower stuff like exec()/exit() might be acceptable. Could you get away with that?
No. Reading and writing is exactly what we want to be able to pause. Otherwise we get processes stuck waiting on pages.
Summary:
- I'll try your user space first, kernel space afterwards suggestion.
- I'll also look into benchmarking the system with and without suspend2 compiled in (ie with and without the hooks, since they compile away to nothing without CONFIG_SOFTWARE_SUSPEND2
Regards,
Nigel
Signature · 7 lines
Nigel & Michelle Cunningham C/- Westminster Presbyterian Church Belconnen 61 Templeton Street, Cook, ACT 2614. +61 (2) 6251 7727(wk); +61 (2) 6254 0216 (home) Evolution (n): A hypothetical process whereby infinitely improbable events occur with alarming frequency, order arises from chaos, and no one is given credit.
Am Freitag, 21. Mai 2004 14:28 schrieb Nigel Cunningham:
Quoted 6 lines
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Yes, but what order? I played with that problem for ages. Perhaps I just didn't find the right combination.
How about recording the order of creation and do it in opposite order?
Regards
Oliver
Hi!
Quoted 9 lines
Quoted 9 lines
Quoted 7 lines
First of all, let me explain that although swsusp and suspend2 work at a very fundamental level in the same way, there are also some important differences. Of particular relevance to this conversation is the fact that swsusp makes what is as close to an atomic copy of the entire image to be saved as we can get and then saves it. In contrast, suspend2 saves one portion of the memory (lru pages), makes an atomic copy of the rest and then saves the atomic copy of the second part.
Quoted 7 lines
Quoted 2 lines
Hmm, I did not realize this difference. Doing these hacks with LRU seems pretty crazy to me...
No... this is what you already know, just described differently. You mentioned in your documentation that suspend2 overcomes the half of memory limitation by saving the image in two parts: the second part is LRU (unless I have my terminology confused: I'm talking about pages on
Yes, I just did not realize that it means changes for freezer.
Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Secondly, we have a more basic problem with the existing freezer implementation. A fundamental assumption made by it is that the order in which processes are signalled does not matter; that there will be no deadlocks caused by freezing one process before another. This simply isn't true.
Quoted 8 lines
Quoted 2 lines
It better should be. If it is not true, then kill -STOP -1 does not work, and that would be a kernel bug, right?
We already discussed the example of trying to do an ls on an NFS share and the NFS threads being frozen first. I can come up with more examples if you'd like. I guess the simplest one (off the top of my head) would be freezing kjournald while processes are submitting and waiting on I/O.
Agreed, kernel processes need to go last.
Quoted 6 lines
Quoted 2 lines
When user thread is stopped, it should better not hold any lock, because otherwise we have problem anyway.
Yes, but we're not just talking about user threads. We could differentiate kernel threads and user threads (presumably using another
PF_flag?) and attempt to freeze the user threads first.
There should be some other way to see kernel threads... their mm is init_mm or something like that.
Quoted 6 lines
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Yes, but what order? I played with that problem for ages. Perhaps I just
didn't find the right combination.
... ... hmm. Not sure.
Did you add hooks into sys_read() to deal with with kernel-thread-vs-kernel-thread ordering?
Quoted 22 lines
Quoted 7 lines
Quoted 4 lines
The implementation of the freezer that I have developed addresses these concerns by adding an atomic count of the number of procesess in critical paths. The first part of the freezer simply waits for the number of processes in critical paths to reach zero.
Exactly, you slowed down critical paths of kernel... This makes patch big, ugly, and is bad idea.
Maybe I wasn't clear enough. When we're not suspending, all that is added to the paths that are modified is:
- 9 tests, possibly resulting in refrigerator entry or immediately dropping through, setting the
PF_FRIDGE_WAITflag and incrementing theatomic_tat the start of a busy path.
- 2 tests, possibly resetting the flag & decrementing the counter at the end.
- 3 tests, setting a local variable, restting theFRIDGE_WAITflag and decrementing theatomic_twhen dropping locks and sleeping in kernel.
- 10 tests, possibly resulting in refrigerator entry or immediately dropping through, restoring thePF_FRIDGE_WAITflag and reincrementing theatomic_tafter such sleeps.
Quoted 2 lines
I've been using this approach for months, and my Celeron 933 doesn't feel slow at all. I've had no complains from users either.
Well, slowness is likely to be something like 1% at microbenchmark. (Try lm_bench, test "lat-read" or something like that). Of course you don't feel any slowness; but you'd probably not feel any slowness if kernel was compiled -O0 either.
Quoted 5 lines
Summary:
- I'll try your user space first, kernel space afterwards suggestion.
- I'll also look into benchmarking the system with and without suspend2 compiled in (ie with and without the hooks, since they compile away to nothing withoutCONFIG_SOFTWARE_SUSPEND2
Don't spend too much time benchmarking... But you might want to ask Al Viro what he thinks about another test in sys_read ;-).
Pavel
Signature · 1 line
934a471f20d6580d5aad759bf0d97ddc
Hi!
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Yes, but what order? I played with that problem for ages. Perhaps I just didn't find the right combination.
How about recording the order of creation and do it in opposite order?
Order of creation is pretty much hidden in pid, but I do not think that will work.
Pavel
Signature · 1 line
934a471f20d6580d5aad759bf0d97ddc
Am Freitag, 21. Mai 2004 19:08 schrieben Sie:
Quoted 6 lines
Hi!
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
Yes, but what order? I played with that problem for ages. Perhaps I just didn't find the right combination.
How about recording the order of creation and do it in opposite order?
Order of creation is pretty much hidden in pid, but I do not think that will work.
Why? Build a list during kernel thread creation. It is not a hot code path.
Regards
Oliver
Hi!
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Yes, but what order? I played with that problem for ages. Perhaps I just didn't find the right combination.
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
How about recording the order of creation and do it in opposite order?
Order of creation is pretty much hidden in pid, but I do not think that will work.
Why? Build a list during kernel thread creation. It is not a hot code path.
Maybe the order in which kernel threads were created is not the same as the order how they need to be frozen?
Pavel
Signature · 1 line
934a471f20d6580d5aad759bf0d97ddc
Am Freitag, 21. Mai 2004 19:15 schrieb Pavel Machek:
Quoted 11 lines
Hi!
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
Kernel threads are different, and each must be handled separately, maybe even with some ordering. But there's relatively small number of kernel threads...
Yes, but what order? I played with that problem for ages. Perhaps I just didn't find the right combination.
How about recording the order of creation and do it in opposite order?
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
Order of creation is pretty much hidden in pid, but I do not think that will work.
Why? Build a list during kernel thread creation. It is not a hot code path.
Maybe the order in which kernel threads were created is not the same as the order how they need to be frozen?
Possible, but unlikely. If there can be a deadlock if they are frozen in reverse order, the same problem existed during creation and needed to be specially handled.
Regards
Oliver
Quoted 4 lines · Oliver Neukum
Possible, but unlikely. If there can be a deadlock if they are frozen in reverse order, the same problem existed during creation and needed to be specially handled.
So exactly which kernel threads will dead lock when frozen in the wrong order? So far I've only seen user process vs. kernel thread examples.
Cheers,
Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txtHi.
Quoted 4 lines · Oliver Neukum
Am Freitag, 21. Mai 2004 14:28 schrieb Nigel Cunningham:
Quoted 2 lines
Yes, but what order? I played with that problem for ages. Perhaps I just
didn't find the right combination.How about recording the order of creation and do it in opposite order?
We could add a field to the process struct to record that. (Since PIDs can wrap, they can't be relied upon for this).
One potential problem is that we'd race with processes that were forking, but that's a problem with the existing implementation anyway.
I can see that the only way I'm going to convince people that we need the method I settled on is by showing the deficiencies of the current one :<
Nigel
Signature · 7 lines
Nigel & Michelle Cunningham C/- Westminster Presbyterian Church Belconnen 61 Templeton Street, Cook, ACT 2614. +61 (2) 6251 7727(wk); +61 (2) 6254 0216 (home) Evolution (n): A hypothetical process whereby infinitely improbable events occur with alarming frequency, order arises from chaos, and no one is given credit.
Hi.
Quoted 4 lines · Pavel Machek
Quoted 1 line
No... this is what you already know, just described differently. You mentioned in your documentation that suspend2 overcomes the half of memory limitation by saving the image in two parts: the second part is LRU (unless I have my terminology confused: I'm talking about pages on
Yes, I just did not realize that it means changes for freezer.
It means that we need to be more careful to ensure that processes all processes are frozen than we do with your implementation: we can't have processes forking or exiting because a timer fires while we're writing the first part of the image. (I saw that happen with bad effects).
Quoted 4 lines
Quoted 1 line
Yes, but we're not just talking about user threads. We could differentiate kernel threads and user threads (presumably using another
PF_flag?) and attempt to freeze the user threads first.There should be some other way to see kernel threads... their mm is
init_mmor something like that.
Yes.
Quoted 2 lines
Did you add hooks into
sys_read()to deal with with kernel-thread-vs-kernel-thread ordering?
With the hooks, I don't have to worry about ordering at all. Once the atomic_t comes down to zero, every process has either entered the refrigerator because it hit a start/restart hook or wasn't doing anything to start with. I don't have to care about ordering because anything that does start activity while I'm signalling hits a hook and gets refrigerated anyway, even if it's not in response to the pseudo-signal.
Quoted 4 lines
Well, slowness is likely to be something like 1% at microbenchmark. (Try
lm_bench, test "lat-read" or something like that). Of course you don't feel any slowness; but you'd probably not feel any slowness if kernel was compiled -O0 either.
:>. I'll put benchmarking on my todo list...
Quoted 8 lines
Quoted 4 lines
Summary:
- I'll try your user space first, kernel space afterwards suggestion.
- I'll also look into benchmarking the system with and without suspend2
compiled in (ie with and without the hooks, since they compile away to nothing withoutCONFIG_SOFTWARE_SUSPEND2Don't spend too much time benchmarking... But you might want to ask Al Viro what he thinks about another test in
sys_read;-).
... and won't spend too long on it :>. I think I can guess.
Nigel
Signature · 7 lines
Nigel & Michelle Cunningham C/- Westminster Presbyterian Church Belconnen 61 Templeton Street, Cook, ACT 2614. +61 (2) 6251 7727(wk); +61 (2) 6254 0216 (home) Evolution (n): A hypothetical process whereby infinitely improbable events occur with alarming frequency, order arises from chaos, and no one is given credit.
Hi.
Quoted 2 lines · Herbert Xu
So exactly which kernel threads will dead lock when frozen in the wrong order? So far I've only seen user process vs. kernel thread examples.
It's been so long since I've seen it happen that I have to confess I've forgotten. I'll take a look in the list archives.
Nigel
Signature · 7 lines
Nigel & Michelle Cunningham C/- Westminster Presbyterian Church Belconnen 61 Templeton Street, Cook, ACT 2614. +61 (2) 6251 7727(wk); +61 (2) 6254 0216 (home) Evolution (n): A hypothetical process whereby infinitely improbable events occur with alarming frequency, order arises from chaos, and no one is given credit.
Quoted 4 lines · Nigel Cunningham
Hi.
Oliver Neukum wrote:
Quoted 8 lines
Quoted 5 lines
Am Freitag, 21. Mai 2004 14:28 schrieb Nigel Cunningham:
Quoted 1 line
Yes, but what order? I played with that problem for ages. Perhaps I just didn't find the right combination.
How about recording the order of creation and do it in opposite order?
We could add a field to the process struct to record that. (Since PIDs can wrap, they can't be relied upon for this).
I would never suggest keeping a process creation date for something trivial, but since you seem to be proposing one for something major, the process creation date could be available in the readdir of the /proc directory. Assuming you intend to keep date at all and not just some counter, of course.
Signature · 3 lines
-bill davidsen ([email protected]) "The secret to procrastination is to put things off until the last possible moment - but no longer" -me