Kernel Traffic #201 For 17 Jan 2003

Geert is correct that the functions are generic. The fb_putcs() and fb_setfont() can be compared to Tile blitting. Tile blitting is a common operation in some games such as Warcraft, Starcraft, and most RPG's. I'm think there is Tile Blitting support in DirectFB.

In a tile-based game, the basic unit is a Tile which is just a bitmap with a predefined width and height. The game has several tiles stored in memory each with it's own unique id. To draw the background/layer, a TileMap is constructed which is basically another array. Its format is something like this - TileMap[x] = y which means draw Tile y at screen position x.

In the fbcon perspective, we can think of each character as a Tile, and fontdata as the collection of tiles. fb_char.data is basically a TileMap. Of course, tile blitting in games is more complicated than this, since games have multiple layers for the background, so layer position, transparency, etc has to be considered.

So maybe if we can rename fb_putcs() to fb_tileblit(), fb_setfont() to fb_loadtiles(), struct fb_chars to struct fb_tilemap and struct fb_fontdata to struct fb_tiledata, maybe it will be more acceptable?

It can be even be expanded by including fb_tiledata.depth fb_tiledata.cmap so we can support multi-colored tiled blitting.

Reporting 'No such device' was actually bug which was introduced some time ago but nobody probably noticed it... It was introduce when quota code was converted from device numbers to 'bdev' structures.

I also fixed one bug in quotaon() call however I'm not sure wheter it could cause the freeze. Anyway patch is attached, try it and tell me about the changes.

The userspace test framework I used to develop module loading on different archs is up at:

http://www.kernel.org/pub/linux/kernel/people/rusty/modules/module-test-framework.tar.gz

I found it much easier to use for each arch than doing the crash/reboot cycle (and you can use a real debugger).

BTW, the change to use shared objects for modules is going to be a 2.7 thing: after 10 architectures, MIPS toolchain issues made it non-trivial. So the current stuff is what is going to be there for 2.6, so no point waiting 8)

We were looking at the performance impact of the IRQ routing from the 2.5.52 Linux kernel. This email includes some of our findings about the way the interrupts are getting moved in the 2.5.52 kernel. Also there is discussion and a patch for a new implementation. Let me know what you think at nitin.a.kamble@intel.com

Current implementation:

We have found that the existing implementation works well on IA32 SMP systems with light load of interrupts. Also we noticed that it is not working that well under heavy interrupt load conditions on these SMP systems. The observations are:

• Interrupt load of each IRQ is getting balanced on CPUs independent of load of other IRQs. Also the current implementation moves the IRQs randomly. This works well when the interrupt load is light. But we start seeing imbalance of interrupt load with existence of multiple heavy interrupt sources. Frequently multiple heavily loaded IRQs gets moved to a single CPU while other CPUs stay very lightly loaded. To achieve a good interrupts load balance, it is important to consider the load of all the interrupts together.

  This further can be explained with an example of 4 CPUs and 4 heavy interrupt sources. With the existing random movement approach, the chance of each of these heavy interrupt sources moving to separate CPUs is: (4/4)*(3/4)*(2/4)*(1/4) = 3/16. It means 13/16 = 81.25% of the time the situation is, some CPUs are very lightly loaded and some are loaded with multiple heavy interrupts. This causes the interrupt load imbalance and results in less performance. In a case of 2 CPUs and 2 heavily loaded interrupt sources, this imbalance happens 1/2 = 50% of the times. This issue becomes more and more severe with increasing number of heavy interrupt sources.

• Another interesting observation is: We cannot see the imbalance of the interrupt load from /proc/interrupts. (/proc/interrupts shows the cumulative load of interrupts on all CPUs.) If the interrupt load is imbalanced and this imbalance is getting rotated among CPUs continuously, then /proc/interrupts will still show that the interrupt load is going to processors very evenly. Currently at the frequency (HZ/50) at which IRQs are moved across CPUs, it is not possible to see any interrupt load imbalance happening.

