linux-kernel - Re: Does the kernel page the CFS's red-black tree nodes?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <AANLkTilOK580U03orIO6jcMvzrHeNsykLSMkdlw0hZLI@mail.gmail.com>
Date:	Tue, 15 Jun 2010 20:55:20 -0400
From:	Richard Yao <shiningarcanine@...il.com>
To:	linux-kernel@...r.kernel.org
Subject: Re: Does the kernel page the CFS's red-black tree nodes?

Dear Linus Torvalds et all:

I read a recently published article on the ACM website, which
discusses the effect virtual memory pressure has on certain algorithms
and explains that data structures need to be designed in such a way
that they minimize such effects:

http://queue.acm.org/detail.cfm?id=1814327

The author observed slow-downs in an algorithm that ignored virtual
memory upon the incidence of page faults. The basic idea I took from
it is that people should use B-Heaps instead of Binary Heaps and
B-Trees instead of Binary Trees for optimal performance on modern
systems that use virtual memory. Today, it occurred to me that the
kernel's completely fair scheduler could be susceptible this sort of
slow-down, provided that the kernel pages its red-black tree nodes to
swap, so I thought I would ask here if this is the case.

With that said, does the kernel page the CFS's red-black tree nodes to
swap? If it does, it might be a good idea to reimplement the CFS'
Red-Black trees in B-Trees, which would minimize slow-downs from
vm-pressure and also have the additional benefit of minimizing cache
misses caused by tree traversal.

This is my first post to the kernel mailing list. The FAQ says that I
should indicate that I "wish to be personally CC'ed the
answers/comments posted to the list in response" to my posting, so
this sentence is my indication that I "wish to be personally CC'ed the
answers/comments posted to the list".

Yours truly,
Richard Yao
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/