Indeed, thanks for the triaging!

Debian packages for patched Hurd (with RC1+20040304) and patched e2fsprogs can be downloaded using this apt source:

deb http://people.debian.org/~mbanck/hurd/ ./

Marco Gerards wrote:

> (default pager): dropping data_request because of previous paging errors
>
> Perhaps this has something to do with forgetting to put swap in
> /etc/fstab after installing this system, but it should not happen
> because I have 390MB RAM.  Please test this.  I have used bonnie++ for
> this (it is in debian).

After searching with google, it seems that it's highly probable that the missing swap is the reason[1].  Another possible reason is bad sectors.

[1] http://lists.debian.org/debian-hurd/2002/debian-hurd-200207/msg00038.html

Anyway, I'll definately try bonnie++ before releasing RC2.

Changes in RC1+20040304:

• ihash* -> hurd_ihash* (use revised libihash API)
• block << log2_block_size -> (off_t) block << log2_block_size (`block' is usually 32-bit and stores larger than 4G didn't work with old code)
• sleep(1) is called only when all cached blocks are referenced.

There are some other minor changes.

Marco Gerards wrote:

> disk_pager_read_page removes the RC_MAPPING bit from the flags and
> notices the disk_cache_wait_remapping that it is safe to continue.
> But you broadcast the condition before removing the bit.  I think this
> can cause some problems, what do you think?

You're right, but this has no practical sequences, because condition_wait will continue after unlocking of disk_cache_lock in disk_pager_read_page.  See below.  Anyway, I'll change this (swap broadcast and clearing the flag) in RC2.

> How about the loop that touches all pages?  I read touch as writing,
> does it make pages dirty?  If that happens it is not acceptable.  when
> it reads in a page that was evicted it is just an unfortunate waste of
> resources but ok for me (but I do not think everyone will agree with
> me).  Better fix it in Mach.

Here "touch" is used as "peek".  Il'l change that too.

And, really, Mach should be fixed.  But I don't have time resource to do this, and Mach code is famous for being unpleasent to read.

> When there are no pages free you just throw the entire cache away (if
> I understand it correctly).  I do not like this because this can be
> one of the main factors that will slow down someone's computer.  Isn't
> it possible to ask Mach to evict 10 pages (for example)?  Mach usually
> knows better which pages should be evicted.  If that is not possible
> you can just evict 10 pages (10 was randomly chosen) and evict the
> non-dirty pages first.

In the text, there is some rationale behind flushing all pages with reference count zero.  Dirty pages are not flushed, because they have refcount > 0.  (Dirty pages are always in some pokel or are synced before deref.)

There is another way for fine-grained flushing of pages. disk_cache_hint cycles through whole cache and is used for finding unreferenced block which is not in core (i.e. evicted).  So next 5-10 unreferenced blocks after disk_cache_hint can be flushed (pager_return_some) and another try can be made.  Synchronization between pager_notify_pageout and disk_cache_map is not clear to me right now, though.  I'll try to implement it for RC2.

> There is some possible locking problem:
> The call disk_cache_wait_remapping is called with disk_cache_lock
> locked.  The condition in disk_pager_read_page is broadcasted while
> disk_cache_lock is locked too.

This is by design.  condition_wait unlocks the lock and waits.  When condition is broadcasted, it locks the lock again, potentially blocking the thread.  In our case, this will make disk_cache_wait_remapping to wait until disk_pager_read_page unlocks disk_cache_lock.

> Please be really careful with a global lock like disk_cache_lock.  It
> cannot make it hard to prevent deadlocks, it can slow ext2fs down
> too.  I do not know if there is another way though.

Yes, but in our case I see no way to avoid it too.

> Have you fixed the bug I reported BTW?

No, unfortunately I still haven't found time for debugging   But this is something that must be fixed before RC2.

Marco Gerards wrote:

> Ognyan Kulev <ogi@fmi.uni-sofia.bg> writes:
>
>> Marco Gerards wrote:
>>
> No, it is not fixed.  It is just that the kernel determines the amount
> of mapped blocks (all individual mappings) and when which mapping
> should be removed.

This is the "next level".  I though about it: http://www.mail-archive.com/bug-hurd@gnu.org/msg07001.html .  But we better focus on fixed size of cache, as changing to floating mapped blocks is not trivial task.

>> It's just that: GNU Mach is instructed to notify us about evicted
>> pages, but it doesn't.  This is not rare case.  The code above is
>> work-around. It first touches all pages and then synces them all.
>> Fortunately this seems to always work.
>
>
> Does this problem cause any problems for currently use ext2fs?

No, because current ext2fs doesn't need notification on evicting page. This seems to happen only on precious clean pages and on eviction sometimes Mach "forgets" to notify us although they are marked as precious.  Current ext2fs doesn't rely on precious pages in any way.

>> The "starving" happens when all blocks are in use.  That is, each
>> block has reference count > 0 and it can't be replaced.  So the best
>> we can hope of is to wait for some other thread to release block.
>
>
> Ok, I understand.  Thinking of this (the amount of threads and the
> amount of blocks that will be referenced by just one thread) it will
> be very unlikely that this will ever happen.
>
> Because this rarely happens it would be wise to test this (perhaps by
> setting DISK_CACHE_BLOCKS to a lower value?).  Did this ever happen
> while you were testing it?

Usually I run with DISK_CACHE_BLOCKS=20.  The minimum seems to be around 10-15.  Below that it's impossible to compile large source like Hurd's.  The uploaded patch has DISK_CACHE_BLOCKS=100, but it should be largened, of course.

So yes, on low values (10-15) I observed this "starving" and depending on what you are doing, you either enter endless loop, or the sleep does its job and ext2fs continues.

> I am thinking if it is possible to prevent this from happening
> completely.  I will come back to this later.

Probably the starving can't be avoided.  And the other case, when no evicted page is found, will be very, very rare when cache is 512M (for example).

Thanks for your fast response.
(The sourcecode I copied into this reply is not really well formatted after copying, it seems)

Because you have tested it only on a 3GB partition I can do just the same.

About the ChangeLog patch, I think you can better leave it out. (I've included things like that, but now I notice a lot of noise can be annoying while reading patches)

Can you please describe how your patches work? I am familiar with how Neal proposed to fix it. So please describe the theory behind your patch and which function is doing that what you describe.

Because this patch it quite big and many people who don't have the time want to discuss it such explanation is important for acceptation of the patch. And such explanation will help me a lot while reading the patch.

Something I have noticed is that there is a disk_cache_blocks. I do not understand why you have that. You can easily map in every page and let GNUMach decide to evict the page (like Neal proposed). But before I can say more about it I can better wait for your reply.

The same is true for pokels. They are there to keep track of all the metadata in memory so you can write it easily to disk when syncing. I assume you have datastructures for your cache that hold this information as well, do you still need the pokel stuff? Well, perhaps I am misunderstanding something about pokels or your patch (because I do not fully understand it yet, give me a bit more time for that :)).

I think we can better discuss all this on the mailinglist. (because not everyone has a look at savannah and the mail notification to bug-hurd is broken)

Some things I have noticed so far:

      /* XXX: Touch all pages.  It seems that sometimes GNU Mach
         "forgets" to notify us about evicted pages.  */
      for (vm_offset_t i = 0; i < disk_cache_size; i += vm_page_size)
        (volatile char )(disk_cache + i);
Why do you need that? What happens when it isn't used?

And doesn't this mean al pages get dirty??

In disk_cache_map:

  bptr = ihash_find (disk_cache_bptr, block);
  if (bptr)
      ...
      return bptr;
    }

Personally I would use "return 0" here.

In the same function I see this code:

      if (pending_end >= 0)
        pager_return_some (diskfs_disk_pager,
                           pending_begin * vm_page_size,
                           (pending_end - pending_begin) * vm_page_size,
                           1);
      else
        printf ("ext2fs: disk cache is starving\n");

      /* Give it some time.  This should happen rarely.  */
      sleep (1);

I'm not that happy with this.  Can you explain when it happens (I guess when you run out of cache?) and how sleeping fixes it.

I see some function calls that is enabled in the debugging code. Please make sure the code works the same when debugging is of like it works when it is on. (So, have you tested with debugging off?)

I hope you can explain the theory and reasoning about this all, but in the meanwhile I will continue to read the patch.

These comments are from Marco Gerards: http://mail.gnu.org/archive/html/bug-hurd/2004-02/msg00048.html

> Original Submission:  Finally, the patch is prepared to enter the Hurd.

This is good to hear.  My first impression of the patch was good (by
reading over it very quickly).

I have some comments so far, I will continue to read the patch and
test it later this weekend.

The changelogs can use some work AFAICS.  For example you notice when
you add new local variables, I would not do this.  Another thing you
do is:

        (DC_DONT_REUSE): Likewise.
        (struct disk_cache_info): New struct.
        Add declarations for disk_cache_bptr, disk_cache_info,
        disk_cache_lock and disk_cache_remapping.
        Add declarations for functions disk_cache_map,
        disk_cache_block_ref, disk_cache_block_ref_ptr,
        disk_cache_block_deref and disk_cache_block_is_ref.
        Add declaration for map_hypermetadata.
        (bptr_index): New macro.
        (boffs_ptr): Instead of macro, now it's inline function that uses

I have copied some of the context.  You should do the same for
disk_cache_map, disk_cache_lock and whatever variables, functions and
macros you add as you did for bptr_index.  If you are in doubt, just
read:

http://www.gnu.org/prep/standards_40.html#SEC40

And I noticed you include the ChangeLog entries in the patch,
personally I don't like this, also because you already included it.

I wanted to test the patch before reading it in detail, so I just
did.  When I used it on a small partition it worked for me.  After
that I made a 10GB partition in GNU/Linux, I put about 2.7GB of data
on it.  When I tried copying a directory to this partition an
assertion was triggered.  Here is some information that can hopefully
help you finding the problem:


ext2fs.static.2: ../../hurd/ext2fs/ext2fs.h:330: boffs_ptr: Assertion `ptr'
failed.


(I put the backtraces at the end of the mail)

Perhaps I can debug this problem myself, but I am not promising
anything. :)