• We have also found that, in certain cases the static IRQ binding performs better than the existing kernel distribution of interrupt load. The reason is, in a well-balanced interrupt load situations, these interrupts are unnecessarily getting frequently moved across CPUs. This adds an extra overhead; also it takes off the CPU cache warmth benefits.

  This came out from the performance measurements done on a 4-way HT (8 logical processors) Pentium 4 Xeon system running 8 copies of netperf. The 4 NICs in the system taking different IRQs generated sizable interrupt load with the help of connected clients.

  Here the netperf transactions/sec throughput numbers observed are:

  IRQs nicely manually bound to CPUs: 56.20K
  The current kernel implementation of IRQ movement: 50.05K
  -----------------------

  The static binding of IRQs has performed 12.28% better than the current IRQ movement implemented in the kernel.

• The current implementation does not distinguish siblings from the HT (Hyper-Threading(tm)) enabled CPUs. It will be beneficial to balance the interrupt load with respect to processor packages first, and then among logical CPUs inside processor packages.

  For example if we have 2 heavy interrupt sources and 2 processor packages (4 logical CPUs); Assigning both the heavy interrupt sources in different processor packages is better, it will use different execution resources from the different processor packages.

New revised implementation:

We also have been working on a new implementation. The following points are in main focus.

• At any moment heavily loaded IRQs are distributed to different CPUs to achieve as much balance as possible.
• Lightly loaded interrupt sources are ignored from the load balancing, as they do not cause considerable imbalance.
• When the heavy interrupt sources are balanced, they are not moved around. This also helps in keeping the CPU caches warm.
• It has been made HT aware. While distributing the load, the load on a processor package to which the logical CPUs belong to is also considered.
• In the situations of few (lesser than num_cpus) heavy interrupt sources, it is not possible to balance them evenly. In such case the existing code has been reused to move the interrupts. The randomness from the original code has been removed.
• The time interval for redistribution has been made flexible. It varies as the system interrupt load changes.
• A new kernel_thread is introduced to do the load balancing calculations for all the interrupt sources. It keeps the balanace_maps ready for interrupt handlers, keeping the overhead in the interrupt handling to minimum.
• It allows the disabling of the IRQ distribution from the boot loader command line, if anybody wants to do it for any reason.
• The algorithm also takes into account the static binding of interrupts to CPUs that user imposes from the /proc/irq/{n}/smp_affinity interface.

Throughput numbers with the netperf setup for the new implementation:

Current kernel IRQ balance implementation: 50.02K transactions/sec
The new IRQ balance implementation: 56.01K transactions/sec
---------------------
The performance improvement on P4 Xeon of 11.9% is observed.

The new IRQ balance implementation also shows little performance improvement on P6 (Pentium II, III) systems.

On a P6 system the netperf throughput numbers are:
Current kernel IRQ balance implementation: 36.96K transactions/sec
The new IRQ balance implementation: 37.65K transactions/sec
---------------------
Here the performance improvement on P6 system of about 2% is observed.

Version 1.10 of my kernel bug database is now on-line at:

http://grabjohn.com/kernelbugdatabase/

Main updates:

• Automatic account creation

  No need to E-Mail a request for an account to me - there is a link to create one if you don't have one already.

• Generate a config file with the same options as the one that was uploaded with the bug report.

  If the original submitter of a bug uploaded their config file, you can download a config file with the same options set.

• Patch database

  Patches can be submitted against a bug report, along with comments, and the facility is in place to automatically test the patch to see if it applies against any number of kernel trees. This will probably not be enabled until the bug database is moved on to another machine which has more disk space for the uncompressed kernel trees.

  It's also possible to browse the available patches, search for strings in patches, and download the patches, (obviously).

• Command line interface improvements

  Eventually intended to be accessible via E-Mail, you can currently test the command line interface via the web. I've added commands related to patch handling.

• Minor enhancements

  Various enhancements, including categorising of drop down lists of kernel versions and config options.

