Muli Ben-Yehuda's journal

Yesterday was the first class of the summer course I’m taking at the Open University, “Algorithmics – Foundations of Computer Science”. When I registered, I was pretty excited about this class. It’s based on the book by Prof. David Harel of the Weizmann institute, that I’ve been meaning to read anyway. Then I got the book (openu edition) and read the first four chapters. While it’s written quite clearly and is interesting, it’s a popular science book, not a text book! there is nary a proof in sight, and the treatment of the material is quite superficial. Therefore, it was with some trepidation that I went to class yesterday. My feelings of foreboding (“is this fluff what I’m going to waste the summer on?”) weren’t helped when I heard class mates talking about this course, which is supposed to be a breeze to pass.

Then the instructor started talking, and within an hour into the lesson, I realized that my summer wasn’t going to be wasted after all. We discussed the “subset sum problem”, NP complete problems, the graph coloring problem and its relation to the map coloring problem[0], and the variations of knapsack problem. Unlike my usual habit, I actually took part in the class, proposing solutions and optimizations and finding flaws in others proposed solutions. Fascinating stuff!

[0] The instructor discussed graph coloring, and showed that any graph which is a clique of size N cannot be colored with less than N colors. This statement, which is obviously correct, contradicted with what I remembered about any map being 4 colorable. After thinking about it for a few minutes, I asked what was the relation between coloring a graph and coloring a map. The answer is that any map can be represented by a planar graph, but not every graph can be represented by a map. All planar graphs are indeed 4 colorable, and a clique of N > 4 cannot be represented by a planar map. Contradiction solved.

Just bought 4 tickets to the Haifa Symphony’s “Beethoven’s 9th Symphony” concert on Sunday next week. Happy happy joy joy!

After reading this great motivational piece again, I have a barely controllable urge to buy The Complete Guide to Navy SEAL Fitness, Revised Edition, by Steward Smith.

(as seen on /.)

Some guy is forking gentoo Linux, as far as I can see, because he expected to make money out of his involvement and didn’t. His manifest, and drobbins’s rebuttal. I couldn’t care less[0] who’s right, but it’s certainly amusing to read.

[0] Uhm, maybe I could care a little – drobbins strikes me as an honest person, while that Zach person reminds me of Moshe Bar, full of his own perceived importance.

Reading lwn.net’s weekly kernel page (subscribers only for this week, sorry), I ran across a link to the Object Based Reversed Mapping patch, aka objrmap. To summarize, objrmap differs from Rik van Riel’s rmap by tracking pte entries by page->mappging->vma, instead of special pte_chains. That left me curious, as I know that wli’s tree includes Anonymous objrmap, aka anobjrmap, which extends the objrmap implementation for anonymous pages, which don’t have an associated mapping! how does it work, then? Some googling later, I found Hugh Dickins’s anobjrmap patches (scroll down to memory management). Putting it very roughly, anobjrmap tracks anonymous pages by a new struct, anonmm, which is attached to the mm, and serves as the page’s mapping.

While I’m in a kernel mood, two more things: Peter Braam, one of the intermezzo hackers, CC’d me on a mail to Chen Yang, asking him to integrate my intermezzo patch of last night and send it on to Linus. Neat! Also, I wonder if the folks at work or haifux would be interested in a series of lectures on the 2.5 VM. A prerequisite for such a lecture is writing at least one reasonably sized VM patch, though.

intermezzo-stack-lossage-2.5.73.diff is tonight’s work. This patch reduces intermezzo’s stack usage in three functions. The kernel has limited stack space for functions, and functions which use 4kb and even 1kb of stack space are unacceptable. Against 2.5.73.

I don’t really expect this patch to get in, as the intermezzo people seem to be ignoring 2.5 for the time being. However, wli said he’s interested in it, as his tree uses 4kb stacks, and maybe someone else will find it interesting as well? other than the grunginess of the intermezzo code, it was fun to write. I should write more kernel code.

It gives me great pleasure to announce that the esteemed, the one and only, the fabulous, ladypine, has joined us.

*wild applause*

I have an lj code, the kind you need to get a free account, which needs a new home. I thought Orna might want it, but she doesn’t. Email or leave a comment and it’s yours – first come, first served.

1. shared page tables support, based on Dave McCracken’s work. wli is planning to do it, question is, can I do it sooner?

2. remove the big kernel lock from trident.c.

3. continue ongoing work with “don’t let slab caches grow beyond a given size”, and sysfsication of slab caches.

More ideas welcome…

One patch to fix a memory leak on an error path in tpam_queues.c made it into the just release 2.5.73 kernel, via the ISDN maintainer. The same fix should also show up in the next 2.4-pre kernel, via the same route.

I sent another patch to Marcelo, the 2.4 maintainer, to fix a b0rked configuration dependency between CONFIG_SOUND_TRIDENT and CONFIG_INPUT_PCIGAME. No response yet, neither from him nor on linux-kernel, but no bk commit has happened since then, so the jury is still out.