headers
Andre Oppermann | 1 Oct 2010 10:54
Picon
Favicon

Re: Examining the VM splay tree effectiveness

On 30.09.2010 19:51, Ivan Voras wrote:
> On 09/30/10 18:37, Andre Oppermann wrote:
>
>> Both the vmmap and page table make use of splay trees to manage the
>> entries and to speed up lookups compared to long to traverse linked
>> lists or more memory expensive hash tables.  Some structures though
>> do have an additional linked list to simplify ordered traversals.
>
> The property of splay tree requiring *writes* for nearly every read
> really is a thorn in the eye for SMP. It seems to me that even if the
> immediate benefits from converting to something else are not directly
> observable, it will still be worth doing it.

Fully agreed.

> It's a shame that RCU is still a patent minefield :/
>
> http://mirror.leaseweb.com/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf

I'm not convinced that RCU is the only scalable way of sharing a
data structure across a possibly large number of CPU's.

The term "lockless" is often used and frequently misunderstood.
Having a lockess data structure *doesn't* mean that is either
performant, scalable or both.  It heavily depends on a number
of additional factors.  Many times "lockless" just replaces a
simple lock/unlock cycle with a number of atomic operations on
the data structure.  This can easily backfire because an atomic
operation just hides the computational complexity and also dirties
the CPU's cache lines.  Generally on cache coherent architectures
(Continue reading)

Permalink | Reply | 1 comment |
headers
Ed Schouten | 1 Oct 2010 20:28
Picon
Gravatar

Re: Examining the VM splay tree effectiveness

Andre,

* Andre Oppermann <andre <at> freebsd.org> wrote:
> A splay tree is an interesting binary search tree with insertion,
> lookup and removal performed in O(log n) *amortized* time.  With
> the *amortized* time being the crucial difference to other binary trees.
> On every access *including* lookup it rotates the tree to make the
> just found element the new root node.  For all gory details see:
>  http://en.wikipedia.org/wiki/Splay_tree

Even though a red-black tree is quite good since it guarantees a $2 \log
n$ upperbound, the problem is that it's quite computationally intensive.

Maybe it would be worth looking at other types of balanced trees? For
example, another type of tree which has only $O(\log n)$ amortized
insertion/removal/lookup time, but could already be a lot better in
practice, is a Treap.

Greetings,
--

-- 
 Ed Schouten <ed <at> 80386.nl>
 WWW: http://80386.nl/
Permalink | Reply | 1 comment |
headers
Paul B Mahol | 3 Oct 2010 15:53
Picon
Gravatar

Improve OptionalObsoleteFiles.inc

Hi,

diff --git a/tools/build/mk/OptionalObsoleteFiles.inc
b/tools/build/mk/OptionalObsoleteFiles.inc
index d3aa4b2..2123107 100644
--- a/tools/build/mk/OptionalObsoleteFiles.inc
+++ b/tools/build/mk/OptionalObsoleteFiles.inc
 <at>  <at>  -141,6 +141,7  <at>  <at>  OLD_FILES+=usr/share/man/man8/authpf.8.gz
 .endif

 .if ${MK_BIND} == no
+OLD_FILES+=etc/periodic/daily/470.status-named
 OLD_FILES+=usr/bin/dig
 OLD_FILES+=usr/bin/host
 OLD_FILES+=usr/bin/nslookup
 <at>  <at>  -943,6 +944,7  <at>  <at>  OLD_FILES+=rescue/ping6
 #.endif

 .if ${MK_IPFILTER} == no
+OLD_FILES+=etc/periodic/security/510.ipfdenied
 OLD_FILES+=rescue/ipf
 OLD_FILES+=sbin/ipf
 OLD_FILES+=sbin/ipfs
 <at>  <at>  -1517,6 +1519,20  <at>  <at>  OLD_FILES+=usr/share/man/man8/verify_krb5_conf.8.gz
 # to be filled in
 #.endif

+.if ${MK_LOCATE} == no
+OLD_FILES+=etc/locate.rc
+OLD_FILES+=etc/periodic/weekly/310.locate
(Continue reading)

Permalink | Reply | 11 comments |
headers
Ivan Voras | 3 Oct 2010 20:24
Picon
Favicon
Gravatar

Re: Examining the VM splay tree effectiveness

On 10/01/10 10:54, Andre Oppermann wrote:
> On 30.09.2010 19:51, Ivan Voras wrote:
>> On 09/30/10 18:37, Andre Oppermann wrote:
>>
>>> Both the vmmap and page table make use of splay trees to manage the
>>> entries and to speed up lookups compared to long to traverse linked
>>> lists or more memory expensive hash tables.  Some structures though
>>> do have an additional linked list to simplify ordered traversals.
>>
>> The property of splay tree requiring *writes* for nearly every read
>> really is a thorn in the eye for SMP. It seems to me that even if the
>> immediate benefits from converting to something else are not directly
>> observable, it will still be worth doing it.
> 
> Fully agreed.
> 
>> It's a shame that RCU is still a patent minefield :/
>>
>> http://mirror.leaseweb.com/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf
>>
> 
> I'm not convinced that RCU is the only scalable way of sharing a
> data structure across a possibly large number of CPU's.