• Various bugfixes

  Various bugfixes and minor enhancaments to improve the bug database overall.

Important note

Bugs in the database are not assigned any kind of status, nor are they assigned to one or more people, for them to work on.

This is intentional - eventually, the best way to use this database will be like this:

• A user uploads their config file, (or an oops, or searches using keywords).
• No bugs are found, or only ones that are nothing to do with the bug the user is experiencing.
• The user submits a bug report
• That bug report is re-named, re-numbered, commented on, or even deleted if it is a duplicate, by developers, until eventually a patch is posted that fixes it.
• The original user uploads their config file, again a week later and gets a list of bug reports back which match certain options in it, which the developers have identified as causing the bugs.
• That list now includes the bug that the user is experiencing, and hopefully also includes a patch to fix it.
• The user downloads the patch, and can also get information about which new kernel versions it can be applied to, and by going back to the bug list, can also find out which new kernel versions the bug is actually fixed in.

Note that if a user's original bug report is actually a duplicate of an existing bug in the database, the bug report can simply be deleted, (possibly after moving comments, patches, etc, from it to the original bug).

As long as the original user does not rely on tracking the bug report by number, and instead searches via config options, (which can be as easy as uploading the relevant .config file), they should still find any applicable comments and patches that the developers have submitted. A list of kernels that any available patches successfully apply to can easily be downloaded, saving even more time in cases where a patch is made against one tree, and the user wants to apply it to another tree, (for example, because of other bugs preventing the latest kernel version from being usable on their machine).

No, you don't just get a copy of the original config file:

When a config file is uploaded to the system, it's parsed and the actual config options are stored in a database. If comments are present in a form that resembles what the existing kernel configurators use to indicate different sections, then those comments are used to categorise the config options in the database.

The main reason for this is so that if somebody reports a bug, and includes their config information, a developer can select one of their config options from a list, and indicate that the bug is triggered by it.

Re-generating the config file from that database, so that somebody else can download it was added as an afterthought :-). Comments are re-inserted, as well as an additional comment showing which kernel version the config was originally intended for.

The Linux Test Project test suite LTP-20030110.tgz has been released. Visit our website (http://ltp.sourceforge.net) to download the latest version of the testsuite, and for information on test results on pre-releases, release candidates & stable releases of the kernel. There is also a list of test cases that are expected to fail, please find the list at (http://ltp.sourceforge.net/expected-errors.php)

The highlights of this release are:

• Many new tests from Wipro.
• Many new SPIE tests ported.
• More than 40 new tests.
• LTP now has over 900 tests.
• Many bug-fixes

We encourage the community to post results, patches, or new tests on our mailing list, and to use the CVS bug tracking facility to report problems that you might encounter. More details available at our web-site.

NGPT - Next Generation POSIX Threading

NGPT Release 2.2.0, released today, 10 January 2003, is the next release of the "Next Generation" of Linux pthreads support. This release is fully suitable as a replacement for LinuxThreads by either a single user or group or an entire distribution.

In this release, the primary focus was performance. Significant performance and scalability enhancements have been made to this release making it the fastest and most scalable POSIX compliant threads package available on the Linux platform.

In this release, performance and scalability were the key focus of NGPT developers. Performance and scalability were improved to the point where NGPT bests both LinuxThreads and the new NPTL threading package in benchmarks. No changes were made to the kernel patches and thanks to the NPTL effort, all changes required to run NGPT on the latest 2.5.x kernels are already included.

Performance and scalability were measured using a benchmark program developed by Sun Microsystems to "prove" that a 1:1 threading model is better than the M:N threading model. As can be seen in the benchmark results NGPT is the performance and scalability leader on both a 2-way and 4-way machine running this benchmark. The benchmark results can be found on the NGPT website. The benchmark itself can be downloaded from the Sun Microsystems site.

The NGPT website can be found at http://www-126.ibm.com/developerworks/opensource/pthreads.

AFAIK, yes, it was included in the Phoebe beta.

However, I also pretty sure that fixes have been made since then, so I would grab the latest glibc from cvs... This is unfortunately a better question for the glibc lists ;-)

