Re: Please review: lookup changes

[Andrew Doran]

On Sun, Mar 08, 2020 at 09:22:28PM +, Taylor R Campbell wrote:

> Maybe we could use a critbit tree?  It will have cache utilization
> characteristics similar to a red/black tree (fanout is 2 either way),
> but the lookup can be pserialized and each step may be a little
> cheaper computationally.
> 
> https://mumble.net/~campbell/hg/critbit/
> 
> Alternatively, there is rmind's thmap already in tree.

I had a look and this is a really interesting data structure.  I think this
plus a seqlock, and a nice reclamation method would do great.  My only
concern is that single threaded performance should be top notch too because
single component name lookups are often more frequent even than traps and
syscalls put together.  I suppose it's a case of trying it.

Another application I can think of is _lwp_unpark() although the minor
complication there is the radixtree is now used to allocate LIDs too by
scanning for unused slots.

Andrew

Re: Patch: allow concurrent faults on a single uvm_object

[Andrew Doran]

Updated patch for current as of right now.  Only one change, fix an invalid
pointer deref in uvmfault_promote():

http://www.netbsd.org/~ad/2020/fault2.diff

It's not high-tech, no RCU or other fancy stuff, but it does cut system time
during build.sh by 40-50% for me.

Cheers,
Andrew

On Sun, Mar 15, 2020 at 09:40:57PM +, Andrew Doran wrote:

> Hi,
> 
> This address the problem with lock contention due to page faults on libc.so
> and other shared objects.  It also allows for concurrent faults on shared
> amaps, for example PostgreSQL's shared buffer.
> 
> The approach is:
> 
> - Add a PGO_NOBUSY flag that has getpages return pages without busying them. 
>   It has to come with PGO_LOCKED and VM_PROT_WRITE == 0.  This allows
>   getpages to be called with a RW_READER lock for the in-core case.
> 
> - For each fault, keep track of the type of lock on the upper & lower
>   objects.  Start out with the assumption that RW_READER is good for both
>   and then make some guesses to refine that.  If the fault runs into trouble
>   because it has a RW_READER lock, try to upgrade to RW_WRITER and if that
>   fails, give up and restart the fault to happen from the beginning with a
>   RW_WRITER lock.
> 
> - Add a couple of "vmstat -s" counters to see how it does in practice.
> 
> - Allow some more uvm_map() operations with RW_READER on the underlock
>   objects.
> 
> - Cut contention from v_interlock in genfs_getpages by adding a flag that's
>   set earlier with both v_interlock + vmobjlock set.
> 
> Changes here:
> 
>   http://www.netbsd.org/~ad/2020/fault.diff
> 
> Comments welcome.
> 
> Thanks,
> Andrew