Of course, it's just well understood currently.

> The term "lockless" is often used and frequently misunderstood.
> Having a lockess data structure *doesn't* mean that is either
> performant, scalable or both.  It heavily depends on a number
> of additional factors.  Many times "lockless" just replaces a
(Continue reading)

Permalink | Reply | 0 comments |
headers
Ivan Voras | 3 Oct 2010 21:42
Picon
Favicon
Gravatar

Re: Examining the VM splay tree effectiveness

On 10/01/10 20:28, Ed Schouten wrote:
> Andre,
> 
> * Andre Oppermann <andre <at> freebsd.org> wrote:
>> A splay tree is an interesting binary search tree with insertion,
>> lookup and removal performed in O(log n) *amortized* time.  With
>> the *amortized* time being the crucial difference to other binary trees.
>> On every access *including* lookup it rotates the tree to make the
>> just found element the new root node.  For all gory details see:
>>  http://en.wikipedia.org/wiki/Splay_tree
> 
> Even though a red-black tree is quite good since it guarantees a $2 \log
> n$ upperbound, the problem is that it's quite computationally intensive.
> 
> Maybe it would be worth looking at other types of balanced trees? For
> example, another type of tree which has only $O(\log n)$ amortized
> insertion/removal/lookup time, but could already be a lot better in
> practice, is a Treap.

How many elements are held in vm_map trees? From the source it looks
like one tree with all pages in the system and then one per-process?

Trees have very varied real-time characteristics, e.g.:

http://attractivechaos.awardspace.com/udb.html
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6795&rep=rep1&type=pdf

_______________________________________________
freebsd-hackers <at> freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
(Continue reading)

Permalink | Reply | 0 comments |
headers
Garrett Cooper | 3 Oct 2010 22:44
Picon
Favicon

Re: Improve OptionalObsoleteFiles.inc

On Sun, Oct 3, 2010 at 6:53 AM, Paul B Mahol <onemda <at> gmail.com> wrote:
> Hi,
>
>
> diff --git a/tools/build/mk/OptionalObsoleteFiles.inc
> b/tools/build/mk/OptionalObsoleteFiles.inc
> index d3aa4b2..2123107 100644
> --- a/tools/build/mk/OptionalObsoleteFiles.inc
> +++ b/tools/build/mk/OptionalObsoleteFiles.inc
>  <at>  <at>  -141,6 +141,7  <at>  <at>  OLD_FILES+=usr/share/man/man8/authpf.8.gz
>  .endif
>
>  .if ${MK_BIND} == no
> +OLD_FILES+=etc/periodic/daily/470.status-named
>  OLD_FILES+=usr/bin/dig
>  OLD_FILES+=usr/bin/host
>  OLD_FILES+=usr/bin/nslookup
>  <at>  <at>  -943,6 +944,7  <at>  <at>  OLD_FILES+=rescue/ping6
>  #.endif
>
>  .if ${MK_IPFILTER} == no
> +OLD_FILES+=etc/periodic/security/510.ipfdenied
>  OLD_FILES+=rescue/ipf
>  OLD_FILES+=sbin/ipf
>  OLD_FILES+=sbin/ipfs
>  <at>  <at>  -1517,6 +1519,20  <at>  <at>  OLD_FILES+=usr/share/man/man8/verify_krb5_conf.8.gz
>  # to be filled in
>  #.endif
>
> +.if ${MK_LOCATE} == no
(Continue reading)

Permalink | Reply | 0 comments |
headers
Alan Cox | 4 Oct 2010 02:03
Picon

Re: page table fault, which should map kernel virtual address space

On Thu, Sep 30, 2010 at 6:28 AM, Svatopluk Kraus <onwahe <at> gmail.com> wrote:

> On Tue, Sep 21, 2010 at 7:38 PM, Alan Cox <alan.l.cox <at> gmail.com> wrote:
> > On Mon, Sep 20, 2010 at 9:32 AM, Svatopluk Kraus <onwahe <at> gmail.com>
> wrote:
> >> Beyond 'kernel_map', some submaps of 'kernel_map' (buffer_map,
> >> pager_map,...) exist as result of 'kmem_suballoc' function call.
> >> When this submaps are used (for example 'kmem_alloc_nofault'
> >> function) and its virtual address subspace is at the end of
> >> used kernel virtual address space at the moment (and above 'NKPT'
> >> preallocation), then missing page tables are not allocated
> >> and double fault can happen.
> >>
> >
> > No, the page tables are allocated.  If you create a submap X of the
> kernel
> > map using kmem_suballoc(), then a vm_map_findspace() is performed by
> > vm_map_find() on the kernel map to find space for the submap X.  As you
> note
> > above, the call to vm_map_findspace() on the kernel map will call
> > pmap_growkernel() if needed to extend the kernel page table.
> >
> > If you create another submap X' of X, then that submap X' can only map
> > addresses that fall within the range for X.  So, any necessary page table
> > pages were allocated when X was created.
>
> You are right. Mea culpa. I was focused on a solution and made
> too quick conclusion. The page table fault hitted in 'pager_map',
> which is submap of 'clean_map' and when I debugged the problem
> I didn't see a submap stuff as a whole.
(Continue reading)

