Closed rick-masters closed 1 year ago
Testing with ram drive does work:
As we talked on IRC #bootstrappable, this is really interesting and might help me to find the cause of this bug. I'll give another try to investigate this bug.
I've found a race condition when using memory pages. After applying the two patches below the bootstrap process no longer shows the page fault issue. It looks like it finishes finely. Please confirm it.
automake-1.15.1: postprocess binaries.
automake-1.15.1: creating package.
automake-1.15.1: checksumming created package.
automake-1.15.1_0.tar.bz2: OK
automake-1.15.1: cleaning up.
automake-1.15.1: installing package.
automake-1.15.1: build successful
binutils-2.30: beginning build using script binutils-2.30.sh
binutils-2.30: getting sources.
binutils-2.30.tar.bz2: OK
binutils-2.30: unpacking source.
Detaching /dev/loop2
Removing /home/mikaku/github/live-bootstrap/tmp
I've been running the bootstrap process 5 times, and in only one case it stopped when tar
'ring the musl library:
/usr/bin/install -c gccbug /tmp/destdir/usr/bin/gccbug
rm -rf /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
mkdir /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
chmod a+rx /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
(cd `${PWDCMD-pwd}`/include ; \
tar -cf - .; exit 0) | (cd /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/includ)
I'm afraid this is another well-known bug with pipes as stated in the bottom of this page. Sometimes the kernel doesn't wakes up the process involved in a pipe communication. The work-around normally is easy, just login on a different terminal and the process resumes, but in this bootstrap environment there is not such possibility. Anyway, we can talk about this once you can ensure that the OP problem is fixed.
Please, apply the following two patches to your kernel:
diff --git a/mm/page.c b/mm/page.c
index e63816b..721a4c8 100644
--- a/mm/page.c
+++ b/mm/page.c
@@ -281,7 +281,9 @@ void invalidate_inode_pages(struct inode *i)
for(offset = 0; offset < i->i_size; offset += PAGE_SIZE) {
if((pg = search_page_hash(i, offset))) {
+ page_lock(pg);
release_page(pg);
+ page_unlock(pg);
remove_from_hash(pg);
}
}
@@ -332,19 +334,31 @@ int bread_page(struct page *pg, struct inode *i, __off_t offset, char prot, char
{
__blk_t block;
__off_t size_read;
- int blksize;
+ int blksize, retval;
struct buffer *buf;
blksize = i->sb->s_blocksize;
- size_read = 0;
+ retval = size_read = 0;
+
+ page_lock(pg);
+
+ /* cache any read-only or public (shared) pages */
+ if(!(prot & PROT_WRITE) || flags & MAP_SHARED) {
+ pg->inode = i->inode;
+ pg->offset = offset;
+ pg->dev = i->dev;
+ insert_to_hash(pg);
+ }
while(size_read < PAGE_SIZE) {
if((block = bmap(i, offset + size_read, FOR_READING)) < 0) {
- return 1;
+ retval = 1;
+ break;
}
if(block) {
if(!(buf = bread(i->dev, block, blksize))) {
- return 1;
+ retval = 1;
+ break;
}
memcpy_b(pg->data + size_read, buf->data, blksize);
brelse(buf);
@@ -355,15 +369,8 @@ int bread_page(struct page *pg, struct inode *i, __off_t offset, char prot, char
size_read += blksize;
}
- /* cache any read-only or public (shared) pages */
- if(!(prot & PROT_WRITE) || flags & MAP_SHARED) {
- pg->inode = i->inode;
- pg->offset = offset;
- pg->dev = i->dev;
- insert_to_hash(pg);
- }
-
- return 0;
+ page_unlock(pg);
+ return retval;
}
int file_read(struct inode *i, struct fd *fd_table, char *buffer, __size_t count)
and
diff --git a/mm/fault.c b/mm/fault.c
index e104e70..9a426c4 100644
--- a/mm/fault.c
+++ b/mm/fault.c
@@ -122,7 +122,9 @@ static int page_not_present(struct vma *vma, unsigned int cr2, struct sigcontext
printk("%s(): Oops, map_page() returned 0!\n", __FUNCTION__);
return 1;
}
+ page_lock(pg);
addr = (unsigned int)pg->data;
+ page_unlock(pg);
}
}
if(!pg) {
and let me know the results.
I'm afraid I haven't seen any significant improvement with this patch. I'm still getting page faults in make and qemu exits and hangs while unpacking sources or installing files. I ran over 40 builds. There were no successes.
Qemu version: QEMU emulator version 4.2.1 (Debian 1:4.2-3ubuntu6.24) Linux build: 5.15.0-1028-aws #32~20.04.1-Ubuntu SMP Mon Jan 9 18:02:08 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux
Perhaps you could post the kernel you tested with. I've attached mine. fiwix.gz
This is the kernel I've used. It should be the same as yours since it was built using your above steps, plus the patch: fiwix.gz
Qemu version:
QEMU emulator version 6.2.0 (qemu-6.2.0-17.fc36)
Linux build:
6.2.8-100.fc36.x86_64 #1 SMP PREEMPT_DYNAMIC Wed Mar 22 19:14:19 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux
OK, I'll continue investigating.
I no longer see page faults with this patch, but yes, it still hangs because of the schedule problems I mentioned before. The kernel sometimes reach a point where all processes are sleeping and no one will wake up them.
I forgot to say that I use the following line to make the build:
export CROSS_COMPILE=~/Fiwix/toolchain/4.7.4-elf/bin/i686-elf- ; make clean ; make CONFFLAGS="-DCONFIG_MMAP2 -DCONFIG_64BIT_SYSCALLS -DNR_PROCS=4096 -DCHILD_MAX=4096 -DOPEN_MAX=1536 -DNR_OPENS=1536 -DDEFAULT_ROOT_FLAGS=0 -DINIT_PROGRAM=\"\\\"/init\\\"\" -DUTS_SYSNAME=\"\\\"Linux\\\"\""
As you can see I use the vanilla GCC 4.7.4 which is the same I use to build the Fiwix kernel from Linux. This is not the GCC that comes with my Fedora 36. Perhaps you might also want to use a vanilla GCC instead of using the GCC that comes with your Linux distribution.
I've tested with your kernel with the same results so the compiler is not the issue. I'm seeing a hang on the pipe command about 65%-70% of builds, page fault on make about 10%-15% of the time and the rest are hangs or qemu exits while unpacking source or installing files. No successful builds so far. I've tested with qemu 4.20 and 7.1.50 (v7.1.0-1005-g8823ef1336-dirty). One big remaining variable is the host kernel. I can try a newer kernel (perhaps Fedora 36) but I'm not sure when I will have time for that.
One big remaining variable is the host kernel. I can try a newer kernel (perhaps Fedora 36) but I'm not sure when I will have time for that.
No, don't waste more your time. Thanks for all your testings.
@rick-masters, #28 resolves, at least, the page faults then?
I didn't include the getcwd code in my live-bootstrap testing. With that fixed though I can try the latest code.
I recently started a new build, but this time I included the line -serial mon:stdio \
in bootfiwix-hd
to be able to press Ctrl-a c
and enter into the QEMU monitor.
Then it was just a matter to wait for another kernel hang:
[...]
/usr/bin/install -c gccbug /tmp/destdir/usr/bin/gccbug
rm -rf /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
mkdir /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
chmod a+rx /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
(cd `${PWDCMD-pwd}`/include ; \
tar -cf - .; exit 0) | (cd /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.)
Once hung I pressed Ctrl-a c
and entered into the QEMU monitor. Once there I used the Magic SysReq key t
to show the list of processes at that time:
QEMU 6.2.0 monitor - type 'help' for more information
(qemu) sendkey alt-sysrq-t
(qemu) sysrq: Task list.
USER PID PPID S SLEEP_ADDR CMD
0 1 0 S 0xc0110500 /init
0 2 0 S 0xc0113a30 kswapd
0 3 0 S 0xc0113de0 kbdflushd
0 50 1 S 0xc0110500 ./x86/bin/kaem
0 164 50 S 0xc0110500 /bin/bash
0 1522 1 Z /usr/bin/sed
0 1523 1 Z /usr/bin/sed
0 1549 1 Z /usr/bin/wc
0 1634 1 Z /usr/bin/wc
0 1803 1 Z /usr/bin/tr
0 1805 1 Z ./configure
0 1808 1 Z /usr/bin/tr
0 1810 1 Z ./configure
0 1813 1 Z /usr/bin/tr
0 1815 1 Z ./configure
0 1818 1 Z /usr/bin/tr
0 1820 1 Z ./configure
0 1828 1 Z /usr/bin/tr
0 1830 1 Z ./configure
0 4584 1 Z /usr/bin/wc
0 5016 1 Z /usr/bin/wc
0 5186 1 Z /usr/bin/tr
0 5188
(The list is longer than normal because I previously tweaked the value NR_CB_QUEUE
in include/tty.h
)
As you can see there are a lot of zombie process not reaped, and all the user processes are sleeping at the address 0xc0110500
which, according to readelf
, is the sys_wait4()
function:
$ readelf -a fiwix | grep c0110500
1129: c0110500 548 FUNC GLOBAL DEFAULT 2 sys_wait4
This leads me to a question. Is the program /init
properly reaping children?
No, the init program in live-bootstrap is a script which does not reap. This is a problem that I've known about for a while. The reason for all the orphaned processes is due to a bug in bash which occurs only when compiled without job control, which is how live-bootstrap compiles it. bash only waits for the last process in a pipeline to complete and orphans the rest.
I tried for a while to fix bash but it was too hard and so I just put in a workaround of increasing the relevant limits in Fiwix.
After working all these days on this, I've been able to detect (and hopefully fix) a number of possible race conditions. Check my recent commits (0aca07c7fddb22f7f1928f0a1efbae21425c878d, 9b86e0ebf853a6362341d648daa1c47392651eed and 4fb552fd8eeb39d06d8be0d1cabc2d244f44554d).
Still, I'm seeing a hang all the time and in the same exact place:
[...]
/usr/bin/install -c gccbug /tmp/destdir/usr/bin/gccbug
rm -rf /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
mkdir /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
chmod a+rx /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/include
(cd `${PWDCMD-pwd}`/include ; \
tar -cf - .; exit 0) | (cd /tmp/destdir/usr/lib/i386-unknown-linux-musl/gcc/i386-unknown-linux-musl/4.0.4/i...
This made me think that instead of tweaking the limits in Fiwix, you could try trap "" SIGCHLD
as explained here (from here).
If the kernel detects that the process is ignoring SIGCHLD it will reap all children automatically:
In all, I'm working now to fix a possible race condition in a memory page.
Yes, there has been substantial improvement with your recent patches. With one more fix described below, I seeing mostly successful builds now.
There appears to be a deadlock in fs/buffer.c between getblk and kbdflushd. The sequence appears to be:
This sequence results in a deadlock.
The main issue is that kbdflush can unlock a buffer but then does not call wakeup(&buffer_wait) immediately. It can continue looping into get_dirty_buffer and get deadlocked so it never exits its loop to call wakeup(&buffer_wait). So the process waiting in step 3 remains asleep even though the buffer it is waiting for is unlocked.
I have been able to solve this by changing kbdflushd to always call wakeup(&buffer_wait) immediately after it unlocks a buffer. I noticed a similar problem with sync_buffers() and so I applied the same fix that function, although I don't have any evidence that sync_buffers is involved in a similar deadlock.
I still see a page fault in /usr/bin/make while building binutils-2.30 around about 7% of builds but I'm hoping that will be easier to debug.
The main issue is that kbdflush can unlock a buffer but then does not call wakeup(&buffer_wait) immediately. It can continue looping into get_dirty_buffer and get deadlocked so it never exits its loop to call wakeup(&buffer_wait). So the process waiting in step 3 remains asleep even though the buffer it is waiting for is unlocked.
Wow!, this is really a good find. You have a keen eye! :smiley:
Following your explanation, I plan to patch fs/buffer.c
as shown below:
diff --git a/fs/buffer.c b/fs/buffer.c
index 8a596c0..d3df8e8 100644
--- a/fs/buffer.c
+++ b/fs/buffer.c
@@ -488,9 +488,7 @@ void brelse(struct buffer *buf)
void sync_buffers(__dev_t dev)
{
struct buffer *buf, *first;
- int synced;
- synced = 0;
first = NULL;
lock_resource(&sync_resource);
@@ -502,6 +500,7 @@ void sync_buffers(__dev_t dev)
if(first == buf) {
insert_on_dirty_list(buf);
buf->flags &= ~BUFFER_LOCKED;
+ wakeup(&buffer_wait);
break;
}
} else {
@@ -511,19 +510,16 @@ void sync_buffers(__dev_t dev)
if(sync_one_buffer(buf)) {
insert_on_dirty_list(buf);
buf->flags &= ~BUFFER_LOCKED;
+ wakeup(&buffer_wait);
continue;
}
- synced = 1;
} else {
insert_on_dirty_list(buf);
}
buf->flags &= ~BUFFER_LOCKED;
- }
- unlock_resource(&sync_resource);
-
- if(synced) {
wakeup(&buffer_wait);
}
+ unlock_resource(&sync_resource);
}
void invalidate_buffers(__dev_t dev)
@@ -620,6 +616,7 @@ int kbdflushd(void)
if(first == buf) {
insert_on_dirty_list(buf);
buf->flags &= ~BUFFER_LOCKED;
+ wakeup(&buffer_wait);
break;
}
} else {
@@ -629,9 +626,11 @@ int kbdflushd(void)
if(sync_one_buffer(buf)) {
insert_on_dirty_list(buf);
buf->flags &= ~BUFFER_LOCKED;
+ wakeup(&buffer_wait);
continue;
}
buf->flags &= ~BUFFER_LOCKED;
+ wakeup(&buffer_wait);
flushed++;
if(flushed == NR_BUF_RECLAIM) {
@@ -643,7 +642,6 @@ int kbdflushd(void)
}
}
unlock_resource(&sync_resource);
- wakeup(&buffer_wait);
}
}
Still, I keep getting the same hang all the time. Please, let me know if your patch is different.
I am surprised that your live-bootstrap builds are still always failing. Did your most recent commit make any difference?
I've constructed a new branch based on your latest code, the live-bootstrap related patches, your fix to mm/page.c in comment https://github.com/mikaku/Fiwix/issues/27#issuecomment-1493317797, the deadlock fix from your last comment, and some additional diagnostics.
That branch is here: https://github.com/rick-masters/Fiwix/tree/fiwix-1.4.0-lb-e1bf632
The commit with diagnostics that I have linked below may be helpful. I used this code to diagnose the deadlock. Of course, the first thing is to determine if the processes are sleeping and if so, what they are waiting for. The commit below shows more information about processes sleeping on buffer_wait. I added information to the process to record the location in the code of the sleep call and I added information to the buffer to record where the buffer was locked. Finally, I added this information to the sysrq output and filtered out zombies. Of course this only applies if your process is sleeping on buffer_wait but maybe you could create similar diagnostics for your situation.
https://github.com/rick-masters/Fiwix/commit/8eb85ca9f32e0488177f1bd2a3c51424696fffc8
Finally, I'm attaching the kernel that I built from this branch. Perhaps you could try that?
Recently I haven't had any failures. I was previously having occasional page faults but then I made some minor changes to add diagnostics and now the problem does not happen so I'm a little confused right now. I may have to backtrack on some fixes to reproduce the tar/pipe hang that you are still seeing and try to determine if there is problem that our recent fixes do not address. But you may be in a better position to track it down if you are still seeing it with the latest branch/kernel I have provided. fiwix.gz
Did your most recent commit make any difference?
No, unfortunately it still hangs 100% of the time and always at the same place.
The commit with diagnostics that I have linked below may be helpful. I used this code to diagnose the deadlock. Of course, the first thing is to determine if the processes are sleeping and if so, what they are waiting for. The commit below shows more information about processes sleeping on buffer_wait. I added information to the process to record the location in the code of the sleep call and I added information to the buffer to record where the buffer was locked. Finally, I added this information to the sysrq output and filtered out zombies. Of course this only applies if your process is sleeping on buffer_wait but maybe you could create similar diagnostics for your situation.
I appreciate your help. I hope this type of diagnose will help me to find issues.
Finally, I'm attaching the kernel that I built from this branch. Perhaps you could try that?
Sure, just tested it and the build completed successfully! It took 1h 30min (aprox.), but it was worth the wait. :smiley:
OK, once I know your kernel was also working here, I decided to clone your new branch fiwix-1.4.0-lb-e1bf632 and see if the build also completes.
So I just cloned it and compiled as it is, I mean, without applying any patch nor touching any file. By the way, the resulting binary kernel here has 316582 bytes, while yours has 400660 bytes. I guess this is because of the different GCC compilers we are using (remember, I'm using vanilla GCC 4.7.4).
Finally I copied that kernel and started the new build:
cp ~/fiwix-1.4.0-lb-e1bf632/fiwix ./kernel
./rootfs.py --qemu --kernel kernel --kernel-fiwix-hd
[building ...]
Good news, so far it looks like the build will also complete because it has passed the critical point where it hung all the time.
This means that (if the build really succeeds) I'll need to check the differences between your recent branch e1bf632 and 73f4c28 that included my patches, and see where is the difference.
By the way, the kernel I gave you was compiled with tcc so that explains the size difference but it also succeeds for me if I build it with gcc.
By the way, the kernel I gave you was compiled with tcc so that explains the size difference
Ahh, that explains it. Hmm, I don't know why I thought that using tcc would reduce the size of the kernel. Perhaps because tcc is lighter. Probably GCC has very strong code optimizations.
Anyway, the build completed successfully. So before closing this issue, I'll like to know what was the culprit responsible of those hangs.
I'll work on it tomorrow.
With only copying the file fs/buffer.c
from the branch https://github.com/mikaku/Fiwix/commit/e1bf63201761080a6b98ec7064b52d9f42cf7186 to https://github.com/mikaku/Fiwix/commit/73f4c28f362a55e6d867739fffdf4591d7e552b7 (and removing your diagnose lines) the build doesn't hang anymore and completes successfully.
There is only one difference between the two files, the branch https://github.com/mikaku/Fiwix/commit/73f4c28f362a55e6d867739fffdf4591d7e552b7 didn't have the commit https://github.com/mikaku/Fiwix/commit/c9934ba1546f52c197e03f774eb44ac95b276548. It seems I forgot to apply it.
The new reclaim_buffers()
function is simpler and more efficient than the previous one. The problem was that the old version was late to remove the buffer from the hash queue and gave chance to other process to get the same buffer and lock it. A simple early location of remove_from_hash(buf);
has been enough to see the build completed.
Anyway, as this is old code, it doesn't seem worth it to spend more time on it.
Thank you very much.
I am using a kernel which can be built this way:
By the way, this is a fork based on your commit 73f4c28f362a55e6d867739fffdf4591d7e552b7 from March 22, 2023. This is the most recent commit that I was able to get working with my changes. If I include the next commit 58ca771f135779113f5181f36fea353909d92425 then live-bootstrap fails with page faults in the
cp
command. I'm looking into that but for now I am unable to provide a fork based on the latest code. However, most of your recent ATA/PCI changes are in the fork I have provided.With that, testing with hard drive does not work:
The hard drive variation fails in various ways. Usually it is a lockup but it may also be a page fault or qemu may simply exit for an unknown reason.
Testing with ram drive does work:
A successful run ends after Linux has been compiled and there is a mount error "Only root can do that". This is a normal ending for Fiwix because Fiwix cannot perform a Linux kexec.
I should note that for both cases there may be a long delay (about a minute) after the "Booting from ROM..." message is displayed. I am not sure why there is a delay and it may depend on your version of qemu but it does start eventually. This delay is an unrelated problem.
For hard drive testing, A difference in behavior can be produced by changing include/fiwix/ata.h:
From this:
To this:
This change will improve the failure rate from 100% to 15% for me. It may appear to work but it does fail regularly so this is not a full solution. For me this change also causes a startup delay for Fiwix of over 6 minutes!
Some information on live-bootstrap may be helpful. Fundamentally live-bootstrap is just creating a drive image and then launching qemu. The scripts that launch qemu are named bootfiwix-rd and bootfiwix-hd and can be found in the root of the live-bootstrap repository. The ram drive and hard drive variations use the exact same ext2 file system. The only difference is that with the hard drive method an MBR with partition table and some padding sectors are prepended to the file system and the qemu options are different.