> To have a chance RC3 or even RC2 to be committed, please don't stop
> reviewing the code at the first thing you don't like.  List precisely
> all things that need to be changed, so that number of release
> iterations is reduced.

Ok.  I will continue reading the patch and test it.  This is just what
I found so far.

> The patch requires changes in libpager and I don't claim they've been
> done in the best way.  For example, ABI compatibility of libpager is
> broken by this patch.  Again, just specify what should be changed in
> the patch.

Is there any way to prevent breaking the ABI?  And do you think the
changes can be made in a better way?

Thanks,
Marco

(gdb) bt
#0  0x080a5cbc in mach_msg_trap ()
#1  0x0807988a in mach_msg ()
#2  0x080e612d in msg_sig_post ()
#3  0x080b72d7 in kill_port.1 ()
#4  0x080b7425 in kill_pid.0 ()
#5  0x080b76cd in kill ()
#6  0x080b6de5 in raise ()
#7  0x08087ce6 in abort ()
#8  0x08083c70 in __assert_perror_fail ()
#9  0x0804d30c in ext2_alloc_inode (dir_inum=454274, mode=16877)
    at ../../hurd/ext2fs/ext2fs.h:342
#10 0x0804daa8 in diskfs_alloc_node (dir=0x814c090, mode=16877, node=0x0)
    at ../../hurd/ext2fs/ialloc.c:300