https://listman.redhat.com/pipermail/phil-list/2003-January/000413.html lists what sources are needed for the latest nptl. Phoebe beta had a slightly earlier snapshot of nptl and glibc.

As far as the kernel goes, it's rumored (https://listman.redhat.com/pipermail/phil-list/2003-January/000419.html) that you're better off using a recent 2.5 kernel than the 2.4 backport in phoebe.

I haven't tried NPTL myself, though, so what do I know...

Trying to make releases slightly more often and slightly smaller.

ACPI, USB, networking (mainly netfilter) updates. Some syscall path updates and a thread bug in mm_release() that would miss updating the TID and cause a few extra traps at exec time.

And a watchdog forward port from 2.4.x by DaveJ.

introduction

a new linux project is soon to be announced and as part of the preparation for its launch, this is an invitation for the top linux and open source people to participate.

once announced, the project will be open to everyone, world-wide, to the benefit of linux and open source, and the advance participation of a few key people will help enormously to pave the way.

this message is therefore intended to reach, in what i believe to be an appropriate way (all things considered), the top linux developers and the most active and recognised open source advocates.

for those people who believe that this approach is inappropriate, i can only apologise in advance: please simply hit delete, now: (hit it _really_ hard - get it out your system, that's right :), and save everyone some further bandwidth.

please contact me direct

if you are one of the ten or so people that have received an email directly from me recently, and you read this first, i would greatly appreciate you taking the time to locate my message to you, or to email me at cb1.com for more information, if that is more appropriate.

advice sought on reaching the top linus and OS community leaders

if you know of any more appropriate forums, or any more appropriate methods by which the top linux developers and advocates and the pioneers of open source may be contacted

... bearing in mind that they are incredibly busy and receive hundreds of email messages per day...

i would love to hear from you (at my cb1.com address).

please help me contact the linux and OS community leaders

if you are personally in touch with, on a regular basis, one of the recognised leaders of the linux and open source communities, then i would greatly appreciate it if you could draw their attention to this message and also ask them to contact me at my cb1.com email address.

if you are NOT in touch with, on a regular and day-to-day basis, the recognised leaders of the linux and open source communities, please do NOT spam their inboxes irresponsibly with "oh, there's this guy who posted on the linux mailing lists who wanted to get in touch with you" style messages, you will only alienate them.

IF IN DOUBT SPAM ME, NOT THEM.

nominations

if you believe that someone, anywhere in the world, is a recognised leader in the open source community and is actively involved in promoting open source and linux, then please email me with:

• their name
• their email address and web site, and best contact method.
• whether you are willing to help assist in contacting them (you know them personally)
• references to some appropriate URLs that describe what they have achieved.

to everyone with the patience and time to read this far:

many, many thanks.

if you love linux and believe in open source, i believe that you will love the new project when it is announced and ready to launch.

Enclosed is an update to the sl82c105 driver against 2.4.21-pre3, I'll produce a 2.5 version once this is accepted by Alan.

It adds a pio_speed field to the generic IDE struct drive. This field is currently only used by this driver, not by the core, and stores the last used PIO speed for use when disabling DMA.

This patch fix the current oops caused by this driver on boot, along with other fixes & HW bugs workarounds by Russel King and me.

Alan, please send to Marcelo if you are ok. Currently tested on a briQ HW (one channel, one master disk).

Note that I intentionally stop force-enabling the second channel (the old driver did that) since this cause problems on machines with only one channel wired and no pull down resistor on D7. It's the responsibility of the BIOS or arch fixup of machines with 2 channels to properly set the enable bits for the second one. The first one is always assumed enabled for now (though I have nothing against changing that too).

Its still broken - if it uses DMA, the ide core will call ide_dma_on, which will call config_for_dma(), which will call ide_config_drive_speed, which will then call ide_dma_on, etc.

Sorry, I don't have a solution off hand for this. I just wish that the IDE core didn't change in these incompatible ways during a stable kernel release.

http://www.zip.com.au/~akpm/linux/patches/2.5/2.5.56/2.5.56-mm1/

Nothing much new here except for a fix for the ext3-related memory leak which Con reported recently.

The main items which remain unmerged from the -mm patch series are now:

• red/black-tree based insertion and sorting for the I/O scheduler.

  Jens will be submitting this next week. It's completely stable, and the patch includes the addition of the I/O scheduler tunables in /sys/block/hda/iosched/, which is fairly important.

• Code to automatically unplug request queues on the basis of their occupancy and a timeout.

  Jens will be reviewing this soon.

• dcache-RCU.

  This was recently updated to fix a rename race. It's quite stable. I'm not sure where we stand wrt merging it now. Al seems to have disappeared.

• Ingo Oeser's user page walking rework. This appears to be stable, although I'm not sure what testing it has had apart from a lot of direct-io testing.
• Quite a lot of misc stuff which I need to go through and either send or toss.

I talked to him in person last week, and this was one of the topics of discussion. He seemed to think it was fundamentally unfixable. He proceed to explain why, and then explained the scheme he worked out to improve things. Unfortunately my memory cannot do justice to the details.

Next time he explains it, I will write it down :)