Permalink | Reply | 1 comment |
headers
Garrett Cooper | 4 Oct 2010 04:33
Picon
Gravatar

Fix mfiutil compile with -DDEBUG

    make -DDEBUG is broken in mfiutil:

$ make -DDEBUG
cc -O2 -pipe -fno-strict-aliasing -pipe -O2 -march=nocona
-fno-builtin-strftime -DDEBUG -Wall -Wcast-align -Woverflow
-Wsign-compare -Wunused -std=gnu99 -fstack-protector -Wsystem-headers
-Werror -Wall -Wno-format-y2k -W -Wno-unused-parameter
-Wstrict-prototypes -Wmissing-prototypes -Wpointer-arith
-Wno-uninitialized -Wno-pointer-sign -c
/usr/src/usr.sbin/mfiutil/mfi_config.c
/usr/src/usr.sbin/mfiutil/mfi_config.c: In function 'dump_config':
/usr/src/usr.sbin/mfiutil/mfi_config.c:1027: error: 'union mfi_pd_ref'
has no member named 'device_id'
/usr/src/usr.sbin/mfiutil/mfi_config.c:1083: error: 'union mfi_pd_ref'
has no member named 'device_id'
*** Error code 1

Stop in /usr/src/usr.sbin/mfiutil.
$

    device_id is a field in the v field in the mfi_pd_ref union
(/sys/dev/mfi/mfireg.h):

union mfi_pd_ref {
        struct {
                uint16_t        device_id;
                uint16_t        seq_num;
        } v;
        uint32_t        ref;
} __packed;
(Continue reading)

Permalink | Reply | 1 comment |
headers
Garrett Cooper | 4 Oct 2010 05:32
Picon
Gravatar

Re: Make mfiutil(8) more robust

On Sun, Oct 3, 2010 at 8:30 PM, Garrett Cooper <yanegomi <at> gmail.com> wrote:
>    As discussed offlist with some of the Yahoo! FreeBSD folks,
> mfiutil catches errors, but doesn't communicate it back up to the
> executing process. Examples follow...
>    Before:
>
> $ ./mfiutil show adapter
> mfiutil: mfi_open: Permission denied
> $ echo $?
> 0
>
>    (I would expect it to exit with a non-zero exit code)
>    After:
>
> $ ./mfiutil show adapter
> mfiutil: mfi_open: Permission denied
> $ echo $?
> 1
>
>    (Much better!)
>
> $ sudo ./mfiutil show adapter
> mfi0 Adapter:
>    Product Name: MegaRAID SAS 8704ELP
>   Serial Number: P391734409
>        Firmware: 11.0.1-0026
>     RAID Levels: JBOD, RAID0, RAID1, RAID5, RAID6, RAID10, RAID50
>  Battery Backup: present
>           NVRAM: 32K
>  Onboard Memory: 128M
(Continue reading)

Permalink | Reply | 1 comment |
headers
Alexander Leidinger | 4 Oct 2010 12:23
Favicon

Re: Improve OptionalObsoleteFiles.inc

Quoting Paul B Mahol <onemda <at> gmail.com> (from Sun, 3 Oct 2010 13:53:26 +0000):

> Hi,
>
>
> diff --git a/tools/build/mk/OptionalObsoleteFiles.inc
> b/tools/build/mk/OptionalObsoleteFiles.inc
> index d3aa4b2..2123107 100644
> --- a/tools/build/mk/OptionalObsoleteFiles.inc
> +++ b/tools/build/mk/OptionalObsoleteFiles.inc
>  <at>  <at>  -141,6 +141,7  <at>  <at>  OLD_FILES+=usr/share/man/man8/authpf.8.gz
>  .endif
>
>  .if ${MK_BIND} == no
> +OLD_FILES+=etc/periodic/daily/470.status-named

If bind is installed from ports instead, this file could be useful, isn't it?

>  OLD_FILES+=usr/bin/dig
>  OLD_FILES+=usr/bin/host
>  OLD_FILES+=usr/bin/nslookup

[...]

>  <at>  <at>  -1976,6 +1998,11  <at>  <at>  OLD_FILES+=usr/share/man/man8/rtquery.8.gz
>  .endif
>
>  .if ${MK_SENDMAIL} == no
> +OLD_FILES+=etc/periodic/daily/150.clean-hoststat
> +OLD_FILES+=etc/periodic/daily/210.backup-aliases
(Continue reading)

Permalink | Reply | 9 comments |

Gmane