#11 0x0805cce5 in diskfs_create_node (dir=0x814c090, name=0x108df58 "doc",
    mode=16877, newnode=0x108be24, cred=0x814b1d8, ds=0x108bdfc)
    at ../../hurd/libdiskfs/node-create.c:52
#12 0x0805ee7b in diskfs_S_dir_mkdir (dircred=0x814b1d8, name=0x108df58 "doc",
    mode=16877) at ../../hurd/libdiskfs/dir-mkdir.c:57
#13 0x0805a0eb in _Xdir_mkdir (InHeadP=0x108df3c, OutHeadP=0x108bf3c)
    at fsServer.c:1753
#14 0x0805a93c in diskfs_fs_server (InHeadP=0x108df3c, OutHeadP=0x0)
    at fsServer.c:2679
#15 0x0805862a in diskfs_demuxer (inp=0x108df3c, outp=0x108bf3c)
---Type <return> to continue, or q <return> to quit---
    at ../../hurd/libdiskfs/demuxer.c:40
#16 0x080719ed in internal_demuxer.0 ()
    at ../../hurd/libports/manage-multithread.c:101
#17 0x08079b1b in mach_msg_server_timeout ()
#18 0x08071ade in thread_function.1 ()
    at ../../hurd/libports/manage-multithread.c:136