Sorry for so lame a data point :)

The rename race is fixed now. Yes, it was unfixable using *existing* RCU techniques, but one has to invent new tricks when the old bag of tricks is empty :)

Fundamentally what happens is that rename may be *two* updates - delete from one hash chain and insert into another hash chain. In order for lockfree traversal to work correctly, you must have a grace period after each update. If we do a grace period between these two updates in a rename, it slows down renames to unacceptable levels. So we had a problem there.

The solution lies in the dcache itself - it has a fast path (cached_lookup) and a slow path (real_lookup). So all we had to do was to detect that a rename had happened to the dentry while we looked it up lockfree. This is done by a generation counter (d_move_count) in the dentry and is protected by the per-dentry spinlock which we take during rename and a successful cache lookup.

Two things can happen due to the rename race - lookup incorrectly succeeds or lookup incorrectly fails. The success case is easily handled by the lockfree lookup code.

If the lookup fails due to rename race, then there will anyway be a slow real_lookup which is serialized with rename.

Maneesh did a lot of testing using many ramfs and many millions of renames with millions of lookups going on at the same time and slow path was hit only 100 times or so. For practical workloads, this should have absolutely no performance impact.

Well, despite numerous setbacks, disasters and various panic-attacks, I've finally got a first draft together for documentation of the Linux VM. This is still incomplete but will hopefully still be a valuable resource to those wishing to understand the VM.

It is based on 2.4.20 as the 2.5.x one still changes too much too regularly to make documenting it feasible. I do believe though that having a good understanding of the 2.4.20 VM is 80% of the work to understanding the 2.5.x one at least. There is a few notable areas not covered yet but will be over the next month or two but I am releasing this early so I can start getting feedback and correcting any errors or poor assumptions now rather than later. The areas are;

• Swap area management (swap.c, swapfile.c etc)
• High memory management (highmem.c)
• Memory locking (mlock.c)
• Mem init (May not cover as it's very arch specific and there is docs out there on the subject already)
• Shared memory (May not cover this at all as it is really an IPC field)
• Buffer management (Same, except it's of more importance to IO)

The documentation comes in two parts. The first is "Understanding the Linux Virtual Memory Manager" and it does pretty much as described. It is available in three formats, PDF, HTML and plain text.

Understanding the Linux Virtual Memory Manager
PDF: http://www.csn.ul.ie/~mel/projects/vm/guide/pdf/understand.pdf
HTML: http://www.csn.ul.ie/~mel/projects/vm/guide/html/understand/
Text: http://www.csn.ul.ie/~mel/projects/vm/guide/text/understand.txt

The second part is a code commentary which is literally a guided tour through the code. It is intended to help decipher the more cryptic sections as well as identify the code patterns that are prevalent through the code. I decided to have the code separate from the first document as maintaining the code in the document would be too painful

Code Commentary on the Linux Virtual Memory Manager
PDF: http://www.csn.ul.ie/~mel/projects/vm/guide/pdf/code.pdf
HTML: http://www.csn.ul.ie/~mel/projects/vm/guide/html/code
Text: http://www.csn.ul.ie/~mel/projects/vm/guide/text/code.txt

Any feedback, comments or suggestions are welcome from anyone with a VM interest but I would appreciate if people already familiar with the VM would even give a brief read to check for technical accuracy. There was rarely an authoritative source to check to make sure I was right and I didn't want to be asking questions every 5 minutes on IRC or mailing lists :-)

I wasn't sure how suitable patches would be for documentation but I'll try anything once. A tar ball of the current tex source is at http://www.csn.ul.ie/~mel/projects/vm/guide/vm_book.tar.gz . There is a CVS tree but it's on a computer thats already heavily loaded so I don't want to have it hammered.

The tex sources are in tex/understand and tex/code . To create a DVI, simply ./make dvi . If you add "understand" or "code", it'll just generate that book.

Forgive if this has been discussed before, but has anyone considered hosting the linux-kernel on a web-based forum as used extensively elsewhere?

I can think of advantages;

Better Thread organisation and seperate topic areas for drivers, patches, ide, ...

Being able to cheery pick threads of interest, and completely ignore others Not having to dump your inbox after a week away just to catch up Moderated forums (Off-topic threads policed and deleted) Read only forums (write for registered/invited members)

I'm sure somebody will enlighten me regarding the disadvantages. :)

Web-based - pain in the ass to use. Especially for people who are not on-line all the time.

Moderated linux-kernel - lots of traffic, too much to be individually moderated.

Certainly the second has been discussed before many many many times.

People, please, if you think you have an damned obvious answer to a problem, at least check the many archives before posting it.

Let us *ALL* try to avoid linux-kernel turning into tens of trolling flamewars.

• Much slower than a local mailbox.
• No filtering.
• No choice of presentation (or not enough).
• No scoring.
• Much higher bandwidth needs.
• Hard to archive.
• Can't forward posts.
• Can't grep posts.
• Can't save some posts in a contiguous mailbox and patch -p1 them.

And the most annoying part, people feel anonymous on web forums and as a result post any crap just because they can, while most of tend to take having to put their email address with usually they real name in it more seriously.

I'm still on my accelerated release schedule, trying to make slightly smaller patches more frequently, instead of having humungous patches and having people forced to either wait or use the BK trees.

HOWEVER, that's going to change. I'm actually leaving for a two-week vacation on Friday, so not only will we have a lull in the merges due to that (I probably won't be on the 'net at all, since I'm travelling with my family), but I'll also have to slow down patches before leaving to try to leave with a fairly stable kernel.

While I'm away, I'm sure the regular suspects are going to work on merging stuff (Andrew & co), so it shouldn't be a big deal, but it still helps to not have major quakes just before going away for a while.

The 2.5.58 stuff is largely a merge of a lot of smaller stuff (tons of trivial patches, for example), with some bigger things: a parisc update, IPMI driver, USB updates, sysfs updates, and RPCSEC_GSS support.

http://www.zip.com.au/~akpm/linux/patches/2.5/2.5.58/2.5.58-mm1/

• Added an implementation of posix_fadvise().

  This can be used for providing the kernel hints about desired readahead patterns, and for launching asynchronous readahead (what sys_readahead does).

  But its main application is for program-directed freeing of pagecache against large streamed files. This is what O_STREAMING gives, only posix_fadvise() is harder to use, less efficient and standards-based.

  There is a test app in
  http://www.zip.com.au/~akpm/linux/patches/stuff/ext3-tools.tar.gz

• The direct-to-BIO readahead for reiserfs works fine.
• Ported one of Andrea's -aa patches into 2.5: merging of file-backed VMAs.