#19 0x08070694 in cthread_body (self=0x8144d90)
    at ../../hurd/libthreads/cthreads.c:306



(gdb) bt full
#0  0x080a5cbc in mach_msg_trap ()
No symbol table info available.
#1  0x0807988a in mach_msg ()
No symbol table info available.
#2  0x080e612d in msg_sig_post ()
No symbol table info available.
#3  0x080b72d7 in kill_port.1 ()
No symbol table info available.
#4  0x080b7425 in kill_pid.0 ()
No symbol table info available.
#5  0x080b76cd in kill ()
No symbol table info available.
#6  0x080b6de5 in raise ()
No symbol table info available.
#7  0x08087ce6 in abort ()
No symbol table info available.
#8  0x08083c70 in __assert_perror_fail ()
No symbol table info available.
#9  0x0804d30c in ext2_alloc_inode (dir_inum=454274, mode=16877)
    at ../../hurd/ext2fs/ext2fs.h:342
        bh = 0x17000 "\001"
        i = 40
        j = 0
---Type <return> to continue, or q <return> to quit---
        inum = 0
        gdp = (struct ext2_group_desc *) 0x8500
        tmp = (struct ext2_group_desc *) 0x0
#10 0x0804daa8 in diskfs_alloc_node (dir=0x814c090, mode=16877, node=0x0)
    at ../../hurd/ext2fs/ialloc.c:300
        err = 0
        sex = 0
        block = 0
        np = (struct node *) 0x108bdd4
        st = (struct stat *) 0x40000002
        inum = 4611686027017322496
#11 0x0805cce5 in diskfs_create_node (dir=0x814c090, name=0x108df58 "doc",
    mode=16877, newnode=0x108be24, cred=0x814b1d8, ds=0x108bdfc)
    at ../../hurd/libdiskfs/node-create.c:52
        np = (struct node *) 0x0
        err = ENOENT
        newuid = 135577744
        newgid = 135577744
#12 0x0805ee7b in diskfs_S_dir_mkdir (dircred=0x814b1d8, name=0x108df58 "doc",
    mode=16877) at ../../hurd/libdiskfs/dir-mkdir.c:57
        dnp = (struct node *) 0x814c090
        np = (struct node *) 0x0
        ds = (struct dirstat *) 0x108bdfc
---Type <return> to continue, or q <return> to quit---
        error = 1073741826
#13 0x0805a0eb in _Xdir_mkdir (InHeadP=0x108df3c, OutHeadP=0x108bf3c)
    at fsServer.c:1753
        nameCheck = {msgt_name = 12, msgt_size = 8, msgt_number = 1024,
  msgt_inline = 1, msgt_longform = 0, msgt_deallocate = 0, msgt_unused = 0}
        modeCheck = {msgt_name = 2, msgt_size = 32, msgt_number = 1,
  msgt_inline = 1, msgt_longform = 0, msgt_deallocate = 0, msgt_unused = 0}
#14 0x0805a93c in diskfs_fs_server (InHeadP=0x108df3c, OutHeadP=0x0)
    at fsServer.c:2679
        RetCodeType = {msgt_name = 2, msgt_size = 32, msgt_number = 1,
  msgt_inline = 1, msgt_longform = 0, msgt_deallocate = 0, msgt_unused = 0}
        routine = 0
#15 0x0805862a in diskfs_demuxer (inp=0x108df3c, outp=0x108bf3c)
    at ../../hurd/libdiskfs/demuxer.c:40
No locals.
#16 0x080719ed in internal_demuxer.0 ()
    at ../../hurd/libports/manage-multithread.c:101
No locals.
#17 0x08079b1b in mach_msg_server_timeout ()
No symbol table info available.
#18 0x08071ade in thread_function.1 ()
    at ../../hurd/libports/manage-multithread.c:136
No locals.
---Type <return> to continue, or q <return> to quit---
#19 0x08070694 in cthread_body (self=0x8144d90)
    at ../../hurd/libthreads/cthreads.c:306
        t = 0x8144d18

Finally, the patch is prepared to enter the Hurd.

To have a chance RC3 or even RC2 to be committed, please don't stop reviewing the code at the first thing you don't like.  List precisely all things that need to be changed, so that number of release iterations is reduced.

The patch requires changes in libpager and I don't claim they've been done in the best way.  For example, ABI compatibility of libpager is broken by this patch.  Again, just specify what should be changed in the patch.